Re: [RFC 0/2] srcu: Remove pre-flip memory barrier

Mathieu Desnoyers
2022-12-18T23:38:43Z

On 2022-12-18 16:30, Joel Fernandes wrote:
> Hi Mathieu,
>
> On Sun, Dec 18, 2022 at 3:56 PM Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
>>
>> On 2022-12-18 14:13, Joel Fernandes (Google) wrote:
>>> Hello, I believe the pre-flip memory barrier is not required. The only reason I
>>> can say to remove it, other than the possibility that it is unnecessary, is to
>>> not have extra code that does not help. However, since we are issuing a fully
>>> memory-barrier after the flip, I cannot say that it hurts to do it anyway.
>>>
>>> For this reason, please consider these patches as "informational", than a
>>> "please merge". :-) Though, feel free to consider merging if you agree!
>>>
>>> All SRCU scenarios pass with these, with 6 hours of testing.
>>
>> Hi Joel,
>>
>> Please have a look at the comments in my side-rcu implementation [1, 2].
>> It is similar to what SRCU does (per-cpu counter based grace period
>> tracking), but implemented for userspace. The comments explain why this
>> works without the memory barrier you identify as useless in SRCU.
>>
>> Following my implementation of side-rcu, I reviewed the SRCU comments
>> and identified that the barrier "/* E */" appears to be useless. I even
>> discussed this privately with Paul E. McKenney.
>>
>> My implementation and comments go further though, and skip the period
>> "flip" entirely if the first pass observes that all readers (in both
>> periods) are quiescent.
>
> Actually in SRCU, the first pass scans only 1 index, then does the
> flip, and the second pass scans the second index. Without doing a
> flip, an index cannot be scanned for forward progress reasons because
> it is still "active". So I am curious how you can skip flip and still
> scan both indexes? I will dig more into your implementation to learn more.

If we look at SRCU read-side:

int __srcu_read_lock(struct srcu_struct *ssp)
{
int idx;

idx = READ_ONCE(ssp->srcu_idx) & 0x1;
this_cpu_inc(ssp->sda->srcu_lock_count[idx]);
smp_mb(); /* B */ /* Avoid leaking the critical section. */
return idx;
}

If the thread is preempted for a long period of time between load of
ssp->srcu_idx and increment of srcu_lock_count[idx], this means this
thread can appear as a "new reader" for the idx period at any arbitrary
time in the future, independently of which period is the current one
within a future grace period.

As a result, the grace period algorithm needs to inherently support the
fact that a "new reader" can appear in any of the two periods,
independently of the current period state.

As a result, this means that while within period "0", we _need_ to allow
newly coming readers to appear as we scan period "0".

As a result, we can simply scan both periods 0/1 for reader quiescence,
even while new readers appear within those periods.

As a result, flipping between periods 0/1 is just relevant for forward
progress, not for correctness.

As a result, we can remove barrier /* E */.

Thoughts ?

Thanks,

Mathieu

>
>> The most relevant comment in side-rcu is:
>>
>> * The grace period completes when it observes that there are no active
>> * readers within each of the periods.
>> *
>> * The active_readers state is initially true for each period, until the
>> * grace period observes that no readers are present for each given
>> * period, at which point the active_readers state becomes false.
>>
>> So I agree with the clarifications you propose here, but I think we can
>> improve the grace period implementation further by clarifying the SRCU
>> grace period model.
>
> Thanks a lot, I am curious how you do the "detection of no new
> readers" part without globally doing some kind of synchronization. I
> will dig more into your implementation to learn more.
>
> Thanks,
>
> - Joel
>
>
>
>>
>> Thanks,
>>
>> Mathieu
>>
>>
>> [1] https://github.com/efficios/libside/blob/master/src/rcu.h
>> [2] https://github.com/efficios/libside/blob/master/src/rcu.c
>>
>>>
>>> thanks,
>>>
>>> - Joel
>>>
>>> Joel Fernandes (Google) (2):
>>> srcu: Remove comment about prior read lock counts
>>> srcu: Remove memory barrier "E" as it is not required
>>>
>>> kernel/rcu/srcutree.c | 10 ----------
>>> 1 file changed, 10 deletions(-)
>>>
>>> --
>>> 2.39.0.314.g84b9a713c41-goog
>>>
>>
>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> https://www.efficios.com
>>

--
Mathieu Desnoyers
EfficiOS Inc.