llvm-project

1
//===-- Symtab.cpp --------------------------------------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8

9
#include <map>
10
#include <set>
11

12
#include "lldb/Core/DataFileCache.h"
13
#include "lldb/Core/Module.h"
14
#include "lldb/Core/RichManglingContext.h"
15
#include "lldb/Core/Section.h"
16
#include "lldb/Symbol/ObjectFile.h"
17
#include "lldb/Symbol/Symbol.h"
18
#include "lldb/Symbol/SymbolContext.h"
19
#include "lldb/Symbol/Symtab.h"
20
#include "lldb/Target/Language.h"
21
#include "lldb/Utility/DataEncoder.h"
22
#include "lldb/Utility/Endian.h"
23
#include "lldb/Utility/RegularExpression.h"
24
#include "lldb/Utility/Stream.h"
25
#include "lldb/Utility/Timer.h"
26

27
#include "llvm/ADT/ArrayRef.h"
28
#include "llvm/ADT/StringRef.h"
29
#include "llvm/Support/DJB.h"
30

31
using namespace lldb;
32
using namespace lldb_private;
33

34
Symtab::Symtab(ObjectFile *objfile)
35
    : m_objfile(objfile), m_symbols(), m_file_addr_to_index(*this),
36
      m_name_to_symbol_indices(), m_mutex(),
37
      m_file_addr_to_index_computed(false), m_name_indexes_computed(false),
38
      m_loaded_from_cache(false), m_saved_to_cache(false) {
39
  m_name_to_symbol_indices.emplace(std::make_pair(
40
      lldb::eFunctionNameTypeNone, UniqueCStringMap<uint32_t>()));
41
  m_name_to_symbol_indices.emplace(std::make_pair(
42
      lldb::eFunctionNameTypeBase, UniqueCStringMap<uint32_t>()));
43
  m_name_to_symbol_indices.emplace(std::make_pair(
44
      lldb::eFunctionNameTypeMethod, UniqueCStringMap<uint32_t>()));
45
  m_name_to_symbol_indices.emplace(std::make_pair(
46
      lldb::eFunctionNameTypeSelector, UniqueCStringMap<uint32_t>()));
47
}
48

49
Symtab::~Symtab() = default;
50

51
void Symtab::Reserve(size_t count) {
52
  // Clients should grab the mutex from this symbol table and lock it manually
53
  // when calling this function to avoid performance issues.
54
  m_symbols.reserve(count);
55
}
56

57
Symbol *Symtab::Resize(size_t count) {
58
  // Clients should grab the mutex from this symbol table and lock it manually
59
  // when calling this function to avoid performance issues.
60
  m_symbols.resize(count);
61
  return m_symbols.empty() ? nullptr : &m_symbols[0];
62
}
63

64
uint32_t Symtab::AddSymbol(const Symbol &symbol) {
65
  // Clients should grab the mutex from this symbol table and lock it manually
66
  // when calling this function to avoid performance issues.
67
  uint32_t symbol_idx = m_symbols.size();
68
  auto &name_to_index = GetNameToSymbolIndexMap(lldb::eFunctionNameTypeNone);
69
  name_to_index.Clear();
70
  m_file_addr_to_index.Clear();
71
  m_symbols.push_back(symbol);
72
  m_file_addr_to_index_computed = false;
73
  m_name_indexes_computed = false;
74
  return symbol_idx;
75
}
76

77
size_t Symtab::GetNumSymbols() const {
78
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
79
  return m_symbols.size();
80
}
81

82
void Symtab::SectionFileAddressesChanged() {
83
  m_file_addr_to_index.Clear();
84
  m_file_addr_to_index_computed = false;
85
}
86

87
void Symtab::Dump(Stream *s, Target *target, SortOrder sort_order,
88
                  Mangled::NamePreference name_preference) {
89
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
90

91
  //    s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
92
  s->Indent();
93
  const FileSpec &file_spec = m_objfile->GetFileSpec();
94
  const char *object_name = nullptr;
95
  if (m_objfile->GetModule())
96
    object_name = m_objfile->GetModule()->GetObjectName().GetCString();
97

98
  if (file_spec)
99
    s->Printf("Symtab, file = %s%s%s%s, num_symbols = %" PRIu64,
100
              file_spec.GetPath().c_str(), object_name ? "(" : "",
101
              object_name ? object_name : "", object_name ? ")" : "",
102
              (uint64_t)m_symbols.size());
103
  else
104
    s->Printf("Symtab, num_symbols = %" PRIu64 "", (uint64_t)m_symbols.size());
105

106
  if (!m_symbols.empty()) {
107
    switch (sort_order) {
108
    case eSortOrderNone: {
109
      s->PutCString(":\n");
110
      DumpSymbolHeader(s);
111
      const_iterator begin = m_symbols.begin();
112
      const_iterator end = m_symbols.end();
113
      for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
114
        s->Indent();
115
        pos->Dump(s, target, std::distance(begin, pos), name_preference);
116
      }
117
    }
118
    break;
119

120
    case eSortOrderByName: {
121
      // Although we maintain a lookup by exact name map, the table isn't
122
      // sorted by name. So we must make the ordered symbol list up ourselves.
123
      s->PutCString(" (sorted by name):\n");
124
      DumpSymbolHeader(s);
125

126
      std::multimap<llvm::StringRef, const Symbol *> name_map;
127
      for (const Symbol &symbol : m_symbols)
128
        name_map.emplace(symbol.GetName().GetStringRef(), &symbol);
129

130
      for (const auto &name_to_symbol : name_map) {
131
        const Symbol *symbol = name_to_symbol.second;
132
        s->Indent();
133
        symbol->Dump(s, target, symbol - &m_symbols[0], name_preference);
134
      }
135
    } break;
136

137
    case eSortOrderBySize: {
138
      s->PutCString(" (sorted by size):\n");
139
      DumpSymbolHeader(s);
140

141
      std::multimap<size_t, const Symbol *, std::greater<size_t>> size_map;
142
      for (const Symbol &symbol : m_symbols)
143
        size_map.emplace(symbol.GetByteSize(), &symbol);
144

145
      size_t idx = 0;
146
      for (const auto &size_to_symbol : size_map) {
147
        const Symbol *symbol = size_to_symbol.second;
148
        s->Indent();
149
        symbol->Dump(s, target, idx++, name_preference);
150
      }
151
    } break;
152

153
    case eSortOrderByAddress:
154
      s->PutCString(" (sorted by address):\n");
155
      DumpSymbolHeader(s);
156
      if (!m_file_addr_to_index_computed)
157
        InitAddressIndexes();
158
      const size_t num_entries = m_file_addr_to_index.GetSize();
159
      for (size_t i = 0; i < num_entries; ++i) {
160
        s->Indent();
161
        const uint32_t symbol_idx = m_file_addr_to_index.GetEntryRef(i).data;
162
        m_symbols[symbol_idx].Dump(s, target, symbol_idx, name_preference);
163
      }
164
      break;
165
    }
166
  } else {
167
    s->PutCString("\n");
168
  }
169
}
170

