contrib/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp

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