Refactor symbol caching.
The O(1) hashmap lookup still showed up in profiles.
(because it is in the hot O(log n) binary search loop)
Refactor the caching to use O(log n) map for the cache,
but pull it outside the binary search loop.
This speeds up the symbol lookup by 2x in perfetto.
Same speed up for BM_symbol_find_single_many_times.
Bug: 169745438
Test: libunwindstack_test
Change-Id: Icbe16bd77b8fa72269f2c71c67740b663efee507
diff --git a/libunwindstack/Symbols.cpp b/libunwindstack/Symbols.cpp
index 2117ebd..3fb175c 100644
--- a/libunwindstack/Symbols.cpp
+++ b/libunwindstack/Symbols.cpp
@@ -41,45 +41,40 @@
return entry->st_shndx != SHN_UNDEF && ELF32_ST_TYPE(entry->st_info) == STT_FUNC;
}
-// Read symbol entry from memory and cache it so we don't have to read it again.
-template <typename SymType>
-inline __attribute__((__always_inline__)) const Symbols::Info* Symbols::ReadFuncInfo(
- uint32_t symbol_index, Memory* elf_memory) {
- auto it = symbols_.find(symbol_index);
- if (it != symbols_.end()) {
- return &it->second;
- }
- SymType sym;
- if (!elf_memory->ReadFully(offset_ + symbol_index * entry_size_, &sym, sizeof(sym))) {
- return nullptr;
- }
- if (!IsFunc(&sym)) {
- // We need the address for binary search, but we don't want it to be matched.
- sym.st_size = 0;
- }
- Info info{.addr = sym.st_value, .size = static_cast<uint32_t>(sym.st_size), .name = sym.st_name};
- return &symbols_.emplace(symbol_index, info).first->second;
-}
-
// Binary search the symbol table to find function containing the given address.
// Without remap, the symbol table is assumed to be sorted and accessed directly.
// If the symbol table is not sorted this method might fail but should not crash.
// When the indices are remapped, they are guaranteed to be sorted by address.
template <typename SymType, bool RemapIndices>
const Symbols::Info* Symbols::BinarySearch(uint64_t addr, Memory* elf_memory) {
- size_t first = 0;
- size_t last = RemapIndices ? remap_->size() : count_;
+ // Fast-path: Check if the symbol has been already read from memory.
+ // Otherwise use the cache iterator to constrain the binary search range.
+ // (the symbol must be in the gap between this and the previous iterator)
+ auto it = symbols_.upper_bound(addr);
+ if (it != symbols_.end() && it->second.addr <= addr) {
+ return &it->second;
+ }
+ uint32_t count = RemapIndices ? remap_->size() : count_;
+ uint32_t last = (it != symbols_.end()) ? it->second.index : count;
+ uint32_t first = (it != symbols_.begin()) ? std::prev(it)->second.index + 1 : 0;
+
while (first < last) {
- size_t current = first + (last - first) / 2;
- size_t symbol_index = RemapIndices ? remap_.value()[current] : current;
- const Info* info = ReadFuncInfo<SymType>(symbol_index, elf_memory);
- if (info == nullptr) {
+ uint32_t current = first + (last - first) / 2;
+ uint32_t symbol_index = RemapIndices ? remap_.value()[current] : current;
+ SymType sym;
+ if (!elf_memory->ReadFully(offset_ + symbol_index * entry_size_, &sym, sizeof(sym))) {
return nullptr;
}
- if (addr < info->addr) {
+ Info info{
+ .index = current,
+ .addr = sym.st_value,
+ .name = IsFunc(&sym) ? sym.st_name : 0, // Mark non-functions as invalid.
+ };
+ it = symbols_.emplace(sym.st_value + sym.st_size, info).first;
+ if (addr < sym.st_value) {
last = current;
- } else if (addr < info->addr + info->size) {
- return info;
+ } else if (addr < sym.st_value + sym.st_size) {
+ return (it->second.name != 0) ? &it->second : nullptr;
} else {
first = current + 1;
}
diff --git a/libunwindstack/Symbols.h b/libunwindstack/Symbols.h
index 3b3f20b..97c03c2 100644
--- a/libunwindstack/Symbols.h
+++ b/libunwindstack/Symbols.h
@@ -19,9 +19,9 @@
#include <stdint.h>
+#include <map>
#include <optional>
#include <string>
-#include <unordered_map>
namespace unwindstack {
@@ -30,9 +30,9 @@
class Symbols {
struct Info {
- uint64_t addr; // Symbol address.
- uint32_t size; // Symbol size in bytes. Zero if not a function.
- uint32_t name; // Offset in .strtab.
+ uint64_t addr; // Symbol address.
+ uint32_t index; // Index into *sorted* symbol table.
+ uint32_t name; // Offset in .strtab, or 0 if the symbol is not a function.
};
public:
@@ -52,9 +52,6 @@
}
private:
- template <typename SymType>
- const Info* ReadFuncInfo(uint32_t symbol_index, Memory* elf_memory);
-
template <typename SymType, bool RemapIndices>
const Info* BinarySearch(uint64_t addr, Memory* elf_memory);
@@ -67,7 +64,7 @@
const uint64_t str_offset_;
const uint64_t str_end_;
- std::unordered_map<uint32_t, Info> symbols_; // Cache of read symbols (keyed by symbol index).
+ std::map<uint64_t, Info> symbols_; // Cache of read symbols (keyed by function *end* address).
std::optional<std::vector<uint32_t>> remap_; // Indices of function symbols sorted by address.
};
diff --git a/libunwindstack/tests/UnwinderTest.cpp b/libunwindstack/tests/UnwinderTest.cpp
index 8bae242..12c23b3 100644
--- a/libunwindstack/tests/UnwinderTest.cpp
+++ b/libunwindstack/tests/UnwinderTest.cpp
@@ -1728,8 +1728,9 @@
sym.st_info = STT_FUNC;
sym.st_value = 0x100300;
sym.st_size = 0x100;
+ sym.st_name = 1;
memory_->SetMemory(0xf7300, &sym, sizeof(sym));
- memory_->SetMemory(0xf7400, "FakeJitFunction");
+ memory_->SetMemory(0xf7401, "FakeJitFunction");
RegsFake regs(10);
regs.FakeSetArch(ARCH_ARM);
