[lld-macho] Use export trie instead of symtab when linking against dylibs

[int3]

Summary

This allows us to link against stripped dylibs. Moreover, it's simply
more correct: The symbol table includes symbols that the dylib uses but
doesn't export.

This temporarily regresses our ability to do lazy symbol binding because
dyld_stub_binder isn't in libSystem's export trie. Rather, it is in one
of the sub-libraries libSystem re-exports. (This doesn't affect our
tests since we are mocking out dyld_stub_binder there.) A follow-up diff
will address this by adding support for sub-libraries.

Depends on D79114.

[int3]

update

[smeenai]

LGTM

lld/MachO/ExportTrie.cpp

244

Can we make this a Twine & instead? Really, a const Twine & should have sufficed, but Twine.h doesn't mark the various operator+ as const even though concat is const :/ (I'll look into fixing that.)

The reason I'm suggesting a reference is that a twine doesn't own any memory, so that if you e.g. concatenate a Twine and a StringRef, the result Twine will store a pointer to that StringRef. Theoretically, in parse below, the compiler could convert the recursive call in the last iteration in the loop to a tail call, since you're passing the Twine by value (and it's small enough to be passed in directly on at least certain ABIs), and both Twine and StringRef have trivial destructors. In that case, the StringRef pointer stored by that Twine will become dangling (since it's pointing to a stack variable in a frame that'll be reused for the tail call). Taking the argument by reference should prevent this by preventing any possibility of a tail call.

(In practice, I don't think the tail call optimization will happen, but eh. I'm also not sure if the x86-64 ABI would let Twines be passed by value in practice either, but it's best to not assume the details of any particular ABI.)

250

Nit: I'd name this callback or something else more descriptive than f :)

lld/MachO/InputFiles.cpp

256

You should include the input file name in this error message.

lld/test/MachO/dylink.s

15

Might be worth running an nm or similar after to confirm that the symbol table is empty.

[smeenai]

lld/MachO/ExportTrie.cpp

244

Oh, wait, operator+ is a non-member function, so it doesn't need to be const. const Twine & should work here then, I think.

[int3]

lld/MachO/ExportTrie.cpp

244

oh good point about TCO! Never realized it could cause issues like that.

[int3]

address comments

[MaskRay]

lld/MachO/ExportTrie.h

40

clang-format may prefer const llvm::Twine & /*name*/

[int3]

format

[smeenai]

LGTM

lld/MachO/ExportTrie.h

 //===- ExportTrie.h ---------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_EXPORT_TRIE_H
 #define LLD_MACHO_EXPORT_TRIE_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
 
 #include <vector>
 
 namespace lld {
 namespace macho {
 
 struct TrieNode;
 class Symbol;
private:
   TrieNode *makeNode();
   void sortAndBuild(llvm::MutableArrayRef<const Symbol *> vec, TrieNode *node,
                     size_t lastPos, size_t pos);
 
   std::vector<const Symbol *> exported;
   std::vector<TrieNode *> nodes;
 };
 
+using TrieEntryCallback =
+    llvm::function_ref<void(const llvm::Twine & /*name*/, uint64_t /*flags*/)>;
+
+void parseTrie(const uint8_t *buf, size_t size, const TrieEntryCallback &);
+
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/ExportTrie.cpp

 // More documentation of the format can be found in
 // llvm/tools/obj2yaml/macho2yaml.cpp.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ExportTrie.h"
 #include "Symbols.h"
 
+#include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Support/LEB128.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace lld;
size_t TrieBuilder::build() {
   return offset;
 }
 
 void TrieBuilder::writeTo(uint8_t *buf) const {
   for (TrieNode *node : nodes)
     node->writeTo(buf);
 }
 
+namespace {
+
+// Parse a serialized trie and invoke a callback for each entry.
+class TrieParser {
+public:
+  TrieParser(const uint8_t *buf, size_t size, const TrieEntryCallback &callback)
+      : start(buf), end(start + size), callback(callback) {}
+
+  void parse(const uint8_t *buf, const Twine &cumulativeString);
+
+  void parse() { parse(start, ""); }
+
+  const uint8_t *start;
+  const uint8_t *end;
+  const TrieEntryCallback &callback;
+};
+
+} // namespace
+
+void TrieParser::parse(const uint8_t *buf, const Twine &cumulativeString) {
+  if (buf >= end)
+    fatal("Node offset points outside export section");
+
+  unsigned ulebSize;
+  uint64_t terminalSize = decodeULEB128(buf, &ulebSize);
+  buf += ulebSize;
+  uint64_t flags = 0;
+  size_t offset;
+  if (terminalSize != 0) {
+    flags = decodeULEB128(buf, &ulebSize);
+    callback(cumulativeString, flags);
+  }
+  buf += terminalSize;
+  uint8_t numEdges = *buf++;
+  for (uint8_t i = 0; i < numEdges; ++i) {
+    const char *cbuf = reinterpret_cast<const char *>(buf);
+    StringRef substring = StringRef(cbuf, strnlen(cbuf, end - buf));
+    buf += substring.size() + 1;
+    offset = decodeULEB128(buf, &ulebSize);
+    buf += ulebSize;
+    parse(start + offset, cumulativeString + substring);
+  }
+}
+
+void parseTrie(const uint8_t *buf, size_t size,
+               const TrieEntryCallback &callback) {
+  if (size == 0)
+    return;
+
+  TrieParser(buf, size, callback).parse();
+}
+
 } // namespace macho
 } // namespace lld

