[clangd] Support external throttler for preamble builds

[sammccall]

Summary

Building preambles is the most resource-intensive thing clangd does, driving
peak RAM and sustained CPU usage.

In a hosted environment where multiple clangd instances are packed into the same
container, it's useful to be able to limit the *aggregate* resource peaks.

[sammccall]

I wanted to send a first version out for feedback even if incomplete.
(I want to do more extensive tests, and likely we should think about having an in-tree throttler on by default)

To motivate the design:

• when attempting to acquire a slot, we want to wait on (acquired || shutting down).
• This means sharing a condition variable for both events, as we can't wait on multiple conditions.
• this leads to the callback-based model for PreambleThrottler, the callback lets us encapsulate the use of a shared CV in this way
• the acquire callback naturally accesses the PreambleThread, but it might have gone away concurrently. This is awkward to solve in a callback API.
• The chosen solution is to heap-allocate a small object that can own the state the callback needs to access

[sammccall]

Summarizing an offline discussion:

• ThrottlerState isolates complexity inside TUScheduler by absolving Throttler of the need to worry about callback lifetimes
• but it does so at the cost of extra aggregate complexity (third object with different lifetime & own threading model)
• the main alternative seems to be to allow deregistration of callbacks on throttler (addListener/removeListener)
  • planning to give that a try.

[kadircet]

we've already discussed most of these so no action needed, but here are some of them before they become completely irrelevant :P

clang-tools-extra/clangd/TUScheduler.cpp

472–482

any reason for capturing locals here now ?

492

in the scenario of a shutdown (or destruction of a preamble thread, because file is closed), i think we also want to call cancellation of the acquire release here. as things stand unless we're destroying the throttler itself i think these requests might stick around.

499

we can move the wait into the if block above, i think.

499

so this implies preamblerequest we issued an acquire for, and the preamble request we'll be building below might be different. this is not a concern initially but i think it would be nice to not get cornered when we want to notify the throttler about such changes.

i guess PreambleThread::update would be the natural place to communicate such changes, if we're overwriting a preamblerequest and there's a pending acquire we can either cancel and make preamblethread re-issue acquire, or we can have a new API on throttler to update the request signals. i think, both of these require having throttlestate as a member. maybe we should do that directly to remind ourselves of this in the future?

1554

let's use "includes" here, similar to above.

clang-tools-extra/clangd/TUScheduler.h

114

can we make the first parameter a struct instead? i feel like we might end up adding more parameters describing the reason for the request here.

[sammccall]

Simplify, leaning more on the throttler's lifetime and expecting it to manage
state.

[sammccall]

remove dead code

[sammccall]

clang-tools-extra/clangd/TUScheduler.cpp

472–482

Just for consistency with the second wait below - I usually don't think it's interesting to list captures when no lifetimes are involved (because the lambda is invoked synchronously)

492

(this is obsolete, but...)

I don't think this leak is possible, after we get Cancel (from Throttler->acquire) then we wait until either:

• request is satisfied (TState->ready() on line 500) in which case no cancel is needed, or
• we call Cancel immediately on line 501.

499

we can move the wait into the if block

that works, but it doesn't really seem clearer to me

wait (..., cond) is just while (!cond) { ... }, so the outer if is redundant.
On the other hand the if is important to the code it currently guards (for reasons explained in the comment), so it seems confusing to split its purpose in this way.

The only way it makes sense to me is as a microoptimization, but it doesn't seem like a useful one.

499

the preamble request we'll be building below might be different

The request in general is (filename, signals). Filename clearly can't change. Signals can, but...

i guess PreambleThread::update would be the natural place to communicate such changes

I don't think so, I think signals naturally come from elsewhere in the system as (filename, signal) pairs and are best thought of as "sticky", where events affect both current and future throttling requests.

As such I think we might have an API like Throttler->updateSignals(Filename, ...) and let the throttler join on filename, rather than require this joining to be done artificially somewhere else in clangd.
One nice thing about this is if there's no throttler, we don't pay for keeping track of the signals.

[sammccall]

address review comments

[kadircet]

thanks, lgtm!

clang-tools-extra/clangd/ClangdServer.h

108

why the qualification ?

clang-tools-extra/clangd/TUScheduler.cpp

414

