blob: c0ae2aa774bff16cd68db219c78731eb820f5358 [file] [log] [blame]
// Copyright 2018 The Fuchsia Authors
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file or at
#include <fbl/canary.h>
#include <fbl/intrusive_double_list.h>
#include <fbl/macros.h>
#include <kernel/thread.h>
#include <kernel/thread_lock.h>
#include <kernel/wait.h>
// Owned wait queues are an extension of wait queues which adds the concept of
// ownership for use when priority inheritance semantics are needed.
// An owned wait queue maintains an unmanaged pointer to a Thread in order to
// track who owns it at any point in time. In addition, it contains node state
// which can be used by the owning thread in order to track the wait queues that
// the thread is currently an owner of. This also makes use of unmanaged
// pointer.
// It should be an error for any thread to destruct while it owns an
// OwnedWaitQueue. Likewise, it should be an error for any wait queue to
// destruct while it has an owner. These invariants are enforced in the
// destructor for OwnedWaitQueue and Thread. This enforcement is considered
// to be the reasoning why holding unmanaged pointers is considered to be safe.
class OwnedWaitQueue : public WaitQueue, public fbl::DoublyLinkedListable<OwnedWaitQueue*> {
// A small helper class which can be injected into Wake and Requeue
// operations to allow calling code to get a callback for each thread which
// is either woken, or requeued. This callback serves two purposes...
// 1) It allows the caller to perform some limited filtering operations, and
// to choose which thread (if any) becomes the new owner of the queue.
// See the comments in the |Action| enum member for details.
// 2) It gives code such as |FutexContext| a chance to perform their own
// per-thread bookkeeping as the wait queue code chooses which threads to
// either wake or re-queue.
// Note that during a wake or requeue operation, the threads being
// considered will each be presented to the user provided Hook (if any)
// by the OwnedWaitQueue code before deciding whether or not to actually
// wake or requeue the thread.
class Hook {
// A set of 3 actions which may be taken when considering whether or not
// to wake or requeue a thread. If no user supplied Hook is provided
// for a given operation, the default behavior will be to return
// Action::SelectAndKeepGoing.
enum class Action {
// Do not wake or requeue this thread and stop considering threads.
// Select this thread to be either woken or requeued, then continue
// to consider more threads (if any). Do not assign this thread to
// be the owner.
// Select this thread to be either woken or requeued, assign it to
// to be the owner of the queue, then stop considering more threads.
// It is illegal to wake a thread and assign it as the owner for the
// queue if at least one thread has already been woken.
using Callback = Action (*)(Thread* thrd, void* ctx);
Hook() : cbk_(nullptr) {}
Hook(Callback cbk, void* ctx) : cbk_(cbk), ctx_(ctx) {}
Action operator()(Thread* thrd) const TA_REQ(thread_lock) {
return cbk_ ? cbk_(thrd, ctx_) : Action::SelectAndKeepGoing;
Callback cbk_;
void* ctx_;
static constexpr uint32_t kOwnedMagic = fbl::magic("ownq");
constexpr OwnedWaitQueue() : WaitQueue(kOwnedMagic) {}
// No copy or move is permitted.
// Release ownership of all wait queues currently owned by |t| and update
// bookkeeping as appropriate. This is meant to be called from the thread
// itself and therefor it is assumed that the thread in question is not
// blocked on any other wait queues.
static void DisownAllQueues(Thread* t) TA_REQ(thread_lock);
// const accessor for the owner member.
Thread* owner() const TA_REQ(thread_lock) { return owner_; }
// Debug Assert wrapper which skips the thread analysis checks just to
// assert that a specific queue is unowned. Used by FutexContext
void AssertNotOwned() const TA_NO_THREAD_SAFETY_ANALYSIS { DEBUG_ASSERT(owner_ == nullptr); }
// Assign ownership of this wait queue to |new_owner|, or explicitly release
// ownership if |new_owner| is nullptr.
// Note, if the new owner exists, but is dead or dying, it will not be
// permitted to become the new owner of the wait_queue. Any existing owner
// will be replaced with no owner in this situation.
void AssignOwner(Thread* new_owner) TA_REQ(thread_lock, preempt_disabled_token) {
DEBUG_ASSERT(magic() == kOwnedMagic);
if (new_owner != owner()) {
UpdateBookkeeping(new_owner, BlockedPriority());
// Block the current thread on this wait queue, and re-assign ownership to
// the specified thread (or remove ownership if new_owner is null);
// Note, if the new owner exists, but is dead or dying, it will not be
// permitted to become the new owner of the wait_queue. Any existing owner
// will be replaced with no owner in this situation.
zx_status_t BlockAndAssignOwner(const Deadline& deadline, Thread* new_owner,
ResourceOwnership resource_ownership, Interruptible interruptible)
TA_REQ(thread_lock, preempt_disabled_token);
// Wake the up to specified number of threads from the wait queue and then
// handle the ownership bookkeeping based on what the Hook told us to do.
// See |Hook::Action| for details.
void WakeThreads(uint32_t wake_count, Hook on_thread_wake_hook = {})
TA_REQ(thread_lock, preempt_disabled_token);
// A specialization of WakeThreads which will...
// 1) Wake the number of threads indicated by |wake_count|
// 2) Move the number of threads indicated by |requeue_count| to the |requeue_target|.
// 3) Update ownership bookkeeping as indicated by |owner_action| and |requeue_owner|.
// This method is used by futexes in order to implement futex_requeue. It
// is wrapped up into a specialized form instead of broken into individual
// parts in order to minimize any thrash in re-computing effective
// priorities for PI purposes. We don't want to re-evaluate ownership or PI
// pressure until after all of the changes to wait queue have taken place.
// |requeue_target| *must* be non-null. If there is no |requeue_target|,
// use WakeThreads instead.
// Note, if the |requeue_owner| exists, but is dead or dying, it will not be
// permitted to become the new owner of the |requeue_target|. Any existing
// owner will be replaced with no owner in this situation.
void WakeAndRequeue(uint32_t wake_count, OwnedWaitQueue* requeue_target, uint32_t requeue_count,
Thread* requeue_owner, Hook on_thread_wake_hook = {},
Hook on_thread_requeue_hook = {}) TA_REQ(thread_lock, preempt_disabled_token);
// Give permission to the WaitQueue thunk to call the
// WaitersPriorityChanged method (below).
friend void WaitQueue::UpdatePriority(int old_prio);
// Called whenever the pressure of a wait queue currently owned by |t| has
// just changed. Propagates priority inheritance side effects.
// It is an error to call this function if |old_prio| == |new_prio|. Be
// sure to check inline before calling.
static void QueuePressureChanged(Thread* t, int old_prio, int new_prio)
TA_REQ(thread_lock, preempt_disabled_token);
// A hook called by the WaitQueue level when the maximum priority across all
// current waiters has changed.
void WaitersPriorityChanged(int old_prio) TA_REQ(thread_lock, preempt_disabled_token);
// Updates ownership bookkeeping and deals with priority inheritance side
// effects. Called by internal code, typically after changes to the
// contents of the queue have been made which may have an effect of the
// maximum priority of the set of waiters.
// |new_owner|
// A pointer to the thread which should be the owner of this wait queue,
// or nullptr if this queue should have no owner.
// |old_prio|
// The priority of this wait queue as recorded by the caller before
// they started to make changes to the queue's contents.
void UpdateBookkeeping(Thread* new_owner, int old_prio)
TA_REQ(thread_lock, preempt_disabled_token);
// Wake the specified number of threads from the wait queue, and return the
// new owner (first thread woken) via the |out_new_owner| out param, or
// nullptr if there should be no new owner. This code is shared by Wake as
// well as WakeAndRequeue. Doing so allows us to preserve common code, and
// to defer the PI pressure recalculations until the point at which all of
// the queue manipulations have taken place.
void WakeThreadsInternal(uint32_t wake_count, Thread** out_new_owner, zx_time_t now,
Hook on_thread_wake_hook) TA_REQ(thread_lock, preempt_disabled_token);
Thread* owner_ TA_GUARDED(thread_lock) = nullptr;