[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

382

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()?

537

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

382

Thanks for pushing back on this :)

I should have stopped being lazy and do it correctly.

537

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

562

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

bool link(ArrayRef<const char *> args, bool canExitEarly, raw_ostream &stdoutOS,
   stderrOS.enable_colors(stderrOS.has_colors());
 
   inputSections.clear();
   outputSections.clear();
   binaryFiles.clear();
   bitcodeFiles.clear();
   objectFiles.clear();
   sharedFiles.clear();
+  backwardReferences.clear();
 
   config = make<Configuration>();
   driver = make<LinkerDriver>();
   script = make<LinkerScript>();
   symtab = make<SymbolTable>();
 
   tar = nullptr;
   memset(&in, 0, sizeof(in));
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

 
 #ifndef LLD_ELF_SYMBOLS_H
 #define LLD_ELF_SYMBOLS_H
 
 #include "InputFiles.h"
 #include "InputSection.h"
 #include "lld/Common/LLVM.h"
 #include "lld/Common/Strings.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/ELF.h"
 
 namespace lld {
 // Returns a string representation for a symbol for diagnostics.
 std::string toString(const elf::Symbol &);
 
 // There are two different ways to convert an Archive::Symbol to a string:
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();
+
+// A mapping from a symbol to an InputFile referencing it backward. Used by
+// --warn-backrefs.
+extern llvm::DenseMap<const Symbol *, const InputFile *> backwardReferences;
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/Symbols.cpp

 Defined *ElfSym::globalOffsetTable;
 Defined *ElfSym::mipsGp;
 Defined *ElfSym::mipsGpDisp;
 Defined *ElfSym::mipsLocalGp;
 Defined *ElfSym::relaIpltStart;
 Defined *ElfSym::relaIpltEnd;
 Defined *ElfSym::riscvGlobalPointer;
 Defined *ElfSym::tlsModuleBase;
+DenseMap<const Symbol *, const InputFile *> backwardReferences;
 
 static uint64_t getSymVA(const Symbol &sym, int64_t &addend) {
   switch (sym.kind()) {
   case Symbol::DefinedKind: {
     auto &d = cast<Defined>(sym);
     SectionBase *isec = d.section;
 
     // This is an absolute symbol.
if (config->hasDynamicList)
     return sym.inDynamicList;
 
   // -Bsymbolic means that definitions are not preempted.
   if (config->bsymbolic || (config->bsymbolicFunctions && sym.isFunc()))
     return false;
   return true;
 }
 
+void reportBackrefs() {
+  for (auto &it : backwardReferences) {
+    const Symbol &sym = *it.first;
+    warn("backward reference detected: " + sym.getName() + " in " +
+         toString(it.second) + " refers to " + toString(sym.file));
+  }
+}
+
 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.
+    //
+    // 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())
-      warn("backward reference detected: " + other.getName() + " in " +
-           toString(other.file) + " refers to " + toString(file));
+      backwardReferences.try_emplace(this, other.file);
     return;
   }
 
   // Undefined symbols in a SharedFile do not change the binding.
   if (dyn_cast_or_null<SharedFile>(other.file))
     return;
 
   if (isUndefined() || isShared()) {
     // The binding will be weak if there is at least one reference and all are
     // weak. The binding has one opportunity to change to weak: if the first
     // reference is weak.
     if (other.binding != STB_WEAK || !referenced)
       binding = other.binding;
   }
 }
 
 // Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
 // foo@@VER. We want to effectively ignore foo, so give precedence to
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())
+      backwardReferences.erase(this);
     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