[ELF] - Implement linker script OVERLAYs.

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.

Differential revision: https://reviews.llvm.org/D44780

llvm-svn: 335714

6 files changed, 141 insertions, 10 deletions

diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
index 56296f4f2de..efb6aabe974 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -102,6 +102,7 @@ public:
   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);
diff --git a/lld/ELF/ScriptParser.cpp b/lld/ELF/ScriptParser.cpp
index 707e1047972..1d6a2174832 100644
--- a/lld/ELF/ScriptParser.cpp
+++ b/lld/ELF/ScriptParser.cpp
@@ -80,7 +80,9 @@ private:
   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();
@@ -436,6 +438,49 @@ void ScriptParser::readSearchDir() {
   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;
 
@@ -448,6 +493,12 @@ void ScriptParser::readSections() {
   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
@@ -673,6 +724,17 @@ static Expr checkAlignment(Expr E, std::string &Loc) {
   };
 }
 
+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());
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 43f5272855d..3eb345b2ba2 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -2095,7 +2095,8 @@ struct SectionOffset {
 
 // 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;
@@ -2106,12 +2107,19 @@ static void checkOverlap(StringRef Name, std::vector<SectionOffset> &Sections) {
   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));
   }
 }
 
@@ -2139,7 +2147,7 @@ template <class ELFT> void Writer<ELFT>::checkSections() {
     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
@@ -2156,7 +2164,7 @@ template <class ELFT> void Writer<ELFT>::checkSections() {
   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
@@ -2165,7 +2173,7 @@ template <class ELFT> void Writer<ELFT>::checkSections() {
   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.
diff --git a/lld/test/ELF/linkerscript/overlay-reject.test b/lld/test/ELF/linkerscript/overlay-reject.test
new file mode 100644
index 00000000000..fcb82b6df4b
--- /dev/null
+++ b/lld/test/ELF/linkerscript/overlay-reject.test
@@ -0,0 +1,13 @@
+# 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) } 
+  } 
+}
diff --git a/lld/test/ELF/linkerscript/overlay-reject2.test b/lld/test/ELF/linkerscript/overlay-reject2.test
new file mode 100644
index 00000000000..490533c5fa5
--- /dev/null
+++ b/lld/test/ELF/linkerscript/overlay-reject2.test
@@ -0,0 +1,17 @@
+# 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
+  }
+}
diff --git a/lld/test/ELF/linkerscript/overlay.test b/lld/test/ELF/linkerscript/overlay.test
new file mode 100644
index 00000000000..a28ab610ec0
--- /dev/null
+++ b/lld/test/ELF/linkerscript/overlay.test
@@ -0,0 +1,30 @@
+# 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