[ELF] Linkerscript: Yet Another Fix For Empty Sections.

[evgeny777]

Summary

Current implementation handles empty section only in case it contains symbols. Unfortunately it's not the only case when empty section should be kept. Consider the following example:

SECTIONS {
  .eh_frame_hdr : { *(.eh_frame_hdr) }
  __eh_frame_hdr_start = ADDR(.eh_frame_hdr);
}

This script cannot be processed by lld in case there is no .eh_frame_hdr section in the target image.
The proposed implementation doesn't have side effects (no extended PT_LOADs and no empty sections in the target image) and doesn't look more complex than the existing one

[• rafael]

I think I am sold on this, but it needs some comments. Also, please don't delete the tests, instead show what is now produced. One of the advantages of this implementation is precisely that PT_LOAD creation is not impacted.

ELF/LinkerScript.cpp

456

Don't you have to adjust the value?

500

Add a comment about what is being done. If I understand it correctly, it is:

• In here, create any missing output section as SHF_EXCLUDE. They are created such that in the end the OutputSectionCommands and the OutputSections are in the same order and have a 1:1 mapping.
• The creation is after the creation of PT_LOADs, so they don't impact them.
• Once addresses have been computed, the sections are deleted.

Also comment about the fact that we know no existing section can have the SHF_EXCLUDE flag.

507

std::find_if

ELF/LinkerScript.h

