All of lore.kernel.org
 help / color / mirror / Atom feed
From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: linux-kernel@vger.kernel.org, mingo@elte.hu,
	laijs@cn.fujitsu.com, dipankar@in.ibm.com,
	akpm@linux-foundation.org, mathieu.desnoyers@polymtl.ca,
	josh@joshtriplett.org, niv@us.ibm.com, tglx@linutronix.de,
	rostedt@goodmis.org, Valdis.Kletnieks@vt.edu,
	dhowells@redhat.com, eric.dumazet@gmail.com, darren@dvhart.com,
	fweisbec@gmail.com, sbw@mit.edu, patches@linaro.org,
	"Paul E. McKenney" <paul.mckenney@linaro.org>
Subject: Re: [PATCH tip/core/rcu 23/23] rcu: Simplify quiescent-state detection
Date: Thu, 6 Sep 2012 13:01:38 -0700	[thread overview]
Message-ID: <20120906200138.GR2448@linux.vnet.ibm.com> (raw)
In-Reply-To: <1346942162.18408.25.camel@twins>

On Thu, Sep 06, 2012 at 04:36:02PM +0200, Peter Zijlstra wrote:
> On Thu, 2012-08-30 at 11:18 -0700, Paul E. McKenney wrote:
> > From: "Paul E. McKenney" <paul.mckenney@linaro.org>
> > 
> > The current quiescent-state detection algorithm is needlessly
> > complex.
> 
> Heh! Be careful, we might be led into believing all this RCU is actually
> really rather simple and this complexity is a bug on your end ;-)

Actually, the smallest "toy" implementation of RCU is only about 20
lines of code -- and on a mythical sequentially consistent system, it
would be smaller still.  Of course, the Linux kernel implementation if
somewhat larger.  Something about wanting scalability above a few tens of
CPUs, real-time response (also on huge numbers of CPUs), energy-efficient
handling of dyntick-idle mode, detection of stalled CPUs, and so on.  ;-)

> >   It records the grace-period number corresponding to
> > the quiescent state at the time of the quiescent state, which
> > works, but it seems better to simply erase any record of previous
> > quiescent states at the time that the CPU notices the new grace
> > period.  This has the further advantage of removing another piece
> > of RCU for which lockless reasoning is required. 
> 
> So why didn't you do that from the start? :-)

Because I was slow and stupid!  ;-)

> That is, I'm curious to know some history, why was it so and what led
> you to this insight?

I had historically (as in for almost 20 years now) used a counter
to track grace periods.  Now these are in theory subject to integer
overflow, but DYNIX/ptx was non-preemptible, so the general line of
reasoning was that anything that might stall long enough for even a 32-bit
grace-period counter to overflow would necessarily stall grace periods,
thus preventing overflow.

Of course, the advent of CONFIG_PREEMPT in the Linux kernel invalidated
this assumption, but for most uses, if the grace-period counter overflows,
you have waited way more than a grace period, so who cares?

Then combination of TREE_RCU and dyntick-idle came along, and it became
necessary to more carefully associate quiescent states with the corresponding
grace period.  Now here overflow is dangerous, because it can result in
associating an ancient quiescent state with the current grace period.
But my attitude was that if you have a task preempted for more than one
year, getting soft-lockup warnings every two minutes during that time,
well, you got what you deserved.  And even then at very low probability.

However, formal validation software (such as Promela) do not take kindly
to free-running counters.  The usual trick is to use a much narrower
counter.  But that would mean that any attempted mechanical validation
would give a big fat false positive on the counter used to associate
quiescent states with grace periods.  Because I have a long-term goal
of formally validating RCU is it sits in the Linux kernel, that counter
had to go.

And I do believe that the result is easier for humans to understand, so
it is all to the good.

This time, at least.  ;-)

							Thanx, Paul


  reply	other threads:[~2012-09-06 20:02 UTC|newest]

