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/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 19 using namespace llvm; 20 21 namespace { 22 23 enum 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 } // namespace 35 36 // Return true if the section identifier is defined in the DWARFv5 standard. 37 constexpr bool isKnownV5SectionID(uint32_t ID) { 38 return ID >= DW_SECT_INFO && ID <= DW_SECT_RNGLISTS && 39 ID != DW_SECT_EXT_TYPES; 40 } 41 42 uint32_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 CASE 62 default: 63 // All other section kinds have no corresponding values in v2 indexes. 64 llvm_unreachable("Invalid DWARFSectionKind"); 65 } 66 } 67 68 DWARFSectionKind 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_##T 79 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 CASE 88 } 89 return DW_SECT_EXT_unknown; 90 } 91 92 bool 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 field 98 // with value of 2, https://gcc.gnu.org/wiki/DebugFissionDWP. 99 // DWARFv5 defines the same space as an uhalf version field with value of 5 100 // 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 115 void DWARFUnitIndex::Header::dump(raw_ostream &OS) const { 116 OS << format("version = %u, units = %u, slots = %u\n\n", Version, NumUnits, NumBuckets); 117 } 118 119 bool DWARFUnitIndex::parse(DataExtractor IndexData) { 120 bool b = parseImpl(IndexData); 121 if (!b) { 122 // Make sure we don't try to dump anything 123 Header.NumBuckets = 0; 124 // Release any partially initialized data. 125 ColumnKinds.reset(); 126 Rows.reset(); 127 } 128 return b; 129 } 130 131 bool 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 Signatures 152 for (unsigned i = 0; i != Header.NumBuckets; ++i) 153 Rows[i].Signature = IndexData.getU64(&Offset); 154 155 // Read Parallel Table of Indexes 156 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 Headers 167 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 Offsets 181 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 Sizes 188 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 197 StringRef 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 215 void 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 else 229 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 else 238 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 else 254 OS << format("[0x%08" PRIx32 ", 0x%08" PRIx32 ") ", 255 Contrib.getOffset32(), 256 Contrib.getOffset32() + Contrib.getLength32()); 257 } 258 OS << '\n'; 259 } 260 } 261 } 262 263 const DWARFUnitIndex::Entry::SectionContribution * 264 DWARFUnitIndex::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 272 DWARFUnitIndex::Entry::SectionContribution & 273 DWARFUnitIndex::Entry::getContribution() { 274 return Contributions[Index->InfoColumn]; 275 } 276 277 const DWARFUnitIndex::Entry::SectionContribution * 278 DWARFUnitIndex::Entry::getContribution() const { 279 return &Contributions[Index->InfoColumn]; 280 } 281 282 const DWARFUnitIndex::Entry * 283 DWARFUnitIndex::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 306 const 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 slot 312 // 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 could 317 // 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