Simpleperf: fix some unknown symbols for report result.

Using debug shared libraries in /usr/lib/debug on linux host.
Match ip addresses with symbols by symbols' virtual addresses instead of
file offsets in elf file. Because symbols' file offsets in debug shared
libraries are different from those in original shared libraries.

Fix overlapped maps.

Bug: 24716851
Change-Id: I9cb64958c4de5c7a6c77c3febc5f689cf2df650f

6 files changed, 169 insertions, 65 deletions

diff --git a/simpleperf/dso.cpp b/simpleperf/dso.cpp
index 13f2bfe3..6f895259 100644
--- a/simpleperf/dso.cpp
+++ b/simpleperf/dso.cpp
@@ -134,7 +134,8 @@ std::unique_ptr<Dso> Dso::CreateDso(DsoType dso_type, const std::string& dso_pat
   return std::unique_ptr<Dso>(new Dso(dso_type, path));
 }
 
-Dso::Dso(DsoType type, const std::string& path) : type_(type), path_(path), is_loaded_(false) {
+Dso::Dso(DsoType type, const std::string& path)
+    : type_(type), path_(path), min_vaddr_(std::numeric_limits<uint64_t>::max()), is_loaded_(false) {
   dso_count_++;
 }
 
@@ -154,7 +155,7 @@ std::string Dso::GetAccessiblePath() const {
   return symfs_dir_ + path_;
 }
 
-const Symbol* Dso::FindSymbol(uint64_t offset_in_dso) {
+const Symbol* Dso::FindSymbol(uint64_t vaddr_in_dso) {
   if (!is_loaded_) {
     is_loaded_ = true;
     if (!Load()) {
@@ -163,17 +164,32 @@ const Symbol* Dso::FindSymbol(uint64_t offset_in_dso) {
     }
   }
 
-  auto it = std::upper_bound(symbols_.begin(), symbols_.end(), Symbol("", offset_in_dso, 0),
+  auto it = std::upper_bound(symbols_.begin(), symbols_.end(), Symbol("", vaddr_in_dso, 0),
                              SymbolComparator());
   if (it != symbols_.begin()) {
     --it;
-    if (it->addr <= offset_in_dso && it->addr + it->len > offset_in_dso) {
+    if (it->addr <= vaddr_in_dso && it->addr + it->len > vaddr_in_dso) {
       return &*it;
     }
   }
   return nullptr;
 }
 
+uint64_t Dso::MinVirtualAddress() {
+  if (min_vaddr_ == std::numeric_limits<uint64_t>::max()) {
+    min_vaddr_ = 0;
+    if (type_ == DSO_ELF_FILE) {
+      BuildId build_id = GetExpectedBuildId(GetAccessiblePath());
+
+      uint64_t addr;
+      if (ReadMinExecutableVirtualAddressFromElfFile(GetAccessiblePath(), build_id, &addr)) {
+        min_vaddr_ = addr;
+      }
+    }
+  }
+  return min_vaddr_;
+}
+
 bool Dso::Load() {
   bool result = false;
   switch (type_) {
@@ -250,7 +266,7 @@ bool Dso::LoadKernel() {
 void Dso::ElfFileSymbolCallback(const ElfFileSymbol& elf_symbol, Dso* dso,
                                 bool (*filter)(const ElfFileSymbol&)) {
   if (filter(elf_symbol)) {
-    dso->InsertSymbol(Symbol(elf_symbol.name, elf_symbol.start_in_file, elf_symbol.len));
+    dso->InsertSymbol(Symbol(elf_symbol.name, elf_symbol.vaddr, elf_symbol.len));
   }
 }
 
@@ -272,11 +288,21 @@ static bool SymbolFilterForDso(const ElfFileSymbol& elf_symbol) {
 }
 
 bool Dso::LoadElfFile() {
-  BuildId build_id = GetExpectedBuildId(path_);
-  ParseSymbolsFromElfFile(
-      symfs_dir_ + path_, build_id,
-      std::bind(ElfFileSymbolCallback, std::placeholders::_1, this, SymbolFilterForDso));
-  return true;
+  bool loaded = false;
+  BuildId build_id = GetExpectedBuildId(GetAccessiblePath());
+
+  if (symfs_dir_.empty()) {
+    // Linux host can store debug shared libraries in /usr/lib/debug.
+    loaded = ParseSymbolsFromElfFile(
+        "/usr/lib/debug" + path_, build_id,
+        std::bind(ElfFileSymbolCallback, std::placeholders::_1, this, SymbolFilterForDso));
+  }
+  if (!loaded) {
+    loaded = ParseSymbolsFromElfFile(
+        GetAccessiblePath(), build_id,
+        std::bind(ElfFileSymbolCallback, std::placeholders::_1, this, SymbolFilterForDso));
+  }
+  return loaded;
 }
 
 void Dso::InsertSymbol(const Symbol& symbol) {
diff --git a/simpleperf/dso.h b/simpleperf/dso.h
index bbe01908..a140e5e9 100644
--- a/simpleperf/dso.h
+++ b/simpleperf/dso.h
@@ -70,7 +70,10 @@ struct Dso {
   // return the path with prefix set by SetSymFsDir().
   std::string GetAccessiblePath() const;
 
-  const Symbol* FindSymbol(uint64_t offset_in_dso);
+  // Return the minimum virtual address in program header.
+  uint64_t MinVirtualAddress();
+
+  const Symbol* FindSymbol(uint64_t vaddr_in_dso);
 
  private:
   static BuildId GetExpectedBuildId(const std::string& filename);
@@ -95,6 +98,7 @@ struct Dso {
 
   const DsoType type_;
   const std::string path_;
+  uint64_t min_vaddr_;
   std::vector<Symbol> symbols_;
   bool is_loaded_;
 };
diff --git a/simpleperf/read_elf.cpp b/simpleperf/read_elf.cpp
index 028af720..5ec289be 100644
--- a/simpleperf/read_elf.cpp
+++ b/simpleperf/read_elf.cpp
@@ -18,7 +18,10 @@
 
 #include <stdio.h>
 #include <string.h>
+
 #include <algorithm>
+#include <limits>
+
 #include <base/file.h>
 #include <base/logging.h>
 
@@ -168,10 +171,9 @@ void ParseSymbolsFromELFFile(const llvm::object::ELFFile<ELFT>* elf,
       continue;
     }
     symbol.vaddr = elf_symbol.st_value;
-    symbol.start_in_file = elf_symbol.st_value - shdr->sh_addr + shdr->sh_offset;
-    if ((symbol.start_in_file & 1) != 0 && is_arm) {
+    if ((symbol.vaddr & 1) != 0 && is_arm) {
       // Arm sets bit 0 to mark it as thumb code, remove the flag.
-      symbol.start_in_file &= ~1;
+      symbol.vaddr &= ~1;
     }
     symbol.len = elf_symbol.st_size;
     int type = elf_symbol.getType();
@@ -196,18 +198,18 @@ void ParseSymbolsFromELFFile(const llvm::object::ELFFile<ELFT>* elf,
   }
 }
 
-bool ParseSymbolsFromElfFile(const std::string& filename, const BuildId& expected_build_id,
-                             std::function<void(const ElfFileSymbol&)> callback) {
-  auto owning_binary = llvm::object::createBinary(llvm::StringRef(filename));
+static llvm::object::ObjectFile* GetObjectFile(
+    llvm::ErrorOr<llvm::object::OwningBinary<llvm::object::Binary>>& owning_binary,
+    const std::string& filename, const BuildId& expected_build_id) {
   if (owning_binary.getError()) {
     PLOG(DEBUG) << "can't open file '" << filename << "'";
-    return false;
+    return nullptr;
   }
   llvm::object::Binary* binary = owning_binary.get().getBinary();
   auto obj = llvm::dyn_cast<llvm::object::ObjectFile>(binary);
   if (obj == nullptr) {
     LOG(DEBUG) << filename << " is not an object file";
-    return false;
+    return nullptr;
   }
   if (!expected_build_id.IsEmpty()) {
     BuildId real_build_id;
@@ -217,9 +219,19 @@ bool ParseSymbolsFromElfFile(const std::string& filename, const BuildId& expecte
                << "): expected " << expected_build_id.ToString() << ", real "
                << real_build_id.ToString();
     if (!result) {
-      return false;
+      return nullptr;
     }
   }
+  return obj;
+}
+
+bool ParseSymbolsFromElfFile(const std::string& filename, const BuildId& expected_build_id,
+                             std::function<void(const ElfFileSymbol&)> callback) {
+  auto owning_binary = llvm::object::createBinary(llvm::StringRef(filename));
+  llvm::object::ObjectFile* obj = GetObjectFile(owning_binary, filename, expected_build_id);
+  if (obj == nullptr) {
+    return false;
+  }
 
   if (auto elf = llvm::dyn_cast<llvm::object::ELF32LEObjectFile>(obj)) {
     ParseSymbolsFromELFFile(elf->getELFFile(), callback);
@@ -231,3 +243,46 @@ bool ParseSymbolsFromElfFile(const std::string& filename, const BuildId& expecte
   }
   return true;
 }
+
+template <class ELFT>
+bool ReadMinExecutableVirtualAddress(const llvm::object::ELFFile<ELFT>* elf, uint64_t* p_vaddr) {
+  bool has_vaddr = false;
+  uint64_t min_addr = std::numeric_limits<uint64_t>::max();
+  for (auto it = elf->begin_program_headers(); it != elf->end_program_headers(); ++it) {
+    if ((it->p_type == llvm::ELF::PT_LOAD) && (it->p_flags & llvm::ELF::PF_X)) {
+      if (it->p_vaddr < min_addr) {
+        min_addr = it->p_vaddr;
+        has_vaddr = true;
+      }
+    }
+  }
+  if (has_vaddr) {
+    *p_vaddr = min_addr;
+  }
+  return has_vaddr;
+}
+
+bool ReadMinExecutableVirtualAddressFromElfFile(const std::string& filename,
+                                                const BuildId& expected_build_id,
+                                                uint64_t* min_vaddr) {
+  auto owning_binary = llvm::object::createBinary(llvm::StringRef(filename));
+  llvm::object::ObjectFile* obj = GetObjectFile(owning_binary, filename, expected_build_id);
+  if (obj == nullptr) {
+    return false;
+  }
+
+  bool result = false;
+  if (auto elf = llvm::dyn_cast<llvm::object::ELF32LEObjectFile>(obj)) {
+    result = ReadMinExecutableVirtualAddress(elf->getELFFile(), min_vaddr);
+  } else if (auto elf = llvm::dyn_cast<llvm::object::ELF64LEObjectFile>(obj)) {
+    result = ReadMinExecutableVirtualAddress(elf->getELFFile(), min_vaddr);
+  } else {
+    LOG(ERROR) << "unknown elf format in file" << filename;
+    return false;
+  }
+
+  if (!result) {
+    LOG(ERROR) << "no program header in file " << filename;
+  }
+  return result;
+}
diff --git a/simpleperf/read_elf.h b/simpleperf/read_elf.h
index 439d6bc4..cc33211f 100644
--- a/simpleperf/read_elf.h
+++ b/simpleperf/read_elf.h
@@ -29,7 +29,6 @@ static const std::string linker_prefix = "__dl_";
 
 struct ElfFileSymbol {
   uint64_t vaddr;
-  uint64_t start_in_file;
   uint64_t len;
   bool is_func;
   bool is_label;
@@ -40,6 +39,10 @@ struct ElfFileSymbol {
 bool ParseSymbolsFromElfFile(const std::string& filename, const BuildId& expected_build_id,
                              std::function<void(const ElfFileSymbol&)> callback);
 
+bool ReadMinExecutableVirtualAddressFromElfFile(const std::string& filename,
+                                                const BuildId& expected_build_id,
+                                                uint64_t* min_addr);
+
 // Expose the following functions for unit tests.
 bool IsArmMappingSymbol(const char* name);
 
diff --git a/simpleperf/thread_tree.cpp b/simpleperf/thread_tree.cpp
index 27b8583d..a45992c9 100644
--- a/simpleperf/thread_tree.cpp
+++ b/simpleperf/thread_tree.cpp
@@ -28,8 +28,8 @@ 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->get_end_addr() != map2->get_end_addr()) {
+    return map1->get_end_addr() < map2->get_end_addr();
   }
   if (map1->time != map2->time) {
     return map1->time < map2->time;
@@ -75,19 +75,6 @@ ThreadEntry* ThreadTree::FindThreadOrNew(int pid, int 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.
@@ -95,11 +82,8 @@ void ThreadTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff,
     return;
   }
   Dso* 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);
+  MapEntry* map = AllocateMap(MapEntry(start_addr, len, pgoff, time, dso));
+  FixOverlappedMap(&kernel_map_tree_, map);
   auto pair = kernel_map_tree_.insert(map);
   CHECK(pair.second);
 }
@@ -123,11 +107,8 @@ void ThreadTree::AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t le
                               uint64_t time, const std::string& filename) {
   ThreadEntry* thread = FindThreadOrNew(pid, tid);
   Dso* 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);
+  MapEntry* map = AllocateMap(MapEntry(start_addr, len, pgoff, time, dso));
+  FixOverlappedMap(&thread->maps, map);
   auto pair = thread->maps.insert(map);
   CHECK(pair.second);
 }
@@ -141,19 +122,47 @@ Dso* ThreadTree::FindUserDsoOrNew(const std::string& filename) {
   return it->second.get();
 }
 
+MapEntry* ThreadTree::AllocateMap(const MapEntry& value) {
+  MapEntry* map = new MapEntry(value);
+  map_storage_.push_back(std::unique_ptr<MapEntry>(map));
+  return map;
+}
+
+void ThreadTree::FixOverlappedMap(std::set<MapEntry*, MapComparator>* map_set, const MapEntry* map) {
+  for (auto it = map_set->begin(); it != map_set->end();) {
+    if ((*it)->start_addr >= map->get_end_addr()) {
+      // No more overlapped maps.
+      break;
+    }
+    if ((*it)->get_end_addr() <= map->start_addr) {
+      ++it;
+    } else {
+      MapEntry* old = *it;
+      if (old->start_addr < map->start_addr) {
+        MapEntry* before = AllocateMap(MapEntry(old->start_addr, map->start_addr - old->start_addr,
+                                                old->pgoff, old->time, old->dso));
+        map_set->insert(before);
+      }
+      if (old->get_end_addr() > map->get_end_addr()) {
+        MapEntry* after = AllocateMap(
+            MapEntry(map->get_end_addr(), old->get_end_addr() - map->get_end_addr(),
+                     map->get_end_addr() - old->start_addr + old->pgoff, old->time, old->dso));
+        map_set->insert(after);
+      }
+
+      it = map_set->erase(it);
+    }
+  }
+}
+
 static bool IsAddrInMap(uint64_t addr, const MapEntry* map) {
-  return (addr >= map->start_addr && addr < map->start_addr + map->len);
+  return (addr >= map->start_addr && addr < map->get_end_addr());
 }
 
 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
-      std::numeric_limits<unsigned long long>::max(),  // len
-      0,                                               // pgoff
-      std::numeric_limits<unsigned long long>::max(),  // time
-      nullptr,                                         // dso
-  };
+  MapEntry find_map(addr, std::numeric_limits<uint64_t>::max(), 0,
+                    std::numeric_limits<uint64_t>::max(), nullptr);
   auto it = maps.upper_bound(&find_map);
   if (it != maps.begin() && IsAddrInMap(addr, *--it)) {
     return *it;
@@ -172,13 +181,13 @@ const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip, bool
 }
 
 const Symbol* ThreadTree::FindSymbol(const MapEntry* map, uint64_t ip) {
-  uint64_t offset_in_file;
+  uint64_t vaddr_in_file;
   if (map->dso == kernel_dso_.get()) {
-    offset_in_file = ip;
+    vaddr_in_file = ip;
   } else {
-    offset_in_file = ip - map->start_addr + map->pgoff;
+    vaddr_in_file = ip - map->start_addr + map->dso->MinVirtualAddress();
   }
-  const Symbol* symbol = map->dso->FindSymbol(offset_in_file);
+  const Symbol* symbol = map->dso->FindSymbol(vaddr_in_file);
   if (symbol == nullptr) {
     symbol = &unknown_symbol_;
   }
diff --git a/simpleperf/thread_tree.h b/simpleperf/thread_tree.h
index 7abfdfc3..2d689e73 100644
--- a/simpleperf/thread_tree.h
+++ b/simpleperf/thread_tree.h
@@ -31,6 +31,16 @@ struct MapEntry {
   uint64_t pgoff;
   uint64_t time;  // Map creation time.
   Dso* dso;
+
+  MapEntry(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time, Dso* dso)
+      : start_addr(start_addr), len(len), pgoff(pgoff), time(time), dso(dso) {
+  }
+  MapEntry() {
+  }
+
+  uint64_t get_end_addr() const {
+    return start_addr + len;
+  }
 };
 
 struct MapComparator {
@@ -48,13 +58,8 @@ class ThreadTree {
  public:
   ThreadTree() : unknown_symbol_("unknown", 0, std::numeric_limits<unsigned long long>::max()) {
     unknown_dso_ = Dso::CreateDso(DSO_ELF_FILE, "unknown");
-    unknown_map_ = MapEntry{
-        0,                                               // start_addr
-        std::numeric_limits<unsigned long long>::max(),  // len
-        0,                                               // pgoff
-        0,                                               // time
-        unknown_dso_.get(),                              // dso
-    };
+    unknown_map_ =
+        MapEntry(0, std::numeric_limits<unsigned long long>::max(), 0, 0, unknown_dso_.get());
   }
 
   void AddThread(int pid, int tid, const std::string& comm);
@@ -73,6 +78,8 @@ class ThreadTree {
  private:
   Dso* FindKernelDsoOrNew(const std::string& filename);
   Dso* FindUserDsoOrNew(const std::string& filename);
+  MapEntry* AllocateMap(const MapEntry& value);
+  void FixOverlappedMap(std::set<MapEntry*, MapComparator>* map_set, const MapEntry* map);
 
   std::unordered_map<int, std::unique_ptr<ThreadEntry>> thread_tree_;
   std::vector<std::unique_ptr<std::string>> thread_comm_storage_;