[PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[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.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
v1->v2: minor nits.

 include/linux/rcu_segcblist.h |  2 +
 kernel/rcu/rcu_segcblist.c    | 90 ++++++++++++++++++++++++++++++++---
 2 files changed, 86 insertions(+), 6 deletions(-)

diff --git a/include/linux/rcu_segcblist.h b/include/linux/rcu_segcblist.h
index b36afe7b22c9..d462ae5e340a 100644
--- a/include/linux/rcu_segcblist.h
+++ b/include/linux/rcu_segcblist.h
@@ -69,8 +69,10 @@ struct rcu_segcblist {
 	unsigned long gp_seq[RCU_CBLIST_NSEGS];
 #ifdef CONFIG_RCU_NOCB_CPU
 	atomic_long_t len;
+	atomic_long_t seglen[RCU_CBLIST_NSEGS];
 #else
 	long len;
+	long seglen[RCU_CBLIST_NSEGS];
 #endif
 	u8 enabled;
 	u8 offloaded;
diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
index 9a0f66133b4b..e55135297e52 100644
--- a/kernel/rcu/rcu_segcblist.c
+++ b/kernel/rcu/rcu_segcblist.c
@@ -88,6 +88,57 @@ 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)
+{
+#ifdef CONFIG_RCU_NOCB_CPU
+	return atomic_long_read(&rsclp->seglen[seg]);
+#else
+	return READ_ONCE(rsclp->seglen[seg]);
+#endif
+}
+
+/* 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)
+{
+#ifdef CONFIG_RCU_NOCB_CPU
+	atomic_long_set(&rsclp->seglen[seg], v);
+#else
+	WRITE_ONCE(rsclp->seglen[seg], v);
+#endif
+}
+
+/* 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)
+{
+#ifdef CONFIG_RCU_NOCB_CPU
+	smp_mb__before_atomic(); /* Up to the caller! */
+	atomic_long_add(v, &rsclp->seglen[seg]);
+	smp_mb__after_atomic(); /* Up to the caller! */
+#else
+	smp_mb(); /* Up to the caller! */
+	WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
+	smp_mb(); /* Up to the caller! */
+#endif
+}
+
+/* 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 = rcu_segcblist_get_seglen(rsclp, from);
+
+	if (!len || from == to)
+		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
@@ -149,8 +200,11 @@ 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;
 }
@@ -245,6 +299,7 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
 			   struct rcu_head *rhp)
 {
 	rcu_segcblist_inc_len(rsclp);
+	rcu_segcblist_inc_seglen(rsclp, RCU_NEXT_TAIL);
 	smp_mb(); /* Ensure counts are updated before callback is enqueued. */
 	rhp->next = NULL;
 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);
@@ -274,6 +329,7 @@ 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[i], &rhp->next);
@@ -307,6 +363,9 @@ 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);
+
 	*rclp->tail = rsclp->head;
 	WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
 	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
@@ -314,6 +373,8 @@ 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 +391,19 @@ 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);
+	}
 }
 
 /*
@@ -359,8 +428,11 @@ void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
 
 	if (!rclp->head)
 		return; /* No callbacks to move. */
+
+	rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);
 	*rclp->tail = rsclp->head;
 	WRITE_ONCE(rsclp->head, rclp->head);
+
 	for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
 		if (&rsclp->head == rsclp->tails[i])
 			WRITE_ONCE(rsclp->tails[i], rclp->tail);
@@ -379,6 +451,8 @@ void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
 {
 	if (!rclp->head)
 		return; /* Nothing to do. */
+
+	rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);
 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);
 	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);
 }
@@ -403,6 +477,7 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
 		if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
 			break;
 		WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);
+		rcu_segcblist_move_seglen(rsclp, i, RCU_DONE_TAIL);
 	}
 
 	/* If no callbacks moved, nothing more need be done. */
@@ -419,10 +494,9 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
 	 * callbacks.  The overall effect is to copy down the later pointers
 	 * into the gap that was created by the now-ready segments.
 	 */
-	for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
-		if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
-			break;  /* No more callbacks. */
+	for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL && j < RCU_NEXT_TAIL; i++, j++) {
 		WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
+		rcu_segcblist_move_seglen(rsclp, i, j);
 		rsclp->gp_seq[j] = rsclp->gp_seq[i];
 	}
 }
@@ -444,7 +518,7 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
  */
 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))
@@ -479,6 +553,10 @@ bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
 	if (++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);
