Reduce memory usage when creating .gdb_index. NFC.

[ruiu]

Summary

.gdb_index sections can be very large. When you are compiling
multi-gibibyte executables, they can be larger than 1 GiB. The previous
implementation of .gdb_index seems to consume too much memory.

This patch is to reduce the memory consumption by eliminating temporary
objects.

[ruiu]

This change reduces memory consumption of the GdbIndexSection when creating a 1350 GiB .gdb_index from 932 MiB to 261 MiB.

[ruiu]

• rebased

[grimar]

Looks good. It feels this change can be split into several smaller changes though.
I would do that for committing.

lld/ELF/SyntheticSections.cpp

2221

This can be a separate change.

2345

This can be a separate NFC.

2357

Seems this part can be a separate little change too.

2391

You are assuming at line 2475 that buffer is filled with zeroes. I think you can omit this line then.

[ruiu]

lld/ELF/SyntheticSections.cpp

2391

Ah, good point. I've never thought of it, but that's true.

lld/ELF/SyntheticSections.h

struct GdbIndexChunk {
 
   struct CuEntry {
     uint64_t CuOffset;
     uint64_t CuLength;
   };
 
   struct NameTypeEntry {
     llvm::CachedHashStringRef Name;
-    uint8_t Type;
+    uint32_t Type;
   };
 
   InputSection *DebugInfoSec;
   std::vector<AddressEntry> AddressAreas;
   std::vector<CuEntry> CompilationUnits;
   std::vector<NameTypeEntry> NamesAndTypes;
 };
 
 // The symbol type for the .gdb_index section.
 struct GdbSymbol {
-  uint32_t NameHash;
-  size_t NameOffset;
-  size_t CuVectorIndex;
+  llvm::CachedHashStringRef Name;
+  size_t OutputOff;
+  size_t CuVectorIdx;
 };
 
 class GdbIndexSection final : public SyntheticSection {
 public:
   GdbIndexSection(std::vector<GdbIndexChunk> &&Chunks);
   void writeTo(uint8_t *Buf) override;
   size_t getSize() const override;
   bool empty() const override;
 
 private:
-  void fixCuIndex();
-  std::vector<std::vector<uint32_t>> createCuVectors();
-  std::vector<GdbSymbol *> createGdbSymtab();
-
   // A symbol table for this .gdb_index section.
-  std::vector<GdbSymbol *> GdbSymtab;
+  std::vector<GdbSymbol> Symbols;
 
   // CU vector is a part of constant pool area of section.
   std::vector<std::vector<uint32_t>> CuVectors;
 
-  // Symbol table contents.
-  llvm::DenseMap<llvm::CachedHashStringRef, GdbSymbol *> Symbols;
-
   // Each chunk contains information gathered from a debug sections of single
   // object and used to build different areas of gdb index.
   std::vector<GdbIndexChunk> Chunks;
 
   static constexpr uint32_t CuListOffset = 24;
   uint32_t CuTypesOffset;
   uint32_t SymtabOffset;
+  uint32_t SymtabSize = 0;
   uint32_t ConstantPoolOffset;
+  uint32_t ConstantPoolSize = 0;
   uint32_t StringPoolOffset;
-  uint32_t StringPoolSize;
+  uint32_t StringPoolSize = 0;
 
   std::vector<size_t> CuVectorOffsets;
 };
 
 template <class ELFT> GdbIndexSection *createGdbIndex();
 
 // --eh-frame-hdr option tells linker to construct a header for all the
 // .eh_frame sections. This header is placed to a section named .eh_frame_hdr

lld/ELF/SyntheticSections.cpp

 using namespace llvm::dwarf;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support;
 
 using namespace lld;
 using namespace lld::elf;
 
+using llvm::support::endian::read32le;
 using llvm::support::endian::write32le;
 using llvm::support::endian::write64le;
 
 constexpr size_t MergeNoTailSection::NumShards;
 
 // Returns an LLD version string.
 static ArrayRef<uint8_t> getVersion() {
   // Check LLD_VERSION first for ease of testing.
for (DWARFAddressRange &R : Ranges) {
       Ret.push_back({IS, R.LowPC - Offset, R.HighPC - Offset, CuIdx});
     }
     ++CuIdx;
   }
   return Ret;
 }
 
 static std::vector<GdbIndexChunk::NameTypeEntry>
