[ELF] Improve section GC for comdat groups

[evgeny777]

Summary

This patch fixes two things

1. If any section within comdat group is marked Live an entire group is marked live.
2. On some occasions GC may crash if symbol references section which is a member of comdat group. This happens in case compiler creates section relocation, i.e:

leaq    .text._Z3fooIiEvv(%rip), %rax

[ruiu]

Can it actually happen that two sections in the same comdat group have no relocations between them? I'm wondering how you found the issue.

[evgeny777]

I'm trying to keep debug information in --gc-sections mode. After I tried modifying isReserved() I immediately stepped on a crash, because .debug_lines section had relocation to one of the member of comdat groups. I think test case shows how this can happen, doesn't it?

[evgeny777]

Or are you trying to tell, that there are always relocs between each member of comdat group and all other members? If so you still need to locate the real section and add it to the queue, no?

[ruiu]

It feels to me that it is doing too much work to handle comdat groups. How about adding std::vector<InputSectionData *> GroupMembers to InputSectionData and use that as successors? InputFile creates such vector and add it to all group member sections, so that you can reach all group members from any group member.

[ruiu]

ELF/MarkLive.cpp

263–269

I don't think this is correct because the last forEachSuccessor could mark a section in a comdat group live, so you want to repeat this process until converge.

[evgeny777]

Let's elaborate the idea. The main problem is that symbol 'D' inside resolveReloc() may point to InputSectionBase<ELFT>::Discarded. This happens because comdat group is added to only one object file and causes crash in GC, because forEachSuccessor implicitly casts Discarded to InputSection<ELFT> and tries to fetch relocs from it. How this 'GroupMembers' vector would help?

[evgeny777]

ELF/MarkLive.cpp

263–269

The piece of code on lines 214-215 :

if (R.Sec->Live)
   return;

handles this, no?

ELF/InputFiles.h

public:
 
   uint8_t getOSABI() const {
     return getObj().getHeader()->e_ident[llvm::ELF::EI_OSABI];
   }
 
   StringRef getStringTable() const { return StringTable; }
 
   uint32_t getSectionIndex(const Elf_Sym &Sym) const;
+  uint32_t getSectionIndex(unsigned SymIndex) const;
 
   Elf_Sym_Range getElfSymbols(bool OnlyGlobals);
 
 protected:
   llvm::object::ELFFile<ELFT> ELFObj;
   const Elf_Shdr *Symtab = nullptr;
   ArrayRef<Elf_Word> SymtabSHNDX;
   StringRef StringTable;
public:
   ArrayRef<SymbolBody *> getLocalSymbols();
   ArrayRef<SymbolBody *> getNonLocalSymbols();
 
   explicit ObjectFile(MemoryBufferRef M);
   void parse(llvm::DenseSet<StringRef> &ComdatGroups);
 
   ArrayRef<InputSectionBase<ELFT> *> getSections() const { return Sections; }
   InputSectionBase<ELFT> *getSection(const Elf_Sym &Sym) const;
+  std::vector<InputSectionBase<ELFT> *>
+  getComdatSections(llvm::DenseSet<StringRef> &Signatures) const;
 
   SymbolBody &getSymbolBody(uint32_t SymbolIndex) const {
     return *SymbolBodies[SymbolIndex];
   }
 
   template <typename RelT> SymbolBody &getRelocTargetSym(const RelT &Rel) const {
     uint32_t SymIndex = Rel.getSymbol(Config->Mips64EL);
     return getSymbolBody(SymIndex);
   }
 
+  template <typename RelT>
+  uint32_t getRelocSectionIndex(const RelT &Rel) const {
+    return this->getSectionIndex(Rel.getSymbol(Config->Mips64EL));
+  }
+
+  StringRef getComdatGroupSignature(unsigned SecIndex);
+
   const Elf_Shdr *getSymbolTable() const { return this->Symtab; };
 
   // Get MIPS GP0 value defined by this file. This value represents the gp value
   // used to create the relocatable object and required to support
   // R_MIPS_GPREL16 / R_MIPS_GPREL32 relocations.
   uint32_t getMipsGp0() const;
 
   // The number is the offset in the string table. It will be used as the
