Zero-cost interior mutability - proposal

language design
1

Zero-cost interior mutability

John Nagle October, 2024

Motivation

Some data structures are hard to create efficiently in Rust. Complex linking can be created using Rc and RefCell, but there is both a performance penalty and the risk of panics. This is an initial draft of a proposal to address that through compile time checks.

There are two parts to this. One is a compile time version of RefCell, and the other is a compile-time version of Rc. This note is about a compile time version of RefCell, and discusses another proposal for the Rc problem.

SafeCell - a new type

SafeCell has much the same semantics as RefCell. But the checking would be at compile time.

API

pub struct SafeCell<T> {
    ...
}

impl SafeCell<T> {
    
    /// Borrow -- checked at compile time, no panics or errors.
    fn borrow(&self) -> &T {
    }
    
    /// Mutable borrow -- checked at compile time, no panics or errors.
    fn borrow_mut(&mut self) -> &mut T {
    }
    
    /// Take -- checked at compile time, no panics or errors.
    fn take(&mut SafeCell<T>) -> T {
    }
    
}

Checking rules

The ideal rules:

  • Scopes of SafeCell mutable borrows of the same object must be disjoint.

  • No scope of an immutable borrow can include a mutable borrow of the same object.

  • No scope of a mutable borrow can include an immutable borrow of the same object.

Because determining if two objects are the same may be difficult, we probably need a more restrictive set of rules that's easier to check.

Simple but overly restrictive rules:

  • Scopes of SafeCell mutable borrows of the same type must be disjoint.

  • No scope of an immutable borrow can include a mutable borrow of the same type.

  • No scope of a mutable borrow can include an immutable borrow of the same type.

This is easy to check by transitive closure, but is probably too restrictive. It prohibits, for example, swapping the contents of two SafeCell structs.

Slightly less restrictive rules:

Add rule:

  • Within a single function, it is permitted to have two mutable borrows of the same type provided that the structs being borrowed from are disjoint.

This allows

fn swap_contents(&mut a: SafeCell<Foo>, &mut b: SafeCell<Foo>) {
    mem::swap(a.borrow_mut(), b.borrow_mut())
}

This handles a common case. In general, with SafeCell being a zero-cost abstraction, programs would pass a SafeCell, rather than a borrowed value from a SafeCell, into a function call. Borrowing should be very local. So single function analysis ought to be sufficient.

Notes on compiler implementation

For each function, the set of SafeCell types which are borrowed or mutably borrowed within that function would be constructed at compile time. Then transitive closure must be performed on those sets across calls. This would be done after generics have been expanded.

With that information available, each .borrow() and .borrow_mut() would be checked against the set of SafeCell types obtained for each function after transitive closure.

Error messages might read like:

Mutable borrow of SafeCell conflicts with a non-mutable borrow of the same type inside function foo. Function foo calls function bar which performs a borrow of SafeCell at line ...

Related work

This is a static replacement for RefCell, but does not address reference counting. The Static Rc proposal could possibly be used with SafeCell.

What's generally needed to replace Rc is a type that does what Rc, Rc::Weak, and .upgrade() do, but with compile time checking. The concept is to allow one owning reference, and N weak references. Weak references can be upgraded within local scopes only. The compile time goal is to show that when the owning reference is deleted, control is not inside a scope which upgrades a weak reference. If that can be shown, reference counts need not be maintained and .upgrade() cannot fail.

The idea is to stay with the user semantics Rust programmers already know from Rc and RefCell, but move the checking to compile time. We know those semantics are sufficient for most use cases, because people use them for that now.

If both of these goals can be accomplished, we have safe zero-cost back-references in Rust. This allows doing most of the things people want to do with references safely, avoiding escapes to unsafe code or raw pointers.

Comments?

2

Could you give an example of a case where SafeCell<T> would work, but a plain T would not work? I don't understand what you're saying.

7 Likes
3

The same situations where you'd need a RefCell.

The MockMessenger example for RefCell should work with SafeCell, because the .borrow() and .borrow_mut() calls are very local. It's easy to demonstrate that the borrow scopes are disjoint.

4

Could you write out example usage of SafeCell? I find your explanation of its behavior incomprehensible, and would like to see how it could be used.

5 
#[cfg(test)]
mod tests {
    use super::*;
    use safeCell::{SafeCell};
    struct MockMessenger {
        sent_messages: SafeCell<Vec<String>>,
    }

    impl MockMessenger {
        fn new() -> MockMessenger {
            MockMessenger {
                sent_messages: SafeCell::new(vec![]),
            }
        }
    }

    impl Messenger for MockMessenger {
        fn send(&self, message: &str) {
            self.sent_messages.borrow_mut().push(String::from(message));
        }
    }

    #[test]
    fn it_sends_an_over_75_percent_warning_message() {
        // --snip--

        assert_eq!(mock_messenger.sent_messages.borrow().len(), 1);
    }
}

As discussed above, it requires new compiler support to prove this is safe. .borrow() and.borrow_mut() for SafeCell don't actually check anything. At run time, it's like UnsafeCell, but what is proposed is compile time safety.

This kind of checking belongs to roughly the same family of problems as static deadlock checking, which has been looked at. This is easier.

6

The compiler can’t know this is safe, because message might itself be borrowed from sent_messages at this time. And it won’t try, because in your signature, borrow_mut (correctly!) requires &mut self.

This is the equivalent of a perpetual motion machine: without whole-program reasoning, it is not possible to get exclusive (&mut) semantics from a nominally-shared reference (&) without either unsafe or run-time checking (which is implemented with unsafe). If it ever is possible, you don’t need *Cell in the first place, as @theme indicated.

10 Likes
7

How would your rules prevent the following from compiling?

use safe_cell::SafeCell;

struct MyList {
    inner: SafeCell<Vec<String>>,
}
impl MyList {
    fn my_append(&self, other: &mut Vec<String>) {
        let inner_ref: &mut Vec<String> = self.inner.borrow_mut();
        inner_ref.append(other);  // Two &muts to the same thing
    }
}

fn append_my_list(list1: &MyList, list2: &MyList) {
    let vec_mut_ref: &mut Vec<String> = list2.inner.borrow_mut();
    list1.my_append(vec_mut_ref);
}

fn main() {
    let list = MyList { inner: SafeCell::new(vec![]) };
    append_my_list(&list, &list);
}
8

fn my_append() borrows type SafeCell<Vec<String>>. The function must be marked at compile time as doing this.

fn append_my_list() borrows type SafeCell<Vec<String>> and then, within the scope of that borrow, calls my_append.

This violates the compile time checkable rule that "Scopes of SafeCell mutable borrows of the same type must be disjoint."

9

Seems like the other commenters are missing this part. This is the hinge of the whole scheme, and is why it actually would be safe.

However, post-monomorphization errors and global reasoning are both usually verboten, with only minor exceptions. Both of those things make it much more difficult to preserve API stability. And global reasoning breaks in the presence of dynamic dispatch.

It would be nice to have a way to encode these kind of restrictions into the type system.

4 Likes
10

How would you do this reasoning while only looking at the body of one function at a time?

How would your rules forbid the following?

use safe_cell::SafeCell;

struct VecWrapper {
    vec: Vec<String>
}
impl VecWrapper {
    fn append_wrapper(&mut self, other: &mut Vec<String>) {
        let vec_mut_ref: &mut Vec<String> = &mut self.vec;
        vec_mut_ref.append(other);  // Two &muts to the same thing
    }
}

struct MyList {
    inner: SafeCell<VecWrapper>,
}
impl MyList {
    fn my_append(&self, other: &mut Vec<String>) {
        // Borrows a VecWrapper, while &mut Vec<String> is "in scope".
        // These are different types, so it's allowed
        let inner_ref: &mut VecWrapper = self.inner.borrow_mut();
        inner_ref.append_wrapper(other);
    }
}

fn append_my_list(list1: &MyList, list2: &MyList) {
    let vec_wrapper_mut_ref: &mut VecWrapper = list2.inner.borrow_mut();
    let vec_mut_ref = &mut vec_wrapper_mut_ref.vec;
    list1.my_append(vec_mut_ref);
}

fn main() {
    let list = MyList { inner: SafeCell::new(vec![]) };
    append_my_list(&list, &list);
}
11

By the way, you can do something like this already using ghost_cell:

It’s not pretty. But it is zero cost, aside from passing around a useless pointer.

There are also various alternative crates with roughly similar designs.

2 Likes
12

You wouldn’t. The proposal is for global reasoning.

13

That's what I'm arguing for - limited global reasoning. Something that can be done cheaply. I built a real proof of correctness system once, and it did global transitive closure. It's not that bad if you're basically propagating info up the call chain. If you have to search for it going down the call tree, it's slow, for obvious combinatoric reasons.

Dynamic dispatch has to be addressed by treating it conservatively. Anything you could possibly call should be treated as called for these checks.

That would probably involve more manual annotations at every call in the call chain. Automation is easier on users.

14

ghost_cell is really clever. I need to read that a few more times.

I'm not sure that separating permissions from data really fits Rust's model, though. Rust ties permissions to data, which makes things comprehensible to programmers. I'm trying to stay close to established Rust semantics.

I'm impressed that the ghost_cell people got this to work for some concurrent cases. Is ghost_cell used much? That makes sense, though.

For safe doubly-linked lists, I'd think in terms of owning references going forward, and weak references going back. It's asymmetrical but more Rust-like. There's a well-defined order of safe destruction, so you don't need arena allocation.

Using the static-rc concept to make those weak pointers zero-cost seems promising, but I'm unsure about the soundness of static-rc at this time.

15

You can check reverse deps and downloads on crates.io (or more conveniently on lib.rs). There are a few crates like that, it looks like ghost_cell and qcell are the two most popular to me. But we are still talking 27 total reverse deps across the 5 or so cell crates I checked. So not completely unused, but definitely not popular.

Which makes sense, I think this is a very niche need, and a complicated concept. I never felt the need to reach for such crates for example.

1 Like
16

How would this work when not all method bodies are known? For example when calling function pointers or methods on trait objects. I suppose they would have to be considered to possibibly borrow anything in order to make them sound.

Also, how does this impact backward compatibility? Would a crate changing the body of one of its functions to call .borrow()/.borrow_mut() be a breaking change? This would also extend to function pointers/trait objects assuming the previous point, which seems much easier to do by chance.

1 Like
17

I find your idea very interesting but I suspect we will prove very reluctant, as a community, to have this reasoning propagate across a very contained an uncontained space. If we did add compiler support I am guessing we would probably want to block it at something like the API boundary of a crate.

Post-monomorphization errors remain controversial, even though we have made them more possible. In brief: people have bad memories of C++ template errors. I'm sure you understand.

I emphatically agree that we do want things to improve the ergonomics of mutable accesses that can be correctly compile-time checked, though.

3 Likes
18

Also, how does this impact backward compatibility? Would a crate changing the body of one of its functions to call .borrow()/.borrow_mut() be a breaking change?

Yes. It's a breaking change with RefCell now. A panic could occur where one was previously impossible. This just moves the check to compile time.

19

Ah. A good view of the larger problems.

I agree. This is an area which Rust has avoided.

However, the C++ crowd, currently under pressure from regulatory and security agencies to get their act together before there's a big loss due to cyber warfare, is looking at global analysis. They're not willing to rule out common C/C++ idioms which Rust disallows. See Safe C++ and Strostrup's "Can C++ be saved" paper. To make that work, the C++ crowd is considering more global analysis. So another look at global analysis for Rust may be necessary for Rust to remain competitive. That's what motivated me to write this up.

Limiting global analysis to the crate level is a good idea. It's common to pass around RefCell and Rc within the functions of a crate, but not common to see an crate API where something is an Rc<RefCell<T>>. Rc and RefCell would remain available, so anything that can't be checked at compile time can be checked at run time.

The object of this proposal is to reduce the need for unsafe code. Quite often, we see unsafe code used because someone wanted to use an idiom from C or C++ in Rust, and is having trouble expressing that in Rust. (On the rare occasions I have to use a debugger on a Rust program, it's almost always because someone took an unsafe shortcut in a crate someone else wrote. I avoid unsafe in my own code.)

Post-monomorphization errors remain controversial, even though we have made them more possible. In brief: people have bad memories of C++ template errors. I'm sure you understand.

Yes. C++ template error amplification of one error into many is painfully real. Most of the problems in global analysis come from situations where it's hard to tell, at compile time, exactly what's being called. Templates and dynamic dispatch, mostly. Fortunately Rust does not use as much dynamic dispatch as C++ and Java do.

This is mostly an template error message problem. If two different instantiations of a template produce the same error message, that's worth recognizing so that the error messages can be assigned to the template, not the instantiation, for display to the user. Rust is pretty good about reporting errors which stem from inconsistency between two separated parts of the program,

It's been suggested that this sort of checking be done through the type system. That involves additional writing of constraints at every step in the call chain. More annotations for templates make templates harder to use. Compilers are better at following the call chain than humans are. Automate if at all possible.

1 Like
20

I was assuming the more "restrictive" set of rules, since they seem the only one that can be realistically be implemented:

A function adding a call to .borrow()/.borrow_mut() on any SafeCell<Foo> would be a breaking change, while a function adding a call to .borrow()/.borrow_mut() on a RefCell<Foo> would be breaking only if that RefCell could be accessed in some other way. The author of the crate can reason about this and conclude it cannot be a breaking change, while with SafeCell it cannot change how the compiler reasons about it and hence will be forced into the breaking change.