[lld-macho] Add support for creating and reading reexported dylibs

[int3]

Summary

Mach-O dylibs can re-export other dylibs as sub-libraries, meaning that the
symbols in those sub-libraries will be available under the umbrella
library's namespace.

Supporting this unblocks the linking of real programs, since many core
system functions are only available as sub-libraries of libSystem.

Depends on D79211.

[smeenai]

lld/MachO/Driver.cpp

120

This seems pretty inefficient in a bunch of ways in that we're iterating over the entire input file list (only a small number of which will be dylibs) multiple times (once for each -sub_library option). I don't know how bad it'll end up being in practice though, and there's a bunch of straightforward ways to make it better if need be, so I guess it's okay for now.

178

Nit: It's more conventional to write loops like this using args.filtered, e.g. https://github.com/llvm/llvm-project/blob/eb7d32e46fe184fdfcb52e0a25973e713047e305/llvm/tools/llvm-objcopy/CopyConfig.cpp#L647-L648

lld/MachO/InputFiles.cpp

131

Do you envision this being used in other places? If not, I'd just inline the loop in the one place it's being used right now; I know @ruiu hasn't been a fan of higher-order functions in the past.

285

Is it an error if a library has this flag set but has no re-exports? (I don't think it's terribly important to implement; just curious.)

312

Hmm. This isn't correct in that @executable_path is supposed to refer to the path of the exectuable that'll be loading this library (which we have no way of knowing right now). @loader_path would be the path of the library that's triggering the load.

Where are you seeing @executable_path be used for re-exports? Hmm, is it from the install name of sub-libraries getting copied over to the re-export load commands? Not sure what the best way to handle that is ... I'd be curious what ld64 does. One idea that springs to mind is to see if the current dylib's install name also begins with @executable_path/, and if so, compute the path of the other dylib relative to the current dylib. (As in, if your current dylib's install name is @executable_path/libfoo.dylib and the one you're re-exporting is @executable_path/../lib/libbar.dylib, it follows that the re-exported dylib should live in ../lib relative to the current dylib. On the other hand, if you flipped that around, the current dylib would have no way of knowing which subdirectory of its parent the re-exported dylib is supposed to live in...)

lld/MachO/Options.td

26

What about -reexport-lx and -reexport_library foo? Those seem to be the more modern options.

[int3]

lld/MachO/Driver.cpp

120

yup, this is definitely quadratic, but I figured input file lists + sub_library options would probably be relatively small

lld/MachO/InputFiles.cpp

131

No plans to use it in other places yet; can inline for now

285

yup! That's why I was always setting it prior to this diff. IIRC dyld would complain

312

Ah, yeah I misunderstood what @executable_path was supposed to represent...

is it from the install name of sub-libraries getting copied over to the re-export load commands?

yup

I'd be curious what ld64 does

I think it loads sub-libraries after parsing the entire command line. I guess our equivalent would be putting the executable path in the Config object, though I'm a bit wary of bloating Config...

Might be easier to just have the test use absolute paths for now and punt on implementing this till later

lld/MachO/Options.td

26

I just wanted to implement enough sub-library creation functionality to test our ability to read them. I think we can punt full support for sub-library creation till later

[int3]

address comments

[smeenai]

LGTM with the unused function removed.

lld/MachO/InputFiles.cpp

311

Same here.

lld/MachO/InputFiles.h

85

This is unused now, right?

lld/MachO/Options.td

26

Sounds good.

[int3]

lld/MachO/InputFiles.h

85

whoops, good catch

[int3]

address comments

