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

   1 //===- PDBStringTableBuilder.cpp - PDB String Table -------------*- 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/PDBStringTableBuilder.h"
  11
  12 #include "llvm/ADT/ArrayRef.h"
  13 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
  14 #include "llvm/DebugInfo/PDB/Native/Hash.h"
  15 #include "llvm/DebugInfo/PDB/Native/PDBFileBuilder.h"
  16 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
  17 #include "llvm/Support/BinaryStreamWriter.h"
  18 #include "llvm/Support/Endian.h"
  19
  20 using namespace llvm;
  21 using namespace llvm::msf;
  22 using namespace llvm::support;
  23 using namespace llvm::support::endian;
  24 using namespace llvm::pdb;
  25
  26 uint32_t PDBStringTableBuilder::insert(StringRef S) {
  27   return Strings.insert(S);
  28 }
  29
  30 static uint32_t computeBucketCount(uint32_t NumStrings) {
  31   // The /names stream is basically an on-disk open-addressing hash table.
  32   // Hash collisions are resolved by linear probing. We cannot make
  33   // utilization 100% because it will make the linear probing extremely
  34   // slow. But lower utilization wastes disk space. As a reasonable
  35   // load factor, we choose 80%. We need +1 because slot 0 is reserved.
  36   return (NumStrings + 1) * 1.25;
  37 }
  38
  39 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
  40   uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
  41   Size += sizeof(uint32_t) * computeBucketCount(Strings.size());
  42
  43   return Size;
  44 }
  45
  46 uint32_t PDBStringTableBuilder::calculateSerializedSize() const {
  47   uint32_t Size = 0;
  48   Size += sizeof(PDBStringTableHeader);
  49   Size += Strings.calculateSerializedSize();
  50   Size += calculateHashTableSize();
  51   Size += sizeof(uint32_t); // The /names stream ends with the string count.
  52   return Size;
  53 }
  54
  55 void PDBStringTableBuilder::setStrings(
  56     const codeview::DebugStringTableSubsection &Strings) {
  57   this->Strings = Strings;
  58 }
  59
  60 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
  61   // Write a header
  62   PDBStringTableHeader H;
  63   H.Signature = PDBStringTableSignature;
  64   H.HashVersion = 1;
  65   H.ByteSize = Strings.calculateSerializedSize();
  66   if (auto EC = Writer.writeObject(H))
  67     return EC;
  68   assert(Writer.bytesRemaining() == 0);
  69   return Error::success();
  70 }
  71
  72 Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
  73   if (auto EC = Strings.commit(Writer))
  74     return EC;
  75
  76   assert(Writer.bytesRemaining() == 0);
  77   return Error::success();
  78 }
  79
  80 Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
  81   // Write a hash table.
  82   uint32_t BucketCount = computeBucketCount(Strings.size());
  83   if (auto EC = Writer.writeInteger(BucketCount))
  84     return EC;
  85   std::vector<ulittle32_t> Buckets(BucketCount);
  86
  87   for (auto &Pair : Strings) {
  88     StringRef S = Pair.getKey();
  89     uint32_t Offset = Pair.getValue();
  90     uint32_t Hash = hashStringV1(S);
  91
  92     for (uint32_t I = 0; I != BucketCount; ++I) {
  93       uint32_t Slot = (Hash + I) % BucketCount;
  94       if (Slot == 0)
  95         continue; // Skip reserved slot
  96       if (Buckets[Slot] != 0)
  97         continue;
  98       Buckets[Slot] = Offset;
  99       break;
 100     }
 101   }
 102
 103   if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
 104     return EC;
 105
 106   assert(Writer.bytesRemaining() == 0);
 107   return Error::success();
 108 }
 109
 110 Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
 111   if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
 112     return EC;
 113   assert(Writer.bytesRemaining() == 0);
 114   return Error::success();
 115 }
 116
 117 Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
 118   BinaryStreamWriter SectionWriter;
 119
 120   std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
 121   if (auto EC = writeHeader(SectionWriter))
 122     return EC;
 123
 124   std::tie(SectionWriter, Writer) =
 125       Writer.split(Strings.calculateSerializedSize());
 126   if (auto EC = writeStrings(SectionWriter))
 127     return EC;
 128
 129   std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
 130   if (auto EC = writeHashTable(SectionWriter))
 131     return EC;
 132
 133   std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
 134   if (auto EC = writeEpilogue(SectionWriter))
 135     return EC;
 136
 137   return Error::success();
 138 }