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