Repository: trafficserver Updated Branches: refs/heads/master f83d6f2d7 -> 0da17e968
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/regressions/ck_hs/benchmark/apply.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_hs/benchmark/apply.c b/lib/ck/regressions/ck_hs/benchmark/apply.c new file mode 100644 index 0000000..ca4a3da --- /dev/null +++ b/lib/ck/regressions/ck_hs/benchmark/apply.c @@ -0,0 +1,260 @@ +/* + * Copyright 2014 Samy Al Bahra. + * Copyright 2014 Backtrace I/O, Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above 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_hs.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_hs_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_hs_destroy(&hs); + return; +} + +static void +set_init(unsigned int size, unsigned int mode) +{ + + if (ck_hs_init(&hs, CK_HS_MODE_OBJECT | CK_HS_MODE_SPMC | mode, hs_hash, hs_compare, + &my_allocator, size, global_seed) == false) { + perror("ck_hs_init"); + exit(EXIT_FAILURE); + } + + return; +} + +static size_t +set_count(void) +{ + + return ck_hs_count(&hs); +} + +static bool +set_reset(void) +{ + + return ck_hs_reset(&hs); +} + +static void * +test_apply(void *key, void *closure) +{ + + (void)key; + + return closure; +} + +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, gp, agp; + struct ck_hs_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++) { + unsigned long h = CK_HS_HASH(&hs, hs_hash, keys[i]); + + if (ck_hs_get(&hs, h, keys[i]) == false) { + if (ck_hs_put(&hs, h, keys[i]) == false) + ck_error("ERROR: Failed get to put workload.\n"); + } else { + d++; + } + } + ck_hs_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 = 0; i < keys_length; i++) { + unsigned long h = CK_HS_HASH(&hs, hs_hash, keys[i]); + + if (ck_hs_get(&hs, h, keys[i]) == false && + ck_hs_put(&hs, h, keys[i]) == false) { + ck_error("ERROR: Failed get to put workload.\n"); + } + } + e = rdtsc(); + a += e - s; + } + gp = 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++) { + unsigned long h = CK_HS_HASH(&hs, hs_hash, keys[i]); + + if (ck_hs_apply(&hs, h, keys[i], test_apply, (void *)keys[i]) == false) + ck_error("ERROR: Failed in apply workload.\n"); + } + e = rdtsc(); + a += e - s; + } + agp = a / (r * keys_length); + + fclose(fp); + + for (i = 0; i < keys_length; i++) { + free(keys[i]); + } + + printf("Get to put: %" PRIu64 " ticks\n", gp); + printf(" Apply: %" PRIu64 " ticks\n", agp); + + 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_hs <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); + + printf("\n==============================================\n" + "Delete mode\n" + "==============================================\n"); + run_test(argv[1], r, size, CK_HS_MODE_DELETE); + return 0; +} + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/regressions/ck_hs/benchmark/parallel_bytestring.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_hs/benchmark/parallel_bytestring.c b/lib/ck/regressions/ck_hs/benchmark/parallel_bytestring.c index ea2eaec..e2e15c9 100644 --- a/lib/ck/regressions/ck_hs/benchmark/parallel_bytestring.c +++ b/lib/ck/regressions/ck_hs/benchmark/parallel_bytestring.c @@ -144,7 +144,7 @@ set_init(void) #ifdef HS_DELETE mode |= CK_HS_MODE_DELETE; -#endif +#endif ck_epoch_init(&epoch_hs); ck_epoch_register(&epoch_hs, &epoch_wr); http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/regressions/ck_hs/benchmark/serial.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_hs/benchmark/serial.c b/lib/ck/regressions/ck_hs/benchmark/serial.c index 995ef1c..ac4caff 100644 --- a/lib/ck/regressions/ck_hs/benchmark/serial.c +++ b/lib/ck/regressions/ck_hs/benchmark/serial.c @@ -133,7 +133,7 @@ set_replace(const char *value) h = CK_HS_HASH(&hs, hs_hash, value); ck_hs_set(&hs, h, value, &previous); - return previous != NULL; + return previous == value; } static void * http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/regressions/ck_hs/validate/serial.c ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_hs/validate/serial.c b/lib/ck/regressions/ck_hs/validate/serial.c index 93a375b..d6f6c0a 100644 --- a/lib/ck/regressions/ck_hs/validate/serial.c +++ b/lib/ck/regressions/ck_hs/validate/serial.c @@ -85,6 +85,49 @@ hs_compare(const void *previous, const void *compare) return strcmp(previous, compare) == 0; } +static void * +test_ip(void *key, void *closure) +{ + const char *a = key; + const char *b = closure; + + if (strcmp(a, b) != 0) + ck_error("Mismatch: %s != %s\n", a, b); + + return closure; +} + +static void * +test_negative(void *key, void *closure) +{ + + (void)closure; + if (key != NULL) + ck_error("ERROR: Apply callback expects NULL argument instead of [%s]\n", key); + + return NULL; +} + +static void * +test_unique(void *key, void *closure) +{ + + if (key != NULL) + ck_error("ERROR: Apply callback expects NULL argument instead of [%s]\n", key); + + return closure; +} + +static void * +test_remove(void *key, void *closure) +{ + + (void)key; + (void)closure; + + return NULL; +} + static void run_test(unsigned int is, unsigned int ad) { @@ -104,11 +147,22 @@ run_test(unsigned int is, unsigned int ad) continue; } - if (ck_hs_put_unique(&hs[j], h, test[i]) == false) - ck_error("ERROR [%zu]: Failed to insert unique (%s)\n", j, test[i]); + if (i & 1) { + if (ck_hs_put_unique(&hs[j], h, test[i]) == false) + ck_error("ERROR [%zu]: Failed to insert unique (%s)\n", j, test[i]); + } else if (ck_hs_apply(&hs[j], h, test[i], test_unique, (char *)test[i]) == false) { + ck_error("ERROR: Failed to apply for insertion.\n"); + } + + if (i & 1) { + if (ck_hs_remove(&hs[j], h, test[i]) == false) + ck_error("ERROR [%zu]: Failed to remove unique (%s)\n", j, test[i]); + } else if (ck_hs_apply(&hs[j], h, test[i], test_remove, NULL) == false) { + ck_error("ERROR: Failed to remove apply.\n"); + } - if (ck_hs_remove(&hs[j], h, test[i]) == false) - ck_error("ERROR [%zu]: Failed to remove unique (%s)\n", j, test[i]); + if (ck_hs_apply(&hs[j], h, test[i], test_negative, (char *)test[i]) == false) + ck_error("ERROR: Failed to apply.\n"); break; } @@ -214,8 +268,16 @@ run_test(unsigned int is, unsigned int ad) } if (strcmp(r, test[i]) != 0) { - ck_error("ERROR [%u]: Invalid &hs[j]: %s != %s\n", (char *)r, test[i], is); + ck_error("ERROR [%u]: Invalid &hs[j]: %s != %s\n", is, test[i], (char *)r); } + + /* Attempt in-place mutation. */ + if (ck_hs_apply(&hs[j], h, test[i], test_ip, (void *)test[i]) == false) + ck_error("ERROR [%u]: Failed to apply: %s != %s\n", is, (char *)r, test[i]); + + d = ck_hs_get(&hs[j], h, test[i]) != NULL; + if (d == false) + ck_error("ERROR [%u]: Expected [%s] to exist.\n", is, test[i]); } if (j == size - 1) http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/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 index 1dc4db1..d11b4e4 100644 --- a/lib/ck/regressions/ck_rhs/validate/serial.c +++ b/lib/ck/regressions/ck_rhs/validate/serial.c @@ -85,6 +85,49 @@ hs_compare(const void *previous, const void *compare) return strcmp(previous, compare) == 0; } +static void * +test_ip(void *key, void *closure) +{ + const char *a = key; + const char *b = closure; + + if (strcmp(a, b) != 0) + ck_error("Mismatch: %s != %s\n", a, b); + + return closure; +} + +static void * +test_negative(void *key, void *closure) +{ + + (void)closure; + if (key != NULL) + ck_error("ERROR: Apply callback expects NULL argument instead of [%s]\n", key); + + return NULL; +} + +static void * +test_unique(void *key, void *closure) +{ + + if (key != NULL) + ck_error("ERROR: Apply callback expects NULL argument instead of [%s]\n", key); + + return closure; +} + +static void * +test_remove(void *key, void *closure) +{ + + (void)key; + (void)closure; + + return NULL; +} + static void run_test(unsigned int is, unsigned int ad) { @@ -104,11 +147,22 @@ run_test(unsigned int is, unsigned int ad) 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 (i & 1) { + if (ck_rhs_put_unique(&hs[j], h, test[i]) == false) + ck_error("ERROR [%zu]: Failed to insert unique (%s)\n", j, test[i]); + } else if (ck_rhs_apply(&hs[j], h, test[i], test_unique, (char *)test[i]) == false) { + ck_error("ERROR: Failed to apply for insertion.\n"); + } - if (ck_rhs_remove(&hs[j], h, test[i]) == false) - ck_error("ERROR [%zu]: Failed to remove unique (%s)\n", j, test[i]); + if (i & 1) { + if (ck_rhs_remove(&hs[j], h, test[i]) == false) + ck_error("ERROR [%zu]: Failed to remove unique (%s)\n", j, test[i]); + } else if (ck_rhs_apply(&hs[j], h, test[i], test_remove, NULL) == false) { + ck_error("ERROR: Failed to remove apply.\n"); + } + + if (ck_rhs_apply(&hs[j], h, test[i], test_negative, (char *)test[i]) == false) + ck_error("ERROR: Failed to apply.\n"); break; } @@ -213,6 +267,13 @@ run_test(unsigned int is, unsigned int ad) if (strcmp(r, test[i]) != 0) { ck_error("ERROR [%u]: Invalid &hs[j]: %s != %s\n", (char *)r, test[i], is); } + /* Attempt in-place mutation. */ + if (ck_rhs_apply(&hs[j], h, test[i], test_ip, (void *)test[i]) == false) + ck_error("ERROR [%u]: Failed to apply: %s != %s\n", is, (char *)r, test[i]); + + d = ck_rhs_get(&hs[j], h, test[i]) != NULL; + if (d == false) + ck_error("ERROR [%u]: Expected [%s] to exist.\n", is, test[i]); } if (j == size - 1) http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/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 index 8c00d80..d8beb77 100644 --- a/lib/ck/regressions/ck_ring/validate/Makefile +++ b/lib/ck/regressions/ck_ring/validate/Makefile @@ -2,7 +2,6 @@ OBJECTS=ck_ring_spsc ck_ring_spmc ck_ring_spmc_template SIZE=16384 -CFLAGS += -g2 all: $(OBJECTS) @@ -15,11 +14,11 @@ ck_ring_spsc: ck_ring_spsc.c ../../../include/ck_ring.h ../../../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 \ + $(CC) $(CFLAGS) -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 \ + $(CC) $(CFLAGS) -o ck_ring_spmc_template ck_ring_spmc_template.c \ ../../../src/ck_barrier_centralized.c clean: http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/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 index 23fe0fa..9563a8f 100644 --- a/lib/ck/regressions/ck_ring/validate/ck_ring_spmc.c +++ b/lib/ck/regressions/ck_ring/validate/ck_ring_spmc.c @@ -197,7 +197,7 @@ test(void *c) 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, + while (ck_ring_dequeue_spmc(ring + context->previous, buffer, &entry) == false); if (context->previous != (unsigned int)entry->tid) { @@ -315,7 +315,7 @@ main(int argc, char *argv[]) /* Wait until queue is not full. */ if (l & 1) { while (ck_ring_enqueue_spmc(&ring_spmc, - buffer, + buffer, entry) == false) ck_pr_stall(); } else { http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/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 index 9facbc7..8840653 100644 --- a/lib/ck/regressions/ck_ring/validate/ck_ring_spmc_template.c +++ b/lib/ck/regressions/ck_ring/validate/ck_ring_spmc_template.c @@ -43,7 +43,7 @@ struct context { unsigned int tid; unsigned int previous; unsigned int next; - struct entry *buffer; + struct entry **buffer; }; struct entry { @@ -54,7 +54,7 @@ struct entry { int value; }; -CK_RING_PROTOTYPE(entry, entry) +CK_RING_PROTOTYPE(entry, entry *) static int nthr; static ck_ring_t *ring; @@ -73,7 +73,7 @@ test_spmc(void *c) unsigned int seed; int i, k, j, tid; struct context *context = c; - struct entry *buffer; + struct entry **buffer; buffer = context->buffer; if (aff_iterate(&a)) { @@ -136,11 +136,11 @@ static void * test(void *c) { struct context *context = c; - struct entry entry; + struct entry *entry; unsigned int s; int i, j; bool r; - ck_ring_buffer_t *buffer = context->buffer; + struct entry **buffer = context->buffer; ck_barrier_centralized_state_t sense = CK_BARRIER_CENTRALIZED_STATE_INITIALIZER; @@ -150,9 +150,9 @@ test(void *c) } if (context->tid == 0) { - struct entry *entries; + struct entry **entries; - entries = malloc(sizeof(struct entry) * size); + entries = malloc(sizeof(struct entry *) * size); assert(entries != NULL); if (ck_ring_size(ring) != 0) { @@ -161,15 +161,18 @@ test(void *c) } for (i = 0; i < size; i++) { - entries[i].value = i; - entries[i].tid = 0; + entries[i] = malloc(sizeof(struct entry)); + assert(entries[i] != NULL); + + entries[i]->value = i; + entries[i]->tid = 0; if (i & 1) { r = CK_RING_ENQUEUE_SPMC(entry, ring, buffer, - entries + i); + &entries[i]); } else { r = CK_RING_ENQUEUE_SPMC_SIZE(entry, ring, - buffer, entries + i, &s); + buffer, &entries[i], &s); if ((int)s != i) { ck_error("Size is %u, expected %d.\n", @@ -200,7 +203,7 @@ test(void *c) for (j = 0; j < size; j++) { buffer = _context[context->previous].buffer; while (CK_RING_DEQUEUE_SPMC(entry, - ring + context->previous, + ring + context->previous, buffer, &entry) == false); if (context->previous != (unsigned int)entry->tid) { @@ -245,7 +248,7 @@ main(int argc, char *argv[]) int i, r; unsigned long l; pthread_t *thread; - struct entry *buffer; + struct entry **buffer; if (argc != 4) { ck_error("Usage: validate <threads> <affinity delta> <size>\n"); @@ -284,9 +287,9 @@ main(int argc, char *argv[]) _context[i].previous = i - 1; } - buffer = malloc(sizeof(struct entry) * (size + 1)); + buffer = malloc(sizeof(struct entry *) * (size + 1)); assert(buffer); - memset(buffer, 0, sizeof(struct entry) * (size + 1)); + 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); @@ -299,9 +302,9 @@ main(int argc, char *argv[]) fprintf(stderr, " done\n"); fprintf(stderr, "SPMC test:\n"); - buffer = malloc(sizeof(ck_ring_buffer_t) * (size + 1)); + buffer = malloc(sizeof(struct entry *) * (size + 1)); assert(buffer); - memset(buffer, 0, sizeof(void *) * (size + 1)); + memset(buffer, 0, sizeof(struct entry *) * (size + 1)); ck_ring_init(&ring_spmc, size + 1); for (i = 0; i < nthr - 1; i++) { _context[i].buffer = buffer; @@ -322,14 +325,14 @@ main(int argc, char *argv[]) /* Wait until queue is not full. */ if (l & 1) { while (CK_RING_ENQUEUE_SPMC(entry, &ring_spmc, - buffer, entry) == false) { + buffer, &entry) == false) { ck_pr_stall(); } } else { unsigned int s; while (CK_RING_ENQUEUE_SPMC_SIZE(entry, &ring_spmc, - buffer, entry, &s) == false) { + buffer, &entry, &s) == false) { ck_pr_stall(); } @@ -342,6 +345,6 @@ main(int argc, char *argv[]) for (i = 0; i < nthr - 1; i++) pthread_join(thread[i], NULL); - return (0); + return 0; } http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/regressions/ck_spinlock/validate/Makefile ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/ck_spinlock/validate/Makefile b/lib/ck/regressions/ck_spinlock/validate/Makefile index 731b68b..0d78e09 100644 --- a/lib/ck/regressions/ck_spinlock/validate/Makefile +++ b/lib/ck/regressions/ck_spinlock/validate/Makefile @@ -50,7 +50,7 @@ ck_dec: ck_dec.c clean: rm -rf ck_ticket ck_mcs ck_dec ck_cas ck_fas ck_clh linux_spinlock ck_ticket_pb \ - ck_anderson ck_spinlock *.dSYM *.exe + ck_anderson ck_spinlock ck_hclh *.dSYM *.exe include ../../../build/regressions.build CFLAGS+=$(PTHREAD_CFLAGS) -D_GNU_SOURCE -lm http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/regressions/common.h ---------------------------------------------------------------------- diff --git a/lib/ck/regressions/common.h b/lib/ck/regressions/common.h index f100e89..4322a07 100644 --- a/lib/ck/regressions/common.h +++ b/lib/ck/regressions/common.h @@ -289,7 +289,7 @@ CK_CC_UNUSED static int aff_iterate_core(struct affinity *acb, unsigned int *core) { cpu_set_t s; - + *core = ck_pr_faa_uint(&acb->request, acb->delta); CPU_ZERO(&s); CPU_SET((*core) % CORES, &s); @@ -454,4 +454,3 @@ ck_error(const char *message, ...) va_end(ap); exit(EXIT_FAILURE); } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_array.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_array.c b/lib/ck/src/ck_array.c index 238ce0b..f7bb87a 100644 --- a/lib/ck/src/ck_array.c +++ b/lib/ck/src/ck_array.c @@ -238,4 +238,3 @@ ck_array_deinit(struct ck_array *array, bool defer) array->transaction = array->active = NULL; return; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_barrier_centralized.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_barrier_centralized.c b/lib/ck/src/ck_barrier_centralized.c index f0604a0..a21ef3e 100644 --- a/lib/ck/src/ck_barrier_centralized.c +++ b/lib/ck/src/ck_barrier_centralized.c @@ -57,4 +57,3 @@ ck_barrier_centralized(struct ck_barrier_centralized *barrier, ck_pr_fence_memory(); return; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_barrier_combining.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_barrier_combining.c b/lib/ck/src/ck_barrier_combining.c index b9df1d4..41291bb 100644 --- a/lib/ck/src/ck_barrier_combining.c +++ b/lib/ck/src/ck_barrier_combining.c @@ -205,4 +205,3 @@ ck_barrier_combining(struct ck_barrier_combining *barrier, state->sense = ~state->sense; return; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_barrier_dissemination.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_barrier_dissemination.c b/lib/ck/src/ck_barrier_dissemination.c index 867e224..dd08923 100644 --- a/lib/ck/src/ck_barrier_dissemination.c +++ b/lib/ck/src/ck_barrier_dissemination.c @@ -121,4 +121,3 @@ ck_barrier_dissemination(struct ck_barrier_dissemination *barrier, state->parity = 1 - state->parity; return; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_barrier_mcs.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_barrier_mcs.c b/lib/ck/src/ck_barrier_mcs.c index ed5959c..4dc8502 100644 --- a/lib/ck/src/ck_barrier_mcs.c +++ b/lib/ck/src/ck_barrier_mcs.c @@ -138,4 +138,3 @@ ck_barrier_mcs(struct ck_barrier_mcs *barrier, state->sense = ~state->sense; return; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_barrier_tournament.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_barrier_tournament.c b/lib/ck/src/ck_barrier_tournament.c index e505890..0f76c6f 100644 --- a/lib/ck/src/ck_barrier_tournament.c +++ b/lib/ck/src/ck_barrier_tournament.c @@ -181,4 +181,3 @@ leave: state->sense = ~state->sense; return; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_epoch.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_epoch.c b/lib/ck/src/ck_epoch.c index 343667c..01320ee 100644 --- a/lib/ck/src/ck_epoch.c +++ b/lib/ck/src/ck_epoch.c @@ -87,7 +87,7 @@ * at e_g - 1 to still be accessed at e_g as threads are "active" * at the same time (real-world time) mutating shared objects. * - * Now, if the epoch counter is ticked to e_g + 1, then no new + * Now, if the epoch counter is ticked to e_g + 1, then no new * hazardous references could exist to objects logically deleted at * e_g - 1. The reason for this is that at e_g + 1, all epoch read-side * critical sections started at e_g - 1 must have been completed. If @@ -118,7 +118,7 @@ * sufficient to represent e_g using only the values 0, 1 or 2. Every time * a thread re-visits a e_g (which can be determined with a non-empty deferral * list) it can assume objects in the e_g deferral list involved at least - * three e_g transitions and are thus, safe, for physical deletion. + * three e_g transitions and are thus, safe, for physical deletion. * * Blocking semantics for epoch reclamation have additional restrictions. * Though we only require three deferral lists, reasonable blocking semantics @@ -257,12 +257,16 @@ static void ck_epoch_dispatch(struct ck_epoch_record *record, unsigned int e) { unsigned int epoch = e & (CK_EPOCH_LENGTH - 1); - ck_stack_entry_t *next, *cursor; + ck_stack_entry_t *head, *next, *cursor; unsigned int i = 0; - CK_STACK_FOREACH_SAFE(&record->pending[epoch], cursor, next) { + head = CK_STACK_FIRST(&record->pending[epoch]); + ck_stack_init(&record->pending[epoch]); + + for (cursor = head; cursor != NULL; cursor = next) { struct ck_epoch_entry *entry = ck_epoch_entry_container(cursor); + next = CK_STACK_NEXT(cursor); entry->function(entry); i++; } @@ -272,7 +276,6 @@ ck_epoch_dispatch(struct ck_epoch_record *record, unsigned int e) record->n_dispatch += i; record->n_pending -= i; - ck_stack_init(&record->pending[epoch]); return; } @@ -426,4 +429,3 @@ ck_epoch_poll(struct ck_epoch *global, struct ck_epoch_record *record) ck_epoch_dispatch(record, epoch + 1); return true; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_hp.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_hp.c b/lib/ck/src/ck_hp.c index 634d94d..a39ff58 100644 --- a/lib/ck/src/ck_hp.c +++ b/lib/ck/src/ck_hp.c @@ -321,4 +321,3 @@ ck_hp_purge(struct ck_hp_record *thread) return; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_hs.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_hs.c b/lib/ck/src/ck_hs.c index 6769dad..5808876 100644 --- a/lib/ck/src/ck_hs.c +++ b/lib/ck/src/ck_hs.c @@ -369,6 +369,17 @@ restart: return true; } +static void +ck_hs_map_postinsert(struct ck_hs *hs, struct ck_hs_map *map) +{ + + map->n_entries++; + if ((map->n_entries << 1) > map->capacity) + ck_hs_grow(hs, map->capacity << 1); + + return; +} + bool ck_hs_rebuild(struct ck_hs *hs) { @@ -587,7 +598,7 @@ ck_hs_gc(struct ck_hs *hs, unsigned long cycles, unsigned long seed) if (maximum != map->probe_maximum) ck_pr_store_uint(&map->probe_maximum, maximum); - if (bounds != NULL) { + if (bounds != NULL) { for (i = 0; i < map->capacity; i++) CK_HS_STORE(&map->probe_bound[i], bounds[i]); @@ -630,6 +641,90 @@ ck_hs_fas(struct ck_hs *hs, return true; } +/* + * An apply function takes two arguments. The first argument is a pointer to a + * pre-existing object. The second argument is a pointer to the fifth argument + * passed to ck_hs_apply. If a non-NULL pointer is passed to the first argument + * and the return value of the apply function is NULL, then the pre-existing + * value is deleted. If the return pointer is the same as the one passed to the + * apply function then no changes are made to the hash table. If the first + * argument is non-NULL and the return pointer is different than that passed to + * the apply function, then the pre-existing value is replaced. For + * replacement, it is required that the value itself is identical to the + * previous value. + */ +bool +ck_hs_apply(struct ck_hs *hs, + unsigned long h, + const void *key, + ck_hs_apply_fn_t *fn, + void *cl) +{ + void **slot, **first, *object, *insert, *delta; + unsigned long n_probes; + struct ck_hs_map *map; + +restart: + map = hs->map; + + slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_HS_PROBE_INSERT); + if (slot == NULL && first == NULL) { + if (ck_hs_grow(hs, map->capacity << 1) == false) + return false; + + goto restart; + } + + delta = fn(object, cl); + if (delta == NULL) { + /* + * The apply function has requested deletion. If the object doesn't exist, + * then exit early. + */ + if (CK_CC_UNLIKELY(object == NULL)) + return true; + + /* Otherwise, mark slot as deleted. */ + ck_pr_store_ptr(slot, CK_HS_TOMBSTONE); + map->n_entries--; + map->tombstones++; + return true; + } + + /* The apply function has not requested hash set modification so exit early. */ + if (delta == object) + return true; + + /* A modification or insertion has been requested. */ + ck_hs_map_bound_set(map, h, n_probes); + + insert = ck_hs_marshal(hs->mode, delta, h); + if (first != NULL) { + /* + * This follows the same semantics as ck_hs_set, please refer to that + * function for documentation. + */ + ck_pr_store_ptr(first, insert); + + if (object != NULL) { + ck_pr_inc_uint(&map->generation[h & CK_HS_G_MASK]); + ck_pr_fence_atomic_store(); + ck_pr_store_ptr(slot, CK_HS_TOMBSTONE); + } + } else { + /* + * If we are storing into same slot, then atomic store is sufficient + * for replacement. + */ + ck_pr_store_ptr(slot, insert); + } + + if (object == NULL) + ck_hs_map_postinsert(hs, map); + + return true; +} + bool ck_hs_set(struct ck_hs *hs, unsigned long h, @@ -680,11 +775,8 @@ restart: ck_pr_store_ptr(slot, insert); } - if (object == NULL) { - map->n_entries++; - if ((map->n_entries << 1) > map->capacity) - ck_hs_grow(hs, map->capacity << 1); - } + if (object == NULL) + ck_hs_map_postinsert(hs, map); *previous = object; return true; @@ -728,10 +820,7 @@ restart: ck_pr_store_ptr(slot, insert); } - map->n_entries++; - if ((map->n_entries << 1) > map->capacity) - ck_hs_grow(hs, map->capacity << 1); - + ck_hs_map_postinsert(hs, map); return true; } @@ -764,7 +853,7 @@ ck_hs_get(struct ck_hs *hs, unsigned int g, g_p, probe; unsigned int *generation; - do { + do { map = ck_pr_load_ptr(&hs->map); generation = &map->generation[h & CK_HS_G_MASK]; g = ck_pr_load_uint(generation); @@ -842,4 +931,3 @@ ck_hs_init(struct ck_hs *hs, hs->map = ck_hs_map_create(hs, n_entries); return hs->map != NULL; } - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_ht.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_ht.c b/lib/ck/src/ck_ht.c index ea9de1e..324a03d 100644 --- a/lib/ck/src/ck_ht.c +++ b/lib/ck/src/ck_ht.c @@ -395,7 +395,7 @@ ck_ht_gc(struct ck_ht *ht, unsigned long cycles, unsigned long seed) return true; } - + if (cycles == 0) { maximum = 0; @@ -1027,4 +1027,3 @@ ck_ht_destroy(struct ck_ht *table) } #endif /* CK_F_HT */ - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_ht_hash.h ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_ht_hash.h b/lib/ck/src/ck_ht_hash.h index 254e3b8..075c2c1 100644 --- a/lib/ck/src/ck_ht_hash.h +++ b/lib/ck/src/ck_ht_hash.h @@ -175,7 +175,7 @@ static inline uint64_t MurmurHash64A ( const void * key, int len, uint64_t seed while(data != end) { uint64_t k; - + if (!((uintptr_t)data & 0x7)) k = *data++; else { http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0da17e96/lib/ck/src/ck_rhs.c ---------------------------------------------------------------------- diff --git a/lib/ck/src/ck_rhs.c b/lib/ck/src/ck_rhs.c index 962a94c..76043ea 100644 --- a/lib/ck/src/ck_rhs.c +++ b/lib/ck/src/ck_rhs.c @@ -327,11 +327,11 @@ ck_rhs_map_create(struct ck_rhs *hs, unsigned long entries) if (hs->mode & CK_RHS_MODE_READ_MOSTLY) size = sizeof(struct ck_rhs_map) + (sizeof(void *) * n_entries + - sizeof(struct ck_rhs_no_entry_desc) * n_entries + + sizeof(struct ck_rhs_no_entry_desc) * n_entries + 2 * CK_MD_CACHELINE - 1); else size = sizeof(struct ck_rhs_map) + - (sizeof(struct ck_rhs_entry_desc) * n_entries + + (sizeof(struct ck_rhs_entry_desc) * n_entries + CK_MD_CACHELINE - 1); map = hs->m->malloc(size); if (map == NULL) @@ -408,7 +408,7 @@ ck_rhs_map_probe_next(struct ck_rhs_map *map, { if (probes & map->offset_mask) { - offset = (offset &~ map->offset_mask) + + offset = (offset &~ map->offset_mask) + ((offset + 1) & map->offset_mask); return offset; } else @@ -421,10 +421,10 @@ ck_rhs_map_probe_prev(struct ck_rhs_map *map, unsigned long offset, { if (probes & map->offset_mask) { - offset = (offset &~ map->offset_mask) + ((offset - 1) & + offset = (offset &~ map->offset_mask) + ((offset - 1) & map->offset_mask); return offset; - } else + } else return ((offset - probes) & map->mask); } @@ -616,7 +616,7 @@ ck_rhs_map_probe_rm(struct ck_rhs *hs, if (behavior != CK_RHS_PROBE_NO_RH) { struct ck_rhs_entry_desc *desc = (void *)&map->entries.no_entries.descs[offset]; - if (pr == -1 && + if (pr == -1 && desc->in_rh == false && desc->probes < probes) { pr = offset; *n_probes = probes; @@ -730,7 +730,7 @@ ck_rhs_map_probe(struct ck_rhs *hs, if ((behavior != CK_RHS_PROBE_NO_RH)) { struct ck_rhs_entry_desc *desc = &map->entries.descs[offset]; - if (pr == -1 && + if (pr == -1 && desc->in_rh == false && desc->probes < probes) { pr = offset; *n_probes = probes; @@ -818,7 +818,7 @@ ck_rhs_gc(struct ck_rhs *hs) } static void -ck_rhs_add_wanted(struct ck_rhs *hs, long end_offset, long old_slot, +ck_rhs_add_wanted(struct ck_rhs *hs, long end_offset, long old_slot, unsigned long h) { struct ck_rhs_map *map = hs->map; @@ -872,7 +872,7 @@ ck_rhs_get_first_offset(struct ck_rhs_map *map, unsigned long offset, unsigned i while (probes > (unsigned long)map->offset_mask + 1) { offset -= ((probes - 1) &~ map->offset_mask); offset &= map->mask; - offset = (offset &~ map->offset_mask) + + offset = (offset &~ map->offset_mask) + ((offset - map->offset_mask) & map->offset_mask); probes -= map->offset_mask + 1; } @@ -892,7 +892,7 @@ ck_rhs_put_robin_hood(struct ck_rhs *hs, unsigned long h = 0; long prev; void *key; - long prevs[512]; + long prevs[CK_RHS_MAX_RH]; unsigned int prevs_nb = 0; map = hs->map; @@ -948,7 +948,7 @@ restart: prev = prevs[--prevs_nb]; ck_pr_store_ptr(ck_rhs_entry_addr(map, orig_slot), ck_rhs_entry(map, prev)); - h = ck_rhs_get_first_offset(map, orig_slot, + h = ck_rhs_get_first_offset(map, orig_slot, desc->probes); ck_rhs_add_wanted(hs, orig_slot, prev, h); ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]); @@ -966,7 +966,7 @@ ck_rhs_do_backward_shift_delete(struct ck_rhs *hs, long slot) struct ck_rhs_map *map = hs->map; struct ck_rhs_entry_desc *desc, *new_desc = NULL; unsigned long h; - + desc = ck_rhs_desc(map, slot); h = ck_rhs_remove_wanted(hs, slot, -1); while (desc->wanted > 0) { @@ -1089,6 +1089,121 @@ restart: return true; } +/* + * An apply function takes two arguments. The first argument is a pointer to a + * pre-existing object. The second argument is a pointer to the fifth argument + * passed to ck_hs_apply. If a non-NULL pointer is passed to the first argument + * and the return value of the apply function is NULL, then the pre-existing + * value is deleted. If the return pointer is the same as the one passed to the + * apply function then no changes are made to the hash table. If the first + * argument is non-NULL and the return pointer is different than that passed to + * the apply function, then the pre-existing value is replaced. For + * replacement, it is required that the value itself is identical to the + * previous value. + */ +bool +ck_rhs_apply(struct ck_rhs *hs, + unsigned long h, + const void *key, + ck_rhs_apply_fn_t *fn, + void *cl) +{ + void *object, *insert, *delta = false; + unsigned long n_probes; + long slot, first; + struct ck_rhs_map *map; + bool delta_set = false; + +restart: + map = hs->map; + + slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_RHS_PROBE_INSERT); + if (slot == -1 && first == -1) { + if (ck_rhs_grow(hs, map->capacity << 1) == false) + return false; + + goto restart; + } + if (!delta_set) { + delta = fn(object, cl); + delta_set = true; + } + + if (delta == NULL) { + /* + * The apply function has requested deletion. If the object doesn't exist, + * then exit early. + */ + if (CK_CC_UNLIKELY(object == NULL)) + return true; + + /* Otherwise, delete it. */ + ck_rhs_do_backward_shift_delete(hs, slot); + return true; + } + + /* The apply function has not requested hash set modification so exit early. */ + if (delta == object) + return true; + + /* A modification or insertion has been requested. */ + ck_rhs_map_bound_set(map, h, n_probes); + + insert = ck_rhs_marshal(hs->mode, delta, h); + if (first != -1) { + /* + * This follows the same semantics as ck_hs_set, please refer to that + * function for documentation. + */ + struct ck_rhs_entry_desc *desc = NULL, *desc2; + if (slot != -1) { + desc = ck_rhs_desc(map, slot); + desc->in_rh = true; + } + desc2 = ck_rhs_desc(map, first); + int ret = ck_rhs_put_robin_hood(hs, first, desc2); + if (slot != -1) + desc->in_rh = false; + + if (CK_CC_UNLIKELY(ret == 1)) + goto restart; + if (CK_CC_UNLIKELY(ret == -1)) + return false; + /* If an earlier bucket was found, then store entry there. */ + ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert); + desc2->probes = n_probes; + /* + * If a duplicate key was found, then delete it after + * signaling concurrent probes to restart. Optionally, + * it is possible to install tombstone after grace + * period if we can guarantee earlier position of + * duplicate key. + */ + ck_rhs_add_wanted(hs, first, -1, h); + if (object != NULL) { + ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]); + ck_pr_fence_atomic_store(); + ck_rhs_do_backward_shift_delete(hs, slot); + } + } else { + /* + * If we are storing into same slot, then atomic store is sufficient + * for replacement. + */ + ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), insert); + ck_rhs_set_probes(map, slot, n_probes); + if (object == NULL) + ck_rhs_add_wanted(hs, slot, -1, h); + } + + if (object == NULL) { + map->n_entries++; + if ((map->n_entries ) > ((map->capacity * CK_RHS_LOAD_FACTOR) / 100)) + ck_rhs_grow(hs, map->capacity << 1); + } + return true; +} + bool ck_rhs_set(struct ck_rhs *hs, unsigned long h, @@ -1140,7 +1255,7 @@ restart: * period if we can guarantee earlier position of * duplicate key. */ - ck_rhs_add_wanted(hs, first, -1, h); + ck_rhs_add_wanted(hs, first, -1, h); if (object != NULL) { ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]); ck_pr_fence_atomic_store(); @@ -1155,7 +1270,7 @@ restart: ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), insert); ck_rhs_set_probes(map, slot, n_probes); if (object == NULL) - ck_rhs_add_wanted(hs, slot, -1, h); + ck_rhs_add_wanted(hs, slot, -1, h); } if (object == NULL) { @@ -1209,12 +1324,12 @@ restart: /* Insert key into first bucket in probe sequence. */ ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert); desc->probes = n_probes; - ck_rhs_add_wanted(hs, first, -1, h); + ck_rhs_add_wanted(hs, first, -1, h); } else { /* An empty slot was found. */ ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), insert); ck_rhs_set_probes(map, slot, n_probes); - ck_rhs_add_wanted(hs, slot, -1, h); + ck_rhs_add_wanted(hs, slot, -1, h); } map->n_entries++; @@ -1253,7 +1368,7 @@ ck_rhs_get(struct ck_rhs *hs, unsigned int g, g_p, probe; unsigned int *generation; - do { + do { map = ck_pr_load_ptr(&hs->map); generation = &map->generation[h & CK_RHS_G_MASK]; g = ck_pr_load_uint(generation); @@ -1332,4 +1447,3 @@ ck_rhs_init(struct ck_rhs *hs, hs->map = ck_rhs_map_create(hs, n_entries); return hs->map != NULL; } -
