[WIP] [ELF] Implement --copy-dt-needed-entries

[mgorny]

Summary

This is my proof-of-concept on making --copy-dt-needed-entries work. Apparently, i've been able to hack on it hard enough to make it actually emit DT_NEEDED for all symbols, recursively:

$ clang -fuse-ld=lld  -Wl,--copy-dt-needed-entries test.c  -lgit2
$ readelf -d a.out 

Dynamic section at offset 0x3010 contains 40 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libgit2.so.27]
 0x0000000000000001 (NEEDED)             Shared library: [librt.so.1]
 0x0000000000000001 (NEEDED)             Shared library: [libpthread.so.0]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
 0x0000000000000001 (NEEDED)             Shared library: [ld-linux-x86-64.so.2]
 0x0000000000000001 (NEEDED)             Shared library: [libcurl.so.4]
 0x0000000000000001 (NEEDED)             Shared library: [libcares.so.2]
 0x0000000000000001 (NEEDED)             Shared library: [libnghttp2.so.14]
 0x0000000000000001 (NEEDED)             Shared library: [libidn2.so.4]
 0x0000000000000001 (NEEDED)             Shared library: [libunistring.so.2]
 0x0000000000000001 (NEEDED)             Shared library: [libssl.so.1.1]
 0x0000000000000001 (NEEDED)             Shared library: [libcrypto.so.1.1]
 0x0000000000000001 (NEEDED)             Shared library: [libz.so.1]
 0x0000000000000001 (NEEDED)             Shared library: [libdl.so.2]
 0x0000000000000001 (NEEDED)             Shared library: [libhttp_parser.so.2.9]
 0x0000000000000001 (NEEDED)             Shared library: [libssh2.so.1]
 0x0000000000000015 (DEBUG)              0x0
 0x0000000000000007 (RELA)               0x200620
 0x0000000000000008 (RELASZ)             48 (bytes)
 0x0000000000000009 (RELAENT)            24 (bytes)
 0x0000000000000017 (JMPREL)             0x200650
 0x0000000000000002 (PLTRELSZ)           72 (bytes)
 0x0000000000000003 (PLTGOT)             0x202010
 0x0000000000000014 (PLTREL)             RELA
 0x0000000000000006 (SYMTAB)             0x2002b0
 0x000000000000000b (SYMENT)             24 (bytes)
 0x0000000000000005 (STRTAB)             0x200488
 0x000000000000000a (STRSZ)              404 (bytes)
 0x000000006ffffef5 (GNU_HASH)           0x200400
 0x0000000000000004 (HASH)               0x200428
 0x0000000000000019 (INIT_ARRAY)         0x203008
 0x000000000000001b (INIT_ARRAYSZ)       8 (bytes)
 0x000000000000001a (FINI_ARRAY)         0x203000
 0x000000000000001c (FINI_ARRAYSZ)       8 (bytes)
 0x000000000000000c (INIT)               0x201200
 0x000000000000000d (FINI)               0x201218
 0x000000006ffffff0 (VERSYM)             0x2003b8
 0x000000006ffffffe (VERNEED)            0x2003d0
 0x000000006fffffff (VERNEEDNUM)         1
 0x0000000000000000 (NULL)               0x0

Can't say the code is nice but before I try to make it cleanly, I'd appreciate some tips on whether I'm even starting in the right direction.

FWICS, GNU ld's --copy-dt-needed-entries adds lot less libraries — it seems as if it implicitly forced --as-needed, and --no-as-needed doesn't seem to make a difference.

[joerg]

As first step, it goes into the right direction. I would explicitly set --as-needed for all those indirectly loaded objects. If people want to retain the questionable behavior of newer GNU tools, it could be a separate flag so that a final round can warn if an indirectly pulled library is necessary, but that behavior doesn't IMO make much sense. Full version has to look at DT_RUNPATH/DT_RPATH and also --rpath-link.

[krytarowski]

@ruiu ping?

[MaskRay]

I read your https://blog.netbsd.org/tnf/entry/the_first_report_on_lld :) The chapter "Handling of indirect shared library dependencies" summarizes the transitive DT_NEEDED problem well.

But do we have a convincing list of applications that really need this option to work? According my understanding, lld doesn't try to be fully ld.bfd compatible. It only implements reasonable ld.bfd features that are still used a lot. lld is enabled on FreeBSD 12 and is capable to link nearly all applications (with ~10 exceptions; but nothing uses --copy-dt-needed-entries) (https://bugs.llvm.org/show_bug.cgi?id=23214#c59)

gold doesn't support --copy-dt-needed-entries https://sourceware.org/git/?p=binutils-gdb.git;a=blob;hb=b09e83c1f814a6f218519abeb94aaf45869ba03c;f=gold/object.cc#l3236 It doesn't support --rpath-link either.

