Page MenuHomePhabricator

[ELF] Let sections reach the end of the address space
Needs RevisionPublic

Authored by hvenev on Oct 15 2021, 2:54 AM.

Details

Summary

Currently LLD doesn't let the virtual addresses of sections reach the
end of the address space. However, this is permitted by the GNU linker.

Fix this by checking the VA of the last byte of the section rather than
the one past the end. For empty sections, we require that the base VA
fits, i.e. they behave like sections with a size of 1 byte.

Diff Detail

Event Timeline

hvenev created this revision.Oct 15 2021, 2:54 AM
hvenev requested review of this revision.Oct 15 2021, 2:54 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 15 2021, 2:54 AM

@MaskRay, @hvenev had a bit of confusion caused by the lld/CODE_OWNERS.txt file which still has Rui as the LLD ELF/COFF code owner. I believe you've taken on that role? If that's correct, could you update the file, please.

I was a bit confused initially by the title and description, had to read the code to work out what the change was for. IIUC the address range of the section is the half open interval [os->addr, os->addr + size) so LLD has an off by one error when checking that the section fits at the end of the address space calculation? Please forgive me if I've got the notation the wrong way around. My memory says [ ] = closed interval, including endpoints, () = open interval, not including endpoints, [ ) half open-interval including start but not end value.

Can you update the description to something similar to what you'd put in the commit message? "This is permitted by the GNU linker." is going to look a bit a bit sparse in the log.

lld/ELF/Writer.cpp
2786

I'f I've got this right then on a 32-bit target we can write a 0 sized OutputSection with a base address higher than UINT32_MAX and pass the check.

Perhaps something like:
uint64_t last_byte = (os->size) ? os->addr + (os->size - 1) : os->addr;

lld/test/ELF/linkerscript/i386-sections-until-end-of-va.s
9

Expressed in bytes written I think it is [0xfffffff0, 0xfffffff0 + 0x10) to show that 0x100000000 (using 64-bit numbers) is not part of the interval.

10

Expressed in bytes written I think this is [0xfffffff0, 0) == [0xfffffff0, 0xffffffff]

lld/test/ELF/linkerscript/sections-until-end-of-va.s
9

Similar comment to the above test case.

hvenev updated this revision to Diff 380169.Oct 16 2021, 4:25 AM
hvenev edited the summary of this revision. (Show Details)

This error looks interesting...

It appears that there is an empty .text section that in the 32-bit case the linker places at address 1<<32. This probably means that there is overflow in when assigning section addresses. For now I'm discarding the .text sections in the 32-bit test case.

GNU ld silently truncates all addresses to 32/64 bits. Sections are allowed to overflow the address space in all cases. However, I don't think this is what we want.

It is more of an issue in the 64-bit case because there we don't detect the overflow. I think the following happens:

  1. LinkerScript::addOrphanSections creates an output .text section command at the end of the SECTIONS block
  2. LinkerScript::assignOffsets is called on the .text output section with dot set to 0`.

I will send a follow-up patch that emits an error when an overflowed . is used as a section base address.

hvenev updated this revision to Diff 380176.Oct 16 2021, 5:44 AM
jhenderson added a comment.EditedOct 18 2021, 12:36 AM

Please upload diffs with full context (create them with something like -U999999), as this makes things easier to review, usually (in this case, I think it's clear-cut enough in the context, so don't fret about it, just useful in the more general case).

I think we need a test case for an empty section at the end of the address space? Similarly, I think we might need test cases that show the error is emitted when the size is just overflowed (i.e. by 1) - I haven't checked what the current state of the test coverage here is.

MaskRay requested changes to this revision.Nov 3 2021, 1:32 PM
This revision now requires changes to proceed.Nov 3 2021, 1:32 PM

(Request changes as there are unaddressed comments and make this outside of reviewers' queues)

hvenev added a comment.Nov 3 2021, 2:24 PM

There already are test cases for overflowing by 1 byte. These two tests are more or less copies of those, except that we exactly reach the end.

Regarding the empty section thing, that's a problem with setting the base address rather than the size. It is something that the linker script interpreter does not handle well, especially in the 64-bit case.

There already are test cases for overflowing by 1 byte. These two tests are more or less copies of those, except that we exactly reach the end.

Regarding the empty section thing, that's a problem with setting the base address rather than the size. It is something that the linker script interpreter does not handle well, especially in the 64-bit case.

I'm not sure that it is? You can have an empty section immediately following a non-empty section after all, so you'd just need a non-empty section that ends at the end of the address space, followed by an empty section.

hvenev added a comment.Nov 4 2021, 9:31 AM

There already are test cases for overflowing by 1 byte. These two tests are more or less copies of those, except that we exactly reach the end.

Regarding the empty section thing, that's a problem with setting the base address rather than the size. It is something that the linker script interpreter does not handle well, especially in the 64-bit case.

I'm not sure that it is? You can have an empty section immediately following a non-empty section after all, so you'd just need a non-empty section that ends at the end of the address space, followed by an empty section.

The current linker script logic does no overflow checking. Instead, it always truncates addresses to 64 bits. This means that e.g. a section that starts at the end of the 64-bit address space is actually moved to address 0. I think this is a bug.

An empty section at the end of the address space has an invalid base address no matter the section size. Ideally such addresses should not be produced by the linker script interpreter, so in such a test case we should not even reach Writer<ELFT>::checkSections.

If I add tests with empty sections at the end of the address space, should I have the 64-bit case expect an error and add XFAIL?

There already are test cases for overflowing by 1 byte. These two tests are more or less copies of those, except that we exactly reach the end.

Regarding the empty section thing, that's a problem with setting the base address rather than the size. It is something that the linker script interpreter does not handle well, especially in the 64-bit case.

I'm not sure that it is? You can have an empty section immediately following a non-empty section after all, so you'd just need a non-empty section that ends at the end of the address space, followed by an empty section.

The current linker script logic does no overflow checking. Instead, it always truncates addresses to 64 bits. This means that e.g. a section that starts at the end of the 64-bit address space is actually moved to address 0. I think this is a bug.

An empty section at the end of the address space has an invalid base address no matter the section size. Ideally such addresses should not be produced by the linker script interpreter, so in such a test case we should not even reach Writer<ELFT>::checkSections.

If I add tests with empty sections at the end of the address space, should I have the 64-bit case expect an error and add XFAIL?

I think we may be misunderstanding each other. By "base address" I thought you meant the initial linker script address, but you mean the section start address.

I realised I was being silly, as there's no way to represent a section with an address at the end of the address space (what would its sh_addr be?). What I actually originally meant was an empty section with address == max(Elf_Addr), i.e. 0xffffffff on 32-bit and 0xffffffffffffffff on 64-bit, because of the new os->size check in the Writer.cpp changes (line 2787 in the current version of the diff). An empty section is needed to exercise that change (and show it's not accidentally treated as a section of size max(size). Please add that test case.