| Message ID | 20221218191310.130904-3-joel@joelfernandes.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | srcu: Remove pre-flip memory barrier | expand |
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 >
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
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 --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); /*
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(-)