[ELF] Simplify sh_addr computation and warn if sh_addr is not a multiple of sh_addralign

[MaskRay]

Summary

See docs/ELF/linker_script.rst for the new computation for sh_addr and sh_addralign. ALIGN(section_align) now means: "increase alignment to section_align"

The "start of section .foo changes from 0x11 to 0x20" warning no longer
makes sense. Change it to warn if sh_addr%sh_addralign!=0.

To decrease the alignment from the default max_input_align,
use .output ALIGN(8) : {} instead of .output : ALIGN(8) {}
See linkerscript/section-address-align.test as an example.

When both an output section address and ALIGN are set (can be seen as an
"undefined behavior" https://sourceware.org/ml/binutils/2020-03/msg00115.html),
lld may align more than GNU ld, but it makes a linker script working
with GNU ld hard to break with lld.

This patch can be considered as restoring part of the behavior before D74736.

[psmith]

In theory I don't mind that we deviate from GNU ld where it makes sense, however given that our Linker Script documentation is the GNU ld docs, and that has considerable gaps, I'd be much more comfortable in approving if we had more user facing documentation where we document the differences. I know that this has come up before but we didn't take any action. Is it worth starting now, even if we only document this one difference and add to it over time? This could either be in our existing man page and/or in the official LLVM docs.

[MaskRay]

In D75724#1909965, @psmith wrote:

In theory I don't mind that we deviate from GNU ld where it makes sense, however given that our Linker Script documentation is the GNU ld docs, and that has considerable gaps, I'd be much more comfortable in approving if we had more user facing documentation where we document the differences. I know that this has come up before but we didn't take any action. Is it worth starting now, even if we only document this one difference and add to it over time? This could either be in our existing man page and/or in the official LLVM docs.

Yeah we need a documentation.

I made these alignment changes because of https://reviews.llvm.org/D74286#1872329 .

I thought about the alternative to simply let ALIGN override max_input_align. After rereading https://bugs.llvm.org/show_bug.cgi?id=45023#c9 , I give up that idea because .output ALIGN(8) : {} can override max_input_align.

Now, our discrepancy with GNU ld is:

• When both an output section address and ALIGN are set, we use max(ALIGN,max_input_align) while GNU ld uses ALIGN. This is an "undefined behavior".
• In GNU ld>=2.35, an output section address can decrease sh_addralign. This is to conform to the ELF spec but my feeling is that this creates a non-conforming/strange section intentionally. I think we should keep sh_addralign to reflect the max of input sections. This also makes problems more obvious.

These are corner cases and undocumented on It is documented in https://sourceware.org/binutils/docs/ld/ . No correct linker script is affected.

[MaskRay]

Incorporate feedback at https://bugs.llvm.org/show_bug.cgi?id=45023#c9

[psmith]

If the ld.bfd developers consider both [address] and [ALIGN(section_align)] as undefined behaviour then I'm happy that we can simplify and the above change does implement that. Would like to hear what some of the other reviewers think as well.

For the documentation may I suggest we add something like this to ld.lld.1

Linker Script implementation notes and policy.

LLD implements a large subset of the GNU ld linker script notation. The LLD
implementation policy is to implement linker script features as they are
documented in the ld manual https://sourceware.org/binutils/docs/ld/Scripts.html
We consider it a bug if the lld implementation does not agree with the manual
and it is not mentioned in the exceptions below.

The ld manual is not a complete specification, and is not sufficient to build
an implementation. In particular some features are only defined by the
implementation and have changed over time.

The lld implementation policy for properties of linker scripts that are not
defined by the documentation is to follow the GNU ld implementation wherever
possible. We reserve the right to make different implementation choices where
it is appropriate for LLD. Intentional deviations will be documented here:

Linker Script deviations

Status: This is under construction and is not complete.

Output Section ALIGN

When an OutputSection S has both [address] and [ALIGN(section_align)]
LLD will set the alignment of S to the maximum of [ALIGN(section_align)] and
the maximum alignment of the input sections in S. GNU ld will always use
[ALIGN(section_align)].

When an OutputSection S has [address] LLD will warn if this not 0 modulo
OutputSection alignment. The ELF file will set sh_addr to [address] and
sh_addralign to OutputSection alignment even if this would produce a
non-compliant ELF file. GNU ld from Binutils 2.35 onwards will reduce
sh_addralign so that sh_addr = 0 (modulo sh_addralign).

We could add to this as we make more decisions, I've kept to just those made in this review here. We could also add a known limitations for the areas where we haven't implemented corner cases.

[MaskRay]

In D75724#1911650, @psmith wrote:

If the ld.bfd developers consider both [address] and [ALIGN(section_align)] as undefined behaviour then I'm happy that we can simplify and the above change does implement that. Would like to hear what some of the other reviewers think as well.

For the documentation may I suggest we add something like this to ld.lld.1

Linker Script implementation notes and policy.

LLD implements a large subset of the GNU ld linker script notation. The LLD
implementation policy is to implement linker script features as they are
documented in the ld manual https://sourceware.org/binutils/docs/ld/Scripts.html
We consider it a bug if the lld implementation does not agree with the manual
and it is not mentioned in the exceptions below.

The ld manual is not a complete specification, and is not sufficient to build
an implementation. In particular some features are only defined by the
implementation and have changed over time.

The lld implementation policy for properties of linker scripts that are not
defined by the documentation is to follow the GNU ld implementation wherever
possible. We reserve the right to make different implementation choices where
it is appropriate for LLD. Intentional deviations will be documented here:

Linker Script deviations

Status: This is under construction and is not complete.

Output Section ALIGN

When an OutputSection S has both [address] and [ALIGN(section_align)]
LLD will set the alignment of S to the maximum of [ALIGN(section_align)] and
the maximum alignment of the input sections in S. GNU ld will always use
[ALIGN(section_align)].

When an OutputSection S has [address] LLD will warn if this not 0 modulo
OutputSection alignment. The ELF file will set sh_addr to [address] and
sh_addralign to OutputSection alignment even if this would produce a
non-compliant ELF file. GNU ld from Binutils 2.35 onwards will reduce
sh_addralign so that sh_addr = 0 (modulo sh_addralign).

We could add to this as we make more decisions, I've kept to just those made in this review here. We could also add a known limitations for the areas where we haven't implemented corner cases.

Thanks for the documentation! I think the paragraphs may be too long for docs/ld.lld.1. May I suggest you create a patch to add Linker Script implementation notes and policy to docs/ELF/linker_script.rst? I can add Output Section ALIGN in this patch. I don't want to take credit for the important policy part.

[MaskRay]

Add docs/ELF/linker_script.rst

[psmith]

Thanks for the documentation! I think the paragraphs may be too long for docs/ld.lld.1. May I suggest you create a patch to add Linker Script implementation notes and policy to docs/ELF/linker_script.rst? I can add Output Section ALIGN in this patch. I don't want to take credit for the important policy part.

Sure I'll do that tomorrow morning, apologies I didn't get to it today.

[psmith]

Created D75921 to create the initial contents of linker_script.rst
While trying to build it I ran into https://bugs.llvm.org/show_bug.cgi?id=41789 as I had too new a version of Sphinx. The solution in the PR worked for the LLD docs, although the overall LLVM docs build failed for a different (deprecation of something in latest Sphinx) in an unrelated file. If this happens to you I suggest setting SPHINX_EXECUTABLE=/path/to/pre_2.0_sphinx_build in your cmake command.

[mcgrathr]

I wholeheartedly endorse documenting the policy on linker script semantics. I think the described deviation from GNU semantics for cases where explicit output section alignment doesn't jibe with input section alignment is generally fine. That is, I think this corner case is best avoided and I'm not too concerned with exactly how it goes when it happens. The warning for the case of an explicit address that is misaligned wrt input section sh_addralign is the most important thing for avoiding accidents. For the explicit alignment being less than than input requirements, the lld behavior of using the maximum of the two seems sensible to me (essentially the explicit alignment in the linker script is just another of the requirements like all the inputs' sh_addralign values and you align to the maximum of the whole set, which is perfectly intuitive). If anything, I think the GNU linkers should warn about violating input sh_addralign requirements if they're going to have that behavior.

In my case, the change in behavior for the explicit alignment < input alignment case revealed a bug in my code producing the input sections and showed me that I really wanted to reorganize my linker script so it was testing the input section alignment with asserts rather than controlling it explicitly in the output section. So if anything that suggests warning for any instance of an explicit alignment not matching up with input requirements. But it seems likely that the most common use of explicit alignments is exactly when setting the minimum alignment of the output section is the intent and that being increased by input sh_addralign requirements is normal and expected, and not a case like mine.

[psmith]

Now that we have some documentation in place to record the decision, and I've not seen any objections to the simplification, I'm happy to approve the change.

lld/ELF/LinkerScript.h

public:
   std::vector<llvm::StringRef> referencedSymbols;
 
   // Used to implement INSERT [AFTER|BEFORE]. Contains output sections that need
   // to be reordered.
   std::vector<InsertCommand> insertCommands;
 
   // Sections that will be warned/errored by --orphan-handling.
   std::vector<const InputSectionBase *> orphanSections;
-
-  // Sections whose addresses are not equal to their addrExpr values.
-  std::vector<std::pair<const OutputSection *, uint64_t>>
-      changedSectionAddresses;
 };
 
 extern LinkerScript *script;
 
 } // end namespace elf
 } // end namespace lld
 
 #endif // LLD_ELF_LINKER_SCRIPT_H