171
void Symtab::Dump(Stream *s, Target *target, std::vector<uint32_t> &indexes,
172
                  Mangled::NamePreference name_preference) const {
173
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
174

175
  const size_t num_symbols = GetNumSymbols();
176
  // s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
177
  s->Indent();
178
  s->Printf("Symtab %" PRIu64 " symbol indexes (%" PRIu64 " symbols total):\n",
179
            (uint64_t)indexes.size(), (uint64_t)m_symbols.size());
180
  s->IndentMore();
181

182
  if (!indexes.empty()) {
183
    std::vector<uint32_t>::const_iterator pos;
184
    std::vector<uint32_t>::const_iterator end = indexes.end();
185
    DumpSymbolHeader(s);
186
    for (pos = indexes.begin(); pos != end; ++pos) {
187
      size_t idx = *pos;
188
      if (idx < num_symbols) {
189
        s->Indent();
190
        m_symbols[idx].Dump(s, target, idx, name_preference);
191
      }
192
    }
193
  }
194
  s->IndentLess();
195
}
196

197
void Symtab::DumpSymbolHeader(Stream *s) {
198
  s->Indent("               Debug symbol\n");
199
  s->Indent("               |Synthetic symbol\n");
200
  s->Indent("               ||Externally Visible\n");
201
  s->Indent("               |||\n");
202
  s->Indent("Index   UserID DSX Type            File Address/Value Load "
203
            "Address       Size               Flags      Name\n");
204
  s->Indent("------- ------ --- --------------- ------------------ "
205
            "------------------ ------------------ ---------- "
206
            "----------------------------------\n");
207
}
208

209
static int CompareSymbolID(const void *key, const void *p) {
210
  const user_id_t match_uid = *(const user_id_t *)key;
211
  const user_id_t symbol_uid = ((const Symbol *)p)->GetID();
212
  if (match_uid < symbol_uid)
213
    return -1;
214
  if (match_uid > symbol_uid)
215
    return 1;
216
  return 0;
217
}
218

219
Symbol *Symtab::FindSymbolByID(lldb::user_id_t symbol_uid) const {
220
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
221

222
  Symbol *symbol =
223
      (Symbol *)::bsearch(&symbol_uid, &m_symbols[0], m_symbols.size(),
224
                          sizeof(m_symbols[0]), CompareSymbolID);
225
  return symbol;
226
}
227

228
Symbol *Symtab::SymbolAtIndex(size_t idx) {
229
  // Clients should grab the mutex from this symbol table and lock it manually
230
  // when calling this function to avoid performance issues.
231
  if (idx < m_symbols.size())
232
    return &m_symbols[idx];
233
  return nullptr;
234
}
235

236
const Symbol *Symtab::SymbolAtIndex(size_t idx) const {
237
  // Clients should grab the mutex from this symbol table and lock it manually
238
  // when calling this function to avoid performance issues.
239
  if (idx < m_symbols.size())
240
    return &m_symbols[idx];
241
  return nullptr;
242
}
243

244
static bool lldb_skip_name(llvm::StringRef mangled,
245
                           Mangled::ManglingScheme scheme) {
246
  switch (scheme) {
247
  case Mangled::eManglingSchemeItanium: {
248
    if (mangled.size() < 3 || !mangled.starts_with("_Z"))
249
      return true;
250

251
    // Avoid the following types of symbols in the index.
252
    switch (mangled[2]) {
253
    case 'G': // guard variables
254
    case 'T': // virtual tables, VTT structures, typeinfo structures + names
255
    case 'Z': // named local entities (if we eventually handle
256
              // eSymbolTypeData, we will want this back)
257
      return true;
258

259
    default:
260
      break;
261
    }
262

263
    // Include this name in the index.
264
    return false;
265
  }
266

267
  // No filters for this scheme yet. Include all names in indexing.
268
  case Mangled::eManglingSchemeMSVC:
269
  case Mangled::eManglingSchemeRustV0:
270
  case Mangled::eManglingSchemeD:
271
  case Mangled::eManglingSchemeSwift:
272
    return false;
273

274
  // Don't try and demangle things we can't categorize.
275
  case Mangled::eManglingSchemeNone:
276
    return true;
277
  }
278
  llvm_unreachable("unknown scheme!");
279
}
280

