Profiler: Use sequential serial numbers for profiling events

Previously Profiler was using timestamps to distinguish processes.
However it is possible that separate processes with the same PID exist
at the exact same timestamp (e.g. for execve). This changes Profiler
to use unique serial numbers for each event instead.

8 files changed, 125 insertions, 47 deletions

diff --git a/Userland/DevTools/Profiler/EventSerialNumber.h b/Userland/DevTools/Profiler/EventSerialNumber.h
new file mode 100644
index 0000000000..a1934c5b33
--- /dev/null
+++ b/Userland/DevTools/Profiler/EventSerialNumber.h
@@ -0,0 +1,70 @@
+/*
+ * Copyright (c) 2021, Gunnar Beutner <gbeutner@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/Assertions.h>
+#include <AK/NumericLimits.h>
+#include <AK/Types.h>
+
+namespace Profiler {
+
+// DistinctNumeric's constructor is non-explicit which makes accidentally turning
+// an unrelated u64 into a serial number all too easy.
+class EventSerialNumber {
+public:
+    constexpr EventSerialNumber() = default;
+
+    void increment()
+    {
+        m_serial++;
+    }
+
+    size_t to_number() const
+    {
+        return m_serial;
+    }
+
+    static EventSerialNumber max_valid_serial()
+    {
+        return EventSerialNumber { NumericLimits<size_t>::max() };
+    }
+
+    bool operator==(EventSerialNumber const& rhs) const
+    {
+        return m_serial == rhs.m_serial;
+    }
+
+    bool operator<(EventSerialNumber const& rhs) const
+    {
+        return m_serial < rhs.m_serial;
+    }
+
+    bool operator>(EventSerialNumber const& rhs) const
+    {
+        return m_serial > rhs.m_serial;
+    }
+
+    bool operator<=(EventSerialNumber const& rhs) const
+    {
+        return m_serial <= rhs.m_serial;
+    }
+
+    bool operator>=(EventSerialNumber const& rhs) const
+    {
+        return m_serial >= rhs.m_serial;
+    }
+
+private:
+    size_t m_serial { 0 };
+
+    constexpr explicit EventSerialNumber(size_t serial)
+        : m_serial(serial)
+    {
+    }
+};
+
+}
diff --git a/Userland/DevTools/Profiler/Process.cpp b/Userland/DevTools/Profiler/Process.cpp
index 9eee7d6489..1fbbddd5ec 100644
--- a/Userland/DevTools/Profiler/Process.cpp
+++ b/Userland/DevTools/Profiler/Process.cpp
@@ -8,19 +8,19 @@
 
 namespace Profiler {
 
-Thread* Process::find_thread(pid_t tid, u64 timestamp)
+Thread* Process::find_thread(pid_t tid, EventSerialNumber serial)
 {
     auto it = threads.find(tid);
     if (it == threads.end())
         return nullptr;
     for (auto& thread : it->value) {
-        if (thread.start_valid < timestamp && (thread.end_valid == 0 || thread.end_valid > timestamp))
+        if (thread.start_valid < serial && (thread.end_valid == EventSerialNumber {} || thread.end_valid > serial))
             return &thread;
     }
     return nullptr;
 }
 
-void Process::handle_thread_create(pid_t tid, u64 timestamp)
+void Process::handle_thread_create(pid_t tid, EventSerialNumber serial)
 {
     auto it = threads.find(tid);
     if (it == threads.end()) {
@@ -28,16 +28,16 @@ void Process::handle_thread_create(pid_t tid, u64 timestamp)
         it = threads.find(tid);
     }
 
-    auto thread = Thread { tid, timestamp, 0 };
+    auto thread = Thread { tid, serial, {} };
     it->value.append(move(thread));
 }
 
-void Process::handle_thread_exit(pid_t tid, u64 timestamp)
+void Process::handle_thread_exit(pid_t tid, EventSerialNumber serial)
 {
-    auto* thread = find_thread(tid, timestamp);
+    auto* thread = find_thread(tid, serial);
     if (!thread)
         return;
-    thread->end_valid = timestamp;
+    thread->end_valid = serial;
 }
 
 HashMap<String, OwnPtr<MappedObject>> g_mapped_object_cache;
diff --git a/Userland/DevTools/Profiler/Process.h b/Userland/DevTools/Profiler/Process.h
index aec50c6142..2bc1875873 100644
--- a/Userland/DevTools/Profiler/Process.h
+++ b/Userland/DevTools/Profiler/Process.h
@@ -6,6 +6,7 @@
 
 #pragma once
 
+#include "EventSerialNumber.h"
 #include <AK/HashMap.h>
 #include <AK/MappedFile.h>
 #include <AK/OwnPtr.h>
@@ -42,12 +43,12 @@ private:
 
 struct Thread {
     pid_t tid;
-    u64 start_valid;
-    u64 end_valid { 0 };
+    EventSerialNumber start_valid;
+    EventSerialNumber end_valid;
 
-    bool valid_at(u64 timestamp) const
+    bool valid_at(EventSerialNumber serial) const
     {
-        return timestamp >= start_valid && (end_valid == 0 || timestamp <= end_valid);
+        return serial >= start_valid && (end_valid == EventSerialNumber {} || serial <= end_valid);
     }
 };
 
@@ -57,16 +58,16 @@ struct Process {
     String basename;
     HashMap<int, Vector<Thread>> threads {};
     LibraryMetadata library_metadata {};
-    u64 start_valid;
-    u64 end_valid { 0 };
+    EventSerialNumber start_valid;
+    EventSerialNumber end_valid;
 
-    Thread* find_thread(pid_t tid, u64 timestamp);
-    void handle_thread_create(pid_t tid, u64 timestamp);
-    void handle_thread_exit(pid_t tid, u64 timestamp);
+    Thread* find_thread(pid_t tid, EventSerialNumber serial);
+    void handle_thread_create(pid_t tid, EventSerialNumber serial);
+    void handle_thread_exit(pid_t tid, EventSerialNumber serial);
 
-    bool valid_at(u64 timestamp) const
+    bool valid_at(EventSerialNumber serial) const
     {
-        return timestamp >= start_valid && (end_valid == 0 || timestamp <= end_valid);
+        return serial >= start_valid && (end_valid == EventSerialNumber {} || serial <= end_valid);
     }
 };
 
diff --git a/Userland/DevTools/Profiler/Profile.cpp b/Userland/DevTools/Profiler/Profile.cpp
index fb46b33862..f169713a0b 100644
--- a/Userland/DevTools/Profiler/Profile.cpp
+++ b/Userland/DevTools/Profiler/Profile.cpp
@@ -61,10 +61,10 @@ void Profile::rebuild_tree()
 {
     Vector<NonnullRefPtr<ProfileNode>> roots;
 
-    auto find_or_create_process_node = [this, &roots](pid_t pid, u64 timestamp) -> ProfileNode& {
-        auto* process = find_process(pid, timestamp);
+    auto find_or_create_process_node = [this, &roots](pid_t pid, EventSerialNumber serial) -> ProfileNode& {
+        auto* process = find_process(pid, serial);
         if (!process) {
-            dbgln("Profile contains event for unknown process with pid={}, timestamp={}", pid, timestamp);
+            dbgln("Profile contains event for unknown process with pid={}, serial={}", pid, serial.to_number());
             VERIFY_NOT_REACHED();
         }
         for (auto root : roots) {
@@ -96,7 +96,7 @@ void Profile::rebuild_tree()
                 continue;
         }
 
-        if (!process_filter_contains(event.pid, event.timestamp))
+        if (!process_filter_contains(event.pid, event.serial))
             continue;
 
         m_filtered_event_indices.append(event_index);
@@ -123,7 +123,7 @@ void Profile::rebuild_tree()
 
         if (!m_show_top_functions) {
             ProfileNode* node = nullptr;
-            auto& process_node = find_or_create_process_node(event.pid, event.timestamp);
+            auto& process_node = find_or_create_process_node(event.pid, event.serial);
             process_node.increment_event_count();
             for_each_frame([&](const Frame& frame, bool is_innermost_frame) {
                 auto& object_name = frame.object_name;
@@ -147,7 +147,7 @@ void Profile::rebuild_tree()
                 return IterationDecision::Continue;
             });
         } else {
-            auto& process_node = find_or_create_process_node(event.pid, event.timestamp);
+            auto& process_node = find_or_create_process_node(event.pid, event.serial);
             process_node.increment_event_count();
             for (size_t i = 0; i < event.frames.size(); ++i) {
                 ProfileNode* node = nullptr;
@@ -163,7 +163,7 @@ void Profile::rebuild_tree()
 
                     // FIXME: More PID/TID mixing cheats here:
                     if (!node) {
-                        node = &find_or_create_process_node(event.pid, event.timestamp);
+                        node = &find_or_create_process_node(event.pid, event.serial);
                         node = &node->find_or_create_child(object_name, symbol, address, offset, event.timestamp, event.pid);
                         root = node;
                         root->will_track_seen_events(m_events.size());
@@ -219,12 +219,15 @@ Result<NonnullOwnPtr<Profile>, String> Profile::load_from_perfcore_file(const St
     NonnullOwnPtrVector<Process> all_processes;
     HashMap<pid_t, Process*> current_processes;
     Vector<Event> events;
+    EventSerialNumber next_serial;
 
     for (auto& perf_event_value : perf_events.values()) {
         auto& perf_event = perf_event_value.as_object();
 
         Event event;
 
+        event.serial = next_serial;
+        next_serial.increment();
         event.timestamp = perf_event.get("timestamp").to_number<u64>();
         event.lost_samples = perf_event.get("lost_samples").to_number<u32>();
         event.type = perf_event.get("type").to_string();
@@ -257,7 +260,8 @@ Result<NonnullOwnPtr<Profile>, String> Profile::load_from_perfcore_file(const St
                 .pid = event.pid,
                 .executable = event.executable,
                 .basename = LexicalPath(event.executable).basename(),
-                .start_valid = event.timestamp,
+                .start_valid = event.serial,
+                .end_valid = {},
             });
 
             current_processes.set(sampled_process->pid, sampled_process);
@@ -267,7 +271,7 @@ Result<NonnullOwnPtr<Profile>, String> Profile::load_from_perfcore_file(const St
             event.executable = perf_event.get("executable").to_string();
 
             auto old_process = current_processes.get(event.pid).value();
-            old_process->end_valid = event.timestamp;
+            old_process->end_valid = event.serial;
 
             current_processes.remove(event.pid);
 
@@ -275,14 +279,16 @@ Result<NonnullOwnPtr<Profile>, String> Profile::load_from_perfcore_file(const St
                 .pid = event.pid,
                 .executable = event.executable,
                 .basename = LexicalPath(event.executable).basename(),
-                .start_valid = event.timestamp });
+                .start_valid = event.serial,
+                .end_valid = {},
+            });
 
             current_processes.set(sampled_process->pid, sampled_process);
             all_processes.append(move(sampled_process));
             continue;
         } else if (event.type == "process_exit"sv) {
             auto old_process = current_processes.get(event.pid).value();
-            old_process->end_valid = event.timestamp;
+            old_process->end_valid = event.serial;
 
             current_processes.remove(event.pid);
             continue;
@@ -290,12 +296,12 @@ Result<NonnullOwnPtr<Profile>, String> Profile::load_from_perfcore_file(const St
             event.parent_tid = perf_event.get("parent_tid").to_i32();
             auto it = current_processes.find(event.pid);
             if (it != current_processes.end())
-                it->value->handle_thread_create(event.tid, event.timestamp);
+                it->value->handle_thread_create(event.tid, event.serial);
             continue;
         } else if (event.type == "thread_exit"sv) {
             auto it = current_processes.find(event.pid);
             if (it != current_processes.end())
-                it->value->handle_thread_exit(event.tid, event.timestamp);
+                it->value->handle_thread_exit(event.tid, event.serial);
             continue;
         }
 
@@ -385,7 +391,7 @@ void Profile::clear_timestamp_filter_range()
     m_samples_model->update();
 }
 
-void Profile::add_process_filter(pid_t pid, u64 start_valid, u64 end_valid)
+void Profile::add_process_filter(pid_t pid, EventSerialNumber start_valid, EventSerialNumber end_valid)
 {
     auto filter = ProcessFilter { pid, start_valid, end_valid };
     if (m_process_filters.contains_slow(filter))
@@ -398,7 +404,7 @@ void Profile::add_process_filter(pid_t pid, u64 start_valid, u64 end_valid)
     m_samples_model->update();
 }
 
-void Profile::remove_process_filter(pid_t pid, u64 start_valid, u64 end_valid)
+void Profile::remove_process_filter(pid_t pid, EventSerialNumber start_valid, EventSerialNumber end_valid)
 {
     auto filter = ProcessFilter { pid, start_valid, end_valid };
     if (!m_process_filters.contains_slow(filter))
@@ -424,13 +430,13 @@ void Profile::clear_process_filter()
     m_samples_model->update();
 }
 
-bool Profile::process_filter_contains(pid_t pid, u32 timestamp)
+bool Profile::process_filter_contains(pid_t pid, EventSerialNumber serial)
 {
     if (!has_process_filter())
         return true;
 
     for (auto const& process_filter : m_process_filters)
-        if (pid == process_filter.pid && timestamp >= process_filter.start_valid && timestamp <= process_filter.end_valid)
+        if (pid == process_filter.pid && serial >= process_filter.start_valid && serial <= process_filter.end_valid)
             return true;
 
     return false;
diff --git a/Userland/DevTools/Profiler/Profile.h b/Userland/DevTools/Profiler/Profile.h
index e25fe3ea29..7ec6e36455 100644
--- a/Userland/DevTools/Profiler/Profile.h
+++ b/Userland/DevTools/Profiler/Profile.h
@@ -126,8 +126,8 @@ private:
 
 struct ProcessFilter {
     pid_t pid { 0 };
-    u64 start_valid { 0 };
-    u64 end_valid { 0 };
+    EventSerialNumber start_valid;
+    EventSerialNumber end_valid;
 
     bool operator==(ProcessFilter const& rhs) const
     {
@@ -143,10 +143,10 @@ public:
     GUI::Model& samples_model();
     GUI::Model* disassembly_model();
 
-    const Process* find_process(pid_t pid, u64 timestamp) const
+    const Process* find_process(pid_t pid, EventSerialNumber serial) const
     {
-        auto it = m_processes.find_if([&](auto& entry) {
-            return entry.pid == pid && entry.valid_at(timestamp);
+        auto it = m_processes.find_if([&pid, &serial](auto& entry) {
+            return entry.pid == pid && entry.valid_at(serial);
         });
         return it.is_end() ? nullptr : &(*it);
     }
@@ -163,6 +163,7 @@ public:
     };
 
     struct Event {
+        EventSerialNumber serial;
         u64 timestamp { 0 };
         String type;
         FlatPtr ptr { 0 };
@@ -190,11 +191,11 @@ public:
     void clear_timestamp_filter_range();
     bool has_timestamp_filter_range() const { return m_has_timestamp_filter_range; }
 
-    void add_process_filter(pid_t pid, u64 start_valid, u64 end_valid);
-    void remove_process_filter(pid_t pid, u64 start_valid, u64 end_valid);
+    void add_process_filter(pid_t pid, EventSerialNumber start_valid, EventSerialNumber end_valid);
+    void remove_process_filter(pid_t pid, EventSerialNumber start_valid, EventSerialNumber end_valid);
     void clear_process_filter();
     bool has_process_filter() const { return !m_process_filters.is_empty(); }
-    bool process_filter_contains(pid_t pid, u32 timestamp);
+    bool process_filter_contains(pid_t pid, EventSerialNumber serial);
 
     bool is_inverted() const { return m_inverted; }
     void set_inverted(bool);
diff --git a/Userland/DevTools/Profiler/SamplesModel.cpp b/Userland/DevTools/Profiler/SamplesModel.cpp
index af23693c70..dddb54b22c 100644
--- a/Userland/DevTools/Profiler/SamplesModel.cpp
+++ b/Userland/DevTools/Profiler/SamplesModel.cpp
@@ -74,7 +74,7 @@ GUI::Variant SamplesModel::data(const GUI::ModelIndex& index, GUI::ModelRole rol
             return event.tid;
 
         if (index.column() == Column::ExecutableName) {
-            if (auto* process = m_profile.find_process(event.pid, event.timestamp))
+            if (auto* process = m_profile.find_process(event.pid, event.serial))
                 return process->executable;
             return "";
         }
diff --git a/Userland/DevTools/Profiler/TimelineTrack.cpp b/Userland/DevTools/Profiler/TimelineTrack.cpp
index f19a6c91e5..1ccdc5e89c 100644
--- a/Userland/DevTools/Profiler/TimelineTrack.cpp
+++ b/Userland/DevTools/Profiler/TimelineTrack.cpp
@@ -73,7 +73,7 @@ void TimelineTrack::paint_event(GUI::PaintEvent& event)
         if (event.pid != m_process.pid)
             continue;
 
-        if (!m_process.valid_at(event.timestamp))
+        if (!m_process.valid_at(event.serial))
             continue;
 
         auto& histogram = event.in_kernel ? kernel_histogram : usermode_histogram;
diff --git a/Userland/DevTools/Profiler/main.cpp b/Userland/DevTools/Profiler/main.cpp
index 144547d03a..0633e6e0c3 100644
--- a/Userland/DevTools/Profiler/main.cpp
+++ b/Userland/DevTools/Profiler/main.cpp
@@ -100,7 +100,7 @@ int main(int argc, char** argv)
     for (auto& process : profile->processes()) {
         bool matching_event_found = false;
         for (auto& event : profile->events()) {
-            if (event.pid == process.pid && process.valid_at(event.timestamp)) {
+            if (event.pid == process.pid && process.valid_at(event.serial)) {
                 matching_event_found = true;
                 break;
             }
@@ -110,7 +110,7 @@ int main(int argc, char** argv)
         auto& timeline_header = timeline_header_container->add<TimelineHeader>(*profile, process);
         timeline_header.set_shrink_to_fit(true);
         timeline_header.on_selection_change = [&](bool selected) {
-            auto end_valid = process.end_valid == 0 ? profile->last_timestamp() : process.end_valid;
+            auto end_valid = process.end_valid == EventSerialNumber {} ? EventSerialNumber::max_valid_serial() : process.end_valid;
             if (selected)
                 profile->add_process_filter(process.pid, process.start_valid, end_valid);
             else