Speculatively instantiate archive members

[ruiu]

Summary

LLD parses archive file index table only at first. When it finds a symbol
it is looking for is defined in a member file in an archive file, it actually
reads the member from the archive file. That's done in the core linker.

That's a single-thread process since the core linker is single threaded.
If your command line contains a few object files and a lot of archive files
(which is quite often the case), LLD hardly utilizes hardware parallelism.

This patch improves parallelism by speculatively instantiating archive
file members. At the beginning of the core linking, we first create a map
containing all symbols defined in all members, and each time we find a
new undefined symbol, we instantiate a member file containing the
symbol (if such a file exists). File instantiation is side effect free, so this
should not affect correctness.

This is a quick benchmark. Time to link self-link LLD executable:

Linux 9.78s -> 8.50s (0.86x)
Windows 6.18s -> 4.51s (0.73x)

[atanasyan]

lib/ReaderWriter/FileArchive.cpp

102

It looks like we can remove the group from the capture list because it is not used in the lambda body.

274

Can we store promises directly and do not use unique_ptr wrapper? Though I did not test the following code, it compiled successfully. Does it have a sense?

// Instantiate the member
_promises.emplace_back();
auto &promise = _promises.back();
_preloaded[memberStart] = promise.get_future();
                                               
group.spawn([this, &promise, ci] {
  std::unique_ptr<File> result;
  if (instantiateMember(ci, result)) {
    promise.set_value(nullptr);
    return;
  }
  promise.set_value(result.release());
});

[...]

mutable std::vector<std::promise<const File *>> _promises;

[ruiu]

lib/ReaderWriter/FileArchive.cpp

102

Done.

274

I think promises created here need to be deleted when it's no longer needed. Your code wouldn't delete promises, no?

[atanasyan]

lib/ReaderWriter/FileArchive.cpp

274

They will be destroyed at the same time with the _promises container as any other types own destructor and stored in the std::vector.

[ruiu]

• Updated as per Simon's suggestion. Since object address is not guaranteed to be the same before group.spawn and inside group.spawn (because other thread may add more items to the vector, and vector contents are copied to extend), the code access the vector using index.

[shankarke]

lib/Core/Resolver.cpp

285

If there is more than one archive having the same symbol name, the last file with the same symbol would be parsed. The archive library file which appears in link order should be the first one to get picked.

Weak symbols and common symbols have the same name across different archives. This doesnot appear to handle the case where the right weak symbol need to be chosen or the right common symbol be chosen.

[shankarke]

Thanks for the explanation. LGTM.

[ruiu]

lib/ReaderWriter/FileArchive.cpp

274

I made a change as you suggested but eventually decided to roll it back because it didn't work on Windows. I don't fully understand why it sometimes raised an exception -- there might be a bug in std::future's move constructor? Anyways, the cost of referencing futures through unique_ptr should be negligible here.

[atanasyan]

Anyway it is a nice patch.

LGTM

[ruiu]

lib/ReaderWriter/FileArchive.cpp

274

I think I understand the reason. A future returned by promise::get_future() has a reference to the promise. When a vector is extended and all elements are moved, the original promise becomes invalid (whose valid() would return false.) When that happens, future::get() fails with an exception.

[denis-protivensky]

My in-place comment doesn't submit for some reason, so I put it here:

lib/ReaderWriter/FileArchive.cpp:105

_promises[index].set_value(nullptr);

Here is also a concurrency issue.

_promises[index] returns a reference to the promise object stored in the vector. If before making set_value() the vector's memory is moved because of reallocation in the other thread (new element inserted), the returned reference will again be invalid as it was in the previous version of the code when capturing promise by reference.

One of the solutions is to avoid vector reallocations. So we need either to reserve some sufficient element count beforehand, or to change vector to deque, for example.

lib/ReaderWriter/FileArchive.cpp

105

Here is also a concurrency issue.

_promises[index] returns a reference to the promise object stored in the vector. If before making set_value() the vector's memory is moved because of reallocation in the other thread (new element inserted), the returned reference will again be invalid as it was in the previous version of the code when capturing promise by reference.

One of the solutions is to avoid vector reallocations. So we need either to reserve some sufficient element count beforehand, or to change vector to deque, for example.

[ruiu]

Denis,

Thank you for reviewing! This code was submitted in r226336 and the final
code doesn't have the issues that you pointed out, I believe.

[denis-protivensky]

Rui,

Yeah, I see that you use locally constructed promise in r226336 and put it into the vector wrapped into unique_ptr. Good that you noticed that issue.

[Eugene.Zelenko]

Committed in r226336.

include/lld/Core/ArchiveLibraryFile.h

 #define LLD_CORE_ARCHIVE_LIBRARY_FILE_H
 
 #include "lld/Core/File.h"
+#include "lld/Core/Parallel.h"
 #include <set>
 
 namespace lld {

   virtual std::error_code
   parseAllMembers(std::vector<std::unique_ptr<File>> &result) = 0;
 
+  // Parses a member file containing a given symbol, so that when you
+  // need the file find() can return that immediately. Calling this function
+  // has no side effect other than pre-instantiating a file. Calling this
+  // function doesn't affect correctness.
+  virtual void preload(TaskGroup &group, StringRef symbolName) {}
+
   /// Returns a set of all defined symbols in the archive, i.e. all
   /// resolvable symbol using this file.
-  virtual std::set<StringRef> getDefinedSymbols() const {
+  virtual std::set<StringRef> getDefinedSymbols() {
     return std::set<StringRef>();
   }
 

include/lld/Core/File.h

 
   std::error_code parse();
 
+  // This function is called just before the core linker tries to use
+  // a file. Currently the PECOFF reader uses this to trigger the
+  // driver to parse .drectve section (which contains command line options).
+  // If you want to do something having side effects, don't do that in
+  // doParse() because a file could be pre-loaded speculatively.
+  // Use this hook instead.
+  virtual void beforeLink() {}
+
   // Usually each file owns a std::unique_ptr<MemoryBuffer>.
   // However, there's one special case. If a file is an archive file,
   // the archive file and its children all shares the same memory buffer.

include/lld/Core/Resolver.h

 #ifndef LLD_CORE_RESOLVER_H
 #define LLD_CORE_RESOLVER_H
 
+#include "lld/Core/ArchiveLibraryFile.h"
 #include "lld/Core/File.h"
 #include "lld/Core/SharedLibraryFile.h"
 #include "lld/Core/SymbolTable.h"

   void maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom);
 
   /// \brief The main function that iterates over the files to resolve
+  void makePreloadArchiveMap();
   bool resolveUndefines();
   void updateReferences();
   void deadStripOptimize();

 
   void markLive(const Atom *atom);
   void addAtoms(const std::vector<const DefinedAtom *>&);
+  void maybePreloadArchiveMember(StringRef sym);
 
   class MergedFile : public MutableFile {
   public:

   std::vector<File *> _files;
   std::map<File *, bool> _newUndefinesAdded;
   size_t _fileIndex;
+
+  // Preloading
+  std::map<StringRef, ArchiveLibraryFile *> _archiveMap;
 };
 
 } // namespace lld

lib/Core/Resolver.cpp

   bool undefAdded = false;
   for (const DefinedAtom *atom : file.defined())
     doDefinedAtom(*atom);
-  for (const UndefinedAtom *atom : file.undefined())
-    if (doUndefinedAtom(*atom))
+  for (const UndefinedAtom *atom : file.undefined()) {
+    if (doUndefinedAtom(*atom)) {
       undefAdded = true;
+      maybePreloadArchiveMember(atom->name());
+    }
+  }
   for (const SharedLibraryAtom *atom : file.sharedLibrary())
     doSharedLibraryAtom(*atom);
   for (const AbsoluteAtom *atom : file.absolute())

     doDefinedAtom(*newAtom);
 }
 
+// Instantiate an archive file member if there's a file containing a
+// defined symbol for a given symbol name. Instantiation is done in a
+// different worker thread and has no visible side effect.
+void Resolver::maybePreloadArchiveMember(StringRef sym) {
+  auto it = _archiveMap.find(sym);
+  if (it == _archiveMap.end())
+    return;
+  ArchiveLibraryFile *archive = it->second;
+  archive->preload(_context.getTaskGroup(), sym);
+}
+
 // Returns true if at least one of N previous files has created an
 // undefined symbol.
 bool Resolver::undefinesAdded(int begin, int end) {

   return cast<FileNode>(inputs[index++].get())->getFile();
 }
 
+// Make a map of Symbol -> ArchiveFile.
+void Resolver::makePreloadArchiveMap() {
+  std::vector<std::unique_ptr<Node>> &nodes = _context.getNodes();
+  for (auto it = nodes.rbegin(), e = nodes.rend(); it != e; ++it)
+    if (auto *fnode = dyn_cast<FileNode>(it->get()))
+      if (auto *archive = dyn_cast<ArchiveLibraryFile>(fnode->getFile()))
+        for (StringRef sym : archive->getDefinedSymbols())
+          _archiveMap[sym] = archive;
+}
+
 // Keep adding atoms until _context.getNextFile() returns an error. This
 // function is where undefined atoms are resolved.
 bool Resolver::resolveUndefines() {

                    << ": " << ec.message() << "\n";
       return false;
     }
+    file->beforeLink();
     switch (file->kind()) {
     case File::kindObject:
       if (groupLevel > 0)

 }
 
 bool Resolver::resolve() {
+  makePreloadArchiveMap();
   if (!resolveUndefines())
     return false;
   updateReferences();

lib/ReaderWriter/FileArchive.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/MemoryBuffer.h"
+#include <future>
 #include <memory>
+#include <mutex>
 #include <set>
 #include <unordered_map>
 

       return nullptr;
 
     _membersInstantiated.insert(memberStart);
+
+    // Check if a file is preloaded.
+    {
+      std::lock_guard<std::mutex> lock(_mutex);
+      auto it = _preloaded.find(memberStart);
+      if (it != _preloaded.end()) {
+        std::future<const File *> &future = it->second;
+        return future.get();
+      }
+    }
+
     std::unique_ptr<File> result;
     if (instantiateMember(ci, result))
       return nullptr;

     return result.release();
   }
 
+  // Instantiate a member file containing a given symbol name.
+  void preload(TaskGroup &group, StringRef name) override {
+    auto member = _symbolMemberMap.find(name);
+    if (member == _symbolMemberMap.end())
+      return;
+    Archive::child_iterator ci = member->second;
+
+    // Do nothing if a member is already instantiated.
+    const char *memberStart = ci->getBuffer().data();
+    if (_membersInstantiated.count(memberStart))
+      return;
+
+    std::lock_guard<std::mutex> lock(_mutex);
+    if (_preloaded.find(memberStart) != _preloaded.end())
+      return;
+
+    // Instantiate the member
+    int index = _promises.size();
+    _promises.emplace_back();
+    _preloaded[memberStart] = _promises[index].get_future();
+
+    group.spawn([=] {
+      std::unique_ptr<File> result;
+      if (instantiateMember(ci, result)) {
+        _promises[index].set_value(nullptr);
+        return;
+      }
+      _promises[index].set_value(result.release());
+    });
+  }
+
   /// \brief parse each member
   std::error_code
   parseAllMembers(std::vector<std::unique_ptr<File>> &result) override {

   }
 
   /// Returns a set of all defined symbols in the archive.
-  std::set<StringRef> getDefinedSymbols() const override {
+  std::set<StringRef> getDefinedSymbols() override {
+    parse();
     std::set<StringRef> ret;
     for (const auto &e : _symbolMemberMap)
       ret.insert(e.first);

   atom_collection_vector<AbsoluteAtom> _absoluteAtoms;
   bool _logLoading;
   mutable std::vector<std::unique_ptr<MemoryBuffer>> _memberBuffers;
+  mutable std::map<const char *, std::future<const File *>> _preloaded;
+  mutable std::vector<std::promise<const File *>> _promises;
+  mutable std::mutex _mutex;
 };
 
 class ArchiveReader : public Reader {

lib/ReaderWriter/PECOFF/ReaderCOFF.cpp

     return _absoluteAtoms;
   }
 
+  void beforeLink() override;
+
   void addDefinedAtom(AliasAtom *atom) {
     atom->setOrdinal(_ordinal++);
     _definedAtoms._atoms.push_back(atom);

   // The mapping for /alternatename is in the context object. This helper
   // function iterate over defined atoms and create alias atoms if needed.
   createAlternateNameAtoms();
+  return std::error_code();
+}
 
+void FileCOFF::beforeLink() {
   // Acquire the mutex to mutate _ctx.
   std::lock_guard<std::recursive_mutex> lock(_ctx.getMutex());
 

     _ctx.setSafeSEH(false);
 
   if (_ctx.deadStrip())
-    for (StringRef sym : undefinedSymbols)
-      _ctx.addDeadStripRoot(sym);
-
-  return std::error_code();
+    for (const UndefinedAtom *undef : undefined())
+      _ctx.addDeadStripRoot(undef->name());
 }
 
 /// Iterate over the symbol table to retrieve all symbols.