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

#ifndef ZIRCON_KERNEL_INCLUDE_KERNEL_OWNED_WAIT_QUEUE_H_
#define ZIRCON_KERNEL_INCLUDE_KERNEL_OWNED_WAIT_QUEUE_H_

#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>

namespace internal {

// fwd decl
// we don't want to drag all of wait_queue_internal.h into this header file, but
// we need to be friends with this internal function, so we just fwd decl it
// here instead..
bool wait_queue_waiters_priority_changed(WaitQueue* wq, int old_prio) TA_REQ(thread_lock);

}  // namespace internal

// 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*> {
 public:
  // 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 {
   public:
    // A set of 4 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, do not declare it to be the
      // owner of anything.  Simply move on to the next thread (if
      // possible).
      Skip,

      // Do not wake or requeue this thread and stop considering threads.
      Stop,

      // 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.
      SelectAndKeepGoing,

      // Select this thread to be either woken or requeued, then stop
      // considering threads.  Do not assign this thread to be the owner.
      SelectAndStop,

      // 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.
      SelectAndAssignOwner,
    };

    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;
    }

   private:
    Callback cbk_;
    void* ctx_;
  };

  static constexpr uint32_t kOwnedMagic = fbl::magic("ownq");
  constexpr OwnedWaitQueue() : WaitQueue(kOwnedMagic) {}
  ~OwnedWaitQueue();

  // No copy or move is permitted.
  DISALLOW_COPY_ASSIGN_AND_MOVE(OwnedWaitQueue);

  // 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.
  //
  // Returns true if a local reschedule is required, or false otherwise.
  bool AssignOwner(Thread* new_owner) TA_REQ(thread_lock) __WARN_UNUSED_RESULT {
    DEBUG_ASSERT(magic_ == kOwnedMagic);

    // If the new owner is the same as the old owner, then we have nothing
    // special to do here.  Just short-circuit.
    if (new_owner == owner()) {
      return false;
    }

    return 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) TA_REQ(thread_lock);

  // 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.
  //
  // Returns true if a local reschedule is required, or false otherwise.
  // Appropriate IPIs will already have been sent.
  bool WakeThreads(uint32_t wake_count, Hook on_thread_wake_hook = {})
      TA_REQ(thread_lock) __WARN_UNUSED_RESULT;

  // 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.
  //
  // Returns true if a local reschedule is required, or false otherwise.
  bool 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) __WARN_UNUSED_RESULT;

 private:
  // Give permission to the wait_queue_t thunk to call the
  // WaitersPriorityChanged method (below).
  friend bool internal::wait_queue_waiters_priority_changed(WaitQueue* wq, int old_prio);

  // A internal helper function which enumerates the wait_queue_t's
  // queue-of-queues structure in a fashion which allows us to remove the
  // threads in question as they are presented to our injected function for
  // consideration.
  //
  // Callable should be a lambda which takes a Thread* for consideration and
  // returns a bool.  If it returns true, iteration continues, otherwise it
  // immediately stops.
  template <typename Callable>
  void ForeachThread(const Callable& visit_thread) TA_REQ(thread_lock) {
    auto consider_queue = [&visit_thread](Thread* queue_head) TA_REQ(thread_lock) -> bool {
      // So, this is a bit tricky.  We need to visit each node in a
      // wait_queue priority level in a way which permits our visit_thread
      // function to remove the thread that we are visiting.
      //
      // Each priority level starts with a queue head which has a list of
      // more threads which exist at that priority level, but the queue
      // head itself is not a member of this list, so some special care
      // must be taken.
      //
      // Start with the queue_head and look up the next thread (if any) at
      // the priority level.  Visit the thread, and if (after visiting the
      // thread), the next thread has become the new queue_head, update
      // queue_head and keep going.
      //
      // If we advance past the queue head, but still have threads to
      // consider, switch to a more standard enumeration of the queue
      // attached to the queue_head.  We know at this point in time that
      // the queue_head can no longer change out from under us.
      //
      DEBUG_ASSERT(queue_head != nullptr);
      Thread* next;

      while (true) {
        next = list_peek_head_type(&queue_head->wait_queue_state_.queue_node_, Thread,
                                   wait_queue_state_.queue_node_);

        if (!visit_thread(queue_head)) {
          return false;
        }

        // Have we run out of things to visit?
        if (!next) {
          return true;
        }

        // If next is not the new queue head, stop.
        if (!list_in_list(&next->wait_queue_state_.wait_queue_heads_node_)) {
          break;
        }

        // Next is the new queue head.  Update and keep going.
        queue_head = next;
      }

      // If we made it this far, then we must still have a valid next.
      DEBUG_ASSERT(next);
      do {
        Thread* t = next;
        next = list_next_type(&queue_head->wait_queue_state_.queue_node_,
                              &t->wait_queue_state_.queue_node_, Thread,
                              wait_queue_state_.queue_node_);

        if (!visit_thread(t)) {
          return false;
        }
      } while (next != nullptr);

      return true;
    };

    Thread* last_queue_head = nullptr;
    Thread* queue_head;

    list_for_every_entry (&this->collection_.heads_, queue_head, Thread,
                          wait_queue_state_.wait_queue_heads_node_) {
      if ((last_queue_head != nullptr) && !consider_queue(last_queue_head)) {
        return;
      }
      last_queue_head = queue_head;
    }

    if (last_queue_head != nullptr) {
      consider_queue(last_queue_head);
    }
  }

  // Called whenever the pressure of a wait queue currently owned by |t| has
  // just changed.  Propagates priority inheritance side effects, but do not
  // send any IPIs.  Simply update the accum_cpu_mask to indicate which CPUs
  // were affected by the change.
  //
  // It is an error to call this function if |old_prio| == |new_prio|.  Be
  // sure to check inline before calling.
  //
  // Returns true if a local reschedule is required, or false otherwise.
  static bool QueuePressureChanged(Thread* t, int old_prio, int new_prio,
                                   cpu_mask_t* accum_cpu_mask) TA_REQ(thread_lock);

  // A hook called by the WaitQueue level when the maximum priority across all
  // current waiters has changed.
  //
  // Returns true if a local reschedule is required, or false otherwise.
  bool WaitersPriorityChanged(int old_prio) TA_REQ(thread_lock) __WARN_UNUSED_RESULT;

  // 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.
  //
  // |accum_cpu_mask|
  //   An optional pointer to a cpu_mask_t.  When non-null, UpdateBookkeeping
  //   will accumulate into this mask the CPUs which have been affected by the
  //   PI side effects of updating this bookkeeping.  When nullptr,
  //   UpdateBookkeeping will automatically update kernel counters and send
  //   IPIs to processors which have been affected by the PI side effects.
  //
  // Returns true if a local reschedule is required, or false otherwise.
  bool UpdateBookkeeping(Thread* new_owner, int old_prio, cpu_mask_t* out_accum_cpu_mask = nullptr)
      TA_REQ(thread_lock) __WARN_UNUSED_RESULT;

  // 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.
  //
  // Returns true if a local reschedule is required, or false otherwise.
  bool WakeThreadsInternal(uint32_t wake_count, Thread** out_new_owner, Hook on_thread_wake_hook)
      TA_REQ(thread_lock) __WARN_UNUSED_RESULT;

  Thread* owner_ TA_GUARDED(thread_lock) = nullptr;
};

#endif  // ZIRCON_KERNEL_INCLUDE_KERNEL_OWNED_WAIT_QUEUE_H_