[ELF] Linkerscript: Fix handling of empty sections

[evgeny777]

Summary

On some occasions output section listed in linker script may not be written to output file. This often happens if same linker script
is used to link many applications, some of them may, for example, contain EH frames or TLS sections and some may not.

In such case two problems arise:

1. All symbols listed in such sections will be added to symbol table incorrectly. Their section index will be invalid.
2. If some symbols refer address or size of an empty section then application will fail to link, because this section is not listed in OutputSections vector.

The ld and gold linkers use different approaches to address this problem:

• ld adds empty section symbols to preceding non-empty output section.
• gold makes those symbols absolute.

This patch uses gold-like way, converting all section-defined symbols to absolute. The address of an empty section is an address which it should have had in case it wasn't
empty.

[evgeny777]

Symbols defined in empty sections may be mentioned in relocation section, so it's necessary to copy at least GotIndex, before
converting Synthetic to Regular.

[ruiu]

I'm wondering why we need to remove empty output sections from output. I cannot think of a reason to not leave them as is except small file/virtual address space wastes for the section table slot for the empty section. Do we need to handle it as a special case?

ELF/LinkerScript.cpp

147

While you are here, can you change the function name so that it sounds like a predicate function? I'd suggest satisifiesConstraint but you may come up with a better name. I think "Check" is not a good name because it is not obvious whether it will return true or false on success.

[evgeny777]

I'm wondering why we need to remove empty output sections from output. I cannot think of a reason to not leave them as is except small file/virtual address space wastes for the section table slot for the empty section. Do we need to handle it as a special case?

Besides wasting some (small) space in ELF image I see two potential issues

a) What type and attributes will you assign for those empty sections? If you flag them with SHF_ALLOC you may end up having extra LOAD segments in ELF image. If you don't, then you'll have to treat them specially in assignAddresses.

b) All "special" sections listed in linker script (like .got, .eh_frame and so on) will have duplicates in ELF image, because they don't consist of input sections. I don't know if this is a real problem, but looks confusing at the very least (IMHO)

[evgeny777]

DIff updated. Changes:

• Rebased
• checkConstraint -> satisfiesConstraint
• Fixed bug in handling absolute symbols in empty sections

[ruiu]

ELF/LinkerScript.cpp

391

DefinedRegular<ELFT> *Regular = ...;

395–396

Is this uintX_t? Please use real types.

404

What does Sec->getVA() do? I think Sec is always empty here, so I'm not sure what this returns.

695

Please use real type instead of auto.

[evgeny777]

Addressed review comments.
Linker script processor sets VA for empty sections to allow calculating ALIGNOF, SIZEOF and ADDR for them

[ruiu]

ELF/LinkerScript.cpp

157–158

Now you can remove this.

404

Could you answer to this question?

[evgeny777]

ELF/LinkerScript.cpp

404

I thin I've already answered it:

Linker script processor sets VA for empty sections to allow calculating ALIGNOF, SIZEOF and ADDR for them

I want the following script to be processed without errors:

. = 0x10000;
.absolutely_empty_section : {}
sym1 = ADDR(.absolutely_empty_section); // Will return 0x10000
sym2 = SIZEOF(.absolutely_empty_section); // Will return 0
sym3 = ALIGNOF(.absolutely_empty_section); // Will return 1

Please also look at the test case

[evgeny777]

Rabased + addressed review comments

[evgeny777]

Diff updated. This one uses a different approach: for all empty sections it virtual output section with type SHT_NULL and SHF_EXCLUDE flag and adds it to OutputSections array. It is slightly more complex than previous ones, but after Rafael added section array "rotation" it looks to be the only way possible.

[• rafael]

ELF/LinkerScript.cpp

311

Sorry for being late in this review.

If you create these empty sections with

• the same flags as the one before it.
• alignment of 1
  
  you should be able to just leave these sections in the output and not worry about breaking any PT_LOAD, no?

That should make the patch simpler as you would not need to convert the symbols.

[evgeny777]

ELF/LinkerScript.cpp

311

you should be able to just leave these sections in the output and not worry about breaking any PT_LOAD, no?

I don't think so. You have special types of sections, like .got, .got.plt, .eh_frame_hdr, which are created after call to createSections(). Also empty section may be the very first one in linker script.

[evgeny777]

New one created
https://reviews.llvm.org/D24920

ELF/LinkerScript.cpp

case SortSectionPolicy::Name:
     return compareName;
   case SortSectionPolicy::Priority:
     return comparePriority;
   default:
     llvm_unreachable("unknown sort policy");
   }
 }
 
 static bool checkConstraint(uint64_t Flags, ConstraintKind Kind) {
   bool RO = (Kind == ConstraintKind::ReadOnly);
   bool RW = (Kind == ConstraintKind::ReadWrite);
   bool Writable = Flags & SHF_WRITE;
   return !(RO && Writable) && !(RW && !Writable);
 }
 
 template <class ELFT>
 static bool matchConstraints(ArrayRef<InputSectionBase<ELFT> *> Sections,
                              ConstraintKind Kind) {
   if (Kind == ConstraintKind::NoConstraint)
     return true;
   return llvm::all_of(Sections, [=](InputSectionData *Sec2) {
     auto *Sec = static_cast<InputSectionBase<ELFT> *>(Sec2);
     return checkConstraint(Sec->getSectionHdr()->sh_flags, Kind);
   });
 }
 
 // Compute and remember which sections the InputSectionDescription matches.
 template <class ELFT>
