linux-kernel - Re: [PATCH] QRCU with lockless fastpath

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] [day] [month] [year] [list]

Message-ID: <20070225201641.GA2266@tv-sign.ru>
Date:	Sun, 25 Feb 2007 23:16:41 +0300
From:	Oleg Nesterov <oleg@...sign.ru>
To:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Cc:	jens.axboe@...cle.com, linux-kernel@...r.kernel.org,
	a.p.zijlstra@...llo.nl, mingo@...e.hu, hch@...radead.org,
	akpm@...l.org, stern@...land.harvard.edu
Subject: Re: [PATCH] QRCU with lockless fastpath

On 02/24, Paul E. McKenney wrote:
> 
> This is an updated version of Oleg Nesterov's QRCU that avoids the
> earlier lock acquisition on the synchronize_qrcu() fastpath.  This passes
> rcutorture on x86 and the weakly ordered POWER.  A promela model of the
> code passes as noted before for 2 readers and 3 updaters and for 3 readers
> and 2 updaters.  3 readers and 3 updaters runs every machine that I have
> access to out of memory -- nothing like a little combinatorial explosion!
> However, after some thought, the proof ended up being simple enough:
> 
> 1.	If synchronize_qrcu() exits too soon, then by definition
> 	there has been a reader present during synchronize_srcu()'s
> 	full execution.
> 
> 2.	The counter corresponding to this reader will be at least
> 	1 at all times.
> 
> 3.	The synchronize_qrcu() code forces at least one of the counters
> 	to be at least one at all times -- if there is a reader, the
> 	sum will be at least two.  (Unfortunately, we cannot fetch
> 	the pair of counters atomically.)
> 
> 4.	Therefore, the only way that synchronize_qrcu()s fastpath can
> 	see a sum of 1 is if it races with another synchronize_qrcu() --
> 	the first synchronize_qrcu() must read one of the counters before
> 	the second synchronize_qrcu() increments it, and must read the
> 	other counter after the second synchronize_qrcu() decrements it.
> 	There can be at most one reader present through this entire
> 	operation -- otherwise, the first synchronize_qrcu() will see
> 	a sum of 2 or greater.
> 
> 5.	But the second synchronize_qrcu() will not release the mutex
> 	until after the reader is done.  During this time, the first
> 	synchronize_qrcu() will always see a sum of at least 2, and
> 	therefore cannot take the remainder of the fastpath until the
> 	reader is done.
> 
> 6.	Because the second synchronize_qrcu() holds the mutex, no other
> 	synchronize_qrcu() can manipulate the counters until the reader
> 	is done.  A repeat of the race called out in #4 above therefore
> 	cannot happen until after the reader is done, in which case it
> 	is safe for the first synchronize_qrcu() to proceed.
> 
> Therefore, two summations of the counter separated by a memory barrier
> suffices and the implementation shown below also suffices.
> 
> (And, yes, the fastpath -could- check for a sum of zero and exit
> immediately, but this would help only in case of a three-way race
> between two synchronize_qrcu()s and a qrcu_read_unlock(), would add
> another compare, so is not worth it.)
> 
> Signed-off-by: Paul E. McKenney <paulmck@...ux.vnet.ibm.com>

Thanks! This fastpath really improves QRCU.

Oleg.


-
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/