15ffd83dbSDimitry Andric //===-- Symtab.cpp --------------------------------------------------------===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric 90b57cec5SDimitry Andric #include <map> 100b57cec5SDimitry Andric #include <set> 110b57cec5SDimitry Andric 120eae32dcSDimitry Andric #include "lldb/Core/DataFileCache.h" 130b57cec5SDimitry Andric #include "lldb/Core/Module.h" 140b57cec5SDimitry Andric #include "lldb/Core/RichManglingContext.h" 150b57cec5SDimitry Andric #include "lldb/Core/Section.h" 160b57cec5SDimitry Andric #include "lldb/Symbol/ObjectFile.h" 170b57cec5SDimitry Andric #include "lldb/Symbol/Symbol.h" 180b57cec5SDimitry Andric #include "lldb/Symbol/SymbolContext.h" 190b57cec5SDimitry Andric #include "lldb/Symbol/Symtab.h" 20fe6060f1SDimitry Andric #include "lldb/Target/Language.h" 210eae32dcSDimitry Andric #include "lldb/Utility/DataEncoder.h" 220eae32dcSDimitry Andric #include "lldb/Utility/Endian.h" 230b57cec5SDimitry Andric #include "lldb/Utility/RegularExpression.h" 240b57cec5SDimitry Andric #include "lldb/Utility/Stream.h" 250b57cec5SDimitry Andric #include "lldb/Utility/Timer.h" 260b57cec5SDimitry Andric 270eae32dcSDimitry Andric #include "llvm/ADT/ArrayRef.h" 280b57cec5SDimitry Andric #include "llvm/ADT/StringRef.h" 290eae32dcSDimitry Andric #include "llvm/Support/DJB.h" 300b57cec5SDimitry Andric 310b57cec5SDimitry Andric using namespace lldb; 320b57cec5SDimitry Andric using namespace lldb_private; 330b57cec5SDimitry Andric 340b57cec5SDimitry Andric Symtab::Symtab(ObjectFile *objfile) 35480093f4SDimitry Andric : m_objfile(objfile), m_symbols(), m_file_addr_to_index(*this), 36fe6060f1SDimitry Andric m_name_to_symbol_indices(), m_mutex(), 3704eeddc0SDimitry Andric m_file_addr_to_index_computed(false), m_name_indexes_computed(false), 3804eeddc0SDimitry Andric m_loaded_from_cache(false), m_saved_to_cache(false) { 39fe6060f1SDimitry Andric m_name_to_symbol_indices.emplace(std::make_pair( 40fe6060f1SDimitry Andric lldb::eFunctionNameTypeNone, UniqueCStringMap<uint32_t>())); 41fe6060f1SDimitry Andric m_name_to_symbol_indices.emplace(std::make_pair( 42fe6060f1SDimitry Andric lldb::eFunctionNameTypeBase, UniqueCStringMap<uint32_t>())); 43fe6060f1SDimitry Andric m_name_to_symbol_indices.emplace(std::make_pair( 44fe6060f1SDimitry Andric lldb::eFunctionNameTypeMethod, UniqueCStringMap<uint32_t>())); 45fe6060f1SDimitry Andric m_name_to_symbol_indices.emplace(std::make_pair( 46fe6060f1SDimitry Andric lldb::eFunctionNameTypeSelector, UniqueCStringMap<uint32_t>())); 47fe6060f1SDimitry Andric } 480b57cec5SDimitry Andric 49fe6060f1SDimitry Andric Symtab::~Symtab() = default; 500b57cec5SDimitry Andric 510b57cec5SDimitry Andric void Symtab::Reserve(size_t count) { 520b57cec5SDimitry Andric // Clients should grab the mutex from this symbol table and lock it manually 530b57cec5SDimitry Andric // when calling this function to avoid performance issues. 540b57cec5SDimitry Andric m_symbols.reserve(count); 550b57cec5SDimitry Andric } 560b57cec5SDimitry Andric 570b57cec5SDimitry Andric Symbol *Symtab::Resize(size_t count) { 580b57cec5SDimitry Andric // Clients should grab the mutex from this symbol table and lock it manually 590b57cec5SDimitry Andric // when calling this function to avoid performance issues. 600b57cec5SDimitry Andric m_symbols.resize(count); 610b57cec5SDimitry Andric return m_symbols.empty() ? nullptr : &m_symbols[0]; 620b57cec5SDimitry Andric } 630b57cec5SDimitry Andric 640b57cec5SDimitry Andric uint32_t Symtab::AddSymbol(const Symbol &symbol) { 650b57cec5SDimitry Andric // Clients should grab the mutex from this symbol table and lock it manually 660b57cec5SDimitry Andric // when calling this function to avoid performance issues. 670b57cec5SDimitry Andric uint32_t symbol_idx = m_symbols.size(); 68fe6060f1SDimitry Andric auto &name_to_index = GetNameToSymbolIndexMap(lldb::eFunctionNameTypeNone); 69fe6060f1SDimitry Andric name_to_index.Clear(); 700b57cec5SDimitry Andric m_file_addr_to_index.Clear(); 710b57cec5SDimitry Andric m_symbols.push_back(symbol); 720b57cec5SDimitry Andric m_file_addr_to_index_computed = false; 730b57cec5SDimitry Andric m_name_indexes_computed = false; 740b57cec5SDimitry Andric return symbol_idx; 750b57cec5SDimitry Andric } 760b57cec5SDimitry Andric 770b57cec5SDimitry Andric size_t Symtab::GetNumSymbols() const { 780b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 790b57cec5SDimitry Andric return m_symbols.size(); 800b57cec5SDimitry Andric } 810b57cec5SDimitry Andric 820b57cec5SDimitry Andric void Symtab::SectionFileAddressesChanged() { 8306c3fb27SDimitry Andric m_file_addr_to_index.Clear(); 840b57cec5SDimitry Andric m_file_addr_to_index_computed = false; 850b57cec5SDimitry Andric } 860b57cec5SDimitry Andric 87480093f4SDimitry Andric void Symtab::Dump(Stream *s, Target *target, SortOrder sort_order, 88480093f4SDimitry Andric Mangled::NamePreference name_preference) { 890b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 900b57cec5SDimitry Andric 910b57cec5SDimitry Andric // s->Printf("%.*p: ", (int)sizeof(void*) * 2, this); 920b57cec5SDimitry Andric s->Indent(); 930b57cec5SDimitry Andric const FileSpec &file_spec = m_objfile->GetFileSpec(); 940b57cec5SDimitry Andric const char *object_name = nullptr; 950b57cec5SDimitry Andric if (m_objfile->GetModule()) 960b57cec5SDimitry Andric object_name = m_objfile->GetModule()->GetObjectName().GetCString(); 970b57cec5SDimitry Andric 980b57cec5SDimitry Andric if (file_spec) 990b57cec5SDimitry Andric s->Printf("Symtab, file = %s%s%s%s, num_symbols = %" PRIu64, 1000b57cec5SDimitry Andric file_spec.GetPath().c_str(), object_name ? "(" : "", 1010b57cec5SDimitry Andric object_name ? object_name : "", object_name ? ")" : "", 1020b57cec5SDimitry Andric (uint64_t)m_symbols.size()); 1030b57cec5SDimitry Andric else 1040b57cec5SDimitry Andric s->Printf("Symtab, num_symbols = %" PRIu64 "", (uint64_t)m_symbols.size()); 1050b57cec5SDimitry Andric 1060b57cec5SDimitry Andric if (!m_symbols.empty()) { 1070b57cec5SDimitry Andric switch (sort_order) { 1080b57cec5SDimitry Andric case eSortOrderNone: { 1090b57cec5SDimitry Andric s->PutCString(":\n"); 1100b57cec5SDimitry Andric DumpSymbolHeader(s); 1110b57cec5SDimitry Andric const_iterator begin = m_symbols.begin(); 1120b57cec5SDimitry Andric const_iterator end = m_symbols.end(); 1130b57cec5SDimitry Andric for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) { 1140b57cec5SDimitry Andric s->Indent(); 115480093f4SDimitry Andric pos->Dump(s, target, std::distance(begin, pos), name_preference); 1160b57cec5SDimitry Andric } 1170eae32dcSDimitry Andric } 1180eae32dcSDimitry Andric break; 1190b57cec5SDimitry Andric 1200b57cec5SDimitry Andric case eSortOrderByName: { 1210b57cec5SDimitry Andric // Although we maintain a lookup by exact name map, the table isn't 1220b57cec5SDimitry Andric // sorted by name. So we must make the ordered symbol list up ourselves. 1230b57cec5SDimitry Andric s->PutCString(" (sorted by name):\n"); 1240b57cec5SDimitry Andric DumpSymbolHeader(s); 125480093f4SDimitry Andric 126480093f4SDimitry Andric std::multimap<llvm::StringRef, const Symbol *> name_map; 1270b57cec5SDimitry Andric for (const_iterator pos = m_symbols.begin(), end = m_symbols.end(); 1280b57cec5SDimitry Andric pos != end; ++pos) { 1290b57cec5SDimitry Andric const char *name = pos->GetName().AsCString(); 1300b57cec5SDimitry Andric if (name && name[0]) 1310b57cec5SDimitry Andric name_map.insert(std::make_pair(name, &(*pos))); 1320b57cec5SDimitry Andric } 1330b57cec5SDimitry Andric 134480093f4SDimitry Andric for (const auto &name_to_symbol : name_map) { 135480093f4SDimitry Andric const Symbol *symbol = name_to_symbol.second; 1360b57cec5SDimitry Andric s->Indent(); 137480093f4SDimitry Andric symbol->Dump(s, target, symbol - &m_symbols[0], name_preference); 1380b57cec5SDimitry Andric } 1390b57cec5SDimitry Andric } break; 1400b57cec5SDimitry Andric 1410b57cec5SDimitry Andric case eSortOrderByAddress: 1420b57cec5SDimitry Andric s->PutCString(" (sorted by address):\n"); 1430b57cec5SDimitry Andric DumpSymbolHeader(s); 1440b57cec5SDimitry Andric if (!m_file_addr_to_index_computed) 1450b57cec5SDimitry Andric InitAddressIndexes(); 1460b57cec5SDimitry Andric const size_t num_entries = m_file_addr_to_index.GetSize(); 1470b57cec5SDimitry Andric for (size_t i = 0; i < num_entries; ++i) { 1480b57cec5SDimitry Andric s->Indent(); 1490b57cec5SDimitry Andric const uint32_t symbol_idx = m_file_addr_to_index.GetEntryRef(i).data; 150480093f4SDimitry Andric m_symbols[symbol_idx].Dump(s, target, symbol_idx, name_preference); 1510b57cec5SDimitry Andric } 1520b57cec5SDimitry Andric break; 1530b57cec5SDimitry Andric } 1540b57cec5SDimitry Andric } else { 1550b57cec5SDimitry Andric s->PutCString("\n"); 1560b57cec5SDimitry Andric } 1570b57cec5SDimitry Andric } 1580b57cec5SDimitry Andric 159480093f4SDimitry Andric void Symtab::Dump(Stream *s, Target *target, std::vector<uint32_t> &indexes, 160480093f4SDimitry Andric Mangled::NamePreference name_preference) const { 1610b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 1620b57cec5SDimitry Andric 1630b57cec5SDimitry Andric const size_t num_symbols = GetNumSymbols(); 1640b57cec5SDimitry Andric // s->Printf("%.*p: ", (int)sizeof(void*) * 2, this); 1650b57cec5SDimitry Andric s->Indent(); 1660b57cec5SDimitry Andric s->Printf("Symtab %" PRIu64 " symbol indexes (%" PRIu64 " symbols total):\n", 1670b57cec5SDimitry Andric (uint64_t)indexes.size(), (uint64_t)m_symbols.size()); 1680b57cec5SDimitry Andric s->IndentMore(); 1690b57cec5SDimitry Andric 1700b57cec5SDimitry Andric if (!indexes.empty()) { 1710b57cec5SDimitry Andric std::vector<uint32_t>::const_iterator pos; 1720b57cec5SDimitry Andric std::vector<uint32_t>::const_iterator end = indexes.end(); 1730b57cec5SDimitry Andric DumpSymbolHeader(s); 1740b57cec5SDimitry Andric for (pos = indexes.begin(); pos != end; ++pos) { 1750b57cec5SDimitry Andric size_t idx = *pos; 1760b57cec5SDimitry Andric if (idx < num_symbols) { 1770b57cec5SDimitry Andric s->Indent(); 178480093f4SDimitry Andric m_symbols[idx].Dump(s, target, idx, name_preference); 1790b57cec5SDimitry Andric } 1800b57cec5SDimitry Andric } 1810b57cec5SDimitry Andric } 1820b57cec5SDimitry Andric s->IndentLess(); 1830b57cec5SDimitry Andric } 1840b57cec5SDimitry Andric 1850b57cec5SDimitry Andric void Symtab::DumpSymbolHeader(Stream *s) { 1860b57cec5SDimitry Andric s->Indent(" Debug symbol\n"); 1870b57cec5SDimitry Andric s->Indent(" |Synthetic symbol\n"); 1880b57cec5SDimitry Andric s->Indent(" ||Externally Visible\n"); 1890b57cec5SDimitry Andric s->Indent(" |||\n"); 1900b57cec5SDimitry Andric s->Indent("Index UserID DSX Type File Address/Value Load " 1910b57cec5SDimitry Andric "Address Size Flags Name\n"); 1920b57cec5SDimitry Andric s->Indent("------- ------ --- --------------- ------------------ " 1930b57cec5SDimitry Andric "------------------ ------------------ ---------- " 1940b57cec5SDimitry Andric "----------------------------------\n"); 1950b57cec5SDimitry Andric } 1960b57cec5SDimitry Andric 1970b57cec5SDimitry Andric static int CompareSymbolID(const void *key, const void *p) { 1980b57cec5SDimitry Andric const user_id_t match_uid = *(const user_id_t *)key; 1990b57cec5SDimitry Andric const user_id_t symbol_uid = ((const Symbol *)p)->GetID(); 2000b57cec5SDimitry Andric if (match_uid < symbol_uid) 2010b57cec5SDimitry Andric return -1; 2020b57cec5SDimitry Andric if (match_uid > symbol_uid) 2030b57cec5SDimitry Andric return 1; 2040b57cec5SDimitry Andric return 0; 2050b57cec5SDimitry Andric } 2060b57cec5SDimitry Andric 2070b57cec5SDimitry Andric Symbol *Symtab::FindSymbolByID(lldb::user_id_t symbol_uid) const { 2080b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 2090b57cec5SDimitry Andric 2100b57cec5SDimitry Andric Symbol *symbol = 2110b57cec5SDimitry Andric (Symbol *)::bsearch(&symbol_uid, &m_symbols[0], m_symbols.size(), 2120b57cec5SDimitry Andric sizeof(m_symbols[0]), CompareSymbolID); 2130b57cec5SDimitry Andric return symbol; 2140b57cec5SDimitry Andric } 2150b57cec5SDimitry Andric 2160b57cec5SDimitry Andric Symbol *Symtab::SymbolAtIndex(size_t idx) { 2170b57cec5SDimitry Andric // Clients should grab the mutex from this symbol table and lock it manually 2180b57cec5SDimitry Andric // when calling this function to avoid performance issues. 2190b57cec5SDimitry Andric if (idx < m_symbols.size()) 2200b57cec5SDimitry Andric return &m_symbols[idx]; 2210b57cec5SDimitry Andric return nullptr; 2220b57cec5SDimitry Andric } 2230b57cec5SDimitry Andric 2240b57cec5SDimitry Andric const Symbol *Symtab::SymbolAtIndex(size_t idx) const { 2250b57cec5SDimitry Andric // Clients should grab the mutex from this symbol table and lock it manually 2260b57cec5SDimitry Andric // when calling this function to avoid performance issues. 2270b57cec5SDimitry Andric if (idx < m_symbols.size()) 2280b57cec5SDimitry Andric return &m_symbols[idx]; 2290b57cec5SDimitry Andric return nullptr; 2300b57cec5SDimitry Andric } 2310b57cec5SDimitry Andric 2320b57cec5SDimitry Andric static bool lldb_skip_name(llvm::StringRef mangled, 2330b57cec5SDimitry Andric Mangled::ManglingScheme scheme) { 2340b57cec5SDimitry Andric switch (scheme) { 2350b57cec5SDimitry Andric case Mangled::eManglingSchemeItanium: { 2360b57cec5SDimitry Andric if (mangled.size() < 3 || !mangled.startswith("_Z")) 2370b57cec5SDimitry Andric return true; 2380b57cec5SDimitry Andric 2390b57cec5SDimitry Andric // Avoid the following types of symbols in the index. 2400b57cec5SDimitry Andric switch (mangled[2]) { 2410b57cec5SDimitry Andric case 'G': // guard variables 2420b57cec5SDimitry Andric case 'T': // virtual tables, VTT structures, typeinfo structures + names 2430b57cec5SDimitry Andric case 'Z': // named local entities (if we eventually handle 2440b57cec5SDimitry Andric // eSymbolTypeData, we will want this back) 2450b57cec5SDimitry Andric return true; 2460b57cec5SDimitry Andric 2470b57cec5SDimitry Andric default: 2480b57cec5SDimitry Andric break; 2490b57cec5SDimitry Andric } 2500b57cec5SDimitry Andric 2510b57cec5SDimitry Andric // Include this name in the index. 2520b57cec5SDimitry Andric return false; 2530b57cec5SDimitry Andric } 2540b57cec5SDimitry Andric 2550b57cec5SDimitry Andric // No filters for this scheme yet. Include all names in indexing. 2560b57cec5SDimitry Andric case Mangled::eManglingSchemeMSVC: 257fe6060f1SDimitry Andric case Mangled::eManglingSchemeRustV0: 258349cc55cSDimitry Andric case Mangled::eManglingSchemeD: 259fe6060f1SDimitry Andric return false; 260fe6060f1SDimitry Andric 2610b57cec5SDimitry Andric // Don't try and demangle things we can't categorize. 2620b57cec5SDimitry Andric case Mangled::eManglingSchemeNone: 2630b57cec5SDimitry Andric return true; 2640b57cec5SDimitry Andric } 2650b57cec5SDimitry Andric llvm_unreachable("unknown scheme!"); 2660b57cec5SDimitry Andric } 2670b57cec5SDimitry Andric 2680b57cec5SDimitry Andric void Symtab::InitNameIndexes() { 2690b57cec5SDimitry Andric // Protected function, no need to lock mutex... 2700b57cec5SDimitry Andric if (!m_name_indexes_computed) { 2710b57cec5SDimitry Andric m_name_indexes_computed = true; 272349cc55cSDimitry Andric ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabIndexTime()); 273e8d8bef9SDimitry Andric LLDB_SCOPED_TIMER(); 274fe6060f1SDimitry Andric 275fe6060f1SDimitry Andric // Collect all loaded language plugins. 276fe6060f1SDimitry Andric std::vector<Language *> languages; 277fe6060f1SDimitry Andric Language::ForEach([&languages](Language *l) { 278fe6060f1SDimitry Andric languages.push_back(l); 279fe6060f1SDimitry Andric return true; 280fe6060f1SDimitry Andric }); 281fe6060f1SDimitry Andric 282fe6060f1SDimitry Andric auto &name_to_index = GetNameToSymbolIndexMap(lldb::eFunctionNameTypeNone); 283fe6060f1SDimitry Andric auto &basename_to_index = 284fe6060f1SDimitry Andric GetNameToSymbolIndexMap(lldb::eFunctionNameTypeBase); 285fe6060f1SDimitry Andric auto &method_to_index = 286fe6060f1SDimitry Andric GetNameToSymbolIndexMap(lldb::eFunctionNameTypeMethod); 287fe6060f1SDimitry Andric auto &selector_to_index = 288fe6060f1SDimitry Andric GetNameToSymbolIndexMap(lldb::eFunctionNameTypeSelector); 2890b57cec5SDimitry Andric // Create the name index vector to be able to quickly search by name 2900b57cec5SDimitry Andric const size_t num_symbols = m_symbols.size(); 291fe6060f1SDimitry Andric name_to_index.Reserve(num_symbols); 2920b57cec5SDimitry Andric 2930b57cec5SDimitry Andric // The "const char *" in "class_contexts" and backlog::value_type::second 2940b57cec5SDimitry Andric // must come from a ConstString::GetCString() 2950b57cec5SDimitry Andric std::set<const char *> class_contexts; 2960b57cec5SDimitry Andric std::vector<std::pair<NameToIndexMap::Entry, const char *>> backlog; 2970b57cec5SDimitry Andric backlog.reserve(num_symbols / 2); 2980b57cec5SDimitry Andric 2990b57cec5SDimitry Andric // Instantiation of the demangler is expensive, so better use a single one 3000b57cec5SDimitry Andric // for all entries during batch processing. 3010b57cec5SDimitry Andric RichManglingContext rmc; 3020b57cec5SDimitry Andric for (uint32_t value = 0; value < num_symbols; ++value) { 3030b57cec5SDimitry Andric Symbol *symbol = &m_symbols[value]; 3040b57cec5SDimitry Andric 3050b57cec5SDimitry Andric // Don't let trampolines get into the lookup by name map If we ever need 3060b57cec5SDimitry Andric // the trampoline symbols to be searchable by name we can remove this and 3070b57cec5SDimitry Andric // then possibly add a new bool to any of the Symtab functions that 308fe6060f1SDimitry Andric // lookup symbols by name to indicate if they want trampolines. We also 309fe6060f1SDimitry Andric // don't want any synthetic symbols with auto generated names in the 310fe6060f1SDimitry Andric // name lookups. 311fe6060f1SDimitry Andric if (symbol->IsTrampoline() || symbol->IsSyntheticWithAutoGeneratedName()) 3120b57cec5SDimitry Andric continue; 3130b57cec5SDimitry Andric 3140b57cec5SDimitry Andric // If the symbol's name string matched a Mangled::ManglingScheme, it is 3150b57cec5SDimitry Andric // stored in the mangled field. 3160b57cec5SDimitry Andric Mangled &mangled = symbol->GetMangled(); 3170b57cec5SDimitry Andric if (ConstString name = mangled.GetMangledName()) { 318fe6060f1SDimitry Andric name_to_index.Append(name, value); 3190b57cec5SDimitry Andric 3200b57cec5SDimitry Andric if (symbol->ContainsLinkerAnnotations()) { 3210b57cec5SDimitry Andric // If the symbol has linker annotations, also add the version without 3220b57cec5SDimitry Andric // the annotations. 3230b57cec5SDimitry Andric ConstString stripped = ConstString( 3240b57cec5SDimitry Andric m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef())); 325fe6060f1SDimitry Andric name_to_index.Append(stripped, value); 3260b57cec5SDimitry Andric } 3270b57cec5SDimitry Andric 3280b57cec5SDimitry Andric const SymbolType type = symbol->GetType(); 3290b57cec5SDimitry Andric if (type == eSymbolTypeCode || type == eSymbolTypeResolver) { 330d56accc7SDimitry Andric if (mangled.GetRichManglingInfo(rmc, lldb_skip_name)) { 3310b57cec5SDimitry Andric RegisterMangledNameEntry(value, class_contexts, backlog, rmc); 332d56accc7SDimitry Andric continue; 333d56accc7SDimitry Andric } 3340b57cec5SDimitry Andric } 3350b57cec5SDimitry Andric } 3360b57cec5SDimitry Andric 3370b57cec5SDimitry Andric // Symbol name strings that didn't match a Mangled::ManglingScheme, are 3380b57cec5SDimitry Andric // stored in the demangled field. 3395ffd83dbSDimitry Andric if (ConstString name = mangled.GetDemangledName()) { 340fe6060f1SDimitry Andric name_to_index.Append(name, value); 3410b57cec5SDimitry Andric 3420b57cec5SDimitry Andric if (symbol->ContainsLinkerAnnotations()) { 3430b57cec5SDimitry Andric // If the symbol has linker annotations, also add the version without 3440b57cec5SDimitry Andric // the annotations. 3450b57cec5SDimitry Andric name = ConstString( 3460b57cec5SDimitry Andric m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef())); 347fe6060f1SDimitry Andric name_to_index.Append(name, value); 3480b57cec5SDimitry Andric } 3490b57cec5SDimitry Andric 3500b57cec5SDimitry Andric // If the demangled name turns out to be an ObjC name, and is a category 3510b57cec5SDimitry Andric // name, add the version without categories to the index too. 352fe6060f1SDimitry Andric for (Language *lang : languages) { 353fe6060f1SDimitry Andric for (auto variant : lang->GetMethodNameVariants(name)) { 354fe6060f1SDimitry Andric if (variant.GetType() & lldb::eFunctionNameTypeSelector) 355fe6060f1SDimitry Andric selector_to_index.Append(variant.GetName(), value); 356fe6060f1SDimitry Andric else if (variant.GetType() & lldb::eFunctionNameTypeFull) 357fe6060f1SDimitry Andric name_to_index.Append(variant.GetName(), value); 358fe6060f1SDimitry Andric else if (variant.GetType() & lldb::eFunctionNameTypeMethod) 359fe6060f1SDimitry Andric method_to_index.Append(variant.GetName(), value); 360fe6060f1SDimitry Andric else if (variant.GetType() & lldb::eFunctionNameTypeBase) 361fe6060f1SDimitry Andric basename_to_index.Append(variant.GetName(), value); 362fe6060f1SDimitry Andric } 3630b57cec5SDimitry Andric } 3640b57cec5SDimitry Andric } 3650b57cec5SDimitry Andric } 3660b57cec5SDimitry Andric 3670b57cec5SDimitry Andric for (const auto &record : backlog) { 3680b57cec5SDimitry Andric RegisterBacklogEntry(record.first, record.second, class_contexts); 3690b57cec5SDimitry Andric } 3700b57cec5SDimitry Andric 371fe6060f1SDimitry Andric name_to_index.Sort(); 372fe6060f1SDimitry Andric name_to_index.SizeToFit(); 373fe6060f1SDimitry Andric selector_to_index.Sort(); 374fe6060f1SDimitry Andric selector_to_index.SizeToFit(); 375fe6060f1SDimitry Andric basename_to_index.Sort(); 376fe6060f1SDimitry Andric basename_to_index.SizeToFit(); 377fe6060f1SDimitry Andric method_to_index.Sort(); 378fe6060f1SDimitry Andric method_to_index.SizeToFit(); 3790b57cec5SDimitry Andric } 3800b57cec5SDimitry Andric } 3810b57cec5SDimitry Andric 3820b57cec5SDimitry Andric void Symtab::RegisterMangledNameEntry( 3830b57cec5SDimitry Andric uint32_t value, std::set<const char *> &class_contexts, 3840b57cec5SDimitry Andric std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog, 3850b57cec5SDimitry Andric RichManglingContext &rmc) { 3860b57cec5SDimitry Andric // Only register functions that have a base name. 387d56accc7SDimitry Andric llvm::StringRef base_name = rmc.ParseFunctionBaseName(); 3880b57cec5SDimitry Andric if (base_name.empty()) 3890b57cec5SDimitry Andric return; 3900b57cec5SDimitry Andric 3910b57cec5SDimitry Andric // The base name will be our entry's name. 3920b57cec5SDimitry Andric NameToIndexMap::Entry entry(ConstString(base_name), value); 393d56accc7SDimitry Andric llvm::StringRef decl_context = rmc.ParseFunctionDeclContextName(); 3940b57cec5SDimitry Andric 3950b57cec5SDimitry Andric // Register functions with no context. 3960b57cec5SDimitry Andric if (decl_context.empty()) { 3970b57cec5SDimitry Andric // This has to be a basename 398fe6060f1SDimitry Andric auto &basename_to_index = 399fe6060f1SDimitry Andric GetNameToSymbolIndexMap(lldb::eFunctionNameTypeBase); 400fe6060f1SDimitry Andric basename_to_index.Append(entry); 4010b57cec5SDimitry Andric // If there is no context (no namespaces or class scopes that come before 4020b57cec5SDimitry Andric // the function name) then this also could be a fullname. 403fe6060f1SDimitry Andric auto &name_to_index = GetNameToSymbolIndexMap(lldb::eFunctionNameTypeNone); 404fe6060f1SDimitry Andric name_to_index.Append(entry); 4050b57cec5SDimitry Andric return; 4060b57cec5SDimitry Andric } 4070b57cec5SDimitry Andric 4080b57cec5SDimitry Andric // Make sure we have a pool-string pointer and see if we already know the 4090b57cec5SDimitry Andric // context name. 4100b57cec5SDimitry Andric const char *decl_context_ccstr = ConstString(decl_context).GetCString(); 4110b57cec5SDimitry Andric auto it = class_contexts.find(decl_context_ccstr); 4120b57cec5SDimitry Andric 413fe6060f1SDimitry Andric auto &method_to_index = 414fe6060f1SDimitry Andric GetNameToSymbolIndexMap(lldb::eFunctionNameTypeMethod); 4150b57cec5SDimitry Andric // Register constructors and destructors. They are methods and create 4160b57cec5SDimitry Andric // declaration contexts. 4170b57cec5SDimitry Andric if (rmc.IsCtorOrDtor()) { 418fe6060f1SDimitry Andric method_to_index.Append(entry); 4190b57cec5SDimitry Andric if (it == class_contexts.end()) 4200b57cec5SDimitry Andric class_contexts.insert(it, decl_context_ccstr); 4210b57cec5SDimitry Andric return; 4220b57cec5SDimitry Andric } 4230b57cec5SDimitry Andric 4240b57cec5SDimitry Andric // Register regular methods with a known declaration context. 4250b57cec5SDimitry Andric if (it != class_contexts.end()) { 426fe6060f1SDimitry Andric method_to_index.Append(entry); 4270b57cec5SDimitry Andric return; 4280b57cec5SDimitry Andric } 4290b57cec5SDimitry Andric 4300b57cec5SDimitry Andric // Regular methods in unknown declaration contexts are put to the backlog. We 4310b57cec5SDimitry Andric // will revisit them once we processed all remaining symbols. 4320b57cec5SDimitry Andric backlog.push_back(std::make_pair(entry, decl_context_ccstr)); 4330b57cec5SDimitry Andric } 4340b57cec5SDimitry Andric 4350b57cec5SDimitry Andric void Symtab::RegisterBacklogEntry( 4360b57cec5SDimitry Andric const NameToIndexMap::Entry &entry, const char *decl_context, 4370b57cec5SDimitry Andric const std::set<const char *> &class_contexts) { 438fe6060f1SDimitry Andric auto &method_to_index = 439fe6060f1SDimitry Andric GetNameToSymbolIndexMap(lldb::eFunctionNameTypeMethod); 4400b57cec5SDimitry Andric auto it = class_contexts.find(decl_context); 4410b57cec5SDimitry Andric if (it != class_contexts.end()) { 442fe6060f1SDimitry Andric method_to_index.Append(entry); 4430b57cec5SDimitry Andric } else { 4440b57cec5SDimitry Andric // If we got here, we have something that had a context (was inside 4450b57cec5SDimitry Andric // a namespace or class) yet we don't know the entry 446fe6060f1SDimitry Andric method_to_index.Append(entry); 447fe6060f1SDimitry Andric auto &basename_to_index = 448fe6060f1SDimitry Andric GetNameToSymbolIndexMap(lldb::eFunctionNameTypeBase); 449fe6060f1SDimitry Andric basename_to_index.Append(entry); 4500b57cec5SDimitry Andric } 4510b57cec5SDimitry Andric } 4520b57cec5SDimitry Andric 4530b57cec5SDimitry Andric void Symtab::PreloadSymbols() { 4540b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 4550b57cec5SDimitry Andric InitNameIndexes(); 4560b57cec5SDimitry Andric } 4570b57cec5SDimitry Andric 4580b57cec5SDimitry Andric void Symtab::AppendSymbolNamesToMap(const IndexCollection &indexes, 4590b57cec5SDimitry Andric bool add_demangled, bool add_mangled, 4600b57cec5SDimitry Andric NameToIndexMap &name_to_index_map) const { 461e8d8bef9SDimitry Andric LLDB_SCOPED_TIMER(); 4620b57cec5SDimitry Andric if (add_demangled || add_mangled) { 4630b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 4640b57cec5SDimitry Andric 4650b57cec5SDimitry Andric // Create the name index vector to be able to quickly search by name 4660b57cec5SDimitry Andric const size_t num_indexes = indexes.size(); 4670b57cec5SDimitry Andric for (size_t i = 0; i < num_indexes; ++i) { 4680b57cec5SDimitry Andric uint32_t value = indexes[i]; 4690b57cec5SDimitry Andric assert(i < m_symbols.size()); 4700b57cec5SDimitry Andric const Symbol *symbol = &m_symbols[value]; 4710b57cec5SDimitry Andric 4720b57cec5SDimitry Andric const Mangled &mangled = symbol->GetMangled(); 4730b57cec5SDimitry Andric if (add_demangled) { 4745ffd83dbSDimitry Andric if (ConstString name = mangled.GetDemangledName()) 4750b57cec5SDimitry Andric name_to_index_map.Append(name, value); 4760b57cec5SDimitry Andric } 4770b57cec5SDimitry Andric 4780b57cec5SDimitry Andric if (add_mangled) { 4790b57cec5SDimitry Andric if (ConstString name = mangled.GetMangledName()) 4800b57cec5SDimitry Andric name_to_index_map.Append(name, value); 4810b57cec5SDimitry Andric } 4820b57cec5SDimitry Andric } 4830b57cec5SDimitry Andric } 4840b57cec5SDimitry Andric } 4850b57cec5SDimitry Andric 4860b57cec5SDimitry Andric uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type, 4870b57cec5SDimitry Andric std::vector<uint32_t> &indexes, 4880b57cec5SDimitry Andric uint32_t start_idx, 4890b57cec5SDimitry Andric uint32_t end_index) const { 4900b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 4910b57cec5SDimitry Andric 4920b57cec5SDimitry Andric uint32_t prev_size = indexes.size(); 4930b57cec5SDimitry Andric 4940b57cec5SDimitry Andric const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index); 4950b57cec5SDimitry Andric 4960b57cec5SDimitry Andric for (uint32_t i = start_idx; i < count; ++i) { 4970b57cec5SDimitry Andric if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type) 4980b57cec5SDimitry Andric indexes.push_back(i); 4990b57cec5SDimitry Andric } 5000b57cec5SDimitry Andric 5010b57cec5SDimitry Andric return indexes.size() - prev_size; 5020b57cec5SDimitry Andric } 5030b57cec5SDimitry Andric 5040b57cec5SDimitry Andric uint32_t Symtab::AppendSymbolIndexesWithTypeAndFlagsValue( 5050b57cec5SDimitry Andric SymbolType symbol_type, uint32_t flags_value, 5060b57cec5SDimitry Andric std::vector<uint32_t> &indexes, uint32_t start_idx, 5070b57cec5SDimitry Andric uint32_t end_index) const { 5080b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 5090b57cec5SDimitry Andric 5100b57cec5SDimitry Andric uint32_t prev_size = indexes.size(); 5110b57cec5SDimitry Andric 5120b57cec5SDimitry Andric const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index); 5130b57cec5SDimitry Andric 5140b57cec5SDimitry Andric for (uint32_t i = start_idx; i < count; ++i) { 5150b57cec5SDimitry Andric if ((symbol_type == eSymbolTypeAny || 5160b57cec5SDimitry Andric m_symbols[i].GetType() == symbol_type) && 5170b57cec5SDimitry Andric m_symbols[i].GetFlags() == flags_value) 5180b57cec5SDimitry Andric indexes.push_back(i); 5190b57cec5SDimitry Andric } 5200b57cec5SDimitry Andric 5210b57cec5SDimitry Andric return indexes.size() - prev_size; 5220b57cec5SDimitry Andric } 5230b57cec5SDimitry Andric 5240b57cec5SDimitry Andric uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type, 5250b57cec5SDimitry Andric Debug symbol_debug_type, 5260b57cec5SDimitry Andric Visibility symbol_visibility, 5270b57cec5SDimitry Andric std::vector<uint32_t> &indexes, 5280b57cec5SDimitry Andric uint32_t start_idx, 5290b57cec5SDimitry Andric uint32_t end_index) const { 5300b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 5310b57cec5SDimitry Andric 5320b57cec5SDimitry Andric uint32_t prev_size = indexes.size(); 5330b57cec5SDimitry Andric 5340b57cec5SDimitry Andric const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index); 5350b57cec5SDimitry Andric 5360b57cec5SDimitry Andric for (uint32_t i = start_idx; i < count; ++i) { 5370b57cec5SDimitry Andric if (symbol_type == eSymbolTypeAny || 5380b57cec5SDimitry Andric m_symbols[i].GetType() == symbol_type) { 5390b57cec5SDimitry Andric if (CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility)) 5400b57cec5SDimitry Andric indexes.push_back(i); 5410b57cec5SDimitry Andric } 5420b57cec5SDimitry Andric } 5430b57cec5SDimitry Andric 5440b57cec5SDimitry Andric return indexes.size() - prev_size; 5450b57cec5SDimitry Andric } 5460b57cec5SDimitry Andric 5470b57cec5SDimitry Andric uint32_t Symtab::GetIndexForSymbol(const Symbol *symbol) const { 5480b57cec5SDimitry Andric if (!m_symbols.empty()) { 5490b57cec5SDimitry Andric const Symbol *first_symbol = &m_symbols[0]; 5500b57cec5SDimitry Andric if (symbol >= first_symbol && symbol < first_symbol + m_symbols.size()) 5510b57cec5SDimitry Andric return symbol - first_symbol; 5520b57cec5SDimitry Andric } 5530b57cec5SDimitry Andric return UINT32_MAX; 5540b57cec5SDimitry Andric } 5550b57cec5SDimitry Andric 5560b57cec5SDimitry Andric struct SymbolSortInfo { 5570b57cec5SDimitry Andric const bool sort_by_load_addr; 5580b57cec5SDimitry Andric const Symbol *symbols; 5590b57cec5SDimitry Andric }; 5600b57cec5SDimitry Andric 5610b57cec5SDimitry Andric namespace { 5620b57cec5SDimitry Andric struct SymbolIndexComparator { 5630b57cec5SDimitry Andric const std::vector<Symbol> &symbols; 5640b57cec5SDimitry Andric std::vector<lldb::addr_t> &addr_cache; 5650b57cec5SDimitry Andric 5660b57cec5SDimitry Andric // Getting from the symbol to the Address to the File Address involves some 5670b57cec5SDimitry Andric // work. Since there are potentially many symbols here, and we're using this 5680b57cec5SDimitry Andric // for sorting so we're going to be computing the address many times, cache 5690b57cec5SDimitry Andric // that in addr_cache. The array passed in has to be the same size as the 5700b57cec5SDimitry Andric // symbols array passed into the member variable symbols, and should be 5710b57cec5SDimitry Andric // initialized with LLDB_INVALID_ADDRESS. 5720b57cec5SDimitry Andric // NOTE: You have to make addr_cache externally and pass it in because 5730b57cec5SDimitry Andric // std::stable_sort 5740b57cec5SDimitry Andric // makes copies of the comparator it is initially passed in, and you end up 5750b57cec5SDimitry Andric // spending huge amounts of time copying this array... 5760b57cec5SDimitry Andric 5770b57cec5SDimitry Andric SymbolIndexComparator(const std::vector<Symbol> &s, 5780b57cec5SDimitry Andric std::vector<lldb::addr_t> &a) 5790b57cec5SDimitry Andric : symbols(s), addr_cache(a) { 5800b57cec5SDimitry Andric assert(symbols.size() == addr_cache.size()); 5810b57cec5SDimitry Andric } 5820b57cec5SDimitry Andric bool operator()(uint32_t index_a, uint32_t index_b) { 5830b57cec5SDimitry Andric addr_t value_a = addr_cache[index_a]; 5840b57cec5SDimitry Andric if (value_a == LLDB_INVALID_ADDRESS) { 5850b57cec5SDimitry Andric value_a = symbols[index_a].GetAddressRef().GetFileAddress(); 5860b57cec5SDimitry Andric addr_cache[index_a] = value_a; 5870b57cec5SDimitry Andric } 5880b57cec5SDimitry Andric 5890b57cec5SDimitry Andric addr_t value_b = addr_cache[index_b]; 5900b57cec5SDimitry Andric if (value_b == LLDB_INVALID_ADDRESS) { 5910b57cec5SDimitry Andric value_b = symbols[index_b].GetAddressRef().GetFileAddress(); 5920b57cec5SDimitry Andric addr_cache[index_b] = value_b; 5930b57cec5SDimitry Andric } 5940b57cec5SDimitry Andric 5950b57cec5SDimitry Andric if (value_a == value_b) { 5960b57cec5SDimitry Andric // The if the values are equal, use the original symbol user ID 5970b57cec5SDimitry Andric lldb::user_id_t uid_a = symbols[index_a].GetID(); 5980b57cec5SDimitry Andric lldb::user_id_t uid_b = symbols[index_b].GetID(); 5990b57cec5SDimitry Andric if (uid_a < uid_b) 6000b57cec5SDimitry Andric return true; 6010b57cec5SDimitry Andric if (uid_a > uid_b) 6020b57cec5SDimitry Andric return false; 6030b57cec5SDimitry Andric return false; 6040b57cec5SDimitry Andric } else if (value_a < value_b) 6050b57cec5SDimitry Andric return true; 6060b57cec5SDimitry Andric 6070b57cec5SDimitry Andric return false; 6080b57cec5SDimitry Andric } 6090b57cec5SDimitry Andric }; 6100b57cec5SDimitry Andric } 6110b57cec5SDimitry Andric 6120b57cec5SDimitry Andric void Symtab::SortSymbolIndexesByValue(std::vector<uint32_t> &indexes, 6130b57cec5SDimitry Andric bool remove_duplicates) const { 6140b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 615e8d8bef9SDimitry Andric LLDB_SCOPED_TIMER(); 6160b57cec5SDimitry Andric // No need to sort if we have zero or one items... 6170b57cec5SDimitry Andric if (indexes.size() <= 1) 6180b57cec5SDimitry Andric return; 6190b57cec5SDimitry Andric 6200b57cec5SDimitry Andric // Sort the indexes in place using std::stable_sort. 6210b57cec5SDimitry Andric // NOTE: The use of std::stable_sort instead of llvm::sort here is strictly 6220b57cec5SDimitry Andric // for performance, not correctness. The indexes vector tends to be "close" 6230b57cec5SDimitry Andric // to sorted, which the stable sort handles better. 6240b57cec5SDimitry Andric 6250b57cec5SDimitry Andric std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS); 6260b57cec5SDimitry Andric 6270b57cec5SDimitry Andric SymbolIndexComparator comparator(m_symbols, addr_cache); 6280b57cec5SDimitry Andric std::stable_sort(indexes.begin(), indexes.end(), comparator); 6290b57cec5SDimitry Andric 6300b57cec5SDimitry Andric // Remove any duplicates if requested 6310b57cec5SDimitry Andric if (remove_duplicates) { 6320b57cec5SDimitry Andric auto last = std::unique(indexes.begin(), indexes.end()); 6330b57cec5SDimitry Andric indexes.erase(last, indexes.end()); 6340b57cec5SDimitry Andric } 6350b57cec5SDimitry Andric } 6360b57cec5SDimitry Andric 637fe6060f1SDimitry Andric uint32_t Symtab::GetNameIndexes(ConstString symbol_name, 638fe6060f1SDimitry Andric std::vector<uint32_t> &indexes) { 639fe6060f1SDimitry Andric auto &name_to_index = GetNameToSymbolIndexMap(lldb::eFunctionNameTypeNone); 640fe6060f1SDimitry Andric const uint32_t count = name_to_index.GetValues(symbol_name, indexes); 641fe6060f1SDimitry Andric if (count) 642fe6060f1SDimitry Andric return count; 643fe6060f1SDimitry Andric // Synthetic symbol names are not added to the name indexes, but they start 644fe6060f1SDimitry Andric // with a prefix and end with a the symbol UserID. This allows users to find 645fe6060f1SDimitry Andric // these symbols without having to add them to the name indexes. These 646fe6060f1SDimitry Andric // queries will not happen very often since the names don't mean anything, so 647fe6060f1SDimitry Andric // performance is not paramount in this case. 648fe6060f1SDimitry Andric llvm::StringRef name = symbol_name.GetStringRef(); 649fe6060f1SDimitry Andric // String the synthetic prefix if the name starts with it. 650fe6060f1SDimitry Andric if (!name.consume_front(Symbol::GetSyntheticSymbolPrefix())) 651fe6060f1SDimitry Andric return 0; // Not a synthetic symbol name 652fe6060f1SDimitry Andric 653fe6060f1SDimitry Andric // Extract the user ID from the symbol name 654fe6060f1SDimitry Andric unsigned long long uid = 0; 655fe6060f1SDimitry Andric if (getAsUnsignedInteger(name, /*Radix=*/10, uid)) 656fe6060f1SDimitry Andric return 0; // Failed to extract the user ID as an integer 657fe6060f1SDimitry Andric Symbol *symbol = FindSymbolByID(uid); 658fe6060f1SDimitry Andric if (symbol == nullptr) 659fe6060f1SDimitry Andric return 0; 660fe6060f1SDimitry Andric const uint32_t symbol_idx = GetIndexForSymbol(symbol); 661fe6060f1SDimitry Andric if (symbol_idx == UINT32_MAX) 662fe6060f1SDimitry Andric return 0; 663fe6060f1SDimitry Andric indexes.push_back(symbol_idx); 664fe6060f1SDimitry Andric return 1; 665fe6060f1SDimitry Andric } 666fe6060f1SDimitry Andric 6670b57cec5SDimitry Andric uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name, 6680b57cec5SDimitry Andric std::vector<uint32_t> &indexes) { 6690b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 6700b57cec5SDimitry Andric 6710b57cec5SDimitry Andric if (symbol_name) { 6720b57cec5SDimitry Andric if (!m_name_indexes_computed) 6730b57cec5SDimitry Andric InitNameIndexes(); 6740b57cec5SDimitry Andric 675fe6060f1SDimitry Andric return GetNameIndexes(symbol_name, indexes); 6760b57cec5SDimitry Andric } 6770b57cec5SDimitry Andric return 0; 6780b57cec5SDimitry Andric } 6790b57cec5SDimitry Andric 6800b57cec5SDimitry Andric uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name, 6810b57cec5SDimitry Andric Debug symbol_debug_type, 6820b57cec5SDimitry Andric Visibility symbol_visibility, 6830b57cec5SDimitry Andric std::vector<uint32_t> &indexes) { 6840b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 6850b57cec5SDimitry Andric 686e8d8bef9SDimitry Andric LLDB_SCOPED_TIMER(); 6870b57cec5SDimitry Andric if (symbol_name) { 6880b57cec5SDimitry Andric const size_t old_size = indexes.size(); 6890b57cec5SDimitry Andric if (!m_name_indexes_computed) 6900b57cec5SDimitry Andric InitNameIndexes(); 6910b57cec5SDimitry Andric 6920b57cec5SDimitry Andric std::vector<uint32_t> all_name_indexes; 6930b57cec5SDimitry Andric const size_t name_match_count = 694fe6060f1SDimitry Andric GetNameIndexes(symbol_name, all_name_indexes); 6950b57cec5SDimitry Andric for (size_t i = 0; i < name_match_count; ++i) { 6960b57cec5SDimitry Andric if (CheckSymbolAtIndex(all_name_indexes[i], symbol_debug_type, 6970b57cec5SDimitry Andric symbol_visibility)) 6980b57cec5SDimitry Andric indexes.push_back(all_name_indexes[i]); 6990b57cec5SDimitry Andric } 7000b57cec5SDimitry Andric return indexes.size() - old_size; 7010b57cec5SDimitry Andric } 7020b57cec5SDimitry Andric return 0; 7030b57cec5SDimitry Andric } 7040b57cec5SDimitry Andric 7050b57cec5SDimitry Andric uint32_t 7060b57cec5SDimitry Andric Symtab::AppendSymbolIndexesWithNameAndType(ConstString symbol_name, 7070b57cec5SDimitry Andric SymbolType symbol_type, 7080b57cec5SDimitry Andric std::vector<uint32_t> &indexes) { 7090b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 7100b57cec5SDimitry Andric 7110b57cec5SDimitry Andric if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0) { 7120b57cec5SDimitry Andric std::vector<uint32_t>::iterator pos = indexes.begin(); 7130b57cec5SDimitry Andric while (pos != indexes.end()) { 7140b57cec5SDimitry Andric if (symbol_type == eSymbolTypeAny || 7150b57cec5SDimitry Andric m_symbols[*pos].GetType() == symbol_type) 7160b57cec5SDimitry Andric ++pos; 7170b57cec5SDimitry Andric else 7180b57cec5SDimitry Andric pos = indexes.erase(pos); 7190b57cec5SDimitry Andric } 7200b57cec5SDimitry Andric } 7210b57cec5SDimitry Andric return indexes.size(); 7220b57cec5SDimitry Andric } 7230b57cec5SDimitry Andric 7240b57cec5SDimitry Andric uint32_t Symtab::AppendSymbolIndexesWithNameAndType( 7250b57cec5SDimitry Andric ConstString symbol_name, SymbolType symbol_type, 7260b57cec5SDimitry Andric Debug symbol_debug_type, Visibility symbol_visibility, 7270b57cec5SDimitry Andric std::vector<uint32_t> &indexes) { 7280b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 7290b57cec5SDimitry Andric 7300b57cec5SDimitry Andric if (AppendSymbolIndexesWithName(symbol_name, symbol_debug_type, 7310b57cec5SDimitry Andric symbol_visibility, indexes) > 0) { 7320b57cec5SDimitry Andric std::vector<uint32_t>::iterator pos = indexes.begin(); 7330b57cec5SDimitry Andric while (pos != indexes.end()) { 7340b57cec5SDimitry Andric if (symbol_type == eSymbolTypeAny || 7350b57cec5SDimitry Andric m_symbols[*pos].GetType() == symbol_type) 7360b57cec5SDimitry Andric ++pos; 7370b57cec5SDimitry Andric else 7380b57cec5SDimitry Andric pos = indexes.erase(pos); 7390b57cec5SDimitry Andric } 7400b57cec5SDimitry Andric } 7410b57cec5SDimitry Andric return indexes.size(); 7420b57cec5SDimitry Andric } 7430b57cec5SDimitry Andric 7440b57cec5SDimitry Andric uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType( 7450b57cec5SDimitry Andric const RegularExpression ®exp, SymbolType symbol_type, 746bdd1243dSDimitry Andric std::vector<uint32_t> &indexes, Mangled::NamePreference name_preference) { 7470b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 7480b57cec5SDimitry Andric 7490b57cec5SDimitry Andric uint32_t prev_size = indexes.size(); 7500b57cec5SDimitry Andric uint32_t sym_end = m_symbols.size(); 7510b57cec5SDimitry Andric 7520b57cec5SDimitry Andric for (uint32_t i = 0; i < sym_end; i++) { 7530b57cec5SDimitry Andric if (symbol_type == eSymbolTypeAny || 7540b57cec5SDimitry Andric m_symbols[i].GetType() == symbol_type) { 755bdd1243dSDimitry Andric const char *name = 756bdd1243dSDimitry Andric m_symbols[i].GetMangled().GetName(name_preference).AsCString(); 7570b57cec5SDimitry Andric if (name) { 7580b57cec5SDimitry Andric if (regexp.Execute(name)) 7590b57cec5SDimitry Andric indexes.push_back(i); 7600b57cec5SDimitry Andric } 7610b57cec5SDimitry Andric } 7620b57cec5SDimitry Andric } 7630b57cec5SDimitry Andric return indexes.size() - prev_size; 7640b57cec5SDimitry Andric } 7650b57cec5SDimitry Andric 7660b57cec5SDimitry Andric uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType( 7670b57cec5SDimitry Andric const RegularExpression ®exp, SymbolType symbol_type, 7680b57cec5SDimitry Andric Debug symbol_debug_type, Visibility symbol_visibility, 769bdd1243dSDimitry Andric std::vector<uint32_t> &indexes, Mangled::NamePreference name_preference) { 7700b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 7710b57cec5SDimitry Andric 7720b57cec5SDimitry Andric uint32_t prev_size = indexes.size(); 7730b57cec5SDimitry Andric uint32_t sym_end = m_symbols.size(); 7740b57cec5SDimitry Andric 7750b57cec5SDimitry Andric for (uint32_t i = 0; i < sym_end; i++) { 7760b57cec5SDimitry Andric if (symbol_type == eSymbolTypeAny || 7770b57cec5SDimitry Andric m_symbols[i].GetType() == symbol_type) { 7780b57cec5SDimitry Andric if (!CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility)) 7790b57cec5SDimitry Andric continue; 7800b57cec5SDimitry Andric 781bdd1243dSDimitry Andric const char *name = 782bdd1243dSDimitry Andric m_symbols[i].GetMangled().GetName(name_preference).AsCString(); 7830b57cec5SDimitry Andric if (name) { 7840b57cec5SDimitry Andric if (regexp.Execute(name)) 7850b57cec5SDimitry Andric indexes.push_back(i); 7860b57cec5SDimitry Andric } 7870b57cec5SDimitry Andric } 7880b57cec5SDimitry Andric } 7890b57cec5SDimitry Andric return indexes.size() - prev_size; 7900b57cec5SDimitry Andric } 7910b57cec5SDimitry Andric 7920b57cec5SDimitry Andric Symbol *Symtab::FindSymbolWithType(SymbolType symbol_type, 7930b57cec5SDimitry Andric Debug symbol_debug_type, 7940b57cec5SDimitry Andric Visibility symbol_visibility, 7950b57cec5SDimitry Andric uint32_t &start_idx) { 7960b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 7970b57cec5SDimitry Andric 7980b57cec5SDimitry Andric const size_t count = m_symbols.size(); 7990b57cec5SDimitry Andric for (size_t idx = start_idx; idx < count; ++idx) { 8000b57cec5SDimitry Andric if (symbol_type == eSymbolTypeAny || 8010b57cec5SDimitry Andric m_symbols[idx].GetType() == symbol_type) { 8020b57cec5SDimitry Andric if (CheckSymbolAtIndex(idx, symbol_debug_type, symbol_visibility)) { 8030b57cec5SDimitry Andric start_idx = idx; 8040b57cec5SDimitry Andric return &m_symbols[idx]; 8050b57cec5SDimitry Andric } 8060b57cec5SDimitry Andric } 8070b57cec5SDimitry Andric } 8080b57cec5SDimitry Andric return nullptr; 8090b57cec5SDimitry Andric } 8100b57cec5SDimitry Andric 8119dba64beSDimitry Andric void 8120b57cec5SDimitry Andric Symtab::FindAllSymbolsWithNameAndType(ConstString name, 8130b57cec5SDimitry Andric SymbolType symbol_type, 8140b57cec5SDimitry Andric std::vector<uint32_t> &symbol_indexes) { 8150b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 8160b57cec5SDimitry Andric 8170b57cec5SDimitry Andric // Initialize all of the lookup by name indexes before converting NAME to a 8180b57cec5SDimitry Andric // uniqued string NAME_STR below. 8190b57cec5SDimitry Andric if (!m_name_indexes_computed) 8200b57cec5SDimitry Andric InitNameIndexes(); 8210b57cec5SDimitry Andric 8220b57cec5SDimitry Andric if (name) { 8230b57cec5SDimitry Andric // The string table did have a string that matched, but we need to check 8240b57cec5SDimitry Andric // the symbols and match the symbol_type if any was given. 8250b57cec5SDimitry Andric AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_indexes); 8260b57cec5SDimitry Andric } 8270b57cec5SDimitry Andric } 8280b57cec5SDimitry Andric 8299dba64beSDimitry Andric void Symtab::FindAllSymbolsWithNameAndType( 8300b57cec5SDimitry Andric ConstString name, SymbolType symbol_type, Debug symbol_debug_type, 8310b57cec5SDimitry Andric Visibility symbol_visibility, std::vector<uint32_t> &symbol_indexes) { 8320b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 8330b57cec5SDimitry Andric 834e8d8bef9SDimitry Andric LLDB_SCOPED_TIMER(); 8350b57cec5SDimitry Andric // Initialize all of the lookup by name indexes before converting NAME to a 8360b57cec5SDimitry Andric // uniqued string NAME_STR below. 8370b57cec5SDimitry Andric if (!m_name_indexes_computed) 8380b57cec5SDimitry Andric InitNameIndexes(); 8390b57cec5SDimitry Andric 8400b57cec5SDimitry Andric if (name) { 8410b57cec5SDimitry Andric // The string table did have a string that matched, but we need to check 8420b57cec5SDimitry Andric // the symbols and match the symbol_type if any was given. 8430b57cec5SDimitry Andric AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type, 8440b57cec5SDimitry Andric symbol_visibility, symbol_indexes); 8450b57cec5SDimitry Andric } 8460b57cec5SDimitry Andric } 8470b57cec5SDimitry Andric 8489dba64beSDimitry Andric void Symtab::FindAllSymbolsMatchingRexExAndType( 8490b57cec5SDimitry Andric const RegularExpression ®ex, SymbolType symbol_type, 8500b57cec5SDimitry Andric Debug symbol_debug_type, Visibility symbol_visibility, 851bdd1243dSDimitry Andric std::vector<uint32_t> &symbol_indexes, 852bdd1243dSDimitry Andric Mangled::NamePreference name_preference) { 8530b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 8540b57cec5SDimitry Andric 8550b57cec5SDimitry Andric AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_debug_type, 856bdd1243dSDimitry Andric symbol_visibility, symbol_indexes, 857bdd1243dSDimitry Andric name_preference); 8580b57cec5SDimitry Andric } 8590b57cec5SDimitry Andric 8600b57cec5SDimitry Andric Symbol *Symtab::FindFirstSymbolWithNameAndType(ConstString name, 8610b57cec5SDimitry Andric SymbolType symbol_type, 8620b57cec5SDimitry Andric Debug symbol_debug_type, 8630b57cec5SDimitry Andric Visibility symbol_visibility) { 8640b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 865e8d8bef9SDimitry Andric LLDB_SCOPED_TIMER(); 8660b57cec5SDimitry Andric if (!m_name_indexes_computed) 8670b57cec5SDimitry Andric InitNameIndexes(); 8680b57cec5SDimitry Andric 8690b57cec5SDimitry Andric if (name) { 8700b57cec5SDimitry Andric std::vector<uint32_t> matching_indexes; 8710b57cec5SDimitry Andric // The string table did have a string that matched, but we need to check 8720b57cec5SDimitry Andric // the symbols and match the symbol_type if any was given. 8730b57cec5SDimitry Andric if (AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type, 8740b57cec5SDimitry Andric symbol_visibility, 8750b57cec5SDimitry Andric matching_indexes)) { 8760b57cec5SDimitry Andric std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end(); 8770b57cec5SDimitry Andric for (pos = matching_indexes.begin(); pos != end; ++pos) { 8780b57cec5SDimitry Andric Symbol *symbol = SymbolAtIndex(*pos); 8790b57cec5SDimitry Andric 8800b57cec5SDimitry Andric if (symbol->Compare(name, symbol_type)) 8810b57cec5SDimitry Andric return symbol; 8820b57cec5SDimitry Andric } 8830b57cec5SDimitry Andric } 8840b57cec5SDimitry Andric } 8850b57cec5SDimitry Andric return nullptr; 8860b57cec5SDimitry Andric } 8870b57cec5SDimitry Andric 8880b57cec5SDimitry Andric typedef struct { 8890b57cec5SDimitry Andric const Symtab *symtab; 8900b57cec5SDimitry Andric const addr_t file_addr; 8910b57cec5SDimitry Andric Symbol *match_symbol; 8920b57cec5SDimitry Andric const uint32_t *match_index_ptr; 8930b57cec5SDimitry Andric addr_t match_offset; 8940b57cec5SDimitry Andric } SymbolSearchInfo; 8950b57cec5SDimitry Andric 8960b57cec5SDimitry Andric // Add all the section file start address & size to the RangeVector, recusively 8970b57cec5SDimitry Andric // adding any children sections. 8980b57cec5SDimitry Andric static void AddSectionsToRangeMap(SectionList *sectlist, 8990b57cec5SDimitry Andric RangeVector<addr_t, addr_t> §ion_ranges) { 9000b57cec5SDimitry Andric const int num_sections = sectlist->GetNumSections(0); 9010b57cec5SDimitry Andric for (int i = 0; i < num_sections; i++) { 9020b57cec5SDimitry Andric SectionSP sect_sp = sectlist->GetSectionAtIndex(i); 9030b57cec5SDimitry Andric if (sect_sp) { 9040b57cec5SDimitry Andric SectionList &child_sectlist = sect_sp->GetChildren(); 9050b57cec5SDimitry Andric 9060b57cec5SDimitry Andric // If this section has children, add the children to the RangeVector. 9070b57cec5SDimitry Andric // Else add this section to the RangeVector. 9080b57cec5SDimitry Andric if (child_sectlist.GetNumSections(0) > 0) { 9090b57cec5SDimitry Andric AddSectionsToRangeMap(&child_sectlist, section_ranges); 9100b57cec5SDimitry Andric } else { 9110b57cec5SDimitry Andric size_t size = sect_sp->GetByteSize(); 9120b57cec5SDimitry Andric if (size > 0) { 9130b57cec5SDimitry Andric addr_t base_addr = sect_sp->GetFileAddress(); 9140b57cec5SDimitry Andric RangeVector<addr_t, addr_t>::Entry entry; 9150b57cec5SDimitry Andric entry.SetRangeBase(base_addr); 9160b57cec5SDimitry Andric entry.SetByteSize(size); 9170b57cec5SDimitry Andric section_ranges.Append(entry); 9180b57cec5SDimitry Andric } 9190b57cec5SDimitry Andric } 9200b57cec5SDimitry Andric } 9210b57cec5SDimitry Andric } 9220b57cec5SDimitry Andric } 9230b57cec5SDimitry Andric 9240b57cec5SDimitry Andric void Symtab::InitAddressIndexes() { 9250b57cec5SDimitry Andric // Protected function, no need to lock mutex... 9260b57cec5SDimitry Andric if (!m_file_addr_to_index_computed && !m_symbols.empty()) { 9270b57cec5SDimitry Andric m_file_addr_to_index_computed = true; 9280b57cec5SDimitry Andric 9290b57cec5SDimitry Andric FileRangeToIndexMap::Entry entry; 9300b57cec5SDimitry Andric const_iterator begin = m_symbols.begin(); 9310b57cec5SDimitry Andric const_iterator end = m_symbols.end(); 9320b57cec5SDimitry Andric for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) { 9330b57cec5SDimitry Andric if (pos->ValueIsAddress()) { 9340b57cec5SDimitry Andric entry.SetRangeBase(pos->GetAddressRef().GetFileAddress()); 9350b57cec5SDimitry Andric entry.SetByteSize(pos->GetByteSize()); 9360b57cec5SDimitry Andric entry.data = std::distance(begin, pos); 9370b57cec5SDimitry Andric m_file_addr_to_index.Append(entry); 9380b57cec5SDimitry Andric } 9390b57cec5SDimitry Andric } 9400b57cec5SDimitry Andric const size_t num_entries = m_file_addr_to_index.GetSize(); 9410b57cec5SDimitry Andric if (num_entries > 0) { 9420b57cec5SDimitry Andric m_file_addr_to_index.Sort(); 9430b57cec5SDimitry Andric 9440b57cec5SDimitry Andric // Create a RangeVector with the start & size of all the sections for 9450b57cec5SDimitry Andric // this objfile. We'll need to check this for any FileRangeToIndexMap 9460b57cec5SDimitry Andric // entries with an uninitialized size, which could potentially be a large 9470b57cec5SDimitry Andric // number so reconstituting the weak pointer is busywork when it is 9480b57cec5SDimitry Andric // invariant information. 9490b57cec5SDimitry Andric SectionList *sectlist = m_objfile->GetSectionList(); 9500b57cec5SDimitry Andric RangeVector<addr_t, addr_t> section_ranges; 9510b57cec5SDimitry Andric if (sectlist) { 9520b57cec5SDimitry Andric AddSectionsToRangeMap(sectlist, section_ranges); 9530b57cec5SDimitry Andric section_ranges.Sort(); 9540b57cec5SDimitry Andric } 9550b57cec5SDimitry Andric 9560b57cec5SDimitry Andric // Iterate through the FileRangeToIndexMap and fill in the size for any 9570b57cec5SDimitry Andric // entries that didn't already have a size from the Symbol (e.g. if we 9580b57cec5SDimitry Andric // have a plain linker symbol with an address only, instead of debug info 9590b57cec5SDimitry Andric // where we get an address and a size and a type, etc.) 9600b57cec5SDimitry Andric for (size_t i = 0; i < num_entries; i++) { 9610b57cec5SDimitry Andric FileRangeToIndexMap::Entry *entry = 9620b57cec5SDimitry Andric m_file_addr_to_index.GetMutableEntryAtIndex(i); 963c14a5a88SDimitry Andric if (entry->GetByteSize() == 0) { 9640b57cec5SDimitry Andric addr_t curr_base_addr = entry->GetRangeBase(); 9650b57cec5SDimitry Andric const RangeVector<addr_t, addr_t>::Entry *containing_section = 9660b57cec5SDimitry Andric section_ranges.FindEntryThatContains(curr_base_addr); 9670b57cec5SDimitry Andric 9680b57cec5SDimitry Andric // Use the end of the section as the default max size of the symbol 9690b57cec5SDimitry Andric addr_t sym_size = 0; 9700b57cec5SDimitry Andric if (containing_section) { 9710b57cec5SDimitry Andric sym_size = 9720b57cec5SDimitry Andric containing_section->GetByteSize() - 9730b57cec5SDimitry Andric (entry->GetRangeBase() - containing_section->GetRangeBase()); 9740b57cec5SDimitry Andric } 9750b57cec5SDimitry Andric 9760b57cec5SDimitry Andric for (size_t j = i; j < num_entries; j++) { 9770b57cec5SDimitry Andric FileRangeToIndexMap::Entry *next_entry = 9780b57cec5SDimitry Andric m_file_addr_to_index.GetMutableEntryAtIndex(j); 9790b57cec5SDimitry Andric addr_t next_base_addr = next_entry->GetRangeBase(); 9800b57cec5SDimitry Andric if (next_base_addr > curr_base_addr) { 9810b57cec5SDimitry Andric addr_t size_to_next_symbol = next_base_addr - curr_base_addr; 9820b57cec5SDimitry Andric 9830b57cec5SDimitry Andric // Take the difference between this symbol and the next one as 9840b57cec5SDimitry Andric // its size, if it is less than the size of the section. 9850b57cec5SDimitry Andric if (sym_size == 0 || size_to_next_symbol < sym_size) { 9860b57cec5SDimitry Andric sym_size = size_to_next_symbol; 9870b57cec5SDimitry Andric } 9880b57cec5SDimitry Andric break; 9890b57cec5SDimitry Andric } 9900b57cec5SDimitry Andric } 9910b57cec5SDimitry Andric 9920b57cec5SDimitry Andric if (sym_size > 0) { 9930b57cec5SDimitry Andric entry->SetByteSize(sym_size); 9940b57cec5SDimitry Andric Symbol &symbol = m_symbols[entry->data]; 9950b57cec5SDimitry Andric symbol.SetByteSize(sym_size); 9960b57cec5SDimitry Andric symbol.SetSizeIsSynthesized(true); 9970b57cec5SDimitry Andric } 9980b57cec5SDimitry Andric } 9990b57cec5SDimitry Andric } 10000b57cec5SDimitry Andric 10010b57cec5SDimitry Andric // Sort again in case the range size changes the ordering 10020b57cec5SDimitry Andric m_file_addr_to_index.Sort(); 10030b57cec5SDimitry Andric } 10040b57cec5SDimitry Andric } 10050b57cec5SDimitry Andric } 10060b57cec5SDimitry Andric 10074824e7fdSDimitry Andric void Symtab::Finalize() { 10080b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 10094824e7fdSDimitry Andric // Calculate the size of symbols inside InitAddressIndexes. 10100b57cec5SDimitry Andric InitAddressIndexes(); 10114824e7fdSDimitry Andric // Shrink to fit the symbols so we don't waste memory 10124824e7fdSDimitry Andric if (m_symbols.capacity() > m_symbols.size()) { 10134824e7fdSDimitry Andric collection new_symbols(m_symbols.begin(), m_symbols.end()); 10144824e7fdSDimitry Andric m_symbols.swap(new_symbols); 10154824e7fdSDimitry Andric } 10160eae32dcSDimitry Andric SaveToCache(); 10170b57cec5SDimitry Andric } 10180b57cec5SDimitry Andric 10190b57cec5SDimitry Andric Symbol *Symtab::FindSymbolAtFileAddress(addr_t file_addr) { 10200b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 10210b57cec5SDimitry Andric if (!m_file_addr_to_index_computed) 10220b57cec5SDimitry Andric InitAddressIndexes(); 10230b57cec5SDimitry Andric 10240b57cec5SDimitry Andric const FileRangeToIndexMap::Entry *entry = 10250b57cec5SDimitry Andric m_file_addr_to_index.FindEntryStartsAt(file_addr); 10260b57cec5SDimitry Andric if (entry) { 10270b57cec5SDimitry Andric Symbol *symbol = SymbolAtIndex(entry->data); 10280b57cec5SDimitry Andric if (symbol->GetFileAddress() == file_addr) 10290b57cec5SDimitry Andric return symbol; 10300b57cec5SDimitry Andric } 10310b57cec5SDimitry Andric return nullptr; 10320b57cec5SDimitry Andric } 10330b57cec5SDimitry Andric 10340b57cec5SDimitry Andric Symbol *Symtab::FindSymbolContainingFileAddress(addr_t file_addr) { 10350b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 10360b57cec5SDimitry Andric 10370b57cec5SDimitry Andric if (!m_file_addr_to_index_computed) 10380b57cec5SDimitry Andric InitAddressIndexes(); 10390b57cec5SDimitry Andric 10400b57cec5SDimitry Andric const FileRangeToIndexMap::Entry *entry = 10410b57cec5SDimitry Andric m_file_addr_to_index.FindEntryThatContains(file_addr); 10420b57cec5SDimitry Andric if (entry) { 10430b57cec5SDimitry Andric Symbol *symbol = SymbolAtIndex(entry->data); 10440b57cec5SDimitry Andric if (symbol->ContainsFileAddress(file_addr)) 10450b57cec5SDimitry Andric return symbol; 10460b57cec5SDimitry Andric } 10470b57cec5SDimitry Andric return nullptr; 10480b57cec5SDimitry Andric } 10490b57cec5SDimitry Andric 10500b57cec5SDimitry Andric void Symtab::ForEachSymbolContainingFileAddress( 10510b57cec5SDimitry Andric addr_t file_addr, std::function<bool(Symbol *)> const &callback) { 10520b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 10530b57cec5SDimitry Andric 10540b57cec5SDimitry Andric if (!m_file_addr_to_index_computed) 10550b57cec5SDimitry Andric InitAddressIndexes(); 10560b57cec5SDimitry Andric 10570b57cec5SDimitry Andric std::vector<uint32_t> all_addr_indexes; 10580b57cec5SDimitry Andric 10590b57cec5SDimitry Andric // Get all symbols with file_addr 10600b57cec5SDimitry Andric const size_t addr_match_count = 10610b57cec5SDimitry Andric m_file_addr_to_index.FindEntryIndexesThatContain(file_addr, 10620b57cec5SDimitry Andric all_addr_indexes); 10630b57cec5SDimitry Andric 10640b57cec5SDimitry Andric for (size_t i = 0; i < addr_match_count; ++i) { 10650b57cec5SDimitry Andric Symbol *symbol = SymbolAtIndex(all_addr_indexes[i]); 10660b57cec5SDimitry Andric if (symbol->ContainsFileAddress(file_addr)) { 10670b57cec5SDimitry Andric if (!callback(symbol)) 10680b57cec5SDimitry Andric break; 10690b57cec5SDimitry Andric } 10700b57cec5SDimitry Andric } 10710b57cec5SDimitry Andric } 10720b57cec5SDimitry Andric 10730b57cec5SDimitry Andric void Symtab::SymbolIndicesToSymbolContextList( 10740b57cec5SDimitry Andric std::vector<uint32_t> &symbol_indexes, SymbolContextList &sc_list) { 10750b57cec5SDimitry Andric // No need to protect this call using m_mutex all other method calls are 10760b57cec5SDimitry Andric // already thread safe. 10770b57cec5SDimitry Andric 10780b57cec5SDimitry Andric const bool merge_symbol_into_function = true; 10790b57cec5SDimitry Andric size_t num_indices = symbol_indexes.size(); 10800b57cec5SDimitry Andric if (num_indices > 0) { 10810b57cec5SDimitry Andric SymbolContext sc; 10820b57cec5SDimitry Andric sc.module_sp = m_objfile->GetModule(); 10830b57cec5SDimitry Andric for (size_t i = 0; i < num_indices; i++) { 10840b57cec5SDimitry Andric sc.symbol = SymbolAtIndex(symbol_indexes[i]); 10850b57cec5SDimitry Andric if (sc.symbol) 10860b57cec5SDimitry Andric sc_list.AppendIfUnique(sc, merge_symbol_into_function); 10870b57cec5SDimitry Andric } 10880b57cec5SDimitry Andric } 10890b57cec5SDimitry Andric } 10900b57cec5SDimitry Andric 10919dba64beSDimitry Andric void Symtab::FindFunctionSymbols(ConstString name, uint32_t name_type_mask, 10920b57cec5SDimitry Andric SymbolContextList &sc_list) { 10930b57cec5SDimitry Andric std::vector<uint32_t> symbol_indexes; 10940b57cec5SDimitry Andric 10950b57cec5SDimitry Andric // eFunctionNameTypeAuto should be pre-resolved by a call to 10960b57cec5SDimitry Andric // Module::LookupInfo::LookupInfo() 10970b57cec5SDimitry Andric assert((name_type_mask & eFunctionNameTypeAuto) == 0); 10980b57cec5SDimitry Andric 10990b57cec5SDimitry Andric if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) { 11000b57cec5SDimitry Andric std::vector<uint32_t> temp_symbol_indexes; 11010b57cec5SDimitry Andric FindAllSymbolsWithNameAndType(name, eSymbolTypeAny, temp_symbol_indexes); 11020b57cec5SDimitry Andric 11030b57cec5SDimitry Andric unsigned temp_symbol_indexes_size = temp_symbol_indexes.size(); 11040b57cec5SDimitry Andric if (temp_symbol_indexes_size > 0) { 11050b57cec5SDimitry Andric std::lock_guard<std::recursive_mutex> guard(m_mutex); 11060b57cec5SDimitry Andric for (unsigned i = 0; i < temp_symbol_indexes_size; i++) { 11070b57cec5SDimitry Andric SymbolContext sym_ctx; 11080b57cec5SDimitry Andric sym_ctx.symbol = SymbolAtIndex(temp_symbol_indexes[i]); 11090b57cec5SDimitry Andric if (sym_ctx.symbol) { 11100b57cec5SDimitry Andric switch (sym_ctx.symbol->GetType()) { 11110b57cec5SDimitry Andric case eSymbolTypeCode: 11120b57cec5SDimitry Andric case eSymbolTypeResolver: 11130b57cec5SDimitry Andric case eSymbolTypeReExported: 1114349cc55cSDimitry Andric case eSymbolTypeAbsolute: 11150b57cec5SDimitry Andric symbol_indexes.push_back(temp_symbol_indexes[i]); 11160b57cec5SDimitry Andric break; 11170b57cec5SDimitry Andric default: 11180b57cec5SDimitry Andric break; 11190b57cec5SDimitry Andric } 11200b57cec5SDimitry Andric } 11210b57cec5SDimitry Andric } 11220b57cec5SDimitry Andric } 11230b57cec5SDimitry Andric } 11240b57cec5SDimitry Andric 11250b57cec5SDimitry Andric if (!m_name_indexes_computed) 11260b57cec5SDimitry Andric InitNameIndexes(); 11270b57cec5SDimitry Andric 1128fe6060f1SDimitry Andric for (lldb::FunctionNameType type : 1129fe6060f1SDimitry Andric {lldb::eFunctionNameTypeBase, lldb::eFunctionNameTypeMethod, 1130fe6060f1SDimitry Andric lldb::eFunctionNameTypeSelector}) { 1131fe6060f1SDimitry Andric if (name_type_mask & type) { 1132fe6060f1SDimitry Andric auto map = GetNameToSymbolIndexMap(type); 1133fe6060f1SDimitry Andric 11340b57cec5SDimitry Andric const UniqueCStringMap<uint32_t>::Entry *match; 1135fe6060f1SDimitry Andric for (match = map.FindFirstValueForName(name); match != nullptr; 1136fe6060f1SDimitry Andric match = map.FindNextValueForName(match)) { 11370b57cec5SDimitry Andric symbol_indexes.push_back(match->value); 11380b57cec5SDimitry Andric } 11390b57cec5SDimitry Andric } 11400b57cec5SDimitry Andric } 11410b57cec5SDimitry Andric 11420b57cec5SDimitry Andric if (!symbol_indexes.empty()) { 1143fcaf7f86SDimitry Andric llvm::sort(symbol_indexes); 11440b57cec5SDimitry Andric symbol_indexes.erase( 11450b57cec5SDimitry Andric std::unique(symbol_indexes.begin(), symbol_indexes.end()), 11460b57cec5SDimitry Andric symbol_indexes.end()); 11470b57cec5SDimitry Andric SymbolIndicesToSymbolContextList(symbol_indexes, sc_list); 11480b57cec5SDimitry Andric } 11490b57cec5SDimitry Andric } 11500b57cec5SDimitry Andric 11510b57cec5SDimitry Andric const Symbol *Symtab::GetParent(Symbol *child_symbol) const { 11520b57cec5SDimitry Andric uint32_t child_idx = GetIndexForSymbol(child_symbol); 11530b57cec5SDimitry Andric if (child_idx != UINT32_MAX && child_idx > 0) { 11540b57cec5SDimitry Andric for (uint32_t idx = child_idx - 1; idx != UINT32_MAX; --idx) { 11550b57cec5SDimitry Andric const Symbol *symbol = SymbolAtIndex(idx); 11560b57cec5SDimitry Andric const uint32_t sibling_idx = symbol->GetSiblingIndex(); 11570b57cec5SDimitry Andric if (sibling_idx != UINT32_MAX && sibling_idx > child_idx) 11580b57cec5SDimitry Andric return symbol; 11590b57cec5SDimitry Andric } 11600b57cec5SDimitry Andric } 11610b57cec5SDimitry Andric return nullptr; 11620b57cec5SDimitry Andric } 11630eae32dcSDimitry Andric 11640eae32dcSDimitry Andric std::string Symtab::GetCacheKey() { 11650eae32dcSDimitry Andric std::string key; 11660eae32dcSDimitry Andric llvm::raw_string_ostream strm(key); 11670eae32dcSDimitry Andric // Symbol table can come from different object files for the same module. A 11680eae32dcSDimitry Andric // module can have one object file as the main executable and might have 11690eae32dcSDimitry Andric // another object file in a separate symbol file. 11700eae32dcSDimitry Andric strm << m_objfile->GetModule()->GetCacheKey() << "-symtab-" 11710eae32dcSDimitry Andric << llvm::format_hex(m_objfile->GetCacheHash(), 10); 11720eae32dcSDimitry Andric return strm.str(); 11730eae32dcSDimitry Andric } 11740eae32dcSDimitry Andric 11750eae32dcSDimitry Andric void Symtab::SaveToCache() { 11760eae32dcSDimitry Andric DataFileCache *cache = Module::GetIndexCache(); 11770eae32dcSDimitry Andric if (!cache) 11780eae32dcSDimitry Andric return; // Caching is not enabled. 11790eae32dcSDimitry Andric InitNameIndexes(); // Init the name indexes so we can cache them as well. 11800eae32dcSDimitry Andric const auto byte_order = endian::InlHostByteOrder(); 11810eae32dcSDimitry Andric DataEncoder file(byte_order, /*addr_size=*/8); 11820eae32dcSDimitry Andric // Encode will return false if the symbol table's object file doesn't have 11830eae32dcSDimitry Andric // anything to make a signature from. 11840eae32dcSDimitry Andric if (Encode(file)) 118504eeddc0SDimitry Andric if (cache->SetCachedData(GetCacheKey(), file.GetData())) 118604eeddc0SDimitry Andric SetWasSavedToCache(); 11870eae32dcSDimitry Andric } 11880eae32dcSDimitry Andric 11890eae32dcSDimitry Andric constexpr llvm::StringLiteral kIdentifierCStrMap("CMAP"); 11900eae32dcSDimitry Andric 11910eae32dcSDimitry Andric static void EncodeCStrMap(DataEncoder &encoder, ConstStringTable &strtab, 11920eae32dcSDimitry Andric const UniqueCStringMap<uint32_t> &cstr_map) { 11930eae32dcSDimitry Andric encoder.AppendData(kIdentifierCStrMap); 11940eae32dcSDimitry Andric encoder.AppendU32(cstr_map.GetSize()); 11950eae32dcSDimitry Andric for (const auto &entry: cstr_map) { 11960eae32dcSDimitry Andric // Make sure there are no empty strings. 11970eae32dcSDimitry Andric assert((bool)entry.cstring); 11980eae32dcSDimitry Andric encoder.AppendU32(strtab.Add(entry.cstring)); 11990eae32dcSDimitry Andric encoder.AppendU32(entry.value); 12000eae32dcSDimitry Andric } 12010eae32dcSDimitry Andric } 12020eae32dcSDimitry Andric 12030eae32dcSDimitry Andric bool DecodeCStrMap(const DataExtractor &data, lldb::offset_t *offset_ptr, 12040eae32dcSDimitry Andric const StringTableReader &strtab, 12050eae32dcSDimitry Andric UniqueCStringMap<uint32_t> &cstr_map) { 12060eae32dcSDimitry Andric llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4); 12070eae32dcSDimitry Andric if (identifier != kIdentifierCStrMap) 12080eae32dcSDimitry Andric return false; 12090eae32dcSDimitry Andric const uint32_t count = data.GetU32(offset_ptr); 121081ad6265SDimitry Andric cstr_map.Reserve(count); 12110eae32dcSDimitry Andric for (uint32_t i=0; i<count; ++i) 12120eae32dcSDimitry Andric { 12130eae32dcSDimitry Andric llvm::StringRef str(strtab.Get(data.GetU32(offset_ptr))); 12140eae32dcSDimitry Andric uint32_t value = data.GetU32(offset_ptr); 12150eae32dcSDimitry Andric // No empty strings in the name indexes in Symtab 12160eae32dcSDimitry Andric if (str.empty()) 12170eae32dcSDimitry Andric return false; 12180eae32dcSDimitry Andric cstr_map.Append(ConstString(str), value); 12190eae32dcSDimitry Andric } 122081ad6265SDimitry Andric // We must sort the UniqueCStringMap after decoding it since it is a vector 122181ad6265SDimitry Andric // of UniqueCStringMap::Entry objects which contain a ConstString and type T. 122281ad6265SDimitry Andric // ConstString objects are sorted by "const char *" and then type T and 122381ad6265SDimitry Andric // the "const char *" are point values that will depend on the order in which 122481ad6265SDimitry Andric // ConstString objects are created and in which of the 256 string pools they 122581ad6265SDimitry Andric // are created in. So after we decode all of the entries, we must sort the 122681ad6265SDimitry Andric // name map to ensure name lookups succeed. If we encode and decode within 122781ad6265SDimitry Andric // the same process we wouldn't need to sort, so unit testing didn't catch 122881ad6265SDimitry Andric // this issue when first checked in. 122981ad6265SDimitry Andric cstr_map.Sort(); 12300eae32dcSDimitry Andric return true; 12310eae32dcSDimitry Andric } 12320eae32dcSDimitry Andric 12330eae32dcSDimitry Andric constexpr llvm::StringLiteral kIdentifierSymbolTable("SYMB"); 12340eae32dcSDimitry Andric constexpr uint32_t CURRENT_CACHE_VERSION = 1; 12350eae32dcSDimitry Andric 12360eae32dcSDimitry Andric /// The encoding format for the symbol table is as follows: 12370eae32dcSDimitry Andric /// 12380eae32dcSDimitry Andric /// Signature signature; 12390eae32dcSDimitry Andric /// ConstStringTable strtab; 12400eae32dcSDimitry Andric /// Identifier four character code: 'SYMB' 12410eae32dcSDimitry Andric /// uint32_t version; 12420eae32dcSDimitry Andric /// uint32_t num_symbols; 12430eae32dcSDimitry Andric /// Symbol symbols[num_symbols]; 12440eae32dcSDimitry Andric /// uint8_t num_cstr_maps; 12450eae32dcSDimitry Andric /// UniqueCStringMap<uint32_t> cstr_maps[num_cstr_maps] 12460eae32dcSDimitry Andric bool Symtab::Encode(DataEncoder &encoder) const { 12470eae32dcSDimitry Andric // Name indexes must be computed before calling this function. 12480eae32dcSDimitry Andric assert(m_name_indexes_computed); 12490eae32dcSDimitry Andric 12500eae32dcSDimitry Andric // Encode the object file's signature 12510eae32dcSDimitry Andric CacheSignature signature(m_objfile); 12520eae32dcSDimitry Andric if (!signature.Encode(encoder)) 12530eae32dcSDimitry Andric return false; 12540eae32dcSDimitry Andric ConstStringTable strtab; 12550eae32dcSDimitry Andric 12560eae32dcSDimitry Andric // Encoder the symbol table into a separate encoder first. This allows us 12570eae32dcSDimitry Andric // gather all of the strings we willl need in "strtab" as we will need to 12580eae32dcSDimitry Andric // write the string table out before the symbol table. 12590eae32dcSDimitry Andric DataEncoder symtab_encoder(encoder.GetByteOrder(), 12600eae32dcSDimitry Andric encoder.GetAddressByteSize()); 12610eae32dcSDimitry Andric symtab_encoder.AppendData(kIdentifierSymbolTable); 12620eae32dcSDimitry Andric // Encode the symtab data version. 12630eae32dcSDimitry Andric symtab_encoder.AppendU32(CURRENT_CACHE_VERSION); 12640eae32dcSDimitry Andric // Encode the number of symbols. 12650eae32dcSDimitry Andric symtab_encoder.AppendU32(m_symbols.size()); 12660eae32dcSDimitry Andric // Encode the symbol data for all symbols. 12670eae32dcSDimitry Andric for (const auto &symbol: m_symbols) 12680eae32dcSDimitry Andric symbol.Encode(symtab_encoder, strtab); 12690eae32dcSDimitry Andric 12700eae32dcSDimitry Andric // Emit a byte for how many C string maps we emit. We will fix this up after 12710eae32dcSDimitry Andric // we emit the C string maps since we skip emitting C string maps if they are 12720eae32dcSDimitry Andric // empty. 12730eae32dcSDimitry Andric size_t num_cmaps_offset = symtab_encoder.GetByteSize(); 12740eae32dcSDimitry Andric uint8_t num_cmaps = 0; 12750eae32dcSDimitry Andric symtab_encoder.AppendU8(0); 12760eae32dcSDimitry Andric for (const auto &pair: m_name_to_symbol_indices) { 12770eae32dcSDimitry Andric if (pair.second.IsEmpty()) 12780eae32dcSDimitry Andric continue; 12790eae32dcSDimitry Andric ++num_cmaps; 12800eae32dcSDimitry Andric symtab_encoder.AppendU8(pair.first); 12810eae32dcSDimitry Andric EncodeCStrMap(symtab_encoder, strtab, pair.second); 12820eae32dcSDimitry Andric } 12830eae32dcSDimitry Andric if (num_cmaps > 0) 12840eae32dcSDimitry Andric symtab_encoder.PutU8(num_cmaps_offset, num_cmaps); 12850eae32dcSDimitry Andric 12860eae32dcSDimitry Andric // Now that all strings have been gathered, we will emit the string table. 12870eae32dcSDimitry Andric strtab.Encode(encoder); 12880eae32dcSDimitry Andric // Followed the the symbol table data. 12890eae32dcSDimitry Andric encoder.AppendData(symtab_encoder.GetData()); 12900eae32dcSDimitry Andric return true; 12910eae32dcSDimitry Andric } 12920eae32dcSDimitry Andric 12930eae32dcSDimitry Andric bool Symtab::Decode(const DataExtractor &data, lldb::offset_t *offset_ptr, 12940eae32dcSDimitry Andric bool &signature_mismatch) { 12950eae32dcSDimitry Andric signature_mismatch = false; 12960eae32dcSDimitry Andric CacheSignature signature; 12970eae32dcSDimitry Andric StringTableReader strtab; 12980eae32dcSDimitry Andric { // Scope for "elapsed" object below so it can measure the time parse. 12990eae32dcSDimitry Andric ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabParseTime()); 13000eae32dcSDimitry Andric if (!signature.Decode(data, offset_ptr)) 13010eae32dcSDimitry Andric return false; 13020eae32dcSDimitry Andric if (CacheSignature(m_objfile) != signature) { 13030eae32dcSDimitry Andric signature_mismatch = true; 13040eae32dcSDimitry Andric return false; 13050eae32dcSDimitry Andric } 13060eae32dcSDimitry Andric // We now decode the string table for all strings in the data cache file. 13070eae32dcSDimitry Andric if (!strtab.Decode(data, offset_ptr)) 13080eae32dcSDimitry Andric return false; 13090eae32dcSDimitry Andric 13100eae32dcSDimitry Andric // And now we can decode the symbol table with string table we just decoded. 13110eae32dcSDimitry Andric llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4); 13120eae32dcSDimitry Andric if (identifier != kIdentifierSymbolTable) 13130eae32dcSDimitry Andric return false; 13140eae32dcSDimitry Andric const uint32_t version = data.GetU32(offset_ptr); 13150eae32dcSDimitry Andric if (version != CURRENT_CACHE_VERSION) 13160eae32dcSDimitry Andric return false; 13170eae32dcSDimitry Andric const uint32_t num_symbols = data.GetU32(offset_ptr); 13180eae32dcSDimitry Andric if (num_symbols == 0) 13190eae32dcSDimitry Andric return true; 13200eae32dcSDimitry Andric m_symbols.resize(num_symbols); 13210eae32dcSDimitry Andric SectionList *sections = m_objfile->GetModule()->GetSectionList(); 13220eae32dcSDimitry Andric for (uint32_t i=0; i<num_symbols; ++i) { 13230eae32dcSDimitry Andric if (!m_symbols[i].Decode(data, offset_ptr, sections, strtab)) 13240eae32dcSDimitry Andric return false; 13250eae32dcSDimitry Andric } 13260eae32dcSDimitry Andric } 13270eae32dcSDimitry Andric 13280eae32dcSDimitry Andric { // Scope for "elapsed" object below so it can measure the time to index. 13290eae32dcSDimitry Andric ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabIndexTime()); 13300eae32dcSDimitry Andric const uint8_t num_cstr_maps = data.GetU8(offset_ptr); 13310eae32dcSDimitry Andric for (uint8_t i=0; i<num_cstr_maps; ++i) { 13320eae32dcSDimitry Andric uint8_t type = data.GetU8(offset_ptr); 13330eae32dcSDimitry Andric UniqueCStringMap<uint32_t> &cstr_map = 13340eae32dcSDimitry Andric GetNameToSymbolIndexMap((lldb::FunctionNameType)type); 13350eae32dcSDimitry Andric if (!DecodeCStrMap(data, offset_ptr, strtab, cstr_map)) 13360eae32dcSDimitry Andric return false; 13370eae32dcSDimitry Andric } 13380eae32dcSDimitry Andric m_name_indexes_computed = true; 13390eae32dcSDimitry Andric } 13400eae32dcSDimitry Andric return true; 13410eae32dcSDimitry Andric } 13420eae32dcSDimitry Andric 13430eae32dcSDimitry Andric bool Symtab::LoadFromCache() { 13440eae32dcSDimitry Andric DataFileCache *cache = Module::GetIndexCache(); 13450eae32dcSDimitry Andric if (!cache) 13460eae32dcSDimitry Andric return false; 13470eae32dcSDimitry Andric 13480eae32dcSDimitry Andric std::unique_ptr<llvm::MemoryBuffer> mem_buffer_up = 13490eae32dcSDimitry Andric cache->GetCachedData(GetCacheKey()); 13500eae32dcSDimitry Andric if (!mem_buffer_up) 13510eae32dcSDimitry Andric return false; 13520eae32dcSDimitry Andric DataExtractor data(mem_buffer_up->getBufferStart(), 13530eae32dcSDimitry Andric mem_buffer_up->getBufferSize(), 13540eae32dcSDimitry Andric m_objfile->GetByteOrder(), 13550eae32dcSDimitry Andric m_objfile->GetAddressByteSize()); 13560eae32dcSDimitry Andric bool signature_mismatch = false; 13570eae32dcSDimitry Andric lldb::offset_t offset = 0; 13580eae32dcSDimitry Andric const bool result = Decode(data, &offset, signature_mismatch); 13590eae32dcSDimitry Andric if (signature_mismatch) 13600eae32dcSDimitry Andric cache->RemoveCacheFile(GetCacheKey()); 136104eeddc0SDimitry Andric if (result) 136204eeddc0SDimitry Andric SetWasLoadedFromCache(); 13630eae32dcSDimitry Andric return result; 13640eae32dcSDimitry Andric } 1365