[ELF] Allow mixed SHF_LINK_ORDER & non-SHF_LINK_ORDER sections and sort within InputSectionDescription

[MaskRay]

Summary

LLD currently does not allow non-contiguous SHF_LINK_ORDER components in an
output section. This makes it infeasible to add SHF_LINK_ORDER to an existing
metadata section if backward compatibility with older object files are
concerned.

We did not allow mixed components (like GNU ld) and D77007 relaxed to allow
non-contiguous SHF_LINK_ORDER components. This patch allows arbitrary mix, with
sorting performed within an InputSectionDescription. For example,
.rodata : {*(.rodata.foo) *(.rodata.bar)}, has two InputSectionDescription's.
If there is at least one SHF_LINK_ORDER and at least one non-SHF_LINK_ORDER in
.rodata.foo, they are ordered within *(.rodata.foo): we arbitrarily place
SHF_LINK_ORDER components before non-SHF_LINK_ORDER components (like Solaris ld).

*(.rodata.bar) is ordered similarly, but the two InputSectionDescription's
don't interact. It can be argued that this is more reasonable than the previous
behavior where written order was not respected.

It would be nice if the two different semantics (ordering requirement & garbage
collection) were not overloaded on one section flag, however, it is probably
difficult to obtain a generic flag at this point
(https://groups.google.com/forum/#!topic/generic-abi/hgx_m1aXqUo
"SHF_LINK_ORDER's original semantics make upgrade difficult").

(Actually, without the GC semantics, SHF_LINK_ORDER would still have the
sh_link!=0 & sh_link=0 issue. It is just that people find the GC semantics more
useful and tend to use the feature more often.)

GNU ld feature request: https://sourceware.org/bugzilla/show_bug.cgi?id=16833

[psmith]

I'll take a look over the weekend, also at D72904, apologies won't be able to get to it today.

[jhenderson]

This is definitely an improvement from my point of view, so in general +1 from me.

FWIW, this doesn't help my specific use-case because all my debug sections have the same name, so can't be distinguished in linker scripts, but the ordering needs to be maintained the same as the input ordering, so I end up with a mix of ordered and unordered sections, which with this change would be allowed, but would end up with all the ordered ones first (and thus the underlying assumption would be broken). Example:

.debug_info [common1]
.debug_info [referencing .text.1]
.debug_info [common2]
.debug_info [referencing .text.2]
...

will end up as:

.debug_info [.text.1]
.debug_info [.text.2]
.debug_info [common1]
.debug_info [common2]

which will not be a valid structure. Anyway, I don't think there's anything that can be done here without disabling the sorting entirely.

lld/test/ELF/linkerscript/linkorder.s

56

You don't use the section header dump here. Can you get rid of -S?

59

I'm either missing something, or something odd is going on here. Where are the cccccc coming from? There doesn't appear to be a .text section with any contents - it has the _start symbol in, if I follow correctly, but should be empty; nothing specifies alignment requirements either here.

69–70

This section doesn't seem to be being used?

78–79

It seems to me like you need test cases for sh_link=0 for SHF_LINK_ORDER sections here too?

[grimar]

lld/ELF/Writer.cpp

1615

This comment needs updating.

1665

Consider reordering to reduce nesting and to remove clear() calls:

// Link order may be distributed across several InputSectionDescriptions.
// Sorting is performed separately.
for (BaseCommand *base : sec->sectionCommands) {
  auto *isd = dyn_cast<InputSectionDescription>(base);
  if (!isd)
    continue;

  bool hasLinkOrder = false;
  std::vector<InputSection **> scriptSections;
  std::vector<InputSection *> sections;
  for (InputSection *&isec : isd->sections) {
    if (isec->flags & SHF_LINK_ORDER) {
      InputSection *link = isec->getLinkOrderDep();
      if (link && !link->getParent())
        error(toString(isec) + ": sh_link points to discarded section " +
              toString(link));
      hasLinkOrder = true;
    }
    scriptSections.push_back(&isec);
    sections.push_back(isec);
  }

  if (!hasLinkOrder || errorCount())
    continue;

  llvm::stable_sort(sections, compareByFilePosition);
  for (int i = 0, n = sections.size(); i < n; ++i)
    *scriptSections[i] = sections[i];
}

[grimar]

lld/ELF/Writer.cpp

1665

Aside: we can replace constructions like:

