1 //===-- Symtab.cpp ----------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
13 #include "Plugins/Language/ObjC/ObjCLanguage.h"
15 #include "lldb/Core/Module.h"
16 #include "lldb/Core/RichManglingContext.h"
17 #include "lldb/Core/STLUtils.h"
18 #include "lldb/Core/Section.h"
19 #include "lldb/Symbol/ObjectFile.h"
20 #include "lldb/Symbol/Symbol.h"
21 #include "lldb/Symbol/SymbolContext.h"
22 #include "lldb/Symbol/Symtab.h"
23 #include "lldb/Utility/RegularExpression.h"
24 #include "lldb/Utility/Stream.h"
25 #include "lldb/Utility/Timer.h"
27 #include "llvm/ADT/StringRef.h"
30 using namespace lldb_private;
32 Symtab::Symtab(ObjectFile *objfile)
33 : m_objfile(objfile), m_symbols(), m_file_addr_to_index(),
34 m_name_to_index(), m_mutex(), m_file_addr_to_index_computed(false),
35 m_name_indexes_computed(false) {}
39 void Symtab::Reserve(size_t count) {
40 // Clients should grab the mutex from this symbol table and lock it manually
41 // when calling this function to avoid performance issues.
42 m_symbols.reserve(count);
45 Symbol *Symtab::Resize(size_t count) {
46 // Clients should grab the mutex from this symbol table and lock it manually
47 // when calling this function to avoid performance issues.
48 m_symbols.resize(count);
49 return m_symbols.empty() ? nullptr : &m_symbols[0];
52 uint32_t Symtab::AddSymbol(const Symbol &symbol) {
53 // Clients should grab the mutex from this symbol table and lock it manually
54 // when calling this function to avoid performance issues.
55 uint32_t symbol_idx = m_symbols.size();
56 m_name_to_index.Clear();
57 m_file_addr_to_index.Clear();
58 m_symbols.push_back(symbol);
59 m_file_addr_to_index_computed = false;
60 m_name_indexes_computed = false;
64 size_t Symtab::GetNumSymbols() const {
65 std::lock_guard<std::recursive_mutex> guard(m_mutex);
66 return m_symbols.size();
69 void Symtab::SectionFileAddressesChanged() {
70 m_name_to_index.Clear();
71 m_file_addr_to_index_computed = false;
74 void Symtab::Dump(Stream *s, Target *target, SortOrder sort_order) {
75 std::lock_guard<std::recursive_mutex> guard(m_mutex);
77 // s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
79 const FileSpec &file_spec = m_objfile->GetFileSpec();
80 const char *object_name = nullptr;
81 if (m_objfile->GetModule())
82 object_name = m_objfile->GetModule()->GetObjectName().GetCString();
85 s->Printf("Symtab, file = %s%s%s%s, num_symbols = %" PRIu64,
86 file_spec.GetPath().c_str(), object_name ? "(" : "",
87 object_name ? object_name : "", object_name ? ")" : "",
88 (uint64_t)m_symbols.size());
90 s->Printf("Symtab, num_symbols = %" PRIu64 "", (uint64_t)m_symbols.size());
92 if (!m_symbols.empty()) {
94 case eSortOrderNone: {
97 const_iterator begin = m_symbols.begin();
98 const_iterator end = m_symbols.end();
99 for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
101 pos->Dump(s, target, std::distance(begin, pos));
105 case eSortOrderByName: {
106 // Although we maintain a lookup by exact name map, the table isn't
107 // sorted by name. So we must make the ordered symbol list up ourselves.
108 s->PutCString(" (sorted by name):\n");
110 typedef std::multimap<const char *, const Symbol *,
111 CStringCompareFunctionObject>
113 CStringToSymbol name_map;
114 for (const_iterator pos = m_symbols.begin(), end = m_symbols.end();
116 const char *name = pos->GetName().AsCString();
118 name_map.insert(std::make_pair(name, &(*pos)));
121 for (CStringToSymbol::const_iterator pos = name_map.begin(),
122 end = name_map.end();
125 pos->second->Dump(s, target, pos->second - &m_symbols[0]);
129 case eSortOrderByAddress:
130 s->PutCString(" (sorted by address):\n");
132 if (!m_file_addr_to_index_computed)
133 InitAddressIndexes();
134 const size_t num_entries = m_file_addr_to_index.GetSize();
135 for (size_t i = 0; i < num_entries; ++i) {
137 const uint32_t symbol_idx = m_file_addr_to_index.GetEntryRef(i).data;
138 m_symbols[symbol_idx].Dump(s, target, symbol_idx);
147 void Symtab::Dump(Stream *s, Target *target,
148 std::vector<uint32_t> &indexes) const {
149 std::lock_guard<std::recursive_mutex> guard(m_mutex);
151 const size_t num_symbols = GetNumSymbols();
152 // s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
154 s->Printf("Symtab %" PRIu64 " symbol indexes (%" PRIu64 " symbols total):\n",
155 (uint64_t)indexes.size(), (uint64_t)m_symbols.size());
158 if (!indexes.empty()) {
159 std::vector<uint32_t>::const_iterator pos;
160 std::vector<uint32_t>::const_iterator end = indexes.end();
162 for (pos = indexes.begin(); pos != end; ++pos) {
164 if (idx < num_symbols) {
166 m_symbols[idx].Dump(s, target, idx);
173 void Symtab::DumpSymbolHeader(Stream *s) {
174 s->Indent(" Debug symbol\n");
175 s->Indent(" |Synthetic symbol\n");
176 s->Indent(" ||Externally Visible\n");
178 s->Indent("Index UserID DSX Type File Address/Value Load "
179 "Address Size Flags Name\n");
180 s->Indent("------- ------ --- --------------- ------------------ "
181 "------------------ ------------------ ---------- "
182 "----------------------------------\n");
185 static int CompareSymbolID(const void *key, const void *p) {
186 const user_id_t match_uid = *(const user_id_t *)key;
187 const user_id_t symbol_uid = ((const Symbol *)p)->GetID();
188 if (match_uid < symbol_uid)
190 if (match_uid > symbol_uid)
195 Symbol *Symtab::FindSymbolByID(lldb::user_id_t symbol_uid) const {
196 std::lock_guard<std::recursive_mutex> guard(m_mutex);
199 (Symbol *)::bsearch(&symbol_uid, &m_symbols[0], m_symbols.size(),
200 sizeof(m_symbols[0]), CompareSymbolID);
204 Symbol *Symtab::SymbolAtIndex(size_t idx) {
205 // Clients should grab the mutex from this symbol table and lock it manually
206 // when calling this function to avoid performance issues.
207 if (idx < m_symbols.size())
208 return &m_symbols[idx];
212 const Symbol *Symtab::SymbolAtIndex(size_t idx) const {
213 // Clients should grab the mutex from this symbol table and lock it manually
214 // when calling this function to avoid performance issues.
215 if (idx < m_symbols.size())
216 return &m_symbols[idx];
220 //----------------------------------------------------------------------
222 //----------------------------------------------------------------------
223 static bool lldb_skip_name(llvm::StringRef mangled,
224 Mangled::ManglingScheme scheme) {
226 case Mangled::eManglingSchemeItanium: {
227 if (mangled.size() < 3 || !mangled.startswith("_Z"))
230 // Avoid the following types of symbols in the index.
231 switch (mangled[2]) {
232 case 'G': // guard variables
233 case 'T': // virtual tables, VTT structures, typeinfo structures + names
234 case 'Z': // named local entities (if we eventually handle
235 // eSymbolTypeData, we will want this back)
242 // Include this name in the index.
246 // No filters for this scheme yet. Include all names in indexing.
247 case Mangled::eManglingSchemeMSVC:
250 // Don't try and demangle things we can't categorize.
251 case Mangled::eManglingSchemeNone:
254 llvm_unreachable("unknown scheme!");
257 void Symtab::InitNameIndexes() {
258 // Protected function, no need to lock mutex...
259 if (!m_name_indexes_computed) {
260 m_name_indexes_computed = true;
261 static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
262 Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
263 // Create the name index vector to be able to quickly search by name
264 const size_t num_symbols = m_symbols.size();
266 m_name_to_index.Reserve(num_symbols);
268 // TODO: benchmark this to see if we save any memory. Otherwise we
269 // will always keep the memory reserved in the vector unless we pull some
270 // STL swap magic and then recopy...
271 uint32_t actual_count = 0;
272 for (const_iterator pos = m_symbols.begin(), end = m_symbols.end();
274 const Mangled &mangled = pos->GetMangled();
275 if (mangled.GetMangledName())
278 if (mangled.GetDemangledName())
282 m_name_to_index.Reserve(actual_count);
285 // The "const char *" in "class_contexts" and backlog::value_type::second
286 // must come from a ConstString::GetCString()
287 std::set<const char *> class_contexts;
288 std::vector<std::pair<NameToIndexMap::Entry, const char *>> backlog;
289 backlog.reserve(num_symbols / 2);
291 // Instantiation of the demangler is expensive, so better use a single one
292 // for all entries during batch processing.
293 RichManglingContext rmc;
294 NameToIndexMap::Entry entry;
296 for (entry.value = 0; entry.value < num_symbols; ++entry.value) {
297 Symbol *symbol = &m_symbols[entry.value];
299 // Don't let trampolines get into the lookup by name map If we ever need
300 // the trampoline symbols to be searchable by name we can remove this and
301 // then possibly add a new bool to any of the Symtab functions that
302 // lookup symbols by name to indicate if they want trampolines.
303 if (symbol->IsTrampoline())
306 // If the symbol's name string matched a Mangled::ManglingScheme, it is
307 // stored in the mangled field.
308 Mangled &mangled = symbol->GetMangled();
309 entry.cstring = mangled.GetMangledName();
311 m_name_to_index.Append(entry);
313 if (symbol->ContainsLinkerAnnotations()) {
314 // If the symbol has linker annotations, also add the version without
316 entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations(
317 entry.cstring.GetStringRef()));
318 m_name_to_index.Append(entry);
321 const SymbolType type = symbol->GetType();
322 if (type == eSymbolTypeCode || type == eSymbolTypeResolver) {
323 if (mangled.DemangleWithRichManglingInfo(rmc, lldb_skip_name))
324 RegisterMangledNameEntry(entry, class_contexts, backlog, rmc);
328 // Symbol name strings that didn't match a Mangled::ManglingScheme, are
329 // stored in the demangled field.
330 entry.cstring = mangled.GetDemangledName(symbol->GetLanguage());
332 m_name_to_index.Append(entry);
334 if (symbol->ContainsLinkerAnnotations()) {
335 // If the symbol has linker annotations, also add the version without
337 entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations(
338 entry.cstring.GetStringRef()));
339 m_name_to_index.Append(entry);
343 // If the demangled name turns out to be an ObjC name, and is a category
344 // name, add the version without categories to the index too.
345 ObjCLanguage::MethodName objc_method(entry.cstring.GetStringRef(), true);
346 if (objc_method.IsValid(true)) {
347 entry.cstring = objc_method.GetSelector();
348 m_selector_to_index.Append(entry);
350 ConstString objc_method_no_category(
351 objc_method.GetFullNameWithoutCategory(true));
352 if (objc_method_no_category) {
353 entry.cstring = objc_method_no_category;
354 m_name_to_index.Append(entry);
359 for (const auto &record : backlog) {
360 RegisterBacklogEntry(record.first, record.second, class_contexts);
363 m_name_to_index.Sort();
364 m_name_to_index.SizeToFit();
365 m_selector_to_index.Sort();
366 m_selector_to_index.SizeToFit();
367 m_basename_to_index.Sort();
368 m_basename_to_index.SizeToFit();
369 m_method_to_index.Sort();
370 m_method_to_index.SizeToFit();
374 void Symtab::RegisterMangledNameEntry(
375 NameToIndexMap::Entry &entry, std::set<const char *> &class_contexts,
376 std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog,
377 RichManglingContext &rmc) {
378 // Only register functions that have a base name.
379 rmc.ParseFunctionBaseName();
380 llvm::StringRef base_name = rmc.GetBufferRef();
381 if (base_name.empty())
384 // The base name will be our entry's name.
385 entry.cstring = ConstString(base_name);
387 rmc.ParseFunctionDeclContextName();
388 llvm::StringRef decl_context = rmc.GetBufferRef();
390 // Register functions with no context.
391 if (decl_context.empty()) {
392 // This has to be a basename
393 m_basename_to_index.Append(entry);
394 // If there is no context (no namespaces or class scopes that come before
395 // the function name) then this also could be a fullname.
396 m_name_to_index.Append(entry);
400 // Make sure we have a pool-string pointer and see if we already know the
402 const char *decl_context_ccstr = ConstString(decl_context).GetCString();
403 auto it = class_contexts.find(decl_context_ccstr);
405 // Register constructors and destructors. They are methods and create
406 // declaration contexts.
407 if (rmc.IsCtorOrDtor()) {
408 m_method_to_index.Append(entry);
409 if (it == class_contexts.end())
410 class_contexts.insert(it, decl_context_ccstr);
414 // Register regular methods with a known declaration context.
415 if (it != class_contexts.end()) {
416 m_method_to_index.Append(entry);
420 // Regular methods in unknown declaration contexts are put to the backlog. We
421 // will revisit them once we processed all remaining symbols.
422 backlog.push_back(std::make_pair(entry, decl_context_ccstr));
425 void Symtab::RegisterBacklogEntry(
426 const NameToIndexMap::Entry &entry, const char *decl_context,
427 const std::set<const char *> &class_contexts) {
428 auto it = class_contexts.find(decl_context);
429 if (it != class_contexts.end()) {
430 m_method_to_index.Append(entry);
432 // If we got here, we have something that had a context (was inside
433 // a namespace or class) yet we don't know the entry
434 m_method_to_index.Append(entry);
435 m_basename_to_index.Append(entry);
439 void Symtab::PreloadSymbols() {
440 std::lock_guard<std::recursive_mutex> guard(m_mutex);
444 void Symtab::AppendSymbolNamesToMap(const IndexCollection &indexes,
445 bool add_demangled, bool add_mangled,
446 NameToIndexMap &name_to_index_map) const {
447 if (add_demangled || add_mangled) {
448 static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
449 Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
450 std::lock_guard<std::recursive_mutex> guard(m_mutex);
452 // Create the name index vector to be able to quickly search by name
453 NameToIndexMap::Entry entry;
454 const size_t num_indexes = indexes.size();
455 for (size_t i = 0; i < num_indexes; ++i) {
456 entry.value = indexes[i];
457 assert(i < m_symbols.size());
458 const Symbol *symbol = &m_symbols[entry.value];
460 const Mangled &mangled = symbol->GetMangled();
462 entry.cstring = mangled.GetDemangledName(symbol->GetLanguage());
464 name_to_index_map.Append(entry);
468 entry.cstring = mangled.GetMangledName();
470 name_to_index_map.Append(entry);
476 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
477 std::vector<uint32_t> &indexes,
479 uint32_t end_index) const {
480 std::lock_guard<std::recursive_mutex> guard(m_mutex);
482 uint32_t prev_size = indexes.size();
484 const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
486 for (uint32_t i = start_idx; i < count; ++i) {
487 if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type)
488 indexes.push_back(i);
491 return indexes.size() - prev_size;
494 uint32_t Symtab::AppendSymbolIndexesWithTypeAndFlagsValue(
495 SymbolType symbol_type, uint32_t flags_value,
496 std::vector<uint32_t> &indexes, uint32_t start_idx,
497 uint32_t end_index) const {
498 std::lock_guard<std::recursive_mutex> guard(m_mutex);
500 uint32_t prev_size = indexes.size();
502 const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
504 for (uint32_t i = start_idx; i < count; ++i) {
505 if ((symbol_type == eSymbolTypeAny ||
506 m_symbols[i].GetType() == symbol_type) &&
507 m_symbols[i].GetFlags() == flags_value)
508 indexes.push_back(i);
511 return indexes.size() - prev_size;
514 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
515 Debug symbol_debug_type,
516 Visibility symbol_visibility,
517 std::vector<uint32_t> &indexes,
519 uint32_t end_index) const {
520 std::lock_guard<std::recursive_mutex> guard(m_mutex);
522 uint32_t prev_size = indexes.size();
524 const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
526 for (uint32_t i = start_idx; i < count; ++i) {
527 if (symbol_type == eSymbolTypeAny ||
528 m_symbols[i].GetType() == symbol_type) {
529 if (CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility))
530 indexes.push_back(i);
534 return indexes.size() - prev_size;
537 uint32_t Symtab::GetIndexForSymbol(const Symbol *symbol) const {
538 if (!m_symbols.empty()) {
539 const Symbol *first_symbol = &m_symbols[0];
540 if (symbol >= first_symbol && symbol < first_symbol + m_symbols.size())
541 return symbol - first_symbol;
546 struct SymbolSortInfo {
547 const bool sort_by_load_addr;
548 const Symbol *symbols;
552 struct SymbolIndexComparator {
553 const std::vector<Symbol> &symbols;
554 std::vector<lldb::addr_t> &addr_cache;
556 // Getting from the symbol to the Address to the File Address involves some
557 // work. Since there are potentially many symbols here, and we're using this
558 // for sorting so we're going to be computing the address many times, cache
559 // that in addr_cache. The array passed in has to be the same size as the
560 // symbols array passed into the member variable symbols, and should be
561 // initialized with LLDB_INVALID_ADDRESS.
562 // NOTE: You have to make addr_cache externally and pass it in because
564 // makes copies of the comparator it is initially passed in, and you end up
565 // spending huge amounts of time copying this array...
567 SymbolIndexComparator(const std::vector<Symbol> &s,
568 std::vector<lldb::addr_t> &a)
569 : symbols(s), addr_cache(a) {
570 assert(symbols.size() == addr_cache.size());
572 bool operator()(uint32_t index_a, uint32_t index_b) {
573 addr_t value_a = addr_cache[index_a];
574 if (value_a == LLDB_INVALID_ADDRESS) {
575 value_a = symbols[index_a].GetAddressRef().GetFileAddress();
576 addr_cache[index_a] = value_a;
579 addr_t value_b = addr_cache[index_b];
580 if (value_b == LLDB_INVALID_ADDRESS) {
581 value_b = symbols[index_b].GetAddressRef().GetFileAddress();
582 addr_cache[index_b] = value_b;
585 if (value_a == value_b) {
586 // The if the values are equal, use the original symbol user ID
587 lldb::user_id_t uid_a = symbols[index_a].GetID();
588 lldb::user_id_t uid_b = symbols[index_b].GetID();
594 } else if (value_a < value_b)
602 void Symtab::SortSymbolIndexesByValue(std::vector<uint32_t> &indexes,
603 bool remove_duplicates) const {
604 std::lock_guard<std::recursive_mutex> guard(m_mutex);
606 static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
607 Timer scoped_timer(func_cat, LLVM_PRETTY_FUNCTION);
608 // No need to sort if we have zero or one items...
609 if (indexes.size() <= 1)
612 // Sort the indexes in place using std::stable_sort.
613 // NOTE: The use of std::stable_sort instead of llvm::sort here is strictly
614 // for performance, not correctness. The indexes vector tends to be "close"
615 // to sorted, which the stable sort handles better.
617 std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS);
619 SymbolIndexComparator comparator(m_symbols, addr_cache);
620 std::stable_sort(indexes.begin(), indexes.end(), comparator);
622 // Remove any duplicates if requested
623 if (remove_duplicates) {
624 auto last = std::unique(indexes.begin(), indexes.end());
625 indexes.erase(last, indexes.end());
629 uint32_t Symtab::AppendSymbolIndexesWithName(const ConstString &symbol_name,
630 std::vector<uint32_t> &indexes) {
631 std::lock_guard<std::recursive_mutex> guard(m_mutex);
633 static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
634 Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
636 if (!m_name_indexes_computed)
639 return m_name_to_index.GetValues(symbol_name, indexes);
644 uint32_t Symtab::AppendSymbolIndexesWithName(const ConstString &symbol_name,
645 Debug symbol_debug_type,
646 Visibility symbol_visibility,
647 std::vector<uint32_t> &indexes) {
648 std::lock_guard<std::recursive_mutex> guard(m_mutex);
650 static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
651 Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
653 const size_t old_size = indexes.size();
654 if (!m_name_indexes_computed)
657 std::vector<uint32_t> all_name_indexes;
658 const size_t name_match_count =
659 m_name_to_index.GetValues(symbol_name, all_name_indexes);
660 for (size_t i = 0; i < name_match_count; ++i) {
661 if (CheckSymbolAtIndex(all_name_indexes[i], symbol_debug_type,
663 indexes.push_back(all_name_indexes[i]);
665 return indexes.size() - old_size;
671 Symtab::AppendSymbolIndexesWithNameAndType(const ConstString &symbol_name,
672 SymbolType symbol_type,
673 std::vector<uint32_t> &indexes) {
674 std::lock_guard<std::recursive_mutex> guard(m_mutex);
676 if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0) {
677 std::vector<uint32_t>::iterator pos = indexes.begin();
678 while (pos != indexes.end()) {
679 if (symbol_type == eSymbolTypeAny ||
680 m_symbols[*pos].GetType() == symbol_type)
683 pos = indexes.erase(pos);
686 return indexes.size();
689 uint32_t Symtab::AppendSymbolIndexesWithNameAndType(
690 const ConstString &symbol_name, SymbolType symbol_type,
691 Debug symbol_debug_type, Visibility symbol_visibility,
692 std::vector<uint32_t> &indexes) {
693 std::lock_guard<std::recursive_mutex> guard(m_mutex);
695 if (AppendSymbolIndexesWithName(symbol_name, symbol_debug_type,
696 symbol_visibility, indexes) > 0) {
697 std::vector<uint32_t>::iterator pos = indexes.begin();
698 while (pos != indexes.end()) {
699 if (symbol_type == eSymbolTypeAny ||
700 m_symbols[*pos].GetType() == symbol_type)
703 pos = indexes.erase(pos);
706 return indexes.size();
709 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
710 const RegularExpression ®exp, SymbolType symbol_type,
711 std::vector<uint32_t> &indexes) {
712 std::lock_guard<std::recursive_mutex> guard(m_mutex);
714 uint32_t prev_size = indexes.size();
715 uint32_t sym_end = m_symbols.size();
717 for (uint32_t i = 0; i < sym_end; i++) {
718 if (symbol_type == eSymbolTypeAny ||
719 m_symbols[i].GetType() == symbol_type) {
720 const char *name = m_symbols[i].GetName().AsCString();
722 if (regexp.Execute(name))
723 indexes.push_back(i);
727 return indexes.size() - prev_size;
730 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
731 const RegularExpression ®exp, SymbolType symbol_type,
732 Debug symbol_debug_type, Visibility symbol_visibility,
733 std::vector<uint32_t> &indexes) {
734 std::lock_guard<std::recursive_mutex> guard(m_mutex);
736 uint32_t prev_size = indexes.size();
737 uint32_t sym_end = m_symbols.size();
739 for (uint32_t i = 0; i < sym_end; i++) {
740 if (symbol_type == eSymbolTypeAny ||
741 m_symbols[i].GetType() == symbol_type) {
742 if (!CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility))
745 const char *name = m_symbols[i].GetName().AsCString();
747 if (regexp.Execute(name))
748 indexes.push_back(i);
752 return indexes.size() - prev_size;
755 Symbol *Symtab::FindSymbolWithType(SymbolType symbol_type,
756 Debug symbol_debug_type,
757 Visibility symbol_visibility,
758 uint32_t &start_idx) {
759 std::lock_guard<std::recursive_mutex> guard(m_mutex);
761 const size_t count = m_symbols.size();
762 for (size_t idx = start_idx; idx < count; ++idx) {
763 if (symbol_type == eSymbolTypeAny ||
764 m_symbols[idx].GetType() == symbol_type) {
765 if (CheckSymbolAtIndex(idx, symbol_debug_type, symbol_visibility)) {
767 return &m_symbols[idx];
775 Symtab::FindAllSymbolsWithNameAndType(const ConstString &name,
776 SymbolType symbol_type,
777 std::vector<uint32_t> &symbol_indexes) {
778 std::lock_guard<std::recursive_mutex> guard(m_mutex);
780 static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
781 Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
782 // Initialize all of the lookup by name indexes before converting NAME to a
783 // uniqued string NAME_STR below.
784 if (!m_name_indexes_computed)
788 // The string table did have a string that matched, but we need to check
789 // the symbols and match the symbol_type if any was given.
790 AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_indexes);
792 return symbol_indexes.size();
795 size_t Symtab::FindAllSymbolsWithNameAndType(
796 const ConstString &name, SymbolType symbol_type, Debug symbol_debug_type,
797 Visibility symbol_visibility, std::vector<uint32_t> &symbol_indexes) {
798 std::lock_guard<std::recursive_mutex> guard(m_mutex);
800 static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
801 Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
802 // Initialize all of the lookup by name indexes before converting NAME to a
803 // uniqued string NAME_STR below.
804 if (!m_name_indexes_computed)
808 // The string table did have a string that matched, but we need to check
809 // the symbols and match the symbol_type if any was given.
810 AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
811 symbol_visibility, symbol_indexes);
813 return symbol_indexes.size();
816 size_t Symtab::FindAllSymbolsMatchingRexExAndType(
817 const RegularExpression ®ex, SymbolType symbol_type,
818 Debug symbol_debug_type, Visibility symbol_visibility,
819 std::vector<uint32_t> &symbol_indexes) {
820 std::lock_guard<std::recursive_mutex> guard(m_mutex);
822 AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_debug_type,
823 symbol_visibility, symbol_indexes);
824 return symbol_indexes.size();
827 Symbol *Symtab::FindFirstSymbolWithNameAndType(const ConstString &name,
828 SymbolType symbol_type,
829 Debug symbol_debug_type,
830 Visibility symbol_visibility) {
831 std::lock_guard<std::recursive_mutex> guard(m_mutex);
833 static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
834 Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
835 if (!m_name_indexes_computed)
839 std::vector<uint32_t> matching_indexes;
840 // The string table did have a string that matched, but we need to check
841 // the symbols and match the symbol_type if any was given.
842 if (AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
845 std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end();
846 for (pos = matching_indexes.begin(); pos != end; ++pos) {
847 Symbol *symbol = SymbolAtIndex(*pos);
849 if (symbol->Compare(name, symbol_type))
858 const Symtab *symtab;
859 const addr_t file_addr;
860 Symbol *match_symbol;
861 const uint32_t *match_index_ptr;
865 // Add all the section file start address & size to the RangeVector, recusively
866 // adding any children sections.
867 static void AddSectionsToRangeMap(SectionList *sectlist,
868 RangeVector<addr_t, addr_t> §ion_ranges) {
869 const int num_sections = sectlist->GetNumSections(0);
870 for (int i = 0; i < num_sections; i++) {
871 SectionSP sect_sp = sectlist->GetSectionAtIndex(i);
873 SectionList &child_sectlist = sect_sp->GetChildren();
875 // If this section has children, add the children to the RangeVector.
876 // Else add this section to the RangeVector.
877 if (child_sectlist.GetNumSections(0) > 0) {
878 AddSectionsToRangeMap(&child_sectlist, section_ranges);
880 size_t size = sect_sp->GetByteSize();
882 addr_t base_addr = sect_sp->GetFileAddress();
883 RangeVector<addr_t, addr_t>::Entry entry;
884 entry.SetRangeBase(base_addr);
885 entry.SetByteSize(size);
886 section_ranges.Append(entry);
893 void Symtab::InitAddressIndexes() {
894 // Protected function, no need to lock mutex...
895 if (!m_file_addr_to_index_computed && !m_symbols.empty()) {
896 m_file_addr_to_index_computed = true;
898 FileRangeToIndexMap::Entry entry;
899 const_iterator begin = m_symbols.begin();
900 const_iterator end = m_symbols.end();
901 for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
902 if (pos->ValueIsAddress()) {
903 entry.SetRangeBase(pos->GetAddressRef().GetFileAddress());
904 entry.SetByteSize(pos->GetByteSize());
905 entry.data = std::distance(begin, pos);
906 m_file_addr_to_index.Append(entry);
909 const size_t num_entries = m_file_addr_to_index.GetSize();
910 if (num_entries > 0) {
911 m_file_addr_to_index.Sort();
913 // Create a RangeVector with the start & size of all the sections for
914 // this objfile. We'll need to check this for any FileRangeToIndexMap
915 // entries with an uninitialized size, which could potentially be a large
916 // number so reconstituting the weak pointer is busywork when it is
917 // invariant information.
918 SectionList *sectlist = m_objfile->GetSectionList();
919 RangeVector<addr_t, addr_t> section_ranges;
921 AddSectionsToRangeMap(sectlist, section_ranges);
922 section_ranges.Sort();
925 // Iterate through the FileRangeToIndexMap and fill in the size for any
926 // entries that didn't already have a size from the Symbol (e.g. if we
927 // have a plain linker symbol with an address only, instead of debug info
928 // where we get an address and a size and a type, etc.)
929 for (size_t i = 0; i < num_entries; i++) {
930 FileRangeToIndexMap::Entry *entry =
931 m_file_addr_to_index.GetMutableEntryAtIndex(i);
932 if (entry->GetByteSize() == 0) {
933 addr_t curr_base_addr = entry->GetRangeBase();
934 const RangeVector<addr_t, addr_t>::Entry *containing_section =
935 section_ranges.FindEntryThatContains(curr_base_addr);
937 // Use the end of the section as the default max size of the symbol
939 if (containing_section) {
941 containing_section->GetByteSize() -
942 (entry->GetRangeBase() - containing_section->GetRangeBase());
945 for (size_t j = i; j < num_entries; j++) {
946 FileRangeToIndexMap::Entry *next_entry =
947 m_file_addr_to_index.GetMutableEntryAtIndex(j);
948 addr_t next_base_addr = next_entry->GetRangeBase();
949 if (next_base_addr > curr_base_addr) {
950 addr_t size_to_next_symbol = next_base_addr - curr_base_addr;
952 // Take the difference between this symbol and the next one as
953 // its size, if it is less than the size of the section.
954 if (sym_size == 0 || size_to_next_symbol < sym_size) {
955 sym_size = size_to_next_symbol;
962 entry->SetByteSize(sym_size);
963 Symbol &symbol = m_symbols[entry->data];
964 symbol.SetByteSize(sym_size);
965 symbol.SetSizeIsSynthesized(true);
970 // Sort again in case the range size changes the ordering
971 m_file_addr_to_index.Sort();
976 void Symtab::CalculateSymbolSizes() {
977 std::lock_guard<std::recursive_mutex> guard(m_mutex);
978 // Size computation happens inside InitAddressIndexes.
979 InitAddressIndexes();
982 Symbol *Symtab::FindSymbolAtFileAddress(addr_t file_addr) {
983 std::lock_guard<std::recursive_mutex> guard(m_mutex);
984 if (!m_file_addr_to_index_computed)
985 InitAddressIndexes();
987 const FileRangeToIndexMap::Entry *entry =
988 m_file_addr_to_index.FindEntryStartsAt(file_addr);
990 Symbol *symbol = SymbolAtIndex(entry->data);
991 if (symbol->GetFileAddress() == file_addr)
997 Symbol *Symtab::FindSymbolContainingFileAddress(addr_t file_addr) {
998 std::lock_guard<std::recursive_mutex> guard(m_mutex);
1000 if (!m_file_addr_to_index_computed)
1001 InitAddressIndexes();
1003 const FileRangeToIndexMap::Entry *entry =
1004 m_file_addr_to_index.FindEntryThatContains(file_addr);
1006 Symbol *symbol = SymbolAtIndex(entry->data);
1007 if (symbol->ContainsFileAddress(file_addr))
1013 void Symtab::ForEachSymbolContainingFileAddress(
1014 addr_t file_addr, std::function<bool(Symbol *)> const &callback) {
1015 std::lock_guard<std::recursive_mutex> guard(m_mutex);
1017 if (!m_file_addr_to_index_computed)
1018 InitAddressIndexes();
1020 std::vector<uint32_t> all_addr_indexes;
1022 // Get all symbols with file_addr
1023 const size_t addr_match_count =
1024 m_file_addr_to_index.FindEntryIndexesThatContain(file_addr,
1027 for (size_t i = 0; i < addr_match_count; ++i) {
1028 Symbol *symbol = SymbolAtIndex(all_addr_indexes[i]);
1029 if (symbol->ContainsFileAddress(file_addr)) {
1030 if (!callback(symbol))
1036 void Symtab::SymbolIndicesToSymbolContextList(
1037 std::vector<uint32_t> &symbol_indexes, SymbolContextList &sc_list) {
1038 // No need to protect this call using m_mutex all other method calls are
1039 // already thread safe.
1041 const bool merge_symbol_into_function = true;
1042 size_t num_indices = symbol_indexes.size();
1043 if (num_indices > 0) {
1045 sc.module_sp = m_objfile->GetModule();
1046 for (size_t i = 0; i < num_indices; i++) {
1047 sc.symbol = SymbolAtIndex(symbol_indexes[i]);
1049 sc_list.AppendIfUnique(sc, merge_symbol_into_function);
1054 size_t Symtab::FindFunctionSymbols(const ConstString &name,
1055 uint32_t name_type_mask,
1056 SymbolContextList &sc_list) {
1058 std::vector<uint32_t> symbol_indexes;
1060 // eFunctionNameTypeAuto should be pre-resolved by a call to
1061 // Module::LookupInfo::LookupInfo()
1062 assert((name_type_mask & eFunctionNameTypeAuto) == 0);
1064 if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) {
1065 std::vector<uint32_t> temp_symbol_indexes;
1066 FindAllSymbolsWithNameAndType(name, eSymbolTypeAny, temp_symbol_indexes);
1068 unsigned temp_symbol_indexes_size = temp_symbol_indexes.size();
1069 if (temp_symbol_indexes_size > 0) {
1070 std::lock_guard<std::recursive_mutex> guard(m_mutex);
1071 for (unsigned i = 0; i < temp_symbol_indexes_size; i++) {
1072 SymbolContext sym_ctx;
1073 sym_ctx.symbol = SymbolAtIndex(temp_symbol_indexes[i]);
1074 if (sym_ctx.symbol) {
1075 switch (sym_ctx.symbol->GetType()) {
1076 case eSymbolTypeCode:
1077 case eSymbolTypeResolver:
1078 case eSymbolTypeReExported:
1079 symbol_indexes.push_back(temp_symbol_indexes[i]);
1089 if (name_type_mask & eFunctionNameTypeBase) {
1090 // From mangled names we can't tell what is a basename and what is a method
1091 // name, so we just treat them the same
1092 if (!m_name_indexes_computed)
1095 if (!m_basename_to_index.IsEmpty()) {
1096 const UniqueCStringMap<uint32_t>::Entry *match;
1097 for (match = m_basename_to_index.FindFirstValueForName(name);
1099 match = m_basename_to_index.FindNextValueForName(match)) {
1100 symbol_indexes.push_back(match->value);
1105 if (name_type_mask & eFunctionNameTypeMethod) {
1106 if (!m_name_indexes_computed)
1109 if (!m_method_to_index.IsEmpty()) {
1110 const UniqueCStringMap<uint32_t>::Entry *match;
1111 for (match = m_method_to_index.FindFirstValueForName(name);
1113 match = m_method_to_index.FindNextValueForName(match)) {
1114 symbol_indexes.push_back(match->value);
1119 if (name_type_mask & eFunctionNameTypeSelector) {
1120 if (!m_name_indexes_computed)
1123 if (!m_selector_to_index.IsEmpty()) {
1124 const UniqueCStringMap<uint32_t>::Entry *match;
1125 for (match = m_selector_to_index.FindFirstValueForName(name);
1127 match = m_selector_to_index.FindNextValueForName(match)) {
1128 symbol_indexes.push_back(match->value);
1133 if (!symbol_indexes.empty()) {
1134 llvm::sort(symbol_indexes.begin(), symbol_indexes.end());
1135 symbol_indexes.erase(
1136 std::unique(symbol_indexes.begin(), symbol_indexes.end()),
1137 symbol_indexes.end());
1138 count = symbol_indexes.size();
1139 SymbolIndicesToSymbolContextList(symbol_indexes, sc_list);
1145 const Symbol *Symtab::GetParent(Symbol *child_symbol) const {
1146 uint32_t child_idx = GetIndexForSymbol(child_symbol);
1147 if (child_idx != UINT32_MAX && child_idx > 0) {
1148 for (uint32_t idx = child_idx - 1; idx != UINT32_MAX; --idx) {
1149 const Symbol *symbol = SymbolAtIndex(idx);
1150 const uint32_t sibling_idx = symbol->GetSiblingIndex();
1151 if (sibling_idx != UINT32_MAX && sibling_idx > child_idx)