[clangd] Introduce background-indexer

[kadircet]

Summary

Sample output:
I[18:37:50.083] BackgroundIndex: build symbol index periodically every 86400000 ms.
I[18:37:50.115] Enqueueing 3742 commands for indexing
I[18:37:50.280] [0/3742] Loaded shards from storage
I[18:37:51.026] [1/3742] Indexed /usr/local/google/home/kadircet/repos/llvm/llvm/lib/Demangle/MicrosoftDemangleNodes.cpp (6422 symbols, 18236 refs, 161 files)
I[18:37:51.581] [2/3742] Indexed /usr/local/google/home/kadircet/repos/llvm/llvm/lib/Support/MD5.cpp (10204 symbols, 28897 refs, 232 files)
I[18:37:51.607] [3/3742] Indexed /usr/local/google/home/kadircet/repos/llvm/llvm/lib/MC/MCSchedule.cpp (11461 symbols, 32420 refs, 247 files)

[Eugene.Zelenko]

clang-tools-extra/clangd/background-indexer/BackgroundIndexer.cpp

14

Please use relative path. Same below.

[ilya-biryukov]

clang-tools-extra/clangd/background-indexer/BackgroundIndexer.cpp

14

Heh, where do these come from?
Does our include insertion prefer to add global paths in some cases? Dynamic index?

clang-tools-extra/clangd/index/Background.cpp

616

Everything else is vlog (or even dlog), what's the rationale of using log here?

clang-tools-extra/clangd/index/Background.h

149

Maybe use std::atomic instead?

[Eugene.Zelenko]

clang-tools-extra/clangd/index/Background.cpp

29

Unnecessary empty line.

[jkorous]

clang-tools-extra/clangd/background-indexer/BackgroundIndexer.cpp

57

Nit: maybe we should give this constant a name? Or maybe create a command line option for this?

61

Maybe we should add a comment about why we do this?

clang-tools-extra/clangd/index/Background.cpp

599

It's not obvious to me that we don't underflow here given we are using size_t. Maybe add an assert or some other sanity check?

clang-tools-extra/clangd/index/Background.h

149

+1 for atomic

[kadircet]

• Address comments

[kadircet]

clang-tools-extra/clangd/background-indexer/BackgroundIndexer.cpp

14

ah interesting, my guess is static index without any "-I" flags to direct path shortening.

57

It is the period for building index data structures which helps making queries fast, as I mentioned in the comment we definitely don't need this to happen until we've indexed every file, and BackgroundIndex should in my opinion work in this mode if period was set to zero. So I don't see any point in giving it a name.

Btw, the reason we want to build index data structures in the end is to just see how long it takes.

clang-tools-extra/clangd/index/Background.cpp

29

not introduced by this change

599

that line is executed at most once per each increment above, if you follow the flow you can see the break below, but good point moving it next to break to better illustrate that.

616

It was to print output mentioned in the summary. What would you rather suggest? Other possibilities I had in mind:

• Poll from client for current status
• Pass an option to background index to dump these logs conditionally

[ilya-biryukov]

I would propose to change the name of the tool.
The "background" part only makes sense in the context of running inside clangd, the index stored on disk is not "background" in any manner.
I'd go with something like build-clangd-index (the best option is probably clangd-indexer, but it's is already taken and we don't want to confuse the two tools).

Also not sure whether the BackgroundIndex is the right abstraction to use here. Conceptually, we want everything from the background index, except the "background" part and the fact that it listens to updates for compile commands (more stuff might get inconsistent in the future, e.g if we start watching for changes to headers, we would probably want to disable this functionality here). I.e. we went with BackgroundIndex for code reuse, not because it's the right abstraction for the job. I do think we could come up with something sensible.

That said, the right abstraction is not there now and it may take considerable refactoring to come up with one. And the tool seems to be useful regardless of the underlying implementation, not exactly sure what's the balance we should strike here (time spent vs useful results).

Kadir, what are your thoughts on that matter?

clang-tools-extra/clangd/background-indexer/BackgroundIndexer.cpp

29

