LLVM  10.0.0svn
PDBStringTableBuilder.cpp
Go to the documentation of this file.
1 //===- PDBStringTableBuilder.cpp - PDB String Table -------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
10 
11 #include "llvm/ADT/ArrayRef.h"
15 #include "llvm/Support/Endian.h"
16 
17 #include <map>
18 
19 using namespace llvm;
20 using namespace llvm::msf;
21 using namespace llvm::support;
22 using namespace llvm::support::endian;
23 using namespace llvm::pdb;
24 
25 StringTableHashTraits::StringTableHashTraits(PDBStringTableBuilder &Table)
26  : Table(&Table) {}
27 
29  // The reference implementation doesn't include code for /src/headerblock
30  // handling, but it can only read natvis entries lld's PDB files if
31  // this hash function truncates the hash to 16 bit.
32  // PDB/include/misc.h in the reference implementation has a hashSz() function
33  // that returns an unsigned short, that seems what's being used for
34  // /src/headerblock.
35  return static_cast<uint16_t>(Table->getIdForString(S));
36 }
37 
39  return Table->getStringForId(Offset);
40 }
41 
43  return Table->insert(S);
44 }
45 
47  return Strings.insert(S);
48 }
49 
51  return Strings.getIdForString(S);
52 }
53 
55  return Strings.getStringForId(Id);
56 }
57 
58 static uint32_t computeBucketCount(uint32_t NumStrings) {
59  // This is a precomputed list of Buckets given the specified number of
60  // strings. Matching the reference algorithm exactly is not strictly
61  // necessary for correctness, but it helps when comparing LLD's PDBs with
62  // Microsoft's PDBs so as to eliminate superfluous differences.
63  // The reference implementation does (in nmt.h, NMT::grow()):
64  // unsigned StringCount = 0;
65  // unsigned BucketCount = 1;
66  // fn insert() {
67  // ++StringCount;
68  // if (BucketCount * 3 / 4 < StringCount)
69  // BucketCount = BucketCount * 3 / 2 + 1;
70  // }
71  // This list contains all StringCount, BucketCount pairs where BucketCount was
72  // just incremented. It ends before the first BucketCount entry where
73  // BucketCount * 3 would overflow a 32-bit unsigned int.
74  static std::map<uint32_t, uint32_t> StringsToBuckets = {
75  {0, 1},
76  {1, 2},
77  {2, 4},
78  {4, 7},
79  {6, 11},
80  {9, 17},
81  {13, 26},
82  {20, 40},
83  {31, 61},
84  {46, 92},
85  {70, 139},
86  {105, 209},
87  {157, 314},
88  {236, 472},
89  {355, 709},
90  {532, 1064},
91  {799, 1597},
92  {1198, 2396},
93  {1798, 3595},
94  {2697, 5393},
95  {4045, 8090},
96  {6068, 12136},
97  {9103, 18205},
98  {13654, 27308},
99  {20482, 40963},
100  {30723, 61445},
101  {46084, 92168},
102  {69127, 138253},
103  {103690, 207380},
104  {155536, 311071},
105  {233304, 466607},
106  {349956, 699911},
107  {524934, 1049867},
108  {787401, 1574801},
109  {1181101, 2362202},
110  {1771652, 3543304},
111  {2657479, 5314957},
112  {3986218, 7972436},
113  {5979328, 11958655},
114  {8968992, 17937983},
115  {13453488, 26906975},
116  {20180232, 40360463},
117  {30270348, 60540695},
118  {45405522, 90811043},
119  {68108283, 136216565},
120  {102162424, 204324848},
121  {153243637, 306487273},
122  {229865455, 459730910},
123  {344798183, 689596366},
124  {517197275, 1034394550},
125  {775795913, 1551591826},
126  {1163693870, 2327387740}};
127  auto Entry = StringsToBuckets.lower_bound(NumStrings);
128  assert(Entry != StringsToBuckets.end());
129  return Entry->second;
130 }
131 
132 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
133  uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
134  Size += sizeof(uint32_t) * computeBucketCount(Strings.size());
135 
136  return Size;
137 }
138 
140  uint32_t Size = 0;
141  Size += sizeof(PDBStringTableHeader);
142  Size += Strings.calculateSerializedSize();
143  Size += calculateHashTableSize();
144  Size += sizeof(uint32_t); // The /names stream ends with the string count.
145  return Size;
146 }
147 
149  const codeview::DebugStringTableSubsection &Strings) {
150  this->Strings = Strings;
151 }
152 
153 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
154  // Write a header
157  H.HashVersion = 1;
158  H.ByteSize = Strings.calculateSerializedSize();
159  if (auto EC = Writer.writeObject(H))
160  return EC;
161  assert(Writer.bytesRemaining() == 0);
162  return Error::success();
163 }
164 
165 Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
166  if (auto EC = Strings.commit(Writer))
167  return EC;
168 
169  assert(Writer.bytesRemaining() == 0);
170  return Error::success();
171 }
172 
173 Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
174  // Write a hash table.
175  uint32_t BucketCount = computeBucketCount(Strings.size());
176  if (auto EC = Writer.writeInteger(BucketCount))
177  return EC;
178  std::vector<ulittle32_t> Buckets(BucketCount);
179 
180  for (auto &Pair : Strings) {
181  StringRef S = Pair.getKey();
182  uint32_t Offset = Pair.getValue();
183  uint32_t Hash = hashStringV1(S);
184 
185  for (uint32_t I = 0; I != BucketCount; ++I) {
186  uint32_t Slot = (Hash + I) % BucketCount;
187  if (Buckets[Slot] != 0)
188  continue;
189  Buckets[Slot] = Offset;
190  break;
191  }
192  }
193 
194  if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
195  return EC;
196 
197  assert(Writer.bytesRemaining() == 0);
198  return Error::success();
199 }
200 
201 Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
202  if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
203  return EC;
204  assert(Writer.bytesRemaining() == 0);
205  return Error::success();
206 }
207 
209  BinaryStreamWriter SectionWriter;
210 
211  std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
212  if (auto EC = writeHeader(SectionWriter))
213  return EC;
214 
215  std::tie(SectionWriter, Writer) =
216  Writer.split(Strings.calculateSerializedSize());
217  if (auto EC = writeStrings(SectionWriter))
218  return EC;
219 
220  std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
221  if (auto EC = writeHashTable(SectionWriter))
222  return EC;
223 
224  std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
225  if (auto EC = writeEpilogue(SectionWriter))
226  return EC;
227 
228  return Error::success();
229 }
Error writeObject(const T &Obj)
Writes the object Obj to the underlying stream, as if by using memcpy.
support::ulittle32_t ByteSize
Definition: RawTypes.h:315
StringRef getStringForId(uint32_t Id) const
uint32_t getIdForString(StringRef S) const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
support::ulittle32_t HashVersion
Definition: RawTypes.h:314
Error commit(BinaryStreamWriter &Writer) const
The header preceding the /names stream.
Definition: RawTypes.h:312
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Error writeArray(ArrayRef< T > Array)
Writes an array of objects of type T to the underlying stream, as if by using memcpy.
uint32_t hashLookupKey(StringRef S) const
void setStrings(const codeview::DebugStringTableSubsection &Strings)
static uint32_t computeBucketCount(uint32_t NumStrings)
uint32_t hashStringV1(StringRef Str)
Definition: Hash.cpp:20
#define H(x, y, z)
Definition: MD5.cpp:57
Provides write only access to a subclass of WritableBinaryStream.
support::ulittle32_t Signature
Definition: RawTypes.h:313
Error writeInteger(T Value)
Write the integer Value to the underlying stream in the specified endianness.
uint32_t bytesRemaining() const
static ErrorSuccess success()
Create a success value.
Definition: Error.h:326
Represents a read-write view of a CodeView string table.
std::pair< BinaryStreamWriter, BinaryStreamWriter > split(uint32_t Off) const
Splits the Writer into two Writers at a given offset.
Adapter to write values to a stream in a particular byte order.
Definition: EndianStream.h:51
#define I(x, y, z)
Definition: MD5.cpp:58
uint32_t Size
Definition: Profile.cpp:46
const uint32_t PDBStringTableSignature
Definition: RawTypes.h:318
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StringRef storageKeyToLookupKey(uint32_t Offset) const
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48