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