281
void Symtab::InitNameIndexes() {
282
  // Protected function, no need to lock mutex...
283
  if (!m_name_indexes_computed) {
284
    m_name_indexes_computed = true;
285
    ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabIndexTime());
286
    LLDB_SCOPED_TIMER();
287

288
    // Collect all loaded language plugins.
289
    std::vector<Language *> languages;
290
    Language::ForEach([&languages](Language *l) {
291
      languages.push_back(l);
292
      return true;
293
    });
294

295
    auto &name_to_index = GetNameToSymbolIndexMap(lldb::eFunctionNameTypeNone);
296
    auto &basename_to_index =
297
        GetNameToSymbolIndexMap(lldb::eFunctionNameTypeBase);
298
    auto &method_to_index =
299
        GetNameToSymbolIndexMap(lldb::eFunctionNameTypeMethod);
300
    auto &selector_to_index =
301
        GetNameToSymbolIndexMap(lldb::eFunctionNameTypeSelector);
302
    // Create the name index vector to be able to quickly search by name
303
    const size_t num_symbols = m_symbols.size();
304
    name_to_index.Reserve(num_symbols);
305

306
    // The "const char *" in "class_contexts" and backlog::value_type::second
307
    // must come from a ConstString::GetCString()
308
    std::set<const char *> class_contexts;
309
    std::vector<std::pair<NameToIndexMap::Entry, const char *>> backlog;
310
    backlog.reserve(num_symbols / 2);
311

312
    // Instantiation of the demangler is expensive, so better use a single one
313
    // for all entries during batch processing.
314
    RichManglingContext rmc;
315
    for (uint32_t value = 0; value < num_symbols; ++value) {
316
      Symbol *symbol = &m_symbols[value];
317

318
      // Don't let trampolines get into the lookup by name map If we ever need
319
      // the trampoline symbols to be searchable by name we can remove this and
320
      // then possibly add a new bool to any of the Symtab functions that
321
      // lookup symbols by name to indicate if they want trampolines. We also
322
      // don't want any synthetic symbols with auto generated names in the
323
      // name lookups.
324
      if (symbol->IsTrampoline() || symbol->IsSyntheticWithAutoGeneratedName())
325
        continue;
326

327
      // If the symbol's name string matched a Mangled::ManglingScheme, it is
328
      // stored in the mangled field.
329
      Mangled &mangled = symbol->GetMangled();
330
      if (ConstString name = mangled.GetMangledName()) {
331
        name_to_index.Append(name, value);
332

333
        if (symbol->ContainsLinkerAnnotations()) {
334
          // If the symbol has linker annotations, also add the version without
335
          // the annotations.
336
          ConstString stripped = ConstString(
337
              m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
338
          name_to_index.Append(stripped, value);
339
        }
340

341
        const SymbolType type = symbol->GetType();
342
        if (type == eSymbolTypeCode || type == eSymbolTypeResolver) {
343
          if (mangled.GetRichManglingInfo(rmc, lldb_skip_name)) {
344
            RegisterMangledNameEntry(value, class_contexts, backlog, rmc);
345
            continue;
346
          }
347
        }
348
      }
349

350
      // Symbol name strings that didn't match a Mangled::ManglingScheme, are
351
      // stored in the demangled field.
352
      if (ConstString name = mangled.GetDemangledName()) {
353
        name_to_index.Append(name, value);
354

355
        if (symbol->ContainsLinkerAnnotations()) {
356
          // If the symbol has linker annotations, also add the version without
357
          // the annotations.
358
          name = ConstString(
359
              m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
360
          name_to_index.Append(name, value);
361
        }
362

363
        // If the demangled name turns out to be an ObjC name, and is a category
364
        // name, add the version without categories to the index too.
365
        for (Language *lang : languages) {
366
          for (auto variant : lang->GetMethodNameVariants(name)) {
367
            if (variant.GetType() & lldb::eFunctionNameTypeSelector)
368
              selector_to_index.Append(variant.GetName(), value);
369
            else if (variant.GetType() & lldb::eFunctionNameTypeFull)
370
              name_to_index.Append(variant.GetName(), value);
371
            else if (variant.GetType() & lldb::eFunctionNameTypeMethod)
372
              method_to_index.Append(variant.GetName(), value);
373
            else if (variant.GetType() & lldb::eFunctionNameTypeBase)
374
              basename_to_index.Append(variant.GetName(), value);
375
          }
376
        }
377
      }
378
    }
379

380
    for (const auto &record : backlog) {
381
      RegisterBacklogEntry(record.first, record.second, class_contexts);
382
    }
383

384
    name_to_index.Sort();
385
    name_to_index.SizeToFit();
386
    selector_to_index.Sort();
387
    selector_to_index.SizeToFit();
388
    basename_to_index.Sort();
389
    basename_to_index.SizeToFit();
390
    method_to_index.Sort();
391
    method_to_index.SizeToFit();
392
  }
393
}
394

395
void Symtab::RegisterMangledNameEntry(
396
    uint32_t value, std::set<const char *> &class_contexts,
397
    std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog,
398
    RichManglingContext &rmc) {
399
  // Only register functions that have a base name.
400
  llvm::StringRef base_name = rmc.ParseFunctionBaseName();
401
  if (base_name.empty())
402
    return;
403

404
  // The base name will be our entry's name.
405
  NameToIndexMap::Entry entry(ConstString(base_name), value);
406
  llvm::StringRef decl_context = rmc.ParseFunctionDeclContextName();
407

408
  // Register functions with no context.
409
  if (decl_context.empty()) {
410
    // This has to be a basename
411
    auto &basename_to_index =
412
        GetNameToSymbolIndexMap(lldb::eFunctionNameTypeBase);
413
    basename_to_index.Append(entry);
414
    // If there is no context (no namespaces or class scopes that come before
415
    // the function name) then this also could be a fullname.
416
    auto &name_to_index = GetNameToSymbolIndexMap(lldb::eFunctionNameTypeNone);
417
    name_to_index.Append(entry);
418
    return;
419
  }
420

421
  // Make sure we have a pool-string pointer and see if we already know the
422
  // context name.
423
  const char *decl_context_ccstr = ConstString(decl_context).GetCString();
424
  auto it = class_contexts.find(decl_context_ccstr);
425

426
  auto &method_to_index =
427
      GetNameToSymbolIndexMap(lldb::eFunctionNameTypeMethod);
428
  // Register constructors and destructors. They are methods and create
429
  // declaration contexts.
430
  if (rmc.IsCtorOrDtor()) {
431
    method_to_index.Append(entry);
432
    if (it == class_contexts.end())
433
      class_contexts.insert(it, decl_context_ccstr);
434
    return;
435
  }
436

437
  // Register regular methods with a known declaration context.
438
  if (it != class_contexts.end()) {
439
    method_to_index.Append(entry);
440
    return;
441
  }
442

443
  // Regular methods in unknown declaration contexts are put to the backlog. We
444
  // will revisit them once we processed all remaining symbols.
445
  backlog.push_back(std::make_pair(entry, decl_context_ccstr));
446
}
447

448
void Symtab::RegisterBacklogEntry(
449
    const NameToIndexMap::Entry &entry, const char *decl_context,
450
    const std::set<const char *> &class_contexts) {
451
  auto &method_to_index =
452
      GetNameToSymbolIndexMap(lldb::eFunctionNameTypeMethod);
453
  auto it = class_contexts.find(decl_context);
454
  if (it != class_contexts.end()) {
455
    method_to_index.Append(entry);
456
  } else {
457
    // If we got here, we have something that had a context (was inside
458
    // a namespace or class) yet we don't know the entry
459
    method_to_index.Append(entry);
460
    auto &basename_to_index =
461
        GetNameToSymbolIndexMap(lldb::eFunctionNameTypeBase);
462
    basename_to_index.Append(entry);
463
  }
464
}
465

466
void Symtab::PreloadSymbols() {
467
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
468
  InitNameIndexes();
469
}
470

471
void Symtab::AppendSymbolNamesToMap(const IndexCollection &indexes,
472
                                    bool add_demangled, bool add_mangled,
473
                                    NameToIndexMap &name_to_index_map) const {
474
  LLDB_SCOPED_TIMER();
475
  if (add_demangled || add_mangled) {
476
    std::lock_guard<std::recursive_mutex> guard(m_mutex);
477

478
    // Create the name index vector to be able to quickly search by name
479
    const size_t num_indexes = indexes.size();
480
    for (size_t i = 0; i < num_indexes; ++i) {
481
      uint32_t value = indexes[i];
482
      assert(i < m_symbols.size());
483
      const Symbol *symbol = &m_symbols[value];
484

485
      const Mangled &mangled = symbol->GetMangled();
486
      if (add_demangled) {
487
        if (ConstString name = mangled.GetDemangledName())
488
          name_to_index_map.Append(name, value);
489
      }
490

491
      if (add_mangled) {
492
        if (ConstString name = mangled.GetMangledName())
493
          name_to_index_map.Append(name, value);
494
      }
495
    }
496
  }
497
}
498

499
uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
500
                                             std::vector<uint32_t> &indexes,
501
                                             uint32_t start_idx,
502
                                             uint32_t end_index) const {
503
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
504

505
  uint32_t prev_size = indexes.size();
506

507
  const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
508

509
  for (uint32_t i = start_idx; i < count; ++i) {
510
    if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type)
511
      indexes.push_back(i);
512
  }
513

514
  return indexes.size() - prev_size;
515
}
516

