[LLD] [COFF] Use StringTableBuilder to optimize the string table

[mstorsjo]

Summary

On a statically linked clang.exe, this shrinks the ~17 MB string
table by around 0.5 MB. This adds ~160 ms to the linking time
which originally was around 950 ms.

I've seen an extreme case where the string table would have been
shrunk from 149 MB to 107 MB though. (llvm-objcopy uses
StringTableBuilder, and thus a no-op copy with llvm-objcopy
currently optimizes the string table.)

Given the modest savings (and a noticable slowdown), do you
think is a worthwhile optimization to do, or should we just
keep things as-is?

For cases where -debug:symtab or -debug:dwarf isn't set, the
string table is only used for long section names, where this
shouldn't make any difference at all.

This requires D120676, because with this in place, strings for long
section names can be placed anywhere in the string table, and the
sprintf overflow becomes a real issue in large executables.

[rnk]

The size improvements are entirely from string tail merging, right?

In any case, this looks good to me. Debug info and symbols are sufficiently large that it's worth taking the time to make it smaller where possible.

[mstorsjo]

FWIW, D113866 made the effect of this much smaller, by writing much less unnecessary symbols.

In D120677#3349959, @rnk wrote:

The size improvements are entirely from string tail merging, right?

Yes, tail merging or plain deduplication.

In any case, this looks good to me. Debug info and symbols are sufficiently large that it's worth taking the time to make it smaller where possible.

Ok, I’ll go ahead and push it soon then.

lld/COFF/Writer.cpp

 #include "Symbols.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Timer.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/StringSwitch.h"
+#include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/xxhash.h"
if (c == 0)
       return characteristics < other.characteristics;
     return true;
   }
 };
 
 // The writer writes a SymbolTable result to a file.
 class Writer {
 public:
-  Writer(COFFLinkerContext &c) : buffer(errorHandler().outputBuffer), ctx(c) {}
+  Writer(COFFLinkerContext &c)
+      : buffer(errorHandler().outputBuffer),
+        strtab(StringTableBuilder::WinCOFF), ctx(c) {}
   void run();
 
 private:
   void createSections();
   void createMiscChunks();
   void createImportTables();
   void appendImportThunks();
   void locateImportTables();
private:
   void addSyntheticIdata();
   void fixPartialSectionChars(StringRef name, uint32_t chars);
   bool fixGnuImportChunks();
   void fixTlsAlignment();
   PartialSection *createPartialSection(StringRef name, uint32_t outChars);
   PartialSection *findPartialSection(StringRef name, uint32_t outChars);
 
   llvm::Optional<coff_symbol16> createSymbol(Defined *d);
-  size_t addEntryToStringTable(StringRef str);
 
   OutputSection *findSection(StringRef name);
   void addBaserels();
   void addBaserelBlocks(std::vector<Baserel> &v);
 
   uint32_t getSizeOfInitializedData();
 
   std::unique_ptr<FileOutputBuffer> &buffer;
   std::map<PartialSectionKey, PartialSection *> partialSections;
-  std::vector<char> strtab;
+  StringTableBuilder strtab;
   std::vector<llvm::object::coff_symbol16> outputSymtab;
   IdataContents idata;
   Chunk *importTableStart = nullptr;
   uint64_t importTableSize = 0;
   Chunk *edataStart = nullptr;
   Chunk *edataEnd = nullptr;
   Chunk *iatStart = nullptr;
   uint64_t iatSize = 0;
void Writer::assignOutputSectionIndices() {
   // too.
   for (MergeChunk *mc : ctx.mergeChunkInstances)
     if (mc)
       for (SectionChunk *sc : mc->sections)
         if (sc && sc->live)
           sc->setOutputSectionIdx(mc->getOutputSectionIdx());
 }
 
-size_t Writer::addEntryToStringTable(StringRef str) {
-  assert(str.size() > COFF::NameSize);
-  size_t offsetOfEntry = strtab.size() + 4; // +4 for the size field
-  strtab.insert(strtab.end(), str.begin(), str.end());
-  strtab.push_back('\0');
-  return offsetOfEntry;
-}
-
 Optional<coff_symbol16> Writer::createSymbol(Defined *def) {
   coff_symbol16 sym;
   switch (def->kind()) {
   case Symbol::DefinedAbsoluteKind:
     sym.Value = def->getRVA();
     sym.SectionNumber = IMAGE_SYM_ABSOLUTE;
     break;
   case Symbol::DefinedSyntheticKind:
Optional<coff_symbol16> Writer::createSymbol(Defined *def) {
   // instead. Avoid emitting them to the symbol table, as they can confuse
   // debuggers.
   if (def->isRuntimePseudoReloc)
     return None;
 
   StringRef name = def->getName();
   if (name.size() > COFF::NameSize) {
     sym.Name.Offset.Zeroes = 0;
-    sym.Name.Offset.Offset = addEntryToStringTable(name);
+    sym.Name.Offset.Offset = 0; // Filled in later
+    strtab.add(name);
   } else {
     memset(sym.Name.ShortName, 0, COFF::NameSize);
     memcpy(sym.Name.ShortName, name.data(), name.size());
   }
 
   if (auto *d = dyn_cast<DefinedCOFF>(def)) {
     COFFSymbolRef ref = d->getCOFFSymbol();
     sym.Type = ref.getType();
void Writer::createSymbolAndStringTable() {
   // PE/COFF images are limited to 8 byte section names. Longer names can be
   // supported by writing a non-standard string table, but this string table is
   // not mapped at runtime and the long names will therefore be inaccessible.
   // link.exe always truncates section names to 8 bytes, whereas binutils always
   // preserves long section names via the string table. LLD adopts a hybrid
   // solution where discardable sections have long names preserved and
   // non-discardable sections have their names truncated, to ensure that any
   // section which is mapped at runtime also has its name mapped at runtime.
+  std::vector<OutputSection *> longNameSections;
   for (OutputSection *sec : ctx.outputSections) {
     if (sec->name.size() <= COFF::NameSize)
       continue;
     if ((sec->header.Characteristics & IMAGE_SCN_MEM_DISCARDABLE) == 0)
       continue;
     if (config->warnLongSectionNames) {
       warn("section name " + sec->name +
            " is longer than 8 characters and will use a non-standard string "
            "table");
     }
-    sec->setStringTableOff(addEntryToStringTable(sec->name));
+
+    strtab.add(sec->name);
+    longNameSections.push_back(sec);
   }
 
+  std::vector<std::pair<size_t, StringRef>> longNameSymbols;
   if (config->debugDwarf || config->debugSymtab) {
     for (ObjFile *file : ctx.objFileInstances) {
       for (Symbol *b : file->getSymbols()) {
         auto *d = dyn_cast_or_null<Defined>(b);
         if (!d || d->writtenToSymtab)
           continue;
         d->writtenToSymtab = true;
         if (auto *dc = dyn_cast_or_null<DefinedCOFF>(d)) {
           COFFSymbolRef symRef = dc->getCOFFSymbol();
           if (symRef.isSectionDefinition() ||
               symRef.getStorageClass() == COFF::IMAGE_SYM_CLASS_LABEL)
             continue;
         }
 
-        if (Optional<coff_symbol16> sym = createSymbol(d))
+        if (Optional<coff_symbol16> sym = createSymbol(d)) {
           outputSymtab.push_back(*sym);
+          if (d->getName().size() > COFF::NameSize)
+            longNameSymbols.push_back({outputSymtab.size() - 1, d->getName()});
+        }
       }
     }
   }
 
-  if (outputSymtab.empty() && strtab.empty())
+  strtab.finalize();
+
+  for (OutputSection *sec : longNameSections)
+    sec->setStringTableOff(strtab.getOffset(sec->name));
+
+  for (auto P : longNameSymbols) {
+    coff_symbol16 &sym = outputSymtab[P.first];
+    sym.Name.Offset.Offset = strtab.getOffset(P.second);
+  }
+
+  if (outputSymtab.empty() && strtab.getSize() <= 4)
     return;
 
   // We position the symbol table to be adjacent to the end of the last section.
   uint64_t fileOff = fileSize;
   pointerToSymbolTable = fileOff;
   fileOff += outputSymtab.size() * sizeof(coff_symbol16);
-  fileOff += 4 + strtab.size();
+  fileOff += strtab.getSize();
   fileSize = alignTo(fileOff, config->fileAlign);
 }
 
 void Writer::mergeSections() {
   if (!pdataSec->chunks.empty()) {
     firstPdata = pdataSec->chunks.front();
     lastPdata = pdataSec->chunks.back();
   }
template <typename PEHeaderTy> void Writer::writeHeader() {
   // Write section table
   for (OutputSection *sec : ctx.outputSections) {
     sec->writeHeaderTo(buf);
     buf += sizeof(coff_section);
   }
   sectionTable = ArrayRef<uint8_t>(
       buf - ctx.outputSections.size() * sizeof(coff_section), buf);
 
-  if (outputSymtab.empty() && strtab.empty())
+  if (outputSymtab.empty() && strtab.getSize() <= 4)
     return;
 
   coff->PointerToSymbolTable = pointerToSymbolTable;
   uint32_t numberOfSymbols = outputSymtab.size();
   coff->NumberOfSymbols = numberOfSymbols;
   auto *symbolTable = reinterpret_cast<coff_symbol16 *>(
       buffer->getBufferStart() + coff->PointerToSymbolTable);
   for (size_t i = 0; i != numberOfSymbols; ++i)
     symbolTable[i] = outputSymtab[i];
   // Create the string table, it follows immediately after the symbol table.
   // The first 4 bytes is length including itself.
   buf = reinterpret_cast<uint8_t *>(&symbolTable[numberOfSymbols]);
-  write32le(buf, strtab.size() + 4);
-  if (!strtab.empty())
-    memcpy(buf + 4, strtab.data(), strtab.size());
+  strtab.write(buf);
 }
 
 void Writer::openFile(StringRef path) {
   buffer = CHECK(
       FileOutputBuffer::create(path, fileSize, FileOutputBuffer::F_executable),
       "failed to open " + path);
 }