Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize local.get stack occurrences #809

Closed
Robbepop opened this issue Nov 25, 2023 · 0 comments · Fixed by #843
Closed

Optimize local.get stack occurrences #809

Robbepop opened this issue Nov 25, 2023 · 0 comments · Fixed by #843
Labels
optimization An performance optimization issue. register-machine A work item for the register-machine engine.

Comments

@Robbepop
Copy link
Member

In the new wasmi register-machine translation we have to preserve values of local.get x registers if they are on the stack while an incoming local.set x or local.tee x overwrites the value of local x. In order to preserve the value of the local x we have to query the current stack for all occurrences of local x and replace them with local y where y refers to a register in the preservation register space.

The register preservation is explained a bit here: #808

In order to safe guard wasmi against malicious attackers it is important to make this stack query as fast and attacker resistant as possible. A naive implementation would simply query the actual stack for local x and replace them with local y. Note that this requires iteration through the entire value stack which can be big. For some sequences of Wasm bytecodes this falls apart quickly and would deteriorate wasmi compilation performance. I.e. this would be attackable. In order to safeguard wasmi against those kinds of attack we instead store occurrences of each local x into a separate data structure which we simply called LocalRefs.

Link: https://github.com/paritytech/wasmi/blob/80e1d212a26da8950f11fa6c0812bcc70661c3ee/crates/wasmi/src/engine/regmach/translator/stack/provider.rs#L193

Once we want to replace all stack occurrences of local x with local y we instead drain the accumulated occurrences via LocalRefs which prevent us from having to iterate through the entire value stack but only adjust those items on the value stack that are actually required to be adjusted.
While this works this also comes with the downside of having to maintain this additional data structure and keep it in sync with the value stack which is costly.
Ideally we could optimize the LocalRefs data structure further since right now it is quite simple or we could use the cheaper attackable algorith up to a point where we deem it "safe" to do so, e.g. when the value stack is still quite small which usually is the case for non malicious Wasm programs.

@Robbepop Robbepop added optimization An performance optimization issue. register-machine A work item for the register-machine engine. labels Nov 25, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
optimization An performance optimization issue. register-machine A work item for the register-machine engine.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant