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

From: Joel Fernandes
Date: Wed Dec 21 2022 - 14:58:10 EST

Mathieu pointed out to me on IRC that adding the control dep on the
update side removes even that need for E. And I see that is what Boqun
was suggesting above and that Frederic modified.

See updated litmus here: https://www.irccloud.com/pastebin/TrXacogO/

With this, I am not seeing the "bad condition" happen.

On Wed, Dec 21, 2022 at 7:33 PM Joel Fernandes <joel@xxxxxxxxxxxxxxxxx> wrote:
>
> Ah Frederic, I think you nailed it. E is required to order the flip
> write with the control-dependency on the READ side. I can confirm the
> below test with bad condition shows the previous reader sees the
> post-flip index when it shouldn't have. Please see below modifications
> to your Litmus test.
>
> I think we should document it in the code that E pairs with the
> control-dependency between idx read and lock count write.
>
> C srcu
> {}
> // updater
> P0(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
> {
> int lock1;
> int unlock1;
> int lock0;
> int unlock0;
>
> // SCAN1
> unlock1 = READ_ONCE(*UNLOCK1);
> smp_mb(); // A
> lock1 = READ_ONCE(*LOCK1);
>
> // FLIP
> smp_mb(); // E -------------------- required to make the bad
> condition not happen.
> WRITE_ONCE(*IDX, 1);
> smp_mb(); // D
>
> // SCAN2
> unlock0 = READ_ONCE(*UNLOCK0);
> smp_mb(); // A
> lock0 = READ_ONCE(*LOCK0);
> }
>
> // reader
> P1(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
> {
> int tmp;
> int idx1;
> int idx2;
>
> // 1st reader
> idx1 = READ_ONCE(*IDX);
> if (idx1 == 0) {
> tmp = READ_ONCE(*LOCK0);
> WRITE_ONCE(*LOCK0, tmp + 1);
> smp_mb(); /* B and C */
> tmp = READ_ONCE(*UNLOCK0);
> WRITE_ONCE(*UNLOCK0, tmp + 1);
> } else {
> tmp = READ_ONCE(*LOCK1);
> WRITE_ONCE(*LOCK1, tmp + 1);
> smp_mb(); /* B and C */
> tmp = READ_ONCE(*UNLOCK1);
> WRITE_ONCE(*UNLOCK1, tmp + 1);
> }
>
> // second reader
> idx2 = READ_ONCE(*IDX);
> if (idx2 == 0) {
> tmp = READ_ONCE(*LOCK0);
> WRITE_ONCE(*LOCK0, tmp + 1);
> smp_mb(); /* B and C */
> tmp = READ_ONCE(*UNLOCK0);
> WRITE_ONCE(*UNLOCK0, tmp + 1);
> } else {
> tmp = READ_ONCE(*LOCK1);
> WRITE_ONCE(*LOCK1, tmp + 1);
> smp_mb(); /* B and C */
> tmp = READ_ONCE(*UNLOCK1);
> WRITE_ONCE(*UNLOCK1, tmp + 1);
> }
> }
>
> exists (0:lock1=1 /\ 1:idx1=1 /\ 1:idx2=1 ) (* bad condition: 1st
> reader saw flip *)
>
>
>
>
>
> On Wed, Dec 21, 2022 at 5:30 PM Frederic Weisbecker <frederic@xxxxxxxxxx> wrote:
> >
> > On Wed, Dec 21, 2022 at 08:02:28AM -0800, Boqun Feng wrote:
> > > On Wed, Dec 21, 2022 at 12:26:29PM +0100, Frederic Weisbecker wrote:
> > > > On Tue, Dec 20, 2022 at 09:41:17PM -0500, Joel Fernandes wrote:
> > > > >
> > > > >
> > > > > > On Dec 20, 2022, at 7:50 PM, Frederic Weisbecker <frederic@xxxxxxxxxx> wrote:
> > > > > >
> > > > > > On Tue, Dec 20, 2022 at 07:15:00PM -0500, Joel Fernandes wrote:
> > > > > >> On Tue, Dec 20, 2022 at 5:45 PM Frederic Weisbecker <frederic@xxxxxxxxxx> wrote:
> > > > > >> Agreed about (1).
> > > > > >>
> > > > > >>> _ In (2), E pairs with the address-dependency between idx and lock_count.
> > > > > >>
> > > > > >> But that is not the only reason. If that was the only reason for (2),
> > > > > >> then there is an smp_mb() just before the next-scan post-flip before
> > > > > >> the lock counts are read.
> > > > > >
> > > > > > The post-flip barrier makes sure the new idx is visible on the next READER's
> > > > > > turn, but it doesn't protect against the fact that "READ idx then WRITE lock[idx]"
> > > > > > may appear unordered from the update side POV if there is no barrier between the
> > > > > > scan and the flip.
> > > > > >
> > > > > > If you remove the smp_mb() from the litmus test I sent, things explode.
> > > > >
> > > > > Sure I see what you are saying and it’s a valid point as well. However why do you need memory barrier D (labeled such in the kernel code) for that? You already have a memory barrier A before the lock count is read. That will suffice for the ordering pairing with the addr dependency.
> > > > > In other words, if updater sees readers lock counts, then reader would be making those lock count updates on post-flip inactive index, not the one being scanned as you wanted, and you will accomplish that just with the mem barrier A.
> > > > >
> > > > > So D fixes the above issue you are talking about (lock count update), however that is already fixed by the memory barrier A. But you still need D for the issue I mentioned (unlock counts vs flip).
> > > > >
> > > > > That’s just my opinion and let’s discuss more because I cannot rule out that I
> > > > > am missing something with this complicated topic ;-)
> > > >
> > > > I must be missing something. I often do.
> > > >
> > > > Ok let's put that on litmus:
> > > >
> > > > ----
> > > > C srcu
> > > >
> > > > {}
> > > >
> > > > // updater
> > > > P0(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
> > > > {
> > > > int lock1;
> > > > int unlock1;
> > > > int lock0;
> > > > int unlock0;
> > > >
> > > > // SCAN1
> > > > unlock1 = READ_ONCE(*UNLOCK1);
> > > > smp_mb(); // A
> > > > lock1 = READ_ONCE(*LOCK1);
> > > >
> > > > // FLIP
> > > > smp_mb(); // E
> > >
> > > In real code there is a control dependency between the READ_ONCE() above
> > > and the WRITE_ONCE() before, i.e. only flip the idx when lock1 ==
> > > unlock1, maybe try with the P0 below? Untested due to not having herd on
> > > this computer ;-)
> > >
> > > > WRITE_ONCE(*IDX, 1);
> > > > smp_mb(); // D
> > > >
> > > > // SCAN2
> > > > unlock0 = READ_ONCE(*UNLOCK0);
> > > > smp_mb(); // A
> > > > lock0 = READ_ONCE(*LOCK0);
> > > > }
> > > >
> > > P0(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
> > > {
> > > int lock1;
> > > int unlock1;
> > > int lock0;
> > > int unlock0;
> > >
> > > // SCAN1
> > > unlock1 = READ_ONCE(*UNLOCK1);
> > > smp_mb(); // A
> > > lock1 = READ_ONCE(*LOCK1);
> > >
> > > // FLIP
> > > if (unlock1 == lock1) {
> > > smp_mb(); // E
> > > WRITE_ONCE(*IDX, 1);
> > > smp_mb(); // D
> > >
> > > // SCAN2
> > > unlock0 = READ_ONCE(*UNLOCK0);
> > > smp_mb(); // A
> > > lock0 = READ_ONCE(*LOCK0);
> > > }
> > > }
> >
> > That becomes the below (same effect).
> >
> > C D
> >
> > {}
> >
> > // updater
> > P0(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
> > {
> > int lock1;
> > int unlock1;
> > int lock0;
> > int unlock0;
> >
> > // SCAN1
> > unlock1 = READ_ONCE(*UNLOCK1);
> > smp_mb(); // A
> > lock1 = READ_ONCE(*LOCK1);
> >
> > if (unlock1 == lock1) {
> > // FLIP
> > smp_mb(); // E
> > WRITE_ONCE(*IDX, 1);
> > smp_mb(); // D
> >
> > // SCAN 2
> > unlock0 = READ_ONCE(*UNLOCK0);
> > smp_mb(); // A
> > lock0 = READ_ONCE(*LOCK0);
> > }
> > }
> >
> > // reader
> > P1(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
> > {
> > int tmp;
> > int idx;
> >
> > // 1st reader
> > idx = READ_ONCE(*IDX);
> > if (idx == 0) {
> > tmp = READ_ONCE(*LOCK0);
> > WRITE_ONCE(*LOCK0, tmp + 1);
> > smp_mb(); /* B and C */
> > tmp = READ_ONCE(*UNLOCK0);
> > WRITE_ONCE(*UNLOCK0, tmp + 1);
> > } else {
> > tmp = READ_ONCE(*LOCK1);
> > WRITE_ONCE(*LOCK1, tmp + 1);
> > smp_mb(); /* B and C */
> > tmp = READ_ONCE(*UNLOCK1);
> > WRITE_ONCE(*UNLOCK1, tmp + 1);
> > }
> >
> > // second reader
> > idx = READ_ONCE(*IDX);
> > if (idx == 0) {
> > tmp = READ_ONCE(*LOCK0);
> > WRITE_ONCE(*LOCK0, tmp + 1);
> > smp_mb(); /* B and C */
> > tmp = READ_ONCE(*UNLOCK0);
> > WRITE_ONCE(*UNLOCK0, tmp + 1);
> > } else {
> > tmp = READ_ONCE(*LOCK1);
> > WRITE_ONCE(*LOCK1, tmp + 1);
> > smp_mb(); /* B and C */
> > tmp = READ_ONCE(*UNLOCK1);
> > WRITE_ONCE(*UNLOCK1, tmp + 1);
> > }
> >
> > // third reader
> > idx = READ_ONCE(*IDX);
> > if (idx == 0) {
> > tmp = READ_ONCE(*LOCK0);
> > WRITE_ONCE(*LOCK0, tmp + 1);
> > smp_mb(); /* B and C */
> > tmp = READ_ONCE(*UNLOCK0);
> > WRITE_ONCE(*UNLOCK0, tmp + 1);
> > } else {
> > tmp = READ_ONCE(*LOCK1);
> > WRITE_ONCE(*LOCK1, tmp + 1);
> > smp_mb(); /* B and C */
> > tmp = READ_ONCE(*UNLOCK1);
> > WRITE_ONCE(*UNLOCK1, tmp + 1);
> > }
> > }
> >
> > exists (0:unlock0=0 /\ 1:idx=0)
> >