[lld-macho] -flat_namespace for dylibs should make all externs interposable

[int3]

Summary

All references to interposable symbols can be redirected at runtime to
point to a different symbol definition (with the same name). For
example, if both dylib A and B define symbol _foo, and we load A before
B at runtime, then all references to _foo within dylib B will point to
the definition in dylib A.

ld64 makes all extern symbols interposable when linking with
-flat_namespace.

TODO 1: Support -interposable and -interposable_list, which should
just be a matter of parsing those CLI flags and setting the
Defined::interposable bit.

TODO 2: Set Reloc::FinalDefinitionInLinkageUnit correctly with this info
(we are currently not setting it at all, so we're erring on the
conservative side, but we should help the LTO backend generate more
optimal code.)

[int3]

update test

[modimo]

lld/MachO/SymbolTable.cpp

99

Could this be a config property rather than a per-symbol? It looks like a link invocation will always have flat_namespace or never have it.

lld/MachO/SyntheticSections.cpp

422

Note that the non-lazy binding and lazy binding sections now have to accommodate both DylibSymbols and (interposable) Defined symbols.

Aside from s/DylibSymbol/Symbol/g is the only other change to support this here?

Also, would recommended factoring out the s/DylibSymbol/Symbol/g change to a separate diff as a parent to make it easier to see what files have logic changes in them

[int3]

lld/MachO/SymbolTable.cpp

99

ah this was done with an eye for future support of -interposable_list, which will allow specific symbols to be treated as interposable. I'll add a comment.

lld/MachO/SyntheticSections.cpp

422

Pretty much yeah. I'll split out the NFC changes 👍

[int3]

split out NFC changes

[modimo]

Internally in LLVM IR processing interposability is represented by the following check:

bool GlobalValue::isInterposable() const {
  if (isInterposableLinkage(getLinkage()))
    return true;
  return getParent() && getParent()->getSemanticInterposition() &&
         !isDSOLocal();
}

I'm wondering: is there's a case where a dso_local function/global that comes into link with -flat_namespace/-interposable set? In ELF land interposability is set at compile time but with these flags on MachO it looks possible to set them at link time. If so that also makes pre-LTO optimizations strange because it might inline a function that later turns interposable. Given the previous statement I suspect I'm missing something here.

lld/MachO/SyntheticSections.cpp

422

Thanks!

[int3]

move assert from other diff

[int3]

Hmm, maybe that's why clang doesn't seem to set dso_local when compiling for macos?

~/tmp: cat test.c
void f1(char a) {}
~/tmp: clang -target x86_64-unknown-linux-gnu -c -emit-llvm test.c -o - | llvm-dis
; ModuleID = '<stdin>'
source_filename = "test.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: noinline nounwind optnone uwtable
define dso_local void @f1(i8 signext %0) #0 {
  %2 = alloca i8, align 1
  store i8 %0, i8* %2, align 1
  ret void
}

attributes #0 = { noinline nounwind optnone uwtable "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"Apple clang version 13.0.0 (clang-1300.0.29.30)"}
~/tmp: clang -target x86_64-apple-darwin -c -emit-llvm test.c -o - | llvm-dis
; ModuleID = '<stdin>'
source_filename = "test.c"
target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx12.0.0"

; Function Attrs: noinline nounwind optnone ssp uwtable
define void @f1(i8 signext %0) #0 {
  %2 = alloca i8, align 1
  store i8 %0, i8* %2, align 1
  ret void
}

attributes #0 = { noinline nounwind optnone ssp uwtable "darwin-stkchk-strong-link" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "probe-stack"="___chkstk_darwin" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+cx8,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0, !1, !2}
!llvm.ident = !{!3}

!0 = !{i32 2, !"SDK Version", [2 x i32] [i32 12, i32 1]}
!1 = !{i32 1, !"wchar_size", i32 4}
!2 = !{i32 7, !"PIC Level", i32 2}
!3 = !{!"Apple clang version 13.0.0 (clang-1300.0.29.30)"}

[int3]

Not sure where in the clang codebase this dso_local (or lack thereof) is being determined, though...

[smeenai]

In D119294#3374129, @int3 wrote:

Not sure where in the clang codebase this dso_local (or lack thereof) is being determined, though...

@MaskRay has done the most with dso_local recently, I think.

[modimo]

Clang-12 maintains dso_local on f1 as well, clang-13 and trunk lose it: https://godbolt.org/z/oejTzWsoW

[MaskRay]

