Respect section groups in GC

[eugenis]

Summary

Treat sections that are part of a group as a unit in GC. This effectively makes ELF section groups behave as associative comdats in COFF.

The current implementation uses section groups for selection (i.e. discard duplicate definitions), but then ignores them in GC, potentially discarding parts of a section group.

• The new implementation matches the BFD linker behavior, while the current implementation matches Gold.

This is also necessary for proper GC of globals in AddressSanitizer. To give some context, ASan emits a "metadata global" for each application global, and needs to iterate over them at runtime. Metadata globals should not affect the liveness of original globals, and they need to be preserved if and only if the corresponding global is preserved.

[rnk]

Great! I'm glad we can do this without extending ELF.

What happens when gold users link asan objects with non-comdat section groups? Does gold simply fail to GC globals in the group, or does it do something bad? If we can treat this as a gold quality-of-implementation issue, we can always emit the section groups this way in ASan.

[eugenis]

Yes, Gold simply fails to GC asan globals. My next change would unconditionally enable the new codegen in ASan.

[ruiu]

At first this seems like a good change, but after thinking for a while, it started feeling that this is not a good one, as this is effectively extending the ELF format by adding a new meaning to SHT_GROUP. As per the ELF spec, SHT_GROUP is a mechanism to group and uniquify sections, and the spec doesn't say anything about GC. Even GNU linkers don't agree with each other. You could argue that it implies that sections in a SHT_GROUP need to be handled as one unit by GC, but you could also argue that it has no business with GC as it doesn't violate any specifications. So it's a dark corner, and I don't think we should rely on such thing.

I wonder if there's a different way to keep them alive. One thing I can think of is to add a dummy relocation (something like R_X86_64_NONE) to a section so that if the section is alive, the other sections will become alive, without actually doing any relocations. Does it work?

[pcc]

In D28481#640798, @ruiu wrote:

At first this seems like a good change, but after thinking for a while, it started feeling that this is not a good one, as this is effectively extending the ELF format by adding a new meaning to SHT_GROUP. As per the ELF spec, SHT_GROUP is a mechanism to group and uniquify sections, and the spec doesn't say anything about GC. Even GNU linkers don't agree with each other. You could argue that it implies that sections in a SHT_GROUP need to be handled as one unit by GC, but you could also argue that it has no business with GC as it doesn't violate any specifications. So it's a dark corner, and I don't think we should rely on such thing.

I wouldn't necessarily draw that conclusion, it may simply mean that the gABI requires clarification.

I wonder if there's a different way to keep them alive. One thing I can think of is to add a dummy relocation (something like R_X86_64_NONE) to a section so that if the section is alive, the other sections will become alive, without actually doing any relocations. Does it work?

This alone is not sufficient, because the linker treats sections whose names are C identifiers as GC roots.

[rnk]

In D28481#640798, @ruiu wrote:

I wonder if there's a different way to keep them alive. One thing I can think of is to add a dummy relocation (something like R_X86_64_NONE) to a section so that if the section is alive, the other sections will become alive, without actually doing any relocations. Does it work?

Currently, linker GC retains all data in sections referenced by start_$section stop_$section. We need to suppress that retention in addition to establishing this inverse reference. How do you propose to do that?

This behavior should also already be suppressed for normal comdat section groups. Consider this assembly: https://ghostbin.com/paste/v5qrp The .init_array global is in a comdat section, and should not be retained by the linker if 'x' is unreferenced.

[ruiu]

We just cut a corner when writing the code to handle section names valid as C identifiers. Because the number of such sections are usually small, we just made all such sections alive. However, if you need more precise GC, I think you could do that.

Can I ask why ASAN uses start_ and end_ symbols?

[pcc]

In D28481#640854, @ruiu wrote:

We just cut a corner when writing the code to handle section names valid as C identifiers. Because the number of such sections are usually small, we just made all such sections alive. However, if you need more precise GC, I think you could do that.

How would you propose to change the GC?

Can I ask why ASAN uses start_ and end_ symbols?

The __start_ and __stop_ symbols define the address range in which the metadata globals are stored. See Evgeniy's other change, D28498, which sets up a call to __asan_register_globals passing in that address range.

[ruiu]

