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

[Lai Jiangshan <laijs@cn.fujitsu.com>]

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@cn.fujitsu.com>
>>>>>> 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.

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