`mvcc_cell`: A software-transactional memory primitive

announcements
1

I've finally gotten around to publishing the STM crate I've been working on.

I'd appreciate any feedback on the API and design, especially if you find any soundness issues.

Future plans include additional getters/setters that don't necessarily require Clone and some transaction-aware collection types.

3 Likes
2

Well, I always enjoy the game of re-inventing/re-implementing the way to exploit incorrect Send- or Sync-bounds for segfaults. :slight_smile:

use std::cell::Cell;

use mvcc_cell::{Mvcc, MvccCell};

fn main() {
    let c = Mvcc::new();
    let cell = MvccCell::new(&c, Box::new(Cell::new(Ok::<&[usize], &[()]>(&[]))));
    let bad_slice = std::thread::scope(|s| {
        let handle = s.spawn(|| {
            let t = c.begin();
            let r = &t[&cell];
            loop {
                let s = r.get();
                if let Ok(v) = s {
                    if !v.is_empty() {
                        break v;
                    }
                }
            }
        });
        let t = c.begin();
        let r = &t[&cell];
        loop {
            r.set(Ok(&[]));
            r.set(Err(&[(); usize::MAX]));
            if handle.is_finished() {
                break;
            }
        }
        handle.join().unwrap()
    });
    println!("Here we go:\n{bad_slice:?}");
}

Here we go:
[7955997338301067891, 2334397761194258990, …… 𝓢𝓝𝓘𝓟 ……, 135959018790191158, [1]    707570 segmentation fault (core dumped)
2 Likes
3

I'm trying to wrap my head around how you broke this, and why the automatic Send and Sync implementations didn't block it. The root of the problem seems to be that the Mutex inside MvccBox<T> is only meant to synchronize the addition/removal of committed Ts, but not access to the Ts themselves. But my use of unsafe to break a real reference outside the guard fooled the compiler into thinking the Ts were synchronized when they really weren't.

If that's the case, the fix is to include a PhantomData<Arc<T>> field inside MvccBox to indicate that the Ts need to have their own synchronization if a MvccCell<T> crosses a thread boundary. Does that sound right to you?

4

Yes, sounds right. Mutex is only designed to do mutually exclusive access. Hacking the lifetime to make it produce (actually shared) shared references means that Mutex’s inherent Send/Sync implementations are no longer appropriate for your use-case.

Rustdoc kindly points out the current implementations:

impl<T: ?Sized> Send for MvccCell<T>
where
    T: Send,
impl<T: ?Sized> Sync for MvccCell<T>
where
    T: Send,

and those are of course inappropriate for a type that also offers (non-mutually-exclusive) &self -> &T access. The Send impl should be fine; you’d pessimize that one by adding Arc<T> phantom data. I assume RwLock is a better point of comparison, so maybe use a phantom-data of that if you don’t want to write a manual Sync implementation :slight_smile:

1 Like
5

It really is impressive, right? What’s (almost/essentially) just a single unsafe in the whole crate can already be one unsafe too much, and can have subtle indirect effects one initially never would have thought of.

3 Likes
6

RwLock is a better comparison (and what I'll use), but doesn't make much difference in practice: I'm using Arc<MvccBox<T>> internally, so Arc's Send bound gets applied anyway.

Which is correct, as MvccCell::clone() would otherwise give you a Sendable alias.

Fixed version published shortly.

I haven't even considered the other auto traits (Ref?UnwindSafe), though ...

1 Like
7

Oh, right… I forgot it’s more of an Arc<RwLock<T>>. Then the current Send implementation was unsound, too.

8

Those aren’t unsafe traits.

1 Like
9

v0.1.2 published with the corrected bounds

2 Likes