An implementation of Joshua Yanovski's Ghost Cell paper.

Last update: Dec 22, 2022

Related tags

Overview

A novel safe and zero-cost borrow-checking paradigm from the GhostCell paper.

Motivation

A number of collections, such as linked-lists, binary-trees, or B-Trees are most easily implemented with aliasing pointers.

Traditionally, this means using run-time borrow-checking in order to still be able to mutate said structures, or using unsafe in the name of performance.

By using brands, GhostCell separate the data from the permission to mutate it, and uses a unique GhostToken to model this permission, tied at compile-time to a number of said GhostCell via the brand.

Safety

In the GhostCell paper, Joshua Yanovski and his colleagues from MPI-SWS, Germany, formally demonstrate the safety of GhostCell using the separation logic they have developed as part of the Rust Belt project. I personally would trust them on this.

The official implementation can be found at https://gitlab.mpi-sws.org/FP/ghostcell/-/tree/master/ghostcell, along with examples. The current implementation will be upgraded soonish, now that I'm aware of it.

Use at your own risks!

(And please report any issue)

Maturity

This is very much an Alpha quality release, at best.

Documentation:

All methods are documented.
All non-trivial methods have examples.

Tests:

All non-trivial methods are tested, via their examples.
All methods with safety invariants are covered with compile-fail tests.
The entire test-suite, including examples, runs under Miri.

How to use?

Let's start from a self-contained example:

use ghost_cell::{GhostToken, GhostCell};

fn demo(n: usize) {
    let value = GhostToken::new(|mut token| {
        let cell = GhostCell::new(42);

        let vec: Vec<_> = (0..n).map(|_| &cell).collect();

        *vec[n / 2].borrow_mut(&mut token) = 33;

        *cell.borrow(&token)
    });

    assert_eq!(value, 33);
}

GhostToken uses the best known way to generate a unique lifetime, hence used as a brand, which is to combine:

A local variable, created within the GhostToken::new method.
A closure which must be valid for all lifetimes.

This means 2 restrictions:

The closure must be variant over the lifetimes, this does not always play well with closures already containing references.
None of the branded items can be returned by the closure.

Then, within the closure, any GhostCell can be associated to one, and only one, GhostToken which will encode its borrowing permissions:

&GhostToken<'brand> is the key to using GhostCell<'brand, T>::borrow -- note the matching 'brand -- and allows obtaining a &T reference.
&mut GhostToken<'brand> is the key to using GhostCell<'brand, T>::borrow_mut and allows obtaining a &mut T reference.

Using borrow or borrow_mut borrow both the cell and the token.

So what?

A GhostCell is a safe, zero-cost, cell. It allows aliasing with compile-time checked borrow-checking.

Combined with StaticRc, it allows writing Doubly Linked Lists, Binary Trees and B-Trees with parent pointers, etc... in safe, stable, Rust.

Other Cells

There are other cells in existence, performing a similar function with different trade-offs:

The standard Cell and RefCell.
The multiple cells of the qcell crate, of which LCell is based on discussions with the author of GhostCell, sharing a similar idea.

That's all folks!

And thanks for reading.

Comments

multiple borrows extension

This adds functionality for getting multiple borrows from different ghostcells at the same time. I put this under an experimental flag, since it seems that this wasn't proven by the ghostcell paper. However, qcell seems to already have this functionality for some time, and it definitely sounds sound to me.

In any case, this probably needs a macro, or some other way, to mutably borrow more than 3 elements at a time, and we can't write a method for each number.

opened by noamtashma 15

Unsoundness using experimental-multiple-mutable-borrows

Recently, looking at wackbyte's pull request made me look into this code again.

I found out this counterexample:

fn main() {
  GhostToken::new(|mut token| {
      let cell_of_array: GhostCell<[i32; 2]> = GhostCell::new([3, 7]);
      let array_of_cells = (&cell_of_array as &GhostCell<[i32]>).as_slice_of_cells();
      let second_cell = &array_of_cells[1];
      let (second_val, array) =
          GhostBorrowMut::borrow_mut((second_cell, &cell_of_array), &mut token).unwrap();
      println!("{}", *second_val);
      array[1] = -4;
      println!("{}", *second_val);
  });
}

opened by noamtashma 7

"left as an exercise to the reader"?

I am a bit confused about which methods you refer to when you say they have been "left as an exercise to the reader". We have a complete and compiling implementation of the GhostCell API surface at https://gitlab.mpi-sws.org/FP/ghostcell/-/tree/master/ghostcell; is there anything missing there that you found is required for ghost-collections (and that cannot be implemented on top of public safe functions)?

opened by RalfJung 7
`check_distinct`: sort the array if it is large enough

This addresses the TODO comment. I chose 10 as the boundary, since my benchmarks showed that this is the point after which sorting first is faster (in the case that all pointers are distinct, which should be the common case).

opened by konsumlamm 5
Unsoundness in ghost-cursor
Here is a counterexample showing ghost-cursor is unsound:

fn ghost_cursor_counterexample() { GhostToken::new(|mut token| { let cell = GhostCell::new(Box::new(GhostCell::new(7))); let cursor = GhostCursor::new(&mut token, Some(&cell)); let inner_cursor = cursor.move_into(|cell| Some(cell)).ok().unwrap(); let (token, inner_cell_ref_opt) = inner_cursor.into_parts(); let inner_cell_ref = inner_cell_ref_opt.unwrap(); // Free the box *cell.borrow_mut(token) = Box::new(GhostCell::new(3)); // Use-after-free! println!("{}", inner_cell_ref.borrow(token)); }); }

This works by using the ghost-cursor in order to obtain a long-living reference in the internal GhostCell, without borrowing the token for the same lifetime. This wouldn't be possible ordinarily. Then, the token is free to be reused to access the outer GhostCell to drop the inner GhostCell.

I think there are two interesting changes to consider that might fix this problem:

Removing the into_parts method.

Ensuring that the cursor must outlive any reference that it gives out, even if they're ghost cells. This essentially means dropping the &GhostCell<T> output from the into_parts method.

Maybe even having it only return an immutable reference to the token will also be fine (like before This issue)?
opened by noamtashma 4
Refactor tests to their own directory

This changes the test suite to be separate from the library. The compile tests now use the trybuild crate. This way, we don't need a hidden public module and the test suite gets cleaner.

I'm a bit skeptical that all of the compile tests are really useful though, most just check that the compiler enforces the borrowing rules (sure, it would catch if someone changed borrow_mut to take a &GhostToken, but I don't see how that could happen).

opened by konsumlamm 3
merge related crates into a workspace

Since these crates expose related functionality and depend on each other, I think it makes sense to unify them under one ghost/ crate in a workspace, and publish that as the main crate (a la tokio).

My ulterior motivation for this is that I'd like to try out making macros by adding a ghost-macro crate that exposes a #[token] macro which allows you to use collections, etc. "outside" of a closure by transforming the annotated code into a big, encapsulated closure. I have no idea if this is possible, or how it would work, and I have never written a macro before in my life, also I barely understand this whole ghost concept, but I think it would be a cool thing to try.

opened by caass 2
WIP Fix GhostBorrowMut interaction with slices
Changes:

Switch check_distinct to detect overlap between slices, and overlap between single values and slices.

Add specialization feature, when using ghost-borrow-mut, to allow the above.

Motivation:

There is a soundness issue as exposed by @noamtashma in #23, since the usecase is useful, it seems better to fix the issue.

Limitations:

Performance may be lackluster.

Specialization is an unstable feature with no clear path towards stabilization.

No test for slice vs slice could be created, it is not clear whether obtaining two independent GhostCells with overlapping slices is even possible in the first place.

Tests of check_distinct, in general, are lackluster.
opened by matthieu-m 1
Even more `?Sized` bounds
Overview:

GhostBorrow/GhostBorrowMut for &(GhostCell<T>, ...): The last type is ?Sized.

The extra macro I wrote to help with this is duplicated between the two modules since it's really small. I can move it to a new module if needed, though.

GhostBorrowMut for (&GhostCell<T>, ...): Each type is ?Sized.

Didn't require any other changes.

GhostBorrowMut for [&GhostCell<T>; N]: T is ?Sized.

I think I've found a solution to the problems discussed in your previous comment.

I made check_distinct generic over a type T and made it take [*const T; N] instead of [*const (); N]. Each pointer is cast to *const () during comparison (I made sure and checked, and std recommends this for by-address equality of fat pointers; see the last example here). [&GhostCell<T>; N] and [*const T; N] definitely have the same layout, so no strange pointer casting issues here.

It doesn't require the pointer metadata API!

I made a few basic positive and negative tests.
opened by wackbyte 1
Some `GhostCursor` fixes (#3)
Just tried to fix some of the issues brought up in #3.

Changes:

GhostCursor::into_parts returns a mutable token

Fixed the GhostCursor::move_mut soundness issue where the reference could escape

A compile test for the above (code from the example in the issue)
opened by wackbyte 1
Add CI via github actions
In response to this comment: https://github.com/matthieu-m/ghost-cell/pull/4#issuecomment-864388500

GH actions should start running by default for most repositories, example here

Added cargo test CI step

Added cargo clippy CI step
opened by mkatychev 1
Add `GhostCell::swap`

Based on Cell::swap. If the cells are the same, it's a no-op. I didn't put it with the other convenience methods since it requires unsafe. If GhostBorrowMut is sound, I'm thinking that this should be as well? (albeit this is much simpler than it)

opened by wackbyte 1
How to write a GhostCell data structure exposing non-GhostCell interface?

Consider we implemented a double-linked-list with GhostCell, and it's type definition would contains 'brand, and almost all it's method would take a GhostToken argument. Then if we want to expose it to end-user, with a std-like interface. It should be like LinkedList<T>, not LinkedList<'brand, T>. We should somehow create a wrapper storing both the structure and its GhostToken. So in every method, we use &mut or & to borrow the token of "the whole linked list", and access or mutate the content. But it seems to be not easy. We simply cannot "save" a lifetime. How can we hide GhostCell as an implementation detail for data structures?

opened by oxalica 1
A little concern about the novelty

Hi. I recently came across this project and be excited about it. However, digging this topic a little more lead me to this thread https://www.reddit.com/r/rust/comments/6hznoz/a_zerooverhead_refcell_variant/ . It seems that the same idea is proposed there 4 years ago. I wonder if there are any definitive difference between the Ghost-cell and the SyncCell in that thread.

opened by ylxdzsw 0
Trying to understand GhostCursor

Hi @matthieu-m, I am trying to understand GhostCursor, but I am somewhat stuck, so I'd appreciate some help. :) First and foremost, I am trying to understand the problem that GhostCursor is solving. From the docs, that is not clear to me. There is a "broken example" but it talks about half-ownership of some points so this already seems to be specific to static-rc... is there some way to phrase this just in terms of standard Rust types? Then I figured, maybe I need to look at how GhostCursor is used. So I looked at the linked list cursor based on this. Just from staring at the code I did not see the problem, so I tried to implement a cursor for our own toy linked list... and I think I have the same API as what you have, but without a GhostCursor. (I even added peek_next_mut on top and that works, too.) You can find it here. Am I missing something? One difference is that this linked list is based on an arena, which makes some things simpler than reference counting -- is that where the problem arises?

opened by RalfJung 6