v5->v6:
- Futex code changes:
1) Allow userspace locking of exclusive locks instead of just
kernel locking (patch 14). This is controlled by a flag passed
to the futex(2) syscall. This enables better throughput.
2) Add a reader-preferring mode to shared locking.
- Futex microbenchmark improvements:
1) Using gcc __atomic builtins instead of the older __sync builtins.
This allowed more optimized code for non-x86 architectures.
2) Add timeout support
3) Count # of times lock/unlock slowpath are invoked instead of
the futex(2) syscalls.
- Include benchmark results on a Power8 system.
- The tp-futex.txt document was updated accordingly.
- Fix a couple of bugs in the v5 patch set.
v4->v5:
- Fix 0-day kernel build test compilation warnings.
- Extract out non-TP futexes futex-mutex and futex-rwlock
microbenchmarks as separate patches, as suggested by Arnaldo.
- Rebased to the latest tip tree & use running_clock() instead
of sched_clock().
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-2 implements userspace exclusive lock and read/write lock
benchmark in perf bench using futexes.
Patches 3-8 are preparatory patches that pave the way to implement
the TP futexes.
Patch 9 implements the basic TP futex that can support userspace
mutexes.
Patch 10 adds robust handling to TP futex to handle the death of TP
futex exclusive lock owners.
Patch 11 adds a lock hand-off mechanism that can prevent lock starvation
to happen while introducing minimal runtime overhead.
Patch 12 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 13 enables userspace applications to supply a timeout value to
abort the lock acquisition attempt after the specified time period
has passed.
Patch 14 enables users to choose to do userspace locking of exclusive
locks by returning the EAGAIN error code instead of doing that in
the kernel.
Patch 15 adds a new document tp-futex.txt in the Documentation
directory to describe the new TP futexes.
Patch 16 extends the TP futexes to support userspace rwlocks.
Patch 17 enables more reader lock stealing of TP futexes in the kernel.
Patch 18 groups readers together as a spin group to enhance reader
throughput.
Patch 19 updates the tp-futex.txt file to add information about
rwlock support.
Patch 20 extends the perf bench futex locking benchmark to include
variants using the new TP futexes.
Patch 21 updates the wake_up_q() function to returns the number
woken tasks.
Patch 22 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 x86-64 system are as follows:
WW futex TP futex Glibc
-------- -------- -----
mutex 136,291 158,897 110,186
rwlock 86,004 138,280 41,267
Patches 15 and 19 contain more detailed information about the
performance characteristics of the TP futexes when implementing
userspace mutex and rwlock respectively when compared with other
possible ways of doing so via the wait-wake futexes.
Waiman Long (22):
perf bench: New microbenchmark for userspace mutex performance
perf bench: New microbenchmark for userspace rwlock performance
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: Optionally return EAGAIN for userspace locking
TP-futex, doc: Add TP futexes documentation
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: Extend mutex/rwlock futex suite to test TP futexes
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 | 310 ++++++
include/linux/sched.h | 4 +-
include/linux/sched/wake_q.h | 2 +-
include/uapi/linux/futex.h | 32 +-
kernel/futex.c | 1436 ++++++++++++++++++++++++--
kernel/sched/core.c | 6 +-
tools/perf/Documentation/perf-bench.txt | 5 +
tools/perf/bench/Build | 1 +
tools/perf/bench/bench.h | 2 +
tools/perf/bench/futex-locks.c | 1680 +++++++++++++++++++++++++++++++
tools/perf/bench/futex.h | 45 +
tools/perf/builtin-bench.c | 11 +
tools/perf/check-headers.sh | 4 +
14 files changed, 3428 insertions(+), 112 deletions(-)
create mode 100644 Documentation/tp-futex.txt
create mode 100644 tools/perf/bench/futex-locks.c
--
1.8.3.1
--
To unsubscribe from this list: send the line "unsubscribe linux-doc" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
