// Copyright 2023 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

#include <lib/kconcurrent/chainlock_transaction.h>
#include <lib/unittest/unittest.h>

#include <kernel/auto_preempt_disabler.h>
#include <kernel/event.h>
#include <kernel/owned_wait_queue.h>
#include <kernel/thread.h>
#include <ktl/unique_ptr.h>

static constexpr uint32_t Invalid = ktl::numeric_limits<uint32_t>::max();

struct OwnedWaitQueueTopologyTests {
  class TestQueue;
  class TestThread {
   public:
    constexpr TestThread() = default;
    ~TestThread() { Shutdown(); }

    static SchedDuration DeadlineForNdx(size_t ndx) {
      constexpr SchedDuration kBaseDuration{ZX_USEC(500)};
      constexpr SchedDuration kDurationInc{ZX_USEC(10)};
      return kBaseDuration + (ndx * kDurationInc);
    }

    bool Init(const SchedulerState::BaseProfile* base_profile = nullptr) {
      BEGIN_TEST;

      ASSERT_NULL(thread_);
      thread_ = Thread::Create(
          "owq_test_thread",
          [](void* arg) -> int { return reinterpret_cast<TestThread*>(arg)->Main(); }, this,
          DEFAULT_PRIORITY);
      ASSERT_NONNULL(thread_);
      if (base_profile != nullptr) {
        thread_->SetBaseProfile(*base_profile);
      }
      thread_->Resume();

      END_TEST;
    }

    void Shutdown() {
      exit_now_.store(true);
      if (thread_ != nullptr) {
        int unused_retcode;
        thread_->Kill();
        thread_->Join(&unused_retcode, ZX_TIME_INFINITE);
        thread_ = nullptr;
      }
    }

    bool DoBlock(TestQueue& queue, TestThread* new_owner);
    Thread* thread() { return thread_; }
    const OwnedWaitQueue* target_queue() const { return target_queue_; }
    const OwnedWaitQueue* blocking_queue() const TA_EXCL(chainlock_transaction_token) {
      ASSERT(thread_ != nullptr);
      SingletonChainLockGuardIrqSave guard{
          thread_->get_lock(), CLT_TAG("OwnedWaitQueueTopologyTests::TestThread::blocking_queue")};
      return OwnedWaitQueue::DowncastToOwq(thread_->wait_queue_state().blocking_wait_queue());
    }

   private:
    int Main();

    static inline WaitQueue final_exit_queue_;

    ktl::atomic<bool> exit_now_{false};
    ktl::atomic<bool> do_baao_{false};
    OwnedWaitQueue* target_queue_{nullptr};
    Thread* target_owner_{nullptr};
    Thread* thread_{nullptr};
  };

  class TestQueue {
   public:
    constexpr TestQueue() = default;
    ~TestQueue() = default;

    bool Init() {
      BEGIN_TEST;

      ASSERT_NULL(owq_);
      fbl::AllocChecker ac;
      owq_.reset(new (&ac) OwnedWaitQueue{});
      ASSERT_TRUE(ac.check());

      END_TEST;
    }

    OwnedWaitQueue* owq() { return owq_.get(); }
    Thread* owner() {
      ASSERT(owq_ != nullptr);
      SingletonChainLockGuardIrqSave guard{
          owq_->get_lock(), CLT_TAG("OwnedWaitQueueTopologyTests::TestQueue::owner")};
      return owq_->owner();
    }

   private:
    ktl::unique_ptr<OwnedWaitQueue> owq_;
  };

  struct Action {
    uint32_t t_ndx;       // ndx of the blocking thread.
    uint32_t bq_ndx;      // ndx of the queue which the thread blocks behind
    uint32_t ot_ndx;      // ndx of the thread declared to be the owner.
    bool owner_expected;  // true if we expect the owner to be accepted, false if
                          // we expect the owner to be rejected (and end up with
                          // no owner after the action.
  };

  struct RequeueAction {
    uint32_t wake_count;
    uint32_t requeue_count;
    uint32_t requeue_owner_ndx;
    bool assign_woken;
  };

  template <size_t ThreadCount>
  static void ShutdownThreads(ktl::array<TestThread, ThreadCount>& threads) {
    for (TestThread& t : threads) {
      t.Shutdown();
    }
  }

