[ELF] Fix branch range computation when picking ThunkSection

[MaskRay]

Summary

Similar to D117734. Take AArch64 as an example when the branch range is +-0x8000000.

getISDThunkSec returns ts when src-0x8000000-r_addend <= tsBase < src-0x8000000
and the new thunk will be placed in ts (ts->addThunk(t)). However, the new
thunk (at the end of ts) may be unreachable from src. In the next pass,
normalizeExistingThunk reverts the relocation back to the original target.
Then a new thunk is created and the same ts is picked as before. The ts is
still unreachable.

I have observed it in one test with a sufficiently large r_addend (47664): there
are initially 245 Thunk's, then in each pass 14 new Thunk's are created and get
appended to the unreachable ThunkSection. After 15 passes lld fails with
thunk creation not converged.

The new test aarch64-thunk-reuse2.s checks the case.

Without - pcBias, arm-thumb-thunk-empty-pass.s and arm-thunk-multipass-plt.s
will fail.

[MaskRay]

add a test

[MaskRay]

I'll push this today to fix some breakage.

[peter.smith]

Looks good to me.

IIUC the problem case is triggered by relocations with addends. Something like:

• ThunkSection selected which is in range of the branch, but not branch + offset.
• Later code identifies the thunk is out of branch range which removes the thunk from the branch
• Branch chooses the same thunk section as before.
• Repeat, until error message.

[MaskRay]

In D124653#3488163, @peter.smith wrote:

Looks good to me.

IIUC the problem case is triggered by relocations with addends. Something like:

• ThunkSection selected which is in range of the branch, but not branch + offset.
• Later code identifies the thunk is out of branch range which removes the thunk from the branch
• Branch chooses the same thunk section as before.
• Repeat, until error message.

Yes, this. Thanks!

lld/ELF/Relocations.cpp

forEachInputSectionDescription(
         std::merge(isd->sections.begin(), isd->sections.end(),
                    newThunks.begin(), newThunks.end(), std::back_inserter(tmp),
                    mergeCmp);
 
         isd->sections = std::move(tmp);
       });
 }
 
+static int64_t getPCBias(RelType type) {
+  if (config->emachine != EM_ARM)
+    return 0;
+  switch (type) {
+  case R_ARM_THM_JUMP19:
+  case R_ARM_THM_JUMP24:
+  case R_ARM_THM_CALL:
+    return 4;
+  default:
+    return 8;
+  }
+}
+
 // Find or create a ThunkSection within the InputSectionDescription (ISD) that
 // is in range of Src. An ISD maps to a range of InputSections described by a
 // linker script section pattern such as { .text .text.* }.
 ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *os,
                                            InputSection *isec,
                                            InputSectionDescription *isd,
                                            const Relocation &rel,
                                            uint64_t src) {
+  // See the comment in getThunk for -pcBias below.
+  const int64_t pcBias = getPCBias(rel.type);
   for (std::pair<ThunkSection *, uint32_t> tp : isd->thunkSections) {
     ThunkSection *ts = tp.first;
-    uint64_t tsBase = os->addr + ts->outSecOff + rel.addend;
-    uint64_t tsLimit = tsBase + ts->getSize() + rel.addend;
+    uint64_t tsBase = os->addr + ts->outSecOff - pcBias;
+    uint64_t tsLimit = tsBase + ts->getSize();
     if (target->inBranchRange(rel.type, src,
                               (src > tsLimit) ? tsBase : tsLimit))
       return ts;
   }
 
   // No suitable ThunkSection exists. This can happen when there is a branch
   // with lower range than the ThunkSection spacing or when there are too
   // many Thunks. Create a new ThunkSection as close to the InputSection as
static bool isThunkSectionCompatible(InputSection *source,
                                      SectionBase *target) {
   // We can't reuse thunks in different loadable partitions because they might
   // not be loaded. But partition 1 (the main partition) will always be loaded.
   if (source->partition != target->partition)
     return target->partition == 1;
   return true;
 }
 
-static int64_t getPCBias(RelType type) {
-  if (config->emachine != EM_ARM)
-    return 0;
-  switch (type) {
-  case R_ARM_THM_JUMP19:
-  case R_ARM_THM_JUMP24:
-  case R_ARM_THM_CALL:
-    return 4;
-  default:
-    return 8;
-  }
-}
-
 std::pair<Thunk *, bool> ThunkCreator::getThunk(InputSection *isec,
                                                 Relocation &rel, uint64_t src) {
   std::vector<Thunk *> *thunkVec = nullptr;
   // Arm and Thumb have a PC Bias of 8 and 4 respectively, this is cancelled
   // out in the relocation addend. We compensate for the PC bias so that
   // an Arm and Thumb relocation to the same destination get the same keyAddend,
   // which is usually 0.
   const int64_t pcBias = getPCBias(rel.type);

lld/test/ELF/aarch64-thunk-reuse2.s

+# REQUIRES: aarch64
+# RUN: llvm-mc -filetype=obj -triple=aarch64 %s -o %t.o
+# RUN: ld.lld -pie -Ttext=0x10300 %t.o -o %t
+# RUN: llvm-objdump -d --no-show-raw-insn --disassemble-symbols=dest,__AArch64ADRPThunk_,high %t | FileCheck %s
+
+## We create initial ThunkSection before the gap. Because the ThunkSection
+## selection code isn't so precise, we may create an unused thunk there (0x10704).
+## In the next pass we will create a ThunkSection after the gap. There used to be
+## a bug reusing the first ThunkSection (unreachable) due to the large r_addend.
+# CHECK:       <dest>:
+# CHECK-NEXT:     10700:       ret
+# CHECK:       <__AArch64ADRPThunk_>:
+# CHECK-NEXT:     10704:       adrp    x16, 0x10000
+# CHECK-NEXT:                  add     x16, x16, #1792
+# CHECK-NEXT:                  br      x16
+# CHECK-EMPTY:
+# CHECK:       <__AArch64ADRPThunk_>:
+# CHECK-NEXT:   8010710:       adrp    x16, 0x10000
+# CHECK-NEXT:                  add     x16, x16, #1792
+# CHECK-NEXT:                  br      x16
+# CHECK-LABEL: <high>:
+# CHECK-NEXT:   801071c:       bl      0x8010710 <__AArch64ADRPThunk_>
+# CHECK-NEXT:                  b       0x8010710 <__AArch64ADRPThunk_>
+
+.section .text._start, "ax", %progbits
+.globl _start
+_start:
+.space 0x400
+dest:
+  ret
+
+.section .text.gap, "ax", %progbits
+.space 0x8000000
+
+.section .text.high, "ax", %progbits
+high:
+  bl dest
+  b dest