[ELF] --warn-backrefs: don't warn for linking sandwich problems

[MaskRay]

Summary

This is an alternative design to D77512.

D45195 added --warn-backrefs to detect

• A. certain input orders which GNU ld either errors ("undefined reference") or has different resolution semantics
• B. (byproduct) some latent multiple definition problems (-ldef1 -lref -ldef2) which I call "linking sandwich problems". def2 may or may not be the same as def1.

When an archive appears more than once (-ldef -lref -ldef), lld and GNU
ld may have the same resolution but --warn-backrefs may warn. This is
not uncommon. For example, currently lld itself has such a problem:

liblldCommon.a liblldCOFF.a ... liblldCommon.a
  _ZN3lld10DWARFCache13getDILineInfoEmm in liblldCOFF.a refers to liblldCommon.a(DWARF.cpp.o)
libLLVMSupport.a also appears twice and has a similar warning

glibc has such problems. It is somewhat destined because of its separate
libc/libpthread/... and arbitrary grouping. The situation is getting
improved over time but I have seen:

-lc __isnanl references -lm
-lc _IO_funlockfile references -lpthread

There are also various issues in interaction with other runtime
libraries such as libgcc_eh and libunwind:

-lc __gcc_personality_v0 references -lgcc_eh
-lpthread __gcc_personality_v0 references -lgcc_eh
-lpthread _Unwind_GetCFA references -lunwind

These problems are actually benign. We want --warn-backrefs to focus on
its main task A and defer task B (which is also useful) to a more
specific future feature (see gold --detect-odr-violations).

Instead of warning immediately, we store the message and only report it
if no subsequent lazy definition exists.

The use of the static variable backrefDiags is similar to undefs in
Relocations.cpp

[MaskRay]

I will try this in our internal large code base and ask Android/ChromeOS folks for help as well. If this goes well (little or no false positive), I hope we can eventually make --warn-backrefs the default.
Here for "false positive" I mean --warn-backrefs warns but our symbol resolution is actually the same as GNU ld's.

[grimar]

lld/ELF/Symbols.cpp

381

backrefDiags.clear();

Should it be called before populating the backrefDiags and not after? I guess it might be
possible when using LLD as a library to return !0 error code after backrefDiags was filled, but before reporting and cleaning.

We initialize a few things like this in

bool link(ArrayRef<const char *> args, bool canExitEarly, raw_ostream &stdoutOS,
          raw_ostream &stderrOS)

We have the known mess with the global variables. Should we at least stop adding them at random places and stick to initializing
new ones in the single place, like in the link()?

530

Looking on this, my first impression was that probably since you now have the reportBackrefs method,
you could move the creation and printing of the warning there probably somehow.
(i.e. leave backrefDiags.try_emplace here, but change the map value from std::string to something else probably).
This should having excessive string allocations.

[MaskRay]

Address comments

lld/ELF/Symbols.cpp

381

Thanks for pushing back on this :)

I should have stopped being lazy and do it correctly.

530

Thanks for the tip. I am not very concerned about the string allocation because every lazy input file there can be at most one such symbol. It looks like changing the signature of the DenseMap will beautify the code, as well as addressing the concern. So I will fix it.

[grimar]

LGTM, thanks!

lld/ELF/Symbols.h

561

Ussd -> Used

lld/test/ELF/warn-backrefs.s

55

Seems you make this comment to be 2 lines.

[grimar]

lld/test/ELF/warn-backrefs.s

55

*you can make

[MaskRay]

Address comments

lld/ELF/Driver.cpp

 //===- Driver.cpp ---------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (!config->relocatable)
     symtab->scanVersionScript();
 
   // Do link-time optimization if given files are LLVM bitcode files.
   // This compiles bitcode files into real object files.
   //
   // With this the symbol table should be complete. After this, no new names
   // except a few linker-synthesized ones will be added to the symbol table.
   compileBitcodeFiles<ELFT>();
