[LLD][ARM] Garbage collection support for .ARM.exidx sections

[peter.smith]

Summary

The .ARM.exidx sections have a reverse dependency on the InputSections that they have a link order dependency to. In effect they should be live only if the InputSection they refer to via the sh_link field is live.

I've used a single pointer to InputSection rather than a vector as there is an InputSection can only have at most one InputSection (.ARM.exidx) with a SHF_LINK_ORDER dependency on it.

This has been split off from https://reviews.llvm.org/D25127 which contains the basic .ARM.exidx recognition and sorting. It implements Rui's suggestion of adding the reverse dependency to InputSections.

The lld changes don't depend on D25127 but the test case may do as it checks the contents of the .ARM.exidx section.

[ruiu]

ELF/InputFiles.cpp

264

Can you make this a separate function, say, initializeARMLinkOrderSection, and call it from ObjectFile::parse?

Please do this only when Config->GcSections is true.

ELF/InputSection.h

232

Variable names should start with uppercase letters.

Is it guaranteed that a section has at most one corresponding .ARM.exidx section?

test/ELF/arm-exidx-gc.s

14

I don't know much about ARM assembly, but do you actually need this amount of assembly code to test your feature?

[peter.smith]

Thanks for the comments. I've made the suggested review changes.

Yes it is guaranteed that there is a 1:1 mapping between a .ARM.exidx section and an executable section. It is stated in the exceptions spec[*] and if it weren't true then SHF_LINK_ORDER couldn't work reliably.

I've cut the assembly down a bit in the test. The difficulty often isn't the ARM assembly, it is provoking the assembler to generate the necessary exception tables. For example .cantunwind and .handlerdata need .fnstart and .fnend to be accepted.

• 4.4 The object producer interface (http://infocenter.arm.com/help/topic/com.arm.doc.ihi0038b/IHI0038B_ehabi.pdf)

An object producer must generate:

• One fragment of index table for each code section.
• One exception-handling table entry corresponding to each function that may need to be unwound.

Each fragment of index table (read-only data) must be generated in its own ELF section. It must contain an index entry for each non-leaf function in the associated code section, in the same order as that of the functions in the code section. The index table section name must be .ARM.exidx optionally followed by further characters. The section type must be SHT_ARM_EXIDX (see [AAELF]). It must have the SHF_LINK_ORDER flag set in the sh_flags field of its section header and be linked to its associated code section via the sh_link field of its section header.

[ruiu]

LGTM

ELF/InputFiles.cpp

148

clang-format-diff please.

275

Reverse the condition and continue earlier.

279

It is not expected to fail, so dyn_cast -> cast.

[• rafael]

Why do you need to store the dependency?

It seem that you should be able to just run mark sections live normally and then do one last pass over the sections. Any SHF_LINK_ORDER pointer to a live section makes the current one live too.

[peter.smith]

The initial patch did start that way. The SHF_LINK_ORDER sections that become live may make other sections that have further SHF_LINK_ORDER dependencies live so it ends up needing to converge. The move to adding the reverse dependency came from an earlier review comment.

I'll try and see what impact the extra field in InputSection has in terms of performance. I've not got a setup for benchmarking right now but I'll take a look at setting one up.

Another possibility is to store the reverse dependency in a map so that only the ARM Target pays the performance cost.

[ruiu]

We need to store reverse edges somewhere. It doesn't have to be InputSection, but I think this is a good place to add them.

[peter.smith]

Committed revision 283734 with Rui's final suggestions above.

ELF/InputFiles.h

public:
 
   // SymbolBodies and Thunks for sections in this file are allocated
   // using this buffer.
   llvm::BumpPtrAllocator Alloc;
 
 private:
   void initializeSections(llvm::DenseSet<StringRef> &ComdatGroups);
   void initializeSymbols();
+  void initializeReverseDependencies();
   InputSectionBase<ELFT> *getRelocTarget(const Elf_Shdr &Sec);
   InputSectionBase<ELFT> *createInputSection(const Elf_Shdr &Sec);
 
   bool shouldMerge(const Elf_Shdr &Sec);
   SymbolBody *createSymbolBody(const Elf_Sym *Sym);
 
   // List of all sections defined by this file.
   std::vector<InputSectionBase<ELFT> *> Sections;

ELF/InputFiles.cpp

template <class ELFT> uint32_t elf::ObjectFile<ELFT>::getMipsGp0() const {
   return 0;
 }
 
 template <class ELFT>
 void elf::ObjectFile<ELFT>::parse(DenseSet<StringRef> &ComdatGroups) {
   // Read section and symbol tables.
   initializeSections(ComdatGroups);
   initializeSymbols();
+  if (Config->GcSections && Config->EMachine == EM_ARM )
+    initializeReverseDependencies();
 }
 
 // Sections with SHT_GROUP and comdat bits define comdat section groups.
 // They are identified and deduplicated by group name. This function
 // returns a group name.
 template <class ELFT>
 StringRef elf::ObjectFile<ELFT>::getShtGroupSignature(const Elf_Shdr &Sec) {
   const ELFFile<ELFT> &Obj = this->ELFObj;
case SHT_SYMTAB_SHNDX:
       break;
     case SHT_STRTAB:
     case SHT_NULL:
       break;
     default:
       Sections[I] = createInputSection(Sec);
     }
   }
 }
 
