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