LLVM  6.0.0svn
PDBStringTableBuilder.cpp
Go to the documentation of this file.
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 
11 
12 #include "llvm/ADT/ArrayRef.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
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 }
Error writeObject(const T &Obj)
Writes the object Obj to the underlying stream, as if by using memcpy.
support::ulittle32_t ByteSize
Definition: RawTypes.h:326
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
support::ulittle32_t HashVersion
Definition: RawTypes.h:325
The header preceeding the /names stream.
Definition: RawTypes.h:323
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Error writeArray(ArrayRef< T > Array)
Writes an array of objects of type T to the underlying stream, as if by using memcpy.
static uint32_t computeBucketCount(uint32_t NumStrings)
uint32_t hashStringV1(StringRef Str)
Definition: Hash.cpp:21
#define H(x, y, z)
Definition: MD5.cpp:57
Provides write only access to a subclass of WritableBinaryStream.
support::ulittle32_t Signature
Definition: RawTypes.h:324
Error writeInteger(T Value)
Write the the integer Value to the underlying stream in the specified endianness. ...
uint32_t bytesRemaining() const
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
Represents a read-write view of a CodeView string table.
std::pair< BinaryStreamWriter, BinaryStreamWriter > split(uint32_t Off) const
Splits the Writer into two Writers at a given offset.
Adapter to write values to a stream in a particular byte order.
Definition: EndianStream.h:27
#define I(x, y, z)
Definition: MD5.cpp:58
const uint32_t PDBStringTableSignature
Definition: RawTypes.h:329
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49