1 //===- DbiStreamBuilder.cpp - PDB Dbi Stream Creation -----------*- 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 // The data structures defined in this file are based on the reference
10 // implementation which is available at
11 // https://github.com/Microsoft/microsoft-pdb/blob/master/PDB/dbi/gsi.cpp
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/DebugInfo/PDB/Native/GSIStreamBuilder.h"
16 
17 #include "llvm/ADT/DenseSet.h"
18 #include "llvm/DebugInfo/CodeView/RecordName.h"
19 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"
20 #include "llvm/DebugInfo/CodeView/SymbolRecord.h"
21 #include "llvm/DebugInfo/CodeView/SymbolSerializer.h"
22 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
23 #include "llvm/DebugInfo/MSF/MSFCommon.h"
24 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
25 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
26 #include "llvm/DebugInfo/PDB/Native/Hash.h"
27 #include "llvm/Support/BinaryItemStream.h"
28 #include "llvm/Support/BinaryStreamWriter.h"
29 #include "llvm/Support/Parallel.h"
30 #include "llvm/Support/xxhash.h"
31 #include <algorithm>
32 #include <vector>
33 
34 using namespace llvm;
35 using namespace llvm::msf;
36 using namespace llvm::pdb;
37 using namespace llvm::codeview;
38 
39 struct llvm::pdb::GSIHashStreamBuilder {
40   struct SymbolDenseMapInfo {
41     static inline CVSymbol getEmptyKey() {
42       static CVSymbol Empty;
43       return Empty;
44     }
45     static inline CVSymbol getTombstoneKey() {
46       static CVSymbol Tombstone(
47           DenseMapInfo<ArrayRef<uint8_t>>::getTombstoneKey());
48       return Tombstone;
49     }
50     static unsigned getHashValue(const CVSymbol &Val) {
51       return xxHash64(Val.RecordData);
52     }
53     static bool isEqual(const CVSymbol &LHS, const CVSymbol &RHS) {
54       return LHS.RecordData == RHS.RecordData;
55     }
56   };
57 
58   std::vector<CVSymbol> Records;
59   llvm::DenseSet<CVSymbol, SymbolDenseMapInfo> SymbolHashes;
60   std::vector<PSHashRecord> HashRecords;
61   std::array<support::ulittle32_t, (IPHR_HASH + 32) / 32> HashBitmap;
62   std::vector<support::ulittle32_t> HashBuckets;
63 
64   uint32_t calculateSerializedLength() const;
65   uint32_t calculateRecordByteSize() const;
66   Error commit(BinaryStreamWriter &Writer);
67 
68   void finalizeBuckets(uint32_t RecordZeroOffset);
69 
70   // Finalize public symbol buckets.
71   void finalizeBuckets(uint32_t RecordZeroOffset,
72                        std::vector<BulkPublic> &&Publics);
73 
74   template <typename T> void addSymbol(const T &Symbol, MSFBuilder &Msf) {
75     T Copy(Symbol);
76     addSymbol(SymbolSerializer::writeOneSymbol(Copy, Msf.getAllocator(),
77                                                CodeViewContainer::Pdb));
78   }
79   void addSymbol(const CVSymbol &Symbol);
80 };
81 
82 void GSIHashStreamBuilder::addSymbol(const codeview::CVSymbol &Symbol) {
83   // Ignore duplicate typedefs and constants.
84   if (Symbol.kind() == S_UDT || Symbol.kind() == S_CONSTANT) {
85     auto Iter = SymbolHashes.insert(Symbol);
86     if (!Iter.second)
87       return;
88   }
89   Records.push_back(Symbol);
90 }
91 
92 namespace {
93 LLVM_PACKED(struct PublicSym32Layout {
94   RecordPrefix Prefix;
95   PublicSym32Header Pub;
96   // char Name[];
97 });
98 }
99 
100 // Calculate how much memory this public needs when serialized.
101 static uint32_t sizeOfPublic(const BulkPublic &Pub) {
102   uint32_t NameLen = Pub.NameLen;
103   NameLen = std::min(NameLen,
104                      uint32_t(MaxRecordLength - sizeof(PublicSym32Layout) - 1));
105   return alignTo(sizeof(PublicSym32Layout) + NameLen + 1, 4);
106 }
107 
108 static CVSymbol serializePublic(uint8_t *Mem, const BulkPublic &Pub) {
109   // Assume the caller has allocated sizeOfPublic bytes.
110   uint32_t NameLen = std::min(
111       Pub.NameLen, uint32_t(MaxRecordLength - sizeof(PublicSym32Layout) - 1));
112   size_t Size = alignTo(sizeof(PublicSym32Layout) + NameLen + 1, 4);
113   assert(Size == sizeOfPublic(Pub));
114   auto *FixedMem = reinterpret_cast<PublicSym32Layout *>(Mem);
115   FixedMem->Prefix.RecordKind = static_cast<uint16_t>(codeview::S_PUB32);
116   FixedMem->Prefix.RecordLen = static_cast<uint16_t>(Size - 2);
117   FixedMem->Pub.Flags = Pub.Flags;
118   FixedMem->Pub.Offset = Pub.Offset;
119   FixedMem->Pub.Segment = Pub.U.Segment;
120   char *NameMem = reinterpret_cast<char *>(FixedMem + 1);
121   memcpy(NameMem, Pub.Name, NameLen);
122   // Zero the null terminator and remaining bytes.
123   memset(&NameMem[NameLen], 0, Size - sizeof(PublicSym32Layout) - NameLen);
124   return CVSymbol(makeArrayRef(reinterpret_cast<uint8_t *>(Mem), Size));
125 }
126 
127 uint32_t GSIHashStreamBuilder::calculateSerializedLength() const {
128   uint32_t Size = sizeof(GSIHashHeader);
129   Size += HashRecords.size() * sizeof(PSHashRecord);
130   Size += HashBitmap.size() * sizeof(uint32_t);
131   Size += HashBuckets.size() * sizeof(uint32_t);
132   return Size;
133 }
134 
135 uint32_t GSIHashStreamBuilder::calculateRecordByteSize() const {
136   uint32_t Size = 0;
137   for (const auto &Sym : Records)
138     Size += Sym.length();
139   return Size;
140 }
141 
142 Error GSIHashStreamBuilder::commit(BinaryStreamWriter &Writer) {
143   GSIHashHeader Header;
144   Header.VerSignature = GSIHashHeader::HdrSignature;
145   Header.VerHdr = GSIHashHeader::HdrVersion;
146   Header.HrSize = HashRecords.size() * sizeof(PSHashRecord);
147   Header.NumBuckets = HashBitmap.size() * 4 + HashBuckets.size() * 4;
148 
149   if (auto EC = Writer.writeObject(Header))
150     return EC;
151 
152   if (auto EC = Writer.writeArray(makeArrayRef(HashRecords)))
153     return EC;
154   if (auto EC = Writer.writeArray(makeArrayRef(HashBitmap)))
155     return EC;
156   if (auto EC = Writer.writeArray(makeArrayRef(HashBuckets)))
157     return EC;
158   return Error::success();
159 }
160 
161 static bool isAsciiString(StringRef S) {
162   return llvm::all_of(S, [](char C) { return unsigned(C) < 0x80; });
163 }
164 
165 // See `caseInsensitiveComparePchPchCchCch` in gsi.cpp
166 static int gsiRecordCmp(StringRef S1, StringRef S2) {
167   size_t LS = S1.size();
168   size_t RS = S2.size();
169   // Shorter strings always compare less than longer strings.
170   if (LS != RS)
171     return LS - RS;
172 
173   // If either string contains non ascii characters, memcmp them.
174   if (LLVM_UNLIKELY(!isAsciiString(S1) || !isAsciiString(S2)))
175     return memcmp(S1.data(), S2.data(), LS);
176 
177   // Both strings are ascii, perform a case-insenstive comparison.
178   return S1.compare_lower(S2.data());
179 }
180 
181 void GSIHashStreamBuilder::finalizeBuckets(uint32_t RecordZeroOffset) {
182   // Build up a list of globals to be bucketed. This repurposes the BulkPublic
183   // struct with different meanings for the fields to avoid reallocating a new
184   // vector during public symbol table hash construction.
185   std::vector<BulkPublic> Globals;
186   Globals.resize(Records.size());
187   uint32_t SymOffset = RecordZeroOffset;
188   for (size_t I = 0, E = Records.size(); I < E; ++I) {
189     StringRef Name = getSymbolName(Records[I]);
190     Globals[I].Name = Name.data();
191     Globals[I].NameLen = Name.size();
192     Globals[I].SymOffset = SymOffset;
193     SymOffset += Records[I].length();
194   }
195 
196   finalizeBuckets(RecordZeroOffset, std::move(Globals));
197 }
198 
199 void GSIHashStreamBuilder::finalizeBuckets(uint32_t RecordZeroOffset,
200                                            std::vector<BulkPublic> &&Globals) {
201   // Hash every name in parallel. The Segment field is no longer needed, so
202   // store the BucketIdx in a union.
203   parallelForEachN(0, Globals.size(), [&](size_t I) {
204     Globals[I].U.BucketIdx = hashStringV1(Globals[I].Name) % IPHR_HASH;
205   });
206 
207   // Parallel sort by bucket index, then name within the buckets. Within the
208   // buckets, sort each bucket by memcmp of the symbol's name.  It's important
209   // that we use the same sorting algorithm as is used by the reference
210   // implementation to ensure that the search for a record within a bucket can
211   // properly early-out when it detects the record won't be found.  The
212   // algorithm used here corredsponds to the function
213   // caseInsensitiveComparePchPchCchCch in the reference implementation.
214   auto BucketCmp = [](const BulkPublic &L, const BulkPublic &R) {
215     if (L.U.BucketIdx != R.U.BucketIdx)
216       return L.U.BucketIdx < R.U.BucketIdx;
217     int Cmp = gsiRecordCmp(L.getName(), R.getName());
218     if (Cmp != 0)
219       return Cmp < 0;
220     // This comparison is necessary to make the sorting stable in the presence
221     // of two static globals with the same name. The easiest way to observe
222     // this is with S_LDATA32 records.
223     return L.SymOffset < R.SymOffset;
224   };
225   parallelSort(Globals, BucketCmp);
226 
227   // Zero out the bucket index bitmap.
228   for (ulittle32_t &Word : HashBitmap)
229     Word = 0;
230 
231   // Compute the three tables: the hash records in bucket and chain order, the
232   // bucket presence bitmap, and the bucket chain start offsets.
233   HashRecords.reserve(Globals.size());
234   uint32_t LastBucketIdx = ~0U;
235   for (const BulkPublic &Global : Globals) {
236     // If this is a new bucket, add it to the bitmap and the start offset map.
237     uint32_t BucketIdx = Global.U.BucketIdx;
238     if (LastBucketIdx != BucketIdx) {
239       HashBitmap[BucketIdx / 32] |= 1U << (BucketIdx % 32);
240 
241       // Calculate what the offset of the first hash record in the chain would
242       // be if it were inflated to contain 32-bit pointers. On a 32-bit system,
243       // each record would be 12 bytes. See HROffsetCalc in gsi.h.
244       const int SizeOfHROffsetCalc = 12;
245       ulittle32_t ChainStartOff =
246           ulittle32_t(HashRecords.size() * SizeOfHROffsetCalc);
247       HashBuckets.push_back(ChainStartOff);
248       LastBucketIdx = BucketIdx;
249     }
250 
251     // Create the hash record. Add one when writing symbol offsets to disk.
252     // See GSI1::fixSymRecs. Always use a refcount of 1 for now.
253     PSHashRecord HRec;
254     HRec.Off = Global.SymOffset + 1;
255     HRec.CRef = 1;
256     HashRecords.push_back(HRec);
257   }
258 }
259 
260 GSIStreamBuilder::GSIStreamBuilder(msf::MSFBuilder &Msf)
261     : Msf(Msf), PSH(std::make_unique<GSIHashStreamBuilder>()),
262       GSH(std::make_unique<GSIHashStreamBuilder>()) {}
263 
264 GSIStreamBuilder::~GSIStreamBuilder() {}
265 
266 uint32_t GSIStreamBuilder::calculatePublicsHashStreamSize() const {
267   uint32_t Size = 0;
268   Size += sizeof(PublicsStreamHeader);
269   Size += PSH->calculateSerializedLength();
270   Size += PubAddrMap.size() * sizeof(uint32_t); // AddrMap
271   // FIXME: Add thunk map and section offsets for incremental linking.
272 
273   return Size;
274 }
275 
276 uint32_t GSIStreamBuilder::calculateGlobalsHashStreamSize() const {
277   return GSH->calculateSerializedLength();
278 }
279 
280 Error GSIStreamBuilder::finalizeMsfLayout() {
281   // First we write public symbol records, then we write global symbol records.
282   uint32_t PublicsSize = PSH->calculateRecordByteSize();
283   uint32_t GlobalsSize = GSH->calculateRecordByteSize();
284   GSH->finalizeBuckets(PublicsSize);
285 
286   Expected<uint32_t> Idx = Msf.addStream(calculateGlobalsHashStreamSize());
287   if (!Idx)
288     return Idx.takeError();
289   GlobalsStreamIndex = *Idx;
290 
291   Idx = Msf.addStream(calculatePublicsHashStreamSize());
292   if (!Idx)
293     return Idx.takeError();
294   PublicsStreamIndex = *Idx;
295 
296   uint32_t RecordBytes = PublicsSize + GlobalsSize;
297 
298   Idx = Msf.addStream(RecordBytes);
299   if (!Idx)
300     return Idx.takeError();
301   RecordStreamIndex = *Idx;
302   return Error::success();
303 }
304 
305 void GSIStreamBuilder::addPublicSymbols(std::vector<BulkPublic> &&Publics) {
306   // Sort the symbols by name. PDBs contain lots of symbols, so use parallelism.
307   parallelSort(Publics, [](const BulkPublic &L, const BulkPublic &R) {
308     return L.getName() < R.getName();
309   });
310 
311   // Assign offsets and allocate one contiguous block of memory for all public
312   // symbols.
313   uint32_t SymOffset = 0;
314   for (BulkPublic &Pub : Publics) {
315     Pub.SymOffset = SymOffset;
316     SymOffset += sizeOfPublic(Pub);
317   }
318   uint8_t *Mem =
319       reinterpret_cast<uint8_t *>(Msf.getAllocator().Allocate(SymOffset, 4));
320 
321   // Instead of storing individual CVSymbol records, store them as one giant
322   // buffer.
323   // FIXME: This is kind of a hack. This makes Records.size() wrong, and we have
324   // to account for that elsewhere.
325   PSH->Records.push_back(CVSymbol(makeArrayRef(Mem, SymOffset)));
326 
327   // Serialize them in parallel.
328   parallelForEachN(0, Publics.size(), [&](size_t I) {
329     const BulkPublic &Pub = Publics[I];
330     serializePublic(Mem + Pub.SymOffset, Pub);
331   });
332 
333   // Re-sort the publics by address so we can build the address map. We no
334   // longer need the original ordering.
335   auto AddrCmp = [](const BulkPublic &L, const BulkPublic &R) {
336     if (L.U.Segment != R.U.Segment)
337       return L.U.Segment < R.U.Segment;
338     if (L.Offset != R.Offset)
339       return L.Offset < R.Offset;
340     // parallelSort is unstable, so we have to do name comparison to ensure
341     // that two names for the same location come out in a determinstic order.
342     return L.getName() < R.getName();
343   };
344   parallelSort(Publics, AddrCmp);
345 
346   // Fill in the symbol offsets in the appropriate order.
347   PubAddrMap.reserve(Publics.size());
348   for (const BulkPublic &Pub : Publics)
349     PubAddrMap.push_back(ulittle32_t(Pub.SymOffset));
350 
351   // Finalize public symbol buckets immediately after they have been added.
352   // They should all be warm in the cache at this point, so go ahead and do it
353   // now.
354   PSH->finalizeBuckets(0, std::move(Publics));
355 }
356 
357 void GSIStreamBuilder::addGlobalSymbol(const ProcRefSym &Sym) {
358   GSH->addSymbol(Sym, Msf);
359 }
360 
361 void GSIStreamBuilder::addGlobalSymbol(const DataSym &Sym) {
362   GSH->addSymbol(Sym, Msf);
363 }
364 
365 void GSIStreamBuilder::addGlobalSymbol(const ConstantSym &Sym) {
366   GSH->addSymbol(Sym, Msf);
367 }
368 
369 void GSIStreamBuilder::addGlobalSymbol(const codeview::CVSymbol &Sym) {
370   GSH->addSymbol(Sym);
371 }
372 
373 static Error writeRecords(BinaryStreamWriter &Writer,
374                           ArrayRef<CVSymbol> Records) {
375   BinaryItemStream<CVSymbol> ItemStream(support::endianness::little);
376   ItemStream.setItems(Records);
377   BinaryStreamRef RecordsRef(ItemStream);
378   return Writer.writeStreamRef(RecordsRef);
379 }
380 
381 Error GSIStreamBuilder::commitSymbolRecordStream(
382     WritableBinaryStreamRef Stream) {
383   BinaryStreamWriter Writer(Stream);
384 
385   // Write public symbol records first, followed by global symbol records.  This
386   // must match the order that we assume in finalizeMsfLayout when computing
387   // PSHZero and GSHZero.
388   if (auto EC = writeRecords(Writer, PSH->Records))
389     return EC;
390   if (auto EC = writeRecords(Writer, GSH->Records))
391     return EC;
392 
393   return Error::success();
394 }
395 
396 Error GSIStreamBuilder::commitPublicsHashStream(
397     WritableBinaryStreamRef Stream) {
398   BinaryStreamWriter Writer(Stream);
399   PublicsStreamHeader Header;
400 
401   // FIXME: Fill these in. They are for incremental linking.
402   Header.SymHash = PSH->calculateSerializedLength();
403   Header.AddrMap = PubAddrMap.size() * 4;
404   Header.NumThunks = 0;
405   Header.SizeOfThunk = 0;
406   Header.ISectThunkTable = 0;
407   memset(Header.Padding, 0, sizeof(Header.Padding));
408   Header.OffThunkTable = 0;
409   Header.NumSections = 0;
410   if (auto EC = Writer.writeObject(Header))
411     return EC;
412 
413   if (auto EC = PSH->commit(Writer))
414     return EC;
415 
416   if (auto EC = Writer.writeArray(makeArrayRef(PubAddrMap)))
417     return EC;
418 
419   return Error::success();
420 }
421 
422 Error GSIStreamBuilder::commitGlobalsHashStream(
423     WritableBinaryStreamRef Stream) {
424   BinaryStreamWriter Writer(Stream);
425   return GSH->commit(Writer);
426 }
427 
428 Error GSIStreamBuilder::commit(const msf::MSFLayout &Layout,
429                                WritableBinaryStreamRef Buffer) {
430   auto GS = WritableMappedBlockStream::createIndexedStream(
431       Layout, Buffer, getGlobalsStreamIndex(), Msf.getAllocator());
432   auto PS = WritableMappedBlockStream::createIndexedStream(
433       Layout, Buffer, getPublicsStreamIndex(), Msf.getAllocator());
434   auto PRS = WritableMappedBlockStream::createIndexedStream(
435       Layout, Buffer, getRecordStreamIndex(), Msf.getAllocator());
436 
437   if (auto EC = commitSymbolRecordStream(*PRS))
438     return EC;
439   if (auto EC = commitGlobalsHashStream(*GS))
440     return EC;
441   if (auto EC = commitPublicsHashStream(*PS))
442     return EC;
443   return Error::success();
444 }
445