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/Section.h"
  17 #include "lldb/Core/STLUtils.h"
  18 #include "lldb/Core/Timer.h"
  19 #include "lldb/Symbol/ObjectFile.h"
  20 #include "lldb/Symbol/Symbol.h"
  21 #include "lldb/Symbol/SymbolContext.h"
  22 #include "lldb/Symbol/Symtab.h"
  23 #include "lldb/Utility/RegularExpression.h"
  24 #include "lldb/Utility/Stream.h"
  25
  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     //        static StreamFile a ("/tmp/a.txt");
 404     //
 405     //        count = m_basename_to_index.GetSize();
 406     //        if (count)
 407     //        {
 408     //            for (size_t i=0; i<count; ++i)
 409     //            {
 410     //                if (m_basename_to_index.GetValueAtIndex(i, entry.value))
 411     //                    a.Printf ("%s BASENAME\n",
 412     //                    m_symbols[entry.value].GetMangled().GetName().GetCString());
 413     //            }
 414     //        }
 415     //        count = m_method_to_index.GetSize();
 416     //        if (count)
 417     //        {
 418     //            for (size_t i=0; i<count; ++i)
 419     //            {
 420     //                if (m_method_to_index.GetValueAtIndex(i, entry.value))
 421     //                    a.Printf ("%s METHOD\n",
 422     //                    m_symbols[entry.value].GetMangled().GetName().GetCString());
 423     //            }
 424     //        }
 425   }
 426 }
 427
 428 void Symtab::PreloadSymbols() {
 429   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 430   InitNameIndexes();
 431 }
 432
 433 void Symtab::AppendSymbolNamesToMap(const IndexCollection &indexes,
 434                                     bool add_demangled, bool add_mangled,
 435                                     NameToIndexMap &name_to_index_map) const {
 436   if (add_demangled || add_mangled) {
 437     static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 438     Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 439     std::lock_guard<std::recursive_mutex> guard(m_mutex);
 440
 441     // Create the name index vector to be able to quickly search by name
 442     NameToIndexMap::Entry entry;
 443     const size_t num_indexes = indexes.size();
 444     for (size_t i = 0; i < num_indexes; ++i) {
 445       entry.value = indexes[i];
 446       assert(i < m_symbols.size());
 447       const Symbol *symbol = &m_symbols[entry.value];
 448
 449       const Mangled &mangled = symbol->GetMangled();
 450       if (add_demangled) {
 451         entry.cstring = mangled.GetDemangledName(symbol->GetLanguage());
 452         if (entry.cstring)
 453           name_to_index_map.Append(entry);
 454       }
 455
 456       if (add_mangled) {
 457         entry.cstring = mangled.GetMangledName();
 458         if (entry.cstring)
 459           name_to_index_map.Append(entry);
 460       }
 461     }
 462   }
 463 }
 464
 465 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
 466                                              std::vector<uint32_t> &indexes,
 467                                              uint32_t start_idx,
 468                                              uint32_t end_index) const {
 469   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 470
 471   uint32_t prev_size = indexes.size();
 472
 473   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 474
 475   for (uint32_t i = start_idx; i < count; ++i) {
 476     if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type)
 477       indexes.push_back(i);
 478   }
 479
 480   return indexes.size() - prev_size;
 481 }
 482
 483 uint32_t Symtab::AppendSymbolIndexesWithTypeAndFlagsValue(
 484     SymbolType symbol_type, uint32_t flags_value,
 485     std::vector<uint32_t> &indexes, uint32_t start_idx,
 486     uint32_t end_index) const {
 487   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 488
 489   uint32_t prev_size = indexes.size();
 490
 491   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 492
 493   for (uint32_t i = start_idx; i < count; ++i) {
 494     if ((symbol_type == eSymbolTypeAny ||
 495          m_symbols[i].GetType() == symbol_type) &&
 496         m_symbols[i].GetFlags() == flags_value)
 497       indexes.push_back(i);
 498   }
 499
 500   return indexes.size() - prev_size;
 501 }
 502
 503 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
 504                                              Debug symbol_debug_type,
 505                                              Visibility symbol_visibility,
 506                                              std::vector<uint32_t> &indexes,
 507                                              uint32_t start_idx,
 508                                              uint32_t end_index) const {
 509   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 510
 511   uint32_t prev_size = indexes.size();
 512
 513   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 514
 515   for (uint32_t i = start_idx; i < count; ++i) {
 516     if (symbol_type == eSymbolTypeAny ||
 517         m_symbols[i].GetType() == symbol_type) {
 518       if (CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility))
 519         indexes.push_back(i);
 520     }
 521   }
 522
 523   return indexes.size() - prev_size;
 524 }
 525
 526 uint32_t Symtab::GetIndexForSymbol(const Symbol *symbol) const {
 527   if (!m_symbols.empty()) {
 528     const Symbol *first_symbol = &m_symbols[0];
 529     if (symbol >= first_symbol && symbol < first_symbol + m_symbols.size())
 530       return symbol - first_symbol;
 531   }
 532   return UINT32_MAX;
 533 }
 534
 535 struct SymbolSortInfo {
 536   const bool sort_by_load_addr;
 537   const Symbol *symbols;
 538 };
 539
 540 namespace {
 541 struct SymbolIndexComparator {
 542   const std::vector<Symbol> &symbols;
 543   std::vector<lldb::addr_t> &addr_cache;
 544
 545   // Getting from the symbol to the Address to the File Address involves some
 546   // work.
 547   // Since there are potentially many symbols here, and we're using this for
 548   // sorting so
 549   // we're going to be computing the address many times, cache that in
 550   // addr_cache.
 551   // The array passed in has to be the same size as the symbols array passed
 552   // into the
 553   // member variable symbols, and should be initialized with
 554   // LLDB_INVALID_ADDRESS.
 555   // NOTE: You have to make addr_cache externally and pass it in because
 556   // std::stable_sort
 557   // makes copies of the comparator it is initially passed in, and you end up
 558   // spending
 559   // huge amounts of time copying this array...
 560
 561   SymbolIndexComparator(const std::vector<Symbol> &s,
 562                         std::vector<lldb::addr_t> &a)
 563       : symbols(s), addr_cache(a) {
 564     assert(symbols.size() == addr_cache.size());
 565   }
 566   bool operator()(uint32_t index_a, uint32_t index_b) {
 567     addr_t value_a = addr_cache[index_a];
 568     if (value_a == LLDB_INVALID_ADDRESS) {
 569       value_a = symbols[index_a].GetAddressRef().GetFileAddress();
 570       addr_cache[index_a] = value_a;
 571     }
 572
 573     addr_t value_b = addr_cache[index_b];
 574     if (value_b == LLDB_INVALID_ADDRESS) {
 575       value_b = symbols[index_b].GetAddressRef().GetFileAddress();
 576       addr_cache[index_b] = value_b;
 577     }
 578
 579     if (value_a == value_b) {
 580       // The if the values are equal, use the original symbol user ID
 581       lldb::user_id_t uid_a = symbols[index_a].GetID();
 582       lldb::user_id_t uid_b = symbols[index_b].GetID();
 583       if (uid_a < uid_b)
 584         return true;
 585       if (uid_a > uid_b)
 586         return false;
 587       return false;
 588     } else if (value_a < value_b)
 589       return true;
 590
 591     return false;
 592   }
 593 };
 594 }
 595
 596 void Symtab::SortSymbolIndexesByValue(std::vector<uint32_t> &indexes,
 597                                       bool remove_duplicates) const {
 598   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 599
 600   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 601   Timer scoped_timer(func_cat, LLVM_PRETTY_FUNCTION);
 602   // No need to sort if we have zero or one items...
 603   if (indexes.size() <= 1)
 604     return;
 605
 606   // Sort the indexes in place using std::stable_sort.
 607   // NOTE: The use of std::stable_sort instead of std::sort here is strictly for
 608   // performance,
 609   // not correctness.  The indexes vector tends to be "close" to sorted, which
 610   // the
 611   // stable sort handles better.
 612
 613   std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS);
 614
 615   SymbolIndexComparator comparator(m_symbols, addr_cache);
 616   std::stable_sort(indexes.begin(), indexes.end(), comparator);
 617
 618   // Remove any duplicates if requested
 619   if (remove_duplicates)
 620     std::unique(indexes.begin(), indexes.end());
 621 }
 622
 623 uint32_t Symtab::AppendSymbolIndexesWithName(const ConstString &symbol_name,
 624                                              std::vector<uint32_t> &indexes) {
 625   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 626
 627   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 628   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 629   if (symbol_name) {
 630     if (!m_name_indexes_computed)
 631       InitNameIndexes();
 632
 633     return m_name_to_index.GetValues(symbol_name, indexes);
 634   }
 635   return 0;
 636 }
 637
 638 uint32_t Symtab::AppendSymbolIndexesWithName(const ConstString &symbol_name,
 639                                              Debug symbol_debug_type,
 640                                              Visibility symbol_visibility,
 641                                              std::vector<uint32_t> &indexes) {
 642   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 643
 644   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 645   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 646   if (symbol_name) {
 647     const size_t old_size = indexes.size();
 648     if (!m_name_indexes_computed)
 649       InitNameIndexes();
 650
 651     std::vector<uint32_t> all_name_indexes;
 652     const size_t name_match_count =
 653         m_name_to_index.GetValues(symbol_name, all_name_indexes);
 654     for (size_t i = 0; i < name_match_count; ++i) {
 655       if (CheckSymbolAtIndex(all_name_indexes[i], symbol_debug_type,
 656                              symbol_visibility))
 657         indexes.push_back(all_name_indexes[i]);
 658     }
 659     return indexes.size() - old_size;
 660   }
 661   return 0;
 662 }
 663
 664 uint32_t
 665 Symtab::AppendSymbolIndexesWithNameAndType(const ConstString &symbol_name,
 666                                            SymbolType symbol_type,
 667                                            std::vector<uint32_t> &indexes) {
 668   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 669
 670   if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0) {
 671     std::vector<uint32_t>::iterator pos = indexes.begin();
 672     while (pos != indexes.end()) {
 673       if (symbol_type == eSymbolTypeAny ||
 674           m_symbols[*pos].GetType() == symbol_type)
 675         ++pos;
 676       else
 677         pos = indexes.erase(pos);
 678     }
 679   }
 680   return indexes.size();
 681 }
 682
 683 uint32_t Symtab::AppendSymbolIndexesWithNameAndType(
 684     const ConstString &symbol_name, SymbolType symbol_type,
 685     Debug symbol_debug_type, Visibility symbol_visibility,
 686     std::vector<uint32_t> &indexes) {
 687   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 688
 689   if (AppendSymbolIndexesWithName(symbol_name, symbol_debug_type,
 690                                   symbol_visibility, indexes) > 0) {
 691     std::vector<uint32_t>::iterator pos = indexes.begin();
 692     while (pos != indexes.end()) {
 693       if (symbol_type == eSymbolTypeAny ||
 694           m_symbols[*pos].GetType() == symbol_type)
 695         ++pos;
 696       else
 697         pos = indexes.erase(pos);
 698     }
 699   }
 700   return indexes.size();
 701 }
 702
 703 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
 704     const RegularExpression &regexp, SymbolType symbol_type,
 705     std::vector<uint32_t> &indexes) {
 706   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 707
 708   uint32_t prev_size = indexes.size();
 709   uint32_t sym_end = m_symbols.size();
 710
 711   for (uint32_t i = 0; i < sym_end; i++) {
 712     if (symbol_type == eSymbolTypeAny ||
 713         m_symbols[i].GetType() == symbol_type) {
 714       const char *name = m_symbols[i].GetName().AsCString();
 715       if (name) {
 716         if (regexp.Execute(name))
 717           indexes.push_back(i);
 718       }
 719     }
 720   }
 721   return indexes.size() - prev_size;
 722 }
 723
 724 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
 725     const RegularExpression &regexp, SymbolType symbol_type,
 726     Debug symbol_debug_type, Visibility symbol_visibility,
 727     std::vector<uint32_t> &indexes) {
 728   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 729
 730   uint32_t prev_size = indexes.size();
 731   uint32_t sym_end = m_symbols.size();
 732
 733   for (uint32_t i = 0; i < sym_end; i++) {
 734     if (symbol_type == eSymbolTypeAny ||
 735         m_symbols[i].GetType() == symbol_type) {
 736       if (CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility) == false)
 737         continue;
 738
 739       const char *name = m_symbols[i].GetName().AsCString();
 740       if (name) {
 741         if (regexp.Execute(name))
 742           indexes.push_back(i);
 743       }
 744     }
 745   }
 746   return indexes.size() - prev_size;
 747 }
 748
 749 Symbol *Symtab::FindSymbolWithType(SymbolType symbol_type,
 750                                    Debug symbol_debug_type,
 751                                    Visibility symbol_visibility,
 752                                    uint32_t &start_idx) {
 753   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 754
 755   const size_t count = m_symbols.size();
 756   for (size_t idx = start_idx; idx < count; ++idx) {
 757     if (symbol_type == eSymbolTypeAny ||
 758         m_symbols[idx].GetType() == symbol_type) {
 759       if (CheckSymbolAtIndex(idx, symbol_debug_type, symbol_visibility)) {
 760         start_idx = idx;
 761         return &m_symbols[idx];
 762       }
 763     }
 764   }
 765   return nullptr;
 766 }
 767
 768 size_t
 769 Symtab::FindAllSymbolsWithNameAndType(const ConstString &name,
 770                                       SymbolType symbol_type,
 771                                       std::vector<uint32_t> &symbol_indexes) {
 772   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 773
 774   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 775   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 776   // Initialize all of the lookup by name indexes before converting NAME
 777   // to a uniqued string NAME_STR below.
 778   if (!m_name_indexes_computed)
 779     InitNameIndexes();
 780
 781   if (name) {
 782     // The string table did have a string that matched, but we need
 783     // to check the symbols and match the symbol_type if any was given.
 784     AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_indexes);
 785   }
 786   return symbol_indexes.size();
 787 }
 788
 789 size_t Symtab::FindAllSymbolsWithNameAndType(
 790     const ConstString &name, SymbolType symbol_type, Debug symbol_debug_type,
 791     Visibility symbol_visibility, std::vector<uint32_t> &symbol_indexes) {
 792   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 793
 794   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 795   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 796   // Initialize all of the lookup by name indexes before converting NAME
 797   // to a uniqued string NAME_STR below.
 798   if (!m_name_indexes_computed)
 799     InitNameIndexes();
 800
 801   if (name) {
 802     // The string table did have a string that matched, but we need
 803     // to check the symbols and match the symbol_type if any was given.
 804     AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
 805                                        symbol_visibility, symbol_indexes);
 806   }
 807   return symbol_indexes.size();
 808 }
 809
 810 size_t Symtab::FindAllSymbolsMatchingRexExAndType(
 811     const RegularExpression &regex, SymbolType symbol_type,
 812     Debug symbol_debug_type, Visibility symbol_visibility,
 813     std::vector<uint32_t> &symbol_indexes) {
 814   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 815
 816   AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_debug_type,
 817                                           symbol_visibility, symbol_indexes);
 818   return symbol_indexes.size();
 819 }
 820
 821 Symbol *Symtab::FindFirstSymbolWithNameAndType(const ConstString &name,
 822                                                SymbolType symbol_type,
 823                                                Debug symbol_debug_type,
 824                                                Visibility symbol_visibility) {
 825   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 826
 827   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
 828   Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
 829   if (!m_name_indexes_computed)
 830     InitNameIndexes();
 831
 832   if (name) {
 833     std::vector<uint32_t> matching_indexes;
 834     // The string table did have a string that matched, but we need
 835     // to check the symbols and match the symbol_type if any was given.
 836     if (AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
 837                                            symbol_visibility,
 838                                            matching_indexes)) {
 839       std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end();
 840       for (pos = matching_indexes.begin(); pos != end; ++pos) {
 841         Symbol *symbol = SymbolAtIndex(*pos);
 842
 843         if (symbol->Compare(name, symbol_type))
 844           return symbol;
 845       }
 846     }
 847   }
 848   return nullptr;
 849 }
 850
 851 typedef struct {
 852   const Symtab *symtab;
 853   const addr_t file_addr;
 854   Symbol *match_symbol;
 855   const uint32_t *match_index_ptr;
 856   addr_t match_offset;
 857 } SymbolSearchInfo;
 858
 859 // Add all the section file start address & size to the RangeVector,
 860 // recusively adding any children sections.
 861 static void AddSectionsToRangeMap(SectionList *sectlist,
 862                                   RangeVector<addr_t, addr_t> &section_ranges) {
 863   const int num_sections = sectlist->GetNumSections(0);
 864   for (int i = 0; i < num_sections; i++) {
 865     SectionSP sect_sp = sectlist->GetSectionAtIndex(i);
 866     if (sect_sp) {
 867       SectionList &child_sectlist = sect_sp->GetChildren();
 868
 869       // If this section has children, add the children to the RangeVector.
 870       // Else add this section to the RangeVector.
 871       if (child_sectlist.GetNumSections(0) > 0) {
 872         AddSectionsToRangeMap(&child_sectlist, section_ranges);
 873       } else {
 874         size_t size = sect_sp->GetByteSize();
 875         if (size > 0) {
 876           addr_t base_addr = sect_sp->GetFileAddress();
 877           RangeVector<addr_t, addr_t>::Entry entry;
 878           entry.SetRangeBase(base_addr);
 879           entry.SetByteSize(size);
 880           section_ranges.Append(entry);
 881         }
 882       }
 883     }
 884   }
 885 }
 886
 887 void Symtab::InitAddressIndexes() {
 888   // Protected function, no need to lock mutex...
 889   if (!m_file_addr_to_index_computed && !m_symbols.empty()) {
 890     m_file_addr_to_index_computed = true;
 891
 892     FileRangeToIndexMap::Entry entry;
 893     const_iterator begin = m_symbols.begin();
 894     const_iterator end = m_symbols.end();
 895     for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
 896       if (pos->ValueIsAddress()) {
 897         entry.SetRangeBase(pos->GetAddressRef().GetFileAddress());
 898         entry.SetByteSize(pos->GetByteSize());
 899         entry.data = std::distance(begin, pos);
 900         m_file_addr_to_index.Append(entry);
 901       }
 902     }
 903     const size_t num_entries = m_file_addr_to_index.GetSize();
 904     if (num_entries > 0) {
 905       m_file_addr_to_index.Sort();
 906
 907       // Create a RangeVector with the start & size of all the sections for
 908       // this objfile.  We'll need to check this for any FileRangeToIndexMap
 909       // entries with an uninitialized size, which could potentially be a
 910       // large number so reconstituting the weak pointer is busywork when it
 911       // is invariant information.
 912       SectionList *sectlist = m_objfile->GetSectionList();
 913       RangeVector<addr_t, addr_t> section_ranges;
 914       if (sectlist) {
 915         AddSectionsToRangeMap(sectlist, section_ranges);
 916         section_ranges.Sort();
 917       }
 918
 919       // Iterate through the FileRangeToIndexMap and fill in the size for any
 920       // entries that didn't already have a size from the Symbol (e.g. if we
 921       // have a plain linker symbol with an address only, instead of debug info
 922       // where we get an address and a size and a type, etc.)
 923       for (size_t i = 0; i < num_entries; i++) {
 924         FileRangeToIndexMap::Entry *entry =
 925             m_file_addr_to_index.GetMutableEntryAtIndex(i);
 926         if (entry->GetByteSize() == 0) {
 927           addr_t curr_base_addr = entry->GetRangeBase();
 928           const RangeVector<addr_t, addr_t>::Entry *containing_section =
 929               section_ranges.FindEntryThatContains(curr_base_addr);
 930
 931           // Use the end of the section as the default max size of the symbol
 932           addr_t sym_size = 0;
 933           if (containing_section) {
 934             sym_size =
 935                 containing_section->GetByteSize() -
 936                 (entry->GetRangeBase() - containing_section->GetRangeBase());
 937           }
 938
 939           for (size_t j = i; j < num_entries; j++) {
 940             FileRangeToIndexMap::Entry *next_entry =
 941                 m_file_addr_to_index.GetMutableEntryAtIndex(j);
 942             addr_t next_base_addr = next_entry->GetRangeBase();
 943             if (next_base_addr > curr_base_addr) {
 944               addr_t size_to_next_symbol = next_base_addr - curr_base_addr;
 945
 946               // Take the difference between this symbol and the next one as its
 947               // size,
 948               // if it is less than the size of the section.
 949               if (sym_size == 0 || size_to_next_symbol < sym_size) {
 950                 sym_size = size_to_next_symbol;
 951               }
 952               break;
 953             }
 954           }
 955
 956           if (sym_size > 0) {
 957             entry->SetByteSize(sym_size);
 958             Symbol &symbol = m_symbols[entry->data];
 959             symbol.SetByteSize(sym_size);
 960             symbol.SetSizeIsSynthesized(true);
 961           }
 962         }
 963       }
 964
 965       // Sort again in case the range size changes the ordering
 966       m_file_addr_to_index.Sort();
 967     }
 968   }
 969 }
 970
 971 void Symtab::CalculateSymbolSizes() {
 972   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 973
 974   if (!m_symbols.empty()) {
 975     if (!m_file_addr_to_index_computed)
 976       InitAddressIndexes();
 977
 978     const size_t num_entries = m_file_addr_to_index.GetSize();
 979
 980     for (size_t i = 0; i < num_entries; ++i) {
 981       // The entries in the m_file_addr_to_index have calculated the sizes
 982       // already
 983       // so we will use this size if we need to.
 984       const FileRangeToIndexMap::Entry &entry =
 985           m_file_addr_to_index.GetEntryRef(i);
 986
 987       Symbol &symbol = m_symbols[entry.data];
 988
 989       // If the symbol size is already valid, no need to do anything
 990       if (symbol.GetByteSizeIsValid())
 991         continue;
 992
 993       const addr_t range_size = entry.GetByteSize();
 994       if (range_size > 0) {
 995         symbol.SetByteSize(range_size);
 996         symbol.SetSizeIsSynthesized(true);
 997       }
 998     }
 999   }
1000 }
1001
1002 Symbol *Symtab::FindSymbolAtFileAddress(addr_t file_addr) {
1003   std::lock_guard<std::recursive_mutex> guard(m_mutex);
1004   if (!m_file_addr_to_index_computed)
1005     InitAddressIndexes();
1006
1007   const FileRangeToIndexMap::Entry *entry =
1008       m_file_addr_to_index.FindEntryStartsAt(file_addr);
1009   if (entry) {
1010     Symbol *symbol = SymbolAtIndex(entry->data);
1011     if (symbol->GetFileAddress() == file_addr)
1012       return symbol;
1013   }
1014   return nullptr;
1015 }
1016
1017 Symbol *Symtab::FindSymbolContainingFileAddress(addr_t file_addr) {
1018   std::lock_guard<std::recursive_mutex> guard(m_mutex);
1019
1020   if (!m_file_addr_to_index_computed)
1021     InitAddressIndexes();
1022
1023   const FileRangeToIndexMap::Entry *entry =
1024       m_file_addr_to_index.FindEntryThatContains(file_addr);
1025   if (entry) {
1026     Symbol *symbol = SymbolAtIndex(entry->data);
1027     if (symbol->ContainsFileAddress(file_addr))
1028       return symbol;
1029   }
1030   return nullptr;
1031 }
1032
1033 void Symtab::ForEachSymbolContainingFileAddress(
1034     addr_t file_addr, std::function<bool(Symbol *)> const &callback) {
1035   std::lock_guard<std::recursive_mutex> guard(m_mutex);
1036
1037   if (!m_file_addr_to_index_computed)
1038     InitAddressIndexes();
1039
1040   std::vector<uint32_t> all_addr_indexes;
1041
1042   // Get all symbols with file_addr
1043   const size_t addr_match_count =
1044       m_file_addr_to_index.FindEntryIndexesThatContain(file_addr,
1045                                                        all_addr_indexes);
1046
1047   for (size_t i = 0; i < addr_match_count; ++i) {
1048     Symbol *symbol = SymbolAtIndex(all_addr_indexes[i]);
1049     if (symbol->ContainsFileAddress(file_addr)) {
1050       if (!callback(symbol))
1051         break;
1052     }
1053   }
1054 }
1055
1056 void Symtab::SymbolIndicesToSymbolContextList(
1057     std::vector<uint32_t> &symbol_indexes, SymbolContextList &sc_list) {
1058   // No need to protect this call using m_mutex all other method calls are
1059   // already thread safe.
1060
1061   const bool merge_symbol_into_function = true;
1062   size_t num_indices = symbol_indexes.size();
1063   if (num_indices > 0) {
1064     SymbolContext sc;
1065     sc.module_sp = m_objfile->GetModule();
1066     for (size_t i = 0; i < num_indices; i++) {
1067       sc.symbol = SymbolAtIndex(symbol_indexes[i]);
1068       if (sc.symbol)
1069         sc_list.AppendIfUnique(sc, merge_symbol_into_function);
1070     }
1071   }
1072 }
1073
1074 size_t Symtab::FindFunctionSymbols(const ConstString &name,
1075                                    uint32_t name_type_mask,
1076                                    SymbolContextList &sc_list) {
1077   size_t count = 0;
1078   std::vector<uint32_t> symbol_indexes;
1079
1080   // eFunctionNameTypeAuto should be pre-resolved by a call to
1081   // Module::LookupInfo::LookupInfo()
1082   assert((name_type_mask & eFunctionNameTypeAuto) == 0);
1083
1084   if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) {
1085     std::vector<uint32_t> temp_symbol_indexes;
1086     FindAllSymbolsWithNameAndType(name, eSymbolTypeAny, temp_symbol_indexes);
1087
1088     unsigned temp_symbol_indexes_size = temp_symbol_indexes.size();
1089     if (temp_symbol_indexes_size > 0) {
1090       std::lock_guard<std::recursive_mutex> guard(m_mutex);
1091       for (unsigned i = 0; i < temp_symbol_indexes_size; i++) {
1092         SymbolContext sym_ctx;
1093         sym_ctx.symbol = SymbolAtIndex(temp_symbol_indexes[i]);
1094         if (sym_ctx.symbol) {
1095           switch (sym_ctx.symbol->GetType()) {
1096           case eSymbolTypeCode:
1097           case eSymbolTypeResolver:
1098           case eSymbolTypeReExported:
1099             symbol_indexes.push_back(temp_symbol_indexes[i]);
1100             break;
1101           default:
1102             break;
1103           }
1104         }
1105       }
1106     }
1107   }
1108
1109   if (name_type_mask & eFunctionNameTypeBase) {
1110     // From mangled names we can't tell what is a basename and what
1111     // is a method name, so we just treat them the same
1112     if (!m_name_indexes_computed)
1113       InitNameIndexes();
1114
1115     if (!m_basename_to_index.IsEmpty()) {
1116       const UniqueCStringMap<uint32_t>::Entry *match;
1117       for (match = m_basename_to_index.FindFirstValueForName(name);
1118            match != nullptr;
1119            match = m_basename_to_index.FindNextValueForName(match)) {
1120         symbol_indexes.push_back(match->value);
1121       }
1122     }
1123   }
1124
1125   if (name_type_mask & eFunctionNameTypeMethod) {
1126     if (!m_name_indexes_computed)
1127       InitNameIndexes();
1128
1129     if (!m_method_to_index.IsEmpty()) {
1130       const UniqueCStringMap<uint32_t>::Entry *match;
1131       for (match = m_method_to_index.FindFirstValueForName(name);
1132            match != nullptr;
1133            match = m_method_to_index.FindNextValueForName(match)) {
1134         symbol_indexes.push_back(match->value);
1135       }
1136     }
1137   }
1138
1139   if (name_type_mask & eFunctionNameTypeSelector) {
1140     if (!m_name_indexes_computed)
1141       InitNameIndexes();
1142
1143     if (!m_selector_to_index.IsEmpty()) {
1144       const UniqueCStringMap<uint32_t>::Entry *match;
1145       for (match = m_selector_to_index.FindFirstValueForName(name);
1146            match != nullptr;
1147            match = m_selector_to_index.FindNextValueForName(match)) {
1148         symbol_indexes.push_back(match->value);
1149       }
1150     }
1151   }
1152
1153   if (!symbol_indexes.empty()) {
1154     std::sort(symbol_indexes.begin(), symbol_indexes.end());
1155     symbol_indexes.erase(
1156         std::unique(symbol_indexes.begin(), symbol_indexes.end()),
1157         symbol_indexes.end());
1158     count = symbol_indexes.size();
1159     SymbolIndicesToSymbolContextList(symbol_indexes, sc_list);
1160   }
1161
1162   return count;
1163 }
1164
1165 const Symbol *Symtab::GetParent(Symbol *child_symbol) const {
1166   uint32_t child_idx = GetIndexForSymbol(child_symbol);
1167   if (child_idx != UINT32_MAX && child_idx > 0) {
1168     for (uint32_t idx = child_idx - 1; idx != UINT32_MAX; --idx) {
1169       const Symbol *symbol = SymbolAtIndex(idx);
1170       const uint32_t sibling_idx = symbol->GetSiblingIndex();
1171       if (sibling_idx != UINT32_MAX && sibling_idx > child_idx)
1172         return symbol;
1173     }
1174   }
1175   return NULL;
1176 }