1 files changed, 146 insertions, 101 deletions

diff --git a/src/core/hle/kernel/scheduler.h b/src/core/hle/kernel/scheduler.h
index b29bf7be8..fcae28e0a 100644
--- a/src/core/hle/kernel/scheduler.h
+++ b/src/core/hle/kernel/scheduler.h
@@ -20,124 +20,172 @@ namespace Kernel {
 
 class Process;
 
-class Scheduler final {
+class GlobalScheduler final {
 public:
-    explicit Scheduler(Core::System& system, Core::ARM_Interface& cpu_core);
-    ~Scheduler();
+    static constexpr u32 NUM_CPU_CORES = 4;
 
-    /// Returns whether there are any threads that are ready to run.
-    bool HaveReadyThreads() const;
+    explicit GlobalScheduler(Core::System& system);
+    ~GlobalScheduler();
+    /// Adds a new thread to the scheduler
+    void AddThread(SharedPtr<Thread> thread);
 
-    /// Reschedules to the next available thread (call after current thread is suspended)
-    void Reschedule();
+    /// Removes a thread from the scheduler
+    void RemoveThread(const Thread* thread);
 
-    /// Gets the current running thread
-    Thread* GetCurrentThread() const;
+    /// Returns a list of all threads managed by the scheduler
+    const std::vector<SharedPtr<Thread>>& GetThreadList() const {
+        return thread_list;
+    }
 
-    /// Gets the timestamp for the last context switch in ticks.
-    u64 GetLastContextSwitchTicks() const;
+    // Add a thread to the suggested queue of a cpu core. Suggested threads may be
+    // picked if no thread is scheduled to run on the core.
+    void Suggest(u32 priority, u32 core, Thread* thread);
 
-    /// Adds a new thread to the scheduler
-    void AddThread(SharedPtr<Thread> thread);
+    // Remove a thread to the suggested queue of a cpu core. Suggested threads may be
+    // picked if no thread is scheduled to run on the core.
+    void Unsuggest(u32 priority, u32 core, Thread* thread);
 
-    /// Removes a thread from the scheduler
-    void RemoveThread(Thread* thread);
+    // Add a thread to the scheduling queue of a cpu core. The thread is added at the
+    // back the queue in its priority level
+    void Schedule(u32 priority, u32 core, Thread* thread);
 
-    /// Schedules a thread that has become "ready"
-    void ScheduleThread(Thread* thread, u32 priority);
+    // Add a thread to the scheduling queue of a cpu core. The thread is added at the
+    // front the queue in its priority level
+    void SchedulePrepend(u32 priority, u32 core, Thread* thread);
 
-    /// Unschedules a thread that was already scheduled
-    void UnscheduleThread(Thread* thread, u32 priority);
+    // Reschedule an already scheduled thread based on a new priority
+    void Reschedule(u32 priority, u32 core, Thread* thread);
 
-    /// Sets the priority of a thread in the scheduler
-    void SetThreadPriority(Thread* thread, u32 priority);
+    // Unschedule a thread.
+    void Unschedule(u32 priority, u32 core, Thread* thread);
 
-    /// Gets the next suggested thread for load balancing
-    Thread* GetNextSuggestedThread(u32 core, u32 minimum_priority) const;
+    // Transfers a thread into an specific core. If the destination_core is -1
+    // it will be unscheduled from its source code and added into its suggested
+    // queue.
+    void TransferToCore(u32 priority, s32 destination_core, Thread* thread);
 
-    /**
-     * YieldWithoutLoadBalancing -- analogous to normal yield on a system
-     * Moves the thread to the end of the ready queue for its priority, and then reschedules the
-     * system to the new head of the queue.
-     *
-     * Example (Single Core -- but can be extrapolated to multi):
-     * ready_queue[prio=0]: ThreadA, ThreadB, ThreadC (->exec order->)
-     * Currently Running: ThreadR
-     *
-     * ThreadR calls YieldWithoutLoadBalancing
-     *
-     * ThreadR is moved to the end of ready_queue[prio=0]:
-     * ready_queue[prio=0]: ThreadA, ThreadB, ThreadC, ThreadR (->exec order->)
-     * Currently Running: Nothing
-     *
-     * System is rescheduled (ThreadA is popped off of queue):
-     * ready_queue[prio=0]: ThreadB, ThreadC, ThreadR (->exec order->)
-     * Currently Running: ThreadA
-     *
-     * If the queue is empty at time of call, no yielding occurs. This does not cross between cores
-     * or priorities at all.
+    /*
+     * UnloadThread selects a core and forces it to unload its current thread's context
      */
-    void YieldWithoutLoadBalancing(Thread* thread);
+    void UnloadThread(s32 core);
+
+    /*
+     * SelectThread takes care of selecting the new scheduled thread.
+     * It does it in 3 steps:
+     * - First a thread is selected from the top of the priority queue. If no thread
+     * is obtained then we move to step two, else we are done.
+     * - Second we try to get a suggested thread that's not assigned to any core or
+     * that is not the top thread in that core.
+     * - Third is no suggested thread is found, we do a second pass and pick a running
+     * thread in another core and swap it with its current thread.
+     */
+    void SelectThread(u32 core);
 
-    /**
-     * YieldWithLoadBalancing -- yield but with better selection of the new running thread
-     * Moves the current thread to the end of the ready queue for its priority, then selects a
-     * 'suggested thread' (a thread on a different core that could run on this core) from the
-     * scheduler, changes its core, and reschedules the current core to that thread.
-     *
-     * Example (Dual Core -- can be extrapolated to Quad Core, this is just normal yield if it were
-     * single core):
-     * ready_queue[core=0][prio=0]: ThreadA, ThreadB (affinities not pictured as irrelevant
-     * ready_queue[core=1][prio=0]: ThreadC[affinity=both], ThreadD[affinity=core1only]
-     * Currently Running: ThreadQ on Core 0 || ThreadP on Core 1
-     *
-     * ThreadQ calls YieldWithLoadBalancing
-     *
-     * ThreadQ is moved to the end of ready_queue[core=0][prio=0]:
-     * ready_queue[core=0][prio=0]: ThreadA, ThreadB
-     * ready_queue[core=1][prio=0]: ThreadC[affinity=both], ThreadD[affinity=core1only]
-     * Currently Running: ThreadQ on Core 0 || ThreadP on Core 1
-     *
-     * A list of suggested threads for each core is compiled
-     * Suggested Threads: {ThreadC on Core 1}
-     * If this were quad core (as the switch is), there could be between 0 and 3 threads in this
-     * list. If there are more than one, the thread is selected by highest prio.
-     *
-     * ThreadC is core changed to Core 0:
-     * ready_queue[core=0][prio=0]: ThreadC, ThreadA, ThreadB, ThreadQ
-     * ready_queue[core=1][prio=0]: ThreadD
-     * Currently Running: None on Core 0 || ThreadP on Core 1
-     *
-     * System is rescheduled (ThreadC is popped off of queue):
-     * ready_queue[core=0][prio=0]: ThreadA, ThreadB, ThreadQ
-     * ready_queue[core=1][prio=0]: ThreadD
-     * Currently Running: ThreadC on Core 0 || ThreadP on Core 1
-     *
-     * If no suggested threads can be found this will behave just as normal yield. If there are
-     * multiple candidates for the suggested thread on a core, the highest prio is taken.
+    bool HaveReadyThreads(u32 core_id) const {
+        return !scheduled_queue[core_id].empty();
+    }
+
+    /*
+     * YieldThread takes a thread and moves it to the back of the it's priority list
+     * This operation can be redundant and no scheduling is changed if marked as so.
      */
-    void YieldWithLoadBalancing(Thread* thread);
+    bool YieldThread(Thread* thread);
 
-    /// Currently unknown -- asserts as unimplemented on call
-    void YieldAndWaitForLoadBalancing(Thread* thread);
+    /*
+     * YieldThreadAndBalanceLoad takes a thread and moves it to the back of the it's priority list.
+     * Afterwards, tries to pick a suggested thread from the suggested queue that has worse time or
+     * a better priority than the next thread in the core.
+     * This operation can be redundant and no scheduling is changed if marked as so.
+     */
+    bool YieldThreadAndBalanceLoad(Thread* thread);
 
-    /// Returns a list of all threads managed by the scheduler
-    const std::vector<SharedPtr<Thread>>& GetThreadList() const {
-        return thread_list;
+    /*
+     * YieldThreadAndWaitForLoadBalancing takes a thread and moves it out of the scheduling queue
+     * and into the suggested queue. If no thread can be squeduled afterwards in that core,
+     * a suggested thread is obtained instead.
+     * This operation can be redundant and no scheduling is changed if marked as so.
+     */
+    bool YieldThreadAndWaitForLoadBalancing(Thread* thread);
+
+    /*
+     * PreemptThreads this operation rotates the scheduling queues of threads at
+     * a preemption priority and then does some core rebalancing. Preemption priorities
+     * can be found in the array 'preemption_priorities'. This operation happens
+     * every 10ms.
+     */
+    void PreemptThreads();
+
+    u32 CpuCoresCount() const {
+        return NUM_CPU_CORES;
+    }
+
+    void SetReselectionPending() {
+        is_reselection_pending.store(true, std::memory_order_release);
     }
 
+    bool IsReselectionPending() const {
+        return is_reselection_pending.load(std::memory_order_acquire);
+    }
+
+    void Shutdown();
+
 private:
-    /**
-     * Pops and returns the next thread from the thread queue
-     * @return A pointer to the next ready thread
-     */
-    Thread* PopNextReadyThread();
+    bool AskForReselectionOrMarkRedundant(Thread* current_thread, Thread* winner);
+
+    static constexpr u32 min_regular_priority = 2;
+    std::array<Common::MultiLevelQueue<Thread*, THREADPRIO_COUNT>, NUM_CPU_CORES> scheduled_queue;
+    std::array<Common::MultiLevelQueue<Thread*, THREADPRIO_COUNT>, NUM_CPU_CORES> suggested_queue;
+    std::atomic<bool> is_reselection_pending;
+
+    // `preemption_priorities` are the priority levels at which the global scheduler
+    // preempts threads every 10 ms. They are ordered from Core 0 to Core 3
+    std::array<u32, NUM_CPU_CORES> preemption_priorities = {59, 59, 59, 62};
+
+    /// Lists all thread ids that aren't deleted/etc.
+    std::vector<SharedPtr<Thread>> thread_list;
+    Core::System& system;
+};
+
+class Scheduler final {
+public:
+    explicit Scheduler(Core::System& system, Core::ARM_Interface& cpu_core, u32 core_id);
+    ~Scheduler();
+
+    /// Returns whether there are any threads that are ready to run.
+    bool HaveReadyThreads() const;
 
+    /// Reschedules to the next available thread (call after current thread is suspended)
+    void TryDoContextSwitch();
+
+    /// Unloads currently running thread
+    void UnloadThread();
+
+    /// Select the threads in top of the scheduling multilist.
+    void SelectThreads();
+
+    /// Gets the current running thread
+    Thread* GetCurrentThread() const;
+
+    /// Gets the currently selected thread from the top of the multilevel queue
+    Thread* GetSelectedThread() const;
+
+    /// Gets the timestamp for the last context switch in ticks.
+    u64 GetLastContextSwitchTicks() const;
+
+    bool ContextSwitchPending() const {
+        return is_context_switch_pending;
+    }
+
+    /// Shutdowns the scheduler.
+    void Shutdown();
+
+private:
+    friend class GlobalScheduler;
     /**
      * Switches the CPU's active thread context to that of the specified thread
      * @param new_thread The thread to switch to
      */
-    void SwitchContext(Thread* new_thread);
+    void SwitchContext();
 
     /**
      * Called on every context switch to update the internal timestamp
@@ -152,19 +200,16 @@ private:
      */
     void UpdateLastContextSwitchTime(Thread* thread, Process* process);
 
-    /// Lists all thread ids that aren't deleted/etc.
-    std::vector<SharedPtr<Thread>> thread_list;
-
-    /// Lists only ready thread ids.
-    Common::MultiLevelQueue<Thread*, THREADPRIO_LOWEST + 1> ready_queue;
-
     SharedPtr<Thread> current_thread = nullptr;
+    SharedPtr<Thread> selected_thread = nullptr;
 
+    Core::System& system;
     Core::ARM_Interface& cpu_core;
     u64 last_context_switch_time = 0;
+    u64 idle_selection_count = 0;
+    const u32 core_id;
 
-    Core::System& system;
-    static std::mutex scheduler_mutex;
+    bool is_context_switch_pending = false;
 };
 
 } // namespace Kernel