[LLD][ELF][ARM] Support /DISCARD/ of subset of .ARM.exidx sections

[psmith]

Summary

Both the .ARM.exidx and .eh_frame sections have a custom SyntheticSection that acts as a container for the InputSections. The InputSections are added to the SyntheticSection prior to /DISCARD/ which limits the affect a /DISCARD/ can have to the whole SyntheticSection. In the majority of cases this is sufficient as it is not common to discard subsets of the InputSections. The Linux kernel has one of these scripts which has something like:

/DISCARD/ : { *(.ARM.exidx.exit.text) *(.ARM.extab.exit.text) ... }

The .ARM.exidx.exit.text are not discarded because the InputSection has been transferred to the Synthetic Section. The *(.ARM.extab.exit.text) sections have not so they are discarded. When we come to write out the .ARM.exidx sections the dangling references from .ARM.exidx.exit.text to .ARM.extab.exit.text currently cause relocation out of range errors, but could as easily cause a fatal error message if we check for dangling references at relocation time.

This patch attempts to respect the /DISCARD/ command by running it on the .ARM.exidx InputSections stored in the SyntheticSection.

The .eh_frame is in theory affected by this problem, but I don't think that there is a dangling reference problem that can happen with these sections.

Fixes remaining part of pr44824 (https://bugs.llvm.org/show_bug.cgi?id=44824)

[MaskRay]

If I understand it correctly,

combineEhSections()
  .ARM.exidx.* are removed from inputSections
script->processSectionCommands()
  /DISCARD/ is handled. computeInputSections can find the synthetic section .ARM.exidx but not individual .ARM.exidx.*
writeResult<ELFT>()
  ...
    writeSections
      ARMExidxSyntheticSection::writeTo called on .ARM.exidx.exit.text which should have been discarded. This causes a relocation overflow

This patch tactfully introduces a mechanism to discard such synthetic sections. Looks great! One nit about an unneeded function.

lld/ELF/LinkerScript.cpp

453

Delete the function which is only called once.

491

cmd->sectionBases = computeInputSections(cmd, inputSections);

[psmith]

Thanks for the review. I've applied the suggestion to remove the function.

This introduces a mechanism to discard individual .ARM.exidx.foo sections from the ARMExidx SyntheticSection. To explain the original problem a bit better:
.ARM.exidx are Exception Index sections. They form an ordered table that can be binary searched to find the unwinding instructions for an exception coming from a given address. If the unwind information is small then it is inlined into the .ARM.exidx section. If the unwind information is large a .ARM.extab section is created to contain the unwind information, the .ARM.exidx section entry then becomes a pc-relative reference to the .ARM.extab.

.text.small <- SHF_LINK_ORDER .ARM.exidx.small
.text.large <- SHF_LINK_ORDER .ARM.exidx.large -> .ARM.extab.large

If /DISCARD/ contains both .ARM.exidx.large and .ARM.extab.large then if we only discard .ARM.extab.large (due to .ARM.exidx.large being hidden away in the SyntheticSection, then .ARM.exidx.large has a dangling reference which causes an error at relocation time.

lld/ELF/LinkerScript.h

class LinkerScript final {
 
   void addSymbol(SymbolAssignment *cmd);
   void assignSymbol(SymbolAssignment *cmd, bool inSec);
   void setDot(Expr e, const Twine &loc, bool inSec);
   void expandOutputSection(uint64_t size);
   void expandMemoryRegions(uint64_t size);
 
   std::vector<InputSectionBase *>
-  computeInputSections(const InputSectionDescription *);
+  computeInputSections(const InputSectionDescription *,
+                       ArrayRef<InputSectionBase *>);
 
   std::vector<InputSectionBase *> createInputSectionList(OutputSection &cmd);
 
+  void discardSynthetic(OutputSection &);
+
   std::vector<size_t> getPhdrIndices(OutputSection *sec);
 
   MemoryRegion *findMemoryRegion(OutputSection *sec);
 
   void switchTo(OutputSection *sec);
   uint64_t advance(uint64_t size, unsigned align);
   void output(InputSection *sec);
 

lld/ELF/LinkerScript.cpp

if (pat.sortInner == SortSectionPolicy::Default)
     sortSections(vec, config->sortSection);
   else
     sortSections(vec, pat.sortInner);
   sortSections(vec, pat.sortOuter);
 }
 
 // Compute and remember which sections the InputSectionDescription matches.
 std::vector<InputSectionBase *>
-LinkerScript::computeInputSections(const InputSectionDescription *cmd) {
+LinkerScript::computeInputSections(const InputSectionDescription *cmd,
+                                   ArrayRef<InputSectionBase *> sections) {
   std::vector<InputSectionBase *> ret;
 
   // Collects all sections that satisfy constraints of Cmd.
   for (const SectionPattern &pat : cmd->sectionPatterns) {
     size_t sizeBefore = ret.size();
 
-    for (InputSectionBase *sec : inputSections) {
+    for (InputSectionBase *sec : sections) {
       if (!sec->isLive() || sec->parent)
         continue;
 
       // For -emit-relocs we have to ignore entries like
       //   .rela.dyn : { *(.rela.data) }
       // which are common because they are in the default bfd script.
       // We do not ignore SHT_REL[A] linker-synthesized sections here because
       // want to support scripts that do custom layout for them.
for (const SectionPattern &pat : cmd->sectionPatterns) {
     sortInputSections(
         MutableArrayRef<InputSectionBase *>(ret).slice(sizeBefore), pat);
   }
   return ret;
 }
 
 void LinkerScript::discard(InputSectionBase *s) {
   if (s == in.shStrTab || s == mainPart->relrDyn)
     error("discarding " + s->name + " section is not allowed");
 
   // You can discard .hash and .gnu.hash sections by linker scripts. Since
   // they are synthesized sections, we need to handle them differently than
   // other regular sections.
   if (s == mainPart->gnuHashTab)
     mainPart->gnuHashTab = nullptr;
   if (s == mainPart->hashTab)
     mainPart->hashTab = nullptr;
 
   s->markDead();
   s->parent = nullptr;
   for (InputSection *ds : s->dependentSections)
     discard(ds);
 }
 
+void LinkerScript::discardSynthetic(OutputSection &outCmd) {
+  for (Partition &part : partitions) {
+    if (!part.armExidx || !part.armExidx->isLive())
+      continue;
+    std::vector<InputSectionBase *> secs(part.armExidx->exidxSections.begin(),
+                                         part.armExidx->exidxSections.end());
+    for (BaseCommand *base : outCmd.sectionCommands)
+      if (auto *cmd = dyn_cast<InputSectionDescription>(base)) {
+        std::vector<InputSectionBase *> matches =
+            computeInputSections(cmd, secs);
+        for (InputSectionBase *s : matches)
+          discard(s);
+      }
+  }
+}
+
 std::vector<InputSectionBase *>
 LinkerScript::createInputSectionList(OutputSection &outCmd) {
   std::vector<InputSectionBase *> ret;
 
   for (BaseCommand *base : outCmd.sectionCommands) {
     if (auto *cmd = dyn_cast<InputSectionDescription>(base)) {
-      cmd->sectionBases = computeInputSections(cmd);
+      cmd->sectionBases = computeInputSections(cmd, inputSections);
       for (InputSectionBase *s : cmd->sectionBases)
         s->parent = &outCmd;
       ret.insert(ret.end(), cmd->sectionBases.begin(), cmd->sectionBases.end());
     }
   }
   return ret;
 }
 
 // Create output sections described by SECTIONS commands.
 void LinkerScript::processSectionCommands() {
   size_t i = 0;
   for (BaseCommand *base : sectionCommands) {
     if (auto *sec = dyn_cast<OutputSection>(base)) {
       std::vector<InputSectionBase *> v = createInputSectionList(*sec);
 
       // The output section name `/DISCARD/' is special.
       // Any input section assigned to it is discarded.
       if (sec->name == "/DISCARD/") {
         for (InputSectionBase *s : v)
           discard(s);
+        discardSynthetic(*sec);
         sec->sectionCommands.clear();
         continue;
       }
 
       // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
       // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
       // sections satisfy a given constraint. If not, a directive is handled
       // as if it wasn't present from the beginning.

lld/ELF/SyntheticSections.cpp

: SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, config->wordsize,
                        ".rld_map") {}
 
 ARMExidxSyntheticSection::ARMExidxSyntheticSection()
     : SyntheticSection(SHF_ALLOC | SHF_LINK_ORDER, SHT_ARM_EXIDX,
                        config->wordsize, ".ARM.exidx") {}
 
 static InputSection *findExidxSection(InputSection *isec) {
   for (InputSection *d : isec->dependentSections)
-    if (d->type == SHT_ARM_EXIDX)
+    if (d->type == SHT_ARM_EXIDX && d->isLive())
       return d;
   return nullptr;
 }
 
 static bool isValidExidxSectionDep(InputSection *isec) {
   return (isec->flags & SHF_ALLOC) && (isec->flags & SHF_EXECINSTR) &&
          isec->getSize() > 0;
 }

lld/test/ELF/arm-exidx-partial-discard-exidx.s

+// REQUIRES: arm
+// RUN: llvm-mc --arm-add-build-attributes --triple=armv7a-linux-gnueabihf -filetype=obj %s -o %t.o
+// RUN: echo "SECTIONS { \
+// RUN:         /DISCARD/ : { *(.ARM.exidx.exit.text) *(.ARM.extab.exit.text)} \
+// RUN:         . = 0x90000000; \
+// RUN:         .ARM.exidx : { *(.ARM.exidx) } \
+// RUN:         .text : { *(.text) } \
+// RUN:         .exit.text : { *(.exit.text) } \
+// RUN:         .rodata : { *(.rodata) } \
+// RUN: } " > %t.script
+// RUN: ld.lld --script %t.script %t.o -o %t
+// RUN: llvm-readelf -x .ARM.exidx %t | FileCheck %s
+
+/// The linker script /DISCARDS/ the .ARM.exidx and .ARM.extab for the
+/// .exit.text . If we do not discard both sections we will end up with
+/// a dangling reference. We expect no linker error for an out of range
+/// relocation/dangling reference and just a single .ARM.exidx entry
+/// for _start and an entry for the terminating sentinel.
+
+// CHECK: Hex dump of section '.ARM.exidx':
+// CHECK-NEXT: 0x90000000 10000000 01000000 10000000 01000000
+// CHECK-NOT:  0x90000010
+ .text
+ .global _start
+ .type _start, %function
+_start:
+ .fnstart
+ bx lr
+ .cantunwind
+ .fnend
+
+ .section .exit.text, "ax", %progbits
+ .global exit_text
+ .type exit_text, %function
+exit_text:
+  .fnstart
+  bx lr
+ .personality __gxx_personality_v0
+ .handlerdata
+ .long 0
+ .fnend
+
+/// Dummy definition for a reference from the personality routine created by
+/// the assembler, use .data to avoid generating a cantunwind table.
+ .section .rodata
+ .global __aeabi_unwind_cpp_pr0
+__aeabi_unwind_cpp_pr0:
+ .word 0