[PDB] Defer public serialization until PDB writing
[lldb.git] / llvm / lib / DebugInfo / PDB / Native / GSIStreamBuilder.cpp
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 #include "llvm/DebugInfo/CodeView/RecordName.h"
17 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"
18 #include "llvm/DebugInfo/CodeView/SymbolRecord.h"
19 #include "llvm/DebugInfo/CodeView/SymbolSerializer.h"
20 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
21 #include "llvm/DebugInfo/MSF/MSFCommon.h"
22 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
23 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
24 #include "llvm/DebugInfo/PDB/Native/Hash.h"
25 #include "llvm/Support/BinaryItemStream.h"
26 #include "llvm/Support/BinaryStreamWriter.h"
27 #include "llvm/Support/Parallel.h"
28 #include "llvm/Support/xxhash.h"
29 #include <algorithm>
30 #include <vector>
31
32 using namespace llvm;
33 using namespace llvm::msf;
34 using namespace llvm::pdb;
35 using namespace llvm::codeview;
36
37 // Helper class for building the public and global PDB hash table buckets.
38 struct llvm::pdb::GSIHashStreamBuilder {
39   // Sum of the size of all public or global records.
40   uint32_t RecordByteSize = 0;
41
42   std::vector<PSHashRecord> HashRecords;
43
44   // The hash bitmap has `ceil((IPHR_HASH + 1) / 32)` words in it. The
45   // reference implementation builds a hash table with IPHR_HASH buckets in it.
46   // The last bucket is used to link together free hash table cells in a linked
47   // list, but it is always empty in the compressed, on-disk format. However,
48   // the bitmap must have a bit for it.
49   std::array<support::ulittle32_t, (IPHR_HASH + 32) / 32> HashBitmap;
50
51   std::vector<support::ulittle32_t> HashBuckets;
52
53   uint32_t calculateSerializedLength() const;
54   Error commit(BinaryStreamWriter &Writer);
55
56   void finalizePublicBuckets();
57   void finalizeGlobalBuckets(uint32_t RecordZeroOffset);
58
59   // Assign public and global symbol records into hash table buckets.
60   // Modifies the list of records to store the bucket index, but does not
61   // change the order.
62   void finalizeBuckets(uint32_t RecordZeroOffset,
63                        MutableArrayRef<BulkPublic> Globals);
64 };
65
66 // DenseMapInfo implementation for deduplicating symbol records.
67 struct llvm::pdb::SymbolDenseMapInfo {
68   static inline CVSymbol getEmptyKey() {
69     static CVSymbol Empty;
70     return Empty;
71   }
72   static inline CVSymbol getTombstoneKey() {
73     static CVSymbol Tombstone(
74         DenseMapInfo<ArrayRef<uint8_t>>::getTombstoneKey());
75     return Tombstone;
76   }
77   static unsigned getHashValue(const CVSymbol &Val) {
78     return xxHash64(Val.RecordData);
79   }
80   static bool isEqual(const CVSymbol &LHS, const CVSymbol &RHS) {
81     return LHS.RecordData == RHS.RecordData;
82   }
83 };
84
85 namespace {
86 LLVM_PACKED_START
87 struct PublicSym32Layout {
88   RecordPrefix Prefix;
89   PublicSym32Header Pub;
90   // char Name[];
91 };
92 LLVM_PACKED_END
93 } // namespace
94
95 // Calculate how much memory this public needs when serialized.
96 static uint32_t sizeOfPublic(const BulkPublic &Pub) {
97   uint32_t NameLen = Pub.NameLen;
98   NameLen = std::min(NameLen,
99                      uint32_t(MaxRecordLength - sizeof(PublicSym32Layout) - 1));
100   return alignTo(sizeof(PublicSym32Layout) + NameLen + 1, 4);
101 }
102
103 static CVSymbol serializePublic(uint8_t *Mem, const BulkPublic &Pub) {
104   // Assume the caller has allocated sizeOfPublic bytes.
105   uint32_t NameLen = std::min(
106       Pub.NameLen, uint32_t(MaxRecordLength - sizeof(PublicSym32Layout) - 1));
107   size_t Size = alignTo(sizeof(PublicSym32Layout) + NameLen + 1, 4);
108   assert(Size == sizeOfPublic(Pub));
109   auto *FixedMem = reinterpret_cast<PublicSym32Layout *>(Mem);
110   FixedMem->Prefix.RecordKind = static_cast<uint16_t>(codeview::S_PUB32);
111   FixedMem->Prefix.RecordLen = static_cast<uint16_t>(Size - 2);
112   FixedMem->Pub.Flags = Pub.Flags;
113   FixedMem->Pub.Offset = Pub.Offset;
114   FixedMem->Pub.Segment = Pub.Segment;
115   char *NameMem = reinterpret_cast<char *>(FixedMem + 1);
116   memcpy(NameMem, Pub.Name, NameLen);
117   // Zero the null terminator and remaining bytes.
118   memset(&NameMem[NameLen], 0, Size - sizeof(PublicSym32Layout) - NameLen);
119   return CVSymbol(makeArrayRef(reinterpret_cast<uint8_t *>(Mem), Size));
120 }
121
122 uint32_t GSIHashStreamBuilder::calculateSerializedLength() const {
123   uint32_t Size = sizeof(GSIHashHeader);
124   Size += HashRecords.size() * sizeof(PSHashRecord);
125   Size += HashBitmap.size() * sizeof(uint32_t);
126   Size += HashBuckets.size() * sizeof(uint32_t);
127   return Size;
128 }
129
130 Error GSIHashStreamBuilder::commit(BinaryStreamWriter &Writer) {
131   GSIHashHeader Header;
132   Header.VerSignature = GSIHashHeader::HdrSignature;
133   Header.VerHdr = GSIHashHeader::HdrVersion;
134   Header.HrSize = HashRecords.size() * sizeof(PSHashRecord);
135   Header.NumBuckets = HashBitmap.size() * 4 + HashBuckets.size() * 4;
136
137   if (auto EC = Writer.writeObject(Header))
138     return EC;
139
140   if (auto EC = Writer.writeArray(makeArrayRef(HashRecords)))
141     return EC;
142   if (auto EC = Writer.writeArray(makeArrayRef(HashBitmap)))
143     return EC;
144   if (auto EC = Writer.writeArray(makeArrayRef(HashBuckets)))
145     return EC;
146   return Error::success();
147 }
148
149 static bool isAsciiString(StringRef S) {
150   return llvm::all_of(S, [](char C) { return unsigned(C) < 0x80; });
151 }
152
153 // See `caseInsensitiveComparePchPchCchCch` in gsi.cpp
154 static int gsiRecordCmp(StringRef S1, StringRef S2) {
155   size_t LS = S1.size();
156   size_t RS = S2.size();
157   // Shorter strings always compare less than longer strings.
158   if (LS != RS)
159     return LS - RS;
160
161   // If either string contains non ascii characters, memcmp them.
162   if (LLVM_UNLIKELY(!isAsciiString(S1) || !isAsciiString(S2)))
163     return memcmp(S1.data(), S2.data(), LS);
164
165   // Both strings are ascii, perform a case-insenstive comparison.
166   return S1.compare_lower(S2.data());
167 }
168
169 void GSIStreamBuilder::finalizePublicBuckets() {
170   PSH->finalizeBuckets(0, Publics);
171 }
172
173 void GSIStreamBuilder::finalizeGlobalBuckets(uint32_t RecordZeroOffset) {
174   // Build up a list of globals to be bucketed. Use the BulkPublic data
175   // structure for this purpose, even though these are global records, not
176   // public records. Most of the same fields are required:
177   // - Name
178   // - NameLen
179   // - SymOffset
180   // - BucketIdx
181   // The dead fields are Offset, Segment, and Flags.
182   std::vector<BulkPublic> Records;
183   Records.resize(Globals.size());
184   uint32_t SymOffset = RecordZeroOffset;
185   for (size_t I = 0, E = Globals.size(); I < E; ++I) {
186     StringRef Name = getSymbolName(Globals[I]);
187     Records[I].Name = Name.data();
188     Records[I].NameLen = Name.size();
189     Records[I].SymOffset = SymOffset;
190     SymOffset += Globals[I].length();
191   }
192
193   GSH->finalizeBuckets(RecordZeroOffset, Records);
194 }
195
196 void GSIHashStreamBuilder::finalizeBuckets(
197     uint32_t RecordZeroOffset, MutableArrayRef<BulkPublic> Records) {
198   // Hash every name in parallel.
199   parallelForEachN(0, Records.size(), [&](size_t I) {
200     Records[I].setBucketIdx(hashStringV1(Records[I].Name) % IPHR_HASH);
201   });
202
203   // Count up the size of each bucket. Then, use an exclusive prefix sum to
204   // calculate the bucket start offsets. This is C++17 std::exclusive_scan, but
205   // we can't use it yet.
206   uint32_t BucketStarts[IPHR_HASH] = {0};
207   for (const BulkPublic &P : Records)
208     ++BucketStarts[P.BucketIdx];
209   uint32_t Sum = 0;
210   for (uint32_t &B : BucketStarts) {
211     uint32_t Size = B;
212     B = Sum;
213     Sum += Size;
214   }
215
216   // Place globals into the hash table in bucket order. When placing a global,
217   // update the bucket start. Every hash table slot should be filled. Always use
218   // a refcount of one for now.
219   HashRecords.resize(Records.size());
220   uint32_t BucketCursors[IPHR_HASH];
221   memcpy(BucketCursors, BucketStarts, sizeof(BucketCursors));
222   for (int I = 0, E = Records.size(); I < E; ++I) {
223     uint32_t HashIdx = BucketCursors[Records[I].BucketIdx]++;
224     HashRecords[HashIdx].Off = I;
225     HashRecords[HashIdx].CRef = 1;
226   }
227
228   // Within the buckets, sort each bucket by memcmp of the symbol's name.  It's
229   // important that we use the same sorting algorithm as is used by the
230   // reference implementation to ensure that the search for a record within a
231   // bucket can properly early-out when it detects the record won't be found.
232   // The algorithm used here corresponds to the function
233   // caseInsensitiveComparePchPchCchCch in the reference implementation.
234   parallelForEachN(0, IPHR_HASH, [&](size_t I) {
235     auto B = &HashRecords[BucketStarts[I]];
236     auto E = &HashRecords[BucketCursors[I]];
237     auto BucketCmp = [Records](const PSHashRecord &LHash,
238                                const PSHashRecord &RHash) {
239       const BulkPublic &L = Records[uint32_t(LHash.Off)];
240       const BulkPublic &R = Records[uint32_t(RHash.Off)];
241       assert(L.BucketIdx == R.BucketIdx);
242       int Cmp = gsiRecordCmp(L.getName(), R.getName());
243       if (Cmp != 0)
244         return Cmp < 0;
245       // This comparison is necessary to make the sorting stable in the presence
246       // of two static globals with the same name. The easiest way to observe
247       // this is with S_LDATA32 records.
248       return L.SymOffset < R.SymOffset;
249     };
250     llvm::sort(B, E, BucketCmp);
251
252     // After we are done sorting, replace the global indices with the stream
253     // offsets of each global. Add one when writing symbol offsets to disk.
254     // See GSI1::fixSymRecs.
255     for (PSHashRecord &HRec : make_range(B, E))
256       HRec.Off = Records[uint32_t(HRec.Off)].SymOffset + 1;
257   });
258
259   // For each non-empty bucket, push the bucket start offset into HashBuckets
260   // and set a bit in the hash bitmap.
261   for (uint32_t I = 0; I < HashBitmap.size(); ++I) {
262     uint32_t Word = 0;
263     for (uint32_t J = 0; J < 32; ++J) {
264       // Skip empty buckets.
265       uint32_t BucketIdx = I * 32 + J;
266       if (BucketIdx >= IPHR_HASH ||
267           BucketStarts[BucketIdx] == BucketCursors[BucketIdx])
268         continue;
269       Word |= (1U << J);
270
271       // Calculate what the offset of the first hash record in the chain would
272       // be if it were inflated to contain 32-bit pointers. On a 32-bit system,
273       // each record would be 12 bytes. See HROffsetCalc in gsi.h.
274       const int SizeOfHROffsetCalc = 12;
275       ulittle32_t ChainStartOff =
276           ulittle32_t(BucketStarts[BucketIdx] * SizeOfHROffsetCalc);
277       HashBuckets.push_back(ChainStartOff);
278     }
279     HashBitmap[I] = Word;
280   }
281 }
282
283 GSIStreamBuilder::GSIStreamBuilder(msf::MSFBuilder &Msf)
284     : Msf(Msf), PSH(std::make_unique<GSIHashStreamBuilder>()),
285       GSH(std::make_unique<GSIHashStreamBuilder>()) {}
286
287 GSIStreamBuilder::~GSIStreamBuilder() {}
288
289 uint32_t GSIStreamBuilder::calculatePublicsHashStreamSize() const {
290   uint32_t Size = 0;
291   Size += sizeof(PublicsStreamHeader);
292   Size += PSH->calculateSerializedLength();
293   Size += Publics.size() * sizeof(uint32_t); // AddrMap
294   // FIXME: Add thunk map and section offsets for incremental linking.
295
296   return Size;
297 }
298
299 uint32_t GSIStreamBuilder::calculateGlobalsHashStreamSize() const {
300   return GSH->calculateSerializedLength();
301 }
302
303 Error GSIStreamBuilder::finalizeMsfLayout() {
304   // First we write public symbol records, then we write global symbol records.
305   finalizePublicBuckets();
306   finalizeGlobalBuckets(PSH->RecordByteSize);
307
308   Expected<uint32_t> Idx = Msf.addStream(calculateGlobalsHashStreamSize());
309   if (!Idx)
310     return Idx.takeError();
311   GlobalsStreamIndex = *Idx;
312
313   Idx = Msf.addStream(calculatePublicsHashStreamSize());
314   if (!Idx)
315     return Idx.takeError();
316   PublicsStreamIndex = *Idx;
317
318   uint32_t RecordBytes = PSH->RecordByteSize + GSH->RecordByteSize;
319
320   Idx = Msf.addStream(RecordBytes);
321   if (!Idx)
322     return Idx.takeError();
323   RecordStreamIndex = *Idx;
324   return Error::success();
325 }
326
327 void GSIStreamBuilder::addPublicSymbols(std::vector<BulkPublic> &&PublicsIn) {
328   assert(Publics.empty() && PSH->RecordByteSize == 0 &&
329          "publics can only be added once");
330   Publics = std::move(PublicsIn);
331
332   // Sort the symbols by name. PDBs contain lots of symbols, so use parallelism.
333   parallelSort(Publics, [](const BulkPublic &L, const BulkPublic &R) {
334     return L.getName() < R.getName();
335   });
336
337   // Assign offsets and calculate the length of the public symbol records.
338   uint32_t SymOffset = 0;
339   for (BulkPublic &Pub : Publics) {
340     Pub.SymOffset = SymOffset;
341     SymOffset += sizeOfPublic(Pub);
342   }
343
344   // Remember the length of the public stream records.
345   PSH->RecordByteSize = SymOffset;
346 }
347
348 void GSIStreamBuilder::addGlobalSymbol(const ProcRefSym &Sym) {
349   serializeAndAddGlobal(Sym);
350 }
351
352 void GSIStreamBuilder::addGlobalSymbol(const DataSym &Sym) {
353   serializeAndAddGlobal(Sym);
354 }
355
356 void GSIStreamBuilder::addGlobalSymbol(const ConstantSym &Sym) {
357   serializeAndAddGlobal(Sym);
358 }
359
360 template <typename T>
361 void GSIStreamBuilder::serializeAndAddGlobal(const T &Symbol) {
362   T Copy(Symbol);
363   addGlobalSymbol(SymbolSerializer::writeOneSymbol(Copy, Msf.getAllocator(),
364                                                    CodeViewContainer::Pdb));
365 }
366
367 void GSIStreamBuilder::addGlobalSymbol(const codeview::CVSymbol &Symbol) {
368   // Ignore duplicate typedefs and constants.
369   if (Symbol.kind() == S_UDT || Symbol.kind() == S_CONSTANT) {
370     auto Iter = GlobalsSeen.insert(Symbol);
371     if (!Iter.second)
372       return;
373   }
374   GSH->RecordByteSize += Symbol.length();
375   Globals.push_back(Symbol);
376 }
377
378 // Serialize each public and write it.
379 static Error writePublics(BinaryStreamWriter &Writer,
380                           ArrayRef<BulkPublic> Publics) {
381   std::vector<uint8_t> Storage;
382   for (const BulkPublic &Pub : Publics) {
383     Storage.resize(sizeOfPublic(Pub));
384     serializePublic(Storage.data(), Pub);
385     if (Error E = Writer.writeBytes(Storage))
386       return E;
387   }
388   return Error::success();
389 }
390
391 static Error writeRecords(BinaryStreamWriter &Writer,
392                           ArrayRef<CVSymbol> Records) {
393   BinaryItemStream<CVSymbol> ItemStream(support::endianness::little);
394   ItemStream.setItems(Records);
395   BinaryStreamRef RecordsRef(ItemStream);
396   return Writer.writeStreamRef(RecordsRef);
397 }
398
399 Error GSIStreamBuilder::commitSymbolRecordStream(
400     WritableBinaryStreamRef Stream) {
401   BinaryStreamWriter Writer(Stream);
402
403   // Write public symbol records first, followed by global symbol records.  This
404   // must match the order that we assume in finalizeMsfLayout when computing
405   // PSHZero and GSHZero.
406   if (auto EC = writePublics(Writer, Publics))
407     return EC;
408   if (auto EC = writeRecords(Writer, Globals))
409     return EC;
410
411   return Error::success();
412 }
413
414 static std::vector<support::ulittle32_t>
415 computeAddrMap(ArrayRef<BulkPublic> Publics) {
416   // Build a parallel vector of indices into the Publics vector, and sort it by
417   // address.
418   std::vector<ulittle32_t> PubAddrMap;
419   PubAddrMap.reserve(Publics.size());
420   for (int I = 0, E = Publics.size(); I < E; ++I)
421     PubAddrMap.push_back(ulittle32_t(I));
422
423   auto AddrCmp = [Publics](const ulittle32_t &LIdx, const ulittle32_t &RIdx) {
424     const BulkPublic &L = Publics[LIdx];
425     const BulkPublic &R = Publics[RIdx];
426     if (L.Segment != R.Segment)
427       return L.Segment < R.Segment;
428     if (L.Offset != R.Offset)
429       return L.Offset < R.Offset;
430     // parallelSort is unstable, so we have to do name comparison to ensure
431     // that two names for the same location come out in a deterministic order.
432     return L.getName() < R.getName();
433   };
434   parallelSort(PubAddrMap, AddrCmp);
435
436   // Rewrite the public symbol indices into symbol offsets.
437   for (ulittle32_t &Entry : PubAddrMap)
438     Entry = Publics[Entry].SymOffset;
439   return PubAddrMap;
440 }
441
442 Error GSIStreamBuilder::commitPublicsHashStream(
443     WritableBinaryStreamRef Stream) {
444   BinaryStreamWriter Writer(Stream);
445   PublicsStreamHeader Header;
446
447   // FIXME: Fill these in. They are for incremental linking.
448   Header.SymHash = PSH->calculateSerializedLength();
449   Header.AddrMap = Publics.size() * 4;
450   Header.NumThunks = 0;
451   Header.SizeOfThunk = 0;
452   Header.ISectThunkTable = 0;
453   memset(Header.Padding, 0, sizeof(Header.Padding));
454   Header.OffThunkTable = 0;
455   Header.NumSections = 0;
456   if (auto EC = Writer.writeObject(Header))
457     return EC;
458
459   if (auto EC = PSH->commit(Writer))
460     return EC;
461
462   std::vector<support::ulittle32_t> PubAddrMap = computeAddrMap(Publics);
463   assert(PubAddrMap.size() == Publics.size());
464   if (auto EC = Writer.writeArray(makeArrayRef(PubAddrMap)))
465     return EC;
466
467   return Error::success();
468 }
469
470 Error GSIStreamBuilder::commitGlobalsHashStream(
471     WritableBinaryStreamRef Stream) {
472   BinaryStreamWriter Writer(Stream);
473   return GSH->commit(Writer);
474 }
475
476 Error GSIStreamBuilder::commit(const msf::MSFLayout &Layout,
477                                WritableBinaryStreamRef Buffer) {
478   auto GS = WritableMappedBlockStream::createIndexedStream(
479       Layout, Buffer, getGlobalsStreamIndex(), Msf.getAllocator());
480   auto PS = WritableMappedBlockStream::createIndexedStream(
481       Layout, Buffer, getPublicsStreamIndex(), Msf.getAllocator());
482   auto PRS = WritableMappedBlockStream::createIndexedStream(
483       Layout, Buffer, getRecordStreamIndex(), Msf.getAllocator());
484
485   if (auto EC = commitSymbolRecordStream(*PRS))
486     return EC;
487   if (auto EC = commitGlobalsHashStream(*GS))
488     return EC;
489   if (auto EC = commitPublicsHashStream(*PS))
490     return EC;
491   return Error::success();
492 }