use PreambleThrottler::RequestID instead of unsigned?

clang-tools-extra/clangd/TUScheduler.h

90

triple slashes here and inside the class

106

there's no cancel anymore.

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

1499

sequencing is hard here but it'd be nice to ensure release is actually seen.

[sammccall]

clang-tools-extra/clangd/ClangdServer.h

108

same name is used for the type and the member name, an error in at least some compilers (I forget what the standard says).
I can't think of another good name

clang-tools-extra/clangd/TUScheduler.h

114

My hypothesis is that *all* other parameters will be provided separately on unrelated codepaths (Throttler->setFoo(Filename, Foo)) and the name here is a join key rather than one parameter among many.

I might be wrong about this but would rather hold off on generalizing until we're sure.

[anarazel]

This caused llvm builds to fail for me (using clang-14, debug, debian unstable, lld as linker):

FAILED: tools/clang/tools/extra/clangd/unittests/ClangdTests 
: && /usr/bin/clang++-14 -gz=zlib -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -fno-common -Woverloaded-virtual -Wno-nested-anon-types -g -Wl,-rpath,/home/andres/build/llvm-project/master/debug-clang/install/lib -Wl,--gdb-index -fuse-ld=lld -Wl,--gdb-index -Wl,--color-diagnostics tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/AddUsing.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/AnnotateHighlightings.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/DumpAST.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/DefineInline.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/DefineOutline.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/ExpandAutoType.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/ExpandMacro.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/ExtractFunction.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/ExtractVariable.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/MemberwiseConstructor.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/ObjCLocalizeStringLiteral.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/ObjCMemberwiseInitializer.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/PopulateSwitch.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/RawStringLiteral.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/RemoveUsingNamespace.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/SpecialMembers.cpp.o tools/clang/tools/extra/clangd/refactor/tweaks/CMakeFiles/obj.clangDaemonTweaks.dir/SwapIfBranches.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/Annotations.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ASTTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ASTSignalsTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/BackgroundIndexTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/CallHierarchyTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/CanonicalIncludesTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ClangdTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ClangdLSPServerTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/CodeCompleteTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/CodeCompletionStringsTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/CollectMacrosTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/CompileCommandsTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/CompilerTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ConfigCompileTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ConfigProviderTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ConfigYAMLTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/DecisionForestTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/DexTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/DiagnosticsTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/DraftStoreTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/DumpASTTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ExpectedTypeTest.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/FeatureModulesTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/FileDistanceTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/FileIndexTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/FindSymbolsTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/FindTargetTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/FormatTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/FSTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/FuzzyMatchTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/GlobalCompilationDatabaseTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/HeadersTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/HeaderSourceSwitchTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/HoverTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/IncludeCleanerTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/IndexActionTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/IndexTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/InlayHintTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/InsertionPointTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/JSONTransportTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/LoggerTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/LSPBinderTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/LSPClient.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ModulesTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ParsedASTTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/PathMappingTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/PreambleTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/PrintASTTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ProjectAwareIndexTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/QualityTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/RenameTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/RIFFTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/SelectionTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/SemanticHighlightingTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/SemanticSelectionTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/SerializationTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/SourceCodeTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/StdLibTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/SymbolCollectorTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/SymbolInfoTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/SyncAPI.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/TUSchedulerTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/TestFS.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/TestIndex.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/TestTU.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/TestWorkspace.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/ThreadCrashReporterTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/TidyProviderTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/TypeHierarchyTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/URITests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/XRefsTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/DecisionForestRuntimeTest.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/CancellationTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/ContextTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/FunctionTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/MarkupTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/MemoryTreeTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/PathTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/ThreadingTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/TestTracer.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/support/TraceTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/AddUsingTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/AnnotateHighlightingsTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/DefineInlineTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/DefineOutlineTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/DumpASTTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/DumpRecordLayoutTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/DumpSymbolTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/ExpandAutoTypeTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/ExpandMacroTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/ExtractFunctionTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/ExtractVariableTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/MemberwiseConstructorTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/ObjCLocalizeStringLiteralTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/ObjCMemberwiseInitializerTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/PopulateSwitchTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/RawStringLiteralTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/RemoveUsingNamespaceTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/ShowSelectionTreeTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/SwapIfBranchesTests.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/TweakTesting.cpp.o tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/tweaks/TweakTests.cpp.o -o tools/clang/tools/extra/clangd/unittests/ClangdTests  -Wl,-rpath,/home/andres/build/llvm-project/master/debug-clang/vpath/lib  -lpthread  lib/libllvm_gtest_main.so.15git  -lpthread  lib/libclangDaemon.so.15git  lib/libclangdSupport.so.15git  lib/libLLVMTestingSupport.so.15git  lib/libLLVMX86Info.so.15git  lib/libclangToolingSyntax.so.15git  lib/libclangTidy.so.15git  lib/libclangTooling.so.15git  lib/libclangToolingRefactoring.so.15git  lib/libclangIndex.so.15git  lib/libclangFormat.so.15git  lib/libclangToolingInclusions.so.15git  lib/libclangFrontend.so.15git  lib/libclangSerialization.so.15git  lib/libclangSema.so.15git  lib/libclangASTMatchers.so.15git  lib/libclangAST.so.15git  lib/libLLVMFrontendOpenMP.so.15git  lib/libclangToolingCore.so.15git  lib/libclangLex.so.15git  lib/libclangBasic.so.15git  lib/libllvm_gtest.so.15git  lib/libLLVMSupport.so.15git  -Wl,-rpath-link,/home/andres/build/llvm-project/master/debug-clang/vpath/lib && :
ld.lld: error: undefined symbol: vtable for clang::clangd::PreambleThrottler
>>> referenced by TUScheduler.h:97 (/home/andres/src/llvm-project/clang-tools-extra/clangd/TUScheduler.h:97)
>>>               tools/clang/tools/extra/clangd/unittests/CMakeFiles/ClangdTests.dir/TUSchedulerTests.cpp.o:(clang::clangd::PreambleThrottler::PreambleThrottler())
>>> the vtable symbol may be undefined because the class is missing its key function (see https://lld.llvm.org/missingkeyfunction)
clang: error: linker command failed with exit code 1 (use -v to see invocation)

[sammccall]

In D129100#3633073, @anarazel wrote:

This caused llvm builds to fail for me (using clang-14, debug, debian unstable, lld as linker):

Thanks, I have a very similar setup but the build passed locally, I'll never understand linkers...

I think I've fixed this in e7fa272bc6a6a504c2899bb7cf66029678d97890

[anarazel]

Hi,

[vitalybuka]

This looks flaky https://lab.llvm.org/buildbot/#/builders/5/builds/25929

[sammccall]

In D129100#3634548, @vitalybuka wrote:

This looks flaky https://lab.llvm.org/buildbot/#/builders/5/builds/25929

Sorry about that, I believe this is fixed in eb64dbd6e0e617298579d32372fb92e595816d45.
(The flake symptoms I was able to see locally are different, but I would guess the same cause)

[sammccall]

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

1499

So this turned out to be the cause of the test flakiness: the mechanism we discussed offline (context destruction) doesn't work.

The problem is that the context lives in the request, and we haven't moved the request from NextReq into CurrentReq yet (we're still throttling).
NextReq is destroyed when stop() is called. So S.remove(A) actually triggers AfterFinishA already, and then the following assertions race against the release() call.

