Re: [PATCH 2/2 RFC] srcu: implement Peter's checking algorithm

[Paul E. McKenney]

On Thu, Mar 01, 2012 at 10:31:22AM +0800, Lai Jiangshan wrote:
> On 02/29/2012 09:55 PM, Paul E. McKenney wrote:
> > On Wed, Feb 29, 2012 at 06:07:32PM +0800, Lai Jiangshan wrote:
> >> On 02/28/2012 09:47 PM, Paul E. McKenney wrote:
> >>> On Tue, Feb 28, 2012 at 09:51:22AM +0800, Lai Jiangshan wrote:
> >>>> On 02/28/2012 02:30 AM, Paul E. McKenney wrote:
> >>>>> On Mon, Feb 27, 2012 at 04:01:04PM +0800, Lai Jiangshan wrote:
> >>>>>> >From 40724998e2d121c2b5a5bd75114625cfd9d4f9a9 Mon Sep 17 00:00:00 2001
> >>>>>> From: Lai Jiangshan <laijs@xxxxxxxxxxxxxx>
> >>>>>> Date: Mon, 27 Feb 2012 14:22:47 +0800
> >>>>>> Subject: [PATCH 2/2] srcu: implement Peter's checking algorithm
> >>>>>>
> >>>>>> This patch implement the algorithm as Peter's:
> >>>>>> https://lkml.org/lkml/2012/2/1/119
> >>>>>>
> >>>>>> o	Make the checking lock-free and we can perform parallel checking,
> >>>>>> 	Although almost parallel checking makes no sense, but we need it
> >>>>>> 	when 1) the original checking task is preempted for long, 2)
> >>>>>> 	sychronize_srcu_expedited(), 3) avoid lock(see next)
> >>>>>>
> >>>>>> o	Since it is lock-free, we save a mutex in state machine for
> >>>>>> 	call_srcu().
> >>>>>>
> >>>>>> o	Remove the SRCU_REF_MASK and remove the coupling with the flipping.
> >>>>>> 	(so we can remove the preempt_disable() in future, but use
> >>>>>> 	 __this_cpu_inc() instead.)
> >>>>>>
> >>>>>> o	reduce a smp_mb(), simplify the comments and make the smp_mb() pairs
> >>>>>> 	more intuitive.
> >>>>>
> >>>>> Hello, Lai,
> >>>>>
> >>>>> Interesting approach!
> >>>>>
> >>>>> What happens given the following sequence of events?
> >>>>>
> >>>>> o	CPU 0 in srcu_readers_active_idx_check() invokes
> >>>>> 	srcu_readers_seq_idx(), getting some number back.
> >>>>>
> >>>>> o	CPU 0 invokes srcu_readers_active_idx(), summing the
> >>>>> 	->c[] array up through CPU 3.
> >>>>>
> >>>>> o	CPU 1 invokes __srcu_read_lock(), and increments its counter
> >>>>> 	but not yet its ->seq[] element.
> >>>>
> >>>>
> >>>> Any __srcu_read_lock() whose increment of active counter is not seen
> >>>> by srcu_readers_active_idx() is considerred as
> >>>> "reader-started-after-this-srcu_readers_active_idx_check()",
> >>>> We don't need to wait.
> >>>>
> >>>> As you said, this srcu C.S 's increment seq is not seen by above
> >>>> srcu_readers_seq_idx().
> >>>>
> >>>>>
> >>>>> o	CPU 0 completes its summing of the ->c[] array, incorrectly
> >>>>> 	obtaining zero.
> >>>>>
> >>>>> o	CPU 0 invokes srcu_readers_seq_idx(), getting the same
> >>>>> 	number back that it got last time.
> >>>>
> >>>> If it incorrectly get zero, it means __srcu_read_unlock() is seen
> >>>> in srcu_readers_active_idx(), and it means the increment of
> >>>> seq is seen in this srcu_readers_seq_idx(), it is different
> >>>> from the above seq that it got last time.
> >>>>
> >>>> increment of seq is not seen by above srcu_readers_seq_idx(),
> >>>> but is seen by later one, so the two returned seq is different,
> >>>> this is the core of Peter's algorithm, and this was written
> >>>> in the comments(Sorry for my bad English). Or maybe I miss
> >>>> your means in this mail.
> >>>
> >>> OK, good, this analysis agrees with what I was thinking.
> >>>
> >>> So my next question is about the lock freedom.  This lock freedom has to
> >>> be limited in nature and carefully implemented.  The reasons for this are:
> >>>
> >>> 1.	Readers can block in any case, which can of course block both
> >>> 	synchronize_srcu_expedited() and synchronize_srcu().
> >>>
> >>> 2.	Because only one CPU at a time can be incrementing ->completed,
> >>> 	some sort of lock with preemption disabling will of course be
> >>> 	needed.  Alternatively, an rt_mutex could be used for its
> >>> 	priority-inheritance properties.
> >>>
> >>> 3.	Once some CPU has incremented ->completed, all CPUs that might
> >>> 	still be summing up the old indexes must stop.  If they don't,
> >>> 	they might incorrectly call a too-short grace period in case of
> >>> 	->seq[]-sum overflow on 32-bit systems.
> >>>
> >>> Or did you have something else in mind?
> >>
> >> When flip happens when check_zero, this check_zero will no be
> >> committed even it is success.
> > 
> > But if the CPU in check_zero isn't blocking the grace period, then
> > ->completed could overflow while that CPU was preempted.  Then how
> > would this CPU know that the flip had happened?
> 
> as you said, check the ->completed.
> but disable the overflow for ->completed.
> 
> there is a spinlock for srcu_struct(including locking for flipping)
> 
> 1) assume we need to wait on widx
> 2) use srcu_read_lock() to hold a reference of the 1-widx active counter
> 3) release the spinlock
> 4) do_check_zero
> 5) gain the spinlock
> 6) srcu_read_unlock()
> 7) if ->completed is not changed, and there is no other later check_zero which
>    is committed earlier than us, we will commit our check_zero if we success.
> 
> too complicated.

Plus I don't see how it disables overflow for ->completed.

As you said earlier, abandoning the goal of lock freedom sounds like the
best approach.  Then you can indeed just hold the srcu_struct's mutex
across the whole thing.

							Thanx, Paul

> Thanks,
> Lai
> 
> > 
> >> I play too much with lock-free for call_srcu(), the code becomes complicated,
> >> I just give up lock-free for call_srcu(), the main aim of call_srcu() is simple.
> > 
> > Makes sense to me!
> > 
> >> (But I still like Peter's approach, it has some other good thing
> >> besides lock-free-checking, if you don't like it, I will send
> >> another patch to fix srcu_readers_active())
> > 
> > Try them both and check their performance &c.  If within espilon of
> > each other, pick whichever one you prefer.
> > 
> > 							Thanx, Paul
> 

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/