323 lines · cpp
1//===- DWARFUnitIndex.cpp -------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"10#include "llvm/ADT/STLExtras.h"11#include "llvm/ADT/StringRef.h"12#include "llvm/Support/DataExtractor.h"13#include "llvm/Support/ErrorHandling.h"14#include "llvm/Support/Format.h"15#include "llvm/Support/raw_ostream.h"16#include <cinttypes>17#include <cstdint>18 19using namespace llvm;20 21namespace {22 23enum class DWARFSectionKindV2 {24 DW_SECT_INFO = 1,25 DW_SECT_TYPES = 2,26 DW_SECT_ABBREV = 3,27 DW_SECT_LINE = 4,28 DW_SECT_LOC = 5,29 DW_SECT_STR_OFFSETS = 6,30 DW_SECT_MACINFO = 7,31 DW_SECT_MACRO = 8,32};33 34} // namespace35 36// Return true if the section identifier is defined in the DWARFv5 standard.37constexpr bool isKnownV5SectionID(uint32_t ID) {38 return ID >= DW_SECT_INFO && ID <= DW_SECT_RNGLISTS &&39 ID != DW_SECT_EXT_TYPES;40}41 42uint32_t llvm::serializeSectionKind(DWARFSectionKind Kind,43 unsigned IndexVersion) {44 if (IndexVersion == 5) {45 assert(isKnownV5SectionID(Kind));46 return static_cast<uint32_t>(Kind);47 }48 assert(IndexVersion == 2);49 switch (Kind) {50#define CASE(S,T) \51 case DW_SECT_##S: \52 return static_cast<uint32_t>(DWARFSectionKindV2::DW_SECT_##T)53 CASE(INFO, INFO);54 CASE(EXT_TYPES, TYPES);55 CASE(ABBREV, ABBREV);56 CASE(LINE, LINE);57 CASE(EXT_LOC, LOC);58 CASE(STR_OFFSETS, STR_OFFSETS);59 CASE(EXT_MACINFO, MACINFO);60 CASE(MACRO, MACRO);61#undef CASE62 default:63 // All other section kinds have no corresponding values in v2 indexes.64 llvm_unreachable("Invalid DWARFSectionKind");65 }66}67 68DWARFSectionKind llvm::deserializeSectionKind(uint32_t Value,69 unsigned IndexVersion) {70 if (IndexVersion == 5)71 return isKnownV5SectionID(Value)72 ? static_cast<DWARFSectionKind>(Value)73 : DW_SECT_EXT_unknown;74 assert(IndexVersion == 2);75 switch (static_cast<DWARFSectionKindV2>(Value)) {76#define CASE(S,T) \77 case DWARFSectionKindV2::DW_SECT_##S: \78 return DW_SECT_##T79 CASE(INFO, INFO);80 CASE(TYPES, EXT_TYPES);81 CASE(ABBREV, ABBREV);82 CASE(LINE, LINE);83 CASE(LOC, EXT_LOC);84 CASE(STR_OFFSETS, STR_OFFSETS);85 CASE(MACINFO, EXT_MACINFO);86 CASE(MACRO, MACRO);87#undef CASE88 }89 return DW_SECT_EXT_unknown;90}91 92bool DWARFUnitIndex::Header::parse(DataExtractor IndexData,93 uint64_t *OffsetPtr) {94 const uint64_t BeginOffset = *OffsetPtr;95 if (!IndexData.isValidOffsetForDataOfSize(*OffsetPtr, 16))96 return false;97 // GCC Debug Fission defines the version as an unsigned 32-bit field98 // with value of 2, https://gcc.gnu.org/wiki/DebugFissionDWP.99 // DWARFv5 defines the same space as an uhalf version field with value of 5100 // and a 2 bytes long padding, see Section 7.3.5.3.101 Version = IndexData.getU32(OffsetPtr);102 if (Version != 2) {103 *OffsetPtr = BeginOffset;104 Version = IndexData.getU16(OffsetPtr);105 if (Version != 5)106 return false;107 *OffsetPtr += 2; // Skip padding.108 }109 NumColumns = IndexData.getU32(OffsetPtr);110 NumUnits = IndexData.getU32(OffsetPtr);111 NumBuckets = IndexData.getU32(OffsetPtr);112 return true;113}114 115void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {116 OS << format("version = %u, units = %u, slots = %u\n\n", Version, NumUnits, NumBuckets);117}118 119bool DWARFUnitIndex::parse(DataExtractor IndexData) {120 bool b = parseImpl(IndexData);121 if (!b) {122 // Make sure we don't try to dump anything123 Header.NumBuckets = 0;124 // Release any partially initialized data.125 ColumnKinds.reset();126 Rows.reset();127 }128 return b;129}130 131bool DWARFUnitIndex::parseImpl(DataExtractor IndexData) {132 uint64_t Offset = 0;133 if (!Header.parse(IndexData, &Offset))134 return false;135 136 // Fix InfoColumnKind: in DWARFv5, type units are in .debug_info.dwo.137 if (Header.Version == 5)138 InfoColumnKind = DW_SECT_INFO;139 140 if (!IndexData.isValidOffsetForDataOfSize(141 Offset, Header.NumBuckets * (8 + 4) +142 (2 * Header.NumUnits + 1) * 4 * Header.NumColumns))143 return false;144 145 Rows = std::make_unique<Entry[]>(Header.NumBuckets);146 auto Contribs =147 std::make_unique<Entry::SectionContribution *[]>(Header.NumUnits);148 ColumnKinds = std::make_unique<DWARFSectionKind[]>(Header.NumColumns);149 RawSectionIds = std::make_unique<uint32_t[]>(Header.NumColumns);150 151 // Read Hash Table of Signatures152 for (unsigned i = 0; i != Header.NumBuckets; ++i)153 Rows[i].Signature = IndexData.getU64(&Offset);154 155 // Read Parallel Table of Indexes156 for (unsigned i = 0; i != Header.NumBuckets; ++i) {157 auto Index = IndexData.getU32(&Offset);158 if (!Index)159 continue;160 Rows[i].Index = this;161 Rows[i].Contributions =162 std::make_unique<Entry::SectionContribution[]>(Header.NumColumns);163 Contribs[Index - 1] = Rows[i].Contributions.get();164 }165 166 // Read the Column Headers167 for (unsigned i = 0; i != Header.NumColumns; ++i) {168 RawSectionIds[i] = IndexData.getU32(&Offset);169 ColumnKinds[i] = deserializeSectionKind(RawSectionIds[i], Header.Version);170 if (ColumnKinds[i] == InfoColumnKind) {171 if (InfoColumn != -1)172 return false;173 InfoColumn = i;174 }175 }176 177 if (InfoColumn == -1)178 return false;179 180 // Read Table of Section Offsets181 for (unsigned i = 0; i != Header.NumUnits; ++i) {182 auto *Contrib = Contribs[i];183 for (unsigned i = 0; i != Header.NumColumns; ++i)184 Contrib[i].setOffset(IndexData.getU32(&Offset));185 }186 187 // Read Table of Section Sizes188 for (unsigned i = 0; i != Header.NumUnits; ++i) {189 auto *Contrib = Contribs[i];190 for (unsigned i = 0; i != Header.NumColumns; ++i)191 Contrib[i].setLength(IndexData.getU32(&Offset));192 }193 194 return true;195}196 197StringRef DWARFUnitIndex::getColumnHeader(DWARFSectionKind DS) {198 switch (DS) {199#define HANDLE_DW_SECT(ID, NAME) \200 case DW_SECT_##NAME: \201 return #NAME;202#include "llvm/BinaryFormat/Dwarf.def"203 case DW_SECT_EXT_TYPES:204 return "TYPES";205 case DW_SECT_EXT_LOC:206 return "LOC";207 case DW_SECT_EXT_MACINFO:208 return "MACINFO";209 case DW_SECT_EXT_unknown:210 return StringRef();211 }212 llvm_unreachable("Unknown DWARFSectionKind");213}214 215void DWARFUnitIndex::dump(raw_ostream &OS) const {216 if (!*this)217 return;218 219 Header.dump(OS);220 OS << "Index Signature ";221 for (unsigned i = 0; i != Header.NumColumns; ++i) {222 DWARFSectionKind Kind = ColumnKinds[i];223 StringRef Name = getColumnHeader(Kind);224 if (!Name.empty())225 OS << ' '226 << left_justify(Name,227 Kind == DWARFSectionKind::DW_SECT_INFO ? 40 : 24);228 else229 OS << format(" Unknown: %-15" PRIu32, RawSectionIds[i]);230 }231 OS << "\n----- ------------------";232 for (unsigned i = 0; i != Header.NumColumns; ++i) {233 DWARFSectionKind Kind = ColumnKinds[i];234 if (Kind == DWARFSectionKind::DW_SECT_INFO ||235 Kind == DWARFSectionKind::DW_SECT_EXT_TYPES)236 OS << " ----------------------------------------";237 else238 OS << " ------------------------";239 }240 OS << '\n';241 for (unsigned i = 0; i != Header.NumBuckets; ++i) {242 auto &Row = Rows[i];243 if (auto *Contribs = Row.Contributions.get()) {244 OS << format("%5u 0x%016" PRIx64 " ", i + 1, Row.Signature);245 for (unsigned i = 0; i != Header.NumColumns; ++i) {246 auto &Contrib = Contribs[i];247 DWARFSectionKind Kind = ColumnKinds[i];248 if (Kind == DWARFSectionKind::DW_SECT_INFO ||249 Kind == DWARFSectionKind::DW_SECT_EXT_TYPES)250 OS << format("[0x%016" PRIx64 ", 0x%016" PRIx64 ") ",251 Contrib.getOffset(),252 Contrib.getOffset() + Contrib.getLength());253 else254 OS << format("[0x%08" PRIx32 ", 0x%08" PRIx32 ") ",255 Contrib.getOffset32(),256 Contrib.getOffset32() + Contrib.getLength32());257 }258 OS << '\n';259 }260 }261}262 263const DWARFUnitIndex::Entry::SectionContribution *264DWARFUnitIndex::Entry::getContribution(DWARFSectionKind Sec) const {265 uint32_t i = 0;266 for (; i != Index->Header.NumColumns; ++i)267 if (Index->ColumnKinds[i] == Sec)268 return &Contributions[i];269 return nullptr;270}271 272DWARFUnitIndex::Entry::SectionContribution &273DWARFUnitIndex::Entry::getContribution() {274 return Contributions[Index->InfoColumn];275}276 277const DWARFUnitIndex::Entry::SectionContribution *278DWARFUnitIndex::Entry::getContribution() const {279 return &Contributions[Index->InfoColumn];280}281 282const DWARFUnitIndex::Entry *283DWARFUnitIndex::getFromOffset(uint64_t Offset) const {284 if (OffsetLookup.empty()) {285 for (uint32_t i = 0; i != Header.NumBuckets; ++i)286 if (Rows[i].Contributions)287 OffsetLookup.push_back(&Rows[i]);288 llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) {289 return E1->Contributions[InfoColumn].getOffset() <290 E2->Contributions[InfoColumn].getOffset();291 });292 }293 auto I = partition_point(OffsetLookup, [&](Entry *E2) {294 return E2->Contributions[InfoColumn].getOffset() <= Offset;295 });296 if (I == OffsetLookup.begin())297 return nullptr;298 --I;299 const auto *E = *I;300 const auto &InfoContrib = E->Contributions[InfoColumn];301 if ((InfoContrib.getOffset() + InfoContrib.getLength()) <= Offset)302 return nullptr;303 return E;304}305 306const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {307 uint64_t Mask = Header.NumBuckets - 1;308 309 auto H = S & Mask;310 auto HP = ((S >> 32) & Mask) | 1;311 // The spec says "while 0 is a valid hash value, the row index in a used slot312 // will always be non-zero". Loop until we find a match or an empty slot.313 while (Rows[H].getSignature() != S && Rows[H].Index != nullptr)314 H = (H + HP) & Mask;315 316 // If the slot is empty, we don't care whether the signature matches (it could317 // be zero and still match the zeros in the empty slot).318 if (Rows[H].Index == nullptr)319 return nullptr;320 321 return &Rows[H];322}323