diff mbox series

[RFC,2/2] srcu: Remove memory barrier "E" as it is not required

Message ID 20221218191310.130904-3-joel@joelfernandes.org
State New
Headers
Series srcu: Remove pre-flip memory barrier |

Commit Message

Joel Fernandes Dec. 18, 2022, 7:13 p.m. UTC 
  During a flip, we have a full memory barrier before idx is incremented.

The effect of this seems to be to guarantee that, if a READER sees srcu_idx
updates (srcu_flip), then prior scans would not see its updates to counters on
that index.

That does not matter because of the following reason: If a prior scan did see
counter updates on the new index, that means the prior scan would would wait
for the reader when it probably did not need to.

And if the prior scan did see both lock and unlock count updates on that index,
that reader is essentially done, so it is OK to end the grace period.

For this reason, remove the full memory barrier before incrementing
srcu_idx.

6 hours of testing shows all SRCU-* scenarios pass with this.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
 kernel/rcu/srcutree.c | 8 --------
 1 file changed, 8 deletions(-)

Comments

Frederic Weisbecker Dec. 18, 2022, 9:42 p.m. UTC | #1 
On Sun, Dec 18, 2022 at 07:13:09PM +0000, Joel Fernandes (Google) wrote:
> During a flip, we have a full memory barrier before idx is incremented.
> 
> The effect of this seems to be to guarantee that, if a READER sees srcu_idx
> updates (srcu_flip), then prior scans would not see its updates to counters on
> that index.
> 
> That does not matter because of the following reason: If a prior scan did see
> counter updates on the new index, that means the prior scan would would wait
> for the reader when it probably did not need to.

I'm confused, isn't it actually what we want to prevent from?
The point of the barrier here is to make sure that the inactive index that
we just scanned is guaranteed to remain seen as inactive during the whole scan
(minus the possible twice residual increments from a given task that we debated
on Paul's patch, but we want the guarantee that the inactive index won't be
incremented thrice by a given task or any further while we are scanning it).

If some readers see the new index and increments the lock and we see that while
we are scanning it, there is a risk that the GP is going to be delayed indefinetly.

