Cache DWARF location rules for a given pc.

Decoding the DWARF opcodes is expensive so make sure we cache it.

This speeds unwinding in simpleperf by over a factor of 3x.

Add unit tests for this new behavior.

Bug: 77258731

Test: libbacktrace/libunwindstack unit tests on host and target.
Test: Ran debuggerd -b on various processes on target.
Change-Id: Ia516c0fa5d3e5f76746190bb4b6fdf49fd1c9388

6 files changed, 111 insertions, 15 deletions

diff --git a/libunwindstack/DwarfCfa.cpp b/libunwindstack/DwarfCfa.cpp
index aa8cd3a..6ecedce 100644
--- a/libunwindstack/DwarfCfa.cpp
+++ b/libunwindstack/DwarfCfa.cpp
@@ -50,7 +50,17 @@ bool DwarfCfa<AddressType>::GetLocationInfo(uint64_t pc, uint64_t start_offset,
   memory_->set_cur_offset(start_offset);
   uint64_t cfa_offset;
   cur_pc_ = fde_->pc_start;
-  while ((cfa_offset = memory_->cur_offset()) < end_offset && cur_pc_ <= pc) {
+  loc_regs->pc_start = cur_pc_;
+  while (true) {
+    if (cur_pc_ > pc) {
+      loc_regs->pc_end = cur_pc_;
+      return true;
+    }
+    if ((cfa_offset = memory_->cur_offset()) >= end_offset) {
+      loc_regs->pc_end = fde_->pc_end;
+      return true;
+    }
+    loc_regs->pc_start = cur_pc_;
     operands_.clear();
     // Read the cfa information.
     uint8_t cfa_value;
@@ -129,7 +139,6 @@ bool DwarfCfa<AddressType>::GetLocationInfo(uint64_t pc, uint64_t start_offset,
       }
     }
   }
-  return true;
 }
 
 template <typename AddressType>
