On Thu, May 12, 2005 at 10:24:37AM +0200, Peter Zijlstra wrote:
> On Tue, 2005-05-10 at 15:36 -0700, Paul E. McKenney wrote:

[ . . . ]

> > > > But the flip is an integral part of detecting a grace period.  So, if I
> > > > understand your proposal correctly, I would have to flip to figure out
> > > > when it was safe to flip.
> > > > 
> > > > What am I missing here?
> > > 
> > > 
> > > int can_flip = 1;
> > > int selector = 0;
> > > 
> > > int counter[2] = {0, 0};
> > > 
> > > void up()
> > > {
> > >   ++counter[current->selection = selector];
> > 
> > Suppose task 0 has just fetched the value of "selector".  How does
> > force_grace() know that it is now inappropriate to invert the value
> > of "selector"?
> > 
> > One might suppress preemption, but there can still be interrupts,
> > ECC error correction, and just plain bad luck.  So up() needs to
> > be able to deal with "selector" getting inverted out from under it.
> > 
> > Unless I am missing something still...
> 
> True, I see you point; there is a race between the = and ++ operators.
> 
> current->selection = selector;
> --> gap
> ++counter[current->selection];
> 
> if you flip and the then old current->selection reached 0 before this
> task gets executed again do_grace gets called and cleans the callbacks;
> which should not matter since this task has not yet started using any
> data. however it will be problematic because when it does get scheduled
> again it works on the wrong counter and thus does not prevent a grace
> period on the data will be using.

Yep, that is indeed my concern.

> however I assumed you had these problems solved with your counter-based
> approach. My code was meant to illustrate how I thought your double
> inversion problem could be avoided.
> 
> Do you by any chance have a RCU impl. based on the counter-based
> approach so I can try to understand and maybe try to intergrate my
> ideas?

There are a couple of counter-based implementations out there:

o	The K42/Tornado implementation of RCU.

o	Dipankar Sarma's rcu_preempt-2.5.8-3.patch and
	rcu_poll_preempt-2.5.14-2.patch that were proposed for
	Linux some years back.  These are attached.

Both of these can potentially suffer from huge grace periods, though
the K42/Tornado guys may have come up with some tricks to avoid this
by now.  These long grace periods were why the above patches were
passed over for Linux's RCU.

Both of these also rely on the fact that the time interval between
a pair of counter switches must have context switches on all CPUs
(or threads, depending on the exact implementation).  We need to
avoid this requirement in CONFIG_PREEMPT_RT in order to deal with
small-memory environments.

						Thanx, Paul