[ELF] Shuffle .init_array/.fini_array with --shuffle-sections=

[MaskRay]

Summary

Useful for detecting static initialization order fiasco.

[grimar]

lld/test/ELF/shuffle-sections-init-fini.s

2

This test passes for me without any code changes.

12

I think this tests nothing. If you have the same result with different seeds, it probably means that
--shuffle-sections= does not work as expected.

What I think can be done to test it:
Run LLD without --shuffle-sections and then check that with this option, the result is just different.
e.g.:

# COMMON:       Hex dump of section '.init_array'
# WITHOUT-NEXT: ff0100
# WITH-NOT:     ff0100
...

18

You do not need "unique" here it seems.

[MaskRay]

lld/test/ELF/shuffle-sections-init-fini.s

12

Random funtion implementations are different across platforms. We may have to create a large number of sections to ensure the result will be different.

[MaskRay]

Improve tests

[respindola]

lld/ELF/Writer.cpp

1364

This will break code that uses init_priority, no?

I think we can only shuffle sections of equal priority.

[MaskRay]

lld/ELF/Writer.cpp

1364

Priorities are respected. Sections with the same priority can be shuffled.

See the test below, .init_array.1 is the first.

# CHECK:      Hex dump of section '.init_array'
# CHECK-NEXT: 0x{{[0-9a-f]+}} ff
# ORDERED-SAME: 000102 03040506 0708090a 0b
# SHUFFLED-NOT: 000102 03040506 0708090a 0b

[respindola]

lld/ELF/Writer.cpp

1364

Oh, I see. I was somehow reading a return after sortISDBySectionOrder, sorry.
What happens is that we first shuffle and then depend on functions like sortInitFini producing a valid order. Sounds reasonable.

What about the script->hasSectionsCommand case? Don't we have to skip sortISDBySectionOrder in when it is true?

[MaskRay]

Improve comment.
Add a test case for script->hasSectionsCommand case

[MaskRay]

lld/ELF/Writer.cpp

1364

I think we can also sort for the script->hasSectionsCommand case. All priorities are ignored. All SHT_INIT_ARRAY sections are shuffled together.

Added a test case.

[respindola]

lld/ELF/Writer.cpp

1364

Sounds reasonable. When using sections the linker script is probably what is responsible for producing the right order and we only sort inside each ISD.

This LGTM, but should probably also get approved by someone more recently active in lld.

[grimar]

LGTM

lld/test/ELF/shuffle-sections-init-fini.s

12

Yes, I think it is fine for now. As far I understand std::mt19937 (i.e. a random number engine based on Mersenne Twister algorithm) should produce the same result on different platforms, because implementation should base on the same algorithm.
As was said in the different thread, the problem is probably comes from std::shuffle, then if we one day get llvm's implementation of one,
it will be possible to simplify this test.
Anyways the number of sections you are adding in this test looks sufficient and not that large to me.

[MaskRay]

Update a comment

lld/ELF/Writer.cpp

