linux-kernel - Re: [RFC][PATCH 4/6] SRCU free VMAs

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <5449C8A6.9080403@cn.fujitsu.com>
Date:	Fri, 24 Oct 2014 11:33:58 +0800
From:	Lai Jiangshan <laijs@...fujitsu.com>
To:	Peter Zijlstra <peterz@...radead.org>
CC:	<torvalds@...ux-foundation.org>, <paulmck@...ux.vnet.ibm.com>,
	<tglx@...utronix.de>, <akpm@...ux-foundation.org>,
	<riel@...hat.com>, <mgorman@...e.de>, <oleg@...hat.com>,
	<mingo@...hat.com>, <minchan@...nel.org>,
	<kamezawa.hiroyu@...fujitsu.com>, <viro@...iv.linux.org.uk>,
	<dave@...olabs.net>, <linux-kernel@...r.kernel.org>,
	<linux-mm@...ck.org>
Subject: Re: [RFC][PATCH 4/6] SRCU free VMAs

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 from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/