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 
9 #include "llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
10 
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/DebugInfo/PDB/Native/Hash.h"
13 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
14 #include "llvm/Support/BinaryStreamWriter.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 
28 uint32_t StringTableHashTraits::hashLookupKey(StringRef S) const {
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 
38 StringRef StringTableHashTraits::storageKeyToLookupKey(uint32_t Offset) const {
39   return Table->getStringForId(Offset);
40 }
41 
42 uint32_t StringTableHashTraits::lookupKeyToStorageKey(StringRef S) {
43   return Table->insert(S);
44 }
45 
46 uint32_t PDBStringTableBuilder::insert(StringRef S) {
47   return Strings.insert(S);
48 }
49 
50 uint32_t PDBStringTableBuilder::getIdForString(StringRef S) const {
51   return Strings.getIdForString(S);
52 }
53 
54 StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const {
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   static std::map<uint32_t, uint32_t> StringsToBuckets = {
64       {1, 2},
65       {2, 4},
66       {4, 7},
67       {6, 11},
68       {9, 17},
69       {13, 26},
70       {20, 40},
71       {31, 61},
72       {46, 92},
73       {70, 139},
74       {105, 209},
75       {157, 314},
76       {236, 472},
77       {355, 709},
78       {532, 1064},
79       {799, 1597},
80       {1198, 2396},
81       {1798, 3595},
82       {2697, 5393},
83       {4045, 8090},
84       {6068, 12136},
85       {9103, 18205},
86       {13654, 27308},
87       {20482, 40963},
88       {30723, 61445},
89       {46084, 92168},
90       {69127, 138253},
91       {103690, 207380},
92       {155536, 311071},
93       {233304, 466607},
94       {349956, 699911},
95       {524934, 1049867},
96       {787401, 1574801},
97       {1181101, 2362202},
98       {1771652, 3543304},
99       {2657479, 5314957},
100       {3986218, 7972436},
101       {5979328, 11958655},
102       {8968992, 17937983},
103       {13453488, 26906975},
104       {20180232, 40360463},
105       {30270348, 60540695},
106       {45405522, 90811043},
107       {68108283, 136216565},
108       {102162424, 204324848},
109       {153243637, 306487273},
110       {229865455, 459730910},
111       {344798183, 689596366},
112       {517197275, 1034394550},
113       {775795913, 1551591826}};
114   auto Entry = StringsToBuckets.lower_bound(NumStrings);
115   assert(Entry != StringsToBuckets.end());
116   return Entry->second;
117 }
118 
119 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
120   uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
121   Size += sizeof(uint32_t) * computeBucketCount(Strings.size());
122 
123   return Size;
124 }
125 
126 uint32_t PDBStringTableBuilder::calculateSerializedSize() const {
127   uint32_t Size = 0;
128   Size += sizeof(PDBStringTableHeader);
129   Size += Strings.calculateSerializedSize();
130   Size += calculateHashTableSize();
131   Size += sizeof(uint32_t); // The /names stream ends with the string count.
132   return Size;
133 }
134 
135 void PDBStringTableBuilder::setStrings(
136     const codeview::DebugStringTableSubsection &Strings) {
137   this->Strings = Strings;
138 }
139 
140 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
141   // Write a header
142   PDBStringTableHeader H;
143   H.Signature = PDBStringTableSignature;
144   H.HashVersion = 1;
145   H.ByteSize = Strings.calculateSerializedSize();
146   if (auto EC = Writer.writeObject(H))
147     return EC;
148   assert(Writer.bytesRemaining() == 0);
149   return Error::success();
150 }
151 
152 Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
153   if (auto EC = Strings.commit(Writer))
154     return EC;
155 
156   assert(Writer.bytesRemaining() == 0);
157   return Error::success();
158 }
159 
160 Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
161   // Write a hash table.
162   uint32_t BucketCount = computeBucketCount(Strings.size());
163   if (auto EC = Writer.writeInteger(BucketCount))
164     return EC;
165   std::vector<ulittle32_t> Buckets(BucketCount);
166 
167   for (auto &Pair : Strings) {
168     StringRef S = Pair.getKey();
169     uint32_t Offset = Pair.getValue();
170     uint32_t Hash = hashStringV1(S);
171 
172     for (uint32_t I = 0; I != BucketCount; ++I) {
173       uint32_t Slot = (Hash + I) % BucketCount;
174       if (Buckets[Slot] != 0)
175         continue;
176       Buckets[Slot] = Offset;
177       break;
178     }
179   }
180 
181   if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
182     return EC;
183 
184   assert(Writer.bytesRemaining() == 0);
185   return Error::success();
186 }
187 
188 Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
189   if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
190     return EC;
191   assert(Writer.bytesRemaining() == 0);
192   return Error::success();
193 }
194 
195 Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
196   BinaryStreamWriter SectionWriter;
197 
198   std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
199   if (auto EC = writeHeader(SectionWriter))
200     return EC;
201 
202   std::tie(SectionWriter, Writer) =
203       Writer.split(Strings.calculateSerializedSize());
204   if (auto EC = writeStrings(SectionWriter))
205     return EC;
206 
207   std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
208   if (auto EC = writeHashTable(SectionWriter))
209     return EC;
210 
211   std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
212   if (auto EC = writeEpilogue(SectionWriter))
213     return EC;
214 
215   return Error::success();
216 }
217