[PDB] Write public symbol records and the publics hash table

[rnk]

Summary

MSVC link.exe records all external symbol names in the publics stream.
It provides similar functionality to an ELF .symtab.

[ruiu]

lld/COFF/PDB.cpp

558

I think it is a good idea to add this (except the check for isCodeView) as isLive() to SymbolBody class.

570–575

You can remove COFFRef local variable if you change this code to

if (auto *D = dyn_cast<DefinedCOFF>(Def))
  if (D->getCOFFSymbol().isSection())
    return None;

580

and

if (auto *D = dyn_cast<DefinedCOFF>(Def)) {
  if (D->getCOFFSymbol().isFunctionDefinition())
    ...

lld/COFF/SymbolTable.h

113–114

Instead of making this public, I'd define forEachSymbol(std::function<void(Symbol *)> Fn).

[pcc]

Test case?

Also, can we remove the logic to write out the non-standard PE symbol table once this lands?

lld/COFF/PDB.cpp

551

I guess this should talk about PDBs rather than COFF symbol tables.

574

Can section symbols appear in SymbolTable::Symtab? I believe that it only contains external symbols.

609

http://llvm-cs.pcc.me.uk/tools/lld/COFF/SymbolTable.h/rSymtab

It doesn't appear that this can ever be null.

613

Is the WrittenToPDB check necessary? I believe that each symbol should only appear once in SymbolTable::Symtab.

[rnk]

lld/COFF/PDB.cpp

558

Makes sense, will do.

613

True, this is a hold-over from when I iterated each symbol in each object file, like the COFF symbol table generation code does. The nice thing about that approach is that it emits symbols in input file order, whereas I have to do a separate sorting step to keep the output deterministic.

622

I suppose we can use std::sort over std::stable_sort since external names must be unique. We did just take them out of a hash table, after all.

[rnk]

• comments

lld/COFF/PDB.cpp

551

I changed this to check for a valid chunk instead. Absolute and synthetic symbols are a risk here because they may not have chunks, so we cannot get their OutputSection, which means they'll have no SectionIndex.

574

I think not, this must be a hold-over from the object file iteration approach.

[ruiu]

LGTM

lld/COFF/SymbolTable.h

112

Since you are not using Pair.first.val() at least at the moment, pass only Pair.second.

lld/COFF/PDB.cpp

 //===- PDB.cpp ------------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PDB.h"
 #include "Chunks.h"
 #include "Config.h"
 #include "Error.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
+#include "Writer.h"
 #include "llvm/DebugInfo/CodeView/CVDebugRecord.h"
 #include "llvm/DebugInfo/CodeView/DebugSubsectionRecord.h"
 #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/SymbolSerializer.h"
 #include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeDumpVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
 #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFCommon.h"
 #include "llvm/DebugInfo/PDB/GenericError.h"
 #include "llvm/DebugInfo/PDB/Native/DbiModuleDescriptorBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/DbiStream.h"
 #include "llvm/DebugInfo/PDB/Native/DbiStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStream.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/NativeSession.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFileBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
+#include "llvm/DebugInfo/PDB/Native/PublicsStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/PDB.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/FileOutputBuffer.h"
if (Checksums.valid()) {
                                                               FileName));
         NewChecksums->addChecksum(FileName, FC.Kind, FC.Checksum);
       }
       File->ModuleDBI->addDebugSubsection(std::move(NewChecksums));
     }
   }
 }
 
