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 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
56   // Write a header
57   PDBStringTableHeader H;
58   H.Signature = PDBStringTableSignature;
59   H.HashVersion = 1;
60   H.ByteSize = Strings.calculateSerializedSize();
61   if (auto EC = Writer.writeObject(H))
62     return EC;
63   assert(Writer.bytesRemaining() == 0);
64   return Error::success();
65 }
66 
67 Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
68   if (auto EC = Strings.commit(Writer))
69     return EC;
70 
71   assert(Writer.bytesRemaining() == 0);
72   return Error::success();
73 }
74 
75 Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
76   // Write a hash table.
77   uint32_t BucketCount = computeBucketCount(Strings.size());
78   if (auto EC = Writer.writeInteger(BucketCount))
79     return EC;
80   std::vector<ulittle32_t> Buckets(BucketCount);
81 
82   for (auto &Pair : Strings) {
83     StringRef S = Pair.getKey();
84     uint32_t Offset = Pair.getValue();
85     uint32_t Hash = hashStringV1(S);
86 
87     for (uint32_t I = 0; I != BucketCount; ++I) {
88       uint32_t Slot = (Hash + I) % BucketCount;
89       if (Slot == 0)
90         continue; // Skip reserved slot
91       if (Buckets[Slot] != 0)
92         continue;
93       Buckets[Slot] = Offset;
94       break;
95     }
96   }
97 
98   if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
99     return EC;
100 
101   assert(Writer.bytesRemaining() == 0);
102   return Error::success();
103 }
104 
105 Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
106   if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
107     return EC;
108   assert(Writer.bytesRemaining() == 0);
109   return Error::success();
110 }
111 
112 Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
113   BinaryStreamWriter SectionWriter;
114 
115   std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
116   if (auto EC = writeHeader(SectionWriter))
117     return EC;
118 
119   std::tie(SectionWriter, Writer) =
120       Writer.split(Strings.calculateSerializedSize());
121   if (auto EC = writeStrings(SectionWriter))
122     return EC;
123 
124   std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
125   if (auto EC = writeHashTable(SectionWriter))
126     return EC;
127 
128   std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
129   if (auto EC = writeEpilogue(SectionWriter))
130     return EC;
131 
132   return Error::success();
133 }
134