Messages in this thread | ![/](/images/icornerl.gif) | | Date | Thu, 28 Apr 2016 16:42:06 -0000 | From | Thomas Gleixner <> | Subject | [patch 0/7] futex: Add support for process private hashing |
| |
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(-)
| ![\](/images/icornerr.gif) |