Fix emission of PDB string table.
This was originally reported as a bug with the symptom being "cvdump
crashes when printing an LLD-linked PDB that has an S_FILESTATIC record
in it". After some additional investigation, I determined that this was
a symptom of a larger problem, and in fact the real problem was in the
way we emitted the global PDB string table. As evidence of this, you can
take any lld-generated PDB, run cvdump -stringtable on it, and it would
return no results.
My hypothesis was that cvdump could not *find* the string table to begin
with. Normally it would do this by looking in the "named stream map",
finding the string /names, and using its value as the stream index. If
this lookup fails, then cvdump would fail to load the string table.
To test this hypothesis, I looked at the name stream map generated by a
link.exe PDB, and I emitted exactly those bytes into an LLD-generated
PDB. Suddenly, cvdump could read our string table!
This code has always been hacky and we knew there was something we
didn't understand. After all, there were some comments to the effect of
"we have to emit strings in a specific order, otherwise things don't
work". The key to fixing this was finally understanding this.
The way it works is that it makes use of a generic serializable hash map
that maps integers to other integers. In this case, the "key" is the
offset into a buffer, and the value is the stream number. If you index
into the buffer at the offset specified by a given key, you find the
name. The underlying cause of all these problems is that we were using
the identity function for the hash. i.e. if a string's offset in the
buffer was 12, the hash value was 12. Instead, we need to hash the
string *at that offset*. There is an additional catch, in that we have
to compute the hash as a uint32 and then truncate it to uint16.
Making this work is a little bit annoying, because we use the same hash
table in other places as well, and normally just using the identity
function for the hash function is actually what's desired. I'm not
totally happy with the template goo I came up with, but it works in any
case.
The reason we never found this bug through our own testing is because we
were building a /parallel/ hash table (in the form of an
llvm::StringMap<>) and doing all of our lookups and "real" hash table
work against that. I deleted all of that code and now everything goes
through the real hash table. Then, to test it, I added a unit test which
adds 7 strings and queries the associated values. I test every possible
insertion order permutation of these 7 strings, to verify that it really
does work as expected.
Differential Revision: https://reviews.llvm.org/D43326
llvm-svn: 325386
diff --git a/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp b/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
index 6cdf6dd..983b6eb 100644
--- a/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
@@ -11,6 +11,7 @@
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/iterator_range.h"
+#include "llvm/DebugInfo/PDB/Native/Hash.h"
#include "llvm/DebugInfo/PDB/Native/HashTable.h"
#include "llvm/DebugInfo/PDB/Native/RawError.h"
#include "llvm/Support/BinaryStreamReader.h"
@@ -26,127 +27,100 @@
using namespace llvm;
using namespace llvm::pdb;
-// FIXME: This shouldn't be necessary, but if we insert the strings in any
-// other order, cvdump cannot read the generated name map. This suggests that
-// we may be using the wrong hash function. A closer inspection of the cvdump
-// source code may reveal something, but for now this at least makes us work,
-// even if only by accident.
-static constexpr const char *OrderedStreamNames[] = {"/LinkInfo", "/names",
- "/src/headerblock"};
+namespace {
+struct NamedStreamMapTraits {
+ static uint16_t hash(StringRef S, const NamedStreamMap &NS) {
+ // In the reference implementation, this uses
+ // HASH Hasher<ULONG*, USHORT*>::hashPbCb(PB pb, size_t cb, ULONG ulMod).
+ // Here, the type HASH is a typedef of unsigned short.
+ // ** It is not a bug that we truncate the result of hashStringV1, in fact
+ // it is a bug if we do not! **
+ return static_cast<uint16_t>(hashStringV1(S));
+ }
+ static StringRef realKey(uint32_t Offset, const NamedStreamMap &NS) {
+ return NS.getString(Offset);
+ }
+ static uint32_t lowerKey(StringRef S, NamedStreamMap &NS) {
+ return NS.appendStringData(S);
+ }
+};
+} // namespace
-NamedStreamMap::NamedStreamMap() = default;
+NamedStreamMap::NamedStreamMap() {}
Error NamedStreamMap::load(BinaryStreamReader &Stream) {
- Mapping.clear();
- FinalizedHashTable.clear();
- FinalizedInfo.reset();
-
uint32_t StringBufferSize;
if (auto EC = Stream.readInteger(StringBufferSize))
return joinErrors(std::move(EC),
make_error<RawError>(raw_error_code::corrupt_file,
"Expected string buffer size"));
- BinaryStreamRef StringsBuffer;
- if (auto EC = Stream.readStreamRef(StringsBuffer, StringBufferSize))
+ StringRef Buffer;
+ if (auto EC = Stream.readFixedString(Buffer, StringBufferSize))
return EC;
+ NamesBuffer.assign(Buffer.begin(), Buffer.end());
- HashTable OffsetIndexMap;
- if (auto EC = OffsetIndexMap.load(Stream))
- return EC;
-
- uint32_t NameOffset;
- uint32_t NameIndex;
- for (const auto &Entry : OffsetIndexMap) {
- std::tie(NameOffset, NameIndex) = Entry;
-
- // Compute the offset of the start of the string relative to the stream.
- BinaryStreamReader NameReader(StringsBuffer);
- NameReader.setOffset(NameOffset);
- // Pump out our c-string from the stream.
- StringRef Str;
- if (auto EC = NameReader.readCString(Str))
- return joinErrors(std::move(EC),
- make_error<RawError>(raw_error_code::corrupt_file,
- "Expected name map name"));
-
- // Add this to a string-map from name to stream number.
- Mapping.insert({Str, NameIndex});
- }
-
- return Error::success();
+ return OffsetIndexMap.load(Stream);
}
Error NamedStreamMap::commit(BinaryStreamWriter &Writer) const {
- assert(FinalizedInfo.hasValue());
-
// The first field is the number of bytes of string data.
- if (auto EC = Writer.writeInteger(FinalizedInfo->StringDataBytes))
+ if (auto EC = Writer.writeInteger<uint32_t>(NamesBuffer.size()))
return EC;
- for (const auto &Name : OrderedStreamNames) {
- auto Item = Mapping.find(Name);
- if (Item == Mapping.end())
- continue;
- if (auto EC = Writer.writeCString(Item->getKey()))
- return EC;
- }
+ // Then the actual string data.
+ StringRef Data(NamesBuffer.data(), NamesBuffer.size());
+ if (auto EC = Writer.writeFixedString(Data))
+ return EC;
// And finally the Offset Index map.
- if (auto EC = FinalizedHashTable.commit(Writer))
+ if (auto EC = OffsetIndexMap.commit(Writer))
return EC;
return Error::success();
}
-uint32_t NamedStreamMap::finalize() {
- if (FinalizedInfo.hasValue())
- return FinalizedInfo->SerializedLength;
-
- // Build the finalized hash table.
- FinalizedHashTable.clear();
- FinalizedInfo.emplace();
-
- for (const auto &Name : OrderedStreamNames) {
- auto Item = Mapping.find(Name);
- if (Item == Mapping.end())
- continue;
- FinalizedHashTable.set(FinalizedInfo->StringDataBytes, Item->getValue());
- FinalizedInfo->StringDataBytes += Item->getKeyLength() + 1;
- }
-
- // Number of bytes of string data.
- FinalizedInfo->SerializedLength += sizeof(support::ulittle32_t);
- // Followed by that many actual bytes of string data.
- FinalizedInfo->SerializedLength += FinalizedInfo->StringDataBytes;
- // Followed by the mapping from Offset to Index.
- FinalizedInfo->SerializedLength +=
- FinalizedHashTable.calculateSerializedLength();
- return FinalizedInfo->SerializedLength;
+uint32_t NamedStreamMap::calculateSerializedLength() const {
+ return sizeof(uint32_t) // String data size
+ + NamesBuffer.size() // String data
+ + OffsetIndexMap.calculateSerializedLength(); // Offset Index Map
}
-iterator_range<StringMapConstIterator<uint32_t>>
-NamedStreamMap::entries() const {
- return make_range<StringMapConstIterator<uint32_t>>(Mapping.begin(),
- Mapping.end());
+uint32_t NamedStreamMap::size() const { return OffsetIndexMap.size(); }
+
+StringRef NamedStreamMap::getString(uint32_t Offset) const {
+ assert(NamesBuffer.size() > Offset);
+ return StringRef(NamesBuffer.data() + Offset);
}
-uint32_t NamedStreamMap::size() const { return Mapping.size(); }
+uint32_t NamedStreamMap::hashString(uint32_t Offset) const {
+ return hashStringV1(getString(Offset));
+}
bool NamedStreamMap::get(StringRef Stream, uint32_t &StreamNo) const {
- auto Iter = Mapping.find(Stream);
- if (Iter == Mapping.end())
+ auto Iter = OffsetIndexMap.find_as<NamedStreamMapTraits>(Stream, *this);
+ if (Iter == OffsetIndexMap.end())
return false;
- StreamNo = Iter->second;
+ StreamNo = (*Iter).second;
return true;
}
-void NamedStreamMap::set(StringRef Stream, uint32_t StreamNo) {
- FinalizedInfo.reset();
- Mapping[Stream] = StreamNo;
+StringMap<uint32_t> NamedStreamMap::entries() const {
+ StringMap<uint32_t> Result;
+ for (const auto &Entry : OffsetIndexMap) {
+ StringRef Stream(NamesBuffer.data() + Entry.first);
+ Result.try_emplace(Stream, Entry.second);
+ }
+ return Result;
}
-void NamedStreamMap::remove(StringRef Stream) {
- FinalizedInfo.reset();
- Mapping.erase(Stream);
+uint32_t NamedStreamMap::appendStringData(StringRef S) {
+ uint32_t Offset = NamesBuffer.size();
+ NamesBuffer.insert(NamesBuffer.end(), S.begin(), S.end());
+ NamesBuffer.push_back('\0');
+ return Offset;
+}
+
+void NamedStreamMap::set(StringRef Stream, uint32_t StreamNo) {
+ OffsetIndexMap.set_as<NamedStreamMapTraits>(Stream, StreamNo, *this);
}