From d0de3683ecb7e0484f298f8926ae9f97c51c5898 Mon Sep 17 00:00:00 2001
From: Pete Cooper <peter_cooper@apple.com>
Date: Fri, 5 Aug 2016 21:37:12 +0000
Subject: [PATCH] ExportTrie nodes need to be visisted in order.

The export trie was being emitted in the order the nodes were
added to the vector, but instead needs to be visited in the order
that the nodes are traversed.  This matches the behaviour of ld64.

llvm-svn: 277869
---
 .../MachO/MachONormalizedFileBinaryWriter.cpp      | 32 ++++++++++-
 lld/test/mach-o/export-trie-order.yaml             | 62 ++++++++++++++++++++++
 2 files changed, 92 insertions(+), 2 deletions(-)
 create mode 100644 lld/test/mach-o/export-trie-order.yaml

diff --git a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
index ed58d92..a0609a5 100644
--- a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
@@ -103,6 +103,9 @@ struct TrieNode {
 
   void addSymbol(const Export &entry, BumpPtrAllocator &allocator,
                  std::vector<TrieNode *> &allNodes);
+
+  void addOrderedNodes(const Export &entry,
+                       std::vector<TrieNode *> &allNodes);
   bool updateOffset(uint32_t &offset);
   void appendToByteBuffer(ByteBuffer &out);
 
@@ -115,6 +118,7 @@ private:
   StringRef                 _importedName;
   uint32_t                  _trieOffset;
   bool                      _hasExportInfo;
+  bool                      _ordered = false;
 };
 
 /// Utility class for writing a mach-o binary file given an in-memory
@@ -1289,6 +1293,24 @@ void TrieNode::addSymbol(const Export& entry,
   allNodes.push_back(newNode);
 }
 
+void TrieNode::addOrderedNodes(const Export& entry,
+                               std::vector<TrieNode*> &orderedNodes) {
+  if (!_ordered) {
+    orderedNodes.push_back(this);
+    _ordered = true;
+  }
+
+  StringRef partialStr = entry.name.drop_front(_cummulativeString.size());
+  for (TrieEdge &edge : _children) {
+    StringRef edgeStr = edge._subString;
+    if (partialStr.startswith(edgeStr)) {
+      // Already have matching edge, go down that path.
+      edge._child->addOrderedNodes(entry, orderedNodes);
+      return;
+    }
+  }
+}
+
 bool TrieNode::updateOffset(uint32_t& offset) {
   uint32_t nodeSize = 1; // Length when no export info
   if (_hasExportInfo) {
@@ -1394,20 +1416,26 @@ void MachOFileLayout::buildExportTrie() {
     rootNode->addSymbol(entry, allocator, allNodes);
   }
 
+  std::vector<TrieNode*> orderedNodes;
+  orderedNodes.reserve(allNodes.size());
+
+  for (const Export& entry : _file.exportInfo)
+    rootNode->addOrderedNodes(entry, orderedNodes);
+
   // Assign each node in the vector an offset in the trie stream, iterating
   // until all uleb128 sizes have stabilized.
   bool more;
   do {
     uint32_t offset = 0;
     more = false;
-    for (TrieNode* node : allNodes) {
+    for (TrieNode* node : orderedNodes) {
       if (node->updateOffset(offset))
         more = true;
     }
   } while (more);
 
   // Serialize trie to ByteBuffer.
-  for (TrieNode* node : allNodes) {
+  for (TrieNode* node : orderedNodes) {
     node->appendToByteBuffer(_exportTrie);
   }
   _exportTrie.align(_is64 ? 8 : 4);
diff --git a/lld/test/mach-o/export-trie-order.yaml b/lld/test/mach-o/export-trie-order.yaml
new file mode 100644
index 0000000..a11c998
--- /dev/null
+++ b/lld/test/mach-o/export-trie-order.yaml
@@ -0,0 +1,62 @@
+# RUN: lld -flavor darwin -arch i386 %s %p/Inputs/hello-world-x86.yaml -o %t
+# RUN: llvm-objdump -exports-trie %t | FileCheck %s
+#
+# Test that the export trie is emitted in order.
+#
+
+--- !mach-o
+arch:            x86
+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, 0x89, 0xE5, 0x83, 0xEC, 0x08, 0xE8, 0x00,
+                       0x00, 0x00, 0x00, 0x58, 0x8D, 0x80, 0x16, 0x00,
+                       0x00, 0x00, 0x89, 0x04, 0x24, 0xE8, 0xE6, 0xFF,
+                       0xFF, 0xFF, 0x31, 0xC0, 0x83, 0xC4, 0x08, 0x5D,
+                       0xC3 ]
+    relocations:
+      - offset:          0x00000016
+        type:            GENERIC_RELOC_VANILLA
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          1
+      - offset:          0x0000000E
+        scattered:       true
+        type:            GENERIC_RELOC_LOCAL_SECTDIFF
+        length:          2
+        pc-rel:          false
+        value:           0x00000021
+      - offset:          0x00000000
+        scattered:       true
+        type:            GENERIC_RELOC_PAIR
+        length:          2
+        pc-rel:          false
+        value:           0x0000000B
+  - segment:         __TEXT
+    section:         __cstring
+    type:            S_CSTRING_LITERALS
+    attributes:      [  ]
+    address:         0x0000000000000021
+    content:         [ 0x68, 0x65, 0x6C, 0x6C, 0x6F, 0x0A, 0x00 ]
+global-symbols:
+  - name:            _main
+    type:            N_SECT
+    scope:           [ N_EXT ]
+    sect:            1
+    value:           0x0000000000000000
+undefined-symbols:
+  - name:            _printf
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+...
+
+# CHECK: Exports trie:
+# CHECK-NEXT: __mh_execute_header
+# CHECK-NEXT: _main
-- 
2.7.4