private:
 
   // MIPS .reginfo section defined by this file.
   std::unique_ptr<MipsReginfoInputSection<ELFT>> MipsReginfo;
   // MIPS .MIPS.options section defined by this file.
   std::unique_ptr<MipsOptionsInputSection<ELFT>> MipsOptions;
   // MIPS .MIPS.abiflags section defined by this file.
   std::unique_ptr<MipsAbiFlagsInputSection<ELFT>> MipsAbiFlags;
 
+  // Section index to comdat group signature map;
+  llvm::DenseMap<unsigned, StringRef> SectionGroupSig;
+
   llvm::SpecificBumpPtrAllocator<InputSection<ELFT>> IAlloc;
   llvm::SpecificBumpPtrAllocator<MergeInputSection<ELFT>> MAlloc;
   llvm::SpecificBumpPtrAllocator<EhInputSection<ELFT>> EHAlloc;
 };
 
 // LazyObjectFile is analogous to ArchiveFile in the sense that
 // the file contains lazy symbols. The difference is that
 // LazyObjectFile wraps a single file instead of multiple files.

ELF/InputFiles.cpp

uint32_t ELFFileBase<ELFT>::getSectionIndex(const Elf_Sym &Sym) const {
   uint32_t I = Sym.st_shndx;
   if (I == ELF::SHN_XINDEX)
     return ELFObj.getExtendedSymbolTableIndex(&Sym, Symtab, SymtabSHNDX);
   if (I >= ELF::SHN_LORESERVE)
     return 0;
   return I;
 }
 
+template <class ELFT>
+uint32_t ELFFileBase<ELFT>::getSectionIndex(unsigned SymIndex) const {
+  Elf_Sym_Range Syms = ELFObj.symbols(Symtab);
+  uint32_t NumSymbols = std::distance(Syms.begin(), Syms.end());
+  if (SymIndex >= NumSymbols)
+    return -1;
+
+  return getSectionIndex(Syms[SymIndex]);
+}
+
 template <class ELFT> void ELFFileBase<ELFT>::initStringTable() {
   if (!Symtab)
     return;
   StringTable = check(ELFObj.getStringTableForSymtab(*Symtab));
 }
 
 template <class ELFT>
 elf::ObjectFile<ELFT>::ObjectFile(MemoryBufferRef M)