In the article,

However, GNU gold, LLD and newer versions of GNU ld use different logic and permit only symbols provided by the direct dependencies.

I just checked that ld.bfd doesn't enable this option by default. It looks like a historical remnant then :)

[krytarowski]

NetBSD patches GNU linker to behave in the original way. This behavior is mandated from lld as well in order to treat it as a drop-in replacement.

Preference here and of other lld characteristics is so strong that the NetBSD community in case of rejected patches will continue to maintain downstream patches.

ELF/Config.h

struct Configuration {
   bool ARMHasBlx = false;
   bool ARMHasMovtMovw = false;
   bool ARMJ1J2BranchEncoding = false;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
   bool CallGraphProfileSort;
   bool CheckSections;
+  bool CopyDtNeededEntries = false;
   bool CompressDebugSections;
   bool Cref;
   bool DefineCommon;
   bool Demangle = true;
   bool DisableVerify;
   bool EhFrameHdr;
   bool EmitLLVM;
   bool EmitRelocs;

ELF/Driver.cpp

if (S == "elf" || S == "default")
     return false;
   error("unknown -format value: " + S +
         " (supported formats: elf, default, binary)");
   return false;
 }
 
 void LinkerDriver::createFiles(opt::InputArgList &Args) {
   // For --{push,pop}-state.
-  std::vector<std::tuple<bool, bool, bool>> Stack;
+  std::vector<std::tuple<bool, bool, bool, bool>> Stack;
 
   // Iterate over argv to process input files and positional arguments.
   for (auto *Arg : Args) {
     switch (Arg->getOption().getUnaliasedOption().getID()) {
     case OPT_library:
       addLibrary(Arg->getValue());
       break;
     case OPT_INPUT:
case OPT_script:
           readLinkerScript(*MB);
         break;
       }
       error(Twine("cannot find linker script ") + Arg->getValue());
       break;
     case OPT_as_needed:
       Config->AsNeeded = true;
       break;
+    case OPT_copy_dt_needed_entries:
+      Config->CopyDtNeededEntries = true;
+      break;
     case OPT_format:
       Config->FormatBinary = isFormatBinary(Arg->getValue());
       break;
     case OPT_no_as_needed:
       Config->AsNeeded = false;
       break;
+    case OPT_no_copy_dt_needed_entries:
+      Config->CopyDtNeededEntries = false;
+      break;
     case OPT_Bstatic:
       Config->Static = true;
       break;
     case OPT_Bdynamic:
       Config->Static = false;
       break;
     case OPT_whole_archive:
       InWholeArchive = true;
for (auto *Arg : Args) {
     case OPT_end_lib:
       if (!InLib)
         error("stray --end-lib");
       InLib = false;
       InputFile::IsInGroup = false;
       ++InputFile::NextGroupId;
       break;
     case OPT_push_state:
-      Stack.emplace_back(Config->AsNeeded, Config->Static, InWholeArchive);
+      Stack.emplace_back(Config->AsNeeded, Config->Static, InWholeArchive,
+                         Config->CopyDtNeededEntries);
       break;
     case OPT_pop_state:
       if (Stack.empty()) {
         error("unbalanced --push-state/--pop-state");
         break;
       }
-      std::tie(Config->AsNeeded, Config->Static, InWholeArchive) = Stack.back();
+      std::tie(Config->AsNeeded, Config->Static, InWholeArchive,
+               Config->CopyDtNeededEntries) = Stack.back();
       Stack.pop_back();
       break;
     }
   }
 
   if (Files.empty() && errorCount() == 0)
     error("no input files");
 }

ELF/InputFiles.h

public:
 
   SharedFile(MemoryBufferRef M, StringRef DefaultSoName);
 
   void parseSoName();
   void parseRest();
   uint32_t getAlignment(ArrayRef<Elf_Shdr> Sections, const Elf_Sym &Sym);
   std::vector<const Elf_Verdef *> parseVerdefs();
   std::vector<uint32_t> parseVersyms();
+  std::vector<std::string> parseDtNeeded();
 
   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 --as-needed
   bool IsNeeded;
+
+  // Used for --copy-dt-needed-entries
+  bool CopyDtNeeded;
 };
 
 class BinaryFile : public InputFile {
 public:
   explicit BinaryFile(MemoryBufferRef M) : InputFile(BinaryKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == BinaryKind; }
   void parse();
 };

ELF/InputFiles.cpp

InputFile *File = createObjectFile(
       MB, getName(), C.getParent()->isThin() ? 0 : C.getChildOffset());
   File->GroupId = GroupId;
   return File;
 }
 
 template <class ELFT>
 SharedFile<ELFT>::SharedFile(MemoryBufferRef M, StringRef DefaultSoName)
     : ELFFileBase<ELFT>(Base::SharedKind, M), SoName(DefaultSoName),
