ELF: Implement the correct semantics of .[cd]tors.

[ruiu]

Summary

As I noted in the comment, the sorting order of .[cd]tors are
different from .{init,fini}_array's.

[davide]

Some comments.

ELF/OutputSections.cpp

805

Can you name '3' instead of using the magic number?

838

Drive by comment: not a huge fan of X and Y as variable names. Sure, their scope is narrow but if you can come up with something more self-explicative, it would be better.

845

It is not obvious to me why you need stable sorting. Do you mind adding a comment?

[silvas]

Can you post your test scripts that you used to verify correct behavior?

[Bigcheese]

ELF/OutputSections.cpp

800

You also need to check for crtend. Its .ctors sections need to go after other .ctors.N sections.

test/ELF/ctors_dtors_priority.s

39

This should be:

1, 4, 5, 3, 2

.ctors is evaluated from the end to the start.

[ruiu]

• Added a test for the crtbegin.o rule.

ELF/OutputSections.cpp

805

We can name it SuffixLen or something like that, but it is probably too narrow. Added a comment instead.

838

I rather prefer this way. I actually tried to name NameA and NameB, but X and Y grows on me as I modified this code many times before sending for the code review.

845

Added a comment to the function for init/fini.

[Bigcheese]

ELF/OutputSections.cpp

805

3 is pretty obvious here, I can't think of a name that would provide any clarification. The function has a comment stating what the regex is.

[ruiu]

• Address Michael's comments.
• Added a test for crtend.

[atanasyan]

GNU ld 2.22 has the following default linker script for .ctors/.dtors sections. I am sure that other versions have the same declarations.

.ctors          :
{
  KEEP (*crtbegin.o(.ctors))
  KEEP (*crtbegin?.o(.ctors))
  /* We don't want to include the .ctor section from
     the crtend.o file until after the sorted ctors.
     The .ctor section from the crtend file contains the
     end of ctors marker and it must be last */
  KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .ctors))
  KEEP (*(SORT(.ctors.*)))
  KEEP (*(.ctors))
}
.dtors          :
{
  KEEP (*crtbegin.o(.dtors))
  KEEP (*crtbegin?.o(.dtors))
  KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .dtors))
  KEEP (*(SORT(.dtors.*)))
  KEEP (*(.dtors))
}

So the order should be follow:

1. .ctors section from *crtbegin.o
2. .ctors section from *crtbegin?.o
3. .ctors sections from other object files except *crtend.o and *crtend?.o
4. .ctors.* from any files sorted by priority
5. .ctors sections from *crtend.o and *crtend?.o

As far as I can see now .ctors/.dtors sections from the crtend.o go first.

[ruiu]

• Address Simon's comment.

[ruiu]

Tried to produce the same result as the linker script. Can you take a look?

[atanasyan]

LGTM Thanks.

[Bigcheese]

Fixes the original testcase and lgtm.

[ruiu]

Committed as r260620.

ELF/OutputSections.h

 public:
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rel Elf_Rel;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rela Elf_Rela;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
   OutputSection(StringRef Name, uint32_t sh_type, uintX_t sh_flags);
   void addSection(InputSectionBase<ELFT> *C) override;
-  void sortByPriority();
+  void sortInitFini();
+  void sortCtorsDtors();
   void writeTo(uint8_t *Buf) override;
 
 private:
+  void reassignOffsets();
   std::vector<InputSection<ELFT> *> Sections;
 };
 
 template <class ELFT>
 class MergeOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename OutputSectionBase<ELFT>::uintX_t uintX_t;
 
   bool shouldTailMerge() const;

ELF/OutputSections.cpp

static int getPriority(StringRef S) {
   if (Pos == StringRef::npos)
     return 65536;
   int V;
   if (S.substr(Pos + 1).getAsInteger(10, V))
     return 65536;
   return V;
 }
 
+// This function is called after we sort input sections
+// to update their offsets.
+template <class ELFT> void OutputSection<ELFT>::reassignOffsets() {
+  uintX_t Off = 0;
+  for (InputSection<ELFT> *S : Sections) {
+    Off = alignTo(Off, S->getAlign());
+    S->OutSecOff = Off;
+    Off += S->getSize();
+  }
+  this->Header.sh_size = Off;
+}
+
 // Sorts input sections by section name suffixes, so that .foo.N comes
 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
+// We want to keep the original order if the priorities are the same
+// because the compiler keeps the original initialization order in a
+// translation unit and we need to respect that.
 // For more detail, read the section of the GCC's manual about init_priority.
-template <class ELFT> void OutputSection<ELFT>::sortByPriority() {
+template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
   // Sort sections by priority.
   typedef std::pair<int, InputSection<ELFT> *> Pair;
   auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
 
   std::vector<Pair> V;
   for (InputSection<ELFT> *S : Sections)
     V.push_back({getPriority(S->getSectionName()), S});
   std::stable_sort(V.begin(), V.end(), Comp);
   Sections.clear();
   for (Pair &P : V)
     Sections.push_back(P.second);
+  reassignOffsets();
+}
 
