[ELF] Special case --shuffle-sections=-1 to reverse input sections

[MaskRay]

Summary

If the number of sections changes, which is common for re-links after
incremental updates, the section order may change drastically.

Special case -1 to reverse input sections. This is a stable transform.
The section order is more resilient to incremental updates. Usually the
code issue (e.g. Static Initialization Order Fiasco, assuming pointer
comparison result of two unrelated objects) is due to the relative order
between two problematic input files A and B. Checking the regular order
and the reversed order is sufficient.

[jhenderson]

lld/ELF/Writer.cpp

1305

lld/test/ELF/shuffle-sections.s

30

Do you need the --symbol-ordering-file option here? It seems like it's unrelated to testing whether -1 reverses the section order. If there's an interaction you want to test between the two, perhaps we should have a case with and a case without.

[peter.smith]

No fundamental objections, although I'm wondering if static constructor order is the main problem it would be better to do something specific. For example reversing the order of the constructors of the same priority while holding the remainder of the program constant. A smaller local change would help rule out other layout changes due to section order change.

Had an idle thought that it might be possible to do some kind of dependency check. For example trace the relocations from each static constructor and look for common read-write data sections. While not a guarantee of order-dependence it would be a good indicator that there may be some order dependence.

[MaskRay]

Thanks for the comments!

In D98445#2621570, @peter.smith wrote:

No fundamental objections, although I'm wondering if static constructor order is the main problem it would be better to do something specific. For example reversing the order of the constructors of the same priority while holding the remainder of the program constant. A smaller local change would help rule out other layout changes due to section order change.

Our internal system actually depends on .ctors/.dtors and hasn't migrated to .init_array/.fini_array yet ;-) Doing the migration has low priority, though.
I have thought about --shuffle-sections .init_array=-1 (<section-pattern>=<seed>) to reverse a specific set of sections.
If such an option exists, we may be able to drop our -fno-use-init-array and catch up the toolchain evolution of obsoleting .ctors/.dtors .
I do not know whether it is too specific.

