Sebastian Andrzej Siewior <[email protected]>, Linus Torvalds <[email protected]>, Darren Hart <[email protected]>, Peter Zijlstra <[email protected]>, Ingo Molnar <[email protected]>, Michael Kerrisk <[email protected]>, Davidlohr Bueso <[email protected]>, Chris Mason <[email protected]>, Carlos O'Donell <[email protected]>, Torvald Riegel <[email protected]>, Eric Dumazet <[email protected]>
Subsystems (7)
v2 cover Sebastian Andrzej Siewior <[email protected]>, Linus Torvalds <[email protected]>, Darren Hart <[email protected]>, Peter Zijlstra <[email protected]>, Ingo Molnar <[email protected]>, Michael Kerrisk <[email protected]>, Davidlohr Bueso <[email protected]>, Chris Mason <[email protected]>, Carlos O'Donell <[email protected]>, Torvald Riegel <[email protected]>, Eric Dumazet <[email protected]>
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 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.
The difference vs. V1 of this series is that it uses hash_long() now that the hash_64 implementation has been fixed in mainline. The performance numbers are more or less the same as with V1 [1].
Thanks,
tglx
[1] http://lkml.kernel.org/r/[email protected]
----
Documentation/sysctl/kernel.txt | 17 +++ b/include/linux/futex_types.h | 12 ++ include/linux/futex.h | 39 +++++-- include/linux/mm_types.h | 4 include/uapi/linux/futex.h | 1 init/Kconfig | 4 kernel/fork.c | 3 kernel/futex.c | 215 +++++++++++++++++++++++++++++++++++++++- kernel/sysctl.c | 21 +++ tools/perf/bench/Build | 4 tools/perf/bench/futex-hash.c | 101 ++++++++++++++++-- tools/perf/bench/futex.h | 5 12 files changed, 403 insertions(+), 23 deletions(-)
PATCH v2 1/7 futex: Add some more function commentry
Add some more comments and reformat existing ones to kernel doc style.
--- kernel/futex.c | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-)
kernel/futex.c +12 -3
@@ -373,8 +373,12 @@ static inline int hb_waiters_pending(str#endif } -/* -* We hash on the keys returned from get_futex_key (see below). +/** +* hash_futex - Return the hash bucket in the global hash +* @key: Pointer to the futex key for which the hash is calculated +* +* We hash on the keys returned from get_futex_key (see below) and return the +* corresponding hash bucket in the global hash. */ static struct futex_hash_bucket *hash_futex (union futex_key *key) {
@@ -384,7 +388,12 @@ static struct futex_hash_bucket *hash_fureturn &futex_queues[hash & (futex_hashsize -1 )]; } -/* + +/** +* match_futex - Check whether to futex keys are equal +* @key1: Pointer to key1 +* @key2: Pointer to key2 +* * Return 1 if two futex_keys are equal, 0 otherwise. */ static inline int match_futex (union futex_key *key1,union futex_key *key2)
PATCH v2 2/7 futex: Hash private futexes per process
In reply to Thomas GleixnerFrom: Sebastian Siewior <[email protected]>
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 especially on NUMA systems and on real-time enabled kernels even to priority inversions.
To mitigate that problem we provide per process private hashing. On the first futex operation in a process the kernel allocates a hash table. The hash table is accessible via the process mm_struct. On Numa systems the hash is allocated node local.
If the allocation fails then the global hash table is used as fallback, so there is no user space visible impact of this feature.
The hash size is a default value which can be tweaked by the sys admin. The sysctl interface is implemented in a follow up patch to make the review simpler. For applications which have special requirements for the private hash and to allow preallocation of the hash for RT applications, we'll provide a futex OP in a follow up patch.
Performance data acquired on a 4 socket (node) Intel machine with perf bench futex-hash:
Threads G 65536 P 4 P 8 P 16 P 32 P 64 P 128 P 256
1 8175006 8645465 8617469 8628686 8625223 8664491 8590934 8631582
2 8149869 8618385 8578185 8622267 8603253 8618787 8595073 8590591 4 7479482 5867840 7882991 7604838 7894380 7882850 7884911 7886278 8 7308822 2378057 5731051 5550479 7691198 7672814 7711939 7681549
16 7295893 677414 2670682 3453552 7158906 7688978 7677603 7690290
So with the proper hash size of the private hash is ~5% faster than the global hash.
With a full perf bench futex-hash run with one process (36 threads) per node and 1024 futexes per thread the following results are achieved:
G 65536 P 4 P 8 P 16 P 32 P 64 P 128 P 256 P 512 P 1024 P 2048 2673390 368952 682626 1223908 1845922 3003524 3538313 4118533 4286925 4289589 4274020
Ratio: 0,14 0,26 0,46 0,69 1,12 1,32 1,54 1,60 1,60 1,60
So with a private hash size of 256 buckets and above the performance is almost steady in this pathological test case and factor 1.6 better than the global hash. Even a 64 buckets hash is already 10% faster,
--- include/linux/futex.h | 38 ++++++++-- include/linux/futex_types.h | 12 +++ include/linux/mm_types.h | 4 + init/Kconfig | 4 + kernel/fork.c | 3 kernel/futex.c | 162 +++++++++++++++++++++++++++++++++++++++++++- 6 files changed, 212 insertions(+), 11 deletions(-) create mode 100644 include/linux/futex_types.h
include/linux/futex.h +30 -8
@@ -1,6 +1,7 @@#ifndef _LINUX_FUTEX_H#define _LINUX_FUTEX_H +#include <linux/futex_types.h> #include <uapi/linux/futex.h> struct inode ;
@@ -21,16 +22,19 @@ handle_futex_death(u32 __user *uaddr, st* * offset is aligned to a multiple of sizeof(u32) (== 4) by definition. * We use the two low order bits of offset to tell what is the kind of key : -* 00 : Private process futex (PTHREAD_PROCESS_PRIVATE) -* (no reference on an inode or mm) +* 00 : Private process futex (PTHREAD_PROCESS_PRIVATE) using process private +* hash (no reference on an inode or mm) * 01 : Shared futex (PTHREAD_PROCESS_SHARED) * mapped on a file (reference on the underlying inode) * 10 : Shared futex (PTHREAD_PROCESS_SHARED) * (but private mapping on an mm, and reference taken on it) +* 11 : Private process futex (PTHREAD_PROCESS_PRIVATE) using global hash +* (no reference on an inode or mm) */ -#define FUT_OFF_INODE 1/* We set bit 0 if key has a reference on inode */ -#define FUT_OFF_MMSHARED 2/* We set bit 1 if key has a reference on mm */ +#define FUT_OFF_INODE 0x01/* Key has a reference on inode */ +#define FUT_OFF_MMSHARED 0x02/* Key has a reference on mm */ +#define FUT_OFF_PRIVATE 0x03/* Key has no ref on inode/mm */ union futex_key { struct {
@@ -60,12 +64,30 @@ extern void exit_pi_state_list(struct ta#else extern int futex_cmpxchg_enabled;#endif +#else -static inline void exit_robust_list (struct task_struct *curr) -{ -} -static inline void exit_pi_state_list (struct task_struct *curr) +static inline void exit_robust_list (struct task_struct *curr) { } +static inline void exit_pi_state_list (struct task_struct *curr) { } +#endif + +#ifdef CONFIG_FUTEX_PRIVATE_HASH +/* Process private hash data for futexes */ + +extern unsigned int futex_default_hash_bits; +extern unsigned int futex_max_hash_bits; + +extern void futex_mm_hash_exit (struct mm_struct *mm); + +static inline void futex_mm_hash_init (struct mm_struct *mm) { +raw_spin_lock_init (&mm->futex_hash.lock); + mm->futex_hash.hash =NULL ; } + +#else + +static inline void futex_mm_hash_init (struct mm_struct *mm) { } +static inline void futex_mm_hash_exit (struct mm_struct *mm) { }#endif +#endif
include/linux/futex_types.h new file +12 -0
@@ -0,0 +1,12 @@ +#ifndef _LINUX_FUTEX_TYPES_H +#define _LINUX_FUTEX_TYPES_H + +struct futex_hash_bucket ; + +struct futex_hash { +struct raw_spinlock lock; +unsigned int hash_bits; +struct futex_hash_bucket *hash; +}; + +#endif
include/linux/mm_types.h +4 -0
@@ -11,6 +11,7 @@#include <linux/completion.h> #include <linux/cpumask.h> #include <linux/uprobes.h> +#include <linux/futex_types.h> #include <linux/page-flags-layout.h> #include <asm/page.h> #include <asm/mmu.h>
@@ -442,6 +443,9 @@ struct mm_struct {struct linux_binfmt *binfmt; +#ifdef CONFIG_FUTEX_PRIVATE_HASH +struct futex_hash futex_hash; +#endif cpumask_var_t cpu_vm_mask_var;/* Architecture-specific MM context */
init/Kconfig +4 -0
@@ -1498,6 +1498,10 @@ config FUTEX support for "fast userspace mutexes". The resulting kernel may not run glibc-based applications correctly. +config FUTEX_PRIVATE_HASH + bool + default FUTEX && SMP + config HAVE_FUTEX_CMPXCHG bool depends on FUTEX
kernel/fork.c +3 -0
@@ -617,6 +617,8 @@ static struct mm_struct *mm_init(structmm_init_owner (mm, p);mmu_notifier_mm_init (mm);clear_tlb_flush_pending (mm); +futex_mm_hash_init (mm); +#if defined(CONFIG_TRANSPARENT_HUGEPAGE ) && !USE_SPLIT_PMD_PTLOCKS mm->pmd_huge_pte =NULL ;#endif
@@ -713,6 +715,7 @@ void mmput(struct mm_struct *mm)khugepaged_exit (mm);/* must run before exit_mmap */ exit_mmap (mm);set_mm_exe_file (mm,NULL ); +futex_mm_hash_exit (mm);if (!list_empty (&mm->mmlist)) {spin_lock (&mmlist_lock);list_del (&mm->mmlist);
kernel/futex.c +159 -3
224 lines not on this page · raw message
PATCH v2 3/7 futex: Add op for hash preallocation
In reply to Thomas GleixnerFrom: Sebastian Siewior <[email protected]>
The per process hash is allocated on the fly at the first futex operation of a process. The size of the hash is determined by a system wide default setting controlled by the sys admin, This is suboptimal for RT applications and applications with pathological futex abuse,
- For RT applications its important to allocate the per process hash before the first futex operation to avoid the allocation on the first futex operation.
- For pathological applications which use gazillions of futexes its useful to allocate a hash greater than the default hash size.
Add a futex op which allows to preallocate the hash with the requested size. The size is limited by the systemwide maximum hash size, which can be set by the admin. The requested size is rounded up to the next order of 2.
The function can be called several times, but ony the first call results in a hash allocation of the requested size as there is no non-intrusive way to reallocate/rehash in a multithreaded application.
Note, that this call must be issued before the first futex operation in the process because that would automatically allocate the default sized hash.
The function returns the actual hash size or 0 if the global hash is used. The latter is the case on UP and in the rare case that the allocation failed and the global hash is used as a fallback.
--- include/uapi/linux/futex.h | 1 + kernel/futex.c | 41 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 42 insertions(+)
include/uapi/linux/futex.h +1 -0
@@ -20,6 +20,7 @@#define FUTEX_WAKE_BITSET 10#define FUTEX_WAIT_REQUEUE_PI 11#define FUTEX_CMP_REQUEUE_PI 12 +#define FUTEX_PREALLOC_HASH 13#define FUTEX_PRIVATE_FLAG 128#define FUTEX_CLOCK_REALTIME 256
kernel/futex.c +41 -0
53 lines not on this page · raw message
PATCH v2 4/7 futex: Add sysctl knobs for process private hash
In reply to Thomas GleixnerFrom: Sebastian Siewior <[email protected]>
To adjust the default hash size and the maximum hash size for process private futexes we add the following sysctls:
futex_private_default_hash_bits:
Adjusts the default hash size (in bits) which is used for automatic hash allocations on the first futex operation
futex_private_max_hash_bits:
Adjusts the maximum hash size (in bits). This limits the hash size which can be preallocated by applications with the FUTEX_PREALLOC_HASH op.
--- Documentation/sysctl/kernel.txt | 17 +++++++++++++++++ include/linux/futex.h | 1 + kernel/futex.c | 5 +++-- kernel/sysctl.c | 21 +++++++++++++++++++++ 4 files changed, 42 insertions(+), 2 deletions(-)
Documentation/sysctl/kernel.txt +17 -0
@@ -29,6 +29,8 @@ Currently, these files might (depending - core_pipe_limit - core_uses_pid - ctrl-alt-del +- futex_private_default_hash_bits +- futex_private_max_hash_bits - dmesg_restrict - domainname - hostname
@@ -265,6 +267,21 @@ to decide what to do with it. ============================================================== +futex_private_default_hash_bits: + +Adjusts the default hash size (in bits) which is used for +automatic hash allocations on the first futex operation + +============================================================== + +futex_private_max_hash_bits: + +Adjusts the maximum hash size (in bits). This limits the hash +size which can be preallocated by applications with the +FUTEX_PREALLOC_HASH op. + +============================================================== + dmesg_restrict: This toggle indicates whether unprivileged users are prevented
include/linux/futex.h +1 -0
@@ -75,6 +75,7 @@ static inline void exit_pi_state_list(stextern unsigned int futex_default_hash_bits;extern unsigned int futex_max_hash_bits; +extern unsigned int futex_sysmax_hash_bits;extern void futex_mm_hash_exit (struct mm_struct *mm);
kernel/futex.c +3 -2
@@ -297,8 +297,9 @@ struct futex_hash_bucket {#define FUTEX_DEF_HASH_BITS order_base_2(8UL)#define FUTEX_MAX_HASH_BITS order_base_2(256UL) -unsigned int futex_default_hash_bits =FUTEX_DEF_HASH_BITS ; -unsigned int futex_max_hash_bits =FUTEX_MAX_HASH_BITS ; +unsigned int futex_default_hash_bits =FUTEX_DEF_HASH_BITS ; +unsigned int futex_max_hash_bits =FUTEX_MAX_HASH_BITS ; +unsigned int __read_mostly futex_sysmax_hash_bits =FUTEX_MAX_HASH_BITS ;#else static const unsigned int futex_default_hash_bits =0 ;#endif
kernel/sysctl.c +21 -0
@@ -65,6 +65,7 @@#include <linux/sched/sysctl.h> #include <linux/kexec.h> #include <linux/bpf.h> +#include <linux/futex.h> #include <asm/uaccess.h> #include <asm/processor.h>
@@ -593,6 +594,26 @@ static struct ctl_table kern_table[] = { .mode = 0644, .proc_handler = proc_dointvec, }, +#ifdef CONFIG_FUTEX_PRIVATE_HASH + { + .procname = "futex_private_default_hash_bits", + .data = &futex_default_hash_bits, + .maxlen = sizeof(int), + .mode = 0644, + .proc_handler = proc_dointvec_minmax, + .extra1 = &two, + .extra2 = &futex_max_hash_bits, + }, + { + .procname = "futex_private_max_hash_bits", + .data = &futex_max_hash_bits, + .maxlen = sizeof(int), + .mode = 0644, + .proc_handler = proc_dointvec_minmax, + .extra1 = &futex_default_hash_bits, + .extra2 = &futex_sysmax_hash_bits, + }, +#endif #ifdef CONFIG_FUNCTION_TRACER { .procname = "ftrace_enabled",
PATCH v2 5/7 perf/bench/futex-hash: Support NUMA
In reply to Thomas GleixnerThis adds a new option to tell perf on which numa node the hash benchmark should run. If set then
- The test is bound to the node
- Memory is allocated on the local NUMA node
- The threads are bound to the cpus on the node
The NUMA node can be specified by the -n argument.
--- tools/perf/bench/Build | 4 ++ tools/perf/bench/futex-hash.c | 89 +++++++++++++++++++++++++++++++++++++------ 2 files changed, 82 insertions(+), 11 deletions(-)
tools/perf/bench/Build +4 -0
@@ -1,3 +1,7 @@ +ifdef CONFIG_NUMA +CFLAGS_futex-hash.o += -DCONFIG_NUMA=1 +endif + perf-y += sched-messaging.o perf-y += sched-pipe.o perf-y += mem-functions.o
tools/perf/bench/futex-hash.c +78 -11
156 lines not on this page · raw message
Signature · 1 line
2.1.4
PATCH v2 6/7 perf/bench/futex-hash: Support preallocate hash table
In reply to Thomas GleixnerInstead of using the default hash size on the first allocation it is possible to allocate a specific number of slots upfront.
--- tools/perf/bench/futex-hash.c | 16 ++++++++++++++-- tools/perf/bench/futex.h | 5 +++++ 2 files changed, 19 insertions(+), 2 deletions(-)
tools/perf/bench/futex-hash.c +14 -2
@@ -30,6 +30,7 @@ static unsigned int nsecs = 10;static unsigned int nfutexes =1024 ;static bool fshared = false, done = false, silent = false;static int futex_flag =0 ; +static unsigned int prealloc;static int numa_node =-1 ;struct timeval start, end, runtime;
@@ -51,6 +52,7 @@ static const struct option options[] = {OPT_UINTEGER ('f' ,"futexes" , &nfutexes,"Specify amount of futexes per threads" ),OPT_BOOLEAN ('s' ,"silent" , &silent,"Silent mode: do not display data/details" ),OPT_BOOLEAN ('S' ,"shared" , &fshared,"Use shared futexes instead of private ones" ), +OPT_UINTEGER ('p' ,"prealloc" ,&prealloc,"Specify number of preallocated hash slots" ), #ifdef CONFIG_NUMA OPT_INTEGER( 'n', "numa", &numa_node, "Specify the NUMA node"), #endif
@@ -138,6 +140,7 @@ int bench_futex_hash(int argc, const chaunsigned int i, ncpus;pthread_attr_t thread_attr;struct worker *worker =NULL ; +char *prealloc_str =NULL ;char *node_str =NULL ;unsigned int cpunum;
@@ -192,11 +195,20 @@ int bench_futex_hash(int argc, const chaif (!fshared) futex_flag =FUTEX_PRIVATE_FLAG ; -printf ("Run summary [PID %d]: %d threads%s, each operating on %d [%s] futexes for %d secs.\n\n" , +if (prealloc) { + ret =futex_preallocate (prealloc); +if (ret <0 ) +err (EXIT_FAILURE ,"futex_prealloate" ); + ret =asprintf (&prealloc_str," P %u %d" , prealloc, ret); +if (ret <0 ) +err (EXIT_FAILURE ,"futex_preallocate, asprintf" ); + } + +printf ("Run summary [PID %d]: %d threads%s, each operating on %d [%s%s] futexes for %d secs.\n\n" ,getpid (), nthreads, node_str ? :"" , nfutexes, fshared ?"shared" :"private" , - nsecs); + prealloc_str ? :"" , nsecs);init_stats (&throughput_stats);pthread_mutex_init (&thread_lock,NULL );
tools/perf/bench/futex.h +5 -0
@@ -101,4 +101,9 @@ static inline int pthread_attr_setaffini }#endif +static inline int futex_preallocate (u_int32_t hash_size) +{ +return futex (0 ,FUTEX_PREALLOC_HASH , hash_size,NULL ,NULL ,0 ,0 ); +} +#endif /* _FUTEX_H */
PATCH v2 7/7 futex.2: Document hash preallocation opcode
In reply to Thomas GleixnerAt least an attempt to document the futex attached mode extension.
--- man2/futex.2 | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+)
man2/futex.2 +40 -0
@@ -767,6 +767,40 @@ operations correspond to and .BR FUTEX_WAKE_BITSET operations where the bit masks are all ones. + +.\" +.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" +.\" +.TP +.BR FUTEX_PREALLOC_HASH " (since Linux ?.?.?)" +This operation preallocates the per process private hash with a hash size +provided by the +.IR val +argument. + +This operation tells the kernel to preallocate the per process private hash +with a given hash size. The size is rounded up to the next power of two and +limited internally in the kernel according to the sys control setting. + +The per process private hash is allocated once and cannot be resized. The +allocation either happens by this op code or automatically when the first real +futex operation takes place. + +If the hash is allocated then subsequent calls with this opcode return the +currently active hash size. + +If the returned size value is 0 then the global hash is used instead of the +process private hash. This can happen on UP machines where the private hashing +is disabled and in case of memory allocation failure. + +The +.IR uaddr , +.IR timeout , +.IR uaddr2 +and +.I val3 +arguments are ignored. + .\" .\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" .\"
@@ -1334,6 +1368,12 @@ the futex word at Returns 0 if the caller was successfully requeued to the futex for the futex word at .IR uaddr2 . +.TP +.B FUTEX_PREALLOC_HASH +Returns the size of the allocated hash, i.e. the number of hash slots. If the +size value is 0 then the global hash is used instead of the process private +hash. This can happen on UP machines where the private hashing is disabled and +in case of memory allocation failure. .\" .\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" .\"