blob: f1ed356d44b298c3177aa6f85109f7f80d6a8569 [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
254void
255Symtab::SortSymbolIndexesByValue (std::vector<uint32_t>& indexes, bool remove_duplicates) const
256{
257 // No need to sort if we have zero or one items...
258 if (indexes.size() <= 1)
259 return;
260
261 // Sort the indexes in place using qsort
262 ::qsort_r (&indexes[0], indexes.size(), sizeof(uint32_t), (void *)&m_symbols[0], Symtab::CompareSymbolValueByIndex);
263
264 // Remove any duplicates if requested
265 if (remove_duplicates)
266 std::unique(indexes.begin(), indexes.end());
267}
268
269uint32_t
270Symtab::AppendSymbolIndexesWithName(const ConstString& symbol_name, std::vector<uint32_t>& indexes)
271{
272 Timer scoped_timer (__PRETTY_FUNCTION__, "%s", __PRETTY_FUNCTION__);
273 if (symbol_name)
274 {
275 const size_t old_size = indexes.size();
276 if (m_name_to_index.IsEmpty())
277 InitNameIndexes();
278
279 const char *symbol_cstr = symbol_name.GetCString();
280 const UniqueCStringMap<uint32_t>::Entry *entry_ptr;
281 for (entry_ptr = m_name_to_index.FindFirstValueForName (symbol_cstr);
282 entry_ptr!= NULL;
283 entry_ptr = m_name_to_index.FindNextValueForName (symbol_cstr, entry_ptr))
284 {
285 indexes.push_back (entry_ptr->value);
286 }
287 return indexes.size() - old_size;
288 }
289 return 0;
290}
291
292uint32_t
293Symtab::AppendSymbolIndexesWithNameAndType(const ConstString& symbol_name, SymbolType symbol_type, std::vector<uint32_t>& indexes)
294{
295 if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0)
296 {
297 std::vector<uint32_t>::iterator pos = indexes.begin();
298 while (pos != indexes.end())
299 {
300 if (symbol_type == eSymbolTypeAny || m_symbols[*pos].GetType() == symbol_type)
301 ++pos;
302 else
303 indexes.erase(pos);
304 }
305 }
306 return indexes.size();
307}
308
309uint32_t
310Symtab::AppendSymbolIndexesMatchingRegExAndType (const RegularExpression &regexp, SymbolType symbol_type, std::vector<uint32_t>& indexes)
311{
312 uint32_t prev_size = indexes.size();
313 uint32_t sym_end = m_symbols.size();
314
315 for (int i = 0; i < sym_end; i++)
316 {
317 if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type)
318 {
319 const char *name = m_symbols[i].GetMangled().GetName().AsCString();
320 if (name)
321 {
322 if (regexp.Execute (name))
323 indexes.push_back(i);
324 }
325 }
326 }
327 return indexes.size() - prev_size;
328
329}
330
331Symbol *
332Symtab::FindSymbolWithType(SymbolType symbol_type, uint32_t& start_idx)
333{
334 const size_t count = m_symbols.size();
335 for (uint32_t idx = start_idx; idx < count; ++idx)
336 {
337 if (symbol_type == eSymbolTypeAny || m_symbols[idx].GetType() == symbol_type)
338 {
339 start_idx = idx;
340 return &m_symbols[idx];
341 }
342 }
343 return NULL;
344}
345
346const Symbol *
347Symtab::FindSymbolWithType(SymbolType symbol_type, uint32_t& start_idx) const
348{
349 const size_t count = m_symbols.size();
350 for (uint32_t idx = start_idx; idx < count; ++idx)
351 {
352 if (symbol_type == eSymbolTypeAny || m_symbols[idx].GetType() == symbol_type)
353 {
354 start_idx = idx;
355 return &m_symbols[idx];
356 }
357 }
358 return NULL;
359}
360
361size_t
362Symtab::FindAllSymbolsWithNameAndType (const ConstString &name, SymbolType symbol_type, std::vector<uint32_t>& symbol_indexes)
363{
364 Timer scoped_timer (__PRETTY_FUNCTION__, "%s", __PRETTY_FUNCTION__);
365 // Initialize all of the lookup by name indexes before converting NAME
366 // to a uniqued string NAME_STR below.
367 if (m_name_to_index.IsEmpty())
368 InitNameIndexes();
369
370 if (name)
371 {
372 // The string table did have a string that matched, but we need
373 // to check the symbols and match the symbol_type if any was given.
374 AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_indexes);
375 }
376 return symbol_indexes.size();
377}
378
379size_t
380Symtab::FindAllSymbolsMatchingRexExAndType (const RegularExpression &regex, SymbolType symbol_type, std::vector<uint32_t>& symbol_indexes)
381{
382 AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_indexes);
383 return symbol_indexes.size();
384}
385
386Symbol *
387Symtab::FindFirstSymbolWithNameAndType (const ConstString &name, SymbolType symbol_type)
388{
389 Timer scoped_timer (__PRETTY_FUNCTION__, "%s", __PRETTY_FUNCTION__);
390 if (m_name_to_index.IsEmpty())
391 InitNameIndexes();
392
393 if (name)
394 {
395 std::vector<uint32_t> matching_indexes;
396 // The string table did have a string that matched, but we need
397 // to check the symbols and match the symbol_type if any was given.
398 if (AppendSymbolIndexesWithNameAndType(name, symbol_type, matching_indexes))
399 {
400 std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end();
401 for (pos = matching_indexes.begin(); pos != end; ++pos)
402 {
403 Symbol *symbol = SymbolAtIndex(*pos);
404
405 if (symbol->Compare(name, symbol_type))
406 return symbol;
407 }
408 }
409 }
410 return NULL;
411}
412
413typedef struct
414{
415 const Symtab *symtab;
416 const addr_t file_addr;
417 Symbol *match_symbol;
418 const uint32_t *match_index_ptr;
419 addr_t match_offset;
420} SymbolSearchInfo;
421
422static int
423SymbolWithFileAddress (SymbolSearchInfo *info, const uint32_t *index_ptr)
424{
425 const Symbol *curr_symbol = info->symtab->SymbolAtIndex (index_ptr[0]);
426 if (curr_symbol == NULL)
427 return -1;
428
429 const addr_t info_file_addr = info->file_addr;
430
431 // lldb::Symbol::GetAddressRangePtr() will only return a non NULL address
432 // range if the symbol has a section!
433 const AddressRange *curr_range = curr_symbol->GetAddressRangePtr();
434 if (curr_range)
435 {
436 const addr_t curr_file_addr = curr_range->GetBaseAddress().GetFileAddress();
437 if (info_file_addr < curr_file_addr)
438 return -1;
439 if (info_file_addr > curr_file_addr)
440 return +1;
441 info->match_symbol = const_cast<Symbol *>(curr_symbol);
442 info->match_index_ptr = index_ptr;
443 return 0;
444 }
445
446 return -1;
447}
448
449static int
450SymbolWithClosestFileAddress (SymbolSearchInfo *info, const uint32_t *index_ptr)
451{
452 const Symbol *symbol = info->symtab->SymbolAtIndex (index_ptr[0]);
453 if (symbol == NULL)
454 return -1;
455
456 const addr_t info_file_addr = info->file_addr;
457 const AddressRange *curr_range = symbol->GetAddressRangePtr();
458 if (curr_range)
459 {
460 const addr_t curr_file_addr = curr_range->GetBaseAddress().GetFileAddress();
461 if (info_file_addr < curr_file_addr)
462 return -1;
463
464 // Since we are finding the closest symbol that is greater than or equal
465 // to 'info->file_addr' we set the symbol here. This will get set
466 // multiple times, but after the search is done it will contain the best
467 // symbol match
468 info->match_symbol = const_cast<Symbol *>(symbol);
469 info->match_index_ptr = index_ptr;
470 info->match_offset = info_file_addr - curr_file_addr;
471
472 if (info_file_addr > curr_file_addr)
473 return +1;
474 return 0;
475 }
476 return -1;
477}
478
479static SymbolSearchInfo
480FindIndexPtrForSymbolContainingAddress(Symtab* symtab, addr_t file_addr, const uint32_t* indexes, uint32_t num_indexes)
481{
482 SymbolSearchInfo info = { symtab, file_addr, NULL, NULL, 0 };
483 bsearch(&info, indexes, num_indexes, sizeof(uint32_t), (comparison_function)SymbolWithClosestFileAddress);
484 return info;
485}
486
487
488void
489Symtab::InitAddressIndexes()
490{
491 if (m_addr_indexes.empty())
492 {
493 AppendSymbolIndexesWithType (eSymbolTypeFunction, m_addr_indexes);
494 AppendSymbolIndexesWithType (eSymbolTypeGlobal, m_addr_indexes);
495 AppendSymbolIndexesWithType (eSymbolTypeStatic, m_addr_indexes);
496 AppendSymbolIndexesWithType (eSymbolTypeCode, m_addr_indexes);
497 AppendSymbolIndexesWithType (eSymbolTypeTrampoline, m_addr_indexes);
498 AppendSymbolIndexesWithType (eSymbolTypeData, m_addr_indexes);
499 SortSymbolIndexesByValue(m_addr_indexes, true);
500 m_addr_indexes.push_back(UINT32_MAX); // Terminator for bsearch since we might need to look at the next symbol
501 }
502}
503
504size_t
505Symtab::CalculateSymbolSize (Symbol *symbol)
506{
507 // Make sure this symbol is from this symbol table...
508 if (symbol < m_symbols.data() && symbol >= m_symbols.data() + m_symbols.size())
509 return 0;
510
511 // See if this symbol already has a byte size?
512 size_t byte_size = symbol->GetByteSize();
513
514 if (byte_size)
515 {
516 // It does, just return it
517 return byte_size;
518 }
519
520 // Else if this is an address based symbol, figure out the delta between
521 // it and the next address based symbol
522 if (symbol->GetAddressRangePtr())
523 {
524 if (m_addr_indexes.empty())
525 InitAddressIndexes();
526 const size_t num_addr_indexes = m_addr_indexes.size();
527 SymbolSearchInfo info = FindIndexPtrForSymbolContainingAddress(this, symbol->GetAddressRangePtr()->GetBaseAddress().GetFileAddress(), m_addr_indexes.data(), num_addr_indexes);
528 if (info.match_index_ptr != NULL)
529 {
530 const lldb::addr_t curr_file_addr = symbol->GetAddressRangePtr()->GetBaseAddress().GetFileAddress();
531 // We can figure out the address range of all symbols except the
532 // last one by taking the delta between the current symbol and
533 // the next symbol
534
535 for (uint32_t addr_index = info.match_index_ptr - m_addr_indexes.data() + 1;
536 addr_index < num_addr_indexes;
537 ++addr_index)
538 {
539 Symbol *next_symbol = SymbolAtIndex(m_addr_indexes[addr_index]);
540 if (next_symbol == NULL)
541 break;
542
543 assert (next_symbol->GetAddressRangePtr());
544 const lldb::addr_t next_file_addr = next_symbol->GetAddressRangePtr()->GetBaseAddress().GetFileAddress();
545 if (next_file_addr > curr_file_addr)
546 {
547 byte_size = next_file_addr - curr_file_addr;
548 symbol->GetAddressRangePtr()->SetByteSize(byte_size);
549 symbol->SetSizeIsSynthesized(true);
550 break;
551 }
552 }
553 }
554 }
555 return byte_size;
556}
557
558Symbol *
559Symtab::FindSymbolWithFileAddress (addr_t file_addr)
560{
561 if (m_addr_indexes.empty())
562 InitAddressIndexes();
563
564 SymbolSearchInfo info = { this, file_addr, NULL, NULL, 0 };
565
566 uint32_t* match = (uint32_t*)bsearch(&info, &m_addr_indexes[0], m_addr_indexes.size(), sizeof(uint32_t), (comparison_function)SymbolWithFileAddress);
567 if (match)
568 return SymbolAtIndex (*match);
569 return NULL;
570}
571
572
573Symbol *
574Symtab::FindSymbolContainingFileAddress (addr_t file_addr, const uint32_t* indexes, uint32_t num_indexes)
575{
576 SymbolSearchInfo info = { this, file_addr, NULL, NULL, 0 };
577
578 bsearch(&info, indexes, num_indexes, sizeof(uint32_t), (comparison_function)SymbolWithClosestFileAddress);
579
580 if (info.match_symbol)
581 {
582 if (info.match_offset < CalculateSymbolSize(info.match_symbol))
583 return info.match_symbol;
584 }
585 return NULL;
586}
587
588Symbol *
589Symtab::FindSymbolContainingFileAddress (addr_t file_addr)
590{
591 if (m_addr_indexes.empty())
592 InitAddressIndexes();
593
594 return FindSymbolContainingFileAddress (file_addr, &m_addr_indexes[0], m_addr_indexes.size());
595}
596