Ordering mutexes, and retrieving raw mutex handle

[Xirdus]

Some time ago, a discussion on Reddit made me think about how one can do ordered locks of Rust mutexes. Sadly, it seems it can't be done right now, because there exists no interface that would let order mutexes. Hence, I propose the following changes to the Mutex API. The first two are independent of each other, but still related enough that I think they can be put in the same RFC.

1. PartialOrd implementation for Mutex

Add the following trait implementations:

impl<T1: ?Sized, T2: ?Sized> PartialEq<Mutex<T2>> for Mutex<T1> { ... }

impl<T: ?Sized> Eq for Mutex {}

impl<T1: ?Sized, T2: ?Sized> PartialOrd<Mutex<T2>> for Mutex<T1> { ... }

impl<T: ?Sized> Ord for Mutex { ... }

This will allow comparing any mutexes of any type with each other. The implementations will use the address of inner box for comparisons, which guarantees strict ordering even when mutexes are moved. The downside is that Mutex would then have to guarantee strict order forever.

2. Expose native mutex handle

This will allow to use native OS API for whatever purpose, and also allow to share mutexes through FFI. Also, in case PartialOrd idea gets rejected, it will allow to implement equivalent functionality outside of sync module, or even in 3rd-party crate. I don't think there are any downsides to this idea, except for usual subjective feelings of API bloat and exposing guts of implementation.

3. ordered_lock! macro

If either of the above ideas get implemented, the next step would be to provide an easy and ergonomic API for ordered locking - due to lack of variadic generics in current Rust, the next best thing is a macro that takes arbitrary number of mutexes as arguments and returns a tuple of MutexGuards. Of course it can be implemented in 3rd-party crate just as well.

[TimNN]

To me, all three proposals seem to be entirely unrelated. Some thoughts:

1. As far as I am aware none of the other "Wrapper" types (Rc, RefCell, Arc, Box) implement the comparison operators if the wrapped type does not. Thus the proposal here seems to be inconsistent and, more important, surprising: I would not expect mutexes to be ordered by some arbitrary location in memory. Additionally, I believe that the fact that mutexes have an "inner box" is just an implementation detail. It seems entirely possible that the standard library want's to adopt something like parking_lot's mutexes in the future which do not use boxes.

2. I think the downside "exposing the guts of implementation" can not be so easily be dismissed, at least if you want to stabilise the newly added methods. This would essentially tie us to one specific mutex implementation, which seems undesirable to me. You mention "sharing mutexes through FFI". I believe this goal would be much better served by an external crate, which exposes the same mutexe implementation used by the foreign functions you want to communicate with.

3. This seems to be the core problem you want to solve, however I (personally) have no Idea what's so special about "ordered locking", and, more importantly, why you would need either (1) or (2) for that. Would an ordered_lock! macro be expected to sort the mutexes before locking? What if I want them locked in a different order? Why doesn't let (a, b, c) = (mutex_a.lock(), mutex_b.lock(), mutex_c.lock()); work?

---

Live Edit: So, after some googling "ordered locking" seems to try to solve the following problem:

If multiple thread try to acquire the same set of resource, but in different orders, this can easily lead to a deadlock. If all threads acquire the resources in the same order, a deadlock can be avoided.

This seems to be better solved using some wrapper type around mutexes, which adds some (maybe thread local) validation.

[sfackler]

Ordering of the mutexes should be achievable by comparing the addresses of the mutexes themselves - they can't be moved if multiple threads have access to them at the same time (or if they're locked) so everything should work.

[goto40]

Ordering of the mutexes should be achievable by comparing the addresses of the mutexes themselves - they can't be moved if multiple threads have access to them at the same time (or if they're locked) so everything should work.

Is this true? I think mutexes can be moved:

fn main() {
    use std::sync::Mutex;
    let m = Mutex::new(5);
    let m2=m;
}

The ability of mutexes to be ordered would solve problems, in my opinion. Like std::lock in C++, which probably orders the mutexes...

[kennytm]

Expose native mutex handle

There's no guarantee that std::sync::Mutex uses any particular OS API. For instance, very recently on 1.78 the Windows target changed the Mutex implementation from SRWLOCK to Futex (rust-lang/rust#121956) by dropping Win7 support. If we had exposed the native mutex handle "to use native OS API for whatever purpose", such change of implementation wouldn't be possible because those code relying on it being a SRWLOCK would be broken.

PartialOrd implementation for Mutex

Implementing (Partial)Ord/Eq on Mutex is very strange, and I think this would lead to some hard to spot bugs such as

type Object = Arc<Mutex<u32>>;

fn do_something(a: Object, b: Object) {
    if a < b { // probably you actually mean {*a.lock().unwrap()} < {*b.lock().unwrap()}
        println!("a is less than b!");
    }
}

Unless you want to put Mutex as a BTreeMap key I can't think of any reason you need to implement these traits directly on the mutex. You could instead introduce an inherent method similar to f32::total_cmp.

impl<T> Mutex<T> {
    pub fn addr_cmp<U>(&self, other: &Mutex<U>) -> std::cmp::Ordering;
}

Like std::lock in C++, which probably orders the mutexes...

At least for libc++ no sorting is involved. The 2-mutex case is like

pub fn lock_2<'a, 'b, T, U>(
    a: &'a Mutex<T>,
    b: &'b Mutex<U>,
) -> (MutexGuard<'a, T>, MutexGuard<'b, U>) {
    loop {
        {
            let guard_a = a.lock().unwrap();
            match b.try_lock() {
                Ok(guard_b) => return (guard_a, guard_b),
                Err(TryLockError::WouldBlock) => {}
                Err(TryLockError::Poisoned(_)) => panic!(),
            }
        }
        yield_now();
        {
            let guard_b = b.lock().unwrap();
            match a.try_lock() {
                Ok(guard_a) => return (guard_a, guard_b),
                Err(TryLockError::WouldBlock) => {}
                Err(TryLockError::Poisoned(_)) => panic!(),
            }
        }
        yield_now();
    }
}

and the multi-lock case is generalizing this by lock one and try_lock the rest in a round-robin way.

[goto40]

Thank you for these Insights! Are you aware of any plans to include something like C++-std::lock in the rust standard lib?

[kennytm]

@goto40 you could file an ACP for this. (But C++'s std::lock approach may not be the best suitable for Rust.)