Index: clang-tools-extra/clangd/ClangdServer.h =================================================================== --- clang-tools-extra/clangd/ClangdServer.h +++ clang-tools-extra/clangd/ClangdServer.h @@ -98,10 +98,6 @@ /// If true, ClangdServer automatically indexes files in the current project /// on background threads. The index is stored in the project root. bool BackgroundIndex = false; - /// If set to non-zero, the background index rebuilds the symbol index - /// periodically every BuildIndexPeriodMs milliseconds; otherwise, the - /// symbol index will be updated for each indexed file. - size_t BackgroundIndexRebuildPeriodMs = 0; /// If set, use this index to augment code completion results. SymbolIndex *StaticIndex = nullptr; Index: clang-tools-extra/clangd/ClangdServer.cpp =================================================================== --- clang-tools-extra/clangd/ClangdServer.cpp +++ clang-tools-extra/clangd/ClangdServer.cpp @@ -128,8 +128,7 @@ if (Opts.BackgroundIndex) { BackgroundIdx = llvm::make_unique( Context::current().clone(), FSProvider, CDB, - BackgroundIndexStorage::createDiskBackedStorageFactory(), - Opts.BackgroundIndexRebuildPeriodMs); + BackgroundIndexStorage::createDiskBackedStorageFactory()); AddIndex(BackgroundIdx.get()); } if (DynamicIdx) Index: clang-tools-extra/clangd/index/Background.h =================================================================== --- clang-tools-extra/clangd/index/Background.h +++ clang-tools-extra/clangd/index/Background.h @@ -72,7 +72,6 @@ Context BackgroundContext, const FileSystemProvider &, const GlobalCompilationDatabase &CDB, BackgroundIndexStorage::Factory IndexStorageFactory, - size_t BuildIndexPeriodMs = 0, size_t ThreadPoolSize = llvm::heavyweight_hardware_concurrency()); ~BackgroundIndex(); // Blocks while the current task finishes. @@ -115,9 +114,6 @@ // index state llvm::Error index(tooling::CompileCommand, BackgroundIndexStorage *IndexStorage); - void buildIndex(); // Rebuild index periodically every BuildIndexPeriodMs. - const size_t BuildIndexPeriodMs; - std::atomic SymbolsUpdatedSinceLastIndex; std::mutex IndexMu; std::condition_variable IndexCV; @@ -142,6 +138,76 @@ loadShards(std::vector ChangedFiles); void enqueue(tooling::CompileCommand Cmd, BackgroundIndexStorage *Storage); + // The IndexRebuilder builds the serving data structures periodically in + // response to events in the background indexer. The goal is to ensure the + // served data stays fairly fresh, without wasting lots of CPU rebuilding it + // often. + // + // The index is always built after a set of shards are loaded from disk. + // This happens when clangd discovers a compilation database that we've + // previously built an index for. It's a fairly fast process that yields lots + // of data, so we wait to get all of it. + // + // The index is built after indexing 5 translation units, if it wasn't built + // already. This ensures quick startup if there's no existing index. + // Waiting for a few random TUs yields coverage of the most common headers. + // + // The index is rebuilt every 100 TUs, to keep if fresh as files are indexed. + // + // The index is rebuilt every time the queue goes idle, if it's stale. + // + // All methods are threadsafe. They're called after FileSymbols is updated + // etc. Without external locking, the rebuilt index may include more updates + // than intended, which is fine. + // + // This class is exposed in the header so it can be tested. + class IndexRebuilder { + public: + IndexRebuilder(SwapIndex *Target, FileSymbols *Source); + + // Called to indicate a TU has been indexed. + // May rebuild, if enough TUs have been indexed. + void indexedTU(); + // Called to indicate that all worker threads are idle. + // May reindex, if the index is not up to date. + void idle(); + // Called to indicate we're going to load a batch of shards from disk. + // startLoading() and doneLoading() must be paired, but multiple loading + // sessions may happen concurrently. + void startLoading(); + // Called to indicate some shards were actually loaded from disk. + void loadedTU(); + // Called to indicate we're finished loading shards from disk. + // May rebuild (if any were loaded). + void doneLoading(); + + // Ensures we won't start any more rebuilds. + void shutdown(); + + private: + // Run Check under the lock, and rebuild if it returns true. + void maybeRebuild(const char *Reason, std::function Check); + bool enoughTUsToRebuild() const; + + // All transient state is guarded by the mutex. + std::mutex Mu; + bool ShouldStop = false; + // Index builds are versioned. ActiveVersion chases StartedVersion. + unsigned StartedVersion = 0; + unsigned ActiveVersion = 0; + // How many TUs have we indexed so far since startup? + unsigned IndexedTUs = 0; + unsigned IndexedTUsAtLastRebuild = 0; + // Are we loading shards? May be multiple concurrent sessions. + unsigned Loading = 0; + unsigned LoadedTUs; // In the current loading session. + + SwapIndex *Target; + FileSymbols *Source; + }; + friend class IndexRebuilderTest; + IndexRebuilder Rebuilder; + // queue management using Task = std::function; void run(); // Main loop executed by Thread. Runs tasks from Queue. Index: clang-tools-extra/clangd/index/Background.cpp =================================================================== --- clang-tools-extra/clangd/index/Background.cpp +++ clang-tools-extra/clangd/index/Background.cpp @@ -17,6 +17,7 @@ #include "Threading.h" #include "Trace.h" #include "URI.h" +#include "index/FileIndex.h" #include "index/IndexAction.h" #include "index/MemIndex.h" #include "index/Ref.h" @@ -37,7 +38,9 @@ #include #include +#include #include +#include #include #include #include @@ -120,13 +123,11 @@ BackgroundIndex::BackgroundIndex( Context BackgroundContext, const FileSystemProvider &FSProvider, const GlobalCompilationDatabase &CDB, - BackgroundIndexStorage::Factory IndexStorageFactory, - size_t BuildIndexPeriodMs, size_t ThreadPoolSize) + BackgroundIndexStorage::Factory IndexStorageFactory, size_t ThreadPoolSize) : SwapIndex(llvm::make_unique()), FSProvider(FSProvider), CDB(CDB), BackgroundContext(std::move(BackgroundContext)), - BuildIndexPeriodMs(BuildIndexPeriodMs), - SymbolsUpdatedSinceLastIndex(false), IndexStorageFactory(std::move(IndexStorageFactory)), + Rebuilder(this, &IndexedSymbols), CommandsChanged( CDB.watch([&](const std::vector &ChangedFiles) { enqueue(ChangedFiles); @@ -137,11 +138,6 @@ ThreadPool.runAsync("background-worker-" + llvm::Twine(I + 1), [this] { run(); }); } - if (BuildIndexPeriodMs > 0) { - log("BackgroundIndex: build symbol index periodically every {0} ms.", - BuildIndexPeriodMs); - ThreadPool.runAsync("background-index-builder", [this] { buildIndex(); }); - } } BackgroundIndex::~BackgroundIndex() { @@ -150,6 +146,7 @@ } void BackgroundIndex::stop() { + Rebuilder.shutdown(); { std::lock_guard QueueLock(QueueMu); std::lock_guard IndexLock(IndexMu); @@ -185,6 +182,13 @@ { std::unique_lock Lock(QueueMu); + if (NumActiveTasks == 1 && Queue.empty()) + { + // We just finished the last item, the queue is going idle. + Lock.unlock(); + Rebuilder.idle(); + Lock.lock(); + } assert(NumActiveTasks > 0 && "before decrementing"); --NumActiveTasks; } @@ -379,32 +383,6 @@ } } -void BackgroundIndex::buildIndex() { - assert(BuildIndexPeriodMs > 0); - while (true) { - { - std::unique_lock Lock(IndexMu); - if (ShouldStop) // Avoid waiting if stopped. - break; - // Wait until this is notified to stop or `BuildIndexPeriodMs` has past. - IndexCV.wait_for(Lock, std::chrono::milliseconds(BuildIndexPeriodMs)); - if (ShouldStop) // Avoid rebuilding index if stopped. - break; - } - if (!SymbolsUpdatedSinceLastIndex.exchange(false)) - continue; - // There can be symbol update right after the flag is reset above and before - // index is rebuilt below. The new index would contain the updated symbols - // but the flag would still be true. This is fine as we would simply run an - // extra index build. - reset( - IndexedSymbols.buildIndex(IndexType::Heavy, DuplicateHandling::Merge)); - log("BackgroundIndex: rebuilt symbol index with estimated memory {0} " - "bytes.", - estimateMemoryUsage()); - } -} - llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd, BackgroundIndexStorage *IndexStorage) { trace::Span Tracer("BackgroundIndex"); @@ -503,12 +481,7 @@ update(AbsolutePath, std::move(Index), ShardVersionsSnapshot, IndexStorage, HadErrors); - if (BuildIndexPeriodMs > 0) - SymbolsUpdatedSinceLastIndex = true; - else - reset( - IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge)); - + Rebuilder.indexedTU(); return llvm::Error::success(); } @@ -628,6 +601,8 @@ std::move(RelS), SI.CountReferences); } } + if (!IntermediateSymbols.empty()) + Rebuilder.loadedTU(); return Dependencies; } @@ -644,6 +619,7 @@ // Keeps track of the loaded shards to make sure we don't perform redundant // disk IO. Keys are absolute paths. llvm::StringSet<> LoadedShards; + Rebuilder.startLoading(); for (const auto &File : ChangedFiles) { ProjectInfo PI; auto Cmd = CDB.getCompileCommand(File, &PI); @@ -667,11 +643,7 @@ break; } } - vlog("Loaded all shards"); - reset(IndexedSymbols.buildIndex(IndexType::Heavy, DuplicateHandling::Merge)); - vlog("BackgroundIndex: built symbol index with estimated memory {0} " - "bytes.", - estimateMemoryUsage()); + Rebuilder.doneLoading(); return NeedsReIndexing; } @@ -679,5 +651,98 @@ PreventStarvation.store(true); } +BackgroundIndex::IndexRebuilder::IndexRebuilder(SwapIndex *Target, + FileSymbols *Source) + : Target(Target), Source(Source) {} + +bool BackgroundIndex::IndexRebuilder::enoughTUsToRebuild() const { + static constexpr unsigned TUsBeforeFirstBuild = 5; + static constexpr unsigned TUsBeforeRebuild = 100; + if (!ActiveVersion) // never built + return IndexedTUs == TUsBeforeFirstBuild; // use low threshold + // rebuild if we've reached the (higher) threshold + return IndexedTUs >= IndexedTUsAtLastRebuild + TUsBeforeRebuild; +} + +void BackgroundIndex::IndexRebuilder::indexedTU() { + maybeRebuild("after indexing enough files", [this] { + ++IndexedTUs; + if (Loading) + return false; // rebuild once loading finishes + if (ActiveVersion != StartedVersion) // currently building + return false; // no urgency, avoid overlapping builds + return enoughTUsToRebuild(); + }); +} + +void BackgroundIndex::IndexRebuilder::idle() { + maybeRebuild("when background indexer is idle", [this] { + // rebuild if there's anything new in the index. + // (even if currently rebuilding! this ensures eventual completeness) + return IndexedTUs > IndexedTUsAtLastRebuild; + }); +} + +void BackgroundIndex::IndexRebuilder::startLoading() { + std::lock_guard Lock(Mu); + if (!Loading) + LoadedTUs = 0; + ++Loading; +} +void BackgroundIndex::IndexRebuilder::loadedTU() { + std::lock_guard Lock(Mu); + assert(Loading); + ++LoadedTUs; +} +void BackgroundIndex::IndexRebuilder::doneLoading() { + maybeRebuild("after loading index from disk", [this] { + assert(Loading); + --Loading; + if (Loading) // was loading multiple batches concurrently + return false; // rebuild once the last batch is done. + // Rebuild if we loaded any shards, or if we stopped an indexedTU rebuild. + return LoadedTUs > 0 || enoughTUsToRebuild(); + }); +} + +void BackgroundIndex::IndexRebuilder::shutdown() { + std::lock_guard Lock(Mu); + ShouldStop = true; +} + +void BackgroundIndex::IndexRebuilder::maybeRebuild( + const char *Reason, std::function Check) { + unsigned BuildVersion = 0; + { + std::lock_guard Lock(Mu); + if (!ShouldStop && Check()) + { + BuildVersion = ++StartedVersion; + IndexedTUsAtLastRebuild = IndexedTUs; + } + } + if (BuildVersion) + { + std::unique_ptr NewIndex; + { + vlog("BackgroundIndex: building version {0} {1}", BuildVersion, Reason); + trace::Span Tracer("RebuildBackgroundIndex"); + SPAN_ATTACH(Tracer, "reason", Reason); + NewIndex = Source->buildIndex(IndexType::Heavy, DuplicateHandling::Merge); + } + { + std::lock_guard Lock(Mu); + // Guard against rebuild finishing in the wrong order. + if (BuildVersion > ActiveVersion) + { + ActiveVersion = BuildVersion; + vlog("BackgroundIndex: serving version {0} ({2} bytes)", BuildVersion, + NewIndex->estimateMemoryUsage()); + Target->reset(std::move(NewIndex)); + } + } + } +} + } // namespace clangd } // namespace clang Index: clang-tools-extra/clangd/test/background-index.test =================================================================== --- clang-tools-extra/clangd/test/background-index.test +++ clang-tools-extra/clangd/test/background-index.test @@ -10,7 +10,7 @@ # We're editing bar.cpp, which includes foo.h. # foo() is declared in foo.h and defined in foo.cpp. # The background index should allow us to go-to-definition on foo(). -# RUN: clangd -background-index -background-index-rebuild-period=0 -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc +# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc # Test that the index is writing files in the expected location. # RUN: ls %t/.clangd/index/foo.cpp.*.idx Index: clang-tools-extra/clangd/tool/ClangdMain.cpp =================================================================== --- clang-tools-extra/clangd/tool/ClangdMain.cpp +++ clang-tools-extra/clangd/tool/ClangdMain.cpp @@ -191,14 +191,6 @@ "Experimental"), llvm::cl::init(true)); -static llvm::cl::opt BackgroundIndexRebuildPeriod( - "background-index-rebuild-period", - llvm::cl::desc( - "If set to non-zero, the background index rebuilds the symbol index " - "periodically every X milliseconds; otherwise, the " - "symbol index will be updated for each indexed file"), - llvm::cl::init(5000), llvm::cl::Hidden); - enum CompileArgsFrom { LSPCompileArgs, FilesystemCompileArgs }; static llvm::cl::opt CompileArgsFrom( "compile_args_from", llvm::cl::desc("The source of compile commands"), @@ -466,7 +458,6 @@ Opts.ResourceDir = ResourceDir; Opts.BuildDynamicSymbolIndex = EnableIndex; Opts.BackgroundIndex = EnableBackgroundIndex; - Opts.BackgroundIndexRebuildPeriodMs = BackgroundIndexRebuildPeriod; std::unique_ptr StaticIdx; std::future AsyncIndexLoad; // Block exit while loading the index. if (EnableIndex && !IndexFile.empty()) { Index: clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp =================================================================== --- clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp +++ clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp @@ -1,6 +1,7 @@ #include "Headers.h" #include "SyncAPI.h" #include "TestFS.h" +#include "TestIndex.h" #include "TestTU.h" #include "index/Background.h" #include "clang/Tooling/CompilationDatabase.h" @@ -294,42 +295,6 @@ EmptyIncludeNode()); } -// FIXME: figure out the right timeouts or rewrite to not use the timeouts and -// re-enable. -TEST_F(BackgroundIndexTest, DISABLED_PeriodicalIndex) { - MockFSProvider FS; - llvm::StringMap Storage; - size_t CacheHits = 0; - MemoryShardStorage MSS(Storage, CacheHits); - OverlayCDB CDB(/*Base=*/nullptr); - BackgroundIndex Idx( - Context::empty(), FS, CDB, [&](llvm::StringRef) { return &MSS; }, - /*BuildIndexPeriodMs=*/500); - - FS.Files[testPath("root/A.cc")] = "#include \"A.h\""; - - tooling::CompileCommand Cmd; - FS.Files[testPath("root/A.h")] = "class X {};"; - Cmd.Filename = testPath("root/A.cc"); - Cmd.CommandLine = {"clang++", Cmd.Filename}; - CDB.setCompileCommand(testPath("root/A.cc"), Cmd); - - ASSERT_TRUE(Idx.blockUntilIdleForTest()); - EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre()); - std::this_thread::sleep_for(std::chrono::milliseconds(1000)); - EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre(Named("X"))); - - FS.Files[testPath("root/A.h")] = "class Y {};"; - FS.Files[testPath("root/A.cc")] += " "; // Force reindex the file. - Cmd.CommandLine = {"clang++", "-DA=1", testPath("root/A.cc")}; - CDB.setCompileCommand(testPath("root/A.cc"), Cmd); - - ASSERT_TRUE(Idx.blockUntilIdleForTest()); - EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre(Named("X"))); - std::this_thread::sleep_for(std::chrono::milliseconds(1000)); - EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre(Named("Y"))); -} - TEST_F(BackgroundIndexTest, ShardStorageLoad) { MockFSProvider FS; FS.Files[testPath("root/A.h")] = R"cpp( @@ -605,5 +570,74 @@ } } +class IndexRebuilderTest : public testing::Test { +protected: + IndexRebuilderTest() + : Target(llvm::make_unique()), Rebuilder(&Target, &Source) { + // Prepare FileSymbols with TestSymbol in it, for checkRebuild. + TestSymbol.ID = SymbolID("foo"); + } + + // Perform Action and determine whether it rebuilt the index or not. + bool checkRebuild(std::function Action) { + // Update reference count so we can tell if the index updates. + ++TestSymbol.References; + SymbolSlab::Builder SB; + SB.insert(TestSymbol); + Source.update("", llvm::make_unique(std::move(SB).build()), + nullptr, nullptr, false); + // Now maybe update the index. + Action(); + // Now query the index to get the reference count. + unsigned ReadReferences = 0; + LookupRequest Req; + Req.IDs.insert(TestSymbol.ID); + Target.lookup(Req, [&](const Symbol &S) { ReadReferences = S.References; }); + // The index was rebuild if the reference count is up to date. + return ReadReferences == TestSymbol.References; + } + + Symbol TestSymbol; + FileSymbols Source; + SwapIndex Target; + BackgroundIndex::IndexRebuilder Rebuilder; +}; + +TEST_F(IndexRebuilderTest, IndexingTUs) { + for (int I = 0; I < 4; ++I) + EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); })); + EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); })); + for (int I = 0; I < 99; ++I) + EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); })); + EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); })); +} + +TEST_F(IndexRebuilderTest, LoadingShards) { + Rebuilder.startLoading(); + Rebuilder.loadedTU(); + Rebuilder.loadedTU(); + EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); })); + + // No rebuild for no shards. + Rebuilder.startLoading(); + EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); })); + + // Loads can overlap. + Rebuilder.startLoading(); + Rebuilder.loadedTU(); + Rebuilder.startLoading(); + Rebuilder.loadedTU(); + EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); })); + Rebuilder.loadedTU(); + EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); })); + + // No rebuilding for indexed files while loading. + Rebuilder.startLoading(); + for (int I = 0; I < 300; ++I) + EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); })); + // But they get indexed when we're done, even if no shards were loaded. + EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); })); +} + } // namespace clangd } // namespace clang