lld/MachO/Config.h

 
 namespace lld {
 namespace macho {
 
 class Symbol;
 
 struct Configuration {
   Symbol *entry;
-  llvm::MachO::HeaderFileType outputType;
+  bool hasReexports = false;
   llvm::StringRef installName;
   llvm::StringRef outputFile;
+  llvm::MachO::HeaderFileType outputType;
   std::vector<llvm::StringRef> searchPaths;
 };
 
 extern Configuration *config;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/Driver.cpp

 #include "lld/Common/Version.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/BinaryFormat/Magic.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Option/Option.h"
 #include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Path.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
 Configuration *lld::macho::config;
static void addFile(StringRef path) {
   case file_magic::macho_dynamically_linked_shared_lib:
     inputFiles.push_back(make<DylibFile>(mbref));
     break;
   default:
     error(path + ": unhandled file type");
   }
 }
 
+// We expect sub-library names of the form "libfoo", which will match a dylib
+// with a path of .*/libfoo.dylib.
+static bool markSubLibrary(StringRef searchName) {
+  for (InputFile *file : inputFiles) {
+    if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
+      StringRef filename = path::filename(dylibFile->getName());
+      if (filename.consume_front(searchName) && filename == ".dylib") {
+        dylibFile->reexport = true;
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
 bool macho::link(llvm::ArrayRef<const char *> argsArr, bool canExitEarly,
                  raw_ostream &stdoutOS, raw_ostream &stderrOS) {
   lld::stdoutOS = &stdoutOS;
   lld::stderrOS = &stderrOS;
 
   stderrOS.enable_colors(stderrOS.has_colors());
   // TODO: Set up error handler properly, e.g. the errorLimitExceededMsg
 
case OPT_INPUT:
       break;
     case OPT_l:
       if (Optional<std::string> path = findDylib(arg->getValue()))
         addFile(*path);
       break;
     }
   }
 
+  // Now that all dylibs have been loaded, search for those that should be
+  // re-exported.
+  for (opt::Arg *arg : args) {
+    if (arg->getOption().getID() == OPT_sub_library) {
+      config->hasReexports = true;
+      StringRef searchName = arg->getValue();
+      if (!markSubLibrary(searchName)) {
+        error("-sub_library " + searchName +
+              " does not match a supplied dylib");
+      }
+    }
+  }
+
   // dyld requires us to load libSystem. Since we may run tests on non-OSX
   // systems which do not have libSystem, we mock it out here.
   // TODO: Replace this with a stub tbd file once we have TAPI support.
   if (StringRef(getenv("LLD_IN_TEST")) == "1" &&
       config->outputType == MH_EXECUTE) {
     inputFiles.push_back(DylibFile::createLibSystemMock());
   }
 

lld/MachO/InputFiles.h

 public:
   explicit ObjFile(MemoryBufferRef mb);
   static bool classof(const InputFile *f) { return f->kind() == ObjKind; }
 };
 
 // .dylib file
 class DylibFile : public InputFile {
 public:
-  explicit DylibFile(MemoryBufferRef mb);
+  // Mach-O dylibs can re-export other dylibs as sub-libraries, meaning that the
+  // symbols in those sub-libraries will be available under the umbrella
+  // library's namespace. Those sub-libraries can also have their own
+  // re-exports. When loading a re-exported dylib, `umbrella` should be set to
+  // the root dylib to ensure symbols in the child library are correctly bound
+  // to the root. On the other hand, if a dylib is being directly loaded
+  // (through an -lfoo flag), then `umbrella` should be a nullptr.
+  explicit DylibFile(MemoryBufferRef mb, DylibFile *umbrella = nullptr);
   static bool classof(const InputFile *f) { return f->kind() == DylibKind; }
 
   // Do not use this constructor!! This is meant only for createLibSystemMock(),
   // but it cannot be made private as we call it via make().
   DylibFile();
   static DylibFile *createLibSystemMock();
 
   StringRef dylibName;
   uint64_t ordinal = 0; // Ordinal numbering starts from 1, so 0 is a sentinel
+  bool reexport = false;
+  std::vector<DylibFile *> reexported;
+
+private:
+  // Expand special path prefixes like @executable_path/.
+  StringRef expandPath(StringRef path);
 };
 
 extern std::vector<InputFile *> inputFiles;
 
 llvm::Optional<MemoryBufferRef> readFile(StringRef path);
 
 } // namespace macho
 
 std::string toString(const macho::InputFile *file);
 } // namespace lld
 
 #endif

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 "Config.h"
 #include "ExportTrie.h"
 #include "InputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Path.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::support::endian;
+using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
 std::vector<InputFile *> macho::inputFiles;
 
 // Open a given file path and return it as a memory-mapped file.
 Optional<MemoryBufferRef> macho::readFile(StringRef path) {
   // Open a file.
for (uint32_t i = 0, n = hdr->ncmds; i < n; ++i) {
     auto *cmd = reinterpret_cast<const load_command *>(p);
     if (cmd->cmd == type)
       return cmd;
     p += cmd->cmdsize;
   }
   return nullptr;
 }
 
