Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
From:   Joel Fernandes <joel@joelfernandes.org>
Mime-Version: 1.0 (1.0)
Subject: Re: [PATCH] srcu: Remove memory barrier "E" as it does not do anything
Date:   Thu, 22 Dec 2022 08:03:39 -0500
Message-Id: <19A03A16-9F38-481F-824D-4C883AB8B105@joelfernandes.org>
References: <20221222120319.GA44533@lothringen>
Cc:     linux-kernel@vger.kernel.org,
        Mathieu Desnoyers <mathieu.desnoyers@efficios.com>,
        Boqun Feng <boqun.feng@gmail.com>,
        Josh Triplett <josh@joshtriplett.org>,
        Lai Jiangshan <jiangshanlai@gmail.com>,
        "Paul E. McKenney" <paulmck@kernel.org>, rcu@vger.kernel.org,
        Steven Rostedt <rostedt@goodmis.org>, neeraj.iitr10@gmail.com
In-Reply-To: <20221222120319.GA44533@lothringen>
To:     Frederic Weisbecker <frederic@kernel.org>
Precedence: bulk


> On Dec 22, 2022, at 7:03 AM, Frederic Weisbecker <frederic@kernel.org> wro=
te:
>=20
> =EF=BB=BFOn Thu, Dec 22, 2022 at 12:20:11AM +0000, Joel Fernandes (Google)=
 wrote:
