Cell::swap assumes Cells never overlap

[RalfJung]

In #80682 (comment), it was uncovered that Cell::swap is making some rather strong assumptions: two Cells with different address but the same type must not overlap. Not only is this a scarily non-local safety invariant, it is also fundamentally incomaptible with some APIs that ought to be correct, as demonstrated by this snippet (thanks to @xfix and @SkiFire13 for help with working out the example):

use std::cell::Cell;
use std::mem::transmute;
use std::convert::TryInto;

fn as_cell_of_array<T, const N: usize>(c: &[Cell<T>; N]) -> &Cell<[T; N]> {
    unsafe { transmute(c) }
}

fn main() {
    let x = [Cell::new(vec![1]), Cell::new(vec![2]),Cell::new(vec![3])];
    let x1: &Cell<[_; 2]> = as_cell_of_array(x[0..2].try_into().unwrap());
    let x2: &Cell<[_; 2]> = as_cell_of_array(x[1..3].try_into().unwrap());
    x1.swap(x2);
}

Run it in Miri to see the issue: ptr::swap will duplicate parts of the memory range when there is overlap, which leads to double-drop (other parts of the memory range are just lost, leading to memory leaks, but that is not the main issue here).

This is not itself a soundness issue as it requires unsafe code to trigger UB. But this likely reflects an unintended consequence of Cell::swap.

Cell::swap history

• This got stabilized in 33a5665 as part of Library stabilizations for 1.17 #40538. That commit references Tracking issue for RFC 1651: Extend Cell to non-Copy types  #39264 and an RFC, but swap is not mentioned in either of them.
• swap was added in Add swap method for Cell #39716.

Possible solutions

• Accept that as_cell_of_array is unsound and document "non-overlap" as part of the Cell safety invariant. This seems very fragile.
• Make Cell::swap not misbehave on overlap, either by panicking or by only swapping the non-overlapping parts.

Cc @rust-lang/lang

[bjorn3]

swap was added in a5e8bbf, which was authored by a "Charlie Fan". This is probably @ghost.

[RalfJung]

Cc @rust-lang/libs

[Darksonn]

or by only swapping the non-overlapping parts.

This makes the as_cell_of_array method sound, but it seems like there could be other seems-like-they-should-be-ok cell projections that break under this behavior.

[RalfJung]

This makes the as_cell_of_array method sound, but it seems like there could be other seems-like-they-should-be-ok cell projections that break under this behavior.

I don't think so. This makes the swap function behave "strangely", but since no data is duplicated nor discarded, I think it is sound.

[danielhenrymantilla]

but it seems like there could be other seems-like-they-should-be-ok cell projections that break under this behavior.

I share this hunch, although the code, out of nowhere, may look very contrived.

Consider:

use ::core::cell::Cell;

#[derive(Clone, Copy)]
#[repr(C)]
struct T(bool, u8, bool);

let ref mut s: [u8; 5] = [1, 2, 0, 1, 0];
let p = s.as_mut_ptr(); // SB: shared read-write over those 5 bytes (`&[Cell<u8>; 5]`)
let a: &Cell< T > = unsafe { &*p.cast() };
let b: &Cell< T > = unsafe { &*p.add(2).cast() };
// `a.2` overlaps with `b.0`
Cell::swap(a, b);
// Assuming the non-overlapping parts swap, the original 5-byte layout now is:
// `[1, 0, 0, 1, 2]`
b.get().2 // invalid `bool`

So it seems like panic!-king (at least for non-Copy types) is the only option that would allow us too keep the structural property of Cells, which, imho, is a very intuitive programmer mindset (and thus, a mistake that many would do should they not know about this caveat), and so a quite important thing to preserve 🙂.

[RalfJung]

I share this hunch, although the code, out of nowhere, may look very contrived.

That is an example of the "strange" behavior not being the right thing for this code, but it is not an unsoundness of swap per se. Your unsafe code is simply making wrong assumptions about the functional behavior of Cell::swap.

Current Cell::swap favors the first operand in case of overlap (according to ptr::swap documentation); unsafe code that incorrectly assumes it would favor the second operand would be equally wrong. I don't see a bug in Cell::swap either way.

So it seems like panic!-king (for non-Copy types!)

IMO it seems rather strange to only panic for non-Copy types.

---

Btw, RefCell::swap also exists. RefCell does not have array/slice projection functions though and they would be wrong due to the counts, so overlapping RefCell probably truly are not a thing.

[CAD97]

At the very least, an argument that &Cell<(bool, u8, bool)> aren't allowed to overlap is easier to defend than that &Cell<[T; N]> aren't allowed to overlap.

Plus also, (bool, u8, bool) doesn't have guaranteed layout in the first place, so any example using tuples is (currently) implementation-detail-tied even before hitting Cell::swap.

