From 98db3badafbc8ee41e4d77688768c8b0bcb137fd Mon Sep 17 00:00:00 2001 From: Nick Gasson Date: Sun, 4 Dec 2022 10:38:33 +0000 Subject: [PATCH] Add a hash table that supports concurrent access --- src/hash.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++ src/hash.h | 5 +++ src/prim.h | 1 + test/mtstress.c | 63 +++++++++++++++++++++++++++++++++++++ test/test_misc.c | 27 ++++++++++++++++ 5 files changed, 177 insertions(+) diff --git a/src/hash.c b/src/hash.c index c77c796c..c478db18 100644 --- a/src/hash.c +++ b/src/hash.c @@ -16,6 +16,7 @@ // #include "hash.h" +#include "thread.h" #include #include @@ -464,3 +465,83 @@ bool hset_contains(hset_t *h, const void *key) return false; } } + +//////////////////////////////////////////////////////////////////////////////// +// Hash table that supports concurrent updates + +typedef struct _chash_node chash_node_t; + +struct _chash_node { + chash_node_t *chain; + const void *key; + void *value; +}; + +struct _chash { + unsigned size; + unsigned members; + chash_node_t *slots[0]; +}; + +chash_t *chash_new(int size) +{ + const int roundup = next_power_of_2(size); + + chash_t *h = xcalloc_flex(sizeof(chash_t), roundup, sizeof(chash_node_t)); + h->size = roundup; + h->members = 0; + + return h; +} + +void chash_free(chash_t *h) +{ + if (h != NULL) { + for (int i = 0; i < h->size; i++) { + for (chash_node_t *it = h->slots[i], *tmp; it; it = tmp) { + tmp = it->chain; + free(it); + } + } + + free(h); + } +} + +bool chash_put(chash_t *h, const void *key, void *value) +{ + const int slot = hash_slot(h->size, key); + + for (;;) { + chash_node_t **p = &(h->slots[slot]); + for (chash_node_t *it; (it = load_acquire(p)); p = &(it->chain)) { + if (it->key == key) { + store_release(&(it->value), value); + return true; + } + } + + chash_node_t *new = xmalloc(sizeof(chash_node_t)); + new->chain = NULL; + new->key = key; + new->value = value; + + if (atomic_cas(p, NULL, new)) + return false; + + free(new); + } +} + +void *chash_get(chash_t *h, const void *key) +{ + const int slot = hash_slot(h->size, key); + + for (chash_node_t *it = load_acquire(&(h->slots[slot])); + it != NULL; it = load_acquire(&(it->chain))) { + if (it->key == key) + return load_acquire(&(it->value)); + } + + return NULL; +} diff --git a/src/hash.h b/src/hash.h index 404607dd..da664525 100644 --- a/src/hash.h +++ b/src/hash.h @@ -51,4 +51,9 @@ void hset_free(hset_t *h); void hset_insert(hset_t *h, const void *key); bool hset_contains(hset_t *h, const void *key); +chash_t *chash_new(int size); +void chash_free(chash_t *h); +bool chash_put(chash_t *h, const void *key, void *value); +void *chash_get(chash_t *h, const void *key); + #endif // _HASH_H diff --git a/src/prim.h b/src/prim.h index 77befd8e..54d8ff85 100644 --- a/src/prim.h +++ b/src/prim.h @@ -38,6 +38,7 @@ typedef struct _fbuf fbuf_t; typedef struct _hash hash_t; typedef struct _shash shash_t; typedef struct _ihash ihash_t; +typedef struct _chash chash_t; typedef struct _hset hset_t; typedef struct _eval eval_t; typedef struct _eval_frame eval_frame_t; diff --git a/test/mtstress.c b/test/mtstress.c index a742720c..060d9c57 100644 --- a/test/mtstress.c +++ b/test/mtstress.c @@ -16,6 +16,7 @@ // #include "util.h" +#include "hash.h" #include "ident.h" #include "opt.h" #include "rt/mspace.h" @@ -90,6 +91,64 @@ START_TEST(test_ident_new) } END_TEST +//////////////////////////////////////////////////////////////////////////////// +// Concurrent hash table updates + +#define CHASH_NVALUES 1024 +#define CHASH_ITERS 10000 + +static void *chash_keys[CHASH_NVALUES]; +static void *chash_values[CHASH_NVALUES]; + +#define VOIDP(x) ((void *)(uintptr_t)x) + +static void *test_chash_thread(void *arg) +{ + chash_t *h = arg; + + while (load_acquire(&start) == 0) + spin_wait(); + + for (int i = 0; i < CHASH_ITERS; i++) { + int nth = rand() % CHASH_NVALUES; + + if (rand() % 3 == 0) + chash_put(h, chash_keys[nth], chash_values[nth]); + else { + void *value = chash_get(h, chash_keys[nth]); + if (value != NULL) + ck_assert_ptr_eq(value, chash_values[nth]); + } + } + + return NULL; +} + +START_TEST(test_chash_rand) +{ + for (int i = 0; i < CHASH_NVALUES; i++) { + do { + chash_keys[i] = VOIDP(((i << 16) | (rand() & 0xffff))); + } while (chash_keys[i] == NULL); + chash_values[i] = VOIDP(rand()); + } + + chash_t *h = chash_new(CHASH_NVALUES / 4); + + const int nproc = nvc_nprocs(); + nvc_thread_t *handles[nproc]; + for (int i = 0; i < nproc; i++) + handles[i] = thread_create(test_chash_thread, h, "test thread %d", i); + + store_release(&start, 1); + + for (int i = 0; i < nproc; i++) + thread_join(handles[i]); + + chash_free(h); +} +END_TEST + //////////////////////////////////////////////////////////////////////////////// int main(int argc, char **argv) @@ -110,6 +169,10 @@ int main(int argc, char **argv) tcase_add_test(tc_ident, test_ident_new); suite_add_tcase(s, tc_ident); + TCase *tc_chash = tcase_create("chash"); + tcase_add_test(tc_chash, test_chash_rand); + suite_add_tcase(s, tc_chash); + SRunner *sr = srunner_create(s); srunner_run_all(sr, CK_NORMAL); diff --git a/test/test_misc.c b/test/test_misc.c index 9f546f49..f0d9d853 100644 --- a/test/test_misc.c +++ b/test/test_misc.c @@ -184,6 +184,32 @@ START_TEST(test_hset_rand) } END_TEST; +START_TEST(test_chash_rand) +{ + chash_t *h = chash_new(32); + + static const int N = 1024; + + void *keys[N]; + void *values[N]; + + for (int i = 0; i < N; i++) { + do { + keys[i] = VOIDP(((i << 16) | (rand() & 0xffff))); + } while (keys[i] == NULL); + values[i] = VOIDP(rand()); + } + + for (int i = 0; i < N; i++) + chash_put(h, keys[i], values[i]); + + for (int i = 0; i < N; i++) + fail_unless(chash_get(h, keys[i]) == values[i]); + + chash_free(h); +} +END_TEST; + START_TEST(test_safe_symbol) { const char *orig = "foo[]()+*\"=bar"; @@ -523,6 +549,7 @@ Suite *get_misc_tests(void) tcase_add_test(tc_hash, test_shash_rand); tcase_add_test(tc_hash, test_ihash_rand); tcase_add_test(tc_hash, test_hset_rand); + tcase_add_test(tc_hash, test_chash_rand); suite_add_tcase(s, tc_hash); TCase *tc_sym = tcase_create("safe_symbol"); -- 2.39.2