thread 'main' has overflowed its stack when file has over 250 nested if statements

[StoneCypher]

Hi. I'm trying to get my library to support deno.

For reasons I don't understand, when I import my library in deno, it overflows the stack. It's fine in the browser, though, or in node if you use dynamic import and change the extension.

Also happens with direct binding (that is, no * as.)

It's immediate and there are no apparent diagnostics.

I recognize that I might sound a little extreme when I say this, but I'm nervously concerned there might be a portability bug in deno. If not, alternately, there might be a resource ceiling on the stack that is significantly lower than in browsers and node. There are a number of other people claiming this is happening, and every single one of them is a Windows user. See #13196, #11356, #9752, and #5848.

Particularly interestingly, #9752 appears to treat this as a bug that was fixed upstream seven months ago.

On the other hand, there's a solid chance that I'm doing it wrong and making some stupid mistake I just don't understand.

You can see a reproduction, if you're interested, by pulling the branch ReattemptDenoSupport from https://github.com/StoneCypher/jssm/tree/ReattemptDenoSupport and running npm install && npm run build, then opening deno and issuing import * as jssm from "./dist/deno/jssm.deno-esm.js".

Sorry, I know it's not cool to put npm instructions in here. I'm trying to fix it to be on deno.land and I'll update this as soon as I get what's going on. It's hard to know if I'm using deno.land correctly when I haven't got my library working as expected.

How does someone go about diagnosing something like this?

[kitsonk]

I am unable to reproduce with:

deno 1.23.3 (release, x86_64-apple-darwin)
v8 10.4.132.8
typescript 4.7.4

I get:

❯ deno                        
Deno 1.23.3
exit using ctrl+d or close()
> import * as jssm from "./dist/deno/jssm.deno-esm.js"
undefined

Commit from the ReattemptDenoSupport branch: d29b22488e10f3ee798b7ecb23598654fe987fb8

Can you give the full output of deno --version?

[StoneCypher]

I believe this to be Windows specific. Several of the attached issues have people saying they can repro on Windows but not on Mac.

john@DESKTOP-26H4050 MINGW64 ~/projects/jssm (main)
$ deno --version
deno 1.23.1 (release, x86_64-pc-windows-msvc)
v8 10.4.132.8
typescript 4.7.2

I appreciate the help.

[StoneCypher]

I'm also happy to provide debug dumps or whatever; this isn't a high security machine.

I just don't know how to under deno. Kind of a noob

[kitsonk]

@dsherret can you reproduce?

[dsherret]

Yup, it occurs with swc parsing a large file and it goes very deep in the stack then overflows.

It occurs on the ./dist/deno/jssm.deno-esm.js file.

Looking at this file, it has some crazy deep nesting.

I would recommend refactoring the code for it to not nest so deeply and that will fix it.

[StoneCypher]

It's a generated parser output that works fine in Netscape Navigator 4 from 1994.

The parser generator in question has been dead for nine years. "Refactoring" is not an option.

This is the single most common parser generator in the Javascript world - peg.js - which owns more than 80% of the total parser market.

This nesting is not even slightly deep, compared to the many common uses of this tool in wide circulation.

I would appeal to you that this is a genuinely important use case, and really should be supported. It is well within the legal language specification, and is safe on 25 year old browsers.

[StoneCypher]

Thank you for taking the time to look into this, and being willing to discuss.

If necessary, I suppose I could fork the dead tool and manually test it then retool it, but that's a multiple year commitment.

[StoneCypher]

I would also note that as I understand it, you are an implementation of v8, and v8 has supported this specific parser in its older incarnations for more than ten years

So I'm wading way out into the guess ocean here, but I believe this suggests that deno has simply configured something with stricter resource constraints

If that's the case, is there a downside to permitting resource usage on par with obsolete instances of the same engine in circulation? (Maybe there is. I'm very new and naive here. I would like to learn.)

[kitsonk]

I would also note that as I understand it, you are an implementation of v8, and v8 has supported this specific parser in its older incarnations for more than ten years

