[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

This could be a bit in OutputSection, no?

ELF/ScriptParser.cpp

451

Are we missing the alignment?

[grimar]

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

ELF/LinkerScript.h

315

Yes. Ok.

ELF/ScriptParser.cpp

451

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

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

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

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

727

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

727

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

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

444–445

This is more conventional.

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

462

Do you have to compute MaxSize inside a lambda?

ELF/Writer.cpp

2004–2005

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

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

2004–2005

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

727

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

ELF/Writer.cpp

2004–2005

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

727

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

2004–2005

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

451

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

454

Can't you use the same LMAExpr again?

ELF/Writer.cpp

2031–2043

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

451

Fixed.

454

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

ELF/Writer.cpp

2031–2043

Fixed.

[ruiu]

ELF/ScriptParser.cpp

454

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

454

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

465

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

466

LIkewise, Max would suffice.

ELF/Writer.cpp

1973

IsVirtualAddr

ELF/LinkerScript.h

public:
 
   // A list of symbols referenced by the script.
   std::vector<llvm::StringRef> ReferencedSymbols;
 
   // Used to implement INSERT [AFTER|BEFORE]. Contains commands that need
   // to be inserted into SECTIONS commands list.
   llvm::DenseMap<StringRef, std::vector<BaseCommand *>> InsertAfterCommands;
   llvm::DenseMap<StringRef, std::vector<BaseCommand *>> InsertBeforeCommands;
+
+  // Used to implement OVERLAY. Contains all output sections
+  // that were seen in overlay descriptions.
+  llvm::DenseSet<OutputSection *> OverlaySections;
 };
 
 extern LinkerScript *Script;
 
 } // end namespace elf
 } // end namespace lld
 
 #endif // LLD_ELF_LINKER_SCRIPT_H

ELF/ScriptParser.cpp

private:
   void readVersion();
   void readVersionScriptCommand();
 
   SymbolAssignment *readAssignment(StringRef Name);
   ByteCommand *readByteCommand(StringRef Tok);
   uint32_t readFill();
   uint32_t parseFill(StringRef Tok);
   void readSectionAddressType(OutputSection *Cmd);
-  OutputSection *readOutputSectionDescription(StringRef OutSec);
+  OutputSection *readOutputSectionDescription(StringRef OutSec, bool InOverlay);
+  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(")");
 }
 
