[ELF] Linkerscript: refactor sorting of special sections

[evgeny777]

Summary

Currently contents of .init_array, .fini_array, .ctors and .dtors is being sorted in Writer::finalizeSections, no matter if those sections are present in linker script or not.
This patch moves sorting of special sections to createSections(), which will allow defining symbols within such sections (required by FreeBSD and number of other projects)

Below is an example:

.init_array {
  __start = .;
  *(.init_array*)
  __end = .;
}

See this review:

https://reviews.llvm.org/D22683

[evgeny777]

Done in https://reviews.llvm.org/D22683

ELF/LinkerScript.cpp

static bool compareAlignment(InputSectionBase<ELFT> *A,
                              InputSectionBase<ELFT> *B) {
   // ">" is not a mistake. Larger alignments are placed before smaller
   // alignments in order to reduce the amount of padding necessary.
   // This is compatible with GNU.
   return A->Alignment > B->Alignment;
 }
 
 template <class ELFT>
+static bool comparePriority(InputSectionBase<ELFT> *A,
+                            InputSectionBase<ELFT> *B) {
+  return getPriority(A->getSectionName()) < getPriority(B->getSectionName());
+}
+
+template <class ELFT>
 static std::function<bool(InputSectionBase<ELFT> *, InputSectionBase<ELFT> *)>
 getComparator(SortKind K) {
   if (K == SortByName)
     return compareName<ELFT>;
   return compareAlignment<ELFT>;
 }
 
 template <class ELFT>
for (auto &P : getSectionMap()) {
 
     if (Cmd->SortInner)
       std::stable_sort(Sections.begin(), Sections.end(),
                        getComparator<ELFT>(Cmd->SortInner));
     if (Cmd->SortOuter)
       std::stable_sort(Sections.begin(), Sections.end(),
                        getComparator<ELFT>(Cmd->SortOuter));
 
+    if (OutputName == ".init_array" || OutputName == ".fini_array")
+      std::stable_sort(Sections.begin(), Sections.end(), comparePriority<ELFT>);
+    else if (OutputName == ".ctors" || OutputName == ".dtors")
+      std::stable_sort(Sections.begin(), Sections.end(), compCtors<ELFT>);
+
     for (InputSectionBase<ELFT> *S : Sections)
       addSection(Factory, *OutputSections, S, OutputName);
   }
 
   // Add all other input sections, which are not listed in script.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
        Symtab<ELFT>::X->getObjectFiles())
     for (InputSectionBase<ELFT> *S : F->getSections())

ELF/OutputSections.h

 
 private:
   Key createKey(InputSectionBase<ELFT> *C, StringRef OutsecName);
 
   llvm::SmallDenseMap<Key, OutputSectionBase<ELFT> *> Map;
   std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> OwningSections;
 };
 
+int getPriority(StringRef S);
+template <class ELFT>
+bool compCtors(const InputSectionBase<ELFT> *A,
+               const InputSectionBase<ELFT> *B);
+
 template <class ELFT> BuildIdSection<ELFT> *Out<ELFT>::BuildId;
 template <class ELFT> DynamicSection<ELFT> *Out<ELFT>::Dynamic;
 template <class ELFT> EhFrameHeader<ELFT> *Out<ELFT>::EhFrameHdr;
 template <class ELFT> EhOutputSection<ELFT> *Out<ELFT>::EhFrame;
 template <class ELFT> GnuHashTableSection<ELFT> *Out<ELFT>::GnuHashTab;
 template <class ELFT> GotPltSection<ELFT> *Out<ELFT>::GotPlt;
 template <class ELFT> GotSection<ELFT> *Out<ELFT>::Got;
 template <class ELFT> HashTableSection<ELFT> *Out<ELFT>::HashTab;

ELF/OutputSections.cpp

void OutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   Sections.push_back(S);
   S->OutSec = this;
   this->updateAlignment(S->Alignment);
 }
 
 // If an input string is in the form of "foo.N" where N is a number,
 // return N. Otherwise, returns 65536, which is one greater than the
 // lowest priority.
