[LLD] Reserve memory in implicitly set LMARegions

[kschwarz]

Summary

If an output section is loaded into an implicitly set LMARegion, we need to reserve space for it. Otherwise, the following output sections will use invalid region counters in their computation of offsets and assign bogus addresses.
The rules for assigning implicit LMARegions are documented here: https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html

Newer versions of ld.bfd have more complicated rules (https://sourceware.org/binutils/docs-2.30/ld/Output-Section-LMA.html#Output-Section-LMA)

[grimar]

This looks good to me. Few comments below.

ELF/LinkerScript.cpp

765

addr -> Addr

It feels that findContainingSection is a wrong name. You are finding and returning the memory region.
I would suggest findRegion or something alike.

823

According to LLD code style, you do not need adding braces for a single line. (Here and below).

test/ELF/linkerscript/Inputs/at10.s

1 ↗

(On Diff #159864)

I would reuse at8.s input. It contains the same sections.
We sometimes reusing the inputs from other tests when it is convenient, I believe it is the case here.

test/ELF/linkerscript/Inputs/at9.s

1 ↗

(On Diff #159864)

The same.

test/ELF/linkerscript/at10.test

21

I think this comment (and the comment in the test below) has the following "issue":
You are referring to the PhysAddr and LMAOffset, which are the details of the implementation
and perhaps should not be mentioned here as might change in theory.

What I would suggest is to avoid using names of variables in test cases and use just regular words
to describe the problem.

[kschwarz]

Address review comments. Thanks!

[ruiu]

I believe this code makes sense, but this is honestly a bit complicated (that's not your fault but by the nature of the linker script itself). I'm curious what program you are trying to link with this patch. Or, are you just fixing it because it's there?

[kschwarz]

I agree it makes the code more complicated. Linker scripts require a lot of corner cases to be handled specially.
This patch right now does not take into account different memory attributes, which would forbid the placement of some output sections into those regions, but would also complicate the handling even more. In this case, we currently expect the user to set a valid LMARegion explicitly.
However, if we want to be compatible with GNU linker scripts, we need to handle these cases.

These features are used heavily in embedded systems packaging several memories with different properties (flash, ram, tightly coupled memories, etc.). In order to program these systems efficiently, the user needs precise control over where the code and date is placed.
An example can be found here: https://github.com/ChibiOS/ChibiOS/blob/trunk/os/common/startup/ARMCMx/compilers/LLVM/ld/STM32F401xE.ld
My patches from last week fix bugs found and worked-around in this script. This patch fixes problems discovered also in existing GNU linker scripts.

[grimar]

It feels to me that we could try to improve the situation a bit if will split the LinkerScript::assignOffsets to move
out the code relative to assigning LMAOffset to some helper.

[kschwarz]

The search for a suitable LMARegion is now extracted into its own function. I updated this logic to the most recent bfd spec, now also taking into account different memory types.

There was also a problem in the previous version of the patch: finding the LMARegion which contains the explicitly set LMA address is not enough, we need to update the current head of the LMARegion to get valid load addresses (done in findAndAdvanceRegion).
If an explicit LMA address is used to move the location counter of a memory region backwards, this might lead to virtual/load address overlaps detected later in checkSections.

[grimar]

ELF/LinkerScript.cpp

784

I tried to simplify the conditions in this method and ended up with the following version: D50602.
What do you think?

[kschwarz]

ELF/LinkerScript.cpp

784

Your version is also fine for me, and has better reusability. I added minor comments in the separate review.

[grimar]

ELF/LinkerScript.cpp

784

Please feel free to use it whole or partially for this patch. Its intention was to show/suggest the slightly different approach.

[ikudrin]

ELF/LinkerScript.cpp

778

There are neither existing nor new test cases which require this function and the corresponding condition. You may want to add the tests or, better, extract the check into a separate patch.

[kschwarz]

I updated the patch with parts of https://reviews.llvm.org/D50602
Additionally, two new test cases now exercise the added conditions in isLMARegionCompatible (thanks @ikudrin)
We are now issuing a warning if the LMA region has incompatible flags, which can lead to overlapping addresses. Both bfd and gold do not issue the warning, but fail similarly. Having a warning seems more user friendly to me.

This patch now also fixes https://bugs.llvm.org/show_bug.cgi?id=38624

[grimar]

Looks good. Few style comments below.

ELF/LinkerScript.cpp

770

You do not need to wrap return M in curly brackets here.

789

You do not need curly brackets here.
Also, we do not use else after return.
So, it can be something like:

if (Sec->LMARegion)
  return Sec->LMARegion;

if (Sec->LMAExpr) {
  uint64_t Addr = Sec->LMAExpr().getValue();
  MemoryRegion *M = findRegion(Addr);
  if (M)
    M->CurPos = Addr;
  return M;
}

808

The same.

812

I think this empty line is excessive.

814

Excessive empty line.

816

I think:

1. LMA perhaps should be uppercase in the error message.
2. Would be nice to include memory region name to this warning.

[kschwarz]

In the last path one required line got lost, now all tests pass.
Also updated style and wording of warning. Thanks!

[kschwarz]

ELF/LinkerScript.cpp

816

After a second thought, I'm not sure if this warning really makes sense.
Initialized data will be copied to RAM at runtime, but has to be loaded to read-only memory. In that case, the flags will obviously not be compatible, and the warning will be confusing.

[grimar]

ELF/LinkerScript.cpp

816

I think its ok to remove it. Patch already do much, we can add/polish the additional warnings/error messages in followups.

819

Seems it is needed for vma.test only. What do you think about splitting this change to separate followup patch (with vma.test)?
I would not introduce moveTo in this patch because this seems to be more or less isolated/independent change and
since we already have setDot, I am not sure it is good to introduce one more method that moves the Dot. I would probably
try to inline it, but first of all, I think it can be discussed/reviewed separately.

[kschwarz]

Removed the warning and moveTo function, which will go into its own patch.

[grimar]

LGTM, thanks! Please wait for Rui's opinion too.

[kschwarz]

@ruiu, are you okay with this change?

[ruiu]

ELF/LinkerScript.cpp

723–724

Remove extraneous parentheses. I.e.

return M && (!M->Flags || (M->Flags & Sec->Flags)) &&
        (M->NegFlags & Sec->Flags) == 0;

But perhaps it is better to deconstruct it a bit by using more lines:

if (!M)
  return false;
if (M->Flags && !(M->Flags & Sec->Flags)
  return false;
return (M->NegFlags & Sec->Flags) == 0;

Now, my question is, can really M be a nullptr?

782

Add a full stop at end of a sentence.

785

Add a blank line before a comment.

786

Ditto.

794

Blank line.

800

Ditto.

830

If you add a comment to else, add {} and write the comment inside {}.

[kschwarz]

ELF/LinkerScript.cpp

723–724

Sure, I can simplify it a bit.

Currently this function can be called with M being a nullptr (from findLMARegion). We can add a check for nullptr there and eliminate the check in areFlagsCompatible, which seems more reasonable.

[kschwarz]

Addressed review comments.

[kschwarz]

@ruiu, does this look good now?

[kschwarz]

ping @ruiu

[ruiu]

ELF/LinkerScript.cpp

722

What is the meaning of the expressions in the function? I'd write a brief function comment.

774

Needs a brief function comment.

[MaskRay]

Ping @kschwarz

ELF/LinkerScript.h

class LinkerScript final {
   std::vector<size_t> getPhdrIndices(OutputSection *Sec);
 
   MemoryRegion *findMemoryRegion(OutputSection *Sec);
 
   void switchTo(OutputSection *Sec);
   uint64_t advance(uint64_t Size, unsigned Align);
   void output(InputSection *Sec);
 
+  MemoryRegion *findLMARegion(OutputSection *Sec);
   void assignOffsets(OutputSection *Sec);
 
   // Ctx captures the local AddressState and makes it accessible
   // deliberately. This is needed as there are some cases where we cannot just
   // thread the current state through to a lambda function created by the
   // script parser.
   // This should remain a plain pointer as its lifetime is smaller than
   // LinkerScript.

ELF/LinkerScript.cpp

 void LinkerScript::switchTo(OutputSection *Sec) {
   Ctx->OutSec = Sec;
 
   uint64_t Before = advance(0, 1);
   Ctx->OutSec->Addr = advance(0, Ctx->OutSec->Alignment);
   expandMemoryRegions(Ctx->OutSec->Addr - Before);
 }
 
+static bool areFlagsCompatible(MemoryRegion *M, OutputSection *Sec) {
+  if (M->Flags && !(M->Flags & Sec->Flags))
+    return false;
+  return (M->NegFlags & Sec->Flags) == 0;
+}
+
 // 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) {
   // If a memory region name was specified in the output section command,
   // then try to find that region first.
   if (!Sec->MemoryRegionName.empty()) {
     if (MemoryRegion *M = MemoryRegions.lookup(Sec->MemoryRegionName))
       return M;
     error("memory region '" + Sec->MemoryRegionName + "' not declared");
     return nullptr;
   }
 
   // If at least one memory region is defined, all sections must
   // belong to some memory region. Otherwise, we don't need to do
   // anything for memory regions.
   if (MemoryRegions.empty())
     return nullptr;
 
   // See if a region can be found by matching section flags.
-  for (auto &Pair : MemoryRegions) {
-    MemoryRegion *M = Pair.second;
-    if ((M->Flags & Sec->Flags) && (M->NegFlags & Sec->Flags) == 0)
-      return M;
-  }
+  for (auto &Pair : MemoryRegions)
+    if (areFlagsCompatible(Pair.second, Sec))
+      return Pair.second;
 
   // Otherwise, no suitable region was found.
   if (Sec->Flags & SHF_ALLOC)
     error("no memory region specified for section '" + Sec->Name + "'");
   return nullptr;
 }
 
 static OutputSection *findFirstSection(PhdrEntry *Load) {
   for (OutputSection *Sec : OutputSections)
     if (Sec->PtLoad == Load)
       return Sec;
   return nullptr;
 }
 
+static MemoryRegion *findRegion(uint64_t Addr) {
+  for (auto &Pair : Script->MemoryRegions) {
+    MemoryRegion *M = Pair.second;
+    if (M->Origin <= Addr && Addr < M->Origin + M->Length)
+      return M;
+  }
+  return nullptr;
+}
+
+static bool isLMARegionCompatible(MemoryRegion *M, OutputSection *Sec) {
+  return (Sec->Type & SHT_NOBITS) || areFlagsCompatible(M, Sec);
+}
+
+MemoryRegion *LinkerScript::findLMARegion(OutputSection *Sec) {
+  // We implement a similar heuristic as the bfd linker
+  // (https://sourceware.org/binutils/docs-2.30/ld/Output-Section-LMA.html).
+
+  // If this section has an LMARegion set, overwrite the previous LMARegion.
+  if (Sec->LMARegion)
+    return Sec->LMARegion;
+
+  // If this section has an LMAExpr set, find the memory region the address
+  // falls into.
+  if (Sec->LMAExpr) {
+    uint64_t Addr = Sec->LMAExpr().getValue();
+    MemoryRegion *M = findRegion(Addr);
+    if (M)
+      M->CurPos = Addr;
+    return M;
+  }
+
+  // If a memory region can be found that is compatible with the current
+  // section, and this region contains at least one section, then the LMA is
+  // set so the difference between the VMA and LMA is the same as the
+  // difference between the VMA and LMA of the last section in the located
+  // region.
+  // This is only possible if the section has a memory region set and it is
+  // identical to the memory region of the previous section.
+  if (Sec->MemRegion && Ctx->LMARegion && Sec->MemRegion == Ctx->MemRegion &&
+      isLMARegionCompatible(Ctx->LMARegion, Sec))
+    return Ctx->LMARegion;
+  return nullptr;
+}
+
 // This function assigns offsets to input sections and an output section
 // for a single sections command (e.g. ".text { *(.text); }").
 void LinkerScript::assignOffsets(OutputSection *Sec) {
+  // First set LMA and Memory regions before modifying any location counter
+  Ctx->LMARegion = findLMARegion(Sec);
+  Ctx->MemRegion = Sec->MemRegion;
+
   if (!(Sec->Flags & SHF_ALLOC))
     Dot = 0;
   else if (Sec->AddrExpr)
     setDot(Sec->AddrExpr, Sec->Location, false);
 
-  Ctx->MemRegion = Sec->MemRegion;
-  Ctx->LMARegion = Sec->LMARegion;
   if (Ctx->MemRegion)
     Dot = Ctx->MemRegion->CurPos;
 
   switchTo(Sec);
 
-  if (Sec->LMAExpr)
-    Ctx->LMAOffset = Sec->LMAExpr().getValue() - Dot;
-
-  if (MemoryRegion *MR = Sec->LMARegion)
+  // Compute the LMAOffset.
+  // If we have an LMARegion set, use it.
+  if (MemoryRegion *MR = Ctx->LMARegion) {
     Ctx->LMAOffset = MR->CurPos - Dot;
+  } else if (Sec->LMAExpr) {
+    // If the LMAExpr is set but we could not find an LMARegion previously,
+    // this means we do not have any MEMORY commands and need to evaluate
+    // the expression again.
+    Ctx->LMAOffset = Sec->LMAExpr().getValue() - Dot;
+  } else {
+    Ctx->LMAOffset = 0;
+  }
 
-  // If neither AT nor AT> is specified for an allocatable section, the linker
-  // will set the LMA such that the difference between VMA and LMA for the
-  // section is the same as the preceding output section in the same region
-  // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
-  // This, however, should only be done by the first "non-header" section
-  // in the segment.
+  // Only the first "non-header" section of each program header should set the
+  // LMAOffset.
   if (PhdrEntry *L = Ctx->OutSec->PtLoad)
     if (Sec == findFirstSection(L))
       L->LMAOffset = Ctx->LMAOffset;
 
   // We can call this method multiple times during the creation of
   // thunks and want to start over calculation each time.
   Sec->Size = 0;
 

test/ELF/linkerscript/at10.test

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/at8.s -o %t.o
+# RUN: ld.lld %t.o --script %s -o %t
+# RUN: llvm-readelf -sections -program-headers %t | FileCheck %s
+
+MEMORY {
+  FLASH  : ORIGIN = 0x08000000, LENGTH = 0x100
+  RAM    : ORIGIN = 0x20000000, LENGTH = 0x200
+}
+
+SECTIONS {
+ .text : { *(.text) } > FLASH
+ .sec1 : AT(0x08000000) { *(.sec1) } > RAM
+ .sec2 : { *(.sec2) } > RAM
+ .sec3 : { *(.sec3) } > FLASH
+}
+
+# Make sure we increase the implicit LMA region of .sec2.
+# Otherwise, .sec3 will receive a huge load address because of
+# unsigned underflow in the calculation of the offset to its
+# virtual address.
+
+# CHECK: Name              Type            Address          Off
+# CHECK: .text             PROGBITS        0000000008000000 001000
+# CHECK: .sec1             PROGBITS        0000000020000000 001000
+# CHECK: .sec2             PROGBITS        0000000020000008 001008
+# CHECK: .sec3             PROGBITS        0000000008000010 001010
+
+# CHECK: Program Headers:
+# CHECK:      Type  Offset   VirtAddr           PhysAddr
+# CHECK-NEXT: LOAD  0x001000 0x0000000020000000 0x0000000008000000
+# CHECK-NEXT: LOAD  0x001010 0x0000000008000010 0x0000000008000010
+# CHECK-NOT: LOAD

test/ELF/linkerscript/at11.test

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/at8.s -o %t.o
+# RUN: not ld.lld %t.o --script %s -o %t 2>&1 | FileCheck %s
+
+MEMORY {
+  FLASH(rx)  : ORIGIN = 0x08000000, LENGTH = 0x100
+  RAM(rwx)   : ORIGIN = 0x20000000, LENGTH = 0x200
+}
+
+SECTIONS {
+ .text : { *(.text) } > FLASH
+ .sec1 : AT(0x08000000) { *(.sec1) } > RAM
+ .sec2 : { *(.sec2) } > RAM
+ .sec3 : { *(.sec3) } > FLASH
+}
+
+# .sec1's load address is explicitly set to the start of FLASH.
+# Since .sec1 and .sec2 share the same memory region, they are put
+# into the same PT_LOAD header. However, because .sec2's section flags are
+# not compatible with FLASH, it is not implicitly put into that LMA
+# region, leading to a load address overlap with .sec3.
+
+# CHECK: error: section .sec2 load address range overlaps with .sec3

test/ELF/linkerscript/at12.test

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/at8.s -o %t.o
+# RUN: not ld.lld %t.o --script %s -o %t 2>&1 | FileCheck %s
+
+MEMORY {
+  FLASH(rx)  : ORIGIN = 0x08000000, LENGTH = 0x100
+  RAM(rwx)   : ORIGIN = 0x20000000, LENGTH = 0x200
+}
+
+SECTIONS {
+ .text : { *(.text) } > FLASH
+ .sec1 : { *(.sec1) } > RAM AT> FLASH
+ .sec2 : { *(.sec2) } > RAM
+ .sec3 : { *(.sec3) } > FLASH
+}
+
+# .sec1's LMA region is explicitly set to FLASH.
+# Since .sec1 and .sec2 share the same memory region, they are put
+# into the same PT_LOAD header. However, because .sec2's section flags are
+# not compatible with FLASH, it is not implicitly put into that LMA
+# region, leading to a load address overlap with .sec3.
+
+# CHECK: error: section .sec2 load address range overlaps with .sec3

test/ELF/linkerscript/at9.test

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/at8.s -o %t.o
+# RUN: ld.lld %t.o --script %s -o %t
+# RUN: llvm-readelf -sections -program-headers %t | FileCheck %s
+
+MEMORY {
+  FLASH  : ORIGIN = 0x08000000, LENGTH = 0x100
+  RAM    : ORIGIN = 0x20000000, LENGTH = 0x200
+}
+
+SECTIONS {
+ .text : { *(.text) } > FLASH
+ .sec1 : { *(.sec1) } > RAM AT > FLASH
+ .sec2 : { *(.sec2) } > RAM
+ .sec3 : { *(.sec3) } > FLASH
+}
+
+# Make sure we increase the implicit LMA region of .sec2.
+# Otherwise, .sec3 will receive a huge load address because of
+# unsigned underflow in the calculation of the offset to its
+# virtual address.
+
+# CHECK: Name              Type            Address          Off
+# CHECK: .text             PROGBITS        0000000008000000 001000
+# CHECK: .sec1             PROGBITS        0000000020000000 001000
+# CHECK: .sec2             PROGBITS        0000000020000008 001008
+# CHECK: .sec3             PROGBITS        0000000008000010 001010
+
+# CHECK: Program Headers:
+# CHECK:      Type  Offset   VirtAddr           PhysAddr
+# CHECK-NEXT: LOAD  0x001000 0x0000000020000000 0x0000000008000000
+# CHECK-NEXT: LOAD  0x001010 0x0000000008000010 0x0000000008000010
+# CHECK-NOT: LOAD