diff options
Diffstat (limited to 'regressions/ck_ht')
-rw-r--r-- | regressions/ck_ht/benchmark/Makefile | 27 | ||||
-rw-r--r-- | regressions/ck_ht/benchmark/parallel_bytestring.c | 559 | ||||
-rw-r--r-- | regressions/ck_ht/benchmark/parallel_direct.c | 545 | ||||
-rw-r--r-- | regressions/ck_ht/benchmark/serial.c | 387 | ||||
-rw-r--r-- | regressions/ck_ht/validate/Makefile | 21 | ||||
-rw-r--r-- | regressions/ck_ht/validate/serial.c | 309 |
6 files changed, 1848 insertions, 0 deletions
diff --git a/regressions/ck_ht/benchmark/Makefile b/regressions/ck_ht/benchmark/Makefile new file mode 100644 index 0000000..fa31274 --- /dev/null +++ b/regressions/ck_ht/benchmark/Makefile @@ -0,0 +1,27 @@ +.PHONY: clean distribution + +OBJECTS=serial serial.delete parallel_bytestring parallel_bytestring.delete parallel_direct + +all: $(OBJECTS) + +serial: serial.c ../../../include/ck_ht.h ../../../src/ck_ht.c + $(CC) $(CFLAGS) -o serial serial.c ../../../src/ck_ht.c + +serial.delete: serial.c ../../../include/ck_ht.h ../../../src/ck_ht.c + $(CC) $(CFLAGS) -DHT_DELETE -o serial.delete serial.c ../../../src/ck_ht.c + +parallel_bytestring.delete: parallel_bytestring.c ../../../include/ck_ht.h ../../../src/ck_ht.c ../../../src/ck_epoch.c + $(CC) $(PTHREAD_CFLAGS) $(CFLAGS) -DHT_DELETE -o parallel_bytestring.delete parallel_bytestring.c ../../../src/ck_ht.c ../../../src/ck_epoch.c + +parallel_bytestring: parallel_bytestring.c ../../../include/ck_ht.h ../../../src/ck_ht.c ../../../src/ck_epoch.c + $(CC) $(PTHREAD_CFLAGS) $(CFLAGS) -o parallel_bytestring parallel_bytestring.c ../../../src/ck_ht.c ../../../src/ck_epoch.c + +parallel_direct: parallel_direct.c ../../../include/ck_ht.h ../../../src/ck_ht.c ../../../src/ck_epoch.c + $(CC) $(PTHREAD_CFLAGS) $(CFLAGS) -o parallel_direct parallel_direct.c ../../../src/ck_ht.c ../../../src/ck_epoch.c + +clean: + rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe + +include ../../../build/regressions.build +CFLAGS+=-D_GNU_SOURCE + diff --git a/regressions/ck_ht/benchmark/parallel_bytestring.c b/regressions/ck_ht/benchmark/parallel_bytestring.c new file mode 100644 index 0000000..f3d3854 --- /dev/null +++ b/regressions/ck_ht/benchmark/parallel_bytestring.c @@ -0,0 +1,559 @@ +/* + * 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_ht.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> + +#include "../../common.h" + +static ck_ht_t ht CK_CC_CACHELINE; +static char **keys; +static size_t keys_length = 0; +static size_t keys_capacity = 128; +static ck_epoch_t epoch_ht; +static ck_epoch_record_t epoch_wr; +static int n_threads; +static bool next_stage; + +enum state { + HT_STATE_STOP = 0, + HT_STATE_GET, + HT_STATE_STRICT_REPLACEMENT, + HT_STATE_DELETION, + HT_STATE_REPLACEMENT, + HT_STATE_COUNT +}; + +static struct affinity affinerator = AFFINITY_INITIALIZER; +static uint64_t accumulator[HT_STATE_COUNT]; +static ck_spinlock_t accumulator_mutex = CK_SPINLOCK_INITIALIZER; +static int barrier[HT_STATE_COUNT]; +static int state; + +struct ht_epoch { + ck_epoch_entry_t epoch_entry; +}; + +COMMON_ALARM_DECLARE_GLOBAL(ht_alarm, alarm_event, next_stage) + +static void +alarm_handler(int s) +{ + + (void)s; + next_stage = true; + return; +} + +static void +ht_destroy(ck_epoch_entry_t *e) +{ + + free(e); + return; +} + +static void * +ht_malloc(size_t r) +{ + ck_epoch_entry_t *b; + + b = malloc(sizeof(*b) + r); + return b + 1; +} + +static void +ht_free(void *p, size_t b, bool r) +{ + struct ht_epoch *e = p; + + (void)b; + + if (r == true) { + /* Destruction requires safe memory reclamation. */ + ck_epoch_call(&epoch_wr, &(--e)->epoch_entry, ht_destroy); + } else { + free(--e); + } + + return; +} + +static struct ck_malloc my_allocator = { + .malloc = ht_malloc, + .free = ht_free +}; + +static void +table_init(void) +{ + unsigned int mode = CK_HT_MODE_BYTESTRING; + +#ifdef HT_DELETE + mode |= CK_HT_WORKLOAD_DELETE; +#endif + + ck_epoch_init(&epoch_ht); + ck_epoch_register(&epoch_ht, &epoch_wr); + common_srand48((long int)time(NULL)); + if (ck_ht_init(&ht, mode, NULL, &my_allocator, 8, common_lrand48()) == false) { + perror("ck_ht_init"); + exit(EXIT_FAILURE); + } + + return; +} + +static bool +table_remove(const char *value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + size_t l = strlen(value); + + ck_ht_hash(&h, &ht, value, l); + ck_ht_entry_key_set(&entry, value, l); + return ck_ht_remove_spmc(&ht, h, &entry); +} + +static bool +table_replace(const char *value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + size_t l = strlen(value); + + ck_ht_hash(&h, &ht, value, l); + ck_ht_entry_set(&entry, h, value, l, "REPLACED"); + return ck_ht_set_spmc(&ht, h, &entry); +} + +static void * +table_get(const char *value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + size_t l = strlen(value); + + ck_ht_hash(&h, &ht, value, l); + ck_ht_entry_key_set(&entry, value, l); + if (ck_ht_get_spmc(&ht, h, &entry) == true) + return ck_ht_entry_value(&entry); + + return NULL; +} + +static bool +table_insert(const char *value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + size_t l = strlen(value); + + ck_ht_hash(&h, &ht, value, l); + ck_ht_entry_set(&entry, h, value, l, value); + return ck_ht_put_spmc(&ht, h, &entry); +} + +static size_t +table_count(void) +{ + + return ck_ht_count(&ht); +} + +static bool +table_reset(void) +{ + + return ck_ht_reset_spmc(&ht); +} + +static void * +reader(void *unused) +{ + size_t i; + ck_epoch_record_t epoch_record; + int state_previous = HT_STATE_STOP; + int n_state; + 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_ht, &epoch_record); + for (;;) { + j++; + ck_epoch_begin(&epoch_record, NULL); + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + char *r; + + r = table_get(keys[i]); + if (r == NULL) + continue; + + if (strcmp(r, "REPLACED") == 0) + continue; + + if (strcmp(r, keys[i]) == 0) + continue; + + ck_error("ERROR: Found invalid value: [%s] but expected [%s]\n", r, keys[i]); + } + a += rdtsc() - s; + ck_epoch_end(&epoch_record, NULL); + + n_state = ck_pr_load_int(&state); + if (n_state != state_previous) { + ck_spinlock_lock(&accumulator_mutex); + accumulator[state_previous] += a / (j * keys_length); + ck_spinlock_unlock(&accumulator_mutex); + 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; +} + +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(ht_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(ht_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; + + table_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 += table_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", + table_count(), d); + + fprintf(stderr, " ,- BASIC TEST\n"); + fprintf(stderr, " | Executing SMR test..."); + a = 0; + for (j = 0; j < r; j++) { + if (table_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += table_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++) + table_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 (table_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++) + table_remove(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + table_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++) { + table_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_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, HT_STATE_GET); + while (ck_pr_load_int(&barrier[HT_STATE_STOP]) != n_threads) + ck_pr_stall(); + ck_pr_inc_int(&barrier[HT_STATE_STOP]); + common_sleep(r); + ck_pr_store_int(&state, HT_STATE_STRICT_REPLACEMENT); + while (ck_pr_load_int(&barrier[HT_STATE_GET]) != n_threads) + ck_pr_stall(); + fprintf(stderr, "done (reader = %" PRIu64 " ticks)\n", + accumulator[HT_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[HT_STATE_GET]); + for (;;) { + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) + table_replace(keys[i]); + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + + ck_pr_store_int(&state, HT_STATE_DELETION); + while (ck_pr_load_int(&barrier[HT_STATE_STRICT_REPLACEMENT]) != n_threads) + ck_pr_stall(); + table_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), accumulator[HT_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[HT_STATE_STRICT_REPLACEMENT]); + for (;;) { + double delete; + + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + table_insert(keys[i]); + if (p_d != 0.0) { + delete = common_drand48(); + if (delete <= p_d) + table_remove(keys[i]); + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + ck_pr_store_int(&state, HT_STATE_REPLACEMENT); + while (ck_pr_load_int(&barrier[HT_STATE_DELETION]) != n_threads) + ck_pr_stall(); + + table_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), accumulator[HT_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[HT_STATE_DELETION]); + for (;;) { + double replace, delete; + + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + table_insert(keys[i]); + if (p_d != 0.0) { + delete = common_drand48(); + if (delete <= p_d) + table_remove(keys[i]); + } + if (p_r != 0.0) { + replace = common_drand48(); + if (replace <= p_r) + table_replace(keys[i]); + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + ck_pr_store_int(&state, HT_STATE_STOP); + while (ck_pr_load_int(&barrier[HT_STATE_REPLACEMENT]) != n_threads) + ck_pr_stall(); + table_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), accumulator[HT_STATE_REPLACEMENT] / n_threads); + + ck_pr_inc_int(&barrier[HT_STATE_REPLACEMENT]); + epoch_temporary = epoch_wr; + ck_epoch_synchronize(&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; +} diff --git a/regressions/ck_ht/benchmark/parallel_direct.c b/regressions/ck_ht/benchmark/parallel_direct.c new file mode 100644 index 0000000..195bb25 --- /dev/null +++ b/regressions/ck_ht/benchmark/parallel_direct.c @@ -0,0 +1,545 @@ +/* + * 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_ht.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> + +#include "../../common.h" + +static ck_ht_t ht CK_CC_CACHELINE; +static uintptr_t *keys; +static size_t keys_length = 0; +static ck_epoch_t epoch_ht; +static ck_epoch_record_t epoch_wr; +static int n_threads; +static bool next_stage; + +enum state { + HT_STATE_STOP = 0, + HT_STATE_GET, + HT_STATE_STRICT_REPLACEMENT, + HT_STATE_DELETION, + HT_STATE_REPLACEMENT, + HT_STATE_COUNT +}; + +static struct affinity affinerator = AFFINITY_INITIALIZER; +static uint64_t accumulator[HT_STATE_COUNT]; +static ck_spinlock_t accumulator_mutex = CK_SPINLOCK_INITIALIZER; +static int barrier[HT_STATE_COUNT]; +static int state; + +struct ht_epoch { + ck_epoch_entry_t epoch_entry; +}; + +COMMON_ALARM_DECLARE_GLOBAL(ht_alarm, alarm_event, next_stage) + +static void +alarm_handler(int s) +{ + + (void)s; + next_stage = true; + return; +} + +static void +ht_destroy(ck_epoch_entry_t *e) +{ + + free(e); + return; +} + +static void * +ht_malloc(size_t r) +{ + ck_epoch_entry_t *b; + + b = malloc(sizeof(*b) + r); + return b + 1; +} + +static void +ht_free(void *p, size_t b, bool r) +{ + struct ht_epoch *e = p; + + (void)b; + + if (r == true) { + /* Destruction requires safe memory reclamation. */ + ck_epoch_call(&epoch_wr, &(--e)->epoch_entry, ht_destroy); + } else { + free(--e); + } + + return; +} + +static struct ck_malloc my_allocator = { + .malloc = ht_malloc, + .free = ht_free +}; + +static void +hash_function(ck_ht_hash_t *h, const void *key, size_t key_length, uint64_t seed) +{ + const uintptr_t *value = key; + + (void)key_length; + (void)seed; + h->value = *value; + return; +} + +static void +table_init(void) +{ + + ck_epoch_init(&epoch_ht); + ck_epoch_register(&epoch_ht, &epoch_wr); + common_srand48((long int)time(NULL)); + if (ck_ht_init(&ht, CK_HT_MODE_DIRECT, hash_function, &my_allocator, 8, common_lrand48()) == false) { + perror("ck_ht_init"); + exit(EXIT_FAILURE); + } + + return; +} + +static bool +table_remove(uintptr_t value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + + ck_ht_hash_direct(&h, &ht, value); + ck_ht_entry_key_set_direct(&entry, value); + return ck_ht_remove_spmc(&ht, h, &entry); +} + +static bool +table_replace(uintptr_t value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + + ck_ht_hash_direct(&h, &ht, value); + ck_ht_entry_set_direct(&entry, h, value, 6605241); + return ck_ht_set_spmc(&ht, h, &entry); +} + +static uintptr_t +table_get(uintptr_t value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + + ck_ht_hash_direct(&h, &ht, value); + ck_ht_entry_key_set_direct(&entry, value); + if (ck_ht_get_spmc(&ht, h, &entry) == true) + return ck_ht_entry_value_direct(&entry); + + return 0; +} + +static bool +table_insert(uintptr_t value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + + ck_ht_hash_direct(&h, &ht, value); + ck_ht_entry_set_direct(&entry, h, value, value); + return ck_ht_put_spmc(&ht, h, &entry); +} + +static size_t +table_count(void) +{ + + return ck_ht_count(&ht); +} + +static bool +table_reset(void) +{ + + return ck_ht_reset_spmc(&ht); +} + +static void * +ht_reader(void *unused) +{ + size_t i; + ck_epoch_record_t epoch_record; + int state_previous = HT_STATE_STOP; + int n_state; + 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_ht, &epoch_record); + for (;;) { + j++; + ck_epoch_begin(&epoch_record, NULL); + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + uintptr_t r; + + r = table_get(keys[i]); + if (r == 0) + continue; + + if (r == 6605241) + continue; + + if (r == keys[i]) + continue; + + ck_error("ERROR: Found invalid value: [%ju]\n", + (uintmax_t)r); + } + a += rdtsc() - s; + ck_epoch_end(&epoch_record, NULL); + + n_state = ck_pr_load_int(&state); + if (n_state != state_previous) { + ck_spinlock_lock(&accumulator_mutex); + accumulator[state_previous] += a / (j * keys_length); + ck_spinlock_unlock(&accumulator_mutex); + 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; +} + +int +main(int argc, char *argv[]) +{ + size_t i, j, r; + unsigned int d = 0; + uint64_t s, e, a, repeated; + pthread_t *readers; + double p_r, p_d; + + COMMON_ALARM_DECLARE_LOCAL(ht_alarm, alarm_event) + + r = 20; + s = 8; + p_d = 0.5; + p_r = 0.5; + n_threads = CORES - 1; + + if (argc < 2) { + fprintf(stderr, "Usage: parallel <#entries> [<interval length> <initial size> <readers>\n" + " <probability of replacement> <probability of deletion> <epoch threshold>]\n"); + exit(EXIT_FAILURE); + } + + 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(ht_alarm, alarm_event, r) + + affinerator.delta = 1; + readers = malloc(sizeof(pthread_t) * n_threads); + assert(readers != NULL); + + keys_length = (size_t)atoi(argv[1]); + keys = malloc(sizeof(uintptr_t) * keys_length); + assert(keys != NULL); + + table_init(); + + for (i = 0; i < keys_length; i++) { + keys[i] = (uintptr_t)common_lrand48(); + while (keys[i] == 2) + keys[i] = (uintptr_t)common_lrand48(); + } + + for (i = 0; i < (size_t)n_threads; i++) { + if (pthread_create(&readers[i], NULL, ht_reader, NULL) != 0) { + ck_error("ERROR: Failed to create thread %zu.\n", i); + } + } + + for (i = 0; i < keys_length; i++) + d += table_insert(keys[i]) == false; + + fprintf(stderr, " [S] %zu entries stored and %u duplicates.\n\n", + table_count(), d); + + fprintf(stderr, " ,- BASIC TEST\n"); + fprintf(stderr, " | Executing SMR test..."); + a = 0; + for (j = 0; j < r; j++) { + if (table_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += table_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++) + table_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 (table_get(keys[i]) == 0) { + ck_error("ERROR: Unexpected 0 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++) + table_remove(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + table_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++) { + table_get(2); + } + 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_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, HT_STATE_GET); + while (ck_pr_load_int(&barrier[HT_STATE_STOP]) != n_threads) + ck_pr_stall(); + ck_pr_inc_int(&barrier[HT_STATE_STOP]); + common_sleep(r); + ck_pr_store_int(&state, HT_STATE_STRICT_REPLACEMENT); + while (ck_pr_load_int(&barrier[HT_STATE_GET]) != n_threads) + ck_pr_stall(); + fprintf(stderr, "done (reader = %" PRIu64 " ticks)\n", + accumulator[HT_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[HT_STATE_GET]); + for (;;) { + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) + table_replace(keys[i]); + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + + ck_pr_store_int(&state, HT_STATE_DELETION); + while (ck_pr_load_int(&barrier[HT_STATE_STRICT_REPLACEMENT]) != n_threads) + ck_pr_stall(); + table_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), accumulator[HT_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[HT_STATE_STRICT_REPLACEMENT]); + for (;;) { + double delete; + + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + table_insert(keys[i]); + if (p_d != 0.0) { + delete = common_drand48(); + if (delete <= p_d) + table_remove(keys[i]); + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + ck_pr_store_int(&state, HT_STATE_REPLACEMENT); + while (ck_pr_load_int(&barrier[HT_STATE_DELETION]) != n_threads) + ck_pr_stall(); + + table_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), accumulator[HT_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[HT_STATE_DELETION]); + for (;;) { + double replace, delete; + + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + table_insert(keys[i]); + if (p_d != 0.0) { + delete = common_drand48(); + if (delete <= p_d) + table_remove(keys[i]); + } + if (p_r != 0.0) { + replace = common_drand48(); + if (replace <= p_r) + table_replace(keys[i]); + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + ck_pr_store_int(&state, HT_STATE_STOP); + while (ck_pr_load_int(&barrier[HT_STATE_REPLACEMENT]) != n_threads) + ck_pr_stall(); + table_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), accumulator[HT_STATE_REPLACEMENT] / n_threads); + + ck_pr_inc_int(&barrier[HT_STATE_REPLACEMENT]); + epoch_temporary = epoch_wr; + ck_epoch_synchronize(&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; +} diff --git a/regressions/ck_ht/benchmark/serial.c b/regressions/ck_ht/benchmark/serial.c new file mode 100644 index 0000000..0daa45c --- /dev/null +++ b/regressions/ck_ht/benchmark/serial.c @@ -0,0 +1,387 @@ +/* + * 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_ht.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" + +static ck_ht_t ht; +static char **keys; +static size_t keys_length = 0; +static size_t keys_capacity = 128; + +static void * +ht_malloc(size_t r) +{ + + return malloc(r); +} + +static void +ht_free(void *p, size_t b, bool r) +{ + + (void)b; + (void)r; + + free(p); + + return; +} + +static struct ck_malloc my_allocator = { + .malloc = ht_malloc, + .free = ht_free +}; + +static void +table_init(void) +{ + unsigned int mode = CK_HT_MODE_BYTESTRING; + +#ifdef HT_DELETE + mode |= CK_HT_WORKLOAD_DELETE; +#endif + + common_srand48((long int)time(NULL)); + if (ck_ht_init(&ht, mode, NULL, &my_allocator, 8, common_lrand48()) == false) { + perror("ck_ht_init"); + exit(EXIT_FAILURE); + } + + return; +} + +static bool +table_remove(const char *value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + size_t l = strlen(value); + + ck_ht_hash(&h, &ht, value, l); + ck_ht_entry_key_set(&entry, value, l); + return ck_ht_remove_spmc(&ht, h, &entry); +} + +static bool +table_replace(const char *value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + size_t l = strlen(value); + + ck_ht_hash(&h, &ht, value, l); + ck_ht_entry_set(&entry, h, value, l, "REPLACED"); + return ck_ht_set_spmc(&ht, h, &entry); +} + +static void * +table_get(const char *value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + size_t l = strlen(value); + void *v = NULL; + + ck_ht_hash(&h, &ht, value, l); + ck_ht_entry_key_set(&entry, value, l); + + if (ck_ht_get_spmc(&ht, h, &entry) == true) { + v = ck_ht_entry_value(&entry); + } + return v; +} + +static bool +table_insert(const char *value) +{ + ck_ht_entry_t entry; + ck_ht_hash_t h; + size_t l = strlen(value); + + ck_ht_hash(&h, &ht, value, l); + ck_ht_entry_set(&entry, h, value, l, "VALUE"); + return ck_ht_put_spmc(&ht, h, &entry); +} + +static size_t +table_count(void) +{ + + return ck_ht_count(&ht); +} + +static bool +table_gc(void) +{ + + return ck_ht_gc(&ht, 0, common_lrand48()); +} + +static bool +table_reset(void) +{ + + return ck_ht_reset_spmc(&ht); +} + +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; +} + +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, ri, si, ai, sr, rg, sg, ag, sd, ng, gg; + char **t; + struct ck_ht_stat st; + + r = 20; + s = 8; + srand(time(NULL)); + + if (argc < 2) { + ck_error("Usage: ck_ht <dictionary> [<repetitions> <initial size>]\n"); + } + + if (argc >= 3) + r = atoi(argv[2]); + + if (argc >= 4) + s = (uint64_t)atoi(argv[3]); + + 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; + + table_init(); + + for (i = 0; i < keys_length; i++) + d += table_insert(keys[i]) == false; + ck_ht_stat(&ht, &st); + + fprintf(stderr, "# %zu entries stored, %u duplicates, %" PRIu64 " probe.\n", + table_count(), d, st.probe_maximum); + + fprintf(stderr, "# reverse_insertion serial_insertion random_insertion serial_replace reverse_get serial_get random_get serial_remove negative_get garbage_collect\n\n"); + + a = 0; + for (j = 0; j < r; j++) { + if (table_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = keys_length; i > 0; i--) + d += table_insert(keys[i - 1]) == false; + e = rdtsc(); + a += e - s; + } + ri = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + if (table_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += table_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 (table_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += table_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++) + table_replace(keys[i]); + e = rdtsc(); + a += e - s; + } + sr = a / (r * keys_length); + + table_reset(); + for (i = 0; i < keys_length; i++) + table_insert(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = keys_length; i > 0; i--) { + if (table_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 (table_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 (table_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++) + table_remove(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + table_insert(keys[i]); + } + sd = a / (r * keys_length); + + for (i = 0; i < keys_length / 2; i++) + table_remove(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + table_gc(); + e = rdtsc(); + a += e - s; + } + gg = a / r; + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + table_get("\x50\x03\x04\x05\x06\x10"); + } + e = rdtsc(); + a += e - s; + } + ng = a / (r * keys_length); + + printf("%zu " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 "\n", + keys_length, ri, si, ai, sr, rg, sg, ag, sd, ng, gg); + + return 0; +} diff --git a/regressions/ck_ht/validate/Makefile b/regressions/ck_ht/validate/Makefile new file mode 100644 index 0000000..cb5682c --- /dev/null +++ b/regressions/ck_ht/validate/Makefile @@ -0,0 +1,21 @@ +.PHONY: check clean distribution + +OBJECTS=serial serial.delete + +all: $(OBJECTS) + +serial: serial.c ../../../include/ck_ht.h ../../../src/ck_ht.c + $(CC) $(CFLAGS) -o serial serial.c ../../../src/ck_ht.c + +serial.delete: serial.c ../../../include/ck_ht.h ../../../src/ck_ht.c + $(CC) $(CFLAGS) -DHT_DELETE -o serial.delete serial.c ../../../src/ck_ht.c + +check: all + ./serial + ./serial.delete + +clean: + rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe + +include ../../../build/regressions.build +CFLAGS+=-D_GNU_SOURCE diff --git a/regressions/ck_ht/validate/serial.c b/regressions/ck_ht/validate/serial.c new file mode 100644 index 0000000..9a85c2f --- /dev/null +++ b/regressions/ck_ht/validate/serial.c @@ -0,0 +1,309 @@ +/* + * 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_ht.h> + +#include <assert.h> +#include <ck_malloc.h> +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include "../../common.h" +#include "../../../src/ck_ht_hash.h" + +static size_t hash_times_called = 0; + +static void * +ht_malloc(size_t r) +{ + + return malloc(r); +} + +static void +ht_free(void *p, size_t b, bool r) +{ + + (void)b; + (void)r; + free(p); + return; +} + +static void +ht_hash_wrapper(struct ck_ht_hash *h, + const void *key, + size_t length, + uint64_t seed) +{ + hash_times_called++; + + h->value = (unsigned long)MurmurHash64A(key, length, seed); + return; +} + +static struct ck_malloc my_allocator = { + .malloc = ht_malloc, + .free = ht_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"}; + +static uintptr_t direct[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 1, 2, 3, 4, 5, 9 }; + +const char *negative = "negative"; + +int +main(void) +{ + size_t i, l; + ck_ht_t ht; + ck_ht_entry_t entry; + ck_ht_hash_t h; + ck_ht_iterator_t iterator = CK_HT_ITERATOR_INITIALIZER; + ck_ht_entry_t *cursor; + unsigned int mode = CK_HT_MODE_BYTESTRING; + +#ifdef HT_DELETE + mode |= CK_HT_WORKLOAD_DELETE; +#endif + + if (ck_ht_init(&ht, mode, ht_hash_wrapper, &my_allocator, 2, 6602834) == false) { + perror("ck_ht_init"); + exit(EXIT_FAILURE); + } + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + l = strlen(test[i]); + ck_ht_hash(&h, &ht, test[i], l); + ck_ht_entry_set(&entry, h, test[i], l, test[i]); + ck_ht_put_spmc(&ht, h, &entry); + } + + l = strlen(test[0]); + ck_ht_hash(&h, &ht, test[0], l); + ck_ht_entry_set(&entry, h, test[0], l, test[0]); + ck_ht_put_spmc(&ht, h, &entry); + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + l = strlen(test[i]); + ck_ht_hash(&h, &ht, test[i], l); + ck_ht_entry_key_set(&entry, test[i], l); + if (ck_ht_get_spmc(&ht, h, &entry) == false) { + ck_error("ERROR (put): Failed to find [%s]\n", test[i]); + } else { + void *k, *v; + + k = ck_ht_entry_key(&entry); + v = ck_ht_entry_value(&entry); + + if (strcmp(k, test[i]) || strcmp(v, test[i])) { + ck_error("ERROR: Mismatch: (%s, %s) != (%s, %s)\n", + (char *)k, (char *)v, test[i], test[i]); + } + } + } + + ck_ht_hash(&h, &ht, negative, strlen(negative)); + ck_ht_entry_key_set(&entry, negative, strlen(negative)); + if (ck_ht_get_spmc(&ht, h, &entry) == true) { + ck_error("ERROR: Found non-existing entry.\n"); + } + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + l = strlen(test[i]); + ck_ht_hash(&h, &ht, test[i], l); + ck_ht_entry_key_set(&entry, test[i], l); + + if (ck_ht_get_spmc(&ht, h, &entry) == false) + continue; + + if (ck_ht_remove_spmc(&ht, h, &entry) == false) { + ck_error("ERROR: Failed to delete existing entry\n"); + } + + if (ck_ht_get_spmc(&ht, h, &entry) == true) + ck_error("ERROR: Able to find [%s] after delete\n", test[i]); + + ck_ht_entry_set(&entry, h, test[i], l, test[i]); + if (ck_ht_put_spmc(&ht, h, &entry) == false) + ck_error("ERROR: Failed to insert [%s]\n", test[i]); + + if (ck_ht_remove_spmc(&ht, h, &entry) == false) { + ck_error("ERROR: Failed to delete existing entry\n"); + } + } + + ck_ht_reset_spmc(&ht); + if (ck_ht_count(&ht) != 0) { + ck_error("ERROR: Map was not reset.\n"); + } + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + l = strlen(test[i]); + ck_ht_hash(&h, &ht, test[i], l); + ck_ht_entry_set(&entry, h, test[i], l, test[i]); + ck_ht_put_spmc(&ht, h, &entry); + } + + for (i = 0; ck_ht_next(&ht, &iterator, &cursor) == true; i++); + if (i != 42) { + ck_error("ERROR: Incorrect number of entries in table.\n"); + } + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + l = strlen(test[i]); + ck_ht_hash(&h, &ht, test[i], l); + ck_ht_entry_set(&entry, h, test[i], l, test[i]); + ck_ht_set_spmc(&ht, h, &entry); + } + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + l = strlen(test[i]); + ck_ht_hash(&h, &ht, test[i], l); + ck_ht_entry_key_set(&entry, test[i], l); + if (ck_ht_get_spmc(&ht, h, &entry) == false) { + ck_error("ERROR (set): Failed to find [%s]\n", test[i]); + } else { + void *k, *v; + + k = ck_ht_entry_key(&entry); + v = ck_ht_entry_value(&entry); + + if (strcmp(k, test[i]) || strcmp(v, test[i])) { + ck_error("ERROR: Mismatch: (%s, %s) != (%s, %s)\n", + (char *)k, (char *)v, test[i], test[i]); + } + } + } + + if (ck_ht_gc(&ht, 0, 27) == false) { + ck_error("ck_ht_gc\n"); + } + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + l = strlen(test[i]); + ck_ht_hash(&h, &ht, test[i], l); + ck_ht_entry_set(&entry, h, test[i], l, "REPLACED"); + ck_ht_set_spmc(&ht, h, &entry); + + if (strcmp(test[i], "What") == 0) + continue; + + if (strcmp(test[i], "down.") == 0) + continue; + + if (strcmp(ck_ht_entry_value(&entry), test[i]) != 0) { + ck_error("Mismatch detected: %s, expected %s\n", + (char *)ck_ht_entry_value(&entry), + test[i]); + } + } + + ck_ht_iterator_init(&iterator); + while (ck_ht_next(&ht, &iterator, &cursor) == true) { + if (strcmp(ck_ht_entry_value(cursor), "REPLACED") != 0) { + ck_error("Mismatch detected: %s, expected REPLACED\n", + (char *)ck_ht_entry_value(cursor)); + } + } + + for (i = 0; i < sizeof(test) / sizeof(*test); i++) { + l = strlen(test[i]); + ck_ht_hash(&h, &ht, test[i], l); + ck_ht_entry_key_set(&entry, test[i], l); + + if (ck_ht_get_spmc(&ht, h, &entry) == false) + continue; + + if (ck_ht_remove_spmc(&ht, h, &entry) == false) { + ck_error("ERROR: Failed to delete existing entry\n"); + } + + if (ck_ht_get_spmc(&ht, h, &entry) == true) + ck_error("ERROR: Able to find [%s] after delete\n", test[i]); + + ck_ht_entry_set(&entry, h, test[i], l, test[i]); + if (ck_ht_put_spmc(&ht, h, &entry) == false) + ck_error("ERROR: Failed to insert [%s]\n", test[i]); + + if (ck_ht_remove_spmc(&ht, h, &entry) == false) { + ck_error("ERROR: Failed to delete existing entry\n"); + } + } + + ck_ht_destroy(&ht); + + if (hash_times_called == 0) { + ck_error("ERROR: Our hash function was not called!\n"); + } + + hash_times_called = 0; + + if (ck_ht_init(&ht, CK_HT_MODE_DIRECT, ht_hash_wrapper, &my_allocator, 8, 6602834) == false) { + perror("ck_ht_init"); + exit(EXIT_FAILURE); + } + + l = 0; + for (i = 0; i < sizeof(direct) / sizeof(*direct); i++) { + ck_ht_hash_direct(&h, &ht, direct[i]); + ck_ht_entry_set_direct(&entry, h, direct[i], (uintptr_t)test[i]); + l += ck_ht_put_spmc(&ht, h, &entry) == false; + } + + if (l != 7) { + ck_error("ERROR: Got %zu failures rather than 7\n", l); + } + + for (i = 0; i < sizeof(direct) / sizeof(*direct); i++) { + ck_ht_hash_direct(&h, &ht, direct[i]); + ck_ht_entry_set_direct(&entry, h, direct[i], (uintptr_t)"REPLACED"); + l += ck_ht_set_spmc(&ht, h, &entry) == false; + } + + ck_ht_iterator_init(&iterator); + while (ck_ht_next(&ht, &iterator, &cursor) == true) { + if (strcmp(ck_ht_entry_value(cursor), "REPLACED") != 0) { + ck_error("Mismatch detected: %s, expected REPLACED\n", + (char *)ck_ht_entry_value(cursor)); + } + } + + ck_ht_destroy(&ht); + + if (hash_times_called == 0) { + ck_error("ERROR: Our hash function was not called!\n"); + } + + return 0; +} |