Hm, now I recall why we did that for C identifier sections. Sections with C identifier names can be garbage collected if no one is referring them, but that cannot be determined until we create output sections, and when we create output sections, it is usually too late to do GC. We could do something tricky to handle that, but it's probably not worth it.

So, maybe I'm fine with this. But I think the implementation can be simplified. It feels it is doing too much ahead of time. Also the new condition Sec->GroupSections.size() == 0 && isValidCIdentifier(S) definitely needs a comment.

[eugenis]

In D28481#640940, @ruiu wrote:

Hm, now I recall why we did that for C identifier sections. Sections with C identifier names can be garbage collected if no one is referring them, but that cannot be determined until we create output sections, and when we create output sections, it is usually too late to do GC. We could do something tricky to handle that, but it's probably not worth it.

So, maybe I'm fine with this. But I think the implementation can be simplified. It feels it is doing too much ahead of time.

Could you elaborate? All this code does is store two words per each section that participates in a group. We do need to store the inverse dependency somewhere...

Also the new condition Sec->GroupSections.size() == 0 && isValidCIdentifier(S) definitely needs a comment.

Will do. Also, it sounds like we want to extend this logic to all special sections (like .ctors below). Basically,
if (Sec->GroupSections.size() != 0) return false;
at the beginning of isReserved().

[ruiu]

In D28481#641827, @eugenis wrote:

In D28481#640940, @ruiu wrote:

Hm, now I recall why we did that for C identifier sections. Sections with C identifier names can be garbage collected if no one is referring them, but that cannot be determined until we create output sections, and when we create output sections, it is usually too late to do GC. We could do something tricky to handle that, but it's probably not worth it.

So, maybe I'm fine with this. But I think the implementation can be simplified. It feels it is doing too much ahead of time.

Could you elaborate? All this code does is store two words per each section that participates in a group. We do need to store the inverse dependency somewhere...

Please avoid instantiating sections that are to be nullified with Discarded section. Previously, we didn't instantiate sections if they are discarded, but with this patch, all sections are instantiated whether they are going to be discarded or not.

[eugenis]

In D28481#642004, @ruiu wrote:

In D28481#641827, @eugenis wrote:

In D28481#640940, @ruiu wrote:

Hm, now I recall why we did that for C identifier sections. Sections with C identifier names can be garbage collected if no one is referring them, but that cannot be determined until we create output sections, and when we create output sections, it is usually too late to do GC. We could do something tricky to handle that, but it's probably not worth it.

So, maybe I'm fine with this. But I think the implementation can be simplified. It feels it is doing too much ahead of time.

Could you elaborate? All this code does is store two words per each section that participates in a group. We do need to store the inverse dependency somewhere...

Please avoid instantiating sections that are to be nullified with Discarded section. Previously, we didn't instantiate sections if they are discarded, but with this patch, all sections are instantiated whether they are going to be discarded or not.

Of course. Good point. Fixed.

[ruiu]

ELF/InputFiles.cpp

296–303

Revert these cosmetic changes.

339

Use ArrayRef<typename ELFT::Word> instead of auto.

341–343

It shouldn't fail this time because we have the same error check above, so you don't need this check. Then this can be written as

for (uint32_t SecIndex : GroupSections)
  if (Sections[SecIndex] != &InputSection<ELFT>::Discarded)
    Sections[SecIndex]->GroupSections = GroupSections;

344–345

It cannot be nullptr, no? I think this can only be Discarded or a regular section.

ELF/InputSection.h

95

This needs a comment. Please describe that if sections are grouped by SHT_GROUP, we handle the sections as a unit in garbage collection, because that is needed for at least ASAN although it is not clearly documented in the standard document.

ELF/MarkLive.cpp

83–84

// Visit relocations.

92

// Visit a reverse link of SHF_LINK_ORDER if exists.

94

// Visit SHT_GROUP members if this section is in a group.

174

Please explain why you want that behavior, in addition to how this code behaves.

[eugenis]

ELF/InputFiles.cpp

296–303

Done, but this file is not clang-format clean.

341–343

The check above runs for discarded groups only.

344–345

These cases above don't seem to set the section pointer:

case SHT_SYMTAB:
 case SHT_SYMTAB_SHNDX:
 case SHT_STRTAB:
 case SHT_NULL:

[ruiu]

