[lld-macho] Do not error out on dead stripped duplicate symbols

[thevinster]

Summary

Builds that error out on duplicate symbols can still succeed if the symbols
will be dead stripped. Currently, this is the current behavior in ld64.
https://github.com/apple-oss-distributions/ld64/blob/main/src/ld/Resolver.cpp#L2018.
In order to provide an easier to path for adoption, introduce a new flag that will
retain compatibility with ld64's behavior (similar to --deduplicate-literals). This is
turned off by default since we do not encourage this behavior in the linker.

[thakis]

it's far better to align with ld64's behavior to be closer as a drop-in replacement

FWIW, I don't agree with this argument, and our doc listing intentional differences doesn't either. (Not deduping strings by default is a big difference and we're stricter in various other areas too.)

I don't have a problem with the patch itself (people who want the stricter behavior can not dead_strip, and most projects probably don't do dead stripping in debug builds), but you need to come up with a better justification: why is fixing this problem harder than others you have to fix when you want to use lld?

[thevinster]

FWIW, I don't agree with this argument, and our doc listing intentional differences doesn't either. (Not deduping strings by default is a big difference and we're stricter in various other areas too.)

I'm not sure if people were aware of this behavior, so it wouldn't be listed as an intentional difference if it's a new finding. Deduping strings is also a performance concern. If LLD had done that, it would slowed down build speed. OTOH, this change has negligible impact to LLD's performance.

why is fixing this problem harder than others you have to fix when you want to use lld?

While it's definitely worth addressing the bad source code issues, there are also third-party libraries that we don't own that requires dead stripping in order for the link to succeed. While I think it's a valiant effort to engage with all those maintainers to fix this bug, it also seems infeasible to fix all of them. That said, would you be more inclined to this change if it were gated behind a flag instead of being the default behavior?

[thakis]

worth addressing the bad source code issues, there are also third-party libraries that we don't own that requires dead stripping in order for the link to succeed. While I think it's a valiant effort to engage with all those maintainers to fix this bug, it also seems infeasible to fix all of them. That said, would you be more inclined to this change if it were gated behind a flag instead of being the default behavior?

Do you have data how much harder these are to fix than (say) the text deduping failures? Like, how many known-broken libraries are we talking?

[int3]

why is fixing this problem harder than others you have to fix when you want to use lld?

I would argue that reducing barriers to LLD adoption is good, regardless of whether the problem is harder or easier to fix. Even if it's just one extra error, that error might be the one that makes a potential adopter decide that adoption is just too much effort.

(Ngl I have already slightly regretted the choice of not deduplicating strings by default. I'm not convinced it saves us that much link time, and moreover I think it's more likely than not that the average adopter would just add that --deduplicate-literals flag rather than fixing their build.)

I think there's a good argument for having stricter behavior by default, though. My preference would be to support this but gate it under a flag (or possibly have a --ld64-compat flag that enables this behavior as well as --deduplicate-literals.)

[thevinster]

Do you have data how much harder these are to fix than (say) the text deduping failures?

I don't have data on how much harder these are to fix since I'm not familiar with most of the third-party libraries in-use. This would require reaching out to the integrators/owners to understand how to fix the offending symbols.

Like, how many known-broken libraries are we talking?

I've kicked off a full re-build of the world, and so far, I'm seeing about 51 failures and counting (at least 11k more in pending). A good chunk of them can be deduplicated to the same issues. Just based on inspection, I'm seeing at least 5 major third-parties that probably need to be fixed. That might seem low, but it's also not trivial to fix legacy related code that also depended on this particular behavior for many years.

With those numbers in mind, are you more open to accepting this change or at least behind some flag to make users easier to transition to LLD? (I can also report back with the final results if you're interested but it would take some time for all the test runs to finish. But tbh, I'm not sure if knowing that changes anything about the above statement I made).

[thakis]

I'm surprised it's that many, but that sounds pretty convincing.

If it's not too much trouble, maybe putting this behind a flag like Jez suggests might be good – code that can _only_ link with -dead_strip seems pretty broken and it might be nice to catch this by default.

[thevinster]

Add flag to gate dead stripped duplicate symbols

[thevinster]

Update comment

[thakis]

Thanks much!

lld/MachO/Config.h

138

call variable like the flag (deadStripDuplicates)

[int3]

lld/MachO/SymbolTable.cpp

49

How about "DuplicateSymbolDiag" to parallel "UndefinedDiag"? IMO a "reporter" sounds like something that has nontrivial logic in it, rather than a POD type

56

maybe make this a SmallVector? I think MaskRay has been converting a lot of std::vectors to SmallVector in order to save on binary size

102–103

could consider moving this into reportPendingDuplicateSymbols -- that way builds that have --dead-strip-duplicates won't pay the cost of building these strings

that said the cost is probably trivial, so up to you

lld/docs/MachO/ld64-vs-lld.rst

18

sorry this is my OCD

19

or "strips dead code"

20–21

super nits:

1. ld64's behavior is not a violation of ODR; rather the build is violating ODR and ld64 is not flagging it
2. we're not maintaining compatibility so much as providing a way for the user to obtain compatible behavior
3. double backticks because rST (I hate how it's subtly different from markdown but oh well)

[int3]

And thanks for doing this!

[thevinster]

Fixed up nits and naming

lld/MachO/SymbolTable.cpp

102–103

Did a very minor refactor on the struct to be able to move the string building to reportPendingDuplicateSymbols. In particular, I needed to save the src locations and files since accessing the values directly from defined would have been replaced with incorrect values by the time we got to the reporting stage.

[int3]

lld/MachO/SymbolTable.cpp

60

maybe rename this to dupSymDiags :)

102–103

gotcha makes sense

[thevinster]

Rename dupSymReporter to dupSymDiags

lld/MachO/Config.h

struct Configuration {
   bool emitFunctionStarts = false;
   bool emitBitcodeBundle = false;
   bool emitDataInCodeInfo = false;
   bool emitEncryptionInfo = false;
   bool emitInitOffsets = false;
   bool timeTraceEnabled = false;
   bool dataConst = false;
   bool dedupLiterals = true;
+  bool deadStripDuplicates = false;
   bool omitDebugInfo = false;
   bool warnDylibInstallName = false;
   bool ignoreOptimizationHints = false;
   bool forceExactCpuSubtypeMatch = false;
   uint32_t headerPad;
   uint32_t dylibCompatibilityVersion = 0;
   uint32_t dylibCurrentVersion = 0;
   uint32_t timeTraceGranularity = 500;

lld/MachO/Driver.cpp

bool macho::link(ArrayRef<const char *> argsArr, llvm::raw_ostream &stdoutOS,
   config->emitBitcodeBundle = args.hasArg(OPT_bitcode_bundle);
   config->emitDataInCodeInfo =
       args.hasFlag(OPT_data_in_code_info, OPT_no_data_in_code_info, true);
   config->emitInitOffsets = args.hasArg(OPT_init_offsets);
   config->icfLevel = getICFLevel(args);
   config->dedupLiterals =
       args.hasFlag(OPT_deduplicate_literals, OPT_icf_eq, false) ||
       config->icfLevel != ICFLevel::none;
+  config->deadStripDuplicates = args.hasArg(OPT_dead_strip_duplicates);
   config->warnDylibInstallName = args.hasFlag(
       OPT_warn_dylib_install_name, OPT_no_warn_dylib_install_name, false);
   config->ignoreOptimizationHints = args.hasArg(OPT_ignore_optimization_hints);
   config->callGraphProfileSort = args.hasFlag(
       OPT_call_graph_profile_sort, OPT_no_call_graph_profile_sort, true);
   config->printSymbolOrder = args.getLastArgValue(OPT_print_symbol_order_eq);
   config->forceExactCpuSubtypeMatch =
       getenv("LD_DYLIB_CPU_SUBTYPES_MUST_MATCH");

lld/MachO/Options.td

def : Flag<["--"], "time-trace">,
     HelpText<"Record time trace to file next to output">,
     Group<grp_lld>;
 def time_trace_granularity_eq: Joined<["--"], "time-trace-granularity=">,
     HelpText<"Minimum time granularity (in microseconds) traced by time profiler">,
     Group<grp_lld>;
 def deduplicate_literals: Flag<["--"], "deduplicate-literals">,
     HelpText<"Enable literal deduplication. This is implied by --icf={safe,all}">,
     Group<grp_lld>;
+def dead_strip_duplicates: Flag<["--"], "dead-strip-duplicates">,
+    HelpText<"Do not error on duplicate symbols that will be dead stripped.">,
+    Group<grp_lld>;
 def print_dylib_search: Flag<["--"], "print-dylib-search">,
     HelpText<"Print which paths lld searched when trying to find dylibs">,
     Group<grp_lld>;
 def icf_eq: Joined<["--"], "icf=">,
     HelpText<"Set level for identical code folding (default: none)">,
     MetaVarName<"[none,safe,all]">,
     Group<grp_lld>;
 def lto_O: Joined<["--"], "lto-O">,

lld/MachO/SymbolTable.h

 
 private:
   std::pair<Symbol *, bool> insert(StringRef name, const InputFile *);
   llvm::DenseMap<llvm::CachedHashStringRef, int> symMap;
   std::vector<Symbol *> symVector;
 };
 
 void reportPendingUndefinedSymbols();
+void reportPendingDuplicateSymbols();
 
 // Call reportPendingUndefinedSymbols() to emit diagnostics.
 void treatUndefinedSymbol(const Undefined &, StringRef source);
 void treatUndefinedSymbol(const Undefined &, const InputSection *,
                           uint64_t offset);
 
 extern std::unique_ptr<SymbolTable> symtab;
 
 } // namespace lld::macho
 
 #endif

lld/MachO/SymbolTable.cpp

if (!p.second) {
     sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
     symVector.push_back(sym);
   }
 
   sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);
   return {sym, p.second};
 }
 
