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
10 #include "llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
11
12 #include "llvm/ADT/ArrayRef.h"
13 #include "llvm/DebugInfo/PDB/Native/Hash.h"
14 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
15 #include "llvm/Support/BinaryStreamWriter.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
StringTableHashTraits(PDBStringTableBuilder & Table)26 StringTableHashTraits::StringTableHashTraits(PDBStringTableBuilder &Table)
27 : Table(&Table) {}
28
hashLookupKey(StringRef S) const29 uint32_t StringTableHashTraits::hashLookupKey(StringRef S) const {
30 return Table->getIdForString(S);
31 }
32
storageKeyToLookupKey(uint32_t Offset) const33 StringRef StringTableHashTraits::storageKeyToLookupKey(uint32_t Offset) const {
34 return Table->getStringForId(Offset);
35 }
36
lookupKeyToStorageKey(StringRef S)37 uint32_t StringTableHashTraits::lookupKeyToStorageKey(StringRef S) {
38 return Table->insert(S);
39 }
40
insert(StringRef S)41 uint32_t PDBStringTableBuilder::insert(StringRef S) {
42 return Strings.insert(S);
43 }
44
getIdForString(StringRef S) const45 uint32_t PDBStringTableBuilder::getIdForString(StringRef S) const {
46 return Strings.getIdForString(S);
47 }
48
getStringForId(uint32_t Id) const49 StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const {
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
computeBucketCount(uint32_t NumStrings)109 static uint32_t computeBucketCount(uint32_t NumStrings) {
110 auto Entry = StringsToBuckets.lower_bound(NumStrings);
111 assert(Entry != StringsToBuckets.end());
112 return Entry->second;
113 }
114
calculateHashTableSize() const115 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
calculateSerializedSize() const122 uint32_t PDBStringTableBuilder::calculateSerializedSize() const {
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
setStrings(const codeview::DebugStringTableSubsection & Strings)131 void PDBStringTableBuilder::setStrings(
132 const codeview::DebugStringTableSubsection &Strings) {
133 this->Strings = Strings;
134 }
135
writeHeader(BinaryStreamWriter & Writer) const136 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
137 // Write a header
138 PDBStringTableHeader H;
139 H.Signature = PDBStringTableSignature;
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
writeStrings(BinaryStreamWriter & Writer) const148 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
writeHashTable(BinaryStreamWriter & Writer) const156 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
writeEpilogue(BinaryStreamWriter & Writer) const184 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
commit(BinaryStreamWriter & Writer) const191 Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
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 }
213