From 0b78cfcc532ed4353019d361fc595012cdf2e7c4 Mon Sep 17 00:00:00 2001 From: Lioncash Date: Fri, 15 Mar 2019 01:02:13 -0400 Subject: kernel/thread: Maintain priority ordering of added mutex waiting threads The kernel keeps the internal waiting list ordered by priority. This is trivial to do with std::find_if followed by an insertion. --- src/core/hle/kernel/thread.cpp | 38 ++++++++++++++++++++++++-------------- 1 file changed, 24 insertions(+), 14 deletions(-) diff --git a/src/core/hle/kernel/thread.cpp b/src/core/hle/kernel/thread.cpp index eb54d6651..7706ca9e5 100644 --- a/src/core/hle/kernel/thread.cpp +++ b/src/core/hle/kernel/thread.cpp @@ -7,8 +7,6 @@ #include #include -#include - #include "common/assert.h" #include "common/common_types.h" #include "common/logging/log.h" @@ -269,8 +267,8 @@ void Thread::AddMutexWaiter(SharedPtr thread) { if (thread->lock_owner == this) { // If the thread is already waiting for this thread to release the mutex, ensure that the // waiters list is consistent and return without doing anything. - auto itr = std::find(wait_mutex_threads.begin(), wait_mutex_threads.end(), thread); - ASSERT(itr != wait_mutex_threads.end()); + const auto iter = std::find(wait_mutex_threads.begin(), wait_mutex_threads.end(), thread); + ASSERT(iter != wait_mutex_threads.end()); return; } @@ -278,11 +276,16 @@ void Thread::AddMutexWaiter(SharedPtr thread) { ASSERT(thread->lock_owner == nullptr); // Ensure that the thread is not already in the list of mutex waiters - auto itr = std::find(wait_mutex_threads.begin(), wait_mutex_threads.end(), thread); - ASSERT(itr == wait_mutex_threads.end()); - + const auto iter = std::find(wait_mutex_threads.begin(), wait_mutex_threads.end(), thread); + ASSERT(iter == wait_mutex_threads.end()); + + // Keep the list in an ordered fashion + const auto insertion_point = std::find_if( + wait_mutex_threads.begin(), wait_mutex_threads.end(), + [&thread](const auto& entry) { return entry->GetPriority() > thread->GetPriority(); }); + wait_mutex_threads.insert(insertion_point, thread); thread->lock_owner = this; - wait_mutex_threads.emplace_back(std::move(thread)); + UpdatePriority(); } @@ -290,10 +293,11 @@ void Thread::RemoveMutexWaiter(SharedPtr thread) { ASSERT(thread->lock_owner == this); // Ensure that the thread is in the list of mutex waiters - auto itr = std::find(wait_mutex_threads.begin(), wait_mutex_threads.end(), thread); - ASSERT(itr != wait_mutex_threads.end()); + const auto iter = std::find(wait_mutex_threads.begin(), wait_mutex_threads.end(), thread); + ASSERT(iter != wait_mutex_threads.end()); + + wait_mutex_threads.erase(iter); - boost::remove_erase(wait_mutex_threads, thread); thread->lock_owner = nullptr; UpdatePriority(); } @@ -310,12 +314,18 @@ void Thread::UpdatePriority() { return; scheduler->SetThreadPriority(this, new_priority); - current_priority = new_priority; + if (!lock_owner) { + return; + } + + // Ensure that the thread is within the correct location in the waiting list. + lock_owner->RemoveMutexWaiter(this); + lock_owner->AddMutexWaiter(this); + // Recursively update the priority of the thread that depends on the priority of this one. - if (lock_owner) - lock_owner->UpdatePriority(); + lock_owner->UpdatePriority(); } void Thread::ChangeCore(u32 core, u64 mask) { -- cgit v1.2.3 From 39483b92b7046c36ee937d80a7342b9ec6bc1ec4 Mon Sep 17 00:00:00 2001 From: Lioncash Date: Thu, 14 Mar 2019 21:47:46 -0400 Subject: kernel/thread: Amend condition within UpdatePriority() This condition was checking against the nominal thread priority, whereas the kernel itself checks against the current priority instead. We were also assigning the nominal priority, when we should be assigning current_priority, which takes priority inheritance into account. This can lead to the incorrect priority being assigned to a thread. Given we recursively update the relevant threads, we don't need to go through the whole mutex waiter list. This matches what the kernel does as well (only accessing the first entry within the waiting list). --- src/core/hle/kernel/thread.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/src/core/hle/kernel/thread.cpp b/src/core/hle/kernel/thread.cpp index 7706ca9e5..4b68b555f 100644 --- a/src/core/hle/kernel/thread.cpp +++ b/src/core/hle/kernel/thread.cpp @@ -305,9 +305,9 @@ void Thread::RemoveMutexWaiter(SharedPtr thread) { void Thread::UpdatePriority() { // Find the highest priority among all the threads that are waiting for this thread's lock u32 new_priority = nominal_priority; - for (const auto& thread : wait_mutex_threads) { - if (thread->nominal_priority < new_priority) - new_priority = thread->nominal_priority; + if (!wait_mutex_threads.empty()) { + if (wait_mutex_threads.front()->current_priority < new_priority) + new_priority = wait_mutex_threads.front()->current_priority; } if (new_priority == current_priority) -- cgit v1.2.3 From e0d1f119680e9fa842ade586106bcc6740930583 Mon Sep 17 00:00:00 2001 From: Lioncash Date: Thu, 14 Mar 2019 21:51:03 -0400 Subject: kernel/thread: Make bracing consistent within UpdatePriority() --- src/core/hle/kernel/thread.cpp | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/src/core/hle/kernel/thread.cpp b/src/core/hle/kernel/thread.cpp index 4b68b555f..c5cee12dd 100644 --- a/src/core/hle/kernel/thread.cpp +++ b/src/core/hle/kernel/thread.cpp @@ -306,12 +306,14 @@ void Thread::UpdatePriority() { // Find the highest priority among all the threads that are waiting for this thread's lock u32 new_priority = nominal_priority; if (!wait_mutex_threads.empty()) { - if (wait_mutex_threads.front()->current_priority < new_priority) + if (wait_mutex_threads.front()->current_priority < new_priority) { new_priority = wait_mutex_threads.front()->current_priority; + } } - if (new_priority == current_priority) + if (new_priority == current_priority) { return; + } scheduler->SetThreadPriority(this, new_priority); current_priority = new_priority; -- cgit v1.2.3 From db47d7e4716effb1021be3ebdc90763c3a53cafc Mon Sep 17 00:00:00 2001 From: Lioncash Date: Thu, 14 Mar 2019 21:58:23 -0400 Subject: kernel/thread: Expand documentation of nominal_priority and current_priority Aims to disambiguate why each priority instance exists a little bit. While we're at it, also add an explanatory comment to UpdatePriority(). --- src/core/hle/kernel/thread.cpp | 4 +++- src/core/hle/kernel/thread.h | 10 ++++++++-- 2 files changed, 11 insertions(+), 3 deletions(-) diff --git a/src/core/hle/kernel/thread.cpp b/src/core/hle/kernel/thread.cpp index c5cee12dd..202997d20 100644 --- a/src/core/hle/kernel/thread.cpp +++ b/src/core/hle/kernel/thread.cpp @@ -303,7 +303,9 @@ void Thread::RemoveMutexWaiter(SharedPtr thread) { } void Thread::UpdatePriority() { - // Find the highest priority among all the threads that are waiting for this thread's lock + // If any of the threads waiting on the mutex have a higher priority + // (taking into account priority inheritance), then this thread inherits + // that thread's priority. u32 new_priority = nominal_priority; if (!wait_mutex_threads.empty()) { if (wait_mutex_threads.front()->current_priority < new_priority) { diff --git a/src/core/hle/kernel/thread.h b/src/core/hle/kernel/thread.h index c48b21aba..96d9982d8 100644 --- a/src/core/hle/kernel/thread.h +++ b/src/core/hle/kernel/thread.h @@ -398,8 +398,14 @@ private: VAddr entry_point = 0; VAddr stack_top = 0; - u32 nominal_priority = 0; ///< Nominal thread priority, as set by the emulated application - u32 current_priority = 0; ///< Current thread priority, can be temporarily changed + /// Nominal thread priority, as set by the emulated application. + /// The nominal priority is the thread priority without priority + /// inheritance taken into account. + u32 nominal_priority = 0; + + /// Current thread priority. This may change over the course of the + /// thread's lifetime in order to facilitate priority inheritance. + u32 current_priority = 0; u64 total_cpu_time_ticks = 0; ///< Total CPU running ticks. u64 last_running_ticks = 0; ///< CPU tick when thread was last running -- cgit v1.2.3