VMA lookup with RCU
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): 20070918205419.60d24da7@lappy
A message that is not in the archive (sent off-list or not yet received): 1191436672.7103.38.camel@alexis
Quoted 6 lines · Alexis Bruemmer
Hi Peter,
Some colleagues and I have been looking at how best to implement your latest suggestions for the VMA lookup with RCU patches, however we have some questions:
Quoted 8 lines
<snip>
Quoted 4 lines
My current plan for these patches is:
Fine grain lock the update side of the B+tree
do a per-node vma reference, so that vma lookup and lock is:How did you envision the implementation here? More specifically, what is the best way to get local copies of B+trees on each node?
Don't copy the whole trees, just keep references to vma's locally. Saves a lot of traffic:
struct vm_area_struct {
... struct rw_semaphore lock; atomic_t refs; };
struct vma_ref {
struct vm_area_struct *vma;
struct rw_semaphore lock;
int dead;
};struct vma_ref *find_get_vma(struct mm_struct *mm, unsigned long addr)
{
struct vm_area_struct *vma;
struct vma_ref *ref = NULL;again:
rcu_read_lock();
vma = btree_find(&mm->btree, addr);
if (!vma)
goto out_unlock;
ref = btree_find(node_local_tree(), (unsigned long)vma);
if (!ref) {
BTREE_LOCK_CONTEXT(ctx, node_local_tree()); /* see fine grain locked RADIX tree */
down_read(&vma->lock);
if (atomic_read(&vma->refs) < 0) {
/* vma got destroyed */
up_read(&vma->lock);
goto out_unlock;
}
atomic_inc(&vma->refs);
rcu_read_unlock(); /* we got vma->lock, can't escape */
ref = kmalloc(sizeof(*ref), GFP_KERNEL);
/* XXX: what to do when fails */
ref->vma = vma;
init_rwsem(&ref->mutex);
ref->dead = 0;
ret = btree_insert(ctx, (unsigned long)vma, ref);
if (ret = -EEXIST) {
kfree(ref);
goto again;
}
}
down_read(&ref->lock);
if (ref->dead) {
up_read(&ref->lock);
rcu_read_unlock();
goto again;
}out_unlock:
rcu_read_unlock(); out: return ref; }
Something like that, it got big holes in it, but should illustrate the idea. We index the local reference by the vma address.
Quoted 6 lines
Quoted 6 lines
lookup in node local tree
if found, take read lock on local reference
if not-found, do global lookup, lock vma, take reference,
insert reference into local tree, take read lock on it, drop vma lock
Quoted 8 lines
Quoted 8 lines
write lock on the vma would:
find the vma in the global tree, lock it enqueue work items in a waitqueue that,
find the local ref, lock it (might sleep) release the reference, unlock and clear from local tree signal completion
once all nodes have completed we have no outstanding refs and since we have the lock, we're exclusive.
void invalidate_vma_refs(void *addr)
{
BTREE_LOCK_CONTEXT(ctx, node_local_tree());
rcu_read_lock();
ref = btree_find(node_local_tree, (unsigned long)addr);
if (!ref)
goto out_unlock;
down_write(&ref->lock); /* no more local refs */
ref->dead = 1;
atomic_dec(&ref->vma->refs); /* release */
btree_delete(ctx, (unsigned long)addr); /* unhook */
rcu_call(free_vma_ref, ref); /* destroy */
up_write(&ref->lock);out_unlock:
rcu_read_unlock(); }
struct vm_area_struct *write_lock_vma(struct mm *mm, unsigned long addr)
{
rcu_read_lock();
vma = btree_find(&mm->btree, addr);
if (!vma)
goto out_unlock;
down_write(&vma->lock); /* no new refs */
rcu_read_unlock();
schedule_on_each_cpu(invalidate_vma_refs, vma, 0, 1);
return vma;out_unlock:
rcu_read_unlock(); return NULL; }
Quoted 2 lines
Some general questions:
How does a process and vma know what node it's on?
numa_node_id() ?
just return the ref object, and unlock against that.
Quoted 4 lines
Also, as we discussed before the initial test results on the first set of these patches showed really no improvement in performance over the vanilla kernel. What kind of performance gains to you predict with this new fine grain lock approach?
Really no idea, the write side is rather heavy, it would need to invalidate (unsigned long)vma on all cpu's (perhaps track a cpumask of cpu's that did take a reference). The advantage is that its per vma, not per mm.
Quoted 3 lines
Finally many local kernel hackers that I have spoke with about this idea have expressed great interest in your patch set. Do you have any objections to opening this discussion up to linux-mm?
done :-)
Quoted 1 line
Thank you again for your time and help,
no problem at all.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 80 lines · Peter Zijlstra
Quoted 6 lines · Alexis Bruemmer
Hi Peter,
Some colleagues and I have been looking at how best to implement your latest suggestions for the VMA lookup with RCU patches, however we have some questions:
Quoted 8 lines
<snip>
Quoted 4 lines
My current plan for these patches is:
Fine grain lock the update side of the B+tree
do a per-node vma reference, so that vma lookup and lock is:How did you envision the implementation here? More specifically, what is the best way to get local copies of B+trees on each node?
Don't copy the whole trees, just keep references to vma's locally. Saves a lot of traffic:
struct
vm_area_struct{... struct rw_semaphore lock; atomic_t refs; };struct vma_ref { struct vm_area_struct *vma; struct rw_semaphore lock; int dead; };struct
vma_ref*find_get_vma(struct mm_struct *mm, unsigned long addr){ struct vm_area_struct *vma; struct vma_ref *ref = NULL;again:
rcu_read_lock(); vma = btree_find(&mm->btree, addr); if (!vma) goto out_unlock; ref = btree_find(node_local_tree(), (unsigned long)vma); if (!ref) { BTREE_LOCK_CONTEXT(ctx, node_local_tree()); /* see fine grain locked RADIX tree */ down_read(&vma->lock); if (atomic_read(&vma->refs) < 0) { /* vma got destroyed */ up_read(&vma->lock); goto out_unlock; } atomic_inc(&vma->refs); rcu_read_unlock(); /* we got vma->lock, can't escape */ ref = kmalloc(sizeof(*ref), GFP_KERNEL); /* XXX: what to do when fails */ ref->vma = vma; init_rwsem(&ref->mutex); ref->dead = 0; ret = btree_insert(ctx, (unsigned long)vma, ref); if (ret = -EEXIST) { kfree(ref); goto again; } } down_read(&ref->lock); if (ref->dead) { up_read(&ref->lock); rcu_read_unlock(); goto again; }
Quoted 5 lines
out_unlock:rcu_read_unlock(); out: return ref; }
Hmm, biggest problem I now realize is that we can freely schedule around, and the up_read() on ref->lock can happen from anywhere :-/
that will pretty much destroy all the good we got from the lookup locality.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 50 lines · Peter Zijlstra
Quoted 6 lines
Quoted 6 lines
lookup in node local tree
if found, take read lock on local reference
if not-found, do global lookup, lock vma, take reference,
insert reference into local tree, take read lock on it, drop vma lockQuoted 8 lines
Quoted 8 lines
write lock on the vma would:
find the vma in the global tree, lock it enqueue work items in a waitqueue that,
find the local ref, lock it (might sleep) release the reference, unlock and clear from local tree signal completion
once all nodes have completed we have no outstanding refs and since we have the lock, we're exclusive.void
invalidate_vma_refs(void *addr){ BTREE_LOCK_CONTEXT(ctx, node_local_tree()); rcu_read_lock(); ref = btree_find(node_local_tree, (unsigned long)addr); if (!ref) goto out_unlock; down_write(&ref->lock); /* no more local refs */ ref->dead = 1; atomic_dec(&ref->vma->refs); /* release */ btree_delete(ctx, (unsigned long)addr); /* unhook */ rcu_call(free_vma_ref, ref); /* destroy */ up_write(&ref->lock);
out_unlock:rcu_read_unlock(); }struct
vm_area_struct*write_lock_vma(struct mm *mm, unsigned long addr){ rcu_read_lock(); vma = btree_find(&mm->btree, addr); if (!vma) goto out_unlock; down_write(&vma->lock); /* no new refs */ rcu_read_unlock(); schedule_on_each_cpu(invalidate_vma_refs, vma, 0, 1); return vma;
Quoted 6 lines
out_unlock:rcu_read_unlock(); return NULL; }
Hi Peter,
Making node local copies of VMA is a good idea to reduce inter-node traffic, but the cost of search and delete is very high. Also, as you have pointed out, if the atomic operations happen on remote node due to scheduler migrating our thread, then all the cycles saved may be lost.
In find_get_vma() cross node traffic is due to btree traversal or the actual VMA object reference? Can we look at duplicating the btree structure per node and have VMA structures just one copy and make all btrees in each node point to the same vma object. This will make write operation and deletion of btree entries on all nodes little simple. All VMA lists will be unique and not duplicated.
Another related idea is to move the VMA object to node local memory. Can we migrate the VMA object to the node where it is referenced the most? We still maintain only _one_ copy of VMA object. No data duplication, but we can move the memory around to make it node local.
Some more thoughts:
Pagefault handler does most of the find_get_vma() to validate user address and then create page table entries (allocate page frames)... can we make the page fault handler run on the node where the VMAs have been allocated?
The CPU that has page-faulted need not necessarily do all the find_vma()
calls and update the page table. The process can sleep while another CPU _near_ to the memory containing VMAs and pagetable can do the job with local memory references.
I don't know if the page tables for the faulting process is allocated in node local memory.
Per CPU last vma cache: Currently we have the last vma referenced in a one entry cache in mm_struct. Can we have this cache per CPU or per node so that a multi threaded application can have node/cpu local cache of last vma referenced. This may reduce btree/rbtree traversal. Let the hardware cache maintain the corresponding VMA object and its coherency.
Please let me know your comment and thoughts.
Thanks,
Vaidy
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 60 lines · Vaidyanathan Srinivasan
Quoted 50 lines · Peter Zijlstra
Quoted 6 lines
Quoted 6 lines
lookup in node local tree
if found, take read lock on local reference
if not-found, do global lookup, lock vma, take reference,
insert reference into local tree, take read lock on it, drop vma lockQuoted 8 lines
Quoted 8 lines
write lock on the vma would:
find the vma in the global tree, lock it enqueue work items in a waitqueue that,
find the local ref, lock it (might sleep) release the reference, unlock and clear from local tree signal completion
once all nodes have completed we have no outstanding refs and since we have the lock, we're exclusive.void
invalidate_vma_refs(void *addr){ BTREE_LOCK_CONTEXT(ctx, node_local_tree()); rcu_read_lock(); ref = btree_find(node_local_tree, (unsigned long)addr); if (!ref) goto out_unlock; down_write(&ref->lock); /* no more local refs */ ref->dead = 1; atomic_dec(&ref->vma->refs); /* release */ btree_delete(ctx, (unsigned long)addr); /* unhook */ rcu_call(free_vma_ref, ref); /* destroy */ up_write(&ref->lock);
out_unlock:rcu_read_unlock(); }struct
vm_area_struct*write_lock_vma(struct mm *mm, unsigned long addr){ rcu_read_lock(); vma = btree_find(&mm->btree, addr); if (!vma) goto out_unlock; down_write(&vma->lock); /* no new refs */ rcu_read_unlock(); schedule_on_each_cpu(invalidate_vma_refs, vma, 0, 1); return vma;Quoted 6 lines
out_unlock:rcu_read_unlock(); return NULL; }Hi Peter,
Quoted 7 lines
Making node local copies of VMA is a good idea to reduce inter-node traffic, but the cost of search and delete is very high. Also, as you have pointed out, if the atomic operations happen on remote node due to scheduler migrating our thread, then all the cycles saved may be lost.
In
find_get_vma()cross node traffic is due to btree traversal or the actual VMA object reference?
Not sure, I'm not sure how to profile cacheline transfers.
The outlined approach would try to keep all accesses read-only, so that the cacheline can be shared. But yeah, once it get evicted it needs to be re-transfered.
Quoted 5 lines
Can we look at duplicating the btree
structure per node and have VMA structures just one copy and make all btrees in each node point to the same vma object. This will make write operation and deletion of btree entries on all nodes little simple. All VMA lists will be unique and not duplicated.
But that would end up with a 2d tree, (mm, vma) in which you can try to find an exact match for a given (mm, address) key.
Trouble with multi-dimensional trees is the balancing thing, afaik its an np-hard problem.
Quoted 4 lines
Another related idea is to move the VMA object to node local memory. Can we migrate the VMA object to the node where it is referenced the most? We still maintain only _one_ copy of VMA object. No data duplication, but we can move the memory around to make it node local.
I guess we can do that, is you take the vma lock in exclusive mode, you can make a copy of the object, replace the tree pointer, mark the old one dead (so that rcu lookups with re-try) and rcu_free the old one.
Quoted 5 lines
Some more thoughts:
Pagefault handler does most of the
find_get_vma()to validate user address and then create page table entries (allocate page frames)... can we make the page fault handler run on the node where the VMAs have been allocated?
explicit migration - like migrate_disable() - make load balancing a very hard problem.
Quoted 4 lines
The CPU that has page-faulted need not necessarily do all the
find_vma()
calls and update the page table. The process can sleep while another CPU _near_ to the memory containing VMAs and pagetable can do the job with local memory references.
would we not end up with remote page tables?
Quoted 10 lines
I don't know if the page tables for the faulting process is allocated in node local memory.
Per CPU last vma cache: Currently we have the last vma referenced in a one entry cache in
mm_struct. Can we have this cache per CPU or per node so that a multi threaded application can have node/cpu local cache of last vma referenced. This may reduce btree/rbtree traversal. Let the hardware cache maintain the corresponding VMA object and its coherency.Please let me know your comment and thoughts.
Nick Piggin (and I think Eric Dumazet) had nice patches for this. I think they were posted in the private futex thread.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 8 lines · Peter Zijlstra
Quoted 6 lines · Vaidyanathan Srinivasan
Per CPU last vma cache: Currently we have the last vma referenced in a one entry cache in
mm_struct. Can we have this cache per CPU or per node so that a multi threaded application can have node/cpu local cache of last vma referenced. This may reduce btree/rbtree traversal. Let the hardware cache maintain the corresponding VMA object and its coherency.
Quoted 4 lines
Quoted 1 line
Please let me know your comment and thoughts.
Nick Piggin (and I think Eric Dumazet) had nice patches for this. I think they were posted in the private futex thread.
All they need is testing and some results to show they help. I actually don't really have a realistic workload where vma lookup contention is a problem, since the malloc fixes and private futexes went in.
Actually -- there is one thing, apparently oprofile does lots of find_vmas, which trashes the vma cache. Either it should have its own cache, or at least use a "nontemporal" lookup.
What I implemented was a per-thread cache. Per-CPU I guess would be equally possible and might be preferable in some cases (although worse in others). Still, the per-thread cache should be fine for basic performance testing.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 18 lines · Nick Piggin
Quoted 8 lines · Peter Zijlstra
Quoted 6 lines · Vaidyanathan Srinivasan
Per CPU last vma cache: Currently we have the last vma referenced in a one entry cache in
mm_struct. Can we have this cache per CPU or per node so that a multi threaded application can have node/cpu local cache of last vma referenced. This may reduce btree/rbtree traversal. Let the hardware cache maintain the corresponding VMA object and its coherency.Quoted 4 lines
Quoted 1 line
Please let me know your comment and thoughts.
Nick Piggin (and I think Eric Dumazet) had nice patches for this. I think they were posted in the private futex thread.
All they need is testing and some results to show they help. I actually don't really have a realistic workload where vma lookup contention is a problem, since the malloc fixes and private futexes went in.
Quoted 8 lines
Actually -- there is one thing, apparently oprofile does lots of
find_vmas, which trashes the vma cache. Either it should have its own cache, or at least use a "nontemporal" lookup.What I implemented was a per-thread cache. Per-CPU I guess would be equally possible and might be preferable in some cases (although worse in others). Still, the per-thread cache should be fine for basic performance testing.
Apparently our IBM friends on this thread have a workload where mmap_sem does hurt, and I suspect its a massively threaded Java app on a somewhat larger box (8-16 cpus), which does a bit of faulting around.
But I'll let them tell about it :-)
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 25 lines · Peter Zijlstra
Quoted 15 lines · Nick Piggin
Quoted 10 lines · Peter Zijlstra
Quoted 7 lines · Vaidyanathan Srinivasan
Per CPU last vma cache: Currently we have the last vma referenced in a one entry cache in
mm_struct. Can we have this cache per CPU or per node so that a multi threaded application can have node/cpu local cache of last vma referenced. This may reduce btree/rbtree traversal. Let the hardware cache maintain the corresponding VMA object and its coherency.Please let me know your comment and thoughts.
Nick Piggin (and I think Eric Dumazet) had nice patches for this. I think they were posted in the private futex thread.
All they need is testing and some results to show they help. I actually don't really have a realistic workload where vma lookup contention is a problem, since the malloc fixes and private futexes went in.
Quoted 8 lines
Actually -- there is one thing, apparently oprofile does lots of
find_vmas, which trashes the vma cache. Either it should have its own cache, or at least use a "nontemporal" lookup.What I implemented was a per-thread cache. Per-CPU I guess would be equally possible and might be preferable in some cases (although worse in others). Still, the per-thread cache should be fine for basic performance testing.
Quoted 6 lines
Apparently our IBM friends on this thread have a workload where
mmap_semdoes hurt, and I suspect its a massively threaded Java app on a somewhat larger box (8-16 cpus), which does a bit of faulting around.But I'll let them tell about it :-)
Nick,
We used the latest glibc (with the private futexes fix) and the latest kernel. We see improvements in scalability, but at 12-16 CPU's, we see a slowdown. Vaidy has been using ebizzy for testing mmap_sem scalability.
Signature · 10 lines
Warm Regards, Balbir Singh Linux Technology Center IBM, ISTL -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 9 lines
Quoted 8 lines
Apparently our IBM friends on this thread have a workload where
mmap_semdoes hurt, and I suspect its a massively threaded Java app on a somewhat larger box (8-16 cpus), which does a bit of faulting around.But I'll let them tell about it :-)
Quoted 7 lines
Nick,
We used the latest glibc (with the private futexes fix) and the latest kernel. We see improvements in scalability, but at 12-16 CPU's, we see a slowdown. Vaidy has been using ebizzy for testing
mmap_semscalability.
Hi Peter and Nick,
We have been doing some tests with ebizzy 0.2 workload. Here are some of the test results...
ebizzy-futex.png plots the performance impact of private futex while ebizzy-rcu-vma.png plots the performance of Peter's RCU VMA look patch against base kernel with and without private futex.
We can observe in both the plots that private futex improved scaling significantly from 4 CPUs to 8 CPUs but we still have scaling issues beyond 12 CPUs.
Peter's RCU based b+tree vma lookup approach gives marginal performance improvement till 4 to 8 CPUs but does not help beyond that.
Perhaps the scaling problem area shifts beyond 8-12 cpus and it is not just the mmap_sem and vma lookup.
The significant oprofile output for various configurations are listed below:
12 CPUs 2.6.23-rc6 No private futex:
samples % symbol name 6908330 23.7520 __down_read 4990895 17.1595 __up_read 2165162 7.4442 find_vma 2069868 7.1166 futex_wait 2063447 7.0945 futex_wake 1557829 5.3561 drop_futex_key_refs 741268 2.5486 task_rq_lock 638947 2.1968 schedule 600493 2.0646 system_call 515924 1.7738 copy_user_generic_unrolled 399672 1.3741 mwait_idle
12 CPUs 2.6.23-rc6 with private futex:
samples % symbol name 2095531 15.5092 task_rq_lock 1094271 8.0988 schedule 1068093 7.9050 futex_wake 516250 3.8208 futex_wait 469220 3.4727 mwait_idle 468979 3.4710 system_call 443208 3.2802 idle_cpu 438301 3.2439 update_curr 397231 2.9399 try_to_wake_up 364424 2.6971 apic_timer_interrupt 362633 2.6839 scheduler_tick
8 CPUs 2.6.23-rc9 + RCU VMA + private futex:
samples % symbol name 386111 10.4460 mwait_idle 367289 9.9368 __btree_search 286286 7.7453 apic_timer_interrupt 272863 7.3821 find_busiest_group 230268 6.2298 scheduler_tick 224902 6.0846 copy_user_generic_unrolled 188991 5.1130 memset 123692 3.3464 __exit_idle 91930 2.4871 hrtimer_run_queues 87796 2.3753 task_rq_lock 85968 2.3258 run_rebalance_domains
12 CPUs 2.6.23-rc9 + RCU VMA + private futex:
samples % symbol name 14505427 18.6891 task_rq_lock 10323001 13.3004 futex_wake 6980246 8.9935 schedule 4768884 6.1443 futex_wait 2981997 3.8421 idle_cpu 2939439 3.7872 system_call 2655022 3.4208 update_curr 2433540 3.1354 try_to_wake_up 1786021 2.3011 check_preempt_curr_fair 1692711 2.1809 syscall_trace_enter 1486381 1.9151 thread_return
All the above test results has the impact of oprofile included. Running oprofile also may significantly increase mmap_sem contention.
I Will run the tests again without oprofile to understand the impact of oprofile itself.
Please let me know your comments and suggestions.
--Vaidy
Quoted 13 lines · Vaidyanathan Srinivasan
Quoted 4 lines
Quoted 4 lines
Apparently our IBM friends on this thread have a workload where
mmap_semdoes hurt, and I suspect its a massively threaded Java app on a somewhat larger box (8-16 cpus), which does a bit of faulting around.Quoted 8 lines
Quoted 1 line
But I'll let them tell about it :-)
Nick,
We used the latest glibc (with the private futexes fix) and the latest kernel. We see improvements in scalability, but at 12-16 CPU's, we see a slowdown. Vaidy has been using ebizzy for testing
mmap_semscalability.
Quoted 4 lines
Hi Peter and Nick,
We have been doing some tests with ebizzy 0.2 workload. Here are some of the test results...
Cool graphs!
Looks like private futexes blew your mmap_sem contention away. Not too
surprising: I wouldn't have expected a high performance app like this to be doing a huge number of mmap()ing and page faults...
They almost tripled your peak performance! Of course that's with ebizzy... what sort of correlation does this have to your real server app? (ie. does it also see a 3x speedup?)
I don't see any synchronisation in ebizzy 2 -- I guess the gain is all due to improved libc heap management scalability?
Quoted 34 lines
ebizzy-futex.png plots the performance impact of private futex while ebizzy-rcu-vma.png plots the performance of Peter's RCU VMA look patch against base kernel with and without private futex.
We can observe in both the plots that private futex improved scaling significantly from 4 CPUs to 8 CPUs but we still have scaling issues beyond 12 CPUs.
Peter's RCU based b+tree vma lookup approach gives marginal performance improvement till 4 to 8 CPUs but does not help beyond that.
Perhaps the scaling problem area shifts beyond 8-12 cpus and it is not just the
mmap_semand vma lookup.The significant oprofile output for various configurations are listed below:
12 CPUs 2.6.23-rc6 No private futex:
samples % symbol name 6908330 23.7520 __down_read 4990895 17.1595 __up_read 2165162 7.4442 find_vma 2069868 7.1166 futex_wait 2063447 7.0945 futex_wake 1557829 5.3561 drop_futex_key_refs 741268 2.5486 task_rq_lock 638947 2.1968 schedule 600493 2.0646 system_call 515924 1.7738 copy_user_generic_unrolled 399672 1.3741 mwait_idle12 CPUs 2.6.23-rc6 with private futex:
Quoted 12 lines
samples % symbol name 2095531 15.5092 task_rq_lock 1094271 8.0988 schedule 1068093 7.9050 futex_wake 516250 3.8208 futex_wait 469220 3.4727 mwait_idle 468979 3.4710 system_call 443208 3.2802 idle_cpu 438301 3.2439 update_curr 397231 2.9399 try_to_wake_up 364424 2.6971 apic_timer_interrupt 362633 2.6839 scheduler_tick
There is basically no more mmap_sem contention or any vma lookups to be seen. So I think it would be a waste of time to test my vma cache patches really :P
It looks like most of the contention is on the runqueue locks and on futex locks now. Both those paths are now pretty optimised... probably some improvements could be made, but fundamentally if you are doing a lot of sleeping on a single futex, and are doing a lot of cross-CPU wakeups, then you are going to have scalability limits.
So improving glibc allocator to be more scalable, or changing the application is likely to be the best course of action from here...
*If* you have a huge number of futexes, or a lot of processes (each with their own threads and private futexes), then there are some possible things we could try to improve in the private futex lookup code... but that doesn't seem to be the case for you?
Quoted 7 lines
All the above test results has the impact of oprofile included. Running oprofile also may significantly increase
mmap_semcontention.I Will run the tests again without oprofile to understand the impact of oprofile itself.
Please let me know your comments and suggestions.
Getting confirmation of what is so costly in futex_wait and futex_wake might be useful if you have time. I'll bet it is the hash lock, but could be wrong.
Playing with the sched-domains parameters and possibly trying to reduce the number of cross-CPU wakeups might help. However you have to be pretty careful with this that you don't just tune the system to work well with ebizzy and not your real workload.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
[snip]
Quoted 7 lines
All the above test results has the impact of oprofile included. Running oprofile also may significantly increase
mmap_semcontention.I Will run the tests again without oprofile to understand the impact of oprofile itself.
Hi,
I have run the same tests without oprofile and also tried to plot the impact of oprofile.
There are two attached graphs.
rcu-vma-scaling.png contains the plot of Peter's RCU-VMA lookup without running oprofile.
There are some variations beyond 10 CPUs. I am trying to wonder if those were due to errors in test/measurement!
oprofile-scaling.png plots similar tests with and without oprofile enabled.
We can see more impact beyond 12 CPUs.
--Vaidy
Quoted 9 lines · Nick Piggin
Quoted 8 lines · Peter Zijlstra
Quoted 6 lines · Vaidyanathan Srinivasan
Per CPU last vma cache: Currently we have the last vma referenced in a one entry cache in
mm_struct. Can we have this cache per CPU or per node so that a multi threaded application can have node/cpu local cache of last vma referenced. This may reduce btree/rbtree traversal. Let the hardware cache maintain the corresponding VMA object and its coherency.
Quoted 7 lines
Quoted 3 lines
Quoted 1 line
Please let me know your comment and thoughts.
Nick Piggin (and I think Eric Dumazet) had nice patches for this. I think they were posted in the private futex thread.
All they need is testing and some results to show they help. I actually don't really have a realistic workload where vma lookup contention is a problem, since the malloc fixes and private futexes went in.
Hi Nick,
Just point me to the patch. I will run them thru ebizzy with and without oprofile on a large system and post the data.
Quoted 9 lines
Actually -- there is one thing, apparently oprofile does lots of
find_vmas, which trashes the vma cache. Either it should have its own cache, or at least use a "nontemporal" lookup.What I implemented was a per-thread cache. Per-CPU I guess would be equally possible and might be preferable in some cases (although worse in others). Still, the per-thread cache should be fine for basic performance testing.
Per-thread last vma cache is a good idea... much simpler to implement than per CPU or per node cache I guess. But still invalidating the caches my be a slow path. Lets check it out.
--Vaidy
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 9 lines · Peter Zijlstra
Quoted 8 lines · Vaidyanathan Srinivasan
Peter Zijlstra wrote:
Hi Peter,Making node local copies of VMA is a good idea to reduce inter-node traffic, but the cost of search and delete is very high. Also, as you have pointed out, if the atomic operations happen on remote node due to scheduler migrating our thread, then all the cycles saved may be lost.
Quoted 4 lines
Quoted 2 lines
In
find_get_vma()cross node traffic is due to btree traversal or the actual VMA object reference?Not sure, I'm not sure how to profile cacheline transfers.
I asked around and found that oprofile can give cache misses. But associating it with find_get_vma() is the problem.
Quoted 10 lines
The outlined approach would try to keep all accesses read-only, so that the cacheline can be shared. But yeah, once it get evicted it needs to be re-transfered.
Quoted 5 lines
Can we look at duplicating the btree
structure per node and have VMA structures just one copy and make all btrees in each node point to the same vma object. This will make write operation and deletion of btree entries on all nodes little simple. All VMA lists will be unique and not duplicated.
Quoted 5 lines
But that would end up with a 2d tree, (mm, vma) in which you can try to find an exact match for a given (mm, address) key.
Trouble with multi-dimensional trees is the balancing thing, afaik its an np-hard problem.
Not a good idea then :)
Quoted 8 lines
Quoted 4 lines
Another related idea is to move the VMA object to node local memory. Can we migrate the VMA object to the node where it is referenced the most? We still maintain only _one_ copy of VMA object. No data duplication, but we can move the memory around to make it node local.
I guess we can do that, is you take the vma lock in exclusive mode, you can make a copy of the object, replace the tree pointer, mark the old one dead (so that rcu lookups with re-try) and
rcu_freethe old one.
So worth a try. I will pick this up.
Quoted 9 lines
Quoted 5 lines
Some more thoughts:
Pagefault handler does most of the
find_get_vma()to validate user address and then create page table entries (allocate page frames)... can we make the page fault handler run on the node where the VMAs have been allocated?explicit migration - like
migrate_disable()- make load balancing a very hard problem.
Quoted 6 lines
Quoted 4 lines
The CPU that has page-faulted need not necessarily do all the
find_vma()
calls and update the page table. The process can sleep while another CPU _near_ to the memory containing VMAs and pagetable can do the job with local memory references.would we not end up with remote page tables?
Remote pagetable update is less costly than remote vma lookup. We will have to balance between the two.
Quoted 9 lines
Quoted 9 lines
I don't know if the page tables for the faulting process is allocated in node local memory.
Per CPU last vma cache: Currently we have the last vma referenced in a one entry cache in
mm_struct. Can we have this cache per CPU or per node so that a multi threaded application can have node/cpu local cache of last vma referenced. This may reduce btree/rbtree traversal. Let the hardware cache maintain the corresponding VMA object and its coherency.
Quoted 4 lines
Quoted 1 line
Please let me know your comment and thoughts.
Nick Piggin (and I think Eric Dumazet) had nice patches for this. I think they were posted in the private futex thread.
Good. I would like to try them out.
Quoted 6 lines
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>