for (BaseCommand *base : sec->sectionCommands) {
  auto *isd = dyn_cast<InputSectionDescription>(base);
  if (!isd)
    continue;

with just

for (auto *isd: filter<InputSectionDescription>(sec->sectionCommands)) {

here and in many other places in LLD if we land D45166 + D45490.

[psmith]

lld/ELF/Writer.cpp

1638

I think we need to be careful here. This is not a problem for .ARM.exidx as we handle it as a special case, but if we followed this pattern it could cause problems. For example a typical ld.bfd linker script has:

.ARM.exidx : { *(.arm.exidx) *(.arm.exidx.*) }

The intent is to form a single table with the sorting order considered all at once. The script above would create two InputSectionDescriptions and if sorted independently could be in the wrong order. There may be other similar cases that follow the .name and .name.suffix pattern.

A possible heuristic is that if all the input section descriptions have SHF_LINK_ORDER then consider them all at once. If there is a mix of SHF_LINK_ORDER and non SHF_LINK_ORDER then it is unlikely that the ordering requirements are being used.

[pcc]

lld/ELF/Writer.cpp

1638

.ARM.exidx : { *(.arm.exidx) *(.arm.exidx.*) }

I think this unambiguously means to sort the groups separately. If the intent was to sort them together, it should have been written as

.ARM.exidx : { *(.arm.exidx .arm.exidx.*) }

But it doesn't look like we can expect linker scripts to be doing this in the first place though? Looking at binutils I see things in the default linker scripts like

ld/testsuite/ld-arm/arm.ld:  .ARM.exidx : { *(.ARM.exidx*) }

which would lead to the correct behavior. And looking at the history of that file it's been that way since the beginning. Presumably if people are copy/pasting from binutils into their linker scripts then they would have a similar clause to this which would be handled correctly.

A possible heuristic is that if all the input section descriptions have SHF_LINK_ORDER then consider them all at once. If there is a mix of SHF_LINK_ORDER and non SHF_LINK_ORDER then it is unlikely that the ordering requirements are being used.

I don't think we should work around broken linker scripts like this, at least not without more evidence that it is a problem, since it will complicate cases involving symbol assignments. For example, in this case:

.foo {
 start_foo = .;
  *(.foo)
  stop_foo = .;
  start_bar = .;
  *(.bar)
  stop_bar = .;
}

start_foo/stop_foo and start_bar/stop_bar would need to cover the correct parts of .foo even if .foo or .bar have SHF_LINK_ORDER sections.

[MaskRay]

Rebase

lld/test/ELF/linkerscript/linkorder.s

59

sh_addralign(.text)=4. lld fills the gap with traps.

78–79

linkorder-mixed.test tested sh_link=0 for SHF_LINK_ORDER sections

[MaskRay]

Rebase after D72904 was pushed

[MaskRay]

Ping..

[psmith]

Given that it is possible to write a linker script that does work with *(pattern1 pattern2) then I don't have any objections. I've tentatively approved as it looks like was the most cautious here.

[MaskRay]

lld/test/ELF/linkerscript/linkorder.s

69–70

This was a leftover from a previous patch where I probably wanted to test an orphan section. It is unrelated to this patch so I will not deal with it. It may find new uses if we take another think about the organization of tests.

[MaskRay]

Address comments

[MaskRay]

Pushed after offline confirmation with pcc.

lld/ELF/Writer.cpp

while (nonScriptI != e) {
     std::rotate(pos, nonScriptI, end);
     nonScriptI = end;
   }
 
   script->adjustSectionsAfterSorting();
 }
 
 static bool compareByFilePosition(InputSection *a, InputSection *b) {
-  InputSection *la = a->getLinkOrderDep();
-  InputSection *lb = b->getLinkOrderDep();
+  InputSection *la = a->flags & SHF_LINK_ORDER ? a->getLinkOrderDep() : nullptr;
+  InputSection *lb = b->flags & SHF_LINK_ORDER ? b->getLinkOrderDep() : nullptr;
   // SHF_LINK_ORDER sections with non-zero sh_link are ordered before others.
   if (!la || !lb)
     return la && !lb;
   OutputSection *aOut = la->getParent();
   OutputSection *bOut = lb->getParent();
 
   if (aOut != bOut)
     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;
 
     // The ARM.exidx section use SHF_LINK_ORDER, but we have consolidated
     // this processing inside the ARMExidxsyntheticsection::finalizeContents().
     if (!config->relocatable && config->emachine == EM_ARM &&
         sec->type == SHT_ARM_EXIDX)
       continue;
 
-    // Link order may be distributed across several InputSectionDescriptions
-    // but sort must consider them all at once.
+    // Link order may be distributed across several InputSectionDescriptions.
+    // Sorting is performed separately.
     std::vector<InputSection **> scriptSections;
     std::vector<InputSection *> sections;
-    bool started = false, stopped = false;
     for (BaseCommand *base : sec->sectionCommands) {
       if (auto *isd = dyn_cast<InputSectionDescription>(base)) {
+        bool hasLinkOrder = false;
+        scriptSections.clear();
+        sections.clear();
         for (InputSection *&isec : isd->sections) {
-          if (!(isec->flags & SHF_LINK_ORDER)) {
-            if (started)
-              stopped = true;
-          } else if (stopped) {
-            error(toString(isec) + ": SHF_LINK_ORDER sections in " + sec->name +
-                  " are not contiguous");
-          } else {
-            started = true;
-
-            scriptSections.push_back(&isec);
-            sections.push_back(isec);
-
+          if (isec->flags & SHF_LINK_ORDER) {
             InputSection *link = isec->getLinkOrderDep();
             if (link && !link->getParent())
               error(toString(isec) + ": sh_link points to discarded section " +
                     toString(link));
+            hasLinkOrder = true;
           }
+          scriptSections.push_back(&isec);
+          sections.push_back(isec);
         }
-      } else if (started) {
-        stopped = true;
-      }
-    }
-
-    if (errorCount())
-      continue;
-
+        if (hasLinkOrder && errorCount() == 0) {
           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

lld/test/ELF/linkerscript/linkorder.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 
 ## Contiguous SHF_LINK_ORDER sections.
-# RUN: echo 'SECTIONS { .rodata : {BYTE(0) *(.rodata*) BYTE(3)} \
+# RUN: echo 'SECTIONS { .rodata : {BYTE(0) *(.rodata*) BYTE(4)} \
 # RUN:   .text : {*(.text.bar) *(.text.foo)} }' > %t.lds
 # RUN: ld.lld -T %t.lds %t.o -o %t
 # RUN: llvm-readelf -S -x .rodata -x .text %t | FileCheck %s
 
 # CHECK:      [ 1] .rodata   {{.*}} AL 3
 # CHECK:      [ 3] .text     {{.*}} AX 0
 # CHECK:      Hex dump of section '.rodata':
-# CHECK-NEXT: 00020103
+# CHECK-NEXT: 00030102 04
 # CHECK:      Hex dump of section '.text':
 # CHECK-NEXT: 0201
 
-# RUN: echo 'SECTIONS { .rodata : {BYTE(0) *(.rodata*) BYTE(3)} \
+# RUN: echo 'SECTIONS { .rodata : {BYTE(0) *(.rodata*) BYTE(4)} \
 # RUN:  .text : {*(.text.foo) *(.text.bar)} }' > %t1.lds
 # RUN: ld.lld -T %t1.lds %t.o -o %t1
 # RUN: llvm-readelf -S -x .rodata -x .text %t1 | FileCheck --check-prefix=CHECK1 %s
 
 # CHECK1:      [ 1] .rodata   {{.*}} AL 3
 # CHECK1:      [ 3] .text     {{.*}} AX 0
 # CHECK1:      Hex dump of section '.rodata':
-# CHECK1-NEXT: 00010203
+# CHECK1-NEXT: 00010302 04
 # CHECK1:      Hex dump of section '.text':
 # CHECK1-NEXT: 0102
 
 ## Adjacent input sections descriptions are contiguous.
-## Orphan section .text.bar precedes .text.foo, so swap the order of .rodata.*
+## Orphan section .text.bar precedes .text.foo. However, don't swap the order of .rodata.*
+## because they are in different InputSectionDescriptions.
 # RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) *(.rodata.bar)} }' > %t2.lds
 # RUN: ld.lld -T %t2.lds %t.o -o %t2
 # RUN: llvm-readelf -S -x .rodata %t2 | FileCheck --check-prefix=CHECK2 %s
 
-# CHECK2:      [ 1] .rodata   {{.*}} AL 4
+# CHECK2:      [ 1] .rodata   {{.*}} AL 5
 # CHECK2:      [ 4] .text.bar {{.*}} AX 0
+# CHECK2:      [ 5] .text.foo {{.*}} AX 0
 # CHECK2:      Hex dump of section '.rodata':
-# CHECK2-NEXT: 0201
+# CHECK2-NEXT: 010302
 
 ## Non-contiguous SHF_LINK_ORDER sections, separated by a BYTE.
-# RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) BYTE(0) *(.rodata.bar)} }' > %terr1.lds
-# RUN: not ld.lld -T %terr1.lds %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR %s
+# RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) BYTE(0) *(.rodata.bar)} }' > %t3.lds
+# RUN: ld.lld -T %t3.lds %t.o -o %t3
+# RUN: llvm-readelf -S -x .rodata %t3 | FileCheck --check-prefix=CHECK3 %s
+
+# CHECK3:      [ 1] .rodata   {{.*}} AL 5
+# CHECK3:      [ 4] .text.bar {{.*}} AX 0
+# CHECK3:      [ 5] .text.foo {{.*}} AX 0
+# CHECK3:      Hex dump of section '.rodata':
+# CHECK3-NEXT: 01000302
 
 ## Non-contiguous SHF_LINK_ORDER sections, separated by a non-SHF_LINK_ORDER section.
-# RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) *(.text) *(.rodata.bar)} }' > %terr2.lds
-# RUN: not ld.lld -T %terr2.lds %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR %s
+# RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) *(.text) *(.rodata.bar)} }' > %t4.lds
+# RUN: ld.lld -T %t4.lds %t.o -o %t4
+# RUN: llvm-readelf -S -x .rodata %t4 | FileCheck --check-prefix=CHECK4 %s
 
-## Non-contiguous SHF_LINK_ORDER sections, separated by a symbol assignment.
-# RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) a = .; *(.rodata.bar)} }' > %terr3.lds
-# RUN: not ld.lld -T %terr3.lds %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR %s
+# CHECK4:      Hex dump of section '.rodata':
+# CHECK4-NEXT: 01cccccc 0302
 
-# ERR: error: {{.*}}.o:(.rodata.bar): SHF_LINK_ORDER sections in .rodata are not contiguous
+## Non-contiguous SHF_LINK_ORDER sections, separated by a symbol assignment.
+# RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) a = .; *(.rodata.bar)} }' > %t5.lds
+# RUN: ld.lld -T %t5.lds %t.o -o %t5
+# RUN: llvm-readelf -S -x .rodata %t5 | FileCheck --check-prefix=CHECK2 %s
 
 .global _start
 _start:
 
 .section .ro,"a"
 .byte 0
 
 .section .text.bar,"a",@progbits
 .byte 2
 .section .text.foo,"a",@progbits
 .byte 1
 .section .rodata.foo,"ao",@progbits,.text.foo
 .byte 1
-.section .rodata.bar,"ao",@progbits,.text.bar
+## If the two .rodata.bar sections are in the same InputSectionDescription,
+## 03 (sh_link!=0) will be ordered before 02 (sh_link=0).
+.section .rodata.bar,"a",@progbits
 .byte 2
+.section .rodata.bar,"ao",@progbits,.text.bar
+.byte 3

lld/test/ELF/linkorder-mixed.s

 # REQUIRES: x86
 ## Test that we allow SHF_LINK_ORDER sections with sh_link=0.
 ## SHF_LINK_ORDER sections with sh_link!=0 are ordered before others.
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
 # RUN: ld.lld %t.o -o %t
 # RUN: llvm-readelf -S -x .linkorder %t | FileCheck %s
 
 # CHECK:      [Nr] Name       {{.*}} Size   ES Flg Lk Inf
 # CHECK-NEXT: [ 0]            {{.*}}
 # CHECK-NEXT: [ 1] .linkorder {{.*}} 000004 00  AL  3   0
 # CHECK-NEXT: [ 2] .ignore    {{.*}}
 # CHECK-NEXT: [ 3] .text      {{.*}}
 
 # CHECK:      Hex dump of section '.linkorder':
 # CHECK-NEXT:   [[#%x,ADDR:]] 01020003
 
-## TODO Allow non-contiguous SHF_LINK_ORDER sections in an output section.
 # RUN: llvm-mc --filetype=obj -triple=x86_64 --defsym EXTRA=1 %s -o %t.o
-# RUN: not ld.lld %t.o -o /dev/null
+# RUN: ld.lld %t.o -o %t1
+# RUN: llvm-readelf -S -x .linkorder %t1 | FileCheck %s --check-prefix=CHECK1
+
+# CHECK1:      [Nr] Name       {{.*}} Size   ES Flg Lk Inf
+# CHECK1-NEXT: [ 0]            {{.*}}
+# CHECK1-NEXT: [ 1] .linkorder {{.*}} 000005 00  AL  2   0
+# CHECK1-NEXT: [ 2] .text      {{.*}}
+
+# CHECK1:      Hex dump of section '.linkorder':
+# CHECK1-NEXT:   [[#%x,ADDR:]] 01020004 03
 
 .section .text,"ax",@progbits,unique,0
 .Ltext0:
 .section .text,"ax",@progbits,unique,1
 .Ltext1:
 .section .linkorder,"ao",@progbits,0,unique,0
   .byte 0
 .section .linkorder,"ao",@progbits,.Ltext0