[ELF] Change --shuffle-sections=<seed> to --shuffle-sections=<section-glob>=<seed>

[MaskRay]

Summary

--shuffle-sections=<seed> applies to all sections. The new
--shuffle-sections=<section-glob>=<seed> makes shuffling selective. To the
best of my knowledge, the option is only used as debugging, so just drop the
original form.

--shuffle-sections '.init_array*=-1' --shuffle-sections '.fini_array*=-1'.
reverses static constructors/destructors of the same priority.
Useful to detect some static initialization order fiasco.

--shuffle-sections '.data*=-1'
reverses .data* sections. Useful to detect unfunded pointer comparison results
of two unrelated objects.

If certain sections have an intrinsic order, the old form cannot be used.

[MaskRay]

add error tests

[jhenderson]

I've not got the time to review this whole change right now, but I've checked and it should be safe from our point of view to change the command-line option. An alternative non-breaking approach would be to treat a shuffle-sections argument without an equals sign as the old-style, but that might be unnecessary additional complexity.

lld/docs/ReleaseNotes.rst

33

I think this sounds better.

[MaskRay]

Rebase

Fix wording

[MaskRay]

fix wording

[jhenderson]

Pre-merge bots indicate there's another test using --shuffle-sections which needs updating.

lld/ELF/Driver.cpp

1154

It would probably be helpful if this error message included what was actually the option, in case they have multiple --shuffle-sections, to allow them to find the right one. Example:

error: --shuffle-sections=: expected <section_glob>=<seed>, but was "abcdef"

lld/ELF/Writer.cpp

1301–1303

Was wondering if there was a way to do this loop in a way using the existing built-in algorithms, but the best I've got is the following:

std::copy_if(sections.begin(), sections.end(), std::back_inserter(matched),
      [&](InputSectionBase *sec) { return patAndSeed.first.match(sec->name); });

which doesn't really seem any clearer to me.

lld/test/ELF/shuffle-sections.s

58

Perhaps also --shuffle-sections=a, (i.e. where the '=' is missing for the option value, but the string is non-empty).

[MaskRay]

rebase

address comments

[jhenderson]

lld/test/ELF/shuffle-sections.s

61

I think it would be a good idea to check the exact string here, to show we're not printing garbage. You can use FileCheck -D to easily do that without needing to duplicate this line per case.

[MaskRay]

check exact message

[jhenderson]

LGTM, thanks!

lld/ELF/Config.h

