The standard futex mechanism in the Linux kernel uses a global hash to store transient state. Collisions on that hash can lead to performance degradation and on real-time enabled kernels to unbound priority inversions.
This new attempt to solve the issue does not require user space changes and operates transparently. On the first futex operation of a process the kernel allocates a hash private to the process. All process private futexes are hashed in this hash. Process shared futexes still use the global hash. For RT applications and pathological use cases a new futex op is provided which allows the application to preallocate and thereby size the process private hash. The series comes with a new 'stupid' hash function based on the good old modulu prime. That function provides way better hash results than hash_ptr/hash_long() for small hash sizes. The last two patches add support to the perf futex-hash benchmark so test can be run on nodes and the preallocation sizing can be tested. The last patch contains a first update for the futex man page. Results from our testing in nice colored charts are available here: perf bench futex-hash run parallel on 4 nodes with global hash and various sized private hashes and various numbers of futexes per thread https://tglx.de/~tglx/f-ops.png perf bench futex-hash run parallel on 4 nodes with global hash and various sized private hashes using the new hash_mod() and various numbers of futexes per thread https://tglx.de/~tglx/f-ops.png perf bench futex-hash run parallel on 4 nodes with global hash and various sized private hashes using hash_long() and various numbers of futexes per thread https://tglx.de/~tglx/f-ops-hlong.png perf bench futex-hash run parallel on 2 nodes with global hash and various sized private hashes and various numbers of futexes per thread https://tglx.de/~tglx/f-ops-2.png perf bench futex-hash run parallel on 4 nodes with global hash and various sized private hashes using hash_mod(). 1 futex per thread and various thread numbers. https://tglx.de/~tglx/f-ops-mod-t.png perf bench futex-hash run parallel on 4 nodes with global hash and various sized private hashes using hash_long(). 1 futex per thread and various thread numbers. https://tglx.de/~tglx/f-ops-hlong-t.png Thanks, tglx ---- Documentation/sysctl/kernel.txt | 17 +++ b/include/linux/futex_types.h | 14 ++ b/lib/hashmod.c | 44 ++++++++ include/linux/futex.h | 39 +++++-- include/linux/hash.h | 28 +++++ include/linux/mm_types.h | 4 include/uapi/linux/futex.h | 1 init/Kconfig | 5 kernel/fork.c | 3 kernel/futex.c | 219 +++++++++++++++++++++++++++++++++++++++- kernel/sysctl.c | 21 +++ lib/Kconfig | 3 lib/Makefile | 1 tools/perf/bench/Build | 4 tools/perf/bench/futex-hash.c | 101 ++++++++++++++++-- tools/perf/bench/futex.h | 5 16 files changed, 486 insertions(+), 23 deletions(-)
