What about: Pointer-to-integer transmutes?
Opened this issue · 130 comments
Transmuting pointers to integers (i.e., not going through the regular cast) is a problem. This is demonstrated by the following silly example:
fn example(ptr: *const i32, cmp: usize) -> usize { unsafe {
let mut storage: usize = 0;
*(&mut storage as *mut _ as *mut *const i32) = ptr; // write at ptr type
let val = storage; // read at int type (0)
storage = val; // redundant write back (1)
external_function(&storage); // just making sure the value in `storage` can be observed
if val == cmp {
return cmp; // could exploit integer equivalence (2)
}
return 0;
} }Imagine executing this code on the Abstract Machine, taking into account that pointers have provenance, i.e., a ptr-to-int conversion loses information. Now what happens at point (0)? Here we read the data stored in storage at type usize. That data however is the ptr ptr, i.e., it has provenance. What should happen with that provenance at (0)?
- We could drop the provenance. That would basically mean that the load of
storageacts like an implicit ptr-to-int cast. The problem with this approach is that we cannot remove the redundant write at (1): the value invalis different from what is stored instorage, sincevalhas no provenance but theptrstored instoragedoes! This is basically another version of https://bugs.llvm.org/show_bug.cgi?id=34548: ptr-to-int casts are not NOPs, and a ptr-int-ptr roundtrip cannot be optimized away. If a load, like at (0), can perform a ptr-to-int cast, now the same concerns apply here. - We could preserve the provenance. Then, however, we end up with
valhaving typeusizeand also having provenance, which is a big problem: the compiler might decide, at program point (2), toreturn valinstead ofreturn cmp(based on the fact thatval == cmp), but ifvalcould have provenance then this transformation is wrong! This is basically the isue at the heart of my blog post on provenance:==ignores provenance, so just because two values are equal according to==does not mean they can be used interchangeably in all circumstances. - What other option is there? Well, we might make the load return
poison-- effectively declaring ptr-to-int transmutes as UB.
The last option is what is being proposed to LLVM, along with a new "byte" type such that loading at type bN would preserve provenance, but loading at type iN would turn bytes with provenance into poison. On the flipside, no arithmetic or logical operations are possible on bN; that type represents "opaque bytes" with the only possible operations being load and store (and explicit casts to remove any provenance that might exist). This leads to a consistent model in which both redundant store elimination and GVN substitution on integer types (the optimizations mentioned above) are possible. I don't know any other way to resolve the contradiction that otherwise arises from doing both of these optimizations. However, the LLVM discussion is still in its early stages, and there were already a lot of responses that I have not read in detail yet. If this ends up being accepted, we on the Rust side will have to figure out if and how we can make use of the new "byte" type and its explicit casts (to pointers or integers).
This thread is about discussing how we need to restrict ptr-to-int transmutes when pointers have provenance but integers do not. See #287 for a discussion with the goal of avoiding provenance in the first place.
Currently, Miri will perform these implicit ptr-to-int casts in many situations, so just because code is fine under Miri does not mean it is fine under the proposed LLVM semantics. I intend to add a flag that will treat ptr-to-int transmutes as UB.
So, clarification question: Is this currently UB or will it eventually be UB under a future LLVM?
The last option is what is being proposed to LLVM, along with a new "byte" type such that loading at type bN would preserve provenance, but loading at type iN would turn provenance into poison.
I'm not sure that's right - those are the proposed semantics for bitcast, but a new cast "bytecast" is also introduced that does not produce poison.
The frontend will always produce a bytecast, which can then be optimized into a more specific cast if necessary.
AFAICT, they don't intend to change what is UB with this change, just fix bugs and reduce the number of pointers that are considered to escape:
In our semantics, byte type carries provenance and copying bytes does not escape pointers, thereby benefiting alias analysis.
So, clarification question: Is this currently UB or will it eventually be UB under a future LLVM?
That depends on whether you consider LLVM semantics to be defined by the docs or the implementation. ;)
The docs do not mention such UB, but the implementation is most likely buggy unless this is UB, as demonstrated by this series of examples. So in a sense this already is UB in the implementation.
I'm not sure that's right - those are the proposed semantics for bitcast, but a new cast "bytecast" is also introduced that does not produce poison.
Note that in the problematic line (0) in the code. there is no cast of any kind. So the question here is not the semantics of bitcast, or the semantics of bytecast, but the semantics of an i64-typed load that accesses memory where a pointer value (with provenance) has been stored.
I came up with an example that, I think, demonstrates that ptr-to-int transmutes are truly broken. I write these as Rust code for better readability, but you should interpret these as LLVM IR programs.
Let's start with this program:
// Prepare some pointers to distinct allocated objects.
let mut p = [0];
let paddr = p.as_mut_ptr();
let mut q = [0];
let qaddr = q.as_mut_ptr();
// Set up a bit of storage with 2 ptrs to it: one usize-typed, one ptr-typed.
let mut storage = 0usize;
let storage_usize = &mut storage as *mut usize;
let storage_ptr = storage_usize as *mut *mut i32;
// Now comes the tricky bit.
*storage_ptr = paddr.wrapping_offset(1);
if *storage_usize == qaddr as usize {
let val = qaddr as usize;
*storage_usize = val;
**storage_ptr = 1;
println!("{}", q[0]);
}The one weird bit that is happening here is that we store qaddr as usize somewhere and then transmute that integer to a pointer, and write to it (**storage_ptr = 1). So, I am assuming here that int-to-ptr transmutes are okay. Possibly there is a way that we could salvage ptr-to-int transmutes if we give up on int-to-ptr transmutes, but (a) that feels even less natural, (b) I have no idea how to do this, and (c) I am not sure if that would actually help anyone; the people transmuting between ptrs and ints probably assume that going both ways is fine. We have to lose one way, and I think losing ptr-to-int transmutes is "less weird".
The program also does a ptr-to-int transmute, namely when it loads *storage_usize to compare that with qaddr as usize. This is the heart of the example: I will assume that this is fine to do, and will then derive a contradiction -- I will give a series of optimizations that change the behavior of this program, even though all these optimizations arguably should be correct. Making ptr-to-int transmute return poison means that the if in the example compares poison with an integer, which is UB, resolving the contradiction.
If this program does not have UB, it has two possible behaviors:
- Print "1" (if
qimmediately followspin memory) - Print nothing (otherwise)
The first optimization is to exploit the == inside the if, replacing qaddr as usize by *storage_usize.
// Prepare some pointers to distinct allocated objects.
let mut p = [0];
let paddr = p.as_mut_ptr();
let mut q = [0];
let qaddr = q.as_mut_ptr();
// Set up a bit of storage with 2 ptrs to it: one usize-typed, one ptr-typed.
let mut storage = 0usize;
let storage_usize = &mut storage as *mut usize;
let storage_ptr = storage_usize as *mut *mut i32;
// Now comes the tricky bit.
*storage_ptr = paddr.wrapping_offset(1);
if *storage_usize == qaddr as usize {
let val = *storage_usize; // this changed
*storage_usize = val;
**storage_ptr = 1;
println!("{}", q[0]);
}The second optimization removes the redundant store to *storage_usize, since we are only storing back what we just loaded. We then also remove the let val = ... since val is unused now.
// Prepare some pointers to distinct allocated objects.
let mut p = [0];
let paddr = p.as_mut_ptr();
let mut q = [0];
let qaddr = q.as_mut_ptr();
// Set up a bit of storage with 2 ptrs to it: one usize-typed, one ptr-typed.
let mut storage = 0usize;
let storage_usize = &mut storage as *mut usize;
let storage_ptr = storage_usize as *mut *mut i32;
// Now comes the tricky bit.
*storage_ptr = paddr.wrapping_offset(1);
if *storage_usize == qaddr as usize {
// 2 lines got removed here.
**storage_ptr = 1;
println!("{}", q[0]);
}Next, we replace the *storage_ptr by the value that has just been written there:
// Prepare some pointers to distinct allocated objects.
let mut p = [0];
let paddr = p.as_mut_ptr();
let mut q = [0];
let qaddr = q.as_mut_ptr();
// Set up a bit of storage with 2 ptrs to it: one usize-typed, one ptr-typed.
let mut storage = 0usize;
let storage_usize = &mut storage as *mut usize;
let storage_ptr = storage_usize as *mut *mut i32;
// Now comes the tricky bit.
*storage_ptr = paddr.wrapping_offset(1);
if *storage_usize == qaddr as usize {
*paddr.wrapping_offset(1) = 1; // this changed
println!("{}", q[0]);
}And finally, we exploit that the only 2 writes that happen definitely do not have the provenance of q, so q remains unchanged, so we can replace the final q[0] by a constant 0:
// Prepare some pointers to distinct allocated objects.
let mut p = [0];
let paddr = p.as_mut_ptr();
let mut q = [0];
let qaddr = q.as_mut_ptr();
// Set up a bit of storage with 2 ptrs to it: one usize-typed, one ptr-typed.
let mut storage = 0usize;
let storage_usize = &mut storage as *mut usize;
let storage_ptr = storage_usize as *mut *mut i32;
// Now comes the tricky bit.
*storage_ptr = paddr.wrapping_offset(1);
if *storage_usize == qaddr as usize {
*paddr.wrapping_offset(1) = 1;
println!("{}", 0); // this changed
}This final program now can print "0" if q immediately follows p in memory. That is not a possible behavior of the original program, so one of the optimizations was wrong -- or the source program had UB.
And finally, we exploit that the only 2 writes that happen definitely do not have the provenance of q, so q remains unchanged, so we can replace the final q[0] by a constant 0:
Correct me if I'm wrong, but I think that this step is not validated by the current stacked borrows model. Once paddr and qaddr are created, both pieces of memory are valid for writes by pointers from any source, so in particular it is valid to use a pointer pointer derived from paddr but numerically equal to qaddr to write to q.
I hesitate to bring this up again, because it has already been discussed at some length after your provenance blog post, but I think there is a reasonably easy to understand model for pointers here that basically amounts to "pointers don't have provenance". We already have to support "wild" pointers for the case of manufacturing numeric addresses and dereferencing them, and the only thing that is needed to recover the majority of optimizations is to make memory only writable if there is a SharedRW(_|_) on the stack. The pointer itself is an untagged integral value.
This problem has been presented as a sort of Gordian knot with no good solution, but it's not like there aren't consistent (and comprehensible!) models for this stuff. I don't think losing this store forwarding optimization is a big deal, partly because it is very contrived, but also because it uses lots of pointer arithmetic and I think that in that case we should encourage people to use references when possible and otherwise do exactly what they wrote and expect the user to take the performance into their own hands.
Correct me if I'm wrong, but I think that this step is not validated by the current stacked borrows model. Once paddr and qaddr are created, both pieces of memory are valid for writes by pointers from any source, so in particular it is valid to use a pointer pointer derived from paddr but numerically equal to qaddr to write to q.
No, that is not true. Once qaddr is created, it is legal to cast an int that is equal to qaddr to a ptr and use that to access q. However, that does not happen in the second-to-last program. Writes using a specific provenance still have to adhere to that provenance. The only writes that happen in the second-to-last program have known provenance (of storage and p, respectively); it would be UB for them to affect or depend on any other allocation, making this transformation legal. (This is basically the same as the last step in my provenance blog post.)
The pointer itself is an untagged integral value.
This is incompatible with many optimizations performed by LLVM. I don't think LLVM will switch to a provenance-free model any time soon, and so by extension Rust will not switch to a provenance-free model. In fact I think it is not possible to write a reasonably optimizing compiler for a model where pointers have no provenance. To my knowledge, every single optimizing compiler for languages such as C and C++ has provenance in its memory model. So, the burden of proof here is IMO on folks that don't like provenance: construct at least a reasonable prototype of a compiler that is correct for a provenance-free model. Even register allocation will be hard for such a compiler (since, in first approximation, any write through a pointer might affect any variable that ever had its address taken).
If you want to continue this discussion, please open a new thread (or maybe there already is one, I forgot). Questioning the existence of provenance itself is certainly off-topic in this issue.
This problem has been presented as a sort of Gordian knot with no good solution, but it's not like there aren't consistent (and comprehensible!) models for this stuff.
There aren't -- not if you also want to support a reasonable set of optimizations that modern compilers support. (Of course, there are easy models without provenance, but those are entirely unrealistic as basis for a compiler that wants to produce good assembly.) This is not just my opinion, it is the consensus of all the researchers that I know that work in this field.
Again, this is off-topic here. Please don't reply to this part inside this thread; create a new issue and link to it instead.
I don't think losing this store forwarding optimization is a big deal, partly because it is very contrived, but also because it uses lots of pointer arithmetic
EDIT: removed my previous reply since I think I misunderstood you. I think you mean the last optimization here, not the one that removes a redundant store. I'm not well-versed in compiler optimization pass jargon. ;)
That optimization is a representative example of something compilers do a lot. I have strong doubts that losing it is a realistic option, unless we want to give up on competing with C/C++.
This is incompatible with many optimizations performed by LLVM. I don't think LLVM will switch to a provenance-free model any time soon, and so by extension Rust will not switch to a provenance-free model. In fact I think it is not possible to write a reasonably optimizing compiler for a model where pointers have no provenance.
I think we need to be careful to distinguish the tasks of making an operational semantics for Rust, and changing LLVM's memory model and/or making the two coincide. There is no reason a priori that they should be joined at the hip, although of course we need to consider how lowering is going to work if the two models differ in the details.
Even so, I don't think in this particular instance it is that hard to produce a valid lowering. The basic mapping is to take Rust references to LLVM pointers, and Rust pointers to LLVM integers (or possibly "wild"/explicitly provenance-erased pointers). This can probably be optimized to the point that Rust pointers mostly map to LLVM pointers, with just a few additional provenance erasing operations being inserted when it looks like LLVM might make an incorrect deduction otherwise.
To my knowledge, every single optimizing compiler for languages such as C and C++ has provenance in its memory model.
This is not a fair comparison - C and C++ don't have references (well, C++ has something they call references but I won't go into why they don't count). Rust is built around the idea that you should be using references and the borrow checker 95+% of the time, so the calculus is completely different, especially if the claim is that this approach has unacceptable performance costs.
So, the burden of proof here is IMO on folks that don't like provenance: construct at least a reasonable prototype of a compiler that is correct for a provenance-free model.
This is a tweak to codegen that I think is within our capabilities to test. I don't know if I am personally in a position to make such modification but gathering data on the performance cost is important to serious consideration of this approach. (I'm willing to try though, if that's what it takes to move this discussion forward. I will probably need mentoring.)
Even register allocation will be hard for such a compiler (since, in first approximation, any write through a pointer might affect any variable that ever had its address taken).
Rust doesn't do register allocation, it hands off to LLVM which can create its own LLVM pointers with LLVM semantics and do optimizations with them. As long as the input Rust code doesn't contain lots of (Rust) pointers and pointer arithmetic, the code will look fairly standard from LLVM's perspective and I see no reason to expect a huge performance degradation.
If you want to continue this discussion, please open a new thread (or maybe there already is one, I forgot). Questioning the existence of provenance itself is certainly off-topic in this issue.
I suspected an answer like this, which was the source of my hesitation. Nevertheless, I believe it should be seriously considered and it is absolutely germane to the discussion of what to do about transmutes and casts between the rust types *mut T and usize, which has always been considered a reasonable operation since Rust's inception (indeed, there isn't much point in the usize type otherwise, you should just stick to u32 and u64 if you don't want pointer-sized ints).
That optimization is a representative example of something compilers do a lot. I have strong doubts that losing it is a realistic option, unless we want to give up on competing with C/C++.
Needless to say, I believe this is overstated. My interest is in getting past the obstacle, and ideally getting to a Rust spec in the end, not just observing how obstacle-like it is. Making int-ptr casts UB will break a lot of code and make certain low level tasks impossible; I don't think it's a solution to the problem, unless there are more refinements to the plan.
But if we're enumerating options, I think that "pointers don't have provenance" should be on the list and we should try to show that it's actually unviable for performance reasons if that's the claim.
One other possible resolution:
if *storage_usize == qaddr as usize {
let val = *storage_usize; // this changed
*storage_usize = val;
**storage_ptr = 1;
println!("{}", q[0]);
}->
if *storage_usize == qaddr as usize {
// 2 lines got replaced with this
erase_provinence(*storage_usize);
**storage_ptr = 1;
println!("{}", q[0]);
}Further transformations are prevented because the compiler can no longer prove that storage_ptr == paddr.wrapping_offset(1) due to the intervening erase_provinence.
Here erase_provinence behaves very similarly to the compiler_fence intrinsic, in that does not generate code, it just influences other optimizations passes.
(AIUI, this is basically saying that integer variables do not have provenance, but memory locations that happen to store integers may have provenance)
Even so, I don't think in this particular instance it is that hard to produce a valid lowering. The basic mapping is to take Rust references to LLVM pointers, and Rust pointers to LLVM integers (or possibly "wild"/explicitly provenance-erased pointers). This can probably be optimized to the point that Rust pointers mostly map to LLVM pointers, with just a few additional provenance erasing operations being inserted when it looks like LLVM might make an incorrect deduction otherwise.
LLVM itself is currently inconsistent, as my series of examples shows. The most likely fix is for them to make i64 loads of pointer values return poison. Under that fix, your proposal clearly does not work. Maybe they find another fix; it is impossible to say if your proposal is compatible with that fix. However, I think it is safe to say that "integers don't have provenance" and "pointers do have provenance" (both of which are Rust concepts) will necessitate Rust to impose restrictions on ptr-to-int transmutes. I am not bringing up LLVM because I think Rust must follow what LLVM does, I am bringing up LLVM because it is a representative example of a modern compiler middle-end, and it is by far the best-documented optimized middle-end IR out there -- having this discussion with a poorly documented or even hypothetical IR is a lot harder.
Of course we can always use some heavy lowering that basically kills all alias analysis, and then whatever LLVM does with provenance becomes a non-issue. In fact that's what you are basically dong by using i64 for raw pointers, and adding a inttoptr before every load. I am convinced beyond doubt that this is not an acceptable approach for people that care about generating good machine code from Rust programs.
You are still trying to remove provenance from pointers here. This is not the thread to do that. Please leave this thread to the discussion of which impact pointer provenance has on int-to-ptr transmutes, and do not derail it by undermining the very premises of the entire discussion here. That's not constructive for this discussion. When people are discussing which book of the Harry Potter franchise is the best, it is not okay to go in and tell them that Lord of the Rings is just a better franchise. So please don't do that. Open a new thread for your other discussion.
I suspected an answer like this, which was the source of my hesitation. Nevertheless, I believe it should be seriously considered
To be clear, I am not opposed to discussing "what would Rust without provenance look like". I am just opposed to discussing it here, in this very GH issue, with GH being as it is. It will be impossible to have that discussion and the entirely parallel discussion of "ptr-to-int transmutes in a world with provenance" together in the same thread. So all I am asking is that you refrain from derailing the latter discussion by hopelessly mixing it with the former.
I have opened #287 for this purpose. I hope this is okay for you. I have seen way too many GH threads dissolve into hopeless chaos due to a lack of discipline about the topic under discussion, and I really don't want this to happen again here. In an RL discussion, many sub-threads can go on in parallel and interleave and it's beautiful, but GH as a tool is unable to reflect that. Hence, in order to keep these threads useful and be able to have any discussion that people can have a chance of following later, I think it is imperative that we split each of these sub-threads in its own issue. Our choice here is between shoehorning the shape of the discussion into the (in)abilities of the tool we are using (GitHub), or else to have the rather frustrating, confusing, and draining experience that stems from using the wrong tool for the job and talking past each other all the time -- and excluding people that want to just partake in one of the sub-threads.
@Diggsey thanks for continuing with the on-topic discussion!
Here erase_provinence behaves very similarly to the compiler_fence intrinsic, in that does not generate code, it just influences other optimizations passes.
Yes, this is an alternative proposal. However, it means that as far as the IR is concened, there is a write to *storage_usize that all the other optimizations need to treat as a proper write. So this negates most of the benefit of redundant store elimination.
So this negates most of the benefit of redundant store elimination.
I think "most" is a little strong, at least without more evidence. It still eliminates the store from the resulting program, so the cost is only potentially missed optimizations from later passes.
Even then, it's not clear to me that erase_provenance prohibits any valid optimizations, since the only example we have is where the later optimization is actually wrong.
To my knowledge, whether or not a piece of code performs a write and whether or not some pointer is written to is very useful information that can have large consequences in the optimizer.
Also note that in Rust we have quite a few language or library concepts that make no difference to the machine code (offset vs wrapping_offset, release/acquire vs sequentially consistent ordering on an x86 machine ...), and yet these concepts are still quite important. For example, to my knowledge the reason that bounds checks cost so much performance is not that the checks are slow on the CPU (the branch predictor can be instructed to assume they will all succeed); the actual cost of a bounds check is that it introduces tons of new control dependencies and thus grinds the optimizer and its ability to analyze the program and reorder instructions to a halt. The effect of some instruction on the optimizer can be more important than its effect in the final assembly.
I guess what I am saying in a round-about way is: this would need serious benchmarking, and it seems unlikely that we can do it with LLVM as our backend.
Even then, it's not clear to me that erase_provenance prohibits any valid optimizations, since the only example we have is where the later optimization is actually wrong.
The later optimization is perfectly fine, it is a standard alias analysis result. The original source program is wrong, IMO. Obviously my example is contrived, because real-world code doing things like this is just way too big to be considered in such detail.^^
For the IR, erase_provenance is a write no different from a "true" store, so every optimization that is prohibited by a true store is also prohibited by erase_provenance.
One thing I'd like to clarify: "transmute" is not a thing in C++. The closest equivalent might be reinterpret_cast? However, C++ explicitly says that it is valid to reinterpret_cast a pointer to an intptr_t and back again.
So what you actually mean here is that type-punning via a store to memory of a pointer type, followed by a load at an integer type (or vice versa) should be considered UB, and that just happens to be how we define transmute right now?
However, C++ explicitly says that it is valid to reinterpret_cast a pointer to an intptr_t and back again.
Oh, fun. I'll leave that to the C++/clang people to figure out. ;)
So what you actually mean here is that type-punning via a store to memory of a pointer type, followed by a load at an integer type (or vice versa) should be considered UB, and that just happens to be how we define transmute right now?
Yes. Type-punning raw ptr loads, union field accesses, and transmute are all equivalent operations in Rust. I don't see any benefit from making them different, since the first two of them cannot actually do anything to the data in a meaningful way as they have no idea what the "source type" of the data should be. So we have to solve this problem anyway, therefore making transmute behave differently than the others just increases complexity without solving the fundamental issue.
One thing I'd like to clarify: "transmute" is not a thing in C++. The closest equivalent might be reinterpret_cast?
reinterpret_cast between pointer and int is the same as the C-style cast, e.g. (intptr_t)ptr (The latter is defined in terms of the former. This is notably distinct from (and weaker than) transmute in many, many ways.
The closest thing to transmute is C++20's bit_cast, which is more-or-less identical to transmute. It's very new though, and probably is (also, it's a library function and not a builtin operator like reinterpret_cast, although this makes little difference in practice).
So, I don't think this will cause problems for C++ really, since IIUC we're not saying ptr as usize is invalid (the as-style cast remains fine), just that the transmute is invalid.
(Also, as you correctly mention, performing the transmute the way we do in these examples, where the underlying memory is interpreted as a different type, is UB in C++ for other reasons anyway)
(Also, as you correctly mention, performing the transmute the way we do in these examples, where the underlying memory is interpreted as a different type, is UB in C++ for other reasons anyway)
Not always. All memory can be read and written via chars regardless of type - and if I've understood correctly, this is the reason for the attempt to introduce a "bytes" type to LLVM, so that Clang can use "bytes" when translating from a C++ char.
I don't really understand how user-implemented memcpy works in this model though, assuming it copies with granularity greater than char...
Yes, I'm aware of the exceptions around char (the "memcpy exception" and such). They don't apply here, since nothing like them is being used in the source in question (the rule around char doesn't apply indirectly, e.g. you can't use the memcpy exception to turn a T* into a U* which you then use as a U, unless that would already be allowed).
And user-implemented memcpy isn't allowed to copy with greater granularity than char for this reason, which is silly but true, and a good example of a place where Rust does a great deal better than C++ at reflecting semantics that real programs need to be efficient.
Anyway, we are well into the weeds at this point and probably off-topic (in a thread that's already had issues with staying on-topic).
They don't apply here, since nothing like them is being used in the source in question
Maybe I'm misunderstanding, but couldn't you simply replace usize with [u8; size_of::<usize>()] in the example and have the same issue? And if you then translated that example into C++ it would not be allowed to be UB.
Oh, hm, probably. I guess I agree with Ralf then that that's, uh, gonna be a tricky one for the clang folks to work out.
I don't really understand how user-implemented memcpy works in this model though, assuming it copies with granularity greater than char...
Whether and how memcpy can be implemented inside C at all is an interesting question -- and a "byte" type is probably part of the answer.
And if you then translated that example into C++ it would not be allowed to be UB.
There would be explicit casts between byte[8] and uintptr_t. Those casts are subject to similar restrictions as int-to-ptr casts: roundtrips cannot be optimized away. That makes at least one of the optimizations wrong, solving the problem.
The latest/next C++ actually has an explicit std::byte type that would map very nicely to the LLVM type. We don't really have anything comparable in Rust, we use MaybeUninit<T> instead... so we should probably ensure that MaybeUninit<usize> becomes b64 (on a 64bit platform).
I'm pretty sure std::byte is semantically identical to all the other character types (like char, and unsigned char) except that it requires an explicit cast to convert to/from it (as it's defined as a enum class, which don't have implicit conversions).
The only places I can find where https://github.com/cplusplus/draft mentions it that aren't as part of a list of the other char types are where it describes which header it's found in and such.
So I think it's not really the same as the proposed llvm bytes type in any meaningful way, unless char/unsigned char also are.
So I think it's not really the same as the proposed llvm bytes type in any meaningful way, unless char/unsigned char also are.
Yes, those are also LLVM byte under the current proposal.
Just to summarize the LLVM proposal now that I understand it more (please LMK where I'm mistaken):
- It will make explicit the distinction between "pointer" types and "integer" types.
- It will introduce a "byte" type that can contain either contain pointer data or integer data, but not both: it simply allows the decision to be punted until runtime.
pointer -> bytes -> pointeris valid.integer -> bytes -> integeris valid. Butpointer -> bytes -> integerand the reverse is still invalid without an explicitptrtoint/inttoptrcast.- C/C++
chartypes will map to "byte".
The C++ solution does not work for Rust, because Rust does not special-case the u8 type in any way (and I think we can all agree we don't want to do this).
The solution I initially suggested would be roughly equivalent to translating all of Rust's integer types to the corresponding LLVM "byte" types. With this we would potentially lose out on optimizations compared to C++ on our non-u8 integer types, but u8 would be the same.
Then there's your opening proposal, which is to continue to map all integers to the corresponding LLVM integer types and make these transmutes UB in Rust. A possible extension to that proposal would be to explicitly introduce a corresponding set of "byte" types that map to the LLVM "byte" types being introduced.
What all of these proposal have in common is that they treat memory as being "typed" (or at least marked as either ptr/non-ptr).
Other possible proposals
These may be impractical, I'm just throwing stuff out there:
-
We could decide that memory is untyped and so does not store provenance information. All pointer writes to memory would be considered to escape the pointer, and all pointer reads would be considered to have any possible escaped provenance. Provenance can still be used for local reasoning.
-
We could do the above, but allow preserving provenance of values stored to memory under some restricted conditions: imagine memory is still untyped, but within a local scope we could keep a "side table" of provenance information, if we can prove that it won't be affected by anything we can't reason about locally.
One more thing:
It seems to me that C/C++ will also have to use this "byte" type and appropriate ptrtoint/inttoptr casts whenever accessing fields of a union, since type punning also is explicitly allowed via unions.
This would set some precedent for treating transmute as different from a store to/load from memory: there would be nothing stopping us from defining "transmute" and our union operations in whatever way Clang chooses for C/C++ unions.
It will introduce a "byte" type that can contain either contain pointer data or integer data, but not both: it simply allows the decision to be punted until runtime.
Not sure what you mean by "but not both": every byte is either an integer byte or a pointer byte (a bit like my definition of Byte in this document). iN will never carry a pointer byte. Pointer types may or may not carry integer types; I am not sure if the proposal says anything about that and I think integer bytes in pointers are fine. bN can carry any byte.
Then there's your opening proposal, which is to continue to map all integers to the corresponding LLVM integer types and make these transmutes UB in Rust. A possible extension to that proposal would be to explicitly introduce a corresponding set of "byte" types that map to the LLVM "byte" types being introduced.
And then there's my proposal to do something with MaybeUninit (or with unions in general).
We could decide that memory is untyped and so does not store provenance information.
Note that even local let-bound variables are stored in memory. So this is, for all intents and purposes, equivalent to just removing provenance entirely. (Saying that "only stack memory carries provenance" brings back all the problems we are discussing here -- my examples don't even use any other kind of memory.)
Ralf, I assume you've read the Proposal N2624, and I assume you have more insight as to whether such a proposal is even feasible for C/Rust/LLVM. From only reading the proposal and presentation, it appears PNVI-ae is option 1. Are there differences between between Rust and C that make this infeasible?
I haven't read it in details, but I spoke with some of its authors, so I have a reasonably good idea of what's in there.
For Rust I hope we will not use PNVI-ae; that explicit "exposed address" mechanism is IMO unnecessary and does not reflect how compilers reason about exposed addresses. I am imagining something more like PNVI-plain for Rust.
But that proposal does not really talk about ptr-to-int transmutes, so it does not help with the question in this issue.
Hmm. Page 40 of the presentation says
Pointer provenance and union type punning
Pointer values can also be constructed by type punning, e.g. writing an int* union member,
reading it as a uintptr_t union member, and then casting back to a pointer type.
The same semantics as for representation-byte reads also permits this: x is deemed exposed by
the read of the provenanced representation bytes by the non-pointer-type read. The
integer-to-pointer cast then recreates the provenance of x.
Iirc, Rust union semantics match C union semantics, which have the same semantic as transmutes? I'm not sure how TBAA affects the pointer read case though, as casting a pointer to pointer to pointer to integer and reading is UB in C. I think C gets to cheat then by still allowing the removal of the redundant write by TBAA, and still allowing int-ptr casts (and transmutes).
Rust union semantics match C union semantics, which have the same semantic as transmutes?
Not really, C union semantics are very restrictive (you must read from the "active" member of the union; the only exception is when two union members share a common prefix of types).
It is not yet clear how to best translate C union accesses to LLVM with "byte". Accesses of int type might have to happen at LLVM "byte" type followed by "bytecast".
Not really, C union semantics are very restrictive (you must read from the "active" member of the union; the only exception is when two union members share a common prefix of types).
I am 80% sure you're thinking of C++ unions, as C unions don't have a concept of active member. Putting aside C as it's kind of off topic, translating this proposals semantics into Rust would mean:
- You cannot roundtrip a pointer (whether standalone or nested inside a strict) into an integer and back again by pointer casts.
- Transmutes and unions as they are defined would also have the same semantics, but it's not unfeasible to imagine they would act as implicit pointer-to-int casts.
It looks like you were right that this proposal does not help us with regards to this issue, which is unfortunate.
I am 80% sure you're thinking of C++ unions, as C unions don't have a concept of active member.
That is possible, I do tend to mix up C and C++. But I am very sure that C has special rules for when two union fields have a common prefix of fields in their type. In fact this contains one of my favorite under-defined quotes of the C standard:
it is permitted to inspect the common initial part of any of them anywhere that a declaration of the completed type of the union is visible.
So far, I don't think anyone has figured our what it means for a "declaration of the completed type of the union" to be "visible", and compilers certainly don't take that into account for their (strict) alias analysis...
So, unions in C definitely are not the same as in Rust.
Now I'll mark this comment as off-topic to hopefully not further derail the discussion. ;)
Random thought: this relevant for function pointers?
It's currently safe and easy to do some_fn_ptr as usize (where some_fn_ptr: fn(some) -> nonsense or whatever), I believe doing the reverse operation requires invoking transmute.
Random thought: this relevant for function pointers?
I think function pointers are mostly like normal (data) pointers in this regard -- they carry provenance.
doing the reverse operation requires invoking transmute.
Oh, that's weird. Why can we cast fn ptrs to ints but not the other way around?
Because they'd be safe to call, and no other as casts are unsafe.
Oh, fun times. But well, I think int-to-ptr transmtues are fine, so this is not necessarily a big issue.
Even for unsafe fn() which requires unsafe this isn't possible without transmute because function pointers are required to be non-null
Sure, the cast would need to be unsafe -- but that doesn't explain why there is no such cast.^^
I spent some time reading the entirety of the latest proposal, and I think there's a difference in mental models here. I think I was wrong when I was talking previously, and this proposal might be suitable for Rust.
According to what I think the semantics of this paper, a pointer-to-int roundtrip is not a NOP, but can be replaced by a NOP and a bit of state tracking that the pointer has escaped. (I'm assuming PNVI-ae here, as it's easier for me to understand).
So if you look at slides 54-57 of N2624, that appears to be what your are talking about in your blog post on provenance.
Based on this, I've come to the same conclusion that optimization 2 is incorrect. LLVM can replace the cast roundtrip; however, it must track that q's address was exposed. Alias analysis can then no longer remove q.
I don't know how this example will work right now actually. You would need PNVI-ae-udi, but there are no situations with ambiguous provenance without one-past-the-end-pointers. This breaks the idea that a roundtrip is replaceable by marking the object as escaped.
Now what I've said doesn't address Rust's implicit casts via transmutes and pointer type aliasing. In the example in your first post:
fn example(ptr: *const i32, cmp: usize) -> usize { unsafe {
let mut storage: usize = 0;
*(&mut storage as *mut _ as *mut *const i32) = ptr; // write at ptr type
let val = storage; // read at int type (0)
storage = val; // redundant write back (1)
external_function(&storage); // just making sure the value in `storage` can be observed
if val == cmp {
return cmp; // could exploit integer equivalence (2)
}
return 0;
} }
We would take option 1 here, where LLVM would drop the provenance on the load. As I've established above, LLVM could then remove the redundant write (being sure to mark ptr as escaping). You would need machinery to mark the implicit ptr-to-int casts caused by transmutes, unions and these pointer-to-pointer casts, and I don't know enough to comment on that. Of particular note is how this is different from section 8 of the twin allocation paper: there, a int-to-ptr cast erases provenance, here the cast recreates the provenance.
This entire thing is maybe a bit rambly and maybe incomplete, but I hope it's at least mostly accurate. I'm certain there's a counterexample lying here somewhere, but it's been a lot of reading and contemplating, and I haven't thought of it yet.
a pointer-to-int roundtrip is not a NOP, but can be replaced by a NOP and a bit of state tracking that the pointer has escaped.
No, not really -- the ptr you get back out has a different, more permissive provenance than the one you put in. (And as a consequence I also disagree with the rest of your analysis.)
Hmm. Is this according to PNVi-ae semantics? I thought that might be the case, but I'm still trying to find a counterexample.
The TR says
For PNVI*, one has to choose whether an integer
that is one-past a live object (and not strictly within another) can be cast to a pointer with valid provenance,
or whether this should give an empty-provenance pointer value. Lee observes that the latter may be necessary
to make some optimisation sound [personal communication], and we imagine that this is not a common idiom in
practice, so for PNVI-plain and PNVI-ae we follow the stricter semantics.
I am not sure where this is actually defined, but from this description, if you have a one-past-the-end ptr with provenance of some object X, and roundtrip it, under PNVI-ae, you get either a ptr with empty provenance or a ptr with provenance of some other object Y that happens to start at that address. Either way, you don't get back your original ptr.
Taking a step back -- PNVI is all about integer-pointer casts. This issue is about transmutes ("type-punning loads"). Why are we talking about PNVI? I think that's off-topic. PNVI does not have an answer to the problem described in the OP, to my knowledge.
Yeah, after playing around with the model a bit, the idea I had did not hold. I guess I'm just loathe to adopt a (admittedly limited) version of type based aliasing for Rust. It breaks a long told adage about Rust, and it's just one of those unfortunate footguns :(
Rust also tells the tale "raw pointers are bad for your health"
type based aliasing
Note that this is not about type-based aliasing. We do not make assumptions like "these two pointers have a different type so they cannot alias".
One could call this "typed memory", though, so maybe that's what you mean. (Though there are only two types: integers and pointers. Everything that's not a pointer is an integer.)
That still seems like quite unfortunate of a change. Ignoring LLVM's specific current semantics (which likely will become less relevant as rust both gains more backends, and gains traction (which can help motivate larger changes in upstream LLVM)), is there any way to avoid that loss, short of #287?
It's not so much that it's hard to learn, but it is going back on a very frequently repeated claim (that Rust has no typed memory) that is well-understood (and now possibly false) by the broader community of Rust programmers writing unsafe code (who largely I don't think follow the happenings in this repo).
In systems with provenance, pointers and integers are fundamentally different beasts. That is one of the underlying lessons of this counterexample: optimizing away ptr-int-ptr roundtrips is wrong; pointers have "more structure" than integers do.
So, I think the only reasonable way to avoid this kind of "typed memory" is to have no provenance at all.
But I don't think of this really as "typed memory" -- I think of this as just "we have provenance", which (pretty much) necessarily implies that there is provenance on values stored in memory, which is what we are talking about here.
Rust still has nothing like TBAA / strict alias analysis, which is the most important part of "Rust does not have typed memory" (in my eyes). What we are discussing here is more about data representation: not everything can be represented as an integer. Some things are "more than just regular bytes".
But I do agree that the broader community of people writing unsafe Rust probably assumes that everything can be represented as an integer, as does the vast majority of C programmers -- and that is a problem. I don't know what to do about that, since the nature of unsafe code is such that we cannot easily use types and APIs to let the compiler and rustdoc do the teaching here. (But I feel like "how do we teach people about provenance" should be a separate thread; this thread here is about the very technical problem of how we define the semantics of ptr-to-int transmutes. If you want to discuss this or even have some ideas, please open a new issue. :)
For what it's worth, "typed memory" and "pointer provenance" were always two completely separate things in my mind, even before I had any inkling as to the formal definitions and how they could technically be special cases of each other in a sufficiently abstract but meaningless-in-practice sense. So I definitely do not feel that the existence of provenance is in any way a betrayal of the oft-repeated and IMO still entirely correct claim that "Rust has no typed memory" (although we probably should prefer to say "Rust has no TBAA" since that is far less ambiguous). After all, it's not like anyone thought "no typed memory" meant "there is no type system" or "types are completely irrelevant for semantics/what counts as UB" or anything like that.
That "regular programmers" seem to be unaware of provenance despite constantly relying on optimizations that require it is a real problem, but hardly a new one, and it seems no worse in Rust than in every other language with pointers and optimizing compilers (if anything, it's likely far better in Rust since IIUC you don't need to know about it until you write unsafe somewhere), and I agree digging into that more would be a subject for another thread.
That "regular programmers" seem to be unaware of provenance despite constantly relying on optimizations that require it is a real problem,
There are two problems. One is programmers not being aware of the precise rules around UB, but the other is where the rules for UB make it impossible to perform certain necessary tasks.
For example, strictly speaking you cannot write a memcpy implementation in C that copies with granularity of more than one byte at a time. However, a performant memcpy must copy with granularity greater than that! There is a point where the abstract-machine must meet the real hardware.
If this (making pointer-to-integer transmutes UB, and introducing a "bytes" type to LLVM) is how we end up proceeding, then that also means complicating the surface language considerably, since Rust will also need new types to operate on "bytes". All code that assumes untyped memory will need to be written to copy using the corresponding "bytes" types instead of integers.
Code which does low-level tricks such as swapping via XOR, or obfuscating memory that may contian pointers, etc. becomes impossible unless the new "bytes" types also gain new arithmetic operations (or are able to be casted to integers without introducing UB).
Rust will also need new types to operate on "bytes"
I think we already have that type: MaybeUninit.
Code which does low-level tricks such as swapping via XOR, or obfuscating memory that may contian pointers, etc. becomes impossible unless the new "bytes" types also gain new arithmetic operations (or are able to be casted to integers without introducing UB).
Having arithmetic on byte would defeat its purpose -- its entire point is that it doesn't have arithmetic so it can hold data on which arithmetic makes no sense.
So yes we need some operation that lets us cast any initialized piece of memory into an integer, dropping provenance if it exists -- like bytecast in the LLVM proposal.
I think we already have that type: MaybeUninit.
That makes sense, although it's a little non-obvious. Would you say that "having no provenance" is part of the initialization invariant for integers?
Having arithmetic on byte would defeat its purpose -- its entire point is that it doesn't have arithmetic so it can hold data on which arithmetic makes no sense.
Some kinds of arithmetic are well-defined for both pointers and integers, and so may make sense to define for bytes. For example, addition (assuming that if it's a pointer is stays within the bounds of the allocation) or indeed any reversible operation (eg. XOR these bytes with a random key, and then repeat the process before re-interpreting the bytes as something else).
Maybe we say that you cannot do these operations in Rust without first dropping the provenance via bytecast, but they exist as possibilities.
Would you say that "having no provenance" is part of the initialization invariant for integers?
Yes, that was my plan to "explain" the UB on ptr-to-int transmutes.
Some kinds of arithmetic are well-defined for both pointers and integers, and so may make sense to define for bytes.
Remember that a pointer-sized sequence of bytes can have different provenances on the different bytes. I don't think it is worth figuring out which rules make sense here...
Another thing to consider are intrinsics which allow reading from or writing to memory.
eg.
https://doc.rust-lang.org/nightly/core/arch/x86/fn._mm256_load_epi32.html
We should probably say that these intrinsics have an implicit bytecast so that they can be used to eg. copy pointers without introducing UB, or else we'd need to introduce more variants.
Then we just have to convince LLVM to adopt that semantics. ;)
How would typed memory be modeled in Miri? Would each byte be an (Type, u8) sort of thing, and a read with the wrong type (either integer or pointer) be UB?
If by "typed memory" you mean the thing that several people above said they would not call "typed memory", then Miri already implements that.
It uses a somewhat clever encoding for performance though (at the cost of not being able to properly execute some weird kinds of programs). The "proper" way to implement byte-wise representation of pointers with provenance in memory is to say that an allocation in memory is a Vec<Byte> where Byte is defined as in this document.
Moving out of a somewhat offtopic IRLO thread:
Also, no idea why you claim Rust would be "more restrictive" than C, that is not the case.
You are (in this issue) proposing that not only is reading a pointer as an integer via pointer punning UB, but all transmute-like operations are. This is more restrictive than C, which allows union punning and the direct transmute equivalent of mempcy(&integer, &pointer, size).
If you combine my two examples, you will see that removing a load whose result is unused is an incorrect optimization. I very much doubt any compiler author will be convinced to give up that optimization. (The only alternative is to say that integers have provenance, which then has a whole other set of "unreasonable" consequences.)
No, there is the alternative I said right there, namely to not completely forget pointer-to-integer casts (at least not when followed by a store of that integer into memory which isn't having alias info tracked), because, taking C's draft as inspiration, that's incorrect by PVNI. You want to call something a strawman, this argument of yours is a strawman rather than nitpicking about wording.
And while this (or whatever LLVM's actual solution winds up being) may be more difficult than what is currently done, it is something LLVM will have to do anyways, to support C. And forbidding pointer-to-integer transmutes doesn't have obvious potential performance wins like everything around &mut does.
You are (in this issue) proposing that not only is reading a pointer as an integer via pointer punning UB, but all transmute-like operations are. This is more restrictive than C, which allows union punning and the direct transmute equivalent of mempcy(&integer, &pointer, size).
C is underspecified. It seems to allow many things but if you take them together you get a contradiction with optimizations that people also say it allows. So there is no way to make a definitive comparison with C until all these ambiguities in the spec are resolved.
My example easily translates into C (replacing the pointer type punning by a type punning method that is acceptable in C), so all the issues Rust has also apply to C. Also keep in mind that C without strict aliasing is a common dialect that needs to be supported as well, and LLVM does not have "global" strict aliasing, so relying on TBAA does not really work.
Indeed we probably have to do something very similar to whatever LLVM does to solve this problem, but based on past experience I would not expect such a solution to just materialize -- LLVM has lived with much easier to fix fundamental spec issues that cause real-world miscompilations for quite a while. So instead of sitting and waiting we might as well see if we can come up with a reasonable solution, and then maybe work with the LLVM people to help fix the problem on their level and find a solution that works for all of us.
No, there is the alternative I said right there, namely to not completely forget pointer-to-integer casts (at least not when followed by a store of that integer into memory which isn't having alias info tracked), because, taking C's draft as inspiration, that's incorrect by PVNI.
I don't know what semantics you mean to sketch here.
For all my examples, you either have to declare the source program UB, or you have to disallow one of the optimizations it performs. So which one shall it be? There is the transmute example, and the with restrict you cannot remove a dead cast example.
PNVI does not solve either of these problems, as far as I know.
And forbidding pointer-to-integer transmutes doesn't have obvious potential performance wins like everything around &mut does.
Forbidding the transmutes has the benefit that we can keep the performance we currently have. Right now, compilers are cheating, they gain performance by doing optimizations that are incorrect -- at least if we follow a naive spec that allows such transmutes. So the comparison with &mut aliasing is off -- &mut aliasing is about getting extra performance through some extra part in our semantics; here in this issue we are talking about fixing the foundations so that we can even have a spec that is actually correctly implemented by compilers. (C does not have such a spec, but the spec it has is written in a way that this is really hard to see.)
To clarify my motivation here: Initially this thread was mostly meant as a heads-up; I am pretty sure something needs to give (see my example) so IMO Rust programmers should avoid writing such code until someone figures out a way to actually make that possible in a consistent way. (The same applies to C programmers IMO, but I have little stake in that.) I think it would not be wise to tell people that they can transmute between pointers and integers when there is AFAIK no proposal on the table (and certainly nothing accepted by LLVM) for doing that in a way that is compatible with widely accepted optimizations. The question of such transmutes is brought to the UCG occasionally, so I created an issue that we could point people to.
I am not entirely sure with which part of this you disagree.
I'm having trouble finding details on PVNI (and other prior art/proposed provenance semantics), which seem relevant to this discussion. Is there a convenient collection of resources somewhere?
You are (in this issue) proposing that not only is reading a pointer as an integer via pointer punning UB, but all transmute-like operations are. This is more restrictive than C, which allows union punning and the direct transmute equivalent of mempcy(&integer, &pointer, size).
C is underspecified. It seems to allow many things but if you take them together you get a contradiction with optimizations that people also say it allows. So there is no way to make a definitive comparison with C until all these ambiguities in the spec are resolved.
It is a stretch to read the current C specs as forbidding it, current code relies on it, the proposals for a more comprehensive description of provenance explicitly allow it. I do not think it is remotely unfair to say that C allows it.
No, there is the alternative I said right there, namely to not completely forget pointer-to-integer casts (at least not when followed by a store of that integer into memory which isn't having alias info tracked), because, taking C's draft as inspiration, that's incorrect by PVNI.
I don't know what semantics you mean to sketch here.
For all my examples, you either have to declare the source program UB, or you have to disallow one of the optimizations it performs. So which one shall it be? There is the transmute example, and the with
restrictyou cannot remove a dead cast example.
I am saying that at least one reasonable solution is the same style as what you mentioned on the mailing list - that let val = qaddr as usize; -> let val = *storage_usize; is incorrect because it is removing knowledge of the escape of qaddr (assuming that the control flow dependency isn't sufficient). This is where the proposed C rules seem like they'd fix the issue, it is the same style of fix as "inttoptr(ptrtoint(x)) is not a no-op", and it doesn't break optimizations except when doing ptrtoint. It also has plenty of room for smarter compilers or more complex standards to permit erasing it while keeping the relevant knowledge.
I am not entirely sure with which part of this you disagree.
I disagree that it is at all likely that C will forbid this (will be /able/ to forbid this, even), and thus it is not reasonable to break backwards compatibility (in the nebulous existence of "promises rustc makes in the absence of a full spec"). If you disagree that this has been promised then I'd say if nothing else the current transmute API docs only saying "it's safer to use as" imply "but the example code is still correct, just easy to typo without warning"
I'm having trouble finding details on PVNI (and other prior art/proposed provenance semantics), which seem relevant to this discussion. Is there a convenient collection of resources somewhere?
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2577.pdf is the source I have been using there.
Thanks @talchas!
It is a stretch to read the current C specs as forbidding it, current code relies on it, the proposals for a more comprehensive description of provenance explicitly allow it.
Explicitly allows it when using union fields, where the compiler can statically see that this might be a ptr-to-int transmute. I doubt they can support this for memcpy.
Also that proposal does add side-effects for these "escaping" operations, so it quite explicitly disallows optimizations that compilers perform, in particular LLVM. I have my doubts that they will stop doing that, so we will see to what extend this proposal really helps here.
I do not think it is remotely unfair to say that C allows it.
Well, I will accept that C allows it once there is a precise spec that allows it and a compiler that actually implements that spec.
Back to things more relevant for Rust:
I am saying that at least one reasonable solution is the same style as what you mentioned on the mailing list - that let val = qaddr as usize; -> let val = *storage_usize; is incorrect
Okay, so you are saying one should not remove redundant stores that store the value that was just loaded. It's not my favorite solution, but it is certainly worth considering.
But this is not a complete fix. At this point you have basically accepted that doing a ptr-to-int transmute is doing the same as a ptr-to-int cast. My other example shows that removing ptr-to-int casts whose result is unused is incorrect. So if we use your fix, I claim we have to accept that removing loads whose result is unused is be incorrect (unless we know for sure they are not loading a pointer value). Do you think that is acceptable (or do you disagree with this claim)? Dead load elimination seems pretty fundamental to me so I would be rather surprised if many people found this acceptable.
Explicitly allows it when using union fields, where the compiler can statically see that this might be a ptr-to-int transmute. I doubt they can support this for memcpy.
memcpy is afaik even more general than a union pun, and is the standard recommended way in C++. I really don't think they can forbid it, though it's certainly possible that the reason the proposal doesn't talk about it is because they couldn't find a way to model it.
At this point you have basically accepted that doing a ptr-to-int transmute is doing the same as a ptr-to-int cast.
Yes, that was absolutely my intent. (Whether there's hidden problems with that that I have missed...)
So if we use your fix, I claim we have to accept that removing loads whose result is unused is be incorrect (unless we know for sure they are not loading a pointer value).
Only if the compiler is tracking provenance information of pointers stored in memory that may alias this integer load. The alias requirement should avoid any performance loss for strict-aliasing C, and I hope can do the same for safe rust? A compiler/model which doesn't track provenance in memory at all has to only keep stores instead (or "eliminate" them into provenance.escape(x)). A compiler which does track provenance in memory locations but has a more explicit aliasing model can replace a dead load with a similar construct, and then turn dead-except-for-provenance stores into escape().
Only if the compiler is tracking provenance information of pointers stored in memory that may alias this integer load. The alias requirement should avoid any performance loss for strict-aliasing C, and I hope can do the same for safe rust? A compiler/model which doesn't track provenance in memory at all has to only keep stores instead (or "eliminate" them into
provenance.escape(x)). A compiler which does track provenance in memory locations but has a more explicit aliasing model can replace a dead load with a similar construct, and then turn dead-except-for-provenance stores into escape().
Rust only has alias information in references and special constructs (Like Box), right? So what you are proposing is to make it so simply using raw pointers instead of references loses some more optimizations?
Rust only has alias information in references and special constructs (Like Box), right?
Only provides additional alias information more than what the compiler can already infer, but yes.
So what you are proposing is to make it so simply using raw pointers instead of references loses some more optimizations?
Yes, if the compiler currently tracks alias info in some particular ways, doesn't add any internal information to regain the ability, and doesn't already have the relevant alias info inferred. The most obvious sort of case is
fn foo(x: *const usize, y: *mut *mut i32) {
...
*y = ptr; //can't remove this (even if there's an immediately following *y = something_else;), given some different assumptions; fix is extremely trivial
let unused_int = *x; //can't remove this, given ralf's assumptions about the compiler; fix is potentially less trivial
// goal is that:
z = some_int as *const whatever;
// now compiler must assume that z can alias *y and ptr
}```
or without the pointers coming from outside of the function it would require sufficiently complex code that it can no longer track that `x` and `y` don't alias.
In exchange some constructs involving raw pointers that were common enough to be parts of entire library crates are no longer UB (safe transmutes for POD no-padding structs is the particular example I am thinking of).Also as a completely separate argument - pointer to integer transmutes in the std::mem::transmute sense don't have to rely on pointer type punning (disallowed by C, but allowed by -fno-strict-aliasing that LLVM supports) or memcpy punning (I say supported by C and encouraged by C++, but you disagree). They could be implemented by union puns, which the provenance draft explicitly calls out as allowed, so there's even less excuse in forbidding that because of "LLVM doesn't and maybe won't ever support it".
I think it would be possible for clang to add ptr2int and int2ptr operations as necessary at LLVM IR level when you do an union pun, in which case I think LLVM IR still won't support ptr2int transmutes.
Sure, in which case rust can do the exact same thing. transmute() has both input and output type available, and knows exactly what the programmer is asking for. It could in fact destructure every struct to find the pointers and ptr2int them in particular, and there is no excuse not to in a world where that is the only way LLVM supports doing the operation.
It sounds difficult to add all those operations while still being zero cost. Even if the ptr2int operations themselves are removed, if it's in a big loop the loop might be cleaned up too late, or it might change an inlining decision. Maybe that's fine, but the idea that transmute is a do-nothing operation is pretty ingrained.
If the question is whether a given transmute<T, U> (which is even supported in the docs!) is always UB or "compiler can't reconstruct the zero-cost memcpy" the choice should be obvious. I still hold that one of the other implementations will be supported by LLVM (and probably all of them) and thus it will be fine, but even in a world where none are there is a way forward.
Sure, in which case rust can do the exact same thing. transmute() has both input and output type available, and knows exactly what the programmer is asking for.
But that would make transmute() behave different from loading a casted pointer to the input value. This trick I mentioned doesn't work when casting the pointer type as at the point of casting the pointer it isn't possible to do the ptr2int cast as that requires the value to be loaded first. The pointer doesn't have to be valid, or there could be a data race when doing said load. It is also not possible to do the ptr2int cast when loading the value behind the pointer as by that point the original type is no longer known. transmute_copy(), which is a more general version of transmute() that doesn't require the from and to size to be identical is defined as being equivalent to loading a casted pointer and is literally implemented as such. This means that transmute() shouldn't do this trick too IMO.
And should instead just be hard UB against what the docs say and crates have relied on? (And transmute_copy probably /could/ do this too, though it's definitely more sketchy there)
An operation which is always incorrect seems very much against Rust's philosophy. If pointer to int transmutes are going to be UB then the only choice consistent with Rust I can see would be disabling them entirely and making any transmute::<*const _, usize>() calls hard errors, as an operation which is always unconditional UB (that is, there's no "surrounding circumstances" or invariants that could possibly make this operation correct, it's just flat out wrong) shouldn't be in Rust, regardless of whether it's an unsafe function or not.
Alternative to that, since I feel like that's not very palpable to most people, we should instead implement the proper code generation to allow for pointer to integer conversions, even if it means special-casing transmute::<*const _, usize>() to use the target backend's ptrtoint equivalent, much like how as works. If a backend can support *const _ as usize, it can support transmute::<*const _, usize>() with minor changes to the compiler. Yes, I'm sure there's some backends that don't actually allow this to happen, but at that point you're left in a situation that leaves me to question whether or not that backend is usable for Rust, regardless of pointer transmutes.
On a codegen level if there's a difference between bitcast *i32 %ptr to i64 and inttoptr *i32 %ptr to i64 that's not Rust's fault, that's a backend bug that they should fix. The shortcomings of theoretical backends should not affect Rust's implementation decisions, especially when Rust's current backend does support this.
we should instead implement the proper code generation to allow for pointer to integer conversions, even if it means special-casing transmute::<*const _, usize>() to use the target backend's ptrtoint equivalent, much like how as works.
The transmute doesn't necessarily have to be directly from a pointer to an integer. It could also be inside a struct, or maybe even behind a pointer itself. If LLVM doesn't allow transmuting between pointers and integers, we can't support the general case without lowering raw pointers to integers at the LLVM level and only inserting inttoptr just before a load or store. Doing so would however prevent a lot of optimizations.
@Kixiron I think (as illustrated in the example in Ralf's first message here) the problem is not limited to just transmute, but is also present if you perform the equivalent of transmute through pointer casts and special casing transmute wouldn't fix that. Special casing transmute also raises the question of what would you do if you're transmuting between types with pointers in them?
#[repr(C)]
struct A {
a: *mut u8,
b: usize
}
#[repr(C)]
struct B {
a: usize,
b: *mut u8
}
// What does transmute::<A, B>() do? Is it "special" or not?Nested pointers are definitely less than ideal, but I again bring up the question of "what's the point of an operation which can never possibly be correct?"
Even if the solution is less than optimal for things like nested pointers, that's still better than having something which always produces an ill-formed program, the only choices in-line with Rust's philosophy are either banning any sort of pointer to int transmutes (no matter the nesting level) or making behavior defined and either fixing the backends or working around them with its codegen
Only if the compiler is tracking provenance information of pointers stored in memory that may alias this integer load.
I don't think we will get very far without preserving provenance in memory. Note that even local (let) variables are stored "in memory". So if provenance is lost when storing data to memory, that basically means there is no provenance worth speaking of. (Yes one could introduce unnecessary complexity by making let variables be stored in some other place, but there's really no good reason to do that, and load forwarding would still be broken, which is actually a pretty important optimization -- much more important than dead store removal.)
Also as a completely separate argument - pointer to integer transmutes in the std::mem::transmute sense don't have to rely on pointer type punning (disallowed by C, but allowed by -fno-strict-aliasing that LLVM supports) or memcpy punning (I say supported by C and encouraged by C++, but you disagree). They could be implemented by union puns, which the provenance draft explicitly calls out as allowed, so there's even less excuse in forbidding that because of "LLVM doesn't and maybe won't ever support it".
I suppose one could exploit the fact that we know that the load is "type-punning" to make it carry different rules -- maybe even making assumptions about the possible source types, though once the union has more than 2 variants that does not seem possible any more. That sounds like a big hack to me that just waits to fall down, but there is also a more concrete technical problem: such loads would then have to carry out ptr-to-int casts which are side-effecting and cannot be removed even if their result is ignored.
An operation which is always incorrect seems very much against Rust's philosophy. If pointer to int transmutes are going to be UB then the only choice consistent with Rust I can see would be disabling them entirely and making any transmute::<*const _, usize>() calls hard errors, as an operation which is always unconditional UB (that is, there's no "surrounding circumstances" or invariants that could possibly make this operation correct, it's just flat out wrong) shouldn't be in Rust, regardless of whether it's an unsafe function or not.
Transmuting () to ! is also never possibly correct. Or transmuting 2u8 to bool. So I don't quite understand what you even mean here -- there are many things transmute is never allowed to do, and Rust does not make an attempt to catch all of them (though having more lints to catch some of these cases would certainly be a good idea). Transmuting a ptr to an int would be just one more thing on that list. (And it's not even always UB, transmuting 8usize as *const i32 back to an int is fine.)
Transmuting () to ! is also never possibly correct. Or transmuting 2u8 to bool.
Neither of these are good comparisons, uninhabited types have a very unique situation and more often than not the compiler will generate a panic for them anyways, like creating a zeroed() uninhabited type. Likewise, the boolean case is one of an invalid value, not the fact that turning a byte into a bool is always 100% wrong
uninhabited types have a very unique situation
Not really, they just have an unsatisfisable validity invariant. The reason the transmute is invalid is hence because the value () is invalid for type ! -- same as in my bool example, and same as (I am proposing with) with ptr-ot-int transmutes.
Likewise, the boolean case is one of an invalid value, not the fact that turning a byte into a bool is always 100% wrong
Ptr-to-int transmutes are also just another example of an invalid value: what I am proposing is that the validity invariant for integers says that the value must not have provenance. So this is really exactly like the bool situation.
"have an unsatisfisable validity invariant" is a very unique situation.
I don't think it is or should be, at least not in any way that is relevant to this thread. Also I think we are digressing.^^
It is not a digression. As Kixiron said:
If pointer to int transmutes are going to be UB then the only choice consistent with Rust I can see would be disabling them entirely
Which actually applies equally to transmuting ptr/int and transmuting ()/!. If we know that the transmutation will always be illegal regardless of what value you pass in, then just statically block the transmutation ahead of time.
I ptr to int transmute would be valid if you did an int to ptr transmute first to create the pointer I would guess or maybe even if you did an int to ptr cast.
Which actually applies equally to transmuting ptr/int and transmuting ()/!. If we know that the transmutation will always be illegal regardless of what value you pass in, then just statically block the transmutation ahead of time.
a) This does not help for the purpose of this discussion, since one can still do the transmute via raw ptr casting, so the original question remains. We cannot statically detect all cases of this happening. Hence whether we can statically detect some of them does not fundamentally matter. (We should detect as many as we can, but that is a separate issue from discussing what happens when the transmute actually happens.)
b) As I already said above: it's not even always UB, transmuting 8usize as *const i32 back to an int is fine. This is specifically about transmuting away provenance. I guess I should have made that more clear.
Only if the compiler is tracking provenance information of pointers stored in memory that may alias this integer load.
I don't think we will get very far without preserving provenance in memory. Note that even local (
let) variables are stored "in memory". So if provenance is lost when storing data to memory, that basically means there is no provenance worth speaking of. (Yes one could introduce unnecessary complexity by makingletvariables be stored in some other place, but there's really no good reason to do that, and load forwarding would still be broken, which is actually a pretty important optimization -- much more important than dead store removal.)
Some of that varies depending on whether we're talking about provenance-as-a-spec or provenance-as-compiler-optimizations, as in the latter case many/most will have turned into llvm variables by the time anything is relevant. More important however is the "may alias" part. If the compiler is tracking provenance/alias info for a pointer stored into memory, in order for this to be useful at all it needs to know that most other pointers being used don't alias that memory. For the specific case of transmute-via-memcpy, it's local and probably not even spanning basic blocks.
As a spec, yes they would definitely want to be just considered part of the value in all locations, but as a spec it's also just fine to say that loading a pointer value as an integer has the side effect of marking its provenance as leaked. (Possibly with an exception for memcpy or sufficiently-memcpy-like functions like the C draft)
Also as a completely separate argument - pointer to integer transmutes in the std::mem::transmute sense don't have to rely on pointer type punning (disallowed by C, but allowed by -fno-strict-aliasing that LLVM supports) or memcpy punning (I say supported by C and encouraged by C++, but you disagree). They could be implemented by union puns, which the provenance draft explicitly calls out as allowed, so there's even less excuse in forbidding that because of "LLVM doesn't and maybe won't ever support it".
I suppose one could exploit the fact that we know that the load is "type-punning" to make it carry different rules -- maybe even making assumptions about the possible source types, though once the union has more than 2 variants that does not seem possible any more. That sounds like a big hack to me that just waits to fall down, but there is also a more concrete technical problem: such loads would then have to carry out ptr-to-int casts which are side-effecting and cannot be removed even if their result is ignored.
.... yes, if ptr-to-int conversions can't be removed they can't be removed, no matter what form they come in. (They could however be converted into other, cheaper ptr-to-int conversions or markers by a compiler that has finished implementing that solution to "do ints have provenance")
(And it's not even always UB, transmuting
8usize as *const i32back to an int is fine.)
[The other arguments re making it an error have been reasonably dealt with by others]
This is true, ugh, though there would be something to be said for making it an error anyways in that world.
Some of that varies depending on whether we're talking about provenance-as-a-spec or provenance-as-compiler-optimizations,
When we talk about provenance in the context of Rust, we always mean an explicit bit of state in the abstract machine, not just some emergent property that arises in compiler analyses. (Also see the glossary.)
as a spec it's also just fine to say that loading a pointer value as an integer has the side effect of marking its provenance as leaked.
No, it's not -- or, well, it's "fine" in the sense of "possible and well-defined" but not good. It means optimizations cannot remove dead loads or redundant stores (of values that were just loaded). That is the entire point of this thread...
Fundamentally this problem is about how to enable optimizations without making life unreasonably difficult for people writing unsafe code.
One "sledgehammer" option would be to create an attribute #[allow_integer_pointers] or something, which you whack on a function, and it has the effect of translating all integer types within that function into byte types within LLVM.
This makes it really easy to eg. write a custom memcpy - you just stick that attribute on your functions, whilst the vast majority of (even unsafe) code can benefit from integers != pointers.
as a spec it's also just fine to say that loading a pointer value as an integer has the side effect of marking its provenance as leaked.
No, it's not -- or, well, it's "fine" in the sense of "possible and well-defined" but not good. It means optimizations cannot remove dead loads or redundant stores (of values that were just loaded). That is the entire point of this thread...
No, it does not, it means that they cannot remove integer loads that might be of provenenced values in memory. And it doesn't even fully mean that, if the compiler can handle track that information without keeping the load around to do so implicitly.
One "sledgehammer" option would be to create an attribute
#[allow_integer_pointers]or something, which you whack on a function, and it has the effect of translating all integer types within that function intobytetypes within LLVM.
Has there actually been serious discussion of byte in LLVM after the mailing list discussion which seemed very negative?
Is it possible for the actual pointer type-punning (casting from a pointer to pointer to a pointer to int) to not be a no-op and clear provenance accordingly?
Afaik Miri currently has no concept of provenance, but it'd be nice to do some experimentation on this and tease out a model.
Is it possible for the actual pointer type-punning (casting from a pointer to pointer to a pointer to int) to not be a no-op and clear provenance accordingly?
Yes -- that basically means performing a ptr-to-int cast as part of the load. Which has a lot of problems as discussed previously in this thread.
Miri does have a concept of provenance and uses it to do proper checking for things like wrapping_offset and Stacked Borrows.
If rust adopts a model similar to what's proposed in rust-lang/rust#95228 / rust-lang/rust#95241, where ptr as usize is:
//ptr.addr() -> usize docs:
/// Gets the "address" portion of the pointer.
///
/// This is equivalent to `self as usize`, which semantically discards
/// *provenance* and *address-space* information. To properly restore that information,
/// use [`with_addr`][pointer::with_addr] or [`map_addr`][pointer::map_addr].Meaning it strips provenance, could ptr-to-int transmutes (And "user implemented memcpy", etc) be made not insta-UB? And instead be equivalent to the as cast and discard provenance.
Looking at the example from #286 (comment) I think this part would become UB:
let val = qaddr as usize;
*storage_usize = val;
**storage_ptr = 1;Since it is writing through a pointer without provenance which was created via as usize, which answers the question of which part is UB.
Ralf mentioned this possibility under that comment:
Possibly there is a way that we could salvage ptr-to-int transmutes if we give up on int-to-ptr transmutes, but (a) that feels even less natural, (b) I have no idea how to do this, and (c) I am not sure if that would actually help anyone; the people transmuting between ptrs and ints probably assume that going both ways is fine. We have to lose one way, and I think losing ptr-to-int transmutes is "less weird".
I think it would make the model easier to understand if a naive memcpy did not trigger UB for types with and without (provenance-carrying) pointers.
EDIT: I'm also a bit confused why we would need to give up on "int-to-ptr transmutes". Couldn't it yield a pointer with invalid provenance, but a valid address? It could only be used to get the address part.
I mean, regardless of the provenance rules in the end this is easy for a spec, easy for miri, valid in clang -fno-strict-aliasing (aka LLVM), and in terms of permitted optimizations is basically just a hack to recover some TBAA. (Said hack may be useful in an SB world, but that should really have an example showing it via SB aliasing rules)
Aria has a great blog post describing all the things that would be needed to be able to target something like CHERI. Are we open to the implications of CHERI?
Perhaps then we don't lose the redundant store elimination with (1).
Proposal
-
inttoptrdeletes provenance information (integers are dumb) -
Reading/writing the result of
inttoptris always UB -
ptrtoint(inttoptr(i))=i("integers are dumb") -
inttoptr(ptrtoint(p))may be optimized top("the compiler may fix a pointer")
Mental model
type usize = u64; // whatever size but no provenance
struct ptr {
provenance: Option<Provenance>,
address: usize
}
/// Any pointer-sized, pointer-aligned value in memory
type ValueInMemory = ptr;- Load or store to a pointer without provenance is UB
- Pointer-type loads and stores do the obvious thing: they keep
Option<Provenance>intact between memory and the expression inttoptrandptrtointthemselves are legal, but you can only roundtrip one way.
Redundant store elimination
To recover redundant store elimination from the original post, let's redefine integer loads+stores in terms of pointer loads+stores:
load int from pdefined asptrtoint(load ptr from p)store int i to pdefined asstore ptr inttoptr(i) to p
Assume we have redundant store elimination on pointers. Then redundant store elimination automatically falls out for the example in the top post.
Known-tricky cases / previous work
-
Chung-Kil Hur's example (as described on https://www.ralfj.de/blog/2020/12/14/provenance.html) is not an issue — the original program dereferences an ptr→int→ptr cast, which I propose is UB (for reasons that Aria describes).
-
Same for the example in LLVM#34548 — the original is already UB.
I suspect that any naughty program that uses memory to type-pun ints and pointers will have to use inttoptr. Then the resulting pointer is useless — you can only use it as an integer or cause UB.
But I'm not certain that there are no problems remaining.
Am I missing something silly?
We are a bit ahead of you over at rust-lang/rust#95228
could ptr-to-int transmutes (And "user implemented memcpy", etc) be made not insta-UB?
That is certainly the easiest solution. It is what Miri implements with -Zmiri-check-number-validity.
But indeed the example vaporizes (like most of them do) when we ban ptr2int2ptr roundtrips, as strict provenance does. That said, for transmutes specifically, some questions remain:
unsafe fn deref(left: *const u8, right: *const u8) {
let left_int: usize = mem::transmute(left);
let right_int: usize = mem::transmute(right);
if left_int == right_int {
let left_ptr: *const u8 = mem::transmute(left_int); // <--
let _val = *left_ptr;
}
}
let ptr1 = &0u8 as *const u8;
let ptr2 = &1u8 as *const u8;
deref(ptr1, ptr2.with_addr(ptr1.addr()));Is this program as written allowed? If we say that a ptr2int2ptr transmute roundtrip is a NOP (because transmutes are NOP so what else could it be), then this program is fine since it will deref ptr1.
However, the compiler is allowed to replace left_int with right_int at the place that I marked. The new program however dereferences ptr2.with_addr(ptr1.addr()), i.e. the provenance of ptr2 for the address of ptr1; that is clearly UB.
Since the optimization of replacing one integer by another based on == is definitely correct, this means the original program must already have been wrong. The question is, why? Which rule it is violating?
I posit that ptr-to-int transmutes are UB, and that's why the program is wrong. Anyone who wants to allow ptr-to-int transmutes has to find some other reason for why this program has UB.
@JakobDegen suggests we could alternatively say that when bytes with provenance are interpreted at integer type, we just drop the provenance. (No "broadcast" side-effect or so, the provenance is irrecoverable.)
This could work, if we have a general theorem that says: adding provenance to any byte without provenance will never change program behavior or introduce UB. (We need that provenance to justify removing self-assignments like x=x; that interpret a bunch of bytes at a given type, and turn them back into bytes unchanged.)
Whether it is what we want is a different question. This model still means that memcpy implemented with u64 chunks is buggy since it loses provenance of pointers in the copied data. IOW, this still does not let you use integer types as "universal containers" for losslessly transfering any kind of data (including pointers with their provenance).
"ptr2int2ptr transmute roundtrip is a NOP" where "NOP" includes "does not reduce optimizations" would clearly require integer provenance.
Assuming we don't want to open up that can of worms, then if mem::transmute int2ptr/ptr2int are allowed they very clearly need to be equivalent to one of the flavors of ptrtoint-the-instruction, whether that's with the "broadcast" sideeffect or strict provenance's "provenance is gone, you can't get it back".
"Broadcast" would require either being mem::transmute being different from pointer punning, or possible global optimization losses (see "the whole rest of this issue"). "Strict" seems like a bad fit in general unless as is also "strict", as now the roundtrip leaves you with an unusable pointer.
UB seems strictly worse than the already meh "compiler error found at monomorphization of transmute". (And both violate the implication in the docs that this is well defined, just using unnecessary power compared to as)