Skip to contentSkip to conversation

futex performance regression from "futex: Allow automatic allocation of process wide futex hash"

PATCH Applied Chris Mason 6 participants 22 messages Jun 3, 2025 – Jul 16, 2025

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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

#1 lore raw
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
index abbd97c2fcba8..9046f3d9693e7 100644
@@ -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
index abbd97c2fcba8..a19a96cc09c9e 100644
@@ -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

#2 lore raw
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_t but 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
index abbd97c2fcba8..9046f3d9693e7 100644
@@ -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: 1

tested 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
index 1be3e280f5c38..40a5f0091111e 100644
@@ -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

#3 lore raw
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 -0
 		fph = 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_HASH off, so the Kconfig help 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> | 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?

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

#4 lore raw
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_HASH off, so the Kconfig help 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> | average

rps: 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

#5 lore raw
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_HASH off, so the Kconfig help 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> | 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 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_IMMUTABLE too early? As the number of threads increases, eventually we'll pick the 2x num_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

#6 lore raw
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 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_HASH off, so the Kconfig help 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> | 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 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
                       syscall
Percent │    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_var

If 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_hwframe

With immutable, futexes are not in the top 10.

-chris

#7 lore raw
In reply to Sebastian Andrzej Siewior
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_IMMUTABLE too early? As the number of threads increases, eventually we'll pick the 2x num_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_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.

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

#8 lore raw
In reply to Sebastian Andrzej Siewior
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 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().

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
index b37193653e6b..5f92c7a8ba57 100644
@@ -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
index d6b91e8a66d6..0f0662157066 100644
@@ -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
index 24a92dc94eb8..1238a7178715 100644
@@ -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 {
#9 lore raw
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 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 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

#10 lore raw
Quoted 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 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().

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

#11 lore raw
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

#12 lore raw
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..

---

init/Kconfig +4 -0
index af4c2f085455..666783eb50ab 100644
@@ -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
#13 lore raw
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

#14 lore raw

PATCH 1/1 futex: Temporary disable FUTEX_PRIVATE_HASH

In reply to Peter Zijlstra

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
index af4c2f0854554..666783eb50abd 100644
@@ -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
#15 lore raw

[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
index af4c2f0..666783e 100644
@@ -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
#16 lore raw

Re: [PATCH] futex: Temporary disable FUTEX_PRIVATE_HASH

In reply to Sebastian Andrzej Siewior
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…

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.instructions

Disclaimer:
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
#17 lore raw
In reply to Peter Zijlstra
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

#18 lore raw
Quoted 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_new matches 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 -1
 		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.

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 of rcu_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.

#19 lore raw
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_new matches 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_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.

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 of rcu_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.

Nah, I am all for a simple cguard(rcu) here.

Sebastian

#20 lore raw
In reply to Peter Zijlstra
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
index b37193653e6b..5f92c7a8ba57 100644
@@ -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 -1
 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
#21 lore raw
Quoted 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
index b37193653e6b..5f92c7a8ba57 100644
@@ -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 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?

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