[wgsl-in] Enforce WGSL statement nesting depth limit

[hcsch]

A program like the following

fn f() {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{

will cause naga to overflow the stack as it recurses in
https://github.com/gfx-rs/naga/blob/db845347f23f3a00add894d38cf62d28f47669ed/src/front/wgsl/mod.rs#L2987-L3012

There should probably be some arbitrary but fixed limit to nesting which is checked with a counter. Programs exceeding that should cause naga to fail safely with an appropriate error message.

Edit: Since this fails at a depth of ~230 for me, I'd suggest going for something like 64 (which is already pretty ridiculous anyways, but I think nobody should be complaining with 64, at least not about it being too little).

[kvark]

Related to gpuweb/gpuweb#1959 (comment)

[hcsch]

Hmm... that lists a minimum limit of 1023 for control flow. If 230 empty blocks already cause an overflow, some optimizations may be needed (since I assume translation of SPIR-V to WGSL should support these kind of cases below the minimum limits).
Edit: and/or a bump of the max stack size.

[kvark]

Did you try running in release? This makes a big difference to our Metal backend.

[hcsch]

Did you try running in release? This makes a big difference to our Metal backend.

Hmm when running naga-cli built in release mode, the even 4096 and more nested blocks don't really cause an issue. Running cargo fuzz run --release wgsl_parser however will still finds stack-overflows for relatively "small" nesting depths. I guess that might have something to do with code instrumentation or something similar that cargo-fuzz / libFuzzer / ASan does.

(edit: I kinda should have thought of trying release mode, thanks for reminding me btw.)

[kvark]

We can proceed in one of the 2 ways:

1. try to come up with a restriction/limit that we'd add to WGSL spec if other parties agree
2. rewrite the parser to avoid using the stack directly. I wonder how this would turn out

[hcsch]

With regards to the first point, since WGSL is meant to translate well into SPIR-V, it'd probably be best to just adapt the limits of that as good as possible.

With regards to the second point, I think that that might be quite a bit of an endeavor, if it is possible at all, since certain parts of the grammar inherently require the use of a stack, like blocks and expressions (be that through recursion or more directly).
I suppose the reduction of stack memory usage is most likely best done looking at the output of some profiling tool (though I haven't looked into profiling stack memory usage yet).

Do you already have any particular ideas regarding how such a rewrite could be accomplished / in what way the code would be structured differently from the current code? I'd be really quite interested in that, as in my mind currently parsing is rather strongly associated with recursive parsing functions mimicking the grammar of the language, making use of the call stack for context and partial results. Perhaps a more direct use of a dedicated stack on the heap?

[kvark]

With regards to the first point, since WGSL is meant to translate well into SPIR-V, it'd probably be best to just adapt the limits of that as good as possible.

It's just that there is no direct mapping between a WGSL block and any limits in SPIR-V, if I understand correctly.

Perhaps a more direct use of a dedicated stack on the heap?

Yes, that would be a dedicated stack on the heap.

[jimblandy]

It'd be nice to know whether this even happens any more in the new front end.

[jimblandy]

I reproduced this on Linux with:

fn f() {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{

[schell]

I hit this with a shader generated with rust-gpu that does a lot of bounds checking and hence has a lot of nesting. Is there any movement on this ticket?

[teoxoy]

How did you hit this with rust-gpu? It happened in the SPIR-V frontend?

[schell]

Heya @teoxoy - It actually happened in the WGSL frontend. I have a test that takes all of my shaders generated by rust-gpu, uses naga to convert them to WGSL and then uses naga again to validate that WGSL. During the last step is where I hit this stack overflow - when naga is validating the WGSL it previously generated. Here is a link to that test, just in case :)

[jimblandy]

WGSL says:

Maximum nesting depth of brace-enclosed statements in a function: 127

If we enforced this limit, I don't think we would blow the stack.

[jimblandy]

WGSL doesn't seem to specify a limit on expression nesting depth, but given that lowering does recurse, Naga may need to impose its own limit. I think this is permitted by the spec as an uncategorized error.

[jimblandy]

Bumping priority as this is a blocker for fuzzing the WGSL front end.

[pyoor]

Running the wgsl_fuzzer triggers a related crash:

==2823932==ERROR: AddressSanitizer: stack-overflow on address 0x7ffc74ff3ba0 (pc 0x63f6c20f48cf bp 0x7ffc74ff44f0 sp 0x7ffc74ff3ba0 T0)
    #0 0x63f6c20f48cf in naga::front::wgsl::parse::Parser::primary_expression::h23ae97a865c14d96 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs
    #1 0x63f6c20ff378 in naga::front::wgsl::parse::Parser::singular_expression::ha0c517ce9764f3ce /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:781:28
    #2 0x63f6c20fbc15 in naga::front::wgsl::parse::Parser::unary_expression::hb636bf585a0be0a9 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:766:18
    #3 0x63f6c20d7425 in naga::front::wgsl::parse::Parser::equality_expression::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::he78b666f61240ed3 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:852:62
    #4 0x63f6c20d7425 in naga::front::wgsl::parse::ExpressionContext::parse_binary_op::h38086c80b9e3d6e9 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:69:31
    #5 0x63f6c20d5f08 in naga::front::wgsl::parse::Parser::equality_expression::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::h2ed5545a487d0ad4 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:838:41
    #6 0x63f6c20d5f08 in naga::front::wgsl::parse::ExpressionContext::parse_binary_op::h3240ab99446cde8c /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:69:31
    #7 0x63f6c20d8908 in naga::front::wgsl::parse::Parser::equality_expression::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::h4d27254f83976e56 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:827:33
    #8 0x63f6c20d8908 in naga::front::wgsl::parse::ExpressionContext::parse_binary_op::h408c8157d12b5582 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:69:31
    #9 0x63f6c20df105 in naga::front::wgsl::parse::Parser::equality_expression::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::h5bb4c116f308755c /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:814:25
    #10 0x63f6c20df105 in naga::front::wgsl::parse::ExpressionContext::parse_binary_op::hc13ca6ee4d636ac6 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:69:31
    #11 0x63f6c20db2b8 in naga::front::wgsl::parse::Parser::equality_expression::_$u7b$$u7b$closure$u7d$$u7d$::he0b7c15779df58ec /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:803:17
    #12 0x63f6c20db2b8 in naga::front::wgsl::parse::ExpressionContext::parse_binary_op::h4ed0251affb97fce /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:69:31
    #13 0x63f6c20d4a5d in naga::front::wgsl::parse::Parser::equality_expression::h25fc839d0c1de10b /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:794:9
    #14 0x63f6c20d4a5d in naga::front::wgsl::parse::Parser::general_expression_with_span::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::hef20e571d15ec2c8 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:923:49
    #15 0x63f6c20d4a5d in naga::front::wgsl::parse::ExpressionContext::parse_binary_op::h188674b6aa4fbb1b /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:69:31
    #16 0x63f6c20d9e0d in naga::front::wgsl::parse::Parser::general_expression_with_span::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::he1a39487ac9ddba9 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:914:41
    #17 0x63f6c20d9e0d in naga::front::wgsl::parse::ExpressionContext::parse_binary_op::h479c23b6cacdbdcd /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:69:31
    #18 0x63f6c20dc7bd in naga::front::wgsl::parse::Parser::general_expression_with_span::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::h3333e466fcb17dd5 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:904:33
    #19 0x63f6c20dc7bd in naga::front::wgsl::parse::ExpressionContext::parse_binary_op::h720587f8be5ad7f9 /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:69:31
    #20 0x63f6c20d35cd in naga::front::wgsl::parse::Parser::general_expression_with_span::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::h719b15e20891d36a /home/jkratzer/working/wgpu/naga/src/front/wgsl/parse/mod.rs:896:25

wgsl_minimized_crash.zip

[ErichDonGubler]

Updated source location for recursion between statements and blocks:

wgpu/naga/src/front/wgsl/parse/mod.rs

Lines 1630 to 1638 in 9f91c95

	(Token::Paren('{'), _) => {
	let (inner, span) = self.block(lexer, ctx)?;
	block.stmts.push(ast::Statement {
	kind: ast::StatementKind::Block(inner),
	span,
	});
	self.pop_rule_span(lexer);
	return Ok(());
	}

[jimblandy]

Posting some answers to questions asked in Mozilla-private chat:

• We should ideally support limits higher than those given in the spec. This will let us avoid having to think about off-by-one errors.
• At the moment, our Rust stack frames are too large to support the limits given. We should file a follow-up issue for that. There are ways to restructure the parser that should eliminate this problem. However, it seems that folks are going to suggest lowering those limits anyway: gpuweb/cts@34d6ab9 It seems like the limits aimed for there are actually within our reach, so maybe we'll be able to close our issue easily.
• What the fuzzers need is an error instead of a crash. So for the time being, we should simply enforce a lower limit, say, 64, even though that's not compliant with today's spec.