LLVM  6.0.0svn
DWARFAcceleratorTable.cpp
Go to the documentation of this file.
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 
11 
12 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/Support/Compiler.h"
17 #include "llvm/Support/Format.h"
19 #include <cstddef>
20 #include <cstdint>
21 #include <utility>
22 
23 using namespace llvm;
24 
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; }
62  return Hdr.HeaderDataLength;
63 }
64 
65 ArrayRef<std::pair<DWARFAcceleratorTable::HeaderData::AtomType,
68  return HdrData.Atoms;
69 }
70 
72  for (auto Atom : getAtomsDesc()) {
73  DWARFFormValue FormValue(Atom.second);
74  switch (Atom.first) {
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>
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) {
100  DieOffset = *FormValue.getAsUnsignedConstant();
101  break;
103  DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
104  break;
105  default:
106  break;
107  }
108  }
109  return {DieOffset, DieTag};
110 }
111 
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;
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 
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,
223  for (auto &Atom : AtomForms)
224  Atom.extractValue(AccelSection, &DataOffset, FormParams);
225  ++Data;
226 }
227 
230  if (!IsValid)
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  }
263 }
This implements the Apple accelerator table format, a precursor of the DWARF 5 accelerator table form...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
StringRef AtomTypeString(unsigned Atom)
Definition: Dwarf.cpp:490
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
uint16_t getU16(uint32_t *offset_ptr) const
Extract a uint16_t value from *offset_ptr.
bool isFormClass(FormClass FC) const
dwarf::Form getForm() const
uint32_t getU32(uint32_t *offset_ptr) const
Extract a uint32_t value from *offset_ptr.
std::pair< uint32_t, dwarf::Tag > readAtoms(uint32_t &HashDataOffset)
Return information related to the DWARF DIE we&#39;re looking for when performing a lookup by name...
StringRef FormEncodingString(unsigned Encoding)
Definition: Dwarf.cpp:105
Key
PAL metadata keys.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
bool isValidOffsetForDataOfSize(uint32_t offset, uint32_t length) const
Test the availability of length bytes of data from offset.
const uint32_t DW_INVALID_OFFSET
Identifier of an invalid DIE offset in the .debug_info section.
Definition: Dwarf.h:68
Optional< uint64_t > getAsUnsignedConstant() const
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in the accelerator table matching Key.
uint64_t getRelocatedValue(uint32_t Size, uint32_t *Off, uint64_t *SectionIndex=nullptr) const
Extracts a value and applies a relocation to the result if one exists for the given offset...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
ArrayRef< std::pair< HeaderData::AtomType, HeaderData::Form > > getAtomsDesc()
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
A helper struct for DWARFFormValue methods, providing information that allows it to know the byte siz...
A range adaptor for a pair of iterators.
This file contains constants used for implementing Dwarf debug support.
uint32_t djbHash(StringRef Buffer)
The Bernstein hash function used by the accelerator tables.
Definition: Dwarf.cpp:579
void dump(raw_ostream &OS) const
const char * getCStr(uint32_t *offset_ptr) const
Extract a C string from *offset_ptr.
bool isValidOffset(uint32_t offset) const
Test the validity of offset.
bool extractValue(const DWARFDataExtractor &Data, uint32_t *OffsetPtr, DWARFFormParams FormParams, const DWARFUnit *U=nullptr)
Extracts a value in Data at offset *OffsetPtr.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49