From 53c6a365e1baa0914529d9cf505663f4fd9ec4b8 Mon Sep 17 00:00:00 2001 From: Nick Gasson Date: Sat, 26 Nov 2022 17:25:55 +0000 Subject: [PATCH] Make ident_t operations thread-safe --- src/ident.c | 34 +++++++------ test/Makemodule.am | 18 +++++-- test/mtstress.c | 117 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 151 insertions(+), 18 deletions(-) create mode 100644 test/mtstress.c diff --git a/src/ident.c b/src/ident.c index 820b789a..ccb03842 100644 --- a/src/ident.c +++ b/src/ident.c @@ -82,8 +82,12 @@ static bool ident_install(ident_t *where, ident_t new, int len) new->write_gen = 0; new->write_index = 0; - *where = new; - return true; + if (atomic_cas(where, NULL, new)) + return true; + else { + free(new); + return false; + } } static ident_t ident_from_bytes(const char *str, hash_state_t hash, int len) @@ -91,9 +95,9 @@ static ident_t ident_from_bytes(const char *str, hash_state_t hash, int len) const int slot = hash & (TABLE_SZ - 1); for (;;) { ident_t *ptr = &(table[slot]); - for (; *ptr; ptr = &((*ptr)->chain)) { - if ((*ptr)->length == len && memcmp((*ptr)->bytes, str, len) == 0) - return *ptr; + for (ident_t it; (it = load_acquire(ptr)); ptr = &(it->chain)) { + if (it->length == len && memcmp(it->bytes, str, len) == 0) + return it; } ident_t new = xmalloc_flex(sizeof(struct _ident), len + 1, sizeof(char)); @@ -218,10 +222,10 @@ ident_t ident_uniq(const char *prefix) const int slot = hash & (TABLE_SZ - 1); for (;;) { ident_t *ptr = &(table[slot]); - for (; *ptr; ptr = &((*ptr)->chain)) { - if ((*ptr)->length == len + sufflen - && memcmp((*ptr)->bytes, prefix, len) == 0 - && memcmp((*ptr)->bytes + len, suffix, sufflen) == 0) + for (ident_t it; (it = load_acquire(ptr)); ptr = &(it->chain)) { + if (it->length == len + sufflen + && memcmp(it->bytes, prefix, len) == 0 + && memcmp(it->bytes + len, suffix, sufflen) == 0) goto exist; } @@ -257,13 +261,13 @@ ident_t ident_prefix(ident_t a, ident_t b, char sep) for (;;) { ident_t *ptr = &(table[slot]); - for (; *ptr; ptr = &((*ptr)->chain)) { - if ((*ptr)->length == len - && memcmp((*ptr)->bytes, a->bytes, a->length) == 0 - && (sep == '\0' || (*ptr)->bytes[a->length] == sep) - && memcmp((*ptr)->bytes + a->length + (sep != '\0'), + for (ident_t it; (it = load_acquire(ptr)); ptr = &(it->chain)) { + if (it->length == len + && memcmp(it->bytes, a->bytes, a->length) == 0 + && (sep == '\0' || it->bytes[a->length] == sep) + && memcmp(it->bytes + a->length + (sep != '\0'), b->bytes, b->length) == 0) - return *ptr; + return it; } ident_t new = xmalloc_flex(sizeof(struct _ident), len + 1, sizeof(char)); diff --git a/test/Makemodule.am b/test/Makemodule.am index 3e9530a0..355d2141 100644 --- a/test/Makemodule.am +++ b/test/Makemodule.am @@ -4,7 +4,7 @@ TESTS = \ check_PROGRAMS += $(TESTS) bin/fstdump -EXTRA_PROGRAMS += bin/lockbench bin/jitperf bin/workqbench +EXTRA_PROGRAMS += bin/lockbench bin/jitperf bin/workqbench bin/mtstress bin_unit_test_SOURCES = \ test/test_util.c \ @@ -30,7 +30,6 @@ bin_unit_test_LDADD = \ lib/libfastlz.a \ lib/libcpustate.a \ $(check_LIBS) \ - $(POW_LIB) \ $(libdw_LIBS) \ $(libffi_LIBS) @@ -74,10 +73,23 @@ bin_workqbench_SOURCES = test/workqbench.c bin_workqbench_LDADD = \ lib/libnvc.a \ + lib/libfastlz.a \ + lib/libcpustate.a \ $(libdw_LIBS) \ $(libffi_LIBS) \ + $(check_LIBS) + +bin_mtstress_SOURCES = test/mtstress.c + +bin_mtstress_LDFLAGS = $(LDFLAGS) $(AM_LDFLAGS) $(EXPORT_LDFLAGS) + +bin_mtstress_LDADD = \ + lib/libnvc.a \ lib/libfastlz.a \ - lib/libcpustate.a + lib/libcpustate.a \ + $(libdw_LIBS) \ + $(libffi_LIBS) \ + $(check_LIBS) TESTS_ENVIRONMENT = \ BUILD_DIR=$(top_builddir) \ diff --git a/test/mtstress.c b/test/mtstress.c new file mode 100644 index 00000000..a742720c --- /dev/null +++ b/test/mtstress.c @@ -0,0 +1,117 @@ +// +// Copyright (C) 2022 Nick Gasson +// +// This program is free software: you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program. If not, see . +// + +#include "util.h" +#include "ident.h" +#include "opt.h" +#include "rt/mspace.h" +#include "thread.h" + +#include +#include +#include +#include +#include + +//////////////////////////////////////////////////////////////////////////////// +// Concurrent calls to ident_new + +#define NWORDS 10000 +static char *words[NWORDS]; +static ident_t idents[NWORDS]; +static volatile int start = 0; + +static void *test_ident_thread(void *arg) +{ + const int nproc = nvc_nprocs(); + + while (load_acquire(&start) == 0) + spin_wait(); + + for (int i = 0; i < NWORDS / 2 / nproc; i++) { + const int pos = rand() % NWORDS; + ident_t id = ident_new(words[pos]), exist; + + again: + exist = load_acquire(&(idents[pos])); + if (exist != NULL) + ck_assert_ptr_eq(exist, id); + else if (!atomic_cas(&(idents[pos]), NULL, id)) + goto again; + } + + return NULL; +} + +START_TEST(test_ident_new) +{ + FILE *f = fopen("/usr/share/dict/words", "r"); + ck_assert_ptr_nonnull(f); + + char *line LOCAL = NULL; + size_t bufsz = 0; + for (int pos = 0; pos < NWORDS; ) { + const int nchars = getline(&line, &bufsz, f); + ck_assert_int_ge(nchars, 2); + + if (islower(line[0]) && nchars > 2 && line[nchars - 3] != '\'') { + line[nchars - 1] = '\0'; + words[pos++] = line; + line = NULL; + bufsz = 0; + } + } + + fclose(f); + + const int nproc = nvc_nprocs(); + nvc_thread_t *handles[nproc]; + for (int i = 0; i < nproc; i++) + handles[i] = thread_create(test_ident_thread, NULL, "test thread %d", i); + + store_release(&start, 1); + + for (int i = 0; i < nproc; i++) + thread_join(handles[i]); +} +END_TEST + +//////////////////////////////////////////////////////////////////////////////// + +int main(int argc, char **argv) +{ + srand((unsigned)time(NULL)); + + term_init(); + thread_init(); + register_signal_handlers(); + set_default_options(); + mspace_stack_limit(MSPACE_CURRENT_FRAME); + + setenv("NVC_LIBPATH", "./lib", 1); + + Suite *s = suite_create("mtstress"); + + TCase *tc_ident = tcase_create("ident"); + tcase_add_test(tc_ident, test_ident_new); + suite_add_tcase(s, tc_ident); + + SRunner *sr = srunner_create(s); + srunner_run_all(sr, CK_NORMAL); + + return srunner_ntests_failed(sr) == 0; +} -- 2.39.2