[lld/mac] Add some support for dynamic lookup symbols, and implement -U

[thakis]

Summary

Dynamic lookup symbols are symbols that work like dynamic symbols
in ELF: They're not bound to a dylib like normal Mach-O twolevel lookup
symbols, but they live in a global pool and dyld resolves them against
exported symbols from all loaded dylibs.

This adds support for dynamical lookup symbols to lld/mac. They are
represented as DylibSymbols with file set to nullptr.

This also uses this support to implement the -U flag, which makes
a specific symbol that's undefined at the end of the link a
dynamic lookup symbol.

For -U, it'd be sufficient to just to a pass over remaining undefined symbols
at the end of the link and to replace them with dynamic lookup symbols then.
But I'd like to use this code to implement flat_namespace too, and that will
require real support for resolving dynamic lookup symbols in SymbolTable. So
this patch adds this now already.

While writing tests for this, I noticed that we didn't set N_WEAK_DEF in the
symbol table for DylibSymbols, so this fixes that too.

---

In addition to -flat_namespace, this will also be useful for implementing
-undefined dynamic_lookup, and, with -flat_namespace, -undefined warning
and -undefined suppress – but for these, the pass at the end would've sufficed too.

This isn't 100% done, there are a few XXXs left, but I'm out of evening, and what's
left is pretty basic. So I'm sending it out now for better timezone overlap :)

[thakis]

lld/MachO/SyntheticSections.cpp

537

I'll extract the ordinal encoding code here and further up into a shared helper function before landing this change if that sounds ok. It's the same code down here and up there, and it needs the same change now.

lld/MachO/Writer.cpp

456

This is a remainder from an old version of the patch, where I tried to make dynamic lookup symbols weak. But that didn't work due to this getting set, so I changed SymbolTable to make non-dynamic-lookup symbols always win over them. So this XXX is already done (and covered by tests).

458

I was debating if I should make a new Symbol subclass for DylibSymbols that don't come from a file, but in most places both dynamic lookup symbols and dylib-bound symbols will be handled the same way, so I decided against the new class.

[int3]

lld/MachO/SyntheticSections.cpp

268–278

you should pull and rebase past D95913: [lld-macho] Implement -bundle_loader

269

that would be BIND_SPECIAL_DYLIB_FLAT_LOOKUP

lld/test/MachO/U_dynamic_lookup.s

1

nit: use hyphens instead of underscores in test file names

[thakis]

address comments and rebase

[thakis]

Ok, this is ready now :)

lld/MachO/SyntheticSections.cpp

268–278

Hey, nice :)

[int3]

lgtm!

lld/MachO/Driver.cpp

bool macho::link(ArrayRef<const char *> argsArr, bool canExitEarly,
 
   config->entry = symtab->addUndefined(args.getLastArgValue(OPT_e, "_main"),
                                        /*file=*/nullptr,
                                        /*isWeakRef=*/false);
   for (auto *arg : args.filtered(OPT_u)) {
     config->explicitUndefineds.push_back(symtab->addUndefined(
         arg->getValue(), /*file=*/nullptr, /*isWeakRef=*/false));
   }
+
+  for (auto *arg : args.filtered(OPT_U))
+    symtab->addDynamicLookup(arg->getValue());
+
   config->outputFile = args.getLastArgValue(OPT_o, "a.out");
   config->installName =
       args.getLastArgValue(OPT_install_name, config->outputFile);
   config->headerPad = args::getHex(args, OPT_headerpad, /*Default=*/32);
   config->headerPadMaxInstallNames =
       args.hasArg(OPT_headerpad_max_install_names);
   config->printEachFile = args.hasArg(OPT_t);
   config->printWhyLoad = args.hasArg(OPT_why_load);

lld/MachO/Options.td

def flat_namespace : Flag<["-"], "flat_namespace">,
      Group<grp_resolve>;
 def u : Separate<["-"], "u">,
      MetaVarName<"<symbol>">,
      HelpText<"Require that <symbol> be defined for the link to succeed">,
      Group<grp_resolve>;
 def U : Separate<["-"], "U">,
      MetaVarName<"<symbol>">,
      HelpText<"Allow <symbol> to have no definition">,
-     Flags<[HelpHidden]>,
      Group<grp_resolve>;
 def undefined : Separate<["-"], "undefined">,
      MetaVarName<"<treatment>">,
      HelpText<"Handle undefined symbols according to <treatment>: error, warning, suppress, or dynamic_lookup (default is error)">,
      Group<grp_resolve>;
 def rpath : Separate<["-"], "rpath">,
      MetaVarName<"<path>">,
      HelpText<"Add <path> to dyld search list for dylibs with load path prefix `@rpath/'">,

lld/MachO/SymbolTable.h

Symbol *addDefined(StringRef name, InputFile *, InputSection *,
                      uint32_t value, bool isWeakDef, bool isPrivateExtern);
 
   Symbol *addUndefined(StringRef name, InputFile *, bool isWeakRef);
 
   Symbol *addCommon(StringRef name, InputFile *, uint64_t size, uint32_t align,
                     bool isPrivateExtern);
 
   Symbol *addDylib(StringRef name, DylibFile *file, bool isWeakDef, bool isTlv);
+  Symbol *addDynamicLookup(StringRef name);
 
   Symbol *addLazy(StringRef name, ArchiveFile *file,
                   const llvm::object::Archive::Symbol &sym);
 
   Symbol *addDSOHandle(const MachHeaderSection *);
 
   ArrayRef<Symbol *> getSymbols() const { return symVector; }
   Symbol *find(StringRef name);

lld/MachO/SymbolTable.cpp

if (auto *defined = dyn_cast<Defined>(s)) {
         defined->overridesWeakDef = true;
     } else if (auto *undefined = dyn_cast<Undefined>(s)) {
       refState = undefined->refState;
     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
       refState = dysym->refState;
     }
   }
 
