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 2015/06/14 00:55:53 UTC
[03/22] trafficserver git commit: TS-3689: Remove libck
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/025a4550/lib/ck/regressions/ck_swlock/validate/validate.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_swlock/validate/validate.c b/lib/ck/regressions/ck_swlock/validate/validate.c
deleted file mode 100644
index 11366ce..0000000
--- a/lib/ck/regressions/ck_swlock/validate/validate.c
+++ /dev/null
@@ -1,455 +0,0 @@
-/*
- * Copyright 2014 Jaidev Sridhar.
- * 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 <errno.h>
-#include <inttypes.h>
-#include <pthread.h>
-#include <math.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <strings.h>
-#include <unistd.h>
-#include <sys/time.h>
-
-#include <ck_pr.h>
-#include <ck_swlock.h>
-
-#include "../../common.h"
-
-#ifndef ITERATE
-#define ITERATE 1000000
-#endif
-
-static struct affinity a;
-static unsigned int locked;
-static int nthr;
-static ck_swlock_t lock = CK_SWLOCK_INITIALIZER;
-static ck_swlock_t copy;
-#ifdef CK_F_PR_RTM
-static void *
-thread_rtm_adaptive(void *arg)
-{
- unsigned int i = ITERATE;
- unsigned int l;
- int tid = ck_pr_load_int(arg);
-
- struct ck_elide_config config = CK_ELIDE_CONFIG_DEFAULT_INITIALIZER;
- struct ck_elide_stat st = CK_ELIDE_STAT_INITIALIZER;
-
- if (aff_iterate(&a)) {
- perror("ERROR: Could not affine thread");
- exit(EXIT_FAILURE);
- }
-
- while (i--) {
- if (tid == 0) {
- CK_ELIDE_LOCK_ADAPTIVE(ck_swlock_write, &st, &config, &lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
-
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 8) {
- ck_error("ERROR [WR:%d]: %u != 2\n", __LINE__, l);
- }
-
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
- }
- CK_ELIDE_UNLOCK_ADAPTIVE(ck_swlock_write, &st, &lock);
- }
-
- CK_ELIDE_LOCK(ck_swlock_read, &lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [RD:%d]: %u != 0\n", __LINE__, l);
- }
- }
- CK_ELIDE_UNLOCK(ck_swlock_read, &lock);
- }
-
- return NULL;
-}
-
-static void *
-thread_rtm_mix(void *arg)
-{
- unsigned int i = ITERATE;
- unsigned int l;
- int tid = ck_pr_load_int(arg);
-
- if (aff_iterate(&a)) {
- perror("ERROR: Could not affine thread");
- exit(EXIT_FAILURE);
- }
-
- while (i--) {
- if (tid == 0) {
- if (i & 1) {
- CK_ELIDE_LOCK(ck_swlock_write, &lock);
- } else {
- ck_swlock_write_lock(&lock);
- }
-
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
-
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 8) {
- ck_error("ERROR [WR:%d]: %u != 2\n", __LINE__, l);
- }
-
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
- }
-
- if (i & 1) {
- CK_ELIDE_UNLOCK(ck_swlock_write, &lock);
- } else {
- ck_swlock_write_unlock(&lock);
- }
- }
- if (i & 1) {
- CK_ELIDE_LOCK(ck_swlock_read, &lock);
- } else {
- ck_swlock_read_lock(&lock);
- }
-
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [RD:%d]: %u != 0\n", __LINE__, l);
- }
- }
-
- if (i & 1) {
- CK_ELIDE_UNLOCK(ck_swlock_read, &lock);
- } else {
- ck_swlock_read_unlock(&lock);
- }
- }
-
- return (NULL);
-}
-
-static void *
-thread_rtm(void *arg)
-{
- unsigned int i = ITERATE;
- unsigned int l;
- int tid = ck_pr_load_int(arg);
-
- if (aff_iterate(&a)) {
- perror("ERROR: Could not affine thread");
- exit(EXIT_FAILURE);
- }
-
- while (i--) {
- if (tid == 0) {
- CK_ELIDE_LOCK(ck_swlock_write, &lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
-
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 8) {
- ck_error("ERROR [WR:%d]: %u != 2\n", __LINE__, l);
- }
-
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
- }
- CK_ELIDE_UNLOCK(ck_swlock_write, &lock);
- }
-
- CK_ELIDE_LOCK(ck_swlock_read, &lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [RD:%d]: %u != 0\n", __LINE__, l);
- }
- }
- CK_ELIDE_UNLOCK(ck_swlock_read, &lock);
- }
-
- return (NULL);
-}
-#endif /* CK_F_PR_RTM */
-
-static void *
-thread_latch(void *arg)
-{
- unsigned int i = ITERATE;
- unsigned int l;
- int tid = ck_pr_load_int(arg);
-
- if (aff_iterate(&a)) {
- perror("ERROR: Could not affine thread");
- exit(EXIT_FAILURE);
- }
-
- while (i--) {
- if (tid == 0) {
- /* Writer */
- ck_swlock_write_latch(&lock);
- {
- memcpy(©, &lock, sizeof(ck_swlock_t));
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
-
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 8) {
- ck_error("ERROR [WR:%d]: %u != 2\n", __LINE__, l);
- }
-
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
- memcpy(&lock, ©, sizeof(ck_swlock_t));
- }
- ck_swlock_write_unlatch(&lock);
- }
-
- ck_swlock_read_lock(&lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [RD:%d]: %u != 0\n", __LINE__, l);
- }
- }
- ck_swlock_read_unlock(&lock);
- }
-
- return (NULL);
-}
-
-static void *
-thread(void *arg)
-{
- unsigned int i = ITERATE;
- unsigned int l;
- int tid = ck_pr_load_int(arg);
-
- if (aff_iterate(&a)) {
- perror("ERROR: Could not affine thread");
- exit(EXIT_FAILURE);
- }
-
- while (i--) {
- if (tid == 0) {
- /* Writer */
- ck_swlock_write_lock(&lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
-
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 8) {
- ck_error("ERROR [WR:%d]: %u != 2\n", __LINE__, l);
- }
-
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
- }
- ck_swlock_write_unlock(&lock);
- }
-
- ck_swlock_read_lock(&lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [RD:%d]: %u != 0\n", __LINE__, l);
- }
- }
- ck_swlock_read_unlock(&lock);
- }
-
- return (NULL);
-}
-
-static void
-swlock_test(pthread_t *threads, void *(*f)(void *), const char *test)
-{
- int i, tid[nthr];
-
- fprintf(stderr, "Creating threads (%s)...", test);
- for (i = 0; i < nthr; i++) {
- ck_pr_store_int(&tid[i], i);
- if (pthread_create(&threads[i], NULL, f, &tid[i])) {
- ck_error("ERROR: Could not create thread %d\n", i);
- }
- }
- fprintf(stderr, ".");
-
- for (i = 0; i < nthr; i++)
- pthread_join(threads[i], NULL);
- fprintf(stderr, "done (passed)\n");
- return;
-}
-
-int
-main(int argc, char *argv[])
-{
- pthread_t *threads;
-
- if (argc != 3) {
- ck_error("Usage: validate <number of threads> <affinity delta>\n");
- }
-
- nthr = atoi(argv[1]);
- if (nthr <= 0) {
- ck_error("ERROR: Number of threads must be greater than 0\n");
- }
-
- threads = malloc(sizeof(pthread_t) * nthr);
- if (threads == NULL) {
- ck_error("ERROR: Could not allocate thread structures\n");
- }
-
- a.delta = atoi(argv[2]);
-
- swlock_test(threads, thread, "regular");
- swlock_test(threads, thread_latch, "latch");
-#ifdef CK_F_PR_RTM
- swlock_test(threads, thread_rtm, "rtm");
- swlock_test(threads, thread_rtm_mix, "rtm-mix");
- swlock_test(threads, thread_rtm_adaptive, "rtm-adaptive");
-#endif
- return 0;
-}
-
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/025a4550/lib/ck/regressions/ck_tflock/benchmark/Makefile
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_tflock/benchmark/Makefile b/lib/ck/regressions/ck_tflock/benchmark/Makefile
deleted file mode 100644
index ed63504..0000000
--- a/lib/ck/regressions/ck_tflock/benchmark/Makefile
+++ /dev/null
@@ -1,17 +0,0 @@
-.PHONY: clean distribution
-
-OBJECTS=latency throughput
-
-all: $(OBJECTS)
-
-latency: latency.c ../../../include/ck_rwlock.h ../../../include/ck_elide.h
- $(CC) $(CFLAGS) -o latency latency.c
-
-throughput: throughput.c ../../../include/ck_rwlock.h ../../../include/ck_elide.h
- $(CC) $(CFLAGS) -o throughput throughput.c
-
-clean:
- rm -rf *.dSYM *.exe *~ *.o $(OBJECTS)
-
-include ../../../build/regressions.build
-CFLAGS+=$(PTHREAD_CFLAGS) -D_GNU_SOURCE
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/025a4550/lib/ck/regressions/ck_tflock/benchmark/latency.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_tflock/benchmark/latency.c b/lib/ck/regressions/ck_tflock/benchmark/latency.c
deleted file mode 100644
index 433a42a..0000000
--- a/lib/ck/regressions/ck_tflock/benchmark/latency.c
+++ /dev/null
@@ -1,73 +0,0 @@
-/*
- * 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_tflock.h>
-#include <inttypes.h>
-#include <stdio.h>
-
-#include "../../common.h"
-
-#define CK_F_PR_RTM
-
-#ifndef STEPS
-#define STEPS 2000000
-#endif
-
-int
-main(void)
-{
- uint64_t s_b, e_b, i;
- ck_tflock_ticket_t tflock = CK_TFLOCK_TICKET_INITIALIZER;
-
- for (i = 0; i < STEPS; i++) {
- ck_tflock_ticket_write_lock(&tflock);
- ck_tflock_ticket_write_unlock(&tflock);
- }
-
- s_b = rdtsc();
- for (i = 0; i < STEPS; i++) {
- ck_tflock_ticket_write_lock(&tflock);
- ck_tflock_ticket_write_unlock(&tflock);
- }
- e_b = rdtsc();
- printf(" WRITE: tflock %15" PRIu64 "\n", (e_b - s_b) / STEPS);
-
- for (i = 0; i < STEPS; i++) {
- ck_tflock_ticket_read_lock(&tflock);
- ck_tflock_ticket_read_unlock(&tflock);
- }
-
- s_b = rdtsc();
- for (i = 0; i < STEPS; i++) {
- ck_tflock_ticket_read_lock(&tflock);
- ck_tflock_ticket_read_unlock(&tflock);
- }
- e_b = rdtsc();
- printf(" READ: tflock %15" PRIu64 "\n", (e_b - s_b) / STEPS);
-
- return 0;
-}
-
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/025a4550/lib/ck/regressions/ck_tflock/benchmark/throughput.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_tflock/benchmark/throughput.c b/lib/ck/regressions/ck_tflock/benchmark/throughput.c
deleted file mode 100644
index 2689842..0000000
--- a/lib/ck/regressions/ck_tflock/benchmark/throughput.c
+++ /dev/null
@@ -1,182 +0,0 @@
-/*
- * 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_tflock.h>
-#include <inttypes.h>
-#include <pthread.h>
-#include <stdio.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <unistd.h>
-
-#include "../../common.h"
-
-#ifndef STEPS
-#define STEPS 1000000
-#endif
-
-static int barrier;
-static int threads;
-static unsigned int flag CK_CC_CACHELINE;
-static struct {
- ck_tflock_ticket_t lock;
-} rw CK_CC_CACHELINE = {
- .lock = CK_TFLOCK_TICKET_INITIALIZER
-};
-
-static struct affinity affinity;
-
-static void *
-thread_lock(void *pun)
-{
- uint64_t s_b, e_b, a, i;
- uint64_t *value = pun;
-
- if (aff_iterate(&affinity) != 0) {
- perror("ERROR: Could not affine thread");
- exit(EXIT_FAILURE);
- }
-
- ck_pr_inc_int(&barrier);
- while (ck_pr_load_int(&barrier) != threads)
- ck_pr_stall();
-
- for (i = 1, a = 0;; i++) {
- s_b = rdtsc();
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- ck_tflock_ticket_read_lock(&rw.lock);
- ck_tflock_ticket_read_unlock(&rw.lock);
- e_b = rdtsc();
-
- a += (e_b - s_b) >> 4;
-
- if (ck_pr_load_uint(&flag) == 1)
- break;
- }
-
- ck_pr_inc_int(&barrier);
- while (ck_pr_load_int(&barrier) != threads * 2)
- ck_pr_stall();
-
- *value = (a / i);
- return NULL;
-}
-
-static void
-tflock_test(pthread_t *p, int d, uint64_t *latency, void *(*f)(void *), const char *label)
-{
- int t;
-
- ck_pr_store_int(&barrier, 0);
- ck_pr_store_uint(&flag, 0);
-
- affinity.delta = d;
- affinity.request = 0;
-
- fprintf(stderr, "Creating threads (%s)...", label);
- for (t = 0; t < threads; t++) {
- if (pthread_create(&p[t], NULL, f, latency + t) != 0) {
- ck_error("ERROR: Could not create thread %d\n", t);
- }
- }
- fprintf(stderr, "done\n");
-
- common_sleep(10);
- ck_pr_store_uint(&flag, 1);
-
- fprintf(stderr, "Waiting for threads to finish acquisition regression...");
- for (t = 0; t < threads; t++)
- pthread_join(p[t], NULL);
- fprintf(stderr, "done\n\n");
-
- for (t = 1; t <= threads; t++)
- printf("%10u %20" PRIu64 "\n", t, latency[t - 1]);
-
- fprintf(stderr, "\n");
- return;
-}
-
-
-int
-main(int argc, char *argv[])
-{
- int d;
- pthread_t *p;
- uint64_t *latency;
-
- if (argc != 3) {
- ck_error("Usage: throughput <delta> <threads>\n");
- }
-
- threads = atoi(argv[2]);
- if (threads <= 0) {
- ck_error("ERROR: Threads must be a value > 0.\n");
- }
-
- p = malloc(sizeof(pthread_t) * threads);
- if (p == NULL) {
- ck_error("ERROR: Failed to initialize thread.\n");
- }
-
- latency = malloc(sizeof(uint64_t) * threads);
- if (latency == NULL) {
- ck_error("ERROR: Failed to create latency buffer.\n");
- }
-
- d = atoi(argv[1]);
- tflock_test(p, d, latency, thread_lock, "tflock");
- return 0;
-}
-
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/025a4550/lib/ck/regressions/ck_tflock/validate/Makefile
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_tflock/validate/Makefile b/lib/ck/regressions/ck_tflock/validate/Makefile
deleted file mode 100644
index 6ae7c73..0000000
--- a/lib/ck/regressions/ck_tflock/validate/Makefile
+++ /dev/null
@@ -1,17 +0,0 @@
-.PHONY: check clean distribution
-
-OBJECTS=validate
-
-all: $(OBJECTS)
-
-validate: validate.c ../../../include/ck_tflock.h ../../../include/ck_elide.h
- $(CC) $(CFLAGS) -o validate validate.c
-
-check: all
- ./validate $(CORES) 1
-
-clean:
- rm -rf *.dSYM *.exe *~ *.o $(OBJECTS)
-
-include ../../../build/regressions.build
-CFLAGS+=$(PTHREAD_CFLAGS) -D_GNU_SOURCE
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/025a4550/lib/ck/regressions/ck_tflock/validate/validate.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_tflock/validate/validate.c b/lib/ck/regressions/ck_tflock/validate/validate.c
deleted file mode 100644
index 1b49e3b..0000000
--- a/lib/ck/regressions/ck_tflock/validate/validate.c
+++ /dev/null
@@ -1,158 +0,0 @@
-/*
- * 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 <errno.h>
-#include <inttypes.h>
-#include <pthread.h>
-#include <math.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <strings.h>
-#include <unistd.h>
-#include <sys/time.h>
-
-#include <ck_pr.h>
-#include <ck_tflock.h>
-
-#include "../../common.h"
-
-#ifndef ITERATE
-#define ITERATE 1000000
-#endif
-
-static struct affinity a;
-static unsigned int locked;
-static int nthr;
-static ck_tflock_ticket_t lock = CK_TFLOCK_TICKET_INITIALIZER;
-
-static void *
-thread(void *null CK_CC_UNUSED)
-{
- unsigned int i = ITERATE;
- unsigned int l;
-
- if (aff_iterate(&a)) {
- perror("ERROR: Could not affine thread");
- exit(EXIT_FAILURE);
- }
-
- while (i--) {
- ck_tflock_ticket_write_lock(&lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
-
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
- ck_pr_inc_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 8) {
- ck_error("ERROR [WR:%d]: %u != 2\n", __LINE__, l);
- }
-
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
- ck_pr_dec_uint(&locked);
-
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [WR:%d]: %u != 0\n", __LINE__, l);
- }
- }
- ck_tflock_ticket_write_unlock(&lock);
-
- ck_tflock_ticket_read_lock(&lock);
- {
- l = ck_pr_load_uint(&locked);
- if (l != 0) {
- ck_error("ERROR [RD:%d]: %u != 0\n", __LINE__, l);
- }
- }
- ck_tflock_ticket_read_unlock(&lock);
- }
-
- return (NULL);
-}
-
-static void
-tflock_ticket_test(pthread_t *threads, void *(*f)(void *), const char *test)
-{
- int i;
-
- fprintf(stderr, "Creating threads (%s)...", test);
- for (i = 0; i < nthr; i++) {
- if (pthread_create(&threads[i], NULL, f, NULL)) {
- ck_error("ERROR: Could not create thread %d\n", i);
- }
- }
- fprintf(stderr, ".");
-
- for (i = 0; i < nthr; i++)
- pthread_join(threads[i], NULL);
- fprintf(stderr, "done (passed)\n");
- return;
-}
-
-int
-main(int argc, char *argv[])
-{
- pthread_t *threads;
-
- if (argc != 3) {
- ck_error("Usage: validate <number of threads> <affinity delta>\n");
- }
-
- nthr = atoi(argv[1]);
- if (nthr <= 0) {
- ck_error("ERROR: Number of threads must be greater than 0\n");
- }
-
- threads = malloc(sizeof(pthread_t) * nthr);
- if (threads == NULL) {
- ck_error("ERROR: Could not allocate thread structures\n");
- }
-
- a.delta = atoi(argv[2]);
-
- tflock_ticket_test(threads, thread, "regular");
- ck_tflock_ticket_init(&lock);
- return 0;
-}
-
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/025a4550/lib/ck/regressions/common.h
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/common.h b/lib/ck/regressions/common.h
deleted file mode 100644
index 4322a07..0000000
--- a/lib/ck/regressions/common.h
+++ /dev/null
@@ -1,456 +0,0 @@
-/*
- * 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/025a4550/lib/ck/src/Makefile.in
----------------------------------------------------------------------
diff --git a/lib/ck/src/Makefile.in b/lib/ck/src/Makefile.in
deleted file mode 100644
index 367b25e..0000000
--- a/lib/ck/src/Makefile.in
+++ /dev/null
@@ -1,65 +0,0 @@
-.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_rhs.o: $(INCLUDE_DIR)/ck_rhs.h $(SDIR)/ck_rhs.c
- $(CC) $(CFLAGS) -c -o $(TARGET_DIR)/ck_rhs.o $(SDIR)/ck_rhs.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/025a4550/lib/ck/src/ck_array.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_array.c b/lib/ck/src/ck_array.c
deleted file mode 100644
index f7bb87a..0000000
--- a/lib/ck/src/ck_array.c
+++ /dev/null
@@ -1,240 +0,0 @@
-/*
- * 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/025a4550/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
deleted file mode 100644
index a21ef3e..0000000
--- a/lib/ck/src/ck_barrier_centralized.c
+++ /dev/null
@@ -1,59 +0,0 @@
-/*
- * 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/025a4550/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
deleted file mode 100644
index 41291bb..0000000
--- a/lib/ck/src/ck_barrier_combining.c
+++ /dev/null
@@ -1,207 +0,0 @@
-/*
- * 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/025a4550/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
deleted file mode 100644
index dd08923..0000000
--- a/lib/ck/src/ck_barrier_dissemination.c
+++ /dev/null
@@ -1,123 +0,0 @@
-/*
- * 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/025a4550/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
deleted file mode 100644
index 4dc8502..0000000
--- a/lib/ck/src/ck_barrier_mcs.c
+++ /dev/null
@@ -1,140 +0,0 @@
-/*
- * 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/025a4550/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
deleted file mode 100644
index 0f76c6f..0000000
--- a/lib/ck/src/ck_barrier_tournament.c
+++ /dev/null
@@ -1,183 +0,0 @@
-/*
- * 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/025a4550/lib/ck/src/ck_epoch.c
----------------------------------------------------------------------
diff --git a/lib/ck/src/ck_epoch.c b/lib/ck/src/ck_epoch.c
deleted file mode 100644
index 01320ee..0000000
--- a/lib/ck/src/ck_epoch.c
+++ /dev/null
@@ -1,431 +0,0 @@
-/*
- * 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 *head, *next, *cursor;
- unsigned int i = 0;
-
- head = CK_STACK_FIRST(&record->pending[epoch]);
- ck_stack_init(&record->pending[epoch]);
-
- for (cursor = head; cursor != NULL; cursor = next) {
- struct ck_epoch_entry *entry = ck_epoch_entry_container(cursor);
-
- next = CK_STACK_NEXT(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;
- 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;
-}