5 ms·
Modern day user-mode pthread mutex uses the futex kernel syscall [1] to implement the lock, which avoids the syscall in the non-contended case, so it can be ver
by ww520 7y ago
Modern day user-mode pthread mutex uses the futex kernel syscall [1] to implement the lock, which avoids the syscall in the non-contended case, so it can be very fast, acquiring the lock in the user-mode code entirely. I'm not sure whether the Rust's mutex API is a wrapper on the pthread mutex or calling the old kernel's mutex syscall directly.
Basically the user mode mutex lock is implemented as:
// In user-mode, if the lock flag is free as 0, lock it to 1 and exit
while !atomic_compare_and_swap(&lock, 0, 1)
// Lock not free, sleeps until the flag is changed back to 0
futex_wait(&lock, 0) // syscall to kernel
When futex_wait() returns, it means the flag has been set back to 0 by the other thread's unlock, and the kernel wakes my thread up so I can check it again. However, another thread can come in and grab the lock in the meantime, so I need to loop back to check again. The atomic CAS operation is the one acquiring the lock.
[1] https://github.com/lattera/glibc/blob/master/nptl/pthread_mutex_lock.c#L168 https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...
Edit: the atomic_compare_and_swap can be just a macro to the assembly CMPXCHG, so it's very fast to acquire a lock if no one else holding the lock.
- bluejekyll 7y agohttps://github.com/rust-lang/rust/blob/master/src/libstd/sys/unix/mutex.rs#L26 https://github.com/rust-lang/rust/blob/master/src/libstd/sys... Looks like it’s relying glibc for lock elision. Mind you the parking_lot::Mutex in the article is not the stdlib implementation, documented here: https://docs.rs/parking_lot/0.10.0/parking_lot/type.Mutex.html https://docs.rs/parking_lot/0.10.0/parking_lot/type.Mutex.ht... And that looks like it’s not using pthread, instead relying on primitives: https://github.com/Amanieu/parking_lot/blob/master/src/raw_mutex.rs https://github.com/Amanieu/parking_lot/blob/master/src/raw_m...
- ww520 7y agoThen it's using the futex implementation. It's very efficient.
- bluejekyll 7y agoI updated my comment. The fastest impl, parking_lot, appears to be a ground up atomic based mutex that doesn’t rely on pthread at all.
- ww520 7y agoIt seems to be doing similar logic. 1. Does a CAS with compare_exchange_weak() at line 69. 2. Then call lock_slow() at line 72 to do spinlocking (Guh!). 3. The call to parking_lot_core::park() at line 256 seems to sleep wait.
- bluejekyll 7y agoYes. I just meant to say that it’s not a pthread based implementation, potentially making it more portable.
- asveikau 7y agoThe P in pthread is the P from Posix which stands for portable. Now, the "zero syscalls for uncontended pthread mutices via futex" optimization is Linux specific and may not be replicated elsewhere. Or it may. It's not Posix, but I know for instance win32 critical sections look a lot like spinlocks when not contended but do syscalls to block, which sounds a lot like a futex. So that would put that technique as dating to the 1990s at the latest. Futex landed in 2002.
- bluejekyll 7y ago> The P in pthread is the P from Posix which stands for portable. What’s your point here? Posix is portable across posix compliant systems, it is not portable beyond that. There are many systems that are posix, but Rust targets more than that.
- asveikau 7y agoAvoiding pthreads because they aren't portable and replacing them with a spinlock sounds a little bit like madness, that was my point. What is the non-posix target you have in mind? Windows? Seems like conditionally compiling against either pthreads or win32 critical section [or anything else] is a feasible thing and reasonable action. Maybe even the spinlock as a last resort.