[ELF] Fix the branch range computation when reusing a thunk

[MaskRay]

Summary

Notation: dst is t->getThunkTargetSym()->getVA()

On AArch64, when src-0x8000000-r_addend <= dst < src-0x8000000, the condition
target->inBranchRange(rel.type, src, rel.sym->getVA(rel.addend)) may
incorrectly consider a thunk reusable.
rel.addend = -getPCBias(rel.type) resets the addend to 0 for AArch64/PPC
and the zero addend is used by rel.sym->getVA(rel.addend) to check
out-of-range relocations.

See the test for a case this computation is wrong:
error: a.o:(.text_high+0x4): relocation R_AARCH64_JUMP26 out of range: -134217732 is not in [-134217728, 134217727]
I have seen a real world case with r_addend=19960.

[peter.smith]

Will need to have a think about this. I should have some time on Friday afternoon. I'd like to try and write a similar Arm case as we'll need to take into account the PC-bias stored in Addend in that case. It may be that we need a special case for Arm here.

[peter.smith]

I'd like to use t->getThunkTargetSym()->getVA(getPCBias(rel.type)) but two arm-* tests would fail. I think that is the remaining getPCBias issue after D97550. Not fixing it is probably fine since the failing scenario seems extremely corner-case.

I think this is very nearly right. On Arm the relocation addend is negative to offset the PC BIAS, so we'll need to invert it. For example:
target->inBranchRange(rel.type, src, t->getThunkTargetSym()->getVA(-getPCBias(rel.type))))

Will see if I can come up with a test case that fails without that and will post it here.

[peter.smith]

Here's a modification of your test case for AArch64 that will fail for Arm

# REQUIRES: arm
# RUN: rm -rf %t && split-file %s %t
# RUN: llvm-mc -filetype=obj -triple=armv7-a-none-eabi --arm-add-build-attributes %t/a.s -o %t/a.o
# RUN: ld.lld -pie -T %t/lds %t/a.o -o %t/a
# RUN: llvm-objdump -d --no-show-raw-insn %t/a | FileCheck %s

## We create a thunk for dest.
# CHECK-LABEL: <mid>:
# CHECK-NEXT: 2010004:       b       0x2010008 <__ARMV7PILongThunk_dest> @ imm = #-4
# CHECK-EMPTY:
# CHECK-NEXT: 02010008 <__ARMV7PILongThunk_dest>:
# CHECK-NEXT:                movw    r12, #65516
# CHECK-NEXT:                movt    r12, #65023
# CHECK-NEXT:                add     r12, r12, pc
# CHECK-NEXT:                bx      r12

## The first instruction can reuse the thunk but the second can't.
## If we reuse the thunk for b, we will get an "out of range" error.
# CHECK-LABEL: <high>:
# CHECK-NEXT: 4010000:       bl      0x2010008 <__ARMV7PILongThunk_dest> @ imm = #-33554432
# CHECK-NEXT:                b       0x4010008 <__ARMV7PILongThunk_dest> @ imm = #-4
# CHECK-EMPTY:
# CHECK-NEXT: 04010008 <__ARMV7PILongThunk_dest>:
# CHECK-NEXT:                movw    r12, #65516
# CHECK-NEXT:                movt    r12, #64511
# CHECK-NEXT:                add     r12, r12, pc
# CHECK-NEXT:                bx      r12

#--- a.s
.section .text_low, "ax", %progbits

.globl _start
_start:
  nop
dest:
  bx lr

.section .text_mid, "ax", %progbits
mid:
  b dest

.section .text_high, "ax", %progbits
high:
  bl dest
  b dest

#--- lds
SECTIONS {
  .text_low 0x10000: { *(.text_low) }
  .text_mid 0x2010004 : { *(.text_mid) }
  .text_high 0x4010000 : { *(.text_high) }
}

Both will pass with target->inBranchRange(rel.type, src, t->getThunkTargetSym()->getVA(-getPCBias(rel.type))))

In theory there is scope for another test for Thumb2 to cover the case of PC BIAS of 4, the test is for Arm with PC BIAS of 8. However if anyone changes the PC BIAS for Thumb other tests will fail.

[MaskRay]

Thanks for spotting my mistake (ah, I should have noticed the flipped sign) and even
providing an arm test! Included in the new diff.

[peter.smith]

LGTM thanks for the update.

lld/ELF/Relocations.cpp

 
 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.
