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