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.
> .
>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>