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   return StringRef();
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     DWARFSectionKind Kind = ColumnKinds[i];
132     StringRef Name = getColumnHeader(Kind);
133     if (!Name.empty())
134       OS << ' ' << left_justify(Name, 24);
135     else
136       OS << format(" Unknown: %-15u", static_cast<unsigned>(Kind));
137   }
138   OS << "\n----- ------------------";
139   for (unsigned i = 0; i != Header.NumColumns; ++i)
140     OS << " ------------------------";
141   OS << '\n';
142   for (unsigned i = 0; i != Header.NumBuckets; ++i) {
143     auto &Row = Rows[i];
144     if (auto *Contribs = Row.Contributions.get()) {
145       OS << format("%5u 0x%016" PRIx64 " ", i + 1, Row.Signature);
146       for (unsigned i = 0; i != Header.NumColumns; ++i) {
147         auto &Contrib = Contribs[i];
148         OS << format("[0x%08x, 0x%08x) ", Contrib.Offset,
149                      Contrib.Offset + Contrib.Length);
150       }
151       OS << '\n';
152     }
153   }
154 }
155 
156 const DWARFUnitIndex::Entry::SectionContribution *
157 DWARFUnitIndex::Entry::getOffset(DWARFSectionKind Sec) const {
158   uint32_t i = 0;
159   for (; i != Index->Header.NumColumns; ++i)
160     if (Index->ColumnKinds[i] == Sec)
161       return &Contributions[i];
162   return nullptr;
163 }
164 
165 const DWARFUnitIndex::Entry::SectionContribution *
166 DWARFUnitIndex::Entry::getOffset() const {
167   return &Contributions[Index->InfoColumn];
168 }
169 
170 const DWARFUnitIndex::Entry *
171 DWARFUnitIndex::getFromOffset(uint32_t Offset) const {
172   if (OffsetLookup.empty()) {
173     for (uint32_t i = 0; i != Header.NumBuckets; ++i)
174       if (Rows[i].Contributions)
175         OffsetLookup.push_back(&Rows[i]);
176     llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) {
177       return E1->Contributions[InfoColumn].Offset <
178              E2->Contributions[InfoColumn].Offset;
179     });
180   }
181   auto I = partition_point(OffsetLookup, [&](Entry *E2) {
182     return E2->Contributions[InfoColumn].Offset <= Offset;
183   });
184   if (I == OffsetLookup.begin())
185     return nullptr;
186   --I;
187   const auto *E = *I;
188   const auto &InfoContrib = E->Contributions[InfoColumn];
189   if ((InfoContrib.Offset + InfoContrib.Length) <= Offset)
190     return nullptr;
191   return E;
192 }
193 
194 const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {
195   uint64_t Mask = Header.NumBuckets - 1;
196 
197   auto H = S & Mask;
198   auto HP = ((S >> 32) & Mask) | 1;
199   while (Rows[H].getSignature() != S && Rows[H].getSignature() != 0)
200     H = (H + HP) & Mask;
201 
202   if (Rows[H].getSignature() != S)
203     return nullptr;
204 
205   return &Rows[H];
206 }
207