[ELF] LLD does not create a record in the .dynsym if a strong symbol defined in the executable file replaces a weak symbol from a shared library.

[atanasyan]

Summary

LLD does not create a record in the .dynsym if a strong symbol defined in the executable file replaces a weak symbol from a shared library. This bug affects all ELF architectures and leads to segfault:

% cat foo.c
extern int __attribute__((weak)) flag;
int foo() { return flag; }

% cat main.c
int flag = 1;
int foo();
int main() { return foo() == 1 ? 0 : -1; }

% clang -c -fPIC foo.c main.c
% lld -flavor gnu -target x86_64 -shared -o libfoo.so ... foo.o
% lld -flavor gnu -target x86_64 -o a.out ... main.o libfoo.so
% ./a.out
Segmentation fault

The problem is in the Resolver class. We lose all information about coalesced symbols after the Resolver::resolve() method is finished. Besides, the symbol resolving code is target independent and we need to keep it in this state.

The patch solves the problem by introducing a new class ELFResolver which is inherited from the Resolver class. In this new class we override the checkUndefines() method, iterate over atoms and configure dynamic export settings for ELFDefinedAtom when necessary.

The Driver class requests an instance if the Resolver class from the LinkingContext. For non-ELF targets we continue to use Resolver class. For ELF targets we create an instance of ELFResolver.

[• shankar.easwaran]

The best way to do this is using a ELF reference that sets a dynamic export tag. We should not be adding a export dynamic to an atom as that's not a property.

[atanasyan]

Symbols require to be exported is now tagged using an ELFReference.

[ruiu]

I'd think we shouldn't subclass Resolver class. Windows linker is probably more different from the original Resolver class behavior but we can still be able to share the class. Also Resolver class already contains some arch/binary format specific code -- for example, fallback atom for Windows and GNU LinkOnce attribute for ELF. I understand the reason why you are adding this code, but what this patch is trying to do seems rather simple compared to its patch size. It feels it's probably better not to subclassing the entire class but instead add a few lines to Resolver directly.

That being said, I don't have a concrete idea on how to do it. The issue is that we lose the information that an undefined atom had after it's coalesced away. That happens in Resolver::updateReference(), in which we completely ditches coalesed-away atoms. Maybe we should add code there to copy some information from a coalesed-away atom to a replacing atom. Then the ELF writer is able to see that to decide if it needs a .dynsym entry for a replacement atom.

[shankarke]

IMO

• We should not be adding dynamicExport() to the Atom, as its not a property of the Atom.
• We should not add a new Resolver.

What we could do is

a) Create references dynamicExportNone, dynamicExportAsNeeded, dynamicExportAlways(For shared libraries)

b) The reader would set the reference to be dynamicExportNone for all atoms that it creates,

c) A new pass (DynamicSymbolTableCreate) would go through all atoms, and if has been resolved from a shared library, sets it to dynamicExportAsNeeded.

d) The ELF writer would go through all the atoms that have been set dynamicExportAsNeeded and create dynsym entries.

With this change, there is no change needed in the Resolver and there is no need of a ELFResolver.

[atanasyan]

Thanks for review. I will try to implement another solution using your ideas.

[kledzik]

From the description of the problem, I thought that libfoo would have a weak definition of "flag" and main had a strong definition of "flag" and the problem was that the binaries were not set up properly so that ld.so would pick main's flag to override libfoo's flag.

But looking at the example code, "flag" is extern. So this seems like the other meaning of weak - that the symbol can be missing at runtime. But the use of "flag" in foo() is not checking if its address is NULL before accessing. But in this case it should not be NULL because ld.so should find it in main.

Which case is this?

What info is missing after resolve() is done?

[shankarke]

When the weak symbol in the shared library is resolved from another object file when building an executable that symbol would need to be exported.

I was suggesting to have a reference in the atom that if it needs to be exported, be set to exportDynamic during the resolution phase.

It could be recorded in the elf context as well but to be cleaner I felt that a reference used.

Does that sound the right way (or) I am over complicating things ?

Shankar Easwaran

include/lld/Core/LinkingContext.h

 #include <vector>
 
 namespace lld {
 class PassManager;
 class File;
 class Writer;
 class InputGraph;
 class InputElement;
+class Resolver;
 class SharedLibraryFile;
 
 /// \brief The LinkingContext class encapsulates "what and how" to link.
 ///
 /// The base class LinkingContext contains the options needed by core linking.
 /// Subclasses of LinkingContext have additional options needed by specific
 /// Writers. For example, ELFLinkingContext has methods that supplies
 /// options to the ELF Writer and ELF Passes.
public:
   typedef StringRefVector::const_iterator StringRefVectorConstIter;
 
   /// Create linker internal files containing atoms for the linker to include
   /// during link. Flavors can override this function in their LinkingContext
   /// to add more internal files. These internal files are positioned before
   /// the actual input files.
   virtual void createInternalFiles(std::vector<std::unique_ptr<File> > &) const;
 
+  virtual std::unique_ptr<Resolver> getResolver();
+
   /// Return the list of undefined symbols that are specified in the
   /// linker command line, using the -u option.
   range<const StringRef *> initialUndefinedSymbols() const {
     return _initialUndefinedSymbols;
   }
 
   /// After all set* methods are called, the Driver calls this method
   /// to validate that there are no missing options or invalid combinations

include/lld/Core/Reference.h

enum {
     // pass.
     kindLayoutAfter = 2,
     // kindLayoutBefore is currently used only by PECOFF port, and will
     // be removed soon. To enforce layout, use kindLayoutAfter instead.
     kindLayoutBefore = 3,
     // kindGroupChild is treated as a bidirected edge too.
     kindGroupChild = 4,
     kindAssociate = 5,
+    // kindDynExport marks an ELF atom which needs to have a .dynsym record.
+    kindDynExport = 6,
   };
 
   // A value to be added to the value of a target
   typedef int64_t Addend;
 
   /// If the reference is a fixup in the Atom, then this returns the
   /// byte offset into the Atom's content to do the fix up.
   virtual uint64_t offsetInAtom() const = 0;

include/lld/Core/Resolver.h

 class Atom;
 class LinkingContext;
 
 /// \brief The Resolver is responsible for merging all input object files
 /// and producing a merged graph.
 class Resolver {
 public:
   Resolver(LinkingContext &context)
-      : _context(context), _symbolTable(context), _result(new MergedFile()) {}
+      : _symbolTable(context), _context(context), _result(new MergedFile()) {}
+
+  virtual ~Resolver() {}
 
   // InputFiles::Handler methods
   void doDefinedAtom(const DefinedAtom&);
   bool doUndefinedAtom(const UndefinedAtom &);
   void doSharedLibraryAtom(const SharedLibraryAtom &);
   void doAbsoluteAtom(const AbsoluteAtom &);
 
   // Handle files, this adds atoms from the current file thats
   // being processed by the resolver
   void handleFile(const File &);
 
   // Handle an archive library file.
   void handleArchiveFile(const File &);
 
   // Handle a shared library file.
   void handleSharedLibrary(const File &);
 
   /// @brief do work of merging and resolving and return list
   bool resolve();
 
   std::unique_ptr<MutableFile> resultFile() { return std::move(_result); }
 
+protected:
+  std::vector<const Atom *> _atoms;
+  SymbolTable _symbolTable;
+
+  virtual bool checkUndefines();
+
+  template <class T, class... Args> T *makeReference(Args &&... args) {
+    return new (_result->_allocator) T(std::forward<Args>(args)...);
+  }
+
 private:
   typedef std::function<void(StringRef, bool)> UndefCallback;
 
   /// \brief Add section group/.gnu.linkonce if it does not exist previously.
   void maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom);
 
   /// \brief The main function that iterates over the files to resolve
   bool resolveUndefines();
   void updateReferences();
   void deadStripOptimize();
-  bool checkUndefines();
   void removeCoalescedAwayAtoms();
   void checkDylibSymbolCollisions();
   void forEachUndefines(bool searchForOverrides, UndefCallback callback);
 
   void markLive(const Atom *atom);
   void addAtoms(const std::vector<const DefinedAtom *>&);
 
   class MergedFile : public MutableFile {
   public:
+    llvm::BumpPtrAllocator _allocator;
+
     MergedFile() : MutableFile("<linker-internal>") {}
 
     const atom_collection<DefinedAtom> &defined() const override {
       return _definedAtoms;
     }
     const atom_collection<UndefinedAtom>& undefined() const override {
       return _undefinedAtoms;
     }
private:
   private:
     atom_collection_vector<DefinedAtom>         _definedAtoms;
     atom_collection_vector<UndefinedAtom>       _undefinedAtoms;
     atom_collection_vector<SharedLibraryAtom>   _sharedLibraryAtoms;
     atom_collection_vector<AbsoluteAtom>        _absoluteAtoms;
   };
 
   LinkingContext &_context;
-  SymbolTable _symbolTable;
-  std::vector<const Atom *>     _atoms;
   std::set<const Atom *>        _deadStripRoots;
   llvm::DenseSet<const Atom *>  _liveAtoms;
   llvm::DenseSet<const Atom *>  _deadAtoms;
   std::unique_ptr<MergedFile>   _result;
   llvm::DenseMap<const Atom *, llvm::DenseSet<const Atom *>> _reverseRef;
 };
 
 } // namespace lld
 
 #endif // LLD_CORE_RESOLVER_H

