
--------------------------[ Reducing the cost of locks ]--------------------------

Locking the memory bus is very expensive in SMP. Thus OS designers try
to avoid it as much as possible: for example, per-CPU memory allocation in
Vmem tries to avoid it as much as possible. But one can only do it
so long before one needs to take a lock; so there's a big payoff to 
lowering the cost of locks themselves.

For this reason, in Illumos, mutex_exit does _not_ use an "atomic" 
instruction. That is, in x86, does not LOCK the memory bus -- indeed, 
have a look at the x86_64 and ia32 implementations of mutex_exit respectively:
http://src.illumos.org/source/xref/illumos-gate/usr/src/uts/intel/ia32/ml/lock_prim.s#698
and 
http://src.illumos.org/source/xref/illumos-gate/usr/src/uts/intel/ia32/ml/lock_prim.s#869
---no LOCKs. The Big Theory Statement explains why this works:

http://src.illumos.org/source/xref/illumos-gate/usr/src/uts/common/os/mutex.c#62

Mark the statement of the line 124. Wow.

Linux kernel also has a lock-less spin_unlock:
http://lxr.free-electrons.com/source/include/asm-i386/spinlock.h?v=2.4.37#L67
Note the #ifdef's : line 75 spin_unlock_string is the common case (the
atomic special case starts at line 93).

Some of Linus Torvalds' responses to the Linux kernel list 
discussion of locks and buses are here:
http://yarchive.net/comp/linux/write_barriers.html
(start at "09 Mar 2006 05:39:18 UTC" and read down)

--------------------------[ Futexes ]-------------------------

Original paper in which futexes were introduced:
https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf

Ulrich Drepper's paper about them:
http://www.akkadia.org/drepper/futex.pdf

Shorter later summary:
http://locklessinc.com/articles/mutex_cv_futex/

Futex implementation code: http://lxr.free-electrons.com/source/kernel/futex.c

-------------------------[ The Futex bug ]-------------------------

The bug is explained in a series of 3 blogposts:
 http://blog.nativeflow.com/topic/futex
(Start reading from the bottom post,
   http://blog.nativeflow.com/the-futex-vulnerability)

CVE summary:
http://www.cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-3153

Exploit example:
http://www.exploit-db.com/exploits/35370/

The fix (which showcases the problem):
https://android.googlesource.com/kernel/goldfish.git/+/52ecbbcb920fa3d529833b1d8ad97d4575c36bd9%5E!/