+template <class T, class F>
+static const load_command *forEachCommand(const mach_header_64 *hdr,
+                                          uint32_t type, F callback) {
+  const uint8_t *p =
+      reinterpret_cast<const uint8_t *>(hdr) + sizeof(mach_header_64);
+
+  for (uint32_t i = 0, n = hdr->ncmds; i < n; ++i) {
+    auto *cmd = reinterpret_cast<const load_command *>(p);
+    if (cmd->cmd == type)
+      callback(reinterpret_cast<const T *>(cmd));
+    p += cmd->cmdsize;
+  }
+  return nullptr;
+}
+
 std::vector<InputSection *>
 InputFile::parseSections(ArrayRef<section_64> sections) {
   std::vector<InputSection *> ret;
   ret.reserve(sections.size());
 
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
 
   for (const section_64 &sec : sections) {
if (!sections.empty()) {
     auto it = sections.begin();
     for (const section_64 &sec : objSections) {
       parseRelocations(sec, (*it)->relocs);
       ++it;
     }
   }
 }
 
-DylibFile::DylibFile(MemoryBufferRef mb) : InputFile(DylibKind, mb) {
+DylibFile::DylibFile(MemoryBufferRef mb, DylibFile *umbrella)
+    : InputFile(DylibKind, mb) {
+  if (umbrella == nullptr)
+    umbrella = this;
+
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   auto *hdr = reinterpret_cast<const mach_header_64 *>(mb.getBufferStart());
 
   // Initialize dylibName.
   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_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));
+                symbols.push_back(symtab->addDylib(saver.save(name), umbrella));
               });
   } else {
     error("LC_DYLD_INFO_ONLY not found");
+    return;
   }
+
+  if (hdr->flags & MH_NO_REEXPORTED_DYLIBS)
+    return;
+
+  forEachCommand<dylib_command>(
+      hdr, LC_REEXPORT_DYLIB, [&](const dylib_command *c) {
+        StringRef reexportPath =
+            reinterpret_cast<const char *>(c) + read32le(&c->dylib.name);
+        Optional<MemoryBufferRef> buffer = readFile(expandPath(reexportPath));
+        if (!buffer) {
+          error("unable to read re-exported dylib at " + reexportPath);
+          return;
+        }
+        reexported.push_back(make<DylibFile>(*buffer, umbrella));
+      });
 }
 
 DylibFile::DylibFile() : InputFile(DylibKind, MemoryBufferRef()) {}
 
 DylibFile *DylibFile::createLibSystemMock() {
   auto *file = make<DylibFile>();
   file->mb = MemoryBufferRef("", "/usr/lib/libSystem.B.dylib");
   file->dylibName = "/usr/lib/libSystem.B.dylib";
   file->symbols.push_back(symtab->addDylib("dyld_stub_binder", file));
   return file;
 }
 
+StringRef DylibFile::expandPath(StringRef path) {
+  if (path.consume_front("@executable_path/")) {
+    SmallString<64> executablePath{getName()};
+    path::remove_filename(executablePath);
+    return saver.save(executablePath + "/" + path);
+  }
+  // TODO: implement other expansions like @rpath
+
+  return path;
+}
+
 // Returns "<internal>" or "baz.o".
 std::string lld::toString(const InputFile *file) {
   return file ? std::string(file->getName()) : "<internal>";
 }

lld/MachO/Options.td

def install_name: Separate<["-"], "install_name">,
   HelpText<"Set the install path of the dynamic library.">;
 
 def l: Joined<["-"], "l">, MetaVarName<"<libname>">,
   HelpText<"Base name of library searched for in -L directories">;
 
 def o: Separate<["-"], "o">, MetaVarName<"<path>">,
   HelpText<"Path to file to write output">;
 
+def sub_library: Separate<["-"], "sub_library">, MetaVarName<"<libname>">,
+  HelpText<"Re-export the specified dylib">;
+
 def v: Flag<["-"], "v">, HelpText<"Display the version number and exit">;
 
 // Ignored options
 def: Flag<["-"], "demangle">;
 def: Flag<["-"], "dynamic">;
 def: Flag<["-"], "no_deduplicate">;
 def: Separate<["-"], "lto_library">;
 def: Separate<["-"], "macosx_version_min">;

lld/MachO/SyntheticSections.cpp

