[mach-o] Support re-exported dylibs

In general two-level namespace means each program records exactly which dylib
each undefined (imported) symbol comes from.  But, sometimes the implementor
wants to hide the implementation dylib.  For instance libSytem.dylib is the base
dylib all Darwin programs must link with.  A few years ago it was split up
into two dozen dylibs by all are hidden behind libSystem.dylib which re-exports
each sub-dylib.  All clients still think libSystem.dylib is the implementor.

To support this, the linker must load "indirect" dylibs and not just the
"direct" dylibs specified on the command line.  This is done in the
createImplicitFiles() method after all command line specified files are
loaded.  Since an indirect dylib may have already been loaded as a direct dylib
(or indirectly via a previous direct dylib), the MachOLinkingContext keeps
a list of all loaded dylibs.

With this change hello world can now be linked against the real OS or SDK.

llvm-svn: 215605

5 files changed, 202 insertions, 42 deletions

diff --git a/lld/lib/ReaderWriter/MachO/Atoms.h b/lld/lib/ReaderWriter/MachO/Atoms.h
index 13d546f0264..3107ee384d6 100644
--- a/lld/lib/ReaderWriter/MachO/Atoms.h
+++ b/lld/lib/ReaderWriter/MachO/Atoms.h
@@ -123,7 +123,7 @@ private:
 class MachOSharedLibraryAtom : public SharedLibraryAtom {
 public:
   MachOSharedLibraryAtom(const File &file, StringRef name,
-                         StringRef dylibInstallName)
+                         StringRef dylibInstallName, bool weakDef)
       : SharedLibraryAtom(), _file(file), _name(name),
         _dylibInstallName(dylibInstallName) {}
   virtual ~MachOSharedLibraryAtom() {}
