[ELF] Make SORT_INIT_PRIORITY support .ctors.N

[MaskRay]

Summary

Input sections .ctors/.ctors.N may go to either the output section .init_array or the output section .ctors:

• output .ctors: currently we sort them by name. This patch changes to sort by priority from high to low. If N in .ctors.N is in the form of %05u, there is no semantic difference. Actually GCC and Clang do use %05u. (In the test ctors_dtors_priority.s and Gold's test gold/testsuite/script_test_14.s, we can see %03u, but they are not really produced by compilers.)
• output .init_array: users can provide an input section description SORT_BY_INIT_PRIORITY(.init_array.* .ctors.*) to mix .init_array.* and .ctors.*. This can make .init_array.N and .ctors.(65535-N) interchangeable.

With this change, users can mix .ctors.N and .init_array.N in .init_array (PR44698 and PR48096) with linker scripts. As an example:

SECTIONS {
  .init_array : {
    *(SORT_BY_INIT_PRIORITY(.init_array.* .ctors.*))
    *(.init_array EXCLUDE_FILE (*crtbegin.o *crtbegin?.o *crtend.o *crtend?.o ) .ctors)
  }
} INSERT AFTER .fini_array;
SECTIONS {
  .fini_array : {
    *(SORT_BY_INIT_PRIORITY(.fini_array.* .dtors.*))
    *(.fini_array EXCLUDE_FILE (*crtbegin.o *crtbegin?.o *crtend.o *crtend?.o ) .dtors)
  }
} INSERT BEFORE .init_array;

[psmith]

Apologies for being so quiet recently. It looks like this is changing .ctors/.dtors away from SORT_BY_NAME when they aren't mixed with .init_array.

lld/ELF/OutputSections.cpp

477

I'm not sure this is right. As I understand it compCtors will only be called when not using a linker script.

In that case we'd have a separate .ctors and .dtors section to an existing .init_array section and in this case the rules for sorting ctors and dtors are different i.e. the default is sort by name (see comment above). It looks like this bit of code will change the default linker script to the equivalent of:

.ctors : { SORT_BY_INIT_PRIORITY (*(.ctors)) }

from:

.ctors : { SORT_BY_NAME (*(.ctors)) }

I think the old way was closer to BFD as that only changes to SORT_BY_INIT_PRIORITY if .ctors are placed in the .init_array OutputSection.

[MaskRay]

Good to hear from you:) Thanks for review!

For GNU ld's internal linker script, the effective part for sections is:

  .init_array    :
  {
    KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.*) SORT_BY_INIT_PRIORITY(.ctors.*)))
    KEEP (*(.init_array EXCLUDE_FILE (*crtbegin.o *crtbegin?.o *crtend.o *crtend?.o ) .ctors))
  }
  .ctors          :
  {
    KEEP (*crtbegin.o(.ctors))   /* Get a -1 sentinel from crtbegin*.o */
    KEEP (*crtbegin?.o(.ctors))
/* the sort-by-name pattern is ineffective due to the pattern in .init_array */
/* the body is essentially empty */
    KEEP (*crtend.o(.ctors) *crtend?.o(.ctors)) /* Get a 0 sentinel from crtend*.o */
  }

You are right that there is a semantic difference.

Clang emits .ctors.%05u and GCC seems to emit .ctors.%.5u. Both should work fine with either SORT (by name, i.e. string comparison, "100" < "5") and SORT_BY_INIT_PRIORITY (by priority). So the change should matter in practice. Note that .ctors.100 has already been converted to .init_array in GNU ld by priority while with the output section .ctors, they should be sorted by name. So I think this semantic change does not matter.

(GCC does not have any test for .ctors.N ; GNU ld only has tests for .ctors.N where N is in the %05u form. .ctors.101 exists in a gold test but it does not seem to match the practical case)

[MaskRay]

lld/ELF/OutputSections.cpp

477

The idea is: getPriority(a->name) > getPriority(b->name) is equivalent to a->name < b->name for .ctors.N sections where N is %05u

If the output section is .ctors, the order of input sections: .ctors, .ctors.00005, .ctors.00100
(This is tested by ctors_dtors_priority.s)

[psmith]

Will take another look tonight.For reference, I tried helping out someone last year with https://bugs.llvm.org/show_bug.cgi?id=44698 I think they had old objects, or a an old GCC on their system and it was mixing with a modern clang. Maybe worth a read through.

[MaskRay]

In D91187#2388190, @psmith wrote:

Will take another look tonight.For reference, I tried helping out someone last year with https://bugs.llvm.org/show_bug.cgi?id=44698 I think they had old objects, or a an old GCC on their system and it was mixing with a modern clang. Maybe worth a read through.

