[QUESTION] srcu: Remove the SCAN2 state

[QUESTION] srcu: Remove the SCAN2 state

[Byungchul Park]

Hello,

I'm sorry for bothering you, and I seem to be obviously missing
something, but I'm really wondering why we check try_check_zero()
again in the state, SCAN1, for the previous srcu_idx.

I mean, since we've already checked try_check_zero() in the previous
grace period and gotten 'true' as a return value, all readers who see
the flipped idx via srcu_flip() won't update the src_{lock,unlock}_count
for the previous idx until it gets flipped back again.

Is there any reasons we check try_check_zero() again in the state, SCAN1?
Is there any problems if the following patch's applied?

Thanks in advance,
Byungchul

---
 kernel/rcu/srcutree.c | 16 +---------------
 1 file changed, 1 insertion(+), 15 deletions(-)

diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index 39e50fe..215c44a 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -1125,24 +1125,10 @@ static void srcu_advance_state(struct srcu_struct *sp)
 			mutex_unlock(&sp->srcu_gp_mutex);
 			return; /* Someone else started the grace period. */
 		}
-	}
-
-	if (rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) == SRCU_STATE_SCAN1) {
-		idx = 1 ^ (sp->srcu_idx & 1);
-		if (!try_check_zero(sp, idx, 1)) {
-			mutex_unlock(&sp->srcu_gp_mutex);
-			return; /* readers present, retry later. */
-		}
 		srcu_flip(sp);
-		rcu_seq_set_state(&sp->srcu_gp_seq, SRCU_STATE_SCAN2);
 	}
 
-	if (rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) == SRCU_STATE_SCAN2) {
-
-		/*
-		 * SRCU read-side critical sections are normally short,
-		 * so check at least twice in quick succession after a flip.
-		 */
+	if (rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) == SRCU_STATE_SCAN1) {
 		idx = 1 ^ (sp->srcu_idx & 1);
 		if (!try_check_zero(sp, idx, 2)) {
 			mutex_unlock(&sp->srcu_gp_mutex);
-- 
1.9.1

Re: [QUESTION] srcu: Remove the SCAN2 state

[Paul E. McKenney]

On Thu, Feb 22, 2018 at 08:57:27AM +0900, Byungchul Park wrote:
> Hello,
> 
> I'm sorry for bothering you, and I seem to be obviously missing
> something, but I'm really wondering why we check try_check_zero()
> again in the state, SCAN1, for the previous srcu_idx.
> 
> I mean, since we've already checked try_check_zero() in the previous
> grace period and gotten 'true' as a return value, all readers who see
> the flipped idx via srcu_flip() won't update the src_{lock,unlock}_count
> for the previous idx until it gets flipped back again.
> 
> Is there any reasons we check try_check_zero() again in the state, SCAN1?
> Is there any problems if the following patch's applied?

Indeed there are!  Removing the second scan exposes us to a nasty race
condition where a reader is preempted (or interrupted or whatever) just
after fetching its counter.  A detailed explanation for an essentially
equivalent race in userspace RCU may be found on the second column of
page 7 of this PDF:

http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf

But please let me know if I am missing the point of your patch below.

							Thanx, Paul

> Thanks in advance,
> Byungchul
> 
> ---
>  kernel/rcu/srcutree.c | 16 +---------------
>  1 file changed, 1 insertion(+), 15 deletions(-)
> 
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index 39e50fe..215c44a 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -1125,24 +1125,10 @@ static void srcu_advance_state(struct srcu_struct *sp)
>  			mutex_unlock(&sp->srcu_gp_mutex);
>  			return; /* Someone else started the grace period. */
>  		}
> -	}
> -
> -	if (rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) == SRCU_STATE_SCAN1) {
> -		idx = 1 ^ (sp->srcu_idx & 1);
> -		if (!try_check_zero(sp, idx, 1)) {
> -			mutex_unlock(&sp->srcu_gp_mutex);
> -			return; /* readers present, retry later. */
> -		}
>  		srcu_flip(sp);
> -		rcu_seq_set_state(&sp->srcu_gp_seq, SRCU_STATE_SCAN2);
>  	}
> 
> -	if (rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) == SRCU_STATE_SCAN2) {
> -
> -		/*
> -		 * SRCU read-side critical sections are normally short,
> -		 * so check at least twice in quick succession after a flip.
> -		 */
> +	if (rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) == SRCU_STATE_SCAN1) {
>  		idx = 1 ^ (sp->srcu_idx & 1);
>  		if (!try_check_zero(sp, idx, 2)) {
>  			mutex_unlock(&sp->srcu_gp_mutex);
> -- 
> 1.9.1
> 

Re: [QUESTION] srcu: Remove the SCAN2 state

[Byungchul Park]

On 2/22/2018 11:11 AM, Paul E. McKenney wrote:
> On Thu, Feb 22, 2018 at 08:57:27AM +0900, Byungchul Park wrote:
>> Hello,
>>
>> I'm sorry for bothering you, and I seem to be obviously missing
>> something, but I'm really wondering why we check try_check_zero()
>> again in the state, SCAN1, for the previous srcu_idx.
>>
>> I mean, since we've already checked try_check_zero() in the previous
>> grace period and gotten 'true' as a return value, all readers who see
>> the flipped idx via srcu_flip() won't update the src_{lock,unlock}_count
>> for the previous idx until it gets flipped back again.
>>
>> Is there any reasons we check try_check_zero() again in the state, SCAN1?
>> Is there any problems if the following patch's applied?
> 
> Indeed there are!  Removing the second scan exposes us to a nasty race
> condition where a reader is preempted (or interrupted or whatever) just

Indeed! I missed the cases. It should be as it is.

Thanks a lot for pointing it out.

> after fetching its counter.  A detailed explanation for an essentially

-- 
Thanks,
Byungchul

Re: [QUESTION] srcu: Remove the SCAN2 state

[Paul E. McKenney]

On Thu, Feb 22, 2018 at 02:05:18PM +0900, Byungchul Park wrote:
> On 2/22/2018 11:11 AM, Paul E. McKenney wrote:
> >On Thu, Feb 22, 2018 at 08:57:27AM +0900, Byungchul Park wrote:
> >>Hello,
> >>
> >>I'm sorry for bothering you, and I seem to be obviously missing
> >>something, but I'm really wondering why we check try_check_zero()
> >>again in the state, SCAN1, for the previous srcu_idx.
> >>
> >>I mean, since we've already checked try_check_zero() in the previous
> >>grace period and gotten 'true' as a return value, all readers who see
> >>the flipped idx via srcu_flip() won't update the src_{lock,unlock}_count
> >>for the previous idx until it gets flipped back again.
> >>
> >>Is there any reasons we check try_check_zero() again in the state, SCAN1?
> >>Is there any problems if the following patch's applied?
> >
> >Indeed there are!  Removing the second scan exposes us to a nasty race
> >condition where a reader is preempted (or interrupted or whatever) just
> 
> Indeed! I missed the cases. It should be as it is.
> 
> Thanks a lot for pointing it out.

Heh!  Everyone I know, myself included, who has written such an algorithm
has had this bug in their initial version.  In one case, the algorithm
was published in a high-end journal and the bug not spotted for more than
a decade.  I suppose I could brag about Mathieu's and my offerings having
been corrected before we published, but the fact remains that an earlier
publication of mine gave the aforementioned algorithm from the high-end
journal as an alternative implementation, and I did not spot the bug.
Nor did any of my co-authors.  ;-)

							Thanx, Paul

> >after fetching its counter.  A detailed explanation for an essentially
> 
> -- 
> Thanks,
> Byungchul
>