[RFC PATCH 0/5] futex: introduce an optimistic spinning futex

[Waiman Long <Waiman.Long@hp.com>]

This patch series introduces two new futex command codes to support
a new optimistic spinning futex for implementing an exclusive lock
primitive that should perform better than the same primitive using
the wait-wake futex in cases where the lock owner is actively working
instead of waiting for I/O completion.

Optimistic spinning means that the waiting tasks spin within the
kernel for the lock owner to release the lock while it is running
instead of going to sleep and to be woken up later on. It is the same
mechanism that improves kernel mutex and rw semaphore performance,
especially on large system with many sockets and CPUs.

This patch series improves futex performance on two different fronts:
 1) Reducing the amount of the futex spinlock contention by using 2
    different spinlocks instead of just one for the wait-wake futex.
 2) Eliminating the context switching overhead and latency due to the
    sleeping and the waking of the waiting tasks.

The performance improvement varies depending on, to a certain extent,
the length of the critical section protected by futex.

Testing done on a 4-socket Westmere-EX boxes with 40 cores (HT off)
showed the following performance data (average kops/s) with various
load factor (number of pause instructions) used in the critical
section using an userspace mutex microbenchmark.

  Threads  Load	Waiting Futex	Spinning Futex 	  %Change
  -------  ----	-------------	--------------	  -------
    256	     1	     6894	    8883	    +29%
    256	    10	     3656	    4912	    +34%
    256	    50	     1332	    4358	   +227%
    256	   100	      792	    2753	   +248%
     10	     1	     6382	    4838	    -24%
     10	    10	     3614	    4748	    +31%
     10	    50	     1319	    3900	   +196%
     10	   100	      782	    2459	   +214%
      2	     1	     7905	    7194	   -9.0%
      2	    10	     4556	    4717	   +3.5%
      2	    50	     2191	    4167	    +90%
      2	   100	     1767	    2407	    +36%

Patch 1 introduces new futex command codes to provide a
mutex abstraction where the waiting tasks just go to sleep (no
spinning).

Patch 2 adds spinning to the mix.

Patch 3 enables wakened tasks to go back to the spinning state if
the owner is running.

Patch 4 changes sleeping queue from a simple FIFO list to an rbtree
sorted by process priority as well as the sequeunce the tasks enter
the kernel.

Patch 5 adds a new document file to describe the spinning futex.

Waiman Long (5):
  futex: add new exclusive lock & unlock command codes
  futex: add optimistic spinning to FUTEX_SPIN_LOCK
  spinning futex: move a wakened task to spinning
  spinning futex: put waiting tasks in a sorted rbtree
  futex, doc: add a document on how to use the spinning futexes

 Documentation/spinning-futex.txt |  109 +++++++
 include/uapi/linux/futex.h       |    4 +
 kernel/futex.c                   |  659 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 772 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/spinning-futex.txt