I probably could have gotten this out of our tsan bot, but it's not producing any sanitizer logs (I suspect D122251).

In any case, this particular race is definitely only in the test, so disabling it until we have a real fix next week.

[kadircet]

clang-tools-extra/clangd/TUScheduler.cpp

499

regarding the flakiness, what about resetting the Throttle here to trigger the release? it's right after the build and would make sure release happens before the context is destroyed (+ we're not holding any locks)

[sammccall]

clang-tools-extra/clangd/TUScheduler.cpp

499

The critical case never gets here: done() is called while waiting for the throttler, and we never get to build anything.

(And by the time that wait is interrupted, the context is already concurrently being destroyed.)

clang-tools-extra/clangd/ClangdServer.h

struct Options {
     unsigned AsyncThreadsCount = getDefaultAsyncThreadsCount();
 
     /// AST caching policy. The default is to keep up to 3 ASTs in memory.
     ASTRetentionPolicy RetentionPolicy;
 
     /// Cached preambles are potentially large. If false, store them on disk.
     bool StorePreamblesInMemory = true;
 
+    /// This throttler controls which preambles may be built at a given time.
+    clangd::PreambleThrottler *PreambleThrottler = nullptr;
+
     /// If true, ClangdServer builds a dynamic in-memory index for symbols in
     /// opened files and uses the index to augment code completion results.
     bool BuildDynamicSymbolIndex = false;
     /// If true, ClangdServer automatically indexes files in the current project
     /// on background threads. The index is stored in the project root.
     bool BackgroundIndex = false;
     llvm::ThreadPriority BackgroundIndexPriority = llvm::ThreadPriority::Low;
 

clang-tools-extra/clangd/ClangdServer.cpp

 
 ClangdServer::Options::operator TUScheduler::Options() const {
   TUScheduler::Options Opts;
   Opts.AsyncThreadsCount = AsyncThreadsCount;
   Opts.RetentionPolicy = RetentionPolicy;
   Opts.StorePreamblesInMemory = StorePreamblesInMemory;
   Opts.UpdateDebounce = UpdateDebounce;
   Opts.ContextProvider = ContextProvider;
+  Opts.PreambleThrottler = PreambleThrottler;
   return Opts;
 }
 
