mozilla/rust — pull request #11520 by bill-myers (2014-01-13 22:34:15+00:00)
Title: Alternative lockless Mutex implementation (2nd try)

This is yet another attempt to create a satisfying implementation of Mutex, created since I believe I have managed to devise a working lockless algorithm.

I think the algorithm is correct, but please check.

This code is based on Alex Crichton's code, but replaces the "held" AtomicBool variable with a more sophisticated MutexState struct which consists of an atomic (lockers, queue_size) pair.

Also, we replace the intrusive MPSC queue implementation with one using list reversal, to remove the need to yield there and the need to store a stub node in the Mutex.

Features:
- No yields!
- Only one OS mutex
- Smallest Mutex struct size ever, since the new MPSC implementation no longers needs a stub node
- Fair even when combining native and green tasks
- Provides "can zap Mutex just after unlock" guarantee since we can now provide it for free

Non-features:
- Recursively locking will deadlock; this can be fixed, but enlarges the mutex or requires an OS mutex with a trylock that can detect recursion (but you can anyway deadlock by taking two mutexes in opposite orders from two threads, so not sure if it's essential)

Non-issues:
- Uses cmpxchg loops rather than non-loops; however, the previous version was using yield loops
- Green tasks can block on the OS mutex, but only when it is known that another thread is about to release it; again, the previous version was using yield loops for the same purpose, which are worse
- unlock is O(n) in the number of contending tasks in the worst case due to list reversal, when green tasks are used; however mutex lock is already fundamentally O(n) due to the obvious contention properties of mutexes, so this shouldn't really matter

The only known issue is that as implemented now this only works with up to 2^16 tasks on 32-bit and up to 2^32 tasks on 64-bit, since it needs to store two variables with a task count in a single atomic variable.

This shouldn't be a problem for two reasons:
1. As long as tasks use at least 64KB (in user stack, kernel stack, etc.) and 64-bit platforms actually only provide 48-bit addressing (this is the case for x86-64 right now) the 2^16/2^32 limitation cannot be overrun
2. Anyway, Pentium Pro+ and ARMv6+ provide 64-bit atomics in 32-bit mode (cmpxchg8b and ldrexd etc.) and x86-64 processors beyond the early Opterons as well as ARMv8 provide 128-bit atomics in 64-bit mode (cmpxchg16b), so it's only a matter of implementing support for and using those if desired

Currently Rust uses 2MB stacks by default, so programs that don't specify the stack size manually already cannot trip this limitation.