517
uint32_t Symtab::AppendSymbolIndexesWithTypeAndFlagsValue(
518
    SymbolType symbol_type, uint32_t flags_value,
519
    std::vector<uint32_t> &indexes, uint32_t start_idx,
520
    uint32_t end_index) const {
521
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
522

523
  uint32_t prev_size = indexes.size();
524

525
  const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
526

527
  for (uint32_t i = start_idx; i < count; ++i) {
528
    if ((symbol_type == eSymbolTypeAny ||
529
         m_symbols[i].GetType() == symbol_type) &&
530
        m_symbols[i].GetFlags() == flags_value)
531
      indexes.push_back(i);
532
  }
533

534
  return indexes.size() - prev_size;
535
}
536

537
uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
538
                                             Debug symbol_debug_type,
539
                                             Visibility symbol_visibility,
540
                                             std::vector<uint32_t> &indexes,
541
                                             uint32_t start_idx,
542
                                             uint32_t end_index) const {
543
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
544

545
  uint32_t prev_size = indexes.size();
546

547
  const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
548

549
  for (uint32_t i = start_idx; i < count; ++i) {
550
    if (symbol_type == eSymbolTypeAny ||
551
        m_symbols[i].GetType() == symbol_type) {
552
      if (CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility))
553
        indexes.push_back(i);
554
    }
555
  }
556

557
  return indexes.size() - prev_size;
558
}
559

560
uint32_t Symtab::GetIndexForSymbol(const Symbol *symbol) const {
561
  if (!m_symbols.empty()) {
562
    const Symbol *first_symbol = &m_symbols[0];
563
    if (symbol >= first_symbol && symbol < first_symbol + m_symbols.size())
564
      return symbol - first_symbol;
565
  }
566
  return UINT32_MAX;
567
}
568

569
struct SymbolSortInfo {
570
  const bool sort_by_load_addr;
571
  const Symbol *symbols;
572
};
573

574
namespace {
575
struct SymbolIndexComparator {
576
  const std::vector<Symbol> &symbols;
577
  std::vector<lldb::addr_t> &addr_cache;
578

579
  // Getting from the symbol to the Address to the File Address involves some
580
  // work. Since there are potentially many symbols here, and we're using this
581
  // for sorting so we're going to be computing the address many times, cache
582
  // that in addr_cache. The array passed in has to be the same size as the
583
  // symbols array passed into the member variable symbols, and should be
584
  // initialized with LLDB_INVALID_ADDRESS.
585
  // NOTE: You have to make addr_cache externally and pass it in because
586
  // std::stable_sort
587
  // makes copies of the comparator it is initially passed in, and you end up
588
  // spending huge amounts of time copying this array...
589

590
  SymbolIndexComparator(const std::vector<Symbol> &s,
591
                        std::vector<lldb::addr_t> &a)
592
      : symbols(s), addr_cache(a) {
593
    assert(symbols.size() == addr_cache.size());
594
  }
595
  bool operator()(uint32_t index_a, uint32_t index_b) {
596
    addr_t value_a = addr_cache[index_a];
597
    if (value_a == LLDB_INVALID_ADDRESS) {
598
      value_a = symbols[index_a].GetAddressRef().GetFileAddress();
599
      addr_cache[index_a] = value_a;
600
    }
601

602
    addr_t value_b = addr_cache[index_b];
603
    if (value_b == LLDB_INVALID_ADDRESS) {
604
      value_b = symbols[index_b].GetAddressRef().GetFileAddress();
605
      addr_cache[index_b] = value_b;
606
    }
607

608
    if (value_a == value_b) {
609
      // The if the values are equal, use the original symbol user ID
610
      lldb::user_id_t uid_a = symbols[index_a].GetID();
611
      lldb::user_id_t uid_b = symbols[index_b].GetID();
612
      if (uid_a < uid_b)
613
        return true;
614
      if (uid_a > uid_b)
615
        return false;
616
      return false;
617
    } else if (value_a < value_b)
618
      return true;
619

620
    return false;
621
  }
622
};
623
}
624

625
void Symtab::SortSymbolIndexesByValue(std::vector<uint32_t> &indexes,
626
                                      bool remove_duplicates) const {
627
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
628
  LLDB_SCOPED_TIMER();
629
  // No need to sort if we have zero or one items...
630
  if (indexes.size() <= 1)
631
    return;
632

633
  // Sort the indexes in place using std::stable_sort.
634
  // NOTE: The use of std::stable_sort instead of llvm::sort here is strictly
635
  // for performance, not correctness.  The indexes vector tends to be "close"
636
  // to sorted, which the stable sort handles better.
637

638
  std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS);
639

640
  SymbolIndexComparator comparator(m_symbols, addr_cache);
641
  std::stable_sort(indexes.begin(), indexes.end(), comparator);
642

643
  // Remove any duplicates if requested
644
  if (remove_duplicates) {
645
    auto last = std::unique(indexes.begin(), indexes.end());
646
    indexes.erase(last, indexes.end());
647
  }
648
}
649

650
uint32_t Symtab::GetNameIndexes(ConstString symbol_name,
651
                                std::vector<uint32_t> &indexes) {
652
  auto &name_to_index = GetNameToSymbolIndexMap(lldb::eFunctionNameTypeNone);
653
  const uint32_t count = name_to_index.GetValues(symbol_name, indexes);
654
  if (count)
655
    return count;
656
  // Synthetic symbol names are not added to the name indexes, but they start
657
  // with a prefix and end with a the symbol UserID. This allows users to find
658
  // these symbols without having to add them to the name indexes. These
659
  // queries will not happen very often since the names don't mean anything, so
660
  // performance is not paramount in this case.
661
  llvm::StringRef name = symbol_name.GetStringRef();
662
  // String the synthetic prefix if the name starts with it.
663
  if (!name.consume_front(Symbol::GetSyntheticSymbolPrefix()))
664
    return 0; // Not a synthetic symbol name
665

666
  // Extract the user ID from the symbol name
667
  unsigned long long uid = 0;
668
  if (getAsUnsignedInteger(name, /*Radix=*/10, uid))
669
    return 0; // Failed to extract the user ID as an integer
670
  Symbol *symbol = FindSymbolByID(uid);
671
  if (symbol == nullptr)
672
    return 0;
673
  const uint32_t symbol_idx = GetIndexForSymbol(symbol);
674
  if (symbol_idx == UINT32_MAX)
675
    return 0;
676
  indexes.push_back(symbol_idx);
677
  return 1;
678
}
679

680
uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name,
681
                                             std::vector<uint32_t> &indexes) {
682
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
683

684
  if (symbol_name) {
685
    if (!m_name_indexes_computed)
686
      InitNameIndexes();
687

688
    return GetNameIndexes(symbol_name, indexes);
689
  }
690
  return 0;
691
}
692

693
uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name,
694
                                             Debug symbol_debug_type,
695
                                             Visibility symbol_visibility,
696
                                             std::vector<uint32_t> &indexes) {
697
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
698

699
  LLDB_SCOPED_TIMER();
700
  if (symbol_name) {
701
    const size_t old_size = indexes.size();
702
    if (!m_name_indexes_computed)
703
      InitNameIndexes();
704

705
    std::vector<uint32_t> all_name_indexes;
706
    const size_t name_match_count =
707
        GetNameIndexes(symbol_name, all_name_indexes);
708
    for (size_t i = 0; i < name_match_count; ++i) {
709
      if (CheckSymbolAtIndex(all_name_indexes[i], symbol_debug_type,
710
                             symbol_visibility))
711
        indexes.push_back(all_name_indexes[i]);
712
    }
713
    return indexes.size() - old_size;
714
  }
715
  return 0;
716
}
717