  template <size_t ThreadCount, size_t QueueCount, size_t ActionCount>
  static bool RunBAAOTest(ktl::array<TestThread, ThreadCount>& threads,
                          ktl::array<TestQueue, QueueCount>& queues,
                          const ktl::array<Action, ActionCount>& actions,
                          bool setup_for_requeue_test = false) {
    BEGIN_TEST;

    // Initialize all of the threads and queues.  We cannot proceed if any of this
    // fails.
    for (size_t i = 0; i < threads.size(); ++i) {
      TestThread& t = threads[i];
      if (!setup_for_requeue_test) {
        ASSERT_TRUE(t.Init());
      } else {
        const SchedDuration deadline = TestThread::DeadlineForNdx(i);
        const SchedDuration capacity = deadline / 2;
        const SchedDeadlineParams params{capacity, deadline};
        const SchedulerState::BaseProfile profile{params};
        ASSERT_TRUE(t.Init(&profile));
      }
    }

    for (TestQueue& q : queues) {
      ASSERT_TRUE(q.Init());
    }

    // Perform each of the actions, blocking a given thread behind a given wait
    // queue and optionally declaring an owner as we do.  Afterwards, verify that
    // each of the threads is blocked behind the queue we expect, and that the
    // owner is who we expect.
    for (const Action& a : actions) {
      // Make sue the action indexes are valid.
      ASSERT_LT(a.t_ndx, threads.size());
      ASSERT_LT(a.bq_ndx, queues.size());

      TestThread& blocking_thread = threads[a.t_ndx];
      TestQueue& target_queue = queues[a.bq_ndx];
      TestThread* new_owner{nullptr};
      if (a.ot_ndx != Invalid) {
        ASSERT_LT(a.ot_ndx, threads.size());
        new_owner = &threads[a.ot_ndx];
      }

      // Then perform the block operation.
      ASSERT_TRUE(blocking_thread.DoBlock(target_queue, new_owner));

      // Now validate everything.
      Thread* expected_owner =
          a.owner_expected && (new_owner != nullptr) ? new_owner->thread() : nullptr;
      EXPECT_EQ(expected_owner, target_queue.owner());
      for (const TestThread& t : threads) {
        EXPECT_EQ(t.target_queue(), t.blocking_queue());
      }
    }

    if (setup_for_requeue_test) {
      // Sleep for longer than the longest relative deadline we assigned to our
      // threads.  This will ensure that none of the currently blocked threads
      // have an active deadline (all of their deadlines will have expired).
      // Since the relative deadlines of the threads were assigned in increasing
      // order relative to their index in the test thread array, this means that
      // when it comes time to choose a thread to wake up from the blocked
      // queue, we should always end up choosing the thread in the queue with
      // the lowest index in the test thread array.
      Thread::Current::SleepRelative(TestThread::DeadlineForNdx(threads.size()).raw_value());
    } else {
      ShutdownThreads(threads);
    }

    END_TEST;
  }

  template <size_t ThreadCount, size_t QueueCount, size_t ActionCount>
  static bool RunRequeueTest(ktl::array<TestThread, ThreadCount>& threads,
                             ktl::array<TestQueue, QueueCount>& queues,
                             const ktl::array<Action, ActionCount>& setup_actions,
                             const RequeueAction& requeue_action,
                             const ktl::array<uint32_t, ThreadCount>& expected_blocking_queues,
                             const ktl::array<uint32_t, QueueCount>& expected_owners) {
    BEGIN_TEST;

    auto NdxToThread = [&](uint32_t ndx) -> Thread* {
      if (ndx == Invalid) {
        return nullptr;
      }
      DEBUG_ASSERT(ndx < threads.size());
      return threads[ndx].thread();
    };

    auto NdxToQueue = [&](uint32_t ndx) -> OwnedWaitQueue* {
      if (ndx == Invalid) {
        return nullptr;
      }
      DEBUG_ASSERT(ndx < queues.size());
      return queues[ndx].owq();
    };

    static_assert(QueueCount >= 2, "Requeue tests must always involve at least two queues");

    // Setup the pre-requeue state.
    ASSERT_TRUE(RunBAAOTest(threads, queues, setup_actions, true));

    // Now perform the requeue action
    Thread* const new_requeue_owner = NdxToThread(requeue_action.requeue_owner_ndx);
    OwnedWaitQueue::IWakeRequeueHook& hooks = OwnedWaitQueue::default_wake_hooks();
    OwnedWaitQueue& src_queue = *queues[0].owq();
    OwnedWaitQueue& dst_queue = *queues[1].owq();
    src_queue.WakeAndRequeue(dst_queue, new_requeue_owner, requeue_action.wake_count,
                             requeue_action.requeue_count, hooks, hooks,
                             requeue_action.assign_woken ? OwnedWaitQueue::WakeOption::AssignOwner
                                                         : OwnedWaitQueue::WakeOption::None);

    // Now verify that all of the threads are blocked (or not) in the proper
    // queues, and that all queues are owned by the expected threads (or no
    // thread).
    for (size_t tndx = 0; tndx < expected_blocking_queues.size(); ++tndx) {
      const uint32_t qndx = expected_blocking_queues[tndx];
      OwnedWaitQueue* const expected_queue = NdxToQueue(qndx);
      EXPECT_EQ(expected_queue, threads[tndx].blocking_queue());
    }

    for (size_t qndx = 0; qndx < expected_owners.size(); ++qndx) {
      const uint32_t tndx = expected_owners[qndx];
      Thread* const expected = NdxToThread(tndx);
      EXPECT_EQ(expected, queues[qndx].owner());
    }

    // Cleanup and we are done.
    ShutdownThreads(threads);
    END_TEST;
  }
};

int OwnedWaitQueueTopologyTests::TestThread::Main() {
  while (!do_baao_.load()) {
    Thread::Current::SleepRelative(ZX_USEC(100));
    if (exit_now_.load()) {
      return -1;
    }
  }

  {
    AnnotatedAutoPreemptDisabler aapd;
    ASSERT(target_queue_ != nullptr);
    target_queue_->BlockAndAssignOwner(Deadline::infinite(), target_owner_,
                                       ResourceOwnership::Normal, Interruptible::Yes);
  }

  if (exit_now_.load()) {
    return -1;
  }

  {
    ChainLockTransactionIrqSave clt{
        CLT_TAG("OwnedWaitQueueTopologyTests::TestThread::Main (final exit block)")};

    Thread* const current_thread = Thread::Current::Get();
    ktl::array locks{&final_exit_queue_.get_lock(), &current_thread->get_lock()};

    while (AcquireChainLockSet(locks) == ChainLock::LockResult::kBackoff) {
      clt.Relax();
    }

    clt.Finalize();
    final_exit_queue_.get_lock().AssertAcquired();
    current_thread->get_lock().AssertAcquired();
    final_exit_queue_.Block(current_thread, Deadline::infinite(), Interruptible::Yes);
    current_thread->get_lock().Release();
  }

  return 0;
}

