Cell and RefCell
So far in this chapter, the mutable references we've been discussing have a property called, by Rust, inherited mutability. That is, values are made mutable when we inherit their ownership or the exclusive right—via a &mut—to mutate the value. Inherited mutability is preferred in Rust as it is statically enforcable—any defects in our program with regards to memory mutation will be caught at compilation time. Rust does provide facilities for interior mutability, that being mutability that is available for pieces of an immutable type. The documentation calls interior mutability something of a last resort but, while not common, it is not exactly rare in practice, either. The two options for interior mutability in Rust are Cell<T> and RefCell<T>.
Let's consider Cell<T>. How is it used? As suggested, Cell<T> is useful when some field or fields of an otherwise immutable structure need to be mutable and the T you're concerned with is T: Copy. Consider a graph structure where a search operation is performed. This is logically immutable—the graph structure does not need to be modified during search. But, also consider the case where we would like to record the total number of traversals along the graph's edges. Our options are to violate the logical immutability of the graph search, require storage outside of the graph, or insert an interior, mutable counter into the graph. Which choice is best will depend on the specific situation. Here is a significantly less complicated example of Cell<T>, compared to a graph search:
use std::cell::Cell;
enum Project {
Apollo,
Gemini,
Mercury,
}
struct Mission {
project: Project,
number: u8,
duration_days: Cell<u8>,
}
fn main() {
let mission = Mission {
project: Project::Mercury,
number: 7,
duration_days: Cell::new(255),
};
mission.duration_days.set(0);
assert_eq!(0, mission.duration_days.get());
}
Of course, that's a bit contrived. Interior mutability shows up when the situation is non-trivial, generally speaking. Note that Cell<u8> had to be manipulated with get and set methods, contrary to the normal process of setting and reading directly or through a pointer. Let's dig into the implementation of Cell<T>, defined in src/libcore/cell.rs:
pub struct Cell<T> {
value: UnsafeCell<T>,
}
As is common in Rust internals, a safe interface hides an unsafe inner core, as we saw in Chapter 2, with HashMap. What is the definition of UnsafeCell?
pub struct UnsafeCell<T: ?Sized> {
value: T,
}
Of particular note is an implementation that follows shortly afterward:
impl<T: ?Sized> !Sync for UnsafeCell<T> {}
We will discuss Sync in the following chapter in greater detail. Suffice it to say, for now, any type that is threadsafe must implement Sync—and many do automatically—and by disabling the Sync trait for UnsafeCell<T>—which is what !Sync means—the type is specifically being marked as not thread-safe. That is, any thread may be manipulating the data owned by UnsafeCell at any time. As we've previously discussed, Rust is able to make a good deal of optimizations off the back of the knowledge that &T is guaranteed to also not be mutable somewhere and that &mut T is unique. UnsafeCell<T> is the only method Rust provides to turn these compiler optimizations off; it is possible to dip into an unsafe block and transmute &T to &mut T, but this is specifically called out as undefined behavior. They key to UnsafeCell<T> is that it is possible for a client to retrieve multiple mutable references to the interior data, even if the UnsafeCell<T> is itself mutable. It is up to the caller to ensure that there is only one mutable reference at any time. The implementation of UnsafeCell —stripped of its comments for clarity's sake—is brief:
impl<T> UnsafeCell<T> {
pub const fn new(value: T) -> UnsafeCell<T> {
UnsafeCell { value: value }
}
pub unsafe fn into_inner(self) -> T {
self.value
}
}
impl<T: ?Sized> UnsafeCell<T> {
pub fn get(&self) -> *mut T {
&self.value as *const T as *mut T
}
}
This brings us back to Cell<T>. We know that Cell<T> is built on top of an unsafe abstraction and we will have to take care not to violate the &mut T uniqueness constraint. How is this done? First, construction of Cell<T> is straightforward, as you may expect:
impl<T> Cell<T> {
pub const fn new(value: T) -> Cell<T> {
Cell {
value: UnsafeCell::new(value),
}
}
The const fn is likely a surprise, on account of it being a nightly-only feature as of writing this book. In Rust, a constant function is evaluated at compile time. The benefit to the programmer of this particular definition is that the result of Cell::new can be assigned to a constant variable, one which will exist for the lifetime of the program. Both as_ptr and get_mut are different views of the underlying T, one a raw mutable pointer and the other a mutable reference:
pub fn as_ptr(&self) -> *mut T {
self.value.get()
}
pub fn get_mut(&mut self) -> &mut T {
unsafe {
&mut *self.value.get()
}
}
pub fn into_inner(self) -> T {
unsafe { self.value.into_inner() }
}
Note that while the internals of get_mut are unsafe, the borrow checker is brought to bear on the problem of keeping &mut T unique and so Cell::get_mut can itself be safe. Cell::as_ptr is not marked as unsafe—it's safe to receive a raw pointer in Rust—but any caller will have to do deferencing of that raw pointer in an unsafe block: it's possible that there will be more than one raw, mutable pointer floating around. Setting a new value into the cell is done in terms of replacement, discussed ahead, but with careful attention made towards forcefully dropping the T pulled from the cell:
pub fn set(&self, val: T) {
let old = self.replace(val);
drop(old);
}
Cell::swap and Cell::replace are done in terms of the lower-level memory manipulation tools from std::ptr and std::mem. swap is intended to replace the interior of one cell with another. Its definition is as follows:
pub fn swap(&self, other: &Self) {
if ptr::eq(self, other) {
return;
}
unsafe {
ptr::swap(self.value.get(), other.value.get());
}
}
swap is done in terms of std::ptr::swap, a function documented as copying the memory through the raw pointers passed to it as arguments. You'll note that Cell::swap is careful to avoid the swap if the passed other is equivalent to self. The reason for this becomes clear when we take a peek at the definition of std::ptr::swap, defined in src/libcore/ptr.rs:
pub unsafe fn swap<T>(x: *mut T, y: *mut T) {
// Give ourselves some scratch space to work with
let mut tmp: T = mem::uninitialized();
// Perform the swap
copy_nonoverlapping(x, &mut tmp, 1);
copy(y, x, 1); // `x` and `y` may overlap
copy_nonoverlapping(&tmp, y, 1);
// y and t now point to the same thing, but we need to completely
forget `tmp`
// because it's no longer relevant.
mem::forget(tmp);
}
The exact details of copy_nonoverlapping and copy are unimportant here, except in noting that swapping does require allocation of uninitialized space and copying back and forth from that space. It's wise to avoid the work if you don't have to do it. Cell::replace works along similar lines:
pub fn replace(&self, val: T) -> T {
mem::replace(unsafe { &mut *self.value.get() }, val)
}
}
std::mem::replace takes a &mut T and a T and then replaces the value at &mut T with the passed in val, returning the old value and dropping neither. The definition of std::mem::replace is in src/libcore/mem.rs and is as follows:
pub fn replace<T>(dest: &mut T, mut src: T) -> T {
swap(dest, &mut src);
src
}
Chasing the definition of swap in the same module, we find it is as follows:
pub fn swap<T>(x: &mut T, y: &mut T) {
unsafe {
ptr::swap_nonoverlapping(x, y, 1);
}
}
std::ptr::swap_nonoverlapping is as follows:
pub unsafe fn swap_nonoverlapping<T>(x: *mut T, y: *mut T, count: usize) {
let x = x as *mut u8;
let y = y as *mut u8;
let len = mem::size_of::<T>() * count;
swap_nonoverlapping_bytes(x, y, len)
}
Finally, the private std::ptr::swap_nonoverlapping_bytes is as follows:
unsafe fn swap_nonoverlapping_bytes(x: *mut u8, y: *mut u8, len: usize) {
// The approach here is to utilize simd to swap x & y efficiently.
// Testing reveals that swapping either 32 bytes or 64 bytes at
// a time is most efficient for intel Haswell E processors.
// LLVM is more able to optimize if we give a struct a
// #[repr(simd)], even if we don't actually use this struct
// directly.
//
// FIXME repr(simd) broken on emscripten and redox
// It's also broken on big-endian powerpc64 and s390x. #42778
#[cfg_attr(not(any(target_os = "emscripten", target_os = "redox",
target_endian = "big")),
repr(simd))]
struct Block(u64, u64, u64, u64);
struct UnalignedBlock(u64, u64, u64, u64);
let block_size = mem::size_of::<Block>();
// Loop through x & y, copying them `Block` at a time
// The optimizer should unroll the loop fully for most types
// N.B. We can't use a for loop as the `range` impl calls
// `mem::swap` recursively
let mut i = 0;
while i + block_size <= len {
// Create some uninitialized memory as scratch space
// Declaring `t` here avoids aligning the stack when this loop
// is unused
let mut t: Block = mem::uninitialized();
let t = &mut t as *mut _ as *mut u8;
let x = x.offset(i as isize);
let y = y.offset(i as isize);
// Swap a block of bytes of x & y, using t as a temporary
// buffer. This should be optimized into efficient SIMD
// operations where available
copy_nonoverlapping(x, t, block_size);
copy_nonoverlapping(y, x, block_size);
copy_nonoverlapping(t, y, block_size);
i += block_size;
}
if i < len {
// Swap any remaining bytes
let mut t: UnalignedBlock = mem::uninitialized();
let rem = len - i;
let t = &mut t as *mut _ as *mut u8;
let x = x.offset(i as isize);
let y = y.offset(i as isize);
copy_nonoverlapping(x, t, rem);
copy_nonoverlapping(y, x, rem);
copy_nonoverlapping(t, y, rem);
}
}
Whew! That's some rabbit hole. Ultimately, what we've discovered here is that std::mem::replace is defined in terms of block copies from one non-overlapping location in memory to another, a process which the Rust developers have tried to make as efficient as possible by exploiting LLVM's ability to optimize a bitwise operation on common processors in terms of SIMD instructions. Neat.
What of RefCell<T>? It too is a safe abstraction over UnsafeCell<T> except that the copy restriction of Cell<T> is lifted. This makes the implementation a touch more complicated, as we'll see:
pub struct RefCell<T: ?Sized> {
borrow: Cell<BorrowFlag>,
value: UnsafeCell<T>,
}
Like Cell, RefCell has an inner unsafe value, that much is the same. What's fun here is borrow: Cell<BorrowFlag>. RefCell<T> is a client of Cell<T>, which makes good sense considering that the immutable RefCell is going to need interior mutability to track the total number of borrows of its inner data. BorrowFlag is defined like so:
// Values [1, MAX-1] represent the number of `Ref` active // (will not outgrow its range since `usize` is the size
// of the address space) type BorrowFlag = usize; const UNUSED: BorrowFlag = 0; const WRITING: BorrowFlag = !0;
The implementation of RefCell<T> is like to that of Cell<T>. RefCell::replace is also implemented in terms of std::mem::replace, RefCell::swap in terms of std::mem::swap. Where things get interesting are the functions new to RefCell, which are those to do with borrowing. We'll look at try_borrow and try_borrow_mut first as they're used in the implementations of the other borrowing functions. try_borrow is defined like so:
pub fn try_borrow(&self) -> Result<Ref<T>, BorrowError> {
match BorrowRef::new(&self.borrow) {
Some(b) => Ok(Ref {
value: unsafe { &*self.value.get() },
borrow: b,
}),
None => Err(BorrowError { _private: () }),
}
}
With BorrowRef being as follows:
struct BorrowRef<'b> {
borrow: &'b Cell<BorrowFlag>,
}
impl<'b> BorrowRef<'b> {
#[inline]
fn new(borrow: &'b Cell<BorrowFlag>) -> Option<BorrowRef<'b>> {
match borrow.get() {
WRITING => None,
b => {
borrow.set(b + 1);
Some(BorrowRef { borrow: borrow })
},
}
}
}
impl<'b> Drop for BorrowRef<'b> {
#[inline]
fn drop(&mut self) {
let borrow = self.borrow.get();
debug_assert!(borrow != WRITING && borrow != UNUSED);
self.borrow.set(borrow - 1);
}
}
BorrowRef is a structure that holds a reference to the borrow field of RefCell<T>. Creating a new BorrowRef depends on the value of that borrow; if the value is WRITING then no BorrowRef is created—None gets returned—and otherwise the total number of borrows are incremented. This achieves the mutual exclusivity of writing needed while allowing for multiple readers—it's not possible for try_borrow to hand out a reference when a write reference is out for the same data. Now, let's consider try_borrow_mut:
pub fn try_borrow_mut(&self) -> Result<RefMut<T>, BorrowMutError> {
match BorrowRefMut::new(&self.borrow) {
Some(b) => Ok(RefMut {
value: unsafe { &mut *self.value.get() },
borrow: b,
}),
None => Err(BorrowMutError { _private: () }),
}
}
Again, we find an implementation in terms of another type, BorrowRefMut:
struct BorrowRefMut<'b> {
borrow: &'b Cell<BorrowFlag>,
}
impl<'b> Drop for BorrowRefMut<'b> {
#[inline]
fn drop(&mut self) {
let borrow = self.borrow.get();
debug_assert!(borrow == WRITING);
self.borrow.set(UNUSED);
}
}
impl<'b> BorrowRefMut<'b> {
#[inline]
fn new(borrow: &'b Cell<BorrowFlag>) -> Option<BorrowRefMut<'b>> {
match borrow.get() {
UNUSED => {
borrow.set(WRITING);
Some(BorrowRefMut { borrow: borrow })
},
_ => None,
}
}
}
The key, as with BorrowRef, is in BorrowRefMut::new. Here, we can see that if the inner borrow from RefCell is unused then the borrow is set to write, excluding any potential read references. Likewise, if there is a read reference in existence, the creation of a mutable reference will fail. And so, exclusive mutable references and multiple immutable references are held at runtime by abstracting over an unsafe structure that allows for the breaking of that guarantee.