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 #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 using namespace llvm; 18 using namespace llvm::support; 19 using namespace llvm::support::endian; 20 using namespace llvm::pdb; 21 22 uint32_t PDBStringTableBuilder::insert(StringRef S) { 23 auto P = Strings.insert({S, StringSize}); 24 25 // If a given string didn't exist in the string table, we want to increment 26 // the string table size. 27 if (P.second) 28 StringSize += S.size() + 1; // +1 for '\0' 29 return P.first->second; 30 } 31 32 uint32_t PDBStringTableBuilder::getStringIndex(StringRef S) { 33 auto Iter = Strings.find(S); 34 assert(Iter != Strings.end()); 35 return Iter->second; 36 } 37 38 static uint32_t computeBucketCount(uint32_t NumStrings) { 39 // The /names stream is basically an on-disk open-addressing hash table. 40 // Hash collisions are resolved by linear probing. We cannot make 41 // utilization 100% because it will make the linear probing extremely 42 // slow. But lower utilization wastes disk space. As a reasonable 43 // load factor, we choose 80%. We need +1 because slot 0 is reserved. 44 return (NumStrings + 1) * 1.25; 45 } 46 47 uint32_t PDBStringTableBuilder::finalize() { 48 uint32_t Size = 0; 49 Size += sizeof(PDBStringTableHeader); 50 Size += StringSize; 51 Size += sizeof(uint32_t); // Hash table begins with 4-byte size field. 52 53 uint32_t BucketCount = computeBucketCount(Strings.size()); 54 Size += BucketCount * sizeof(uint32_t); 55 56 Size += 57 sizeof(uint32_t); // The /names stream ends with the number of strings. 58 return Size; 59 } 60 61 Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const { 62 // Write a header 63 PDBStringTableHeader H; 64 H.Signature = PDBStringTableSignature; 65 H.HashVersion = 1; 66 H.ByteSize = StringSize; 67 if (auto EC = Writer.writeObject(H)) 68 return EC; 69 70 // Write a string table. 71 uint32_t StringStart = Writer.getOffset(); 72 for (auto Pair : Strings) { 73 StringRef S = Pair.first; 74 uint32_t Offset = Pair.second; 75 Writer.setOffset(StringStart + Offset); 76 if (auto EC = Writer.writeCString(S)) 77 return EC; 78 } 79 Writer.setOffset(StringStart + StringSize); 80 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.first; 89 uint32_t Offset = Pair.second; 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 if (auto EC = Writer.writeInteger(static_cast<uint32_t>(Strings.size()))) 106 return EC; 107 return Error::success(); 108 } 109