 ClangdServer::ClangdServer(const GlobalCompilationDatabase &CDB,
                            const ThreadsafeFS &TFS, const Options &Opts,
                            Callbacks *Callbacks)
     : FeatureModules(Opts.FeatureModules), CDB(CDB), TFS(TFS),
       DynamicIdx(Opts.BuildDynamicSymbolIndex ? new FileIndex() : nullptr),

clang-tools-extra/clangd/TUScheduler.h

struct DebouncePolicy {
   float RebuildRatio = 1;
 
   /// Compute the time to debounce based on this policy and recent build times.
   clock::duration compute(llvm::ArrayRef<clock::duration> History) const;
   /// A policy that always returns the same duration, useful for tests.
   static DebouncePolicy fixed(clock::duration);
 };
 
+/// PreambleThrottler controls which preambles can build at any given time.
+/// This can be used to limit overall concurrency, and to prioritize some
+/// preambles over others.
+/// In a distributed environment, a throttler may be able to coordinate resource
+/// use across several clangd instances.
+///
+/// This class is threadsafe.
+class PreambleThrottler {
+public:
+  virtual ~PreambleThrottler() = default;
+
+  using RequestID = unsigned;
+  using Callback = llvm::unique_function<void()>;
+  /// Attempt to acquire resources to build a file's preamble.
+  ///
+  /// Does not block, may eventually invoke the callback to satisfy the request.
+  /// If the callback is invoked, release() must be called afterwards.
+  virtual RequestID acquire(llvm::StringRef Filename, Callback);
+  /// Abandons the request/releases any resources that have been acquired.
+  ///
+  /// Must be called exactly once after acquire().
+  /// acquire()'s callback will not be invoked after release() returns.
+  virtual void release(RequestID) = 0;
+
+  // FIXME: we may want to be able attach signals to filenames.
+  //        this would allow the throttler to make better scheduling decisions.
+};
+
 enum class PreambleAction {
-  Idle,
+  Queued,
   Building,
+  Idle,
 };
 
 struct ASTAction {
   enum Kind {
     Queued,        // The action is pending in the thread task queue to be run.
     RunningAction, // Started running actions on the TU.
     Building,      // The AST is being built.
     Idle, // Indicates the worker thread is idle, and ready to run any upcoming
struct Options {
 
     /// Time to wait after an update to see if another one comes along.
     /// This tries to ensure we rebuild once the user stops typing.
     DebouncePolicy UpdateDebounce;
 
     /// Determines when to keep idle ASTs in memory for future use.
     ASTRetentionPolicy RetentionPolicy;
 
+    /// This throttler controls which preambles may be built at a given time.
+    clangd::PreambleThrottler *PreambleThrottler = nullptr;
+
     /// 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".
     std::function<Context(PathRef)> ContextProvider;
   };
 
   TUScheduler(const GlobalCompilationDatabase &CDB, const Options &Opts,
               std::unique_ptr<ParsingCallbacks> ASTCallbacks = nullptr);

clang-tools-extra/clangd/TUScheduler.cpp

private:
   const Path FileName;
 
