ReentrantLock can be held by multiple threads at the same time

[tmiasko]

The code below verifies that the only one thread holds the ReentrantLock by recording the owner thread id inside. It should be true since the lock is never unlocked (note that the lock guard is leaked). In practice, in some executions the assertion fails:

#![feature(reentrant_lock)]
#![feature(thread_id_value)]

use std::cell::Cell;
use std::mem::ManuallyDrop;
use std::sync::ReentrantLock;
use std::thread;

fn main() {
    let lock = ReentrantLock::new(Cell::new(None));
    let run = || {
        let id = ManuallyDrop::new(lock.lock());
        match id.get() {
            None => id.set(Some(thread::current().id())),
            Some(id) => assert_eq!(id, thread::current().id()),
        }
    };
    thread::scope(|s| {
        s.spawn(run);
    });
    thread::scope(|s| {
        s.spawn(run);
    });
}

$ cargo run
thread '<unnamed>' panicked at src/main.rs:15:25:
assertion `left == right` failed
  left: ThreadId(2)
 right: ThreadId(3)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'main' panicked at src/main.rs:21:5:
a scoped thread panicked

Inspired by report from rust-lang/miri#3450, which also explains why this fails.

Ideally the assertion failure wouldn't be among possible executions.

[joboet]

This is a bit of rule-lawyering, but this isn't guaranteed. The documentation of lock says:

This function will block the caller until it is available to acquire the lock. Upon returning, the thread is the only thread with the lock held. When the thread calling this method already holds the lock, the call succeeds without blocking.

And all of these things are fulfilled, even in the case you describe.

[tmiasko]

Upon returning, the thread is the only thread with the lock held.

That part is false, since according to the documentation lock is unlocked when a lock guard is dropped. No lock guard is ever dropped in the example, so another thread still holds the lock.

If you would like to allow this execution, you would have to update the documentation to explain when and why lock was unlocked. Although, I would consider this to be clearly undesirable behavior.

Furthermore we already have ThreadId with necessary guarantees could be used to address the issue.

[joboet]

so another thread still holds the lock

No, the other thread has died.

Furthermore we already have ThreadId with necessary guarantees could be used to address the issue.

Unfortunately, getting the ThreadId is much more expensive, as it lives in Thread, which is Drop, and therefore needs a TLS destructor. Also, it will not be available in TLS destructors. We can get around this, of course, but the current approach is quite efficient, so it will be hard to beat.

[Sp00ph]

I agree that if this behavior stays as is, it should at least be very explicitly documented (something like "If a thread previously held the lock and terminated without releasing it, another thread may then be able to acquire the lock without deadlocking"). Still I'd prefer for the semantics to be "If any thread terminates while holding a lock, no other thread may ever reacquire the lock", which would require something like ThreadId which is unique over the lifetime of the process. I'm not convinced that the ThreadId approach would be much slower than the current one, it's mostly just cloning and then dropping an Arc, which is 2 atomic ops, and it saves a library call. On the other hand, using ThreadId would then always require a 64 bit ID, which might need some form of spin lock protecting every access on platforms that don't have 64 bit atomics.

[botahamec]

I know the point of Reentrant is to avoid deadlock, but my thinking is that if someone uses ManuallyDrop on the guard, they probably had a good reason for it, and might want to keep it locked. I'm kinda fighting my own bias here though, since I've also been trying to prevent deadlocks in Rust.

[joboet]

As this seems important to so many people, we should definitely add those docs.

I'm opposed to fixing this however, unless we find a really efficient solution. This gets called on every single println!, so it's definitely on the hot path. Also, we might consider using pthread_self for this in the future, which might be more efficient on Linux than the TLS access. pthread_ids can get reused, so if we fix this, we wouldn't be able to do that.

[CAD97]

Modulo the need to use 64-bit atomics, a ThreadId approach can be made almost entirely identical in performance to the current one: in std::thread when the current thread threadlocal, also have a thread local that only stores the thread ID and is set when the current thread is initialized and claims a thread ID. current_thread_unique_ptr is replaced with consuming something like the following from std::thread:

// in std::thread

thread_local! {
    static CURRENT: OnceCell<Thread> = const { OnceCell::new() };
    static CURRENT_ID: Cell<Option<ThreadId>> = const { Cell::new(None) };
}

/// Sets the thread handle for the current thread.
///
/// Panics if the handle has been set already or when called from a TLS destructor.
pub(crate) fn set_current(thread: Thread) {
    CURRENT.with(|current| {
        current.set(thread).unwrap();
        CURRENT_ID.set(Some(thread.id()));
    });
}

/// Gets a handle to the thread that invokes it.
///
/// In contrast to the public `current` function, this will not panic if called
/// from inside a TLS destructor.
pub(crate) fn try_current() -> Option<Thread> {
    CURRENT
        .try_with(|current| {
            let thread = current.get_or_init(|| Thread::new(imp::Thread::get_name())).clone();
            CURRENT_ID.set(thread.id().as_u64().get());
        })
        .ok()
}

/// Gets the id of the thread that invokes it.
///
/// If called from inside a TLS destructor and the thread was never
/// assigned an id, returns `None`.
pub(crate) fn try_current_id() -> Option<ThreadId> {
    if CURRENT_ID.get().is_none() {
        let _ = try_current();
    }
    CURRENT_ID.get()
}

The common case -- the thread was created by Rust and has its Thread data already created -- only gains a pointer read and predicted comparison against zero over the current current_thread_unique_ptr which uses the thread local address.

[Sp00ph]

Since the tid is only ever written to while holding a mutex, we could just use a seqlock to store it on platforms which only support 32-bit atomics (which I believe all platforms with std do), something like this: https://rust.godbolt.org/z/6dEnqz8be . While this means at least 4 atomic operations per tid access (including a store) instead of just 1, this seems acceptable to me because it would only affect 32 bit platforms anyways, the majority of platforms could just use a single 64 bit atomic access. Also, reader-writer contention would be extremely low, as the tid only gets written to when a thread acquires the first lock and when the last lock gets released. Would this together with the more efficient ThreadId fetching by @CAD97 be a reasonable tradeoff to allow the stricter guarantee for process-lifetime unique thread ids?

[RalfJung]

If you would like to allow this execution, you would have to update the documentation to explain when and why lock was unlocked. Although, I would consider this to be clearly undesirable behavior.

So the answer here is that the lock gets implicitly unlocked when the thread dies. This is not how Mutex works, but doesn't seem outrageous either.

Of course if it can be avoided at reasonable cost, that seems better.

Since the tid is only ever written to while holding a mutex, we could just use a seqlock to store it on platforms which only support 32-bit atomics (which I believe all platforms with std do)

I was about to remark on the unsoundness of seqlocks, but this variant actually seems fine -- you are using relaxed atomic accesses for the data, so there's no data race, just a race condition. Nice!

[Sp00ph]

So the answer here is that the lock gets implicitly unlocked when the thread dies. This is not how Mutex works, but doesn't seem outrageous either.

Note that it only looks unlocked to a subsequent thread if that thread is assigned the same TLS block as the thread that held the lock. Any other thread would still deadlock, which means we currently can't guarantee either behavior consistently.

[RalfJung]

Sure, this behavior is non-deterministic. I was just talking about the specific execution we are considering, where the second thread does acquire the lock.