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