| // 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(), ¤t_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") |