[lld-macho] Support EH frames under arm64

[int3]

Summary

For arm64, llvm-mc emits relocations for the target function
address like so:

ltmp:
  <CIE start>
  ...
  <CIE end>
  ... multiple FDEs ...
  <FDE start>
  <target function address - (ltmp + pcrel offset)>
  ...

If any of the FDEs in multiple FDEs get dead-stripped, then FDE start
will move to an earlier address, and ltmp + pcrel offset will no longer
reflect an accurate pcrel value. To avoid this problem, we "canonicalize"
our relocation by adding an EH_Frame symbol at FDE start, and updating
the reloc to be target function address - (EH_Frame + new pcrel offset).

[uabelho]

Hello,

When I run tests (check-all) on this commit I get the follwoing two failures:

Failed Tests (2):
  lld :: MachO/eh-frame.s
  lld :: MachO/icf-safe.s

They crash with

Command Output (stderr):
--
ld64.lld: ../../lld/MachO/UnwindInfoSection.cpp:216: void lld::macho::UnwindInfoSection::addSymbol(const lld::macho::Defined *): Assertion `!p.first->second->unwindEntry' failed.
/repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/eh-frame.s.script: line 17: 123869 Aborted                 ld64.lld -arch x86_64 -platform_version macos 11.0 11.0 -syslibroot /repo/uabelho/main-github/lld/test/MachO/Inputs/MacOSX.sdk -fatal_warnings -arch arm64 -lSystem -lc++ /repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/eh-frame.s.tmp/eh-frame-arm64.o -o /repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/eh-frame.s.tmp/eh-frame-arm64

and

Command Output (stderr):
--
ld64.lld: ../../lld/MachO/ICF.cpp:451: auto lld::macho::foldIdenticalSections()::(anonymous class)::operator()(lld::macho::ConcatInputSection *) const: Assertion `isec->icfEqClass[0] == 0' failed.
ld64.lld: ../../lld/MachO/ICF.cpp:451: auto lld::macho::foldIdenticalSections()::(anonymous class)::operator()(lld::macho::ConcatInputSection *) const: Assertion `isec->icfEqClass[0] == 0' failed.
/repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/icf-safe.s.script: line 6: 45777 Aborted                 ld64.lld -arch x86_64 -platform_version macos 11.0 11.0 -syslibroot /repo/uabelho/main-github/lld/test/MachO/Inputs/MacOSX.sdk -fatal_warnings -arch arm64 -lSystem --icf=safe -dylib -o /repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/icf-safe.s.tmp/icf-safe.dylib /repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/icf-safe.s.tmp/icf-obj.o

Any idea what's happening?

[dyung]

The test you changed is failing on the PS4 Windows/Linux bots due to the arm64 triple not being available. Can you please fix the test?

https://lab.llvm.org/buildbot/#/builders/139/builds/23051
https://lab.llvm.org/buildbot/#/builders/216/builds/5579

Command Output (stderr):
--
/home/buildbot/buildbot-root/llvm-clang-x86_64-sie-ubuntu-fast/build/bin/llvm-mc: error: unable to get target for 'arm64-apple-macos11.0', see --version and --triple.

[dyung]

In D124561#3569218, @uabelho wrote:

Hello,

When I run tests (check-all) on this commit I get the follwoing two failures:

Failed Tests (2):
  lld :: MachO/eh-frame.s
  lld :: MachO/icf-safe.s

They crash with

Command Output (stderr):
--
ld64.lld: ../../lld/MachO/UnwindInfoSection.cpp:216: void lld::macho::UnwindInfoSection::addSymbol(const lld::macho::Defined *): Assertion `!p.first->second->unwindEntry' failed.
/repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/eh-frame.s.script: line 17: 123869 Aborted                 ld64.lld -arch x86_64 -platform_version macos 11.0 11.0 -syslibroot /repo/uabelho/main-github/lld/test/MachO/Inputs/MacOSX.sdk -fatal_warnings -arch arm64 -lSystem -lc++ /repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/eh-frame.s.tmp/eh-frame-arm64.o -o /repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/eh-frame.s.tmp/eh-frame-arm64

