[lld] [ELF] Only mark as DT_NEEDED libs that are strictly necessary

[rafaelauler]

Summary

This patch enhances the creation of an ELF dynamic executable by avoiding
recording unnecessary shared libraries as NEEDED to load this program.

To do this, we must keep track of not only symbols that were referenced but
also of COPY relocations, which steal the symbol from a shared library but does
not store from which lib this symbol came from. To fix this, this patch changes
ObjectSymbol to store the original library from which this symbol came. With
this information, we are able to build a list of the exact shared libraries that
must be marked as DT_NEEDED, instead of blindly marking all shared libraries as
needed.

This logic originally came from the MIPS backend with some adaptation.

[atanasyan]

LGTM

[• shankar.easwaran]

LGTM

[rafaelauler]

Committed r219353.

include/lld/ReaderWriter/ELFLinkingContext.h

public:
   /// This table is evaluated at loadtime by the dynamic loader and is
   /// referenced by the DT_RELA{,ENT,SZ} entries in the dynamic table.
   /// Relocations that return true will be added to the dynamic relocation
   /// table.
   virtual bool isDynamicRelocation(const DefinedAtom &,
                                    const Reference &) const {
     return false;
   }
+
+  /// \brief Is this a copy relocation?
+  ///
+  /// If this is a copy relocation, its target must be an ObjectAtom. We must
+  /// include in DT_NEEDED the name of the library where this object came from.
+  virtual bool isCopyRelocation(const Reference &) const {
+    return false;
+  }
+
   bool validateImpl(raw_ostream &diagnostics) override;
 
   /// \brief Does the linker allow dynamic libraries to be linked with?
   /// This is true when the output mode of the executable is set to be
   /// having NMAGIC/OMAGIC
   virtual bool allowLinkWithDynamicLibraries() const {
     if (_outputMagic == OutputMagic::NMAGIC ||
         _outputMagic == OutputMagic::OMAGIC || _noAllowDynamicLibraries)

lib/ReaderWriter/ELF/AArch64/AArch64LinkingContext.h

bool isDynamicRelocation(const DefinedAtom &,
     case llvm::ELF::R_AARCH64_TLSDESC:
     case llvm::ELF::R_AARCH64_IRELATIVE:
       return true;
     default:
       return false;
     }
   }
 