I'm wondering: is there's a case where a dso_local function/global that comes into link with -flat_namespace/-interposable set? In ELF land interposability is set at compile time but with these flags on MachO it looks possible to set them at link time. If so that also makes pre-LTO optimizations strange because it might inline a function that later turns interposable. Given the previous statement I suspect I'm missing something here.

https://maskray.me/blog/2021-05-09-fno-semantic-interposition#clang--fno-semantic-interposition has some information about ELF -fno-semantic-interposition.

For ELF, yes. -fno-pic and -fpie have no interposition on defined symbols.
For -fpic, Clang defaults to -fhalf-no-semantic-interposition where interprocedural optimizations are available at compile time even if at link time the symbol are preemptible.
This seems strange but is important to retain the longstanding behavior (not regressing optimizations people get with default clang -fpic -O2 a.cc).
I actually hope that we can transit from the current confusing 3 states to: "Can Clang default to -fno-semantic-interposition?" but there may be some risk (perhaps some people can complain about some cases as described in https://maskray.me/blog/2021-05-16-elf-interposition-and-bsymbolic#interaction-with-ld_preload)

Hmm, maybe that's why clang doesn't seem to set dso_local when compiling for macos?

D98458 (in release/13.x but not in release/12.x) is related. Seems that XNU has reliance on not having dso_local for some cases.

[MaskRay]

lld/test/MachO/flat-namespace-interposable.s

51

add .private_extern test

[int3]

exclude private_externs from being interposable

lld/test/MachO/flat-namespace-interposable.s

51

whoops, I'd indeed forgotten to handle this case in the code. Thanks!

lld/MachO/SymbolTable.cpp

if (!wasInserted) {
     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
       overridesWeakDef = !isWeakDef && dysym->isWeakDef();
       dysym->unreference();
     }
     // Defined symbols take priority over other types of symbols, so in case
     // of a name conflict, we fall through to the replaceSymbol() call below.
   }
 
+  // With -flat_namespace, all extern symbols in dylibs are interposable.
+  // FIXME: Add support for `-interposable` (PR53680).
+  bool interposable = config->namespaceKind == NamespaceKind::flat &&
+                      config->outputType != MachO::MH_EXECUTE &&
+                      !isPrivateExtern;
   Defined *defined = replaceSymbol<Defined>(
       s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,
       isPrivateExtern, isThumb, isReferencedDynamically, noDeadStrip,
-      overridesWeakDef, isWeakDefCanBeHidden);
+      overridesWeakDef, isWeakDefCanBeHidden, interposable);
   return defined;
 }
 
 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,
                                   bool isWeakRef) {
   Symbol *s;
   bool wasInserted;
   std::tie(s, wasInserted) = insert(name, file);

lld/MachO/Symbols.h

public:
   bool used : 1;
 };
 
 class Defined : public Symbol {
 public:
   Defined(StringRefZ name, InputFile *file, InputSection *isec, uint64_t value,
           uint64_t size, bool isWeakDef, bool isExternal, bool isPrivateExtern,
           bool isThumb, bool isReferencedDynamically, bool noDeadStrip,
-          bool canOverrideWeakDef = false, bool isWeakDefCanBeHidden = false);
+          bool canOverrideWeakDef = false, bool isWeakDefCanBeHidden = false,
+          bool interposable = false);
 
   bool isWeakDef() const override { return weakDef; }
   bool isExternalWeakDef() const {
     return isWeakDef() && isExternal() && !privateExtern;
   }
   bool isTlv() const override;
 
   bool isExternal() const { return external; }
public:
   // This is information for the static linker, and it's also written to the
   // output file's symbol table for tools running later (such as `strip`).
   bool referencedDynamically : 1;
   // Set on symbols that should not be removed by dead code stripping.
   // Set for example on `__attribute__((used))` globals, or on some Objective-C
   // metadata. This is information only for the static linker and not written
   // to the output.
   bool noDeadStrip : 1;
+  // Whether references to this symbol can be interposed at runtime to point to
+  // a different symbol definition (with the same name). For example, if both
+  // dylib A and B define an interposable symbol _foo, and we load A before B at
+  // runtime, then all references to _foo within dylib B will point to the
+  // definition in dylib A.
+  //
+  // Only extern symbols may be interposable.
+  bool interposable : 1;
 
   bool weakDefCanBeHidden : 1;
 
 private:
   const bool weakDef : 1;
   const bool external : 1;
 
 public:

