| //===- DWARFAcceleratorTable.cpp ------------------------------------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h" |
| |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/BinaryFormat/Dwarf.h" |
| #include "llvm/DebugInfo/DWARF/DWARFContext.h" |
| #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h" |
| #include "llvm/Support/Compiler.h" |
| #include "llvm/Support/Format.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <cstddef> |
| #include <cstdint> |
| #include <utility> |
| |
| using namespace llvm; |
| |
| bool DWARFAcceleratorTable::extract() { |
| uint32_t Offset = 0; |
| |
| // Check that we can at least read the header. |
| if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength)+4)) |
| return false; |
| |
| Hdr.Magic = AccelSection.getU32(&Offset); |
| Hdr.Version = AccelSection.getU16(&Offset); |
| Hdr.HashFunction = AccelSection.getU16(&Offset); |
| Hdr.NumBuckets = AccelSection.getU32(&Offset); |
| Hdr.NumHashes = AccelSection.getU32(&Offset); |
| Hdr.HeaderDataLength = AccelSection.getU32(&Offset); |
| |
| // Check that we can read all the hashes and offsets from the |
| // section (see SourceLevelDebugging.rst for the structure of the index). |
| if (!AccelSection.isValidOffset(sizeof(Hdr) + Hdr.HeaderDataLength + |
| Hdr.NumBuckets*4 + Hdr.NumHashes*8)) |
| return false; |
| |
| HdrData.DIEOffsetBase = AccelSection.getU32(&Offset); |
| uint32_t NumAtoms = AccelSection.getU32(&Offset); |
| |
| for (unsigned i = 0; i < NumAtoms; ++i) { |
| uint16_t AtomType = AccelSection.getU16(&Offset); |
| auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset)); |
| HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm)); |
| } |
| |
| IsValid = true; |
| return true; |
| } |
| |
| uint32_t DWARFAcceleratorTable::getNumBuckets() { return Hdr.NumBuckets; } |
| uint32_t DWARFAcceleratorTable::getNumHashes() { return Hdr.NumHashes; } |
| uint32_t DWARFAcceleratorTable::getSizeHdr() { return sizeof(Hdr); } |
| uint32_t DWARFAcceleratorTable::getHeaderDataLength() { |
| return Hdr.HeaderDataLength; |
| } |
| |
| ArrayRef<std::pair<DWARFAcceleratorTable::HeaderData::AtomType, |
| DWARFAcceleratorTable::HeaderData::Form>> |
| DWARFAcceleratorTable::getAtomsDesc() { |
| return HdrData.Atoms; |
| } |
| |
| bool DWARFAcceleratorTable::validateForms() { |
| for (auto Atom : getAtomsDesc()) { |
| DWARFFormValue FormValue(Atom.second); |
| switch (Atom.first) { |
| case dwarf::DW_ATOM_die_offset: |
| case dwarf::DW_ATOM_die_tag: |
| case dwarf::DW_ATOM_type_flags: |
| if ((!FormValue.isFormClass(DWARFFormValue::FC_Constant) && |
| !FormValue.isFormClass(DWARFFormValue::FC_Flag)) || |
| FormValue.getForm() == dwarf::DW_FORM_sdata) |
| return false; |
| default: |
| break; |
| } |
| } |
| return true; |
| } |
| |
| std::pair<uint32_t, dwarf::Tag> |
| DWARFAcceleratorTable::readAtoms(uint32_t &HashDataOffset) { |
| uint32_t DieOffset = dwarf::DW_INVALID_OFFSET; |
| dwarf::Tag DieTag = dwarf::DW_TAG_null; |
| |
| for (auto Atom : getAtomsDesc()) { |
| DWARFFormValue FormValue(Atom.second); |
| FormValue.extractValue(AccelSection, &HashDataOffset, NULL); |
| switch (Atom.first) { |
| case dwarf::DW_ATOM_die_offset: |
| DieOffset = *FormValue.getAsUnsignedConstant(); |
| break; |
| case dwarf::DW_ATOM_die_tag: |
| DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant(); |
| break; |
| default: |
| break; |
| } |
| } |
| return {DieOffset, DieTag}; |
| } |
| |
| LLVM_DUMP_METHOD void DWARFAcceleratorTable::dump(raw_ostream &OS) const { |
| if (!IsValid) |
| return; |
| |
| // Dump the header. |
| OS << "Magic = " << format("0x%08x", Hdr.Magic) << '\n' |
| << "Version = " << format("0x%04x", Hdr.Version) << '\n' |
| << "Hash function = " << format("0x%08x", Hdr.HashFunction) << '\n' |
| << "Bucket count = " << Hdr.NumBuckets << '\n' |
| << "Hashes count = " << Hdr.NumHashes << '\n' |
| << "HeaderData length = " << Hdr.HeaderDataLength << '\n' |
| << "DIE offset base = " << HdrData.DIEOffsetBase << '\n' |
| << "Number of atoms = " << HdrData.Atoms.size() << '\n'; |
| |
| unsigned i = 0; |
| SmallVector<DWARFFormValue, 3> AtomForms; |
| for (const auto &Atom: HdrData.Atoms) { |
| OS << format("Atom[%d] Type: ", i++); |
| auto TypeString = dwarf::AtomTypeString(Atom.first); |
| if (!TypeString.empty()) |
| OS << TypeString; |
| else |
| OS << format("DW_ATOM_Unknown_0x%x", Atom.first); |
| OS << " Form: "; |
| auto FormString = dwarf::FormEncodingString(Atom.second); |
| if (!FormString.empty()) |
| OS << FormString; |
| else |
| OS << format("DW_FORM_Unknown_0x%x", Atom.second); |
| OS << '\n'; |
| AtomForms.push_back(DWARFFormValue(Atom.second)); |
| } |
| |
| // Now go through the actual tables and dump them. |
| uint32_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength; |
| unsigned HashesBase = Offset + Hdr.NumBuckets * 4; |
| unsigned OffsetsBase = HashesBase + Hdr.NumHashes * 4; |
| |
| for (unsigned Bucket = 0; Bucket < Hdr.NumBuckets; ++Bucket) { |
| unsigned Index = AccelSection.getU32(&Offset); |
| |
| OS << format("Bucket[%d]\n", Bucket); |
| if (Index == UINT32_MAX) { |
| OS << " EMPTY\n"; |
| continue; |
| } |
| |
| for (unsigned HashIdx = Index; HashIdx < Hdr.NumHashes; ++HashIdx) { |
| unsigned HashOffset = HashesBase + HashIdx*4; |
| unsigned OffsetsOffset = OffsetsBase + HashIdx*4; |
| uint32_t Hash = AccelSection.getU32(&HashOffset); |
| |
| if (Hash % Hdr.NumBuckets != Bucket) |
| break; |
| |
| unsigned DataOffset = AccelSection.getU32(&OffsetsOffset); |
| OS << format(" Hash = 0x%08x Offset = 0x%08x\n", Hash, DataOffset); |
| if (!AccelSection.isValidOffset(DataOffset)) { |
| OS << " Invalid section offset\n"; |
| continue; |
| } |
| while (AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) { |
| unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset); |
| if (!StringOffset) |
| break; |
| OS << format(" Name: %08x \"%s\"\n", StringOffset, |
| StringSection.getCStr(&StringOffset)); |
| unsigned NumData = AccelSection.getU32(&DataOffset); |
| for (unsigned Data = 0; Data < NumData; ++Data) { |
| OS << format(" Data[%d] => ", Data); |
| unsigned i = 0; |
| for (auto &Atom : AtomForms) { |
| OS << format("{Atom[%d]: ", i++); |
| if (Atom.extractValue(AccelSection, &DataOffset, nullptr)) |
| Atom.dump(OS); |
| else |
| OS << "Error extracting the value"; |
| OS << "} "; |
| } |
| OS << '\n'; |
| } |
| } |
| } |
| } |
| } |
| |
| DWARFAcceleratorTable::ValueIterator::ValueIterator( |
| const DWARFAcceleratorTable &AccelTable, unsigned Offset) |
| : AccelTable(&AccelTable), DataOffset(Offset) { |
| if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) |
| return; |
| |
| for (const auto &Atom : AccelTable.HdrData.Atoms) |
| AtomForms.push_back(DWARFFormValue(Atom.second)); |
| |
| // Read the first entry. |
| NumData = AccelTable.AccelSection.getU32(&DataOffset); |
| Next(); |
| } |
| |
| void DWARFAcceleratorTable::ValueIterator::Next() { |
| assert(NumData > 0 && "attempted to increment iterator past the end"); |
| auto &AccelSection = AccelTable->AccelSection; |
| if (Data >= NumData || |
| !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) { |
| NumData = 0; |
| return; |
| } |
| for (auto &Atom : AtomForms) |
| Atom.extractValue(AccelSection, &DataOffset, nullptr); |
| ++Data; |
| } |
| |
| iterator_range<DWARFAcceleratorTable::ValueIterator> |
| DWARFAcceleratorTable::equal_range(StringRef Key) const { |
| if (!IsValid) |
| return make_range(ValueIterator(), ValueIterator()); |
| |
| // Find the bucket. |
| unsigned HashValue = dwarf::djbHash(Key); |
| unsigned Bucket = HashValue % Hdr.NumBuckets; |
| unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength; |
| unsigned HashesBase = BucketBase + Hdr.NumBuckets * 4; |
| unsigned OffsetsBase = HashesBase + Hdr.NumHashes * 4; |
| |
| unsigned BucketOffset = BucketBase + Bucket * 4; |
| unsigned Index = AccelSection.getU32(&BucketOffset); |
| |
| // Search through all hashes in the bucket. |
| for (unsigned HashIdx = Index; HashIdx < Hdr.NumHashes; ++HashIdx) { |
| unsigned HashOffset = HashesBase + HashIdx * 4; |
| unsigned OffsetsOffset = OffsetsBase + HashIdx * 4; |
| uint32_t Hash = AccelSection.getU32(&HashOffset); |
| |
| if (Hash % Hdr.NumBuckets != Bucket) |
| // We are already in the next bucket. |
| break; |
| |
| unsigned DataOffset = AccelSection.getU32(&OffsetsOffset); |
| unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset); |
| if (!StringOffset) |
| break; |
| |
| // Finally, compare the key. |
| if (Key == StringSection.getCStr(&StringOffset)) |
| return make_range({*this, DataOffset}, ValueIterator()); |
| } |
| return make_range(ValueIterator(), ValueIterator()); |
| } |