718
uint32_t
719
Symtab::AppendSymbolIndexesWithNameAndType(ConstString symbol_name,
720
                                           SymbolType symbol_type,
721
                                           std::vector<uint32_t> &indexes) {
722
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
723

724
  if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0) {
725
    std::vector<uint32_t>::iterator pos = indexes.begin();
726
    while (pos != indexes.end()) {
727
      if (symbol_type == eSymbolTypeAny ||
728
          m_symbols[*pos].GetType() == symbol_type)
729
        ++pos;
730
      else
731
        pos = indexes.erase(pos);
732
    }
733
  }
734
  return indexes.size();
735
}
736

737
uint32_t Symtab::AppendSymbolIndexesWithNameAndType(
738
    ConstString symbol_name, SymbolType symbol_type,
739
    Debug symbol_debug_type, Visibility symbol_visibility,
740
    std::vector<uint32_t> &indexes) {
741
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
742

743
  if (AppendSymbolIndexesWithName(symbol_name, symbol_debug_type,
744
                                  symbol_visibility, indexes) > 0) {
745
    std::vector<uint32_t>::iterator pos = indexes.begin();
746
    while (pos != indexes.end()) {
747
      if (symbol_type == eSymbolTypeAny ||
748
          m_symbols[*pos].GetType() == symbol_type)
749
        ++pos;
750
      else
751
        pos = indexes.erase(pos);
752
    }
753
  }
754
  return indexes.size();
755
}
756

757
uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
758
    const RegularExpression &regexp, SymbolType symbol_type,
759
    std::vector<uint32_t> &indexes, Mangled::NamePreference name_preference) {
760
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
761

762
  uint32_t prev_size = indexes.size();
763
  uint32_t sym_end = m_symbols.size();
764

765
  for (uint32_t i = 0; i < sym_end; i++) {
766
    if (symbol_type == eSymbolTypeAny ||
767
        m_symbols[i].GetType() == symbol_type) {
768
      const char *name =
769
          m_symbols[i].GetMangled().GetName(name_preference).AsCString();
770
      if (name) {
771
        if (regexp.Execute(name))
772
          indexes.push_back(i);
773
      }
774
    }
775
  }
776
  return indexes.size() - prev_size;
777
}
778

779
uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
780
    const RegularExpression &regexp, SymbolType symbol_type,
781
    Debug symbol_debug_type, Visibility symbol_visibility,
782
    std::vector<uint32_t> &indexes, Mangled::NamePreference name_preference) {
783
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
784

785
  uint32_t prev_size = indexes.size();
786
  uint32_t sym_end = m_symbols.size();
787

788
  for (uint32_t i = 0; i < sym_end; i++) {
789
    if (symbol_type == eSymbolTypeAny ||
790
        m_symbols[i].GetType() == symbol_type) {
791
      if (!CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility))
792
        continue;
793

794
      const char *name =
795
          m_symbols[i].GetMangled().GetName(name_preference).AsCString();
796
      if (name) {
797
        if (regexp.Execute(name))
798
          indexes.push_back(i);
799
      }
800
    }
801
  }
802
  return indexes.size() - prev_size;
803
}
804

805
Symbol *Symtab::FindSymbolWithType(SymbolType symbol_type,
806
                                   Debug symbol_debug_type,
807
                                   Visibility symbol_visibility,
808
                                   uint32_t &start_idx) {
809
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
810

811
  const size_t count = m_symbols.size();
812
  for (size_t idx = start_idx; idx < count; ++idx) {
813
    if (symbol_type == eSymbolTypeAny ||
814
        m_symbols[idx].GetType() == symbol_type) {
815
      if (CheckSymbolAtIndex(idx, symbol_debug_type, symbol_visibility)) {
816
        start_idx = idx;
817
        return &m_symbols[idx];
818
      }
819
    }
820
  }
821
  return nullptr;
822
}
823

824
void
825
Symtab::FindAllSymbolsWithNameAndType(ConstString name,
826
                                      SymbolType symbol_type,
827
                                      std::vector<uint32_t> &symbol_indexes) {
828
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
829

830
  // Initialize all of the lookup by name indexes before converting NAME to a
831
  // uniqued string NAME_STR below.
832
  if (!m_name_indexes_computed)
833
    InitNameIndexes();
834

835
  if (name) {
836
    // The string table did have a string that matched, but we need to check
837
    // the symbols and match the symbol_type if any was given.
838
    AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_indexes);
839
  }
840
}
841

842
void Symtab::FindAllSymbolsWithNameAndType(
843
    ConstString name, SymbolType symbol_type, Debug symbol_debug_type,
844
    Visibility symbol_visibility, std::vector<uint32_t> &symbol_indexes) {
845
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
846

847
  LLDB_SCOPED_TIMER();
848
  // Initialize all of the lookup by name indexes before converting NAME to a
849
  // uniqued string NAME_STR below.
850
  if (!m_name_indexes_computed)
851
    InitNameIndexes();
852

853
  if (name) {
854
    // The string table did have a string that matched, but we need to check
855
    // the symbols and match the symbol_type if any was given.
856
    AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
857
                                       symbol_visibility, symbol_indexes);
858
  }
859
}
860

861
void Symtab::FindAllSymbolsMatchingRexExAndType(
862
    const RegularExpression &regex, SymbolType symbol_type,
863
    Debug symbol_debug_type, Visibility symbol_visibility,
864
    std::vector<uint32_t> &symbol_indexes,
865
    Mangled::NamePreference name_preference) {
866
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
867

868
  AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_debug_type,
869
                                          symbol_visibility, symbol_indexes,
870
                                          name_preference);
871
}
872

873
Symbol *Symtab::FindFirstSymbolWithNameAndType(ConstString name,
874
                                               SymbolType symbol_type,
875
                                               Debug symbol_debug_type,
876
                                               Visibility symbol_visibility) {
877
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
878
  LLDB_SCOPED_TIMER();
879
  if (!m_name_indexes_computed)
880
    InitNameIndexes();
881

882
  if (name) {
883
    std::vector<uint32_t> matching_indexes;
884
    // The string table did have a string that matched, but we need to check
885
    // the symbols and match the symbol_type if any was given.
886
    if (AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
887
                                           symbol_visibility,
888
                                           matching_indexes)) {
889
      std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end();
890
      for (pos = matching_indexes.begin(); pos != end; ++pos) {
891
        Symbol *symbol = SymbolAtIndex(*pos);
892

893
        if (symbol->Compare(name, symbol_type))
894
          return symbol;
895
      }
896
    }
897
  }
898
  return nullptr;
899
}
900

901
typedef struct {
902
  const Symtab *symtab;
903
  const addr_t file_addr;
904
  Symbol *match_symbol;
905
  const uint32_t *match_index_ptr;
906
  addr_t match_offset;
907
} SymbolSearchInfo;
908

