[ELF] Allow SHF_LINK_ORDER sections to have sh_link=0

[MaskRay]

Summary

Part of https://bugs.llvm.org/show_bug.cgi?id=41734

The semantics of SHF_LINK_ORDER have been extended to represent metadata
sections associated with some other sections (usually text).

The associated text section may be discarded (e.g. LTO) and we want the
metadata section to have sh_link=0 (D72899, D76802).

Normally the metadata section is only referenced by the associated text
section. sh_link=0 means the associated text section is discarded, and
the metadata section will be garbage collected. If there is another
section (.gc_root) referencing the metadata section, the metadata
section will be retained. It's the .gc_root consumer's job to validate
the metadata sections.

# This creates a SHF_LINK_ORDER .meta with sh_link=0
.section .meta,"awo",@progbits,0
1:
.section .meta,"awo",@progbits,foo
2:

.section .gc_root,"a",@progbits
.quad 1b
.quad 2b

[merge_guards_bot]

Unit tests: fail. 61935 tests passed, 2 failed and 783 were skipped.

failed: LLVM-Unit.TableGen/_/TableGenTests/Automata.BinPackerAutomatonAccepts
failed: LLVM-Unit.TableGen/_/TableGenTests/Automata.BinPackerAutomatonExplains

clang-tidy: unknown.

clang-format: pass.

Build artifacts: diff.json, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[peter.smith]

I'm reluctantly in favour of making the change on the basis that there exists a design using SHF_LINKORDER that lets this happen. My reservation is that in some use cases of SHF_LINKORDER such as .ARM.exidx sections where there is a 1 : 1 relationship between meta-data and "content" (for want of a better word) section then sh_link = 0 would be a sign that something had gone badly wrong. Having said that there isn't any thing in ELF that forbids the use case that this needs. I think that for .ARM.exidx which is the other main user of SHF_LINKORDER we handle it as a special case so this shouldn't make a difference in practice.

[lebedev.ri]

Reverse-ping, thanks.

[pcc]

Should we drop this and just let users set sh_link=self if they want these semantics?

[phosek]

In D72904#2071861, @pcc wrote:

Should we drop this and just let users set sh_link=self if they want these semantics?

One issue I ran into while trying to use sh_link=self in D76802 is that bfd.ld doesn't seem to handle that case: older versions of bfd.ld report an error while the tip-of-tree version hits an infinite loop.

[MaskRay]

Rebase. Referenced D76802

[MaskRay]

@pcc @phosek PTAL (after offline discussion)

