From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753360AbcD1Qo4 (ORCPT ); Thu, 28 Apr 2016 12:44:56 -0400 Received: from www.linutronix.de ([62.245.132.108]:58912 "EHLO Galois.linutronix.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753064AbcD1Qnp (ORCPT ); Thu, 28 Apr 2016 12:43:45 -0400 Message-Id: <20160428161742.363543816@linutronix.de> User-Agent: quilt/0.63-1 Date: Thu, 28 Apr 2016 16:42:06 -0000 From: Thomas Gleixner To: LKML Cc: Peter Zijlstra , Ingo Molnar , Linus Torvalds , Andrew Morton , Sebastian Andrzej Siewior , Darren Hart , Michael Kerrisk , Davidlohr Bueso , Chris Mason , "Carlos O'Donell" , Torvald Riegel , Eric Dumazet Subject: [patch 0/7] futex: Add support for process private hashing X-Linutronix-Spam-Score: -1.0 X-Linutronix-Spam-Level: - X-Linutronix-Spam-Status: No , -1.0 points, 5.0 required, ALL_TRUSTED=-1,SHORTCIRCUIT=-0.0001 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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(-)