//===- DWARFAcceleratorTable.h ----------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_DEBUGINFO_DWARF_DWARFACCELERATORTABLE_H
#define LLVM_DEBUGINFO_DWARF_DWARFACCELERATORTABLE_H
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
#include <cstdint>
#include <utility>
namespace llvm {
class raw_ostream;
class ScopedPrinter;
/// The accelerator tables are designed to allow efficient random access
/// (using a symbol name as a key) into debug info by providing an index of the
/// debug info DIEs. This class implements the common functionality of Apple and
/// DWARF 5 accelerator tables.
/// TODO: Generalize the rest of the AppleAcceleratorTable interface and move it
/// to this class.
class DWARFAcceleratorTable {
protected:
DWARFDataExtractor AccelSection;
DataExtractor StringSection;
public:
/// An abstract class representing a single entry in the accelerator tables.
class Entry {
protected:
SmallVector<DWARFFormValue, 3> Values;
Entry() = default;
// Make these protected so only (final) subclasses can be copied around.
Entry(const Entry &) = default;
Entry(Entry &&) = default;
Entry &operator=(const Entry &) = default;
Entry &operator=(Entry &&) = default;
~Entry() = default;
public:
/// Returns the Offset of the Compilation Unit associated with this
/// Accelerator Entry or std::nullopt if the Compilation Unit offset is not
/// recorded in this Accelerator Entry.
virtual std::optional<uint64_t> getCUOffset() const = 0;
/// Returns the Tag of the Debug Info Entry associated with this
/// Accelerator Entry or std::nullopt if the Tag is not recorded in this
/// Accelerator Entry.
virtual std::optional<dwarf::Tag> getTag() const = 0;
/// Returns the raw values of fields in the Accelerator Entry. In general,
/// these can only be interpreted with the help of the metadata in the
/// owning Accelerator Table.
ArrayRef<DWARFFormValue> getValues() const { return Values; }
};
DWARFAcceleratorTable(const DWARFDataExtractor &AccelSection,
DataExtractor StringSection)
: AccelSection(AccelSection), StringSection(StringSection) {}
virtual ~DWARFAcceleratorTable();
virtual Error extract() = 0;
virtual void dump(raw_ostream &OS) const = 0;
DWARFAcceleratorTable(const DWARFAcceleratorTable &) = delete;
void operator=(const DWARFAcceleratorTable &) = delete;
};
/// This implements the Apple accelerator table format, a precursor of the
/// DWARF 5 accelerator table format.
class AppleAcceleratorTable : public DWARFAcceleratorTable {
struct Header {
uint32_t Magic;
uint16_t Version;
uint16_t HashFunction;
uint32_t BucketCount;
uint32_t HashCount;
uint32_t HeaderDataLength;
void dump(ScopedPrinter &W) const;
};
struct HeaderData {
using AtomType = uint16_t;
using Form = dwarf::Form;
uint64_t DIEOffsetBase;
SmallVector<std::pair<AtomType, Form>, 3> Atoms;
std::optional<uint64_t>
extractOffset(std::optional<DWARFFormValue> Value) const;
};
struct Header Hdr;
struct HeaderData HdrData;
bool IsValid = false;
/// Returns true if we should continue scanning for entries or false if we've
/// reached the last (sentinel) entry of encountered a parsing error.
bool dumpName(ScopedPrinter &W, SmallVectorImpl<DWARFFormValue> &AtomForms,
uint64_t *DataOffset) const;
public:
/// Apple-specific implementation of an Accelerator Entry.
class Entry final : public DWARFAcceleratorTable::Entry {
const HeaderData *HdrData = nullptr;
Entry(const HeaderData &Data);
Entry() = default;
void extract(const AppleAcceleratorTable &AccelTable, uint64_t *Offset);
public:
std::optional<uint64_t> getCUOffset() const override;
/// Returns the Section Offset of the Debug Info Entry associated with this
/// Accelerator Entry or std::nullopt if the DIE offset is not recorded in
/// this Accelerator Entry. The returned offset is relative to the start of
/// the Section containing the DIE.
std::optional<uint64_t> getDIESectionOffset() const;
std::optional<dwarf::Tag> getTag() const override;
/// Returns the value of the Atom in this Accelerator Entry, if the Entry
/// contains such Atom.
std::optional<DWARFFormValue> lookup(HeaderData::AtomType Atom) const;
friend class AppleAcceleratorTable;
friend class ValueIterator;
};
class ValueIterator {
const AppleAcceleratorTable *AccelTable = nullptr;
Entry Current; ///< The current entry.
uint64_t DataOffset = 0; ///< Offset into the section.
unsigned Data = 0; ///< Current data entry.
unsigned NumData = 0; ///< Number of data entries.
/// Advance the iterator.
void Next();
public:
using iterator_category = std::input_iterator_tag;
using value_type = Entry;
using difference_type = std::ptrdiff_t;
using pointer = value_type *;
using reference = value_type &;
/// Construct a new iterator for the entries at \p DataOffset.
ValueIterator(const AppleAcceleratorTable &AccelTable, uint64_t DataOffset);
/// End marker.
ValueIterator() = default;
const Entry &operator*() const { return Current; }
ValueIterator &operator++() { Next(); return *this; }
ValueIterator operator++(int) {
ValueIterator I = *this;
Next();
return I;
}
friend bool operator==(const ValueIterator &A, const ValueIterator &B) {
return A.NumData == B.NumData && A.DataOffset == B.DataOffset;
}
friend bool operator!=(const ValueIterator &A, const ValueIterator &B) {
return !(A == B);
}
};
AppleAcceleratorTable(const DWARFDataExtractor &AccelSection,
DataExtractor StringSection)
: DWARFAcceleratorTable(AccelSection, StringSection) {}
Error extract() override;
uint32_t getNumBuckets();
uint32_t getNumHashes();
uint32_t getSizeHdr();
uint32_t getHeaderDataLength();
/// Return the Atom description, which can be used to interpret the raw values
/// of the Accelerator Entries in this table.
ArrayRef<std::pair<HeaderData::AtomType, HeaderData::Form>> getAtomsDesc();
bool validateForms();
/// Return information related to the DWARF DIE we're looking for when
/// performing a lookup by name.
///
/// \param HashDataOffset an offset into the hash data table
/// \returns <DieOffset, DieTag>
/// DieOffset is the offset into the .debug_info section for the DIE
/// related to the input hash data offset.
/// DieTag is the tag of the DIE
std::pair<uint64_t, dwarf::Tag> readAtoms(uint64_t *HashDataOffset);
void dump(raw_ostream &OS) const override;
/// Look up all entries in the accelerator table matching \c Key.
iterator_range<ValueIterator> equal_range(StringRef Key) const;
};
/// .debug_names section consists of one or more units. Each unit starts with a
/// header, which is followed by a list of compilation units, local and foreign
/// type units.
///
/// These may be followed by an (optional) hash lookup table, which consists of
/// an array of buckets and hashes similar to the apple tables above. The only
/// difference is that the hashes array is 1-based, and consequently an empty
/// bucket is denoted by 0 and not UINT32_MAX.
///
/// Next is the name table, which consists of an array of names and array of
/// entry offsets. This is different from the apple tables, which store names
/// next to the actual entries.
///
/// The structure of the entries is described by an abbreviations table, which
/// comes after the name table. Unlike the apple tables, which have a uniform
/// entry structure described in the header, each .debug_names entry may have
/// different index attributes (DW_IDX_???) attached to it.
///
/// The last segment consists of a list of entries, which is a 0-terminated list
/// referenced by the name table and interpreted with the help of the
/// abbreviation table.
class DWARFDebugNames : public DWARFAcceleratorTable {
public:
class NameIndex;
class NameIterator;
class ValueIterator;
/// DWARF v5 Name Index header.
struct Header {
uint64_t UnitLength;
dwarf::DwarfFormat Format;
uint16_t Version;
uint32_t CompUnitCount;
uint32_t LocalTypeUnitCount;
uint32_t ForeignTypeUnitCount;
uint32_t BucketCount;
uint32_t NameCount;
uint32_t AbbrevTableSize;
uint32_t AugmentationStringSize;
SmallString<8> AugmentationString;
Error extract(const DWARFDataExtractor &AS, uint64_t *Offset);
void dump(ScopedPrinter &W) const;
};
/// Index attribute and its encoding.
struct AttributeEncoding {
dwarf::Index Index;
dwarf::Form Form;
constexpr AttributeEncoding(dwarf::Index Index, dwarf::Form Form)
: Index(Index), Form(Form) {}
friend bool operator==(const AttributeEncoding &LHS,
const AttributeEncoding &RHS) {
return LHS.Index == RHS.Index && LHS.Form == RHS.Form;
}
};
/// Abbreviation describing the encoding of Name Index entries.
struct Abbrev {
uint32_t Code; ///< Abbreviation code
dwarf::Tag Tag; ///< Dwarf Tag of the described entity.
std::vector<AttributeEncoding> Attributes; ///< List of index attributes.
Abbrev(uint32_t Code, dwarf::Tag Tag,
std::vector<AttributeEncoding> Attributes)
: Code(Code), Tag(Tag), Attributes(std::move(Attributes)) {}
void dump(ScopedPrinter &W) const;
};
/// DWARF v5-specific implementation of an Accelerator Entry.
class Entry final : public DWARFAcceleratorTable::Entry {
const NameIndex *NameIdx;
const Abbrev *Abbr;
Entry(const NameIndex &NameIdx, const Abbrev &Abbr);
public:
std::optional<uint64_t> getCUOffset() const override;
std::optional<dwarf::Tag> getTag() const override { return tag(); }
/// Returns the Index into the Compilation Unit list of the owning Name
/// Index or std::nullopt if this Accelerator Entry does not have an
/// associated Compilation Unit. It is up to the user to verify that the
/// returned Index is valid in the owning NameIndex (or use getCUOffset(),
/// which will handle that check itself). Note that entries in NameIndexes
/// which index just a single Compilation Unit are implicitly associated
/// with that unit, so this function will return 0 even without an explicit
/// DW_IDX_compile_unit attribute.
std::optional<uint64_t> getCUIndex() const;
/// .debug_names-specific getter, which always succeeds (DWARF v5 index
/// entries always have a tag).
dwarf::Tag tag() const { return Abbr->Tag; }
/// Returns the Offset of the DIE within the containing CU or TU.
std::optional<uint64_t> getDIEUnitOffset() const;
/// Return the Abbreviation that can be used to interpret the raw values of
/// this Accelerator Entry.
const Abbrev &getAbbrev() const { return *Abbr; }
/// Returns the value of the Index Attribute in this Accelerator Entry, if
/// the Entry contains such Attribute.
std::optional<DWARFFormValue> lookup(dwarf::Index Index) const;
void dump(ScopedPrinter &W) const;
friend class NameIndex;
friend class ValueIterator;
};
/// Error returned by NameIndex::getEntry to report it has reached the end of
/// the entry list.
class SentinelError : public ErrorInfo<SentinelError> {
public:
static char ID;
void log(raw_ostream &OS) const override { OS << "Sentinel"; }
std::error_code convertToErrorCode() const override;
};
private:
/// DenseMapInfo for struct Abbrev.
struct AbbrevMapInfo {
static Abbrev getEmptyKey();
static Abbrev getTombstoneKey();
static unsigned getHashValue(uint32_t Code) {
return DenseMapInfo<uint32_t>::getHashValue(Code);
}
static unsigned getHashValue(const Abbrev &Abbr) {
return getHashValue(Abbr.Code);
}
static bool isEqual(uint32_t LHS, const Abbrev &RHS) {
return LHS == RHS.Code;
}
static bool isEqual(const Abbrev &LHS, const Abbrev &RHS) {
return LHS.Code == RHS.Code;
}
};
public:
/// A single entry in the Name Table (DWARF v5 sect. 6.1.1.4.6) of the Name
/// Index.
class NameTableEntry {
DataExtractor StrData;
uint32_t Index;
uint64_t StringOffset;
uint64_t EntryOffset;
public:
NameTableEntry(const DataExtractor &StrData, uint32_t Index,
uint64_t StringOffset, uint64_t EntryOffset)
: StrData(StrData), Index(Index), StringOffset(StringOffset),
EntryOffset(EntryOffset) {}
/// Return the index of this name in the parent Name Index.
uint32_t getIndex() const { return Index; }
/// Returns the offset of the name of the described entities.
uint64_t getStringOffset() const { return StringOffset; }
/// Return the string referenced by this name table entry or nullptr if the
/// string offset is not valid.
const char *getString() const {
uint64_t Off = StringOffset;
return StrData.getCStr(&Off);
}
/// Returns the offset of the first Entry in the list.
uint64_t getEntryOffset() const { return EntryOffset; }
};
/// Represents a single accelerator table within the DWARF v5 .debug_names
/// section.
class NameIndex {
DenseSet<Abbrev, AbbrevMapInfo> Abbrevs;
struct Header Hdr;
const DWARFDebugNames &Section;
// Base of the whole unit and of various important tables, as offsets from
// the start of the section.
uint64_t Base;
uint64_t CUsBase;
uint64_t BucketsBase;
uint64_t HashesBase;
uint64_t StringOffsetsBase;
uint64_t EntryOffsetsBase;
uint64_t EntriesBase;
void dumpCUs(ScopedPrinter &W) const;
void dumpLocalTUs(ScopedPrinter &W) const;
void dumpForeignTUs(ScopedPrinter &W) const;
void dumpAbbreviations(ScopedPrinter &W) const;
bool dumpEntry(ScopedPrinter &W, uint64_t *Offset) const;
void dumpName(ScopedPrinter &W, const NameTableEntry &NTE,
std::optional<uint32_t> Hash) const;
void dumpBucket(ScopedPrinter &W, uint32_t Bucket) const;
Expected<AttributeEncoding> extractAttributeEncoding(uint64_t *Offset);
Expected<std::vector<AttributeEncoding>>
extractAttributeEncodings(uint64_t *Offset);
Expected<Abbrev> extractAbbrev(uint64_t *Offset);
public:
NameIndex(const DWARFDebugNames &Section, uint64_t Base)
: Section(Section), Base(Base) {}
/// Reads offset of compilation unit CU. CU is 0-based.
uint64_t getCUOffset(uint32_t CU) const;
uint32_t getCUCount() const { return Hdr.CompUnitCount; }
/// Reads offset of local type unit TU, TU is 0-based.
uint64_t getLocalTUOffset(uint32_t TU) const;
uint32_t getLocalTUCount() const { return Hdr.LocalTypeUnitCount; }
/// Reads signature of foreign type unit TU. TU is 0-based.
uint64_t getForeignTUSignature(uint32_t TU) const;
uint32_t getForeignTUCount() const { return Hdr.ForeignTypeUnitCount; }
/// Reads an entry in the Bucket Array for the given Bucket. The returned
/// value is a (1-based) index into the Names, StringOffsets and
/// EntryOffsets arrays. The input Bucket index is 0-based.
uint32_t getBucketArrayEntry(uint32_t Bucket) const;
uint32_t getBucketCount() const { return Hdr.BucketCount; }
/// Reads an entry in the Hash Array for the given Index. The input Index
/// is 1-based.
uint32_t getHashArrayEntry(uint32_t Index) const;
/// Reads an entry in the Name Table for the given Index. The Name Table
/// consists of two arrays -- String Offsets and Entry Offsets. The returned
/// offsets are relative to the starts of respective sections. Input Index
/// is 1-based.
NameTableEntry getNameTableEntry(uint32_t Index) const;
uint32_t getNameCount() const { return Hdr.NameCount; }
const DenseSet<Abbrev, AbbrevMapInfo> &getAbbrevs() const {
return Abbrevs;
}
Expected<Entry> getEntry(uint64_t *Offset) const;
/// Look up all entries in this Name Index matching \c Key.
iterator_range<ValueIterator> equal_range(StringRef Key) const;
NameIterator begin() const { return NameIterator(this, 1); }
NameIterator end() const { return NameIterator(this, getNameCount() + 1); }
Error extract();
uint64_t getUnitOffset() const { return Base; }
uint64_t getNextUnitOffset() const {
return Base + dwarf::getUnitLengthFieldByteSize(Hdr.Format) +
Hdr.UnitLength;
}
void dump(ScopedPrinter &W) const;
friend class DWARFDebugNames;
};
class ValueIterator {
public:
using iterator_category = std::input_iterator_tag;
using value_type = Entry;
using difference_type = std::ptrdiff_t;
using pointer = value_type *;
using reference = value_type &;
private:
/// The Name Index we are currently iterating through. The implementation
/// relies on the fact that this can also be used as an iterator into the
/// "NameIndices" vector in the Accelerator section.
const NameIndex *CurrentIndex = nullptr;
/// Whether this is a local iterator (searches in CurrentIndex only) or not
/// (searches all name indices).
bool IsLocal;
std::optional<Entry> CurrentEntry;
uint64_t DataOffset = 0; ///< Offset into the section.
std::string Key; ///< The Key we are searching for.
std::optional<uint32_t> Hash; ///< Hash of Key, if it has been computed.
bool getEntryAtCurrentOffset();
std::optional<uint64_t> findEntryOffsetInCurrentIndex();
bool findInCurrentIndex();
void searchFromStartOfCurrentIndex();
void next();
/// Set the iterator to the "end" state.
void setEnd() { *this = ValueIterator(); }
public:
/// Create a "begin" iterator for looping over all entries in the
/// accelerator table matching Key. The iterator will run through all Name
/// Indexes in the section in sequence.
ValueIterator(const DWARFDebugNames &AccelTable, StringRef Key);
/// Create a "begin" iterator for looping over all entries in a specific
/// Name Index. Other indices in the section will not be visited.
ValueIterator(const NameIndex &NI, StringRef Key);
/// End marker.
ValueIterator() = default;
const Entry &operator*() const { return *CurrentEntry; }
ValueIterator &operator++() {
next();
return *this;
}
ValueIterator operator++(int) {
ValueIterator I = *this;
next();
return I;
}
friend bool operator==(const ValueIterator &A, const ValueIterator &B) {
return A.CurrentIndex == B.CurrentIndex && A.DataOffset == B.DataOffset;
}
friend bool operator!=(const ValueIterator &A, const ValueIterator &B) {
return !(A == B);
}
};
class NameIterator {
/// The Name Index we are iterating through.
const NameIndex *CurrentIndex;
/// The current name in the Name Index.
uint32_t CurrentName;
void next() {
assert(CurrentName <= CurrentIndex->getNameCount());
++CurrentName;
}
public:
using iterator_category = std::input_iterator_tag;
using value_type = NameTableEntry;
using difference_type = uint32_t;
using pointer = NameTableEntry *;
using reference = NameTableEntry; // We return entries by value.
/// Creates an iterator whose initial position is name CurrentName in
/// CurrentIndex.
NameIterator(const NameIndex *CurrentIndex, uint32_t CurrentName)
: CurrentIndex(CurrentIndex), CurrentName(CurrentName) {}
NameTableEntry operator*() const {
return CurrentIndex->getNameTableEntry(CurrentName);
}
NameIterator &operator++() {
next();
return *this;
}
NameIterator operator++(int) {
NameIterator I = *this;
next();
return I;
}
friend bool operator==(const NameIterator &A, const NameIterator &B) {
return A.CurrentIndex == B.CurrentIndex && A.CurrentName == B.CurrentName;
}
friend bool operator!=(const NameIterator &A, const NameIterator &B) {
return !(A == B);
}
};
private:
SmallVector<NameIndex, 0> NameIndices;
DenseMap<uint64_t, const NameIndex *> CUToNameIndex;
public:
DWARFDebugNames(const DWARFDataExtractor &AccelSection,
DataExtractor StringSection)
: DWARFAcceleratorTable(AccelSection, StringSection) {}
Error extract() override;
void dump(raw_ostream &OS) const override;
/// Look up all entries in the accelerator table matching \c Key.
iterator_range<ValueIterator> equal_range(StringRef Key) const;
using const_iterator = SmallVector<NameIndex, 0>::const_iterator;
const_iterator begin() const { return NameIndices.begin(); }
const_iterator end() const { return NameIndices.end(); }
/// Return the Name Index covering the compile unit at CUOffset, or nullptr if
/// there is no Name Index covering that unit.
const NameIndex *getCUNameIndex(uint64_t CUOffset);
};
} // end namespace llvm
#endif // LLVM_DEBUGINFO_DWARF_DWARFACCELERATORTABLE_H