+// .ARM.exidx sections have a reverse dependency on the InputSection they
+// have a SHF_LINK_ORDER dependency, this is identified by the sh_link.
+template <class ELFT>
+void elf::ObjectFile<ELFT>::initializeReverseDependencies() {
+  unsigned I = -1;
+  for (const Elf_Shdr &Sec : this->ELFObj.sections()) {
+    ++I;
+    if (Sections[I] == &InputSection<ELFT>::Discarded)
+      continue;
+    if (Sec.sh_flags & SHF_LINK_ORDER) {
+      if (Sec.sh_link >= Sections.size())
+        fatal(getFilename(this) + ": invalid sh_link index: " +
+              Twine(Sec.sh_link));
+      auto *IS = dyn_cast<InputSection<ELFT>>(Sections[Sec.sh_link]);
+      IS->DependentSection = Sections[I];
+    }
+  }
+}
+
 template <class ELFT>
 InputSectionBase<ELFT> *
 elf::ObjectFile<ELFT>::getRelocTarget(const Elf_Shdr &Sec) {
   uint32_t Idx = Sec.sh_info;
   if (Idx >= Sections.size())
     fatal(getFilename(this) + ": invalid relocated section index: " +
           Twine(Idx));
   InputSectionBase<ELFT> *Target = Sections[Idx];

ELF/InputSection.h

public:
 
   // Relocation sections that refer to this one.
   llvm::TinyPtrVector<const Elf_Shdr *> RelocSections;
 
   // The offset from beginning of the output sections this section was assigned
   // to. The writer sets a value.
   uint64_t OutSecOff = 0;
 
+  // InputSection that is dependent on us (reverse dependency for GC)
+  InputSectionBase<ELFT> *DependentSection = nullptr;
+
   static bool classof(const InputSectionBase<ELFT> *S);
 
   InputSectionBase<ELFT> *getRelocatedSection();
 
   // Register thunk related to the symbol. When the section is written
   // to a mmap'ed file, target is requested to write an actual thunk code.
   // Now thunks is supported for MIPS and ARM target only.
   void addThunk(const Thunk<ELFT> *T);

ELF/MarkLive.cpp

for (const typename ELFT::Shdr *RelSec : Sec.RelocSections) {
     if (RelSec->sh_type == SHT_RELA) {
       for (const typename ELFT::Rela &Rel : Obj.relas(RelSec))
         Fn(resolveReloc(Sec, Rel));
     } else {
       for (const typename ELFT::Rel &Rel : Obj.rels(RelSec))
         Fn(resolveReloc(Sec, Rel));
     }
   }
+  if (Sec.DependentSection)
+    Fn({Sec.DependentSection, 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

test/ELF/arm-exidx-gc.s

+// RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
+// RUN: ld.lld %t -o %t2 --gc-sections 2>&1
+// RUN: llvm-objdump -d -triple=armv7a-none-linux-gnueabi %t2 | FileCheck %s
+// RUN: llvm-objdump -s -triple=armv7a-none-linux-gnueabi %t2 | FileCheck -check-prefix=CHECK-EXIDX %s
+// REQUIRES: arm
+
+// Test the behavior of .ARM.exidx sections under garbage collection
+// A .ARM.exidx section is live if it has a relocation to a live executable
+// section.
+// A .ARM.exidx section may have a relocation to a .ARM.extab section, if the
+// .ARM.exidx is live then the .ARM.extab section is live
+
+ .syntax unified
+ .section .text.func1, "ax",%progbits
+ .global func1
+func1:
+ .fnstart
+ bx lr
+ .save {r7, lr}
+ .setfp r7, sp, #0
+ .fnend
+
+ .section .text.unusedfunc1, "ax",%progbits
+ .global unusedfunc1
+unusedfunc1:
+ .fnstart
+ bx lr
+ .cantunwind
+ .fnend
+
+ // Unwinding instructions for .text2 too large for an inline entry ARM.exidx
+ // entry. A separate .ARM.extab section is created to hold the unwind entries
+ // The .ARM.exidx table entry has a reference to the .ARM.extab section.
+ .section .text.func2, "ax",%progbits
+ .global func2
+func2:
+ .fnstart
+ bx lr
+ .personality __gxx_personality_v0
+ .handlerdata
+ .section .text.func2
+ .fnend
+
+ // An unused function with a reference to a .ARM.extab section. Both should
+ // be removed by gc.
+ .section .text.unusedfunc2, "ax",%progbits
+ .global unusedfunc2
+unusedfunc2:
+ .fnstart
+ bx lr
+ .personality __gxx_personality_v1
+ .handlerdata
+ .section .text.unusedfunc2
+ .fnend
+
+ // Dummy implementation of personality routines to satisfy reference from
+ // exception tables
+ .section .text.__gcc_personality_v0, "ax", %progbits
+ .global __gxx_personality_v0
+__gxx_personality_v0:
+ .fnstart
+ bx lr
+ .cantunwind
+ .fnend
+
+ .section .text.__gcc_personality_v1, "ax", %progbits
+ .global __gxx_personality_v1
+__gxx_personality_v1:
+ .fnstart
+ bx lr
+ .cantunwind
+ .fnend
+
+ .section .text.__aeabi_unwind_cpp_pr0, "ax", %progbits
+ .global __aeabi_unwind_cpp_pr0
+__aeabi_unwind_cpp_pr0:
+ .fnstart
+ bx lr
+ .cantunwind
+ .fnend
+
+// Entry point for GC
+ .text
+ .global _start
+_start:
+ bl func1
+ bl func2
+ bx lr
+
+// GC should have only removed unusedfunc1 and unusedfunc2 the personality
+// routines are kept alive by references from live .ARM.exidx and .ARM.extab
+// sections
+// CHECK: Disassembly of section .text:
+// CHECK-NEXT: _start:
+// CHECK-NEXT:   11000:       01 00 00 eb     bl      #4 <func1>
+// CHECK-NEXT:   11004:       01 00 00 eb     bl      #4 <func2>
+// CHECK-NEXT:   11008:       1e ff 2f e1     bx      lr
+// CHECK: func1:
+// CHECK-NEXT:   1100c:       1e ff 2f e1     bx      lr
+// CHECK: func2:
+// CHECK-NEXT:   11010:       1e ff 2f e1     bx      lr
+// CHECK: __gxx_personality_v0:
+// CHECK-NEXT:   11014:       1e ff 2f e1     bx      lr
+// CHECK: __aeabi_unwind_cpp_pr0:
+// CHECK-NEXT:   11018:       1e ff 2f e1     bx      lr
+
+// GC should have removed table entries for unusedfunc1, unusedfunc2
+// and __gxx_personality_v1
+// CHECK-NOT: unusedfunc1
+// CHECK-NOT: unusedfunc2
+// CHECK-NOT: __gxx_personality_v1
+
+// CHECK-EXIDX-NOT: Contents of section .ARM.extab.text.unusedfunc2:
+// CHECK-EXIDX: Contents of section .ARM.exidx:
+// 100d4 + f38 = 1100c = func1
+// 100dc + f34 = 11010 = func2 (100e0 + 14 = 100f4 = .ARM.extab.text.func2)
+// CHECK-EXIDX-NEXT: 100d4 380f0000 08849780 340f0000 14000000
+// 100e4 + f30 = 11014 = __gxx_personality_v0
+// 100ec + f2c = 11018 = __aeabi_unwind_cpp_pr0
+// CHECK-EXIDX-NEXT: 100e4 300f0000 01000000 2c0f0000 01000000
+// CHECK-EXIDX-NEXT: Contents of section .ARM.extab.text.func2:
+// 100f4 + f20 = 11014 = __gxx_personality_v0
+// CHECK-EXIDX-NEXT: 100f4 200f0000 b0b0b000