[clangd] Move DirBasedCDB broadcasting onto its own thread.

[sammccall]

Summary

This is on the critical path (it blocks getting the compile command for
the first file).

It's not trivially fast: it involves processing all filenames in the CDB
and doing some IO to look for shadowing CDBs.

And we may make this slower soon - making CDB configurable implies evaluating
the config for each listed to see which ones really are owned by the
broadcasted CDB.

[kadircet]

clang-tools-extra/clangd/GlobalCompilationDatabase.cpp

496

nit: we already hold the lock within the loop while reading. it is nice that we no longer need to acquire the lock during destructor, but is it worth the extra mental load that comes with memory orderings? (also IIRC, default load/store behaviors are already acquire-release)

541

don't we need some context propagation here? previously broadcasting was running with the context of the astworker that discovered the cdb. i suppose it is not needed at the moment, as most of the stuff we do in ::process isn't context-aware, but I can't be sure if we don't have any users that make use of some context-aware FS.

[sammccall]

address comments

clang-tools-extra/clangd/GlobalCompilationDatabase.cpp

496

Whoops, I split this patch in half and now this makes no sense.

The point is rather that we should interrupt the "evaluate the config for every file" loop (which will be part of process()) if ShouldStop is set. So we check this atomic inside that loop, without acquiring the lock.

(In practice maybe this is always "fast enough" that we should just run the whole loop, enqueue all the background indexing stuff, and then shut down afterwards?)

(also IIRC, default load/store behaviors are already acquire-release)

Default is sequentially consistent, which is almost always more than we need.

---

I've added a check to the existing loop (which probes directory caches), less necessary but shows the idea. If you prefer to drop this entirely that's OK too.

[kadircet]

thanks, lgtm!

clang-tools-extra/clangd/GlobalCompilationDatabase.cpp

496

The point is rather that we should interrupt the "evaluate the config for every file" loop (which will be part of process()) if ShouldStop is set. So we check this atomic inside that loop, without acquiring the lock.

ah okay now it makes sense.

I've added a check to the existing loop (which probes directory caches), less necessary but shows the idea. If you prefer to drop this entirely that's OK too.

i suppose we could end up blocking the shutdown for quite some time in pathological cases due to disk io. so this looks like a good tradeoff.

clang-tools-extra/clangd/GlobalCompilationDatabase.h

public:
 
   DirectoryBasedGlobalCompilationDatabase(const Options &Opts);
   ~DirectoryBasedGlobalCompilationDatabase() override;
 
   /// Scans File's parents looking for compilation databases.
   /// Any extra flags will be added.
   /// Might trigger OnCommandChanged, if CDB wasn't broadcasted yet.
   llvm::Optional<tooling::CompileCommand>
   getCompileCommand(PathRef File) const override;
 
   /// Returns the path to first directory containing a compilation database in
   /// \p File's parents.
   llvm::Optional<ProjectInfo> getProjectInfo(PathRef File) const override;
 
+  bool blockUntilIdle(Deadline Timeout) const override;
+
 private:
   Options Opts;
 
   class DirectoryCache;
   // If there's an explicit CompileCommandsDir, cache of the CDB found there.
   mutable std::unique_ptr<DirectoryCache> OnlyDirCache;
 
   // Keyed by possibly-case-folded directory path.
struct CDBLookupRequest {
     std::chrono::steady_clock::time_point FreshTimeMissing;
   };
   struct CDBLookupResult {
     std::shared_ptr<const tooling::CompilationDatabase> CDB;
     ProjectInfo PI;
   };
   llvm::Optional<CDBLookupResult> lookupCDB(CDBLookupRequest Request) const;
 
+  class BroadcastThread;
+  std::unique_ptr<BroadcastThread> Broadcaster;
+
   // Performs broadcast on governed files.
   void broadcastCDB(CDBLookupResult Res) const;
 
   // cache test calls lookupCDB directly to ensure valid/invalid times.
   friend class DirectoryBasedGlobalCompilationDatabaseCacheTest;
 };
 
 /// Extracts system include search path from drivers matching QueryDriverGlobs

