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