LLD and layout convergence

Subprojects LLD
1

Consider the following linker script:

SECTIONS {
.text ADDR(.data)+0x1000 : { *(.text) }
.data : { *(.data) }
}

This script is artificial, but it exemplifies some real-world scenarios.

GNU ld fails to link this with script.t:2: non constant or forward reference address expression for section .text. lld produces a binary without any diagnostics, where .data is placed immediately after .text:

1 .text 00000022 0000000000002022 TEXT
2 .data 00000000 0000000000002044 DATA

I would like to understand why lld produces such output. An iterative layout algorithm would not converge if the linker naively applied all the rules and check after each iteration that the layout has settled. It seems the initial address is about double the offset used in the script. For example, changing the .text section to ADDR(.data)+0x4000 will move it to 0x8022. This makes it look like lld does two iterations.

In general, what should be the user’s expectation regarding this kind of input? Obviously, the address of .text is not equal to the address of .data plus 0x1000 in the final lld layout. The section address is effectively ignored.

On the other hand, GNU ld behavior seem too restrictive as an iterative algorithm may still produce a valid output even when there are references to not yet laid out sections, for example (again, artificial):

SECTIONS {
.text (ADDR(.data)-ADDR(.data)+0x1000) : { *(.text) }
.data : { *(.data) }
}

Thanks!

2

This is a bit of a grey area as linker scripts are underspecified. I think the respective linker’s outputs are more down to particular implementation details. From memory in LLD we needed to be able to support some GNU linker scripts that had a series of symbol assignments. In pseudo code
a2 = a1
a3 = a2
a4 = a3
The way LLD’s expression evaluation worked out meant that multiple passes were needed to propagate the values all the way to the final symbol. There wasn’t any thought of supporting forward references at the time.

My personal sympathies are with GNU ld here. While it is possible for some forward references to converge, I’m not sure if there is a good way of describing the cases that could work, and would work in a predictable way, as well as giving good error messages for the cases that wouldn’t.

1 Like
3

Naively, one might think that LLD’s address assignment loop directly checks for the stabilization of symbol values should mean that it’s straightforward to support any linker script structure that does eventually converge within the maximum allowable passes. It’s very interesting that it doesn’t actually seem to be true. LLD isn’t reporting a failure to converge; instead LLD converges to something arguably inappropriate.

Would it be possible to upload a LLD reproducer tarball (ld.lld --reproduce=file.tar) that exhibits this behavior? I’d definitely like to get a debugger attached and see what’s happening in more detail.

4

