Mutex, align(4096)

#[align(4096)]
pub struct Foo { ...}

now, Vec<Mutex<Foo>> would be quite wasteful with space, so we might want to do something like:

pub struct Manager {
  data: Vec<Foo>,
  locks: Vec<Mutex<()>>
}

where acquiring locks[i], by convention, grants access to data[i]

This, of course, runs into all types of problems of: what is elements of data are freed out of sync ?

Is there a nice way to solve this problem without lots of unsafe ?

We can assume, after an initialization, the data.len() and locks.len() are fixed and equal.

You could pull this off with no (new) unsafe code using ouroboros to manage mutexes of references to data:

use ouroboros::self_referencing;
use std::sync::Mutex;

#[repr(align(4096))]
pub struct Foo {
    stuff: i32,
}

#[self_referencing]
pub struct Manager {
    data: Vec<Foo>,
    #[borrows(mut data)]
    #[not_covariant]
    locks: Vec<Mutex<&'this mut Foo>>,
}

impl Manager {
    pub fn from_foos(data: Vec<Foo>) -> Self {
        ManagerBuilder {
            data,
            locks_builder: |data| data.iter_mut().map(Mutex::new).collect(),
        }
        .build()
    }

    pub fn with_locked<R>(&self, index: usize, f: impl FnOnce(&mut Foo) -> R) -> R {
        // with_locks() is an ouroboros-generated private method
        self.with_locks(|locks| f(&mut *locks[index].lock().unwrap()))
    }
}

fn main() {
    let foos = vec![Foo { stuff: 1 }, Foo { stuff: 2 }];
    let manager = Manager::from_foos(foos);
    manager.with_locked(0, |foo| {
        foo.stuff += 10;
    });    
    manager.with_locked(1, |foo| {
        foo.stuff += 100;
    });    

    assert_eq!(11, manager.with_locked(0, |foo| foo.stuff));
}

This is more limited than an interface which can hand out individual lock guards, and it wastes some memory by keeping the references around, but it stays straightforwardly safe by using the Mutex to actually protect access (to the mutable references).

1 Like

I am new to self referential structs (and have tried to avoid them as much as possible). However, this looks very interesting.

#[self_referencing]
pub struct Manager {
    data: Vec<Foo>,
    #[borrows(mut data)]
    #[not_covariant]
    locks: Vec<Mutex<&'this mut Foo>>,
}

Can a similar technique be used to solve Help with My_Box::as_mut_ref ?

In particular, the locks: Vec<Mutex<&'this mut Foo>>, line which I'm still trying to understand.

Once you're entertaining pointer indirection, you could also use Vec<Mutex<Box<Foo>>>.

2 Likes

'this is a special lifetime that the ouroboros::self_referencing macro makes happen, which refers to any borrow of another field within that field. It is not part of normal Rust. The #[borrows] and #[not_covariant] attributes are also specific to ouroboros.

Advantages of this approach: it's very simple and does not depend on dubious tricks. (ouroboros has no known unsoundness and has been maintained well so far, but other self-reference crates have not fared well in the past.) Disadvantages: memory overhead of multiple allocations rather than just one, and the Foos are not stored contiguously so cache locality is likely worse.

Your original idea of using unsafe code to associate the mutex with the vector of data would likely be ideal, but of course has the risk of possibly writing incorrect unsafe code. If you do pursue it, note that the structure needs UnsafeCells,

pub struct Manager {
  data: Vec<UnsafeCell<Foo>>,
  locks: Vec<Mutex<()>>
}

or it would not be sound to mutate the data.

3 Likes

At 4kB alignment, you're strictly past that as a concern. There's a possibly more important equivalent of being memory prefetch friendly if accesses are sufficiently sequential though!

4 Likes

You can avoid the need for a callback-style-only access if the Mutex supports some form of mapped guards, as e.g. the Mutexes of parking_lot do, so that the 'this lifetime can be eliminated from the returned guard type:

use ouroboros::self_referencing;
use parking_lot::{MappedMutexGuard, Mutex, MutexGuard};

#[repr(align(4096))]
pub struct Foo {
    stuff: i32,
}

#[self_referencing]
pub struct Manager {
    data: Vec<Foo>,
    #[borrows(mut data)]
    #[not_covariant]
    locks: Vec<Mutex<&'this mut Foo>>,
}

impl Manager {
    pub fn from_foos(data: Vec<Foo>) -> Self {
        ManagerBuilder {
            data,
            locks_builder: |data| data.iter_mut().map(Mutex::new).collect(),
        }
        .build()
    }

    pub fn lock<'a>(&'a self, index: usize) -> MappedMutexGuard<'a, Foo> {
        // compiler doesn’t like to infer the `::<'a>` on its own here for some reason…
        self.with_locks::<'a>(|locks| MutexGuard::map(locks[index].lock(), |foo| *foo))
    }
}

fn main() {
    let foos = vec![Foo { stuff: 1 }, Foo { stuff: 2 }];
    let manager = Manager::from_foos(foos);
    {
        let mut foo = manager.lock(0);
        foo.stuff += 10;
    }
    {
        let mut foo = manager.lock(1);
        foo.stuff += 100;
    }

    assert_eq!(11, manager.lock(0).stuff);
}
1 Like

That's super interesting: Skimming through this GitHub thread today, Tracking Issue for scoped threads · Issue #93203 · rust-lang/rust · GitHub, there was a somewhat similar-looking case that only worked when an explicit lifetime was given to a function. And sure enough, the same solution apppears to work here, too: With #[feature(nll)] on nightly, the ::<'a> becomes unnecessary.

Proof of stake, self driving cars, and NLL are all going to be out next year, it'll be great! :yum:

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.