contrib/llvm-project/lldb/source/Symbol/Symtab.cpp

   1 //===-- Symtab.cpp ----------------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include <map>
  10 #include <set>
  11
  12 #include "Plugins/Language/ObjC/ObjCLanguage.h"
  13
  14 #include "lldb/Core/Module.h"
  15 #include "lldb/Core/RichManglingContext.h"
  16 #include "lldb/Core/STLUtils.h"
  17 #include "lldb/Core/Section.h"
  18 #include "lldb/Symbol/ObjectFile.h"
  19 #include "lldb/Symbol/Symbol.h"
  20 #include "lldb/Symbol/SymbolContext.h"
  21 #include "lldb/Symbol/Symtab.h"
  22 #include "lldb/Utility/RegularExpression.h"
  23 #include "lldb/Utility/Stream.h"
  24 #include "lldb/Utility/Timer.h"
  25
  26 #include "llvm/ADT/StringRef.h"
  27
  28 using namespace lldb;
  29 using namespace lldb_private;
  30
  31 Symtab::Symtab(ObjectFile *objfile)
  32     : m_objfile(objfile), m_symbols(), m_file_addr_to_index(),
  33       m_name_to_index(), m_mutex(), m_file_addr_to_index_computed(false),
  34       m_name_indexes_computed(false) {}
  35
  36 Symtab::~Symtab() {}
  37
  38 void Symtab::Reserve(size_t count) {
  39   // Clients should grab the mutex from this symbol table and lock it manually
  40   // when calling this function to avoid performance issues.
  41   m_symbols.reserve(count);
  42 }
  43
  44 Symbol *Symtab::Resize(size_t count) {
  45   // Clients should grab the mutex from this symbol table and lock it manually
  46   // when calling this function to avoid performance issues.
  47   m_symbols.resize(count);
  48   return m_symbols.empty() ? nullptr : &m_symbols[0];
  49 }
  50
  51 uint32_t Symtab::AddSymbol(const Symbol &symbol) {
  52   // Clients should grab the mutex from this symbol table and lock it manually
  53   // when calling this function to avoid performance issues.
  54   uint32_t symbol_idx = m_symbols.size();
  55   m_name_to_index.Clear();
  56   m_file_addr_to_index.Clear();
  57   m_symbols.push_back(symbol);
  58   m_file_addr_to_index_computed = false;
  59   m_name_indexes_computed = false;
  60   return symbol_idx;
  61 }
  62
  63 size_t Symtab::GetNumSymbols() const {
  64   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  65   return m_symbols.size();
  66 }
  67
  68 void Symtab::SectionFileAddressesChanged() {
  69   m_name_to_index.Clear();
  70   m_file_addr_to_index_computed = false;
  71 }
  72
  73 void Symtab::Dump(Stream *s, Target *target, SortOrder sort_order) {
  74   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  75
  76   //    s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
  77   s->Indent();
  78   const FileSpec &file_spec = m_objfile->GetFileSpec();
  79   const char *object_name = nullptr;
  80   if (m_objfile->GetModule())
  81     object_name = m_objfile->GetModule()->GetObjectName().GetCString();
  82
  83   if (file_spec)
  84     s->Printf("Symtab, file = %s%s%s%s, num_symbols = %" PRIu64,
  85               file_spec.GetPath().c_str(), object_name ? "(" : "",
  86               object_name ? object_name : "", object_name ? ")" : "",
  87               (uint64_t)m_symbols.size());
  88   else
  89     s->Printf("Symtab, num_symbols = %" PRIu64 "", (uint64_t)m_symbols.size());
  90
  91   if (!m_symbols.empty()) {
  92     switch (sort_order) {
  93     case eSortOrderNone: {
  94       s->PutCString(":\n");
  95       DumpSymbolHeader(s);
  96       const_iterator begin = m_symbols.begin();
  97       const_iterator end = m_symbols.end();
  98       for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
  99         s->Indent();
 100         pos->Dump(s, target, std::distance(begin, pos));
 101       }
 102     } break;
 103
 104     case eSortOrderByName: {
 105       // Although we maintain a lookup by exact name map, the table isn't
 106       // sorted by name. So we must make the ordered symbol list up ourselves.
 107       s->PutCString(" (sorted by name):\n");
 108       DumpSymbolHeader(s);
 109       typedef std::multimap<const char *, const Symbol *,
 110                             CStringCompareFunctionObject>
 111           CStringToSymbol;
 112       CStringToSymbol name_map;
 113       for (const_iterator pos = m_symbols.begin(), end = m_symbols.end();
 114            pos != end; ++pos) {
 115         const char *name = pos->GetName().AsCString();
 116         if (name && name[0])
 117           name_map.insert(std::make_pair(name, &(*pos)));
 118       }
 119
 120       for (CStringToSymbol::const_iterator pos = name_map.begin(),
 121                                            end = name_map.end();
 122            pos != end; ++pos) {
 123         s->Indent();
 124         pos->second->Dump(s, target, pos->second - &m_symbols[0]);
 125       }
 126     } break;
 127
 128     case eSortOrderByAddress:
 129       s->PutCString(" (sorted by address):\n");
 130       DumpSymbolHeader(s);
 131       if (!m_file_addr_to_index_computed)
 132         InitAddressIndexes();
 133       const size_t num_entries = m_file_addr_to_index.GetSize();
 134       for (size_t i = 0; i < num_entries; ++i) {
 135         s->Indent();
 136         const uint32_t symbol_idx = m_file_addr_to_index.GetEntryRef(i).data;
 137         m_symbols[symbol_idx].Dump(s, target, symbol_idx);
 138       }
 139       break;
 140     }
 141   } else {
 142     s->PutCString("\n");
 143   }
 144 }
 145
 146 void Symtab::Dump(Stream *s, Target *target,
 147                   std::vector<uint32_t> &indexes) const {
 148   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 149
 150   const size_t num_symbols = GetNumSymbols();
 151   // s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
 152   s->Indent();
 153   s->Printf("Symtab %" PRIu64 " symbol indexes (%" PRIu64 " symbols total):\n",
 154             (uint64_t)indexes.size(), (uint64_t)m_symbols.size());
 155   s->IndentMore();
 156
 157   if (!indexes.empty()) {
 158     std::vector<uint32_t>::const_iterator pos;
 159     std::vector<uint32_t>::const_iterator end = indexes.end();
 160     DumpSymbolHeader(s);
 161     for (pos = indexes.begin(); pos != end; ++pos) {
 162       size_t idx = *pos;
 163       if (idx < num_symbols) {
 164         s->Indent();
 165         m_symbols[idx].Dump(s, target, idx);
 166       }
 167     }
 168   }
 169   s->IndentLess();
 170 }
 171
 172 void Symtab::DumpSymbolHeader(Stream *s) {
 173   s->Indent("               Debug symbol\n");
 174   s->Indent("               |Synthetic symbol\n");
 175   s->Indent("               ||Externally Visible\n");
 176   s->Indent("               |||\n");
 177   s->Indent("Index   UserID DSX Type            File Address/Value Load "
 178             "Address       Size               Flags      Name\n");
 179   s->Indent("------- ------ --- --------------- ------------------ "
 180             "------------------ ------------------ ---------- "
 181             "----------------------------------\n");
 182 }
 183
 184 static int CompareSymbolID(const void *key, const void *p) {
 185   const user_id_t match_uid = *(const user_id_t *)key;
 186   const user_id_t symbol_uid = ((const Symbol *)p)->GetID();
 187   if (match_uid < symbol_uid)
 188     return -1;
 189   if (match_uid > symbol_uid)
 190     return 1;
 191   return 0;
 192 }
 193
 194 Symbol *Symtab::FindSymbolByID(lldb::user_id_t symbol_uid) const {
 195   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 196
 197   Symbol *symbol =
 198       (Symbol *)::bsearch(&symbol_uid, &m_symbols[0], m_symbols.size(),
 199                           sizeof(m_symbols[0]), CompareSymbolID);
 200   return symbol;
 201 }
 202
 203 Symbol *Symtab::SymbolAtIndex(size_t idx) {
 204   // Clients should grab the mutex from this symbol table and lock it manually
 205   // when calling this function to avoid performance issues.
 206   if (idx < m_symbols.size())
 207     return &m_symbols[idx];
 208   return nullptr;
 209 }
 210
 211 const Symbol *Symtab::SymbolAtIndex(size_t idx) const {
 212   // Clients should grab the mutex from this symbol table and lock it manually
 213   // when calling this function to avoid performance issues.
 214   if (idx < m_symbols.size())
 215     return &m_symbols[idx];
 216   return nullptr;
 217 }
 218
 219 static bool lldb_skip_name(llvm::StringRef mangled,
 220                            Mangled::ManglingScheme scheme) {
 221   switch (scheme) {
 222   case Mangled::eManglingSchemeItanium: {
 223     if (mangled.size() < 3 || !mangled.startswith("_Z"))
 224       return true;
 225
 226     // Avoid the following types of symbols in the index.
 227     switch (mangled[2]) {
 228     case 'G': // guard variables
 229     case 'T': // virtual tables, VTT structures, typeinfo structures + names
 230     case 'Z': // named local entities (if we eventually handle
 231               // eSymbolTypeData, we will want this back)
 232       return true;
 233
 234     default:
 235       break;
 236     }
 237
 238     // Include this name in the index.
 239     return false;
 240   }
 241
 242   // No filters for this scheme yet. Include all names in indexing.
 243   case Mangled::eManglingSchemeMSVC:
 244     return false;
 245
 246   // Don't try and demangle things we can't categorize.
 247   case Mangled::eManglingSchemeNone:
 248     return true;
 249   }
 250   llvm_unreachable("unknown scheme!");
 251 }
 252
 253 void Symtab::InitNameIndexes() {
 254   // Protected function, no need to lock mutex...
 255   if (!m_name_indexes_computed) {
 256     m_name_indexes_computed = true;
 257     static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 258     Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 259     // Create the name index vector to be able to quickly search by name
 260     const size_t num_symbols = m_symbols.size();
 261     m_name_to_index.Reserve(num_symbols);
 262
 263     // The "const char *" in "class_contexts" and backlog::value_type::second
 264     // must come from a ConstString::GetCString()
 265     std::set<const char *> class_contexts;
 266     std::vector<std::pair<NameToIndexMap::Entry, const char *>> backlog;
 267     backlog.reserve(num_symbols / 2);
 268
 269     // Instantiation of the demangler is expensive, so better use a single one
 270     // for all entries during batch processing.
 271     RichManglingContext rmc;
 272     for (uint32_t value = 0; value < num_symbols; ++value) {
 273       Symbol *symbol = &m_symbols[value];
 274
 275       // Don't let trampolines get into the lookup by name map If we ever need
 276       // the trampoline symbols to be searchable by name we can remove this and
 277       // then possibly add a new bool to any of the Symtab functions that
 278       // lookup symbols by name to indicate if they want trampolines.
 279       if (symbol->IsTrampoline())
 280         continue;
 281
 282       // If the symbol's name string matched a Mangled::ManglingScheme, it is
 283       // stored in the mangled field.
 284       Mangled &mangled = symbol->GetMangled();
 285       if (ConstString name = mangled.GetMangledName()) {
 286         m_name_to_index.Append(name, value);
 287
 288         if (symbol->ContainsLinkerAnnotations()) {
 289           // If the symbol has linker annotations, also add the version without
 290           // the annotations.
 291           ConstString stripped = ConstString(
 292               m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
 293           m_name_to_index.Append(stripped, value);
 294         }
 295
 296         const SymbolType type = symbol->GetType();
 297         if (type == eSymbolTypeCode || type == eSymbolTypeResolver) {
 298           if (mangled.DemangleWithRichManglingInfo(rmc, lldb_skip_name))
 299             RegisterMangledNameEntry(value, class_contexts, backlog, rmc);
 300         }
 301       }
 302
 303       // Symbol name strings that didn't match a Mangled::ManglingScheme, are
 304       // stored in the demangled field.
 305       if (ConstString name = mangled.GetDemangledName(symbol->GetLanguage())) {
 306         m_name_to_index.Append(name, value);
 307
 308         if (symbol->ContainsLinkerAnnotations()) {
 309           // If the symbol has linker annotations, also add the version without
 310           // the annotations.
 311           name = ConstString(
 312               m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
 313           m_name_to_index.Append(name, value);
 314         }
 315
 316         // If the demangled name turns out to be an ObjC name, and is a category
 317         // name, add the version without categories to the index too.
 318         ObjCLanguage::MethodName objc_method(name.GetStringRef(), true);
 319         if (objc_method.IsValid(true)) {
 320           m_selector_to_index.Append(objc_method.GetSelector(), value);
 321
 322           if (ConstString objc_method_no_category =
 323                   objc_method.GetFullNameWithoutCategory(true))
 324             m_name_to_index.Append(objc_method_no_category, value);
 325         }
 326       }
 327     }
 328
 329     for (const auto &record : backlog) {
 330       RegisterBacklogEntry(record.first, record.second, class_contexts);
 331     }
 332
 333     m_name_to_index.Sort();
 334     m_name_to_index.SizeToFit();
 335     m_selector_to_index.Sort();
 336     m_selector_to_index.SizeToFit();
 337     m_basename_to_index.Sort();
 338     m_basename_to_index.SizeToFit();
 339     m_method_to_index.Sort();
 340     m_method_to_index.SizeToFit();
 341   }
 342 }
 343
 344 void Symtab::RegisterMangledNameEntry(
 345     uint32_t value, std::set<const char *> &class_contexts,
 346     std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog,
 347     RichManglingContext &rmc) {
 348   // Only register functions that have a base name.
 349   rmc.ParseFunctionBaseName();
 350   llvm::StringRef base_name = rmc.GetBufferRef();
 351   if (base_name.empty())
 352     return;
 353
 354   // The base name will be our entry's name.
 355   NameToIndexMap::Entry entry(ConstString(base_name), value);
 356
 357   rmc.ParseFunctionDeclContextName();
 358   llvm::StringRef decl_context = rmc.GetBufferRef();
 359
 360   // Register functions with no context.
 361   if (decl_context.empty()) {
 362     // This has to be a basename
 363     m_basename_to_index.Append(entry);
 364     // If there is no context (no namespaces or class scopes that come before
 365     // the function name) then this also could be a fullname.
 366     m_name_to_index.Append(entry);
 367     return;
 368   }
 369
 370   // Make sure we have a pool-string pointer and see if we already know the
 371   // context name.
 372   const char *decl_context_ccstr = ConstString(decl_context).GetCString();
 373   auto it = class_contexts.find(decl_context_ccstr);
 374
 375   // Register constructors and destructors. They are methods and create
 376   // declaration contexts.
 377   if (rmc.IsCtorOrDtor()) {
 378     m_method_to_index.Append(entry);
 379     if (it == class_contexts.end())
 380       class_contexts.insert(it, decl_context_ccstr);
 381     return;
 382   }
 383
 384   // Register regular methods with a known declaration context.
 385   if (it != class_contexts.end()) {
 386     m_method_to_index.Append(entry);
 387     return;
 388   }
 389
 390   // Regular methods in unknown declaration contexts are put to the backlog. We
 391   // will revisit them once we processed all remaining symbols.
 392   backlog.push_back(std::make_pair(entry, decl_context_ccstr));
 393 }
 394
 395 void Symtab::RegisterBacklogEntry(
 396     const NameToIndexMap::Entry &entry, const char *decl_context,
 397     const std::set<const char *> &class_contexts) {
 398   auto it = class_contexts.find(decl_context);
 399   if (it != class_contexts.end()) {
 400     m_method_to_index.Append(entry);
 401   } else {
 402     // If we got here, we have something that had a context (was inside
 403     // a namespace or class) yet we don't know the entry
 404     m_method_to_index.Append(entry);
 405     m_basename_to_index.Append(entry);
 406   }
 407 }
 408
 409 void Symtab::PreloadSymbols() {
 410   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 411   InitNameIndexes();
 412 }
 413
 414 void Symtab::AppendSymbolNamesToMap(const IndexCollection &indexes,
 415                                     bool add_demangled, bool add_mangled,
 416                                     NameToIndexMap &name_to_index_map) const {
 417   if (add_demangled || add_mangled) {
 418     static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 419     Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 420     std::lock_guard<std::recursive_mutex> guard(m_mutex);
 421
 422     // Create the name index vector to be able to quickly search by name
 423     const size_t num_indexes = indexes.size();
 424     for (size_t i = 0; i < num_indexes; ++i) {
 425       uint32_t value = indexes[i];
 426       assert(i < m_symbols.size());
 427       const Symbol *symbol = &m_symbols[value];
 428
 429       const Mangled &mangled = symbol->GetMangled();
 430       if (add_demangled) {
 431         if (ConstString name = mangled.GetDemangledName(symbol->GetLanguage()))
 432           name_to_index_map.Append(name, value);
 433       }
 434
 435       if (add_mangled) {
 436         if (ConstString name = mangled.GetMangledName())
 437           name_to_index_map.Append(name, value);
 438       }
 439     }
 440   }
 441 }
 442
 443 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
 444                                              std::vector<uint32_t> &indexes,
 445                                              uint32_t start_idx,
 446                                              uint32_t end_index) const {
 447   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 448
 449   uint32_t prev_size = indexes.size();
 450
 451   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 452
 453   for (uint32_t i = start_idx; i < count; ++i) {
 454     if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type)
 455       indexes.push_back(i);
 456   }
 457
 458   return indexes.size() - prev_size;
 459 }
 460
 461 uint32_t Symtab::AppendSymbolIndexesWithTypeAndFlagsValue(
 462     SymbolType symbol_type, uint32_t flags_value,
 463     std::vector<uint32_t> &indexes, uint32_t start_idx,
 464     uint32_t end_index) const {
 465   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 466
 467   uint32_t prev_size = indexes.size();
 468
 469   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 470
 471   for (uint32_t i = start_idx; i < count; ++i) {
 472     if ((symbol_type == eSymbolTypeAny ||
 473          m_symbols[i].GetType() == symbol_type) &&
 474         m_symbols[i].GetFlags() == flags_value)
 475       indexes.push_back(i);
 476   }
 477
 478   return indexes.size() - prev_size;
 479 }
 480
 481 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
 482                                              Debug symbol_debug_type,
 483                                              Visibility symbol_visibility,
 484                                              std::vector<uint32_t> &indexes,
 485                                              uint32_t start_idx,
 486                                              uint32_t end_index) const {
 487   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 488
 489   uint32_t prev_size = indexes.size();
 490
 491   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 492
 493   for (uint32_t i = start_idx; i < count; ++i) {
 494     if (symbol_type == eSymbolTypeAny ||
 495         m_symbols[i].GetType() == symbol_type) {
 496       if (CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility))
 497         indexes.push_back(i);
 498     }
 499   }
 500
 501   return indexes.size() - prev_size;
 502 }
 503
 504 uint32_t Symtab::GetIndexForSymbol(const Symbol *symbol) const {
 505   if (!m_symbols.empty()) {
 506     const Symbol *first_symbol = &m_symbols[0];
 507     if (symbol >= first_symbol && symbol < first_symbol + m_symbols.size())
 508       return symbol - first_symbol;
 509   }
 510   return UINT32_MAX;
 511 }
 512
 513 struct SymbolSortInfo {
 514   const bool sort_by_load_addr;
 515   const Symbol *symbols;
 516 };
 517
 518 namespace {
 519 struct SymbolIndexComparator {
 520   const std::vector<Symbol> &symbols;
 521   std::vector<lldb::addr_t> &addr_cache;
 522
 523   // Getting from the symbol to the Address to the File Address involves some
 524   // work. Since there are potentially many symbols here, and we're using this
 525   // for sorting so we're going to be computing the address many times, cache
 526   // that in addr_cache. The array passed in has to be the same size as the
 527   // symbols array passed into the member variable symbols, and should be
 528   // initialized with LLDB_INVALID_ADDRESS.
 529   // NOTE: You have to make addr_cache externally and pass it in because
 530   // std::stable_sort
 531   // makes copies of the comparator it is initially passed in, and you end up
 532   // spending huge amounts of time copying this array...
 533
 534   SymbolIndexComparator(const std::vector<Symbol> &s,
 535                         std::vector<lldb::addr_t> &a)
 536       : symbols(s), addr_cache(a) {
 537     assert(symbols.size() == addr_cache.size());
 538   }
 539   bool operator()(uint32_t index_a, uint32_t index_b) {
 540     addr_t value_a = addr_cache[index_a];
 541     if (value_a == LLDB_INVALID_ADDRESS) {
 542       value_a = symbols[index_a].GetAddressRef().GetFileAddress();
 543       addr_cache[index_a] = value_a;
 544     }
 545
 546     addr_t value_b = addr_cache[index_b];
 547     if (value_b == LLDB_INVALID_ADDRESS) {
 548       value_b = symbols[index_b].GetAddressRef().GetFileAddress();
 549       addr_cache[index_b] = value_b;
 550     }
 551
 552     if (value_a == value_b) {
 553       // The if the values are equal, use the original symbol user ID
 554       lldb::user_id_t uid_a = symbols[index_a].GetID();
 555       lldb::user_id_t uid_b = symbols[index_b].GetID();
 556       if (uid_a < uid_b)
 557         return true;
 558       if (uid_a > uid_b)
 559         return false;
 560       return false;
 561     } else if (value_a < value_b)
 562       return true;
 563
 564     return false;
 565   }
 566 };
 567 }
 568
 569 void Symtab::SortSymbolIndexesByValue(std::vector<uint32_t> &indexes,
 570                                       bool remove_duplicates) const {
 571   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 572
 573   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 574   Timer scoped_timer(func_cat, LLVM_PRETTY_FUNCTION);
 575   // No need to sort if we have zero or one items...
 576   if (indexes.size() <= 1)
 577     return;
 578
 579   // Sort the indexes in place using std::stable_sort.
 580   // NOTE: The use of std::stable_sort instead of llvm::sort here is strictly
 581   // for performance, not correctness.  The indexes vector tends to be "close"
 582   // to sorted, which the stable sort handles better.
 583
 584   std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS);
 585
 586   SymbolIndexComparator comparator(m_symbols, addr_cache);
 587   std::stable_sort(indexes.begin(), indexes.end(), comparator);
 588
 589   // Remove any duplicates if requested
 590   if (remove_duplicates) {
 591     auto last = std::unique(indexes.begin(), indexes.end());
 592     indexes.erase(last, indexes.end());
 593   }
 594 }
 595
 596 uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name,
 597                                              std::vector<uint32_t> &indexes) {
 598   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 599
 600   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 601   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 602   if (symbol_name) {
 603     if (!m_name_indexes_computed)
 604       InitNameIndexes();
 605
 606     return m_name_to_index.GetValues(symbol_name, indexes);
 607   }
 608   return 0;
 609 }
 610
 611 uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name,
 612                                              Debug symbol_debug_type,
 613                                              Visibility symbol_visibility,
 614                                              std::vector<uint32_t> &indexes) {
 615   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 616
 617   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 618   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 619   if (symbol_name) {
 620     const size_t old_size = indexes.size();
 621     if (!m_name_indexes_computed)
 622       InitNameIndexes();
 623
 624     std::vector<uint32_t> all_name_indexes;
 625     const size_t name_match_count =
 626         m_name_to_index.GetValues(symbol_name, all_name_indexes);
 627     for (size_t i = 0; i < name_match_count; ++i) {
 628       if (CheckSymbolAtIndex(all_name_indexes[i], symbol_debug_type,
 629                              symbol_visibility))
 630         indexes.push_back(all_name_indexes[i]);
 631     }
 632     return indexes.size() - old_size;
 633   }
 634   return 0;
 635 }
 636
 637 uint32_t
 638 Symtab::AppendSymbolIndexesWithNameAndType(ConstString symbol_name,
 639                                            SymbolType symbol_type,
 640                                            std::vector<uint32_t> &indexes) {
 641   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 642
 643   if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0) {
 644     std::vector<uint32_t>::iterator pos = indexes.begin();
 645     while (pos != indexes.end()) {
 646       if (symbol_type == eSymbolTypeAny ||
 647           m_symbols[*pos].GetType() == symbol_type)
 648         ++pos;
 649       else
 650         pos = indexes.erase(pos);
 651     }
 652   }
 653   return indexes.size();
 654 }
 655
 656 uint32_t Symtab::AppendSymbolIndexesWithNameAndType(
 657     ConstString symbol_name, SymbolType symbol_type,
 658     Debug symbol_debug_type, Visibility symbol_visibility,
 659     std::vector<uint32_t> &indexes) {
 660   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 661
 662   if (AppendSymbolIndexesWithName(symbol_name, symbol_debug_type,
 663                                   symbol_visibility, indexes) > 0) {
 664     std::vector<uint32_t>::iterator pos = indexes.begin();
 665     while (pos != indexes.end()) {
 666       if (symbol_type == eSymbolTypeAny ||
 667           m_symbols[*pos].GetType() == symbol_type)
 668         ++pos;
 669       else
 670         pos = indexes.erase(pos);
 671     }
 672   }
 673   return indexes.size();
 674 }
 675
 676 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
 677     const RegularExpression &regexp, SymbolType symbol_type,
 678     std::vector<uint32_t> &indexes) {
 679   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 680
 681   uint32_t prev_size = indexes.size();
 682   uint32_t sym_end = m_symbols.size();
 683
 684   for (uint32_t i = 0; i < sym_end; i++) {
 685     if (symbol_type == eSymbolTypeAny ||
 686         m_symbols[i].GetType() == symbol_type) {
 687       const char *name = m_symbols[i].GetName().AsCString();
 688       if (name) {
 689         if (regexp.Execute(name))
 690           indexes.push_back(i);
 691       }
 692     }
 693   }
 694   return indexes.size() - prev_size;
 695 }
 696
 697 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
 698     const RegularExpression &regexp, SymbolType symbol_type,
 699     Debug symbol_debug_type, Visibility symbol_visibility,
 700     std::vector<uint32_t> &indexes) {
 701   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 702
 703   uint32_t prev_size = indexes.size();
 704   uint32_t sym_end = m_symbols.size();
 705
 706   for (uint32_t i = 0; i < sym_end; i++) {
 707     if (symbol_type == eSymbolTypeAny ||
 708         m_symbols[i].GetType() == symbol_type) {
 709       if (!CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility))
 710         continue;
 711
 712       const char *name = m_symbols[i].GetName().AsCString();
 713       if (name) {
 714         if (regexp.Execute(name))
 715           indexes.push_back(i);
 716       }
 717     }
 718   }
 719   return indexes.size() - prev_size;
 720 }
 721
 722 Symbol *Symtab::FindSymbolWithType(SymbolType symbol_type,
 723                                    Debug symbol_debug_type,
 724                                    Visibility symbol_visibility,
 725                                    uint32_t &start_idx) {
 726   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 727
 728   const size_t count = m_symbols.size();
 729   for (size_t idx = start_idx; idx < count; ++idx) {
 730     if (symbol_type == eSymbolTypeAny ||
 731         m_symbols[idx].GetType() == symbol_type) {
 732       if (CheckSymbolAtIndex(idx, symbol_debug_type, symbol_visibility)) {
 733         start_idx = idx;
 734         return &m_symbols[idx];
 735       }
 736     }
 737   }
 738   return nullptr;
 739 }
 740
 741 size_t
 742 Symtab::FindAllSymbolsWithNameAndType(ConstString name,
 743                                       SymbolType symbol_type,
 744                                       std::vector<uint32_t> &symbol_indexes) {
 745   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 746
 747   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 748   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 749   // Initialize all of the lookup by name indexes before converting NAME to a
 750   // uniqued string NAME_STR below.
 751   if (!m_name_indexes_computed)
 752     InitNameIndexes();
 753
 754   if (name) {
 755     // The string table did have a string that matched, but we need to check
 756     // the symbols and match the symbol_type if any was given.
 757     AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_indexes);
 758   }
 759   return symbol_indexes.size();
 760 }
 761
 762 size_t Symtab::FindAllSymbolsWithNameAndType(
 763     ConstString name, SymbolType symbol_type, Debug symbol_debug_type,
 764     Visibility symbol_visibility, std::vector<uint32_t> &symbol_indexes) {
 765   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 766
 767   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 768   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 769   // Initialize all of the lookup by name indexes before converting NAME to a
 770   // uniqued string NAME_STR below.
 771   if (!m_name_indexes_computed)
 772     InitNameIndexes();
 773
 774   if (name) {
 775     // The string table did have a string that matched, but we need to check
 776     // the symbols and match the symbol_type if any was given.
 777     AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
 778                                        symbol_visibility, symbol_indexes);
 779   }
 780   return symbol_indexes.size();
 781 }
 782
 783 size_t Symtab::FindAllSymbolsMatchingRexExAndType(
 784     const RegularExpression &regex, SymbolType symbol_type,
 785     Debug symbol_debug_type, Visibility symbol_visibility,
 786     std::vector<uint32_t> &symbol_indexes) {
 787   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 788
 789   AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_debug_type,
 790                                           symbol_visibility, symbol_indexes);
 791   return symbol_indexes.size();
 792 }
 793
 794 Symbol *Symtab::FindFirstSymbolWithNameAndType(ConstString name,
 795                                                SymbolType symbol_type,
 796                                                Debug symbol_debug_type,
 797                                                Visibility symbol_visibility) {
 798   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 799
 800   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 801   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 802   if (!m_name_indexes_computed)
 803     InitNameIndexes();
 804
 805   if (name) {
 806     std::vector<uint32_t> matching_indexes;
 807     // The string table did have a string that matched, but we need to check
 808     // the symbols and match the symbol_type if any was given.
 809     if (AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
 810                                            symbol_visibility,
 811                                            matching_indexes)) {
 812       std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end();
 813       for (pos = matching_indexes.begin(); pos != end; ++pos) {
 814         Symbol *symbol = SymbolAtIndex(*pos);
 815
 816         if (symbol->Compare(name, symbol_type))
 817           return symbol;
 818       }
 819     }
 820   }
 821   return nullptr;
 822 }
 823
 824 typedef struct {
 825   const Symtab *symtab;
 826   const addr_t file_addr;
 827   Symbol *match_symbol;
 828   const uint32_t *match_index_ptr;
 829   addr_t match_offset;
 830 } SymbolSearchInfo;
 831
 832 // Add all the section file start address & size to the RangeVector, recusively
 833 // adding any children sections.
 834 static void AddSectionsToRangeMap(SectionList *sectlist,
 835                                   RangeVector<addr_t, addr_t> &section_ranges) {
 836   const int num_sections = sectlist->GetNumSections(0);
 837   for (int i = 0; i < num_sections; i++) {
 838     SectionSP sect_sp = sectlist->GetSectionAtIndex(i);
 839     if (sect_sp) {
 840       SectionList &child_sectlist = sect_sp->GetChildren();
 841
 842       // If this section has children, add the children to the RangeVector.
 843       // Else add this section to the RangeVector.
 844       if (child_sectlist.GetNumSections(0) > 0) {
 845         AddSectionsToRangeMap(&child_sectlist, section_ranges);
 846       } else {
 847         size_t size = sect_sp->GetByteSize();
 848         if (size > 0) {
 849           addr_t base_addr = sect_sp->GetFileAddress();
 850           RangeVector<addr_t, addr_t>::Entry entry;
 851           entry.SetRangeBase(base_addr);
 852           entry.SetByteSize(size);
 853           section_ranges.Append(entry);
 854         }
 855       }
 856     }
 857   }
 858 }
 859
 860 void Symtab::InitAddressIndexes() {
 861   // Protected function, no need to lock mutex...
 862   if (!m_file_addr_to_index_computed && !m_symbols.empty()) {
 863     m_file_addr_to_index_computed = true;
 864
 865     FileRangeToIndexMap::Entry entry;
 866     const_iterator begin = m_symbols.begin();
 867     const_iterator end = m_symbols.end();
 868     for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
 869       if (pos->ValueIsAddress()) {
 870         entry.SetRangeBase(pos->GetAddressRef().GetFileAddress());
 871         entry.SetByteSize(pos->GetByteSize());
 872         entry.data = std::distance(begin, pos);
 873         m_file_addr_to_index.Append(entry);
 874       }
 875     }
 876     const size_t num_entries = m_file_addr_to_index.GetSize();
 877     if (num_entries > 0) {
 878       m_file_addr_to_index.Sort();
 879
 880       // Create a RangeVector with the start & size of all the sections for
 881       // this objfile.  We'll need to check this for any FileRangeToIndexMap
 882       // entries with an uninitialized size, which could potentially be a large
 883       // number so reconstituting the weak pointer is busywork when it is
 884       // invariant information.
 885       SectionList *sectlist = m_objfile->GetSectionList();
 886       RangeVector<addr_t, addr_t> section_ranges;
 887       if (sectlist) {
 888         AddSectionsToRangeMap(sectlist, section_ranges);
 889         section_ranges.Sort();
 890       }
 891
 892       // Iterate through the FileRangeToIndexMap and fill in the size for any
 893       // entries that didn't already have a size from the Symbol (e.g. if we
 894       // have a plain linker symbol with an address only, instead of debug info
 895       // where we get an address and a size and a type, etc.)
 896       for (size_t i = 0; i < num_entries; i++) {
 897         FileRangeToIndexMap::Entry *entry =
 898             m_file_addr_to_index.GetMutableEntryAtIndex(i);
 899         if (entry->GetByteSize() > 0)
 900           continue;
 901         addr_t curr_base_addr = entry->GetRangeBase();
 902         // Symbols with non-zero size will show after zero-sized symbols on the
 903         // same address. So do not set size of a non-last zero-sized symbol.
 904         if (i == num_entries - 1 ||
 905             m_file_addr_to_index.GetMutableEntryAtIndex(i + 1)
 906                     ->GetRangeBase() != curr_base_addr) {
 907           const RangeVector<addr_t, addr_t>::Entry *containing_section =
 908               section_ranges.FindEntryThatContains(curr_base_addr);
 909
 910           // Use the end of the section as the default max size of the symbol
 911           addr_t sym_size = 0;
 912           if (containing_section) {
 913             sym_size =
 914                 containing_section->GetByteSize() -
 915                 (entry->GetRangeBase() - containing_section->GetRangeBase());
 916           }
 917
 918           for (size_t j = i; j < num_entries; j++) {
 919             FileRangeToIndexMap::Entry *next_entry =
 920                 m_file_addr_to_index.GetMutableEntryAtIndex(j);
 921             addr_t next_base_addr = next_entry->GetRangeBase();
 922             if (next_base_addr > curr_base_addr) {
 923               addr_t size_to_next_symbol = next_base_addr - curr_base_addr;
 924
 925               // Take the difference between this symbol and the next one as
 926               // its size, if it is less than the size of the section.
 927               if (sym_size == 0 || size_to_next_symbol < sym_size) {
 928                 sym_size = size_to_next_symbol;
 929               }
 930               break;
 931             }
 932           }
 933
 934           if (sym_size > 0) {
 935             entry->SetByteSize(sym_size);
 936             Symbol &symbol = m_symbols[entry->data];
 937             symbol.SetByteSize(sym_size);
 938             symbol.SetSizeIsSynthesized(true);
 939           }
 940         }
 941       }
 942
 943       // Sort again in case the range size changes the ordering
 944       m_file_addr_to_index.Sort();
 945     }
 946   }
 947 }
 948
 949 void Symtab::CalculateSymbolSizes() {
 950   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 951   // Size computation happens inside InitAddressIndexes.
 952   InitAddressIndexes();
 953 }
 954
 955 Symbol *Symtab::FindSymbolAtFileAddress(addr_t file_addr) {
 956   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 957   if (!m_file_addr_to_index_computed)
 958     InitAddressIndexes();
 959
 960   const FileRangeToIndexMap::Entry *entry =
 961       m_file_addr_to_index.FindEntryStartsAt(file_addr);
 962   if (entry) {
 963     Symbol *symbol = SymbolAtIndex(entry->data);
 964     if (symbol->GetFileAddress() == file_addr)
 965       return symbol;
 966   }
 967   return nullptr;
 968 }
 969
 970 Symbol *Symtab::FindSymbolContainingFileAddress(addr_t file_addr) {
 971   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 972
 973   if (!m_file_addr_to_index_computed)
 974     InitAddressIndexes();
 975
 976   const FileRangeToIndexMap::Entry *entry =
 977       m_file_addr_to_index.FindEntryThatContains(file_addr);
 978   if (entry) {
 979     Symbol *symbol = SymbolAtIndex(entry->data);
 980     if (symbol->ContainsFileAddress(file_addr))
 981       return symbol;
 982   }
 983   return nullptr;
 984 }
 985
 986 void Symtab::ForEachSymbolContainingFileAddress(
 987     addr_t file_addr, std::function<bool(Symbol *)> const &callback) {
 988   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 989
 990   if (!m_file_addr_to_index_computed)
 991     InitAddressIndexes();
 992
 993   std::vector<uint32_t> all_addr_indexes;
 994
 995   // Get all symbols with file_addr
 996   const size_t addr_match_count =
 997       m_file_addr_to_index.FindEntryIndexesThatContain(file_addr,
 998                                                        all_addr_indexes);
 999
1000   for (size_t i = 0; i < addr_match_count; ++i) {
1001     Symbol *symbol = SymbolAtIndex(all_addr_indexes[i]);
1002     if (symbol->ContainsFileAddress(file_addr)) {
1003       if (!callback(symbol))
1004         break;
1005     }
1006   }
1007 }
1008
1009 void Symtab::SymbolIndicesToSymbolContextList(
1010     std::vector<uint32_t> &symbol_indexes, SymbolContextList &sc_list) {
1011   // No need to protect this call using m_mutex all other method calls are
1012   // already thread safe.
1013
1014   const bool merge_symbol_into_function = true;
1015   size_t num_indices = symbol_indexes.size();
1016   if (num_indices > 0) {
1017     SymbolContext sc;
1018     sc.module_sp = m_objfile->GetModule();
1019     for (size_t i = 0; i < num_indices; i++) {
1020       sc.symbol = SymbolAtIndex(symbol_indexes[i]);
1021       if (sc.symbol)
1022         sc_list.AppendIfUnique(sc, merge_symbol_into_function);
1023     }
1024   }
1025 }
1026
1027 size_t Symtab::FindFunctionSymbols(ConstString name,
1028                                    uint32_t name_type_mask,
1029                                    SymbolContextList &sc_list) {
1030   size_t count = 0;
1031   std::vector<uint32_t> symbol_indexes;
1032
1033   // eFunctionNameTypeAuto should be pre-resolved by a call to
1034   // Module::LookupInfo::LookupInfo()
1035   assert((name_type_mask & eFunctionNameTypeAuto) == 0);
1036
1037   if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) {
1038     std::vector<uint32_t> temp_symbol_indexes;
1039     FindAllSymbolsWithNameAndType(name, eSymbolTypeAny, temp_symbol_indexes);
1040
1041     unsigned temp_symbol_indexes_size = temp_symbol_indexes.size();
1042     if (temp_symbol_indexes_size > 0) {
1043       std::lock_guard<std::recursive_mutex> guard(m_mutex);
1044       for (unsigned i = 0; i < temp_symbol_indexes_size; i++) {
1045         SymbolContext sym_ctx;
1046         sym_ctx.symbol = SymbolAtIndex(temp_symbol_indexes[i]);
1047         if (sym_ctx.symbol) {
1048           switch (sym_ctx.symbol->GetType()) {
1049           case eSymbolTypeCode:
1050           case eSymbolTypeResolver:
1051           case eSymbolTypeReExported:
1052             symbol_indexes.push_back(temp_symbol_indexes[i]);
1053             break;
1054           default:
1055             break;
1056           }
1057         }
1058       }
1059     }
1060   }
1061
1062   if (name_type_mask & eFunctionNameTypeBase) {
1063     // From mangled names we can't tell what is a basename and what is a method
1064     // name, so we just treat them the same
1065     if (!m_name_indexes_computed)
1066       InitNameIndexes();
1067
1068     if (!m_basename_to_index.IsEmpty()) {
1069       const UniqueCStringMap<uint32_t>::Entry *match;
1070       for (match = m_basename_to_index.FindFirstValueForName(name);
1071            match != nullptr;
1072            match = m_basename_to_index.FindNextValueForName(match)) {
1073         symbol_indexes.push_back(match->value);
1074       }
1075     }
1076   }
1077
1078   if (name_type_mask & eFunctionNameTypeMethod) {
1079     if (!m_name_indexes_computed)
1080       InitNameIndexes();
1081
1082     if (!m_method_to_index.IsEmpty()) {
1083       const UniqueCStringMap<uint32_t>::Entry *match;
1084       for (match = m_method_to_index.FindFirstValueForName(name);
1085            match != nullptr;
1086            match = m_method_to_index.FindNextValueForName(match)) {
1087         symbol_indexes.push_back(match->value);
1088       }
1089     }
1090   }
1091
1092   if (name_type_mask & eFunctionNameTypeSelector) {
1093     if (!m_name_indexes_computed)
1094       InitNameIndexes();
1095
1096     if (!m_selector_to_index.IsEmpty()) {
1097       const UniqueCStringMap<uint32_t>::Entry *match;
1098       for (match = m_selector_to_index.FindFirstValueForName(name);
1099            match != nullptr;
1100            match = m_selector_to_index.FindNextValueForName(match)) {
1101         symbol_indexes.push_back(match->value);
1102       }
1103     }
1104   }
1105
1106   if (!symbol_indexes.empty()) {
1107     llvm::sort(symbol_indexes.begin(), symbol_indexes.end());
1108     symbol_indexes.erase(
1109         std::unique(symbol_indexes.begin(), symbol_indexes.end()),
1110         symbol_indexes.end());
1111     count = symbol_indexes.size();
1112     SymbolIndicesToSymbolContextList(symbol_indexes, sc_list);
1113   }
1114
1115   return count;
1116 }
1117
1118 const Symbol *Symtab::GetParent(Symbol *child_symbol) const {
1119   uint32_t child_idx = GetIndexForSymbol(child_symbol);
1120   if (child_idx != UINT32_MAX && child_idx > 0) {
1121     for (uint32_t idx = child_idx - 1; idx != UINT32_MAX; --idx) {
1122       const Symbol *symbol = SymbolAtIndex(idx);
1123       const uint32_t sibling_idx = symbol->GetSiblingIndex();
1124       if (sibling_idx != UINT32_MAX && sibling_idx > child_idx)
1125         return symbol;
1126     }
1127   }
1128   return nullptr;
1129 }