+  bool isDynamicLookup = file == nullptr;
   if (wasInserted || isa<Undefined>(s) ||
-      (isa<DylibSymbol>(s) && !isWeakDef && s->isWeakDef()))
+      (isa<DylibSymbol>(s) &&
+       ((!isWeakDef && s->isWeakDef()) ||
+        (!isDynamicLookup && cast<DylibSymbol>(s)->isDynamicLookup()))))
     replaceSymbol<DylibSymbol>(s, file, name, isWeakDef, refState, isTlv);
 
   return s;
 }
 
+Symbol *SymbolTable::addDynamicLookup(StringRef name) {
+  return addDylib(name, /*file=*/nullptr, /*isWeakDef=*/false, /*isTlv=*/false);
+}
+
 Symbol *SymbolTable::addLazy(StringRef name, ArchiveFile *file,
                              const object::Archive::Symbol &sym) {
   Symbol *s;
   bool wasInserted;
   std::tie(s, wasInserted) = insert(name);
 
   if (wasInserted)
     replaceSymbol<LazySymbol>(s, file, sym);
   else if (isa<Undefined>(s) || (isa<DylibSymbol>(s) && s->isWeakDef()))
     file->fetch(sym);
   return s;
 }
 
 Symbol *SymbolTable::addDSOHandle(const MachHeaderSection *header) {
   Symbol *s;
   bool wasInserted;
   std::tie(s, wasInserted) = insert(DSOHandle::name);
   if (!wasInserted) {
     // FIXME: Make every symbol (including absolute symbols) contain a
     // reference to their originating file, then add that file name to this
-    // error message.
+    // error message. dynamic_lookup symbols don't have an originating file.
     if (isa<Defined>(s))
       error("found defined symbol with illegal name " + DSOHandle::name);
   }
   replaceSymbol<DSOHandle>(s, header);
   return s;
 }
 
 void lld::macho::treatUndefinedSymbol(const Undefined &sym) {

lld/MachO/Symbols.h

DylibSymbol(DylibFile *file, StringRefZ name, bool isWeakDef,
               RefState refState, bool isTlv)
       : Symbol(DylibKind, name, file), refState(refState), weakDef(isWeakDef),
         tlv(isTlv) {}
 
   bool isWeakDef() const override { return weakDef; }
   bool isWeakRef() const override { return refState == RefState::Weak; }
   bool isReferenced() const { return refState != RefState::Unreferenced; }
   bool isTlv() const override { return tlv; }
+  bool isDynamicLookup() const { return file == nullptr; }
   bool hasStubsHelper() const { return stubsHelperIndex != UINT32_MAX; }
-  DylibFile *getFile() const { return cast<DylibFile>(file); }
+
+  DylibFile *getFile() const {
+    assert(!isDynamicLookup());
+    return cast<DylibFile>(file);
+  }
+  void setFile(DylibFile *f) { file = f; }
 
   static bool classof(const Symbol *s) { return s->kind() == DylibKind; }
 
   uint32_t stubsHelperIndex = UINT32_MAX;
   uint32_t lazyBindOffset = UINT32_MAX;
 
   RefState refState : 2;
 

lld/MachO/SyntheticSections.cpp

 BindingSection::BindingSection()
     : LinkEditSection(segment_names::linkEdit, section_names::binding) {}
 
 namespace {
 struct Binding {
   OutputSegment *segment = nullptr;
   uint64_t offset = 0;
   int64_t addend = 0;
-  uint8_t ordinal = 0;
+  int32_t ordinal = 0;
 };
 } // namespace
 
 // Encode a sequence of opcodes that tell dyld to write the address of symbol +
 // addend at osec->addr + outSecOff.
 //
 // The bind opcode "interpreter" remembers the values of each binding field, so
 // we only need to encode the differences between bindings. Hence the use of
static void encodeBinding(const Symbol *sym, const OutputSection *osec,
   // 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 void encodeDylibOrdinal(const DylibSymbol *dysym, Binding &lastBinding,
                                raw_svector_ostream &os) {
   using namespace llvm::MachO;
-  if (lastBinding.ordinal != dysym->getFile()->ordinal) {
-    if (dysym->getFile()->ordinal <= BIND_IMMEDIATE_MASK) {
-      os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
-                                 dysym->getFile()->ordinal);
+
+  // XXX named constant for -2
+  int32_t ordinal = dysym->isDynamicLookup() ? -2 : dysym->getFile()->ordinal;
+
+  if (lastBinding.ordinal != ordinal) {
+    if (ordinal < 0) {
+      assert(ordinal == -2);
+      // XXX named constant for 0xe (but it's just -2 in 4 bits two's complement)
+      os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM | 0xe);
+    } else if (dysym->getFile()->ordinal <= BIND_IMMEDIATE_MASK) {
+      os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | ordinal);
     } else {
       os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
-      encodeULEB128(dysym->getFile()->ordinal, os);
+      encodeULEB128(ordinal, os);
     }
-    lastBinding.ordinal = dysym->getFile()->ordinal;
+    lastBinding.ordinal = ordinal;
   }
 }
 
 static void encodeWeakOverride(const Defined *defined,
                                raw_svector_ostream &os) {
   using namespace llvm::MachO;
   os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM |
                              BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION)

 uint32_t LazyBindingSection::encode(const DylibSymbol &sym) {
   uint32_t opstreamOffset = contents.size();
   OutputSegment *dataSeg = in.lazyPointers->parent;
   os << static_cast<uint8_t>(MachO::BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                              dataSeg->index);
   uint64_t offset = in.lazyPointers->addr - dataSeg->firstSection()->addr +
                     sym.stubsIndex * WordSize;
   encodeULEB128(offset, os);
-  if (sym.getFile()->ordinal <= MachO::BIND_IMMEDIATE_MASK) {
+
+  // XXX named constant for -2
+  int32_t ordinal = sym.isDynamicLookup() ? -2 : sym.getFile()->ordinal;
+
+  if (ordinal < 0) {
+    assert(ordinal == -2);
+    // XXX named constant for 0xe (but it's just -2 in 4 bits two's complement)
+    os << static_cast<uint8_t>(MachO::BIND_OPCODE_SET_DYLIB_SPECIAL_IMM | 0xe);
+  } else if (ordinal <= MachO::BIND_IMMEDIATE_MASK) {
     os << static_cast<uint8_t>(MachO::BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
-                               sym.getFile()->ordinal);
+                               ordinal);
   } else {
     os << static_cast<uint8_t>(MachO::BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
-    encodeULEB128(sym.getFile()->ordinal, os);
+    encodeULEB128(ordinal, os);
   }
 
   uint8_t flags = MachO::BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
   if (sym.isWeakRef())
     flags |= MachO::BIND_SYMBOL_FLAGS_WEAK_IMPORT;
 
   os << flags << sym.getName() << '\0'
      << static_cast<uint8_t>(MachO::BIND_OPCODE_DO_BIND)
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())
+        MachO::SET_LIBRARY_ORDINAL(n_desc, MachO::DYNAMIC_LOOKUP_ORDINAL);
+      else
+        // XXX this would do the right thing for isDynamicLookup() if
+        // we got an ordinal of -2 here
         MachO::SET_LIBRARY_ORDINAL(n_desc, dysym->getFile()->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;
   }
 }
 
 IndirectSymtabSection::IndirectSymtabSection()

