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

From: Waiman Long
Date: Thu Dec 29 2016 - 11:19:08 EST

- 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.

- 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.

- 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

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

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