[PATCH v4 00/20] futex: Introducing throughput-optimized (TP) futexes

[Waiman Long]

 v3->v4:
  - Properly handle EFAULT error due to page fault.
  - Extend the use cases of TP futexes to userspace rwlock.
  - Change the lock handoff trigger from number of spinnings to
    elapsed time (5ms).
  - Various updates to the "perf bench futex mutex" microbenchmark.
  - Add a new "perf bench futex rwlock" microbenchmark for measuring
    rwlock performance.
  - Add mutex_owner to futex_state object to hold the serialization
    mutex owner.
  - Streamline a number of helper functions and other miscellenous
    coding improvements.
  - Rebase the patchset to the 4.10 kernel.

 v2->v3:
  - Use the abbreviation TP for the new futexes instead of TO.
  - Make a number of changes accordingly to review comments from
    ThomasG, PeterZ and MikeG.
  - Breaks the main futex patch into smaller pieces to make them easier
    to review.

 v1->v2:
  - Adds an explicit lock hand-off mechanism.
  - Adds timeout support.
  - Simplifies the required userspace code.
  - Fixes a number of problems in the v1 code.

This patchset introduces a new futex implementation called
throughput-optimized (TP) futexes. It is similar to PI futexes in its
calling convention, but provides better throughput than the wait-wake
(WW) futexes by encouraging lock stealing and optimistic spinning.

The new TP futexes can be used in implementing both userspace mutexes
and rwlocks. They provides better performance while simplifying the
userspace locking implementation at the same time. The WW futexes
are still needed to implement other synchronization primitives like
conditional variables and semaphores that cannot be handled by the
TP futexes.

Another advantage of TP futexes is that it has a built-in lock handoff
mechanism to prevent lock starvation from happenning as long as the
underlying kernel mutex doesn't have lock starvation problem.

Patches 1-6 are preparatory patches that pave the way to implement
the TP futexes.

Patch 7 implements the basic TP futex that can support userspace
mutexes.

Patch 8 adds robust handling to TP futex to handle the death of TP
futex exclusive lock owners.

Patch 9 adds a lock hand-off mechanism that can prevent lock starvation
to happen while introducing minimal runtime overhead.

Patch 10 enables the FUTEX_LOCK futex(2) syscall to return status
information, such as how the lock is acquired and how many time
the task needs to sleep in the spinning loop, that can be used by
userspace utilities to monitor how the TP futexes are performing.

Patch 11 enables userspace applications to supply a timeout value to
abort the lock acquisition attempt after the specified time period
has passed.

Patch 12 adds a new document tp-futex.txt in the Documentation
directory to describe the new TP futexes.

Patch 13 adds a microbenchmark to the "perf bench futex" suite to
measure the performance of the WW, PI and TP futexes when implementing
a userspace mutex.

Patch 14 extends the TP futexes to support userspace rwlocks.

Patch 15 enables more reader lock stealing of TP futexes in the kernel.

Patch 16 groups readers together as a spin group to enhance reader
throughput.

Patch 17 updates the tp-futex.txt file to add information about
rwlock support.

Patch 18 adds another microbenchmark to the "perf bench futex" suite
to measure the performance of the WW, TP futexes and Glibc when
implementing a userspace rwlock.

Patch 19 updates the wake_up_q() function to returns the number
woken tasks.

Patch 20 enables the dumping of internal futex state information
via debugfs.

All the benchmark results shown in the change logs were produced by
the microbenchmarks included in this patchset. So everyone can run
the microbenchmark to see how the TP futexes perform and behave in
their own test systems.

Once this patchset is finalized, an updated manpage patch to document
the new TP futexes will be sent out. The next step will then be to
make Glibc NTPL use the new TP futexes.

Performance highlight in term of average locking rates (ops/sec)
on a 2-socket system are as follows:

                WW futex       TP futex      Glibc
                --------       --------      -----
  mutex         121,129        152,242         -
  rwlock         99,149        162,887       30,362

Patches 7 and 16 contain more detailed information about the
performance characteristics of the TP futexes when implementing
userspace mutex and rwlock respectively when compared with other
possible way of doing so via the wait-wake futexes.

Waiman Long (20):
  futex: Consolidate duplicated timer setup code
  futex: Rename futex_pi_state to futex_state
  futex: Add helpers to get & cmpxchg futex value without lock
  futex: Consolidate pure pi_state_list add & delete codes to helpers
  futex: Add a new futex type field into futex_state
  futex: Allow direct attachment of futex_state objects to hash bucket
  futex: Introduce throughput-optimized (TP) futexes
  TP-futex: Enable robust handling
  TP-futex: Implement lock handoff to prevent lock starvation
  TP-futex: Return status code on FUTEX_LOCK calls
  TP-futex: Add timeout support
  TP-futex, doc: Add TP futexes documentation
  perf bench: New microbenchmark for userspace mutex performance
  TP-futex: Support userspace reader/writer locks
  TP-futex: Enable kernel reader lock stealing
  TP-futex: Group readers together in wait queue
  TP-futex, doc: Update TP futexes document on shared locking
  perf bench: New microbenchmark for userspace rwlock performance
  sched, TP-futex: Make wake_up_q() return wakeup count
  futex: Dump internal futex state via debugfs

 Documentation/00-INDEX         |    2 +
 Documentation/tp-futex.txt     |  284 +++++++
 include/linux/sched.h          |    6 +-
 include/uapi/linux/futex.h     |   32 +-
 kernel/futex.c                 | 1411 +++++++++++++++++++++++++++++++---
 kernel/sched/core.c            |    6 +-
 tools/perf/bench/Build         |    1 +
 tools/perf/bench/bench.h       |    2 +
 tools/perf/bench/futex-locks.c | 1654 ++++++++++++++++++++++++++++++++++++++++
 tools/perf/bench/futex.h       |   43 ++
 tools/perf/builtin-bench.c     |   11 +
 tools/perf/check-headers.sh    |    4 +
 12 files changed, 3335 insertions(+), 121 deletions(-)
 create mode 100644 Documentation/tp-futex.txt
 create mode 100644 tools/perf/bench/futex-locks.c

-- 
1.8.3.1