linux-kernel - Re: JRCU Theory of Operation

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20110314005052.GE2167@linux.vnet.ibm.com>
Date:	Sun, 13 Mar 2011 17:50:52 -0700
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Joe Korty <joe.korty@...r.com>
Cc:	Frederic Weisbecker <fweisbec@...il.com>,
	Peter Zijlstra <peterz@...radead.org>,
	Lai Jiangshan <laijs@...fujitsu.com>,
	"mathieu.desnoyers@...icios.com" <mathieu.desnoyers@...icios.com>,
	"dhowells@...hat.com" <dhowells@...hat.com>,
	"loic.minier@...aro.org" <loic.minier@...aro.org>,
	"dhaval.giani@...il.com" <dhaval.giani@...il.com>,
	"tglx@...utronix.de" <tglx@...utronix.de>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"josh@...htriplett.org" <josh@...htriplett.org>,
	"houston.jim@...cast.net" <houston.jim@...cast.net>,
	"corbet@....net" <corbet@....net>
Subject: Re: JRCU Theory of Operation

On Sun, Mar 13, 2011 at 07:53:51PM -0400, Joe Korty wrote:
> On Sun, Mar 13, 2011 at 12:56:27AM -0500, Paul E. McKenney wrote:
> > > Even though I keep saying 50msecs for everything, I
> > > suspect that the Q switching meets all the above quiescent
> > > requirements in a few tens of microseconds.  Thus even
> > > a 1 msec JRCU sampling period is expected to be safe,
> > > at least in regard to Q switching.
> > 
> > I would feel better about this is the CPU vendors were willing to give
> > an upper bound...
> 
> I suspect they don't because they don't really know
> themselves .. in that whatever it is, it keeps changing
> from chip to chip, trying to describe such would be beyond
> the english language, and any description would tie them
> down on what they could do in future chip designs.

Indeed!

> But, there is a hint in current behavior.  It is well known
> that many multithreaded apps don't uses barriers at all;
> the authors had no idea what they are for.  Yet such apps
> largely work.  This implies that the chip designers are
> very aggressive in doing implied memory barriers wherever
> possible, and they are very aggressive in pushing out
> stores to caches very quickly even when memory barriers,
> implied or not, are not present.

Ahem.  Or that many barrier-omission failures have a low probability
of occurring.  One case in point is a bug in RCU a few years back,
where ten-hour rcutorture runs produced only a handful of errors (see
http://paulmck.livejournal.com/14639.html).  Other cases are turned up by
Peter Sewell's work, which tests code sequences with and without memory
barriers (http://www.cl.cam.ac.uk/~pes20/).  In many cases, broken code
sequences have failure rates in the parts per billion.

This should not be a surprise.  You can see the same effect with locking.
If you have very contention on a given lock, then there will be a very
low probability of encountering bugs involving forgetting to acquire
that lock.

If the CPU count continues increasing, these sorts of latent bugs
will have increasing probabilities of biting us.

						Thanx, Paul
--
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/