Page MenuHomePhabricator

[ELF] Write output sections in PT_LOAD segment order
Needs ReviewPublic

Authored by pattop on Jan 21 2021, 7:04 PM.

Details

Reviewers
MaskRay
psmith
Summary

Previously if sections in a link script were not in program segment
order lld often failed with file range overlap errors.

The new out-of-order-sections test case previously failed with:

ld.lld: error: section .foo file range overlaps with .bar

.foo range is [0x2000, 0x2000]
.bar range is [0x2000, 0x2000]

Diff Detail

Event Timeline

pattop created this revision.Jan 21 2021, 7:04 PM
pattop requested review of this revision.Jan 21 2021, 7:04 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 21 2021, 7:04 PM
MaskRay added a comment.EditedJan 21 2021, 9:16 PM

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.

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.

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

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 added a subscriber: grimar.Jan 22 2021, 4:59 PM

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.

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.

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.

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
2652

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.

2654

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.

2658

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.

2673

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

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 added inline comments.Jan 31 2021, 8:22 PM
lld/ELF/Writer.cpp
2654

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.

2658

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.

2673

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 this revision to Diff 320391.Jan 31 2021, 8:40 PM

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

pattop marked 10 inline comments as not done.Jan 31 2021, 8:42 PM

Not sure why my comments were automatically marked as done.

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 added a comment.Feb 1 2021, 2:19 PM

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.

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 added inline comments.Feb 4 2021, 9:35 PM
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 updated this revision to Diff 321657.Feb 4 2021, 9:42 PM

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.

pattop marked an inline comment as not done.Feb 4 2021, 9:43 PM

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.

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 added a subscriber: jrtc27.Mon, Feb 8, 12:02 PM
jrtc27 added inline comments.
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 added inline comments.Mon, Feb 8, 3:22 PM
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 updated this revision to Diff 322280.Mon, Feb 8, 9:22 PM

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.