bool OwnedWaitQueueTopologyTests::TestThread::DoBlock(TestQueue& queue, TestThread* new_owner) {
  BEGIN_TEST;

  ASSERT_FALSE(do_baao_.load());
  ASSERT_NULL(target_queue_);
  ASSERT_NULL(target_owner_);
  ASSERT_NONNULL(queue.owq());
  if (new_owner) {
    ASSERT_NONNULL(new_owner->thread());
    target_owner_ = new_owner->thread();
  }
  target_queue_ = queue.owq();
  do_baao_.store(true);

  while (true) {
    {
      SingletonChainLockGuardIrqSave guard{
          thread_->get_lock(), CLT_TAG("OwnedWaitQueueTopologyTests::TestThread::DoBlock")};
      if (thread_->state() == THREAD_BLOCKED) {
        break;
      }
    }
    Thread::Current::SleepRelative(ZX_USEC(100));
  }

  END_TEST;
}

namespace {

using TestThread = OwnedWaitQueueTopologyTests::TestThread;
using TestQueue = OwnedWaitQueueTopologyTests::TestQueue;
using Action = OwnedWaitQueueTopologyTests::Action;
using RequeueAction = OwnedWaitQueueTopologyTests::RequeueAction;

bool owq_topology_test_simple() {
  BEGIN_TEST;

  // A basic smoke test.  Simply generate
  //
  // +----+     +----+
  // | T0 | --> | Q0 |
  // +----+     +----+
  //

  ktl::array<TestQueue, 1> queues;
  ktl::array<TestThread, 1> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_simple_owner_change() {
  BEGIN_TEST;

  // Change owners, moving from this
  //
  // +----+     +----+     +----+
  // | T0 | --> | Q0 | --> | T2 |
  // +----+     +----+     +----+
  //
  // to this:
  //
  // +----+     +----+     +----+
  // | T0 | --> | Q0 | --> | T3 |
  // +----+  ^  +----+     +----+
  //         |
  // +----+  |  +----+
  // | T1 | -+  | Q0 |
  // +----+     +----+

  ktl::array<TestQueue, 1> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 2, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_deny_self_own() {
  BEGIN_TEST;

  // Try to do this
  //
  //  +----------------------+
  //  |                      |
  //  |  +----+     +----+   |
  //  +->| T0 | --> | Q0 | --+
  //     +----+     +----+
  //
  // Which should be denied, ending up with this.
  //
  //     +----+     +----+
  //     | T0 | --> | Q0 |
  //     +----+     +----+
  //

  ktl::array<TestQueue, 1> queues;
  ktl::array<TestThread, 1> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 0, .owner_expected = false},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_owner_becomes_blocked_no_new_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 |
  //     +----+     +----+     +----+
  //
  // To this, by having T1 block, and declare no new owner.
  //
  //     +----+     +----+
  //     | T0 | --> | Q0 |
  //     +----+  ^  +----+
  //             |
  //     +----+  |
  //     | T1 | -+
  //     +----+
  //

  ktl::array<TestQueue, 1> queues;
  ktl::array<TestThread, 2> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_owner_becomes_blocked_yes_new_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 |
  //     +----+     +----+     +----+
  //
  // To this, by having T1 block, and declare T2 as the new owner.
  //
  //     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T2 |
  //     +----+  ^  +----+     +----+
  //             |
  //     +----+  |
  //     | T1 | -+
  //     +----+
  //
  ktl::array<TestQueue, 1> queues;
  ktl::array<TestThread, 3> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 2, .owner_expected = true},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_owner_becomes_blocked_deny_blocked_new_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 |
  //     +----+     +----+     +----+
  //
  // To this, by having T1 block, and declare T0 as the owner.
  //
  //  +----------------------+
  //  |                      |
  //  |  +----+     +----+   |
  //  +->| T0 | --> | Q0 | --+
  //     +----+  ^  +----+
  //             |
  //     +----+  |
  //     | T1 | -+
  //     +----+
  //
  // Because of the cycle, this should be denied, resulting in this:
  //
  //     +----+     +----+
  //     | T0 | --> | Q0 |
  //     +----+  ^  +----+
  //             |
  //     +----+  |
  //     | T1 | -+
  //     +----+
  //

  ktl::array<TestQueue, 1> queues;
  ktl::array<TestThread, 2> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 0, .owner_expected = false},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_blocked_owners() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 | --> | Q1 |
  //     +----+     +----+     +----+     +----+
  //
  //                           +----+     +----+
  //                           | T2 | --> | Q2 |
  //                           +----+     +----+
  //
  // To this, by having T3 block, and declare T2 as the owner.
  //
  //                           +----+     +----+
  //                           | T1 | --> | Q1 |
  //                           +----+     +----+
  //
  //     +----+     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T2 | --> | Q2 |
  //     +----+  ^  +----+     +----+     +----+
  //             |
  //     +----+  |
  //     | T3 | -+
  //     +----+
  //