lld/MachO/Symbols.cpp

 uint64_t Symbol::getStubVA() const { return in.stubs->getVA(stubsIndex); }
 uint64_t Symbol::getGotVA() const { return in.got->getVA(gotIndex); }
 uint64_t Symbol::getTlvVA() const { return in.tlvPointers->getVA(gotIndex); }
 
 Defined::Defined(StringRefZ name, InputFile *file, InputSection *isec,
                  uint64_t value, uint64_t size, bool isWeakDef, bool isExternal,
                  bool isPrivateExtern, bool isThumb,
                  bool isReferencedDynamically, bool noDeadStrip,
-                 bool canOverrideWeakDef, bool isWeakDefCanBeHidden)
+                 bool canOverrideWeakDef, bool isWeakDefCanBeHidden,
+                 bool interposable)
     : Symbol(DefinedKind, name, file), overridesWeakDef(canOverrideWeakDef),
       privateExtern(isPrivateExtern), includeInSymtab(true), thumb(isThumb),
       referencedDynamically(isReferencedDynamically), noDeadStrip(noDeadStrip),
-      weakDefCanBeHidden(isWeakDefCanBeHidden), weakDef(isWeakDef),
-      external(isExternal), isec(isec), value(value), size(size) {
+      interposable(interposable), weakDefCanBeHidden(isWeakDefCanBeHidden),
+      weakDef(isWeakDef), external(isExternal), isec(isec), value(value),
+      size(size) {
   if (isec) {
     isec->symbols.push_back(this);
     // Maintain sorted order.
     for (auto it = isec->symbols.rbegin(), rend = isec->symbols.rend();
          it != rend; ++it) {
       auto next = std::next(it);
       if (next == rend)
         break;

lld/MachO/SyntheticSections.cpp

void macho::addNonLazyBindingEntries(const Symbol *sym,
   if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
     in.binding->addEntry(dysym, isec, offset, addend);
     if (dysym->isWeakDef())
       in.weakBinding->addEntry(sym, isec, offset, addend);
   } else if (const auto *defined = dyn_cast<Defined>(sym)) {
     in.rebase->addEntry(isec, offset);
     if (defined->isExternalWeakDef())
       in.weakBinding->addEntry(sym, isec, offset, addend);
+    else if (defined->interposable)
+      in.binding->addEntry(sym, isec, offset, addend);
   } else {
     // Undefined symbols are filtered out in scanRelocations(); we should never
     // get here
     llvm_unreachable("cannot bind to an undefined symbol");
   }
 }
 
 void NonLazyPointerSectionBase::addEntry(Symbol *sym) {

 // Non-weak bindings need to have their dylib ordinal encoded as well.
 static int16_t ordinalForDylibSymbol(const DylibSymbol &dysym) {
   if (config->namespaceKind == NamespaceKind::flat || dysym.isDynamicLookup())
     return static_cast<int16_t>(BIND_SPECIAL_DYLIB_FLAT_LOOKUP);
   assert(dysym.getFile()->isReferenced());
   return dysym.getFile()->ordinal;
 }
 
 static int16_t ordinalForSymbol(const Symbol &sym) {
   if (const auto *dysym = dyn_cast<DylibSymbol>(&sym))
     return ordinalForDylibSymbol(*dysym);
+  assert(cast<Defined>(&sym)->interposable);
   return BIND_SPECIAL_DYLIB_FLAT_LOOKUP;
 }
 
 static void encodeDylibOrdinal(int16_t ordinal, raw_svector_ostream &os) {
   if (ordinal <= 0) {
     os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
                                (ordinal & BIND_IMMEDIATE_MASK));
   } else if (ordinal <= BIND_IMMEDIATE_MASK) {

lld/MachO/Writer.cpp

static void prepareBranchTarget(Symbol *sym) {
   } else if (auto *defined = dyn_cast<Defined>(sym)) {
     if (defined->isExternalWeakDef()) {
       if (in.stubs->addEntry(sym)) {
         in.rebase->addEntry(in.lazyPointers->isec,
                             sym->stubsIndex * target->wordSize);
         in.weakBinding->addEntry(sym, in.lazyPointers->isec,
                                  sym->stubsIndex * target->wordSize);
       }
+    } else if (defined->interposable) {
+      if (in.stubs->addEntry(sym))
+        in.lazyBinding->addEntry(sym);
     }
   } else {
     llvm_unreachable("invalid branch target symbol type");
   }
 }
 
 // Can a symbol's address can only be resolved at runtime?
 static bool needsBinding(const Symbol *sym) {
   if (isa<DylibSymbol>(sym))
     return true;
   if (const auto *defined = dyn_cast<Defined>(sym))
-    return defined->isExternalWeakDef();
+    return defined->isExternalWeakDef() || defined->interposable;
   return false;
 }
 
 static void prepareSymbolRelocation(Symbol *sym, const InputSection *isec,
                                     const lld::macho::Reloc &r) {
   assert(sym->isLive());
   const RelocAttrs &relocAttrs = target->getRelocAttrs(r.type);
 

lld/test/MachO/flat-namespace-interposable.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+
+## With -flat_namespace, non-weak extern symbols in dylibs become interposable.
+## Check that we generate the correct bindings for them. The test also includes
+## other symbol types like weak externs to verify we continue to do the same
+## (correct) thing even when `-flat_namespace` is enabled, instead of generating
+## spurious bindings.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/foo.o %t/foo.s
+# RUN: %lld -lSystem -flat_namespace -o %t/foo %t/foo.o
+# RUN: %lld -lSystem -dylib -flat_namespace -o %t/foo.dylib %t/foo.o
+# RUN: %lld -lSystem -bundle -flat_namespace -o %t/foo.bundle %t/foo.o
+# RUN: llvm-objdump --macho --bind --lazy-bind --weak-bind %t/foo | FileCheck \
+# RUN:   %s --check-prefix=EXEC --implicit-check-not=_private_extern
+# RUN: llvm-objdump --macho --bind --lazy-bind --weak-bind %t/foo.dylib | \
+# RUN:   FileCheck %s --check-prefix=DYLIB --implicit-check-not=_private_extern
+# RUN: llvm-objdump --macho --bind --lazy-bind --weak-bind %t/foo.bundle | \
+# RUN:   FileCheck %s --check-prefix=DYLIB --implicit-check-not=_private_extern
+
+## Executables with -flat_namespace don't have interposable externs.
+# EXEC:       Bind table:
+# EXEC-NEXT:  segment  section          address  type     addend dylib   symbol
+# EXEC-EMPTY:
+# EXEC-NEXT:  Lazy bind table:
+# EXEC-NEXT:  segment  section          address  dylib    symbol
+# EXEC-EMPTY:
+# EXEC-NEXT:  Weak bind table:
+# EXEC-NEXT:  segment  section          address  type     addend   symbol
+# EXEC-NEXT:  __DATA   __la_symbol_ptr  {{.*}}   pointer       0   _weak_extern
+# EXEC-NEXT:  __DATA   __data           {{.*}}   pointer       0   _weak_extern
+# EXEC-EMPTY:
+
+# DYLIB:       Bind table:
+# DYLIB-NEXT:  segment      section        address  type     addend dylib            symbol
+# DYLIB-DAG:   __DATA       __data         {{.*}}   pointer       0 flat-namespace   _extern
+# DYLIB-DAG:   __DATA       __thread_ptrs  {{.*}}   pointer       0 flat-namespace   _tlv
+# DYLIB-DAG:   __DATA_CONST __got          {{.*}}   pointer       0 flat-namespace   dyld_stub_binder
+# DYLIB-EMPTY:
+# DYLIB-NEXT:  Lazy bind table:
+# DYLIB-NEXT:  segment  section            address  dylib            symbol
+# DYLIB-NEXT:  __DATA   __la_symbol_ptr    {{.*}}   flat-namespace   _extern
+# DYLIB-EMPTY:
+# DYLIB-NEXT:  Weak bind table:
+# DYLIB-NEXT:  segment  section            address  type    addend   symbol
+# DYLIB-NEXT:  __DATA   __la_symbol_ptr    {{.*}}   pointer      0   _weak_extern
+# DYLIB-NEXT:  __DATA   __data             {{.*}}   pointer      0   _weak_extern
+
+#--- foo.s
+
+.globl _main, _extern, _weak_extern, _tlv
+.weak_definition _weak_extern
+.private_extern _private_extern
+
+_extern:
+  retq
+_weak_extern:
+  retq
+_private_extern:
+  retq
+_local:
+  retq
+
+_main:
+  callq _extern
+  callq _weak_extern
+  callq _private_extern
+  callq _local
+  mov _tlv@TLVP(%rip), %rax
+  retq
+
+.data
+.quad _extern
+.quad _weak_extern
+.quad _local
+
+.section __DATA,__thread_vars,thread_local_variables
+_tlv:
+
+.subsections_via_symbols