+
+  // Symbol resolution finished. Report backward reference problems.
+  reportBackrefs();
   if (errorCount())
     return;
 
   // If -thinlto-index-only is given, we should create only "index
   // files" and not object files. Index file creation is already done
   // in addCombinedLTOObject, so we are done if that's the case.
   if (config->thinLTOIndexOnly)
     return;

lld/ELF/Symbols.h

 //===- Symbols.h ------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
void Symbol::replace(const Symbol &newSym) {
   // Print out a log message if --trace-symbol was specified.
   // This is for debugging.
   if (traced)
     printTraceSymbol(this);
 }
 
 void maybeWarnUnorderableSymbol(const Symbol *sym);
 bool computeIsPreemptible(const Symbol &sym);
+void reportBackrefs();
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/Symbols.cpp

 //===- Symbols.cpp --------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
if (config->hasDynamicList)
     return sym.inDynamicList;
 
   // -Bsymbolic means that definitions are not preempted.
   if (config->bsymbolic || (config->bsymbolicFunctions && sym.isFunc()))
     return false;
   return true;
 }
 
+static DenseMap<StringRef, std::string> backrefDiags;
+
+void reportBackrefs() {
+  for (auto &it : backrefDiags)
+    warn(it.second);
+  backrefDiags.clear();
+}
+
 static uint8_t getMinVisibility(uint8_t va, uint8_t vb) {
   if (va == STV_DEFAULT)
     return vb;
   if (vb == STV_DEFAULT)
     return va;
   return std::min(va, vb);
 }
 
