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