void MachHeaderSection::writeTo(uint8_t *buf) {
   auto *hdr = reinterpret_cast<mach_header_64 *>(buf);
   hdr->magic = MH_MAGIC_64;
   hdr->cputype = CPU_TYPE_X86_64;
   hdr->cpusubtype = CPU_SUBTYPE_X86_64_ALL | CPU_SUBTYPE_LIB64;
   hdr->filetype = config->outputType;
   hdr->ncmds = loadCommands.size();
   hdr->sizeofcmds = sizeOfCmds;
   hdr->flags = MH_NOUNDEFS | MH_DYLDLINK | MH_TWOLEVEL;
-  if (config->outputType == MH_DYLIB)
+  if (config->outputType == MH_DYLIB && !config->hasReexports)
     hdr->flags |= MH_NO_REEXPORTED_DYLIBS;
 
   uint8_t *p = reinterpret_cast<uint8_t *>(hdr + 1);
   for (LoadCommand *lc : loadCommands) {
     lc->writeTo(p);
     p += lc->getSize();
   }
 }

lld/MachO/Writer.cpp

void writeTo(uint8_t *buf) const override {
     c->stroff = stringTableSection->getFileOffset();
     c->strsize = stringTableSection->getFileSize();
   }
 
   SymtabSection *symtabSection = nullptr;
   StringTableSection *stringTableSection = nullptr;
 };
 
-class LCLoadDylib : public LoadCommand {
+// There are several dylib load commands that share the same structure:
+//   * LC_LOAD_DYLIB
+//   * LC_ID_DYLIB
+//   * LC_REEXPORT_DYLIB
+class LCDylib : public LoadCommand {
 public:
-  LCLoadDylib(StringRef path) : path(path) {}
+  LCDylib(LoadCommandType type, StringRef path) : type(type), path(path) {}
 
   uint32_t getSize() const override {
     return alignTo(sizeof(dylib_command) + path.size() + 1, 8);
   }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<dylib_command *>(buf);
     buf += sizeof(dylib_command);
 
-    c->cmd = LC_LOAD_DYLIB;
+    c->cmd = type;
     c->cmdsize = getSize();
     c->dylib.name = sizeof(dylib_command);
 
     memcpy(buf, path.data(), path.size());
     buf[path.size()] = '\0';
   }
 
 private:
+  LoadCommandType type;
   StringRef path;
 };
 