diff --git a/libunwindstack/DwarfSection.cpp b/libunwindstack/DwarfSection.cpp
index 5586e72..65eec65 100644
--- a/libunwindstack/DwarfSection.cpp
+++ b/libunwindstack/DwarfSection.cpp
@@ -55,21 +55,29 @@ const DwarfFde* DwarfSection::GetFdeFromPc(uint64_t pc) {
 }
 
 bool DwarfSection::Step(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished) {
-  last_error_.code = DWARF_ERROR_NONE;
-  const DwarfFde* fde = GetFdeFromPc(pc);
-  if (fde == nullptr || fde->cie == nullptr) {
-    last_error_.code = DWARF_ERROR_ILLEGAL_STATE;
-    return false;
-  }
+  // Lookup the pc in the cache.
+  auto it = loc_regs_.upper_bound(pc);
+  if (it == loc_regs_.end() || pc < it->second.pc_start) {
+    last_error_.code = DWARF_ERROR_NONE;
+    const DwarfFde* fde = GetFdeFromPc(pc);
+    if (fde == nullptr || fde->cie == nullptr) {
+      last_error_.code = DWARF_ERROR_ILLEGAL_STATE;
+      return false;
+    }
 
-  // Now get the location information for this pc.
-  dwarf_loc_regs_t loc_regs;
-  if (!GetCfaLocationInfo(pc, fde, &loc_regs)) {
-    return false;
+    // Now get the location information for this pc.
+    dwarf_loc_regs_t loc_regs;
+    if (!GetCfaLocationInfo(pc, fde, &loc_regs)) {
+      return false;
+    }
+    loc_regs.cie = fde->cie;
+
+    // Store it in the cache.
+    it = loc_regs_.emplace(loc_regs.pc_end, std::move(loc_regs)).first;
   }
 
   // Now eval the actual registers.
-  return Eval(fde->cie, process_memory, loc_regs, regs, finished);
+  return Eval(it->second.cie, process_memory, it->second, regs, finished);
 }
 
 template <typename AddressType>
diff --git a/libunwindstack/include/unwindstack/DwarfLocation.h b/libunwindstack/include/unwindstack/DwarfLocation.h
index 0881182..3d50ccf 100644
--- a/libunwindstack/include/unwindstack/DwarfLocation.h
+++ b/libunwindstack/include/unwindstack/DwarfLocation.h
@@ -23,6 +23,8 @@
 
 namespace unwindstack {
 
+struct DwarfCie;
+
 enum DwarfLocationEnum : uint8_t {
   DWARF_LOCATION_INVALID = 0,
   DWARF_LOCATION_UNDEFINED,
@@ -38,7 +40,13 @@ struct DwarfLocation {
   uint64_t values[2];
 };
 
-typedef std::unordered_map<uint32_t, DwarfLocation> dwarf_loc_regs_t;
+struct DwarfLocations : public std::unordered_map<uint32_t, DwarfLocation> {
+  const DwarfCie* cie;
+  // The range of PCs where the locations are valid (end is exclusive).
+  uint64_t pc_start = 0;
+  uint64_t pc_end = 0;
+};
+typedef DwarfLocations dwarf_loc_regs_t;
 
 }  // namespace unwindstack
 
diff --git a/libunwindstack/include/unwindstack/DwarfSection.h b/libunwindstack/include/unwindstack/DwarfSection.h
index da91fd0..209c54a 100644
--- a/libunwindstack/include/unwindstack/DwarfSection.h
+++ b/libunwindstack/include/unwindstack/DwarfSection.h
@@ -20,6 +20,7 @@
 #include <stdint.h>
 
 #include <iterator>
+#include <map>
 #include <unordered_map>
 
 #include <unwindstack/DwarfError.h>
@@ -112,6 +113,7 @@ class DwarfSection {
   std::unordered_map<uint64_t, DwarfFde> fde_entries_;
   std::unordered_map<uint64_t, DwarfCie> cie_entries_;
   std::unordered_map<uint64_t, dwarf_loc_regs_t> cie_loc_regs_;
+  std::map<uint64_t, dwarf_loc_regs_t> loc_regs_;  // Single row indexed by pc_end.
 };
 
 template <typename AddressType>
diff --git a/libunwindstack/tests/DwarfSectionImplTest.cpp b/libunwindstack/tests/DwarfSectionImplTest.cpp
index c85764c..c340291 100644
--- a/libunwindstack/tests/DwarfSectionImplTest.cpp
+++ b/libunwindstack/tests/DwarfSectionImplTest.cpp
@@ -853,7 +853,8 @@ TYPED_TEST_P(DwarfSectionImplTest, GetCfaLocationInfo_cie_cached) {
   fde.cfa_instructions_offset = 0x6000;
   fde.cfa_instructions_end = 0x6002;
 
-  dwarf_loc_regs_t cie_loc_regs{{6, {DWARF_LOCATION_REGISTER, {4, 0}}}};
+  dwarf_loc_regs_t cie_loc_regs;
+  cie_loc_regs[6] = DwarfLocation{DWARF_LOCATION_REGISTER, {4, 0}};
   this->section_->TestSetCachedCieLocRegs(0x8000, cie_loc_regs);
   this->memory_.SetMemory(0x6000, std::vector<uint8_t>{0x09, 0x04, 0x03});
 
diff --git a/libunwindstack/tests/DwarfSectionTest.cpp b/libunwindstack/tests/DwarfSectionTest.cpp
index 3fcd2b6..071d2df 100644
--- a/libunwindstack/tests/DwarfSectionTest.cpp
+++ b/libunwindstack/tests/DwarfSectionTest.cpp
@@ -165,4 +165,72 @@ TEST_F(DwarfSectionTest, Step_pass) {
   ASSERT_TRUE(mock_section.Step(0x1000, nullptr, &process, &finished));
 }
 
+static bool MockGetCfaLocationInfo(::testing::Unused, const DwarfFde* fde,
+                                   dwarf_loc_regs_t* loc_regs) {
+  loc_regs->pc_start = fde->pc_start;
+  loc_regs->pc_end = fde->pc_end;
+  return true;
+}
+
+TEST_F(DwarfSectionTest, Step_cache) {
+  MockDwarfSection mock_section(&memory_);
+
+  DwarfCie cie{};
+  DwarfFde fde{};
+  fde.pc_start = 0x500;
+  fde.pc_end = 0x2000;
+  fde.cie = &cie;
+
+  EXPECT_CALL(mock_section, GetFdeOffsetFromPc(0x1000, ::testing::_))
+      .WillOnce(::testing::Return(true));
+  EXPECT_CALL(mock_section, GetFdeFromOffset(::testing::_)).WillOnce(::testing::Return(&fde));
+
+  EXPECT_CALL(mock_section, GetCfaLocationInfo(0x1000, &fde, ::testing::_))
+      .WillOnce(::testing::Invoke(MockGetCfaLocationInfo));
+
+  MemoryFake process;
+  EXPECT_CALL(mock_section, Eval(&cie, &process, ::testing::_, nullptr, ::testing::_))
+      .WillRepeatedly(::testing::Return(true));
+
+  bool finished;
+  ASSERT_TRUE(mock_section.Step(0x1000, nullptr, &process, &finished));
+  ASSERT_TRUE(mock_section.Step(0x1000, nullptr, &process, &finished));
+  ASSERT_TRUE(mock_section.Step(0x1500, nullptr, &process, &finished));
+}
+
+TEST_F(DwarfSectionTest, Step_cache_not_in_pc) {
+  MockDwarfSection mock_section(&memory_);
+
+  DwarfCie cie{};
+  DwarfFde fde0{};
+  fde0.pc_start = 0x1000;
+  fde0.pc_end = 0x2000;
+  fde0.cie = &cie;
+  EXPECT_CALL(mock_section, GetFdeOffsetFromPc(0x1000, ::testing::_))
+      .WillOnce(::testing::Return(true));
+  EXPECT_CALL(mock_section, GetFdeFromOffset(::testing::_)).WillOnce(::testing::Return(&fde0));
+  EXPECT_CALL(mock_section, GetCfaLocationInfo(0x1000, &fde0, ::testing::_))
+      .WillOnce(::testing::Invoke(MockGetCfaLocationInfo));
+
+  MemoryFake process;
+  EXPECT_CALL(mock_section, Eval(&cie, &process, ::testing::_, nullptr, ::testing::_))
+      .WillRepeatedly(::testing::Return(true));
+
+  bool finished;
+  ASSERT_TRUE(mock_section.Step(0x1000, nullptr, &process, &finished));
+
+  DwarfFde fde1{};
+  fde1.pc_start = 0x500;
+  fde1.pc_end = 0x800;
+  fde1.cie = &cie;
+  EXPECT_CALL(mock_section, GetFdeOffsetFromPc(0x600, ::testing::_))
+      .WillOnce(::testing::Return(true));
+  EXPECT_CALL(mock_section, GetFdeFromOffset(::testing::_)).WillOnce(::testing::Return(&fde1));
+  EXPECT_CALL(mock_section, GetCfaLocationInfo(0x600, &fde1, ::testing::_))
+      .WillOnce(::testing::Invoke(MockGetCfaLocationInfo));
+
+  ASSERT_TRUE(mock_section.Step(0x600, nullptr, &process, &finished));
+  ASSERT_TRUE(mock_section.Step(0x700, nullptr, &process, &finished));
+}
+
 }  // namespace unwindstack