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