[ELF] Support --{,no-}allow-shlib-undefined

[MaskRay]

Summary

In ld.bfd/gold, --no-allow-shlib-undefined is the default when linking
an executable. This patch implements a check to error on undefined
symbols in a shared object, if all of its DT_NEEDED entries are seen.

Our approach resembles the one used in gold, achieves a good balance to
be useful but not too smart (ld.bfd traces all DSOs and emulates the
behavior of a dynamic linker to catch more cases).

The error is issued based on the symbol table, different from undefined
reference errors issued for relocations. It is most effective when there
are DSOs that were not linked with -z defs (e.g. when static sanitizers
runtime is used).

gold has a comment that some system libraries on GNU/Linux may have
spurious undefined references and thus system libraries should be
excluded (https://sourceware.org/bugzilla/show_bug.cgi?id=6811). The
story may have changed now but we make --allow-shlib-undefined the
default for now. Its interaction with -shared can be discussed in the
future.

[ruiu]

ld.bfd traces all DSOs using the same logic as the runtime to try to resolve all undefined symbols in all DSOs. The linker even reads from /etc/ld.so.conf to see how DSOs would be resolved at runtime. That's I believe the original concept of --no-allow-shlib-undefines, as you can find any DSO symbols that can fail to be resolved at runtime. But that's apparently too much for us.

ld.gold instead does what you implemented in this patch. For a DSO X, if we know all DSOs that X depends on, then we emit a warning if there is an undefined symbol in X that cannot be resolved using any DSO. That perhaps achieves the right balance between being useful and being not too smart.

So I think this patch essentially looks good. The only concern is that the patch doesn't contain any comment about the design decision as described above.

ELF/InputFiles.h

335

We already have IsNeeded bit, so Needed would be confusing. DtNeeded is better.

ELF/Writer.cpp

1709

This code is added without what this is supposed to do, so it would be hard to understand in the future.

Is this the best place to add this error check? Can you run another for loop to separate this new logic from another?

1714

The way you check whether we've seen all needed libraries seems a bit too complicated. I think that can be implemented much simpler code. At least you shouldn't mix two independent checks, undefined symbol check and needed lib check in a single loop. The latter can be done in a separate loop.

[MaskRay]

Add design decision (we take an approach resembling gold)

Delete an unnecessary check in the test in allow_shlib_undefined.s and a check line for the error message

[MaskRay]

Split the loop to two: 1) check if all DT_NEEDED are seen 2) --no-allow-shlib-undefined check

[MaskRay]

ELF/Writer.cpp

1709

After splitting the "whether all DT_NEEDED entries are seen for a SharedFile" logic, the actual error checking code in the loop body is simple enough. I think it does not hurt to be placed beside addSymbol, but I'd like to put it into another loop if you prefer.

[MaskRay]

Put !AllowShlibUndefined code together.

This does what the comment says:

Is this the best place to add this error check? Can you run another for loop to separate this new logic from another?

[MaskRay]

Change the order of AND clauses to be more efficient

[grimar]

It looks good to me. Few comments about the code/style are below.

ELF/Writer.cpp

1692

nit: gold->ld.gold for consistency?

1705

It would not change anything, but probably be slightly more consistent to use toString(File) here:
error(toString(Sym->File) + ": undefined reference to " + toString(*Sym));

Actually, I would rewrite this block with the use of early returns, it feels a bit better readable to me, but that is up to you:

for (Symbol *Sym : Symtab->getSymbols()) {
  if (!Sym->isUndefined() || Sym->isWeak())
    continue;
  if (!Sym->File || !isa<SharedFile<ELFT>>(Sym->File))
    continue;
  if (AllNeededIsKnown.count(Sym->File))
    error(toString(Sym->File) + ": undefined reference to " + toString(*Sym));
}

[joerg]

Neither GNU ld nor gold implement really useful behavior here. Ideally, every library would be linked with -z defs, but that normally doesn't work because on many systems certain symbols are imported from the main program by default. A good example are the entry points of the dynamic linker. A bad example historically speaking is libwrap. From a user perspective it would be desirable to have a way to say "This symbol will be supplied by someone else" when linking a shared library or potentially even the main binary. That would allow whitelisting intentionally undefined symbols and allow avoiding any symbol resolution dance for shared libraries. A single pass over the symbol tables is still necessary for the sake of knowing the defined symbols and for potential copy relocations, but no further work should be needed.

[ruiu]

