[lld/mac] Add support for -flat_namespace

[thakis]

Summary

-flat_namespace makes lld emit binaries that use name lookup that's more in
line with other POSIX systems: Instead of looking up symbols as (dylib,name)
pairs by dyld, they're instead looked up just by name.

-flat_namespace has three effects:

1. MH_TWOLEVEL and MH_NNOUNDEFS are no longer set in the Mach-O header
2. All symbols use BIND_SPECIAL_DYLIB_FLAT_LOOKUP as ordinal
3. When a dylib is added to the link, its dependent dylibs are also added, so that lld can verify that no undefined symbols remain at the end of a link with -flat_namespace. These transitive dylibs are added for symbol resolution, but they are not emitted in LC_LOAD_COMMANDs.

-undefined with -flat_namespace still isn't implemented. Before this change,
it was impossible to hit that combination because -flat_namespace caused a
diagnostic. Now that it no longer does, emit a dedicated temporary diagnostic
when both flags are used.

[int3]

lld/MachO/InputFiles.cpp

705

hm is the :: prefix necessary?

lld/test/MachO/flat-namespace.s

38–39

does llvm-objdump --syms or llvm-readobj print anything better?

lld/test/MachO/header.s

15–16

ultra nit: align the header

[int3]

lld/MachO/InputFiles.cpp

705

judging from the test failures, I guess we need to account for syslibroot here too

[thakis]

Thanks!

lld/MachO/InputFiles.cpp

705

hm is the :: prefix necessary?

Yes, else ADL makes this try to use lld::macho::loadDyib() (from Driver.h, in DriverUtils.cpp)

705

judging from the test failures, I guess we need to account for syslibroot here too

ah, annoying. will try to do that…

lld/test/MachO/flat-namespace.s

38–39

llvm-objdump --syms doesn't print it. llvm-readobj has it as Flags [ (0xFE00). obj2yaml also prints it as n_desc: 65024.

I think we definitely want to test nm here since that's what end users are most likely to use. Want me to add a readobj/yaml2obj test in addition to what's here, or nah?

lld/test/MachO/header.s

15–16

Done, but it's not aligned in llvm-objdump output :P

[int3]

lld/test/MachO/flat-namespace.s

38–39

A readobj test would be nice :)

[thakis]

readobj test; honor syslibroot

[thakis]

Hm, still fails with

lld: error: unable to locate library '/usr/lib/libSystem.B.dylib' loaded from '/mnt/disks/ssd0/agent/llvm-project/build/tools/lld/test/MachO/Output/flat-namespace.s.tmp/baz.dylib' for -flat_namespace

I think that's because lld/test/MachO/Inputs/MacOSX.sdk/usr/lib/libSystem.tbd contains /usr/lib/libSystem.B.dylib (note .B) but we don't have a lld/test/MachO/Inputs/MacOSX.sdk/usr/lib/libSystem.B.tbd. In Real Life, libSystem.dylib symlinks to libSystem.B.dylib. Symlinks are tricky because Windows. Options:

1. Make a copy of lld/test/MachO/Inputs/MacOSX.sdk/usr/lib/libSystem.tbd at lld/test/MachO/Inputs/MacOSX.sdk/usr/lib/libSystem.B.tbd and check it in. Somewhat ugly because two copies of that file checked in, but the file basically never changes.
2. In the test, make a temp dummy dir, copy lld/test/MachO/Inputs/MacOSX.sdk/usr/lib/libSystem.tbd to both %t/mysysroot/libSystem.tbd and %t/mysysroot/libSystem.B.tbd, and use that as -libsysroot. Somewhat ugly because the test doesn't "know" about libsysroot since that comes in via %lld.

Opinions? I weakly lean towards 1.

[int3]

How about just removing all references to libSystem.B.dylib and just use libSystem.dylib everywhere? I don't think we have anything in our code or tests that actually cares that it's symlinked

[thakis]

In D97641#2595270, @int3 wrote:

How about just removing all references to libSystem.B.dylib and just use libSystem.dylib everywhere? I don't think we have anything in our code or tests that actually cares that it's symlinked

Hey, that's a great idea. Landed with that in a separate preparatory commit (3e6b6cee00819d256f30e84aec7ae634e0725534) :)

lld/MachO/Driver.cpp

bool macho::link(ArrayRef<const char *> argsArr, bool canExitEarly,
   if (const opt::Arg *arg = args.getLastArg(OPT_static, OPT_dynamic))
     config->staticLink = (arg->getOption().getID() == OPT_static);
 
   if (const opt::Arg *arg =
           args.getLastArg(OPT_flat_namespace, OPT_twolevel_namespace)) {
     config->namespaceKind = arg->getOption().getID() == OPT_twolevel_namespace
                                 ? NamespaceKind::twolevel
                                 : NamespaceKind::flat;
-    if (config->namespaceKind == NamespaceKind::flat) {
-      warn("Option '" + arg->getOption().getPrefixedName() +
-           "' is not yet implemented. Stay tuned...");
-      config->namespaceKind = NamespaceKind::twolevel;
-    }
   }
 
   config->systemLibraryRoots = getSystemLibraryRoots(args);
   config->librarySearchPaths =
       getLibrarySearchPaths(args, config->systemLibraryRoots);
   config->frameworkSearchPaths =
       getFrameworkSearchPaths(args, config->systemLibraryRoots);
   if (const opt::Arg *arg =

lld/MachO/InputFiles.cpp

parseTrie(buf + c->export_off, c->export_size,
                 symbols.push_back(symtab->addDylib(
                     saver.save(name), exportingFile, isWeakDef, isTlv));
               });
   } else {
     error("LC_DYLD_INFO_ONLY not found in " + toString(this));
     return;
   }
 
-  if (hdr->flags & MH_NO_REEXPORTED_DYLIBS)
-    return;
-
   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);
     p += cmd->cmdsize;
-    if (cmd->cmd != LC_REEXPORT_DYLIB)
-      continue;
 
+    if (!(hdr->flags & MH_NO_REEXPORTED_DYLIBS) &&
+        cmd->cmd == LC_REEXPORT_DYLIB) {
       auto *c = reinterpret_cast<const dylib_command *>(cmd);
       StringRef reexportPath =
           reinterpret_cast<const char *>(c) + read32le(&c->dylib.name);
       loadReexport(reexportPath, umbrella);
     }
