Add sync::ReentrantLock

[joboet]

Proposal

Problem statement

Provide a lightweight, correct reentrant mutex in std.

Motivation, use-cases

A number of crates need a reentrant mutex for implementing deadlock-free synchronization. Because such a lock is not currently available, crate authors turn to parking_lot¹ (bringing in quite a lot of extra weight for such a simple purpose), manually wrap pthread_mutex ² (aaaaah!) or implement it themselves ³, sometimes in very hacky fashion⁴.

Solution sketches

std already has the private ReentrantMutex, which it uses to implement Stdout locking. I propose to make this type public with the following API (copying some elements from Mutex):

// in std::sync

pub struct ReentrantLock<T: ?Sized> { .. }

impl<T> ReentrantLock<T> {
    pub const fn new(t: T) -> ReentrantLock<T>;
    pub const fn into_inner(self) -> T;
}

impl<T: ?Sized> ReentrantLock<T> {
    pub fn lock(&self) -> ReentrantLockGuard<'_, T>;
    pub fn get_mut(&mut self) -> &mut T;
}

impl<T: ?Sized + Send> Send for ReentrantLock<T> {}
impl<T: ?Sized + Send> Sync for ReentrantLock<T> {}

impl<T: ?Sized + Debug> Debug for ReentrantLock<T> { .. }
impl<T: Default> Default for ReentrantLock<T> { .. }
impl<T> From<T> for ReentrantLock<T> { .. }

pub struct ReentrantLockGuard<'a, T> { .. }

impl<'a, T: ?Sized> !Send for ReentrantLockGuard<'a, T> {}
impl<'a, T: ?Sized + Sync> Sync for ReentrantLockGuard<'a, T> {}

impl<'a, T: ?Sized> Deref for ReentrantLockGuard<'a, T> { .. }
impl<'a, T: ?Sized + Debug> Debug for ReentrantLockGuard<'a, T> { .. }
impl<'a, T: ?Sized + Display> Display for ReentrantLockGuard<'a, T> { .. }

Unresolved questions

Poisoning

I would argue that ReentrantLock should not implement lock poisoning. Since it only provides shared access, breaking the invariants of the inner type is something that the lock has no control over, as it requires interior mutability. It would make sense to require that T: RefUnwindSafe, but I think that is too inconvenient for now. If RefUnwindSafe were a lint trait, it should definitely be used.

Fallible locking

Is there a need for fallible locking, even if it cannot fail because of reentrancy? How would this look like, considering that TryLockResult also has a poisoning case, which would never be used here?

Naming

New synchronization primitives like OnceLock have used the Lock suffix. IMHO the name ReentrantLock rhymes well with the other types and is more consistent, but ReentrantMutex better highlights the similarity to Mutex.

Links and related work

• parking_lot's ReentrantMutex

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

Footnotes

1. https://github.com/imgui-rs/imgui-rs/blob/ba02f2287fb5781bb921b7dc4a7ec95cd88b74d0/imgui/src/context.rs#L1 ↩

2. https://github.com/douchuan/jvm/blob/5678df31a13ec56faa0daddb561d34ae2def8f1d/crates/vm/src/runtime/thread/mutex.rs#L10 ↩

3. https://github.com/servo/servo/blob/be6e25a1b223325f47db85050c47982c641c8f0f/components/remutex/lib.rs#L156 ↩

4. https://github.com/rust-lang/backtrace-rs/blob/a3406f93f3e6d91e05525c671fa694a0aea22c82/src/lib.rs#L154 ↩

[m-ou-se]

We briefly discussed this in the libs-api meeting.

We're happy to see this added as unstable. Feel free to open a tracking issue (with the unresolved questions) and add its number to your implementation PR. Thanks!

[kennytm]

New synchronization primitives like OnceLock have used the Lock suffix. IMHO the name ReentrantLock rhymes well with the other types and is more consistent, but ReentrantMutex better highlights the similarity to Mutex.

I think it's better keeping the name ReentrantMutex (↔ Mutex) because there could be a ReentrantRwLock (↔ RwLock).

[pitaj]

What different behavior would ReentrantRwLock have?

[kennytm]

You mean RwLock vs ReentrantRwLock? Acquiring the second .write() lock nested within the lifetime of the first guard won't dead-lock?

[Veykril]

ReentrantRwLock can't have a write() that returns mutable access, as otherwise you could alias, hence why ReentrantMutex only gives read access when locked.

[programmerjake]

about the only sane ReentrantRwLock API I can think of is:

pub struct ReentrantRwLock<T> { .. }

unsafe impl<T: Send> Send for ReentrantRwLock<T> {}
unsafe impl<T: Send + Sync> Sync for ReentrantRwLock<T> {}

impl<T> ReentrantRwLock<T> {
    pub fn read(&self) -> ReadLock<T> { .. }
    pub fn write(&self) -> WriteLock<T> { .. }
    ..
}

pub struct ReadLock<'a, T: 'a> { .. }
pub struct WriteLock<'a, T: 'a> { .. }

impl<T> Deref for ReadLock<'_, T> {
    type Target = T; // allows access via `&T` since we have a read lock
    fn deref(&self) -> &Self::Target { .. }
}

impl<T> Deref for WriteLock<'_, T> {
    type Target = Cell<T>; // allows access via `&Cell<T>` (shared mutable access) since we have a write lock
    fn deref(&self) -> &Self::Target { .. }
}

[kennytm]

The thing about RwLock besides getting a &mut vs & is that the read (shared) locks don't block each other and write (exclusive) locks block all the read locks. Both guards returning &T is ok.

Anyway I'm not proposing std to include ReentrantRwLock, I'm just saying the name ReentrantMutex sounds better than ReentrantLock. The naming motivation also mentioned OnceLock and LazyLock, but these two have totally different API from Mutex so I think that argument is irrelevant. Not to mention that, for "newer primitives", we have Exclusive rather than ExclusiveLock.

[programmerjake]

The thing about RwLock besides getting a &mut vs & is that the read (shared) locks don't block each other and write (exclusive) locks block all the read locks. Both guards returning &T is ok.

if both guards return &T that's kinda throwing away the advantage of write locks, since &T doesn't allow writing arbitrary T but &Cell<T> does...since the lock requires T: Send + Sync there is no other way for T to know it doesn't need any inter-thread synchronization when returned by the write lock.

ReentrantLock<T> doesn't have this problem since it doesn't require T: Sync

[RalfJung]

A number of crates need a reentrant mutex for implementing deadlock-free synchronization.

This has me confused for a bit, since deadlocks are still possible with reentrant locks -- e.g. by lock order mismatches. Would be good to spell out a bit more where reentrant mutexes come up.

[joboet]

This has me confused for a bit, since deadlocks are still possible with reentrant locks -- e.g. by lock order mismatches. Would be good to spell out a bit more where reentrant mutexes come up.

As this is a closed ACP, I won't bother to change that here. The tracking issue and documentation are (a bit) clearer about the intended use-case, do they resolve your concern?