[ELF] Improve compatibility with ld.bfd linker scripts

[pattop]

Summary

Previously sections in a linker script had to be sorted by segment and address
otherwise lld would fail with perplexing errors such as "section .foo file
range overlaps with .bar" or "unable to place section .foo at file offset
[...]; check your linker script for overflows".

This patch improves compatibility with ld.bfd by supporting two new cases:

1. Sections with decreasing addresses in the same program header, e.g:

.text 0x2000 : {*(.text*)} :ph1
.bar 0x1000 : {*(.bar*)} :ph1

2. Interleaving sections across program headers, e.g:

.text 0x2000 : {*(.text*)} :ph1
.foo 0x0 : {*(.foo*)} :ph2
.bar 0x1000 : {*(.bar*)} :ph1

While it is possible in both cases to modify the linker script we would need to
correctly detect these cases and emit more helpful diagnostics for them.
However, as lld claims it is a "drop-in replacement for the GNU linkers that
accepts the same command line arguments and linker scripts as GNU" it makes
sense to improve compatibility instead.

Supporting these cases requires sorting sections within a segment by address
then placing the output in load segment order.

A new out-of-order-sections test is also introduced.

[MaskRay]

For out-of-order-sections.s, you could just swap foo and bar. The few updated tests seem to have undesired sh_offset changes.

GNU ld's placement rules are much more complex. We implement sufficient parts to be compatible with a wide range of linker scripts and may require updating the linker scripts in some cases.

[pattop]

In D95199#2514547, @MaskRay wrote:

For out-of-order-sections.s, you could just swap foo and bar.

Yes, this is true. I crafted the test case specifically to highlight the problem.

The few updated tests seem to have undesired sh_offset changes.

I examined these and to the best of my (limited) understanding the resultant offset changes looked ok, however, I may have missed something important.

GNU ld's placement rules are much more complex. We implement sufficient parts to be compatible with a wide range of linker scripts and may require updating the linker scripts in some cases.

My desire to have this case work comes from a real world embedded project. In conjunction with https://reviews.llvm.org/D95198 it makes lld far more usable in this context.

[pattop]

If the direction of the patch is acceptable I can provide a detailed analysis of each required testcase adjustment.

[pattop]

In fact, if https://reviews.llvm.org/D95198 is acceptable it is a separate justification for this change. In order to place program headers somewhere other than the lowest VMA in the program image something like this needs to happen.

[MaskRay]

In D95199#2514581, @pattop wrote:

In fact, if https://reviews.llvm.org/D95198 is acceptable it is a separate justification for this change. In order to place program headers somewhere other than the lowest VMA in the program image something like this needs to happen.

Both this patch and D95198 look a bit arbitrary to me. Please see my question in D95198. Also adding @grimar who has improved linker scripts a lot.

[pattop]

In D95199#2517071, @MaskRay wrote:

In D95199#2514581, @pattop wrote:

In fact, if https://reviews.llvm.org/D95198 is acceptable it is a separate justification for this change. In order to place program headers somewhere other than the lowest VMA in the program image something like this needs to happen.

Both this patch and D95198 look a bit arbitrary to me. Please see my question in D95198. Also adding @grimar who has improved linker scripts a lot.

I don't agree that these are arbitrary issues.

I proposed this and D95198 as I encountered these issues in the real world while porting projects which have been working with GNU ld for many years.

Sure, this one can be worked around by reordering the link script, but it's certainly confusing for a user coming from GNU ld. Especially as the error message (pertaining to file range) does not really point to the underlying problem.

It was very surprising to me that LLD requires sections in a link script to be in a special order.

[grimar]

This looks to me it solves a specific corner case, but I really don't feel I have enough knowledges about embedded world/scripts to say whether it is a good or bad thing to support it.
It seems matches to what GNU ld/gold do. I'll add Peter who I guess might have an opinion about this.

[psmith]

Apologies for the delay in responding. As I understand it, this would only cause a problem with PHDRS? Our implicit creation of program headers should already be in OutputSection order.