-static int getPriority(StringRef S) {
+int elf::getPriority(StringRef S) {
   size_t Pos = S.rfind('.');
   if (Pos == StringRef::npos)
     return 65536;
   int V;
   if (S.substr(Pos + 1).getAsInteger(10, V))
     return 65536;
   return V;
 }

 //
 //  4. The section was contained in crtend, which contains an end marker.
 //
 // In an ideal world, we don't need this function because .init_array and
 // .ctors are duplicate features (and .init_array is newer.) However, there
 // are too many real-world use cases of .ctors, so we had no choice to
 // support that with this rather ad-hoc semantics.
 template <class ELFT>
-static bool compCtors(const InputSection<ELFT> *A,
-                      const InputSection<ELFT> *B) {
+bool elf::compCtors(const InputSectionBase<ELFT> *A,
+                    const InputSectionBase<ELFT> *B) {
   bool BeginA = isCrtbegin(A->getFile()->getName());
   bool BeginB = isCrtbegin(B->getFile()->getName());
   if (BeginA != BeginB)
     return BeginA;
   bool EndA = isCrtend(A->getFile()->getName());
   bool EndB = isCrtend(B->getFile()->getName());
   if (EndA != EndB)
     return EndB;

 template class BuildIdHexstring<ELF32BE>;
 template class BuildIdHexstring<ELF64LE>;
 template class BuildIdHexstring<ELF64BE>;
 
 template class OutputSectionFactory<ELF32LE>;
 template class OutputSectionFactory<ELF32BE>;
 template class OutputSectionFactory<ELF64LE>;
 template class OutputSectionFactory<ELF64BE>;
+
+template bool compCtors<ELF32LE>(const InputSectionBase<ELF32LE> *,
+                                 const InputSectionBase<ELF32LE> *);
+template bool compCtors<ELF32BE>(const InputSectionBase<ELF32BE> *,
+                                 const InputSectionBase<ELF32BE> *);
+template bool compCtors<ELF64LE>(const InputSectionBase<ELF64LE> *,
+                                 const InputSectionBase<ELF64LE> *);
+template bool compCtors<ELF64BE>(const InputSectionBase<ELF64BE> *,
+                                 const InputSectionBase<ELF64BE> *);
 }
 }

ELF/Writer.cpp

for (InputSectionBase<ELFT> *C : F->getSections()) {
       OutputSectionBase<ELFT> *Sec;
       bool IsNew;
       std::tie(Sec, IsNew) = Factory.create(C, getOutputSectionName(C));
       if (IsNew)
         OutputSections.push_back(Sec);
       Sec->addSection(C);
     }
   }
+
+  // Sort section contents for __attribute__((init_priority(N)).
+  sortInitFini(
+      Factory.lookup(".init_array", SHT_INIT_ARRAY, SHF_WRITE | SHF_ALLOC));
+  sortInitFini(
+      Factory.lookup(".fini_array", SHT_FINI_ARRAY, SHF_WRITE | SHF_ALLOC));
+  sortCtorsDtors(Factory.lookup(".ctors", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC));
+  sortCtorsDtors(Factory.lookup(".dtors", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC));
 }
 
 // Create output section objects and add them to OutputSections.
 template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // Create output sections for input object file sections.
   std::vector<OutputSectionBase<ELFT> *> RegularSections = OutputSections;
 
   // If we have a .opd section (used under PPC64 for function descriptors),
   // store a pointer to it here so that we can use it later when processing
   // relocations.
   Out<ELFT>::Opd = Factory.lookup(".opd", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC);
 
   Out<ELFT>::Dynamic->PreInitArraySec = Factory.lookup(
       ".preinit_array", SHT_PREINIT_ARRAY, SHF_WRITE | SHF_ALLOC);
   Out<ELFT>::Dynamic->InitArraySec =
       Factory.lookup(".init_array", SHT_INIT_ARRAY, SHF_WRITE | SHF_ALLOC);
   Out<ELFT>::Dynamic->FiniArraySec =
       Factory.lookup(".fini_array", SHT_FINI_ARRAY, SHF_WRITE | SHF_ALLOC);
 
-  // Sort section contents for __attribute__((init_priority(N)).
-  sortInitFini(Out<ELFT>::Dynamic->InitArraySec);
-  sortInitFini(Out<ELFT>::Dynamic->FiniArraySec);
-  sortCtorsDtors(Factory.lookup(".ctors", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC));
-  sortCtorsDtors(Factory.lookup(".dtors", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC));
-
   // The linker needs to define SECNAME_start, SECNAME_end and SECNAME_stop
   // symbols for sections, so that the runtime can get the start and end
   // addresses of each section by section name. Add such symbols.
   if (!Config->Relocatable) {
     addStartEndSymbols();
     for (OutputSectionBase<ELFT> *Sec : RegularSections)
       addStartStopSymbols(Sec);
   }

test/ELF/linkerscript/linkerscript-ctors-dtors.s

+// RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1
+// RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux \
+// RUN:   %p/../Inputs/ctors_dtors_priority1.s -o %t-crtbegin.o
+// RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux \
+// RUN:   %p/../Inputs/ctors_dtors_priority2.s -o %t2
+// RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux \
+// RUN:   %p/../Inputs/ctors_dtors_priority3.s -o %t-crtend.o
+// RUN: echo "SECTIONS {.ctors : {*(.ctors*)} \
+// RUN:                 .dtors : {*(.dtors*)} }" > %t.script
+// RUN: ld.lld %t1 %t2 %t-crtend.o %t-crtbegin.o --script %t.script -o %t.exe
+// RUN: llvm-objdump -s %t.exe | FileCheck %s
+// REQUIRES: x86
+
+.globl _start
+_start:
+  nop
+
+.section .ctors, "aw", @progbits
+  .byte 1
+.section .ctors.100, "aw", @progbits
+  .byte 2
+.section .ctors.005, "aw", @progbits
+  .byte 3
+.section .ctors, "aw", @progbits
+  .byte 4
+.section .ctors, "aw", @progbits
+  .byte 5
+
+.section .dtors, "aw", @progbits
+  .byte 0x11
+.section .dtors.100, "aw", @progbits
+  .byte 0x12
+.section .dtors.005, "aw", @progbits
+  .byte 0x13
+.section .dtors, "aw", @progbits
+  .byte 0x14
+.section .dtors, "aw", @progbits
+  .byte 0x15
+
+// CHECK:      Contents of section .ctors:
+// CHECK-NEXT: a1010405 b10302c1
+// CHECK:      Contents of section .dtors:
+// CHECK-NEXT: a2111415 b21312c2

test/ELF/linkerscript/linkerscript-init-fini.s

+// RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+// RUN: echo "SECTIONS {.init_array : {*(.init_array*)} \
+// RUN:                 .fini_array : {*(.fini_array*)} }" > %t.script
+// RUN: ld.lld %t --script %t.script -o %t.exe
+// RUN: llvm-objdump -s %t.exe | FileCheck %s
+// REQUIRES: x86
+
+.globl _start
+_start:
+  nop
+
+.section .init_array, "aw", @init_array
+  .align 8
+  .byte 1
+.section .init_array.100, "aw", @init_array
+  .long 2
+.section .init_array.5, "aw", @init_array
+  .byte 3
+.section .init_array, "aw", @init_array
+  .byte 4
+.section .init_array, "aw", @init_array
+  .byte 5
+
+.section .fini_array, "aw", @fini_array
+  .align 8
+  .byte 0x11
+.section .fini_array.100, "aw", @fini_array
+  .long 0x12
+.section .fini_array.5, "aw", @fini_array
+  .byte 0x13
+.section .fini_array, "aw", @fini_array
+  .byte 0x14
+.section .fini_array, "aw", @fini_array
+  .byte 0x15
+
+// CHECK:      Contents of section .init_array:
+// CHECK-NEXT: 03020000 00000000 010405
+// CHECK:      Contents of section .fini_array:
+// CHECK-NEXT: 13120000 00000000 111415