ELF/Writer.cpp

1704

Isn't looking up a hash table for each symbol too slow? Maybe you should add a bit to SharedFile?

[MaskRay]

Make AllNeededIsKnown a bool in SharedFile

[MaskRay]

ELF/Writer.cpp

1705

Changed File->getName() to toString(F).

As of the early-return pattern, the if condition used here is simple.. So I'd prefer keeping the current form.

[ruiu]

ELF/Writer.cpp

1705

I think the current style is fine. Probably the following style is more common in lld though:

for (...)
  if (...)
    if (auto *F = dyn_cast_or_null<SharedFile<ELFT>>(Sym->File))
      if (F->AllNeededIsKnown)
        error(...)

[MaskRay]

Address the comment "I think the current style is fine. Probably the following style is more common in lld though:"

[MaskRay]

// (A) D57385 will not enable the check ("allow shlib undefined")
Config->AllowShlibUndefined = Args.hasFlag(OPT_allow_shlib_undefined, OPT_no_allow_shlib_undefined, true);

// (B) In a future change, check errors when linking executables
Config->AllowShlibUndefined = Args.hasFlag(OPT_allow_shlib_undefined, OPT_no_allow_shlib_undefined, Args.hasFlag(OPT_shared));

I've tested (B) on our (numerous) internal targets and only 0.025% targets fail to build after the (B) change. Most if not all broken targets share the same root cause which is not lld's fault. So I believe (B) is also safe but I'll postpone it to a future change.

[ruiu]

LGTM

ELF/InputFiles.h

362

Thank you for adding the comment.

ELF/Config.h

struct Configuration {
   std::vector<SymbolVersion> DynamicList;
   std::vector<SymbolVersion> VersionScriptGlobals;
   std::vector<SymbolVersion> VersionScriptLocals;
   std::vector<uint8_t> BuildIdVector;
   llvm::MapVector<std::pair<const InputSectionBase *, const InputSectionBase *>,
                   uint64_t>
       CallGraphProfile;
   bool AllowMultipleDefinition;
+  bool AllowShlibUndefined;
   bool AndroidPackDynRelocs;
   bool ARMHasBlx = false;
   bool ARMHasMovtMovw = false;
   bool ARMJ1J2BranchEncoding = false;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
   bool CallGraphProfileSort;

ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   errorHandler().FatalWarnings =
       Args.hasFlag(OPT_fatal_warnings, OPT_no_fatal_warnings, false);
   ThreadsEnabled = Args.hasFlag(OPT_threads, OPT_no_threads, true);
 
   Config->AllowMultipleDefinition =
       Args.hasFlag(OPT_allow_multiple_definition,
                    OPT_no_allow_multiple_definition, false) ||
       hasZOption(Args, "muldefs");
+  Config->AllowShlibUndefined = Args.hasFlag(
+      OPT_allow_shlib_undefined, OPT_no_allow_shlib_undefined, true);
   Config->AuxiliaryList = args::getStrings(Args, OPT_auxiliary);
   Config->Bsymbolic = Args.hasArg(OPT_Bsymbolic);
   Config->BsymbolicFunctions = Args.hasArg(OPT_Bsymbolic_functions);
   Config->CheckSections =
       Args.hasFlag(OPT_check_sections, OPT_no_check_sections, true);
   Config->Chroot = Args.getLastArgValue(OPT_chroot);
   Config->CompressDebugSections = getCompressDebugSections(Args);
   Config->Cref = Args.hasFlag(OPT_cref, OPT_no_cref, false);

ELF/InputFiles.h

template <class ELFT> class SharedFile : public ELFFileBase<ELFT> {
   typedef typename ELFT::Verdef Elf_Verdef;
   typedef typename ELFT::Versym Elf_Versym;
 
   const Elf_Shdr *VersymSec = nullptr;
   const Elf_Shdr *VerdefSec = nullptr;
 
 public:
   std::vector<const Elf_Verdef *> Verdefs;
+  std::vector<StringRef> DtNeeded;
   std::string SoName;
 
   static bool classof(const InputFile *F) {
     return F->kind() == Base::SharedKind;
   }
 
   SharedFile(MemoryBufferRef M, StringRef DefaultSoName);
 
-  void parseSoName();
+  void parseDynamic();
   void parseRest();
   uint32_t getAlignment(ArrayRef<Elf_Shdr> Sections, const Elf_Sym &Sym);
   std::vector<const Elf_Verdef *> parseVerdefs();
   std::vector<uint32_t> parseVersyms();
 
   struct NeededVer {
     // The string table offset of the version name in the output file.
     size_t StrTab;
 
     // The version identifier for this version name.
     uint16_t Index;
   };
 
   // Mapping from Elf_Verdef data structures to information about Elf_Vernaux
   // data structures in the output file.
   std::map<const Elf_Verdef *, NeededVer> VerdefMap;
 
+  // Used for --no-allow-shlib-undefined.
+  bool AllNeededIsKnown;
+
   // Used for --as-needed
   bool IsNeeded;
 };
 
