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;
MIME-Version: 1.0
References: <20221218191310.130904-1-joel@joelfernandes.org>
 <20221218191310.130904-2-joel@joelfernandes.org> <db4cccb8-e7fd-3d54-c5c8-3df90c5ddc49@efficios.com>
In-Reply-To: <db4cccb8-e7fd-3d54-c5c8-3df90c5ddc49@efficios.com>
From:   Joel Fernandes <joel@joelfernandes.org>
Date:   Sun, 18 Dec 2022 16:19:07 -0500
Message-ID: <CAEXW_YRSKRkVc=+HiknQYkLrBGwWfUn3cCp3Btj5AAeqY7KKZw@mail.gmail.com>
Subject: Re: [RFC 1/2] srcu: Remove comment about prior read lock counts
To:     Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc:     linux-kernel@vger.kernel.org,
        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>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

Hi Mathieu,
Thanks a lot for sharing details of side-rcu, I will review it over
the holidays! I agree we can/should borrow from that implementation
where possible. I replied to the comments below:

On Sun, Dec 18, 2022 at 4:07 PM Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
>
> On 2022-12-18 14:13, Joel Fernandes (Google) wrote:
> > The comment says that if an updater saw lock count updates, then
> > ensure the reader does not see the new srcu_idx.
> >
> > However, there is no memory barrier between a READER reading srcu_idx
> > with respect to incrementing the lock count for that srcu_idx.
> >
> > So what is really happening is, both "B" and "C" will order the current
> > reader's unlock count update, and the _next_ readers lock count update, with
> > respect to the write to the currently active index.
> >
> > Consider first the case of the unlock count update being seen by the UPDATER:
> >
> > (for brevity, the pseudocode shortens "srcu_idx" to "idx")
> >
> > READER                            UPDATER
> >
> > rcu_read_lock() {
> >      idx = READ(idx);
> >      lock_count[idx]++;
> >
> >      smp_mb();    // B
> > }
> >                                  srcu_flip() {
> >                                      smp_mb(); //E
> >                                      idx++;
> >                                      smp_mb();
> >                                  }
> > rcu_read_unlock() {
> >      smp_mb();    // C
> >      unlock_count[idx]++;
> > }
> >
> > Consider that the updater saw the unlock count update, and due to this, we
> > expect "E" to make sure that the reader only used the old srcu_idx.
> >
> > However, say the reader used the new srcu_idx because we dropped "E".  That is
> > totally OK because both unlock and lock counts of this reader will negate each
> > other during the next scan of the srcu_idx. So we don't have to guarantee at
> > all that the reader used the old srcu_idx, that does not buy us anything
> > because if it used the new one, we would just ignore it during the next scan
> > anyway (the reader is "done").
> >
> > Now lets look at the following case:
> >
> > READER                            UPDATER
> >
> > rcu_read_lock() {
> >      idx = READ(idx);
> >      lock_count[idx]++;
> >
> >      smp_mb();    // B
> > }
> >
> > rcu_read_unlock() {
> >      smp_mb();    // C
> >      unlock_count[idx]++;
> > }
> >                                  srcu_flip() {
> >                                      smp_mb(); //E
> >                                      idx++;
> > rcu_read_lock() {
> >      idx = READ(idx);
> >      lock_count[idx]++;
> >
> >      smp_mb();    // B
> >                                      smp_mb();
> >                                  }
> > }
> >
> > Consider that the updater saw the lock count update of the second
> > rcu_read_lock(). It does not matter that we guarantee that the reader sees only
> > the old srcu_idx. This is because, a reader could totally just sample
> > srcu_idx, and stay preempted for long periods of time. So, during any scan, we
> > already have the issue of a preempted-reader randomly springing up with a copy
> > of the index which we consider the "new index". So guaranteeing that the reader
> > saw the old srcu_idx instead of the new one if we saw its lock count updates,
> > also does not buy us anything.
> >
> > Due to these reasons, drop the argument that the reader has to see a certain
> > srcu_idx since we have no control over that anyway, and guaranteeing that does not
> > buy us anything.
>
> I don't understand why this first patch only removes a comment about the
> need to order things, when in fact it's the entire memory barrier /* E
> */ that is useless.
>
> I suspect we should just remove the comment along with the barrier
> without this added step.

Yes, this is what I do in patch 2/2. I just wanted to break it down
because the change log would be too big otherwise. There were 2
reasons given for the "E" memory barrier, so I split it into 2 patches
for that reason so both patches can be discussed possibly separately.
But no issues with squashing as well and merging change logs.

> What SRCU fundamentally does is detect quiescence of all SRCU readers
> between the beginning of the grace period and its completion. In order
> to ensure forward progress, it does so in a two-phase algorithm. What
> the grace period does to detect quiescence is to observe that each of
> the periods (0/1) have no active reader at a given point in the grace
> period.

Yes agreed! By deactivating an index, it is possible to ensure new
readers don't show up on the deactivated one, and so we are bound in
scan time / forward progress. (Except for the special case where a
reader was preempted after picking up the index, and then suddenly
shows up in the scan).

> Then the fact that the period is flipped to send new-coming
> readers into a different period is just to ensure forward progress, and
> is basically irrelevant (order-wise) with the fact that the grace period
> scans both periods and validates that both periods are observed to have
> no active readers.

Yes.

> I'd favor just clarifying the SRCU model in this way, and then remove
> the useless barrier, and also implement improvements to the SRCU
> algorithm and skip the "flip" entirely when we notice (early) that no
> active readers are present in both periods. This is actually similar to
> what I implemented in side-rcu.
> Thoughts ?

Agreed! Thanks so much for sharing this, and I will take a look on my
side and study it. Interesting on that optimization to skip the flip!

Thanks,

 - Joel


>
> Thanks,
>
> Mathieu
>
> >
> > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > ---
> >   kernel/rcu/srcutree.c | 10 ++++------
> >   1 file changed, 4 insertions(+), 6 deletions(-)
> >
> > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > index 1c304fec89c0..d6a4c2439ca6 100644
> > --- a/kernel/rcu/srcutree.c
> > +++ b/kernel/rcu/srcutree.c
> > @@ -983,12 +983,10 @@ static bool try_check_zero(struct srcu_struct *ssp, int 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).
> > +      * 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. */
> >
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com
>