We use a Rust library to do dependency analysis on code, which parses the JavaScript, and appears to have challenges with deeply nested if statements. So while V8 can run this, the dependency analysis cannot parse it without overflowing the stack. It is arguable that it is an issue with swc, as while somewhat incredible, there are clearly instances of >250 nested if statements in the wild, as well as the behaviour is different between windows and other situations. Ideally swc shouldn't overflow the stack in such an unsafe way.

[StoneCypher]

as while somewhat incredible, there are clearly instances of >250 nested if statements in the wild

this is actually very common with non-lens parser generators in essentially every language. this is what antlr, bison, yacc, etc do as well. you use this kind of stuff every single day.

[StoneCypher]

direct-compile regular expression engines that aren't advanced enough to be finite state machines also very frequently take this strategy

this is also how github's highlighting stuff works, so we're using this stuff to talk about this stuff 😅

parseception

[KevinCathcart]

While fixing swc to not use this much stack for such parsers is the arguable correct fix, I believe Deno can can avoid this (and other stack related crashes) on Windows pretty easily.

On Windows the main thread has a maximum stack size of 1 MiB by default, while Linux and MacOS will let main thread to grow up to 8MiB by default (controlled by ulimit). There are some differences with respect to spawning other threads on each platform, but all let you specify a custom maximum stack size. Threads spawned by Rust code will use a maximum stack size of 2MiB by default, regardless of the OS default, but this does not apply to the main thread.

Increasing the default stack size on Windows is possible as a linker flag. Increasing the default to 8MiB would bring Windows in line with Linux and MacOS's default ulimit and would not be unreasonable. While window's strict memory accounting often makes it act differently than Linux, for this purpose Windows actually acts more like most Linux allocations do (explained later), and thus this bigger size will not make the program use more memory, unless/until the stack is used enough to grow to that size.

The only real downside here is that changing the default stack size will also change the default maximum stack size for threads created by non-rust code, but that really is not an issue, as it is not memory but only reserved virtual address space. For x64 this really only means a few extra page table entries are created per natively created thread. In a 32 bit program the extra address space reserved could potentially be a concern, but Deno only supports x64 on windows anyway, and even if it did, it would need many dozens of threads to realistically be an issue.

Lastly Deno is already increasing the stack size for debug builds on Windows (see .cargo/config.toml), so switching to an 8MiB default stack reservation size for all Windows builds instead of only debug builds is actually a simplification, and would avoid a bunch of cases where things can crash from stack limits on Windows while working on Linux and MacOS.

---

More about how stack works on Windows:

While Windows' strict memory accounting normally makes it work differently from Linux, for stack size windows actually behaves similarly to most allocations in Linux, where a larger maximum stack size does not make it use more memory unless the stack grows that big.

This is because Windows only reserves the address space, for the full stack, but does not initially map it to memory (which requires "committing" it). Instead it commits memory as the stack grows, which does mean that the program can crash with a stack overflow before reaching the max stack size, but only if Windows does not have enough physical memory plus swap to allow for more committed memory. To allow programs to be sure they won't crash from not enough stack, Windows offers a second value that determines the minimum committed stack size.

When creating other threads on windows, you can specify a minimum committed stack size to override the default, and if this minimum is greater than the default maximum, the thread will be created with a larger maximum to accommodate. You can instead use the STACK_SIZE_PARAM_IS_A_RESERVATION flag when creating a thread to set the maximum stack size for a new thread, without forcing that memory to be fully committed. (Rust does this when creating threads.)

Hope this helps.

[StoneCypher]

That probably gets me out of the fire, but larger parsers would still be stuck

Is a dynamic stack an option?

[KevinCathcart]

I've heard that even with setting the stack size limit to unlimited on macOS, it will limit it at 64 MB for the main thread. Windows does not have any such unlimited concept for OS managed stacks. On Linux, if ulimit for stacks is set to unlimited, the main thread stack can continue to grow indefinitely, until to runs into part of the address space already being used (whether by malloc, mmaped files, the stack for some other thread, etc).