That's not the accurate name or description, right?
We would actually walk up the directory tree as normal and discover any compilation database up the tree, right?

Maybe rename and document accordingly?

40

Why? Maybe add a comment?

47

I think that's actually a hard requirement.
We definitely want to run with normal priority when running as a separate tool.

56

Maybe use std::numeric_limits<size_t>::max() here?
Would mean we'll never build the dex index, exactly what we want here.

65

We seem to be fighting with the interface we defined here.
If we need to support an operation of re-building the index for the underlying CDB, let's add it explicitly.

68

We can't leave the function called like this, since we now seem to have a legitimate usage outside the test code.

Maybe rename it accordingly?

clang-tools-extra/clangd/index/Background.h

149

This change is not related to the rest of the patch.
Even adding some stats makes sense, could you move into a separate change to keep this change minimal?

[kadircet]

Looking at the current state of BackgroundIndex, it has the following implementation details:

• Loading of shards from storage
• Storing of shards to storage
• Collecting symbols from a TU
• Sharding of symbol information collected from one translation unit
• Performing all these tasks in a thread pool that can change scheduling priority of the thread depending on the task running.

Our requirements from the tool that currently is not possible through BackgroundIndex:

• Running tasks without lowering scheduling priority
• Blocking until all of the indexing actions finishes

I believe we can achive the first one by adding some options. The second one is already possible but it is using a test method we implemented for tests, as you mentioned we can just change the name.
Of course the above mentioned solutions would imply exposing that functionality to every user of BackgroundIndex.

I feel like it is better than exposing rest of the implementation details I mentioned in the first section(and also would be a lot faster to implement). WDYT?

clang-tools-extra/clangd/background-indexer/BackgroundIndexer.cpp

65

I should've rather performed this through enqueue, will change to use that.

[ilya-biryukov]

To reiterate the offline discussion: the tool seems useful to me, but it would be best to keep the client code simpler, it's currently fighting with BackgroundIndex because it's trying to hijack some of its functionality.
More specifically, I propose to add a function to BackgroundIndex.h that would be a one-shot update of the index, the client code would become significantly simpler and we would have more flexibility in how we move code around in BackgroundIndex.cpp to actually make this happen.

Adding @sammccall, who might also be interested in this.

[ilya-biryukov]

To make it clear, I think the question is not just "which part of functionality is missing in BackgroundIndex", it's rather "which part of BackgroundIndex we don't need".

[ilya-biryukov]

Leaving a summary of the offline discussion here.

@sammccall has pointed out maintaining and shipping more tools is work and we should probably avoid adding them upstream without careful design.
We ended up deciding to not land this particular upstream just yet, but anyone is free to patch this change on top of their LLVM repo in case they need something like this for debugging purposes.

Obviously no guarantees that this won't break.

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   )
 
 add_subdirectory(refactor/tweaks)
 if( LLVM_LIB_FUZZING_ENGINE OR LLVM_USE_SANITIZE_COVERAGE )
   add_subdirectory(fuzzer)
 endif()
 add_subdirectory(tool)
 add_subdirectory(indexer)
+add_subdirectory(background-indexer)
 add_subdirectory(index/dex/dexp)
 
 if (LLVM_INCLUDE_BENCHMARKS)
   add_subdirectory(benchmarks)
 endif()
 if ( CLANGD_BUILD_XPC )
   add_subdirectory(xpc)
 endif ()

clang-tools-extra/clangd/background-indexer/BackgroundIndexer.cpp

+//===--- BackgroundIndexer.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
+//
+//===----------------------------------------------------------------------===//
+//
+// A standalone binary to run clangd's background indexer.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Context.h"
+#include "FSProvider.h"
+#include "GlobalCompilationDatabase.h"
+#include "Logger.h"
+#include "index/Background.h"
+#include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/Signals.h"
+#include "llvm/Support/raw_ostream.h"
+#include <memory>
+
+static llvm::cl::opt<std::string> CompileCommandsDir(
+    llvm::cl::Positional,
+    llvm::cl::desc("Directory containing compilation database"),
+    llvm::cl::init("."));
+
+int main(int Argc, const char **Argv) {
+  llvm::sys::PrintStackTraceOnErrorSignal(Argv[0]);
+  llvm::cl::ParseCommandLineOptions(
+      Argc, Argv, "A standalone binary to run clangd's background indexer.");
+  clang::clangd::RealFileSystemProvider FSProvider;
+
+  llvm::errs().SetBuffered();
+  clang::clangd::StreamLogger Logger(llvm::errs(), clang::clangd::Logger::Info);
+  clang::clangd::LoggingSession LoggingSession(Logger);
+
+  clang::clangd::DirectoryBasedGlobalCompilationDatabase DirectoryBasedCDB(
+      /*CompileCommandsDir=*/llvm::None);
+  clang::clangd::OverlayCDB CDB(&DirectoryBasedCDB);
+  // FIXME: Maybe add a way to not lower thread priority?
+  clang::clangd::BackgroundIndex BackgroundIdx(
+      clang::clangd::Context::empty(), FSProvider, CDB,
+      clang::clangd::BackgroundIndexStorage::createDiskBackedStorageFactory(),
+      // We don't want to build dex/mem index until every file has been
+      // indexed/loaded.
+      // FIXME: Change BackgroundIndex to only built after all files have been
+      // read if build period is zero, which should only be used by
+      // non-interactive tools like this one.
+      24 * 60 * 60 * 1000);
+
+  // To trigger background indexing we need to discover a compilation database,
+  // which can be done by simply querying compile commands for a cpp file under
+  // the directory containing compilation_database.jon.
+  llvm::SmallString<128> DummyFile(CompileCommandsDir);
+  llvm::sys::fs::make_absolute(DummyFile);
+  llvm::sys::path::remove_dots(DummyFile, true);
+  llvm::sys::path::append(DummyFile, "dummy.cpp");
+  CDB.getCompileCommand(DummyFile);
+
+  // Wait untill indexing finishes.
+  BackgroundIdx.blockUntilIdleForTest(llvm::None);
+  return 0;
+}

clang-tools-extra/clangd/background-indexer/CMakeLists.txt

+include_directories(${CMAKE_CURRENT_SOURCE_DIR}/../)
+
+set(LLVM_LINK_COMPONENTS
+    Support
+    )
+
+add_clang_executable(clangd-background-indexer
+  BackgroundIndexer.cpp
+)
+
+target_link_libraries(clangd-background-indexer
+  PRIVATE
+  clangAST
+  clangIndex
+  clangDaemon
+  clangBasic
+  clangFrontend
+  clangLex
+  clangTooling
+)

clang-tools-extra/clangd/index/Background.h

void enqueueLocked(tooling::CompileCommand Cmd,
                      BackgroundIndexStorage *IndexStorage);
   std::mutex QueueMu;
   unsigned NumActiveTasks = 0; // Only idle when queue is empty *and* no tasks.
   std::condition_variable QueueCV;
   bool ShouldStop = false;
   std::deque<std::pair<Task, ThreadPriority>> Queue;
   std::vector<std::thread> ThreadPool; // FIXME: Abstract this away.
   GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
+
+  // For logging
+  std::atomic<size_t> EnqueuedTUs{0};
+  std::atomic<size_t> IndexedTUs{0};
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/index/Background.cpp

 #include "index/SymbolCollector.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/SHA1.h"
 
 #include <chrono>
 #include <memory>
