source: mainline/kernel/generic/src/synch/waitq.c

/*
 * 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)
{
        *wq = WAITQ_INITIALIZER(*wq);
}

/**
 * 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)
{
        *wq = WAITQ_INITIALIZER_WITH_COUNT(*wq, 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);
}

/** @}
 */