   std::mutex StatusMu;
   TUStatus Status;
   bool CanPublish = true;
   ParsingCallbacks &Callbacks;
 };
 
+// An attempt to acquire resources for a task using PreambleThrottler.
+// Initially it is unsatisfied, it (hopefully) becomes satisfied later but may
+// be destroyed before then. Destruction releases all resources.
+class PreambleThrottlerRequest {
+public:
+  // The condition variable is signalled when the request is satisfied.
+  PreambleThrottlerRequest(llvm::StringRef Filename,
+                           PreambleThrottler *Throttler,
+                           std::condition_variable &CV)
+      : Throttler(Throttler), Satisfied(Throttler == nullptr) {
+    // If there is no throttler, this dummy request is always satisfied.
+    if (!Throttler)
+      return;
+    ID = Throttler->acquire(Filename, [&] {
+      Satisfied.store(true, std::memory_order_release);
+      CV.notify_all();
+    });
+  }
+
+  bool satisfied() const { return Satisfied.load(std::memory_order_acquire); }
+
+  // When the request is destroyed:
+  //  - if resources are not yet obtained, stop trying to get them.
+  //  - if resources were obtained, release them.
+  ~PreambleThrottlerRequest() {
+    if (Throttler)
+      Throttler->release(ID);
+  }
+
+private:
+  PreambleThrottler::RequestID ID;
+  PreambleThrottler *Throttler;
+  std::atomic<bool> Satisfied = {false};
+};
+
 /// Responsible for building preambles. Whenever the thread is idle and the
 /// preamble is outdated, it starts to build a fresh preamble from the latest
 /// inputs. If RunSync is true, preambles are built synchronously in update()
 /// instead.
 class PreambleThread {
 public:
   PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks,
                  bool StorePreambleInMemory, bool RunSync,
-                 SynchronizedTUStatus &Status,
+                 PreambleThrottler *Throttler, SynchronizedTUStatus &Status,
                  TUScheduler::HeaderIncluderCache &HeaderIncluders,
                  ASTWorker &AW)
       : FileName(FileName), Callbacks(Callbacks),
-        StoreInMemory(StorePreambleInMemory), RunSync(RunSync), Status(Status),
-        ASTPeer(AW), HeaderIncluders(HeaderIncluders) {}
+        StoreInMemory(StorePreambleInMemory), RunSync(RunSync),
+        Throttler(Throttler), Status(Status), ASTPeer(AW),
+        HeaderIncluders(HeaderIncluders) {}
 
   /// 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
   /// will be built.
   void update(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
               std::vector<Diag> CIDiags, WantDiagnostics WantDiags) {
     Request Req = {std::move(CI), std::move(PI), std::move(CIDiags), WantDiags,
                    Context::current().clone()};
void update(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
     }
     // Let the worker thread know there's a request, notify_one is safe as there
     // should be a single worker thread waiting on it.
     ReqCV.notify_all();
   }
 
