Simpleperf: adjust sort strategy in RecordCache.

In order to report correctly, We should keep the order of self created
records when reading perf.data. So adjust sort strategy in RecordCache
to avoid reordering it.

Bug: 26214604
Change-Id: I40812ee5f4f6051103d40459edf4b4a2d7a80313

4 files changed, 58 insertions, 20 deletions

diff --git a/simpleperf/cmd_dumprecord.cpp b/simpleperf/cmd_dumprecord.cpp
index 438f1e4f..c6af5528 100644
--- a/simpleperf/cmd_dumprecord.cpp
+++ b/simpleperf/cmd_dumprecord.cpp
@@ -179,7 +179,7 @@ void DumpRecordCommand::DumpDataSection() {
   record_file_reader_->ReadDataSection([](std::unique_ptr<Record> record) {
     record->Dump();
     return true;
-  });
+  }, false);
 }
 
 void DumpRecordCommand::DumpFeatureSection() {
diff --git a/simpleperf/record.cpp b/simpleperf/record.cpp
index c8735e5b..5f853a4a 100644
--- a/simpleperf/record.cpp
+++ b/simpleperf/record.cpp
@@ -674,26 +674,27 @@ BuildIdRecord CreateBuildIdRecord(bool in_kernel, pid_t pid, const BuildId& buil
   return record;
 }
 
-bool IsRecordHappensBefore(const Record* r1, const Record* r2) {
-  bool is_r1_sample = (r1->header.type == PERF_RECORD_SAMPLE);
-  bool is_r2_sample = (r2->header.type == PERF_RECORD_SAMPLE);
-  uint64_t time1 = r1->Timestamp();
-  uint64_t time2 = r2->Timestamp();
+bool RecordCache::RecordWithSeq::IsHappensBefore(const RecordWithSeq& other) const {
+  bool is_sample = (record->header.type == PERF_RECORD_SAMPLE);
+  bool is_other_sample = (other.record->header.type == PERF_RECORD_SAMPLE);
+  uint64_t time = record->Timestamp();
+  uint64_t other_time = other.record->Timestamp();
   // The record with smaller time happens first.
-  if (time1 != time2) {
-    return time1 < time2;
+  if (time != other_time) {
+    return time < other_time;
   }
   // If happening at the same time, make non-sample records before sample records,
   // because non-sample records may contain useful information to parse sample records.
-  if (is_r1_sample != is_r2_sample) {
-    return is_r1_sample ? false : true;
+  if (is_sample != is_other_sample) {
+    return is_sample ? false : true;
   }
-  // Otherwise, don't care of the order.
-  return false;
+  // Otherwise, use the same order as they enter the cache.
+  return seq < other.seq;
 }
 
-bool RecordCache::RecordComparator::operator()(const Record* r1, const Record* r2) {
-  return !IsRecordHappensBefore(r1, r2);
+bool RecordCache::RecordComparator::operator()(const RecordWithSeq& r1,
+                                               const RecordWithSeq& r2) {
+  return r2.IsHappensBefore(r1);
 }
 
 RecordCache::RecordCache(const perf_event_attr& attr, size_t min_cache_size,
@@ -703,6 +704,7 @@ RecordCache::RecordCache(const perf_event_attr& attr, size_t min_cache_size,
       min_cache_size_(min_cache_size),
       min_time_diff_in_ns_(min_time_diff_in_ns),
       last_time_(0),
+      cur_seq_(0),
       queue_(RecordComparator()) {
 }
 
@@ -718,19 +720,19 @@ void RecordCache::Push(const char* data, size_t size) {
     }
   }
   for (auto& r : records) {
-    queue_.push(r.release());
+    queue_.push(CreateRecordWithSeq(r.release()));
   }
 }
 
 void RecordCache::Push(std::unique_ptr<Record> record) {
-  queue_.push(record.release());
+  queue_.push(CreateRecordWithSeq(record.release()));
 }
 
 std::unique_ptr<Record> RecordCache::Pop() {
   if (queue_.size() < min_cache_size_) {
     return nullptr;
   }
-  Record* r = queue_.top();
+  Record* r = queue_.top().record;
   if (has_timestamp_) {
     if (r->Timestamp() + min_time_diff_in_ns_ > last_time_) {
       return nullptr;
@@ -743,8 +745,15 @@ std::unique_ptr<Record> RecordCache::Pop() {
 std::vector<std::unique_ptr<Record>> RecordCache::PopAll() {
   std::vector<std::unique_ptr<Record>> result;
   while (!queue_.empty()) {
-    result.emplace_back(queue_.top());
+    result.emplace_back(queue_.top().record);
     queue_.pop();
   }
   return result;
 }
+
+RecordCache::RecordWithSeq RecordCache::CreateRecordWithSeq(Record *r) {
+  RecordWithSeq result;
+  result.seq = cur_seq_++;
+  result.record = r;
+  return result;
+}
diff --git a/simpleperf/record.h b/simpleperf/record.h
index 58c72b03..a0aad16f 100644
--- a/simpleperf/record.h
+++ b/simpleperf/record.h
@@ -327,16 +327,27 @@ class RecordCache {
   std::vector<std::unique_ptr<Record>> PopAll();
 
  private:
+  struct RecordWithSeq {
+    uint32_t seq;
+    Record *record;
+
+    bool IsHappensBefore(const RecordWithSeq& other) const;
+  };
+
   struct RecordComparator {
-    bool operator()(const Record* r1, const Record* r2);
+    bool operator()(const RecordWithSeq& r1, const RecordWithSeq& r2);
   };
 
+  RecordWithSeq CreateRecordWithSeq(Record *r);
+
   const perf_event_attr attr_;
   bool has_timestamp_;
   size_t min_cache_size_;
   uint64_t min_time_diff_in_ns_;
   uint64_t last_time_;
-  std::priority_queue<Record*, std::vector<Record*>, RecordComparator> queue_;
+  uint32_t cur_seq_;
+  std::priority_queue<RecordWithSeq, std::vector<RecordWithSeq>,
+      RecordComparator> queue_;
 };
 
 std::vector<std::unique_ptr<Record>> ReadRecordsFromBuffer(const perf_event_attr& attr,
diff --git a/simpleperf/record_test.cpp b/simpleperf/record_test.cpp
index 6e4ed745..76eebe98 100644
--- a/simpleperf/record_test.cpp
+++ b/simpleperf/record_test.cpp
@@ -100,3 +100,21 @@ TEST_F(RecordTest, RecordCache_smoke) {
   ASSERT_EQ(1u, last_records.size());
   CheckRecordEqual(r4, *last_records[0]);
 }
+
+TEST_F(RecordTest, RecordCache_FIFO) {
+  event_attr.sample_id_all = 1;
+  event_attr.sample_type |= PERF_SAMPLE_TIME;
+  RecordCache cache(event_attr, 2, 2);
+  std::vector<MmapRecord> records;
+  for (size_t i = 0; i < 10; ++i) {
+    MmapRecord r = CreateMmapRecord(event_attr, true, 1, i, 0x100, 0x200, 0x300, "mmap_record1");
+    records.push_back(r);
+    std::vector<char> buf = r.BinaryFormat();
+    cache.Push(buf.data(), buf.size());
+  }
+  std::vector<std::unique_ptr<Record>> out_records = cache.PopAll();
+  ASSERT_EQ(records.size(), out_records.size());
+  for (size_t i = 0; i < records.size(); ++i) {
+    CheckRecordEqual(records[i], *out_records[i]);
+  }
+}