You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by so...@apache.org on 2014/08/01 22:44:15 UTC
[02/20] TS-2950: Initial commit of libck.
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/common.h
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/common.h b/lib/ck/regressions/common.h
new file mode 100644
index 0000000..f100e89
--- /dev/null
+++ b/lib/ck/regressions/common.h
@@ -0,0 +1,457 @@
+/*
+ * Copyright 2011-2014 Samy Al Bahra.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 <ck_cc.h>
+#include <ck_pr.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+
+#ifdef __linux__
+#include <sched.h>
+#include <sys/types.h>
+#include <sys/syscall.h>
+#elif defined(__MACH__)
+#include <mach/mach.h>
+#include <mach/thread_policy.h>
+#elif defined(__FreeBSD__)
+#include <sys/param.h>
+#include <sys/cpuset.h>
+#endif
+
+#if defined(_WIN32)
+#include <assert.h>
+#define NOMINMAX
+#include <windows.h>
+#define DELTA_EPOCH 11644473600000000ULL
+#else
+#include <signal.h>
+#include <unistd.h>
+#endif
+
+#ifndef CORES
+#define CORES 8
+#endif
+
+CK_CC_INLINE static void
+common_srand(unsigned int i)
+{
+#ifdef _WIN32
+ srand(i);
+#else
+ srandom(i);
+#endif
+}
+
+CK_CC_INLINE static int
+common_rand(void)
+{
+#ifdef _WIN32
+ return rand();
+#else
+ return random();
+#endif
+}
+
+CK_CC_INLINE static int
+common_rand_r(unsigned int *i)
+{
+#ifdef _WIN32
+ (void)i;
+
+ /*
+ * When linked with -mthreads, rand() is thread-safe.
+ * rand_s is also an option.
+ */
+ return rand();
+#else
+ return rand_r(i);
+#endif
+}
+
+CK_CC_INLINE static void
+common_srand48(long int i)
+{
+#ifdef _WIN32
+ srand(i);
+#else
+ srand48(i);
+#endif
+}
+
+CK_CC_INLINE static long int
+common_lrand48(void)
+{
+#ifdef _WIN32
+ return rand();
+#else
+ return lrand48();
+#endif
+}
+
+CK_CC_INLINE static double
+common_drand48(void)
+{
+#ifdef _WIN32
+ return (double)rand()/RAND_MAX;
+#else
+ return drand48();
+#endif
+}
+
+CK_CC_INLINE static void
+common_sleep(unsigned int n)
+{
+#ifdef _WIN32
+ Sleep(n * 1000);
+#else
+ sleep(n);
+#endif
+}
+
+CK_CC_INLINE static int
+common_gettimeofday(struct timeval *tv, void *tz)
+{
+#ifdef _WIN32
+ FILETIME ft;
+ uint64_t tmp_time = 0;
+ static bool tzflag = false;
+ struct timezone *tzp = tz;
+
+ if (tv != NULL) {
+ GetSystemTimeAsFileTime(&ft);
+ tmp_time |= ft.dwHighDateTime;
+ tmp_time <<= 32;
+ tmp_time |= ft.dwLowDateTime;
+
+ /* GetSystemTimeAsFileTime returns 100 nanosecond intervals. */
+ tmp_time /= 10;
+
+ /* Windows' epoch starts on 01/01/1601, while Unix' starts on 01/01/1970. */
+ tmp_time -= DELTA_EPOCH;
+
+ tv->tv_sec = (long)(tmp_time / 1000000UL);
+ tv->tv_usec = (long)(tmp_time % 1000000UL);
+ }
+
+
+ if (tz != NULL) {
+ if (tzflag == false) {
+ _tzset();
+ tzflag = true;
+ }
+
+ tzp->tz_minuteswest = _timezone / 60;
+ tzp->tz_dsttime = _daylight;
+ }
+
+ return 0;
+#else
+ return gettimeofday(tv, tz);
+#endif
+}
+
+CK_CC_UNUSED static unsigned int
+common_alarm(void (*sig_handler)(int), void *alarm_event, unsigned int duration)
+{
+#ifdef _WIN32
+ (void)sig_handler;
+ (void)duration;
+ bool success;
+ HANDLE *alarm_handle = alarm_event;
+ success = SetEvent(*alarm_handle);
+ assert(success != false);
+ return 0;
+#else
+ (void)alarm_event;
+ signal(SIGALRM, sig_handler);
+ return alarm(duration);
+#endif
+}
+
+#ifdef _WIN32
+#ifndef SECOND_TIMER
+#define SECOND_TIMER 10000000
+#endif
+#define COMMON_ALARM_DECLARE_GLOBAL(prefix, alarm_event_name, flag_name) \
+static HANDLE prefix##_common_win_alarm_timer; \
+static HANDLE alarm_event_name; \
+static LARGE_INTEGER prefix##_common_alarm_timer_length; \
+ \
+static void CALLBACK \
+prefix##_common_win_alarm_handler(LPVOID arg, DWORD timer_low_value, DWORD timer_high_value) \
+{ \
+ (void)arg; \
+ (void)timer_low_value; \
+ (void)timer_high_value; \
+ flag_name = true; \
+ return; \
+} \
+ \
+static void * \
+prefix##_common_win_alarm(void *unused) \
+{ \
+ (void)unused; \
+ bool timer_success = false; \
+ for (;;) { \
+ WaitForSingleObjectEx(alarm_event_name, INFINITE, true); \
+ timer_success = SetWaitableTimer(prefix##_common_win_alarm_timer, \
+ &prefix##_common_alarm_timer_length, \
+ 0, \
+ prefix##_common_win_alarm_handler, NULL, false); \
+ assert(timer_success != false); \
+ WaitForSingleObjectEx(prefix##_common_win_alarm_timer, INFINITE, true); \
+ } \
+ \
+ return NULL; \
+}
+
+#define COMMON_ALARM_DECLARE_LOCAL(prefix, alarm_event_name) \
+ int64_t prefix##_common_alarm_tl; \
+ pthread_t prefix##_common_win_alarm_thread;
+
+#define COMMON_ALARM_INIT(prefix, alarm_event_name, duration) \
+ prefix##_common_alarm_tl = -1 * (duration) * SECOND_TIMER; \
+ prefix##_common_alarm_timer_length.LowPart = \
+ (DWORD) (prefix##_common_alarm_tl & 0xFFFFFFFF); \
+ prefix##_common_alarm_timer_length.HighPart = \
+ (LONG) (prefix##_common_alarm_tl >> 32); \
+ alarm_event_name = CreateEvent(NULL, false, false, NULL); \
+ assert(alarm_event_name != NULL); \
+ prefix##_common_win_alarm_timer = CreateWaitableTimer(NULL, true, NULL); \
+ assert(prefix##_common_win_alarm_timer != NULL); \
+ if (pthread_create(&prefix##_common_win_alarm_thread, \
+ NULL, \
+ prefix##_common_win_alarm, \
+ NULL) != 0) \
+ ck_error("ERROR: Failed to create common_win_alarm thread.\n");
+#else
+#define COMMON_ALARM_DECLARE_GLOBAL(prefix, alarm_event_name, flag_name)
+#define COMMON_ALARM_DECLARE_LOCAL(prefix, alarm_event_name) \
+ int alarm_event_name = 0;
+#define COMMON_ALARM_INIT(prefix, alarm_event_name, duration)
+#endif
+
+struct affinity {
+ unsigned int delta;
+ unsigned int request;
+};
+
+#define AFFINITY_INITIALIZER {0, 0}
+
+#ifdef __linux__
+#ifndef gettid
+static pid_t
+gettid(void)
+{
+ return syscall(__NR_gettid);
+}
+#endif /* gettid */
+
+CK_CC_UNUSED static int
+aff_iterate(struct affinity *acb)
+{
+ cpu_set_t s;
+ unsigned int c;
+
+ c = ck_pr_faa_uint(&acb->request, acb->delta);
+ CPU_ZERO(&s);
+ CPU_SET(c % CORES, &s);
+
+ return sched_setaffinity(gettid(), sizeof(s), &s);
+}
+
+CK_CC_UNUSED static int
+aff_iterate_core(struct affinity *acb, unsigned int *core)
+{
+ cpu_set_t s;
+
+ *core = ck_pr_faa_uint(&acb->request, acb->delta);
+ CPU_ZERO(&s);
+ CPU_SET((*core) % CORES, &s);
+
+ return sched_setaffinity(gettid(), sizeof(s), &s);
+}
+#elif defined(__MACH__)
+CK_CC_UNUSED static int
+aff_iterate(struct affinity *acb)
+{
+ thread_affinity_policy_data_t policy;
+ unsigned int c;
+
+ c = ck_pr_faa_uint(&acb->request, acb->delta) % CORES;
+ policy.affinity_tag = c;
+ return thread_policy_set(mach_thread_self(),
+ THREAD_AFFINITY_POLICY,
+ (thread_policy_t)&policy,
+ THREAD_AFFINITY_POLICY_COUNT);
+}
+
+CK_CC_UNUSED static int
+aff_iterate_core(struct affinity *acb, unsigned int *core)
+{
+ thread_affinity_policy_data_t policy;
+
+ *core = ck_pr_faa_uint(&acb->request, acb->delta) % CORES;
+ policy.affinity_tag = *core;
+ return thread_policy_set(mach_thread_self(),
+ THREAD_AFFINITY_POLICY,
+ (thread_policy_t)&policy,
+ THREAD_AFFINITY_POLICY_COUNT);
+}
+#elif defined(__FreeBSD__)
+CK_CC_UNUSED static int
+aff_iterate(struct affinity *acb CK_CC_UNUSED)
+{
+ unsigned int c;
+ cpuset_t mask;
+
+ c = ck_pr_faa_uint(&acb->request, acb->delta) % CORES;
+ CPU_ZERO(&mask);
+ CPU_SET(c, &mask);
+ return (cpuset_setaffinity(CPU_LEVEL_WHICH, CPU_WHICH_TID, -1,
+ sizeof(mask), &mask));
+}
+
+CK_CC_UNUSED static int
+aff_iterate_core(struct affinity *acb CK_CC_UNUSED, unsigned int *core)
+{
+ cpuset_t mask;
+
+ *core = ck_pr_faa_uint(&acb->request, acb->delta) % CORES;
+ CPU_ZERO(&mask);
+ CPU_SET(*core, &mask);
+ return (cpuset_setaffinity(CPU_LEVEL_WHICH, CPU_WHICH_TID, -1,
+ sizeof(mask), &mask));
+}
+#else
+CK_CC_UNUSED static int
+aff_iterate(struct affinity *acb CK_CC_UNUSED)
+{
+
+ return (0);
+}
+
+CK_CC_UNUSED static int
+aff_iterate_core(struct affinity *acb CK_CC_UNUSED, unsigned int *core)
+{
+ *core = 0;
+ return (0);
+}
+#endif
+
+CK_CC_INLINE static uint64_t
+rdtsc(void)
+{
+#if defined(__x86_64__)
+ uint32_t eax = 0, edx;
+#if defined(CK_MD_RDTSCP)
+ __asm__ __volatile__("rdtscp"
+ : "+a" (eax), "=d" (edx)
+ :
+ : "%ecx", "memory");
+
+ return (((uint64_t)edx << 32) | eax);
+#else
+ __asm__ __volatile__("cpuid;"
+ "rdtsc;"
+ : "+a" (eax), "=d" (edx)
+ :
+ : "%ebx", "%ecx", "memory");
+
+ __asm__ __volatile__("xorl %%eax, %%eax;"
+ "cpuid;"
+ :
+ :
+ : "%eax", "%ebx", "%ecx", "%edx", "memory");
+
+ return (((uint64_t)edx << 32) | eax);
+#endif /* !CK_MD_RDTSCP */
+#elif defined(__x86__)
+ uint32_t eax = 0, edx;
+#if defined(CK_MD_RDTSCP)
+ __asm__ __volatile__("rdtscp"
+ : "+a" (eax), "=d" (edx)
+ :
+ : "%ecx", "memory");
+
+ return (((uint64_t)edx << 32) | eax);
+#else
+ __asm__ __volatile__("pushl %%ebx;"
+ "cpuid;"
+ "rdtsc;"
+ : "+a" (eax), "=d" (edx)
+ :
+ : "%ecx", "memory");
+
+ __asm__ __volatile__("xorl %%eax, %%eax;"
+ "cpuid;"
+ "popl %%ebx;"
+ :
+ :
+ : "%eax", "%ecx", "%edx", "memory");
+
+ return (((uint64_t)edx << 32) | eax);
+#endif /* !CK_MD_RDTSCP */
+#elif defined(__sparcv9__)
+ uint64_t r;
+
+ __asm__ __volatile__("rd %%tick, %0"
+ : "=r" (r)
+ :
+ : "memory");
+ return r;
+#elif defined(__ppc64__)
+ uint32_t high, low, snapshot;
+
+ do {
+ __asm__ __volatile__("isync;"
+ "mftbu %0;"
+ "mftb %1;"
+ "mftbu %2;"
+ : "=r" (high), "=r" (low), "=r" (snapshot)
+ :
+ : "memory");
+ } while (snapshot != high);
+
+ return (((uint64_t)high << 32) | low);
+#else
+ return 0;
+#endif
+}
+
+CK_CC_USED static void
+ck_error(const char *message, ...)
+{
+ va_list ap;
+
+ va_start(ap, message);
+ vfprintf(stderr, message, ap);
+ va_end(ap);
+ exit(EXIT_FAILURE);
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/Makefile.in
----------------------------------------------------------------------
diff --git a/lib/ck/src/Makefile.in b/lib/ck/src/Makefile.in
new file mode 100644
index 0000000..baef71b
--- /dev/null
+++ b/lib/ck/src/Makefile.in
@@ -0,0 +1,62 @@
+.PHONY: clean distribution
+
+include @BUILD_DIR@/build/ck.build
+
+TARGET_DIR=$(BUILD_DIR)/src
+SDIR=$(SRC_DIR)/src
+INCLUDE_DIR=$(SRC_DIR)/include
+
+OBJECTS=ck_barrier_centralized.o \
+ ck_barrier_combining.o \
+ ck_barrier_dissemination.o \
+ ck_barrier_tournament.o \
+ ck_barrier_mcs.o \
+ ck_epoch.o \
+ ck_ht.o \
+ ck_hp.o \
+ ck_hs.o \
+ ck_rhs.o \
+ ck_array.o
+
+all: $(ALL_LIBS)
+
+libck.so: $(OBJECTS)
+ $(LD) $(LDFLAGS) -o $(TARGET_DIR)/libck.so $(OBJECTS)
+
+libck.a: $(OBJECTS)
+ ar rcs $(TARGET_DIR)/libck.a $(OBJECTS)
+
+ck_array.o: $(INCLUDE_DIR)/ck_array.h $(SDIR)/ck_array.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_array.o $(SDIR)/ck_array.c
+
+ck_epoch.o: $(INCLUDE_DIR)/ck_epoch.h $(SDIR)/ck_epoch.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_epoch.o $(SDIR)/ck_epoch.c
+
+ck_hs.o: $(INCLUDE_DIR)/ck_hs.h $(SDIR)/ck_hs.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_hs.o $(SDIR)/ck_hs.c
+
+ck_ht.o: $(INCLUDE_DIR)/ck_ht.h $(SDIR)/ck_ht.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_ht.o $(SDIR)/ck_ht.c
+
+ck_hp.o: $(SDIR)/ck_hp.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_hp.o $(SDIR)/ck_hp.c
+
+ck_barrier_centralized.o: $(SDIR)/ck_barrier_centralized.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_barrier_centralized.o $(SDIR)/ck_barrier_centralized.c
+
+ck_barrier_combining.o: $(SDIR)/ck_barrier_combining.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_barrier_combining.o $(SDIR)/ck_barrier_combining.c
+
+ck_barrier_dissemination.o: $(SDIR)/ck_barrier_dissemination.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_barrier_dissemination.o $(SDIR)/ck_barrier_dissemination.c
+
+ck_barrier_tournament.o: $(SDIR)/ck_barrier_tournament.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_barrier_tournament.o $(SDIR)/ck_barrier_tournament.c
+
+ck_barrier_mcs.o: $(SDIR)/ck_barrier_mcs.c
+ $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_barrier_mcs.o $(SDIR)/ck_barrier_mcs.c
+
+clean:
+ rm -rf $(TARGET_DIR)/*.dSYM $(TARGET_DIR)/*~ $(TARGET_DIR)/*.o \
+ $(OBJECTS) $(TARGET_DIR)/libck.a $(TARGET_DIR)/libck.so
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_array.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_array.c b/lib/ck/src/ck_array.c
new file mode 100644
index 0000000..238ce0b
--- /dev/null
+++ b/lib/ck/src/ck_array.c
@@ -0,0 +1,241 @@
+/*
+ * Copyright 2013-2014 Samy Al Bahra
+ * Copyright 2013-2014 AppNexus, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 <ck_array.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+#include <string.h>
+
+static struct _ck_array *
+ck_array_create(struct ck_malloc *allocator, unsigned int length)
+{
+ struct _ck_array *active;
+
+ active = allocator->malloc(sizeof(struct _ck_array) + sizeof(void *) * length);
+ if (active == NULL)
+ return NULL;
+
+ active->n_committed = 0;
+ active->length = length;
+
+ return active;
+}
+
+bool
+ck_array_init(struct ck_array *array, unsigned int mode, struct ck_malloc *allocator, unsigned int length)
+{
+ struct _ck_array *active;
+
+ (void)mode;
+
+ if (allocator->realloc == NULL ||
+ allocator->malloc == NULL ||
+ allocator->free == NULL ||
+ length == 0)
+ return false;
+
+ active = ck_array_create(allocator, length);
+ if (active == NULL)
+ return false;
+
+ array->n_entries = 0;
+ array->allocator = allocator;
+ array->active = active;
+ array->transaction = NULL;
+ return true;
+}
+
+bool
+ck_array_put(struct ck_array *array, void *value)
+{
+ struct _ck_array *target;
+ unsigned int size;
+
+ /*
+ * If no transaction copy has been necessary, attempt to do in-place
+ * modification of the array.
+ */
+ if (array->transaction == NULL) {
+ target = array->active;
+
+ if (array->n_entries == target->length) {
+ size = target->length << 1;
+
+ target = array->allocator->realloc(target,
+ sizeof(struct _ck_array) + sizeof(void *) * array->n_entries,
+ sizeof(struct _ck_array) + sizeof(void *) * size,
+ true);
+
+ if (target == NULL)
+ return false;
+
+ ck_pr_store_uint(&target->length, size);
+
+ /* Serialize with respect to contents. */
+ ck_pr_fence_store();
+ ck_pr_store_ptr(&array->active, target);
+ }
+
+ target->values[array->n_entries++] = value;
+ return true;
+ }
+
+ target = array->transaction;
+ if (array->n_entries == target->length) {
+ size = target->length << 1;
+
+ target = array->allocator->realloc(target,
+ sizeof(struct _ck_array) + sizeof(void *) * array->n_entries,
+ sizeof(struct _ck_array) + sizeof(void *) * size,
+ true);
+
+ if (target == NULL)
+ return false;
+
+ target->length = size;
+ array->transaction = target;
+ }
+
+ target->values[array->n_entries++] = value;
+ return false;
+}
+
+int
+ck_array_put_unique(struct ck_array *array, void *value)
+{
+ unsigned int i, limit;
+ void **v;
+
+ limit = array->n_entries;
+ if (array->transaction != NULL) {
+ v = array->transaction->values;
+ } else {
+ v = array->active->values;
+ }
+
+ for (i = 0; i < limit; i++) {
+ if (v[i] == value)
+ return 1;
+ }
+
+ return -!ck_array_put(array, value);
+}
+
+bool
+ck_array_remove(struct ck_array *array, void *value)
+{
+ struct _ck_array *target;
+ unsigned int i;
+
+ if (array->transaction != NULL) {
+ target = array->transaction;
+
+ for (i = 0; i < array->n_entries; i++) {
+ if (target->values[i] == value) {
+ target->values[i] = target->values[--array->n_entries];
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ target = array->active;
+
+ for (i = 0; i < array->n_entries; i++) {
+ if (target->values[i] == value)
+ break;
+ }
+
+ if (i == array->n_entries)
+ return false;
+
+ /* If there are pending additions, immediately eliminate the operation. */
+ if (target->n_committed != array->n_entries) {
+ ck_pr_store_ptr(&target->values[i], target->values[--array->n_entries]);
+ return true;
+ }
+
+ /*
+ * The assumption is that these allocations are small to begin with.
+ * If there is no immediate opportunity for transaction, allocate a
+ * transactional array which will be applied upon commit time.
+ */
+ target = ck_array_create(array->allocator, array->n_entries);
+ if (target == NULL)
+ return false;
+
+ memcpy(target->values, array->active->values, sizeof(void *) * array->n_entries);
+ target->length = array->n_entries;
+ target->n_committed = array->n_entries;
+ target->values[i] = target->values[--array->n_entries];
+
+ array->transaction = target;
+ return true;
+}
+
+bool
+ck_array_commit(ck_array_t *array)
+{
+ struct _ck_array *m = array->transaction;
+
+ if (m != NULL) {
+ struct _ck_array *p;
+
+ m->n_committed = array->n_entries;
+ ck_pr_fence_store();
+ p = array->active;
+ ck_pr_store_ptr(&array->active, m);
+ array->allocator->free(p, sizeof(struct _ck_array) +
+ p->length * sizeof(void *), true);
+ array->transaction = NULL;
+
+ return true;
+ }
+
+ ck_pr_fence_store();
+ ck_pr_store_uint(&array->active->n_committed, array->n_entries);
+ return true;
+}
+
+void
+ck_array_deinit(struct ck_array *array, bool defer)
+{
+
+ array->allocator->free(array->active,
+ sizeof(struct _ck_array) + sizeof(void *) * array->active->length, defer);
+
+ if (array->transaction != NULL) {
+ array->allocator->free(array->transaction,
+ sizeof(struct _ck_array) + sizeof(void *) * array->transaction->length, defer);
+ }
+
+ array->transaction = array->active = NULL;
+ return;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_barrier_centralized.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_barrier_centralized.c b/lib/ck/src/ck_barrier_centralized.c
new file mode 100644
index 0000000..f0604a0
--- /dev/null
+++ b/lib/ck/src/ck_barrier_centralized.c
@@ -0,0 +1,60 @@
+/*
+ * Copyright 2011-2014 Samy Al Bahra.
+ * Copyright 2011 David Joseph.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 <ck_barrier.h>
+#include <ck_pr.h>
+
+void
+ck_barrier_centralized(struct ck_barrier_centralized *barrier,
+ struct ck_barrier_centralized_state *state,
+ unsigned int n_threads)
+{
+ unsigned int sense, value;
+
+ /*
+ * Every execution context has a sense associated with it.
+ * This sense is reversed when the barrier is entered. Every
+ * thread will spin on the global sense until the last thread
+ * reverses it.
+ */
+ sense = state->sense = ~state->sense;
+ value = ck_pr_faa_uint(&barrier->value, 1);
+ if (value == n_threads - 1) {
+ ck_pr_store_uint(&barrier->value, 0);
+ ck_pr_fence_memory();
+ ck_pr_store_uint(&barrier->sense, sense);
+ return;
+ }
+
+ ck_pr_fence_load();
+ while (sense != ck_pr_load_uint(&barrier->sense))
+ ck_pr_stall();
+
+ ck_pr_fence_memory();
+ return;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_barrier_combining.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_barrier_combining.c b/lib/ck/src/ck_barrier_combining.c
new file mode 100644
index 0000000..b9df1d4
--- /dev/null
+++ b/lib/ck/src/ck_barrier_combining.c
@@ -0,0 +1,208 @@
+/*
+ * Copyright 2011-2014 Samy Al Bahra.
+ * Copyright 2011 David Joseph.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 <ck_barrier.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <ck_spinlock.h>
+
+struct ck_barrier_combining_queue {
+ struct ck_barrier_combining_group *head;
+ struct ck_barrier_combining_group *tail;
+};
+
+CK_CC_INLINE static struct ck_barrier_combining_group *
+ck_barrier_combining_queue_dequeue(struct ck_barrier_combining_queue *queue)
+{
+ struct ck_barrier_combining_group *front = NULL;
+
+ if (queue->head != NULL) {
+ front = queue->head;
+ queue->head = queue->head->next;
+ }
+
+ return front;
+}
+
+CK_CC_INLINE static void
+ck_barrier_combining_insert(struct ck_barrier_combining_group *parent,
+ struct ck_barrier_combining_group *tnode,
+ struct ck_barrier_combining_group **child)
+{
+
+ *child = tnode;
+ tnode->parent = parent;
+
+ /*
+ * After inserting, we must increment the parent group's count for
+ * number of threads expected to reach it; otherwise, the
+ * barrier may end prematurely.
+ */
+ parent->k++;
+ return;
+}
+
+/*
+ * This implementation of software combining tree barriers
+ * uses level order traversal to insert new thread groups
+ * into the barrier's tree. We use a queue to implement this
+ * traversal.
+ */
+CK_CC_INLINE static void
+ck_barrier_combining_queue_enqueue(struct ck_barrier_combining_queue *queue,
+ struct ck_barrier_combining_group *node_value)
+{
+
+ node_value->next = NULL;
+ if (queue->head == NULL) {
+ queue->head = queue->tail = node_value;
+ return;
+ }
+
+ queue->tail->next = node_value;
+ queue->tail = node_value;
+
+ return;
+}
+
+
+void
+ck_barrier_combining_group_init(struct ck_barrier_combining *root,
+ struct ck_barrier_combining_group *tnode,
+ unsigned int nthr)
+{
+ struct ck_barrier_combining_group *node;
+ struct ck_barrier_combining_queue queue;
+
+ queue.head = queue.tail = NULL;
+
+ tnode->k = nthr;
+ tnode->count = 0;
+ tnode->sense = 0;
+ tnode->left = tnode->right = NULL;
+
+ /*
+ * Finds the first available node for linkage into the combining
+ * tree. The use of a spinlock is excusable as this is a one-time
+ * initialization cost.
+ */
+ ck_spinlock_fas_lock(&root->mutex);
+ ck_barrier_combining_queue_enqueue(&queue, root->root);
+ while (queue.head != NULL) {
+ node = ck_barrier_combining_queue_dequeue(&queue);
+
+ /* If the left child is free, link the group there. */
+ if (node->left == NULL) {
+ ck_barrier_combining_insert(node, tnode, &node->left);
+ goto leave;
+ }
+
+ /* If the right child is free, link the group there. */
+ if (node->right == NULL) {
+ ck_barrier_combining_insert(node, tnode, &node->right);
+ goto leave;
+ }
+
+ /*
+ * If unsuccessful, try inserting as a child of the children of the
+ * current node.
+ */
+ ck_barrier_combining_queue_enqueue(&queue, node->left);
+ ck_barrier_combining_queue_enqueue(&queue, node->right);
+ }
+
+leave:
+ ck_spinlock_fas_unlock(&root->mutex);
+ return;
+}
+
+void
+ck_barrier_combining_init(struct ck_barrier_combining *root,
+ struct ck_barrier_combining_group *init_root)
+{
+
+ init_root->k = 0;
+ init_root->count = 0;
+ init_root->sense = 0;
+ init_root->parent = init_root->left = init_root->right = NULL;
+ ck_spinlock_fas_init(&root->mutex);
+ root->root = init_root;
+ return;
+}
+
+static void
+ck_barrier_combining_aux(struct ck_barrier_combining *barrier,
+ struct ck_barrier_combining_group *tnode,
+ unsigned int sense)
+{
+
+ /*
+ * If this is the last thread in the group, it moves on to the parent group.
+ * Otherwise, it spins on this group's sense.
+ */
+ if (ck_pr_faa_uint(&tnode->count, 1) == tnode->k - 1) {
+ /*
+ * If we are and will be the last thread entering the barrier for the
+ * current group then signal the parent group if one exists.
+ */
+ if (tnode->parent != NULL)
+ ck_barrier_combining_aux(barrier, tnode->parent, sense);
+
+ /*
+ * Once the thread returns from its parent(s), it reinitializes the group's
+ * arrival count and signals other threads to continue by flipping the group
+ * sense. Order of these operations is not important since we assume a static
+ * number of threads are members of a barrier for the lifetime of the barrier.
+ * Since count is explicitly reinitialized, it is guaranteed that at any point
+ * tnode->count is equivalent to tnode->k if and only if that many threads
+ * are at the barrier.
+ */
+ ck_pr_store_uint(&tnode->count, 0);
+ ck_pr_fence_store();
+ ck_pr_store_uint(&tnode->sense, ~tnode->sense);
+ } else {
+ ck_pr_fence_memory();
+ while (sense != ck_pr_load_uint(&tnode->sense))
+ ck_pr_stall();
+ }
+
+ return;
+}
+
+void
+ck_barrier_combining(struct ck_barrier_combining *barrier,
+ struct ck_barrier_combining_group *tnode,
+ struct ck_barrier_combining_state *state)
+{
+
+ ck_barrier_combining_aux(barrier, tnode, state->sense);
+
+ /* Reverse the execution context's sense for the next barrier. */
+ state->sense = ~state->sense;
+ return;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_barrier_dissemination.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_barrier_dissemination.c b/lib/ck/src/ck_barrier_dissemination.c
new file mode 100644
index 0000000..867e224
--- /dev/null
+++ b/lib/ck/src/ck_barrier_dissemination.c
@@ -0,0 +1,124 @@
+/*
+ * Copyright 2011-2014 Samy Al Bahra.
+ * Copyright 2011 David Joseph.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 <ck_barrier.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <ck_spinlock.h>
+
+#include "ck_internal.h"
+
+void
+ck_barrier_dissemination_init(struct ck_barrier_dissemination *barrier,
+ struct ck_barrier_dissemination_flag **barrier_internal,
+ unsigned int nthr)
+{
+ unsigned int i, j, k, size, offset;
+ bool p = nthr & (nthr - 1);
+
+ barrier->nthr = nthr;
+ barrier->size = size = ck_internal_log(ck_internal_power_2(nthr));
+ ck_pr_store_uint(&barrier->tid, 0);
+
+ for (i = 0; i < nthr; ++i) {
+ barrier[i].flags[0] = barrier_internal[i];
+ barrier[i].flags[1] = barrier_internal[i] + size;
+ }
+
+ for (i = 0; i < nthr; ++i) {
+ for (k = 0, offset = 1; k < size; ++k, offset <<= 1) {
+ /*
+ * Determine the thread's partner, j, for the current round, k.
+ * Partners are chosen such that by the completion of the barrier,
+ * every thread has been directly (having one of its flag set) or
+ * indirectly (having one of its partners's flags set) signaled
+ * by every other thread in the barrier.
+ */
+ if (p == false)
+ j = (i + offset) & (nthr - 1);
+ else
+ j = (i + offset) % nthr;
+
+ /* Set the thread's partner for round k. */
+ barrier[i].flags[0][k].pflag = &barrier[j].flags[0][k].tflag;
+ barrier[i].flags[1][k].pflag = &barrier[j].flags[1][k].tflag;
+
+ /* Set the thread's flags to false. */
+ barrier[i].flags[0][k].tflag = barrier[i].flags[1][k].tflag = 0;
+ }
+ }
+
+ return;
+}
+
+void
+ck_barrier_dissemination_subscribe(struct ck_barrier_dissemination *barrier,
+ struct ck_barrier_dissemination_state *state)
+{
+
+ state->parity = 0;
+ state->sense = ~0;
+ state->tid = ck_pr_faa_uint(&barrier->tid, 1);
+ return;
+}
+
+unsigned int
+ck_barrier_dissemination_size(unsigned int nthr)
+{
+
+ return (ck_internal_log(ck_internal_power_2(nthr)) << 1);
+}
+
+void
+ck_barrier_dissemination(struct ck_barrier_dissemination *barrier,
+ struct ck_barrier_dissemination_state *state)
+{
+ unsigned int i;
+ unsigned int size = barrier->size;
+
+ for (i = 0; i < size; ++i) {
+ /* Unblock current partner. */
+ ck_pr_store_uint(barrier[state->tid].flags[state->parity][i].pflag, state->sense);
+
+ /* Wait until some other thread unblocks this one. */
+ while (ck_pr_load_uint(&barrier[state->tid].flags[state->parity][i].tflag) != state->sense)
+ ck_pr_stall();
+ }
+
+ /*
+ * Dissemination barriers use two sets of flags to prevent race conditions
+ * between successive calls to the barrier. Parity indicates which set will
+ * be used for the next barrier. They also use a sense reversal technique
+ * to avoid re-initialization of the flags for every two calls to the barrier.
+ */
+ if (state->parity == 1)
+ state->sense = ~state->sense;
+
+ state->parity = 1 - state->parity;
+ return;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_barrier_mcs.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_barrier_mcs.c b/lib/ck/src/ck_barrier_mcs.c
new file mode 100644
index 0000000..ed5959c
--- /dev/null
+++ b/lib/ck/src/ck_barrier_mcs.c
@@ -0,0 +1,141 @@
+/*
+ * Copyright 2011-2014 Samy Al Bahra.
+ * Copyright 2011 David Joseph.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 <ck_barrier.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+
+void
+ck_barrier_mcs_init(struct ck_barrier_mcs *barrier, unsigned int nthr)
+{
+ unsigned int i, j;
+
+ ck_pr_store_uint(&barrier->tid, 0);
+
+ for (i = 0; i < nthr; ++i) {
+ for (j = 0; j < 4; ++j) {
+ /*
+ * If there are still threads that don't have parents,
+ * add it as a child.
+ */
+ barrier[i].havechild[j] = ((i << 2) + j < nthr - 1) ? ~0 : 0;
+
+ /*
+ * childnotready is initialized to havechild to ensure
+ * a thread does not wait for a child that does not exist.
+ */
+ barrier[i].childnotready[j] = barrier[i].havechild[j];
+ }
+
+ /* The root thread does not have a parent. */
+ barrier[i].parent = (i == 0) ?
+ &barrier[i].dummy :
+ &barrier[(i - 1) >> 2].childnotready[(i - 1) & 3];
+
+ /* Leaf threads do not have any children. */
+ barrier[i].children[0] = ((i << 1) + 1 >= nthr) ?
+ &barrier[i].dummy :
+ &barrier[(i << 1) + 1].parentsense;
+
+ barrier[i].children[1] = ((i << 1) + 2 >= nthr) ?
+ &barrier[i].dummy :
+ &barrier[(i << 1) + 2].parentsense;
+
+ barrier[i].parentsense = 0;
+ }
+
+ return;
+}
+
+void
+ck_barrier_mcs_subscribe(struct ck_barrier_mcs *barrier, struct ck_barrier_mcs_state *state)
+{
+
+ state->sense = ~0;
+ state->vpid = ck_pr_faa_uint(&barrier->tid, 1);
+ return;
+}
+
+CK_CC_INLINE static bool
+ck_barrier_mcs_check_children(unsigned int *childnotready)
+{
+
+ if (ck_pr_load_uint(&childnotready[0]) != 0)
+ return false;
+ if (ck_pr_load_uint(&childnotready[1]) != 0)
+ return false;
+ if (ck_pr_load_uint(&childnotready[2]) != 0)
+ return false;
+ if (ck_pr_load_uint(&childnotready[3]) != 0)
+ return false;
+
+ return true;
+}
+
+CK_CC_INLINE static void
+ck_barrier_mcs_reinitialize_children(struct ck_barrier_mcs *node)
+{
+
+ ck_pr_store_uint(&node->childnotready[0], node->havechild[0]);
+ ck_pr_store_uint(&node->childnotready[1], node->havechild[1]);
+ ck_pr_store_uint(&node->childnotready[2], node->havechild[2]);
+ ck_pr_store_uint(&node->childnotready[3], node->havechild[3]);
+ return;
+}
+
+void
+ck_barrier_mcs(struct ck_barrier_mcs *barrier,
+ struct ck_barrier_mcs_state *state)
+{
+
+ /*
+ * Wait until all children have reached the barrier and are done waiting
+ * for their children.
+ */
+ while (ck_barrier_mcs_check_children(barrier[state->vpid].childnotready) == false)
+ ck_pr_stall();
+
+ /* Reinitialize for next barrier. */
+ ck_barrier_mcs_reinitialize_children(&barrier[state->vpid]);
+
+ /* Inform parent thread and its children have arrived at the barrier. */
+ ck_pr_store_uint(barrier[state->vpid].parent, 0);
+
+ /* Wait until parent indicates all threads have arrived at the barrier. */
+ if (state->vpid != 0) {
+ while (ck_pr_load_uint(&barrier[state->vpid].parentsense) != state->sense)
+ ck_pr_stall();
+ }
+
+ /* Inform children of successful barrier. */
+ ck_pr_store_uint(barrier[state->vpid].children[0], state->sense);
+ ck_pr_store_uint(barrier[state->vpid].children[1], state->sense);
+ state->sense = ~state->sense;
+ return;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_barrier_tournament.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_barrier_tournament.c b/lib/ck/src/ck_barrier_tournament.c
new file mode 100644
index 0000000..e505890
--- /dev/null
+++ b/lib/ck/src/ck_barrier_tournament.c
@@ -0,0 +1,184 @@
+/*
+ * Copyright 2011-2014 Samy Al Bahra.
+ * Copyright 2011 David Joseph.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 <ck_barrier.h>
+#include <ck_pr.h>
+
+#include "ck_internal.h"
+
+/*
+ * This is a tournament barrier implementation. Threads are statically
+ * assigned roles to perform for each round of the barrier. Winners
+ * move on to the next round, while losers spin in their current rounds
+ * on their own flags. During the last round, the champion of the tournament
+ * sets the last flag that begins the wakeup process.
+ */
+
+enum {
+ CK_BARRIER_TOURNAMENT_BYE,
+ CK_BARRIER_TOURNAMENT_CHAMPION,
+ CK_BARRIER_TOURNAMENT_DROPOUT,
+ CK_BARRIER_TOURNAMENT_LOSER,
+ CK_BARRIER_TOURNAMENT_WINNER
+};
+
+void
+ck_barrier_tournament_subscribe(struct ck_barrier_tournament *barrier,
+ struct ck_barrier_tournament_state *state)
+{
+
+ state->sense = ~0;
+ state->vpid = ck_pr_faa_uint(&barrier->tid, 1);
+ return;
+}
+
+void
+ck_barrier_tournament_init(struct ck_barrier_tournament *barrier,
+ struct ck_barrier_tournament_round **rounds,
+ unsigned int nthr)
+{
+ unsigned int i, k, size, twok, twokm1, imod2k;
+
+ ck_pr_store_uint(&barrier->tid, 0);
+ barrier->size = size = ck_barrier_tournament_size(nthr);
+
+ for (i = 0; i < nthr; ++i) {
+ /* The first role is always CK_BARRIER_TOURNAMENT_DROPOUT. */
+ rounds[i][0].flag = 0;
+ rounds[i][0].role = CK_BARRIER_TOURNAMENT_DROPOUT;
+ for (k = 1, twok = 2, twokm1 = 1; k < size; ++k, twokm1 = twok, twok <<= 1) {
+ rounds[i][k].flag = 0;
+
+ imod2k = i & (twok - 1);
+ if (imod2k == 0) {
+ if ((i + twokm1 < nthr) && (twok < nthr))
+ rounds[i][k].role = CK_BARRIER_TOURNAMENT_WINNER;
+ else if (i + twokm1 >= nthr)
+ rounds[i][k].role = CK_BARRIER_TOURNAMENT_BYE;
+ }
+
+ if (imod2k == twokm1)
+ rounds[i][k].role = CK_BARRIER_TOURNAMENT_LOSER;
+ else if ((i == 0) && (twok >= nthr))
+ rounds[i][k].role = CK_BARRIER_TOURNAMENT_CHAMPION;
+
+ if (rounds[i][k].role == CK_BARRIER_TOURNAMENT_LOSER)
+ rounds[i][k].opponent = &rounds[i - twokm1][k].flag;
+ else if (rounds[i][k].role == CK_BARRIER_TOURNAMENT_WINNER ||
+ rounds[i][k].role == CK_BARRIER_TOURNAMENT_CHAMPION)
+ rounds[i][k].opponent = &rounds[i + twokm1][k].flag;
+ }
+ }
+
+ ck_pr_store_ptr(&barrier->rounds, rounds);
+ return;
+}
+
+unsigned int
+ck_barrier_tournament_size(unsigned int nthr)
+{
+
+ return (ck_internal_log(ck_internal_power_2(nthr)) + 1);
+}
+
+void
+ck_barrier_tournament(struct ck_barrier_tournament *barrier,
+ struct ck_barrier_tournament_state *state)
+{
+ struct ck_barrier_tournament_round **rounds = ck_pr_load_ptr(&barrier->rounds);
+ int round = 1;
+
+ if (barrier->size == 1)
+ return;
+
+ for (;; ++round) {
+ switch (rounds[state->vpid][round].role) {
+ case CK_BARRIER_TOURNAMENT_BYE:
+ break;
+ case CK_BARRIER_TOURNAMENT_CHAMPION:
+ /*
+ * The CK_BARRIER_TOURNAMENT_CHAMPION waits until it wins the tournament; it then
+ * sets the final flag before the wakeup phase of the barrier.
+ */
+ while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense)
+ ck_pr_stall();
+
+ ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense);
+ goto wakeup;
+ case CK_BARRIER_TOURNAMENT_DROPOUT:
+ /* NOTREACHED */
+ break;
+ case CK_BARRIER_TOURNAMENT_LOSER:
+ /*
+ * CK_BARRIER_TOURNAMENT_LOSERs set the flags of their opponents and wait until
+ * their opponents release them after the tournament is over.
+ */
+ ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense);
+ while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense)
+ ck_pr_stall();
+
+ goto wakeup;
+ case CK_BARRIER_TOURNAMENT_WINNER:
+ /*
+ * CK_BARRIER_TOURNAMENT_WINNERs wait until their current opponent sets their flag; they then
+ * continue to the next round of the tournament.
+ */
+ while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense)
+ ck_pr_stall();
+ break;
+ }
+ }
+
+wakeup:
+ for (round -= 1 ;; --round) {
+ switch (rounds[state->vpid][round].role) {
+ case CK_BARRIER_TOURNAMENT_BYE:
+ break;
+ case CK_BARRIER_TOURNAMENT_CHAMPION:
+ /* NOTREACHED */
+ break;
+ case CK_BARRIER_TOURNAMENT_DROPOUT:
+ goto leave;
+ break;
+ case CK_BARRIER_TOURNAMENT_LOSER:
+ /* NOTREACHED */
+ break;
+ case CK_BARRIER_TOURNAMENT_WINNER:
+ /*
+ * Winners inform their old opponents the tournament is over
+ * by setting their flags.
+ */
+ ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense);
+ break;
+ }
+ }
+
+leave:
+ state->sense = ~state->sense;
+ return;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_epoch.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_epoch.c b/lib/ck/src/ck_epoch.c
new file mode 100644
index 0000000..343667c
--- /dev/null
+++ b/lib/ck/src/ck_epoch.c
@@ -0,0 +1,429 @@
+/*
+ * Copyright 2011-2014 Samy Al Bahra.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+ */
+
+/*
+ * The implementation here is inspired from the work described in:
+ * Fraser, K. 2004. Practical Lock-Freedom. PhD Thesis, University
+ * of Cambridge Computing Laboratory.
+ */
+
+#include <ck_backoff.h>
+#include <ck_cc.h>
+#include <ck_epoch.h>
+#include <ck_pr.h>
+#include <ck_stack.h>
+#include <stdbool.h>
+
+/*
+ * Only three distinct values are used for reclamation, but reclamation occurs
+ * at e + 2 rather than e + 1. Any thread in a "critical section" would have
+ * acquired some snapshot (e) of the global epoch value (e_g) and set an active
+ * flag. Any hazardous references will only occur after a full memory barrier.
+ * For example, assume an initial e_g value of 1, e value of 0 and active value
+ * of 0.
+ *
+ * ck_epoch_begin(...)
+ * e = e_g
+ * active = 1
+ * memory_barrier();
+ *
+ * Any serialized reads may observe e = 0 or e = 1 with active = 0, or
+ * e = 0 or e = 1 with active = 1. The e_g value can only go from 1
+ * to 2 if every thread has already observed the value of "1" (or the
+ * value we are incrementing from). This guarantees us that for any
+ * given value e_g, any threads with-in critical sections (referred
+ * to as "active" threads from here on) would have an e value of
+ * e_g - 1 or e_g. This also means that hazardous references may be
+ * shared in both e_g - 1 and e_g even if they are logically deleted
+ * in e_g.
+ *
+ * For example, assume all threads have an e value of e_g. Another
+ * thread may increment to e_g to e_g + 1. Older threads may have
+ * a reference to an object which is only deleted in e_g + 1. It
+ * could be that reader threads are executing some hash table look-ups,
+ * while some other writer thread (which causes epoch counter tick)
+ * actually deletes the same items that reader threads are looking
+ * up (this writer thread having an e value of e_g + 1). This is possible
+ * if the writer thread re-observes the epoch after the counter tick.
+ *
+ * Psuedo-code for writer:
+ * ck_epoch_begin()
+ * ht_delete(x)
+ * ck_epoch_end()
+ * ck_epoch_begin()
+ * ht_delete(x)
+ * ck_epoch_end()
+ *
+ * Psuedo-code for reader:
+ * for (;;) {
+ * x = ht_lookup(x)
+ * ck_pr_inc(&x->value);
+ * }
+ *
+ * Of course, it is also possible for references logically deleted
+ * at e_g - 1 to still be accessed at e_g as threads are "active"
+ * at the same time (real-world time) mutating shared objects.
+ *
+ * Now, if the epoch counter is ticked to e_g + 1, then no new
+ * hazardous references could exist to objects logically deleted at
+ * e_g - 1. The reason for this is that at e_g + 1, all epoch read-side
+ * critical sections started at e_g - 1 must have been completed. If
+ * any epoch read-side critical sections at e_g - 1 were still active,
+ * then we would never increment to e_g + 1 (active != 0 ^ e != e_g).
+ * Additionally, e_g may still have hazardous references to objects
+ * logically deleted at e_g - 1 which means objects logically deleted
+ * at e_g - 1 cannot be deleted at e_g + 1 unless all threads have
+ * observed e_g + 1 (since it is valid for active threads to be at e_g
+ * and threads at e_g still require safe memory accesses).
+ *
+ * However, at e_g + 2, all active threads must be either at e_g + 1 or
+ * e_g + 2. Though e_g + 2 may share hazardous references with e_g + 1,
+ * and e_g + 1 shares hazardous references to e_g, no active threads are
+ * at e_g or e_g - 1. This means no hazardous references could exist to
+ * objects deleted at e_g - 1 (at e_g + 2).
+ *
+ * To summarize these important points,
+ * 1) Active threads will always have a value of e_g or e_g - 1.
+ * 2) Items that are logically deleted e_g or e_g - 1 cannot be
+ * physically deleted.
+ * 3) Objects logically deleted at e_g - 1 can be physically destroyed
+ * at e_g + 2 or at e_g + 1 if no threads are at e_g.
+ *
+ * Last but not least, if we are at e_g + 2, then no active thread is at
+ * e_g which means it is safe to apply modulo-3 arithmetic to e_g value
+ * in order to re-use e_g to represent the e_g + 3 state. This means it is
+ * sufficient to represent e_g using only the values 0, 1 or 2. Every time
+ * a thread re-visits a e_g (which can be determined with a non-empty deferral
+ * list) it can assume objects in the e_g deferral list involved at least
+ * three e_g transitions and are thus, safe, for physical deletion.
+ *
+ * Blocking semantics for epoch reclamation have additional restrictions.
+ * Though we only require three deferral lists, reasonable blocking semantics
+ * must be able to more gracefully handle bursty write work-loads which could
+ * easily cause e_g wrap-around if modulo-3 arithmetic is used. This allows for
+ * easy-to-trigger live-lock situations. The work-around to this is to not apply
+ * modulo arithmetic to e_g but only to deferral list indexing.
+ */
+#define CK_EPOCH_GRACE 3U
+
+enum {
+ CK_EPOCH_STATE_USED = 0,
+ CK_EPOCH_STATE_FREE = 1
+};
+
+CK_STACK_CONTAINER(struct ck_epoch_record, record_next, ck_epoch_record_container)
+CK_STACK_CONTAINER(struct ck_epoch_entry, stack_entry, ck_epoch_entry_container)
+
+void
+ck_epoch_init(struct ck_epoch *global)
+{
+
+ ck_stack_init(&global->records);
+ global->epoch = 1;
+ global->n_free = 0;
+ ck_pr_fence_store();
+ return;
+}
+
+struct ck_epoch_record *
+ck_epoch_recycle(struct ck_epoch *global)
+{
+ struct ck_epoch_record *record;
+ ck_stack_entry_t *cursor;
+ unsigned int state;
+
+ if (ck_pr_load_uint(&global->n_free) == 0)
+ return NULL;
+
+ CK_STACK_FOREACH(&global->records, cursor) {
+ record = ck_epoch_record_container(cursor);
+
+ if (ck_pr_load_uint(&record->state) == CK_EPOCH_STATE_FREE) {
+ /* Serialize with respect to deferral list clean-up. */
+ ck_pr_fence_load();
+ state = ck_pr_fas_uint(&record->state, CK_EPOCH_STATE_USED);
+ if (state == CK_EPOCH_STATE_FREE) {
+ ck_pr_dec_uint(&global->n_free);
+ return record;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+void
+ck_epoch_register(struct ck_epoch *global, struct ck_epoch_record *record)
+{
+ size_t i;
+
+ record->state = CK_EPOCH_STATE_USED;
+ record->active = 0;
+ record->epoch = 0;
+ record->n_dispatch = 0;
+ record->n_peak = 0;
+ record->n_pending = 0;
+
+ for (i = 0; i < CK_EPOCH_LENGTH; i++)
+ ck_stack_init(&record->pending[i]);
+
+ ck_pr_fence_store();
+ ck_stack_push_upmc(&global->records, &record->record_next);
+ return;
+}
+
+void
+ck_epoch_unregister(struct ck_epoch *global, struct ck_epoch_record *record)
+{
+ size_t i;
+
+ record->active = 0;
+ record->epoch = 0;
+ record->n_dispatch = 0;
+ record->n_peak = 0;
+ record->n_pending = 0;
+
+ for (i = 0; i < CK_EPOCH_LENGTH; i++)
+ ck_stack_init(&record->pending[i]);
+
+ ck_pr_fence_store();
+ ck_pr_store_uint(&record->state, CK_EPOCH_STATE_FREE);
+ ck_pr_inc_uint(&global->n_free);
+ return;
+}
+
+static struct ck_epoch_record *
+ck_epoch_scan(struct ck_epoch *global,
+ struct ck_epoch_record *cr,
+ unsigned int epoch,
+ bool *af)
+{
+ ck_stack_entry_t *cursor;
+
+ *af = false;
+ if (cr == NULL) {
+ cursor = CK_STACK_FIRST(&global->records);
+ } else {
+ cursor = &cr->record_next;
+ }
+
+ while (cursor != NULL) {
+ unsigned int state, active;
+
+ cr = ck_epoch_record_container(cursor);
+
+ state = ck_pr_load_uint(&cr->state);
+ if (state & CK_EPOCH_STATE_FREE) {
+ cursor = CK_STACK_NEXT(cursor);
+ continue;
+ }
+
+ active = ck_pr_load_uint(&cr->active);
+ *af |= active;
+
+ if (active != 0 && ck_pr_load_uint(&cr->epoch) != epoch)
+ return cr;
+
+ cursor = CK_STACK_NEXT(cursor);
+ }
+
+ return NULL;
+}
+
+static void
+ck_epoch_dispatch(struct ck_epoch_record *record, unsigned int e)
+{
+ unsigned int epoch = e & (CK_EPOCH_LENGTH - 1);
+ ck_stack_entry_t *next, *cursor;
+ unsigned int i = 0;
+
+ CK_STACK_FOREACH_SAFE(&record->pending[epoch], cursor, next) {
+ struct ck_epoch_entry *entry = ck_epoch_entry_container(cursor);
+
+ entry->function(entry);
+ i++;
+ }
+
+ if (record->n_pending > record->n_peak)
+ record->n_peak = record->n_pending;
+
+ record->n_dispatch += i;
+ record->n_pending -= i;
+ ck_stack_init(&record->pending[epoch]);
+ return;
+}
+
+/*
+ * Reclaim all objects associated with a record.
+ */
+void
+ck_epoch_reclaim(struct ck_epoch_record *record)
+{
+ unsigned int epoch;
+
+ for (epoch = 0; epoch < CK_EPOCH_LENGTH; epoch++)
+ ck_epoch_dispatch(record, epoch);
+
+ return;
+}
+
+/*
+ * This function must not be called with-in read section.
+ */
+void
+ck_epoch_synchronize(struct ck_epoch *global, struct ck_epoch_record *record)
+{
+ struct ck_epoch_record *cr;
+ unsigned int delta, epoch, goal, i;
+ bool active;
+
+ /*
+ * Technically, we are vulnerable to an overflow in presence of multiple
+ * writers. Realistically, this will require 2^32 scans. You can use
+ * epoch-protected sections on the writer-side if this is a concern.
+ */
+ delta = epoch = ck_pr_load_uint(&global->epoch);
+ goal = epoch + CK_EPOCH_GRACE;
+
+ /*
+ * Guarantee any mutations previous to the barrier will be made visible
+ * with respect to epoch snapshots we will read.
+ */
+ ck_pr_fence_memory();
+
+ for (i = 0, cr = NULL; i < CK_EPOCH_GRACE - 1; cr = NULL, i++) {
+ /*
+ * Determine whether all threads have observed the current epoch.
+ * We can get away without a fence here.
+ */
+ while (cr = ck_epoch_scan(global, cr, delta, &active), cr != NULL) {
+ unsigned int e_d;
+
+ ck_pr_stall();
+
+ /* Another writer may have already observed a grace period. */
+ e_d = ck_pr_load_uint(&global->epoch);
+ if (e_d != delta) {
+ delta = e_d;
+ goto reload;
+ }
+ }
+
+ /*
+ * If we have observed all threads as inactive, then we assume
+ * we are at a grace period.
+ */
+ if (active == false)
+ break;
+
+ /*
+ * Increment current epoch. CAS semantics are used to eliminate
+ * increment operations for synchronization that occurs for the
+ * same global epoch value snapshot.
+ *
+ * If we can guarantee there will only be one active barrier
+ * or epoch tick at a given time, then it is sufficient to
+ * use an increment operation. In a multi-barrier workload,
+ * however, it is possible to overflow the epoch value if we
+ * apply modulo-3 arithmetic.
+ */
+ if (ck_pr_cas_uint_value(&global->epoch, delta, delta + 1, &delta) == true) {
+ delta = delta + 1;
+ continue;
+ }
+
+reload:
+ if ((goal > epoch) & (delta >= goal)) {
+ /*
+ * Right now, epoch overflow is handled as an edge case. If
+ * we have already observed an epoch generation, then we can
+ * be sure no hazardous references exist to objects from this
+ * generation. We can actually avoid an addtional scan step
+ * at this point.
+ */
+ break;
+ }
+ }
+
+ record->epoch = delta;
+ return;
+}
+
+void
+ck_epoch_barrier(struct ck_epoch *global, struct ck_epoch_record *record)
+{
+
+ ck_epoch_synchronize(global, record);
+ ck_epoch_reclaim(record);
+ return;
+}
+
+/*
+ * It may be worth it to actually apply these deferral semantics to an epoch
+ * that was observed at ck_epoch_call time. The problem is that the latter would
+ * require a full fence.
+ *
+ * ck_epoch_call will dispatch to the latest epoch snapshot that was observed.
+ * There are cases where it will fail to reclaim as early as it could. If this
+ * becomes a problem, we could actually use a heap for epoch buckets but that
+ * is far from ideal too.
+ */
+bool
+ck_epoch_poll(struct ck_epoch *global, struct ck_epoch_record *record)
+{
+ bool active;
+ struct ck_epoch_record *cr = NULL;
+ unsigned int epoch = ck_pr_load_uint(&global->epoch);
+ unsigned int snapshot;
+
+ /* Serialize record epoch snapshots with respect to global epoch load. */
+ ck_pr_fence_memory();
+ cr = ck_epoch_scan(global, cr, epoch, &active);
+ if (cr != NULL) {
+ record->epoch = epoch;
+ return false;
+ }
+
+ /* We are at a grace period if all threads are inactive. */
+ if (active == false) {
+ record->epoch = epoch;
+ for (epoch = 0; epoch < CK_EPOCH_LENGTH; epoch++)
+ ck_epoch_dispatch(record, epoch);
+
+ return true;
+ }
+
+ /* If an active thread exists, rely on epoch observation. */
+ if (ck_pr_cas_uint_value(&global->epoch, epoch, epoch + 1, &snapshot) == false) {
+ record->epoch = snapshot;
+ } else {
+ record->epoch = epoch + 1;
+ }
+
+ ck_epoch_dispatch(record, epoch + 1);
+ return true;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_hp.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_hp.c b/lib/ck/src/ck_hp.c
new file mode 100644
index 0000000..634d94d
--- /dev/null
+++ b/lib/ck/src/ck_hp.c
@@ -0,0 +1,324 @@
+/*
+ * Copyright 2010-2014 Samy Al Bahra.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+ */
+
+/*
+ * (c) Copyright 2008, IBM Corporation.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * This is an implementation of hazard pointers as detailed in:
+ * http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf
+ *
+ * This API provides a publishing mechanism that defers destruction of
+ * hazard pointers until it is safe to do so. Preventing arbitrary re-use
+ * protects against the ABA problem and provides safe memory reclamation.
+ * The implementation was derived from the Hazard Pointers implementation
+ * from the Amino CBBS project. It has been heavily modified for Concurrency
+ * Kit.
+ */
+
+#include <ck_backoff.h>
+#include <ck_cc.h>
+#include <ck_hp.h>
+#include <ck_pr.h>
+#include <ck_stack.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+CK_STACK_CONTAINER(struct ck_hp_record, global_entry, ck_hp_record_container)
+CK_STACK_CONTAINER(struct ck_hp_hazard, pending_entry, ck_hp_hazard_container)
+
+void
+ck_hp_init(struct ck_hp *state,
+ unsigned int degree,
+ unsigned int threshold,
+ ck_hp_destructor_t destroy)
+{
+
+ state->threshold = threshold;
+ state->degree = degree;
+ state->destroy = destroy;
+ state->n_subscribers = 0;
+ state->n_free = 0;
+ ck_stack_init(&state->subscribers);
+ ck_pr_fence_store();
+
+ return;
+}
+
+void
+ck_hp_set_threshold(struct ck_hp *state, unsigned int threshold)
+{
+
+ ck_pr_store_uint(&state->threshold, threshold);
+ return;
+}
+
+struct ck_hp_record *
+ck_hp_recycle(struct ck_hp *global)
+{
+ struct ck_hp_record *record;
+ ck_stack_entry_t *entry;
+ int state;
+
+ if (ck_pr_load_uint(&global->n_free) == 0)
+ return NULL;
+
+ CK_STACK_FOREACH(&global->subscribers, entry) {
+ record = ck_hp_record_container(entry);
+
+ if (ck_pr_load_int(&record->state) == CK_HP_FREE) {
+ ck_pr_fence_load();
+ state = ck_pr_fas_int(&record->state, CK_HP_USED);
+ if (state == CK_HP_FREE) {
+ ck_pr_dec_uint(&global->n_free);
+ return record;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+void
+ck_hp_unregister(struct ck_hp_record *entry)
+{
+
+ entry->n_pending = 0;
+ entry->n_peak = 0;
+ entry->n_reclamations = 0;
+ ck_stack_init(&entry->pending);
+ ck_pr_fence_store();
+ ck_pr_store_int(&entry->state, CK_HP_FREE);
+ ck_pr_inc_uint(&entry->global->n_free);
+ return;
+}
+
+void
+ck_hp_register(struct ck_hp *state,
+ struct ck_hp_record *entry,
+ void **pointers)
+{
+
+ entry->state = CK_HP_USED;
+ entry->global = state;
+ entry->pointers = pointers;
+ entry->n_pending = 0;
+ entry->n_peak = 0;
+ entry->n_reclamations = 0;
+ memset(pointers, 0, state->degree * sizeof(void *));
+ ck_stack_init(&entry->pending);
+ ck_pr_fence_store();
+ ck_stack_push_upmc(&state->subscribers, &entry->global_entry);
+ ck_pr_inc_uint(&state->n_subscribers);
+ return;
+}
+
+static int
+hazard_compare(const void *a, const void *b)
+{
+ void * const *x;
+ void * const *y;
+
+ x = a;
+ y = b;
+ return ((*x > *y) - (*x < *y));
+}
+
+CK_CC_INLINE static bool
+ck_hp_member_scan(ck_stack_entry_t *entry, unsigned int degree, void *pointer)
+{
+ struct ck_hp_record *record;
+ unsigned int i;
+ void *hazard;
+
+ do {
+ record = ck_hp_record_container(entry);
+ if (ck_pr_load_int(&record->state) == CK_HP_FREE)
+ continue;
+
+ if (ck_pr_load_ptr(&record->pointers) == NULL)
+ continue;
+
+ for (i = 0; i < degree; i++) {
+ hazard = ck_pr_load_ptr(&record->pointers[i]);
+ if (hazard == pointer)
+ return (true);
+ }
+ } while ((entry = CK_STACK_NEXT(entry)) != NULL);
+
+ return (false);
+}
+
+CK_CC_INLINE static void *
+ck_hp_member_cache(struct ck_hp *global, void **cache, unsigned int *n_hazards)
+{
+ struct ck_hp_record *record;
+ ck_stack_entry_t *entry;
+ unsigned int hazards = 0;
+ unsigned int i;
+ void *pointer;
+
+ CK_STACK_FOREACH(&global->subscribers, entry) {
+ record = ck_hp_record_container(entry);
+ if (ck_pr_load_int(&record->state) == CK_HP_FREE)
+ continue;
+
+ if (ck_pr_load_ptr(&record->pointers) == NULL)
+ continue;
+
+ for (i = 0; i < global->degree; i++) {
+ if (hazards > CK_HP_CACHE)
+ break;
+
+ pointer = ck_pr_load_ptr(&record->pointers[i]);
+ if (pointer != NULL)
+ cache[hazards++] = pointer;
+ }
+ }
+
+ *n_hazards = hazards;
+ return (entry);
+}
+
+void
+ck_hp_reclaim(struct ck_hp_record *thread)
+{
+ struct ck_hp_hazard *hazard;
+ struct ck_hp *global = thread->global;
+ unsigned int n_hazards;
+ void **cache, *marker, *match;
+ ck_stack_entry_t *previous, *entry, *next;
+
+ /* Store as many entries as possible in local array. */
+ cache = thread->cache;
+ marker = ck_hp_member_cache(global, cache, &n_hazards);
+
+ /*
+ * In theory, there is an n such that (n * (log n) ** 2) < np.
+ */
+ qsort(cache, n_hazards, sizeof(void *), hazard_compare);
+
+ previous = NULL;
+ CK_STACK_FOREACH_SAFE(&thread->pending, entry, next) {
+ hazard = ck_hp_hazard_container(entry);
+ match = bsearch(&hazard->pointer, cache, n_hazards,
+ sizeof(void *), hazard_compare);
+ if (match != NULL) {
+ previous = entry;
+ continue;
+ }
+
+ if (marker != NULL &&
+ ck_hp_member_scan(marker, global->degree, hazard->pointer)) {
+ previous = entry;
+ continue;
+ }
+
+ thread->n_pending -= 1;
+
+ /* Remove from the pending stack. */
+ if (previous)
+ CK_STACK_NEXT(previous) = CK_STACK_NEXT(entry);
+ else
+ CK_STACK_FIRST(&thread->pending) = CK_STACK_NEXT(entry);
+
+ /* The entry is now safe to destroy. */
+ global->destroy(hazard->data);
+ thread->n_reclamations++;
+ }
+
+ return;
+}
+
+void
+ck_hp_retire(struct ck_hp_record *thread,
+ struct ck_hp_hazard *hazard,
+ void *data,
+ void *pointer)
+{
+
+ ck_pr_store_ptr(&hazard->pointer, pointer);
+ ck_pr_store_ptr(&hazard->data, data);
+ ck_stack_push_spnc(&thread->pending, &hazard->pending_entry);
+
+ thread->n_pending += 1;
+ if (thread->n_pending > thread->n_peak)
+ thread->n_peak = thread->n_pending;
+
+ return;
+}
+
+void
+ck_hp_free(struct ck_hp_record *thread,
+ struct ck_hp_hazard *hazard,
+ void *data,
+ void *pointer)
+{
+ struct ck_hp *global;
+
+ global = ck_pr_load_ptr(&thread->global);
+ ck_pr_store_ptr(&hazard->data, data);
+ ck_pr_store_ptr(&hazard->pointer, pointer);
+ ck_stack_push_spnc(&thread->pending, &hazard->pending_entry);
+
+ thread->n_pending += 1;
+ if (thread->n_pending > thread->n_peak)
+ thread->n_peak = thread->n_pending;
+
+ if (thread->n_pending >= global->threshold)
+ ck_hp_reclaim(thread);
+
+ return;
+}
+
+void
+ck_hp_purge(struct ck_hp_record *thread)
+{
+ ck_backoff_t backoff = CK_BACKOFF_INITIALIZER;
+
+ while (thread->n_pending > 0) {
+ ck_hp_reclaim(thread);
+ if (thread->n_pending > 0)
+ ck_backoff_eb(&backoff);
+ }
+
+ return;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/src/ck_hs.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_hs.c b/lib/ck/src/ck_hs.c
new file mode 100644
index 0000000..6769dad
--- /dev/null
+++ b/lib/ck/src/ck_hs.c
@@ -0,0 +1,845 @@
+/*
+ * Copyright 2012-2014 Samy Al Bahra.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 <ck_cc.h>
+#include <ck_hs.h>
+#include <ck_limits.h>
+#include <ck_md.h>
+#include <ck_pr.h>
+#include <ck_stdint.h>
+#include <stdbool.h>
+#include <string.h>
+
+#include "ck_internal.h"
+
+#ifndef CK_HS_PROBE_L1_SHIFT
+#define CK_HS_PROBE_L1_SHIFT 3ULL
+#endif /* CK_HS_PROBE_L1_SHIFT */
+
+#define CK_HS_PROBE_L1 (1 << CK_HS_PROBE_L1_SHIFT)
+#define CK_HS_PROBE_L1_MASK (CK_HS_PROBE_L1 - 1)
+
+#ifndef CK_HS_PROBE_L1_DEFAULT
+#define CK_HS_PROBE_L1_DEFAULT CK_MD_CACHELINE
+#endif
+
+#define CK_HS_VMA_MASK ((uintptr_t)((1ULL << CK_MD_VMA_BITS) - 1))
+#define CK_HS_VMA(x) \
+ ((void *)((uintptr_t)(x) & CK_HS_VMA_MASK))
+
+#define CK_HS_EMPTY NULL
+#define CK_HS_TOMBSTONE ((void *)~(uintptr_t)0)
+#define CK_HS_G (2)
+#define CK_HS_G_MASK (CK_HS_G - 1)
+
+#if defined(CK_F_PR_LOAD_8) && defined(CK_F_PR_STORE_8)
+#define CK_HS_WORD uint8_t
+#define CK_HS_WORD_MAX UINT8_MAX
+#define CK_HS_STORE(x, y) ck_pr_store_8(x, y)
+#define CK_HS_LOAD(x) ck_pr_load_8(x)
+#elif defined(CK_F_PR_LOAD_16) && defined(CK_F_PR_STORE_16)
+#define CK_HS_WORD uint16_t
+#define CK_HS_WORD_MAX UINT16_MAX
+#define CK_HS_STORE(x, y) ck_pr_store_16(x, y)
+#define CK_HS_LOAD(x) ck_pr_load_16(x)
+#elif defined(CK_F_PR_LOAD_32) && defined(CK_F_PR_STORE_32)
+#define CK_HS_WORD uint32_t
+#define CK_HS_WORD_MAX UINT32_MAX
+#define CK_HS_STORE(x, y) ck_pr_store_32(x, y)
+#define CK_HS_LOAD(x) ck_pr_load_32(x)
+#else
+#error "ck_hs is not supported on your platform."
+#endif
+
+enum ck_hs_probe_behavior {
+ CK_HS_PROBE = 0, /* Default behavior. */
+ CK_HS_PROBE_TOMBSTONE, /* Short-circuit on tombstone. */
+ CK_HS_PROBE_INSERT /* Short-circuit on probe bound if tombstone found. */
+};
+
+struct ck_hs_map {
+ unsigned int generation[CK_HS_G];
+ unsigned int probe_maximum;
+ unsigned long mask;
+ unsigned long step;
+ unsigned int probe_limit;
+ unsigned int tombstones;
+ unsigned long n_entries;
+ unsigned long capacity;
+ unsigned long size;
+ CK_HS_WORD *probe_bound;
+ void **entries;
+};
+
+void
+ck_hs_iterator_init(struct ck_hs_iterator *iterator)
+{
+
+ iterator->cursor = NULL;
+ iterator->offset = 0;
+ return;
+}
+
+bool
+ck_hs_next(struct ck_hs *hs, struct ck_hs_iterator *i, void **key)
+{
+ struct ck_hs_map *map = hs->map;
+ void *value;
+
+ if (i->offset >= map->capacity)
+ return false;
+
+ do {
+ value = map->entries[i->offset];
+ if (value != CK_HS_EMPTY && value != CK_HS_TOMBSTONE) {
+#ifdef CK_HS_PP
+ if (hs->mode & CK_HS_MODE_OBJECT)
+ value = CK_HS_VMA(value);
+#endif
+ i->offset++;
+ *key = value;
+ return true;
+ }
+ } while (++i->offset < map->capacity);
+
+ return false;
+}
+
+void
+ck_hs_stat(struct ck_hs *hs, struct ck_hs_stat *st)
+{
+ struct ck_hs_map *map = hs->map;
+
+ st->n_entries = map->n_entries;
+ st->tombstones = map->tombstones;
+ st->probe_maximum = map->probe_maximum;
+ return;
+}
+
+unsigned long
+ck_hs_count(struct ck_hs *hs)
+{
+
+ return hs->map->n_entries;
+}
+
+static void
+ck_hs_map_destroy(struct ck_malloc *m, struct ck_hs_map *map, bool defer)
+{
+
+ m->free(map, map->size, defer);
+ return;
+}
+
+void
+ck_hs_destroy(struct ck_hs *hs)
+{
+
+ ck_hs_map_destroy(hs->m, hs->map, false);
+ return;
+}
+
+static struct ck_hs_map *
+ck_hs_map_create(struct ck_hs *hs, unsigned long entries)
+{
+ struct ck_hs_map *map;
+ unsigned long size, n_entries, prefix, limit;
+
+ n_entries = ck_internal_power_2(entries);
+ if (n_entries < CK_HS_PROBE_L1)
+ return NULL;
+
+ size = sizeof(struct ck_hs_map) + (sizeof(void *) * n_entries + CK_MD_CACHELINE - 1);
+
+ if (hs->mode & CK_HS_MODE_DELETE) {
+ prefix = sizeof(CK_HS_WORD) * n_entries;
+ size += prefix;
+ } else {
+ prefix = 0;
+ }
+
+ map = hs->m->malloc(size);
+ if (map == NULL)
+ return NULL;
+
+ map->size = size;
+
+ /* We should probably use a more intelligent heuristic for default probe length. */
+ limit = ck_internal_max(n_entries >> (CK_HS_PROBE_L1_SHIFT + 2), CK_HS_PROBE_L1_DEFAULT);
+ if (limit > UINT_MAX)
+ limit = UINT_MAX;
+
+ map->probe_limit = (unsigned int)limit;
+ map->probe_maximum = 0;
+ map->capacity = n_entries;
+ map->step = ck_internal_bsf(n_entries);
+ map->mask = n_entries - 1;
+ map->n_entries = 0;
+
+ /* Align map allocation to cache line. */
+ map->entries = (void *)(((uintptr_t)&map[1] + prefix +
+ CK_MD_CACHELINE - 1) & ~(CK_MD_CACHELINE - 1));
+
+ memset(map->entries, 0, sizeof(void *) * n_entries);
+ memset(map->generation, 0, sizeof map->generation);
+
+ if (hs->mode & CK_HS_MODE_DELETE) {
+ map->probe_bound = (CK_HS_WORD *)&map[1];
+ memset(map->probe_bound, 0, prefix);
+ } else {
+ map->probe_bound = NULL;
+ }
+
+ /* Commit entries purge with respect to map publication. */
+ ck_pr_fence_store();
+ return map;
+}
+
+bool
+ck_hs_reset_size(struct ck_hs *hs, unsigned long capacity)
+{
+ struct ck_hs_map *map, *previous;
+
+ previous = hs->map;
+ map = ck_hs_map_create(hs, capacity);
+ if (map == NULL)
+ return false;
+
+ ck_pr_store_ptr(&hs->map, map);
+ ck_hs_map_destroy(hs->m, previous, true);
+ return true;
+}
+
+bool
+ck_hs_reset(struct ck_hs *hs)
+{
+ struct ck_hs_map *previous;
+
+ previous = hs->map;
+ return ck_hs_reset_size(hs, previous->capacity);
+}
+
+static inline unsigned long
+ck_hs_map_probe_next(struct ck_hs_map *map,
+ unsigned long offset,
+ unsigned long h,
+ unsigned long level,
+ unsigned long probes)
+{
+ unsigned long r, stride;
+
+ r = (h >> map->step) >> level;
+ stride = (r & ~CK_HS_PROBE_L1_MASK) << 1 | (r & CK_HS_PROBE_L1_MASK);
+
+ return (offset + (probes >> CK_HS_PROBE_L1_SHIFT) +
+ (stride | CK_HS_PROBE_L1)) & map->mask;
+}
+
+static inline void
+ck_hs_map_bound_set(struct ck_hs_map *m,
+ unsigned long h,
+ unsigned long n_probes)
+{
+ unsigned long offset = h & m->mask;
+
+ if (n_probes > m->probe_maximum)
+ ck_pr_store_uint(&m->probe_maximum, n_probes);
+
+ if (m->probe_bound != NULL && m->probe_bound[offset] < n_probes) {
+ if (n_probes > CK_HS_WORD_MAX)
+ n_probes = CK_HS_WORD_MAX;
+
+ CK_HS_STORE(&m->probe_bound[offset], n_probes);
+ ck_pr_fence_store();
+ }
+
+ return;
+}
+
+static inline unsigned int
+ck_hs_map_bound_get(struct ck_hs_map *m, unsigned long h)
+{
+ unsigned long offset = h & m->mask;
+ unsigned int r = CK_HS_WORD_MAX;
+
+ if (m->probe_bound != NULL) {
+ r = CK_HS_LOAD(&m->probe_bound[offset]);
+ if (r == CK_HS_WORD_MAX)
+ r = ck_pr_load_uint(&m->probe_maximum);
+ } else {
+ r = ck_pr_load_uint(&m->probe_maximum);
+ }
+
+ return r;
+}
+
+bool
+ck_hs_grow(struct ck_hs *hs,
+ unsigned long capacity)
+{
+ struct ck_hs_map *map, *update;
+ void **bucket, *previous;
+ unsigned long k, i, j, offset, probes;
+
+restart:
+ map = hs->map;
+ if (map->capacity > capacity)
+ return false;
+
+ update = ck_hs_map_create(hs, capacity);
+ if (update == NULL)
+ return false;
+
+ for (k = 0; k < map->capacity; k++) {
+ unsigned long h;
+
+ previous = map->entries[k];
+ if (previous == CK_HS_EMPTY || previous == CK_HS_TOMBSTONE)
+ continue;
+
+#ifdef CK_HS_PP
+ if (hs->mode & CK_HS_MODE_OBJECT)
+ previous = CK_HS_VMA(previous);
+#endif
+
+ h = hs->hf(previous, hs->seed);
+ offset = h & update->mask;
+ i = probes = 0;
+
+ for (;;) {
+ bucket = (void *)((uintptr_t)&update->entries[offset] & ~(CK_MD_CACHELINE - 1));
+
+ for (j = 0; j < CK_HS_PROBE_L1; j++) {
+ void **cursor = bucket + ((j + offset) & (CK_HS_PROBE_L1 - 1));
+
+ if (probes++ == update->probe_limit)
+ break;
+
+ if (CK_CC_LIKELY(*cursor == CK_HS_EMPTY)) {
+ *cursor = map->entries[k];
+ update->n_entries++;
+
+ ck_hs_map_bound_set(update, h, probes);
+ break;
+ }
+ }
+
+ if (j < CK_HS_PROBE_L1)
+ break;
+
+ offset = ck_hs_map_probe_next(update, offset, h, i++, probes);
+ }
+
+ if (probes > update->probe_limit) {
+ /*
+ * We have hit the probe limit, map needs to be even larger.
+ */
+ ck_hs_map_destroy(hs->m, update, false);
+ capacity <<= 1;
+ goto restart;
+ }
+ }
+
+ ck_pr_fence_store();
+ ck_pr_store_ptr(&hs->map, update);
+ ck_hs_map_destroy(hs->m, map, true);
+ return true;
+}
+
+bool
+ck_hs_rebuild(struct ck_hs *hs)
+{
+
+ return ck_hs_grow(hs, hs->map->capacity);
+}
+
+static void **
+ck_hs_map_probe(struct ck_hs *hs,
+ struct ck_hs_map *map,
+ unsigned long *n_probes,
+ void ***priority,
+ unsigned long h,
+ const void *key,
+ void **object,
+ unsigned long probe_limit,
+ enum ck_hs_probe_behavior behavior)
+{
+ void **bucket, **cursor, *k;
+ const void *compare;
+ void **pr = NULL;
+ unsigned long offset, j, i, probes, opl;
+
+#ifdef CK_HS_PP
+ /* If we are storing object pointers, then we may leverage pointer packing. */
+ unsigned long hv = 0;
+
+ if (hs->mode & CK_HS_MODE_OBJECT) {
+ hv = (h >> 25) & CK_HS_KEY_MASK;
+ compare = CK_HS_VMA(key);
+ } else {
+ compare = key;
+ }
+#else
+ compare = key;
+#endif
+
+ offset = h & map->mask;
+ *object = NULL;
+ i = probes = 0;
+
+ opl = probe_limit;
+ if (behavior == CK_HS_PROBE_INSERT)
+ probe_limit = ck_hs_map_bound_get(map, h);
+
+ for (;;) {
+ bucket = (void **)((uintptr_t)&map->entries[offset] & ~(CK_MD_CACHELINE - 1));
+
+ for (j = 0; j < CK_HS_PROBE_L1; j++) {
+ cursor = bucket + ((j + offset) & (CK_HS_PROBE_L1 - 1));
+
+ if (probes++ == probe_limit) {
+ if (probe_limit == opl || pr != NULL) {
+ k = CK_HS_EMPTY;
+ goto leave;
+ }
+
+ /*
+ * If no eligible slot has been found yet, continue probe
+ * sequence with original probe limit.
+ */
+ probe_limit = opl;
+ }
+
+ k = ck_pr_load_ptr(cursor);
+ if (k == CK_HS_EMPTY)
+ goto leave;
+
+ if (k == CK_HS_TOMBSTONE) {
+ if (pr == NULL) {
+ pr = cursor;
+ *n_probes = probes;
+
+ if (behavior == CK_HS_PROBE_TOMBSTONE) {
+ k = CK_HS_EMPTY;
+ goto leave;
+ }
+ }
+
+ continue;
+ }
+
+#ifdef CK_HS_PP
+ if (hs->mode & CK_HS_MODE_OBJECT) {
+ if (((uintptr_t)k >> CK_MD_VMA_BITS) != hv)
+ continue;
+
+ k = CK_HS_VMA(k);
+ }
+#endif
+
+ if (k == compare)
+ goto leave;
+
+ if (hs->compare == NULL)
+ continue;
+
+ if (hs->compare(k, key) == true)
+ goto leave;
+ }
+
+ offset = ck_hs_map_probe_next(map, offset, h, i++, probes);
+ }
+
+leave:
+ if (probes > probe_limit) {
+ cursor = NULL;
+ } else {
+ *object = k;
+ }
+
+ if (pr == NULL)
+ *n_probes = probes;
+
+ *priority = pr;
+ return cursor;
+}
+
+static inline void *
+ck_hs_marshal(unsigned int mode, const void *key, unsigned long h)
+{
+ void *insert;
+
+#ifdef CK_HS_PP
+ if (mode & CK_HS_MODE_OBJECT) {
+ insert = (void *)((uintptr_t)CK_HS_VMA(key) | ((h >> 25) << CK_MD_VMA_BITS));
+ } else {
+ insert = (void *)key;
+ }
+#else
+ (void)mode;
+ (void)h;
+ insert = (void *)key;
+#endif
+
+ return insert;
+}
+
+bool
+ck_hs_gc(struct ck_hs *hs, unsigned long cycles, unsigned long seed)
+{
+ unsigned long size = 0;
+ unsigned long i;
+ struct ck_hs_map *map = hs->map;
+ unsigned int maximum;
+ CK_HS_WORD *bounds = NULL;
+
+ if (map->n_entries == 0) {
+ ck_pr_store_uint(&map->probe_maximum, 0);
+ if (map->probe_bound != NULL)
+ memset(map->probe_bound, 0, sizeof(CK_HS_WORD) * map->capacity);
+
+ return true;
+ }
+
+ if (cycles == 0) {
+ maximum = 0;
+
+ if (map->probe_bound != NULL) {
+ size = sizeof(CK_HS_WORD) * map->capacity;
+ bounds = hs->m->malloc(size);
+ if (bounds == NULL)
+ return false;
+
+ memset(bounds, 0, size);
+ }
+ } else {
+ maximum = map->probe_maximum;
+ }
+
+ for (i = 0; i < map->capacity; i++) {
+ void **first, *object, *entry, **slot;
+ unsigned long n_probes, offset, h;
+
+ entry = map->entries[(i + seed) & map->mask];
+ if (entry == CK_HS_EMPTY || entry == CK_HS_TOMBSTONE)
+ continue;
+
+#ifdef CK_HS_PP
+ if (hs->mode & CK_HS_MODE_OBJECT)
+ entry = CK_HS_VMA(entry);
+#endif
+
+ h = hs->hf(entry, hs->seed);
+ offset = h & map->mask;
+
+ slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, entry, &object,
+ ck_hs_map_bound_get(map, h), CK_HS_PROBE);
+
+ if (first != NULL) {
+ void *insert = ck_hs_marshal(hs->mode, entry, h);
+
+ ck_pr_store_ptr(first, insert);
+ ck_pr_inc_uint(&map->generation[h & CK_HS_G_MASK]);
+ ck_pr_fence_atomic_store();
+ ck_pr_store_ptr(slot, CK_HS_TOMBSTONE);
+ }
+
+ if (cycles == 0) {
+ if (n_probes > maximum)
+ maximum = n_probes;
+
+ if (n_probes > CK_HS_WORD_MAX)
+ n_probes = CK_HS_WORD_MAX;
+
+ if (bounds != NULL && n_probes > bounds[offset])
+ bounds[offset] = n_probes;
+ } else if (--cycles == 0)
+ break;
+ }
+
+ /*
+ * The following only apply to garbage collection involving
+ * a full scan of all entries.
+ */
+ if (maximum != map->probe_maximum)
+ ck_pr_store_uint(&map->probe_maximum, maximum);
+
+ if (bounds != NULL) {
+ for (i = 0; i < map->capacity; i++)
+ CK_HS_STORE(&map->probe_bound[i], bounds[i]);
+
+ hs->m->free(bounds, size, false);
+ }
+
+ return true;
+}
+
+bool
+ck_hs_fas(struct ck_hs *hs,
+ unsigned long h,
+ const void *key,
+ void **previous)
+{
+ void **slot, **first, *object, *insert;
+ unsigned long n_probes;
+ struct ck_hs_map *map = hs->map;
+
+ *previous = NULL;
+ slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object,
+ ck_hs_map_bound_get(map, h), CK_HS_PROBE);
+
+ /* Replacement semantics presume existence. */
+ if (object == NULL)
+ return false;
+
+ insert = ck_hs_marshal(hs->mode, key, h);
+
+ if (first != NULL) {
+ ck_pr_store_ptr(first, insert);
+ ck_pr_inc_uint(&map->generation[h & CK_HS_G_MASK]);
+ ck_pr_fence_atomic_store();
+ ck_pr_store_ptr(slot, CK_HS_TOMBSTONE);
+ } else {
+ ck_pr_store_ptr(slot, insert);
+ }
+
+ *previous = object;
+ return true;
+}
+
+bool
+ck_hs_set(struct ck_hs *hs,
+ unsigned long h,
+ const void *key,
+ void **previous)
+{
+ void **slot, **first, *object, *insert;
+ unsigned long n_probes;
+ struct ck_hs_map *map;
+
+ *previous = NULL;
+
+restart:
+ map = hs->map;
+
+ slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_HS_PROBE_INSERT);
+ if (slot == NULL && first == NULL) {
+ if (ck_hs_grow(hs, map->capacity << 1) == false)
+ return false;
+
+ goto restart;
+ }
+
+ ck_hs_map_bound_set(map, h, n_probes);
+ insert = ck_hs_marshal(hs->mode, key, h);
+
+ if (first != NULL) {
+ /* If an earlier bucket was found, then store entry there. */
+ ck_pr_store_ptr(first, insert);
+
+ /*
+ * If a duplicate key was found, then delete it after
+ * signaling concurrent probes to restart. Optionally,
+ * it is possible to install tombstone after grace
+ * period if we can guarantee earlier position of
+ * duplicate key.
+ */
+ if (object != NULL) {
+ ck_pr_inc_uint(&map->generation[h & CK_HS_G_MASK]);
+ ck_pr_fence_atomic_store();
+ ck_pr_store_ptr(slot, CK_HS_TOMBSTONE);
+ }
+ } else {
+ /*
+ * If we are storing into same slot, then atomic store is sufficient
+ * for replacement.
+ */
+ ck_pr_store_ptr(slot, insert);
+ }
+
+ if (object == NULL) {
+ map->n_entries++;
+ if ((map->n_entries << 1) > map->capacity)
+ ck_hs_grow(hs, map->capacity << 1);
+ }
+
+ *previous = object;
+ return true;
+}
+
+CK_CC_INLINE static bool
+ck_hs_put_internal(struct ck_hs *hs,
+ unsigned long h,
+ const void *key,
+ enum ck_hs_probe_behavior behavior)
+{
+ void **slot, **first, *object, *insert;
+ unsigned long n_probes;
+ struct ck_hs_map *map;
+
+restart:
+ map = hs->map;
+
+ slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object,
+ map->probe_limit, behavior);
+
+ if (slot == NULL && first == NULL) {
+ if (ck_hs_grow(hs, map->capacity << 1) == false)
+ return false;
+
+ goto restart;
+ }
+
+ /* Fail operation if a match was found. */
+ if (object != NULL)
+ return false;
+
+ ck_hs_map_bound_set(map, h, n_probes);
+ insert = ck_hs_marshal(hs->mode, key, h);
+
+ if (first != NULL) {
+ /* Insert key into first bucket in probe sequence. */
+ ck_pr_store_ptr(first, insert);
+ } else {
+ /* An empty slot was found. */
+ ck_pr_store_ptr(slot, insert);
+ }
+
+ map->n_entries++;
+ if ((map->n_entries << 1) > map->capacity)
+ ck_hs_grow(hs, map->capacity << 1);
+
+ return true;
+}
+
+bool
+ck_hs_put(struct ck_hs *hs,
+ unsigned long h,
+ const void *key)
+{
+
+ return ck_hs_put_internal(hs, h, key, CK_HS_PROBE_INSERT);
+}
+
+bool
+ck_hs_put_unique(struct ck_hs *hs,
+ unsigned long h,
+ const void *key)
+{
+
+ return ck_hs_put_internal(hs, h, key, CK_HS_PROBE_TOMBSTONE);
+}
+
+void *
+ck_hs_get(struct ck_hs *hs,
+ unsigned long h,
+ const void *key)
+{
+ void **first, *object;
+ struct ck_hs_map *map;
+ unsigned long n_probes;
+ unsigned int g, g_p, probe;
+ unsigned int *generation;
+
+ do {
+ map = ck_pr_load_ptr(&hs->map);
+ generation = &map->generation[h & CK_HS_G_MASK];
+ g = ck_pr_load_uint(generation);
+ probe = ck_hs_map_bound_get(map, h);
+ ck_pr_fence_load();
+
+ ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, probe, CK_HS_PROBE);
+
+ ck_pr_fence_load();
+ g_p = ck_pr_load_uint(generation);
+ } while (g != g_p);
+
+ return object;
+}
+
+void *
+ck_hs_remove(struct ck_hs *hs,
+ unsigned long h,
+ const void *key)
+{
+ void **slot, **first, *object;
+ struct ck_hs_map *map = hs->map;
+ unsigned long n_probes;
+
+ slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object,
+ ck_hs_map_bound_get(map, h), CK_HS_PROBE);
+ if (object == NULL)
+ return NULL;
+
+ ck_pr_store_ptr(slot, CK_HS_TOMBSTONE);
+ map->n_entries--;
+ map->tombstones++;
+ return object;
+}
+
+bool
+ck_hs_move(struct ck_hs *hs,
+ struct ck_hs *source,
+ ck_hs_hash_cb_t *hf,
+ ck_hs_compare_cb_t *compare,
+ struct ck_malloc *m)
+{
+
+ if (m == NULL || m->malloc == NULL || m->free == NULL || hf == NULL)
+ return false;
+
+ hs->mode = source->mode;
+ hs->seed = source->seed;
+ hs->map = source->map;
+ hs->m = m;
+ hs->hf = hf;
+ hs->compare = compare;
+ return true;
+}
+
+bool
+ck_hs_init(struct ck_hs *hs,
+ unsigned int mode,
+ ck_hs_hash_cb_t *hf,
+ ck_hs_compare_cb_t *compare,
+ struct ck_malloc *m,
+ unsigned long n_entries,
+ unsigned long seed)
+{
+
+ if (m == NULL || m->malloc == NULL || m->free == NULL || hf == NULL)
+ return false;
+
+ hs->m = m;
+ hs->mode = mode;
+ hs->seed = seed;
+ hs->hf = hf;
+ hs->compare = compare;
+
+ hs->map = ck_hs_map_create(hs, n_entries);
+ return hs->map != NULL;
+}
+