sortISDBySectionOrder(InputSectionDescription *isd,
   for (InputSection *isec : makeArrayRef(unorderedSections).slice(insPt))
     isd->sections.push_back(isec);
 }
 
 static void sortSection(OutputSection *sec,
                         const DenseMap<const InputSectionBase *, int> &order) {
   StringRef name = sec->name;
 
+  // Never sort these.
+  if (name == ".init" || name == ".fini")
+    return;
+
+  // Sort input sections by priority using the list provided by
+  // --symbol-ordering-file or --shuffle-sections=. This is a least significant
+  // digit radix sort. The sections may be sorted stably again by a more
+  // significant key.
+  if (!order.empty())
+    for (BaseCommand *b : sec->sectionCommands)
+      if (auto *isd = dyn_cast<InputSectionDescription>(b))
+        sortISDBySectionOrder(isd, order);
+
   // Sort input sections by section name suffixes for
   // __attribute__((init_priority(N))).
   if (name == ".init_array" || name == ".fini_array") {
     if (!script->hasSectionsCommand)
       sec->sortInitFini();
     return;
   }
 
   // Sort input sections by the special rule for .ctors and .dtors.
   if (name == ".ctors" || name == ".dtors") {
     if (!script->hasSectionsCommand)
       sec->sortCtorsDtors();
     return;
   }
 
-  // Never sort these.
-  if (name == ".init" || name == ".fini")
-    return;
-
   // .toc is allocated just after .got and is accessed using GOT-relative
   // relocations. Object files compiled with small code model have an
   // addressable range of [.got, .got + 0xFFFC] for GOT-relative relocations.
   // To reduce the risk of relocation overflow, .toc contents are sorted so that
   // sections having smaller relocation offsets are at beginning of .toc
   if (config->emachine == EM_PPC64 && name == ".toc") {
     if (script->hasSectionsCommand)
       return;
     assert(sec->sectionCommands.size() == 1);
     auto *isd = cast<InputSectionDescription>(sec->sectionCommands[0]);
     llvm::stable_sort(isd->sections,
                       [](const InputSection *a, const InputSection *b) -> bool {
                         return a->file->ppc64SmallCodeModelTocRelocs &&
                                !b->file->ppc64SmallCodeModelTocRelocs;
                       });
     return;
   }
-
-  // Sort input sections by priority using the list provided
-  // by --symbol-ordering-file.
-  if (!order.empty())
-    for (BaseCommand *b : sec->sectionCommands)
-      if (auto *isd = dyn_cast<InputSectionDescription>(b))
-        sortISDBySectionOrder(isd, order);
 }
 
 // If no layout was provided by linker script, we want to apply default
 // sorting for special input sections. This also handles --symbol-ordering-file.
 template <class ELFT> void Writer<ELFT>::sortInputSections() {
   // Build the order once since it is expensive.
   DenseMap<const InputSectionBase *, int> order = buildSectionOrder();
   maybeShuffle(order);

lld/test/ELF/shuffle-sections-init-fini.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+
+# RUN: ld.lld %t.o -o %t
+# RUN: llvm-readelf -x .init -x .fini -x .init_array -x .fini_array %t | \
+# RUN:   FileCheck --check-prefixes=CHECK,ORDERED %s
+
+# RUN: ld.lld %t.o --shuffle-sections=1 -o %t1
+# RUN: llvm-readelf -x .init -x .fini -x .init_array -x .fini_array %t1 | \
+# RUN:   FileCheck --check-prefixes=CHECK,SHUFFLED %s
+
+## .init and .fini rely on a particular order, e.g. crti.o crtbegin.o crtend.o crtn.o
+## Don't shuffle them.
+# CHECK:      Hex dump of section '.init'
+# CHECK-NEXT: 00010203 04050607 08090a0b
+
+# CHECK:      Hex dump of section '.fini'
+# CHECK-NEXT: 00010203 04050607 08090a0b
+
+## SHT_INIT_ARRAY/SHT_FINI_ARRAY with explicit priorities are still ordered.
+# CHECK:      Hex dump of section '.init_array'
+# CHECK-NEXT: 0x{{[0-9a-f]+}} ff
+# ORDERED-SAME: 000102 03040506 0708090a 0b
+# SHUFFLED-NOT: 000102 03040506 0708090a 0b
+
+# CHECK:      Hex dump of section '.fini_array'
+# CHECK-NEXT: 0x{{[0-9a-f]+}} ff
+# ORDERED-SAME: 000102 03040506 0708090a 0b
+# SHUFFLED-NOT: 000102 03040506 0708090a 0b
+
+## With a SECTIONS command, SHT_INIT_ARRAY prirotities are ignored.
+## All .init_array* are shuffled together.
+# RUN: echo 'SECTIONS {}' > %t.script
+# RUN: ld.lld -T %t.script %t.o -o %t2
+# RUN: llvm-readelf -x .init -x .fini -x .init_array -x .fini_array %t2 | \
+# RUN:   FileCheck --check-prefixes=CHECK2,ORDERED2 %s
+# RUN: ld.lld -T %t.script %t.o --shuffle-sections=1 -o %t3
+# RUN: llvm-readelf -x .init -x .fini -x .init_array -x .fini_array %t3 | \
+# RUN:   FileCheck --check-prefixes=CHECK2,SHUFFLED2 %s
+
+# CHECK2:       Hex dump of section '.init_array'
+# ORDERED2-NEXT:  0x{{[0-9a-f]+}} 00010203 04050607 08090a0b ff
+# SHUFFLED2-NOT:  0x{{[0-9a-f]+}} 00010203 04050607 08090a0b ff
+
+## std::shuffle have different implementations.
+## When the number of input sections are large, it is almost guaranteed
+## to have an unordered result with --shuffle-sections=.
+.irp i,0,1,2,3,4,5,6,7,8,9,10,11
+  .section .init,"ax",@progbits,unique,\i
+  .byte \i
+  .section .fini,"ax",@progbits,unique,\i
+  .byte \i
+  .section .init_array,"aw",@init_array,unique,\i
+  .byte \i
+  .section .fini_array,"aw",@fini_array,unique,\i
+  .byte \i
+.endr
+
+.section .init_array.1,"aw",@init_array
+.byte 255
+.section .fini_array.1,"aw",@fini_array
+.byte 255