+  bool isCopyRelocation(const Reference &r) const override {
+    if (r.kindNamespace() != Reference::KindNamespace::ELF)
+      return false;
+    assert(r.kindArch() == Reference::KindArch::AArch64);
+    if (r.kindValue() == llvm::ELF::R_AARCH64_COPY)
+      return true;
+    return false;
+  }
+
   bool isPLTRelocation(const DefinedAtom &,
                                const Reference &r) const override {
     if (r.kindNamespace() != Reference::KindNamespace::ELF)
       return false;
     assert(r.kindArch() == Reference::KindArch::AArch64);
     switch (r.kindValue()) {
     case llvm::ELF::R_AARCH64_JUMP_SLOT:
     case llvm::ELF::R_AARCH64_IRELATIVE:

lib/ReaderWriter/ELF/AArch64/AArch64RelocationPass.cpp

#endif
     return pa;
   }
 
   const ObjectAtom *getObjectEntry(const SharedLibraryAtom *a) {
     auto obj = _objectMap.find(a);
     if (obj != _objectMap.end())
       return obj->second;
 
-    auto oa = new (_file._alloc) ObjectAtom(_file);
+    auto oa = new (_file._alloc) ObjectAtom(_file, a);
     // This needs to point to the atom that we just created.
     oa->addReferenceELF_AArch64(R_AARCH64_COPY, 0, oa, 0);
 
     oa->_name = a->name();
     oa->_size = a->size();
 
     _objectMap[a] = oa;
     _objectVector.push_back(oa);

lib/ReaderWriter/ELF/Atoms.h

void addReferenceELF_AArch64(uint16_t relocType, uint64_t off, const Atom *t,
                                Reference::Addend a) {
     this->addReferenceELF(Reference::KindArch::AArch64, relocType, off, t, a);
   }
 };
 
 /// \brief Atom which represents an object for which a COPY relocation will be
 ///   generated.
 class ObjectAtom : public SimpleELFDefinedAtom {
+  const SharedLibraryAtom *_sla;
+
 public:
-  ObjectAtom(const File &f) : SimpleELFDefinedAtom(f) {}
+  ObjectAtom(const File &f, const SharedLibraryAtom *sla)
+      : SimpleELFDefinedAtom(f), _sla(sla) {}
 
   Scope scope() const override { return scopeGlobal; }
 
   SectionChoice sectionChoice() const override { return sectionBasedOnContent; }
 
   ContentType contentType() const override { return typeZeroFill; }
 
   uint64_t size() const override { return _size; }
 
   DynamicExport dynamicExport() const override { return dynamicExportAlways; }
 
   ContentPermissions permissions() const override { return permRW_; }
 
   ArrayRef<uint8_t> rawContent() const override { return ArrayRef<uint8_t>(); }
 
   Alignment alignment() const override {
     // The alignment should be 8 byte aligned
     return Alignment(3);
   }
 
   StringRef name() const override { return _name; }
 
+  const SharedLibraryAtom *getOriginalOwner() const { return _sla; }
+
   std::string _name;
   uint64_t _size;
 };
 
 class GOTAtom : public SimpleELFDefinedAtom {
   StringRef _section;
 
 public:

lib/ReaderWriter/ELF/DefaultLayout.h

 //===- lib/ReaderWriter/ELF/DefaultLayout.h -------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_READER_WRITER_ELF_DEFAULT_LAYOUT_H
 #define LLD_READER_WRITER_ELF_DEFAULT_LAYOUT_H
 
+#include "Atoms.h"
 #include "Chunk.h"
 #include "HeaderChunks.h"
 #include "Layout.h"
 #include "SectionChunks.h"
 #include "SegmentChunks.h"
 
 #include "lld/Core/Instrumentation.h"
 #include "lld/Core/STDExtras.h"
struct FindByName {
     const std::string _name;
     FindByName(StringRef name) : _name(name) {}
     bool operator()(const lld::AtomLayout *j) { return j->_atom->name() == _name; }
   };
 
   typedef typename std::vector<lld::AtomLayout *>::iterator AbsoluteAtomIterT;
 
   typedef llvm::DenseSet<const Atom *> AtomSetT;
+  typedef llvm::DenseSet<const SharedLibraryAtom *> SharedLibraryAtomSetT;
 
   DefaultLayout(const ELFLinkingContext &context) : _context(context) {}
 
   /// \brief Return the section order for a input section
   SectionOrder getSectionOrder(StringRef name, int32_t contentType,
                                int32_t contentPermissions) override;
 
   /// \brief This maps the input sections to the output section names
for (const auto &phdr : *_programHeader)
         return phdr->p_memsz;
     return 0;
   }
 
   bool isReferencedByDefinedAtom(const Atom *a) const {
     return _referencedDynAtoms.count(a);
   }
 
+  const SharedLibraryAtomSetT &getCopiedDynAtoms() const {
+    return _copiedDynAtoms;
+  }
+
 protected:
   /// \brief Allocate a new section.
   virtual AtomSection<ELFT> *createSection(
       StringRef name, int32_t contentType,
       DefinedAtom::ContentPermissions contentPermissions,
       SectionOrder sectionOrder);
 
 protected:
   llvm::BumpPtrAllocator _allocator;
   SectionMapT _sectionMap;
   MergedSectionMapT _mergedSectionMap;
   AdditionalSegmentMapT _additionalSegmentMap;
   SegmentMapT _segmentMap;
   std::vector<Chunk<ELFT> *> _sections;
   std::vector<Segment<ELFT> *> _segments;
   std::vector<MergedSections<ELFT> *> _mergedSections;
   ELFHeader<ELFT> *_elfHeader;
   ProgramHeader<ELFT> *_programHeader;
   LLD_UNIQUE_BUMP_PTR(RelocationTable<ELFT>) _dynamicRelocationTable;
   LLD_UNIQUE_BUMP_PTR(RelocationTable<ELFT>) _pltRelocationTable;
   std::vector<lld::AtomLayout *> _absoluteAtoms;
   AtomSetT _referencedDynAtoms;
+  SharedLibraryAtomSetT _copiedDynAtoms;
   const ELFLinkingContext &_context;
 };
 
 /// \brief Handle linker scripts. TargetLayouts would derive
 /// from this class to override some of the functionalities.
 template<class ELFT>
 class ScriptLayout: public DefaultLayout<ELFT> {
 public:
for (const auto &reloc : *definedAtom) {
 
       if (!reloc->target())
         continue;
 
       //Ignore undefined atoms that are not target of dynamic relocations
       if (isa<UndefinedAtom>(reloc->target()) && isLocalReloc)
         continue;
 
+      if (!_context.isCopyRelocation(*reloc)) {
         _referencedDynAtoms.insert(reloc->target());
+        continue;
+      }
+
+      const ObjectAtom *oa = dyn_cast<ObjectAtom>(reloc->target());
+      assert (oa != nullptr && "Targets of copy relocs must be ObjectAtoms");
+      _copiedDynAtoms.insert(oa->getOriginalOwner());
     }
 
     return section->appendAtom(atom);
   } else if (const AbsoluteAtom *absoluteAtom = dyn_cast<AbsoluteAtom>(atom)) {
     // Absolute atoms are not part of any section, they are global for the whole
     // link
     _absoluteAtoms.push_back(new (_allocator)
         lld::AtomLayout(absoluteAtom, 0, absoluteAtom->value()));

lib/ReaderWriter/ELF/Mips/MipsDynamicLibraryWriter.h

protected:
   void finalizeDefaultAtomValues() override;
 
   std::error_code setELFHeader() override {
     DynamicLibraryWriter<ELFT>::setELFHeader();
     _writeHelper.setELFHeader(*this->_elfHeader);
     return std::error_code();
   }
 
-  bool isNeededTagRequired(const SharedLibraryAtom *sla) const override {
-    return _writeHelper.isNeededTagRequired(sla);
-  }
-
   LLD_UNIQUE_BUMP_PTR(DynamicTable<ELFT>) createDynamicTable();
 
   LLD_UNIQUE_BUMP_PTR(DynamicSymbolTable<ELFT>) createDynamicSymbolTable();
 
 private:
   MipsELFWriter<ELFT> _writeHelper;
   MipsLinkingContext &_mipsContext;
   MipsTargetLayout<Mips32ElELFType> &_mipsTargetLayout;

lib/ReaderWriter/ELF/Mips/MipsELFWriters.h

if (_ctx.isDynamic()) {
       file->addAbsoluteAtom("_GLOBAL_OFFSET_TABLE_");
       file->addAbsoluteAtom("_gp");
       file->addAbsoluteAtom("_gp_disp");
       file->addAbsoluteAtom("__gnu_local_gp");
     }
     return file;
   }
 
