futex: Dynamically allocate futex_queues depending on nr_node_ids
Subsystems (3)
RFC PATCH 1/1 futex: Dynamically allocate futex_queues depending on nr_node_ids
CONFIG_NODES_SHIFT (which influences MAX_NUMNODES) is often configured generously by distros while the actual number of possible NUMA nodes on most systems is often quite conservative.
Instead of reserving MAX_NUMNODES worth of space for futex_queues, dynamically allocate it based on "nr_node_ids" at the time of futex_init().
"nr_node_ids" at the time of futex_init() is cached as "nr_futex_queues" to compensate for the extra dereference necessary to access the elements of futex_queues which ends up in a different cacheline now.
Running 5 runs of perf bench futex showed no measurable impact for any variants on a dual socket 3rd generation AMD EPYC system (2 x 64C/128T):
variant locking/futex base + patch %diff
futex/hash 1220783.2 1333296.2 (9%) futex/wake 0.71186 0.72584 (2%) futex/wake-parallel 0.00624 0.00664 (6%) futex/requeue 0.25088 0.26102 (4%) futex/lock-pi 57.6 57.8 (0%)
Note: futex/hash had noticeable run to run variance on test machine.
"nr_node_ids" can rarely be larger than num_possible_nodes() but the additional space allows for simpler handling of node index in presence of sparse node_possible_map.
---
Sebastian,
Does this work for your concerns with the large "MAX_NUMNODES" values on most distros? It does put the "queues" into a separate cacheline from the __futex_data.
The other option is to dynamically allocate the entire __futex_data as:
struct {
unsigned long hashmask;
unsigned int hashshift;
unsigned int nr_queues;
struct futex_hash_bucket *queues[] __counted_by(nr_queues);
} *__futex_data __ro_after_init;with a variable length "queues" at the end if we want to ensure everything ends up in the same cacheline but all the __futex_data member access would then be pointer dereferencing which might not be ideal.
Thoughts?
--- kernel/futex/core.c | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-)
kernel/futex/core.c +9 -3
@@ -56,11 +56,13 @@static struct {unsigned long hashmask;unsigned int hashshift; -struct futex_hash_bucket *queues[MAX_NUMNODES ]; +unsigned int nr_queues; +struct futex_hash_bucket **queues; } __futex_data__read_mostly __aligned(2*sizeof(long)) ;#define futex_hashmask (__futex_data.hashmask)#define futex_hashshift (__futex_data.hashshift) +#define nr_futex_queues (__futex_data.nr_queues)#define futex_queues (__futex_data.queues)struct futex_private_hash {
@@ -439,10 +441,10 @@ __futex_hash(union futex_key *key, struct futex_private_hash *fph)* NOTE: this isn't perfectly uniform, but it is fast and * handles sparse node masks. */ - node = (hash >> futex_hashshift) % nr_node_ids; + node = (hash >> futex_hashshift) % nr_futex_queues;if (!node_possible (node)) { node =find_next_bit_wrap (node_possible_map.bits, - nr_node_ids, node); + nr_futex_queues, node); } }
@@ -1987,6 +1989,10 @@ static int __init futex_init(void) size =sizeof (struct futex_hash_bucket ) * hashsize; order =get_order (size); + nr_futex_queues = nr_node_ids; + futex_queues =kcalloc (nr_futex_queues,sizeof (*futex_queues),GFP_KERNEL ); +BUG_ON (!futex_queues); +for_each_node (n) {struct futex_hash_bucket *table;
base-commit: c42ba5a87bdccbca11403b7ca8bad1a57b833732
Signature · 1 line
2.34.1
Quoted 11 lines · K Prateek Nayak
CONFIG_NODES_SHIFT(which influencesMAX_NUMNODES) is often configured generously by distros while the actual number of possible NUMA nodes on most systems is often quite conservative.Instead of reserving
MAX_NUMNODESworth of space forfutex_queues, dynamically allocate it based on "nr_node_ids" at the time offutex_init()."
nr_node_ids" at the time offutex_init()is cached as "nr_futex_queues" to compensate for the extra dereference necessary to access the elements offutex_queueswhich ends up in a different cacheline now.
With the Debian config CONFIG_NODES_SHIFT is set to 10 as of 6.18.12+deb14 for amd64 probably due to MAXSMP.
Quoted 11 lines
Running 5 runs of perf bench futex showed no measurable impact for any variants on a dual socket 3rd generation AMD EPYC system (2 x 64C/128T):
variant locking/futex base + patch %diff
futex/hash 1220783.2 1333296.2 (9%) futex/wake 0.71186 0.72584 (2%) futex/wake-parallel 0.00624 0.00664 (6%) futex/requeue 0.25088 0.26102 (4%) futex/lock-pi 57.6 57.8 (0%)Note: futex/hash had noticeable run to run variance on test machine.
so we are getting slightly worse?
Quoted 4 lines
"
nr_node_ids" can rarely be larger thannum_possible_nodes()but the additional space allows for simpler handling of node index in presence of sparsenode_possible_map.
Quoted 8 lines
Reported-by Sebastian Andrzej Siewior <[email protected]>Signed-off-by K Prateek Nayak <[email protected]>---
Sebastian,Does this work for your concerns with the large "
MAX_NUMNODES" values on most distros? It does put the "queues" into a separate cacheline from the__futex_data.
I didn't want to do this because now we have two pointers to resolve, nr_node_ids vs nr_futex_queues should be largely the same. And I *think* the kernel image is mapped interleaved while the kcalloc() is from the current node (mostly #1). Having the huge array does not create any runtime overhead, it is just that we allocate 8KiB of memory here while 32 bytes for the 4 average nodes should be just fine. At least this is my imagination that 4 nodes the average upper limit.
My question was initially is 1024 for max-nodes something that people really use. It was introduced as of
https://lore.kernel.org/all/[email protected]/
but it looks odd. It might just one or two machines which are left :)
Quoted 9 lines
The other option is to dynamically allocate the entire
__futex_dataas:struct { unsigned long hashmask; unsigned int hashshift; unsigned int nr_queues; struct futex_hash_bucket *queues[] __counted_by(nr_queues); } *__futex_data __ro_after_init;
Quoted 4 lines
with a variable length "queues" at the end if we want to ensure everything ends up in the same cacheline but all the
__futex_datamember access would then be pointer dereferencing which might not be ideal.
Here we would have also two pointers and I don't think it is worth it.
Quoted 1 line
Thoughts?
Having a statement that these machines are in the minority and not used by a wider range of people might convince Debian to lower the default. I haven't look into other distros but the MAXSMP on x86 will probably force the 10 there, too.
Especially if *those* machines are used only by Google/ Amazon/ Oracle and they use their own kernel and not the Debian one. Maybe it would work to hide it behind MAXNUMA and keep the default for x86 at 6. Looking around, the range is also 1…10 on arm64 and riscv, too. Looking into the configs I see
| boot/config-6.18.12+deb14-arm64:CONFIG_NODES_SHIFT=4 | boot/config-6.18.12+deb14-arm64-16k:CONFIG_NODES_SHIFT=4 | boot/config-6.18.12+deb14-loong64:CONFIG_NODES_SHIFT=6 | boot/config-6.18.12+deb14-powerpc64le:CONFIG_NODES_SHIFT=8 | boot/config-6.18.12+deb14-powerpc64le-64k:CONFIG_NODES_SHIFT=8 | boot/config-6.18.12+deb14-riscv64:CONFIG_NODES_SHIFT=2
While most look sane, loong64 looks odd as in an architecture this young already having 64 nodes by default. Not sure how much of this copy/ paste and how much is actual need.
Sebastian
Hello Sebastian,
Quoted 5 lines · Sebastian Andrzej Siewior
My question was initially is 1024 for max-nodes something that people really use. It was introduced as of
https://lore.kernel.org/all/[email protected]/but it looks odd. It might just one or two machines which are left :)
I have it on good faith that some EPYC user on distro kernels turn on "L3 as NUMA" option which currently results into 32 NUMA nodes on our largest configuration.
Adding a little bit more margin for CXL nodes should make even CONFIG_NODES_SHIFT=6 pretty sane default for most real-word configs. I don't think we can go more than 10 or so CXL nodes considering the number of PCIe lanes unless there are more creative ways to attach tiered memory that appear as a NUMA node.
I'm not sure if Intel has similar crazy combination but NODES_SHIFT=6 can accommodate (16 socket * SNC-3) + up to 16 CXL nodes so it should be fine for most distro users too?
Signature · 2 lines
Thanks and Regards, Prateek
Quoted 1 line · K Prateek Nayak
Hello Sebastian,
Hi Prateek,
Quoted 17 lines · Sebastian Andrzej Siewior
Quoted 5 lines
My question was initially is 1024 for max-nodes something that people really use. It was introduced as of
https://lore.kernel.org/all/[email protected]/but it looks odd. It might just one or two machines which are left :)
I have it on good faith that some EPYC user on distro kernels turn on "L3 as NUMA" option which currently results into 32 NUMA nodes on our largest configuration.
Adding a little bit more margin for CXL nodes should make even
CONFIG_NODES_SHIFT=6pretty sane default for most real-word configs. I don't think we can go more than 10 or so CXL nodes considering the number of PCIe lanes unless there are more creative ways to attach tiered memory that appear as a NUMA node.
Quoted 3 lines
I'm not sure if Intel has similar crazy combination but NODES_SHIFT=6 can accommodate (16 socket * SNC-3) + up to 16 CXL nodes so it should be fine for most distro users too?
Okay. According to Kconfig, this is the default for X86_64. The 10 gets set by MAXSMP. This option raises the NR_CPUS_DEFAULT to 8192. That might the overkill. What would be a sane value for NR_CPUS_DEFAULT? I don't have anything that exceeds 3 digits but I also don't have anything with more than 4 nodes ;)
Sebastian
Quoted 21 lines · Sebastian Andrzej Siewior
Quoted 1 line · K Prateek Nayak
Hello Sebastian,
Hi Prateek,
Quoted 17 lines · Sebastian Andrzej Siewior
Quoted 5 lines
My question was initially is 1024 for max-nodes something that people really use. It was introduced as of
https://lore.kernel.org/all/[email protected]/but it looks odd. It might just one or two machines which are left :)
I have it on good faith that some EPYC user on distro kernels turn on "L3 as NUMA" option which currently results into 32 NUMA nodes on our largest configuration.
Adding a little bit more margin for CXL nodes should make even
CONFIG_NODES_SHIFT=6pretty sane default for most real-word configs. I don't think we can go more than 10 or so CXL nodes considering the number of PCIe lanes unless there are more creative ways to attach tiered memory that appear as a NUMA node.
Quoted 7 lines
Quoted 3 lines
I'm not sure if Intel has similar crazy combination but NODES_SHIFT=6 can accommodate (16 socket * SNC-3) + up to 16 CXL nodes so it should be fine for most distro users too?
Okay. According to
Kconfig, this is the default forX86_64. The 10 gets set by MAXSMP. This option raises theNR_CPUS_DEFAULTto 8192. That might the overkill. What would be a sane value forNR_CPUS_DEFAULT?
I would have thought a quarter of that would be plenty but looking at the footnote in [1] that says "16 socket GNR system" and the fact that GNR can feature up to 256 threads per socket - that could theoretically put such systems at that NR_CPUS_DEFAULT limit - I don't know if it is practically possible.
[1] https://lore.kernel.org/lkml/[email protected]/
Still, I doubt such setup would practically cross more than 64 nodes.
Why was this selected as the default for MAXSMP? It came from [2] but I'm not really able to understand why other than this line in Mike's response:
"MAXSMP" represents what's really usable
so we just set it to the max of range to test for scalability? Seems little impractical for real-world cases but on the flip side if we don't sit it, some bits might not get enough testing?
[2] https://lore.kernel.org/lkml/[email protected]/
Quoted 2 lines
I don't have anything that exceeds 3 digits but I also don't have anything with more than 4 nodes ;)
And mine tops out at 32 nodes ;-)
Signature · 2 lines
Thanks and Regards, Prateek
On 2026-02-25 14:21:33 [+0530], K Prateek Nayak wrote:
Hi Prateek,
Quoted 9 lines
I would have thought a quarter of that would be plenty but looking at the footnote in [1] that says "16 socket GNR system" and the fact that GNR can feature up to 256 threads per socket - that could theoretically put such systems at that
NR_CPUS_DEFAULTlimit - I don't know if it is practically possible.[1] https://lore.kernel.org/lkml/[email protected]/
Still, I doubt such setup would practically cross more than 64 nodes.
I am still trying to figure out if this is practical or some drunk guys saying "you know what would be fun?"
Quoted 9 lines
Why was this selected as the default for MAXSMP? It came from [2] but I'm not really able to understand why other than this line in Mike's response:
"MAXSMP" represents what's really usable
so we just set it to the max of range to test for scalability? Seems little impractical for real-world cases but on the flip side if we don't sit it, some bits might not get enough testing?
Sounds like it. What would be sane default upper limit then? Something like 1024 CPUs? 2048? Or even more than that?
I would try to use this and convince Debian to drop MAXSMP and then lower NODES_SHIFT to default 6. I would need a default for NR_CPUS_DEFAULT without having people complaining about missing CPUs. Maybe we could get a sane default setting in kernel without testing limits.
Also probably will compile two kernels to see how much memory this safes in total since there should be other data structures depending on max CPUs/ NODEs.
Sebastian
Hey Sebastian,
Sorry for the delay!
Quoted 20 lines · Sebastian Andrzej Siewior
On 2026-02-25 14:21:33 [+0530], K Prateek Nayak wrote:
Hi Prateek,Quoted 9 lines
I would have thought a quarter of that would be plenty but looking at the footnote in [1] that says "16 socket GNR system" and the fact that GNR can feature up to 256 threads per socket - that could theoretically put such systems at that
NR_CPUS_DEFAULTlimit - I don't know if it is practically possible.[1] https://lore.kernel.org/lkml/[email protected]/
Still, I doubt such setup would practically cross more than 64 nodes.
I am still trying to figure out if this is practical or some drunk guys saying "you know what would be fun?"
Quoted 4 lines
Why was this selected as the default for MAXSMP? It came from [2] but I'm not really able to understand why other than this line in Mike's response:
Quoted 8 lines
Quoted 5 lines
"MAXSMP" represents what's really usable
so we just set it to the max of range to test for scalability? Seems little impractical for real-world cases but on the flip side if we don't sit it, some bits might not get enough testing?
Sounds like it. What would be sane default upper limit then? Something like 1024 CPUs? 2048? Or even more than that?
I feel the current default for NR_CPUS can be be retained as is just to be on the safer side.
Turns out QEMU allows for a ridiculous amount of vCPUs per guest and I've found enough evidence of extremely large guests running oversubscribed that sometimes run distro kernels :-(
Quoted 6 lines
I would try to use this and convince Debian to drop MAXSMP and then lower
NODES_SHIFTto default 6. I would need a default forNR_CPUS_DEFAULTwithout having people complaining about missing CPUs. Maybe we could get a sane default setting in kernel without testing limits.
*Theoretically* with SNC-3 and 16 sockets + CXL we can get close to the !MAXSMP limits for NODES_SHIFT (6) so perhaps we should drop it down a couple of notch from 10 as far as defaults are concerned to 8 - that should give us ample room for a long time in my opinion.
Folks who are doing *insane* NUMA emulation can perhaps explain the use case or resort to building a kernel with a non-default NODES_SHIFT.
Quoted 4 lines
Also probably will compile two kernels to see how much memory this safes in total since there should be other data structures depending on max CPUs/ NODEs.
To keep the configs as close as possible, I had to resort to selecting CONFIG_CPUMASK_OFFSTACK for !MAXSMP. Following was bloat-o-meter output with the reduced NODES_SHIFT on kernels built with very close to Ubuntu distro config:
o NODES_SHIFT=8 : Total: Before=33017117, After=32109495, chg -2.75% o NODES_SHIFT=6 : Total: Before=33017117, After=31930101, chg -3.29% o NODES_SHIFT=6; NR_CPUS=4k : Total: Before=33017117, After=31196664, chg -5.51% o NODES_SHIFT=6; NR_CPUS=2k : Total: Before=33017117, After=30829862, chg -6.62%
That last couple configs adds ARCH_SUPPORTS_KMAP_LOCAL_FORCE_MAP. If I remove that dependency , I don't really see any change to the bloat-o-meter results so I don't think it makes much of a difference.
Runtime memory consumption difference are within the noise range for me - I really couldn't see anything meaningful difference (or even a trend with multiple runs) between the extreme configs after boot. I haven't done any meaningful longer testing to pot anything.
I'll let you decide what is a good trade off between space saving and future headaches :-)
Signature · 2 lines
Thanks and Regards, Prateek
Quoted 1 line · K Prateek Nayak
Hey Sebastian,
Hi Prateek,
Quoted 1 line
Sorry for the delay!
No worries.
Quoted 10 lines · Sebastian Andrzej Siewior
Quoted 2 lines
Sounds like it. What would be sane default upper limit then? Something like 1024 CPUs? 2048? Or even more than that?
I feel the current default for
NR_CPUScan be be retained as is just to be on the safer side.Turns out QEMU allows for a ridiculous amount of vCPUs per guest and I've found enough evidence of extremely large guests running oversubscribed that sometimes run distro kernels :-(
You mean distro kernel in 8k CPUs guest? I do this kind of things for testing but not with a distro kernel. Oh well.
Quoted 2 lines
I'll let you decide what is a good trade off between space saving and future headaches :-)
So you are saying NODES_SHIFT=8 and NR_CPUS=4k is what should be default given "sane" upper limits as of today? I did hope for SHIFT 6 & NR=2k. Not sure this is worth fighting for.
Thank you.
Sebastian
Hello Sebastian,
Quoted 6 lines · Sebastian Andrzej Siewior
Quoted 6 lines
Quoted 2 lines
Sounds like it. What would be sane default upper limit then? Something like 1024 CPUs? 2048? Or even more than that?
I feel the current default for
NR_CPUScan be be retained as is just to be on the safer side.
Quoted 6 lines
Quoted 3 lines
Turns out QEMU allows for a ridiculous amount of vCPUs per guest and I've found enough evidence of extremely large guests running oversubscribed that sometimes run distro kernels :-(
You mean distro kernel in 8k CPUs guest? I do this kind of things for testing but not with a distro kernel. Oh well.
I bet there are interesting justifications with stuff like live migration, reliability, etc. but I haven't dared to ask!
Quoted 6 lines
Quoted 3 lines
I'll let you decide what is a good trade off between space saving and future headaches :-)
So you are saying NODES_SHIFT=8 and NR_CPUS=4k is what should be default given "sane" upper limits as of today?
Yup those seem sane in my opinion and amounts to a decent chunk of space saved.
Quoted 1 line
I did hope for SHIFT 6 & NR=2k. Not sure this is worth fighting for.
We leave a little buffer for insanity ;-)
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
reviewerQuoted 46 lines · K Prateek Nayak
CONFIG_NODES_SHIFT(which influencesMAX_NUMNODES) is often configured generously by distros while the actual number of possible NUMA nodes on most systems is often quite conservative.Instead of reserving
MAX_NUMNODESworth of space forfutex_queues, dynamically allocate it based on "nr_node_ids" at the time offutex_init()."
nr_node_ids" at the time offutex_init()is cached as "nr_futex_queues" to compensate for the extra dereference necessary to access the elements offutex_queueswhich ends up in a different cacheline now.Running 5 runs of perf bench futex showed no measurable impact for any variants on a dual socket 3rd generation AMD EPYC system (2 x 64C/128T):
variant locking/futex base + patch %diff
futex/hash 1220783.2 1333296.2 (9%) futex/wake 0.71186 0.72584 (2%) futex/wake-parallel 0.00624 0.00664 (6%) futex/requeue 0.25088 0.26102 (4%) futex/lock-pi 57.6 57.8 (0%)Note: futex/hash had noticeable run to run variance on test machine.
"
nr_node_ids" can rarely be larger thannum_possible_nodes()but the additional space allows for simpler handling of node index in presence of sparsenode_possible_map.Reported-by Sebastian Andrzej Siewior <[email protected]>Signed-off-by K Prateek Nayak <[email protected]>---
Sebastian,Does this work for your concerns with the large "
MAX_NUMNODES" values on most distros? It does put the "queues" into a separate cacheline from the__futex_data.The other option is to dynamically allocate the entire
__futex_dataas:struct { unsigned long hashmask; unsigned int hashshift; unsigned int nr_queues; struct futex_hash_bucket *queues[] __counted_by(nr_queues); } *__futex_data __ro_after_init;
Quoted 6 lines
with a variable length "queues" at the end if we want to ensure everything ends up in the same cacheline but all the
__futex_datamember access would then be pointer dereferencing which might not be ideal.Thoughts?
Both will result in at least one extra deref/cacheline for each futex op, no?
Hello Peter,
Quoted 52 lines · Peter Zijlstra
Quoted 51 lines · K Prateek Nayak
CONFIG_NODES_SHIFT(which influencesMAX_NUMNODES) is often configured generously by distros while the actual number of possible NUMA nodes on most systems is often quite conservative.Instead of reserving
MAX_NUMNODESworth of space forfutex_queues, dynamically allocate it based on "nr_node_ids" at the time offutex_init()."
nr_node_ids" at the time offutex_init()is cached as "nr_futex_queues" to compensate for the extra dereference necessary to access the elements offutex_queueswhich ends up in a different cacheline now.Running 5 runs of perf bench futex showed no measurable impact for any variants on a dual socket 3rd generation AMD EPYC system (2 x 64C/128T):
variant locking/futex base + patch %diff
futex/hash 1220783.2 1333296.2 (9%) futex/wake 0.71186 0.72584 (2%) futex/wake-parallel 0.00624 0.00664 (6%) futex/requeue 0.25088 0.26102 (4%) futex/lock-pi 57.6 57.8 (0%)Note: futex/hash had noticeable run to run variance on test machine.
"
nr_node_ids" can rarely be larger thannum_possible_nodes()but the additional space allows for simpler handling of node index in presence of sparsenode_possible_map.Reported-by Sebastian Andrzej Siewior <[email protected]>Signed-off-by K Prateek Nayak <[email protected]>---
Sebastian,Does this work for your concerns with the large "
MAX_NUMNODES" values on most distros? It does put the "queues" into a separate cacheline from the__futex_data.The other option is to dynamically allocate the entire
__futex_dataas:struct { unsigned long hashmask; unsigned int hashshift; unsigned int nr_queues; struct futex_hash_bucket *queues[] __counted_by(nr_queues); } *__futex_data __ro_after_init;with a variable length "queues" at the end if we want to ensure everything ends up in the same cacheline but all the
__futex_datamember access would then be pointer dereferencing which might not be ideal.
Quoted 4 lines
Quoted 1 line
Thoughts?
Both will result in at least one extra deref/cacheline for each futex op, no?
Ack but I was wondering if that penalty can be offset by the fact that we no longer need to look at "nr_node_ids" in a separate cacheline?
I ran futex bench enough time before posting to come to conclusion that there isn't any noticeable regression - the numbers swung either ways and I just took one set for comparison.
Sebastian and I have been having a more philosophical discussion on that CONFIG_NODES_SHIFT default but I guess as far as this patch is concerned, the conclusion is we want to avoid an extra dereference in the fast-path at the cost of a little bit extra space?
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
reviewerQuoted 6 lines · K Prateek Nayak
Quoted 2 lines
Both will result in at least one extra deref/cacheline for each futex op, no?
Ack but I was wondering if that penalty can be offset by the fact that we no longer need to look at "
nr_node_ids" in a separate cacheline?
Quoted 8 lines
I ran futex bench enough time before posting to come to conclusion that there isn't any noticeable regression - the numbers swung either ways and I just took one set for comparison.
Sebastian and I have been having a more philosophical discussion on that
CONFIG_NODES_SHIFTdefault but I guess as far as this patch is concerned, the conclusion is we want to avoid an extra dereference in the fast-path at the cost of a little bit extra space?
Ooh, I just remebered, I've always wanted to apply Linus' runtime-const stuff to the futex thing.
Something like the below. But I'm not sure if it actually makes a difference these days :/
But that can surely fix up the extra deref.
---
arch/x86/include/asm/runtime-const.h +14 -0
@@ -41,6 +41,15 @@ :"+r" (__ret)); \ __ret; }) +#define runtime_const_mask_32 (val, sym) ({ \ + typeof(0u+(val)) __ret = (val); \ + asm_inline("and $0x12345678, %k0\n1:\n" \ + ".pushsection runtime_mask_" #sym ",\"a\"\n\t"\ + ".long 1b - 4 - .\n" \ + ".popsection" \ + : "+r" (__ret)); \ + __ret; }) +#define runtime_const_init (type, sym) do { \ extern s32 __start_runtime_##type##_##sym[]; \ extern s32 __stop_runtime_##type##_##sym[]; \
@@ -65,6 +74,11 @@ static inline void __runtime_fixup_shift(void *where, unsigned long val) *(unsigned char *)where = val; } +static inline void __runtime_fixup_mask (void *where,unsigned long val) +{ + *(unsigned int *)where = val; +} +static inline void runtime_const_fixup (void (*fn)(void *,unsigned long ),unsigned long val,s32 *start,s32 *end) {
include/asm-generic/runtime-const.h +1 -0
@@ -10,6 +10,7 @@*/ #define runtime_const_ptr (sym) (sym)#define runtime_const_shift_right_32 (val, sym) ((u32)(val)>>(sym)) +#define runtime_const_mask_32 (val, sym) ((u32)(val)&(sym))#define runtime_const_init (type,sym) do { } while (0)#endif
include/asm-generic/vmlinux.lds.h +4 -1
@@ -973,7 +973,10 @@ RUNTIME_CONST(shift, d_hash_shift) \ RUNTIME_CONST(ptr, dentry_hashtable) \ RUNTIME_CONST(ptr, __dentry_cache) \ -RUNTIME_CONST (ptr, __names_cache) + RUNTIME_CONST(ptr, __names_cache) \ + RUNTIME_CONST(shift, __futex_shift) \ + RUNTIME_CONST(mask, __futex_mask) \ +RUNTIME_CONST (ptr, __futex_queues) /* Alignment must be consistent with (kunit_suite *) in include/kunit/test.h */#define KUNIT_TABLE () \
kernel/futex/core.c +20 -11
@@ -54,14 +54,17 @@* reside in the same cacheline. */ static struct { -unsigned long hashmask; -unsigned int hashshift;struct futex_hash_bucket *queues[MAX_NUMNODES ]; } __futex_data__read_mostly __aligned(2*sizeof(long)) ; -#define futex_hashmask (__futex_data.hashmask) -#define futex_hashshift (__futex_data.hashshift) -#define futex_queues (__futex_data.queues) +static u32 __futex_mask; +static u32 __futex_shift; +static struct futex_hash_bucket **__futex_queues; + +static __always_inline struct futex_hash_bucket **futex_queues(void) +{ +return runtime_const_ptr (__futex_queues); +}struct futex_private_hash {int state;
@@ -439,14 +442,14 @@ __futex_hash(union futex_key *key, struct futex_private_hash *fph)* NOTE: this isn't perfectly uniform, but it is fast and * handles sparse node masks. */ - node = (hash >> futex_hashshift) % nr_node_ids; + node =runtime_const_shift_right_32 (hash, __futex_shift) % nr_node_ids;if (!node_possible (node)) { node =find_next_bit_wrap (node_possible_map.bits, nr_node_ids, node); } } -return &futex_queues[node][hash & futex_hashmask]; +return &futex_queues ()[node][runtime_const_mask_32 (hash, __futex_mask)]; }/**
@@ -1913,7 +1916,7 @@ int futex_hash_allocate_default(void)* 16 <= threads * 4 <= global hash size */ buckets =roundup_pow_of_two (4 * threads); - buckets =clamp (buckets,16 , futex_hashmask +1 ); + buckets =clamp (buckets,16 , __futex_mask +1 );if (current_buckets >= buckets)return 0 ;
@@ -1983,10 +1986,17 @@ static int __init futex_init(void) hashsize =max (4 , hashsize); hashsize =roundup_pow_of_two (hashsize);#endif - futex_hashshift =ilog2 (hashsize); + __futex_mask = hashsize -1 ; + __futex_shift =ilog2 (hashsize); size =sizeof (struct futex_hash_bucket ) * hashsize; order =get_order (size); +void *__futex_queues = &__futex_data.queues; + +runtime_const_init (shift, __futex_shift); +runtime_const_init (mask, __futex_mask); +runtime_const_init (ptr, __futex_queues); +for_each_node (n) {struct futex_hash_bucket *table;
@@ -2000,10 +2010,9 @@ static int __init futex_init(void)for (i =0 ; i < hashsize; i++)futex_hash_bucket_init (&table[i],NULL ); - futex_queues[n] = table; +futex_queues ()[n] = table; } - futex_hashmask = hashsize -1 ;pr_info ("futex hash table entries: %lu (%lu bytes on %d NUMA nodes, total %lu KiB, %s).\n" , hashsize, size,num_possible_nodes (), size *num_possible_nodes () /1024 , order >MAX_PAGE_ORDER ?"vmalloc" :"linear" );
Quoted 2 lines · Peter Zijlstra
Ooh, I just remebered, I've always wanted to apply Linus' runtime-const stuff to the futex thing.
I wasn't aware we have this, I did want to do/ have something like this.
Need to look at this in detail but…
kernel/futex/core.c __futex_hash(union futex_key *key, struct futex_private_hash *fph) · line 445
Quoted 8 lines
kernel/futex/core.c +1
-1@@ -439,14 +442,14 @@ __futex_hash(union futex_key *key, struct futex_private_hash *fph)* NOTE: this isn't perfectly uniform, but it is fast and * handles sparse node masks. */ - node = (hash >> futex_hashshift) % nr_node_ids; + node =runtime_const_shift_right_32 (hash, __futex_shift) % nr_node_ids;
getting rid of that div here would be the next step. If we could round it up to the next pow2 then we could avoid it. But I remember it did not show up in bench as much as I was thinking it would.
kernel/futex/core.c __futex_hash(union futex_key *key, struct futex_private_hash *fph) · line 446
Quoted 1 line
kernel/futex/core.c +0
-0if (!node_possible (node)) {
Sebastian
Peter Zijlstra
reviewerQuoted 8 lines · Sebastian Andrzej Siewior
Quoted 2 lines · Peter Zijlstra
Ooh, I just remebered, I've always wanted to apply Linus' runtime-const stuff to the futex thing.
I wasn't aware we have this, I did want to do/ have something like this.
Need to look at this in detail but…
Quoted 12 lines
kernel/futex/core.c __futex_hash(union futex_key *key, struct futex_private_hash *fph) · line 445
Quoted 8 lines
kernel/futex/core.c +1
-1@@ -439,14 +442,14 @@ __futex_hash(union futex_key *key, struct futex_private_hash *fph)* NOTE: this isn't perfectly uniform, but it is fast and * handles sparse node masks. */ - node = (hash >> futex_hashshift) % nr_node_ids; + node =runtime_const_shift_right_32 (hash, __futex_shift) % nr_node_ids;getting rid of that div here would be the next step. If we could round it up to the next pow2 then we could avoid it. But I remember it did not show up in bench as much as I was thinking it would.
Right, modern x86 seems really rather good at division (unlike a few years ago).
But yes, it would be nice to do better there.
Hello Peter, Sebastian,
Quoted 12 lines · Peter Zijlstra
Quoted 10 lines · K Prateek Nayak
Quoted 2 lines
Both will result in at least one extra deref/cacheline for each futex op, no?
Ack but I was wondering if that penalty can be offset by the fact that we no longer need to look at "
nr_node_ids" in a separate cacheline?I ran futex bench enough time before posting to come to conclusion that there isn't any noticeable regression - the numbers swung either ways and I just took one set for comparison.
Quoted 7 lines
Quoted 4 lines
Sebastian and I have been having a more philosophical discussion on that
CONFIG_NODES_SHIFTdefault but I guess as far as this patch is concerned, the conclusion is we want to avoid an extra dereference in the fast-path at the cost of a little bit extra space?Ooh, I just remebered, I've always wanted to apply Linus' runtime-const stuff to the futex thing.
I had no clue this existed! Nifty.
Quoted 6 lines
Something like the below. But I'm not sure if it actually makes a difference these days :/
But that can surely fix up the extra deref.
[..snip..]
Review static int __init futex_init(void) · line 1994
Quoted 11 lines
(quoted diff) +3
-1@@ -1983,10 +1986,17 @@ static int __init futex_init(void) hashsize = max(4, hashsize); hashsize = roundup_pow_of_two(hashsize); #endif - futex_hashshift = ilog2(hashsize); + __futex_mask = hashsize - 1; + __futex_shift = ilog2(hashsize); size = sizeof(struct futex_hash_bucket) * hashsize; order = get_order(size); + void *__futex_queues = &__futex_data.queues;
For __futex_queues, can we instead do:
kernel/futex/core.c +3 -10
@@ -48,15 +48,6 @@#include "futex.h" #include "../locking/rtmutex_common.h" -/* -* The base of the bucket array and its size are always used together -* (after initialization only in futex_hash()), so ensure that they -* reside in the same cacheline. -*/ -static struct { -struct futex_hash_bucket *queues[MAX_NUMNODES ]; -} __futex_data__read_mostly __aligned(2*sizeof(long)) ; -static u32 __futex_mask;static u32 __futex_shift;static struct futex_hash_bucket **__futex_queues;
@@ -1991,12 +1982,14 @@ static int __init futex_init(void) size =sizeof (struct futex_hash_bucket ) * hashsize; order =get_order (size); -void *__futex_queues = &__futex_data.queues; + __futex_queues =kcalloc (nr_node_ids,sizeof (*__futex_queues),GFP_KERNEL );runtime_const_init (shift, __futex_shift);runtime_const_init (mask, __futex_mask);runtime_const_init (ptr, __futex_queues); +BUG_ON (!futex_queues ()); +for_each_node (n) {struct futex_hash_bucket *table;
---
My machine didn't crash right away on running perf bench futex so I'm assuming this works?
Sebastian, I haven't found any evidence of static data being interleaved across NUMA (at least on x86). Since kernel data is identity mapped, is it even possible for a static array to be allocated interleaved during boot unless the policy in the BIOS is set to interleaved?
If the static allocation is same as a kcalloc(GFP_KERNEL) from NUMA standpoint, is the above feasible?
Quoted 8 lines
(quoted diff) +5
-0+ + runtime_const_init(shift, __futex_shift); + runtime_const_init(mask, __futex_mask); + runtime_const_init(ptr, __futex_queues); + for_each_node(n) { struct futex_hash_bucket *table;
Signature · 2 lines
Thanks and Regards, Prateek