blob: 649e4c5f64a81838ba233cd428f4690c9cf57f56 [file] [log] [blame]
Chris Lattner24943d22010-06-08 16:52:24 +00001//===-- Symtab.cpp ----------------------------------------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include <map>
11
12#include "lldb/Core/Module.h"
13#include "lldb/Core/RegularExpression.h"
14#include "lldb/Core/Timer.h"
15#include "lldb/Symbol/ObjectFile.h"
16#include "lldb/Symbol/Symtab.h"
17
18using namespace lldb;
19using namespace lldb_private;
20
21
22
23Symtab::Symtab(ObjectFile *objfile) :
24 m_objfile(objfile),
25 m_symbols(),
26 m_addr_indexes(),
27 m_name_to_index()
28{
29}
30
31Symtab::~Symtab()
32{
33}
34
35void
36Symtab::Reserve(uint32_t count)
37{
38 m_symbols.reserve (count);
39}
40
41Symbol *
42Symtab::Resize(uint32_t count)
43{
44 m_symbols.resize (count);
45 return &m_symbols[0];
46}
47
48uint32_t
49Symtab::AddSymbol(const Symbol& symbol)
50{
51 uint32_t symbol_idx = m_symbols.size();
52 m_name_to_index.Clear();
53 m_addr_indexes.clear();
54 m_symbols.push_back(symbol);
55 return symbol_idx;
56}
57
58size_t
59Symtab::GetNumSymbols() const
60{
61 return m_symbols.size();
62}
63
64void
65Symtab::Dump(Stream *s, Process *process) const
66{
67 const_iterator pos;
68 s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
69 s->Indent();
70 const FileSpec &file_spec = m_objfile->GetFileSpec();
71 const char * object_name = NULL;
72 if (m_objfile->GetModule())
73 object_name = m_objfile->GetModule()->GetObjectName().GetCString();
74
75 if (file_spec)
76 s->Printf("Symtab, file = %s/%s%s%s%s, num_symbols = %u:\n",
77 file_spec.GetDirectory().AsCString(),
78 file_spec.GetFilename().AsCString(),
79 object_name ? "(" : "",
80 object_name ? object_name : "",
81 object_name ? ")" : "",
82 m_symbols.size());
83 else
84 s->Printf("Symtab, num_symbols = %u:\n", m_symbols.size());
85 s->IndentMore();
86
87 if (!m_symbols.empty())
88 {
89 const_iterator begin = m_symbols.begin();
90 const_iterator end = m_symbols.end();
91 DumpSymbolHeader (s);
92 for (pos = m_symbols.begin(); pos != end; ++pos)
93 {
94 s->Indent();
95 pos->Dump(s, process, std::distance(begin, pos));
96 }
97 }
98 s->IndentLess ();
99}
100
101void
102Symtab::Dump(Stream *s, Process *process, std::vector<uint32_t>& indexes) const
103{
104 const size_t num_symbols = GetNumSymbols();
105 s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
106 s->Indent();
107 s->Printf("Symtab %u symbol indexes (%u symbols total):\n", indexes.size(), m_symbols.size());
108 s->IndentMore();
109
110 if (!indexes.empty())
111 {
112 std::vector<uint32_t>::const_iterator pos;
113 std::vector<uint32_t>::const_iterator end = indexes.end();
114 DumpSymbolHeader (s);
115 for (pos = indexes.begin(); pos != end; ++pos)
116 {
117 uint32_t idx = *pos;
118 if (idx < num_symbols)
119 {
120 s->Indent();
121 m_symbols[idx].Dump(s, process, idx);
122 }
123 }
124 }
125 s->IndentLess ();
126}
127
128void
129Symtab::DumpSymbolHeader (Stream *s)
130{
131 s->Indent(" Debug symbol\n");
132 s->Indent(" |Synthetic symbol\n");
133 s->Indent(" ||Externally Visible\n");
134 s->Indent(" |||\n");
135 s->Indent("Index UserID DSX Type File Address/Value Load Address Size Flags Name\n");
136 s->Indent("------- ------ --- ------------ ------------------ ------------------ ------------------ ---------- ----------------------------------\n");
137}
138
139Symbol *
140Symtab::SymbolAtIndex(uint32_t idx)
141{
142 if (idx < m_symbols.size())
143 return &m_symbols[idx];
144 return NULL;
145}
146
147
148const Symbol *
149Symtab::SymbolAtIndex(uint32_t idx) const
150{
151 if (idx < m_symbols.size())
152 return &m_symbols[idx];
153 return NULL;
154}
155
156//----------------------------------------------------------------------
157// InitNameIndexes
158//----------------------------------------------------------------------
159void
160Symtab::InitNameIndexes()
161{
162 Timer scoped_timer (__PRETTY_FUNCTION__, "%s", __PRETTY_FUNCTION__);
163 // Create the name index vector to be able to quickly search by name
164 const size_t count = m_symbols.size();
165 assert(m_objfile != NULL);
166 assert(m_objfile->GetModule() != NULL);
167 m_name_to_index.Reserve (count);
168
169 UniqueCStringMap<uint32_t>::Entry entry;
170
171 for (entry.value = 0; entry.value < count; ++entry.value)
172 {
173 const Symbol *symbol = &m_symbols[entry.value];
174
175 // Don't let trampolines get into the lookup by name map
176 // If we ever need the trampoline symbols to be searchable by name
177 // we can remove this and then possibly add a new bool to any of the
178 // Symtab functions that lookup symbols by name to indicate if they
179 // want trampolines.
180 if (symbol->IsTrampoline())
181 continue;
182
183 const Mangled &mangled = symbol->GetMangled();
184 entry.cstring = mangled.GetMangledName().GetCString();
185 if (entry.cstring && entry.cstring[0])
186 m_name_to_index.Append (entry);
187
188 entry.cstring = mangled.GetDemangledName().GetCString();
189 if (entry.cstring && entry.cstring[0])
190 m_name_to_index.Append (entry);
191 }
192 m_name_to_index.Sort();
193}
194
195uint32_t
196Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type, std::vector<uint32_t>& indexes, uint32_t start_idx, uint32_t end_index) const
197{
198 uint32_t prev_size = indexes.size();
199
200 const uint32_t count = std::min<uint32_t> (m_symbols.size(), end_index);
201
202 for (uint32_t i = start_idx; i < count; ++i)
203 {
204 if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type)
205 indexes.push_back(i);
206 }
207
208 return indexes.size() - prev_size;
209}
210
211struct SymbolSortInfo
212{
213 const bool sort_by_load_addr;
214 const Symbol *symbols;
215};
216
217int
218Symtab::CompareSymbolValueByIndex (void *thunk, const void *a, const void *b)
219{
220 const Symbol *symbols = (const Symbol *)thunk;
221 uint32_t index_a = *((uint32_t *) a);
222 uint32_t index_b = *((uint32_t *) b);
223
224 addr_t value_a;
225 addr_t value_b;
226 if (symbols[index_a].GetValue().GetSection() == symbols[index_b].GetValue().GetSection())
227 {
228 value_a = symbols[index_a].GetValue ().GetOffset();
229 value_b = symbols[index_b].GetValue ().GetOffset();
230 }
231 else
232 {
233 value_a = symbols[index_a].GetValue ().GetFileAddress();
234 value_b = symbols[index_b].GetValue ().GetFileAddress();
235 }
236
237 if (value_a == value_b)
238 {
239 // The if the values are equal, use the original symbol user ID
240 lldb::user_id_t uid_a = symbols[index_a].GetID();
241 lldb::user_id_t uid_b = symbols[index_b].GetID();
242 if (uid_a < uid_b)
243 return -1;
244 if (uid_a > uid_b)
245 return 1;
246 return 0;
247 }
248 else if (value_a < value_b)
249 return -1;
250
251 return 1;
252}
253
Greg Claytonbeb77422010-06-11 00:51:46 +0000254int Symtab::CompareSymbolValueByIndexLinux(const void* a, const void* b, void* thunk)
255{
256 return CompareSymbolValueByIndex(thunk, a, b);
Eli Friedman020f3532010-06-10 23:36:31 +0000257}
258
Chris Lattner24943d22010-06-08 16:52:24 +0000259void
260Symtab::SortSymbolIndexesByValue (std::vector<uint32_t>& indexes, bool remove_duplicates) const
261{
262 // No need to sort if we have zero or one items...
263 if (indexes.size() <= 1)
264 return;
265
266 // Sort the indexes in place using qsort
Eli Friedman020f3532010-06-10 23:36:31 +0000267 // FIXME: (WRONGDEFINE) Need a better define for this!
268#ifdef __APPLE__
Chris Lattner24943d22010-06-08 16:52:24 +0000269 ::qsort_r (&indexes[0], indexes.size(), sizeof(uint32_t), (void *)&m_symbols[0], Symtab::CompareSymbolValueByIndex);
Eli Friedman020f3532010-06-10 23:36:31 +0000270#else
271 ::qsort_r (&indexes[0], indexes.size(), sizeof(uint32_t), CompareSymbolValueByIndexLinux, (void *)&m_symbols[0]);
272#endif
Chris Lattner24943d22010-06-08 16:52:24 +0000273
274 // Remove any duplicates if requested
275 if (remove_duplicates)
276 std::unique(indexes.begin(), indexes.end());
277}
278
279uint32_t
280Symtab::AppendSymbolIndexesWithName(const ConstString& symbol_name, std::vector<uint32_t>& indexes)
281{
282 Timer scoped_timer (__PRETTY_FUNCTION__, "%s", __PRETTY_FUNCTION__);
283 if (symbol_name)
284 {
285 const size_t old_size = indexes.size();
286 if (m_name_to_index.IsEmpty())
287 InitNameIndexes();
288
289 const char *symbol_cstr = symbol_name.GetCString();
290 const UniqueCStringMap<uint32_t>::Entry *entry_ptr;
291 for (entry_ptr = m_name_to_index.FindFirstValueForName (symbol_cstr);
292 entry_ptr!= NULL;
293 entry_ptr = m_name_to_index.FindNextValueForName (symbol_cstr, entry_ptr))
294 {
295 indexes.push_back (entry_ptr->value);
296 }
297 return indexes.size() - old_size;
298 }
299 return 0;
300}
301
302uint32_t
303Symtab::AppendSymbolIndexesWithNameAndType(const ConstString& symbol_name, SymbolType symbol_type, std::vector<uint32_t>& indexes)
304{
305 if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0)
306 {
307 std::vector<uint32_t>::iterator pos = indexes.begin();
308 while (pos != indexes.end())
309 {
310 if (symbol_type == eSymbolTypeAny || m_symbols[*pos].GetType() == symbol_type)
311 ++pos;
312 else
313 indexes.erase(pos);
314 }
315 }
316 return indexes.size();
317}
318
319uint32_t
320Symtab::AppendSymbolIndexesMatchingRegExAndType (const RegularExpression &regexp, SymbolType symbol_type, std::vector<uint32_t>& indexes)
321{
322 uint32_t prev_size = indexes.size();
323 uint32_t sym_end = m_symbols.size();
324
325 for (int i = 0; i < sym_end; i++)
326 {
327 if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type)
328 {
329 const char *name = m_symbols[i].GetMangled().GetName().AsCString();
330 if (name)
331 {
332 if (regexp.Execute (name))
333 indexes.push_back(i);
334 }
335 }
336 }
337 return indexes.size() - prev_size;
338
339}
340
341Symbol *
342Symtab::FindSymbolWithType(SymbolType symbol_type, uint32_t& start_idx)
343{
344 const size_t count = m_symbols.size();
345 for (uint32_t idx = start_idx; idx < count; ++idx)
346 {
347 if (symbol_type == eSymbolTypeAny || m_symbols[idx].GetType() == symbol_type)
348 {
349 start_idx = idx;
350 return &m_symbols[idx];
351 }
352 }
353 return NULL;
354}
355
356const Symbol *
357Symtab::FindSymbolWithType(SymbolType symbol_type, uint32_t& start_idx) const
358{
359 const size_t count = m_symbols.size();
360 for (uint32_t idx = start_idx; idx < count; ++idx)
361 {
362 if (symbol_type == eSymbolTypeAny || m_symbols[idx].GetType() == symbol_type)
363 {
364 start_idx = idx;
365 return &m_symbols[idx];
366 }
367 }
368 return NULL;
369}
370
371size_t
372Symtab::FindAllSymbolsWithNameAndType (const ConstString &name, SymbolType symbol_type, std::vector<uint32_t>& symbol_indexes)
373{
374 Timer scoped_timer (__PRETTY_FUNCTION__, "%s", __PRETTY_FUNCTION__);
375 // Initialize all of the lookup by name indexes before converting NAME
376 // to a uniqued string NAME_STR below.
377 if (m_name_to_index.IsEmpty())
378 InitNameIndexes();
379
380 if (name)
381 {
382 // The string table did have a string that matched, but we need
383 // to check the symbols and match the symbol_type if any was given.
384 AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_indexes);
385 }
386 return symbol_indexes.size();
387}
388
389size_t
390Symtab::FindAllSymbolsMatchingRexExAndType (const RegularExpression &regex, SymbolType symbol_type, std::vector<uint32_t>& symbol_indexes)
391{
392 AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_indexes);
393 return symbol_indexes.size();
394}
395
396Symbol *
397Symtab::FindFirstSymbolWithNameAndType (const ConstString &name, SymbolType symbol_type)
398{
399 Timer scoped_timer (__PRETTY_FUNCTION__, "%s", __PRETTY_FUNCTION__);
400 if (m_name_to_index.IsEmpty())
401 InitNameIndexes();
402
403 if (name)
404 {
405 std::vector<uint32_t> matching_indexes;
406 // The string table did have a string that matched, but we need
407 // to check the symbols and match the symbol_type if any was given.
408 if (AppendSymbolIndexesWithNameAndType(name, symbol_type, matching_indexes))
409 {
410 std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end();
411 for (pos = matching_indexes.begin(); pos != end; ++pos)
412 {
413 Symbol *symbol = SymbolAtIndex(*pos);
414
415 if (symbol->Compare(name, symbol_type))
416 return symbol;
417 }
418 }
419 }
420 return NULL;
421}
422
423typedef struct
424{
425 const Symtab *symtab;
426 const addr_t file_addr;
427 Symbol *match_symbol;
428 const uint32_t *match_index_ptr;
429 addr_t match_offset;
430} SymbolSearchInfo;
431
432static int
433SymbolWithFileAddress (SymbolSearchInfo *info, const uint32_t *index_ptr)
434{
435 const Symbol *curr_symbol = info->symtab->SymbolAtIndex (index_ptr[0]);
436 if (curr_symbol == NULL)
437 return -1;
438
439 const addr_t info_file_addr = info->file_addr;
440
441 // lldb::Symbol::GetAddressRangePtr() will only return a non NULL address
442 // range if the symbol has a section!
443 const AddressRange *curr_range = curr_symbol->GetAddressRangePtr();
444 if (curr_range)
445 {
446 const addr_t curr_file_addr = curr_range->GetBaseAddress().GetFileAddress();
447 if (info_file_addr < curr_file_addr)
448 return -1;
449 if (info_file_addr > curr_file_addr)
450 return +1;
451 info->match_symbol = const_cast<Symbol *>(curr_symbol);
452 info->match_index_ptr = index_ptr;
453 return 0;
454 }
455
456 return -1;
457}
458
459static int
460SymbolWithClosestFileAddress (SymbolSearchInfo *info, const uint32_t *index_ptr)
461{
462 const Symbol *symbol = info->symtab->SymbolAtIndex (index_ptr[0]);
463 if (symbol == NULL)
464 return -1;
465
466 const addr_t info_file_addr = info->file_addr;
467 const AddressRange *curr_range = symbol->GetAddressRangePtr();
468 if (curr_range)
469 {
470 const addr_t curr_file_addr = curr_range->GetBaseAddress().GetFileAddress();
471 if (info_file_addr < curr_file_addr)
472 return -1;
473
474 // Since we are finding the closest symbol that is greater than or equal
475 // to 'info->file_addr' we set the symbol here. This will get set
476 // multiple times, but after the search is done it will contain the best
477 // symbol match
478 info->match_symbol = const_cast<Symbol *>(symbol);
479 info->match_index_ptr = index_ptr;
480 info->match_offset = info_file_addr - curr_file_addr;
481
482 if (info_file_addr > curr_file_addr)
483 return +1;
484 return 0;
485 }
486 return -1;
487}
488
489static SymbolSearchInfo
490FindIndexPtrForSymbolContainingAddress(Symtab* symtab, addr_t file_addr, const uint32_t* indexes, uint32_t num_indexes)
491{
492 SymbolSearchInfo info = { symtab, file_addr, NULL, NULL, 0 };
493 bsearch(&info, indexes, num_indexes, sizeof(uint32_t), (comparison_function)SymbolWithClosestFileAddress);
494 return info;
495}
496
497
498void
499Symtab::InitAddressIndexes()
500{
501 if (m_addr_indexes.empty())
502 {
503 AppendSymbolIndexesWithType (eSymbolTypeFunction, m_addr_indexes);
504 AppendSymbolIndexesWithType (eSymbolTypeGlobal, m_addr_indexes);
505 AppendSymbolIndexesWithType (eSymbolTypeStatic, m_addr_indexes);
506 AppendSymbolIndexesWithType (eSymbolTypeCode, m_addr_indexes);
507 AppendSymbolIndexesWithType (eSymbolTypeTrampoline, m_addr_indexes);
508 AppendSymbolIndexesWithType (eSymbolTypeData, m_addr_indexes);
509 SortSymbolIndexesByValue(m_addr_indexes, true);
510 m_addr_indexes.push_back(UINT32_MAX); // Terminator for bsearch since we might need to look at the next symbol
511 }
512}
513
514size_t
515Symtab::CalculateSymbolSize (Symbol *symbol)
516{
517 // Make sure this symbol is from this symbol table...
518 if (symbol < m_symbols.data() && symbol >= m_symbols.data() + m_symbols.size())
519 return 0;
520
521 // See if this symbol already has a byte size?
522 size_t byte_size = symbol->GetByteSize();
523
524 if (byte_size)
525 {
526 // It does, just return it
527 return byte_size;
528 }
529
530 // Else if this is an address based symbol, figure out the delta between
531 // it and the next address based symbol
532 if (symbol->GetAddressRangePtr())
533 {
534 if (m_addr_indexes.empty())
535 InitAddressIndexes();
536 const size_t num_addr_indexes = m_addr_indexes.size();
537 SymbolSearchInfo info = FindIndexPtrForSymbolContainingAddress(this, symbol->GetAddressRangePtr()->GetBaseAddress().GetFileAddress(), m_addr_indexes.data(), num_addr_indexes);
538 if (info.match_index_ptr != NULL)
539 {
540 const lldb::addr_t curr_file_addr = symbol->GetAddressRangePtr()->GetBaseAddress().GetFileAddress();
541 // We can figure out the address range of all symbols except the
542 // last one by taking the delta between the current symbol and
543 // the next symbol
544
545 for (uint32_t addr_index = info.match_index_ptr - m_addr_indexes.data() + 1;
546 addr_index < num_addr_indexes;
547 ++addr_index)
548 {
549 Symbol *next_symbol = SymbolAtIndex(m_addr_indexes[addr_index]);
550 if (next_symbol == NULL)
551 break;
552
553 assert (next_symbol->GetAddressRangePtr());
554 const lldb::addr_t next_file_addr = next_symbol->GetAddressRangePtr()->GetBaseAddress().GetFileAddress();
555 if (next_file_addr > curr_file_addr)
556 {
557 byte_size = next_file_addr - curr_file_addr;
558 symbol->GetAddressRangePtr()->SetByteSize(byte_size);
559 symbol->SetSizeIsSynthesized(true);
560 break;
561 }
562 }
563 }
564 }
565 return byte_size;
566}
567
568Symbol *
569Symtab::FindSymbolWithFileAddress (addr_t file_addr)
570{
571 if (m_addr_indexes.empty())
572 InitAddressIndexes();
573
574 SymbolSearchInfo info = { this, file_addr, NULL, NULL, 0 };
575
576 uint32_t* match = (uint32_t*)bsearch(&info, &m_addr_indexes[0], m_addr_indexes.size(), sizeof(uint32_t), (comparison_function)SymbolWithFileAddress);
577 if (match)
578 return SymbolAtIndex (*match);
579 return NULL;
580}
581
582
583Symbol *
584Symtab::FindSymbolContainingFileAddress (addr_t file_addr, const uint32_t* indexes, uint32_t num_indexes)
585{
586 SymbolSearchInfo info = { this, file_addr, NULL, NULL, 0 };
587
588 bsearch(&info, indexes, num_indexes, sizeof(uint32_t), (comparison_function)SymbolWithClosestFileAddress);
589
590 if (info.match_symbol)
591 {
592 if (info.match_offset < CalculateSymbolSize(info.match_symbol))
593 return info.match_symbol;
594 }
595 return NULL;
596}
597
598Symbol *
599Symtab::FindSymbolContainingFileAddress (addr_t file_addr)
600{
601 if (m_addr_indexes.empty())
602 InitAddressIndexes();
603
604 return FindSymbolContainingFileAddress (file_addr, &m_addr_indexes[0], m_addr_indexes.size());
605}
606