void elf::ObjectFile<ELFT>::initializeSections(
   Sections.resize(Size);
   unsigned I = -1;
   const ELFFile<ELFT> &Obj = this->ELFObj;
   for (const Elf_Shdr &Sec : Obj.sections()) {
     ++I;
     if (Sections[I] == &InputSection<ELFT>::Discarded)
       continue;
 
+    bool NewGroup;
+    StringRef GroupSig;
     switch (Sec.sh_type) {
     case SHT_GROUP:
       Sections[I] = &InputSection<ELFT>::Discarded;
-      if (ComdatGroups.insert(getShtGroupSignature(Sec)).second)
-        continue;
+      GroupSig = getShtGroupSignature(Sec);
+      NewGroup = ComdatGroups.insert(GroupSig).second;
       for (uint32_t SecIndex : getShtGroupEntries(Sec)) {
         if (SecIndex >= Size)
           fatal(getFilename(this) + ": invalid section index in group: " +
                 Twine(SecIndex));
+        if (!NewGroup)
           Sections[SecIndex] = &InputSection<ELFT>::Discarded;
+        SectionGroupSig[SecIndex] = GroupSig;
       }
       break;
     case SHT_SYMTAB:
       this->Symtab = &Sec;
       break;
     case SHT_SYMTAB_SHNDX:
       this->SymtabSHNDX = check(Obj.getSHNDXTable(Sec));
       break;
elf::ObjectFile<ELFT>::getSection(const Elf_Sym &Sym) const {
   // In this case it is fine for section to be null here as we
   // do not allocate sections of these types.
   if (!S || S == &InputSectionBase<ELFT>::Discarded)
     return S;
   return S->Repl;
 }
 
 template <class ELFT>
+std::vector<InputSectionBase<ELFT> *> elf::ObjectFile<ELFT>::getComdatSections(
+    DenseSet<StringRef> &Signatures) const {
+  std::vector<InputSectionBase<ELFT> *> Ret;
+  for (auto &P : SectionGroupSig)
+    if (Signatures.find(P.second) != Signatures.end() &&
+        Sections[P.first] != &InputSectionBase<ELFT>::Discarded)
+      Ret.push_back(Sections[P.first]);
+
+  return Ret;
+}
+
+template <class ELFT>
+StringRef elf::ObjectFile<ELFT>::getComdatGroupSignature(unsigned SecIndex) {
+  return SectionGroupSig[SecIndex];
+}
+
+template <class ELFT>
 SymbolBody *elf::ObjectFile<ELFT>::createSymbolBody(const Elf_Sym *Sym) {
   int Binding = Sym->getBinding();
   InputSectionBase<ELFT> *Sec = getSection(*Sym);
   if (Binding == STB_LOCAL) {
     if (Sym->st_shndx == SHN_UNDEF)
       return new (this->Alloc)
           Undefined(Sym->st_name, Sym->st_other, Sym->getType(), this);
     return new (this->Alloc) DefinedRegular<ELFT>(*Sym, Sec);

ELF/MarkLive.cpp

 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
 namespace {
 // A resolved relocation. The Sec and Offset fields are set if the relocation
-// was resolved to an offset within a section.
+// was resolved to an offset within a section. If relocation was resolved to
+// a member of comdat group then Sec may be null and Offset is an index of
+// section in File.
 template <class ELFT>
 struct ResolvedReloc {
+  ObjectFile<ELFT> *File;
   InputSectionBase<ELFT> *Sec;
   typename ELFT::uint Offset;
 };
 } // end anonymous namespace
 
 template <class ELFT>
 static typename ELFT::uint getAddend(InputSectionBase<ELFT> &Sec,
                                      const typename ELFT::Rel &Rel) {
   return Target->getImplicitAddend(Sec.Data.begin(),
                                    Rel.getType(Config->Mips64EL));
 }
 
 template <class ELFT>
 static typename ELFT::uint getAddend(InputSectionBase<ELFT> &Sec,
                                      const typename ELFT::Rela &Rel) {
   return Rel.r_addend;
 }
 
 template <class ELFT, class RelT>
 static ResolvedReloc<ELFT> resolveReloc(InputSectionBase<ELFT> &Sec,
                                         RelT &Rel) {
   SymbolBody &B = Sec.getFile()->getRelocTargetSym(Rel);
   auto *D = dyn_cast<DefinedRegular<ELFT>>(&B);
   if (!D || !D->Section)
-    return {nullptr, 0};
+    return {nullptr, nullptr, 0};
+  if (D->Section == &InputSectionBase<ELFT>::Discarded)
+    return {Sec.getFile(), nullptr, Sec.getFile()->getRelocSectionIndex(Rel)};
   typename ELFT::uint Offset = D->Value;
   if (D->isSection())
     Offset += getAddend(Sec, Rel);
-  return {D->Section->Repl, Offset};
+  return {D->Section->Repl->getFile(), D->Section->Repl, Offset};
 }
 
 // Calls Fn for each section that Sec refers to via relocations.
 template <class ELFT>
 static void forEachSuccessor(InputSection<ELFT> &Sec,
                              std::function<void(ResolvedReloc<ELFT>)> Fn) {
   ELFFile<ELFT> &Obj = Sec.getFile()->getObj();
   for (const typename ELFT::Shdr *RelSec : Sec.RelocSections) {
for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
       const RelTy &Rel = Rels[I2];
       if (Rel.r_offset >= PieceEnd)
         break;
       ResolvedReloc<ELFT> R = resolveReloc(EH, Rels[I2]);
       if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded)
         continue;
       if (R.Sec->getSectionHdr()->sh_flags & SHF_EXECINSTR)
         continue;
-      Enqueue({R.Sec, 0});
+      Enqueue({R.Sec->getFile(), R.Sec, 0});
     }
   }
 }
 
 template <class ELFT>
 static void
 scanEhFrameSection(EhInputSection<ELFT> &EH,
                    std::function<void(ResolvedReloc<ELFT>)> Enqueue) {
template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) {
   }
 }
 
 // This is the main function of the garbage collector.
 // Starting from GC-root sections, this function visits all reachable
 // sections to set their "Live" bits.
 template <class ELFT> void elf::markLive() {
   SmallVector<InputSection<ELFT> *, 256> Q;
+  DenseSet<StringRef> LiveComdatGroups;
 
   auto Enqueue = [&](ResolvedReloc<ELFT> R) {
-    if (!R.Sec)
+    if (!R.Sec) {
+      if (!R.File)
         return;
 
+      StringRef GroupSig = R.File->getComdatGroupSignature(R.Offset);
+      if (!GroupSig.empty())
+        LiveComdatGroups.insert(GroupSig);
+      return;
+    }
+
     // Usually, a whole section is marked as live or dead, but in mergeable
     // (splittable) sections, each piece of data has independent liveness bit.
     // So we explicitly tell it which offset is in use.
     if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec))
       MS->markLiveAt(R.Offset);
 
     if (R.Sec->Live)
       return;
     R.Sec->Live = true;
     if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec))
       Q.push_back(S);
   };
 
   auto MarkSymbol = [&](const SymbolBody *Sym) {
     if (auto *D = dyn_cast_or_null<DefinedRegular<ELFT>>(Sym))
-      Enqueue({D->Section, D->Value});
+      Enqueue({D->Section->getFile(), D->Section, D->Value});
   };
 
   // Add GC root symbols.
   if (Config->EntrySym)
     MarkSymbol(Config->EntrySym->body());
   MarkSymbol(Symtab<ELFT>::X->find(Config->Init));
   MarkSymbol(Symtab<ELFT>::X->find(Config->Fini));
   for (StringRef S : Config->Undefined)
