Raise the PDB Hash Map out of the NameMap class

[zturner]

Summary

[pdb] Raise out the hash table used in NameMap to its own class.

This data structure is used in other places in the PDB code,
one of which we have immediate need for in the TPI stream.  The
data structure is the exact same as that used by the NameMap.
It is not really so much of a hash table as it is a linear
dictionary where items can be deleted and then later re-used.

In raising this out, I found some bugs in the original
implementation, particularly regarding the deleted and present
bit vectors whose values were improperly being ignored upon
serialization.

In the Microsoft implementation, this is a template class where
key and value can be arbitrary types.  However, in all uses
which seem important to serialize, the key and value are
32-bit integers, so to simplify things I've called this class
LinearIntegerMap.  We can re-generalize later if we find it
necessary to do so.

[ruiu]

llvm/include/llvm/DebugInfo/PDB/Raw/LinearIntegerMap.h

8

It doesn't have to be detailed, but this needs a file comment to describe what this is.

69–70

You can initialize them by = {0};, no?

llvm/lib/DebugInfo/PDB/Raw/LinearIntegerMap.cpp

22

What does HAH stand for?

32–33

You are extending these vectors unconditionally. What was the point of resize(1) in the ctor?

67–70

Does this actually find largest numbers?

153–154

Remove this.

188

This needs a comment.

[zturner]

llvm/lib/DebugInfo/PDB/Raw/LinearIntegerMap.cpp

22

Left over from old code where it was more obvious. I can fix this.

32–33

You can either create one of these and manipulate it in memory then serialize it, or you can load one from a serialized format. If you create one from scratch, the capacity needs to be at least 1 so that you can write an item into it.

67–70

Yes since it's a bit vector, the values you get from iterating over it are the indices that contain set bits. It iterates over the indices which contain 1 bits, in ascending order. So the last value should be the index of the largest set bit.

188

Good point. FWIW this comes from the Microsoft code, where they want to maintain < 2/3 load factor (size / capacity ratio)

[majnemer]

llvm/include/llvm/DebugInfo/PDB/Raw/LinearIntegerMap.h

59

Capacity ?

79

= default; ?

llvm/lib/DebugInfo/PDB/Raw/LinearIntegerMap.cpp

187–188

Capacity ? Also, I'd add parens.

194

capacity() * 3 can overflow, should there be a std::max with capacity()? Maybe std::max(capacity() * 3 / 2 + 1, capacity() + 1) ?

[zturner]

There are some intricacies of the data structure that I didn't properly handle with regards to growing and some interactions between deleted and empty entries.

AFAICT this is basically an open address hash table with lazy deletion where the hash function is the identity. I need to re-work this to properly handle rehashing and lazy deletion.

[zturner]

This patch is entirely re-worked. Support for Present and Deleted fields is correctly implemented, linear probing is correctly implemented, growing is correctly implemented, and some unit tests are added to verify all of this.

[majnemer]

llvm/lib/DebugInfo/PDB/Raw/HashTable.cpp

189 ↗

