futex performance regression from "futex: Allow automatic allocation of process wide futex hash"
Hi everyone,
While testing Peter's latest scheduler patches against current Linus git, I found a pretty big performance regression with schbench:
https://github.com/masoncl/schbench
The command line I was using:
schbench -L -m 4 -M auto -t 256 -n 0 -r 60 -s 0
Bisecting the problem I landed on commit:
commit 7c4f75a21f636486d2969d9b6680403ea8483539 (HEAD -> update)
Author: Sebastian Andrzej Siewior <[email protected]> Date: Wed Apr 16 18:29:13 2025 +0200
futex: Allow automatic allocation of process wide futex hash
Allocate a private futex hash with 16 slots if a task forks its first thread.
Link:
https://lore.kernel.org/r/[email protected]
schbench uses one futex per thread, and the command line ends up allocating 1024 threads, so the default bucket size used by this commit is just too small. Using 2048 buckets makes the problem go away.
On my big turin system, this commit slows down RPS by 36%. But even a VM on a skylake machine sees a 29% difference.
schbench is a microbenchmark, so grain of salt on all of this, but I think our defaults are probably too low.
-chris
Quoted 1 line · Chris Mason
Hi everyone,
Hi,
Quoted 9 lines
While testing Peter's latest scheduler patches against current Linus git, I found a pretty big performance regression with schbench:
https://github.com/masoncl/schbench
The command line I was using:
schbench -L -m 4 -M auto -t 256 -n 0 -r 60 -s 0
…
Quoted 3 lines
schbench uses one futex per thread, and the command line ends up allocating 1024 threads, so the default bucket size used by this commit is just too small. Using 2048 buckets makes the problem go away.
There is also this pthread_mutex_t but yeah
Quoted 5 lines
On my big turin system, this commit slows down RPS by 36%. But even a VM on a skylake machine sees a 29% difference.
schbench is a microbenchmark, so grain of salt on all of this, but I think our defaults are probably too low.
we could
kernel/futex/core.c +1 -1
@@ -1687,7 +1687,7 @@ int futex_hash_allocate_default(void)scoped_guard (rcu) { threads = min_t(unsigned int,get_nr_threads (current), -num_online_cpus ()); +num_online_cpus () *2 ); fph =rcu_dereference (current->mm->futex_phash);if (fph) {
which would increase it to 2048 as Chris asks for. Then there the possibility of
kernel/futex/core.c +9 -3
@@ -1680,6 +1680,8 @@ int futex_hash_allocate_default(void) {unsigned int threads, buckets, current_buckets =0 ;struct futex_private_hash *fph; +bool current_immutable = false; +unsigned int flags =0 ;if (!current->mm)return 0 ;
@@ -1695,6 +1697,7 @@ int futex_hash_allocate_default(void)return 0 ; current_buckets = fph->hash_mask +1 ; + current_immutable = fph->immutable; } }
@@ -1705,10 +1708,13 @@ int futex_hash_allocate_default(void) buckets =roundup_pow_of_two (4 * threads); buckets =clamp (buckets,16 , futex_hashmask +1 ); -if (current_buckets >= buckets) -return 0 ; +if (current_buckets >= buckets) { +if (current_immutable) +return 0 ; + flags =FH_IMMUTABLE ; + } -return futex_hash_allocate (buckets,0 ); +return futex_hash_allocate (buckets, flags); }static int futex_hash_get_slots (void )
to make hash immutable once the upper limit has been reached. There will be no more auto-resize. One could argue that if the user did not touch it, he might not do it at all.
This would avoid the reference accounting. Some testing:
256 cores, 2xNUMA:
| average rps: 1 701 947.02 Futex HBs: 0 immutable: 1 | average rps: 785 446.07 Futex HBs: 1024 immutable: 0 | average rps: 1 586 755.62 Futex HBs: 1024 immutable: 1 | average rps: 736 769.77 Futex HBs: 2048 immutable: 0 | average rps: 1 555 182.52 Futex HBs: 2048 immutable: 1
144 cores, 4xNUMA:
| average rps: 2 691 912.55 Futex HBs: 0 immutable: 1 | average rps: 1 306 443.68 Futex HBs: 1024 immutable: 0 | average rps: 2 471 382.28 Futex HBs: 1024 immutable: 1 | average rps: 1 269 503.90 Futex HBs: 2048 immutable: 0 | average rps: 2 656 228.67 Futex HBs: 2048 immutable: 1
tested with this on top:
schbench.c +41 -1
84 lines not on this page · raw message
Comments?
Quoted 1 line
-chris
Sebastian
Quoted 11 lines · Sebastian Andrzej Siewior
Quoted 1 line · Chris Mason
Hi everyone,
Hi,
Quoted 7 lines
While testing Peter's latest scheduler patches against current Linus git, I found a pretty big performance regression with schbench:
https://github.com/masoncl/schbench
The command line I was using:
Quoted 8 lines
Quoted 2 lines
schbench -L -m 4 -M auto -t 256 -n 0 -r 60 -s 0
…
Quoted 3 lines
schbench uses one futex per thread, and the command line ends up allocating 1024 threads, so the default bucket size used by this commit is just too small. Using 2048 buckets makes the problem go away.
There is also this
pthread_mutex_tbut yeah
Yeah, but -L disables the pthread nonsense.
Quoted 23 lines
Quoted 6 lines
On my big turin system, this commit slows down RPS by 36%. But even a VM on a skylake machine sees a 29% difference.
schbench is a microbenchmark, so grain of salt on all of this, but I think our defaults are probably too low.
we could
kernel/futex/core.c +1
-1@@ -1687,7 +1687,7 @@ int futex_hash_allocate_default(void)scoped_guard (rcu) { threads = min_t(unsigned int,get_nr_threads (current), -num_online_cpus ()); +num_online_cpus () *2 ); fph =rcu_dereference (current->mm->futex_phash);if (fph) {
Quoted 1 line
which would increase it to 2048 as Chris asks for.
I haven't followed these changes, so asking some extra questions. This would bump to num_online_cpus() * 2, which probably isn't 2048 right?
We've got large systems that are basically dedicated to single workloads, and those will probably miss the larger global hash table, regressing like schbench did. Then we have large systems spread over multiple big workloads that will love the private tables.
In either case, I think growing the hash table as a multiple of thread count instead of cpu count will probably better reflect the crazy things multi-threaded applications do? At any rate, I don't think we want applications to need prctl to get back to the performance they had on older kernels.
For people that want to avoid that memory overhead, I'm assuming they want the CONFIG_FUTEX_PRIVATE_HASH off, so the Kconfig help text should make that more clear.
kernel/futex/core.c> index
Quoted 3 lines
Then there the possibility of
kernel/futex/core.c> index renamed from kernel/futex/core.c +0
-0
abbd97c2fcba8..a19a96cc09c9e 100644
Quoted 40 lines
kernel/futex/core.c +9
-3@@ -1680,6 +1680,8 @@ int futex_hash_allocate_default(void) {unsigned int threads, buckets, current_buckets =0 ;struct futex_private_hash *fph; +bool current_immutable = false; +unsigned int flags =0 ;if (!current->mm)return 0 ;@@ -1695,6 +1697,7 @@ int futex_hash_allocate_default(void)return 0 ; current_buckets = fph->hash_mask +1 ; + current_immutable = fph->immutable; } }@@ -1705,10 +1708,13 @@ int futex_hash_allocate_default(void) buckets =roundup_pow_of_two (4 * threads); buckets =clamp (buckets,16 , futex_hashmask +1 ); -if (current_buckets >= buckets) -return 0 ; +if (current_buckets >= buckets) { +if (current_immutable) +return 0 ; + flags =FH_IMMUTABLE ; + } -return futex_hash_allocate (buckets,0 ); +return futex_hash_allocate (buckets, flags); } > static int futex_hash_get_slots(void)to make hash immutable once the upper limit has been reached. There will be no more auto-resize. One could argue that if the user did not touch it, he might not do it at all.
Quoted 6 lines
This would avoid the reference accounting. Some testing:
256 cores, 2xNUMA:
| average rps: 1 701 947.02 Futex HBs: 0 immutable: 1 | average rps: 785 446.07 Futex HBs: 1024 immutable: 0 | average rps: 1 586 755.62 Futex HBs: 1024 immutable: 1> | average
rps: 736 769.77 Futex HBs: 2048 immutable: 0
Quoted 1 line
| average rps: 1 555 182.52 Futex HBs: 2048 immutable: 1
How long are these runs? That's a huge benefit from being immutable (1.5M vs 736K?) but the hash table churn should be confined to early in the schbench run right?
Quoted 9 lines
144 cores, 4xNUMA:
| average rps: 2 691 912.55 Futex HBs: 0 immutable: 1 | average rps: 1 306 443.68 Futex HBs: 1024 immutable: 0 | average rps: 2 471 382.28 Futex HBs: 1024 immutable: 1 | average rps: 1 269 503.90 Futex HBs: 2048 immutable: 0 | average rps: 2 656 228.67 Futex HBs: 2048 immutable: 1tested with this on top:
This schbench hunk is just testing the performance impact of different bucket sizes, but hopefully we don't need it long term unless we want to play with even bigger hash tables?
-chris
Quoted 103 lines
schbench.c +41
-1@@ -19,6 +19,8 @@#include <unistd.h> #include <errno.h> #include <getopt.h> +#include <linux/prctl.h> +#include <sys/prctl.h> #include <sys/time.h> #include <time.h> #include <string.h> @@ -42,6 +44,9 @@#define USEC_PER_SEC (1000000) +static int futex_size =-1 ; +static int futex_flags; +/* -m number of message threads */ static int message_threads =1 ;/* -t number of workers per message thread */ @@ -127,7 +132,7 @@ enum { HELP_LONG_OPT = 1, }; -char *option_string ="p:m:M:W:t:Cr:R:w:i:z:A:n:F:Lj:s:J:" ; +char *option_string ="p:m:M:W:t:Cr:R:w:i:z:A:n:F:Lj:s:J:H:I" ;static struct option long_options[] = { {"pipe" , required_argument,0 ,'p' }, {"message-threads" , required_argument,0 ,'m' },@@ -176,6 +181,29 @@ static void print_usage(void)exit (1 ); } +#ifndef PR_FUTEX_HASH +#define PR_FUTEX_HASH 78 +# define PR_FUTEX_HASH_SET_SLOTS 1 +# define FH_FLAG_IMMUTABLE (1ULL << 0) +# define PR_FUTEX_HASH_GET_SLOTS 2 +# define PR_FUTEX_HASH_GET_IMMUTABLE 3 +#endif + +static int futex_hash_slots_set (unsigned int slots,int flags) +{ +return prctl (PR_FUTEX_HASH ,PR_FUTEX_HASH_SET_SLOTS , slots, flags); +} + +static int futex_hash_slots_get (void ) +{ +return prctl (PR_FUTEX_HASH ,PR_FUTEX_HASH_GET_SLOTS ); +} + +static int futex_hash_immutable_get (void ) +{ +return prctl (PR_FUTEX_HASH ,PR_FUTEX_HASH_GET_IMMUTABLE ); +} +/* * returns 0 if we fail to parse and 1 if we succeed */ @@ -347,6 +375,13 @@ static void parse_options(int ac, char **av)exit (1 ); }break ; +case 'H' : + futex_size =atoi (optarg); +break ; +case 'I' : + futex_flags =FH_FLAG_IMMUTABLE ; +break ; +case '?' :case HELP_LONG_OPT :print_usage ();@@ -1811,6 +1846,9 @@ int main(int ac, char **av) } } +if (futex_size >=0 ) +futex_hash_slots_set (futex_size, futex_flags); + requests_per_sec /= message_threads; loops_per_sec =0 ; stopping =0 ;@@ -1920,6 +1958,8 @@ int main(int ac, char **av) }free (message_threads_mem); +fprintf (stderr,"Futex HBs: %d immutable: %d\n" ,futex_hash_slots_get (), +futex_hash_immutable_get ());return 0 ; }Comments?
Quoted 1 line
-chris
Sebastian
Quoted 9 lines · Chris Mason
Quoted 9 lines
kernel/futex/core.c +1
-1@@ -1687,7 +1687,7 @@ int futex_hash_allocate_default(void)scoped_guard (rcu) { threads = min_t(unsigned int,get_nr_threads (current), -num_online_cpus ()); +num_online_cpus () *2 );
Quoted 7 lines
Quoted 4 lines
kernel/futex/core.c +0
-0fph =rcu_dereference (current->mm->futex_phash);if (fph) {which would increase it to 2048 as Chris asks for.
I haven't followed these changes, so asking some extra questions. This would bump to
num_online_cpus()* 2, which probably isn't 2048 right?
Assuming you have 256 CPUs and -m 4 -t 256 creates 4 * 256 = 1024 then threads = 512 gets computed (= min(1024, 256 * 2)). Later we do 512 * 4 (roundup_pow_of_two(4 * threads)). This makes 2048 hash buckets.
Quoted 10 lines
We've got large systems that are basically dedicated to single workloads, and those will probably miss the larger global hash table, regressing like schbench did. Then we have large systems spread over multiple big workloads that will love the private tables.
In either case, I think growing the hash table as a multiple of thread count instead of cpu count will probably better reflect the crazy things multi-threaded applications do? At any rate, I don't think we want applications to need prctl to get back to the performance they had on older kernels.
This is only an issue if all you CPUs spend their time in the kernel using the hash buckets at the same time.
This was the case in every benchmark I've seen so far. Your thing might be closer to an actual workload.
Quoted 5 lines
For people that want to avoid that memory overhead, I'm assuming they want the
CONFIG_FUTEX_PRIVATE_HASHoff, so theKconfighelp text should make that more clear.Quoted 1 line
Then there the possibility of
…
Quoted 11 lines
Quoted 4 lines
256 cores, 2xNUMA:
| average rps: 1 701 947.02 Futex HBs: 0 immutable: 1 | average rps: 785 446.07 Futex HBs: 1024 immutable: 0 | average rps: 1 586 755.62 Futex HBs: 1024 immutable: 1> | averagerps: 736 769.77 Futex HBs: 2048 immutable: 0
Quoted 1 line
| average rps: 1 555 182.52 Futex HBs: 2048 immutable: 1
How long are these runs? That's a huge benefit from being immutable (1.5M vs 736K?) but the hash table churn should be confined to early in the schbench run right?
I think 30 secs or so. I used your command line. The 256 core box showed a higher improvement than the 144 one. I attached a patch against schbench in the previous mail, I did then
./schbench -L -m 4 -M auto -t 256 -n 0 -r 60 -s 0 -H 1024 -I
…
Quoted 3 lines
This schbench hunk is just testing the performance impact of different bucket sizes, but hopefully we don't need it long term unless we want to play with even bigger hash tables?
If you do "-H 0" then you should get the "old" behaviour. However the hash bucket are spread now over the NUMA nodes:
| dmesg |grep -i futex | [ 0.501736] futex hash table entries: 32768 (2097152 bytes on 2 NUMA nodes, total 4096 KiB, linear).
Now there are 32768 hash buckets on both NUMA nodes. Depending on the hash it computes, it uses the data structures on NUMA node 1 or 2. The old code allocated 65536 hash buckets via vmalloc().
The bigger hash table isn't always the answer. Yes, you could play around figure out what works best for you. The problem is that the hash is based on the mm and the (user) memory address. So on each run you will get a different hash and therefore different collisions. If you end up having many hash collisions and then block on the same lock then yes, larger hash table will be the cure. If you have many threads doing the futex syscall simultaneously then making the hash immutable avoids two atomic ops on the same memory address. This would be my favorite.
Now that I think about it, it might be possible to move the atomic ops the hash bucket itself. Then it wouldn't bounce the cache line so much. Making the hash immutable is simpler.
Quoted 1 line
-chris
Sebastian
Quoted 13 lines · Sebastian Andrzej Siewior
Quoted 12 lines · Chris Mason
Quoted 12 lines
kernel/futex/core.c +1
-1@@ -1687,7 +1687,7 @@ int futex_hash_allocate_default(void)scoped_guard (rcu) { threads = min_t(unsigned int,get_nr_threads (current), -num_online_cpus ()); +num_online_cpus () *2 ); fph =rcu_dereference (current->mm->futex_phash);if (fph) {
Quoted 9 lines
Quoted 4 lines
Quoted 1 line
which would increase it to 2048 as Chris asks for.
I haven't followed these changes, so asking some extra questions. This would bump to
num_online_cpus()* 2, which probably isn't 2048 right?Assuming you have 256 CPUs and -m 4 -t 256 creates 4 * 256 = 1024 then threads = 512 gets computed (=
min(1024, 256 * 2)). Later we do 512 * 4 (roundup_pow_of_two(4 * threads)). This makes 2048 hash buckets.
Ah right, I missed the x4.
Quoted 11 lines
Quoted 10 lines
We've got large systems that are basically dedicated to single workloads, and those will probably miss the larger global hash table, regressing like schbench did. Then we have large systems spread over multiple big workloads that will love the private tables.
In either case, I think growing the hash table as a multiple of thread count instead of cpu count will probably better reflect the crazy things multi-threaded applications do? At any rate, I don't think we want applications to need prctl to get back to the performance they had on older kernels.
Quoted 5 lines
This is only an issue if all you CPUs spend their time in the kernel using the hash buckets at the same time.
This was the case in every benchmark I've seen so far. Your thing might be closer to an actual workload.
I didn't spend a ton of time looking at the perf profiles of the slower kernel, was the bottleneck in the hash chain length or in contention for the buckets?
Quoted 11 lines
Quoted 5 lines
For people that want to avoid that memory overhead, I'm assuming they want the
CONFIG_FUTEX_PRIVATE_HASHoff, so theKconfighelp text should make that more clear.Quoted 1 line
Then there the possibility of
…
Quoted 5 lines
Quoted 4 lines
256 cores, 2xNUMA:
| average rps: 1 701 947.02 Futex HBs: 0 immutable: 1 | average rps: 785 446.07 Futex HBs: 1024 immutable: 0 | average rps: 1 586 755.62 Futex HBs: 1024 immutable: 1> | averagerps: 736 769.77 Futex HBs: 2048 immutable: 0
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
| average rps: 1 555 182.52 Futex HBs: 2048 immutable: 1
How long are these runs? That's a huge benefit from being immutable (1.5M vs 736K?) but the hash table churn should be confined to early in the schbench run right?
I think 30 secs or so. I used your command line.
Ah ok, my command line is 60 seconds. It feels like something is strange for the immutable flag to make it that much faster? schbench starts all the threads up front, so it should hit steady state pretty quickly. More on NUMA below, but I'll benchmark with the immutable flag on the turin box in the morning to see if it is the extra atomics.
Quoted 13 lines
The 256 core box showed
a higher improvement than the 144 one. I attached a patch against schbench in the previous mail, I did then./schbench -L -m 4 -M auto -t 256 -n 0 -r 60 -s 0 -H 1024 -I…
Quoted 3 lines
This schbench hunk is just testing the performance impact of different bucket sizes, but hopefully we don't need it long term unless we want to play with even bigger hash tables?
If you do "-H 0" then you should get the "old" behaviour. However the hash bucket are spread now over the NUMA nodes:
Quoted 6 lines
| dmesg |grep -i futex | [ 0.501736] futex hash table entries: 32768 (2097152 bytes on 2 NUMA nodes, total 4096 KiB, linear).Now there are 32768 hash buckets on both NUMA nodes. Depending on the hash it computes, it uses the data structures on NUMA node 1 or 2. The old code allocated 65536 hash buckets via
vmalloc().
So I wanted to mention this earlier and forgot, but schbench obviously isn't numa aware at all. This combination of command line options basically just has the 4 message threads waking up the 256 worker threads (per message thread) after scribbling a timestamp into shared memory. From a schbench pov at least, we'll get much more stable numbers by sticking to a single socket. <makes numa placement hand gestures>
Quoted 11 lines
The bigger hash table isn't always the answer. Yes, you could play around figure out what works best for you. The problem is that the hash is based on the mm and the (user) memory address. So on each run you will get a different hash and therefore different collisions. If you end up having many hash collisions and then block on the same lock then yes, larger hash table will be the cure. If you have many threads doing the futex syscall simultaneously then making the hash immutable avoids two atomic ops on the same memory address. This would be my favorite.
Quoted 3 lines
Now that I think about it, it might be possible to move the atomic ops the hash bucket itself. Then it wouldn't bounce the cache line so much. Making the hash immutable is simpler.
Going back to your diff, if we have a process growing the total number of threads, can we set FH_IMMUTABLE too early? As the number of threads increases, eventually we'll pick the 2x num_cpus, but that'll take a while?
I do see what you mean about immutable being simpler though, I'll get some numbers on those atomics.
-chris
Quoted 17 lines · Chris Mason
Quoted 11 lines
Quoted 10 lines
We've got large systems that are basically dedicated to single workloads, and those will probably miss the larger global hash table, regressing like schbench did. Then we have large systems spread over multiple big workloads that will love the private tables.
In either case, I think growing the hash table as a multiple of thread count instead of cpu count will probably better reflect the crazy things multi-threaded applications do? At any rate, I don't think we want applications to need prctl to get back to the performance they had on older kernels.
Quoted 5 lines
This is only an issue if all you CPUs spend their time in the kernel using the hash buckets at the same time.
This was the case in every benchmark I've seen so far. Your thing might be closer to an actual workload.
Quoted 3 lines
I didn't spend a ton of time looking at the perf profiles of the slower kernel, was the bottleneck in the hash chain length or in contention for the buckets?
Every futex operation does a rcuref_get() (which is an atomic inc) on the private hash. This is before anything else happens. If you have two threads, on two CPUs, which simultaneously do a futex() operation then both do this rcuref_get(). That atomic inc ensures that the cacheline bounces from one CPU to the other. On the exit of the syscall there is a matching rcuref_put().
Quoted 18 lines
Quoted 18 lines
Quoted 5 lines
For people that want to avoid that memory overhead, I'm assuming they want the
CONFIG_FUTEX_PRIVATE_HASHoff, so theKconfighelp text should make that more clear.Quoted 1 line
Then there the possibility of
…
Quoted 11 lines
Quoted 4 lines
256 cores, 2xNUMA:
| average rps: 1 701 947.02 Futex HBs: 0 immutable: 1 | average rps: 785 446.07 Futex HBs: 1024 immutable: 0 | average rps: 1 586 755.62 Futex HBs: 1024 immutable: 1> | averagerps: 736 769.77 Futex HBs: 2048 immutable: 0
Quoted 1 line
| average rps: 1 555 182.52 Futex HBs: 2048 immutable: 1
How long are these runs? That's a huge benefit from being immutable (1.5M vs 736K?) but the hash table churn should be confined to early in the schbench run right?
Quoted 7 lines
Quoted 1 line
I think 30 secs or so. I used your command line.
Ah ok, my command line is 60 seconds. It feels like something is strange for the immutable flag to make it that much faster? schbench starts all the threads up front, so it should hit steady state pretty quickly. More on NUMA below, but I'll benchmark with the immutable flag on the turin box in the morning to see if it is the extra atomics.
That immutable flag makes this rcuref_get()/ put() go away. The price is that you can't change the size of the private hash anymore. So if your workload works best with a hash size of X and you don't intend to change it during the runtime of the program, set the immutable flag.
Quoted 20 lines
Quoted 13 lines
The 256 core box showed
a higher improvement than the 144 one. I attached a patch against schbench in the previous mail, I did then./schbench -L -m 4 -M auto -t 256 -n 0 -r 60 -s 0 -H 1024 -I…
Quoted 3 lines
This schbench hunk is just testing the performance impact of different bucket sizes, but hopefully we don't need it long term unless we want to play with even bigger hash tables?
If you do "-H 0" then you should get the "old" behaviour. However the hash bucket are spread now over the NUMA nodes:
Quoted 6 lines
| dmesg |grep -i futex | [ 0.501736] futex hash table entries: 32768 (2097152 bytes on 2 NUMA nodes, total 4096 KiB, linear).Now there are 32768 hash buckets on both NUMA nodes. Depending on the hash it computes, it uses the data structures on NUMA node 1 or 2. The old code allocated 65536 hash buckets via
vmalloc().
Quoted 7 lines
So I wanted to mention this earlier and forgot, but schbench obviously isn't numa aware at all. This combination of command line options basically just has the 4 message threads waking up the 256 worker threads (per message thread) after scribbling a timestamp into shared memory. From a schbench pov at least, we'll get much more stable numbers by sticking to a single socket. <makes numa placement hand gestures>
Earlier the global hash was somehow spread via vmalloc(). Now it is spread slightly different. If you request the private hash, then it is allocated on the current node. Unless you move from one node the other, this should be good.
Quoted 10 lines
Quoted 10 lines
The bigger hash table isn't always the answer. Yes, you could play around figure out what works best for you. The problem is that the hash is based on the mm and the (user) memory address. So on each run you will get a different hash and therefore different collisions. If you end up having many hash collisions and then block on the same lock then yes, larger hash table will be the cure. If you have many threads doing the futex syscall simultaneously then making the hash immutable avoids two atomic ops on the same memory address. This would be my favorite.
Quoted 7 lines
Quoted 3 lines
Now that I think about it, it might be possible to move the atomic ops the hash bucket itself. Then it wouldn't bounce the cache line so much. Making the hash immutable is simpler.
Going back to your diff, if we have a process growing the total number of threads, can we set
FH_IMMUTABLEtoo early? As the number of threads increases, eventually we'll pick the 2xnum_cpus, but that'll take a while?
If you refer to the schbench diff, then set it early. Once the prctl() to set the size of the private hash, there will be no resize by the kernel.
If you refer to the kernel diff where set the FH_IMMUTABLE flag, then it is set once the upper limit is reached (that was the plan in case I did the logic wrong). Which means at that point it won't increase any further because of the CPU limit. The only way how you can reach it too early is if you offline CPUs.
Quoted 2 lines
I do see what you mean about immutable being simpler though, I'll get some numbers on those atomics.
I have another idea to add a refcount to the hb slot itself. I hope that it won't be that expensive if a atomic inc/dec occurs on different memory locations. But then maybe freeze it if the upper limit is reached. But that might help if we don't reach the upper limit.
Quoted 1 line
-chris
Sebastian
Quoted 55 lines · Sebastian Andrzej Siewior
Quoted 17 lines · Chris Mason
Quoted 11 lines
Quoted 10 lines
We've got large systems that are basically dedicated to single workloads, and those will probably miss the larger global hash table, regressing like schbench did. Then we have large systems spread over multiple big workloads that will love the private tables.
In either case, I think growing the hash table as a multiple of thread count instead of cpu count will probably better reflect the crazy things multi-threaded applications do? At any rate, I don't think we want applications to need prctl to get back to the performance they had on older kernels.
Quoted 5 lines
This is only an issue if all you CPUs spend their time in the kernel using the hash buckets at the same time.
This was the case in every benchmark I've seen so far. Your thing might be closer to an actual workload.Quoted 3 lines
I didn't spend a ton of time looking at the perf profiles of the slower kernel, was the bottleneck in the hash chain length or in contention for the buckets?
Every futex operation does a
rcuref_get()(which is an atomic inc) on the private hash. This is before anything else happens. If you have two threads, on two CPUs, which simultaneously do afutex()operation then both do thisrcuref_get(). That atomic inc ensures that the cacheline bounces from one CPU to the other. On the exit of the syscall there is a matchingrcuref_put().Quoted 18 lines
Quoted 18 lines
Quoted 5 lines
For people that want to avoid that memory overhead, I'm assuming they want the
CONFIG_FUTEX_PRIVATE_HASHoff, so theKconfighelp text should make that more clear.Quoted 1 line
Then there the possibility of
…
Quoted 11 lines
Quoted 4 lines
256 cores, 2xNUMA:
| average rps: 1 701 947.02 Futex HBs: 0 immutable: 1 | average rps: 785 446.07 Futex HBs: 1024 immutable: 0 | average rps: 1 586 755.62 Futex HBs: 1024 immutable: 1> | averagerps: 736 769.77 Futex HBs: 2048 immutable: 0
Quoted 1 line
| average rps: 1 555 182.52 Futex HBs: 2048 immutable: 1
How long are these runs? That's a huge benefit from being immutable (1.5M vs 736K?) but the hash table churn should be confined to early in the schbench run right?
Quoted 7 lines
Quoted 1 line
I think 30 secs or so. I used your command line.
Ah ok, my command line is 60 seconds. It feels like something is strange for the immutable flag to make it that much faster? schbench starts all the threads up front, so it should hit steady state pretty quickly. More on NUMA below, but I'll benchmark with the immutable flag on the turin box in the morning to see if it is the extra atomics.
Quoted 4 lines
That immutable flag makes this rcuref_get()/
put()go away. The price is that you can't change the size of the private hash anymore. So if your workload works best with a hash size of X and you don't intend to change it during the runtime of the program, set the immutable flag.
ok, for the benchmarks, I hard coded the number of buckets at 1024 and the only thing I flipped was the immutable flag. I was running on top of c0c9379f235df33a12ceae94370ad80c5278324d (just today's Linus).
schbench -L -m 4 -M auto -t 256 -n 0 -r 60 -s 0
1024 bucket without immutable:
RPS 2 297 856
1024 with immutable:
RPS 3 665 920
This is pretty similar to what 6.15 obtains, so I'm hoping we can find a way to get the 6.15 performance levels without the applications needing to call prctl manually.
I took some profiles on the 1024 + non-immutable
16.92% schbench [kernel.kallsyms] [k] futex_hash_put
|
|--8.93%--fpost
|
|--6.99%--xlist_wake_all
|
--0.58%--entry_SYSCALL_64
syscall
13.27% schbench libc.so.6 [.] syscall
|
|--8.90%--xlist_wake_all
|
--3.98%--entry_SYSCALL_64
syscall
12.36% schbench [kernel.kallsyms] [k] entry_SYSCALL_64
|
|--11.04%--__futex_hash
| futex_hash
| futex_wake
| do_futex
| __x64_sys_futex
| do_syscall_64
| entry_SYSCALL_64_after_hwframe
| syscall
|
--1.23%--futex_hash
futex_wake
do_futex
__x64_sys_futex
do_syscall_64
entry_SYSCALL_64_after_hwframe
syscallPercent │ 0xffffffff813f2f80 <futex_hash_put>:
0.05 │ → callq __fentry__
0.06 │ pushq %rbx
0.08 │ movq 0x18(%rdi),%rbx
0.05 │ testq %rbx,%rbx
0.03 │ ↓ je 15
12.49 │ cmpb $0x0,0x21(%rbx)
12.58 │ ↓ je 17
│15: popq %rbx
│ ← retq
0.24 │17: movl $0xffffffff,%esi
12.76 │ lock
│ xaddl %esi,(%rbx)
7.80 │ ┌──subl $0x1,%esi
22.96 │ ├──js 27
23.05 │ │ popq %rbx
7.85 │ │← retq
│27:└─→movq %rbx,%rdi
│ → callq rcuref_put_slowpath
│ testb %al,%al
│ ↑ je 15
│ movq 0x18(%rbx),%rdi
│ popq %rbx
│ → jmp wake_up_varIf you like profiles with line numbers:
12830 samples (10.24%) Comms: schbench
futex_hash_put @ /root/linux-6.15/kernel/futex/core.c:179:2
futex_private_hash_put @ /root/linux-6.15/kernel/futex/core.c:148:6 [inlined]
futex_private_hash_put @ /root/linux-6.15/kernel/futex/core.c:153:6 [inlined]
rcuref_put @ /root/linux-6.15/./include/linux/rcuref.h:173:13 [inlined]
__rcuref_put @ /root/linux-6.15/./include/linux/rcuref.h:110:5 [inlined]
futex_wake @ /root/linux-6.15/kernel/futex/waitwake.c:200:1
do_futex @ /root/linux-6.15/kernel/futex/syscalls.c:107:10
__x64_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:160:1
__se_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:160:1 [inlined]
__do_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:179:9 [inlined]
do_syscall_64 @ /root/linux-6.15/arch/x86/entry/syscall_64.c:94:7
do_syscall_x64 @ /root/linux-6.15/arch/x86/entry/syscall_64.c:63:12 [inlined]
entry_SYSCALL_64_after_hwframe
13795 samples (11.01%) Comms: schbench
futex_hash @ /root/linux-6.15/kernel/futex/core.c:311:15
futex_private_hash_get @ /root/linux-6.15/kernel/futex/core.c:143:5 [inlined]
futex_wake @ /root/linux-6.15/kernel/futex/waitwake.c:172:2
class_hb_constructor @ /root/linux-6.15/kernel/futex/futex.h:242:1 [inlined]
do_futex @ /root/linux-6.15/kernel/futex/syscalls.c:107:10
__x64_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:160:1
__se_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:160:1 [inlined]
__do_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:179:9 [inlined]
do_syscall_64 @ /root/linux-6.15/arch/x86/entry/syscall_64.c:94:7
do_syscall_x64 @ /root/linux-6.15/arch/x86/entry/syscall_64.c:63:12 [inlined]
entry_SYSCALL_64_after_hwframe
14364 samples (11.46%) Comms: schbench
entry_SYSCALL_64
17612 samples (14.05%) Comms: schbench
futex_hash @ /root/linux-6.15/kernel/futex/core.c:311:15
futex_private_hash_get @ /root/linux-6.15/kernel/futex/core.c:145:9 [inlined]
rcuref_get @ /root/linux-6.15/./include/linux/rcuref.h:87:5 [inlined]
futex_wake @ /root/linux-6.15/kernel/futex/waitwake.c:172:2
class_hb_constructor @ /root/linux-6.15/kernel/futex/futex.h:242:1 [inlined]
do_futex @ /root/linux-6.15/kernel/futex/syscalls.c:107:10
__x64_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:160:1
__se_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:160:1 [inlined]
__do_sys_futex @ /root/linux-6.15/kernel/futex/syscalls.c:179:9 [inlined]
do_syscall_64 @ /root/linux-6.15/arch/x86/entry/syscall_64.c:94:7
do_syscall_x64 @ /root/linux-6.15/arch/x86/entry/syscall_64.c:63:12 [inlined]
entry_SYSCALL_64_after_hwframeWith immutable, futexes are not in the top 10.
-chris
Quoted 1 line · Sebastian Andrzej Siewior
On 2025-06-05 20:55:27 [-0400], Chris Mason wrote:
[ ... ]
Quoted 8 lines
Quoted 3 lines
Going back to your diff, if we have a process growing the total number of threads, can we set
FH_IMMUTABLEtoo early? As the number of threads increases, eventually we'll pick the 2xnum_cpus, but that'll take a while?If you refer to the schbench diff, then set it early. Once the
prctl()to set the size of the private hash, there will be no resize by the kernel.
Quoted 5 lines
If you refer to the kernel diff where set the
FH_IMMUTABLEflag, then it is set once the upper limit is reached (that was the plan in case I did the logic wrong). Which means at that point it won't increase any further because of the CPU limit. The only way how you can reach it too early is if you offline CPUs.
I pulled your immutable diff on top of c0c9379f235d. Just the immutable diff, not the first suggestion that bumped num_online_cpus() * 2.
The RPS did not improve (~2.5M RPS). Looking at the futex_private_hash of the process:
Quoted 1 line
Quoted 1 line
Quoted 1 line
task.mm.futex_phash
*(struct futex_private_hash *)0xff110003bbd15000 = {
.users = (rcuref_t){
.refcnt = (atomic_t){
.counter = (int)0,
},
},
.hash_mask = (unsigned int)15,
.rcu = (struct callback_head){
.next = (struct callback_head *)0x0,
.func = (void (*)(struct callback_head *))0x0,
},
.mm = (void *)0xff110003321a2400,
.custom = (bool)0,
.immutable = (bool)1,
.queues = (struct futex_hash_bucket []){},
}It's because our calculation on the max is based on min(get_nr_threads(current), num_online_cpus())
get_nr_threads starts smaller than num_online_cpus(), so we immediately decide we've maxed out the buckets?
-chris
Peter Zijlstra
reviewerQuoted 22 lines · Sebastian Andrzej Siewior
Quoted 17 lines · Chris Mason
Quoted 11 lines
Quoted 10 lines
We've got large systems that are basically dedicated to single workloads, and those will probably miss the larger global hash table, regressing like schbench did. Then we have large systems spread over multiple big workloads that will love the private tables.
In either case, I think growing the hash table as a multiple of thread count instead of cpu count will probably better reflect the crazy things multi-threaded applications do? At any rate, I don't think we want applications to need prctl to get back to the performance they had on older kernels.
Quoted 5 lines
This is only an issue if all you CPUs spend their time in the kernel using the hash buckets at the same time.
This was the case in every benchmark I've seen so far. Your thing might be closer to an actual workload.Quoted 3 lines
I didn't spend a ton of time looking at the perf profiles of the slower kernel, was the bottleneck in the hash chain length or in contention for the buckets?
Quoted 6 lines
Every futex operation does a
rcuref_get()(which is an atomic inc) on the private hash. This is before anything else happens. If you have two threads, on two CPUs, which simultaneously do afutex()operation then both do thisrcuref_get(). That atomic inc ensures that the cacheline bounces from one CPU to the other. On the exit of the syscall there is a matchingrcuref_put().
How about something like this (very lightly tested)...
the TL;DR is that it turns all those refcounts into per-cpu ops when there is no hash replacement pending (eg. the normal case), and only folds the lot into an atomic when we really care about it.
There's some sharp corners still.. but it boots and survives the (slightly modified) selftest.
--- include/linux/futex.h | 12 +- include/linux/mm_types.h | 5 + kernel/futex/core.c | 238 +++++++++++++++++++-- .../selftests/futex/functional/futex_priv_hash.c | 11 +- 4 files changed, 239 insertions(+), 27 deletions(-)
include/linux/futex.h +3 -9
@@ -85,17 +85,11 @@ int futex_hash_prctl(unsigned long arg2, unsigned long arg3, unsigned long arg4)#ifdef CONFIG_FUTEX_PRIVATE_HASH int futex_hash_allocate_default (void );void futex_hash_free (struct mm_struct *mm); - -static inline void futex_mm_init (struct mm_struct *mm) -{ -RCU_INIT_POINTER (mm->futex_phash,NULL ); - mm->futex_phash_new =NULL ; -mutex_init (&mm->futex_hash_lock); -} +int futex_mm_init (struct mm_struct *mm);#else /* !CONFIG_FUTEX_PRIVATE_HASH */ static inline int futex_hash_allocate_default (void ) {return 0 ; } -static inline void futex_hash_free (struct mm_struct *mm) { } +static inline int futex_hash_free (struct mm_struct *mm) {return 0 ; }static inline void futex_mm_init (struct mm_struct *mm) { }#endif /* CONFIG_FUTEX_PRIVATE_HASH */
@@ -118,7 +112,7 @@ static inline int futex_hash_allocate_default(void) {return 0 ; } -static inline void futex_hash_free (struct mm_struct *mm) { } +static inline int futex_hash_free (struct mm_struct *mm) {return 0 ; }static inline void futex_mm_init (struct mm_struct *mm) { }#endif
include/linux/mm_types.h +5 -0
@@ -1070,6 +1070,11 @@ struct mm_struct {struct mutex futex_hash_lock;struct futex_private_hash __rcu *futex_phash;struct futex_private_hash *futex_phash_new; +/* futex-ref */ +unsigned long futex_batches; +struct rcu_head futex_rcu; +atomic_long_t futex_atomic; +unsigned int __percpu *futex_ref;#endif unsigned long hiwater_rss;/* High-watermark of RSS usage */
kernel/futex/core.c +221 -17
320 lines not on this page · raw message
tools/testing/selftests/futex/functional/futex_priv_hash.c +10 -1
@@ -97,6 +97,7 @@ static void create_max_threads(void *(*thread_fn)(void *)) ret =pthread_create (&threads[i],NULL , thread_fn,NULL );if (ret)ksft_exit_fail_msg ("pthread_create failed: %m\n" ); +usleep (5000 ); } }
@@ -131,6 +132,7 @@ int main(int argc, char *argv[])int use_global_hash =0 ;int ret;int c; +int retry =2 ;while ((c =getopt (argc, argv,"cghv:" )) !=-1 ) {switch (c) {
@@ -208,11 +210,18 @@ int main(int argc, char *argv[])*/ ksft_print_msg ("Online CPUs: %d\n" , online_cpus);if (online_cpus >16 ) { +again: futex_slotsn =futex_hash_slots_get ();if (futex_slotsn <0 || futex_slots1 == futex_slotsn) {ksft_print_msg ("Expected increase of hash buckets but got: %d -> %d\n" , futex_slots1, futex_slotsn); -ksft_exit_fail_msg (test_msg_auto_inc); +if (--retry) { +usleep (500000 ); + goto again; + }else { +ksft_test_result_fail (test_msg_auto_inc); +// ksft_exit_fail_msg(test_msg_auto_inc); + } }ksft_test_result_pass (test_msg_auto_inc); }else {
Quoted 30 lines · Peter Zijlstra
Quoted 22 lines · Sebastian Andrzej Siewior
Quoted 17 lines · Chris Mason
Quoted 11 lines
Quoted 10 lines
We've got large systems that are basically dedicated to single workloads, and those will probably miss the larger global hash table, regressing like schbench did. Then we have large systems spread over multiple big workloads that will love the private tables.
In either case, I think growing the hash table as a multiple of thread count instead of cpu count will probably better reflect the crazy things multi-threaded applications do? At any rate, I don't think we want applications to need prctl to get back to the performance they had on older kernels.
Quoted 5 lines
This is only an issue if all you CPUs spend their time in the kernel using the hash buckets at the same time.
This was the case in every benchmark I've seen so far. Your thing might be closer to an actual workload.Quoted 3 lines
I didn't spend a ton of time looking at the perf profiles of the slower kernel, was the bottleneck in the hash chain length or in contention for the buckets?
Quoted 6 lines
Every futex operation does a
rcuref_get()(which is an atomic inc) on the private hash. This is before anything else happens. If you have two threads, on two CPUs, which simultaneously do afutex()operation then both do thisrcuref_get(). That atomic inc ensures that the cacheline bounces from one CPU to the other. On the exit of the syscall there is a matchingrcuref_put().
Quoted 8 lines
How about something like this (very lightly tested)...
the TL;DR is that it turns all those refcounts into per-cpu ops when there is no hash replacement pending (eg. the normal case), and only folds the lot into an atomic when we really care about it.
There's some sharp corners still.. but it boots and survives the (slightly modified) selftest.
I can get some benchmarks going of this, thanks. For 6.16, is the goal to put something like this in, or default to the global hash table until we've nailed it down?
I'd vote for defaulting to global for one more release.
-chris
Peter Zijlstra
reviewerQuoted 37 lines · Chris Mason
Quoted 36 lines · Peter Zijlstra
Quoted 22 lines · Sebastian Andrzej Siewior
Quoted 17 lines · Chris Mason
Quoted 11 lines
Quoted 10 lines
We've got large systems that are basically dedicated to single workloads, and those will probably miss the larger global hash table, regressing like schbench did. Then we have large systems spread over multiple big workloads that will love the private tables.
In either case, I think growing the hash table as a multiple of thread count instead of cpu count will probably better reflect the crazy things multi-threaded applications do? At any rate, I don't think we want applications to need prctl to get back to the performance they had on older kernels.
Quoted 5 lines
This is only an issue if all you CPUs spend their time in the kernel using the hash buckets at the same time.
This was the case in every benchmark I've seen so far. Your thing might be closer to an actual workload.Quoted 3 lines
I didn't spend a ton of time looking at the perf profiles of the slower kernel, was the bottleneck in the hash chain length or in contention for the buckets?
Quoted 6 lines
Every futex operation does a
rcuref_get()(which is an atomic inc) on the private hash. This is before anything else happens. If you have two threads, on two CPUs, which simultaneously do afutex()operation then both do thisrcuref_get(). That atomic inc ensures that the cacheline bounces from one CPU to the other. On the exit of the syscall there is a matchingrcuref_put().How about something like this (very lightly tested)...
the TL;DR is that it turns all those refcounts into per-cpu ops when there is no hash replacement pending (eg. the normal case), and only folds the lot into an atomic when we really care about it.
Quoted 8 lines
Quoted 2 lines
There's some sharp corners still.. but it boots and survives the (slightly modified) selftest.
I can get some benchmarks going of this, thanks. For 6.16, is the goal to put something like this in, or default to the global hash table until we've nailed it down?
I'd vote for defaulting to global for one more release.
Probably best to do that; means we don't have to rush crazy code :-)
Quoted 3 lines · Peter Zijlstra
Quoted 1 line
I'd vote for defaulting to global for one more release.
Probably best to do that; means we don't have to rush crazy code :-)
If we do that, that means we need to ensure that the private hash is not deployed while a thread is created and the prctl() function can only work create the private hash if the application is single threaded.
Sebastian
Peter Zijlstra
reviewerQuoted 8 lines · Sebastian Andrzej Siewior
Quoted 3 lines · Peter Zijlstra
Quoted 1 line
I'd vote for defaulting to global for one more release.
Probably best to do that; means we don't have to rush crazy code :-)
If we do that, that means we need to ensure that the private hash is not deployed while a thread is created and the
prctl()function can only work create the private hash if the application is single threaded.
I was thinking something like so..
---
init/Kconfig +4 -0
@@ -1716,9 +1716,13 @@ config FUTEX_PI depends on FUTEX && RT_MUTEXES default y +# +# marked broken for performance reasons; gives us one more cycle to sort things out. +# config FUTEX_PRIVATE_HASH bool depends on FUTEX && !BASE_SMALL && MMU + depends on BROKEN default y config FUTEX_MPOL
Quoted 11 lines · Peter Zijlstra
Quoted 8 lines · Sebastian Andrzej Siewior
Quoted 3 lines · Peter Zijlstra
Quoted 1 line
I'd vote for defaulting to global for one more release.
Probably best to do that; means we don't have to rush crazy code :-)
If we do that, that means we need to ensure that the private hash is not deployed while a thread is created and the
prctl()function can only work create the private hash if the application is single threaded.I was thinking something like so..
Okay. That increases the motivation to fix it in one cycle. Anything you want me to do here?
Sebastian
PATCH 1/1 futex: Temporary disable FUTEX_PRIVATE_HASH
In reply to Peter ZijlstraChris Mason reported a performance regression on big iron. Reports of this kind were usually reported as part of a micro benchmark but Chris' test did mimic his real workload. This makes it a real regression.
The root cause is rcuref_get() which is invoked during each futex operation. If all threads of an application do this simultaneously then it leads to cache line bouncing and the performance drops.
Disable FUTEX_PRIVATE_HASH entirely for this cycle. The performance regression will be addressed in the following cycle enabling the option again.
--- init/Kconfig | 4 ++++ 1 file changed, 4 insertions(+)
init/Kconfig +4 -0
@@ -1716,9 +1716,13 @@ config FUTEX_PI depends on FUTEX && RT_MUTEXES default y +# +# marked broken for performance reasons; gives us one more cycle to sort things out. +# config FUTEX_PRIVATE_HASH bool depends on FUTEX && !BASE_SMALL && MMU + depends on BROKEN default y config FUTEX_MPOL
Signature · 1 line
2.50.0
[tip: locking/urgent] futex: Temporary disable FUTEX_PRIVATE_HASH
The following commit has been merged into the locking/urgent branch of tip:
The following commit has been merged into the locking/urgent branch of tip:
Commit-ID: 9a57c3773152a3ff2c35cc8325e088d011c9f83b Gitweb: https://git.kernel.org/tip/9a57c3773152a3ff2c35cc8325e088d011c9f83b Author: Sebastian Andrzej Siewior <[email protected]> AuthorDate: Mon, 30 Jun 2025 16:50:34 +02:00 Committer: Peter Zijlstra <[email protected]> CommitterDate: Tue, 01 Jul 2025 15:02:05 +02:00
futex: Temporary disable FUTEX_PRIVATE_HASH
Chris Mason reported a performance regression on big iron. Reports of this kind were usually reported as part of a micro benchmark but Chris' test did mimic his real workload. This makes it a real regression.
The root cause is rcuref_get() which is invoked during each futex operation. If all threads of an application do this simultaneously then it leads to cache line bouncing and the performance drops.
Disable FUTEX_PRIVATE_HASH entirely for this cycle. The performance regression will be addressed in the following cycle enabling the option again.
--- init/Kconfig | 4 ++++ 1 file changed, 4 insertions(+)
init/Kconfig +4 -0
@@ -1716,9 +1716,13 @@ config FUTEX_PI depends on FUTEX && RT_MUTEXES default y +# +# marked broken for performance reasons; gives us one more cycle to sort things out. +# config FUTEX_PRIVATE_HASH bool depends on FUTEX && !BASE_SMALL && MMU + depends on BROKEN default y config FUTEX_MPOL
kernel test robot
build botRe: [PATCH] futex: Temporary disable FUTEX_PRIVATE_HASH
In reply to Sebastian Andrzej Siewiorfrom the commit message, we know this 'temporary disable' is to address a performance regression. so we still send out this report FYI what's the possible performance impact. however, our team focus…
Hello,
from the commit message, we know this 'temporary disable' is to address a performance regression. so we still send out this report FYI what's the possible performance impact. however, our team focus on micro benchmark, so, anyway, just FYI.
kernel test robot noticed a 1.9% improvement of perf-bench-futex.ops/s on:
commit: bc1aa469e545fe16a62d501e095630cccc3fe1c4 ("[PATCH] futex: Temporary disable FUTEX_PRIVATE_HASH")
url: https://github.com/intel-lab-lkp/linux/commits/Sebastian-Andrzej-Siewior/futex-Temporary-disable-FUTEX_PRIVATE_HASH/20250630-225317
base: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git d0b3b7b22dfa1f4b515fd3a295b3fd958f9e81af patch link: https://lore.kernel.org/all/[email protected]/
patch subject: [PATCH] futex: Temporary disable FUTEX_PRIVATE_HASH
testcase: perf-bench-futex
config: x86_64-rhel-9.4
compiler: gcc-12
test machine: 192 threads 2 sockets Intel(R) Xeon(R) 6740E CPU @ 2.4GHz (Sierra Forest) with 256G memory parameters:
runtime: 300s nr_task: 100% test: hash shared: shared cpufreq_governor: performance
Details are as below:
-------------------------------------------------------------------------------------------------->
The kernel config and materials to reproduce are available at:
https://download.01.org/0day-ci/archive/20250716/[email protected]
=========================================================================================
compiler/cpufreq_governor/kconfig/nr_task/rootfs/runtime/shared/tbox_group/test/testcase:
gcc-12/performance/x86_64-rhel-9.4/100%/debian-12-x86_64-20240206.cgz/300s/shared/lkp-srf-2sp2/hash/perf-bench-futex
commit:
v6.16-rc4
bc1aa469e5 ("futex: Temporary disable FUTEX_PRIVATE_HASH")
v6.16-rc4 bc1aa469e545fe16a62d501e095
---------------- ---------------------------
%stddev %change %stddev
\ | \
2249734 +1.9% 2291792 perf-bench-futex.ops/s
6622 +3.7% 6868 perf-bench-futex.time.user_time
115.83 ± 12% +40.1% 162.33 ± 18% perf-sched.wait_and_delay.count.irqentry_exit_to_user_mode.asm_sysvec_call_function_single.[unknown].[unknown]
4.40 ± 19% +343.0% 19.51 ± 64% perf-sched.wait_and_delay.max.ms.schedule_timeout.__wait_for_common.wait_for_completion_state.kernel_clone
4.15 ± 17% +347.3% 18.55 ± 69% perf-sched.wait_time.max.ms.schedule_timeout.__wait_for_common.wait_for_completion_state.kernel_clone
21.00 ± 63% +121.4% 46.50 ± 11% perf-c2c.DRAM.local
4129 ± 57% +225.5% 13444 perf-c2c.DRAM.remote
67558 ± 56% +66.3% 112351 perf-c2c.HITM.local
4045 ± 57% +227.2% 13237 perf-c2c.HITM.remote
71603 ± 57% +75.4% 125588 perf-c2c.HITM.total
1.674e+08 ± 20% +19.0% 1.991e+08 perf-stat.i.cache-misses
4.096e+08 ± 20% +19.4% 4.891e+08 perf-stat.i.cache-references
0.36 +2.9% 0.37 perf-stat.overall.MPKI
3127 -1.8% 3070 perf-stat.overall.cycles-between-cache-misses
1.669e+08 ± 20% +18.9% 1.985e+08 perf-stat.ps.cache-misses
4.085e+08 ± 20% +19.3% 4.874e+08 perf-stat.ps.cache-references
1.622e+14 -1.0% 1.606e+14 perf-stat.total.instructionsDisclaimer:
Results have been estimated based on internal Intel analysis and are provided for informational purposes only. Any difference in system hardware or software design or configuration may affect actual performance.
Signature · 2 lines
0-DAY CI Kernel Test Service https://github.com/intel/lkp-tests/wiki
Quoted 5 lines · Peter Zijlstra
How about something like this (very lightly tested)...
the TL;DR is that it turns all those refcounts into per-cpu ops when there is no hash replacement pending (eg. the normal case), and only folds the lot into an atomic when we really care about it.
so we have per-CPU counter and on resize we wait one RCU grace period to ensure everybody observed current fph, switch to atomics and wait one grace period to ensure everyone is using atomics. Last step is to align the atomic counter with the per-CPU counters and once the counter reaches 0 perform the swap.
This looks fine :) Due to the RCU grace period, the swap takes longer than before. I guess that is why you said earlier with to use srcu. For things like "hackbench -T" you end up creating a new hash on every thread creation which is not applied because RCU takes a while. This could be optimized later by checking if the hash in futex_phash_new matches the requested size.
Quoted 2 lines
There's some sharp corners still.. but it boots and survives the (slightly modified) selftest.
The refcount does not pop up in perf so that is good.
Quoted 7 lines
kernel/futex/core.c +0
-1@@ -243,14 +247,18 @@ static bool __futex_pivot_hash(struct mm_struct *mm, fph =rcu_dereference_protected (mm->futex_phash,lockdep_is_held (&mm->futex_hash_lock));if (fph) { -if (!rcuref_is_dead (&fph->users)) {
kernel/futex/core.c static bool __futex_pivot_hash(struct mm_struct *mm, · line 258
Quoted 10 lines
kernel/futex/core.c +3
-1+if (!futex_ref_is_dead (fph)) { mm->futex_phash_new = new;return false; }futex_rehash_private (fph, new); } -rcu_assign_pointer (mm->futex_phash, new); + new->state =FR_PERCPU ; +scoped_guard (rcu) {
We do space or we don't? It looks like sched/ does while the remaining bits of the kernel mostly don't. I don't care but we could (later) adjust it for futex towards one direction.
Quoted 6 lines
kernel/futex/core.c +3
-0+ mm->futex_batches =get_state_synchronize_rcu (); +rcu_assign_pointer (mm->futex_phash, new); + }kvfree_rcu (fph, rcu);return true; }
…
Quoted 1 line
+static void
futex_ref_drop(struct futex_private_hash *fph)
…
kernel/futex/core.c
Quoted 1 line
kernel/futex/core.c +1
-0+call_rcu_hurry (&mm->futex_rcu, futex_ref_rcu);
Do you think it would improve with srcu or it is not worth it?
Quoted 31 lines
kernel/futex/core.c +31
-0+} + +static bool futex_ref_get (struct futex_private_hash *fph) +{ +struct mm_struct *mm = fph->mm; + +guard (preempt)(); + +if (smp_load_acquire (&fph->state) ==FR_PERCPU ) { +this_cpu_inc (*mm->futex_ref); +return true; + } + +return atomic_long_inc_not_zero (&mm->futex_atomic); +} + +static bool futex_ref_put (struct futex_private_hash *fph) +{ +struct mm_struct *mm = fph->mm; + +guard (preempt)(); + +if (smp_load_acquire (&fph->state) ==FR_PERCPU ) { +this_cpu_dec (*mm->futex_ref); +return false; + } + +return atomic_long_dec_and_test (&mm->futex_atomic); +} + +static bool futex_ref_is_dead (struct futex_private_hash *fph)
kernel/futex/core.c static void futex_hash_bucket_init(struct futex_hash_bucket *fhb, · line 1717
Quoted 10 lines
kernel/futex/core.c +10
-0+{ +struct mm_struct *mm = fph->mm; + +guard (preempt)(); + +if (smp_load_acquire (&fph->state) ==FR_PERCPU ) +return false; + +return atomic_long_read (&mm->futex_atomic) ==0 ; +}
Why preempt_disable()? Is it just an optimized version of rcu_read_lock()? I don't understand why. You don't even go for __this_cpu_inc() so I a bit puzzled.
Sebastian
Peter Zijlstra
reviewerQuoted 7 lines · Sebastian Andrzej Siewior
Quoted 5 lines · Peter Zijlstra
How about something like this (very lightly tested)...
the TL;DR is that it turns all those refcounts into per-cpu ops when there is no hash replacement pending (eg. the normal case), and only folds the lot into an atomic when we really care about it.
Quoted 8 lines
so we have per-CPU counter and on resize we wait one RCU grace period to ensure everybody observed current fph, switch to atomics and wait one grace period to ensure everyone is using atomics. Last step is to align the atomic counter with the per-CPU counters and once the counter reaches 0 perform the swap.
This looks fine :) Due to the RCU grace period, the swap takes longer than before.
Yes, but given this is supposed to be 'rare', I didn't think that was a problem.
Quoted 5 lines
I guess that is why you said earlier with to use srcu. For things like "hackbench -T" you end up creating a new hash on every thread creation which is not applied because RCU takes a while. This could be optimized later by checking if the hash in
futex_phash_newmatches the requested size.
So the main benefit of using SRCU (I have half a patch and a head-ache to show for it) is that you don't need the per-mm-per-cpu memory storage. The down-side is that you share the 'refcount' between all mm's so it gets to be even slower.
The 'problem' is that reasoning about stuff comes even harder. But the main idea is to replace mm->futex_phash with a 'tombstone' value to force __futex_hash() into taking the slow-path and hitting mm->futex_hash_lock.
Then you do call_srcu() to wait one SRCU period, this has everybody stalled, and guarantees the fph you had is now unused so we can rehash. Then replace the tombstone with the new hash and start over.
It's just that stuff like futex_hash_get() gets somewhat tricky, you have to ensure the SRCU periods overlap.
Anyway, that approach should be feasible as well, just not sure of the trade-offs.
Quoted 4 lines
Quoted 2 lines
There's some sharp corners still.. but it boots and survives the (slightly modified) selftest.
The refcount does not pop up in perf so that is good.
\o/
Quoted 12 lines
Quoted 12 lines
kernel/futex/core.c +1
-1@@ -243,14 +247,18 @@ static bool __futex_pivot_hash(struct mm_struct *mm, fph =rcu_dereference_protected (mm->futex_phash,lockdep_is_held (&mm->futex_hash_lock));if (fph) { -if (!rcuref_is_dead (&fph->users)) { +if (!futex_ref_is_dead (fph)) { mm->futex_phash_new = new;return false; }
Quoted 9 lines
kernel/futex/core.c static bool __futex_pivot_hash(struct mm_struct *mm, · line 258
Quoted 5 lines
kernel/futex/core.c +2
-1futex_rehash_private (fph, new); } -rcu_assign_pointer (mm->futex_phash, new); + new->state =FR_PERCPU ; +scoped_guard (rcu) {We do space or we don't? It looks like sched/ does while the remaining bits of the kernel mostly don't. I don't care but we could (later) adjust it for futex towards one direction.
Oh, scoped_guard is for and we write for loops with a space on. Perhaps its because I wrote it all and know this. But yeah, meh :-)
Quoted 7 lines
Quoted 6 lines
kernel/futex/core.c +3
-0+ mm->futex_batches =get_state_synchronize_rcu (); +rcu_assign_pointer (mm->futex_phash, new); + }kvfree_rcu (fph, rcu);return true; }…
Quoted 5 lines
Quoted 1 line
+static void
futex_ref_drop(struct futex_private_hash *fph)…
kernel/futex/core.c
Quoted 1 line
kernel/futex/core.c +1
-0+call_rcu_hurry (&mm->futex_rcu, futex_ref_rcu);Do you think it would improve with srcu or it is not worth it?
Per the above, I'm not sure about the trade-offs. I think the SRCU approach can be made to work -- I just got me head in a twist.
Quoted 37 lines
Quoted 37 lines
kernel/futex/core.c +37
-0+} + +static bool futex_ref_get (struct futex_private_hash *fph) +{ +struct mm_struct *mm = fph->mm; + +guard (preempt)(); + +if (smp_load_acquire (&fph->state) ==FR_PERCPU ) { +this_cpu_inc (*mm->futex_ref); +return true; + } + +return atomic_long_inc_not_zero (&mm->futex_atomic); +} + +static bool futex_ref_put (struct futex_private_hash *fph) +{ +struct mm_struct *mm = fph->mm; + +guard (preempt)(); + +if (smp_load_acquire (&fph->state) ==FR_PERCPU ) { +this_cpu_dec (*mm->futex_ref); +return false; + } + +return atomic_long_dec_and_test (&mm->futex_atomic); +} + +static bool futex_ref_is_dead (struct futex_private_hash *fph) +{ +struct mm_struct *mm = fph->mm; + +guard (preempt)(); + +if (smp_load_acquire (&fph->state) ==FR_PERCPU )
Quoted 8 lines
kernel/futex/core.c static void futex_hash_bucket_init(struct futex_hash_bucket *fhb, · line 1717
Quoted 4 lines
kernel/futex/core.c +4
-0+return false; + +return atomic_long_read (&mm->futex_atomic) ==0 ; +}Why
preempt_disable()? Is it just an optimized version ofrcu_read_lock()? I don't understand why. You don't even go for__this_cpu_inc()so I a bit puzzled.
The code morphed a lot over the two days it took to write this. But yeah, preempt or rcu doesn't really matter here.
I didn't yet think about __this_cpu, its not really relevant on x86. If you want to make that relaxation you have to consider IRQ and SoftIRQ handling though. Given we have this_cpu_inc() in the RCU callback, which is ran from SoftIRQ context, this might not be safe.
Quoted 10 lines · Peter Zijlstra
Quoted 5 lines
I guess that is why you said earlier with to use srcu. For things like "hackbench -T" you end up creating a new hash on every thread creation which is not applied because RCU takes a while. This could be optimized later by checking if the hash in
futex_phash_newmatches the requested size.So the main benefit of using SRCU (I have half a patch and a head-ache to show for it) is that you don't need the per-mm-per-cpu memory storage. The down-side is that you share the 'refcount' between all mm's so it gets to be even slower.
I see. So it is not just s/rcu/srcu/ for the hopefully quicker grace period since it does not affect whole system. It a different algorithm.
Quoted 9 lines
The 'problem' is that reasoning about stuff comes even harder. But the main idea is to replace
mm->futex_phashwith a 'tombstone' value to force__futex_hash()into taking the slow-path and hittingmm->futex_hash_lock.Then you do
call_srcu()to wait one SRCU period, this has everybody stalled, and guarantees the fph you had is now unused so we can rehash. Then replace the tombstone with the new hash and start over.
Quoted 5 lines
It's just that stuff like
futex_hash_get()gets somewhat tricky, you have to ensure the SRCU periods overlap.Anyway, that approach should be feasible as well, just not sure of the trade-offs.
The current looks reasonable enough and it survived yesterday's testing.
Quoted 11 lines
Quoted 3 lines
Why
preempt_disable()? Is it just an optimized version ofrcu_read_lock()? I don't understand why. You don't even go for__this_cpu_inc()so I a bit puzzled.The code morphed a lot over the two days it took to write this. But yeah, preempt or rcu doesn't really matter here.
I didn't yet think about
__this_cpu, its not really relevant on x86. If you want to make that relaxation you have to consider IRQ and SoftIRQ handling though. Given we havethis_cpu_inc()in the RCU callback, which is ran from SoftIRQ context, this might not be safe.
Nah, I am all for a simple cguard(rcu) here.
Sebastian
Quoted 28 lines · Peter Zijlstra
How about something like this (very lightly tested)...
the TL;DR is that it turns all those refcounts into per-cpu ops when there is no hash replacement pending (eg. the normal case), and only folds the lot into an atomic when we really care about it.
There's some sharp corners still.. but it boots and survives the (slightly modified) selftest.
--- include/linux/futex.h | 12 +- include/linux/mm_types.h | 5 + kernel/futex/core.c | 238 +++++++++++++++++++-- .../selftests/futex/functional/futex_priv_hash.c | 11 +- 4 files changed, 239 insertions(+), 27 deletions(-)include/linux/futex.h +0
-3@@ -85,17 +85,11 @@ int futex_hash_prctl(unsigned long arg2, unsigned long arg3, unsigned long arg4)#ifdef CONFIG_FUTEX_PRIVATE_HASH int futex_hash_allocate_default (void );void futex_hash_free (struct mm_struct *mm); - -static inline void futex_mm_init (struct mm_struct *mm) -{
include/linux/futex.h int futex_hash_prctl(unsigned long arg2, unsigned long arg3, unsigned long arg4) · line 92
Quoted 10 lines
include/linux/futex.h +2
-5-RCU_INIT_POINTER (mm->futex_phash,NULL ); - mm->futex_phash_new =NULL ; - mutex_init(&mm->futex_hash_lock); -} +int futex_mm_init (struct mm_struct *mm);#else /* !CONFIG_FUTEX_PRIVATE_HASH */ static inline int futex_hash_allocate_default (void ) {return 0 ; } -static inline void futex_hash_free (struct mm_struct *mm) { } +static inline int futex_hash_free (struct mm_struct *mm) {return 0 ; }
Minor nit.
futex_hash_free() is defined to return void for CONFIG_FUTEX_PRIVATE_HASH
config. But is now defined to return int for !CONFIG_FUTEX_PRIVATE_HASH and !CONFIG_FUTEX configs. But it seems like nobody is actually checking the return value. It
seems to make more sense to keep the return value as void here so
the return value is consistent?
Tim
Quoted 12 lines
include/linux/futex.h +1
-1static inline void futex_mm_init (struct mm_struct *mm) { }#endif /* CONFIG_FUTEX_PRIVATE_HASH */ @@ -118,7 +112,7 @@ static inline int futex_hash_allocate_default(void) {return 0 ; } -static inline void futex_hash_free (struct mm_struct *mm) { } +static inline int futex_hash_free (struct mm_struct *mm) {return 0 ; }static inline void futex_mm_init (struct mm_struct *mm) { }#endif
Peter Zijlstra
reviewerQuoted 42 lines · Tim Chen
Quoted 28 lines · Peter Zijlstra
How about something like this (very lightly tested)...
the TL;DR is that it turns all those refcounts into per-cpu ops when there is no hash replacement pending (eg. the normal case), and only folds the lot into an atomic when we really care about it.
There's some sharp corners still.. but it boots and survives the (slightly modified) selftest.
--- include/linux/futex.h | 12 +- include/linux/mm_types.h | 5 + kernel/futex/core.c | 238 +++++++++++++++++++-- .../selftests/futex/functional/futex_priv_hash.c | 11 +- 4 files changed, 239 insertions(+), 27 deletions(-)include/linux/futex.h +0
-3@@ -85,17 +85,11 @@ int futex_hash_prctl(unsigned long arg2, unsigned long arg3, unsigned long arg4)#ifdef CONFIG_FUTEX_PRIVATE_HASH int futex_hash_allocate_default (void );void futex_hash_free (struct mm_struct *mm); - -static inline void futex_mm_init (struct mm_struct *mm) -{include/linux/futex.h int futex_hash_prctl(unsigned long arg2, unsigned long arg3, unsigned long arg4) · line 92
Quoted 10 lines
include/linux/futex.h +2
-5-RCU_INIT_POINTER (mm->futex_phash,NULL ); - mm->futex_phash_new =NULL ; - mutex_init(&mm->futex_hash_lock); -} +int futex_mm_init (struct mm_struct *mm);#else /* !CONFIG_FUTEX_PRIVATE_HASH */ static inline int futex_hash_allocate_default (void ) {return 0 ; } -static inline void futex_hash_free (struct mm_struct *mm) { } +static inline int futex_hash_free (struct mm_struct *mm) {return 0 ; }Minor nit.
Quoted 5 lines
futex_hash_free()is defined to return void forCONFIG_FUTEX_PRIVATE_HASH
config. But is now defined to return int for !CONFIG_FUTEX_PRIVATE_HASH and !CONFIG_FUTEX configs. But it seems like nobody is actually checking the return value. It
seems to make more sense to keep the return value as void here so
the return value is consistent?
YEah, not sure what happened there. There's a TODO item to actually make sure someone looks at the futex_mm_init() return value, I guess that's a good moment to clean this up too :-)