Out-of-memory, removing unused allocations, and pointer comparison vs address comparison

TLDR

There is the issue with our current operational semantics that unused allocations can technically not be removed (https://github.com/rust-lang/unsafe-code-guidelines/issues/328). There is no perfect fix; the most reasonable option is to make a pointer comparison ptr1 == ptr2 non-equivalent to ptr1.addr() == ptr2.addr().

The Problem

Consider a program which allocates memory in a loop; in pseudo-code:

let layout = Layout::new::<u16>();
for _i in 0..=usize::MAX {
    let _ptr = alloc(layout);
}
println!("So much RAM!");

Here alloc is some AM primitive which creates an allocation for a given layout, or aborts the process due to an out-of-memory (OOM) condition/stack overflow. It would for example be used by the language to allocate memory for local variables.[^only-ref-locals]

Clearly, the program is trying to allocate more memory than could possibly exist. Even with infinite memory, at some point we run out of address space: two of the ptrs returned by alloc would have the same address. Thus we deduce that the program must abort due to OOM, and never reaches the println.

However, each of the allocations is unused, so we would like to optimise them away.[^llvm] If we do so we end up with the program println!("So much RAM!");. This will perform the println. So the optimisation modified the observable behaviour the program might exhibit. That is bad![^bad-optimisation]

[^only-ref-locals]: Technically it would only be needed for locals which have a reference taken. Other locals could reside in some "magic" AM storage.
[^llvm]: LLVM obviously does this kind of optimisations today.
[^bad-optimisation]: It just means that the optimisation is not valid. So we cannot remove unused allocations, including ones for local variables.

A Solution and a Problem

There are of course solutions. It just requires us to have infinitely many distinct pointer values in the AM. And indeed, we have that already due to pointer provenance! But unsafe code authors would really like pointer equality to provide at least some useful guarantee. In particular, if ptr1 == ptr2 evaluates to true, and you happen to know that both are dereferenceable, it would be extremely surprising if *ptr1 == *ptr2 would evaluate to false.

We can make pointer equality ptr1 == ptr2 actually useful. But not ptr1.addr() == ptr2.addr() (without making addr a huge optimisation barrier). So ptr1 == ptr2 and ptr1.addr() == ptr2.addr() would have to be non-equivalent, directly contradicting the current documentation:[^unsized-types]

Pointer equality is by address, as produced by the <*const T>::addr method.

[^unsized-types]: Btw, I think this comment is wrong when T is an unsized type. As far as I understand equality of fat pointers also compares the metadata.

Proposal

There is no perfect solution to the problem. I think this is the best solution we have. (If you think there should be a better solution please read the Pick your Poison section below.) So I would propose we change the documentation (and add a warning regarding this to the documentation of addr) now, rather than ignoring the problem (which we have done until now) and having to change it years from now. There are still swaths of code not using the strict-provenance APIs, and they would hopefully see the updated documentation if/when they decide to upgrade.

Note that I don't think we need to commit to the exact semantics now (although there is a proposal that seems reasonable). It is just overwhelmingly likely that the solution is going to distinguish between pointer and address comparison, where only the former might give actually useful guarantees.

(@RalfJung suggested I create this issue.)

Details for the Curious

Sorry, this became quite an essay. Only read/expand what you are interested in.

Pick your Poison

As I said, there is no perfect solution:

Theorem (Impossibility Theorem).
In any "reasonable"[^*] semantics, you cannot have all of the following:

1. let _ = ptr.addr(); can be optimized away
2. let ptr = alloc(); dealloc(ptr); can be optimized away
3. integers do not carry provenance
4. ptr1 == ptr2 is equivalent to ptr1.addr() == ptr2.addr() (assuming thin pointers)
5. if ptr1 == ptr2 { assert_eq!(*ptr1, *ptr2); } never panicks (unless UB)
6. a fully safe program cannot hit UB

So pick your poison! What would you compromise on? (expand the item of your choice)

1. Bad for optimisations

   So addr is not pure. That means you cannot optimise away addr, but it also makes code motion optimisations much more difficult. In particular, you cannot sink a call to addr down some other function call f() unless you can prove that f() is guaranteed to return (not diverge and not unwind); otherwise you might have "optimised away" the addr() without knowing. addr was meant to be a pure alternative to expose_provenance, so it would optimise better. But now it suddenly optimises worse than expose_provenance used to.

   If you argue it can't be too bad, since expose_provenance is already impure and optimises quite nicely in practise, let me quote our LLVM expert Nikita Popov (nikic):

   [...] expose_addr() compiles to the same LLVM IR as addr()... (That is, it is not currently treated as having a side effect.)

   (Okay, you could have a 2-stage optimiser, where in the first stage addr is treated impure and thus a huge optimisation barrier, but unused allocations can be optimised away, and after that move to a world where addr is considered pure, but unused allocations can no longer be optimised away. This is strictly better than choosing item 2, but I think still leaves quite some unused allocations that you cannot optimise away.)

2. Bad for memory usage

   You can only remove unused allocations if you know the program will never exhaust the address space. But we allow life before main, so even in a hello-world program you cannot prove this. Recall that this does not only apply to heap allocations through the global allocator, but also local variables (at least if they have a reference taken). Pretty disasterous for memory usage! Now go and inform embedded people about this...

3. Ugly, and difficult to keep optimisations for integers

   Okay, so usize can have infinitely many values, and in fact they need to be distinguished by equality. So in particular,

   let addr = alloc().addr();
   for n in 0..=usize::MAX {
       if n == addr { println!("yes"); }
   }
   

   might not print anything. That is surprising. But also, how do you define operations like addition, multiplication and division on these integer values? LLVM does optimisations where it uses algebraic rules that hold for addition, multiplication, etc. to simplify computations, e.g. addition and multiplication are commutative and associative, multiplication distributes over addition, 0 is neutral for the addition and 1 is neutral for multiplication, etc. Do you ditch those optimisations? Maybe there is a semantics where most of these properties hold (I don't know), but it is going to be a complicated one.

4. I agree!

   With the strict-provenance project it already became quite clear that integers and pointers are just fundamentally different things. Distinguishing their equality comparisons fits in there quite naturally. And all our other options are quite horrible!

5. Pointer equality doesn't provide any useful guarantee

   What is the point of having an implementation of PartialEq on pointers, if there is literally nothing useful you could do with the result? No slice equality fast-path. No thread-ids using pointers. Unsafe code authors are going to like this...

6. That kind of breaks the key promise of Rust

   Okay, so you would say that a program which exhausts the address space has UB. But on 16- or even 32-bit targets it is actually imaginable that a program would run out of address space. And a simple memory leak could suddenly lead to undefined behaviour. And honestly, I would also be worried about reputational damage to Rust, given that "safe Rust is UB-free" is kind of the key promise Rust made.

[^*]: No, this is not going to save us. The assumptions are all really reasonable (at least much more than properties 1 to 6). Two examples: equality comparison on integers is pure (can be optimised away if the result is unused), and writing to one allocation shouldn't change the contents of another allocation.

How about expose_provenance?

(And recall that ptr as usize is equivalent to ptr.expose_provenance().) For deep technical reasons, address comparison on exposed pointers has to actually do the pointer comparison. So we cannot sacrifice item 4 in the Impossibility Theorem for expose_provenance. The solution is to sacrifice item 1 (for expose_provenance instead of addr) instead; in fact item 1 already didn't hold here. expose_provenance is impure by design. It still becomes a bit worse than it was, but

• expose_provenance was already quite an optimisation barrier (theoretically, still "miscompiles" with LLVM as far as I'm aware)
• there is the performant alternative of using addr if you adhere to strict provenance.

A Proposed Solution

Instead of a single address space, we imagine we have many full address spaces, which we call planes. For technical reasons related to pointer order comparison (PartialOrd), I prefer to index the planes by rational numbers (= fractions), rather than natural numbers or integers. Comparison of pointers also compares the plane. For order comparison, the proposal is to first compare the plane, and only if they are equal the address. The plane is chosen non-deterministically by the allocator. But to support expose_provenance and with_exposed_provenance, we treat plane 0 as special, and we enforce that every pointer that is ever exposed, lives in plane 0. This means that address comparison coincides with pointer comparison when both pointers have previously been exposed.

struct Ptr {
    /// The runtime address of the pointer on the actual hardware
    addr: usize,
    /// On CHERI you also have capabilities that tell what memory you are allowed to access,
    /// at hardware runtime
    cpu_cap,
    /// The "plane of allocation" as it is called in the UCG thread, exists in the AM only,
    /// together with `cpu_addr` this identifies an offset in an allocation
    plane: Rational,
    /// The provenance as we know it, which determines whether it is UB to perform a read or write
    /// through the pointer
    ghost_cap,
}

impl Ptr {
    fn addr(self) -> usize {
        self.cpu_addr
    }
}

impl Eq for Ptr {
    fn eq(self, other: Ptr) -> bool {
        self.cpu_addr == other.cpu_addr
        && self.plane == other.plane
    }
}

impl Ptr {
    fn expose_provenance(self) -> usize {
        if self.ghost_addr != 0 {
            oom()
        }
        // the actual "expose" as we previously thought of it
        // this writes this pointer to some global table of exposed pointers, but since we have no idea what
        // `with_exposed_provenance` does, we also don't know which parts of the pointer we actually need to store there
        self.actually_expose();
        self.addr()
    }
}

Links

• The UCG issue: https://github.com/rust-lang/unsafe-code-guidelines/issues/328
• The issue was recently discussed extensively on the t-opsem channel on zulip
• A proof sketch of the Impossibility Theorem is in that thread

Start by reading the current pointer equality and addr documentation linked in the issue, then review the referenced unsafe-code-guidelines discussion and the proposed semantics here. The issue names no implementation files or tests; done would require an agreed resolution for pointer-versus-address comparison and corresponding documentation changes.