Merge pull request #683 from bunnei/thread-priority

Thread priority and scheduler improvements

5 files changed, 70 insertions, 28 deletions

diff --git a/src/core/hle/kernel/address_arbiter.cpp b/src/core/hle/kernel/address_arbiter.cpp
index 42f8ce2d9..19135266c 100644
--- a/src/core/hle/kernel/address_arbiter.cpp
+++ b/src/core/hle/kernel/address_arbiter.cpp
@@ -46,14 +46,12 @@ ResultCode AddressArbiter::ArbitrateAddress(ArbitrationType type, VAddr address,
     case ArbitrationType::WaitIfLessThan:
         if ((s32)Memory::Read32(address) <= value) {
             Kernel::WaitCurrentThread_ArbitrateAddress(address);
-            HLE::Reschedule(__func__);
         }
         break;
     case ArbitrationType::WaitIfLessThanWithTimeout:
         if ((s32)Memory::Read32(address) <= value) {
             Kernel::WaitCurrentThread_ArbitrateAddress(address);
             GetCurrentThread()->WakeAfterDelay(nanoseconds);
-            HLE::Reschedule(__func__);
         }
         break;
     case ArbitrationType::DecrementAndWaitIfLessThan:
@@ -62,7 +60,6 @@ ResultCode AddressArbiter::ArbitrateAddress(ArbitrationType type, VAddr address,
         Memory::Write32(address, memory_value);
         if (memory_value <= value) {
             Kernel::WaitCurrentThread_ArbitrateAddress(address);
-            HLE::Reschedule(__func__);
         }
         break;
     }
@@ -73,7 +70,6 @@ ResultCode AddressArbiter::ArbitrateAddress(ArbitrationType type, VAddr address,
         if (memory_value <= value) {
             Kernel::WaitCurrentThread_ArbitrateAddress(address);
             GetCurrentThread()->WakeAfterDelay(nanoseconds);
-            HLE::Reschedule(__func__);
         }
         break;
     }
diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp
index 498b2ec98..6261b82b6 100644
--- a/src/core/hle/kernel/kernel.cpp
+++ b/src/core/hle/kernel/kernel.cpp
@@ -154,7 +154,7 @@ void Shutdown() {
  */
 bool LoadExec(u32 entry_point) {
     // 0x30 is the typical main thread priority I've seen used so far
-    g_main_thread = Kernel::SetupMainThread(Kernel::DEFAULT_STACK_SIZE, entry_point, 0x30);
+    g_main_thread = Kernel::SetupMainThread(Kernel::DEFAULT_STACK_SIZE, entry_point, THREADPRIO_DEFAULT);
 
     return true;
 }
diff --git a/src/core/hle/kernel/mutex.cpp b/src/core/hle/kernel/mutex.cpp
index be2c49706..ebc9e79d7 100644
--- a/src/core/hle/kernel/mutex.cpp
+++ b/src/core/hle/kernel/mutex.cpp
@@ -56,7 +56,15 @@ SharedPtr<Mutex> Mutex::Create(bool initial_locked, std::string name) {
 }
 
 bool Mutex::ShouldWait() {
-    return lock_count > 0 && holding_thread != GetCurrentThread();;
+    auto thread = GetCurrentThread();
+    bool wait = lock_count > 0 && holding_thread != thread;
+
+    // If the holding thread of the mutex is lower priority than this thread, that thread should
+    // temporarily inherit this thread's priority
+    if (wait && thread->current_priority < holding_thread->current_priority)
+        holding_thread->BoostPriority(thread->current_priority);
+
+    return wait;
 }
 
 void Mutex::Acquire() {
diff --git a/src/core/hle/kernel/thread.cpp b/src/core/hle/kernel/thread.cpp
index be1aed615..33d66b986 100644
--- a/src/core/hle/kernel/thread.cpp
+++ b/src/core/hle/kernel/thread.cpp
@@ -140,6 +140,28 @@ void ArbitrateAllThreads(u32 address) {
     }
 }
 
+/// Boost low priority threads (temporarily) that have been starved
+static void PriorityBoostStarvedThreads() {
+    u64 current_ticks = CoreTiming::GetTicks();
+
+    for (auto& thread : thread_list) {
+        // TODO(bunnei): Threads that have been waiting to be scheduled for `boost_ticks` (or
+        // longer) will have their priority temporarily adjusted to 1 higher than the highest
+        // priority thread to prevent thread starvation. This general behavior has been verified
+        // on hardware. However, this is almost certainly not perfect, and the real CTR OS scheduler
+        // should probably be reversed to verify this.
+
+        const u64 boost_timeout = 2000000;  // Boost threads that have been ready for > this long
+
+        u64 delta = current_ticks - thread->last_running_ticks;
+
+        if (thread->status == THREADSTATUS_READY && delta > boost_timeout && !thread->idle) {
+            const s32 priority = std::max(ready_queue.get_first()->current_priority - 1, 0);
+            thread->BoostPriority(priority);
+        }
+    }
+}
+
 /** 
  * Switches the CPU's active thread context to that of the specified thread
  * @param new_thread The thread to switch to
@@ -151,6 +173,7 @@ static void SwitchContext(Thread* new_thread) {
 
     // Save context for previous thread
     if (previous_thread) {
+        previous_thread->last_running_ticks = CoreTiming::GetTicks();
         Core::g_app_core->SaveContext(previous_thread->context);
 
         if (previous_thread->status == THREADSTATUS_RUNNING) {
@@ -168,6 +191,9 @@ static void SwitchContext(Thread* new_thread) {
         ready_queue.remove(new_thread->current_priority, new_thread);
         new_thread->status = THREADSTATUS_RUNNING;
 
+        // Restores thread to its nominal priority if it has been temporarily changed
+        new_thread->current_priority = new_thread->nominal_priority;
+
         Core::g_app_core->LoadContext(new_thread->context);
     } else {
         current_thread = nullptr;
@@ -364,7 +390,8 @@ ResultVal<SharedPtr<Thread>> Thread::Create(std::string name, VAddr entry_point,
     thread->status = THREADSTATUS_DORMANT;
     thread->entry_point = entry_point;
     thread->stack_top = stack_top;
-    thread->initial_priority = thread->current_priority = priority;
+    thread->nominal_priority = thread->current_priority = priority;
+    thread->last_running_ticks = CoreTiming::GetTicks();
     thread->processor_id = processor_id;
     thread->wait_set_output = false;
     thread->wait_all = false;
@@ -400,17 +427,15 @@ static void ClampPriority(const Thread* thread, s32* priority) {
 void Thread::SetPriority(s32 priority) {
     ClampPriority(this, &priority);
 
-    if (current_priority == priority) {
-        return;
-    }
+    // If thread was ready, adjust queues
+    if (status == THREADSTATUS_READY)
+        ready_queue.move(this, current_priority, priority);
 
-    if (status == THREADSTATUS_READY) {
-        // If thread was ready, adjust queues
-        ready_queue.remove(current_priority, this);
-        ready_queue.prepare(priority);
-        ready_queue.push_back(priority, this);
-    }
-    
+    nominal_priority = current_priority = priority;
+}
+
+void Thread::BoostPriority(s32 priority) {
+    ready_queue.move(this, current_priority, priority);
     current_priority = priority;
 }
 
@@ -440,6 +465,9 @@ SharedPtr<Thread> SetupMainThread(u32 stack_size, u32 entry_point, s32 priority)
 
 void Reschedule() {
     Thread* prev = GetCurrentThread();
+
+    PriorityBoostStarvedThreads();
+
     Thread* next = PopNextReadyThread();
     HLE::g_reschedule = false;
 
diff --git a/src/core/hle/kernel/thread.h b/src/core/hle/kernel/thread.h
index cfd073a70..233bcbdbd 100644
--- a/src/core/hle/kernel/thread.h
+++ b/src/core/hle/kernel/thread.h
@@ -17,17 +17,19 @@
 #include "core/hle/kernel/kernel.h"
 #include "core/hle/result.h"
 
-enum ThreadPriority {
-    THREADPRIO_HIGHEST      = 0,    ///< Highest thread priority
-    THREADPRIO_DEFAULT      = 16,   ///< Default thread priority for userland apps
-    THREADPRIO_LOW          = 31,   ///< Low range of thread priority for userland apps
-    THREADPRIO_LOWEST       = 63,   ///< Thread priority max checked by svcCreateThread
+enum ThreadPriority : s32{
+    THREADPRIO_HIGHEST          = 0,  ///< Highest thread priority
+    THREADPRIO_USERLAND_MAX     = 24, ///< Highest thread priority for userland apps
+    THREADPRIO_DEFAULT          = 48, ///< Default thread priority for userland apps
+    THREADPRIO_LOWEST           = 63, ///< Lowest thread priority
 };
 
-enum ThreadProcessorId {
-    THREADPROCESSORID_0     = 0xFFFFFFFE,   ///< Enables core appcode
-    THREADPROCESSORID_1     = 0xFFFFFFFD,   ///< Enables core syscore
-    THREADPROCESSORID_ALL   = 0xFFFFFFFC,   ///< Enables both cores
+enum ThreadProcessorId : s32 {
+    THREADPROCESSORID_DEFAULT   = -2, ///< Run thread on default core specified by exheader
+    THREADPROCESSORID_ALL       = -1, ///< Run thread on either core
+    THREADPROCESSORID_0         =  0, ///< Run thread on core 0 (AppCore)
+    THREADPROCESSORID_1         =  1, ///< Run thread on core 1 (SysCore)
+    THREADPROCESSORID_MAX       =  2, ///< Processor ID must be less than this
 };
 
 enum ThreadStatus {
@@ -88,6 +90,12 @@ public:
     void SetPriority(s32 priority);
 
     /**
+     * Temporarily boosts the thread's priority until the next time it is scheduled
+     * @param priority The new priority
+     */
+    void BoostPriority(s32 priority);
+
+    /**
      * Gets the thread's thread ID
      * @return The thread's ID
      */
@@ -135,8 +143,10 @@ public:
     u32 entry_point;
     u32 stack_top;
 
-    s32 initial_priority;
-    s32 current_priority;
+    s32 nominal_priority;   ///< Nominal thread priority, as set by the emulated application
+    s32 current_priority;   ///< Current thread priority, can be temporarily changed
+
+    u64 last_running_ticks; ///< CPU tick when thread was last running
 
     s32 processor_id;