   void run() {
     while (true) {
+      llvm::Optional<PreambleThrottlerRequest> Throttle;
       {
         std::unique_lock<std::mutex> Lock(Mutex);
         assert(!CurrentReq && "Already processing a request?");
         // Wait until stop is called or there is a request.
-        ReqCV.wait(Lock, [this] { return NextReq || Done; });
+        ReqCV.wait(Lock, [&] { return NextReq || Done; });
         if (Done)
           break;
+
+        Throttle.emplace(FileName, Throttler, ReqCV);
+        // If acquire succeeded synchronously, avoid status jitter.
+        if (!Throttle->satisfied())
+          Status.update([&](TUStatus &Status) {
+            Status.PreambleActivity = PreambleAction::Queued;
+          });
+        ReqCV.wait(Lock, [&] { return Throttle->satisfied() || Done; });
+        if (Done)
+          break;
+        // While waiting for the throttler, the request may have been updated!
+        // That's fine though, there's still guaranteed to be some request.
+
         CurrentReq = std::move(*NextReq);
         NextReq.reset();
       }
 
       {
         WithContext Guard(std::move(CurrentReq->Ctx));
         // Note that we don't make use of the ContextProvider here.
         // Preamble tasks are always scheduled by ASTWorker tasks, and we
         // reuse the context/config that was created at that level.
 
         // Build the preamble and let the waiters know about it.
         build(std::move(*CurrentReq));
       }
       bool IsEmpty = false;
       {
         std::lock_guard<std::mutex> Lock(Mutex);
         CurrentReq.reset();
         IsEmpty = !NextReq;
       }
       if (IsEmpty) {
private:
   mutable std::condition_variable ReqCV; /* GUARDED_BY(Mutex) */
   // Accessed only by preamble thread.
   std::shared_ptr<const PreambleData> LatestBuild;
 
   const Path FileName;
   ParsingCallbacks &Callbacks;
   const bool StoreInMemory;
   const bool RunSync;
+  PreambleThrottler *Throttler;
 
   SynchronizedTUStatus &Status;
   ASTWorker &ASTPeer;
   TUScheduler::HeaderIncluderCache &HeaderIncluders;
 };
 
 class ASTWorkerHandle;
 
ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
                      Semaphore &Barrier, bool RunSync,
                      const TUScheduler::Options &Opts,
                      ParsingCallbacks &Callbacks)
     : IdleASTs(LRUCache), HeaderIncluders(HeaderIncluders), 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,
-                   Status, HeaderIncluders, *this) {
+                   Opts.PreambleThrottler, Status, HeaderIncluders, *this) {
   // 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);
 }
 
