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(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
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(n: 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(new_size: 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(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
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(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
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(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
197	void 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
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(key: &symbol_uid, base: &m_symbols[0], nmemb: m_symbols.size(),
224	size: sizeof(m_symbols[0]), compar: 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(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
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(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
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(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
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(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
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(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
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>(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
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>(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
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>(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
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	llvm::stable_sort(Range&: indexes, C: comparator);
642
643	// Remove any duplicates if requested
644	if (remove_duplicates) {
645	auto last = llvm::unique(R&: indexes);
646	indexes.erase(first: last, 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(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 the symbol file address. This allows users to
658	// find 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 file address from the symbol name
667	unsigned long long file_address = 0;
668	if (getAsUnsignedInteger(Str: name, /*Radix=*/16, Result&: file_address))
669	return 0; // Failed to extract the user ID as an integer
670
671	Symbol *symbol = FindSymbolAtFileAddress(file_addr: static_cast<addr_t>(file_address));
672	if (symbol == nullptr)
673	return 0;
674	const uint32_t symbol_idx = GetIndexForSymbol(symbol);
675	if (symbol_idx == UINT32_MAX)
676	return 0;
677	indexes.push_back(x: symbol_idx);
678	return 1;
679	}
680
681	uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name,
682	std::vector<uint32_t> &indexes) {
683	std::lock_guard<std::recursive_mutex> guard(m_mutex);
684
685	if (symbol_name) {
686	if (!m_name_indexes_computed)
687	InitNameIndexes();
688
689	return GetNameIndexes(symbol_name, indexes);
690	}
691	return 0;
692	}
693
694	uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name,
695	Debug symbol_debug_type,
696	Visibility symbol_visibility,
697	std::vector<uint32_t> &indexes) {
698	std::lock_guard<std::recursive_mutex> guard(m_mutex);
699
700	LLDB_SCOPED_TIMER();
701	if (symbol_name) {
702	const size_t old_size = indexes.size();
703	if (!m_name_indexes_computed)
704	InitNameIndexes();
705
706	std::vector<uint32_t> all_name_indexes;
707	const size_t name_match_count =
708	GetNameIndexes(symbol_name, indexes&: all_name_indexes);
709	for (size_t i = 0; i < name_match_count; ++i) {
710	if (CheckSymbolAtIndex(idx: all_name_indexes[i], symbol_debug_type,
711	symbol_visibility))
712	indexes.push_back(x: all_name_indexes[i]);
713	}
714	return indexes.size() - old_size;
715	}
716	return 0;
717	}
718
719	uint32_t
720	Symtab::AppendSymbolIndexesWithNameAndType(ConstString symbol_name,
721	SymbolType symbol_type,
722	std::vector<uint32_t> &indexes) {
723	std::lock_guard<std::recursive_mutex> guard(m_mutex);
724
725	if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0) {
726	std::vector<uint32_t>::iterator pos = indexes.begin();
727	while (pos != indexes.end()) {
728	if (symbol_type == eSymbolTypeAny ||
729	m_symbols[*pos].GetType() == symbol_type)
730	++pos;
731	else
732	pos = indexes.erase(position: pos);
733	}
734	}
735	return indexes.size();
736	}
737
738	uint32_t Symtab::AppendSymbolIndexesWithNameAndType(
739	ConstString symbol_name, SymbolType symbol_type,
740	Debug symbol_debug_type, Visibility symbol_visibility,
741	std::vector<uint32_t> &indexes) {
742	std::lock_guard<std::recursive_mutex> guard(m_mutex);
743
744	if (AppendSymbolIndexesWithName(symbol_name, symbol_debug_type,
745	symbol_visibility, indexes) > 0) {
746	std::vector<uint32_t>::iterator pos = indexes.begin();
747	while (pos != indexes.end()) {
748	if (symbol_type == eSymbolTypeAny ||
749	m_symbols[*pos].GetType() == symbol_type)
750	++pos;
751	else
752	pos = indexes.erase(position: pos);
753	}
754	}
755	return indexes.size();
756	}
757
758	uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
759	const RegularExpression &regexp, SymbolType symbol_type,
760	std::vector<uint32_t> &indexes, Mangled::NamePreference name_preference) {
761	std::lock_guard<std::recursive_mutex> guard(m_mutex);
762
763	uint32_t prev_size = indexes.size();
764	uint32_t sym_end = m_symbols.size();
765
766	for (uint32_t i = 0; i < sym_end; i++) {
767	if (symbol_type == eSymbolTypeAny ||
768	m_symbols[i].GetType() == symbol_type) {
769	const char *name =
770	m_symbols[i].GetMangled().GetName(preference: name_preference).AsCString();
771	if (name) {
772	if (regexp.Execute(string: name))
773	indexes.push_back(x: i);
774	}
775	}
776	}
777	return indexes.size() - prev_size;
778	}
779
780	uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
781	const RegularExpression &regexp, SymbolType symbol_type,
782	Debug symbol_debug_type, Visibility symbol_visibility,
783	std::vector<uint32_t> &indexes, Mangled::NamePreference name_preference) {
784	std::lock_guard<std::recursive_mutex> guard(m_mutex);
785
786	uint32_t prev_size = indexes.size();
787	uint32_t sym_end = m_symbols.size();
788
789	for (uint32_t i = 0; i < sym_end; i++) {
790	if (symbol_type == eSymbolTypeAny ||
791	m_symbols[i].GetType() == symbol_type) {
792	if (!CheckSymbolAtIndex(idx: i, symbol_debug_type, symbol_visibility))
793	continue;
794
795	const char *name =
796	m_symbols[i].GetMangled().GetName(preference: name_preference).AsCString();
797	if (name) {
798	if (regexp.Execute(string: name))
799	indexes.push_back(x: i);
800	}
801	}
802	}
803	return indexes.size() - prev_size;
804	}
805
806	Symbol *Symtab::FindSymbolWithType(SymbolType symbol_type,
807	Debug symbol_debug_type,
808	Visibility symbol_visibility,
809	uint32_t &start_idx) {
810	std::lock_guard<std::recursive_mutex> guard(m_mutex);
811
812	const size_t count = m_symbols.size();
813	for (size_t idx = start_idx; idx < count; ++idx) {
814	if (symbol_type == eSymbolTypeAny ||
815	m_symbols[idx].GetType() == symbol_type) {
816	if (CheckSymbolAtIndex(idx, symbol_debug_type, symbol_visibility)) {
817	start_idx = idx;
818	return &m_symbols[idx];
819	}
820	}
821	}
822	return nullptr;
823	}
824
825	void
826	Symtab::FindAllSymbolsWithNameAndType(ConstString name,
827	SymbolType symbol_type,
828	std::vector<uint32_t> &symbol_indexes) {
829	std::lock_guard<std::recursive_mutex> guard(m_mutex);
830
831	// Initialize all of the lookup by name indexes before converting NAME to a
832	// uniqued string NAME_STR below.
833	if (!m_name_indexes_computed)
834	InitNameIndexes();
835
836	if (name) {
837	// The string table did have a string that matched, but we need to check
838	// the symbols and match the symbol_type if any was given.
839	AppendSymbolIndexesWithNameAndType(symbol_name: name, symbol_type, indexes&: symbol_indexes);
840	}
841	}
842
843	void Symtab::FindAllSymbolsWithNameAndType(
844	ConstString name, SymbolType symbol_type, Debug symbol_debug_type,
845	Visibility symbol_visibility, std::vector<uint32_t> &symbol_indexes) {
846	std::lock_guard<std::recursive_mutex> guard(m_mutex);
847
848	LLDB_SCOPED_TIMER();
849	// Initialize all of the lookup by name indexes before converting NAME to a
850	// uniqued string NAME_STR below.
851	if (!m_name_indexes_computed)
852	InitNameIndexes();
853
854	if (name) {
855	// The string table did have a string that matched, but we need to check
856	// the symbols and match the symbol_type if any was given.
857	AppendSymbolIndexesWithNameAndType(symbol_name: name, symbol_type, symbol_debug_type,
858	symbol_visibility, indexes&: symbol_indexes);
859	}
860	}
861
862	void Symtab::FindAllSymbolsMatchingRexExAndType(
863	const RegularExpression &regex, SymbolType symbol_type,
864	Debug symbol_debug_type, Visibility symbol_visibility,
865	std::vector<uint32_t> &symbol_indexes,
866	Mangled::NamePreference name_preference) {
867	std::lock_guard<std::recursive_mutex> guard(m_mutex);
868
869	AppendSymbolIndexesMatchingRegExAndType(regexp: regex, symbol_type, symbol_debug_type,
870	symbol_visibility, indexes&: symbol_indexes,
871	name_preference);
872	}
873
874	Symbol *Symtab::FindFirstSymbolWithNameAndType(ConstString name,
875	SymbolType symbol_type,
876	Debug symbol_debug_type,
877	Visibility symbol_visibility) {
878	std::lock_guard<std::recursive_mutex> guard(m_mutex);
879	LLDB_SCOPED_TIMER();
880	if (!m_name_indexes_computed)
881	InitNameIndexes();
882
883	if (name) {
884	std::vector<uint32_t> matching_indexes;
885	// The string table did have a string that matched, but we need to check
886	// the symbols and match the symbol_type if any was given.
887	if (AppendSymbolIndexesWithNameAndType(symbol_name: name, symbol_type, symbol_debug_type,
888	symbol_visibility,
889	indexes&: matching_indexes)) {
890	std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end();
891	for (pos = matching_indexes.begin(); pos != end; ++pos) {
892	Symbol *symbol = SymbolAtIndex(idx: *pos);
893
894	if (symbol->Compare(name, type: symbol_type))
895	return symbol;
896	}
897	}
898	}
899	return nullptr;
900	}
901
902	typedef struct {
903	const Symtab *symtab;
904	const addr_t file_addr;
905	Symbol *match_symbol;
906	const uint32_t *match_index_ptr;
907	addr_t match_offset;
908	} SymbolSearchInfo;
909
910	// Add all the section file start address & size to the RangeVector, recusively
911	// adding any children sections.
912	static void AddSectionsToRangeMap(SectionList *sectlist,
913	RangeVector<addr_t, addr_t> &section_ranges) {
914	const int num_sections = sectlist->GetNumSections(depth: 0);
915	for (int i = 0; i < num_sections; i++) {
916	SectionSP sect_sp = sectlist->GetSectionAtIndex(idx: i);
917	if (sect_sp) {
918	SectionList &child_sectlist = sect_sp->GetChildren();
919
920	// If this section has children, add the children to the RangeVector.
921	// Else add this section to the RangeVector.
922	if (child_sectlist.GetNumSections(depth: 0) > 0) {
923	AddSectionsToRangeMap(sectlist: &child_sectlist, section_ranges);
924	} else {
925	size_t size = sect_sp->GetByteSize();
926	if (size > 0) {
927	addr_t base_addr = sect_sp->GetFileAddress();
928	RangeVector<addr_t, addr_t>::Entry entry;
929	entry.SetRangeBase(base_addr);
930	entry.SetByteSize(size);
931	section_ranges.Append(entry);
932	}
933	}
934	}
935	}
936	}
937
938	void Symtab::InitAddressIndexes() {
939	// Protected function, no need to lock mutex...
940	if (!m_file_addr_to_index_computed && !m_symbols.empty()) {
941	m_file_addr_to_index_computed = true;
942
943	FileRangeToIndexMap::Entry entry;
944	const_iterator begin = m_symbols.begin();
945	const_iterator end = m_symbols.end();
946	for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
947	if (pos->ValueIsAddress()) {
948	entry.SetRangeBase(pos->GetAddressRef().GetFileAddress());
949	entry.SetByteSize(pos->GetByteSize());
950	entry.data = std::distance(first: begin, last: pos);
951	m_file_addr_to_index.Append(entry);
952	}
953	}
954	const size_t num_entries = m_file_addr_to_index.GetSize();
955	if (num_entries > 0) {
956	m_file_addr_to_index.Sort();
957
958	// Create a RangeVector with the start & size of all the sections for
959	// this objfile. We'll need to check this for any FileRangeToIndexMap
960	// entries with an uninitialized size, which could potentially be a large
961	// number so reconstituting the weak pointer is busywork when it is
962	// invariant information.
963	SectionList *sectlist = m_objfile->GetSectionList();
964	RangeVector<addr_t, addr_t> section_ranges;
965	if (sectlist) {
966	AddSectionsToRangeMap(sectlist, section_ranges);
967	section_ranges.Sort();
968	}
969
970	// Iterate through the FileRangeToIndexMap and fill in the size for any
971	// entries that didn't already have a size from the Symbol (e.g. if we
972	// have a plain linker symbol with an address only, instead of debug info
973	// where we get an address and a size and a type, etc.)
974	for (size_t i = 0; i < num_entries; i++) {
975	FileRangeToIndexMap::Entry *entry =
976	m_file_addr_to_index.GetMutableEntryAtIndex(i);
977	if (entry->GetByteSize() == 0) {
978	addr_t curr_base_addr = entry->GetRangeBase();
979	const RangeVector<addr_t, addr_t>::Entry *containing_section =
980	section_ranges.FindEntryThatContains(addr: curr_base_addr);
981
982	// Use the end of the section as the default max size of the symbol
983	addr_t sym_size = 0;
984	if (containing_section) {
985	sym_size =
986	containing_section->GetByteSize() -
987	(entry->GetRangeBase() - containing_section->GetRangeBase());
988	}
989
990	for (size_t j = i; j < num_entries; j++) {
991	FileRangeToIndexMap::Entry *next_entry =
992	m_file_addr_to_index.GetMutableEntryAtIndex(i: j);
993	addr_t next_base_addr = next_entry->GetRangeBase();
994	if (next_base_addr > curr_base_addr) {
995	addr_t size_to_next_symbol = next_base_addr - curr_base_addr;
996
997	// Take the difference between this symbol and the next one as
998	// its size, if it is less than the size of the section.
999	if (sym_size == 0 || size_to_next_symbol < sym_size) {
1000	sym_size = size_to_next_symbol;
1001	}
1002	break;
1003	}
1004	}
1005
1006	if (sym_size > 0) {
1007	entry->SetByteSize(sym_size);
1008	Symbol &symbol = m_symbols[entry->data];
1009	symbol.SetByteSize(sym_size);
1010	symbol.SetSizeIsSynthesized(true);
1011	}
1012	}
1013	}
1014
1015	// Sort again in case the range size changes the ordering
1016	m_file_addr_to_index.Sort();
1017	}
1018	}
1019	}
1020
1021	void Symtab::Finalize() {
1022	std::lock_guard<std::recursive_mutex> guard(m_mutex);
1023	// Calculate the size of symbols inside InitAddressIndexes.
1024	InitAddressIndexes();
1025	// Shrink to fit the symbols so we don't waste memory
1026	m_symbols.shrink_to_fit();
1027	SaveToCache();
1028	}
1029
1030	Symbol *Symtab::FindSymbolAtFileAddress(addr_t file_addr) {
1031	std::lock_guard<std::recursive_mutex> guard(m_mutex);
1032	if (!m_file_addr_to_index_computed)
1033	InitAddressIndexes();
1034
1035	const FileRangeToIndexMap::Entry *entry =
1036	m_file_addr_to_index.FindEntryStartsAt(addr: file_addr);
1037	if (entry) {
1038	Symbol *symbol = SymbolAtIndex(idx: entry->data);
1039	if (symbol->GetFileAddress() == file_addr)
1040	return symbol;
1041	}
1042	return nullptr;
1043	}
1044
1045	Symbol *Symtab::FindSymbolContainingFileAddress(addr_t file_addr) {
1046	std::lock_guard<std::recursive_mutex> guard(m_mutex);
1047
1048	if (!m_file_addr_to_index_computed)
1049	InitAddressIndexes();
1050
1051	const FileRangeToIndexMap::Entry *entry =
1052	m_file_addr_to_index.FindEntryThatContains(addr: file_addr);
1053	if (entry) {
1054	Symbol *symbol = SymbolAtIndex(idx: entry->data);
1055	if (symbol->ContainsFileAddress(file_addr))
1056	return symbol;
1057	}
1058	return nullptr;
1059	}
1060
1061	void Symtab::ForEachSymbolContainingFileAddress(
1062	addr_t file_addr, std::function<bool(Symbol *)> const &callback) {
1063	std::lock_guard<std::recursive_mutex> guard(m_mutex);
1064
1065	if (!m_file_addr_to_index_computed)
1066	InitAddressIndexes();
1067
1068	std::vector<uint32_t> all_addr_indexes;
1069
1070	// Get all symbols with file_addr
1071	const size_t addr_match_count =
1072	m_file_addr_to_index.FindEntryIndexesThatContain(addr: file_addr,
1073	indexes&: all_addr_indexes);
1074
1075	for (size_t i = 0; i < addr_match_count; ++i) {
1076	Symbol *symbol = SymbolAtIndex(idx: all_addr_indexes[i]);
1077	if (symbol->ContainsFileAddress(file_addr)) {
1078	if (!callback(symbol))
1079	break;
1080	}
1081	}
1082	}
1083
1084	void Symtab::SymbolIndicesToSymbolContextList(
1085	std::vector<uint32_t> &symbol_indexes, SymbolContextList &sc_list) {
1086	// No need to protect this call using m_mutex all other method calls are
1087	// already thread safe.
1088
1089	const bool merge_symbol_into_function = true;
1090	size_t num_indices = symbol_indexes.size();
1091	if (num_indices > 0) {
1092	SymbolContext sc;
1093	sc.module_sp = m_objfile->GetModule();
1094	for (size_t i = 0; i < num_indices; i++) {
1095	sc.symbol = SymbolAtIndex(idx: symbol_indexes[i]);
1096	if (sc.symbol)
1097	sc_list.AppendIfUnique(sc, merge_symbol_into_function);
1098	}
1099	}
1100	}
1101
1102	void Symtab::FindFunctionSymbols(ConstString name, uint32_t name_type_mask,
1103	SymbolContextList &sc_list) {
1104	std::vector<uint32_t> symbol_indexes;
1105
1106	// eFunctionNameTypeAuto should be pre-resolved by a call to
1107	// Module::LookupInfo::LookupInfo()
1108	assert((name_type_mask & eFunctionNameTypeAuto) == 0);
1109
1110	if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) {
1111	std::vector<uint32_t> temp_symbol_indexes;
1112	FindAllSymbolsWithNameAndType(name, symbol_type: eSymbolTypeAny, symbol_indexes&: temp_symbol_indexes);
1113
1114	unsigned temp_symbol_indexes_size = temp_symbol_indexes.size();
1115	if (temp_symbol_indexes_size > 0) {
1116	std::lock_guard<std::recursive_mutex> guard(m_mutex);
1117	for (unsigned i = 0; i < temp_symbol_indexes_size; i++) {
1118	SymbolContext sym_ctx;
1119	sym_ctx.symbol = SymbolAtIndex(idx: temp_symbol_indexes[i]);
1120	if (sym_ctx.symbol) {
1121	switch (sym_ctx.symbol->GetType()) {
1122	case eSymbolTypeCode:
1123	case eSymbolTypeResolver:
1124	case eSymbolTypeReExported:
1125	case eSymbolTypeAbsolute:
1126	symbol_indexes.push_back(x: temp_symbol_indexes[i]);
1127	break;
1128	default:
1129	break;
1130	}
1131	}
1132	}
1133	}
1134	}
1135
1136	if (!m_name_indexes_computed)
1137	InitNameIndexes();
1138
1139	for (lldb::FunctionNameType type :
1140	{lldb::eFunctionNameTypeBase, lldb::eFunctionNameTypeMethod,
1141	lldb::eFunctionNameTypeSelector}) {
1142	if (name_type_mask & type) {
1143	auto map = GetNameToSymbolIndexMap(type);
1144
1145	const UniqueCStringMap<uint32_t>::Entry *match;
1146	for (match = map.FindFirstValueForName(unique_cstr: name); match != nullptr;
1147	match = map.FindNextValueForName(entry_ptr: match)) {
1148	symbol_indexes.push_back(x: match->value);
1149	}
1150	}
1151	}
1152
1153	if (!symbol_indexes.empty()) {
1154	llvm::sort(C&: symbol_indexes);
1155	symbol_indexes.erase(first: llvm::unique(R&: symbol_indexes), last: symbol_indexes.end());
1156	SymbolIndicesToSymbolContextList(symbol_indexes, sc_list);
1157	}
1158	}
1159
1160	const Symbol *Symtab::GetParent(Symbol *child_symbol) const {
1161	uint32_t child_idx = GetIndexForSymbol(symbol: child_symbol);
1162	if (child_idx != UINT32_MAX && child_idx > 0) {
1163	for (uint32_t idx = child_idx - 1; idx != UINT32_MAX; --idx) {
1164	const Symbol *symbol = SymbolAtIndex(idx);
1165	const uint32_t sibling_idx = symbol->GetSiblingIndex();
1166	if (sibling_idx != UINT32_MAX && sibling_idx > child_idx)
1167	return symbol;
1168	}
1169	}
1170	return nullptr;
1171	}
1172
1173	std::string Symtab::GetCacheKey() {
1174	std::string key;
1175	llvm::raw_string_ostream strm(key);
1176	// Symbol table can come from different object files for the same module. A
1177	// module can have one object file as the main executable and might have
1178	// another object file in a separate symbol file.
1179	strm << m_objfile->GetModule()->GetCacheKey() << "-symtab-"
1180	<< llvm::format_hex(N: m_objfile->GetCacheHash(), Width: 10);
1181	return key;
1182	}
1183
1184	void Symtab::SaveToCache() {
1185	DataFileCache *cache = Module::GetIndexCache();
1186	if (!cache)
1187	return; // Caching is not enabled.
1188	InitNameIndexes(); // Init the name indexes so we can cache them as well.
1189	const auto byte_order = endian::InlHostByteOrder();
1190	DataEncoder file(byte_order, /*addr_size=*/8);
1191	// Encode will return false if the symbol table's object file doesn't have
1192	// anything to make a signature from.
1193	if (Encode(encoder&: file))
1194	if (cache->SetCachedData(key: GetCacheKey(), data: file.GetData()))
1195	SetWasSavedToCache();
1196	}
1197
1198	constexpr llvm::StringLiteral kIdentifierCStrMap("CMAP");
1199
1200	static void EncodeCStrMap(DataEncoder &encoder, ConstStringTable &strtab,
1201	const UniqueCStringMap<uint32_t> &cstr_map) {
1202	encoder.AppendData(data: kIdentifierCStrMap);
1203	encoder.AppendU32(value: cstr_map.GetSize());
1204	for (const auto &entry: cstr_map) {
1205	// Make sure there are no empty strings.
1206	assert((bool)entry.cstring);
1207	encoder.AppendU32(value: strtab.Add(s: entry.cstring));
1208	encoder.AppendU32(value: entry.value);
1209	}
1210	}
1211
1212	bool DecodeCStrMap(const DataExtractor &data, lldb::offset_t *offset_ptr,
1213	const StringTableReader &strtab,
1214	UniqueCStringMap<uint32_t> &cstr_map) {
1215	llvm::StringRef identifier((const char *)data.GetData(offset_ptr, length: 4), 4);
1216	if (identifier != kIdentifierCStrMap)
1217	return false;
1218	const uint32_t count = data.GetU32(offset_ptr);
1219	cstr_map.Reserve(n: count);
1220	for (uint32_t i=0; i<count; ++i)
1221	{
1222	llvm::StringRef str(strtab.Get(offset: data.GetU32(offset_ptr)));
1223	uint32_t value = data.GetU32(offset_ptr);
1224	// No empty strings in the name indexes in Symtab
1225	if (str.empty())
1226	return false;
1227	cstr_map.Append(unique_cstr: ConstString(str), value);
1228	}
1229	// We must sort the UniqueCStringMap after decoding it since it is a vector
1230	// of UniqueCStringMap::Entry objects which contain a ConstString and type T.
1231	// ConstString objects are sorted by "const char *" and then type T and
1232	// the "const char *" are point values that will depend on the order in which
1233	// ConstString objects are created and in which of the 256 string pools they
1234	// are created in. So after we decode all of the entries, we must sort the
1235	// name map to ensure name lookups succeed. If we encode and decode within
1236	// the same process we wouldn't need to sort, so unit testing didn't catch
1237	// this issue when first checked in.
1238	cstr_map.Sort();
1239	return true;
1240	}
1241
1242	constexpr llvm::StringLiteral kIdentifierSymbolTable("SYMB");
1243	constexpr uint32_t CURRENT_CACHE_VERSION = 1;
1244
1245	/// The encoding format for the symbol table is as follows:
1246	///
1247	/// Signature signature;
1248	/// ConstStringTable strtab;
1249	/// Identifier four character code: 'SYMB'
1250	/// uint32_t version;
1251	/// uint32_t num_symbols;
1252	/// Symbol symbols[num_symbols];
1253	/// uint8_t num_cstr_maps;
1254	/// UniqueCStringMap<uint32_t> cstr_maps[num_cstr_maps]
1255	bool Symtab::Encode(DataEncoder &encoder) const {
1256	// Name indexes must be computed before calling this function.
1257	assert(m_name_indexes_computed);
1258
1259	// Encode the object file's signature
1260	CacheSignature signature(m_objfile);
1261	if (!signature.Encode(encoder))
1262	return false;
1263	ConstStringTable strtab;
1264
1265	// Encoder the symbol table into a separate encoder first. This allows us
1266	// gather all of the strings we willl need in "strtab" as we will need to
1267	// write the string table out before the symbol table.
1268	DataEncoder symtab_encoder(encoder.GetByteOrder(),
1269	encoder.GetAddressByteSize());
1270	symtab_encoder.AppendData(data: kIdentifierSymbolTable);
1271	// Encode the symtab data version.
1272	symtab_encoder.AppendU32(value: CURRENT_CACHE_VERSION);
1273	// Encode the number of symbols.
1274	symtab_encoder.AppendU32(value: m_symbols.size());
1275	// Encode the symbol data for all symbols.
1276	for (const auto &symbol: m_symbols)
1277	symbol.Encode(encoder&: symtab_encoder, strtab);
1278
1279	// Emit a byte for how many C string maps we emit. We will fix this up after
1280	// we emit the C string maps since we skip emitting C string maps if they are
1281	// empty.
1282	size_t num_cmaps_offset = symtab_encoder.GetByteSize();
1283	uint8_t num_cmaps = 0;
1284	symtab_encoder.AppendU8(value: 0);
1285	for (const auto &pair: m_name_to_symbol_indices) {
1286	if (pair.second.IsEmpty())
1287	continue;
1288	++num_cmaps;
1289	symtab_encoder.AppendU8(value: pair.first);
1290	EncodeCStrMap(encoder&: symtab_encoder, strtab, cstr_map: pair.second);
1291	}
1292	if (num_cmaps > 0)
1293	symtab_encoder.PutU8(offset: num_cmaps_offset, value: num_cmaps);
1294
1295	// Now that all strings have been gathered, we will emit the string table.
1296	strtab.Encode(encoder);
1297	// Followed by the symbol table data.
1298	encoder.AppendData(data: symtab_encoder.GetData());
1299	return true;
1300	}
1301
1302	bool Symtab::Decode(const DataExtractor &data, lldb::offset_t *offset_ptr,
1303	bool &signature_mismatch) {
1304	signature_mismatch = false;
1305	CacheSignature signature;
1306	StringTableReader strtab;
1307	{ // Scope for "elapsed" object below so it can measure the time parse.
1308	ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabParseTime());
1309	if (!signature.Decode(data, offset_ptr))
1310	return false;
1311	if (CacheSignature(m_objfile) != signature) {
1312	signature_mismatch = true;
1313	return false;
1314	}
1315	// We now decode the string table for all strings in the data cache file.
1316	if (!strtab.Decode(data, offset_ptr))
1317	return false;
1318
1319	// And now we can decode the symbol table with string table we just decoded.
1320	llvm::StringRef identifier((const char *)data.GetData(offset_ptr, length: 4), 4);
1321	if (identifier != kIdentifierSymbolTable)
1322	return false;
1323	const uint32_t version = data.GetU32(offset_ptr);
1324	if (version != CURRENT_CACHE_VERSION)
1325	return false;
1326	const uint32_t num_symbols = data.GetU32(offset_ptr);
1327	if (num_symbols == 0)
1328	return true;
1329	m_symbols.resize(new_size: num_symbols);
1330	SectionList *sections = m_objfile->GetModule()->GetSectionList();
1331	for (uint32_t i=0; i<num_symbols; ++i) {
1332	if (!m_symbols[i].Decode(data, offset_ptr, section_list: sections, strtab))
1333	return false;
1334	}
1335	}
1336
1337	{ // Scope for "elapsed" object below so it can measure the time to index.
1338	ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabIndexTime());
1339	const uint8_t num_cstr_maps = data.GetU8(offset_ptr);
1340	for (uint8_t i=0; i<num_cstr_maps; ++i) {
1341	uint8_t type = data.GetU8(offset_ptr);
1342	UniqueCStringMap<uint32_t> &cstr_map =
1343	GetNameToSymbolIndexMap(type: (lldb::FunctionNameType)type);
1344	if (!DecodeCStrMap(data, offset_ptr, strtab, cstr_map))
1345	return false;
1346	}
1347	m_name_indexes_computed = true;
1348	}
1349	return true;
1350	}
1351
1352	bool Symtab::LoadFromCache() {
1353	DataFileCache *cache = Module::GetIndexCache();
1354	if (!cache)
1355	return false;
1356
1357	std::unique_ptr<llvm::MemoryBuffer> mem_buffer_up =
1358	cache->GetCachedData(key: GetCacheKey());
1359	if (!mem_buffer_up)
1360	return false;
1361	DataExtractor data(mem_buffer_up->getBufferStart(),
1362	mem_buffer_up->getBufferSize(),
1363	m_objfile->GetByteOrder(),
1364	m_objfile->GetAddressByteSize());
1365	bool signature_mismatch = false;
1366	lldb::offset_t offset = 0;
1367	const bool result = Decode(data, offset_ptr: &offset, signature_mismatch);
1368	if (signature_mismatch)
1369	cache->RemoveCacheFile(key: GetCacheKey());
1370	if (result)
1371	SetWasLoadedFromCache();
1372	return result;
1373	}
1374