x86: spread tlb flush vector between nodes
PATCH 1/1 x86: spread tlb flush vector between nodes
Currently flush tlb vector allocation is based on below equation:
sender = smp_processor_id() % 8
This isn't optimal, CPUs from different node can have the same vector, this causes a lot of lock contention. Instead, we can assign the same vectors to CPUs from the same node, while different node has different vectors. This has below advantages:
a. if there is lock contention, the lock contention is between CPUs from one node. This should be much cheaper than the contention between nodes. b. completely avoid lock contention between nodes. This especially benefits kswapd, which is the biggest user of tlb flush, since kswapd sets its affinity to specific node.
In my test, this could reduce > 20% CPU overhead in extreme case.
--- arch/x86/mm/tlb.c | 47 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 46 insertions(+), 1 deletion(-)
arch/x86/mm/tlb.c +46 -1
@@ -5,6 +5,7 @@#include <linux/smp.h> #include <linux/interrupt.h> #include <linux/module.h> +#include <linux/cpu.h> #include <asm/tlbflush.h> #include <asm/mmu_context.h>
@@ -52,6 +53,8 @@want false sharing in the per cpu data segment. */ static union smp_flush_state flush_state[NUM_INVALIDATE_TLB_VECTORS ]; +static int tlb_vector_offset[NR_CPUS ]__read_mostly ; +/* * We cannot call mmdrop() because we are in interrupt context, * instead update mm->cpu_vm_mask.
@@ -173,7 +176,7 @@union smp_flush_state *f;/* Caller has disabled preemption */ - sender =smp_processor_id () %NUM_INVALIDATE_TLB_VECTORS ; + sender = tlb_vector_offset[smp_processor_id ()]; f = &flush_state[sender];/*
@@ -218,6 +221,46 @@flush_tlb_others_ipi (cpumask, mm, va); } +static void __cpuinit calculate_tlb_offset (void ) +{ +int cpu, node, nr_node_vecs; +/* +* we are changing tlb_vector_offset[] for each CPU in runtime, but this +* will not cause inconsistency, as the write is atomic under X86. we +* might see more lock contentions in a short time, but after all CPU's +* tlb_vector_offset[] are changed, everything should go normal +* +* Note: if NUM_INVALIDATE_TLB_VECTORS % nr_online_nodes !=0, we might +* waste some vectors. +**/ +if (nr_online_nodes >NUM_INVALIDATE_TLB_VECTORS ) + nr_node_vecs =1 ; +else + nr_node_vecs =NUM_INVALIDATE_TLB_VECTORS /nr_online_nodes; + +for_each_online_node (node) { +int node_offset = (node %NUM_INVALIDATE_TLB_VECTORS ) * + nr_node_vecs; +int cpu_offset =0 ; +for_each_cpu (cpu,cpumask_of_node (node)) { + tlb_vector_offset[cpu] = node_offset + cpu_offset; + cpu_offset++; + cpu_offset = cpu_offset % nr_node_vecs; + } + } +} + +static int tlb_cpuhp_notify (struct notifier_block *n, +unsigned long action,void *hcpu) +{ +switch (action &0xf ) { +case CPU_ONLINE : +case CPU_DEAD : +calculate_tlb_offset (); + } +return NOTIFY_OK ; +} +static int __cpuinit init_smp_flush (void ) {int i;
@@ -225,6 +268,8 @@for (i =0 ; i <ARRAY_SIZE (flush_state); i++)raw_spin_lock_init (&flush_state[i].tlbstate_lock); +calculate_tlb_offset (); +hotcpu_notifier (tlb_cpuhp_notify,0 );return 0 ; }core_initcall (init_smp_flush);
On Wed, Oct 13, 2010 at 03:41:38PM +0800, Shaohua Li wrote:
Hi Shaohua,
Quoted 11 lines
Currently flush tlb vector allocation is based on below equation:
sender =smp_processor_id()% 8
This isn't optimal, CPUs from different node can have the same vector, this causes a lot of lock contention. Instead, we can assign the same vectors to CPUs from the same node, while different node has different vectors. This has below advantages:
a. if there is lock contention, the lock contention is between CPUs from one node. This should be much cheaper than the contention between nodes. b. completely avoid lock contention between nodes. This especially benefits kswapd, which is the biggest user of tlb flush, since kswapd sets its affinity to specific node.
The original scheme with 8 vectors was designed when Linux didn't have per CPU interrupt numbers yet, and interrupts vectors were a scarce resource.
Now that we have per CPU interrupts and there is no immediate danger of running out I think it's better to use more than 8 vectors for the TLB flushes.
Perhaps could use 32 vectors or so and give each node on a 8S system 4 slots and on a 4 node system 8 slots?
Quoted 1 line
In my test, this could reduce > 20% CPU overhead in extreme case.
Nice result.
arch/x86/mm/tlb.c line 261
Quoted 10 lines
arch/x86/mm/tlb.c +10
-0+ +static int tlb_cpuhp_notify (struct notifier_block *n, +unsigned long action,void *hcpu) +{ +switch (action &0xf ) { +case CPU_ONLINE : +case CPU_DEAD : +calculate_tlb_offset (); + } +return NOTIFY_OK ;
I don't think we really need the complexity of a notifier here. In most x86 setups possible is very similar to online.
So I would suggest simply to compute a static mapping at boot and simplify the code.
In theory there is a slight danger of node<->CPU numbers changing with consecutive hot plug actions, but right now this should not happen anyways and it would be unlikely later.
-Andi
Quoted 19 lines · Andi Kleen
On Wed, Oct 13, 2010 at 03:41:38PM +0800, Shaohua Li wrote:
Hi Shaohua,
Quoted 11 lines
Currently flush tlb vector allocation is based on below equation:
sender =smp_processor_id()% 8
This isn't optimal, CPUs from different node can have the same vector, this causes a lot of lock contention. Instead, we can assign the same vectors to CPUs from the same node, while different node has different vectors. This has below advantages:
a. if there is lock contention, the lock contention is between CPUs from one node. This should be much cheaper than the contention between nodes. b. completely avoid lock contention between nodes. This especially benefits kswapd, which is the biggest user of tlb flush, since kswapd sets its affinity to specific node.The original scheme with 8 vectors was designed when Linux didn't have per CPU interrupt numbers yet, and interrupts vectors were a scarce resource.
Quoted 6 lines
Now that we have per CPU interrupts and there is no immediate danger of running out I think it's better to use more than 8 vectors for the TLB flushes.
Perhaps could use 32 vectors or so and give each node on a 8S system 4 slots and on a 4 node system 8 slots?
Haven't too much idea. Before we have per CPU interrupts, muti vector msi-x isn't widely deployed. Thought we need data if this is really required.
Quoted 14 lines
arch/x86/mm/tlb.c line 261
Quoted 10 lines
arch/x86/mm/tlb.c +10
-0+ +static int tlb_cpuhp_notify (struct notifier_block *n, +unsigned long action,void *hcpu) +{ +switch (action &0xf ) { +case CPU_ONLINE : +case CPU_DEAD : +calculate_tlb_offset (); + } +return NOTIFY_OK ;I don't think we really need the complexity of a notifier here. In most x86 setups possible is very similar to online.
Quoted 7 lines
So I would suggest simply to compute a static mapping at boot and simplify the code.
In theory there is a slight danger of node<->CPU numbers changing with consecutive hot plug actions, but right now this should not happen anyways and it would be unlikely later.
yes, it's unlikely. could we get the node info for a CPU before it's hotplugged? Anyway, this doesn't take overhead.
Thanks,
Shaohua
Quoted 19 lines · Shaohua Li
Quoted 18 lines · Andi Kleen
arch/x86/mm/tlb.c line 261
Quoted 10 lines · Shaohua Li
arch/x86/mm/tlb.c +10
-0+ +static int tlb_cpuhp_notify (struct notifier_block *n, +unsigned long action,void *hcpu) +{ +switch (action &0xf ) { +case CPU_ONLINE : +case CPU_DEAD : +calculate_tlb_offset (); + } +return NOTIFY_OK ;I don't think we really need the complexity of a notifier here. In most x86 setups possible is very similar to online.
So I would suggest simply to compute a static mapping at boot and simplify the code.
Quoted 7 lines
Quoted 4 lines
In theory there is a slight danger of node<->CPU numbers changing with consecutive hot plug actions, but right now this should not happen anyways and it would be unlikely later.
yes, it's unlikely. could we get the node info for a CPU before it's hotplugged? Anyway, this doesn't take overhead.
It would be rather stupid to throw away the fairly simple hotplug-aware code you wrote and replace it with some lame boot-time calculated mapping just because currently it's considered rare.
Thanks,
Ingo
Quoted 24 lines · Shaohua Li
Quoted 23 lines · Andi Kleen
On Wed, Oct 13, 2010 at 03:41:38PM +0800, Shaohua Li wrote:
Hi Shaohua,
Quoted 11 lines
Currently flush tlb vector allocation is based on below equation:
sender =smp_processor_id()% 8
This isn't optimal, CPUs from different node can have the same vector, this causes a lot of lock contention. Instead, we can assign the same vectors to CPUs from the same node, while different node has different vectors. This has below advantages:
a. if there is lock contention, the lock contention is between CPUs from one node. This should be much cheaper than the contention between nodes. b. completely avoid lock contention between nodes. This especially benefits kswapd, which is the biggest user of tlb flush, since kswapd sets its affinity to specific node.The original scheme with 8 vectors was designed when Linux didn't have per CPU interrupt numbers yet, and interrupts vectors were a scarce resource.
Now that we have per CPU interrupts and there is no immediate danger of running out I think it's better to use more than 8 vectors for the TLB flushes.
Quoted 5 lines
Quoted 2 lines
Perhaps could use 32 vectors or so and give each node on a 8S system 4 slots and on a 4 node system 8 slots?
Haven't too much idea. Before we have per CPU interrupts, muti vector msi-x isn't widely deployed. Thought we need data if this is really required.
looks there are still some overhead with total 8 vectors in a big machine. I'll try the 32 vectors as you suggested. I'll send separate patches out to address the 32 vectors issue. Can we merge this patch first?
Thanks,
Shaohua
H. Peter Anvin
reviewerTechnically, it is way too late for anything new in this merge window, but we can try to make a reasonable assessment of the risk since the merge window got delayed. However, this close to the merge window you cannot just expect to be merged even if the patch itself is OK.
Quoted 38 lines · Shaohua Li
Quoted 24 lines · Shaohua Li
Quoted 23 lines · Andi Kleen
On Wed, Oct 13, 2010 at 03:41:38PM +0800, Shaohua Li wrote:
Hi Shaohua,
Quoted 11 lines
Currently flush tlb vector allocation is based on below equation:
sender =smp_processor_id()% 8
This isn't optimal, CPUs from different node can have the same vector, this causes a lot of lock contention. Instead, we can assign the same vectors to CPUs from the same node, while different node has different vectors. This has below advantages:
a. if there is lock contention, the lock contention is between CPUs from one node. This should be much cheaper than the contention between nodes. b. completely avoid lock contention between nodes. This especially benefits kswapd, which is the biggest user of tlb flush, since kswapd sets its affinity to specific node.The original scheme with 8 vectors was designed when Linux didn't have per CPU interrupt numbers yet, and interrupts vectors were a scarce resource.
Now that we have per CPU interrupts and there is no immediate danger of running out I think it's better to use more than 8 vectors for the TLB flushes.
Quoted 5 lines
Quoted 2 lines
Perhaps could use 32 vectors or so and give each node on a 8S system 4 slots and on a 4 node system 8 slots?
Haven't too much idea. Before we have per CPU interrupts, muti vector msi-x isn't widely deployed. Thought we need data if this is really required.
looks there are still some overhead with total 8 vectors in a big machine. I'll try the 32 vectors as you suggested. I'll send separate patches out to address the 32 vectors issue. Can we merge this patch first?
Thanks,
Shaohua
Signature · 1 line
Sent from my mobile phone. Please pardon any lack of formatting.
Quoted 4 lines · H. Peter Anvin
Technically, it is way too late for anything new in this merge window, but we can try to make a reasonable assessment of the risk since the merge window got delayed. However, this close to the merge window you cannot just expect to be merged even if the patch itself is OK.
a prompt re-send of the patch today-ish, with proper changelog, etc. and with the new tuning in place is definitely a must.
Ingo
Quoted 9 lines · Ingo Molnar
Quoted 4 lines · H. Peter Anvin
Technically, it is way too late for anything new in this merge window, but we can try to make a reasonable assessment of the risk since the merge window got delayed. However, this close to the merge window you cannot just expect to be merged even if the patch itself is OK.
a prompt re-send of the patch today-ish, with proper changelog, etc. and with the new tuning in place is definitely a must.
the previous patch has changelog. what did you mean a new tuning?
Quoted 8 lines · Shaohua Li
Quoted 7 lines · Ingo Molnar
Quoted 4 lines · H. Peter Anvin
Technically, it is way too late for anything new in this merge window, but we can try to make a reasonable assessment of the risk since the merge window got delayed. However, this close to the merge window you cannot just expect to be merged even if the patch itself is OK.
Quoted 4 lines
Quoted 2 lines
a prompt re-send of the patch today-ish, with proper changelog, etc. and with the new tuning in place is definitely a must.
the previous patch has changelog. what did you mean a new tuning?
The new tuning would be the 8->32 patch - but that would be a more complex and separate (and definitely controversial) patch anyway.
So if hpa gives his ack we can try this current spread-tlb-vectors-better patch in -tip and see how it fares. Could you please update the changelog to specify the 20% improvement more precisely? What kind of workload was used and how was the improvement measured?
Thanks,
Ingo
Quoted 10 lines · Ingo Molnar
Quoted 8 lines · Shaohua Li
Quoted 7 lines · Ingo Molnar
Quoted 4 lines · H. Peter Anvin
Technically, it is way too late for anything new in this merge window, but we can try to make a reasonable assessment of the risk since the merge window got delayed. However, this close to the merge window you cannot just expect to be merged even if the patch itself is OK.
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
a prompt re-send of the patch today-ish, with proper changelog, etc. and with the new tuning in place is definitely a must.
the previous patch has changelog. what did you mean a new tuning?
The new tuning would be the 8->32 patch - but that would be a more complex and separate (and definitely controversial) patch anyway.
Yes, I'm working on it. And it hasn't too many relation with this patch.
Quoted 4 lines
So if hpa gives his ack we can try this current spread-tlb-vectors-better patch in -tip and see how it fares. Could you please update the changelog to specify the 20% improvement more precisely? What kind of workload was used and how was the improvement measured?
Below is the updated patch which describes the workload I use.
Currently flush tlb vector allocation is based on below equation:
sender = smp_processor_id() % 8
This isn't optimal, CPUs from different node can have the same vector, this causes a lot of lock contention. Instead, we can assign the same vectors to CPUs from the same node, while different node has different vectors. This has below advantages:
a. if there is lock contention, the lock contention is between CPUs from one node. This should be much cheaper than the contention between nodes. b. completely avoid lock contention between nodes. This especially benefits kswapd, which is the biggest user of tlb flush, since kswapd sets its affinity to specific node.
In my test, this could reduce > 20% CPU overhead in extreme case. The test machine has 4 nodes and each node has 16 CPUs. I then bind each node's kswapd to the first CPU of the node. I run a workload with 4 sequential mmap file read thread. The files are empty sparse file. This workload will trigger a lot of page reclaim and tlbflush. The kswapd bind is to easy trigger the extreme tlb flush lock contention because otherwise kswapd keeps migrating between CPUs of a node and I can't get stable result. Sure in real workload, we can't always see so big tlb flush lock contention, but it's possible.
--- arch/x86/mm/tlb.c | 47 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 46 insertions(+), 1 deletion(-)
arch/x86/mm/tlb.c +46 -1
@@ -5,6 +5,7 @@#include <linux/smp.h> #include <linux/interrupt.h> #include <linux/module.h> +#include <linux/cpu.h> #include <asm/tlbflush.h> #include <asm/mmu_context.h>
@@ -52,6 +53,8 @@want false sharing in the per cpu data segment. */ static union smp_flush_state flush_state[NUM_INVALIDATE_TLB_VECTORS ]; +static int tlb_vector_offset[NR_CPUS ]__read_mostly ; +/* * We cannot call mmdrop() because we are in interrupt context, * instead update mm->cpu_vm_mask.
@@ -173,7 +176,7 @@union smp_flush_state *f;/* Caller has disabled preemption */ - sender =smp_processor_id () %NUM_INVALIDATE_TLB_VECTORS ; + sender = tlb_vector_offset[smp_processor_id ()]; f = &flush_state[sender];/*
@@ -218,6 +221,46 @@flush_tlb_others_ipi (cpumask, mm, va); } +static void __cpuinit calculate_tlb_offset (void ) +{ +int cpu, node, nr_node_vecs; +/* +* we are changing tlb_vector_offset[] for each CPU in runtime, but this +* will not cause inconsistency, as the write is atomic under X86. we +* might see more lock contentions in a short time, but after all CPU's +* tlb_vector_offset[] are changed, everything should go normal +* +* Note: if NUM_INVALIDATE_TLB_VECTORS % nr_online_nodes !=0, we might +* waste some vectors. +**/ +if (nr_online_nodes >NUM_INVALIDATE_TLB_VECTORS ) + nr_node_vecs =1 ; +else + nr_node_vecs =NUM_INVALIDATE_TLB_VECTORS /nr_online_nodes; + +for_each_online_node (node) { +int node_offset = (node %NUM_INVALIDATE_TLB_VECTORS ) * + nr_node_vecs; +int cpu_offset =0 ; +for_each_cpu (cpu,cpumask_of_node (node)) { + tlb_vector_offset[cpu] = node_offset + cpu_offset; + cpu_offset++; + cpu_offset = cpu_offset % nr_node_vecs; + } + } +} + +static int tlb_cpuhp_notify (struct notifier_block *n, +unsigned long action,void *hcpu) +{ +switch (action &0xf ) { +case CPU_ONLINE : +case CPU_DEAD : +calculate_tlb_offset (); + } +return NOTIFY_OK ; +} +static int __cpuinit init_smp_flush (void ) {int i;
@@ -225,6 +268,8 @@for (i =0 ; i <ARRAY_SIZE (flush_state); i++)raw_spin_lock_init (&flush_state[i].tlbstate_lock); +calculate_tlb_offset (); +hotcpu_notifier (tlb_cpuhp_notify,0 );return 0 ; }core_initcall (init_smp_flush);
Quoted 2 lines
+static int tlb_vector_offset[NR_CPUS]
__read_mostly;
Never use NR_CPUS. Always use per cpu data.
Otherwise you waste a lot of space on a CONFIG_MAX_SMP kernel running on a smaller box.
-Andi
Quoted 7 lines · Andi Kleen
Quoted 2 lines
+static int tlb_vector_offset[NR_CPUS]
__read_mostly;Never use
NR_CPUS. Always use per cpu data.Otherwise you waste a lot of space on a
CONFIG_MAX_SMPkernel running on a smaller box.
ha, I want it to be __read_mostly to avoid cache pollution, apparently we have no per cpu API to do this. Maybe I need add one.
Thanks,
Shaohua
H. Peter Anvin
reviewerQuoted 11 lines · Shaohua Li
Quoted 7 lines · Andi Kleen
Quoted 2 lines
+static int tlb_vector_offset[NR_CPUS]
__read_mostly;Never use
NR_CPUS. Always use per cpu data.Otherwise you waste a lot of space on a
CONFIG_MAX_SMPkernel running on a smaller box.ha, I want it to be
__read_mostlyto avoid cache pollution, apparently we have no per cpu API to do this. Maybe I need add one.
Quite possible, however, definitely percpu over a static array.
-hpa
Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf.