Re: [PATCH v8 2/6] rcu/segcblist: Add counters to segcblist datastructure

2020-10-27 Thread Joel Fernandes 
On Mon, Oct 26, 2020 at 12:24:45PM +0100, Frederic Weisbecker wrote:
[..] 
> > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > index 0f23d20d485a..79b7081143a7 100644
> > --- a/kernel/rcu/srcutree.c
> > +++ b/kernel/rcu/srcutree.c
> > @@ -1160,6 +1160,7 @@ static void srcu_advance_state(struct srcu_struct 
> > *ssp)
> >   */
> >  static void srcu_invoke_callbacks(struct work_struct *work)
> >  {
> > +   long len;
> > bool more;
> > struct rcu_cblist ready_cbs;
> > struct rcu_head *rhp;
> > @@ -1182,6 +1183,7 @@ static void srcu_invoke_callbacks(struct work_struct 
> > *work)
> > /* We are on the job!  Extract and invoke ready callbacks. */
> > sdp->srcu_cblist_invoking = true;
> > rcu_segcblist_extract_done_cbs(&sdp->srcu_cblist, &ready_cbs);
> > +   len = ready_cbs.len;
> > spin_unlock_irq_rcu_node(sdp);
> > rhp = rcu_cblist_dequeue(&ready_cbs);
> > for (; rhp != NULL; rhp = rcu_cblist_dequeue(&ready_cbs)) {
> > @@ -1190,13 +1192,14 @@ static void srcu_invoke_callbacks(struct 
> > work_struct *work)
> > rhp->func(rhp);
> > local_bh_enable();
> > }
> > +   WARN_ON_ONCE(ready_cbs.len);
> >  
> > /*
> >  * Update counts, accelerate new callbacks, and if needed,
> >  * schedule another round of callback invocation.
> >  */
> > spin_lock_irq_rcu_node(sdp);
> > -   rcu_segcblist_insert_count(&sdp->srcu_cblist, &ready_cbs);
> > +   rcu_segcblist_add_len(&sdp->srcu_cblist, -len);
> > (void)rcu_segcblist_accelerate(&sdp->srcu_cblist,
> >rcu_seq_snap(&ssp->srcu_gp_seq));
> > sdp->srcu_cblist_invoking = false;
> 
> Looks good! Thanks.

Just to report, with this fix the (s)rcutorture tests pass:

SRCU-N --- 259086 GPs (143.937/s) [srcu: g3342384 f0x0 total-gps=3342384]
SRCU-P --- 69443 GPs (38.5794/s) [srcud: g637552 f0x0 total-gps=637552]

thanks,

 - Joel

Re: [PATCH v8 2/6] rcu/segcblist: Add counters to segcblist datastructure

2020-10-26 Thread Frederic Weisbecker 
On Mon, Oct 26, 2020 at 01:45:57AM -0400, Joel Fernandes wrote:
> On Mon, Oct 26, 2020 at 01:50:58AM +0100, Frederic Weisbecker wrote:
> > On Wed, Oct 21, 2020 at 03:08:09PM -0400, Joel Fernandes (Google) wrote:
> > >  bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long 
> > > seq)
> > >  {
> > > - int i;
> > > + int i, j;
> > >  
> > >   WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
> > >   if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
> > > @@ -487,6 +508,10 @@ bool rcu_segcblist_accelerate(struct rcu_segcblist 
> > > *rsclp, unsigned long seq)
> > >   if (rcu_segcblist_restempty(rsclp, i) || ++i >= RCU_NEXT_TAIL)
> > >   return false;
> > >  
> > > + /* Accounting: everything below i is about to get merged into i. */
> > > + for (j = i + 1; j <= RCU_NEXT_TAIL; j++)
> > > + rcu_segcblist_move_seglen(rsclp, j, i);
> > > +
> > 
> > Can you perhaps reuse the below loop to move the seglen?
> 
> Not easily, because we will need to store 'i' into another variable then, 
> which
> does not change.
> 
> Besides IMHO, the code is more readable with the loops separated.

Works for me.

Thanks!

Re: [PATCH v8 2/6] rcu/segcblist: Add counters to segcblist datastructure

2020-10-26 Thread Frederic Weisbecker 
On Mon, Oct 26, 2020 at 01:40:43AM -0400, Joel Fernandes wrote:
> On Mon, Oct 26, 2020 at 01:32:12AM +0100, Frederic Weisbecker wrote:
> > You seem to have forgotten the suggestion?
> > 
> > rclp->len += rcu_segcblist_get_seglen(rsclp, i)
> 
> I decided to keep it this way as I did not see how it could be better.
> You mentioned you are Ok with either option so I left it as is.
> 
> Thanks!

Fair enough!

> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index 0f23d20d485a..79b7081143a7 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -1160,6 +1160,7 @@ static void srcu_advance_state(struct srcu_struct *ssp)
>   */
>  static void srcu_invoke_callbacks(struct work_struct *work)
>  {
> + long len;
>   bool more;
>   struct rcu_cblist ready_cbs;
>   struct rcu_head *rhp;
> @@ -1182,6 +1183,7 @@ static void srcu_invoke_callbacks(struct work_struct 
> *work)
>   /* We are on the job!  Extract and invoke ready callbacks. */
>   sdp->srcu_cblist_invoking = true;
>   rcu_segcblist_extract_done_cbs(&sdp->srcu_cblist, &ready_cbs);
> + len = ready_cbs.len;
>   spin_unlock_irq_rcu_node(sdp);
>   rhp = rcu_cblist_dequeue(&ready_cbs);
>   for (; rhp != NULL; rhp = rcu_cblist_dequeue(&ready_cbs)) {
> @@ -1190,13 +1192,14 @@ static void srcu_invoke_callbacks(struct work_struct 
> *work)
>   rhp->func(rhp);
>   local_bh_enable();
>   }
> + WARN_ON_ONCE(ready_cbs.len);
>  
>   /*
>* Update counts, accelerate new callbacks, and if needed,
>* schedule another round of callback invocation.
>*/
>   spin_lock_irq_rcu_node(sdp);
> - rcu_segcblist_insert_count(&sdp->srcu_cblist, &ready_cbs);
> + rcu_segcblist_add_len(&sdp->srcu_cblist, -len);
>   (void)rcu_segcblist_accelerate(&sdp->srcu_cblist,
>  rcu_seq_snap(&ssp->srcu_gp_seq));
>   sdp->srcu_cblist_invoking = false;

Looks good! Thanks.

Re: [PATCH v8 2/6] rcu/segcblist: Add counters to segcblist datastructure

2020-10-25 Thread Joel Fernandes 
On Mon, Oct 26, 2020 at 01:50:58AM +0100, Frederic Weisbecker wrote:
> On Wed, Oct 21, 2020 at 03:08:09PM -0400, Joel Fernandes (Google) wrote:
> >  bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long 
> > seq)
> >  {
> > -   int i;
> > +   int i, j;
> >  
> > WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
> > if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
> > @@ -487,6 +508,10 @@ bool rcu_segcblist_accelerate(struct rcu_segcblist 
> > *rsclp, unsigned long seq)
> > if (rcu_segcblist_restempty(rsclp, i) || ++i >= RCU_NEXT_TAIL)
> > return false;
> >  
> > +   /* Accounting: everything below i is about to get merged into i. */
> > +   for (j = i + 1; j <= RCU_NEXT_TAIL; j++)
> > +   rcu_segcblist_move_seglen(rsclp, j, i);
> > +
> 
> Can you perhaps reuse the below loop to move the seglen?

Not easily, because we will need to store 'i' into another variable then, which
does not change.

Besides IMHO, the code is more readable with the loops separated.

thanks,

 - Joel
 

> > /*
> >  * Merge all later callbacks, including newly arrived callbacks,
> >  * into the segment located by the for-loop above.  Assign "seq"

Re: [PATCH v8 2/6] rcu/segcblist: Add counters to segcblist datastructure

2020-10-25 Thread Joel Fernandes 
On Mon, Oct 26, 2020 at 01:32:12AM +0100, Frederic Weisbecker wrote:
> On Wed, Oct 21, 2020 at 03:08:09PM -0400, Joel Fernandes (Google) wrote:
> > @@ -307,6 +317,7 @@ void rcu_segcblist_extract_done_cbs(struct 
> > rcu_segcblist *rsclp,
> >  
> > if (!rcu_segcblist_ready_cbs(rsclp))
> > return; /* Nothing to do. */
> > +   rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_DONE_TAIL);
> 
> I realize, doesn't it break the unsegmented count in srcu_invoke_callbacks() ?
> 
> It still does rcu_segcblist_insert_count(), so it adds zero to rsclp->len
> which thus doesn't get cleared and probably keeps growing.

You are right. This needs changing :-( Its my fault, I did not test SRCU
torture tests which are indeed failing.

I fixed it with the diff attached to the end of the email and will test it
more.

> > *rclp->tail = rsclp->head;
> > WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
> > WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
> > @@ -314,6 +325,7 @@ void rcu_segcblist_extract_done_cbs(struct 
> > rcu_segcblist *rsclp,
> > for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)
> > if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])
> > WRITE_ONCE(rsclp->tails[i], &rsclp->head);
> > +   rcu_segcblist_set_seglen(rsclp, RCU_DONE_TAIL, 0);
> >  }
> >  
> >  /*
> > @@ -330,11 +342,16 @@ void rcu_segcblist_extract_pend_cbs(struct 
> > rcu_segcblist *rsclp,
> >  
> > if (!rcu_segcblist_pend_cbs(rsclp))
> > return; /* Nothing to do. */
> > +   rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_WAIT_TAIL) +
> > +   rcu_segcblist_get_seglen(rsclp, RCU_NEXT_READY_TAIL) +
> > +   rcu_segcblist_get_seglen(rsclp, RCU_NEXT_TAIL);
> > *rclp->tail = *rsclp->tails[RCU_DONE_TAIL];
> > rclp->tail = rsclp->tails[RCU_NEXT_TAIL];
> > WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
> > -   for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++)
> > +   for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++) {
> > WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]);
> > +   rcu_segcblist_set_seglen(rsclp, i, 0);
> 
> You seem to have forgotten the suggestion?
> 
> rclp->len += rcu_segcblist_get_seglen(rsclp, i)