-  int64_t keyAddend = rel.addend + getPCBias(rel.type);
+  const int64_t pcBias = getPCBias(rel.type);
+  const int64_t keyAddend = rel.addend + pcBias;
 
   // We use a ((section, offset), addend) pair to find the thunk position if
   // possible so that we create only one thunk for aliased symbols or ICFed
   // sections. There may be multiple relocations sharing the same (section,
   // offset + addend) pair. We may revert the relocation back to its original
   // non-Thunk target, so we cannot fold offset + addend.
   if (auto *d = dyn_cast<Defined>(rel.sym))
     if (!d->isInPlt() && d->section)
       thunkVec = &thunkedSymbolsBySectionAndAddend[{{d->section, d->value},
                                                     keyAddend}];
   if (!thunkVec)
     thunkVec = &thunkedSymbols[{rel.sym, keyAddend}];
 
   // Check existing Thunks for Sym to see if they can be reused
   for (Thunk *t : *thunkVec)
     if (isThunkSectionCompatible(isec, t->getThunkTargetSym()->section) &&
         t->isCompatibleWith(*isec, rel) &&
         target->inBranchRange(rel.type, src,
-                              t->getThunkTargetSym()->getVA(rel.addend)))
+                              t->getThunkTargetSym()->getVA(-pcBias)))
       return std::make_pair(t, false);
 
   // No existing compatible Thunk in range, create a new one
   Thunk *t = addThunk(*isec, rel);
   thunkVec->push_back(t);
   return std::make_pair(t, true);
 }
 

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

+# REQUIRES: aarch64
+# RUN: rm -rf %t && split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=aarch64 %t/a.s -o %t/a.o
+# RUN: ld.lld -pie -T %t/lds %t/a.o -o %t/a
+# RUN: llvm-objdump -d --no-show-raw-insn %t/a | FileCheck %s
+
+## We create a thunk for dest.
+# CHECK-LABEL: <mid>:
+# CHECK-NEXT:   8010008:       b       0x801000c <__AArch64ADRPThunk_>
+# CHECK-EMPTY:
+# CHECK-NEXT:  <__AArch64ADRPThunk_>:
+# CHECK-NEXT:   801000c:       adrp    x16, 0x10000
+# CHECK-NEXT:                  add     x16, x16, #4
+# CHECK-NEXT:                  br      x16
+
+## The first instruction can reuse the thunk but the second can't.
+## If we reuse the thunk for b, we will get an "out of range" error.
+# CHECK-LABEL: <high>:
+# CHECK-NEXT:  1001000c:       bl      0x801000c <__AArch64ADRPThunk_>
+# CHECK-NEXT:                  b       0x10010014 <__AArch64ADRPThunk_>
+# CHECK-EMPTY:
+# CHECK-NEXT:  <__AArch64ADRPThunk_>:
+# CHECK-NEXT:  10010014:       adrp    x16, 0x10000
+# CHECK-NEXT:                  add     x16, x16, #4
+# CHECK-NEXT:                  br      x16
+
+#--- a.s
+.section .text_low, "ax", %progbits
+.globl _start
+_start:
+  nop
+dest:
+  ret
+
+.section .text_mid, "ax", %progbits
+mid:
+  b dest
+
+.section .text_high, "ax", %progbits
+high:
+  bl dest
+  b dest
+
+#--- lds
+SECTIONS {
+  .text_low 0x10000: { *(.text_low) }
+  .text_mid 0x8010008 : { *(.text_mid) }
+  .text_high 0x1001000c : { *(.text_high) }
+}

lld/test/ELF/arm-thunk-reuse.s

+# REQUIRES: arm
+# RUN: rm -rf %t && split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=armv7-a-none-eabi --arm-add-build-attributes %t/a.s -o %t/a.o
+# RUN: ld.lld -pie -T %t/lds %t/a.o -o %t/a
+# RUN: llvm-objdump -d --no-show-raw-insn %t/a | FileCheck %s
+
+## We create a thunk for dest.
+# CHECK-LABEL: <mid>:
+# CHECK-NEXT:   2010004:     b       0x2010008 <__ARMV7PILongThunk_dest>
+# CHECK-EMPTY:
+# CHECK-NEXT:  <__ARMV7PILongThunk_dest>:
+# CHECK-NEXT:   2010008:     movw    r12, #65516
+# CHECK-NEXT:                movt    r12, #65023
+# CHECK-NEXT:                add     r12, r12, pc
+# CHECK-NEXT:                bx      r12
+
+## The first instruction can reuse the thunk but the second can't.
+## If we reuse the thunk for b, we will get an "out of range" error.
+# CHECK-LABEL: <high>:
+# CHECK-NEXT:   4010000:      bl      0x2010008 <__ARMV7PILongThunk_dest>
+# CHECK-NEXT:                 b       0x4010008 <__ARMV7PILongThunk_dest>
+# CHECK-EMPTY:
+# CHECK-NEXT:  <__ARMV7PILongThunk_dest>:
+# CHECK-NEXT:   4010008:      movw    r12, #65516
+# CHECK-NEXT:                 movt    r12, #64511
+# CHECK-NEXT:                 add     r12, r12, pc
+# CHECK-NEXT:                 bx      r12
+
+#--- a.s
+.section .text_low, "ax", %progbits
+
+.globl _start
+_start:
+  nop
+dest:
+  bx lr
+
+.section .text_mid, "ax", %progbits
+mid:
+  b dest
+
+.section .text_high, "ax", %progbits
+high:
+  bl dest
+  b dest
+
+#--- lds
+SECTIONS {
+  .text_low 0x10000: { *(.text_low) }
+  .text_mid 0x2010004 : { *(.text_mid) }
+  .text_high 0x4010000 : { *(.text_high) }
+}