if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base1.get())) {
         continue;
       }
 
       for (const std::unique_ptr<BaseCommand> &Base : Cmd->Commands)
         if (auto *OutCmd = dyn_cast<SymbolAssignment>(Base.get()))
           if (shouldDefine<ELFT>(OutCmd))
             addSymbol<ELFT>(OutCmd);
 
-      if (V.empty())
+      if (V.empty()) {
+        OutputSectionBase<ELFT> *Empty = new OutputSectionBase<ELFT>(
+            Cmd->Name, SHT_NULL, SHF_ALLOC | SHF_EXCLUDE);
+        OutputSections->push_back(Empty);
+        Out<ELFT>::Pool.emplace_back(Empty);
         continue;
+      }
 
       for (InputSectionBase<ELFT> *Sec : V) {
         addSection(Factory, Sec, Cmd->Name);
         if (uint32_t Subalign = Cmd->SubalignExpr ? Cmd->SubalignExpr(0) : 0)
           Sec->Alignment = Subalign;
       }
     }
   }
 }
 
 template <class ELFT>
 void LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
   processCommands(Factory);
   // Add orphan sections.
   for (ObjectFile<ELFT> *F : Symtab<ELFT>::X->getObjectFiles())
     for (InputSectionBase<ELFT> *S : F->getSections())
       if (!isDiscarded(S) && !S->OutSec)
         addSection(Factory, S, getOutputSectionName(S));
 }
 
+// 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 = cast<DefinedSynthetic<ELFT>>(Body);
+  Symbol *S = Synthetic->symbol();
+  const OutputSectionBase<ELFT> *Section = Synthetic->Section;
+  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;
+  Regular->Value += Section->getVA();
+}
+
 // Sets value of a section-defined symbol. Two kinds of
 // symbols are processed: synthetic symbols, whose value
 // is an offset from beginning of section and regular
 // symbols whose value is absolute.
 template <class ELFT>
 static void assignSectionSymbol(SymbolAssignment *Cmd,
                                 OutputSectionBase<ELFT> *Sec,
                                 typename ELFT::uint Off) {
   if (!Cmd->Sym)
     return;
 
   if (auto *Body = dyn_cast<DefinedSynthetic<ELFT>>(Cmd->Sym)) {
     Body->Section = Sec;
     Body->Value = Cmd->Expression(Sec->getVA() + Off) - Sec->getVA();
+    if (Sec->getFlags() & SHF_EXCLUDE)
+      makeAbsolute<ELFT>(Body);
     return;
   }
   auto *Body = cast<DefinedRegular<ELFT>>(Cmd->Sym);
   Body->Value = Cmd->Expression(Sec->getVA() + Off);
 }
 
 template <class ELFT> void LinkerScript<ELFT>::output(InputSection<ELFT> *S) {
   if (!AlreadyOutputIS.insert(S).second)
     return;
   bool IsTbss =
       (CurOutSec->getFlags() & SHF_TLS) && CurOutSec->getType() == SHT_NOBITS;
 
   uintX_t Pos = IsTbss ? Dot + ThreadBssOffset : Dot;
   Pos = alignTo(Pos, S->Alignment);
   S->OutSecOff = Pos - CurOutSec->getVA();
   Pos += S->getSize();
 
   // Update output section size after adding each section. This is so that
   // SIZEOF works correctly in the case below:
   // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
   CurOutSec->setSize(Pos - CurOutSec->getVA());
 
   if (!IsTbss)
     Dot = Pos;
 }
 
 template <class ELFT> void LinkerScript<ELFT>::flush() {
   if (auto *OutSec = dyn_cast_or_null<OutputSection<ELFT>>(CurOutSec)) {
     for (InputSection<ELFT> *I : OutSec->Sections)
       output(I);
     AlreadyOutputOS.insert(CurOutSec);
   }
 }
 
 template <class ELFT>
 void LinkerScript<ELFT>::switchTo(OutputSectionBase<ELFT> *Sec) {
   if (CurOutSec == Sec)
     return;
   if (AlreadyOutputOS.count(Sec))
     return;
 
   flush();
   CurOutSec = Sec;
 
for (InputSectionData *ID : ICmd.Sections) {
     switchTo(IB->OutSec);
     if (auto *I = dyn_cast<InputSection<ELFT>>(IB))
       output(I);
     else if (AlreadyOutputOS.insert(CurOutSec).second)
       Dot += CurOutSec->getSize();
   }
 }
 
+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>
 static std::vector<OutputSectionBase<ELFT> *>
 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);