+static Optional<PublicSym32> createPublic(Defined *Def) {
+  // Relative symbols are unrepresentable in a COFF symbol table.
+  // FIXME: Reconsider?
+  if (isa<DefinedSynthetic>(Def) || isa<DefinedAbsolute>(Def))
+    return None;
+
+  // Don't create public symbols for dead symbols or symbols for CodeView
+  // symbols.
+  if (auto *D = dyn_cast<DefinedRegular>(Def)) {
+    if (!D->getChunk()->isLive() || D->getChunk()->isCodeView())
+      return None;
+  } else if (auto *Sym = dyn_cast<DefinedImportData>(Def)) {
+    if (!Sym->File->Live)
+      return None;
+  } else if (auto *Sym = dyn_cast<DefinedImportThunk>(Def)) {
+    if (!Sym->WrappedSym->File->Live)
+      return None;
+  }
+
+  COFFSymbolRef COFFRef;
+  if (auto *D = dyn_cast<DefinedCOFF>(Def)) {
+    COFFRef = D->getCOFFSymbol();
+
+    // Skip section symbols.
+    if (COFFRef.isSection())
+      return None;
+  }
+
+  PublicSym32 Pub(SymbolKind::S_PUB32);
+  Pub.Name = Def->getName();
+  if (isa<DefinedCOFF>(Def) && COFFRef.isFunctionDefinition())
+    Pub.Flags = PublicSymFlags::Function;
+  else if (isa<DefinedImportThunk>(Def))
+    Pub.Flags = PublicSymFlags::Function;
+
+  OutputSection *OS = Def->getChunk()->getOutputSection();
+  assert(OS && "all publics should be in final image");
+  Pub.Offset = Def->getRVA() - OS->getRVA();
+  Pub.Segment = OS->SectionIndex;
+  return Pub;
+}
+
 // Add all object files to the PDB. Merge .debug$T sections into IpiData and
 // TpiData.
 void PDBLinker::addObjectsToPDB() {
   for (ObjectFile *File : Symtab->ObjectFiles)
     addObjectFile(File);
 
   Builder.getStringTableBuilder().setStrings(PDBStrTab);
 
   // Construct TPI stream contents.
   addTypeInfo(Builder.getTpiBuilder(), TypeTable);
 
   // Construct IPI stream contents.
   addTypeInfo(Builder.getIpiBuilder(), IDTable);
 
-  // Add public and symbol records stream.
+  // Compute the public symbols.
+  std::vector<PublicSym32> Publics;
+  for (const auto &Pair : Symtab->Symtab) {
+    if (!Pair.second)
+      continue;
+    SymbolBody *B = Pair.second->body();
+    auto *D = dyn_cast<Defined>(B);
+    if (!D || D->WrittenToPDB)
+      continue;
+    D->WrittenToPDB = true;
+    if (Optional<PublicSym32> Pub = createPublic(D))
+      Publics.push_back(*Pub);
+  }
 
-  // For now we don't actually write any thing useful to the publics stream, but
-  // the act of "getting" it also creates it lazily so that we write an empty
-  // stream.
-  (void)Builder.getPublicsBuilder();
+  if (!Publics.empty()) {
+    // Sort the public symbols and add them to the stream.
+    std::stable_sort(Publics.begin(), Publics.end(),
+                     [](const PublicSym32 &L, const PublicSym32 &R) {
+                       return L.Name < R.Name;
+                     });
+    auto &PublicsBuilder = Builder.getPublicsBuilder();
+    for (const PublicSym32 &Pub : Publics)
+      PublicsBuilder.addPublicSymbol(Pub);
+  }
 }
 
 static void addLinkerModuleSymbols(StringRef Path,
                                    pdb::DbiModuleDescriptorBuilder &Mod,
                                    BumpPtrAllocator &Allocator) {
   codeview::SymbolSerializer Serializer(Allocator, CodeViewContainer::Pdb);
   codeview::ObjNameSym ONS(SymbolRecordKind::ObjNameSym);
   codeview::Compile3Sym CS(SymbolRecordKind::Compile3Sym);

lld/COFF/SymbolTable.h

public:
   void reportDuplicate(Symbol *Existing, InputFile *NewFile);
 
   // A list of chunks which to be added to .rdata.
   std::vector<Chunk *> LocalImportChunks;
 
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
   StringRef findByPrefix(StringRef Prefix);
 
+public:
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> Symtab;
 
+private:
   std::vector<BitcodeFile *> BitcodeFiles;
   std::unique_ptr<BitcodeCompiler> LTO;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace coff
 } // namespace lld
 
 #endif

lld/COFF/Symbols.h

public:
   const Symbol *symbol() const {
     return const_cast<SymbolBody *>(this)->symbol();
   }
 
 protected:
   friend SymbolTable;
   explicit SymbolBody(Kind K, StringRef N = "")
       : SymbolKind(K), IsExternal(true), IsCOMDAT(false),
-        WrittenToSymtab(false), Name(N) {}
+        WrittenToSymtab(false), WrittenToPDB(false), Name(N) {}
 
   const unsigned SymbolKind : 8;
   unsigned IsExternal : 1;
 
   // This bit is used by the \c DefinedRegular subclass.
   unsigned IsCOMDAT : 1;
 
 public:
   // This bit is used by Writer::createSymbolAndStringTable() to prevent
   // symbols from being written to the symbol table more than once.
   unsigned WrittenToSymtab : 1;
 
