Index: uspace/Makefile =================================================================== --- uspace/Makefile (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/Makefile (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -66,5 +66,4 @@ app/redir \ app/rcutest \ - app/rcubench \ app/sbi \ app/sportdmp \ Index: pace/app/rcubench/Makefile =================================================================== --- uspace/app/rcubench/Makefile (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ (revision ) @@ -1,37 +1,0 @@ -# -# 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 = ../.. - -BINARY = rcubench - -SOURCES = \ - rcubench.c - -include $(USPACE_PREFIX)/Makefile.common - Index: pace/app/rcubench/rcubench.c =================================================================== --- uspace/app/rcubench/rcubench.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ (revision ) @@ -1,286 +1,0 @@ -/* - * 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; - fibril_semaphore_t done_threads; -} 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 errno_t thread_func(void *arg) -{ - bench_t *bench = (bench_t *)arg; - - bench->func(bench); - - /* Signal another thread completed. */ - fibril_semaphore_up(&bench->done_threads); - return EOK; -} - -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); - } - - fibril_test_spawn_runners(bench->nthreads - 1); - - /* Create and run the first nthreads - 1 threads.*/ - for (size_t k = 1; k < bench->nthreads; ++k) { - fid_t f = fibril_create(thread_func, bench); - if (!f) { - printf("Error: Failed to create benchmark thread.\n"); - abort(); - } - fibril_detach(f); - fibril_add_ready(f); - } - - /* - * 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) { - fibril_semaphore_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; - } - - 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; - errno_t 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; - - fibril_semaphore_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_diff(&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/rcutest.c =================================================================== --- uspace/app/rcutest/rcutest.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/app/rcutest/rcutest.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -46,5 +46,4 @@ #include #include -#include #include Index: uspace/lib/c/generic/async/ports.c =================================================================== --- uspace/lib/c/generic/async/ports.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/async/ports.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -51,4 +51,5 @@ #include #include "../private/libc.h" +#include "../private/fibril.h" /** Interface data */ Index: uspace/lib/c/generic/io/kio.c =================================================================== --- uspace/lib/c/generic/io/kio.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/io/kio.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -44,5 +44,6 @@ #include #include -#include + +#include "../private/futex.h" #define KIO_BUFFER_SIZE PAGE_SIZE Index: uspace/lib/c/generic/ipc.c =================================================================== --- uspace/lib/c/generic/ipc.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/ipc.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -46,5 +46,4 @@ #include #include -#include #include #include Index: uspace/lib/c/generic/malloc.c =================================================================== --- uspace/lib/c/generic/malloc.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/malloc.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -44,8 +44,9 @@ #include #include -#include #include #include + #include "private/malloc.h" +#include "private/fibril.h" /** Magic used in heap headers. */ Index: uspace/lib/c/generic/private/fibril.h =================================================================== --- uspace/lib/c/generic/private/fibril.h (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/private/fibril.h (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -35,5 +35,13 @@ #include #include -#include +#include + +#include "./futex.h" + +typedef struct { + fibril_t *fibril; +} fibril_event_t; + +#define FIBRIL_EVENT_INIT ((fibril_event_t) {0}) struct fibril { @@ -73,3 +81,55 @@ extern void __fibrils_init(void); +extern void fibril_wait_for(fibril_event_t *); +extern errno_t fibril_wait_timeout(fibril_event_t *, const struct timeval *); +extern void fibril_notify(fibril_event_t *); + +extern errno_t fibril_ipc_wait(ipc_call_t *, const struct timeval *); +extern void fibril_ipc_poke(void); + +/** + * "Restricted" fibril mutex. + * + * Similar to `fibril_mutex_t`, but has a set of restrictions placed on its + * use. Within a rmutex critical section, you + * - may not use any other synchronization primitive, + * save for another `fibril_rmutex_t`. This includes nonblocking + * operations like cvar signal and mutex unlock, unless otherwise + * specified. + * - may not read IPC messages + * - may not start a new thread/fibril + * (creating fibril without starting is fine) + * + * Additionally, locking with a timeout is not possible on this mutex, + * and there is no associated condition variable type. + * This is a design constraint, not a lack of implementation effort. + */ +typedef struct { + // TODO: At this point, this is just silly handwaving to hide current + // futex use behind a fibril based abstraction. Later, the imple- + // mentation will change, but the restrictions placed on this type + // will allow it to be simpler and faster than a regular mutex. + // There might also be optional debug checking of the assumptions. + // + // Note that a consequence of the restrictions is that if we are + // running on a single thread, no other fibril can ever get to run + // while a fibril has a rmutex locked. That means that for + // single-threaded programs, we can reduce all rmutex locks and + // unlocks to simple branches on a global bool variable. + + futex_t futex; +} fibril_rmutex_t; + +#define FIBRIL_RMUTEX_INITIALIZER(name) \ + { .futex = FUTEX_INITIALIZE(1) } + +#define FIBRIL_RMUTEX_INITIALIZE(name) \ + fibril_rmutex_t name = FIBRIL_RMUTEX_INITIALIZER(name) + +extern void fibril_rmutex_initialize(fibril_rmutex_t *); +extern void fibril_rmutex_lock(fibril_rmutex_t *); +extern bool fibril_rmutex_trylock(fibril_rmutex_t *); +extern void fibril_rmutex_unlock(fibril_rmutex_t *); + + #endif Index: uspace/lib/c/generic/private/futex.h =================================================================== --- uspace/lib/c/generic/private/futex.h (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) +++ uspace/lib/c/generic/private/futex.h (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -0,0 +1,232 @@ +/* + * Copyright (c) 2006 Jakub Jermar + * 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_FUTEX_H_ +#define LIBC_FUTEX_H_ + +#include +#include +#include +#include +#include + +typedef struct futex { + atomic_t val; +#ifdef CONFIG_DEBUG_FUTEX + void *owner; +#endif +} futex_t; + +extern void futex_initialize(futex_t *futex, int value); + +#ifdef CONFIG_DEBUG_FUTEX + +#define FUTEX_INITIALIZE(val) {{ (val) }, NULL } +#define FUTEX_INITIALIZER FUTEX_INITIALIZE(1) + +void __futex_assert_is_locked(futex_t *, const char *); +void __futex_assert_is_not_locked(futex_t *, const char *); +void __futex_lock(futex_t *, const char *); +void __futex_unlock(futex_t *, const char *); +bool __futex_trylock(futex_t *, const char *); +void __futex_give_to(futex_t *, void *, const char *); + +#define futex_lock(futex) __futex_lock((futex), #futex) +#define futex_unlock(futex) __futex_unlock((futex), #futex) +#define futex_trylock(futex) __futex_trylock((futex), #futex) + +#define futex_give_to(futex, new_owner) __futex_give_to((futex), (new_owner), #futex) +#define futex_assert_is_locked(futex) __futex_assert_is_locked((futex), #futex) +#define futex_assert_is_not_locked(futex) __futex_assert_is_not_locked((futex), #futex) + +#else + +#define FUTEX_INITIALIZE(val) {{ (val) }} +#define FUTEX_INITIALIZER FUTEX_INITIALIZE(1) + +#define futex_lock(fut) (void) futex_down((fut)) +#define futex_trylock(fut) futex_trydown((fut)) +#define futex_unlock(fut) (void) futex_up((fut)) + +#define futex_give_to(fut, owner) ((void)0) +#define futex_assert_is_locked(fut) assert((atomic_signed_t) (fut)->val.count <= 0) +#define futex_assert_is_not_locked(fut) ((void)0) + +#endif + +/** Down the futex with timeout, composably. + * + * This means that when the operation fails due to a timeout or being + * interrupted, the next futex_up() is ignored, which allows certain kinds of + * composition of synchronization primitives. + * + * In most other circumstances, regular futex_down_timeout() is a better choice. + * + * @param futex Futex. + * + * @return ENOENT if there is no such virtual address. + * @return ETIMEOUT if timeout expires. + * @return EOK on success. + * @return Error code from otherwise. + * + */ +static inline errno_t futex_down_composable(futex_t *futex, const struct timeval *expires) +{ + // TODO: Add tests for this. + + if ((atomic_signed_t) atomic_predec(&futex->val) >= 0) + return EOK; + + suseconds_t timeout; + + if (!expires) { + /* No timeout. */ + timeout = 0; + } else { + if (expires->tv_sec == 0) { + /* We can't just return ETIMEOUT. That wouldn't be composable. */ + timeout = 1; + } else { + struct timeval tv; + getuptime(&tv); + timeout = tv_gteq(&tv, expires) ? 1 : + tv_sub_diff(expires, &tv); + } + + assert(timeout > 0); + } + + return __SYSCALL2(SYS_FUTEX_SLEEP, (sysarg_t) &futex->val.count, (sysarg_t) timeout); +} + +/** Up the futex. + * + * @param futex Futex. + * + * @return ENOENT if there is no such virtual address. + * @return EOK on success. + * @return Error code from otherwise. + * + */ +static inline errno_t 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 EOK; +} + +static inline errno_t futex_down_timeout(futex_t *futex, const struct timeval *expires) +{ + if (expires && expires->tv_sec == 0 && expires->tv_usec == 0) { + /* Nonblocking down. */ + + /* + * Try good old CAS a few times. + * Not too much though, we don't want to bloat the caller. + */ + for (int i = 0; i < 2; i++) { + atomic_signed_t old = atomic_get(&futex->val); + if (old <= 0) + return ETIMEOUT; + + if (cas(&futex->val, old, old - 1)) + return EOK; + } + + // TODO: builtin atomics with relaxed ordering can make this + // faster. + + /* + * If we don't succeed with CAS, we can't just return failure + * because that would lead to spurious failures where + * futex_down_timeout returns ETIMEOUT despite there being + * available tokens. That could break some algorithms. + * We also don't want to loop on CAS indefinitely, because + * that would make the semaphore not wait-free, even when all + * atomic operations and the underlying base semaphore are all + * wait-free. + * Instead, we fall back to regular down_timeout(), with + * an already expired deadline. That way we delegate all these + * concerns to the base semaphore. + */ + } + + /* + * This combination of a "composable" sleep followed by futex_up() on + * failure is necessary to prevent breakage due to certain race + * conditions. + */ + errno_t rc = futex_down_composable(futex, expires); + if (rc != EOK) + futex_up(futex); + return rc; +} + +/** Try to down the futex. + * + * @param futex Futex. + * + * @return true if the futex was acquired. + * @return false if the futex was not acquired. + * + */ +static inline bool futex_trydown(futex_t *futex) +{ + /* + * down_timeout with an already expired deadline should behave like + * trydown. + */ + struct timeval tv = { .tv_sec = 0, .tv_usec = 0 }; + return futex_down_timeout(futex, &tv) == EOK; +} + +/** Down the futex. + * + * @param futex Futex. + * + * @return ENOENT if there is no such virtual address. + * @return EOK on success. + * @return Error code from otherwise. + * + */ +static inline errno_t futex_down(futex_t *futex) +{ + return futex_down_timeout(futex, NULL); +} + +#endif + +/** @} + */ Index: uspace/lib/c/generic/thread/fibril.c =================================================================== --- uspace/lib/c/generic/thread/fibril.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/thread/fibril.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -42,5 +42,4 @@ #include #include -#include #include @@ -51,4 +50,5 @@ #include "../private/thread.h" +#include "../private/futex.h" #include "../private/fibril.h" #include "../private/libc.h" Index: uspace/lib/c/generic/thread/fibril_synch.c =================================================================== --- uspace/lib/c/generic/thread/fibril_synch.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/thread/fibril_synch.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -37,5 +37,4 @@ #include #include -#include #include #include @@ -50,4 +49,5 @@ #include "../private/async.h" #include "../private/fibril.h" +#include "../private/futex.h" void fibril_rmutex_initialize(fibril_rmutex_t *m) Index: uspace/lib/c/generic/thread/futex.c =================================================================== --- uspace/lib/c/generic/thread/futex.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/thread/futex.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -33,6 +33,4 @@ */ -#include - #include #include @@ -41,4 +39,5 @@ #include "../private/fibril.h" +#include "../private/futex.h" //#define DPRINTF(...) kio_printf(__VA_ARGS__) Index: uspace/lib/c/generic/thread/mpsc.c =================================================================== --- uspace/lib/c/generic/thread/mpsc.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/thread/mpsc.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -36,4 +36,6 @@ #include #include + +#include "../private/fibril.h" /* Index: uspace/lib/c/generic/thread/rcu.c =================================================================== --- uspace/lib/c/generic/thread/rcu.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/generic/thread/rcu.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -73,5 +73,4 @@ #include #include -#include #include #include Index: uspace/lib/c/include/fibril.h =================================================================== --- uspace/lib/c/include/fibril.h (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/include/fibril.h (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -49,10 +49,4 @@ typedef fibril_t *fid_t; -typedef struct { - fibril_t *fibril; -} fibril_event_t; - -#define FIBRIL_EVENT_INIT ((fibril_event_t) {0}) - /** Fibril-local variable specifier */ #define fibril_local __thread @@ -82,11 +76,4 @@ extern __noreturn void fibril_exit(long); -extern void fibril_wait_for(fibril_event_t *); -extern errno_t fibril_wait_timeout(fibril_event_t *, const struct timeval *); -extern void fibril_notify(fibril_event_t *); - -extern errno_t fibril_ipc_wait(ipc_call_t *, const struct timeval *); -extern void fibril_ipc_poke(void); - #endif Index: uspace/lib/c/include/fibril_synch.h =================================================================== --- uspace/lib/c/include/fibril_synch.h (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/include/fibril_synch.h (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -41,44 +41,4 @@ #include #include -#include - -/** - * "Restricted" fibril mutex. - * - * Similar to `fibril_mutex_t`, but has a set of restrictions placed on its - * use. Within a rmutex critical section, you - * - may not use any other synchronization primitive, - * save for another `fibril_rmutex_t`. This includes nonblocking - * operations like cvar signal and mutex unlock, unless otherwise - * specified. - * - may not read IPC messages - * - may not start a new thread/fibril - * (creating fibril without starting is fine) - * - * Additionally, locking with a timeout is not possible on this mutex, - * and there is no associated condition variable type. - * This is a design constraint, not a lack of implementation effort. - */ -typedef struct { - // TODO: At this point, this is just silly handwaving to hide current - // futex use behind a fibril based abstraction. Later, the imple- - // mentation will change, but the restrictions placed on this type - // will allow it to be simpler and faster than a regular mutex. - // There might also be optional debug checking of the assumptions. - // - // Note that a consequence of the restrictions is that if we are - // running on a single thread, no other fibril can ever get to run - // while a fibril has a rmutex locked. That means that for - // single-threaded programs, we can reduce all rmutex locks and - // unlocks to simple branches on a global bool variable. - - futex_t futex; -} fibril_rmutex_t; - -#define FIBRIL_RMUTEX_INITIALIZER(name) \ - { .futex = FUTEX_INITIALIZE(1) } - -#define FIBRIL_RMUTEX_INITIALIZE(name) \ - fibril_rmutex_t name = FIBRIL_RMUTEX_INITIALIZER(name) typedef struct { @@ -204,9 +164,4 @@ fibril_semaphore_t name = FIBRIL_SEMAPHORE_INITIALIZER(name, cnt) -extern void fibril_rmutex_initialize(fibril_rmutex_t *); -extern void fibril_rmutex_lock(fibril_rmutex_t *); -extern bool fibril_rmutex_trylock(fibril_rmutex_t *); -extern void fibril_rmutex_unlock(fibril_rmutex_t *); - extern void fibril_mutex_initialize(fibril_mutex_t *); extern void fibril_mutex_lock(fibril_mutex_t *); Index: pace/lib/c/include/futex.h =================================================================== --- uspace/lib/c/include/futex.h (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ (revision ) @@ -1,232 +1,0 @@ -/* - * Copyright (c) 2006 Jakub Jermar - * 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_FUTEX_H_ -#define LIBC_FUTEX_H_ - -#include -#include -#include -#include -#include - -typedef struct futex { - atomic_t val; -#ifdef CONFIG_DEBUG_FUTEX - void *owner; -#endif -} futex_t; - -extern void futex_initialize(futex_t *futex, int value); - -#ifdef CONFIG_DEBUG_FUTEX - -#define FUTEX_INITIALIZE(val) {{ (val) }, NULL } -#define FUTEX_INITIALIZER FUTEX_INITIALIZE(1) - -void __futex_assert_is_locked(futex_t *, const char *); -void __futex_assert_is_not_locked(futex_t *, const char *); -void __futex_lock(futex_t *, const char *); -void __futex_unlock(futex_t *, const char *); -bool __futex_trylock(futex_t *, const char *); -void __futex_give_to(futex_t *, void *, const char *); - -#define futex_lock(futex) __futex_lock((futex), #futex) -#define futex_unlock(futex) __futex_unlock((futex), #futex) -#define futex_trylock(futex) __futex_trylock((futex), #futex) - -#define futex_give_to(futex, new_owner) __futex_give_to((futex), (new_owner), #futex) -#define futex_assert_is_locked(futex) __futex_assert_is_locked((futex), #futex) -#define futex_assert_is_not_locked(futex) __futex_assert_is_not_locked((futex), #futex) - -#else - -#define FUTEX_INITIALIZE(val) {{ (val) }} -#define FUTEX_INITIALIZER FUTEX_INITIALIZE(1) - -#define futex_lock(fut) (void) futex_down((fut)) -#define futex_trylock(fut) futex_trydown((fut)) -#define futex_unlock(fut) (void) futex_up((fut)) - -#define futex_give_to(fut, owner) ((void)0) -#define futex_assert_is_locked(fut) assert((atomic_signed_t) (fut)->val.count <= 0) -#define futex_assert_is_not_locked(fut) ((void)0) - -#endif - -/** Down the futex with timeout, composably. - * - * This means that when the operation fails due to a timeout or being - * interrupted, the next futex_up() is ignored, which allows certain kinds of - * composition of synchronization primitives. - * - * In most other circumstances, regular futex_down_timeout() is a better choice. - * - * @param futex Futex. - * - * @return ENOENT if there is no such virtual address. - * @return ETIMEOUT if timeout expires. - * @return EOK on success. - * @return Error code from otherwise. - * - */ -static inline errno_t futex_down_composable(futex_t *futex, const struct timeval *expires) -{ - // TODO: Add tests for this. - - if ((atomic_signed_t) atomic_predec(&futex->val) >= 0) - return EOK; - - suseconds_t timeout; - - if (!expires) { - /* No timeout. */ - timeout = 0; - } else { - if (expires->tv_sec == 0) { - /* We can't just return ETIMEOUT. That wouldn't be composable. */ - timeout = 1; - } else { - struct timeval tv; - getuptime(&tv); - timeout = tv_gteq(&tv, expires) ? 1 : - tv_sub_diff(expires, &tv); - } - - assert(timeout > 0); - } - - return __SYSCALL2(SYS_FUTEX_SLEEP, (sysarg_t) &futex->val.count, (sysarg_t) timeout); -} - -/** Up the futex. - * - * @param futex Futex. - * - * @return ENOENT if there is no such virtual address. - * @return EOK on success. - * @return Error code from otherwise. - * - */ -static inline errno_t 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 EOK; -} - -static inline errno_t futex_down_timeout(futex_t *futex, const struct timeval *expires) -{ - if (expires && expires->tv_sec == 0 && expires->tv_usec == 0) { - /* Nonblocking down. */ - - /* - * Try good old CAS a few times. - * Not too much though, we don't want to bloat the caller. - */ - for (int i = 0; i < 2; i++) { - atomic_signed_t old = atomic_get(&futex->val); - if (old <= 0) - return ETIMEOUT; - - if (cas(&futex->val, old, old - 1)) - return EOK; - } - - // TODO: builtin atomics with relaxed ordering can make this - // faster. - - /* - * If we don't succeed with CAS, we can't just return failure - * because that would lead to spurious failures where - * futex_down_timeout returns ETIMEOUT despite there being - * available tokens. That could break some algorithms. - * We also don't want to loop on CAS indefinitely, because - * that would make the semaphore not wait-free, even when all - * atomic operations and the underlying base semaphore are all - * wait-free. - * Instead, we fall back to regular down_timeout(), with - * an already expired deadline. That way we delegate all these - * concerns to the base semaphore. - */ - } - - /* - * This combination of a "composable" sleep followed by futex_up() on - * failure is necessary to prevent breakage due to certain race - * conditions. - */ - errno_t rc = futex_down_composable(futex, expires); - if (rc != EOK) - futex_up(futex); - return rc; -} - -/** Try to down the futex. - * - * @param futex Futex. - * - * @return true if the futex was acquired. - * @return false if the futex was not acquired. - * - */ -static inline bool futex_trydown(futex_t *futex) -{ - /* - * down_timeout with an already expired deadline should behave like - * trydown. - */ - struct timeval tv = { .tv_sec = 0, .tv_usec = 0 }; - return futex_down_timeout(futex, &tv) == EOK; -} - -/** Down the futex. - * - * @param futex Futex. - * - * @return ENOENT if there is no such virtual address. - * @return EOK on success. - * @return Error code from otherwise. - * - */ -static inline errno_t futex_down(futex_t *futex) -{ - return futex_down_timeout(futex, NULL); -} - -#endif - -/** @} - */ Index: uspace/lib/c/include/ipc/common.h =================================================================== --- uspace/lib/c/include/ipc/common.h (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/c/include/ipc/common.h (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -37,8 +37,7 @@ #include -#include #include -#include #include +#include #define IPC_FLAG_BLOCKING 0x01 Index: uspace/lib/drv/include/dev_iface.h =================================================================== --- uspace/lib/drv/include/dev_iface.h (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/lib/drv/include/dev_iface.h (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -38,4 +38,5 @@ #include #include +#include /* Index: uspace/srv/hid/input/ctl/stty.c =================================================================== --- uspace/srv/hid/input/ctl/stty.c (revision 1de92fb061a30c6722110b2a588542d6cc5cdb29) +++ uspace/srv/hid/input/ctl/stty.c (revision f787c8e603e6091f428e7d4b79342b95a4fc26f4) @@ -38,4 +38,5 @@ */ +#include #include #include "../stroke.h"