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;
Date:   Fri, 16 Dec 2022 16:32:39 +0000
From:   Joel Fernandes <joel@joelfernandes.org>
To:     "Paul E. McKenney" <paulmck@kernel.org>
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
Subject: Re: [PATCH RFC] srcu: Yet more detail for
 srcu_readers_active_idx_check() comments
Message-ID: <Y5ydp2YPRqGHq+eM@google.com>
References: <20221215201356.GM4001@paulmck-ThinkPad-P17-Gen-1>
 <EE4EC3CC-395E-475D-BEBE-545955AB97C8@joelfernandes.org>
 <20221216010914.GX4001@paulmck-ThinkPad-P17-Gen-1>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20221216010914.GX4001@paulmck-ThinkPad-P17-Gen-1>
Precedence: bulk

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 reader
> > >> has no new smp_mb() that happens AFTER the flip happened. So it can
> > >> totally sample the old idx again -- that particular reader will
> > >> increment twice, but the next time, it will see the flipped one.
> > > 
> > > I will let you transliterate both.  ;-)
> > 
> > I think I see what you mean now :)
> > 
> > I believe the access I am referring to is the read of idx on one side and
> > the write to idx on the other. However that is incomplete and I need to
> > pair that with some of other access on both sides.
> > 
> > So perhaps this:
> > 
> > Writer does flip + smp_mb + read unlock counts [1]
> > 
> > Reader does:
> >  read idx + smp_mb() + increment lock counts [2]
> > 
> > And subsequently reader does
> > Smp_mb() + increment unlock count. [3]
> > 
> > So [1] races with either [2] or [2]+[3].
> > 
> > Is that fair?
> 
> That does look much better, thank you!

Perhaps a comment with an ASCII diagram will help?


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 problem. This
let's a single reader contribute a maximum (unlock minus lock) imbalance of 2.

The following diagram shows the subtle worst case followed by a simplified
store-buffer explanation.

READER                  UPDATER
-------------           ----------
                           // idx is initially 0.
read_lock() {
  READ(idx) = 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)=0;                                           |
  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]++; 
}

read_lock() {
  READ(idx) = 1; //Y
  lock[1]++;
  ...
}
                           scan_readers_idx(0) {
                               count all unlock[0]; //Q
                               ...
                          }

This makes it similar to the store buffer pattern. Using X, Y, P and Q
annotated above, we get:

READER                    UPDATER
X (write)                 P (write)

smp_mb();                 smp_mb();

Y (read)                  Q (read)


thanks,

 - Joel