Thanks for the pointer. (I did recall we had another bug about .ctors (which motivated me to investigate the behaviors and observe several problems) but did not find the bug number..

With this patch, the user can provide a linker script fragment

SECTIONS {
  .init_array : {
    *(SORT_BY_INIT_PRIORITY(.init_array.* .ctors.*))
    *(.init_array EXCLUDE_FILE (*crtbegin.o *crtbegin?.o *crtend.o *crtend?.o ) .ctors)
  }
} INSERT AFTER .fini_array;
SECTIONS {
  .fini_array : {
    *(SORT_BY_INIT_PRIORITY(.fini_array.* .dtors.*))
    *(.fini_array EXCLUDE_FILE (*crtbegin.o *crtbegin?.o *crtend.o *crtend?.o ) .dtors)
  }
} INSERT BEFORE .init_array;

The use of INSERT [AFTER|BEFORE] is a bit of an abuse but in the absence of a better syntax (https://sourceware.org/bugzilla/show_bug.cgi?id=26404) this may be the best the user can achieve without providing a full script.

[MaskRay]

The original comment was wrong about point 2 and 3. Rewrite the comment.

[MaskRay]

Fix potential use after free

[psmith]

Thanks for updating the comments. If the lexical ordering is going to work out the same I don't have any objections.

lld/ELF/OutputSections.cpp

 }
 
 static bool isCrtend(StringRef s) {
   static std::regex re(R"((clang_rt\.)?crtend[ST]?(-.*)?\.o)");
   s = sys::path::filename(s);
   return std::regex_match(s.begin(), s.end(), re);
 }
 
-// .ctors and .dtors are sorted by this priority from highest to lowest.
+// .ctors and .dtors are sorted by this order:
 //
-//  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.
+// 1. .ctors/.dtors in crtbegin (which contains a sentinel value -1).
+// 2. The section is named ".ctors" or ".dtors" (priority: 65536).
+// 3. The section has an optional priority value in the form of ".ctors.N" or
+//    ".dtors.N" where N is a number in the form of %05u (priority: 65535-N).
+// 4. .ctors/.dtors in crtend (which contains a sentinel value 0).
+//
+// For 2 and 3, the sections are sorted by priority from high to low, e.g.
+// .ctors (65536), .ctors.00100 (65436), .ctors.00200 (65336).  In GNU ld's
+// internal linker scripts, the sorting is by string comparison which can
+// achieve the same goal given the optional priority values are of the same
+// length.
 //
 // 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.
 static bool compCtors(const InputSection *a, const InputSection *b) {
   bool beginA = isCrtbegin(a->file->getName());
   bool beginB = isCrtbegin(b->file->getName());
   if (beginA != beginB)
     return beginA;
   bool endA = isCrtend(a->file->getName());
   bool endB = isCrtend(b->file->getName());
   if (endA != endB)
     return endB;
-  StringRef x = a->name;
-  StringRef y = b->name;
-  assert(x.startswith(".ctors") || x.startswith(".dtors"));
-  assert(y.startswith(".ctors") || y.startswith(".dtors"));
-  x = x.substr(6);
-  y = y.substr(6);
-  return x < y;
+  return getPriority(a->name) > getPriority(b->name);
 }
 
 // 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.
 void OutputSection::sortCtorsDtors() {
   assert(sectionCommands.size() == 1);
   auto *isd = cast<InputSectionDescription>(sectionCommands[0]);
   llvm::stable_sort(isd->sections, compCtors);
 }
 
-// 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.
+// If an input string is in the form of "foo.N" where N is a number, return N
+// (65535-N if .ctors.N or .dtors.N). Otherwise, returns 65536, which is one
+// greater than the lowest priority.
 int elf::getPriority(StringRef s) {
   size_t pos = s.rfind('.');
   if (pos == StringRef::npos)
     return 65536;
-  int v;
-  if (!to_integer(s.substr(pos + 1), v, 10))
-    return 65536;
+  int v = 65536;
+  if (to_integer(s.substr(pos + 1), v, 10) &&
+      (pos == 6 && (s.startswith(".ctors") || s.startswith(".dtors"))))
+    v = 65535 - v;
   return v;
 }
 
 InputSection *elf::getFirstInputSection(const OutputSection *os) {
   for (BaseCommand *base : os->sectionCommands)
     if (auto *isd = dyn_cast<InputSectionDescription>(base))
       if (!isd->sections.empty())
         return isd->sections[0];

lld/test/ELF/linkerscript/sort-init.s

 # REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
-# RUN: echo "SECTIONS { .init_array : { *(SORT_BY_INIT_PRIORITY(.init_array.* foo*)) } }" > %t1.script
-# RUN: ld.lld --script %t1.script %t1.o -o %t2
-# RUN: llvm-objdump -s %t2 | FileCheck %s
+## Test SORT_BY_INIT_PRIORITY can be used to convert .ctors into .init_array
 
-# CHECK:      Contents of section .init_array:
-# CHECK-NEXT: 03020000 00060000 010405
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/asm -o %t.o
+# RUN: ld.lld -T %t/lds %t.o -o %t.out
+# RUN: llvm-readelf -x .init_array %t.out | FileCheck %s
 
+# CHECK:      Hex dump of section '.init_array':
+# CHECK-NEXT: 0x00000001 00010203 04050607
+
+#--- asm
 .globl _start
 _start:
   nop
 
 .section foo, "aw", @init_array
-  .byte 6
-.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 5
+
+.section .ctors.65435, "a"
   .byte 3
-.section .init_array, "aw", @init_array
+.section .init_array.100, "aw", @init_array
   .byte 4
+
+.section .init_array.7, "aw", @init_array
+  .byte 2
+.section .ctors.65529,"a"
+  .byte 1
+.section .init_array.5, "aw", @init_array
+  .byte 0
+
 .section .init_array, "aw", @init_array
-  .byte 5
+  .byte 6
+.section .ctors, "a"
+  .byte 7
+
+#--- lds
+SECTIONS {
+  .init_array : {
+    *(SORT_BY_INIT_PRIORITY(.init_array.* .ctors.*) SORT_BY_INIT_PRIORITY(foo*))
+    *(.init_array .ctors)
+  }
+}