Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision d742db216b1d7efda0a82bee848205d7ffe4a730) +++ uspace/lib/c/Makefile (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) @@ -51,5 +51,4 @@ generic/libc.c \ generic/ddi.c \ - generic/atomic.c \ generic/as.c \ generic/bd.c \ @@ -85,13 +84,8 @@ generic/strtol.c \ generic/l18n/langs.c \ - generic/fibril.c \ - generic/fibril_synch.c \ generic/pcb.c \ generic/smc.c \ generic/smp_memory_barrier.c \ - generic/thread.c \ - generic/tls.c \ generic/task.c \ - generic/futex.c \ generic/imath.c \ generic/inet/addr.c \ @@ -142,4 +136,11 @@ generic/stdio/sstream.c \ generic/stdio/vsprintf.c \ + generic/thread/atomic.c \ + generic/thread/fibril.c \ + generic/thread/fibril_synch.c \ + generic/thread/thread.c \ + generic/thread/tls.c \ + generic/thread/futex.c \ + generic/thread/rcu.c \ generic/sysinfo.c \ generic/ipc.c \ @@ -165,5 +166,4 @@ generic/vfs/mtab.c \ generic/vfs/vfs.c \ - generic/rcu.c \ generic/setjmp.c \ generic/stack.c \ Index: uspace/lib/c/generic/atomic.c =================================================================== --- uspace/lib/c/generic/atomic.c (revision d742db216b1d7efda0a82bee848205d7ffe4a730) +++ (revision ) @@ -1,68 +1,0 @@ -/* - * Copyright (c) 2018 CZ.NIC, z.s.p.o. - * 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. - */ - -#include - -#ifdef PLATFORM_arm32 - -/* - * Older ARMs don't have atomic instructions, so we need to define a bunch - * of symbols for GCC to use. - */ - -unsigned __sync_add_and_fetch_4(volatile void *vptr, unsigned val) -{ - return atomic_add((atomic_t *)vptr, val); -} - -unsigned __sync_sub_and_fetch_4(volatile void *vptr, unsigned val) -{ - return atomic_add((atomic_t *)vptr, -(atomic_signed_t)val); -} - -bool __sync_bool_compare_and_swap_4(volatile void *ptr, unsigned old_val, unsigned new_val) -{ - return cas((atomic_t *)ptr, old_val, new_val); -} - -unsigned __sync_val_compare_and_swap_4(volatile void *ptr, unsigned old_val, unsigned new_val) -{ - while (true) { - if (__sync_bool_compare_and_swap_4(ptr, old_val, new_val)) { - return old_val; - } - - unsigned current = *(volatile unsigned *)ptr; - if (current != old_val) - return current; - - /* If the current value is the same as old_val, retry. */ - } -} - -#endif Index: uspace/lib/c/generic/fibril.c =================================================================== --- uspace/lib/c/generic/fibril.c (revision d742db216b1d7efda0a82bee848205d7ffe4a730) +++ (revision ) @@ -1,917 +1,0 @@ -/* - * Copyright (c) 2006 Ondrej Palkovsky - * Copyright (c) 2007 Jakub Jermar - * Copyright (c) 2018 CZ.NIC, z.s.p.o. - * 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 -#include -#include -#include -#include -#include -#include -#include - -#include -#include -#include -#include -#include "private/thread.h" -#include "private/fibril.h" -#include "private/libc.h" - -#define DPRINTF(...) ((void)0) -#undef READY_DEBUG - -/** Member of timeout_list. */ -typedef struct { - link_t link; - struct timeval expires; - fibril_event_t *event; -} _timeout_t; - -typedef struct { - errno_t rc; - link_t link; - ipc_call_t *call; - fibril_event_t event; -} _ipc_waiter_t; - -typedef struct { - errno_t rc; - link_t link; - ipc_call_t call; -} _ipc_buffer_t; - -typedef enum { - SWITCH_FROM_DEAD, - SWITCH_FROM_HELPER, - SWITCH_FROM_YIELD, - SWITCH_FROM_BLOCKED, -} _switch_type_t; - -static bool multithreaded = false; - -/* This futex serializes access to global data. */ -static futex_t fibril_futex = FUTEX_INITIALIZER; -static futex_t ready_semaphore = FUTEX_INITIALIZE(0); -static long ready_st_count; - -static LIST_INITIALIZE(ready_list); -static LIST_INITIALIZE(fibril_list); -static LIST_INITIALIZE(timeout_list); - -static futex_t ipc_lists_futex = FUTEX_INITIALIZER; -static LIST_INITIALIZE(ipc_waiter_list); -static LIST_INITIALIZE(ipc_buffer_list); -static LIST_INITIALIZE(ipc_buffer_free_list); - -/* Only used as unique markers for triggered events. */ -static fibril_t _fibril_event_triggered; -static fibril_t _fibril_event_timed_out; -#define _EVENT_INITIAL (NULL) -#define _EVENT_TRIGGERED (&_fibril_event_triggered) -#define _EVENT_TIMED_OUT (&_fibril_event_timed_out) - -static inline void _ready_debug_check(void) -{ -#ifdef READY_DEBUG - assert(!multithreaded); - long count = (long) list_count(&ready_list) + - (long) list_count(&ipc_buffer_free_list); - assert(ready_st_count == count); -#endif -} - -static inline long _ready_count(void) -{ - /* - * The number of available tokens is always equal to the number - * of fibrils in the ready list + the number of free IPC buffer - * buckets. - */ - - if (multithreaded) - return atomic_get(&ready_semaphore.val); - - _ready_debug_check(); - return ready_st_count; -} - -static inline void _ready_up(void) -{ - if (multithreaded) { - futex_up(&ready_semaphore); - } else { - ready_st_count++; - _ready_debug_check(); - } -} - -static inline errno_t _ready_down(const struct timeval *expires) -{ - if (multithreaded) - return futex_down_timeout(&ready_semaphore, expires); - - _ready_debug_check(); - ready_st_count--; - return EOK; -} - -static atomic_t threads_in_ipc_wait = { 0 }; - -/** Function that spans the whole life-cycle of a fibril. - * - * Each fibril begins execution in this function. Then the function implementing - * the fibril logic is called. After its return, the return value is saved. - * The fibril then switches to another fibril, which cleans up after it. - * - */ -static void _fibril_main(void) -{ - /* fibril_futex is locked when a fibril is started. */ - futex_unlock(&fibril_futex); - - fibril_t *fibril = fibril_self(); - - /* Call the implementing function. */ - fibril_exit(fibril->func(fibril->arg)); - - /* Not reached */ -} - -/** Allocate a fibril structure and TCB, but don't do anything else with it. */ -fibril_t *fibril_alloc(void) -{ - tcb_t *tcb = tls_make(__progsymbols.elfstart); - if (!tcb) - return NULL; - - fibril_t *fibril = calloc(1, sizeof(fibril_t)); - if (!fibril) { - tls_free(tcb); - return NULL; - } - - tcb->fibril_data = fibril; - fibril->tcb = tcb; - fibril->is_freeable = true; - - fibril_setup(fibril); - return fibril; -} - -/** - * Put the fibril into fibril_list. - */ -void fibril_setup(fibril_t *f) -{ - futex_lock(&fibril_futex); - list_append(&f->all_link, &fibril_list); - futex_unlock(&fibril_futex); -} - -void fibril_teardown(fibril_t *fibril) -{ - futex_lock(&fibril_futex); - list_remove(&fibril->all_link); - futex_unlock(&fibril_futex); - - if (fibril->is_freeable) { - tls_free(fibril->tcb); - free(fibril); - } -} - -/** - * Event notification with a given reason. - * - * @param reason Reason of the notification. - * Can be either _EVENT_TRIGGERED or _EVENT_TIMED_OUT. - */ -static fibril_t *_fibril_trigger_internal(fibril_event_t *event, fibril_t *reason) -{ - assert(reason != _EVENT_INITIAL); - assert(reason == _EVENT_TIMED_OUT || reason == _EVENT_TRIGGERED); - - futex_assert_is_locked(&fibril_futex); - - if (event->fibril == _EVENT_INITIAL) { - event->fibril = reason; - return NULL; - } - - if (event->fibril == _EVENT_TIMED_OUT) { - assert(reason == _EVENT_TRIGGERED); - event->fibril = reason; - return NULL; - } - - if (event->fibril == _EVENT_TRIGGERED) { - /* Already triggered. Nothing to do. */ - return NULL; - } - - fibril_t *f = event->fibril; - event->fibril = reason; - - assert(f->sleep_event == event); - return f; -} - -static errno_t _ipc_wait(ipc_call_t *call, const struct timeval *expires) -{ - if (!expires) - return ipc_wait(call, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE); - - if (expires->tv_sec == 0) - return ipc_wait(call, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NON_BLOCKING); - - struct timeval now; - getuptime(&now); - - if (tv_gteq(&now, expires)) - return ipc_wait(call, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NON_BLOCKING); - - return ipc_wait(call, tv_sub_diff(expires, &now), SYNCH_FLAGS_NONE); -} - -/* - * Waits until a ready fibril is added to the list, or an IPC message arrives. - * Returns NULL on timeout and may also return NULL if returning from IPC - * wait after new ready fibrils are added. - */ -static fibril_t *_ready_list_pop(const struct timeval *expires, bool locked) -{ - if (locked) { - futex_assert_is_locked(&fibril_futex); - assert(expires); - /* Must be nonblocking. */ - assert(expires->tv_sec == 0); - } else { - futex_assert_is_not_locked(&fibril_futex); - } - - errno_t rc = _ready_down(expires); - if (rc != EOK) - return NULL; - - /* - * Once we acquire a token from ready_semaphore, there are two options. - * Either there is a ready fibril in the list, or it's our turn to - * call `ipc_wait_cycle()`. There is one extra token on the semaphore - * for each entry of the call buffer. - */ - - - if (!locked) - futex_lock(&fibril_futex); - fibril_t *f = list_pop(&ready_list, fibril_t, link); - if (!f) - atomic_inc(&threads_in_ipc_wait); - if (!locked) - futex_unlock(&fibril_futex); - - if (f) - return f; - - if (!multithreaded) - assert(list_empty(&ipc_buffer_list)); - - /* No fibril is ready, IPC wait it is. */ - ipc_call_t call = { 0 }; - rc = _ipc_wait(&call, expires); - - atomic_dec(&threads_in_ipc_wait); - - if (rc != EOK && rc != ENOENT) { - /* Return token. */ - _ready_up(); - return NULL; - } - - /* - * We might get ENOENT due to a poke. - * In that case, we propagate the null call out of fibril_ipc_wait(), - * because poke must result in that call returning. - */ - - /* - * If a fibril is already waiting for IPC, we wake up the fibril, - * and return the token to ready_semaphore. - * If there is no fibril waiting, we pop a buffer bucket and - * put our call there. The token then returns when the bucket is - * returned. - */ - - if (!locked) - futex_lock(&fibril_futex); - - futex_lock(&ipc_lists_futex); - - - _ipc_waiter_t *w = list_pop(&ipc_waiter_list, _ipc_waiter_t, link); - if (w) { - *w->call = call; - w->rc = rc; - /* We switch to the woken up fibril immediately if possible. */ - f = _fibril_trigger_internal(&w->event, _EVENT_TRIGGERED); - - /* Return token. */ - _ready_up(); - } else { - _ipc_buffer_t *buf = list_pop(&ipc_buffer_free_list, _ipc_buffer_t, link); - assert(buf); - *buf = (_ipc_buffer_t) { .call = call, .rc = rc }; - list_append(&buf->link, &ipc_buffer_list); - } - - futex_unlock(&ipc_lists_futex); - - if (!locked) - futex_unlock(&fibril_futex); - - return f; -} - -static fibril_t *_ready_list_pop_nonblocking(bool locked) -{ - struct timeval tv = { .tv_sec = 0, .tv_usec = 0 }; - return _ready_list_pop(&tv, locked); -} - -static void _ready_list_push(fibril_t *f) -{ - if (!f) - return; - - futex_assert_is_locked(&fibril_futex); - - /* Enqueue in ready_list. */ - list_append(&f->link, &ready_list); - _ready_up(); - - if (atomic_get(&threads_in_ipc_wait)) { - DPRINTF("Poking.\n"); - /* Wakeup one thread sleeping in SYS_IPC_WAIT. */ - ipc_poke(); - } -} - -/* Blocks the current fibril until an IPC call arrives. */ -static errno_t _wait_ipc(ipc_call_t *call, const struct timeval *expires) -{ - futex_assert_is_not_locked(&fibril_futex); - - futex_lock(&ipc_lists_futex); - _ipc_buffer_t *buf = list_pop(&ipc_buffer_list, _ipc_buffer_t, link); - if (buf) { - *call = buf->call; - errno_t rc = buf->rc; - - /* Return to freelist. */ - list_append(&buf->link, &ipc_buffer_free_list); - /* Return IPC wait token. */ - _ready_up(); - - futex_unlock(&ipc_lists_futex); - return rc; - } - - _ipc_waiter_t w = { .call = call }; - list_append(&w.link, &ipc_waiter_list); - futex_unlock(&ipc_lists_futex); - - errno_t rc = fibril_wait_timeout(&w.event, expires); - if (rc == EOK) - return w.rc; - - futex_lock(&ipc_lists_futex); - if (link_in_use(&w.link)) - list_remove(&w.link); - else - rc = w.rc; - futex_unlock(&ipc_lists_futex); - return rc; -} - -/** Fire all timeouts that expired. */ -static struct timeval *_handle_expired_timeouts(struct timeval *next_timeout) -{ - struct timeval tv; - getuptime(&tv); - - futex_lock(&fibril_futex); - - while (!list_empty(&timeout_list)) { - link_t *cur = list_first(&timeout_list); - _timeout_t *to = list_get_instance(cur, _timeout_t, link); - - if (tv_gt(&to->expires, &tv)) { - *next_timeout = to->expires; - futex_unlock(&fibril_futex); - return next_timeout; - } - - list_remove(&to->link); - - _ready_list_push(_fibril_trigger_internal( - to->event, _EVENT_TIMED_OUT)); - } - - futex_unlock(&fibril_futex); - return NULL; -} - -/** - * Clean up after a dead fibril from which we restored context, if any. - * Called after a switch is made and fibril_futex is unlocked. - */ -static void _fibril_cleanup_dead(void) -{ - fibril_t *srcf = fibril_self(); - if (!srcf->clean_after_me) - return; - - void *stack = srcf->clean_after_me->stack; - assert(stack); - as_area_destroy(stack); - fibril_teardown(srcf->clean_after_me); - srcf->clean_after_me = NULL; -} - -/** Switch to a fibril. */ -static void _fibril_switch_to(_switch_type_t type, fibril_t *dstf, bool locked) -{ - assert(fibril_self()->rmutex_locks == 0); - - if (!locked) - futex_lock(&fibril_futex); - else - futex_assert_is_locked(&fibril_futex); - - fibril_t *srcf = fibril_self(); - assert(srcf); - assert(dstf); - - switch (type) { - case SWITCH_FROM_YIELD: - _ready_list_push(srcf); - break; - case SWITCH_FROM_DEAD: - dstf->clean_after_me = srcf; - break; - case SWITCH_FROM_HELPER: - case SWITCH_FROM_BLOCKED: - break; - } - - dstf->thread_ctx = srcf->thread_ctx; - srcf->thread_ctx = NULL; - - /* Just some bookkeeping to allow better debugging of futex locks. */ - futex_give_to(&fibril_futex, dstf); - - /* Swap to the next fibril. */ - context_swap(&srcf->ctx, &dstf->ctx); - - assert(srcf == fibril_self()); - assert(srcf->thread_ctx); - - if (!locked) { - /* Must be after context_swap()! */ - futex_unlock(&fibril_futex); - _fibril_cleanup_dead(); - } -} - -/** - * Main function for a helper fibril. - * The helper fibril executes on threads in the lightweight fibril pool when - * there is no fibril ready to run. Its only purpose is to block until - * another fibril is ready, or a timeout expires, or an IPC message arrives. - * - * There is at most one helper fibril per thread. - * - */ -static errno_t _helper_fibril_fn(void *arg) -{ - /* Set itself as the thread's own context. */ - fibril_self()->thread_ctx = fibril_self(); - - (void) arg; - - struct timeval next_timeout; - while (true) { - struct timeval *to = _handle_expired_timeouts(&next_timeout); - fibril_t *f = _ready_list_pop(to, false); - if (f) { - _fibril_switch_to(SWITCH_FROM_HELPER, f, false); - } - } - - return EOK; -} - -/** Create a new fibril. - * - * @param func Implementing function of the new fibril. - * @param arg Argument to pass to func. - * @param stksz Stack size in bytes. - * - * @return 0 on failure or TLS of the new fibril. - * - */ -fid_t fibril_create_generic(errno_t (*func)(void *), void *arg, size_t stksz) -{ - fibril_t *fibril; - - fibril = fibril_alloc(); - if (fibril == NULL) - return 0; - - fibril->stack_size = (stksz == FIBRIL_DFLT_STK_SIZE) ? - stack_size_get() : stksz; - fibril->stack = as_area_create(AS_AREA_ANY, fibril->stack_size, - AS_AREA_READ | AS_AREA_WRITE | AS_AREA_CACHEABLE | AS_AREA_GUARD | - AS_AREA_LATE_RESERVE, AS_AREA_UNPAGED); - if (fibril->stack == AS_MAP_FAILED) { - fibril_teardown(fibril); - return 0; - } - - fibril->func = func; - fibril->arg = arg; - - context_create_t sctx = { - .fn = _fibril_main, - .stack_base = fibril->stack, - .stack_size = fibril->stack_size, - .tls = fibril->tcb, - }; - - context_create(&fibril->ctx, &sctx); - return (fid_t) fibril; -} - -/** Delete a fibril that has never run. - * - * Free resources of a fibril that has been created with fibril_create() - * but never started using fibril_start(). - * - * @param fid Pointer to the fibril structure of the fibril to be - * added. - */ -void fibril_destroy(fid_t fid) -{ - fibril_t *fibril = (fibril_t *) fid; - - assert(!fibril->is_running); - assert(fibril->stack); - as_area_destroy(fibril->stack); - fibril_teardown(fibril); -} - -static void _insert_timeout(_timeout_t *timeout) -{ - futex_assert_is_locked(&fibril_futex); - assert(timeout); - - link_t *tmp = timeout_list.head.next; - while (tmp != &timeout_list.head) { - _timeout_t *cur = list_get_instance(tmp, _timeout_t, link); - - if (tv_gteq(&cur->expires, &timeout->expires)) - break; - - tmp = tmp->next; - } - - list_insert_before(&timeout->link, tmp); -} - -/** - * Same as `fibril_wait_for()`, except with a timeout. - * - * It is guaranteed that timing out cannot cause another thread's - * `fibril_notify()` to be lost. I.e. the function returns success if and - * only if `fibril_notify()` was called after the last call to - * wait/wait_timeout returned, and before the call timed out. - * - * @return ETIMEOUT if timed out. EOK otherwise. - */ -errno_t fibril_wait_timeout(fibril_event_t *event, const struct timeval *expires) -{ - assert(fibril_self()->rmutex_locks == 0); - - DPRINTF("### Fibril %p sleeping on event %p.\n", fibril_self(), event); - - if (!fibril_self()->thread_ctx) { - fibril_self()->thread_ctx = - fibril_create_generic(_helper_fibril_fn, NULL, PAGE_SIZE); - if (!fibril_self()->thread_ctx) - return ENOMEM; - } - - futex_lock(&fibril_futex); - - if (event->fibril == _EVENT_TRIGGERED) { - DPRINTF("### Already triggered. Returning. \n"); - event->fibril = _EVENT_INITIAL; - futex_unlock(&fibril_futex); - return EOK; - } - - assert(event->fibril == _EVENT_INITIAL); - - fibril_t *srcf = fibril_self(); - fibril_t *dstf = NULL; - - /* - * We cannot block here waiting for another fibril becoming - * ready, since that would require unlocking the fibril_futex, - * and that in turn would allow another thread to restore - * the source fibril before this thread finished switching. - * - * Instead, we switch to an internal "helper" fibril whose only - * job is to wait for an event, freeing the source fibril for - * wakeups. There is always one for each running thread. - */ - - dstf = _ready_list_pop_nonblocking(true); - if (!dstf) { - // XXX: It is possible for the _ready_list_pop_nonblocking() to - // check for IPC, find a pending message, and trigger the - // event on which we are currently trying to sleep. - if (event->fibril == _EVENT_TRIGGERED) { - event->fibril = _EVENT_INITIAL; - futex_unlock(&fibril_futex); - return EOK; - } - - dstf = srcf->thread_ctx; - assert(dstf); - } - - _timeout_t timeout = { 0 }; - if (expires) { - timeout.expires = *expires; - timeout.event = event; - _insert_timeout(&timeout); - } - - assert(srcf); - - event->fibril = srcf; - srcf->sleep_event = event; - - assert(event->fibril != _EVENT_INITIAL); - - _fibril_switch_to(SWITCH_FROM_BLOCKED, dstf, true); - - assert(event->fibril != srcf); - assert(event->fibril != _EVENT_INITIAL); - assert(event->fibril == _EVENT_TIMED_OUT || event->fibril == _EVENT_TRIGGERED); - - list_remove(&timeout.link); - errno_t rc = (event->fibril == _EVENT_TIMED_OUT) ? ETIMEOUT : EOK; - event->fibril = _EVENT_INITIAL; - - futex_unlock(&fibril_futex); - _fibril_cleanup_dead(); - return rc; -} - -void fibril_wait_for(fibril_event_t *event) -{ - assert(fibril_self()->rmutex_locks == 0); - - (void) fibril_wait_timeout(event, NULL); -} - -void fibril_notify(fibril_event_t *event) -{ - futex_lock(&fibril_futex); - _ready_list_push(_fibril_trigger_internal(event, _EVENT_TRIGGERED)); - futex_unlock(&fibril_futex); -} - -/** Start a fibril that has not been running yet. */ -void fibril_start(fibril_t *fibril) -{ - futex_lock(&fibril_futex); - assert(!fibril->is_running); - fibril->is_running = true; - - if (!link_in_use(&fibril->all_link)) - list_append(&fibril->all_link, &fibril_list); - - _ready_list_push(fibril); - - futex_unlock(&fibril_futex); -} - -/** Start a fibril that has not been running yet. (obsolete) */ -void fibril_add_ready(fibril_t *fibril) -{ - fibril_start(fibril); -} - -/** @return the currently running fibril. */ -fibril_t *fibril_self(void) -{ - assert(__tcb_is_set()); - tcb_t *tcb = __tcb_get(); - assert(tcb->fibril_data); - return tcb->fibril_data; -} - -/** - * Obsolete, use fibril_self(). - * - * @return ID of the currently running fibril. - */ -fid_t fibril_get_id(void) -{ - return (fid_t) fibril_self(); -} - -/** - * Switch to another fibril, if one is ready to run. - * Has no effect on a heavy fibril. - */ -void fibril_yield(void) -{ - if (fibril_self()->rmutex_locks > 0) - return; - - fibril_t *f = _ready_list_pop_nonblocking(false); - if (f) - _fibril_switch_to(SWITCH_FROM_YIELD, f, false); -} - -static void _runner_fn(void *arg) -{ - _helper_fibril_fn(arg); -} - -/** - * Spawn a given number of runners (i.e. OS threads) immediately, and - * unconditionally. This is meant to be used for tests and debugging. - * Regular programs should just use `fibril_enable_multithreaded()`. - * - * @param n Number of runners to spawn. - * @return Number of runners successfully spawned. - */ -int fibril_test_spawn_runners(int n) -{ - assert(fibril_self()->rmutex_locks == 0); - - if (!multithreaded) { - _ready_debug_check(); - atomic_set(&ready_semaphore.val, ready_st_count); - multithreaded = true; - } - - errno_t rc; - - for (int i = 0; i < n; i++) { - thread_id_t tid; - rc = thread_create(_runner_fn, NULL, "fibril runner", &tid); - if (rc != EOK) - return i; - thread_detach(tid); - } - - return n; -} - -/** - * Opt-in to have more than one runner thread. - * - * Currently, a task only ever runs in one thread because multithreading - * might break some existing code. - * - * Eventually, the number of runner threads for a given task should become - * configurable in the environment and this function becomes no-op. - */ -void fibril_enable_multithreaded(void) -{ - // TODO: Implement better. - // For now, 4 total runners is a sensible default. - if (!multithreaded) { - fibril_test_spawn_runners(3); - } -} - -/** - * Detach a fibril. - */ -void fibril_detach(fid_t f) -{ - // TODO: Currently all fibrils are detached by default, but they - // won't always be. Code that explicitly spawns fibrils with - // limited lifetime should call this function. -} - -/** - * Exit a fibril. Never returns. - * - * @param retval Value to return from fibril_join() called on this fibril. - */ -_Noreturn void fibril_exit(long retval) -{ - // TODO: implement fibril_join() and remember retval - (void) retval; - - fibril_t *f = _ready_list_pop_nonblocking(false); - if (!f) - f = fibril_self()->thread_ctx; - - _fibril_switch_to(SWITCH_FROM_DEAD, f, false); - __builtin_unreachable(); -} - -void __fibrils_init(void) -{ - /* - * We allow a fixed, small amount of parallelism for IPC reads, but - * since IPC is currently serialized in kernel, there's not much - * we can get from more threads reading messages. - */ - -#define IPC_BUFFER_COUNT 1024 - static _ipc_buffer_t buffers[IPC_BUFFER_COUNT]; - - for (int i = 0; i < IPC_BUFFER_COUNT; i++) { - list_append(&buffers[i].link, &ipc_buffer_free_list); - _ready_up(); - } -} - -void fibril_usleep(suseconds_t timeout) -{ - struct timeval expires; - getuptime(&expires); - tv_add_diff(&expires, timeout); - - fibril_event_t event = FIBRIL_EVENT_INIT; - fibril_wait_timeout(&event, &expires); -} - -void fibril_sleep(unsigned int sec) -{ - struct timeval expires; - getuptime(&expires); - expires.tv_sec += sec; - - fibril_event_t event = FIBRIL_EVENT_INIT; - fibril_wait_timeout(&event, &expires); -} - -void fibril_ipc_poke(void) -{ - DPRINTF("Poking.\n"); - /* Wakeup one thread sleeping in SYS_IPC_WAIT. */ - ipc_poke(); -} - -errno_t fibril_ipc_wait(ipc_call_t *call, const struct timeval *expires) -{ - return _wait_ipc(call, expires); -} - -/** @} - */ Index: uspace/lib/c/generic/fibril_synch.c =================================================================== --- uspace/lib/c/generic/fibril_synch.c (revision d742db216b1d7efda0a82bee848205d7ffe4a730) +++ (revision ) @@ -1,795 +1,0 @@ -/* - * Copyright (c) 2009 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 - */ - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include "private/async.h" -#include "private/fibril.h" - -void fibril_rmutex_initialize(fibril_rmutex_t *m) -{ - futex_initialize(&m->futex, 1); -} - -/** - * Lock restricted mutex. - * When a restricted mutex is locked, the fibril may not sleep or create new - * threads. Any attempt to do so will abort the program. - */ -void fibril_rmutex_lock(fibril_rmutex_t *m) -{ - futex_lock(&m->futex); - fibril_self()->rmutex_locks++; -} - -bool fibril_rmutex_trylock(fibril_rmutex_t *m) -{ - if (futex_trylock(&m->futex)) { - fibril_self()->rmutex_locks++; - return true; - } else { - return false; - } -} - -void fibril_rmutex_unlock(fibril_rmutex_t *m) -{ - fibril_self()->rmutex_locks--; - futex_unlock(&m->futex); -} - -static fibril_local bool deadlocked = false; - -static futex_t fibril_synch_futex = FUTEX_INITIALIZER; - -typedef struct { - link_t link; - fibril_event_t event; - fibril_mutex_t *mutex; - fid_t fid; -} awaiter_t; - -#define AWAITER_INIT { .fid = fibril_get_id() } - -static void print_deadlock(fibril_owner_info_t *oi) -{ - // FIXME: Print to stderr. - - fibril_t *f = (fibril_t *) fibril_get_id(); - - if (deadlocked) { - kio_printf("Deadlock detected while printing deadlock. Aborting.\n"); - abort(); - } - deadlocked = true; - - printf("Deadlock detected.\n"); - stacktrace_print(); - - printf("Fibril %p waits for primitive %p.\n", f, oi); - - while (oi && oi->owned_by) { - printf("Primitive %p is owned by fibril %p.\n", - oi, oi->owned_by); - if (oi->owned_by == f) - break; - stacktrace_print_fp_pc( - context_get_fp(&oi->owned_by->ctx), - context_get_pc(&oi->owned_by->ctx)); - printf("Fibril %p waits for primitive %p.\n", - oi->owned_by, oi->owned_by->waits_for); - oi = oi->owned_by->waits_for; - } -} - - -static void check_fibril_for_deadlock(fibril_owner_info_t *oi, fibril_t *fib) -{ - futex_assert_is_locked(&fibril_synch_futex); - - while (oi && oi->owned_by) { - if (oi->owned_by == fib) { - futex_unlock(&fibril_synch_futex); - print_deadlock(oi); - abort(); - } - oi = oi->owned_by->waits_for; - } -} - -static void check_for_deadlock(fibril_owner_info_t *oi) -{ - check_fibril_for_deadlock(oi, fibril_self()); -} - -void fibril_mutex_initialize(fibril_mutex_t *fm) -{ - fm->oi.owned_by = NULL; - fm->counter = 1; - list_initialize(&fm->waiters); -} - -void fibril_mutex_lock(fibril_mutex_t *fm) -{ - fibril_t *f = (fibril_t *) fibril_get_id(); - - futex_lock(&fibril_synch_futex); - - if (fm->counter-- > 0) { - fm->oi.owned_by = f; - futex_unlock(&fibril_synch_futex); - return; - } - - awaiter_t wdata = AWAITER_INIT; - list_append(&wdata.link, &fm->waiters); - check_for_deadlock(&fm->oi); - f->waits_for = &fm->oi; - - futex_unlock(&fibril_synch_futex); - - fibril_wait_for(&wdata.event); -} - -bool fibril_mutex_trylock(fibril_mutex_t *fm) -{ - bool locked = false; - - futex_lock(&fibril_synch_futex); - if (fm->counter > 0) { - fm->counter--; - fm->oi.owned_by = (fibril_t *) fibril_get_id(); - locked = true; - } - futex_unlock(&fibril_synch_futex); - - return locked; -} - -static void _fibril_mutex_unlock_unsafe(fibril_mutex_t *fm) -{ - assert(fm->oi.owned_by == (fibril_t *) fibril_get_id()); - - if (fm->counter++ < 0) { - awaiter_t *wdp = list_pop(&fm->waiters, awaiter_t, link); - assert(wdp); - - fibril_t *f = (fibril_t *) wdp->fid; - fm->oi.owned_by = f; - f->waits_for = NULL; - - fibril_notify(&wdp->event); - } else { - fm->oi.owned_by = NULL; - } -} - -void fibril_mutex_unlock(fibril_mutex_t *fm) -{ - futex_lock(&fibril_synch_futex); - _fibril_mutex_unlock_unsafe(fm); - futex_unlock(&fibril_synch_futex); -} - -bool fibril_mutex_is_locked(fibril_mutex_t *fm) -{ - futex_lock(&fibril_synch_futex); - bool locked = (fm->oi.owned_by == (fibril_t *) fibril_get_id()); - futex_unlock(&fibril_synch_futex); - return locked; -} - -void fibril_rwlock_initialize(fibril_rwlock_t *frw) -{ - frw->oi.owned_by = NULL; - frw->writers = 0; - frw->readers = 0; - list_initialize(&frw->waiters); -} - -void fibril_rwlock_read_lock(fibril_rwlock_t *frw) -{ - fibril_t *f = (fibril_t *) fibril_get_id(); - - futex_lock(&fibril_synch_futex); - - if (!frw->writers) { - /* Consider the first reader the owner. */ - if (frw->readers++ == 0) - frw->oi.owned_by = f; - futex_unlock(&fibril_synch_futex); - return; - } - - f->is_writer = false; - - awaiter_t wdata = AWAITER_INIT; - list_append(&wdata.link, &frw->waiters); - check_for_deadlock(&frw->oi); - f->waits_for = &frw->oi; - - futex_unlock(&fibril_synch_futex); - - fibril_wait_for(&wdata.event); -} - -void fibril_rwlock_write_lock(fibril_rwlock_t *frw) -{ - fibril_t *f = (fibril_t *) fibril_get_id(); - - futex_lock(&fibril_synch_futex); - - if (!frw->writers && !frw->readers) { - frw->oi.owned_by = f; - frw->writers++; - futex_unlock(&fibril_synch_futex); - return; - } - - f->is_writer = true; - - awaiter_t wdata = AWAITER_INIT; - list_append(&wdata.link, &frw->waiters); - check_for_deadlock(&frw->oi); - f->waits_for = &frw->oi; - - futex_unlock(&fibril_synch_futex); - - fibril_wait_for(&wdata.event); -} - -static void _fibril_rwlock_common_unlock(fibril_rwlock_t *frw) -{ - if (frw->readers) { - if (--frw->readers) { - if (frw->oi.owned_by == (fibril_t *) fibril_get_id()) { - /* - * If this reader fibril was considered the - * owner of this rwlock, clear the ownership - * information even if there are still more - * readers. - * - * This is the limitation of the detection - * mechanism rooted in the fact that tracking - * all readers would require dynamically - * allocated memory for keeping linkage info. - */ - frw->oi.owned_by = NULL; - } - - return; - } - } else { - frw->writers--; - } - - assert(!frw->readers && !frw->writers); - - frw->oi.owned_by = NULL; - - while (!list_empty(&frw->waiters)) { - link_t *tmp = list_first(&frw->waiters); - awaiter_t *wdp; - fibril_t *f; - - wdp = list_get_instance(tmp, awaiter_t, link); - f = (fibril_t *) wdp->fid; - - if (f->is_writer) { - if (frw->readers) - break; - frw->writers++; - } else { - frw->readers++; - } - - f->waits_for = NULL; - list_remove(&wdp->link); - frw->oi.owned_by = f; - fibril_notify(&wdp->event); - - if (frw->writers) - break; - } -} - -void fibril_rwlock_read_unlock(fibril_rwlock_t *frw) -{ - futex_lock(&fibril_synch_futex); - assert(frw->readers > 0); - _fibril_rwlock_common_unlock(frw); - futex_unlock(&fibril_synch_futex); -} - -void fibril_rwlock_write_unlock(fibril_rwlock_t *frw) -{ - futex_lock(&fibril_synch_futex); - assert(frw->writers == 1); - assert(frw->oi.owned_by == fibril_self()); - _fibril_rwlock_common_unlock(frw); - futex_unlock(&fibril_synch_futex); -} - -bool fibril_rwlock_is_read_locked(fibril_rwlock_t *frw) -{ - futex_lock(&fibril_synch_futex); - bool locked = (frw->readers > 0); - futex_unlock(&fibril_synch_futex); - return locked; -} - -bool fibril_rwlock_is_write_locked(fibril_rwlock_t *frw) -{ - futex_lock(&fibril_synch_futex); - assert(frw->writers <= 1); - bool locked = (frw->writers > 0) && (frw->oi.owned_by == fibril_self()); - futex_unlock(&fibril_synch_futex); - return locked; -} - -bool fibril_rwlock_is_locked(fibril_rwlock_t *frw) -{ - return fibril_rwlock_is_read_locked(frw) || - fibril_rwlock_is_write_locked(frw); -} - -void fibril_condvar_initialize(fibril_condvar_t *fcv) -{ - list_initialize(&fcv->waiters); -} - -/** - * FIXME: If `timeout` is negative, the function returns ETIMEOUT immediately, - * and if `timeout` is 0, the wait never times out. - * This is not consistent with other similar APIs. - */ -errno_t -fibril_condvar_wait_timeout(fibril_condvar_t *fcv, fibril_mutex_t *fm, - suseconds_t timeout) -{ - assert(fibril_mutex_is_locked(fm)); - - if (timeout < 0) - return ETIMEOUT; - - awaiter_t wdata = AWAITER_INIT; - wdata.mutex = fm; - - struct timeval tv; - struct timeval *expires = NULL; - if (timeout) { - getuptime(&tv); - tv_add_diff(&tv, timeout); - expires = &tv; - } - - futex_lock(&fibril_synch_futex); - _fibril_mutex_unlock_unsafe(fm); - list_append(&wdata.link, &fcv->waiters); - futex_unlock(&fibril_synch_futex); - - (void) fibril_wait_timeout(&wdata.event, expires); - - futex_lock(&fibril_synch_futex); - bool timed_out = link_in_use(&wdata.link); - list_remove(&wdata.link); - futex_unlock(&fibril_synch_futex); - - fibril_mutex_lock(fm); - - return timed_out ? ETIMEOUT : EOK; -} - -void fibril_condvar_wait(fibril_condvar_t *fcv, fibril_mutex_t *fm) -{ - (void) fibril_condvar_wait_timeout(fcv, fm, 0); -} - -void fibril_condvar_signal(fibril_condvar_t *fcv) -{ - futex_lock(&fibril_synch_futex); - - awaiter_t *w = list_pop(&fcv->waiters, awaiter_t, link); - if (w != NULL) - fibril_notify(&w->event); - - futex_unlock(&fibril_synch_futex); -} - -void fibril_condvar_broadcast(fibril_condvar_t *fcv) -{ - futex_lock(&fibril_synch_futex); - - awaiter_t *w; - while ((w = list_pop(&fcv->waiters, awaiter_t, link))) - fibril_notify(&w->event); - - futex_unlock(&fibril_synch_futex); -} - -/** Timer fibril. - * - * @param arg Timer - */ -static errno_t fibril_timer_func(void *arg) -{ - fibril_timer_t *timer = (fibril_timer_t *) arg; - errno_t rc; - - fibril_mutex_lock(timer->lockp); - - while (timer->state != fts_cleanup) { - switch (timer->state) { - case fts_not_set: - case fts_fired: - fibril_condvar_wait(&timer->cv, timer->lockp); - break; - case fts_active: - rc = fibril_condvar_wait_timeout(&timer->cv, - timer->lockp, timer->delay); - if (rc == ETIMEOUT && timer->state == fts_active) { - timer->state = fts_fired; - timer->handler_fid = fibril_get_id(); - fibril_mutex_unlock(timer->lockp); - timer->fun(timer->arg); - fibril_mutex_lock(timer->lockp); - timer->handler_fid = 0; - } - break; - case fts_cleanup: - case fts_clean: - assert(false); - break; - } - } - - /* Acknowledge timer fibril has finished cleanup. */ - timer->state = fts_clean; - fibril_condvar_broadcast(&timer->cv); - fibril_mutex_unlock(timer->lockp); - - return 0; -} - -/** Create new timer. - * - * @return New timer on success, @c NULL if out of memory. - */ -fibril_timer_t *fibril_timer_create(fibril_mutex_t *lock) -{ - fid_t fid; - fibril_timer_t *timer; - - timer = calloc(1, sizeof(fibril_timer_t)); - if (timer == NULL) - return NULL; - - fid = fibril_create(fibril_timer_func, (void *) timer); - if (fid == 0) { - free(timer); - return NULL; - } - - fibril_mutex_initialize(&timer->lock); - fibril_condvar_initialize(&timer->cv); - - timer->fibril = fid; - timer->state = fts_not_set; - timer->lockp = (lock != NULL) ? lock : &timer->lock; - - fibril_add_ready(fid); - return timer; -} - -/** Destroy timer. - * - * @param timer Timer, must not be active or accessed by other threads. - */ -void fibril_timer_destroy(fibril_timer_t *timer) -{ - fibril_mutex_lock(timer->lockp); - assert(timer->state == fts_not_set || timer->state == fts_fired); - - /* Request timer fibril to terminate. */ - timer->state = fts_cleanup; - fibril_condvar_broadcast(&timer->cv); - - /* Wait for timer fibril to terminate */ - while (timer->state != fts_clean) - fibril_condvar_wait(&timer->cv, timer->lockp); - fibril_mutex_unlock(timer->lockp); - - free(timer); -} - -/** Set timer. - * - * Set timer to execute a callback function after the specified - * interval. - * - * @param timer Timer - * @param delay Delay in microseconds - * @param fun Callback function - * @param arg Argument for @a fun - */ -void fibril_timer_set(fibril_timer_t *timer, suseconds_t delay, - fibril_timer_fun_t fun, void *arg) -{ - fibril_mutex_lock(timer->lockp); - fibril_timer_set_locked(timer, delay, fun, arg); - fibril_mutex_unlock(timer->lockp); -} - -/** Set locked timer. - * - * Set timer to execute a callback function after the specified - * interval. Must be called when the timer is locked. - * - * @param timer Timer - * @param delay Delay in microseconds - * @param fun Callback function - * @param arg Argument for @a fun - */ -void fibril_timer_set_locked(fibril_timer_t *timer, suseconds_t delay, - fibril_timer_fun_t fun, void *arg) -{ - assert(fibril_mutex_is_locked(timer->lockp)); - assert(timer->state == fts_not_set || timer->state == fts_fired); - timer->state = fts_active; - timer->delay = delay; - timer->fun = fun; - timer->arg = arg; - fibril_condvar_broadcast(&timer->cv); -} - -/** Clear timer. - * - * Clears (cancels) timer and returns last state of the timer. - * This can be one of: - * - fts_not_set If the timer has not been set or has been cleared - * - fts_active Timer was set but did not fire - * - fts_fired Timer fired - * - * @param timer Timer - * @return Last timer state - */ -fibril_timer_state_t fibril_timer_clear(fibril_timer_t *timer) -{ - fibril_timer_state_t old_state; - - fibril_mutex_lock(timer->lockp); - old_state = fibril_timer_clear_locked(timer); - fibril_mutex_unlock(timer->lockp); - - return old_state; -} - -/** Clear locked timer. - * - * Clears (cancels) timer and returns last state of the timer. - * This can be one of: - * - fts_not_set If the timer has not been set or has been cleared - * - fts_active Timer was set but did not fire - * - fts_fired Timer fired - * Must be called when the timer is locked. - * - * @param timer Timer - * @return Last timer state - */ -fibril_timer_state_t fibril_timer_clear_locked(fibril_timer_t *timer) -{ - fibril_timer_state_t old_state; - - assert(fibril_mutex_is_locked(timer->lockp)); - - while (timer->handler_fid != 0) { - if (timer->handler_fid == fibril_get_id()) { - printf("Deadlock detected.\n"); - stacktrace_print(); - printf("Fibril %p is trying to clear timer %p from " - "inside its handler %p.\n", - fibril_get_id(), timer, timer->fun); - abort(); - } - - fibril_condvar_wait(&timer->cv, timer->lockp); - } - - old_state = timer->state; - timer->state = fts_not_set; - - timer->delay = 0; - timer->fun = NULL; - timer->arg = NULL; - fibril_condvar_broadcast(&timer->cv); - - return old_state; -} - -/** - * Initialize a semaphore with initial count set to the provided value. - * - * @param sem Semaphore to initialize. - * @param count Initial count. Must not be negative. - */ -void fibril_semaphore_initialize(fibril_semaphore_t *sem, long count) -{ - /* - * Negative count denotes the length of waitlist, - * so it makes no sense as an initial value. - */ - assert(count >= 0); - sem->closed = false; - sem->count = count; - list_initialize(&sem->waiters); -} - -/** - * Produce one token. - * If there are fibrils waiting for tokens, this operation satisfies - * exactly one waiting `fibril_semaphore_down()`. - * This operation never blocks the fibril. - * - * @param sem Semaphore to use. - */ -void fibril_semaphore_up(fibril_semaphore_t *sem) -{ - futex_lock(&fibril_synch_futex); - - if (sem->closed) { - futex_unlock(&fibril_synch_futex); - return; - } - - sem->count++; - - if (sem->count <= 0) { - awaiter_t *w = list_pop(&sem->waiters, awaiter_t, link); - assert(w); - fibril_notify(&w->event); - } - - futex_unlock(&fibril_synch_futex); -} - -/** - * Consume one token. - * If there are no available tokens (count <= 0), this operation blocks until - * another fibril produces a token using `fibril_semaphore_up()`. - * - * @param sem Semaphore to use. - */ -void fibril_semaphore_down(fibril_semaphore_t *sem) -{ - futex_lock(&fibril_synch_futex); - - if (sem->closed) { - futex_unlock(&fibril_synch_futex); - return; - } - - sem->count--; - - if (sem->count >= 0) { - futex_unlock(&fibril_synch_futex); - return; - } - - awaiter_t wdata = AWAITER_INIT; - list_append(&wdata.link, &sem->waiters); - - futex_unlock(&fibril_synch_futex); - - fibril_wait_for(&wdata.event); -} - -errno_t fibril_semaphore_down_timeout(fibril_semaphore_t *sem, suseconds_t timeout) -{ - if (timeout < 0) - return ETIMEOUT; - - futex_lock(&fibril_synch_futex); - if (sem->closed) { - futex_unlock(&fibril_synch_futex); - return EOK; - } - - sem->count--; - - if (sem->count >= 0) { - futex_unlock(&fibril_synch_futex); - return EOK; - } - - awaiter_t wdata = AWAITER_INIT; - list_append(&wdata.link, &sem->waiters); - - futex_unlock(&fibril_synch_futex); - - struct timeval tv; - struct timeval *expires = NULL; - if (timeout) { - getuptime(&tv); - tv_add_diff(&tv, timeout); - expires = &tv; - } - - errno_t rc = fibril_wait_timeout(&wdata.event, expires); - if (rc == EOK) - return EOK; - - futex_lock(&fibril_synch_futex); - if (!link_in_use(&wdata.link)) { - futex_unlock(&fibril_synch_futex); - return EOK; - } - - list_remove(&wdata.link); - sem->count++; - futex_unlock(&fibril_synch_futex); - - return rc; -} - -/** - * Close the semaphore. - * All future down() operations return instantly. - */ -void fibril_semaphore_close(fibril_semaphore_t *sem) -{ - futex_lock(&fibril_synch_futex); - sem->closed = true; - awaiter_t *w; - - while ((w = list_pop(&sem->waiters, awaiter_t, link))) - fibril_notify(&w->event); - - futex_unlock(&fibril_synch_futex); -} - -/** @} - */ Index: uspace/lib/c/generic/futex.c =================================================================== --- uspace/lib/c/generic/futex.c (revision d742db216b1d7efda0a82bee848205d7ffe4a730) +++ (revision ) @@ -1,139 +1,0 @@ -/* - * Copyright (c) 2008 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 - */ - -#include - -#include -#include -#include -#include - -#include "private/fibril.h" - -//#define DPRINTF(...) kio_printf(__VA_ARGS__) -#define DPRINTF(...) dummy_printf(__VA_ARGS__) - -/** Initialize futex counter. - * - * @param futex Futex. - * @param val Initialization value. - * - */ -void futex_initialize(futex_t *futex, int val) -{ - atomic_set(&futex->val, val); -} - -#ifdef CONFIG_DEBUG_FUTEX - -void __futex_assert_is_locked(futex_t *futex, const char *name) -{ - void *owner = __atomic_load_n(&futex->owner, __ATOMIC_RELAXED); - fibril_t *self = (fibril_t *) fibril_get_id(); - if (owner != self) { - DPRINTF("Assertion failed: %s (%p) is not locked by fibril %p (instead locked by fibril %p).\n", name, futex, self, owner); - } - assert(owner == self); -} - -void __futex_assert_is_not_locked(futex_t *futex, const char *name) -{ - void *owner = __atomic_load_n(&futex->owner, __ATOMIC_RELAXED); - fibril_t *self = (fibril_t *) fibril_get_id(); - if (owner == self) { - DPRINTF("Assertion failed: %s (%p) is already locked by fibril %p.\n", name, futex, self); - } - assert(owner != self); -} - -void __futex_lock(futex_t *futex, const char *name) -{ - /* - * We use relaxed atomics to avoid violating C11 memory model. - * They should compile to regular load/stores, but simple assignments - * would be UB by definition. - * The proper ordering is ensured by the surrounding futex operation. - */ - - fibril_t *self = (fibril_t *) fibril_get_id(); - DPRINTF("Locking futex %s (%p) by fibril %p.\n", name, futex, self); - __futex_assert_is_not_locked(futex, name); - futex_down(futex); - - void *prev_owner = __atomic_load_n(&futex->owner, __ATOMIC_RELAXED); - assert(prev_owner == NULL); - __atomic_store_n(&futex->owner, self, __ATOMIC_RELAXED); -} - -void __futex_unlock(futex_t *futex, const char *name) -{ - fibril_t *self = (fibril_t *) fibril_get_id(); - DPRINTF("Unlocking futex %s (%p) by fibril %p.\n", name, futex, self); - __futex_assert_is_locked(futex, name); - __atomic_store_n(&futex->owner, NULL, __ATOMIC_RELAXED); - futex_up(futex); -} - -bool __futex_trylock(futex_t *futex, const char *name) -{ - fibril_t *self = (fibril_t *) fibril_get_id(); - bool success = futex_trydown(futex); - if (success) { - void *owner = __atomic_load_n(&futex->owner, __ATOMIC_RELAXED); - assert(owner == NULL); - - __atomic_store_n(&futex->owner, self, __ATOMIC_RELAXED); - - DPRINTF("Trylock on futex %s (%p) by fibril %p succeeded.\n", name, futex, self); - } else { - DPRINTF("Trylock on futex %s (%p) by fibril %p failed.\n", name, futex, self); - } - - return success; -} - -void __futex_give_to(futex_t *futex, void *new_owner, const char *name) -{ - fibril_t *self = fibril_self(); - fibril_t *no = new_owner; - DPRINTF("Passing futex %s (%p) from fibril %p to fibril %p.\n", name, futex, self, no); - - __futex_assert_is_locked(futex, name); - __atomic_store_n(&futex->owner, new_owner, __ATOMIC_RELAXED); -} - -#endif - -/** @} - */ Index: uspace/lib/c/generic/rcu.c =================================================================== --- uspace/lib/c/generic/rcu.c (revision d742db216b1d7efda0a82bee848205d7ffe4a730) +++ (revision ) @@ -1,442 +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 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 -#include - -#include "private/fibril.h" - - -/** 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; - fibril_rmutex_t list_mutex; - list_t fibrils_list; - struct { - fibril_rmutex_t mutex; - bool locked; - list_t blocked_fibrils; - } sync_lock; -} rcu_data_t; - -typedef struct blocked_fibril { - fibril_event_t unblock; - 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_mutex = FIBRIL_RMUTEX_INITIALIZER(rcu.list_mutex), - .fibrils_list = LIST_INITIALIZER(rcu.fibrils_list), - .sync_lock = { - .mutex = FIBRIL_RMUTEX_INITIALIZER(rcu.sync_lock.mutex), - .locked = false, - .blocked_fibrils = LIST_INITIALIZER(rcu.sync_lock.blocked_fibrils), - }, -}; - - -static void wait_for_readers(size_t reader_group); -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(void); -static void unlock_sync(void); -static void sync_sleep(void); - -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); - - fibril_rmutex_lock(&rcu.list_mutex); - list_append(&fibril_rcu.link, &rcu.fibrils_list); - fibril_rmutex_unlock(&rcu.list_mutex); - - 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; - - fibril_rmutex_lock(&rcu.list_mutex); - list_remove(&fibril_rcu.link); - fibril_rmutex_unlock(&rcu.list_mutex); - - 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 end 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(void) -{ - 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(); - - /* - * 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); - - /* 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); - - /* 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) -{ - fibril_rmutex_lock(&rcu.list_mutex); - - 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)) { - fibril_rmutex_unlock(&rcu.list_mutex); - sync_sleep(); - fibril_rmutex_lock(&rcu.list_mutex); - /* Break to while loop. */ - break; - } else { - list_remove(fibril_it); - list_append(fibril_it, &quiescent_fibrils); - } - } - } - - list_concat(&rcu.fibrils_list, &quiescent_fibrils); - fibril_rmutex_unlock(&rcu.list_mutex); -} - -static void lock_sync(void) -{ - fibril_rmutex_lock(&rcu.sync_lock.mutex); - if (rcu.sync_lock.locked) { - blocked_fibril_t blocked_fib; - blocked_fib.unblock = FIBRIL_EVENT_INIT; - - list_append(&blocked_fib.link, &rcu.sync_lock.blocked_fibrils); - - do { - blocked_fib.is_ready = false; - fibril_rmutex_unlock(&rcu.sync_lock.mutex); - fibril_wait_for(&blocked_fib.unblock); - fibril_rmutex_lock(&rcu.sync_lock.mutex); - } while (rcu.sync_lock.locked); - - list_remove(&blocked_fib.link); - rcu.sync_lock.locked = true; - } else { - rcu.sync_lock.locked = true; - } -} - -static void unlock_sync(void) -{ - assert(rcu.sync_lock.locked); - - /* 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_notify(&blocked_fib->unblock); - } - } - - rcu.sync_lock.locked = false; - fibril_rmutex_unlock(&rcu.sync_lock.mutex); -} - -static void sync_sleep(void) -{ - assert(rcu.sync_lock.locked); - /* - * Release the futex to avoid deadlocks in singlethreaded apps - * but keep sync locked. - */ - fibril_rmutex_unlock(&rcu.sync_lock.mutex); - fibril_usleep(RCU_SLEEP_MS * 1000); - fibril_rmutex_lock(&rcu.sync_lock.mutex); -} - - -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/c/generic/thread.c =================================================================== --- uspace/lib/c/generic/thread.c (revision d742db216b1d7efda0a82bee848205d7ffe4a730) +++ (revision ) @@ -1,204 +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 - */ - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include "private/thread.h" -#include "private/fibril.h" - -/** Main thread function. - * - * This function is called from __thread_entry() and is used - * to call the thread's implementing function and perform cleanup - * and exit when thread returns back. - * - * @param uarg Pointer to userspace argument structure. - * - */ -void __thread_main(uspace_arg_t *uarg) -{ - assert(!__tcb_is_set()); - - fibril_t *fibril = uarg->uspace_thread_arg; - assert(fibril); - - __tcb_set(fibril->tcb); - - uarg->uspace_thread_function(fibril->arg); - /* - * XXX: we cannot free the userspace stack while running on it - * - * free(uarg->uspace_stack); - * free(uarg); - */ - - fibril_teardown(fibril); - thread_exit(0); -} - -/** Create userspace thread. - * - * This function creates new userspace thread and allocates userspace - * stack and userspace argument structure for it. - * - * @param function Function implementing the thread. - * @param arg Argument to be passed to thread. - * @param name Symbolic name of the thread. - * @param tid Thread ID of the newly created thread. - * - * @return Zero on success or a code from @ref errno.h on failure. - */ -errno_t thread_create(void (*function)(void *), void *arg, const char *name, - thread_id_t *tid) -{ - uspace_arg_t *uarg = calloc(1, sizeof(uspace_arg_t)); - if (!uarg) - return ENOMEM; - - fibril_t *fibril = fibril_alloc(); - if (!fibril) { - free(uarg); - return ENOMEM; - } - - size_t stack_size = stack_size_get(); - void *stack = as_area_create(AS_AREA_ANY, stack_size, - AS_AREA_READ | AS_AREA_WRITE | AS_AREA_CACHEABLE | AS_AREA_GUARD | - AS_AREA_LATE_RESERVE, AS_AREA_UNPAGED); - if (stack == AS_MAP_FAILED) { - fibril_teardown(fibril); - free(uarg); - return ENOMEM; - } - - fibril->arg = arg; - uarg->uspace_entry = (void *) FADDR(__thread_entry); - uarg->uspace_stack = stack; - uarg->uspace_stack_size = stack_size; - uarg->uspace_thread_function = function; - uarg->uspace_thread_arg = fibril; - uarg->uspace_uarg = uarg; - - errno_t rc = (errno_t) __SYSCALL4(SYS_THREAD_CREATE, (sysarg_t) uarg, - (sysarg_t) name, (sysarg_t) str_size(name), (sysarg_t) tid); - - if (rc != EOK) { - /* - * Failed to create a new thread. - * Free up the allocated data. - */ - as_area_destroy(stack); - free(uarg); - } - - return rc; -} - -/** Terminate current thread. - * - * @param status Exit status. Currently not used. - * - */ -void thread_exit(int status) -{ - __SYSCALL1(SYS_THREAD_EXIT, (sysarg_t) status); - - /* Unreachable */ - while (true) - ; -} - -/** Detach thread. - * - * Currently not implemented. - * - * @param thread TID. - */ -void thread_detach(thread_id_t thread) -{ -} - -/** Get current thread ID. - * - * @return Current thread ID. - */ -thread_id_t thread_get_id(void) -{ - thread_id_t thread_id; - - (void) __SYSCALL1(SYS_THREAD_GET_ID, (sysarg_t) &thread_id); - - return thread_id; -} - -/** Wait unconditionally for specified number of microseconds - * - */ -int thread_usleep(useconds_t usec) -{ - (void) __SYSCALL1(SYS_THREAD_USLEEP, usec); - return 0; -} - -/** Wait unconditionally for specified number of seconds - * - */ -unsigned int thread_sleep(unsigned int sec) -{ - /* - * Sleep in 1000 second steps to support - * full argument range - */ - - while (sec > 0) { - unsigned int period = (sec > 1000) ? 1000 : sec; - - thread_usleep(period * 1000000); - sec -= period; - } - - return 0; -} - -/** @} - */ Index: uspace/lib/c/generic/thread/atomic.c =================================================================== --- uspace/lib/c/generic/thread/atomic.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) +++ uspace/lib/c/generic/thread/atomic.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2018 CZ.NIC, z.s.p.o. + * 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. + */ + +#include + +#ifdef PLATFORM_arm32 + +/* + * Older ARMs don't have atomic instructions, so we need to define a bunch + * of symbols for GCC to use. + */ + +unsigned __sync_add_and_fetch_4(volatile void *vptr, unsigned val) +{ + return atomic_add((atomic_t *)vptr, val); +} + +unsigned __sync_sub_and_fetch_4(volatile void *vptr, unsigned val) +{ + return atomic_add((atomic_t *)vptr, -(atomic_signed_t)val); +} + +bool __sync_bool_compare_and_swap_4(volatile void *ptr, unsigned old_val, unsigned new_val) +{ + return cas((atomic_t *)ptr, old_val, new_val); +} + +unsigned __sync_val_compare_and_swap_4(volatile void *ptr, unsigned old_val, unsigned new_val) +{ + while (true) { + if (__sync_bool_compare_and_swap_4(ptr, old_val, new_val)) { + return old_val; + } + + unsigned current = *(volatile unsigned *)ptr; + if (current != old_val) + return current; + + /* If the current value is the same as old_val, retry. */ + } +} + +#endif Index: uspace/lib/c/generic/thread/fibril.c =================================================================== --- uspace/lib/c/generic/thread/fibril.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) +++ uspace/lib/c/generic/thread/fibril.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) @@ -0,0 +1,918 @@ +/* + * Copyright (c) 2006 Ondrej Palkovsky + * Copyright (c) 2007 Jakub Jermar + * Copyright (c) 2018 CZ.NIC, z.s.p.o. + * 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 +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +#include "../private/thread.h" +#include "../private/fibril.h" +#include "../private/libc.h" + +#define DPRINTF(...) ((void)0) +#undef READY_DEBUG + +/** Member of timeout_list. */ +typedef struct { + link_t link; + struct timeval expires; + fibril_event_t *event; +} _timeout_t; + +typedef struct { + errno_t rc; + link_t link; + ipc_call_t *call; + fibril_event_t event; +} _ipc_waiter_t; + +typedef struct { + errno_t rc; + link_t link; + ipc_call_t call; +} _ipc_buffer_t; + +typedef enum { + SWITCH_FROM_DEAD, + SWITCH_FROM_HELPER, + SWITCH_FROM_YIELD, + SWITCH_FROM_BLOCKED, +} _switch_type_t; + +static bool multithreaded = false; + +/* This futex serializes access to global data. */ +static futex_t fibril_futex = FUTEX_INITIALIZER; +static futex_t ready_semaphore = FUTEX_INITIALIZE(0); +static long ready_st_count; + +static LIST_INITIALIZE(ready_list); +static LIST_INITIALIZE(fibril_list); +static LIST_INITIALIZE(timeout_list); + +static futex_t ipc_lists_futex = FUTEX_INITIALIZER; +static LIST_INITIALIZE(ipc_waiter_list); +static LIST_INITIALIZE(ipc_buffer_list); +static LIST_INITIALIZE(ipc_buffer_free_list); + +/* Only used as unique markers for triggered events. */ +static fibril_t _fibril_event_triggered; +static fibril_t _fibril_event_timed_out; +#define _EVENT_INITIAL (NULL) +#define _EVENT_TRIGGERED (&_fibril_event_triggered) +#define _EVENT_TIMED_OUT (&_fibril_event_timed_out) + +static inline void _ready_debug_check(void) +{ +#ifdef READY_DEBUG + assert(!multithreaded); + long count = (long) list_count(&ready_list) + + (long) list_count(&ipc_buffer_free_list); + assert(ready_st_count == count); +#endif +} + +static inline long _ready_count(void) +{ + /* + * The number of available tokens is always equal to the number + * of fibrils in the ready list + the number of free IPC buffer + * buckets. + */ + + if (multithreaded) + return atomic_get(&ready_semaphore.val); + + _ready_debug_check(); + return ready_st_count; +} + +static inline void _ready_up(void) +{ + if (multithreaded) { + futex_up(&ready_semaphore); + } else { + ready_st_count++; + _ready_debug_check(); + } +} + +static inline errno_t _ready_down(const struct timeval *expires) +{ + if (multithreaded) + return futex_down_timeout(&ready_semaphore, expires); + + _ready_debug_check(); + ready_st_count--; + return EOK; +} + +static atomic_t threads_in_ipc_wait = { 0 }; + +/** Function that spans the whole life-cycle of a fibril. + * + * Each fibril begins execution in this function. Then the function implementing + * the fibril logic is called. After its return, the return value is saved. + * The fibril then switches to another fibril, which cleans up after it. + * + */ +static void _fibril_main(void) +{ + /* fibril_futex is locked when a fibril is started. */ + futex_unlock(&fibril_futex); + + fibril_t *fibril = fibril_self(); + + /* Call the implementing function. */ + fibril_exit(fibril->func(fibril->arg)); + + /* Not reached */ +} + +/** Allocate a fibril structure and TCB, but don't do anything else with it. */ +fibril_t *fibril_alloc(void) +{ + tcb_t *tcb = tls_make(__progsymbols.elfstart); + if (!tcb) + return NULL; + + fibril_t *fibril = calloc(1, sizeof(fibril_t)); + if (!fibril) { + tls_free(tcb); + return NULL; + } + + tcb->fibril_data = fibril; + fibril->tcb = tcb; + fibril->is_freeable = true; + + fibril_setup(fibril); + return fibril; +} + +/** + * Put the fibril into fibril_list. + */ +void fibril_setup(fibril_t *f) +{ + futex_lock(&fibril_futex); + list_append(&f->all_link, &fibril_list); + futex_unlock(&fibril_futex); +} + +void fibril_teardown(fibril_t *fibril) +{ + futex_lock(&fibril_futex); + list_remove(&fibril->all_link); + futex_unlock(&fibril_futex); + + if (fibril->is_freeable) { + tls_free(fibril->tcb); + free(fibril); + } +} + +/** + * Event notification with a given reason. + * + * @param reason Reason of the notification. + * Can be either _EVENT_TRIGGERED or _EVENT_TIMED_OUT. + */ +static fibril_t *_fibril_trigger_internal(fibril_event_t *event, fibril_t *reason) +{ + assert(reason != _EVENT_INITIAL); + assert(reason == _EVENT_TIMED_OUT || reason == _EVENT_TRIGGERED); + + futex_assert_is_locked(&fibril_futex); + + if (event->fibril == _EVENT_INITIAL) { + event->fibril = reason; + return NULL; + } + + if (event->fibril == _EVENT_TIMED_OUT) { + assert(reason == _EVENT_TRIGGERED); + event->fibril = reason; + return NULL; + } + + if (event->fibril == _EVENT_TRIGGERED) { + /* Already triggered. Nothing to do. */ + return NULL; + } + + fibril_t *f = event->fibril; + event->fibril = reason; + + assert(f->sleep_event == event); + return f; +} + +static errno_t _ipc_wait(ipc_call_t *call, const struct timeval *expires) +{ + if (!expires) + return ipc_wait(call, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE); + + if (expires->tv_sec == 0) + return ipc_wait(call, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NON_BLOCKING); + + struct timeval now; + getuptime(&now); + + if (tv_gteq(&now, expires)) + return ipc_wait(call, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NON_BLOCKING); + + return ipc_wait(call, tv_sub_diff(expires, &now), SYNCH_FLAGS_NONE); +} + +/* + * Waits until a ready fibril is added to the list, or an IPC message arrives. + * Returns NULL on timeout and may also return NULL if returning from IPC + * wait after new ready fibrils are added. + */ +static fibril_t *_ready_list_pop(const struct timeval *expires, bool locked) +{ + if (locked) { + futex_assert_is_locked(&fibril_futex); + assert(expires); + /* Must be nonblocking. */ + assert(expires->tv_sec == 0); + } else { + futex_assert_is_not_locked(&fibril_futex); + } + + errno_t rc = _ready_down(expires); + if (rc != EOK) + return NULL; + + /* + * Once we acquire a token from ready_semaphore, there are two options. + * Either there is a ready fibril in the list, or it's our turn to + * call `ipc_wait_cycle()`. There is one extra token on the semaphore + * for each entry of the call buffer. + */ + + + if (!locked) + futex_lock(&fibril_futex); + fibril_t *f = list_pop(&ready_list, fibril_t, link); + if (!f) + atomic_inc(&threads_in_ipc_wait); + if (!locked) + futex_unlock(&fibril_futex); + + if (f) + return f; + + if (!multithreaded) + assert(list_empty(&ipc_buffer_list)); + + /* No fibril is ready, IPC wait it is. */ + ipc_call_t call = { 0 }; + rc = _ipc_wait(&call, expires); + + atomic_dec(&threads_in_ipc_wait); + + if (rc != EOK && rc != ENOENT) { + /* Return token. */ + _ready_up(); + return NULL; + } + + /* + * We might get ENOENT due to a poke. + * In that case, we propagate the null call out of fibril_ipc_wait(), + * because poke must result in that call returning. + */ + + /* + * If a fibril is already waiting for IPC, we wake up the fibril, + * and return the token to ready_semaphore. + * If there is no fibril waiting, we pop a buffer bucket and + * put our call there. The token then returns when the bucket is + * returned. + */ + + if (!locked) + futex_lock(&fibril_futex); + + futex_lock(&ipc_lists_futex); + + + _ipc_waiter_t *w = list_pop(&ipc_waiter_list, _ipc_waiter_t, link); + if (w) { + *w->call = call; + w->rc = rc; + /* We switch to the woken up fibril immediately if possible. */ + f = _fibril_trigger_internal(&w->event, _EVENT_TRIGGERED); + + /* Return token. */ + _ready_up(); + } else { + _ipc_buffer_t *buf = list_pop(&ipc_buffer_free_list, _ipc_buffer_t, link); + assert(buf); + *buf = (_ipc_buffer_t) { .call = call, .rc = rc }; + list_append(&buf->link, &ipc_buffer_list); + } + + futex_unlock(&ipc_lists_futex); + + if (!locked) + futex_unlock(&fibril_futex); + + return f; +} + +static fibril_t *_ready_list_pop_nonblocking(bool locked) +{ + struct timeval tv = { .tv_sec = 0, .tv_usec = 0 }; + return _ready_list_pop(&tv, locked); +} + +static void _ready_list_push(fibril_t *f) +{ + if (!f) + return; + + futex_assert_is_locked(&fibril_futex); + + /* Enqueue in ready_list. */ + list_append(&f->link, &ready_list); + _ready_up(); + + if (atomic_get(&threads_in_ipc_wait)) { + DPRINTF("Poking.\n"); + /* Wakeup one thread sleeping in SYS_IPC_WAIT. */ + ipc_poke(); + } +} + +/* Blocks the current fibril until an IPC call arrives. */ +static errno_t _wait_ipc(ipc_call_t *call, const struct timeval *expires) +{ + futex_assert_is_not_locked(&fibril_futex); + + futex_lock(&ipc_lists_futex); + _ipc_buffer_t *buf = list_pop(&ipc_buffer_list, _ipc_buffer_t, link); + if (buf) { + *call = buf->call; + errno_t rc = buf->rc; + + /* Return to freelist. */ + list_append(&buf->link, &ipc_buffer_free_list); + /* Return IPC wait token. */ + _ready_up(); + + futex_unlock(&ipc_lists_futex); + return rc; + } + + _ipc_waiter_t w = { .call = call }; + list_append(&w.link, &ipc_waiter_list); + futex_unlock(&ipc_lists_futex); + + errno_t rc = fibril_wait_timeout(&w.event, expires); + if (rc == EOK) + return w.rc; + + futex_lock(&ipc_lists_futex); + if (link_in_use(&w.link)) + list_remove(&w.link); + else + rc = w.rc; + futex_unlock(&ipc_lists_futex); + return rc; +} + +/** Fire all timeouts that expired. */ +static struct timeval *_handle_expired_timeouts(struct timeval *next_timeout) +{ + struct timeval tv; + getuptime(&tv); + + futex_lock(&fibril_futex); + + while (!list_empty(&timeout_list)) { + link_t *cur = list_first(&timeout_list); + _timeout_t *to = list_get_instance(cur, _timeout_t, link); + + if (tv_gt(&to->expires, &tv)) { + *next_timeout = to->expires; + futex_unlock(&fibril_futex); + return next_timeout; + } + + list_remove(&to->link); + + _ready_list_push(_fibril_trigger_internal( + to->event, _EVENT_TIMED_OUT)); + } + + futex_unlock(&fibril_futex); + return NULL; +} + +/** + * Clean up after a dead fibril from which we restored context, if any. + * Called after a switch is made and fibril_futex is unlocked. + */ +static void _fibril_cleanup_dead(void) +{ + fibril_t *srcf = fibril_self(); + if (!srcf->clean_after_me) + return; + + void *stack = srcf->clean_after_me->stack; + assert(stack); + as_area_destroy(stack); + fibril_teardown(srcf->clean_after_me); + srcf->clean_after_me = NULL; +} + +/** Switch to a fibril. */ +static void _fibril_switch_to(_switch_type_t type, fibril_t *dstf, bool locked) +{ + assert(fibril_self()->rmutex_locks == 0); + + if (!locked) + futex_lock(&fibril_futex); + else + futex_assert_is_locked(&fibril_futex); + + fibril_t *srcf = fibril_self(); + assert(srcf); + assert(dstf); + + switch (type) { + case SWITCH_FROM_YIELD: + _ready_list_push(srcf); + break; + case SWITCH_FROM_DEAD: + dstf->clean_after_me = srcf; + break; + case SWITCH_FROM_HELPER: + case SWITCH_FROM_BLOCKED: + break; + } + + dstf->thread_ctx = srcf->thread_ctx; + srcf->thread_ctx = NULL; + + /* Just some bookkeeping to allow better debugging of futex locks. */ + futex_give_to(&fibril_futex, dstf); + + /* Swap to the next fibril. */ + context_swap(&srcf->ctx, &dstf->ctx); + + assert(srcf == fibril_self()); + assert(srcf->thread_ctx); + + if (!locked) { + /* Must be after context_swap()! */ + futex_unlock(&fibril_futex); + _fibril_cleanup_dead(); + } +} + +/** + * Main function for a helper fibril. + * The helper fibril executes on threads in the lightweight fibril pool when + * there is no fibril ready to run. Its only purpose is to block until + * another fibril is ready, or a timeout expires, or an IPC message arrives. + * + * There is at most one helper fibril per thread. + * + */ +static errno_t _helper_fibril_fn(void *arg) +{ + /* Set itself as the thread's own context. */ + fibril_self()->thread_ctx = fibril_self(); + + (void) arg; + + struct timeval next_timeout; + while (true) { + struct timeval *to = _handle_expired_timeouts(&next_timeout); + fibril_t *f = _ready_list_pop(to, false); + if (f) { + _fibril_switch_to(SWITCH_FROM_HELPER, f, false); + } + } + + return EOK; +} + +/** Create a new fibril. + * + * @param func Implementing function of the new fibril. + * @param arg Argument to pass to func. + * @param stksz Stack size in bytes. + * + * @return 0 on failure or TLS of the new fibril. + * + */ +fid_t fibril_create_generic(errno_t (*func)(void *), void *arg, size_t stksz) +{ + fibril_t *fibril; + + fibril = fibril_alloc(); + if (fibril == NULL) + return 0; + + fibril->stack_size = (stksz == FIBRIL_DFLT_STK_SIZE) ? + stack_size_get() : stksz; + fibril->stack = as_area_create(AS_AREA_ANY, fibril->stack_size, + AS_AREA_READ | AS_AREA_WRITE | AS_AREA_CACHEABLE | AS_AREA_GUARD | + AS_AREA_LATE_RESERVE, AS_AREA_UNPAGED); + if (fibril->stack == AS_MAP_FAILED) { + fibril_teardown(fibril); + return 0; + } + + fibril->func = func; + fibril->arg = arg; + + context_create_t sctx = { + .fn = _fibril_main, + .stack_base = fibril->stack, + .stack_size = fibril->stack_size, + .tls = fibril->tcb, + }; + + context_create(&fibril->ctx, &sctx); + return (fid_t) fibril; +} + +/** Delete a fibril that has never run. + * + * Free resources of a fibril that has been created with fibril_create() + * but never started using fibril_start(). + * + * @param fid Pointer to the fibril structure of the fibril to be + * added. + */ +void fibril_destroy(fid_t fid) +{ + fibril_t *fibril = (fibril_t *) fid; + + assert(!fibril->is_running); + assert(fibril->stack); + as_area_destroy(fibril->stack); + fibril_teardown(fibril); +} + +static void _insert_timeout(_timeout_t *timeout) +{ + futex_assert_is_locked(&fibril_futex); + assert(timeout); + + link_t *tmp = timeout_list.head.next; + while (tmp != &timeout_list.head) { + _timeout_t *cur = list_get_instance(tmp, _timeout_t, link); + + if (tv_gteq(&cur->expires, &timeout->expires)) + break; + + tmp = tmp->next; + } + + list_insert_before(&timeout->link, tmp); +} + +/** + * Same as `fibril_wait_for()`, except with a timeout. + * + * It is guaranteed that timing out cannot cause another thread's + * `fibril_notify()` to be lost. I.e. the function returns success if and + * only if `fibril_notify()` was called after the last call to + * wait/wait_timeout returned, and before the call timed out. + * + * @return ETIMEOUT if timed out. EOK otherwise. + */ +errno_t fibril_wait_timeout(fibril_event_t *event, const struct timeval *expires) +{ + assert(fibril_self()->rmutex_locks == 0); + + DPRINTF("### Fibril %p sleeping on event %p.\n", fibril_self(), event); + + if (!fibril_self()->thread_ctx) { + fibril_self()->thread_ctx = + fibril_create_generic(_helper_fibril_fn, NULL, PAGE_SIZE); + if (!fibril_self()->thread_ctx) + return ENOMEM; + } + + futex_lock(&fibril_futex); + + if (event->fibril == _EVENT_TRIGGERED) { + DPRINTF("### Already triggered. Returning. \n"); + event->fibril = _EVENT_INITIAL; + futex_unlock(&fibril_futex); + return EOK; + } + + assert(event->fibril == _EVENT_INITIAL); + + fibril_t *srcf = fibril_self(); + fibril_t *dstf = NULL; + + /* + * We cannot block here waiting for another fibril becoming + * ready, since that would require unlocking the fibril_futex, + * and that in turn would allow another thread to restore + * the source fibril before this thread finished switching. + * + * Instead, we switch to an internal "helper" fibril whose only + * job is to wait for an event, freeing the source fibril for + * wakeups. There is always one for each running thread. + */ + + dstf = _ready_list_pop_nonblocking(true); + if (!dstf) { + // XXX: It is possible for the _ready_list_pop_nonblocking() to + // check for IPC, find a pending message, and trigger the + // event on which we are currently trying to sleep. + if (event->fibril == _EVENT_TRIGGERED) { + event->fibril = _EVENT_INITIAL; + futex_unlock(&fibril_futex); + return EOK; + } + + dstf = srcf->thread_ctx; + assert(dstf); + } + + _timeout_t timeout = { 0 }; + if (expires) { + timeout.expires = *expires; + timeout.event = event; + _insert_timeout(&timeout); + } + + assert(srcf); + + event->fibril = srcf; + srcf->sleep_event = event; + + assert(event->fibril != _EVENT_INITIAL); + + _fibril_switch_to(SWITCH_FROM_BLOCKED, dstf, true); + + assert(event->fibril != srcf); + assert(event->fibril != _EVENT_INITIAL); + assert(event->fibril == _EVENT_TIMED_OUT || event->fibril == _EVENT_TRIGGERED); + + list_remove(&timeout.link); + errno_t rc = (event->fibril == _EVENT_TIMED_OUT) ? ETIMEOUT : EOK; + event->fibril = _EVENT_INITIAL; + + futex_unlock(&fibril_futex); + _fibril_cleanup_dead(); + return rc; +} + +void fibril_wait_for(fibril_event_t *event) +{ + assert(fibril_self()->rmutex_locks == 0); + + (void) fibril_wait_timeout(event, NULL); +} + +void fibril_notify(fibril_event_t *event) +{ + futex_lock(&fibril_futex); + _ready_list_push(_fibril_trigger_internal(event, _EVENT_TRIGGERED)); + futex_unlock(&fibril_futex); +} + +/** Start a fibril that has not been running yet. */ +void fibril_start(fibril_t *fibril) +{ + futex_lock(&fibril_futex); + assert(!fibril->is_running); + fibril->is_running = true; + + if (!link_in_use(&fibril->all_link)) + list_append(&fibril->all_link, &fibril_list); + + _ready_list_push(fibril); + + futex_unlock(&fibril_futex); +} + +/** Start a fibril that has not been running yet. (obsolete) */ +void fibril_add_ready(fibril_t *fibril) +{ + fibril_start(fibril); +} + +/** @return the currently running fibril. */ +fibril_t *fibril_self(void) +{ + assert(__tcb_is_set()); + tcb_t *tcb = __tcb_get(); + assert(tcb->fibril_data); + return tcb->fibril_data; +} + +/** + * Obsolete, use fibril_self(). + * + * @return ID of the currently running fibril. + */ +fid_t fibril_get_id(void) +{ + return (fid_t) fibril_self(); +} + +/** + * Switch to another fibril, if one is ready to run. + * Has no effect on a heavy fibril. + */ +void fibril_yield(void) +{ + if (fibril_self()->rmutex_locks > 0) + return; + + fibril_t *f = _ready_list_pop_nonblocking(false); + if (f) + _fibril_switch_to(SWITCH_FROM_YIELD, f, false); +} + +static void _runner_fn(void *arg) +{ + _helper_fibril_fn(arg); +} + +/** + * Spawn a given number of runners (i.e. OS threads) immediately, and + * unconditionally. This is meant to be used for tests and debugging. + * Regular programs should just use `fibril_enable_multithreaded()`. + * + * @param n Number of runners to spawn. + * @return Number of runners successfully spawned. + */ +int fibril_test_spawn_runners(int n) +{ + assert(fibril_self()->rmutex_locks == 0); + + if (!multithreaded) { + _ready_debug_check(); + atomic_set(&ready_semaphore.val, ready_st_count); + multithreaded = true; + } + + errno_t rc; + + for (int i = 0; i < n; i++) { + thread_id_t tid; + rc = thread_create(_runner_fn, NULL, "fibril runner", &tid); + if (rc != EOK) + return i; + thread_detach(tid); + } + + return n; +} + +/** + * Opt-in to have more than one runner thread. + * + * Currently, a task only ever runs in one thread because multithreading + * might break some existing code. + * + * Eventually, the number of runner threads for a given task should become + * configurable in the environment and this function becomes no-op. + */ +void fibril_enable_multithreaded(void) +{ + // TODO: Implement better. + // For now, 4 total runners is a sensible default. + if (!multithreaded) { + fibril_test_spawn_runners(3); + } +} + +/** + * Detach a fibril. + */ +void fibril_detach(fid_t f) +{ + // TODO: Currently all fibrils are detached by default, but they + // won't always be. Code that explicitly spawns fibrils with + // limited lifetime should call this function. +} + +/** + * Exit a fibril. Never returns. + * + * @param retval Value to return from fibril_join() called on this fibril. + */ +_Noreturn void fibril_exit(long retval) +{ + // TODO: implement fibril_join() and remember retval + (void) retval; + + fibril_t *f = _ready_list_pop_nonblocking(false); + if (!f) + f = fibril_self()->thread_ctx; + + _fibril_switch_to(SWITCH_FROM_DEAD, f, false); + __builtin_unreachable(); +} + +void __fibrils_init(void) +{ + /* + * We allow a fixed, small amount of parallelism for IPC reads, but + * since IPC is currently serialized in kernel, there's not much + * we can get from more threads reading messages. + */ + +#define IPC_BUFFER_COUNT 1024 + static _ipc_buffer_t buffers[IPC_BUFFER_COUNT]; + + for (int i = 0; i < IPC_BUFFER_COUNT; i++) { + list_append(&buffers[i].link, &ipc_buffer_free_list); + _ready_up(); + } +} + +void fibril_usleep(suseconds_t timeout) +{ + struct timeval expires; + getuptime(&expires); + tv_add_diff(&expires, timeout); + + fibril_event_t event = FIBRIL_EVENT_INIT; + fibril_wait_timeout(&event, &expires); +} + +void fibril_sleep(unsigned int sec) +{ + struct timeval expires; + getuptime(&expires); + expires.tv_sec += sec; + + fibril_event_t event = FIBRIL_EVENT_INIT; + fibril_wait_timeout(&event, &expires); +} + +void fibril_ipc_poke(void) +{ + DPRINTF("Poking.\n"); + /* Wakeup one thread sleeping in SYS_IPC_WAIT. */ + ipc_poke(); +} + +errno_t fibril_ipc_wait(ipc_call_t *call, const struct timeval *expires) +{ + return _wait_ipc(call, expires); +} + +/** @} + */ Index: uspace/lib/c/generic/thread/fibril_synch.c =================================================================== --- uspace/lib/c/generic/thread/fibril_synch.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) +++ uspace/lib/c/generic/thread/fibril_synch.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) @@ -0,0 +1,795 @@ +/* + * Copyright (c) 2009 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 + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "../private/async.h" +#include "../private/fibril.h" + +void fibril_rmutex_initialize(fibril_rmutex_t *m) +{ + futex_initialize(&m->futex, 1); +} + +/** + * Lock restricted mutex. + * When a restricted mutex is locked, the fibril may not sleep or create new + * threads. Any attempt to do so will abort the program. + */ +void fibril_rmutex_lock(fibril_rmutex_t *m) +{ + futex_lock(&m->futex); + fibril_self()->rmutex_locks++; +} + +bool fibril_rmutex_trylock(fibril_rmutex_t *m) +{ + if (futex_trylock(&m->futex)) { + fibril_self()->rmutex_locks++; + return true; + } else { + return false; + } +} + +void fibril_rmutex_unlock(fibril_rmutex_t *m) +{ + fibril_self()->rmutex_locks--; + futex_unlock(&m->futex); +} + +static fibril_local bool deadlocked = false; + +static futex_t fibril_synch_futex = FUTEX_INITIALIZER; + +typedef struct { + link_t link; + fibril_event_t event; + fibril_mutex_t *mutex; + fid_t fid; +} awaiter_t; + +#define AWAITER_INIT { .fid = fibril_get_id() } + +static void print_deadlock(fibril_owner_info_t *oi) +{ + // FIXME: Print to stderr. + + fibril_t *f = (fibril_t *) fibril_get_id(); + + if (deadlocked) { + kio_printf("Deadlock detected while printing deadlock. Aborting.\n"); + abort(); + } + deadlocked = true; + + printf("Deadlock detected.\n"); + stacktrace_print(); + + printf("Fibril %p waits for primitive %p.\n", f, oi); + + while (oi && oi->owned_by) { + printf("Primitive %p is owned by fibril %p.\n", + oi, oi->owned_by); + if (oi->owned_by == f) + break; + stacktrace_print_fp_pc( + context_get_fp(&oi->owned_by->ctx), + context_get_pc(&oi->owned_by->ctx)); + printf("Fibril %p waits for primitive %p.\n", + oi->owned_by, oi->owned_by->waits_for); + oi = oi->owned_by->waits_for; + } +} + + +static void check_fibril_for_deadlock(fibril_owner_info_t *oi, fibril_t *fib) +{ + futex_assert_is_locked(&fibril_synch_futex); + + while (oi && oi->owned_by) { + if (oi->owned_by == fib) { + futex_unlock(&fibril_synch_futex); + print_deadlock(oi); + abort(); + } + oi = oi->owned_by->waits_for; + } +} + +static void check_for_deadlock(fibril_owner_info_t *oi) +{ + check_fibril_for_deadlock(oi, fibril_self()); +} + +void fibril_mutex_initialize(fibril_mutex_t *fm) +{ + fm->oi.owned_by = NULL; + fm->counter = 1; + list_initialize(&fm->waiters); +} + +void fibril_mutex_lock(fibril_mutex_t *fm) +{ + fibril_t *f = (fibril_t *) fibril_get_id(); + + futex_lock(&fibril_synch_futex); + + if (fm->counter-- > 0) { + fm->oi.owned_by = f; + futex_unlock(&fibril_synch_futex); + return; + } + + awaiter_t wdata = AWAITER_INIT; + list_append(&wdata.link, &fm->waiters); + check_for_deadlock(&fm->oi); + f->waits_for = &fm->oi; + + futex_unlock(&fibril_synch_futex); + + fibril_wait_for(&wdata.event); +} + +bool fibril_mutex_trylock(fibril_mutex_t *fm) +{ + bool locked = false; + + futex_lock(&fibril_synch_futex); + if (fm->counter > 0) { + fm->counter--; + fm->oi.owned_by = (fibril_t *) fibril_get_id(); + locked = true; + } + futex_unlock(&fibril_synch_futex); + + return locked; +} + +static void _fibril_mutex_unlock_unsafe(fibril_mutex_t *fm) +{ + assert(fm->oi.owned_by == (fibril_t *) fibril_get_id()); + + if (fm->counter++ < 0) { + awaiter_t *wdp = list_pop(&fm->waiters, awaiter_t, link); + assert(wdp); + + fibril_t *f = (fibril_t *) wdp->fid; + fm->oi.owned_by = f; + f->waits_for = NULL; + + fibril_notify(&wdp->event); + } else { + fm->oi.owned_by = NULL; + } +} + +void fibril_mutex_unlock(fibril_mutex_t *fm) +{ + futex_lock(&fibril_synch_futex); + _fibril_mutex_unlock_unsafe(fm); + futex_unlock(&fibril_synch_futex); +} + +bool fibril_mutex_is_locked(fibril_mutex_t *fm) +{ + futex_lock(&fibril_synch_futex); + bool locked = (fm->oi.owned_by == (fibril_t *) fibril_get_id()); + futex_unlock(&fibril_synch_futex); + return locked; +} + +void fibril_rwlock_initialize(fibril_rwlock_t *frw) +{ + frw->oi.owned_by = NULL; + frw->writers = 0; + frw->readers = 0; + list_initialize(&frw->waiters); +} + +void fibril_rwlock_read_lock(fibril_rwlock_t *frw) +{ + fibril_t *f = (fibril_t *) fibril_get_id(); + + futex_lock(&fibril_synch_futex); + + if (!frw->writers) { + /* Consider the first reader the owner. */ + if (frw->readers++ == 0) + frw->oi.owned_by = f; + futex_unlock(&fibril_synch_futex); + return; + } + + f->is_writer = false; + + awaiter_t wdata = AWAITER_INIT; + list_append(&wdata.link, &frw->waiters); + check_for_deadlock(&frw->oi); + f->waits_for = &frw->oi; + + futex_unlock(&fibril_synch_futex); + + fibril_wait_for(&wdata.event); +} + +void fibril_rwlock_write_lock(fibril_rwlock_t *frw) +{ + fibril_t *f = (fibril_t *) fibril_get_id(); + + futex_lock(&fibril_synch_futex); + + if (!frw->writers && !frw->readers) { + frw->oi.owned_by = f; + frw->writers++; + futex_unlock(&fibril_synch_futex); + return; + } + + f->is_writer = true; + + awaiter_t wdata = AWAITER_INIT; + list_append(&wdata.link, &frw->waiters); + check_for_deadlock(&frw->oi); + f->waits_for = &frw->oi; + + futex_unlock(&fibril_synch_futex); + + fibril_wait_for(&wdata.event); +} + +static void _fibril_rwlock_common_unlock(fibril_rwlock_t *frw) +{ + if (frw->readers) { + if (--frw->readers) { + if (frw->oi.owned_by == (fibril_t *) fibril_get_id()) { + /* + * If this reader fibril was considered the + * owner of this rwlock, clear the ownership + * information even if there are still more + * readers. + * + * This is the limitation of the detection + * mechanism rooted in the fact that tracking + * all readers would require dynamically + * allocated memory for keeping linkage info. + */ + frw->oi.owned_by = NULL; + } + + return; + } + } else { + frw->writers--; + } + + assert(!frw->readers && !frw->writers); + + frw->oi.owned_by = NULL; + + while (!list_empty(&frw->waiters)) { + link_t *tmp = list_first(&frw->waiters); + awaiter_t *wdp; + fibril_t *f; + + wdp = list_get_instance(tmp, awaiter_t, link); + f = (fibril_t *) wdp->fid; + + if (f->is_writer) { + if (frw->readers) + break; + frw->writers++; + } else { + frw->readers++; + } + + f->waits_for = NULL; + list_remove(&wdp->link); + frw->oi.owned_by = f; + fibril_notify(&wdp->event); + + if (frw->writers) + break; + } +} + +void fibril_rwlock_read_unlock(fibril_rwlock_t *frw) +{ + futex_lock(&fibril_synch_futex); + assert(frw->readers > 0); + _fibril_rwlock_common_unlock(frw); + futex_unlock(&fibril_synch_futex); +} + +void fibril_rwlock_write_unlock(fibril_rwlock_t *frw) +{ + futex_lock(&fibril_synch_futex); + assert(frw->writers == 1); + assert(frw->oi.owned_by == fibril_self()); + _fibril_rwlock_common_unlock(frw); + futex_unlock(&fibril_synch_futex); +} + +bool fibril_rwlock_is_read_locked(fibril_rwlock_t *frw) +{ + futex_lock(&fibril_synch_futex); + bool locked = (frw->readers > 0); + futex_unlock(&fibril_synch_futex); + return locked; +} + +bool fibril_rwlock_is_write_locked(fibril_rwlock_t *frw) +{ + futex_lock(&fibril_synch_futex); + assert(frw->writers <= 1); + bool locked = (frw->writers > 0) && (frw->oi.owned_by == fibril_self()); + futex_unlock(&fibril_synch_futex); + return locked; +} + +bool fibril_rwlock_is_locked(fibril_rwlock_t *frw) +{ + return fibril_rwlock_is_read_locked(frw) || + fibril_rwlock_is_write_locked(frw); +} + +void fibril_condvar_initialize(fibril_condvar_t *fcv) +{ + list_initialize(&fcv->waiters); +} + +/** + * FIXME: If `timeout` is negative, the function returns ETIMEOUT immediately, + * and if `timeout` is 0, the wait never times out. + * This is not consistent with other similar APIs. + */ +errno_t +fibril_condvar_wait_timeout(fibril_condvar_t *fcv, fibril_mutex_t *fm, + suseconds_t timeout) +{ + assert(fibril_mutex_is_locked(fm)); + + if (timeout < 0) + return ETIMEOUT; + + awaiter_t wdata = AWAITER_INIT; + wdata.mutex = fm; + + struct timeval tv; + struct timeval *expires = NULL; + if (timeout) { + getuptime(&tv); + tv_add_diff(&tv, timeout); + expires = &tv; + } + + futex_lock(&fibril_synch_futex); + _fibril_mutex_unlock_unsafe(fm); + list_append(&wdata.link, &fcv->waiters); + futex_unlock(&fibril_synch_futex); + + (void) fibril_wait_timeout(&wdata.event, expires); + + futex_lock(&fibril_synch_futex); + bool timed_out = link_in_use(&wdata.link); + list_remove(&wdata.link); + futex_unlock(&fibril_synch_futex); + + fibril_mutex_lock(fm); + + return timed_out ? ETIMEOUT : EOK; +} + +void fibril_condvar_wait(fibril_condvar_t *fcv, fibril_mutex_t *fm) +{ + (void) fibril_condvar_wait_timeout(fcv, fm, 0); +} + +void fibril_condvar_signal(fibril_condvar_t *fcv) +{ + futex_lock(&fibril_synch_futex); + + awaiter_t *w = list_pop(&fcv->waiters, awaiter_t, link); + if (w != NULL) + fibril_notify(&w->event); + + futex_unlock(&fibril_synch_futex); +} + +void fibril_condvar_broadcast(fibril_condvar_t *fcv) +{ + futex_lock(&fibril_synch_futex); + + awaiter_t *w; + while ((w = list_pop(&fcv->waiters, awaiter_t, link))) + fibril_notify(&w->event); + + futex_unlock(&fibril_synch_futex); +} + +/** Timer fibril. + * + * @param arg Timer + */ +static errno_t fibril_timer_func(void *arg) +{ + fibril_timer_t *timer = (fibril_timer_t *) arg; + errno_t rc; + + fibril_mutex_lock(timer->lockp); + + while (timer->state != fts_cleanup) { + switch (timer->state) { + case fts_not_set: + case fts_fired: + fibril_condvar_wait(&timer->cv, timer->lockp); + break; + case fts_active: + rc = fibril_condvar_wait_timeout(&timer->cv, + timer->lockp, timer->delay); + if (rc == ETIMEOUT && timer->state == fts_active) { + timer->state = fts_fired; + timer->handler_fid = fibril_get_id(); + fibril_mutex_unlock(timer->lockp); + timer->fun(timer->arg); + fibril_mutex_lock(timer->lockp); + timer->handler_fid = 0; + } + break; + case fts_cleanup: + case fts_clean: + assert(false); + break; + } + } + + /* Acknowledge timer fibril has finished cleanup. */ + timer->state = fts_clean; + fibril_condvar_broadcast(&timer->cv); + fibril_mutex_unlock(timer->lockp); + + return 0; +} + +/** Create new timer. + * + * @return New timer on success, @c NULL if out of memory. + */ +fibril_timer_t *fibril_timer_create(fibril_mutex_t *lock) +{ + fid_t fid; + fibril_timer_t *timer; + + timer = calloc(1, sizeof(fibril_timer_t)); + if (timer == NULL) + return NULL; + + fid = fibril_create(fibril_timer_func, (void *) timer); + if (fid == 0) { + free(timer); + return NULL; + } + + fibril_mutex_initialize(&timer->lock); + fibril_condvar_initialize(&timer->cv); + + timer->fibril = fid; + timer->state = fts_not_set; + timer->lockp = (lock != NULL) ? lock : &timer->lock; + + fibril_add_ready(fid); + return timer; +} + +/** Destroy timer. + * + * @param timer Timer, must not be active or accessed by other threads. + */ +void fibril_timer_destroy(fibril_timer_t *timer) +{ + fibril_mutex_lock(timer->lockp); + assert(timer->state == fts_not_set || timer->state == fts_fired); + + /* Request timer fibril to terminate. */ + timer->state = fts_cleanup; + fibril_condvar_broadcast(&timer->cv); + + /* Wait for timer fibril to terminate */ + while (timer->state != fts_clean) + fibril_condvar_wait(&timer->cv, timer->lockp); + fibril_mutex_unlock(timer->lockp); + + free(timer); +} + +/** Set timer. + * + * Set timer to execute a callback function after the specified + * interval. + * + * @param timer Timer + * @param delay Delay in microseconds + * @param fun Callback function + * @param arg Argument for @a fun + */ +void fibril_timer_set(fibril_timer_t *timer, suseconds_t delay, + fibril_timer_fun_t fun, void *arg) +{ + fibril_mutex_lock(timer->lockp); + fibril_timer_set_locked(timer, delay, fun, arg); + fibril_mutex_unlock(timer->lockp); +} + +/** Set locked timer. + * + * Set timer to execute a callback function after the specified + * interval. Must be called when the timer is locked. + * + * @param timer Timer + * @param delay Delay in microseconds + * @param fun Callback function + * @param arg Argument for @a fun + */ +void fibril_timer_set_locked(fibril_timer_t *timer, suseconds_t delay, + fibril_timer_fun_t fun, void *arg) +{ + assert(fibril_mutex_is_locked(timer->lockp)); + assert(timer->state == fts_not_set || timer->state == fts_fired); + timer->state = fts_active; + timer->delay = delay; + timer->fun = fun; + timer->arg = arg; + fibril_condvar_broadcast(&timer->cv); +} + +/** Clear timer. + * + * Clears (cancels) timer and returns last state of the timer. + * This can be one of: + * - fts_not_set If the timer has not been set or has been cleared + * - fts_active Timer was set but did not fire + * - fts_fired Timer fired + * + * @param timer Timer + * @return Last timer state + */ +fibril_timer_state_t fibril_timer_clear(fibril_timer_t *timer) +{ + fibril_timer_state_t old_state; + + fibril_mutex_lock(timer->lockp); + old_state = fibril_timer_clear_locked(timer); + fibril_mutex_unlock(timer->lockp); + + return old_state; +} + +/** Clear locked timer. + * + * Clears (cancels) timer and returns last state of the timer. + * This can be one of: + * - fts_not_set If the timer has not been set or has been cleared + * - fts_active Timer was set but did not fire + * - fts_fired Timer fired + * Must be called when the timer is locked. + * + * @param timer Timer + * @return Last timer state + */ +fibril_timer_state_t fibril_timer_clear_locked(fibril_timer_t *timer) +{ + fibril_timer_state_t old_state; + + assert(fibril_mutex_is_locked(timer->lockp)); + + while (timer->handler_fid != 0) { + if (timer->handler_fid == fibril_get_id()) { + printf("Deadlock detected.\n"); + stacktrace_print(); + printf("Fibril %p is trying to clear timer %p from " + "inside its handler %p.\n", + fibril_get_id(), timer, timer->fun); + abort(); + } + + fibril_condvar_wait(&timer->cv, timer->lockp); + } + + old_state = timer->state; + timer->state = fts_not_set; + + timer->delay = 0; + timer->fun = NULL; + timer->arg = NULL; + fibril_condvar_broadcast(&timer->cv); + + return old_state; +} + +/** + * Initialize a semaphore with initial count set to the provided value. + * + * @param sem Semaphore to initialize. + * @param count Initial count. Must not be negative. + */ +void fibril_semaphore_initialize(fibril_semaphore_t *sem, long count) +{ + /* + * Negative count denotes the length of waitlist, + * so it makes no sense as an initial value. + */ + assert(count >= 0); + sem->closed = false; + sem->count = count; + list_initialize(&sem->waiters); +} + +/** + * Produce one token. + * If there are fibrils waiting for tokens, this operation satisfies + * exactly one waiting `fibril_semaphore_down()`. + * This operation never blocks the fibril. + * + * @param sem Semaphore to use. + */ +void fibril_semaphore_up(fibril_semaphore_t *sem) +{ + futex_lock(&fibril_synch_futex); + + if (sem->closed) { + futex_unlock(&fibril_synch_futex); + return; + } + + sem->count++; + + if (sem->count <= 0) { + awaiter_t *w = list_pop(&sem->waiters, awaiter_t, link); + assert(w); + fibril_notify(&w->event); + } + + futex_unlock(&fibril_synch_futex); +} + +/** + * Consume one token. + * If there are no available tokens (count <= 0), this operation blocks until + * another fibril produces a token using `fibril_semaphore_up()`. + * + * @param sem Semaphore to use. + */ +void fibril_semaphore_down(fibril_semaphore_t *sem) +{ + futex_lock(&fibril_synch_futex); + + if (sem->closed) { + futex_unlock(&fibril_synch_futex); + return; + } + + sem->count--; + + if (sem->count >= 0) { + futex_unlock(&fibril_synch_futex); + return; + } + + awaiter_t wdata = AWAITER_INIT; + list_append(&wdata.link, &sem->waiters); + + futex_unlock(&fibril_synch_futex); + + fibril_wait_for(&wdata.event); +} + +errno_t fibril_semaphore_down_timeout(fibril_semaphore_t *sem, suseconds_t timeout) +{ + if (timeout < 0) + return ETIMEOUT; + + futex_lock(&fibril_synch_futex); + if (sem->closed) { + futex_unlock(&fibril_synch_futex); + return EOK; + } + + sem->count--; + + if (sem->count >= 0) { + futex_unlock(&fibril_synch_futex); + return EOK; + } + + awaiter_t wdata = AWAITER_INIT; + list_append(&wdata.link, &sem->waiters); + + futex_unlock(&fibril_synch_futex); + + struct timeval tv; + struct timeval *expires = NULL; + if (timeout) { + getuptime(&tv); + tv_add_diff(&tv, timeout); + expires = &tv; + } + + errno_t rc = fibril_wait_timeout(&wdata.event, expires); + if (rc == EOK) + return EOK; + + futex_lock(&fibril_synch_futex); + if (!link_in_use(&wdata.link)) { + futex_unlock(&fibril_synch_futex); + return EOK; + } + + list_remove(&wdata.link); + sem->count++; + futex_unlock(&fibril_synch_futex); + + return rc; +} + +/** + * Close the semaphore. + * All future down() operations return instantly. + */ +void fibril_semaphore_close(fibril_semaphore_t *sem) +{ + futex_lock(&fibril_synch_futex); + sem->closed = true; + awaiter_t *w; + + while ((w = list_pop(&sem->waiters, awaiter_t, link))) + fibril_notify(&w->event); + + futex_unlock(&fibril_synch_futex); +} + +/** @} + */ Index: uspace/lib/c/generic/thread/futex.c =================================================================== --- uspace/lib/c/generic/thread/futex.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) +++ uspace/lib/c/generic/thread/futex.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) @@ -0,0 +1,139 @@ +/* + * Copyright (c) 2008 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 + */ + +#include + +#include +#include +#include +#include + +#include "../private/fibril.h" + +//#define DPRINTF(...) kio_printf(__VA_ARGS__) +#define DPRINTF(...) dummy_printf(__VA_ARGS__) + +/** Initialize futex counter. + * + * @param futex Futex. + * @param val Initialization value. + * + */ +void futex_initialize(futex_t *futex, int val) +{ + atomic_set(&futex->val, val); +} + +#ifdef CONFIG_DEBUG_FUTEX + +void __futex_assert_is_locked(futex_t *futex, const char *name) +{ + void *owner = __atomic_load_n(&futex->owner, __ATOMIC_RELAXED); + fibril_t *self = (fibril_t *) fibril_get_id(); + if (owner != self) { + DPRINTF("Assertion failed: %s (%p) is not locked by fibril %p (instead locked by fibril %p).\n", name, futex, self, owner); + } + assert(owner == self); +} + +void __futex_assert_is_not_locked(futex_t *futex, const char *name) +{ + void *owner = __atomic_load_n(&futex->owner, __ATOMIC_RELAXED); + fibril_t *self = (fibril_t *) fibril_get_id(); + if (owner == self) { + DPRINTF("Assertion failed: %s (%p) is already locked by fibril %p.\n", name, futex, self); + } + assert(owner != self); +} + +void __futex_lock(futex_t *futex, const char *name) +{ + /* + * We use relaxed atomics to avoid violating C11 memory model. + * They should compile to regular load/stores, but simple assignments + * would be UB by definition. + * The proper ordering is ensured by the surrounding futex operation. + */ + + fibril_t *self = (fibril_t *) fibril_get_id(); + DPRINTF("Locking futex %s (%p) by fibril %p.\n", name, futex, self); + __futex_assert_is_not_locked(futex, name); + futex_down(futex); + + void *prev_owner = __atomic_load_n(&futex->owner, __ATOMIC_RELAXED); + assert(prev_owner == NULL); + __atomic_store_n(&futex->owner, self, __ATOMIC_RELAXED); +} + +void __futex_unlock(futex_t *futex, const char *name) +{ + fibril_t *self = (fibril_t *) fibril_get_id(); + DPRINTF("Unlocking futex %s (%p) by fibril %p.\n", name, futex, self); + __futex_assert_is_locked(futex, name); + __atomic_store_n(&futex->owner, NULL, __ATOMIC_RELAXED); + futex_up(futex); +} + +bool __futex_trylock(futex_t *futex, const char *name) +{ + fibril_t *self = (fibril_t *) fibril_get_id(); + bool success = futex_trydown(futex); + if (success) { + void *owner = __atomic_load_n(&futex->owner, __ATOMIC_RELAXED); + assert(owner == NULL); + + __atomic_store_n(&futex->owner, self, __ATOMIC_RELAXED); + + DPRINTF("Trylock on futex %s (%p) by fibril %p succeeded.\n", name, futex, self); + } else { + DPRINTF("Trylock on futex %s (%p) by fibril %p failed.\n", name, futex, self); + } + + return success; +} + +void __futex_give_to(futex_t *futex, void *new_owner, const char *name) +{ + fibril_t *self = fibril_self(); + fibril_t *no = new_owner; + DPRINTF("Passing futex %s (%p) from fibril %p to fibril %p.\n", name, futex, self, no); + + __futex_assert_is_locked(futex, name); + __atomic_store_n(&futex->owner, new_owner, __ATOMIC_RELAXED); +} + +#endif + +/** @} + */ Index: uspace/lib/c/generic/thread/rcu.c =================================================================== --- uspace/lib/c/generic/thread/rcu.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) +++ uspace/lib/c/generic/thread/rcu.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) @@ -0,0 +1,442 @@ +/* + * 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 +#include + +#include "../private/fibril.h" + + +/** 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; + fibril_rmutex_t list_mutex; + list_t fibrils_list; + struct { + fibril_rmutex_t mutex; + bool locked; + list_t blocked_fibrils; + } sync_lock; +} rcu_data_t; + +typedef struct blocked_fibril { + fibril_event_t unblock; + 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_mutex = FIBRIL_RMUTEX_INITIALIZER(rcu.list_mutex), + .fibrils_list = LIST_INITIALIZER(rcu.fibrils_list), + .sync_lock = { + .mutex = FIBRIL_RMUTEX_INITIALIZER(rcu.sync_lock.mutex), + .locked = false, + .blocked_fibrils = LIST_INITIALIZER(rcu.sync_lock.blocked_fibrils), + }, +}; + + +static void wait_for_readers(size_t reader_group); +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(void); +static void unlock_sync(void); +static void sync_sleep(void); + +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); + + fibril_rmutex_lock(&rcu.list_mutex); + list_append(&fibril_rcu.link, &rcu.fibrils_list); + fibril_rmutex_unlock(&rcu.list_mutex); + + 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; + + fibril_rmutex_lock(&rcu.list_mutex); + list_remove(&fibril_rcu.link); + fibril_rmutex_unlock(&rcu.list_mutex); + + 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 end 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(void) +{ + 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(); + + /* + * 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); + + /* 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); + + /* 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) +{ + fibril_rmutex_lock(&rcu.list_mutex); + + 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)) { + fibril_rmutex_unlock(&rcu.list_mutex); + sync_sleep(); + fibril_rmutex_lock(&rcu.list_mutex); + /* Break to while loop. */ + break; + } else { + list_remove(fibril_it); + list_append(fibril_it, &quiescent_fibrils); + } + } + } + + list_concat(&rcu.fibrils_list, &quiescent_fibrils); + fibril_rmutex_unlock(&rcu.list_mutex); +} + +static void lock_sync(void) +{ + fibril_rmutex_lock(&rcu.sync_lock.mutex); + if (rcu.sync_lock.locked) { + blocked_fibril_t blocked_fib; + blocked_fib.unblock = FIBRIL_EVENT_INIT; + + list_append(&blocked_fib.link, &rcu.sync_lock.blocked_fibrils); + + do { + blocked_fib.is_ready = false; + fibril_rmutex_unlock(&rcu.sync_lock.mutex); + fibril_wait_for(&blocked_fib.unblock); + fibril_rmutex_lock(&rcu.sync_lock.mutex); + } while (rcu.sync_lock.locked); + + list_remove(&blocked_fib.link); + rcu.sync_lock.locked = true; + } else { + rcu.sync_lock.locked = true; + } +} + +static void unlock_sync(void) +{ + assert(rcu.sync_lock.locked); + + /* 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_notify(&blocked_fib->unblock); + } + } + + rcu.sync_lock.locked = false; + fibril_rmutex_unlock(&rcu.sync_lock.mutex); +} + +static void sync_sleep(void) +{ + assert(rcu.sync_lock.locked); + /* + * Release the futex to avoid deadlocks in singlethreaded apps + * but keep sync locked. + */ + fibril_rmutex_unlock(&rcu.sync_lock.mutex); + fibril_usleep(RCU_SLEEP_MS * 1000); + fibril_rmutex_lock(&rcu.sync_lock.mutex); +} + + +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/c/generic/thread/thread.c =================================================================== --- uspace/lib/c/generic/thread/thread.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) +++ uspace/lib/c/generic/thread/thread.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) @@ -0,0 +1,205 @@ +/* + * 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 + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "../private/thread.h" +#include "../private/fibril.h" + +/** Main thread function. + * + * This function is called from __thread_entry() and is used + * to call the thread's implementing function and perform cleanup + * and exit when thread returns back. + * + * @param uarg Pointer to userspace argument structure. + * + */ +void __thread_main(uspace_arg_t *uarg) +{ + assert(!__tcb_is_set()); + + fibril_t *fibril = uarg->uspace_thread_arg; + assert(fibril); + + __tcb_set(fibril->tcb); + + uarg->uspace_thread_function(fibril->arg); + /* + * XXX: we cannot free the userspace stack while running on it + * + * free(uarg->uspace_stack); + * free(uarg); + */ + + fibril_teardown(fibril); + thread_exit(0); +} + +/** Create userspace thread. + * + * This function creates new userspace thread and allocates userspace + * stack and userspace argument structure for it. + * + * @param function Function implementing the thread. + * @param arg Argument to be passed to thread. + * @param name Symbolic name of the thread. + * @param tid Thread ID of the newly created thread. + * + * @return Zero on success or a code from @ref errno.h on failure. + */ +errno_t thread_create(void (*function)(void *), void *arg, const char *name, + thread_id_t *tid) +{ + uspace_arg_t *uarg = calloc(1, sizeof(uspace_arg_t)); + if (!uarg) + return ENOMEM; + + fibril_t *fibril = fibril_alloc(); + if (!fibril) { + free(uarg); + return ENOMEM; + } + + size_t stack_size = stack_size_get(); + void *stack = as_area_create(AS_AREA_ANY, stack_size, + AS_AREA_READ | AS_AREA_WRITE | AS_AREA_CACHEABLE | AS_AREA_GUARD | + AS_AREA_LATE_RESERVE, AS_AREA_UNPAGED); + if (stack == AS_MAP_FAILED) { + fibril_teardown(fibril); + free(uarg); + return ENOMEM; + } + + fibril->arg = arg; + uarg->uspace_entry = (void *) FADDR(__thread_entry); + uarg->uspace_stack = stack; + uarg->uspace_stack_size = stack_size; + uarg->uspace_thread_function = function; + uarg->uspace_thread_arg = fibril; + uarg->uspace_uarg = uarg; + + errno_t rc = (errno_t) __SYSCALL4(SYS_THREAD_CREATE, (sysarg_t) uarg, + (sysarg_t) name, (sysarg_t) str_size(name), (sysarg_t) tid); + + if (rc != EOK) { + /* + * Failed to create a new thread. + * Free up the allocated data. + */ + as_area_destroy(stack); + free(uarg); + } + + return rc; +} + +/** Terminate current thread. + * + * @param status Exit status. Currently not used. + * + */ +void thread_exit(int status) +{ + __SYSCALL1(SYS_THREAD_EXIT, (sysarg_t) status); + + /* Unreachable */ + while (true) + ; +} + +/** Detach thread. + * + * Currently not implemented. + * + * @param thread TID. + */ +void thread_detach(thread_id_t thread) +{ +} + +/** Get current thread ID. + * + * @return Current thread ID. + */ +thread_id_t thread_get_id(void) +{ + thread_id_t thread_id; + + (void) __SYSCALL1(SYS_THREAD_GET_ID, (sysarg_t) &thread_id); + + return thread_id; +} + +/** Wait unconditionally for specified number of microseconds + * + */ +int thread_usleep(useconds_t usec) +{ + (void) __SYSCALL1(SYS_THREAD_USLEEP, usec); + return 0; +} + +/** Wait unconditionally for specified number of seconds + * + */ +unsigned int thread_sleep(unsigned int sec) +{ + /* + * Sleep in 1000 second steps to support + * full argument range + */ + + while (sec > 0) { + unsigned int period = (sec > 1000) ? 1000 : sec; + + thread_usleep(period * 1000000); + sec -= period; + } + + return 0; +} + +/** @} + */ Index: uspace/lib/c/generic/thread/tls.c =================================================================== --- uspace/lib/c/generic/thread/tls.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) +++ uspace/lib/c/generic/thread/tls.c (revision 6340b4d2b8d527b31a31396c1e0dedb44bc5f58b) @@ -0,0 +1,256 @@ +/* + * 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 + * + * Support for thread-local storage, as described in: + * Drepper U.: ELF Handling For Thread-Local Storage, 2005 + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +#ifdef CONFIG_RTLD +#include +#endif + +#include "../private/libc.h" + +#if !defined(CONFIG_TLS_VARIANT_1) && !defined(CONFIG_TLS_VARIANT_2) +#error Unknown TLS variant. +#endif + +static ptrdiff_t _tcb_data_offset(void) +{ + const elf_segment_header_t *tls = + elf_get_phdr(__progsymbols.elfstart, PT_TLS); + + size_t tls_align = tls ? tls->p_align : 1; + +#ifdef CONFIG_TLS_VARIANT_1 + return ALIGN_UP((ptrdiff_t) sizeof(tcb_t), tls_align); +#else + size_t tls_size = tls ? tls->p_memsz : 0; + return -ALIGN_UP((ptrdiff_t) tls_size, max(tls_align, _Alignof(tcb_t))); +#endif +} + +/** Get address of static TLS block */ +void *tls_get(void) +{ +#ifdef CONFIG_RTLD + assert(runtime_env == NULL); +#endif + return (uint8_t *)__tcb_get() + _tcb_data_offset(); +} + +static tcb_t *tls_make_generic(const void *elf, void *(*alloc)(size_t, size_t)) +{ + assert(!elf_get_phdr(elf, PT_DYNAMIC)); +#ifdef CONFIG_RTLD + assert(runtime_env == NULL); +#endif + + const elf_segment_header_t *tls = elf_get_phdr(elf, PT_TLS); + size_t tls_size = tls ? tls->p_memsz : 0; + size_t tls_align = tls ? tls->p_align : 1; + + /* + * We don't currently support alignment this big, + * and neither should we need to. + */ + assert(tls_align <= PAGE_SIZE); + +#ifdef CONFIG_TLS_VARIANT_1 + size_t alloc_size = + ALIGN_UP(sizeof(tcb_t), tls_align) + tls_size; +#else + size_t alloc_size = + ALIGN_UP(tls_size, max(tls_align, _Alignof(tcb_t))) + sizeof(tcb_t); +#endif + + void *area = alloc(max(tls_align, _Alignof(tcb_t)), alloc_size); + if (!area) + return NULL; + +#ifdef CONFIG_TLS_VARIANT_1 + tcb_t *tcb = area; + uint8_t *data = (uint8_t *)tcb + _tcb_data_offset(); + memset(tcb, 0, sizeof(*tcb)); +#else + uint8_t *data = area; + tcb_t *tcb = (tcb_t *) (data - _tcb_data_offset()); + memset(tcb, 0, sizeof(tcb_t)); + tcb->self = tcb; +#endif + + if (!tls) + return tcb; + + uintptr_t bias = elf_get_bias(elf); + + /* Copy thread local data from the initialization image. */ + memcpy(data, (void *)(tls->p_vaddr + bias), tls->p_filesz); + /* Zero out the thread local uninitialized data. */ + memset(data + tls->p_filesz, 0, tls->p_memsz - tls->p_filesz); + + return tcb; +} + +static void *early_alloc(size_t align, size_t alloc_size) +{ + assert(align <= PAGE_SIZE); + alloc_size = ALIGN_UP(alloc_size, PAGE_SIZE); + + void *area = as_area_create(AS_AREA_ANY, alloc_size, + AS_AREA_READ | AS_AREA_WRITE | AS_AREA_CACHEABLE, AS_AREA_UNPAGED); + if (area == AS_MAP_FAILED) + return NULL; + return area; +} + +/** Same as tls_make(), but uses as_area_create() instead of memalign(). + * Only used in __libc_main() if the program was created by the kernel. + */ +tcb_t *tls_make_initial(const void *elf) +{ + return tls_make_generic(elf, early_alloc); +} + +/** Create TLS (Thread Local Storage) data structures. + * + * @return Pointer to TCB. + */ +tcb_t *tls_make(const void *elf) +{ + // TODO: Always use rtld. + +#ifdef CONFIG_RTLD + if (runtime_env != NULL) + return rtld_tls_make(runtime_env); +#endif + + return tls_make_generic(elf, memalign); +} + +void tls_free(tcb_t *tcb) +{ +#ifdef CONFIG_RTLD + free(tcb->dtv); + + if (runtime_env != NULL) { + tls_free_arch(tcb, runtime_env->tls_size, runtime_env->tls_align); + return; + } +#endif + const elf_segment_header_t *tls = + elf_get_phdr(__progsymbols.elfstart, PT_TLS); + + assert(tls != NULL); + tls_free_arch(tcb, + ALIGN_UP(tls->p_memsz, tls->p_align) + sizeof(tcb_t), + max(tls->p_align, _Alignof(tcb_t))); +} + +#ifdef CONFIG_TLS_VARIANT_1 +/** Allocate TLS variant 1 data structures. + * + * @param data Start of TLS section. This is an output argument. + * @param size Size of tdata + tbss section. + * @return Pointer to tcb_t structure. + */ +tcb_t *tls_alloc_variant_1(size_t size, size_t align) +{ + tcb_t *tcb = memalign(align, size); + if (!tcb) + return NULL; + memset(tcb, 0, sizeof(tcb_t)); + return tcb; +} + +/** Free TLS variant I data structures. + * + * @param tcb Pointer to TCB structure. + * @param size This argument is ignored. + */ +void tls_free_variant_1(tcb_t *tcb, size_t size, size_t align) +{ + free(tcb); +} +#endif + +#ifdef CONFIG_TLS_VARIANT_2 +/** Allocate TLS variant II data structures. + * + * @param data Pointer to pointer to thread local data. This is + * actually an output argument. + * @param size Size of thread local data. + * @param align Alignment of thread local data. + * @return Pointer to TCB structure. + */ +tcb_t *tls_alloc_variant_2(size_t size, size_t align) +{ + void *data = memalign(align, size); + if (data == NULL) + return NULL; + + tcb_t *tcb = (tcb_t *) (data + size - sizeof(tcb_t)); + memset(tcb, 0, sizeof(tcb_t)); + tcb->self = tcb; + return tcb; +} + +/** Free TLS variant II data structures. + * + * @param tcb Pointer to TCB structure. + * @param size Size of thread local data. + * @param align Alignment of thread local data. + */ +void tls_free_variant_2(tcb_t *tcb, size_t size, size_t align) +{ + if (tcb != NULL) { + void *start = ((void *) tcb) + sizeof(tcb_t) - size; + free(start); + } +} +#endif + +/** @} + */ Index: uspace/lib/c/generic/tls.c =================================================================== --- uspace/lib/c/generic/tls.c (revision d742db216b1d7efda0a82bee848205d7ffe4a730) +++ (revision ) @@ -1,256 +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 - * - * Support for thread-local storage, as described in: - * Drepper U.: ELF Handling For Thread-Local Storage, 2005 - */ - -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include - -#ifdef CONFIG_RTLD -#include -#endif - -#include "private/libc.h" - -#if !defined(CONFIG_TLS_VARIANT_1) && !defined(CONFIG_TLS_VARIANT_2) -#error Unknown TLS variant. -#endif - -static ptrdiff_t _tcb_data_offset(void) -{ - const elf_segment_header_t *tls = - elf_get_phdr(__progsymbols.elfstart, PT_TLS); - - size_t tls_align = tls ? tls->p_align : 1; - -#ifdef CONFIG_TLS_VARIANT_1 - return ALIGN_UP((ptrdiff_t) sizeof(tcb_t), tls_align); -#else - size_t tls_size = tls ? tls->p_memsz : 0; - return -ALIGN_UP((ptrdiff_t) tls_size, max(tls_align, _Alignof(tcb_t))); -#endif -} - -/** Get address of static TLS block */ -void *tls_get(void) -{ -#ifdef CONFIG_RTLD - assert(runtime_env == NULL); -#endif - return (uint8_t *)__tcb_get() + _tcb_data_offset(); -} - -static tcb_t *tls_make_generic(const void *elf, void *(*alloc)(size_t, size_t)) -{ - assert(!elf_get_phdr(elf, PT_DYNAMIC)); -#ifdef CONFIG_RTLD - assert(runtime_env == NULL); -#endif - - const elf_segment_header_t *tls = elf_get_phdr(elf, PT_TLS); - size_t tls_size = tls ? tls->p_memsz : 0; - size_t tls_align = tls ? tls->p_align : 1; - - /* - * We don't currently support alignment this big, - * and neither should we need to. - */ - assert(tls_align <= PAGE_SIZE); - -#ifdef CONFIG_TLS_VARIANT_1 - size_t alloc_size = - ALIGN_UP(sizeof(tcb_t), tls_align) + tls_size; -#else - size_t alloc_size = - ALIGN_UP(tls_size, max(tls_align, _Alignof(tcb_t))) + sizeof(tcb_t); -#endif - - void *area = alloc(max(tls_align, _Alignof(tcb_t)), alloc_size); - if (!area) - return NULL; - -#ifdef CONFIG_TLS_VARIANT_1 - tcb_t *tcb = area; - uint8_t *data = (uint8_t *)tcb + _tcb_data_offset(); - memset(tcb, 0, sizeof(*tcb)); -#else - uint8_t *data = area; - tcb_t *tcb = (tcb_t *) (data - _tcb_data_offset()); - memset(tcb, 0, sizeof(tcb_t)); - tcb->self = tcb; -#endif - - if (!tls) - return tcb; - - uintptr_t bias = elf_get_bias(elf); - - /* Copy thread local data from the initialization image. */ - memcpy(data, (void *)(tls->p_vaddr + bias), tls->p_filesz); - /* Zero out the thread local uninitialized data. */ - memset(data + tls->p_filesz, 0, tls->p_memsz - tls->p_filesz); - - return tcb; -} - -static void *early_alloc(size_t align, size_t alloc_size) -{ - assert(align <= PAGE_SIZE); - alloc_size = ALIGN_UP(alloc_size, PAGE_SIZE); - - void *area = as_area_create(AS_AREA_ANY, alloc_size, - AS_AREA_READ | AS_AREA_WRITE | AS_AREA_CACHEABLE, AS_AREA_UNPAGED); - if (area == AS_MAP_FAILED) - return NULL; - return area; -} - -/** Same as tls_make(), but uses as_area_create() instead of memalign(). - * Only used in __libc_main() if the program was created by the kernel. - */ -tcb_t *tls_make_initial(const void *elf) -{ - return tls_make_generic(elf, early_alloc); -} - -/** Create TLS (Thread Local Storage) data structures. - * - * @return Pointer to TCB. - */ -tcb_t *tls_make(const void *elf) -{ - // TODO: Always use rtld. - -#ifdef CONFIG_RTLD - if (runtime_env != NULL) - return rtld_tls_make(runtime_env); -#endif - - return tls_make_generic(elf, memalign); -} - -void tls_free(tcb_t *tcb) -{ -#ifdef CONFIG_RTLD - free(tcb->dtv); - - if (runtime_env != NULL) { - tls_free_arch(tcb, runtime_env->tls_size, runtime_env->tls_align); - return; - } -#endif - const elf_segment_header_t *tls = - elf_get_phdr(__progsymbols.elfstart, PT_TLS); - - assert(tls != NULL); - tls_free_arch(tcb, - ALIGN_UP(tls->p_memsz, tls->p_align) + sizeof(tcb_t), - max(tls->p_align, _Alignof(tcb_t))); -} - -#ifdef CONFIG_TLS_VARIANT_1 -/** Allocate TLS variant 1 data structures. - * - * @param data Start of TLS section. This is an output argument. - * @param size Size of tdata + tbss section. - * @return Pointer to tcb_t structure. - */ -tcb_t *tls_alloc_variant_1(size_t size, size_t align) -{ - tcb_t *tcb = memalign(align, size); - if (!tcb) - return NULL; - memset(tcb, 0, sizeof(tcb_t)); - return tcb; -} - -/** Free TLS variant I data structures. - * - * @param tcb Pointer to TCB structure. - * @param size This argument is ignored. - */ -void tls_free_variant_1(tcb_t *tcb, size_t size, size_t align) -{ - free(tcb); -} -#endif - -#ifdef CONFIG_TLS_VARIANT_2 -/** Allocate TLS variant II data structures. - * - * @param data Pointer to pointer to thread local data. This is - * actually an output argument. - * @param size Size of thread local data. - * @param align Alignment of thread local data. - * @return Pointer to TCB structure. - */ -tcb_t *tls_alloc_variant_2(size_t size, size_t align) -{ - void *data = memalign(align, size); - if (data == NULL) - return NULL; - - tcb_t *tcb = (tcb_t *) (data + size - sizeof(tcb_t)); - memset(tcb, 0, sizeof(tcb_t)); - tcb->self = tcb; - return tcb; -} - -/** Free TLS variant II data structures. - * - * @param tcb Pointer to TCB structure. - * @param size Size of thread local data. - * @param align Alignment of thread local data. - */ -void tls_free_variant_2(tcb_t *tcb, size_t size, size_t align) -{ - if (tcb != NULL) { - void *start = ((void *) tcb) + sizeof(tcb_t) - size; - free(start); - } -} -#endif - -/** @} - */