[ELF] Improve --gc-sections compatibility with GNU ld regarding section groups

[MaskRay]

Summary

Based on D70020 by serge-sans-paille.

The ELF spec says:

Furthermore, there may be internal references among these sections that would not make sense if one of the sections were removed or replaced by a duplicate from another object. Therefore, such groups must be included or omitted from the linked object as a unit. A section cannot be a member of more than one group.

GNU ld has 2 behaviors that we don't have:

• Group members (nextInSectionGroup != nullptr) are subject to garbage collection. This includes non-SHF_ALLOC SHT_NOTE sections. In particular, discarding non-SHF_ALLOC SHT_NOTE sections is an expected behavior by the Annobin project. See https://developers.redhat.com/blog/2018/02/20/annobin-storing-information-binaries/ for more information.
• Groups members are retained or discarded as a unit. Members may have internal references that are not expressed as SHF_LINK_ORDER, relocations, etc. It seems that we should be more conservative here: if a section is marked live, mark all the other member within the group.

Both behaviors are reasonable. This patch implements them.

A new field InputSectionBase::nextInSectionGroup tracks the next member
within a group. on ELF64, this increases sizeof(InputSectionBase) froms
144 to 152.

InputSectionBase::dependentSections tracks section dependencies, which
is used by both --gc-sections and /DISCARD/. We can't overload it for
the "next member" semantic, because we should allow /DISCARD/ to discard
sections independent of --gc-sections (GNU ld behavior). This behavior
may be reasonably used by /DISCARD/ : { *(.ARM.exidx*) } or `/DISCARD/
: { *(.note*) } (new test linkerscript/discard-group.s`).

[MaskRay]

Improve the description and a comment.

[serge-sans-paille]

LGTM. The only thing that has me worried is to have two fields (dependentSections and nextInGroup) to represent concepts that are close (but different, due to that strange behavior wrt. /DISCARD/ sections).

[peter.smith]

I'm broadly in favour of making this change. I recognise there are some concerns about the intent behind the ELF specification, which is largely written without garbage collection in mind. One reading of it is that garbage collection is orthogonal to group selection, and the all or nothing comments relate to group selection only. Will be good to wait a few days to see if there are any strong objections. I tend towards the conservative approach unless there are some demonstrable benefits from not doing so.

For upstream clang compiled objects I don't think that there would be a large impact for this change as the majority of groups have just one Section and a Relocation Section. ARM compiled groups also have .ARM.exidx and accompanying relocations but these are already all or nothing due to the way they are constructed, nothing refers to the .ARM.exidx and we rely on the SHF_LINK_ORDER reverse dependency for garbage collection protection.

I'm happy to separate out nextInGroup and dependentSections as while there are some similarities the former is used for ELF groups the latter is used for SHF_LINK_ORDER and keeping the concepts separate is reasonable.

[serge-sans-paille]

Cool. I've started this thread https://sourceware.org/ml/binutils/2019-11/msg00187.html to gather more opinions about the reading of the specs.

[grimar]

FTR, I also think I have no objections. A few minor nits are inline.

lld/ELF/InputFiles.cpp

621

nit: I so not think that we declare more than one variable on a line in the LLD code.
Personally I find it OK for my pet projects, but this probably violates the LLD style, so ...

623

use continue?

lld/test/ELF/linkerscript/discard-group.s

2

Why arm? Can this be x86?

[MaskRay]

review comments

[MaskRay]

lld/test/ELF/linkerscript/discard-group.s

2

The intention is to create a practical use case which is more practical. It demonstrates the advantage that makes section group selection and garbage collection orthogonal for group members. https://sourceware.org/ml/binutils/2019-11/msg00210.html

.fnstart creates an associated section (.ARM.exidx*) in the section group, while .cfi_startproc creates .eh_frame outside the group.

[grimar]

lld/test/ELF/linkerscript/discard-group.s

2

Ok, I see now, thanks.

.fnstart creates an associated section (.ARM.exidx*) in the section group

Perhaps I'd mention this in the comments in this test case, for readers who are not so familar with arm (like me).

[MaskRay]

Add more comments to test/ELF/linkerscript/discard-group.s

[ruiu]

LGTM

lld/ELF/InputFiles.cpp

595

