lkml.org 
[lkml]   [2014]   [Oct]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC][PATCH 4/6] SRCU free VMAs
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.


\
 
 \ /
  Last update: 2014-10-24 10:01    [W:0.063 / U:0.120 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site