+
 	/*
 	 * Merge all later callbacks, including newly arrived callbacks,
 	 * into the segment located by the for-loop above.  Assign "seq"
-- 
2.28.0.rc0.105.gf9edc3c819-goog

Re: [PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[Joel Fernandes]

On Sat, Jul 18, 2020 at 11:55 PM Joel Fernandes (Google)
<joel@joelfernandes.org> wrote:
[...]
>         /* If no callbacks moved, nothing more need be done. */
> @@ -419,10 +494,9 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
>          * callbacks.  The overall effect is to copy down the later pointers
>          * into the gap that was created by the now-ready segments.
>          */
> -       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
> -               if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
> -                       break;  /* No more callbacks. */
> +       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL && j < RCU_NEXT_TAIL; i++, j++) {
>                 WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
> +               rcu_segcblist_move_seglen(rsclp, i, j);
>                 rsclp->gp_seq[j] = rsclp->gp_seq[i];
>         }

Unfortunately I broke this code, _sigh_.  I need to reinstate the
if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL]) , I completely
misunderstood that.

Re: [PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[Joel Fernandes]

On Sun, Jul 19, 2020 at 12:06:28AM -0400, Joel Fernandes wrote:
> On Sat, Jul 18, 2020 at 11:55 PM Joel Fernandes (Google)
> <joel@joelfernandes.org> wrote:
> [...]
> >         /* If no callbacks moved, nothing more need be done. */
> > @@ -419,10 +494,9 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
> >          * callbacks.  The overall effect is to copy down the later pointers
> >          * into the gap that was created by the now-ready segments.
> >          */
> > -       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
> > -               if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
> > -                       break;  /* No more callbacks. */
> > +       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL && j < RCU_NEXT_TAIL; i++, j++) {
> >                 WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
> > +               rcu_segcblist_move_seglen(rsclp, i, j);
> >                 rsclp->gp_seq[j] = rsclp->gp_seq[i];
> >         }
> 
> Unfortunately I broke this code, _sigh_.  I need to reinstate the
> if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL]) , I completely
> misunderstood that.

And hopefully, third time's a charm with various extra newlines removed:

---8<-----------------------

From: "Joel Fernandes (Google)" <joel@joelfernandes.org>
Subject: [PATCH v3] rcu/segcblist: Add counters to segcblist datastructure

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.

Tested by profusely reading traces when segcblist counts updated.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>

v1->v3: minor nits.
---
 include/linux/rcu_segcblist.h |  2 +
 kernel/rcu/rcu_segcblist.c    | 77 +++++++++++++++++++++++++++++++++--
 2 files changed, 76 insertions(+), 3 deletions(-)

diff --git a/include/linux/rcu_segcblist.h b/include/linux/rcu_segcblist.h
index b36afe7b22c9..d462ae5e340a 100644
--- a/include/linux/rcu_segcblist.h
+++ b/include/linux/rcu_segcblist.h
@@ -69,8 +69,10 @@ struct rcu_segcblist {
 	unsigned long gp_seq[RCU_CBLIST_NSEGS];
 #ifdef CONFIG_RCU_NOCB_CPU
 	atomic_long_t len;
+	atomic_long_t seglen[RCU_CBLIST_NSEGS];
 #else
 	long len;
+	long seglen[RCU_CBLIST_NSEGS];
 #endif
 	u8 enabled;
 	u8 offloaded;
diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
index 9a0f66133b4b..c5841efcd38e 100644
--- a/kernel/rcu/rcu_segcblist.c
+++ b/kernel/rcu/rcu_segcblist.c
@@ -88,6 +88,57 @@ 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)
+{
+#ifdef CONFIG_RCU_NOCB_CPU
+	return atomic_long_read(&rsclp->seglen[seg]);
+#else
+	return READ_ONCE(rsclp->seglen[seg]);
+#endif
+}
+
+/* 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)
+{
+#ifdef CONFIG_RCU_NOCB_CPU
+	atomic_long_set(&rsclp->seglen[seg], v);
+#else
+	WRITE_ONCE(rsclp->seglen[seg], v);
+#endif
+}
+
+/* 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)
+{
+#ifdef CONFIG_RCU_NOCB_CPU
+	smp_mb__before_atomic(); /* Up to the caller! */
+	atomic_long_add(v, &rsclp->seglen[seg]);
+	smp_mb__after_atomic(); /* Up to the caller! */
+#else
+	smp_mb(); /* Up to the caller! */
+	WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
+	smp_mb(); /* Up to the caller! */
+#endif
+}
+
+/* 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 = rcu_segcblist_get_seglen(rsclp, from);
+
+	if (!len || from == to)
+		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
@@ -149,8 +200,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;
 }
@@ -245,6 +298,7 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
 			   struct rcu_head *rhp)
 {
 	rcu_segcblist_inc_len(rsclp);
+	rcu_segcblist_inc_seglen(rsclp, RCU_NEXT_TAIL);
 	smp_mb(); /* Ensure counts are updated before callback is enqueued. */
 	rhp->next = NULL;
 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);
@@ -274,6 +328,7 @@ 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[i], &rhp->next);
@@ -307,6 +362,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);
 	*rclp->tail = rsclp->head;
 	WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
 	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
@@ -314,6 +370,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 +387,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);
+	}
 }
 
 /*
@@ -359,6 +421,7 @@ void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
 
 	if (!rclp->head)
 		return; /* No callbacks to move. */
+	rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);
 	*rclp->tail = rsclp->head;
 	WRITE_ONCE(rsclp->head, rclp->head);
 	for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
@@ -379,6 +442,8 @@ void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
 {
 	if (!rclp->head)
 		return; /* Nothing to do. */
+
+	rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);
 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);
 	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);
 }
@@ -403,6 +468,7 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
 		if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
 			break;
 		WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);
+		rcu_segcblist_move_seglen(rsclp, i, RCU_DONE_TAIL);
 	}
 
 	/* If no callbacks moved, nothing more need be done. */
@@ -423,6 +489,7 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
 		if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
 			break;  /* No more callbacks. */
 		WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
+		rcu_segcblist_move_seglen(rsclp, i, j);
 		rsclp->gp_seq[j] = rsclp->gp_seq[i];
 	}
 }
@@ -444,7 +511,7 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
  */
 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))
@@ -479,6 +546,10 @@ bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
 	if (++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);
+
 	/*
 	 * Merge all later callbacks, including newly arrived callbacks,
 	 * into the segment located by the for-loop above.  Assign "seq"
-- 
2.28.0.rc0.105.gf9edc3c819-goog

Re: [PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[boqun.feng]

Hi Joel,

On Sun, Jul 19, 2020 at 12:18:41AM -0400, Joel Fernandes wrote:
> On Sun, Jul 19, 2020 at 12:06:28AM -0400, Joel Fernandes wrote:
> > On Sat, Jul 18, 2020 at 11:55 PM Joel Fernandes (Google)
> > <joel@joelfernandes.org> wrote:
> > [...]
> > >         /* If no callbacks moved, nothing more need be done. */
> > > @@ -419,10 +494,9 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
> > >          * callbacks.  The overall effect is to copy down the later pointers
> > >          * into the gap that was created by the now-ready segments.
> > >          */
> > > -       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
> > > -               if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
> > > -                       break;  /* No more callbacks. */
> > > +       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL && j < RCU_NEXT_TAIL; i++, j++) {
> > >                 WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
> > > +               rcu_segcblist_move_seglen(rsclp, i, j);
> > >                 rsclp->gp_seq[j] = rsclp->gp_seq[i];
> > >         }
> > 
> > Unfortunately I broke this code, _sigh_.  I need to reinstate the
> > if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL]) , I completely
> > misunderstood that.
> 
> And hopefully, third time's a charm with various extra newlines removed:
> 
> ---8<-----------------------
> 
> From: "Joel Fernandes (Google)" <joel@joelfernandes.org>
> Subject: [PATCH v3] rcu/segcblist: Add counters to segcblist datastructure
> 
> 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.
> 
> Tested by profusely reading traces when segcblist counts updated.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> 
> v1->v3: minor nits.
> ---
>  include/linux/rcu_segcblist.h |  2 +
>  kernel/rcu/rcu_segcblist.c    | 77 +++++++++++++++++++++++++++++++++--
>  2 files changed, 76 insertions(+), 3 deletions(-)
> 
> diff --git a/include/linux/rcu_segcblist.h b/include/linux/rcu_segcblist.h
> index b36afe7b22c9..d462ae5e340a 100644
> --- a/include/linux/rcu_segcblist.h
> +++ b/include/linux/rcu_segcblist.h
> @@ -69,8 +69,10 @@ struct rcu_segcblist {
>  	unsigned long gp_seq[RCU_CBLIST_NSEGS];
>  #ifdef CONFIG_RCU_NOCB_CPU
>  	atomic_long_t len;
> +	atomic_long_t seglen[RCU_CBLIST_NSEGS];
>  #else
>  	long len;
> +	long seglen[RCU_CBLIST_NSEGS];
>  #endif
>  	u8 enabled;
>  	u8 offloaded;
> diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
> index 9a0f66133b4b..c5841efcd38e 100644
> --- a/kernel/rcu/rcu_segcblist.c
> +++ b/kernel/rcu/rcu_segcblist.c
> @@ -88,6 +88,57 @@ 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)
> +{
> +#ifdef CONFIG_RCU_NOCB_CPU
> +	return atomic_long_read(&rsclp->seglen[seg]);
> +#else
> +	return READ_ONCE(rsclp->seglen[seg]);
> +#endif
> +}
> +
> +/* 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)
> +{
> +#ifdef CONFIG_RCU_NOCB_CPU
> +	atomic_long_set(&rsclp->seglen[seg], v);
> +#else
> +	WRITE_ONCE(rsclp->seglen[seg], v);
> +#endif

These #ifdef really make me uncomfortable ;-) Since we are allowed to
use the '_Generic' key from C11 (see include/linux/compiler_types.h), I
wonder whether it's better if we have a few "generic" primitives like:

	#define gen_long_read(x) _Generic((x),						\
					  atomic_long_t: atomic_long_read(&x, v),	\
					  long: READ_ONCE(x)),				\
					  ...

	#define gen_long_set(x, v) _Generic((x),					\
					    atomic_long_t: atomic_long_set(&x, v),	\
					    long: WRITE_ONCE(x, v)),			\
					    ...

, and similar for _xchg and _add.

With these primitives introduced, you can avoid to add those
rcu_segcblist_*_seglen() which have #ifdefs in them. Of course, an
alternative would be that we implement rcu_segcblist_*_seglen() using
_Generic, but I think someone else may have the similar problems or
requirement (already or in the future), so it might be worthwhile to
introduce the gen_ primitives for broader usage.

Also add Peter and Will to the Cc list.

To summarize, Joel's patch points out that there are some places where
the developers want to save some cost from atomic APIs in a particular
configuration, and obviously they know what they are doing when they use
{READ,WRITE}_ONCE() to replace atomic APIs: they use different types in
different configurations. With the help of C11's _Generic keyword, we
can provide a set of APIs help developers write less but cleaner code.

Any idea? I admit that "gen_" is not a good prefix, just put it here as
a placeholder ;-)

Regards,
Boqun

> +}
> +
> +/* 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)
> +{
> +#ifdef CONFIG_RCU_NOCB_CPU
> +	smp_mb__before_atomic(); /* Up to the caller! */
> +	atomic_long_add(v, &rsclp->seglen[seg]);
> +	smp_mb__after_atomic(); /* Up to the caller! */
> +#else
> +	smp_mb(); /* Up to the caller! */
> +	WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
> +	smp_mb(); /* Up to the caller! */
> +#endif
> +}
> +
> +/* 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 = rcu_segcblist_get_seglen(rsclp, from);
> +
> +	if (!len || from == to)
> +		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
> @@ -149,8 +200,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;
>  }
> @@ -245,6 +298,7 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
>  			   struct rcu_head *rhp)
>  {
>  	rcu_segcblist_inc_len(rsclp);
> +	rcu_segcblist_inc_seglen(rsclp, RCU_NEXT_TAIL);
>  	smp_mb(); /* Ensure counts are updated before callback is enqueued. */
>  	rhp->next = NULL;
>  	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);
> @@ -274,6 +328,7 @@ 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[i], &rhp->next);
> @@ -307,6 +362,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);
>  	*rclp->tail = rsclp->head;
>  	WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
>  	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
> @@ -314,6 +370,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 +387,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);
> +	}
>  }
>  
>  /*
> @@ -359,6 +421,7 @@ void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
>  
>  	if (!rclp->head)
>  		return; /* No callbacks to move. */
> +	rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);
>  	*rclp->tail = rsclp->head;
>  	WRITE_ONCE(rsclp->head, rclp->head);
>  	for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
> @@ -379,6 +442,8 @@ void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
>  {
>  	if (!rclp->head)
>  		return; /* Nothing to do. */
> +
> +	rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);
>  	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);
>  	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);
>  }
> @@ -403,6 +468,7 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
>  		if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
>  			break;
>  		WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);
> +		rcu_segcblist_move_seglen(rsclp, i, RCU_DONE_TAIL);
>  	}
>  
>  	/* If no callbacks moved, nothing more need be done. */
> @@ -423,6 +489,7 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
>  		if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
>  			break;  /* No more callbacks. */
>  		WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
> +		rcu_segcblist_move_seglen(rsclp, i, j);
>  		rsclp->gp_seq[j] = rsclp->gp_seq[i];
>  	}
>  }
> @@ -444,7 +511,7 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
>   */
>  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))
> @@ -479,6 +546,10 @@ bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
>  	if (++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);
> +
>  	/*
>  	 * Merge all later callbacks, including newly arrived callbacks,
>  	 * into the segment located by the for-loop above.  Assign "seq"
> -- 
> 2.28.0.rc0.105.gf9edc3c819-goog
> 

Re: [PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[Joel Fernandes]

On Mon, Jul 20, 2020 at 4:22 AM <boqun.feng@gmail.com> wrote:
>
> Hi Joel,

Sorry for the late reply as I was on vacation last several days.

>
> On Sun, Jul 19, 2020 at 12:18:41AM -0400, Joel Fernandes wrote:
> > On Sun, Jul 19, 2020 at 12:06:28AM -0400, Joel Fernandes wrote:
> > > On Sat, Jul 18, 2020 at 11:55 PM Joel Fernandes (Google)
> > > <joel@joelfernandes.org> wrote:
> > > [...]
> > > >         /* If no callbacks moved, nothing more need be done. */
> > > > @@ -419,10 +494,9 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
> > > >          * callbacks.  The overall effect is to copy down the later pointers
> > > >          * into the gap that was created by the now-ready segments.
> > > >          */
> > > > -       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
> > > > -               if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
> > > > -                       break;  /* No more callbacks. */
> > > > +       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL && j < RCU_NEXT_TAIL; i++, j++) {
> > > >                 WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
> > > > +               rcu_segcblist_move_seglen(rsclp, i, j);
> > > >                 rsclp->gp_seq[j] = rsclp->gp_seq[i];
> > > >         }
> > >
> > > Unfortunately I broke this code, _sigh_.  I need to reinstate the
> > > if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL]) , I completely
> > > misunderstood that.
> >
> > And hopefully, third time's a charm with various extra newlines removed:
> >
> > ---8<-----------------------
> >
> > From: "Joel Fernandes (Google)" <joel@joelfernandes.org>
> > Subject: [PATCH v3] rcu/segcblist: Add counters to segcblist datastructure
> >
> > 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.
> >
> > Tested by profusely reading traces when segcblist counts updated.
> >
> > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> >
> > v1->v3: minor nits.
> > ---
> >  include/linux/rcu_segcblist.h |  2 +
> >  kernel/rcu/rcu_segcblist.c    | 77 +++++++++++++++++++++++++++++++++--
> >  2 files changed, 76 insertions(+), 3 deletions(-)
> >
> > diff --git a/include/linux/rcu_segcblist.h b/include/linux/rcu_segcblist.h
> > index b36afe7b22c9..d462ae5e340a 100644
> > --- a/include/linux/rcu_segcblist.h
> > +++ b/include/linux/rcu_segcblist.h
> > @@ -69,8 +69,10 @@ struct rcu_segcblist {
> >       unsigned long gp_seq[RCU_CBLIST_NSEGS];
> >  #ifdef CONFIG_RCU_NOCB_CPU
> >       atomic_long_t len;
> > +     atomic_long_t seglen[RCU_CBLIST_NSEGS];
> >  #else
> >       long len;
> > +     long seglen[RCU_CBLIST_NSEGS];
> >  #endif
> >       u8 enabled;
> >       u8 offloaded;
> > diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
> > index 9a0f66133b4b..c5841efcd38e 100644
> > --- a/kernel/rcu/rcu_segcblist.c
> > +++ b/kernel/rcu/rcu_segcblist.c
> > @@ -88,6 +88,57 @@ 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)
> > +{
> > +#ifdef CONFIG_RCU_NOCB_CPU
> > +     return atomic_long_read(&rsclp->seglen[seg]);
> > +#else
> > +     return READ_ONCE(rsclp->seglen[seg]);
> > +#endif
> > +}
> > +
> > +/* 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)
> > +{
> > +#ifdef CONFIG_RCU_NOCB_CPU
> > +     atomic_long_set(&rsclp->seglen[seg], v);
> > +#else
> > +     WRITE_ONCE(rsclp->seglen[seg], v);
> > +#endif
>
> These #ifdef really make me uncomfortable ;-) Since we are allowed to
> use the '_Generic' key from C11 (see include/linux/compiler_types.h), I
> wonder whether it's better if we have a few "generic" primitives like:
>
>         #define gen_long_read(x) _Generic((x),                                          \
>                                           atomic_long_t: atomic_long_read(&x, v),       \
>                                           long: READ_ONCE(x)),                          \
>                                           ...
>
>         #define gen_long_set(x, v) _Generic((x),                                        \
>                                             atomic_long_t: atomic_long_set(&x, v),      \
>                                             long: WRITE_ONCE(x, v)),                    \
>                                             ...
>
> , and similar for _xchg and _add.

This sounds like a good idea. But isn't the kernel compiled with -std=gnu89

Here are the KBUILD_CFLAGS

KBUILD_CFLAGS   := -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs \
                   -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE \
                   -Werror=implicit-function-declaration -Werror=implicit-int \
                   -Wno-format-security \
                   -std=gnu89

With "make kernel/rcu/tree.o V=1" confirming it as well:

  gcc -Wp,-MD,kernel/rcu/.tree.o.d  -nostdinc -isystem
/usr/lib/gcc/x86_64-linux-gnu/9/include -I./arch/x86/include
-I./arch/x86/include/generated  -I./include -I./arch/x86/include/uapi
-I./arch/x86/include/generated/uapi -I./include/uapi
-I./include/generated/uapi -include ./include/linux/kconfig.h -include
./include/linux/compiler_types.h -D__KERNEL__ -Wall -Wundef
-Werror=strict-prototypes -Wno-trigraphs -fno-strict-aliasing
-fno-common -fshort-wchar -fno-PIE
-Werror=implicit-function-declaration -Werror=implicit-int
-Wno-format-security -std=gnu89

>
> With these primitives introduced, you can avoid () to add those
> rcu_segcblist_*_seglen() which have #ifdefs in them. Of course, an
> alternative would be that we implement rcu_segcblist_*_seglen() using
> _Generic, but I think someone else may have the similar problems or
> requirement (already or in the future), so it might be worthwhile to
> introduce the gen_ primitives for broader usage.

One issue is code using memory barriers around the operation, such as
in rcu_segcblist_add_len() where you use smp_mb__before_atomic() for
the atomic version, and regular smp_mb() for the non-atomic version.
So ifdef will still exist to some degree.

thanks,

 - Joel

Re: [PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[Boqun Feng]

On Fri, Jul 24, 2020 at 03:34:46PM -0400, Joel Fernandes wrote:
> On Mon, Jul 20, 2020 at 4:22 AM <boqun.feng@gmail.com> wrote:
> >
> > Hi Joel,
> 
> Sorry for the late reply as I was on vacation last several days.
> 
> >
> > On Sun, Jul 19, 2020 at 12:18:41AM -0400, Joel Fernandes wrote:
> > > On Sun, Jul 19, 2020 at 12:06:28AM -0400, Joel Fernandes wrote:
> > > > On Sat, Jul 18, 2020 at 11:55 PM Joel Fernandes (Google)
> > > > <joel@joelfernandes.org> wrote:
> > > > [...]
> > > > >         /* If no callbacks moved, nothing more need be done. */
> > > > > @@ -419,10 +494,9 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
> > > > >          * callbacks.  The overall effect is to copy down the later pointers
> > > > >          * into the gap that was created by the now-ready segments.
> > > > >          */
> > > > > -       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
> > > > > -               if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
> > > > > -                       break;  /* No more callbacks. */
> > > > > +       for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL && j < RCU_NEXT_TAIL; i++, j++) {
> > > > >                 WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
> > > > > +               rcu_segcblist_move_seglen(rsclp, i, j);
> > > > >                 rsclp->gp_seq[j] = rsclp->gp_seq[i];
> > > > >         }
> > > >
> > > > Unfortunately I broke this code, _sigh_.  I need to reinstate the
> > > > if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL]) , I completely
> > > > misunderstood that.
> > >
> > > And hopefully, third time's a charm with various extra newlines removed:
> > >
> > > ---8<-----------------------
> > >
> > > From: "Joel Fernandes (Google)" <joel@joelfernandes.org>
> > > Subject: [PATCH v3] rcu/segcblist: Add counters to segcblist datastructure
> > >
> > > 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.
> > >
> > > Tested by profusely reading traces when segcblist counts updated.
> > >
> > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > >
> > > v1->v3: minor nits.
> > > ---
> > >  include/linux/rcu_segcblist.h |  2 +
> > >  kernel/rcu/rcu_segcblist.c    | 77 +++++++++++++++++++++++++++++++++--
> > >  2 files changed, 76 insertions(+), 3 deletions(-)
> > >
> > > diff --git a/include/linux/rcu_segcblist.h b/include/linux/rcu_segcblist.h
> > > index b36afe7b22c9..d462ae5e340a 100644
> > > --- a/include/linux/rcu_segcblist.h
> > > +++ b/include/linux/rcu_segcblist.h
> > > @@ -69,8 +69,10 @@ struct rcu_segcblist {
> > >       unsigned long gp_seq[RCU_CBLIST_NSEGS];
> > >  #ifdef CONFIG_RCU_NOCB_CPU
> > >       atomic_long_t len;
> > > +     atomic_long_t seglen[RCU_CBLIST_NSEGS];
> > >  #else
> > >       long len;
> > > +     long seglen[RCU_CBLIST_NSEGS];
> > >  #endif
> > >       u8 enabled;
> > >       u8 offloaded;
> > > diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
> > > index 9a0f66133b4b..c5841efcd38e 100644
> > > --- a/kernel/rcu/rcu_segcblist.c
> > > +++ b/kernel/rcu/rcu_segcblist.c
> > > @@ -88,6 +88,57 @@ 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)
> > > +{
> > > +#ifdef CONFIG_RCU_NOCB_CPU
> > > +     return atomic_long_read(&rsclp->seglen[seg]);
> > > +#else
> > > +     return READ_ONCE(rsclp->seglen[seg]);
> > > +#endif
> > > +}
> > > +
> > > +/* 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)
> > > +{
> > > +#ifdef CONFIG_RCU_NOCB_CPU
> > > +     atomic_long_set(&rsclp->seglen[seg], v);
> > > +#else
> > > +     WRITE_ONCE(rsclp->seglen[seg], v);
> > > +#endif
> >
> > These #ifdef really make me uncomfortable ;-) Since we are allowed to
> > use the '_Generic' key from C11 (see include/linux/compiler_types.h), I
> > wonder whether it's better if we have a few "generic" primitives like:
> >
> >         #define gen_long_read(x) _Generic((x),                                          \
> >                                           atomic_long_t: atomic_long_read(&x, v),       \
> >                                           long: READ_ONCE(x)),                          \
> >                                           ...
> >
> >         #define gen_long_set(x, v) _Generic((x),                                        \
> >                                             atomic_long_t: atomic_long_set(&x, v),      \
> >                                             long: WRITE_ONCE(x, v)),                    \
> >                                             ...
> >
> > , and similar for _xchg and _add.
> 
> This sounds like a good idea. But isn't the kernel compiled with -std=gnu89
> 
> Here are the KBUILD_CFLAGS
> 
> KBUILD_CFLAGS   := -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs \
>                    -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE \
>                    -Werror=implicit-function-declaration -Werror=implicit-int \
>                    -Wno-format-security \
>                    -std=gnu89
> 
> With "make kernel/rcu/tree.o V=1" confirming it as well:
> 
>   gcc -Wp,-MD,kernel/rcu/.tree.o.d  -nostdinc -isystem
> /usr/lib/gcc/x86_64-linux-gnu/9/include -I./arch/x86/include
> -I./arch/x86/include/generated  -I./include -I./arch/x86/include/uapi
> -I./arch/x86/include/generated/uapi -I./include/uapi
> -I./include/generated/uapi -include ./include/linux/kconfig.h -include
> ./include/linux/compiler_types.h -D__KERNEL__ -Wall -Wundef
> -Werror=strict-prototypes -Wno-trigraphs -fno-strict-aliasing
> -fno-common -fshort-wchar -fno-PIE
> -Werror=implicit-function-declaration -Werror=implicit-int
> -Wno-format-security -std=gnu89
> 

Note that gnu89 is not equal to c89, according to gcc manual:

	https://gcc.gnu.org/onlinedocs/gcc/Standards.html#C-Language

"""
By default, GCC provides some extensions to the C language that, on
rare occasions conflict with the C standard. See Extensions to the C
Language Family. Some features that are part of the C99 standard are
accepted as extensions in C90 mode, and some features that are part of
the C11 standard are accepted as extensions in C90 and C99 modes. Use of
the -std options listed above disables these extensions where they
conflict with the C standard version selected. You may also select an
extended version of the C language explicitly with -std=gnu90 (for C90
with GNU extensions), -std=gnu99 (for C99 with GNU extensions) or
-std=gnu11 (for C11 with GNU extensions).
"""

So C11 features are available to gnu89 as extensions, also I tried to
compile the following code with -std=gnu89:

	#include <stdio.h>

	typedef struct {
		int a;
	} atomic_t;

	void g(void) {
		printf("this is g\n");
	}

	void h(void) {
		printf("this is f\n");
	}

	#define gen(x) _Generic((x), atomic_t : h(), int : g())

	int main(void) {
		int a;
		atomic_t b;
		gen(a);
		gen(b);
		gen(b);
	}

, and it worked.

Besides, please note that in include/linux/compiler_types.h, _Generic is
already used.

> >
> > With these primitives introduced, you can avoid () to add those
> > rcu_segcblist_*_seglen() which have #ifdefs in them. Of course, an
> > alternative would be that we implement rcu_segcblist_*_seglen() using
> > _Generic, but I think someone else may have the similar problems or
> > requirement (already or in the future), so it might be worthwhile to
> > introduce the gen_ primitives for broader usage.
> 
> One issue is code using memory barriers around the operation, such as
> in rcu_segcblist_add_len() where you use smp_mb__before_atomic() for
> the atomic version, and regular smp_mb() for the non-atomic version.
> So ifdef will still exist to some degree.
> 

Right, I think we can have two functions: long_add_mb() and
atomic_long_add_mb(), this part is similar to ifdef approach, but we can
make a gen_long_add_mb() based on these two functions, and
gen_long_add_mb() simply switches between those functions according to
the actual type of the field, which I think is better than ifdef
approach at readability and maintenance.

Regards,
Boqun

> thanks,
> 
>  - Joel

Re: [PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[Joel Fernandes]

On Mon, Jul 27, 2020 at 09:49:25PM +0800, Boqun Feng wrote:
[...] 
> So C11 features are available to gnu89 as extensions, also I tried to
> compile the following code with -std=gnu89:
> 
> 	#include <stdio.h>
> 
> 	typedef struct {
> 		int a;
> 	} atomic_t;
> 
> 	void g(void) {
> 		printf("this is g\n");
> 	}
> 
> 	void h(void) {
> 		printf("this is f\n");
> 	}
> 
> 	#define gen(x) _Generic((x), atomic_t : h(), int : g())
> 
> 	int main(void) {
> 		int a;
> 		atomic_t b;
> 		gen(a);
> 		gen(b);
> 		gen(b);
> 	}
> 
> , and it worked.
> 
> Besides, please note that in include/linux/compiler_types.h, _Generic is
> already used.

> > > With these primitives introduced, you can avoid () to add those
> > > rcu_segcblist_*_seglen() which have #ifdefs in them. Of course, an
> > > alternative would be that we implement rcu_segcblist_*_seglen() using
> > > _Generic, but I think someone else may have the similar problems or
> > > requirement (already or in the future), so it might be worthwhile to
> > > introduce the gen_ primitives for broader usage.
> > 
> > One issue is code using memory barriers around the operation, such as
> > in rcu_segcblist_add_len() where you use smp_mb__before_atomic() for
> > the atomic version, and regular smp_mb() for the non-atomic version.
> > So ifdef will still exist to some degree.
> > 
> 
> Right, I think we can have two functions: long_add_mb() and
> atomic_long_add_mb(), this part is similar to ifdef approach, but we can
> make a gen_long_add_mb() based on these two functions, and
> gen_long_add_mb() simply switches between those functions according to
> the actual type of the field, which I think is better than ifdef
> approach at readability and maintenance.

Thanks for clarification. I agree with your idea, would you be able to write
a patch to add the helpers my patch can use?

If others are Ok with your idea, I can go ahead and use your helpers.

(I could write the helpers myself as well, next time I send the patch).

thanks,

 - Joel

Re: [PATCH RFC v2] rcu/segcblist: Add counters to segcblist datastructure

[Boqun Feng]

[-- Attachment #1: Type: text/plain, Size: 2441 bytes --]

On Mon, Jul 27, 2020 at 07:03:23PM -0400, Joel Fernandes wrote:
> On Mon, Jul 27, 2020 at 09:49:25PM +0800, Boqun Feng wrote:
> [...] 
> > So C11 features are available to gnu89 as extensions, also I tried to
> > compile the following code with -std=gnu89:
> > 
> > 	#include <stdio.h>
> > 
> > 	typedef struct {
> > 		int a;
> > 	} atomic_t;
> > 
> > 	void g(void) {
> > 		printf("this is g\n");
> > 	}
> > 
> > 	void h(void) {
> > 		printf("this is f\n");
> > 	}
> > 
> > 	#define gen(x) _Generic((x), atomic_t : h(), int : g())
> > 
> > 	int main(void) {
> > 		int a;
> > 		atomic_t b;
> > 		gen(a);
> > 		gen(b);
> > 		gen(b);
> > 	}
> > 
> > , and it worked.
> > 
> > Besides, please note that in include/linux/compiler_types.h, _Generic is
> > already used.
> 
> > > > With these primitives introduced, you can avoid () to add those
> > > > rcu_segcblist_*_seglen() which have #ifdefs in them. Of course, an
> > > > alternative would be that we implement rcu_segcblist_*_seglen() using
> > > > _Generic, but I think someone else may have the similar problems or
> > > > requirement (already or in the future), so it might be worthwhile to
> > > > introduce the gen_ primitives for broader usage.
> > > 
> > > One issue is code using memory barriers around the operation, such as
> > > in rcu_segcblist_add_len() where you use smp_mb__before_atomic() for
> > > the atomic version, and regular smp_mb() for the non-atomic version.
> > > So ifdef will still exist to some degree.
> > > 
> > 
> > Right, I think we can have two functions: long_add_mb() and
> > atomic_long_add_mb(), this part is similar to ifdef approach, but we can
> > make a gen_long_add_mb() based on these two functions, and
> > gen_long_add_mb() simply switches between those functions according to
> > the actual type of the field, which I think is better than ifdef
> > approach at readability and maintenance.
> 
> Thanks for clarification. I agree with your idea, would you be able to write
> a patch to add the helpers my patch can use?
> 

Sure, I will send a prototype to see others' feelings about this, will
try to get that done by a day or two, so hopefully it won't block your
work ;-)

Regards,
Boqun

> If others are Ok with your idea, I can go ahead and use your helpers.
> 
> (I could write the helpers myself as well, next time I send the patch).
> 
> thanks,
> 
>  - Joel
> 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]