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