909
// Add all the section file start address & size to the RangeVector, recusively
910
// adding any children sections.
911
static void AddSectionsToRangeMap(SectionList *sectlist,
912
                                  RangeVector<addr_t, addr_t> &section_ranges) {
913
  const int num_sections = sectlist->GetNumSections(0);
914
  for (int i = 0; i < num_sections; i++) {
915
    SectionSP sect_sp = sectlist->GetSectionAtIndex(i);
916
    if (sect_sp) {
917
      SectionList &child_sectlist = sect_sp->GetChildren();
918

919
      // If this section has children, add the children to the RangeVector.
920
      // Else add this section to the RangeVector.
921
      if (child_sectlist.GetNumSections(0) > 0) {
922
        AddSectionsToRangeMap(&child_sectlist, section_ranges);
923
      } else {
924
        size_t size = sect_sp->GetByteSize();
925
        if (size > 0) {
926
          addr_t base_addr = sect_sp->GetFileAddress();
927
          RangeVector<addr_t, addr_t>::Entry entry;
928
          entry.SetRangeBase(base_addr);
929
          entry.SetByteSize(size);
930
          section_ranges.Append(entry);
931
        }
932
      }
933
    }
934
  }
935
}
936

937
void Symtab::InitAddressIndexes() {
938
  // Protected function, no need to lock mutex...
939
  if (!m_file_addr_to_index_computed && !m_symbols.empty()) {
940
    m_file_addr_to_index_computed = true;
941

942
    FileRangeToIndexMap::Entry entry;
943
    const_iterator begin = m_symbols.begin();
944
    const_iterator end = m_symbols.end();
945
    for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
946
      if (pos->ValueIsAddress()) {
947
        entry.SetRangeBase(pos->GetAddressRef().GetFileAddress());
948
        entry.SetByteSize(pos->GetByteSize());
949
        entry.data = std::distance(begin, pos);
950
        m_file_addr_to_index.Append(entry);
951
      }
952
    }
953
    const size_t num_entries = m_file_addr_to_index.GetSize();
954
    if (num_entries > 0) {
955
      m_file_addr_to_index.Sort();
956

957
      // Create a RangeVector with the start & size of all the sections for
958
      // this objfile.  We'll need to check this for any FileRangeToIndexMap
959
      // entries with an uninitialized size, which could potentially be a large
960
      // number so reconstituting the weak pointer is busywork when it is
961
      // invariant information.
962
      SectionList *sectlist = m_objfile->GetSectionList();
963
      RangeVector<addr_t, addr_t> section_ranges;
964
      if (sectlist) {
965
        AddSectionsToRangeMap(sectlist, section_ranges);
966
        section_ranges.Sort();
967
      }
968

969
      // Iterate through the FileRangeToIndexMap and fill in the size for any
970
      // entries that didn't already have a size from the Symbol (e.g. if we
971
      // have a plain linker symbol with an address only, instead of debug info
972
      // where we get an address and a size and a type, etc.)
973
      for (size_t i = 0; i < num_entries; i++) {
974
        FileRangeToIndexMap::Entry *entry =
975
            m_file_addr_to_index.GetMutableEntryAtIndex(i);
976
        if (entry->GetByteSize() == 0) {
977
          addr_t curr_base_addr = entry->GetRangeBase();
978
          const RangeVector<addr_t, addr_t>::Entry *containing_section =
979
              section_ranges.FindEntryThatContains(curr_base_addr);
980

981
          // Use the end of the section as the default max size of the symbol
982
          addr_t sym_size = 0;
983
          if (containing_section) {
984
            sym_size =
985
                containing_section->GetByteSize() -
986
                (entry->GetRangeBase() - containing_section->GetRangeBase());
987
          }
988

989
          for (size_t j = i; j < num_entries; j++) {
990
            FileRangeToIndexMap::Entry *next_entry =
991
                m_file_addr_to_index.GetMutableEntryAtIndex(j);
992
            addr_t next_base_addr = next_entry->GetRangeBase();
993
            if (next_base_addr > curr_base_addr) {
994
              addr_t size_to_next_symbol = next_base_addr - curr_base_addr;
995

996
              // Take the difference between this symbol and the next one as
997
              // its size, if it is less than the size of the section.
998
              if (sym_size == 0 || size_to_next_symbol < sym_size) {
999
                sym_size = size_to_next_symbol;
1000
              }
1001
              break;
1002
            }
1003
          }
1004

1005
          if (sym_size > 0) {
1006
            entry->SetByteSize(sym_size);
1007
            Symbol &symbol = m_symbols[entry->data];
1008
            symbol.SetByteSize(sym_size);
1009
            symbol.SetSizeIsSynthesized(true);
1010
          }
1011
        }
1012
      }
1013

1014
      // Sort again in case the range size changes the ordering
1015
      m_file_addr_to_index.Sort();
1016
    }
1017
  }
1018
}
1019

1020
void Symtab::Finalize() {
1021
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
1022
  // Calculate the size of symbols inside InitAddressIndexes.
1023
  InitAddressIndexes();
1024
  // Shrink to fit the symbols so we don't waste memory
1025
  m_symbols.shrink_to_fit();
1026
  SaveToCache();
1027
}
1028

1029
Symbol *Symtab::FindSymbolAtFileAddress(addr_t file_addr) {
1030
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
1031
  if (!m_file_addr_to_index_computed)
1032
    InitAddressIndexes();
1033

1034
  const FileRangeToIndexMap::Entry *entry =
1035
      m_file_addr_to_index.FindEntryStartsAt(file_addr);
1036
  if (entry) {
1037
    Symbol *symbol = SymbolAtIndex(entry->data);
1038
    if (symbol->GetFileAddress() == file_addr)
1039
      return symbol;
1040
  }
1041
  return nullptr;
1042
}
1043

1044
Symbol *Symtab::FindSymbolContainingFileAddress(addr_t file_addr) {
1045
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
1046

1047
  if (!m_file_addr_to_index_computed)
1048
    InitAddressIndexes();
1049

1050
  const FileRangeToIndexMap::Entry *entry =
1051
      m_file_addr_to_index.FindEntryThatContains(file_addr);
1052
  if (entry) {
1053
    Symbol *symbol = SymbolAtIndex(entry->data);
1054
    if (symbol->ContainsFileAddress(file_addr))
1055
      return symbol;
1056
  }
1057
  return nullptr;
1058
}
1059

1060
void Symtab::ForEachSymbolContainingFileAddress(
1061
    addr_t file_addr, std::function<bool(Symbol *)> const &callback) {
1062
  std::lock_guard<std::recursive_mutex> guard(m_mutex);
1063

1064
  if (!m_file_addr_to_index_computed)
1065
    InitAddressIndexes();
1066

1067
  std::vector<uint32_t> all_addr_indexes;
1068

1069
  // Get all symbols with file_addr
1070
  const size_t addr_match_count =
1071
      m_file_addr_to_index.FindEntryIndexesThatContain(file_addr,
1072
                                                       all_addr_indexes);
1073

1074
  for (size_t i = 0; i < addr_match_count; ++i) {
1075
    Symbol *symbol = SymbolAtIndex(all_addr_indexes[i]);
1076
    if (symbol->ContainsFileAddress(file_addr)) {
1077
      if (!callback(symbol))
1078
        break;
1079
    }
1080
  }
1081
}
1082

