From 8634b8cb83755b6c6554faa11c0e488d2ad21f90 Mon Sep 17 00:00:00 2001 From: Subv Date: Sat, 3 Dec 2016 22:38:14 -0500 Subject: Threading: Reworked the way our scheduler works. Threads will now be awakened when the objects they're waiting on are signaled, instead of repeating the WaitSynchronization call every now and then. The scheduler is now called once after every SVC call, and once after a thread is awakened from sleep by its timeout callback. This new implementation is based off reverse-engineering of the real kernel. See https://gist.github.com/Subv/02f29bd9f1e5deb7aceea1e8f019c8f4 for a more detailed description of how the real kernel handles rescheduling. --- src/core/hle/kernel/kernel.cpp | 59 ++++++++++++++++++++++++++++++++++++++---- 1 file changed, 54 insertions(+), 5 deletions(-) (limited to 'src/core/hle/kernel/kernel.cpp') diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp index 0c8752670..be7a5a6d8 100644 --- a/src/core/hle/kernel/kernel.cpp +++ b/src/core/hle/kernel/kernel.cpp @@ -31,13 +31,62 @@ void WaitObject::RemoveWaitingThread(Thread* thread) { waiting_threads.erase(itr); } -void WaitObject::WakeupAllWaitingThreads() { - for (auto thread : waiting_threads) - thread->ResumeFromWait(); +SharedPtr WaitObject::GetHighestPriorityReadyThread() { + // Remove the threads that are ready or already running from our waitlist + waiting_threads.erase(std::remove_if(waiting_threads.begin(), waiting_threads.end(), [](SharedPtr thread) -> bool { + return thread->status == THREADSTATUS_RUNNING || thread->status == THREADSTATUS_READY; + }), waiting_threads.end()); + + if (waiting_threads.empty()) + return nullptr; - waiting_threads.clear(); + auto candidate_threads = waiting_threads; - HLE::Reschedule(__func__); + // Eliminate all threads that are waiting on more than one object, and not all of them are ready + candidate_threads.erase(std::remove_if(candidate_threads.begin(), candidate_threads.end(), [](SharedPtr thread) -> bool { + for (auto object : thread->wait_objects) + if (object->ShouldWait()) + return true; + return false; + }), candidate_threads.end()); + + // Return the thread with the lowest priority value (The one with the highest priority) + auto thread_itr = std::min_element(candidate_threads.begin(), candidate_threads.end(), [](const SharedPtr& lhs, const SharedPtr& rhs) { + return lhs->current_priority < rhs->current_priority; + }); + + if (thread_itr == candidate_threads.end()) + return nullptr; + + return *thread_itr; +} + +void WaitObject::WakeupAllWaitingThreads() { + // Wake up all threads that can be awoken, in priority order + while (auto thread = GetHighestPriorityReadyThread()) { + if (thread->wait_objects.empty()) { + Acquire(); + // Set the output index of the WaitSynchronizationN call to the index of this object. + if (thread->wait_set_output) { + thread->SetWaitSynchronizationOutput(thread->GetWaitObjectIndex(this)); + thread->wait_set_output = false; + } + } else { + for (auto object : thread->wait_objects) { + object->Acquire(); + // Remove the thread from the object's waitlist + object->RemoveWaitingThread(thread.get()); + } + // Note: This case doesn't update the output index of WaitSynchronizationN. + // Clear the thread's waitlist + thread->wait_objects.clear(); + } + + // Set the result of the call to WaitSynchronization to RESULT_SUCCESS + thread->SetWaitSynchronizationResult(RESULT_SUCCESS); + thread->ResumeFromWait(); + // Note: Removing the thread from the object's waitlist will be done by GetHighestPriorityReadyThread + } } const std::vector>& WaitObject::GetWaitingThreads() const { -- cgit v1.2.3 From bdad00c73f46106ba78995bdde1b50349e940b09 Mon Sep 17 00:00:00 2001 From: Subv Date: Sun, 4 Dec 2016 09:58:36 -0500 Subject: Threading: Added some utility functions and const correctness. --- src/core/hle/kernel/kernel.cpp | 13 ++++++------- 1 file changed, 6 insertions(+), 7 deletions(-) (limited to 'src/core/hle/kernel/kernel.cpp') diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp index be7a5a6d8..6d358def7 100644 --- a/src/core/hle/kernel/kernel.cpp +++ b/src/core/hle/kernel/kernel.cpp @@ -33,7 +33,7 @@ void WaitObject::RemoveWaitingThread(Thread* thread) { SharedPtr WaitObject::GetHighestPriorityReadyThread() { // Remove the threads that are ready or already running from our waitlist - waiting_threads.erase(std::remove_if(waiting_threads.begin(), waiting_threads.end(), [](SharedPtr thread) -> bool { + waiting_threads.erase(std::remove_if(waiting_threads.begin(), waiting_threads.end(), [](const SharedPtr& thread) -> bool { return thread->status == THREADSTATUS_RUNNING || thread->status == THREADSTATUS_READY; }), waiting_threads.end()); @@ -42,12 +42,11 @@ SharedPtr WaitObject::GetHighestPriorityReadyThread() { auto candidate_threads = waiting_threads; - // Eliminate all threads that are waiting on more than one object, and not all of them are ready - candidate_threads.erase(std::remove_if(candidate_threads.begin(), candidate_threads.end(), [](SharedPtr thread) -> bool { - for (auto object : thread->wait_objects) - if (object->ShouldWait()) - return true; - return false; + // Eliminate all threads that are waiting on more than one object, and not all of said objects are ready + candidate_threads.erase(std::remove_if(candidate_threads.begin(), candidate_threads.end(), [](const SharedPtr& thread) -> bool { + return std::any_of(thread->wait_objects.begin(), thread->wait_objects.end(), [](const SharedPtr& object) -> bool { + return object->ShouldWait(); + }); }), candidate_threads.end()); // Return the thread with the lowest priority value (The one with the highest priority) -- cgit v1.2.3 From 1f286b72a1b9e1fb98e37a01192f4e31b0ad4e1f Mon Sep 17 00:00:00 2001 From: Subv Date: Tue, 6 Dec 2016 19:15:32 -0500 Subject: Improved the algorithm for GetHighestPriorityReadyThread. --- src/core/hle/kernel/kernel.cpp | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-) (limited to 'src/core/hle/kernel/kernel.cpp') diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp index 6d358def7..07f420099 100644 --- a/src/core/hle/kernel/kernel.cpp +++ b/src/core/hle/kernel/kernel.cpp @@ -40,24 +40,23 @@ SharedPtr WaitObject::GetHighestPriorityReadyThread() { if (waiting_threads.empty()) return nullptr; - auto candidate_threads = waiting_threads; + SharedPtr candidate = nullptr; + s32 candidate_priority = THREADPRIO_LOWEST + 1; - // Eliminate all threads that are waiting on more than one object, and not all of said objects are ready - candidate_threads.erase(std::remove_if(candidate_threads.begin(), candidate_threads.end(), [](const SharedPtr& thread) -> bool { - return std::any_of(thread->wait_objects.begin(), thread->wait_objects.end(), [](const SharedPtr& object) -> bool { + for (const auto& thread : waiting_threads) { + if (thread->current_priority >= candidate_priority) + continue; + + bool ready_to_run = std::none_of(thread->wait_objects.begin(), thread->wait_objects.end(), [](const SharedPtr& object) { return object->ShouldWait(); }); - }), candidate_threads.end()); - - // Return the thread with the lowest priority value (The one with the highest priority) - auto thread_itr = std::min_element(candidate_threads.begin(), candidate_threads.end(), [](const SharedPtr& lhs, const SharedPtr& rhs) { - return lhs->current_priority < rhs->current_priority; - }); - - if (thread_itr == candidate_threads.end()) - return nullptr; + if (ready_to_run) { + candidate = thread; + candidate_priority = thread->current_priority; + } + } - return *thread_itr; + return candidate; } void WaitObject::WakeupAllWaitingThreads() { -- cgit v1.2.3 From 7cde5b83bc9c2dc178bca9fa16ebb28657456b81 Mon Sep 17 00:00:00 2001 From: Subv Date: Tue, 6 Dec 2016 19:31:53 -0500 Subject: Use boost remove_erase_if instead of the erase-remove idiom --- src/core/hle/kernel/kernel.cpp | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'src/core/hle/kernel/kernel.cpp') diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp index 07f420099..b8b69f9d0 100644 --- a/src/core/hle/kernel/kernel.cpp +++ b/src/core/hle/kernel/kernel.cpp @@ -3,6 +3,7 @@ // Refer to the license.txt file included. #include +#include #include "common/assert.h" #include "common/logging/log.h" #include "core/hle/config_mem.h" @@ -33,9 +34,9 @@ void WaitObject::RemoveWaitingThread(Thread* thread) { SharedPtr WaitObject::GetHighestPriorityReadyThread() { // Remove the threads that are ready or already running from our waitlist - waiting_threads.erase(std::remove_if(waiting_threads.begin(), waiting_threads.end(), [](const SharedPtr& thread) -> bool { + boost::range::remove_erase_if(waiting_threads, [](const SharedPtr& thread) -> bool { return thread->status == THREADSTATUS_RUNNING || thread->status == THREADSTATUS_READY; - }), waiting_threads.end()); + }); if (waiting_threads.empty()) return nullptr; -- cgit v1.2.3 From 17b29d8865ea4d96c18f7e1671bd6d0f01eab95f Mon Sep 17 00:00:00 2001 From: Subv Date: Thu, 8 Dec 2016 10:34:53 -0500 Subject: WaitSynch: Removed unused variables and reduced SharedPtr copies. Define a variable with the value of the sync timeout error code. Use a boost::flat_map instead of an unordered_map to hold the equivalence of objects and wait indices in a WaitSynchN call. --- src/core/hle/kernel/kernel.cpp | 14 ++++---------- 1 file changed, 4 insertions(+), 10 deletions(-) (limited to 'src/core/hle/kernel/kernel.cpp') diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp index b8b69f9d0..653697843 100644 --- a/src/core/hle/kernel/kernel.cpp +++ b/src/core/hle/kernel/kernel.cpp @@ -34,14 +34,11 @@ void WaitObject::RemoveWaitingThread(Thread* thread) { SharedPtr WaitObject::GetHighestPriorityReadyThread() { // Remove the threads that are ready or already running from our waitlist - boost::range::remove_erase_if(waiting_threads, [](const SharedPtr& thread) -> bool { + boost::range::remove_erase_if(waiting_threads, [](const SharedPtr& thread) { return thread->status == THREADSTATUS_RUNNING || thread->status == THREADSTATUS_READY; }); - if (waiting_threads.empty()) - return nullptr; - - SharedPtr candidate = nullptr; + Thread* candidate = nullptr; s32 candidate_priority = THREADPRIO_LOWEST + 1; for (const auto& thread : waiting_threads) { @@ -52,7 +49,7 @@ SharedPtr WaitObject::GetHighestPriorityReadyThread() { return object->ShouldWait(); }); if (ready_to_run) { - candidate = thread; + candidate = thread.get(); candidate_priority = thread->current_priority; } } @@ -61,9 +58,8 @@ SharedPtr WaitObject::GetHighestPriorityReadyThread() { } void WaitObject::WakeupAllWaitingThreads() { - // Wake up all threads that can be awoken, in priority order while (auto thread = GetHighestPriorityReadyThread()) { - if (thread->wait_objects.empty()) { + if (!thread->IsSleepingOnWaitAll()) { Acquire(); // Set the output index of the WaitSynchronizationN call to the index of this object. if (thread->wait_set_output) { @@ -73,7 +69,6 @@ void WaitObject::WakeupAllWaitingThreads() { } else { for (auto object : thread->wait_objects) { object->Acquire(); - // Remove the thread from the object's waitlist object->RemoveWaitingThread(thread.get()); } // Note: This case doesn't update the output index of WaitSynchronizationN. @@ -81,7 +76,6 @@ void WaitObject::WakeupAllWaitingThreads() { thread->wait_objects.clear(); } - // Set the result of the call to WaitSynchronization to RESULT_SUCCESS thread->SetWaitSynchronizationResult(RESULT_SUCCESS); thread->ResumeFromWait(); // Note: Removing the thread from the object's waitlist will be done by GetHighestPriorityReadyThread -- cgit v1.2.3 From 406907d57055965780e04769482556995de8c50a Mon Sep 17 00:00:00 2001 From: Subv Date: Sat, 10 Dec 2016 13:29:31 -0500 Subject: Properly remove a thread from its wait_objects' waitlist when it is awoken by a timeout. --- src/core/hle/kernel/kernel.cpp | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'src/core/hle/kernel/kernel.cpp') diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp index 653697843..2ddeffcdd 100644 --- a/src/core/hle/kernel/kernel.cpp +++ b/src/core/hle/kernel/kernel.cpp @@ -38,6 +38,11 @@ SharedPtr WaitObject::GetHighestPriorityReadyThread() { return thread->status == THREADSTATUS_RUNNING || thread->status == THREADSTATUS_READY; }); + // TODO(Subv): This call should be performed inside the loop below to check if an object can be + // acquired by a particular thread. This is useful for things like recursive locking of Mutexes. + if (ShouldWait()) + return nullptr; + Thread* candidate = nullptr; s32 candidate_priority = THREADPRIO_LOWEST + 1; @@ -67,7 +72,7 @@ void WaitObject::WakeupAllWaitingThreads() { thread->wait_set_output = false; } } else { - for (auto object : thread->wait_objects) { + for (auto& object : thread->wait_objects) { object->Acquire(); object->RemoveWaitingThread(thread.get()); } -- cgit v1.2.3 From 5b1edc6ae70972d4a11eee1f1ff8fdff2122b5a2 Mon Sep 17 00:00:00 2001 From: Subv Date: Wed, 14 Dec 2016 12:13:02 -0500 Subject: Fixed the codestyle to match our clang-format rules. --- src/core/hle/kernel/kernel.cpp | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'src/core/hle/kernel/kernel.cpp') diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp index 2ddeffcdd..209d35270 100644 --- a/src/core/hle/kernel/kernel.cpp +++ b/src/core/hle/kernel/kernel.cpp @@ -50,9 +50,9 @@ SharedPtr WaitObject::GetHighestPriorityReadyThread() { if (thread->current_priority >= candidate_priority) continue; - bool ready_to_run = std::none_of(thread->wait_objects.begin(), thread->wait_objects.end(), [](const SharedPtr& object) { - return object->ShouldWait(); - }); + bool ready_to_run = + std::none_of(thread->wait_objects.begin(), thread->wait_objects.end(), + [](const SharedPtr& object) { return object->ShouldWait(); }); if (ready_to_run) { candidate = thread.get(); candidate_priority = thread->current_priority; @@ -83,7 +83,8 @@ void WaitObject::WakeupAllWaitingThreads() { thread->SetWaitSynchronizationResult(RESULT_SUCCESS); thread->ResumeFromWait(); - // Note: Removing the thread from the object's waitlist will be done by GetHighestPriorityReadyThread + // Note: Removing the thread from the object's waitlist will be + // done by GetHighestPriorityReadyThread. } } -- cgit v1.2.3