Line data Source code
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 :
26 111 : StringTableHashTraits::StringTableHashTraits(PDBStringTableBuilder &Table)
27 111 : : Table(&Table) {}
28 :
29 0 : uint32_t StringTableHashTraits::hashLookupKey(StringRef S) const {
30 0 : return Table->getIdForString(S);
31 : }
32 :
33 0 : StringRef StringTableHashTraits::storageKeyToLookupKey(uint32_t Offset) const {
34 0 : return Table->getStringForId(Offset);
35 : }
36 :
37 0 : uint32_t StringTableHashTraits::lookupKeyToStorageKey(StringRef S) {
38 0 : return Table->insert(S);
39 : }
40 :
41 100 : uint32_t PDBStringTableBuilder::insert(StringRef S) {
42 100 : return Strings.insert(S);
43 : }
44 :
45 0 : uint32_t PDBStringTableBuilder::getIdForString(StringRef S) const {
46 0 : return Strings.getIdForString(S);
47 : }
48 :
49 0 : StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const {
50 0 : 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 :
109 : static uint32_t computeBucketCount(uint32_t NumStrings) {
110 : auto Entry = StringsToBuckets.lower_bound(NumStrings);
111 : assert(Entry != StringsToBuckets.end());
112 768 : return Entry->second;
113 : }
114 :
115 548 : uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
116 : uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
117 548 : Size += sizeof(uint32_t) * computeBucketCount(Strings.size());
118 :
119 548 : return Size;
120 : }
121 :
122 328 : uint32_t PDBStringTableBuilder::calculateSerializedSize() const {
123 : uint32_t Size = 0;
124 : Size += sizeof(PDBStringTableHeader);
125 328 : Size += Strings.calculateSerializedSize();
126 328 : Size += calculateHashTableSize();
127 328 : Size += sizeof(uint32_t); // The /names stream ends with the string count.
128 328 : return Size;
129 : }
130 :
131 108 : void PDBStringTableBuilder::setStrings(
132 : const codeview::DebugStringTableSubsection &Strings) {
133 108 : this->Strings = Strings;
134 108 : }
135 :
136 220 : Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
137 : // Write a header
138 : PDBStringTableHeader H;
139 : H.Signature = PDBStringTableSignature;
140 : H.HashVersion = 1;
141 220 : H.ByteSize = Strings.calculateSerializedSize();
142 220 : if (auto EC = Writer.writeObject(H))
143 : return EC;
144 : assert(Writer.bytesRemaining() == 0);
145 : return Error::success();
146 : }
147 :
148 220 : Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
149 440 : if (auto EC = Strings.commit(Writer))
150 : return EC;
151 :
152 : assert(Writer.bytesRemaining() == 0);
153 : return Error::success();
154 : }
155 :
156 220 : Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
157 : // Write a hash table.
158 220 : uint32_t BucketCount = computeBucketCount(Strings.size());
159 440 : if (auto EC = Writer.writeInteger(BucketCount))
160 : return EC;
161 220 : std::vector<ulittle32_t> Buckets(BucketCount);
162 :
163 490 : for (auto &Pair : Strings) {
164 270 : StringRef S = Pair.getKey();
165 270 : uint32_t Offset = Pair.getValue();
166 270 : uint32_t Hash = hashStringV1(S);
167 :
168 310 : for (uint32_t I = 0; I != BucketCount; ++I) {
169 310 : uint32_t Slot = (Hash + I) % BucketCount;
170 620 : if (Buckets[Slot] != 0)
171 : continue;
172 : Buckets[Slot] = Offset;
173 : break;
174 : }
175 : }
176 :
177 220 : 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 220 : Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
185 440 : if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
186 : return EC;
187 : assert(Writer.bytesRemaining() == 0);
188 : return Error::success();
189 : }
190 :
191 220 : Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
192 : BinaryStreamWriter SectionWriter;
193 :
194 220 : std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
195 440 : if (auto EC = writeHeader(SectionWriter))
196 : return EC;
197 :
198 220 : std::tie(SectionWriter, Writer) =
199 220 : Writer.split(Strings.calculateSerializedSize());
200 440 : if (auto EC = writeStrings(SectionWriter))
201 : return EC;
202 :
203 220 : std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
204 440 : if (auto EC = writeHashTable(SectionWriter))
205 : return EC;
206 :
207 220 : std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
208 440 : if (auto EC = writeEpilogue(SectionWriter))
209 : return EC;
210 :
211 : return Error::success();
212 : }
|
