Memory barriers are needed when updating the full length of the
segcblist, however it is not fully clearly why one is needed before and
after. This patch therefore adds additional comments to the function
header to explain it.
Signed-off-by: Joel Fernandes (Google) <[email protected]>
---
kernel/rcu/rcu_segcblist.c | 38 ++++++++++++++++++++++++++++++++++----
1 file changed, 34 insertions(+), 4 deletions(-)
diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
index 271d5d9d7f60..25ffd07f9951 100644
--- a/kernel/rcu/rcu_segcblist.c
+++ b/kernel/rcu/rcu_segcblist.c
@@ -147,17 +147,47 @@ static void rcu_segcblist_inc_seglen(struct rcu_segcblist *rsclp, int seg)
* field to disagree with the actual number of callbacks on the structure.
* This increase is fully ordered with respect to the callers accesses
* both before and after.
+ *
+ * About memory barriers:
+ * There is a situation where rcu_barrier() locklessly samples the full
+ * length of the segmented cblist before deciding what to do. That can
+ * race with another path that calls this function. rcu_barrier() should
+ * not wrongly assume there are no callbacks, so any transitions from 1->0
+ * and 0->1 have to be carefully ordered with respect to list modifications.
+ *
+ * Memory barrier is needed before adding to length, for the case where
+ * v is negative which does not happen in current code, but used
+ * to happen. Keep the memory barrier for robustness reasons. When/If the
+ * length transitions from 1 -> 0, the write to 0 has to be ordered *after*
+ * the memory accesses of the CBs that were dequeued and the segcblist
+ * modifications:
+ * P0 (what P1 sees) P1
+ * set len = 0
+ * rcu_barrier sees len as 0
+ * dequeue from list
+ * rcu_barrier does nothing.
+ *
+ * Memory barrier is needed after adding to length for the case
+ * where length transitions from 0 -> 1. This is because rcu_barrier()
+ * should never miss an update to the length. So the update to length
+ * has to be seen *before* any modifications to the segmented list. Otherwise a
+ * race can happen.
+ * P0 (what P1 sees) P1
+ * queue to list
+ * rcu_barrier sees len as 0
+ * set len = 1.
+ * rcu_barrier does nothing.
*/
void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v)
{
#ifdef CONFIG_RCU_NOCB_CPU
- smp_mb__before_atomic(); /* Up to the caller! */
+ smp_mb__before_atomic(); /* Read function's comments */
atomic_long_add(v, &rsclp->len);
- smp_mb__after_atomic(); /* Up to the caller! */
+ smp_mb__after_atomic(); /* Read function's comments */
#else
- smp_mb(); /* Up to the caller! */
+ smp_mb(); /* Read function's comments */
WRITE_ONCE(rsclp->len, rsclp->len + v);
- smp_mb(); /* Up to the caller! */
+ smp_mb(); /* Read function's comments */
#endif
}
--
2.28.0.1011.ga647a8990f-goog
On Wed, Oct 14, 2020 at 08:23:01PM -0400, Joel Fernandes (Google) wrote:
> Memory barriers are needed when updating the full length of the
> segcblist, however it is not fully clearly why one is needed before and
> after. This patch therefore adds additional comments to the function
> header to explain it.
>
> Signed-off-by: Joel Fernandes (Google) <[email protected]>
> ---
> kernel/rcu/rcu_segcblist.c | 38 ++++++++++++++++++++++++++++++++++----
> 1 file changed, 34 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
> index 271d5d9d7f60..25ffd07f9951 100644
> --- a/kernel/rcu/rcu_segcblist.c
> +++ b/kernel/rcu/rcu_segcblist.c
> @@ -147,17 +147,47 @@ static void rcu_segcblist_inc_seglen(struct rcu_segcblist *rsclp, int seg)
> * field to disagree with the actual number of callbacks on the structure.
> * This increase is fully ordered with respect to the callers accesses
> * both before and after.
> + *
> + * About memory barriers:
> + * There is a situation where rcu_barrier() locklessly samples the full
> + * length of the segmented cblist before deciding what to do. That can
> + * race with another path that calls this function. rcu_barrier() should
> + * not wrongly assume there are no callbacks, so any transitions from 1->0
> + * and 0->1 have to be carefully ordered with respect to list modifications.
> + *
> + * Memory barrier is needed before adding to length, for the case where
> + * v is negative which does not happen in current code, but used
> + * to happen. Keep the memory barrier for robustness reasons.
Heh, I seem to recongnize someone's decision's style ;-)
> When/If the
> + * length transitions from 1 -> 0, the write to 0 has to be ordered *after*
> + * the memory accesses of the CBs that were dequeued and the segcblist
> + * modifications:
> + * P0 (what P1 sees) P1
> + * set len = 0
> + * rcu_barrier sees len as 0
> + * dequeue from list
> + * rcu_barrier does nothing.
It's a bit difficult to read that way. So that would be:
rcu_do_batch() rcu_barrier()
-- --
dequeue l = READ(len)
smp_mb() if (!l)
WRITE(len, 0) check next CPU...
But I'm a bit confused against what it pairs in rcu_barrier().
> + *
> + * Memory barrier is needed after adding to length for the case
> + * where length transitions from 0 -> 1. This is because rcu_barrier()
> + * should never miss an update to the length. So the update to length
> + * has to be seen *before* any modifications to the segmented list. Otherwise a
> + * race can happen.
> + * P0 (what P1 sees) P1
> + * queue to list
> + * rcu_barrier sees len as 0
> + * set len = 1.
> + * rcu_barrier does nothing.
So that would be:
call_rcu() rcu_barrier()
-- --
WRITE(len, len + 1) l = READ(len)
smp_mb() if (!l)
queue check next CPU...
But I still don't see against what it pairs in rcu_barrier.
Thanks.
On Fri, Oct 16, 2020 at 09:27:53PM -0400, [email protected] wrote:
[..]
> > > + *
> > > + * Memory barrier is needed after adding to length for the case
> > > + * where length transitions from 0 -> 1. This is because rcu_barrier()
> > > + * should never miss an update to the length. So the update to length
> > > + * has to be seen *before* any modifications to the segmented list. Otherwise a
> > > + * race can happen.
> > > + * P0 (what P1 sees) P1
> > > + * queue to list
> > > + * rcu_barrier sees len as 0
> > > + * set len = 1.
> > > + * rcu_barrier does nothing.
> >
> > So that would be:
> >
> > call_rcu() rcu_barrier()
> > -- --
> > WRITE(len, len + 1) l = READ(len)
> > smp_mb() if (!l)
> > queue check next CPU...
> >
> >
> > But I still don't see against what it pairs in rcu_barrier.
>
> Actually, for the second case maybe a similar reasoning can be applied
> (control dependency) but I'm unable to come up with a litmus test.
> In fact, now I'm wondering how is it possible that call_rcu() races with
> rcu_barrier(). The module should ensure that no more call_rcu() should happen
> before rcu_barrier() is called.
>
> confused
So I made a litmus test to show that smp_mb() is needed also after the update
to length. Basically, otherwise it is possible the callback will see garbage
that the module cleanup/unload did.
C rcubarrier+ctrldep
(*
* Result: Never
*
* This litmus test shows that rcu_barrier (P1) prematurely
* returning by reading len 0 can cause issues if P0 does
* NOT have a smb_mb() after WRITE_ONCE(len, 1).
* mod_data == 2 means module was unloaded (so data is garbage).
*)
{ int len = 0; int enq = 0; }
P0(int *len, int *mod_data, int *enq)
{
int r0;
WRITE_ONCE(*len, 1);
smp_mb(); /* Needed! */
WRITE_ONCE(*enq, 1);
r0 = READ_ONCE(*mod_data);
}
P1(int *len, int *mod_data, int *enq)
{
int r0;
int r1;
r1 = READ_ONCE(*enq);
// barrier Just for test purpose ("exists" clause) to force the..
// ..rcu_barrier() to see enq before len
smp_mb();
r0 = READ_ONCE(*len);
// implicit memory barrier due to conditional */
if (r0 == 0)
WRITE_ONCE(*mod_data, 2);
}
// Did P0 read garbage?
exists (0:r0=2 /\ 1:r0=0 /\ 1:r1=1)
Adding Alan as well as its memory barrier discussion ;-)
On Thu, Oct 15, 2020 at 03:35:11PM +0200, Frederic Weisbecker wrote:
> On Wed, Oct 14, 2020 at 08:23:01PM -0400, Joel Fernandes (Google) wrote:
> > Memory barriers are needed when updating the full length of the
> > segcblist, however it is not fully clearly why one is needed before and
> > after. This patch therefore adds additional comments to the function
> > header to explain it.
> >
> > Signed-off-by: Joel Fernandes (Google) <[email protected]>
> > ---
> > kernel/rcu/rcu_segcblist.c | 38 ++++++++++++++++++++++++++++++++++----
> > 1 file changed, 34 insertions(+), 4 deletions(-)
> >
> > diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
> > index 271d5d9d7f60..25ffd07f9951 100644
> > --- a/kernel/rcu/rcu_segcblist.c
> > +++ b/kernel/rcu/rcu_segcblist.c
> > @@ -147,17 +147,47 @@ static void rcu_segcblist_inc_seglen(struct rcu_segcblist *rsclp, int seg)
> > * field to disagree with the actual number of callbacks on the structure.
> > * This increase is fully ordered with respect to the callers accesses
> > * both before and after.
> > + *
> > + * About memory barriers:
> > + * There is a situation where rcu_barrier() locklessly samples the full
> > + * length of the segmented cblist before deciding what to do. That can
> > + * race with another path that calls this function. rcu_barrier() should
> > + * not wrongly assume there are no callbacks, so any transitions from 1->0
> > + * and 0->1 have to be carefully ordered with respect to list modifications.
> > + *
> > + * Memory barrier is needed before adding to length, for the case where
> > + * v is negative which does not happen in current code, but used
> > + * to happen. Keep the memory barrier for robustness reasons.
>
> Heh, I seem to recongnize someone's decision's style ;-)
Actually, the last paragraph I added is bogus. Indeed this memory barrier is
not just for robustness reasons. It is needed because rcu_do_batch() adjusts
the length of the list (possibly to 0) _after_ executing the callbacks, so
that's a negative number:
rcu_segcblist_add_len(&rdp->cblist, -count);
> > When/If the
> > + * length transitions from 1 -> 0, the write to 0 has to be ordered *after*
> > + * the memory accesses of the CBs that were dequeued and the segcblist
> > + * modifications:
> > + * P0 (what P1 sees) P1
> > + * set len = 0
> > + * rcu_barrier sees len as 0
> > + * dequeue from list
> > + * rcu_barrier does nothing.
>
> It's a bit difficult to read that way. So that would be:
>
>
> rcu_do_batch() rcu_barrier()
> -- --
> dequeue l = READ(len)
> smp_mb() if (!l)
> WRITE(len, 0) check next CPU...
>
> But I'm a bit confused against what it pairs in rcu_barrier().
I believe it pairs with an implied memory barrier via control dependency.
The following litmus test would confirm it:
C rcubarrier+ctrldep
(*
* Result: Never
*
* This litmus test shows that rcu_barrier (P1) prematurely
* returning by reading len 0 can cause issues if P0 does
* NOT have a smb_mb() before WRITE_ONCE().
*
* mod_data == 2 means garbage which the callback should never see.
*)
{ int len = 1; }
P0(int *len, int *mod_data)
{
int r0;
// accessed by say RCU callback in rcu_do_batch();
r0 = READ_ONCE(*mod_data);
smp_mb(); // Remove this and the "exists" will become true.
WRITE_ONCE(*len, 0);
}
P1(int *len, int *mod_data)
{
int r0;
r0 = READ_ONCE(*len);
// rcu_barrier will return early if len is 0
if (r0 == 0)
WRITE_ONCE(*mod_data, 2);
}
// Is it possible?
exists (0:r0=2 /\ 1:r0=0)
> > + *
> > + * Memory barrier is needed after adding to length for the case
> > + * where length transitions from 0 -> 1. This is because rcu_barrier()
> > + * should never miss an update to the length. So the update to length
> > + * has to be seen *before* any modifications to the segmented list. Otherwise a
> > + * race can happen.
> > + * P0 (what P1 sees) P1
> > + * queue to list
> > + * rcu_barrier sees len as 0
> > + * set len = 1.
> > + * rcu_barrier does nothing.
>
> So that would be:
>
> call_rcu() rcu_barrier()
> -- --
> WRITE(len, len + 1) l = READ(len)
> smp_mb() if (!l)
> queue check next CPU...
>
>
> But I still don't see against what it pairs in rcu_barrier.
Actually, for the second case maybe a similar reasoning can be applied
(control dependency) but I'm unable to come up with a litmus test.
In fact, now I'm wondering how is it possible that call_rcu() races with
rcu_barrier(). The module should ensure that no more call_rcu() should happen
before rcu_barrier() is called.
confused,
- Joel
On Fri, Oct 16, 2020 at 11:19:41PM -0400, [email protected] wrote:
> On Fri, Oct 16, 2020 at 09:27:53PM -0400, [email protected] wrote:
> [..]
> > > > + *
> > > > + * Memory barrier is needed after adding to length for the case
> > > > + * where length transitions from 0 -> 1. This is because rcu_barrier()
> > > > + * should never miss an update to the length. So the update to length
> > > > + * has to be seen *before* any modifications to the segmented list. Otherwise a
> > > > + * race can happen.
> > > > + * P0 (what P1 sees) P1
> > > > + * queue to list
> > > > + * rcu_barrier sees len as 0
> > > > + * set len = 1.
> > > > + * rcu_barrier does nothing.
> > >
> > > So that would be:
> > >
> > > call_rcu() rcu_barrier()
> > > -- --
> > > WRITE(len, len + 1) l = READ(len)
> > > smp_mb() if (!l)
> > > queue check next CPU...
> > >
> > >
> > > But I still don't see against what it pairs in rcu_barrier.
> >
> > Actually, for the second case maybe a similar reasoning can be applied
> > (control dependency) but I'm unable to come up with a litmus test.
> > In fact, now I'm wondering how is it possible that call_rcu() races with
> > rcu_barrier(). The module should ensure that no more call_rcu() should happen
> > before rcu_barrier() is called.
> >
> > confused
>
> So I made a litmus test to show that smp_mb() is needed also after the update
> to length. Basically, otherwise it is possible the callback will see garbage
> that the module cleanup/unload did.
>
> C rcubarrier+ctrldep
>
> (*
> * Result: Never
> *
> * This litmus test shows that rcu_barrier (P1) prematurely
> * returning by reading len 0 can cause issues if P0 does
> * NOT have a smb_mb() after WRITE_ONCE(len, 1).
> * mod_data == 2 means module was unloaded (so data is garbage).
> *)
>
> { int len = 0; int enq = 0; }
>
> P0(int *len, int *mod_data, int *enq)
> {
> int r0;
>
> WRITE_ONCE(*len, 1);
> smp_mb(); /* Needed! */
> WRITE_ONCE(*enq, 1);
>
> r0 = READ_ONCE(*mod_data);
> }
>
> P1(int *len, int *mod_data, int *enq)
> {
> int r0;
> int r1;
>
> r1 = READ_ONCE(*enq);
>
> // barrier Just for test purpose ("exists" clause) to force the..
> // ..rcu_barrier() to see enq before len
> smp_mb();
> r0 = READ_ONCE(*len);
>
> // implicit memory barrier due to conditional */
> if (r0 == 0)
> WRITE_ONCE(*mod_data, 2);
> }
I'm not sure what scenario P1 refers to in practice, and to what module?
>
> // Did P0 read garbage?
> exists (0:r0=2 /\ 1:r0=0 /\ 1:r1=1)
>
What also scares me is that in rcu_barrier():
for_each_possible_cpu(cpu) {
rdp = per_cpu_ptr(&rcu_data, cpu);
if (cpu_is_offline(cpu) &&
!rcu_segcblist_is_offloaded(&rdp->cblist))
continue;
if (rcu_segcblist_n_cbs(&rdp->cblist) && cpu_online(cpu)) {
rcu_barrier_trace(TPS("OnlineQ"), cpu,
rcu_state.barrier_sequence);
smp_call_function_single(cpu, rcu_barrier_func, (void *)cpu, 1);
} else if (rcu_segcblist_n_cbs(&rdp->cblist) &&
cpu_is_offline(cpu)) {
rcu_barrier_trace(TPS("OfflineNoCBQ"), cpu,
rcu_state.barrier_sequence);
local_irq_disable();
rcu_barrier_func((void *)cpu);
local_irq_enable();
} else if (cpu_is_offline(cpu)) {
rcu_barrier_trace(TPS("OfflineNoCBNoQ"), cpu,
rcu_state.barrier_sequence);
} else {
rcu_barrier_trace(TPS("OnlineNQ"), cpu,
rcu_state.barrier_sequence);
}
}
I can't find something that makes sure this isn't racy while reading
rcu_segcblist_n_cbs(&rdp->cblist).
I mean what I see sums up to this:
CPU 0 CPU 1
rcu_barrier() call_rcu()/rcu_segcblist_enqueue()
------------ --------
smp_mb();
inc_len();
smp_mb();
queue callback;
for_each_possible_cpu(cpu)
if (!rcu_segcblist_n_cbs(&rdp->cblist))
continue;
It looks possible for rcu_barrier() to believe there is no callback enqueued
and see rcu_segcblist_n_cbs(&rdp->cblist) == 0 here.
I'm very likely missing something obvious somewhere.
On Fri, Oct 16, 2020 at 09:27:53PM -0400, [email protected] wrote:
> Adding Alan as well as its memory barrier discussion ;-)
I don't know the internals of how RCU works, so I'll just speak to the
litmus test itself, ignoring issues of whether the litmus test is
appropriate or expresses what you really want.
> The following litmus test would confirm it:
>
> C rcubarrier+ctrldep
>
> (*
> * Result: Never
> *
> * This litmus test shows that rcu_barrier (P1) prematurely
> * returning by reading len 0 can cause issues if P0 does
> * NOT have a smb_mb() before WRITE_ONCE().
> *
> * mod_data == 2 means garbage which the callback should never see.
> *)
>
> { int len = 1; }
>
> P0(int *len, int *mod_data)
> {
> int r0;
>
> // accessed by say RCU callback in rcu_do_batch();
> r0 = READ_ONCE(*mod_data);
> smp_mb(); // Remove this and the "exists" will become true.
> WRITE_ONCE(*len, 0);
> }
>
> P1(int *len, int *mod_data)
> {
> int r0;
>
> r0 = READ_ONCE(*len);
>
> // rcu_barrier will return early if len is 0
> if (r0 == 0)
> WRITE_ONCE(*mod_data, 2);
> }
>
> // Is it possible?
> exists (0:r0=2 /\ 1:r0=0)
This result is indeed not possible. And yes, some sort of memory
barrier is needed in P0. But it doesn't have to be smp_mb(); you could
use a weaker barrier instead. For example, you could replace the
READ_ONCE in P0 with smp_load_acquire(), or you could replace the
WRITE_ONCE with smp_store_release(). Either of those changes would
suffice to prevent this outcome.
Alan
[I sent this reply earlier, but since it hasn't shown up in the mailing
list archives, I may have forgotten to include the proper CC's. At the
risk of repeating myself, here it is again.]
On Fri, Oct 16, 2020 at 11:19:41PM -0400, [email protected] wrote:
> So I made a litmus test to show that smp_mb() is needed also after the update
> to length. Basically, otherwise it is possible the callback will see garbage
> that the module cleanup/unload did.
>
> C rcubarrier+ctrldep
>
> (*
> * Result: Never
> *
> * This litmus test shows that rcu_barrier (P1) prematurely
> * returning by reading len 0 can cause issues if P0 does
> * NOT have a smb_mb() after WRITE_ONCE(len, 1).
> * mod_data == 2 means module was unloaded (so data is garbage).
> *)
>
> { int len = 0; int enq = 0; }
>
> P0(int *len, int *mod_data, int *enq)
> {
> int r0;
>
> WRITE_ONCE(*len, 1);
> smp_mb(); /* Needed! */
> WRITE_ONCE(*enq, 1);
>
> r0 = READ_ONCE(*mod_data);
> }
>
> P1(int *len, int *mod_data, int *enq)
> {
> int r0;
> int r1;
>
> r1 = READ_ONCE(*enq);
>
> // barrier Just for test purpose ("exists" clause) to force the..
> // ..rcu_barrier() to see enq before len
> smp_mb();
> r0 = READ_ONCE(*len);
>
> // implicit memory barrier due to conditional */
> if (r0 == 0)
> WRITE_ONCE(*mod_data, 2);
> }
>
> // Did P0 read garbage?
> exists (0:r0=2 /\ 1:r0=0 /\ 1:r1=1)
Is this exists clause really what you meant? Not only can it not be
satisfied, it couldn't even be satisfied if you left out the 0:r0=2
part. And smp_mb() is stronger than neessary to enforce this.
However, some memory barrier is needed. If the smp_mb() in P1 were
omitted then P1 would be free to reorder its reads, and the exists
clause could be satisfied as follows:
P0 P1
------------------------------------------
Read len = 0
Write len = 1
smp_mb();
Write enq = 1
Read enq = 1
Write mod_data = 2
Read mod_data = 2
Alan
On Sat, Oct 17, 2020 at 03:29:54PM +0200, Frederic Weisbecker wrote:
> On Fri, Oct 16, 2020 at 11:19:41PM -0400, [email protected] wrote:
> > On Fri, Oct 16, 2020 at 09:27:53PM -0400, [email protected] wrote:
> > [..]
> > > > > + *
> > > > > + * Memory barrier is needed after adding to length for the case
> > > > > + * where length transitions from 0 -> 1. This is because rcu_barrier()
> > > > > + * should never miss an update to the length. So the update to length
> > > > > + * has to be seen *before* any modifications to the segmented list. Otherwise a
> > > > > + * race can happen.
> > > > > + * P0 (what P1 sees) P1
> > > > > + * queue to list
> > > > > + * rcu_barrier sees len as 0
> > > > > + * set len = 1.
> > > > > + * rcu_barrier does nothing.
> > > >
> > > > So that would be:
> > > >
> > > > call_rcu() rcu_barrier()
> > > > -- --
> > > > WRITE(len, len + 1) l = READ(len)
> > > > smp_mb() if (!l)
> > > > queue check next CPU...
> > > >
> > > >
> > > > But I still don't see against what it pairs in rcu_barrier.
> > >
> > > Actually, for the second case maybe a similar reasoning can be applied
> > > (control dependency) but I'm unable to come up with a litmus test.
> > > In fact, now I'm wondering how is it possible that call_rcu() races with
> > > rcu_barrier(). The module should ensure that no more call_rcu() should happen
> > > before rcu_barrier() is called.
> > >
> > > confused
> >
> > So I made a litmus test to show that smp_mb() is needed also after the update
> > to length. Basically, otherwise it is possible the callback will see garbage
> > that the module cleanup/unload did.
> >
> > C rcubarrier+ctrldep
> >
> > (*
> > * Result: Never
> > *
> > * This litmus test shows that rcu_barrier (P1) prematurely
> > * returning by reading len 0 can cause issues if P0 does
> > * NOT have a smb_mb() after WRITE_ONCE(len, 1).
> > * mod_data == 2 means module was unloaded (so data is garbage).
> > *)
> >
> > { int len = 0; int enq = 0; }
> >
> > P0(int *len, int *mod_data, int *enq)
> > {
> > int r0;
> >
> > WRITE_ONCE(*len, 1);
> > smp_mb(); /* Needed! */
> > WRITE_ONCE(*enq, 1);
> >
> > r0 = READ_ONCE(*mod_data);
> > }
> >
> > P1(int *len, int *mod_data, int *enq)
> > {
> > int r0;
> > int r1;
> >
> > r1 = READ_ONCE(*enq);
> >
> > // barrier Just for test purpose ("exists" clause) to force the..
> > // ..rcu_barrier() to see enq before len
> > smp_mb();
> > r0 = READ_ONCE(*len);
> >
> > // implicit memory barrier due to conditional */
> > if (r0 == 0)
> > WRITE_ONCE(*mod_data, 2);
> > }
>
> I'm not sure what scenario P1 refers to in practice, and to what module?
Kernel module usecase for rcu_barrier. See the docs. P1() in the litmus test
is just a thread of execution which I was using to show the memory accesses
of rcu_barrier.
> > // Did P0 read garbage?
> > exists (0:r0=2 /\ 1:r0=0 /\ 1:r1=1)
> >
>
>
> What also scares me is that in rcu_barrier():
>
> for_each_possible_cpu(cpu) {
> rdp = per_cpu_ptr(&rcu_data, cpu);
> if (cpu_is_offline(cpu) &&
> !rcu_segcblist_is_offloaded(&rdp->cblist))
> continue;
> if (rcu_segcblist_n_cbs(&rdp->cblist) && cpu_online(cpu)) {
> rcu_barrier_trace(TPS("OnlineQ"), cpu,
> rcu_state.barrier_sequence);
> smp_call_function_single(cpu, rcu_barrier_func, (void *)cpu, 1);
> } else if (rcu_segcblist_n_cbs(&rdp->cblist) &&
> cpu_is_offline(cpu)) {
> rcu_barrier_trace(TPS("OfflineNoCBQ"), cpu,
> rcu_state.barrier_sequence);
> local_irq_disable();
> rcu_barrier_func((void *)cpu);
> local_irq_enable();
> } else if (cpu_is_offline(cpu)) {
> rcu_barrier_trace(TPS("OfflineNoCBNoQ"), cpu,
> rcu_state.barrier_sequence);
> } else {
> rcu_barrier_trace(TPS("OnlineNQ"), cpu,
> rcu_state.barrier_sequence);
> }
> }
>
> I can't find something that makes sure this isn't racy while reading
> rcu_segcblist_n_cbs(&rdp->cblist).
>
> I mean what I see sums up to this:
>
> CPU 0 CPU 1
> rcu_barrier() call_rcu()/rcu_segcblist_enqueue()
> ------------ --------
>
> smp_mb();
> inc_len();
> smp_mb();
> queue callback;
> for_each_possible_cpu(cpu)
> if (!rcu_segcblist_n_cbs(&rdp->cblist))
> continue;
>
> It looks possible for rcu_barrier() to believe there is no callback enqueued
> and see rcu_segcblist_n_cbs(&rdp->cblist) == 0 here.
>
> I'm very likely missing something obvious somewhere.
>
> CPU 0 CPU 1
> rcu_barrier() call_rcu()/rcu_segcblist_enqueue()
> ------------ --------
>
> smp_mb();
> inc_len();
> smp_mb();
> queue callback;
> for_each_possible_cpu(cpu)
> if (!rcu_segcblist_n_cbs(&rdp->cblist))
> continue;
>
> invoke_callback
If CPU 0 saw the enqueue of the callback (that is the CPU 1's writes to the
segcb_list propagated to CPU 0), then it would have also seen the
effects of the inc_len. I forced this case in my last litmus test by this
code in P1():
r1 = READ_ONCE(*enq);
smp_mb(); /* barrier Just for test purpose to show that the.. */
/* ..rcu_barrier() saw list modification */
On the other hand, if CPU 0 did not see the enqueue, then there is really no
issue. Since that is the same case where call_rcu() happened _after_ the
rcu_barrier() and there's no race. rcu_barrier() does not need to wait if
there was no callback enqueued.
This is not exactly the easiest thing to explain, hence the litmus.
- Joel
On Sat, Oct 17, 2020 at 7:31 AM Alan Stern <[email protected]> wrote:
>
> On Fri, Oct 16, 2020 at 09:27:53PM -0400, [email protected] wrote:
> > Adding Alan as well as its memory barrier discussion ;-)
>
> I don't know the internals of how RCU works, so I'll just speak to the
> litmus test itself, ignoring issues of whether the litmus test is
> appropriate or expresses what you really want.
>
> > The following litmus test would confirm it:
> >
> > C rcubarrier+ctrldep
> >
> > (*
> > * Result: Never
> > *
> > * This litmus test shows that rcu_barrier (P1) prematurely
> > * returning by reading len 0 can cause issues if P0 does
> > * NOT have a smb_mb() before WRITE_ONCE().
> > *
> > * mod_data == 2 means garbage which the callback should never see.
> > *)
> >
> > { int len = 1; }
> >
> > P0(int *len, int *mod_data)
> > {
> > int r0;
> >
> > // accessed by say RCU callback in rcu_do_batch();
> > r0 = READ_ONCE(*mod_data);
> > smp_mb(); // Remove this and the "exists" will become true.
> > WRITE_ONCE(*len, 0);
> > }
> >
> > P1(int *len, int *mod_data)
> > {
> > int r0;
> >
> > r0 = READ_ONCE(*len);
> >
> > // rcu_barrier will return early if len is 0
> > if (r0 == 0)
> > WRITE_ONCE(*mod_data, 2);
> > }
> >
> > // Is it possible?
> > exists (0:r0=2 /\ 1:r0=0)
>
> This result is indeed not possible. And yes, some sort of memory
> barrier is needed in P0. But it doesn't have to be smp_mb(); you could
> use a weaker barrier instead. For example, you could replace the
> READ_ONCE in P0 with smp_load_acquire(), or you could replace the
> WRITE_ONCE with smp_store_release(). Either of those changes would
> suffice to prevent this outcome.
Right, that works as well. The main point I was trying to hit was the
control-dependency hardware ordering in P1 (due to rcu_barrier()
checking for a condition before doing whatever is after the
rcu_barrier()).
thanks,
- Joel
On Sat, Oct 17, 2020 at 08:35:56PM -0400, [email protected] wrote:
> On Sat, Oct 17, 2020 at 03:29:54PM +0200, Frederic Weisbecker wrote:
> > > C rcubarrier+ctrldep
> > >
> > > (*
> > > * Result: Never
> > > *
> > > * This litmus test shows that rcu_barrier (P1) prematurely
> > > * returning by reading len 0 can cause issues if P0 does
> > > * NOT have a smb_mb() after WRITE_ONCE(len, 1).
> > > * mod_data == 2 means module was unloaded (so data is garbage).
> > > *)
> > >
> > > { int len = 0; int enq = 0; }
> > >
> > > P0(int *len, int *mod_data, int *enq)
> > > {
> > > int r0;
> > >
> > > WRITE_ONCE(*len, 1);
> > > smp_mb(); /* Needed! */
> > > WRITE_ONCE(*enq, 1);
> > >
> > > r0 = READ_ONCE(*mod_data);
> > > }
> > >
> > > P1(int *len, int *mod_data, int *enq)
> > > {
> > > int r0;
> > > int r1;
> > >
> > > r1 = READ_ONCE(*enq);
> > >
> > > // barrier Just for test purpose ("exists" clause) to force the..
> > > // ..rcu_barrier() to see enq before len
> > > smp_mb();
> > > r0 = READ_ONCE(*len);
> > >
> > > // implicit memory barrier due to conditional */
> > > if (r0 == 0)
> > > WRITE_ONCE(*mod_data, 2);
> > > }
> >
> > I'm not sure what scenario P1 refers to in practice, and to what module?
>
> Kernel module usecase for rcu_barrier. See the docs.
My bad, I'm just reading that documentation now :-s
> >
> > I'm very likely missing something obvious somewhere.
> >
> > CPU 0 CPU 1
> > rcu_barrier() call_rcu()/rcu_segcblist_enqueue()
> > ------------ --------
> >
> > smp_mb();
> > inc_len();
> > smp_mb();
> > queue callback;
> > for_each_possible_cpu(cpu)
> > if (!rcu_segcblist_n_cbs(&rdp->cblist))
> > continue;
> >
>
> > invoke_callback
>
> If CPU 0 saw the enqueue of the callback (that is the CPU 1's writes to the
> segcb_list propagated to CPU 0), then it would have also seen the
> effects of the inc_len. I forced this case in my last litmus test by this
> code in P1():
But then I can't find to which part of rcu_barrier() this refers to.
I see the len read before anything else.
>
> r1 = READ_ONCE(*enq);
> smp_mb(); /* barrier Just for test purpose to show that the.. */
> /* ..rcu_barrier() saw list modification */
>
> On the other hand, if CPU 0 did not see the enqueue, then there is really no
> issue. Since that is the same case where call_rcu() happened _after_ the
> rcu_barrier() and there's no race. rcu_barrier() does not need to wait if
> there was no callback enqueued.
>
> This is not exactly the easiest thing to explain, hence the litmus.
Now, reading the documentation of rcu_barrier() (thanks to you!):
Pseudo-code using rcu_barrier() is as follows:
1. Prevent any new RCU callbacks from being posted.
2. Execute rcu_barrier().
3. Allow the module to be unloaded.
I think with point 1, it is assumed that the caller of rcu_barrier() must have
not only stopped but also sync'ed with the possible enqueuers. Correct me if I'm wrong
here. So for example if a kthread used to post the module RCU callbacks, calling kthread_stop()
does the job as it prevents from further RCU callbacks from being enqueued and it also syncs
with the kthread thanks to the completion implied by any caller of kthread_stop() which then
sees what the kthread has read and written, including RCU callbacks enqueued. So if the caller
of kthread_stop() calls rcu_barrier() right after, rcu_barrier() should see at least the len
corresponding to the last enqueue.
cancel_work_sync() also seem to really sync as well. I'm less sure about del_timer_sync().
Say we have:
expire_timers (CPU 0) CPU 1
------------- -----------
detach_timer(timer)
raw_spin_unlock(&base->lock);
call_timer_fn(timer, fn, baseclk);
-> enqueue callback
//would need at least smp_wmb() here
base->running_timer = NULL;
del_timer_sync() {
raw_spin_lock(&base->lock);
if (base->running_timer != timer)
ret = detach_if_pending(timer, base, true);
if (!timer_pending())
return 0;
raw_spin_unlock(&base->lock);
}
//would need at least smp_rmb() here
//although rcu_seq_start() implies a full barrier
rcu_barrier() {
// Sees rcu_segcblist_n_cbs(rdp(CPU 0)->cblist) == 0
// So ignore it
But I'm sure I'm missing something obvious. That's my specialism.
Hi,
Thanks Alan for your replies.
On Sat, Oct 17, 2020 at 1:24 PM Alan Stern <[email protected]> wrote:
>
> [I sent this reply earlier, but since it hasn't shown up in the mailing
> list archives, I may have forgotten to include the proper CC's. At the
> risk of repeating myself, here it is again.]
Np, I did get your first reply and wanted to take a deep look before
replying. Also things here have been crazy.
>
> On Fri, Oct 16, 2020 at 11:19:41PM -0400, [email protected] wrote:
> > So I made a litmus test to show that smp_mb() is needed also after the update
> > to length. Basically, otherwise it is possible the callback will see garbage
> > that the module cleanup/unload did.
> >
> > C rcubarrier+ctrldep
> >
> > (*
> > * Result: Never
> > *
> > * This litmus test shows that rcu_barrier (P1) prematurely
> > * returning by reading len 0 can cause issues if P0 does
> > * NOT have a smb_mb() after WRITE_ONCE(len, 1).
> > * mod_data == 2 means module was unloaded (so data is garbage).
> > *)
> >
> > { int len = 0; int enq = 0; }
> >
> > P0(int *len, int *mod_data, int *enq)
> > {
> > int r0;
> >
> > WRITE_ONCE(*len, 1);
> > smp_mb(); /* Needed! */
> > WRITE_ONCE(*enq, 1);
> >
> > r0 = READ_ONCE(*mod_data);
> > }
> >
> > P1(int *len, int *mod_data, int *enq)
> > {
> > int r0;
> > int r1;
> >
> > r1 = READ_ONCE(*enq);
> >
> > // barrier Just for test purpose ("exists" clause) to force the..
> > // ..rcu_barrier() to see enq before len
> > smp_mb();
> > r0 = READ_ONCE(*len);
> >
> > // implicit memory barrier due to conditional */
> > if (r0 == 0)
> > WRITE_ONCE(*mod_data, 2);
> > }
> >
> > // Did P0 read garbage?
> > exists (0:r0=2 /\ 1:r0=0 /\ 1:r1=1)
>
> Is this exists clause really what you meant? Not only can it not be
> satisfied, it couldn't even be satisfied if you left out the 0:r0=2
> part. And smp_mb() is stronger than neessary to enforce this.
This is indeed what I meant.
Maybe the exists clause can be simplified, but I just wanted to
enforce that P1 saw P0's write to enq before seeing anything else.
Per my test, if you remove the smp_mb() in P0, the test will fail.
What I wanted to show was P0() seeing mod_data == 2 is bad and should
never happen (as that implies rcu_barrier() saw len == 0 when it
should not have). Maybe you can point out what is my test missing?
> However, some memory barrier is needed. If the smp_mb() in P1 were
> omitted then P1 would be free to reorder its reads, and the exists
> clause could be satisfied as follows:
>
> P0 P1
> ------------------------------------------
> Read len = 0
> Write len = 1
> smp_mb();
> Write enq = 1
> Read enq = 1
> Write mod_data = 2
> Read mod_data = 2
Right, so I think I got it right then. I want to show that the control
dependency in P1 provides the needed ordering. The extra smp_mb() I
added was just so that I could force P1 to see P0's enqueue.
Thanks!
- Joel
On Sun, Oct 18, 2020 at 01:45:31PM -0700, Joel Fernandes wrote:
> Hi,
> Thanks Alan for your replies.
You're welcome.
> > > C rcubarrier+ctrldep
> > >
> > > (*
> > > * Result: Never
> > > *
> > > * This litmus test shows that rcu_barrier (P1) prematurely
> > > * returning by reading len 0 can cause issues if P0 does
> > > * NOT have a smb_mb() after WRITE_ONCE(len, 1).
> > > * mod_data == 2 means module was unloaded (so data is garbage).
> > > *)
> > >
> > > { int len = 0; int enq = 0; }
> > >
> > > P0(int *len, int *mod_data, int *enq)
> > > {
> > > int r0;
> > >
> > > WRITE_ONCE(*len, 1);
> > > smp_mb(); /* Needed! */
> > > WRITE_ONCE(*enq, 1);
> > >
> > > r0 = READ_ONCE(*mod_data);
> > > }
> > >
> > > P1(int *len, int *mod_data, int *enq)
> > > {
> > > int r0;
> > > int r1;
> > >
> > > r1 = READ_ONCE(*enq);
> > >
> > > // barrier Just for test purpose ("exists" clause) to force the..
> > > // ..rcu_barrier() to see enq before len
> > > smp_mb();
> > > r0 = READ_ONCE(*len);
> > >
> > > // implicit memory barrier due to conditional */
> > > if (r0 == 0)
> > > WRITE_ONCE(*mod_data, 2);
> > > }
> > >
> > > // Did P0 read garbage?
> > > exists (0:r0=2 /\ 1:r0=0 /\ 1:r1=1)
> >
> > Is this exists clause really what you meant? Not only can it not be
> > satisfied, it couldn't even be satisfied if you left out the 0:r0=2
> > part. And smp_mb() is stronger than neessary to enforce this.
>
> This is indeed what I meant.
>
> Maybe the exists clause can be simplified, but I just wanted to
> enforce that P1 saw P0's write to enq before seeing anything else.
>
> Per my test, if you remove the smp_mb() in P0, the test will fail.
>
> What I wanted to show was P0() seeing mod_data == 2 is bad and should
> never happen (as that implies rcu_barrier() saw len == 0 when it
> should not have). Maybe you can point out what is my test missing?
That's a little tricky, since I don't understand what the test is trying
to say.
For example, you could change the exists clause to omit "/\ 1:r1=1".
Maybe that's not a meaningful thing to do... but then it could be
satisfied simply by having P1 run to completion before P0 starts.
Or you could leave the exists clause as it is and remove the smp_mb()
from P0. As you said, that version of the test would also fail since P0
could then reorder its two writes.
> > However, some memory barrier is needed. If the smp_mb() in P1 were
> > omitted then P1 would be free to reorder its reads, and the exists
> > clause could be satisfied as follows:
> >
> > P0 P1
> > ------------------------------------------
> > Read len = 0
> > Write len = 1
> > smp_mb();
> > Write enq = 1
> > Read enq = 1
> > Write mod_data = 2
> > Read mod_data = 2
>
> Right, so I think I got it right then. I want to show that the control
> dependency in P1 provides the needed ordering. The extra smp_mb() I
> added was just so that I could force P1 to see P0's enqueue.
Yes, it's quite correct that because of the control dependency, P1
cannot write mod_data before it reads the value of len.
Alan Stern
On Mon, Oct 19, 2020 at 5:37 AM Frederic Weisbecker <[email protected]> wrote:
>
[..]
> > >
> > > I'm very likely missing something obvious somewhere.
> > >
> > > CPU 0 CPU 1
> > > rcu_barrier() call_rcu()/rcu_segcblist_enqueue()
> > > ------------ --------
> > >
> > > smp_mb();
> > > inc_len();
> > > smp_mb();
> > > queue callback;
> > > for_each_possible_cpu(cpu)
> > > if (!rcu_segcblist_n_cbs(&rdp->cblist))
> > > continue;
> > >
> >
> > > invoke_callback
> >
> > If CPU 0 saw the enqueue of the callback (that is the CPU 1's writes to the
> > segcb_list propagated to CPU 0), then it would have also seen the
> > effects of the inc_len. I forced this case in my last litmus test by this
> > code in P1():
>
> But then I can't find to which part of rcu_barrier() this refers to.
> I see the len read before anything else.
>
> >
> > r1 = READ_ONCE(*enq);
> > smp_mb(); /* barrier Just for test purpose to show that the.. */
> > /* ..rcu_barrier() saw list modification */
> >
> > On the other hand, if CPU 0 did not see the enqueue, then there is really no
> > issue. Since that is the same case where call_rcu() happened _after_ the
> > rcu_barrier() and there's no race. rcu_barrier() does not need to wait if
> > there was no callback enqueued.
> >
> > This is not exactly the easiest thing to explain, hence the litmus.
>
> Now, reading the documentation of rcu_barrier() (thanks to you!):
>
> Pseudo-code using rcu_barrier() is as follows:
>
> 1. Prevent any new RCU callbacks from being posted.
> 2. Execute rcu_barrier().
> 3. Allow the module to be unloaded.
>
Basically, you are saying that if all CPUs agree that len == 0
henceforth (through other memory barriers), then callback enqueuing
does not need a memory barrier before setting length to 0.
I think that makes sense but is it worth removing the memory barrier
before WRITE(len, 1) and hoping after #1, the caller would have
ensured things are fine? Also I am not sure if the above is the only
usecase for rcu_barrier().
> I think with point 1, it is assumed that the caller of rcu_barrier() must have
> not only stopped but also sync'ed with the possible enqueuers. Correct me if I'm wrong
> here. So for example if a kthread used to post the module RCU callbacks, calling kthread_stop()
> does the job as it prevents from further RCU callbacks from being enqueued and it also syncs
> with the kthread thanks to the completion implied by any caller of kthread_stop() which then
> sees what the kthread has read and written, including RCU callbacks enqueued. So if the caller
> of kthread_stop() calls rcu_barrier() right after, rcu_barrier() should see at least the len
> corresponding to the last enqueue.
>
> cancel_work_sync() also seem to really sync as well. I'm less sure about del_timer_sync().
>
> Say we have:
>
> expire_timers (CPU 0) CPU 1
> ------------- -----------
> detach_timer(timer)
> raw_spin_unlock(&base->lock);
> call_timer_fn(timer, fn, baseclk);
> -> enqueue callback
> //would need at least smp_wmb() here
> base->running_timer = NULL;
>
> del_timer_sync() {
> raw_spin_lock(&base->lock);
> if (base->running_timer != timer)
> ret = detach_if_pending(timer, base, true);
> if (!timer_pending())
> return 0;
> raw_spin_unlock(&base->lock);
> }
> //would need at least smp_rmb() here
Regarding "would need at least smp_rmb.." :
But the rcu_barrier() has the control dependency we discussed in last
emails, between READ(len) and whatever follows the rcu_barrier().
That itself will provide the ordering right?
> //although rcu_seq_start() implies a full barrier
> rcu_barrier() {
> // Sees rcu_segcblist_n_cbs(rdp(CPU 0)->cblist) == 0
> // So ignore it
>
>
> But I'm sure I'm missing something obvious. That's my specialism.
I could be missing something too :-/. But I'll include this patch in
my next posting anyway and let us also maybe see if Paul disagrees.
thanks,
- Joel
On Wed, Oct 21, 2020 at 11:57:04AM -0700, Joel Fernandes wrote:
> On Mon, Oct 19, 2020 at 5:37 AM Frederic Weisbecker <[email protected]> wrote:
> > Now, reading the documentation of rcu_barrier() (thanks to you!):
> >
> > Pseudo-code using rcu_barrier() is as follows:
> >
> > 1. Prevent any new RCU callbacks from being posted.
> > 2. Execute rcu_barrier().
> > 3. Allow the module to be unloaded.
> >
>
> Basically, you are saying that if all CPUs agree that len == 0
> henceforth (through other memory barriers), then callback enqueuing
> does not need a memory barrier before setting length to 0.
I think setting length to 0 isn't much an issue. At worst we send a useless
IPI and queue a needless callback. But incrementing from 0 to 1 is precisely
what we don't want to miss.
> I think that makes sense but is it worth removing the memory barrier
> before WRITE(len, 1) and hoping after #1, the caller would have
> ensured things are fine? Also I am not sure if the above is the only
> usecase for rcu_barrier().
I'm not sure either. Also I need to check your scenario again.
> > cancel_work_sync() also seem to really sync as well. I'm less sure about del_timer_sync().
> >
> > Say we have:
> >
> > expire_timers (CPU 0) CPU 1
> > ------------- -----------
> > detach_timer(timer)
> > raw_spin_unlock(&base->lock);
> > call_timer_fn(timer, fn, baseclk);
> > -> enqueue callback
> > //would need at least smp_wmb() here
Aah, my bad, the smp_mb() after inc_len does that.
> > base->running_timer = NULL;
> >
> > del_timer_sync() {
> > raw_spin_lock(&base->lock);
> > if (base->running_timer != timer)
> > ret = detach_if_pending(timer, base, true);
> > if (!timer_pending())
> > return 0;
> > raw_spin_unlock(&base->lock);
> > }
> > //would need at least smp_rmb() here
And rcu_seq_start() implies that, although I'm not sure that's what was intended.
So we are good.
>
> Regarding "would need at least smp_rmb.." :
> But the rcu_barrier() has the control dependency we discussed in last
> emails, between READ(len) and whatever follows the rcu_barrier().
> That itself will provide the ordering right?
I'm not sure that was enough. The len itself has to be synchronized against
whatever callback enqueuer that got stopped.
> I could be missing something too :-/. But I'll include this patch in
> my next posting anyway and let us also maybe see if Paul disagrees.
Ok.
Thanks!