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
31using namespace lldb;
32using namespace lldb_private;
33
34Symtab::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(args: std::make_pair(
40 x: lldb::eFunctionNameTypeNone, y: UniqueCStringMap<uint32_t>()));
41 m_name_to_symbol_indices.emplace(args: std::make_pair(
42 x: lldb::eFunctionNameTypeBase, y: UniqueCStringMap<uint32_t>()));
43 m_name_to_symbol_indices.emplace(args: std::make_pair(
44 x: lldb::eFunctionNameTypeMethod, y: UniqueCStringMap<uint32_t>()));
45 m_name_to_symbol_indices.emplace(args: std::make_pair(
46 x: lldb::eFunctionNameTypeSelector, y: UniqueCStringMap<uint32_t>()));
47}
48
49Symtab::~Symtab() = default;
50
51void 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(n: count);
55}
56
57Symbol *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(new_size: count);
61 return m_symbols.empty() ? nullptr : &m_symbols[0];
62}
63
64uint32_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(type: lldb::eFunctionNameTypeNone);
69 name_to_index.Clear();
70 m_file_addr_to_index.Clear();
71 m_symbols.push_back(x: symbol);
72 m_file_addr_to_index_computed = false;
73 m_name_indexes_computed = false;
74 return symbol_idx;
75}
76
77size_t Symtab::GetNumSymbols() const {
78 std::lock_guard<std::recursive_mutex> guard(m_mutex);
79 return m_symbols.size();
80}
81
82void Symtab::SectionFileAddressesChanged() {
83 m_file_addr_to_index.Clear();
84 m_file_addr_to_index_computed = false;
85}
86
87void 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(format: "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(format: "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(cstr: ":\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, index: std::distance(first: begin, last: 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(cstr: " (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(args: symbol.GetName().GetStringRef(), args: &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, index: symbol - &m_symbols[0], name_preference);
134 }
135 } break;
136
137 case eSortOrderBySize: {
138 s->PutCString(cstr: " (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(args: symbol.GetByteSize(), args: &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, index: idx++, name_preference);
150 }
151 } break;
152
153 case eSortOrderByAddress:
154 s->PutCString(cstr: " (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, index: symbol_idx, name_preference);
163 }
164 break;
165 }
166 } else {
167 s->PutCString(cstr: "\n");
168 }
169}
170
171void 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(format: "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, index: idx, name_preference);
191 }
192 }
193 }
194 s->IndentLess();
195}
196
197void Symtab::DumpSymbolHeader(Stream *s) {
198 s->Indent(s: " Debug symbol\n");
199 s->Indent(s: " |Synthetic symbol\n");
200 s->Indent(s: " ||Externally Visible\n");
201 s->Indent(s: " |||\n");
202 s->Indent(s: "Index UserID DSX Type File Address/Value Load "
203 "Address Size Flags Name\n");
204 s->Indent(s: "------- ------ --- --------------- ------------------ "
205 "------------------ ------------------ ---------- "
206 "----------------------------------\n");
207}
208
209static 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
219Symbol *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(key: &symbol_uid, base: &m_symbols[0], nmemb: m_symbols.size(),
224 size: sizeof(m_symbols[0]), compar: CompareSymbolID);
225 return symbol;
226}
227
228Symbol *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
236const 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
244static 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(Prefix: "_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
281void 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(callback: [&languages](Language *l) {
291 languages.push_back(x: l);
292 return true;
293 });
294
295 auto &name_to_index = GetNameToSymbolIndexMap(type: lldb::eFunctionNameTypeNone);
296 auto &basename_to_index =
297 GetNameToSymbolIndexMap(type: lldb::eFunctionNameTypeBase);
298 auto &method_to_index =
299 GetNameToSymbolIndexMap(type: lldb::eFunctionNameTypeMethod);
300 auto &selector_to_index =
301 GetNameToSymbolIndexMap(type: 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(n: 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(n: 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(unique_cstr: 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(symbol_name: name.GetStringRef()));
338 name_to_index.Append(unique_cstr: stripped, value);
339 }
340
341 const SymbolType type = symbol->GetType();
342 if (type == eSymbolTypeCode || type == eSymbolTypeResolver) {
343 if (mangled.GetRichManglingInfo(context&: rmc, skip_mangled_name: 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(unique_cstr: 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(symbol_name: name.GetStringRef()));
360 name_to_index.Append(unique_cstr: 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(method_name: name)) {
367 if (variant.GetType() & lldb::eFunctionNameTypeSelector)
368 selector_to_index.Append(unique_cstr: variant.GetName(), value);
369 else if (variant.GetType() & lldb::eFunctionNameTypeFull)
370 name_to_index.Append(unique_cstr: variant.GetName(), value);
371 else if (variant.GetType() & lldb::eFunctionNameTypeMethod)
372 method_to_index.Append(unique_cstr: variant.GetName(), value);
373 else if (variant.GetType() & lldb::eFunctionNameTypeBase)
374 basename_to_index.Append(unique_cstr: variant.GetName(), value);
375 }
376 }
377 }
378 }
379
380 for (const auto &record : backlog) {
381 RegisterBacklogEntry(entry: record.first, decl_context: 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
395void 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(type: lldb::eFunctionNameTypeBase);
413 basename_to_index.Append(e: 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(type: lldb::eFunctionNameTypeNone);
417 name_to_index.Append(e: 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(x: decl_context_ccstr);
425
426 auto &method_to_index =
427 GetNameToSymbolIndexMap(type: lldb::eFunctionNameTypeMethod);
428 // Register constructors and destructors. They are methods and create
429 // declaration contexts.
430 if (rmc.IsCtorOrDtor()) {
431 method_to_index.Append(e: entry);
432 if (it == class_contexts.end())
433 class_contexts.insert(position: it, x: 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(e: 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(x: std::make_pair(x&: entry, y&: decl_context_ccstr));
446}
447
448void 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(type: lldb::eFunctionNameTypeMethod);
453 auto it = class_contexts.find(x: decl_context);
454 if (it != class_contexts.end()) {
455 method_to_index.Append(e: 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(e: entry);
460 auto &basename_to_index =
461 GetNameToSymbolIndexMap(type: lldb::eFunctionNameTypeBase);
462 basename_to_index.Append(e: entry);
463 }
464}
465
466void Symtab::PreloadSymbols() {
467 std::lock_guard<std::recursive_mutex> guard(m_mutex);
468 InitNameIndexes();
469}
470
471void 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(unique_cstr: name, value);
489 }
490
491 if (add_mangled) {
492 if (ConstString name = mangled.GetMangledName())
493 name_to_index_map.Append(unique_cstr: name, value);
494 }
495 }
496 }
497}
498
499uint32_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>(a: m_symbols.size(), b: 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(x: i);
512 }
513
514 return indexes.size() - prev_size;
515}
516
517uint32_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>(a: m_symbols.size(), b: 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(x: i);
532 }
533
534 return indexes.size() - prev_size;
535}
536
537uint32_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>(a: m_symbols.size(), b: 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(idx: i, symbol_debug_type, symbol_visibility))
553 indexes.push_back(x: i);
554 }
555 }
556
557 return indexes.size() - prev_size;
558}
559
560uint32_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
569struct SymbolSortInfo {
570 const bool sort_by_load_addr;
571 const Symbol *symbols;
572};
573
574namespace {
575struct 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
625void 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(first: indexes.begin(), last: indexes.end(), comp: comparator);
642
643 // Remove any duplicates if requested
644 if (remove_duplicates) {
645 auto last = std::unique(first: indexes.begin(), last: indexes.end());
646 indexes.erase(first: last, last: indexes.end());
647 }
648}
649
650uint32_t Symtab::GetNameIndexes(ConstString symbol_name,
651 std::vector<uint32_t> &indexes) {
652 auto &name_to_index = GetNameToSymbolIndexMap(type: lldb::eFunctionNameTypeNone);
653 const uint32_t count = name_to_index.GetValues(unique_cstr: symbol_name, values&: 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(Prefix: 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(Str: name, /*Radix=*/10, Result&: uid))
669 return 0; // Failed to extract the user ID as an integer
670 Symbol *symbol = FindSymbolByID(symbol_uid: 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(x: symbol_idx);
677 return 1;
678}
679
680uint32_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
693uint32_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, indexes&: all_name_indexes);
708 for (size_t i = 0; i < name_match_count; ++i) {
709 if (CheckSymbolAtIndex(idx: all_name_indexes[i], symbol_debug_type,
710 symbol_visibility))
711 indexes.push_back(x: all_name_indexes[i]);
712 }
713 return indexes.size() - old_size;
714 }
715 return 0;
716}
717
718uint32_t
719Symtab::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(position: pos);
732 }
733 }
734 return indexes.size();
735}
736
737uint32_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(position: pos);
752 }
753 }
754 return indexes.size();
755}
756
757uint32_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(preference: name_preference).AsCString();
770 if (name) {
771 if (regexp.Execute(string: name))
772 indexes.push_back(x: i);
773 }
774 }
775 }
776 return indexes.size() - prev_size;
777}
778
779uint32_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(idx: i, symbol_debug_type, symbol_visibility))
792 continue;
793
794 const char *name =
795 m_symbols[i].GetMangled().GetName(preference: name_preference).AsCString();
796 if (name) {
797 if (regexp.Execute(string: name))
798 indexes.push_back(x: i);
799 }
800 }
801 }
802 return indexes.size() - prev_size;
803}
804
805Symbol *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
824void
825Symtab::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(symbol_name: name, symbol_type, indexes&: symbol_indexes);
839 }
840}
841
842void 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(symbol_name: name, symbol_type, symbol_debug_type,
857 symbol_visibility, indexes&: symbol_indexes);
858 }
859}
860
861void 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(regexp: regex, symbol_type, symbol_debug_type,
869 symbol_visibility, indexes&: symbol_indexes,
870 name_preference);
871}
872
873Symbol *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(symbol_name: name, symbol_type, symbol_debug_type,
887 symbol_visibility,
888 indexes&: 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(idx: *pos);
892
893 if (symbol->Compare(name, type: symbol_type))
894 return symbol;
895 }
896 }
897 }
898 return nullptr;
899}
900
901typedef 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.
911static void AddSectionsToRangeMap(SectionList *sectlist,
912 RangeVector<addr_t, addr_t> &section_ranges) {
913 const int num_sections = sectlist->GetNumSections(depth: 0);
914 for (int i = 0; i < num_sections; i++) {
915 SectionSP sect_sp = sectlist->GetSectionAtIndex(idx: 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(depth: 0) > 0) {
922 AddSectionsToRangeMap(sectlist: &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
937void 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(first: begin, last: 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(addr: 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(i: 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
1020void 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
1029Symbol *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(addr: file_addr);
1036 if (entry) {
1037 Symbol *symbol = SymbolAtIndex(idx: entry->data);
1038 if (symbol->GetFileAddress() == file_addr)
1039 return symbol;
1040 }
1041 return nullptr;
1042}
1043
1044Symbol *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(addr: file_addr);
1052 if (entry) {
1053 Symbol *symbol = SymbolAtIndex(idx: entry->data);
1054 if (symbol->ContainsFileAddress(file_addr))
1055 return symbol;
1056 }
1057 return nullptr;
1058}
1059
1060void 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(addr: file_addr,
1072 indexes&: all_addr_indexes);
1073
1074 for (size_t i = 0; i < addr_match_count; ++i) {
1075 Symbol *symbol = SymbolAtIndex(idx: all_addr_indexes[i]);
1076 if (symbol->ContainsFileAddress(file_addr)) {
1077 if (!callback(symbol))
1078 break;
1079 }
1080 }
1081}
1082
1083void 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(idx: symbol_indexes[i]);
1095 if (sc.symbol)
1096 sc_list.AppendIfUnique(sc, merge_symbol_into_function);
1097 }
1098 }
1099}
1100
1101void 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, symbol_type: eSymbolTypeAny, symbol_indexes&: 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(idx: 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(x: 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(unique_cstr: name); match != nullptr;
1146 match = map.FindNextValueForName(entry_ptr: match)) {
1147 symbol_indexes.push_back(x: match->value);
1148 }
1149 }
1150 }
1151
1152 if (!symbol_indexes.empty()) {
1153 llvm::sort(C&: symbol_indexes);
1154 symbol_indexes.erase(
1155 first: std::unique(first: symbol_indexes.begin(), last: symbol_indexes.end()),
1156 last: symbol_indexes.end());
1157 SymbolIndicesToSymbolContextList(symbol_indexes, sc_list);
1158 }
1159}
1160
1161const Symbol *Symtab::GetParent(Symbol *child_symbol) const {
1162 uint32_t child_idx = GetIndexForSymbol(symbol: 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
1174std::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(N: m_objfile->GetCacheHash(), Width: 10);
1182 return strm.str();
1183}
1184
1185void 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(encoder&: file))
1195 if (cache->SetCachedData(key: GetCacheKey(), data: file.GetData()))
1196 SetWasSavedToCache();
1197}
1198
1199constexpr llvm::StringLiteral kIdentifierCStrMap("CMAP");
1200
1201static void EncodeCStrMap(DataEncoder &encoder, ConstStringTable &strtab,
1202 const UniqueCStringMap<uint32_t> &cstr_map) {
1203 encoder.AppendData(data: kIdentifierCStrMap);
1204 encoder.AppendU32(value: 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(value: strtab.Add(s: entry.cstring));
1209 encoder.AppendU32(value: entry.value);
1210 }
1211}
1212
1213bool 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, length: 4), 4);
1217 if (identifier != kIdentifierCStrMap)
1218 return false;
1219 const uint32_t count = data.GetU32(offset_ptr);
1220 cstr_map.Reserve(n: count);
1221 for (uint32_t i=0; i<count; ++i)
1222 {
1223 llvm::StringRef str(strtab.Get(offset: 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(unique_cstr: 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
1243constexpr llvm::StringLiteral kIdentifierSymbolTable("SYMB");
1244constexpr 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]
1256bool 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(data: kIdentifierSymbolTable);
1272 // Encode the symtab data version.
1273 symtab_encoder.AppendU32(value: CURRENT_CACHE_VERSION);
1274 // Encode the number of symbols.
1275 symtab_encoder.AppendU32(value: m_symbols.size());
1276 // Encode the symbol data for all symbols.
1277 for (const auto &symbol: m_symbols)
1278 symbol.Encode(encoder&: 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(value: 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(value: pair.first);
1291 EncodeCStrMap(encoder&: symtab_encoder, strtab, cstr_map: pair.second);
1292 }
1293 if (num_cmaps > 0)
1294 symtab_encoder.PutU8(offset: num_cmaps_offset, value: 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(data: symtab_encoder.GetData());
1300 return true;
1301}
1302
1303bool 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, length: 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(new_size: 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, section_list: 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(type: (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
1353bool 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(key: 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_ptr: &offset, signature_mismatch);
1369 if (signature_mismatch)
1370 cache->RemoveCacheFile(key: GetCacheKey());
1371 if (result)
1372 SetWasLoadedFromCache();
1373 return result;
1374}
1375

source code of lldb/source/Symbol/Symtab.cpp