  ktl::array<TestQueue, 3> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 1, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 2, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 0, .ot_ndx = 2, .owner_expected = true},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_blocking_thread_downstream_of_owner_no_owner_change() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+     +----+     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 | --> | Q1 | --> | T2 |
  //     +----+     +----+     +----+     +----+     +----+
  //
  //
  // To this, by having T2 block in Q0, declaring T1 to still be the owner.
  //
  //     +----+     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 | --> | Q1 |
  //     +----+  ^  +----+     +----+     +----+
  //             |                          |
  //     +----+  |                          |
  //     | T2 | -+                          |
  //     +----+                             |
  //       ^                                |
  //       |                                |
  //       +--------------------------------+
  //
  // This should fail because of the cycle, and result in this instead.
  //
  //                          +----+     +----+
  //                          | T0 | --> | Q0 |
  //                          +----+  ^  +----+
  //                                  |
  //    +----+     +----+     +----+  |
  //    | T1 | --> | Q1 | --> | T2 | -+
  //    +----+     +----+     +----+
  //

  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 3> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 1, .ot_ndx = 2, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = false},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_blocking_thread_downstream_of_owner_yes_owner_change() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 |
  //     +----+     +----+     +----+
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q1 | --> | T3 |
  //     +----+     +----+     +----+
  //
  // To this, by having T3 block in Q0, declaring T2 to be the new owner.
  //
  //     +----+
  //     | T1 |
  //     +----+
  //
  //     +----+     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T2 | --> | Q1 |
  //     +----+  ^  +----+     +----+     +----+
  //             |                          |
  //     +----+  |                          |
  //     | T3 | -+                          |
  //     +----+                             |
  //       ^                                |
  //       |                                |
  //       +--------------------------------+
  //
  // This should fail because of the cycle, and result in this instead.
  //     +----+
  //     | T1 |
  //     +----+
  //
  //     +----+     +----+
  //     | T0 | --> | Q0 |
  //     +----+  ^  +----+
  //             |
  //     +----+  |
  //     | T3 | -+
  //     +----+
  //
  //     +----+     +----+
  //     | T2 | --> | Q1 |
  //     +----+     +----+
  //

  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 1, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 0, .ot_ndx = 2, .owner_expected = false},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_intersecting_owner_chains() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+     +----+     +----+     +----+     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 | --> | Q1 | --> | T2 | --> | Q2 | --> | T3 |
  //     +----+     +----+     +----+     +----+     +----+  ^  +----+     +----+
  //                                                         |
  //                                                 +----+  |
  //                                                 | T4 | -+
  //                                                 +----+
  //
  // To this, by having T5 block in Q0, declaring T4 to be the new owner.
  //
  //     +----+     +----+     +----+
  //     | T1 | --> | Q1 | --> | T2 | -+
  //     +----+     +----+     +----+  |
  //                                   |
  //     +----+     +----+     +----+  V  +----+     +----+
  //     | T0 | --> | Q0 | --> | T4 | --> | Q2 | --> | T3 |
  //     +----+  ^  +----+     +----+     +----+     +----+
  //             |
  //     +----+  |
  //     | T5 | -+
  //     +----+
  //
  ktl::array<TestQueue, 3> queues;
  ktl::array<TestThread, 6> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 1, .ot_ndx = 2, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 2, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 4, .bq_ndx = 2, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 5, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_intersecting_owner_chains_old_owner_target_of_new_owner_chain() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //                           +----+     +----+     +----+
  //                           | T0 | --> | Q0 | --> | T3 |
  //                           +----+     +----+  ^  +----+
  //                                              |
  //     +----+     +----+     +----+     +----+  |
  //     | T1 | --> | Q1 | --> | T2 | --> | Q2 | -+
  //     +----+     +----+     +----+     +----+
  //
  // To this, by having T4 block in Q0, declaring T1 to be the new owner.
  //
  //     +----+
  //     | T4 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+     +----+     +----+     +----+     +----+     +----+
  //     | T0 | --> | Q0 | --> | T1 | --> | Q1 | --> | T2 | --> | Q2 | --> | T3 |
  //     +----+     +----+     +----+     +----+     +----+     +----+     +----+
  //
  //

  ktl::array<TestQueue, 3> queues;
  ktl::array<TestThread, 5> threads;
  constexpr ktl::array actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 1, .ot_ndx = 2, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 2, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 4, .bq_ndx = 0, .ot_ndx = 1, .owner_expected = true},
  };

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunBAAOTest(threads, queues, actions));

  END_TEST;
}

