http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_pr/validate/ck_pr_unary.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_pr/validate/ck_pr_unary.c b/lib/ck/regressions/ck_pr/validate/ck_pr_unary.c new file mode 100644 index 0000000..b2300cd --- /dev/null +++ b/lib/ck/regressions/ck_pr/validate/ck_pr_unary.c @@ -0,0 +1,117 @@ +/* + * 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 <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <ck_pr.h> + +#define REPEAT 2000000 + +#define TEST_UNARY(K, S, M, T, P, D, H) \ + static void \ + test_##K##_##S(M *target) \ + { \ + *target = *target P 1; \ + \ + return; \ + } \ + static void \ + test_##K##_##S##_zero(M *target, bool *zero) \ + { \ + *zero = *target == H; \ + *target = *target P 1; \ + \ + return; \ + } \ + static void \ + run_test_##K##_##S(bool use_zero) \ + { \ + int i; \ + T x = 1, y = 1; \ + bool zero_x = false, zero_y = false; \ + \ + use_zero ? puts("***TESTING ck_pr_"#K"_"#S"_zero***") \ + : puts("***TESTING ck_pr_"#K"_"#S"***"); \ + for (i = 0; i < REPEAT; ++i) { \ + if (use_zero) { \ + test_##K##_##S##_zero(&x, &zero_x); \ + ck_pr_##K##_##S##_zero(&y, &zero_y); \ + } \ + else { \ + test_##K##_##S(&x); \ + ck_pr_##K##_##S(&y); \ + } \ + \ + if (x != y || zero_x != zero_y) { \ + printf("Serial(%"#D") and ck_pr(%"#D")" \ + #K"_"#S" do not match.\n" \ + "FAILURE.\n", \ + x, y); \ + \ + return; \ + } \ + \ + if (zero_x) \ + printf("Variables are zero at iteration %d\n", i); \ + } \ + \ + \ + printf("\tserial_"#K"_"#S": %"#D"\n" \ + "\tck_pr_"#K"_"#S": %"#D"\n" \ + "SUCCESS.\n", \ + x, y); \ + \ + return; \ + } + +#define GENERATE_TEST(K, P, Y, Z) \ + TEST_UNARY(K, int, int, int, P, d, Y) \ + TEST_UNARY(K, uint, unsigned int, unsigned int, P, u, Z) \ + static void \ + run_test_##K(void) \ + { \ + run_test_##K##_int(false); \ + run_test_##K##_int(true); \ + run_test_##K##_uint(false); \ + run_test_##K##_uint(true); \ + } + +GENERATE_TEST(inc, +, -1, UINT_MAX) +GENERATE_TEST(dec, -, 1, 1) + +#undef GENERATE_TEST +#undef TEST_UNARY + +int +main(void) +{ + run_test_inc(); + run_test_dec(); + + return (0); +} +
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_pr/validate/ck_pr_xor.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_pr/validate/ck_pr_xor.c b/lib/ck/regressions/ck_pr/validate/ck_pr_xor.c new file mode 100644 index 0000000..4515cc4 --- /dev/null +++ b/lib/ck/regressions/ck_pr/validate/ck_pr_xor.c @@ -0,0 +1,147 @@ +/* + * Copyright 2009 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 <inttypes.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <unistd.h> + +#include <ck_pr.h> + +#include "../../common.h" +#ifndef R_REPEAT +#define R_REPEAT 200000 +#endif + +#define BM(m, w) ((uint##m##_t)-1 << (w)) + +#define CK_PR_XOR_T(w, v, d) \ + { \ + uint##w##_t t = v; \ + ck_pr_xor_##w(&t, d); \ + if (t != (uint##w##_t)(v ^ d)) { \ + printf("FAIL ["); \ + printf("%" PRIu##w " (%" PRIu##w ") -> %" PRIu##w "]\n",\ + (uint##w##_t)v, d, t); \ + exit(EXIT_FAILURE); \ + } \ + } + +#define CK_PR_XOR_B(w) \ + { \ + unsigned int __ck_i = 0; \ + printf("ck_pr_xor_" #w ": "); \ + if (w < 10) \ + printf(" "); \ + for (__ck_i = 0; __ck_i < R_REPEAT; __ck_i++) { \ + uint##w##_t a = (uint##w##_t)common_rand(); \ + uint##w##_t b = (uint##w##_t)common_rand(); \ + CK_PR_XOR_T(w, a, b); \ + } \ + rg_width(w); \ + printf(" SUCCESS\n"); \ + } + +#define CK_PR_XOR_W(m, w) \ + { \ + uint##m##_t t = -1; \ + ck_pr_xor_##w((uint##w##_t *)(void *)&t, -1); \ + if (t != BM(m, w)) { \ + printf(" FAIL [%#" PRIx##m " != %#" PRIx##m "]\n", t, BM(m, w)); \ + exit(EXIT_FAILURE); \ + } \ + } + +static void +rg_width(int m) +{ + + /* Other architectures are bi-endian. */ +#if !defined(__x86__) && !defined(__x86_64__) + return; +#endif + +#ifdef CK_F_PR_XOR_64 + if (m == 64) { +#if defined(CK_F_PR_XOR_32) + CK_PR_XOR_W(64, 32); +#endif +#if defined(CK_PR_XOR_16) + CK_PR_XOR_W(64, 16); +#endif +#if defined(CK_PR_XOR_8) + CK_PR_XOR_W(64, 8); +#endif + } +#endif /* CK_PR_XOR_64 */ + +#ifdef CK_F_PR_XOR_32 + if (m == 32) { +#if defined(CK_F_PR_XOR_16) + CK_PR_XOR_W(32, 16); +#endif +#if defined(CK_PR_XOR_8) + CK_PR_XOR_W(32, 8); +#endif + } +#endif /* CK_PR_XOR_32 */ + +#if defined(CK_F_PR_XOR_16) && defined(CK_PR_XOR_8) + if (m == 16) { + CK_PR_XOR_W(16, 8); + } +#endif /* CK_PR_XOR_16 && CK_PR_XOR_8 */ + + return; +} + +int +main(void) +{ + + common_srand((unsigned int)getpid()); + +#ifdef CK_F_PR_XOR_64 + CK_PR_XOR_B(64); +#endif + +#ifdef CK_F_PR_XOR_32 + CK_PR_XOR_B(32); +#endif + +#ifdef CK_F_PR_XOR_16 + CK_PR_XOR_B(16); +#endif + +#ifdef CK_F_PR_XOR_8 + CK_PR_XOR_B(8); +#endif + + return (0); +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_queue/validate/Makefile ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_queue/validate/Makefile b/lib/ck/regressions/ck_queue/validate/Makefile new file mode 100644 index 0000000..d6be3dc --- /dev/null +++ b/lib/ck/regressions/ck_queue/validate/Makefile @@ -0,0 +1,26 @@ +.PHONY: check clean distribution + +HEADER=../../../include/ck_queue.h +OBJECTS=ck_list ck_slist ck_stailq + +all: $(OBJECTS) + +check: all + ./ck_list $(CORES) 5 + ./ck_slist $(CORES) 5 + ./ck_stailq $(CORES) 1000000 + +ck_list: $(HEADER) ck_list.c + $(CC) $(CFLAGS) -o ck_list ck_list.c + +ck_slist: $(HEADER) ck_slist.c + $(CC) $(CFLAGS) -o ck_slist ck_slist.c + +ck_stailq: $(HEADER) ck_stailq.c + $(CC) $(CFLAGS) -o ck_stailq ck_stailq.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_queue/validate/ck_list.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_queue/validate/ck_list.c b/lib/ck/regressions/ck_queue/validate/ck_list.c new file mode 100644 index 0000000..2a29480 --- /dev/null +++ b/lib/ck/regressions/ck_queue/validate/ck_list.c @@ -0,0 +1,236 @@ +/* + * 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 <assert.h> +#include <stdlib.h> +#include <stdio.h> +#include <pthread.h> +#include <ck_queue.h> + +#include "../../common.h" + +struct test { + int value; + CK_LIST_ENTRY(test) list_entry; +}; +static CK_LIST_HEAD(test_list, test) head = CK_LIST_HEAD_INITIALIZER(head); + +static int goal; + +static void +test_foreach(void) +{ + struct test *n, *next, *safe; + int i, s = 0, j = 0, k = 0; + + for (i = goal; i != 0; i = goal) { + s = 0; + + CK_LIST_FOREACH(n, &head, list_entry) { + j++; + if (s == 0) + s = n->value; + else + s = s - 1; + + if (n->value != s) { + ck_error("\nExpected %d, but got %d.\n", + s, n->value); + } + + next = CK_LIST_NEXT(n, list_entry); + if (next != NULL && next->value != s - 1) { + ck_error("\nExpected %d, but got %d.\n", + s, next->value); + } + + i--; + } + + if (i == 0) + break; + + s = 0; + CK_LIST_FOREACH_SAFE(n, &head, list_entry, safe) { + k++; + + if (s == 0) + s = n->value; + else + s = s - 1; + + if (n->value != s) { + ck_error("\nExpected %d, but got %d.\n", + s, n->value); + } + + next = CK_LIST_NEXT(n, list_entry); + if (next != NULL && next->value != s - 1) { + ck_error("\nExpected %d, but got %d.\n", + s, next->value); + } + + i--; + } + + if (i == 0 || CK_LIST_EMPTY(&head) == true) + break; + } + + fprintf(stderr, "(%d, %d) ", j, k); + return; +} + +static void * +execute(void *c) +{ + + (void)c; + test_foreach(); + return NULL; +} + +int +main(int argc, char *argv[]) +{ + pthread_t *thread; + struct test *n, a, b; + struct test_list target; + int n_threads, i; + + if (argc != 3) { + ck_error("Usage: %s <number of threads> <number of list entries>\n", argv[0]); + } + + n_threads = atoi(argv[1]); + if (n_threads < 1) { + ck_error("ERROR: Number of threads must be >= 1.\n"); + } + + thread = malloc(sizeof(pthread_t) * n_threads); + assert(thread != NULL); + + goal = atoi(argv[2]); + if (goal < 4) { + ck_error("ERROR: Number of entries must be >= 4.\n"); + } + + fprintf(stderr, "Beginning serial test..."); + CK_LIST_INIT(&head); + + for (i = 1; i <= goal; i++) { + n = malloc(sizeof *n); + assert(n != NULL); + n->value = i; + CK_LIST_INSERT_HEAD(&head, n, list_entry); + } + + test_foreach(); + + for (i = 1; i <= goal; i++) { + n = CK_LIST_FIRST(&head); + CK_LIST_REMOVE(n, list_entry); + free(n); + } + + CK_LIST_INSERT_HEAD(&head, &a, list_entry); + CK_LIST_INSERT_HEAD(&head, &b, list_entry); + CK_LIST_REMOVE(&a, list_entry); + if (CK_LIST_FIRST(&head) != &b) + ck_error("List is in invalid state.\n"); + CK_LIST_REMOVE(&b, list_entry); + + if (CK_LIST_EMPTY(&head) == false) { + ck_error("List is not empty after bulk removal.\n"); + } + + CK_LIST_INSERT_HEAD(&head, &a, list_entry); + CK_LIST_INSERT_AFTER(&a, &b, list_entry); + + if (CK_LIST_NEXT(&b, list_entry) != NULL) + ck_error("Inserted item after last, it should not have no next.\n"); + + CK_LIST_INIT(&head); + + CK_LIST_INSERT_HEAD(&head, &a, list_entry); + CK_LIST_INSERT_BEFORE(&a, &b, list_entry); + + if (CK_LIST_NEXT(&b, list_entry) != &a) + ck_error("Inserted item before last, it should point to last.\n"); + + CK_LIST_INIT(&head); + fprintf(stderr, "done (success)\n"); + + fprintf(stderr, "Beginning parallel traversal..."); + + n = malloc(sizeof *n); + assert(n != NULL); + n->value = 1; + CK_LIST_INSERT_HEAD(&head, n, list_entry); + + for (i = 0; i < n_threads; i++) { + int r = pthread_create(&thread[i], NULL, execute, NULL); + assert(r == 0); + } + + for (i = 2; i <= goal; i++) { + volatile int j; + + n = malloc(sizeof *n); + assert(n != NULL); + n->value = i; + CK_LIST_INSERT_HEAD(&head, n, list_entry); + for (j = 0; j <= 1000; j++); + } + + for (i = 0; i < n_threads; i++) + pthread_join(thread[i], NULL); + + for (i = 0; i < n_threads; i++) { + int r = pthread_create(&thread[i], NULL, execute, NULL); + assert(r == 0); + } + + CK_LIST_MOVE(&target, &head, list_entry); + + for (i = 1; i <= goal; i++) { + volatile int j; + + if (CK_LIST_EMPTY(&target) == false) { + struct test *r = CK_LIST_FIRST(&target); + CK_LIST_REMOVE(r, list_entry); + } + + for (j = 0; j <= 1000; j++); + } + + for (i = 0; i < n_threads; i++) + pthread_join(thread[i], NULL); + + fprintf(stderr, "done (success)\n"); + return (0); +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_queue/validate/ck_slist.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_queue/validate/ck_slist.c b/lib/ck/regressions/ck_queue/validate/ck_slist.c new file mode 100644 index 0000000..a26fe81 --- /dev/null +++ b/lib/ck/regressions/ck_queue/validate/ck_slist.c @@ -0,0 +1,217 @@ +/* + * 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 <assert.h> +#include <stdlib.h> +#include <stdio.h> +#include <pthread.h> +#include <ck_queue.h> + +#include "../../common.h" + +struct test { + int value; + CK_SLIST_ENTRY(test) list_entry; +}; +static CK_SLIST_HEAD(test_list, test) head = CK_SLIST_HEAD_INITIALIZER(head); + +static int goal; + +static void +test_foreach(void) +{ + struct test *n, *next, *safe; + int i, s = 0, j = 0, k = 0; + + for (i = goal; i != 0; i = goal) { + s = 0; + + CK_SLIST_FOREACH(n, &head, list_entry) { + j++; + if (s == 0) + s = n->value; + else + s = s - 1; + + if (n->value != s) { + ck_error("\nExpected %d, but got %d.\n", + s, n->value); + } + + next = CK_SLIST_NEXT(n, list_entry); + if (next != NULL && next->value != s - 1) { + ck_error("\nExpected %d, but got %d.\n", + s, next->value); + } + + i--; + } + + if (i == 0) + break; + + s = 0; + CK_SLIST_FOREACH_SAFE(n, &head, list_entry, safe) { + k++; + + if (s == 0) + s = n->value; + else + s = s - 1; + + if (n->value != s) { + ck_error("\nExpected %d, but got %d.\n", + s, n->value); + } + + next = CK_SLIST_NEXT(n, list_entry); + if (next != NULL && next->value != s - 1) { + ck_error("\nExpected %d, but got %d.\n", + s, next->value); + } + + i--; + } + + if (i == 0 || CK_SLIST_EMPTY(&head) == true) + break; + } + + fprintf(stderr, "(%d, %d) ", j, k); + return; +} + +static void * +execute(void *c) +{ + + (void)c; + test_foreach(); + return NULL; +} + +int +main(int argc, char *argv[]) +{ + pthread_t *thread; + struct test *n; + struct test_list target; + int n_threads, i; + + if (argc != 3) { + ck_error("Usage: %s <number of threads> <number of list entries>\n", argv[0]); + } + + n_threads = atoi(argv[1]); + if (n_threads < 1) { + ck_error("ERROR: Number of threads must be >= 1.\n"); + } + + thread = malloc(sizeof(pthread_t) * n_threads); + assert(thread != NULL); + + goal = atoi(argv[2]); + if (goal < 4) { + ck_error("ERROR: Number of entries must be >= 4.\n"); + } + + fprintf(stderr, "Beginning serial test..."); + CK_SLIST_INIT(&head); + + for (i = 1; i <= goal; i++) { + n = malloc(sizeof *n); + assert(n != NULL); + n->value = i; + CK_SLIST_INSERT_HEAD(&head, n, list_entry); + } + + test_foreach(); + + for (i = 1; i <= goal; i++) { + n = CK_SLIST_FIRST(&head); + CK_SLIST_REMOVE_HEAD(&head, list_entry); + free(n); + } + + if (CK_SLIST_EMPTY(&head) == false) { + ck_error("List is not empty after bulk removal.\n"); + } + + fprintf(stderr, "done (success)\n"); + + fprintf(stderr, "Beginning parallel traversal..."); + + n = malloc(sizeof *n); + assert(n != NULL); + n->value = 1; + CK_SLIST_INSERT_HEAD(&head, n, list_entry); + + for (i = 0; i < n_threads; i++) { + int r = pthread_create(&thread[i], NULL, execute, NULL); + assert(r == 0); + } + + for (i = 2; i <= goal; i++) { + volatile int j; + + n = malloc(sizeof *n); + assert(n != NULL); + n->value = i; + CK_SLIST_INSERT_HEAD(&head, n, list_entry); + for (j = 0; j <= 1000; j++); + } + + for (i = 0; i < n_threads; i++) + pthread_join(thread[i], NULL); + + for (i = 0; i < n_threads; i++) { + int r = pthread_create(&thread[i], NULL, execute, NULL); + assert(r == 0); + } + + CK_SLIST_MOVE(&target, &head, list_entry); + + for (i = 1; i <= goal; i++) { + volatile int j; + + if (CK_SLIST_EMPTY(&target) == false) + CK_SLIST_REMOVE_HEAD(&target, list_entry); + + for (j = 0; j <= 1000; j++); + + if (CK_SLIST_EMPTY(&target) == false) { + struct test *r = CK_SLIST_FIRST(&target); + CK_SLIST_REMOVE(&target, r, test, list_entry); + } + } + + for (i = 0; i < n_threads; i++) + pthread_join(thread[i], NULL); + + fprintf(stderr, "done (success)\n"); + return (0); +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_queue/validate/ck_stailq.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_queue/validate/ck_stailq.c b/lib/ck/regressions/ck_queue/validate/ck_stailq.c new file mode 100644 index 0000000..1fafb0e --- /dev/null +++ b/lib/ck/regressions/ck_queue/validate/ck_stailq.c @@ -0,0 +1,256 @@ +/* + * 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 <assert.h> +#include <stdlib.h> +#include <stdio.h> +#include <pthread.h> +#include <ck_queue.h> +#include "../../common.h" + +struct test { + int value; + CK_STAILQ_ENTRY(test) list_entry; +}; +static CK_STAILQ_HEAD(test_list, test) head = CK_STAILQ_HEAD_INITIALIZER(head); + +static int goal; + +static void +test_foreach(void) +{ + struct test *n, *next, *safe; + int i, s = 0, j = 0, k = 0; + + for (i = goal; i != 0; i = goal) { + s = 0; + + CK_STAILQ_FOREACH(n, &head, list_entry) { + j++; + if (s == 0) + s = n->value; + else + s = s - 1; + + if (n->value != s) { + ck_error("\nExpected %d, but got %d.\n", + s, n->value); + } + + next = CK_STAILQ_NEXT(n, list_entry); + if (next != NULL && next->value != s - 1) { + ck_error("\nExpected %d, but got %d.\n", + s, next->value); + } + + i--; + } + + if (i == 0) + break; + + s = 0; + CK_STAILQ_FOREACH_SAFE(n, &head, list_entry, safe) { + k++; + + if (s == 0) + s = n->value; + else + s = s - 1; + + if (n->value != s) { + ck_error("\nExpected %d, but got %d.\n", + s, n->value); + } + + next = CK_STAILQ_NEXT(n, list_entry); + if (next != NULL && next->value != s - 1) { + ck_error("\nExpected %d, but got %d.\n", + s, next->value); + } + + i--; + } + + if (i == 0 || CK_STAILQ_EMPTY(&head) == true) + break; + } + + fprintf(stderr, "(%d, %d) ", j, k); + return; +} + +static void * +execute(void *c) +{ + + (void)c; + test_foreach(); + return NULL; +} + +int +main(int argc, char *argv[]) +{ + pthread_t *thread; + struct test *n, a, b; + struct test_list target; + int n_threads, i; + + if (argc != 3) { + ck_error("Usage: %s <number of threads> <number of list entries>\n", argv[0]); + } + + n_threads = atoi(argv[1]); + if (n_threads < 1) { + ck_error("ERROR: Number of threads must be >= 1.\n"); + } + + thread = malloc(sizeof(pthread_t) * n_threads); + assert(thread != NULL); + + goal = atoi(argv[2]); + if (goal < 4) { + ck_error("ERROR: Number of entries must be >= 4.\n"); + } + + fprintf(stderr, "Beginning serial test..."); + CK_STAILQ_INIT(&head); + + for (i = 1; i <= goal; i++) { + n = malloc(sizeof *n); + assert(n != NULL); + n->value = i; + CK_STAILQ_INSERT_HEAD(&head, n, list_entry); + } + + test_foreach(); + + for (i = 1; i <= goal; i++) { + n = CK_STAILQ_FIRST(&head); + CK_STAILQ_REMOVE(&head, n, test, list_entry); + free(n); + } + + if (CK_STAILQ_EMPTY(&head) == false) { + ck_error("List is not empty after bulk removal.\n"); + } + + for (i = 1; i <= goal; i++) { + n = malloc(sizeof *n); + assert(n != NULL); + n->value = goal - i; + CK_STAILQ_INSERT_TAIL(&head, n, list_entry); + } + + test_foreach(); + + for (i = 1; i <= goal; i++) { + n = CK_STAILQ_FIRST(&head); + CK_STAILQ_REMOVE(&head, n, test, list_entry); + free(n); + } + + if (CK_STAILQ_EMPTY(&head) == false) { + ck_error("List is not empty after bulk removal.\n"); + } + + CK_STAILQ_INSERT_HEAD(&head, &a, list_entry); + CK_STAILQ_INSERT_HEAD(&head, &b, list_entry); + CK_STAILQ_REMOVE(&head, &a, test, list_entry); + if (CK_STAILQ_FIRST(&head) != &b) + ck_error("List is in invalid state.\n"); + CK_STAILQ_REMOVE(&head, &b, test, list_entry); + + if (CK_STAILQ_EMPTY(&head) == false) { + ck_error("List is not empty after bulk removal.\n"); + } + + CK_STAILQ_INSERT_HEAD(&head, &a, list_entry); + CK_STAILQ_INSERT_AFTER(&head, &a, &b, list_entry); + + if (CK_STAILQ_NEXT(&b, list_entry) != NULL) + ck_error("Inserted item after last, it should not have no next.\n"); + + CK_STAILQ_INIT(&head); + + CK_STAILQ_INSERT_HEAD(&head, &a, list_entry); + if (CK_STAILQ_NEXT(&a, list_entry) != NULL) + ck_error("Inserted item as last, but it contains next pointer.\n"); + + CK_STAILQ_INIT(&head); + fprintf(stderr, "done (success)\n"); + + fprintf(stderr, "Beginning parallel traversal..."); + + n = malloc(sizeof *n); + assert(n != NULL); + n->value = 1; + CK_STAILQ_INSERT_HEAD(&head, n, list_entry); + + for (i = 0; i < n_threads; i++) { + int r = pthread_create(&thread[i], NULL, execute, NULL); + assert(r == 0); + } + + for (i = 2; i <= goal; i++) { + volatile int j; + + n = malloc(sizeof *n); + assert(n != NULL); + n->value = i; + CK_STAILQ_INSERT_HEAD(&head, n, list_entry); + for (j = 0; j <= 1000; j++); + } + + for (i = 0; i < n_threads; i++) + pthread_join(thread[i], NULL); + + for (i = 0; i < n_threads; i++) { + int r = pthread_create(&thread[i], NULL, execute, NULL); + assert(r == 0); + } + + CK_STAILQ_MOVE(&target, &head, list_entry); + + for (i = 1; i <= goal; i++) { + volatile int j; + + if (CK_STAILQ_EMPTY(&target) == false) { + struct test *r = CK_STAILQ_FIRST(&target); + CK_STAILQ_REMOVE(&target, r, test, list_entry); + } + + for (j = 0; j <= 1000; j++); + } + + for (i = 0; i < n_threads; i++) + pthread_join(thread[i], NULL); + + fprintf(stderr, "done (success)\n"); + return (0); +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_rhs/benchmark/Makefile ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_rhs/benchmark/Makefile b/lib/ck/regressions/ck_rhs/benchmark/Makefile new file mode 100644 index 0000000..e997993 --- /dev/null +++ b/lib/ck/regressions/ck_rhs/benchmark/Makefile @@ -0,0 +1,17 @@ +.PHONY: clean distribution + +OBJECTS=serial parallel_bytestring + +all: $(OBJECTS) + +serial: serial.c ../../../include/ck_rhs.h ../../../src/ck_rhs.c + $(CC) $(CFLAGS) -o serial serial.c ../../../src/ck_rhs.c + +parallel_bytestring: parallel_bytestring.c ../../../include/ck_rhs.h ../../../src/ck_rhs.c ../../../src/ck_epoch.c + $(CC) $(PTHREAD_CFLAGS) $(CFLAGS) -o parallel_bytestring parallel_bytestring.c ../../../src/ck_rhs.c ../../../src/ck_epoch.c + +clean: + rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe + +include ../../../build/regressions.build +CFLAGS+=-D_GNU_SOURCE http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_rhs/benchmark/parallel_bytestring.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_rhs/benchmark/parallel_bytestring.c b/lib/ck/regressions/ck_rhs/benchmark/parallel_bytestring.c new file mode 100644 index 0000000..f99cc89 --- /dev/null +++ b/lib/ck/regressions/ck_rhs/benchmark/parallel_bytestring.c @@ -0,0 +1,599 @@ +/* + * Copyright 2012 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 copyrighs + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyrighs + * 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 "../../common.h" +#include <ck_rhs.h> +#include "../../../src/ck_ht_hash.h" +#include <assert.h> +#include <ck_epoch.h> +#include <ck_malloc.h> +#include <ck_pr.h> +#include <ck_spinlock.h> + +#include <errno.h> +#include <inttypes.h> +#include <pthread.h> +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <unistd.h> + +static ck_rhs_t hs CK_CC_CACHELINE; +static char **keys; +static size_t keys_length = 0; +static size_t keys_capacity = 128; +static ck_epoch_t epoch_hs; +static ck_epoch_record_t epoch_wr; +static int n_threads; +static bool next_stage; + +enum state { + HS_STATE_STOP = 0, + HS_STATE_GET, + HS_STATE_STRICT_REPLACEMENT, + HS_STATE_DELETION, + HS_STATE_REPLACEMENT, + HS_STATE_COUNT +}; + +static ck_spinlock_t mtx = CK_SPINLOCK_INITIALIZER; +static struct affinity affinerator = AFFINITY_INITIALIZER; +static uint64_t accumulator[HS_STATE_COUNT]; +static int barrier[HS_STATE_COUNT]; +static int state; + +struct hs_epoch { + ck_epoch_entry_t epoch_entry; +}; + +COMMON_ALARM_DECLARE_GLOBAL(hs_alarm, alarm_event, next_stage) + +static void +alarm_handler(int s) +{ + + (void)s; + next_stage = true; + return; +} + +static unsigned long +hs_hash(const void *object, unsigned long seed) +{ + const char *c = object; + unsigned long h; + + h = (unsigned long)MurmurHash64A(c, strlen(c), seed); + return h; +} + +static bool +hs_compare(const void *previous, const void *compare) +{ + + return strcmp(previous, compare) == 0; +} + +static void +hs_destroy(ck_epoch_entry_t *e) +{ + + free(e); + return; +} + +static void * +hs_malloc(size_t r) +{ + ck_epoch_entry_t *b; + + b = malloc(sizeof(*b) + r); + return b + 1; +} + +static void +hs_free(void *p, size_t b, bool r) +{ + struct hs_epoch *e = p; + + (void)b; + + if (r == true) { + /* Destruction requires safe memory reclamation. */ + ck_epoch_call(&epoch_hs, &epoch_wr, &(--e)->epoch_entry, hs_destroy); + } else { + free(--e); + } + + return; +} + +static struct ck_malloc my_allocator = { + .malloc = hs_malloc, + .free = hs_free +}; + +static void +set_init(void) +{ + unsigned int mode = CK_RHS_MODE_OBJECT | CK_RHS_MODE_SPMC; + + + ck_epoch_init(&epoch_hs); + ck_epoch_register(&epoch_hs, &epoch_wr); + common_srand48((long int)time(NULL)); + if (ck_rhs_init(&hs, mode, hs_hash, hs_compare, &my_allocator, 65536, common_lrand48()) == false) { + perror("ck_rhs_init"); + exit(EXIT_FAILURE); + } + + return; +} + +static bool +set_remove(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return (bool)ck_rhs_remove(&hs, h, value); +} + +static bool +set_replace(const char *value) +{ + unsigned long h; + void *previous; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_set(&hs, h, value, &previous); +} + +static bool +set_swap(const char *value) +{ + unsigned long h; + void *previous; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_fas(&hs, h, value, &previous); +} + +static void * +set_get(const char *value) +{ + unsigned long h; + void *v; + + h = CK_RHS_HASH(&hs, hs_hash, value); + v = ck_rhs_get(&hs, h, value); + return v; +} + +static bool +set_insert(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_put(&hs, h, value); +} + +static size_t +set_count(void) +{ + + return ck_rhs_count(&hs); +} + +static bool +set_reset(void) +{ + + return ck_rhs_reset(&hs); +} + +static void * +reader(void *unused) +{ + size_t i; + ck_epoch_record_t epoch_record; + int state_previous = HS_STATE_STOP; + int n_state = 0; + uint64_t s, j, a; + + (void)unused; + if (aff_iterate(&affinerator) != 0) + perror("WARNING: Failed to affine thread"); + + s = j = a = 0; + ck_epoch_register(&epoch_hs, &epoch_record); + for (;;) { + j++; + ck_epoch_begin(&epoch_hs, &epoch_record); + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + char *r; + + r = set_get(keys[i]); + if (r == NULL) { + if (n_state == HS_STATE_STRICT_REPLACEMENT) { + ck_error("ERROR: Did not find during replacement: %s\n", keys[i]); + } + + continue; + } + + if (strcmp(r, keys[i]) == 0) + continue; + + ck_error("ERROR: Found invalid value: [%s] but expected [%s]\n", (char *)r, keys[i]); + } + a += rdtsc() - s; + ck_epoch_end(&epoch_hs, &epoch_record); + + n_state = ck_pr_load_int(&state); + if (n_state != state_previous) { + ck_spinlock_lock(&mtx); + accumulator[state_previous] += a / (j * keys_length); + ck_spinlock_unlock(&mtx); + + ck_pr_inc_int(&barrier[state_previous]); + while (ck_pr_load_int(&barrier[state_previous]) != n_threads + 1) + ck_pr_stall(); + + state_previous = n_state; + s = j = a = 0; + } + } + + return NULL; +} + +static uint64_t +acc(size_t i) +{ + uint64_t r; + + ck_spinlock_lock(&mtx); + r = accumulator[i]; + ck_spinlock_unlock(&mtx); + + return r; +} + +int +main(int argc, char *argv[]) +{ + FILE *fp; + char buffer[512]; + size_t i, j, r; + unsigned int d = 0; + uint64_t s, e, a, repeated; + char **t; + pthread_t *readers; + double p_r, p_d; + + COMMON_ALARM_DECLARE_LOCAL(hs_alarm, alarm_event) + + r = 20; + s = 8; + p_d = 0.5; + p_r = 0.5; + n_threads = CORES - 1; + + if (argc < 2) { + ck_error("Usage: parallel <dictionary> [<interval length> <initial size> <readers>\n" + " <probability of replacement> <probability of deletion> <epoch threshold>]\n"); + } + + if (argc >= 3) + r = atoi(argv[2]); + + if (argc >= 4) + s = (uint64_t)atoi(argv[3]); + + if (argc >= 5) { + n_threads = atoi(argv[4]); + if (n_threads < 1) { + ck_error("ERROR: Number of readers must be >= 1.\n"); + } + } + + if (argc >= 6) { + p_r = atof(argv[5]) / 100.00; + if (p_r < 0) { + ck_error("ERROR: Probability of replacement must be >= 0 and <= 100.\n"); + } + } + + if (argc >= 7) { + p_d = atof(argv[6]) / 100.00; + if (p_d < 0) { + ck_error("ERROR: Probability of deletion must be >= 0 and <= 100.\n"); + } + } + + COMMON_ALARM_INIT(hs_alarm, alarm_event, r) + + affinerator.delta = 1; + readers = malloc(sizeof(pthread_t) * n_threads); + assert(readers != NULL); + + keys = malloc(sizeof(char *) * keys_capacity); + assert(keys != NULL); + + fp = fopen(argv[1], "r"); + assert(fp != NULL); + + while (fgets(buffer, sizeof(buffer), fp) != NULL) { + buffer[strlen(buffer) - 1] = '\0'; + keys[keys_length++] = strdup(buffer); + assert(keys[keys_length - 1] != NULL); + + if (keys_length == keys_capacity) { + t = realloc(keys, sizeof(char *) * (keys_capacity *= 2)); + assert(t != NULL); + keys = t; + } + } + + t = realloc(keys, sizeof(char *) * keys_length); + assert(t != NULL); + keys = t; + + set_init(); + + for (i = 0; i < (size_t)n_threads; i++) { + if (pthread_create(&readers[i], NULL, reader, NULL) != 0) { + ck_error("ERROR: Failed to create thread %zu.\n", i); + } + } + + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + + fprintf(stderr, " [S] %d readers, 1 writer.\n", n_threads); + fprintf(stderr, " [S] %zu entries stored and %u duplicates.\n\n", + set_count(), d); + + fprintf(stderr, " ,- BASIC TEST\n"); + fprintf(stderr, " | Executing SMR test..."); + a = 0; + for (j = 0; j < r; j++) { + if (set_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + e = rdtsc(); + a += e - s; + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + fprintf(stderr, " | Executing replacement test..."); + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_replace(keys[i]); + e = rdtsc(); + a += e - s; + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + fprintf(stderr, " | Executing get test..."); + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + if (set_get(keys[i]) == NULL) { + ck_error("ERROR: Unexpected NULL value.\n"); + } + } + e = rdtsc(); + a += e - s; + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + a = 0; + fprintf(stderr, " | Executing removal test..."); + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + fprintf(stderr, " | Executing negative look-up test..."); + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + set_get("\x50\x03\x04\x05\x06\x10"); + } + e = rdtsc(); + a += e - s; + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + ck_epoch_record_t epoch_temporary = epoch_wr; + ck_epoch_synchronize(&epoch_hs, &epoch_wr); + + fprintf(stderr, " '- Summary: %u pending, %u peak, %lu reclamations -> " + "%u pending, %u peak, %lu reclamations\n\n", + epoch_temporary.n_pending, epoch_temporary.n_peak, epoch_temporary.n_dispatch, + epoch_wr.n_pending, epoch_wr.n_peak, epoch_wr.n_dispatch); + + fprintf(stderr, " ,- READER CONCURRENCY\n"); + fprintf(stderr, " | Executing reader test..."); + + ck_pr_store_int(&state, HS_STATE_GET); + while (ck_pr_load_int(&barrier[HS_STATE_STOP]) != n_threads) + ck_pr_stall(); + ck_pr_inc_int(&barrier[HS_STATE_STOP]); + common_sleep(r); + ck_pr_store_int(&state, HS_STATE_STRICT_REPLACEMENT); + while (ck_pr_load_int(&barrier[HS_STATE_GET]) != n_threads) + ck_pr_stall(); + + fprintf(stderr, "done (reader = %" PRIu64 " ticks)\n", + acc(HS_STATE_GET) / n_threads); + + fprintf(stderr, " | Executing strict replacement test..."); + + a = repeated = 0; + common_alarm(alarm_handler, &alarm_event, r); + + ck_pr_inc_int(&barrier[HS_STATE_GET]); + for (;;) { + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + if (i & 1) { + set_replace(keys[i]); + } else { + set_swap(keys[i]); + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + + ck_pr_store_int(&state, HS_STATE_DELETION); + while (ck_pr_load_int(&barrier[HS_STATE_STRICT_REPLACEMENT]) != n_threads) + ck_pr_stall(); + set_reset(); + ck_epoch_synchronize(&epoch_hs, &epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), acc(HS_STATE_STRICT_REPLACEMENT) / n_threads); + + common_alarm(alarm_handler, &alarm_event, r); + + fprintf(stderr, " | Executing deletion test (%.2f)...", p_d * 100); + a = repeated = 0; + ck_pr_inc_int(&barrier[HS_STATE_STRICT_REPLACEMENT]); + for (;;) { + double delete; + + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + set_insert(keys[i]); + if (p_d != 0.0) { + delete = common_drand48(); + if (delete <= p_d) + set_remove(keys[i]); + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + ck_pr_store_int(&state, HS_STATE_REPLACEMENT); + while (ck_pr_load_int(&barrier[HS_STATE_DELETION]) != n_threads) + ck_pr_stall(); + + set_reset(); + ck_epoch_synchronize(&epoch_hs, &epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), acc(HS_STATE_DELETION) / n_threads); + + common_alarm(alarm_handler, &alarm_event, r); + + fprintf(stderr, " | Executing replacement test (%.2f)...", p_r * 100); + a = repeated = 0; + ck_pr_inc_int(&barrier[HS_STATE_DELETION]); + for (;;) { + double delete, replace; + + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + set_insert(keys[i]); + if (p_d != 0.0) { + delete = common_drand48(); + if (delete <= p_d) + set_remove(keys[i]); + } else { + delete = 0.0; + } + + if (p_r != 0.0) { + replace = common_drand48(); + if (replace <= p_r) { + if ((i & 1) || (delete <= p_d)) { + set_replace(keys[i]); + } else { + set_swap(keys[i]); + } + } + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + ck_pr_store_int(&state, HS_STATE_STOP); + while (ck_pr_load_int(&barrier[HS_STATE_REPLACEMENT]) != n_threads) + ck_pr_stall(); + set_reset(); + ck_epoch_synchronize(&epoch_hs, &epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), acc(HS_STATE_REPLACEMENT) / n_threads); + + ck_pr_inc_int(&barrier[HS_STATE_REPLACEMENT]); + epoch_temporary = epoch_wr; + ck_epoch_synchronize(&epoch_hs, &epoch_wr); + + fprintf(stderr, " '- Summary: %u pending, %u peak, %lu reclamations -> " + "%u pending, %u peak, %lu reclamations\n\n", + epoch_temporary.n_pending, epoch_temporary.n_peak, epoch_temporary.n_dispatch, + epoch_wr.n_pending, epoch_wr.n_peak, epoch_wr.n_dispatch); + return 0; +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_rhs/benchmark/serial.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_rhs/benchmark/serial.c b/lib/ck/regressions/ck_rhs/benchmark/serial.c new file mode 100644 index 0000000..18fa892 --- /dev/null +++ b/lib/ck/regressions/ck_rhs/benchmark/serial.c @@ -0,0 +1,517 @@ +/* + * Copyright 2012 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 copyrighs + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyrighs + * 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_rhs.h> + +#include <assert.h> +#include <ck_malloc.h> +#include <errno.h> +#include <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include "../../common.h" +#include "../../../src/ck_ht_hash.h" + +static ck_rhs_t hs; +static char **keys; +static size_t keys_length = 0; +static size_t keys_capacity = 128; +static unsigned long global_seed; + +static void * +hs_malloc(size_t r) +{ + + return malloc(r); +} + +static void +hs_free(void *p, size_t b, bool r) +{ + + (void)b; + (void)r; + + free(p); + + return; +} + +static struct ck_malloc my_allocator = { + .malloc = hs_malloc, + .free = hs_free +}; + +static unsigned long +hs_hash(const void *object, unsigned long seed) +{ + const char *c = object; + unsigned long h; + + h = (unsigned long)MurmurHash64A(c, strlen(c), seed); + return h; +} + +static bool +hs_compare(const void *previous, const void *compare) +{ + + return strcmp(previous, compare) == 0; +} + +static void +set_destroy(void) +{ + + ck_rhs_destroy(&hs); + return; +} + +static void +set_init(unsigned int size, unsigned int mode) +{ + + if (ck_rhs_init(&hs, CK_RHS_MODE_OBJECT | CK_RHS_MODE_SPMC | mode, hs_hash, hs_compare, + &my_allocator, size, global_seed) == false) { + perror("ck_rhs_init"); + exit(EXIT_FAILURE); + } + + return; +} + +static bool +set_remove(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_remove(&hs, h, value) != NULL; +} + +static bool +set_swap(const char *value) +{ + unsigned long h; + void *previous; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_fas(&hs, h, value, &previous); +} + +static bool +set_replace(const char *value) +{ + unsigned long h; + void *previous; + + h = CK_RHS_HASH(&hs, hs_hash, value); + ck_rhs_set(&hs, h, value, &previous); + return previous != NULL; +} + +static void * +set_get(const char *value) +{ + unsigned long h; + void *v; + + h = CK_RHS_HASH(&hs, hs_hash, value); + v = ck_rhs_get(&hs, h, value); + return v; +} + +static bool +set_insert(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_put(&hs, h, value); +} + +static bool +set_insert_unique(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_put_unique(&hs, h, value); +} + +static size_t +set_count(void) +{ + + return ck_rhs_count(&hs); +} + +static bool +set_reset(void) +{ + + return ck_rhs_reset(&hs); +} + +static void +set_gc(void) +{ + + ck_rhs_gc(&hs); + return; +} + +static void +set_rebuild(void) +{ + + ck_rhs_rebuild(&hs); + return; +} + +static void +keys_shuffle(char **k) +{ + size_t i, j; + char *t; + + for (i = keys_length; i > 1; i--) { + j = rand() % (i - 1); + + if (j != i - 1) { + t = k[i - 1]; + k[i - 1] = k[j]; + k[j] = t; + } + } + + return; +} + +static void +run_test(const char *file, size_t r, unsigned int size, unsigned int mode) +{ + FILE *fp; + char buffer[512]; + size_t i, j; + unsigned int d = 0; + uint64_t s, e, a, ri, si, ai, sr, rg, sg, ag, sd, ng, ss, sts, su, sgc, sb; + struct ck_rhs_stat st; + char **t; + + keys = malloc(sizeof(char *) * keys_capacity); + assert(keys != NULL); + + fp = fopen(file, "r"); + assert(fp != NULL); + + while (fgets(buffer, sizeof(buffer), fp) != NULL) { + buffer[strlen(buffer) - 1] = '\0'; + keys[keys_length++] = strdup(buffer); + assert(keys[keys_length - 1] != NULL); + + if (keys_length == keys_capacity) { + t = realloc(keys, sizeof(char *) * (keys_capacity *= 2)); + assert(t != NULL); + keys = t; + } + } + + t = realloc(keys, sizeof(char *) * keys_length); + assert(t != NULL); + keys = t; + + set_init(size, mode); + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + ck_rhs_stat(&hs, &st); + + fprintf(stderr, "# %zu entries stored, %u duplicates, %u probe.\n", + set_count(), d, st.probe_maximum); + + a = 0; + for (j = 0; j < r; j++) { + if (set_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = keys_length; i > 0; i--) + d += set_insert(keys[i - 1]) == false; + e = rdtsc(); + a += e - s; + } + ri = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + if (set_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + e = rdtsc(); + a += e - s; + } + si = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + keys_shuffle(keys); + + if (set_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + e = rdtsc(); + a += e - s; + } + ai = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_swap(keys[i]); + e = rdtsc(); + a += e - s; + } + ss = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_replace(keys[i]); + e = rdtsc(); + a += e - s; + } + sr = a / (r * keys_length); + + set_reset(); + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = keys_length; i > 0; i--) { + if (set_get(keys[i - 1]) == NULL) { + ck_error("ERROR: Unexpected NULL value.\n"); + } + } + e = rdtsc(); + a += e - s; + } + rg = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + if (set_get(keys[i]) == NULL) { + ck_error("ERROR: Unexpected NULL value.\n"); + } + } + e = rdtsc(); + a += e - s; + } + sg = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + keys_shuffle(keys); + + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + if (set_get(keys[i]) == NULL) { + ck_error("ERROR: Unexpected NULL value.\n"); + } + } + e = rdtsc(); + a += e - s; + } + ag = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + } + sd = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + set_get("\x50\x03\x04\x05\x06\x10"); + } + e = rdtsc(); + a += e - s; + } + ng = a / (r * keys_length); + + set_reset(); + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + } + sts = a / (r * keys_length); + + set_reset(); + + /* Prune duplicates. */ + for (i = 0; i < keys_length; i++) { + if (set_insert(keys[i]) == true) + continue; + + free(keys[i]); + keys[i] = keys[--keys_length]; + } + + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_insert_unique(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + } + su = a / (r * keys_length); + + for (i = 0; i < keys_length; i++) + set_insert_unique(keys[i]); + + for (i = 0; i < keys_length / 2; i++) + set_remove(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + set_gc(); + e = rdtsc(); + a += e - s; + } + sgc = a / r; + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + set_rebuild(); + e = rdtsc(); + a += e - s; + } + sb = a / r; + + printf("%zu " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 "\n", + keys_length, ri, si, ai, ss, sr, rg, sg, ag, sd, ng, sts, su, sgc, sb); + + fclose(fp); + + for (i = 0; i < keys_length; i++) { + free(keys[i]); + } + + free(keys); + keys_length = 0; + set_destroy(); + return; +} + +int +main(int argc, char *argv[]) +{ + unsigned int r, size; + + common_srand48((long int)time(NULL)); + if (argc < 2) { + ck_error("Usage: ck_rhs <dictionary> [<repetitions> <initial size>]\n"); + } + + r = 16; + if (argc >= 3) + r = atoi(argv[2]); + + size = 8; + if (argc >= 4) + size = atoi(argv[3]); + + global_seed = common_lrand48(); + run_test(argv[1], r, size, 0); + run_test(argv[1], r, size, CK_RHS_MODE_READ_MOSTLY); + fprintf(stderr, "# reverse_insertion serial_insertion random_insertion serial_swap " + "serial_replace reverse_get serial_get random_get serial_remove negative_get tombstone " + "set_unique gc rebuild\n\n"); + + return 0; +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_rhs/validate/Makefile ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_rhs/validate/Makefile b/lib/ck/regressions/ck_rhs/validate/Makefile new file mode 100644 index 0000000..5987395 --- /dev/null +++ b/lib/ck/regressions/ck_rhs/validate/Makefile @@ -0,0 +1,17 @@ +.PHONY: check clean distribution + +OBJECTS=serial + +all: $(OBJECTS) + +serial: serial.c ../../../include/ck_rhs.h ../../../src/ck_rhs.c + $(CC) $(CFLAGS) -o serial serial.c ../../../src/ck_rhs.c + +check: all + ./serial + +clean: + rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe + +include ../../../build/regressions.build +CFLAGS+=-D_GNU_SOURCE http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_rhs/validate/serial.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_rhs/validate/serial.c b/lib/ck/regressions/ck_rhs/validate/serial.c new file mode 100644 index 0000000..1dc4db1 --- /dev/null +++ b/lib/ck/regressions/ck_rhs/validate/serial.c @@ -0,0 +1,245 @@ +/* + * Copyright 2012 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 copyrighs + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyrighs + * 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_rhs.h> + +#include <assert.h> +#include <ck_malloc.h> +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "../../common.h" + +static void * +hs_malloc(size_t r) +{ + + return malloc(r); +} + +static void +hs_free(void *p, size_t b, bool r) +{ + + (void)b; + (void)r; + free(p); + return; +} + +static struct ck_malloc my_allocator = { + .malloc = hs_malloc, + .free = hs_free +}; + +const char *test[] = { "Samy", "Al", "Bahra", "dances", "in", "the", "wind.", "Once", + "upon", "a", "time", "his", "gypsy", "ate", "one", "itsy", + "bitsy", "spider.", "What", "goes", "up", "must", + "come", "down.", "What", "is", "down", "stays", + "down.", "A", "B", "C", "D", "E", "F", "G", "H", + "I", "J", "K", "L", "M", "N", "O", "P", "Q" }; + +const char *negative = "negative"; + +/* Purposefully crappy hash function. */ +static unsigned long +hs_hash(const void *object, unsigned long seed) +{ + const char *c = object; + unsigned long h; + + (void)seed; + h = c[0]; + return h; +} + +static bool +hs_compare(const void *previous, const void *compare) +{ + + return strcmp(previous, compare) == 0; +} + +static void +run_test(unsigned int is, unsigned int ad) +{ + ck_rhs_t hs[16]; + const size_t size = sizeof(hs) / sizeof(*hs); + size_t i, j; + const char *blob = "#blobs"; + unsigned long h; + + if (ck_rhs_init(&hs[0], CK_RHS_MODE_SPMC | CK_RHS_MODE_OBJECT | ad, hs_hash, hs_compare, &my_allocator, is, 6602834) == false) + ck_error("ck_rhs_init\n"); + + for (j = 0; j < size; j++) { + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + h = test[i][0]; + if (ck_rhs_get(&hs[j], h, test[i]) != NULL) { + continue; + } + + if (ck_rhs_put_unique(&hs[j], h, test[i]) == false) + ck_error("ERROR [%zu]: Failed to insert unique (%s)\n", j, test[i]); + + if (ck_rhs_remove(&hs[j], h, test[i]) == false) + ck_error("ERROR [%zu]: Failed to remove unique (%s)\n", j, test[i]); + + break; + } + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + h = test[i][0]; + ck_rhs_put(&hs[j], h, test[i]); + if (ck_rhs_put(&hs[j], h, test[i]) == true) { + ck_error("ERROR [%u] [1]: put must fail on collision (%s).\n", is, test[i]); + } + if (ck_rhs_get(&hs[j], h, test[i]) == NULL) { + ck_error("ERROR [%u]: get must not fail after put\n", is); + } + } + + /* Test grow semantics. */ + ck_rhs_grow(&hs[j], 128); + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + h = test[i][0]; + if (ck_rhs_put(&hs[j], h, test[i]) == true) { + ck_error("ERROR [%u] [2]: put must fail on collision.\n", is); + } + + if (ck_rhs_get(&hs[j], h, test[i]) == NULL) { + ck_error("ERROR [%u]: get must not fail\n", is); + } + } + + h = blob[0]; + if (ck_rhs_get(&hs[j], h, blob) == NULL) { + if (j > 0) + ck_error("ERROR [%u]: Blob must always exist after first.\n", is); + + if (ck_rhs_put(&hs[j], h, blob) == false) { + ck_error("ERROR [%u]: A unique blob put failed.\n", is); + } + } else { + if (ck_rhs_put(&hs[j], h, blob) == true) { + ck_error("ERROR [%u]: Duplicate blob put succeeded.\n", is); + } + } + + /* Grow set and check get semantics. */ + ck_rhs_grow(&hs[j], 512); + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + h = test[i][0]; + if (ck_rhs_get(&hs[j], h, test[i]) == NULL) { + ck_error("ERROR [%u]: get must not fail\n", is); + } + } + + /* Delete and check negative membership. */ + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + void *r; + + h = test[i][0]; + if (ck_rhs_get(&hs[j], h, test[i]) == NULL) + continue; + + if (r = ck_rhs_remove(&hs[j], h, test[i]), r == NULL) { + ck_error("ERROR [%u]: remove must not fail\n", is); + } + + if (strcmp(r, test[i]) != 0) { + ck_error("ERROR [%u]: Removed incorrect node (%s != %s)\n", (char *)r, test[i], is); + } + } + + /* Test replacement semantics. */ + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + void *r; + bool d; + + h = test[i][0]; + d = ck_rhs_get(&hs[j], h, test[i]) != NULL; + if (ck_rhs_set(&hs[j], h, test[i], &r) == false) { + ck_error("ERROR [%u]: Failed to set\n", is); + } + + /* Expected replacement. */ + if (d == true && (r == NULL || strcmp(r, test[i]) != 0)) { + ck_error("ERROR [%u]: Incorrect previous value: %s != %s\n", + is, test[i], (char *)r); + } + + /* Replacement should succeed. */ + if (ck_rhs_fas(&hs[j], h, test[i], &r) == false) + ck_error("ERROR [%u]: ck_rhs_fas must succeed.\n", is); + + if (strcmp(r, test[i]) != 0) { + ck_error("ERROR [%u]: Incorrect replaced value: %s != %s\n", + is, test[i], (char *)r); + } + + if (ck_rhs_fas(&hs[j], h, negative, &r) == true) + ck_error("ERROR [%u]: Replacement of negative should fail.\n", is); + + if (ck_rhs_set(&hs[j], h, test[i], &r) == false) { + ck_error("ERROR [%u]: Failed to set [1]\n", is); + } + + if (strcmp(r, test[i]) != 0) { + ck_error("ERROR [%u]: Invalid &hs[j]: %s != %s\n", (char *)r, test[i], is); + } + } + + if (j == size - 1) + break; + + if (ck_rhs_move(&hs[j + 1], &hs[j], hs_hash, hs_compare, &my_allocator) == false) + ck_error("Failed to move hash table"); + + ck_rhs_gc(&hs[j + 1]); + + if (ck_rhs_rebuild(&hs[j + 1]) == false) + ck_error("Failed to rebuild"); + } + + return; +} + +int +main(void) +{ + unsigned int k; + + for (k = 16; k <= 64; k <<= 1) { + run_test(k, 0); + break; + } + + return 0; +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_ring/benchmark/Makefile ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_ring/benchmark/Makefile b/lib/ck/regressions/ck_ring/benchmark/Makefile new file mode 100644 index 0000000..4087ed1 --- /dev/null +++ b/lib/ck/regressions/ck_ring/benchmark/Makefile @@ -0,0 +1,14 @@ +.PHONY: clean distribution + +OBJECTS=latency + +all: $(OBJECTS) + +latency: latency.c ../../../include/ck_ring.h + $(CC) $(CFLAGS) -o latency latency.c + +clean: + rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe + +include ../../../build/regressions.build +CFLAGS+=-D_GNU_SOURCE http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_ring/benchmark/latency.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_ring/benchmark/latency.c b/lib/ck/regressions/ck_ring/benchmark/latency.c new file mode 100644 index 0000000..5e46b1c --- /dev/null +++ b/lib/ck/regressions/ck_ring/benchmark/latency.c @@ -0,0 +1,93 @@ +#include <ck_ring.h> +#include <inttypes.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> + +#include "../../common.h" + +#ifndef ITERATIONS +#define ITERATIONS (128000) +#endif + +struct entry { + int tid; + int value; +}; + +int +main(int argc, char *argv[]) +{ + int i, r, size; + uint64_t s, e, e_a, d_a; + struct entry entry = {0, 0}; + ck_ring_buffer_t *buf; + ck_ring_t ring; + + if (argc != 2) { + ck_error("Usage: latency <size>\n"); + } + + size = atoi(argv[1]); + if (size <= 4 || (size & (size - 1))) { + ck_error("ERROR: Size must be a power of 2 greater than 4.\n"); + } + + buf = malloc(sizeof(ck_ring_buffer_t) * size); + if (buf == NULL) { + ck_error("ERROR: Failed to allocate buffer\n"); + } + + ck_ring_init(&ring, size); + + e_a = d_a = s = e = 0; + for (r = 0; r < ITERATIONS; r++) { + for (i = 0; i < size / 4; i += 4) { + s = rdtsc(); + ck_ring_enqueue_spsc(&ring, buf, &entry); + ck_ring_enqueue_spsc(&ring, buf, &entry); + ck_ring_enqueue_spsc(&ring, buf, &entry); + ck_ring_enqueue_spsc(&ring, buf, &entry); + e = rdtsc(); + } + e_a += (e - s) / 4; + + for (i = 0; i < size / 4; i += 4) { + s = rdtsc(); + ck_ring_dequeue_spsc(&ring, buf, &entry); + ck_ring_dequeue_spsc(&ring, buf, &entry); + ck_ring_dequeue_spsc(&ring, buf, &entry); + ck_ring_dequeue_spsc(&ring, buf, &entry); + e = rdtsc(); + } + d_a += (e - s) / 4; + } + + printf("spsc %10d %16" PRIu64 " %16" PRIu64 "\n", size, e_a / ITERATIONS, d_a / ITERATIONS); + + e_a = d_a = s = e = 0; + for (r = 0; r < ITERATIONS; r++) { + for (i = 0; i < size / 4; i += 4) { + s = rdtsc(); + ck_ring_enqueue_spmc(&ring, buf, &entry); + ck_ring_enqueue_spmc(&ring, buf, &entry); + ck_ring_enqueue_spmc(&ring, buf, &entry); + ck_ring_enqueue_spmc(&ring, buf, &entry); + e = rdtsc(); + } + e_a += (e - s) / 4; + + for (i = 0; i < size / 4; i += 4) { + s = rdtsc(); + ck_ring_dequeue_spmc(&ring, buf, &entry); + ck_ring_dequeue_spmc(&ring, buf, &entry); + ck_ring_dequeue_spmc(&ring, buf, &entry); + ck_ring_dequeue_spmc(&ring, buf, &entry); + e = rdtsc(); + } + d_a += (e - s) / 4; + } + + printf("spmc %10d %16" PRIu64 " %16" PRIu64 "\n", size, e_a / ITERATIONS, d_a / ITERATIONS); + return (0); +} http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_ring/validate/Makefile ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_ring/validate/Makefile b/lib/ck/regressions/ck_ring/validate/Makefile new file mode 100644 index 0000000..8c00d80 --- /dev/null +++ b/lib/ck/regressions/ck_ring/validate/Makefile @@ -0,0 +1,29 @@ +.PHONY: check clean distribution + +OBJECTS=ck_ring_spsc ck_ring_spmc ck_ring_spmc_template +SIZE=16384 +CFLAGS += -g2 + +all: $(OBJECTS) + +check: all + ./ck_ring_spsc $(CORES) 1 $(SIZE) + ./ck_ring_spmc $(CORES) 1 $(SIZE) + +ck_ring_spsc: ck_ring_spsc.c ../../../include/ck_ring.h + $(CC) $(CFLAGS) -o ck_ring_spsc ck_ring_spsc.c \ + ../../../src/ck_barrier_centralized.c + +ck_ring_spmc: ck_ring_spmc.c ../../../include/ck_ring.h + $(CC) $(CFLAGS) -g2 -o ck_ring_spmc ck_ring_spmc.c \ + ../../../src/ck_barrier_centralized.c + +ck_ring_spmc_template: ck_ring_spmc_template.c ../../../include/ck_ring.h + $(CC) $(CFLAGS) -g2 -o ck_ring_spmc_template ck_ring_spmc.c \ + ../../../src/ck_barrier_centralized.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_ring/validate/ck_ring_spmc.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_ring/validate/ck_ring_spmc.c b/lib/ck/regressions/ck_ring/validate/ck_ring_spmc.c new file mode 100644 index 0000000..23fe0fa --- /dev/null +++ b/lib/ck/regressions/ck_ring/validate/ck_ring_spmc.c @@ -0,0 +1,340 @@ +/* + * 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 <string.h> +#include <pthread.h> + +#include <ck_barrier.h> +#include <ck_ring.h> +#include <ck_spinlock.h> +#include "../../common.h" + +#ifndef ITERATIONS +#define ITERATIONS 128 +#endif + +struct context { + unsigned int tid; + unsigned int previous; + unsigned int next; + ck_ring_buffer_t *buffer; +}; + +struct entry { + unsigned long value_long; + unsigned int magic; + unsigned int ref; + int tid; + int value; +}; + +static int nthr; +static ck_ring_t *ring; +static ck_ring_t ring_spmc CK_CC_CACHELINE; +static struct affinity a; +static int size; +static int eb; +static ck_barrier_centralized_t barrier = CK_BARRIER_CENTRALIZED_INITIALIZER; +static struct context *_context; + +static void * +test_spmc(void *c) +{ + unsigned int observed = 0; + unsigned long previous = 0; + unsigned int seed; + int i, k, j, tid; + struct context *context = c; + ck_ring_buffer_t *buffer; + + buffer = context->buffer; + if (aff_iterate(&a)) { + perror("ERROR: Could not affine thread"); + exit(EXIT_FAILURE); + } + + tid = ck_pr_faa_int(&eb, 1); + ck_pr_fence_memory(); + while (ck_pr_load_int(&eb) != nthr - 1); + + for (i = 0; i < ITERATIONS; i++) { + for (j = 0; j < size; j++) { + struct entry *o; + int spin; + + /* Keep trying until we encounter at least one node. */ + if (j & 1) { + while (ck_ring_dequeue_spmc(&ring_spmc, buffer, + &o) == false); + } else { + while (ck_ring_trydequeue_spmc(&ring_spmc, buffer, + &o) == false); + } + + observed++; + if (o->value < 0 + || o->value != o->tid + || o->magic != 0xdead + || (previous != 0 && previous >= o->value_long)) { + ck_error("[0x%p] (%x) (%d, %d) >< (0, %d)\n", + (void *)o, o->magic, o->tid, o->value, size); + } + + o->magic = 0xbeef; + o->value = -31337; + o->tid = -31338; + previous = o->value_long; + + if (ck_pr_faa_uint(&o->ref, 1) != 0) { + ck_error("[%p] We dequeued twice.\n", (void *)o); + } + + if ((i % 4) == 0) { + spin = common_rand_r(&seed) % 16384; + for (k = 0; k < spin; k++) { + ck_pr_stall(); + } + } + + free(o); + } + } + + fprintf(stderr, "[%d] Observed %u\n", tid, observed); + return NULL; +} + +static void * +test(void *c) +{ + struct context *context = c; + struct entry *entry; + unsigned int s; + int i, j; + bool r; + ck_ring_buffer_t *buffer = context->buffer; + ck_barrier_centralized_state_t sense = + CK_BARRIER_CENTRALIZED_STATE_INITIALIZER; + + if (aff_iterate(&a)) { + perror("ERROR: Could not affine thread"); + exit(EXIT_FAILURE); + } + + if (context->tid == 0) { + struct entry *entries; + + entries = malloc(sizeof(struct entry) * size); + assert(entries != NULL); + + if (ck_ring_size(ring) != 0) { + ck_error("More entries than expected: %u > 0\n", + ck_ring_size(ring)); + } + + for (i = 0; i < size; i++) { + entries[i].value = i; + entries[i].tid = 0; + + if (i & 1) { + r = ck_ring_enqueue_spmc(ring, buffer, + entries + i); + } else { + r = ck_ring_enqueue_spmc_size(ring, buffer, + entries + i, &s); + + if ((int)s != i) { + ck_error("Size is %u, expected %d.\n", + s, size); + } + } + + assert(r != false); + } + + if (ck_ring_size(ring) != (unsigned int)size) { + ck_error("Less entries than expected: %u < %d\n", + ck_ring_size(ring), size); + } + + if (ck_ring_capacity(ring) != ck_ring_size(ring) + 1) { + ck_error("Capacity less than expected: %u < %u\n", + ck_ring_size(ring), ck_ring_capacity(ring)); + } + } + + /* + * Wait for all threads. The idea here is to maximize the contention. + */ + ck_barrier_centralized(&barrier, &sense, nthr); + + for (i = 0; i < ITERATIONS; i++) { + for (j = 0; j < size; j++) { + buffer = _context[context->previous].buffer; + while (ck_ring_dequeue_spmc(ring + context->previous, + buffer, &entry) == false); + + if (context->previous != (unsigned int)entry->tid) { + ck_error("[%u:%p] %u != %u\n", + context->tid, (void *)entry, entry->tid, context->previous); + } + + if (entry->value < 0 || entry->value >= size) { + ck_error("[%u:%p] %u </> %u\n", + context->tid, (void *)entry, entry->tid, context->previous); + } + + entry->tid = context->tid; + buffer = context->buffer; + + if (i & 1) { + r = ck_ring_enqueue_spmc(ring + context->tid, + buffer, entry); + } else { + r = ck_ring_enqueue_spmc_size(ring + context->tid, + buffer, entry, &s); + + if ((int)s >= size) { + ck_error("Size %u out of range of %d\n", + s, size); + } + } + assert(r == true); + } + } + + return NULL; +} + +int +main(int argc, char *argv[]) +{ + int i, r; + unsigned long l; + pthread_t *thread; + ck_ring_buffer_t *buffer; + + 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 >= 4 && (size & size - 1) == 0); + size -= 1; + + ring = malloc(sizeof(ck_ring_t) * nthr); + assert(ring); + + _context = malloc(sizeof(*_context) * nthr); + assert(_context); + + thread = malloc(sizeof(pthread_t) * nthr); + assert(thread); + + fprintf(stderr, "SPSC test:"); + for (i = 0; i < nthr; i++) { + _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; + } + + buffer = malloc(sizeof(ck_ring_buffer_t) * (size + 1)); + assert(buffer); + memset(buffer, 0, sizeof(ck_ring_buffer_t) * (size + 1)); + _context[i].buffer = buffer; + ck_ring_init(ring + i, size + 1); + r = pthread_create(thread + i, NULL, test, _context + i); + assert(r == 0); + } + + for (i = 0; i < nthr; i++) + pthread_join(thread[i], NULL); + + fprintf(stderr, " done\n"); + + fprintf(stderr, "SPMC test:\n"); + buffer = malloc(sizeof(ck_ring_buffer_t) * (size + 1)); + assert(buffer); + memset(buffer, 0, sizeof(void *) * (size + 1)); + ck_ring_init(&ring_spmc, size + 1); + for (i = 0; i < nthr - 1; i++) { + _context[i].buffer = buffer; + r = pthread_create(thread + i, NULL, test_spmc, _context + i); + assert(r == 0); + } + + for (l = 0; l < (unsigned long)size * ITERATIONS * (nthr - 1) ; l++) { + struct entry *entry = malloc(sizeof *entry); + + assert(entry != NULL); + entry->value_long = l; + entry->value = (int)l; + entry->tid = (int)l; + entry->magic = 0xdead; + entry->ref = 0; + + /* Wait until queue is not full. */ + if (l & 1) { + while (ck_ring_enqueue_spmc(&ring_spmc, + buffer, + entry) == false) + ck_pr_stall(); + } else { + unsigned int s; + + while (ck_ring_enqueue_spmc_size(&ring_spmc, + buffer, entry, &s) == false) { + ck_pr_stall(); + } + + if ((int)s >= (size * ITERATIONS * (nthr - 1))) { + ck_error("MPMC: Unexpected size of %u\n", s); + } + } + } + + for (i = 0; i < nthr - 1; i++) + pthread_join(thread[i], NULL); + + return (0); +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/regressions/ck_ring/validate/ck_ring_spmc_template.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_ring/validate/ck_ring_spmc_template.c b/lib/ck/regressions/ck_ring/validate/ck_ring_spmc_template.c new file mode 100644 index 0000000..9facbc7 --- /dev/null +++ b/lib/ck/regressions/ck_ring/validate/ck_ring_spmc_template.c @@ -0,0 +1,347 @@ +/* + * 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 <string.h> +#include <pthread.h> + +#include <ck_barrier.h> +#include <ck_ring.h> +#include <ck_spinlock.h> +#include "../../common.h" + +#ifndef ITERATIONS +#define ITERATIONS 128 +#endif + +struct context { + unsigned int tid; + unsigned int previous; + unsigned int next; + struct entry *buffer; +}; + +struct entry { + unsigned long value_long; + unsigned int magic; + unsigned int ref; + int tid; + int value; +}; + +CK_RING_PROTOTYPE(entry, entry) + +static int nthr; +static ck_ring_t *ring; +static ck_ring_t ring_spmc CK_CC_CACHELINE; +static struct affinity a; +static int size; +static int eb; +static ck_barrier_centralized_t barrier = CK_BARRIER_CENTRALIZED_INITIALIZER; +static struct context *_context; + +static void * +test_spmc(void *c) +{ + unsigned int observed = 0; + unsigned long previous = 0; + unsigned int seed; + int i, k, j, tid; + struct context *context = c; + struct entry *buffer; + + buffer = context->buffer; + if (aff_iterate(&a)) { + perror("ERROR: Could not affine thread"); + exit(EXIT_FAILURE); + } + + tid = ck_pr_faa_int(&eb, 1); + ck_pr_fence_memory(); + while (ck_pr_load_int(&eb) != nthr - 1); + + for (i = 0; i < ITERATIONS; i++) { + for (j = 0; j < size; j++) { + struct entry *o; + int spin; + + /* Keep trying until we encounter at least one node. */ + if (j & 1) { + while (CK_RING_DEQUEUE_SPMC(entry, + &ring_spmc, buffer, &o) == false); + } else { + while (CK_RING_TRYDEQUEUE_SPMC(entry, + &ring_spmc, buffer, &o) == false); + } + + observed++; + if (o->value < 0 + || o->value != o->tid + || o->magic != 0xdead + || (previous != 0 && previous >= o->value_long)) { + ck_error("[0x%p] (%x) (%d, %d) >< (0, %d)\n", + (void *)o, o->magic, o->tid, o->value, size); + } + + o->magic = 0xbeef; + o->value = -31337; + o->tid = -31338; + previous = o->value_long; + + if (ck_pr_faa_uint(&o->ref, 1) != 0) { + ck_error("[%p] We dequeued twice.\n", (void *)o); + } + + if ((i % 4) == 0) { + spin = common_rand_r(&seed) % 16384; + for (k = 0; k < spin; k++) { + ck_pr_stall(); + } + } + + free(o); + } + } + + fprintf(stderr, "[%d] Observed %u\n", tid, observed); + return NULL; +} + +static void * +test(void *c) +{ + struct context *context = c; + struct entry entry; + unsigned int s; + int i, j; + bool r; + ck_ring_buffer_t *buffer = context->buffer; + ck_barrier_centralized_state_t sense = + CK_BARRIER_CENTRALIZED_STATE_INITIALIZER; + + if (aff_iterate(&a)) { + perror("ERROR: Could not affine thread"); + exit(EXIT_FAILURE); + } + + if (context->tid == 0) { + struct entry *entries; + + entries = malloc(sizeof(struct entry) * size); + assert(entries != NULL); + + if (ck_ring_size(ring) != 0) { + ck_error("More entries than expected: %u > 0\n", + ck_ring_size(ring)); + } + + for (i = 0; i < size; i++) { + entries[i].value = i; + entries[i].tid = 0; + + if (i & 1) { + r = CK_RING_ENQUEUE_SPMC(entry, ring, buffer, + entries + i); + } else { + r = CK_RING_ENQUEUE_SPMC_SIZE(entry, ring, + buffer, entries + i, &s); + + if ((int)s != i) { + ck_error("Size is %u, expected %d.\n", + s, size); + } + } + + assert(r != false); + } + + if (ck_ring_size(ring) != (unsigned int)size) { + ck_error("Less entries than expected: %u < %d\n", + ck_ring_size(ring), size); + } + + if (ck_ring_capacity(ring) != ck_ring_size(ring) + 1) { + ck_error("Capacity less than expected: %u < %u\n", + ck_ring_size(ring), ck_ring_capacity(ring)); + } + } + + /* + * Wait for all threads. The idea here is to maximize the contention. + */ + ck_barrier_centralized(&barrier, &sense, nthr); + + for (i = 0; i < ITERATIONS; i++) { + for (j = 0; j < size; j++) { + buffer = _context[context->previous].buffer; + while (CK_RING_DEQUEUE_SPMC(entry, + ring + context->previous, + buffer, &entry) == false); + + if (context->previous != (unsigned int)entry->tid) { + ck_error("[%u:%p] %u != %u\n", + context->tid, (void *)entry, + entry->tid, context->previous); + } + + if (entry->value < 0 || entry->value >= size) { + ck_error("[%u:%p] %u </> %u\n", + context->tid, (void *)entry, + entry->tid, context->previous); + } + + entry->tid = context->tid; + buffer = context->buffer; + + if (i & 1) { + r = CK_RING_ENQUEUE_SPMC(entry, + ring + context->tid, + buffer, &entry); + } else { + r = CK_RING_ENQUEUE_SPMC_SIZE(entry, + ring + context->tid, + buffer, &entry, &s); + + if ((int)s >= size) { + ck_error("Size %u out of range of %d\n", + s, size); + } + } + assert(r == true); + } + } + + return NULL; +} + +int +main(int argc, char *argv[]) +{ + int i, r; + unsigned long l; + pthread_t *thread; + struct entry *buffer; + + 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 >= 4 && (size & size - 1) == 0); + size -= 1; + + ring = malloc(sizeof(ck_ring_t) * nthr); + assert(ring); + + _context = malloc(sizeof(*_context) * nthr); + assert(_context); + + thread = malloc(sizeof(pthread_t) * nthr); + assert(thread); + + fprintf(stderr, "SPSC test:"); + for (i = 0; i < nthr; i++) { + _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; + } + + buffer = malloc(sizeof(struct entry) * (size + 1)); + assert(buffer); + memset(buffer, 0, sizeof(struct entry) * (size + 1)); + _context[i].buffer = buffer; + ck_ring_init(ring + i, size + 1); + r = pthread_create(thread + i, NULL, test, _context + i); + assert(r == 0); + } + + for (i = 0; i < nthr; i++) + pthread_join(thread[i], NULL); + + fprintf(stderr, " done\n"); + + fprintf(stderr, "SPMC test:\n"); + buffer = malloc(sizeof(ck_ring_buffer_t) * (size + 1)); + assert(buffer); + memset(buffer, 0, sizeof(void *) * (size + 1)); + ck_ring_init(&ring_spmc, size + 1); + for (i = 0; i < nthr - 1; i++) { + _context[i].buffer = buffer; + r = pthread_create(thread + i, NULL, test_spmc, _context + i); + assert(r == 0); + } + + for (l = 0; l < (unsigned long)size * ITERATIONS * (nthr - 1) ; l++) { + struct entry *entry = malloc(sizeof *entry); + + assert(entry != NULL); + entry->value_long = l; + entry->value = (int)l; + entry->tid = (int)l; + entry->magic = 0xdead; + entry->ref = 0; + + /* Wait until queue is not full. */ + if (l & 1) { + while (CK_RING_ENQUEUE_SPMC(entry, &ring_spmc, + buffer, entry) == false) { + ck_pr_stall(); + } + } else { + unsigned int s; + + while (CK_RING_ENQUEUE_SPMC_SIZE(entry, &ring_spmc, + buffer, entry, &s) == false) { + ck_pr_stall(); + } + + if ((int)s >= (size * ITERATIONS * (nthr - 1))) { + ck_error("MPMC: Unexpected size of %u\n", s); + } + } + } + + for (i = 0; i < nthr - 1; i++) + pthread_join(thread[i], NULL); + + return (0); +} +
