From 6ec3db1bb94a6eee55020b7fa4ac1ba8425a4b2d Mon Sep 17 00:00:00 2001 From: "matt@linuxbox.com" Date: Sat, 25 Jul 2009 14:10:25 -0400 Subject: [PATCH] MCAS changes from Matt Change static max allocators to 30. Add atomic add/sub macros returning original value, based on CASIO. Add interfaces to add and remove generic allocator caches. Add atomic inc/dec/sub macros using MCAS primitives. Add inline assembly for x86_64 and shim for Solaris (9+) atomic operations, providing Solaris x86 and alternate shim for Solaris Sparc. Set interface adapted for iteration and generalized for use with opaque key, value pointers. File cas_skip_func.c provides kv interface, cas_skip_adt.c provides kv interface, plus iteration on skip lists. Casual dependencies on stdio and exit() defined out. LICENSE BSD Reviewed-on: http://gerrit.openafs.org/214 Reviewed-by: Derrick Brashear Tested-by: Derrick Brashear --- src/mcas/Makefile.osi | 88 +++++ src/mcas/Makefile.unit | 111 +++++++ src/mcas/TODO | 27 ++ src/mcas/alpha_defns.h | 30 ++ src/mcas/amd64_defns.h | 165 ++++++++++ src/mcas/gc.c | 47 ++- src/mcas/gc.h | 30 ++ src/mcas/ia64_defns.h | 30 ++ src/mcas/intel_defns.h | 30 ++ src/mcas/mips_defns.h | 30 ++ src/mcas/osi_mcas_atomic.h | 80 +++++ src/mcas/osi_mcas_obj_cache.c | 54 ++++ src/mcas/osi_mcas_obj_cache.h | 26 ++ src/mcas/portable_defns.h | 74 ++++- src/mcas/ppc_defns.h | 30 ++ src/mcas/ptst.h | 27 ++ src/mcas/random.h | 28 ++ src/mcas/set.h | 30 ++ src/mcas/set_adt.h | 148 +++++++++ src/mcas/set_queue_adt.h | 162 ++++++++++ src/mcas/skip_adt_test.c | 346 ++++++++++++++++++++ src/mcas/skip_cas_adt.c | 571 +++++++++++++++++++++++++++++++++ src/mcas/skip_cas_func.c | 510 +++++++++++++++++++++++++++++ src/mcas/solaris_amd64_defns.h | 156 +++++++++ src/mcas/solaris_x86_defns.h | 154 +++++++++ src/mcas/sparc_defns.h | 30 ++ src/mcas/stm.h | 26 ++ 27 files changed, 3028 insertions(+), 12 deletions(-) create mode 100644 src/mcas/Makefile.osi create mode 100644 src/mcas/Makefile.unit create mode 100644 src/mcas/TODO create mode 100644 src/mcas/amd64_defns.h create mode 100644 src/mcas/osi_mcas_atomic.h create mode 100644 src/mcas/osi_mcas_obj_cache.c create mode 100644 src/mcas/osi_mcas_obj_cache.h create mode 100644 src/mcas/set_adt.h create mode 100644 src/mcas/set_queue_adt.h create mode 100644 src/mcas/skip_adt_test.c create mode 100644 src/mcas/skip_cas_adt.c create mode 100644 src/mcas/skip_cas_func.c create mode 100644 src/mcas/solaris_amd64_defns.h create mode 100644 src/mcas/solaris_x86_defns.h diff --git a/src/mcas/Makefile.osi b/src/mcas/Makefile.osi new file mode 100644 index 000000000..a4b47e304 --- /dev/null +++ b/src/mcas/Makefile.osi @@ -0,0 +1,88 @@ +# Including Makefile shall have set ARCH to one of: +# +# INTEL, X86_64, PPC, IA64, MIPS, SPARC, ALPHA +# + +ifeq ($(SYS_NAME),i386_linux24) +ARCH := INTEL +endif + +ifeq ($(SYS_NAME),i386_linux26) +ARCH := INTEL +endif + +ifeq ($(SYS_NAME),amd64_linux24) +ARCH := X86_64 +endif + +ifeq ($(SYS_NAME),amd64_linux26) +ARCH := X86_64 +endif + +ifeq ($(SYS_NAME),sunx86_510) +ARCH := SOLARIS_X86_686 +endif + +#ifeq ($(SYS_NAME),sunx86_510) +#ARCH := SOLARIS_X86_AMD64 +#endif + + +# TODO: more platforms, or find alternate mechanism. In particular, +# sparc handling will be inadequate + +DEBUGGING := -DNDEBUG + +ifeq ($(ARCH),INTEL) +CC := gcc +MCAS_CFLAGS := -g -O0 -DINTEL -fomit-frame-pointer -march=i686 +LDFLAGS := -lpthread +endif + +ifeq ($(ARCH),X86_64) +CC := gcc +MCAS_CFLAGS := -g -O0 -DX86_64 -fomit-frame-pointer -march=athlon64 +LDFLAGS := -lpthread +endif + +ifeq ($(ARCH),SOLARIS_X86_686) +MCAS_CFLAGS := -KPIC -DSOLARIS_X86_686 -xarch=pentium_pro +endif + +ifeq ($(ARCH),SOLARIS_X86_AMD64) +MCAS_CFLAGS := -KPIC -DSOLARIS_X86_AMD64 -xarch=amd64 +endif + +ifeq ($(ARCH),PPC) +CC := cc_r +MCAS_CFLAGS := -O3 -DPPC -q64 -w +LDFLAGS := -lpthread -q64 +ASFLAGS := -a64 +endif + +ifeq ($(ARCH),IA64) +CC := gcc +MCAS_CFLAGS := -O3 -DIA64 -fomit-frame-pointer +LDFLAGS := -lpthread +endif + +ifeq ($(ARCH),MIPS) +CC := gcc +MCAS_CFLAGS := -O3 -DMIPS -fomit-frame-pointer +LDFLAGS := -lpthread +endif + +ifeq ($(ARCH),SPARC) +CC := /opt/SUNWspro/bin/cc +MCAS_CFLAGS := -xO3 -DSPARC sparc_mcas.il -xarch=v9b +LDFLAGS := -DSPARC sparc_mcas.il -xarch=v9b -lthread -lrt +endif + +ifeq ($(ARCH),ALPHA) +CC := cc +MCAS_CFLAGS := -accept vaxc_keywords -O3 -DALPHA +MCAS_CFLAGS += -fomit-frame-pointer -DWEAK_MEM_ORDER +LDFLAGS := -lpthread +endif + +MCAS_CFLAGS += $(DEBUGGING) diff --git a/src/mcas/Makefile.unit b/src/mcas/Makefile.unit new file mode 100644 index 000000000..0cadcdaf2 --- /dev/null +++ b/src/mcas/Makefile.unit @@ -0,0 +1,111 @@ + +ARCH := X86_64 +DEBUGGING := -DNDEBUG + +ifeq ($(ARCH),INTEL) +CC := gcc +CFLAGS := -g -O0 -DINTEL -fomit-frame-pointer -march=i686 +LDFLAGS := -lpthread +endif + +ifeq ($(ARCH),X86_64) +CC := gcc +CFLAGS := -g -O0 -DX86_64 -fomit-frame-pointer -march=athlon64 +LDFLAGS := -lpthread +endif + +ifeq ($(ARCH),PPC) +CC := cc_r +CFLAGS := -O3 -DPPC -q64 -w +LDFLAGS := -lpthread -q64 +ASFLAGS := -a64 +endif + +ifeq ($(ARCH),IA64) +CC := gcc +CFLAGS := -O3 -DIA64 -fomit-frame-pointer +LDFLAGS := -lpthread +endif + +ifeq ($(ARCH),MIPS) +CC := gcc +CFLAGS := -O3 -DMIPS -fomit-frame-pointer +LDFLAGS := -lpthread +endif + +ifeq ($(ARCH),SPARC) +CC := /opt/SUNWspro/bin/cc +CFLAGS := -xO3 -DSPARC sparc_mcas.il -xarch=v9b +LDFLAGS := -DSPARC sparc_mcas.il -xarch=v9b -lthread -lrt +endif + +ifeq ($(ARCH),ALPHA) +CC := cc +CFLAGS := -accept vaxc_keywords -O3 -DALPHA +CFLAGS += -fomit-frame-pointer -DWEAK_MEM_ORDER +LDFLAGS := -lpthread +endif + +CFLAGS += $(DEBUGGING) +COMMON_DEPS += Makefile $(wildcard *.h) + +GC_HARNESS_TARGETS := skip_lock_perlist skip_lock_pernode skip_lock_perpointer +GC_HARNESS_TARGETS += skip_cas skip_mcas + +GC_HARNESS_TARGETS += bst_lock_fraser bst_lock_manber bst_lock_kung +GC_HARNESS_TARGETS += bst_mcas + +GC_HARNESS_TARGETS += rb_lock_concurrentwriters rb_lock_serialisedwriters +GC_HARNESS_TARGETS += rb_lock_mutex + +TARGETS := $(GC_HARNESS_TARGETS) +TARGETS += rb_stm_fraser rb_stm_herlihy rb_stm_lock +TARGETS += skip_stm_fraser skip_stm_herlihy skip_stm_lock + +all: skip_cas_adt_test + +skip_cas_adt_test: skip_adt_test.o skip_cas_adt.o gc.o ptst.o + $(CC) $(CFLAGS) -o $@ \ + skip_cas_adt.o gc.o ptst.o skip_adt_test.o \ + $(LDFLAGS) + +skip_cas_adt.o: skip_cas_adt.c + $(CC) $(CFLAGS) -c -o $@ $< + +clean: + rm -f $(TARGETS) replay *~ core *.o *.a + +replay: %: %.c $(COMMON_DEPS) + $(CC) $(CFLAGS) -c -o $(patsubst %.c,%.o,$<) $< + $(CC) -o $@ $(patsubst %.c,%.o,$<) $(LDFLAGS) + +tree_mcas.o: tree_mcas.c mcas.c $(COMMON_DEPS) + $(CC) $(CFLAGS) -c -o $@ $< +skip_lock_perpointer.o: skip_lock.c $(COMMON_DEPS) + $(CC) $(CFLAGS) -DTINY_MTX -c -o $@ $< +skip_lock_pernode.o: skip_lock.c $(COMMON_DEPS) + $(CC) $(CFLAGS) -c -o $@ $< +skip_lock_perlist.o: skip_lock.c $(COMMON_DEPS) + $(CC) $(CFLAGS) -DFAT_MTX -c -o $@ $< +skip_mcas.o: skip_mcas.c mcas.c $(COMMON_DEPS) + $(CC) $(CFLAGS) -c -o $@ $< + +%.o: %.c $(COMMON_DEPS) + $(CC) $(CFLAGS) -c -o $@ $< + +skip_stm_lock: skip_stm.o stm_lock.o set_harness.o ptst.o gc.o + $(CC) -o $@ $^ $(LDFLAGS) +skip_stm_fraser: skip_stm.o stm_fraser.o set_harness.o ptst.o gc.o + $(CC) -o $@ $^ $(LDFLAGS) +skip_stm_herlihy: skip_stm.o stm_herlihy.o set_harness.o ptst.o gc.o + $(CC) -o $@ $^ $(LDFLAGS) + +rb_stm_lock: rb_stm.o stm_lock.o set_harness.o ptst.o gc.o + $(CC) -o $@ $^ $(LDFLAGS) +rb_stm_fraser: rb_stm.o stm_fraser.o set_harness.o ptst.o gc.o + $(CC) -o $@ $^ $(LDFLAGS) +rb_stm_herlihy: rb_stm.o stm_herlihy.o set_harness.o ptst.o gc.o + $(CC) -o $@ $^ $(LDFLAGS) + +$(GC_HARNESS_TARGETS): %: %.o set_harness.o ptst.o gc.o + $(CC) -o $@ $^ $(LDFLAGS) diff --git a/src/mcas/TODO b/src/mcas/TODO new file mode 100644 index 000000000..6e3805b3e --- /dev/null +++ b/src/mcas/TODO @@ -0,0 +1,27 @@ +Todo List + +* Adapt more implementations to take opaque key data and a comparison + function, as in set_func.h, skip_cas_func.c + +* Adapt implementations for use in various kernels + +* Implement key-pointer/comparison function versions of more structures, in + particular, trees + +Desired Additions + +* It would be attractive to develop an implementation of the priority queue + implementation described in + + H. Sundell and P. Tsigas, “Fast and Lock-Free Concurrent Priority + Queues for Multi-Thread Systems,” in Proceedings of the 17th Inter- + national Parallel and Distributed Processing Symposium, 11 pp., IEEE + press, Apr. 2003. + + (A more up-to-date description is available in the Ph.D. thesis of H°akan + Sundell, Ch. 5.) + +* It would be interesting to compare the CAS skiplist implementation here with + that in the H°akan Sundell thesis, Ch. 6, which claims to have better + efficiency + diff --git a/src/mcas/alpha_defns.h b/src/mcas/alpha_defns.h index f74558cf7..75e07dda8 100644 --- a/src/mcas/alpha_defns.h +++ b/src/mcas/alpha_defns.h @@ -1,3 +1,33 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __ALPHA_DEFNS_H__ #define __ALPHA_DEFNS_H__ diff --git a/src/mcas/amd64_defns.h b/src/mcas/amd64_defns.h new file mode 100644 index 000000000..a5d79cebc --- /dev/null +++ b/src/mcas/amd64_defns.h @@ -0,0 +1,165 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef __INTEL_DEFNS_H__ +#define __INTEL_DEFNS_H__ + +#include +#include + +#ifndef X86_64 +#define X86_64 +#endif + +#define CACHE_LINE_SIZE 64 + +#if 0 +#define pthread_mutex_init(_m,_i) \ +({ pthread_mutex_init(_m,_i); (_m)->__m_kind = PTHREAD_MUTEX_ADAPTIVE_NP; }) +#endif + + +/* + * I. Compare-and-swap. + */ + +/* + * This is a strong barrier! Reads cannot be delayed beyond a later store. + * Reads cannot be hoisted beyond a LOCK prefix. Stores always in-order. + */ +#define CAS32(_a, _o, _n) \ +({ __typeof__(_o) __o = _o; \ + __asm__ __volatile__( \ + "lock cmpxchg %3,%1" \ + : "=a" (__o), "=m" (*(volatile unsigned int *)(_a)) \ + : "0" (__o), "r" (_n) ); \ + __o; \ +}) + +#define FAS32(_a, _n) \ +({ __typeof__(_n) __o; \ + __asm__ __volatile__( \ + "lock xchg %0,%1" \ + : "=r" (__o), "=m" (*(volatile unsigned int *)(_a)) \ + : "0" (_n) ); \ + __o; \ +}) + +#define FAS64(_a, _n) \ + ({ __typeof__(_n) __o; \ + __asm__ __volatile__( \ + "xchgq %0,%1" \ + : "=r" (__o), "=m" (*(volatile unsigned long long *)(_a)) \ + : "0" (_n) \ + ); \ + __o; \ +}) + +/* Valid, but not preferred */ +#define CAS64_x86_style(_a, _o, _n) \ +({ __typeof__(_o) __o = _o; \ + __asm__ __volatile__( \ + "movl %3, %%ecx;" \ + "movl %4, %%ebx;" \ + "lock cmpxchg8b %1" \ + : "=A" (__o), "=m" (*(volatile unsigned long long *)(_a)) \ + : "0" (__o), "m" (_n >> 32), "m" (_n) \ + : "ebx", "ecx" ); \ + __o; \ +}) + +#define CAS64(_a, _o, _n) \ + ({ __typeof__(_o) __o = _o; \ + __asm__ __volatile__ ("lock cmpxchgq %1,%2" \ + : "=a" (__o) \ + :"r" (_n), \ + "m" (*(volatile unsigned long long *)(_a)), \ + "0" (__o) \ + : "memory"); \ + __o; \ + }) + +#define CAS(_x,_o,_n) ((sizeof (*_x) == 4)?CAS32(_x,_o,_n):CAS64(_x,_o,_n)) +#define FAS(_x,_n) ((sizeof (*_x) == 4)?FAS32(_x,_n) :FAS64(_x,_n)) + +/* Update Integer location, return Old value. */ +#define CASIO CAS +#define FASIO FAS +/* Update Pointer location, return Old value. */ +#define CASPO CAS64 +#define FASPO FAS64 +/* Update 32/64-bit location, return Old value. */ +#define CAS32O CAS +#define CAS64O CAS64 + +/* + * II. Memory barriers. + * WMB(): All preceding write operations must commit before any later writes. + * RMB(): All preceding read operations must commit before any later reads. + * MB(): All preceding memory accesses must commit before any later accesses. + * + * If the compiler does not observe these barriers (but any sane compiler + * will!), then VOLATILE should be defined as 'volatile'. + */ + +#define MB() __asm__ __volatile__("" : : : "memory") +#define WMB() MB() +#define RMB() MB() +#define VOLATILE /*volatile */ + +/* On Intel, CAS is a strong barrier, but not a compile barrier. */ +#define RMB_NEAR_CAS() WMB() +#define WMB_NEAR_CAS() WMB() +#define MB_NEAR_CAS() WMB() + + +/* + * III. Cycle counter access. + */ + +typedef unsigned long long tick_t; + +#define RDTICK() \ + ({ unsigned __a, __d; tick_t __t; \ + __asm__ __volatile__ ("rdtsc" : "=a" (__a), "=d" (__d)); \ + __t=((unsigned long long) __a) | (((unsigned long long) __d) << 32); \ + __t; }) + + +/* + * IV. Types. + */ + +typedef unsigned char _u8; +typedef unsigned short _u16; +typedef unsigned int _u32; +typedef unsigned long long _u64; + +#endif /* __INTEL_DEFNS_H__ */ diff --git a/src/mcas/gc.c b/src/mcas/gc.c index f5445c4b3..602372299 100644 --- a/src/mcas/gc.c +++ b/src/mcas/gc.c @@ -42,6 +42,7 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include #include "portable_defns.h" #include "gc.h" +#include /*#define MINIMAL_GC*/ /*#define YIELD_TO_HELP_PROGRESS*/ @@ -51,8 +52,9 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #define INVALID_BYTE 0 #define INITIALISE_NODES(_p,_c) memset((_p), INVALID_BYTE, (_c)); -/* Number of unique block sizes we can deal with. */ -#define MAX_SIZES 20 +/* Number of unique block sizes we can deal with. Equivalently, the + * number of unique object caches which can be created. */ +#define MAX_SIZES 30 #define MAX_HOOKS 4 @@ -108,6 +110,10 @@ static struct gc_global_st VOLATILE unsigned int inreclaim; CACHE_PAD(2); + + /* Allocator caches currently defined */ + long n_allocators; + /* * RUN-TIME CONSTANTS (to first approximation) */ @@ -172,13 +178,15 @@ struct gc_st chunk_t *hook[NR_EPOCHS][MAX_HOOKS]; }; +/* XXX generalize */ +#ifndef KERNEL -#define MEM_FAIL(_s) \ -do { \ +#define MEM_FAIL(_s) \ +do { \ fprintf(stderr, "OUT OF MEMORY: %d bytes at line %d\n", (_s), __LINE__); \ - exit(1); \ + abort(); \ } while ( 0 ) - +#endif /* Allocate more empty chunks from the heap. */ #define CHUNKS_PER_ALLOC 1000 @@ -447,6 +455,11 @@ void *gc_alloc(ptst_t *ptst, int alloc_id) return ch->blk[--ch->i]; } +int +gc_get_blocksize(int alloc_id) +{ + return (gc_global.blk_sizes[alloc_id]); +} static chunk_t *chunk_from_cache(gc_t *gc) { @@ -617,11 +630,25 @@ gc_t *gc_init(void) } -int gc_add_allocator(int alloc_size) +int +gc_add_allocator(int alloc_size) { - int ni, i = gc_global.nr_sizes; - while ( (ni = CASIO(&gc_global.nr_sizes, i, i+1)) != i ) i = ni; - gc_global.blk_sizes[i] = alloc_size; + int ni, i; + + RMB(); + FASPO(&gc_global.n_allocators, gc_global.n_allocators + 1); + if (gc_global.n_allocators > MAX_SIZES) { + /* critical error */ +#if !defined(KERNEL) + printf("MCAS gc max allocators exceeded, aborting\n"); +#endif + abort(); + } + + i = gc_global.nr_sizes; + while ((ni = CASIO(&gc_global.nr_sizes, i, i + 1)) != i) + i = ni; + gc_global.blk_sizes[i] = alloc_size; gc_global.alloc_size[i] = ALLOC_CHUNKS_PER_LIST; gc_global.alloc[i] = get_filled_chunks(ALLOC_CHUNKS_PER_LIST, alloc_size); return i; diff --git a/src/mcas/gc.h b/src/mcas/gc.h index 962e1aa30..4872e0a6a 100644 --- a/src/mcas/gc.h +++ b/src/mcas/gc.h @@ -1,3 +1,33 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __GC_H__ #define __GC_H__ diff --git a/src/mcas/ia64_defns.h b/src/mcas/ia64_defns.h index 7413b1b14..3a9544737 100644 --- a/src/mcas/ia64_defns.h +++ b/src/mcas/ia64_defns.h @@ -1,3 +1,33 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __IA64_DEFNS_H__ #define __IA64_DEFNS_H__ diff --git a/src/mcas/intel_defns.h b/src/mcas/intel_defns.h index fcdb03d7d..970ba26db 100644 --- a/src/mcas/intel_defns.h +++ b/src/mcas/intel_defns.h @@ -1,3 +1,33 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __INTEL_DEFNS_H__ #define __INTEL_DEFNS_H__ diff --git a/src/mcas/mips_defns.h b/src/mcas/mips_defns.h index 7fc120682..28dd78d28 100644 --- a/src/mcas/mips_defns.h +++ b/src/mcas/mips_defns.h @@ -1,3 +1,33 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __MIPS_DEFNS_H__ #define __MIPS_DEFNS_H__ diff --git a/src/mcas/osi_mcas_atomic.h b/src/mcas/osi_mcas_atomic.h new file mode 100644 index 000000000..e0d843f8a --- /dev/null +++ b/src/mcas/osi_mcas_atomic.h @@ -0,0 +1,80 @@ +/* + * Copyright (c) 2008-2009 + * The Linux Box Corporation + * ALL RIGHTS RESERVED + * + * Permission is granted to use, copy, create derivative works + * and redistribute this software and such derivative works + * for any purpose, so long as the name of the Linux Box + * Corporation is not used in any advertising or publicity + * pertaining to the use or distribution of this software + * without specific, written prior authorization. If the + * above copyright notice or any other identification of the + * Linux Box Corporation is included in any copy of any + * portion of this software, then the disclaimer below must + * also be included. + * + * This software is provided as is, without representation + * from the Linux Box Corporation as to its fitness for any + * purpose, and without warranty by the Linux Box Corporation + * of any kind, either express or implied, including + * without limitation the implied warranties of + * merchantability and fitness for a particular purpose. The + * regents of the Linux Box Corporation shall not be liable + * for any damages, including special, indirect, incidental, or + * consequential damages, with respect to any claim arising + * out of or in connection with the use of the software, even + * if it has been or is hereafter advised of the possibility of + * such damages. + */ + +#ifndef OSI_MCAS_ATOMIC_H +#define OSI_MCAS_ATOMIC_H + +#include "portable_defns.h" /* FASPO, CASIO, etc. */ + +#define CASIO_ATOMICS 1 + +typedef unsigned long osi_atomic_t; + + +#if CASIO_ATOMICS + +#warning Compiling with new CASIO atomic inc/dec + +/* these update in place, discarding the result */ +#define osi_atomic_inc(x) ADD_TO((x), 1UL) +#define osi_atomic_dec(x) SUB_FROM((x), 1UL) +#define osi_atomic_dec_n(x, n) SUB_FROM((x), (n)) + +/* these return the old value of x when the update succeeds */ +#define osi_atomic_add_n_r(x, n, r) ADD_TO_RETURNING_OLD((x), (n), (r)) +#define osi_atomic_sub_n_r(x, n, r) SUB_FROM_RETURNING_OLD((x), (n), (r)) +#define osi_atomic_inc_r(x, r) ADD_TO_RETURNING_OLD((x), 1UL, (r)) +#define osi_atomic_dec_r(x, r) SUB_FROM_RETURNING_OLD((x), 1UL, (r)) + +#else + +#warning Compiling with FASPO and RMB() atomic inc/dec + +#define osi_atomic_inc(x) \ +do { \ + RMB(); \ + FASPO(&x, x+1); \ +} while(0); + +#define osi_atomic_dec(x) \ +do { \ + RMB(); \ + FASPO(&x, x-1); \ +} while(0); + +#define osi_atomic_dec_n(x, n) \ +do { \ + RMB(); \ + FASPO(&x, x-n); \ +} while(0); + +#endif /* old atomics */ + +#endif /* OSI_MCAS_ATOMIC_H */ diff --git a/src/mcas/osi_mcas_obj_cache.c b/src/mcas/osi_mcas_obj_cache.c new file mode 100644 index 000000000..963962036 --- /dev/null +++ b/src/mcas/osi_mcas_obj_cache.c @@ -0,0 +1,54 @@ +#include "osi_mcas_obj_cache.h" +#include + +void +osi_mcas_obj_cache_create(osi_mcas_obj_cache_t * gc_id, size_t size) +{ + ViceLog(7, + ("osi_mcas_obj_cache_create: size, adjsize %d\n", size, + size + sizeof(int *))); + + *(int *)gc_id = gc_add_allocator(size + sizeof(int *)); +} + +void gc_trace(int alloc_id); +int gc_get_blocksize(int alloc_id); + +void * +osi_mcas_obj_cache_alloc(osi_mcas_obj_cache_t gc_id) +{ + ptst_t *ptst; + void *obj; + +#if MCAS_ALLOC_DISABLED +#warning XXXXX mcas allocator cache is DISABLED for debugging!! + obj = malloc(gc_get_blocksize(gc_id)); +#else + ptst = critical_enter(); + obj = (void *)gc_alloc(ptst, gc_id); + critical_exit(ptst); +#endif + return (obj); +} + +void +osi_mcas_obj_cache_free(osi_mcas_obj_cache_t gc_id, void *obj) +{ + ptst_t *ptst; + +#if MCAS_ALLOC_DISABLED +#warning XXXXX mcas allocator cache is DISABLED for debugging!! +#else + ptst = critical_enter(); + gc_free(ptst, (void *)obj, gc_id); + critical_exit(ptst); +#endif +} + +void +osi_mcas_obj_cache_destroy(osi_mcas_obj_cache_t gc_id) +{ + /* TODO: implement, will need to implement gc_remove_allocator and related + * modifications in gc.c */ + return; +} diff --git a/src/mcas/osi_mcas_obj_cache.h b/src/mcas/osi_mcas_obj_cache.h new file mode 100644 index 000000000..b02e200d7 --- /dev/null +++ b/src/mcas/osi_mcas_obj_cache.h @@ -0,0 +1,26 @@ + +#ifndef __OSI_MCAS_OBJ_CACHE_H +#define __OSI_MCAS_OBJ_CACHE_H + +#include "../mcas/portable_defns.h" +#include "../mcas/ptst.h" +#include "../mcas/gc.h" + +typedef int osi_mcas_obj_cache_t; + +/* Create a new MCAS GC pool, and return its identifier, which + * follows future calls */ +void osi_mcas_obj_cache_create(osi_mcas_obj_cache_t * gc_id, size_t size); /* alignment? */ + +/* Allocate an object from the pool identified by + * gc_id */ +void *osi_mcas_obj_cache_alloc(osi_mcas_obj_cache_t gc_id); + +/* Release object obj to its GC pool, identified by + * gc_id */ +void osi_mcas_obj_cache_free(osi_mcas_obj_cache_t gc_id, void *obj); + +/* Terminate an MCAS GC pool */ +void osi_mcas_obj_cache_destroy(osi_mcas_obj_cache_t gc_id); + +#endif /* __OSI_MCAS_OBJ_CACHE_H */ diff --git a/src/mcas/portable_defns.h b/src/mcas/portable_defns.h index fb1c246e0..19a4b6653 100644 --- a/src/mcas/portable_defns.h +++ b/src/mcas/portable_defns.h @@ -1,12 +1,48 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __PORTABLE_DEFNS_H__ #define __PORTABLE_DEFNS_H__ -#define MAX_THREADS 128 /* Nobody will ever have more! */ +#define MAX_THREADS 256 /* Nobody will ever have more! */ #if defined(SPARC) #include "sparc_defns.h" +#elif defined(SOLARIS_X86_686) +#include "solaris_x86_defns.h" +#elif defined(SOLARIS_X86_AMD64) +#include "solaris_amd64_defns.h" #elif defined(INTEL) #include "intel_defns.h" +#elif defined(X86_64) +#include "amd64_defns.h" #elif defined(PPC) #include "ppc_defns.h" #elif defined(IA64) @@ -29,7 +65,6 @@ typedef unsigned long int_addr_t; -typedef int bool_t; #define FALSE 0 #define TRUE 1 @@ -40,6 +75,34 @@ do { \ __val = __newval; \ } while ( 0 ) +/* new 'returning' versions allow use of old value at the successful + * CAS update (Matt). This allows an atomic inc to know if it was, for + * example, the operation which uniquely incremented _v from 0 to 1, and + * all equivalent threshold assertions */ + +#define ADD_TO_RETURNING_OLD(_v,_x,_o) \ +do { \ + int __val = (_v), __newval; \ + while ( (__newval = CASIO(&(_v),__val,__val+(_x))) != __val ) \ + __val = __newval; \ + _o = __val; \ +} while ( 0 ) + +#define SUB_FROM(_v,_x) \ +do { \ + int __val = (_v), __newval; \ + while ( (__newval = CASIO(&(_v),__val,__val-(_x))) != __val ) \ + __val = __newval; \ +} while ( 0 ) + +#define SUB_FROM_RETURNING_OLD(_v,_x,_o) \ +do { \ + int __val = (_v), __newval; \ + while ( (__newval = CASIO(&(_v),__val,__val-(_x))) != __val ) \ + __val = __newval; \ + _o = __val; \ +} while ( 0 ) + /* * Allow us to efficiently align and pad structures so that shared fields * don't cause contention on thread-local or read-only fields. @@ -99,6 +162,8 @@ do { \ #endif +#if !defined(INTEL) && !defined(SOLARIS_X86_686) && !defined(SOLARIS_X86_AMD64) && !defined(X86_64) + /* * Strong LL/SC operations */ @@ -120,6 +185,8 @@ static _u32 strong_ll(_u64 *ptr, int p) return (_u32) (val_read >> 32); } +#endif /* !INTEL */ + static int strong_vl(_u64 *ptr, int p) { @@ -132,6 +199,7 @@ static int strong_vl(_u64 *ptr, int p) return (val_read & flag); } +#if !defined(INTEL) && !defined(X86_64) static int strong_sc(_u64 *ptr, int p, _u32 n) { _u64 val_read; @@ -155,6 +223,8 @@ static int strong_sc(_u64 *ptr, int p, _u32 n) return 0; } +#endif /* !INTEL */ + static void s_store(_u64 *ptr, _u32 n) { diff --git a/src/mcas/ppc_defns.h b/src/mcas/ppc_defns.h index c52def995..17658060c 100644 --- a/src/mcas/ppc_defns.h +++ b/src/mcas/ppc_defns.h @@ -1,3 +1,33 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __PPC_DEFNS_H__ #define __PPC_DEFNS_H__ diff --git a/src/mcas/ptst.h b/src/mcas/ptst.h index 8e6e30874..c56984424 100644 --- a/src/mcas/ptst.h +++ b/src/mcas/ptst.h @@ -4,6 +4,33 @@ * Per-thread state management. * * Copyright (c) 2002-2003, K A Fraser +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef __PTST_H__ diff --git a/src/mcas/random.h b/src/mcas/random.h index 9a4826ff1..4eb480dff 100644 --- a/src/mcas/random.h +++ b/src/mcas/random.h @@ -3,6 +3,34 @@ * * A really simple random-number generator. Crappy linear congruential * taken from glibc, but has at least a 2^32 period. + +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef __RANDOM_H__ diff --git a/src/mcas/set.h b/src/mcas/set.h index 8e521f2a5..3c80e1531 100644 --- a/src/mcas/set.h +++ b/src/mcas/set.h @@ -1,3 +1,33 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __SET_H__ #define __SET_H__ diff --git a/src/mcas/set_adt.h b/src/mcas/set_adt.h new file mode 100644 index 000000000..69fe9f07f --- /dev/null +++ b/src/mcas/set_adt.h @@ -0,0 +1,148 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/****************************************************************************** + * set_func.h + * + * Matt Benjamin + * + * Adapts MCAS set interface to use a pointer-key and typed comparison + * function style (because often, your key isn't an integer). + * + * Caution, pointer values 0x0, 0x01, and 0x02 are reserved. Fortunately, + * no real pointer is likely to have one of these values. + * + */ + +#ifndef __SET_ADT_H__ +#define __SET_ADT_H__ + + +typedef void *setkey_t; +typedef void *setval_t; + + +#ifdef __SET_IMPLEMENTATION__ + +/************************************* + * INTERNAL DEFINITIONS + */ + +/* Fine for 2^NUM_LEVELS nodes. */ +#define NUM_LEVELS 20 + + +/* Internal key values with special meanings. */ +#define INVALID_FIELD (0) /* Uninitialised field value. */ +#define SENTINEL_KEYMIN ( 1UL) /* Key value of first dummy node. */ +#define SENTINEL_KEYMAX (~0UL) /* Key value of last dummy node. */ + + +/* + * SUPPORT FOR WEAK ORDERING OF MEMORY ACCESSES + */ + +#ifdef WEAK_MEM_ORDER + +/* Read field @_f into variable @_x. */ +#define READ_FIELD(_x,_f) \ +do { \ + (_x) = (_f); \ + if ( (_x) == INVALID_FIELD ) { RMB(); (_x) = (_f); } \ + assert((_x) != INVALID_FIELD); \ +} while ( 0 ) + +#else + +/* Read field @_f into variable @_x. */ +#define READ_FIELD(_x,_f) ((_x) = (_f)) + +#endif + + +#else + +/************************************* + * PUBLIC DEFINITIONS + */ + +/* + * Key range accepted by set functions. + * We lose three values (conveniently at top end of key space). + * - Known invalid value to which all fields are initialised. + * - Sentinel key values for up to two dummy nodes. + */ +#define KEY_MIN ( 0U) +#define KEY_MAX ((~0U) - 3) + +typedef void set_t; /* opaque */ + +/* Set element comparison function */ +typedef int (*osi_set_cmp_func) (const void *lhs, const void *rhs); + +/* One-time initialize set adt package */ +void _init_set_subsystem(void); + +/* + * Allocate an empty set. + * + * @cmpf - function to compare two keys, it must return an integer + * less than, equal to, or greater than 0 if 1st argument + * orders less than, equal to, or greater than the 2nd, as + * in qsort(3) + */ +set_t *set_alloc(osi_set_cmp_func cmpf); + +/* + * Add mapping (@k -> @v) into set @s. Return previous mapped value if + * one existed, or NULL if no previous mapping for @k existed. + * + * If @overwrite is FALSE, then if a mapping already exists it is not + * modified, and the existing value is returned unchanged. It is possible + * to see if the value was changed by observing if the return value is NULL. + */ +setval_t set_update(set_t * s, setkey_t k, setval_t v, int overwrite); + +/* + * Remove mapping for key @k from set @s. Return value associated with + * removed mapping, or NULL is there was no mapping to delete. + */ +setval_t set_remove(set_t * s, setkey_t k); + +/* + * Look up mapping for key @k in set @s. Return value if found, else NULL. + */ +setval_t set_lookup(set_t * s, setkey_t k); + + +#endif /* __SET_IMPLEMENTATION__ */ + + +#endif /* __SET_ADT_H__ */ diff --git a/src/mcas/set_queue_adt.h b/src/mcas/set_queue_adt.h new file mode 100644 index 000000000..303746e24 --- /dev/null +++ b/src/mcas/set_queue_adt.h @@ -0,0 +1,162 @@ +/****************************************************************************** + * set_queue_adt.h + * + * Matt Benjamin + * + * Adapts MCAS set interface to use a pointer-key and typed comparison + * function style (because often, your key isn't an integer). + * + * Also, set_for_each (and future additions) allow a set to be iterated. + * Current set_for_each iteration is unordered. + * + * Caution, pointer values 0x0, 0x01, and 0x02 are reserved. Fortunately, + * no real pointer is likely to have one of these values. + * + +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef __SET_ADT_H__ +#define __SET_ADT_H__ + + +typedef void *setkey_t; +typedef void *setval_t; + + +#ifdef __SET_IMPLEMENTATION__ + + +/************************************* + * INTERNAL DEFINITIONS + */ + +/* Fine for 2^NUM_LEVELS nodes. */ +#define NUM_LEVELS 20 +//#define NUM_LEVELS 19 + + +/* Internal key values with special meanings. */ +#define INVALID_FIELD (0) /* Uninitialised field value. */ +#define SENTINEL_KEYMIN ( 1UL) /* Key value of first dummy node. */ +#define SENTINEL_KEYMAX (~0UL) /* Key value of last dummy node. */ + + +/* + * SUPPORT FOR WEAK ORDERING OF MEMORY ACCESSES + */ + +#ifdef WEAK_MEM_ORDER + +/* Read field @_f into variable @_x. */ +#define READ_FIELD(_x,_f) \ +do { \ + (_x) = (_f); \ + if ( (_x) == INVALID_FIELD ) { RMB(); (_x) = (_f); } \ + assert((_x) != INVALID_FIELD); \ +} while ( 0 ) + +#else + +/* Read field @_f into variable @_x. */ +#define READ_FIELD(_x,_f) ((_x) = (_f)) + +#endif + + +#else + +/************************************* + * PUBLIC DEFINITIONS + */ + +/* + * Key range accepted by set functions. + * We lose three values (conveniently at top end of key space). + * - Known invalid value to which all fields are initialised. + * - Sentinel key values for up to two dummy nodes. + */ +#define KEY_MIN ( 0U) +#define KEY_MAX ((~0U) - 3) + +typedef void osi_set_t; /* opaque */ + +/* Set element comparison function */ +typedef int (*osi_set_cmp_func) (const void *lhs, const void *rhs); + +/* Each-element function passed to set_for_each */ +typedef void (*osi_set_each_func) (osi_set_t * l, setval_t v, void *arg); + +void _init_osi_cas_skip_subsystem(void); + +/* + * Allocate an empty set. + * + * @cmpf - function to compare two keys, it must return an integer + * less than, equal to, or greater than 0 if 1st argument + * orders less than, equal to, or greater than the 2nd, as + * in qsort(3) + */ +osi_set_t *osi_cas_skip_alloc(int (*cmpf) (const void *, const void *)); + +/* + * Add mapping (@k -> @v) into set @s. Return previous mapped value if + * one existed, or NULL if no previous mapping for @k existed. + * + * If @overwrite is FALSE, then if a mapping already exists it is not + * modified, and the existing value is returned unchanged. It is possible + * to see if the value was changed by observing if the return value is NULL. + */ +setval_t osi_cas_skip_update(osi_set_t * s, setkey_t k, setval_t v, + int overwrite); + +/* + * Remove mapping for key @k from set @s. Return value associated with + * removed mapping, or NULL is there was no mapping to delete. + */ +setval_t osi_cas_skip_remove(osi_set_t * s, setkey_t k); + +/* + * Look up mapping for key @k in set @s. Return value if found, else NULL. + */ +setval_t osi_cas_skip_lookup(osi_set_t * s, setkey_t k); + + +/* Hybrid Set/Queue Operations (Matt) */ + +/* Iterate over a sequential structure, calling callback_func + * on each (undeleted) element visited. Unordered. + */ +void osi_cas_skip_for_each(osi_set_t * l, osi_set_each_func each_func, + void *arg); + +#endif /* __SET_IMPLEMENTATION__ */ + + +#endif /* __SET_ADT_H__ */ diff --git a/src/mcas/skip_adt_test.c b/src/mcas/skip_adt_test.c new file mode 100644 index 000000000..b174bca23 --- /dev/null +++ b/src/mcas/skip_adt_test.c @@ -0,0 +1,346 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +/* for mutex testing */ +#include + +#include "portable_defns.h" +#include "set_queue_adt.h" +#include "ptst.h" + +#define CREATE_N 1000000 + +#define SENTINEL_KEYMIN ( 1UL) +#define SENTINEL_KEYMAX (~0UL) + +typedef struct { + unsigned long key; + unsigned long secret_key; + unsigned long xxx[10]; + int traversal; + pthread_mutex_t lock; + void *gc_id; +} harness_ulong_t; + +static struct { + CACHE_PAD(0); + osi_set_t *set; + CACHE_PAD(1); + osi_set_t *set2; + CACHE_PAD(2); +} shared; + +/* lock-free object cache */ + +typedef int osi_mcas_obj_cache_t; + +void +osi_mcas_obj_cache_create(osi_mcas_obj_cache_t * gc_id, size_t size) +{ /* alignment? */ + *(int *)gc_id = gc_add_allocator(size + sizeof(int *)); +} + +void * +osi_mcas_obj_cache_alloc(osi_mcas_obj_cache_t gc_id) +{ + ptst_t *ptst; + void *obj; + + ptst = critical_enter(); + obj = (void *)gc_alloc(ptst, gc_id); + critical_exit(ptst); + return (obj); +} + +void +osi_mcas_obj_cache_free(osi_mcas_obj_cache_t gc_id, void *obj) +{ + ptst_t *ptst; + + ptst = critical_enter(); + gc_free(ptst, (void *)obj, gc_id); + critical_exit(ptst); +} + +void +osi_mcas_obj_cache_destroy(osi_mcas_obj_cache_t gc_id) +{ + // implement? + return; +} + +/* lock-free object cache */ + +/* Key data type and comparison function */ +int +harness_ulong_comp(const void *lhs, const void *rhs) +{ + harness_ulong_t *l, *r; + + l = (harness_ulong_t *) lhs; + r = (harness_ulong_t *) rhs; + + /* todo: move to wrapper macro outside + * cmpf */ + + if (lhs == (void *)SENTINEL_KEYMAX) + return (1); + if (rhs == (void *)SENTINEL_KEYMAX) + return (-1); + + if (lhs == (void *)SENTINEL_KEYMIN) + return (-1); + if (rhs == (void *)SENTINEL_KEYMIN) + return (1); + /* end todo */ + + if (l->key == r->key) + return (0); + if (l->key > r->key) + return (1); + + return (-1); +} + +void +test_each_func(osi_set_t * l, setval_t v, void *arg) +{ + + harness_ulong_t *z; + osi_mcas_obj_cache_t gc_id; + int traversal; + + traversal = *(int *)arg; + z = (harness_ulong_t *) v; + gc_id = z->gc_id; + + if (z->traversal == traversal) + goto done; + + if (z->key % 10 == 0) { + printf("SPONGEBOB would delete key %d: secret key: %d (t: %d) \n", + z->key, z->secret_key, z->traversal); + + osi_cas_skip_remove(l, z); + osi_mcas_obj_cache_free(gc_id, z); + } else { + printf("SQUAREPANTS still here key %d: secret key: %d (t: %d) \n", + z->key, z->secret_key, z->traversal); + } + + done: + z->traversal = traversal; +} + +void +test_each_func_2(osi_set_t * l, setval_t v, void *arg) +{ + + int traversal; + harness_ulong_t *z; + + traversal = *(int *)arg; + z = (harness_ulong_t *) v; + + if (z->traversal == traversal) + goto done; + + printf("SQUAREPANTS still here key %d: secret key: %d\n", + z->key, z->secret_key); + done: + z->traversal = traversal; +} + +void +thread_do_test(void *arg) +{ + int ix, ix2, six, eix, sv; + harness_ulong_t *node, *node2, *snode; + + sv = *((int *)arg); + + six = CREATE_N / 4 * sv; + eix = six + CREATE_N / 4; + + printf("Starting thread with %d %d %d\n", sv, six, eix); + + /* Allocate nodes and insert in skip queue */ + + for (; six < eix; ++six) { + + /* set 1 */ + node = (harness_ulong_t *) malloc(sizeof(harness_ulong_t)); + memset(node, 0, sizeof(harness_ulong_t)); + node->key = six; + node->secret_key = 2 * six; + printf("thread %d insert: %d key: %d secret: %d\n", sv, node, + node->key, node->secret_key); + osi_cas_skip_update(shared.set, node, node, 1); + +#if 0 /* reuse package test */ + /* set 2 */ + node2 = (harness_ulong_t *) malloc(sizeof(harness_ulong_t)); + memset(node2, 0, sizeof(harness_ulong_t)); + node2->key = six; + node2->secret_key = 3 * six; + printf("thread %d insert: %d key: %d secret: %d\n", sv, node2, + node2->key, node2->secret_key); + osi_cas_skip_update(shared.set2, node2, node2, 1); +#endif + } + + snode = (harness_ulong_t *) malloc(sizeof(harness_ulong_t)); + goto tdone; + + ix2 = 0; + do { + for (ix = 0; ix < CREATE_N; ix += 1) { + snode->key = ix; + node = osi_cas_skip_lookup(shared.set, snode); + if (node) { + printf("thread %d searched set(1) for and found: key: " + "%d secret_key: %d\n", + sv, node->key, node->secret_key); + } else { + printf("thread %d searched set(1) for and didn't find: %d\n", + sv, snode->key); + } +#if 0 /* set2 */ + node = osi_cas_skip_lookup(shared.set2, snode); + if (node) { + printf("thread %d searched set(2) for and found: key: " + "%d secret_key: %d\n", + sv, node->key, node->secret_key); + } else { + printf("thread %d searched set(2) for and didn't find: %d\n", + sv, snode->key); + } +#endif + } + ix2++; + } while (ix2 < 10000); + + /* dump queue */ + tdone: + ix2++; + +} + +/* help test atomic inc, dec */ + +typedef long osi_atomic_t; + +#define osi_atomic_inc(x) \ +do { \ + RMB(); \ + FASPO(&x, x+1); \ +} while(0); + +#define osi_atomic_dec(x) \ +do { \ + RMB(); \ + FASPO(&x, x-1); \ +} while(0); + + +int +main(int argc, char **argv) +{ + + int ix, traversal; + harness_ulong_t *node, *node2, *snode; + osi_mcas_obj_cache_t gc_id, gc2_id; + + printf("Starting ADT Test\n"); + + /* do this once, 1st thread */ + _init_ptst_subsystem(); + _init_gc_subsystem(); + _init_osi_cas_skip_subsystem(); + + osi_mcas_obj_cache_create(&gc_id, sizeof(harness_ulong_t)); + osi_mcas_obj_cache_create(&gc2_id, sizeof(harness_ulong_t)); + + shared.set = osi_cas_skip_alloc(&harness_ulong_comp); + shared.set2 = osi_cas_skip_alloc(&harness_ulong_comp); + + /* just insert and iterate */ + + for (ix = 0; ix < CREATE_N; ++ix) { + + /* set 1 */ + node = (harness_ulong_t *) osi_mcas_obj_cache_alloc(gc_id); + pthread_mutex_init(&node->lock, NULL); + + /* and pound on collector 2 */ + node2 = (harness_ulong_t *) osi_mcas_obj_cache_alloc(gc2_id); + + node->gc_id = gc_id; + node->key = ix; + node->secret_key = 2 * ix; + printf("insert: %d key: %d secret: %d\n", node, + node->key, node->secret_key); + osi_cas_skip_update(shared.set, node, node, 1); + } + + snode = (harness_ulong_t *) osi_mcas_obj_cache_alloc(gc_id); + snode->gc_id = gc_id; + snode->key = 5; + node = osi_cas_skip_lookup(shared.set, snode); + if (node) { + printf("searched set(1) for and found: key: " + "%d secret_key: %d\n", node->key, node->secret_key); + } else { + printf("searched set(1) for and didn't find: %d\n", snode->key); + } + + sleep(1); + + /* traversal is used to avoid acting on duplicate references (which + * are an artifact of skip list implementation; assumes only one + * thread may be in set_for_each, as implemented */ + + printf("now... \n"); + traversal = 1; + osi_cas_skip_for_each(shared.set, &test_each_func, &traversal); + + sleep(1); + + printf("now... \n"); + traversal = 2; + osi_cas_skip_for_each(shared.set, &test_each_func_2, &traversal); + + /* test osi_atomic_inc */ + + { + int a_ix; + osi_atomic_t ai; + + for (ai = 0, a_ix = 0; a_ix < 10; ++a_ix) { + osi_atomic_inc(ai); + } + osi_atomic_dec(ai); + + printf("ai is: %d\n", ai); + } + + osi_mcas_obj_cache_free(gc_id, node); + + return 0; +} diff --git a/src/mcas/skip_cas_adt.c b/src/mcas/skip_cas_adt.c new file mode 100644 index 000000000..b677dd9ed --- /dev/null +++ b/src/mcas/skip_cas_adt.c @@ -0,0 +1,571 @@ +/****************************************************************************** + * skip_cas_adt.c + * + * Skip lists, allowing concurrent update by use of CAS primitives. + * + * Matt Benjamin + * + * Adapts MCAS skip list to use a pointer-key and typed comparison + * function style (because often, your key isn't an integer). + * + * Also, set_for_each (and future additions) allow a set to be iterated. + * Current set_for_each iteration is unordered. + * + * Caution, pointer values 0x0, 0x01, and 0x02 are reserved. Fortunately, + * no real pointer is likely to have one of these values. + +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#define __SET_IMPLEMENTATION__ + +#include +#include +#include +#include "portable_defns.h" +#include "ptst.h" +#include "set_queue_adt.h" + +// todo: get rid of me +typedef struct { + unsigned long key; + unsigned long secret_key; +} harness_ulong_t; + + + +/* + * SKIP LIST + */ + +typedef struct node_st node_t; +typedef struct set_st osi_set_t; +typedef VOLATILE node_t *sh_node_pt; + +struct node_st { + int level; +// int xxx[1024]; /* XXXX testing gc */ +#define LEVEL_MASK 0x0ff +#define READY_FOR_FREE 0x100 + setkey_t k; + setval_t v; + sh_node_pt next[1]; +}; + +typedef int (*osi_set_cmp_func) (const void *lhs, const void *rhs); + +struct set_st { + CACHE_PAD(0); + osi_set_cmp_func cmpf; + CACHE_PAD(1); + node_t head; + CACHE_PAD(2); +}; + +static int gc_id[NUM_LEVELS]; + +/* + * PRIVATE FUNCTIONS + */ + +#define compare_keys(s, k1, k2) (s->cmpf((const void*) k1, (const void *) k2)) + +/* + * Random level generator. Drop-off rate is 0.5 per level. + * Returns value 1 <= level <= NUM_LEVELS. + */ +static int +get_level(ptst_t * ptst) +{ + unsigned long r = rand_next(ptst); + int l = 1; + r = (r >> 4) & ((1 << (NUM_LEVELS - 1)) - 1); + while ((r & 1)) { + l++; + r >>= 1; + } + return (l); +} + + +/* + * Allocate a new node, and initialise its @level field. + * NB. Initialisation will eventually be pushed into garbage collector, + * because of dependent read reordering. + */ +static node_t * +alloc_node(ptst_t * ptst) +{ + int l; + node_t *n; + l = get_level(ptst); + n = gc_alloc(ptst, gc_id[l - 1]); + n->level = l; + return (n); +} + + +/* Free a node to the garbage collector. */ +static void +free_node(ptst_t * ptst, sh_node_pt n) +{ + gc_free(ptst, (void *)n, gc_id[(n->level & LEVEL_MASK) - 1]); +} + + +/* + * Search for first non-deleted node, N, with key >= @k at each level in @l. + * RETURN VALUES: + * Array @pa: @pa[i] is non-deleted predecessor of N at level i + * Array @na: @na[i] is N itself, which should be pointed at by @pa[i] + * MAIN RETURN VALUE: same as @na[0]. + */ +static sh_node_pt +strong_search_predecessors(osi_set_t * l, setkey_t k, sh_node_pt * pa, + sh_node_pt * na) +{ + sh_node_pt x, x_next, old_x_next, y, y_next; + setkey_t y_k; + int i; + + retry: + RMB(); + + x = &l->head; + for (i = NUM_LEVELS - 1; i >= 0; i--) { + /* We start our search at previous level's unmarked predecessor. */ + READ_FIELD(x_next, x->next[i]); + /* If this pointer's marked, so is @pa[i+1]. May as well retry. */ + if (is_marked_ref(x_next)) + goto retry; + + for (y = x_next;; y = y_next) { + /* Shift over a sequence of marked nodes. */ + for (;;) { + READ_FIELD(y_next, y->next[i]); + if (!is_marked_ref(y_next)) + break; + y = get_unmarked_ref(y_next); + } + + READ_FIELD(y_k, y->k); + if (compare_keys(l, y_k, k) >= 0) + break; + + /* Update estimate of predecessor at this level. */ + x = y; + x_next = y_next; + } + + /* Swing forward pointer over any marked nodes. */ + if (x_next != y) { + old_x_next = CASPO(&x->next[i], x_next, y); + if (old_x_next != x_next) + goto retry; + } + + if (pa) + pa[i] = x; + if (na) + na[i] = y; + } + + return (y); +} + + +/* This function does not remove marked nodes. Use it optimistically. */ +static sh_node_pt +weak_search_predecessors(osi_set_t * l, setkey_t k, sh_node_pt * pa, + sh_node_pt * na) +{ + sh_node_pt x, x_next; + setkey_t x_next_k; + int i; + + x = &l->head; + for (i = NUM_LEVELS - 1; i >= 0; i--) { + for (;;) { + READ_FIELD(x_next, x->next[i]); + x_next = get_unmarked_ref(x_next); + + READ_FIELD(x_next_k, x_next->k); + if (compare_keys(l, x_next_k, k) >= 0) + break; + + x = x_next; + } + + if (pa) + pa[i] = x; + if (na) + na[i] = x_next; + } + + return (x_next); +} + + +/* + * Mark @x deleted at every level in its list from @level down to level 1. + * When all forward pointers are marked, node is effectively deleted. + * Future searches will properly remove node by swinging predecessors' + * forward pointers. + */ +static void +mark_deleted(sh_node_pt x, int level) +{ + sh_node_pt x_next; + + while (--level >= 0) { + x_next = x->next[level]; + while (!is_marked_ref(x_next)) { + x_next = CASPO(&x->next[level], x_next, get_marked_ref(x_next)); + } + WEAK_DEP_ORDER_WMB(); /* mark in order */ + } +} + + +static int +check_for_full_delete(sh_node_pt x) +{ + int level = x->level; + return ((level & READY_FOR_FREE) || + (CASIO(&x->level, level, level | READY_FOR_FREE) != level)); +} + + +static void +do_full_delete(ptst_t * ptst, osi_set_t * l, sh_node_pt x, int level) +{ + setkey_t k = x->k; +#ifdef WEAK_MEM_ORDER + sh_node_pt preds[NUM_LEVELS]; + int i = level; + retry: + (void)strong_search_predecessors(l, k, preds, NULL); + /* + * Above level 1, references to @x can disappear if a node is inserted + * immediately before and we see an old value for its forward pointer. This + * is a conservative way of checking for that situation. + */ + if (i > 0) + RMB(); + while (i > 0) { + node_t *n = get_unmarked_ref(preds[i]->next[i]); + while (compare_keys(l, n->k, k) < 0) { + n = get_unmarked_ref(n->next[i]); + RMB(); /* we don't want refs to @x to "disappear" */ + } + if (n == x) + goto retry; + i--; /* don't need to check this level again, even if we retry. */ + } +#else + (void)strong_search_predecessors(l, k, NULL, NULL); +#endif + free_node(ptst, x); +} + + +/* + * PUBLIC FUNCTIONS + */ + +/* + * Called once before any set operations, including set_alloc + */ +void +_init_osi_cas_skip_subsystem(void) +{ + int i; + + for (i = 0; i < NUM_LEVELS; i++) { + gc_id[i] = gc_add_allocator(sizeof(node_t) + i * sizeof(node_t *)); + } +} + + +osi_set_t * +osi_cas_skip_alloc(osi_set_cmp_func cmpf) +{ + osi_set_t *l; + node_t *n; + int i; + + n = malloc(sizeof(*n) + (NUM_LEVELS - 1) * sizeof(node_t *)); + memset(n, 0, sizeof(*n) + (NUM_LEVELS - 1) * sizeof(node_t *)); + n->k = (setkey_t *) SENTINEL_KEYMAX; + + /* + * Set the forward pointers of final node to other than NULL, + * otherwise READ_FIELD() will continually execute costly barriers. + * Note use of 0xfe -- that doesn't look like a marked value! + */ + memset(n->next, 0xfe, NUM_LEVELS * sizeof(node_t *)); + + l = malloc(sizeof(*l) + (NUM_LEVELS - 1) * sizeof(node_t *)); + l->cmpf = cmpf; + l->head.k = (setkey_t *) SENTINEL_KEYMIN; + l->head.level = NUM_LEVELS; + for (i = 0; i < NUM_LEVELS; i++) { + l->head.next[i] = n; + } + + return (l); +} + + +setval_t +osi_cas_skip_update(osi_set_t * l, setkey_t k, setval_t v, int overwrite) +{ + setval_t ov, new_ov; + ptst_t *ptst; + sh_node_pt preds[NUM_LEVELS], succs[NUM_LEVELS]; + sh_node_pt pred, succ, new = NULL, new_next, old_next; + int i, level; + + ptst = critical_enter(); + + succ = weak_search_predecessors(l, k, preds, succs); + + retry: + ov = NULL; + + if (compare_keys(l, succ->k, k) == 0) { + /* Already a @k node in the list: update its mapping. */ + new_ov = succ->v; + do { + if ((ov = new_ov) == NULL) { + /* Finish deleting the node, then retry. */ + READ_FIELD(level, succ->level); + mark_deleted(succ, level & LEVEL_MASK); + succ = strong_search_predecessors(l, k, preds, succs); + goto retry; + } + } while (overwrite && ((new_ov = CASPO(&succ->v, ov, v)) != ov)); + + if (new != NULL) + free_node(ptst, new); + goto out; + } +#ifdef WEAK_MEM_ORDER + /* Free node from previous attempt, if this is a retry. */ + if (new != NULL) { + free_node(ptst, new); + new = NULL; + } +#endif + + /* Not in the list, so initialise a new node for insertion. */ + if (new == NULL) { + new = alloc_node(ptst); + new->k = k; + new->v = v; + } + level = new->level; + + /* If successors don't change, this saves us some CAS operations. */ + for (i = 0; i < level; i++) { + new->next[i] = succs[i]; + } + + /* We've committed when we've inserted at level 1. */ + WMB_NEAR_CAS(); /* make sure node fully initialised before inserting */ + old_next = CASPO(&preds[0]->next[0], succ, new); + if (old_next != succ) { + succ = strong_search_predecessors(l, k, preds, succs); + goto retry; + } + + /* Insert at each of the other levels in turn. */ + i = 1; + while (i < level) { + pred = preds[i]; + succ = succs[i]; + + /* Someone *can* delete @new under our feet! */ + new_next = new->next[i]; + if (is_marked_ref(new_next)) + goto success; + + /* Ensure forward pointer of new node is up to date. */ + if (new_next != succ) { + old_next = CASPO(&new->next[i], new_next, succ); + if (is_marked_ref(old_next)) + goto success; + assert(old_next == new_next); + } + + /* Ensure we have unique key values at every level. */ + if (compare_keys(l, succ->k, k) == 0) + goto new_world_view; + + assert((compare_keys(l, pred->k, k) < 0) && + (compare_keys(l, succ->k, k) > 0)); + + /* Replumb predecessor's forward pointer. */ + old_next = CASPO(&pred->next[i], succ, new); + if (old_next != succ) { + new_world_view: + RMB(); /* get up-to-date view of the world. */ + (void)strong_search_predecessors(l, k, preds, succs); + continue; + } + + /* Succeeded at this level. */ + i++; + } + + success: + /* Ensure node is visible at all levels before punting deletion. */ + WEAK_DEP_ORDER_WMB(); + if (check_for_full_delete(new)) { + MB(); /* make sure we see all marks in @new. */ + do_full_delete(ptst, l, new, level - 1); + } + out: + critical_exit(ptst); + return (ov); +} + +setval_t +osi_cas_skip_remove(osi_set_t * l, setkey_t k) +{ + setval_t v = NULL, new_v; + ptst_t *ptst; + sh_node_pt preds[NUM_LEVELS], x; + int level, i; + + ptst = critical_enter(); + + x = weak_search_predecessors(l, k, preds, NULL); + if (compare_keys(l, x->k, k) > 0) + goto out; + + READ_FIELD(level, x->level); + level = level & LEVEL_MASK; + + /* Once we've marked the value field, the node is effectively deleted. */ + new_v = x->v; + do { + v = new_v; + if (v == NULL) + goto out; + } while ((new_v = CASPO(&x->v, v, NULL)) != v); + + /* Committed to @x: mark lower-level forward pointers. */ + WEAK_DEP_ORDER_WMB(); /* enforce above as linearisation point */ + mark_deleted(x, level); + + /* + * We must swing predecessors' pointers, or we can end up with + * an unbounded number of marked but not fully deleted nodes. + * Doing this creates a bound equal to number of threads in the system. + * Furthermore, we can't legitimately call 'free_node' until all shared + * references are gone. + */ + for (i = level - 1; i >= 0; i--) { + if (CASPO(&preds[i]->next[i], x, get_unmarked_ref(x->next[i])) != x) { + if ((i != (level - 1)) || check_for_full_delete(x)) { + MB(); /* make sure we see node at all levels. */ + do_full_delete(ptst, l, x, i); + } + goto out; + } + } + + free_node(ptst, x); + + out: + critical_exit(ptst); + return (v); +} + + +setval_t +osi_cas_skip_lookup(osi_set_t * l, setkey_t k) +{ + setval_t v = NULL; + ptst_t *ptst; + sh_node_pt x; + + ptst = critical_enter(); + + x = weak_search_predecessors(l, k, NULL, NULL); + if (compare_keys(l, x->k, k) == 0) + READ_FIELD(v, x->v); + + critical_exit(ptst); + return (v); +} + + +/* Hybrid Set/Queue Operations (Matt) */ + +/* Iterate over a sequential structure, calling callback_func + * on each (undeleted) element visited. */ + +/* Each-element function passed to set_for_each */ +typedef void (*osi_set_each_func) (osi_set_t * l, setval_t v, void *arg); +void +osi_cas_skip_for_each(osi_set_t * l, osi_set_each_func each_func, void *arg) +{ + sh_node_pt x, y, x_next, old_x_next; + setkey_t x_next_k; + ptst_t *ptst; + int i; + + ptst = critical_enter(); + + x = &l->head; + for (i = NUM_LEVELS - 1; i >= 0; i--) { + /* must revisit x at each level to see all + * nodes in the structure */ + y = x; + + for (;;) { + READ_FIELD(x_next, y->next[i]); + x_next = get_unmarked_ref(x_next); + + READ_FIELD(x_next_k, x_next->k); + if (x_next_k == (setkey_t) SENTINEL_KEYMAX) + break; + + /* in our variation, a (stored) k is a v, + * ie, x_next_k is x_next_v */ + each_func(l, x_next_k, arg); + + y = x_next; + } + } + + critical_exit(ptst); +} diff --git a/src/mcas/skip_cas_func.c b/src/mcas/skip_cas_func.c new file mode 100644 index 000000000..2a3b19f3e --- /dev/null +++ b/src/mcas/skip_cas_func.c @@ -0,0 +1,510 @@ +/****************************************************************************** + * skip_cas_func.c + * + * Skip lists, allowing concurrent update by use of CAS primitives. + * + * Matt Benjamin + * + * Adapts MCAS skip list to use a pointer-key and typed comparison + * function style (because often, your key isn't an integer). + * + * Caution, pointer values 0x0, 0x01, and 0x02 are reserved. Fortunately, + * no real pointer is likely to have one of these values. + +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#define __SET_IMPLEMENTATION__ + +#include +#include +#include +#include "portable_defns.h" +#include "ptst.h" +#include "set_func.h" + + +/* + * SKIP LIST + */ + +typedef struct node_st node_t; +typedef struct set_st set_t; +typedef VOLATILE node_t *sh_node_pt; + +struct node_st { + int level; +#define LEVEL_MASK 0x0ff +#define READY_FOR_FREE 0x100 + setkey_t k; + setval_t v; + sh_node_pt next[1]; +}; + +struct set_st { + node_t head; + int (*cmpf) (const void *, const void *); +}; + +static int gc_id[NUM_LEVELS]; + +/* + * PRIVATE FUNCTIONS + */ + +#define compare_keys(s, k1, k2) (s->cmpf(k1, k2)); + +/* + * Random level generator. Drop-off rate is 0.5 per level. + * Returns value 1 <= level <= NUM_LEVELS. + */ +static int +get_level(ptst_t * ptst) +{ + unsigned long r = rand_next(ptst); + int l = 1; + r = (r >> 4) & ((1 << (NUM_LEVELS - 1)) - 1); + while ((r & 1)) { + l++; + r >>= 1; + } + return (l); +} + + +/* + * Allocate a new node, and initialise its @level field. + * NB. Initialisation will eventually be pushed into garbage collector, + * because of dependent read reordering. + */ +static node_t * +alloc_node(ptst_t * ptst) +{ + int l; + node_t *n; + l = get_level(ptst); + n = gc_alloc(ptst, gc_id[l - 1]); + n->level = l; + return (n); +} + + +/* Free a node to the garbage collector. */ +static void +free_node(ptst_t * ptst, sh_node_pt n) +{ + gc_free(ptst, (void *)n, gc_id[(n->level & LEVEL_MASK) - 1]); +} + + +/* + * Search for first non-deleted node, N, with key >= @k at each level in @l. + * RETURN VALUES: + * Array @pa: @pa[i] is non-deleted predecessor of N at level i + * Array @na: @na[i] is N itself, which should be pointed at by @pa[i] + * MAIN RETURN VALUE: same as @na[0]. + */ +static sh_node_pt +strong_search_predecessors(set_t * l, setkey_t k, sh_node_pt * pa, + sh_node_pt * na) +{ + sh_node_pt x, x_next, old_x_next, y, y_next; + setkey_t y_k; + int i; + + retry: + RMB(); + + x = &l->head; + for (i = NUM_LEVELS - 1; i >= 0; i--) { + /* We start our search at previous level's unmarked predecessor. */ + READ_FIELD(x_next, x->next[i]); + /* If this pointer's marked, so is @pa[i+1]. May as well retry. */ + if (is_marked_ref(x_next)) + goto retry; + + for (y = x_next;; y = y_next) { + /* Shift over a sequence of marked nodes. */ + for (;;) { + READ_FIELD(y_next, y->next[i]); + if (!is_marked_ref(y_next)) + break; + y = get_unmarked_ref(y_next); + } + + READ_FIELD(y_k, y->k); + if (compare_keys(l, y_k, k) >= 0) + break; + + /* Update estimate of predecessor at this level. */ + x = y; + x_next = y_next; + } + + /* Swing forward pointer over any marked nodes. */ + if (x_next != y) { + old_x_next = CASPO(&x->next[i], x_next, y); + if (old_x_next != x_next) + goto retry; + } + + if (pa) + pa[i] = x; + if (na) + na[i] = y; + } + + return (y); +} + + +/* This function does not remove marked nodes. Use it optimistically. */ +static sh_node_pt +weak_search_predecessors(set_t * l, setkey_t k, sh_node_pt * pa, + sh_node_pt * na) +{ + sh_node_pt x, x_next; + setkey_t x_next_k; + int i; + + x = &l->head; + for (i = NUM_LEVELS - 1; i >= 0; i--) { + for (;;) { + READ_FIELD(x_next, x->next[i]); + x_next = get_unmarked_ref(x_next); + + READ_FIELD(x_next_k, x_next->k); + if (compare_keys(l, x_next_k, k) >= 0) + break; + + x = x_next; + } + + if (pa) + pa[i] = x; + if (na) + na[i] = x_next; + } + + return (x_next); +} + + +/* + * Mark @x deleted at every level in its list from @level down to level 1. + * When all forward pointers are marked, node is effectively deleted. + * Future searches will properly remove node by swinging predecessors' + * forward pointers. + */ +static void +mark_deleted(sh_node_pt x, int level) +{ + sh_node_pt x_next; + + while (--level >= 0) { + x_next = x->next[level]; + while (!is_marked_ref(x_next)) { + x_next = CASPO(&x->next[level], x_next, get_marked_ref(x_next)); + } + WEAK_DEP_ORDER_WMB(); /* mark in order */ + } +} + + +static int +check_for_full_delete(sh_node_pt x) +{ + int level = x->level; + return ((level & READY_FOR_FREE) || + (CASIO(&x->level, level, level | READY_FOR_FREE) != level)); +} + + +static void +do_full_delete(ptst_t * ptst, set_t * l, sh_node_pt x, int level) +{ + int k = x->k; +#ifdef WEAK_MEM_ORDER + sh_node_pt preds[NUM_LEVELS]; + int i = level; + retry: + (void)strong_search_predecessors(l, k, preds, NULL); + /* + * Above level 1, references to @x can disappear if a node is inserted + * immediately before and we see an old value for its forward pointer. This + * is a conservative way of checking for that situation. + */ + if (i > 0) + RMB(); + while (i > 0) { + node_t *n = get_unmarked_ref(preds[i]->next[i]); + while (compare_keys(l, n->k, k) < 0) { + n = get_unmarked_ref(n->next[i]); + RMB(); /* we don't want refs to @x to "disappear" */ + } + if (n == x) + goto retry; + i--; /* don't need to check this level again, even if we retry. */ + } +#else + (void)strong_search_predecessors(l, k, NULL, NULL); +#endif + free_node(ptst, x); +} + + +/* + * PUBLIC FUNCTIONS + */ + +set_t * +set_alloc(int (*cmpf) (const void *, const void *)) +{ + set_t *l; + node_t *n; + int i; + + n = malloc(sizeof(*n) + (NUM_LEVELS - 1) * sizeof(node_t *)); + memset(n, 0, sizeof(*n) + (NUM_LEVELS - 1) * sizeof(node_t *)); + n->k = SENTINEL_KEYMAX; + + /* + * Set the forward pointers of final node to other than NULL, + * otherwise READ_FIELD() will continually execute costly barriers. + * Note use of 0xfe -- that doesn't look like a marked value! + */ + memset(n->next, 0xfe, NUM_LEVELS * sizeof(node_t *)); + + l = malloc(sizeof(*l) + (NUM_LEVELS - 1) * sizeof(node_t *)); + l->cmpf = cmpf; + l->head.k = SENTINEL_KEYMIN; + l->head.level = NUM_LEVELS; + for (i = 0; i < NUM_LEVELS; i++) { + l->head.next[i] = n; + } + + return (l); +} + + +setval_t +set_update(set_t * l, setkey_t k, setval_t v, int overwrite) +{ + setval_t ov, new_ov; + ptst_t *ptst; + sh_node_pt preds[NUM_LEVELS], succs[NUM_LEVELS]; + sh_node_pt pred, succ, new = NULL, new_next, old_next; + int i, level; + + ptst = critical_enter(); + + succ = weak_search_predecessors(l, k, preds, succs); + + retry: + ov = NULL; + + if (compare_keys(l, succ->k, k) == 0) { + /* Already a @k node in the list: update its mapping. */ + new_ov = succ->v; + do { + if ((ov = new_ov) == NULL) { + /* Finish deleting the node, then retry. */ + READ_FIELD(level, succ->level); + mark_deleted(succ, level & LEVEL_MASK); + succ = strong_search_predecessors(l, k, preds, succs); + goto retry; + } + } while (overwrite && ((new_ov = CASPO(&succ->v, ov, v)) != ov)); + + if (new != NULL) + free_node(ptst, new); + goto out; + } +#ifdef WEAK_MEM_ORDER + /* Free node from previous attempt, if this is a retry. */ + if (new != NULL) { + free_node(ptst, new); + new = NULL; + } +#endif + + /* Not in the list, so initialise a new node for insertion. */ + if (new == NULL) { + new = alloc_node(ptst); + new->k = k; + new->v = v; + } + level = new->level; + + /* If successors don't change, this saves us some CAS operations. */ + for (i = 0; i < level; i++) { + new->next[i] = succs[i]; + } + + /* We've committed when we've inserted at level 1. */ + WMB_NEAR_CAS(); /* make sure node fully initialised before inserting */ + old_next = CASPO(&preds[0]->next[0], succ, new); + if (old_next != succ) { + succ = strong_search_predecessors(l, k, preds, succs); + goto retry; + } + + /* Insert at each of the other levels in turn. */ + i = 1; + while (i < level) { + pred = preds[i]; + succ = succs[i]; + + /* Someone *can* delete @new under our feet! */ + new_next = new->next[i]; + if (is_marked_ref(new_next)) + goto success; + + /* Ensure forward pointer of new node is up to date. */ + if (new_next != succ) { + old_next = CASPO(&new->next[i], new_next, succ); + if (is_marked_ref(old_next)) + goto success; + assert(old_next == new_next); + } + + /* Ensure we have unique key values at every level. */ + if (compare_keys(l, succ->k, k) == 0) + goto new_world_view; + + assert((compare_keys(l, pred->k, k) < 0) && + (compare_keys(l, succ->k, k) > 0)); + + /* Replumb predecessor's forward pointer. */ + old_next = CASPO(&pred->next[i], succ, new); + if (old_next != succ) { + new_world_view: + RMB(); /* get up-to-date view of the world. */ + (void)strong_search_predecessors(l, k, preds, succs); + continue; + } + + /* Succeeded at this level. */ + i++; + } + + success: + /* Ensure node is visible at all levels before punting deletion. */ + WEAK_DEP_ORDER_WMB(); + if (check_for_full_delete(new)) { + MB(); /* make sure we see all marks in @new. */ + do_full_delete(ptst, l, new, level - 1); + } + out: + critical_exit(ptst); + return (ov); +} + + +setval_t +set_remove(set_t * l, setkey_t k) +{ + setval_t v = NULL, new_v; + ptst_t *ptst; + sh_node_pt preds[NUM_LEVELS], x; + int level, i; + + ptst = critical_enter(); + + x = weak_search_predecessors(l, k, preds, NULL); + if (compare_keys(l, x->k, k) > 0) + goto out; + + READ_FIELD(level, x->level); + level = level & LEVEL_MASK; + + /* Once we've marked the value field, the node is effectively deleted. */ + new_v = x->v; + do { + v = new_v; + if (v == NULL) + goto out; + } while ((new_v = CASPO(&x->v, v, NULL)) != v); + + /* Committed to @x: mark lower-level forward pointers. */ + WEAK_DEP_ORDER_WMB(); /* enforce above as linearisation point */ + mark_deleted(x, level); + + /* + * We must swing predecessors' pointers, or we can end up with + * an unbounded number of marked but not fully deleted nodes. + * Doing this creates a bound equal to number of threads in the system. + * Furthermore, we can't legitimately call 'free_node' until all shared + * references are gone. + */ + for (i = level - 1; i >= 0; i--) { + if (CASPO(&preds[i]->next[i], x, get_unmarked_ref(x->next[i])) != x) { + if ((i != (level - 1)) || check_for_full_delete(x)) { + MB(); /* make sure we see node at all levels. */ + do_full_delete(ptst, l, x, i); + } + goto out; + } + } + + free_node(ptst, x); + + out: + critical_exit(ptst); + return (v); +} + + +setval_t +set_lookup(set_t * l, setkey_t k) +{ + setval_t v = NULL; + ptst_t *ptst; + sh_node_pt x; + + ptst = critical_enter(); + + x = weak_search_predecessors(l, k, NULL, NULL); + if (compare_keys(l, x->k, k) == 0) + READ_FIELD(v, x->v); + + critical_exit(ptst); + return (v); +} + + +void +_init_set_subsystem(void) +{ + int i; + + for (i = 0; i < NUM_LEVELS; i++) { + gc_id[i] = gc_add_allocator(sizeof(node_t) + i * sizeof(node_t *)); + } +} diff --git a/src/mcas/solaris_amd64_defns.h b/src/mcas/solaris_amd64_defns.h new file mode 100644 index 000000000..d3c4e7054 --- /dev/null +++ b/src/mcas/solaris_amd64_defns.h @@ -0,0 +1,156 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef __SOLARIS_X86_DEFNS_H__ +#define __SOLARIS_X86_DEFNS_H__ + +#ifndef SOLARIS_X86_686 +#define SOLARIS_X86_686 +#endif + +#include +#include +#include +#include +#include +#include + +#define CACHE_LINE_SIZE 64 + +#if 0 +#include +#define pthread_mutex_t mutex_t +#define pthread_cond_t cond_t +#define pthread_t thread_t +#define pthread_key_t thread_key_t +#define pthread_create(_a,_b,_c,_d) thr_create(NULL,0,_c,_d,THR_BOUND|THR_NEW_LWP,_a) +#define pthread_join(_a,_b) thr_join(_a,NULL,NULL) +#define pthread_key_create(_a,_b) thr_keycreate(_a,_b) +#define pthread_setspecific(_a,_b) thr_setspecific(_a,_b) +static void * +pthread_getspecific(pthread_key_t _a) +{ + void *__x; + thr_getspecific(_a, &__x); + return __x; +} + +#define pthread_setconcurrency(_x) thr_setconcurrency(_x) +#define pthread_mutex_init(_a,_b) mutex_init(_a,USYNC_THREAD,NULL) +#define pthread_mutex_lock(_a) mutex_lock(_a) +#define pthread_mutex_unlock(_a) mutex_unlock(_a) +#define pthread_cond_init(_a,_b) cond_init(_a,USYNC_THREAD,NULL) +#define pthread_cond_wait(_a,_b) cond_wait(_a,_b) +#define pthread_cond_broadcast(_a) cond_broadcast(_a) +#else +#include +#endif + + +/* + * I. Compare-and-swap. + */ + +#define CAS(_a, _o, _n)\ +atomic_cas_64((_a), (_o), (_n)) + +#define FAS(_a, _n)\ +atomic_swap_64((_a), (uint64_t)(_n)) + +/* Update Pointer location, return Old value. */ +#define FASPO(_a, _n)\ +atomic_swap_ptr((volatile uint32_t *)(_a), (void *)(_n)) + +#define CASPO(_a, _o, _n)\ +atomic_cas_ptr((_a), (void *)(_o), (void *)(_n)) + +#define CAS64(_a, _o, _n)\ +(_u64) atomic_cas_64((volatile uint64_t *)(_a), (_o), (_n)) + +/* Update Integer location, return Old value. */ +#define CASIO(_a, _o, _n)\ +atomic_cas_64((volatile uint64_t *)(_a), (_o), (_n)) + +#define FASIO(_a, _n)\ +atomic_swap_64((volatile uint64_t *)(_a), (_n)) + +/* Update 32/64-bit location, return Old value. */ +#define CAS32O(_a, _o, _n)\ +(_u32) atomic_cas_32((volatile uint32_t *)(_a), (_o), (_n)) + +#define CAS64 CAS +#define CAS64O CAS + + +/* + * II. Memory barriers. + * WMB(): All preceding write operations must commit before any later writes. + * RMB(): All preceding read operations must commit before any later reads. + * MB(): All preceding memory accesses must commit before any later accesses. + * + * If the compiler does not observe these barriers (but any sane compiler + * will!), then VOLATILE should be defined as 'volatile'. + */ + +#define MB() membar_exit +#define WMB() membar_producer +#define RMB() membar_consumer + +#define VOLATILE volatile + +/* On Intel, CAS is a strong barrier, but not a compile barrier. */ +#define RMB_NEAR_CAS() WMB() +#define WMB_NEAR_CAS() WMB() +#define MB_NEAR_CAS() WMB() + +/* + * III. Cycle counter access. + */ + +#if 1 /* Sun Studio 12 */ +typedef unsigned long long tick_t; +#define RDTICK() \ + ({ tick_t __t; __asm__ __volatile__ ("rdtsc" : "=A" (__t)); __t; }) +#else +typedef unsigned long tick_t; +extern tick_t RDTICK(void); +#endif + + +/* + * IV. Types. + */ + +typedef unsigned char _u8; +typedef unsigned short _u16; +typedef unsigned int _u32; +typedef unsigned long long _u64; + +#endif /* __SOLARIS_X86_DEFNS_H__ */ diff --git a/src/mcas/solaris_x86_defns.h b/src/mcas/solaris_x86_defns.h new file mode 100644 index 000000000..583ad912e --- /dev/null +++ b/src/mcas/solaris_x86_defns.h @@ -0,0 +1,154 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef __SOLARIS_X86_DEFNS_H__ +#define __SOLARIS_X86_DEFNS_H__ + +#ifndef SOLARIS_X86_686 +#define SOLARIS_X86_686 +#endif + +#include +#include +#include +#include +#include +#include + +#define CACHE_LINE_SIZE 64 + +#if 0 +#include +#define pthread_mutex_t mutex_t +#define pthread_cond_t cond_t +#define pthread_t thread_t +#define pthread_key_t thread_key_t +#define pthread_create(_a,_b,_c,_d) thr_create(NULL,0,_c,_d,THR_BOUND|THR_NEW_LWP,_a) +#define pthread_join(_a,_b) thr_join(_a,NULL,NULL) +#define pthread_key_create(_a,_b) thr_keycreate(_a,_b) +#define pthread_setspecific(_a,_b) thr_setspecific(_a,_b) +static void * +pthread_getspecific(pthread_key_t _a) +{ + void *__x; + thr_getspecific(_a, &__x); + return __x; +} + +#define pthread_setconcurrency(_x) thr_setconcurrency(_x) +#define pthread_mutex_init(_a,_b) mutex_init(_a,USYNC_THREAD,NULL) +#define pthread_mutex_lock(_a) mutex_lock(_a) +#define pthread_mutex_unlock(_a) mutex_unlock(_a) +#define pthread_cond_init(_a,_b) cond_init(_a,USYNC_THREAD,NULL) +#define pthread_cond_wait(_a,_b) cond_wait(_a,_b) +#define pthread_cond_broadcast(_a) cond_broadcast(_a) +#else +#include +#endif + + +/* + * I. Compare-and-swap. + */ + +#define CAS(_a, _o, _n)\ +atomic_cas_32((_a), (_o), (_n)) + +#define FAS(_a, _n)\ +atomic_swap_32((_a), (uint32_t)(_n)) + +/* Update Pointer location, return Old value. */ +#define FASPO(_a, _n)\ +atomic_swap_ptr((_a), (_n)) + +#define CASPO(_a, _o, _n)\ +atomic_cas_ptr((_a), (void *) (_o), (void *) (_n)) + +#define CAS64(_a, _o, _n)\ +(_u64) atomic_cas_64((volatile uint64_t *)(_a), (_o), (_n)) + +/* Update Integer location, return Old value. */ +#define CASIO(_a, _o, _n)\ +atomic_cas_32((volatile uint32_t *)(_a), (_o), (_n)) + +#define FASIO(_a, _n)\ +atomic_swap_32((volatile uint32_t *)(_a), (_n)) + +/* Update 32/64-bit location, return Old value. */ +#define CAS32O CAS +#define CAS64O CAS64 + + +/* + * II. Memory barriers. + * WMB(): All preceding write operations must commit before any later writes. + * RMB(): All preceding read operations must commit before any later reads. + * MB(): All preceding memory accesses must commit before any later accesses. + * + * If the compiler does not observe these barriers (but any sane compiler + * will!), then VOLATILE should be defined as 'volatile'. + */ + +#define WMB() membar_producer +#define RMB() membar_consumer +#define MB()\ +(membar_enter(),membar_exit(),membar_producer(),membar_consumer()) + +#define VOLATILE volatile + +/* On Intel, CAS is a strong barrier, but not a compile barrier. */ +#define RMB_NEAR_CAS() WMB() +#define WMB_NEAR_CAS() WMB() +#define MB_NEAR_CAS() WMB() + +/* + * III. Cycle counter access. + */ + +#if 1 /* Sun Studio 12 */ +typedef unsigned long long tick_t; +#define RDTICK() \ + ({ tick_t __t; __asm__ __volatile__ ("rdtsc" : "=A" (__t)); __t; }) +#else +typedef unsigned long tick_t; +extern tick_t RDTICK(void); +#endif + + +/* + * IV. Types. + */ + +typedef unsigned char _u8; +typedef unsigned short _u16; +typedef unsigned int _u32; +typedef unsigned long long _u64; + +#endif /* __SOLARIS_X86_DEFNS_H__ */ diff --git a/src/mcas/sparc_defns.h b/src/mcas/sparc_defns.h index e4767c171..150007f44 100644 --- a/src/mcas/sparc_defns.h +++ b/src/mcas/sparc_defns.h @@ -1,3 +1,33 @@ +/* +Copyright (c) 2003, Keir Fraser All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + #ifndef __SPARC_DEFNS_H__ #define __SPARC_DEFNS_H__ diff --git a/src/mcas/stm.h b/src/mcas/stm.h index 4d2e25f38..c7d8186a9 100644 --- a/src/mcas/stm.h +++ b/src/mcas/stm.h @@ -4,6 +4,32 @@ * Interface definitions for software transactional memory (STM). * * Copyright (c) 2002-2003, K A Fraser + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. Neither the name of the Keir Fraser + * nor the names of its contributors may be used to endorse or + * promote products derived from this software without specific + * prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "ptst.h" -- 2.39.5