libunwindstack/Symbols.cpp - platform/system/unwinding - Git at Google

 /*
  * Copyright (C) 2017 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include <elf.h>
 #include <stdint.h>
 #include <string.h>

 #include <algorithm>
 #include <string>
 #include <vector>

 #include <unwindstack/Memory.h>

 #include "Check.h"
 #include "Symbols.h"

 namespace unwindstack {

 Symbols::Symbols(uint64_t offset, uint64_t size, uint64_t entry_size, uint64_t str_offset,
                  uint64_t str_size)
     : offset_(offset),
       count_(entry_size != 0 ? size / entry_size : 0),
       entry_size_(entry_size),
       str_offset_(str_offset),
       str_end_(str_offset_ + str_size) {}

 template <typename SymType>
 static bool IsFunc(const SymType* entry) {
   return entry->st_shndx != SHN_UNDEF && ELF32_ST_TYPE(entry->st_info) == STT_FUNC;
 }

 // 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>
 Symbols::Info* Symbols::BinarySearch(uint64_t addr, Memory* elf_memory, uint64_t* func_offset) {
   // 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()) {
     uint64_t sym_value = (it->first - it->second.size);  // Function address.
     if (sym_value <= addr) {
       *func_offset = addr - sym_value;
       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) {
     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;
     }
     // There shouldn't be multiple symbols with same end address, but in case there are,
     // overwrite the cache with the last entry, so that 'sym' and 'info' are consistent.
     Info& info = symbols_[sym.st_value + sym.st_size];
     info = {.size = static_cast<uint32_t>(sym.st_size), .index = current};
     if (addr < sym.st_value) {
       last = current;
     } else if (addr < sym.st_value + sym.st_size) {
       *func_offset = addr - sym.st_value;
       return &info;
     } else {
       first = current + 1;
     }
   }
   return nullptr;
 }

 // Create remapping table which allows us to access symbols as if they were sorted by address.
 template <typename SymType>
 void Symbols::BuildRemapTable(Memory* elf_memory) {
   std::vector<uint64_t> addrs;  // Addresses of all symbols (addrs[i] == symbols[i].st_value).
   addrs.reserve(count_);
   remap_.emplace();  // Construct the optional remap table.
   remap_->reserve(count_);
   for (size_t symbol_idx = 0; symbol_idx < count_;) {
     // Read symbols from memory.  We intentionally bypass the cache to save memory.
     // Do the reads in batches so that we minimize the number of memory read calls.
     uint8_t buffer[1024];
     size_t read = std::min<size_t>(sizeof(buffer), (count_ - symbol_idx) * entry_size_);
     size_t size = elf_memory->Read(offset_ + symbol_idx * entry_size_, buffer, read);
     if (size < sizeof(SymType)) {
       break;  // Stop processing, something looks like it is corrupted.
     }
     for (size_t offset = 0; offset + sizeof(SymType) <= size; offset += entry_size_, symbol_idx++) {
       SymType sym;
       memcpy(&sym, &buffer[offset], sizeof(SymType));  // Copy to ensure alignment.
       addrs.push_back(sym.st_value);  // Always insert so it is indexable by symbol index.
       // NB: It is important to filter our zero-sized symbols since otherwise we can get
       // duplicate end addresses in the table (e.g. if there is custom "end" symbol marker).
       if (IsFunc(&sym) && sym.st_size != 0) {
         remap_->push_back(symbol_idx);  // Indices of function symbols only.
       }
     }
   }
   // Sort by address to make the remap list binary searchable (stable due to the a<b tie break).
   auto comp = [&addrs](auto a, auto b) { return std::tie(addrs[a], a) < std::tie(addrs[b], b); };
   std::sort(remap_->begin(), remap_->end(), comp);
   // Remove duplicate entries (methods de-duplicated by the linker).
   auto pred = [&addrs](auto a, auto b) { return addrs[a] == addrs[b]; };
   remap_->erase(std::unique(remap_->begin(), remap_->end(), pred), remap_->end());
   remap_->shrink_to_fit();
 }

 template <typename SymType>
 bool Symbols::GetName(uint64_t addr, Memory* elf_memory, SharedString* name,
                       uint64_t* func_offset) {
   Info* info;
   if (!remap_.has_value()) {
     // Assume the symbol table is sorted. If it is not, this will gracefully fail.
     info = BinarySearch<SymType, false>(addr, elf_memory, func_offset);
     if (info == nullptr) {
       // Create the remapping table and retry the search.
       BuildRemapTable<SymType>(elf_memory);
       symbols_.clear();  // Remove cached symbols since the access pattern will be different.
       info = BinarySearch<SymType, true>(addr, elf_memory, func_offset);
     }
   } else {
     // Fast search using the previously created remap table.
     info = BinarySearch<SymType, true>(addr, elf_memory, func_offset);
   }
   if (info == nullptr) {
     return false;
   }
   // Read and cache the symbol name.
   if (info->name.is_null()) {
     SymType sym;
     uint32_t symbol_index = remap_.has_value() ? remap_.value()[info->index] : info->index;
     if (!elf_memory->ReadFully(offset_ + symbol_index * entry_size_, &sym, sizeof(sym))) {
       return false;
     }
     std::string symbol_name;
     uint64_t str;
     if (__builtin_add_overflow(str_offset_, sym.st_name, &str) || str >= str_end_) {
       return false;
     }
     if (!IsFunc(&sym) || !elf_memory->ReadString(str, &symbol_name, str_end_ - str)) {
       return false;
     }
     info->name = SharedString(std::move(symbol_name));
   }
   *name = info->name;
   return true;
 }

 template <typename SymType>
 bool Symbols::GetGlobal(Memory* elf_memory, const std::string& name, uint64_t* memory_address) {
   // Lookup from cache.
   auto it = global_variables_.find(name);
   if (it != global_variables_.end()) {
     if (it->second.has_value()) {
       *memory_address = it->second.value();
       return true;
     }
     return false;
   }

   // Linear scan of all symbols.
   for (uint32_t i = 0; i < count_; i++) {
     SymType entry;
     if (!elf_memory->ReadFully(offset_ + i * entry_size_, &entry, sizeof(entry))) {
       return false;
     }

     if (entry.st_shndx != SHN_UNDEF && ELF32_ST_TYPE(entry.st_info) == STT_OBJECT &&
         ELF32_ST_BIND(entry.st_info) == STB_GLOBAL) {
       uint64_t str_offset = str_offset_ + entry.st_name;
       if (str_offset < str_end_) {
         std::string symbol;
         if (elf_memory->ReadString(str_offset, &symbol, str_end_ - str_offset) && symbol == name) {
           global_variables_.emplace(name, entry.st_value);
           *memory_address = entry.st_value;
           return true;
         }
       }
     }
   }
   global_variables_.emplace(name, std::optional<uint64_t>());  // Remember "not found" outcome.
   return false;
 }

 // Instantiate all of the needed template functions.
 template bool Symbols::GetName<Elf32_Sym>(uint64_t, Memory*, SharedString*, uint64_t*);
 template bool Symbols::GetName<Elf64_Sym>(uint64_t, Memory*, SharedString*, uint64_t*);

 template bool Symbols::GetGlobal<Elf32_Sym>(Memory*, const std::string&, uint64_t*);
 template bool Symbols::GetGlobal<Elf64_Sym>(Memory*, const std::string&, uint64_t*);
 }  // namespace unwindstack
	/*
	* Copyright (C) 2017 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include <elf.h>
	#include <stdint.h>
	#include <string.h>

	#include <algorithm>
	#include <string>
	#include <vector>

	#include <unwindstack/Memory.h>

	#include "Check.h"
	#include "Symbols.h"

	namespace unwindstack {

	Symbols::Symbols(uint64_t offset, uint64_t size, uint64_t entry_size, uint64_t str_offset,
	uint64_t str_size)
	: offset_(offset),
	count_(entry_size != 0 ? size / entry_size : 0),
	entry_size_(entry_size),
	str_offset_(str_offset),
	str_end_(str_offset_ + str_size) {}

	template <typename SymType>
	static bool IsFunc(const SymType* entry) {
	return entry->st_shndx != SHN_UNDEF && ELF32_ST_TYPE(entry->st_info) == STT_FUNC;
	}

	// 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>
	Symbols::Info* Symbols::BinarySearch(uint64_t addr, Memory* elf_memory, uint64_t* func_offset) {
	// 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()) {
	uint64_t sym_value = (it->first - it->second.size); // Function address.
	if (sym_value <= addr) {
	*func_offset = addr - sym_value;
	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) {
	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;
	}
	// There shouldn't be multiple symbols with same end address, but in case there are,
	// overwrite the cache with the last entry, so that 'sym' and 'info' are consistent.
	Info& info = symbols_[sym.st_value + sym.st_size];
	info = {.size = static_cast<uint32_t>(sym.st_size), .index = current};
	if (addr < sym.st_value) {
	last = current;
	} else if (addr < sym.st_value + sym.st_size) {
	*func_offset = addr - sym.st_value;
	return &info;
	} else {
	first = current + 1;
	}
	}
	return nullptr;
	}

	// Create remapping table which allows us to access symbols as if they were sorted by address.
	template <typename SymType>
	void Symbols::BuildRemapTable(Memory* elf_memory) {
	std::vector<uint64_t> addrs; // Addresses of all symbols (addrs[i] == symbols[i].st_value).
	addrs.reserve(count_);
	remap_.emplace(); // Construct the optional remap table.
	remap_->reserve(count_);
	for (size_t symbol_idx = 0; symbol_idx < count_;) {
	// Read symbols from memory. We intentionally bypass the cache to save memory.
	// Do the reads in batches so that we minimize the number of memory read calls.
	uint8_t buffer[1024];
	size_t read = std::min<size_t>(sizeof(buffer), (count_ - symbol_idx) * entry_size_);
	size_t size = elf_memory->Read(offset_ + symbol_idx * entry_size_, buffer, read);
	if (size < sizeof(SymType)) {
	break; // Stop processing, something looks like it is corrupted.
	}
	for (size_t offset = 0; offset + sizeof(SymType) <= size; offset += entry_size_, symbol_idx++) {
	SymType sym;
	memcpy(&sym, &buffer[offset], sizeof(SymType)); // Copy to ensure alignment.
	addrs.push_back(sym.st_value); // Always insert so it is indexable by symbol index.
	// NB: It is important to filter our zero-sized symbols since otherwise we can get
	// duplicate end addresses in the table (e.g. if there is custom "end" symbol marker).
	if (IsFunc(&sym) && sym.st_size != 0) {
	remap_->push_back(symbol_idx); // Indices of function symbols only.
	}
	}
	}
	// Sort by address to make the remap list binary searchable (stable due to the a<b tie break).
	auto comp = [&addrs](auto a, auto b) { return std::tie(addrs[a], a) < std::tie(addrs[b], b); };
	std::sort(remap_->begin(), remap_->end(), comp);
	// Remove duplicate entries (methods de-duplicated by the linker).
	auto pred = [&addrs](auto a, auto b) { return addrs[a] == addrs[b]; };
	remap_->erase(std::unique(remap_->begin(), remap_->end(), pred), remap_->end());
	remap_->shrink_to_fit();
	}

	template <typename SymType>
	bool Symbols::GetName(uint64_t addr, Memory* elf_memory, SharedString* name,
	uint64_t* func_offset) {
	Info* info;
	if (!remap_.has_value()) {
	// Assume the symbol table is sorted. If it is not, this will gracefully fail.
	info = BinarySearch<SymType, false>(addr, elf_memory, func_offset);
	if (info == nullptr) {
	// Create the remapping table and retry the search.
	BuildRemapTable<SymType>(elf_memory);
	symbols_.clear(); // Remove cached symbols since the access pattern will be different.
	info = BinarySearch<SymType, true>(addr, elf_memory, func_offset);
	}
	} else {
	// Fast search using the previously created remap table.
	info = BinarySearch<SymType, true>(addr, elf_memory, func_offset);
	}
	if (info == nullptr) {
	return false;
	}
	// Read and cache the symbol name.
	if (info->name.is_null()) {
	SymType sym;
	uint32_t symbol_index = remap_.has_value() ? remap_.value()[info->index] : info->index;
	if (!elf_memory->ReadFully(offset_ + symbol_index * entry_size_, &sym, sizeof(sym))) {
	return false;
	}
	std::string symbol_name;
	uint64_t str;
	if (__builtin_add_overflow(str_offset_, sym.st_name, &str) \|\| str >= str_end_) {
	return false;
	}
	if (!IsFunc(&sym) \|\| !elf_memory->ReadString(str, &symbol_name, str_end_ - str)) {
	return false;
	}
	info->name = SharedString(std::move(symbol_name));
	}
	*name = info->name;
	return true;
	}

	template <typename SymType>
	bool Symbols::GetGlobal(Memory* elf_memory, const std::string& name, uint64_t* memory_address) {
	// Lookup from cache.
	auto it = global_variables_.find(name);
	if (it != global_variables_.end()) {
	if (it->second.has_value()) {
	*memory_address = it->second.value();
	return true;
	}
	return false;
	}

	// Linear scan of all symbols.
	for (uint32_t i = 0; i < count_; i++) {
	SymType entry;
	if (!elf_memory->ReadFully(offset_ + i * entry_size_, &entry, sizeof(entry))) {
	return false;
	}

	if (entry.st_shndx != SHN_UNDEF && ELF32_ST_TYPE(entry.st_info) == STT_OBJECT &&
	ELF32_ST_BIND(entry.st_info) == STB_GLOBAL) {
	uint64_t str_offset = str_offset_ + entry.st_name;
	if (str_offset < str_end_) {
	std::string symbol;
	if (elf_memory->ReadString(str_offset, &symbol, str_end_ - str_offset) && symbol == name) {
	global_variables_.emplace(name, entry.st_value);
	*memory_address = entry.st_value;
	return true;
	}
	}
	}
	}
	global_variables_.emplace(name, std::optional<uint64_t>()); // Remember "not found" outcome.
	return false;
	}

	// Instantiate all of the needed template functions.
	template bool Symbols::GetName<Elf32_Sym>(uint64_t, Memory, SharedString, uint64_t*);
	template bool Symbols::GetName<Elf64_Sym>(uint64_t, Memory, SharedString, uint64_t*);

	template bool Symbols::GetGlobal<Elf32_Sym>(Memory, const std::string&, uint64_t);
	template bool Symbols::GetGlobal<Elf64_Sym>(Memory, const std::string&, uint64_t);
	} // namespace unwindstack