Symtab.cpp revision beb7742b18e7d1e5afe9555d6656fe38d514386f
1//===-- 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 254int Symtab::CompareSymbolValueByIndexLinux(const void* a, const void* b, void* thunk) 255{ 256 return CompareSymbolValueByIndex(thunk, a, b); 257} 258 259void 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 267 // FIXME: (WRONGDEFINE) Need a better define for this! 268#ifdef __APPLE__ 269 ::qsort_r (&indexes[0], indexes.size(), sizeof(uint32_t), (void *)&m_symbols[0], Symtab::CompareSymbolValueByIndex); 270#else 271 ::qsort_r (&indexes[0], indexes.size(), sizeof(uint32_t), CompareSymbolValueByIndexLinux, (void *)&m_symbols[0]); 272#endif 273 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 ®exp, 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 ®ex, 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 607