diff --git a/lld/lib/ReaderWriter/MachO/File.h b/lld/lib/ReaderWriter/MachO/File.h
index df9be71c18c..bc6a75a39f5 100644
--- a/lld/lib/ReaderWriter/MachO/File.h
+++ b/lld/lib/ReaderWriter/MachO/File.h
@@ -175,22 +175,16 @@ private:
 
 class MachODylibFile : public SharedLibraryFile {
 public:
-  MachODylibFile(StringRef path) : SharedLibraryFile(path), _dylib_name(path) {}
-
-  virtual const SharedLibraryAtom *exports(StringRef name,
-                                           bool dataSymbolOnly) const {
-    // FIXME: we obviously need to record code/data if we're going to make
-    // proper use of dataSymbolOnly.
-    auto sym = _nameToAtom.find(name);
-
-    if (sym == _nameToAtom.end())
-      return nullptr;
-
-    if (!sym->second)
-      sym->second =
-          new (_allocator) MachOSharedLibraryAtom(*this, name, _dylib_name);
+  MachODylibFile(StringRef path, StringRef installName)
+      : SharedLibraryFile(path), _installName(installName) {
+  }
 
-    return sym->second;
+  virtual const SharedLibraryAtom *exports(StringRef name, bool isData) const {
+    // Pass down _installName and _allocator so that if this requested symbol
+    // is re-exported through this dylib, the SharedLibraryAtom's loadName()
+    // is this dylib installName and not the implementation dylib's.
+    // NOTE: isData is not needed for dylibs (it matters for static libs).
+    return exports(name, _installName, _allocator);
   }
 
   const atom_collection<DefinedAtom> &defined() const override {
@@ -209,22 +203,78 @@ public:
     return _absoluteAtoms;
   }
 
-  void addSharedLibraryAtom(StringRef name, bool copyRefs) {
+  /// Adds symbol name that this dylib exports. The corresponding
+  /// SharedLibraryAtom is created lazily (since most symbols are not used).
+  void addExportedSymbol(StringRef name, bool weakDef, bool copyRefs) {
     if (copyRefs) {
       name = name.copy(_allocator);
     }
+    AtomAndFlags info(weakDef);
+    _nameToAtom[name] = info;
+  }
 
-    _nameToAtom[name] = nullptr;
+  void addReExportedDylib(StringRef dylibPath) {
+    _reExportedDylibs.emplace_back(dylibPath);
+  }
+
+  StringRef installName() { return _installName; }
+
+  typedef std::function<MachODylibFile *(StringRef)> FindDylib;
+
+  void loadReExportedDylibs(FindDylib find) {
+    for (ReExportedDylib &entry : _reExportedDylibs) {
+      entry.file = find(entry.path);
+    }
   }
 
 private:
-  StringRef _dylib_name;
+  const SharedLibraryAtom *exports(StringRef name, StringRef installName,
+                                   llvm::BumpPtrAllocator &allocator) const {
+    // First, check if requested symbol is directly implemented by this dylib.
+    auto entry = _nameToAtom.find(name);
+    if (entry != _nameToAtom.end()) {
+      if (!entry->second.atom) {
+        // Lazily create SharedLibraryAtom.
+        entry->second.atom =
+          new (allocator) MachOSharedLibraryAtom(*this, name, installName,
+                                                 entry->second.weakDef);
+      }
+      return entry->second.atom;
+    }
+
+    // Next, check if symbol is implemented in some re-exported dylib.
+    for (const ReExportedDylib &dylib : _reExportedDylibs) {
+      assert(dylib.file);
+      auto atom = dylib.file->exports(name, installName, allocator);
+      if (atom)
+        return atom;
+    }
+
+    // Symbol not exported or re-exported by this dylib.
+    return nullptr;
+  }
+
+
+  struct ReExportedDylib {
+    ReExportedDylib(StringRef p) : path(p), file(nullptr) { }
+    StringRef       path;
+    MachODylibFile *file;
+  };
+
+  struct AtomAndFlags {
+    AtomAndFlags() : atom(nullptr), weakDef(false) { }
+    AtomAndFlags(bool weak) : atom(nullptr), weakDef(weak) { }
+    const SharedLibraryAtom  *atom;
+    bool                      weakDef;
+  };
+
+  StringRef _installName;
   atom_collection_vector<DefinedAtom>        _definedAtoms;
   atom_collection_vector<UndefinedAtom>      _undefinedAtoms;
   atom_collection_vector<SharedLibraryAtom>  _sharedLibraryAtoms;
   atom_collection_vector<AbsoluteAtom>       _absoluteAtoms;
-
-  mutable std::unordered_map<StringRef, SharedLibraryAtom *> _nameToAtom;
+  std::vector<ReExportedDylib>               _reExportedDylibs;
+  mutable std::unordered_map<StringRef, AtomAndFlags> _nameToAtom;
   mutable llvm::BumpPtrAllocator _allocator;
 };
 
diff --git a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
index a5bca11cb5f..427b59a8b70 100644
--- a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
@@ -10,9 +10,11 @@
 #include "lld/ReaderWriter/MachOLinkingContext.h"
 
 #include "ArchHandler.h"
+#include "File.h"
 #include "MachOPasses.h"
 
 #include "lld/Core/PassManager.h"
+#include "lld/Driver/DarwinInputGraph.h"
 #include "lld/ReaderWriter/Reader.h"
 #include "lld/ReaderWriter/Writer.h"
 #include "lld/Passes/LayoutPass.h"
@@ -28,6 +30,7 @@
 #include <algorithm>
 
 using lld::mach_o::ArchHandler;
+using lld::mach_o::MachODylibFile;
 using namespace llvm::MachO;
 
 namespace lld {
@@ -304,16 +307,16 @@ bool MachOLinkingContext::pathExists(StringRef path) const {
   return _existingPaths.find(key) != _existingPaths.end();
 }
 
-void MachOLinkingContext::addModifiedSearchDir(
-    StringRef libPath, const StringRefVector &syslibRoots, bool isSystemPath) {
+void MachOLinkingContext::addModifiedSearchDir(StringRef libPath,
+                                               bool isSystemPath) {
   bool addedModifiedPath = false;
 
   // Two cases to consider here:
   //   + If the last -syslibroot is "/", all of them are ignored (don't ask).
   //   + -syslibroot only applies to absolute paths.
-  if (!syslibRoots.empty() && syslibRoots.back() != "/" &&
+  if (!_syslibRoots.empty() && _syslibRoots.back() != "/" &&
       libPath.startswith("/")) {
-    for (auto syslibRoot : syslibRoots) {
+    for (auto syslibRoot : _syslibRoots) {
       SmallString<256> path(syslibRoot);
       llvm::sys::path::append(path, libPath);
       if (pathExists(path)) {
@@ -328,7 +331,7 @@ void MachOLinkingContext::addModifiedSearchDir(
 
   // Finally, if only one -syslibroot is given, system paths which aren't in it
   // get suppressed.
-  if (syslibRoots.size() != 1 || !isSystemPath) {
+  if (_syslibRoots.size() != 1 || !isSystemPath) {
     if (pathExists(libPath)) {
       _searchDirs.push_back(libPath);
     }
@@ -419,6 +422,86 @@ Writer &MachOLinkingContext::writer() const {
   return *_writer;
 }
 
+MachODylibFile* MachOLinkingContext::loadIndirectDylib(StringRef path) const {
+  std::unique_ptr<MachOFileNode> node(new MachOFileNode(path, false));
+  std::error_code ec = node->parse(*this, llvm::errs());
+  if (ec)
+    return nullptr;
+
+  assert(node->files().size() == 1 && "expected one file in dylib");
+  // lld::File object is owned by MachOFileNode object. This method returns
+  // an unowned pointer to the lld::File object.
+  MachODylibFile* result = reinterpret_cast<MachODylibFile*>(
+                                                   node->files().front().get());
+
+  // Node object now owned by _indirectDylibs vector.
+  _indirectDylibs.push_back(std::move(node));
+
+  return result;
+}
+
+
+MachODylibFile* MachOLinkingContext::findIndirectDylib(StringRef path) const {
+  // See if already loaded.
+  auto pos = _pathToDylibMap.find(path);
+  if (pos != _pathToDylibMap.end())
+    return pos->second;
+
+  // Search -L paths if of the form "libXXX.dylib"
+  std::pair<StringRef, StringRef> split = path.rsplit('/');
+  StringRef leafName = split.second;
+  if (leafName.startswith("lib") && leafName.endswith(".dylib")) {
+    // FIXME: Need to enhance searchLibrary() to only look for .dylib
+    auto libPath = searchLibrary(leafName);
+    if (!libPath.getError()) {
+      return loadIndirectDylib(libPath.get());
+    }
+  }
+
+  // Try full path with sysroot.
+  for (StringRef sysPath : _syslibRoots) {
+    SmallString<256> fullPath;
+    fullPath.assign(sysPath);
+    llvm::sys::path::append(fullPath, path);
+    if (pathExists(fullPath))
+      return loadIndirectDylib(fullPath);
+  }
+
+  // Try full path.
+  if (pathExists(path)) {
+    return loadIndirectDylib(path);
+  }
+
+  return nullptr;
+}
+
+bool MachOLinkingContext::createImplicitFiles(
+                            std::vector<std::unique_ptr<File> > &result) const {
+  // Add indirect dylibs by asking each linked dylib to add its indirects.
+  // Iterate until no more dylibs get loaded.
+  size_t dylibCount = 0;
+  while (dylibCount != _allDylibs.size()) {
+    dylibCount = _allDylibs.size();
+    for (MachODylibFile *dylib : _allDylibs) {
+      dylib->loadReExportedDylibs([this] (StringRef path) -> MachODylibFile* {
+                                  return findIndirectDylib(path); });
+    }
+  }
+
+  // Let writer add output type specific extras.
+  return writer().createImplicitFiles(result);
+}
+
+
+void MachOLinkingContext::registerDylib(MachODylibFile *dylib) {
+  _allDylibs.insert(dylib);
+  _pathToDylibMap[dylib->installName()] = dylib;
+  // If path is different than install name, register path too.
+  if (!dylib->path().equals(dylib->installName()))
+    _pathToDylibMap[dylib->path()] = dylib;
+}
+
+
 ArchHandler &MachOLinkingContext::archHandler() const {
   if (!_archHandler)
     _archHandler = ArchHandler::create(_arch);
diff --git a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryReader.cpp b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryReader.cpp
index 27162450d64..fc43141ca24 100644
--- a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryReader.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryReader.cpp
@@ -28,6 +28,7 @@
 
 #include "lld/Core/Error.h"
 #include "lld/Core/LLVM.h"
+#include "lld/Core/SharedLibraryFile.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSwitch.h"
@@ -233,8 +234,9 @@ readBinary(std::unique_ptr<MemoryBuffer> &mb,
   uint32_t dataInCodeSize = 0;
   ec = forEachLoadCommand(lcRange, lcCount, swap, is64,
                     [&] (uint32_t cmd, uint32_t size, const char* lc) -> bool {
-    if (is64) {
-      if (cmd == LC_SEGMENT_64) {
+    switch(cmd) {
+    case LC_SEGMENT_64:
+      if (is64) {
         const segment_command_64 *seg =
                               reinterpret_cast<const segment_command_64*>(lc);
         const unsigned sectionCount = (swap
@@ -276,8 +278,9 @@ readBinary(std::unique_ptr<MemoryBuffer> &mb,
           f->sections.push_back(section);
         }
       }
-    } else {
-      if (cmd == LC_SEGMENT) {
+      break;
+    case LC_SEGMENT:
+      if (!is64) {
         const segment_command *seg =
                               reinterpret_cast<const segment_command*>(lc);
         const unsigned sectionCount = (swap
@@ -319,8 +322,8 @@ readBinary(std::unique_ptr<MemoryBuffer> &mb,
           f->sections.push_back(section);
         }
       }
-    }
-    if (cmd == LC_SYMTAB) {
+      break;
+    case LC_SYMTAB: {
       const symtab_command *st = reinterpret_cast<const symtab_command*>(lc);
       const char *strings = start + read32(swap, st->stroff);
       const uint32_t strSize = read32(swap, st->strsize);
@@ -389,15 +392,31 @@ readBinary(std::unique_ptr<MemoryBuffer> &mb,
             f->localSymbols.push_back(sout);
         }
       }
-    } else if (cmd == LC_ID_DYLIB) {
+      }
+      break;
+    case LC_ID_DYLIB: {
       const dylib_command *dl = reinterpret_cast<const dylib_command*>(lc);
       f->installName = lc + read32(swap, dl->dylib.name);
-    } else if (cmd == LC_DATA_IN_CODE) {
+      }
+      break;
+    case LC_DATA_IN_CODE: {
       const linkedit_data_command *ldc =
                             reinterpret_cast<const linkedit_data_command*>(lc);
       dataInCode = reinterpret_cast<const data_in_code_entry*>(
                                             start + read32(swap, ldc->dataoff));
       dataInCodeSize = read32(swap, ldc->datasize);
+      }
+    case LC_LOAD_DYLIB:
+    case LC_LOAD_WEAK_DYLIB:
+    case LC_REEXPORT_DYLIB:
+    case LC_LOAD_UPWARD_DYLIB: {
+      const dylib_command *dl = reinterpret_cast<const dylib_command*>(lc);
+      DependentDylib entry;
+      entry.path = lc + read32(swap, dl->dylib.name);
+      entry.kind = LoadCommandType(cmd);
+      f->dependentDylibs.push_back(entry);
+      }
+      break;
     }
     return false;
   });
@@ -422,7 +441,7 @@ readBinary(std::unique_ptr<MemoryBuffer> &mb,
 
 class MachOReader : public Reader {
 public:
-  MachOReader(MachOLinkingContext::Arch arch) : _arch(arch) {}
+  MachOReader(MachOLinkingContext &ctx) : _ctx(ctx) {}
 
   bool canParse(file_magic magic, StringRef ext,
                 const MemoryBuffer &mb) const override {
@@ -437,7 +456,7 @@ public:
   parseFile(std::unique_ptr<MemoryBuffer> &mb, const Registry &registry,
             std::vector<std::unique_ptr<File>> &result) const override {
     // Convert binary file to normalized mach-o.
-    auto normFile = readBinary(mb, _arch);
+    auto normFile = readBinary(mb, _ctx.arch());
     if (std::error_code ec = normFile.getError())
       return ec;
     // Convert normalized mach-o to atoms.
@@ -450,16 +469,16 @@ public:
     return std::error_code();
   }
 private:
-  MachOLinkingContext::Arch _arch;
+  MachOLinkingContext &_ctx;
 };
 
 
 } // namespace normalized
 } // namespace mach_o
 
-void Registry::addSupportMachOObjects(const MachOLinkingContext &ctx) {
+void Registry::addSupportMachOObjects(MachOLinkingContext &ctx) {
   MachOLinkingContext::Arch arch = ctx.arch();
-  add(std::unique_ptr<Reader>(new mach_o::normalized::MachOReader(arch)));
+  add(std::unique_ptr<Reader>(new mach_o::normalized::MachOReader(ctx)));
   addKindTable(Reference::KindNamespace::mach_o, ctx.archHandler().kindArch(), 
                ctx.archHandler().kindStrings());
   add(std::unique_ptr<YamlIOTaggedDocumentHandler>(
diff --git a/lld/lib/ReaderWriter/MachO/MachONormalizedFileToAtoms.cpp b/lld/lib/ReaderWriter/MachO/MachONormalizedFileToAtoms.cpp
index 900c9eb9680..9b9c625ab76 100644
--- a/lld/lib/ReaderWriter/MachO/MachONormalizedFileToAtoms.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachONormalizedFileToAtoms.cpp
@@ -671,12 +671,19 @@ normalizedObjectToAtoms(const NormalizedFile &normalizedFile, StringRef path,
 ErrorOr<std::unique_ptr<lld::File>>
 normalizedDylibToAtoms(const NormalizedFile &normalizedFile, StringRef path,
                        bool copyRefs) {
+  // Instantiate SharedLibraryFile object.
   std::unique_ptr<MachODylibFile> file(
-      new MachODylibFile(normalizedFile.installName));
-
+                          new MachODylibFile(path, normalizedFile.installName));
+  // Tell MachODylibFile object about all symbols it exports.
   for (auto &sym : normalizedFile.globalSymbols) {
     assert((sym.scope & N_EXT) && "only expect external symbols here");
-    file->addSharedLibraryAtom(sym.name, copyRefs);
+    bool weakDef = (sym.desc & N_WEAK_DEF);
+    file->addExportedSymbol(sym.name, weakDef, copyRefs);
+  }
+  // Tell MachODylibFile object about all dylibs it re-exports.
+  for (const DependentDylib &dep : normalizedFile.dependentDylibs) {
+    if (dep.kind == llvm::MachO::LC_REEXPORT_DYLIB)
+      file->addReExportedDylib(dep.path);
   }
 
   return std::unique_ptr<File>(std::move(file));
@@ -715,6 +722,7 @@ normalizedToAtoms(const NormalizedFile &normalizedFile, StringRef path,
                   bool copyRefs) {
   switch (normalizedFile.fileType) {
   case MH_DYLIB:
+  case MH_DYLIB_STUB:
     return normalizedDylibToAtoms(normalizedFile, path, copyRefs);
   case MH_OBJECT:
     return normalizedObjectToAtoms(normalizedFile, path, copyRefs);