In the meantime, I have filed a feature request on REVERSE(...) https://sourceware.org/bugzilla/show_bug.cgi?id=27565
If both REVERSE(...) and linker script extension (https://sourceware.org/bugzilla/show_bug.cgi?id=26404) are supported, we can actually do it with a linker script.

Had an idle thought that it might be possible to do some kind of dependency check. For example trace the relocations from each static constructor and look for common read-write data sections. While not a guarantee of order-dependence it would be a good indicator that there may be some order dependence.

Yes, some kind of dependency based checking may be useful to implement a bettern --warn-backrefs. Currently --warn-backrefs just catches problems which GNU ld/gold catch.
However, the check is performed with one particular input order so there may be other lurking problems. This is an interesting topic but I haven't thought much on it.

[MaskRay]

lld/test/ELF/shuffle-sections.s

30

The -1 test does not need it. I'll delete it.

--symbol-ordering-file has been tested by the lines above so the interaction does not need re-test.

[MaskRay]

address comments

[jhenderson]

The pre-merge checks appear to be failing with the test.

[MaskRay]

Fix test

[jhenderson]

Functionally, the change LGTM. Please wait for @peter.smith.

[peter.smith]

I'm fine with the change.

lld/ELF/Options.td

def opt_remarks_format: Separate<["--"], "opt-remarks-format">,
   HelpText<"The format used for serializing remarks (default: YAML)">;
 def save_temps: F<"save-temps">, HelpText<"Save intermediate LTO compilation results">;
 def lto_basic_block_sections: JJ<"lto-basic-block-sections=">,
   HelpText<"Enable basic block sections for LTO">;
 defm lto_unique_basic_block_section_names: BB<"lto-unique-basic-block-section-names",
     "Give unique names to every basic block section for LTO",
     "Do not give unique names to every basic block section for LTO (default)">;
 def shuffle_sections: JJ<"shuffle-sections=">, MetaVarName<"<seed>">,
-  HelpText<"Shuffle input sections using the given seed. If 0, use a random seed">;
+  HelpText<"Shuffle input sections using the given seed. "
+  "If -1, reverse the section order. If 0, use a random seed">;
 def thinlto_cache_dir: JJ<"thinlto-cache-dir=">,
   HelpText<"Path to ThinLTO cached object file directory">;
 defm thinlto_cache_policy: EEq<"thinlto-cache-policy", "Pruning policy for the ThinLTO cache">;
 def thinlto_emit_imports_files: FF<"thinlto-emit-imports-files">;
 def thinlto_index_only: FF<"thinlto-index-only">;
 def thinlto_index_only_eq: JJ<"thinlto-index-only=">;
 def thinlto_jobs: JJ<"thinlto-jobs=">,
   HelpText<"Number of ThinLTO jobs. Default to --threads=">;

lld/ELF/Writer.cpp

static void maybeShuffle(DenseMap<const InputSectionBase *, int> &order) {
 
   std::vector<int> priorities(inputSections.size() - order.size());
   // Existing priorities are < 0, so use priorities >= 0 for the missing
   // sections.
   int curPrio = 0;
   for (int &prio : priorities)
     prio = curPrio++;
   uint32_t seed = *config->shuffleSectionSeed;
+  if (seed == UINT32_MAX) {
+    // If --shuffle-sections=-1, reverse the section order. The section order is
+    // stable even if the number of sections changes. This is useful to catch
+    // issues like static initialization order fiasco reliably.
+    std::reverse(priorities.begin(), priorities.end());
+  } else {
     std::mt19937 g(seed ? seed : std::random_device()());
     llvm::shuffle(priorities.begin(), priorities.end(), g);
+  }
   int prioIndex = 0;
   for (InputSectionBase *sec : inputSections) {
     if (order.try_emplace(sec, priorities[prioIndex]).second)
       ++prioIndex;
   }
 }
 
 // Builds section order for handling --symbol-ordering-file.

lld/docs/ld.lld.1

 .Ar file .
 If multiple linker scripts are given, they are processed as if they
 were concatenated in the order they appeared on the command line.
 .It Fl -section-start Ns = Ns Ar section Ns = Ns Ar address
 Set address of section.
 .It Fl -shared , Fl -Bsharable
 Build a shared object.
 .It Fl -shuffle-sections Ns = Ns Ar seed
-Shuffle input sections using the given seed. If 0, use a random seed.
+Shuffle input sections using the given seed.
+If -1, reverse the section order. If 0, use a random seed.
 .It Fl -soname Ns = Ns Ar value , Fl h Ar value
 Set
 .Dv DT_SONAME
 to
 .Ar value .
 .It Fl -sort-common
 This option is ignored for GNU compatibility.
 .It Fl -sort-section Ns = Ns Ar value

lld/test/ELF/shuffle-sections.s

 # SHUFFLE2: Hex dump of section '.text':
 # SHUFFLE2-NEXT: 02cccccc 010304
 
 # RUN: ld.lld --symbol-ordering-file %t_order.txt --shuffle-sections=3 %t.o -o %t3.out
 # RUN: llvm-readelf -x .text %t3.out | FileCheck %s --check-prefix=SHUFFLE3
 # SHUFFLE3: Hex dump of section '.text':
 # SHUFFLE3-NEXT: 02cccccc 010403
 
+## As a special case, -1 reverses sections as a stable transform.
+# RUN: ld.lld --shuffle-sections=-1 %t.o -o %t-1.out
+# RUN: llvm-readelf -x .text %t-1.out | FileCheck %s --check-prefix=SHUFFLE-1
+# SHUFFLE-1: Hex dump of section '.text':
+# SHUFFLE-1-NEXT: 040302cc 01
+
 ## .text has an alignment of 4.
 .global _start
 _start:
   .byte 1
 
 .section .text.foo,"ax"
 .global foo
 foo: