LLD: Implement our own future and use that for FileArchive::preload().

[ruiu]

Summary

std::promise and std::future in old version of libstdc++ are buggy.
I think that's the reason why LLD tests were flaky on Ubuntu 13
buildbots until we disabled file preloading.

In this patch, I implemented very simple future and used that in
FileArchive. Compared to std::promise and std::future, it lacks
many features, but should suffice for our purpose.

[chandlerc]

Is there a reason not to implement essentially the exact future/promise API from the standard in the 'llvm' namespace? We do this in ADT or Support for a lot of things that we'd like from the standard library but can't rely on (yet).

Maybe it makes more sense to start smaller here, but then I wonder if it would be useful to make the APIs at least be a subset to ease migration in the future? (ba-dum!)

Not a big deal either way, just a thought.

[ruiu]

The reason why I didn't implement complete future and promise as specified in C++11 is because the amount of effort that would require. I implemented a future just in 30 lines here. On the other hand a complete implementation probably require 200+ lines. This is the only place we use future, so I thought that it just doesn't pay.

If we are going to use future in many places in LLVM projects, it worth implementing a "real" one. But I imagine it's unlikely -- the linker is probably exceptional in the sense that it gains a lot from multi-threading. If we are going to see more uses of future in LLVM, maybe we should think about that.

[ruiu]

Oh, and speaking of the API, I don't actually understand why C++11 separates producer side (std::promise) and consumer side (std::future). My implementation is not compatible with that at all -- I just defined std::future and use that for both, just like future in java.util.concurrent. Seems working fine -- so I didn't go so far as to define one more class.

[shankarke]

include/lld/Core/Parallel.h

77

there is only one usage of Future with lld::File, Why do we want to make this a template ?

lib/ReaderWriter/FileArchive.cpp

63–69

The _preloaded map could get resized here ? Can we resize the map in advance since we know how many members are in the archive ?

261–262

looks like/most of the members are mutable, I think this needs to be made non-const.

269

llvm::DenseMap ?

[• shankar.easwaran]

lgtm

[Eugene.Zelenko]

Committed in r231153.

include/lld/Core/Parallel.h

public:
   void sync() const {
     std::unique_lock<std::mutex> lock(_condMut);
     _cond.wait(lock, [&] {
       return _count == 0;
     });
   }
 };
 
+/// \brief An implementation of future. std:future and std::promise in
+/// libstdc++ had a threading bug; there is a small chance that a call
+/// of future::get throws an exception in the normal use case. We want
+/// to use our own future implementation until we drop support of old
+/// version of libstdc++.
+/// https://gcc.gnu.org/ml/gcc-patches/2014-05/msg01389.html
+template<typename T> class Future {
+public:
+  Future() : _hasValue(false) {}
+
+  void set(T &&val) {
+    assert(!_hasValue);
+    {
+      std::unique_lock<std::mutex> lock(_mutex);
+      _val = val;
+      _hasValue = true;
+    }
+    _cond.notify_all();
+  }
+
+  T &get() {
+    std::unique_lock<std::mutex> lock(_mutex);
+    if (_hasValue)
+      return _val;
+    _cond.wait(lock, [&] { return _hasValue; });
+    return _val;
+  }
+
+private:
+  T _val;
+  bool _hasValue;
+  std::mutex _mutex;
+  std::condition_variable _cond;
+};
+
 /// \brief An abstract class that takes closures and runs them asynchronously.
 class Executor {
 public:
   virtual ~Executor() {}
   virtual void add(std::function<void()> func) = 0;
 };
 
 /// \brief An implementation of an Executor that runs closures on a thread pool

lib/Core/Resolver.cpp

 #include <vector>
 
 namespace lld {
 
 bool Resolver::handleFile(const File &file) {
   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())
     doAbsoluteAtom(*atom);
   return undefAdded;
 }
 
 void Resolver::forEachUndefines(bool searchForOverrides,

 }
 
 // utility to add a vector of atoms
 void Resolver::addAtoms(const std::vector<const DefinedAtom *> &newAtoms) {
   for (const DefinedAtom *newAtom : newAtoms)
     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(_ctx.getTaskGroup(), sym);
+}
+
 // Returns true if at least one of N previous files has created an
 // undefined symbol.
 bool Resolver::undefinesAdded(int begin, int end) {
   std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
   for (int i = begin; i < end; ++i)
     if (FileNode *node = dyn_cast<FileNode>(inputs[i].get()))
       if (_newUndefinesAdded[node->getFile()])
         return true;

lib/ReaderWriter/FileArchive.cpp

 //===- lib/ReaderWriter/FileArchive.cpp -----------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lld/Core/ArchiveLibraryFile.h"
 #include "lld/Core/LLVM.h"
 #include "lld/Core/LinkingContext.h"
+#include "lld/Core/Parallel.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/ObjectFile.h"
 #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>
 
 using llvm::object::Archive;
 using llvm::object::ObjectFile;
 using llvm::object::SymbolRef;
if (_membersInstantiated.count(memberStart))
       return nullptr;
     if (dataSymbolOnly && !isDataSymbol(ci, name))
       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<Future<const File *>> &p = it->second;
+        Future<const File *> *future = p.get();
+        return future->get();
       }
     }
 
     std::unique_ptr<File> result;
     if (instantiateMember(ci, result))
       return nullptr;
 
     // give up the pointer so that this object no longer manages it
     return result.release();
void preload(TaskGroup &group, StringRef name) override {
     if (_membersInstantiated.count(memberStart))
       return;
 
     std::lock_guard<std::mutex> lock(_mutex);
     if (_preloaded.find(memberStart) != _preloaded.end())
       return;
 
     // Instantiate the member
-    auto *promise = new std::promise<const File *>;
-    _preloaded[memberStart] = promise->get_future();
-    _promises.push_back(std::unique_ptr<std::promise<const File *>>(promise));
+    auto *future = new Future<const File *>();
+    _preloaded[memberStart] = std::unique_ptr<Future<const File *>>(future);
 
     group.spawn([=] {
       std::unique_ptr<File> result;
-      if (instantiateMember(ci, result)) {
-        promise->set_value(nullptr);
-        return;
-      }
-      promise->set_value(result.release());
+      std::error_code ec = instantiateMember(ci, result);
+      future->set(ec ? nullptr : result.release());
     });
   }
 
   /// \brief parse each member
   std::error_code
   parseAllMembers(std::vector<std::unique_ptr<File>> &result) override {
     if (std::error_code ec = parse())
       return ec;

 
 private:
   typedef std::unordered_map<StringRef, Archive::child_iterator> MemberMap;
   typedef std::set<const char *> InstantiatedSet;
 
   std::shared_ptr<MemoryBuffer> _mb;
   const Registry &_registry;
   std::unique_ptr<Archive> _archive;
   mutable MemberMap _symbolMemberMap;
   mutable InstantiatedSet _membersInstantiated;
   atom_collection_vector<DefinedAtom> _definedAtoms;
   atom_collection_vector<UndefinedAtom> _undefinedAtoms;
   atom_collection_vector<SharedLibraryAtom> _sharedLibraryAtoms;
   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::unique_ptr<std::promise<const File *>>> _promises;
+  mutable std::map<const char *, std::unique_ptr<Future<const File *>>> _preloaded;
   mutable std::mutex _mutex;
 };
 
 class ArchiveReader : public Reader {
 public:
   ArchiveReader(bool logLoading) : _logLoading(logLoading) {}
 
   bool canParse(file_magic magic, StringRef,