LGTM with nits.

ELF/MarkLive.cpp

83–84

This belongs to this entire if { ~ } else { ~ } and not to this if clause, so it should be written before if.

95

auto -> uint32_t

187

nit: use empty() if ArrayRef has that function.

[pcc]

ELF/MarkLive.cpp

178

Can it, though? I think we still need to run the global initializer since it may have observable side effects other than initializing the global.

[rnk]

ELF/MarkLive.cpp

178

This is a valid concern. MSVC actually puts '/include:globalsym' in the .drective section to ensure that such globals are not garbage collected.

ELF/InputFiles.cpp

if ((Sec.sh_flags & SHF_EXCLUDE) && !Config->Relocatable) {
       Sections[I] = &InputSection<ELFT>::Discarded;
       continue;
     }
 
     switch (Sec.sh_type) {
     case SHT_GROUP:
       Sections[I] = &InputSection<ELFT>::Discarded;
       if (ComdatGroups.insert(CachedHashStringRef(
                                   getShtGroupSignature(ObjSections, Sec)))
               .second)
         continue;
       for (uint32_t SecIndex : getShtGroupEntries(Sec)) {
         if (SecIndex >= Size)
           fatal(toString(this) + ": invalid section index in group: " +
                 Twine(SecIndex));
         Sections[SecIndex] = &InputSection<ELFT>::Discarded;
       }
       break;
     case SHT_SYMTAB:
       this->initSymtab(ObjSections, &Sec);
       break;
     case SHT_SYMTAB_SHNDX:
       this->SymtabSHNDX = check(Obj.getSHNDXTable(Sec, ObjSections));
       break;
for (const Elf_Shdr &Sec : ObjSections) {
     if (Sec.sh_flags & SHF_LINK_ORDER) {
       if (Sec.sh_link >= Sections.size())
         fatal(toString(this) + ": invalid sh_link index: " +
               Twine(Sec.sh_link));
       auto *IS = cast<InputSection<ELFT>>(Sections[Sec.sh_link]);
       IS->DependentSection = Sections[I];
     }
   }
+
+  // Handle SHT_GROUP by giving all members of the selected group a GC link back
+  // to the group section, and discarding the rest. This is done after the main
+  // loop because it needs group member sections to be initialized.
+  I = -1;
+  for (const Elf_Shdr &Sec : ObjSections) {
+    ++I;
+    if (Sec.sh_type != SHT_GROUP)
+      continue;
+
+    ArrayRef<typename ELFT::Word> GroupSections = getShtGroupEntries(Sec);
+    for (uint32_t SecIndex : GroupSections) {
+      if (SecIndex >= Size)
+        fatal(toString(this) +
+              ": invalid section index in group: " + Twine(SecIndex));
+      if (!Sections[SecIndex] ||
+          Sections[SecIndex] == &InputSection<ELFT>::Discarded)
+        continue;
+      Sections[SecIndex]->GroupSections = GroupSections;
+    }
+  }
 }
 
 template <class ELFT>
 InputSectionBase<ELFT> *
 elf::ObjectFile<ELFT>::getRelocTarget(const Elf_Shdr &Sec) {
   uint32_t Idx = Sec.sh_info;
   if (Idx >= Sections.size())
     fatal(toString(this) + ": invalid relocated section index: " + Twine(Idx));

ELF/InputSection.h

public:
   // These corresponds to the fields in Elf_Shdr.
   uintX_t Flags;
   uintX_t Offset = 0;
   uintX_t Entsize;
   uint32_t Type;
   uint32_t Link;
   uint32_t Info;
 
+  // If this section is part of a section group, this list contains indices of
+  // all sections in that group. Section groups are treated as a unit in garbage
+  // collection. Even through it is not clearly documented in the standard, this
+  // matches the BFD linker behavior and is also important for AddressSanitizer
+  // (see https://github.com/google/sanitizers/issues/260).
+  ArrayRef<typename ELFT::Word> GroupSections;
+
   InputSectionBase()
       : InputSectionData(Regular, "", ArrayRef<uint8_t>(), false), Repl(this) {
     NumRelocations = 0;
     AreRelocsRela = false;
   }
 
   InputSectionBase(ObjectFile<ELFT> *File, const Elf_Shdr *Header,
                    StringRef Name, Kind SectionKind);

ELF/MarkLive.cpp

if (D->isSection())
     Offset += getAddend(Sec, Rel);
   return {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) {
   if (Sec.AreRelocsRela) {
+    // Visit relocations.
     for (const typename ELFT::Rela &Rel : Sec.relas())
       Fn(resolveReloc(Sec, Rel));
   } else {
     for (const typename ELFT::Rel &Rel : Sec.rels())
       Fn(resolveReloc(Sec, Rel));
   }
+  // Visit a reverse link of SHF_LINK_ORDER if exists.
   if (Sec.DependentSection)
     Fn({Sec.DependentSection, 0});
+  // Visit SHT_GROUP members if this section is in a group.
+  for (auto SecIdx : Sec.GroupSections) {
+    InputSectionBase<ELFT> *SameGroupSection =
+        Sec.getFile()->getSections()[SecIdx];
+    if (SameGroupSection &&
+        SameGroupSection != &InputSection<ELFT>::Discarded &&
+        SameGroupSection != &Sec)
+      Fn({SameGroupSection, 0});
+  }
 }
 
 // The .eh_frame section is an unfortunate special case.
 // The section is divided in CIEs and FDEs and the relocations it can have are
 // * CIEs can refer to a personality function.
 // * FDEs can refer to a LSDA
 // * FDEs refer to the function they contain information about
 // The last kind of relocation cannot keep the referred section alive, or they
scanEhFrameSection(EhInputSection<ELFT> &EH,
   else
     scanEhFrameSection(EH, EH.rels(), Enqueue);
 }
 
 // We do not garbage-collect two types of sections:
 // 1) Sections used by the loader (.init, .fini, .ctors, .dtors or .jcr)
 // 2) Non-allocatable sections which typically contain debugging information
 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) {
+  // Sections that are part of a group follow the usual GC rules.
+  //
+  // This allows discarding special sections that are associated with regular
+  // sections. As an example, an .init_array pointer for a global initializer
+  // can be discarded if the global is unused (and that, in turn, would allow to
+  // discard the global itself).
+  //
+  // Another example is AddressSanitizer, which attaches special descriptors to
+  // all globals and collects them in a specially-named section. Even though the
+  // name of that section isValidCIdentifier(), the descriptors should not
+  // affect the liveness of corresponding globals in any way, which mean that
+  // should not be added to GC roots based on the section name. See
+  // https://github.com/google/sanitizers/issues/260 for more context.
+  if (Sec->GroupSections.size() > 0)
+    return false;
+
   switch (Sec->Type) {
   case SHT_FINI_ARRAY:
   case SHT_INIT_ARRAY:
   case SHT_NOTE:
   case SHT_PREINIT_ARRAY:
     return true;
   default:
     if (!(Sec->Flags & SHF_ALLOC))

test/ELF/comdat-gc.s

+// Test that GC respects section groups.
+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+// RUN: ld.lld -shared -gc-sections %t.o -o %t
+// RUN: llvm-objdump -t %t | FileCheck --check-prefix=SYM %s
+// RUN: llvm-objdump -section-headers %t | FileCheck --check-prefix=SEC %s
+
+  .text
+  .section  .bss.x,"aGw",@nobits,x,comdat
+  .globl  x
+x:
+  .quad 0
+  .section  .bss.y,"aGw",@nobits,x,comdat
+y:
+  .quad 0
+// "x" is a GC root (external global in a
+// shared library), "y" is in the same section group as "x" and therefore must
+// not be discarded.
+// SYM-DAG: .bss{{.*}} y{{$}}
+
+  .section  zzz_no_comdat,"aw",@nobits
+z1:
+  .quad 0
+// A section with a name that is a valid C identifier, not part of any section
+// group => GC root.
+// SYM-DAG: zzz_no_comdat{{.*}} z1{{$}}
+
+  .section  zzz_comdat,"aGw",@nobits,z2,comdat
+z2:
+  .quad 0
+// No special treatment if the section is in a section group.
+// SEC-NOT: zzz_comdat
+
+  .section  .ctors,"aGw",@progbits,z3,comdat
+z3:
+  .quad 0
+// No special treatment if the section is in a section group, even for magic
+// sections like .ctors.
+// SEC-NOT: .ctors