lld/MachO/Writer.cpp

for (InputSection *isec : inputSections) {
     }
   }
 }
 
 void Writer::scanSymbols() {
   for (const macho::Symbol *sym : symtab->getSymbols()) {
     if (const auto *defined = dyn_cast<Defined>(sym)) {
       if (defined->overridesWeakDef)
-        in.weakBinding->addNonWeakDefinition(defined);
+        in.weakBinding->addNonWeakDefinition(defined); // XXX do i want this for dynamics?
     } else if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
+      if (dysym->isDynamicLookup()) // XXX votes for separate class
+        continue;
       dysym->getFile()->refState =
           std::max(dysym->getFile()->refState, dysym->refState);
     }
   }
 }
 
 void Writer::createLoadCommands() {
   uint8_t segIndex = 0;

lld/test/MachO/U_dynamic_lookup.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/main.o %t/main.s
+
+# _foo starts out as a (non-weak) dynamically looked up symbol and is merged
+# against the Undefined from foo.o. _bar isn't referenced in any object file,
+# but starts out as Undefined because of the -u flag. _baz isn't referenced
+# at all.
+# RUN: %lld -lSystem %t/main.o -U _foo -U _bar -u _bar -U _baz -o %t/out
+# RUN: llvm-objdump --macho --lazy-bind %t/out | FileCheck --check-prefix=DYNAMIC %s
+# RUN: llvm-nm -m %t/out | FileCheck --check-prefix=DYNAMICSYM %s
+
+# Same thing should happen if _foo starts out as an Undefined.
+# `-U _foo` being passed twice shouldn't have an effect either.
+# RUN: %lld -lSystem %t/main.o -u _foo -U _foo -U _foo -u _bar -U _bar -U _baz -o %t/out
+# RUN: llvm-objdump --macho --lazy-bind %t/out | FileCheck --check-prefix=DYNAMIC %s
+# RUN: llvm-nm -m %t/out | FileCheck --check-prefix=DYNAMICSYM %s
+
+# Unreferenced dynamic lookup symbols don't make it into the bind tables, but
+# they do make it into the symbol table in ld64 if they're an undefined from -u
+# for some reason. lld happens to have the same behavior when no explicit code
+# handles this case, so match ld64's behavior.
+
+# DYNAMIC-NOT: _bar
+# DYNAMIC-NOT: _baz
+# DYNAMIC: flat-namespace   _foo
+
+# DYNAMICSYM:      (undefined) external _bar (dynamically looked up)
+# DYNAMICSYM-NOT:      (undefined) external _bar (dynamically looked up)
+# DYNAMICSYM-NEXT: (undefined) external _foo (dynamically looked up)
+
+# Test with a Defined. Here, foo.o provides _foo and the symbol doesn't need
+# to be imported.
+# RUN: %lld -lSystem %t/main.o %t/foo.o -U _foo -o %t/out
+# RUN: llvm-objdump --macho --lazy-bind %t/out | FileCheck --check-prefix=NOTDYNAMIC %s
+
+# NOTDYNAMIC-NOT: _foo
+
+# Here, foo.dylib provides _foo and the symbol doesn't need to be imported
+# dynamically.
+# RUN: %lld -lSystem %t/main.o %t/foo.dylib -U _foo -o %t/out
+# RUN: llvm-objdump --macho --lazy-bind %t/out | FileCheck --check-prefix=TWOLEVEL %s
+# RUN: llvm-nm -m %t/out | FileCheck --check-prefix=TWOLEVELSYM %s
+
+# TWOLEVEL: foo              _foo
+# TWOLEVELSYM: (undefined) external _foo (from foo)
+
+# Test resolving dynamic lookup symbol with weak defined.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/weak-foo.o %t/weak-foo.s
+# RUN: %lld -dylib -o %t/weak-foo.dylib %t/weak-foo.o -U _foo
+# RUN: llvm-objdump --macho --bind --lazy-bind --weak-bind %t/weak-foo.dylib | FileCheck --check-prefix=WEAKDEF %s
+# RUN: llvm-nm -m %t/weak-foo.dylib | FileCheck --check-prefix=WEAKDEFSYM %s
+# WEAKDEF-NOT: _foo
+# WEAKDEFSYM: weak external _foo
+
+# Same if foo.dylib provides _foo weakly, except that the symbol is weak then.
+# RUN: %lld -lSystem %t/main.o %t/weak-foo.dylib -U _foo -o %t/out
+# RUN: llvm-objdump --macho --bind --lazy-bind --weak-bind %t/out | FileCheck --check-prefix=TWOLEVELWEAK %s
+# RUN: llvm-nm -m %t/out | FileCheck --check-prefix=TWOLEVELWEAKSYM %s
+
+# TWOLEVELWEAK-LABEL: Bind table:
+# TWOLEVELWEAK:       __DATA        __la_symbol_ptr 0x[[#%x,ADDR:]]   pointer 0 weak-foo    _foo
+# TWOLEVELWEAK-LABEL: Lazy bind table:
+# TWOLEVELWEAK-NOT:   weak-foo         _foo
+# TWOLEVELWEAK-LABEL: Weak bind table:
+# TWOLEVELWEAK:       __DATA   __la_symbol_ptr      0x[[#ADDR]]       pointer 0 _foo
+
+# TWOLEVELWEAKSYM: (undefined) weak external _foo (from weak-foo)
+
+#--- foo.s
+.globl _foo
+_foo:
+  ret
+
+#--- weak-foo.s
+.globl _foo
+.weak_definition _foo
+_foo:
+  ret
+
+#--- main.s
+.globl _main
+_main:
+  callq _foo
+  ret