[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

1

This test passes for me without any code changes.

11

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
...

17

You do not need "unique" here it seems.

[MaskRay]

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

11

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

11

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;
 
+  // Sort input sections by priority using the list provided
+  // by --symbol-ordering-file.
+  auto sortBySectionOrder = [&]() {
+    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)
+    if (!script->hasSectionsCommand) {
+      sortBySectionOrder();
       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;
if (config->emachine == EM_PPC64 && name == ".toc") {
     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);
+  sortBySectionOrder();
 }
 
 // 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 --shuffle-sections=1 %t.o -o %t
+# RUN: llvm-readelf -x .init_array -x .fini_array %t | FileCheck %s
+# RUN: ld.lld --shuffle-sections=2 %t.o -o %t
+# RUN: llvm-readelf -x .init_array -x .fini_array %t | FileCheck %s
+# CHECK:      Hex dump of section '.init_array'
+# CHECK-NEXT: ff{{....}}
+# CHECK:      Hex dump of section '.fini_array'
+# CHECK-NEXT: {{....}}ff
+
+.section .init_array,"aw",@init_array,unique,0
+.byte 0
+.section .init_array,"aw",@init_array,unique,1
+.byte 1
+.section .init_array.1,"aw",@init_array,unique,2
+.byte 255
+
+.section .fini_array,"aw",@fini_array,unique,0
+.byte 0
+.section .fini_array,"aw",@fini_array,unique,1
+.byte 1
+.section .fini_array.1,"aw",@fini_array,unique,2
+.byte 255