-readPubNamesAndTypes(DWARFContext &Dwarf) {
+readPubNamesAndTypes(DWARFContext &Dwarf, uint32_t Idx) {
   StringRef Sec1 = Dwarf.getDWARFObj().getGnuPubNamesSection();
   StringRef Sec2 = Dwarf.getDWARFObj().getGnuPubTypesSection();
 
   std::vector<GdbIndexChunk::NameTypeEntry> Ret;
   for (StringRef Sec : {Sec1, Sec2}) {
     DWARFDebugPubTable Table(Sec, Config->IsLE, true);
-    for (const DWARFDebugPubTable::Set &Set : Table.getData()) {
-      for (const DWARFDebugPubTable::Entry &Ent : Set.Entries) {
-        CachedHashStringRef S(Ent.Name, computeGdbHash(Ent.Name));
-        Ret.push_back({S, Ent.Descriptor.toBits()});
-      }
-    }
+    for (const DWARFDebugPubTable::Set &Set : Table.getData())
+      for (const DWARFDebugPubTable::Entry &Ent : Set.Entries)
+        Ret.push_back({{Ent.Name, computeGdbHash(Ent.Name)},
+                       (Ent.Descriptor.toBits() << 24) | Idx});
   }
   return Ret;
 }
 
 static std::vector<InputSection *> getDebugInfoSections() {
   std::vector<InputSection *> Ret;
   for (InputSectionBase *S : InputSections)
     if (InputSection *IS = dyn_cast<InputSection>(S))
       if (IS->Name == ".debug_info")
         Ret.push_back(IS);
   return Ret;
 }
 
-void GdbIndexSection::fixCuIndex() {
-  uint32_t Idx = 0;
-  for (GdbIndexChunk &Chunk : Chunks) {
-    for (GdbIndexChunk::AddressEntry &Ent : Chunk.AddressAreas)
-      Ent.CuIndex += Idx;
-    Idx += Chunk.CompilationUnits.size();
-  }
-}
-
-std::vector<std::vector<uint32_t>> GdbIndexSection::createCuVectors() {
-  std::vector<std::vector<uint32_t>> Ret;
-  uint32_t Idx = 0;
-  uint32_t Off = 0;
-
-  for (GdbIndexChunk &Chunk : Chunks) {
-    for (GdbIndexChunk::NameTypeEntry &Ent : Chunk.NamesAndTypes) {
-      GdbSymbol *&Sym = Symbols[Ent.Name];
-      if (!Sym) {
-        Sym = make<GdbSymbol>(GdbSymbol{Ent.Name.hash(), Off, Ret.size()});
-        Off += Ent.Name.size() + 1;
-        Ret.push_back({});
-      }
-
-      // gcc 5.4.1 produces a buggy .debug_gnu_pubnames that contains
-      // duplicate entries, so we want to dedup them.
-      std::vector<uint32_t> &Vec = Ret[Sym->CuVectorIndex];
-      uint32_t Val = (Ent.Type << 24) | Idx;
-      if (Vec.empty() || Vec.back() != Val)
-        Vec.push_back(Val);
-    }
-    Idx += Chunk.CompilationUnits.size();
-  }
-
-  StringPoolSize = Off;
-  return Ret;
-}
-
 template <class ELFT> GdbIndexSection *elf::createGdbIndex() {
   // Gather debug info to create a .gdb_index section.
   std::vector<InputSection *> Sections = getDebugInfoSections();
   std::vector<GdbIndexChunk> Chunks(Sections.size());
 
   parallelForEachN(0, Chunks.size(), [&](size_t I) {
     ObjFile<ELFT> *File = Sections[I]->getFile<ELFT>();
     DWARFContext Dwarf(make_unique<LLDDwarfObj<ELFT>>(File));
 
     Chunks[I].DebugInfoSec = Sections[I];
     Chunks[I].CompilationUnits = readCuList(Dwarf);
     Chunks[I].AddressAreas = readAddressAreas(Dwarf, Sections[I]);
-    Chunks[I].NamesAndTypes = readPubNamesAndTypes(Dwarf);
+    Chunks[I].NamesAndTypes = readPubNamesAndTypes(Dwarf, I);
   });
 
   // .debug_gnu_pub{names,types} are useless in executables.
   // They are present in input object files solely for creating
   // a .gdb_index. So we can remove it from the output.
   for (InputSectionBase *S : InputSections)
     if (S->Name == ".debug_gnu_pubnames" || S->Name == ".debug_gnu_pubtypes")
       S->Live = false;

 
 static size_t getAddressAreaSize(ArrayRef<GdbIndexChunk> Arr) {
   size_t Ret = 0;
   for (const GdbIndexChunk &D : Arr)
     Ret += D.AddressAreas.size();
   return Ret;
 }
 
-std::vector<GdbSymbol *> GdbIndexSection::createGdbSymtab() {
-  uint32_t Size = NextPowerOf2(Symbols.size() * 4 / 3);
-  if (Size < 1024)
-    Size = 1024;
-
-  uint32_t Mask = Size - 1;
-  std::vector<GdbSymbol *> Ret(Size);
-
-  for (auto &KV : Symbols) {
-    GdbSymbol *Sym = KV.second;
-    uint32_t I = Sym->NameHash & Mask;
-    uint32_t Step = ((Sym->NameHash * 17) & Mask) | 1;
-
-    while (Ret[I])
-      I = (I + Step) & Mask;
-    Ret[I] = Sym;
-  }
-  return Ret;
+// Returns the desired size of an on-disk hash table for a .gdb_index section.
+// There's a tradeoff between size and collision rate. We aim 75% utilization.
+static size_t getSymtabSize(size_t NumSymbols) {
+  return std::max<size_t>(NextPowerOf2(NumSymbols * 4 / 3), 1024);
 }
 
 GdbIndexSection::GdbIndexSection(std::vector<GdbIndexChunk> &&C)
     : SyntheticSection(0, SHT_PROGBITS, 1, ".gdb_index"), Chunks(std::move(C)) {
-  fixCuIndex();
-  CuVectors = createCuVectors();
-  GdbSymtab = createGdbSymtab();
+  // A map to identify duplicate symbols.
+  DenseMap<CachedHashStringRef, size_t> Map;
+
+  // Initialize Symbols and CuVectors while deduplicating symbols by name.
+  for (GdbIndexChunk &Chunk : Chunks) {
+    for (GdbIndexChunk::NameTypeEntry &Ent : Chunk.NamesAndTypes) {
+      CachedHashStringRef S = Ent.Name;
+      size_t &Idx = Map[S];
+
+      if (!Idx) {
+        Idx = Symbols.size() + 1;
+        Symbols.push_back({S, StringPoolSize, Symbols.size()});
+        StringPoolSize += S.size() + 1;
+        CuVectors.push_back({});
+      }
+
+      // gcc 5.4.1 produces a buggy .debug_gnu_pubnames that contains
+      // duplicate entries, so we want to dedup them.
+      std::vector<uint32_t> &Vec = CuVectors[Symbols[Idx - 1].CuVectorIdx];
+      if (Vec.empty() || Vec.back() != Ent.Type)
+        Vec.push_back(Ent.Type);
+    }
+
+    // NamesAndTypes is useless beyond this point, so clear it to save memory.
+    Chunk.NamesAndTypes = {};
+  }
 
   // Compute offsets early to know the section size.
   // Each chunk size needs to be in sync with what we write in writeTo.
   CuTypesOffset = CuListOffset + getCuSize(Chunks) * 16;
   SymtabOffset = CuTypesOffset + getAddressAreaSize(Chunks) * 20;
-  ConstantPoolOffset = SymtabOffset + GdbSymtab.size() * 8;
+  SymtabSize = getSymtabSize(Symbols.size());
+  ConstantPoolOffset = SymtabOffset + SymtabSize * 8;
 
-  size_t Off = 0;
   for (ArrayRef<uint32_t> Vec : CuVectors) {
-    CuVectorOffsets.push_back(Off);
-    Off += (Vec.size() + 1) * 4;
+    CuVectorOffsets.push_back(ConstantPoolSize);
+    ConstantPoolSize += (Vec.size() + 1) * 4;
   }
-  StringPoolOffset = ConstantPoolOffset + Off;
+  StringPoolOffset = ConstantPoolOffset + ConstantPoolSize;
 }
 
 size_t GdbIndexSection::getSize() const {
   return StringPoolOffset + StringPoolSize;
 }
 
 void GdbIndexSection::writeTo(uint8_t *Buf) {
   // Write the section header.
   write32le(Buf, 7);
   write32le(Buf + 4, CuListOffset);
   write32le(Buf + 8, CuTypesOffset);
   write32le(Buf + 12, CuTypesOffset);
   write32le(Buf + 16, SymtabOffset);
   write32le(Buf + 20, ConstantPoolOffset);
   Buf += 24;
 
   // Write the CU list.
-  for (GdbIndexChunk &D : Chunks) {
-    for (GdbIndexChunk::CuEntry &Cu : D.CompilationUnits) {
-      write64le(Buf, D.DebugInfoSec->OutSecOff + Cu.CuOffset);
+  for (GdbIndexChunk &Chunk : Chunks) {
+    for (GdbIndexChunk::CuEntry &Cu : Chunk.CompilationUnits) {
+      write64le(Buf, Chunk.DebugInfoSec->OutSecOff + Cu.CuOffset);
       write64le(Buf + 8, Cu.CuLength);
       Buf += 16;
     }
   }
 
   // Write the address area.
-  for (GdbIndexChunk &D : Chunks) {
-    for (GdbIndexChunk::AddressEntry &E : D.AddressAreas) {
+  uint32_t Idx = 0;
+  for (GdbIndexChunk &Chunk : Chunks) {
+    for (GdbIndexChunk::AddressEntry &E : Chunk.AddressAreas) {
       uint64_t BaseAddr = E.Section->getVA(0);
       write64le(Buf, BaseAddr + E.LowAddress);
       write64le(Buf + 8, BaseAddr + E.HighAddress);
-      write32le(Buf + 16, E.CuIndex);
+      write32le(Buf + 16, E.CuIndex + Idx);
       Buf += 20;
     }
+    Idx += Chunk.CompilationUnits.size();
   }
 
-  // Write the symbol table.
-  for (GdbSymbol *Sym : GdbSymtab) {
-    if (Sym) {
-      write32le(Buf, Sym->NameOffset + StringPoolOffset - ConstantPoolOffset);
-      write32le(Buf + 4, CuVectorOffsets[Sym->CuVectorIndex]);
-    }
-    Buf += 8;
+  // Write the on-disk open-addressing hash table containing symbols.
+  for (GdbSymbol &Sym : Symbols) {
+    uint32_t Mask = SymtabSize - 1;
+    uint32_t H = Sym.Name.hash();
+    uint32_t I = H & Mask;
+    uint32_t Step = ((H * 17) & Mask) | 1;
+
+    while (read32le(Buf + I * 8))
+      I = (I + Step) & Mask;
+
+    uint8_t *P = Buf + I * 8;
+    write32le(P, ConstantPoolSize + Sym.OutputOff);
+    write32le(P + 4, CuVectorOffsets[Sym.CuVectorIdx]);
   }
 
+  Buf += SymtabSize * 8;
+
   // Write the CU vectors.
   for (ArrayRef<uint32_t> Vec : CuVectors) {
     write32le(Buf, Vec.size());
     Buf += 4;
     for (uint32_t Val : Vec) {
       write32le(Buf, Val);
       Buf += 4;
     }
   }
 
   // Write the string pool.
-  for (auto &KV : Symbols) {
-    CachedHashStringRef S = KV.first;
-    GdbSymbol *Sym = KV.second;
-    size_t Off = Sym->NameOffset;
-    memcpy(Buf + Off, S.val().data(), S.size());
-    Buf[Off + S.size()] = '\0';
+  for (GdbSymbol &Sym : Symbols) {
+    StringRef S = Sym.Name.val();
+    memcpy(Buf + Sym.OutputOff, S.data(), S.size());
+    Buf[Sym.OutputOff + S.size()] = '\0';
   }
 }
 
 bool GdbIndexSection::empty() const { return !Out::DebugInfo; }
 
 EhFrameHeader::EhFrameHeader()
     : SyntheticSection(SHF_ALLOC, SHT_PROGBITS, 4, ".eh_frame_hdr") {}