HashedNameToDIE.h revision 37bb8ddd443da172f42bb8657f15ec856a525c84
1//===-- HashedNameToDIE.h ---------------------------------------*- 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#ifndef SymbolFileDWARF_HashedNameToDIE_h_ 11#define SymbolFileDWARF_HashedNameToDIE_h_ 12 13#include <vector> 14 15#include "DWARFFormValue.h" 16 17#include "lldb/lldb-defines.h" 18#include "lldb/Core/dwarf.h" 19#include "lldb/Core/RegularExpression.h" 20#include "lldb/Core/MappedHash.h" 21 22 23class SymbolFileDWARF; 24class DWARFCompileUnit; 25class DWARFDebugInfoEntry; 26 27struct DWARFMappedHash 28{ 29 struct DIEInfo 30 { 31 dw_offset_t offset; // The DIE offset 32 uint32_t type_flags; // Any flags for this DIEInfo 33 34 DIEInfo (dw_offset_t _offset = DW_INVALID_OFFSET, 35 uint32_t _type_flags = 0) : 36 offset(_offset), 37 type_flags (_type_flags) 38 { 39 } 40 41 void 42 Clear() 43 { 44 offset = DW_INVALID_OFFSET; 45 type_flags = 0; 46 } 47 }; 48 49 typedef std::vector<DIEInfo> DIEInfoArray; 50 typedef std::vector<uint32_t> DIEArray; 51 52 static void 53 ExtractDIEArray (const DIEInfoArray &die_info_array, 54 DIEArray &die_offsets) 55 { 56 const size_t count = die_info_array.size(); 57 for (size_t i=0; i<count; ++i) 58 { 59 die_offsets.push_back (die_info_array[i].offset); 60 } 61 } 62 63 enum AtomType 64 { 65 eAtomTypeNULL = 0u, 66 eAtomTypeDIEOffset = 1u, // DIE offset, check form for encoding 67 eAtomTypeCUOffset = 2u, // DIE offset of the compiler unit header that contains the item in question 68 eAtomTypeTag = 3u, // DW_TAG_xxx value, should be encoded as DW_FORM_data1 (if no tags exceed 255) or DW_FORM_data2 69 eAtomTypeNameFlags = 4u, // Flags from enum NameFlags 70 eAtomTypeTypeFlags = 5u // Flags from enum TypeFlags 71 }; 72 73 // Held in bits[3:0] of the eAtomTypeTypeFlags value to help us know what kind of type 74 // the name is describing 75 enum TypeFlagsTypeClass 76 { 77 eTypeClassInvalid = 0u, // An invalid type class, this might happend when type flags were not correctly set 78 eTypeClassOther = 1u, // A type other than any listed below 79 eTypeClassBuiltIn = 2u, // Language built in type 80 eTypeClassClassOrStruct = 3u, // A class or structure, just not an objective C class 81 eTypeClassClassOBJC = 4u, 82 eTypeClassEnum = 5u, 83 eTypeClassTypedef = 7u, 84 eTypeClassUnion = 8u 85 }; 86 87 // Other type bits for the eAtomTypeTypeFlags flags 88 89 enum TypeFlags 90 { 91 // Make bits [3:0] of the eAtomTypeTypeFlags value and see TypeFlagsTypeClass 92 eTypeFlagClassMask = 0x0000000fu, 93 94 // If the name contains the namespace and class scope or the type 95 // exists in the global namespace, then this bits should be set 96 eTypeFlagNameIsFullyQualified = ( 1u << 4 ), 97 98 // Always set for C++, only set for ObjC if this is the 99 // @implementation for class 100 eTypeFlagClassIsImplementation = ( 1u << 5 ), 101 102 }; 103 104 struct Atom 105 { 106 uint16_t type; 107 dw_form_t form; 108 109 Atom (uint16_t t = eAtomTypeNULL, dw_form_t f = 0) : 110 type (t), 111 form (f) 112 { 113 } 114 }; 115 116 typedef std::vector<Atom> AtomArray; 117 118 static uint32_t 119 GetTypeFlags (SymbolFileDWARF *dwarf2Data, 120 const DWARFCompileUnit* cu, 121 const DWARFDebugInfoEntry* die); 122 123 124 static const char * 125 GetAtomTypeName (uint16_t atom) 126 { 127 switch (atom) 128 { 129 case eAtomTypeNULL: return "NULL"; 130 case eAtomTypeDIEOffset: return "die-offset"; 131 case eAtomTypeCUOffset: return "cu-offset"; 132 case eAtomTypeTag: return "die-tag"; 133 case eAtomTypeNameFlags: return "name-flags"; 134 case eAtomTypeTypeFlags: return "type-flags"; 135 } 136 return "<invalid>"; 137 } 138 struct Prologue 139 { 140 // DIE offset base so die offsets in hash_data can be CU relative 141 dw_offset_t die_base_offset; 142 AtomArray atoms; 143 size_t min_hash_data_byte_size; 144 145 Prologue (dw_offset_t _die_base_offset = 0) : 146 die_base_offset (_die_base_offset), 147 atoms(), 148 min_hash_data_byte_size(0) 149 { 150 // Define an array of DIE offsets by first defining an array, 151 // and then define the atom type for the array, in this case 152 // we have an array of DIE offsets 153 AppendAtom (eAtomTypeDIEOffset, DW_FORM_data4); 154 min_hash_data_byte_size = 4; 155 } 156 157 virtual ~Prologue() 158 { 159 } 160 161 virtual void 162 Clear () 163 { 164 die_base_offset = 0; 165 atoms.clear(); 166 } 167 168 void 169 AppendAtom (AtomType type, dw_form_t form) 170 { 171 atoms.push_back (Atom(type, form)); 172 switch (form) 173 { 174 case DW_FORM_indirect: 175 case DW_FORM_exprloc: 176 case DW_FORM_flag_present: 177 case DW_FORM_ref_sig8: 178 assert (!"Unhandled atom form"); 179 break; 180 181 case DW_FORM_string: 182 case DW_FORM_block: 183 case DW_FORM_block1: 184 case DW_FORM_flag: 185 case DW_FORM_data1: 186 case DW_FORM_ref1: 187 case DW_FORM_sdata: 188 case DW_FORM_udata: 189 case DW_FORM_sec_offset: 190 case DW_FORM_ref_udata: 191 min_hash_data_byte_size += 1; 192 break; 193 case DW_FORM_block2: 194 case DW_FORM_data2: 195 case DW_FORM_ref2: 196 min_hash_data_byte_size += 2; 197 break; 198 case DW_FORM_block4: 199 case DW_FORM_data4: 200 case DW_FORM_ref4: 201 case DW_FORM_addr: 202 case DW_FORM_ref_addr: 203 case DW_FORM_strp: 204 min_hash_data_byte_size += 4; 205 break; 206 case DW_FORM_data8: 207 case DW_FORM_ref8: 208 min_hash_data_byte_size += 8; 209 break; 210 211 } 212 } 213 214// void 215// Dump (std::ostream* ostrm_ptr); 216 217 uint32_t 218 Read (const lldb_private::DataExtractor &data, uint32_t offset) 219 { 220 atoms.clear(); 221 222 die_base_offset = data.GetU32 (&offset); 223 224 const uint32_t atom_count = data.GetU32 (&offset); 225 if (atom_count == 0x00060003u) 226 { 227 // Old format, deal with contents of old pre-release format 228 while (data.GetU32(&offset)) 229 /* do nothing */; 230 231 // Hardcode to the only know value for now. 232 AppendAtom (eAtomTypeDIEOffset, DW_FORM_data4); 233 } 234 else 235 { 236 for (uint32_t i=0; i<atom_count; ++i) 237 { 238 AtomType type = (AtomType)data.GetU16 (&offset); 239 dw_form_t form = (dw_form_t)data.GetU16 (&offset); 240 AppendAtom (type, form); 241 } 242 } 243 return offset; 244 } 245 246// virtual void 247// Write (BinaryStreamBuf &s); 248 249 size_t 250 GetByteSize () const 251 { 252 // Add an extra count to the atoms size for the zero termination Atom that gets 253 // written to disk 254 return sizeof(die_base_offset) + sizeof(uint32_t) + atoms.size() * sizeof(Atom); 255 } 256 257 size_t 258 GetHashDataByteSize () const 259 { 260 return min_hash_data_byte_size; 261 } 262 263 }; 264 265 struct Header : public MappedHash::Header<Prologue> 266 { 267 Header (dw_offset_t _die_base_offset = 0) 268 { 269 } 270 271 virtual 272 ~Header() 273 { 274 } 275 276 virtual size_t 277 GetByteSize (const HeaderData &header_data) 278 { 279 return header_data.GetByteSize(); 280 } 281 282 size_t 283 GetHashDataByteSize () 284 { 285 return header_data.GetHashDataByteSize(); 286 } 287 288 // virtual void 289 // Dump (std::ostream* ostrm_ptr); 290 // 291 virtual uint32_t 292 Read (lldb_private::DataExtractor &data, uint32_t offset) 293 { 294 offset = MappedHash::Header<Prologue>::Read (data, offset); 295 if (offset != UINT32_MAX) 296 { 297 offset = header_data.Read (data, offset); 298 } 299 return offset; 300 } 301 302 bool 303 Read (const lldb_private::DataExtractor &data, 304 uint32_t *offset_ptr, 305 DIEInfo &hash_data) const 306 { 307 const size_t num_atoms = header_data.atoms.size(); 308 if (num_atoms == 0) 309 return false; 310 311 for (size_t i=0; i<num_atoms; ++i) 312 { 313 DWARFFormValue form_value (header_data.atoms[i].form); 314 315 if (!form_value.ExtractValue(data, offset_ptr, NULL)) 316 return false; 317 318 switch (header_data.atoms[i].type) 319 { 320 case eAtomTypeDIEOffset: // DIE offset, check form for encoding 321 hash_data.offset = form_value.Reference (header_data.die_base_offset); 322 break; 323 case eAtomTypeTypeFlags: // Flags from enum TypeFlags 324 hash_data.type_flags = form_value.Unsigned (); 325 break; 326 default: 327 return false; 328 break; 329 } 330 } 331 return true; 332 } 333 334 void 335 Dump (lldb_private::Stream& strm, const DIEInfo &hash_data) const 336 { 337 const size_t num_atoms = header_data.atoms.size(); 338 for (size_t i=0; i<num_atoms; ++i) 339 { 340 if (i > 0) 341 strm.PutCString (", "); 342 343 DWARFFormValue form_value (header_data.atoms[i].form); 344 switch (header_data.atoms[i].type) 345 { 346 case eAtomTypeDIEOffset: // DIE offset, check form for encoding 347 strm.Printf ("0x%8.8x", hash_data.offset); 348 break; 349 350 case eAtomTypeTypeFlags: // Flags from enum TypeFlags 351 strm.Printf ("0x%2.2x ( type = ", hash_data.type_flags); 352 switch (hash_data.type_flags & eTypeFlagClassMask) 353 { 354 case eTypeClassInvalid: strm.PutCString ("invalid"); break; 355 case eTypeClassOther: strm.PutCString ("other"); break; 356 case eTypeClassBuiltIn: strm.PutCString ("built-in"); break; 357 case eTypeClassClassOrStruct: strm.PutCString ("class-struct"); break; 358 case eTypeClassClassOBJC: strm.PutCString ("class-objc"); break; 359 case eTypeClassEnum: strm.PutCString ("enum"); break; 360 case eTypeClassTypedef: strm.PutCString ("typedef"); break; 361 case eTypeClassUnion: strm.PutCString ("union"); break; 362 default: strm.PutCString ("???"); break; 363 } 364 365 if (hash_data.type_flags & ~eTypeFlagClassMask) 366 { 367 strm.PutCString (", flags ="); 368 if (hash_data.type_flags & eTypeFlagNameIsFullyQualified) 369 strm.PutCString (" qualified"); 370 371 if (hash_data.type_flags & eTypeFlagClassIsImplementation) 372 strm.PutCString (" implementation"); 373 } 374 strm.PutCString (" )"); 375 break; 376 377 default: 378 strm.Printf ("AtomType(0x%x)", header_data.atoms[i].type); 379 break; 380 } 381 } 382 } 383 384 }; 385 386// class ExportTable 387// { 388// public: 389// ExportTable (); 390// 391// void 392// AppendNames (DWARFDebugPubnamesSet &pubnames_set, 393// StringTable &string_table); 394// 395// void 396// AppendNamesEntry (SymbolFileDWARF *dwarf2Data, 397// const DWARFCompileUnit* cu, 398// const DWARFDebugInfoEntry* die, 399// StringTable &string_table); 400// 401// void 402// AppendTypesEntry (DWARFData *dwarf2Data, 403// const DWARFCompileUnit* cu, 404// const DWARFDebugInfoEntry* die, 405// StringTable &string_table); 406// 407// size_t 408// Save (BinaryStreamBuf &names_data, const StringTable &string_table); 409// 410// void 411// AppendName (const char *name, 412// uint32_t die_offset, 413// StringTable &string_table, 414// dw_offset_t name_debug_str_offset = DW_INVALID_OFFSET); // If "name" has already been looked up, then it can be supplied 415// void 416// AppendType (const char *name, 417// uint32_t die_offset, 418// StringTable &string_table); 419// 420// 421// protected: 422// struct Entry 423// { 424// uint32_t hash; 425// uint32_t str_offset; 426// uint32_t die_offset; 427// }; 428// 429// // Map uniqued .debug_str offset to the corresponding DIE offsets 430// typedef std::map<uint32_t, DIEInfoArray> NameInfo; 431// // Map a name hash to one or more name infos 432// typedef std::map<uint32_t, NameInfo> BucketEntry; 433// 434// static uint32_t 435// GetByteSize (const NameInfo &name_info); 436// 437// typedef std::vector<BucketEntry> BucketEntryColl; 438// typedef std::vector<Entry> EntryColl; 439// EntryColl m_entries; 440// 441// }; 442 443 444 // A class for reading and using a saved hash table from a block of data 445 // in memory 446 class MemoryTable : public MappedHash::MemoryTable<uint32_t, DWARFMappedHash::Header, DIEInfoArray> 447 { 448 public: 449 450 MemoryTable (lldb_private::DataExtractor &table_data, 451 const lldb_private::DataExtractor &string_table, 452 const char *name) : 453 MappedHash::MemoryTable<uint32_t, Header, DIEInfoArray> (table_data), 454 m_data (table_data), 455 m_string_table (string_table), 456 m_name (name) 457 { 458 } 459 460 virtual 461 ~MemoryTable () 462 { 463 } 464 465 virtual const char * 466 GetStringForKeyType (KeyType key) const 467 { 468 // The key in the DWARF table is the .debug_str offset for the string 469 return m_string_table.PeekCStr (key); 470 } 471 472 virtual Result 473 GetHashDataForName (const char *name, 474 uint32_t* hash_data_offset_ptr, 475 Pair &pair) const 476 { 477 pair.key = m_data.GetU32 (hash_data_offset_ptr); 478 // If the key is zero, this terminates our chain of HashData objects 479 // for this hash value. 480 if (pair.key == 0) 481 return eResultEndOfHashData; 482 483 // There definitely should be a string for this string offset, if 484 // there isn't, there is something wrong, return and error 485 const char *strp_cstr = m_string_table.PeekCStr (pair.key); 486 if (strp_cstr == NULL) 487 return eResultError; 488 489 const uint32_t count = m_data.GetU32 (hash_data_offset_ptr); 490 const uint32_t data_size = count * m_header.header_data.GetHashDataByteSize(); 491 if (count > 0 && m_data.ValidOffsetForDataOfSize (*hash_data_offset_ptr, data_size)) 492 { 493 if (strcmp (name, strp_cstr) == 0) 494 { 495 pair.value.clear(); 496 for (uint32_t i=0; i<count; ++i) 497 { 498 DIEInfo die_info; 499 if (m_header.Read(m_data, hash_data_offset_ptr, die_info)) 500 pair.value.push_back (die_info); 501 } 502 return eResultKeyMatch; 503 } 504 else 505 { 506 // Skip the data so we are ready to parse another HashData 507 // for this hash value 508 *hash_data_offset_ptr += data_size; 509 // The key doesn't match 510 return eResultKeyMismatch; 511 } 512 } 513 else 514 { 515 *hash_data_offset_ptr = UINT32_MAX; 516 return eResultError; 517 } 518 } 519 520 virtual Result 521 AppendHashDataForRegularExpression (const lldb_private::RegularExpression& regex, 522 uint32_t* hash_data_offset_ptr, 523 Pair &pair) const 524 { 525 pair.key = m_data.GetU32 (hash_data_offset_ptr); 526 // If the key is zero, this terminates our chain of HashData objects 527 // for this hash value. 528 if (pair.key == 0) 529 return eResultEndOfHashData; 530 531 // There definitely should be a string for this string offset, if 532 // there isn't, there is something wrong, return and error 533 const char *strp_cstr = m_string_table.PeekCStr (pair.key); 534 if (strp_cstr == NULL) 535 return eResultError; 536 537 const uint32_t count = m_data.GetU32 (hash_data_offset_ptr); 538 const uint32_t data_size = count * m_header.header_data.GetHashDataByteSize(); 539 if (count > 0 && m_data.ValidOffsetForDataOfSize (*hash_data_offset_ptr, data_size)) 540 { 541 if (regex.Execute(strp_cstr)) 542 { 543 for (uint32_t i=0; i<count; ++i) 544 { 545 DIEInfo die_info; 546 if (m_header.Read(m_data, hash_data_offset_ptr, die_info)) 547 pair.value.push_back (die_info); 548 } 549 return eResultKeyMatch; 550 } 551 else 552 { 553 // Skip the data so we are ready to parse another HashData 554 // for this hash value 555 *hash_data_offset_ptr += data_size; 556 // The key doesn't match 557 return eResultKeyMismatch; 558 } 559 } 560 else 561 { 562 *hash_data_offset_ptr = UINT32_MAX; 563 return eResultError; 564 } 565 } 566 567 size_t 568 AppendAllDIEsThatMatchingRegex (const lldb_private::RegularExpression& regex, 569 DIEInfoArray &die_info_array) const 570 { 571 const uint32_t hash_count = m_header.hashes_count; 572 Pair pair; 573 for (uint32_t offset_idx=0; offset_idx<hash_count; ++offset_idx) 574 { 575 uint32_t hash_data_offset = GetHashDataOffset (offset_idx); 576 while (hash_data_offset != UINT32_MAX) 577 { 578 const uint32_t prev_hash_data_offset = hash_data_offset; 579 Result hash_result = AppendHashDataForRegularExpression (regex, &hash_data_offset, pair); 580 if (prev_hash_data_offset == hash_data_offset) 581 break; 582 583 // Check the result of getting our hash data 584 switch (hash_result) 585 { 586 case eResultKeyMatch: 587 case eResultKeyMismatch: 588 // Whether we matches or not, it doesn't matter, we 589 // keep looking. 590 break; 591 592 case eResultEndOfHashData: 593 case eResultError: 594 hash_data_offset = UINT32_MAX; 595 break; 596 } 597 } 598 } 599 die_info_array.swap (pair.value); 600 return die_info_array.size(); 601 } 602 603 size_t 604 AppendAllDIEsInRange (const uint32_t die_offset_start, 605 const uint32_t die_offset_end, 606 DIEInfoArray &die_info_array) const 607 { 608 const uint32_t hash_count = m_header.hashes_count; 609 for (uint32_t offset_idx=0; offset_idx<hash_count; ++offset_idx) 610 { 611 bool done = false; 612 uint32_t hash_data_offset = GetHashDataOffset (offset_idx); 613 while (!done && hash_data_offset != UINT32_MAX) 614 { 615 KeyType key = m_data.GetU32 (&hash_data_offset); 616 // If the key is zero, this terminates our chain of HashData objects 617 // for this hash value. 618 if (key == 0) 619 break; 620 621 const uint32_t count = m_data.GetU32 (&hash_data_offset); 622 for (uint32_t i=0; i<count; ++i) 623 { 624 DIEInfo die_info; 625 if (m_header.Read(m_data, &hash_data_offset, die_info)) 626 { 627 if (die_info.offset == 0) 628 done = true; 629 if (die_offset_start <= die_info.offset && die_info.offset < die_offset_end) 630 die_info_array.push_back(die_info); 631 } 632 } 633 } 634 } 635 return die_info_array.size(); 636 } 637 638 size_t 639 FindByName (const char *name, DIEArray &die_offsets) 640 { 641 DIEInfoArray die_info_array; 642 if (FindByName(name, die_info_array)) 643 DWARFMappedHash::ExtractDIEArray (die_info_array, die_offsets); 644 return die_info_array.size(); 645 } 646 647 size_t 648 FindByName (const char *name, DIEInfoArray &die_info_array) 649 { 650 Pair kv_pair; 651 size_t old_size = die_info_array.size(); 652 if (Find (name, kv_pair)) 653 { 654 die_info_array.swap(kv_pair.value); 655 return die_info_array.size() - old_size; 656 } 657 return 0; 658 } 659 660 protected: 661 const lldb_private::DataExtractor &m_data; 662 const lldb_private::DataExtractor &m_string_table; 663 std::string m_name; 664 }; 665}; 666 667 668#endif // SymbolFileDWARF_HashedNameToDIE_h_ 669