clang-tools-extra/clangd/GlobalCompilationDatabase.cpp

 //===--- GlobalCompilationDatabase.cpp ---------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "GlobalCompilationDatabase.h"
 #include "FS.h"
 #include "SourceCode.h"
 #include "support/Logger.h"
 #include "support/Path.h"
+#include "support/Threading.h"
 #include "support/ThreadsafeFS.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Tooling/ArgumentsAdjusters.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/CompilationDatabasePluginRegistry.h"
 #include "clang/Tooling/JSONCompilationDatabase.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/FileUtilities.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/VirtualFileSystem.h"
+#include <atomic>
 #include <chrono>
+#include <condition_variable>
 #include <string>
 #include <tuple>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
for (const auto &Entry :
     // Don't log Error here, it's usually just "couldn't find <file>".
   }
   vlog("No compilation database at {0}", Path);
   return true;
 }
 
 DirectoryBasedGlobalCompilationDatabase::
     DirectoryBasedGlobalCompilationDatabase(const Options &Opts)
-    : Opts(Opts) {
+    : Opts(Opts), Broadcaster(std::make_unique<BroadcastThread>(*this)) {
   if (Opts.CompileCommandsDir)
     OnlyDirCache = std::make_unique<DirectoryCache>(*Opts.CompileCommandsDir);
 }
 
 DirectoryBasedGlobalCompilationDatabase::
     ~DirectoryBasedGlobalCompilationDatabase() = default;
 
 llvm::Optional<tooling::CompileCommand>
DirectoryBasedGlobalCompilationDatabase::lookupCDB(
 
   if (!CDB)
     return llvm::None;
 
   CDBLookupResult Result;
   Result.CDB = std::move(CDB);
   Result.PI.SourceRoot = DirCache->Path;
 
-  // FIXME: Maybe make the following part async, since this can block
-  // retrieval of compile commands.
   if (ShouldBroadcast)
     broadcastCDB(Result);
   return Result;
 }
 
-void DirectoryBasedGlobalCompilationDatabase::broadcastCDB(
-    CDBLookupResult Result) const {
-  vlog("Broadcasting compilation database from {0}", Result.PI.SourceRoot);
-  assert(Result.CDB && "Trying to broadcast an invalid CDB!");
+// The broadcast thread announces files with new compile commands to the world.
+// Primarily this is used to enqueue them for background indexing.
+//
+// It's on a separate thread because:
+//  - otherwise it would block the first parse of the initial file
+//  - we need to enumerate all files in the CDB, of which there are many
+//  - we (will) have to evaluate config for every file in the CDB, which is slow
+class DirectoryBasedGlobalCompilationDatabase::BroadcastThread {
+  class Filter;
+  DirectoryBasedGlobalCompilationDatabase &Parent;
+
+  std::mutex Mu;
+  std::condition_variable CV;
+  std::atomic<bool> ShouldStop = {false}; // Must notify CV after writing.
+  struct Task {
+    CDBLookupResult Lookup;
+    Context Ctx;
+  };
+  std::deque<Task> Queue;
+  llvm::Optional<Task> ActiveTask;
+  std::thread Thread; // Must be last member.
+
+  // Thread body: this is just the basic queue procesing boilerplate.
+  void run() {
+    std::unique_lock<std::mutex> Lock(Mu);
+    while (true) {
+      bool Stopping = false;
+      CV.wait(Lock, [&] {
+        return (Stopping = ShouldStop.load(std::memory_order_acquire)) ||
+               !Queue.empty();
+      });
+      if (Stopping) {
+        Queue.clear();
+        CV.notify_all();
+        return;
+      }
+      ActiveTask = std::move(Queue.front());
+      Queue.pop_front();
+
+      Lock.unlock();
+      {
+        WithContext WithCtx(std::move(ActiveTask->Ctx));
+        process(ActiveTask->Lookup);
+      }
+      Lock.lock();
+      ActiveTask.reset();
+      CV.notify_all();
+    }
+  }
+
+  // Inspects a new CDB and broadcasts the files it owns.
+  void process(const CDBLookupResult &T);
+
+public:
+  BroadcastThread(DirectoryBasedGlobalCompilationDatabase &Parent)
+      : Parent(Parent), Thread([this] { run(); }) {}
+
+  void enqueue(CDBLookupResult Lookup) {
+    {
+      assert(!Lookup.PI.SourceRoot.empty());
+      std::lock_guard<std::mutex> Lock(Mu);
+      // New CDB takes precedence over any queued one for the same directory.
+      llvm::erase_if(Queue, [&](const Task &T) {
+        return T.Lookup.PI.SourceRoot == Lookup.PI.SourceRoot;
+      });
+      Queue.push_back({std::move(Lookup), Context::current().clone()});
+    }
+    CV.notify_all();
+  }
+
+  bool blockUntilIdle(Deadline Timeout) {
+    std::unique_lock<std::mutex> Lock(Mu);
+    return wait(Lock, CV, Timeout,
+                [&] { return Queue.empty() && !ActiveTask.hasValue(); });
+  }
+
+  ~BroadcastThread() {
+    ShouldStop.store(true, std::memory_order_release);
+    CV.notify_all();
+    Thread.join();
+  }
+};
+
+void DirectoryBasedGlobalCompilationDatabase::BroadcastThread::process(
+    const CDBLookupResult &T) {
+  vlog("Broadcasting compilation database from {0}", T.PI.SourceRoot);
 
-  std::vector<std::string> AllFiles = Result.CDB->getAllFiles();
+  std::vector<std::string> AllFiles = T.CDB->getAllFiles();
   // We assume CDB in CompileCommandsDir owns all of its entries, since we don't
   // perform any search in parent paths whenever it is set.
-  if (OnlyDirCache) {
-    assert(OnlyDirCache->Path == Result.PI.SourceRoot &&
+  if (Parent.OnlyDirCache) {
+    assert(Parent.OnlyDirCache->Path == T.PI.SourceRoot &&
            "Trying to broadcast a CDB outside of CompileCommandsDir!");
-    OnCommandChanged.broadcast(std::move(AllFiles));
+    Parent.OnCommandChanged.broadcast(std::move(AllFiles));
     return;
   }
 
   // Uniquify all parent directories of all files.
   llvm::StringMap<bool> DirectoryHasCDB;
   std::vector<llvm::StringRef> FileAncestors;
   for (llvm::StringRef File : AllFiles) {
     actOnAllParentDirectories(File, [&](PathRef Path) {
       auto It = DirectoryHasCDB.try_emplace(Path);
       // Already seen this path, and all of its parents.
       if (!It.second)
         return true;
 
       FileAncestors.push_back(It.first->getKey());
-      return pathEqual(Path, Result.PI.SourceRoot);
+      return pathEqual(Path, T.PI.SourceRoot);
     });
   }
   // Work out which ones have CDBs in them.
   // Given that we know that CDBs have been moved/generated, don't trust caches.
   // (This should be rare, so it's OK to add a little latency).
   constexpr auto IgnoreCache = std::chrono::steady_clock::time_point::max();
-  auto DirectoryCaches = getDirectoryCaches(FileAncestors);
+  auto DirectoryCaches = Parent.getDirectoryCaches(FileAncestors);
   assert(DirectoryCaches.size() == FileAncestors.size());
   for (unsigned I = 0; I < DirectoryCaches.size(); ++I) {
     bool ShouldBroadcast = false;
-    if (DirectoryCaches[I]->get(Opts.TFS, ShouldBroadcast,
+    if (ShouldStop.load(std::memory_order_acquire)) {
+      log("Giving up on broadcasting CDB, as we're shutting down");
+      return;
+    }
+    if (DirectoryCaches[I]->get(Parent.Opts.TFS, ShouldBroadcast,
                                 /*FreshTime=*/IgnoreCache,
                                 /*FreshTimeMissing=*/IgnoreCache))
       DirectoryHasCDB.find(FileAncestors[I])->setValue(true);
   }
 
   std::vector<std::string> GovernedFiles;
   for (llvm::StringRef File : AllFiles) {
     // A file is governed by this CDB if lookup for the file would find it.
     // Independent of whether it has an entry for that file or not.
     actOnAllParentDirectories(File, [&](PathRef Path) {
       if (DirectoryHasCDB.lookup(Path)) {
-        if (pathEqual(Path, Result.PI.SourceRoot))
+        if (pathEqual(Path, T.PI.SourceRoot))
           // Make sure listeners always get a canonical path for the file.
           GovernedFiles.push_back(removeDots(File));
         // Stop as soon as we hit a CDB.
         return true;
       }
       return false;
     });
   }
 
-  OnCommandChanged.broadcast(std::move(GovernedFiles));
+  Parent.OnCommandChanged.broadcast(std::move(GovernedFiles));
+}
+
+void DirectoryBasedGlobalCompilationDatabase::broadcastCDB(
+    CDBLookupResult Result) const {
+  assert(Result.CDB && "Trying to broadcast an invalid CDB!");
+  Broadcaster->enqueue(Result);
+}
+
+bool DirectoryBasedGlobalCompilationDatabase::blockUntilIdle(
+    Deadline Timeout) const {
+  return Broadcaster->blockUntilIdle(Timeout);
 }
 
 llvm::Optional<ProjectInfo>
 DirectoryBasedGlobalCompilationDatabase::getProjectInfo(PathRef File) const {
   CDBLookupRequest Req;
   Req.FileName = File;
   Req.ShouldBroadcast = false;
   Req.FreshTime = Req.FreshTimeMissing =

clang-tools-extra/clangd/unittests/GlobalCompilationDatabaseTests.cpp

// happens in practice though.
     DirectoryBasedGlobalCompilationDatabase DB(FS);
     std::vector<std::string> DiscoveredFiles;
     auto Sub =
         DB.watch([&DiscoveredFiles](const std::vector<std::string> Changes) {
           DiscoveredFiles = Changes;
         });
 
     DB.getCompileCommand(testPath("build/../a.cc"));
+    ASSERT_TRUE(DB.blockUntilIdle(timeoutSeconds(10)));
     EXPECT_THAT(DiscoveredFiles, UnorderedElementsAre(AllOf(
                                      EndsWith("a.cc"), Not(HasSubstr("..")))));
     DiscoveredFiles.clear();
 
     DB.getCompileCommand(testPath("build/gen.cc"));
+    ASSERT_TRUE(DB.blockUntilIdle(timeoutSeconds(10)));
     EXPECT_THAT(DiscoveredFiles, UnorderedElementsAre(EndsWith("gen.cc")));
   }
 
   // With a custom compile commands dir.
   {
     DirectoryBasedGlobalCompilationDatabase::Options Opts(FS);
     Opts.CompileCommandsDir = testRoot();
     DirectoryBasedGlobalCompilationDatabase DB(Opts);
     std::vector<std::string> DiscoveredFiles;
     auto Sub =
         DB.watch([&DiscoveredFiles](const std::vector<std::string> Changes) {
           DiscoveredFiles = Changes;
         });
 
     DB.getCompileCommand(testPath("a.cc"));
+    ASSERT_TRUE(DB.blockUntilIdle(timeoutSeconds(10)));
     EXPECT_THAT(DiscoveredFiles,
                 UnorderedElementsAre(EndsWith("a.cc"), EndsWith("gen.cc"),
                                      EndsWith("gen2.cc")));
     DiscoveredFiles.clear();
 
     DB.getCompileCommand(testPath("build/gen.cc"));
+    ASSERT_TRUE(DB.blockUntilIdle(timeoutSeconds(10)));
     EXPECT_THAT(DiscoveredFiles, IsEmpty());
   }
 }
 
 TEST(GlobalCompilationDatabaseTest, BuildDir) {
   MockFS FS;
   auto Command = [&](llvm::StringRef Relative) {
     DirectoryBasedGlobalCompilationDatabase::Options Opts(FS);