[LLD][ELF][ARM][AArch64] Only round up ThunkSection Size when large OS.

[peter.smith]

Summary

In D71281 a fix was put in to round up the size of a ThunkSection to the nearest 4KiB when performing errata patching. This fixed a problem with a very large instrumented program that had thunks and patches mutually trigger each other. Unfortunately it triggers an assertion failure in an AArch64 allyesconfig build of the kernel. There is a specific assertion preventing an InputSectionDescription being larger than 4KiB. This will always trigger if there is at least one Thunk needed in that InputSectionDescription, which is possible for an allyesconfig build.

Abstractly the problem case is:

.text : {
          *(.text) ;
          ...
          . = ALIGN(SZ_4K);
          __idmap_text_start = .;
          *(.idmap.text)
          __idmap_text_end = .;
          ...
        }

The assertion checks that idmap_text_end - idmap_start is < 4 KiB. Note that there is more than one InputSectionDescription in the OutputSection so we can't just restrict the fix to OutputSections smaller than 4 KiB.

The fix presented here limits the D71281 to InputSectionDescriptions that meet the following conditions:

• The OutputSection is bigger than the thunkSectionSpacing so adding thunks will affect the addresses of following code.
• The InputSectionDescription is smaller than 4 KiB. This will prevent any assertion failures that an InputSectionDescription is < 4 KiB in size.

We do this at ThunkSection creation time as at this point we know that the addresses are stable and up to date prior to adding the thunks as assignAddresses() will have been called immediately prior to thunk generation.

The fix reverts the two tests affected by D71281 to their original state as they no longer need the 4KiB size roundup. I've added simpler tests to check for D71281 when the OutputSection size is larger than the ThunkSection spacing.

Fixes https://github.com/ClangBuiltLinux/linux/issues/812

[peter.smith]

On looking again at the linux kernel makefile

#define IDMAP_TEXT					\
	. = ALIGN(SZ_4K);				\
	__idmap_text_start = .;				\
	*(.idmap.text)					\
	__idmap_text_end = .;
...
.text : {			/* Real text segment		*/
		_stext = .;		/* Text and read-only data	*/
			IRQENTRY_TEXT
			SOFTIRQENTRY_TEXT
			ENTRY_TEXT
			TEXT_TEXT
			SCHED_TEXT
			CPUIDLE_TEXT
			LOCK_TEXT
			KPROBES_TEXT
			HYPERVISOR_TEXT
			IDMAP_TEXT
			HIBERNATE_TEXT
			TRAMP_TEXT
			*(.fixup)
			*(.gnu.warning)
		. = ALIGN(16);
		*(.got)			/* Global offset table		*/
	}

It looks like this fix may not be enough if the aggregate size of the .text section is > ThunkSectionSpacing. If it isn't enough then my next preference would be to only set roundUpSizeForErrata if the InputSectionDescription such as *(.idmap.text) is over a certain size. A small InputSectionDescription is not likely to generate a large enough range of patches and thunks to cause the iterate for ever corner case.

[grimar]

lld/ELF/SyntheticSections.cpp

3462

does the following look better?

roundUpSizeForErrata = (config->fixCortexA53Errata843419 || config->fixCortexA8) &&
      os->size >= target->getThunkSectionSpacing();

