[clang][clangd] Ensure the stack bottom before building AST

[zyounan]

Summary

clang::runWithSufficientStackSpace requires the address of the
initial stack bottom to prevent potential stack overflows.

In addition, add a fallback to ASTFrontendAction in case any client
forgets to call it when not through CompilerInstance::ExecuteAction,
which is rare.

Fixes https://github.com/clangd/clangd/issues/1745.

[ilya-biryukov]

Would it be better to do this in the code that runs the parser?
This should help not only Clangd, but all the tools as well.

clang::ParseAST or ASTFrontendAction::ExecuteAction look like good candidates to me.

WDYT?

[zyounan]

clang::ParseAST or ASTFrontendAction::ExecuteAction look like good candidates to me.

We had already placed the initialization in ASTFrontendAction::ExecuteAction, but we don't have such if we prefer invoking the action outside the libclang. (Just as what we're doing now at the clangd site.)

I'm not 100% sure if clang::ParseAST is appropriate since this might cause a side effect to the global state. Would this break the encapsulation hierarchy?

[ilya-biryukov]

In D158967#4620931, @zyounan wrote:

We had already placed the initialization in ASTFrontendAction::ExecuteAction, but we don't have such if we prefer invoking the action outside the libclang. (Just as what we're doing now at the clangd site.)

That's CompilerInstance::ExecuteAction, Clangd invokes ASTFrontendAction::ExecuteAction and had the noteBottomOfStack() been placed there, no change would be needed on the Clangd side.

I'm not 100% sure if clang::ParseAST is appropriate since this might cause a side effect to the global state. Would this break the encapsulation hierarchy?

Could you clarify what kind of encapsulation would it break?
Setting the global variable is suspicious, but the same argument applies for CompilerInstance::ExecuteAction.

Pragmatically, it's hard to ensure that noteBottomOfStack is called for each Clang tool (I'm sure there is a long tail of tools that don't do that).
Currently the code in CompilerInstance::ExecuteAction seems to acknowledge that there should be a fallback. I'm suggesting to move this fallback down to a function that actually runs parsing.
This would ensure the same workaround applies to more tools (including Clangd, IIUC) that don't call noteBottomOfStack.
Tools that do call noteBottomOfStack will not be affected as the function only remembers the first value for each thread.

Another alternative to enforce the right contract would be to assert that bottom of stack is set when parser and other recursive computations are called.
It's easy enough to achieve, but would be breaking many clients and would be a bigger cleanup.

That being said, it's perfectly reasonable to make sure Clangd calls noteBottomOfStack at the right places.
According to documentation of noteBottomOfStack, those should be tied to thread creation, i.e. main and AsyncTaskRunner are two most common entry points for threads that do parsing.
Clangd also creates other threads, but IIUC they are not running any recursive computations, so noteBottomOfStack is not strictly necessary there (but shouldn't hurt either).

[zyounan]

Thanks for the reply. And I understand (and agree with) the point that it's better to solve this problem once and for all.

Currently the code in CompilerInstance::ExecuteAction seems to acknowledge that there should be a fallback. I'm suggesting to move this fallback down to a function that actually runs parsing.

One thing I'm afraid of is, that there are/were some compatible reasons that made us decide not to insert this call at ASTFrontendAction::ExecuteAction nor clang::ParseAST. (I didn't see the explanation in D66361. Richard, could you kindly explain why? @rsmith)

That's CompilerInstance::ExecuteAction

Sorry for my mistake. I thought placing that in CompilerInstance was enough for most tools since it's less likely for developers to invoke the FrontendAction on their own, and for "advanced" users (like clangd) who'd like to control every step handling the AST, maybe it's fine to give them the opportunity to decide if it should crash on infinite recursion?

However, creating such a discrepancy doesn't make much sense. I'm happy to move this call to libclang if this won't break many things.

Could you clarify what kind of encapsulation would it break?

(That's just my spitballing, please don't mind. :)

[zyounan]

According to documentation of noteBottomOfStack, those should be tied to thread creation, i.e. main and AsyncTaskRunner are two most common entry points for threads that do parsing.

Yeah, I was about to put this call there. But they both boil down to the single ParsedAST::build(), right? (Admittedly, this breaks the "encapsulation" if we say 'the build process for AST should not bring any other side effects besides the AST itself', and this doesn't adhere to the document that it should be created at the beginning of the thread/program.)

Currently the code in CompilerInstance::ExecuteAction seems to acknowledge that there should be a fallback. I'm suggesting to move this fallback down to a function that actually runs parsing.

Upon the implementation, the result will be more accurate if it occurs earlier before diving into parsing. Maybe we can do both, that put this call at clangd site and libclang's ASTFrontendAction::ExecuteAction?

[zyounan]

Adopt the comments.

[zyounan]

.

[zyounan]

@ilya-biryukov I've updated the patch following your suggestion. PTAL, thanks!

[zyounan]

Oops, something went wrong accidently.

[rsmith]

In D158967#4621361, @zyounan wrote:

Currently the code in CompilerInstance::ExecuteAction seems to acknowledge that there should be a fallback. I'm suggesting to move this fallback down to a function that actually runs parsing.

One thing I'm afraid of is, that there are/were some compatible reasons that made us decide not to insert this call at ASTFrontendAction::ExecuteAction nor clang::ParseAST. (I didn't see the explanation in D66361. Richard, could you kindly explain why? @rsmith)

D66361 wasn't intended to cover all possible uses by itself. The recovery from deep recursion is best-effort, and it was expected that some tools that call into Clang in less common ways would need to manually call noteBottomOfStack if they wanted to enable this recovery. I put the fallback call in CompilerInstance::ExecuteAction because I thought it would do the right thing in most cases, and not require any effort for most tools. Adding another fallback in ASTFrontendAction::ExecuteAction seems OK to me if that's an entry point that's commonly used by tools. (Where is that being called from in clangd's case? Is there a higher point in the call stack where we could put the call to noteBottomOfStack instead?)

[sammccall]

In D158967#4626156, @rsmith wrote:

