Perfprofd: Implement symbolization over quipper data

Reimplement the symbolization post-process step to walk quipper
protobufs, looking for mapped files without build ID data.

(cherry picked from commit cbc02bc7a2e84f90f11b3b066ec0aeb66c3d38eb)

Bug: 73175642
Test: mmma system/extras/perfprofd
Test: perfprofd_test
Merged-In: I7c27b09b6a7f9c743472837962021845b2f4db7f
Change-Id: I7c27b09b6a7f9c743472837962021845b2f4db7f

7 files changed, 390 insertions, 12 deletions

diff --git a/perfprofd/binder_interface/perfprofd_binder.cc b/perfprofd/binder_interface/perfprofd_binder.cc
index 184d38c1..6667ca5e 100644
--- a/perfprofd/binder_interface/perfprofd_binder.cc
+++ b/perfprofd/binder_interface/perfprofd_binder.cc
@@ -60,7 +60,7 @@ using Status = ::android::binder::Status;
 
 class BinderConfig : public Config {
  public:
-  bool send_to_dropbox = true;
+  bool send_to_dropbox = false;
 
   bool is_profiling = false;
 
diff --git a/perfprofd/map_utils.h b/perfprofd/map_utils.h
new file mode 100644
index 00000000..2e3d97d9
--- /dev/null
+++ b/perfprofd/map_utils.h
@@ -0,0 +1,129 @@
+#ifndef SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_
+#define SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_
+
+#include <map>
+#include <set>
+
+#include <android-base/logging.h>
+
+namespace android {
+namespace perfprofd {
+
+template <typename T, typename U>
+decltype(static_cast<T*>(nullptr)->begin()) GetLeqIterator(T& map, U key) {
+  if (map.empty()) {
+    return map.end();
+  }
+  auto it = map.upper_bound(key);
+  if (it == map.begin()) {
+    return map.end();
+  }
+  --it;
+  return it;
+}
+
+template <typename SymType, typename ValType>
+class RangeMap {
+ public:
+  struct AggregatedSymbol {
+    SymType symbol;
+    std::set<ValType> offsets;
+    AggregatedSymbol(const SymType& sym, const ValType& offset) : symbol(sym) {
+      offsets.insert(offset);
+    }
+  };
+
+ public:
+  void Insert(const SymType& sym, const ValType& val) {
+    auto aggr_it = GetLeqIterator(map_, val);
+    if (aggr_it == map_.end()) {
+      // Maybe we need to extend the first one.
+      if (!map_.empty()) {
+        AggregatedSymbol& first = map_.begin()->second;
+        CHECK_LT(val, map_.begin()->first);
+        if (first.symbol == sym) {
+          ExtendLeft(map_.begin(), val);
+          return;
+        }
+      }
+      // Nope, new entry needed.
+      map_.emplace(val, AggregatedSymbol(sym, val));
+      return;
+    }
+
+    AggregatedSymbol& maybe_match = aggr_it->second;
+
+    if (maybe_match.symbol == sym) {
+      // Same symbol, just insert. This is true for overlap as well as extension.
+      maybe_match.offsets.insert(val);
+      return;
+    }
+
+    // Is there overlap?
+    if (*maybe_match.offsets.rbegin() < val) {
+      // No. See if it can be merged with the next one.
+      ++aggr_it;
+      if (aggr_it != map_.end() && aggr_it->second.symbol == sym) {
+        ExtendLeft(aggr_it, val);
+        return;
+      }
+
+      // Just add a new symbol entry.
+      map_.emplace(val, AggregatedSymbol(sym, val));
+      return;
+    }
+
+    // OK, we have an overlapping non-symbol-equal AggregatedSymbol. Need to break
+    // things up.
+    AggregatedSymbol left(maybe_match.symbol, *maybe_match.offsets.begin());
+    auto offset_it = maybe_match.offsets.begin();
+    for (; *offset_it < val; ++offset_it) {
+      left.offsets.insert(*offset_it);
+    }
+
+    if (*offset_it == val) {
+      // This should not happen.
+      LOG(ERROR) << "Unexpected overlap!";
+      return;
+    }
+
+    AggregatedSymbol right(maybe_match.symbol, *offset_it);
+    for (; offset_it != maybe_match.offsets.end(); ++offset_it) {
+      right.offsets.insert(*offset_it);
+    }
+
+    map_.erase(aggr_it);
+    map_.emplace(*left.offsets.begin(), std::move(left));
+    map_.emplace(val, AggregatedSymbol(sym, val));
+    map_.emplace(*right.offsets.begin(), std::move(right));
+  }
+
+  using RangeMapType = std::map<ValType, AggregatedSymbol>;
+
+  typename RangeMapType::const_iterator begin() const {
+    return map_.begin();
+  }
+  typename RangeMapType::const_iterator end() const {
+    return map_.end();
+  }
+
+  bool empty() const {
+    return map_.empty();
+  }
+
+ private:
+  void ExtendLeft(typename RangeMapType::iterator it, const ValType& val) {
+    CHECK(val < *it->second.offsets.begin());
+    AggregatedSymbol copy = std::move(it->second);
+    map_.erase(it);
+    copy.offsets.insert(val);
+    map_.emplace(val, std::move(copy));
+  }
+
+  RangeMapType map_;
+};
+
+}  // namespace perfprofd
+}  // namespace android
+
+#endif  // SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_
diff --git a/perfprofd/perf_data_converter.cc b/perfprofd/perf_data_converter.cc
index ffd1444d..f94cc861 100644
--- a/perfprofd/perf_data_converter.cc
+++ b/perfprofd/perf_data_converter.cc
@@ -5,15 +5,21 @@
 #include <limits>
 #include <map>
 #include <memory>
+#include <set>
 #include <unordered_map>
 
+#include <android-base/logging.h>
 #include <android-base/macros.h>
 #include <android-base/strings.h>
+#include <perf_data_utils.h>
 #include <perf_parser.h>
 #include <perf_protobuf_io.h>
 
 #include "perfprofd_record.pb.h"
+#include "perf_data.pb.h"
 
+#include "map_utils.h"
+#include "quipper_helper.h"
 #include "symbolizer.h"
 
 using std::map;
@@ -21,24 +27,163 @@ using std::map;
 namespace android {
 namespace perfprofd {
 
+namespace {
+
+void AddSymbolInfo(PerfprofdRecord* record,
+                   ::quipper::PerfParser& perf_parser,
+                   ::perfprofd::Symbolizer* symbolizer) {
+  std::unordered_set<std::string> filenames_w_build_id;
+  for (auto& perf_build_id : record->perf_data().build_ids()) {
+    filenames_w_build_id.insert(perf_build_id.filename());
+  }
+
+  std::unordered_set<std::string> files_wo_build_id;
+  {
+    quipper::MmapEventIterator it(record->perf_data());
+    for (; it != it.end(); ++it) {
+      const ::quipper::PerfDataProto_MMapEvent* mmap_event = &it->mmap_event();
+      if (!mmap_event->has_filename() || !mmap_event->has_start() || !mmap_event->has_len()) {
+        // Don't care.
+        continue;
+      }
+      if (filenames_w_build_id.count(mmap_event->filename()) == 0) {
+        files_wo_build_id.insert(mmap_event->filename());
+      }
+    }
+  }
+  if (files_wo_build_id.empty()) {
+    return;
+  }
+
+  struct Dso {
+    uint64_t min_vaddr;
+    RangeMap<std::string, uint64_t> symbols;
+    explicit Dso(uint64_t min_vaddr_in) : min_vaddr(min_vaddr_in) {
+    }
+  };
+  std::unordered_map<std::string, Dso> files;
+
+  auto it = record->perf_data().events().begin();
+  auto end = record->perf_data().events().end();
+  auto parsed_it = perf_parser.parsed_events().begin();
+  auto parsed_end = perf_parser.parsed_events().end();
+  for (; it != end; ++it, ++parsed_it) {
+    CHECK(parsed_it != parsed_end);
+    if (!it->has_sample_event()) {
+      continue;
+    }
+
+    const ::quipper::PerfDataProto_SampleEvent& sample_event = it->sample_event();
+
+    if (android::base::kEnableDChecks) {
+      // Check that the parsed_event and sample_event are consistent.
+      CHECK_EQ(parsed_it->callchain.size(), sample_event.callchain_size());
+    }
+
+    auto check_address = [&](const std::string& dso_name, uint64_t offset) {
+      if (files_wo_build_id.count(dso_name) == 0) {
+        return;
+      }
+
+      // OK, that's a hit in the mmap segment (w/o build id).
+
+      Dso* dso_data;
+      {
+        auto dso_it = files.find(dso_name);
+        constexpr uint64_t kNoMinAddr = std::numeric_limits<uint64_t>::max();
+        if (dso_it == files.end()) {
+          uint64_t min_vaddr;
+          bool has_min_vaddr = symbolizer->GetMinExecutableVAddr(dso_name, &min_vaddr);
+          if (!has_min_vaddr) {
+            min_vaddr = kNoMinAddr;
+          }
+          auto it = files.emplace(dso_name, Dso(min_vaddr));
+          dso_data = &it.first->second;
+        } else {
+          dso_data = &dso_it->second;
+        }
+        if (dso_data->min_vaddr == kNoMinAddr) {
+          return;
+        }
+      }
+
+      // TODO: Is min_vaddr necessary here?
+      const uint64_t file_addr = offset;
+
+      std::string symbol = symbolizer->Decode(dso_name, file_addr);
+      if (symbol.empty()) {
+        return;
+      }
+
+      dso_data->symbols.Insert(symbol, file_addr);
+    };
+    if (sample_event.has_ip() && parsed_it->dso_and_offset.dso_info_ != nullptr) {
+      check_address(parsed_it->dso_and_offset.dso_info_->name, parsed_it->dso_and_offset.offset_);
+    }
+    if (sample_event.callchain_size() > 0) {
+      for (auto& callchain_data: parsed_it->callchain) {
+        if (callchain_data.dso_info_ == nullptr) {
+          continue;
+        }
+        check_address(callchain_data.dso_info_->name, callchain_data.offset_);
+      }
+    }
+  }
+
+  if (!files.empty()) {
+    // We have extra symbol info, create proto messages now.
+    for (auto& file_data : files) {
+      const std::string& filename = file_data.first;
+      const Dso& dso = file_data.second;
+      if (dso.symbols.empty()) {
+        continue;
+      }
+
+      PerfprofdRecord_SymbolInfo* symbol_info = record->add_symbol_info();
+      symbol_info->set_filename(filename);
+      symbol_info->set_filename_md5_prefix(::quipper::Md5Prefix(filename));
+      symbol_info->set_min_vaddr(dso.min_vaddr);
+      for (auto& aggr_sym : dso.symbols) {
+        PerfprofdRecord_SymbolInfo_Symbol* symbol = symbol_info->add_symbols();
+        symbol->set_addr(*aggr_sym.second.offsets.begin());
+        symbol->set_size(*aggr_sym.second.offsets.rbegin() - *aggr_sym.second.offsets.begin() + 1);
+        symbol->set_name(aggr_sym.second.symbol);
+        symbol->set_name_md5_prefix(::quipper::Md5Prefix(aggr_sym.second.symbol));
+      }
+    }
+  }
+}
+
+}  // namespace
+
 PerfprofdRecord*
 RawPerfDataToAndroidPerfProfile(const string &perf_file,
-                                ::perfprofd::Symbolizer* symbolizer ATTRIBUTE_UNUSED) {
+                                ::perfprofd::Symbolizer* symbolizer) {
   std::unique_ptr<PerfprofdRecord> ret(new PerfprofdRecord());
   ret->set_id(0);  // TODO.
 
-  quipper::PerfParserOptions options = {};
+  ::quipper::PerfParserOptions options = {};
   options.do_remap = true;
   options.discard_unused_events = true;
   options.read_missing_buildids = true;
 
-  quipper::PerfDataProto* perf_data = ret->mutable_perf_data();
+  ::quipper::PerfDataProto* perf_data = ret->mutable_perf_data();
 
-  if (!quipper::SerializeFromFileWithOptions(perf_file, options, perf_data)) {
-    return nullptr;
-  }
+  ::quipper::PerfReader reader;
+  if (!reader.ReadFile(perf_file)) return nullptr;
+
+  ::quipper::PerfParser parser(&reader, options);
+  if (!parser.ParseRawEvents()) return nullptr;
+
+  if (!reader.Serialize(perf_data)) return nullptr;
+
+  // Append parser stats to protobuf.
+  ::quipper::PerfSerializer::SerializeParserStats(parser.stats(), perf_data);
 
   // TODO: Symbolization.
+  if (symbolizer != nullptr) {
+    AddSymbolInfo(ret.get(), parser, symbolizer);
+  }
 
   return ret.release();
 }
diff --git a/perfprofd/perfprofd_record.proto b/perfprofd/perfprofd_record.proto
index 95a9d316..08b5fa2b 100644
--- a/perfprofd/perfprofd_record.proto
+++ b/perfprofd/perfprofd_record.proto
@@ -8,9 +8,31 @@ option java_package = "com.google.android.perfprofd";
 package android.perfprofd;
 
 message PerfprofdRecord {
+  // Symbol info for a shared library without build id.
+  message SymbolInfo {
+    // A symbol, stretching the given range of the library.
+    message Symbol {
+      optional string name = 1;
+      optional uint64 name_md5_prefix = 2;
+
+      optional uint64 addr = 3;
+      optional uint64 size = 4;
+    };
+
+    optional string filename = 1;
+    optional uint64 filename_md5_prefix = 2;
+
+    optional uint64 min_vaddr = 3;
+
+    repeated Symbol symbols = 4;
+  };
+
   optional int64 id = 1;
   optional quipper.PerfDataProto perf_data = 2;
 
+  // Extra symbol info.
+  repeated SymbolInfo symbol_info = 3;
+
   // Stats inherited from old perf_profile.proto.
 
   // is device screen on at point when profile is collected?
diff --git a/perfprofd/symbolizer.cc b/perfprofd/symbolizer.cc
index 3f7ea4d1..2be6f96c 100644
--- a/perfprofd/symbolizer.cc
+++ b/perfprofd/symbolizer.cc
@@ -80,6 +80,11 @@ struct SimpleperfSymbolizer : public Symbolizer {
     dsos.emplace(dso, std::move(data));
   }
 
+  bool GetMinExecutableVAddr(const std::string& dso, uint64_t* addr) override {
+    ElfStatus status = ReadMinExecutableVirtualAddressFromElfFile(dso, BuildId(), addr);
+    return status == ElfStatus::NO_ERROR;
+  }
+
   std::unordered_map<std::string, SymbolMap> dsos;
 };
 
diff --git a/perfprofd/symbolizer.h b/perfprofd/symbolizer.h
index 87e8a25e..10771595 100644
--- a/perfprofd/symbolizer.h
+++ b/perfprofd/symbolizer.h
@@ -25,6 +25,7 @@ namespace perfprofd {
 struct Symbolizer {
   virtual ~Symbolizer() {}
   virtual std::string Decode(const std::string& dso, uint64_t address) = 0;
+  virtual bool GetMinExecutableVAddr(const std::string& dso, uint64_t* addr) = 0;
 };
 
 std::unique_ptr<Symbolizer> CreateELFSymbolizer();
diff --git a/perfprofd/tests/perfprofd_test.cc b/perfprofd/tests/perfprofd_test.cc
index 5e8a0e3b..61eb09d2 100644
--- a/perfprofd/tests/perfprofd_test.cc
+++ b/perfprofd/tests/perfprofd_test.cc
@@ -41,6 +41,7 @@
 
 #include "config.h"
 #include "configreader.h"
+#include "map_utils.h"
 #include "perfprofdcore.h"
 #include "quipper_helper.h"
 #include "symbolizer.h"
@@ -85,16 +86,20 @@ class TestLogHelper {
   }
 
  private:
-  void TestLogFunction(LogId log_id ATTRIBUTE_UNUSED,
+  void TestLogFunction(LogId log_id,
                        LogSeverity severity,
                        const char* tag,
-                       const char* file ATTRIBUTE_UNUSED,
-                       unsigned int line ATTRIBUTE_UNUSED,
+                       const char* file,
+                       unsigned int line,
                        const char* message) {
     std::unique_lock<std::mutex> ul(lock_);
     constexpr char log_characters[] = "VDIWEFF";
     char severity_char = log_characters[severity];
     test_log_messages_.push_back(android::base::StringPrintf("%c: %s", severity_char, message));
+
+    if (severity >= LogSeverity::FATAL_WITHOUT_ABORT) {
+      android::base::StderrLogger(log_id, severity, tag, file, line, message);
+    }
   }
 
  private:
@@ -897,7 +902,7 @@ TEST_F(BasicRunWithCannedPerf, Compressed)
   VerifyBasicCannedProfile(encodedProfile);
 }
 
-TEST_F(BasicRunWithCannedPerf, DISABLED_WithSymbolizer)
+TEST_F(BasicRunWithCannedPerf, WithSymbolizer)
 {
   //
   // Verify the portion of the daemon that reads and encodes
@@ -925,6 +930,10 @@ TEST_F(BasicRunWithCannedPerf, DISABLED_WithSymbolizer)
     std::string Decode(const std::string& dso, uint64_t address) override {
       return dso + "@" + std::to_string(address);
     }
+    bool GetMinExecutableVAddr(const std::string& dso, uint64_t* addr) override {
+      *addr = 4096;
+      return true;
+    }
   };
   TestSymbolizer test_symbolizer;
   PROFILE_RESULT result =
@@ -941,7 +950,32 @@ TEST_F(BasicRunWithCannedPerf, DISABLED_WithSymbolizer)
 
   VerifyBasicCannedProfile(encodedProfile);
 
-  // TODO: Re-add symbolization.
+  auto find_symbol = [&](const std::string& filename)
+      -> const android::perfprofd::PerfprofdRecord_SymbolInfo* {
+    for (auto& symbol_info : encodedProfile.symbol_info()) {
+      if (symbol_info.filename() == filename) {
+        return &symbol_info;
+      }
+    }
+    return nullptr;
+  };
+  auto all_filenames = [&]() {
+    std::ostringstream oss;
+    for (auto& symbol_info : encodedProfile.symbol_info()) {
+      oss << " " << symbol_info.filename();
+    }
+    return oss.str();
+  };
+
+  EXPECT_TRUE(find_symbol("/data/app/com.google.android.apps.plus-1/lib/arm/libcronet.so")
+                  != nullptr) << all_filenames() << test_logger.JoinTestLog("\n");
+  EXPECT_TRUE(find_symbol("/data/dalvik-cache/arm/system@framework@wifi-service.jar@classes.dex")
+                  != nullptr) << all_filenames();
+  EXPECT_TRUE(find_symbol("/data/dalvik-cache/arm/data@app@com.google.android.gms-2@base.apk@"
+                          "classes.dex")
+                  != nullptr) << all_filenames();
+  EXPECT_TRUE(find_symbol("/data/dalvik-cache/arm/system@framework@boot.oat") != nullptr)
+      << all_filenames();
 }
 
 TEST_F(PerfProfdTest, CallchainRunWithCannedPerf)
@@ -1221,6 +1255,48 @@ TEST_F(PerfProfdTest, CallChainRunWithLivePerf)
 
 #endif
 
+class RangeMapTest : public testing::Test {
+};
+
+TEST_F(RangeMapTest, TestRangeMap) {
+  using namespace android::perfprofd;
+
+  RangeMap<std::string, uint64_t> map;
+  auto print = [&]() {
+    std::ostringstream oss;
+    for (auto& aggr_sym : map) {
+      oss << aggr_sym.first << "#" << aggr_sym.second.symbol;
+      oss << "[";
+      for (auto& x : aggr_sym.second.offsets) {
+        oss << x << ",";
+      }
+      oss << "]";
+    }
+    return oss.str();
+  };
+
+  EXPECT_STREQ("", print().c_str());
+
+  map.Insert("a", 10);
+  EXPECT_STREQ("10#a[10,]", print().c_str());
+  map.Insert("a", 100);
+  EXPECT_STREQ("10#a[10,100,]", print().c_str());
+  map.Insert("a", 1);
+  EXPECT_STREQ("1#a[1,10,100,]", print().c_str());
+  map.Insert("a", 1);
+  EXPECT_STREQ("1#a[1,10,100,]", print().c_str());
+  map.Insert("a", 2);
+  EXPECT_STREQ("1#a[1,2,10,100,]", print().c_str());
+
+  map.Insert("b", 200);
+  EXPECT_STREQ("1#a[1,2,10,100,]200#b[200,]", print().c_str());
+  map.Insert("b", 199);
+  EXPECT_STREQ("1#a[1,2,10,100,]199#b[199,200,]", print().c_str());
+
+  map.Insert("c", 50);
+  EXPECT_STREQ("1#a[1,2,10,]50#c[50,]100#a[100,]199#b[199,200,]", print().c_str());
+}
+
 int main(int argc, char **argv) {
   // Always log to cerr, so that device failures are visible.
   android::base::SetLogger(android::base::StderrLogger);