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

(Edited together with @RalfJung)

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.

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. And in fact, this is exactly what already happens today: we end up with the program println!("So much RAM!");. This will perform the println. Either this is a compiler bug, or our reasoning about the finiteness of the address space is wrong.

Declaring this a compiler bug would have pretty disastrous consequences: we would basically have to say that it is illegal to remove allocations from the program. In particular this would make it impossible for the compiler to entirely optimize away local variables that have their address taken, as those are allocations.[^non-addr-taken]

[^non-addr-taken]: Local variables that do not have their address taken are also allocations, but it is conceivable that we could play tricks with those in the opsem. But the moment you create an &self method on a local variable, making it a piece of regular addressable storage is pretty inevitable.

A Solution and a Problem

We therefore have to accept that the address space exhaustion reasoning we did has to be wrong. On the AM level, this means we need to be able to have infinitely many distinct pointer values. And indeed, we have that already due to pointer provenance! So far, provenance was only used to determine whether a memory access is legal or not, but it could not affect the outcome of that access. If we take one further step and say that provenance can be used to disambiguate which memory is even meant by a given access, we can easily explain the behavior of the progrma above: alloc can return the same address multiple times, with different provenance, and each memory access uses the provenance to figure out which of the "overlapping" allocations was meant.

This solution, aside from being deeply unintuitive, also causes new problems. Programmers both in safe and unsafe code 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. This could be used, for instance, as a fast-path when comparing two &[u8] to skip the memcmp if both slices point at the same address.[^fast-path]

[^fast-path]: The standard library had such a fast-path for a long time but it got removed many years ago. However, the memcmp that we call to compare &[u8] likely still has a similar fast-path.

Without going into all the details, there are promising models that can keep pointer equality ptr1 == ptr2 actually useful. However, under those models, ptr1.addr() == ptr2.addr() becomes different from ptr1 == ptr2. This directly contradicts 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

We propose to remove the guarantee from the docs which says that ptr1 == ptr2 is the same as ptr1.addr() == ptr2.addr(), and instead explicitly document that they are not the same.

ptr1.expose_provenance() == ptr2.expose_provenance() remains a valid way to compare pointers. However, under all models we have found so far, expose_provenance() is a much bigger optimization barrier than addr() or ptr::eq() so it should be avoided in performance-sensitive code. (See below for more details.)

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

As mentioned above, the intent is to ensure that ptr1.expose_provenance() == ptr2.expose_provenance() remains a valid way to compare pointers. So we want to have that if ptr1.expose_provenance() == ptr2.expose_provenance() { assert_eq!(*ptr1, *ptr2); } never panics, which we gave up on for addr. The solution is to sacrifice optimizations (for expose_provenance instead of addr) instead: expose_provenance becomes an optimization barrier; it cannot be optimized away and it prevents reordering.

Note that already before this proposal, expose_provenance has a side effect (it mutates the global set of exposed provenances), and so it cannot be removed even if the result is unused. However, we are still miscompiling expose_provenance today, so current benchmarks do not show the performance impact of expose_provenance being an optimisation barrier. The models we found so far that fix address space exhaustion all make expose_provenance an even bigger optimization barrier: it is no longer willreturn, i.e., the compiler can no longer move potentially-UB operations from after the expose_provenance to before, or hoist expose_provenance out of a loop that may never run.

addr remains available as a better-optimized alternative, if you can live with its semantics.

A Proposed Solution

Instead of a single address space, we imagine we have many full address spaces, which we call planes. The full location of an allocation is given by its plane and its address within the plane. Allocations are always contained within a plane and cannot overlap -- but multiple allocations can be at address 0x42 in different planes! The address part of this pair is stored in the actually physically represented 64-bit address of the pointer, while the plane is only stored in provenance, i.e., AM-only "ghost" state.

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.

More formally (if you have time)...

A pointer consists of four parts:

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,
}

(A different approach would be to store the allocation ID, and have the plane for each allocation stored in the global table with metadata about all allocations.)

The plane allows us to have as many "address space copies" in the AM as we want, so you never run out of address space. addr() simply gives you the hardware address:

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

Equality checks both the hardware address and the plane:

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

No side effects, no NB, perfectly optimisable. But not the same as comparing the hardware addresses.

You can also do Ord, just take the lexicographic order on the pair (plane, cpu_addr), i.e. first compare the plane, if equal compare the hardware address.

Only expose_provanance() is miserable... One reason is you want ptr1.expose_provenance() == ptr2.expose_provenance() to compare the pointers, not only addresses. The deeper reason is that from_exposed_provenance() becomes crazy otherwise. So what we do is that we force all exposed allocations to live in the same "plane", let's say plane 0. If the pointed-to allocation is in a different plane, we just OOM.

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()
    }
}

Advantages:

• infinite address space, so you can remove dead allocs or deallocate early if no pointer to the allocation is ever passed to expose_provenance()
• Ptr::addr() and Ptr::eq() have no side effects, and don't really form an optimisation barrier in any way
• No NB, angelic choice or other questionable things
• No infinite integers or provenance on integers

Disadvantages:

• If you want to compare pointers, you have to compare the pointers, not their addresses
• expose_provenance is not willreturn, it can abort execution if the allocation was on the wrong plane

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