> @@ -982,14 +982,6 @@ static bool try_check_zero(struct srcu_struct *ssp, int idx, int trycount)
>   */
>  static void srcu_flip(struct srcu_struct *ssp)
>  {
> -	/*
> -	 * Ensure that if a given reader sees the new value of ->srcu_idx, this
> -	 * updater's earlier scans cannot have seen that reader's increments
> -	 * (which is OK, because this grace period need not wait on that
> -	 * reader).
> -	 */
> -	smp_mb(); /* E */  /* Pairs with B and C. */

That said, I've been starring at this very barrier for the whole day, and I'm
wondering what does it match exactly on the other end?

      UPDATER                               READER
      -------                               ------
      idx = ssp->srcu_idx;                  idx = srcu_idx;
      READ srcu_unlock_count[srcu_idx ^ 1]  srcu_lock_count[idx]++
      smp_mb();                             smp_mb();
      READ srcu_lock_count[srcu_idx ^ 1]    srcu_unlock_count[old_idx]++
      smp_mb()
      srcu_idx++;

For a true match, I would expect a barrier between srcu_idx read and
srcu_lock_count write. I'm not used to ordering writes after reads.
So what is the pattern here? I would expect something like the below
but that doesn't match the above:

C rwrw

{}


P0(int *X, int *Y)
{
	int x;

	x = READ_ONCE(*X);
	smp_mb();
	WRITE_ONCE(*Y, 1);
}

P1(int *X, int *Y)
{

	int y;

	y = READ_ONCE(*Y);
	smp_mb();
	WRITE_ONCE(*X, 1);
}

exists (0:x=1 /\ 1:y=1)


> -
>  	WRITE_ONCE(ssp->srcu_idx, ssp->srcu_idx + 1);
>  
>  	/*
> -- 
> 2.39.0.314.g84b9a713c41-goog
>
Joel Fernandes Dec. 18, 2022, 11:26 p.m. UTC | #2 
On Sun, Dec 18, 2022 at 10:42:43PM +0100, Frederic Weisbecker wrote:
> On Sun, Dec 18, 2022 at 07:13:09PM +0000, Joel Fernandes (Google) wrote:
> > During a flip, we have a full memory barrier before idx is incremented.
> > 
> > The effect of this seems to be to guarantee that, if a READER sees srcu_idx
> > updates (srcu_flip), then prior scans would not see its updates to counters on
> > that index.
> > 
> > That does not matter because of the following reason: If a prior scan did see
> > counter updates on the new index, that means the prior scan would would wait
> > for the reader when it probably did not need to.
> 
> I'm confused, isn't it actually what we want to prevent from?
> The point of the barrier here is to make sure that the inactive index that
> we just scanned is guaranteed to remain seen as inactive during the whole scan
> (minus the possible twice residual increments from a given task that we debated
> on Paul's patch, but we want the guarantee that the inactive index won't be
> incremented thrice by a given task or any further while we are scanning it).

I believe you are talking about the memory barrier after the flip, that's the
one that guarantees what you are talking about it, I feel. That is, readers
see the newly inactivated index eventually, so that we are not scanning
indefinitely.

For that, we need smp_mb() after the flip but before the second scan which is
a much needed memory barrier IMHO, and not what this patch is talking about.

> If some readers see the new index and increments the lock and we see that while
> we are scanning it, there is a risk that the GP is going to be delayed indefinetly.

The "new" index is the index after the flip, do you mean the "old" index?
i.e. the index before the flip? That is what barrier E is talking about, not
the index after the flip.

> 
> > @@ -982,14 +982,6 @@ static bool try_check_zero(struct srcu_struct *ssp, int idx, int trycount)
> >   */
> >  static void srcu_flip(struct srcu_struct *ssp)
> >  {
> > -	/*
> > -	 * Ensure that if a given reader sees the new value of ->srcu_idx, this
> > -	 * updater's earlier scans cannot have seen that reader's increments
> > -	 * (which is OK, because this grace period need not wait on that
> > -	 * reader).
> > -	 */
> > -	smp_mb(); /* E */  /* Pairs with B and C. */
> 
> That said, I've been starring at this very barrier for the whole day, and I'm
> wondering what does it match exactly on the other end?
> 
>       UPDATER                               READER
>       -------                               ------
>       idx = ssp->srcu_idx;                  idx = srcu_idx;
>       READ srcu_unlock_count[srcu_idx ^ 1]  srcu_lock_count[idx]++
>       smp_mb();                             smp_mb();
>       READ srcu_lock_count[srcu_idx ^ 1]    srcu_unlock_count[old_idx]++
>       smp_mb()
>       srcu_idx++;
> 
> For a true match, I would expect a barrier between srcu_idx read and
> srcu_lock_count write. I'm not used to ordering writes after reads.
> So what is the pattern here? I would expect something like the below
> but that doesn't match the above:

IMHO, it is matching updates to index and the lock count of a reader.

> 
> C rwrw
> 
> {}
> 
> 
> P0(int *X, int *Y)
> {
> 	int x;
> 
> 	x = READ_ONCE(*X);
> 	smp_mb();
> 	WRITE_ONCE(*Y, 1);
> }
> 
> P1(int *X, int *Y)
> {
> 
> 	int y;
> 
> 	y = READ_ONCE(*Y);
> 	smp_mb();
> 	WRITE_ONCE(*X, 1);
> }
> 
> exists (0:x=1 /\ 1:y=1)

Hmm, I guess first lets degenerate the real code to an access pattern:


    READER                            UPDATER

                		    scanner() {
				    	count_all_unlocks();
				    	smp_mb();
                                        count_all_locks(); (Y)
	            		    }

    rcu_read_lock() {
        idx = READ(idx); (X)
        lock_count[idx]++;

        smp_mb();    // mb B
    }

    rcu_read_unlock() {
        smp_mb();    // mb C
        unlock_count[idx]++;
    }
                                    srcu_flip() {
                                        smp_mb(); //E
                                        idx++; (X)
    rcu_read_lock() {
        idx = READ(idx);
        lock_count[idx]++; (Y)

        smp_mb();    // mb B
                                        smp_mb();
                                    }
    }


That becomes:

// READER
P0(int *X, int *Y)
{
	int r0;

 	r0 = READ_ONCE(*X);	// PP
 	smp_mb(); // B+C	// QQ
 	WRITE_ONCE(*Y, 1);	// RR
}

// UPDATER
P1(int *X, int *Y)
{
	int r1;

 	r1 = READ_ONCE(*Y);	// SS
 	smp_mb(); // E		// TT
 	WRITE_ONCE(*X, 1);	// UU
}

Impossible that:
exists (0:r0=1 /\ 1: r1:1)

Because if r0=1, there is PP ->rf UU relation. So because of the smp_mb(), it
is impossible that r1=1.

So "E" is saying, if a reader saw new idx, that is the "X" in the litmus
test, then previous scan where it count all the locks (SS) cannot see the
lock count updates made at the new index.

However, that does not matter IMHO because due to preemption after current
index is sampled, we have no control anyway over which lock counts are
incremented anyway, so this cannot effect correctness.

And if forward progress is a problem, we are doing a full memory barrier
after the flip anyway so I am not seeing the point of "E".

thanks,

 - Joel
Joel Fernandes Dec. 19, 2022, 12:30 a.m. UTC | #3 
On Sun, Dec 18, 2022 at 6:26 PM Joel Fernandes <joel@joelfernandes.org> wrote:
>
> On Sun, Dec 18, 2022 at 10:42:43PM +0100, Frederic Weisbecker wrote:
> > On Sun, Dec 18, 2022 at 07:13:09PM +0000, Joel Fernandes (Google) wrote:
> > > During a flip, we have a full memory barrier before idx is incremented.
> > >
> > > The effect of this seems to be to guarantee that, if a READER sees srcu_idx
> > > updates (srcu_flip), then prior scans would not see its updates to counters on
> > > that index.
> > >
> > > That does not matter because of the following reason: If a prior scan did see
> > > counter updates on the new index, that means the prior scan would would wait
> > > for the reader when it probably did not need to.
> >
> > I'm confused, isn't it actually what we want to prevent from?
> > The point of the barrier here is to make sure that the inactive index that
> > we just scanned is guaranteed to remain seen as inactive during the whole scan
> > (minus the possible twice residual increments from a given task that we debated
> > on Paul's patch, but we want the guarantee that the inactive index won't be
> > incremented thrice by a given task or any further while we are scanning it).
>
> I believe you are talking about the memory barrier after the flip, that's the
> one that guarantees what you are talking about it, I feel. That is, readers
> see the newly inactivated index eventually, so that we are not scanning
> indefinitely.
>
> For that, we need smp_mb() after the flip but before the second scan which is
> a much needed memory barrier IMHO, and not what this patch is talking about.
>
> > If some readers see the new index and increments the lock and we see that while
> > we are scanning it, there is a risk that the GP is going to be delayed indefinetly.
>
> The "new" index is the index after the flip, do you mean the "old" index?
> i.e. the index before the flip? That is what barrier E is talking about, not
> the index after the flip.
>
> >
> > > @@ -982,14 +982,6 @@ static bool try_check_zero(struct srcu_struct *ssp, int idx, int trycount)
> > >   */
> > >  static void srcu_flip(struct srcu_struct *ssp)
> > >  {
> > > -   /*
> > > -    * Ensure that if a given reader sees the new value of ->srcu_idx, this
> > > -    * updater's earlier scans cannot have seen that reader's increments
> > > -    * (which is OK, because this grace period need not wait on that
> > > -    * reader).
> > > -    */
> > > -   smp_mb(); /* E */  /* Pairs with B and C. */
> >
> > That said, I've been starring at this very barrier for the whole day, and I'm
> > wondering what does it match exactly on the other end?
> >
> >       UPDATER                               READER
> >       -------                               ------
> >       idx = ssp->srcu_idx;                  idx = srcu_idx;
> >       READ srcu_unlock_count[srcu_idx ^ 1]  srcu_lock_count[idx]++
> >       smp_mb();                             smp_mb();
> >       READ srcu_lock_count[srcu_idx ^ 1]    srcu_unlock_count[old_idx]++
> >       smp_mb()
> >       srcu_idx++;
> >
> > For a true match, I would expect a barrier between srcu_idx read and
> > srcu_lock_count write. I'm not used to ordering writes after reads.
> > So what is the pattern here? I would expect something like the below
> > but that doesn't match the above:
>
> IMHO, it is matching updates to index and the lock count of a reader.
>
> >
> > C rwrw
> >
> > {}
> >
> >
> > P0(int *X, int *Y)
> > {
> >       int x;
> >
> >       x = READ_ONCE(*X);
> >       smp_mb();
> >       WRITE_ONCE(*Y, 1);
> > }
> >
> > P1(int *X, int *Y)
> > {
> >
> >       int y;
> >
> >       y = READ_ONCE(*Y);
> >       smp_mb();
> >       WRITE_ONCE(*X, 1);
> > }
> >
> > exists (0:x=1 /\ 1:y=1)
>
> Hmm, I guess first lets degenerate the real code to an access pattern:
>
>
>     READER                            UPDATER
>
>                                     scanner() {
>                                         count_all_unlocks();
>                                         smp_mb();
>                                         count_all_locks(); (Y)
>                                     }
>
>     rcu_read_lock() {
>         idx = READ(idx); (X)
>         lock_count[idx]++;
>
>         smp_mb();    // mb B
>     }
>
>     rcu_read_unlock() {
>         smp_mb();    // mb C
>         unlock_count[idx]++;
>     }
>                                     srcu_flip() {
>                                         smp_mb(); //E
>                                         idx++; (X)
>     rcu_read_lock() {
>         idx = READ(idx);
>         lock_count[idx]++; (Y)
>
>         smp_mb();    // mb B
>                                         smp_mb();
>                                     }
>     }
>
>
> That becomes:
>
> // READER
> P0(int *X, int *Y)
> {
>         int r0;
>
>         r0 = READ_ONCE(*X);     // PP
>         smp_mb(); // B+C        // QQ
>         WRITE_ONCE(*Y, 1);      // RR
> }
>
> // UPDATER
> P1(int *X, int *Y)
> {
>         int r1;
>
>         r1 = READ_ONCE(*Y);     // SS
>         smp_mb(); // E          // TT
>         WRITE_ONCE(*X, 1);      // UU
> }
>
> Impossible that:
> exists (0:r0=1 /\ 1: r1:1)
>
> Because if r0=1, there is PP ->rf UU relation. So because of the smp_mb(), it
> is impossible that r1=1.
>
> So "E" is saying, if a reader saw new idx, that is the "X" in the litmus
> test, then previous scan where it count all the locks (SS) cannot see the
> lock count updates made at the new index.
>
> However, that does not matter IMHO because due to preemption after current
> index is sampled, we have no control anyway over which lock counts are
> incremented anyway, so this cannot effect correctness.
>
> And if forward progress is a problem, we are doing a full memory barrier
> after the flip anyway so I am not seeing the point of "E".

And you made me realize that the previous scan (the one that happened
before the flip) does not care about lock count on the "new" idx value
(because, duh, in program order, the previous scan was scanning the
old pre-flip idx0, and if we go for scans before that, we end up
running into smp_mb() in the previous scan which is plenty enough. So
I am still not seeing the purpose that "E" serves, as far as it
concerns the comment that this patch deletes.

Anyway, phew, time for a break ;-)
Thanks,

 - Joel
diff mbox series

Patch

diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index d6a4c2439ca6..2d2e6d304a43 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -982,14 +982,6 @@  static bool try_check_zero(struct srcu_struct *ssp, int idx, int trycount)
  */
 static void srcu_flip(struct srcu_struct *ssp)
 {
-	/*
-	 * Ensure that if a given reader sees the new value of ->srcu_idx, this
-	 * updater's earlier scans cannot have seen that reader's increments
-	 * (which is OK, because this grace period need not wait on that
-	 * reader).
-	 */
-	smp_mb(); /* E */  /* Pairs with B and C. */
-
 	WRITE_ONCE(ssp->srcu_idx, ssp->srcu_idx + 1);
 
 	/*