lld/MachO/InputFiles.cpp

 // and r_symbolnum is zero.
 //
 // Without the above differences, I think you can use your knowledge about ELF
 // and COFF for Mach-O.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputFiles.h"
+#include "ExportTrie.h"
 #include "InputSection.h"
 #include "OutputSection.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
if (const load_command *cmd = findCommand(hdr, LC_ID_DYLIB)) {
     auto *c = reinterpret_cast<const dylib_command *>(cmd);
     dylibName = reinterpret_cast<const char *>(cmd) + read32le(&c->dylib.name);
   } else {
     error("dylib " + getName() + " missing LC_ID_DYLIB load command");
     return;
   }
 
   // Initialize symbols.
-  if (const load_command *cmd = findCommand(hdr, LC_SYMTAB)) {
-    auto *c = reinterpret_cast<const symtab_command *>(cmd);
-    const char *strtab = reinterpret_cast<const char *>(buf + c->stroff);
-    ArrayRef<const nlist_64> nList(
-        reinterpret_cast<const nlist_64 *>(buf + c->symoff), c->nsyms);
-
-    symbols.reserve(c->nsyms);
-
-    for (const nlist_64 &sym : nList) {
-      StringRef name = strtab + sym.n_strx;
-      // TODO: Figure out what to do about undefined symbols: ignore or warn
-      // if unsatisfied? Also make sure we handle re-exported symbols
-      // correctly.
-      symbols.push_back(symtab->addDylib(name, this));
-    }
+  if (const load_command *cmd = findCommand(hdr, LC_DYLD_INFO_ONLY)) {
+    auto *c = reinterpret_cast<const dyld_info_command *>(cmd);
+    parseTrie(buf + c->export_off, c->export_size,
+              [&](const Twine &name, uint64_t flags) {
+                symbols.push_back(symtab->addDylib(saver.save(name), this));
+              });
+  } else {
+    error("LC_DYLD_INFO_ONLY not found in " + getName());
   }
 }
 
 DylibFile::DylibFile() : InputFile(DylibKind, MemoryBufferRef()) {}
 
 DylibFile *DylibFile::createLibSystemMock() {
   auto *file = make<DylibFile>();
   file->mb = MemoryBufferRef("", "/usr/lib/libSystem.B.dylib");

lld/test/CMakeLists.txt

configure_lit_site_cfg(
   ${CMAKE_CURRENT_SOURCE_DIR}/Unit/lit.cfg.py
   )
 
 set(LLD_TEST_DEPS lld)
 if (NOT LLD_BUILT_STANDALONE)
   list(APPEND LLD_TEST_DEPS
     FileCheck count llc llvm-ar llvm-as llvm-bcanalyzer llvm-config llvm-cvtres
     llvm-dis llvm-dwarfdump llvm-lib llvm-lipo llvm-mc llvm-nm llvm-objcopy
-    llvm-objdump llvm-pdbutil llvm-readelf llvm-readobj not obj2yaml opt
-    yaml2obj
+    llvm-objdump llvm-pdbutil llvm-readelf llvm-readobj llvm-strip not obj2yaml
+    opt yaml2obj
     )
 endif()
 
 if (LLVM_INCLUDE_TESTS)
   list(APPEND LLD_TEST_DEPS LLDUnitTests)
 endif()
 
 add_lit_testsuite(check-lld "Running lld test suite"

lld/test/MachO/dylink.s

 # REQUIRES: x86
 # RUN: mkdir -p %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %p/Inputs/libhello.s \
 # RUN:   -o %t/libhello.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %p/Inputs/libgoodbye.s \
 # RUN:   -o %t/libgoodbye.o
 # RUN: lld -flavor darwinnew -dylib -install_name \
 # RUN:   @executable_path/libhello.dylib %t/libhello.o -o %t/libhello.dylib
 # RUN: lld -flavor darwinnew -dylib -install_name \
 # RUN:   @executable_path/libgoodbye.dylib %t/libgoodbye.o -o %t/libgoodbye.dylib
+
+## Make sure we are using the export trie and not the symbol table when linking
+## against these dylibs.
+# RUN: llvm-strip %t/libhello.dylib
+# RUN: llvm-strip %t/libgoodbye.dylib
+# RUN: llvm-nm %t/libhello.dylib 2>&1 | FileCheck %s --check-prefix=NOSYM
+# RUN: llvm-nm %t/libgoodbye.dylib 2>&1 | FileCheck %s --check-prefix=NOSYM
+# NOSYM: no symbols
+
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/dylink.o
 # RUN: lld -flavor darwinnew -o %t/dylink -Z -L%t -lhello -lgoodbye %t/dylink.o
 # RUN: llvm-objdump --bind -d %t/dylink | FileCheck %s
 
 # CHECK: movq [[#%u, HELLO_OFF:]](%rip), %rsi
 # CHECK-NEXT: [[#%x, HELLO_RIP:]]:
 
 # CHECK: movq [[#%u, HELLO_ITS_ME_OFF:]](%rip), %rsi