(On Diff #84745)

Should we assert that NewCapacity is bigger than capacity()?

[zturner]

llvm/lib/DebugInfo/PDB/Raw/HashTable.cpp

189 ↗

(On Diff #84745)

Forgot about this, I'm using your suggestion of std::max from the previous comment, will upload a fix and some other minor cleanups shortly.

[zturner]

Fix an unchecked overflow in HashTable::grow() and fix some small typos and cleanups.

[zturner]

Ping.

[majnemer]

LGTM

llvm/include/llvm/DebugInfo/PDB/Raw/LinearIntegerMap.h

+//===- LinearIntegerMap.h - PDB Linear Map ----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_PDB_RAW_LINEARINTEGERMAP_H
+#define LLVM_DEBUGINFO_PDB_RAW_LINEARINTEGERMAP_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/SparseBitVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/DebugInfo/MSF/StreamArray.h"
+#include "llvm/DebugInfo/MSF/StreamReader.h"
+#include "llvm/DebugInfo/MSF/StreamWriter.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MathExtras.h"
+
+#include <cstdint>
+#include <utility>
+
+namespace llvm {
+namespace pdb {
+
+class LinearIntegerMap {
+  friend class LinearIntegerMapIterator;
+  struct Header {
+    support::ulittle32_t Size;
+    support::ulittle32_t Capacity;
+  };
+
+public:
+  typedef std::pair<uint32_t, uint32_t> Mapping;
+  LinearIntegerMap();
+
+  Error load(msf::StreamReader &Stream);
+
+  uint32_t calculateSerializedLength() const;
+  Error commit(msf::StreamWriter &Writer) const;
+
+  uint32_t capacity() const;
+  uint32_t size() const;
+
+  LinearIntegerMapIterator begin() const;
+  LinearIntegerMapIterator end() const;
+  LinearIntegerMapIterator find(uint32_t K);
+
+  void insertOrUpdate(uint32_t K, uint32_t V);
+  void remove(uint32_t K);
+  uint32_t get(uint32_t K);
+
+private:
+  std::pair<uint32_t, LinearIntegerMapIterator> findInternal(uint32_t K);
+  static uint32_t maxSize(uint32_t capacity);
+  void growIfAtCapacity();
+  static Error readSparseBitVector(msf::StreamReader &Stream,
+                                   SparseBitVector<> &V);
+  static Error writeSparseBitVector(msf::StreamWriter &Writer,
+                                    SparseBitVector<> &Vec);
+
+  mutable SparseBitVector<> Present;
+  mutable SparseBitVector<> Deleted;
+
+  std::vector<uint32_t> Keys;
+  std::vector<uint32_t> Values;
+};
+
+class LinearIntegerMapIterator
+    : public iterator_facade_base<LinearIntegerMapIterator,
+                                  std::forward_iterator_tag,
+                                  std::pair<uint32_t, uint32_t>> {
+public:
+  LinearIntegerMapIterator(const LinearIntegerMap &Map);
+  LinearIntegerMapIterator() {}
+
+  LinearIntegerMapIterator &operator=(const LinearIntegerMapIterator &R);
+  bool operator==(const LinearIntegerMapIterator &R) const;
+  const std::pair<uint32_t, uint32_t> &operator*() const;
+  LinearIntegerMapIterator &operator++();
+
+private:
+  void update();
+  bool isEnd() const;
+
+  std::pair<uint32_t, uint32_t> Item;
+  const LinearIntegerMap *Map = nullptr;
+  llvm::SparseBitVector<>::iterator Iter;
+};
+
+} // end namespace pdb
+} // end namespace llvm
+
+#endif // LLVM_DEBUGINFO_PDB_RAW_LINEARMAP_H

llvm/include/llvm/DebugInfo/PDB/Raw/NameMapBuilder.h

 //===- NameMapBuilder.h - PDB Name Map Builder ------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_PDB_RAW_PDBNAMEMAPBUILDER_H
 #define LLVM_DEBUGINFO_PDB_RAW_PDBNAMEMAPBUILDER_H
 
-#include "llvm/ADT/StringMap.h"
+#include "llvm/DebugInfo/PDB/Raw/LinearIntegerMap.h"
 #include "llvm/Support/Error.h"
 
 #include <cstdint>
 #include <memory>
+#include <vector>
 
 namespace llvm {
 namespace msf {
 class StreamWriter;
 }
 namespace pdb {
 class NameMap;
 
 class NameMapBuilder {
 public:
   NameMapBuilder();
 
   void addMapping(StringRef Name, uint32_t Mapping);
 
-  Expected<std::unique_ptr<NameMap>> build();
   Error commit(msf::StreamWriter &Writer) const;
 
   uint32_t calculateSerializedLength() const;
 
 private:
-  StringMap<uint32_t> Map;
-  uint32_t StringDataBytes = 0;
+  std::vector<StringRef> Strings;
+  LinearIntegerMap Map;
+  uint32_t Offset = 0;
 };
 
 } // end namespace pdb
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_PDB_RAW_PDBNAMEMAPBUILDER_H

llvm/lib/DebugInfo/PDB/CMakeLists.txt

add_pdb_impl_folder(Raw
   Raw/DbiStream.cpp
   Raw/DbiStreamBuilder.cpp
   Raw/EnumTables.cpp
   Raw/GlobalsStream.cpp
   Raw/GSI.cpp
   Raw/Hash.cpp
   Raw/InfoStream.cpp
   Raw/InfoStreamBuilder.cpp
+  Raw/LinearIntegerMap.cpp
   Raw/ModInfo.cpp
   Raw/ModStream.cpp
   Raw/NameHashTable.cpp
   Raw/NameMap.cpp
   Raw/NameMapBuilder.cpp
   Raw/PDBFile.cpp
   Raw/PDBFileBuilder.cpp
   Raw/PublicsStream.cpp

llvm/lib/DebugInfo/PDB/Raw/LinearIntegerMap.cpp

+//===- LinearIntegerMap.cpp - PDB Linear Map --------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/PDB/Raw/LinearIntegerMap.h"
+#include "llvm/DebugInfo/PDB/Raw/RawError.h"
+
+using namespace llvm;
+using namespace llvm::pdb;
+
+LinearIntegerMap::LinearIntegerMap() {
+  Keys.resize(1);
+  Values.resize(1);
+}
+
+Error LinearIntegerMap::load(msf::StreamReader &Stream) {
+  const Header *HAH;
+  if (auto EC = Stream.readObject(HAH))
+    return EC;
+  if (HAH->Capacity == 0)
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "Invalid Linear Map Capacity");
+  if (HAH->Size > maxSize(HAH->Capacity))
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "Invalid Linear Map Size");
+
+  Keys.resize(HAH->Capacity);
+  Values.resize(HAH->Capacity);
+
+  if (auto EC = readSparseBitVector(Stream, Present))
+    return EC;
+  if (Present.count() != HAH->Size)
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "Present bit vector does not match size!");
+
+  if (auto EC = readSparseBitVector(Stream, Deleted))
+    return EC;
+  if (Present.intersects(Deleted))
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "Present bit vector interesects deleted!");
+
+  for (uint32_t I = 0; I < HAH->Capacity; ++I) {
+    if (!Present.test(I))
+      continue;
+
+    if (auto EC = Stream.readInteger(Keys[I]))
+      return EC;
+    if (auto EC = Stream.readInteger(Values[I]))
+      return EC;
+  }
+  return Error::success();
+}
+
+uint32_t LinearIntegerMap::calculateSerializedLength() const {
+  uint32_t Size = sizeof(Header);
+
+  // Figure out the number of 32-bit words required to hold all of the bits in
+  // the present and deleted sets.  The only way to do this is to find the
+  // largest value in each set, which is O(n) in the number of set bits.
+  uint32_t LargestP = 0;
+  uint32_t LargestD = 0;
+  for (uint32_t P : Present)
+    LargestP = P;
+  for (uint32_t D : Deleted)
+    LargestD = D;
+  uint32_t PresentWords =
+      alignTo(LargestP, sizeof(uint32_t)) / sizeof(uint32_t);
+  uint32_t DeletedWords =
+      alignTo(LargestD, sizeof(uint32_t)) / sizeof(uint32_t);
+
+  // Present bit set number of words, followed by that many actual words.
+  Size += sizeof(uint32_t);
+  Size += PresentWords * sizeof(uint32_t);
+
+  // Deleted bit set number of words, followed by that many actual words.
+  Size += sizeof(uint32_t);
+  Size += DeletedWords * sizeof(uint32_t);
+
+  // One (Key, Value) pair for each entry Present.
+  Size += 2 * sizeof(uint32_t) * Present.count();
+
+  return Size;
+}
+
+Error LinearIntegerMap::commit(msf::StreamWriter &Writer) const {
+  Header H;
+  H.Size = size();
+  H.Capacity = capacity();
+  if (auto EC = Writer.writeObject(H))
+    return EC;
+
+  if (auto EC = writeSparseBitVector(Writer, Present))
+    return EC;
+
+  if (auto EC = writeSparseBitVector(Writer, Deleted))
+    return EC;
+
+  for (const auto &Entry : *this) {
+    if (auto EC = Writer.writeInteger(Entry.first))
+      return EC;
+    if (auto EC = Writer.writeInteger(Entry.second))
+      return EC;
+  }
+  return Error::success();
+}
+
+uint32_t LinearIntegerMap::capacity() const { return Keys.size(); }
+uint32_t LinearIntegerMap::size() const { return Present.count(); }
+
+LinearIntegerMapIterator LinearIntegerMap::begin() const {
+  return LinearIntegerMapIterator(*this);
+}
+LinearIntegerMapIterator LinearIntegerMap::end() const {
+  return LinearIntegerMapIterator();
+}
+
+LinearIntegerMapIterator LinearIntegerMap::find(uint32_t K) {
+  return findInternal(K).second;
+}
+
+void LinearIntegerMap::insertOrUpdate(uint32_t K, uint32_t V) {
+  auto Entry = findInternal(K);
+  if (Entry.second != end()) {
+    assert(Present.test(Entry.first));
+    assert(!Deleted.test(Entry.first));
+    // We're updating, no need to do anything special.
+    Values[Entry.first] = V;
+    return;
+  }
+
+  // We're inserting, try to put it in the first deleted location.
+  int D = Deleted.find_first();
+  if (D != -1) {
+    Keys[D] = K;
+    Values[D] = V;
+    Present.set(D);
+    Deleted.reset(D);
+    return;
+  }
+
+  // No deleted locations exist, append it to the end, making sure to grow if
+  // necessary.
+  uint32_t S = size();
+  Keys[S] = K;
+  Values[S] = V;
+  Present.set(S);
+  growIfAtCapacity();
+
+  return;
+}
+
+void LinearIntegerMap::remove(uint32_t K) {
+  auto Entry = findInternal(K);
+  // It wasn't here to begin with, just exit.
+  if (Entry.second == end()) {
+    assert(!Present.test(Entry.first));
+    return;
+  }
+
+  assert(Present.test(Entry.first) && !Deleted.test(Entry.first));
+  Present.reset(Entry.first);
+  Deleted.set(Entry.first);
+}
+
+uint32_t LinearIntegerMap::get(uint32_t K) {
+  auto I = find(K);
+  assert(I != end());
+  return (*I).second;
+}
+
+std::pair<uint32_t, LinearIntegerMapIterator>
+LinearIntegerMap::findInternal(uint32_t K) {
+  uint32_t Idx = 0;
+  for (auto IT = begin(); IT != end(); ++IT, ++Idx) {
+    if ((*IT).first == K)
+      return std::make_pair(Idx, IT);
+  }
+
+  return std::make_pair(size(), end());
+}
+
+uint32_t LinearIntegerMap::maxSize(uint32_t capacity) {
+  return capacity * 2 / 3 + 1;
+}
+
+void LinearIntegerMap::growIfAtCapacity() {
+  if (size() < maxSize(capacity()))
+    return;
+  uint32_t NewCapacity = capacity() * 3 / 2 + 1;
+  Keys.resize(NewCapacity);
+  Values.resize(NewCapacity);
+}
+
+Error LinearIntegerMap::readSparseBitVector(msf::StreamReader &Stream,
+                                            SparseBitVector<> &V) {
+  uint32_t NumWords;
+  if (auto EC = Stream.readInteger(NumWords))
+    return joinErrors(
+        std::move(EC),
+        make_error<RawError>(raw_error_code::corrupt_file,
+                             "Expected Linear map number of words"));
+
+  for (uint32_t I = 0; I != NumWords; ++I) {
+    uint32_t Word;
+    if (auto EC = Stream.readInteger(Word))
+      return joinErrors(std::move(EC),
+                        make_error<RawError>(raw_error_code::corrupt_file,
+                                             "Expected Linear map word"));
+    for (unsigned Idx = 0; Idx < 32; ++Idx)
+      if (Word & (1U << Idx))
+        V.set((I * 32) + Idx);
+  }
+  return Error::success();
+}
+
+Error LinearIntegerMap::writeSparseBitVector(msf::StreamWriter &Writer,
+                                             SparseBitVector<> &Vec) {
+  uint32_t Largest = 0;
+  for (uint32_t V : Vec)
+    Largest = V;
+  uint32_t NumWords = alignTo(Largest, sizeof(uint32_t)) / sizeof(uint32_t);
+  if (auto EC = Writer.writeInteger(NumWords))
+    return joinErrors(
+        std::move(EC),
+        make_error<RawError>(raw_error_code::corrupt_file,
+                             "Could not write linear map number of words"));
+
+  uint32_t Idx = 0;
+  for (uint32_t I = 0; I != NumWords; ++I) {
+    uint32_t Word = 0;
+    for (uint32_t WordIdx = 0; WordIdx < 32; ++WordIdx, ++Idx) {
+      if (Vec.test(Idx))
+        Word |= (1 << WordIdx);
+    }
+    if (auto EC = Writer.writeInteger(Word))
+      return joinErrors(std::move(EC), make_error<RawError>(
+                                           raw_error_code::corrupt_file,
+                                           "Could not write linear map word"));
+  }
+  return Error::success();
+}
+
+LinearIntegerMapIterator::LinearIntegerMapIterator(const LinearIntegerMap &Map)
+    : Map(&Map), Iter(Map.Present.begin()) {
+  update();
+}
+
+LinearIntegerMapIterator &LinearIntegerMapIterator::
+operator=(const LinearIntegerMapIterator &R) {
+  Map = R.Map;
+  return *this;
+}
+
+bool LinearIntegerMapIterator::
+operator==(const LinearIntegerMapIterator &R) const {
+  if (isEnd() && R.isEnd())
+    return true;
+
+  return (Map == R.Map) && (Iter == R.Iter);
+}
+
+const std::pair<uint32_t, uint32_t> &LinearIntegerMapIterator::
+operator*() const {
+  return Item;
+}
+
+LinearIntegerMapIterator &LinearIntegerMapIterator::operator++() {
+  ++Iter;
+  update();
+  return *this;
+}
+
+void LinearIntegerMapIterator::update() {
+  if (isEnd())
+    return;
+  Item.first = Map->Keys[*Iter];
+  Item.second = Map->Values[*Iter];
+}
+bool LinearIntegerMapIterator::isEnd() const {
+  return !Map || Iter == Map->Present.end();
+}

