[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 ↗

(On Diff #108196)

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

570–575 ↗

(On Diff #108196)

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 ↗

(On Diff #108196)

and

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

lld/COFF/SymbolTable.h

113–114 ↗

(On Diff #108196)

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 ↗

(On Diff #108196)

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

574 ↗

(On Diff #108196)

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

609 ↗

(On Diff #108196)

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

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

613 ↗

(On Diff #108196)

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

[rnk]

lld/COFF/PDB.cpp

558 ↗

(On Diff #108196)

Makes sense, will do.

613 ↗

(On Diff #108196)

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 ↗

(On Diff #108196)

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 ↗

(On Diff #108196)

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 ↗

(On Diff #108196)

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

[ruiu]

LGTM

lld/COFF/SymbolTable.h

112 ↗

(On Diff #108327)

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

lld/trunk/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 PublicSym32 createPublic(Defined *Def) {
+  PublicSym32 Pub(SymbolKind::S_PUB32);
+  Pub.Name = Def->getName();
+  if (auto *D = dyn_cast<DefinedCOFF>(Def)) {
+    if (D->getCOFFSymbol().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 (ObjFile *File : ObjFile::Instances)
     addObjFile(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;
+  Symtab->forEachSymbol([&Publics](Symbol *S) {
+    // Only emit defined, live symbols that have a chunk.
+    auto *Def = dyn_cast<Defined>(S->body());
+    if (Def && Def->isLive() && Def->getChunk())
+      Publics.push_back(createPublic(Def));
+  });
 
-  // 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::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/trunk/COFF/SymbolTable.h

public:
   Symbol *addImportThunk(StringRef Name, DefinedImportData *S,
                          uint16_t Machine);
 
   void reportDuplicate(Symbol *Existing, InputFile *NewFile);
 
   // A list of chunks which to be added to .rdata.
   std::vector<Chunk *> LocalImportChunks;
 
+  // Iterates symbols in non-determinstic hash table order.
+  template <typename T> void forEachSymbol(T Callback) {
+    for (auto &Pair : Symtab)
+      Callback(Pair.second);
+  }
+
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
   StringRef findByPrefix(StringRef Prefix);
 
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> Symtab;
   std::unique_ptr<BitcodeCompiler> LTO;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace coff
 } // namespace lld
 
 #endif

lld/trunk/COFF/Symbols.h

public:
   bool isExternal() { return IsExternal; }
 
   // Returns the symbol name.
   StringRef getName();
 
   // Returns the file from which this symbol was created.
   InputFile *getFile();
 
+  // Indicates that this symbol will be included in the final image. Only valid
+  // after calling markLive.
+  bool isLive() const;
+
   Symbol *symbol();
   const Symbol *symbol() const {
     return const_cast<SymbolBody *>(this)->symbol();
   }
 
 protected:
   friend SymbolTable;
   explicit SymbolBody(Kind K, StringRef N = "")
DefinedRegular(InputFile *F, StringRef N, bool IsCOMDAT,
     this->IsExternal = IsExternal;
     this->IsCOMDAT = IsCOMDAT;
   }
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedRegularKind;
   }
 
-  uint64_t getRVA() { return (*Data)->getRVA() + Sym->Value; }
-  bool isCOMDAT() { return IsCOMDAT; }
-  SectionChunk *getChunk() { return *Data; }
-  uint32_t getValue() { return Sym->Value; }
+  uint64_t getRVA() const { return (*Data)->getRVA() + Sym->Value; }
+  bool isCOMDAT() const { return IsCOMDAT; }
+  SectionChunk *getChunk() const { return *Data; }
+  uint32_t getValue() const { return Sym->Value; }
 
 private:
   SectionChunk **Data;
 };
 
 class DefinedCommon : public DefinedCOFF {
 public:
   DefinedCommon(InputFile *F, StringRef N, uint64_t Size,

lld/trunk/COFF/Symbols.cpp

 InputFile *SymbolBody::getFile() {
   if (auto *Sym = dyn_cast<DefinedCOFF>(this))
     return Sym->File;
   if (auto *Sym = dyn_cast<Lazy>(this))
     return Sym->File;
   return nullptr;
 }
 
+bool SymbolBody::isLive() const {
+  if (auto *R = dyn_cast<DefinedRegular>(this))
+    return R->getChunk()->isLive();
+  if (auto *Imp = dyn_cast<DefinedImportData>(this))
+    return Imp->File->Live;
+  if (auto *Imp = dyn_cast<DefinedImportThunk>(this))
+    return Imp->WrappedSym->File->Live;
+  // Assume any other kind of symbol is live.
+  return true;
+}
+
 COFFSymbolRef DefinedCOFF::getCOFFSymbol() {
   size_t SymSize = cast<ObjFile>(File)->getCOFFObj()->getSymbolTableEntrySize();
   if (SymSize == sizeof(coff_symbol16))
     return COFFSymbolRef(reinterpret_cast<const coff_symbol16 *>(Sym));
   assert(SymSize == sizeof(coff_symbol32));
   return COFFSymbolRef(reinterpret_cast<const coff_symbol32 *>(Sym));
 }
 

lld/trunk/COFF/Writer.cpp

size_t Writer::addEntryToStringTable(StringRef Str) {
   return OffsetOfEntry;
 }
 
 Optional<coff_symbol16> Writer::createSymbol(Defined *Def) {
   // Relative symbols are unrepresentable in a COFF symbol table.
   if (isa<DefinedSynthetic>(Def))
     return None;
 
-  if (auto *D = dyn_cast<DefinedRegular>(Def)) {
-    // Don't write dead symbols or symbols in codeview sections to the symbol
-    // table.
-    if (!D->getChunk()->isLive() || D->getChunk()->isCodeView())
-      return None;
-  }
-
-  if (auto *Sym = dyn_cast<DefinedImportData>(Def))
-    if (!Sym->File->Live)
-      return None;
-
-  if (auto *Sym = dyn_cast<DefinedImportThunk>(Def))
-    if (!Sym->WrappedSym->File->Live)
+  if (!Def->isLive())
+  if (auto *D = dyn_cast<DefinedRegular>(Def))
+    if (D->getChunk()->isCodeView())
       return None;
 
   coff_symbol16 Sym;
   StringRef Name = Def->getName();
   if (Name.size() > COFF::NameSize) {
     Sym.Name.Offset.Zeroes = 0;
     Sym.Name.Offset.Offset = addEntryToStringTable(Name);
   } else {

lld/trunk/test/COFF/pdb-import-gc.yaml

 # RUN: yaml2obj %s -o %t.obj
 # RUN: lld-link %t.obj %S/Inputs/pdb-import-gc.lib -debug -entry:main \
 # RUN:          -nodefaultlib -debug -out:%t.exe -pdb:%t.pdb
-# RUN: llvm-pdbutil dump -symbols %t.pdb | FileCheck %s
+# RUN: llvm-pdbutil dump -publics -symbols %t.pdb | FileCheck %s
 
 # This tests the case where an __imp_ chunk is discarded by linker GC. The debug
 # info may refer to the __imp_ symbol still.
 
 # Compile this code with MSVC to regenerate the test case:
 #   extern char __declspec(dllimport) __wc_mb_cur;
 #   int discarded() { return __wc_mb_cur; }
 #   int main() { return g2; }

lld/trunk/test/COFF/pdb-publics-import.test

+Make a DLL that exports a few functions, then make a DLL with PDBs that imports
+them. Check that the __imp_ pointer and the generated thunks appear in the
+publics stream.
+
+RUN: yaml2obj < %p/Inputs/export.yaml > %t1.obj
+RUN: lld-link /out:%t1.dll /dll %t1.obj /implib:%t1.lib \
+RUN:   /export:exportfn1 /export:exportfn2
+RUN: yaml2obj < %p/Inputs/import.yaml > %t2.obj
+RUN: lld-link /out:%t2.exe /pdb:%t2.pdb /debug /entry:main %t2.obj %t1.lib
+RUN: llvm-pdbutil dump %t2.pdb -publics | FileCheck %s
+
+CHECK:                             Public Symbols
+CHECK-NEXT: ============================================================
+CHECK-NEXT:      112 | S_PUB32 [size = 20] `main`
+CHECK-NEXT:            flags = function, addr = 0001:0000
+CHECK-NEXT:       64 | S_PUB32 [size = 24] `exportfn1`
+CHECK-NEXT:            flags = function, addr = 0001:0016
+CHECK-NEXT:       88 | S_PUB32 [size = 24] `exportfn2`
+CHECK-NEXT:            flags = function, addr = 0001:0032
+CHECK-NEXT:       32 | S_PUB32 [size = 32] `__imp_exportfn2`
+CHECK-NEXT:            flags = none, addr = 0003:0072
+CHECK-NEXT:        0 | S_PUB32 [size = 32] `__imp_exportfn1`
+CHECK-NEXT:            flags = none, addr = 0003:0064

lld/trunk/test/COFF/pdb.test

 # RUN: yaml2obj < %p/Inputs/pdb1.yaml > %t1.obj
 # RUN: yaml2obj < %p/Inputs/pdb2.yaml > %t2.obj
 # RUN: lld-link /debug /pdb:%t.pdb /dll /out:%t.dll /entry:main /nodefaultlib \
 # RUN:   %t1.obj %t2.obj
 
 # RUN: llvm-pdbutil pdb2yaml -stream-metadata -stream-directory -pdb-stream \
 # RUN:   -dbi-stream -ipi-stream -tpi-stream %t.pdb | FileCheck %s
 
 # RUN: llvm-pdbutil dump -modules -section-map -section-contribs \
-# RUN:   -types -ids -type-extras -id-extras %t.pdb | FileCheck -check-prefix RAW %s
+# RUN:   -publics -public-extras -types -ids -type-extras -id-extras %t.pdb \
+# RUN:   | FileCheck -check-prefix RAW %s
 
 # CHECK:      MSF:
 # CHECK-NEXT:   SuperBlock:
 # CHECK-NEXT:     BlockSize:       4096
 # CHECK-NEXT:     FreeBlockMap:    1
 # CHECK-NEXT:     NumBlocks:
 # CHECK-NEXT:     NumDirectoryBytes:
 # CHECK-NEXT:     Unknown1:        0

 RAW-NEXT:            0x1006: ` -I"C:\Program Files (x86)\Windows Kits\8.1\include\um" -I"C:\Program Files (x86)\Windows Kits\8.1\include\winrt" -TC -X`
 RAW-NEXT:   0x100A | LF_STRING_ID [size = 20, hash = 0x39C] ID: <no type>, String: ret42-sub.c
 RAW-NEXT:   0x100B | LF_BUILDINFO [size = 28, hash = 0xAD7]
 RAW-NEXT:            0x1002: `D:\b`
 RAW-NEXT:            0x1003: `C:\vs14\VC\BIN\amd64\cl.exe`
 RAW-NEXT:            0x100A: `ret42-sub.c`
 RAW-NEXT:            0x1008: `D:\b\vc140.pdb`
 RAW-NEXT:            0x1006: ` -I"C:\Program Files (x86)\Windows Kits\8.1\include\um" -I"C:\Program Files (x86)\Windows Kits\8.1\include\winrt" -TC -X`
+RAW:                            Public Symbols
+RAW-NEXT:============================================================
+RAW-NEXT:      20 | S_PUB32 [size = 20] `main`
+RAW-NEXT:           flags = function, addr = 0002:0000
+RAW-NEXT:       0 | S_PUB32 [size = 20] `foo`
+RAW-NEXT:           flags = function, addr = 0002:0016
+RAW-NOT: S_PUB32
+RAW-NEXT:  Hash Records
+RAW-NEXT:    off = 21, refcnt = 1
+RAW-NEXT:    off = 1, refcnt = 1
+RAW-NEXT:  Hash Buckets
+RAW-NEXT:    0x00000000
+RAW-NEXT:    0x0000000c
+RAW-NEXT:  Address Map
+RAW-NEXT:    off = 20
+RAW-NEXT:    off = 0
 RAW:                        Section Contributions
 RAW-NEXT: ============================================================
 RAW-NEXT:   SC  | mod = 0, 65535:1288, size = 14, data crc = 0, reloc crc = 0
 RAW-NEXT:         IMAGE_SCN_CNT_CODE | IMAGE_SCN_ALIGN_16BYTES | IMAGE_SCN_MEM_EXECUTE |
 RAW-NEXT:         IMAGE_SCN_MEM_READ
 RAW-NEXT:   SC  | mod = 0, 65535:1312, size = 8, data crc = 0, reloc crc = 0
 RAW-NEXT:         IMAGE_SCN_CNT_INITIALIZED_DATA | IMAGE_SCN_ALIGN_4BYTES | IMAGE_SCN_MEM_READ
 RAW-NEXT:   SC  | mod = 0, 65535:1320, size = 12, data crc = 0, reloc crc = 0

llvm/trunk/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/trunk/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/trunk/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/trunk/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/trunk/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);
+  }
+}