-  // Reassign section addresses.
-  uintX_t Off = 0;
-  for (InputSection<ELFT> *S : Sections) {
-    Off = alignTo(Off, S->getAlign());
-    S->OutSecOff = Off;
-    Off += S->getSize();
-  }
-  this->Header.sh_size = Off;
+// Returns true if S matches /Filename.?\.o$/.
+static bool isCrtBeginEnd(StringRef S, StringRef Filename) {
+  if (!S.endswith(".o"))
+    return false;
+  S = S.drop_back(2);
+  if (S.endswith(Filename))
+    return true;
+  return !S.empty() && S.drop_back(1).endswith(Filename);
+
+static bool isCrtbegin(StringRef S) { return isCrtBeginEnd(S, "crtbegin"); }
+static bool isCrtend(StringRef S) { return isCrtBeginEnd(S, "crtend"); }
+
+// .ctors and .dtors are sorted by this priority from highest to lowest.
+//
+//  1. The section was contained in crtbegin (crtbegin contains
+//     some sentinel value in its .ctors and .dtors so that the runtime
+//     can find the beginning of the sections.)
+//
+//  2. The section has an optional priority value in the form of ".ctors.N"
+//     or ".dtors.N" where N is a number. Unlike .{init,fini}_array,
+//     they are compared as string rather than number.
+//
+//  3. The section is just ".ctors" or ".dtors".
+//
+//  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 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;
+  StringRef X = A->getSectionName();
+  StringRef Y = B->getSectionName();
+  assert(X.startswith(".ctors") || X.startswith(".dtors"));
+  assert(Y.startswith(".ctors") || Y.startswith(".dtors"));
+  X = X.substr(6);
+  Y = Y.substr(6);
+  if (X.empty() || Y.empty())
+    return X.empty();
+  return X < Y;
+}
+
+// Sorts input sections by the special rules for .ctors and .dtors.
+// Unfortunately, the rules are different from the one for .{init,fini}_array.
+// Read the comment above.
+template <class ELFT> void OutputSection<ELFT>::sortCtorsDtors() {
+  std::stable_sort(Sections.begin(), Sections.end(), compCtors<ELFT>);
+  reassignOffsets();
 }
 
 // Returns a VA which a relocatin RI refers to. Used only for local symbols.
 // For non-local symbols, use SymbolBody::getVA instead.
 template <class ELFT, bool IsRela>
 typename ELFFile<ELFT>::uintX_t
 elf2::getLocalRelTarget(const ObjectFile<ELFT> &File,
                         const Elf_Rel_Impl<ELFT, IsRela> &RI,

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::addReservedSymbols() {
   // break programs that uses "end" as a regular symbol.
   if (SymbolBody *B = Symtab.find("end"))
     if (B->isUndefined())
       Symtab.addAbsolute("end", ElfSym<ELFT>::End);
 }
 
 // Sort input sections by section name suffixes for
 // __attribute__((init_priority(N))).
-template <class ELFT> static void sortByPriority(OutputSectionBase<ELFT> *S) {
+template <class ELFT> static void sortInitFini(OutputSectionBase<ELFT> *S) {
   if (S)
-    reinterpret_cast<OutputSection<ELFT> *>(S)->sortByPriority();
+    reinterpret_cast<OutputSection<ELFT> *>(S)->sortInitFini();
+}
+
+// Sort input sections by the special rule for .ctors and .dtors.
+template <class ELFT> static void sortCtorsDtors(OutputSectionBase<ELFT> *S) {
+  if (S)
+    reinterpret_cast<OutputSection<ELFT> *>(S)->sortCtorsDtors();
 }
 
 // Create output section objects and add them to OutputSections.
 template <class ELFT> bool Writer<ELFT>::createSections() {
   OutputSections.push_back(Out<ELFT>::ElfHeader);
   OutputSections.push_back(Out<ELFT>::ProgramHeaders);
 
   // Add .interp first because some loaders want to see that section
template <class ELFT> bool Writer<ELFT>::createSections() {
   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)).
-  sortByPriority(Out<ELFT>::Dynamic->InitArraySec);
-  sortByPriority(Out<ELFT>::Dynamic->FiniArraySec);
-  sortByPriority(Factory.lookup(".ctors", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC));
-  sortByPriority(Factory.lookup(".dtors", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC));
+  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.
   addStartEndSymbols();
   for (OutputSectionBase<ELFT> *Sec : RegularSections)
     addStartStopSymbols(Sec);
 

test/ELF/Inputs/ctors_dtors_priority1.s

+.section .ctors, "aw", @progbits
+  .byte 0xA1
+
+.section .dtors, "aw", @progbits
+  .byte 0xA2

test/ELF/Inputs/ctors_dtors_priority2.s

+.section .ctors, "aw", @progbits
+  .byte 0xB1
+
+.section .dtors, "aw", @progbits
+  .byte 0xB2

test/ELF/Inputs/ctors_dtors_priority3.s

+.section .ctors, "aw", @progbits
+  .byte 0xC1
+
+.section .dtors, "aw", @progbits
+  .byte 0xC2

test/ELF/ctors_dtors_priority.s

-// RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
-// RUN: ld.lld %t -o %t.exe
+// 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: ld.lld %t1 %t2 %t-crtend.o %t-crtbegin.o -o %t.exe
 // RUN: llvm-objdump -s %t.exe | FileCheck %s
 // REQUIRES: x86
 
 .globl _start
 _start:
   nop
 
 .section .ctors, "aw", @progbits
-  .align 8
   .byte 1
 .section .ctors.100, "aw", @progbits
-  .long 2
-.section .ctors.5, "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
-  .align 8
   .byte 0x11
 .section .dtors.100, "aw", @progbits
-  .long 0x12
-.section .dtors.5, "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: 03020000 00000000 010405
+// CHECK-NEXT: a1b10104 050302c1
 // CHECK:      Contents of section .dtors:
-// CHECK-NEXT: 13120000 00000000 111415
+// CHECK-NEXT: a2b21114 151312c2