[LLD][ELF][ARM] Fix ARM Exidx order for non monotonic section order

[psmith]

Summary

The contents of the .ARM.exidx section must be ordered by SHF_LINK_ORDER rules. We don't need to know the precise address for this order, but we do need to know the relative order of sections. We have been using the sectionIndex for this purpose, this works when the OutputSection order has a monotonically increasing virtual address, but it is possible to write a linker script with non-monotonically increasing virtual address. For these cases we need to evaluate the base address of the OutputSection so that we can order the .ARM.exidx sections properly.

This change moves the finalisation of .ARM.exidx till after the first call to AssignAddresses. This permits us to sort on virtual address which is linker script safe. It also permits a fix for part of pr44824 where we generate .ARM.exidx section for the vector table when that table is so far away it is out of range of the .ARM.exidx section. This fix will come in a follow up patch.

I think that this also affects the standard SHF_LINK_ORDER, I think resolveSHFLinkOrder() probably needs to be moved to a similar place.

[MaskRay]

The patch looks good. I think applying it does not hurt.

// RUN: .text.1 0x80000200 : AT(0x80000200) { *(.text.1) } \
// RUN: .text.2 0x80000100 : AT(0x80000100) { *(.text.2) } \

This is interesting. Does linux/arch/arm have such a use case where VMA(.text.1) > VMA(.text.2) with optional LMA(.text.1) < LMA(.text.2)? If it does, we probably should let it drop that requirement.

For symbol assignments, lld has such a diagnostic:

void LinkerScript::setDot(Expr e, const Twine &loc, bool inSec) {
  uint64_t val = e().getValue();
  if (val < dot && inSec)
    error(loc + ": unable to move location counter backward for: " +
          ctx->outSec->name);

the only software I know (unintentionally) making use of this property is seabios but I have a patch to fix that (https://mail.coreboot.org/hyperkitty/list/[e-mail]/thread/KBHQU4OLW2THG5Q5F5X7EWTQDJHKNVYC/ )

Not sure how the Linux kernel leverage non-increasing VMAs but the BFD logic does not make me feel comfortable that it can handle various corner cases well:
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=ld/ldlang.c;hb=49d1d1f53df552f0592b1cc4cc9a74db70d5ffa7#l5782

I think that this also affects the standard SHF_LINK_ORDER, I think resolveSHFLinkOrder() probably needs to be moved to a similar place.

My understanding is that when linked-to sections span multiple output sections, the order is unspecified. That said, I agree that respecting the VMA order instead of the section header table order seems more reasonable.
If we are going to support non-increasing VMAs, making generic SHF_LINK_ORDER aligns with .ARM.exidx should be preferable.
I'll still decipher more about BFD's non-increasing VMA support.

This change moves the finalisation of .ARM.exidx till after the first call to AssignAddresses.

assignAddresses

lld/test/ELF/arm-exidx-script-order.s

2

// REQUIRES: ARM

11

delete excess space before %t

18

Missing CHECK-NEXT:

[psmith]

In D78422#1991026, @MaskRay wrote:

The patch looks good. I think applying it does not hurt.

// RUN: .text.1 0x80000200 : AT(0x80000200) { *(.text.1) } \
// RUN: .text.2 0x80000100 : AT(0x80000100) { *(.text.2) } \

This is interesting. Does linux/arch/arm have such a use case where VMA(.text.1) > VMA(.text.2) with optional LMA(.text.1) < LMA(.text.2)? If it does, we probably should let it drop that requirement.

Difficult to tell, the linker script is generated from macros and is not easy to understand, I've untangled it a bit and expanded.

__vectors_start = .; .vectors 0xffff0000 : AT(__vectors_start) { *(.vectors) } 
. = __vectors_start + SIZEOF(.vectors); __vectors_end = .; 
__stubs_start = .; .stubs ADDR(.vectors) + 0x1000 : AT(__stubs_start) { *(.stubs) } 
. = __stubs_start + SIZEOF(.stubs); __stubs_end = .
; PROVIDE(vector_fiq_offset = vector_fiq - ADDR(.vectors));
. = ALIGN(8); 
.init.text : AT(ADDR(.init.text) - 0) { _sinittext = .; *(.init.text .init.text.*) *(.text.startup) *(.meminit.text*) _einittext = .; }
.exit.text : {
 *(.exit.text) *(.text.exit) *(.memexit.text)
}

With a corresponding map file

.vectors        0x00000000ffff0000       0x20 load address 0x0000000080b00000
 *(.vectors)
 .vectors       0x00000000ffff0000       0x20 arch/arm/kernel/entry-armv.o
                0x0000000080b00020                . = (__vectors_start + SIZEOF (.vectors))
                0x0000000080b00020                __vectors_end = .
                0x0000000080b00020                __stubs_start = .

.stubs          0x00000000ffff1000      0x2ac load address 0x0000000080b00020
 *(.stubs)
 .stubs         0x00000000ffff1000      0x2ac arch/arm/kernel/entry-armv.o
                0x00000000ffff1240                vector_fiq
                0x0000000080b002cc                . = (__stubs_start + SIZEOF (.stubs))
                0x0000000080b002cc                __stubs_end = .
                [!provide]                        PROVIDE (vector_fiq_offset = (vector_fiq - ADDR (.vectors)))
                0x0000000080b002d0                . = ALIGN (0x8)

.init.text      0x0000000080b002e0    0x32410
                0x0000000080b002e0                _sinittext = .
 *(.init.text .init.text.*)

For symbol assignments, lld has such a diagnostic:

void LinkerScript::setDot(Expr e, const Twine &loc, bool inSec) {
  uint64_t val = e().getValue();
  if (val < dot && inSec)
    error(loc + ": unable to move location counter backward for: " +
          ctx->outSec->name);

the only software I know (unintentionally) making use of this property is seabios but I have a patch to fix that (https://mail.coreboot.org/hyperkitty/list/[e-mail]/thread/KBHQU4OLW2THG5Q5F5X7EWTQDJHKNVYC/ )

Not sure how the Linux kernel leverage non-increasing VMAs but the BFD logic does not make me feel comfortable that it can handle various corner cases well:
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=ld/ldlang.c;hb=49d1d1f53df552f0592b1cc4cc9a74db70d5ffa7#l5782

FWIW in embedded systems it is quite common to have linker scripts where different OutputSections need to be copied to various disjoint memory locations and these are often not in order of ascending address. I think it is common for these to be in ascending LMA though. These are almost always done with an explicit assignment of the OutputSection base address though. I will need to search to see what examples I can find online, most of the complicated embedded projects are not open source so it is difficult to get examples.

I think that this also affects the standard SHF_LINK_ORDER, I think resolveSHFLinkOrder() probably needs to be moved to a similar place.

My understanding is that when linked-to sections span multiple output sections, the order is unspecified. That said, I agree that respecting the VMA order instead of the section header table order seems more reasonable.
If we are going to support non-increasing VMAs, making generic SHF_LINK_ORDER aligns with .ARM.exidx should be preferable.
I'll still decipher more about BFD's non-increasing VMA support.

This change moves the finalisation of .ARM.exidx till after the first call to AssignAddresses.

assignAddresses

I'll take a look to see what BFD supports. From looking at the linux kernel example it looks like it is assigning addresses to sections and symbols in a similar way to LLD. Instructions to reproduce the problem are in the PR if you are interested.

[grimar]

2 nits, otherwise LG.

lld/ELF/Writer.cpp

1622

I'd expand this comment a bit.
"relative address of OutputSections, because ... "

lld/test/ELF/arm-exidx-script-order.s

21

Missing an empty line before .text.

[MaskRay]

lld/test/ELF/arm-exidx-script-order.s

51

Capitalize

[psmith]

Thanks both for the comments. I'll make an update this evening.

[psmith]

I've updated the tests to address review comments, and have made the addresses increase in LMA. I've got a follow up patch that I can send for SHF_LINK_ORDER as I can reproduce a problem with a similar test case.

[MaskRay]

Thanks for the update. LG with the few test comments addressed, and @grimar's suggestion about expanding a code comment.

[psmith]

Thanks, and apologies for forgetting George's comment request. I'll upload a new version and commit tomorrow.

lld/test/ELF/arm-exidx-script-order.s

2

I think it has to be all lower case (all other REQUIRES are lower case). If I use ARM then llvm-lit won't recognise it.

[psmith]

Added additional detail in comment and fix up spacing in tests.

[psmith]

I had to revert due to an msan build bot failure. I don't fully understand it yet http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/40693/steps/check-lld%20msan/logs/stdio as I can't yet see how script->assignAddresses would not set OutSec->addr. However msan is more likely to be right than me.

[psmith]

In D78422#1999427, @psmith wrote:

I had to revert due to an msan build bot failure. I don't fully understand it yet http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/40693/steps/check-lld%20msan/logs/stdio as I can't yet see how script->assignAddresses would not set OutSec->addr. However msan is more likely to be right than me.

OK, found it. It wasn't that OutSec->addr hadn't been set, it was that the .ARM.exidx SyntheticSection size was unitialized (it is set by finalize()) and this polluted the addr values calculated by assignAddresses, an update to initialize the size based on an estimate of .ARM.exidx section size pre-compression fixes the problem. Will recommit with fix.

lld/ELF/SyntheticSections.cpp

void ARMExidxSyntheticSection::finalizeContents() {
   // ICF may remove executable InputSections and their dependent .ARM.exidx
   // section that we recorded earlier.
   auto isDiscarded = [](const InputSection *isec) { return !isec->isLive(); };
   llvm::erase_if(executableSections, isDiscarded);
   llvm::erase_if(exidxSections, isDiscarded);
 
   // Sort the executable sections that may or may not have associated
   // .ARM.exidx sections by order of ascending address. This requires the
-  // relative positions of InputSections to be known.
+  // relative positions of InputSections and OutputSections to be known.
   auto compareByFilePosition = [](const InputSection *a,
                                   const InputSection *b) {
     OutputSection *aOut = a->getParent();
     OutputSection *bOut = b->getParent();
 
     if (aOut != bOut)
-      return aOut->sectionIndex < bOut->sectionIndex;
+      return aOut->addr < bOut->addr;
     return a->outSecOff < b->outSecOff;
   };
   llvm::stable_sort(executableSections, compareByFilePosition);
   sentinel = executableSections.back();
   // Optionally merge adjacent duplicate entries.
   if (config->mergeArmExidx) {
     std::vector<InputSection *> selectedSections;
     selectedSections.reserve(executableSections.size());

lld/ELF/Writer.cpp

for (OutputSection *sec : outputSections) {
 
     llvm::stable_sort(sections, compareByFilePosition);
 
     for (int i = 0, n = sections.size(); i < n; ++i)
       *scriptSections[i] = sections[i];
   }
 }
 
+static void finalizeSynthetic(SyntheticSection *sec) {
+  if (sec && sec->isNeeded() && sec->getParent())
+    sec->finalizeContents();
+}
+
 // We need to generate and finalize the content that depends on the address of
 // InputSections. As the generation of the content may also alter InputSection
 // addresses we must converge to a fixed point. We do that here. See the comment
 // in Writer<ELFT>::finalizeSections().
 template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
   ThunkCreator tc;
   AArch64Err843419Patcher a64p;
   ARMErr657417Patcher a32p;
   script->assignAddresses();
+  // .ARM.exidx does not require precise addresses, but it does require the
+  // relative addresses of OutputSections because linker scripts can assign
+  // Virtual Addresses to OutputSections that are not monotonically increasing.
+  for (Partition &part : partitions)
+    finalizeSynthetic(part.armExidx);
 
   // Converts call x@GDPLT to call __tls_get_addr
   if (config->emachine == EM_HEXAGON)
     hexagonTLSSymbolUpdate(outputSections);
 
   int assignPasses = 0;
   for (;;) {
     bool changed = target->needsThunks && tc.createThunks(outputSections);
template <class ELFT> void Writer<ELFT>::optimizeBasicBlockJumps() {
 
   for (OutputSection *os : outputSections) {
     std::vector<InputSection *> sections = getInputSections(os);
     for (InputSection *is : sections)
       is->trim();
   }
 }
 
-static void finalizeSynthetic(SyntheticSection *sec) {
-  if (sec && sec->isNeeded() && sec->getParent())
-    sec->finalizeContents();
-}
-
 // In order to allow users to manipulate linker-synthesized sections,
 // we had to add synthetic sections to the input section list early,
 // even before we make decisions whether they are needed. This allows
 // users to write scripts like this: ".mygot : { .got }".
 //
 // Doing it has an unintended side effects. If it turns out that we
 // don't need a .got (for example) at all because there's no
 // relocation that needs a .got, we don't want to emit .got.
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   finalizeSynthetic(in.plt);
   finalizeSynthetic(in.iplt);
   finalizeSynthetic(in.ppc32Got2);
   finalizeSynthetic(in.partIndex);
 
   // Dynamic section must be the last one in this list and dynamic
   // symbol table section (dynSymTab) must be the first one.
   for (Partition &part : partitions) {
-    finalizeSynthetic(part.armExidx);
     finalizeSynthetic(part.dynSymTab);
     finalizeSynthetic(part.gnuHashTab);
     finalizeSynthetic(part.hashTab);
     finalizeSynthetic(part.verDef);
     finalizeSynthetic(part.relaDyn);
     finalizeSynthetic(part.relrDyn);
     finalizeSynthetic(part.ehFrameHdr);
     finalizeSynthetic(part.verSym);

lld/test/ELF/arm-exidx-script-order.s

+// REQUIRES: arm
+// RUN: llvm-mc --arm-add-build-attributes --triple=armv7a-linux-gnueabihf -filetype=obj %s -o %t.o
+// RUN: echo "SECTIONS { \
+// RUN:         . = 0x80000000; \
+// RUN:         .ARM.exidx : { *(.ARM.exidx) } \
+// RUN:         .text : { *(.text) } \
+// RUN:         .text.1 0x80000200 : AT(0x1000) { *(.text.1) } \
+// RUN:         .text.2 0x80000100 : AT(0x2000) { *(.text.2) } \
+// RUN: } " > %t.script
+// RUN: ld.lld --script %t.script %t.o -o %t
+// RUN: llvm-readobj -x .ARM.exidx %t | FileCheck %s
+
+/// When a linker script does not have monotonically increasing addresses
+/// the .ARM.exidx table should still be in monotonically increasing order.
+
+// CHECK: Hex dump of section '.ARM.exidx':
+// 0x80000000 + 0x28 = 0x80000028, 0x80000008 + 0xf8 = 0x80000100 
+// CHECK-NEXT: 0x80000000 24000000 08849780 f8000000 20849980
+// 0x80000010 + 0x1f0 = 0x8000200, 0x80000018 + 0x1ec = 0x8000204
+// CHECK-NEXT: 0x80000010 f0010000 10849880 ec010000 01000000
+
+ .text
+ .global _start
+ .type _start, %function
+_start:
+ .fnstart
+ bx lr
+ .save {r7, lr}
+ .setfp r7, sp, #0
+ .fnend
+
+ .section .text.1, "ax", %progbits
+ .global fn1
+ .type fn1, %function
+fn1:
+ .fnstart
+ bx lr
+ .save {r8, lr}
+ .setfp r8, sp, #0
+ .fnend
+
+ .section .text.2, "ax", %progbits
+ .global fn2
+ .type fn2, %function
+fn2:
+ .fnstart
+ bx lr
+ .save {r9, lr}
+ .setfp r9, sp, #0
+ .fnend
+
+/// Dummy definition for a reference from the personality routine created by
+/// the assembler, use .data to avoid generating a cantunwind table.
+ .section .rodata
+ .global __aeabi_unwind_cpp_pr0
+__aeabi_unwind_cpp_pr0:
+ .word 0