+  // This bit is used to prevent symbols from being written to the PDB publics
+  // stream more than once.
+  unsigned WrittenToPDB : 1;
+
 protected:
   StringRef Name;
 };
 
 // The base class for any defined symbols, including absolute symbols,
 // etc.
 class Defined : public SymbolBody {
 public:

llvm/include/llvm/DebugInfo/CodeView/SymbolRecord.h

 // S_PUB32
 class PublicSym32 : public SymbolRecord {
 public:
   explicit PublicSym32(SymbolRecordKind Kind) : SymbolRecord(Kind) {}
   explicit PublicSym32(uint32_t RecordOffset)
       : SymbolRecord(SymbolRecordKind::PublicSym32),
         RecordOffset(RecordOffset) {}
 
-  PublicSymFlags Flags;
-  uint32_t Offset;
-  uint16_t Segment;
+  PublicSymFlags Flags = PublicSymFlags::None;
+  uint32_t Offset = 0;
+  uint16_t Segment = 0;
   StringRef Name;
 
-  uint32_t RecordOffset;
+  uint32_t RecordOffset = 0;
 };
 
 // S_REGISTER
 class RegisterSym : public SymbolRecord {
 public:
   explicit RegisterSym(SymbolRecordKind Kind) : SymbolRecord(Kind) {}
   RegisterSym(uint32_t RecordOffset)
       : SymbolRecord(SymbolRecordKind::RegisterSym),

llvm/include/llvm/DebugInfo/PDB/Native/PublicsStreamBuilder.h

 //===- PublicsStreamBuilder.h - PDB Publics Stream Creation -----*- 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_PDBPUBLICSTREAMBUILDER_H
 #define LLVM_DEBUGINFO_PDB_RAW_PDBPUBLICSTREAMBUILDER_H
 
+#include "llvm/DebugInfo/CodeView/SymbolRecord.h"
 #include "llvm/DebugInfo/PDB/Native/RawConstants.h"
 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
+#include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
 #include "llvm/Support/BinaryByteStream.h"
+#include "llvm/Support/BinaryItemStream.h"
 #include "llvm/Support/BinaryStreamRef.h"
 #include "llvm/Support/BinaryStreamWriter.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 
 namespace llvm {
+
+template <> struct BinaryItemTraits<codeview::CVSymbol> {
+  static size_t length(const codeview::CVSymbol &Item) {
+    return Item.RecordData.size();
+  }
+  static ArrayRef<uint8_t> bytes(const codeview::CVSymbol &Item) {
+    return Item.RecordData;
+  }
+};
+
 namespace msf {
 class MSFBuilder;
 }
 namespace pdb {
 class PublicsStream;
 struct PublicsStreamHeader;
 
+struct GSIHashTableBuilder {
+  void addSymbols(ArrayRef<codeview::CVSymbol> Symbols);
+
+  std::vector<PSHashRecord> HashRecords;
+  std::array<support::ulittle32_t, (IPHR_HASH + 32) / 32> HashBitmap;
+  std::vector<support::ulittle32_t> HashBuckets;
+};
+
 class PublicsStreamBuilder {
 public:
   explicit PublicsStreamBuilder(msf::MSFBuilder &Msf);
   ~PublicsStreamBuilder();
 
   PublicsStreamBuilder(const PublicsStreamBuilder &) = delete;
   PublicsStreamBuilder &operator=(const PublicsStreamBuilder &) = delete;
 
   Error finalizeMsfLayout();
   uint32_t calculateSerializedLength() const;
 
-  Error commit(BinaryStreamWriter &PublicsWriter);
+  Error commit(BinaryStreamWriter &PublicsWriter,
+               BinaryStreamWriter &RecWriter);
 
   uint32_t getStreamIndex() const { return StreamIdx; }
   uint32_t getRecordStreamIdx() const { return RecordStreamIdx; }
 
+  void addPublicSymbol(const codeview::PublicSym32 &Pub);
+
 private:
   uint32_t StreamIdx = kInvalidStreamIndex;
   uint32_t RecordStreamIdx = kInvalidStreamIndex;
-  std::vector<PSHashRecord> HashRecords;
+  std::unique_ptr<GSIHashTableBuilder> Table;
+  std::vector<codeview::CVSymbol> Publics;
   msf::MSFBuilder &Msf;
 };
 } // namespace pdb
 } // namespace llvm
 
 #endif

llvm/lib/DebugInfo/PDB/Native/DbiModuleDescriptorBuilder.cpp

 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/BinaryFormat/COFF.h"
 #include "llvm/DebugInfo/CodeView/DebugSubsectionRecord.h"
 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFCommon.h"
 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
 #include "llvm/DebugInfo/PDB/Native/DbiModuleDescriptor.h"
+#include "llvm/DebugInfo/PDB/Native/PublicsStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/RawConstants.h"
 #include "llvm/DebugInfo/PDB/Native/RawError.h"
 #include "llvm/Support/BinaryItemStream.h"
 #include "llvm/Support/BinaryStreamWriter.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
 using namespace llvm::msf;
 using namespace llvm::pdb;
 
-namespace llvm {
-template <> struct BinaryItemTraits<CVSymbol> {
-  static size_t length(const CVSymbol &Item) { return Item.RecordData.size(); }
-
-  static ArrayRef<uint8_t> bytes(const CVSymbol &Item) {
-    return Item.RecordData;
-  }
-};
-}
-
 static uint32_t calculateDiSymbolStreamSize(uint32_t SymbolByteSize,
                                             uint32_t C13Size) {
   uint32_t Size = sizeof(uint32_t);   // Signature
   Size += alignTo(SymbolByteSize, 4); // Symbol Data
   Size += 0;                          // TODO: Layout.C11Bytes
   Size += C13Size;                    // C13 Debug Info Size
   Size += sizeof(uint32_t);           // GlobalRefs substream size (always 0)
   Size += 0;                          // GlobalRefs substream bytes

llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

Error PDBFileBuilder::commit(StringRef Filename) {
   if (Ipi) {
     if (auto EC = Ipi->commit(Layout, Buffer))
       return EC;
   }
 
   if (Publics) {
     auto PS = WritableMappedBlockStream::createIndexedStream(
         Layout, Buffer, Publics->getStreamIndex(), Allocator);
+    auto PRS = WritableMappedBlockStream::createIndexedStream(
+        Layout, Buffer, Publics->getRecordStreamIdx(), Allocator);
     BinaryStreamWriter PSWriter(*PS);
-    if (auto EC = Publics->commit(PSWriter))
+    BinaryStreamWriter RecWriter(*PRS);
+    if (auto EC = Publics->commit(PSWriter, RecWriter))
       return EC;
   }
 
   return Buffer.commit();
 }

llvm/lib/DebugInfo/PDB/Native/PublicsStreamBuilder.cpp

 //===- DbiStreamBuilder.cpp - PDB Dbi Stream Creation -----------*- 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/Native/PublicsStreamBuilder.h"
+#include "llvm/DebugInfo/CodeView/SymbolRecord.h"
+#include "llvm/DebugInfo/CodeView/SymbolSerializer.h"
 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFCommon.h"
 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
+#include "llvm/DebugInfo/PDB/Native/Hash.h"
+#include "llvm/Support/BinaryItemStream.h"
+#include "llvm/Support/BinaryStreamWriter.h"
+#include <algorithm>
+#include <vector>
 
 using namespace llvm;
 using namespace llvm::msf;
 using namespace llvm::pdb;
+using namespace llvm::codeview;
 
-PublicsStreamBuilder::PublicsStreamBuilder(msf::MSFBuilder &Msf) : Msf(Msf) {}
+PublicsStreamBuilder::PublicsStreamBuilder(msf::MSFBuilder &Msf)
+    : Table(new GSIHashTableBuilder), Msf(Msf) {}
 
 PublicsStreamBuilder::~PublicsStreamBuilder() {}
 
 uint32_t PublicsStreamBuilder::calculateSerializedLength() const {
   uint32_t Size = 0;
   Size += sizeof(PublicsStreamHeader);
   Size += sizeof(GSIHashHeader);
-  Size += HashRecords.size() * sizeof(PSHashRecord);
-  size_t BitmapSizeInBits = alignTo(IPHR_HASH + 1, 32);
-  uint32_t NumBitmapEntries = BitmapSizeInBits / 8;
-  Size += NumBitmapEntries;
-
-  // FIXME: Account for hash buckets.  For now since we we write a zero-bitmap
-  // indicating that no hash buckets are valid, we also write zero byets of hash
-  // bucket data.
-  Size += 0;
+  Size += Table->HashRecords.size() * sizeof(PSHashRecord);
+  Size += Table->HashBitmap.size() * sizeof(uint32_t);
+  Size += Table->HashBuckets.size() * sizeof(uint32_t);
+
+  Size += Publics.size() * sizeof(uint32_t); // AddrMap
+
+  // FIXME: Add thunk map and section offsets for incremental linking.
+
   return Size;
 }
 
 Error PublicsStreamBuilder::finalizeMsfLayout() {
+  Table->addSymbols(Publics);
+
   Expected<uint32_t> Idx = Msf.addStream(calculateSerializedLength());
   if (!Idx)
     return Idx.takeError();
   StreamIdx = *Idx;
 
-  Expected<uint32_t> RecordIdx = Msf.addStream(0);
+  uint32_t PublicRecordBytes = 0;
+  for (auto &Pub : Publics)
+    PublicRecordBytes += Pub.length();
+
+  Expected<uint32_t> RecordIdx = Msf.addStream(PublicRecordBytes);
   if (!RecordIdx)
     return RecordIdx.takeError();
   RecordStreamIdx = *RecordIdx;
   return Error::success();
 }
 
-Error PublicsStreamBuilder::commit(BinaryStreamWriter &PublicsWriter) {
+void PublicsStreamBuilder::addPublicSymbol(const PublicSym32 &Pub) {
+  Publics.push_back(SymbolSerializer::writeOneSymbol(
+      const_cast<PublicSym32 &>(Pub), Msf.getAllocator(),
+      CodeViewContainer::Pdb));
+}
+
+// FIXME: Put this back in the header.
+struct PubSymLayout {
+  ulittle16_t reclen;
+  ulittle16_t reckind;
+  ulittle32_t flags;
+  ulittle32_t off;
+  ulittle16_t seg;
+  char name[1];
+};
+
+bool comparePubSymByAddrAndName(const CVSymbol *LS, const CVSymbol *RS) {
+  assert(LS->length() > sizeof(PubSymLayout) &&
+         RS->length() > sizeof(PubSymLayout));
+  auto *L = reinterpret_cast<const PubSymLayout *>(LS->data().data());
+  auto *R = reinterpret_cast<const PubSymLayout *>(RS->data().data());
+  if (L->seg < R->seg)
+    return true;
+  if (L->seg > R->seg)
+    return false;
+  if (L->off < R->off)
+    return true;
+  if (L->off > R->off)
+    return false;
+  return strcmp(L->name, R->name) < 0;
+}
+
+static StringRef getSymbolName(const CVSymbol &Sym) {
+  assert(Sym.kind() == S_PUB32 && "handle other kinds");
+  ArrayRef<uint8_t> NameBytes =
+      Sym.data().drop_front(offsetof(PubSymLayout, name));
+  return StringRef(reinterpret_cast<const char *>(NameBytes.data()),
+                   NameBytes.size())
+      .trim('\0');
+}
+
+/// Compute the address map. The address map is an array of symbol offsets
+/// sorted so that it can be binary searched by address.
+static std::vector<ulittle32_t> computeAddrMap(ArrayRef<CVSymbol> Publics) {
+  // Make a vector of pointers to the symbols so we can sort it by address.
+  // Also gather the symbol offsets while we're at it.
+  std::vector<const CVSymbol *> PublicsByAddr;
+  std::vector<uint32_t> SymOffsets;
+  PublicsByAddr.reserve(Publics.size());
+  uint32_t SymOffset = 0;
+  for (const CVSymbol &Sym : Publics) {
+    PublicsByAddr.push_back(&Sym);
+    SymOffsets.push_back(SymOffset);
+    SymOffset += Sym.length();
+  }
+  std::stable_sort(PublicsByAddr.begin(), PublicsByAddr.end(),
+                   comparePubSymByAddrAndName);
+
+  // Fill in the symbol offsets in the appropriate order.
+  std::vector<ulittle32_t> AddrMap;
+  AddrMap.reserve(Publics.size());
+  for (const CVSymbol *Sym : PublicsByAddr) {
+    ptrdiff_t Idx = std::distance(Publics.data(), Sym);
+    assert(Idx >= 0 && size_t(Idx) < Publics.size());
+    AddrMap.push_back(ulittle32_t(SymOffsets[Idx]));
+  }
+  return AddrMap;
+}
+
+Error PublicsStreamBuilder::commit(BinaryStreamWriter &PublicsWriter,
+                                   BinaryStreamWriter &RecWriter) {
+  assert(Table->HashRecords.size() == Publics.size());
+
   PublicsStreamHeader PSH;
   GSIHashHeader GSH;
 
-  // FIXME: Figure out what to put for these values.
-  PSH.AddrMap = 0;
-  PSH.ISectThunkTable = 0;
-  PSH.NumSections = 0;
+  PSH.AddrMap = Publics.size() * 4;
+
+  // FIXME: Fill these in. They are for incremental linking.
   PSH.NumThunks = 0;
-  PSH.OffThunkTable = 0;
   PSH.SizeOfThunk = 0;
-  PSH.SymHash = 0;
+  PSH.ISectThunkTable = 0;
+  PSH.OffThunkTable = 0;
+  PSH.NumSections = 0;
 
   GSH.VerSignature = GSIHashHeader::HdrSignature;
   GSH.VerHdr = GSIHashHeader::HdrVersion;
-  GSH.HrSize = 0;
-  GSH.NumBuckets = 0;
+  GSH.HrSize = Table->HashRecords.size() * sizeof(PSHashRecord);
+  GSH.NumBuckets = Table->HashBitmap.size() * 4 + Table->HashBuckets.size() * 4;
+
+  PSH.SymHash = sizeof(GSH) + GSH.HrSize + GSH.NumBuckets;
 
   if (auto EC = PublicsWriter.writeObject(PSH))
     return EC;
   if (auto EC = PublicsWriter.writeObject(GSH))
     return EC;
-  if (auto EC = PublicsWriter.writeArray(makeArrayRef(HashRecords)))
+
+  if (auto EC = PublicsWriter.writeArray(makeArrayRef(Table->HashRecords)))
+    return EC;
+  if (auto EC = PublicsWriter.writeArray(makeArrayRef(Table->HashBitmap)))
+    return EC;
+  if (auto EC = PublicsWriter.writeArray(makeArrayRef(Table->HashBuckets)))
+    return EC;
+
+  std::vector<ulittle32_t> AddrMap = computeAddrMap(Publics);
+  if (auto EC = PublicsWriter.writeArray(makeArrayRef(AddrMap)))
     return EC;
 
-  size_t BitmapSizeInBits = alignTo(IPHR_HASH + 1, 32);
-  uint32_t NumBitmapEntries = BitmapSizeInBits / 8;
-  std::vector<uint8_t> BitmapData(NumBitmapEntries);
-  // FIXME: Build an actual bitmap
-  if (auto EC = PublicsWriter.writeBytes(makeArrayRef(BitmapData)))
+  BinaryItemStream<CVSymbol> Records(support::endianness::little);
+  Records.setItems(Publics);
+  BinaryStreamRef RecordsRef(Records);
+  if (auto EC = RecWriter.writeStreamRef(RecordsRef))
     return EC;
 
-  // FIXME: Write actual hash buckets.
   return Error::success();
 }
+
+void GSIHashTableBuilder::addSymbols(ArrayRef<CVSymbol> Symbols) {
+  std::array<std::vector<PSHashRecord>, IPHR_HASH + 1> TmpBuckets;
+  uint32_t SymOffset = 0;
+  for (const CVSymbol &Sym : Symbols) {
+    PSHashRecord HR;
+    // Add one when writing symbol offsets to disk. See GSI1::fixSymRecs.
+    HR.Off = SymOffset + 1;
+    HR.CRef = 1; // Always use a refcount of 1.
+
+    // Hash the name to figure out which bucket this goes into.
+    StringRef Name = getSymbolName(Sym);
+    size_t BucketIdx = hashStringV1(Name) % IPHR_HASH;
+    TmpBuckets[BucketIdx].push_back(HR); // FIXME: Does order matter?
+
+    SymOffset += Sym.length();
+  }
+
+  // Compute the three tables: the hash records in bucket and chain order, the
+  // bucket presence bitmap, and the bucket chain start offsets.
+  HashRecords.reserve(Symbols.size());
+  for (size_t BucketIdx = 0; BucketIdx < IPHR_HASH + 1; ++BucketIdx) {
+    auto &Bucket = TmpBuckets[BucketIdx];
+    if (Bucket.empty())
+      continue;
+    HashBitmap[BucketIdx / 32] |= 1U << (BucketIdx % 32);
+
+    // Calculate what the offset of the first hash record in the chain would be
+    // if it were inflated to contain 32-bit pointers. On a 32-bit system, each
+    // record would be 12 bytes. See HROffsetCalc in gsi.h.
+    const int SizeOfHROffsetCalc = 12;
+    ulittle32_t ChainStartOff =
+        ulittle32_t(HashRecords.size() * SizeOfHROffsetCalc);
+    HashBuckets.push_back(ChainStartOff);
+    for (const auto &HR : Bucket)
+      HashRecords.push_back(HR);
+  }
+}