This is not your code, but could you please add a comment for this block since you add more code to this function? This block handles SHF_LINK_ORDER section flags.

lld/ELF/InputSection.h

147

I'd probably name this sectionGroupNextMember or something like that, so that it is clear that "group" means "section group".

[MaskRay]

lld/ELF/InputSection.h

147

What about nextInSectionGroup?

@peter.smith What do you think?

(I confess that in BFD, a member serving a similar purpose is named next_in_group.)

[MaskRay]

Add a comment

[ruiu]

lld/ELF/InputSection.h

147

That's fine too. I honestly don't think next_in_group is a good name, as we use "group" for other meanings such as --start-group.

[MaskRay]

nextInGroup -> nextInSectionGroup

[peter.smith]

This looks good to me too.

lld/ELF/InputSection.h

147

Yes nextInSectionGroup is fine.

lld/ELF/InputFiles.cpp

void ObjFile<ELFT>::initializeSections(bool ignoreComdats) {
   const ELFFile<ELFT> &obj = this->getObj();
 
   ArrayRef<Elf_Shdr> objSections = CHECK(obj.sections(), this);
   uint64_t size = objSections.size();
   this->sections.resize(size);
   this->sectionStringTable =
       CHECK(obj.getSectionStringTable(objSections), this);
 
+  std::vector<ArrayRef<Elf_Word>> selectedGroups;
+
   for (size_t i = 0, e = objSections.size(); i < e; ++i) {
     if (this->sections[i] == &InputSection::discarded)
       continue;
     const Elf_Shdr &sec = objSections[i];
 
     if (sec.sh_type == ELF::SHT_LLVM_CALL_GRAPH_PROFILE)
       cgProfile =
           check(obj.template getSectionContentsAsArray<Elf_CGProfile>(&sec));
case SHT_GROUP: {
 
       bool isNew =
           ignoreComdats ||
           symtab->comdatGroups.try_emplace(CachedHashStringRef(signature), this)
               .second;
       if (isNew) {
         if (config->relocatable)
           this->sections[i] = createInputSection(sec);
+        selectedGroups.push_back(entries);
         continue;
       }
 
       // Otherwise, discard group members.
       for (uint32_t secIndex : entries.slice(1)) {
         if (secIndex >= size)
           fatal(toString(this) +
                 ": invalid section index in group: " + Twine(secIndex));
         this->sections[secIndex] = &InputSection::discarded;
       }
       break;
     }
     case SHT_SYMTAB_SHNDX:
       shndxTable = CHECK(obj.getSHNDXTable(sec, objSections), this);
       break;
     case SHT_SYMTAB:
     case SHT_STRTAB:
     case SHT_NULL:
       break;
     default:
       this->sections[i] = createInputSection(sec);
     }
   }
 
+  // This block handles SHF_LINK_ORDER.
   for (size_t i = 0, e = objSections.size(); i < e; ++i) {
     if (this->sections[i] == &InputSection::discarded)
       continue;
     const Elf_Shdr &sec = objSections[i];
     if (!(sec.sh_flags & SHF_LINK_ORDER))
       continue;
 
     // .ARM.exidx sections have a reverse dependency on the InputSection they
     // have a SHF_LINK_ORDER dependency, this is identified by the sh_link.
     InputSectionBase *linkSec = nullptr;
     if (sec.sh_link < this->sections.size())
       linkSec = this->sections[sec.sh_link];
     if (!linkSec)
       fatal(toString(this) + ": invalid sh_link index: " + Twine(sec.sh_link));
 
     InputSection *isec = cast<InputSection>(this->sections[i]);
     linkSec->dependentSections.push_back(isec);
     if (!isa<InputSection>(linkSec))
       error("a section " + isec->name +
             " with SHF_LINK_ORDER should not refer a non-regular section: " +
             toString(linkSec));
   }