1083
void Symtab::SymbolIndicesToSymbolContextList(
1084
    std::vector<uint32_t> &symbol_indexes, SymbolContextList &sc_list) {
1085
  // No need to protect this call using m_mutex all other method calls are
1086
  // already thread safe.
1087

1088
  const bool merge_symbol_into_function = true;
1089
  size_t num_indices = symbol_indexes.size();
1090
  if (num_indices > 0) {
1091
    SymbolContext sc;
1092
    sc.module_sp = m_objfile->GetModule();
1093
    for (size_t i = 0; i < num_indices; i++) {
1094
      sc.symbol = SymbolAtIndex(symbol_indexes[i]);
1095
      if (sc.symbol)
1096
        sc_list.AppendIfUnique(sc, merge_symbol_into_function);
1097
    }
1098
  }
1099
}
1100

1101
void Symtab::FindFunctionSymbols(ConstString name, uint32_t name_type_mask,
1102
                                 SymbolContextList &sc_list) {
1103
  std::vector<uint32_t> symbol_indexes;
1104

1105
  // eFunctionNameTypeAuto should be pre-resolved by a call to
1106
  // Module::LookupInfo::LookupInfo()
1107
  assert((name_type_mask & eFunctionNameTypeAuto) == 0);
1108

1109
  if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) {
1110
    std::vector<uint32_t> temp_symbol_indexes;
1111
    FindAllSymbolsWithNameAndType(name, eSymbolTypeAny, temp_symbol_indexes);
1112

1113
    unsigned temp_symbol_indexes_size = temp_symbol_indexes.size();
1114
    if (temp_symbol_indexes_size > 0) {
1115
      std::lock_guard<std::recursive_mutex> guard(m_mutex);
1116
      for (unsigned i = 0; i < temp_symbol_indexes_size; i++) {
1117
        SymbolContext sym_ctx;
1118
        sym_ctx.symbol = SymbolAtIndex(temp_symbol_indexes[i]);
1119
        if (sym_ctx.symbol) {
1120
          switch (sym_ctx.symbol->GetType()) {
1121
          case eSymbolTypeCode:
1122
          case eSymbolTypeResolver:
1123
          case eSymbolTypeReExported:
1124
          case eSymbolTypeAbsolute:
1125
            symbol_indexes.push_back(temp_symbol_indexes[i]);
1126
            break;
1127
          default:
1128
            break;
1129
          }
1130
        }
1131
      }
1132
    }
1133
  }
1134

1135
  if (!m_name_indexes_computed)
1136
    InitNameIndexes();
1137

1138
  for (lldb::FunctionNameType type :
1139
       {lldb::eFunctionNameTypeBase, lldb::eFunctionNameTypeMethod,
1140
        lldb::eFunctionNameTypeSelector}) {
1141
    if (name_type_mask & type) {
1142
      auto map = GetNameToSymbolIndexMap(type);
1143

1144
      const UniqueCStringMap<uint32_t>::Entry *match;
1145
      for (match = map.FindFirstValueForName(name); match != nullptr;
1146
           match = map.FindNextValueForName(match)) {
1147
        symbol_indexes.push_back(match->value);
1148
      }
1149
    }
1150
  }
1151

1152
  if (!symbol_indexes.empty()) {
1153
    llvm::sort(symbol_indexes);
1154
    symbol_indexes.erase(
1155
        std::unique(symbol_indexes.begin(), symbol_indexes.end()),
1156
        symbol_indexes.end());
1157
    SymbolIndicesToSymbolContextList(symbol_indexes, sc_list);
1158
  }
1159
}
1160

1161
const Symbol *Symtab::GetParent(Symbol *child_symbol) const {
1162
  uint32_t child_idx = GetIndexForSymbol(child_symbol);
1163
  if (child_idx != UINT32_MAX && child_idx > 0) {
1164
    for (uint32_t idx = child_idx - 1; idx != UINT32_MAX; --idx) {
1165
      const Symbol *symbol = SymbolAtIndex(idx);
1166
      const uint32_t sibling_idx = symbol->GetSiblingIndex();
1167
      if (sibling_idx != UINT32_MAX && sibling_idx > child_idx)
1168
        return symbol;
1169
    }
1170
  }
1171
  return nullptr;
1172
}
1173

1174
std::string Symtab::GetCacheKey() {
1175
  std::string key;
1176
  llvm::raw_string_ostream strm(key);
1177
  // Symbol table can come from different object files for the same module. A
1178
  // module can have one object file as the main executable and might have
1179
  // another object file in a separate symbol file.
1180
  strm << m_objfile->GetModule()->GetCacheKey() << "-symtab-"
1181
      << llvm::format_hex(m_objfile->GetCacheHash(), 10);
1182
  return strm.str();
1183
}
1184

1185
void Symtab::SaveToCache() {
1186
  DataFileCache *cache = Module::GetIndexCache();
1187
  if (!cache)
1188
    return; // Caching is not enabled.
1189
  InitNameIndexes(); // Init the name indexes so we can cache them as well.
1190
  const auto byte_order = endian::InlHostByteOrder();
1191
  DataEncoder file(byte_order, /*addr_size=*/8);
1192
  // Encode will return false if the symbol table's object file doesn't have
1193
  // anything to make a signature from.
1194
  if (Encode(file))
1195
    if (cache->SetCachedData(GetCacheKey(), file.GetData()))
1196
      SetWasSavedToCache();
1197
}
1198

1199
constexpr llvm::StringLiteral kIdentifierCStrMap("CMAP");
1200

1201
static void EncodeCStrMap(DataEncoder &encoder, ConstStringTable &strtab,
1202
                          const UniqueCStringMap<uint32_t> &cstr_map) {
1203
  encoder.AppendData(kIdentifierCStrMap);
1204
  encoder.AppendU32(cstr_map.GetSize());
1205
  for (const auto &entry: cstr_map) {
1206
    // Make sure there are no empty strings.
1207
    assert((bool)entry.cstring);
1208
    encoder.AppendU32(strtab.Add(entry.cstring));
1209
    encoder.AppendU32(entry.value);
1210
  }
1211
}
1212

1213
bool DecodeCStrMap(const DataExtractor &data, lldb::offset_t *offset_ptr,
1214
                   const StringTableReader &strtab,
1215
                   UniqueCStringMap<uint32_t> &cstr_map) {
1216
  llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4);
1217
  if (identifier != kIdentifierCStrMap)
1218
    return false;
1219
  const uint32_t count = data.GetU32(offset_ptr);
1220
  cstr_map.Reserve(count);
1221
  for (uint32_t i=0; i<count; ++i)
