[mach-o] Sort GOT entries by name to make links reproducible

The GOT slots were being laid out in a random order by the GOTPass which
caused randomness in the output file.

Note: With this change lld now bootstraps on darwin.  That is:
1) link lld using system linker to make lld.1
2) link lld using lld.1 to make lld.2
3) link lld using lld.2 to make lld.3
Now lld.2 and lld.3 are identical.

llvm-svn: 221831

2 files changed, 152 insertions, 5 deletions

diff --git a/lld/lib/ReaderWriter/MachO/GOTPass.cpp b/lld/lib/ReaderWriter/MachO/GOTPass.cpp
index b86160efc24..b5381115c01 100644
--- a/lld/lib/ReaderWriter/MachO/GOTPass.cpp
+++ b/lld/lib/ReaderWriter/MachO/GOTPass.cpp
@@ -52,8 +52,8 @@ namespace mach_o {
 //
 class GOTEntryAtom : public SimpleDefinedAtom {
 public:
-  GOTEntryAtom(const File &file, bool is64) 
-    : SimpleDefinedAtom(file), _is64(is64) { }
+  GOTEntryAtom(const File &file, bool is64, StringRef name)
+    : SimpleDefinedAtom(file), _is64(is64), _name(name) { }
 
   ContentType contentType() const override {
     return DefinedAtom::typeGOT;
@@ -77,8 +77,13 @@ public:
     return llvm::makeArrayRef(zeros, size());
   }
 
+  StringRef slotName() const {
+    return _name;
+  }
+
 private:
   const bool _is64;
+  StringRef _name;
 };
 
 
@@ -116,9 +121,17 @@ private:
       }
     }
 
-    // add all created GOT Atoms to master file
+    // Sort and add all created GOT Atoms to master file
+    std::vector<const GOTEntryAtom *> entries;
+    entries.reserve(_targetToGOT.size());
     for (auto &it : _targetToGOT)