You could still construct an example using only #[repr(C)] types, of course; just replace the tuple with an actual #[repr(C)] type. You could even make it Copy.

---

As I understand it, there's three main cases here.

• Cell::swapping two nonoverlapping T is fine.
• Cell::swapping two partially overlapping [T; N] without any bound on T has a sound, if surprising, definition, where the nonoverlapping part of the arrays are swapped.
• Cell::swapping two partially overlapping unknown T is unsound in any definition, unless T both has no safety invariants and the overlapping portion is Copy.

The third case is obviously the most restricting one, and Cell::swap is defined on Cell<T>. To expound on first of the two subissues:

Consider a type Q([u8; 2]) with the extra safety invariant that the second u8 must be double the first u8. Q could even be Copy. It would be valid to create two &Q from [2, 4, 8], as you'd have &[2, 4] and &[4, 8]. There is no possible definition of swap (other than a no-op) which preserves the safety invariant. And of course the Cell::swap impl doesn't even know about the safety invariant.

I could probably create an even worse example using underaligned types and relying on a specific endianness, perhaps even accidentally breaking validity invariants (think #[repr(packed)] around partially overlapping NonZeroU64).

The only two resolutions I'm confident in are making Cell::swap always panic for overlapping cells (because there could be safety invariants being broken) or forbidding overlapping Cells to Cell::swap-compatible types (optionally: that would be broken by Cell::swap). And I don't like the subtle implications of the latter (e.g. Cell<[T]> -> Cell<[T; N]> being unsound for unbound T).

[SkiFire13]

And I don't like the subtle implications of the latter (e.g. Cell<[T]> -> Cell<[T; N]> being unsound for unbound T

I don't think &Cell<[T]> -> &Cell<[T; N]> would be immediately unsound, you would still need a way to create overlapping &Cell<[T]>s.

[RalfJung]

At the very least, an argument that &Cell<(bool, u8, bool)> aren't allowed to overlap is easier to defend than that &Cell<[T; N]> aren't allowed to overlap.

In particular, they certainly can only overlap in restricted ways -- if they overlap such that one's bool sits on the other's u8, I can already cause UB without swap just by storing 3 into that u8 and then reading it as a bool.

Cell::swapping two partially overlapping unknown T is unsound in any definition, unless T both has no safety invariants and the overlapping portion is Copy.

Oh I see... to only swap the non-overlapping parts we have to make an argument that these parts have the same type (safety+validity invariant). Which... seems utterly bogus now that I think about it. Worse, the invariant could correlate the overlapping with the non-overlapping part, as in your Q example.

(Removed a whole bunch of nonsense where I try to find some special cases that work.)

Yeah we should make it panic.^^

Consider a type Q([u8; 2]) with the extra safety invariant that the second u8 must be double the first u8. Q could even be Copy. It would be valid to create two &Q from [2, 4, 8], as you'd have &[2, 4] and &[4, 8]. There is no possible definition of swap (other than a no-op) which preserves the safety invariant. And of course the Cell::swap impl doesn't even know about the safety invariant.

It is unsound to create an &Cell to these Q though, even without swap I can already violate the safety invariant here by setting the second reference to [1, 2]. Ergo this is not a problem for swap, we can already assume such references do not exist.

or forbidding overlapping Cells to Cell::swap-compatible types (optionally: that would be broken by Cell::swap)

I am confused, is there a negation missing somewhere in this sentence?

[CAD97]

It is unsound to create an &Cell to these Q though, even without swap I can already violate the safety invariant here by setting the second reference to [1, 2]. Ergo this is not a problem for swap, we can already assume such references do not exist.

Fair. I'm fairly confident that it'd be possible to come up with some safety invariant that a partial swap would break, though, with more data-dependent qualities.

or forbidding overlapping Cells to Cell::swap-compatible types (optionally: that would be broken by Cell::swap)
I am confused, is there a negation missing somewhere in this sentence?

The parenthetical is an optional relaxation of the potential requirement (but at the cost of a lot of complexity).

[RalfJung]

But shouldn't it be forbidding overlapping Cells to Cell::swap-incompatible types? Not that I know what either of these things mean, but forbidding incompatible seems to make more sense than forbidding compatible.^^

[CAD97]

Yeah, poor verbage. I meant roughly "forbidding overlapping Cells of types that can be used in Cell::swap (i.e. sized types)", with the optional extension of "only for those actually broken by Cell::swap" (however that would be defined).

[CAD97]

notriddle brings up that partially overlapping Cells through an enum is problematic even without Cell::swap:

fn unwrap_left<L, R>(either: &Cell<Either<L, R>>) -> &Cell<L> { ... }

let cell = Cell::new(Either::Left(...));
let left = unwrap_left(&cell);
cell.set(Either::Right(...));
left.get()