Fix regression introduced in r205566.

[ruiu]

Summary

In r205566, I made a change to Resolver so that Resolver revisit
only archive files in --start-group and --end-group pair. That's
not correct, as it also has to revisit DSO files.

This patch is to fix the issue. I once tried to just revisit DSO
files in a group, but it made Resolver to fall in an infinite loop.
I needed to fix the bug that Resolver loops over a group even if
no undefined symbols are newly created in the group.

Added a test to demonstrate the fix. I confirmed that it succeeded
before r205566, failed after r205566, and is ok with this patch.

[atanasyan]

LGTM with some minor notes.

include/lld/Driver/GnuLdInputGraph.h

81 ↗

(On Diff #9329)

This phrase only if the node is an archive library does not correspond to the current code. Now we reset the next file index for shared libraries too.

lib/Core/Resolver.cpp

65 ↗

(On Diff #9329)

It is not good to always print undefAdded: ... in debug mode. Let's remove this debug output or surround it by the DEBUG_WITH_TYPE macros.

182 ↗

(On Diff #9329)

The comment Returns true is inconsistent. The Resolver::doDefinedAtom() method has void return type.

[shankarke]

lib/Core/Resolver.cpp

66–68 ↗

(On Diff #9329)

it looks like notifyProgress is called only if there is a undefined atom added, can we do it in doUndefinedAtom ? This way there would be no need to change much.

[atanasyan]

It looks like there is a bug in this patch. The lld linker hangs when build a.out executable in the following test case.

% cat main.c
int foo();

int main() {
  return foo();
}

% cat foo.c
int bar();

int foo() {
  return bar();
}

% cat bar.c
void func();

int bar() {
  return 0;
}

int bar1() {
  func();
  return 0;
}

% gcc -c main.c foo.c
% gcc -c -fPIC bar.c
% lld -flavor gnu -target x86_64 -shared --noinhibit-exec -o libbar.so bar.o
% lld -flavor gnu -target x86_64 -e main -o a.out main.o --start-group libbar.so foo.o --end-group

Probably because each time we scan libbar.so we find the undefined symbol func and call the notifyProgress() and go to the next scan.

[ruiu]

• fix the infinite loop bug that Simon pointed out

[ruiu]

The infinite loop bug was not caused by the notifyProgress call, but because we accidentally created a loop in _replacedAtoms. When the undefined atom "func" is added to the symbol table second time, it's replacement atom (in _replacedAtoms in SymbolTable.cpp) is set to itself. It's easily fixable. PTAL.

[ruiu]

lib/Core/Resolver.cpp

66–68 ↗

(On Diff #9329)

I don't want to call notifyProgress in doUndefinedAtom. If we do, notifyProgress() would be called for each undefined atom. That's not wrong but would be slow. I want call it only once.

[atanasyan]

LGTM

[ruiu]

Closed by commit rL208797 (authored by @ruiu).

lld/trunk/include/lld/Core/Resolver.h

 /// and producing a merged graph.
 class Resolver {
 public:
   Resolver(LinkingContext &context)
       : _context(context), _symbolTable(context), _result(new MergedFile()) {}
 
   // InputFiles::Handler methods
   void doDefinedAtom(const DefinedAtom&);
-  void doUndefinedAtom(const UndefinedAtom&);
+  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.

lld/trunk/include/lld/Core/SymbolTable.h

 /// All atoms coalescable by-name or by-content should be added.
 /// The method replacement() can be used to find the replacement atom
 /// if an atom has been coalesced away.
 class SymbolTable {
 public:
   explicit SymbolTable(const LinkingContext &);
 
   /// @brief add atom to symbol table
-  void add(const DefinedAtom &);
+  bool add(const DefinedAtom &);
 
   /// @brief add atom to symbol table
-  void add(const UndefinedAtom &);
+  bool add(const UndefinedAtom &);
 
   /// @brief add atom to symbol table
-  void add(const SharedLibraryAtom &);
+  bool add(const SharedLibraryAtom &);
 
   /// @brief add atom to symbol table
-  void add(const AbsoluteAtom &);
+  bool add(const AbsoluteAtom &);
 
   /// @brief checks if name is in symbol table and if so atom is not
   ///        UndefinedAtom
   bool isDefined(StringRef sym);
 
   /// @brief returns atom in symbol table for specified name (or nullptr)
   const Atom *findByName(StringRef sym);
 
struct AtomMappingInfo {
     static const DefinedAtom * getEmptyKey() { return nullptr; }
     static const DefinedAtom * getTombstoneKey() { return (DefinedAtom*)(-1); }
     static unsigned getHashValue(const DefinedAtom * const Val);
     static bool isEqual(const DefinedAtom * const LHS,
                         const DefinedAtom * const RHS);
   };
   typedef llvm::DenseSet<const DefinedAtom*, AtomMappingInfo> AtomContentSet;
 
-  void addByName(const Atom &);
-  void addByContent(const DefinedAtom &);
+  bool addByName(const Atom &);
+  bool addByContent(const DefinedAtom &);
 
   const LinkingContext &_context;
   AtomToAtom _replacedAtoms;
   NameToAtom _nameTable;
   NameToAtom _groupTable;
   AtomContentSet _contentTable;
 };
 
 } // namespace lld
 
 #endif // LLD_CORE_SYMBOL_TABLE_H

lld/trunk/include/lld/Driver/GnuLdInputGraph.h

public:
   error_code parse(const LinkingContext &, raw_ostream &) override;
 
   /// \brief This is used by Group Nodes, when there is a need to reset the
   /// the file to be processed next. When handling a group node that contains
   /// Input elements, if the group node has to be reprocessed, the linker needs
   /// to start processing files as part of the input element from beginning.
   /// Reset the next file index to 0 only if the node is an archive library.
   void resetNextIndex() override {
-    if (_files[0]->kind() == File::kindArchiveLibrary &&
-        !_attributes._isWholeArchive) {
+    auto kind = _files[0]->kind();
+    if (kind == File::kindSharedLibrary ||
+        (kind == File::kindArchiveLibrary && !_attributes._isWholeArchive)) {
       _nextFileIndex = 0;
     }
   }
 
   /// \brief Return the file that has to be processed by the resolver
   /// to resolve atoms. This iterates over all the files thats part
   /// of this node. Returns no_more_files when there are no files to be
   /// processed

lld/trunk/lib/Core/Resolver.cpp

 
 private:
   SymbolTable &_symbolTable;
 };
 
 } // namespace
 
 void Resolver::handleFile(const File &file) {
-  bool isEmpty = file.defined().empty() && file.undefined().empty() &&
-                 file.sharedLibrary().empty() && file.absolute().empty();
-  if (isEmpty)
-    return;
-
+  bool undefAdded = false;
   for (const DefinedAtom *atom : file.defined())
     doDefinedAtom(*atom);
   for (const UndefinedAtom *atom : file.undefined())
-    doUndefinedAtom(*atom);
+    if (doUndefinedAtom(*atom))
+      undefAdded = true;
   for (const SharedLibraryAtom *atom : file.sharedLibrary())
     doSharedLibraryAtom(*atom);
   for (const AbsoluteAtom *atom : file.absolute())
     doAbsoluteAtom(*atom);
 
   // Notify the input file manager of the fact that we have made some progress
   // on linking using the current input file. It may want to know the fact for
   // --start-group/--end-group.
+  if (undefAdded) {
     _context.getInputGraph().notifyProgress();
   }
+}
 
 void Resolver::forEachUndefines(bool searchForOverrides,
                                 UndefCallback callback) {
   // Handle normal archives
   unsigned undefineGenCount = 0;
   do {
     undefineGenCount = _symbolTable.size();
     for (const UndefinedAtom *undefAtom : _symbolTable.undefines()) {
void Resolver::handleSharedLibrary(const File &file) {
   forEachUndefines(searchForOverrides,
                    [&](StringRef undefName, bool dataSymbolOnly) {
     if (const SharedLibraryAtom *atom =
             sharedLibrary->exports(undefName, dataSymbolOnly))
       doSharedLibraryAtom(*atom);
   });
 }
 
-void Resolver::doUndefinedAtom(const UndefinedAtom &atom) {
+bool Resolver::doUndefinedAtom(const UndefinedAtom &atom) {
   DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                     << "       UndefinedAtom: "
                     << llvm::format("0x%09lX", &atom)
                     << ", name=" << atom.name() << "\n");
 
   // add to list of known atoms
   _atoms.push_back(&atom);
 
   // tell symbol table
-  _symbolTable.add(atom);
+  bool newUndefAdded = _symbolTable.add(atom);
 
   // If the undefined symbol has an alternative name, try to resolve the
   // symbol with the name to give it a second chance. This feature is used
   // for COFF "weak external" symbol.
   if (!_symbolTable.isDefined(atom.name())) {
     if (const UndefinedAtom *fallbackAtom = atom.fallback()) {
       doUndefinedAtom(*fallbackAtom);
       _symbolTable.addReplacement(&atom, fallbackAtom);
     }
   }
+  return newUndefAdded;
 }
 
 /// \brief Add the section group and the group-child reference members.
 bool Resolver::maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom) {
   // First time adding a group?
   bool isFirstTime = _symbolTable.addGroup(atom);
 
   if (!isFirstTime) {
if ((r->kindNamespace() == lld::Reference::KindNamespace::all) &&
                        "be associated with Defined Atoms only");
       _atoms.push_back(target);
       _symbolTable.add(*target);
     }
   }
   return true;
 }
 
-// called on each atom when a file is added
+// Called on each atom when a file is added. Returns true if a given
+// atom is added to the symbol table.
 void Resolver::doDefinedAtom(const DefinedAtom &atom) {
   DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                     << "         DefinedAtom: "
                     << llvm::format("0x%09lX", &atom)
                     << ", file=#"
                     << atom.file().ordinal()
                     << ", atom=#"
                     << atom.ordinal()

lld/trunk/lib/Core/SymbolTable.cpp

 #include <algorithm>
 #include <cassert>
 #include <cstdlib>
 #include <vector>
 
 namespace lld {
 SymbolTable::SymbolTable(const LinkingContext &context) : _context(context) {}
 
-void SymbolTable::add(const UndefinedAtom &atom) { addByName(atom); }
+bool SymbolTable::add(const UndefinedAtom &atom) { return addByName(atom); }
 
-void SymbolTable::add(const SharedLibraryAtom &atom) { addByName(atom); }
+bool SymbolTable::add(const SharedLibraryAtom &atom) { return addByName(atom); }
 
-void SymbolTable::add(const AbsoluteAtom &atom) { addByName(atom); }
+bool SymbolTable::add(const AbsoluteAtom &atom) { return addByName(atom); }
 
-void SymbolTable::add(const DefinedAtom &atom) {
+bool SymbolTable::add(const DefinedAtom &atom) {
   if (!atom.name().empty() &&
       atom.scope() != DefinedAtom::scopeTranslationUnit) {
     // Named atoms cannot be merged by content.
     assert(atom.merge() != DefinedAtom::mergeByContent);
     // Track named atoms that are not scoped to file (static).
-    addByName(atom);
-    return;
+    return addByName(atom);
   }
   if (atom.merge() == DefinedAtom::mergeByContent) {
     // Named atoms cannot be merged by content.
     assert(atom.name().empty());
-    addByContent(atom);
+    return addByContent(atom);
   }
+  return false;
 }
 
 const Atom *SymbolTable::findGroup(StringRef sym) {
   NameToAtom::iterator pos = _groupTable.find(sym);
   if (pos == _groupTable.end())
     return nullptr;
   return pos->second;
 }

 // section are connected by layout-before and layout-after edges, so this
 // function traverses them to get the total size of atoms in the same section.
 static uint64_t sectionSize(const DefinedAtom *atom) {
   return atom->size()
       + getSizeFollowReferences(atom, lld::Reference::kindLayoutBefore)
       + getSizeFollowReferences(atom, lld::Reference::kindLayoutAfter);
 }
 
-void SymbolTable::addByName(const Atom &newAtom) {
+bool SymbolTable::addByName(const Atom &newAtom) {
   StringRef name = newAtom.name();
   assert(!name.empty());
   const Atom *existing = findByName(name);
   if (existing == nullptr) {
     // Name is not in symbol table yet, add it associate with this atom.
     _nameTable[name] = &newAtom;
-    return;
+    return true;
   }
 
+  // Do nothing if the same object is added more than once.
+  if (existing == &newAtom)
+    return false;
+
   // Name is already in symbol table and associated with another atom.
   bool useNew = true;
   switch (collide(existing->definition(), newAtom.definition())) {
   case NCR_First:
     useNew = false;
     break;
   case NCR_Second:
     useNew = true;
if (useNew) {
     // Update name table to use new atom.
     _nameTable[name] = &newAtom;
     // Add existing atom to replacement table.
     _replacedAtoms[existing] = &newAtom;
   } else {
     // New atom is not being used.  Add it to replacement table.
     _replacedAtoms[&newAtom] = existing;
   }
+  return false;
 }
 
 unsigned SymbolTable::AtomMappingInfo::getHashValue(const DefinedAtom *atom) {
   auto content = atom->rawContent();
   return llvm::hash_combine(atom->size(),
                             atom->contentType(),
                             llvm::hash_combine_range(content.begin(),
                                                      content.end()));
if (l->contentType() != r->contentType())
     return false;
   if (l->size() != r->size())
     return false;
   ArrayRef<uint8_t> lc = l->rawContent();
   ArrayRef<uint8_t> rc = r->rawContent();
   return memcmp(lc.data(), rc.data(), lc.size()) == 0;
 }
 
-void SymbolTable::addByContent(const DefinedAtom & newAtom) {
+bool SymbolTable::addByContent(const DefinedAtom &newAtom) {
   // Currently only read-only constants can be merged.
   assert(newAtom.permissions() == DefinedAtom::permR__);
   AtomContentSet::iterator pos = _contentTable.find(&newAtom);
   if (pos == _contentTable.end()) {
     _contentTable.insert(&newAtom);
-    return;
+    return true;
   }
   const Atom* existing = *pos;
   // New atom is not being used.  Add it to replacement table.
   _replacedAtoms[&newAtom] = existing;
+  return false;
 }
 
 const Atom *SymbolTable::findByName(StringRef sym) {
   NameToAtom::iterator pos = _nameTable.find(sym);
   if (pos == _nameTable.end())
     return nullptr;
   return pos->second;
 }

lld/trunk/test/elf/X86_64/Inputs/group/group.sh

 int fn1() {
 fn2();
 }
 !
 
 gcc -c 1.c fn.c fn2.c fn1.c
 ar cr libfn.a fn.o fn2.o
 ar cr libfn1.a fn1.o
+lld -flavor gnu -target x86_64 -shared -o libfn2.so fn2.o
 lld -flavor gnu -target x86_64 1.o libfn.a libfn1.a -o x
 lld -flavor gnu -target x86_64 1.o --start-group libfn.a libfn1.a --end-group -o x
 lld -flavor gnu -target x86_64 1.o --start-group fn.o fn2.o fn1.o --end-group -o x
 lld -flavor gnu -target x86_64 1.o --start-group --whole-archive libfn.a --no-whole-archive libfn1.a --end-group -o x

lld/trunk/test/elf/X86_64/startGroupEndGroup.test

 RUN:   %p/Inputs/group/fn.o %p/Inputs/group/fn2.o \
 RUN:   %p/Inputs/group/fn1.o --end-group -o %t2
 
 # Mix Whole archive input, the group should not iterate the file libfn.a
 RUN: lld -flavor gnu -target x86_64 %p/Inputs/group/1.o --start-group \
 RUN:   --whole-archive %p/Inputs/group/libfn.a --no-whole-archive \
 RUN:   %p/Inputs/group/libfn1.a --end-group -o %t3
 
+# Defined symbols in a shared library.
+RUN: lld -flavor gnu -target x86_64 %p/Inputs/group/1.o --start-group \
+RUN:   %p/Inputs/group/libfn2.so %p/Inputs/group/fn1.o %p/Inputs/group/fn.o \
+RUN:   --end-group -o %t4
+
 # Test alias options too, as they are more widely used
 # Test group
 RUN: lld -flavor gnu -target x86_64 %p/Inputs/group/1.o '-(' \
 RUN:   %p/Inputs/group/libfn.a %p/Inputs/group/libfn1.a '-)' -o %t1.alias
 
 # Mix object files in group
 RUN: lld -flavor gnu -target x86_64 %p/Inputs/group/1.o '-(' \
 RUN:   %p/Inputs/group/fn.o %p/Inputs/group/fn2.o \