diff --git a/clang-tools-extra/clangd/ClangdServer.h b/clang-tools-extra/clangd/ClangdServer.h --- a/clang-tools-extra/clangd/ClangdServer.h +++ b/clang-tools-extra/clangd/ClangdServer.h @@ -126,6 +126,10 @@ /// If false, respect the value in clang. bool PreserveRecoveryASTType = false; + // The number of preambles that will be retained even after the file is + // closed + size_t KeepPreambles = 0; + /// Clangd's workspace root. Relevant for "workspace" operations not bound /// to a particular file. /// FIXME: If not set, should use the current working directory. diff --git a/clang-tools-extra/clangd/ClangdServer.cpp b/clang-tools-extra/clangd/ClangdServer.cpp --- a/clang-tools-extra/clangd/ClangdServer.cpp +++ b/clang-tools-extra/clangd/ClangdServer.cpp @@ -123,6 +123,7 @@ Opts.AsyncThreadsCount = 4; // Consistent! Opts.TheiaSemanticHighlighting = true; Opts.AsyncPreambleBuilds = true; + Opts.KeepPreambles = 0; return Opts; } @@ -133,6 +134,7 @@ Opts.StorePreamblesInMemory = StorePreamblesInMemory; Opts.UpdateDebounce = UpdateDebounce; Opts.AsyncPreambleBuilds = AsyncPreambleBuilds; + Opts.KeepPreambles = KeepPreambles; return Opts; } diff --git a/clang-tools-extra/clangd/TUScheduler.h b/clang-tools-extra/clangd/TUScheduler.h --- a/clang-tools-extra/clangd/TUScheduler.h +++ b/clang-tools-extra/clangd/TUScheduler.h @@ -197,6 +197,10 @@ /// No-op if AsyncThreadsCount is 0. bool AsyncPreambleBuilds = true; + // The number of preambles that will be retained even after the file is + // closed + size_t KeepPreambles = 0; + /// Used to create a context that wraps each single operation. /// Typically to inject per-file configuration. /// If the path is empty, context sholud be "generic". @@ -305,6 +309,9 @@ /// an LRU cache. class ASTCache; + /// Responsible for retaining preambles. + class PreambleCache; + // The file being built/processed in the current thread. This is a hack in // order to get the file name into the index implementations. Do not depend on // this inside clangd. @@ -321,6 +328,7 @@ std::unique_ptr Callbacks; // not nullptr Semaphore Barrier; llvm::StringMap> Files; + std::unique_ptr CachedPreambles; std::unique_ptr IdleASTs; // None when running tasks synchronously and non-None when running tasks // asynchronously. diff --git a/clang-tools-extra/clangd/TUScheduler.cpp b/clang-tools-extra/clangd/TUScheduler.cpp --- a/clang-tools-extra/clangd/TUScheduler.cpp +++ b/clang-tools-extra/clangd/TUScheduler.cpp @@ -179,6 +179,91 @@ std::vector LRU; /* GUARDED_BY(Mut) */ }; +/// LRU cache with amortized O(1) put and take +/// Preambles can be stored on disk so we may want to store a high +/// number of entries +class TUScheduler::PreambleCache { +public: + PreambleCache(size_t MaxSize, bool StorePreamblesInMemory) + : MaxSize(MaxSize), StorePreamblesInMemory(StorePreamblesInMemory) { + vlog("TUScheduler will cache {0} preambles", MaxSize); + } + + /// Get the preamble associated with a \p Key, removing + /// it from the cache + std::shared_ptr take(llvm::StringRef Key) { + auto It = Data.find(Key); + if (It == Data.end()) + return nullptr; + auto Result = std::move(It->second); + + // Remove the key from all internal data structures + auto KeyToLRUIt = KeyToLRU.find(Key); + assert(KeyToLRUIt != KeyToLRU.end() && "Key is missing"); + auto LRUIt = KeyToLRUIt->second; + Data.erase(It); + KeyToLRU.erase(KeyToLRUIt); + LRU.erase(LRUIt); + + return Result; + } + + /// Add a \p Preamble associated with a \p Key, the preamble must + /// not be in the cache when this function is called + void put(llvm::StringRef Key, std::shared_ptr Preamble) { + assert(KeyToLRU.find(Key) == KeyToLRU.end()); + if (MaxSize == 0) + return; + + LRU.emplace_front(Key.str()); + // Use the newly created string as the storage + Key = LRU.front(); + + Data[Key] = std::move(Preamble); + KeyToLRU[Key] = LRU.begin(); + vlog("Added {0} to preamble cache", Key); + + // Trim the LRU to the max size + while (LRU.size() > MaxSize) { + const auto &OldestKey = LRU.back(); + KeyToLRU.erase(OldestKey); + Data.erase(OldestKey); + vlog("Removed {0} from preamble cache", OldestKey); + LRU.pop_back(); + } + } + + void profile(MemoryTree &MT) const { + auto &ContainersMT = MT.child("containers"); + ContainersMT.addUsage(LRU.size() * sizeof(void *) * 2); + ContainersMT.addUsage(KeyToLRU.getMemorySize()); + ContainersMT.addUsage(Data.getMemorySize()); + + if (!StorePreamblesInMemory) + return; + + auto &PreamblesMT = MT.child("preambles"); + for (const auto &Entry : Data) { + auto &EntryMT = PreamblesMT.detail(Entry.first).child("cached_preamble"); + EntryMT.child("key").addUsage(Entry.first.size()); + EntryMT.child("preamble").addUsage(Entry.second->Preamble.getSize()); + } + } + +private: + using LRUType = std::list; + + // LRU holds the keys, most recent first + // The maps below use references as keys, they reference + // string in this LRU list + LRUType LRU; + llvm::DenseMap KeyToLRU; + llvm::DenseMap> Data; + + size_t MaxSize; + bool StorePreamblesInMemory; +}; + namespace { /// Threadsafe manager for updating a TUStatus and emitting it after each /// update. @@ -221,10 +306,11 @@ public: PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks, bool StorePreambleInMemory, bool RunSync, - SynchronizedTUStatus &Status, ASTWorker &AW) - : FileName(FileName), Callbacks(Callbacks), - StoreInMemory(StorePreambleInMemory), RunSync(RunSync), Status(Status), - ASTPeer(AW) {} + SynchronizedTUStatus &Status, ASTWorker &AW, + std::shared_ptr InitialPreamble) + : LatestBuild(std::move(InitialPreamble)), FileName(FileName), + Callbacks(Callbacks), StoreInMemory(StorePreambleInMemory), + RunSync(RunSync), Status(Status), ASTPeer(AW) {} /// It isn't guaranteed that each requested version will be built. If there /// are multiple update requests while building a preamble, only the last one @@ -369,7 +455,8 @@ friend class ASTWorkerHandle; ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB, TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, bool RunSync, - const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks); + const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks, + std::shared_ptr InitialPreamble); public: /// Create a new ASTWorker and return a handle to it. @@ -377,12 +464,12 @@ /// is null, all requests will be processed on the calling thread /// synchronously instead. \p Barrier is acquired when processing each /// request, it is used to limit the number of actively running threads. - static ASTWorkerHandle create(PathRef FileName, - const GlobalCompilationDatabase &CDB, - TUScheduler::ASTCache &IdleASTs, - AsyncTaskRunner *Tasks, Semaphore &Barrier, - const TUScheduler::Options &Opts, - ParsingCallbacks &Callbacks); + static ASTWorkerHandle + create(PathRef FileName, const GlobalCompilationDatabase &CDB, + TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks, + Semaphore &Barrier, const TUScheduler::Options &Opts, + ParsingCallbacks &Callbacks, + std::shared_ptr InitialPreamble); ~ASTWorker(); void update(ParseInputs Inputs, WantDiagnostics, bool ContentChanged); @@ -566,14 +653,15 @@ std::shared_ptr Worker; }; -ASTWorkerHandle ASTWorker::create(PathRef FileName, - const GlobalCompilationDatabase &CDB, - TUScheduler::ASTCache &IdleASTs, - AsyncTaskRunner *Tasks, Semaphore &Barrier, - const TUScheduler::Options &Opts, - ParsingCallbacks &Callbacks) { - std::shared_ptr Worker(new ASTWorker( - FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks, Opts, Callbacks)); +ASTWorkerHandle +ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB, + TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks, + Semaphore &Barrier, const TUScheduler::Options &Opts, + ParsingCallbacks &Callbacks, + std::shared_ptr InitialPreamble) { + std::shared_ptr Worker( + new ASTWorker(FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks, Opts, + Callbacks, std::move(InitialPreamble))); if (Tasks) { Tasks->runAsync("ASTWorker:" + llvm::sys::path::filename(FileName), [Worker]() { Worker->run(); }); @@ -587,17 +675,24 @@ ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB, TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, bool RunSync, const TUScheduler::Options &Opts, - ParsingCallbacks &Callbacks) + ParsingCallbacks &Callbacks, + std::shared_ptr InitialPreamble) : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(Opts.UpdateDebounce), FileName(FileName), ContextProvider(Opts.ContextProvider), CDB(CDB), Callbacks(Callbacks), Barrier(Barrier), Done(false), Status(FileName, Callbacks), PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory, - RunSync || !Opts.AsyncPreambleBuilds, Status, *this) { + RunSync || !Opts.AsyncPreambleBuilds, Status, *this, + InitialPreamble) { // Set a fallback command because compile command can be accessed before // `Inputs` is initialized. Other fields are only used after initialization // from client inputs. FileInputs.CompileCommand = CDB.getFallbackCommand(FileName); + if (InitialPreamble) { + vlog("ASTWorker for {0} using an initial preamble ({1})", FileName, + InitialPreamble->Version); + LatestPreamble = std::move(InitialPreamble); + } } ASTWorker::~ASTWorker() { @@ -1249,6 +1344,8 @@ Callbacks(Callbacks ? move(Callbacks) : std::make_unique()), Barrier(Opts.AsyncThreadsCount), + CachedPreambles(std::make_unique( + Opts.KeepPreambles, Opts.StorePreamblesInMemory)), IdleASTs( std::make_unique(Opts.RetentionPolicy.MaxRetainedASTs)) { // Avoid null checks everywhere. @@ -1291,10 +1388,10 @@ bool ContentChanged = false; if (!FD) { // Create a new worker to process the AST-related tasks. - ASTWorkerHandle Worker = - ASTWorker::create(File, CDB, *IdleASTs, - WorkerThreads ? WorkerThreads.getPointer() : nullptr, - Barrier, Opts, *Callbacks); + ASTWorkerHandle Worker = ASTWorker::create( + File, CDB, *IdleASTs, + WorkerThreads ? WorkerThreads.getPointer() : nullptr, Barrier, Opts, + *Callbacks, CachedPreambles->take(File)); FD = std::unique_ptr( new FileData{Inputs.Contents, std::move(Worker)}); ContentChanged = true; @@ -1307,10 +1404,17 @@ } void TUScheduler::remove(PathRef File) { - bool Removed = Files.erase(File); - if (!Removed) + auto It = Files.find(File); + if (It == Files.end()) { elog("Trying to remove file from TUScheduler that is not tracked: {0}", File); + return; + } + + assert(It->second && "FileData not allocated"); + if (auto Preamble = It->second->Worker->getPossiblyStalePreamble()) + CachedPreambles->put(File, std::move(Preamble)); + Files.erase(It); } llvm::StringMap TUScheduler::getAllFileContents() const { @@ -1448,13 +1552,17 @@ } void TUScheduler::profile(MemoryTree &MT) const { + auto &FilesMT = MT.child("files"); for (const auto &Elem : fileStats()) { - MT.detail(Elem.first()) + FilesMT.detail(Elem.first()) .child("preamble") .addUsage(Opts.StorePreamblesInMemory ? Elem.second.UsedBytesPreamble : 0); - MT.detail(Elem.first()).child("ast").addUsage(Elem.second.UsedBytesAST); + FilesMT.detail(Elem.first()) + .child("ast") + .addUsage(Elem.second.UsedBytesAST); } + CachedPreambles->profile(MT.child("cache")); } } // namespace clangd } // namespace clang diff --git a/clang-tools-extra/clangd/test/memory_tree.test b/clang-tools-extra/clangd/test/memory_tree.test --- a/clang-tools-extra/clangd/test/memory_tree.test +++ b/clang-tools-extra/clangd/test/memory_tree.test @@ -57,20 +57,32 @@ # CHECK-NEXT: } # CHECK-NEXT: }, # CHECK-NEXT: "tuscheduler": { -# CHECK-NEXT: "{{.*}}main.cpp": { +# CHECK-NEXT: "_self": {{[0-9]+}}, +# CHECK-NEXT: "_total": {{[0-9]+}}, +# CHECK-NEXT: "cache": { # CHECK-NEXT: "_self": {{[0-9]+}}, # CHECK-NEXT: "_total": {{[0-9]+}}, -# CHECK-NEXT: "ast": { -# CHECK-NEXT: "_self": {{[0-9]+}}, -# CHECK-NEXT: "_total": {{[0-9]+}} -# CHECK-NEXT: }, -# CHECK-NEXT: "preamble": { +# CHECK-NEXT: "containers": { # CHECK-NEXT: "_self": {{[0-9]+}}, # CHECK-NEXT: "_total": {{[0-9]+}} # CHECK-NEXT: } # CHECK-NEXT: }, -# CHECK-NEXT: "_self": {{[0-9]+}}, -# CHECK-NEXT: "_total": {{[0-9]+}} +# CHECK-NEXT: "files": { +# CHECK-NEXT: "{{.*}}main.cpp": { +# CHECK-NEXT: "_self": {{[0-9]+}}, +# CHECK-NEXT: "_total": {{[0-9]+}}, +# CHECK-NEXT: "ast": { +# CHECK-NEXT: "_self": {{[0-9]+}}, +# CHECK-NEXT: "_total": {{[0-9]+}} +# CHECK-NEXT: }, +# CHECK-NEXT: "preamble": { +# CHECK-NEXT: "_self": {{[0-9]+}}, +# CHECK-NEXT: "_total": {{[0-9]+}} +# CHECK-NEXT: } +# CHECK-NEXT: }, +# CHECK-NEXT: "_self": {{[0-9]+}}, +# CHECK-NEXT: "_total": {{[0-9]+}} +# CHECK-NEXT: } # CHECK-NEXT: } # CHECK-NEXT: } # CHECK-NEXT: } diff --git a/clang-tools-extra/clangd/tool/ClangdMain.cpp b/clang-tools-extra/clangd/tool/ClangdMain.cpp --- a/clang-tools-extra/clangd/tool/ClangdMain.cpp +++ b/clang-tools-extra/clangd/tool/ClangdMain.cpp @@ -347,6 +347,16 @@ init(getDefaultAsyncThreadsCount()), }; +// Magic value to know when the user does not specify a value +constexpr size_t DefaultKeepPreambleValue = std::numeric_limits::max(); +constexpr size_t DefaultKeepPreambleMemory = 10; +constexpr size_t DefaultKeepPreambleDisk = 1000; +opt KeepPreambles{ + "keep-preambles", cat(Misc), + desc("Number of preambles of closed files that clangd will keep in cache.\n" + "Note that preambles may be stored in memory or in disk."), + init(DefaultKeepPreambleValue)}; + opt IndexFile{ "index-file", cat(Misc), @@ -821,6 +831,13 @@ Opts.StaticIndex = PAI.get(); } Opts.AsyncThreadsCount = WorkerThreadsCount; + + if (KeepPreambles == DefaultKeepPreambleValue) // User did not specify a value + Opts.KeepPreambles = Opts.StorePreamblesInMemory ? DefaultKeepPreambleMemory + : DefaultKeepPreambleDisk; + else + Opts.KeepPreambles = KeepPreambles; + Opts.BuildRecoveryAST = RecoveryAST; Opts.PreserveRecoveryASTType = RecoveryASTType; Opts.FoldingRanges = FoldingRanges; diff --git a/clang-tools-extra/clangd/unittests/ClangdTests.cpp b/clang-tools-extra/clangd/unittests/ClangdTests.cpp --- a/clang-tools-extra/clangd/unittests/ClangdTests.cpp +++ b/clang-tools-extra/clangd/unittests/ClangdTests.cpp @@ -1256,7 +1256,7 @@ MemoryTree MT(&Alloc); Server.profile(MT); ASSERT_TRUE(MT.children().count("tuscheduler")); - EXPECT_TRUE(MT.child("tuscheduler").children().count(FooCpp)); + EXPECT_TRUE(MT.child("tuscheduler").child("files").children().count(FooCpp)); } } // namespace } // namespace clangd