and

Command Output (stderr):
--
ld64.lld: ../../lld/MachO/ICF.cpp:451: auto lld::macho::foldIdenticalSections()::(anonymous class)::operator()(lld::macho::ConcatInputSection *) const: Assertion `isec->icfEqClass[0] == 0' failed.
ld64.lld: ../../lld/MachO/ICF.cpp:451: auto lld::macho::foldIdenticalSections()::(anonymous class)::operator()(lld::macho::ConcatInputSection *) const: Assertion `isec->icfEqClass[0] == 0' failed.
/repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/icf-safe.s.script: line 6: 45777 Aborted                 ld64.lld -arch x86_64 -platform_version macos 11.0 11.0 -syslibroot /repo/uabelho/main-github/lld/test/MachO/Inputs/MacOSX.sdk -fatal_warnings -arch arm64 -lSystem --icf=safe -dylib -o /repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/icf-safe.s.tmp/icf-safe.dylib /repo/uabelho/main-github/llvm/build-all/tools/lld/test/MachO/Output/icf-safe.s.tmp/icf-obj.o

Any idea what's happening?

We are also seeing the same failure on our internal linux build bot, and upstream build bots as well:

• https://lab.llvm.org/buildbot/#/builders/58/builds/23914
• https://lab.llvm.org/buildbot/#/builders/36/builds/21771

[dyung]

Hi, your recommit of your changes are causing a test failure on the PS4 bots because the newly added test target arm64 is not present, can you either fixup the test to not require that or add a REQUIRES line?

https://lab.llvm.org/buildbot/#/builders/139/builds/23146

/home/buildbot/buildbot-root/llvm-clang-x86_64-sie-ubuntu-fast/build/bin/llvm-mc: error: unable to get target for 'arm64-apple-macos11.0', see --version and --triple.

[int3]

My bad, I now see you pointed it out in an earlier comment as well. Sorry about the churn.

lld/MachO/InputFiles.cpp

 
 // EH frame target addresses may be encoded as pcrel offsets. However, instead
 // of using an actual pcrel reloc, ld64 emits subtractor relocations instead.
 // This function recovers the target address from the subtractors, essentially
 // performing the inverse operation of EhRelocator.
 //
 // Concretely, we expect our relocations to write the value of `PC -
 // target_addr` to `PC`. `PC` itself is denoted by a minuend relocation that
-// points to a symbol or section plus an addend.
+// points to a symbol plus an addend.
+//
+// It is important that the minuend relocation point to a symbol within the
+// same section as the fixup value, since sections may get moved around.
+//
+// For example, for arm64, llvm-mc emits relocations for the target function
+// address like so:
+//
+//   ltmp:
+//     <CIE start>
+//     ...
+//     <CIE end>
+//     ... multiple FDEs ...
+//     <FDE start>
+//     <target function address - (ltmp + pcrel offset)>
+//     ...
+//
+// If any of the FDEs in `multiple FDEs` get dead-stripped, then `FDE start`
+// will move to an earlier address, and `ltmp + pcrel offset` will no longer
+// reflect an accurate pcrel value. To avoid this problem, we "canonicalize"
+// our relocation by adding an `EH_Frame` symbol at `FDE start`, and updating
+// the reloc to be `target function address - (EH_Frame + new pcrel offset)`.
 //
 // If `Invert` is set, then we instead expect `target_addr - PC` to be written
 // to `PC`.
 template <bool Invert = false>
 Defined *
