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 bool DWARFUnitIndex::Header::parse(DataExtractor IndexData, 21 uint64_t *OffsetPtr) { 22 if (!IndexData.isValidOffsetForDataOfSize(*OffsetPtr, 16)) 23 return false; 24 Version = IndexData.getU32(OffsetPtr); 25 NumColumns = IndexData.getU32(OffsetPtr); 26 NumUnits = IndexData.getU32(OffsetPtr); 27 NumBuckets = IndexData.getU32(OffsetPtr); 28 return Version <= 2; 29 } 30 31 void DWARFUnitIndex::Header::dump(raw_ostream &OS) const { 32 OS << format("version = %u slots = %u\n\n", Version, NumBuckets); 33 } 34 35 bool DWARFUnitIndex::parse(DataExtractor IndexData) { 36 bool b = parseImpl(IndexData); 37 if (!b) { 38 // Make sure we don't try to dump anything 39 Header.NumBuckets = 0; 40 // Release any partially initialized data. 41 ColumnKinds.reset(); 42 Rows.reset(); 43 } 44 return b; 45 } 46 47 bool DWARFUnitIndex::parseImpl(DataExtractor IndexData) { 48 uint64_t Offset = 0; 49 if (!Header.parse(IndexData, &Offset)) 50 return false; 51 52 if (!IndexData.isValidOffsetForDataOfSize( 53 Offset, Header.NumBuckets * (8 + 4) + 54 (2 * Header.NumUnits + 1) * 4 * Header.NumColumns)) 55 return false; 56 57 Rows = std::make_unique<Entry[]>(Header.NumBuckets); 58 auto Contribs = 59 std::make_unique<Entry::SectionContribution *[]>(Header.NumUnits); 60 ColumnKinds = std::make_unique<DWARFSectionKind[]>(Header.NumColumns); 61 62 // Read Hash Table of Signatures 63 for (unsigned i = 0; i != Header.NumBuckets; ++i) 64 Rows[i].Signature = IndexData.getU64(&Offset); 65 66 // Read Parallel Table of Indexes 67 for (unsigned i = 0; i != Header.NumBuckets; ++i) { 68 auto Index = IndexData.getU32(&Offset); 69 if (!Index) 70 continue; 71 Rows[i].Index = this; 72 Rows[i].Contributions = 73 std::make_unique<Entry::SectionContribution[]>(Header.NumColumns); 74 Contribs[Index - 1] = Rows[i].Contributions.get(); 75 } 76 77 // Read the Column Headers 78 for (unsigned i = 0; i != Header.NumColumns; ++i) { 79 ColumnKinds[i] = static_cast<DWARFSectionKind>(IndexData.getU32(&Offset)); 80 if (ColumnKinds[i] == InfoColumnKind) { 81 if (InfoColumn != -1) 82 return false; 83 InfoColumn = i; 84 } 85 } 86 87 if (InfoColumn == -1) 88 return false; 89 90 // Read Table of Section Offsets 91 for (unsigned i = 0; i != Header.NumUnits; ++i) { 92 auto *Contrib = Contribs[i]; 93 for (unsigned i = 0; i != Header.NumColumns; ++i) 94 Contrib[i].Offset = IndexData.getU32(&Offset); 95 } 96 97 // Read Table of Section Sizes 98 for (unsigned i = 0; i != Header.NumUnits; ++i) { 99 auto *Contrib = Contribs[i]; 100 for (unsigned i = 0; i != Header.NumColumns; ++i) 101 Contrib[i].Length = IndexData.getU32(&Offset); 102 } 103 104 return true; 105 } 106 107 StringRef DWARFUnitIndex::getColumnHeader(DWARFSectionKind DS) { 108 #define CASE(DS) \ 109 case DW_SECT_##DS: \ 110 return #DS; 111 switch (DS) { 112 CASE(INFO); 113 CASE(TYPES); 114 CASE(ABBREV); 115 CASE(LINE); 116 CASE(LOC); 117 CASE(STR_OFFSETS); 118 CASE(MACINFO); 119 CASE(MACRO); 120 } 121 llvm_unreachable("unknown DWARFSectionKind"); 122 } 123 124 void DWARFUnitIndex::dump(raw_ostream &OS) const { 125 if (!*this) 126 return; 127 128 Header.dump(OS); 129 OS << "Index Signature "; 130 for (unsigned i = 0; i != Header.NumColumns; ++i) 131 OS << ' ' << left_justify(getColumnHeader(ColumnKinds[i]), 24); 132 OS << "\n----- ------------------"; 133 for (unsigned i = 0; i != Header.NumColumns; ++i) 134 OS << " ------------------------"; 135 OS << '\n'; 136 for (unsigned i = 0; i != Header.NumBuckets; ++i) { 137 auto &Row = Rows[i]; 138 if (auto *Contribs = Row.Contributions.get()) { 139 OS << format("%5u 0x%016" PRIx64 " ", i + 1, Row.Signature); 140 for (unsigned i = 0; i != Header.NumColumns; ++i) { 141 auto &Contrib = Contribs[i]; 142 OS << format("[0x%08x, 0x%08x) ", Contrib.Offset, 143 Contrib.Offset + Contrib.Length); 144 } 145 OS << '\n'; 146 } 147 } 148 } 149 150 const DWARFUnitIndex::Entry::SectionContribution * 151 DWARFUnitIndex::Entry::getOffset(DWARFSectionKind Sec) const { 152 uint32_t i = 0; 153 for (; i != Index->Header.NumColumns; ++i) 154 if (Index->ColumnKinds[i] == Sec) 155 return &Contributions[i]; 156 return nullptr; 157 } 158 159 const DWARFUnitIndex::Entry::SectionContribution * 160 DWARFUnitIndex::Entry::getOffset() const { 161 return &Contributions[Index->InfoColumn]; 162 } 163 164 const DWARFUnitIndex::Entry * 165 DWARFUnitIndex::getFromOffset(uint32_t Offset) const { 166 if (OffsetLookup.empty()) { 167 for (uint32_t i = 0; i != Header.NumBuckets; ++i) 168 if (Rows[i].Contributions) 169 OffsetLookup.push_back(&Rows[i]); 170 llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) { 171 return E1->Contributions[InfoColumn].Offset < 172 E2->Contributions[InfoColumn].Offset; 173 }); 174 } 175 auto I = partition_point(OffsetLookup, [&](Entry *E2) { 176 return E2->Contributions[InfoColumn].Offset <= Offset; 177 }); 178 if (I == OffsetLookup.begin()) 179 return nullptr; 180 --I; 181 const auto *E = *I; 182 const auto &InfoContrib = E->Contributions[InfoColumn]; 183 if ((InfoContrib.Offset + InfoContrib.Length) <= Offset) 184 return nullptr; 185 return E; 186 } 187 188 const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const { 189 uint64_t Mask = Header.NumBuckets - 1; 190 191 auto H = S & Mask; 192 auto HP = ((S >> 32) & Mask) | 1; 193 while (Rows[H].getSignature() != S && Rows[H].getSignature() != 0) 194 H = (H + HP) & Mask; 195 196 if (Rows[H].getSignature() != S) 197 return nullptr; 198 199 return &Rows[H]; 200 } 201