It might theoretically be possible to have MacOS and Windows use a userspace managed stack instead of a kernel managed stack. In that case, it could be allowed to grow to an indeterminate size not unlike Linux's kernel manage stack can if the default limit is turned off, but that involves some rather hairy low level memory management code that I'm not so sure that the Deno team would want.

The main culprit of stack issues seems to be swc (https://github.com/swc-project/swc). swc uses a recursive descent parser implemented with recursion, which inherently means there will be some limit to the depth it can reach with any fixed stack size. I cannot see them changing this approach. They could probably reduce how much stack is used by each level of nesting, which may become enough for realistically sized parsers. Otherwise they would probably need to do something like use https://github.com/rust-lang/stacker to implement segmented stacks in the parser, which is how the rust compiler (rustc) avoids this very same problem.

Bumping the windows stack size is something the deno team can pretty easily do on their own. Fixing the problem for possible every possible parser is something the swc team would need to do. I'd suggest filing a bug over there that points to this bug. If you know of a PEG.js parser that generates output with a lot more nesting, it might not be a bad idea to link that too, so they can test against that too.

[StoneCypher]

Oof. Understood.

This honestly seems like a pretty severe limitation to me.

[StoneCypher]

upstream has closed this as needing a reproduction

i did the best i could to create one, but i wasn't able to

[littledivy]

We already increase the stack size on Windows but only for debug builds. Maybe we should do this on release builds too.

deno/.cargo/config.toml

Lines 9 to 10 in 1727153

	# increase the stack size to prevent swc overflowing the stack in debug
	"link-arg=/STACK:2097152",

Actionable items:

• Make a simple swc reproduction of the issue.
• Increase stack size on Windows to circumvent the issue.

[StoneCypher]

as noted above, the wall has already been pushed back three times

this is a common structure for generated code, and this grammar is actually quite small; it seems almost certain that this will end up being hit again

[StoneCypher]

i mean, it'd probably get me through my current problem, so I won't turn it down, but I think probably it will re-emerge within a year, looking at the timings of the previous wall pushes

[StoneCypher]

@littledivy - is there some way I can pitch in here? I'd really like to get through this

I haven't released on Deno yet. 😂

[littledivy]

There are actionable items in my previous comment that you can try out and send a PR. This is not a priority for the core team at the moment.

[dsherret]

@littledivy I'm not sure we should increase the stack size any more. Also, contrary to what the config indicates that gets applied to the release build as well due to a bug in cargo.

Make a simple swc reproduction of the issue.

I think we should do this.

[StoneCypher]

There was a reproduction. The upstream tool closed it.

[StoneCypher]

@dsherret - So, it sounds like almost all generated parsers will never run in Deno, then? 😥

[dsherret]

The reproduction was done using Deno swc-project/swc#5470 (comment)

It would need to be reproduced with just swc.

[KevinCathcart]

Testing the with native "swcx compile" command and the module in question, and it crashed with stack overflow in versions 1.3.3 and older. version 1.3.4 panics about accessing a thread local variable. version 1.3.5 and later work without crashing.

If I test the latest deno (1.28.3), I am able to do import * as jssm from "https://raw.githubusercontent.com/StoneCypher/jssm/Reat temptDenoSupport/dist/deno/jssm.deno-esm.js" without issue. So this may already be resolved at least for this particular case.

[rijenkii]

I may have generated a reproduction for this issue, see swc-project/swc#6813.

[StoneCypher]

I may have generated a reproduction for this issue, see swc-project/swc#6813.

Thank you very much. I tried something like this and I didn't get results, but I'm neither an swc, a deno, nor a rust person, so I wasn't able to figure out why

[rijenkii]

So, the swc bug was just closed and some version of swc was released with the bugfix. Seems like it uses stacker now, as suggested.

[StoneCypher]

Confirmed fixed. Thank you.