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