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