struct OutputSectionCommand : BaseCommand {
   Expr AddrExpr;
   Expr AlignExpr;
   Expr LmaExpr;
   Expr SubalignExpr;
   std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
+  bool IsEmpty = false;
 };
 
 // This struct represents one section match pattern in SECTIONS() command.
 // It can optionally have negative match pattern for EXCLUDED_FILE command.
 // Also it may be surrounded with SORT() command, so contains sorting rules.
 struct SectionPattern {
   SectionPattern(llvm::Regex &&Re1, llvm::Regex &&Re2)
       : ExcludedFileRe(std::forward<llvm::Regex>(Re1)),
private:
 
   void addSection(OutputSectionFactory<ELFT> &Factory,
                   InputSectionBase<ELFT> *Sec, StringRef Name);
   void discard(ArrayRef<InputSectionBase<ELFT> *> V);
 
   std::vector<InputSectionBase<ELFT> *>
   createInputSectionList(OutputSectionCommand &Cmd);
 
+  void addEmptySections();
+
   // "ScriptConfig" is a bit too long, so define a short name for it.
   ScriptConfiguration &Opt = *ScriptConfig;
 
   std::vector<size_t> getPhdrIndices(StringRef SectionName);
   size_t getPhdrIndex(StringRef PhdrName);
 
   uintX_t Dot;
   OutputSectionBase<ELFT> *CurOutSec = nullptr;

ELF/LinkerScript.cpp

findSections(OutputSectionCommand &Cmd,
              const std::vector<OutputSectionBase<ELFT> *> &Sections) {
   std::vector<OutputSectionBase<ELFT> *> Ret;
   for (OutputSectionBase<ELFT> *Sec : Sections)
     if (Sec->getName() == Cmd.Name)
       Ret.push_back(Sec);
   return Ret;
 }
 
+// Convert synthetic symbol to absolute. Used for symbols defined in
+// empty sections. Those sections do not exist in final ELF image
+template <class ELFT> static void makeAbsolute(SymbolBody *Body) {
+  auto *Synthetic = dyn_cast_or_null<DefinedSynthetic<ELFT>>(Body);
+  if (!Synthetic)
+    return;
+
+  Symbol *S = Synthetic->symbol();
+  uint32_t GotIndex = Synthetic->GotIndex;
+  unsigned DynsymIndex = Synthetic->DynsymIndex;
+
+  replaceBody<DefinedRegular<ELFT>>(S, Body->getName(),
+                                    static_cast<uint8_t>(S->Visibility));
+  auto *Regular = cast<DefinedRegular<ELFT>>(Body);
+  Regular->GotIndex = GotIndex;
+  Regular->DynsymIndex = DynsymIndex;
+}
+
+// Convert all section synthetic symbols to absolute. This is
+// done for empty sections, which are removed in assignAddresses().
+template <class ELFT>
+static void makeSymbolsAbsolute(OutputSectionCommand *Cmd) {
+  for (std::unique_ptr<BaseCommand> &Base : Cmd->Commands)
+    if (auto *AssignCmd = dyn_cast<SymbolAssignment>(Base.get()))
+      makeAbsolute<ELFT>(AssignCmd->Sym);
+}
+
 template <class ELFT>
 void LinkerScript<ELFT>::assignOffsets(OutputSectionCommand *Cmd) {
   std::vector<OutputSectionBase<ELFT> *> Sections =
       findSections(*Cmd, *OutputSections);
   if (Sections.empty())
     return;
   switchTo(Sections[0]);
 
+  // We are to remove all empty sections, so symbols should be
+  // made absolute.
+  if (Cmd->IsEmpty)
+    makeSymbolsAbsolute<ELFT>(Cmd);
+
   // Find the last section output location. We will output orphan sections
   // there so that end symbols point to the correct location.
   auto E = std::find_if(Cmd->Commands.rbegin(), Cmd->Commands.rend(),
                         [](const std::unique_ptr<BaseCommand> &Cmd) {
                           return !isa<SymbolAssignment>(*Cmd);
                         })
                .base();
   for (auto I = Cmd->Commands.begin(); I != E; ++I)
     process(**I);
   for (OutputSectionBase<ELFT> *Base : Sections)
     switchTo(Base);
   flush();
   std::for_each(E, Cmd->Commands.end(),
                 [this](std::unique_ptr<BaseCommand> &B) { process(*B.get()); });
 }
 
-template <class ELFT> void LinkerScript<ELFT>::adjustSectionsBeforeSorting() {
-  // It is common practice to use very generic linker scripts. So for any
-  // given run some of the output sections in the script will be empty.
-  // We could create corresponding empty output sections, but that would
-  // clutter the output.
-  // We instead remove trivially empty sections. The bfd linker seems even
-  // more aggressive at removing them.
-  auto Pos = std::remove_if(
-      Opt.Commands.begin(), Opt.Commands.end(),
-      [&](const std::unique_ptr<BaseCommand> &Base) {
-        auto *Cmd = dyn_cast<OutputSectionCommand>(Base.get());
-        if (!Cmd)
-          return false;
-        std::vector<OutputSectionBase<ELFT> *> Secs =
-            findSections(*Cmd, *OutputSections);
-        if (!Secs.empty())
-          return false;
-        for (const std::unique_ptr<BaseCommand> &I : Cmd->Commands)
-          if (!isa<InputSectionDescription>(I.get()))
-            return false;
-        return true;
-      });
-  Opt.Commands.erase(Pos, Opt.Commands.end());
-
-  // If the output section contains only symbol assignments, create a
-  // corresponding output section. The bfd linker seems to only create them if
-  // '.' is assigned to, but creating these section should not have any bad
-  // consequeces and gives us a section to put the symbol in.
-  uintX_t Flags = SHF_ALLOC;
-  uint32_t Type = 0;
+template <class ELFT> void LinkerScript<ELFT>::addEmptySections() {
+  auto InsertIt = OutputSections->begin();
   for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
-    auto *Cmd = dyn_cast<OutputSectionCommand>(Base.get());
-    if (!Cmd)
-      continue;
-    std::vector<OutputSectionBase<ELFT> *> Secs =
-        findSections(*Cmd, *OutputSections);
-    if (!Secs.empty()) {
-      Flags = Secs[0]->getFlags();
-      Type = Secs[0]->getType();
+    OutputSectionCommand *Cmd = dyn_cast<OutputSectionCommand>(Base.get());
+    if (!Cmd || Cmd->Name == "/DISCARD/")
       continue;
+
+    bool FoundIt = false;
+    for (auto It = OutputSections->begin(); It != OutputSections->end(); ++It)
+      if ((*It)->getName() == Cmd->Name) {
+        FoundIt = true;
+        InsertIt = It + 1;
       }
 
-    auto *OutSec = new OutputSection<ELFT>(Cmd->Name, Type, Flags);
-    Out<ELFT>::Pool.emplace_back(OutSec);
-    OutputSections->push_back(OutSec);
+    if (!FoundIt) {
+      Cmd->IsEmpty = true;
+      OutputSectionBase<ELFT> *EmptySec = new OutputSectionBase<ELFT>(
+          Cmd->Name, SHT_NULL, SHF_EXCLUDE | SHF_ALLOC);
+      InsertIt = OutputSections->insert(InsertIt, EmptySec) + 1;
+      Out<ELFT>::Pool.emplace_back(EmptySec);
+    }
   }
 }
 
 // When placing orphan sections, we want to place them after symbol assignments
 // so that an orphan after
 //   begin_foo = .;
 //   foo : { *(foo) }
 //   end_foo = .;
static bool shouldSkip(const BaseCommand &Cmd) {
   if (isa<OutputSectionCommand>(Cmd))
     return false;
   const auto *Assign = dyn_cast<SymbolAssignment>(&Cmd);
   if (!Assign)
     return true;
   return Assign->Name != ".";
 }
 
+template <class Range, class Pred> static void removeIf(Range &R, Pred P) {
+  R.erase(std::remove_if(R.begin(), R.end(), P), R.end());
+}
+
 template <class ELFT> void LinkerScript<ELFT>::assignAddresses() {
+  // Temporarily add empty sections to the list of output sections.
+  addEmptySections();
+
   // Orphan sections are sections present in the input files which
   // are not explicitly placed into the output file by the linker script.
   // We place orphan sections at end of file.
   // Other linkers places them using some heuristics as described in
   // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
 
   // The OutputSections are already in the correct order.
   // This loops creates or moves commands as needed so that they are in the
for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     auto *Cmd = cast<OutputSectionCommand>(Base.get());
 
     if (Cmd->AddrExpr)
       Dot = Cmd->AddrExpr(Dot);
 
     assignOffsets(Cmd);
   }
 
+  removeIf(*OutputSections, [](OutputSectionBase<ELFT> *Sec) {
+    return Sec->getFlags() & SHF_EXCLUDE;
+  });
+
   uintX_t MinVA = std::numeric_limits<uintX_t>::max();
   for (OutputSectionBase<ELFT> *Sec : *OutputSections) {
     if (Sec->getFlags() & SHF_ALLOC)
       MinVA = std::min(MinVA, Sec->getVA());
     else
       Sec->setVA(0);
   }
 

ELF/Writer.cpp

 }
 
 template <class ELFT> void Writer<ELFT>::sortSections() {
   if (!ScriptConfig->HasSections) {
     std::stable_sort(OutputSections.begin(), OutputSections.end(),
                      compareSectionsNonScript<ELFT>);
     return;
   }
-  Script<ELFT>::X->adjustSectionsBeforeSorting();
-
   // The order of the sections in the script is arbitrary and may not agree with
   // compareSectionsNonScript. This means that we cannot easily define a
   // strict weak ordering. To see why, consider a comparison of a section in the
   // script and one not in the script. We have a two simple options:
   // * Make them equivalent (a is not less than b, and b is not less than a).
   //   The problem is then that equivalence has to be transitive and we can
   //   have sections a, b and c with only b in a script and a less than c
   //   which breaks this property.

test/ELF/linkerscript/extend-pt-load.s

-# REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
-
-# This test demonstrates an odd consequence of the way we handle sections with just symbol
-# assignments.
-
-# First, run a test with no such section.
-
-# RUN: echo "SECTIONS { \
-# RUN:  .text : { *(.text) } \
-# RUN:  . = ALIGN(0x1000); \
-# RUN:  .data.rel.ro : { *(.data.rel.ro) } \
-# RUN: }" > %t.script
-# RUN: ld.lld -o %t1 --script %t.script %t.o -shared
-# RUN: llvm-readobj --elf-output-style=GNU -l -s %t1 | FileCheck --check-prefix=CHECK1 %s
-
-# CHECK1:      .text        PROGBITS 00000000000001bc 0001bc 000001 00 AX
-# CHECK1-NEXT: .data.rel.ro PROGBITS 0000000000001000 001000 000001 00 WA
-
-# CHECK1:      LOAD 0x000000 0x0000000000000000 0x0000000000000000 0x0001bd 0x0001bd R E
-# CHECK1-NEXT: LOAD 0x001000 0x0000000000001000 0x0000000000001000 0x000068 0x000068 RW
-
-# Then add the section bar. Note how bar is given AX flags, which causes the PT_LOAD to now
-# cover the padding bits created by ALIGN.
-
-# RUN: echo "SECTIONS { \
-# RUN:  .text : { *(.text) } \
-# RUN:  . = ALIGN(0x1000); \
-# RUN:  bar : { HIDDEN(bar_sym = .); } \
-# RUN:  .data.rel.ro : { *(.data.rel.ro) } \
-# RUN: }" > %t.script
-# RUN: ld.lld -o %t2 --script %t.script %t.o -shared
-# RUN: llvm-readobj --elf-output-style=GNU -l -s %t2 | FileCheck --check-prefix=CHECK2 %s
-
-# CHECK2:      .text        PROGBITS 00000000000001bc 0001bc 000001 00 AX
-# CHECK2-NEXT: bar          PROGBITS 0000000000001000 001000 000000 00 AX
-# CHECK2-NEXT: .data.rel.ro PROGBITS 0000000000001000 001000 000001 00 WA
-
-# CHECK2:      LOAD 0x000000 0x0000000000000000 0x0000000000000000 0x001000 0x001000 R E
-# CHECK2-NEXT: LOAD 0x001000 0x0000000000001000 0x0000000000001000 0x000068 0x000068 RW
-
-# If the current behavior becomes a problem we should consider just moving the commands out
-# of the section. That is, handle the above like the following test.
-
-# RUN: echo "SECTIONS { \
-# RUN:  .text : { *(.text) } \
-# RUN:  . = ALIGN(0x1000); \
-# RUN:  HIDDEN(bar_sym = .); \
-# RUN:  .data.rel.ro : { *(.data.rel.ro) } \
-# RUN: }" > %t.script
-# RUN: ld.lld -o %t3 --script %t.script %t.o -shared
-# RUN: llvm-readobj --elf-output-style=GNU -l -s %t3 | FileCheck --check-prefix=CHECK1 %s
-
-nop
-
-.section .data.rel.ro, "aw"
-.byte 0

test/ELF/linkerscript/symbol-only.s

-# REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
-
-# RUN: echo "SECTIONS { \
-# RUN:  abc : { foo = .; } \
-# RUN:  . = ALIGN(0x1000); \
-# RUN:  bar : { *(bar) } \
-# RUN: }" > %t.script
-# RUN: ld.lld -o %t1 --script %t.script %t -shared
-# RUN: llvm-objdump -section-headers -t %t1 | FileCheck %s
-# CHECK:      Sections:
-# CHECK-NEXT: Idx Name          Size      Address
-# CHECK-NEXT:   0               00000000 0000000000000000
-# CHECK-NEXT:   1 abc           00000000 [[ADDR:[0-9a-f]*]]
-# CHECK-NEXT:   2 bar           00000000 0000000000001000 DATA
-
-# CHECK: SYMBOL TABLE:
-# CHECK:     [[ADDR]]         abc                00000000 foo
-
-.section bar, "a"

test/ELF/linkerscript/symbols-synthetic.s

 # RUN:             PROVIDE_HIDDEN(_begin_sec = .); \
 # RUN:             *(.eh_frame_hdr) \
 # RUN:             *(.eh_frame_hdr) \
 # RUN:             PROVIDE_HIDDEN(_end_sec_abs = ABSOLUTE(.)); \
 # RUN:             PROVIDE_HIDDEN(_end_sec = .); } \
 # RUN:         }" > %t.script
 # RUN: ld.lld -o %t1 --eh-frame-hdr --script %t.script %t
 
+# Check symbols inside empty section. Also check section size and address.
+# RUN: echo "SECTIONS { \
+# RUN:          .aaa : { \
+# RUN:             PROVIDE_HIDDEN(_begin_sec = .); \
+# RUN:             *(.bbb) \
+# RUN:             *(.ccc) \
+# RUN:             PROVIDE_HIDDEN(_end_sec = .); \
+# RUN:             PROVIDE_HIDDEN(_end_sec_abs = ABSOLUTE(.)); } \
+# RUN:          addr_of_aaa = ADDR(.aaa); \
+# RUN:          size_of_aaa = SIZEOF(.aaa); \
+# RUN:          align_of_aaa = ALIGNOF(.aaa); \
+# RUN:         }" > %t.script
+# RUN: ld.lld -o %t1 --script %t.script %t
+# RUN: llvm-objdump -t %t1 | FileCheck --check-prefix=EMPTY %s
+
 # SIMPLE:      0000000000000128         .foo    00000000 .hidden _end_sec
 # SIMPLE-NEXT: 0000000000000120         .foo    00000000 _begin_sec
 # SIMPLE-NEXT: 0000000000000128         *ABS*   00000000 _end_sec_abs
 # SIMPLE-NEXT: 0000000000001048         .text   00000000 _start
 # SIMPLE-NEXT: 0000000000000120         .foo    00000000 begin_foo
 # SIMPLE-NEXT: 0000000000000128         .foo    00000000 end_foo
 # SIMPLE-NEXT: 0000000000000008         .foo    00000000 size_foo_1
 # SIMPLE-NEXT: 0000000000000008         *ABS*   00000000 size_foo_1_abs
 # SIMPLE-NEXT: 0000000000001000         .foo    00000000 begin_bar
 # SIMPLE-NEXT: 0000000000001004         .foo    00000000 end_bar
 # SIMPLE-NEXT: 0000000000000ee4         .foo    00000000 size_foo_2
 # SIMPLE-NEXT: 0000000000000ee4         *ABS*   00000000 size_foo_3
 # SIMPLE-NEXT: 0000000000001004         .eh_frame_hdr     00000000 __eh_frame_hdr_start
 # SIMPLE-NEXT: 0000000000001010         *ABS*             00000000 __eh_frame_hdr_start2
 # SIMPLE-NEXT: 0000000000001018         .eh_frame_hdr     00000000 __eh_frame_hdr_end
 # SIMPLE-NEXT: 0000000000001020         *ABS*             00000000 __eh_frame_hdr_end2
 
+# EMPTY:       00000000000000e8         *ABS*     00000000 .hidden _begin_sec
+# EMPTY-NEXT:  00000000000000e8         *ABS*     00000000 .hidden _end_sec
+# EMPTY-NEXT:  00000000000000e8         *ABS*     00000000 .hidden _end_sec_abs
+# EMPTY-NEXT:  0000000000000128         .text     00000000 _start
+# EMPTY-NEXT:  00000000000000e8         *ABS*     00000000 addr_of_aaa
+# EMPTY-NEXT:  0000000000000000         *ABS*     00000000 size_of_aaa
+# EMPTY-NEXT:  0000000000000001         *ABS*     00000000 align_of_aaa
+
 .global _start
 _start:
  nop
 
 .section .foo,"a"
  .quad 0
 
 .section .bar,"a"
  .long 0
 
 .section .dah,"ax",@progbits
  .cfi_startproc
  nop
  .cfi_endproc
 
 .global _begin_sec, _end_sec, _end_sec_abs