1222
  {
1223
    llvm::StringRef str(strtab.Get(data.GetU32(offset_ptr)));
1224
    uint32_t value = data.GetU32(offset_ptr);
1225
    // No empty strings in the name indexes in Symtab
1226
    if (str.empty())
1227
      return false;
1228
    cstr_map.Append(ConstString(str), value);
1229
  }
1230
  // We must sort the UniqueCStringMap after decoding it since it is a vector
1231
  // of UniqueCStringMap::Entry objects which contain a ConstString and type T.
1232
  // ConstString objects are sorted by "const char *" and then type T and
1233
  // the "const char *" are point values that will depend on the order in which
1234
  // ConstString objects are created and in which of the 256 string pools they
1235
  // are created in. So after we decode all of the entries, we must sort the
1236
  // name map to ensure name lookups succeed. If we encode and decode within
1237
  // the same process we wouldn't need to sort, so unit testing didn't catch
1238
  // this issue when first checked in.
1239
  cstr_map.Sort();
1240
  return true;
1241
}
1242

1243
constexpr llvm::StringLiteral kIdentifierSymbolTable("SYMB");
1244
constexpr uint32_t CURRENT_CACHE_VERSION = 1;
1245

1246
/// The encoding format for the symbol table is as follows:
1247
///
1248
/// Signature signature;
1249
/// ConstStringTable strtab;
1250
/// Identifier four character code: 'SYMB'
1251
/// uint32_t version;
1252
/// uint32_t num_symbols;
1253
/// Symbol symbols[num_symbols];
1254
/// uint8_t num_cstr_maps;
1255
/// UniqueCStringMap<uint32_t> cstr_maps[num_cstr_maps]
1256
bool Symtab::Encode(DataEncoder &encoder) const {
1257
  // Name indexes must be computed before calling this function.
1258
  assert(m_name_indexes_computed);
1259

1260
  // Encode the object file's signature
1261
  CacheSignature signature(m_objfile);
1262
  if (!signature.Encode(encoder))
1263
    return false;
1264
  ConstStringTable strtab;
1265

1266
  // Encoder the symbol table into a separate encoder first. This allows us
1267
  // gather all of the strings we willl need in "strtab" as we will need to
1268
  // write the string table out before the symbol table.
1269
  DataEncoder symtab_encoder(encoder.GetByteOrder(),
1270
                              encoder.GetAddressByteSize());
1271
  symtab_encoder.AppendData(kIdentifierSymbolTable);
1272
  // Encode the symtab data version.
1273
  symtab_encoder.AppendU32(CURRENT_CACHE_VERSION);
1274
  // Encode the number of symbols.
1275
  symtab_encoder.AppendU32(m_symbols.size());
1276
  // Encode the symbol data for all symbols.
1277
  for (const auto &symbol: m_symbols)
1278
    symbol.Encode(symtab_encoder, strtab);
1279

1280
  // Emit a byte for how many C string maps we emit. We will fix this up after
1281
  // we emit the C string maps since we skip emitting C string maps if they are
1282
  // empty.
1283
  size_t num_cmaps_offset = symtab_encoder.GetByteSize();
1284
  uint8_t num_cmaps = 0;
1285
  symtab_encoder.AppendU8(0);
1286
  for (const auto &pair: m_name_to_symbol_indices) {
1287
    if (pair.second.IsEmpty())
1288
      continue;
1289
    ++num_cmaps;
1290
    symtab_encoder.AppendU8(pair.first);
1291
    EncodeCStrMap(symtab_encoder, strtab, pair.second);
1292
  }
1293
  if (num_cmaps > 0)
1294
    symtab_encoder.PutU8(num_cmaps_offset, num_cmaps);
1295

1296
  // Now that all strings have been gathered, we will emit the string table.
1297
  strtab.Encode(encoder);
1298
  // Followed by the symbol table data.
1299
  encoder.AppendData(symtab_encoder.GetData());
1300
  return true;
1301
}
1302

1303
bool Symtab::Decode(const DataExtractor &data, lldb::offset_t *offset_ptr,
1304
                    bool &signature_mismatch) {
1305
  signature_mismatch = false;
1306
  CacheSignature signature;
1307
  StringTableReader strtab;
1308
  { // Scope for "elapsed" object below so it can measure the time parse.
1309
    ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabParseTime());
1310
    if (!signature.Decode(data, offset_ptr))
1311
      return false;
1312
    if (CacheSignature(m_objfile) != signature) {
1313
      signature_mismatch = true;
1314
      return false;
1315
    }
1316
    // We now decode the string table for all strings in the data cache file.
1317
    if (!strtab.Decode(data, offset_ptr))
1318
      return false;
1319

1320
    // And now we can decode the symbol table with string table we just decoded.
1321
    llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4);
1322
    if (identifier != kIdentifierSymbolTable)
1323
      return false;
1324
    const uint32_t version = data.GetU32(offset_ptr);
1325
    if (version != CURRENT_CACHE_VERSION)
1326
      return false;
1327
    const uint32_t num_symbols = data.GetU32(offset_ptr);
1328
    if (num_symbols == 0)
1329
      return true;
1330
    m_symbols.resize(num_symbols);
1331
    SectionList *sections = m_objfile->GetModule()->GetSectionList();
1332
    for (uint32_t i=0; i<num_symbols; ++i) {
1333
      if (!m_symbols[i].Decode(data, offset_ptr, sections, strtab))
1334
        return false;
1335
    }
1336
  }
1337

1338
  { // Scope for "elapsed" object below so it can measure the time to index.
1339
    ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabIndexTime());
1340
    const uint8_t num_cstr_maps = data.GetU8(offset_ptr);
1341
    for (uint8_t i=0; i<num_cstr_maps; ++i) {
1342
      uint8_t type = data.GetU8(offset_ptr);
1343
      UniqueCStringMap<uint32_t> &cstr_map =
1344
          GetNameToSymbolIndexMap((lldb::FunctionNameType)type);
1345
      if (!DecodeCStrMap(data, offset_ptr, strtab, cstr_map))
1346
        return false;
1347
    }
1348
    m_name_indexes_computed = true;
1349
  }
1350
  return true;
1351
}
1352

1353
bool Symtab::LoadFromCache() {
1354
  DataFileCache *cache = Module::GetIndexCache();
1355
  if (!cache)
1356
    return false;
1357

1358
  std::unique_ptr<llvm::MemoryBuffer> mem_buffer_up =
1359
      cache->GetCachedData(GetCacheKey());
1360
  if (!mem_buffer_up)
1361
    return false;
1362
  DataExtractor data(mem_buffer_up->getBufferStart(),
1363
                     mem_buffer_up->getBufferSize(),
1364
                     m_objfile->GetByteOrder(),
1365
                     m_objfile->GetAddressByteSize());
1366
  bool signature_mismatch = false;
1367
  lldb::offset_t offset = 0;
1368
  const bool result = Decode(data, &offset, signature_mismatch);
1369
  if (signature_mismatch)
1370
    cache->RemoveCacheFile(GetCacheKey());
1371
  if (result)
1372
    SetWasLoadedFromCache();
1373
  return result;
1374
}
1375