+
+    // FIXME: What about LC_LOAD_UPWARD_DYLIB, LC_LAZY_LOAD_DYLIB,
+    // LC_LOAD_WEAK_DYLIB, LC_REEXPORT_DYLIB (..are reexports from dylibs with
+    // MH_NO_REEXPORTED_DYLIBS loaded for -flat_namespace)?
+    if (config->namespaceKind == NamespaceKind::flat &&
+        cmd->cmd == LC_LOAD_DYLIB) {
+      auto *c = reinterpret_cast<const dylib_command *>(cmd);
+      StringRef dylibPath =
+          reinterpret_cast<const char *>(c) + read32le(&c->dylib.name);
+      ::loadDylib(dylibPath, umbrella);
+    }
+  }
 }
 
 DylibFile::DylibFile(const InterfaceFile &interface, DylibFile *umbrella,
                      bool isBundleLoader)
     : InputFile(DylibKind, interface), refState(RefState::Unreferenced),
       isBundleLoader(isBundleLoader) {
   // FIXME: Add test for the missing TBD code path.
 

lld/MachO/Options.td

def alias : MultiArg<["-"], "alias", 2>,
      Group<grp_resolve>;
 def alias_list : Separate<["-"], "alias_list">,
      MetaVarName<"<file>">,
      HelpText<"Create symbol aliases specified in <file>">,
      Flags<[HelpHidden]>,
      Group<grp_resolve>;
 def flat_namespace : Flag<["-"], "flat_namespace">,
      HelpText<"Resolve symbols from all dylibs, both direct and transitive. Do not record source libraries: dyld must re-search at runtime and use the first definition found">,
-     Flags<[HelpHidden]>,
      Group<grp_resolve>;
 def twolevel_namespace : Flag<["-"], "twolevel_namespace">,
      HelpText<"Make dyld look up symbols by (dylib,name) pairs (default)">,
      Group<grp_resolve>;
 def u : Separate<["-"], "u">,
      MetaVarName<"<symbol>">,
      HelpText<"Require that <symbol> be defined for the link to succeed">,
      Group<grp_resolve>;

lld/MachO/SymbolTable.cpp

 void lld::macho::treatUndefinedSymbol(const Undefined &sym) {
   std::string message = "undefined symbol: " + toString(sym);
   std::string fileName = toString(sym.getFile());
 
   if (!fileName.empty())
     message += "\n>>> referenced by " + fileName;
   switch (config->undefinedSymbolTreatment) {
   case UndefinedSymbolTreatment::suppress:
+    error("-undefined suppress unimplemented");
     break;
   case UndefinedSymbolTreatment::error:
     error(message);
     break;
   case UndefinedSymbolTreatment::warning:
     warn(message);
+    error("-undefined warning unimplemented");
     break;
   case UndefinedSymbolTreatment::dynamic_lookup:
     error("dynamic_lookup unimplemented for " + message);
     break;
   case UndefinedSymbolTreatment::unknown:
     llvm_unreachable("unknown -undefined TREATMENT");
   }
 }
 
 SymbolTable *macho::symtab;

lld/MachO/SyntheticSections.cpp

 void MachHeaderSection::writeTo(uint8_t *buf) const {
   auto *hdr = reinterpret_cast<MachO::mach_header_64 *>(buf);
   hdr->magic = MachO::MH_MAGIC_64;
   hdr->cputype = target->cpuType;
   hdr->cpusubtype = cpuSubtype();
   hdr->filetype = config->outputType;
   hdr->ncmds = loadCommands.size();
   hdr->sizeofcmds = sizeOfCmds;
-  hdr->flags = MachO::MH_NOUNDEFS | MachO::MH_DYLDLINK | MachO::MH_TWOLEVEL;
+  hdr->flags = MachO::MH_DYLDLINK;
+
+  if (config->namespaceKind == NamespaceKind::twolevel)
+    hdr->flags |= MachO::MH_NOUNDEFS | MachO::MH_TWOLEVEL;
 
   if (config->outputType == MachO::MH_DYLIB && !config->hasReexports)
     hdr->flags |= MachO::MH_NO_REEXPORTED_DYLIBS;
 
   if (config->outputType == MachO::MH_EXECUTE && config->isPic)
     hdr->flags |= MachO::MH_PIE;
 
   if (in.exports->hasWeakSymbol || in.weakBinding->hasNonWeakDefinition())
os << flags << sym->getName() << '\0'
      << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER)
      << static_cast<uint8_t>(BIND_OPCODE_DO_BIND);
   // DO_BIND causes dyld to both perform the binding and increment the offset
   lastBinding.offset += WordSize;
 }
 
 // Non-weak bindings need to have their dylib ordinal encoded as well.
 static int16_t ordinalForDylibSymbol(const DylibSymbol &dysym) {
-  return dysym.isDynamicLookup() ? MachO::BIND_SPECIAL_DYLIB_FLAT_LOOKUP
-                                 : dysym.getFile()->ordinal;
+  return config->namespaceKind == NamespaceKind::flat || dysym.isDynamicLookup()
+             ? MachO::BIND_SPECIAL_DYLIB_FLAT_LOOKUP
 }
 
 static void encodeDylibOrdinal(int16_t ordinal, raw_svector_ostream &os) {
   using namespace llvm::MachO;
   if (ordinal <= 0) {
     os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
                                (ordinal & BIND_IMMEDIATE_MASK));
   } else if (ordinal <= BIND_IMMEDIATE_MASK) {
if (auto *defined = dyn_cast<Defined>(entry.sym)) {
         nList->n_type = scope | MachO::N_SECT;
         nList->n_sect = defined->isec->parent->index;
         // For the N_SECT symbol type, n_value is the address of the symbol
         nList->n_value = defined->getVA();
       }
       nList->n_desc |= defined->isExternalWeakDef() ? MachO::N_WEAK_DEF : 0;
     } else if (auto *dysym = dyn_cast<DylibSymbol>(entry.sym)) {
       uint16_t n_desc = nList->n_desc;
-      if (dysym->isDynamicLookup())
+      int16_t ordinal = ordinalForDylibSymbol(*dysym);
+      if (ordinal == MachO::BIND_SPECIAL_DYLIB_FLAT_LOOKUP)
         MachO::SET_LIBRARY_ORDINAL(n_desc, MachO::DYNAMIC_LOOKUP_ORDINAL);
-      else if (dysym->getFile()->isBundleLoader)
+      else if (ordinal == MachO::BIND_SPECIAL_DYLIB_MAIN_EXECUTABLE)
         MachO::SET_LIBRARY_ORDINAL(n_desc, MachO::EXECUTABLE_ORDINAL);
-      else
-        MachO::SET_LIBRARY_ORDINAL(
-            n_desc, static_cast<uint8_t>(dysym->getFile()->ordinal));
+      else {
+        assert(ordinal > 0);
+        MachO::SET_LIBRARY_ORDINAL(n_desc, static_cast<uint8_t>(ordinal));
+      }
 
       nList->n_type = MachO::N_EXT;
       n_desc |= dysym->isWeakDef() ? MachO::N_WEAK_DEF : 0;
       n_desc |= dysym->isWeakRef() ? MachO::N_WEAK_REF : 0;
       nList->n_desc = n_desc;
     }
     ++nList;
   }

lld/test/MachO/flat-namespace.s