But, basing on the comment which says "os->size is stable" (I've not debug the code, sorry),
can't you just get rid of roundUpSizeForErrata and do the following?

size_t ThunkSection::getSize() const {
  if ((config->fixCortexA53Errata843419 || config->fixCortexA8) &&
      this->parent->size >= target->getThunkSectionSpacing())
    return alignTo(size, 4096);
  return size;
}

lld/ELF/SyntheticSections.h

1079

This needs a comment probably.

[peter.smith]

Thanks for the comments. I've decided to rework this In light of it not actually fixing the problem in Linux. In the allyesconfig build the overall .text OutputSection is larger than thunkSectionSpacing, but the assert was for in effect an InputSectionDescription within .text so I've had to think again. I'm nearly ready to submit again, just got to test in on the kernel itself first.

lld/ELF/SyntheticSections.cpp

3462

Unfortunately not as getSize() is called when calculating the addresses and this resets this->parent->size. I ended up with a different size reported when doing assignOffsets.

lld/ELF/SyntheticSections.h

1079

Agreed, will do so by reference.

[peter.smith]

Updated the fix, and description after testing on a real linux kernel allyesconfig build. The description contains the full details, which should also be present in the comment. In summary we round up the size of a thunk section to nearest 4KiB when:

• The erratum fix is being used.
• The thunk section may be placed before the end of Output Section so there may be code after it.
• The InputSectionDescription is larger than 4KiB.

[MaskRay]

lld/ELF/Relocations.cpp

1772

larger? ( isdLimit - isdBase > 4096)

1775

Can we simplify isdBase + target->getThunkSectionSpacing() < os->size to off + target->getThunkSectionSpacing() < os->size

[MaskRay]

lld/ELF/Relocations.cpp

1775

We can't.

off + target->getThunkSectionSpacing() < os->size can cause https://bugs.llvm.org//show_bug.cgi?id=44071#c5 to fail with ld.lld: error: thunk creation not converged.

I suggested off because I thought off corresponds to prevIsecLimit in the code below:

if (isecLimit > thunkUpperBound) {
  addThunkSection(os, isd, prevIsecLimit);
  thunkUpperBound = prevIsecLimit + thunkSectionSpacing;
}

Still puzzled why we use isdBase + target->getThunkSectionSpacing() < os->size here.

1781

I wonder whether we should use 4 unconditionally https://reviews.llvm.org/D72819 .

Most thunks are 16 bytes. I don't know why we selected 8, instead of 4 or 16 in D29129.
(If 8 were for locality/cache line considerations, 16 would be a better choice.)

[peter.smith]

Thanks for the comments. I'll post an update with a simplification as I don't think I can justify the heuristic without being too hand wavy.

lld/ELF/Relocations.cpp

1772

Yes, larger. Thanks for spotting that one.

1775

Going over this again, and refreshing where the thunks are actually inserted and not using my memory and looking at the failing chromium example the isdBase, TS1 off, TS2 off, isdLimit are as follows

0	TS1 0x7fcffb8	TS2 0x8051488	0x10024008

The Thunk insertion code tries to insert the first thunk section as far away as thunkUpperBound, but stops at lastThunkLowerBound as we can comfortably reach from a branch from the end of the isd.

Both the ThunkSections + thunkSectionSpacing are > os->size, but isdBase + thunkSectionSpacing is not, so any ThunkSection created in the isd will have its size rounded up.

The isdBase + thunkSectionSpacing < os->size is essentially a heuristic. In effect saying that we are less likely to need thunks and patches when in the last thunkSectionSpacing() of the os. I can only really justify as a balance in avoiding running out of passes versus an arbitrary assertion such as in the linux kernel. If we are less concerned about the latter then I think we can simplify to:

if  (os->size > target->getThunkSectionSpacing() && (isdLimit - isdBase > 4096))

This will get both of the problems we know about, but may be too specific to the linux kernel assert.

1781

Agreeed. It was probably my fault for introducing it in the first place. I didn't have a good reason for it for Arm/AArch64 but didn't know about other targets so I used config->wordsize.

[peter.smith]

Updated diff (and description) to simplify part of the check to os->size > target->getThunkSectionSpacing(). This is conservative, but simple. We can in theory do better, but it is difficult to do so without using heuristics. In effect it is a judgement that ThunkSections close to, but not necessarily at the end of the OutputSection have less of a chance of generating sufficient extra thunks and patches to cause non-convergence.

I've taken out the reduction in alignment of ThunkSection for AArch64 as this change can be made outside of this patch.

Tested against Linux Kernel allyesconfig and instrumented Chromium build.

[nickdesaulniers]

Thanks everyone!

lld/ELF/Relocations.cpp

forEachInputSectionDescription(
       });
 }
 
 ThunkSection *ThunkCreator::addThunkSection(OutputSection *os,
                                             InputSectionDescription *isd,
                                             uint64_t off) {
   auto *ts = make<ThunkSection>(os, off);
   ts->partition = os->partition;
+  if ((config->fixCortexA53Errata843419 || config->fixCortexA8) &&
+      !isd->sections.empty()) {
+    // The errata fixes are sensitive to addresses modulo 4 KiB. When we add
+    // thunks we disturb the base addresses of sections placed after the thunks
+    // this makes patches we have generated redundant, and may cause us to
+    // generate more patches as different instructions are now in sensitive
+    // locations. When we generate more patches we may force more branches to
+    // go out of range, causing more thunks to be generated. In pathological
+    // cases this can cause the address dependent content pass not to converge.
+    // We fix this by rounding up the size of the ThunkSection to 4KiB, this
+    // limits the insertion of a ThunkSection on the addresses modulo 4 KiB,
+    // which means that adding Thunks to the section does not invalidate
+    // errata patches for following code.
+    // Rounding up the size to 4KiB has consequences for code-size and can
+    // trip up linker script defined assertions. For example the linux kernel
+    // has an assertion that what LLD represents as an InputSectionDescription
+    // does not exceed 4 KiB even if the overall OutputSection is > 128 Mib.
+    // We use the heuristic of rounding up the size when both of the following
+    // conditions are true:
+    // 1.) The OutputSection is larger than the ThunkSectionSpacing. This
+    //     accounts for the case where no single InputSectionDescription is
+    //     larger than the OutputSection size. This is conservative but simple.
+    // 2.) The InputSectionDescription is larger than 4 KiB. This will prevent
+    //     any assertion failures that an InputSectionDescription is < 4 KiB
+    //     in size.
+    uint64_t isdSize = isd->sections.back()->outSecOff +
+                       isd->sections.back()->getSize() -
+                       isd->sections.front()->outSecOff;
+    if (os->size > target->getThunkSectionSpacing() && isdSize > 4096)
+      ts->roundUpSizeForErrata = true;
+  }
   isd->thunkSections.push_back({ts, pass});
   return ts;
 }
 
 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;
 }

