LLVM  8.0.0svn
PDBStringTableBuilder.cpp
Go to the documentation of this file.
1 //===- PDBStringTableBuilder.cpp - PDB String Table -------------*- C++ -*-===//
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/ArrayRef.h"
16 #include "llvm/Support/Endian.h"
17 
18 #include <map>
19 
20 using namespace llvm;
21 using namespace llvm::msf;
22 using namespace llvm::support;
23 using namespace llvm::support::endian;
24 using namespace llvm::pdb;
25 
26 StringTableHashTraits::StringTableHashTraits(PDBStringTableBuilder &Table)
27  : Table(&Table) {}
28 
30  return Table->getIdForString(S);
31 }
32 
34  return Table->getStringForId(Offset);
35 }
36 
38  return Table->insert(S);
39 }
40 
42  return Strings.insert(S);
43 }
44 
46  return Strings.getIdForString(S);
47 }
48 
50  return Strings.getStringForId(Id);
51 }
52 
53 // This is a precomputed list of Buckets given the specified number of
54 // strings. Matching the reference algorithm exactly is not strictly
55 // necessary for correctness, but it helps when comparing LLD's PDBs with
56 // Microsoft's PDBs so as to eliminate superfluous differences.
57 static std::map<uint32_t, uint32_t> StringsToBuckets = {
58  {1, 2},
59  {2, 4},
60  {4, 7},
61  {6, 11},
62  {9, 17},
63  {13, 26},
64  {20, 40},
65  {31, 61},
66  {46, 92},
67  {70, 139},
68  {105, 209},
69  {157, 314},
70  {236, 472},
71  {355, 709},
72  {532, 1064},
73  {799, 1597},
74  {1198, 2396},
75  {1798, 3595},
76  {2697, 5393},
77  {4045, 8090},
78  {6068, 12136},
79  {9103, 18205},
80  {13654, 27308},
81  {20482, 40963},
82  {30723, 61445},
83  {46084, 92168},
84  {69127, 138253},
85  {103690, 207380},
86  {155536, 311071},
87  {233304, 466607},
88  {349956, 699911},
89  {524934, 1049867},
90  {787401, 1574801},
91  {1181101, 2362202},
92  {1771652, 3543304},
93  {2657479, 5314957},
94  {3986218, 7972436},
95  {5979328, 11958655},
96  {8968992, 17937983},
97  {13453488, 26906975},
98  {20180232, 40360463},
99  {30270348, 60540695},
100  {45405522, 90811043},
101  {68108283, 136216565},
102  {102162424, 204324848},
103  {153243637, 306487273},
104  {229865455, 459730910},
105  {344798183, 689596366},
106  {517197275, 1034394550},
107  {775795913, 1551591826}};
108 
110  auto Entry = StringsToBuckets.lower_bound(NumStrings);
111  assert(Entry != StringsToBuckets.end());
112  return Entry->second;
113 }
114 
115 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
116  uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
117  Size += sizeof(uint32_t) * computeBucketCount(Strings.size());
118 
119  return Size;
120 }
121 
123  uint32_t Size = 0;
124  Size += sizeof(PDBStringTableHeader);
125  Size += Strings.calculateSerializedSize();
126  Size += calculateHashTableSize();
127  Size += sizeof(uint32_t); // The /names stream ends with the string count.
128  return Size;
129 }
130 
132  const codeview::DebugStringTableSubsection &Strings) {
133  this->Strings = Strings;
134 }
135 
136 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
137  // Write a header
140  H.HashVersion = 1;
141  H.ByteSize = Strings.calculateSerializedSize();
142  if (auto EC = Writer.writeObject(H))
143  return EC;
144  assert(Writer.bytesRemaining() == 0);
145  return Error::success();
146 }
147 
148 Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
149  if (auto EC = Strings.commit(Writer))
150  return EC;
151 
152  assert(Writer.bytesRemaining() == 0);
153  return Error::success();
154 }
155 
156 Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
157  // Write a hash table.
158  uint32_t BucketCount = computeBucketCount(Strings.size());
159  if (auto EC = Writer.writeInteger(BucketCount))
160  return EC;
161  std::vector<ulittle32_t> Buckets(BucketCount);
162 
163  for (auto &Pair : Strings) {
164  StringRef S = Pair.getKey();
165  uint32_t Offset = Pair.getValue();
166  uint32_t Hash = hashStringV1(S);
167 
168  for (uint32_t I = 0; I != BucketCount; ++I) {
169  uint32_t Slot = (Hash + I) % BucketCount;
170  if (Buckets[Slot] != 0)
171  continue;
172  Buckets[Slot] = Offset;
173  break;
174  }
175  }
176 
177  if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
178  return EC;
179 
180  assert(Writer.bytesRemaining() == 0);
181  return Error::success();
182 }
183 
184 Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
185  if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
186  return EC;
187  assert(Writer.bytesRemaining() == 0);
188  return Error::success();
189 }
190 
192  BinaryStreamWriter SectionWriter;
193 
194  std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
195  if (auto EC = writeHeader(SectionWriter))
196  return EC;
197 
198  std::tie(SectionWriter, Writer) =
199  Writer.split(Strings.calculateSerializedSize());
200  if (auto EC = writeStrings(SectionWriter))
201  return EC;
202 
203  std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
204  if (auto EC = writeHashTable(SectionWriter))
205  return EC;
206 
207  std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
208  if (auto EC = writeEpilogue(SectionWriter))
209  return EC;
210 
211  return Error::success();
212 }
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:316
StringRef getStringForId(uint32_t Id) const
uint32_t getIdForString(StringRef S) const
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
support::ulittle32_t HashVersion
Definition: RawTypes.h:315
static std::map< uint32_t, uint32_t > StringsToBuckets
constexpr int I
Definition: RawTypes.h:346
Error commit(BinaryStreamWriter &Writer) const
The header preceeding the /names stream.
Definition: RawTypes.h:313
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
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:21
#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:314
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:327
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:52
uint32_t Size
Definition: Profile.cpp:47
const uint32_t PDBStringTableSignature
Definition: RawTypes.h:319
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:158
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49