Simpleperf: separate ThreadTree from SampleTree.

It is a preparation for unwinding in record command.

Bug: 22229391
Change-Id: I2f5c6df3f7332d4c98b61c7f9f922456b5bbeaaa

7 files changed, 327 insertions, 260 deletions

diff --git a/simpleperf/Android.mk b/simpleperf/Android.mk
index 278b96e2..35bec549 100644
--- a/simpleperf/Android.mk
+++ b/simpleperf/Android.mk
@@ -46,6 +46,7 @@ libsimpleperf_common_src_files := \
   record.cpp \
   record_file_reader.cpp \
   sample_tree.cpp \
+  thread_tree.cpp \
   utils.cpp \
 
 libsimpleperf_src_files := \
diff --git a/simpleperf/cmd_report.cpp b/simpleperf/cmd_report.cpp
index ab5b083e..ca9e5aab 100644
--- a/simpleperf/cmd_report.cpp
+++ b/simpleperf/cmd_report.cpp
@@ -34,6 +34,7 @@
 #include "record.h"
 #include "record_file.h"
 #include "sample_tree.h"
+#include "thread_tree.h"
 
 class Displayable {
  public:
@@ -257,7 +258,8 @@ class ReportCommand : public Command {
         print_callgraph_(false) {
     compare_sample_func_t compare_sample_callback = std::bind(
         &ReportCommand::CompareSampleEntry, this, std::placeholders::_1, std::placeholders::_2);
-    sample_tree_ = std::unique_ptr<SampleTree>(new SampleTree(compare_sample_callback));
+    sample_tree_ =
+        std::unique_ptr<SampleTree>(new SampleTree(&thread_tree_, compare_sample_callback));
   }
 
   bool Run(const std::vector<std::string>& args);
@@ -282,6 +284,7 @@ class ReportCommand : public Command {
   perf_event_attr event_attr_;
   std::vector<std::unique_ptr<Displayable>> displayable_items_;
   std::vector<Comparable*> comparable_items_;
+  ThreadTree thread_tree_;
   std::unique_ptr<SampleTree> sample_tree_;
   bool use_branch_address_;
   std::string record_cmdline_;
@@ -445,38 +448,38 @@ bool ReportCommand::ReadEventAttrFromRecordFile() {
 }
 
 void ReportCommand::ReadSampleTreeFromRecordFile() {
-  sample_tree_->AddThread(0, 0, "swapper");
+  thread_tree_.AddThread(0, 0, "swapper");
 
   std::vector<std::unique_ptr<const Record>> records = record_file_reader_->DataSection();
   for (auto& record : records) {
     if (record->header.type == PERF_RECORD_MMAP) {
       const MmapRecord& r = *static_cast<const MmapRecord*>(record.get());
       if ((r.header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL) {
-        sample_tree_->AddKernelMap(r.data.addr, r.data.len, r.data.pgoff,
-                                   r.sample_id.time_data.time, r.filename);
+        thread_tree_.AddKernelMap(r.data.addr, r.data.len, r.data.pgoff, r.sample_id.time_data.time,
+                                  r.filename);
       } else {
-        sample_tree_->AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
-                                   r.sample_id.time_data.time, r.filename);
+        thread_tree_.AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
+                                  r.sample_id.time_data.time, r.filename);
       }
     } else if (record->header.type == PERF_RECORD_MMAP2) {
       const Mmap2Record& r = *static_cast<const Mmap2Record*>(record.get());
       if ((r.header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL) {
-        sample_tree_->AddKernelMap(r.data.addr, r.data.len, r.data.pgoff,
-                                   r.sample_id.time_data.time, r.filename);
+        thread_tree_.AddKernelMap(r.data.addr, r.data.len, r.data.pgoff, r.sample_id.time_data.time,
+                                  r.filename);
       } else {
         std::string filename =
             (r.filename == DEFAULT_EXECNAME_FOR_THREAD_MMAP) ? "[unknown]" : r.filename;
-        sample_tree_->AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
-                                   r.sample_id.time_data.time, filename);
+        thread_tree_.AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
+                                  r.sample_id.time_data.time, filename);
       }
     } else if (record->header.type == PERF_RECORD_SAMPLE) {
       ProcessSampleRecord(*static_cast<const SampleRecord*>(record.get()));
     } else if (record->header.type == PERF_RECORD_COMM) {
       const CommRecord& r = *static_cast<const CommRecord*>(record.get());
-      sample_tree_->AddThread(r.data.pid, r.data.tid, r.comm);
+      thread_tree_.AddThread(r.data.pid, r.data.tid, r.comm);
     } else if (record->header.type == PERF_RECORD_FORK) {
       const ForkRecord& r = *static_cast<const ForkRecord*>(record.get());
-      sample_tree_->ForkThread(r.data.pid, r.data.tid, r.data.ppid, r.data.ptid);
+      thread_tree_.ForkThread(r.data.pid, r.data.tid, r.data.ppid, r.data.ptid);
     }
   }
 }
diff --git a/simpleperf/sample_tree.cpp b/simpleperf/sample_tree.cpp
index 6d0b403f..f8f27b10 100644
--- a/simpleperf/sample_tree.cpp
+++ b/simpleperf/sample_tree.cpp
@@ -20,151 +20,11 @@
 
 #include "environment.h"
 
-bool MapComparator::operator()(const MapEntry* map1, const MapEntry* map2) const {
-  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->time != map2->time) {
-    return map1->time < map2->time;
-  }
-  return false;
-}
-
-void SampleTree::AddThread(int pid, int tid, const std::string& comm) {
-  auto it = thread_tree_.find(tid);
-  if (it == thread_tree_.end()) {
-    ThreadEntry* thread = new ThreadEntry{
-        pid, tid,
-        "unknown",                             // comm
-        std::set<MapEntry*, MapComparator>(),  // maps
-    };
-    auto pair = thread_tree_.insert(std::make_pair(tid, std::unique_ptr<ThreadEntry>(thread)));
-    CHECK(pair.second);
-    it = pair.first;
-  }
-  thread_comm_storage_.push_back(std::unique_ptr<std::string>(new std::string(comm)));
-  it->second->comm = thread_comm_storage_.back()->c_str();
-}
-
-void SampleTree::ForkThread(int pid, int tid, int ppid, int ptid) {
-  ThreadEntry* parent = FindThreadOrNew(ppid, ptid);
-  ThreadEntry* child = FindThreadOrNew(pid, tid);
-  child->comm = parent->comm;
-  child->maps = parent->maps;
-}
-
-static void RemoveOverlappedMap(std::set<MapEntry*, MapComparator>* map_set, const MapEntry* map) {
-  for (auto it = map_set->begin(); it != map_set->end();) {
-    if ((*it)->start_addr >= map->start_addr + map->len) {
-      break;
-    }
-    if ((*it)->start_addr + (*it)->len <= map->start_addr) {
-      ++it;
-    } else {
-      it = map_set->erase(it);
-    }
-  }
-}
-
-void SampleTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
-                              const std::string& filename) {
-  // kernel map len can be 0 when record command is not run in supervisor mode.
-  if (len == 0) {
-    return;
-  }
-  DsoEntry* dso = FindKernelDsoOrNew(filename);
-  MapEntry* map = new MapEntry{
-      start_addr, len, pgoff, time, dso,
-  };
-  map_storage_.push_back(std::unique_ptr<MapEntry>(map));
-  RemoveOverlappedMap(&kernel_map_tree_, map);
-  auto pair = kernel_map_tree_.insert(map);
-  CHECK(pair.second);
-}
-
-DsoEntry* SampleTree::FindKernelDsoOrNew(const std::string& filename) {
-  if (filename == DEFAULT_KERNEL_MMAP_NAME) {
-    if (kernel_dso_ == nullptr) {
-      kernel_dso_ = DsoFactory::GetInstance()->CreateDso(DSO_KERNEL);
-    }
-    return kernel_dso_.get();
-  }
-  auto it = module_dso_tree_.find(filename);
-  if (it == module_dso_tree_.end()) {
-    module_dso_tree_[filename] = DsoFactory::GetInstance()->CreateDso(DSO_KERNEL_MODULE, filename);
-    it = module_dso_tree_.find(filename);
-  }
-  return it->second.get();
-}
-
-void SampleTree::AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
-                              uint64_t time, const std::string& filename) {
-  ThreadEntry* thread = FindThreadOrNew(pid, tid);
-  DsoEntry* dso = FindUserDsoOrNew(filename);
-  MapEntry* map = new MapEntry{
-      start_addr, len, pgoff, time, dso,
-  };
-  map_storage_.push_back(std::unique_ptr<MapEntry>(map));
-  RemoveOverlappedMap(&thread->maps, map);
-  auto pair = thread->maps.insert(map);
-  CHECK(pair.second);
-}
-
-ThreadEntry* SampleTree::FindThreadOrNew(int pid, int tid) {
-  auto it = thread_tree_.find(tid);
-  if (it == thread_tree_.end()) {
-    AddThread(pid, tid, "unknown");
-    it = thread_tree_.find(tid);
-  } else {
-    CHECK_EQ(pid, it->second.get()->pid) << "tid = " << tid;
-  }
-  return it->second.get();
-}
-
-DsoEntry* SampleTree::FindUserDsoOrNew(const std::string& filename) {
-  auto it = user_dso_tree_.find(filename);
-  if (it == user_dso_tree_.end()) {
-    user_dso_tree_[filename] = DsoFactory::GetInstance()->CreateDso(DSO_ELF_FILE, filename);
-    it = user_dso_tree_.find(filename);
-  }
-  return it->second.get();
-}
-
-static bool IsIpInMap(uint64_t ip, const MapEntry* map) {
-  return (map->start_addr <= ip && map->start_addr + map->len > ip);
-}
-
-const MapEntry* SampleTree::FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel) {
-  // Construct a map_entry which is strictly after the searched map_entry, based on MapComparator.
-  MapEntry find_map = {
-      ip,          // start_addr
-      ULLONG_MAX,  // len
-      0,           // pgoff
-      ULLONG_MAX,  // time
-      nullptr,     // dso
-  };
-  if (!in_kernel) {
-    auto it = thread->maps.upper_bound(&find_map);
-    if (it != thread->maps.begin() && IsIpInMap(ip, *--it)) {
-      return *it;
-    }
-  } else {
-    auto it = kernel_map_tree_.upper_bound(&find_map);
-    if (it != kernel_map_tree_.begin() && IsIpInMap(ip, *--it)) {
-      return *it;
-    }
-  }
-  return &unknown_map_;
-}
-
 SampleEntry* SampleTree::AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
                                    bool in_kernel) {
-  const ThreadEntry* thread = FindThreadOrNew(pid, tid);
-  const MapEntry* map = FindMap(thread, ip, in_kernel);
-  const SymbolEntry* symbol = FindSymbol(map, ip);
+  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
+  const MapEntry* map = thread_tree_->FindMap(thread, ip, in_kernel);
+  const SymbolEntry* symbol = thread_tree_->FindSymbol(map, ip);
 
   SampleEntry value(ip, time, period, 0, 1, thread, map, symbol);
 
@@ -173,17 +33,17 @@ SampleEntry* SampleTree::AddSample(int pid, int tid, uint64_t ip, uint64_t time,
 
 void SampleTree::AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to_ip,
                                  uint64_t branch_flags, uint64_t time, uint64_t period) {
-  const ThreadEntry* thread = FindThreadOrNew(pid, tid);
-  const MapEntry* from_map = FindMap(thread, from_ip, false);
-  if (from_map == &unknown_map_) {
-    from_map = FindMap(thread, from_ip, true);
+  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
+  const MapEntry* from_map = thread_tree_->FindMap(thread, from_ip, false);
+  if (from_map == thread_tree_->UnknownMap()) {
+    from_map = thread_tree_->FindMap(thread, from_ip, true);
   }
-  const SymbolEntry* from_symbol = FindSymbol(from_map, from_ip);
-  const MapEntry* to_map = FindMap(thread, to_ip, false);
-  if (to_map == &unknown_map_) {
-    to_map = FindMap(thread, to_ip, true);
+  const SymbolEntry* from_symbol = thread_tree_->FindSymbol(from_map, from_ip);
+  const MapEntry* to_map = thread_tree_->FindMap(thread, to_ip, false);
+  if (to_map == thread_tree_->UnknownMap()) {
+    to_map = thread_tree_->FindMap(thread, to_ip, true);
   }
-  const SymbolEntry* to_symbol = FindSymbol(to_map, to_ip);
+  const SymbolEntry* to_symbol = thread_tree_->FindSymbol(to_map, to_ip);
 
   SampleEntry value(to_ip, time, period, 0, 1, thread, to_map, to_symbol);
   value.branch_from.ip = from_ip;
@@ -197,9 +57,9 @@ void SampleTree::AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to
 SampleEntry* SampleTree::AddCallChainSample(int pid, int tid, uint64_t ip, uint64_t time,
                                             uint64_t period, bool in_kernel,
                                             const std::vector<SampleEntry*>& callchain) {
-  const ThreadEntry* thread = FindThreadOrNew(pid, tid);
-  const MapEntry* map = FindMap(thread, ip, in_kernel);
-  const SymbolEntry* symbol = FindSymbol(map, ip);
+  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
+  const MapEntry* map = thread_tree_->FindMap(thread, ip, in_kernel);
+  const SymbolEntry* symbol = thread_tree_->FindSymbol(map, ip);
 
   SampleEntry value(ip, time, 0, period, 0, thread, map, symbol);
 
@@ -238,20 +98,6 @@ SampleEntry* SampleTree::AllocateSample(SampleEntry& value) {
   return sample;
 }
 
-const SymbolEntry* SampleTree::FindSymbol(const MapEntry* map, uint64_t ip) {
-  uint64_t offset_in_file;
-  if (map->dso == kernel_dso_.get()) {
-    offset_in_file = ip;
-  } else {
-    offset_in_file = ip - map->start_addr + map->pgoff;
-  }
-  const SymbolEntry* symbol = map->dso->FindSymbol(offset_in_file);
-  if (symbol == nullptr) {
-    symbol = &unknown_symbol_;
-  }
-  return symbol;
-}
-
 void SampleTree::InsertCallChainForSample(SampleEntry* sample,
                                           const std::vector<SampleEntry*>& callchain,
                                           uint64_t period) {
diff --git a/simpleperf/sample_tree.h b/simpleperf/sample_tree.h
index 4e51aca3..b79f164c 100644
--- a/simpleperf/sample_tree.h
+++ b/simpleperf/sample_tree.h
@@ -25,26 +25,7 @@
 #include <vector>
 
 #include "callchain.h"
-#include "dso.h"
-
-struct MapEntry {
-  uint64_t start_addr;
-  uint64_t len;
-  uint64_t pgoff;
-  uint64_t time;  // Map creation time.
-  DsoEntry* dso;
-};
-
-struct MapComparator {
-  bool operator()(const MapEntry* map1, const MapEntry* map2) const;
-};
-
-struct ThreadEntry {
-  int pid;
-  int tid;
-  const char* comm;  // It always refers to the latest comm.
-  std::set<MapEntry*, MapComparator> maps;
-};
+#include "thread_tree.h"
 
 struct BranchFromEntry {
   uint64_t ip;
@@ -92,34 +73,16 @@ typedef std::function<int(const SampleEntry&, const SampleEntry&)> compare_sampl
 
 class SampleTree {
  public:
-  SampleTree(compare_sample_func_t sample_compare_function)
-      : unknown_dso_(DSO_ELF_FILE, "unknown"),
+  SampleTree(ThreadTree* thread_tree, compare_sample_func_t sample_compare_function)
+      : thread_tree_(thread_tree),
         sample_comparator_(sample_compare_function),
         sample_tree_(sample_comparator_),
         sorted_sample_comparator_(sample_compare_function),
         sorted_sample_tree_(sorted_sample_comparator_),
         total_samples_(0),
         total_period_(0) {
-    unknown_map_ = MapEntry{
-        0,              // start_addr
-        ULLONG_MAX,     // len
-        0,              // pgoff
-        0,              // time
-        &unknown_dso_,  // dso
-    };
-    unknown_symbol_ = SymbolEntry{
-        "unknown",   // name
-        0,           // addr
-        ULLONG_MAX,  // len
-    };
   }
 
-  void AddThread(int pid, int tid, const std::string& comm);
-  void ForkThread(int pid, int tid, int ppid, int ptid);
-  void AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
-                    const std::string& filename);
-  void AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
-                    uint64_t time, const std::string& filename);
   SampleEntry* AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
                          bool in_kernel);
   void AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to_ip, uint64_t branch_flags,
@@ -139,11 +102,6 @@ class SampleTree {
   }
 
  private:
-  ThreadEntry* FindThreadOrNew(int pid, int tid);
-  const MapEntry* FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel);
-  DsoEntry* FindKernelDsoOrNew(const std::string& filename);
-  DsoEntry* FindUserDsoOrNew(const std::string& filename);
-  const SymbolEntry* FindSymbol(const MapEntry* map, uint64_t ip);
   SampleEntry* InsertSample(SampleEntry& value);
   SampleEntry* AllocateSample(SampleEntry& value);
 
@@ -173,19 +131,7 @@ class SampleTree {
     compare_sample_func_t compare_function;
   };
 
-  std::unordered_map<int, std::unique_ptr<ThreadEntry>> thread_tree_;
-  std::vector<std::unique_ptr<std::string>> thread_comm_storage_;
-
-  std::set<MapEntry*, MapComparator> kernel_map_tree_;
-  std::vector<std::unique_ptr<MapEntry>> map_storage_;
-  MapEntry unknown_map_;
-
-  std::unique_ptr<DsoEntry> kernel_dso_;
-  std::unordered_map<std::string, std::unique_ptr<DsoEntry>> module_dso_tree_;
-  std::unordered_map<std::string, std::unique_ptr<DsoEntry>> user_dso_tree_;
-  DsoEntry unknown_dso_;
-  SymbolEntry unknown_symbol_;
-
+  ThreadTree* thread_tree_;
   SampleComparator sample_comparator_;
   std::set<SampleEntry*, SampleComparator> sample_tree_;
   SortedSampleComparator sorted_sample_comparator_;
diff --git a/simpleperf/sample_tree_test.cpp b/simpleperf/sample_tree_test.cpp
index 9b37f470..cb590832 100644
--- a/simpleperf/sample_tree_test.cpp
+++ b/simpleperf/sample_tree_test.cpp
@@ -80,21 +80,22 @@ void VisitSampleTree(SampleTree* sample_tree,
 class SampleTreeTest : public testing::Test {
  protected:
   virtual void SetUp() {
-    sample_tree = std::unique_ptr<SampleTree>(new SampleTree(CompareSampleFunction));
-    sample_tree->AddThread(1, 1, "p1t1");
-    sample_tree->AddThread(1, 11, "p1t11");
-    sample_tree->AddThread(2, 2, "p2t2");
-    sample_tree->AddThreadMap(1, 1, 1, 5, 0, 0, "process1_thread1");
-    sample_tree->AddThreadMap(1, 1, 6, 5, 0, 0, "process1_thread1_map2");
-    sample_tree->AddThreadMap(1, 11, 1, 10, 0, 0, "process1_thread11");
-    sample_tree->AddThreadMap(2, 2, 1, 20, 0, 0, "process2_thread2");
-    sample_tree->AddKernelMap(10, 20, 0, 0, "kernel");
+    thread_tree.AddThread(1, 1, "p1t1");
+    thread_tree.AddThread(1, 11, "p1t11");
+    thread_tree.AddThread(2, 2, "p2t2");
+    thread_tree.AddThreadMap(1, 1, 1, 5, 0, 0, "process1_thread1");
+    thread_tree.AddThreadMap(1, 1, 6, 5, 0, 0, "process1_thread1_map2");
+    thread_tree.AddThreadMap(1, 11, 1, 10, 0, 0, "process1_thread11");
+    thread_tree.AddThreadMap(2, 2, 1, 20, 0, 0, "process2_thread2");
+    thread_tree.AddKernelMap(10, 20, 0, 0, "kernel");
+    sample_tree = std::unique_ptr<SampleTree>(new SampleTree(&thread_tree, CompareSampleFunction));
   }
 
   void VisitSampleTree(const std::vector<ExpectedSampleInMap>& expected_samples) {
     ::VisitSampleTree(sample_tree.get(), expected_samples);
   }
 
+  ThreadTree thread_tree;
   std::unique_ptr<SampleTree> sample_tree;
 };
 
@@ -128,7 +129,7 @@ TEST_F(SampleTreeTest, different_tid) {
 
 TEST_F(SampleTreeTest, different_comm) {
   sample_tree->AddSample(1, 1, 1, 0, 0, false);
-  sample_tree->AddThread(1, 1, "p1t1_comm2");
+  thread_tree.AddThread(1, 1, "p1t1_comm2");
   sample_tree->AddSample(1, 1, 1, 0, 0, false);
   std::vector<ExpectedSampleInMap> expected_samples = {
       {1, 1, "p1t1", "process1_thread1", 1, 1}, {1, 1, "p1t1_comm2", "process1_thread1", 1, 1},
@@ -166,16 +167,17 @@ TEST_F(SampleTreeTest, map_kernel) {
 }
 
 TEST(sample_tree, overlapped_map) {
-  auto sample_tree = std::unique_ptr<SampleTree>(new SampleTree(CompareSampleFunction));
-  sample_tree->AddThread(1, 1, "thread1");
-  sample_tree->AddThreadMap(1, 1, 1, 10, 0, 0, "map1");  // Add map 1.
-  sample_tree->AddSample(1, 1, 5, 0, 0, false);          // Hit map 1.
-  sample_tree->AddThreadMap(1, 1, 5, 20, 0, 0, "map2");  // Add map 2.
-  sample_tree->AddSample(1, 1, 6, 0, 0, false);          // Hit map 2.
-  sample_tree->AddSample(1, 1, 4, 0, 0, false);          // Hit unknown map.
-  sample_tree->AddThreadMap(1, 1, 2, 7, 0, 0, "map3");   // Add map 3.
-  sample_tree->AddSample(1, 1, 7, 0, 0, false);          // Hit map 3.
-  sample_tree->AddSample(1, 1, 10, 0, 0, false);         // Hit unknown map.
+  ThreadTree thread_tree;
+  SampleTree sample_tree(&thread_tree, CompareSampleFunction);
+  thread_tree.AddThread(1, 1, "thread1");
+  thread_tree.AddThreadMap(1, 1, 1, 10, 0, 0, "map1");  // Add map 1.
+  sample_tree.AddSample(1, 1, 5, 0, 0, false);          // Hit map 1.
+  thread_tree.AddThreadMap(1, 1, 5, 20, 0, 0, "map2");  // Add map 2.
+  sample_tree.AddSample(1, 1, 6, 0, 0, false);          // Hit map 2.
+  sample_tree.AddSample(1, 1, 4, 0, 0, false);          // Hit unknown map.
+  thread_tree.AddThreadMap(1, 1, 2, 7, 0, 0, "map3");   // Add map 3.
+  sample_tree.AddSample(1, 1, 7, 0, 0, false);          // Hit map 3.
+  sample_tree.AddSample(1, 1, 10, 0, 0, false);         // Hit unknown map.
 
   std::vector<ExpectedSampleInMap> expected_samples = {
       {1, 1, "thread1", "map1", 1, 1},
@@ -183,5 +185,5 @@ TEST(sample_tree, overlapped_map) {
       {1, 1, "thread1", "map3", 2, 1},
       {1, 1, "thread1", "unknown", 0, 2},
   };
-  VisitSampleTree(sample_tree.get(), expected_samples);
+  VisitSampleTree(&sample_tree, expected_samples);
 }
diff --git a/simpleperf/thread_tree.cpp b/simpleperf/thread_tree.cpp
new file mode 100644
index 00000000..ef51b5c5
--- /dev/null
+++ b/simpleperf/thread_tree.cpp
@@ -0,0 +1,177 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "thread_tree.h"
+
+#include <base/logging.h>
+#include "environment.h"
+
+bool MapComparator::operator()(const MapEntry* map1, const MapEntry* map2) const {
+  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->time != map2->time) {
+    return map1->time < map2->time;
+  }
+  return false;
+}
+
+void ThreadTree::AddThread(int pid, int tid, const std::string& comm) {
+  auto it = thread_tree_.find(tid);
+  if (it == thread_tree_.end()) {
+    ThreadEntry* thread = new ThreadEntry{
+        pid, tid,
+        "unknown",                             // comm
+        std::set<MapEntry*, MapComparator>(),  // maps
+    };
+    auto pair = thread_tree_.insert(std::make_pair(tid, std::unique_ptr<ThreadEntry>(thread)));
+    CHECK(pair.second);
+    it = pair.first;
+  }
+  thread_comm_storage_.push_back(std::unique_ptr<std::string>(new std::string(comm)));
+  it->second->comm = thread_comm_storage_.back()->c_str();
+}
+
+void ThreadTree::ForkThread(int pid, int tid, int ppid, int ptid) {
+  ThreadEntry* parent = FindThreadOrNew(ppid, ptid);
+  ThreadEntry* child = FindThreadOrNew(pid, tid);
+  child->comm = parent->comm;
+  child->maps = parent->maps;
+}
+
+ThreadEntry* ThreadTree::FindThreadOrNew(int pid, int tid) {
+  auto it = thread_tree_.find(tid);
+  if (it == thread_tree_.end()) {
+    AddThread(pid, tid, "unknown");
+    it = thread_tree_.find(tid);
+  } else {
+    CHECK_EQ(pid, it->second.get()->pid) << "tid = " << tid;
+  }
+  return it->second.get();
+}
+
+static void RemoveOverlappedMap(std::set<MapEntry*, MapComparator>* map_set, const MapEntry* map) {
+  for (auto it = map_set->begin(); it != map_set->end();) {
+    if ((*it)->start_addr >= map->start_addr + map->len) {
+      break;
+    }
+    if ((*it)->start_addr + (*it)->len <= map->start_addr) {
+      ++it;
+    } else {
+      it = map_set->erase(it);
+    }
+  }
+}
+
+void ThreadTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
+                              const std::string& filename) {
+  // kernel map len can be 0 when record command is not run in supervisor mode.
+  if (len == 0) {
+    return;
+  }
+  DsoEntry* dso = FindKernelDsoOrNew(filename);
+  MapEntry* map = new MapEntry{
+      start_addr, len, pgoff, time, dso,
+  };
+  map_storage_.push_back(std::unique_ptr<MapEntry>(map));
+  RemoveOverlappedMap(&kernel_map_tree_, map);
+  auto pair = kernel_map_tree_.insert(map);
+  CHECK(pair.second);
+}
+
+DsoEntry* ThreadTree::FindKernelDsoOrNew(const std::string& filename) {
+  if (filename == DEFAULT_KERNEL_MMAP_NAME) {
+    if (kernel_dso_ == nullptr) {
+      kernel_dso_ = DsoFactory::GetInstance()->CreateDso(DSO_KERNEL);
+    }
+    return kernel_dso_.get();
+  }
+  auto it = module_dso_tree_.find(filename);
+  if (it == module_dso_tree_.end()) {
+    module_dso_tree_[filename] = DsoFactory::GetInstance()->CreateDso(DSO_KERNEL_MODULE, filename);
+    it = module_dso_tree_.find(filename);
+  }
+  return it->second.get();
+}
+
+void ThreadTree::AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
+                              uint64_t time, const std::string& filename) {
+  ThreadEntry* thread = FindThreadOrNew(pid, tid);
+  DsoEntry* dso = FindUserDsoOrNew(filename);
+  MapEntry* map = new MapEntry{
+      start_addr, len, pgoff, time, dso,
+  };
+  map_storage_.push_back(std::unique_ptr<MapEntry>(map));
+  RemoveOverlappedMap(&thread->maps, map);
+  auto pair = thread->maps.insert(map);
+  CHECK(pair.second);
+}
+
+DsoEntry* ThreadTree::FindUserDsoOrNew(const std::string& filename) {
+  auto it = user_dso_tree_.find(filename);
+  if (it == user_dso_tree_.end()) {
+    user_dso_tree_[filename] = DsoFactory::GetInstance()->CreateDso(DSO_ELF_FILE, filename);
+    it = user_dso_tree_.find(filename);
+  }
+  return it->second.get();
+}
+
+static bool IsAddrInMap(uint64_t addr, const MapEntry* map) {
+  return (addr >= map->start_addr && addr < map->start_addr + map->len);
+}
+
+static MapEntry* FindMapByAddr(const std::set<MapEntry*, MapComparator>& maps, uint64_t addr) {
+  // Construct a map_entry which is strictly after the searched map_entry, based on MapComparator.
+  MapEntry find_map = {
+      addr,        // start_addr
+      ULLONG_MAX,  // len
+      0,           // pgoff
+      ULLONG_MAX,  // time
+      nullptr,     // dso
+  };
+  auto it = maps.upper_bound(&find_map);
+  if (it != maps.begin() && IsAddrInMap(addr, *--it)) {
+    return *it;
+  }
+  return nullptr;
+}
+
+const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel) {
+  MapEntry* result = nullptr;
+  if (!in_kernel) {
+    result = FindMapByAddr(thread->maps, ip);
+  } else {
+    result = FindMapByAddr(kernel_map_tree_, ip);
+  }
+  return result != nullptr ? result : &unknown_map_;
+}
+
+const SymbolEntry* ThreadTree::FindSymbol(const MapEntry* map, uint64_t ip) {
+  uint64_t offset_in_file;
+  if (map->dso == kernel_dso_.get()) {
+    offset_in_file = ip;
+  } else {
+    offset_in_file = ip - map->start_addr + map->pgoff;
+  }
+  const SymbolEntry* symbol = map->dso->FindSymbol(offset_in_file);
+  if (symbol == nullptr) {
+    symbol = &unknown_symbol_;
+  }
+  return symbol;
+}
diff --git a/simpleperf/thread_tree.h b/simpleperf/thread_tree.h
new file mode 100644
index 00000000..8e96e36e
--- /dev/null
+++ b/simpleperf/thread_tree.h
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SIMPLE_PERF_THREAD_TREE_H_
+#define SIMPLE_PERF_THREAD_TREE_H_
+
+#include <limits.h>
+#include <stdint.h>
+#include <set>
+#include "dso.h"
+
+struct MapEntry {
+  uint64_t start_addr;
+  uint64_t len;
+  uint64_t pgoff;
+  uint64_t time;  // Map creation time.
+  DsoEntry* dso;
+};
+
+struct MapComparator {
+  bool operator()(const MapEntry* map1, const MapEntry* map2) const;
+};
+
+struct ThreadEntry {
+  int pid;
+  int tid;
+  const char* comm;  // It always refers to the latest comm.
+  std::set<MapEntry*, MapComparator> maps;
+};
+
+class ThreadTree {
+ public:
+  ThreadTree() : unknown_dso_(DSO_ELF_FILE, "unknown") {
+    unknown_map_ = MapEntry{
+        0,              // start_addr
+        ULLONG_MAX,     // len
+        0,              // pgoff
+        0,              // time
+        &unknown_dso_,  // dso
+    };
+    unknown_symbol_ = SymbolEntry{
+        "unknown",   // name
+        0,           // addr
+        ULLONG_MAX,  // len
+    };
+  }
+
+  void AddThread(int pid, int tid, const std::string& comm);
+  void ForkThread(int pid, int tid, int ppid, int ptid);
+  ThreadEntry* FindThreadOrNew(int pid, int tid);
+  void AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
+                    const std::string& filename);
+  void AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
+                    uint64_t time, const std::string& filename);
+  const MapEntry* FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel);
+  const SymbolEntry* FindSymbol(const MapEntry* map, uint64_t ip);
+  const MapEntry* UnknownMap() const {
+    return &unknown_map_;
+  }
+
+ private:
+  DsoEntry* FindKernelDsoOrNew(const std::string& filename);
+  DsoEntry* FindUserDsoOrNew(const std::string& filename);
+
+  std::unordered_map<int, std::unique_ptr<ThreadEntry>> thread_tree_;
+  std::vector<std::unique_ptr<std::string>> thread_comm_storage_;
+
+  std::set<MapEntry*, MapComparator> kernel_map_tree_;
+  std::vector<std::unique_ptr<MapEntry>> map_storage_;
+  MapEntry unknown_map_;
+
+  std::unique_ptr<DsoEntry> kernel_dso_;
+  std::unordered_map<std::string, std::unique_ptr<DsoEntry>> module_dso_tree_;
+  std::unordered_map<std::string, std::unique_ptr<DsoEntry>> user_dso_tree_;
+  DsoEntry unknown_dso_;
+  SymbolEntry unknown_symbol_;
+};
+
+#endif  // SIMPLE_PERF_THREAD_TREE_H_