-  bool isNeededTagRequired(const SharedLibraryAtom *sla) const {
-    return _targetLayout.isReferencedByDefinedAtom(sla) ||
-           _targetLayout.isCopied(sla);
-  }
-
 private:
   MipsLinkingContext &_ctx;
   MipsTargetLayout<ELFT> &_targetLayout;
 
   void setAtomValue(StringRef name, uint64_t value) {
     auto atom = _targetLayout.findAbsoluteAtom(name);
     assert(atom != _targetLayout.absoluteAtoms().end());
     (*atom)->_virtualAddr = value;
   }
 };
 
 } // elf
 } // lld
 
 #endif

lib/ReaderWriter/ELF/Mips/MipsExecutableWriter.h

protected:
   void finalizeDefaultAtomValues() override;
 
   std::error_code setELFHeader() override {
     ExecutableWriter<ELFT>::setELFHeader();
     _writeHelper.setELFHeader(*this->_elfHeader);
     return std::error_code();
   }
 
-  bool isNeededTagRequired(const SharedLibraryAtom *sla) const override {
-    return _writeHelper.isNeededTagRequired(sla);
-  }
-
   LLD_UNIQUE_BUMP_PTR(DynamicTable<ELFT>) createDynamicTable();
 
   LLD_UNIQUE_BUMP_PTR(DynamicSymbolTable<ELFT>) createDynamicSymbolTable();
 
 private:
   MipsELFWriter<ELFT> _writeHelper;
   MipsLinkingContext &_mipsContext;
   MipsTargetLayout<Mips32ElELFType> &_mipsTargetLayout;