Thread overview: 85+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2012-08-30 18:18 [PATCH tip/core/rcu 0/23] Improvements to RT response on big systems and expedited functions Paul E. McKenney
2012-08-30 18:18 ` [PATCH tip/core/rcu 01/23] rcu: Move RCU grace-period initialization into a kthread Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 02/23] rcu: Allow RCU grace-period initialization to be preempted Paul E. McKenney
2012-09-02  1:09     ` Josh Triplett
2012-09-05  1:22       ` Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 03/23] rcu: Move RCU grace-period cleanup into kthread Paul E. McKenney
2012-09-02  1:22     ` Josh Triplett
2012-09-06 13:34     ` Peter Zijlstra
2012-09-06 17:29       ` Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 04/23] rcu: Allow RCU grace-period cleanup to be preempted Paul E. McKenney
2012-09-02  1:36     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 05/23] rcu: Prevent offline CPUs from executing RCU core code Paul E. McKenney
2012-09-02  1:45     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 06/23] rcu: Break up rcu_gp_kthread() into subfunctions Paul E. McKenney
2012-09-02  2:11     ` Josh Triplett
2012-09-06 13:39     ` Peter Zijlstra
2012-09-06 17:32       ` Paul E. McKenney
2012-09-06 18:49         ` Josh Triplett
2012-09-06 19:09           ` Peter Zijlstra
2012-09-06 20:30             ` Paul E. McKenney
2012-09-06 20:30           ` Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 07/23] rcu: Provide OOM handler to motivate lazy RCU callbacks Paul E. McKenney
2012-09-02  2:13     ` Josh Triplett
2012-09-03  9:08     ` Lai Jiangshan
2012-09-05 17:45       ` Paul E. McKenney
2012-09-06 13:46     ` Peter Zijlstra
2012-09-06 13:52       ` Steven Rostedt
2012-09-06 17:41         ` Paul E. McKenney
2012-09-06 17:46           ` Peter Zijlstra
2012-09-06 20:32             ` Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 08/23] rcu: Segregate rcu_state fields to improve cache locality Paul E. McKenney
2012-09-02  2:51     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 09/23] rcu: Move quiescent-state forcing into kthread Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 10/23] rcu: Allow RCU quiescent-state forcing to be preempted Paul E. McKenney
2012-09-02  5:23     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 11/23] rcu: Adjust debugfs tracing for kthread-based quiescent-state forcing Paul E. McKenney
2012-09-02  6:05     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 12/23] rcu: Prevent force_quiescent_state() memory contention Paul E. McKenney
2012-09-02 10:47     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 13/23] rcu: Control grace-period duration from sysfs Paul E. McKenney
2012-09-03  9:30     ` Josh Triplett
2012-09-03  9:31       ` Josh Triplett
2012-09-06 14:15     ` Peter Zijlstra
2012-09-06 17:53       ` Paul E. McKenney
2012-09-06 18:28         ` Peter Zijlstra
2012-09-06 20:37           ` Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 14/23] rcu: Remove now-unused rcu_state fields Paul E. McKenney
2012-09-03  9:31     ` Josh Triplett
2012-09-06 14:17     ` Peter Zijlstra
2012-09-06 18:02       ` Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 15/23] rcu: Make rcutree module parameters visible in sysfs Paul E. McKenney
2012-09-03  9:32     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 16/23] rcu: Prevent initialization-time quiescent-state race Paul E. McKenney
2012-09-03  9:37     ` Josh Triplett
2012-09-05 18:19       ` Paul E. McKenney
2012-09-05 18:55         ` Josh Triplett
2012-09-05 19:49           ` Paul E. McKenney
2012-09-06 14:21         ` Peter Zijlstra
2012-09-06 16:18           ` Paul E. McKenney
2012-09-06 16:22             ` Peter Zijlstra
2012-08-30 18:18   ` [PATCH tip/core/rcu 17/23] rcu: Fix day-zero grace-period initialization/cleanup race Paul E. McKenney
2012-09-03  9:39     ` Josh Triplett
2012-09-06 14:24     ` Peter Zijlstra
2012-09-06 18:06       ` Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 18/23] rcu: Add random PROVE_RCU_DELAY to grace-period initialization Paul E. McKenney
2012-09-03  9:41     ` Josh Triplett
2012-09-06 14:27     ` Peter Zijlstra
2012-09-06 18:25       ` Paul E. McKenney
2012-08-30 18:18   ` [PATCH tip/core/rcu 19/23] rcu: Adjust for unconditional ->completed assignment Paul E. McKenney
2012-09-03  9:42     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 20/23] rcu: Remove callback acceleration from grace-period initialization Paul E. McKenney
2012-09-03  9:42     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 21/23] rcu: Eliminate signed overflow in synchronize_rcu_expedited() Paul E. McKenney
2012-09-03  9:43     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 22/23] rcu: Reduce synchronize_rcu_expedited() latency Paul E. McKenney
2012-09-03  9:46     ` Josh Triplett
2012-08-30 18:18   ` [PATCH tip/core/rcu 23/23] rcu: Simplify quiescent-state detection Paul E. McKenney
2012-09-03  9:56     ` Josh Triplett
2012-09-06 14:36     ` Peter Zijlstra
2012-09-06 20:01       ` Paul E. McKenney [this message]
2012-09-06 21:18         ` Mathieu Desnoyers
2012-09-06 21:31           ` Paul E. McKenney
2012-09-02  1:04   ` [PATCH tip/core/rcu 01/23] rcu: Move RCU grace-period initialization into a kthread Josh Triplett
2012-09-06 13:32   ` Peter Zijlstra
2012-09-06 17:00     ` Paul E. McKenney

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20120906200138.GR2448@linux.vnet.ibm.com \
    --to=paulmck@linux.vnet.ibm.com \
    --cc=Valdis.Kletnieks@vt.edu \
    --cc=akpm@linux-foundation.org \
    --cc=darren@dvhart.com \
    --cc=dhowells@redhat.com \
    --cc=dipankar@in.ibm.com \
    --cc=eric.dumazet@gmail.com \
    --cc=fweisbec@gmail.com \
    --cc=josh@joshtriplett.org \
    --cc=laijs@cn.fujitsu.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mathieu.desnoyers@polymtl.ca \
    --cc=mingo@elte.hu \
    --cc=niv@us.ibm.com \
    --cc=patches@linaro.org \
    --cc=paul.mckenney@linaro.org \
    --cc=peterz@infradead.org \
    --cc=rostedt@goodmis.org \
    --cc=sbw@mit.edu \
    --cc=tglx@linutronix.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.