Stream: git-wasmtime

Topic: wasmtime / issue #4924 Memoize `can_optimize_var_lookup`

Wasmtime GitHub notifications bot (Sep 19 2022 at 15:23):

adambratschikaye commented on issue #4924:

Looks like @fitzgen makes the most sense for review? I don't seem to be able to assign a reviewer though.

Wasmtime GitHub notifications bot (Sep 20 2022 at 07:49):

adambratschikaye commented on issue #4924:

Thanks @abrown and @fitzgen!

Wasmtime GitHub notifications bot (Sep 20 2022 at 23:00):

jameysharp commented on issue #4924:

This PR apparently can cause excessive memory consumption: see #4931 for a fuzz input causing use_var_nonlocal to attempt to allocate 3GiB for the self.calls vector. I suspect this is effectively an infinite loop, but the control flow is obscured by the state machine and heap-based recursion in SSABuilder. I'm very much in favor of removing quadratic behavior but I think we may need to revert this PR and think harder about what the invariants are supposed to be in the SSABuilder. Right now I find that whole source file confusing.

I haven't confirmed the root cause, but here's what I believe is happening. There's no guarantee that the blocks which can_optimize_var_lookup examines are sealed, which means that it's possible to add more predecessors to them afterward. So let's say it's called once on a block which doesn't have any predecessors yet, and a result of true is saved in the memo-table. Then exactly one predecessor is added that causes it to be part of a cycle, and then this function is called again. Now the un-memoized version would change to returning false, but the memoized version still returns true.

This wouldn't be as visible if not for another issue: use_var_nonlocal calls can_optimize_var_lookup every time, but only uses its result if the current block is sealed. Without memoizing, this is a waste of time for unsealed blocks but has no effect on correctness. If this were fixed, the above issue would be less likely to happen because we'd only update the memo-table if at least the initial block were sealed. However, I don't think that would fix the bug.

Also worth noting: I think this is hard to trigger from Wasmtime because if I recall correctly cranelift-wasm tries to seal blocks as soon as possible. That said, I bet there exists some wasm input that would still hit this bug. By contrast, the Cranelift fuzzers don't seal blocks until the whole function is built, so it's much easier to hit this bug there.

I think we might be able to fix this by keeping track of which blocks aren't currently part of a cycle, but doing it proactively in declare_block_predecessor instead of memoizing can_optimize_var_lookup.

Wasmtime GitHub notifications bot (Sep 21 2022 at 07:44):

adambratschikaye commented on issue #4924:

Oh shoot. I didn't realize the graph was being modified in between these calls to can_optimize_var_lookup and it definitely doesn't make sense to memoize if that's the case. I can look into the declare_block_predecessor suggestion.

Wasmtime GitHub notifications bot (Sep 21 2022 at 15:15):

jameysharp commented on issue #4924:

I have a patch mostly put together for that idea, but it wasn't passing the test suite yet when I had to stop for the day yesterday. I feel like it should work out though. We'll see!

Wasmtime GitHub notifications bot (Sep 21 2022 at 16:13):

fitzgen commented on issue #4924:

Reverting in https://github.com/bytecodealliance/wasmtime/pull/4937 until we figure out a proper fix for the original performance bug.

Last updated: Nov 22 2024 at 16:03 UTC