+# REQUIRES: x86
+# RUN: rm -rf %t
+# RUN: split-file %s %t
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/foo.o %t/foo.s
+# RUN: %lld -dylib -o %t/foo.dylib %t/foo.o
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/bar.o %t/bar.s
+# RUN: %lld -lSystem -dylib -o %t/bar.dylib %t/bar.o %t/foo.dylib
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/baz.o %t/baz.s
+# RUN: %lld -lSystem -dylib -o %t/baz.dylib %t/baz.o %t/bar.dylib
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/main.o %t/main.s
+
+# With flat_namespace, the linker automatically looks in foo.dylib and
+# bar.dylib too, but it doesn't add a LC_LOAD_DYLIB for it.
+# RUN: %lld -flat_namespace -lSystem %t/main.o %t/baz.dylib -o %t/out
+# RUN: llvm-objdump --macho --all-headers %t/out \
+# RUN:     | FileCheck --check-prefix=HEADERBITS %s
+# RUN: llvm-objdump --macho --bind --lazy-bind --weak-bind %t/out \
+# RUN:     | FileCheck --check-prefix=FLAT %s
+# RUN: llvm-nm -m %t/out | FileCheck --check-prefix=FLATSYM %s
+
+# HEADERBITS-NOT: NOUNDEFS
+# HEADERBITS-NOT: TWOLEVEL
+# HEADERBITS: DYLDLINK
+# HEADERBITS-NOT: foo.dylib
+# HEADERBITS-NOT: bar.dylib
+
+# FLAT: Bind table:
+# FLAT: __DATA_CONST __got          0x{{[0-9a-f]*}} pointer         0 flat-namespace   dyld_stub_binder
+# FLAT: Lazy bind table:
+# FLAT-DAG: __DATA   __la_symbol_ptr    0x{{[0-9a-f]*}} flat-namespace   _bar
+# FLAT-DAG: __DATA   __la_symbol_ptr    0x{{[0-9a-f]*}} flat-namespace   _baz
+# FLAT-DAG: __DATA   __la_symbol_ptr    0x{{[0-9a-f]*}} flat-namespace   _foo
+
+# No "(dynamically looked up)" because llvm-nm -m doesn't print that
+# for files without MH_TWOLEVEL for some reason.
+# FLATSYM: (undefined) external _bar
+# FLATSYM: (undefined) external _baz
+# FLATSYM: (undefined) external _foo
+
+# Undefined symbols should still cause errors by default.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     -o %t/main-with-undef.o %t/main-with-undef.s
+# RUN: not %lld -flat_namespace -lSystem %t/main-with-undef.o %t/bar.dylib \
+# RUN:     -o %t/out 2>&1 | FileCheck --check-prefix=UNDEF %s
+# UNDEF: error: undefined symbol: _quux
+
+#--- foo.s
+.globl _foo
+_foo:
+  ret
+
+#--- bar.s
+.globl _bar
+_bar:
+  callq _foo
+  ret
+
+#--- baz.s
+.globl _baz
+_baz:
+  callq _bar
+  ret
+
+#--- main.s
+.globl _main
+_main:
+  callq _foo
+  callq _bar
+  callq _baz
+  ret
+
+#--- main-with-undef.s
+.globl _main
+_main:
+  callq _foo
+  callq _bar
+  callq _baz
+  callq _quux
+  ret

lld/test/MachO/header.s

 # REQUIRES: x86, aarch64
 # RUN: rm -rf %t && mkdir -p %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/x86_64-test.o
 # RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %s -o %t/arm64-test.o
 # RUN: %lld -arch x86_64 -platform_version macos 10.5.0 11.0 -o %t/x86-64-executable %t/x86_64-test.o
 # RUN: %lld -arch arm64 -o %t/arm64-executable %t/arm64-test.o
 # RUN: %lld -arch x86_64 -dylib -o %t/x86-64-dylib %t/x86_64-test.o
 # RUN: %lld -arch arm64  -dylib -o %t/arm64-dylib %t/arm64-test.o
 
 # RUN: llvm-objdump --macho --all-headers %t/x86-64-executable | FileCheck %s -DCAPS=LIB64
 # RUN: llvm-objdump --macho --all-headers %t/arm64-executable | FileCheck %s -DCAPS=0x00
 # RUN: llvm-objdump --macho --all-headers %t/x86-64-dylib | FileCheck %s -DCAPS=0x00
 # RUN: llvm-objdump --macho --all-headers %t/arm64-dylib | FileCheck %s -DCAPS=0x00
 
 # CHECK:      magic        cputype cpusubtype  caps    filetype
-# CHECK-NEXT: MH_MAGIC_64  {{.*}}         ALL  [[CAPS]]   {{.*}}
+# CHECK-NEXT: MH_MAGIC_64  {{.*}}         ALL  [[CAPS]]   {{.*}} TWOLEVEL
 
 .globl _main
 _main:
   ret