1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include <elf.h>
18 #include <stdint.h>
19 
20 #include <algorithm>
21 #include <string>
22 #include <vector>
23 
24 #include <unwindstack/Memory.h>
25 
26 #include "Check.h"
27 #include "Symbols.h"
28 
29 namespace unwindstack {
30 
Symbols(uint64_t offset,uint64_t size,uint64_t entry_size,uint64_t str_offset,uint64_t str_size)31 Symbols::Symbols(uint64_t offset, uint64_t size, uint64_t entry_size, uint64_t str_offset,
32                  uint64_t str_size)
33     : offset_(offset),
34       count_(entry_size != 0 ? size / entry_size : 0),
35       entry_size_(entry_size),
36       str_offset_(str_offset),
37       str_end_(str_offset_ + str_size) {}
38 
39 template <typename SymType>
IsFunc(const SymType * entry)40 static bool IsFunc(const SymType* entry) {
41   return entry->st_shndx != SHN_UNDEF && ELF32_ST_TYPE(entry->st_info) == STT_FUNC;
42 }
43 
44 // Read symbol entry from memory and cache it so we don't have to read it again.
45 template <typename SymType>
ReadFuncInfo(uint32_t symbol_index,Memory * elf_memory)46 inline __attribute__((__always_inline__)) const Symbols::Info* Symbols::ReadFuncInfo(
47     uint32_t symbol_index, Memory* elf_memory) {
48   auto it = symbols_.find(symbol_index);
49   if (it != symbols_.end()) {
50     return &it->second;
51   }
52   SymType sym;
53   if (!elf_memory->ReadFully(offset_ + symbol_index * entry_size_, &sym, sizeof(sym))) {
54     return nullptr;
55   }
56   if (!IsFunc(&sym)) {
57     // We need the address for binary search, but we don't want it to be matched.
58     sym.st_size = 0;
59   }
60   Info info{.addr = sym.st_value, .size = static_cast<uint32_t>(sym.st_size), .name = sym.st_name};
61   return &symbols_.emplace(symbol_index, info).first->second;
62 }
63 
64 // Binary search the symbol table to find function containing the given address.
65 // Without remap, the symbol table is assumed to be sorted and accessed directly.
66 // If the symbol table is not sorted this method might fail but should not crash.
67 // When the indices are remapped, they are guaranteed to be sorted by address.
68 template <typename SymType, bool RemapIndices>
BinarySearch(uint64_t addr,Memory * elf_memory)69 const Symbols::Info* Symbols::BinarySearch(uint64_t addr, Memory* elf_memory) {
70   size_t first = 0;
71   size_t last = RemapIndices ? remap_->size() : count_;
72   while (first < last) {
73     size_t current = first + (last - first) / 2;
74     size_t symbol_index = RemapIndices ? remap_.value()[current] : current;
75     const Info* info = ReadFuncInfo<SymType>(symbol_index, elf_memory);
76     if (info == nullptr) {
77       return nullptr;
78     }
79     if (addr < info->addr) {
80       last = current;
81     } else if (addr < info->addr + info->size) {
82       return info;
83     } else {
84       first = current + 1;
85     }
86   }
87   return nullptr;
88 }
89 
90 // Create remapping table which allows us to access symbols as if they were sorted by address.
91 template <typename SymType>
BuildRemapTable(Memory * elf_memory)92 void Symbols::BuildRemapTable(Memory* elf_memory) {
93   std::vector<uint64_t> addrs;  // Addresses of all symbols (addrs[i] == symbols[i].st_value).
94   addrs.reserve(count_);
95   remap_.emplace();  // Construct the optional remap table.
96   remap_->reserve(count_);
97   for (size_t symbol_idx = 0; symbol_idx < count_;) {
98     // Read symbols from memory.  We intentionally bypass the cache to save memory.
99     // Do the reads in batches so that we minimize the number of memory read calls.
100     uint8_t buffer[1024];
101     size_t read = std::min<size_t>(sizeof(buffer), (count_ - symbol_idx) * entry_size_);
102     size_t size = elf_memory->Read(offset_ + symbol_idx * entry_size_, buffer, read);
103     if (size < sizeof(SymType)) {
104       break;  // Stop processing, something looks like it is corrupted.
105     }
106     for (size_t offset = 0; offset + sizeof(SymType) <= size; offset += entry_size_, symbol_idx++) {
107       SymType sym;
108       memcpy(&sym, &buffer[offset], sizeof(SymType));  // Copy to ensure alignment.
109       addrs.push_back(sym.st_value);  // Always insert so it is indexable by symbol index.
110       if (IsFunc(&sym)) {
111         remap_->push_back(symbol_idx);  // Indices of function symbols only.
112       }
113     }
114   }
115   // Sort by address to make the remap list binary searchable (stable due to the a<b tie break).
116   auto comp = [&addrs](auto a, auto b) { return std::tie(addrs[a], a) < std::tie(addrs[b], b); };
117   std::sort(remap_->begin(), remap_->end(), comp);
118   // Remove duplicate entries (methods de-duplicated by the linker).
119   auto pred = [&addrs](auto a, auto b) { return addrs[a] == addrs[b]; };
120   remap_->erase(std::unique(remap_->begin(), remap_->end(), pred), remap_->end());
121   remap_->shrink_to_fit();
122 }
123 
124 template <typename SymType>
GetName(uint64_t addr,Memory * elf_memory,std::string * name,uint64_t * func_offset)125 bool Symbols::GetName(uint64_t addr, Memory* elf_memory, std::string* name, uint64_t* func_offset) {
126   const Info* info;
127   if (!remap_.has_value()) {
128     // Assume the symbol table is sorted. If it is not, this will gracefully fail.
129     info = BinarySearch<SymType, false>(addr, elf_memory);
130     if (info == nullptr) {
131       // Create the remapping table and retry the search.
132       BuildRemapTable<SymType>(elf_memory);
133       symbols_.clear();  // Remove cached symbols since the access pattern will be different.
134       info = BinarySearch<SymType, true>(addr, elf_memory);
135     }
136   } else {
137     // Fast search using the previously created remap table.
138     info = BinarySearch<SymType, true>(addr, elf_memory);
139   }
140   if (info == nullptr) {
141     return false;
142   }
143   // Read the function name from the string table.
144   *func_offset = addr - info->addr;
145   uint64_t str = str_offset_ + info->name;
146   return str < str_end_ && elf_memory->ReadString(str, name, str_end_ - str);
147 }
148 
149 template <typename SymType>
GetGlobal(Memory * elf_memory,const std::string & name,uint64_t * memory_address)150 bool Symbols::GetGlobal(Memory* elf_memory, const std::string& name, uint64_t* memory_address) {
151   for (uint32_t i = 0; i < count_; i++) {
152     SymType entry;
153     if (!elf_memory->ReadFully(offset_ + i * entry_size_, &entry, sizeof(entry))) {
154       return false;
155     }
156 
157     if (entry.st_shndx != SHN_UNDEF && ELF32_ST_TYPE(entry.st_info) == STT_OBJECT &&
158         ELF32_ST_BIND(entry.st_info) == STB_GLOBAL) {
159       uint64_t str_offset = str_offset_ + entry.st_name;
160       if (str_offset < str_end_) {
161         std::string symbol;
162         if (elf_memory->ReadString(str_offset, &symbol, str_end_ - str_offset) && symbol == name) {
163           *memory_address = entry.st_value;
164           return true;
165         }
166       }
167     }
168   }
169   return false;
170 }
171 
172 // Instantiate all of the needed template functions.
173 template bool Symbols::GetName<Elf32_Sym>(uint64_t, Memory*, std::string*, uint64_t*);
174 template bool Symbols::GetName<Elf64_Sym>(uint64_t, Memory*, std::string*, uint64_t*);
175 
176 template bool Symbols::GetGlobal<Elf32_Sym>(Memory*, const std::string&, uint64_t*);
177 template bool Symbols::GetGlobal<Elf64_Sym>(Memory*, const std::string&, uint64_t*);
178 }  // namespace unwindstack
179