@grimar @jhenderson @psmith: @pcc, @phosek and I discussed non-contiguous SHF_LINK_ORDER. An agreement among us is that we should just relax D77007 further to allow non-contiguous SHF_LINK_ORDER.
I placed sh_link=0 sections after sh_link!=0 sections to match the Solaris behavior. (https://groups.google.com/forum/#!topic/generic-abi/hgx_m1aXqUo Ali does not seem to want a new section flag so a generic ELF ABI section flag seems a no-go)

With a new section flag (SHF_ASSOCIATED), we still have to think of mixed section flag & mixed sh_link cases. I don't particularly like the non-orthogonality of SHF_LINK_ORDER but adding a new section flag will not make implementation easier.

[jhenderson]

Whilst the actual change seems fine, in that it does what it sets out to do, I believe, I'm struggling to follow why a SHF_LINK_ORDER section should have a sh_link of 0 at all. Surely the section should just then not have SHF_LINK_ORDER? What sections actually have sh_link=0 and SHF_LINK_ORDER?

[psmith]

In D72904#2157639, @jhenderson wrote:

Whilst the actual change seems fine, in that it does what it sets out to do, I believe, I'm struggling to follow why a SHF_LINK_ORDER section should have a sh_link of 0 at all. Surely the section should just then not have SHF_LINK_ORDER? What sections actually have sh_link=0 and SHF_LINK_ORDER?

From memory there was an unfortunate interaction with Garbage Collection that ended up with sh_link being 0. I think in the PR there was something like:

• non-live-section <- metadata1 (SHF_LINK_ORDER) to non-live-section
• live-section -> metadata1

The non-live-section was removed but due to another live-section referencing the metadata was kept.

I'm not particularly keen on use of SHF_LINK_ORDER just for garbage collection, but I don't think that view is the majority so on balance being robust to this situation is definitely better than a crash/assertion failure.

[MaskRay]

See also @jhenderson's latest reply to the generic-abi thread "SHF_LINK_ORDER's original semantics make upgrade difficult"

# input.o:
<table header> [common]
- DW_TAG_compile_unit [common]
-- DW_TAG_variable [.data.foo]
-- DW_TAG_namespace [common]
--- DW_TAG_subprogram [.text.bar]
--- DW_TAG_variable [.data.baz]
<table footer> [common]

@pcc I sent the patches since you expressed a preference on more work on SHF_LINK_ORDER. Though, @jhenderson's needs (and my header/footer argument in that thread) make me think more whether we should continue patching SHF_LINK_ORDER or start pursuing another section flag.

Without metadata sections's override, SHF_LINK_ORDER will have very few use cases. The problems still exist but we probably don't really need to address them.

[pcc]

In D72904#2164880, @MaskRay wrote:

See also @jhenderson's latest reply to the generic-abi thread "SHF_LINK_ORDER's original semantics make upgrade difficult"

# input.o:
<table header> [common]
- DW_TAG_compile_unit [common]
-- DW_TAG_variable [.data.foo]
-- DW_TAG_namespace [common]
--- DW_TAG_subprogram [.text.bar]
--- DW_TAG_variable [.data.baz]
<table footer> [common]

@pcc I sent the patches since you expressed a preference on more work on SHF_LINK_ORDER. Though, @jhenderson's needs (and my header/footer argument in that thread) make me think more whether we should continue patching SHF_LINK_ORDER or start pursuing another section flag.

Without metadata sections's override, SHF_LINK_ORDER will have very few use cases. The problems still exist but we probably don't really need to address them.

I think it is too premature to consider adding a section flag, since they are a limited resource. Furthermore, adding a flag whose absence means "use the linker's default input section ordering", and creating compiler features that rely on said default input section order, may constrain us in the future if we want to change the default order (consider features like ICF). Ideally, we would create a flag that means "instead of using the normal SHF_LINK_ORDER ordering, use this other ordering". But that would require specifying exactly what that means so that future linker changes don't break it.

lld/test/ELF/linkorder-mixed.test

1

This can become a .s if we implement the parser changes in D72899, no?

[jhenderson]

In D72904#2165103, @pcc wrote:

In D72904#2164880, @MaskRay wrote:

See also @jhenderson's latest reply to the generic-abi thread "SHF_LINK_ORDER's original semantics make upgrade difficult"

# input.o:
<table header> [common]
- DW_TAG_compile_unit [common]
-- DW_TAG_variable [.data.foo]
-- DW_TAG_namespace [common]
--- DW_TAG_subprogram [.text.bar]
--- DW_TAG_variable [.data.baz]
<table footer> [common]

@pcc I sent the patches since you expressed a preference on more work on SHF_LINK_ORDER. Though, @jhenderson's needs (and my header/footer argument in that thread) make me think more whether we should continue patching SHF_LINK_ORDER or start pursuing another section flag.

Without metadata sections's override, SHF_LINK_ORDER will have very few use cases. The problems still exist but we probably don't really need to address them.

I think it is too premature to consider adding a section flag, since they are a limited resource. Furthermore, adding a flag whose absence means "use the linker's default input section ordering", and creating compiler features that rely on said default input section order, may constrain us in the future if we want to change the default order (consider features like ICF). Ideally, we would create a flag that means "instead of using the normal SHF_LINK_ORDER ordering, use this other ordering". But that would require specifying exactly what that means so that future linker changes don't break it.

I think the new flag would not have anything to do with ordering, and would be used for the depedency relationship currently specified by SHF_LINK_ORDER - thus a section could be associated with another section, but not want any reordering. That being said, as mentioned in the gABI thread, the group section approach might be better. Some brief experimentation I did yesterday suggested that fragmenting the DWARF had no significant performance impact, which might suggest that the additional section overhead of a group section is actually harmless. However, I have yet to verfiy either that idea, or my initial results.

[MaskRay]

Rebase after D72899.

Rewrite a yaml test with assembly

[MaskRay]

D72899 has been submitted. PTAL

My understanding about the situation:

• The overloaded semantics of SHF_LINK_ORDER are indeed unfortunate and do get in the way.
• GNU ld already has support for SHF_LINK_ORDER, and chances are that the maintainers will not be object to mixed SHF_LINK_ORDER & non-SHF_LINK_ORDER (Solaris ld has done this for years)
• It'd be difficult to get a new section flag for metadata semantics. Even if we can invent one for LLVM, we want to defer the decision because an early decision may restrict our design space. We might not be able to sort out all the implications. (I highly believe in this)
• In the meantime,,,,,,,, let's stick with SHF_LINK_ORDER. The Solaris ld semantics are not too bad. We can just follow. We can continue using SHF_LINK_ORDER until we botch it ;-)
• TODO Allow non-contiguous SHF_LINK_ORDER sections in an output section in the comment will be fixed by D84001

@lebedev.ri Is https://bugs.llvm.org/show_bug.cgi?id=41734 still alive and does this address the problem?

[jhenderson]

Looks reasonable to me, but a second opinion is probably worth getting.

By the way, I realised I messed up my initial investigation I mentioned about fragmenting DWARF sections proving reasonable from a performance perspective - after I fixed the issue, a second attempt showed serious performance issues. The .group section idea will likely have the same issue, so the approach as a whole may be a non-starter given the current DWARF format and cost of sections in LLD.

[pcc]

LGTM

[thakis]

This breaks tests on windows: http://45.33.8.238/win/21396/step_10.txt

(Probably just needs a triple)

[MaskRay]

In D72904#2198162, @thakis wrote:

This breaks tests on windows: http://45.33.8.238/win/21396/step_10.txt

(Probably just needs a triple)

Thanks. Fixed by eb45b978b7d646a7fb96a2734e44d03b2a066dfa

lld/ELF/InputFiles.cpp

void ObjFile<ELFT>::initializeSections(bool ignoreComdats) {
   for (size_t i = 0, e = objSections.size(); i < e; ++i) {
     if (this->sections[i] == &InputSection::discarded)
       continue;
     const Elf_Shdr &sec = objSections[i];
 
     if (sec.sh_type == SHT_REL || sec.sh_type == SHT_RELA)
       this->sections[i] = createInputSection(sec);
 
-    if (!(sec.sh_flags & SHF_LINK_ORDER))
+    // A SHF_LINK_ORDER section with sh_link=0 is handled as if it did not have
+    // the flag.
+    if (!(sec.sh_flags & SHF_LINK_ORDER) || !sec.sh_link)
       continue;
 
-    // .ARM.exidx sections have a reverse dependency on the InputSection they
-    // have a SHF_LINK_ORDER dependency, this is identified by the sh_link.
     InputSectionBase *linkSec = nullptr;
     if (sec.sh_link < this->sections.size())
       linkSec = this->sections[sec.sh_link];
     if (!linkSec)
       fatal(toString(this) + ": invalid sh_link index: " + Twine(sec.sh_link));
 
+    // A SHF_LINK_ORDER section is discarded if its linked-to section is
+    // discarded.
     InputSection *isec = cast<InputSection>(this->sections[i]);
     linkSec->dependentSections.push_back(isec);
     if (!isa<InputSection>(linkSec))
       error("a section " + isec->name +
             " with SHF_LINK_ORDER should not refer a non-regular section: " +
             toString(linkSec));
   }
 

lld/ELF/InputSection.cpp

void InputSectionBase::parseCompressedHeader() {
   }
 
   uncompressedSize = hdr->ch_size;
   alignment = std::max<uint32_t>(hdr->ch_addralign, 1);
   rawData = rawData.slice(sizeof(*hdr));
 }
 
 InputSection *InputSectionBase::getLinkOrderDep() const {
-  assert(link);
   assert(flags & SHF_LINK_ORDER);
+  if (!link)
+    return nullptr;
   return cast<InputSection>(file->getSections()[link]);
 }
 
 // Find a function symbol that encloses a given location.
 template <class ELFT>
 Defined *InputSectionBase::getEnclosingFunction(uint64_t offset) {
   for (Symbol *b : file->getSymbols())
     if (Defined *d = dyn_cast<Defined>(b))

lld/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::sortSections() {
   }
 
   script->adjustSectionsAfterSorting();
 }
 
 static bool compareByFilePosition(InputSection *a, InputSection *b) {
   InputSection *la = a->getLinkOrderDep();
   InputSection *lb = b->getLinkOrderDep();
+  // 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;
 }
 
for (BaseCommand *base : sec->sectionCommands) {
                   " are not contiguous");
           } else {
             started = true;
 
             scriptSections.push_back(&isec);
             sections.push_back(isec);
 
             InputSection *link = isec->getLinkOrderDep();
-            if (!link->getParent())
+            if (link && !link->getParent())
               error(toString(isec) + ": sh_link points to discarded section " +
                     toString(link));
           }
         }
       } else if (started) {
         stopped = true;
       }
     }

