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