lld/ELF/SyntheticSections.h

public:
   // Thunk defines a symbol in this InputSection that can be used as target
   // of a relocation
   void addThunk(Thunk *t);
   size_t getSize() const override;
   void writeTo(uint8_t *buf) override;
   InputSection *getTargetInputSection() const;
   bool assignOffsets();
 
+  // When true, round up reported size of section to 4 KiB. See comment
+  // in addThunkSection() for more details.
+  bool roundUpSizeForErrata = false;
+
 private:
   std::vector<Thunk *> thunks;
   size_t size = 0;
 };
 
 // Used to compute outSecOff of .got2 in each object file. This is needed to
 // synthesize PLT entries for PPC32 Secure PLT ABI.
 class PPC32Got2Section final : public SyntheticSection {
 public:
   PPC32Got2Section();
   size_t getSize() const override { return 0; }
   bool isNeeded() const override;

lld/ELF/SyntheticSections.cpp

 
 ThunkSection::ThunkSection(OutputSection *os, uint64_t off)
     : SyntheticSection(SHF_ALLOC | SHF_EXECINSTR, SHT_PROGBITS, 4,
                        ".text.thunk") {
   this->parent = os;
   this->outSecOff = off;
 }
 
-// When the errata patching is on, we round the size up to a 4 KiB
-// boundary. This limits the effect that adding Thunks has on the addresses
-// of the program modulo 4 KiB. As the errata patching is sensitive to address
-// modulo 4 KiB this can prevent further patches from being needed due to
-// Thunk insertion.
 size_t ThunkSection::getSize() const {
-  if (config->fixCortexA53Errata843419 || config->fixCortexA8)
+  if (roundUpSizeForErrata)
     return alignTo(size, 4096);
   return size;
 }
 
 void ThunkSection::addThunk(Thunk *t) {
   thunks.push_back(t);
   t->addSymbols(*this);
 }
 

lld/test/ELF/aarch64-cortex-a53-843419-thunk-align.s

+// REQUIRES: aarch64
+// RUN: llvm-mc -filetype=obj -triple=aarch64-none-linux %s -o %t.o
+// RUN: echo "SECTIONS { \
+// RUN:                  .text 0x10000 : { \
+// RUN:                  *(.text.01) ; \
+// RUN:                  . += 0x8000000 ;  \
+// RUN:                  *(.text.02) } \
+// RUN:                  .foo : { *(.foo_sec) } } " > %t.script
+// RUN: ld.lld -pie --fix-cortex-a53-843419 --script=%t.script %t.o -o %t2
+// RUN: llvm-objdump --no-show-raw-insn -triple=aarch64-linux-gnu -d %t2
+
+
+/// %t2 is > 128 Megabytes, so delete it early.
+// RUN: rm %t2
+
+/// Test case that for an OutputSection larger than the ThunkSectionSpacing
+/// --fix-cortex-a53-843419 will cause the size of the ThunkSection to be
+/// rounded up to the nearest 4KiB
+
+ .section .text.01, "ax", %progbits
+ .balign 4096
+ .globl _start
+ .type _start, %function
+_start:
+/// Range extension thunk needed, due to linker script
+ bl far_away
+ .space 4096 - 12
+
+/// Erratum sequence
+ .globl t3_ff8_ldr
+ .type t3_ff8_ldr, %function
+t3_ff8_ldr:
+ adrp x0, dat
+ ldr x1, [x1, #0]
+ ldr x0, [x0, :lo12:dat]
+ ret
+
+/// Expect thunk and patch to be inserted here
+// CHECK: 0000000000011008 __AArch64ADRPThunk_far_away:
+// CHECK-NEXT: 11008: adrp    x16, #134221824
+// CHECK-NEXT:        add     x16, x16, #16
+// CHECK-NEXT:        br      x16
+// CHECK: 0000000000012008 __CortexA53843419_11000:
+// CHECK-NEXT: 12008: ldr     x0, [x0, #168]
+// CHECK-NEXT:        b       #-4104 <t3_ff8_ldr+0xc>
+
+ .section .text.02, "ax", %progbits
+ .globl far_away
+ .type far_away, function
+far_away:
+ bl _start
+ ret
+/// Expect thunk for _start not to have size rounded up to 4KiB as it is at
+/// the end of the OutputSection
+// CHECK: 0000000008012010 far_away:
+// CHECK-NEXT:  8012010: bl      #8
+// CHECK-NEXT:           ret
+// CHECK: 0000000008012018 __AArch64ADRPThunk__start:
+// CHECK-NEXT:  8012018: adrp    x16, #-134225920
+// CHECK-NEXT:           add     x16, x16, #0
+// CHECK-NEXT:           br      x16
+// CHECK: 0000000008012024 foo:
+// CHECK-NEXT:  8012024: ret
+ .section .foo_sec, "ax", %progbits
+ .globl foo
+ .type foo, function
+foo:
+  ret
+
+
+ .section .data
+ .balign 8
+ .globl dat
+dat:    .quad 0

lld/test/ELF/aarch64-cortex-a53-843419-thunk.s

 // REQUIRES: aarch64
 // RUN: llvm-mc -filetype=obj -triple=aarch64-none-linux %s -o %t.o
 // RUN: echo "SECTIONS { \
 // RUN:          .text1 0x10000 : { *(.text.01) *(.text.02) *(.text.03) } \
 // RUN:          .text2 0x8010000 : { *(.text.04) } } " > %t.script
 // RUN: ld.lld --script %t.script -fix-cortex-a53-843419 -verbose %t.o -o %t2 \
 // RUN:   2>&1 | FileCheck -check-prefix=CHECK-PRINT %s
-
 // RUN: llvm-objdump --no-show-raw-insn -triple=aarch64-linux-gnu -d %t2 | FileCheck %s
 
 /// %t2 is 128 Megabytes, so delete it early.
 // RUN: rm %t2
 
 /// Test cases for Cortex-A53 Erratum 843419 that involve interactions with
 /// range extension thunks. Both erratum fixes and range extension thunks need
 /// precise address information and after creation alter address information.
 
 
         .section .text.01, "ax", %progbits
         .balign 4096
         .globl _start
         .type _start, %function
 _start:
         bl far_away
         /// Thunk to far_away, size 16-bytes goes here.
-        /// Thunk Section with patch enabled has its size rounded up to 4KiB
-        /// this leaves the address of following sections the same modulo 4 KiB
 
         .section .text.02, "ax", %progbits
-        .space 4096 - 12
+        .space 4096 - 28
 
         /// Erratum sequence will only line up at address 0 modulo 0xffc when
         /// Thunk is inserted.
         .section .text.03, "ax", %progbits
         .globl t3_ff8_ldr
         .type t3_ff8_ldr, %function
 t3_ff8_ldr:
         adrp x0, dat
         ldr x1, [x1, #0]
         ldr x0, [x0, :got_lo12:dat]
         ret
 
-// CHECK-PRINT: detected cortex-a53-843419 erratum sequence starting at 11FF8 in unpatched output.
-// CHECK: 0000000000011ff8 t3_ff8_ldr:
-// CHECK-NEXT: adrp    x0, #134213632
+// CHECK-PRINT: detected cortex-a53-843419 erratum sequence starting at 10FF8 in unpatched output.
+// CHECK: 0000000000010ff8 t3_ff8_ldr:
+// CHECK-NEXT: adrp    x0, #134217728
 // CHECK-NEXT: ldr     x1, [x1]
 // CHECK-NEXT: b       #8
 // CHECK-NEXT: ret
-// CHECK: 0000000000012008 __CortexA53843419_12000:
+// CHECK: 0000000000011008 __CortexA53843419_11000:
 // CHECK-NEXT: ldr     x0, [x0, #8]
 // CHECK-NEXT: b       #-8
         .section .text.04, "ax", %progbits
         .globl far_away
         .type far_away, function
 far_away:
         ret
 
         .section .data
         .globl dat
 dat:    .quad 0

lld/test/ELF/arm-fix-cortex-a8-thunk-align.s

+// REQUIRES: arm
+// RUN: llvm-mc -filetype=obj -triple=armv7a-linux-gnueabihf --arm-add-build-attributes %s -o %t.o
+// RUN: ld.lld --fix-cortex-a8 --shared %t.o -o %t2
+// RUN: llvm-objdump -d --no-show-raw-insn %t2 | FileCheck %s
+
+/// Test case that for an OutputSection larger than the ThunkSectionSpacing
+/// --fix-cortex-a8 will cause the size of the ThunkSection to be rounded up to
+/// the nearest 4KiB
+ .thumb
+
+ .section .text.01, "ax", %progbits
+ .balign 4096
+ .globl _start
+ .type _start, %function
+_start:
+  /// state change thunk required
+  b.w arm_func
+thumb_target:
+  .space 4096 - 10
+  /// erratum patch needed
+  nop.w
+  b.w thumb_target
+
+/// Expect thunk and patch to be inserted here
+// CHECK:  00003004 __ThumbV7PILongThunk_arm_func:
+// CHECK-NEXT: 3004: movw    r12, #4088
+// CHECK-NEXT:       movt    r12, #256
+// CHECK-NEXT:       add     r12, pc
+// CHECK-NEXT:       bx      r12
+// CHECK:  00004004 __CortexA8657417_2FFE:
+// CHECK-NEXT: 4004: b.w     #-8196
+ .section .text.02
+ /// Take us over thunk section spacing
+ .space 16 * 1024 * 1024
+
+ .section .text.03, "ax", %progbits
+ .arm
+ .balign 4
+ .type arm_func, %function
+arm_func:
+  bx lr

lld/test/ELF/arm-fix-cortex-a8-thunk.s

 // REQUIRES: arm
 // RUN: llvm-mc -filetype=obj -triple=armv7a-linux-gnueabihf --arm-add-build-attributes %s -o %t.o
 // RUN: echo "SECTIONS { \
-// RUN:          .text0 0x01200a : { *(.text.00) } \
+// RUN:          .text0 0x011006 : { *(.text.00) } \
 // RUN:          .text1 0x110000 : { *(.text.01) *(.text.02) *(.text.03) \
 // RUN:                             *(.text.04) } \
 // RUN:          .text2 0x210000 : { *(.text.05) } } " > %t.script
 // RUN: ld.lld --script %t.script --fix-cortex-a8 --shared -verbose %t.o -o %t2 2>&1
 // RUN: llvm-objdump -d --no-show-raw-insn %t2 | FileCheck %s
 
 /// Test cases for Cortex-a8 Erratum 657417 that involve interactions with
 /// range extension thunks. Both erratum fixes and range extension thunks need

 /// Thunk to far_away and state change needed, size 12-bytes goes here.
 // CHECK: 00110004 __ThumbV7PILongThunk_far_away:
 // CHECK-NEXT: 110004: movw    r12, #65524
 // CHECK-NEXT:         movt    r12, #15
 // CHECK-NEXT:         add     r12, pc
 // CHECK-NEXT:         bx      r12
 
  .section .text.02, "ax", %progbits
- .space 4096 - 10
+ .space 4096 - 22
 
  .section .text.03, "ax", %progbits
  .thumb_func
 target:
 /// After thunk is added this branch will line up across 2 4 KiB regions
 /// and will trigger a patch.
  nop.w
  bl target
 
 /// Expect erratum patch inserted here
-// CHECK: 00111ffa target:
-// CHECK-NEXT: 111ffa: nop.w
+// CHECK: 00110ffa target:
+// CHECK-NEXT: 110ffa: nop.w
 // CHECK-NEXT:         bl      #2
-// CHECK: 00112004 __CortexA8657417_111FFE:
-// CHECK-NEXT: 112004: b.w     #-14
+// CHECK: 00111004 __CortexA8657417_110FFE:
+// CHECK-NEXT: 111004: b.w     #-14
 
 /// Expect range extension thunk here.
-// CHECK: 00112008 __ThumbV7PILongThunk_early:
-// CHECK-NEXT: 112008: b.w     #-1048578
+// CHECK: 00111008 __ThumbV7PILongThunk_early:
+// CHECK-NEXT: 111008: b.w     #-1048582
 
  .section .text.04, "ax", %progbits
 /// The erratum patch will push this branch out of range, so another
 /// range extension thunk will be needed.
         beq.w early
-// CHECK:   113008:            beq.w   #-4100
+// CHECK:   11100c:            beq.w   #-8
 
  .section .text.05, "ax", %progbits
  .arm
  nop
  .type far_away, %function
 far_away:
   bx lr