What assumptions can safe-interface functions make about `&Cell`s of different types aliasing?

[ais523]

Background: Suppose we have two functions, each of which potentially uses unsafe code internally but presents a safe interface. f returns a value of some type T, and g takes a T as its argument. We want to prove that g(f()) is sound (i.e. no undefined behaviour), which means that anything that g assumes is true about its argument for its safety proof must be ensured by f, and that in turn depends on what g's safety assumptions are. As such, some explicit choice needs to be made for "the safety assumptions that a function with a safe interface is allowed to assume" – making these less stringent makes g harder to write, making them more stringent makes f harder to write.

My question is about what explicit choice should be made for these "safe-interface safety assumptions" with respect to aliasing &Cells. It's clear that some combinations must be disallowed, because they could lead to UB in safe code. For example, this (safe interface and internally safe) function has undefined behaviour if its arguments alias:

fn f1(x: &Cell<&'static usize>, y: &Cell<*const usize>) -> usize {
    y.set(core::ptr::null());
    *x.get()
}

A similar problem can happen with a single argument, if it's a cell that aliases its own contents (this is UB if the &'static Cell<usize> inside x is an alias for x itself, which can happen if the memory location *x holds a pointer to itself):

fn f2(x: &Cell<&'static Cell<usize>>) -> usize {
    x.get().set(0);
    x.get().get()
}

On the other hand, there are some similar cases which can't (in current stable Rust), as far as I know, lead to undefined behaviour in code that uses no unsafe internally. For example, a &Cell<Singleton<&'static Cell<usize>>> (where Singleton<T> is a non-Copy transparent public-field wrapper around T but can only be constructed once per program execution) probably can't be directly exploited in safe Rust because the only way to observe the value inside the Singleton would be to move the Singleton out of the cell, but it can't be moved out because there's no way to construct a replacement Singleton to swap/replace it with.

It would be possible to say that the explicit choice for the safe-interface safety assumption about aliasing Cells would be "anything that can't be used to cause undefined behaviour without unsafe is allowed". But this would reject some useful code; in particular I'm thinking of rust-lang/rust#145329 which wants to be able to make a safety assumption that an &Cell<Rc<T>> doesn't alias its own reference count (which is a Cell<usize> accessible via a pointer contained in the Rc). But in stable Rust, without using unsafe internally, such a Cell<Rc<T>> doesn't seem to be able to lead to undefined behaviour in code that does not have a T nor Rc<T> and is unable to construct one (because without access to an Rc<T>, you don't have anything to move into the Cell, and thus can't use any of the methods of &Cell except swap and as_ptr which don't help). So it would be nice if the safe-interface safety assumption were a little stronger, making it possible to write a sound Cell::get_cloned().

[RalfJung]

This reminds me of rust-lang/rust#80778 though I think the question is separate.

I would argue that &Cell<i32> and &Cell<[u8; 4]> can be freely converted (with an alignment check). So in general I don't think you can assume much here. The justification for cloning Cell<Rc<T>> involves Rc keeping its refcount fields private; it's not about their types.

[ia0]

What assumptions can safe-interface functions make

This should be answered by the safety invariant of its parameters. So maybe the question is about the safety invariant of &Cell<T>. But there should be enough consensus on that to answer the different examples. In particular, the safety invariant of &Cell<T> implies the safety invariant of its content (needed for Cell::replace() to be sound when it actually replaces the content instead of returning its argument) while being opened in a non-reentrant way by the appropriate thread (as described in RustBelt with non-atomic persistent borrows).

So a function taking &Cell<T> can assume that Cell::get() will return a safe value (a value satisfying its safety invariant).

For &Cell<&'static usize> this implies that the result of Cell::get() is valid for read. And if the function also takes a &Cell<*const usize>, nothing changes. It's still the caller responsibility to make sure that the safety invariant of the first parameter holds (if it's a safe caller, it holds by typing, but if it's an unsafe caller, they have to prove it). In particular, if the cells alias, the caller needs to make sure the function won't write to the second parameter in such a way that would break the safety invariant of the first parameter.

The other examples (&Cell<&'static Cell<usize>> and &Cell<Rc<T>>) are similar, in the sense that if there is aliasing involved, then the safety invariant of those cells doesn't hold, so the caller needs to make sure the function won't use its parameter in such a way that leads to UB for the actual unsafe values (values that don't satisfy their safety invariant) it will call the function with.

For Cell::swap(), it used to be unsound. The previous implementation was opening the non-atomic persistent borrow twice (once for each cell simultaneously) which is not permitted. The new implementation still does so, but at least it makes sure the memory regions don't overlap, so its soundness probably can't be proved in RustBelt, but there's probably a system where it can be proved.

For &Cell<i32> and &Cell<[u8; 4]>, they have the same safety invariant (assuming alignment, which follows from aliasing), so the caller doesn't need to prove anything since the function can't break the safety invariant of one of its argument using the second.

However for &Cell<bool> and &Cell<u8>, now there's a proof to be done by the caller, to make sure the function doesn't write anything greater than 1 to the second parameter. But the function can still assume to read a valid bool, because that's what the safety invariant of &Cell<bool> says, irrespective of other parameters.

[ia0]

Actually, to complete Ralf's sentence:

it's not about their types.

It's about the safety invariant of their types.

In other words, if a safe function takes &Cell<T> and &Cell<S> as parameters, it can assume they only alias where their safety invariants match.

For example a function taking &Cell<[u8; 4]> and &Cell<u16> cannot assume those cells don't overlap, as they may overlap in 5 different ways. However, if it also takes a &Cell<bool>, then it can assume that this last parameter doesn't overlap with the 2 previous parameters (as long as it doesn't at the same time guarantee in any way that it only writes values to the first 2 parameters that have the high 7 bits of their bytes set to zero).