-getTargetSymbolFromSubtraction(const InputSection *isec,
+targetSymFromCanonicalSubtractor(const InputSection *isec,
                                  std::vector<macho::Reloc>::iterator relocIt) {
-  const macho::Reloc &subtrahend = *relocIt;
-  const macho::Reloc &minuend = *std::next(relocIt);
+  macho::Reloc &subtrahend = *relocIt;
+  macho::Reloc &minuend = *std::next(relocIt);
   assert(target->hasAttr(subtrahend.type, RelocAttrBits::SUBTRAHEND));
   assert(target->hasAttr(minuend.type, RelocAttrBits::UNSIGNED));
   // Note: pcSym may *not* be exactly at the PC; there's usually a non-zero
   // addend.
   auto *pcSym = cast<Defined>(subtrahend.referent.get<macho::Symbol *>());
   Defined *target =
       cast_or_null<Defined>(minuend.referent.dyn_cast<macho::Symbol *>());
   if (!pcSym) {
     auto *targetIsec =
         cast<ConcatInputSection>(minuend.referent.get<InputSection *>());
     target = findSymbolAtOffset(targetIsec, minuend.addend);
   }
   if (Invert)
     std::swap(pcSym, target);
-  if (pcSym->isec != isec ||
-      pcSym->value - (Invert ? -1 : 1) * minuend.addend != subtrahend.offset)
+  if (pcSym->isec == isec) {
+    if (pcSym->value - (Invert ? -1 : 1) * minuend.addend != subtrahend.offset)
       fatal("invalid FDE relocation in __eh_frame");
+  } else {
+    // Ensure the pcReloc points to a symbol within the current EH frame.
+    // HACK: we should really verify that the original relocation's semantics
+    // are preserved. In particular, we should have
+    // `oldSym->value + oldOffset == newSym + newOffset`. However, we don't
+    // have an easy way to access the offsets from this point in the code; some
+    // refactoring is needed for that.
+    macho::Reloc &pcReloc = Invert ? minuend : subtrahend;
+    pcReloc.referent = isec->symbols[0];
+    assert(isec->symbols[0]->value == 0);
+    minuend.addend = pcReloc.offset * (Invert ? 1LL : -1LL);
+  }
   return target;
 }
 
 Defined *findSymbolAtAddress(const std::vector<Section *> &sections,
                              uint64_t addr) {
   Section *sec = findContainingSection(sections, &addr);
   auto *isec = cast<ConcatInputSection>(findContainingSubsection(*sec, &addr));
   return findSymbolAtOffset(isec, addr);
for (const Subsection &subsec : ehFrameSection.subsections) {
 
     EhRelocator ehRelocator(isec);
     auto cieOffRelocIt = llvm::find_if(
         isec->relocs, [=](const Reloc &r) { return r.offset == cieOffOff; });
     InputSection *cieIsec = nullptr;
     if (cieOffRelocIt != isec->relocs.end()) {
       // We already have an explicit relocation for the CIE offset.
       cieIsec =
-          getTargetSymbolFromSubtraction</*Invert=*/true>(isec, cieOffRelocIt)
+          targetSymFromCanonicalSubtractor</*Invert=*/true>(isec, cieOffRelocIt)
               ->isec;
       dataOff += sizeof(uint32_t);
     } else {
       // If we haven't found a relocation, then the CIE offset is most likely
       // embedded in the section data (AKA an "abs-ified" reloc.). Parse that
       // and generate a Reloc struct.
       uint32_t cieMinuend = reader.readU32(&dataOff);
       if (cieMinuend == 0)
for (auto it = isec->relocs.begin(); it != isec->relocs.end(); ++it) {
       if (it->offset == funcAddrOff)
         funcAddrRelocIt = it++; // Found subtrahend; skip over minuend reloc
       else if (lsdaAddrOpt && it->offset == lsdaAddrOff)
         lsdaAddrRelocIt = it++; // Found subtrahend; skip over minuend reloc
     }
 
     Defined *funcSym;
     if (funcAddrRelocIt != isec->relocs.end()) {
-      funcSym = getTargetSymbolFromSubtraction(isec, funcAddrRelocIt);
+      funcSym = targetSymFromCanonicalSubtractor(isec, funcAddrRelocIt);
     } else {
       funcSym = findSymbolAtAddress(sections, funcAddr);
       ehRelocator.makePcRel(funcAddrOff, funcSym, target->p2WordSize);
     }
     // The symbol has been coalesced, or already has a compact unwind entry.
     if (!funcSym || funcSym->getFile() != this || funcSym->unwindEntry) {
       // We must prune unused FDEs for correctness, so we cannot rely on
       // -dead_strip being enabled.
       isec->live = false;
       continue;
     }
 
     InputSection *lsdaIsec = nullptr;
     if (lsdaAddrRelocIt != isec->relocs.end()) {
-      lsdaIsec = getTargetSymbolFromSubtraction(isec, lsdaAddrRelocIt)->isec;
+      lsdaIsec = targetSymFromCanonicalSubtractor(isec, lsdaAddrRelocIt)->isec;
     } else if (lsdaAddrOpt) {
       uint64_t lsdaAddr = *lsdaAddrOpt;
       Section *sec = findContainingSection(sections, &lsdaAddr);
       lsdaIsec =
           cast<ConcatInputSection>(findContainingSubsection(*sec, &lsdaAddr));
       ehRelocator.makePcRel(lsdaAddrOff, lsdaIsec, target->p2WordSize);
     }
 

lld/test/MachO/eh-frame.s

 ## checked-in copy of `ld -r`'s output should be updated too!
 # COM: ld -r %t/eh-frame-x86_64.o -o %S/Inputs/eh-frame-x86_64-r.o
 # RUN: %lld -lSystem -lc++ %S/Inputs/eh-frame-x86_64-r.o -o %t/eh-frame-x86_64-r
 # RUN: llvm-objdump --macho --syms --indirect-symbols --unwind-info \
 # RUN:   --dwarf=frames %t/eh-frame-x86_64-r | FileCheck %s -D#BASE=0x100000000 -D#DWARF_ENC=4
 # RUN: llvm-nm -m %t/eh-frame-x86_64-r | FileCheck %s --check-prefix NO-EH-SYMS
 # RUN: llvm-readobj --section-headers %t/eh-frame-x86_64-r | FileCheck %s --check-prefix=ALIGN -D#ALIGN=3
 
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-macos11.0 %s -o %t/eh-frame-arm64.o
+# RUN: %lld -arch arm64 -lSystem -lc++ %t/eh-frame-arm64.o -o %t/eh-frame-arm64
+# RUN: llvm-objdump --macho --syms --indirect-symbols --unwind-info \
+# RUN:   --dwarf=frames %t/eh-frame-arm64 | FileCheck %s -D#BASE=0x100000000 -D#DWARF_ENC=3
+# RUN: llvm-nm -m %t/eh-frame-arm64 | FileCheck %s --check-prefix NO-EH-SYMS
+
+# COM: ld -r %t/eh-frame-arm64.o -o %S/Inputs/eh-frame-arm64-r.o
+# RUN: %lld -arch arm64 -lSystem -lc++ %S/Inputs/eh-frame-arm64-r.o -o %t/eh-frame-arm64-r
+# RUN: llvm-objdump --macho --syms --indirect-symbols --unwind-info \
+# RUN:   --dwarf=frames %t/eh-frame-arm64-r | FileCheck %s -D#BASE=0x100000000 -D#DWARF_ENC=3
+# RUN: llvm-nm -m %t/eh-frame-arm64-r | FileCheck %s --check-prefix NO-EH-SYMS
+
 # ALIGN:      Name: __eh_frame
 # ALIGN-NEXT: Segment: __TEXT
 # ALIGN-NEXT: Address:
 # ALIGN-NEXT: Size:
 # ALIGN-NEXT: Offset:
 # ALIGN-NEXT: Alignment: [[#ALIGN]]
 
 # NO-EH-SYMS-NOT: __eh_frame