+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;
+  while (!errorCount() && !consume("}")) {
+    OutputSection *Prev = V.empty() ? nullptr : cast<OutputSection>(V.back());
+    OutputSection *Cmd =
+        readOutputSectionDescription(next(), /*InOverlay=*/true);
+    // VA is the same for all sections. The LMAs are consecutive in memory
+    // starting from the base load address specified.
+    Cmd->AddrExpr = AddrExpr;
+    if (Prev)
+      Cmd->LMAExpr = [=] { return Prev->LMAExpr().getValue() + Prev->Size; };
+    else
+      Cmd->LMAExpr = LMAExpr;
+
+    Script->OverlaySections.insert(Cmd);
+    V.push_back(Cmd);
+  }
+
+  // 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 MoveDotExpr = [=] {
+    uint64_t MaxSize = 0;
+    for (BaseCommand *Cmd : V)
+      if (MaxSize < cast<OutputSection>(Cmd)->Size)
+        MaxSize = cast<OutputSection>(Cmd)->Size;
+    return AddrExpr().getValue() + MaxSize;
+  };
+  V.push_back(make<SymbolAssignment>(".", MoveDotExpr, getCurrentLocation(),
+                                     "" /*CommandString*/));
+  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;
+    }
+
     BaseCommand *Cmd = readProvideOrAssignment(Tok);
     if (!Cmd) {
       if (Tok == "ASSERT")
         Cmd = readAssert();
       else
-        Cmd = readOutputSectionDescription(Tok);
+        Cmd = readOutputSectionDescription(Tok, /*InOverlay=*/false);
     }
     V.push_back(Cmd);
   }
 
   if (!atEOF() && consume("INSERT")) {
     std::vector<BaseCommand *> *Dest = nullptr;
     if (consume("AFTER"))
       Dest = &Script->InsertAfterCommands[next()];
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::readOutputSectionDescription(StringRef OutSec) {
+OutputSection *ScriptParser::readOutputSectionDescription(StringRef OutSec,
+                                                          bool InOverlay) {
   OutputSection *Cmd =
       Script->createOutputSection(OutSec, getCurrentLocation());
 
   size_t SymbolsReferenced = Script->ReferencedSymbols.size();
 
+  if (!InOverlay) {
     if (peek() != ":")
       readSectionAddressType(Cmd);
     expect(":");
 
     std::string Location = getCurrentLocation();
     if (consume("AT"))
       Cmd->LMAExpr = readParenExpr();
     if (consume("ALIGN"))
       Cmd->AlignExpr = checkAlignment(readParenExpr(), Location);
     if (consume("SUBALIGN"))
       Cmd->SubalignExpr = checkAlignment(readParenExpr(), Location);
 
     // Parse constraints.
     if (consume("ONLY_IF_RO"))
       Cmd->Constraint = ConstraintKind::ReadOnly;
     if (consume("ONLY_IF_RW"))
       Cmd->Constraint = ConstraintKind::ReadWrite;
+  }
   expect("{");
 
   while (!errorCount() && !consume("}")) {
     StringRef Tok = next();
     if (Tok == ";") {
       // Empty commands are allowed. Do nothing here.
     } else if (SymbolAssignment *Assign = readProvideOrAssignment(Tok)) {
       Cmd->SectionCommands.push_back(Assign);

ELF/Writer.cpp

for (PhdrEntry *P : Phdrs) {
     if (P->p_type == PT_TLS) {
       Out::TlsPhdr = P;
       if (P->p_memsz)
         P->p_memsz = alignTo(P->p_memsz, P->p_align);
     }
   }
 }
 
+enum class OverlapKind : uint8_t { File, VirtualAddress, LoadAddress };
+
 // Check whether sections overlap for a specific address range (file offsets,
 // load and virtual adresses).
 //
 // This is a helper function called by Writer::checkNoOverlappingSections().
 template <typename Getter, typename Predicate>
 static void checkForSectionOverlap(ArrayRef<OutputSection *> AllSections,
-                                   StringRef Kind, Getter GetStart,
+                                   OverlapKind Kind, Getter GetStart,
                                    Predicate ShouldSkip) {
   std::vector<OutputSection *> Sections;
   // By removing all zero-size sections we can simplify the check for overlap to
   // just checking whether the section range contains the other section's start
   // address. Additionally, it also slightly speeds up the checking since we
   // don't bother checking for overlap with sections that can never overlap.
   for (OutputSection *Sec : AllSections)
     if (Sec->Size > 0 && !ShouldSkip(Sec))
       Sections.push_back(Sec);
 
   // Instead of comparing every OutputSection with every other output section
   // we sort the sections by address (file offset or load/virtual address). This
   // way we find all overlapping sections but only need one comparision with the
   // next section in the common non-overlapping case. The only time we end up
   // doing more than one iteration of the following nested loop is if there are
   // overlapping sections.
   std::sort(Sections.begin(), Sections.end(),
             [=](const OutputSection *A, const OutputSection *B) {
               return GetStart(A) < GetStart(B);
             });
+  StringRef KindS[] = {"file", "virtual address", "load address"};
   for (size_t I = 0; I < Sections.size(); ++I) {
     OutputSection *Sec = Sections[I];
     uint64_t Start = GetStart(Sec);
     for (auto *Other : ArrayRef<OutputSection *>(Sections).slice(I + 1)) {
       // Since the sections are sorted by start address we only need to check
       // whether the other sections starts before the end of Sec. If this is
       // not the case we can break out of this loop since all following sections
       // will also start after the end of Sec.
       if (Start + Sec->Size <= GetStart(Other))
         break;
-      errorOrWarn("section " + Sec->Name + " " + Kind +
+
+      // If both sections are in OVERLAY we allow the overlapping of virtual
+      // addresses, because it is what OVERLAY was designed for.
+      if (Kind == OverlapKind::VirtualAddress &&
+          Script->OverlaySections.count(Sec) &&
+          Script->OverlaySections.count(Other))
+        continue;
+
+      errorOrWarn("section " + Sec->Name + " " + KindS[(uint8_t)Kind] +
                   " range overlaps with " + Other->Name + "\n>>> " + Sec->Name +
                   " range is " + rangeToString(Start, Sec->Size) + "\n>>> " +
                   Other->Name + " range is " +
                   rangeToString(GetStart(Other), Other->Size));
     }
   }
 }
 
 // Check for overlapping sections
 //
 // 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>::checkNoOverlappingSections() {
   // First check for overlapping file offsets. In this case we need to skip
   // Any section marked as SHT_NOBITS. These sections don't actually occupy
   // space in 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.
-  checkForSectionOverlap(OutputSections, "file",
+  checkForSectionOverlap(OutputSections, OverlapKind::File,
                          [](const OutputSection *Sec) { return Sec->Offset; },
                          [](const OutputSection *Sec) {
                            return Sec->Type == SHT_NOBITS ||
                                   (Config->OFormatBinary &&
                                    (Sec->Flags & SHF_ALLOC) == 0);
                          });
 
   // 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.
   auto SkipNonAllocSections = [](const OutputSection *Sec) {
     return (Sec->Flags & SHF_ALLOC) == 0 || (Sec->Flags & SHF_TLS);
   };
-  checkForSectionOverlap(OutputSections, "virtual address",
+  checkForSectionOverlap(OutputSections, OverlapKind::VirtualAddress,
                          [](const OutputSection *Sec) { return Sec->Addr; },
                          SkipNonAllocSections);
 
   // 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().
-  checkForSectionOverlap(OutputSections, "load address",
+  checkForSectionOverlap(OutputSections, OverlapKind::LoadAddress,
                          [](const OutputSection *Sec) { return Sec->getLMA(); },
                          SkipNonAllocSections);
 }
 
 // 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;

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