zircon/kernel/object/include/object/futex_context.h - fuchsia - Git at Google

 // Copyright 2016 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
 // https://opensource.org/licenses/MIT

 #ifndef ZIRCON_KERNEL_OBJECT_INCLUDE_OBJECT_FUTEX_CONTEXT_H_
 #define ZIRCON_KERNEL_OBJECT_INCLUDE_OBJECT_FUTEX_CONTEXT_H_

 #include <lib/user_copy/user_ptr.h>
 #include <zircon/types.h>

 #include <fbl/intrusive_double_list.h>
 #include <fbl/intrusive_hash_table.h>
 #include <fbl/ref_ptr.h>
 #include <kernel/lockdep.h>
 #include <kernel/mutex.h>
 #include <kernel/owned_wait_queue.h>
 #include <kernel/thread_lock.h>
 #include <ktl/move.h>
 #include <ktl/unique_ptr.h>

 class ThreadDispatcher;

 // FutexContex
 //
 // A FutexContext is the object which manages the state of all of the active
 // futexes for a user-mode process.  Each ProcessDispatcher in the system will
 // have a single FutexContext contained within it, and the objects should exist
 // no-where else in the system.
 //
 // FutexContexts manage a pool of FutexContext::FutexStates which are
 // contributed by threads created within the process.  This pool guarantees that
 // threads are guaranteed to be able to allocate a FutexState object in O(1)
 // time whenever they perform a FutexWait operation, as a Futex is only "active"
 // when it has any waiters.  See (Grow|Shrink)FutexStatePool comments as well as
 // the FutexState's notes (below) for more details.
 //
 // The remaining methods in the public interface implement the 3 primary futex
 // syscall operations (Wait, Wake, and Requeue) as well as the one
 // test/diagnostic operation (GetOwner).  See the zircon syscall documentation
 // for further details.
 //
 class FutexContext {
  public:
   // Owner action is an enum used to signal what to do when threads are woken
   // from a futex.  The defined behaviors are as follows.
   //
   // RELEASE
   // Remove any owner regardless of how many threads are woken (including zero
   // threads)
   //
   // ASSIGN_WOKEN
   // Only permitted when wake_count is exactly 1.  Assign ownership to the
   // thread who was woken if there was a thread to wake, and there are still
   // threads left in the futex after waking.  Otherwise, set the futex queue
   // owner to nothing.
   //
   enum class OwnerAction {
     RELEASE,
     ASSIGN_WOKEN,
   };

   FutexContext();
   ~FutexContext();

   // Called as ThreadDispatchers are created and destroyed in order to ensure
   // that there are always two FutexStates for each ThreadDispatcher in a
   // process.
   //
   // Why two and not one?  Because of the FutexRequeue operation.  Without
   // requeue, we would only need one, since a futex with waiters requires one
   // futex state, and there can be at most N futexes with waiters, where N is
   // the number of threads in a process.
   //
   // During FutexRequeue, however, a thread needs to grab a hold of two futex
   // contexts at the same time.  In addition, the thread performing this
   // operation is no longer holding a process wide futex context lock.  Instead,
   // it simply locks in order to activate the FutexStates and then unlocks.
   // Another thread can attempt a requeue in parallel, or it could exit in
   // parallel.  If only one FutexState were added for each thread, it would be
   // possible to run out of FutexStates if these operations were happening in
   // parallel.
   //
   zx_status_t GrowFutexStatePool();
   void ShrinkFutexStatePool();

   // FutexWait first verifies that the integer pointed to by |value_ptr| still equals
   // |current_value|. If the test fails, FutexWait returns BAD_STATE.  Otherwise it will block the
   // current thread until the |deadline| passes, or until the thread is woken by a FutexWake or
   // FutexRequeue operation on the same |value_ptr| futex.
   //
   // Note that this method and FutexRequeue both take a user mode handle instead of having the
   // syscall dispatch layer resolve the handle into a thread before proceeding.  This is because
   // we need to perform the current_value == *value_ptr check before attempting to validate the
   // thread handle, and this check needs to happen inside of the futex context lock.  To do
   // otherwise leaves the potential to hit a race condition where we end up appearing to violate
   // the "bad handle" policy when actually we didn't.  See fxbug.dev/34382 for details.
   zx_status_t FutexWait(user_in_ptr<const zx_futex_t> value_ptr, zx_futex_t current_value,
                         zx_handle_t new_futex_owner, const Deadline& deadline);

   // FutexWake will wake up to |wake_count| number of threads blocked on the |value_ptr| futex.
   //
   // If owner_action is set to RELEASE, then the futex's owner will be set to nullptr in the
   // process.  If the owner_action is set to ASSIGN_WOKEN, then the wake_count *must* be 1, and
   // the futex's owner will be set to the thread which was woken during the operation, or nullptr
   // if no thread was woken.
   zx_status_t FutexWake(user_in_ptr<const zx_futex_t> value_ptr, uint32_t wake_count,
                         OwnerAction owner_action);

   // FutexRequeue first verifies that the integer pointed to by |wake_ptr| still equals
   // |current_value|. If the test fails, FutexRequeue returns BAD_STATE.  Otherwise it will wake
   // up to |wake_count| number of threads blocked on the |wake_ptr| futex.  If any other threads
   // remain blocked on on the |wake_ptr| futex, up to |requeue_count| of them will then be
   // requeued to the tail of the list of threads blocked on the |requeue_ptr| futex.
   //
   // If owner_action is set to RELEASE, then the futex's owner will be set to nullptr in the
   // process.  If the owner_action is set to ASSIGN_WOKEN, then the wake_count *must* be 1, and
   // the futex's owner will be set to the thread which was woken during the operation, or nullptr
   // if no thread was woken.
   zx_status_t FutexRequeue(user_in_ptr<const zx_futex_t> wake_ptr, uint32_t wake_count,
                            zx_futex_t current_value, OwnerAction owner_action,
                            user_in_ptr<const zx_futex_t> requeue_ptr, uint32_t requeue_count,
                            zx_handle_t new_requeue_owner_handle);

   // Get the KOID of the current owner of the specified futex, if any, or ZX_KOID_INVALID if there
   // is no known owner.
   zx_status_t FutexGetOwner(user_in_ptr<const zx_futex_t> value_ptr, user_out_ptr<zx_koid_t> koid);

  private:
   template <typename GuardType>
   zx_status_t FutexWaitInternal(user_in_ptr<const zx_futex_t> value_ptr, zx_futex_t current_value,
                                 ThreadDispatcher* futex_owner_thread, Thread* new_owner,
                                 GuardType&& adopt_new_owner_guard, zx_status_t validator_status,
                                 const Deadline& deadline);

   template <typename GuardType>
   zx_status_t FutexRequeueInternal(user_in_ptr<const zx_futex_t> wake_ptr, uint32_t wake_count,
                                    zx_futex_t current_value, OwnerAction owner_action,
                                    user_in_ptr<const zx_futex_t> requeue_ptr,
                                    uint32_t requeue_count, ThreadDispatcher* requeue_owner_thread,
                                    Thread* new_requeue_owner, GuardType&& adopt_new_owner_guard,
                                    zx_status_t validator_status);

   // Notes about FutexState lifecycle.
   // aka. Why is this safe?
   //
   // FutexState objects are used to track the state of any futex which currently
   // has waiters.  Currently, each thread in a process allocates two FutexStates
   // and contributes them to its process' futex context's free pool.  When the
   // thread exits, it take two FutexStates out of the free pool and lets them
   // expire.
   //
   // There is a master spin lock for each process which protects the sets of
   // active and free FutexStates.  Any time a thread needs to work with futex
   // ID X, it must first obtain the process-wide pool lock and either find the
   // FutexState in the active set with that ID, or activate one from the free
   // list.  After this, the process wide pool lock is immediately released.
   //
   // In order to keep this FutexState from disappearing out from under
   // the thread during its Wait/Wake/Requeue operation, a "pending operation"
   // ref count is increased in the FutexState object.  FutexStates are returned
   // to the free pool _only_ when the pending operation count reaches zero.
   //
   // FutexState objects are managed using ktl::unique_ptr.  At all times, a
   // FutexState will be in one of three states.
   //
   // 1) A member of a FutexContext's active_futexes_ hashtable.  Futexes in this state are
   //    currently involved in at least one futex operation.  Their futex ID will
   //    be non-zero as will their pending operation count..
   // 2) A member of a FutexContext's free_futexes_ list.  These futexes are
   //    not currently in use, but are available to be allocated and used.
   //    Their futex ID and pending operation count will be zero.
   // 3) A member of neither.  These futexes have been created, but not added
   //    to the pool yet, or removed from the free list by a thread which is
   //    exiting.  Their futex ID and pending operation count will be zero.
   //
   class FutexState : public fbl::DoublyLinkedListable<ktl::unique_ptr<FutexState>> {
    public:
     // PendingOpRef is a simple RAII helper meant to help management of the
     // pending operation count ref-counting in a FutexState object.  All of the
     // ways to fetch a FutexState from the free/active sets will return a
     // PendingOpRef to represent the borrow from the pool instead of a raw
     // FutexState pointer.  By default, these object will release a pending
     // operation reference when they go out of scope.  They do this under the
     // protection of the outer FutexContext's pool_lock_, returning the
     // FutexState to the FutexContext's free pool when the pending operation
     // count reaches zero.
     //
     // There are a few special extensions to the PendingOpRef added in order to
     // support some optimizations in the futex code paths.
     //
     // :: CancelRef ::
     // When a thread is about to block on a futex, it will have a PendingOpRef
     // in scope which is holding a pending operation reference to the
     // FutexState.  The thread which is about to block needs to keep that
     // reference on the FutexState as it sleeps, but it should never make an
     // attempt to remove the reference itself when it wakes up again.  There are
     // two reasons for this but the most important one is that, because of the
     // FutexRequeue operation, it may block on Futex A, but get moved over to
     // Futex B while blocking.  By the time it wakes up again, Futex A's
     // FutexState may no longer exist.
     //
     // When a thread has passed all of its checks and it is about to block, it
     // has entered the thread lock, and it uses CancelRef in order to cause its
     // PendingOpRef object to forget about the reference it is holding as it
     // blocks.
     //
     // :: SetExtraRefs ::
     // When a thread calls FutexWake, it will eventually enter the thread lock
     // in order to manipulate the targeted FutexState's wait queue.  For every
     // thread that it successfully wakes up from the wait queue, the wakeup
     // thread assumes responsibility for the woken thread's pending operation
     // reference.  This way, a thread which is successfully woken from a
     // FutexWake operation does not need to acquire any locks on its way out.
     // The thread which woke it up will release its pending operation reference
     // for it.  In order to account for these extra references, the waking
     // thread may call "SetExtraRefs" to account for the references that it took
     // responsibility for during the wake operation.
     //
     // Likewise, SetExtraRefs gets used on the slow path of a thread unblocking
     // from FutexWait.  In the case that a thread unblocks from FutexWait with
     // an error (timeout, thread killed, etc...), it will first wake up and find
     // it's FutexState using its blocking_futex_id_ member.  This may not be the
     // same futex that it originally blocked on.  Once the thread has found the
     // FutexState, it will be holding one pending operation reference as a
     // result of the find operation.  It needs to add another to account for the
     // pending operation reference it placed on the state when it originally
     // went to sleep.  It uses SetExtraRefs to accomplish this.
     //
     // :: TakeRefs ::
     // Finally, during a requeue operation, we are moving threads which are
     // currently blocked on futex A over to futex B.  As we do this, we need to
     // make sure to move their pending operation references at the same time.
     // TakeRefs is the method which allows us to do this.
     class PendingOpRef {
      public:
       PendingOpRef(FutexContext* ctx, FutexState* state) : ctx_(ctx), state_(state) {
         DEBUG_ASSERT(ctx_ != nullptr);
       }
       ~PendingOpRef() { Release(); }

       // RValue construction.
       PendingOpRef(PendingOpRef&& other) noexcept
           : ctx_(other.ctx_), state_(other.state_), extra_refs_(other.extra_refs_) {
         other.state_ = nullptr;
       }

       // No move assignment, and no copy of any form.  Also, no default
       // construction (although, this should be guaranteed by the lack of
       // inline-initializer for the const |ctx_| member.
       PendingOpRef() = delete;
       PendingOpRef(const PendingOpRef&) = delete;
       PendingOpRef& operator=(const PendingOpRef&) = delete;
       PendingOpRef& operator=(PendingOpRef&& other) = delete;

       void SetExtraRefs(uint32_t extra_refs) {
         DEBUG_ASSERT((extra_refs_ == 0) && (state_ != nullptr));
         extra_refs_ = extra_refs;
       }

       void TakeRefs(PendingOpRef* other, uint32_t count) {
         Guard<SpinLock, IrqSave> pool_lock_guard{&ctx_->pool_lock_};
         DEBUG_ASSERT(state_ != nullptr);
         DEBUG_ASSERT(other->state_ != nullptr);
         DEBUG_ASSERT(state_->pending_operation_count_ > 0);
         DEBUG_ASSERT(other->state_->pending_operation_count_ > count);

         state_->pending_operation_count_ += count;
         other->state_->pending_operation_count_ -= count;
       }

       void CancelRef() {
         DEBUG_ASSERT(state_ != nullptr);
         state_ = nullptr;
       }

       // Allow comparison against null, and dereferencing of the underlying state_ pointer.
       bool operator!=(nullptr_t) const { return (state_ != nullptr); }
       bool operator==(nullptr_t) const { return (state_ == nullptr); }
       const FutexState* operator->() const { return state_; }
       FutexState* operator->() { return state_; }

      private:
       void Release() {
         if (state_ != nullptr) {
           Guard<SpinLock, IrqSave> pool_lock_guard{&ctx_->pool_lock_};
           uint32_t release_count = 1 + extra_refs_;

           DEBUG_ASSERT(state_ != nullptr);
           DEBUG_ASSERT(state_->id() != 0);
           DEBUG_ASSERT(state_->pending_operation_count_ >= release_count);

           state_->pending_operation_count_ -= release_count;
           if (state_->pending_operation_count_ == 0) {
             ctx_->free_futexes_.push_front(ctx_->active_futexes_.erase(*state_));
             state_->id_ = 0;
             state_->waiters_.AssertNotOwned();
           }

           state_ = nullptr;
         }
       }

       // A PendingOpRef is a stack-only construct which exists within the scope
       // of a single FutexContext.  There is no reason why this value ever needs
       // to change over the life of the op-ref.
       FutexContext* const ctx_;
       FutexState* state_ = nullptr;
       uint32_t extra_refs_ = 0;
     };

     uintptr_t id() const { return id_; }

     // hashtable support
     uintptr_t GetKey() const { return id(); }
     static size_t GetHash(uintptr_t key) { return (key >> 3); }

    private:
     friend typename ktl::unique_ptr<FutexState>::deleter_type;
     friend class FutexContext;

     FutexState() = default;
     ~FutexState();

     FutexState(const FutexState&) = delete;
     FutexState(FutexState&&) = delete;
     FutexState& operator=(const FutexState&) = delete;
     FutexState& operator=(FutexState&&) = delete;

     uint32_t pending_operation_count() const { return pending_operation_count_; }

     uintptr_t id_ = 0;
     OwnedWaitQueue waiters_;

     // pending operation count is protected by the outer FutexContext pool lock.
     // Sadly, there is no good way to express this using static annotations.
     uint32_t pending_operation_count_ = 0;

     DECLARE_MUTEX(FutexContext) lock_ TA_ACQ_BEFORE(thread_lock);
   };

   // Definition of two small callback hooks used with OwnedWaitQueue::Wake and
   // OwnedWaitQueue::WakeAndRequeue.  These hooks perform two jobs.
   //
   // 1) They allow us to count the number of threads actually woken or requeued
   //    during these operations.  This is needed for proper pending op reference
   //    bookkeeping.
   //
   // 2) Second, they allow us to maintain user-thread blocked_futex_id info as
   //    the OwnedWaitQueue code selects threads to be woken/requeued.
   template <OwnedWaitQueue::Hook::Action action>
   static OwnedWaitQueue::Hook::Action ResetBlockingFutexId(Thread* thrd,
                                                            void* ctx) TA_NO_THREAD_SAFETY_ANALYSIS;
   template <OwnedWaitQueue::Hook::Action action>
   static OwnedWaitQueue::Hook::Action SetBlockingFutexId(Thread* thrd,
                                                          void* ctx) TA_NO_THREAD_SAFETY_ANALYSIS;

   // FutexContexts may not be copied, moved, or allocated on the heap.  They
   // are to exist as singleton members of the ProcessDispatcher class and
   // exist nowhere else in the system.
   FutexContext(const FutexContext&) = delete;
   FutexContext& operator=(const FutexContext&) = delete;
   FutexContext(FutexContext&&) = delete;
   FutexContext& operator=(FutexContext&&) = delete;
   static void* operator new(size_t) = delete;
   static void* operator new[](size_t) = delete;

   // Find the futex state for a given ID in the futex table, increment its
   // pending operation reference count, and return an RAII helper which helps to
   // manage the pending operation references.
   FutexState::PendingOpRef FindActiveFutex(uintptr_t id) TA_EXCL(pool_lock_) {
     Guard<SpinLock, IrqSave> pool_lock_guard{&pool_lock_};
     return FindActiveFutexLocked(id);
   }

   FutexState::PendingOpRef FindActiveFutexLocked(uintptr_t id) TA_REQ(pool_lock_) {
     auto iter = active_futexes_.find(id);

     if (iter.IsValid()) {
       DEBUG_ASSERT(iter->pending_operation_count_ > 0);
       ++(iter->pending_operation_count_);
       return {this, &(*iter)};
     }

     return {this, nullptr};
   }

   // Find a futex with the specified ID, increment its pending_operation_count
   // and return it to the caller.  If the given futex ID is not currently
   // active, grab a free one and activate it.
   FutexState::PendingOpRef ActivateFutex(uintptr_t id) TA_EXCL(pool_lock_) {
     Guard<SpinLock, IrqSave> pool_lock_guard{&pool_lock_};
     return ActivateFutexLocked(id);
   }

   FutexState::PendingOpRef ActivateFutexLocked(uintptr_t id) TA_REQ(pool_lock_) {
     if (auto ret = FindActiveFutexLocked(id); ret != nullptr) {
       return ret;
     }

     ktl::unique_ptr<FutexState> new_state = free_futexes_.pop_front();

     // Sanity checks.
     DEBUG_ASSERT(new_state != nullptr);
     DEBUG_ASSERT(new_state->id() == 0);
     DEBUG_ASSERT(new_state->pending_operation_count_ == 0);
     new_state->waiters_.AssertNotOwned();

     FutexState* ptr = new_state.get();
     ptr->id_ = id;
     ++ptr->pending_operation_count_;
     active_futexes_.insert(ktl::move(new_state));

     return {this, ptr};
   }

   // Protects the free futex pool, and active futex table.  This is an
   // irq-disable spin lock because it should _never_ be held during any blocking
   // operations.  Only when putting FutexStates into and out of the free pool,
   // and when moving Futexes states to and from the active table.
   //
   // There are times where an individual futex state must be held invariant
   // while a decision to return a futex into the free pool needs to be made.  In
   // these cases, the pool lock must be acquired *after* the individual
   // FutexState lock.  Sadly, I don't know a good way to express this with
   // static analysis.
   //
   // Note that lockdep tracking is disabled on this lock because it is acquired
   // while holding the thread lock.
   DECLARE_SPINLOCK(FutexContext, lockdep::LockFlagsTrackingDisabled) pool_lock_;

   // Hash table for FutexStates currently in use (eg; futexes with waiters).
   fbl::HashTable<uintptr_t, ktl::unique_ptr<FutexState>,
                  fbl::DoublyLinkedList<ktl::unique_ptr<FutexState>>>
       active_futexes_ TA_GUARDED(pool_lock_);

   // Free list for all futexes which are currently not in use.
   fbl::DoublyLinkedList<ktl::unique_ptr<FutexState>> free_futexes_ TA_GUARDED(pool_lock_);
 };

 #endif  // ZIRCON_KERNEL_OBJECT_INCLUDE_OBJECT_FUTEX_CONTEXT_H_
	// Copyright 2016 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
	// https://opensource.org/licenses/MIT

	#ifndef ZIRCON_KERNEL_OBJECT_INCLUDE_OBJECT_FUTEX_CONTEXT_H_
	#define ZIRCON_KERNEL_OBJECT_INCLUDE_OBJECT_FUTEX_CONTEXT_H_

	#include <lib/user_copy/user_ptr.h>
	#include <zircon/types.h>

	#include <fbl/intrusive_double_list.h>
	#include <fbl/intrusive_hash_table.h>
	#include <fbl/ref_ptr.h>
	#include <kernel/lockdep.h>
	#include <kernel/mutex.h>
	#include <kernel/owned_wait_queue.h>
	#include <kernel/thread_lock.h>
	#include <ktl/move.h>
	#include <ktl/unique_ptr.h>

	class ThreadDispatcher;

	// FutexContex
	//
	// A FutexContext is the object which manages the state of all of the active
	// futexes for a user-mode process. Each ProcessDispatcher in the system will
	// have a single FutexContext contained within it, and the objects should exist
	// no-where else in the system.
	//
	// FutexContexts manage a pool of FutexContext::FutexStates which are
	// contributed by threads created within the process. This pool guarantees that
	// threads are guaranteed to be able to allocate a FutexState object in O(1)
	// time whenever they perform a FutexWait operation, as a Futex is only "active"
	// when it has any waiters. See (Grow\|Shrink)FutexStatePool comments as well as
	// the FutexState's notes (below) for more details.
	//
	// The remaining methods in the public interface implement the 3 primary futex
	// syscall operations (Wait, Wake, and Requeue) as well as the one
	// test/diagnostic operation (GetOwner). See the zircon syscall documentation
	// for further details.
	//
	class FutexContext {
	public:
	// Owner action is an enum used to signal what to do when threads are woken
	// from a futex. The defined behaviors are as follows.
	//
	// RELEASE
	// Remove any owner regardless of how many threads are woken (including zero
	// threads)
	//
	// ASSIGN_WOKEN
	// Only permitted when wake_count is exactly 1. Assign ownership to the
	// thread who was woken if there was a thread to wake, and there are still
	// threads left in the futex after waking. Otherwise, set the futex queue
	// owner to nothing.
	//
	enum class OwnerAction {
	RELEASE,
	ASSIGN_WOKEN,
	};

	FutexContext();
	~FutexContext();

	// Called as ThreadDispatchers are created and destroyed in order to ensure
	// that there are always two FutexStates for each ThreadDispatcher in a
	// process.
	//
	// Why two and not one? Because of the FutexRequeue operation. Without
	// requeue, we would only need one, since a futex with waiters requires one
	// futex state, and there can be at most N futexes with waiters, where N is
	// the number of threads in a process.
	//
	// During FutexRequeue, however, a thread needs to grab a hold of two futex
	// contexts at the same time. In addition, the thread performing this
	// operation is no longer holding a process wide futex context lock. Instead,
	// it simply locks in order to activate the FutexStates and then unlocks.
	// Another thread can attempt a requeue in parallel, or it could exit in
	// parallel. If only one FutexState were added for each thread, it would be
	// possible to run out of FutexStates if these operations were happening in
	// parallel.
	//
	zx_status_t GrowFutexStatePool();
	void ShrinkFutexStatePool();

	// FutexWait first verifies that the integer pointed to by \|value_ptr\| still equals
	// \|current_value\|. If the test fails, FutexWait returns BAD_STATE. Otherwise it will block the
	// current thread until the \|deadline\| passes, or until the thread is woken by a FutexWake or
	// FutexRequeue operation on the same \|value_ptr\| futex.
	//
	// Note that this method and FutexRequeue both take a user mode handle instead of having the
	// syscall dispatch layer resolve the handle into a thread before proceeding. This is because
	// we need to perform the current_value == *value_ptr check before attempting to validate the
	// thread handle, and this check needs to happen inside of the futex context lock. To do
	// otherwise leaves the potential to hit a race condition where we end up appearing to violate
	// the "bad handle" policy when actually we didn't. See fxbug.dev/34382 for details.
	zx_status_t FutexWait(user_in_ptr<const zx_futex_t> value_ptr, zx_futex_t current_value,
	zx_handle_t new_futex_owner, const Deadline& deadline);

	// FutexWake will wake up to \|wake_count\| number of threads blocked on the \|value_ptr\| futex.
	//
	// If owner_action is set to RELEASE, then the futex's owner will be set to nullptr in the
	// process. If the owner_action is set to ASSIGN_WOKEN, then the wake_count must be 1, and
	// the futex's owner will be set to the thread which was woken during the operation, or nullptr
	// if no thread was woken.
	zx_status_t FutexWake(user_in_ptr<const zx_futex_t> value_ptr, uint32_t wake_count,
	OwnerAction owner_action);

	// FutexRequeue first verifies that the integer pointed to by \|wake_ptr\| still equals
	// \|current_value\|. If the test fails, FutexRequeue returns BAD_STATE. Otherwise it will wake
	// up to \|wake_count\| number of threads blocked on the \|wake_ptr\| futex. If any other threads
	// remain blocked on on the \|wake_ptr\| futex, up to \|requeue_count\| of them will then be
	// requeued to the tail of the list of threads blocked on the \|requeue_ptr\| futex.
	//
	// If owner_action is set to RELEASE, then the futex's owner will be set to nullptr in the
	// process. If the owner_action is set to ASSIGN_WOKEN, then the wake_count must be 1, and
	// the futex's owner will be set to the thread which was woken during the operation, or nullptr
	// if no thread was woken.
	zx_status_t FutexRequeue(user_in_ptr<const zx_futex_t> wake_ptr, uint32_t wake_count,
	zx_futex_t current_value, OwnerAction owner_action,
	user_in_ptr<const zx_futex_t> requeue_ptr, uint32_t requeue_count,
	zx_handle_t new_requeue_owner_handle);

	// Get the KOID of the current owner of the specified futex, if any, or ZX_KOID_INVALID if there
	// is no known owner.
	zx_status_t FutexGetOwner(user_in_ptr<const zx_futex_t> value_ptr, user_out_ptr<zx_koid_t> koid);

	private:
	template <typename GuardType>
	zx_status_t FutexWaitInternal(user_in_ptr<const zx_futex_t> value_ptr, zx_futex_t current_value,
	ThreadDispatcher* futex_owner_thread, Thread* new_owner,
	GuardType&& adopt_new_owner_guard, zx_status_t validator_status,
	const Deadline& deadline);

	template <typename GuardType>
	zx_status_t FutexRequeueInternal(user_in_ptr<const zx_futex_t> wake_ptr, uint32_t wake_count,
	zx_futex_t current_value, OwnerAction owner_action,
	user_in_ptr<const zx_futex_t> requeue_ptr,
	uint32_t requeue_count, ThreadDispatcher* requeue_owner_thread,
	Thread* new_requeue_owner, GuardType&& adopt_new_owner_guard,
	zx_status_t validator_status);

	// Notes about FutexState lifecycle.
	// aka. Why is this safe?
	//
	// FutexState objects are used to track the state of any futex which currently
	// has waiters. Currently, each thread in a process allocates two FutexStates
	// and contributes them to its process' futex context's free pool. When the
	// thread exits, it take two FutexStates out of the free pool and lets them
	// expire.
	//
	// There is a master spin lock for each process which protects the sets of
	// active and free FutexStates. Any time a thread needs to work with futex
	// ID X, it must first obtain the process-wide pool lock and either find the
	// FutexState in the active set with that ID, or activate one from the free
	// list. After this, the process wide pool lock is immediately released.
	//
	// In order to keep this FutexState from disappearing out from under
	// the thread during its Wait/Wake/Requeue operation, a "pending operation"
	// ref count is increased in the FutexState object. FutexStates are returned
	// to the free pool _only_ when the pending operation count reaches zero.
	//
	// FutexState objects are managed using ktl::unique_ptr. At all times, a
	// FutexState will be in one of three states.
	//
	// 1) A member of a FutexContext's active_futexes_ hashtable. Futexes in this state are
	// currently involved in at least one futex operation. Their futex ID will
	// be non-zero as will their pending operation count..
	// 2) A member of a FutexContext's free_futexes_ list. These futexes are
	// not currently in use, but are available to be allocated and used.
	// Their futex ID and pending operation count will be zero.
	// 3) A member of neither. These futexes have been created, but not added
	// to the pool yet, or removed from the free list by a thread which is
	// exiting. Their futex ID and pending operation count will be zero.
	//
	class FutexState : public fbl::DoublyLinkedListable<ktl::unique_ptr<FutexState>> {
	public:
	// PendingOpRef is a simple RAII helper meant to help management of the
	// pending operation count ref-counting in a FutexState object. All of the
	// ways to fetch a FutexState from the free/active sets will return a
	// PendingOpRef to represent the borrow from the pool instead of a raw
	// FutexState pointer. By default, these object will release a pending
	// operation reference when they go out of scope. They do this under the
	// protection of the outer FutexContext's pool_lock_, returning the
	// FutexState to the FutexContext's free pool when the pending operation
	// count reaches zero.
	//
	// There are a few special extensions to the PendingOpRef added in order to
	// support some optimizations in the futex code paths.
	//
	// :: CancelRef ::
	// When a thread is about to block on a futex, it will have a PendingOpRef
	// in scope which is holding a pending operation reference to the
	// FutexState. The thread which is about to block needs to keep that
	// reference on the FutexState as it sleeps, but it should never make an
	// attempt to remove the reference itself when it wakes up again. There are
	// two reasons for this but the most important one is that, because of the
	// FutexRequeue operation, it may block on Futex A, but get moved over to
	// Futex B while blocking. By the time it wakes up again, Futex A's
	// FutexState may no longer exist.
	//
	// When a thread has passed all of its checks and it is about to block, it
	// has entered the thread lock, and it uses CancelRef in order to cause its
	// PendingOpRef object to forget about the reference it is holding as it
	// blocks.
	//
	// :: SetExtraRefs ::
	// When a thread calls FutexWake, it will eventually enter the thread lock
	// in order to manipulate the targeted FutexState's wait queue. For every
	// thread that it successfully wakes up from the wait queue, the wakeup
	// thread assumes responsibility for the woken thread's pending operation
	// reference. This way, a thread which is successfully woken from a
	// FutexWake operation does not need to acquire any locks on its way out.
	// The thread which woke it up will release its pending operation reference
	// for it. In order to account for these extra references, the waking
	// thread may call "SetExtraRefs" to account for the references that it took
	// responsibility for during the wake operation.
	//
	// Likewise, SetExtraRefs gets used on the slow path of a thread unblocking
	// from FutexWait. In the case that a thread unblocks from FutexWait with
	// an error (timeout, thread killed, etc...), it will first wake up and find
	// it's FutexState using its blocking_futex_id_ member. This may not be the
	// same futex that it originally blocked on. Once the thread has found the
	// FutexState, it will be holding one pending operation reference as a
	// result of the find operation. It needs to add another to account for the
	// pending operation reference it placed on the state when it originally
	// went to sleep. It uses SetExtraRefs to accomplish this.
	//
	// :: TakeRefs ::
	// Finally, during a requeue operation, we are moving threads which are
	// currently blocked on futex A over to futex B. As we do this, we need to
	// make sure to move their pending operation references at the same time.
	// TakeRefs is the method which allows us to do this.
	class PendingOpRef {
	public:
	PendingOpRef(FutexContext* ctx, FutexState* state) : ctx_(ctx), state_(state) {
	DEBUG_ASSERT(ctx_ != nullptr);
	}
	~PendingOpRef() { Release(); }

	// RValue construction.
	PendingOpRef(PendingOpRef&& other) noexcept
	: ctx_(other.ctx_), state_(other.state_), extra_refs_(other.extra_refs_) {
	other.state_ = nullptr;
	}

	// No move assignment, and no copy of any form. Also, no default
	// construction (although, this should be guaranteed by the lack of
	// inline-initializer for the const \|ctx_\| member.
	PendingOpRef() = delete;
	PendingOpRef(const PendingOpRef&) = delete;
	PendingOpRef& operator=(const PendingOpRef&) = delete;
	PendingOpRef& operator=(PendingOpRef&& other) = delete;

	void SetExtraRefs(uint32_t extra_refs) {
	DEBUG_ASSERT((extra_refs_ == 0) && (state_ != nullptr));
	extra_refs_ = extra_refs;
	}

	void TakeRefs(PendingOpRef* other, uint32_t count) {
	Guard<SpinLock, IrqSave> pool_lock_guard{&ctx_->pool_lock_};
	DEBUG_ASSERT(state_ != nullptr);
	DEBUG_ASSERT(other->state_ != nullptr);
	DEBUG_ASSERT(state_->pending_operation_count_ > 0);
	DEBUG_ASSERT(other->state_->pending_operation_count_ > count);

	state_->pending_operation_count_ += count;
	other->state_->pending_operation_count_ -= count;
	}

	void CancelRef() {
	DEBUG_ASSERT(state_ != nullptr);
	state_ = nullptr;
	}

	// Allow comparison against null, and dereferencing of the underlying state_ pointer.
	bool operator!=(nullptr_t) const { return (state_ != nullptr); }
	bool operator==(nullptr_t) const { return (state_ == nullptr); }
	const FutexState* operator->() const { return state_; }
	FutexState* operator->() { return state_; }

	private:
	void Release() {
	if (state_ != nullptr) {
	Guard<SpinLock, IrqSave> pool_lock_guard{&ctx_->pool_lock_};
	uint32_t release_count = 1 + extra_refs_;

	DEBUG_ASSERT(state_ != nullptr);
	DEBUG_ASSERT(state_->id() != 0);
	DEBUG_ASSERT(state_->pending_operation_count_ >= release_count);

	state_->pending_operation_count_ -= release_count;
	if (state_->pending_operation_count_ == 0) {
	ctx_->free_futexes_.push_front(ctx_->active_futexes_.erase(*state_));
	state_->id_ = 0;
	state_->waiters_.AssertNotOwned();
	}

	state_ = nullptr;
	}
	}

	// A PendingOpRef is a stack-only construct which exists within the scope
	// of a single FutexContext. There is no reason why this value ever needs
	// to change over the life of the op-ref.
	FutexContext* const ctx_;
	FutexState* state_ = nullptr;
	uint32_t extra_refs_ = 0;
	};

	uintptr_t id() const { return id_; }

	// hashtable support
	uintptr_t GetKey() const { return id(); }
	static size_t GetHash(uintptr_t key) { return (key >> 3); }

	private:
	friend typename ktl::unique_ptr<FutexState>::deleter_type;
	friend class FutexContext;

	FutexState() = default;
	~FutexState();

	FutexState(const FutexState&) = delete;
	FutexState(FutexState&&) = delete;
	FutexState& operator=(const FutexState&) = delete;
	FutexState& operator=(FutexState&&) = delete;

	uint32_t pending_operation_count() const { return pending_operation_count_; }

	uintptr_t id_ = 0;
	OwnedWaitQueue waiters_;

	// pending operation count is protected by the outer FutexContext pool lock.
	// Sadly, there is no good way to express this using static annotations.
	uint32_t pending_operation_count_ = 0;

	DECLARE_MUTEX(FutexContext) lock_ TA_ACQ_BEFORE(thread_lock);
	};

	// Definition of two small callback hooks used with OwnedWaitQueue::Wake and
	// OwnedWaitQueue::WakeAndRequeue. These hooks perform two jobs.
	//
	// 1) They allow us to count the number of threads actually woken or requeued
	// during these operations. This is needed for proper pending op reference
	// bookkeeping.
	//
	// 2) Second, they allow us to maintain user-thread blocked_futex_id info as
	// the OwnedWaitQueue code selects threads to be woken/requeued.
	template <OwnedWaitQueue::Hook::Action action>
	static OwnedWaitQueue::Hook::Action ResetBlockingFutexId(Thread* thrd,
	void* ctx) TA_NO_THREAD_SAFETY_ANALYSIS;
	template <OwnedWaitQueue::Hook::Action action>
	static OwnedWaitQueue::Hook::Action SetBlockingFutexId(Thread* thrd,
	void* ctx) TA_NO_THREAD_SAFETY_ANALYSIS;

	// FutexContexts may not be copied, moved, or allocated on the heap. They
	// are to exist as singleton members of the ProcessDispatcher class and
	// exist nowhere else in the system.
	FutexContext(const FutexContext&) = delete;
	FutexContext& operator=(const FutexContext&) = delete;
	FutexContext(FutexContext&&) = delete;
	FutexContext& operator=(FutexContext&&) = delete;
	static void* operator new(size_t) = delete;
	static void* operator new[](size_t) = delete;

	// Find the futex state for a given ID in the futex table, increment its
	// pending operation reference count, and return an RAII helper which helps to
	// manage the pending operation references.
	FutexState::PendingOpRef FindActiveFutex(uintptr_t id) TA_EXCL(pool_lock_) {
	Guard<SpinLock, IrqSave> pool_lock_guard{&pool_lock_};
	return FindActiveFutexLocked(id);
	}

	FutexState::PendingOpRef FindActiveFutexLocked(uintptr_t id) TA_REQ(pool_lock_) {
	auto iter = active_futexes_.find(id);

	if (iter.IsValid()) {
	DEBUG_ASSERT(iter->pending_operation_count_ > 0);
	++(iter->pending_operation_count_);
	return {this, &(*iter)};
	}

	return {this, nullptr};
	}

	// Find a futex with the specified ID, increment its pending_operation_count
	// and return it to the caller. If the given futex ID is not currently
	// active, grab a free one and activate it.
	FutexState::PendingOpRef ActivateFutex(uintptr_t id) TA_EXCL(pool_lock_) {
	Guard<SpinLock, IrqSave> pool_lock_guard{&pool_lock_};
	return ActivateFutexLocked(id);
	}

	FutexState::PendingOpRef ActivateFutexLocked(uintptr_t id) TA_REQ(pool_lock_) {
	if (auto ret = FindActiveFutexLocked(id); ret != nullptr) {
	return ret;
	}

	ktl::unique_ptr<FutexState> new_state = free_futexes_.pop_front();

	// Sanity checks.
	DEBUG_ASSERT(new_state != nullptr);
	DEBUG_ASSERT(new_state->id() == 0);
	DEBUG_ASSERT(new_state->pending_operation_count_ == 0);
	new_state->waiters_.AssertNotOwned();

	FutexState* ptr = new_state.get();
	ptr->id_ = id;
	++ptr->pending_operation_count_;
	active_futexes_.insert(ktl::move(new_state));

	return {this, ptr};
	}

	// Protects the free futex pool, and active futex table. This is an
	// irq-disable spin lock because it should _never_ be held during any blocking
	// operations. Only when putting FutexStates into and out of the free pool,
	// and when moving Futexes states to and from the active table.
	//
	// There are times where an individual futex state must be held invariant
	// while a decision to return a futex into the free pool needs to be made. In
	// these cases, the pool lock must be acquired after the individual
	// FutexState lock. Sadly, I don't know a good way to express this with
	// static analysis.
	//
	// Note that lockdep tracking is disabled on this lock because it is acquired
	// while holding the thread lock.
	DECLARE_SPINLOCK(FutexContext, lockdep::LockFlagsTrackingDisabled) pool_lock_;

	// Hash table for FutexStates currently in use (eg; futexes with waiters).
	fbl::HashTable<uintptr_t, ktl::unique_ptr<FutexState>,
	fbl::DoublyLinkedList<ktl::unique_ptr<FutexState>>>
	active_futexes_ TA_GUARDED(pool_lock_);

	// Free list for all futexes which are currently not in use.
	fbl::DoublyLinkedList<ktl::unique_ptr<FutexState>> free_futexes_ TA_GUARDED(pool_lock_);
	};

	#endif // ZIRCON_KERNEL_OBJECT_INCLUDE_OBJECT_FUTEX_CONTEXT_H_