lkml.org 
[lkml]   [2016]   [Apr]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
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(-)

\
 
 \ /
  Last update: 2016-04-28 19:01    [W:0.149 / U:1.120 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site