mozilla/rust — pull request #11509 by bill-myers (2014-01-13 04:44:34+00:00)
Title: Alternative Mutex implementation

Pull #11462 implements a Mutex using a lockless algorithm that has to use thread_yield.

This is an alternative approach that removes all yields by introducing an internal lock, while still keeping the principle that in the native case the mutex must reduce to the native mutex.

Furthermore, this implementation should be fair even when mixing native and green mutexes (assuming that the OS mutex is fair), can always detect recursive mutex locking, and support for green threads can be disabled by changing a constant to improve performance.

There is no longer a need for the MPSC intrusive queue since we now protect the queue with the internal queue_lock.

It compiles and passes tests, but of course would need review.

Contention on the internal lock with green tasks shouldn't be a problem, since such a contention would happen anyway if the tasks were native, and the MPSC queue still involves atomics on a common cacheline, which also generates contention.

The Linux kernel also uses a spinlock to protect its own sleepable mutexes in the contended case (note that in the Linux kernel mutexes all threads behave as green tasks since there is no OS mutex to fallback to, so the requirements are a bit different).

Someone with access to a large server could perhaps benchmark both approaches if desired.

This does not provide the "as soon as unlock() returns you can obliterate the mutex" guarantee, but this is unnecessary for Rust mutexes as discussed in pull #11462.