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 #include <map> 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 StringTableHashTraits::StringTableHashTraits(PDBStringTableBuilder &Table) 27 : Table(&Table) {} 28 29 uint32_t StringTableHashTraits::hashLookupKey(StringRef S) const { 30 return Table->getIdForString(S); 31 } 32 33 StringRef StringTableHashTraits::storageKeyToLookupKey(uint32_t Offset) const { 34 return Table->getStringForId(Offset); 35 } 36 37 uint32_t StringTableHashTraits::lookupKeyToStorageKey(StringRef S) { 38 return Table->insert(S); 39 } 40 41 uint32_t PDBStringTableBuilder::insert(StringRef S) { 42 return Strings.insert(S); 43 } 44 45 uint32_t PDBStringTableBuilder::getIdForString(StringRef S) const { 46 return Strings.getIdForString(S); 47 } 48 49 StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const { 50 return Strings.getStringForId(Id); 51 } 52 53 // This is a precomputed list of Buckets given the specified number of 54 // strings. Matching the reference algorithm exactly is not strictly 55 // necessary for correctness, but it helps when comparing LLD's PDBs with 56 // Microsoft's PDBs so as to eliminate superfluous differences. 57 static std::map<uint32_t, uint32_t> StringsToBuckets = { 58 {1, 2}, 59 {2, 4}, 60 {4, 7}, 61 {6, 11}, 62 {9, 17}, 63 {13, 26}, 64 {20, 40}, 65 {31, 61}, 66 {46, 92}, 67 {70, 139}, 68 {105, 209}, 69 {157, 314}, 70 {236, 472}, 71 {355, 709}, 72 {532, 1064}, 73 {799, 1597}, 74 {1198, 2396}, 75 {1798, 3595}, 76 {2697, 5393}, 77 {4045, 8090}, 78 {6068, 12136}, 79 {9103, 18205}, 80 {13654, 27308}, 81 {20482, 40963}, 82 {30723, 61445}, 83 {46084, 92168}, 84 {69127, 138253}, 85 {103690, 207380}, 86 {155536, 311071}, 87 {233304, 466607}, 88 {349956, 699911}, 89 {524934, 1049867}, 90 {787401, 1574801}, 91 {1181101, 2362202}, 92 {1771652, 3543304}, 93 {2657479, 5314957}, 94 {3986218, 7972436}, 95 {5979328, 11958655}, 96 {8968992, 17937983}, 97 {13453488, 26906975}, 98 {20180232, 40360463}, 99 {30270348, 60540695}, 100 {45405522, 90811043}, 101 {68108283, 136216565}, 102 {102162424, 204324848}, 103 {153243637, 306487273}, 104 {229865455, 459730910}, 105 {344798183, 689596366}, 106 {517197275, 1034394550}, 107 {775795913, 1551591826}}; 108 109 static uint32_t computeBucketCount(uint32_t NumStrings) { 110 auto Entry = StringsToBuckets.lower_bound(NumStrings); 111 assert(Entry != StringsToBuckets.end()); 112 return Entry->second; 113 } 114 115 uint32_t PDBStringTableBuilder::calculateHashTableSize() const { 116 uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field. 117 Size += sizeof(uint32_t) * computeBucketCount(Strings.size()); 118 119 return Size; 120 } 121 122 uint32_t PDBStringTableBuilder::calculateSerializedSize() const { 123 uint32_t Size = 0; 124 Size += sizeof(PDBStringTableHeader); 125 Size += Strings.calculateSerializedSize(); 126 Size += calculateHashTableSize(); 127 Size += sizeof(uint32_t); // The /names stream ends with the string count. 128 return Size; 129 } 130 131 void PDBStringTableBuilder::setStrings( 132 const codeview::DebugStringTableSubsection &Strings) { 133 this->Strings = Strings; 134 } 135 136 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const { 137 // Write a header 138 PDBStringTableHeader H; 139 H.Signature = PDBStringTableSignature; 140 H.HashVersion = 1; 141 H.ByteSize = Strings.calculateSerializedSize(); 142 if (auto EC = Writer.writeObject(H)) 143 return EC; 144 assert(Writer.bytesRemaining() == 0); 145 return Error::success(); 146 } 147 148 Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const { 149 if (auto EC = Strings.commit(Writer)) 150 return EC; 151 152 assert(Writer.bytesRemaining() == 0); 153 return Error::success(); 154 } 155 156 Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const { 157 // Write a hash table. 158 uint32_t BucketCount = computeBucketCount(Strings.size()); 159 if (auto EC = Writer.writeInteger(BucketCount)) 160 return EC; 161 std::vector<ulittle32_t> Buckets(BucketCount); 162 163 for (auto &Pair : Strings) { 164 StringRef S = Pair.getKey(); 165 uint32_t Offset = Pair.getValue(); 166 uint32_t Hash = hashStringV1(S); 167 168 for (uint32_t I = 0; I != BucketCount; ++I) { 169 uint32_t Slot = (Hash + I) % BucketCount; 170 if (Buckets[Slot] != 0) 171 continue; 172 Buckets[Slot] = Offset; 173 break; 174 } 175 } 176 177 if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets))) 178 return EC; 179 180 assert(Writer.bytesRemaining() == 0); 181 return Error::success(); 182 } 183 184 Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const { 185 if (auto EC = Writer.writeInteger<uint32_t>(Strings.size())) 186 return EC; 187 assert(Writer.bytesRemaining() == 0); 188 return Error::success(); 189 } 190 191 Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const { 192 BinaryStreamWriter SectionWriter; 193 194 std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader)); 195 if (auto EC = writeHeader(SectionWriter)) 196 return EC; 197 198 std::tie(SectionWriter, Writer) = 199 Writer.split(Strings.calculateSerializedSize()); 200 if (auto EC = writeStrings(SectionWriter)) 201 return EC; 202 203 std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize()); 204 if (auto EC = writeHashTable(SectionWriter)) 205 return EC; 206 207 std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t)); 208 if (auto EC = writeEpilogue(SectionWriter)) 209 return EC; 210 211 return Error::success(); 212 } 213
