Stacked Borrows: track raw pointers more precisely

[RalfJung]

Currently, Stacked Borrows teats all raw pointers as identical -- if any raw pointer is allowed to access some memory, then all are. This does not reflect LLVM's pointer treatment though, and it leads to confusing behavior (e.g. rust-lang/miri#1526).

I have long planned to make tracking more precise, but there's a big open question in how to handle integer-pointer casts. We cannot (and do not want to) track integers, so we have to somehow mark memory as "integer-available" when casting to int, and then use that when casting back from an int.

[bjorn3]

We cannot (and do not want to) track integers, so we have to somehow mark memory as "integer-available" when casting to int, and then use that when casting back from an int.

When getting a raw pointer as argument it would be unknown if the raw pointer is "integer-available".

[RalfJung]

When getting a raw pointer as argument it would be unknown if the raw pointer is "integer-available".

Sure. But that's fine. This is something optimizations have to live with, but that is likewise true in C/C++.

LLVM IR has some bugs in this area, but obviously there's no way to design a semantics for a buggy optimizer. So the only real guidance we have is to allow as little as possible but as much as needed.

[chorman0773]

In #263 (now closed because it duplicates this), I mentioned that the current model is suprising to me, and at issue with the working model I have for lccc (which is incredibly desireable because of the optimizations it enables, a small example of which is in that issue). lccc tracks raw pointers exactly the same as it tracks references, because it treats all pointers (of which references and raw pointers are both subsets) the same.

As for int->pointer casts, that is fun, but the rule that C++ (and thus lccc) has is that if you (reinterpret_)cast a pointer to an integer, and (reinterpret_)cast that integer back to a pointer type, you get the same pointer, provenence and all (if multiple pointers were cast to the same integer, you get whichever one gives the code defined behaviour, if possible).

[RustyYato]

if multiple pointers were cast to the same integer, you get whichever one gives the code defined behaviour, if possible

@chorman0773 what happens if multiple pointers give the code defined behavior, is that not possible?

[chorman0773]

what happens if multiple pointers give the code defined behavior, is that not possible?

In C++, at least, that's not possible. The only way this would work is if you had multiple objects of the same type at that address, which is not possible. In rust, I also don't think it's possible, necessarily. However, the actual chosen one would be unspecified (but note that in all cases, this is somewhat oversimplified).

[comex]

There isn't really any C++ rule on how provenance works. The C and C++ committees are progressing towards adopting one, but this is a recent development, and the current specs say very little about it, leaving it unclear whether integers have provenance and even whether provenance exists at all. Meanwhile, among major C++ compilers, at least GCC and Clang have open bugs regarding how exactly pointer<->integer conversions should be optimized. That's part of what makes coming up with rules for Rust so difficult, especially since Rust is somewhat bound to whatever memory model LLVM ends up with.

[sollyucko]

Would something along these lines make any sense? (Assuming no issues with e.g. LLVM)

• References always have a memory region of provenance, and must always be valid
• Pointers have an optional "memory region of provenance" they are allowed to access, and may be transiently invalid
• Integers store no provenance information
• Reborrowing a field of a reference: memory region of provenance is just that field (plus any other relevant SB info is copied as normal, I'm not sure if that's a thing)
• Converting a pointer to point to a field (without going via references or integers!): same provenance
• Reference -> pointer: the pointer has the memory region of provenance of the original reference
• Pointer -> integer: integers do not track provenance
• Integer -> pointer: the pointer has no memory region of provenance, i.e. unrestricted
• Pointer -> reference:
  • UB occurs if the range, starting at the pointer's address and with a size of size_of::<T> bytes, does not point within the intersection of the memory region of provenance of the pointer and the union of: the memory regions of provenance of all pointers (except those with no region of provenance) and references accessible from that point in the code, the memory used to store each static (and leaked boxes?) (except static muts or UnsafeCells?) (hmm... what about some sort of SB-based rule about disallowing illegal aliasing?), and any memory not managed by the Abstract Machine (e.g. hardware-defined memory-mapped I/O).
  • The memory region of provenance is the size_of::<T> bytes at/after the address
