[patch 0/7] futex: Add support for process private hashing

[Thomas Gleixner]

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(-)