contrib/llvm/tools/lldb/source/Symbol/Symtab.cpp

   1 //===-- Symtab.cpp ----------------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include <map>
  11 #include <set>
  12
  13 #include "Plugins/Language/ObjC/ObjCLanguage.h"
  14
  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"
  26
  27 #include "llvm/ADT/StringRef.h"
  28
  29 using namespace lldb;
  30 using namespace lldb_private;
  31
  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) {}
  36
  37 Symtab::~Symtab() {}
  38
  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);
  43 }
  44
  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];
  50 }
  51
  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;
  61   return symbol_idx;
  62 }
  63
  64 size_t Symtab::GetNumSymbols() const {
  65   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  66   return m_symbols.size();
  67 }
  68
  69 void Symtab::SectionFileAddressesChanged() {
  70   m_name_to_index.Clear();
  71   m_file_addr_to_index_computed = false;
  72 }
  73
  74 void Symtab::Dump(Stream *s, Target *target, SortOrder sort_order) {
  75   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  76
  77   //    s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
  78   s->Indent();
  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();
  83
  84   if (file_spec)
  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());
  89   else
  90     s->Printf("Symtab, num_symbols = %" PRIu64 "", (uint64_t)m_symbols.size());
  91
  92   if (!m_symbols.empty()) {
  93     switch (sort_order) {
  94     case eSortOrderNone: {
  95       s->PutCString(":\n");
  96       DumpSymbolHeader(s);
  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) {
 100         s->Indent();
 101         pos->Dump(s, target, std::distance(begin, pos));
 102       }
 103     } break;
 104
 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");
 109       DumpSymbolHeader(s);
 110       typedef std::multimap<const char *, const Symbol *,
 111                             CStringCompareFunctionObject>
 112           CStringToSymbol;
 113       CStringToSymbol name_map;
 114       for (const_iterator pos = m_symbols.begin(), end = m_symbols.end();
 115            pos != end; ++pos) {
 116         const char *name = pos->GetName().AsCString();
 117         if (name && name[0])
 118           name_map.insert(std::make_pair(name, &(*pos)));
 119       }
 120
 121       for (CStringToSymbol::const_iterator pos = name_map.begin(),
 122                                            end = name_map.end();
 123            pos != end; ++pos) {
 124         s->Indent();
 125         pos->second->Dump(s, target, pos->second - &m_symbols[0]);
 126       }
 127     } break;
 128
 129     case eSortOrderByAddress:
 130       s->PutCString(" (sorted by address):\n");
 131       DumpSymbolHeader(s);
 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) {
 136         s->Indent();
 137         const uint32_t symbol_idx = m_file_addr_to_index.GetEntryRef(i).data;
 138         m_symbols[symbol_idx].Dump(s, target, symbol_idx);
 139       }
 140       break;
 141     }
 142   } else {
 143     s->PutCString("\n");
 144   }
 145 }
 146
 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);
 150
 151   const size_t num_symbols = GetNumSymbols();
 152   // s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
 153   s->Indent();
 154   s->Printf("Symtab %" PRIu64 " symbol indexes (%" PRIu64 " symbols total):\n",
 155             (uint64_t)indexes.size(), (uint64_t)m_symbols.size());
 156   s->IndentMore();
 157
 158   if (!indexes.empty()) {
 159     std::vector<uint32_t>::const_iterator pos;
 160     std::vector<uint32_t>::const_iterator end = indexes.end();
 161     DumpSymbolHeader(s);
 162     for (pos = indexes.begin(); pos != end; ++pos) {
 163       size_t idx = *pos;
 164       if (idx < num_symbols) {
 165         s->Indent();
 166         m_symbols[idx].Dump(s, target, idx);
 167       }
 168     }
 169   }
 170   s->IndentLess();
 171 }
 172
 173 void Symtab::DumpSymbolHeader(Stream *s) {
 174   s->Indent("               Debug symbol\n");
 175   s->Indent("               |Synthetic symbol\n");
 176   s->Indent("               ||Externally Visible\n");
 177   s->Indent("               |||\n");
 178   s->Indent("Index   UserID DSX Type            File Address/Value Load "
 179             "Address       Size               Flags      Name\n");
 180   s->Indent("------- ------ --- --------------- ------------------ "
 181             "------------------ ------------------ ---------- "
 182             "----------------------------------\n");
 183 }
 184
 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)
 189     return -1;
 190   if (match_uid > symbol_uid)
 191     return 1;
 192   return 0;
 193 }
 194
 195 Symbol *Symtab::FindSymbolByID(lldb::user_id_t symbol_uid) const {
 196   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 197
 198   Symbol *symbol =
 199       (Symbol *)::bsearch(&symbol_uid, &m_symbols[0], m_symbols.size(),
 200                           sizeof(m_symbols[0]), CompareSymbolID);
 201   return symbol;
 202 }
 203
 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];
 209   return nullptr;
 210 }
 211
 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];
 217   return nullptr;
 218 }
 219
 220 //----------------------------------------------------------------------
 221 // InitNameIndexes
 222 //----------------------------------------------------------------------
 223 static bool lldb_skip_name(llvm::StringRef mangled,
 224                            Mangled::ManglingScheme scheme) {
 225   switch (scheme) {
 226   case Mangled::eManglingSchemeItanium: {
 227     if (mangled.size() < 3 || !mangled.startswith("_Z"))
 228       return true;
 229
 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)
 236       return true;
 237
 238     default:
 239       break;
 240     }
 241
 242     // Include this name in the index.
 243     return false;
 244   }
 245
 246   // No filters for this scheme yet. Include all names in indexing.
 247   case Mangled::eManglingSchemeMSVC:
 248     return false;
 249
 250   // Don't try and demangle things we can't categorize.
 251   case Mangled::eManglingSchemeNone:
 252     return true;
 253   }
 254   llvm_unreachable("unknown scheme!");
 255 }
 256
 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();
 265 #if 1
 266     m_name_to_index.Reserve(num_symbols);
 267 #else
 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();
 273          pos != end; ++pos) {
 274       const Mangled &mangled = pos->GetMangled();
 275       if (mangled.GetMangledName())
 276         ++actual_count;
 277
 278       if (mangled.GetDemangledName())
 279         ++actual_count;
 280     }
 281
 282     m_name_to_index.Reserve(actual_count);
 283 #endif
 284
 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);
 290
 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;
 295
 296     for (entry.value = 0; entry.value < num_symbols; ++entry.value) {
 297       Symbol *symbol = &m_symbols[entry.value];
 298
 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())
 304         continue;
 305
 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();
 310       if (entry.cstring) {
 311         m_name_to_index.Append(entry);
 312
 313         if (symbol->ContainsLinkerAnnotations()) {
 314           // If the symbol has linker annotations, also add the version without
 315           // the annotations.
 316           entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations(
 317                                         entry.cstring.GetStringRef()));
 318           m_name_to_index.Append(entry);
 319         }
 320
 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);
 325         }
 326       }
 327
 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());
 331       if (entry.cstring) {
 332         m_name_to_index.Append(entry);
 333
 334         if (symbol->ContainsLinkerAnnotations()) {
 335           // If the symbol has linker annotations, also add the version without
 336           // the annotations.
 337           entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations(
 338                                         entry.cstring.GetStringRef()));
 339           m_name_to_index.Append(entry);
 340         }
 341       }
 342
 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);
 349
 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);
 355         }
 356       }
 357     }
 358
 359     for (const auto &record : backlog) {
 360       RegisterBacklogEntry(record.first, record.second, class_contexts);
 361     }
 362
 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();
 371   }
 372 }
 373
 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())
 382     return;
 383
 384   // The base name will be our entry's name.
 385   entry.cstring = ConstString(base_name);
 386
 387   rmc.ParseFunctionDeclContextName();
 388   llvm::StringRef decl_context = rmc.GetBufferRef();
 389
 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);
 397     return;
 398   }
 399
 400   // Make sure we have a pool-string pointer and see if we already know the
 401   // context name.
 402   const char *decl_context_ccstr = ConstString(decl_context).GetCString();
 403   auto it = class_contexts.find(decl_context_ccstr);
 404
 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);
 411     return;
 412   }
 413
 414   // Register regular methods with a known declaration context.
 415   if (it != class_contexts.end()) {
 416     m_method_to_index.Append(entry);
 417     return;
 418   }
 419
 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));
 423 }
 424
 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);
 431   } else {
 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);
 436   }
 437 }
 438
 439 void Symtab::PreloadSymbols() {
 440   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 441   InitNameIndexes();
 442 }
 443
 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);
 451
 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];
 459
 460       const Mangled &mangled = symbol->GetMangled();
 461       if (add_demangled) {
 462         entry.cstring = mangled.GetDemangledName(symbol->GetLanguage());
 463         if (entry.cstring)
 464           name_to_index_map.Append(entry);
 465       }
 466
 467       if (add_mangled) {
 468         entry.cstring = mangled.GetMangledName();
 469         if (entry.cstring)
 470           name_to_index_map.Append(entry);
 471       }
 472     }
 473   }
 474 }
 475
 476 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
 477                                              std::vector<uint32_t> &indexes,
 478                                              uint32_t start_idx,
 479                                              uint32_t end_index) const {
 480   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 481
 482   uint32_t prev_size = indexes.size();
 483
 484   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 485
 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);
 489   }
 490
 491   return indexes.size() - prev_size;
 492 }
 493
 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);
 499
 500   uint32_t prev_size = indexes.size();
 501
 502   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 503
 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);
 509   }
 510
 511   return indexes.size() - prev_size;
 512 }
 513
 514 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
 515                                              Debug symbol_debug_type,
 516                                              Visibility symbol_visibility,
 517                                              std::vector<uint32_t> &indexes,
 518                                              uint32_t start_idx,
 519                                              uint32_t end_index) const {
 520   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 521
 522   uint32_t prev_size = indexes.size();
 523
 524   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 525
 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);
 531     }
 532   }
 533
 534   return indexes.size() - prev_size;
 535 }
 536
 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;
 542   }
 543   return UINT32_MAX;
 544 }
 545
 546 struct SymbolSortInfo {
 547   const bool sort_by_load_addr;
 548   const Symbol *symbols;
 549 };
 550
 551 namespace {
 552 struct SymbolIndexComparator {
 553   const std::vector<Symbol> &symbols;
 554   std::vector<lldb::addr_t> &addr_cache;
 555
 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
 563   // std::stable_sort
 564   // makes copies of the comparator it is initially passed in, and you end up
 565   // spending huge amounts of time copying this array...
 566
 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());
 571   }
 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;
 577     }
 578
 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;
 583     }
 584
 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();
 589       if (uid_a < uid_b)
 590         return true;
 591       if (uid_a > uid_b)
 592         return false;
 593       return false;
 594     } else if (value_a < value_b)
 595       return true;
 596
 597     return false;
 598   }
 599 };
 600 }
 601
 602 void Symtab::SortSymbolIndexesByValue(std::vector<uint32_t> &indexes,
 603                                       bool remove_duplicates) const {
 604   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 605
 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)
 610     return;
 611
 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.
 616
 617   std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS);
 618
 619   SymbolIndexComparator comparator(m_symbols, addr_cache);
 620   std::stable_sort(indexes.begin(), indexes.end(), comparator);
 621
 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());
 626   }
 627 }
 628
 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);
 632
 633   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 634   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 635   if (symbol_name) {
 636     if (!m_name_indexes_computed)
 637       InitNameIndexes();
 638
 639     return m_name_to_index.GetValues(symbol_name, indexes);
 640   }
 641   return 0;
 642 }
 643
 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);
 649
 650   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 651   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 652   if (symbol_name) {
 653     const size_t old_size = indexes.size();
 654     if (!m_name_indexes_computed)
 655       InitNameIndexes();
 656
 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,
 662                              symbol_visibility))
 663         indexes.push_back(all_name_indexes[i]);
 664     }
 665     return indexes.size() - old_size;
 666   }
 667   return 0;
 668 }
 669
 670 uint32_t
 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);
 675
 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)
 681         ++pos;
 682       else
 683         pos = indexes.erase(pos);
 684     }
 685   }
 686   return indexes.size();
 687 }
 688
 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);
 694
 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)
 701         ++pos;
 702       else
 703         pos = indexes.erase(pos);
 704     }
 705   }
 706   return indexes.size();
 707 }
 708
 709 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
 710     const RegularExpression &regexp, SymbolType symbol_type,
 711     std::vector<uint32_t> &indexes) {
 712   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 713
 714   uint32_t prev_size = indexes.size();
 715   uint32_t sym_end = m_symbols.size();
 716
 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();
 721       if (name) {
 722         if (regexp.Execute(name))
 723           indexes.push_back(i);
 724       }
 725     }
 726   }
 727   return indexes.size() - prev_size;
 728 }
 729
 730 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
 731     const RegularExpression &regexp, 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);
 735
 736   uint32_t prev_size = indexes.size();
 737   uint32_t sym_end = m_symbols.size();
 738
 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))
 743         continue;
 744
 745       const char *name = m_symbols[i].GetName().AsCString();
 746       if (name) {
 747         if (regexp.Execute(name))
 748           indexes.push_back(i);
 749       }
 750     }
 751   }
 752   return indexes.size() - prev_size;
 753 }
 754
 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);
 760
 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)) {
 766         start_idx = idx;
 767         return &m_symbols[idx];
 768       }
 769     }
 770   }
 771   return nullptr;
 772 }
 773
 774 size_t
 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);
 779
 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)
 785     InitNameIndexes();
 786
 787   if (name) {
 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);
 791   }
 792   return symbol_indexes.size();
 793 }
 794
 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);
 799
 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)
 805     InitNameIndexes();
 806
 807   if (name) {
 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);
 812   }
 813   return symbol_indexes.size();
 814 }
 815
 816 size_t Symtab::FindAllSymbolsMatchingRexExAndType(
 817     const RegularExpression &regex, 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);
 821
 822   AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_debug_type,
 823                                           symbol_visibility, symbol_indexes);
 824   return symbol_indexes.size();
 825 }
 826
 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);
 832
 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)
 836     InitNameIndexes();
 837
 838   if (name) {
 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,
 843                                            symbol_visibility,
 844                                            matching_indexes)) {
 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);
 848
 849         if (symbol->Compare(name, symbol_type))
 850           return symbol;
 851       }
 852     }
 853   }
 854   return nullptr;
 855 }
 856
 857 typedef struct {
 858   const Symtab *symtab;
 859   const addr_t file_addr;
 860   Symbol *match_symbol;
 861   const uint32_t *match_index_ptr;
 862   addr_t match_offset;
 863 } SymbolSearchInfo;
 864
 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> &section_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);
 872     if (sect_sp) {
 873       SectionList &child_sectlist = sect_sp->GetChildren();
 874
 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);
 879       } else {
 880         size_t size = sect_sp->GetByteSize();
 881         if (size > 0) {
 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);
 887         }
 888       }
 889     }
 890   }
 891 }
 892
 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;
 897
 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);
 907       }
 908     }
 909     const size_t num_entries = m_file_addr_to_index.GetSize();
 910     if (num_entries > 0) {
 911       m_file_addr_to_index.Sort();
 912
 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;
 920       if (sectlist) {
 921         AddSectionsToRangeMap(sectlist, section_ranges);
 922         section_ranges.Sort();
 923       }
 924
 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);
 936
 937           // Use the end of the section as the default max size of the symbol
 938           addr_t sym_size = 0;
 939           if (containing_section) {
 940             sym_size =
 941                 containing_section->GetByteSize() -
 942                 (entry->GetRangeBase() - containing_section->GetRangeBase());
 943           }
 944
 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;
 951
 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;
 956               }
 957               break;
 958             }
 959           }
 960
 961           if (sym_size > 0) {
 962             entry->SetByteSize(sym_size);
 963             Symbol &symbol = m_symbols[entry->data];
 964             symbol.SetByteSize(sym_size);
 965             symbol.SetSizeIsSynthesized(true);
 966           }
 967         }
 968       }
 969
 970       // Sort again in case the range size changes the ordering
 971       m_file_addr_to_index.Sort();
 972     }
 973   }
 974 }
 975
 976 void Symtab::CalculateSymbolSizes() {
 977   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 978   // Size computation happens inside InitAddressIndexes.
 979   InitAddressIndexes();
 980 }
 981
 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();
 986
 987   const FileRangeToIndexMap::Entry *entry =
 988       m_file_addr_to_index.FindEntryStartsAt(file_addr);
 989   if (entry) {
 990     Symbol *symbol = SymbolAtIndex(entry->data);
 991     if (symbol->GetFileAddress() == file_addr)
 992       return symbol;
 993   }
 994   return nullptr;
 995 }
 996
 997 Symbol *Symtab::FindSymbolContainingFileAddress(addr_t file_addr) {
 998   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 999
1000   if (!m_file_addr_to_index_computed)
1001     InitAddressIndexes();
1002
1003   const FileRangeToIndexMap::Entry *entry =
1004       m_file_addr_to_index.FindEntryThatContains(file_addr);
1005   if (entry) {
1006     Symbol *symbol = SymbolAtIndex(entry->data);
1007     if (symbol->ContainsFileAddress(file_addr))
1008       return symbol;
1009   }
1010   return nullptr;
1011 }
1012
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);
1016
1017   if (!m_file_addr_to_index_computed)
1018     InitAddressIndexes();
1019
1020   std::vector<uint32_t> all_addr_indexes;
1021
1022   // Get all symbols with file_addr
1023   const size_t addr_match_count =
1024       m_file_addr_to_index.FindEntryIndexesThatContain(file_addr,
1025                                                        all_addr_indexes);
1026
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))
1031         break;
1032     }
1033   }
1034 }
1035
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.
1040
1041   const bool merge_symbol_into_function = true;
1042   size_t num_indices = symbol_indexes.size();
1043   if (num_indices > 0) {
1044     SymbolContext sc;
1045     sc.module_sp = m_objfile->GetModule();
1046     for (size_t i = 0; i < num_indices; i++) {
1047       sc.symbol = SymbolAtIndex(symbol_indexes[i]);
1048       if (sc.symbol)
1049         sc_list.AppendIfUnique(sc, merge_symbol_into_function);
1050     }
1051   }
1052 }
1053
1054 size_t Symtab::FindFunctionSymbols(const ConstString &name,
1055                                    uint32_t name_type_mask,
1056                                    SymbolContextList &sc_list) {
1057   size_t count = 0;
1058   std::vector<uint32_t> symbol_indexes;
1059
1060   // eFunctionNameTypeAuto should be pre-resolved by a call to
1061   // Module::LookupInfo::LookupInfo()
1062   assert((name_type_mask & eFunctionNameTypeAuto) == 0);
1063
1064   if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) {
1065     std::vector<uint32_t> temp_symbol_indexes;
1066     FindAllSymbolsWithNameAndType(name, eSymbolTypeAny, temp_symbol_indexes);
1067
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]);
1080             break;
1081           default:
1082             break;
1083           }
1084         }
1085       }
1086     }
1087   }
1088
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)
1093       InitNameIndexes();
1094
1095     if (!m_basename_to_index.IsEmpty()) {
1096       const UniqueCStringMap<uint32_t>::Entry *match;
1097       for (match = m_basename_to_index.FindFirstValueForName(name);
1098            match != nullptr;
1099            match = m_basename_to_index.FindNextValueForName(match)) {
1100         symbol_indexes.push_back(match->value);
1101       }
1102     }
1103   }
1104
1105   if (name_type_mask & eFunctionNameTypeMethod) {
1106     if (!m_name_indexes_computed)
1107       InitNameIndexes();
1108
1109     if (!m_method_to_index.IsEmpty()) {
1110       const UniqueCStringMap<uint32_t>::Entry *match;
1111       for (match = m_method_to_index.FindFirstValueForName(name);
1112            match != nullptr;
1113            match = m_method_to_index.FindNextValueForName(match)) {
1114         symbol_indexes.push_back(match->value);
1115       }
1116     }
1117   }
1118
1119   if (name_type_mask & eFunctionNameTypeSelector) {
1120     if (!m_name_indexes_computed)
1121       InitNameIndexes();
1122
1123     if (!m_selector_to_index.IsEmpty()) {
1124       const UniqueCStringMap<uint32_t>::Entry *match;
1125       for (match = m_selector_to_index.FindFirstValueForName(name);
1126            match != nullptr;
1127            match = m_selector_to_index.FindNextValueForName(match)) {
1128         symbol_indexes.push_back(match->value);
1129       }
1130     }
1131   }
1132
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);
1140   }
1141
1142   return count;
1143 }
1144
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)
1152         return symbol;
1153     }
1154   }
1155   return NULL;
1156 }