1 //===-- HashedNameToDIE.cpp -------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "HashedNameToDIE.h"
11 #include "llvm/ADT/StringRef.h"
13 void DWARFMappedHash::ExtractDIEArray(const DIEInfoArray &die_info_array,
14 DIEArray &die_offsets) {
15 const size_t count = die_info_array.size();
16 for (size_t i = 0; i < count; ++i)
17 die_offsets.emplace_back(die_info_array[i].cu_offset,
18 die_info_array[i].offset);
21 void DWARFMappedHash::ExtractDIEArray(const DIEInfoArray &die_info_array,
23 DIEArray &die_offsets) {
25 ExtractDIEArray(die_info_array, die_offsets);
27 const size_t count = die_info_array.size();
28 for (size_t i = 0; i < count; ++i) {
29 const dw_tag_t die_tag = die_info_array[i].tag;
30 bool tag_matches = die_tag == 0 || tag == die_tag;
32 if (die_tag == DW_TAG_class_type || die_tag == DW_TAG_structure_type)
34 tag == DW_TAG_structure_type || tag == DW_TAG_class_type;
37 die_offsets.emplace_back(die_info_array[i].cu_offset,
38 die_info_array[i].offset);
43 void DWARFMappedHash::ExtractDIEArray(const DIEInfoArray &die_info_array,
45 const uint32_t qualified_name_hash,
46 DIEArray &die_offsets) {
48 ExtractDIEArray(die_info_array, die_offsets);
50 const size_t count = die_info_array.size();
51 for (size_t i = 0; i < count; ++i) {
52 if (qualified_name_hash != die_info_array[i].qualified_name_hash)
54 const dw_tag_t die_tag = die_info_array[i].tag;
55 bool tag_matches = die_tag == 0 || tag == die_tag;
57 if (die_tag == DW_TAG_class_type || die_tag == DW_TAG_structure_type)
59 tag == DW_TAG_structure_type || tag == DW_TAG_class_type;
62 die_offsets.emplace_back(die_info_array[i].cu_offset,
63 die_info_array[i].offset);
68 void DWARFMappedHash::ExtractClassOrStructDIEArray(
69 const DIEInfoArray &die_info_array,
70 bool return_implementation_only_if_available, DIEArray &die_offsets) {
71 const size_t count = die_info_array.size();
72 for (size_t i = 0; i < count; ++i) {
73 const dw_tag_t die_tag = die_info_array[i].tag;
74 if (die_tag == 0 || die_tag == DW_TAG_class_type ||
75 die_tag == DW_TAG_structure_type) {
76 if (die_info_array[i].type_flags & eTypeFlagClassIsImplementation) {
77 if (return_implementation_only_if_available) {
78 // We found the one true definition for this class, so
81 die_offsets.emplace_back(die_info_array[i].cu_offset,
82 die_info_array[i].offset);
85 // Put the one true definition as the first entry so it
87 die_offsets.emplace(die_offsets.begin(), die_info_array[i].cu_offset,
88 die_info_array[i].offset);
91 die_offsets.emplace_back(die_info_array[i].cu_offset,
92 die_info_array[i].offset);
98 void DWARFMappedHash::ExtractTypesFromDIEArray(
99 const DIEInfoArray &die_info_array, uint32_t type_flag_mask,
100 uint32_t type_flag_value, DIEArray &die_offsets) {
101 const size_t count = die_info_array.size();
102 for (size_t i = 0; i < count; ++i) {
103 if ((die_info_array[i].type_flags & type_flag_mask) == type_flag_value)
104 die_offsets.emplace_back(die_info_array[i].cu_offset,
105 die_info_array[i].offset);
109 const char *DWARFMappedHash::GetAtomTypeName(uint16_t atom) {
113 case eAtomTypeDIEOffset:
115 case eAtomTypeCUOffset:
119 case eAtomTypeNameFlags:
121 case eAtomTypeTypeFlags:
123 case eAtomTypeQualNameHash:
124 return "qualified-name-hash";
129 DWARFMappedHash::DIEInfo::DIEInfo()
130 : cu_offset(DW_INVALID_OFFSET), offset(DW_INVALID_OFFSET), tag(0),
131 type_flags(0), qualified_name_hash(0) {}
133 DWARFMappedHash::DIEInfo::DIEInfo(dw_offset_t c, dw_offset_t o, dw_tag_t t,
134 uint32_t f, uint32_t h)
135 : cu_offset(c), offset(o), tag(t), type_flags(f), qualified_name_hash(h) {}
137 DWARFMappedHash::Prologue::Prologue(dw_offset_t _die_base_offset)
138 : die_base_offset(_die_base_offset), atoms(), atom_mask(0),
139 min_hash_data_byte_size(0), hash_data_has_fixed_byte_size(true) {
140 // Define an array of DIE offsets by first defining an array,
141 // and then define the atom type for the array, in this case
142 // we have an array of DIE offsets
143 AppendAtom(eAtomTypeDIEOffset, DW_FORM_data4);
146 void DWARFMappedHash::Prologue::ClearAtoms() {
147 hash_data_has_fixed_byte_size = true;
148 min_hash_data_byte_size = 0;
153 bool DWARFMappedHash::Prologue::ContainsAtom(AtomType atom_type) const {
154 return (atom_mask & (1u << atom_type)) != 0;
157 void DWARFMappedHash::Prologue::Clear() {
162 void DWARFMappedHash::Prologue::AppendAtom(AtomType type, dw_form_t form) {
163 atoms.push_back({type, form});
164 atom_mask |= 1u << type;
166 case DW_FORM_indirect:
167 case DW_FORM_exprloc:
168 case DW_FORM_flag_present:
169 case DW_FORM_ref_sig8:
170 llvm_unreachable("Unhandled atom form");
177 case DW_FORM_ref_udata:
178 case DW_FORM_GNU_addr_index:
179 case DW_FORM_GNU_str_index:
180 hash_data_has_fixed_byte_size = false;
185 case DW_FORM_sec_offset:
186 min_hash_data_byte_size += 1;
190 hash_data_has_fixed_byte_size = false;
194 min_hash_data_byte_size += 2;
198 hash_data_has_fixed_byte_size = false;
203 case DW_FORM_ref_addr:
205 min_hash_data_byte_size += 4;
210 min_hash_data_byte_size += 8;
216 DWARFMappedHash::Prologue::Read(const lldb_private::DataExtractor &data,
217 lldb::offset_t offset) {
220 die_base_offset = data.GetU32(&offset);
222 const uint32_t atom_count = data.GetU32(&offset);
223 if (atom_count == 0x00060003u) {
224 // Old format, deal with contents of old pre-release format
225 while (data.GetU32(&offset))
228 // Hardcode to the only known value for now.
229 AppendAtom(eAtomTypeDIEOffset, DW_FORM_data4);
231 for (uint32_t i = 0; i < atom_count; ++i) {
232 AtomType type = (AtomType)data.GetU16(&offset);
233 dw_form_t form = (dw_form_t)data.GetU16(&offset);
234 AppendAtom(type, form);
240 size_t DWARFMappedHash::Prologue::GetByteSize() const {
241 // Add an extra count to the atoms size for the zero termination Atom that
244 return sizeof(die_base_offset) + sizeof(uint32_t) +
245 atoms.size() * sizeof(Atom);
248 size_t DWARFMappedHash::Prologue::GetMinimumHashDataByteSize() const {
249 return min_hash_data_byte_size;
252 bool DWARFMappedHash::Prologue::HashDataHasFixedByteSize() const {
253 return hash_data_has_fixed_byte_size;
256 size_t DWARFMappedHash::Header::GetByteSize(const HeaderData &header_data) {
257 return header_data.GetByteSize();
260 lldb::offset_t DWARFMappedHash::Header::Read(lldb_private::DataExtractor &data,
261 lldb::offset_t offset) {
262 offset = MappedHash::Header<Prologue>::Read(data, offset);
263 if (offset != UINT32_MAX) {
264 offset = header_data.Read(data, offset);
269 bool DWARFMappedHash::Header::Read(const lldb_private::DWARFDataExtractor &data,
270 lldb::offset_t *offset_ptr,
271 DIEInfo &hash_data) const {
272 const size_t num_atoms = header_data.atoms.size();
276 for (size_t i = 0; i < num_atoms; ++i) {
277 DWARFFormValue form_value(NULL, header_data.atoms[i].form);
279 if (!form_value.ExtractValue(data, offset_ptr))
282 switch (header_data.atoms[i].type) {
283 case eAtomTypeDIEOffset: // DIE offset, check form for encoding
285 (dw_offset_t)form_value.Reference(header_data.die_base_offset);
288 case eAtomTypeTag: // DW_TAG value for the DIE
289 hash_data.tag = (dw_tag_t)form_value.Unsigned();
292 case eAtomTypeTypeFlags: // Flags from enum TypeFlags
293 hash_data.type_flags = (uint32_t)form_value.Unsigned();
296 case eAtomTypeQualNameHash: // Flags from enum TypeFlags
297 hash_data.qualified_name_hash = form_value.Unsigned();
301 // We can always skip atoms we don't know about
308 void DWARFMappedHash::Header::Dump(lldb_private::Stream &strm,
309 const DIEInfo &hash_data) const {
310 const size_t num_atoms = header_data.atoms.size();
311 for (size_t i = 0; i < num_atoms; ++i) {
313 strm.PutCString(", ");
315 DWARFFormValue form_value(NULL, header_data.atoms[i].form);
316 switch (header_data.atoms[i].type) {
317 case eAtomTypeDIEOffset: // DIE offset, check form for encoding
318 strm.Printf("{0x%8.8x}", hash_data.offset);
321 case eAtomTypeTag: // DW_TAG value for the DIE
323 const char *tag_cstr = lldb_private::DW_TAG_value_to_name(hash_data.tag);
325 strm.PutCString(tag_cstr);
327 strm.Printf("DW_TAG_(0x%4.4x)", hash_data.tag);
330 case eAtomTypeTypeFlags: // Flags from enum TypeFlags
331 strm.Printf("0x%2.2x", hash_data.type_flags);
332 if (hash_data.type_flags) {
333 strm.PutCString(" (");
334 if (hash_data.type_flags & eTypeFlagClassIsImplementation)
335 strm.PutCString(" implementation");
336 strm.PutCString(" )");
340 case eAtomTypeQualNameHash: // Flags from enum TypeFlags
341 strm.Printf("0x%8.8x", hash_data.qualified_name_hash);
345 strm.Printf("AtomType(0x%x)", header_data.atoms[i].type);
351 DWARFMappedHash::MemoryTable::MemoryTable(
352 lldb_private::DWARFDataExtractor &table_data,
353 const lldb_private::DWARFDataExtractor &string_table, const char *name)
354 : MappedHash::MemoryTable<uint32_t, Header, DIEInfoArray>(table_data),
355 m_data(table_data), m_string_table(string_table), m_name(name) {}
358 DWARFMappedHash::MemoryTable::GetStringForKeyType(KeyType key) const {
359 // The key in the DWARF table is the .debug_str offset for the string
360 return m_string_table.PeekCStr(key);
363 bool DWARFMappedHash::MemoryTable::ReadHashData(uint32_t hash_data_offset,
364 HashData &hash_data) const {
365 lldb::offset_t offset = hash_data_offset;
366 offset += 4; // Skip string table offset that contains offset of hash name in
368 const uint32_t count = m_data.GetU32(&offset);
370 hash_data.resize(count);
371 for (uint32_t i = 0; i < count; ++i) {
372 if (!m_header.Read(m_data, &offset, hash_data[i]))
380 DWARFMappedHash::MemoryTable::Result
381 DWARFMappedHash::MemoryTable::GetHashDataForName(
382 const char *name, lldb::offset_t *hash_data_offset_ptr, Pair &pair) const {
383 pair.key = m_data.GetU32(hash_data_offset_ptr);
386 // If the key is zero, this terminates our chain of HashData objects
387 // for this hash value.
389 return eResultEndOfHashData;
391 // There definitely should be a string for this string offset, if
392 // there isn't, there is something wrong, return and error
393 const char *strp_cstr = m_string_table.PeekCStr(pair.key);
394 if (strp_cstr == NULL) {
395 *hash_data_offset_ptr = UINT32_MAX;
399 const uint32_t count = m_data.GetU32(hash_data_offset_ptr);
400 const size_t min_total_hash_data_size =
401 count * m_header.header_data.GetMinimumHashDataByteSize();
403 m_data.ValidOffsetForDataOfSize(*hash_data_offset_ptr,
404 min_total_hash_data_size)) {
405 // We have at least one HashData entry, and we have enough
406 // data to parse at least "count" HashData entries.
408 // First make sure the entire C string matches...
409 const bool match = strcmp(name, strp_cstr) == 0;
411 if (!match && m_header.header_data.HashDataHasFixedByteSize()) {
412 // If the string doesn't match and we have fixed size data,
413 // we can just add the total byte size of all HashData objects
414 // to the hash data offset and be done...
415 *hash_data_offset_ptr += min_total_hash_data_size;
417 // If the string does match, or we don't have fixed size data
418 // then we need to read the hash data as a stream. If the
419 // string matches we also append all HashData objects to the
421 for (uint32_t i = 0; i < count; ++i) {
423 if (m_header.Read(m_data, hash_data_offset_ptr, die_info)) {
424 // Only happened if the HashData of the string matched...
426 pair.value.push_back(die_info);
428 // Something went wrong while reading the data
429 *hash_data_offset_ptr = UINT32_MAX;
434 // Return the correct response depending on if the string matched
437 return eResultKeyMatch; // The key (cstring) matches and we have lookup
440 return eResultKeyMismatch; // The key doesn't match, this function will
442 // again for the next key/value or the key terminator
443 // which in our case is a zero .debug_str offset.
445 *hash_data_offset_ptr = UINT32_MAX;
450 DWARFMappedHash::MemoryTable::Result
451 DWARFMappedHash::MemoryTable::AppendHashDataForRegularExpression(
452 const lldb_private::RegularExpression ®ex,
453 lldb::offset_t *hash_data_offset_ptr, Pair &pair) const {
454 pair.key = m_data.GetU32(hash_data_offset_ptr);
455 // If the key is zero, this terminates our chain of HashData objects
456 // for this hash value.
458 return eResultEndOfHashData;
460 // There definitely should be a string for this string offset, if
461 // there isn't, there is something wrong, return and error
462 const char *strp_cstr = m_string_table.PeekCStr(pair.key);
463 if (strp_cstr == NULL)
466 const uint32_t count = m_data.GetU32(hash_data_offset_ptr);
467 const size_t min_total_hash_data_size =
468 count * m_header.header_data.GetMinimumHashDataByteSize();
470 m_data.ValidOffsetForDataOfSize(*hash_data_offset_ptr,
471 min_total_hash_data_size)) {
472 const bool match = regex.Execute(llvm::StringRef(strp_cstr));
474 if (!match && m_header.header_data.HashDataHasFixedByteSize()) {
475 // If the regex doesn't match and we have fixed size data,
476 // we can just add the total byte size of all HashData objects
477 // to the hash data offset and be done...
478 *hash_data_offset_ptr += min_total_hash_data_size;
480 // If the string does match, or we don't have fixed size data
481 // then we need to read the hash data as a stream. If the
482 // string matches we also append all HashData objects to the
484 for (uint32_t i = 0; i < count; ++i) {
486 if (m_header.Read(m_data, hash_data_offset_ptr, die_info)) {
487 // Only happened if the HashData of the string matched...
489 pair.value.push_back(die_info);
491 // Something went wrong while reading the data
492 *hash_data_offset_ptr = UINT32_MAX;
497 // Return the correct response depending on if the string matched
500 return eResultKeyMatch; // The key (cstring) matches and we have lookup
503 return eResultKeyMismatch; // The key doesn't match, this function will
505 // again for the next key/value or the key terminator
506 // which in our case is a zero .debug_str offset.
508 *hash_data_offset_ptr = UINT32_MAX;
513 size_t DWARFMappedHash::MemoryTable::AppendAllDIEsThatMatchingRegex(
514 const lldb_private::RegularExpression ®ex,
515 DIEInfoArray &die_info_array) const {
516 const uint32_t hash_count = m_header.hashes_count;
518 for (uint32_t offset_idx = 0; offset_idx < hash_count; ++offset_idx) {
519 lldb::offset_t hash_data_offset = GetHashDataOffset(offset_idx);
520 while (hash_data_offset != UINT32_MAX) {
521 const lldb::offset_t prev_hash_data_offset = hash_data_offset;
523 AppendHashDataForRegularExpression(regex, &hash_data_offset, pair);
524 if (prev_hash_data_offset == hash_data_offset)
527 // Check the result of getting our hash data
528 switch (hash_result) {
529 case eResultKeyMatch:
530 case eResultKeyMismatch:
531 // Whether we matches or not, it doesn't matter, we
535 case eResultEndOfHashData:
537 hash_data_offset = UINT32_MAX;
542 die_info_array.swap(pair.value);
543 return die_info_array.size();
546 size_t DWARFMappedHash::MemoryTable::AppendAllDIEsInRange(
547 const uint32_t die_offset_start, const uint32_t die_offset_end,
548 DIEInfoArray &die_info_array) const {
549 const uint32_t hash_count = m_header.hashes_count;
550 for (uint32_t offset_idx = 0; offset_idx < hash_count; ++offset_idx) {
552 lldb::offset_t hash_data_offset = GetHashDataOffset(offset_idx);
553 while (!done && hash_data_offset != UINT32_MAX) {
554 KeyType key = m_data.GetU32(&hash_data_offset);
555 // If the key is zero, this terminates our chain of HashData objects
556 // for this hash value.
560 const uint32_t count = m_data.GetU32(&hash_data_offset);
561 for (uint32_t i = 0; i < count; ++i) {
563 if (m_header.Read(m_data, &hash_data_offset, die_info)) {
564 if (die_info.offset == 0)
566 if (die_offset_start <= die_info.offset &&
567 die_info.offset < die_offset_end)
568 die_info_array.push_back(die_info);
573 return die_info_array.size();
576 size_t DWARFMappedHash::MemoryTable::FindByName(const char *name,
577 DIEArray &die_offsets) {
578 if (!name || !name[0])
581 DIEInfoArray die_info_array;
582 if (FindByName(name, die_info_array))
583 DWARFMappedHash::ExtractDIEArray(die_info_array, die_offsets);
584 return die_info_array.size();
587 size_t DWARFMappedHash::MemoryTable::FindByNameAndTag(const char *name,
589 DIEArray &die_offsets) {
590 DIEInfoArray die_info_array;
591 if (FindByName(name, die_info_array))
592 DWARFMappedHash::ExtractDIEArray(die_info_array, tag, die_offsets);
593 return die_info_array.size();
596 size_t DWARFMappedHash::MemoryTable::FindByNameAndTagAndQualifiedNameHash(
597 const char *name, const dw_tag_t tag, const uint32_t qualified_name_hash,
598 DIEArray &die_offsets) {
599 DIEInfoArray die_info_array;
600 if (FindByName(name, die_info_array))
601 DWARFMappedHash::ExtractDIEArray(die_info_array, tag, qualified_name_hash,
603 return die_info_array.size();
606 size_t DWARFMappedHash::MemoryTable::FindCompleteObjCClassByName(
607 const char *name, DIEArray &die_offsets, bool must_be_implementation) {
608 DIEInfoArray die_info_array;
609 if (FindByName(name, die_info_array)) {
610 if (must_be_implementation &&
611 GetHeader().header_data.ContainsAtom(eAtomTypeTypeFlags)) {
612 // If we have two atoms, then we have the DIE offset and
613 // the type flags so we can find the objective C class
615 DWARFMappedHash::ExtractTypesFromDIEArray(die_info_array, UINT32_MAX,
616 eTypeFlagClassIsImplementation,
619 // We don't only want the one true definition, so try and see
620 // what we can find, and only return class or struct DIEs.
621 // If we do have the full implementation, then return it alone,
622 // else return all possible matches.
623 const bool return_implementation_only_if_available = true;
624 DWARFMappedHash::ExtractClassOrStructDIEArray(
625 die_info_array, return_implementation_only_if_available, die_offsets);
628 return die_offsets.size();
631 size_t DWARFMappedHash::MemoryTable::FindByName(const char *name,
632 DIEInfoArray &die_info_array) {
633 if (!name || !name[0])
637 size_t old_size = die_info_array.size();
638 if (Find(name, kv_pair)) {
639 die_info_array.swap(kv_pair.value);
640 return die_info_array.size() - old_size;