Personally I'd be in favour of making our PHDRS support more closely match ld.bfd. Both Arm and RiscV are making more of an effort to push LLVM rather than GCC in the embedded space (https://github.com/ARM-software/LLVM-embedded-toolchain-for-Arm) and LLD is the linker of choice. Avoiding migration problems for embedded developers is helpful. Yes it is true that people can rewrite their linker scripts in most cases, however it normally needs an expert to debug the limitation from an overlap error message.

For this particular change, I've made a few comments and I would like an explanation for some of the file-offset differences and the addition of foo implicit-program-header.test? I can't immediately see from the script why there would be any change in output section order.

lld/ELF/Writer.cpp

2659

I'd prefer a comment that explains why we are doing this. As it stands it is just a 1 line summary of the code.

2661

Is there a chance that we've not written a SHF_ALLOC output section. I think this would only be possible if the section were not assigned to a program header, which I don't think is possible if our PHDRS or implicit program header implementation is correct. Is there any way we can check for this.

2665

Can we guarantee that all sections with SHF_ALLOC are assigned to a loadable program header? From a brief scan of the code I think so.

Can we guarantee that all sections assigned to SHF_ALLOC have SHF_ALLOC? I'm not sure we can guarantee it if PHDRS command is used, but I think we can if PHDRS is not used (linker creates them implicitly), would be good to check that this is the case with an assertion.

2680

Similarly we may be able to assert that (sec->flags & SHF_ALLOC) == 0 here.

[pattop]

Thanks for taking the time to review.

This causes problems any time the sections are not in segment order.

I agree that it would be good if lld's behaviours can more closely match BFD ld. https://lld.llvm.org/ even says that lld is supposed to be a drop in replacement for GNU linkers.

I've commented on most of the test case changes and will update the patch to address your review comments.

lld/test/ELF/linkerscript/at8.test

23 ↗