+
+  // If we get more than one section then try removing empty ones.
+  if (Ret.size() > 1)
+    removeIf(Ret, [](OutputSectionBase<ELFT> *Sec) {
+      return Sec->getFlags() & SHF_EXCLUDE;
+    });
+
   return Ret;
 }
 
 template <class ELFT>
 void LinkerScript<ELFT>::assignOffsets(OutputSectionCommand *Cmd) {
   std::vector<OutputSectionBase<ELFT> *> Sections =
       findSections(*Cmd, *OutputSections);
   if (Sections.empty())
for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     auto *Cmd = cast<OutputSectionCommand>(Base.get());
 
     if (Cmd->AddrExpr)
       Dot = Cmd->AddrExpr(Dot);
 
     assignOffsets(Cmd);
   }
 
+  // Remove all empty sections from output vector.
+  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);
   }
 
std::vector<PhdrEntry<ELFT>> LinkerScript<ELFT>::createPhdrs() {
 
   // Add output sections to program headers.
   PhdrEntry<ELFT> *Load = nullptr;
   uintX_t Flags = PF_R;
   for (OutputSectionBase<ELFT> *Sec : *OutputSections) {
     if (!(Sec->getFlags() & SHF_ALLOC))
       break;
 
+    // Skip empty sections. They shouldn't be written to final image.
+    if (Sec->getFlags() & SHF_EXCLUDE)
+      continue;
+
     std::vector<size_t> PhdrIds = getPhdrIndices(Sec->getName());
     if (!PhdrIds.empty()) {
       // Assign headers specified by linker script
       for (size_t Id : PhdrIds) {
         Ret[Id].add(Sec);
         if (Opt.PhdrsCommands[Id].Flags == UINT_MAX)
           Ret[Id].H.p_flags |= Sec->getPhdrFlags();
       }

 template <class ELFT> bool LinkerScript<ELFT>::hasPhdrsCommands() {
   return !Opt.PhdrsCommands.empty();
 }
 
 template <class ELFT>
 uint64_t LinkerScript<ELFT>::getOutputSectionAddress(StringRef Name) {
   for (OutputSectionBase<ELFT> *Sec : *OutputSections)
     if (Sec->getName() == Name)
       return Sec->getVA();
   error("undefined section " + Name);
   return 0;
 }
 
 template <class ELFT>
 uint64_t LinkerScript<ELFT>::getOutputSectionSize(StringRef Name) {
   for (OutputSectionBase<ELFT> *Sec : *OutputSections)
     if (Sec->getName() == Name)

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // This function adds linker-created Out<ELFT>::* sections.
   addPredefinedSections();
 
   std::stable_sort(OutputSections.begin(), OutputSections.end(),
                    compareSections<ELFT>);
 
   unsigned I = 1;
   for (OutputSectionBase<ELFT> *Sec : OutputSections) {
+    if (Sec->getFlags() & SHF_EXCLUDE)
+      continue;
+
     Sec->SectionIndex = I++;
     Sec->setSHName(Out<ELFT>::ShStrTab->addString(Sec->getName()));
   }
 
   // Finalizers fix each section's size.
   // .dynsym is finalized early since that may fill up .gnu.hash.
   if (Out<ELFT>::DynSymTab)
     Out<ELFT>::DynSymTab->finalize();
std::vector<PhdrEntry<ELFT>> Writer<ELFT>::createPhdrs() {
 
   Phdr TlsHdr(PT_TLS, PF_R);
   Phdr RelRo(PT_GNU_RELRO, PF_R);
   Phdr Note(PT_NOTE, PF_R);
   for (OutputSectionBase<ELFT> *Sec : OutputSections) {
     if (!(Sec->getFlags() & SHF_ALLOC))
       break;
 
+    // Skip empty sections. They shouldn't be written to final image.
+    if (Sec->getFlags() & SHF_EXCLUDE)
+      continue;
+
     // If we meet TLS section then we create TLS header
     // and put all TLS sections inside for futher use when
     // assign addresses.
     if (Sec->getFlags() & SHF_TLS)
       TlsHdr.add(Sec);
 
     if (!needsPtLoad(Sec))
       continue;

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:      0000000000000160         .foo    00000000 .hidden _end_sec
 # SIMPLE-NEXT: 0000000000000158         .foo    00000000 _begin_sec
 # SIMPLE-NEXT: 0000000000000160         *ABS*   00000000 _end_sec_abs
 # SIMPLE-NEXT: 0000000000001048         .text   00000000 _start
 # SIMPLE-NEXT: 0000000000000158         .foo    00000000 begin_foo
 # SIMPLE-NEXT: 0000000000000160         .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: 0000000000000eac         .foo    00000000 size_foo_2
 # SIMPLE-NEXT: 0000000000000eac         *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
 
+# ERROR: section '.eh_frame_hdr' supports only start and end symbols
+
+# EMPTY:       0000000000000120         *ABS*     00000000 .hidden _begin_sec
+# EMPTY-NEXT:  0000000000000120         *ABS*     00000000 .hidden _end_sec
+# EMPTY-NEXT:  0000000000000120         *ABS*     00000000 .hidden _end_sec_abs
+# EMPTY-NEXT:  0000000000000160         .text     00000000 _start
+# EMPTY-NEXT:  0000000000000120         *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