Stream: git-wasmtime

Topic: wasmtime / issue #9015 Should a "pointer type" be added t...

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 00:24):

alexcrichton added the cranelift label to Issue #9015.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 00:24):

alexcrichton opened issue #9015:

Today Cranelift does not have a type for pointers. Instead it has i32 and i64 and you're supposed to use the right one for 32 and 64-bit platforms. This is a simplification over LLVM, for example, which has a ptr type which is required for loads/stores. The downside to this, however, is that Cranelift and its backends do not know what's a pointer and what's not.

Why would Cranelift want a pointer type when it's done well enough without it? The Pulley interpreter recently added is going to add a new backend to Cranelift which emits pulley bytecode. This bytecode, when run, will violate Rust's pointer provenance rules.

Rust pointer provenance basically says that you can't convert an integer into a pointer. Pulley bytecode, however, will perform an operation that looks like:

The final load here is a load from a pointer which is created through an int-to-pointer conversion. Provenance in Rust does not allow that. No matter how we slice this we cannot get around it because the source of the problem is the original load. The original load of the pointer was a load of an integer, not a pointer, which means that in Rust-land the "provenance" of this pointer is never established. To correctly work with Rust's provenance the original load of a pointer has to map, in Rust, to a load of a pointer.

Another problem for Pully is pointer arithmetic. Cranelift models pointer arithmetic as integer operations with an i64 type for a 64-bit platform. This means that Pulley will calculate some addresses (like above) by adding two numbers together. To correctly respect provenance in Rust it must be known which of these integers is a pointer. Pulley and the Cranelift backend, however, have no knowledge of which is a pointer (and it's not valid to add two pointers together).

All-in-all, if Pulley wants to respect Rust's "strict provenance", then the current design of Cranelift is not suitable. Cranelift will be required to have a pointer type of some kind which makes its way through to the backend so the bytecode iteslf can look different if a pointer is being loaded or a 64-bit integer is being loaded.

What would a pointer type in Cranelift look like?

A straw-proposal would be to add p32 and p64 types. Validation requires that the current target only uses either p32 or p64 depending on the bit-width of the target. This would retain the ability to easily calculate the size of a type (without the context of a TargetIsa).

Existing instructions like load and store would change to taking a pNN address instead of an integral address. Existing polymorphic instructions like load and store would change to support loading/storing pointers as well.

At least one new instruction would be required for pointer arithmetic, something like padd (or maybe ptradd) to byte offset forwards-and-back from a pointer.

The bitcast instruction would need to be updated as well to support pointer-to-integer casts.

The Pulley backend would not support a bitcast from an integer-to-a-pointer at all, but other backends could support this to assist transitioning backends such as the Rustc Cranelift backend.

Is this necessary?

I'm honestly not sure if this is necessary to do. It is a fact that WebAssembly modules cannot be run in MIRI through Pulley with -Zmiri-strict-provenance. They will run however with -Zmiri-permissive-provenance. What I do not fully understand is, looking into the future, whether requiring permissive provenance is going to be UB or not. Or in other words will int-to-pointer casts become UB in Rust in the future (or LLVM?)

If permissive provenance is always allowed in Rust, even into the future, then it may not be worth this undertaking. It's likely going to be quite nontrivial to add a pointer type to Cranelift. If, however, permissive provenance will become UB in Rust in the future it's probably best to start thinking about this now about how it might be added to Cranelift.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 00:27):

alexcrichton commented on issue #9015:

For those who aren't the most familiar with provenance, which is me included, I can also elaborate how I think about it. I believe that on CHERI pointers are 128-bits large with a 64-bit address and a 64-bit "thing". I don't know what this "thing" is but I think of it as the provenance of the pointer. This crystallizes to me how the basic operation of "cast an integer to a pointer" cannot work with strict provenance because there is no way to materialize the "thing". Additionally loads/stores from memory must understand they're operating on a pointer because the "thing" must be stored into memory.

On other architectures, e.g. everything supported by Cranelift, the "thing" is actually zero-sized and pointers a 64-bits large. Nevertheless this is part of the optimization and memory model of Rust and the "thing" is also something known at compile-time and optimized around.

Not sure if that'll help, but it's at least how I think about provenance and helps me simplify and understand a lot of MIRI issues about the lack of provenance thereof.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 00:50):

cfallin commented on issue #9015:

I wrote a long writeup on my thoughts on pointer provenance here last year; tl;dr is that I don't think it's a good idea to add this notion to Cranelift. The key bit is:

In particular, substituting a pointer with an expression that evaluates to that pointer, but is not that pointer, violates pointer provenance but I worry it may arise as emergent behavior when optimizations compose. p0 + (p1 - p0) seems silly, but mid-end rules that rewrite integer expressions are quite reasonable, and in general we consider these correct as long as they result in code that computes the same integer. In a pointer-provenance world, we now need to have a "may be a pointer?" analysis, and exclude any possibly-pointer SSA values from any rewrites that may "mix in" another pointer. (Alternately, we could come up with a set metarules around how we write our rules, such that no legal pointer manipulation can be rewritten into an illegal one. But my brain hurts just thinking about that.)

It also precludes some rewrites that the producer might do. For example, in a pointer-provenance world, pointers can't be stored to memory. Or if they are, we need an escape analysis and a "has escaped, could alias anything" state in addition to our "provenance is strictly tracked" state for each storage location. One might argue that a producer should be careful about this but consider: this means that we can no longer write general code like "write all arguments to memory and call a trampoline". Or even write a producer that, e.g., directly compiles stack-based bytecode to use a value stack in memory: as soon as the opcode for "get scratch space" compiles to a stack_addr and a store of that addr, it has lost its provenance and is just bytes in memory. Again, escape analysis could catch this, but it's just more complexity.

Aside from all that, adding additional types to Cranelift imposes a large and ongoing tax as we write all of our rules: we have to consider how they apply across the cross-product of types and opcodes. Already ref-types (r64/r32) are problematic and raise questions, and @fitzgen and others are making efforts to hoist stackmaps up the pipeline so we don't need Cranelift to know about them.

Where does that leave Pulley wrt pointer provenance? I agree with you that the primitive that Pulley provides -- raw read/write access to the process's memory -- is fundamentally beneath the level of Rust-with-pointer-provenance; but I think that this is as it must be, as long as the rest of the engine is built assuming it is producing JIT code. Said another way: Pulley provides the same thing that other compilation targets do for Wasmtime, namely, raw load/store instructions that can access data structures, including data structures touched by runtime code. We don't have or ensure pointer provenance carefully throughout the native JIT-code that we generate; so fundamentally it would be a large rearchitecting to ensure we carry that provenance through Wasmtime's codegen. (How even does that work for something with dynamic layout like the vmctx struct, where there is no corresponding static Rust type with a pointer-typed field we store to and load from?)

As a last note I guess I'm curious what the practical implications here are. Pointer provenance is... part of the language semantics today? Planned to be part of them tomorrow? If the idea is that eventually there might be deeper alias analysis and optimizations based on it, I would hope we would be able to find the appropriate barrier mechanisms to prevent optimization across these primitives, because we'll need the same such barriers to prevent optimizations across calls to JIT code (that similarly may lose provenance) as well!

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 01:00):

cfallin commented on issue #9015:

And as a practical example of an optimization I have personally written that violates pointer provenance (in Wasm, where pointers are also semantically just integers and perfectly well-defined as such): in weval here, I wrote a pass that turns a bunch of constant-offset values like p, p+k1, p+k1-k2, ... into uses of one canonical base plus a positive offset. This came up in e.g. uses of the shadow stack with structs and sub-structs. This freely moves "across different objects" in memory, but as long as pointers are just integers (and in Wasm they are, and in Cranelift they are, and on the native ISA they are, sighs of relief all around) the algebra is valid.

We could totally carry the caution through all our opt passes needed for provenance, but it is a big lift, is all I'm trying to say!

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 01:01):

cfallin edited a comment on issue #9015:

And as a practical example of an optimization I have personally written that violates pointer provenance (in Wasm, where pointers are also semantically just integers and perfectly well-defined as such): in weval here, I wrote a pass that turns a bunch of constant-offset values like p, p+k1, p+k1-k2, ... into uses of one canonical base plus a positive offset. This came up in e.g. uses of the shadow stack with structs and sub-structs, as well as uses of statically-known offsets on an operand stack. This freely moves "across different objects" in memory, but as long as pointers are just integers (and in Wasm they are, and in Cranelift they are, and on the native ISA they are, sighs of relief all around) the algebra is valid.

We could totally carry the caution through all our opt passes needed for provenance, but it is a big lift, is all I'm trying to say!

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 09:33):

bjorn3 commented on issue #9015:

I don't see how pointer types are necessary for Pulley if it is only used by Wasmtime. It can do an int2ptr cast before every memory operation and a ptr2int cast every time a pointer is put into a Pulley register. Each ptr2int cast will expose the provenance of the pointer and each int2ptr cast will pick the right exposed provenance to use. Only when you have to handle memory that itself can contain pointers with provenance (which wasm doesn't have) does this not work as loading a pointer directly as integer will never expose the provenance.

For CHERI and for better optimizations for cg_clif a pointer type would be very useful though.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 17:34):

alexcrichton commented on issue #9015:

I fear I may have led to some misunderstandings here. My worry is that if Rust does not allow permissive provenance, aka an int-to-ptr operation, then Pulley is impossible to work with its design today. My impressions is that strict provenance means that an int-to-ptr operation is never executed. If this is the future world of Rust then we must either (a) remove/redesign pulley or (b) add a pointer type to Cranelift.

To be clear I'm not saying we should add a pointer type to Cranelift because I think it's a good idea. I'm postulating here that we will be required to do so to work with strict provenance in Rust. I see no other possible solution to the problem in a world where int-to-pointer is a non-existent operation.

For example, in a pointer-provenance world, pointers can't be stored to memory.

This is an example of something I don't understand. No model would work at all if you couldn't store a pointer into memory, and I'm quite certain Rust's model for provenance supports this. MIRI seems to be quite rigorous about tracking this and understands that if you store a 64-bit integer to memory and load it as a pointer then it has no provenance.

This is what makes me think that there may be some misunderstanding about provenance? I think I'll put something on the next Cranelift agenda to talk more in depth about this as well. I'll continue to emphasize though that I do not know the future direction of Rust, and this entire proposal hinges on "Rust requires strict provenance". So if Rust doesn't require strict provenance then we're good here and Cranelift need not do anything.

adding additional types to Cranelift imposes a large and ongoing tax as we write all of our rules

I very much agree with this and is why I'm not saying we should do this today. I highlight this again here to emphasize that my current understanding of provenance is that we will simply not have a choice if Rust doesn't allow permissive provenance.

It can do an int2ptr cast before every memory operation and a ptr2int cast every time a pointer is put into a Pulley register

My current understanding is that emitting an int2ptr operation is a violation of strict provenance. I do not claim to be a provenance expert though so I could also be wrong in my interpretation. If this is the case though I don't think that this alternative would work?

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 17:52):

cfallin commented on issue #9015:

This is an example of something I don't understand. No model would work at all if you couldn't store a pointer into memory, and I'm quite certain Rust's model for provenance supports this. MIRI seems to be quite rigorous about tracking this and understands that if you store a 64-bit integer to memory and load it as a pointer then it has no provenance.

Note that the quote I gave was in the context of pointer provenance in Cranelift. One key distinction between Cranelift and Rust is that Cranelift does not have struct types: it cannot know that p points to a thing that, at offset 8, stores a *mut T. Rust on the other hand does have this strong typing, so provenance can be checked at store time (is this a valid *mut T with appropriate provenance?) and assumed at load time. But from the point of view of Cranelift, memory is "the Great Mixer" -- bytes go in, bytes come out -- and we'd need not only pointer types but struct types to maintain appropriate provenance. Note I'm not arguing this from a "Rust does this" basis but from a "this is necessary from first principles to know that the pointer came from the right place" basis -- otherwise, resynthesizing a pointer from 4 or 8 bytes in memory at some offset is no better than casting from an integer.

That led to my question around vmctx in particular: how do we keep miri happy with the dynamically-located fields in vmctx? Is there some sort of unsafe assert or assumption that, when we take offset K into pointer P (with some arbitrary dynamically-computed layout), and load it, we're promising the loaded bits have valid provenance? If so, there's our escape hatch. If not, it's the same problem as here.

My question around "how does JIT code fit into this" remains too, or I guess around FFI boundaries in general. If Rust can call code that doesn't have the same provenance guarantees, how does it make that safe? We can use whatever solution we have for that to do Pulley's loads/stores as well. In the worst case -- this would be silly, but as an example -- we could call out to helpers written in C that do the arbitrary loads/stores; from Rust's PoV that's no different than a call to JIT code, and will have the same potential side-effects.

Given that I don't think I'm seeing the link as so strong necessarily -- Rust chooses this path, we must change Cranelift. Definitely interested in talking more.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 18:11):

bjorn3 commented on issue #9015:

I think it is unlikely that rust will enforce strict provenance on any platform (except maybe CHERI, which is non-conformant in other ways anyway). The exact way exposed provenance works is not yet specified and it is harder to analyze for miri, so using strict provenance in your code is a way to have something that is guaranteed to work no matter what the rules for exposed provenance will turn out to be, but exposed provenance is not something that will be removed.

That led to my question around vmctx in particular: how do we keep miri happy with the dynamically-located fields in vmctx? Is there some sort of unsafe assert or assumption that, when we take offset K into pointer P (with some arbitrary dynamically-computed layout), and load it, we're promising the loaded bits have valid provenance? If so, there's our escape hatch. If not, it's the same problem as here.

You can ptr2int them before storing them in the vmctx so that when you load it as integer later you can int2ptr it as the provenance was exposed by the earlier ptr2int.

That is not to say I oppose the introduction of a pointer type in Cranelift. In fact I would like to have it for the purpose of better optimizations. I just don't think Pulley strictly needs it within the constrained context of Wasmtime. If Pulley were to be used with cg_clif (or some other compiler interfacing with native code that would actually benefit from Pulley), it would need pointers as cg_clif can't guarantee that every pointer that is used had a ptr2int operation applied to it before Pulley could do the int2ptr.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 18:27):

cfallin commented on issue #9015:

You can ptr2int them before storing them in the vmctx so that when you load it as integer later you can int2ptr it as the provenance was exposed by the earlier ptr2int.

That seems to be a reasonable answer to me then: Wasmtime itself cannot work under strict provenance without ptr2int and int2ptr because it uses structs with dynamically-computed layouts, without a corresponding static Rust type. So as long as we do that, we are already requiring the primitives that Pulley also needs to work. Does that square with your understanding @alexcrichton or am I missing a subtlety here (probably likely)?

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 18:42):

alexcrichton commented on issue #9015:

I asked on Zulip as well and got a similar confirmation that Rust is unlikely to ever require strict provenance, which from my perspective makes this whole issue moot since that just means that pulley will require permissive provenance which Rust will allow.

I don't know how Rust's model handles FFI which Cranelift-generated code effectively is, so I can't speak much to that. What I can say though is that Wasmtime and its tests that don't use Cranelift all pass under strict provenance today. I believe the requirement is that if you load a pointer from memory you were required to store a pointer there previously. Storing a 64-bit integer isn't sufficient, it had to have been a pointer store operation. In that sense I don't believe there's any issues with the vmctx because we always view fields in memory with the same type and load/store with the same type.

The strict provenance operation I'm worried about is that the Pulley backend of Cranelift will emit "load 64-bit integer, add offset, load another integer from this pointer". That's materializing a pointer out of thin air from an integer which works at the machine level of course but does not work with strict provenance. What I believe this means is that when we load/store from memory in the Pulley interpreter we'll have to use ptr::with_exposed_provenance at the very least. Where exactly we would call ptr::expose_provenance I'm not entirely sure, though.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 18:47):

bjorn3 commented on issue #9015:

I believe the requirement is that if you load a pointer from memory you were required to store a pointer there previously.

If you want to be able to dereference a pointer, it has to have valid provenance for the address of the pointer. Integers do not have provenance. If you load an integer value from a place where a pointer was stored or you load a pointer from a place where an integer was stored, you will get a value without provenance (that is in the integer load case just a plain address, and in the pointer load case a pointer which can't be dereferenced). If you want to load the value at the address pointed to by an integer, you have to use from_exposed_provenance (int2ptr), which will try to pick a random provenance which has been previously exposed, but will try to pick the provenance which avoids UB if doing so is possible. This requires the provenance to have been previously exposed using expose_provenance (ptr2int).

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 19:08):

alexcrichton closed issue #9015:

Today Cranelift does not have a type for pointers. Instead it has i32 and i64 and you're supposed to use the right one for 32 and 64-bit platforms. This is a simplification over LLVM, for example, which has a ptr type which is required for loads/stores. The downside to this, however, is that Cranelift and its backends do not know what's a pointer and what's not.

Why would Cranelift want a pointer type when it's done well enough without it? The Pulley interpreter recently added is going to add a new backend to Cranelift which emits pulley bytecode. This bytecode, when run, will violate Rust's pointer provenance rules.

Rust pointer provenance basically says that you can't convert an integer into a pointer. Pulley bytecode, however, will perform an operation that looks like:

The final load here is a load from a pointer which is created through an int-to-pointer conversion. Provenance in Rust does not allow that. No matter how we slice this we cannot get around it because the source of the problem is the original load. The original load of the pointer was a load of an integer, not a pointer, which means that in Rust-land the "provenance" of this pointer is never established. To correctly work with Rust's provenance the original load of a pointer has to map, in Rust, to a load of a pointer.

Another problem for Pully is pointer arithmetic. Cranelift models pointer arithmetic as integer operations with an i64 type for a 64-bit platform. This means that Pulley will calculate some addresses (like above) by adding two numbers together. To correctly respect provenance in Rust it must be known which of these integers is a pointer. Pulley and the Cranelift backend, however, have no knowledge of which is a pointer (and it's not valid to add two pointers together).

All-in-all, if Pulley wants to respect Rust's "strict provenance", then the current design of Cranelift is not suitable. Cranelift will be required to have a pointer type of some kind which makes its way through to the backend so the bytecode iteslf can look different if a pointer is being loaded or a 64-bit integer is being loaded.

What would a pointer type in Cranelift look like?

A straw-proposal would be to add p32 and p64 types. Validation requires that the current target only uses either p32 or p64 depending on the bit-width of the target. This would retain the ability to easily calculate the size of a type (without the context of a TargetIsa).

Existing instructions like load and store would change to taking a pNN address instead of an integral address. Existing polymorphic instructions like load and store would change to support loading/storing pointers as well.

At least one new instruction would be required for pointer arithmetic, something like padd (or maybe ptradd) to byte offset forwards-and-back from a pointer.

The bitcast instruction would need to be updated as well to support pointer-to-integer casts.

The Pulley backend would not support a bitcast from an integer-to-a-pointer at all, but other backends could support this to assist transitioning backends such as the Rustc Cranelift backend.

Is this necessary?

I'm honestly not sure if this is necessary to do. It is a fact that WebAssembly modules cannot be run in MIRI through Pulley with -Zmiri-strict-provenance. They will run however with -Zmiri-permissive-provenance. What I do not fully understand is, looking into the future, whether requiring permissive provenance is going to be UB or not. Or in other words will int-to-pointer casts become UB in Rust in the future (or LLVM?)

If permissive provenance is always allowed in Rust, even into the future, then it may not be worth this undertaking. It's likely going to be quite nontrivial to add a pointer type to Cranelift. If, however, permissive provenance will become UB in Rust in the future it's probably best to start thinking about this now about how it might be added to Cranelift.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 19:08):

alexcrichton commented on issue #9015:

Ok sounds good, thanks for the clarification!

So given all this I'm going to close this, but I'm going to open a separate issue for Pulley and using provenance correctly.

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 19:08):

cfallin commented on issue #9015:

I believe the requirement is that if you load a pointer from memory you were required to store a pointer there previously. Storing a 64-bit integer isn't sufficient, it had to have been a pointer store operation.

As a meta-comment, I guess I continue to be a little baffled (coming from the experience of working with alias analysis and similar things) on the distinction between the dynamic model here -- miri can presumably keep a metadata shadow on memory and track this -- and what an ahead-of-time compiler (rustc) can actually get out of this. It seems unlikely to me (?), and impossible in the general case, to statically model memory layout to prove that at offset K1 we stored a pointer so a load from K2 later has a provenance that ties it to that earlier pointer. Or in other words, I see how one could do this for static struct layouts but Wasmtime is truly dynamic here and K1 and K2 may or may not be equal at runtime, so there is nothing any optimization could ever do here (it could never actually connect up the provenance) -- imagine we store p1 and p2 at different vmctx slots, then load q1 and q2, does q2 get p1's or p2's provenance? If no static compiler can prove one or the other because it depends on dynamic data coming from outside the analysis scope, then nothing can be optimized using the provenance anyway.

(Said another way I guess I'm making a variant of the "but the compiler doesn't do this in practice" fallacy-argument that removes the fallacy by saying "from first principles, no compiler can ever do this in our situation"; which really points to the need to maintain the escape hatch in the language semantics)

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 19:08):

cfallin commented on issue #9015:

(ah sorry, raced with issue closing)

view this post on Zulip Wasmtime GitHub notifications bot (Jul 26 2024 at 19:10):

alexcrichton commented on issue #9015:

I suspect that you might be able to have a good discussion in the rust-lang/rust zulip with those questions? I don't feel confident enough to answer them myself other than what you already mention at the end of I think things are being set up for the compiler to take advantage of in the future perhaps

Last updated: Oct 23 2024 at 20:03 UTC