[ELF] - Implement linker script OVERLAYs.

[grimar]

Summary

This is PR36768.

Linker script OVERLAYs are described in 4.6.9. Overlay Description of the spec:
https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/4/html/Using_ld_the_GNU_Linker/sections.html

They are used to allow output sections which have different LMAs but the same VAs
and used for embedded programming.

Currently, LLD restricts overlapping of sections and that seems to be the most desired
behaviour for defaults. My thoughts about possible approaches for PR36768 are on the bug page,
this patch implements OVERLAY keyword and allows VAs overlapping for sections that within the overlay.

[grimar]

• Minor simplification.

[• espindola]

I agree that adding this is better than relaxing our section overlap checks for every linker script.

Please also add a test showing that we reject explicit addresses and memory regions for the sections inside the overlay.

ELF/LinkerScript.h

315 ↗

(On Diff #139439)

This could be a bit in OutputSection, no?

ELF/ScriptParser.cpp

451 ↗

(On Diff #139439)

Are we missing the alignment?

[grimar]

• Addressed review comments.
• Added load_start_*/load_stop* symbols as specification requests.

ELF/LinkerScript.h

315 ↗

(On Diff #139439)

Yes. Ok.

ELF/ScriptParser.cpp

451 ↗

(On Diff #139439)

GNU ld does not seem to respect the alignment here.

For example for code and script:

.section .aaa, "a"; 
.byte 0; 

.section .bbb, "a"; 
.align 4; 
.byte 0;

SECTIONS {
 . = 0x1000;
  OVERLAY 0x1000 : AT ( 0x4000 ) {
    .aaa { *(.aaa) } 
    .bbb { *(.bbb) } 
  } 
}

Output is:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .aaa              PROGBITS         0000000000001000  00001000
       0000000000000001  0000000000000000   A       0     0     1
  [ 2] .bbb              PROGBITS         0000000000001000  00002000
       0000000000000001  0000000000000000   A       0     0     4

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  LOAD           0x0000000000001000 0x0000000000001000 0x0000000000004000
                 0x0000000000000001 0x0000000000000001  R      1000
  LOAD           0x0000000000002000 0x0000000000001000 0x0000000000004001
                 0x0000000000000001 0x0000000000000001  R      1000

 Section to Segment mapping:
  Segment Sections...
   00     .aaa 
   01     .bbb

And I might be missing something, but it seems correct to me. I see no reason to
waste space with alignments for OVERLAYs, because overlay manager is responsible to
copy sections in and out of the runtime memory address and therefore I think alignment
is just unuseful here.
(4.6.9 Overlay Description, https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/4/html/Using_ld_the_GNU_Linker/sections.html)

[ruiu]

I'm not opposing this patch, but I'm not entirely convinced that we need this feature in the first place. If you need it, please say so.

ELF/ScriptParser.cpp

432 ↗

(On Diff #140077)

This function is too long.

[grimar]

• Addressed review comment.

[grimar]

In D44780#1050794, @ruiu wrote:

I'm not opposing this patch, but I'm not entirely convinced that we need this feature in the first place. If you need it, please say so.

I am implementing it because we have the PR (and because the alternative would be to relax the linker script checks, which is a bit scary way).

[• espindola]

In D44780#1050794, @ruiu wrote:

I'm not opposing this patch, but I'm not entirely convinced that we need this feature in the first place. If you need it, please say so.

We would like something like it.

With bfd this is just syntactic sugar, but only so because it is very liberal about allowing sections to overlap. We could do that, but only allowing overlaps when there is an explicit OVERLAY is better IMHO.

[• espindola]

ELF/ScriptParser.cpp

433 ↗

(On Diff #140214)

Can't we create these symbols in the existing addStartStopSymbols function?

I might be a good idea to leave the symbols for a followup patch.

[grimar]

ELF/ScriptParser.cpp

433 ↗

(On Diff #140214)

I do not think we can use addStartStopSymbols because it uses just created Defined symbols
which values are based on VAs, but here symbols have LMA based values.
Also first what this function does is rejects the sections with !isValidCIdentifier names. This is
different from OVERLAY symbol crafting rules which just drop non-C symbols from the name.

Leaving the symbols for followup sounds OK (if we will choose this way and not the relaxing option instead).

[grimar]

• Rebased.
• Removed start/stop symbols creation part from this patch.

[grimar]

• Minor simplification.

[ruiu]

ELF/ScriptParser.cpp

725 ↗

(On Diff #140923)

We shouldn't add a new parameter to this existing function for the minor feature. Please just remove it.

[grimar]

• Addressed review comment.

ELF/ScriptParser.cpp

725 ↗

(On Diff #140923)

Do you mean we should just accept the syntax which is documented as not
supported for overlayed sections, like AT/ALIGN/SUBALIGN and memory
regions?

I am not fond of that idea honestly, but if so, there would be one more difference in
the syntax that does not allow me simply to drop the InOverlay:

Overlay declaration looks like:

 OVERLAY 0x1000 : AT ( 0x4000 ) {
    .abc { *(.foo) } 
...

Regular section declaration is:

abc : { *(foo) }

Notice that : follows the abc for regular section declaration syntax. And I have to skip it somehow.
I do not think we can use consume(":") in place of expect(":") as it would relax all of our scripts.

What we can probably do instead then is to introduce readOverlaySectionDescription with the minimal needed
syntax support. I did it.

[grimar]

• Rebased + simplified a bit.

[ruiu]

ELF/ScriptParser.cpp

432 ↗

(On Diff #141133)

This needs a pointer to the page describing the OVERLAY command.

444–445 ↗

(On Diff #141133)

This is more conventional.

OutputSection *Prev = nullptr;
for (...) {
  ...
  Prev = OS;
}

462 ↗

(On Diff #141133)

Do you have to compute MaxSize inside a lambda?

ELF/Writer.cpp

2069–2070 ↗

(On Diff #141133)

This seems a overdesign. Implementation simplicity is important. Just skip if "InOverlay" is true. Remove OverlapKind enum.

[grimar]

• Addressed review comments.

ELF/ScriptParser.cpp

462 ↗

(On Diff #141133)

At the moment of parsing the linker script declaration, we do not know the output section sizes yet.
The lambda is needed to delay the computation. I see no other good way to do that.

ELF/Writer.cpp

2069–2070 ↗

(On Diff #141133)

I think that was one of the reasons to implement the OVERLAY instead of using the --no-check-sections.
It was mentioned in comments on bug page (https://bugs.llvm.org/show_bug.cgi?id=36768) that
"One problem with that is that it disables all checking"

Rafael?

[• espindola]

ELF/ScriptParser.cpp

725 ↗

(On Diff #140923)

A possible option is to parse as usual and then error if one of the fields is set, no?

ELF/Writer.cpp

2069–2070 ↗

(On Diff #141133)

I agree with George on this one. We should not disable more checks than necessary.

But you only need a IsVirtualAddresses boolean instead of the enum, no?

[grimar]

• Addressed review comments.

ELF/ScriptParser.cpp

725 ↗

(On Diff #140923)

Unfortunately for the particular place, I am referring to it would not work,
and would need something like InOverlay flag anyways:

We can't parse .abc { *(.foo) } and .abc : { *(.foo) } in the same way I believe.
: is always present for the non-overlay case and always absent for overlays.
So we need to skip it somehow when parsing the overlay or to relax the
syntax parser at this place.

ELF/Writer.cpp

2069–2070 ↗

(On Diff #141133)

Done.

[• espindola]

I think this is the best way to offer this feature.

Do wait for Rui to have a look too.

[grimar]

Ping. Rui?

[grimar]

Ping. Rui?

[grimar]

Ping.

• Rebased.

[ruiu]

ELF/ScriptParser.cpp

460 ↗

(On Diff #152848)

You always call this function with next(), so it is better to call next() inside that function rather than at the call site.

463 ↗

(On Diff #152848)

Can't you use the same LMAExpr again?

ELF/Writer.cpp

2155 ↗

(On Diff #152848)

Since this is a file-scope local function that is written close enough to this call site, you don't need /* IsVirtualAddress */ comment.

[grimar]

• Addressed comments.

ELF/ScriptParser.cpp

460 ↗

(On Diff #152848)

Fixed.

463 ↗

(On Diff #152848)

Sorry, I did not understand what was your suggestion about using LMAExpr here?

ELF/Writer.cpp

2155 ↗

(On Diff #152848)

Fixed.

[ruiu]

ELF/ScriptParser.cpp

463 ↗

(On Diff #152848)

Maybe it's not just doable, but what I was wondering was whether you could repalce this line with OS->LMAExpr = LMAExpr or not.

[grimar]

ELF/ScriptParser.cpp

463 ↗

(On Diff #152848)

Like that?

OutputSection *OS = readOverlaySectionDescription();
OS->AddrExpr = AddrExpr;
OS->LMAExpr = LMAExpr;
V.push_back(OS);

Then no, I can't, because it would cause sections to overlap, for example overlay.test would fail with:

error : section .out.big load address range overlaps with .out.small
>
>  >>> .out.big range is [0x4000, 0x4007]
>
>  >>> .out.small range is [0x4000, 0x4003]
>

It's happening because we need to assign consecutive addresses, but with the code above we would use the same start LMA
for each output section, what is wrong.

[ruiu]

LGTM

ELF/ScriptParser.cpp

474 ↗

(On Diff #152863)

Maybe MoveDot should suffice as the variable has a very narrow scope.

475 ↗

(On Diff #152863)

LIkewise, Max would suffice.

ELF/Writer.cpp

2104 ↗

(On Diff #152863)

IsVirtualAddr

lld/trunk/ELF/OutputSections.h

public:
   llvm::Optional<uint32_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
   std::string Location;
   std::string MemoryRegionName;
   std::string LMARegionName;
   bool NonAlloc = false;
   bool Noload = false;
   bool ExpressionsUseSymbols = false;
+  bool InOverlay = false;
 
   template <class ELFT> void finalize();
   template <class ELFT> void writeTo(uint8_t *Buf);
   template <class ELFT> void maybeCompress();
 
   void sort(llvm::function_ref<int(InputSectionBase *S)> Order);
   void sortInitFini();
   void sortCtorsDtors();

lld/trunk/ELF/ScriptParser.cpp

private:
   void readVersion();
   void readVersionScriptCommand();
 
   SymbolAssignment *readSymbolAssignment(StringRef Name);
   ByteCommand *readByteCommand(StringRef Tok);
   uint32_t readFill();
   uint32_t parseFill(StringRef Tok);
   void readSectionAddressType(OutputSection *Cmd);
+  OutputSection *readOverlaySectionDescription();
   OutputSection *readOutputSectionDescription(StringRef OutSec);
+  std::vector<BaseCommand *> readOverlay();
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription(StringRef Tok);
   StringMatcher readFilePatterns();
   std::vector<SectionPattern> readInputSectionsList();
   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
   unsigned readPhdrType();
   SortSectionPolicy readSortKind();
   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);

 void ScriptParser::readSearchDir() {
   expect("(");
   StringRef Tok = next();
   if (!Config->Nostdlib)
     Config->SearchPaths.push_back(unquote(Tok));
   expect(")");
 }
 
+// This reads an overlay description. Overlays are used to describe output
+// sections that use the same virtual memory range and normally would trigger
+// linker's sections sanity check failures.
+// https://sourceware.org/binutils/docs/ld/Overlay-Description.html#Overlay-Description
+std::vector<BaseCommand *> ScriptParser::readOverlay() {
+  // VA and LMA expressions are optional, though for simplicity of
+  // implementation we assume they are not. That is what OVERLAY was designed
+  // for first of all: to allow sections with overlapping VAs at different LMAs.
+  Expr AddrExpr = readExpr();
+  expect(":");
+  expect("AT");
+  Expr LMAExpr = readParenExpr();
+  expect("{");
+
+  std::vector<BaseCommand *> V;
+  OutputSection *Prev = nullptr;
+  while (!errorCount() && !consume("}")) {
+    // VA is the same for all sections. The LMAs are consecutive in memory
+    // starting from the base load address specified.
+    OutputSection *OS = readOverlaySectionDescription();
+    OS->AddrExpr = AddrExpr;
+    if (Prev)
+      OS->LMAExpr = [=] { return Prev->getLMA() + Prev->Size; };
+    else
+      OS->LMAExpr = LMAExpr;
+    V.push_back(OS);
+    Prev = OS;
+  }
+
+  // According to the specification, at the end of the overlay, the location
+  // counter should be equal to the overlay base address plus size of the
+  // largest section seen in the overlay.
+  // Here we want to create the Dot assignment command to achieve that.
+  Expr MoveDot = [=] {
+    uint64_t Max = 0;
+    for (BaseCommand *Cmd : V)
+      Max = std::max(Max, cast<OutputSection>(Cmd)->Size);
+    return AddrExpr().getValue() + Max;
+  };
+  V.push_back(make<SymbolAssignment>(".", MoveDot, getCurrentLocation()));
+  return V;
+}
+
 void ScriptParser::readSections() {
   Script->HasSectionsCommand = true;
 
   // -no-rosegment is used to avoid placing read only non-executable sections in
   // their own segment. We do the same if SECTIONS command is present in linker
   // script. See comment for computeFlags().
   Config->SingleRoRx = true;
 
   expect("{");
   std::vector<BaseCommand *> V;
   while (!errorCount() && !consume("}")) {
     StringRef Tok = next();
+    if (Tok == "OVERLAY") {
+      for (BaseCommand *Cmd : readOverlay())
+        V.push_back(Cmd);
+      continue;
+    }
+
     if (BaseCommand *Cmd = readAssignment(Tok))
       V.push_back(Cmd);
     else
       V.push_back(readOutputSectionDescription(Tok));
   }
 
   if (!atEOF() && consume("INSERT")) {
     std::vector<BaseCommand *> *Dest = nullptr;
return [=] {
     if (!isPowerOf2_64(Alignment)) {
       error(Loc + ": alignment must be power of 2");
       return (uint64_t)1; // Return a dummy value.
     }
     return Alignment;
   };
 }
 
+OutputSection *ScriptParser::readOverlaySectionDescription() {
+  OutputSection *Cmd =
+      Script->createOutputSection(next(), getCurrentLocation());
+  Cmd->InOverlay = true;
+  expect("{");
+  while (!errorCount() && !consume("}"))
+    Cmd->SectionCommands.push_back(readInputSectionRules(next()));
+  Cmd->Phdrs = readOutputSectionPhdrs();
+  return Cmd;
+}
+
 OutputSection *ScriptParser::readOutputSectionDescription(StringRef OutSec) {
   OutputSection *Cmd =
       Script->createOutputSection(OutSec, getCurrentLocation());
 
   size_t SymbolsReferenced = Script->ReferencedSymbols.size();
 
   if (peek() != ":")
     readSectionAddressType(Cmd);

lld/trunk/ELF/Writer.cpp

 struct SectionOffset {
   OutputSection *Sec;
   uint64_t Offset;
 };
 } // namespace
 
 // Check whether sections overlap for a specific address range (file offsets,
 // load and virtual adresses).
-static void checkOverlap(StringRef Name, std::vector<SectionOffset> &Sections) {
+static void checkOverlap(StringRef Name, std::vector<SectionOffset> &Sections,
+                         bool IsVirtualAddr) {
   llvm::sort(Sections.begin(), Sections.end(),
              [=](const SectionOffset &A, const SectionOffset &B) {
                return A.Offset < B.Offset;
              });
 
   // Finding overlap is easy given a vector is sorted by start position.
   // If an element starts before the end of the previous element, they overlap.
   for (size_t I = 1, End = Sections.size(); I < End; ++I) {
     SectionOffset A = Sections[I - 1];
     SectionOffset B = Sections[I];
-    if (B.Offset < A.Offset + A.Sec->Size)
-      errorOrWarn(
-          "section " + A.Sec->Name + " " + Name + " range overlaps with " +
-          B.Sec->Name + "\n>>> " + A.Sec->Name + " range is " +
-          rangeToString(A.Offset, A.Sec->Size) + "\n>>> " + B.Sec->Name +
-          " range is " + rangeToString(B.Offset, B.Sec->Size));
+    if (B.Offset >= A.Offset + A.Sec->Size)
+      continue;
+
+    // If both sections are in OVERLAY we allow the overlapping of virtual
+    // addresses, because it is what OVERLAY was designed for.
+    if (IsVirtualAddr && A.Sec->InOverlay && B.Sec->InOverlay)
+      continue;
+
+    errorOrWarn("section " + A.Sec->Name + " " + Name +
+                " range overlaps with " + B.Sec->Name + "\n>>> " + A.Sec->Name +
+                " range is " + rangeToString(A.Offset, A.Sec->Size) + "\n>>> " +
+                B.Sec->Name + " range is " +
+                rangeToString(B.Offset, B.Sec->Size));
   }
 }
 
 // Check for overlapping sections and address overflows.
 //
 // In this function we check that none of the output sections have overlapping
 // file offsets. For SHF_ALLOC sections we also check that the load address
 // ranges and the virtual address ranges don't overlap
template <class ELFT> void Writer<ELFT>::checkSections() {
   // the file so Sec->Offset + Sec->Size can overlap with others. If --oformat
   // binary is specified only add SHF_ALLOC sections are added to the output
   // file so we skip any non-allocated sections in that case.
   std::vector<SectionOffset> FileOffs;
   for (OutputSection *Sec : OutputSections)
     if (0 < Sec->Size && Sec->Type != SHT_NOBITS &&
         (!Config->OFormatBinary || (Sec->Flags & SHF_ALLOC)))
       FileOffs.push_back({Sec, Sec->Offset});
-  checkOverlap("file", FileOffs);
+  checkOverlap("file", FileOffs, false);
 
   // When linking with -r there is no need to check for overlapping virtual/load
   // addresses since those addresses will only be assigned when the final
   // executable/shared object is created.
   if (Config->Relocatable)
     return;
 
   // Checking for overlapping virtual and load addresses only needs to take
   // into account SHF_ALLOC sections since others will not be loaded.
   // Furthermore, we also need to skip SHF_TLS sections since these will be
   // mapped to other addresses at runtime and can therefore have overlapping
   // ranges in the file.
   std::vector<SectionOffset> VMAs;
   for (OutputSection *Sec : OutputSections)
     if (0 < Sec->Size && (Sec->Flags & SHF_ALLOC) && !(Sec->Flags & SHF_TLS))
       VMAs.push_back({Sec, Sec->Addr});
-  checkOverlap("virtual address", VMAs);
+  checkOverlap("virtual address", VMAs, true);
 
   // Finally, check that the load addresses don't overlap. This will usually be
   // the same as the virtual addresses but can be different when using a linker
   // script with AT().
   std::vector<SectionOffset> LMAs;
   for (OutputSection *Sec : OutputSections)
     if (0 < Sec->Size && (Sec->Flags & SHF_ALLOC) && !(Sec->Flags & SHF_TLS))
       LMAs.push_back({Sec, Sec->getLMA()});
-  checkOverlap("load address", LMAs);
+  checkOverlap("load address", LMAs, false);
 }
 
 // The entry point address is chosen in the following ways.
 //
 // 1. the '-e' entry command-line option;
 // 2. the ENTRY(symbol) command in a linker control script;
 // 3. the value of the symbol _start, if present;
 // 4. the number represented by the entry symbol, if it is a number;

lld/trunk/test/ELF/linkerscript/overlay-reject.test

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux /dev/null -o %t.o
+# RUN: not ld.lld %t.o --script %s -o %t 2>&1 | FileCheck %s
+
+# CHECK:      {{.*}}.test:{{.*}}: { expected, but got 0x3000
+# CHECK-NEXT: >>>     .out.aaa 0x3000 : { *(.aaa) }
+# CHECK-NEXT: >>>              ^
+
+SECTIONS {
+  OVERLAY 0x1000 : AT ( 0x2000 ) {
+    .out.aaa 0x3000 : { *(.aaa) } 
+  } 
+}

lld/trunk/test/ELF/linkerscript/overlay-reject2.test

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux /dev/null -o %t.o
+# RUN: not ld.lld %t.o --script %s -o %t 2>&1 | FileCheck %s
+
+# CHECK:      {{.*}}.test:{{.*}}: { expected, but got AX
+# CHECK-NEXT: >>>      .out.aaa { *(.aaa) } > AX AT>FLASH
+# CHECK-NEXT: >>>                             ^
+
+MEMORY {
+  AX (ax)    : ORIGIN = 0x3000, LENGTH = 0x4000
+}
+
+SECTIONS {
+  OVERLAY 0x1000 : AT ( 0x2000 ) {
+    .out.aaa { *(.aaa) } > AX AT>FLASH
+  }
+}

lld/trunk/test/ELF/linkerscript/overlay.test

+# REQUIRES: x86
+# RUN: echo 'nop; .section .small, "a"; .long 0; .section .big, "a"; .quad 1;' \
+# RUN:   | llvm-mc -filetype=obj -triple=x86_64-unknown-linux - -o %t.o
+# RUN: ld.lld %t.o --script %s -o %t
+
+SECTIONS {
+  OVERLAY 0x1000 : AT ( 0x4000 ) {
+    .out.big { *(.big) } 
+    .out.small { *(.small) } 
+  } 
+}
+
+## Here we check that can handle OVERLAY which will produce sections 
+## .out.big and .out.small with the same starting VAs, but different LMAs.
+## Section .big is larger than .small, we check that placing of section
+## .text does not cause overlapping error and that
+## .text's VA is 0x1000 + max(sizeof(.out.big), sizeof(.out.small)).
+
+# RUN: llvm-readobj -sections -program-headers -elf-output-style=GNU %t | FileCheck %s
+
+# CHECK: Section Headers:
+# CHECK: Name       Type     Address          Off    Size
+# CHECK: .out.big   PROGBITS 0000000000001000 001000 000008
+# CHECK: .out.small PROGBITS 0000000000001000 002000 000004
+# CHECK: .text      PROGBITS 0000000000001008 002008 000001
+
+# CHECK:      Program Headers:
+# CHECK:      Type Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
+# CHECK-NEXT: LOAD 0x001000 0x0000000000001000 0x0000000000004000 0x000008 0x000008 R E 0x1000
+# CHECK-NEXT: LOAD 0x002000 0x0000000000001000 0x0000000000004008 0x000009 0x000009 R E 0x1000