-class LCIdDylib : public LoadCommand {
-public:
-  LCIdDylib(StringRef name) : name(name) {}
-
-  uint32_t getSize() const override {
-    return alignTo(sizeof(dylib_command) + name.size() + 1, 8);
-  }
-
-  void writeTo(uint8_t *buf) const override {
-    auto *c = reinterpret_cast<dylib_command *>(buf);
-    buf += sizeof(dylib_command);
-
-    c->cmd = LC_ID_DYLIB;
-    c->cmdsize = getSize();
-    c->dylib.name = sizeof(dylib_command);
-
-    memcpy(buf, name.data(), name.size());
-    buf[name.size()] = '\0';
-  }
-
-private:
-  StringRef name;
-};
-
 class LCLoadDylinker : public LoadCommand {
 public:
   uint32_t getSize() const override {
     return alignTo(sizeof(dylinker_command) + path.size() + 1, 8);
   }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<dylinker_command *>(buf);
void Writer::createLoadCommands() {
   headerSection->addLoadCommand(make<LCDysymtab>());
 
   switch (config->outputType) {
   case MH_EXECUTE:
     headerSection->addLoadCommand(make<LCMain>());
     headerSection->addLoadCommand(make<LCLoadDylinker>());
     break;
   case MH_DYLIB:
-    headerSection->addLoadCommand(make<LCIdDylib>(config->installName));
+    headerSection->addLoadCommand(
+        make<LCDylib>(LC_ID_DYLIB, config->installName));
     break;
   default:
     llvm_unreachable("unhandled output file type");
   }
 
   uint8_t segIndex = 0;
   for (OutputSegment *seg : outputSegments) {
     if (seg->isNeeded()) {
       headerSection->addLoadCommand(make<LCSegment>(seg->name, seg));
       seg->index = segIndex++;
     }
   }
 
   uint64_t dylibOrdinal = 1;
   for (InputFile *file : inputFiles) {
     if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
-      headerSection->addLoadCommand(make<LCLoadDylib>(dylibFile->dylibName));
+      headerSection->addLoadCommand(
+          make<LCDylib>(LC_LOAD_DYLIB, dylibFile->dylibName));
       dylibFile->ordinal = dylibOrdinal++;
+
+      if (dylibFile->reexport)
+        headerSection->addLoadCommand(
+            make<LCDylib>(LC_REEXPORT_DYLIB, dylibFile->dylibName));
     }
   }
 }
 
 void Writer::createHiddenSections() {
   headerSection = createInputSection<MachHeaderSection>();
   bindingSection = createInputSection<BindingSection>();
   lazyBindingSection = createInputSection<LazyBindingSection>();

lld/test/MachO/sub-library.s

+# REQUIRES: x86
+# RUN: mkdir -p %t
+
+## Create a libsuper that has libgoodbye as a sub-library, which in turns has
+## libhello as another sub-library.
+# 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: echo "" | llvm-mc -filetype=obj -triple=x86_64-apple-darwin -o %t/libsuper.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 -L%t -sub_library libhello -lhello -install_name \
+# RUN:   @executable_path/libgoodbye.dylib %t/libgoodbye.o -o %t/libgoodbye.dylib
+# RUN: lld -flavor darwinnew -dylib -L%t -sub_library libgoodbye -lgoodbye -install_name \
+# RUN:   @executable_path/libsuper.dylib %t/libsuper.o -o %t/libsuper.dylib
+
+
+## Check that they have the appropriate LC_REEXPORT_DYLIB commands, and that
+## NO_REEXPORTED_DYLIBS is (un)set as appropriate.
+
+# RUN: llvm-objdump --macho --all-headers %t/libhello.dylib | FileCheck %s \
+# RUN:   --check-prefix=HELLO-HEADERS
+# HELLO-HEADERS: NO_REEXPORTED_DYLIBS
+
+# RUN: llvm-objdump --macho --all-headers %t/libgoodbye.dylib | FileCheck %s \
+# RUN:   --check-prefix=GOODBYE-HEADERS
+# GOODBYE-HEADERS-NOT: NO_REEXPORTED_DYLIBS
+# GOODBYE-HEADERS:     cmd     LC_REEXPORT_DYLIB
+# GOODBYE-HEADERS-NOT: Load command
+# GOODBYE-HEADERS:     name    @executable_path/libhello.dylib
+
+# RUN: llvm-objdump --macho --all-headers %t/libsuper.dylib | FileCheck %s \
+# RUN:   --check-prefix=SUPER-HEADERS
+# SUPER-HEADERS-NOT: NO_REEXPORTED_DYLIBS
+# SUPER-HEADERS:     cmd     LC_REEXPORT_DYLIB
+# SUPER-HEADERS-NOT: Load command
+# SUPER-HEADERS:     name    @executable_path/libgoodbye.dylib
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/sub-library.o
+# RUN: lld -flavor darwinnew -o %t/sub-library -Z -L%t -lsuper %t/sub-library.o
+
+# RUN: llvm-objdump --macho --bind %t/sub-library | FileCheck %s
+# CHECK-LABEL: Bind table:
+# CHECK-DAG:   __DATA_CONST __got {{.*}} libsuper _hello_world
+# CHECK-DAG:   __DATA_CONST __got {{.*}} libsuper _goodbye_world
+
+
+## Check that we fail gracefully if the sub-library is missing
+# RUN: not lld -flavor darwinnew -dylib -Z -o %t/sub-library -sub_library libmissing %t/sub-library.o 2>&1 \
+# RUN:   | FileCheck %s --check-prefix=MISSING-SUB-LIBRARY
+# MISSING-SUB-LIBRARY: error: -sub_library libmissing does not match a supplied dylib
+# RUN: rm -f %t/libgoodbye.dylib
+# RUN: not lld -flavor darwinnew -o %t/sub-library -Z -L%t -lsuper %t/sub-library.o 2>&1 \
+# RUN:  | FileCheck %s --check-prefix=MISSING-REEXPORT
+# MISSING-REEXPORT: error: unable to read re-exported dylib at @executable_path/libgoodbye.dylib
+
+.text
+.globl _main
+
+_main:
+  movl $0x2000004, %eax # write() syscall
+  mov $1, %rdi # stdout
+  movq _hello_world@GOTPCREL(%rip), %rsi
+  mov $13, %rdx # length of str
+  syscall
+  mov $0, %rax
+
+  movl $0x2000004, %eax # write() syscall
+  mov $1, %rdi # stdout
+  movq _goodbye_world@GOTPCREL(%rip), %rsi
+  mov $15, %rdx # length of str
+  syscall
+  mov $0, %rax
+  ret