llvm/lib/DebugInfo/PDB/Raw/NameMap.cpp

 //===- NameMap.cpp - PDB Name Map -------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/DebugInfo/PDB/Raw/NameMap.h"
+
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/DebugInfo/MSF/StreamReader.h"
-#include "llvm/DebugInfo/PDB/Raw/NameMap.h"
+#include "llvm/DebugInfo/PDB/Raw/LinearIntegerMap.h"
 #include "llvm/DebugInfo/PDB/Raw/RawError.h"
 #include "llvm/Support/Error.h"
 #include <algorithm>
 #include <cstdint>
 
 using namespace llvm;
 using namespace llvm::msf;
 using namespace llvm::pdb;
 
 NameMap::NameMap() = default;
 
 Error NameMap::load(StreamReader &Stream) {
-  // This is some sort of weird string-set/hash table encoded in the stream.
-  // It starts with the number of bytes in the table.
-  uint32_t NumberOfBytes;
-  if (auto EC = Stream.readInteger(NumberOfBytes))
+  uint32_t StringBufferSize;
+  if (auto EC = Stream.readInteger(StringBufferSize))
     return joinErrors(std::move(EC),
                       make_error<RawError>(raw_error_code::corrupt_file,
-                                           "Expected name map length"));
-  if (Stream.bytesRemaining() < NumberOfBytes)
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Invalid name map length");
-
-  // Following that field is the starting offset of strings in the name table.
-  uint32_t StringsOffset = Stream.getOffset();
-  Stream.setOffset(StringsOffset + NumberOfBytes);
-
-  // This appears to be equivalent to the total number of strings *actually*
-  // in the name table.
-  uint32_t HashSize;
-  if (auto EC = Stream.readInteger(HashSize))
-    return joinErrors(std::move(EC),
-                      make_error<RawError>(raw_error_code::corrupt_file,
-                                           "Expected name map hash size"));
+                                           "Expected string buffer size"));
 
