1 //===- DWARFAcceleratorTable.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/DWARFAcceleratorTable.h"
11 
12 #include "llvm/ADT/SmallVector.h"
13 #include "llvm/BinaryFormat/Dwarf.h"
14 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
15 #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
16 #include "llvm/Support/Compiler.h"
17 #include "llvm/Support/Format.h"
18 #include "llvm/Support/raw_ostream.h"
19 #include <cstddef>
20 #include <cstdint>
21 #include <utility>
22 
23 using namespace llvm;
24 
25 bool DWARFAcceleratorTable::extract() {
26   uint32_t Offset = 0;
27 
28   // Check that we can at least read the header.
29   if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength)+4))
30     return false;
31 
32   Hdr.Magic = AccelSection.getU32(&Offset);
33   Hdr.Version = AccelSection.getU16(&Offset);
34   Hdr.HashFunction = AccelSection.getU16(&Offset);
35   Hdr.NumBuckets = AccelSection.getU32(&Offset);
36   Hdr.NumHashes = AccelSection.getU32(&Offset);
37   Hdr.HeaderDataLength = AccelSection.getU32(&Offset);
38 
39   // Check that we can read all the hashes and offsets from the
40   // section (see SourceLevelDebugging.rst for the structure of the index).
41   if (!AccelSection.isValidOffset(sizeof(Hdr) + Hdr.HeaderDataLength +
42                                   Hdr.NumBuckets*4 + Hdr.NumHashes*8))
43     return false;
44 
45   HdrData.DIEOffsetBase = AccelSection.getU32(&Offset);
46   uint32_t NumAtoms = AccelSection.getU32(&Offset);
47 
48   for (unsigned i = 0; i < NumAtoms; ++i) {
49     uint16_t AtomType = AccelSection.getU16(&Offset);
50     auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset));
51     HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));
52   }
53 
54   IsValid = true;
55   return true;
56 }
57 
58 uint32_t DWARFAcceleratorTable::getNumBuckets() { return Hdr.NumBuckets; }
59 uint32_t DWARFAcceleratorTable::getNumHashes() { return Hdr.NumHashes; }
60 uint32_t DWARFAcceleratorTable::getSizeHdr() { return sizeof(Hdr); }
61 uint32_t DWARFAcceleratorTable::getHeaderDataLength() {
62   return Hdr.HeaderDataLength;
63 }
64 
65 ArrayRef<std::pair<DWARFAcceleratorTable::HeaderData::AtomType,
66                    DWARFAcceleratorTable::HeaderData::Form>>
67 DWARFAcceleratorTable::getAtomsDesc() {
68   return HdrData.Atoms;
69 }
70 
71 bool DWARFAcceleratorTable::validateForms() {
72   for (auto Atom : getAtomsDesc()) {
73     DWARFFormValue FormValue(Atom.second);
74     switch (Atom.first) {
75     case dwarf::DW_ATOM_die_offset:
76     case dwarf::DW_ATOM_die_tag:
77     case dwarf::DW_ATOM_type_flags:
78       if ((!FormValue.isFormClass(DWARFFormValue::FC_Constant) &&
79            !FormValue.isFormClass(DWARFFormValue::FC_Flag)) ||
80           FormValue.getForm() == dwarf::DW_FORM_sdata)
81         return false;
82     default:
83       break;
84     }
85   }
86   return true;
87 }
88 
89 std::pair<uint32_t, dwarf::Tag>
90 DWARFAcceleratorTable::readAtoms(uint32_t &HashDataOffset) {
91   uint32_t DieOffset = dwarf::DW_INVALID_OFFSET;
92   dwarf::Tag DieTag = dwarf::DW_TAG_null;
93   DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
94 
95   for (auto Atom : getAtomsDesc()) {
96     DWARFFormValue FormValue(Atom.second);
97     FormValue.extractValue(AccelSection, &HashDataOffset, FormParams);
98     switch (Atom.first) {
99     case dwarf::DW_ATOM_die_offset:
100       DieOffset = *FormValue.getAsUnsignedConstant();
101       break;
102     case dwarf::DW_ATOM_die_tag:
103       DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
104       break;
105     default:
106       break;
107     }
108   }
109   return {DieOffset, DieTag};
110 }
111 
112 LLVM_DUMP_METHOD void DWARFAcceleratorTable::dump(raw_ostream &OS) const {
113   if (!IsValid)
114     return;
115 
116   // Dump the header.
117   OS << "Magic = " << format("0x%08x", Hdr.Magic) << '\n'
118      << "Version = " << format("0x%04x", Hdr.Version) << '\n'
119      << "Hash function = " << format("0x%08x", Hdr.HashFunction) << '\n'
120      << "Bucket count = " << Hdr.NumBuckets << '\n'
121      << "Hashes count = " << Hdr.NumHashes << '\n'
122      << "HeaderData length = " << Hdr.HeaderDataLength << '\n'
123      << "DIE offset base = " << HdrData.DIEOffsetBase << '\n'
124      << "Number of atoms = " << HdrData.Atoms.size() << '\n';
125 
126   unsigned i = 0;
127   SmallVector<DWARFFormValue, 3> AtomForms;
128   for (const auto &Atom: HdrData.Atoms) {
129     OS << format("Atom[%d] Type: ", i++);
130     auto TypeString = dwarf::AtomTypeString(Atom.first);
131     if (!TypeString.empty())
132       OS << TypeString;
133     else
134       OS << format("DW_ATOM_Unknown_0x%x", Atom.first);
135     OS << " Form: ";
136     auto FormString = dwarf::FormEncodingString(Atom.second);
137     if (!FormString.empty())
138       OS << FormString;
139     else
140       OS << format("DW_FORM_Unknown_0x%x", Atom.second);
141     OS << '\n';
142     AtomForms.push_back(DWARFFormValue(Atom.second));
143   }
144 
145   // Now go through the actual tables and dump them.
146   uint32_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;
147   unsigned HashesBase = Offset + Hdr.NumBuckets * 4;
148   unsigned OffsetsBase = HashesBase + Hdr.NumHashes * 4;
149   DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
150 
151   for (unsigned Bucket = 0; Bucket < Hdr.NumBuckets; ++Bucket) {
152     unsigned Index = AccelSection.getU32(&Offset);
153 
154     OS << format("Bucket[%d]\n", Bucket);
155     if (Index == UINT32_MAX) {
156       OS << "  EMPTY\n";
157       continue;
158     }
159 
160     for (unsigned HashIdx = Index; HashIdx < Hdr.NumHashes; ++HashIdx) {
161       unsigned HashOffset = HashesBase + HashIdx*4;
162       unsigned OffsetsOffset = OffsetsBase + HashIdx*4;
163       uint32_t Hash = AccelSection.getU32(&HashOffset);
164 
165       if (Hash % Hdr.NumBuckets != Bucket)
166         break;
167 
168       unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
169       OS << format("  Hash = 0x%08x Offset = 0x%08x\n", Hash, DataOffset);
170       if (!AccelSection.isValidOffset(DataOffset)) {
171         OS << "    Invalid section offset\n";
172         continue;
173       }
174       while (AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
175         unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset);
176         if (!StringOffset)
177           break;
178         OS << format("    Name: %08x \"%s\"\n", StringOffset,
179                      StringSection.getCStr(&StringOffset));
180         unsigned NumData = AccelSection.getU32(&DataOffset);
181         for (unsigned Data = 0; Data < NumData; ++Data) {
182           OS << format("    Data[%d] => ", Data);
183           unsigned i = 0;
184           for (auto &Atom : AtomForms) {
185             OS << format("{Atom[%d]: ", i++);
186             if (Atom.extractValue(AccelSection, &DataOffset, FormParams))
187               Atom.dump(OS);
188             else
189               OS << "Error extracting the value";
190             OS << "} ";
191           }
192           OS << '\n';
193         }
194       }
195     }
196   }
197 }
198 
199 DWARFAcceleratorTable::ValueIterator::ValueIterator(
200     const DWARFAcceleratorTable &AccelTable, unsigned Offset)
201     : AccelTable(&AccelTable), DataOffset(Offset) {
202   if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4))
203     return;
204 
205   for (const auto &Atom : AccelTable.HdrData.Atoms)
206     AtomForms.push_back(DWARFFormValue(Atom.second));
207 
208   // Read the first entry.
209   NumData = AccelTable.AccelSection.getU32(&DataOffset);
210   Next();
211 }
212 
213 void DWARFAcceleratorTable::ValueIterator::Next() {
214   assert(NumData > 0 && "attempted to increment iterator past the end");
215   auto &AccelSection = AccelTable->AccelSection;
216   if (Data >= NumData ||
217       !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
218     NumData = 0;
219     return;
220   }
221   DWARFFormParams FormParams = {AccelTable->Hdr.Version, 0,
222                                 dwarf::DwarfFormat::DWARF32};
223   for (auto &Atom : AtomForms)
224     Atom.extractValue(AccelSection, &DataOffset, FormParams);
225   ++Data;
226 }
227 
228 iterator_range<DWARFAcceleratorTable::ValueIterator>
229 DWARFAcceleratorTable::equal_range(StringRef Key) const {
230   if (!IsValid)
231     return make_range(ValueIterator(), ValueIterator());
232 
233   // Find the bucket.
234   unsigned HashValue = dwarf::djbHash(Key);
235   unsigned Bucket = HashValue % Hdr.NumBuckets;
236   unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
237   unsigned HashesBase = BucketBase + Hdr.NumBuckets * 4;
238   unsigned OffsetsBase = HashesBase + Hdr.NumHashes * 4;
239 
240   unsigned BucketOffset = BucketBase + Bucket * 4;
241   unsigned Index = AccelSection.getU32(&BucketOffset);
242 
243   // Search through all hashes in the bucket.
244   for (unsigned HashIdx = Index; HashIdx < Hdr.NumHashes; ++HashIdx) {
245     unsigned HashOffset = HashesBase + HashIdx * 4;
246     unsigned OffsetsOffset = OffsetsBase + HashIdx * 4;
247     uint32_t Hash = AccelSection.getU32(&HashOffset);
248 
249     if (Hash % Hdr.NumBuckets != Bucket)
250       // We are already in the next bucket.
251       break;
252 
253     unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
254     unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset);
255     if (!StringOffset)
256       break;
257 
258     // Finally, compare the key.
259     if (Key == StringSection.getCStr(&StringOffset))
260       return make_range({*this, DataOffset}, ValueIterator());
261   }
262   return make_range(ValueIterator(), ValueIterator());
263 }
264