Using Mutex to guard collection structure, but not values

I’m working on a software-transactional memory library, and I need to have some collections where I can guard structure changes with a lock, but need the items themselves to be unguarded. A minimal example of my approach for this is here (where Vec will be something else in practice, like HashMap). Does this look like a sensible approach?

use std::cell::UnsafeCell;
use std::sync::Mutex;

#[derive(Default)]
struct RoExample<T>(Mutex<Vec<Box<T>>>);

impl<T> RoExample<T> {
    fn get(&self, i: usize) -> &T {
        let guard = self.0.lock().unwrap();
        let item: *const T = &*guard[i] as *const T;

        // Safety: item addresses are stable, never dropped before self, and never the target of &mut
        unsafe { &*item }
    }

    fn add(&self, val: T) {
        self.0.lock().unwrap().insert(0, Box::new(val));
    }
}

#[derive(Default)]
struct RwExample<T>(Mutex<Vec<UnsafeCell<Box<T>>>>);

impl<T> RwExample<T> {
    fn get_mut(&self, i: usize) -> &mut T {
        let guard = self.0.lock().unwrap();

        // Safety: item addresses are stable, never dropped before self,
        //         and aliasing rules are enforced externally (not shown)
        unsafe { &mut **guard[i].get() }
    }

    fn add(&self, val: T) {
        self.0
            .lock()
            .unwrap()
            .insert(0, UnsafeCell::new(Box::new(val)));
    }
}
1 Like

RwExample::get_mut() is unsound because it allows mutable aliasing.

fn main() {
    let v = RwExample::<char>::default();
    v.add('a');
    let a = v.get_mut(0);
    let b = v.get_mut(0);

    dbg!(a, b);
}

The error from miri is:

error: Undefined Behavior: trying to retag from <3913> for Unique permission at alloc1819[0x0], but that tag does not exist in the borrow stack for this location
  --> src/main.rs:47:5
   |
47 |     dbg!(a, b);
   |     ^^^^^^^^^^
   |     |
   |     trying to retag from <3913> for Unique permission at alloc1819[0x0], but that tag does not exist in the borrow stack for this location
   |     this error occurs as part of retag at alloc1819[0x0..0x4]
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <3913> was created by a Unique retag at offsets [0x0..0x4]
  --> src/main.rs:44:13
   |
44 |     let a = v.get_mut(0);
   |             ^^^^^^^^^^^^
help: <3913> was later invalidated at offsets [0x0..0x4] by a Unique retag
  --> src/main.rs:30:18
   |
30 |         unsafe { &mut **guard[i].get() }
   |                  ^^^^^^^^^^^^^^^^^^^^^
   = note: BACKTRACE:
   = note: inside `main` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/macros.rs:351:13
   = note: this error originates in the macro `$crate::dbg` which comes from the expansion of the macro `dbg` (in Nightly builds, run with -Z macro-backtrace for more info)

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to previous error; 2 warnings emitted
2 Likes

Yes; that’s because I left out the aliasing-prevention mechanism for the sake of brevity:

In my actual application, this is used to provide a temporary typed storage space for a transaction, which is not itself dependent on the storage type: Instead of a usize parameter, it takes &mut Transaction, and the uses the guaranteed-unique transaction ID as the collection key.


To give a broader overview, there are three main types in the system:

  • Controller, which keeps track of open transactions and ensures commits are serializable.
  • Transaction, which acts as a snapshot of the system and collects changes to be atomically committed.
  • MvccCell<T>, which represents a storage location that can take part in atomic updates.

These collections are used within MvccCell to store a history of committed values and pending values, respectively.

I suppose this is an argument to mark get_mut as unsafe, even if it is used only internally. It can only be truly safe if it also sound to use in any safe code (including the example that introduces UB). If nothing else, keeping it as a safe API means that any refactor in the future is a potential footgun for introducing UB by mistake because unsafe is "out of sight, out of mind".


BTW, I like the RoExample. I was confused why it worked at all because I somehow completely missed the Box. It's a good way to reorder the collection while keeping references stable, if you have a need for this property!

3 Likes

This is a bit more representative example of my read-write case:

use std::cell::UnsafeCell;
use std::collections::HashMap;
use std::sync::Mutex;

/// Safety: no two concurrent values of the same type
///         may have the same id, and a value's id
///         must never change
unsafe trait HasUniqueId: Sized {
    fn unique_id(&self) -> u64;
}

#[derive(Debug)]
struct Token(u64);

/// UNSOUND; for example only
unsafe impl HasUniqueId for Token {
    fn unique_id(&self) -> u64 {
        self.0
    }
}

#[derive(Default)]
struct RwExample<T>(Mutex<HashMap<u64, UnsafeCell<Box<T>>>>);

impl<T> RwExample<T> {
    fn get_mut<'a>(&'a self, tok: &'a mut Token) -> &'a mut T {
        let guard = self.0.lock().unwrap();

        // Safety: item addresses are stable, never dropped before self,
        //         and aliasing rules are enforced externally (not shown)
        unsafe { &mut **guard.get(&tok.unique_id()).unwrap().get() }
    }

    fn get<'a>(&'a self, tok: &'a Token) -> &'a T {
        let guard = self.0.lock().unwrap();

        // Safety: item addresses are stable, never dropped before self,
        //         and aliasing rules are enforced externally (not shown)
        unsafe { &**guard.get(&tok.unique_id()).unwrap().get() }
    }

    fn add(&self, tok: &mut Token, val: T) {
        self.0
            .lock()
            .unwrap()
            .insert(tok.unique_id(), UnsafeCell::new(Box::new(val)));
    }
}