[mach-o] Add support for upward linking

To deal with cycles in shared library dependencies, the darwin linker supports
marking specific link dependencies as "upward".  An upward link is when a
lower level library links against a higher level library.

llvm-svn: 219949

12 files changed, 155 insertions, 19 deletions

diff --git a/lld/include/lld/Driver/DarwinInputGraph.h b/lld/include/lld/Driver/DarwinInputGraph.h
index c7967f865d0..fb7ba565b8d 100644
--- a/lld/include/lld/Driver/DarwinInputGraph.h
+++ b/lld/include/lld/Driver/DarwinInputGraph.h
@@ -25,8 +25,9 @@ namespace lld {
 /// \brief Represents a MachO File
 class MachOFileNode : public FileNode {
 public:
-  MachOFileNode(StringRef path, bool isWholeArchive, MachOLinkingContext &ctx)
-      : FileNode(path), _context(ctx), _isWholeArchive(isWholeArchive) {}
+  MachOFileNode(StringRef path, MachOLinkingContext &ctx)
+      : FileNode(path), _context(ctx), _isWholeArchive(false),
+        _upwardDylib(false) {}
 
   /// \brief Parse the input file to lld::File.
   std::error_code parse(const LinkingContext &ctx,
@@ -42,11 +43,20 @@ public:
     return *_files[_nextFileIndex++];
   }
 
+  void setLoadWholeArchive(bool value=true) {
+    _isWholeArchive = value;
+  }
+
+  void setUpwardDylib(bool value=true) {
+    _upwardDylib = value;
+  }
+
 private:
  void narrowFatBuffer(StringRef filePath);
 
   MachOLinkingContext &_context;
   bool _isWholeArchive;
+  bool _upwardDylib;
 };
 
 } // namespace lld
diff --git a/lld/include/lld/ReaderWriter/MachOLinkingContext.h b/lld/include/lld/ReaderWriter/MachOLinkingContext.h
index 9f2d49d43f0..ad40dd02a35 100644
--- a/lld/include/lld/ReaderWriter/MachOLinkingContext.h
+++ b/lld/include/lld/ReaderWriter/MachOLinkingContext.h
@@ -237,7 +237,7 @@ public:
   StringRef binderSymbolName() const;
 
   /// Used to keep track of direct and indirect dylibs.
-  void registerDylib(mach_o::MachODylibFile *dylib) const;
+  void registerDylib(mach_o::MachODylibFile *dylib, bool upward) const;
 
   /// Used to find indirect dylibs. Instantiates a MachODylibFile if one
   /// has not already been made for the requested dylib.  Uses -L and -F
@@ -252,6 +252,9 @@ public:
   bool sliceFromFatFile(const MemoryBuffer &mb, uint32_t &offset,
                         uint32_t &size);
 
+  /// Returns if a command line option specified dylib is an upward link.
+  bool isUpwardDylib(StringRef installName) const;
+
   static bool isThinObjectFile(StringRef path, Arch &arch);
   static Arch archFromCpuType(uint32_t cputype, uint32_t cpusubtype);
   static Arch archFromName(StringRef archName);
@@ -317,6 +320,7 @@ private:
   std::vector<SectionAlign> _sectAligns;
   mutable llvm::StringMap<mach_o::MachODylibFile*> _pathToDylibMap;
   mutable std::set<mach_o::MachODylibFile*> _allDylibs;
+  mutable std::set<mach_o::MachODylibFile*> _upwardDylibs;
   mutable std::vector<std::unique_ptr<class MachOFileNode>> _indirectDylibs;
   ExportMode _exportMode;
   llvm::StringSet<> _exportedSymbols;