+namespace {
+struct DuplicateSymbolDiag {
+  // Pair containing source location and source file
+  const std::pair<std::string, std::string> src1;
+  const std::pair<std::string, std::string> src2;
+  const Symbol *sym;
+
+  DuplicateSymbolDiag(const std::pair<std::string, std::string> src1,
+                      const std::pair<std::string, std::string> src2,
+                      const Symbol *sym)
+      : src1(src1), src2(src2), sym(sym) {}
+};
+SmallVector<DuplicateSymbolDiag> dupSymReporter;
+} // namespace
+
 Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
                                  InputSection *isec, uint64_t value,
                                  uint64_t size, bool isWeakDef,
                                  bool isPrivateExtern, bool isThumb,
                                  bool isReferencedDynamically, bool noDeadStrip,
                                  bool isWeakDefCanBeHidden) {
   bool overridesWeakDef = false;
   auto [s, wasInserted] = insert(name, file);
if (auto *defined = dyn_cast<Defined>(s)) {
       if (defined->isWeakDef()) {
         // FIXME: Handle this for bitcode files.
         if (auto concatIsec =
                 dyn_cast_or_null<ConcatInputSection>(defined->isec)) {
           concatIsec->wasCoalesced = true;
           concatIsec->symbols.erase(llvm::find(concatIsec->symbols, defined));
         }
       } else {
-        std::string src1 = defined->getSourceLocation();
-        std::string src2 = isec ? isec->getSourceLocation(value) : "";
+        std::string srcLoc1 = defined->getSourceLocation();
+        std::string srcLoc2 = isec ? isec->getSourceLocation(value) : "";
+        std::string srcFile1 = toString(defined->getFile());
+        std::string srcFile2 = toString(file);
 
-        std::string message =
-            "duplicate symbol: " + toString(*defined) + "\n>>> defined in ";
-        if (!src1.empty())
-          message += src1 + "\n>>>            ";
-        message += toString(defined->getFile()) + "\n>>> defined in ";
-        if (!src2.empty())
-          message += src2 + "\n>>>            ";
-        error(message + toString(file));
+        dupSymReporter.push_back({make_pair(srcLoc1, srcFile1),
+                                  make_pair(srcLoc2, srcFile2), defined});
       }
 
     } 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.
struct UndefinedDiag {
 
   std::vector<SectionAndOffset> codeReferences;
   std::vector<std::string> otherReferences;
 };
 
 MapVector<const Undefined *, UndefinedDiag> undefs;
 }
 