-  // This appears to be an upper bound on the number of strings in the name
-  // table.
-  uint32_t MaxNumberOfStrings;
-  if (auto EC = Stream.readInteger(MaxNumberOfStrings))
-    return joinErrors(std::move(EC),
-                      make_error<RawError>(raw_error_code::corrupt_file,
-                                           "Expected name map max strings"));
+  msf::ReadableStreamRef StringsBuffer;
+  if (auto EC = Stream.readStreamRef(StringsBuffer, StringBufferSize))
+    return EC;
 
-  if (MaxNumberOfStrings > (UINT32_MAX / sizeof(uint32_t)))
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Implausible number of strings");
-
-  const uint32_t MaxNumberOfWords = UINT32_MAX / (sizeof(uint32_t) * 8);
-
-  // This appears to be a hash table which uses bitfields to determine whether
-  // or not a bucket is 'present'.
-  uint32_t NumPresentWords;
-  if (auto EC = Stream.readInteger(NumPresentWords))
-    return joinErrors(std::move(EC),
-                      make_error<RawError>(raw_error_code::corrupt_file,
-                                           "Expected name map num words"));
-
-  if (NumPresentWords > MaxNumberOfWords)
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Number of present words is too large");
-
-  SparseBitVector<> Present;
-  for (uint32_t I = 0; I != NumPresentWords; ++I) {
-    uint32_t Word;
-    if (auto EC = Stream.readInteger(Word))
-      return joinErrors(std::move(EC),
-                        make_error<RawError>(raw_error_code::corrupt_file,
-                                             "Expected name map word"));
-    for (unsigned Idx = 0; Idx < 32; ++Idx)
-      if (Word & (1U << Idx))
-        Present.set((I * 32) + Idx);
-  }
+  LinearIntegerMap OffsetIndexMap;
+  if (auto EC = OffsetIndexMap.load(Stream))
+    return EC;
 
