Message-ID: <CAEXW_YQ4W=upWV_x1woSgq-DJPFXmBjH2pVmUnBVb_n_UKrw7A@mail.gmail.com>
Date: Wed, 29 Jan 2025 18:10:10 -0500
From: Joel Fernandes <joel@...lfernandes.org>
To: paulmck@...nel.org
Cc: linux-kernel@...r.kernel.org, Frederic Weisbecker <frederic@...nel.org>, 
	Neeraj Upadhyay <neeraj.upadhyay@...nel.org>, Josh Triplett <josh@...htriplett.org>, 
	Boqun Feng <boqun.feng@...il.com>, Uladzislau Rezki <urezki@...il.com>, 
	Steven Rostedt <rostedt@...dmis.org>, Mathieu Desnoyers <mathieu.desnoyers@...icios.com>, 
	Lai Jiangshan <jiangshanlai@...il.com>, Zqiang <qiang.zhang1211@...il.com>, rcu@...r.kernel.org
Subject: Re: [PATCH] rcu: Merge rcu_seq_done_exact() logic into rcu_seq_done()

On Wed, Jan 29, 2025 at 12:25 PM Paul E. McKenney <paulmck@...nel.org> wrote:
>
> On Wed, Jan 29, 2025 at 06:34:53AM -0500, Joel Fernandes wrote:
> >
> >
> > > On Jan 28, 2025, at 9:21 PM, Paul E. McKenney <paulmck@...nel.org> wrote:
> > >
> > > On Tue, Jan 28, 2025 at 09:13:45PM -0500, Joel Fernandes wrote:
> > >>> On Tue, Jan 28, 2025 at 8:47 PM Paul E. McKenney <paulmck@...nel.org> wrote:
> > >>>
> > >>> On Tue, Jan 28, 2025 at 08:38:57PM -0500, Joel Fernandes wrote:
> > >>>> On Tue, Jan 28, 2025 at 8:33 PM Paul E. McKenney <paulmck@...nel.org> wrote:
> > >>>>>
> > >>>>> On Tue, Jan 28, 2025 at 08:22:48PM -0500, Joel Fernandes wrote:
> > >>>>>> On Mon, Jan 27, 2025 at 07:09:34PM -0500, Joel Fernandes wrote:
> > >>>>>>> On Mon, Jan 27, 2025 at 7:07 PM Joel Fernandes (Google)
> > >>>>>>> <joel@...lfernandes.org> wrote:
> > >>>>>>>>
> > >>>>>>>> The rcu_seq_done() API has a large "false-negative" windows of size
> > >>>>>>>> ULONG_MAX/2, where after wrap around, it is possible that it will think
> > >>>>>>>> that a GP has not completed if a wrap around happens and the delta is
> > >>>>>>>> large.
> > >>>>>>>>
> > >>>>>>>> rcu_seq_done_exact() is more accurate avoiding this wrap around issue,
> > >>>>>>>> by making the window of false-negativity by only 3 GPs. Use this logic
> > >>>>>>>> for rcu_seq_done() which is a nice negative code delta and could
> > >>>>>>>> potentially avoid issues in the future where rcu_seq_done() was
> > >>>>>>>> reporting false-negatives for too long.
> > >>>>>>>>
> > >>>>>>>> rcutorture runs of all scenarios for 15 minutes passed. Code inspection
> > >>>>>>>> was done of all users to convince the change would work.
> > >>>>>>>>
> > >>>>>>>> Signed-off-by: Joel Fernandes (Google) <joel@...lfernandes.org>
> > >>>>>>>
> > >>>>>>> I am leaving a 60 minute overnight run of all scenarios on my personal
> > >>>>>>> server for further testing.
> > >>>>>>
> > >>>>>> The run passed, details below:
> > >>>>>>
> > >>>>>> --- Mon Jan 27 11:49:49 PM EST 2025 Test summary:
> > >>>>>> Results directory:
> > >>>>>> tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 60
> > >>>>>> RUDE01 ------- 14309 GPs (3.97472/s) [tasks-rude: g57884 f0x0 total-gps=57880] n_max_cbs: 0
> > >>>>>> SRCU-L ------- 34121 GPs (9.47806/s) [srcu: g316564 f0x0 total-gps=79242] n_max_cbs: 150000
> > >>>>>> SRCU-N ------- 151316 GPs (42.0322/s) [srcu: g1840064 f0x0 total-gps=460117] n_max_cbs: 150000
> > >>>>>> SRCU-P ------- 35189 GPs (9.77472/s) [srcud: g320792 f0x0 total-gps=80299] n_max_cbs: 150000
> > >>>>>> SRCU-T ------- 389034 GPs (108.065/s) [srcu: g4142406 f0x0 total-gps=1035602] n_max_cbs: 50000
> > >>>>>> SRCU-U ------- 376267 GPs (104.519/s) [srcud: g3953834 f0x0 total-gps=988459] n_max_cbs: 50000
> > >>>>>> SRCU-V ------- 407633 GPs (113.231/s) [srcud: g4371704 f0x0 total-gps=1092927] n_max_cbs: 1000
> > >>>>>> TASKS01 ------- 11007 GPs (3.0575/s) [tasks: g57816 f0x0 total-gps=57808]
> > >>>>>> TASKS02 ------- 10539 GPs (2.9275/s) [tasks: g57936 f0x0 total-gps=57936]
> > >>>>>> TASKS03 ------- 10453 GPs (2.90361/s) [tasks: g57508 f0x0 total-gps=57508]
> > >>>>>> TINY01 ------- 511634 GPs (142.121/s) [rcu: g0 f0x0 total-gps=0] n_max_cbs: 57078
> > >>>>>> TINY02 ------- 541799 GPs (150.5/s) [rcu: g0 f0x0 total-gps=0] n_max_cbs: 2619
> > >>>>>> TRACE01 ------- 7299 GPs (2.0275/s) [tasks-tracing: g45844 f0x0 total-gps=45844] n_max_cbs: 50000
> > >>>>>> TRACE02 ------- 101265 GPs (28.1292/s) [tasks-tracing: g305464 f0x0 total-gps=305456] n_max_cbs: 100000
> > >>>>>> TREE01 ------- 97989 GPs (27.2192/s) [rcu: g479473 f0x0 total-gps=120151]
> > >>>>>> TREE02 ------- 202908 GPs (56.3633/s) [rcu: g1459509 f0x0 total-gps=365162] n_max_cbs: 1139244
> > >>>>>> TREE03 ------- 168901 GPs (46.9169/s) [rcu: g1764445 f0x0 total-gps=441393] n_max_cbs: 1341765
> > >>>>>> TREE04 ------- 148876 GPs (41.3544/s) [rcu: g951744 f0x0 total-gps=238225] n_max_cbs: 236765
> > >>>>>> TREE05 ------- 220092 GPs (61.1367/s) [rcu: g1234385 f0x0 total-gps=308880] n_max_cbs: 82801
> > >>>>>> TREE07 ------- 34678 GPs (9.63278/s) [rcu: g207257 f0x0 total-gps=52094]
> > >>>>>> TREE09 ------- 341706 GPs (94.9183/s) [rcu: g7693569 f0x0 total-gps=1923688] n_max_cbs: 1845334
> > >>>>>> --- Done at Mon Jan 27 11:49:55 PM EST 2025 (4:41:24) exitcode 0
> > >>>>>
> > >>>>> Very good!
> > >>>>>
> > >>>>> How would you go about analyzing whether this is really safe vs. getting
> > >>>>> just getting lucky and not having provoked an overflow?
> > >>>>
> > >>>> I would probably add a more specific test case stressing the API, or
> > >>>> even a unit test of just the API by passing a range of sequences.. I
> > >>>> should go ahead and do that but it sounds like you feel there is an
> > >>>> issue with the patch? :)
> > >>>
> > >>> 2^31 (let alone 2^63) is a very large number of grace periods, and
> > >>> so it is hard to test grace-period sequence-number wrap.
> > >>>
> > >>> Not impossible, though...
> > >>
> > >> We could test a decent number of candidate sequences to cover
> > >> different cases. Not ideal like bruteforcing, but...   Another idea is
> > >> to hardcode/assume ULONG_MAX as 16-bit in a unit test.
> > >
> > > Or put the various sequence numbers into an unsigned short or even
> > > an unsigned char.
> > >
> > > One set of use cases checks to see if a given CPU's ->gp_seq has fallen
> > > too far behind the current grace period, and sets a flag to alert
> > > that CPU.  Others rely on a false negative being functionally OK.
> > >
> > > Or so I believe.  ;-)
> >
> > Thanks, I am itching to create a visualization of all eight bit combinations and the output of both API, which will be a fun exercise however I’m missing something fundamental because as I mentioned in that 100 and 200 example, the API itself cannot distinguish between a wraparound and a legitimate delay in comparison between start and a delayed end. I need to understand this better and go through the code more. ;-/
>
> The big questions are "under what conditions does it need to distinguish,
> and what are the consequences of failing to get this right?"   Also, "what
> is the purpose of ->gpwrap?".

My understanding is we take a snapshot of a sequence and then check at
later time if it was reached. Ok I shall explore these questions.
Meanwhile I created the following visualization using 5-bit numbers:

https://drive.google.com/file/d/1w2sgJga7B5dye4iH0oPZ79obaKO-e_Jn/view?usp=sharing

I find as we expect, that for rcu_seq_done(), as long as the distance
between the "running sequence" and the "target" is ULONG_MAX/2, it
returns correct results. OTHERWISE, it can return false results. So
for target value of 28 (in 5-bit world), only initial running values
from 12 would return FALSE. Before number 12, everything is TRUE. This
can cause both false-positives and false-negatives depending on the
input, however it is possible that are no users who use it causing
false-positives! So I guess it really depends on user.

False positives:
If the initial value is ULONG_MAX/2 away from the target, then
rcu_seq_done() can return TRUE when *no wraparound* happened.

False negatives:
The initial value of the snapshot was *within* the ULONG_MAX/2
distance from target. A full *wrap around then happened*, and we ended
where we were initially, so rcu_seq_done() should return TRUE but it
returns FALSE because it doesn't know about the wrap.

Now we move rcu_seq_done_exact. It has the exact same behavior except
that instead of ULONG_MAX/2, the above situations are shrunk to about
10 counts from the target. So if target is 28, then the initial
sequence should have been at least 18 to avoid false-positive, but
again it is possible and I certain see in the code that it cannot be
used this way.. (at least so far).. So all we are left with is the
false-negative band of ~2.5 GPs..

About "what are the consequences of failing to get this right".  I
believe false-positive is unacceptable unless it is maybe debug code -
that can break functionality in code, too short GPs and all that.
However false-negative is OK as long as the usecase can retry later
and can afford to wait. Did I get that much correct?

Thanks,

- Joel

Powered by blists - more mailing lists