[lld/mac] Fix nondeterminism in output section ordering

[thakis]

Summary

The two different thread_local_regular sections (__thread_data and
more_thread_data) had nondeterminstic ordering for two reasons:

1. https://reviews.llvm.org/D102972 changed concatOutputSections from MapVector to DenseMap, so when we iterate it to make output segments, we would add the two sections to the __DATA output segment in nondeterministic order.

2. The same change also moved the two stable_sort()s for segments and sections to sort(). Since sections with assigned priority (such as TLV data) have the same priority for all sections, this is incorrect -- we must use stable_sort() so that the initial (input-order-based) order remains.

As a side effect, we now (deterministically) put the common
section in front of bss (while previously we happened to
put it after it). (common and bss are both zerofill so
both have order INT_MAX, but common symbols are added to
inputSections before normal sections are collected.)

Makes lld/test/MachO/tlv.s and lld/test/MachO/tlv-dylib.s pass with
LLVM_ENABLE_EXPENSIVE_CHECKS=ON.

[tschuett]

lld/MachO/OutputSegment.cpp

143–145

Do you want to add a comment here: it has to be stable_sort ...

lld/MachO/Writer.cpp

82–85

Do you want to add a comment here: The order of bla has to be deterministic or whatever.

[thakis]

comments, tlv-dylib.s

[int3]

D'oh, sorry about that, and thanks for the fix!

[MaskRay]

Make lld/test/MachO/tlv.s,tlv-dylib.s pass with expensive tests

I think the subject needs to mention that it fixes a non-determinism, otherwise people might think this just adjusts fragile tests.

[thakis]

In D105054#2845535, @MaskRay wrote:

Make lld/test/MachO/tlv.s,tlv-dylib.s pass with expensive tests

I think the subject needs to mention that it fixes a non-determinism, otherwise people might think this just adjusts fragile tests.

Good point, done.

lld/MachO/OutputSegment.cpp

static int sectionOrder(OutputSection *osec) {
   // size to detect if a segment has zerofill sections, and if so it maps
   // the missing tail as zerofill.
   if (sectionType(osec->flags) == S_ZEROFILL)
     return std::numeric_limits<int>::max();
   return osec->inputOrder;
 }
 
 void OutputSegment::sortOutputSections() {
-  llvm::sort(sections, compareByOrder<OutputSection *>(sectionOrder));
+  // Must be stable_sort() to keep special sections such as
+  // S_THREAD_LOCAL_REGULAR in input order.
+  llvm::stable_sort(sections, compareByOrder<OutputSection *>(sectionOrder));
 }
 
 void macho::sortOutputSegments() {
+  // sort() instead of stable_sort() is fine because segmentOrder() is
+  // name-based and getOrCreateOutputSegment() makes there's only a single
+  // segment for every name.
   llvm::sort(outputSegments, compareByOrder<OutputSegment *>(segmentOrder));
 }
 
 static DenseMap<StringRef, OutputSegment *> nameToOutputSegment;
 std::vector<OutputSegment *> macho::outputSegments;
 
 OutputSegment *macho::getOrCreateOutputSegment(StringRef name) {
   OutputSegment *&segRef = nameToOutputSegment[name];

lld/MachO/Writer.cpp

public:
   SymtabSection *symtabSection = nullptr;
   IndirectSymtabSection *indirectSymtabSection = nullptr;
   CodeSignatureSection *codeSignatureSection = nullptr;
   DataInCodeSection *dataInCodeSection = nullptr;
   FunctionStartsSection *functionStartsSection = nullptr;
 
   LCUuid *uuidCommand = nullptr;
   OutputSegment *linkEditSegment = nullptr;
-  DenseMap<NamePair, ConcatOutputSection *> concatOutputSections;
+
+  // Output sections are added to output segments in iteration order
+  // of ConcatOutputSection, so must have deterministic iteration order.
+  MapVector<NamePair, ConcatOutputSection *> concatOutputSections;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo final : public LoadCommand {
 public:
   LCDyldInfo(RebaseSection *rebaseSection, BindingSection *bindingSection,
              WeakBindingSection *weakBindingSection,
              LazyBindingSection *lazyBindingSection,

lld/test/MachO/tlv-dylib.s

 # FLAGS-NEXT:   segname __DATA
 # FLAGS-NEXT:      addr
 # FLAGS-NEXT:      size 0x0000000000000008
 # FLAGS-NEXT:    offset 0
 # FLAGS-NEXT:     align 2^3 (8)
 # FLAGS-NEXT:    reloff 0
 # FLAGS-NEXT:    nreloc 0
 # FLAGS-NEXT:      type S_THREAD_LOCAL_ZEROFILL
-# FLAGS:       sectname __bss
+# FLAGS:       sectname __common
 # FLAGS-NEXT:   segname __DATA
 # FLAGS-NEXT:      addr
-# FLAGS-NEXT:      size 0x0000000000002000
+# FLAGS-NEXT:      size 0x0000000000004000
 # FLAGS-NEXT:    offset 0
-# FLAGS-NEXT:     align 2^0 (1)
+# FLAGS-NEXT:     align 2^14 (16384)
 # FLAGS-NEXT:    reloff 0
 # FLAGS-NEXT:    nreloc 0
 # FLAGS-NEXT:      type S_ZEROFILL
-# FLAGS:       sectname __common
+# FLAGS:       sectname __bss
 # FLAGS-NEXT:   segname __DATA
 # FLAGS-NEXT:      addr
-# FLAGS-NEXT:      size 0x0000000000004000
+# FLAGS-NEXT:      size 0x0000000000002000
 # FLAGS-NEXT:    offset 0
-# FLAGS-NEXT:     align 2^14 (16384)
+# FLAGS-NEXT:     align 2^0 (1)
 # FLAGS-NEXT:    reloff 0
 # FLAGS-NEXT:    nreloc 0
 # FLAGS-NEXT:      type S_ZEROFILL
 
 #--- libtlv.s
 .section __DATA,__thread_vars,thread_local_variables
 .globl _foo, _bar, _baz
 _foo: