1 //===- DbiStreamBuilder.cpp - PDB Dbi Stream Creation -----------*- 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/GSIStreamBuilder.h"
11 
12 #include "llvm/DebugInfo/CodeView/RecordName.h"
13 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"
14 #include "llvm/DebugInfo/CodeView/SymbolRecord.h"
15 #include "llvm/DebugInfo/CodeView/SymbolSerializer.h"
16 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
17 #include "llvm/DebugInfo/MSF/MSFCommon.h"
18 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
19 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
20 #include "llvm/DebugInfo/PDB/Native/Hash.h"
21 #include "llvm/Support/BinaryItemStream.h"
22 #include "llvm/Support/BinaryStreamWriter.h"
23 #include <algorithm>
24 #include <vector>
25 
26 using namespace llvm;
27 using namespace llvm::msf;
28 using namespace llvm::pdb;
29 using namespace llvm::codeview;
30 
31 struct llvm::pdb::GSIHashStreamBuilder {
32   std::vector<CVSymbol> Records;
33   uint32_t StreamIndex;
34   std::vector<PSHashRecord> HashRecords;
35   std::array<support::ulittle32_t, (IPHR_HASH + 32) / 32> HashBitmap;
36   std::vector<support::ulittle32_t> HashBuckets;
37 
38   uint32_t calculateSerializedLength() const;
39   uint32_t calculateRecordByteSize() const;
40   Error commit(BinaryStreamWriter &Writer);
41   void finalizeBuckets(uint32_t RecordZeroOffset);
42 
43   template <typename T> void addSymbol(const T &Symbol, MSFBuilder &Msf) {
44     T Copy(Symbol);
45     Records.push_back(SymbolSerializer::writeOneSymbol(Copy, Msf.getAllocator(),
46                                                        CodeViewContainer::Pdb));
47   }
48   void addSymbol(const CVSymbol &Symbol) { Records.push_back(Symbol); }
49 };
50 
51 uint32_t GSIHashStreamBuilder::calculateSerializedLength() const {
52   uint32_t Size = sizeof(GSIHashHeader);
53   Size += HashRecords.size() * sizeof(PSHashRecord);
54   Size += HashBitmap.size() * sizeof(uint32_t);
55   Size += HashBuckets.size() * sizeof(uint32_t);
56   return Size;
57 }
58 
59 uint32_t GSIHashStreamBuilder::calculateRecordByteSize() const {
60   uint32_t Size = 0;
61   for (const auto &Sym : Records)
62     Size += Sym.length();
63   return Size;
64 }
65 
66 Error GSIHashStreamBuilder::commit(BinaryStreamWriter &Writer) {
67   GSIHashHeader Header;
68   Header.VerSignature = GSIHashHeader::HdrSignature;
69   Header.VerHdr = GSIHashHeader::HdrVersion;
70   Header.HrSize = HashRecords.size() * sizeof(PSHashRecord);
71   Header.NumBuckets = HashBitmap.size() * 4 + HashBuckets.size() * 4;
72 
73   if (auto EC = Writer.writeObject(Header))
74     return EC;
75 
76   if (auto EC = Writer.writeArray(makeArrayRef(HashRecords)))
77     return EC;
78   if (auto EC = Writer.writeArray(makeArrayRef(HashBitmap)))
79     return EC;
80   if (auto EC = Writer.writeArray(makeArrayRef(HashBuckets)))
81     return EC;
82   return Error::success();
83 }
84 
85 void GSIHashStreamBuilder::finalizeBuckets(uint32_t RecordZeroOffset) {
86   std::array<std::vector<PSHashRecord>, IPHR_HASH + 1> TmpBuckets;
87   uint32_t SymOffset = RecordZeroOffset;
88   for (const CVSymbol &Sym : Records) {
89     PSHashRecord HR;
90     // Add one when writing symbol offsets to disk. See GSI1::fixSymRecs.
91     HR.Off = SymOffset + 1;
92     HR.CRef = 1; // Always use a refcount of 1.
93 
94     // Hash the name to figure out which bucket this goes into.
95     StringRef Name = getSymbolName(Sym);
96     size_t BucketIdx = hashStringV1(Name) % IPHR_HASH;
97     TmpBuckets[BucketIdx].push_back(HR); // FIXME: Does order matter?
98 
99     SymOffset += Sym.length();
100   }
101 
102   // Compute the three tables: the hash records in bucket and chain order, the
103   // bucket presence bitmap, and the bucket chain start offsets.
104   HashRecords.reserve(Records.size());
105   for (ulittle32_t &Word : HashBitmap)
106     Word = 0;
107   for (size_t BucketIdx = 0; BucketIdx < IPHR_HASH + 1; ++BucketIdx) {
108     auto &Bucket = TmpBuckets[BucketIdx];
109     if (Bucket.empty())
110       continue;
111     HashBitmap[BucketIdx / 32] |= 1U << (BucketIdx % 32);
112 
113     // Calculate what the offset of the first hash record in the chain would
114     // be if it were inflated to contain 32-bit pointers. On a 32-bit system,
115     // each record would be 12 bytes. See HROffsetCalc in gsi.h.
116     const int SizeOfHROffsetCalc = 12;
117     ulittle32_t ChainStartOff =
118         ulittle32_t(HashRecords.size() * SizeOfHROffsetCalc);
119     HashBuckets.push_back(ChainStartOff);
120     for (const auto &HR : Bucket)
121       HashRecords.push_back(HR);
122   }
123 }
124 
125 GSIStreamBuilder::GSIStreamBuilder(msf::MSFBuilder &Msf)
126     : Msf(Msf), PSH(llvm::make_unique<GSIHashStreamBuilder>()),
127       GSH(llvm::make_unique<GSIHashStreamBuilder>()) {}
128 
129 GSIStreamBuilder::~GSIStreamBuilder() {}
130 
131 uint32_t GSIStreamBuilder::calculatePublicsHashStreamSize() const {
132   uint32_t Size = 0;
133   Size += sizeof(PublicsStreamHeader);
134   Size += PSH->calculateSerializedLength();
135   Size += PSH->Records.size() * sizeof(uint32_t); // AddrMap
136   // FIXME: Add thunk map and section offsets for incremental linking.
137 
138   return Size;
139 }
140 
141 uint32_t GSIStreamBuilder::calculateGlobalsHashStreamSize() const {
142   return GSH->calculateSerializedLength();
143 }
144 
145 Error GSIStreamBuilder::finalizeMsfLayout() {
146   // First we write public symbol records, then we write global symbol records.
147   uint32_t PSHZero = 0;
148   uint32_t GSHZero = PSH->calculateRecordByteSize();
149 
150   PSH->finalizeBuckets(PSHZero);
151   GSH->finalizeBuckets(GSHZero);
152 
153   Expected<uint32_t> Idx = Msf.addStream(calculateGlobalsHashStreamSize());
154   if (!Idx)
155     return Idx.takeError();
156   GSH->StreamIndex = *Idx;
157   Idx = Msf.addStream(calculatePublicsHashStreamSize());
158   if (!Idx)
159     return Idx.takeError();
160   PSH->StreamIndex = *Idx;
161 
162   uint32_t RecordBytes =
163       GSH->calculateRecordByteSize() + PSH->calculateRecordByteSize();
164 
165   Idx = Msf.addStream(RecordBytes);
166   if (!Idx)
167     return Idx.takeError();
168   RecordStreamIdx = *Idx;
169   return Error::success();
170 }
171 
172 static bool comparePubSymByAddrAndName(
173     const std::pair<const CVSymbol *, const PublicSym32 *> &LS,
174     const std::pair<const CVSymbol *, const PublicSym32 *> &RS) {
175   if (LS.second->Segment != RS.second->Segment)
176     return LS.second->Segment < RS.second->Segment;
177   if (LS.second->Offset != RS.second->Offset)
178     return LS.second->Offset < RS.second->Offset;
179 
180   return LS.second->Name < RS.second->Name;
181 }
182 
183 /// Compute the address map. The address map is an array of symbol offsets
184 /// sorted so that it can be binary searched by address.
185 static std::vector<ulittle32_t> computeAddrMap(ArrayRef<CVSymbol> Records) {
186   // Make a vector of pointers to the symbols so we can sort it by address.
187   // Also gather the symbol offsets while we're at it.
188 
189   std::vector<PublicSym32> DeserializedPublics;
190   std::vector<std::pair<const CVSymbol *, const PublicSym32 *>> PublicsByAddr;
191   std::vector<uint32_t> SymOffsets;
192   DeserializedPublics.reserve(Records.size());
193   PublicsByAddr.reserve(Records.size());
194   SymOffsets.reserve(Records.size());
195 
196   uint32_t SymOffset = 0;
197   for (const CVSymbol &Sym : Records) {
198     assert(Sym.kind() == SymbolKind::S_PUB32);
199     DeserializedPublics.push_back(
200         cantFail(SymbolDeserializer::deserializeAs<PublicSym32>(Sym)));
201     PublicsByAddr.emplace_back(&Sym, &DeserializedPublics.back());
202     SymOffsets.push_back(SymOffset);
203     SymOffset += Sym.length();
204   }
205   std::stable_sort(PublicsByAddr.begin(), PublicsByAddr.end(),
206                    comparePubSymByAddrAndName);
207 
208   // Fill in the symbol offsets in the appropriate order.
209   std::vector<ulittle32_t> AddrMap;
210   AddrMap.reserve(Records.size());
211   for (auto &Sym : PublicsByAddr) {
212     ptrdiff_t Idx = std::distance(Records.data(), Sym.first);
213     assert(Idx >= 0 && size_t(Idx) < Records.size());
214     AddrMap.push_back(ulittle32_t(SymOffsets[Idx]));
215   }
216   return AddrMap;
217 }
218 
219 uint32_t GSIStreamBuilder::getPublicsStreamIndex() const {
220   return PSH->StreamIndex;
221 }
222 
223 uint32_t GSIStreamBuilder::getGlobalsStreamIndex() const {
224   return GSH->StreamIndex;
225 }
226 
227 void GSIStreamBuilder::addPublicSymbol(const PublicSym32 &Pub) {
228   PSH->addSymbol(Pub, Msf);
229 }
230 
231 void GSIStreamBuilder::addGlobalSymbol(const ProcRefSym &Sym) {
232   GSH->addSymbol(Sym, Msf);
233 }
234 
235 void GSIStreamBuilder::addGlobalSymbol(const DataSym &Sym) {
236   GSH->addSymbol(Sym, Msf);
237 }
238 
239 void GSIStreamBuilder::addGlobalSymbol(const ConstantSym &Sym) {
240   GSH->addSymbol(Sym, Msf);
241 }
242 
243 void GSIStreamBuilder::addGlobalSymbol(const UDTSym &Sym) {
244   GSH->addSymbol(Sym, Msf);
245 }
246 
247 void GSIStreamBuilder::addGlobalSymbol(const codeview::CVSymbol &Sym) {
248   GSH->addSymbol(Sym);
249 }
250 
251 static Error writeRecords(BinaryStreamWriter &Writer,
252                           ArrayRef<CVSymbol> Records) {
253   BinaryItemStream<CVSymbol> ItemStream(support::endianness::little);
254   ItemStream.setItems(Records);
255   BinaryStreamRef RecordsRef(ItemStream);
256   return Writer.writeStreamRef(RecordsRef);
257 }
258 
259 Error GSIStreamBuilder::commitSymbolRecordStream(
260     WritableBinaryStreamRef Stream) {
261   BinaryStreamWriter Writer(Stream);
262 
263   // Write public symbol records first, followed by global symbol records.  This
264   // must match the order that we assume in finalizeMsfLayout when computing
265   // PSHZero and GSHZero.
266   if (auto EC = writeRecords(Writer, PSH->Records))
267     return EC;
268   if (auto EC = writeRecords(Writer, GSH->Records))
269     return EC;
270 
271   return Error::success();
272 }
273 
274 Error GSIStreamBuilder::commitPublicsHashStream(
275     WritableBinaryStreamRef Stream) {
276   BinaryStreamWriter Writer(Stream);
277   PublicsStreamHeader Header;
278 
279   // FIXME: Fill these in. They are for incremental linking.
280   Header.NumThunks = 0;
281   Header.SizeOfThunk = 0;
282   Header.ISectThunkTable = 0;
283   Header.OffThunkTable = 0;
284   Header.NumSections = 0;
285   Header.SymHash = PSH->calculateSerializedLength();
286   Header.AddrMap = PSH->Records.size() * 4;
287   if (auto EC = Writer.writeObject(Header))
288     return EC;
289 
290   if (auto EC = PSH->commit(Writer))
291     return EC;
292 
293   std::vector<ulittle32_t> AddrMap = computeAddrMap(PSH->Records);
294   if (auto EC = Writer.writeArray(makeArrayRef(AddrMap)))
295     return EC;
296 
297   return Error::success();
298 }
299 
300 Error GSIStreamBuilder::commitGlobalsHashStream(
301     WritableBinaryStreamRef Stream) {
302   BinaryStreamWriter Writer(Stream);
303   return GSH->commit(Writer);
304 }
305 
306 Error GSIStreamBuilder::commit(const msf::MSFLayout &Layout,
307                                WritableBinaryStreamRef Buffer) {
308   auto GS = WritableMappedBlockStream::createIndexedStream(
309       Layout, Buffer, getGlobalsStreamIndex(), Msf.getAllocator());
310   auto PS = WritableMappedBlockStream::createIndexedStream(
311       Layout, Buffer, getPublicsStreamIndex(), Msf.getAllocator());
312   auto PRS = WritableMappedBlockStream::createIndexedStream(
313       Layout, Buffer, getRecordStreamIdx(), Msf.getAllocator());
314 
315   if (auto EC = commitSymbolRecordStream(*PRS))
316     return EC;
317   if (auto EC = commitGlobalsHashStream(*GS))
318     return EC;
319   if (auto EC = commitPublicsHashStream(*PS))
320     return EC;
321   return Error::success();
322 }
323