+#include <mutex>
 #include <numeric>
 #include <queue>
 #include <random>
 #include <string>
 #include <thread>
 
 namespace clang {
 namespace clangd {

 
 void BackgroundIndex::enqueue(const std::vector<std::string> &ChangedFiles) {
   enqueueTask(
       [this, ChangedFiles] {
         trace::Span Tracer("BackgroundIndexEnqueue");
         // We're doing this asynchronously, because we'll read shards here too.
         log("Enqueueing {0} commands for indexing", ChangedFiles.size());
         SPAN_ATTACH(Tracer, "files", int64_t(ChangedFiles.size()));
+        EnqueuedTUs += ChangedFiles.size();
 
         auto NeedsReIndexing = loadShards(std::move(ChangedFiles));
         // Run indexing for files that need to be updated.
         std::shuffle(NeedsReIndexing.begin(), NeedsReIndexing.end(),
                      std::mt19937(std::random_device{}()));
         for (auto &Elem : NeedsReIndexing)
           enqueue(std::move(Elem.first), Elem.second);
       },
if (Clang->hasDiagnostics() &&
     return llvm::createStringError(
         llvm::inconvertibleErrorCode(),
         "IndexingAction failed: has uncompilable errors");
   }
 
   assert(Index.Symbols && Index.Refs && Index.Sources &&
          "Symbols, Refs and Sources must be set.");
 
-  log("Indexed {0} ({1} symbols, {2} refs, {3} files)",
-      Inputs.CompileCommand.Filename, Index.Symbols->size(),
+  ++IndexedTUs;
+  log("[{0}/{1}] Indexed {2} ({3} symbols, {4} refs, {5} files)", IndexedTUs,
+      EnqueuedTUs, Inputs.CompileCommand.Filename, Index.Symbols->size(),
       Index.Refs->numRefs(), Index.Sources->size());
   SPAN_ATTACH(Tracer, "symbols", int(Index.Symbols->size()));
   SPAN_ATTACH(Tracer, "refs", int(Index.Refs->numRefs()));
   SPAN_ATTACH(Tracer, "sources", int(Index.Sources->size()));
 
   update(AbsolutePath, std::move(Index), DigestsSnapshot, IndexStorage);
 
   if (BuildIndexPeriodMs > 0)
BackgroundIndex::loadShards(std::vector<std::string> ChangedFiles) {
   std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>>
       NeedsReIndexing;
   // Keeps track of the files that will be reindexed, to make sure we won't
   // re-index same dependencies more than once. Keys are AbsolutePaths.
   llvm::StringSet<> FilesToIndex;
   // Keeps track of the loaded shards to make sure we don't perform redundant
   // disk IO. Keys are absolute paths.
   llvm::StringSet<> LoadedShards;
+  size_t UpToDateTUs = 0;
   for (const auto &File : ChangedFiles) {
     ProjectInfo PI;
     auto Cmd = CDB.getCompileCommand(File, &PI);
     if (!Cmd)
       continue;
     BackgroundIndexStorage *IndexStorage = IndexStorageFactory(PI.SourceRoot);
+    ++UpToDateTUs;
     auto Dependencies = loadShard(*Cmd, IndexStorage, LoadedShards);
     for (const auto &Dependency : Dependencies) {
       if (!Dependency.NeedsReIndexing || FilesToIndex.count(Dependency.Path))
         continue;
       // FIXME: Currently, we simply schedule indexing on a TU whenever any of
       // its dependencies needs re-indexing. We might do it smarter by figuring
       // out a minimal set of TUs that will cover all the stale dependencies.
-      vlog("Enqueueing TU {0} because its dependency {1} needs re-indexing.",
+      dlog("Enqueueing TU {0} because its dependency {1} needs re-indexing.",
            Cmd->Filename, Dependency.Path);
       NeedsReIndexing.push_back({std::move(*Cmd), IndexStorage});
       // Mark all of this TU's dependencies as to-be-indexed so that we won't
       // try to re-index those.
       for (const auto &Dependency : Dependencies)
         FilesToIndex.insert(Dependency.Path);
+      --UpToDateTUs;
       break;
     }
   }
-  vlog("Loaded all shards");
+  IndexedTUs += UpToDateTUs;
+  log("[{0}/{1}] Loaded shards from storage", IndexedTUs, EnqueuedTUs);
   reset(IndexedSymbols.buildIndex(IndexType::Heavy, DuplicateHandling::Merge));
   vlog("BackgroundIndex: built symbol index with estimated memory {0} "
        "bytes.",
        estimateMemoryUsage());
   return NeedsReIndexing;
 }
 
 } // namespace clangd
 } // namespace clang