-  // This appears to be a hash table which uses bitfields to determine whether
-  // or not a bucket is 'deleted'.
-  uint32_t NumDeletedWords;
-  if (auto EC = Stream.readInteger(NumDeletedWords))
-    return joinErrors(
-        std::move(EC),
-        make_error<RawError>(raw_error_code::corrupt_file,
-                             "Expected name map num deleted words"));
-
-  if (NumDeletedWords > MaxNumberOfWords)
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Number of deleted words is too large");
-
-  SparseBitVector<> Deleted;
-  for (uint32_t I = 0; I != NumDeletedWords; ++I) {
-    uint32_t Word;
-    if (auto EC = Stream.readInteger(Word))
-      return joinErrors(std::move(EC),
-                        make_error<RawError>(raw_error_code::corrupt_file,
-                                             "Expected name map word"));
-    for (unsigned Idx = 0; Idx < 32; ++Idx)
-      if (Word & (1U << Idx))
-        Deleted.set((I * 32) + Idx);
-  }
-
-  for (unsigned I : Present) {
-    // For all present entries, dump out their mapping.
-    (void)I;
-
-    // This appears to be an offset relative to the start of the strings.
-    // It tells us where the null-terminated string begins.
-    uint32_t NameOffset;
-    if (auto EC = Stream.readInteger(NameOffset))
-      return joinErrors(std::move(EC),
-                        make_error<RawError>(raw_error_code::corrupt_file,
-                                             "Expected name map name offset"));
-
-    // This appears to be a stream number into the stream directory.
-    uint32_t NameIndex;
-    if (auto EC = Stream.readInteger(NameIndex))
-      return joinErrors(std::move(EC),
-                        make_error<RawError>(raw_error_code::corrupt_file,
-                                             "Expected name map name index"));
+  for (const auto &Entry : OffsetIndexMap) {
+    std::tie(NameOffset, NameIndex) = Entry;
 
     // Compute the offset of the start of the string relative to the stream.
-    uint32_t StringOffset = StringsOffset + NameOffset;
-    uint32_t OldOffset = Stream.getOffset();
+    msf::StreamReader NameReader(StringsBuffer);
+    NameReader.setOffset(NameOffset);
     // Pump out our c-string from the stream.
     StringRef Str;
-    Stream.setOffset(StringOffset);
-    if (auto EC = Stream.readZeroString(Str))
+    if (auto EC = NameReader.readZeroString(Str))
       return joinErrors(std::move(EC),
                         make_error<RawError>(raw_error_code::corrupt_file,
                                              "Expected name map name"));
 
-    Stream.setOffset(OldOffset);
     // Add this to a string-map from name to stream number.
     Mapping.insert({Str, NameIndex});
   }
 
   return Error::success();
 }
 
 iterator_range<StringMapConstIterator<uint32_t>> NameMap::entries() const {

llvm/lib/DebugInfo/PDB/Raw/NameMapBuilder.cpp

 #include <cstdint>
 
 using namespace llvm;
 using namespace llvm::pdb;
 
 NameMapBuilder::NameMapBuilder() = default;
 
 void NameMapBuilder::addMapping(StringRef Name, uint32_t Mapping) {
-  StringDataBytes += Name.size() + 1;
-  Map.insert({Name, Mapping});
-}
-
-Expected<std::unique_ptr<NameMap>> NameMapBuilder::build() {
-  auto Result = llvm::make_unique<NameMap>();
-  Result->Mapping = Map;
-  return std::move(Result);
+  Strings.push_back(Name);
+  Map.insertOrUpdate(Offset, Mapping);
+  Offset += Name.size() + 1;
 }
 
 uint32_t NameMapBuilder::calculateSerializedLength() const {
   uint32_t TotalLength = 0;
 
-  TotalLength += sizeof(support::ulittle32_t); // StringDataBytes value
-  TotalLength += StringDataBytes;              // actual string data
-
-  TotalLength += sizeof(support::ulittle32_t); // Hash Size
-  TotalLength += sizeof(support::ulittle32_t); // Max Number of Strings
-  TotalLength += sizeof(support::ulittle32_t); // Num Present Words
-  // One bitmask word for each present entry
-  TotalLength += Map.size() * sizeof(support::ulittle32_t);
-  TotalLength += sizeof(support::ulittle32_t); // Num Deleted Words
-
-  // For each present word, which we are treating as equivalent to the number of
-  // entries in the table, we have a pair of integers.  An offset into the
-  // string data, and a corresponding stream number.
-  TotalLength += Map.size() * 2 * sizeof(support::ulittle32_t);
+  // Number of bytes of string data.
+  TotalLength += sizeof(support::ulittle32_t);
+  // Followed by that many actual bytes of string data.
+  TotalLength += Offset;
+  // Followed by the mapping from Name to Index.
+  TotalLength += Map.calculateSerializedLength();
 
   return TotalLength;
 }
 
 Error NameMapBuilder::commit(msf::StreamWriter &Writer) const {
-  // The first field is the number of bytes of string data.  So add
-  // up the length of all strings plus a null terminator for each
-  // one.
-  uint32_t NumBytes = 0;
-  for (auto B = Map.begin(), E = Map.end(); B != E; ++B) {
-    NumBytes += B->getKeyLength() + 1;
-  }
-
-  if (auto EC = Writer.writeInteger(NumBytes)) // Number of bytes of string data
+  // The first field is the number of bytes of string data.  We've already been
+  // keeping a running total of this in `Offset`.
+  if (auto EC = Writer.writeInteger(Offset)) // Number of bytes of string data
     return EC;
-  // Now all of the string data itself.
-  for (auto B = Map.begin(), E = Map.end(); B != E; ++B) {
-    if (auto EC = Writer.writeZeroString(B->getKey()))
-      return EC;
-  }
 
-  if (auto EC = Writer.writeInteger(Map.size())) // Hash Size
-    return EC;
-
-  if (auto EC = Writer.writeInteger(Map.size())) // Max Number of Strings
-    return EC;
-
-  if (auto EC = Writer.writeInteger(Map.size())) // Num Present Words
-    return EC;
-
-  // For each entry in the mapping, write a bit mask which represents a bucket
-  // to store it in.  We don't use this, so the value we write isn't important
-  // to us, it just has to be there.
-  for (auto B = Map.begin(), E = Map.end(); B != E; ++B) {
-    if (auto EC = Writer.writeInteger(1U))
+  // Now all of the string data itself.
+  for (auto S : Strings) {
+    if (auto EC = Writer.writeZeroString(S))
       return EC;
   }
 
-  if (auto EC = Writer.writeInteger(0U)) // Num Deleted Words
-    return EC;
-
-  // Mappings of each word.
-  uint32_t OffsetSoFar = 0;
-  for (auto B = Map.begin(), E = Map.end(); B != E; ++B) {
-    // This is a list of key value pairs where the key is the offset into the
-    // strings buffer, and the value is a stream number.  Write each pair.
-    if (auto EC = Writer.writeInteger(OffsetSoFar))
-      return EC;
-
-    if (auto EC = Writer.writeInteger(B->second))
-      return EC;
+  // And finally the Linear Map.
+  if (auto EC = Map.commit(Writer))
 
-    OffsetSoFar += B->getKeyLength() + 1;
-  }
-
   return Error::success();
 }