Adding another fallback in ASTFrontendAction::ExecuteAction seems OK to me if that's an entry point that's commonly used by tools. (Where is that being called from in clangd's case? Is there a higher point in the call stack where we could put the call to noteBottomOfStack instead?)

clangd calls FrontendAction::Execute() (in clangd::ParsedAST::build, in clang::PrecompiledPreamble::Build, and in clangd::BackgroundIndex::index). I doubt we're the only one.
All of these run somewhere under main() or in a thread spawned by an AsyncTaskRunner.

So to me this fallback makes sense, but we should also add calls to those two places so we really get the bottom of the stack.

(If noteBottomOfStack() were part of llvm support, then this could be built into llvm::Thread...)

clang-tools-extra/clangd/tool/Check.cpp

445 ↗

(On Diff #554285)

I like the idea that we only parse on the main thread with -check, but it's not quite true: we also do this with -sync. I think this should go in main() instead.

[zyounan]

Address comment

[zyounan]

Thanks again for Richard and Sam's comments!

(I didn't add another lit test for asynchronous case since it essentially works the same as the synchronous one. Hope this isn't harmful.)

[sammccall]

clang-tools-extra/clangd/support/Threading.cpp

102 ↗

(On Diff #554674)

ugh, I forgot: this function is part of clangBasic (which is not small!) and clangdSupport shouldn't depend on clang at all.

I'm afraid the easiest fix is to move this to the tasks in the relevant callsites:

• indexStdlib() in ClangdServer.cpp
• ASTWorker::run(), PreambleWorker::run(), TUScheduler::runWithPreamble() in TUScheduler.cpp
• BackgroundIndex() in index/Background.cpp

(I guess principled thing would be to make noteBottomOfStack() part of llvm Support, but that seems complicated)

[zyounan]

Disperse the call over clangd tasks

[zyounan]

Thanks! I hope I'm getting things right. Specifically,

1. UpdateIndexCallbacks::indexStdlib()::Task in ClangdServer.cpp
2. PreambleThread::run(), ASTWorker::run() and TUScheduler::runWithPreamble()::Task in TUScheduler.cpp
3. The lambda of runAsync in BackgroundIndex::BackgroundIndex() in index/Background.cpp.

clang-tools-extra/clangd/support/Threading.cpp

102 ↗

(On Diff #554674)

Ah, I've never noticed clangdSupport is independent of clang.

(I guess principled thing would be to make noteBottomOfStack() part of llvm Support, but that seems complicated)

Agreed. And I think it requires an RFC before we have that migrate to llvmSupport.

[sammccall]

Thanks! Sorry about the layering mess...

clang-tools-extra/clangd/support/Threading.cpp

11 ↗

(On Diff #555356)

need to remove this include too :-)

[zyounan]

Remove the stray header

clang-tools-extra/clangd/ClangdServer.cpp

 #include "index/StdLib.h"
 #include "refactor/Rename.h"
 #include "refactor/Tweak.h"
 #include "support/Cancellation.h"
 #include "support/Logger.h"
 #include "support/MemoryTree.h"
 #include "support/ThreadsafeFS.h"
 #include "support/Trace.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Format/Format.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <chrono>
 #include <future>
 #include <memory>
 #include <mutex>
 #include <optional>
 #include <string>
 #include <type_traits>
-#include <vector>
 #include <utility>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 // Tracks number of times a tweak has been offered.
 static constexpr trace::Metric TweakAvailable(
     "tweak_available", trace::Metric::Counter, "tweak_id");
void indexStdlib(const CompilerInvocation &CI, StdLibLocation Loc) {
     auto Task = [LO(*CI.getLangOpts()), Loc(std::move(Loc)),
                  CI(std::make_unique<CompilerInvocation>(CI)),
                  // External values that outlive ClangdServer
                  TFS(&TFS),
                  // Index outlives TUScheduler (declared first)
                  FIndex(FIndex),
                  // shared_ptr extends lifetime
                  Stdlib(Stdlib)]() mutable {
+      clang::noteBottomOfStack();
       IndexFileIn IF;
       IF.Symbols = indexStandardLibrary(std::move(CI), Loc, *TFS);
       if (Stdlib->isBest(LO))
         FIndex->updatePreamble(std::move(IF));
     };
     if (Tasks)
       // This doesn't have a semaphore to enforce -j, but it's rare.
       Tasks->runAsync("IndexStdlib", std::move(Task));

clang-tools-extra/clangd/TUScheduler.cpp

 #include "support/Cancellation.h"
 #include "support/Context.h"
 #include "support/Logger.h"
 #include "support/MemoryTree.h"
 #include "support/Path.h"
 #include "support/ThreadCrashReporter.h"
 #include "support/Threading.h"
 #include "support/Trace.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/FunctionExtras.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
if (RunSync) {
       NextReq = std::move(Req);
     }
     // 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() {
+    // We mark the current as the stack bottom so that clang running on this
+    // thread can notice the stack usage and prevent stack overflow with best
+    // efforts. Same applies to other calls thoughout clangd.
+    clang::noteBottomOfStack();
     while (true) {
       std::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, [&] { return NextReq || Done; });
         if (Done)
if (RunSync) {
     Requests.push_back({std::move(Task), std::string(Name), steady_clock::now(),
                         std::move(Ctx), std::move(QueueCtx), Update,
                         Invalidation, std::move(Invalidate)});
   }
   RequestsCV.notify_all();
 }
 
 void ASTWorker::run() {
+  clang::noteBottomOfStack();
   while (true) {
     {
       std::unique_lock<std::mutex> Lock(Mutex);
       assert(!CurrentRequest && "A task is already running, multiple workers?");
       for (auto Wait = scheduleLocked(); !Wait.expired();
            Wait = scheduleLocked()) {
         assert(PreambleRequests.empty() &&
                "Preamble updates should be scheduled immediately");
void TUScheduler::runWithPreamble(llvm::StringRef Name, PathRef File,
 
   std::shared_ptr<const ASTWorker> Worker = It->second->Worker.lock();
   auto Task = [Worker, Consistency, Name = Name.str(), File = File.str(),
                Contents = It->second->Contents,
                Command = Worker->getCurrentCompileCommand(),
                Ctx = Context::current().derive(FileBeingProcessed,
                                                std::string(File)),
                Action = std::move(Action), this]() mutable {
+    clang::noteBottomOfStack();
     ThreadCrashReporter ScopedReporter([&Name, &Contents, &Command]() {
       llvm::errs() << "Signalled during preamble action: " << Name << "\n";
       crashDumpCompileCommand(llvm::errs(), Command);
       crashDumpFileContents(llvm::errs(), Contents);
     });
     std::shared_ptr<const PreambleData> Preamble;
     if (Consistency == PreambleConsistency::Stale) {
       // Wait until the preamble is built for the first time, if preamble

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

 #include "support/Context.h"
 #include "support/Logger.h"
 #include "support/Path.h"
 #include "support/Threading.h"
 #include "support/ThreadsafeFS.h"
 #include "support/Trace.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Frontend/FrontendAction.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Path.h"
: SwapIndex(std::make_unique<MemIndex>()), TFS(TFS), CDB(CDB),
           CDB.watch([&](const std::vector<std::string> &ChangedFiles) {
             enqueue(ChangedFiles);
           })) {
   assert(Opts.ThreadPoolSize > 0 && "Thread pool size can't be zero.");
   assert(this->IndexStorageFactory && "Storage factory can not be null!");
   for (unsigned I = 0; I < Opts.ThreadPoolSize; ++I) {
     ThreadPool.runAsync("background-worker-" + llvm::Twine(I + 1),
                         [this, Ctx(Context::current().clone())]() mutable {
+                          clang::noteBottomOfStack();
                           WithContext BGContext(std::move(Ctx));
                           Queue.work([&] { Rebuilder.idle(); });
                         });
   }
 }
 
 BackgroundIndex::~BackgroundIndex() {
   stop();

clang-tools-extra/clangd/test/infinite-instantiation.test

+// RUN: cp %s %t.cpp
+// RUN: not clangd -check=%t.cpp 2>&1 | FileCheck -strict-whitespace %s
+
+// CHECK: [template_recursion_depth_exceeded]
+
+template <typename... T>
+constexpr int f(T... args) {
+  return f(0, args...);
+}
+
+int main() {
+  auto i = f();
+}

clang-tools-extra/clangd/tool/ClangdMain.cpp

 #include "index/Merge.h"
 #include "index/ProjectAware.h"
 #include "index/remote/Client.h"
 #include "support/Path.h"
 #include "support/Shutdown.h"
 #include "support/ThreadCrashReporter.h"
 #include "support/ThreadsafeFS.h"
 #include "support/Trace.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Format/Format.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/Process.h"
 #include "llvm/Support/Program.h"

 
 enum class ErrorResultCode : int {
   NoShutdownRequest = 1,
   CantRunAsXPCService = 2,
   CheckFailed = 3
 };
 
 int clangdMain(int argc, char *argv[]) {
+  // Clang could run on the main thread. e.g., when the flag '-check' or '-sync'
+  // is enabled.
+  clang::noteBottomOfStack();
   llvm::InitializeAllTargetInfos();
   llvm::sys::PrintStackTraceOnErrorSignal(argv[0]);
   llvm::sys::AddSignalHandler(
       [](void *) {
         ThreadCrashReporter::runCrashHandlers();
         // Ensure ThreadCrashReporter and PrintStackTrace output is visible.
         llvm::errs().flush();
       },

clang/lib/Frontend/FrontendAction.cpp

 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclGroup.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileEntry.h"
 #include "clang/Basic/LangStandard.h"
 #include "clang/Basic/Sarif.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Frontend/ASTUnit.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendDiagnostic.h"
 #include "clang/Frontend/FrontendPluginRegistry.h"
 #include "clang/Frontend/LayoutOverrideSource.h"
 #include "clang/Frontend/MultiplexConsumer.h"
 #include "clang/Frontend/SARIFDiagnosticPrinter.h"
 #include "clang/Frontend/Utils.h"

 //===----------------------------------------------------------------------===//
 // Utility Actions
 //===----------------------------------------------------------------------===//
 
 void ASTFrontendAction::ExecuteAction() {
   CompilerInstance &CI = getCompilerInstance();
   if (!CI.hasPreprocessor())
     return;
+  // This is a fallback: If the client forgets to invoke this, we mark the
+  // current stack as the bottom. Though not optimal, this could help prevent
+  // stack overflow during deep recursion.
+  clang::noteBottomOfStack();
 
   // FIXME: Move the truncation aspect of this into Sema, we delayed this till
   // here so the source manager would be initialized.
   if (hasCodeCompletionSupport() &&
       !CI.getFrontendOpts().CodeCompletionAt.FileName.empty())
     CI.createCodeCompletionConsumer();
 
   // Use a code completion consumer?