Manage the VMAs with SRCU such that we can do a lockless VMA lookup.
We put the fput(vma->vm_file) in the SRCU callback, this keeps files
valid during speculative faults, this is possible due to the delayed
fput work by Al Viro -- do we need srcu_barrier() in unmount
someplace?
We guard the mm_rb tree with a seqlock (XXX could be a seqcount but
we'd have to disable preemption around the write side in order to make
the retry loop in __read_seqcount_begin() work) such that we can know
if the rb tree walk was correct. We cannot trust the restult of a
lockless tree walk in the face of concurrent tree rotations; although
we can trust on the termination of such walks -- tree rotations
guarantee the end result is a tree again after all.
Furthermore, we rely on the WMB implied by the
write_seqlock/count_begin() to separate the VMA initialization and the
publishing stores, analogous to the RELEASE in rcu_assign_pointer().
We also rely on the RMB from read_seqretry() to separate the vma load
from further loads like the smp_read_barrier_depends() in regular
RCU.
We must not touch the vmacache while doing SRCU lookups as that is not
properly serialized against changes. We update gap information after
publishing the VMA, but A) we don't use that and B) the seqlock
read side would fix that anyhow.
We clear vma->vm_rb for nodes removed from the vma tree such that we
can easily detect such 'dead' nodes, we rely on the WMB from
write_sequnlock() to separate the tree removal and clearing the node.
Provide find_vma_srcu() which wraps the required magic.
XXX: mmap()/munmap() heavy workloads might suffer from the global lock
in call_srcu() -- this is fixable with a 'better' SRCU implementation.
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
---
include/linux/mm_types.h | 3 +
kernel/fork.c | 1
mm/init-mm.c | 1
mm/internal.h | 18 +++++++++
mm/mmap.c | 88 ++++++++++++++++++++++++++++++++++++-----------
5 files changed, 91 insertions(+), 20 deletions(-)
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -14,6 +14,7 @@
#include <linux/uprobes.h>
#include <linux/page-flags-layout.h>
#include <linux/seqlock.h>
+#include <linux/srcu.h>
#include <asm/page.h>
#include <asm/mmu.h>
@@ -310,6 +311,7 @@ struct vm_area_struct {
struct mempolicy *vm_policy; /* NUMA policy for the VMA */
#endif
seqcount_t vm_sequence;
+ struct rcu_head vm_rcu_head;
};
struct core_thread {
@@ -347,6 +349,7 @@ struct kioctx_table;
struct mm_struct {
struct vm_area_struct *mmap; /* list of VMAs */
struct rb_root mm_rb;
+ seqlock_t mm_seq;
u32 vmacache_seqnum; /* per-thread vmacache */
#ifdef CONFIG_MMU
unsigned long (*get_unmapped_area) (struct file *filp,
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -553,6 +553,7 @@ static struct mm_struct *mm_init(struct
mm->mmap = NULL;
mm->mm_rb = RB_ROOT;
mm->vmacache_seqnum = 0;
+ seqlock_init(&mm->mm_seq);
atomic_set(&mm->mm_users, 1);
atomic_set(&mm->mm_count, 1);
init_rwsem(&mm->mmap_sem);
--- a/mm/init-mm.c
+++ b/mm/init-mm.c
@@ -15,6 +15,7 @@
struct mm_struct init_mm = {
.mm_rb = RB_ROOT,
+ .mm_seq = __SEQLOCK_UNLOCKED(init_mm.mm_seq),
.pgd = swapper_pg_dir,
.mm_users = ATOMIC_INIT(2),
.mm_count = ATOMIC_INIT(1),
--- a/mm/internal.h
+++ b/mm/internal.h
@@ -14,6 +14,24 @@
#include <linux/fs.h>
#include <linux/mm.h>
+extern struct srcu_struct vma_srcu;
+
+extern struct vm_area_struct *find_vma_srcu(struct mm_struct *mm, unsigned long addr);
+
+static inline bool vma_is_dead(struct vm_area_struct *vma, unsigned int sequence)
+{
+ int ret = RB_EMPTY_NODE(&vma->vm_rb);
+ unsigned seq = ACCESS_ONCE(vma->vm_sequence.sequence);
+
+ /*
+ * Matches both the wmb in write_seqlock_{begin,end}() and
+ * the wmb in vma_rb_erase().
+ */
+ smp_rmb();
+
+ return ret || seq != sequence;
+}
+
void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
unsigned long floor, unsigned long ceiling);
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -247,6 +247,23 @@ void unlink_file_vma(struct vm_area_stru
}
}
+DEFINE_SRCU(vma_srcu);
+
+static void __free_vma(struct rcu_head *head)
+{
+ struct vm_area_struct *vma =
+ container_of(head, struct vm_area_struct, vm_rcu_head);
+
+ if (vma->vm_file)
+ fput(vma->vm_file);
+ kmem_cache_free(vm_area_cachep, vma);
+}
+
+static void free_vma(struct vm_area_struct *vma)
+{
+ call_srcu(&vma_srcu, &vma->vm_rcu_head, __free_vma);
+}
+
/*
* Close a vm structure and free it, returning the next.
*/
@@ -257,10 +274,8 @@ static struct vm_area_struct *remove_vma
might_sleep();
if (vma->vm_ops && vma->vm_ops->close)
vma->vm_ops->close(vma);
- if (vma->vm_file)
- fput(vma->vm_file);
mpol_put(vma_policy(vma));
- kmem_cache_free(vm_area_cachep, vma);
+ free_vma(vma);
return next;
}
@@ -468,17 +483,19 @@ static void vma_gap_update(struct vm_are
vma_gap_callbacks_propagate(&vma->vm_rb, NULL);
}
-static inline void vma_rb_insert(struct vm_area_struct *vma,
- struct rb_root *root)
+static inline void vma_rb_insert(struct vm_area_struct *vma, struct mm_struct *mm)
{
+ struct rb_root *root = &mm->mm_rb;
+
/* All rb_subtree_gap values must be consistent prior to insertion */
validate_mm_rb(root, NULL);
rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks);
}
-static void vma_rb_erase(struct vm_area_struct *vma, struct rb_root *root)
+static void vma_rb_erase(struct vm_area_struct *vma, struct mm_struct *mm)
{
+ struct rb_root *root = &mm->mm_rb;
/*
* All rb_subtree_gap values must be consistent prior to erase,
* with the possible exception of the vma being erased.
@@ -490,7 +507,15 @@ static void vma_rb_erase(struct vm_area_
* so make sure we instantiate it only once with our desired
* augmented rbtree callbacks.
*/
+ write_seqlock(&mm->mm_seq);
rb_erase_augmented(&vma->vm_rb, root, &vma_gap_callbacks);
+ write_sequnlock(&mm->mm_seq); /* wmb */
+
+ /*
+ * Ensure the removal is complete before clearing the node.
+ * Matched by vma_is_dead()/handle_speculative_fault().
+ */
+ RB_CLEAR_NODE(&vma->vm_rb);
}
/*
@@ -607,10 +632,12 @@ void __vma_link_rb(struct mm_struct *mm,
* immediately update the gap to the correct value. Finally we
* rebalance the rbtree after all augmented values have been set.
*/
+ write_seqlock(&mm->mm_seq);
rb_link_node(&vma->vm_rb, rb_parent, rb_link);
vma->rb_subtree_gap = 0;
vma_gap_update(vma);
- vma_rb_insert(vma, &mm->mm_rb);
+ vma_rb_insert(vma, mm);
+ write_sequnlock(&mm->mm_seq);
}
static void __vma_link_file(struct vm_area_struct *vma)
@@ -687,7 +714,7 @@ __vma_unlink(struct mm_struct *mm, struc
{
struct vm_area_struct *next;
- vma_rb_erase(vma, &mm->mm_rb);
+ vma_rb_erase(vma, mm);
prev->vm_next = next = vma->vm_next;
if (next)
next->vm_prev = prev;
@@ -872,15 +899,13 @@ again: remove_next = 1 + (end > next->
}
if (remove_next) {
- if (file) {
+ if (file)
uprobe_munmap(next, next->vm_start, next->vm_end);
- fput(file);
- }
if (next->anon_vma)
anon_vma_merge(vma, next);
mm->map_count--;
mpol_put(vma_policy(next));
- kmem_cache_free(vm_area_cachep, next);
+ free_vma(next);
/*
* In mprotect's case 6 (see comments on vma_merge),
* we must remove another next too. It would clutter
@@ -2027,16 +2052,11 @@ get_unmapped_area(struct file *file, uns
EXPORT_SYMBOL(get_unmapped_area);
/* Look up the first VMA which satisfies addr < vm_end, NULL if none. */
-struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
+static struct vm_area_struct *__find_vma(struct mm_struct *mm, unsigned long addr)
{
struct rb_node *rb_node;
struct vm_area_struct *vma;
- /* Check the cache first. */
- vma = vmacache_find(mm, addr);
- if (likely(vma))
- return vma;
-
rb_node = mm->mm_rb.rb_node;
vma = NULL;
@@ -2054,13 +2074,41 @@ struct vm_area_struct *find_vma(struct m
rb_node = rb_node->rb_right;
}
+ return vma;
+}
+
+struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
+{
+ struct vm_area_struct *vma;
+
+ /* Check the cache first. */
+ vma = vmacache_find(mm, addr);
+ if (likely(vma))
+ return vma;
+
+ vma = __find_vma(mm, addr);
if (vma)
vmacache_update(addr, vma);
+
return vma;
}
-
EXPORT_SYMBOL(find_vma);
+struct vm_area_struct *find_vma_srcu(struct mm_struct *mm, unsigned long addr)
+{
+ struct vm_area_struct *vma;
+ unsigned int seq;
+
+ WARN_ON_ONCE(!srcu_read_lock_held(&vma_srcu));
+
+ do {
+ seq = read_seqbegin(&mm->mm_seq);
+ vma = __find_vma(mm, addr);
+ } while (read_seqretry(&mm->mm_seq, seq));
+
+ return vma;
+}
+
/*
* Same as find_vma, but also return a pointer to the previous VMA in *pprev.
*/
@@ -2415,7 +2463,7 @@ detach_vmas_to_be_unmapped(struct mm_str
insertion_point = (prev ? &prev->vm_next : &mm->mmap);
vma->vm_prev = NULL;
do {
- vma_rb_erase(vma, &mm->mm_rb);
+ vma_rb_erase(vma, mm);
mm->map_count--;
tail_vma = vma;
vma = vma->vm_next;
On Mon, Oct 20, 2014 at 2:56 PM, Peter Zijlstra <[email protected]> wrote:
> Manage the VMAs with SRCU such that we can do a lockless VMA lookup.
Can you explain why srcu, and not plain regular rcu?
Especially as you then *note* some of the problems srcu can have.
Making it regular rcu would also seem to make it possible to make the
seqlock be just a seqcount, no?
Linus
On Mon, Oct 20, 2014 at 04:41:45PM -0700, Linus Torvalds wrote:
> On Mon, Oct 20, 2014 at 2:56 PM, Peter Zijlstra <[email protected]> wrote:
> > Manage the VMAs with SRCU such that we can do a lockless VMA lookup.
>
> Can you explain why srcu, and not plain regular rcu?
>
> Especially as you then *note* some of the problems srcu can have.
> Making it regular rcu would also seem to make it possible to make the
> seqlock be just a seqcount, no?
Because we need to hold onto the RCU read side lock across the entire
fault, which can involve IO and all kinds of other blocking ops.
On Mon, Oct 20, 2014 at 04:41:45PM -0700, Linus Torvalds wrote:
> On Mon, Oct 20, 2014 at 2:56 PM, Peter Zijlstra <[email protected]> wrote:
> > Manage the VMAs with SRCU such that we can do a lockless VMA lookup.
>
> Can you explain why srcu, and not plain regular rcu?
>
> Especially as you then *note* some of the problems srcu can have.
> Making it regular rcu would also seem to make it possible to make the
> seqlock be just a seqcount, no?
Ah, the reason I did the seqlock is because the read side will spin-wait
for &1 to go away. If the write side is preemptible that's horrid. I
used seqlock because that takes a lock (and thus disables preemption) on
the write side, but I could equally have done:
preempt_disable();
write_seqcount_begin();
...
write_seqcount_end();
preempt_disable();
Since the lock is indeed superfluous, we're already fully serialized by
mmap_sem in this path.
Using regular RCU isn't sufficient, because of PREEMPT_RCU.
>
> +struct vm_area_struct *find_vma_srcu(struct mm_struct *mm, unsigned long addr)
> +{
> + struct vm_area_struct *vma;
> + unsigned int seq;
> +
> + WARN_ON_ONCE(!srcu_read_lock_held(&vma_srcu));
> +
> + do {
> + seq = read_seqbegin(&mm->mm_seq);
> + vma = __find_vma(mm, addr);
will the __find_vma() loops for ever due to the rotations in the RBtree?
> + } while (read_seqretry(&mm->mm_seq, seq));
> +
> + return vma;
> +}
On Thu, Oct 23, 2014 at 06:14:45PM +0800, Lai Jiangshan wrote:
>
> >
> > +struct vm_area_struct *find_vma_srcu(struct mm_struct *mm, unsigned long addr)
> > +{
> > + struct vm_area_struct *vma;
> > + unsigned int seq;
> > +
> > + WARN_ON_ONCE(!srcu_read_lock_held(&vma_srcu));
> > +
> > + do {
> > + seq = read_seqbegin(&mm->mm_seq);
> > + vma = __find_vma(mm, addr);
>
> will the __find_vma() loops for ever due to the rotations in the RBtree?
No, a rotation takes a tree and generates a tree, furthermore the
rotation has a fairly strict fwd progress guarantee seeing how its now
done with preemption disabled.
Therefore, even if we're in a node that's being rotated up, we can only
'loop' for as long as it takes for the new pointer stores to become
visible on our CPU.
Thus we have a tree descent termination guarantee.
On 10/23/2014 07:03 PM, Peter Zijlstra wrote:
> On Thu, Oct 23, 2014 at 06:14:45PM +0800, Lai Jiangshan wrote:
>>
>>>
>>> +struct vm_area_struct *find_vma_srcu(struct mm_struct *mm, unsigned long addr)
>>> +{
>>> + struct vm_area_struct *vma;
>>> + unsigned int seq;
>>> +
>>> + WARN_ON_ONCE(!srcu_read_lock_held(&vma_srcu));
>>> +
>>> + do {
>>> + seq = read_seqbegin(&mm->mm_seq);
>>> + vma = __find_vma(mm, addr);
>>
>> will the __find_vma() loops for ever due to the rotations in the RBtree?
>
> No, a rotation takes a tree and generates a tree, furthermore the
> rotation has a fairly strict fwd progress guarantee seeing how its now
> done with preemption disabled.
I can't get the magic.
__find_vma is visiting vma_a,
vma_a is rotated to near the top due to multiple updates to the mm.
__find_vma is visiting down to near the bottom, vma_b.
now vma_b is rotated up to near the top again.
__find_vma is visiting down to near the bottom, vma_c.
now vma_c is rotated up to near the top again.
...
>
> Therefore, even if we're in a node that's being rotated up, we can only
> 'loop' for as long as it takes for the new pointer stores to become
> visible on our CPU.
>
> Thus we have a tree descent termination guarantee.
> .
>
On Fri, Oct 24, 2014 at 11:33:58AM +0800, Lai Jiangshan wrote:
> On 10/23/2014 07:03 PM, Peter Zijlstra wrote:
> > On Thu, Oct 23, 2014 at 06:14:45PM +0800, Lai Jiangshan wrote:
> >>
> >>>
> >>> +struct vm_area_struct *find_vma_srcu(struct mm_struct *mm, unsigned long addr)
> >>> +{
> >>> + struct vm_area_struct *vma;
> >>> + unsigned int seq;
> >>> +
> >>> + WARN_ON_ONCE(!srcu_read_lock_held(&vma_srcu));
> >>> +
> >>> + do {
> >>> + seq = read_seqbegin(&mm->mm_seq);
> >>> + vma = __find_vma(mm, addr);
> >>
> >> will the __find_vma() loops for ever due to the rotations in the RBtree?
> >
> > No, a rotation takes a tree and generates a tree, furthermore the
> > rotation has a fairly strict fwd progress guarantee seeing how its now
> > done with preemption disabled.
>
> I can't get the magic.
>
> __find_vma is visiting vma_a,
> vma_a is rotated to near the top due to multiple updates to the mm.
> __find_vma is visiting down to near the bottom, vma_b.
> now vma_b is rotated up to near the top again.
> __find_vma is visiting down to near the bottom, vma_c.
> now vma_c is rotated up to near the top again.
>
> ...
Why would there be that much rotations? Is this a scenario where someone
is endlessly changing the tree?
If you stop updating the tree, the traversal will finish.
This is no different to the reader starvation already present with
seqlocks.
On Tue, 21 Oct 2014, Peter Zijlstra wrote:
> On Mon, Oct 20, 2014 at 04:41:45PM -0700, Linus Torvalds wrote:
> > On Mon, Oct 20, 2014 at 2:56 PM, Peter Zijlstra <[email protected]> wrote:
> > > Manage the VMAs with SRCU such that we can do a lockless VMA lookup.
> >
> > Can you explain why srcu, and not plain regular rcu?
> >
> > Especially as you then *note* some of the problems srcu can have.
> > Making it regular rcu would also seem to make it possible to make the
> > seqlock be just a seqcount, no?
>
> Because we need to hold onto the RCU read side lock across the entire
> fault, which can involve IO and all kinds of other blocking ops.
Hmmm... One optimization to do before we get into these changes is to work
on allowing the dropping of mmap_sem before we get to sleeping and I/O and
then reevaluate when I/O etc is complete? This is probably the longest
hold on mmap_sem that is also frequent. Then it may be easier to use
standard RCU later.
On Fri, Oct 24, 2014 at 10:16:24AM -0500, Christoph Lameter wrote:
> Hmmm... One optimization to do before we get into these changes is to work
> on allowing the dropping of mmap_sem before we get to sleeping and I/O and
> then reevaluate when I/O etc is complete? This is probably the longest
> hold on mmap_sem that is also frequent. Then it may be easier to use
> standard RCU later.
The hold time isn't relevant, in fact breaking up the mmap_sem such that
we require multiple acquisitions will just increase the cacheline
bouncing.
Also I think it makes more sense to continue an entire fault operation,
including blocking, if at all possible. Every retry will just waste more
time.
Also, there is a lot of possible blocking, there's lock_page,
page_mkwrite() -- which ends up calling into the dirty throttle etc. We
could not possibly retry on all that, the error paths involved would be
horrible for one.
That said, there's a fair bit of code that does allow the retry, and I
think most fault paths actually do the retry on IO.
On Fri, 24 Oct 2014, Peter Zijlstra wrote:
> The hold time isn't relevant, in fact breaking up the mmap_sem such that
> we require multiple acquisitions will just increase the cacheline
> bouncing.
Well this wont be happening anymore once you RCUify the stuff. If you go
to sleep then its best to release mmap_sem and then the bouncing wont
matter.
Dropping mmap_sem there will also expose you to races you will see later
too when you RCUify the code paths. That way those can be deal with
beforehand.
> Also I think it makes more sense to continue an entire fault operation,
> including blocking, if at all possible. Every retry will just waste more
> time.
Ok then dont retry. Just drop mmap_sem before going to sleep. When you
come back evaluate the situation and if we can proceed do so otherwise
retry.