diff options
Diffstat (limited to 'regressions/ck_hp/validate')
| -rw-r--r-- | regressions/ck_hp/validate/Makefile | 33 | ||||
| -rw-r--r-- | regressions/ck_hp/validate/ck_hp_fifo.c | 187 | ||||
| -rw-r--r-- | regressions/ck_hp/validate/ck_hp_fifo_donner.c | 213 | ||||
| -rw-r--r-- | regressions/ck_hp/validate/ck_hp_stack.c | 165 | ||||
| -rw-r--r-- | regressions/ck_hp/validate/nbds_haz_test.c | 226 | ||||
| -rw-r--r-- | regressions/ck_hp/validate/serial.c | 127 |
6 files changed, 951 insertions, 0 deletions
diff --git a/regressions/ck_hp/validate/Makefile b/regressions/ck_hp/validate/Makefile new file mode 100644 index 0000000..476b34f --- /dev/null +++ b/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 diff --git a/regressions/ck_hp/validate/ck_hp_fifo.c b/regressions/ck_hp/validate/ck_hp_fifo.c new file mode 100644 index 0000000..4454283 --- /dev/null +++ b/regressions/ck_hp/validate/ck_hp_fifo.c @@ -0,0 +1,187 @@ +/* + * Copyright 2011-2015 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); +} + diff --git a/regressions/ck_hp/validate/ck_hp_fifo_donner.c b/regressions/ck_hp/validate/ck_hp_fifo_donner.c new file mode 100644 index 0000000..1b52a37 --- /dev/null +++ b/regressions/ck_hp/validate/ck_hp_fifo_donner.c @@ -0,0 +1,213 @@ +/* + * Copyright 2012 Hendrik Donner + * Copyright 2012-2015 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; +} + diff --git a/regressions/ck_hp/validate/ck_hp_stack.c b/regressions/ck_hp/validate/ck_hp_stack.c new file mode 100644 index 0000000..ad9b927 --- /dev/null +++ b/regressions/ck_hp/validate/ck_hp_stack.c @@ -0,0 +1,165 @@ +/* + * Copyright 2010-2015 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); +} diff --git a/regressions/ck_hp/validate/nbds_haz_test.c b/regressions/ck_hp/validate/nbds_haz_test.c new file mode 100644 index 0000000..9b85e76 --- /dev/null +++ b/regressions/ck_hp/validate/nbds_haz_test.c @@ -0,0 +1,226 @@ +/* + * Copyright 2010-2015 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); + ck_pr_fence_store(); + + while (ck_pr_cas_ptr_value(&target->head, lstack, entry, &lstack) == false) { + ck_pr_store_ptr(&entry->next, lstack); + ck_pr_fence_store(); + 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_fence(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_fence(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); +} diff --git a/regressions/ck_hp/validate/serial.c b/regressions/ck_hp/validate/serial.c new file mode 100644 index 0000000..fd31581 --- /dev/null +++ b/regressions/ck_hp/validate/serial.c @@ -0,0 +1,127 @@ +/* + * Copyright 2010-2015 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; +} |