This is an archive of the discontinued LLVM Phabricator instance.

[ELF] Allow SHF_LINK_ORDER sections to have sh_link=0
ClosedPublic

Authored by MaskRay on Jan 17 2020, 1:01 AM.

Details

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

Diff Detail

Event Timeline

MaskRay created this revision.Jan 17 2020, 1:01 AM

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

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.

Reverse-ping, thanks.

pcc added a comment.Jun 3 2020, 11:09 AM

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

phosek added a subscriber: phosek.Jun 10 2020, 8:57 PM
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 updated this revision to Diff 278585.EditedJul 16 2020, 12:53 PM
MaskRay edited the summary of this revision. (Show Details)
MaskRay edited reviewers, added: jhenderson, psmith; removed: peter.smith.

Rebase. Referenced D76802

MaskRay added a comment.EditedJul 16 2020, 12:58 PM

@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.

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?

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 added a comment.EditedJul 21 2020, 11:33 AM

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 added a comment.Jul 21 2020, 12:53 PM

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 ↗(On Diff #278585)

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

In D72904#2165103, @pcc 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 updated this revision to Diff 282802.Aug 3 2020, 11:00 PM
MaskRay marked an inline comment as done.

Rebase after D72899.

Rewrite a yaml test with assembly

MaskRay added a comment.EditedAug 3 2020, 11:09 PM

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 accepted this revision.EditedAug 4 2020, 1:23 AM

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.

This revision is now accepted and ready to land.Aug 4 2020, 1:23 AM
pcc accepted this revision.Aug 5 2020, 4:05 PM

LGTM

MaskRay edited the summary of this revision. (Show Details)Aug 5 2020, 4:09 PM
This revision was landed with ongoing or failed builds.Aug 5 2020, 4:18 PM
This revision was automatically updated to reflect the committed changes.
thakis added a subscriber: thakis.Aug 5 2020, 4:26 PM

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

(Probably just needs a triple)

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/Writer.cpp