lld/ELF/LinkerScript.cpp

void LinkerScript::output(InputSection *s) {
   // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
   expandOutputSection(pos - before);
 }
 
 void LinkerScript::switchTo(OutputSection *sec) {
   ctx->outSec = sec;
 
   uint64_t pos = advance(0, 1);
-  if (sec->addrExpr && !sec->alignExpr) {
+  if (sec->addrExpr && script->hasSectionsCommand) {
     // The alignment is ignored.
     ctx->outSec->addr = pos;
   } else {
-    // If ALIGN is specified, advance sh_addr according to ALIGN and ignore the
-    // maximum of input section alignments.
-    //
-    // When no SECTIONS command is given, sec->alignExpr is set to the maximum
-    // of input section alignments.
-    uint32_t align =
-        sec->alignExpr ? sec->alignExpr().getValue() : ctx->outSec->alignment;
-    ctx->outSec->addr = advance(0, align);
+    // ctx->outSec->alignment is the max of ALIGN and the maximum of input
+    // section alignments.
+    ctx->outSec->addr = advance(0, ctx->outSec->alignment);
     expandMemoryRegions(ctx->outSec->addr - pos);
   }
 }
 
 // This function searches for a memory region to place the given output
 // section in. If found, a pointer to the appropriate memory region is
 // returned. Otherwise, a nullptr is returned.
 MemoryRegion *LinkerScript::findMemoryRegion(OutputSection *sec) {
void LinkerScript::assignOffsets(OutputSection *sec) {
   // If the address of the section has been moved forward by an explicit
   // expression so that it now starts past the current curPos of the enclosing
   // region, we need to expand the current region to account for the space
   // between the previous section, if any, and the start of this section.
   if (ctx->memRegion && ctx->memRegion->curPos < dot)
     expandMemoryRegion(ctx->memRegion, dot - ctx->memRegion->curPos,
                        ctx->memRegion->name, sec->name);
 
-  uint64_t oldDot = dot;
   switchTo(sec);
-  if (sec->addrExpr && oldDot != dot)
-    changedSectionAddresses.push_back({sec, oldDot});
 
   ctx->lmaOffset = 0;
 
   if (sec->lmaExpr)
     ctx->lmaOffset = sec->lmaExpr().getValue() - dot;
   if (MemoryRegion *mr = sec->lmaRegion)
     ctx->lmaOffset = alignTo(mr->curPos, sec->alignment) - dot;
 
if (script->hasSectionsCommand) {
     Out::elfHeader->addr = dot;
     Out::programHeaders->addr = dot + Out::elfHeader->size;
     dot += getHeaderSize();
   }
 
   auto deleter = std::make_unique<AddressState>();
   ctx = deleter.get();
   errorOnMissingSection = true;
-  changedSectionAddresses.clear();
   switchTo(aether);
 
   SymbolAssignmentMap oldValues = getSymbolAssignmentValues(sectionCommands);
   for (BaseCommand *base : sectionCommands) {
     if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
       cmd->addr = dot;
       assignSymbol(cmd, false);
       cmd->size = dot - cmd->addr;

lld/ELF/Writer.cpp

if (!changed) {
       if (++assignPasses == 5) {
         errorOrWarn("assignment to symbol " + toString(*changedSym) +
                     " does not converge");
         break;
       }
     }
   }
 
-  // If a SECTIONS command is given, addrExpr, if set, is the specified output
-  // section address. Warn if the computed value is different from the actual
-  // address.
-  if (!script->hasSectionsCommand)
-    return;
-  for (auto changed : script->changedSectionAddresses) {
-    const OutputSection *os = changed.first;
-    warn("start of section " + os->name + " changes from 0x" +
-         utohexstr(changed.second) + " to 0x" + utohexstr(os->addr));
-  }
+  // If addrExpr is set, the address may not be a multiple of the alignment.
+  // Warn because this is error-prone.
+  for (BaseCommand *cmd : script->sectionCommands)
+    if (auto *os = dyn_cast<OutputSection>(cmd))
+      if (os->addr % os->alignment != 0)
+        warn("address (0x" + Twine::utohexstr(os->addr) + ") of section " +
+             os->name + " is not a multiple of alignment (" +
+             Twine(os->alignment) + ")");
 }
 
 static void finalizeSynthetic(SyntheticSection *sec) {
   if (sec && sec->isNeeded() && sec->getParent())
     sec->finalizeContents();
 }
 
 // In order to allow users to manipulate linker-synthesized sections,

lld/docs/ELF/linker_script.rst

 an implementation. In particular some features are only defined by the
 implementation and have changed over time.
 
 The lld implementation policy for properties of linker scripts that are not
 defined by the documentation is to follow the GNU ld implementation wherever
 possible. We reserve the right to make different implementation choices where
 it is appropriate for LLD. Intentional deviations will be documented in this
 file.
+
+Output section description
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+The description of an output section looks like:
+
+::
+
+  section [address] [(type)] : [AT(lma)] [ALIGN(section_align)] [SUBALIGN](subsection_align)] {
+    output-section-command
+    ...
+  } [>region] [AT>lma_region] [:phdr ...] [=fillexp] [,]
+
+Output section address
+----------------------
+
+When an *OutputSection* *S* has ``address``, LLD will set sh_addr to ``address``.
+
+The ELF specification says:
+
+> The value of sh_addr must be congruent to 0, modulo the value of sh_addralign.
+
+The presence of ``address`` can cause the condition unsatisfied. LLD will warn.
+GNU ld from Binutils 2.35 onwards will reduce sh_addralign so that
+sh_addr=0 (modulo sh_addralign).
+
+Output section alignment
+------------------------
+
+sh_addralign of an *OutputSection* *S* is the maximum of
+``ALIGN(section_align)`` and the maximum alignment of the input sections in
+*S*.
+
+When an *OutputSection* *S* has both ``address`` and ``ALIGN(section_align)``,
+GNU ld will set sh_addralign to ``ALIGN(section_align)``.

lld/test/ELF/linkerscript/lma-align.test

 # REQUIRES: x86
 # RUN: echo '.globl _start; _start: ret; .data.rel.ro; .balign 16; .byte 0; \
 # RUN:   .data; .balign 32; .byte 0; .bss; .byte 0' | \
 # RUN:   llvm-mc -filetype=obj -triple=x86_64 - -o %t.o
 # RUN: ld.lld -T %s %t.o -o %t 2>&1 | FileCheck --check-prefix=WARN %s --implicit-check-not=warning:
 # RUN: llvm-readelf -S -l %t | FileCheck %s
 
-# WARN: warning: start of section .data changes from 0x11001 to 0x11010
-# WARN: warning: start of section .bss changes from 0x11021 to 0x11040
+# WARN: warning: address (0x11001) of section .data is not a multiple of alignment (32)
+# WARN: warning: address (0x11021) of section .bss is not a multiple of alignment (64)
 
 # CHECK:      Name         Type     Address          Off    Size   ES Flg Lk Inf Al
 # CHECK-NEXT:              NULL     0000000000000000 000000 000000 00      0   0  0
 # CHECK-NEXT: .text        PROGBITS 0000000000001000 001000 000001 00  AX  0   0  4
 # CHECK-NEXT: .data.rel.ro PROGBITS 0000000000011000 002000 000001 00  WA  0   0 16
-# CHECK-NEXT: .data        PROGBITS 0000000000011010 002010 000011 00  WA  0   0 32
-# CHECK-NEXT: .bss         NOBITS   0000000000011040 002040 000001 00  WA  0   0 64
+# CHECK-NEXT: .data        PROGBITS 0000000000011001 002001 000020 00  WA  0   0 32
+# CHECK-NEXT: .bss         NOBITS   0000000000011021 002021 000001 00  WA  0   0 64
 
 # CHECK:      Type  Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
 # CHECK-NEXT: LOAD  0x001000 0x0000000000001000 0x0000000000001000 0x000001 0x000001 R E 0x1000
 # CHECK-NEXT: LOAD  0x002000 0x0000000000011000 0x0000000000001010 0x000001 0x000001 RW  0x1000
-# CHECK-NEXT: LOAD  0x002010 0x0000000000011010 0x0000000000001020 0x000011 0x000011 RW  0x1000
-# CHECK-NEXT: LOAD  0x002040 0x0000000000011040 0x0000000000011040 0x000000 0x000001 RW  0x1000
+# CHECK-NEXT: LOAD  0x002001 0x0000000000011001 0x0000000000001020 0x000020 0x000020 RW  0x1000
+# CHECK-NEXT: LOAD  0x002021 0x0000000000011021 0x0000000000011021 0x000000 0x000001 RW  0x1000
 
 MEMORY {
   ROM : ORIGIN = 0x1000, LENGTH = 1K
   RAM : ORIGIN = 0x11000, LENGTH = 1K
 }
 SECTIONS {
   .text 0x1000 : { *(.text*) } >ROM
   ## Input section alignment decides output section alignment.
   .data.rel.ro 0x11000 : { *(.data.rel.ro) } >RAM AT>ROM
   ## ALIGN decides output section alignment.
   .data . : ALIGN(16) { *(.data*) } >RAM AT>ROM
   ## Start a new PT_LOAD because the LMA region is different from the previous one.
   .bss . : ALIGN(64) { *(.bss*) } >RAM
 }

lld/test/ELF/linkerscript/section-address-align.test

+# REQUIRES: x86
+## Test ALIGN when specifying the output section address.
+
+# RUN: echo '.globl _start; _start: ret; \
+# RUN:   .data.rel.ro; .balign 8; .byte 0; \
+# RUN:   .data; .byte 0; \
+# RUN:   .bss; .balign 32; .byte 0' | \
+# RUN:   llvm-mc -filetype=obj -triple=x86_64 - -o %t.o
+# RUN: ld.lld -T %s %t.o -o %t 2>&1 | FileCheck --check-prefix=WARN %s --implicit-check-not=warning:
+# RUN: llvm-readelf -S %t | FileCheck %s
+
+# WARN: warning: address (0x10004) of section .data.rel.ro is not a multiple of alignment (8)
+# WARN: warning: address (0x20008) of section .bss is not a multiple of alignment (32)
+
+# CHECK:      Name         Type     Address          Off    Size   ES Flg Lk Inf Al
+# CHECK-NEXT:              NULL     0000000000000000 000000 000000 00      0   0  0
+# CHECK-NEXT: .text        PROGBITS 0000000000010000 001000 000001 00  AX  0   0  4
+# CHECK-NEXT: .data.rel.ro PROGBITS 0000000000010004 001004 000005 00  WA  0   0  8
+# CHECK-NEXT: .data        PROGBITS 0000000000020000 002000 000001 00  WA  0   0  1
+# CHECK-NEXT: .bss         NOBITS   0000000000020008 002001 000019 00  WA  0   0 32
+
+SECTIONS {
+  .text 0x10000 : { *(.text) }
+  ## The output .data.rel.ro starts at 0x10004.
+  ## The input .data.rel.ro starts at 0x10008 and ends at 0x10009.
+  ## sh_size(.data.rel.ro) = 0x10009-0x10004 = 0x5.
+  .data.rel.ro ALIGN(4) : { *(.data.rel.ro) }
+
+  .data 0x20000 : { *(.data) }
+  ## The output .bss starts at 0x20008.
+  ## The input .bss starts at 0x20020 and ends at 0x20021.
+  ## sh_size(.bss) = 0x20021-0x20008 = 0x19.
+  .bss ALIGN(8) : { *(.bss) }
+}

lld/test/ELF/linkerscript/section-align2.test

 # REQUIRES: aarch64
 ## Test ALIGN and its interaction with explicit output section addresses.
 
 # RUN: echo '.globl _start; _start: ret; .data.rel.ro; .balign 8; .byte 0; .data; .byte 0; \
-# RUN:   .section .data2,"aw"; .balign 8; .byte 0; .bss; .balign 32; .byte 0' | \
+# RUN:   .section .data2,"aw"; .balign 8; .byte 0; \
+# RUN:   .section .data3,"aw"; .balign 32; .byte 0; \
+# RUN:   .bss; .balign 32; .byte 0' | \
 # RUN:   llvm-mc -filetype=obj -triple=aarch64 - -o %t.o
 # RUN: ld.lld -T %s %t.o -o %t 2>&1 | FileCheck --check-prefix=WARN %s --implicit-check-not=warning:
 # RUN: llvm-readelf -S %t | FileCheck %s
 
 ## Check we don't warn in the absence of SECTIONS.
 # RUN: ld.lld --fatal-warnings -Ttext=0x10000 %t.o -o /dev/null
 
-# WARN: warning: start of section .data.rel.ro changes from 0x10004 to 0x10010
-# WARN: warning: start of section .bss changes from 0x20009 to 0x20010
+# WARN: warning: address (0x10004) of section .data.rel.ro is not a multiple of alignment (16)
+# WARN: warning: address (0x20001) of section .data2 is not a multiple of alignment (8)
+# WARN: warning: address (0x20021) of section .bss is not a multiple of alignment (32)
 
 # CHECK:      Name         Type     Address          Off    Size   ES Flg Lk Inf Al
 # CHECK-NEXT:              NULL     0000000000000000 000000 000000 00      0   0  0
 # CHECK-NEXT: .text        PROGBITS 0000000000010000 010000 000004 00  AX  0   0  4
-# CHECK-NEXT: .data.rel.ro PROGBITS 0000000000010010 010010 000001 00  WA  0   0 16
+# CHECK-NEXT: .data.rel.ro PROGBITS 0000000000010004 010004 000005 00  WA  0   0 16
 # CHECK-NEXT: .data        PROGBITS 0000000000020000 020000 000001 00  WA  0   0  1
 # CHECK-NEXT: .data2       PROGBITS 0000000000020001 020001 000008 00  WA  0   0  8
-# CHECK-NEXT: .bss         NOBITS   0000000000020010 020009 000011 00  WA  0   0 32
+# CHECK-NEXT: .data3       PROGBITS 0000000000020020 020020 000001 00  WA  0   0 32
+# CHECK-NEXT: .bss         NOBITS   0000000000020021 020021 000020 00  WA  0   0 32
 
 SECTIONS {
   .text 0x10000 : { *(.text) }
   ## sh_addr is aligned to 16.
   .data.rel.ro . : ALIGN(16) { *(.data.rel.ro) }
 
   .data 0x20000 : { *(.data) }
   ## The output section address is set without ALIGN. sh_addr is set to Dot, ignoring alignment.
   ## sh_addralign is the maximum of input section alignments, 8.
   .data2 . : { *(.data2) }
+  ## sh_addr is aligned to 32.
+  ## The input section has a larger alignment and is thus preceded by a gap.
+  .data3 : ALIGN(16) { *(.data3) }
   ## sh_addr is aligned to 16.
   ## The input section has a larger alignment and is thus preceded by a gap.
   .bss . : ALIGN(16) { *(.bss) }
 }