From 82151d407d8021fa8865cf8dd51c4d5cf0a4b702 Mon Sep 17 00:00:00 2001
From: B3n30 <bene_thomas@web.de>
Date: Sat, 25 Nov 2017 14:56:57 +0100
Subject: CoreTiming: Reworked CoreTiming (cherry-picked from Citra #3119)

* CoreTiming: New CoreTiming; Add Test for CoreTiming
---
 src/core/core_timing.cpp | 610 +++++++++++------------------------------------
 1 file changed, 143 insertions(+), 467 deletions(-)

(limited to 'src/core/core_timing.cpp')

diff --git a/src/core/core_timing.cpp b/src/core/core_timing.cpp
index c90e62385..a0656f0a8 100644
--- a/src/core/core_timing.cpp
+++ b/src/core/core_timing.cpp
@@ -1,562 +1,238 @@
-// Copyright (c) 2012- PPSSPP Project / Dolphin Project.
-// Licensed under GPLv2 or any later version
+// Copyright 2008 Dolphin Emulator Project / 2017 Citra Emulator Project
+// Licensed under GPLv2+
 // Refer to the license.txt file included.
 
-#include <atomic>
+#include "core/core_timing.h"
+
+#include <algorithm>
 #include <cinttypes>
 #include <mutex>
+#include <string>
+#include <tuple>
+#include <unordered_map>
 #include <vector>
-#include "common/chunk_file.h"
+#include "common/assert.h"
 #include "common/logging/log.h"
-#include "common/string_util.h"
-#include "core/arm/arm_interface.h"
-#include "core/core.h"
-#include "core/core_timing.h"
-
-int g_clock_rate_arm11 = BASE_CLOCK_RATE;
-
-// is this really necessary?
-#define INITIAL_SLICE_LENGTH 20000
-#define MAX_SLICE_LENGTH 100000000
+#include "common/thread.h"
+#include "common/threadsafe_queue.h"
 
 namespace CoreTiming {
-struct EventType {
-    EventType() {}
 
-    EventType(TimedCallback cb, const char* n) : callback(cb), name(n) {}
+static s64 global_timer;
+static int slice_length;
+static int downcount;
 
+struct EventType {
     TimedCallback callback;
-    const char* name;
+    const std::string* name;
 };
 
-static std::vector<EventType> event_types;
-
-struct BaseEvent {
+struct Event {
     s64 time;
+    u64 fifo_order;
     u64 userdata;
-    int type;
+    const EventType* type;
 };
 
-typedef LinkedListItem<BaseEvent> Event;
-
-static Event* first;
-static Event* ts_first;
-static Event* ts_last;
-
-// event pools
-static Event* event_pool = nullptr;
-static Event* event_ts_pool = nullptr;
-static int allocated_ts_events = 0;
-// Optimization to skip MoveEvents when possible.
-static std::atomic<bool> has_ts_events(false);
-
-int g_slice_length;
-
-static s64 global_timer;
-static s64 idled_cycles;
-static s64 last_global_time_ticks;
-static s64 last_global_time_us;
-
-static s64 down_count = 0; ///< A decreasing counter of remaining cycles before the next event,
-                           /// decreased by the cpu run loop
-
-static std::recursive_mutex external_event_section;
-
-// Warning: not included in save state.
-using AdvanceCallback = void(int cycles_executed);
-static AdvanceCallback* advance_callback = nullptr;
-static std::vector<MHzChangeCallback> mhz_change_callbacks;
-
-static void FireMhzChange() {
-    for (auto callback : mhz_change_callbacks)
-        callback();
-}
-
-void SetClockFrequencyMHz(int cpu_mhz) {
-    // When the mhz changes, we keep track of what "time" it was before hand.
-    // This way, time always moves forward, even if mhz is changed.
-    last_global_time_us = GetGlobalTimeUs();
-    last_global_time_ticks = GetTicks();
-
-    g_clock_rate_arm11 = cpu_mhz * 1000000;
-    // TODO: Rescale times of scheduled events?
-
-    FireMhzChange();
-}
-
-int GetClockFrequencyMHz() {
-    return g_clock_rate_arm11 / 1000000;
+// Sort by time, unless the times are the same, in which case sort by the order added to the queue
+static bool operator>(const Event& left, const Event& right) {
+    return std::tie(left.time, left.fifo_order) > std::tie(right.time, right.fifo_order);
 }
 
-u64 GetGlobalTimeUs() {
-    s64 ticks_since_last = GetTicks() - last_global_time_ticks;
-    int freq = GetClockFrequencyMHz();
-    s64 us_since_last = ticks_since_last / freq;
-    return last_global_time_us + us_since_last;
+static bool operator<(const Event& left, const Event& right) {
+    return std::tie(left.time, left.fifo_order) < std::tie(right.time, right.fifo_order);
 }
 
-static Event* GetNewEvent() {
-    if (!event_pool)
-        return new Event;
-
-    Event* event = event_pool;
-    event_pool = event->next;
-    return event;
-}
+// unordered_map stores each element separately as a linked list node so pointers to elements
+// remain stable regardless of rehashes/resizing.
+static std::unordered_map<std::string, EventType> event_types;
 
-static Event* GetNewTsEvent() {
-    allocated_ts_events++;
+// The queue is a min-heap using std::make_heap/push_heap/pop_heap.
+// We don't use std::priority_queue because we need to be able to serialize, unserialize and
+// erase arbitrary events (RemoveEvent()) regardless of the queue order. These aren't accomodated
+// by the standard adaptor class.
+static std::vector<Event> event_queue;
+static u64 event_fifo_id;
+// the queue for storing the events from other threads threadsafe until they will be added
+// to the event_queue by the emu thread
+static Common::MPSCQueue<Event, false> ts_queue;
 
-    if (!event_ts_pool)
-        return new Event;
+static constexpr int MAX_SLICE_LENGTH = 20000;
 
-    Event* event = event_ts_pool;
-    event_ts_pool = event->next;
-    return event;
-}
-
-static void FreeEvent(Event* event) {
-    event->next = event_pool;
-    event_pool = event;
-}
+static s64 idled_cycles;
 
-static void FreeTsEvent(Event* event) {
-    event->next = event_ts_pool;
-    event_ts_pool = event;
-    allocated_ts_events--;
-}
+// Are we in a function that has been called from Advance()
+// If events are sheduled from a function that gets called from Advance(),
+// don't change slice_length and downcount.
+static bool is_global_timer_sane;
 
-int RegisterEvent(const char* name, TimedCallback callback) {
-    event_types.emplace_back(callback, name);
-    return (int)event_types.size() - 1;
-}
+static EventType* ev_lost = nullptr;
 
-static void AntiCrashCallback(u64 userdata, int cycles_late) {
-    LOG_CRITICAL(Core_Timing, "Savestate broken: an unregistered event was called.");
-}
+static void EmptyTimedCallback(u64 userdata, s64 cyclesLate) {}
 
-void RestoreRegisterEvent(int event_type, const char* name, TimedCallback callback) {
-    if (event_type >= (int)event_types.size())
-        event_types.resize(event_type + 1, EventType(AntiCrashCallback, "INVALID EVENT"));
+EventType* RegisterEvent(const std::string& name, TimedCallback callback) {
+    // check for existing type with same name.
+    // we want event type names to remain unique so that we can use them for serialization.
+    ASSERT_MSG(event_types.find(name) == event_types.end(),
+               "CoreTiming Event \"%s\" is already registered. Events should only be registered "
+               "during Init to avoid breaking save states.",
+               name.c_str());
 
-    event_types[event_type] = EventType(callback, name);
+    auto info = event_types.emplace(name, EventType{callback, nullptr});
+    EventType* event_type = &info.first->second;
+    event_type->name = &info.first->first;
+    return event_type;
 }
 
 void UnregisterAllEvents() {
-    if (first)
-        LOG_ERROR(Core_Timing, "Cannot unregister events with events pending");
+    ASSERT_MSG(event_queue.empty(), "Cannot unregister events with events pending");
     event_types.clear();
 }
 
 void Init() {
-    down_count = INITIAL_SLICE_LENGTH;
-    g_slice_length = INITIAL_SLICE_LENGTH;
+    downcount = MAX_SLICE_LENGTH;
+    slice_length = MAX_SLICE_LENGTH;
     global_timer = 0;
     idled_cycles = 0;
-    last_global_time_ticks = 0;
-    last_global_time_us = 0;
-    has_ts_events = 0;
-    mhz_change_callbacks.clear();
-
-    first = nullptr;
-    ts_first = nullptr;
-    ts_last = nullptr;
 
-    event_pool = nullptr;
-    event_ts_pool = nullptr;
-    allocated_ts_events = 0;
+    // The time between CoreTiming being intialized and the first call to Advance() is considered
+    // the slice boundary between slice -1 and slice 0. Dispatcher loops must call Advance() before
+    // executing the first cycle of each slice to prepare the slice length and downcount for
+    // that slice.
+    is_global_timer_sane = true;
 
-    advance_callback = nullptr;
+    event_fifo_id = 0;
+    ev_lost = RegisterEvent("_lost_event", &EmptyTimedCallback);
 }
 
 void Shutdown() {
     MoveEvents();
     ClearPendingEvents();
     UnregisterAllEvents();
-
-    while (event_pool) {
-        Event* event = event_pool;
-        event_pool = event->next;
-        delete event;
-    }
-
-    std::lock_guard<std::recursive_mutex> lock(external_event_section);
-    while (event_ts_pool) {
-        Event* event = event_ts_pool;
-        event_ts_pool = event->next;
-        delete event;
-    }
 }
 
-void AddTicks(u64 ticks) {
-    down_count -= ticks;
-    if (down_count < 0) {
-        Advance();
+// This should only be called from the CPU thread. If you are calling
+// it from any other thread, you are doing something evil
+u64 GetTicks() {
+    u64 ticks = static_cast<u64>(global_timer);
+    if (!is_global_timer_sane) {
+        ticks += slice_length - downcount;
     }
+    return ticks;
 }
 
-u64 GetTicks() {
-    return (u64)global_timer + g_slice_length - down_count;
+void AddTicks(u64 ticks) {
+    downcount -= ticks;
 }
 
 u64 GetIdleTicks() {
-    return (u64)idled_cycles;
-}
-
-// This is to be called when outside threads, such as the graphics thread, wants to
-// schedule things to be executed on the main thread.
-void ScheduleEvent_Threadsafe(s64 cycles_into_future, int event_type, u64 userdata) {
-    std::lock_guard<std::recursive_mutex> lock(external_event_section);
-    Event* new_event = GetNewTsEvent();
-    new_event->time = GetTicks() + cycles_into_future;
-    new_event->type = event_type;
-    new_event->next = nullptr;
-    new_event->userdata = userdata;
-    if (!ts_first)
-        ts_first = new_event;
-    if (ts_last)
-        ts_last->next = new_event;
-    ts_last = new_event;
-
-    has_ts_events = true;
-}
-
-// Same as ScheduleEvent_Threadsafe(0, ...) EXCEPT if we are already on the CPU thread
-// in which case the event will get handled immediately, before returning.
-void ScheduleEvent_Threadsafe_Immediate(int event_type, u64 userdata) {
-    if (false) // Core::IsCPUThread())
-    {
-        std::lock_guard<std::recursive_mutex> lock(external_event_section);
-        event_types[event_type].callback(userdata, 0);
-    } else
-        ScheduleEvent_Threadsafe(0, event_type, userdata);
+    return static_cast<u64>(idled_cycles);
 }
 
 void ClearPendingEvents() {
-    while (first) {
-        Event* event = first->next;
-        FreeEvent(first);
-        first = event;
-    }
-}
-
-static void AddEventToQueue(Event* new_event) {
-    Event* prev_event = nullptr;
-    Event** next_event = &first;
-    for (;;) {
-        Event*& next = *next_event;
-        if (!next || new_event->time < next->time) {
-            new_event->next = next;
-            next = new_event;
-            break;
-        }
-        prev_event = next;
-        next_event = &prev_event->next;
-    }
-}
-
-void ScheduleEvent(s64 cycles_into_future, int event_type, u64 userdata) {
-    Event* new_event = GetNewEvent();
-    new_event->userdata = userdata;
-    new_event->type = event_type;
-    new_event->time = GetTicks() + cycles_into_future;
-    AddEventToQueue(new_event);
-}
-
-s64 UnscheduleEvent(int event_type, u64 userdata) {
-    s64 result = 0;
-    if (!first)
-        return result;
-    while (first) {
-        if (first->type == event_type && first->userdata == userdata) {
-            result = first->time - GetTicks();
-
-            Event* next = first->next;
-            FreeEvent(first);
-            first = next;
-        } else {
-            break;
-        }
-    }
-    if (!first)
-        return result;
-
-    Event* prev_event = first;
-    Event* ptr = prev_event->next;
-
-    while (ptr) {
-        if (ptr->type == event_type && ptr->userdata == userdata) {
-            result = ptr->time - GetTicks();
-
-            prev_event->next = ptr->next;
-            FreeEvent(ptr);
-            ptr = prev_event->next;
-        } else {
-            prev_event = ptr;
-            ptr = ptr->next;
-        }
-    }
-
-    return result;
+    event_queue.clear();
 }
 
-s64 UnscheduleThreadsafeEvent(int event_type, u64 userdata) {
-    s64 result = 0;
-    std::lock_guard<std::recursive_mutex> lock(external_event_section);
-    if (!ts_first)
-        return result;
-
-    while (ts_first) {
-        if (ts_first->type == event_type && ts_first->userdata == userdata) {
-            result = ts_first->time - GetTicks();
-
-            Event* next = ts_first->next;
-            FreeTsEvent(ts_first);
-            ts_first = next;
-        } else {
-            break;
-        }
-    }
+void ScheduleEvent(s64 cycles_into_future, const EventType* event_type, u64 userdata) {
+    ASSERT(event_type != nullptr);
+    s64 timeout = GetTicks() + cycles_into_future;
 
-    if (!ts_first) {
-        ts_last = nullptr;
-        return result;
-    }
+    // If this event needs to be scheduled before the next advance(), force one early
+    if (!is_global_timer_sane)
+        ForceExceptionCheck(cycles_into_future);
 
-    Event* prev_event = ts_first;
-    Event* next = prev_event->next;
-    while (next) {
-        if (next->type == event_type && next->userdata == userdata) {
-            result = next->time - GetTicks();
-
-            prev_event->next = next->next;
-            if (next == ts_last)
-                ts_last = prev_event;
-            FreeTsEvent(next);
-            next = prev_event->next;
-        } else {
-            prev_event = next;
-            next = next->next;
-        }
-    }
-
-    return result;
+    event_queue.emplace_back(Event{timeout, event_fifo_id++, userdata, event_type});
+    std::push_heap(event_queue.begin(), event_queue.end(), std::greater<Event>());
 }
 
-// Warning: not included in save state.
-void RegisterAdvanceCallback(AdvanceCallback* callback) {
-    advance_callback = callback;
+void ScheduleEventThreadsafe(s64 cycles_into_future, const EventType* event_type, u64 userdata) {
+    ts_queue.Push(Event{global_timer + cycles_into_future, 0, userdata, event_type});
 }
 
-void RegisterMHzChangeCallback(MHzChangeCallback callback) {
-    mhz_change_callbacks.push_back(callback);
-}
-
-bool IsScheduled(int event_type) {
-    if (!first)
-        return false;
-    Event* event = first;
-    while (event) {
-        if (event->type == event_type)
-            return true;
-        event = event->next;
-    }
-    return false;
-}
+void UnscheduleEvent(const EventType* event_type, u64 userdata) {
+    auto itr = std::remove_if(event_queue.begin(), event_queue.end(), [&](const Event& e) {
+        return e.type == event_type && e.userdata == userdata;
+    });
 
-void RemoveEvent(int event_type) {
-    if (!first)
-        return;
-    while (first) {
-        if (first->type == event_type) {
-            Event* next = first->next;
-            FreeEvent(first);
-            first = next;
-        } else {
-            break;
-        }
-    }
-    if (!first)
-        return;
-    Event* prev = first;
-    Event* next = prev->next;
-    while (next) {
-        if (next->type == event_type) {
-            prev->next = next->next;
-            FreeEvent(next);
-            next = prev->next;
-        } else {
-            prev = next;
-            next = next->next;
-        }
+    // Removing random items breaks the invariant so we have to re-establish it.
+    if (itr != event_queue.end()) {
+        event_queue.erase(itr, event_queue.end());
+        std::make_heap(event_queue.begin(), event_queue.end(), std::greater<Event>());
     }
 }
 
-void RemoveThreadsafeEvent(int event_type) {
-    std::lock_guard<std::recursive_mutex> lock(external_event_section);
-    if (!ts_first)
-        return;
-
-    while (ts_first) {
-        if (ts_first->type == event_type) {
-            Event* next = ts_first->next;
-            FreeTsEvent(ts_first);
-            ts_first = next;
-        } else {
-            break;
-        }
-    }
-
-    if (!ts_first) {
-        ts_last = nullptr;
-        return;
-    }
+void RemoveEvent(const EventType* event_type) {
+    auto itr = std::remove_if(event_queue.begin(), event_queue.end(),
+                              [&](const Event& e) { return e.type == event_type; });
 
-    Event* prev = ts_first;
-    Event* next = prev->next;
-    while (next) {
-        if (next->type == event_type) {
-            prev->next = next->next;
-            if (next == ts_last)
-                ts_last = prev;
-            FreeTsEvent(next);
-            next = prev->next;
-        } else {
-            prev = next;
-            next = next->next;
-        }
+    // Removing random items breaks the invariant so we have to re-establish it.
+    if (itr != event_queue.end()) {
+        event_queue.erase(itr, event_queue.end());
+        std::make_heap(event_queue.begin(), event_queue.end(), std::greater<Event>());
     }
 }
 
-void RemoveAllEvents(int event_type) {
-    RemoveThreadsafeEvent(event_type);
+void RemoveNormalAndThreadsafeEvent(const EventType* event_type) {
+    MoveEvents();
     RemoveEvent(event_type);
 }
 
-// This raise only the events required while the fifo is processing data
-void ProcessFifoWaitEvents() {
-    while (first) {
-        if (first->time <= (s64)GetTicks()) {
-            Event* evt = first;
-            first = first->next;
-            event_types[evt->type].callback(evt->userdata, (int)(GetTicks() - evt->time));
-            FreeEvent(evt);
-        } else {
-            break;
-        }
+void ForceExceptionCheck(s64 cycles) {
+    cycles = std::max<s64>(0, cycles);
+    if (downcount > cycles) {
+        // downcount is always (much) smaller than MAX_INT so we can safely cast cycles to an int
+        // here. Account for cycles already executed by adjusting the g.slice_length
+        slice_length -= downcount - static_cast<int>(cycles);
+        downcount = static_cast<int>(cycles);
     }
 }
 
 void MoveEvents() {
-    has_ts_events = false;
-
-    std::lock_guard<std::recursive_mutex> lock(external_event_section);
-    // Move events from async queue into main queue
-    while (ts_first) {
-        Event* next = ts_first->next;
-        AddEventToQueue(ts_first);
-        ts_first = next;
-    }
-    ts_last = nullptr;
-
-    // Move free events to threadsafe pool
-    while (allocated_ts_events > 0 && event_pool) {
-        Event* event = event_pool;
-        event_pool = event->next;
-        event->next = event_ts_pool;
-        event_ts_pool = event;
-        allocated_ts_events--;
+    for (Event ev; ts_queue.Pop(ev);) {
+        ev.fifo_order = event_fifo_id++;
+        event_queue.emplace_back(std::move(ev));
+        std::push_heap(event_queue.begin(), event_queue.end(), std::greater<Event>());
     }
 }
 
-void ForceCheck() {
-    s64 cycles_executed = g_slice_length - down_count;
-    global_timer += cycles_executed;
-    // This will cause us to check for new events immediately.
-    down_count = 0;
-    // But let's not eat a bunch more time in Advance() because of this.
-    g_slice_length = 0;
-}
-
 void Advance() {
-    s64 cycles_executed = g_slice_length - down_count;
+    MoveEvents();
+
+    int cycles_executed = slice_length - downcount;
     global_timer += cycles_executed;
-    down_count = g_slice_length;
-
-    if (has_ts_events)
-        MoveEvents();
-    ProcessFifoWaitEvents();
-
-    if (!first) {
-        if (g_slice_length < 10000) {
-            g_slice_length += 10000;
-            down_count += g_slice_length;
-        }
-    } else {
-        // Note that events can eat cycles as well.
-        int target = (int)(first->time - global_timer);
-        if (target > MAX_SLICE_LENGTH)
-            target = MAX_SLICE_LENGTH;
-
-        const int diff = target - g_slice_length;
-        g_slice_length += diff;
-        down_count += diff;
-    }
-    if (advance_callback)
-        advance_callback(static_cast<int>(cycles_executed));
-}
+    slice_length = MAX_SLICE_LENGTH;
 
-void LogPendingEvents() {
-    Event* event = first;
-    while (event) {
-        // LOG_TRACE(Core_Timing, "PENDING: Now: %lld Pending: %lld Type: %d", globalTimer,
-        // next->time, next->type);
-        event = event->next;
+    is_global_timer_sane = true;
+
+    while (!event_queue.empty() && event_queue.front().time <= global_timer) {
+        Event evt = std::move(event_queue.front());
+        std::pop_heap(event_queue.begin(), event_queue.end(), std::greater<Event>());
+        event_queue.pop_back();
+        evt.type->callback(evt.userdata, global_timer - evt.time);
     }
-}
 
-void Idle(int max_idle) {
-    s64 cycles_down = down_count;
-    if (max_idle != 0 && cycles_down > max_idle)
-        cycles_down = max_idle;
-
-    if (first && cycles_down > 0) {
-        s64 cycles_executed = g_slice_length - down_count;
-        s64 cycles_next_event = first->time - global_timer;
-
-        if (cycles_next_event < cycles_executed + cycles_down) {
-            cycles_down = cycles_next_event - cycles_executed;
-            // Now, now... no time machines, please.
-            if (cycles_down < 0)
-                cycles_down = 0;
-        }
+    is_global_timer_sane = false;
+
+    // Still events left (scheduled in the future)
+    if (!event_queue.empty()) {
+        slice_length = static_cast<int>(
+            std::min<s64>(event_queue.front().time - global_timer, MAX_SLICE_LENGTH));
     }
 
-    LOG_TRACE(Core_Timing, "Idle for %" PRId64 " cycles! (%f ms)", cycles_down,
-              cycles_down / (float)(g_clock_rate_arm11 * 0.001f));
+    downcount = slice_length;
+}
 
-    idled_cycles += cycles_down;
-    down_count -= cycles_down;
-    if (down_count == 0)
-        down_count = -1;
+void Idle() {
+    idled_cycles += downcount;
+    downcount = 0;
 }
 
-std::string GetScheduledEventsSummary() {
-    Event* event = first;
-    std::string text = "Scheduled events\n";
-    text.reserve(1000);
-    while (event) {
-        unsigned int t = event->type;
-        if (t >= event_types.size())
-            LOG_ERROR(Core_Timing, "Invalid event type"); // %i", t);
-        const char* name = event_types[event->type].name;
-        if (!name)
-            name = "[unknown]";
-        text += Common::StringFromFormat("%s : %i %08x%08x\n", name, (int)event->time,
-                                         (u32)(event->userdata >> 32), (u32)(event->userdata));
-        event = event->next;
-    }
-    return text;
+u64 GetGlobalTimeUs() {
+    return GetTicks() * 1000000 / BASE_CLOCK_RATE;
+}
+
+int GetDowncount() {
+    return downcount;
 }
 
-} // namespace
+} // namespace CoreTiming
-- 
cgit v1.2.3