if (isLazy()) {
     // files) form group 2. E forms group 3. I think that you can see how this
     // group assignment rule simulates the traditional linker's semantics.
     bool backref = config->warnBackrefs && other.file &&
                    file->groupId < other.file->groupId;
     fetch();
 
     // We don't report backward references to weak symbols as they can be
     // overridden later.
-    if (backref && !isWeak())
-      warn("backward reference detected: " + other.getName() + " in " +
-           toString(other.file) + " refers to " + toString(file));
+    //
+    // A traditional linker does not error for -ldef1 -lref -ldef2 (linking
+    // sandwich), where def2 may or may not be the same as def1. We don't want
+    // to warn for this case, so dismiss the warning if we see a subsequent lazy
+    // definition.
+    if (backref && !isWeak()) {
+      backrefDiags.try_emplace(
+          other.getName(),
+          ("backward reference detected: " + other.getName() + " in " +
+           toString(other.file) + " refers to " + toString(file))
+              .str());
+    }
     return;
   }
 
   // Undefined symbols in a SharedFile do not change the binding.
   if (dyn_cast_or_null<SharedFile>(other.file))
     return;
 
   if (isUndefined() || isShared()) {
if (cmp > 0)
     replace(other);
   else if (cmp == 0)
     reportDuplicate(this, other.file,
                     dyn_cast_or_null<InputSectionBase>(other.section),
                     other.value);
 }
 
 template <class LazyT> void Symbol::resolveLazy(const LazyT &other) {
-  if (!isUndefined())
+  if (!isUndefined()) {
+    // See the comment in resolveUndefined().
+    if (isDefined())
+      backrefDiags.erase(other.getName());
     return;
+  }
 
   // An undefined weak will not fetch archive members. See comment on Lazy in
   // Symbols.h for the details.
   if (isWeak()) {
     uint8_t ty = type;
     replace(other);
     type = ty;
     binding = STB_WEAK;

lld/test/ELF/warn-backrefs.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t1.o
 # RUN: echo '.globl foo; foo:' | llvm-mc -filetype=obj -triple=x86_64 - -o %t2.o
 # RUN: rm -f %t2.a
 # RUN: llvm-ar rcs %t2.a %t2.o
+# RUN: ld.lld -shared %t2.o -o %t2.so
 
 ## A forward reference is accepted by a traditional Unix linker.
 # RUN: ld.lld --fatal-warnings %t1.o %t2.a -o /dev/null
 # RUN: ld.lld --fatal-warnings --warn-backrefs %t1.o %t2.a -o /dev/null
 # RUN: ld.lld --fatal-warnings --warn-backrefs %t1.o --start-lib %t2.o --end-lib -o /dev/null
 
 # RUN: echo 'INPUT("%t1.o" "%t2.a")' > %t1.lds
 # RUN: ld.lld --fatal-warnings --warn-backrefs %t1.lds -o /dev/null
 
 ## A backward reference from %t1.o to %t2.a
 # RUN: ld.lld --fatal-warnings %t2.a %t1.o -o /dev/null
 # RUN: ld.lld --warn-backrefs %t2.a %t1.o -o /dev/null 2>&1 | FileCheck %s
 # RUN: ld.lld --warn-backrefs %t2.a '-(' %t1.o '-)' -o /dev/null 2>&1 | FileCheck %s
 
 ## Placing the definition and the backward reference in a group can suppress the warning.
 # RUN: echo 'GROUP("%t2.a" "%t1.o")' > %t2.lds
 # RUN: ld.lld --fatal-warnings --warn-backrefs %t2.lds -o /dev/null
 # RUN: ld.lld --fatal-warnings --warn-backrefs '-(' %t2.a %t1.o '-)' -o /dev/null
 
 ## A backward reference from %t1.o to %t2.a (added by %t3.lds).
 # RUN: echo 'GROUP("%t2.a")' > %t3.lds
 # RUN: ld.lld --warn-backrefs %t3.lds %t1.o -o /dev/null 2>&1 | FileCheck %s
 # RUN: ld.lld --fatal-warnings --warn-backrefs '-(' %t3.lds %t1.o '-)' -o /dev/null
+## If a lazy definition appears after the backward reference, don't warn.
+# RUN: ld.lld --fatal-warnings --warn-backrefs %t3.lds %t1.o %t3.lds -o /dev/null
 
 # CHECK: warning: backward reference detected: foo in {{.*}}1.o refers to {{.*}}2.a
 
 ## A backward reference from %t1.o to %t2.o
 # RUN: ld.lld --warn-backrefs --start-lib %t2.o --end-lib %t1.o -o /dev/null 2>&1 | \
 # RUN:   FileCheck --check-prefix=OBJECT %s
+## If a lazy definition appears after the backward reference, don't warn.
+# RUN: ld.lld --fatal-warnings --warn-backrefs --start-lib %t2.o --end-lib %t1.o --start-lib %t2.o --end-lib -o /dev/null
 
 # OBJECT: warning: backward reference detected: foo in {{.*}}1.o refers to {{.*}}2.o
 
 ## Don't warn if the definition and the backward reference are in a group.
 # RUN: echo '.globl bar; bar:' | llvm-mc -filetype=obj -triple=x86_64 - -o %t3.o
 # RUN: echo '.globl foo; foo: call bar' | llvm-mc -filetype=obj -triple=x86_64 - -o %t4.o
 # RUN: ld.lld --fatal-warnings --warn-backrefs %t1.o --start-lib %t3.o %t4.o --end-lib -o /dev/null
 
 ## We don't report backward references to weak symbols as they can be overridden later.
 # RUN: echo '.weak foo; foo:' | llvm-mc -filetype=obj -triple=x86_64 - -o %tweak.o
 # RUN: ld.lld --fatal-warnings --warn-backrefs --start-lib %tweak.o --end-lib %t1.o %t2.o -o /dev/null
 
+## If a lazy definition appears after the backward reference, don't warn.
+## A traditional Unix linker will resolve the reference to the later
+## definition.
+# RUN: ld.lld --fatal-warnings --warn-backrefs %t2.a %t1.o %t2.a -o /dev/null
+
+## lld fetches the archive while GNU ld resolves the reference to the shared definition.
+## Warn because the resolution rules are different.
+# RUN: ld.lld --warn-backrefs %t2.a %t1.o %t2.so -o /dev/null 2>&1 | FileCheck %s
+
+## This is a limitation. The resolution rules are different but
+## --warn-backrefs does not warn.
+# RUN: ld.lld --fatal-warnings --warn-backrefs %t2.a %t1.o %t2.so %t2.a -o /dev/null
+
 .globl _start, foo
 _start:
   call foo