[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

761

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.

783

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

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

The same.

test/ELF/linkerscript/at10.test

20

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

780

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

780

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

[grimar]

ELF/LinkerScript.cpp

780

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

774

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

766

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

774

I think this empty line is excessive.

778

I think:

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

785

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;
}

804

The same.

810

Excessive empty line.

[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

778

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

777

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.

778

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

[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?

778

Add a full stop at end of a sentence.

781

Add a blank line before a comment.

782

Ditto.

790

Blank line.

796

Ditto.

807

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.

770

Needs a brief function comment.

[MaskRay]

Ping @kschwarz

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);
 }
 
 // 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;

 
 static OutputSection *findFirstSection(PhdrEntry *Load) {
   for (OutputSection *Sec : OutputSections)
     if (Sec->PtLoad == Load)
       return Sec;
   return nullptr;
 }
 
+static MemoryRegion *findContainingSection(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;
+}
+
+
 // 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) {
   if (!(Sec->Flags & SHF_ALLOC))
     Dot = 0;
   else if (Sec->AddrExpr)
     setDot(Sec->AddrExpr, Sec->Location, false);
 
   Ctx->MemRegion = Sec->MemRegion;
+
+  // If this section has an LMARegion set, overwrite the previous
+  // LMARegion in the context
+  if (Sec->LMARegion) {
     Ctx->LMARegion = Sec->LMARegion;
+  }
   if (Ctx->MemRegion)
     Dot = Ctx->MemRegion->CurPos;
 
   switchTo(Sec);
 
-  if (Sec->LMAExpr)
-    Ctx->LMAOffset = Sec->LMAExpr().getValue() - Dot;
+  // If the LMARegion is identical to the MemRegion, the offset should
+  // be 0 (might happen for implicitly set LMARegions)
+  if (Sec->MemRegion && Sec->MemRegion == Ctx->LMARegion) {
+    Ctx->LMAOffset = 0;
+  }
+
+  // If a section has an LMAExpr set, we need to find the memory region
+  // the address falls into to reserve some space for it
+  if (Sec->LMAExpr) {
+    uint64_t LMAAddr = Sec->LMAExpr().getValue();
+    Ctx->LMAOffset = LMAAddr - Dot;
+    Ctx->LMARegion = findContainingSection(LMAAddr);
+  }
 
   if (MemoryRegion *MR = Sec->LMARegion)
     Ctx->LMAOffset = MR->CurPos - Dot;
 
   // 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.
   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

test/ELF/linkerscript/Inputs/at10.s

+.section .sec1,"aw",@progbits
+.quad   1
+
+.section .sec2,"aw",@progbits
+.quad   2
+
+.section .sec3,"aw",@progbits
+.quad   3

test/ELF/linkerscript/Inputs/at9.s

+.section .sec1,"aw",@progbits
+.quad   1
+
+.section .sec2,"aw",@progbits
+.quad   2
+
+.section .sec3,"aw",@progbits
+.quad   3

test/ELF/linkerscript/at10.test

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/at10.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 show a huge PhysAddr because of
+# unsigned underflow in the calculation of the LMAOffset
+
+# 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/at9.test

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/at9.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 show a huge PhysAddr because of
+# unsigned underflow in the calculation of the LMAOffset
+
+# 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