lib/ReaderWriter/ELF/Mips/MipsLinkingContext.h

public:
   bool isLittleEndian() const override;
   uint64_t getBaseAddress() const override;
   StringRef entrySymbolName() const override;
   StringRef getDefaultInterpreter() const override;
   void addPasses(PassManager &pm) override;
   bool isRelaOutputFormat() const override { return false; }
   bool isDynamicRelocation(const DefinedAtom &,
                            const Reference &r) const override;
+  bool isCopyRelocation(const Reference &r) const override;
   bool isPLTRelocation(const DefinedAtom &, const Reference &r) const override;
 };
 
 } // elf
 } // lld
 
 #endif

lib/ReaderWriter/ELF/Mips/MipsLinkingContext.cpp

bool MipsLinkingContext::isDynamicRelocation(const DefinedAtom &,
   case llvm::ELF::R_MIPS_TLS_DTPREL32:
   case llvm::ELF::R_MIPS_TLS_TPREL32:
     return true;
   default:
     return false;
   }
 }
 
+bool MipsLinkingContext::isCopyRelocation(const Reference &r) const {
+  if (r.kindNamespace() != Reference::KindNamespace::ELF)
+    return false;
+  assert(r.kindArch() == Reference::KindArch::Mips);
+  if (r.kindValue() == llvm::ELF::R_MIPS_COPY)
+    return true;
+  return false;
+}
+
 bool MipsLinkingContext::isPLTRelocation(const DefinedAtom &,
                                          const Reference &r) const {
   if (r.kindNamespace() != Reference::KindNamespace::ELF)
     return false;
   assert(r.kindArch() == Reference::KindArch::Mips);
   switch (r.kindValue()) {
   case llvm::ELF::R_MIPS_JUMP_SLOT:
     return true;
   default:
     return false;
   }
 }

lib/ReaderWriter/ELF/Mips/MipsRelocationPass.cpp

 
 template <typename ELFT>
 const ObjectAtom *
 RelocationPass<ELFT>::getObjectEntry(const SharedLibraryAtom *a) {
   auto obj = _objectMap.find(a);
   if (obj != _objectMap.end())
     return obj->second;
 
-  auto oa = new (_file._alloc) ObjectAtom(_file);
+  auto oa = new (_file._alloc) ObjectAtom(_file, a);
   oa->addReferenceELF_Mips(R_MIPS_COPY, 0, oa, 0);
   oa->_name = a->name();
   oa->_size = a->size();
 
   _objectMap[a] = oa;
   _objectVector.push_back(oa);
 
   return oa;

lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h

Layout::SegmentType getSegmentType(Section<ELFType> *section) const override {
     case DefaultLayout<ELFType>::ORDER_CTORS:
     case DefaultLayout<ELFType>::ORDER_DTORS:
       return llvm::ELF::PT_LOAD;
     default:
       return TargetLayout<ELFType>::getSegmentType(section);
     }
   }
 