+void macho::reportPendingDuplicateSymbols() {
+  for (const auto &duplicate : dupSymReporter) {
+    if (!config->deadStripDuplicates || duplicate.sym->isLive()) {
+      std::string message =
+          "duplicate symbol: " + toString(*duplicate.sym) + "\n>>> defined in ";
+      if (!duplicate.src1.first.empty())
+        message += duplicate.src1.first + "\n>>>            ";
+      message += duplicate.src1.second + "\n>>> defined in ";
+      if (!duplicate.src2.first.empty())
+        message += duplicate.src2.first + "\n>>>            ";
+      error(message + duplicate.src2.second);
+    }
+  }
+}
+
 void macho::reportPendingUndefinedSymbols() {
   for (const auto &undef : undefs) {
     const UndefinedDiag &locations = undef.second;
 
     std::string message = "undefined symbol";
     if (config->archMultiple)
       message += (" for arch " + getArchitectureName(config->arch())).str();
     message += ": " + toString(*undef.first);

lld/MachO/Writer.cpp

template <class LP> void Writer::run() {
   // InputSections, we should have `isec->canonical() == isec`.
   scanSymbols();
   if (in.objcStubs->isNeeded())
     in.objcStubs->setUp();
   scanRelocations();
   if (in.initOffsets->isNeeded())
     in.initOffsets->setUp();
 
-  // Do not proceed if there was an undefined symbol.
+  // Do not proceed if there were undefined or duplicate symbols.
   reportPendingUndefinedSymbols();
+  reportPendingDuplicateSymbols();
   if (errorCount())
     return;
 
   if (in.stubHelper->isNeeded())
     in.stubHelper->setUp();
 
   if (in.objCImageInfo->isNeeded())
     in.objCImageInfo->finalizeContents();

lld/docs/MachO/ld64-vs-lld.rst

 =================
 ld64 vs LLD-MachO
 =================
 
 This doc lists all significant deliberate differences in behavior between ld64
 and LLD-MachO.
 
 String Literal Deduplication
 ****************************
 ld64 always deduplicates string literals. LLD only does it when the ``--icf=``
 or the ``--deduplicate-literals`` flag is passed. Omitting deduplication by
 default ensures that our link is as fast as possible. However, it may also break
 some programs which have (incorrectly) relied on string deduplication always
 occurring. In particular, programs which compare string literals via pointer
 equality must be fixed to use value equality instead.
 
+Dead Stripping Duplicate Symbols
+********************************
+ld64 strips dead code before reporting duplicate symbols. By default, LLD does
+the opposite. ld64's behavior hides ODR violations, so we have chosen not
+to follow it. But, to make adoption easy, LLD can mimic this behavior via
+the ``--dead-strip-duplicates`` flag. Usage of this flag is discouraged, and
+this behavior should be fixed in the source. However, for sources that are not
+within the user's control, this will mitigate users for adoption.
+
 ``-no_deduplicate`` Flag
 ************************
 - ld64: This turns off ICF (deduplication pass) in the linker.
 - LLD: This turns off ICF and string merging in the linker.
 
 String Alignment
 ****************
 LLD is `slightly less conservative about aligning cstrings

lld/test/MachO/abs-duplicate.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/weakfoo.s -o %t/weakfoo.o
+# RUN: not %lld -lSystem %t/test.o %t/weakfoo.o -o /dev/null 2>&1 | FileCheck %s
+
+# CHECK:      error: duplicate symbol: _weakfoo
+# CHECK-NEXT: >>> defined in {{.*}}/test.o
+# CHECK-NEXT: >>> defined in {{.*}}/weakfoo.o
+
+## Duplicate absolute symbols that will be dead stripped later should not fail.
+# RUN: %lld -lSystem -dead_strip --dead-strip-duplicates -map %t/stripped-duplicate-map \
+# RUN:     %t/test.o %t/weakfoo.o -o %t/test
+# RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=DUP
+# DUP-LABEL: SYMBOL TABLE:
+# DUP-NEXT:   g F __TEXT,__text _main
+# DUP-NEXT:   g F __TEXT,__text __mh_execute_header
+# DUP-NEXT:   *UND* dyld_stub_binder
+
+## Dead stripped non-section symbols don't show up in map files because there's no input section.
+## Check that _weakfoo doesn't show up. This matches ld64.
+# RUN: FileCheck --check-prefix=DUPMAP %s < %t/stripped-duplicate-map
+# DUPMAP: _main
+# DUPMAP-LABEL: Dead Stripped Symbols
+# DUPMAP-NOT: _weakfoo
+
+#--- weakfoo.s
+.globl _weakfoo
+## The weak attribute is ignored for absolute symbols, so we will have a
+## duplicate symbol error for _weakfoo.
+.weak_definition _weakfoo
+_weakfoo = 0x1234
+
+#--- test.s
+.globl _main, _weakfoo
+.weak_definition _weakfoo
+_weakfoo = 0x5678
+
+.text
+_main:
+  ret

lld/test/MachO/dead-strip.s

 # EXECSTABS:     N_FUN {{.*}} '_main'
 # EXECSTABS-NOT: N_FUN {{.*}} '_unref'
 
 # RUN: llvm-mc -g -filetype=obj -triple=x86_64-apple-macos \
 # RUN:     %t/literals.s -o %t/literals.o
 # RUN: %lld -dylib -dead_strip --deduplicate-literals %t/literals.o -o %t/literals
 # RUN: llvm-objdump --macho --section="__TEXT,__cstring" --section="__DATA,str_ptrs" \
 # RUN:   --section="__TEXT,__literals" %t/literals | FileCheck %s --check-prefix=LIT
-
 # LIT:      Contents of (__TEXT,__cstring) section
 # LIT-NEXT: foobar
 # LIT-NEXT: Contents of (__DATA,str_ptrs) section
 # LIT-NEXT: __TEXT:__cstring:bar
 # LIT-NEXT: __TEXT:__cstring:bar
 # LIT-NEXT: Contents of (__TEXT,__literals) section
 # LIT-NEXT: ef be ad de {{$}}
 
+## Duplicate symbols that will be dead stripped later should not fail when using
+## the --dead-stripped-duplicates flag
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/duplicate1.s -o %t/duplicate1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/duplicate2.s -o %t/duplicate2.o
+# RUN: %lld -lSystem -dead_strip --dead-strip-duplicates -map %t/stripped-duplicate-map \
+# RUN:     %t/duplicate1.o %t/duplicate2.o -o %t/duplicate
+# RUN: llvm-objdump --syms %t/duplicate | FileCheck %s --check-prefix=DUP
+# DUP-LABEL: SYMBOL TABLE:
+# DUP-NEXT:   g F __TEXT,__text _main
+# DUP-NEXT:   g F __TEXT,__text __mh_execute_header
+# DUP-NEXT:   *UND* dyld_stub_binder
+
+## Check that the duplicate dead stripped symbols get listed properly.
+# RUN: FileCheck --check-prefix=DUPMAP %s < %t/stripped-duplicate-map
+# DUPMAP: _main
+# DUPMAP-LABEL: Dead Stripped Symbols
+# DUPMAP: <<dead>> [ 2] _foo
+
+#--- duplicate1.s
+.text
+.globl _main, _foo
+_foo:
+  retq
+
+_main:
+  retq
+
+.subsections_via_symbols
+
+#--- duplicate2.s
+.text
+.globl _foo
+_foo:
+  retq
+
+.subsections_via_symbols
+
 #--- basics.s
 .comm _ref_com, 1
 .comm _unref_com, 1
 
 .section __DATA,__unref_section
 _unref_data:
   .quad 4
 

lld/test/MachO/invalid/abs-duplicate.s

-# REQUIRES: x86
-# RUN: rm -rf %t; split-file %s %t
-# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
-# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/weakfoo.s -o %t/weakfoo.o
-# RUN: not %lld -lSystem %t/test.o %t/weakfoo.o -o %t/test 2>&1 | FileCheck %s
-
-# CHECK:      error: duplicate symbol: _weakfoo
-# CHECK-NEXT: >>> defined in {{.*}}/test.o
-# CHECK-NEXT: >>> defined in {{.*}}/weakfoo.o
-
-#--- weakfoo.s
-.globl _weakfoo
-## The weak attribute is ignored for absolute symbols, so we will have a
-## duplicate symbol error for _weakfoo.
-.weak_definition _weakfoo
-_weakfoo = 0x1234
-
-#--- test.s
-.globl _main, _weakfoo
-.weak_definition _weakfoo
-_weakfoo = 0x5678
-
-.text
-_main:
-  ret