-      IsNeeded(!Config->AsNeeded) {}
+      IsNeeded(!Config->AsNeeded), CopyDtNeeded(Config->CopyDtNeededEntries)
+{}
 
 // Partially parse the shared object file so that we can call
 // getSoName on this object.
 template <class ELFT> void SharedFile<ELFT>::parseSoName() {
   const Elf_Shdr *DynamicSec = nullptr;
   const ELFFile<ELFT> Obj = this->getObj();
   ArrayRef<Elf_Shdr> Sections = CHECK(Obj.sections(), this);
 
for (unsigned I = 0; I != VerdefCount; ++I) {
     unsigned VerdefIndex = CurVerdef->vd_ndx;
     Verdefs.resize(VerdefIndex + 1);
     Verdefs[VerdefIndex] = CurVerdef;
   }
 
   return Verdefs;
 }
 
+// Parse the shared object file for list of DT_NEEDED libraries.
+template <class ELFT>
+std::vector<std::string> SharedFile<ELFT>::parseDtNeeded() {
+  const ELFFile<ELFT> Obj = this->getObj();
+  ArrayRef<typename ELFT::Shdr> Sections = CHECK(Obj.sections(), this);
+  std::vector<std::string> DtNeeded;
+
+  for (const typename ELFT::Shdr &Sec : Sections) {
+    if (Sec.sh_type != SHT_DYNAMIC)
+      continue;
+
+    ArrayRef<Elf_Dyn> Arr =
+        CHECK(Obj.template getSectionContentsAsArray<Elf_Dyn>(&Sec), this);
+    for (const Elf_Dyn &Dyn : Arr) {
+      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);
+      }
+    }
+
+    break;
+  }
+  return DtNeeded;
+}
+
 // We do not usually care about alignments of data in shared object
 // files because the loader takes care of it. However, if we promote a
 // DSO symbol to point to .bss due to copy relocation, we need to keep
 // the original alignment requirements. We infer it in this function.
 template <class ELFT>
 uint32_t SharedFile<ELFT>::getAlignment(ArrayRef<Elf_Shdr> Sections,
                                         const Elf_Sym &Sym) {
   uint64_t Ret = UINT64_MAX;

ELF/Options.td

 
 def color_diagnostics: F<"color-diagnostics">,
   HelpText<"Alias for --color-diagnostics=always">;
 
 def color_diagnostics_eq: J<"color-diagnostics=">,
   HelpText<"Use colors in diagnostics">,
   MetaVarName<"[auto,always,never]">;
 
+defm copy_dt_needed_entries: B<"copy-dt-needed-entries",
+    "Recursively include all dependencies (DT_NEEDED) of linked libraries in the executable",
+    "Include only DT_NEEDED entries for libraries explicity listed (default)">;
+
 defm cref: B<"cref",
     "Output cross reference table",
     "Do not output cross reference table">;
 
 defm define_common: B<"define-common",
     "Assign space to common symbols",
     "Do not assign space to common symbols">;
 

 
 // 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">;
 def: F<"stats">;

ELF/SymbolTable.cpp

 // all input files to the symbol table. The symbol table is basically
 // a hash table with the logic to resolve symbol name conflicts using
 // the symbol types.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolTable.h"
 #include "Config.h"
+#include "Driver.h"
 #include "LinkerScript.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
 #include "llvm/ADT/STLExtras.h"
 
if (auto *F = dyn_cast<SharedFile<ELFT>>(File)) {
     DenseMap<StringRef, InputFile *>::iterator It;
     bool WasInserted;
     std::tie(It, WasInserted) = SoNames.try_emplace(F->SoName, F);
     cast<SharedFile<ELFT>>(It->second)->IsNeeded |= F->IsNeeded;
     if (!WasInserted)
       return;
 
     SharedFiles.push_back(F);
+    if (F->CopyDtNeeded) {
+      for (std::string& DtNeeded : F->parseDtNeeded()) {
+        if (Optional<std::string> Path = searchLibrary(":" + DtNeeded)) {
+          // TODO: how does memory management work here?
+          if (Optional<MemoryBufferRef> Buffer = readFile(*Path))
+            addFile<ELFT>(make<SharedFile<ELFT>>(*Buffer, DtNeeded));
+        } else {
+          // TODO: error out?
+        }
+      }
+    }
     F->parseRest();
     return;
   }
 
   // LLVM bitcode file
   if (auto *F = dyn_cast<BitcodeFile>(File)) {
     BitcodeFiles.push_back(F);
     F->parse<ELFT>(ComdatGroups);