-  ErrorOr<const lld::AtomLayout &> addAtom(const Atom *atom) override {
-    // Maintain:
-    // 1. Set of shared library atoms referenced by regular defined atoms.
-    // 2. Set of shared library atoms have corresponding R_MIPS_COPY copies.
-    if (const auto *da = dyn_cast<DefinedAtom>(atom))
-      for (const Reference *ref : *da) {
-        if (ref->kindNamespace() == lld::Reference::KindNamespace::ELF) {
-          assert(ref->kindArch() == Reference::KindArch::Mips);
-          if (ref->kindValue() == llvm::ELF::R_MIPS_COPY)
-            _copiedDynSymNames.insert(atom->name());
-        }
-      }
-
-    return TargetLayout<ELFType>::addAtom(atom);
-  }
-
-  bool isCopied(const SharedLibraryAtom *sla) const {
-    return _copiedDynSymNames.count(sla->name());
-  }
-
   /// \brief GP offset relative to .got section.
   uint64_t getGPOffset() const { return 0x7FF0; }
 
   /// \brief Get '_gp' symbol atom layout.
   AtomLayout *getGP() {
     if (!_gpAtom.hasValue()) {
       auto atom = this->findAbsoluteAtom("_gp");
       _gpAtom = atom != this->absoluteAtoms().end() ? *atom : nullptr;
public:
   }
 
 private:
   llvm::BumpPtrAllocator _alloc;
   MipsGOTSection<ELFType> *_gotSection;
   MipsPLTSection<ELFType> *_pltSection;
   llvm::Optional<AtomLayout *> _gpAtom;
   llvm::Optional<AtomLayout *> _gpDispAtom;
-  llvm::StringSet<> _copiedDynSymNames;
 };
 
 /// \brief Mips Runtime file.
 template <class ELFType>
 class MipsRuntimeFile final : public CRuntimeFile<ELFType> {
 public:
   MipsRuntimeFile(const MipsLinkingContext &ctx)
       : CRuntimeFile<ELFType>(ctx, "Mips runtime file") {}

lib/ReaderWriter/ELF/OutputELFWriter.h

if (auto section = dyn_cast<AtomSection<ELFT>>(sec))
       for (const auto &atom : section->atoms()) {
         const DefinedAtom *da = dyn_cast<const DefinedAtom>(atom->_atom);
         if (da && (da->dynamicExport() == DefinedAtom::dynamicExportAlways ||
                    _context.isDynamicallyExportedSymbol(da->name())))
           _dynamicSymbolTable->addSymbol(atom->_atom, section->ordinal(),
                                          atom->_virtualAddr, atom);
       }
   for (const auto &sla : file.sharedLibrary()) {
-    if (isDynSymEntryRequired(sla))
-      _dynamicSymbolTable->addSymbol(sla, ELF::SHN_UNDEF);
+    if (!isDynSymEntryRequired(sla))
+      continue;
     if (isNeededTagRequired(sla))
       _soNeeded.insert(sla->loadName());
   }
+  for (const auto &sla : _layout.getCopiedDynAtoms())
+    _soNeeded.insert(sla->loadName());
   // Never mark the dynamic linker as DT_NEEDED
   _soNeeded.erase(sys::path::filename(_context.getInterpreter()));
   for (const auto &loadName : _soNeeded) {
     Elf_Dyn dyn;
     dyn.d_tag = DT_NEEDED;
     dyn.d_un.d_val = _dynamicStringTable->addString(loadName.getKey());
     _dynamicTable->addEntry(dyn);
   }

lib/ReaderWriter/ELF/X86_64/X86_64LinkingContext.h

bool isDynamicRelocation(const DefinedAtom &,
     case llvm::ELF::R_X86_64_DTPMOD64:
     case llvm::ELF::R_X86_64_DTPOFF64:
       return true;
     default:
       return false;
     }
   }
 
+  bool isCopyRelocation(const Reference &r) const override {
+    if (r.kindNamespace() != Reference::KindNamespace::ELF)
+      return false;
+    assert(r.kindArch() == Reference::KindArch::x86_64);
+    if (r.kindValue() == llvm::ELF::R_X86_64_COPY)
+      return true;
+    return false;
+  }
+
   virtual bool isPLTRelocation(const DefinedAtom &,
                                const Reference &r) const override {
     if (r.kindNamespace() != Reference::KindNamespace::ELF)
       return false;
     assert(r.kindArch() == Reference::KindArch::x86_64);
     switch (r.kindValue()) {
     case llvm::ELF::R_X86_64_JUMP_SLOT:
     case llvm::ELF::R_X86_64_IRELATIVE:

lib/ReaderWriter/ELF/X86_64/X86_64RelocationPass.cpp

#endif
     return pa;
   }
 
   const ObjectAtom *getObjectEntry(const SharedLibraryAtom *a) {
     auto obj = _objectMap.find(a);
     if (obj != _objectMap.end())
       return obj->second;
 
-    auto oa = new (_file._alloc) ObjectAtom(_file);
+    auto oa = new (_file._alloc) ObjectAtom(_file, a);
     // This needs to point to the atom that we just created.
     oa->addReferenceELF_x86_64(R_X86_64_COPY, 0, oa, 0);
 
     oa->_name = a->name();
     oa->_size = a->size();
 
     _objectMap[a] = oa;
     _objectVector.push_back(oa);