Index: uspace/Makefile =================================================================== --- uspace/Makefile (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/Makefile (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -61,4 +61,6 @@ app/nterm \ app/redir \ + app/rcutest \ + app/rcubench \ app/sbi \ app/sportdmp \ @@ -227,4 +229,5 @@ lib/trackmod \ lib/uri \ + lib/urcu \ lib/usb \ lib/usbhost \ Index: uspace/Makefile.common =================================================================== --- uspace/Makefile.common (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/Makefile.common (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -156,4 +156,6 @@ LIBGPT_PREFIX = $(LIB_PREFIX)/gpt +LIBURCU_PREFIX = $(LIB_PREFIX)/urcu + ifeq ($(STATIC_NEEDED),y) STATIC_BUILD = y @@ -281,4 +283,9 @@ JOBFILE = $(LIBC_PREFIX)/../../../tools/jobfile.py +ifeq ($(FUTEX_UPGRADABLE),y) + CFLAGS += -I$(LIBURCU_PREFIX)/ + LIBS += $(LIBURCU_PREFIX)/liburcu.a +endif + ifeq ($(COMPILER),gcc_cross) CFLAGS += $(GCC_CFLAGS) $(EXTRA_CFLAGS) Index: uspace/app/rcubench/Makefile =================================================================== --- uspace/app/rcubench/Makefile (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/app/rcubench/Makefile (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,41 @@ +# +# Copyright (c) 2012 Adam Hraska +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - 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. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. +# + +USPACE_PREFIX = ../.. + +LIBS = $(LIBURCU_PREFIX)/liburcu.a + +EXTRA_CFLAGS += -I$(LIBURCU_PREFIX) + +BINARY = rcubench + +SOURCES = \ + rcubench.c + +include $(USPACE_PREFIX)/Makefile.common + Index: uspace/app/rcubench/rcubench.c =================================================================== --- uspace/app/rcubench/rcubench.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/app/rcubench/rcubench.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,288 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. + */ + +/** @addtogroup test + * @{ + */ + +/** + * @file rcubench.c + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + + +/* Results are printed to this file in addition to stdout. */ +static FILE *results_fd = NULL; + +typedef struct bench { + const char *name; + void (*func)(struct bench *); + size_t iters; + size_t nthreads; + futex_t done_threads; + + futex_t bench_fut; +} bench_t; + + + + +static void kernel_futex_bench(bench_t *bench) +{ + const size_t iters = bench->iters; + int val = 0; + + for (size_t i = 0; i < iters; ++i) { + __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &val); + __SYSCALL1(SYS_FUTEX_SLEEP, (sysarg_t) &val); + } +} + +static void libc_futex_lock_bench(bench_t *bench) +{ + const size_t iters = bench->iters; + futex_t loc_fut = FUTEX_INITIALIZER; + + for (size_t i = 0; i < iters; ++i) { + futex_lock(&loc_fut); + /* no-op */ + compiler_barrier(); + futex_unlock(&loc_fut); + } +} + +static void libc_futex_sema_bench(bench_t *bench) +{ + const size_t iters = bench->iters; + futex_t loc_fut = FUTEX_INITIALIZER; + + for (size_t i = 0; i < iters; ++i) { + futex_down(&loc_fut); + /* no-op */ + compiler_barrier(); + futex_up(&loc_fut); + } +} + +static void thread_func(void *arg) +{ + bench_t *bench = (bench_t*)arg; + + bench->func(bench); + + /* Signal another thread completed. */ + futex_up(&bench->done_threads); +} + +static void run_threads_and_wait(bench_t *bench) +{ + assert(1 <= bench->nthreads); + + if (2 <= bench->nthreads) { + printf("Creating %zu additional threads...\n", bench->nthreads - 1); + } + + /* Create and run the first nthreads - 1 threads.*/ + for (size_t k = 1; k < bench->nthreads; ++k) { + thread_id_t tid; + /* Also sets up a fibril for the thread. */ + int ret = thread_create(thread_func, bench, "rcubench-t", &tid); + if (ret != EOK) { + printf("Error: Failed to create benchmark thread.\n"); + abort(); + } + thread_detach(tid); + } + + /* + * Run the last thread in place so that we create multiple threads + * only when needed. Otherwise libc would immediately upgrade + * single-threaded futexes to proper multithreaded futexes + */ + thread_func(bench); + + printf("Waiting for remaining threads to complete.\n"); + + /* Wait for threads to complete. */ + for (size_t k = 0; k < bench->nthreads; ++k) { + futex_down(&bench->done_threads); + } +} + +static const char *results_txt = "/tmp/urcu-bench-results.txt"; + +static bool open_results(void) +{ + results_fd = fopen(results_txt, "a"); + return NULL != results_fd; +} + +static void close_results(void) +{ + if (results_fd) { + fclose(results_fd); + } +} + +static void print_res(const char *fmt, ... ) +{ + va_list args; + + va_start(args, fmt); + vfprintf(results_fd, fmt, args); + va_end(args); + + va_start(args, fmt); + vprintf(fmt, args); + va_end(args); +} + +static void print_usage(void) +{ + printf("rcubench [test-name] [k-iterations] [n-threads]\n"); + printf("Available tests: \n"); + printf(" sys-futex.. threads make wakeup/sleepdown futex syscalls in a loop\n"); + printf(" but for separate variables/futex kernel objects.\n"); + printf(" lock .. threads lock/unlock separate futexes.\n"); + printf(" sema .. threads down/up separate futexes.\n"); + printf("eg:\n"); + printf(" rcubench sys-futex 100000 3\n"); + printf(" rcubench lock 100000 2 ..runs futex_lock/unlock in a loop\n"); + printf(" rcubench sema 100000 2 ..runs futex_down/up in a loop\n"); + printf("Results are stored in %s\n", results_txt); +} + +static bool parse_cmd_line(int argc, char **argv, bench_t *bench, + const char **err) +{ + if (argc < 4) { + *err = "Not enough parameters"; + return false; + } + + futex_initialize(&bench->bench_fut, 1); + + if (0 == str_cmp(argv[1], "sys-futex")) { + bench->func = kernel_futex_bench; + } else if (0 == str_cmp(argv[1], "lock")) { + bench->func = libc_futex_lock_bench; + } else if (0 == str_cmp(argv[1], "sema")) { + bench->func = libc_futex_sema_bench; + } else { + *err = "Unknown test name"; + return false; + } + + bench->name = argv[1]; + + /* Determine iteration count. */ + uint32_t iter_cnt = 0; + int ret = str_uint32_t(argv[2], NULL, 0, true, &iter_cnt); + + if (ret == EOK && 1 <= iter_cnt) { + bench->iters = iter_cnt; + } else { + *err = "Err: Invalid number of iterations"; + return false; + } + + /* Determine thread count. */ + uint32_t thread_cnt = 0; + ret = str_uint32_t(argv[3], NULL, 0, true, &thread_cnt); + + if (ret == EOK && 1 <= thread_cnt && thread_cnt <= 64) { + bench->nthreads = thread_cnt; + } else { + *err = "Err: Invalid number of threads"; + return false; + } + + return true; +} + +int main(int argc, char **argv) +{ + const char *err = "(error)"; + bench_t bench; + + futex_initialize(&bench.done_threads, 0); + + if (!parse_cmd_line(argc, argv, &bench, &err)) { + printf("%s\n", err); + print_usage(); + return -1; + } + + open_results(); + + print_res("Running '%s' futex bench in '%zu' threads with '%zu' iterations.\n", + bench.name, bench.nthreads, bench.iters); + + struct timeval start, end; + getuptime(&start); + + run_threads_and_wait(&bench); + + getuptime(&end); + int64_t duration = tv_sub(&end, &start); + + uint64_t secs = (uint64_t)duration / 1000 / 1000; + uint64_t total_iters = (uint64_t)bench.iters * bench.nthreads; + uint64_t iters_per_sec = 0; + + if (0 < duration) { + iters_per_sec = total_iters * 1000 * 1000 / duration; + } + + print_res("Completed %" PRIu64 " iterations in %" PRId64 " usecs (%" PRIu64 + " secs); %" PRIu64 " iters/sec\n", + total_iters, duration, secs, iters_per_sec); + + close_results(); + + return 0; +} + + +/** + * @} + */ Index: uspace/app/rcutest/Makefile =================================================================== --- uspace/app/rcutest/Makefile (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/app/rcutest/Makefile (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,41 @@ +# +# Copyright (c) 2012 Adam Hraska +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - 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. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. +# + +USPACE_PREFIX = ../.. + +LIBS = $(LIBURCU_PREFIX)/liburcu.a + +EXTRA_CFLAGS += -I$(LIBURCU_PREFIX) + +BINARY = rcutest + +SOURCES = \ + rcutest.c + +include $(USPACE_PREFIX)/Makefile.common + Index: uspace/app/rcutest/rcutest.c =================================================================== --- uspace/app/rcutest/rcutest.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/app/rcutest/rcutest.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,909 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. + */ + +/** @addtogroup test + * @{ + */ + +/** + * @file rcutest.c + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + + + +#define USECS_PER_SEC (1000 * 1000) +#define USECS_PER_MS 1000 + +/* fwd decl. */ +struct test_info; + +typedef struct test_desc { + /* Aggregate test that runs other tests already in the table test_desc. */ + bool aggregate; + enum { + T_OTHER, + T_SANITY, + T_STRESS + } type; + bool (*func)(struct test_info*); + const char *name; + const char *desc; +} test_desc_t; + + +typedef struct test_info { + size_t thread_cnt; + test_desc_t *desc; +} test_info_t; + + + +static bool run_all_tests(struct test_info*); +static bool run_sanity_tests(struct test_info*); +static bool run_stress_tests(struct test_info*); + +static bool wait_for_one_reader(struct test_info*); +static bool basic_sanity_check(struct test_info*); +static bool dont_wait_for_new_reader(struct test_info*); +static bool wait_for_exiting_reader(struct test_info*); +static bool seq_test(struct test_info*); + + +static test_desc_t test_desc[] = { + { + .aggregate = true, + .type = T_OTHER, + .func = run_all_tests, + .name = "*", + .desc = "Runs all tests.", + }, + { + .aggregate = true, + .type = T_SANITY, + .func = run_sanity_tests, + .name = "sanity-tests", + .desc = "Runs all RCU sanity tests.", + }, + { + .aggregate = true, + .type = T_STRESS, + .func = run_stress_tests, + .name = "stress-tests", + .desc = "Runs all RCU stress tests.", + }, + + { + .aggregate = false, + .type = T_SANITY, + .func = basic_sanity_check, + .name = "basic-sanity", + .desc = "Locks/unlocks and syncs in 1 fibril, no contention.", + }, + { + .aggregate = false, + .type = T_SANITY, + .func = wait_for_one_reader, + .name = "wait-for-one", + .desc = "Syncs with one 2 secs sleeping reader.", + }, + { + .aggregate = false, + .type = T_SANITY, + .func = dont_wait_for_new_reader, + .name = "ignore-new-r", + .desc = "Syncs with preexisting reader; ignores new reader.", + }, + { + .aggregate = false, + .type = T_SANITY, + .func = wait_for_exiting_reader, + .name = "dereg-unlocks", + .desc = "Lets deregister_fibril unlock the reader section.", + }, + { + .aggregate = false, + .type = T_STRESS, + .func = seq_test, + .name = "seq", + .desc = "Checks lock/unlock/sync w/ global time sequence.", + }, + { + .aggregate = false, + .type = T_OTHER, + .func = NULL, + .name = "(null)", + .desc = "", + }, +}; + +static const size_t test_desc_cnt = sizeof(test_desc) / sizeof(test_desc[0]); + +/*--------------------------------------------------------------------*/ + +static size_t next_rand(size_t seed) +{ + return (seed * 1103515245 + 12345) & ((1U << 31) - 1); +} + + +typedef int (*fibril_func_t)(void *); + +static bool create_fibril(int (*func)(void*), void *arg) +{ + fid_t fid = fibril_create(func, arg); + + if (0 == fid) { + printf("Failed to create a fibril!\n"); + return false; + } + + fibril_add_ready(fid); + return true; +} + +/*--------------------------------------------------------------------*/ + +static bool run_tests(test_info_t *info, bool (*include_filter)(test_desc_t *)) +{ + size_t failed_cnt = 0; + size_t ok_cnt = 0; + + for (size_t i = 0; i < test_desc_cnt; ++i) { + test_desc_t *t = &test_desc[i]; + + if (t->func && !t->aggregate && include_filter(t)) { + printf("Running \'%s\'...\n", t->name); + bool ok = test_desc[i].func(info); + + if (ok) { + ++ok_cnt; + printf("Passed: \'%s\'\n", t->name); + } else { + ++failed_cnt; + printf("FAILED: \'%s\'\n", t->name); + } + } + } + + printf("\n"); + + printf("%zu tests passed\n", ok_cnt); + + if (failed_cnt) { + printf("%zu tests failed\n", failed_cnt); + } + + return 0 == failed_cnt; +} + +/*--------------------------------------------------------------------*/ + +static bool all_tests_include_filter(test_desc_t *desc) +{ + return true; +} + +/* Runs all available tests tests one-by-one. */ +static bool run_all_tests(test_info_t *test_info) +{ + printf("Running all tests...\n"); + return run_tests(test_info, all_tests_include_filter); +} + +/*--------------------------------------------------------------------*/ + +static bool stress_tests_include_filter(test_desc_t *desc) +{ + return desc->type == T_STRESS; +} + +/* Runs all available stress tests one-by-one. */ +static bool run_stress_tests(test_info_t *test_info) +{ + printf("Running stress tests...\n"); + return run_tests(test_info, stress_tests_include_filter); +} + +/*--------------------------------------------------------------------*/ + +static bool sanity_tests_include_filter(test_desc_t *desc) +{ + return desc->type == T_SANITY; +} + +/* Runs all available sanity tests one-by-one. */ +static bool run_sanity_tests(test_info_t *test_info) +{ + printf("Running sanity tests...\n"); + return run_tests(test_info, sanity_tests_include_filter); +} + +/*--------------------------------------------------------------------*/ + +/* Locks/unlocks rcu and synchronizes without contention in a single fibril. */ +static bool basic_sanity_check(test_info_t *test_info) +{ + rcu_read_lock(); + /* nop */ + rcu_read_unlock(); + + rcu_read_lock(); + /* nop */ + rcu_read_unlock(); + + rcu_synchronize(); + + /* Nested lock with yield(). */ + rcu_read_lock(); + fibril_yield(); + rcu_read_lock(); + fibril_yield(); + rcu_read_unlock(); + fibril_yield(); + rcu_read_unlock(); + + fibril_yield(); + rcu_synchronize(); + rcu_synchronize(); + + rcu_read_lock(); + /* nop */ + if (!rcu_read_locked()) + return false; + + rcu_read_unlock(); + + return !rcu_read_locked(); +} + +typedef struct one_reader_info { + bool entered_cs; + bool exited_cs; + size_t done_sleeps_cnt; + bool synching; + bool synched; + size_t failed; +} one_reader_info_t; + + +static int sleeping_reader(one_reader_info_t *arg) +{ + rcu_register_fibril(); + + printf("lock{"); + rcu_read_lock(); + rcu_read_lock(); + arg->entered_cs = true; + rcu_read_unlock(); + + printf("r-sleep{"); + /* 2 sec */ + async_usleep(2 * USECS_PER_SEC); + ++arg->done_sleeps_cnt; + printf("}"); + + if (arg->synched) { + arg->failed = 1; + printf("Error: rcu_sync exited prematurely.\n"); + } + + arg->exited_cs = true; + rcu_read_unlock(); + printf("}"); + + rcu_deregister_fibril(); + return 0; +} + +static bool wait_for_one_reader(test_info_t *test_info) +{ + one_reader_info_t info = { 0 }; + + if (!create_fibril((fibril_func_t) sleeping_reader, &info)) + return false; + + /* 1 sec, waits for the reader to enter its critical section and sleep. */ + async_usleep(1 * USECS_PER_SEC); + + if (!info.entered_cs || info.exited_cs) { + printf("Error: reader is unexpectedly outside of critical section.\n"); + return false; + } + + info.synching = true; + printf("sync["); + rcu_synchronize(); + printf("]\n"); + info.synched = true; + + /* Load info.exited_cs */ + memory_barrier(); + + if (!info.exited_cs || info.failed) { + printf("Error: rcu_sync() returned before the reader exited its CS.\n"); + /* + * Sleep some more so we don't free info on stack while the reader + * is using it. + */ + /* 1.5 sec */ + async_usleep(1500 * 1000); + return false; + } else { + return true; + } +} + +/*--------------------------------------------------------------------*/ + +#define WAIT_STEP_US 500 * USECS_PER_MS + +typedef struct two_reader_info { + bool new_entered_cs; + bool new_exited_cs; + bool old_entered_cs; + bool old_exited_cs; + bool synching; + bool synched; + size_t failed; +} two_reader_info_t; + + +static int preexisting_reader(two_reader_info_t *arg) +{ + rcu_register_fibril(); + + printf("old-lock{"); + rcu_read_lock(); + arg->old_entered_cs = true; + + printf("wait-for-sync{"); + /* Wait for rcu_sync() to start waiting for us. */ + while (!arg->synching) { + async_usleep(WAIT_STEP_US); + } + printf(" }"); + + /* A new reader starts while rcu_sync() is in progress. */ + + printf("wait-for-new-R{"); + /* Wait for the new reader to enter its reader section. */ + while (!arg->new_entered_cs) { + async_usleep(WAIT_STEP_US); + } + printf(" }"); + + arg->old_exited_cs = true; + + assert(!arg->new_exited_cs); + + if (arg->synched) { + arg->failed = 1; + printf("Error: rcu_sync() did not wait for preexisting reader.\n"); + } + + rcu_read_unlock(); + printf(" }"); + + rcu_deregister_fibril(); + return 0; +} + +static int new_reader(two_reader_info_t *arg) +{ + rcu_register_fibril(); + + /* Wait until rcu_sync() starts. */ + while (!arg->synching) { + async_usleep(WAIT_STEP_US); + } + + /* + * synching is set when rcu_sync() is about to be entered so wait + * some more to make sure it really does start executing. + */ + async_usleep(WAIT_STEP_US); + + printf("new-lock("); + rcu_read_lock(); + arg->new_entered_cs = true; + + /* Wait for rcu_sync() exit, ie stop waiting for the preexisting reader. */ + while (!arg->synched) { + async_usleep(WAIT_STEP_US); + } + + arg->new_exited_cs = true; + /* Write new_exited_cs before exiting reader section. */ + memory_barrier(); + + /* + * Preexisting reader should have exited by now, so rcu_synchronize() + * must have returned. + */ + if (!arg->old_exited_cs) { + arg->failed = 1; + printf("Error: preexisting reader should have exited by now!\n"); + } + + rcu_read_unlock(); + printf(")"); + + rcu_deregister_fibril(); + return 0; +} + +static bool dont_wait_for_new_reader(test_info_t *test_info) +{ + two_reader_info_t info = { 0 }; + + if (!create_fibril((fibril_func_t) preexisting_reader, &info)) + return false; + + if (!create_fibril((fibril_func_t) new_reader, &info)) + return false; + + /* Waits for the preexisting_reader to enter its CS.*/ + while (!info.old_entered_cs) { + async_usleep(WAIT_STEP_US); + } + + assert(!info.old_exited_cs); + assert(!info.new_entered_cs); + assert(!info.new_exited_cs); + + printf("sync["); + info.synching = true; + rcu_synchronize(); + printf(" ]"); + + /* Load info.exited_cs */ + memory_barrier(); + + if (!info.old_exited_cs) { + printf("Error: rcu_sync() returned before preexisting reader exited.\n"); + info.failed = 1; + } + + bool new_outside_cs = !info.new_entered_cs || info.new_exited_cs; + + /* Test if new reader is waiting in CS before setting synched. */ + compiler_barrier(); + info.synched = true; + + if (new_outside_cs) { + printf("Error: new reader CS held up rcu_sync(). (4)\n"); + info.failed = 1; + } else { + /* Wait for the new reader. */ + rcu_synchronize(); + + if (!info.new_exited_cs) { + printf("Error: 2nd rcu_sync() returned before new reader exited.\n"); + info.failed = 1; + } + + printf("\n"); + } + + if (info.failed) { + /* + * Sleep some more so we don't free info on stack while readers + * are using it. + */ + async_usleep(WAIT_STEP_US); + } + + return 0 == info.failed; +} + +#undef WAIT_STEP_US + +/*--------------------------------------------------------------------*/ +#define WAIT_STEP_US 500 * USECS_PER_MS + +typedef struct exit_reader_info { + bool entered_cs; + bool exited_cs; + bool synching; + bool synched; +} exit_reader_info_t; + + +static int exiting_locked_reader(exit_reader_info_t *arg) +{ + rcu_register_fibril(); + + printf("old-lock{"); + rcu_read_lock(); + rcu_read_lock(); + rcu_read_lock(); + arg->entered_cs = true; + + printf("wait-for-sync{"); + /* Wait for rcu_sync() to start waiting for us. */ + while (!arg->synching) { + async_usleep(WAIT_STEP_US); + } + printf(" }"); + + rcu_read_unlock(); + printf(" }"); + + arg->exited_cs = true; + /* Store exited_cs before unlocking reader section in deregister. */ + memory_barrier(); + + /* Deregister forcefully unlocks the reader section. */ + rcu_deregister_fibril(); + return 0; +} + + +static bool wait_for_exiting_reader(test_info_t *test_info) +{ + exit_reader_info_t info = { 0 }; + + if (!create_fibril((fibril_func_t) exiting_locked_reader, &info)) + return false; + + /* Waits for the preexisting_reader to enter its CS.*/ + while (!info.entered_cs) { + async_usleep(WAIT_STEP_US); + } + + assert(!info.exited_cs); + + printf("sync["); + info.synching = true; + rcu_synchronize(); + info.synched = true; + printf(" ]\n"); + + /* Load info.exited_cs */ + memory_barrier(); + + if (!info.exited_cs) { + printf("Error: rcu_deregister_fibril did not unlock the CS.\n"); + return false; + } + + return true; +} + +#undef WAIT_STEP_US + + +/*--------------------------------------------------------------------*/ + +typedef struct { + atomic_t time; + atomic_t max_start_time_of_done_sync; + + size_t total_workers; + size_t done_reader_cnt; + size_t done_updater_cnt; + fibril_mutex_t done_cnt_mtx; + fibril_condvar_t done_cnt_changed; + + size_t read_iters; + size_t upd_iters; + + atomic_t seed; + int failed; +} seq_test_info_t; + + +static void signal_seq_fibril_done(seq_test_info_t *arg, size_t *cnt) +{ + fibril_mutex_lock(&arg->done_cnt_mtx); + ++*cnt; + + if (arg->total_workers == arg->done_reader_cnt + arg->done_updater_cnt) { + fibril_condvar_signal(&arg->done_cnt_changed); + } + + fibril_mutex_unlock(&arg->done_cnt_mtx); +} + +static int seq_reader(seq_test_info_t *arg) +{ + rcu_register_fibril(); + + size_t seed = (size_t) atomic_preinc(&arg->seed); + bool first = (seed == 1); + + for (size_t k = 0; k < arg->read_iters; ++k) { + /* Print progress if the first reader fibril. */ + if (first && 0 == k % (arg->read_iters/100 + 1)) { + printf("."); + } + + rcu_read_lock(); + atomic_count_t start_time = atomic_preinc(&arg->time); + + /* Do some work. */ + seed = next_rand(seed); + size_t idle_iters = seed % 8; + + for (size_t i = 0; i < idle_iters; ++i) { + fibril_yield(); + } + + /* + * Check if the most recently started rcu_sync of the already + * finished rcu_syncs did not happen to start after this reader + * and, therefore, should have waited for this reader to exit + * (but did not - since it already announced it completed). + */ + if (start_time <= atomic_get(&arg->max_start_time_of_done_sync)) { + arg->failed = 1; + } + + rcu_read_unlock(); + } + + rcu_deregister_fibril(); + + signal_seq_fibril_done(arg, &arg->done_reader_cnt); + return 0; +} + +static int seq_updater(seq_test_info_t *arg) +{ + rcu_register_fibril(); + + for (size_t k = 0; k < arg->upd_iters; ++k) { + atomic_count_t start_time = atomic_get(&arg->time); + rcu_synchronize(); + + /* This is prone to a race but if it happens it errs to the safe side.*/ + if (atomic_get(&arg->max_start_time_of_done_sync) < start_time) { + atomic_set(&arg->max_start_time_of_done_sync, start_time); + } + } + + rcu_deregister_fibril(); + + signal_seq_fibril_done(arg, &arg->done_updater_cnt); + return 0; +} + +static bool seq_test(test_info_t *test_info) +{ + size_t reader_cnt = test_info->thread_cnt; + size_t updater_cnt = test_info->thread_cnt; + + seq_test_info_t info = { + .time = {0}, + .max_start_time_of_done_sync = {0}, + .read_iters = 10 * 1000, + .upd_iters = 5 * 1000, + .total_workers = updater_cnt + reader_cnt, + .done_reader_cnt = 0, + .done_updater_cnt = 0, + .done_cnt_mtx = FIBRIL_MUTEX_INITIALIZER(info.done_cnt_mtx), + .done_cnt_changed = FIBRIL_CONDVAR_INITIALIZER(info.done_cnt_changed), + .seed = {0}, + .failed = 0, + }; + + /* Create and start worker fibrils. */ + for (size_t k = 0; k + k < reader_cnt + updater_cnt; ++k) { + bool ok = create_fibril((fibril_func_t) seq_reader, &info); + ok = ok && create_fibril((fibril_func_t) seq_updater, &info); + + if (!ok) { + /* Let the already created fibrils corrupt the stack. */ + return false; + } + } + + /* Wait for all worker fibrils to complete their work. */ + fibril_mutex_lock(&info.done_cnt_mtx); + + while (info.total_workers != info.done_reader_cnt + info.done_updater_cnt) { + fibril_condvar_wait(&info.done_cnt_changed, &info.done_cnt_mtx); + } + + fibril_mutex_unlock(&info.done_cnt_mtx); + + if (info.failed) { + printf("Error: rcu_sync() did not wait for a preexisting reader."); + } + + return 0 == info.failed; +} + +/*--------------------------------------------------------------------*/ + +static FIBRIL_MUTEX_INITIALIZE(blocking_mtx); + +static void dummy_fibril(void *arg) +{ + /* Block on an already locked mutex - enters the fibril manager. */ + fibril_mutex_lock(&blocking_mtx); + assert(false); +} + +static bool create_threads(size_t cnt) +{ + /* Sanity check. */ + assert(cnt < 1024); + + /* Keep this mutex locked so that dummy fibrils never exit. */ + bool success = fibril_mutex_trylock(&blocking_mtx); + assert(success); + + for (size_t k = 0; k < cnt; ++k) { + thread_id_t tid; + + int ret = thread_create(dummy_fibril, NULL, "urcu-test-worker", &tid); + if (EOK != ret) { + printf("Failed to create thread '%zu' (error: %d)\n", k + 1, ret); + return false; + } + } + + return true; +} + +/*--------------------------------------------------------------------*/ +static test_desc_t *find_test(const char *name) +{ + /* First match for test name. */ + for (size_t k = 0; k < test_desc_cnt; ++k) { + test_desc_t *t = &test_desc[k]; + + if (t->func && 0 == str_cmp(t->name, name)) + return t; + } + + /* Try to match the test number. */ + uint32_t test_num = 0; + + if (EOK == str_uint32_t(name, NULL, 0, true, &test_num)) { + if (test_num < test_desc_cnt && test_desc[test_num].func) { + return &test_desc[test_num]; + } + } + + return NULL; +} + +static void list_tests(void) +{ + printf("Available tests: \n"); + + for (size_t i = 0; i < test_desc_cnt; ++i) { + test_desc_t *t = &test_desc[i]; + + if (!t->func) + continue; + + const char *type = ""; + + if (t->type == T_SANITY) + type = " (sanity)"; + if (t->type == T_STRESS) + type = " (stress)"; + + printf("%zu: %s ..%s %s\n", i, t->name, type, t->desc); + } +} + + +static void print_usage(void) +{ + printf("Usage: rcutest [test_name|test_number] {number_of_threads}\n"); + list_tests(); + + printf("\nExample usage:\n"); + printf("\trcutest *\n"); + printf("\trcutest sanity-tests\n"); +} + + +static bool parse_cmd_line(int argc, char **argv, test_info_t *info) +{ + if (argc != 2 && argc != 3) { + print_usage(); + return false; + } + + info->desc = find_test(argv[1]); + + if (!info->desc) { + printf("Non-existent test '%s'.\n", argv[1]); + list_tests(); + return false; + } + + if (argc == 3) { + uint32_t thread_cnt = 0; + int ret = str_uint32_t(argv[2], NULL, 0, true, &thread_cnt); + + if (ret == EOK && 1 <= thread_cnt && thread_cnt <= 64) { + info->thread_cnt = thread_cnt; + } else { + info->thread_cnt = 1; + printf("Err: Invalid number of threads '%s'; using 1.\n", argv[2]); + } + } else { + info->thread_cnt = 1; + } + + return true; +} + +int main(int argc, char **argv) +{ + rcu_register_fibril(); + + test_info_t info; + + bool ok = parse_cmd_line(argc, argv, &info); + ok = ok && create_threads(info.thread_cnt - 1); + + if (ok) { + assert(1 <= info.thread_cnt); + test_desc_t *t = info.desc; + + printf("Running '%s' (in %zu threads)...\n", t->name, info.thread_cnt); + ok = t->func(&info); + + printf("%s: '%s'\n", ok ? "Passed" : "FAILED", t->name); + + rcu_deregister_fibril(); + + /* Let the kernel clean up the created background threads. */ + return ok ? 0 : 1; + } else { + rcu_deregister_fibril(); + return 2; + } +} + + +/** + * @} + */ Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/Makefile (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -47,4 +47,7 @@ LSONAME = libc.so0 +LIBS = $(LIBURCU_PREFIX)/liburcu.a +EXTRA_CFLAGS += -I$(LIBURCU_PREFIX) + -include $(CONFIG_MAKEFILE) -include arch/$(UARCH)/Makefile.inc @@ -88,4 +91,5 @@ generic/pcb.c \ generic/smc.c \ + generic/smp_memory_barrier.c \ generic/thread.c \ generic/tls.c \ Index: uspace/lib/c/generic/adt/hash_table.c =================================================================== --- uspace/lib/c/generic/adt/hash_table.c (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/generic/adt/hash_table.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -134,5 +134,5 @@ free(h->bucket); - h->bucket = 0; + h->bucket = NULL; h->bucket_cnt = 0; } Index: uspace/lib/c/generic/async.c =================================================================== --- uspace/lib/c/generic/async.c (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/generic/async.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -167,5 +167,5 @@ /** Async framework global futex */ -atomic_t async_futex = FUTEX_INITIALIZER; +futex_t async_futex = FUTEX_INITIALIZER; /** Number of threads waiting for IPC in the kernel. */ Index: uspace/lib/c/generic/fibril.c =================================================================== --- uspace/lib/c/generic/fibril.c (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/generic/fibril.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -49,4 +49,9 @@ #include #include +#include + +#ifdef FUTEX_UPGRADABLE +#include +#endif /** @@ -54,5 +59,5 @@ * serialized_list and manager_list. */ -static atomic_t fibril_futex = FUTEX_INITIALIZER; +static futex_t fibril_futex = FUTEX_INITIALIZER; static LIST_INITIALIZE(ready_list); @@ -83,4 +88,8 @@ { fibril_t *fibril = __tcb_get()->fibril_data; + +#ifdef FUTEX_UPGRADABLE + rcu_register_fibril(); +#endif /* Call the implementing function. */ @@ -146,5 +155,5 @@ int retval = 0; - futex_down(&fibril_futex); + futex_lock(&fibril_futex); if (stype == FIBRIL_PREEMPT && list_empty(&ready_list)) @@ -168,7 +177,7 @@ if ((stype == FIBRIL_TO_MANAGER) || (stype == FIBRIL_FROM_DEAD)) { while (list_empty(&manager_list)) { - futex_up(&fibril_futex); + futex_unlock(&fibril_futex); async_create_manager(); - futex_down(&fibril_futex); + futex_lock(&fibril_futex); } } @@ -203,5 +212,5 @@ } - return 1; /* futex_up already done here */ + return 1; /* futex_unlock already done here */ } @@ -246,10 +255,17 @@ list_remove(&dstf->link); - futex_up(&fibril_futex); + futex_unlock(&fibril_futex); + +#ifdef FUTEX_UPGRADABLE + if (stype == FIBRIL_FROM_DEAD) { + rcu_deregister_fibril(); + } +#endif + context_restore(&dstf->ctx); /* not reached */ ret_0: - futex_up(&fibril_futex); + futex_unlock(&fibril_futex); return retval; } @@ -318,5 +334,5 @@ fibril_t *fibril = (fibril_t *) fid; - futex_down(&fibril_futex); + futex_lock(&fibril_futex); if ((fibril->flags & FIBRIL_SERIALIZED)) @@ -325,5 +341,5 @@ list_append(&fibril->link, &ready_list); - futex_up(&fibril_futex); + futex_unlock(&fibril_futex); } @@ -338,7 +354,7 @@ fibril_t *fibril = (fibril_t *) fid; - futex_down(&fibril_futex); + futex_lock(&fibril_futex); list_append(&fibril->link, &manager_list); - futex_up(&fibril_futex); + futex_unlock(&fibril_futex); } @@ -346,10 +362,10 @@ void fibril_remove_manager(void) { - futex_down(&fibril_futex); + futex_lock(&fibril_futex); if (!list_empty(&manager_list)) list_remove(list_first(&manager_list)); - futex_up(&fibril_futex); + futex_unlock(&fibril_futex); } Index: uspace/lib/c/generic/futex.c =================================================================== --- uspace/lib/c/generic/futex.c (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/generic/futex.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -35,7 +35,4 @@ #include #include -#include -#include -#include /** Initialize futex counter. @@ -47,63 +44,26 @@ void futex_initialize(futex_t *futex, int val) { - atomic_set(futex, val); + atomic_set(&futex->val, val); } -/** Try to down the futex. - * - * @param futex Futex. - * - * @return Non-zero if the futex was acquired. - * @return Zero if the futex was not acquired. - * - */ -int futex_trydown(futex_t *futex) + +#ifdef FUTEX_UPGRADABLE + +int _upgrade_futexes = 0; +static futex_t upg_and_wait_futex = FUTEX_INITIALIZER; + +void futex_upgrade_all_and_wait(void) { - int rc; - - rc = cas(futex, 1, 0); - CS_ENTER_BARRIER(); - - return rc; + futex_down(&upg_and_wait_futex); + + if (!_upgrade_futexes) { + rcu_assign(_upgrade_futexes, 1); + _rcu_synchronize(BM_BLOCK_THREAD); + } + + futex_up(&upg_and_wait_futex); } -/** Down the futex. - * - * @param futex Futex. - * - * @return ENOENT if there is no such virtual address. - * @return Zero in the uncontended case. - * @return Otherwise one of ESYNCH_OK_ATOMIC or ESYNCH_OK_BLOCKED. - * - */ -int futex_down(futex_t *futex) -{ - atomic_signed_t nv; - - nv = (atomic_signed_t) atomic_predec(futex); - CS_ENTER_BARRIER(); - if (nv < 0) - return __SYSCALL1(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count); - - return 0; -} - -/** Up the futex. - * - * @param futex Futex. - * - * @return ENOENT if there is no such virtual address. - * @return Zero in the uncontended case. - * - */ -int futex_up(futex_t *futex) -{ - CS_LEAVE_BARRIER(); - - if ((atomic_signed_t) atomic_postinc(futex) < 0) - return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count); - - return 0; -} +#endif /** @} Index: uspace/lib/c/generic/ipc.c =================================================================== --- uspace/lib/c/generic/ipc.c (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/generic/ipc.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -81,5 +81,5 @@ LIST_INITIALIZE(queued_calls); -static atomic_t ipc_futex = FUTEX_INITIALIZER; +static futex_t ipc_futex = FUTEX_INITIALIZER; /** Send asynchronous message via syscall. @@ -136,10 +136,10 @@ if (!call) { /* Nothing to do regardless if failed or not */ - futex_up(&ipc_futex); + futex_unlock(&ipc_futex); return; } if (callid == (ipc_callid_t) IPC_CALLRET_FATAL) { - futex_up(&ipc_futex); + futex_unlock(&ipc_futex); /* Call asynchronous handler with error code */ @@ -152,5 +152,5 @@ if (callid == (ipc_callid_t) IPC_CALLRET_TEMPORARY) { - futex_up(&ipc_futex); + futex_unlock(&ipc_futex); call->u.msg.phoneid = phoneid; @@ -175,5 +175,5 @@ /* Add call to the list of dispatched calls */ list_append(&call->list, &dispatched_calls); - futex_up(&ipc_futex); + futex_unlock(&ipc_futex); } @@ -219,5 +219,5 @@ */ - futex_down(&ipc_futex); + futex_lock(&ipc_futex); ipc_callid_t callid = __SYSCALL6(SYS_IPC_CALL_ASYNC_FAST, phoneid, imethod, arg1, arg2, arg3, arg4); @@ -226,6 +226,8 @@ if (!call) { call = ipc_prepare_async(private, callback); - if (!call) + if (!call) { + futex_unlock(&ipc_futex); return; + } } @@ -289,5 +291,5 @@ */ - futex_down(&ipc_futex); + futex_lock(&ipc_futex); ipc_callid_t callid = ipc_call_async_internal(phoneid, &call->u.msg.data); @@ -384,7 +386,7 @@ call->u.callid = callid; - futex_down(&ipc_futex); + futex_lock(&ipc_futex); list_append(&call->list, &dispatched_calls); - futex_up(&ipc_futex); + futex_unlock(&ipc_futex); } @@ -412,5 +414,5 @@ callid &= ~IPC_CALLID_ANSWERED; - futex_down(&ipc_futex); + futex_lock(&ipc_futex); link_t *item; @@ -423,5 +425,5 @@ list_remove(&call->list); - futex_up(&ipc_futex); + futex_unlock(&ipc_futex); if (call->callback) @@ -434,5 +436,5 @@ } - futex_up(&ipc_futex); + futex_unlock(&ipc_futex); } Index: uspace/lib/c/generic/libc.c =================================================================== --- uspace/lib/c/generic/libc.c (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/generic/libc.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -52,7 +52,12 @@ #include "private/io.h" +#ifdef FUTEX_UPGRADABLE +#include +#endif + #ifdef CONFIG_RTLD #include #endif + static bool env_setup = false; @@ -62,5 +67,4 @@ /* Initialize user task run-time environment */ __malloc_init(); - __async_init(); fibril_t *fibril = fibril_setup(); @@ -72,4 +76,10 @@ /* Save the PCB pointer */ __pcb = (pcb_t *) pcb_ptr; + +#ifdef FUTEX_UPGRADABLE + rcu_register_fibril(); +#endif + + __async_init(); /* The basic run-time environment is setup */ Index: uspace/lib/c/generic/malloc.c =================================================================== --- uspace/lib/c/generic/malloc.c (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/generic/malloc.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -200,5 +200,5 @@ do { \ if (!(expr)) {\ - futex_up(&malloc_futex); \ + heap_unlock(); \ assert_abort(#expr, __FILE__, __LINE__); \ } \ @@ -210,4 +210,69 @@ #endif /* NDEBUG */ + + +#ifdef FUTEX_UPGRADABLE +/** True if the heap may be accessed from multiple threads. */ +static bool multithreaded = false; + +/** Makes accesses to the heap thread safe. */ +void malloc_enable_multithreaded(void) +{ + multithreaded = true; +} + +/** Serializes access to the heap from multiple threads. */ +static inline void heap_lock(void) +{ + if (multithreaded) { + futex_down(&malloc_futex); + } else { + /* + * Malloc never switches fibrils while the heap is locked. + * Similarly, it never creates new threads from within the + * locked region. Therefore, if there are no other threads + * except this one, the whole operation will complete without + * any interruptions. + */ + } +} + +/** Serializes access to the heap from multiple threads. */ +static inline void heap_unlock(void) +{ + if (multithreaded) { + futex_up(&malloc_futex); + } else { + /* + * Malloc never switches fibrils while the heap is locked. + * Similarly, it never creates new threads from within the + * locked region. Therefore, if there are no other threads + * except this one, the whole operation will complete without + * any interruptions. + */ + } +} + +#else + +/** Makes accesses to the heap thread safe. */ +void malloc_enable_multithreaded(void) +{ + /* No-op. Already using thread-safe heap locking operations. */ +} + +/** Serializes access to the heap from multiple threads. */ +static inline void heap_lock(void) +{ + futex_down(&malloc_futex); +} + +/** Serializes access to the heap from multiple threads. */ +static inline void heap_unlock(void) +{ + futex_up(&malloc_futex); +} +#endif + /** Initialize a heap block @@ -785,8 +850,8 @@ void *malloc(const size_t size) { - futex_down(&malloc_futex); + heap_lock(); void *block = malloc_internal(size, BASE_ALIGN); - futex_up(&malloc_futex); - + heap_unlock(); + return block; } @@ -807,9 +872,9 @@ size_t palign = 1 << (fnzb(max(sizeof(void *), align) - 1) + 1); - - futex_down(&malloc_futex); + + heap_lock(); void *block = malloc_internal(size, palign); - futex_up(&malloc_futex); - + heap_unlock(); + return block; } @@ -828,5 +893,5 @@ return malloc(size); - futex_down(&malloc_futex); + heap_lock(); /* Calculate the position of the header. */ @@ -885,5 +950,5 @@ } - futex_up(&malloc_futex); + heap_unlock(); if (reloc) { @@ -908,5 +973,5 @@ return; - futex_down(&malloc_futex); + heap_lock(); /* Calculate the position of the header. */ @@ -953,13 +1018,13 @@ heap_shrink(area); - futex_up(&malloc_futex); + heap_unlock(); } void *heap_check(void) { - futex_down(&malloc_futex); + heap_lock(); if (first_heap_area == NULL) { - futex_up(&malloc_futex); + heap_unlock(); return (void *) -1; } @@ -975,5 +1040,5 @@ (((uintptr_t) area->start % PAGE_SIZE) != 0) || (((uintptr_t) area->end % PAGE_SIZE) != 0)) { - futex_up(&malloc_futex); + heap_unlock(); return (void *) area; } @@ -986,5 +1051,5 @@ /* Check heap block consistency */ if (head->magic != HEAP_BLOCK_HEAD_MAGIC) { - futex_up(&malloc_futex); + heap_unlock(); return (void *) head; } @@ -994,5 +1059,5 @@ if ((foot->magic != HEAP_BLOCK_FOOT_MAGIC) || (head->size != foot->size)) { - futex_up(&malloc_futex); + heap_unlock(); return (void *) foot; } @@ -1000,5 +1065,5 @@ } - futex_up(&malloc_futex); + heap_unlock(); return NULL; Index: uspace/lib/c/generic/smp_memory_barrier.c =================================================================== --- uspace/lib/c/generic/smp_memory_barrier.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/lib/c/generic/smp_memory_barrier.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ + +#include +#include + +void smp_memory_barrier(void) +{ + __SYSCALL0(SYS_SMP_MEMORY_BARRIER); +} + +/** @} + */ Index: uspace/lib/c/generic/thread.c =================================================================== --- uspace/lib/c/generic/thread.c (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/generic/thread.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -46,4 +46,9 @@ #include "private/thread.h" +#ifdef FUTEX_UPGRADABLE +#include +#endif + + /** Main thread function. * @@ -63,4 +68,9 @@ __tcb_set(fibril->tcb); +#ifdef FUTEX_UPGRADABLE + rcu_register_fibril(); + futex_upgrade_all_and_wait(); +#endif + uarg->uspace_thread_function(uarg->uspace_thread_arg); /* @@ -73,4 +83,9 @@ /* If there is a manager, destroy it */ async_destroy_manager(); + +#ifdef FUTEX_UPGRADABLE + rcu_deregister_fibril(); +#endif + fibril_teardown(fibril); @@ -106,4 +121,7 @@ return ENOMEM; } + + /* Make heap thread safe. */ + malloc_enable_multithreaded(); uarg->uspace_entry = (void *) FADDR(__thread_entry); Index: uspace/lib/c/include/adt/list.h =================================================================== --- uspace/lib/c/include/adt/list.h (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/include/adt/list.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -58,5 +58,23 @@ */ #define LIST_INITIALIZE(name) \ - list_t name = { \ + list_t name = LIST_INITIALIZER(name) + +/** Initializer for statically allocated list. + * + * @code + * struct named_list { + * const char *name; + * list_t list; + * } var = { + * .name = "default name", + * .list = LIST_INITIALIZER(name_list.list) + * }; + * @endcode + * + * @param name Name of the new statically allocated list. + * + */ +#define LIST_INITIALIZER(name) \ + { \ .head = { \ .prev = &(name).head, \ Index: uspace/lib/c/include/compiler/barrier.h =================================================================== --- uspace/lib/c/include/compiler/barrier.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/lib/c/include/compiler/barrier.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ + +#ifndef LIBC_COMPILER_BARRIER_H_ +#define LIBC_COMPILER_BARRIER_H_ + +#define compiler_barrier() asm volatile ("" ::: "memory") + +/** Forces the compiler to access (ie load/store) the variable only once. */ +#define ACCESS_ONCE(var) (*((volatile typeof(var)*)&(var))) + +#endif /* LIBC_COMPILER_BARRIER_H_ */ Index: uspace/lib/c/include/futex.h =================================================================== --- uspace/lib/c/include/futex.h (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/include/futex.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -38,13 +38,115 @@ #include #include +#include -#define FUTEX_INITIALIZER {1} +typedef struct futex { + atomic_t val; +#ifdef FUTEX_UPGRADABLE + int upgraded; +#endif +} futex_t; -typedef atomic_t futex_t; extern void futex_initialize(futex_t *futex, int value); -extern int futex_down(futex_t *futex); -extern int futex_trydown(futex_t *futex); -extern int futex_up(futex_t *futex); + +#ifdef FUTEX_UPGRADABLE +#include + +#define FUTEX_INITIALIZE(val) {{ (val) }, 0} + +#define futex_lock(fut) \ +({ \ + rcu_read_lock(); \ + (fut)->upgraded = rcu_access(_upgrade_futexes); \ + if ((fut)->upgraded) \ + (void) futex_down((fut)); \ +}) + +#define futex_trylock(fut) \ +({ \ + rcu_read_lock(); \ + int _upgraded = rcu_access(_upgrade_futexes); \ + if (_upgraded) { \ + int _acquired = futex_trydown((fut)); \ + if (!_acquired) { \ + rcu_read_unlock(); \ + } else { \ + (fut)->upgraded = true; \ + } \ + _acquired; \ + } else { \ + (fut)->upgraded = false; \ + 1; \ + } \ +}) + +#define futex_unlock(fut) \ +({ \ + if ((fut)->upgraded) \ + (void) futex_up((fut)); \ + rcu_read_unlock(); \ +}) + +extern int _upgrade_futexes; + +extern void futex_upgrade_all_and_wait(void); + +#else + +#define FUTEX_INITIALIZE(val) {{ (val) }} + +#define futex_lock(fut) (void) futex_down((fut)) +#define futex_trylock(fut) futex_trydown((fut)) +#define futex_unlock(fut) (void) futex_up((fut)) + +#endif + +#define FUTEX_INITIALIZER FUTEX_INITIALIZE(1) + +/** Try to down the futex. + * + * @param futex Futex. + * + * @return Non-zero if the futex was acquired. + * @return Zero if the futex was not acquired. + * + */ +static inline int futex_trydown(futex_t *futex) +{ + return cas(&futex->val, 1, 0); +} + +/** Down the futex. + * + * @param futex Futex. + * + * @return ENOENT if there is no such virtual address. + * @return Zero in the uncontended case. + * @return Otherwise one of ESYNCH_OK_ATOMIC or ESYNCH_OK_BLOCKED. + * + */ +static inline int futex_down(futex_t *futex) +{ + if ((atomic_signed_t) atomic_predec(&futex->val) < 0) + return __SYSCALL1(SYS_FUTEX_SLEEP, (sysarg_t) &futex->val.count); + + return 0; +} + +/** Up the futex. + * + * @param futex Futex. + * + * @return ENOENT if there is no such virtual address. + * @return Zero in the uncontended case. + * + */ +static inline int futex_up(futex_t *futex) +{ + if ((atomic_signed_t) atomic_postinc(&futex->val) < 0) + return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->val.count); + + return 0; +} #endif Index: uspace/lib/c/include/ipc/common.h =================================================================== --- uspace/lib/c/include/ipc/common.h (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/include/ipc/common.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -40,4 +40,5 @@ #include #include +#include #define IPC_FLAG_BLOCKING 0x01 @@ -51,5 +52,5 @@ typedef sysarg_t ipc_callid_t; -extern atomic_t async_futex; +extern futex_t async_futex; #endif Index: uspace/lib/c/include/malloc.h =================================================================== --- uspace/lib/c/include/malloc.h (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/include/malloc.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -48,4 +48,5 @@ extern void *heap_check(void); +extern void malloc_enable_multithreaded(void); #endif Index: uspace/lib/c/include/rwlock.h =================================================================== --- uspace/lib/c/include/rwlock.h (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/include/rwlock.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -49,8 +49,8 @@ #define rwlock_initialize(rwlock) futex_initialize((rwlock), 1) -#define rwlock_read_lock(rwlock) futex_down((rwlock)) -#define rwlock_write_lock(rwlock) futex_down((rwlock)) -#define rwlock_read_unlock(rwlock) futex_up((rwlock)) -#define rwlock_write_unlock(rwlock) futex_up((rwlock)) +#define rwlock_read_lock(rwlock) futex_lock((rwlock)) +#define rwlock_write_lock(rwlock) futex_lock((rwlock)) +#define rwlock_read_unlock(rwlock) futex_unlock((rwlock)) +#define rwlock_write_unlock(rwlock) futex_unlock((rwlock)) #endif Index: uspace/lib/c/include/smp_memory_barrier.h =================================================================== --- uspace/lib/c/include/smp_memory_barrier.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/lib/c/include/smp_memory_barrier.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ + +#ifndef LIBC_SMP_MEM_BAR_H_ +#define LIBC_SMP_MEM_BAR_H_ + +extern void smp_memory_barrier(void); + +#endif + +/** @} + */ Index: uspace/lib/c/include/sys/time.h =================================================================== --- uspace/lib/c/include/sys/time.h (revision 21799398fb5b1afa28852a26b87fcf58caf15a28) +++ uspace/lib/c/include/sys/time.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -79,4 +79,5 @@ extern void udelay(useconds_t); +extern int usleep(useconds_t); extern time_t mktime(struct tm *tm); Index: uspace/lib/urcu/Makefile =================================================================== --- uspace/lib/urcu/Makefile (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/lib/urcu/Makefile (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,40 @@ +# +# Copyright (c) 2012 Adam Hraska +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - 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. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. +# + +USPACE_PREFIX = ../.. + +LIBS = $(LIBC_PREFIX)/libc.a + +EXTRA_CFLAGS = -I. -I$(LIBC_PREFIX)/include + +LIBRARY = liburcu + +SOURCES = \ + rcu.c + +include $(USPACE_PREFIX)/Makefile.common Index: uspace/lib/urcu/rcu.c =================================================================== --- uspace/lib/urcu/rcu.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/lib/urcu/rcu.c (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,465 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. + */ + +/** @addtogroup liburcu + * @{ + */ +/** + * @file + * + * User space RCU is based on URCU utilizing signals [1]. This + * implementation does not however signal each thread of the process + * to issue a memory barrier. Instead, we introduced a syscall that + * issues memory barriers (via IPIs) on cpus that are running threads + * of the current process. First, it does not require us to schedule + * and run every thread of the process. Second, IPIs are less intrusive + * than switching contexts and entering user space. + * + * This algorithm is further modified to require a single instead of + * two reader group changes per grace period. Signal-URCU flips + * the reader group and waits for readers of the previous group + * twice in succession in order to wait for new readers that were + * delayed and mistakenly associated with the previous reader group. + * The modified algorithm ensures that the new reader group is + * always empty (by explicitly waiting for it to become empty). + * Only then does it flip the reader group and wait for preexisting + * readers of the old reader group (invariant of SRCU [2, 3]). + * + * + * [1] User-level implementations of read-copy update, + * 2012, appendix + * http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf + * + * [2] linux/kernel/srcu.c in Linux 3.5-rc2, + * 2012 + * http://tomoyo.sourceforge.jp/cgi-bin/lxr/source/kernel/srcu.c?v=linux-3.5-rc2-ccs-1.8.3 + * + * [3] [RFC PATCH 5/5 single-thread-version] implement + * per-domain single-thread state machine, + * 2012, Lai + * https://lkml.org/lkml/2012/3/6/586 + */ + +#include "rcu.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + + +/** RCU sleeps for RCU_SLEEP_MS before polling an active RCU reader again. */ +#define RCU_SLEEP_MS 10 + +#define RCU_NESTING_SHIFT 1 +#define RCU_NESTING_INC (1 << RCU_NESTING_SHIFT) +#define RCU_GROUP_BIT_MASK (size_t)(RCU_NESTING_INC - 1) +#define RCU_GROUP_A (size_t)(0 | RCU_NESTING_INC) +#define RCU_GROUP_B (size_t)(1 | RCU_NESTING_INC) + + +/** Fibril local RCU data. */ +typedef struct fibril_rcu_data { + size_t nesting_cnt; + link_t link; + bool registered; +} fibril_rcu_data_t; + +/** Process global RCU data. */ +typedef struct rcu_data { + size_t cur_gp; + size_t reader_group; + futex_t list_futex; + list_t fibrils_list; + struct { + futex_t futex; + bool locked; + list_t blocked_fibrils; + size_t blocked_thread_cnt; + futex_t futex_blocking_threads; + } sync_lock; +} rcu_data_t; + +typedef struct blocked_fibril { + fid_t id; + link_t link; + bool is_ready; +} blocked_fibril_t; + + +/** Fibril local RCU data. */ +static fibril_local fibril_rcu_data_t fibril_rcu = { + .nesting_cnt = 0, + .link = { + .next = NULL, + .prev = NULL + }, + .registered = false +}; + +/** Process global RCU data. */ +static rcu_data_t rcu = { + .cur_gp = 0, + .reader_group = RCU_GROUP_A, + .list_futex = FUTEX_INITIALIZER, + .fibrils_list = LIST_INITIALIZER(rcu.fibrils_list), + .sync_lock = { + .futex = FUTEX_INITIALIZER, + .locked = false, + .blocked_fibrils = LIST_INITIALIZER(rcu.sync_lock.blocked_fibrils), + .blocked_thread_cnt = 0, + .futex_blocking_threads = FUTEX_INITIALIZE(0), + }, +}; + + +static void wait_for_readers(size_t reader_group, blocking_mode_t blocking_mode); +static void force_mb_in_all_threads(void); +static bool is_preexisting_reader(const fibril_rcu_data_t *fib, size_t group); + +static void lock_sync(blocking_mode_t blocking_mode); +static void unlock_sync(void); +static void sync_sleep(blocking_mode_t blocking_mode); + +static bool is_in_group(size_t nesting_cnt, size_t group); +static bool is_in_reader_section(size_t nesting_cnt); +static size_t get_other_group(size_t group); + + +/** Registers a fibril so it may start using RCU read sections. + * + * A fibril must be registered with rcu before it can enter RCU critical + * sections delineated by rcu_read_lock() and rcu_read_unlock(). + */ +void rcu_register_fibril(void) +{ + assert(!fibril_rcu.registered); + + futex_down(&rcu.list_futex); + list_append(&fibril_rcu.link, &rcu.fibrils_list); + futex_up(&rcu.list_futex); + + fibril_rcu.registered = true; +} + +/** Deregisters a fibril that had been using RCU read sections. + * + * A fibril must be deregistered before it exits if it had + * been registered with rcu via rcu_register_fibril(). + */ +void rcu_deregister_fibril(void) +{ + assert(fibril_rcu.registered); + + /* + * Forcefully unlock any reader sections. The fibril is exiting + * so it is not holding any references to data protected by the + * rcu section. Therefore, it is safe to unlock. Otherwise, + * rcu_synchronize() would wait indefinitely. + */ + memory_barrier(); + fibril_rcu.nesting_cnt = 0; + + futex_down(&rcu.list_futex); + list_remove(&fibril_rcu.link); + futex_up(&rcu.list_futex); + + fibril_rcu.registered = false; +} + +/** Delimits the start of an RCU reader critical section. + * + * RCU reader sections may be nested. + */ +void rcu_read_lock(void) +{ + assert(fibril_rcu.registered); + + size_t nesting_cnt = ACCESS_ONCE(fibril_rcu.nesting_cnt); + + if (0 == (nesting_cnt >> RCU_NESTING_SHIFT)) { + ACCESS_ONCE(fibril_rcu.nesting_cnt) = ACCESS_ONCE(rcu.reader_group); + /* Required by MB_FORCE_L */ + compiler_barrier(); /* CC_BAR_L */ + } else { + ACCESS_ONCE(fibril_rcu.nesting_cnt) = nesting_cnt + RCU_NESTING_INC; + } +} + +/** Delimits the start of an RCU reader critical section. */ +void rcu_read_unlock(void) +{ + assert(fibril_rcu.registered); + assert(rcu_read_locked()); + + /* Required by MB_FORCE_U */ + compiler_barrier(); /* CC_BAR_U */ + /* todo: ACCESS_ONCE(nesting_cnt) ? */ + fibril_rcu.nesting_cnt -= RCU_NESTING_INC; +} + +/** Returns true if the current fibril is in an RCU reader section. */ +bool rcu_read_locked(void) +{ + return 0 != (fibril_rcu.nesting_cnt >> RCU_NESTING_SHIFT); +} + +/** Blocks until all preexisting readers exit their critical sections. */ +void _rcu_synchronize(blocking_mode_t blocking_mode) +{ + assert(!rcu_read_locked()); + + /* Contain load of rcu.cur_gp. */ + memory_barrier(); + + /* Approximately the number of the GP in progress. */ + size_t gp_in_progress = ACCESS_ONCE(rcu.cur_gp); + + lock_sync(blocking_mode); + + /* + * Exit early if we were stuck waiting for the mutex for a full grace + * period. Started waiting during gp_in_progress (or gp_in_progress + 1 + * if the value propagated to this cpu too late) so wait for the next + * full GP, gp_in_progress + 1, to finish. Ie don't wait if the GP + * after that, gp_in_progress + 2, already started. + */ + /* rcu.cur_gp >= gp_in_progress + 2, but tolerates overflows. */ + if (rcu.cur_gp != gp_in_progress && rcu.cur_gp + 1 != gp_in_progress) { + unlock_sync(); + return; + } + + ++ACCESS_ONCE(rcu.cur_gp); + + /* + * Pairs up with MB_FORCE_L (ie CC_BAR_L). Makes changes prior + * to rcu_synchronize() visible to new readers. + */ + memory_barrier(); /* MB_A */ + + /* + * Pairs up with MB_A. + * + * If the memory barrier is issued before CC_BAR_L in the target + * thread, it pairs up with MB_A and the thread sees all changes + * prior to rcu_synchronize(). Ie any reader sections are new + * rcu readers. + * + * If the memory barrier is issued after CC_BAR_L, it pairs up + * with MB_B and it will make the most recent nesting_cnt visible + * in this thread. Since the reader may have already accessed + * memory protected by RCU (it ran instructions passed CC_BAR_L), + * it is a preexisting reader. Seeing the most recent nesting_cnt + * ensures the thread will be identified as a preexisting reader + * and we will wait for it in wait_for_readers(old_reader_group). + */ + force_mb_in_all_threads(); /* MB_FORCE_L */ + + /* + * Pairs with MB_FORCE_L (ie CC_BAR_L, CC_BAR_U) and makes the most + * current fibril.nesting_cnt visible to this cpu. + */ + read_barrier(); /* MB_B */ + + size_t new_reader_group = get_other_group(rcu.reader_group); + wait_for_readers(new_reader_group, blocking_mode); + + /* Separates waiting for readers in new_reader_group from group flip. */ + memory_barrier(); + + /* Flip the group new readers should associate with. */ + size_t old_reader_group = rcu.reader_group; + rcu.reader_group = new_reader_group; + + /* Flip the group before waiting for preexisting readers in the old group.*/ + memory_barrier(); + + wait_for_readers(old_reader_group, blocking_mode); + + /* MB_FORCE_U */ + force_mb_in_all_threads(); /* MB_FORCE_U */ + + unlock_sync(); +} + +/** Issues a memory barrier in each thread of this process. */ +static void force_mb_in_all_threads(void) +{ + /* + * Only issue barriers in running threads. The scheduler will + * execute additional memory barriers when switching to threads + * of the process that are currently not running. + */ + smp_memory_barrier(); +} + +/** Waits for readers of reader_group to exit their readers sections. */ +static void wait_for_readers(size_t reader_group, blocking_mode_t blocking_mode) +{ + futex_down(&rcu.list_futex); + + list_t quiescent_fibrils; + list_initialize(&quiescent_fibrils); + + while (!list_empty(&rcu.fibrils_list)) { + list_foreach_safe(rcu.fibrils_list, fibril_it, next_fibril) { + fibril_rcu_data_t *fib = member_to_inst(fibril_it, + fibril_rcu_data_t, link); + + if (is_preexisting_reader(fib, reader_group)) { + futex_up(&rcu.list_futex); + sync_sleep(blocking_mode); + futex_down(&rcu.list_futex); + /* Break to while loop. */ + break; + } else { + list_remove(fibril_it); + list_append(fibril_it, &quiescent_fibrils); + } + } + } + + list_concat(&rcu.fibrils_list, &quiescent_fibrils); + futex_up(&rcu.list_futex); +} + +static void lock_sync(blocking_mode_t blocking_mode) +{ + futex_down(&rcu.sync_lock.futex); + if (rcu.sync_lock.locked) { + if (blocking_mode == BM_BLOCK_FIBRIL) { + blocked_fibril_t blocked_fib; + blocked_fib.id = fibril_get_id(); + + list_append(&blocked_fib.link, &rcu.sync_lock.blocked_fibrils); + + do { + blocked_fib.is_ready = false; + futex_up(&rcu.sync_lock.futex); + fibril_switch(FIBRIL_TO_MANAGER); + futex_down(&rcu.sync_lock.futex); + } while (rcu.sync_lock.locked); + + list_remove(&blocked_fib.link); + rcu.sync_lock.locked = true; + } else { + assert(blocking_mode == BM_BLOCK_THREAD); + rcu.sync_lock.blocked_thread_cnt++; + futex_up(&rcu.sync_lock.futex); + futex_down(&rcu.sync_lock.futex_blocking_threads); + } + } else { + rcu.sync_lock.locked = true; + } +} + +static void unlock_sync(void) +{ + assert(rcu.sync_lock.locked); + + /* + * Blocked threads have a priority over fibrils when accessing sync(). + * Pass the lock onto a waiting thread. + */ + if (0 < rcu.sync_lock.blocked_thread_cnt) { + --rcu.sync_lock.blocked_thread_cnt; + futex_up(&rcu.sync_lock.futex_blocking_threads); + } else { + /* Unlock but wake up any fibrils waiting for the lock. */ + + if (!list_empty(&rcu.sync_lock.blocked_fibrils)) { + blocked_fibril_t *blocked_fib = member_to_inst( + list_first(&rcu.sync_lock.blocked_fibrils), blocked_fibril_t, link); + + if (!blocked_fib->is_ready) { + blocked_fib->is_ready = true; + fibril_add_ready(blocked_fib->id); + } + } + + rcu.sync_lock.locked = false; + futex_up(&rcu.sync_lock.futex); + } +} + +static void sync_sleep(blocking_mode_t blocking_mode) +{ + assert(rcu.sync_lock.locked); + /* + * Release the futex to avoid deadlocks in singlethreaded apps + * but keep sync locked. + */ + futex_up(&rcu.sync_lock.futex); + + if (blocking_mode == BM_BLOCK_FIBRIL) { + async_usleep(RCU_SLEEP_MS * 1000); + } else { + usleep(RCU_SLEEP_MS * 1000); + } + + futex_down(&rcu.sync_lock.futex); +} + + +static bool is_preexisting_reader(const fibril_rcu_data_t *fib, size_t group) +{ + size_t nesting_cnt = ACCESS_ONCE(fib->nesting_cnt); + + return is_in_group(nesting_cnt, group) && is_in_reader_section(nesting_cnt); +} + +static size_t get_other_group(size_t group) +{ + if (group == RCU_GROUP_A) + return RCU_GROUP_B; + else + return RCU_GROUP_A; +} + +static bool is_in_reader_section(size_t nesting_cnt) +{ + return RCU_NESTING_INC <= nesting_cnt; +} + +static bool is_in_group(size_t nesting_cnt, size_t group) +{ + return (nesting_cnt & RCU_GROUP_BIT_MASK) == (group & RCU_GROUP_BIT_MASK); +} + + + +/** @} + */ Index: uspace/lib/urcu/rcu.h =================================================================== --- uspace/lib/urcu/rcu.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) +++ uspace/lib/urcu/rcu.h (revision b1c57a828cb73794beb6a309f5ec0199ca75ecc2) @@ -0,0 +1,114 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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. + */ + +/** @addtogroup liburcu + * @{ + */ +/** + * @file + */ + +#ifndef LIBURCU_RCU_H_ +#define LIBURCU_RCU_H_ + +#include +#include +#include + +/** Use to assign a pointer to newly initialized data to a rcu reader + * accessible pointer. + * + * Example: + * @code + * typedef struct exam { + * struct exam *next; + * int grade; + * } exam_t; + * + * exam_t *exam_list; + * // .. + * + * // Insert at the beginning of the list. + * exam_t *my_exam = malloc(sizeof(exam_t), 0); + * my_exam->grade = 5; + * my_exam->next = exam_list; + * rcu_assign(exam_list, my_exam); + * + * // Changes properly propagate. Every reader either sees + * // the old version of exam_list or the new version with + * // the fully initialized my_exam. + * rcu_synchronize(); + * // Now we can be sure every reader sees my_exam. + * + * @endcode + */ +#define rcu_assign(ptr, value) \ + do { \ + memory_barrier(); \ + (ptr) = (value); \ + } while (0) + +/** Use to access RCU protected data in a reader section. + * + * Example: + * @code + * exam_t *exam_list; + * // ... + * + * rcu_read_lock(); + * exam_t *first_exam = rcu_access(exam_list); + * // We can now safely use first_exam, it won't change + * // under us while we're using it. + * + * // .. + * rcu_read_unlock(); + * @endcode + */ +#define rcu_access(ptr) ACCESS_ONCE(ptr) + +typedef enum blocking_mode { + BM_BLOCK_FIBRIL, + BM_BLOCK_THREAD +} blocking_mode_t; + +extern void rcu_register_fibril(void); +extern void rcu_deregister_fibril(void); + +extern void rcu_read_lock(void); +extern void rcu_read_unlock(void); + +extern bool rcu_read_locked(void); + +#define rcu_synchronize() _rcu_synchronize(BM_BLOCK_FIBRIL) + +extern void _rcu_synchronize(blocking_mode_t); + +#endif + +/** @} + */