>> During a flip, we have a full memory barrier before srcu_idx is increment=
ed.
>>=20
>> The idea is we intend to order the first phase scan's read of lock
>> counters with the flipping of the index.
>>=20
>> However, such ordering is already enforced because of the
>> control-dependency between the 2 scans. We would be flipping the index
>> only if lock and unlock counts matched.
>>=20
>> But such match will not happen if there was a pending reader before the f=
lip
>> in the first place (observation courtesy Mathieu Desnoyers).
>>=20
>> The litmus test below shows this:
>> (test courtesy Frederic Weisbecker, Changes for ctrldep by Boqun/me):
>>=20
>> C srcu
>>=20
>> {}
>>=20
>> // updater
>> P0(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
>> {
>>        int lock1;
>>        int unlock1;
>>        int lock0;
>>        int unlock0;
>>=20
>>        // SCAN1
>>        unlock1 =3D READ_ONCE(*UNLOCK1);
>>        smp_mb(); // A
>>        lock1 =3D READ_ONCE(*LOCK1);
>>=20
>>        // FLIP
>>        if (lock1 =3D=3D unlock1) {         // Control dep
>>                smp_mb(); // E
>>                WRITE_ONCE(*IDX, 1);
>>                smp_mb(); // D
>>=20
>>                // SCAN2
>>                unlock0 =3D READ_ONCE(*UNLOCK0);
>>                smp_mb(); // A
>>                lock0 =3D READ_ONCE(*LOCK0);
>>        }
>> }
>>=20
>> // reader
>> P1(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
>> {
>>        int tmp;
>>        int idx1;
>>        int idx2;
>>=20
>>        // 1st reader
>>        idx1 =3D READ_ONCE(*IDX);
>>        if (idx1 =3D=3D 0) {
>>                tmp =3D READ_ONCE(*LOCK0);
>>                WRITE_ONCE(*LOCK0, tmp + 1);
>>                smp_mb(); /* B and C */
>>                tmp =3D READ_ONCE(*UNLOCK0);
>>                WRITE_ONCE(*UNLOCK0, tmp + 1);
>>        } else {
>>                tmp =3D READ_ONCE(*LOCK1);
>>                WRITE_ONCE(*LOCK1, tmp + 1);
>>                smp_mb(); /* B and C */
>>                tmp =3D READ_ONCE(*UNLOCK1);
>>                WRITE_ONCE(*UNLOCK1, tmp + 1);
>>        }
>>=20
>>        // second reader
>>        idx2 =3D READ_ONCE(*IDX);
>>        if (idx2 =3D=3D 0) {
>>                tmp =3D READ_ONCE(*LOCK0);
>>                WRITE_ONCE(*LOCK0, tmp + 1);
>>                smp_mb(); /* B and C */
>>                tmp =3D READ_ONCE(*UNLOCK0);
>>                WRITE_ONCE(*UNLOCK0, tmp + 1);
>>        } else {
>>                tmp =3D READ_ONCE(*LOCK1);
>>                WRITE_ONCE(*LOCK1, tmp + 1);
>>                smp_mb(); /* B and C */
>>                tmp =3D READ_ONCE(*UNLOCK1);
>>                WRITE_ONCE(*UNLOCK1, tmp + 1);
>>        }
>> }
>>=20
>> The following bad condition will not occur even if memory barrier E
>> is dropped:
>>=20
>> (* bad condition: SCAN1 saw lock count changes though 1st reader saw flip=
 *)
>> exists (0:lock1=3D1 /\ 1:idx1=3D1 /\ 1:idx2=3D1)
>=20
> Good catch!
>=20
> The litmus test can be shorten with removing the second reader and limit t=
he
> exists clause to 0:lock1=3D1 :

Yes. Made the change and that works too.

>=20
> ---
> C srcu-E
>=20
> {}
>=20
> // updater
> P0(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
> {
>    int lock1;
>    int unlock1;
>    int lock0;
>    int unlock0;
>=20
>    // SCAN1
>    unlock1 =3D READ_ONCE(*UNLOCK1);
>    smp_mb(); // A
>    lock1 =3D READ_ONCE(*LOCK1);
>=20
>    // FLIP
>    if (lock1 =3D=3D unlock1) {         // Control dep
>        WRITE_ONCE(*IDX, 1);
>        smp_mb(); // D
>=20
>        // SCAN2
>        unlock0 =3D READ_ONCE(*UNLOCK0);
>        smp_mb(); // A
>        lock0 =3D READ_ONCE(*LOCK0);
>    }
> }
>=20
> // reader
> P1(int *IDX, int *LOCK0, int *UNLOCK0, int *LOCK1, int *UNLOCK1)
> {
>    int tmp;
>    int idx1;
>    int idx2;
>=20
>    // 1st reader
>    idx1 =3D READ_ONCE(*IDX);
>    if (idx1 =3D=3D 0) {
>        tmp =3D READ_ONCE(*LOCK0);
>        WRITE_ONCE(*LOCK0, tmp + 1);
>        smp_mb(); /* B and C */
>        tmp =3D READ_ONCE(*UNLOCK0);
>        WRITE_ONCE(*UNLOCK0, tmp + 1);
>    } else {
>        tmp =3D READ_ONCE(*LOCK1);
>        WRITE_ONCE(*LOCK1, tmp + 1);
>        smp_mb(); /* B and C */
>        tmp =3D READ_ONCE(*UNLOCK1);
>        WRITE_ONCE(*UNLOCK1, tmp + 1);
>    }
> }
> exists (0:lock1=3D1) (* only happens if the control dep is removed *)
> --
>=20
>> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
>> index 1c304fec89c0..d1368d64fdba 100644
>> --- a/kernel/rcu/srcutree.c
>> +++ b/kernel/rcu/srcutree.c
>> @@ -983,15 +983,9 @@ static bool try_check_zero(struct srcu_struct *ssp, i=
nt idx, int trycount)
>> static void srcu_flip(struct srcu_struct *ssp)
>> {
>>    /*
>> -     * Ensure that if this updater saw a given reader's increment
>> -     * from __srcu_read_lock(), that reader was using an old value
>> -     * of ->srcu_idx.  Also 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).
>> +     * Control dependency locks=3D=3Dunlocks ensures that if a reader se=
es the
>> +     * flip, previous scan would only see before-flip reader lock counts=
.
>=20
> I would personally prefer that we keep the detailed comment explaining the=

> ordering requirements here, just mentioning it's performed via control
> dependency now. This way we don't need to debate that again in 10 years.

Cool, will update the patch.

Thanks.


>=20
>=20
>>     */
>> -    smp_mb(); /* E */  /* Pairs with B and C. */
>> -
>>    WRITE_ONCE(ssp->srcu_idx, ssp->srcu_idx + 1);
>>=20
>>    /*
>> --=20
>> 2.39.0.314.g84b9a713c41-goog
>>=20