(On Diff #318394)

This change in file offest happens because .text is not part of a LOAD segment as it's empty. Is checking the offset of an empty section sensible? (this happens a few more times below).

Maybe, as a separate change, we should set the offset for empty sections to 0?

The rest of the offsets are not affected as .text is empty.

lld/test/ELF/linkerscript/empty-sections-expressions.test

12 ↗

(On Diff #318394)

The same reasoning as at8.test applies.

lld/test/ELF/linkerscript/implicit-program-header.test

10

This new result aligns closely with what BFD ld 2.35.1 produces which is:

Section to Segment mapping:
 Segment Sections...
  00     .text .dynsym .dynstr .hash .dynamic 
  01     .foo 
  02     .foo

The SECTIONS command says that .bar should go into the ph_exec and ph_note segments. I think the expectation is that .foo should be the same as it does not specify a new segment.

Previously .foo was also included in the ph_write segment which I think is incorrect.

The segments lld produces for this test are a bit weird compared to BFD ld both before and after this change.

BFD ld:

Type           Offset             VirtAddr           PhysAddr           FileSiz            MemSiz              Flags  Align
LOAD           0x0000000000001008 0x0000000000000008 0x0000000000000008 0x00000000000000e8 0x00000000000000e8   W     0x1000
LOAD           0x0000000000001000 0x0000000000000000 0x0000000000000000 0x0000000000000008 0x0000000000000008    E    0x1000
NOTE           0x0000000000001000 0x0000000000000000 0x0000000000000000 0x0000000000000008 0x0000000000000008  R E    0x1

lld without this patch:

Type           Offset             VirtAddr           PhysAddr           FileSiz            MemSiz              Flags  Align
LOAD           0x0000000000001000 0x0000000000000000 0x0000000000000000 0x00000000000000a0 0x00000000000000a0   W     0x1000
LOAD           0x0000000000001029 0x0000000000000029 0x0000000000000029 0x0000000000000008 0x0000000000000008    E    0x1000
NOTE           0x0000000000001029 0x0000000000000029 0x0000000000000029 0x0000000000000008 0x0000000000000008  R E    0x1

lld with this patch:

Type           Offset             VirtAddr           PhysAddr           FileSiz            MemSiz              Flags  Align
LOAD           0x0000000000001000 0x0000000000000000 0x0000000000000000 0x00000000000000a0 0x00000000000000a0   W     0x1000
LOAD           0x0000000000002029 0x0000000000000029 0x0000000000000029 0x0000000000000008 0x0000000000000008    E    0x1000
NOTE           0x0000000000002029 0x0000000000000029 0x0000000000000029 0x0000000000000008 0x0000000000000008  R E    0x1

With this change lld no longer produces overlapping load segments which I think is a step in the right direction.

lld/test/ELF/linkerscript/nobits-offset.s

18 ↗

(On Diff #318394)

The file offset of .text is not important as it is empty.
The file offset of .sec1 is not important as it has no file data.

lld/test/ELF/linkerscript/tbss.s

38 ↗

(On Diff #318394)

As the comment states, what matters here is that a thread local bss section doesn't take up any address space. This effectively means that the location counter must not be advanced when processing such a section.

I don't think this change is correct. What's important is that the address of the section foo is the same as the address of the next section bar. That validates the assertion that no address space has been used.

I'm not sure why the file offset was considered in this test. It doesn't seem relevant?

The reason the file offsets change at all is because bar is now placed in the file first followed by .text and foo.

I will update this.

lld/test/ELF/partition-synthetic-sections.s

195 ↗

(On Diff #318394)

This looks harmless to me as the output is shifted by exactly one page and can be explained by a slight reordering of sections in the output. Everything else is identical.

I haven't done a detailed analysis of why this moves. If there are concerns I can investigate further.

lld/test/ELF/tls-offset.s

58 ↗

(On Diff #318394)

I don't think the file offsets here are important. .tbss is a NOBITS section and has no file data associated with it.

Somewhat concerningly the TLS segment changes size from 4 bytes to 8 byes (not covered by this test) which should probably be investigated.

[pattop]

lld/ELF/Writer.cpp

2661

I think tbss is a special case section which is allocated but not assigned to a load segment. That makes adding a check more difficult.

2665

Can we guarantee that all sections with SHF_ALLOC are assigned to a loadable program header? From a brief scan of the code I think so.

I don't think this is the case for tbss.

Can we guarantee that all sections assigned to SHF_ALLOC have SHF_ALLOC? I'm not sure we can guarantee it if PHDRS command is used, but I think we can if PHDRS is not used (linker creates them implicitly), would be good to check that this is the case with an assertion.

Did you mean all sections assigned to a loadable segment have SHF_ALLOC? If so, yes, I think this can be asserted.

2680

Unfortunately we can't assert this because:

1. tbss is a special case which is allocated but not part of a load segment
2. sometimes we don't generate load segments (just a file header, no program headers) in which case all output is written from this loop

[pattop]

Updated comments.
Add assertion that all sections in a load segment must be allocated.
Fix tbss.s test case.

[pattop]

Not sure why my comments were automatically marked as done.

[peter.smith]

Thanks for the update, I'll try and take a look later in the week. Will have to have a think about the zero size section case. If we haven't assigned it to a PT_LOAD and it defines no symbol it may be possible to not put it in the object file.

[pattop]

In D95199#2534394, @peter.smith wrote:

Thanks for the update, I'll try and take a look later in the week. Will have to have a think about the zero size section case. If we haven't assigned it to a PT_LOAD and it defines no symbol it may be possible to not put it in the object file.

No problem. Hopefully my comments on the test cases make some sense. Unfortunately some of your code comments moved around a bit when I updated the patch.

Doing something with zero size sections could be a nice cleanup, but it looks like it would cause some churn in the tests. Either way, I think it's separate to this issue.

[peter.smith]

I've had a look at a couple of the tests (not looked at the others) there look to be some ordering problems with some special cases like partition sections and .tbss. To find these I checked the order of writing sections with the new and old. As mentioned in the comment I don't know much about the partition mechanism, as such I'd recommend making sure that there were no explainable differences in those tests. Will try and find some more time to look at the others later in the week/weekend.

lld/test/ELF/partition-synthetic-sections.s

195 ↗

(On Diff #318394)

Looking at the ordering of sections the special part1 and .part.end sections are not written in the same order. In particular .part.end comes after part1. I'm not familiar with the partition feature, but it is used by chrome, which is very aggressive at reverting any patch that breaks it. I think it will be worth understanding how partitions intersect with pt_load

lld/test/ELF/tls-offset.s

58 ↗

(On Diff #318394)

There is an ordering difference. See needsPTLoad the .tbss is deliberately not assigned to a program header so it is getting written in the non SHF_ALLOC portion. This may not be a problem in practice but it does result in a discontinuity in file offsets that is at the least confusing. Personally I'd prefer that we write the .tbss in its address order.

[pattop]

lld/test/ELF/partition-synthetic-sections.s

195 ↗

(On Diff #318394)

You're right, the ordering is different, but the extracted partitions still pass all of the tests which is why I thought this probably wasn't significant.

I'm struggling to understand what this 'od' test is actually validating. I read through D62350 which is where the test originated but didn't find any explanation.

Unfortunately I'm not in a position where I can try a chrome build to see if anything breaks.

lld/test/ELF/tls-offset.s

58 ↗

(On Diff #318394)

Explainable file offsets is one reason why I think setting a file offset on sections without file data isn't helpful. IMHO it would be easier to expalin that the file offset on a section with no file data is always 0.

Writing .tbss in address order should be doable, I'll take a look.

[pattop]

Maintain section address order as much as possible when assigning file offsets.

This resolves most file offset adjustments in tests previously required due to
reordering of empty sections.

The logic in assignFileOffsets could possibly be cleaner but I can't quite see
how right now.

[peter.smith]

Thanks for the updates. My day job has been very busy of late so I've not got a lot of spare time to look. As it stands I'm still a bit nervous about the test changes, it is also worth mentioing that I'd want at least one of grimar and MaskRay to agree on any changes in this area as they were both initially hesitant.

I did have a thought on what might make this (and your other patch) easier to upstream. Instead of changing the code directly keep the existing code below:

// Layout SHF_ALLOC sections before non-SHF_ALLOC sections. A non-SHF_ALLOC
// will not occupy file offsets contained by a PT_LOAD.

Given that the problem with ordering only exists with PHDR commands, then we can do something like (pseudo code):

if linker script has program headers {
    reorder Output Sections covered by PT_LOAD
}
...
// Layout SHF_ALLOC sections before non-SHF_ALLOC sections. A non-SHF_ALLOC
// will not occupy file offsets contained by a PT_LOAD.

While it may be a bit more code, it is isolated to when PT_LOAD is used, which should limit the impact on the existing tests to the tests using PHDR. From reading the partition documentation (see below) this feature is incompatible with linker scripts and PHDR anyway. This should make it easier to review, although I can't speak for MaskRay and grimar here.

For the partitions bit:
Sadly the LLD tests don't always capture all of the properties that need to hold. I've had a scan through the documentation and some of the reviews. The code does mention partiion end markers which tools like objdump use to extract partitions. I

References for the partition
Initial RFC https://lists.llvm.org/pipermail/llvm-dev/2019-February/130583.html
LLD reviews: D60242 D60353 D62350 D62349

The author of partitions is pcc , he may be able to comment on the changes, although is also frequently busy.

[MaskRay]

The change to partition-synthetic-sections.s is not ideal. Originally the sections have non-decreasing offsets. With the change, .part.end (NOBITS) is the first to be assigned an offset 0x3150. In the next iteration, sh_offset(part1) is 0x4000 (was: 0x3000), wasting one page.

The change to implicit-program-header.test is not ideal, either. You can use the existing assembly, or add a .bar and change PT_NOTE to PT_LOAD. In both cases GNU ld places .foo before .text. The current behavior is similar. With this patch, .foo will be assigned an offset from the next page.

In the presence of PHDRS, I think the new behavior is pretty much desired. It remains uncertain for me whether making it the behavior in the absence of PHDRS is the right choice. It gives my a feeling to address specific corner case while regressing normal case behaviors and greatly increasing complexity.

[jrtc27]

lld/test/ELF/linkerscript/out-of-order-sections.s

4

Without commenting on the changes to Writer.cpp, this is rather ugly and should probably be in a separate file. Certainly the formatting here is wrong with respect to closing curly braces.

[pattop]

lld/test/ELF/linkerscript/out-of-order-sections.s

4

Can you please clarify what should be in a separate file?

As far as the formatting is concerned I was looking at phdrs.s when I first wrote this. Looking again, phdrs.s is quite inconsistent in its formatting and in hindsight is probably a poor example to follow.

openbsd-randomize.s and phdrs-flags.s also place the closing curly brace on the same line of a multi-line SECTIONS.

I'll fix this next time I update the patch.

[pattop]

Thanks for the feedback!

peter.smith's comment suggesting reordering sections made me rethink my approach to the problem.

I don't think we can reorder outputSections as many parts of the code depend on this. What I have done instead is add a segment to section mapping in the PhdrEntry struct. I think this is a good approach as it allows us to sort the sections in a segment by address without affecting anything else. Doing this greatly simplifies the logic in assignFileOffsets().

As a further cleanup the firstSec and lastSec members of PhdrEntry can probably become simple inline functions returning the first and last entry in the sections vector. I didn't want to do this unless the direction is OK to simplify review.

I have limited this to only affect the output when a PHDRS command is in use as per peter.smith's suggestion, but that won't cover all cases. A link script containing just a SECTIONS command can place sections at arbitrary addresses which also needs this new logic to work properly. Unfortunately, doing so with the current logic brings back some previously discussed undesirable side effects.

As MaskRay said the new output of implicit-program-header.test isn't great. As far as I can tell the reason this happens is beause we place .dynsym .hash and .dynstr before .foo rather than after .text. I'm not sure how to resolve this.

[pattop]

Just a quick ping on this to see if there's any more feedback.

[MaskRay]

The description does not convey the motivation clearly. Can you avoid referring to D95198 but make the description of this patch self-contained?
I am inclined to think D95198 is too ad-hoc but this patch may be promising.
(I am still on the fence, so hope a clear description can convince me that doing so is justified.)

However, the description should mention why we need to do the sorting. More specifically, I want the two questions to be answered:

.text 0x2000 : {*(.text*)} :ph1
.bar 0x1000 : {*(.bar*)} :ph1

Shall we support sections with decreasing addresses within the same program header?
(Note that this is different from decreasing addresses with different program headers, e.g. linkorder-script.s)

.text 0x2000 : {*(.text*)} :ph1
.foo 0 : {*(.foo*)} :ph2
.bar 0x1000 : {*(.bar*)} :ph1

Shall we support interleaving ph1 and ph2?

In both cases, why can't the linker script be modified to reorder sections instead?

lld/test/ELF/linkerscript/out-of-order-sections.s

3

Use .o for object files and prefer split-file to echo + output redirection.

See newer tests like symbol-assign-type.s

16

Prefer llvm-readelf -l to llvm-readobj -l. See newer tests.

[MaskRay]

lld/ELF/Writer.cpp

1087

stable_sort

[MaskRay]

lld/ELF/Writer.cpp

2227

// Sort segment sections by address. For one segment, we layout sections in the order of addresses.

2662

The comment is not on-topic. What we do here is to make interleaving segments work. See my question in the main comment.

link script -> linker script

[pattop]

Address MaskRay feedback.

[pattop]

I have updated the description (summary?) to hopefully more clearly convey the intent.

[pattop]

Minor fix - used CHECK instead of CHECK-NEXT in during rework.

[pattop]

I have cleaned up D95198 too. IMHO the change is now much clearer.

[pattop]

Another ping to see if there's anything else I can do to get this across the line.