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:21 UTC
[08/20] TS-2950: Initial commit of libck.
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_epoch/validate/Makefile
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_epoch/validate/Makefile b/lib/ck/regressions/ck_epoch/validate/Makefile
new file mode 100644
index 0000000..73f8e5d
--- /dev/null
+++ b/lib/ck/regressions/ck_epoch/validate/Makefile
@@ -0,0 +1,26 @@
+.PHONY: check clean distribution
+
+OBJECTS=ck_stack ck_epoch_synchronize ck_epoch_poll
+HALF=`expr $(CORES) / 2`
+
+all: $(OBJECTS)
+
+check: all
+ ./ck_stack $(CORES) 1
+ ./ck_epoch_synchronize $(HALF) $(HALF) 1
+ ./ck_epoch_poll $(CORES) 1 1
+
+ck_epoch_synchronize: ck_epoch_synchronize.c ../../../include/ck_stack.h ../../../include/ck_epoch.h ../../../src/ck_epoch.c
+ $(CC) $(CFLAGS) -o ck_epoch_synchronize ck_epoch_synchronize.c ../../../src/ck_epoch.c
+
+ck_epoch_poll: ck_epoch_poll.c ../../../include/ck_stack.h ../../../include/ck_epoch.h ../../../src/ck_epoch.c
+ $(CC) $(CFLAGS) -o ck_epoch_poll ck_epoch_poll.c ../../../src/ck_epoch.c
+
+ck_stack: ck_stack.c ../../../include/ck_stack.h ../../../include/ck_epoch.h ../../../src/ck_epoch.c
+ $(CC) $(CFLAGS) -o ck_stack ck_stack.c ../../../src/ck_epoch.c
+
+clean:
+ rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe
+
+include ../../../build/regressions.build
+CFLAGS+=$(PTHREAD_CFLAGS) -D_GNU_SOURCE
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_epoch/validate/ck_epoch_poll.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_epoch/validate/ck_epoch_poll.c b/lib/ck/regressions/ck_epoch/validate/ck_epoch_poll.c
new file mode 100644
index 0000000..86cdbb4
--- /dev/null
+++ b/lib/ck/regressions/ck_epoch/validate/ck_epoch_poll.c
@@ -0,0 +1,245 @@
+/*
+ * 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.
+ */
+
+#include <errno.h>
+#include <inttypes.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <strings.h>
+#include <unistd.h>
+#include <sys/time.h>
+
+#include <ck_backoff.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <string.h>
+#include <ck_epoch.h>
+#include <ck_stack.h>
+
+#include "../../common.h"
+
+static unsigned int n_rd;
+static unsigned int n_wr;
+static unsigned int n_threads;
+static unsigned int barrier;
+static unsigned int e_barrier;
+static unsigned int readers;
+static unsigned int writers;
+
+#ifndef PAIRS_S
+#define PAIRS_S 100000
+#endif
+
+#ifndef ITERATE_S
+#define ITERATE_S 20
+#endif
+
+struct node {
+ unsigned int value;
+ ck_stack_entry_t stack_entry;
+ ck_epoch_entry_t epoch_entry;
+};
+static ck_stack_t stack = CK_STACK_INITIALIZER;
+static ck_epoch_t stack_epoch;
+CK_STACK_CONTAINER(struct node, stack_entry, stack_container)
+CK_EPOCH_CONTAINER(struct node, epoch_entry, epoch_container)
+static struct affinity a;
+static const char animate[] = "-/|\\";
+
+static void
+destructor(ck_epoch_entry_t *p)
+{
+ struct node *e = epoch_container(p);
+
+ free(e);
+ return;
+}
+
+static void *
+read_thread(void *unused CK_CC_UNUSED)
+{
+ unsigned int j;
+ ck_epoch_record_t record CK_CC_CACHELINE;
+ ck_stack_entry_t *cursor;
+
+ /*
+ * This is redundant post-incremented in order to silence some
+ * irrelevant GCC warnings. It is volatile in order to prevent
+ * elimination.
+ */
+ volatile ck_stack_entry_t *n;
+
+ ck_epoch_register(&stack_epoch, &record);
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: failed to affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < n_threads);
+
+ while (CK_STACK_ISEMPTY(&stack) == true) {
+ if (ck_pr_load_uint(&readers) != 0)
+ break;
+
+ ck_pr_stall();
+ }
+
+ j = 0;
+ for (;;) {
+ ck_epoch_begin(&stack_epoch, &record);
+ CK_STACK_FOREACH(&stack, cursor) {
+ if (cursor == NULL)
+ continue;
+
+ n = CK_STACK_NEXT(cursor);
+
+ /* Force n use. */
+ j += ((uintptr_t)(void *)n & 0) + 1;
+ }
+ ck_epoch_end(&stack_epoch, &record);
+
+ if (j != 0 && ck_pr_load_uint(&readers) == 0)
+ ck_pr_store_uint(&readers, 1);
+
+ if (CK_STACK_ISEMPTY(&stack) == true &&
+ ck_pr_load_uint(&e_barrier) != 0)
+ break;
+ }
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < n_threads);
+
+ fprintf(stderr, "[R] Observed entries: %u\n", j);
+ return (NULL);
+}
+
+static void *
+write_thread(void *unused CK_CC_UNUSED)
+{
+ struct node **entry, *e;
+ unsigned int i, j, tid;
+ ck_epoch_record_t record;
+ ck_stack_entry_t *s;
+
+ ck_epoch_register(&stack_epoch, &record);
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: failed to affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ tid = ck_pr_faa_uint(&writers, 1);
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < n_threads);
+
+ entry = malloc(sizeof(struct node *) * PAIRS_S);
+ if (entry == NULL) {
+ ck_error("Failed allocation.\n");
+ }
+
+ for (j = 0; j < ITERATE_S; j++) {
+ for (i = 0; i < PAIRS_S; i++) {
+ entry[i] = malloc(sizeof(struct node));
+ if (entry == NULL) {
+ ck_error("Failed individual allocation\n");
+ }
+ }
+
+ for (i = 0; i < PAIRS_S; i++) {
+ ck_stack_push_upmc(&stack, &entry[i]->stack_entry);
+ }
+
+ while (ck_pr_load_uint(&readers) == 0)
+ ck_pr_stall();
+
+ if (tid == 0) {
+ fprintf(stderr, "\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b[W] %2.2f: %c",
+ (double)j / ITERATE_S, animate[i % strlen(animate)]);
+ }
+
+ for (i = 0; i < PAIRS_S; i++) {
+ ck_epoch_begin(&stack_epoch, &record);
+ s = ck_stack_pop_upmc(&stack);
+ e = stack_container(s);
+ ck_epoch_end(&stack_epoch, &record);
+
+ ck_epoch_call(&stack_epoch, &record, &e->epoch_entry, destructor);
+ ck_epoch_poll(&stack_epoch, &record);
+ }
+ }
+
+ ck_epoch_barrier(&stack_epoch, &record);
+
+ if (tid == 0) {
+ fprintf(stderr, "\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b[W] Peak: %u (%2.2f%%)\n Reclamations: %lu\n\n",
+ record.n_peak,
+ (double)record.n_peak / ((double)PAIRS_S * ITERATE_S) * 100,
+ record.n_dispatch);
+ }
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < n_threads);
+ return (NULL);
+}
+
+int
+main(int argc, char *argv[])
+{
+ unsigned int i;
+ pthread_t *threads;
+
+ if (argc != 4) {
+ ck_error("Usage: stack <#readers> <#writers> <affinity delta>\n");
+ }
+
+ n_rd = atoi(argv[1]);
+ n_wr = atoi(argv[2]);
+ n_threads = n_wr + n_rd;
+
+ a.delta = atoi(argv[3]);
+ a.request = 0;
+
+ threads = malloc(sizeof(pthread_t) * n_threads);
+ ck_epoch_init(&stack_epoch);
+
+ for (i = 0; i < n_rd; i++)
+ pthread_create(threads + i, NULL, read_thread, NULL);
+
+ do {
+ pthread_create(threads + i, NULL, write_thread, NULL);
+ } while (++i < n_wr + n_rd);
+
+ for (i = 0; i < n_threads; i++)
+ pthread_join(threads[i], NULL);
+
+ return (0);
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c b/lib/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c
new file mode 100644
index 0000000..3ce2de8
--- /dev/null
+++ b/lib/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c
@@ -0,0 +1,258 @@
+/*
+ * 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.
+ */
+
+#include <errno.h>
+#include <inttypes.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <strings.h>
+#include <unistd.h>
+#include <sys/time.h>
+
+#include <ck_backoff.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <string.h>
+#include <ck_epoch.h>
+#include <ck_stack.h>
+
+#include "../../common.h"
+
+static unsigned int n_rd;
+static unsigned int n_wr;
+static unsigned int n_threads;
+static unsigned int barrier;
+static unsigned int e_barrier;
+static unsigned int readers;
+static unsigned int writers;
+
+#ifndef PAIRS_S
+#define PAIRS_S 10000
+#endif
+
+#ifndef ITERATE_S
+#define ITERATE_S 20
+#endif
+
+struct node {
+ unsigned int value;
+ ck_stack_entry_t stack_entry;
+ ck_epoch_entry_t epoch_entry;
+};
+static ck_stack_t stack = CK_STACK_INITIALIZER;
+static ck_epoch_t stack_epoch;
+CK_STACK_CONTAINER(struct node, stack_entry, stack_container)
+CK_EPOCH_CONTAINER(struct node, epoch_entry, epoch_container)
+static struct affinity a;
+static const char animate[] = "-/|\\";
+
+static void
+destructor(ck_epoch_entry_t *p)
+{
+ struct node *e = epoch_container(p);
+
+ free(e);
+ return;
+}
+
+static void *
+read_thread(void *unused CK_CC_UNUSED)
+{
+ unsigned int j;
+ ck_epoch_record_t record CK_CC_CACHELINE;
+ ck_stack_entry_t *cursor;
+
+ /*
+ * This is redundant post-incremented in order to silence some
+ * irrelevant GCC warnings. It is volatile in order to prevent
+ * elimination.
+ */
+ volatile ck_stack_entry_t *n;
+
+ ck_epoch_register(&stack_epoch, &record);
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: failed to affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < n_threads);
+
+ while (CK_STACK_ISEMPTY(&stack) == true) {
+ if (ck_pr_load_uint(&readers) != 0)
+ break;
+
+ ck_pr_stall();
+ }
+
+ j = 0;
+ for (;;) {
+ ck_epoch_begin(&stack_epoch, &record);
+ CK_STACK_FOREACH(&stack, cursor) {
+ if (cursor == NULL)
+ continue;
+
+ n = CK_STACK_NEXT(cursor);
+
+ /* Force n use. */
+ j += ((uintptr_t)(void *)n & 0) + 1;
+ }
+ ck_epoch_end(&stack_epoch, &record);
+
+ if (j != 0 && ck_pr_load_uint(&readers) == 0)
+ ck_pr_store_uint(&readers, 1);
+
+ if (CK_STACK_ISEMPTY(&stack) == true &&
+ ck_pr_load_uint(&e_barrier) != 0)
+ break;
+ }
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < n_threads);
+
+ fprintf(stderr, "[R] Observed entries: %u\n", j);
+ return (NULL);
+}
+
+static void *
+write_thread(void *unused CK_CC_UNUSED)
+{
+ struct node **entry, *e;
+ unsigned int i, j, tid;
+ ck_epoch_record_t record;
+ ck_stack_entry_t *s;
+
+ ck_epoch_register(&stack_epoch, &record);
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: failed to affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ tid = ck_pr_faa_uint(&writers, 1);
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < n_threads);
+
+ entry = malloc(sizeof(struct node *) * PAIRS_S);
+ if (entry == NULL) {
+ ck_error("Failed allocation.\n");
+ }
+
+ for (j = 0; j < ITERATE_S; j++) {
+ for (i = 0; i < PAIRS_S; i++) {
+ entry[i] = malloc(sizeof(struct node));
+ if (entry == NULL) {
+ ck_error("Failed individual allocation\n");
+ }
+ }
+
+ for (i = 0; i < PAIRS_S; i++) {
+ ck_stack_push_upmc(&stack, &entry[i]->stack_entry);
+ }
+
+ while (ck_pr_load_uint(&readers) == 0)
+ ck_pr_stall();
+
+ if (tid == 0) {
+ fprintf(stderr, "\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b[W] %2.2f: %c",
+ (double)j / ITERATE_S, animate[i % strlen(animate)]);
+ }
+
+ for (i = 0; i < PAIRS_S; i++) {
+ ck_epoch_begin(&stack_epoch, &record);
+ s = ck_stack_pop_upmc(&stack);
+ e = stack_container(s);
+ ck_epoch_end(&stack_epoch, &record);
+
+ if (i & 1) {
+ ck_epoch_synchronize(&stack_epoch, &record);
+ ck_epoch_reclaim(&record);
+ } else {
+ ck_epoch_barrier(&stack_epoch, &record);
+ }
+
+ if (i & 1) {
+ ck_epoch_call(&stack_epoch, &record, &e->epoch_entry, destructor);
+ } else {
+ if (tid == 0 && i % 8192)
+ fprintf(stderr, "\b%c", animate[i % strlen(animate)]);
+
+ destructor(&e->epoch_entry);
+ }
+ }
+ }
+
+ ck_epoch_synchronize(&stack_epoch, &record);
+
+ if (tid == 0) {
+ fprintf(stderr, "\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b[W] Peak: %u (%2.2f%%)\n Reclamations: %lu\n\n",
+ record.n_peak,
+ (double)record.n_peak / ((double)PAIRS_S * ITERATE_S) * 100,
+ record.n_dispatch);
+ }
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < n_threads);
+ return (NULL);
+}
+
+int
+main(int argc, char *argv[])
+{
+ unsigned int i;
+ pthread_t *threads;
+
+ if (argc != 4) {
+ ck_error("Usage: stack <#readers> <#writers> <affinity delta>\n");
+ }
+
+ n_rd = atoi(argv[1]);
+ n_wr = atoi(argv[2]);
+ n_threads = n_wr + n_rd;
+
+ a.delta = atoi(argv[3]);
+ a.request = 0;
+
+ threads = malloc(sizeof(pthread_t) * n_threads);
+ ck_epoch_init(&stack_epoch);
+
+ for (i = 0; i < n_rd; i++)
+ pthread_create(threads + i, NULL, read_thread, NULL);
+
+ do {
+ pthread_create(threads + i, NULL, write_thread, NULL);
+ } while (++i < n_wr + n_rd);
+
+ for (i = 0; i < n_threads; i++)
+ pthread_join(threads[i], NULL);
+
+ return (0);
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_epoch/validate/ck_stack.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_epoch/validate/ck_stack.c b/lib/ck/regressions/ck_epoch/validate/ck_stack.c
new file mode 100644
index 0000000..00356f8
--- /dev/null
+++ b/lib/ck/regressions/ck_epoch/validate/ck_stack.c
@@ -0,0 +1,164 @@
+/*
+ * 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.
+ */
+
+#include <errno.h>
+#include <inttypes.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <strings.h>
+#include <unistd.h>
+#include <sys/time.h>
+
+#include <ck_backoff.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <ck_epoch.h>
+#include <ck_stack.h>
+
+#include "../../common.h"
+
+static unsigned int n_threads;
+static unsigned int barrier;
+static unsigned int e_barrier;
+
+#ifndef PAIRS
+#define PAIRS 5000000
+#endif
+
+struct node {
+ unsigned int value;
+ ck_epoch_entry_t epoch_entry;
+ ck_stack_entry_t stack_entry;
+};
+static ck_stack_t stack = {NULL, NULL};
+static ck_epoch_t stack_epoch;
+CK_STACK_CONTAINER(struct node, stack_entry, stack_container)
+CK_EPOCH_CONTAINER(struct node, epoch_entry, epoch_container)
+static struct affinity a;
+
+static void
+destructor(ck_epoch_entry_t *p)
+{
+ struct node *e = epoch_container(p);
+
+ free(e);
+ return;
+}
+
+static void *
+thread(void *unused CK_CC_UNUSED)
+{
+ struct node **entry, *e;
+ ck_epoch_record_t record;
+ ck_stack_entry_t *s;
+ unsigned long smr = 0;
+ unsigned int i;
+
+ ck_epoch_register(&stack_epoch, &record);
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: failed to affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ entry = malloc(sizeof(struct node *) * PAIRS);
+ if (entry == NULL) {
+ ck_error("Failed allocation.\n");
+ }
+
+ for (i = 0; i < PAIRS; i++) {
+ entry[i] = malloc(sizeof(struct node));
+ if (entry == NULL) {
+ ck_error("Failed individual allocation\n");
+ }
+ }
+
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < n_threads);
+
+ for (i = 0; i < PAIRS; i++) {
+ ck_epoch_begin(&stack_epoch, &record);
+ ck_stack_push_upmc(&stack, &entry[i]->stack_entry);
+ s = ck_stack_pop_upmc(&stack);
+ ck_epoch_end(&stack_epoch, &record);
+
+ e = stack_container(s);
+ ck_epoch_call(&stack_epoch, &record, &e->epoch_entry, destructor);
+ smr += ck_epoch_poll(&stack_epoch, &record) == false;
+ }
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < n_threads);
+
+ fprintf(stderr, "Deferrals: %lu (%2.2f)\n", smr, (double)smr / PAIRS);
+ fprintf(stderr, "Peak: %u (%2.2f%%), %u pending\nReclamations: %lu\n\n",
+ record.n_peak,
+ (double)record.n_peak / PAIRS * 100,
+ record.n_pending,
+ record.n_dispatch);
+
+ ck_epoch_barrier(&stack_epoch, &record);
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < (n_threads << 1));
+
+ if (record.n_pending != 0) {
+ ck_error("ERROR: %u pending, expecting none.\n",
+ record.n_pending);
+ }
+
+ return (NULL);
+}
+
+int
+main(int argc, char *argv[])
+{
+ unsigned int i;
+ pthread_t *threads;
+
+ if (argc != 3) {
+ ck_error("Usage: stack <threads> <affinity delta>\n");
+ }
+
+ n_threads = atoi(argv[1]);
+ a.delta = atoi(argv[2]);
+ a.request = 0;
+
+ threads = malloc(sizeof(pthread_t) * n_threads);
+
+ ck_epoch_init(&stack_epoch);
+
+ for (i = 0; i < n_threads; i++)
+ pthread_create(threads + i, NULL, thread, NULL);
+
+ for (i = 0; i < n_threads; i++)
+ pthread_join(threads[i], NULL);
+
+ return (0);
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_fifo/benchmark/Makefile
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_fifo/benchmark/Makefile b/lib/ck/regressions/ck_fifo/benchmark/Makefile
new file mode 100644
index 0000000..6e2df2a
--- /dev/null
+++ b/lib/ck/regressions/ck_fifo/benchmark/Makefile
@@ -0,0 +1,14 @@
+.PHONY: clean distribution
+
+OBJECTS=latency
+
+all: $(OBJECTS)
+
+latency: latency.c
+ $(CC) $(CFLAGS) -o latency latency.c
+
+clean:
+ rm -rf *~ *.o *.dSYM *.exe $(OBJECTS)
+
+include ../../../build/regressions.build
+CFLAGS+=$(PTHREAD_CFLAGS) -D_GNU_SOURCE
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_fifo/benchmark/latency.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_fifo/benchmark/latency.c b/lib/ck/regressions/ck_fifo/benchmark/latency.c
new file mode 100644
index 0000000..3c78b6f
--- /dev/null
+++ b/lib/ck/regressions/ck_fifo/benchmark/latency.c
@@ -0,0 +1,157 @@
+/*
+ * 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_fifo.h>
+#include <ck_spinlock.h>
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+
+#include "../../common.h"
+
+#ifndef ENTRIES
+#define ENTRIES 4096
+#endif
+
+#ifndef STEPS
+#define STEPS 40000
+#endif
+
+int
+main(void)
+{
+ ck_spinlock_fas_t mutex = CK_SPINLOCK_FAS_INITIALIZER;
+ void *r;
+ uint64_t s, e, a;
+ unsigned int i;
+ unsigned int j;
+
+#if defined(CK_F_FIFO_SPSC)
+ ck_fifo_spsc_t spsc_fifo;
+ ck_fifo_spsc_entry_t spsc_entry[ENTRIES];
+ ck_fifo_spsc_entry_t spsc_stub;
+#endif
+
+#if defined(CK_F_FIFO_MPMC)
+ ck_fifo_mpmc_t mpmc_fifo;
+ ck_fifo_mpmc_entry_t mpmc_entry[ENTRIES];
+ ck_fifo_mpmc_entry_t mpmc_stub;
+ ck_fifo_mpmc_entry_t *garbage;
+#endif
+
+#ifdef CK_F_FIFO_SPSC
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_fifo_spsc_init(&spsc_fifo, &spsc_stub);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++) {
+ ck_spinlock_fas_lock(&mutex);
+ ck_fifo_spsc_enqueue(&spsc_fifo, spsc_entry + j, NULL);
+ ck_spinlock_fas_unlock(&mutex);
+ }
+ e = rdtsc();
+
+ a += e - s;
+ }
+ printf(" spinlock_enqueue: %16" PRIu64 "\n", a / STEPS / (sizeof(spsc_entry) / sizeof(*spsc_entry)));
+
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_fifo_spsc_init(&spsc_fifo, &spsc_stub);
+ for (j = 0; j < ENTRIES; j++)
+ ck_fifo_spsc_enqueue(&spsc_fifo, spsc_entry + j, NULL);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++) {
+ ck_spinlock_fas_lock(&mutex);
+ ck_fifo_spsc_dequeue(&spsc_fifo, &r);
+ ck_spinlock_fas_unlock(&mutex);
+ }
+ e = rdtsc();
+ a += e - s;
+ }
+ printf(" spinlock_dequeue: %16" PRIu64 "\n", a / STEPS / (sizeof(spsc_entry) / sizeof(*spsc_entry)));
+
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_fifo_spsc_init(&spsc_fifo, &spsc_stub);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++)
+ ck_fifo_spsc_enqueue(&spsc_fifo, spsc_entry + j, NULL);
+ e = rdtsc();
+
+ a += e - s;
+ }
+ printf("ck_fifo_spsc_enqueue: %16" PRIu64 "\n", a / STEPS / (sizeof(spsc_entry) / sizeof(*spsc_entry)));
+
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_fifo_spsc_init(&spsc_fifo, &spsc_stub);
+ for (j = 0; j < ENTRIES; j++)
+ ck_fifo_spsc_enqueue(&spsc_fifo, spsc_entry + j, NULL);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++)
+ ck_fifo_spsc_dequeue(&spsc_fifo, &r);
+ e = rdtsc();
+ a += e - s;
+ }
+ printf("ck_fifo_spsc_dequeue: %16" PRIu64 "\n", a / STEPS / (sizeof(spsc_entry) / sizeof(*spsc_entry)));
+#endif
+
+#ifdef CK_F_FIFO_MPMC
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_fifo_mpmc_init(&mpmc_fifo, &mpmc_stub);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++)
+ ck_fifo_mpmc_enqueue(&mpmc_fifo, mpmc_entry + j, NULL);
+ e = rdtsc();
+
+ a += e - s;
+ }
+ printf("ck_fifo_mpmc_enqueue: %16" PRIu64 "\n", a / STEPS / (sizeof(mpmc_entry) / sizeof(*mpmc_entry)));
+
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_fifo_mpmc_init(&mpmc_fifo, &mpmc_stub);
+ for (j = 0; j < ENTRIES; j++)
+ ck_fifo_mpmc_enqueue(&mpmc_fifo, mpmc_entry + j, NULL);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++)
+ ck_fifo_mpmc_dequeue(&mpmc_fifo, &r, &garbage);
+ e = rdtsc();
+ a += e - s;
+ }
+ printf("ck_fifo_mpmc_dequeue: %16" PRIu64 "\n", a / STEPS / (sizeof(mpmc_entry) / sizeof(*mpmc_entry)));
+#endif
+
+ return 0;
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_fifo/validate/Makefile
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_fifo/validate/Makefile b/lib/ck/regressions/ck_fifo/validate/Makefile
new file mode 100644
index 0000000..6bfc696
--- /dev/null
+++ b/lib/ck/regressions/ck_fifo/validate/Makefile
@@ -0,0 +1,29 @@
+.PHONY: check clean distribution
+
+OBJECTS=ck_fifo_spsc ck_fifo_mpmc ck_fifo_spsc_iterator ck_fifo_mpmc_iterator
+
+all: $(OBJECTS)
+
+check: all
+ ./ck_fifo_spsc $(CORES) 1 64000
+ ./ck_fifo_mpmc $(CORES) 1 16000
+ ./ck_fifo_spsc_iterator
+ ./ck_fifo_mpmc_iterator
+
+ck_fifo_spsc: ck_fifo_spsc.c ../../../include/ck_fifo.h
+ $(CC) $(CFLAGS) -o ck_fifo_spsc ck_fifo_spsc.c
+
+ck_fifo_mpmc: ck_fifo_mpmc.c ../../../include/ck_fifo.h
+ $(CC) $(CFLAGS) -o ck_fifo_mpmc ck_fifo_mpmc.c
+
+ck_fifo_spsc_iterator: ck_fifo_spsc_iterator.c ../../../include/ck_fifo.h
+ $(CC) $(CFLAGS) -o ck_fifo_spsc_iterator ck_fifo_spsc_iterator.c
+
+ck_fifo_mpmc_iterator: ck_fifo_mpmc_iterator.c ../../../include/ck_fifo.h
+ $(CC) $(CFLAGS) -o ck_fifo_mpmc_iterator ck_fifo_mpmc_iterator.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/f098175e/lib/ck/regressions/ck_fifo/validate/ck_fifo_mpmc.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_fifo/validate/ck_fifo_mpmc.c b/lib/ck/regressions/ck_fifo/validate/ck_fifo_mpmc.c
new file mode 100644
index 0000000..cbf4d93
--- /dev/null
+++ b/lib/ck/regressions/ck_fifo/validate/ck_fifo_mpmc.c
@@ -0,0 +1,168 @@
+/*
+ * 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 <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <pthread.h>
+#include <ck_fifo.h>
+
+#include "../../common.h"
+
+#ifdef CK_F_FIFO_MPMC
+#ifndef ITERATIONS
+#define ITERATIONS 128
+#endif
+
+struct context {
+ unsigned int tid;
+ unsigned int previous;
+ unsigned int next;
+};
+
+struct entry {
+ int tid;
+ int value;
+};
+
+static int nthr;
+
+#ifdef CK_F_FIFO_MPMC
+static ck_fifo_mpmc_t fifo CK_CC_CACHELINE;
+#endif
+
+static struct affinity a;
+static int size;
+static unsigned int barrier;
+
+static void *
+test(void *c)
+{
+#ifdef CK_F_FIFO_MPMC
+ struct context *context = c;
+ struct entry *entry;
+ ck_fifo_mpmc_entry_t *fifo_entry, *garbage;
+ int i, j;
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: Could not affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < (unsigned int)nthr);
+
+ for (i = 0; i < ITERATIONS; i++) {
+ for (j = 0; j < size; j++) {
+ fifo_entry = malloc(sizeof(ck_fifo_mpmc_entry_t));
+ entry = malloc(sizeof(struct entry));
+ entry->tid = context->tid;
+ ck_fifo_mpmc_enqueue(&fifo, fifo_entry, entry);
+ if (ck_fifo_mpmc_dequeue(&fifo, &entry, &garbage) == false) {
+ ck_error("ERROR [%u] Queue should never be empty.\n", context->tid);
+ }
+
+ if (entry->tid < 0 || entry->tid >= nthr) {
+ ck_error("ERROR [%u] Incorrect value in entry.\n", entry->tid);
+ }
+ }
+ }
+
+ for (i = 0; i < ITERATIONS; i++) {
+ for (j = 0; j < size; j++) {
+ fifo_entry = malloc(sizeof(ck_fifo_mpmc_entry_t));
+ entry = malloc(sizeof(struct entry));
+ entry->tid = context->tid;
+ while (ck_fifo_mpmc_tryenqueue(&fifo, fifo_entry, entry) == false)
+ ck_pr_stall();
+
+ while (ck_fifo_mpmc_trydequeue(&fifo, &entry, &garbage) == false)
+ ck_pr_stall();
+
+ if (entry->tid < 0 || entry->tid >= nthr) {
+ ck_error("ERROR [%u] Incorrect value in entry when using try interface.\n", entry->tid);
+ }
+ }
+ }
+#endif
+
+ return (NULL);
+}
+
+int
+main(int argc, char *argv[])
+{
+ int i, r;
+ struct context *context;
+ ck_fifo_mpmc_entry_t *garbage;
+ pthread_t *thread;
+
+ if (argc != 4) {
+ ck_error("Usage: validate <threads> <affinity delta> <size>\n");
+ }
+
+ a.request = 0;
+ a.delta = atoi(argv[2]);
+
+ nthr = atoi(argv[1]);
+ assert(nthr >= 1);
+
+ size = atoi(argv[3]);
+ assert(size > 0);
+
+ context = malloc(sizeof(*context) * nthr);
+ assert(context);
+
+ thread = malloc(sizeof(pthread_t) * nthr);
+ assert(thread);
+
+ ck_fifo_mpmc_init(&fifo, malloc(sizeof(ck_fifo_mpmc_entry_t)));
+ ck_fifo_mpmc_deinit(&fifo, &garbage);
+ if (garbage == NULL)
+ ck_error("ERROR: Expected non-NULL stub node on deinit.\n");
+ free(garbage);
+ ck_fifo_mpmc_init(&fifo, malloc(sizeof(ck_fifo_mpmc_entry_t)));
+
+ for (i = 0; i < nthr; i++) {
+ context[i].tid = i;
+ r = pthread_create(thread + i, NULL, test, context + i);
+ assert(r == 0);
+ }
+
+ for (i = 0; i < nthr; i++)
+ pthread_join(thread[i], NULL);
+
+ return (0);
+}
+#else
+int
+main(void)
+{
+ fprintf(stderr, "Unsupported.\n");
+ return 0;
+}
+#endif
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_fifo/validate/ck_fifo_mpmc_iterator.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_fifo/validate/ck_fifo_mpmc_iterator.c b/lib/ck/regressions/ck_fifo/validate/ck_fifo_mpmc_iterator.c
new file mode 100644
index 0000000..5ac8175
--- /dev/null
+++ b/lib/ck/regressions/ck_fifo/validate/ck_fifo_mpmc_iterator.c
@@ -0,0 +1,90 @@
+/*
+ * 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_fifo.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#ifdef CK_F_FIFO_MPMC
+struct example {
+ int x;
+};
+
+static ck_fifo_mpmc_t mpmc_fifo;
+
+int
+main(void)
+{
+ int i, length = 3;
+ struct example *examples;
+ ck_fifo_mpmc_entry_t *stub, *entries, *entry, *next;
+
+ stub = malloc(sizeof(ck_fifo_mpmc_entry_t));
+ if (stub == NULL)
+ exit(EXIT_FAILURE);
+
+ ck_fifo_mpmc_init(&mpmc_fifo, stub);
+
+ entries = malloc(sizeof(ck_fifo_mpmc_entry_t) * length);
+ if (entries == NULL)
+ exit(EXIT_FAILURE);
+
+ examples = malloc(sizeof(struct example) * length);
+ /* Need these for this unit test. */
+ if (examples == NULL)
+ exit(EXIT_FAILURE);
+
+ for (i = 0; i < length; ++i) {
+ examples[i].x = i;
+ ck_fifo_mpmc_enqueue(&mpmc_fifo, entries + i, examples + i);
+ }
+
+ puts("Testing CK_FIFO_MPMC_FOREACH.");
+ CK_FIFO_MPMC_FOREACH(&mpmc_fifo, entry) {
+ printf("Next value in fifo: %d\n", ((struct example *)entry->value)->x);
+ }
+
+ puts("Testing CK_FIFO_MPMC_FOREACH_SAFE.");
+ CK_FIFO_MPMC_FOREACH_SAFE(&mpmc_fifo, entry, next) {
+ if (entry->next.pointer != next)
+ exit(EXIT_FAILURE);
+ printf("Next value in fifo: %d\n", ((struct example *)entry->value)->x);
+ }
+
+ free(examples);
+ free(entries);
+ free(stub);
+
+ return (0);
+}
+#else
+int
+main(void)
+{
+ return (0);
+}
+#endif
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_fifo/validate/ck_fifo_spsc.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_fifo/validate/ck_fifo_spsc.c b/lib/ck/regressions/ck_fifo/validate/ck_fifo_spsc.c
new file mode 100644
index 0000000..c2ae16e
--- /dev/null
+++ b/lib/ck/regressions/ck_fifo/validate/ck_fifo_spsc.c
@@ -0,0 +1,177 @@
+/*
+ * 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 <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <pthread.h>
+
+#include <ck_fifo.h>
+
+#include "../../common.h"
+
+#ifndef ITERATIONS
+#define ITERATIONS 128
+#endif
+
+struct context {
+ unsigned int tid;
+ unsigned int previous;
+ unsigned int next;
+};
+
+struct entry {
+ int tid;
+ int value;
+};
+
+static int nthr;
+static ck_fifo_spsc_t *fifo;
+static struct affinity a;
+static int size;
+static unsigned int barrier;
+
+static void *
+test(void *c)
+{
+ struct context *context = c;
+ struct entry *entry;
+ ck_fifo_spsc_entry_t *fifo_entry;
+ int i, j;
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: Could not affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+#ifdef DEBUG
+ fprintf(stderr, "%p %u: %u -> %u\n", fifo+context->tid, context->tid, context->previous, context->tid);
+#endif
+
+ if (context->tid == 0) {
+ struct entry *entries;
+
+ entries = malloc(sizeof(struct entry) * size);
+ assert(entries != NULL);
+
+ for (i = 0; i < size; i++) {
+ entries[i].value = i;
+ entries[i].tid = 0;
+
+ fifo_entry = malloc(sizeof(ck_fifo_spsc_entry_t));
+ ck_fifo_spsc_enqueue(fifo + context->tid, fifo_entry, entries + i);
+ }
+ }
+
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < (unsigned int)nthr);
+
+ for (i = 0; i < ITERATIONS; i++) {
+ for (j = 0; j < size; j++) {
+ while (ck_fifo_spsc_dequeue(fifo + context->previous, &entry) == false);
+ if (context->previous != (unsigned int)entry->tid) {
+ ck_error("T [%u:%p] %u != %u\n",
+ context->tid, (void *)entry, entry->tid, context->previous);
+ }
+
+ if (entry->value != j) {
+ ck_error("V [%u:%p] %u != %u\n",
+ context->tid, (void *)entry, entry->value, j);
+ }
+
+ entry->tid = context->tid;
+ fifo_entry = ck_fifo_spsc_recycle(fifo + context->tid);
+ if (fifo_entry == NULL)
+ fifo_entry = malloc(sizeof(ck_fifo_spsc_entry_t));
+
+ ck_fifo_spsc_enqueue(fifo + context->tid, fifo_entry, entry);
+ }
+ }
+
+ return (NULL);
+}
+
+int
+main(int argc, char *argv[])
+{
+ int i, r;
+ struct context *context;
+ pthread_t *thread;
+
+ if (argc != 4) {
+ ck_error("Usage: validate <threads> <affinity delta> <size>\n");
+ }
+
+ a.request = 0;
+ a.delta = atoi(argv[2]);
+
+ nthr = atoi(argv[1]);
+ assert(nthr >= 1);
+
+ size = atoi(argv[3]);
+ assert(size > 0);
+
+ fifo = malloc(sizeof(ck_fifo_spsc_t) * nthr);
+ assert(fifo);
+
+ context = malloc(sizeof(*context) * nthr);
+ assert(context);
+
+ thread = malloc(sizeof(pthread_t) * nthr);
+ assert(thread);
+
+ for (i = 0; i < nthr; i++) {
+ ck_fifo_spsc_entry_t *garbage;
+
+ context[i].tid = i;
+ if (i == 0) {
+ context[i].previous = nthr - 1;
+ context[i].next = i + 1;
+ } else if (i == nthr - 1) {
+ context[i].next = 0;
+ context[i].previous = i - 1;
+ } else {
+ context[i].next = i + 1;
+ context[i].previous = i - 1;
+ }
+
+ ck_fifo_spsc_init(fifo + i, malloc(sizeof(ck_fifo_spsc_entry_t)));
+ ck_fifo_spsc_deinit(fifo + i, &garbage);
+ if (garbage == NULL)
+ ck_error("ERROR: Expected non-NULL stub node on deinit.\n");
+
+ free(garbage);
+ ck_fifo_spsc_init(fifo + i, malloc(sizeof(ck_fifo_spsc_entry_t)));
+ r = pthread_create(thread + i, NULL, test, context + i);
+ assert(r == 0);
+ }
+
+ for (i = 0; i < nthr; i++)
+ pthread_join(thread[i], NULL);
+
+ return (0);
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_fifo/validate/ck_fifo_spsc_iterator.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_fifo/validate/ck_fifo_spsc_iterator.c b/lib/ck/regressions/ck_fifo/validate/ck_fifo_spsc_iterator.c
new file mode 100644
index 0000000..97804de
--- /dev/null
+++ b/lib/ck/regressions/ck_fifo/validate/ck_fifo_spsc_iterator.c
@@ -0,0 +1,83 @@
+/*
+ * 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_fifo.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+struct example {
+ int x;
+};
+
+static ck_fifo_spsc_t spsc_fifo;
+
+int
+main(void)
+{
+ int i, length = 3;
+ struct example *examples;
+ ck_fifo_spsc_entry_t *stub, *entries, *entry, *next;
+
+ stub = malloc(sizeof(ck_fifo_spsc_entry_t));
+ if (stub == NULL)
+ exit(EXIT_FAILURE);
+
+ ck_fifo_spsc_init(&spsc_fifo, stub);
+
+ entries = malloc(sizeof(ck_fifo_spsc_entry_t) * length);
+ if (entries == NULL)
+ exit(EXIT_FAILURE);
+
+ examples = malloc(sizeof(struct example) * length);
+ /* Need these for this unit test. */
+ if (examples == NULL)
+ exit(EXIT_FAILURE);
+
+ for (i = 0; i < length; ++i) {
+ examples[i].x = i;
+ ck_fifo_spsc_enqueue(&spsc_fifo, entries + i, examples + i);
+ }
+
+ puts("Testing CK_FIFO_SPSC_FOREACH.");
+ CK_FIFO_SPSC_FOREACH(&spsc_fifo, entry) {
+ printf("Next value in fifo: %d\n", ((struct example *)entry->value)->x);
+ }
+
+ puts("Testing CK_FIFO_SPSC_FOREACH_SAFE.");
+ CK_FIFO_SPSC_FOREACH_SAFE(&spsc_fifo, entry, next) {
+ if (entry->next != next)
+ exit(EXIT_FAILURE);
+ printf("Next value in fifo: %d\n", ((struct example *)entry->value)->x);
+ }
+
+ free(examples);
+ free(entries);
+ free(stub);
+
+ return (0);
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/benchmark/Makefile
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/benchmark/Makefile b/lib/ck/regressions/ck_hp/benchmark/Makefile
new file mode 100644
index 0000000..2025ea9
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/benchmark/Makefile
@@ -0,0 +1,17 @@
+.PHONY: clean distribution
+
+OBJECTS=fifo_latency stack_latency
+
+all: $(OBJECTS)
+
+fifo_latency: fifo_latency.c
+ $(CC) $(CFLAGS) -o fifo_latency ../../../src/ck_hp.c fifo_latency.c
+
+stack_latency: stack_latency.c
+ $(CC) $(CFLAGS) -o stack_latency ../../../src/ck_hp.c stack_latency.c
+
+clean:
+ rm -rf *~ *.o *.dSYM *.exe $(OBJECTS)
+
+include ../../../build/regressions.build
+CFLAGS+=$(PTHREAD_CFLAGS) -D_GNU_SOURCE
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/benchmark/fifo_latency.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/benchmark/fifo_latency.c b/lib/ck/regressions/ck_hp/benchmark/fifo_latency.c
new file mode 100644
index 0000000..c32986b
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/benchmark/fifo_latency.c
@@ -0,0 +1,94 @@
+/*
+ * 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_hp.h>
+#include <ck_hp_fifo.h>
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "../../common.h"
+
+#ifndef ENTRIES
+#define ENTRIES 4096
+#endif
+
+#ifndef STEPS
+#define STEPS 40000
+#endif
+
+static ck_hp_fifo_t fifo;
+static ck_hp_t fifo_hp;
+
+int
+main(void)
+{
+ void *r;
+ uint64_t s, e, a;
+ unsigned int i;
+ unsigned int j;
+ ck_hp_fifo_entry_t hp_entry[ENTRIES];
+ ck_hp_fifo_entry_t hp_stub;
+ ck_hp_record_t record;
+
+ ck_hp_init(&fifo_hp, CK_HP_FIFO_SLOTS_COUNT, 1000000, NULL);
+
+ r = malloc(CK_HP_FIFO_SLOTS_SIZE);
+ if (r == NULL) {
+ ck_error("ERROR: Failed to allocate slots.\n");
+ }
+ ck_hp_register(&fifo_hp, &record, r);
+
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_hp_fifo_init(&fifo, &hp_stub);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++)
+ ck_hp_fifo_enqueue_mpmc(&record, &fifo, hp_entry + j, NULL);
+ e = rdtsc();
+
+ a += e - s;
+ }
+ printf("ck_hp_fifo_enqueue_mpmc: %16" PRIu64 "\n", a / STEPS / ENTRIES);
+
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_hp_fifo_init(&fifo, &hp_stub);
+ for (j = 0; j < ENTRIES; j++)
+ ck_hp_fifo_enqueue_mpmc(&record, &fifo, hp_entry + j, NULL);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++)
+ ck_hp_fifo_dequeue_mpmc(&record, &fifo, &r);
+ e = rdtsc();
+ a += e - s;
+ }
+ printf("ck_hp_fifo_dequeue_mpmc: %16" PRIu64 "\n", a / STEPS / ENTRIES);
+
+ return 0;
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/benchmark/stack_latency.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/benchmark/stack_latency.c b/lib/ck/regressions/ck_hp/benchmark/stack_latency.c
new file mode 100644
index 0000000..bdde7bd
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/benchmark/stack_latency.c
@@ -0,0 +1,95 @@
+/*
+ * 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_hp.h>
+#include <ck_hp_stack.h>
+#include <ck_stack.h>
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "../../common.h"
+
+#ifndef ENTRIES
+#define ENTRIES 4096
+#endif
+
+#ifndef STEPS
+#define STEPS 40000
+#endif
+
+static ck_stack_t stack;
+static ck_hp_t stack_hp;
+
+int
+main(void)
+{
+ ck_hp_record_t record;
+ ck_stack_entry_t entry[ENTRIES];
+ uint64_t s, e, a;
+ unsigned int i;
+ unsigned int j;
+ void *r;
+
+ ck_hp_init(&stack_hp, CK_HP_STACK_SLOTS_COUNT, 1000000, NULL);
+ r = malloc(CK_HP_STACK_SLOTS_SIZE);
+ if (r == NULL) {
+ ck_error("ERROR: Failed to allocate slots.\n");
+ }
+ ck_hp_register(&stack_hp, &record, (void *)r);
+
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_stack_init(&stack);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++)
+ ck_hp_stack_push_mpmc(&stack, entry + j);
+ e = rdtsc();
+
+ a += e - s;
+ }
+ printf("ck_hp_stack_push_mpmc: %16" PRIu64 "\n", a / STEPS / ENTRIES);
+
+ a = 0;
+ for (i = 0; i < STEPS; i++) {
+ ck_stack_init(&stack);
+
+ for (j = 0; j < ENTRIES; j++)
+ ck_hp_stack_push_mpmc(&stack, entry + j);
+
+ s = rdtsc();
+ for (j = 0; j < ENTRIES; j++) {
+ r = ck_hp_stack_pop_mpmc(&record, &stack);
+ }
+ e = rdtsc();
+ a += e - s;
+ }
+ printf(" ck_hp_stack_pop_mpmc: %16" PRIu64 "\n", a / STEPS / ENTRIES);
+
+ return 0;
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/validate/Makefile
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/validate/Makefile b/lib/ck/regressions/ck_hp/validate/Makefile
new file mode 100644
index 0000000..476b34f
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/validate/Makefile
@@ -0,0 +1,33 @@
+.PHONY: check clean distribution
+
+OBJECTS=ck_hp_stack nbds_haz_test serial ck_hp_fifo ck_hp_fifo_donner
+
+all: $(OBJECTS)
+
+check: all
+ ./serial
+ ./ck_hp_stack $(CORES) 100 1
+ ./ck_hp_fifo $(CORES) 1 16384 100
+ ./nbds_haz_test $(CORES) 15 1
+ ./ck_hp_fifo_donner $(CORES) 16384
+
+ck_hp_stack: ../../../src/ck_hp.c ck_hp_stack.c ../../../include/ck_hp_stack.h
+ $(CC) $(CFLAGS) ../../../src/ck_hp.c -o ck_hp_stack ck_hp_stack.c
+
+ck_hp_fifo: ../../../src/ck_hp.c ck_hp_fifo.c ../../../include/ck_hp_fifo.h
+ $(CC) $(CFLAGS) ../../../src/ck_hp.c -o ck_hp_fifo ck_hp_fifo.c
+
+ck_hp_fifo_donner: ../../../src/ck_hp.c ck_hp_fifo_donner.c ../../../include/ck_hp_fifo.h
+ $(CC) $(CFLAGS) ../../../src/ck_hp.c -o ck_hp_fifo_donner ck_hp_fifo_donner.c
+
+serial: ../../../src/ck_hp.c serial.c ../../../include/ck_hp_stack.h
+ $(CC) $(CFLAGS) ../../../src/ck_hp.c -o serial serial.c
+
+nbds_haz_test: ../../../src/ck_hp.c nbds_haz_test.c
+ $(CC) $(CFLAGS) ../../../src/ck_hp.c -o nbds_haz_test nbds_haz_test.c
+
+clean:
+ rm -rf *~ *.o *.dSYM *.exe $(OBJECTS)
+
+include ../../../build/regressions.build
+CFLAGS+=$(PTHREAD_CFLAGS) -D_GNU_SOURCE
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/validate/ck_hp_fifo.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/validate/ck_hp_fifo.c b/lib/ck/regressions/ck_hp/validate/ck_hp_fifo.c
new file mode 100644
index 0000000..297041b
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/validate/ck_hp_fifo.c
@@ -0,0 +1,187 @@
+/*
+ * 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 <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <pthread.h>
+#include <ck_hp_fifo.h>
+
+#include "../../common.h"
+
+#ifndef ITERATIONS
+#define ITERATIONS 128
+#endif
+
+struct context {
+ unsigned int tid;
+ unsigned int previous;
+ unsigned int next;
+};
+
+struct entry {
+ int tid;
+ int value;
+};
+
+static ck_hp_fifo_t fifo;
+static ck_hp_t fifo_hp;
+static int nthr;
+
+static struct affinity a;
+static int size;
+static unsigned int barrier;
+static unsigned int e_barrier;
+
+static void *
+test(void *c)
+{
+ struct context *context = c;
+ struct entry *entry;
+ ck_hp_fifo_entry_t *fifo_entry;
+ ck_hp_record_t record;
+ int i, j;
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: Could not affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ ck_hp_register(&fifo_hp, &record, malloc(sizeof(void *) * 2));
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < (unsigned int)nthr);
+
+ for (i = 0; i < ITERATIONS; i++) {
+ for (j = 0; j < size; j++) {
+ fifo_entry = malloc(sizeof(ck_hp_fifo_entry_t));
+ entry = malloc(sizeof(struct entry));
+ entry->tid = context->tid;
+ ck_hp_fifo_enqueue_mpmc(&record, &fifo, fifo_entry, entry);
+
+ ck_pr_barrier();
+
+ fifo_entry = ck_hp_fifo_dequeue_mpmc(&record, &fifo, &entry);
+ if (fifo_entry == NULL) {
+ ck_error("ERROR [%u] Queue should never be empty.\n", context->tid);
+ }
+
+ ck_pr_barrier();
+
+ if (entry->tid < 0 || entry->tid >= nthr) {
+ ck_error("ERROR [%u] Incorrect value in entry.\n", entry->tid);
+ }
+
+ ck_hp_free(&record, &fifo_entry->hazard, fifo_entry, fifo_entry);
+ }
+ }
+
+ for (i = 0; i < ITERATIONS; i++) {
+ for (j = 0; j < size; j++) {
+ fifo_entry = malloc(sizeof(ck_hp_fifo_entry_t));
+ entry = malloc(sizeof(struct entry));
+ entry->tid = context->tid;
+
+ while (ck_hp_fifo_tryenqueue_mpmc(&record, &fifo, fifo_entry, entry) == false)
+ ck_pr_stall();
+
+ while (fifo_entry = ck_hp_fifo_trydequeue_mpmc(&record, &fifo, &entry), fifo_entry == NULL)
+ ck_pr_stall();
+
+ if (entry->tid < 0 || entry->tid >= nthr) {
+ ck_error("ERROR [%u] Incorrect value in entry.\n", entry->tid);
+ }
+
+ ck_hp_free(&record, &fifo_entry->hazard, fifo_entry, fifo_entry);
+ }
+ }
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < (unsigned int)nthr);
+
+ return (NULL);
+}
+
+static void
+destructor(void *p)
+{
+
+ free(p);
+ return;
+}
+
+int
+main(int argc, char *argv[])
+{
+ int i, r;
+ struct context *context;
+ pthread_t *thread;
+ int threshold;
+
+ if (argc != 5) {
+ ck_error("Usage: validate <threads> <affinity delta> <size> <threshold>\n");
+ }
+
+ a.delta = atoi(argv[2]);
+
+ nthr = atoi(argv[1]);
+ assert(nthr >= 1);
+
+ size = atoi(argv[3]);
+ assert(size > 0);
+
+ threshold = atoi(argv[4]);
+ assert(threshold > 0);
+
+ context = malloc(sizeof(*context) * nthr);
+ assert(context);
+
+ thread = malloc(sizeof(pthread_t) * nthr);
+ assert(thread);
+
+ ck_hp_init(&fifo_hp, 2, threshold, destructor);
+ ck_hp_fifo_init(&fifo, malloc(sizeof(ck_hp_fifo_entry_t)));
+
+ ck_hp_fifo_entry_t *entry;
+ ck_hp_fifo_deinit(&fifo, &entry);
+
+ if (entry == NULL)
+ ck_error("ERROR: Expected non-NULL stub node.\n");
+
+ free(entry);
+ ck_hp_fifo_init(&fifo, malloc(sizeof(ck_hp_fifo_entry_t)));
+
+ for (i = 0; i < nthr; i++) {
+ context[i].tid = i;
+ r = pthread_create(thread + i, NULL, test, context + i);
+ assert(r == 0);
+ }
+
+ for (i = 0; i < nthr; i++)
+ pthread_join(thread[i], NULL);
+
+ return (0);
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/validate/ck_hp_fifo_donner.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/validate/ck_hp_fifo_donner.c b/lib/ck/regressions/ck_hp/validate/ck_hp_fifo_donner.c
new file mode 100644
index 0000000..43e00ae
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/validate/ck_hp_fifo_donner.c
@@ -0,0 +1,213 @@
+/*
+ * Copyright 2012 Hendrik Donner
+ * 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_hp.h>
+#include <ck_hp_fifo.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <pthread.h>
+#include <sys/time.h>
+#include <assert.h>
+#include "../../common.h"
+
+/* FIFO queue */
+static ck_hp_fifo_t fifo;
+
+/* Hazard pointer global */
+static ck_hp_t fifo_hp;
+
+/* thread local element count */
+static unsigned long *count;
+
+static unsigned long thread_count;
+
+static unsigned int start_barrier;
+static unsigned int end_barrier;
+
+/* destructor for FIFO queue */
+static void
+destructor(void *p)
+{
+
+ free(p);
+ return;
+}
+
+/* entry struct for FIFO queue entries */
+struct entry {
+ unsigned long value;
+};
+
+/* function for thread */
+static void *
+queue_50_50(void *elements)
+{
+ struct entry *entry;
+ ck_hp_fifo_entry_t *fifo_entry;
+ ck_hp_record_t *record;
+ void *slots;
+ unsigned long j, element_count = *(unsigned long *)elements;
+ unsigned int seed;
+
+ record = malloc(sizeof(ck_hp_record_t));
+ assert(record);
+
+ slots = malloc(CK_HP_FIFO_SLOTS_SIZE);
+ assert(slots);
+
+ /* different seed for each thread */
+ seed = 1337; /*(unsigned int) pthread_self(); */
+
+ /*
+ * This subscribes the thread to the fifo_hp state using the thread-owned
+ * record.
+ * FIFO queue needs 2 hazard pointers.
+ */
+ ck_hp_register(&fifo_hp, record, slots);
+
+ /* start barrier */
+ ck_pr_inc_uint(&start_barrier);
+ while (ck_pr_load_uint(&start_barrier) < thread_count + 1)
+ ck_pr_stall();
+
+ /* 50/50 enqueue-dequeue */
+ for(j = 0; j < element_count; j++) {
+ /* rand_r with thread local state should be thread safe */
+ if( 50 < (1+(int) (100.0*common_rand_r(&seed)/(RAND_MAX+1.0)))) {
+ /* This is the container for the enqueued data. */
+ fifo_entry = malloc(sizeof(ck_hp_fifo_entry_t));
+
+ if (fifo_entry == NULL) {
+ exit(EXIT_FAILURE);
+ }
+
+ /* This is the data. */
+ entry = malloc(sizeof(struct entry));
+ if (entry != NULL) {
+ entry->value = j;
+ }
+
+ /*
+ * Enqueue the value of the pointer entry into FIFO queue using the
+ * container fifo_entry.
+ */
+ ck_hp_fifo_enqueue_mpmc(record, &fifo, fifo_entry, entry);
+ } else {
+ /*
+ * ck_hp_fifo_dequeue_mpmc will return a pointer to the first unused node and store
+ * the value of the first pointer in the FIFO queue in entry.
+ */
+ fifo_entry = ck_hp_fifo_dequeue_mpmc(record, &fifo, &entry);
+ if (fifo_entry != NULL) {
+ /*
+ * Safely reclaim memory associated with fifo_entry.
+ * This inserts garbage into a local list. Once the list (plist) reaches
+ * a length of 100, ck_hp_free will attempt to reclaim all references
+ * to objects on the list.
+ */
+ ck_hp_free(record, &fifo_entry->hazard, fifo_entry, fifo_entry);
+ }
+ }
+ }
+
+ /* end barrier */
+ ck_pr_inc_uint(&end_barrier);
+ while (ck_pr_load_uint(&end_barrier) < thread_count + 1)
+ ck_pr_stall();
+
+ return NULL;
+}
+
+int
+main(int argc, char** argv)
+{
+ ck_hp_fifo_entry_t *stub;
+ unsigned long element_count, i;
+ pthread_t *thr;
+
+ if (argc != 3) {
+ ck_error("Usage: cktest <thread_count> <element_count>\n");
+ }
+
+ /* Get element count from argument */
+ element_count = atoi(argv[2]);
+
+ /* Get element count from argument */
+ thread_count = atoi(argv[1]);
+
+ /* pthread handles */
+ thr = malloc(sizeof(pthread_t) * thread_count);
+
+ /* array for local operation count */
+ count = malloc(sizeof(unsigned long *) * thread_count);
+
+ /*
+ * Initialize global hazard pointer safe memory reclamation to execute free()
+ * when a fifo_entry is safe to be deleted.
+ * Hazard pointer scan routine will be called when the thread local intern plist's
+ * size exceed 100 entries.
+ */
+
+ /* FIFO queue needs 2 hazard pointers */
+ ck_hp_init(&fifo_hp, CK_HP_FIFO_SLOTS_COUNT, 100, destructor);
+
+ /* The FIFO requires one stub entry on initialization. */
+ stub = malloc(sizeof(ck_hp_fifo_entry_t));
+
+ /* Behavior is undefined if stub is NULL. */
+ if (stub == NULL) {
+ exit(EXIT_FAILURE);
+ }
+
+ /* This is called once to initialize the fifo. */
+ ck_hp_fifo_init(&fifo, stub);
+
+ /* Create threads */
+ for (i = 0; i < thread_count; i++) {
+ count[i] = (element_count + i) / thread_count;
+ if (pthread_create(&thr[i], NULL, queue_50_50, (void *) &count[i]) != 0) {
+ exit(EXIT_FAILURE);
+ }
+ }
+
+ /* start barrier */
+ ck_pr_inc_uint(&start_barrier);
+ while (ck_pr_load_uint(&start_barrier) < thread_count + 1);
+
+ /* end barrier */
+ ck_pr_inc_uint(&end_barrier);
+ while (ck_pr_load_uint(&end_barrier) < thread_count + 1);
+
+ /* Join threads */
+ for (i = 0; i < thread_count; i++)
+ pthread_join(thr[i], NULL);
+
+ return 0;
+}
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/validate/ck_hp_stack.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/validate/ck_hp_stack.c b/lib/ck/regressions/ck_hp/validate/ck_hp_stack.c
new file mode 100644
index 0000000..b028ce0
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/validate/ck_hp_stack.c
@@ -0,0 +1,165 @@
+/*
+ * 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.
+ */
+
+#include <errno.h>
+#include <inttypes.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <strings.h>
+#include <unistd.h>
+#include <sys/time.h>
+
+#include <ck_backoff.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <ck_hp.h>
+#include <ck_stack.h>
+#include <ck_hp_stack.h>
+
+#include "../../common.h"
+
+static unsigned int threshold;
+static unsigned int n_threads;
+static unsigned int barrier;
+static unsigned int e_barrier;
+
+#ifndef PAIRS
+#define PAIRS 5000000
+#endif
+
+struct node {
+ unsigned int value;
+ ck_hp_hazard_t hazard;
+ ck_stack_entry_t stack_entry;
+};
+static ck_stack_t stack = {NULL, NULL};
+static ck_hp_t stack_hp;
+CK_STACK_CONTAINER(struct node, stack_entry, stack_container)
+static struct affinity a;
+
+static void *
+thread(void *unused CK_CC_UNUSED)
+{
+ struct node **entry, *e;
+ unsigned int i;
+ ck_hp_record_t record;
+ void **pointers;
+ ck_stack_entry_t *s;
+
+ unused = NULL;
+ pointers = malloc(sizeof(void *));
+ ck_hp_register(&stack_hp, &record, pointers);
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: failed to affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ entry = malloc(sizeof(struct node *) * PAIRS);
+ if (entry == NULL) {
+ ck_error("Failed allocation.\n");
+ }
+
+ for (i = 0; i < PAIRS; i++) {
+ entry[i] = malloc(sizeof(struct node));
+ if (entry == NULL) {
+ ck_error("Failed individual allocation\n");
+ }
+ }
+
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < n_threads)
+ ck_pr_stall();
+
+ for (i = 0; i < PAIRS; i++) {
+ ck_hp_stack_push_mpmc(&stack, &entry[i]->stack_entry);
+ s = ck_hp_stack_pop_mpmc(&record, &stack);
+ e = stack_container(s);
+ ck_hp_free(&record, &e->hazard, e, s);
+ }
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < n_threads)
+ ck_pr_stall();
+
+ fprintf(stderr, "Peak: %u (%2.2f%%)\nReclamations: %" PRIu64 "\n\n",
+ record.n_peak,
+ (double)record.n_peak / PAIRS * 100,
+ record.n_reclamations);
+
+ ck_hp_clear(&record);
+ ck_hp_purge(&record);
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < (n_threads << 1));
+
+ if (record.n_pending != 0) {
+ ck_error("ERROR: %u pending, expecting none.\n",
+ record.n_pending);
+ }
+
+ return (NULL);
+}
+
+static void
+destructor(void *p)
+{
+
+ free(p);
+ return;
+}
+
+int
+main(int argc, char *argv[])
+{
+ unsigned int i;
+ pthread_t *threads;
+
+ if (argc != 4) {
+ ck_error("Usage: stack <threads> <threshold> <delta>\n");
+ }
+
+ n_threads = atoi(argv[1]);
+ threshold = atoi(argv[2]);
+ a.delta = atoi(argv[3]);
+ a.request = 0;
+
+ threads = malloc(sizeof(pthread_t) * n_threads);
+
+ ck_hp_init(&stack_hp, 1, threshold, destructor);
+
+ for (i = 0; i < n_threads; i++)
+ pthread_create(threads + i, NULL, thread, NULL);
+
+ for (i = 0; i < n_threads; i++)
+ pthread_join(threads[i], NULL);
+
+ return (0);
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/validate/nbds_haz_test.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/validate/nbds_haz_test.c b/lib/ck/regressions/ck_hp/validate/nbds_haz_test.c
new file mode 100644
index 0000000..a0346b4
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/validate/nbds_haz_test.c
@@ -0,0 +1,224 @@
+/*
+ * 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.
+ */
+
+/*
+ * This is a unit test similar to the implementation in John Dybnis's nbds
+ * test.
+ */
+
+#include <assert.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <pthread.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_backoff.h>
+#include <ck_cc.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <ck_hp.h>
+
+#include "../../common.h"
+
+#define STACK_CONTAINER(T, M, N) CK_CC_CONTAINER(stack_entry_t, T, M, N)
+
+struct stack_entry {
+ struct stack_entry *next;
+} CK_CC_ALIGN(8);
+typedef struct stack_entry stack_entry_t;
+
+struct stack {
+ struct stack_entry *head;
+ char *generation;
+} CK_CC_PACKED CK_CC_ALIGN(16);
+typedef struct stack hp_stack_t;
+
+static unsigned int threshold;
+static unsigned int n_threads;
+static unsigned int barrier;
+static unsigned int e_barrier;
+static unsigned int global_tid;
+static unsigned int pops;
+static unsigned int pushs;
+
+#ifndef PAIRS
+#define PAIRS 1000000
+#endif
+
+struct node {
+ unsigned int value;
+ ck_hp_hazard_t hazard;
+ stack_entry_t stack_entry;
+};
+hp_stack_t stack = {NULL, NULL};
+ck_hp_t stack_hp;
+
+STACK_CONTAINER(struct node, stack_entry, stack_container)
+static struct affinity a;
+
+/*
+ * Stack producer operation safe for multiple unique producers and multiple consumers.
+ */
+CK_CC_INLINE static void
+stack_push_mpmc(struct stack *target, struct stack_entry *entry)
+{
+ struct stack_entry *lstack;
+ ck_backoff_t backoff = CK_BACKOFF_INITIALIZER;
+
+ lstack = ck_pr_load_ptr(&target->head);
+ ck_pr_store_ptr(&entry->next, lstack);
+
+ while (ck_pr_cas_ptr_value(&target->head, lstack, entry, &lstack) == false) {
+ ck_pr_store_ptr(&entry->next, lstack);
+ ck_backoff_eb(&backoff);
+ }
+
+ return;
+}
+
+/*
+ * Stack consumer operation safe for multiple unique producers and multiple consumers.
+ */
+CK_CC_INLINE static struct stack_entry *
+stack_pop_mpmc(ck_hp_record_t *record, struct stack *target)
+{
+ struct stack_entry *entry;
+ ck_backoff_t backoff = CK_BACKOFF_INITIALIZER;
+
+ do {
+ entry = ck_pr_load_ptr(&target->head);
+ if (entry == NULL)
+ return (NULL);
+
+ ck_hp_set(record, 0, entry);
+ } while (entry != ck_pr_load_ptr(&target->head));
+
+ while (ck_pr_cas_ptr_value(&target->head, entry, entry->next, &entry) == false) {
+ if (ck_pr_load_ptr(&entry) == NULL)
+ break;
+
+ ck_hp_set(record, 0, entry);
+ if (entry != ck_pr_load_ptr(&target->head))
+ continue;
+
+ ck_backoff_eb(&backoff);
+ }
+
+ return (entry);
+}
+
+static void *
+thread(void *unused CK_CC_UNUSED)
+{
+ struct node *entry, *e;
+ unsigned int i;
+ ck_hp_record_t record;
+ void **pointers;
+ stack_entry_t *s;
+ unsigned int tid = ck_pr_faa_uint(&global_tid, 1) + 1;
+ unsigned int r = (unsigned int)(tid + 1) * 0x5bd1e995;
+
+ unused = NULL;
+ pointers = malloc(sizeof(void *));
+ ck_hp_register(&stack_hp, &record, pointers);
+
+ if (aff_iterate(&a)) {
+ perror("ERROR: failed to affine thread");
+ exit(EXIT_FAILURE);
+ }
+
+ ck_pr_inc_uint(&barrier);
+ while (ck_pr_load_uint(&barrier) < n_threads)
+ ck_pr_stall();
+
+ for (i = 0; i < PAIRS; i++) {
+ r ^= r << 6; r ^= r >> 21; r ^= r << 7;
+
+ if (r & 0x1000) {
+ entry = malloc(sizeof(struct node));
+ assert(entry);
+ stack_push_mpmc(&stack, &entry->stack_entry);
+ ck_pr_inc_uint(&pushs);
+ } else {
+ s = stack_pop_mpmc(&record, &stack);
+ if (s == NULL)
+ continue;
+
+ e = stack_container(s);
+ ck_hp_free(&record, &e->hazard, e, s);
+ ck_pr_inc_uint(&pops);
+ }
+ }
+
+ ck_pr_inc_uint(&e_barrier);
+ while (ck_pr_load_uint(&e_barrier) < n_threads);
+
+ return (NULL);
+}
+
+static void
+destructor(void *p)
+{
+ free(p);
+ return;
+}
+
+int
+main(int argc, char *argv[])
+{
+ unsigned int i;
+ pthread_t *threads;
+
+ if (argc != 4) {
+ ck_error("Usage: stack <threads> <threshold> <delta>\n");
+ }
+
+ n_threads = atoi(argv[1]);
+ threshold = atoi(argv[2]);
+ a.delta = atoi(argv[3]);
+ a.request = 0;
+
+ threads = malloc(sizeof(pthread_t) * n_threads);
+
+ ck_hp_init(&stack_hp, 1, threshold, destructor);
+
+ for (i = 0; i < n_threads; i++)
+ pthread_create(threads + i, NULL, thread, NULL);
+
+ for (i = 0; i < n_threads; i++)
+ pthread_join(threads[i], NULL);
+
+ fprintf(stderr, "Push: %u\nPop: %u\n", pushs, pops);
+ return (0);
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hp/validate/serial.c
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hp/validate/serial.c b/lib/ck/regressions/ck_hp/validate/serial.c
new file mode 100644
index 0000000..0385686
--- /dev/null
+++ b/lib/ck/regressions/ck_hp/validate/serial.c
@@ -0,0 +1,127 @@
+/*
+ * 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.
+ */
+
+#include <errno.h>
+#include <inttypes.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <strings.h>
+#include <unistd.h>
+#include <sys/time.h>
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <ck_hp.h>
+
+#include "../../common.h"
+
+struct entry {
+ unsigned int value;
+ ck_hp_hazard_t hazard;
+};
+
+static void
+destructor(void *pointer)
+{
+
+ fprintf(stderr, "Free %p\n", pointer);
+ free(pointer);
+ return;
+}
+
+int
+main(int argc, char *argv[])
+{
+ ck_hp_t state;
+ ck_hp_record_t record[2];
+ void **pointers;
+ struct entry *entry, *other;
+
+ (void)argc;
+ (void)argv;
+
+ ck_hp_init(&state, 1, 1, destructor);
+
+ pointers = malloc(sizeof(void *));
+ if (pointers == NULL) {
+ ck_error("ERROR: Failed to allocate slot.\n");
+ }
+ ck_hp_register(&state, &record[0], pointers);
+ ck_hp_reclaim(&record[0]);
+
+ entry = malloc(sizeof *entry);
+ ck_hp_set(&record[0], 0, entry);
+ ck_hp_reclaim(&record[0]);
+ ck_hp_free(&record[0], &entry->hazard, entry, entry);
+ ck_hp_reclaim(&record[0]);
+ ck_hp_set(&record[0], 0, NULL);
+ ck_hp_reclaim(&record[0]);
+
+ entry = malloc(sizeof *entry);
+ ck_hp_set(&record[0], 0, entry);
+ ck_hp_reclaim(&record[0]);
+ ck_hp_free(&record[0], &entry->hazard, entry, entry);
+ ck_hp_reclaim(&record[0]);
+ ck_hp_set(&record[0], 0, NULL);
+ ck_hp_reclaim(&record[0]);
+
+ pointers = malloc(sizeof(void *));
+ if (pointers == NULL) {
+ ck_error("ERROR: Failed to allocate slot.\n");
+ }
+ ck_hp_register(&state, &record[1], pointers);
+ ck_hp_reclaim(&record[1]);
+
+ entry = malloc(sizeof *entry);
+ ck_hp_set(&record[1], 0, entry);
+ ck_hp_reclaim(&record[1]);
+ ck_hp_free(&record[1], &entry->hazard, entry, entry);
+ ck_hp_reclaim(&record[1]);
+ ck_hp_set(&record[1], 0, NULL);
+ ck_hp_reclaim(&record[1]);
+
+ printf("Allocating entry and freeing in other HP record...\n");
+ entry = malloc(sizeof *entry);
+ entry->value = 42;
+ ck_hp_set(&record[0], 0, entry);
+ ck_hp_free(&record[1], &entry->hazard, entry, entry);
+ ck_pr_store_uint(&entry->value, 1);
+
+ other = malloc(sizeof *other);
+ other->value = 24;
+ ck_hp_set(&record[1], 0, other);
+ ck_hp_free(&record[0], &other->hazard, other, other);
+ ck_pr_store_uint(&other->value, 32);
+ ck_hp_set(&record[0], 0, NULL);
+ ck_hp_reclaim(&record[1]);
+ ck_hp_set(&record[1], 0, NULL);
+ ck_hp_reclaim(&record[0]);
+ ck_hp_reclaim(&record[1]);
+
+ return 0;
+}
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_hs/benchmark/Makefile
----------------------------------------------------------------------
diff --git a/lib/ck/regressions/ck_hs/benchmark/Makefile b/lib/ck/regressions/ck_hs/benchmark/Makefile
new file mode 100644
index 0000000..ca20809
--- /dev/null
+++ b/lib/ck/regressions/ck_hs/benchmark/Makefile
@@ -0,0 +1,20 @@
+.PHONY: clean distribution
+
+OBJECTS=serial parallel_bytestring parallel_bytestring.delete
+
+all: $(OBJECTS)
+
+serial: serial.c ../../../include/ck_hs.h ../../../src/ck_hs.c
+ $(CC) $(CFLAGS) -o serial serial.c ../../../src/ck_hs.c
+
+parallel_bytestring: parallel_bytestring.c ../../../include/ck_hs.h ../../../src/ck_hs.c ../../../src/ck_epoch.c
+ $(CC) $(PTHREAD_CFLAGS) $(CFLAGS) -o parallel_bytestring parallel_bytestring.c ../../../src/ck_hs.c ../../../src/ck_epoch.c
+
+parallel_bytestring.delete: parallel_bytestring.c ../../../include/ck_hs.h ../../../src/ck_hs.c ../../../src/ck_epoch.c
+ $(CC) $(PTHREAD_CFLAGS) $(CFLAGS) -DHS_DELETE -o parallel_bytestring.delete parallel_bytestring.c ../../../src/ck_hs.c ../../../src/ck_epoch.c
+
+clean:
+ rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe
+
+include ../../../build/regressions.build
+CFLAGS+=-D_GNU_SOURCE