 ASTWorker::~ASTWorker() {
   // Make sure we remove the cached AST, if any.

 // to users (say C++ programmers) directly to avoid confusion, we use terms that
 // are familiar by C++ programmers.
 std::string renderTUAction(const PreambleAction PA, const ASTAction &AA) {
   llvm::SmallVector<std::string, 2> Result;
   switch (PA) {
   case PreambleAction::Building:
     Result.push_back("parsing includes");
     break;
+  case PreambleAction::Queued:
+    Result.push_back("includes are queued");
+    break;
   case PreambleAction::Idle:
     // We handle idle specially below.
     break;
   }
   switch (AA.K) {
   case ASTAction::Queued:
     Result.push_back("file is queued");
     break;

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

for (bool Sync : {false, true}) {
 
     // An update with the same contents should not change LastActiveFile.
     auto LastActive = Path;
     Path = testPath("runWithAST.cc");
     S.update(Path, getInputs(Path, ""), WantDiagnostics::No);
     CheckNoFileActionsSeesLastActiveFile(LastActive);
   }
 }
+
+TEST_F(TUSchedulerTests, PreambleThrottle) {
+  const int NumRequests = 4;
+  // Silly throttler that waits for 4 requests, and services them in reverse.
+  // Doesn't honor cancellation but records it.
+  struct : public PreambleThrottler {
+    std::mutex Mu;
+    std::vector<std::string> Acquires;
+    std::vector<RequestID> Releases;
+    llvm::DenseMap<RequestID, Callback> Callbacks;
+    // If set, the notification is signalled after acquiring the specified ID.
+    llvm::Optional<std::pair<RequestID, Notification *>> Notify;
+
+    RequestID acquire(llvm::StringRef Filename, Callback CB) override {
+      RequestID ID;
+      Callback Invoke;
+      {
+        std::lock_guard<std::mutex> Lock(Mu);
+        ID = Acquires.size();
+        Acquires.emplace_back(Filename);
+        // If we're full, satisfy this request immediately.
+        if (Acquires.size() == NumRequests) {
+          Invoke = std::move(CB);
+        } else {
+          Callbacks.try_emplace(ID, std::move(CB));
+        }
+      }
+      if (Invoke)
+        Invoke();
+      if (Notify && ID == Notify->first) {
+        Notify->second->notify();
+        Notify.reset();
+      }
+      return ID;
+    }
+
+    void release(RequestID ID) override {
+      Releases.push_back(ID);
+      Callback SatisfyNext;
+      {
+        std::lock_guard<std::mutex> Lock(Mu);
+        if (ID > 0)
+          SatisfyNext = std::move(Callbacks[ID - 1]);
+      }
+      if (SatisfyNext)
+        SatisfyNext();
+    }
+
+    void reset() {
+      Acquires.clear();
+      Releases.clear();
+      Callbacks.clear();
+    }
+  } Throttler;
+
+  struct CaptureBuiltFilenames : public ParsingCallbacks {
+    std::vector<std::string> &Filenames;
+    CaptureBuiltFilenames(std::vector<std::string> &Filenames)
+        : Filenames(Filenames) {}
+    void onPreambleAST(PathRef Path, llvm::StringRef Version,
+                       const CompilerInvocation &CI, ASTContext &Ctx,
+                       Preprocessor &PP, const CanonicalIncludes &) override {
+      // Deliberately no synchronization.
+      // The PreambleThrottler should serialize these calls, if not then tsan
+      // will find a bug here.
+      Filenames.emplace_back(Path);
+    }
+  };
+
+  auto Opts = optsForTest();
+  Opts.AsyncThreadsCount = 2 * NumRequests; // throttler is the bottleneck
+  Opts.PreambleThrottler = &Throttler;
+
+  std::vector<std::string> Filenames;
+
+  {
+    std::vector<std::string> BuiltFilenames;
+    TUScheduler S(CDB, Opts,
+                  std::make_unique<CaptureBuiltFilenames>(BuiltFilenames));
+    for (unsigned I = 0; I < NumRequests; ++I) {
+      auto Path = testPath(std::to_string(I) + ".cc");
+      Filenames.push_back(Path);
+      S.update(Path, getInputs(Path, ""), WantDiagnostics::Yes);
+    }
+    ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+
+    // The throttler saw all files, and we built them.
+    EXPECT_THAT(Throttler.Acquires,
+                testing::UnorderedElementsAreArray(Filenames));
+    EXPECT_THAT(BuiltFilenames,
+                testing::UnorderedElementsAreArray(Filenames));
+    // We built the files in reverse order that the throttler saw them.
+    EXPECT_THAT(BuiltFilenames,
+                testing::ElementsAreArray(Throttler.Acquires.rbegin(),
+                                          Throttler.Acquires.rend()));
+    // Resources for each file were correctly released.
+    EXPECT_THAT(Throttler.Releases, ElementsAre(3, 2, 1, 0));
+  }
+
+  Throttler.reset();
+
+  // This time, enqueue 2 files, then cancel one of them while still waiting.
+  // Finally shut down the server. Observe that everything gets cleaned up.
+  Notification AfterAcquire2;
+  Notification AfterFinishA;
+  Throttler.Notify = {1, &AfterAcquire2};
+  std::vector<std::string> BuiltFilenames;
+  auto A = testPath("a.cc");
+  auto B = testPath("b.cc");
+  Filenames = {A, B};
+  {
+    TUScheduler S(CDB, Opts,
+                  std::make_unique<CaptureBuiltFilenames>(BuiltFilenames));
+    updateWithCallback(S, A, getInputs(A, ""), WantDiagnostics::Yes,
+                       [&] { AfterFinishA.notify(); });
+    S.update(B, getInputs(B, ""), WantDiagnostics::Yes);
+    AfterAcquire2.wait();
+
+    // The throttler saw all files, but we built none.
+    EXPECT_THAT(Throttler.Acquires,
+                testing::UnorderedElementsAreArray(Filenames));
+    EXPECT_THAT(BuiltFilenames, testing::IsEmpty());
+    // We haven't released anything yet, we're still waiting.
+    EXPECT_THAT(Throttler.Releases, testing::IsEmpty());
+
+    // Now close file A, which will shut down its AST worker.
+    S.remove(A);
+    // Request is destroyed after the queue shutdown, so release() has happened.
+    AfterFinishA.wait();
+    // We still didn't build anything.
+    EXPECT_THAT(BuiltFilenames, testing::IsEmpty());
+    // But we've cancelled the request to build A (not sure which its ID is).
+    EXPECT_THAT(Throttler.Releases, ElementsAre(AnyOf(1, 0)));
+
+    // Now shut down the TU Scheduler.
+  }
+  // The throttler saw all files, but we built none.
+  EXPECT_THAT(Throttler.Acquires,
+              testing::UnorderedElementsAreArray(Filenames));
+  EXPECT_THAT(BuiltFilenames, testing::IsEmpty());
+  // We gave up waiting and everything got released (in some order).
+  EXPECT_THAT(Throttler.Releases, UnorderedElementsAre(1, 0));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang