/* * Copyright (c) 2001-2004 Jakub Jermar * Copyright (c) 2022 Jiří Zárevúcky * 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 kernel_sync * @{ */ /** * @file * @brief Wait queue. * * Wait queue is the basic synchronization primitive upon which all * other synchronization primitives build. * * It allows threads to wait for an event in first-come, first-served * fashion. Conditional operation as well as timeouts and interruptions * are supported. * */ #include <assert.h> #include <errno.h> #include <synch/waitq.h> #include <synch/spinlock.h> #include <preemption.h> #include <proc/thread.h> #include <proc/scheduler.h> #include <arch/asm.h> #include <typedefs.h> #include <time/timeout.h> #include <arch.h> #include <context.h> #include <adt/list.h> #include <arch/cycle.h> #include <memw.h> /** Initialize wait queue * * Initialize wait queue. * * @param wq Pointer to wait queue to be initialized. * */ void waitq_initialize(waitq_t *wq) { memsetb(wq, sizeof(*wq), 0); irq_spinlock_initialize(&wq->lock, "wq.lock"); list_initialize(&wq->sleepers); } /** * Initialize wait queue with an initial number of queued wakeups * (or a wakeup debt if negative). */ void waitq_initialize_with_count(waitq_t *wq, int count) { waitq_initialize(wq); wq->wakeup_balance = count; } #define PARAM_NON_BLOCKING(flags, usec) \ (((flags) & SYNCH_FLAGS_NON_BLOCKING) && ((usec) == 0)) errno_t waitq_sleep(waitq_t *wq) { return _waitq_sleep_timeout(wq, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE); } errno_t waitq_sleep_timeout(waitq_t *wq, uint32_t usec) { return _waitq_sleep_timeout(wq, usec, SYNCH_FLAGS_NON_BLOCKING); } /** Sleep until either wakeup, timeout or interruption occurs * * Sleepers are organised in a FIFO fashion in a structure called wait queue. * * Other functions as waitq_sleep() and all the *_timeout() functions are * implemented using this function. * * @param wq Pointer to wait queue. * @param usec Timeout in microseconds. * @param flags Specify mode of the sleep. * * The sleep can be interrupted only if the * SYNCH_FLAGS_INTERRUPTIBLE bit is specified in flags. * * If usec is greater than zero, regardless of the value of the * SYNCH_FLAGS_NON_BLOCKING bit in flags, the call will not return until either * timeout, interruption or wakeup comes. * * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is not set in flags, * the call will not return until wakeup or interruption comes. * * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is set in flags, the * call will immediately return, reporting either success or failure. * * @return ETIMEOUT, meaning that the sleep timed out, or a nonblocking call * returned unsuccessfully. * @return EINTR, meaning that somebody interrupted the sleeping thread. * @return EOK, meaning that none of the above conditions occured, and the * thread was woken up successfuly by `waitq_wake_*()`. * */ errno_t _waitq_sleep_timeout(waitq_t *wq, uint32_t usec, unsigned int flags) { assert((!PREEMPTION_DISABLED) || (PARAM_NON_BLOCKING(flags, usec))); return waitq_sleep_timeout_unsafe(wq, usec, flags, waitq_sleep_prepare(wq)); } /** Prepare to sleep in a waitq. * * This function will return holding the lock of the wait queue * and interrupts disabled. * * @param wq Wait queue. * * @return Interrupt level as it existed on entry to this function. * */ wait_guard_t waitq_sleep_prepare(waitq_t *wq) { ipl_t ipl = interrupts_disable(); irq_spinlock_lock(&wq->lock, false); return (wait_guard_t) { .ipl = ipl, }; } errno_t waitq_sleep_unsafe(waitq_t *wq, wait_guard_t guard) { return waitq_sleep_timeout_unsafe(wq, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE, guard); } /** Internal implementation of waitq_sleep_timeout(). * * This function implements logic of sleeping in a wait queue. * This call must be preceded by a call to waitq_sleep_prepare(). * * @param wq See waitq_sleep_timeout(). * @param usec See waitq_sleep_timeout(). * @param flags See waitq_sleep_timeout(). * * @param[out] blocked See waitq_sleep_timeout(). * * @return See waitq_sleep_timeout(). * */ errno_t waitq_sleep_timeout_unsafe(waitq_t *wq, uint32_t usec, unsigned int flags, wait_guard_t guard) { errno_t rc; /* * If true, and this thread's sleep returns without a wakeup * (timed out or interrupted), waitq ignores the next wakeup. * This is necessary for futex to be able to handle those conditions. */ bool sleep_composable = (flags & SYNCH_FLAGS_FUTEX); bool interruptible = (flags & SYNCH_FLAGS_INTERRUPTIBLE); if (wq->closed) { rc = EOK; goto exit; } /* Checks whether to go to sleep at all */ if (wq->wakeup_balance > 0) { wq->wakeup_balance--; rc = EOK; goto exit; } if (PARAM_NON_BLOCKING(flags, usec)) { /* Return immediately instead of going to sleep */ rc = ETIMEOUT; goto exit; } /* Just for debugging output. */ atomic_store_explicit(&THREAD->sleep_queue, wq, memory_order_relaxed); /* * This thread_t field is synchronized exclusively via * waitq lock of the waitq currently listing it. */ list_append(&THREAD->wq_link, &wq->sleepers); /* Needs to be run when interrupts are still disabled. */ deadline_t deadline = usec > 0 ? timeout_deadline_in_usec(usec) : DEADLINE_NEVER; while (true) { bool terminating = (thread_wait_start() == THREAD_TERMINATING); if (terminating && interruptible) { rc = EINTR; goto exit; } irq_spinlock_unlock(&wq->lock, false); bool timed_out = (thread_wait_finish(deadline) == THREAD_WAIT_TIMEOUT); /* * We always need to re-lock the WQ, since concurrently running * waitq_wakeup() may still not have exitted. * If we didn't always do this, we'd risk waitq_wakeup() that woke us * up still running on another CPU even after this function returns, * and that would be an issue if the waitq is allocated locally to * wait for a one-off asynchronous event. We'd need more external * synchronization in that case, and that would be a pain. * * On the plus side, always regaining a lock simplifies cleanup. */ irq_spinlock_lock(&wq->lock, false); if (!link_in_use(&THREAD->wq_link)) { /* * We were woken up by the desired event. Return success, * regardless of any concurrent timeout or interruption. */ rc = EOK; goto exit; } if (timed_out) { rc = ETIMEOUT; goto exit; } /* Interrupted for some other reason. */ } exit: if (THREAD) list_remove(&THREAD->wq_link); if (rc != EOK && sleep_composable) wq->wakeup_balance--; if (THREAD) atomic_store_explicit(&THREAD->sleep_queue, NULL, memory_order_relaxed); irq_spinlock_unlock(&wq->lock, false); interrupts_restore(guard.ipl); return rc; } static void _wake_one(waitq_t *wq) { /* Pop one thread from the queue and wake it up. */ thread_t *thread = list_get_instance(list_first(&wq->sleepers), thread_t, wq_link); list_remove(&thread->wq_link); thread_wakeup(thread); } /** * Meant for implementing condvar signal. * Always wakes one thread if there are any sleeping, * has no effect if no threads are waiting for wakeup. */ void waitq_signal(waitq_t *wq) { irq_spinlock_lock(&wq->lock, true); if (!list_empty(&wq->sleepers)) _wake_one(wq); irq_spinlock_unlock(&wq->lock, true); } /** * Wakes up one thread sleeping on this waitq. * If there are no threads waiting, saves the wakeup so that the next sleep * returns immediately. If a previous failure in sleep created a wakeup debt * (see SYNCH_FLAGS_FUTEX) this debt is annulled and no thread is woken up. */ void waitq_wake_one(waitq_t *wq) { irq_spinlock_lock(&wq->lock, true); if (!wq->closed) { if (wq->wakeup_balance < 0 || list_empty(&wq->sleepers)) wq->wakeup_balance++; else _wake_one(wq); } irq_spinlock_unlock(&wq->lock, true); } static void _wake_all(waitq_t *wq) { while (!list_empty(&wq->sleepers)) _wake_one(wq); } /** * Wakes up all threads currently waiting on this waitq * and makes all future sleeps return instantly. */ void waitq_close(waitq_t *wq) { irq_spinlock_lock(&wq->lock, true); wq->wakeup_balance = 0; wq->closed = true; _wake_all(wq); irq_spinlock_unlock(&wq->lock, true); } /** * Wakes up all threads currently waiting on this waitq */ void waitq_wake_all(waitq_t *wq) { irq_spinlock_lock(&wq->lock, true); wq->wakeup_balance = 0; _wake_all(wq); irq_spinlock_unlock(&wq->lock, true); } /** @} */