[lld][MachO] Initial implementation of -flat_namespace and -undefined.

This is a basic initial implementation of the -flat_namespace and
-undefined options for LLD-darwin. It ignores several subtlties,
but the result is close enough that we can now link LLVM (but not
clang) on Darwin and pass all regression tests.

llvm-svn: 248732

11 files changed, 288 insertions, 12 deletions

diff --git a/lld/include/lld/ReaderWriter/MachOLinkingContext.h b/lld/include/lld/ReaderWriter/MachOLinkingContext.h
index 1f845a97ea2..a3459693c7d 100644
--- a/lld/include/lld/ReaderWriter/MachOLinkingContext.h
+++ b/lld/include/lld/ReaderWriter/MachOLinkingContext.h
@@ -63,6 +63,13 @@ public:
     noDebugMap      // -S option
   };
 
+  enum class UndefinedMode {
+    error,
+    warning,
+    suppress,
+    dynamicLookup
+  };
+
   /// Initializes the context to sane default values given the specified output
   /// file type, arch, os, and minimum os version.  This should be called before
   /// other setXXX() methods.
@@ -204,6 +211,30 @@ public:
   /// when linking a binary that does not use any of its symbols.
   bool deadStrippableDylib() const { return _deadStrippableDylib; }
 
+  /// \brief Whether or not to use flat namespace.
+  ///
+  /// MachO usually uses a two-level namespace, where each external symbol
+  /// referenced by the target is associated with the dylib that will provide
+  /// the symbol's definition at runtime. Using flat namespace overrides this
+  /// behavior: the linker searches all dylibs on the command line and all
+  /// dylibs those original dylibs depend on, but does not record which dylib
+  /// an external symbol came from. At runtime dyld again searches all images
+  /// and uses the first definition it finds. In addition, any undefines in
+  /// loaded flat_namespace dylibs must be resolvable at build time.
+  bool useFlatNamespace() const { return _flatNamespace; }
+
+  /// \brief How to handle undefined symbols.
+  ///
+  /// Options are:
+  ///  * error: Report an error and terminate linking.
+  ///  * warning: Report a warning, but continue linking.
+  ///  * suppress: Ignore and continue linking.
+  ///  * dynamic_lookup: For use with -twolevel namespace: Records source dylibs
+  ///    for symbols that are defined in a linked dylib at static link time.
+  ///    Undefined symbols are handled by searching all loaded images at
+  ///    runtime.
+  UndefinedMode undefinedMode() const { return _undefinedMode; }
+
   /// \brief The path to the executable that will load the bundle at runtime.
   ///
   /// When building a Mach-O bundle, this executable will be examined if there
@@ -218,6 +249,14 @@ public:
   void setDeadStrippableDylib(bool deadStrippable) {
     _deadStrippableDylib = deadStrippable;
   }
+  void setUseFlatNamespace(bool flatNamespace) {
+    _flatNamespace = flatNamespace;
+  }
+
+  void setUndefinedMode(UndefinedMode undefinedMode) {
+    _undefinedMode = undefinedMode;
+  }
+
   void setBundleLoader(StringRef loader) { _bundleLoader = loader; }
   void setPrintAtoms(bool value=true) { _printAtoms = value; }
   void setTestingFileUsage(bool value = true) {
@@ -301,6 +340,11 @@ public:
   bool customAtomOrderer(const DefinedAtom *left, const DefinedAtom *right,
                          bool &leftBeforeRight) const;
 
+  /// Return the 'flat namespace' file. This is the file that supplies
+  /// atoms for otherwise undefined symbols when the -flat_namespace or
+  /// -undefined dynamic_lookup options are used.
+  File* flatNamespaceFile() const { return _flatNamespaceFile; }
+
 private:
   Writer &writer() const override;
   mach_o::MachODylibFile* loadIndirectDylib(StringRef path);
@@ -349,6 +393,8 @@ private:
   uint32_t _currentVersion;
   StringRef _installName;
   StringRefVector _rpaths;
+  bool _flatNamespace;
+  UndefinedMode _undefinedMode;
   bool _deadStrippableDylib;
   bool _printAtoms;
   bool _testingFileUsage;
@@ -369,6 +415,7 @@ private:
   std::unique_ptr<llvm::raw_fd_ostream> _dependencyInfo;
   llvm::StringMap<std::vector<OrderFileNode>> _orderFiles;
   unsigned _orderFileEntries;
+  File *_flatNamespaceFile;
 };
 
 } // end namespace lld