• Pointer reads/writes apply the same rules as converting to references

A few corollaries:

• Reference -> pointer -> reference: no effect
• Pointer -> integer -> pointer: destroys/expands the memory region of provenance
• Integer -> pointer -> integer: no effect
• Pointer -> reference -> pointer: asserts that the address range is within the original provenance and within the memory accessible from that point in the code, then restricts (note that this is only guaranteed to be a restriction as a result of the previous assertion) the provenance to point to just the size_of::<T> bytes at/after the address
• Reference -> pointer -> integer -> pointer -> reference: no effect
• Integer -> pointer -> reference -> pointer -> integer: asserts that the address range is within the memory accessible from that point in the code

Note: I'm not very familiar with Stacked Borrows, so I'm not sure of the details of how that would work with this.

[chorman0773]

ptr->int->ptr expanding provenance is one of the things I do not want. The code I showed in the linked issue was an exposition as to why that would be undesirable. I'd be fine with it destroying provenance, or allowing the previous provenance of the pointer to pop up elsewhere (provided the borrow item still exists), but allowing it to extend without bound negates every other rule in whatever list you may use.

[sollyucko]

FWIW, here is how I would analyze the does_something function you mentioned in #263, as called by either do_interesting_things, in a way that makes it UB:

pub unsafe extern "C" fn does_something(
    ptr: *mut usize // memory region of provenance: array[0]
){
    let ptr = std::transmute( // memory region of provenance: none
        std::transmute<usize>( // memory region of provenance: N/A
            ptr // memory region of provenance: array[0]
        )
    ) as *mut Interesting;

    // <see below>
    (*ptr).exclusive_access = ptr as *mut ();
}

This write implies a pointer-to-reference conversion, which has the following preconditions:

• The address range must be within the original provenance. => Trivially true
• The address range must be within the memory accessible from here. => This FAILS:
  • The relevant contributions to the memory accessible from here are:
    • The original ptr argument, which has a provenance region of array[0].
    • The new value of ptr is not included since it has no provenance region. (I have clarified my previous reply to state this, sorry.)
  • This means that the entire Interesting struct at ptr is not accessible, thereby triggering UB.

[RalfJung]

ptr->int->ptr expanding provenance is one of the things I do not want

I think this is impossible to avoid. Specifically, the only way to avoid it is to give integers provenance, and that has all sorts of even-less-desirable consequences, or to give pointers no provenance, and that kills most of the alias analyses that LLVM, GCC and likely also lccc do.

I am not saying I like the fact that ptr->int->ptr is not a NOP. But this is an unfortunate consequence of a bunch of other properties that it would be even more problematic to lose.

Basically, provenance and integer-ptr-casts are mutually incompatible. Most languages only have one: Java, ML and other high-level languages have provenance but no integer-ptr-casts; assembly has integer-ptr-casts (well it doesn't even need a cast, there simply is no distinction) but it does not have provenance. If you want to have them both in the same language, there will be suffering and non-intuitive behavior. I believe this to be unavoidable, and I will soon (finally) publish the blog post laying down this argument in more detail.

[chorman0773]

I think this is impossible to avoid

Perhaps not. If converting back to a pointer is defined to assert provenance, I think there is a way to get that information. It can be pulled from the borrow stack.
If there is an item for the location that has been converted to an integer, that item is used (do not pop items from the borrow stack in this search). Otherwise, the resulting pointer is invalid/dangling and cannot be dereferenced.
Alternatively, it could be called a "deferred" pointer, which has similar semantics to untracked raw pointers, which, when dereferenced/reborrowed, it looks for a valid borrow item that is usable, and has been converted to an integer.
In the former case, it wouldn't care about the actual size, in the latter it would. This may not be a perfect specification, but it may be enough to save provenance of pointers converted to integers.