I decided to keep it this way as I did not see how it could be better.
You mentioned you are Ok with either option so I left it as is.

Thanks!

 - Joel

---8<---

diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index 0f23d20d485a..79b7081143a7 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -1160,6 +1160,7 @@ static void srcu_advance_state(struct srcu_struct *ssp)
  */
 static void srcu_invoke_callbacks(struct work_struct *work)
 {
+   long len;
bool more;
struct rcu_cblist ready_cbs;
struct rcu_head *rhp;
@@ -1182,6 +1183,7 @@ static void srcu_invoke_callbacks(struct work_struct 
*work)
/* We are on the job!  Extract and invoke ready callbacks. */
sdp->srcu_cblist_invoking = true;
rcu_segcblist_extract_done_cbs(&sdp->srcu_cblist, &ready_cbs);
+   len = ready_cbs.len;
spin_unlock_irq_rcu_node(sdp);
rhp = rcu_cblist_dequeue(&ready_cbs);
for (; rhp != NULL; rhp = rcu_cblist_dequeue(&ready_cbs)) {
@@ -1190,13 +1192,14 @@ static void srcu_invoke_callbacks(struct work_struct 
*work)
rhp->func(rhp);
local_bh_enable();
}
+   WARN_ON_ONCE(ready_cbs.len);
 
/*
 * Update counts, accelerate new callbacks, and if needed,
 * schedule another round of callback invocation.
 */
spin_lock_irq_rcu_node(sdp);
-   rcu_segcblist_insert_count(&sdp->srcu_cblist, &ready_cbs);
+   rcu_segcblist_add_len(&sdp->srcu_cblist, -len);
(void)rcu_segcblist_accelerate(&sdp->srcu_cblist,
   rcu_seq_snap(&ssp->srcu_gp_seq));
sdp->srcu_cblist_invoking = false;

Re: [PATCH v8 2/6] rcu/segcblist: Add counters to segcblist datastructure

2020-10-25 Thread Frederic Weisbecker 
On Wed, Oct 21, 2020 at 03:08:09PM -0400, Joel Fernandes (Google) wrote:
>  bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
>  {
> - int i;
> + int i, j;
>  
>   WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
>   if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
> @@ -487,6 +508,10 @@ bool rcu_segcblist_accelerate(struct rcu_segcblist 
> *rsclp, unsigned long seq)
>   if (rcu_segcblist_restempty(rsclp, i) || ++i >= RCU_NEXT_TAIL)
>   return false;
>  
> + /* Accounting: everything below i is about to get merged into i. */
> + for (j = i + 1; j <= RCU_NEXT_TAIL; j++)
> + rcu_segcblist_move_seglen(rsclp, j, i);
> +

Can you perhaps reuse the below loop to move the seglen?

Thanks.

>   /*
>* Merge all later callbacks, including newly arrived callbacks,
>* into the segment located by the for-loop above.  Assign "seq"

Re: [PATCH v8 2/6] rcu/segcblist: Add counters to segcblist datastructure

2020-10-25 Thread Frederic Weisbecker 
On Wed, Oct 21, 2020 at 03:08:09PM -0400, Joel Fernandes (Google) wrote:
> @@ -307,6 +317,7 @@ void rcu_segcblist_extract_done_cbs(struct rcu_segcblist 
> *rsclp,
>  
>   if (!rcu_segcblist_ready_cbs(rsclp))
>   return; /* Nothing to do. */
> + rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_DONE_TAIL);

I realize, doesn't it break the unsegmented count in srcu_invoke_callbacks() ?

It still does rcu_segcblist_insert_count(), so it adds zero to rsclp->len
which thus doesn't get cleared and probably keeps growing.

At least srcu_barrier() relies on it. And module exit should warn.

>   *rclp->tail = rsclp->head;
>   WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
>   WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
> @@ -314,6 +325,7 @@ void rcu_segcblist_extract_done_cbs(struct rcu_segcblist 
> *rsclp,
>   for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)
>   if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])
>   WRITE_ONCE(rsclp->tails[i], &rsclp->head);
> + rcu_segcblist_set_seglen(rsclp, RCU_DONE_TAIL, 0);
>  }
>  
>  /*
> @@ -330,11 +342,16 @@ void rcu_segcblist_extract_pend_cbs(struct 
> rcu_segcblist *rsclp,
>  
>   if (!rcu_segcblist_pend_cbs(rsclp))
>   return; /* Nothing to do. */
> + rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_WAIT_TAIL) +
> + rcu_segcblist_get_seglen(rsclp, RCU_NEXT_READY_TAIL) +
> + rcu_segcblist_get_seglen(rsclp, RCU_NEXT_TAIL);
>   *rclp->tail = *rsclp->tails[RCU_DONE_TAIL];
>   rclp->tail = rsclp->tails[RCU_NEXT_TAIL];
>   WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
> - for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++)
> + for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++) {
>   WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]);
> + rcu_segcblist_set_seglen(rsclp, i, 0);

You seem to have forgotten the suggestion?

rclp->len += rcu_segcblist_get_seglen(rsclp, i)


Thanks.

[PATCH v8 2/6] rcu/segcblist: Add counters to segcblist datastructure

2020-10-21 Thread Joel Fernandes (Google) 
Add counting of segment lengths of segmented callback list.

This will be useful for a number of things such as knowing how big the
ready-to-execute segment have gotten. The immediate benefit is ability
to trace how the callbacks in the segmented callback list change.

Also this patch remove hacks related to using donecbs's ->len field as a
temporary variable to save the segmented callback list's length. This cannot be
done anymore and is not needed.

Signed-off-by: Joel Fernandes (Google) 
---
 include/linux/rcu_segcblist.h |   1 +
 kernel/rcu/rcu_segcblist.c| 120 ++
 kernel/rcu/rcu_segcblist.h|   2 -
 3 files changed, 79 insertions(+), 44 deletions(-)

diff --git a/include/linux/rcu_segcblist.h b/include/linux/rcu_segcblist.h
index b36afe7b22c9..6c01f09a6456 100644
--- a/include/linux/rcu_segcblist.h
+++ b/include/linux/rcu_segcblist.h
@@ -72,6 +72,7 @@ struct rcu_segcblist {
 #else
long len;
 #endif
+   long seglen[RCU_CBLIST_NSEGS];
u8 enabled;
u8 offloaded;
 };
diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
index bb246d8c6ef1..357c19bbcb00 100644
--- a/kernel/rcu/rcu_segcblist.c
+++ b/kernel/rcu/rcu_segcblist.c
@@ -7,10 +7,11 @@
  * Authors: Paul E. McKenney 
  */
 
-#include 
-#include 
+#include 
 #include 
+#include 
 #include 
+#include 
 
 #include "rcu_segcblist.h"
 
@@ -88,6 +89,46 @@ static void rcu_segcblist_set_len(struct rcu_segcblist 
*rsclp, long v)
 #endif
 }
 
+/* Get the length of a segment of the rcu_segcblist structure. */
+static long rcu_segcblist_get_seglen(struct rcu_segcblist *rsclp, int seg)
+{
+   return READ_ONCE(rsclp->seglen[seg]);
+}
+
+/* Set the length of a segment of the rcu_segcblist structure. */
+static void rcu_segcblist_set_seglen(struct rcu_segcblist *rsclp, int seg, 
long v)
+{
+   WRITE_ONCE(rsclp->seglen[seg], v);
+}
+
+/* Return number of callbacks in a segment of the segmented callback list. */
+static void rcu_segcblist_add_seglen(struct rcu_segcblist *rsclp, int seg, 
long v)
+{
+   WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
+}
+
+/* Move from's segment length to to's segment. */
+static void rcu_segcblist_move_seglen(struct rcu_segcblist *rsclp, int from, 
int to)
+{
+   long len;
+
+   if (from == to)
+   return;
+
+   len = rcu_segcblist_get_seglen(rsclp, from);
+   if (!len)
+   return;
+
+   rcu_segcblist_add_seglen(rsclp, to, len);
+   rcu_segcblist_set_seglen(rsclp, from, 0);
+}
+
+/* Increment segment's length. */
+static void rcu_segcblist_inc_seglen(struct rcu_segcblist *rsclp, int seg)
+{
+   rcu_segcblist_add_seglen(rsclp, seg, 1);
+}
+
 /*
  * Increase the numeric length of an rcu_segcblist structure by the
  * specified amount, which can be negative.  This can cause the ->len
@@ -119,26 +160,6 @@ void rcu_segcblist_inc_len(struct rcu_segcblist *rsclp)
rcu_segcblist_add_len(rsclp, 1);
 }
 
-/*
- * Exchange the numeric length of the specified rcu_segcblist structure
- * with the specified value.  This can cause the ->len field to disagree
- * with the actual number of callbacks on the structure.  This exchange is
- * fully ordered with respect to the callers accesses both before and after.
- */
-static long rcu_segcblist_xchg_len(struct rcu_segcblist *rsclp, long v)
-{
-#ifdef CONFIG_RCU_NOCB_CPU
-   return atomic_long_xchg(&rsclp->len, v);
-#else
-   long ret = rsclp->len;
-
-   smp_mb(); /* Up to the caller! */
-   WRITE_ONCE(rsclp->len, v);
-   smp_mb(); /* Up to the caller! */
-   return ret;
-#endif
-}
-
 /*
  * Initialize an rcu_segcblist structure.
  */
@@ -149,8 +170,10 @@ void rcu_segcblist_init(struct rcu_segcblist *rsclp)
BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq));
BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq));
rsclp->head = NULL;
-   for (i = 0; i < RCU_CBLIST_NSEGS; i++)
+   for (i = 0; i < RCU_CBLIST_NSEGS; i++) {
rsclp->tails[i] = &rsclp->head;
+   rcu_segcblist_set_seglen(rsclp, i, 0);
+   }
rcu_segcblist_set_len(rsclp, 0);
rsclp->enabled = 1;
 }
@@ -246,6 +269,7 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
 {
rcu_segcblist_inc_len(rsclp);
smp_mb(); /* Ensure counts are updated before callback is enqueued. */
+   rcu_segcblist_inc_seglen(rsclp, RCU_NEXT_TAIL);
rhp->next = NULL;
WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);
WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], &rhp->next);
@@ -274,27 +298,13 @@ bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)
if (rsclp->tails[i] != rsclp->tails[i - 1])
break;
+   rcu_segcblist_inc_seglen(rsclp, i);
WRITE_ONCE(*rsclp->tails[i], rhp);
for (; i <= RCU_NEXT_TAIL; i++)
WRITE_ONCE(rsclp->tails