bool owq_topology_test_basic_requeue() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+          +----+
  //     | T1 | --> | Q0 |          | Q1 |
  //     +----+  ^  +----+          +----+
  //             |
  //     +----+  |
  //     | T2 | -+
  //     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1
  //
  //     +----+
  //     | T0 |
  //     +----+
  //
  //     +----+     +----+
  //     | T2 | --> | Q0 |
  //     +----+     +----+
  //
  //     +----+     +----+
  //     | T1 | --> | Q1 |
  //     +----+     +----+
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 3> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = Invalid, .assign_woken = false};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u};
  constexpr ktl::array expected_owners{Invalid, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_assign_woken_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+          +----+
  //     | T1 | --> | Q0 |          | Q1 |
  //     +----+  ^  +----+          +----+
  //             |
  //     +----+  |
  //     | T2 | -+
  //     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner in the process.
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //     +----+     +----+
  //     | T1 | --> | Q1 |
  //     +----+     +----+
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 3> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = Invalid, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u};
  constexpr ktl::array expected_owners{0u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_assign_both_owners() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+          +----+
  //     | T1 | --> | Q0 |          | Q1 |
  //     +----+  ^  +----+          +----+
  //             |
  //     +----+  |                  +----+
  //     | T2 | -+                  | T3 |
  //     +----+                     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and T3 as the Q1 owner in the process.
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //     +----+     +----+     +----+
  //     | T1 | --> | Q1 | --> | T3 |
  //     +----+     +----+     +----+
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 3, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, Invalid};
  constexpr ktl::array expected_owners{0u, 3u};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_owner_in_wake_queue() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+          +----+
  //     | T1 | --> | Q0 |          | Q1 |
  //     +----+  ^  +----+          +----+
  //             |
  //     +----+  |
  //     | T2 | -+
  //     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and T2 as the new requeue owner.
  //
  //     +----+     +----+     +----+     +----+     +----+
  //     | T1 | --> | Q1 | --> | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+     +----+     +----+
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 3> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 2, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u};
  constexpr ktl::array expected_owners{0u, 2u};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_owner_is_new_wake_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+          +----+
  //     | T1 | --> | Q0 |          | Q1 |
  //     +----+  ^  +----+          +----+
  //             |
  //     +----+  |
  //     | T2 | -+
  //     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and T0 as the new requeue owner.
  //
  //     +----+     +----+
  //     | T1 | --> | Q1 | -+
  //     +----+     +----+  |
  //                        |
  //     +----+     +----+  V  +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 3> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 0, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u};
  constexpr ktl::array expected_owners{0u, 0u};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_owner_is_in_requeue_target() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+          +----+
  //     | T1 | --> | Q0 |          | Q1 |
  //     +----+  ^  +----+          +----+
  //             |
  //     +----+  |
  //     | T2 | -+
  //     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and T1 as the new requeue owner.
  //
  //          +----+     +----+
  //      +-> | T1 | --> | Q1 | -+
  //      |   +----+     +----+  |
  //      |                      |
  //      +----------------------+
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  // This will fail because of the cycle, and should result in:
  //
  //     +----+     +----+
  //     | T1 | --> | Q1 |
  //     +----+     +----+
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 3> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 1, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u};
  constexpr ktl::array expected_owners{0u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_wake_owner_becomes_requeue_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+     +----+          +----+
  //     | T1 | --> | Q0 | --> | T3 |          | Q1 |
  //     +----+  ^  +----+     +----+          +----+
  //             |
  //     +----+  |
  //     | T2 | -+
  //     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and T3 as the new requeue owner.
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //     +----+     +----+     +----+
  //     | T1 | --> | Q1 | --> | T3 |
  //     +----+     +----+     +----+
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 3, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, Invalid};
  constexpr ktl::array expected_owners{0u, 3u};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_wake_and_requeue_have_same_owner_keep_rq_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+     +----+
  //     | T1 | --> | Q0 | --> | T4 |
  //     +----+  ^  +----+  ^  +----+
  //             |          |
  //     +----+  |          |
  //     | T2 | -+          |
  //     +----+             |
  //                        |
  //     +----+     +----+  |
  //     | T3 | --> | Q1 | -+
  //     +----+     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and keep T4 as the requeue owner.
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //     +----+     +----+     +----+
  //     | T1 | --> | Q1 | --> | T4 |
  //     +----+  ^  +----+     +----+
  //             |
  //     +----+  |
  //     | T3 | -+
  //     +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 5> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 4, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 4, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u, Invalid};
  constexpr ktl::array expected_owners{0u, 4u};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_wake_and_requeue_have_same_owner_lose_rq_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+     +----+
  //     | T1 | --> | Q0 | --> | T4 |
  //     +----+  ^  +----+  ^  +----+
  //             |          |
  //     +----+  |          |
  //     | T2 | -+          |
  //     +----+             |
  //                        |
  //     +----+     +----+  |
  //     | T3 | --> | Q1 | -+
  //     +----+     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and no owner for Q1.
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //     +----+     +----+
  //     | T1 | --> | Q1 |
  //     +----+  ^  +----+
  //             |
  //     +----+  |
  //     | T3 | -+
  //     +----+
  //
  //     +----+
  //     | T4 |
  //     +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 5> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 4, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = Invalid, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u, Invalid};
  constexpr ktl::array expected_owners{0u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_op_intersecting_owner_chains_no_rq_owner_change() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+     +----+     +----+     +----+     +----+
  //     | T1 | --> | Q0 | --> | T4 | --> | Q2 | --> | T5 | --> | Q3 |
  //     +----+  ^  +----+     +----+     +----+  ^  +----+     +----+
  //             |                                |
  //     +----+  |                                |
  //     | T2 | -+                                |
  //     +----+                                   |
  //                                              |
  //                           +----+     +----+  |
  //                           | T3 | --> | Q1 | -+
  //                           +----+     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and keeping T5 as the owner for Q1.
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //     +----+     +----+     +----+     +----+
  //     | T4 | --> | Q2 | --> | T5 | --> | Q3 |
  //     +----+     +----+  ^  +----+     +----+
  //                        |
  //     +----+     +----+  |
  //     | T3 | --> | Q1 | -+
  //     +----+  ^  +----+
  //             |
  //     +----+  |
  //     | T1 | -+
  //     +----+
  //
  //
  ktl::array<TestQueue, 4> queues;
  ktl::array<TestThread, 6> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 5, .owner_expected = true},
      Action{.t_ndx = 4, .bq_ndx = 2, .ot_ndx = 5, .owner_expected = true},
      Action{.t_ndx = 5, .bq_ndx = 3, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 5, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u, 2u, 3u};
  constexpr ktl::array expected_owners{0u, 5u, 5u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_op_intersecting_owner_chains_change_rqo_to_none() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+     +----+     +----+     +----+     +----+
  //     | T1 | --> | Q0 | --> | T4 | --> | Q2 | --> | T5 | --> | Q3 |
  //     +----+  ^  +----+     +----+     +----+  ^  +----+     +----+
  //             |                                |
  //     +----+  |                                |
  //     | T2 | -+                                |
  //     +----+                                   |
  //                                              |
  //                           +----+     +----+  |
  //                           | T3 | --> | Q1 | -+
  //                           +----+     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing no-owner for Q1.
  //
  //     +----+     +----+     +----+
  //     | T2 | --> | Q0 | --> | T0 |
  //     +----+     +----+     +----+
  //
  //     +----+     +----+     +----+     +----+
  //     | T4 | --> | Q2 | --> | T5 | --> | Q3 |
  //     +----+     +----+     +----+     +----+
  //
  //     +----+     +----+
  //     | T3 | --> | Q1 |
  //     +----+  ^  +----+
  //             |
  //     +----+  |
  //     | T1 | -+
  //     +----+
  //
  //
  ktl::array<TestQueue, 4> queues;
  ktl::array<TestThread, 6> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 5, .owner_expected = true},
      Action{.t_ndx = 4, .bq_ndx = 2, .ot_ndx = 5, .owner_expected = true},
      Action{.t_ndx = 5, .bq_ndx = 3, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = Invalid, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u, 2u, 3u};
  constexpr ktl::array expected_owners{0u, Invalid, 5u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_op_intersecting_owner_chains_change_rqo_to_wq_thread() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //     +----+
  //     | T0 | -+
  //     +----+  |
  //             |
  //     +----+  V  +----+     +----+     +----+     +----+     +----+
  //     | T1 | --> | Q0 | --> | T4 | --> | Q2 | --> | T5 | --> | Q3 |
  //     +----+  ^  +----+     +----+     +----+  ^  +----+     +----+
  //             |                                |
  //     +----+  |                                |
  //     | T2 | -+                                |
  //     +----+                                   |
  //                                              |
  //                           +----+     +----+  |
  //                           | T3 | --> | Q1 | -+
  //                           +----+     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing T2 as the new owner of Q1.
  //
  //     +----+     +----+     +----+     +----+     +----+
  //     | T3 | --> | Q1 | --> | T2 | --> | Q0 | --> | T0 |
  //     +----+  ^  +----+     +----+     +----+     +----+
  //             |
  //     +----+  |
  //     | T1 | -+
  //     +----+
  //
  //     +----+     +----+     +----+     +----+
  //     | T4 | --> | Q2 | --> | T5 | --> | Q3 |
  //     +----+     +----+     +----+     +----+
  //
  ktl::array<TestQueue, 4> queues;
  ktl::array<TestThread, 6> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 4, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 5, .owner_expected = true},
      Action{.t_ndx = 4, .bq_ndx = 2, .ot_ndx = 5, .owner_expected = true},
      Action{.t_ndx = 5, .bq_ndx = 3, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 2u, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u, 2u, 3u};
  constexpr ktl::array expected_owners{0u, 2u, 5u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_target_upstream_from_woken_thread() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //    +----+     +----+     +----+
  //    | T3 | --> | Q1 | --> | T0 | -+
  //    +----+     +----+     +----+  |
  //                                  |
  //                          +----+  V  +----+
  //                          | T1 | --> | Q0 |
  //                          +----+  ^  +----+
  //                                  |
  //                          +----+  |
  //                          | T2 | -+
  //                          +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing no owner for Q1.
  //
  //    +----+     +----+     +----+
  //    | T2 | --> | Q0 | --> | T0 |
  //    +----+     +----+     +----+
  //
  //    +----+     +----+
  //    | T1 | --> | Q1 |
  //    +----+  ^  +----+
  //            |
  //    +----+  |
  //    | T3 | -+
  //    +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 0, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = Invalid, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u};
  constexpr ktl::array expected_owners{0u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_target_upstream_from_requeue_thread() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //                          +----+
  //                          | T0 | -+
  //                          +----+  |
  //                                  |
  //    +----+     +----+     +----+  V  +----+
  //    | T3 | --> | Q1 | --> | T1 | --> | Q0 |
  //    +----+     +----+     +----+  ^  +----+
  //                                  |
  //                          +----+  |
  //                          | T2 | -+
  //                          +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing no owner for Q1.
  //
  //    +----+     +----+     +----+
  //    | T2 | --> | Q0 | --> | T0 |
  //    +----+     +----+     +----+
  //
  //    +----+     +----+
  //    | T1 | --> | Q1 |
  //    +----+  ^  +----+
  //            |
  //    +----+  |
  //    | T3 | -+
  //    +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 1, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = Invalid, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u};
  constexpr ktl::array expected_owners{0u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_target_upstream_from_still_blocked_thread() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //                          +----+
  //                          | T0 | -+
  //                          +----+  |
  //                                  |
  //                          +----+  V  +----+
  //                          | T1 | --> | Q0 |
  //                          +----+  ^  +----+
  //                                  |
  //    +----+     +----+     +----+  |
  //    | T3 | --> | Q1 | --> | T2 | -+
  //    +----+     +----+     +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing no owner for Q1.
  //
  //    +----+     +----+     +----+
  //    | T2 | --> | Q0 | --> | T0 |
  //    +----+     +----+     +----+
  //
  //    +----+     +----+
  //    | T1 | --> | Q1 |
  //    +----+  ^  +----+
  //            |
  //    +----+  |
  //    | T3 | -+
  //    +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 2, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = Invalid, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u};
  constexpr ktl::array expected_owners{0u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_requeue_target_upstream_from_requeue_thread_stays_upstream() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //                          +----+
  //                          | T0 | -+
  //                          +----+  |
  //                                  |
  //    +----+     +----+     +----+  V  +----+
  //    | T3 | --> | Q1 | --> | T1 | --> | Q0 |
  //    +----+     +----+     +----+  ^  +----+
  //                                  |
  //                          +----+  |
  //                          | T2 | -+
  //                          +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing T2 as the new owner for Q1.
  //
  //    +----+     +----+     +----+     +----+     +----+
  //    | T1 | --> | Q1 | --> | T2 | --> | Q0 | --> | T0 |
  //    +----+  ^  +----+     +----+     +----+     +----+
  //            |
  //    +----+  |
  //    | T3 | -+
  //    +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = Invalid, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = 1, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 2, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u};
  constexpr ktl::array expected_owners{0u, 2u};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_wake_queue_upstream_from_requeue_target() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //    +----+
  //    | T0 | -+
  //    +----+  |
  //            |
  //    +----+  V  +----+     +----+     +----+
  //    | T1 | --> | Q0 | --> | T3 | --> | Q1 |
  //    +----+  ^  +----+     +----+     +----+
  //            |
  //    +----+  |
  //    | T2 | -+
  //    +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing no owner for Q1.
  //
  //    +----+     +----+     +----+
  //    | T2 | --> | Q0 | --> | T0 |
  //    +----+     +----+     +----+
  //
  //    +----+     +----+
  //    | T1 | --> | Q1 |
  //    +----+  ^  +----+
  //            |
  //    +----+  |
  //    | T3 | -+
  //    +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = Invalid, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u};
  constexpr ktl::array expected_owners{0u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_wake_queue_upstream_from_requeue_target_swaps_position() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //    +----+
  //    | T0 | -+
  //    +----+  |
  //            |
  //    +----+  V  +----+     +----+     +----+
  //    | T1 | --> | Q0 | --> | T3 | --> | Q1 |
  //    +----+  ^  +----+     +----+     +----+
  //            |
  //    +----+  |
  //    | T2 | -+
  //    +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing T2 for the new owner of Q1.
  //
  //    +----+     +----+     +----+     +----+     +----+
  //    | T1 | --> | Q1 | --> | T2 | --> | Q0 | --> | T0 |
  //    +----+  ^  +----+     +----+     +----+     +----+
  //            |
  //    +----+  |
  //    | T3 | -+
  //    +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 2, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u};
  constexpr ktl::array expected_owners{0u, 2u};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_wake_queue_upstream_from_requeue_target_shares_new_wq_owner() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //    +----+
  //    | T0 | -+
  //    +----+  |
  //            |
  //    +----+  V  +----+     +----+     +----+
  //    | T1 | --> | Q0 | --> | T3 | --> | Q1 |
  //    +----+  ^  +----+     +----+     +----+
  //            |
  //    +----+  |
  //    | T2 | -+
  //    +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing T0 for the new owner of Q1.
  //
  //    +----+     +----+     +----+
  //    | T2 | --> | Q0 | --> | T0 |
  //    +----+     +----+  ^  +----+
  //                       |
  //    +----+     +----+  |
  //    | T1 | --> | Q1 | -+
  //    +----+  ^  +----+
  //            |
  //    +----+  |
  //    | T3 | -+
  //    +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 0, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u};
  constexpr ktl::array expected_owners{0u, 0u};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

bool owq_topology_test_wake_queue_upstream_from_requeue_target_rejects_new_rq_thread() {
  BEGIN_TEST;

  // Try to go from this:
  //
  //    +----+
  //    | T0 | -+
  //    +----+  |
  //            |
  //    +----+  V  +----+     +----+     +----+
  //    | T1 | --> | Q0 | --> | T3 | --> | Q1 |
  //    +----+  ^  +----+     +----+     +----+
  //            |
  //    +----+  |
  //    | T2 | -+
  //    +----+
  //
  // To this, by doing a wake-1, requeue-1 from Q0 to Q1, assigning the woken
  // thread as the Q0 owner, and choosing T1 for the new owner of Q1.
  //
  //    +----+     +----+     +----+
  //    | T2 | --> | Q0 | --> | T0 |
  //    +----+     +----+     +----+
  //
  //     +----------------------+
  //     |                      |
  //     V   +----+     +----+  |
  //     +-> | T1 | --> | Q1 |--+
  //         +----+  ^  +----+
  //                 |
  //         +----+  |
  //         | T3 | -+
  //         +----+
  //
  // This cycle should be rejected, resulting in the following:
  //
  //    +----+     +----+     +----+
  //    | T2 | --> | Q0 | --> | T0 |
  //    +----+     +----+     +----+
  //
  //    +----+     +----+
  //    | T1 | --> | Q1 |
  //    +----+  ^  +----+
  //            |
  //    +----+  |
  //    | T3 | -+
  //    +----+
  //
  //
  ktl::array<TestQueue, 2> queues;
  ktl::array<TestThread, 4> threads;
  constexpr ktl::array setup_actions{
      Action{.t_ndx = 0, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 1, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 2, .bq_ndx = 0, .ot_ndx = 3, .owner_expected = true},
      Action{.t_ndx = 3, .bq_ndx = 1, .ot_ndx = Invalid, .owner_expected = true},
  };
  constexpr RequeueAction requeue_action = {
      .wake_count = 1, .requeue_count = 1, .requeue_owner_ndx = 1, .assign_woken = true};
  constexpr ktl::array expected_blocking_queues{Invalid, 1u, 0u, 1u};
  constexpr ktl::array expected_owners{0u, Invalid};

  ASSERT_TRUE(OwnedWaitQueueTopologyTests::RunRequeueTest(
      threads, queues, setup_actions, requeue_action, expected_blocking_queues, expected_owners));

  END_TEST;
}

}  // namespace

UNITTEST_START_TESTCASE(owq_topology_tests)
UNITTEST("simple", owq_topology_test_simple)
UNITTEST("simple owner change", owq_topology_test_simple_owner_change)
UNITTEST("deny self own", owq_topology_test_deny_self_own)
UNITTEST("owner becomes blocked; no new owner",
         owq_topology_test_owner_becomes_blocked_no_new_owner)
UNITTEST("owner becomes blocked; yes new owner",
         owq_topology_test_owner_becomes_blocked_yes_new_owner)
UNITTEST("owner becomes blocked deny blocked new owner",
         owq_topology_test_owner_becomes_blocked_deny_blocked_new_owner)
UNITTEST("blocked owners", owq_topology_test_blocked_owners)
UNITTEST("blocking thread downstream of owner; no owner change",
         owq_topology_test_blocking_thread_downstream_of_owner_no_owner_change)
UNITTEST("blocking thread downstream of owner; yes owner change",
         owq_topology_test_blocking_thread_downstream_of_owner_yes_owner_change)
UNITTEST("intersecting owner chains", owq_topology_test_intersecting_owner_chains)
UNITTEST("intersecting owner chains; old owner is target of new owner chain",
         owq_topology_test_intersecting_owner_chains_old_owner_target_of_new_owner_chain)
UNITTEST("basic requeue", owq_topology_test_basic_requeue)
UNITTEST("requeue assign woken owner", owq_topology_test_requeue_assign_woken_owner)
UNITTEST("requeue assign both owners", owq_topology_test_requeue_assign_both_owners)
UNITTEST("requeue owner in wake queue", owq_topology_test_requeue_owner_in_wake_queue)
UNITTEST("requeue owner is new wake owner", owq_topology_test_requeue_owner_is_new_wake_owner)
UNITTEST("requeue owner is in requeue target", owq_topology_test_requeue_owner_is_in_requeue_target)
UNITTEST("wake owner becomes requeue owner", owq_topology_test_wake_owner_becomes_requeue_owner)
UNITTEST("wake and requeue have same owner keep rq owner",
         owq_topology_test_wake_and_requeue_have_same_owner_keep_rq_owner)
UNITTEST("wake and requeue have same owner lose rq owner",
         owq_topology_test_wake_and_requeue_have_same_owner_lose_rq_owner)
UNITTEST("requeue op intersecting owner chains no rq owner change",
         owq_topology_test_requeue_op_intersecting_owner_chains_no_rq_owner_change)
UNITTEST("requeue op intersecting owner chains change rqo to none",
         owq_topology_test_requeue_op_intersecting_owner_chains_change_rqo_to_none)
UNITTEST("requeue op intersecting owner chains change rqo to wq thread",
         owq_topology_test_requeue_op_intersecting_owner_chains_change_rqo_to_wq_thread)
UNITTEST("requeue target upstream from woken thread",
         owq_topology_test_requeue_target_upstream_from_woken_thread)
UNITTEST("requeue target upstream from requeue thread",
         owq_topology_test_requeue_target_upstream_from_requeue_thread)
UNITTEST("requeue target upstream from still blocked thread",
         owq_topology_test_requeue_target_upstream_from_still_blocked_thread)
UNITTEST("requeue target upstream from requeue thread stays upstream",
         owq_topology_test_requeue_target_upstream_from_requeue_thread_stays_upstream)
UNITTEST("wake queue upstream from requeue target",
         owq_topology_test_wake_queue_upstream_from_requeue_target)
UNITTEST("wake queue upstream from requeue target swaps position",
         owq_topology_test_wake_queue_upstream_from_requeue_target_swaps_position)
UNITTEST("wake queue upstream from requeue target shares new wq owner",
         owq_topology_test_wake_queue_upstream_from_requeue_target_shares_new_wq_owner)
UNITTEST("wake queue upstream from requeue target rejects new rq thread",
         owq_topology_test_wake_queue_upstream_from_requeue_target_rejects_new_rq_thread)
UNITTEST_END_TESTCASE(owq_topology_tests, "owq", "OwnedWaitQueue topology tests")