lld/test/ELF/invalid/linkorder-invalid-sec2.test

-# REQUIRES: x86
-# RUN: yaml2obj %s -o %t.o
-# RUN: not ld.lld %t.o -o /dev/null 2>&1 | FileCheck %s
-# CHECK: invalid sh_link index: 0
-
---- !ELF
-FileHeader:
-  Class:           ELFCLASS64
-  Data:            ELFDATA2LSB
-  Type:            ET_REL
-  Machine:         EM_X86_64
-Sections:
-  - Name:          .linkorder
-    Type:          SHT_PROGBITS
-    Flags:         [ SHF_ALLOC, SHF_EXECINSTR, SHF_LINK_ORDER ]
-    Link:          0

lld/test/ELF/linkorder-mixed.test

+## 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: yaml2obj %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: yaml2obj -D EXTRA='.linkorder (4)' %s -o %t.o
+# RUN: not ld.lld %t.o -o /dev/null
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_REL
+  Machine: EM_X86_64
+Sections:
+  - Name: .text (0)
+    Type:  SHT_PROGBITS
+    Flags: [ SHF_ALLOC, SHF_EXECINSTR ]
+  - Name: .text (1)
+    Type:  SHT_PROGBITS
+    Flags: [ SHF_ALLOC, SHF_EXECINSTR ]
+  - Name:  .linkorder (0)
+    Type:  SHT_PROGBITS
+    Flags: [ SHF_ALLOC, SHF_LINK_ORDER ]
+    Link:  0
+    Content: 00
+  - Name:  .linkorder (1)
+    Type:  SHT_PROGBITS
+    Flags: [ SHF_ALLOC, SHF_LINK_ORDER ]
+    Link:  1
+    Content: 01
+  - Name:  .linkorder (2)
+    Type:  SHT_PROGBITS
+    Flags: [ SHF_ALLOC, SHF_LINK_ORDER ]
+    Link:  2
+    Content: 02
+  - Name:  [[EXTRA=.ignore]]
+    Type:  SHT_PROGBITS
+    Flags: [ SHF_ALLOC ]
+    Content: 04
+  - Name:  .linkorder (3)
+    Type:  SHT_PROGBITS
+    Flags: [ SHF_ALLOC, SHF_LINK_ORDER ]
+    Link:  0
+    Content: 03