for (ObjectFile<ELFT> *F : Symtab<ELFT>::X->getObjectFiles()) {
     for (InputSectionBase<ELFT> *Sec : F->getSections()) {
       if (Sec && Sec != &InputSection<ELFT>::Discarded) {
         // .eh_frame is always marked as live now, but also it can reference to
         // sections that contain personality. We preserve all non-text sections
         // referred by .eh_frame here.
         if (auto *EH = dyn_cast_or_null<EhInputSection<ELFT>>(Sec))
           scanEhFrameSection<ELFT>(*EH, Enqueue);
         if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec))
-          Enqueue({Sec, 0});
+          Enqueue({Sec->getFile(), Sec, 0});
       }
     }
   }
 
-  // Mark all reachable sections.
+  // Pass 1. Mark all reachable sections, except comdat groups.
+  while (!Q.empty())
+    forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
+
+  if (LiveComdatGroups.empty())
+    return;
+
+  // Pass 2. Identify and mark reachable comdat groups.
+  for (ObjectFile<ELFT> *F : Symtab<ELFT>::X->getObjectFiles())
+    for (InputSectionBase<ELFT> *Sec : F->getComdatSections(LiveComdatGroups))
+      Enqueue({Sec->getFile(), Sec, 0});
+
   while (!Q.empty())
     forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
 }
 
 template void elf::markLive<ELF32LE>();
 template void elf::markLive<ELF32BE>();
 template void elf::markLive<ELF64LE>();
 template void elf::markLive<ELF64BE>();

test/ELF/Inputs/comdat-gc.s

+.weak _Z3fooIiEvv
+.section  .text._Z3fooIiEvv,"axG",@progbits,_Z3fooIiEvv,comdat
+_Z3fooIiEvv:
+  ret
+
+.global _start
+.section .zzz, "ax"  
+_start:
+   leaq    .text._Z3fooIiEvv(%rip), %rax
+

test/ELF/comdat-gc.s

+// Check that the linker doesn't crash and comdat group is not gc'ed
+// RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+// RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/comdat-gc.s -o %t2.o
+// RUN: ld.lld --gc-sections %t.o %t2.o -o %t
+// RUN: llvm-readobj -t %t | FileCheck %s
+// CHECK: _Z3fooIiEvv
+
+.weak _Z3fooIiEvv
+
+.section  .text._Z3fooIiEvv,"axG",@progbits,_Z3fooIiEvv,comdat
+_Z3fooIiEvv:
+  ret
+