include/lld/ReaderWriter/ELFLinkingContext.h

public:
   virtual ~TargetHandlerBase() {}
   virtual void registerRelocationNames(Registry &) = 0;
 
   virtual std::unique_ptr<Reader> getObjReader(bool) = 0;
 
   virtual std::unique_ptr<Reader> getDSOReader(bool) = 0;
 
   virtual std::unique_ptr<Writer> getWriter() = 0;
+
+  virtual std::unique_ptr<Resolver> getResolver() = 0;
 };
 
 class ELFLinkingContext : public LinkingContext {
 public:
 
   /// \brief The type of ELF executable that the linker
   /// creates.
   enum class OutputMagic : uint8_t {
public:
   void setNoInhibitExec(bool v) { _noInhibitExec = v; }
   void setIsStaticExecutable(bool v) { _isStaticExecutable = v; }
   void setMergeCommonStrings(bool v) { _mergeCommonStrings = v; }
   void setUseShlibUndefines(bool use) { _useShlibUndefines = use; }
   void setOutputELFType(uint32_t type) { _outputELFType = type; }
 
   void createInternalFiles(std::vector<std::unique_ptr<File>> &) const override;
 
+  std::unique_ptr<Resolver> getResolver() override;
+
   /// \brief Set the dynamic linker path
   void setInterpreter(StringRef dynamicLinker) {
     _dynamicLinkerArg = true;
     _dynamicLinkerPath = dynamicLinker;
   }
 
   /// \brief Set NMAGIC output kind when the linker specifies --nmagic
   /// or -n in the command line

lib/Core/LinkingContext.cpp

void LinkingContext::createInternalFiles(
   if (std::unique_ptr<File> file = createEntrySymbolFile())
     result.push_back(std::move(file));
   if (std::unique_ptr<File> file = createUndefinedSymbolFile())
     result.push_back(std::move(file));
   if (std::unique_ptr<File> file = createAliasSymbolFile())
     result.push_back(std::move(file));
 }
 
+std::unique_ptr<Resolver> LinkingContext::getResolver() {
+  return llvm::make_unique<Resolver>(*this);
+}
+
 void LinkingContext::addPasses(PassManager &pm) {}
 
 } // end namespace lld

lib/Driver/Driver.cpp

bool Driver::link(LinkingContext &context, raw_ostream &diagnostics) {
   InputGraph::FileVectorT implicitFiles;
   context.createImplicitFiles(implicitFiles);
   if (implicitFiles.size())
     fileNode->addFiles(std::move(implicitFiles));
   context.getInputGraph().addInputElementFront(std::move(fileNode));
 
   // Do core linking.
   ScopedTask resolveTask(getDefaultDomain(), "Resolve");
-  Resolver resolver(context);
-  if (!resolver.resolve())
+  auto resolver = context.getResolver();
+  if (!resolver->resolve())
     return false;
-  std::unique_ptr<MutableFile> merged = resolver.resultFile();
+  std::unique_ptr<MutableFile> merged = resolver->resultFile();
   resolveTask.end();
 
   // Run passes on linked atoms.
   ScopedTask passTask(getDefaultDomain(), "Passes");
   PassManager pm;
   context.addPasses(pm);
 
 #ifndef NDEBUG

lib/ReaderWriter/ELF/Atoms.h

Scope scope() const override {
     if (_symbol->st_other == llvm::ELF::STV_HIDDEN)
       return scopeLinkageUnit;
     else if (_symbol->getBinding() != llvm::ELF::STB_LOCAL)
       return scopeGlobal;
     else
       return scopeTranslationUnit;
   }
 
+  DynamicExport dynamicExport() const override {
+    for (const auto &r : *this)
+      if (r->kindNamespace() == lld::Reference::KindNamespace::all &&
+          r->kindArch() == lld::Reference::KindArch::all &&
+          r->kindValue() == Reference::kindDynExport)
+        return dynamicExportAlways;
+    return dynamicExportNormal;
+  }
+
   // FIXME: Need to revisit this in future.
   Interposable interposable() const override { return interposeNo; }
 
   // FIXME: What ways can we determine this in ELF?
   Merge merge() const override {
     if (_symbol->getBinding() == llvm::ELF::STB_WEAK)
       return mergeAsWeak;
 

lib/ReaderWriter/ELF/DefaultTargetHandler.h

 //===- lib/ReaderWriter/ELF/DefaultTargetHandler.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_TARGET_HANDLER_H
 #define LLD_READER_WRITER_ELF_DEFAULT_TARGET_HANDLER_H
 
 #include "DefaultLayout.h"
 #include "TargetHandler.h"
 #include "ELFReader.h"
+#include "ELFResolver.h"
 #include "DynamicLibraryWriter.h"
 #include "ExecutableWriter.h"
 
 #include "lld/ReaderWriter/ELFLinkingContext.h"
 
 #include "llvm/ADT/Triple.h"
 #include "llvm/Support/ELF.h"
 
virtual std::unique_ptr<Reader> getObjReader(bool atomizeStrings) {
     return std::unique_ptr<Reader>(new ELFObjectReader(atomizeStrings));
   }
 
   virtual std::unique_ptr<Reader> getDSOReader(bool useShlibUndefines) {
     return std::unique_ptr<Reader>(new ELFDSOReader(useShlibUndefines));
   }
 
   virtual std::unique_ptr<Writer> getWriter() = 0;
+
+  virtual std::unique_ptr<Resolver> getResolver() {
+    return llvm::make_unique<ELFResolver<ELFT>>(this->_context);
+  }
 };
 
 } // end namespace elf
 } // end namespace lld
 #endif

lib/ReaderWriter/ELF/ELFLinkingContext.cpp

for (auto &i : getAbsoluteSymbols()) {
     StringRef sym = i.first;
     uint64_t val = i.second;
     file->addAtom(*(new (_allocator) CommandLineAbsoluteAtom(*file, sym, val)));
   }
   files.push_back(std::move(file));
   LinkingContext::createInternalFiles(files);
 }
 
+std::unique_ptr<Resolver> ELFLinkingContext::getResolver() {
+  return _targetHandler->getResolver();
+}
+
 std::unique_ptr<File> ELFLinkingContext::createUndefinedSymbolFile() const {
   if (_initialUndefinedSymbols.empty())
     return nullptr;
   std::unique_ptr<SimpleFile> undefinedSymFile(
       new SimpleFile("command line option -u"));
   for (auto undefSymStr : _initialUndefinedSymbols)
     undefinedSymFile->addAtom(*(new (_allocator) CommandLineUndefinedAtom(
         *undefinedSymFile, undefSymStr)));
   return std::move(undefinedSymFile);
 }
 
 } // end namespace lld

lib/ReaderWriter/ELF/ELFResolver.h

+//===- lib/ReaderWriter/ELF/Resolver.h - Resolves Atom References ---------===//
+//
+//                             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_RESOLVER_H
+#define LLD_READER_WRITER_ELF_RESOLVER_H
+
+#include "Atoms.h"
+
+#include "lld/Core/Resolver.h"
+
+namespace lld {
+namespace elf {
+
+template <class ELFT> class ELFResolver : public Resolver {
+public:
+  ELFResolver(LinkingContext &context) : Resolver(context) {}
+
+protected:
+  bool checkUndefines() override;
+};
+
+template <class ELFT>
+bool ELFResolver<ELFT>::checkUndefines() {
+  if (Resolver::checkUndefines())
+    return true;
+
+  for (const Atom *a : _atoms) {
+    auto *ua = dyn_cast<ELFUndefinedAtom<ELFT>>(a);
+    // Skip non-weak symbols.
+    if (!ua || ua->canBeNull() == UndefinedAtom::canBeNullNever)
+      continue;
+    // Skip weak symbols from non-shared libraries.
+    if (!isa<SharedLibraryFile>(ua->file()))
+      continue;
+    auto *da = dyn_cast<ELFDefinedAtom<ELFT>>(_symbolTable.replacement(ua));
+    if (!da)
+      continue;
+    // Request dynamic export for coalesced symbols replaced
+    // by strong defined atoms.
+    auto *r = this->makeReference<ELFReference<ELFT>>(Reference::kindDynExport);
+    r->setTarget(ua);
+    const_cast<ELFDefinedAtom<ELFT> *>(da)->addReference(r);
+  }
+
+  return false;
+}
+
+} // namespace elf
+} // namespace lld
+
+#endif // LLD_READER_WRITER_ELF_RESOLVER_H

lib/ReaderWriter/ELF/TargetHandler.h

public:
   virtual std::unique_ptr<Reader> getObjReader(bool) = 0;
 
   /// How does the target deal with reading dynamic libraries.
   virtual std::unique_ptr<Reader> getDSOReader(bool) = 0;
 
   /// How does the target deal with writing ELF output.
   virtual std::unique_ptr<Writer> getWriter() = 0;
 