+
+  // For each secion group, connect its members in a circular doubly-linked list
+  // via nextInSectionGroup. See the comment in markLive().
+  for (ArrayRef<Elf_Word> entries : selectedGroups) {
+    InputSectionBase *head;
+    InputSectionBase *prev = nullptr;
+    for (uint32_t secIndex : entries.slice(1)) {
+      InputSectionBase *s = this->sections[secIndex];
+      if (!s || s == &InputSection::discarded)
+        continue;
+      if (prev)
+        prev->nextInSectionGroup = s;
+      else
+        head = s;
+      prev = s;
+    }
+    if (prev)
+      prev->nextInSectionGroup = head;
+  }
 }
 
 // For ARM only, to set the EF_ARM_ABI_FLOAT_SOFT or EF_ARM_ABI_FLOAT_HARD
 // flag in the ELF Header we need to look at Tag_ABI_VFP_args to find out how
 // the input objects have been compiled.
 static void updateARMVFPArgs(const ARMAttributeParser &attributes,
                              const InputFile *f) {
   if (!attributes.hasAttribute(ARMBuildAttrs::ABI_VFP_args))

lld/ELF/InputSection.h

public:
   uint64_t getOffsetInFile() const;
 
   // Input sections are part of an output section. Special sections
   // like .eh_frame and merge sections are first combined into a
   // synthetic section that is then added to an output section. In all
   // cases this points one level up.
   SectionBase *parent = nullptr;
 
+  // The next member in the section group if this section is in a group. This is
+  // used by --gc-sections.
+  InputSectionBase *nextInSectionGroup = nullptr;
+
   template <class ELFT> ArrayRef<typename ELFT::Rel> rels() const {
     assert(!areRelocsRela);
     return llvm::makeArrayRef(
         static_cast<const typename ELFT::Rel *>(firstRelocation),
         numRelocations);
   }
 
   template <class ELFT> ArrayRef<typename ELFT::Rela> relas() const {

lld/ELF/MarkLive.cpp

 
 // Some sections are used directly by the loader, so they should never be
 // garbage-collected. This function returns true if a given section is such
 // section.
 static bool isReserved(InputSectionBase *sec) {
   switch (sec->type) {
   case SHT_FINI_ARRAY:
   case SHT_INIT_ARRAY:
-  case SHT_NOTE:
   case SHT_PREINIT_ARRAY:
     return true;
+  case SHT_NOTE:
+    // SHT_NOTE sections in a group are subject to garbage collection.
+    return !sec->nextInSectionGroup;
   default:
     StringRef s = sec->name;
     return s.startswith(".ctors") || s.startswith(".dtors") ||
            s.startswith(".init") || s.startswith(".fini") ||
            s.startswith(".jcr");
   }
 }
 
if (sec.areRelocsRela) {
         resolveReloc(sec, rel, false);
     } else {
       for (const typename ELFT::Rel &rel : sec.template rels<ELFT>())
         resolveReloc(sec, rel, false);
     }
 
     for (InputSectionBase *isec : sec.dependentSections)
       enqueue(isec, 0);
+
+    // Mark the next group member.
+    if (sec.nextInSectionGroup)
+      enqueue(sec.nextInSectionGroup, 0);
   }
 }
 
 // Move the sections for some symbols to the main partition, specifically ifuncs
 // (because they can result in an IRELATIVE being added to the main partition's
 // GOT, which means that the ifunc must be available when the main partition is
 // loaded) and TLS symbols (because we only know how to correctly process TLS
 // relocations for the main partition).