diff --git a/lld/lib/Driver/DarwinInputGraph.cpp b/lld/lib/Driver/DarwinInputGraph.cpp
index 5a337086420..1ddde24b534 100644
--- a/lld/lib/Driver/DarwinInputGraph.cpp
+++ b/lld/lib/Driver/DarwinInputGraph.cpp
@@ -57,7 +57,8 @@ std::error_code MachOFileNode::parse(const LinkingContext &ctx,
   for (std::unique_ptr<File> &pf : parsedFiles) {
     // If a dylib was parsed, inform LinkingContext about it.
     if (SharedLibraryFile *shl = dyn_cast<SharedLibraryFile>(pf.get())) {
-      _context.registerDylib(reinterpret_cast<mach_o::MachODylibFile*>(shl));
+      _context.registerDylib(reinterpret_cast<mach_o::MachODylibFile*>(shl),
+                             _upwardDylib);
     }
     _files.push_back(std::move(pf));
   }
diff --git a/lld/lib/Driver/DarwinLdDriver.cpp b/lld/lib/Driver/DarwinLdDriver.cpp
index 5aedd7b9774..41cec564956 100644
--- a/lld/lib/Driver/DarwinLdDriver.cpp
+++ b/lld/lib/Driver/DarwinLdDriver.cpp
@@ -85,9 +85,14 @@ static std::string canonicalizePath(StringRef path) {
 }
 
 static void addFile(StringRef path, std::unique_ptr<InputGraph> &inputGraph,
-                    bool forceLoad, MachOLinkingContext &ctx) {
-   inputGraph->addInputElement(std::unique_ptr<InputElement>(
-                                      new MachOFileNode(path, forceLoad, ctx)));
+                    MachOLinkingContext &ctx, bool loadWholeArchive,
+                    bool upwardDylib) {
+  auto node = llvm::make_unique<MachOFileNode>(path, ctx);
+  if (loadWholeArchive)
+    node->setLoadWholeArchive();
+  if (upwardDylib)
+    node->setUpwardDylib();
+  inputGraph->addInputElement(std::move(node));
 }
 
 // Export lists are one symbol per line.  Blank lines are ignored.
@@ -165,7 +170,7 @@ static std::error_code parseFileList(StringRef fileListPath,
     if (ctx.testingFileUsage()) {
       diagnostics << "Found filelist entry " << canonicalizePath(path) << '\n';
     }
-    addFile(path, inputGraph, forceLoad, ctx);
+    addFile(path, inputGraph, ctx, forceLoad, false);
     buffer = lineAndRest.second;
   }
   return std::error_code();
@@ -638,34 +643,44 @@ bool DarwinLdDriver::parse(int argc, const char *argv[],
 
   // Handle input files
   for (auto &arg : *parsedArgs) {
+    bool upward;
     ErrorOr<StringRef> resolvedPath = StringRef();
     switch (arg->getOption().getID()) {
     default:
       continue;
     case OPT_INPUT:
-      addFile(arg->getValue(), inputGraph, globalWholeArchive, ctx);
+      addFile(arg->getValue(), inputGraph, ctx, globalWholeArchive, false);
+      break;
+    case OPT_upward_library:
+      addFile(arg->getValue(), inputGraph, ctx, false, true);
       break;
     case OPT_l:
+    case OPT_upward_l:
+      upward = (arg->getOption().getID() == OPT_upward_l);
       resolvedPath = ctx.searchLibrary(arg->getValue());
       if (!resolvedPath) {
-        diagnostics << "Unable to find library -l" << arg->getValue() << "\n";
+        diagnostics << "Unable to find library for " << arg->getSpelling()
+                    << arg->getValue() << "\n";
         return false;
       } else if (ctx.testingFileUsage()) {
-       diagnostics << "Found library "
+        diagnostics << "Found " << (upward ? "upward " : " ") << "library "
                    << canonicalizePath(resolvedPath.get()) << '\n';
       }
-      addFile(resolvedPath.get(), inputGraph, globalWholeArchive, ctx);
+      addFile(resolvedPath.get(), inputGraph, ctx, globalWholeArchive, upward);
       break;
     case OPT_framework:
+    case OPT_upward_framework:
+      upward = (arg->getOption().getID() == OPT_upward_framework);
       resolvedPath = ctx.findPathForFramework(arg->getValue());
       if (!resolvedPath) {
-        diagnostics << "Unable to find -framework " << arg->getValue() << "\n";
+        diagnostics << "Unable to find framework for "
+                    << arg->getSpelling() << " " << arg->getValue() << "\n";
         return false;
       } else if (ctx.testingFileUsage()) {
-        diagnostics << "Found framework "
+        diagnostics << "Found " << (upward ? "upward " : " ") << "framework "
                     << canonicalizePath(resolvedPath.get()) << '\n';
       }
-      addFile(resolvedPath.get(), inputGraph, globalWholeArchive, ctx);
+      addFile(resolvedPath.get(), inputGraph, ctx, globalWholeArchive, upward);
       break;
     case OPT_filelist:
       if (std::error_code ec = parseFileList(arg->getValue(), inputGraph,
diff --git a/lld/lib/Driver/DarwinLdOptions.td b/lld/lib/Driver/DarwinLdOptions.td
index 22d6e354906..fff976cf06f 100644
--- a/lld/lib/Driver/DarwinLdOptions.td
+++ b/lld/lib/Driver/DarwinLdOptions.td
@@ -115,9 +115,18 @@ def syslibroot : Separate<["-"], "syslibroot">, MetaVarName<"<dir>">,
 def l : Joined<["-"], "l">,
      MetaVarName<"<libname>">,
      HelpText<"Base name of library searched for in -L directories">;
+def upward_l : Joined<["-"], "upward-l">,
+     MetaVarName<"<libname>">,
+     HelpText<"Base name of upward library searched for in -L directories">;
 def framework : Separate<["-"], "framework">,
      MetaVarName<"<name>">,
      HelpText<"Base name of framework searched for in -F directories">;
+def upward_framework : Separate<["-"], "upward_framework">,
+     MetaVarName<"<name>">,
+     HelpText<"Base name of upward framework searched for in -F directories">;
+def upward_library : Separate<["-"], "upward_library">,
+     MetaVarName<"<path>">,
+     HelpText<"path to upward dylib to link with">;
 def filelist : Separate<["-"], "filelist">,
      MetaVarName<"<path>">,
      HelpText<"file containing paths to input files">;
diff --git a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
index 3b9c6fb9973..f23bfc86a6e 100644
--- a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
@@ -598,7 +598,7 @@ Writer &MachOLinkingContext::writer() const {
 }
 
 MachODylibFile* MachOLinkingContext::loadIndirectDylib(StringRef path) {
-  std::unique_ptr<MachOFileNode> node(new MachOFileNode(path, false, *this));
+  std::unique_ptr<MachOFileNode> node(new MachOFileNode(path, *this));
   std::error_code ec = node->parse(*this, llvm::errs());
   if (ec)
     return nullptr;
@@ -668,15 +668,26 @@ bool MachOLinkingContext::createImplicitFiles(
 }
 
 
-void MachOLinkingContext::registerDylib(MachODylibFile *dylib) const {
+void MachOLinkingContext::registerDylib(MachODylibFile *dylib,
+                                        bool upward) const {
   _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;
+  if (upward)
+    _upwardDylibs.insert(dylib);
 }
 
 
+bool MachOLinkingContext::isUpwardDylib(StringRef installName) const {
+  for (MachODylibFile *dylib : _upwardDylibs) {
+    if (dylib->installName().equals(installName))
+      return true;
+  }
+  return false;
+}
+
 ArchHandler &MachOLinkingContext::archHandler() const {
   if (!_archHandler)
     _archHandler = ArchHandler::create(_arch);
diff --git a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
index e41d9189640..531479de250 100644
--- a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
@@ -808,7 +808,7 @@ std::error_code MachOFileLayout::writeLoadCommands() {
     for (const DependentDylib &dep : _file.dependentDylibs) {
       dylib_command* dc = reinterpret_cast<dylib_command*>(lc);
       uint32_t size = sizeof(dylib_command) + pointerAlign(dep.path.size()+1);
-      dc->cmd                         = LC_LOAD_DYLIB;
+      dc->cmd                         = dep.kind;
       dc->cmdsize                     = size;
       dc->dylib.name                  = sizeof(dylib_command); // offset
       dc->dylib.timestamp             = 0; // FIXME
diff --git a/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp b/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp
index 7147c1222c5..d3ee9f0be29 100644
--- a/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp
@@ -935,6 +935,8 @@ void Util::addDependentDylibs(const lld::File &atomFile,NormalizedFile &nFile) {
     DylibInfo &info = _dylibInfo[dep.path];
     if (info.hasWeak && !info.hasNonWeak)
       dep.kind = llvm::MachO::LC_LOAD_WEAK_DYLIB;
+    else if (_context.isUpwardDylib(dep.path))
+      dep.kind = llvm::MachO::LC_LOAD_UPWARD_DYLIB;
   }
 }
 
diff --git a/lld/test/mach-o/Inputs/bar.yaml b/lld/test/mach-o/Inputs/bar.yaml
new file mode 100644
index 00000000000..5605e67e7c3
--- /dev/null
+++ b/lld/test/mach-o/Inputs/bar.yaml
@@ -0,0 +1,18 @@
+
+--- !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:         [ 0xC3 ]
+global-symbols:
+  - name:            _bar
+    type:            N_SECT
+    scope:           [ N_EXT ]
+    sect:            1
+    value:           0x0000000000000000
diff --git a/lld/test/mach-o/libresolve-bizarre-root-override.yaml b/lld/test/mach-o/libresolve-bizarre-root-override.yaml
index 5e4b80baa15..c65ca319432 100644
--- a/lld/test/mach-o/libresolve-bizarre-root-override.yaml
+++ b/lld/test/mach-o/libresolve-bizarre-root-override.yaml
@@ -14,4 +14,4 @@
 # CHECK: Library search paths:
 # CHECK:     /usr/lib
 # CHECK-NOT:     /usr/local/lib
-# CHECK: Unable to find library -lSystem
+# CHECK: Unable to find library for -lSystem
diff --git a/lld/test/mach-o/upward-dylib-load-command.yaml b/lld/test/mach-o/upward-dylib-load-command.yaml
new file mode 100644
index 00000000000..fee3e41d5bd
--- /dev/null
+++ b/lld/test/mach-o/upward-dylib-load-command.yaml
@@ -0,0 +1,48 @@
+# RUN: lld -flavor darwin -arch x86_64 -dylib %p/Inputs/bar.yaml \
+# RUN:     -install_name /usr/lib/libbar.dylib %p/Inputs/libSystem.yaml -o %t1.dylib
+# RUN: lld -flavor darwin -arch x86_64 -dylib %s -upward_library  %t1.dylib \
+# RUN:      -install_name /usr/lib/libfoo.dylib %p/Inputs/libSystem.yaml -o %t 
+# RUN: llvm-objdump -private-headers %t | FileCheck %s
+#
+#
+# Test upward linking: 1) build libbar.dylib, 2) build libfoo.dylib and upward
+# like with libbar.dylib, 3) dump load commands of libfoo and verify upward link.
+#
+
+--- !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, 0x31, 0xC0, 0x5D, 0xE9, 
+                       0x00, 0x00, 0x00, 0x00 ]
+    relocations:
+      - offset:          0x00000008
+        type:            X86_64_RELOC_BRANCH
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          1
+global-symbols:
+  - name:            _foo
+    type:            N_SECT
+    scope:           [ N_EXT ]
+    sect:            1
+    value:           0x0000000000000000
+undefined-symbols:
+  - name:            _bar
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+
+...
+
+
+# CHECK:	              cmd LC_LOAD_UPWARD_DYLIB
+# CHECK-NEXT:	      cmdsize 48
+# CHECK-NEXT:	         name /usr/lib/libbar.dylib (offset 24)
diff --git a/lld/test/mach-o/upward-dylib-paths.yaml b/lld/test/mach-o/upward-dylib-paths.yaml
new file mode 100644
index 00000000000..53ff9fa2298
--- /dev/null
+++ b/lld/test/mach-o/upward-dylib-paths.yaml
@@ -0,0 +1,18 @@
+#
+#
+# RUN: lld -flavor darwin -arch x86_64 -r -test_file_usage -v \
+# RUN:        -path_exists /Custom/Frameworks \
+# RUN:        -path_exists /Custom/Frameworks/Bar.framework/Bar \
+# RUN:        -path_exists /usr/lib \
+# RUN:        -path_exists /usr/lib/libfoo.dylib \
+# RUN:        -path_exists /opt/stuff/libstuff.dylib \
+# RUN:        -F/Custom/Frameworks \
+# RUN:        -upward_framework Bar \
+# RUN:        -upward-lfoo \
+# RUN:        -upward_library /opt/stuff/libstuff.dylib \
+# RUN: 2>&1 | FileCheck %s
+
+# CHECK: Found upward framework /Custom/Frameworks/Bar.framework/Bar
+# CHECK: Found upward library /usr/lib/libfoo.dylib
+
+