lld uses a fixed-point iteration algorithm to compute section and symbol addresses.
assignAddresses (which is called a few times within an iteration) does not check whether an output section’s address has changed. I am thinking of extending the scriptSymOrder mechanism ([ELF] Respect orders of symbol assignments and DEFINED by MaskRay · Pull Request #65866 · llvm/llvm-project · GitHub) to check whether the ADDR referenced section has been defined and report an error for a forward reference.

Since we allow symbols to retain addresses of the previous iteration. You can still cause some non-convergence cases if you use symbols as output section addresses.

5

Some time ago, we opened a bug (LLD does not report forward reference errors in linker script · Issue #80276 · llvm/llvm-project · GitHub), which was closed [it could have been written clearer though].

It might be ideal to define the rules that the end user can comprehend, instead of referencing internal algorithms in each linker. I have tried to understand under which conditions GNU reports this error, but I could not.

6

The test case is really simple. It’s possible to debug it but I more wonder what the desired behavior should be.

$ cat 1.c

int a = 0;
int b = 10;
int foo() { return a + b; }

$ cat script.t

SECTIONS {
.text (ADDR(.data)+0x1000) : { *(.text) }
.data : { *(.data) }
}

$ arm-none-eabi-gcc -c 1.c
$ arm-none-eabi-ld -T script.t 1.o

script.t:2: non constant or forward reference address expression for section .text

$ ld.lld -T script.t 1.o

ld.lld: warning: cannot find entry symbol _start; not setting start address

$ llvm-objdump -h a.out

a.out: file format elf32-littlearm

Sections:
Idx Name Size VMA Type
0 00000000 00000000
1 .text 00000034 00002034 TEXT
2 .data 00000004 00002068 DATA
3 .bss 00000004 0000206c BSS
4 .comment 00000045 00000000
5 .ARM.attributes 00000030 00000000
6 .symtab 00000090 00000000
7 .shstrtab 00000045 00000000
8 .strtab 00000019 00000000

7

Discussions of the semantics of a programming language often involve the operation of an abstract machine; there isn’t an intrinsic problem with that. Linker scripts are so underspecified though that the “abstract machine” is often the actual implementation of the linker.

The issue is that the linker script language is expressive enough to allow self-reference, a bit like “liar sentences” in a logic. You can say the following: .text ADDR(.text)+1 : { *(.text) }. That is, ".text is to be assigned to a different address than the one that it is assigned to. A bit like “this sentence is false”.

There are generally two ways to deal with this: syntactic restrictions and semantic restrictions.

Syntactically, you can restrict the legal syntax via a system of rules in such a way to make impossible assignment requests illegal to express. This can be difficult, and the rules might end up complicated or very conservative, depending on the tradoffs chosen. But, it’s the usual choice, since the syntactic rule violations can be detected very efficiently.

Semantically, you could initialize all the symbol values and section addresses to zero, then evaluate the linker script with that assignment. Then repeat until addresses stop changing or some fixed number of iterations. A failure to terminate means that the specification was unsatisfiable. (Incidentally, a logical version of this approach is known due to Saul Kripke, and it can assign truth values to self-referential sentences using an infinite hierarchy of languages.)

A successful termination doesn’t necessarily mean that the expression was “grounded”, however. Consider .text ADDR(.text) : { *(.text) }. Any address assignment for .text whatsoever “works”. One could fix such ungrounded cases to zero (which is closer to what LLD currently does), or one could detect such ungroundedness by running fixed-point iteration twice with different starting points. If that produced different results, then the differing expressions were ungrounded.

Personally, I’m partial to the semantic approach. But this is largely due to my annoyance at encountering errors about things like “forward references” in cases that are trivially innocuous to a human. Software people easily get used to such UX warts, but they’re still a bit warty. Then again, mysterious “address assignment unsatisfiable” or “failed to terminate” errors may be worse than “you broke this rule you don’t need to understand the reason for.”

Hard-coding zero as a starting point seems sensible rather than trying to detect ungroundedness. I wouldn’t usually be concerned if the linker picked a different assignment than the one I had in mind, so long as all of the constraints specified are satisfied.

8

I added some examples at #80276 that GNU ld’s non constant or forward reference address expression for section is incomplete: the error can be easily circumvented with a symbol assignment. I propose [ELF] Detect convergence of output section addresses by MaskRay · Pull Request #93888 · llvm/llvm-project · GitHub to detect convergence of output section addresses properly. The diagnostic message might not be as good as “forward reference address expression”, but I believe adding a custom message for “forward reference address” has little marginal benefit.

I agree with @smithp35 and @mysterymath’s analysis. Linker scripts are so complex and so underspecified. While coming up a set of rules to forbid problematic constructions would prevent unsound scripts, it could reject many reasonable use cases.

set -e
cat > a.s <<e
.text; .space 4
.data; .byte 0
e
cat > x.lds <<e
SECTIONS {
  .text ADDR(.data)+0x1000 : { *(.text) }
  .data : { *(.data) }
}
e
cat > x1.lds <<e
SECTIONS {
  .text foo : { *(.text) }
  .data : { *(.data) }
  foo = ADDR(.data)+0x1000;
}
e
cat > y.lds <<e
SECTIONS {
  .text : { foo = ADDR(.data); *(.text) }
  .data : { *(.data) }
}
e
gcc -c a.s
not ld.bfd -T x.lds a.o  # non constant or forward reference address expression for section .text
ld.bfd -T x1.lds a.o # essentially identical to x.lds, but accepted
ld.bfd -T y.lds a.o  # accepted