template <class ELFT> void markLive() {
   // Note on SHF_LINK_ORDER: Such sections contain metadata and they
   // have a reverse dependency on the InputSection they are linked with.
   // We are able to garbage collect them.
   //
   // Note on SHF_REL{,A}: Such sections reach here only when -r
   // or -emit-reloc were given. And they are subject of garbage
   // collection because, if we remove a text section, we also
   // remove its relocation section.
+  //
+  // Note on nextInSectionGroup: The ELF spec says that group sections are
+  // included or omitted as a unit. We take the interpretation that:
+  //
+  // - Group members (nextInSectionGroup != nullptr) are subject to garbage
+  //   collection.
+  // - Groups members are retained or discarded as a unit.
   for (InputSectionBase *sec : inputSections) {
     bool isAlloc = (sec->flags & SHF_ALLOC);
     bool isLinkOrder = (sec->flags & SHF_LINK_ORDER);
     bool isRel = (sec->type == SHT_REL || sec->type == SHT_RELA);
 
-    if (!isAlloc && !isLinkOrder && !isRel)
+    if (!isAlloc && !isLinkOrder && !isRel && !sec->nextInSectionGroup)
       sec->markLive();
   }
 
   // Follow the graph to mark all live sections.
   for (unsigned curPart = 1; curPart <= partitions.size(); ++curPart)
     MarkLive<ELFT>(curPart).run();
 
   // If we have multiple partitions, some sections need to live in the main

lld/test/ELF/gc-sections-group.s

+# REQUIRES: x86
+## Check that group members are retained or discarded as a unit, and
+## non-SHF_ALLOC sections in a group are subject to garbage collection.
+## This is compatible with GNU ld.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+# RUN: ld.lld --gc-sections %t.o -o %t.dead
+# RUN: llvm-readobj -S %t.dead | FileCheck %s --check-prefix=CHECK-DEAD
+
+## .mynote.bar is retained because it is not in a group.
+# CHECK-DEAD-NOT: Name: .myanote.foo
+# CHECK-DEAD-NOT: Name: .mytext.foo
+# CHECK-DEAD-NOT: Name: .mybss.foo
+# CHECK-DEAD-NOT: Name: .mynote.foo
+# CHECK-DEAD:     Name: .mynote.bar
+
+# RUN: ld.lld --gc-sections %t.o -o %t -e anote_foo
+# RUN: llvm-readobj -S %t | FileCheck %s --check-prefix=CHECK-LIVE
+# RUN: ld.lld --gc-sections %t.o -o %t -e foo
+# RUN: llvm-readobj -S %t | FileCheck %s --check-prefix=CHECK-LIVE
+# RUN: ld.lld --gc-sections %t.o -o %t -e bss_foo
+# RUN: llvm-readobj -S %t | FileCheck %s --check-prefix=CHECK-LIVE
+
+## note_foo as the entry point does not make much sense because it is defined
+## in a non-SHF_ALLOC section. This is just to demonstrate the behavior.
+# RUN: ld.lld --gc-sections %t.o -o %t -e note_foo
+# RUN: llvm-readobj -S %t | FileCheck %s --check-prefix=CHECK-LIVE
+
+# CHECK-LIVE: Name: .myanote.foo
+# CHECK-LIVE: Name: .mytext.foo
+# CHECK-LIVE: Name: .mybss.foo
+# CHECK-LIVE: Name: .mynote.foo
+# CHECK-LIVE: Name: .mynote.bar
+
+.globl anote_foo, foo, bss_foo, note_foo
+
+.section .myanote.foo,"aG",@note,foo,comdat
+anote_foo:
+.byte 0
+
+.section .mytext.foo,"axG",@progbits,foo,comdat
+foo:
+.byte 0
+
+.section .mybss.foo,"awG",@nobits,foo,comdat
+bss_foo:
+.byte 0
+
+.section .mynote.foo,"G",@note,foo,comdat
+note_foo:
+.byte 0
+
+.section .mynote.bar,"",@note
+.byte 0

lld/test/ELF/linkerscript/discard-group.s

+# REQUIRES: arm
+## For --gc-sections, group members are retained or discarded as a unit.
+## However, discarding a section via /DISCARD/ should not discard other members
+## within the group. This is compatible with GNU ld.
+
+# RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t.o
+
+## We can discard .ARM.exidx* in a group.
+# RUN: echo 'SECTIONS { /DISCARD/ : { *(.ARM.exidx*) }}' > %t.noarm.script
+# RUN: ld.lld %t.o --gc-sections -T %t.noarm.script -o %t.noarm
+# RUN: llvm-readobj -S %t.noarm | FileCheck %s --check-prefix=NOARM --implicit-check-not='Name: .ARM.exidx'
+
+# NOARM: Name: .text
+# NOARM: Name: .note._start
+
+## Another example, we can discard SHT_NOTE in a group.
+# RUN: echo 'SECTIONS { /DISCARD/ : { *(.note*) }}' > %t.nonote.script
+# RUN: ld.lld %t.o --gc-sections -T %t.nonote.script -o %t.nonote
+# RUN: llvm-readobj -S %t.nonote | FileCheck %s --check-prefix=NONOTE --implicit-check-not='Name: .note'
+
+# NONOTE: Name: .ARM.exidx
+# NONOTE: Name: .text
+
+.section .text._start,"axG",%progbits,_start,comdat
+.globl _start
+_start:
+.fnstart
+.cantunwind
+bx lr
+.fnend
+
+.section .note._start,"G",%note,_start,comdat
+.byte 0