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

[hvenev]

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.

[jhenderson]

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

[peter.smith]

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]

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.

[jhenderson]

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]

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

[hvenev]

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.

[jhenderson]

In D111871#3107393, @hvenev wrote:

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]

In D111871#3108247, @jhenderson wrote:

In D111871#3107393, @hvenev wrote:

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?

[jhenderson]

In D111871#3109228, @hvenev wrote:

In D111871#3108247, @jhenderson wrote:

In D111871#3107393, @hvenev wrote:

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.

lld/ELF/Writer.cpp

 // ranges and the virtual address ranges don't overlap
 template <class ELFT> void Writer<ELFT>::checkSections() {
   // First, check that section's VAs fit in available address space for target.
-  for (OutputSection *os : outputSections)
-    if ((os->addr + os->size < os->addr) ||
-        (!ELFT::Is64Bits && os->addr + os->size > UINT32_MAX))
+  for (OutputSection *os : outputSections) {
+    // For empty sections, we want the base VA to fit.
+    uint64_t lastByte = os->addr + (os->size ? os->size - 1 : 0);
+    if ((lastByte < os->addr) || (!ELFT::Is64Bits && lastByte > UINT32_MAX))
       errorOrWarn("section " + os->name + " at 0x" + utohexstr(os->addr) +
                   " of size 0x" + utohexstr(os->size) +
                   " exceeds available address space");
+  }
 
   // Check for overlapping file offsets. In this case we need to skip any
   // section marked as SHT_NOBITS. These sections don't actually occupy space in

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

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=i386-unknown-linux %s -o %t.o
+
+# RUN: echo "SECTIONS { . = 0xfffffff0;" > %t.script
+# RUN: echo "           .bar : { *(.bar*) }" >> %t.script
+# RUN: echo "           /DISCARD/ : { *(.text) } }" >> %t.script
+# RUN: ld.lld -o /dev/null --script %t.script %t.o 2>&1
+
+## .bar section has data in [0xfffffff0, 0xfffffff0 + 0x10) ==
+## [0xfffffff0, 0x100000000). The address of the last byte of the section is
+## 0xffffffff, so this is not considered overflow.
+
+.section .bar,"ax",@progbits
+.zero 0x10

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

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+
+# RUN: echo "SECTIONS { . = 0xfffffffffffffff0;" > %t.script
+# RUN: echo "           .bar : { *(.bar*) } }" >> %t.script
+# RUN: ld.lld -o /dev/null --script %t.script %t.o 2>&1
+
+## .bar section has data in [0xfffffffffffffff0, 0xfffffffffffffff0 + 0x10) ==
+## [0xfffffffffffffff0, 0x10000000000000000). The address of the last byte of
+## the section is 0xffffffffffffffff, so this is not considered overflow.
+
+.section .bar,"ax",@progbits
+.zero 0x10