[ELF] Support -r --gc-sections

[MaskRay]

Summary

-r --gc-sections is usually not useful because it just makes intermediate output
smaller. https://bugs.llvm.org/show_bug.cgi?id=46700#c7 mentions a use case:
validating the absence of undefined symbols ealier than in the final link.

After D84129 (SHT_GROUP support in -r links), we can support -r
--gc-sections without extra code. So let's allow it.

[MaskRay]

lld/test/ELF/relocatable-gc.s

27

Note that GNU ld will error if neither -e nor -u is specified, although --init can serve as GC roots as well.

I don't find the GNU ld error particularly useful, so I just don't bother implementing it.

[jhenderson]

The pre-merge check seems to be saying there are failing tests?

[psmith]

I guess if the use case for -r is a kernel module then garbage collection can make sense as the "object" is not relinked. What happens when there is no GC root? I think it will be worth detecting that and turning GC off as otherwise everything will get removed which is unlikely to be what was wanted.

[MaskRay]

In D84131#2161527, @psmith wrote:

I guess if the use case for -r is a kernel module then garbage collection can make sense as the "object" is not relinked. What happens when there is no GC root? I think it will be worth detecting that and turning GC off as otherwise everything will get removed which is unlikely to be what was wanted.

GNU ld has a diagnostic gc-sections requires either an entry or an undefined symbol (the resolution to https://sourceware.org/bugzilla/show_bug.cgi?id=26265 added --init and --fini).
We have other GC roots like SHT_INIT_ARRAY and C identifier sections. I don't know whether we want such a diagnostic. Users of the feature usually come from GNU ld. Failing to set a GC root can get pretty obvious broken output. I don't thing the diagnostic is very necessary.

[MaskRay]

In D84131#2161500, @jhenderson wrote:

The pre-merge check seems to be saying there are failing tests?

It depends on D84129. Harbormaster probably does not support dependent revisions.

[jhenderson]

lld/ELF/InputFiles.cpp

947–948

Whilst you're moving this comment, some grammar fixes:

apply relocation -> apply relocations
to output -> to the output

951–955

similar like we -> like we
for the case when linker script -> when a linker script
the "/DISCARD/" -> a "/DISCARD/" output section
have to handle such case and not to crash -> have to handle such cases without crashing

lld/test/ELF/relocatable-gc.s

7–8

I'm not sure I follow from this why group signature symbols and STT_SECTION symbols are kept? I think this explanation needs expanding.

21

"Other group members"

[MaskRay]

Simplify InputFiles.cpp SHT_REL[A] handling
Add a test comment

lld/ELF/InputFiles.cpp

951–955

The two if can be merged. I merged them.

[jhenderson]

LGTM, with one remaining nit.

lld/ELF/InputFiles.cpp

946–956

returning -> return

951–955

Makes sense!

[MaskRay]

returning -> return

[grimar]

LGTM

lld/ELF/Driver.cpp

if (config->strip == StripPolicy::All && config->emitRelocs)
     error("--strip-all and --emit-relocs may not be used together");
 
   if (config->zText && config->zIfuncNoplt)
     error("-z text and -z ifunc-noplt may not be used together");
 
   if (config->relocatable) {
     if (config->shared)
       error("-r and -shared may not be used together");
-    if (config->gcSections)
-      error("-r and --gc-sections may not be used together");
     if (config->gdbIndex)
       error("-r and --gdb-index may not be used together");
     if (config->icf != ICFLevel::None)
       error("-r and --icf may not be used together");
     if (config->pie)
       error("-r and -pie may not be used together");
     if (config->exportDynamic)
       error("-r and --export-dynamic may not be used together");

lld/ELF/InputFiles.cpp

case SHT_REL: {
     // because applying relocations at end of linking changes section
     // contents. So, we simply handle such sections as non-mergeable ones.
     // Degrading like this is acceptable because section merging is optional.
     if (auto *ms = dyn_cast<MergeInputSection>(target)) {
       target = toRegularSection(ms);
       this->sections[sec.sh_info] = target;
     }
 
-    // This section contains relocation information.
-    // If -r is given, we do not interpret or apply relocation
-    // but just copy relocation sections to output.
-    if (config->relocatable) {
-      InputSection *relocSec = make<InputSection>(*this, sec, name);
-      // We want to add a dependency to target, similar like we do for
-      // -emit-relocs below. This is useful for the case when linker script
-      // contains the "/DISCARD/". It is perhaps uncommon to use a script with
-      // -r, but we faced it in the Linux kernel and have to handle such case
-      // and not to crash.
-      target->dependentSections.push_back(relocSec);
-      return relocSec;
-    }
-
     if (target->firstRelocation)
       fatal(toString(this) +
             ": multiple relocation sections to one section are not supported");
 
     if (sec.sh_type == SHT_RELA) {
       ArrayRef<Elf_Rela> rels = CHECK(getObj().relas(&sec), this);
       target->firstRelocation = rels.begin();
       target->numRelocations = rels.size();
       target->areRelocsRela = true;
     } else {
       ArrayRef<Elf_Rel> rels = CHECK(getObj().rels(&sec), this);
       target->firstRelocation = rels.begin();
       target->numRelocations = rels.size();
       target->areRelocsRela = false;
     }
     assert(isUInt<31>(target->numRelocations));
 
-    // Relocation sections processed by the linker are usually removed
-    // from the output, so returning `nullptr` for the normal case.
-    // However, if -emit-relocs is given, we need to leave them in the output.
-    // (Some post link analysis tools need this information.)
-    if (config->emitRelocs) {
-      InputSection *relocSec = make<InputSection>(*this, sec, name);
-      // We will not emit relocation section if target was discarded.
-      target->dependentSections.push_back(relocSec);
-      return relocSec;
-    }
-    return nullptr;
-  }
+    // Relocation sections are usually removed from the output, so return
+    // `nullptr` for the normal case. However, if -r or --emit-relocs is
+    // specified, we need to copy them to the output. (Some post link analysis
+    // tools specify --emit-relocs to obtain the information.)
+    if (!config->relocatable && !config->emitRelocs)
+      return nullptr;
+    // If the relocated section is discarded (due to /DISCARD/ or
+    // --gc-sections), the relocation section should be discarded as well.
   }
 
   // The GNU linker uses .note.GNU-stack section as a marker indicating
   // that the code in the object file does not expect that the stack is
   // executable (in terms of NX bit). If all input files have the marker,
   // the GNU linker adds a PT_GNU_STACK segment to tells the loader to
   // make the stack non-executable. Most object files have this section as
   // of 2017.

lld/test/ELF/driver.test

 # RUN: ld.lld -shared %t -o %t.so
 # RUN: not ld.lld -r %t.so %t -o /dev/null 2>&1 | FileCheck -check-prefix=ERR %s
 # ERR: attempted static link of dynamic object
 
 ## Attempt to use -r and -shared together
 # RUN: not ld.lld -r -shared %t -o /dev/null 2>&1 | FileCheck -check-prefix=ERR2 %s
 # ERR2: -r and -shared may not be used together
 
-## Attempt to use -r and --gc-sections together
-# RUN: not ld.lld -r --gc-sections %t -o /dev/null 2>&1 | FileCheck -check-prefix=ERR3 %s
-# ERR3: -r and --gc-sections may not be used together
-
 ## Attempt to use -r and --gdb-index together
 # RUN: not ld.lld -r --gdb-index %t -o /dev/null 2>&1 | FileCheck -check-prefix=ERR4 %s
 # ERR4: -r and --gdb-index may not be used together
 
 ## Attempt to use -r and --icf together
 # RUN: not ld.lld -r --icf=all %t -o /dev/null 2>&1 | FileCheck -check-prefix=ERR5 %s
 # ERR5: -r and --icf may not be used together
 

lld/test/ELF/relocatable-gc.s

+# REQUIRES: x86
+## Test -r --gc-sections.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+
+## By default all regular sections are discarded. We currently don't track
+## usage of group signature symbols and will retain them and their associated
+## STT_SECTION symbols.
+# RUN: ld.lld -r --gc-sections --print-gc-sections %t.o -o %t
+# RUN: llvm-readelf -S -s %t | FileCheck %s
+
+# CHECK:      [ 1] .group
+# CHECK-NEXT: [ 2] .note.GNU-stack
+
+# CHECK:      Symbol table '.symtab' contains 3 entries:
+# CHECK-NEXT: Num:
+# CHECK-NEXT: 0:
+# CHECK-NEXT: 1: {{.*}} NOTYPE  LOCAL DEFAULT  1 group
+# CHECK-NEXT: 2: {{.*}} SECTION LOCAL DEFAULT  1
+
+## -u keeps .text.bar alive. Other group members are kept alive as well.
+# RUN: ld.lld -r --gc-sections -u bar %t.o -o - | llvm-readelf -Ss - | \
+# RUN:   FileCheck %s --check-prefix=KEEP_GROUP
+## -e, --init and --fini are similar.
+# RUN: ld.lld -r --gc-sections -e bar %t.o -o - | llvm-readelf -Ss - | \
+# RUN:   FileCheck %s --check-prefix=KEEP_GROUP
+# RUN: ld.lld -r --gc-sections --init=bar %t.o -o - | llvm-readelf -Ss - | \
+# RUN:   FileCheck %s --check-prefix=KEEP_GROUP
+# RUN: ld.lld -r --gc-sections --fini=bar %t.o -o - | llvm-readelf -Ss - | \
+# RUN:   FileCheck %s --check-prefix=KEEP_GROUP
+
+# KEEP_GROUP:      [ 1] .group
+# KEEP_GROUP-NEXT: [ 2] .text.bar
+# KEEP_GROUP-NEXT: [ 3] .text.foo
+# KEEP_GROUP-NEXT: [ 4] .note.GNU-stack
+
+# KEEP_GROUP:      Symbol table '.symtab' contains 7 entries:
+# KEEP_GROUP:      4: {{.*}} SECTION
+# KEEP_GROUP-NEXT: 5: {{.*}}   2 bar
+# KEEP_GROUP-NEXT: 6: {{.*}}   3 foo
+
+## If .text is retained, its referenced qux and .fred are retained as well.
+## fred_und is used (by .fred) and thus emitted.
+## Note, GNU ld does not retain qux.
+# RUN: ld.lld -r --gc-sections -e _start %t.o -o %tstart.ro
+# RUN: llvm-readelf -Ss %tstart.ro | FileCheck %s --check-prefix=KEEP_START
+
+# KEEP_START:      [ 1] .text
+# KEEP_START-NEXT: [ 2] .rela.text
+# KEEP_START-NEXT: [ 3] qux
+# KEEP_START-NEXT: [ 4] .group
+# KEEP_START-NEXT: [ 5] .fred
+# KEEP_START-NEXT: [ 6] .rela.fred
+# KEEP_START-NEXT: [ 7] .note.GNU-stack
+
+# KEEP_START:      Symbol table '.symtab' contains 10 entries:
+# KEEP_START:      5: {{.*}} SECTION
+# KEEP_START-NEXT: 6: {{.*}} UND __start_qux
+# KEEP_START-NEXT: 7: {{.*}}   1 _start
+# KEEP_START-NEXT: 8: {{.*}}   5 fred
+# KEEP_START-NEXT: 9: {{.*}} UND fred_und
+
+.section qux,"a",@progbits
+  .byte 0
+
+.text
+.globl _start, bar, foo, fred
+_start:
+  call fred
+  .quad __start_qux
+
+.section .text.bar,"axG",@progbits,group,comdat
+bar:
+  .byte 1
+.section .text.foo,"axG",@progbits,group,comdat
+foo:
+  .byte 2
+.section .fred,"ax",@progbits
+fred:
+  call fred_und