 class BinaryFile : public InputFile {
 public:
   explicit BinaryFile(MemoryBufferRef M) : InputFile(BinaryKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == BinaryKind; }

ELF/InputFiles.cpp

 
 template <class ELFT>
 SharedFile<ELFT>::SharedFile(MemoryBufferRef M, StringRef DefaultSoName)
     : ELFFileBase<ELFT>(Base::SharedKind, M), SoName(DefaultSoName),
       IsNeeded(!Config->AsNeeded) {}
 
 // Partially parse the shared object file so that we can call
 // getSoName on this object.
-template <class ELFT> void SharedFile<ELFT>::parseSoName() {
+template <class ELFT> void SharedFile<ELFT>::parseDynamic() {
   const Elf_Shdr *DynamicSec = nullptr;
   const ELFFile<ELFT> Obj = this->getObj();
   ArrayRef<Elf_Shdr> Sections = CHECK(Obj.sections(), this);
 
   // Search for .dynsym, .dynamic, .symtab, .gnu.version and .gnu.version_d.
   for (const Elf_Shdr &Sec : Sections) {
     switch (Sec.sh_type) {
     default:
if (this->VersymSec && this->ELFSyms.empty())
     error("SHT_GNU_versym should be associated with symbol table");
 
   // Search for a DT_SONAME tag to initialize this->SoName.
   if (!DynamicSec)
     return;
   ArrayRef<Elf_Dyn> Arr =
       CHECK(Obj.template getSectionContentsAsArray<Elf_Dyn>(DynamicSec), this);
   for (const Elf_Dyn &Dyn : Arr) {
-    if (Dyn.d_tag == DT_SONAME) {
+    if (Dyn.d_tag == DT_NEEDED) {
+      uint64_t Val = Dyn.getVal();
+      if (Val >= this->StringTable.size())
+        fatal(toString(this) + ": invalid DT_NEEDED entry");
+      DtNeeded.push_back(this->StringTable.data() + Val);
+    } else if (Dyn.d_tag == DT_SONAME) {
       uint64_t Val = Dyn.getVal();
       if (Val >= this->StringTable.size())
         fatal(toString(this) + ": invalid DT_SONAME entry");
       SoName = this->StringTable.data() + Val;
-      return;
     }
   }
 }
 
 // Parses ".gnu.version" section which is a parallel array for the symbol table.
 // If a given file doesn't have ".gnu.version" section, returns VER_NDX_GLOBAL.
 template <class ELFT> std::vector<uint32_t> SharedFile<ELFT>::parseVersyms() {
   size_t Size = this->ELFSyms.size() - this->FirstGlobal;
uint32_t SharedFile<ELFT>::getAlignment(ArrayRef<Elf_Shdr> Sections,
   uint64_t Ret = UINT64_MAX;
   if (Sym.st_value)
     Ret = 1ULL << countTrailingZeros((uint64_t)Sym.st_value);
   if (0 < Sym.st_shndx && Sym.st_shndx < Sections.size())
     Ret = std::min<uint64_t>(Ret, Sections[Sym.st_shndx].sh_addralign);
   return (Ret > UINT32_MAX) ? 0 : Ret;
 }
 
-// Fully parse the shared object file. This must be called after parseSoName().
+// Fully parse the shared object file. This must be called after parseDynamic().
 //
 // This function parses symbol versions. If a DSO has version information,
 // the file has a ".gnu.version_d" section which contains symbol version
 // definitions. Each symbol is associated to one version through a table in
 // ".gnu.version" section. That table is a parallel array for the symbol
 // table, and each table entry contains an index in ".gnu.version_d".
 //
 // The special index 0 is reserved for VERF_NDX_LOCAL and 1 is for

ELF/Options.td

 defm Tdata: Eq<"Tdata", "Same as --section-start with .data as the sectionname">;
 
 defm Ttext: Eq<"Ttext", "Same as --section-start with .text as the sectionname">;
 
 defm allow_multiple_definition: B<"allow-multiple-definition",
     "Allow multiple definitions",
     "Do not allow multiple definitions (default)">;
 
+defm allow_shlib_undefined: B<"allow-shlib-undefined",
+    "Allow unresolved references in shared libraries (default)",
+    "Do not allow unresolved references in shared libraries">;
+
 defm apply_dynamic_relocs: B<"apply-dynamic-relocs",
     "Apply link-time values for dynamic relocations",
     "Do not apply link-time values for dynamic relocations (default)">;
 
 defm as_needed: B<"as-needed",
     "Only set DT_NEEDED for shared libraries if used",
     "Always set DT_NEEDED for shared libraries (default)">;
 

 defm plugin: Eq<"plugin", "Ignored for compatibility with GNU linkers">;
 
 def plugin_opt_fresolution_eq: J<"plugin-opt=-fresolution=">;
 def plugin_opt_pass_through_eq: J<"plugin-opt=-pass-through=">;
 def plugin_opt_thinlto: J<"plugin-opt=thinlto">;
 def plugin_opt_slash: J<"plugin-opt=/">;
 
 // Options listed below are silently ignored for now for compatibility.
-def: F<"allow-shlib-undefined">;
 def: F<"detect-odr-violations">;
 def: Flag<["-"], "g">;
 def: F<"long-plt">;
 def: F<"no-add-needed">;
-def: F<"no-allow-shlib-undefined">;
 def: F<"no-copy-dt-needed-entries">;
 def: F<"no-ctors-in-init-array">;
 def: F<"no-keep-memory">;
 def: F<"no-mmap-output-file">;
 def: F<"no-warn-mismatch">;
 def: Separate<["--", "-"], "rpath-link">;
 def: J<"rpath-link=">;
 def: F<"sort-common">;

ELF/SymbolTable.h

public:
   void scanVersionScript();
 
   Symbol *find(StringRef Name);
 
   void trace(StringRef Name);
 
   void handleDynamicList();
 
+  // Set of .so files to not link the same shared object file more than once.
+  llvm::DenseMap<StringRef, InputFile *> SoNames;
+
 private:
   std::pair<Symbol *, bool> insertName(StringRef Name);
 
   std::vector<Symbol *> findByVersion(SymbolVersion Ver);
   std::vector<Symbol *> findAllByVersion(SymbolVersion Ver);
 
   llvm::StringMap<std::vector<Symbol *>> &getDemangledSyms();
   void handleAnonymousVersion();
private:
   llvm::DenseMap<llvm::CachedHashStringRef, int> SymMap;
   std::vector<Symbol *> SymVector;
 
   // Comdat groups define "link once" sections. If two comdat groups have the
   // same name, only one of them is linked, and the other is ignored. This set
   // is used to uniquify them.
   llvm::DenseSet<llvm::CachedHashStringRef> ComdatGroups;
 
-  // Set of .so files to not link the same shared object file more than once.
-  llvm::DenseMap<StringRef, InputFile *> SoNames;
-
   // A map from demangled symbol names to their symbol objects.
   // This mapping is 1:N because two symbols with different versions
   // can have the same name. We use this map to handle "extern C++ {}"
   // directive in version scripts.
   llvm::Optional<llvm::StringMap<std::vector<Symbol *>>> DemangledSyms;
 
   // For LTO.
   std::unique_ptr<BitcodeCompiler> LTO;
 };
 
 extern SymbolTable *Symtab;
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/SymbolTable.cpp

template <class ELFT> void SymbolTable::addFile(InputFile *File) {
   }
 
   if (Config->Trace)
     message(toString(File));
 
   // .so file
   if (auto *F = dyn_cast<SharedFile<ELFT>>(File)) {
     // DSOs are uniquified not by filename but by soname.
-    F->parseSoName();
+    F->parseDynamic();
     if (errorCount())
       return;
 
     // If a DSO appears more than once on the command line with and without
     // --as-needed, --no-as-needed takes precedence over --as-needed because a
     // user can add an extra DSO with --no-as-needed to force it to be added to
     // the dependency list.
     DenseMap<StringRef, InputFile *>::iterator It;

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::finalizeSections() {
   if (!Config->Relocatable)
     forEachRelSec(scanRelocations<ELFT>);
 
   if (In.Plt && !In.Plt->empty())
     In.Plt->addSymbols();
   if (In.Iplt && !In.Iplt->empty())
     In.Iplt->addSymbols();
 
+  if (!Config->AllowShlibUndefined) {
+    // Error on undefined symbols in a shared object, if all of its DT_NEEDED
+    // entires are seen. These cases would otherwise lead to runtime errors
+    // reported by the dynamic linker.
+    //
+    // ld.bfd traces all DT_NEEDED to emulate the logic of the dynamic linker to
+    // catch more cases. That is too much for us. Our approach resembles the one
+    // used in ld.gold, achieves a good balance to be useful but not too smart.
+    for (InputFile *File : SharedFiles) {
+      SharedFile<ELFT> *F = cast<SharedFile<ELFT>>(File);
+      F->AllNeededIsKnown = llvm::all_of(F->DtNeeded, [&](StringRef Needed) {
+        return Symtab->SoNames.count(Needed);
+      });
+    }
+    for (Symbol *Sym : Symtab->getSymbols())
+      if (Sym->isUndefined() && !Sym->isWeak())
+        if (auto *F = dyn_cast_or_null<SharedFile<ELFT>>(Sym->File))
+          if (F->AllNeededIsKnown)
+            error(toString(F) + ": undefined reference to " + toString(*Sym));
+  }
+
   // Now that we have defined all possible global symbols including linker-
   // synthesized ones. Visit all symbols to give the finishing touches.
   for (Symbol *Sym : Symtab->getSymbols()) {
     if (!includeInSymtab(*Sym))
       continue;
     if (In.SymTab)
       In.SymTab->addSymbol(Sym);
 
     if (Sym->includeInDynsym()) {
       In.DynSymTab->addSymbol(Sym);
       if (auto *File = dyn_cast_or_null<SharedFile<ELFT>>(Sym->File))
         if (File->IsNeeded && !Sym->isUndefined())
           InX<ELFT>::VerNeed->addSymbol(Sym);
     }
   }
 
   // Do not proceed if there was an undefined symbol.

test/ELF/allow-shlib-undefined.s

 # REQUIRES: x86
-# --allow-shlib-undefined and --no-allow-shlib-undefined are fully
-# ignored in linker implementation.
 # --allow-shlib-undefined is set by default
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux \
-# RUN: %p/Inputs/allow-shlib-undefined.s -o %t
-# RUN: ld.lld -shared %t -o %t.so
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1
-
-# Executable: should link with DSO containing undefined symbols in any case.
-# RUN: ld.lld %t1 %t.so -o %t2
-# RUN: ld.lld --no-allow-shlib-undefined %t1 %t.so -o %t2
-# RUN: ld.lld --allow-shlib-undefined %t1 %t.so -o %t2
+# RUN:   %p/Inputs/allow-shlib-undefined.s -o %t1.o
+# RUN: ld.lld -shared %t1.o -o %t.so
+
+# RUN: ld.lld %t.o %t.so -o /dev/null
+# RUN: ld.lld --allow-shlib-undefined %t.o %t.so -o /dev/null
+# RUN: not ld.lld --no-allow-shlib-undefined %t.o %t.so -o /dev/null 2>&1 | FileCheck %s
+
+# RUN: echo | llvm-mc -filetype=obj -triple=x86_64-unknown-linux -o %tempty.o
+# RUN: ld.lld -shared %tempty.o -o %tempty.so
+# RUN: ld.lld -shared %t1.o %tempty.so -o %t2.so
+# RUN: ld.lld --no-allow-shlib-undefined %t.o %t2.so -o /dev/null
 
 # DSO with undefines:
 # should link with or without any of these options.
-# RUN: ld.lld -shared %t -o %t.so
-# RUN: ld.lld -shared --allow-shlib-undefined %t -o %t.so
-# RUN: ld.lld -shared --no-allow-shlib-undefined %t -o %t.so
-
-# Executable still should not link when have undefines inside.
-# RUN: not ld.lld %t -o %t.so
+# RUN: ld.lld -shared %t1.o -o /dev/null
+# RUN: ld.lld -shared --allow-shlib-undefined %t1.o -o /dev/null
+# RUN: ld.lld -shared --no-allow-shlib-undefined %t1.o -o /dev/null
 
 .globl _start
 _start:
   callq _shared@PLT
+
+# CHECK: undefined reference to _unresolved