This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by zyounan on Aug 28 2023, 12:15 AM.

Details

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.

Diff Detail

Event Timeline

zyounan created this revision.Aug 28 2023, 12:15 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 28 2023, 12:15 AM
zyounan requested review of this revision.Aug 28 2023, 12:15 AM
ilya-biryukov added a comment.EditedAug 28 2023, 1:53 AM

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?

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?

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 added a subscriber: rsmith.Aug 28 2023, 7:51 AM

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. :)

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 updated this revision to Diff 554279.Aug 29 2023, 5:52 AM

Adopt the comments.

Herald added a project: Restricted Project. · View Herald TranscriptAug 29 2023, 5:52 AM
zyounan retitled this revision from [clangd] Record the stack bottom before building AST to [clang][clangd] Ensure the stack bottom before building AST.

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

zyounan updated this revision to Diff 554285.Aug 29 2023, 6:05 AM

Oops, something went wrong accidently.

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?)

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

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 updated this revision to Diff 554674.Aug 30 2023, 5:46 AM
zyounan marked an inline comment as done.

Address comment

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 added inline comments.Aug 31 2023, 11:27 AM
clang-tools-extra/clangd/support/Threading.cpp
102

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 updated this revision to Diff 555356.Sep 1 2023, 6:16 AM

Disperse the call over clangd tasks

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

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.

zyounan marked an inline comment as done.Sep 1 2023, 6:18 AM
sammccall accepted this revision.Sep 1 2023, 8:49 AM

Thanks! Sorry about the layering mess...

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

need to remove this include too :-)

This revision is now accepted and ready to land.Sep 1 2023, 8:49 AM
zyounan updated this revision to Diff 555577.Sep 2 2023, 3:50 AM
zyounan marked an inline comment as done.

Remove the stray header

zyounan edited the summary of this revision. (Show Details)Sep 2 2023, 3:52 AM
This revision was landed with ongoing or failed builds.Sep 2 2023, 3:53 AM
This revision was automatically updated to reflect the committed changes.