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 RFC] srcu: Yet more detail for srcu_readers_active_idx_check() comments
Date:   Sat, 17 Dec 2022 01:32:25 -0500
Message-Id: <BF7A41E0-883D-45BD-A214-A2444A913B47@joelfernandes.org>
References: <20221217051519.GI4001@paulmck-ThinkPad-P17-Gen-1>
Cc:     Frederic Weisbecker <frederic@kernel.org>, boqun.feng@gmail.com,
        neeraj.iitr10@gmail.com, urezki@gmail.com, rcu@vger.kernel.org,
        linux-kernel@vger.kernel.org
In-Reply-To: <20221217051519.GI4001@paulmck-ThinkPad-P17-Gen-1>
To:     paulmck@kernel.org
Precedence: bulk


> On Dec 17, 2022, at 12:15 AM, Paul E. McKenney <paulmck@kernel.org> wrote:=

>=20
> =EF=BB=BFOn Fri, Dec 16, 2022 at 10:21:25PM -0500, Joel Fernandes wrote:
>>> On Fri, Dec 16, 2022 at 10:19 PM Joel Fernandes <joel@joelfernandes.org>=
 wrote:
>>>=20
>>> Hi,
>>> On the related subject of this function, I drew a diagram for one of
>>> the reasons why per-CPU unlock counts have to be scanned first, for a
>>> particular index, before the per-CPU lock counts, and not the other
>>> way. Otherwise, a reader that got preempted after reading the index,
>>> can suddenly get scheduled during the inactive index's scan, and cause
>>> the total lock and unlock counts to falsely match:
>>> https://i.imgur.com/79fDWdQ.png
>>=20
>> Better diagram: https://i.imgur.com/PXKJnmW.png
>> (Added the preemption reasoning for Reader 0).
>=20
> Nice!!!

Thanks!

> The other way to look at this is using a memory-ordering viewpoint.
> This is a member of the message-passing litmus-test family, and the reader=

> must read the variables in the opposite order that the writer writes them.=


Exactly, thanks. If we read the unlock counts first, which includes the unlo=
ck count of that spurious reader 0 in my figure, then would have already see=
n the reader 0=E2=80=99s lock count when we sum up the lock counts, thanks t=
o MP pattern - so that spurious reader cannot do any damage or imbalance in t=
he delta between the lock and unlock counts.   In MP pattern, if we see the f=
lag, then we would have already seen the data (message). And on the other CP=
U the data is written first followed by the write to the flag. Which is exac=
tly what we do in the SRCU as you mentioned with the reversal of the orderin=
g of the variables we read. I will reason about it this way as well in my no=
tes, thank you!

The other way I reason is, during scanning, if we count unlocks first before=
 locks, it=E2=80=99s OK to miss some unlocks, as that just means we will fal=
sely delay ending of GP. However if we count locks first and then unlocks, w=
e are screwed if we miss counting a lock, because if we count the unlock cou=
nt for that missed lock, then we might end the GP sooner than we should!!!

Thanks,

  - Joel=20


>=20
> (See the infamous test6.pdf file, "MP" pattern.)
>=20
>                            Thanx, Paul
>=20
>> thanks,
>>=20
>> - Joel
>>=20
>>=20
>>> Cheers,
>>>=20
>>> - Joel
>>>=20
>>>=20
>>>=20
>>> On Fri, Dec 16, 2022 at 11:54 AM Joel Fernandes <joel@joelfernandes.org>=
 wrote:
>>>>=20
>>>>=20
>>>>=20
>>>>> On Dec 16, 2022, at 11:51 AM, Paul E. McKenney <paulmck@kernel.org> wr=
ote:
>>>>>=20
>>>>> =EF=BB=BFOn Fri, Dec 16, 2022 at 04:32:39PM +0000, Joel Fernandes wrot=
e:
>>>>>> On Thu, Dec 15, 2022 at 05:09:14PM -0800, Paul E. McKenney wrote:
>>>>>> [...]
>>>>>>>>>> 2. unlock()'s smp_mb() happened before Flip+smp_mb() , now the re=
ader
>>>>>>>>>> has no new smp_mb() that happens AFTER the flip happened. So it c=
an
>>>>>>>>>> totally sample the old idx again -- that particular reader will
>>>>>>>>>> increment twice, but the next time, it will see the flipped one.
>>>>>>>>>=20
>>>>>>>>> I will let you transliterate both.  ;-)
>>>>>>>>=20
>>>>>>>> I think I see what you mean now :)
>>>>>>>>=20
>>>>>>>> I believe the access I am referring to is the read of idx on one si=
de and
>>>>>>>> the write to idx on the other. However that is incomplete and I nee=
d to
>>>>>>>> pair that with some of other access on both sides.
>>>>>>>>=20
>>>>>>>> So perhaps this:
>>>>>>>>=20
>>>>>>>> Writer does flip + smp_mb + read unlock counts [1]
>>>>>>>>=20
>>>>>>>> Reader does:
>>>>>>>> read idx + smp_mb() + increment lock counts [2]
>>>>>>>>=20
>>>>>>>> And subsequently reader does
>>>>>>>> Smp_mb() + increment unlock count. [3]
>>>>>>>>=20
>>>>>>>> So [1] races with either [2] or [2]+[3].
>>>>>>>>=20
>>>>>>>> Is that fair?
>>>>>>>=20
>>>>>>> That does look much better, thank you!
>>>>>>=20
>>>>>> Perhaps a comment with an ASCII diagram will help?
>>>>>>=20
>>>>>>=20
>>>>>> Case 2:
>>>>>> Both the reader and the updater see each other's writes too late, but=
 because
>>>>>> of memory barriers on both sides, they will eventually see each other=
's write
>>>>>> with respect to their own. This is similar to the store-buffer proble=
m. This
>>>>>> let's a single reader contribute a maximum (unlock minus lock) imbala=
nce of 2.
>>>>>>=20
>>>>>> The following diagram shows the subtle worst case followed by a simpl=
ified
>>>>>> store-buffer explanation.
>>>>>>=20
>>>>>> READER                  UPDATER
>>>>>> -------------           ----------
>>>>>>                          // idx is initially 0.
>>>>>> read_lock() {
>>>>>> READ(idx) =3D 0;
>>>>>> lock[0]++; --------------------------------------------,
>>>>>>                          flip() {                      |
>>>>>>                             smp_mb();                  |
>>>>>> smp_mb();                                              |
>>>>>> }                                                        |
>>>>>>                                                        |
>>>>>> // RSCS                                                  |
>>>>>>                                                        |
>>>>>> read_unlock() {                                          |
>>>>>> smp_mb();                                              |
>>>>>>                             idx++;  // P               |
>>>>>>                             smp_mb();                  |
>>>>>>                          }                             |
>>>>>>                                                        |
>>>>>>                          scan_readers_idx(0) {         |
>>>>>>                              count all unlock[0];      |
>>>>>>                                  |                     |
>>>>>>                                  |                     |
>>>>>> unlock[0]++; //X <--not-counted--`-----,               |
>>>>>>                                        |               |
>>>>>> }                                        V               `------,
>>>>>>                              // Will make sure next scan      |
>>>>>>                              // will not miss this unlock (X) |
>>>>>>                              // if other side saw flip (P) ,--`
>>>>>>                              // Call this MB [1]           |
>>>>>>                              // Order write(idx) with      |
>>>>>>                              // next scan's unlock.        |
>>>>>>                              smp_mb();                 ,---`
>>>>>> read_lock() {                                            |
>>>>>> READ(idx)=3D0;                                           |
>>>>>> lock[0]++; ----------------> count all lock[0];        |
>>>>>> smp_mb();         |     }                              |
>>>>>> }     |             |                                    V
>>>>>>     |             `---> // Incorrect contribution to lock counting
>>>>>>     |                   // upto a maximum of 2 times.
>>>>>>     |
>>>>>>      `---> // Pairs with MB [1]. Makes sure that
>>>>>>            // the next read_lock()'s' idx read (Y) is ordered
>>>>>>            // with above write to unlock[0] (X).
>>>>>>                           |
>>>>>> rcu_read_unlock() {         |
>>>>>> smp_mb(); <---------------`
>>>>>> unlock[0]++;
>>>>>> }
>>>>>>=20
>>>>>> read_lock() {
>>>>>> READ(idx) =3D 1; //Y
>>>>>> lock[1]++;
>>>>>> ...
>>>>>> }
>>>>>>                          scan_readers_idx(0) {
>>>>>>                              count all unlock[0]; //Q
>>>>>>                              ...
>>>>>>=20
>>>>>>=20
>>>>>> thanks,
>>>>>>=20
>>>>>> - Joel
>>>>>>=20
>>>>>>                         }
>>>>>>=20
>>>>>> This makes it similar to the store buffer pattern. Using X, Y, P and Q=

>>>>>> annotated above, we get:
>>>>>>=20
>>>>>> READER                    UPDATER
>>>>>> X (write)                 P (write)
>>>>>>=20
>>>>>> smp_mb();                 smp_mb();
>>>>>>=20
>>>>>> Y (read)                  Q (read)
>>>>>=20
>>>>> Given that this diagram is more than 50 lines long, it might go better=
 in
>>>>> a design document describing this part of RCU.  Perhaps less detail or=

>>>>> segmented, but the same general idea as this guy:
>>>>>=20
>>>>> Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.rst
>>>>=20
>>>> Yes, this sounds like a good place to add it and perhaps we refer to it=
 from the C source file? I can take this up to do over the holidays, if you p=
refer.
>>>>=20
>>>> Thanks,
>>>>=20
>>>>  - Joel
>>>>=20
>>>>=20
>>>>>=20
>>>>> Thoughts?
>>>>>=20
>>>>>                       Thanx, Paul