diff --git a/lld/lib/Driver/DarwinLdDriver.cpp b/lld/lib/Driver/DarwinLdDriver.cpp
index e70aac441b6..b4a1cf3d431 100644
--- a/lld/lib/Driver/DarwinLdDriver.cpp
+++ b/lld/lib/Driver/DarwinLdDriver.cpp
@@ -751,6 +751,49 @@ bool DarwinLdDriver::parse(llvm::ArrayRef<const char *> args,
     }
   }
 
+  // Handle -flat_namespace.
+  if (llvm::opt::Arg *ns =
+          parsedArgs.getLastArg(OPT_flat_namespace, OPT_twolevel_namespace)) {
+    if (ns->getOption().getID() == OPT_flat_namespace)
+      ctx.setUseFlatNamespace(true);
+  }
+
+  // Handle -undefined
+  if (llvm::opt::Arg *undef = parsedArgs.getLastArg(OPT_undefined)) {
+    MachOLinkingContext::UndefinedMode UndefMode;
+    if (StringRef(undef->getValue()).equals("error"))
+      UndefMode = MachOLinkingContext::UndefinedMode::error;
+    else if (StringRef(undef->getValue()).equals("warning"))
+      UndefMode = MachOLinkingContext::UndefinedMode::warning;
+    else if (StringRef(undef->getValue()).equals("suppress"))
+      UndefMode = MachOLinkingContext::UndefinedMode::suppress;
+    else if (StringRef(undef->getValue()).equals("dynamic_lookup"))
+      UndefMode = MachOLinkingContext::UndefinedMode::dynamicLookup;
+    else {
+      diagnostics << "error: invalid option to -undefined "
+                     "[ warning | error | suppress | dynamic_lookup ]\n";
+      return false;
+    }
+
+    if (ctx.useFlatNamespace()) {
+      // If we're using -flat_namespace then 'warning', 'suppress' and
+      // 'dynamic_lookup' are all equivalent, so map them to 'suppress'.
+      if (UndefMode != MachOLinkingContext::UndefinedMode::error)
+        UndefMode = MachOLinkingContext::UndefinedMode::suppress;
+    } else {
+      // If we're using -twolevel_namespace then 'warning' and 'suppress' are
+      // illegal. Emit a diagnostic if they've been (mis)used.
+      if (UndefMode == MachOLinkingContext::UndefinedMode::warning ||
+          UndefMode == MachOLinkingContext::UndefinedMode::suppress) {
+        diagnostics << "error: can't use -undefined warning or suppress with "
+                       "-twolevel_namespace\n";
+        return false;
+      }
+    }
+
+    ctx.setUndefinedMode(UndefMode);
+  }
+
   // Handle -rpath <path>
   if (parsedArgs.hasArg(OPT_rpath)) {
     switch (ctx.outputMachOType()) {
diff --git a/lld/lib/Driver/DarwinLdOptions.td b/lld/lib/Driver/DarwinLdOptions.td
index f9b243ec45c..6631ee9527b 100644
--- a/lld/lib/Driver/DarwinLdOptions.td
+++ b/lld/lib/Driver/DarwinLdOptions.td
@@ -55,6 +55,19 @@ def order_file : Separate<["-"], "order_file">,
      MetaVarName<"<file-path>">,
      HelpText<"re-order and move specified symbols to start of their section">,
      Group<grp_opts>;
+def flat_namespace : Flag<["-"], "flat_namespace">,
+     HelpText<"Resolves symbols in any (transitively) linked dynamic libraries. "
+              "Source libraries are not recorded: dyld will re-search all "
+              "images at runtime and use the first definition found.">,
+     Group<grp_opts>;
+def twolevel_namespace : Flag<["-"], "twolevel_namespace">,
+     HelpText<"Resolves symbols in listed libraries only. Source libraries are "
+              "recorded in the symbol table.">,
+     Group<grp_opts>;
+def undefined : Separate<["-"], "undefined">,
+                MetaVarName<"<undefined>">,
+                HelpText<"Determines how undefined symbols are handled.">,
+                Group<grp_opts>;
 
 // main executable options
 def grp_main : OptionGroup<"opts">, HelpText<"MAIN EXECUTABLE OPTIONS">;
diff --git a/lld/lib/ReaderWriter/MachO/FlatNamespaceFile.h b/lld/lib/ReaderWriter/MachO/FlatNamespaceFile.h
new file mode 100644
index 00000000000..54710f21c53
--- /dev/null
+++ b/lld/lib/ReaderWriter/MachO/FlatNamespaceFile.h
@@ -0,0 +1,61 @@
+//===- lib/ReaderWriter/MachO/FlatNamespaceFile.h -------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_READER_WRITER_MACHO_FLAT_NAMESPACE_FILE_H
+#define LLD_READER_WRITER_MACHO_FLAT_NAMESPACE_FILE_H
+
+#include "lld/Core/SharedLibraryFile.h"
+#include "llvm/Support/Debug.h"
+
+namespace lld {
+namespace mach_o {
+
+//
+// A FlateNamespaceFile instance may be added as a resolution source of last
+// resort, depending on how -flat_namespace and -undefined are set.
+//
+class FlatNamespaceFile : public SharedLibraryFile {
+public:
+    FlatNamespaceFile(const MachOLinkingContext &context, bool warnOnUndef)
+      : SharedLibraryFile("flat namespace") { }
+
+  const SharedLibraryAtom *exports(StringRef name,
+                                   bool dataSymbolOnly) const override {
+    _sharedLibraryAtoms.push_back(
+      new (allocator()) MachOSharedLibraryAtom(*this, name, getDSOName(),
+                                               false));
+
+    return _sharedLibraryAtoms.back();
+  }
+
+  StringRef getDSOName() const override { return "flat-namespace"; }
+
+  const AtomVector<DefinedAtom> &defined() const override {
+    return _noDefinedAtoms;
+  }
+  const AtomVector<UndefinedAtom> &undefined() const override {
+    return _noUndefinedAtoms;
+  }
+
+  const AtomVector<SharedLibraryAtom> &sharedLibrary() const override {
+    return _sharedLibraryAtoms;
+  }
+
+  const AtomVector<AbsoluteAtom> &absolute() const override {
+    return _noAbsoluteAtoms;
+  }
+
+private:
+  mutable AtomVector<SharedLibraryAtom> _sharedLibraryAtoms;
+};
+
+} // namespace mach_o
+} // namespace lld
+
+#endif // LLD_READER_WRITER_MACHO_EXECUTABLE_ATOMS_H
diff --git a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
index c29bcdd7387..3b9406d745c 100644
--- a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
@@ -10,6 +10,7 @@
 #include "lld/ReaderWriter/MachOLinkingContext.h"
 #include "ArchHandler.h"
 #include "File.h"
+#include "FlatNamespaceFile.h"
 #include "MachONormalizedFile.h"
 #include "MachOPasses.h"
 #include "lld/Core/ArchiveLibraryFile.h"
@@ -143,10 +144,12 @@ MachOLinkingContext::MachOLinkingContext()
       _doNothing(false), _pie(false), _arch(arch_unknown), _os(OS::macOSX),
       _osMinVersion(0), _pageZeroSize(0), _pageSize(4096), _baseAddress(0),
       _stackSize(0), _compatibilityVersion(0), _currentVersion(0),
+      _flatNamespace(false), _undefinedMode(UndefinedMode::error),
       _deadStrippableDylib(false), _printAtoms(false), _testingFileUsage(false),
       _keepPrivateExterns(false), _demangle(false), _archHandler(nullptr),
       _exportMode(ExportMode::globals),
-      _debugInfoMode(DebugInfoMode::addDebugMap), _orderFileEntries(0) {}
+      _debugInfoMode(DebugInfoMode::addDebugMap), _orderFileEntries(0),
+      _flatNamespaceFile(nullptr) {}
 
 MachOLinkingContext::~MachOLinkingContext() {}
 
@@ -716,6 +719,15 @@ void MachOLinkingContext::createImplicitFiles(
 
   // Let writer add output type specific extras.
   writer().createImplicitFiles(result);
+
+  // If we're using flat namespace or undefinedMode is != error, add a
+  // FlatNamespaceFile instance. This will provide a SharedLibraryAtom for
+  // symbols that aren't defined elsewhere.
+  if (useFlatNamespace() && undefinedMode() != UndefinedMode::error) {
+    bool warnOnUndef = undefinedMode() == UndefinedMode::warning;
+    result.emplace_back(new mach_o::FlatNamespaceFile(*this, warnOnUndef));
+    _flatNamespaceFile = result.back().get();
+  }
 }
 
 
diff --git a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
index 908945d7f8a..bbf62de6102 100644
--- a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
@@ -1042,7 +1042,12 @@ void MachOFileLayout::buildBindInfo() {
     _bindingInfo.append_byte(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB
                             | entry.segIndex);
     _bindingInfo.append_uleb128(entry.segOffset);
-    _bindingInfo.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | entry.ordinal);
+    if (entry.ordinal > 0)
+      _bindingInfo.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
+                               (entry.ordinal & 0xF));
+    else
+      _bindingInfo.append_byte(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
+                               (entry.ordinal & 0xF));
     _bindingInfo.append_byte(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM);
     _bindingInfo.append_string(entry.symbolName);
     if (entry.addend != lastAddend) {
@@ -1062,7 +1067,12 @@ void MachOFileLayout::buildLazyBindInfo() {
     _lazyBindingInfo.append_byte(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB
                             | entry.segIndex);
     _lazyBindingInfo.append_uleb128Fixed(entry.segOffset, 5);
-    _lazyBindingInfo.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | entry.ordinal);
+    if (entry.ordinal > 0)
+      _lazyBindingInfo.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
+                                   (entry.ordinal & 0xF));
+    else
+      _lazyBindingInfo.append_byte(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
+                                   (entry.ordinal & 0xF));
     _lazyBindingInfo.append_byte(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM);
     _lazyBindingInfo.append_string(entry.symbolName);
     _lazyBindingInfo.append_byte(BIND_OPCODE_DO_BIND);
diff --git a/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp b/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp
index 35ff1e8d46a..9585691a8d3 100644
--- a/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp
@@ -855,7 +855,9 @@ std::error_code Util::addSymbols(const lld::File &atomFile,
     Symbol sym;
     uint16_t desc = 0;
     if (!rMode) {
-      uint8_t ordinal = dylibOrdinal(dyn_cast<SharedLibraryAtom>(ai.atom));
+      uint8_t ordinal = 0;
+      if (!_ctx.useFlatNamespace())
+        ordinal = dylibOrdinal(dyn_cast<SharedLibraryAtom>(ai.atom));
       llvm::MachO::SET_LIBRARY_ORDINAL(desc, ordinal);
     }
     sym.name  = ai.atom->name();
@@ -953,16 +955,28 @@ void Util::addDependentDylibs(const lld::File &atomFile,NormalizedFile &nFile) {
     DylibPathToInfo::iterator pos = _dylibInfo.find(loadPath);
     if (pos == _dylibInfo.end()) {
       DylibInfo info;
-      info.ordinal = ordinal++;
+      bool flatNamespaceAtom = &slAtom->file() == _ctx.flatNamespaceFile();
+
+      // If we're in -flat_namespace mode (or this atom came from the flat
+      // namespace file under -undefined dynamic_lookup) then use the flat
+      // lookup ordinal.
+      if (flatNamespaceAtom || _ctx.useFlatNamespace())
+        info.ordinal = BIND_SPECIAL_DYLIB_FLAT_LOOKUP;
+      else
+        info.ordinal = ordinal++;
       info.hasWeak = slAtom->canBeNullAtRuntime();
       info.hasNonWeak = !info.hasWeak;
       _dylibInfo[loadPath] = info;
-      DependentDylib depInfo;
-      depInfo.path = loadPath;
-      depInfo.kind = llvm::MachO::LC_LOAD_DYLIB;
-      depInfo.currentVersion = _ctx.dylibCurrentVersion(loadPath);
-      depInfo.compatVersion = _ctx.dylibCompatVersion(loadPath);
-      nFile.dependentDylibs.push_back(depInfo);
+
+      // Unless this was a flat_namespace atom, record the source dylib.
+      if (!flatNamespaceAtom) {
+        DependentDylib depInfo;
+        depInfo.path = loadPath;
+        depInfo.kind = llvm::MachO::LC_LOAD_DYLIB;
+        depInfo.currentVersion = _ctx.dylibCurrentVersion(loadPath);
+        depInfo.compatVersion = _ctx.dylibCompatVersion(loadPath);
+        nFile.dependentDylibs.push_back(depInfo);
+      }
     } else {
       if ( slAtom->canBeNullAtRuntime() )
         pos->second.hasWeak = true;
@@ -1180,7 +1194,9 @@ uint32_t Util::fileFlags() {
   if (_ctx.outputMachOType() == MH_OBJECT) {
     return MH_SUBSECTIONS_VIA_SYMBOLS;
   } else {
-    uint32_t flags = MH_DYLDLINK | MH_NOUNDEFS | MH_TWOLEVEL;
+    uint32_t flags = MH_DYLDLINK;
+    if (!_ctx.useFlatNamespace())
+        flags |= MH_TWOLEVEL | MH_NOUNDEFS;
     if ((_ctx.outputMachOType() == MH_EXECUTE) && _ctx.PIE())
       flags |= MH_PIE;
     if (_hasTLVDescriptors)
diff --git a/lld/test/mach-o/flat_namespace_undef_error.yaml b/lld/test/mach-o/flat_namespace_undef_error.yaml
new file mode 100644
index 00000000000..904b9c776e5
--- /dev/null
+++ b/lld/test/mach-o/flat_namespace_undef_error.yaml
@@ -0,0 +1,17 @@
+# RUN: not lld -flavor darwin -arch x86_64 -macosx_version_min 10.9 -flat_namespace -undefined error %s -o %t %p/Inputs/libSystem.yaml 2>&1 | FileCheck %s
+
+--- !native
+defined-atoms:
+  - name:            _main
+    scope:           global
+    content:         [ E9, 00, 00, 00, 00 ]
+    alignment:       16
+    references:
+      - kind:            branch32
+        offset:          1
+        target:          _bar
+undefined-atoms:
+  - name:            _bar
+
+# Make sure we error out for -flat_namespace -undefined error.
+# CHECK: Undefined symbol: : _bar
diff --git a/lld/test/mach-o/flat_namespace_undef_suppress.yaml b/lld/test/mach-o/flat_namespace_undef_suppress.yaml
new file mode 100644
index 00000000000..5152a1cd985
--- /dev/null
+++ b/lld/test/mach-o/flat_namespace_undef_suppress.yaml
@@ -0,0 +1,17 @@
+# RUN: lld -flavor darwin -arch x86_64 -macosx_version_min 10.9 -flat_namespace -undefined suppress %s -o %t %p/Inputs/libSystem.yaml
+#
+# Sanity check '-flat_namespace -undefined suppress'.
+# This should pass without error, even though '_bar' is undefined.
+
+--- !native
+defined-atoms:
+  - name:            _main
+    scope:           global
+    content:         [ E9, 00, 00, 00, 00 ]
+    alignment:       16
+    references:
+      - kind:            branch32
+        offset:          1
+        target:          _bar
+undefined-atoms:
+  - name:            _bar
diff --git a/lld/test/mach-o/twolevel_namespace_undef_dynamic_lookup.yaml b/lld/test/mach-o/twolevel_namespace_undef_dynamic_lookup.yaml
new file mode 100644
index 00000000000..190a4ede6d9
--- /dev/null
+++ b/lld/test/mach-o/twolevel_namespace_undef_dynamic_lookup.yaml
@@ -0,0 +1,17 @@
+# RUN: lld -flavor darwin -arch x86_64 -macosx_version_min 19.9 -twolevel_namespace -undefined dynamic_lookup %s -o %t %p/Inputs/libSystem.yaml
+#
+# Sanity check '-twolevel_namespace -undefined dynamic_lookup'.
+# This should pass without error, even though '_bar' is undefined.
+
+--- !native
+defined-atoms:
+  - name:            _main
+    scope:           global
+    content:         [ E9, 00, 00, 00, 00 ]
+    alignment:       16
+    references:
+      - kind:            branch32
+        offset:          1
+        target:          _bar
+undefined-atoms:
+  - name:            _bar
diff --git a/lld/test/mach-o/twolevel_namespace_undef_warning_suppress.yaml b/lld/test/mach-o/twolevel_namespace_undef_warning_suppress.yaml
new file mode 100644
index 00000000000..eeb01de5f70
--- /dev/null
+++ b/lld/test/mach-o/twolevel_namespace_undef_warning_suppress.yaml
@@ -0,0 +1,23 @@
+# RUN: not lld -flavor darwin -arch x86_64 -macosx_version_min 10.9 -twolevel_namespace -undefined warning %s -o %t %p/Inputs/libSystem.yaml 2>&1 | \
+# RUN:   FileCheck --check-prefix=CHECK-WARNING %s
+# RUN: not lld -flavor darwin -arch x86_64 -macosx_version_min 10.9 -twolevel_namespace -undefined suppress %s -o %t %p/Inputs/libSystem.yaml 2>&1 | \
+# RUN:   FileCheck --check-prefix=CHECK-SUPPRESS %s
+
+--- !native
+defined-atoms:
+  - name:            _main
+    scope:           global
+    content:         [ E9, 00, 00, 00, 00 ]
+    alignment:       16
+    references:
+      - kind:            branch32
+        offset:          1
+        target:          _bar
+undefined-atoms:
+  - name:            _bar
+
+# Make sure that the driver issues an error diagnostic about this combination
+# being invalid.
+#
+# CHECK-WARNING:  can't use -undefined warning or suppress with -twolevel_namespace
+# CHECK-SUPPRESS: can't use -undefined warning or suppress with -twolevel_namespace
\ No newline at end of file