struct Configuration {
   bool optRemarksWithHotness;
   bool picThunk;
   bool pie;
   bool printGcSections;
   bool printIcfSections;
   bool relocatable;
   bool relrPackDynRelocs;
   bool saveTemps;
-  llvm::Optional<uint32_t> shuffleSectionSeed;
+  std::vector<std::pair<llvm::GlobPattern, uint32_t>> shuffleSections;
   bool singleRoRx;
   bool shared;
   bool symbolic;
   bool isStatic = false;
   bool sysvHash = false;
   bool target1Rel;
   bool trace;
   bool thinLTOEmitImportsFiles;

lld/ELF/Driver.cpp

static void readConfigs(opt::InputArgList &args) {
   config->printGcSections =
       args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false);
   config->printArchiveStats = args.getLastArgValue(OPT_print_archive_stats);
   config->printSymbolOrder =
       args.getLastArgValue(OPT_print_symbol_order);
   config->rpath = getRpath(args);
   config->relocatable = args.hasArg(OPT_relocatable);
   config->saveTemps = args.hasArg(OPT_save_temps);
-  if (args.hasArg(OPT_shuffle_sections))
-    config->shuffleSectionSeed = args::getInteger(args, OPT_shuffle_sections, 0);
   config->searchPaths = args::getStrings(args, OPT_library_path);
   config->sectionStartMap = getSectionStartMap(args);
   config->shared = args.hasArg(OPT_shared);
   config->singleRoRx = !args.hasFlag(OPT_rosegment, OPT_no_rosegment, true);
   config->soName = args.getLastArgValue(OPT_soname);
   config->sortSection = getSortSection(args);
   config->splitStackAdjustSize = args::getInteger(args, OPT_split_stack_adjust_size, 16384);
   config->strip = getStrip(args);
static void readConfigs(opt::InputArgList &args) {
 
   if (opt::Arg *arg = args.getLastArg(OPT_eb, OPT_el)) {
     if (arg->getOption().matches(OPT_eb))
       config->optEB = true;
     else
       config->optEL = true;
   }
 
+  for (opt::Arg *arg : args.filtered(OPT_shuffle_sections)) {
+    constexpr StringRef errPrefix = "--shuffle-sections=: ";
+    std::pair<StringRef, StringRef> kv = StringRef(arg->getValue()).split('=');
+    if (kv.first.empty() || kv.second.empty()) {
+      error(errPrefix + "expected <section_glob>=<seed>");
+      continue;
+    }
+    // Signed so that <section_glob>=-1 is allowed.
+    int64_t v;
+    if (!to_integer(kv.second, v))
+      error(errPrefix + "expected an integer, but got '" + kv.second + "'");
+    else if (Expected<GlobPattern> pat = GlobPattern::create(kv.first))
+      config->shuffleSections.emplace_back(std::move(*pat), uint32_t(v));
+    else
+      error(errPrefix + toString(pat.takeError()));
+  }
+
   for (opt::Arg *arg : args.filtered(OPT_z)) {
     std::pair<StringRef, StringRef> option =
         StringRef(arg->getValue()).split('=');
     if (option.first != "dead-reloc-in-nonalloc")
       continue;
     constexpr StringRef errPrefix = "-z dead-reloc-in-nonalloc=: ";
     std::pair<StringRef, StringRef> kv = option.second.split('=');
     if (kv.first.empty() || kv.second.empty()) {

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 -1, reverse input sections. If 0, use a random seed">;
+defm shuffle_sections: EEq<"shuffle-sections",
+  "Shuffle matched sections using the given seed before mapping them to the output sections. "
+  "If -1, reverse the section order. If 0, use a random seed">,
+  MetaVarName<"<section-glob>=<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

findOrphanPos(std::vector<BaseCommand *>::iterator b,
 
   while (i != e && shouldSkip(*i))
     ++i;
   return i;
 }
 
 // Adds random priorities to sections not already in the map.
 static void maybeShuffle(DenseMap<const InputSectionBase *, int> &order) {
-  if (!config->shuffleSectionSeed)
+  if (config->shuffleSections.empty())
     return;
 
-  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;
+  std::vector<InputSectionBase *> matched, sections = inputSections;
+  matched.reserve(sections.size());
+  for (const auto &patAndSeed : config->shuffleSections) {
+    matched.clear();
+    for (InputSectionBase *sec : sections)
+      if (patAndSeed.first.match(sec->name))
+        matched.push_back(sec);
+    const uint32_t seed = patAndSeed.second;
     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());
+      // If --shuffle-sections <section-glob>=-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(matched.begin(), matched.end());
     } else {
       std::mt19937 g(seed ? seed : std::random_device()());
-    llvm::shuffle(priorities.begin(), priorities.end(), g);
+      llvm::shuffle(matched.begin(), matched.end(), g);
+    }
+    size_t i = 0;
+    for (InputSectionBase *&sec : sections)
+      if (patAndSeed.first.match(sec->name))
+        sec = matched[i++];
   }
-  int prioIndex = 0;
-  for (InputSectionBase *sec : inputSections) {
-    if (order.try_emplace(sec, priorities[prioIndex]).second)
-      ++prioIndex;
+
+  // Existing priorities are < 0, so use priorities >= 0 for the missing
+  // sections.
+  int prio = 0;
+  for (InputSectionBase *sec : sections) {
+    if (order.try_emplace(sec, prio).second)
+      ++prio;
   }
 }
 
 // Builds section order for handling --symbol-ordering-file.
 static DenseMap<const InputSectionBase *, int> buildSectionOrder() {
   DenseMap<const InputSectionBase *, int> sectionOrder;
   // Use the rarely used option -call-graph-ordering-file to sort sections.
   if (!config->callGraphProfile.empty())

lld/docs/ReleaseNotes.rst

 ELF Improvements
 ----------------
 
 * ...
 
 Breaking changes
 ----------------
 
-* ...
+* ``--shuffle-sections=<seed>`` has been changed to ``--shuffle-sections=<section-glob>=<seed>``.
+  Specify ``*`` as ``<section-glob>`` to get the original behavior.
 
 COFF Improvements
 -----------------
 
 * ...
 
 MinGW Improvements
 ------------------

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 -1, reverse input sections. If 0, use a random seed.
+Shuffle matched sections using the given seed before mapping them to the output sections.
+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-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: 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-SAME: 04000b 06010a08 09070203 05
+# SHUFFLED-SAME: 080301 04050907 0b020a06 00
 
 # CHECK:      Hex dump of section '.fini_array'
 # CHECK-NEXT: 0x{{[0-9a-f]+}} ff
 # ORDERED-SAME:  000102 03040506 0708090a 0b
-# SHUFFLED-SAME: 090401 070b0003 080a0605 02
+# SHUFFLED-SAME: 0a0405 08070b02 03090006 01
 
 ## With a SECTIONS command, SHT_INIT_ARRAY prirotities are ignored.
 ## All .init_array* are shuffled together.
 # RUN: echo 'SECTIONS { \
 # RUN:   .init_array : { *(.init_array*) } \
 # RUN:   .fini_array : { *(.fini_array*) }}' > %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: 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-NEXT: 0x{{[0-9a-f]+}} 04000b06 010a0809 07ff0203 05
+# SHUFFLED2-NEXT: 0x{{[0-9a-f]+}} 08030104 0509070b 02ff0a06 00
 
 .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

lld/test/ELF/shuffle-sections.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
 
 # RUN: ld.lld %t.o -o %t.out
 # RUN: llvm-readelf -x .text %t.out | FileCheck %s
 # CHECK: Hex dump of section '.text':
 # CHECK-NEXT: 01020304
 
 ## --shuffle-sections= shuffles input sections.
-# RUN: ld.lld --shuffle-sections=1 %t.o -o %t1.out
+# RUN: ld.lld --shuffle-sections='*=1' %t.o -o %t1.out
 # RUN: llvm-readelf -x .text %t1.out | FileCheck %s --check-prefix=SHUFFLE1
 # SHUFFLE1: Hex dump of section '.text':
-# SHUFFLE1-NEXT: 0204cccc 0103
+# SHUFFLE1-NEXT: 0203cccc 0104
 
 ## Test that --shuffle-sections= can be used with --symbol-ordering-file
 # RUN: echo "foo" > %t_order.txt
 # RUN: echo "_start " >> %t_order.txt
 
-# RUN: ld.lld --symbol-ordering-file %t_order.txt --shuffle-sections=2 %t.o -o %t2.out
+# RUN: ld.lld --symbol-ordering-file %t_order.txt --shuffle-sections='*=2' %t.o -o %t2.out
 # RUN: llvm-readelf -x .text %t2.out | FileCheck %s --check-prefix=SHUFFLE2
 # SHUFFLE2: Hex dump of section '.text':
-# SHUFFLE2-NEXT: 02cccccc 010304
+# SHUFFLE2-NEXT: 02cccccc 010403
 
-# RUN: ld.lld --symbol-ordering-file %t_order.txt --shuffle-sections=3 %t.o -o %t3.out
+# 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=SHUFFLE3
+# 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: 02cccccc 040301
+# SHUFFLE-1-NEXT: 040302cc 01
+
+## .text does not change its order while .text.{foo,bar,zed} are reversed.
+# RUN: ld.lld --shuffle-sections '.text.*=-1' %t.o -o %t4.out
+# RUN: llvm-readelf -x .text %t4.out | FileCheck %s --check-prefix=SHUFFLE4
+# SHUFFLE4: Hex dump of section '.text':
+# SHUFFLE4-NEXT: 01040302
+
+## Reversing twice restores the original order.
+# RUN: ld.lld --shuffle-sections '.text.*=-1' --shuffle-sections '.text.*=-1' %t.o -o %t.out
+# RUN: llvm-readelf -x .text %t.out | FileCheck %s
 
 ## .text has an alignment of 4.
 .global _start
 _start:
   .byte 1
 
 .section .text.foo,"ax"
 .global foo
 foo:
   .byte 2
 
 .section .text.bar,"ax"
 .global bar
 bar:
   .byte 3
 
 .section .text.zed,"ax"
 .global zed
 zed:
   .byte 4