What about: Pointer-to-integer transmutes?

[RalfJung]

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)?

1. We could drop the provenance. That would basically mean that the load of storage acts like an implicit ptr-to-int cast. The problem with this approach is that we cannot remove the redundant write at (1): the value in val is different from what is stored in storage, since val has no provenance but the ptr stored in storage does! 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.
2. We could preserve the provenance. Then, however, we end up with val having type usize and also having provenance, which is a big problem: the compiler might decide, at program point (2), to return val instead of return cmp (based on the fact that val == cmp), but if val could 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.
3. 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 https://github.com/rust-lang/unsafe-code-guidelines/issues/287 for a discussion with the goal of avoiding provenance in the first place.

[RalfJung]

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.

[Lokathor]

So, clarification question: Is this currently UB or will it eventually be UB under a future LLVM?

[Diggsey]

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.

[RalfJung]

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.

[RalfJung]

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 q immediately follows p in 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.

[digama0]

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.

[RalfJung]

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++.

[digama0]

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.

[Diggsey]

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)

[RalfJung]

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 https://github.com/rust-lang/unsafe-code-guidelines/issues/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.

[RalfJung]

@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.

[Diggsey]

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.

[RalfJung]

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.

[Diggsey]

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?

[RalfJung]

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.

[thomcc]

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)

[Diggsey]

(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...

[thomcc]

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).

[Diggsey]

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.

[thomcc]

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.

[RalfJung]

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.

[RalfJung]

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).

[thomcc]

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.

[RalfJung]

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.

[Diggsey]

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 -> pointer is valid. integer -> bytes -> integer is valid. But pointer -> bytes -> integer and the reverse is still invalid without an explicit ptrtoint/inttoptr cast.
• C/C++ char types 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.

[Diggsey]

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.

[RalfJung]

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.)

[carbotaniuman]

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?

[RalfJung]

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.

[carbotaniuman]

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).

[RalfJung]

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".

[carbotaniuman]

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.

[RalfJung]

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. ;)

[thomcc]

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.

[RalfJung]

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?

[thomcc]

Because they'd be safe to call, and no other as casts are unsafe.

[RalfJung]

Oh, fun times. But well, I think int-to-ptr transmtues are fine, so this is not necessarily a big issue.

[elichai]

Even for unsafe fn() which requires unsafe this isn't possible without transmute because function pointers are required to be non-null

[RalfJung]

Sure, the cast would need to be unsafe -- but that doesn't explain why there is no such cast.^^

[carbotaniuman]

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.

[RalfJung]

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.)

[carbotaniuman]

Hmm. Is this according to PNVi-ae semantics? I thought that might be the case, but I'm still trying to find a counterexample.

[RalfJung]

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.

[carbotaniuman]

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 :(

[Lokathor]

Rust also tells the tale "raw pointers are bad for your health"

[RalfJung]

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.)

[thomcc]

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).

[RalfJung]

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".

[RalfJung]

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. :)

[Ixrec]

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.