Merge "Simpleperf: remove overlapped user map in SampleTree."

3 files changed, 89 insertions, 32 deletions

diff --git a/simpleperf/sample_tree.cpp b/simpleperf/sample_tree.cpp
index 9c792f28..b980af41 100644
--- a/simpleperf/sample_tree.cpp
+++ b/simpleperf/sample_tree.cpp
@@ -18,18 +18,18 @@
 
 #include <base/logging.h>
 
-bool SampleTree::MapComparator::operator()(const MapEntry& map1, const MapEntry& map2) {
-  if (map1.pid != map2.pid) {
-    return map1.pid < map2.pid;
+bool SampleTree::MapComparator::operator()(const MapEntry* map1, const MapEntry* map2) {
+  if (map1->pid != map2->pid) {
+    return map1->pid < map2->pid;
   }
-  if (map1.start_addr != map2.start_addr) {
-    return map1.start_addr < map2.start_addr;
+  if (map1->start_addr != map2->start_addr) {
+    return map1->start_addr < map2->start_addr;
   }
-  if (map1.len != map2.len) {
-    return map1.len < map2.len;
+  if (map1->len != map2->len) {
+    return map1->len < map2->len;
   }
-  if (map1.time != map2.time) {
-    return map1.time < map2.time;
+  if (map1->time != map2->time) {
+    return map1->time < map2->time;
   }
   return false;
 }
@@ -43,7 +43,7 @@ void SampleTree::AddProcess(int pid, const std::string& comm) {
 
 void SampleTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
                               const std::string& filename) {
-  MapEntry map = {
+  MapEntry* map = new MapEntry{
       .pid = -1,
       .start_addr = start_addr,
       .len = len,
@@ -51,12 +51,13 @@ void SampleTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff,
       .time = time,
       .filename = filename,
   };
+  map_storage_.push_back(map);
   kernel_map_tree_.insert(map);
 }
 
 void SampleTree::AddUserMap(int pid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
                             uint64_t time, const std::string& filename) {
-  MapEntry map = {
+  MapEntry* map = new MapEntry{
       .pid = pid,
       .start_addr = start_addr,
       .len = len,
@@ -64,9 +65,28 @@ void SampleTree::AddUserMap(int pid, uint64_t start_addr, uint64_t len, uint64_t
       .time = time,
       .filename = filename,
   };
+  map_storage_.push_back(map);
+  RemoveOverlappedUserMap(map);
   user_map_tree_.insert(map);
 }
 
+void SampleTree::RemoveOverlappedUserMap(const MapEntry* map) {
+  MapEntry find_map = {
+      .pid = map->pid, .start_addr = 0, .len = 0, .time = 0,
+  };
+  auto it = user_map_tree_.lower_bound(&find_map);
+  while (it != user_map_tree_.end() && (*it)->pid == map->pid) {
+    if ((*it)->start_addr >= map->start_addr + map->len) {
+      break;
+    }
+    if ((*it)->start_addr + (*it)->len <= map->start_addr) {
+      ++it;
+    } else {
+      it = user_map_tree_.erase(it);
+    }
+  }
+}
+
 const ProcessEntry* SampleTree::FindProcessEntryOrNew(int pid) {
   auto it = process_tree_.find(pid);
   if (it == process_tree_.end()) {
@@ -79,8 +99,8 @@ const ProcessEntry* SampleTree::FindProcessEntryOrNew(int pid) {
   return &it->second;
 }
 
-static bool IsIpInMap(int pid, uint64_t ip, const MapEntry& map) {
-  return (pid == map.pid && map.start_addr <= ip && map.start_addr + map.len > ip);
+static bool IsIpInMap(int pid, uint64_t ip, const MapEntry* map) {
+  return (pid == map->pid && map->start_addr <= ip && map->start_addr + map->len > ip);
 }
 
 const MapEntry* SampleTree::FindMapEntryOrNew(int pid, uint64_t ip) {
@@ -91,18 +111,22 @@ const MapEntry* SampleTree::FindMapEntryOrNew(int pid, uint64_t ip) {
       .len = static_cast<uint64_t>(-1),
       .time = static_cast<uint64_t>(-1),
   };
-  auto it = user_map_tree_.upper_bound(find_map);
+  auto it = user_map_tree_.upper_bound(&find_map);
   if (it != user_map_tree_.begin() && IsIpInMap(pid, ip, *--it)) {
-    return &*it;
+    return *it;
   }
   find_map.pid = -1;
-  it = kernel_map_tree_.upper_bound(find_map);
+  it = kernel_map_tree_.upper_bound(&find_map);
   if (it != kernel_map_tree_.begin() && IsIpInMap(-1, ip, *--it)) {
-    return &*it;
+    return *it;
   }
-  auto unknown_it = unknown_maps_.find(pid);
-  if (unknown_it == unknown_maps_.end()) {
-    MapEntry unknown_map = {
+  return FindUnknownMapEntryOrNew(pid);
+}
+
+const MapEntry* SampleTree::FindUnknownMapEntryOrNew(int pid) {
+  auto it = unknown_maps_.find(pid);
+  if (it == unknown_maps_.end()) {
+    MapEntry* map = new MapEntry{
         .pid = pid,
         .start_addr = 0,
         .len = static_cast<uint64_t>(-1),
@@ -110,10 +134,11 @@ const MapEntry* SampleTree::FindMapEntryOrNew(int pid, uint64_t ip) {
         .time = 0,
         .filename = "unknown",
     };
-    auto pair = unknown_maps_.insert(std::make_pair(pid, unknown_map));
-    unknown_it = pair.first;
+    map_storage_.push_back(map);
+    auto pair = unknown_maps_.insert(std::make_pair(pid, map));
+    it = pair.first;
   }
-  return &unknown_it->second;
+  return it->second;
 }
 
 void SampleTree::AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period) {
diff --git a/simpleperf/sample_tree.h b/simpleperf/sample_tree.h
index ba144baa..852f4da7 100644
--- a/simpleperf/sample_tree.h
+++ b/simpleperf/sample_tree.h
@@ -21,6 +21,7 @@
 #include <set>
 #include <string>
 #include <unordered_map>
+#include <vector>
 
 struct ProcessEntry {
   int pid;
@@ -59,6 +60,12 @@ class SampleTree {
         total_period_(0) {
   }
 
+  ~SampleTree() {
+    for (auto& map : map_storage_) {
+      delete map;
+    }
+  }
+
   void AddProcess(int pid, const std::string& comm);
   void AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
                     const std::string& filename);
@@ -76,11 +83,13 @@ class SampleTree {
   }
 
  private:
+  void RemoveOverlappedUserMap(const MapEntry* map);
   const ProcessEntry* FindProcessEntryOrNew(int pid);
   const MapEntry* FindMapEntryOrNew(int pid, uint64_t ip);
+  const MapEntry* FindUnknownMapEntryOrNew(int pid);
 
   struct MapComparator {
-    bool operator()(const MapEntry& map1, const MapEntry& map2);
+    bool operator()(const MapEntry* map1, const MapEntry* map2);
   };
 
   struct SampleComparator {
@@ -109,9 +118,10 @@ class SampleTree {
 
   std::unordered_map<int, ProcessEntry> process_tree_;
 
-  std::set<MapEntry, MapComparator> kernel_map_tree_;
-  std::set<MapEntry, MapComparator> user_map_tree_;
-  std::unordered_map<int, MapEntry> unknown_maps_;
+  std::set<MapEntry*, MapComparator> kernel_map_tree_;
+  std::set<MapEntry*, MapComparator> user_map_tree_;
+  std::unordered_map<int, MapEntry*> unknown_maps_;
+  std::vector<MapEntry*> map_storage_;
 
   SampleComparator sample_comparator_;
   std::set<SampleEntry, SampleComparator> sample_tree_;
diff --git a/simpleperf/sample_tree_test.cpp b/simpleperf/sample_tree_test.cpp
index 09a7a2cd..114fa037 100644
--- a/simpleperf/sample_tree_test.cpp
+++ b/simpleperf/sample_tree_test.cpp
@@ -64,6 +64,14 @@ static int CompareSampleFunction(const SampleEntry& sample1, const SampleEntry&
   return 0;
 }
 
+void VisitSampleTree(SampleTree* sample_tree,
+                     const std::vector<ExpectedSampleInMap>& expected_samples) {
+  size_t pos = 0;
+  sample_tree->VisitAllSamples(
+      std::bind(&CheckSampleCallback, std::placeholders::_1, expected_samples, &pos));
+  ASSERT_EQ(expected_samples.size(), pos);
+}
+
 class SampleTreeTest : public testing::Test {
  protected:
   virtual void SetUp() {
@@ -74,11 +82,8 @@ class SampleTreeTest : public testing::Test {
     sample_tree->AddKernelMap(11, 20, 0, 0, "");
   }
 
-  void VisitSampleTree(std::vector<ExpectedSampleInMap>& expected_samples) {
-    size_t pos = 0;
-    sample_tree->VisitAllSamples(
-        std::bind(&CheckSampleCallback, std::placeholders::_1, expected_samples, &pos));
-    ASSERT_EQ(expected_samples.size(), pos);
+  void VisitSampleTree(const std::vector<ExpectedSampleInMap>& expected_samples) {
+    ::VisitSampleTree(sample_tree.get(), expected_samples);
   }
 
   std::unique_ptr<SampleTree> sample_tree;
@@ -140,3 +145,20 @@ TEST_F(SampleTreeTest, map_kernel) {
   };
   VisitSampleTree(expected_samples);
 }
+
+TEST(sample_tree, overlapped_map) {
+  auto sample_tree = std::unique_ptr<SampleTree>(new SampleTree(CompareSampleFunction));
+  sample_tree->AddUserMap(1, 1, 10, 0, 0, "");  // Add map 1.
+  sample_tree->AddSample(1, 1, 5, 0, 0);        // Hit map 1.
+  sample_tree->AddUserMap(1, 5, 20, 0, 0, "");  // Add map 2.
+  sample_tree->AddSample(1, 1, 6, 0, 0);        // Hit map 2.
+  sample_tree->AddSample(1, 1, 4, 0, 0);        // Hit unknown map.
+  sample_tree->AddUserMap(1, 2, 7, 0, 0, "");   // Add map 3.
+  sample_tree->AddSample(1, 1, 7, 0, 0);        // Hit map 3.
+  sample_tree->AddSample(1, 1, 10, 0, 0);       // Hit unknown map.
+
+  std::vector<ExpectedSampleInMap> expected_samples = {
+      {1, 1, 1, 0, 2}, {1, 1, 1, 1, 1}, {1, 1, 1, 2, 1}, {1, 1, 1, 5, 1},
+  };
+  VisitSampleTree(sample_tree.get(), expected_samples);
+}