-private:
+protected:
   ELFLinkingContext &_context;
 };
 } // end namespace elf
 } // end namespace lld
 
 #endif

lib/ReaderWriter/Reader.cpp

 }
 
 static const Registry::KindStrings kindStrings[] = {
     {Reference::kindInGroup, "in-group"},
     {Reference::kindLayoutAfter, "layout-after"},
     {Reference::kindLayoutBefore, "layout-before"},
     {Reference::kindGroupChild, "group-child"},
     {Reference::kindAssociate, "associate"},
+    {Reference::kindDynExport, "dyn-export"},
     LLD_KIND_STRING_END};
 
 Registry::Registry() {
   addKindTable(Reference::KindNamespace::all, Reference::KindArch::all,
                kindStrings);
 }
 
 bool Registry::handleTaggedDoc(llvm::yaml::IO &io,

test/elf/X86_64/dynsym-weak.test

+# Check that a symbol declared as a week in a shared library gets a dynamic
+# symbol table record in an executable file if this executabe file declares the
+# symbol as strong.
+
+# RUN: yaml2obj -format=elf -docnum 1 %s > %t.foo.o
+# RUN: lld -flavor gnu -target x86_64 -shared -o %t.so %t.foo.o
+# RUN: yaml2obj -format=elf -docnum 2 %s > %t.main.o
+#
+# Link executable file with strong symbol. Weak symbol is in the shared lib.
+# RUN: lld -flavor gnu -target x86_64 -e main -o %t.exe %t.main.o %t.so
+# RUN: llvm-readobj -dyn-symbols %t.exe | FileCheck -check-prefix=EXE %s
+#
+# Link executable file. Strong and weak symbol come from different object files.
+# RUN: lld -flavor gnu -target x86_64 -e main -o %t.exe %t.main.o %t.foo.o
+# RUN: llvm-readobj -dyn-symbols %t.exe | FileCheck -check-prefix=OBJ %s
+#
+# Link shared library. Weak symbol is in the another shared lib.
+# RUN: lld -flavor gnu -target x86_64 -shared -o %t.res.so %t.main.o %t.so
+# RUN: llvm-readobj -dyn-symbols %t.res.so | FileCheck -check-prefix=SO %s
+
+# EXE:      Symbol {
+# EXE:        Name: flag@ ({{[0-9]+}})
+# EXE-NEXT:   Value: 0x{{[0-9A-F]+}}
+# EXE-NEXT:   Size: 4
+# EXE-NEXT:   Binding: Global (0x1)
+# EXE-NEXT:   Type: Object (0x1)
+# EXE-NEXT:   Other: 0
+# EXE-NEXT:   Section: .data (0x{{[0-9A-F]+}})
+# EXE-NEXT: }
+
+# OBJ-NOT:  Name: flag@ ({{[0-9]+}})
+
+# SO:      Symbol {
+# SO:        Name: flag@ ({{[0-9]+}})
+# SO-NEXT:   Value: 0x{{[0-9A-F]+}}
+# SO-NEXT:   Size: 4
+# SO-NEXT:   Binding: Global (0x1)
+# SO-NEXT:   Type: Object (0x1)
+# SO-NEXT:   Other: 0
+# SO-NEXT:   Section: .data (0x{{[0-9A-F]+}})
+# SO-NEXT: }
+
+# foo.o
+---
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_X86_64
+
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    AddressAlign:    0x04
+    Size:            0x08
+  - Name:            .rela.text
+    Type:            SHT_RELA
+    Link:            .symtab
+    AddressAlign:    0x08
+    Info:            .text
+    Relocations:
+      - Offset:          0x00
+        Symbol:          flag
+        Type:            R_X86_64_GOTPCREL
+        Addend:          -4
+
+Symbols:
+  Global:
+    - Name:            foo
+      Type:            STT_FUNC
+      Section:         .text
+      Size:            0x08
+  Weak:
+    - Name:            flag
+
+# main.o
+---
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_X86_64
+
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    AddressAlign:    0x04
+    Size:            0x08
+  - Name:            .rela.text
+    Type:            SHT_RELA
+    Link:            .symtab
+    AddressAlign:    0x08
+    Info:            .text
+    Relocations:
+      - Offset:          0x00
+        Symbol:          foo
+        Type:            R_X86_64_PLT32
+        Addend:          -4
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x04
+    Size:            0x04
+
+Symbols:
+  Global:
+    - Name:            flag
+      Type:            STT_OBJECT
+      Section:         .data
+      Size:            0x04
+    - Name:            main
+      Type:            STT_FUNC
+      Section:         .text
+      Size:            0x08
+    - Name:            foo
+...