13 files changed, 290 insertions, 109 deletions

diff --git a/src/core/CMakeLists.txt b/src/core/CMakeLists.txt
index c6b5ac196..0252c8c31 100644
--- a/src/core/CMakeLists.txt
+++ b/src/core/CMakeLists.txt
@@ -201,6 +201,9 @@ add_library(core STATIC
     hle/kernel/k_event_info.h
     hle/kernel/k_handle_table.cpp
     hle/kernel/k_handle_table.h
+    hle/kernel/k_hardware_timer_base.h
+    hle/kernel/k_hardware_timer.cpp
+    hle/kernel/k_hardware_timer.h
     hle/kernel/k_interrupt_manager.cpp
     hle/kernel/k_interrupt_manager.h
     hle/kernel/k_light_condition_variable.cpp
@@ -268,6 +271,7 @@ add_library(core STATIC
     hle/kernel/k_thread_local_page.h
     hle/kernel/k_thread_queue.cpp
     hle/kernel/k_thread_queue.h
+    hle/kernel/k_timer_task.h
     hle/kernel/k_trace.h
     hle/kernel/k_transfer_memory.cpp
     hle/kernel/k_transfer_memory.h
@@ -290,8 +294,6 @@ add_library(core STATIC
     hle/kernel/svc_common.h
     hle/kernel/svc_types.h
     hle/kernel/svc_wrap.h
-    hle/kernel/time_manager.cpp
-    hle/kernel/time_manager.h
     hle/result.h
     hle/service/acc/acc.cpp
     hle/service/acc/acc.h
diff --git a/src/core/hle/kernel/k_address_arbiter.cpp b/src/core/hle/kernel/k_address_arbiter.cpp
index f85b11557..a442a3b98 100644
--- a/src/core/hle/kernel/k_address_arbiter.cpp
+++ b/src/core/hle/kernel/k_address_arbiter.cpp
@@ -10,7 +10,6 @@
 #include "core/hle/kernel/k_thread_queue.h"
 #include "core/hle/kernel/kernel.h"
 #include "core/hle/kernel/svc_results.h"
-#include "core/hle/kernel/time_manager.h"
 #include "core/memory.h"
 
 namespace Kernel {
diff --git a/src/core/hle/kernel/k_hardware_timer.cpp b/src/core/hle/kernel/k_hardware_timer.cpp
new file mode 100644
index 000000000..6bba79ea0
--- /dev/null
+++ b/src/core/hle/kernel/k_hardware_timer.cpp
@@ -0,0 +1,74 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#include "core/core.h"
+#include "core/core_timing.h"
+#include "core/hle/kernel/k_hardware_timer.h"
+#include "core/hle/kernel/k_scheduler.h"
+
+namespace Kernel {
+
+void KHardwareTimer::Initialize() {
+    // Create the timing callback to register with CoreTiming.
+    m_event_type = Core::Timing::CreateEvent(
+        "KHardwareTimer::Callback", [](std::uintptr_t timer_handle, s64, std::chrono::nanoseconds) {
+            reinterpret_cast<KHardwareTimer*>(timer_handle)->DoTask();
+            return std::nullopt;
+        });
+}
+
+void KHardwareTimer::Finalize() {
+    this->DisableInterrupt();
+    m_event_type.reset();
+}
+
+void KHardwareTimer::DoTask() {
+    // Handle the interrupt.
+    {
+        KScopedSchedulerLock slk{m_kernel};
+        KScopedSpinLock lk(this->GetLock());
+
+        //! Ignore this event if needed.
+        if (!this->GetInterruptEnabled()) {
+            return;
+        }
+
+        // Disable the timer interrupt while we handle this.
+        this->DisableInterrupt();
+
+        if (const s64 next_time = this->DoInterruptTaskImpl(GetTick());
+            0 < next_time && next_time <= m_wakeup_time) {
+            // We have a next time, so we should set the time to interrupt and turn the interrupt
+            // on.
+            this->EnableInterrupt(next_time);
+        }
+    }
+
+    // Clear the timer interrupt.
+    // Kernel::GetInterruptManager().ClearInterrupt(KInterruptName_NonSecurePhysicalTimer,
+    //                                              GetCurrentCoreId());
+}
+
+void KHardwareTimer::EnableInterrupt(s64 wakeup_time) {
+    this->DisableInterrupt();
+
+    m_wakeup_time = wakeup_time;
+    m_kernel.System().CoreTiming().ScheduleEvent(std::chrono::nanoseconds{m_wakeup_time},
+                                                 m_event_type, reinterpret_cast<uintptr_t>(this),
+                                                 true);
+}
+
+void KHardwareTimer::DisableInterrupt() {
+    m_kernel.System().CoreTiming().UnscheduleEvent(m_event_type, reinterpret_cast<uintptr_t>(this));
+    m_wakeup_time = std::numeric_limits<s64>::max();
+}
+
+s64 KHardwareTimer::GetTick() const {
+    return m_kernel.System().CoreTiming().GetGlobalTimeNs().count();
+}
+
+bool KHardwareTimer::GetInterruptEnabled() {
+    return m_wakeup_time != std::numeric_limits<s64>::max();
+}
+
+} // namespace Kernel
diff --git a/src/core/hle/kernel/k_hardware_timer.h b/src/core/hle/kernel/k_hardware_timer.h
new file mode 100644
index 000000000..00bef6ea1
--- /dev/null
+++ b/src/core/hle/kernel/k_hardware_timer.h
@@ -0,0 +1,54 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include "core/hle/kernel/k_hardware_timer_base.h"
+
+namespace Core::Timing {
+struct EventType;
+} // namespace Core::Timing
+
+namespace Kernel {
+
+class KHardwareTimer : /* public KInterruptTask, */ public KHardwareTimerBase {
+public:
+    explicit KHardwareTimer(KernelCore& kernel) : KHardwareTimerBase{kernel} {}
+
+    // Public API.
+    void Initialize();
+    void Finalize();
+
+    s64 GetCount() const {
+        return GetTick();
+    }
+
+    void RegisterTask(KTimerTask* task, s64 time_from_now) {
+        this->RegisterAbsoluteTask(task, GetTick() + time_from_now);
+    }
+
+    void RegisterAbsoluteTask(KTimerTask* task, s64 task_time) {
+        KScopedDisableDispatch dd{m_kernel};
+        KScopedSpinLock lk{this->GetLock()};
+
+        if (this->RegisterAbsoluteTaskImpl(task, task_time)) {
+            if (task_time <= m_wakeup_time) {
+                this->EnableInterrupt(task_time);
+            }
+        }
+    }
+
+private:
+    void EnableInterrupt(s64 wakeup_time);
+    void DisableInterrupt();
+    bool GetInterruptEnabled();
+    s64 GetTick() const;
+    void DoTask();
+
+private:
+    // Absolute time in nanoseconds
+    s64 m_wakeup_time{std::numeric_limits<s64>::max()};
+    std::shared_ptr<Core::Timing::EventType> m_event_type{};
+};
+
+} // namespace Kernel
diff --git a/src/core/hle/kernel/k_hardware_timer_base.h b/src/core/hle/kernel/k_hardware_timer_base.h
new file mode 100644
index 000000000..6318b35bd
--- /dev/null
+++ b/src/core/hle/kernel/k_hardware_timer_base.h
@@ -0,0 +1,92 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include "core/hle/kernel/k_spin_lock.h"
+#include "core/hle/kernel/k_thread.h"
+#include "core/hle/kernel/k_timer_task.h"
+
+namespace Kernel {
+
+class KHardwareTimerBase {
+public:
+    explicit KHardwareTimerBase(KernelCore& kernel) : m_kernel{kernel} {}
+
+    void CancelTask(KTimerTask* task) {
+        KScopedDisableDispatch dd{m_kernel};
+        KScopedSpinLock lk{m_lock};
+
+        if (const s64 task_time = task->GetTime(); task_time > 0) {
+            this->RemoveTaskFromTree(task);
+        }
+    }
+
+protected:
+    KSpinLock& GetLock() {
+        return m_lock;
+    }
+
+    s64 DoInterruptTaskImpl(s64 cur_time) {
+        // We want to handle all tasks, returning the next time that a task is scheduled.
+        while (true) {
+            // Get the next task. If there isn't one, return 0.
+            KTimerTask* task = m_next_task;
+            if (task == nullptr) {
+                return 0;
+            }
+
+            // If the task needs to be done in the future, do it in the future and not now.
+            if (const s64 task_time = task->GetTime(); task_time > cur_time) {
+                return task_time;
+            }
+
+            // Remove the task from the tree of tasks, and update our next task.
+            this->RemoveTaskFromTree(task);
+
+            // Handle the task.
+            task->OnTimer();
+        }
+    }
+
+    bool RegisterAbsoluteTaskImpl(KTimerTask* task, s64 task_time) {
+        ASSERT(task_time > 0);
+
+        // Set the task's time, and insert it into our tree.
+        task->SetTime(task_time);
+        m_task_tree.insert(*task);
+
+        // Update our next task if relevant.
+        if (m_next_task != nullptr && m_next_task->GetTime() <= task_time) {
+            return false;
+        }
+        m_next_task = task;
+        return true;
+    }
+
+private:
+    void RemoveTaskFromTree(KTimerTask* task) {
+        // Erase from the tree.
+        auto it = m_task_tree.erase(m_task_tree.iterator_to(*task));
+
+        // Clear the task's scheduled time.
+        task->SetTime(0);
+
+        // Update our next task if relevant.
+        if (m_next_task == task) {
+            m_next_task = (it != m_task_tree.end()) ? std::addressof(*it) : nullptr;
+        }
+    }
+
+protected:
+    KernelCore& m_kernel;
+
+private:
+    using TimerTaskTree = Common::IntrusiveRedBlackTreeBaseTraits<KTimerTask>::TreeType<KTimerTask>;
+
+    KSpinLock m_lock{};
+    TimerTaskTree m_task_tree{};
+    KTimerTask* m_next_task{};
+};
+
+} // namespace Kernel
diff --git a/src/core/hle/kernel/k_scoped_scheduler_lock_and_sleep.h b/src/core/hle/kernel/k_scoped_scheduler_lock_and_sleep.h
index 76c095e69..76db65a4d 100644
--- a/src/core/hle/kernel/k_scoped_scheduler_lock_and_sleep.h
+++ b/src/core/hle/kernel/k_scoped_scheduler_lock_and_sleep.h
@@ -5,9 +5,9 @@
 
 #include "common/common_types.h"
 #include "core/hle/kernel/global_scheduler_context.h"
+#include "core/hle/kernel/k_hardware_timer.h"
 #include "core/hle/kernel/k_thread.h"
 #include "core/hle/kernel/kernel.h"
-#include "core/hle/kernel/time_manager.h"
 
 namespace Kernel {
 
@@ -22,7 +22,7 @@ public:
     ~KScopedSchedulerLockAndSleep() {
         // Register the sleep.
         if (timeout_tick > 0) {
-            kernel.TimeManager().ScheduleTimeEvent(thread, timeout_tick);
+            kernel.HardwareTimer().RegisterTask(thread, timeout_tick);
         }
 
         // Unlock the scheduler.
diff --git a/src/core/hle/kernel/k_thread.h b/src/core/hle/kernel/k_thread.h
index dc52b4ed3..7cd94a340 100644
--- a/src/core/hle/kernel/k_thread.h
+++ b/src/core/hle/kernel/k_thread.h
@@ -22,6 +22,7 @@
 #include "core/hle/kernel/k_light_lock.h"
 #include "core/hle/kernel/k_spin_lock.h"
 #include "core/hle/kernel/k_synchronization_object.h"
+#include "core/hle/kernel/k_timer_task.h"
 #include "core/hle/kernel/k_worker_task.h"
 #include "core/hle/kernel/slab_helpers.h"
 #include "core/hle/kernel/svc_common.h"
@@ -112,7 +113,8 @@ void SetCurrentThread(KernelCore& kernel, KThread* thread);
 [[nodiscard]] s32 GetCurrentCoreId(KernelCore& kernel);
 
 class KThread final : public KAutoObjectWithSlabHeapAndContainer<KThread, KWorkerTask>,
-                      public boost::intrusive::list_base_hook<> {
+                      public boost::intrusive::list_base_hook<>,
+                      public KTimerTask {
     KERNEL_AUTOOBJECT_TRAITS(KThread, KSynchronizationObject);
 
 private:
@@ -840,4 +842,8 @@ private:
     KernelCore& kernel;
 };
 
+inline void KTimerTask::OnTimer() {
+    static_cast<KThread*>(this)->OnTimer();
+}
+
 } // namespace Kernel
diff --git a/src/core/hle/kernel/k_thread_queue.cpp b/src/core/hle/kernel/k_thread_queue.cpp
index 9f4e081ba..5f1dc97eb 100644
--- a/src/core/hle/kernel/k_thread_queue.cpp
+++ b/src/core/hle/kernel/k_thread_queue.cpp
@@ -1,9 +1,9 @@
 // SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
 // SPDX-License-Identifier: GPL-2.0-or-later
 
+#include "core/hle/kernel/k_hardware_timer.h"
 #include "core/hle/kernel/k_thread_queue.h"
 #include "core/hle/kernel/kernel.h"
-#include "core/hle/kernel/time_manager.h"
 
 namespace Kernel {
 
@@ -22,7 +22,7 @@ void KThreadQueue::EndWait(KThread* waiting_thread, Result wait_result) {
     waiting_thread->ClearWaitQueue();
 
     // Cancel the thread task.
-    kernel.TimeManager().UnscheduleTimeEvent(waiting_thread);
+    kernel.HardwareTimer().CancelTask(waiting_thread);
 }
 
 void KThreadQueue::CancelWait(KThread* waiting_thread, Result wait_result, bool cancel_timer_task) {
@@ -37,7 +37,7 @@ void KThreadQueue::CancelWait(KThread* waiting_thread, Result wait_result, bool
 
     // Cancel the thread task.
     if (cancel_timer_task) {
-        kernel.TimeManager().UnscheduleTimeEvent(waiting_thread);
+        kernel.HardwareTimer().CancelTask(waiting_thread);
     }
 }
 
diff --git a/src/core/hle/kernel/k_timer_task.h b/src/core/hle/kernel/k_timer_task.h
new file mode 100644
index 000000000..66f0a5a90
--- /dev/null
+++ b/src/core/hle/kernel/k_timer_task.h
@@ -0,0 +1,40 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include "common/intrusive_red_black_tree.h"
+
+namespace Kernel {
+
+class KTimerTask : public Common::IntrusiveRedBlackTreeBaseNode<KTimerTask> {
+public:
+    static constexpr int Compare(const KTimerTask& lhs, const KTimerTask& rhs) {
+        if (lhs.GetTime() < rhs.GetTime()) {
+            return -1;
+        } else {
+            return 1;
+        }
+    }
+
+    constexpr explicit KTimerTask() = default;
+
+    constexpr void SetTime(s64 t) {
+        m_time = t;
+    }
+
+    constexpr s64 GetTime() const {
+        return m_time;
+    }
+
+    // NOTE: This is virtual in Nintendo's kernel. Prior to 13.0.0, KWaitObject was also a
+    // TimerTask; this is no longer the case. Since this is now KThread exclusive, we have
+    // devirtualized (see inline declaration for this inside k_thread.h).
+    void OnTimer();
+
+private:
+    // Absolute time in nanoseconds
+    s64 m_time{};
+};
+
+} // namespace Kernel
diff --git a/src/core/hle/kernel/kernel.cpp b/src/core/hle/kernel/kernel.cpp
index 0eb74a422..b75bac5df 100644
--- a/src/core/hle/kernel/kernel.cpp
+++ b/src/core/hle/kernel/kernel.cpp
@@ -26,6 +26,7 @@
 #include "core/hle/kernel/k_client_port.h"
 #include "core/hle/kernel/k_dynamic_resource_manager.h"
 #include "core/hle/kernel/k_handle_table.h"
+#include "core/hle/kernel/k_hardware_timer.h"
 #include "core/hle/kernel/k_memory_layout.h"
 #include "core/hle/kernel/k_memory_manager.h"
 #include "core/hle/kernel/k_page_buffer.h"
@@ -39,7 +40,6 @@
 #include "core/hle/kernel/kernel.h"
 #include "core/hle/kernel/physical_core.h"
 #include "core/hle/kernel/service_thread.h"
-#include "core/hle/kernel/time_manager.h"
 #include "core/hle/result.h"
 #include "core/hle/service/sm/sm.h"
 #include "core/memory.h"
@@ -55,7 +55,7 @@ struct KernelCore::Impl {
     static constexpr size_t ReservedDynamicPageCount = 64;
 
     explicit Impl(Core::System& system_, KernelCore& kernel_)
-        : time_manager{system_}, service_threads_manager{1, "ServiceThreadsManager"},
+        : service_threads_manager{1, "ServiceThreadsManager"},
           service_thread_barrier{2}, system{system_} {}
 
     void SetMulticore(bool is_multi) {
@@ -63,6 +63,9 @@ struct KernelCore::Impl {
     }
 
     void Initialize(KernelCore& kernel) {
+        hardware_timer = std::make_unique<Kernel::KHardwareTimer>(kernel);
+        hardware_timer->Initialize();
+
         global_object_list_container = std::make_unique<KAutoObjectWithListContainer>(kernel);
         global_scheduler_context = std::make_unique<Kernel::GlobalSchedulerContext>(kernel);
         global_handle_table = std::make_unique<Kernel::KHandleTable>(kernel);
@@ -193,6 +196,9 @@ struct KernelCore::Impl {
         // Ensure that the object list container is finalized and properly shutdown.
         global_object_list_container->Finalize();
         global_object_list_container.reset();
+
+        hardware_timer->Finalize();
+        hardware_timer.reset();
     }
 
     void CloseServices() {
@@ -832,7 +838,7 @@ struct KernelCore::Impl {
     std::vector<KProcess*> process_list;
     std::atomic<KProcess*> current_process{};
     std::unique_ptr<Kernel::GlobalSchedulerContext> global_scheduler_context;
-    Kernel::TimeManager time_manager;
+    std::unique_ptr<Kernel::KHardwareTimer> hardware_timer;
 
     Init::KSlabResourceCounts slab_resource_counts{};
     KResourceLimit* system_resource_limit{};
@@ -1019,12 +1025,8 @@ Kernel::KScheduler* KernelCore::CurrentScheduler() {
     return impl->schedulers[core_id].get();
 }
 
-Kernel::TimeManager& KernelCore::TimeManager() {
-    return impl->time_manager;
-}
-
-const Kernel::TimeManager& KernelCore::TimeManager() const {
-    return impl->time_manager;
+Kernel::KHardwareTimer& KernelCore::HardwareTimer() {
+    return *impl->hardware_timer;
 }
 
 Core::ExclusiveMonitor& KernelCore::GetExclusiveMonitor() {
diff --git a/src/core/hle/kernel/kernel.h b/src/core/hle/kernel/kernel.h
index 2e22fe0f6..8d22f8d2c 100644
--- a/src/core/hle/kernel/kernel.h
+++ b/src/core/hle/kernel/kernel.h
@@ -39,6 +39,7 @@ class KDynamicPageManager;
 class KEvent;
 class KEventInfo;
 class KHandleTable;
+class KHardwareTimer;
 class KLinkedListNode;
 class KMemoryLayout;
 class KMemoryManager;
@@ -63,7 +64,6 @@ class KCodeMemory;
 class PhysicalCore;
 class ServiceThread;
 class Synchronization;
-class TimeManager;
 
 using ServiceInterfaceFactory =
     std::function<KClientPort&(Service::SM::ServiceManager&, Core::System&)>;
@@ -175,11 +175,8 @@ public:
     /// Gets the an instance of the current physical CPU core.
     const Kernel::PhysicalCore& CurrentPhysicalCore() const;
 
-    /// Gets the an instance of the TimeManager Interface.
-    Kernel::TimeManager& TimeManager();
-
-    /// Gets the an instance of the TimeManager Interface.
-    const Kernel::TimeManager& TimeManager() const;
+    /// Gets the an instance of the hardware timer.
+    Kernel::KHardwareTimer& HardwareTimer();
 
     /// Stops execution of 'id' core, in order to reschedule a new thread.
     void PrepareReschedule(std::size_t id);
diff --git a/src/core/hle/kernel/time_manager.cpp b/src/core/hle/kernel/time_manager.cpp
deleted file mode 100644
index 5ee72c432..000000000
--- a/src/core/hle/kernel/time_manager.cpp
+++ /dev/null
@@ -1,44 +0,0 @@
-// SPDX-FileCopyrightText: Copyright 2020 yuzu Emulator Project
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-#include "common/assert.h"
-#include "core/core.h"
-#include "core/core_timing.h"
-#include "core/hle/kernel/k_scheduler.h"
-#include "core/hle/kernel/k_thread.h"
-#include "core/hle/kernel/time_manager.h"
-
-namespace Kernel {
-
-TimeManager::TimeManager(Core::System& system_) : system{system_} {
-    time_manager_event_type = Core::Timing::CreateEvent(
-        "Kernel::TimeManagerCallback",
-        [this](std::uintptr_t thread_handle, s64 time,
-               std::chrono::nanoseconds) -> std::optional<std::chrono::nanoseconds> {
-            KThread* thread = reinterpret_cast<KThread*>(thread_handle);
-            {
-                KScopedSchedulerLock sl(system.Kernel());
-                thread->OnTimer();
-            }
-            return std::nullopt;
-        });
-}
-
-void TimeManager::ScheduleTimeEvent(KThread* thread, s64 nanoseconds) {
-    std::scoped_lock lock{mutex};
-    if (nanoseconds > 0) {
-        ASSERT(thread);
-        ASSERT(thread->GetState() != ThreadState::Runnable);
-        system.CoreTiming().ScheduleEvent(std::chrono::nanoseconds{nanoseconds},
-                                          time_manager_event_type,
-                                          reinterpret_cast<uintptr_t>(thread));
-    }
-}
-
-void TimeManager::UnscheduleTimeEvent(KThread* thread) {
-    std::scoped_lock lock{mutex};
-    system.CoreTiming().UnscheduleEvent(time_manager_event_type,
-                                        reinterpret_cast<uintptr_t>(thread));
-}
-
-} // namespace Kernel
diff --git a/src/core/hle/kernel/time_manager.h b/src/core/hle/kernel/time_manager.h
deleted file mode 100644
index 94d16b3b4..000000000
--- a/src/core/hle/kernel/time_manager.h
+++ /dev/null
@@ -1,41 +0,0 @@
-// SPDX-FileCopyrightText: Copyright 2020 yuzu Emulator Project
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-#pragma once
-
-#include <memory>
-#include <mutex>
-
-namespace Core {
-class System;
-} // namespace Core
-
-namespace Core::Timing {
-struct EventType;
-} // namespace Core::Timing
-
-namespace Kernel {
-
-class KThread;
-
-/**
- * The `TimeManager` takes care of scheduling time events on threads and executes their TimeUp
- * method when the event is triggered.
- */
-class TimeManager {
-public:
-    explicit TimeManager(Core::System& system);
-
-    /// Schedule a time event on `timetask` thread that will expire in 'nanoseconds'
-    void ScheduleTimeEvent(KThread* time_task, s64 nanoseconds);
-
-    /// Unschedule an existing time event
-    void UnscheduleTimeEvent(KThread* thread);
-
-private:
-    Core::System& system;
-    std::shared_ptr<Core::Timing::EventType> time_manager_event_type;
-    std::mutex mutex;
-};
-
-} // namespace Kernel