-      mergedFile->addAtom(*it.second);
+      entries.push_back(it.second);
+    std::sort(entries.begin(), entries.end(),
+              [](const GOTEntryAtom *left, const GOTEntryAtom *right) {
+      return (left->slotName().compare(right->slotName()) < 0);
+    });
+    for (const GOTEntryAtom *slot : entries)
+      mergedFile->addAtom(*slot);
   }
 
   bool shouldReplaceTargetWithGOTAtom(const Atom *target, bool canBypassGOT) {
@@ -142,7 +155,7 @@ private:
     auto pos = _targetToGOT.find(target);
     if (pos == _targetToGOT.end()) {
       GOTEntryAtom *gotEntry = new (_file.allocator()) 
-                                        GOTEntryAtom(_file, _context.is64Bit());
+          GOTEntryAtom(_file, _context.is64Bit(), target->name());
       _targetToGOT[target] = gotEntry;
       const ArchHandler::ReferenceInfo &nlInfo = _archHandler.stubInfo().
                                                 nonLazyPointerReferenceToBinder;
diff --git a/lld/test/mach-o/got-order.yaml b/lld/test/mach-o/got-order.yaml
new file mode 100644
index 00000000000..fbbc4e0397f
--- /dev/null
+++ b/lld/test/mach-o/got-order.yaml
@@ -0,0 +1,134 @@
+# RUN: lld -flavor darwin -arch x86_64  %s -o %t %p/Inputs/libSystem.yaml
+# RUN: llvm-objdump -bind %t | FileCheck %s
+#
+# Test that GOT slots are sorted by name
+#
+
+--- !mach-o
+arch:            x86_64
+file-type:       MH_OBJECT
+flags:           [ MH_SUBSECTIONS_VIA_SYMBOLS ]
+sections:        
+  - segment:         __TEXT
+    section:         __text
+    type:            S_REGULAR
+    attributes:      [ S_ATTR_PURE_INSTRUCTIONS, S_ATTR_SOME_INSTRUCTIONS ]
+    address:         0x0000000000000000
+    content:         [ 0x55, 0x48, 0x89, 0xE5, 0x48, 0x8B, 0x0D, 0x00, 
+                       0x00, 0x00, 0x00, 0x48, 0x8B, 0x05, 0x00, 0x00, 
+                       0x00, 0x00, 0x8B, 0x00, 0x03, 0x01, 0x48, 0x8B, 
+                       0x0D, 0x00, 0x00, 0x00, 0x00, 0x03, 0x01, 0x5D, 
+                       0xC3 ]
+    relocations:     
+      - offset:          0x00000019
+        type:            X86_64_RELOC_GOT_LOAD
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          2
+      - offset:          0x0000000E
+        type:            X86_64_RELOC_GOT_LOAD
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          1
+      - offset:          0x00000007
+        type:            X86_64_RELOC_GOT_LOAD
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          3
+global-symbols:  
+  - name:            _func
+    type:            N_SECT
+    scope:           [ N_EXT ]
+    sect:            1
+    value:           0x0000000000000000
+undefined-symbols: 
+  - name:            _aaa
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+  - name:            _fff
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+  - name:            _zzz
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+    
+--- !mach-o
+arch:            x86_64
+file-type:       MH_OBJECT
+flags:           [ MH_SUBSECTIONS_VIA_SYMBOLS ]
+sections:        
+  - segment:         __TEXT
+    section:         __text
+    type:            S_REGULAR
+    attributes:      [ S_ATTR_PURE_INSTRUCTIONS, S_ATTR_SOME_INSTRUCTIONS ]
+    address:         0x0000000000000000
+    content:         [ 0x55, 0x48, 0x89, 0xE5, 0x48, 0x8B, 0x0D, 0x00, 
+                       0x00, 0x00, 0x00, 0x48, 0x8B, 0x05, 0x00, 0x00, 
+                       0x00, 0x00, 0x8B, 0x00, 0x03, 0x01, 0x48, 0x8B, 
+                       0x0D, 0x00, 0x00, 0x00, 0x00, 0x03, 0x01, 0x5D, 
+                       0xC3 ]
+    relocations:     
+      - offset:          0x00000019
+        type:            X86_64_RELOC_GOT_LOAD
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          2
+      - offset:          0x0000000E
+        type:            X86_64_RELOC_GOT_LOAD
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          1
+      - offset:          0x00000007
+        type:            X86_64_RELOC_GOT_LOAD
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          3
+global-symbols:  
+  - name:            _main
+    type:            N_SECT
+    scope:           [ N_EXT ]
+    sect:            1
+    value:           0x0000000000000000
+undefined-symbols: 
+  - name:            _bar
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+  - name:            _foo
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+  - name:            _zazzle
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+
+--- !mach-o
+arch:            x86_64
+file-type:       MH_DYLIB
+install-name:    /usr/lib/libfoobar.dylib
+exports:
+  - name:            _bar
+  - name:            _zazzle
+  - name:            _foo
+  - name:            _aaa
+  - name:            _fff
+  - name:            _zzz
+...
+
+
+# CHECK:	    __DATA   __got  {{[0-9a-zA-Z _]+}} pointer   0 libfoobar     _aaa
+# CHECK-NEXT:	__DATA   __got  {{[0-9a-zA-Z _]+}} pointer   0 libfoobar     _bar
+# CHECK-NEXT:	__DATA   __got  {{[0-9a-zA-Z _]+}} pointer   0 libfoobar     _fff
+# CHECK-NEXT:	__DATA   __got  {{[0-9a-zA-Z _]+}} pointer   0 libfoobar     _foo
+# CHECK-NEXT:	__DATA   __got  {{[0-9a-zA-Z _]+}} pointer   0 libfoobar     _zazzle
+# CHECK-NEXT:	__DATA   __got  {{[0-9a-zA-Z _]+}} pointer   0 libfoobar     _zzz