--- /dev/null
+# 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)
--- /dev/null
+
+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)
--- /dev/null
+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
+
+/*
+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__
--- /dev/null
+/*
+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 <pthread.h>
+#include <sched.h>
+
+#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__ */
#include <unistd.h>
#include "portable_defns.h"
#include "gc.h"
+#include <afs/afsutil.h>
/*#define MINIMAL_GC*/
/*#define YIELD_TO_HELP_PROGRESS*/
#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
VOLATILE unsigned int inreclaim;
CACHE_PAD(2);
+
+ /* Allocator caches currently defined */
+ long n_allocators;
+
/*
* RUN-TIME CONSTANTS (to first approximation)
*/
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
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)
{
}
-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;
+/*
+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__
+/*
+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__
+/*
+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__
+/*
+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__
--- /dev/null
+/*
+ * 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 */
--- /dev/null
+#include "osi_mcas_obj_cache.h"
+#include <afs/afsutil.h>
+
+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;
+}
--- /dev/null
+
+#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 */
+/*
+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)
typedef unsigned long int_addr_t;
-typedef int bool_t;
#define FALSE 0
#define TRUE 1
__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.
#endif
+#if !defined(INTEL) && !defined(SOLARIS_X86_686) && !defined(SOLARIS_X86_AMD64) && !defined(X86_64)
+
/*
* Strong LL/SC operations
*/
return (_u32) (val_read >> 32);
}
+#endif /* !INTEL */
+
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;
return 0;
}
+#endif /* !INTEL */
+
static void s_store(_u64 *ptr, _u32 n)
{
+/*
+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__
* 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__
*
* 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__
+/*
+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__
--- /dev/null
+/*
+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 <matt@linuxbox.com>
+ *
+ * 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__ */
--- /dev/null
+/******************************************************************************
+ * set_queue_adt.h
+ *
+ * Matt Benjamin <matt@linuxbox.com>
+ *
+ * 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__ */
--- /dev/null
+#include <sys/resource.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <sys/time.h>
+#include <sys/times.h>
+#include <sys/mman.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <ucontext.h>
+#include <signal.h>
+#include <sched.h>
+#include <limits.h>
+#include <assert.h>
+#include <stdarg.h>
+
+/* for mutex testing */
+#include <pthread.h>
+
+#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;
+}
--- /dev/null
+/******************************************************************************
+ * skip_cas_adt.c
+ *
+ * Skip lists, allowing concurrent update by use of CAS primitives.
+ *
+ * Matt Benjamin <matt@linuxbox.com>
+ *
+ * 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 <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#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);
+}
--- /dev/null
+/******************************************************************************
+ * skip_cas_func.c
+ *
+ * Skip lists, allowing concurrent update by use of CAS primitives.
+ *
+ * Matt Benjamin <matt@linuxbox.com>
+ *
+ * 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 <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#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 *));
+ }
+}
--- /dev/null
+/*
+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 <sys/types.h>
+#include <sys/processor.h>
+#include <sys/procset.h>
+#include <sys/atomic.h>
+#include <sched.h>
+#include <alloca.h>
+
+#define CACHE_LINE_SIZE 64
+
+#if 0
+#include <thread.h>
+#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 <pthread.h>
+#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__ */
--- /dev/null
+/*
+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 <sys/types.h>
+#include <sys/processor.h>
+#include <sys/procset.h>
+#include <sys/atomic.h>
+#include <sched.h>
+#include <alloca.h>
+
+#define CACHE_LINE_SIZE 64
+
+#if 0
+#include <thread.h>
+#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 <pthread.h>
+#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__ */
+/*
+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__
* 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"
git://git.openafs.org / openafs.git / commitdiff