[ELF] Move SHF_LINK_ORDER till OutputSection addresses are known

[psmith]

Summary

Sections L with the SHF_LINK_ORDER flag must be ordered in the same relative order as the Sections they have a link to. When using a linker script an arbitrary expression may be used for the virtual address of the OutputSection. In some cases the virtual address does not monotonically increase as the OutputSection index increases, so if we base the ordering of the SHF_LINK_ORDER sections on the index then we can get the order wrong. We fix this by moving SHF_LINK_ORDER resolution till after we have created OutputSection virtual addresses.

This is a follow up patch from D78422 which moved the .ARM.exidx to a similar place.

[grimar]

This LGTM. Please wait for another approvement.

nit: the patch is missing content.

(I am on vacation until 12 of May).

lld/ELF/Writer.cpp

2135

nit: unrelated comment change.

lld/test/ELF/linkorder-script.s

12

nit: double space after .linkorder

24

nit: I'd probably just use nop for text*

[psmith]

Add context to diff

[MaskRay]

lld/ELF/Writer.cpp

2131

Confirmed that gc-sections-linkorder-err.s (initially added in D67761) needs early-return here.

lld/test/ELF/linkorder-script.s

24

You can use nop for .text* and .byte for .linkorder*

Everything being one-byte makes it easier to recognize the section order.

[MaskRay]

Sections L with the SHF_LINK_ORDER flag must be ordered in the same relative order as the Sections they have a link to.

s/Sections L/Sections/

[psmith]

Thanks for the comments. I've updated the patch prior to commit.

lld/ELF/Writer.cpp

 
 static bool compareByFilePosition(InputSection *a, InputSection *b) {
   InputSection *la = a->getLinkOrderDep();
   InputSection *lb = b->getLinkOrderDep();
   OutputSection *aOut = la->getParent();
   OutputSection *bOut = lb->getParent();
 
   if (aOut != bOut)
-    return aOut->sectionIndex < bOut->sectionIndex;
+    return aOut->addr < bOut->addr;
   return la->outSecOff < lb->outSecOff;
 }
 
 template <class ELFT> void Writer<ELFT>::resolveShfLinkOrder() {
   for (OutputSection *sec : outputSections) {
     if (!(sec->flags & SHF_LINK_ORDER))
       continue;
 

 // 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.
+  // .ARM.exidx and SHF_LINK_ORDER do not require precise addresses, but they
+  // do 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);
+  resolveShfLinkOrder();
 
   // 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);
for (Partition &part : partitions) {
     finalizeSynthetic(part.verSym);
     finalizeSynthetic(part.verNeed);
     finalizeSynthetic(part.dynamic);
   }
 
   if (!script->hasSectionsCommand && !config->relocatable)
     fixSectionAlignments();
 
-  // SHFLinkOrder processing must be processed after relative section placements are
-  // known but before addresses are allocated.
-  resolveShfLinkOrder();
-  if (errorCount())
-    return;
-
   // This is used to:
   // 1) Create "thunks":
   //    Jump instructions in many ISAs have small displacements, and therefore
   //    they cannot jump to arbitrary addresses in memory. For example, RISC-V
   //    JAL instruction can target only +-1 MiB from PC. It is a linker's
   //    responsibility to create and insert small pieces of code between
   //    sections to extend the ranges if jump targets are out of range. Such
   //    code pieces are called "thunks".
   //
   //    We add thunks at this stage. We couldn't do this before this point
   //    because this is the earliest point where we know sizes of sections and
   //    their layouts (that are needed to determine if jump targets are in
   //    range).
   //
   // 2) Update the sections. We need to generate content that depends on the
   //    address of InputSections. For example, MIPS GOT section content or
   //    android packed relocations sections content.
   //
   // 3) Assign the final values for the linker script symbols. Linker scripts
   //    sometimes using forward symbol declarations. We want to set the correct
   //    values. They also might change after adding the thunks.
   finalizeAddressDependentContent();
+  if (errorCount())
+    return;
 
-  // finalizeAddressDependentContent may have added local symbols to the static symbol table.
+  // finalizeAddressDependentContent may have added local symbols to the static
+  // symbol table.
   finalizeSynthetic(in.symTab);
   finalizeSynthetic(in.ppc64LongBranchTarget);
 
   // Relaxation to delete inter-basic block jumps created by basic block
   // sections. Run after in.symTab is finalized as optimizeBasicBlockJumps
   // can relax jump instructions based on symbol offset.
   if (config->optimizeBBJumps)
     optimizeBasicBlockJumps();

lld/test/ELF/linkorder-script.s

+// REQUIRES: x86
+// RUN: llvm-mc --triple=x86_64 -filetype=obj %s -o %t.o
+// RUN: echo "SECTIONS { \
+// RUN:         . = 0x80000000; \
+// RUN:         .linkorder : { *(.linkorder.*) } \
+// 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 .linkorder  %t | FileCheck %s
+
+/// When a linker script does not have monotonically increasing addresses
+/// the SHF_LINK_ORDER sections should still be in monotonically increasing
+/// order.
+
+// CHECK: Hex dump of section '.linkorder':
+// CHECK-NEXT: 0x80000000 02000000 00000000 01000000 00000000
+
+.section .text.1, "ax", %progbits
+.global _start
+_start:
+.quad 0
+
+.section .text.2, "ax", %progbits
+.quad 0
+
+.section .linkorder.1, "ao", %progbits, .text.1
+.quad 1
+
+.section .linkorder.2, "ao", %progbits, .text.2
+.quad 2