* [PATCH v7 0/6] Add support for length of each segment in the segcblist
@ 2020-10-15 0:22 Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 1/6] rcu/tree: Make rcu_do_batch count how many callbacks were executed Joel Fernandes (Google)
` (5 more replies)
0 siblings, 6 replies; 25+ messages in thread
From: Joel Fernandes (Google) @ 2020-10-15 0:22 UTC (permalink / raw)
To: linux-kernel
Cc: Joel Fernandes (Google), Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), fweisbec,
neeraj.iitr10
This is required for several usecases identified. One of them being tracing how
the segmented callback list changes. Tracing this has identified issues in RCU
code in the past.
>From Paul:
Another use case is of course more accurately determining whether a given CPU's
large pile of callbacks can be best served by making grace periods go faster,
invoking callbacks more vigorously, or both. It should also be possible to
simplify some of the callback handling a bit, given that some of the unnatural
acts are due to there having been no per-batch counts.
Revision history:
v7: Cleaned up memory barriers (thanks fweisbec@ for reviewing), made minor
corrections per Neeraj (thanks).
v6: Fixed TREE04, and restored older logic to ensure rcu_barrier works.
v5: Various changes, bug fixes. Discovery of rcu_barrier issue.
v4: Restructured rcu_do_batch() and segcblist merging to avoid issues.
Fixed minor nit from Davidlohr.
v1->v3: minor nits.
(https://lore.kernel.org/lkml/20200719034210.2382053-1-joel@xxxxxxxxxxxxxxxxx/)
Joel Fernandes (Google) (6):
rcu/tree: Make rcu_do_batch count how many callbacks were executed
rcu/segcblist: Add counters to segcblist datastructure
rcu/trace: Add tracing for how segcb list changes
rcu/segcblist: Remove useless rcupdate.h include
rcu/tree: Remove redundant smp_mb() in rcu_do_batch
rcu/segcblist: Add additional comments to explain smp_mb()
include/linux/rcu_segcblist.h | 2 +
include/trace/events/rcu.h | 25 +++++
kernel/rcu/rcu_segcblist.c | 205 ++++++++++++++++++++++++++--------
kernel/rcu/rcu_segcblist.h | 8 +-
kernel/rcu/tree.c | 21 ++--
5 files changed, 203 insertions(+), 58 deletions(-)
--
2.28.0.1011.ga647a8990f-goog
^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH v7 1/6] rcu/tree: Make rcu_do_batch count how many callbacks were executed
2020-10-15 0:22 [PATCH v7 0/6] Add support for length of each segment in the segcblist Joel Fernandes (Google)
@ 2020-10-15 0:22 ` Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure Joel Fernandes (Google)
` (4 subsequent siblings)
5 siblings, 0 replies; 25+ messages in thread
From: Joel Fernandes (Google) @ 2020-10-15 0:22 UTC (permalink / raw)
To: linux-kernel
Cc: Joel Fernandes (Google), Frederic Weisbecker, Ingo Molnar,
Josh Triplett, Lai Jiangshan, Marco Elver, Mathieu Desnoyers,
Paul E. McKenney, rcu, Steven Rostedt, Uladzislau Rezki (Sony),
fweisbec, neeraj.iitr10
Currently, rcu_do_batch() depends on the unsegmented callback list's len field
to know how many CBs are executed. This fields counts down from 0 as CBs are
dequeued. It is possible that all CBs could not be run because of reaching
limits in which case the remaining unexecuted callbacks are requeued in the
CPU's segcblist.
The number of callbacks that were not requeued are then the negative count (how
many CBs were run) stored in the rcl->len which has been counting down on every
dequeue. This negative count is then added to the per-cpu segmented callback
list's to correct its count.
Such a design works against future efforts to track the length of each segment
of the segmented callback list. The reason is because
rcu_segcblist_extract_done_cbs() will be populating the unsegmented callback
list's length field (rcl->len) during extraction.
Also, the design of counting down from 0 is confusing and error-prone IMHO.
This commit therefore explicitly counts how many callbacks were executed in
rcu_do_batch() itself, and uses that to update the per-CPU segcb list's ->len
field, without relying on the negativity of rcl->len.
Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
Reviewed-by: Frederic Weisbecker <frederic@kernel.org>
---
kernel/rcu/rcu_segcblist.c | 2 +-
kernel/rcu/rcu_segcblist.h | 1 +
kernel/rcu/tree.c | 11 +++++------
3 files changed, 7 insertions(+), 7 deletions(-)
diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
index 2d2a6b6b9dfb..bb246d8c6ef1 100644
--- a/kernel/rcu/rcu_segcblist.c
+++ b/kernel/rcu/rcu_segcblist.c
@@ -95,7 +95,7 @@ static void rcu_segcblist_set_len(struct rcu_segcblist *rsclp, long v)
* This increase is fully ordered with respect to the callers accesses
* both before and after.
*/
-static void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v)
+void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v)
{
#ifdef CONFIG_RCU_NOCB_CPU
smp_mb__before_atomic(); /* Up to the caller! */
diff --git a/kernel/rcu/rcu_segcblist.h b/kernel/rcu/rcu_segcblist.h
index 492262bcb591..1d2d61406463 100644
--- a/kernel/rcu/rcu_segcblist.h
+++ b/kernel/rcu/rcu_segcblist.h
@@ -76,6 +76,7 @@ static inline bool rcu_segcblist_restempty(struct rcu_segcblist *rsclp, int seg)
}
void rcu_segcblist_inc_len(struct rcu_segcblist *rsclp);
+void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v);
void rcu_segcblist_init(struct rcu_segcblist *rsclp);
void rcu_segcblist_disable(struct rcu_segcblist *rsclp);
void rcu_segcblist_offload(struct rcu_segcblist *rsclp);
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 286dc0a1b184..24c00020ab83 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -2429,7 +2429,7 @@ static void rcu_do_batch(struct rcu_data *rdp)
const bool offloaded = rcu_segcblist_is_offloaded(&rdp->cblist);
struct rcu_head *rhp;
struct rcu_cblist rcl = RCU_CBLIST_INITIALIZER(rcl);
- long bl, count;
+ long bl, count = 0;
long pending, tlimit = 0;
/* If no callbacks are ready, just return. */
@@ -2474,6 +2474,7 @@ static void rcu_do_batch(struct rcu_data *rdp)
for (; rhp; rhp = rcu_cblist_dequeue(&rcl)) {
rcu_callback_t f;
+ count++;
debug_rcu_head_unqueue(rhp);
rcu_lock_acquire(&rcu_callback_map);
@@ -2487,15 +2488,14 @@ static void rcu_do_batch(struct rcu_data *rdp)
/*
* Stop only if limit reached and CPU has something to do.
- * Note: The rcl structure counts down from zero.
*/
- if (-rcl.len >= bl && !offloaded &&
+ if (count >= bl && !offloaded &&
(need_resched() ||
(!is_idle_task(current) && !rcu_is_callbacks_kthread())))
break;
if (unlikely(tlimit)) {
/* only call local_clock() every 32 callbacks */
- if (likely((-rcl.len & 31) || local_clock() < tlimit))
+ if (likely((count & 31) || local_clock() < tlimit))
continue;
/* Exceeded the time limit, so leave. */
break;
@@ -2512,7 +2512,6 @@ static void rcu_do_batch(struct rcu_data *rdp)
local_irq_save(flags);
rcu_nocb_lock(rdp);
- count = -rcl.len;
rdp->n_cbs_invoked += count;
trace_rcu_batch_end(rcu_state.name, count, !!rcl.head, need_resched(),
is_idle_task(current), rcu_is_callbacks_kthread());
@@ -2520,7 +2519,7 @@ static void rcu_do_batch(struct rcu_data *rdp)
/* Update counts and requeue any remaining callbacks. */
rcu_segcblist_insert_done_cbs(&rdp->cblist, &rcl);
smp_mb(); /* List handling before counting for rcu_barrier(). */
- rcu_segcblist_insert_count(&rdp->cblist, &rcl);
+ rcu_segcblist_add_len(&rdp->cblist, -count);
/* Reinstate batch limit if we have worked down the excess. */
count = rcu_segcblist_n_cbs(&rdp->cblist);
--
2.28.0.1011.ga647a8990f-goog
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure
2020-10-15 0:22 [PATCH v7 0/6] Add support for length of each segment in the segcblist Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 1/6] rcu/tree: Make rcu_do_batch count how many callbacks were executed Joel Fernandes (Google)
@ 2020-10-15 0:22 ` Joel Fernandes (Google)
2020-10-15 12:21 ` Frederic Weisbecker
2020-10-15 0:22 ` [PATCH v7 3/6] rcu/trace: Add tracing for how segcb list changes Joel Fernandes (Google)
` (3 subsequent siblings)
5 siblings, 1 reply; 25+ messages in thread
From: Joel Fernandes (Google) @ 2020-10-15 0:22 UTC (permalink / raw)
To: linux-kernel
Cc: Joel Fernandes (Google), Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), fweisbec,
neeraj.iitr10
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) <joel@joelfernandes.org>
---
include/linux/rcu_segcblist.h | 2 +
kernel/rcu/rcu_segcblist.c | 133 +++++++++++++++++++++++-----------
kernel/rcu/rcu_segcblist.h | 2 -
3 files changed, 92 insertions(+), 45 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 bb246d8c6ef1..d9fab49dee1b 100644
--- a/kernel/rcu/rcu_segcblist.c
+++ b/kernel/rcu/rcu_segcblist.c
@@ -7,10 +7,11 @@
* Authors: Paul E. McKenney <paulmck@linux.ibm.com>
*/
-#include <linux/types.h>
-#include <linux/kernel.h>
+#include <linux/cpu.h>
#include <linux/interrupt.h>
+#include <linux/kernel.h>
#include <linux/rcupdate.h>
+#include <linux/types.h>
#include "rcu_segcblist.h"
@@ -88,6 +89,58 @@ 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
+ atomic_long_add(v, &rsclp->seglen[seg]);
+#else
+ WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
+#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;
+
+ 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 +172,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 +182,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,7 +280,7 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
struct rcu_head *rhp)
{
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 +309,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[i], &rhp->next);
return true;
}
-/*
- * Extract only the counts from the specified rcu_segcblist structure,
- * and place them in the specified rcu_cblist structure. This function
- * supports both callback orphaning and invocation, hence the separation
- * of counts and callbacks. (Callbacks ready for invocation must be
- * orphaned and adopted separately from pending callbacks, but counts
- * apply to all callbacks. Locking must be used to make sure that
- * both orphaned-callbacks lists are consistent.)
- */
-void rcu_segcblist_extract_count(struct rcu_segcblist *rsclp,
- struct rcu_cblist *rclp)
-{
- rclp->len = rcu_segcblist_xchg_len(rsclp, 0);
-}
-
/*
* Extract only those callbacks ready to be invoked from the specified
* rcu_segcblist structure and place them in the specified rcu_cblist
@@ -307,6 +328,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 +336,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 +353,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);
+ }
}
/*
@@ -345,7 +373,6 @@ void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp,
struct rcu_cblist *rclp)
{
rcu_segcblist_add_len(rsclp, rclp->len);
- rclp->len = 0;
}
/*
@@ -359,6 +386,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 +407,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 +433,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 +454,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 +476,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))
@@ -487,6 +519,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);
+
/*
* Merge all later callbacks, including newly arrived callbacks,
* into the segment located by the for-loop above. Assign "seq"
@@ -514,13 +550,24 @@ void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp,
struct rcu_cblist donecbs;
struct rcu_cblist pendcbs;
+ lockdep_assert_cpus_held();
+
rcu_cblist_init(&donecbs);
rcu_cblist_init(&pendcbs);
- rcu_segcblist_extract_count(src_rsclp, &donecbs);
+
rcu_segcblist_extract_done_cbs(src_rsclp, &donecbs);
rcu_segcblist_extract_pend_cbs(src_rsclp, &pendcbs);
+
+ /*
+ * No need smp_mb() before setting to length to 0, because CPU hotplug
+ * lock excludes rcu_barrier.
+ */
+ rcu_segcblist_set_len(src_rsclp, 0);
+
rcu_segcblist_insert_count(dst_rsclp, &donecbs);
+ rcu_segcblist_insert_count(dst_rsclp, &pendcbs);
rcu_segcblist_insert_done_cbs(dst_rsclp, &donecbs);
rcu_segcblist_insert_pend_cbs(dst_rsclp, &pendcbs);
+
rcu_segcblist_init(src_rsclp);
}
diff --git a/kernel/rcu/rcu_segcblist.h b/kernel/rcu/rcu_segcblist.h
index 1d2d61406463..cd35c9faaf51 100644
--- a/kernel/rcu/rcu_segcblist.h
+++ b/kernel/rcu/rcu_segcblist.h
@@ -89,8 +89,6 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
struct rcu_head *rhp);
bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
struct rcu_head *rhp);
-void rcu_segcblist_extract_count(struct rcu_segcblist *rsclp,
- struct rcu_cblist *rclp);
void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
struct rcu_cblist *rclp);
void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp,
--
2.28.0.1011.ga647a8990f-goog
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH v7 3/6] rcu/trace: Add tracing for how segcb list changes
2020-10-15 0:22 [PATCH v7 0/6] Add support for length of each segment in the segcblist Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 1/6] rcu/tree: Make rcu_do_batch count how many callbacks were executed Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure Joel Fernandes (Google)
@ 2020-10-15 0:22 ` Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 4/6] rcu/segcblist: Remove useless rcupdate.h include Joel Fernandes (Google)
` (2 subsequent siblings)
5 siblings, 0 replies; 25+ messages in thread
From: Joel Fernandes (Google) @ 2020-10-15 0:22 UTC (permalink / raw)
To: linux-kernel
Cc: Joel Fernandes (Google), Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), fweisbec,
neeraj.iitr10
Track how the segcb list changes before/after acceleration, during
queuing and during dequeuing.
This has proved useful to discover an optimization to avoid unwanted GP
requests when there are no callbacks accelerated. The overhead is minimal as
each segment's length is now stored in the respective segment.
Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
include/trace/events/rcu.h | 25 +++++++++++++++++++++++++
kernel/rcu/rcu_segcblist.c | 31 +++++++++++++++++++++++++++++++
kernel/rcu/rcu_segcblist.h | 5 +++++
kernel/rcu/tree.c | 9 +++++++++
4 files changed, 70 insertions(+)
diff --git a/include/trace/events/rcu.h b/include/trace/events/rcu.h
index 155b5cb43cfd..9f2237d9b0c8 100644
--- a/include/trace/events/rcu.h
+++ b/include/trace/events/rcu.h
@@ -505,6 +505,31 @@ TRACE_EVENT_RCU(rcu_callback,
__entry->qlen)
);
+TRACE_EVENT_RCU(rcu_segcb,
+
+ TP_PROTO(const char *ctx, int *cb_count, unsigned long *gp_seq),
+
+ TP_ARGS(ctx, cb_count, gp_seq),
+
+ TP_STRUCT__entry(
+ __field(const char *, ctx)
+ __array(int, cb_count, RCU_CBLIST_NSEGS)
+ __array(unsigned long, gp_seq, RCU_CBLIST_NSEGS)
+ ),
+
+ TP_fast_assign(
+ __entry->ctx = ctx;
+ memcpy(__entry->cb_count, cb_count, RCU_CBLIST_NSEGS * sizeof(int));
+ memcpy(__entry->gp_seq, gp_seq, RCU_CBLIST_NSEGS * sizeof(unsigned long));
+ ),
+
+ TP_printk("%s cb_count: (DONE=%d, WAIT=%d, NEXT_READY=%d, NEXT=%d) "
+ "gp_seq: (DONE=%lu, WAIT=%lu, NEXT_READY=%lu, NEXT=%lu)", __entry->ctx,
+ __entry->cb_count[0], __entry->cb_count[1], __entry->cb_count[2], __entry->cb_count[3],
+ __entry->gp_seq[0], __entry->gp_seq[1], __entry->gp_seq[2], __entry->gp_seq[3])
+
+);
+
/*
* Tracepoint for the registration of a single RCU callback of the special
* kvfree() form. The first argument is the RCU type, the second argument
diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
index d9fab49dee1b..2dccbd29cd3a 100644
--- a/kernel/rcu/rcu_segcblist.c
+++ b/kernel/rcu/rcu_segcblist.c
@@ -14,6 +14,7 @@
#include <linux/types.h>
#include "rcu_segcblist.h"
+#include "rcu.h"
/* Initialize simple callback list. */
void rcu_cblist_init(struct rcu_cblist *rclp)
@@ -339,6 +340,36 @@ void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
rcu_segcblist_set_seglen(rsclp, RCU_DONE_TAIL, 0);
}
+/*
+ * Return how many CBs each segment along with their gp_seq values.
+ *
+ * This function is O(N) where N is the number of segments. Only used from
+ * tracing code which is usually disabled in production.
+ */
+#ifdef CONFIG_RCU_TRACE
+static void rcu_segcblist_countseq(struct rcu_segcblist *rsclp,
+ int cbcount[RCU_CBLIST_NSEGS],
+ unsigned long gpseq[RCU_CBLIST_NSEGS])
+{
+ int i;
+
+ for (i = 0; i < RCU_CBLIST_NSEGS; i++) {
+ cbcount[i] = rcu_segcblist_get_seglen(rsclp, i);
+ gpseq[i] = rsclp->gp_seq[i];
+ }
+}
+
+void trace_rcu_segcb_list(struct rcu_segcblist *rsclp, const char *context)
+{
+ int cbs[RCU_CBLIST_NSEGS];
+ unsigned long gps[RCU_CBLIST_NSEGS];
+
+ rcu_segcblist_countseq(rsclp, cbs, gps);
+
+ trace_rcu_segcb(context, cbs, gps);
+}
+#endif
+
/*
* Extract only those callbacks still pending (not yet ready to be
* invoked) from the specified rcu_segcblist structure and place them in
diff --git a/kernel/rcu/rcu_segcblist.h b/kernel/rcu/rcu_segcblist.h
index cd35c9faaf51..c2e274ae0912 100644
--- a/kernel/rcu/rcu_segcblist.h
+++ b/kernel/rcu/rcu_segcblist.h
@@ -103,3 +103,8 @@ void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq);
bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq);
void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp,
struct rcu_segcblist *src_rsclp);
+#ifdef CONFIG_RCU_TRACE
+void trace_rcu_segcb_list(struct rcu_segcblist *rsclp, const char *context);
+#else
+#define trace_rcu_segcb_list(...)
+#endif
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 24c00020ab83..346a05506935 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -1497,6 +1497,8 @@ static bool rcu_accelerate_cbs(struct rcu_node *rnp, struct rcu_data *rdp)
if (!rcu_segcblist_pend_cbs(&rdp->cblist))
return false;
+ trace_rcu_segcb_list(&rdp->cblist, TPS("SegCbPreAcc"));
+
/*
* Callbacks are often registered with incomplete grace-period
* information. Something about the fact that getting exact
@@ -1517,6 +1519,8 @@ static bool rcu_accelerate_cbs(struct rcu_node *rnp, struct rcu_data *rdp)
else
trace_rcu_grace_period(rcu_state.name, gp_seq_req, TPS("AccReadyCB"));
+ trace_rcu_segcb_list(&rdp->cblist, TPS("SegCbPostAcc"));
+
return ret;
}
@@ -2466,11 +2470,14 @@ static void rcu_do_batch(struct rcu_data *rdp)
rcu_segcblist_extract_done_cbs(&rdp->cblist, &rcl);
if (offloaded)
rdp->qlen_last_fqs_check = rcu_segcblist_n_cbs(&rdp->cblist);
+
+ trace_rcu_segcb_list(&rdp->cblist, TPS("SegCbDequeued"));
rcu_nocb_unlock_irqrestore(rdp, flags);
/* Invoke callbacks. */
tick_dep_set_task(current, TICK_DEP_BIT_RCU);
rhp = rcu_cblist_dequeue(&rcl);
+
for (; rhp; rhp = rcu_cblist_dequeue(&rcl)) {
rcu_callback_t f;
@@ -2983,6 +2990,8 @@ __call_rcu(struct rcu_head *head, rcu_callback_t func)
trace_rcu_callback(rcu_state.name, head,
rcu_segcblist_n_cbs(&rdp->cblist));
+ trace_rcu_segcb_list(&rdp->cblist, TPS("SegCBQueued"));
+
/* Go handle any RCU core processing required. */
if (unlikely(rcu_segcblist_is_offloaded(&rdp->cblist))) {
__call_rcu_nocb_wake(rdp, was_alldone, flags); /* unlocks */
--
2.28.0.1011.ga647a8990f-goog
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH v7 4/6] rcu/segcblist: Remove useless rcupdate.h include
2020-10-15 0:22 [PATCH v7 0/6] Add support for length of each segment in the segcblist Joel Fernandes (Google)
` (2 preceding siblings ...)
2020-10-15 0:22 ` [PATCH v7 3/6] rcu/trace: Add tracing for how segcb list changes Joel Fernandes (Google)
@ 2020-10-15 0:22 ` Joel Fernandes (Google)
2020-10-15 0:23 ` [PATCH v7 5/6] rcu/tree: Remove redundant smp_mb() in rcu_do_batch Joel Fernandes (Google)
2020-10-15 0:23 ` [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb() Joel Fernandes (Google)
5 siblings, 0 replies; 25+ messages in thread
From: Joel Fernandes (Google) @ 2020-10-15 0:22 UTC (permalink / raw)
To: linux-kernel
Cc: Joel Fernandes (Google), Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), fweisbec,
neeraj.iitr10
Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
kernel/rcu/rcu_segcblist.c | 1 -
1 file changed, 1 deletion(-)
diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
index 2dccbd29cd3a..271d5d9d7f60 100644
--- a/kernel/rcu/rcu_segcblist.c
+++ b/kernel/rcu/rcu_segcblist.c
@@ -10,7 +10,6 @@
#include <linux/cpu.h>
#include <linux/interrupt.h>
#include <linux/kernel.h>
-#include <linux/rcupdate.h>
#include <linux/types.h>
#include "rcu_segcblist.h"
--
2.28.0.1011.ga647a8990f-goog
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH v7 5/6] rcu/tree: Remove redundant smp_mb() in rcu_do_batch
2020-10-15 0:22 [PATCH v7 0/6] Add support for length of each segment in the segcblist Joel Fernandes (Google)
` (3 preceding siblings ...)
2020-10-15 0:22 ` [PATCH v7 4/6] rcu/segcblist: Remove useless rcupdate.h include Joel Fernandes (Google)
@ 2020-10-15 0:23 ` Joel Fernandes (Google)
2020-10-15 0:23 ` [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb() Joel Fernandes (Google)
5 siblings, 0 replies; 25+ messages in thread
From: Joel Fernandes (Google) @ 2020-10-15 0:23 UTC (permalink / raw)
To: linux-kernel
Cc: Joel Fernandes (Google), Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), fweisbec,
neeraj.iitr10
This memory barrier is not needed as rcu_segcblist_add_len() already
includes a memory barrier.
Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
kernel/rcu/tree.c | 1 -
1 file changed, 1 deletion(-)
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 346a05506935..6c6d3c7036e6 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -2525,7 +2525,6 @@ static void rcu_do_batch(struct rcu_data *rdp)
/* Update counts and requeue any remaining callbacks. */
rcu_segcblist_insert_done_cbs(&rdp->cblist, &rcl);
- smp_mb(); /* List handling before counting for rcu_barrier(). */
rcu_segcblist_add_len(&rdp->cblist, -count);
/* Reinstate batch limit if we have worked down the excess. */
--
2.28.0.1011.ga647a8990f-goog
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-15 0:22 [PATCH v7 0/6] Add support for length of each segment in the segcblist Joel Fernandes (Google)
` (4 preceding siblings ...)
2020-10-15 0:23 ` [PATCH v7 5/6] rcu/tree: Remove redundant smp_mb() in rcu_do_batch Joel Fernandes (Google)
@ 2020-10-15 0:23 ` Joel Fernandes (Google)
2020-10-15 13:35 ` Frederic Weisbecker
5 siblings, 1 reply; 25+ messages in thread
From: Joel Fernandes (Google) @ 2020-10-15 0:23 UTC (permalink / raw)
To: linux-kernel
Cc: Joel Fernandes (Google), Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), fweisbec,
neeraj.iitr10
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) <joel@joelfernandes.org>
---
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
^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure
2020-10-15 0:22 ` [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure Joel Fernandes (Google)
@ 2020-10-15 12:21 ` Frederic Weisbecker
2020-10-17 1:31 ` joel
2020-10-21 15:33 ` joel
0 siblings, 2 replies; 25+ messages in thread
From: Frederic Weisbecker @ 2020-10-15 12:21 UTC (permalink / raw)
To: Joel Fernandes (Google)
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10
On Wed, Oct 14, 2020 at 08:22:57PM -0400, Joel Fernandes (Google) wrote:
> 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) <joel@joelfernandes.org>
> ---
> include/linux/rcu_segcblist.h | 2 +
> kernel/rcu/rcu_segcblist.c | 133 +++++++++++++++++++++++-----------
> kernel/rcu/rcu_segcblist.h | 2 -
> 3 files changed, 92 insertions(+), 45 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];
Also does it really need to be atomic?
> @@ -245,7 +280,7 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
> struct rcu_head *rhp)
> {
> rcu_segcblist_inc_len(rsclp);
> - smp_mb(); /* Ensure counts are updated before callback is enqueued. */
That's a significant change that shouldn't be hidden and unexplained in an unrelated
patch or it may be easily missed. I'd suggest to move this line together in
"rcu/tree: Remove redundant smp_mb() in rcu_do_batch" (with the title updated perhaps)
and maybe put it in the beginning of the series?
> + 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);
[...]
> @@ -330,11 +353,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);
> + }
So, that's probably just a matter of personal preference, so feel free to
ignore but I'd rather do:
rclp->len += rcu_segcblist_get_seglen(rsclp, i);
rcu_segcblist_set_seglen(rsclp, i, 0);
instead of the big addition above. That way, if a new index ever gets added/renamed
to the segcblist, we'll take it into account. Also that spares a few lines.
Thanks.
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-15 0:23 ` [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb() Joel Fernandes (Google)
@ 2020-10-15 13:35 ` Frederic Weisbecker
2020-10-17 1:27 ` joel
0 siblings, 1 reply; 25+ messages in thread
From: Frederic Weisbecker @ 2020-10-15 13:35 UTC (permalink / raw)
To: Joel Fernandes (Google)
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10
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) <joel@joelfernandes.org>
> ---
> 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.
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-15 13:35 ` Frederic Weisbecker
@ 2020-10-17 1:27 ` joel
2020-10-17 3:19 ` joel
2020-10-17 14:31 ` Alan Stern
0 siblings, 2 replies; 25+ messages in thread
From: joel @ 2020-10-17 1:27 UTC (permalink / raw)
To: Frederic Weisbecker
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10,
stern
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) <joel@joelfernandes.org>
> > ---
> > 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
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure
2020-10-15 12:21 ` Frederic Weisbecker
@ 2020-10-17 1:31 ` joel
2020-10-21 15:33 ` joel
1 sibling, 0 replies; 25+ messages in thread
From: joel @ 2020-10-17 1:31 UTC (permalink / raw)
To: Frederic Weisbecker
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10
On Thu, Oct 15, 2020 at 02:21:58PM +0200, Frederic Weisbecker wrote:
> On Wed, Oct 14, 2020 at 08:22:57PM -0400, Joel Fernandes (Google) wrote:
> > 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) <joel@joelfernandes.org>
> > ---
> > include/linux/rcu_segcblist.h | 2 +
> > kernel/rcu/rcu_segcblist.c | 133 +++++++++++++++++++++++-----------
> > kernel/rcu/rcu_segcblist.h | 2 -
> > 3 files changed, 92 insertions(+), 45 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];
>
> Also does it really need to be atomic?
Yeah I think not. In fact, I am not even sure if ->len in the existing code
needs to be atomic. I am considering vetting all code paths. Paul told me it
used to be the case that ->len could be lockless written (possibly without
IRQs disabled) I think but that maybe nowadays it is not the case. Let us
double check to be sure.
> > @@ -245,7 +280,7 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
> > struct rcu_head *rhp)
> > {
> > rcu_segcblist_inc_len(rsclp);
> > - smp_mb(); /* Ensure counts are updated before callback is enqueued. */
>
> That's a significant change that shouldn't be hidden and unexplained in an unrelated
> patch or it may be easily missed. I'd suggest to move this line together in
> "rcu/tree: Remove redundant smp_mb() in rcu_do_batch" (with the title updated perhaps)
> and maybe put it in the beginning of the series?
Ok I can do that.
> > + 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);
> [...]
> > @@ -330,11 +353,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);
> > + }
>
> So, that's probably just a matter of personal preference, so feel free to
> ignore but I'd rather do:
>
> rclp->len += rcu_segcblist_get_seglen(rsclp, i);
> rcu_segcblist_set_seglen(rsclp, i, 0);
>
> instead of the big addition above. That way, if a new index ever gets added/renamed
> to the segcblist, we'll take it into account. Also that spares a few lines.
Yeah your way is better, I will do it this way.
thanks,
- Joel
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-17 1:27 ` joel
@ 2020-10-17 3:19 ` joel
2020-10-17 13:29 ` Frederic Weisbecker
2020-10-17 20:24 ` Alan Stern
2020-10-17 14:31 ` Alan Stern
1 sibling, 2 replies; 25+ messages in thread
From: joel @ 2020-10-17 3:19 UTC (permalink / raw)
To: Frederic Weisbecker
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10,
stern
On Fri, Oct 16, 2020 at 09:27:53PM -0400, joel@joelfernandes.org 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)
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-17 3:19 ` joel
@ 2020-10-17 13:29 ` Frederic Weisbecker
2020-10-18 0:35 ` joel
2020-10-17 20:24 ` Alan Stern
1 sibling, 1 reply; 25+ messages in thread
From: Frederic Weisbecker @ 2020-10-17 13:29 UTC (permalink / raw)
To: joel
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10,
stern
On Fri, Oct 16, 2020 at 11:19:41PM -0400, joel@joelfernandes.org wrote:
> On Fri, Oct 16, 2020 at 09:27:53PM -0400, joel@joelfernandes.org 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.
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-17 1:27 ` joel
2020-10-17 3:19 ` joel
@ 2020-10-17 14:31 ` Alan Stern
2020-10-18 20:16 ` Joel Fernandes
1 sibling, 1 reply; 25+ messages in thread
From: Alan Stern @ 2020-10-17 14:31 UTC (permalink / raw)
To: joel
Cc: Frederic Weisbecker, linux-kernel, Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), fweisbec,
neeraj.iitr10
On Fri, Oct 16, 2020 at 09:27:53PM -0400, joel@joelfernandes.org 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
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-17 3:19 ` joel
2020-10-17 13:29 ` Frederic Weisbecker
@ 2020-10-17 20:24 ` Alan Stern
2020-10-18 20:45 ` Joel Fernandes
1 sibling, 1 reply; 25+ messages in thread
From: Alan Stern @ 2020-10-17 20:24 UTC (permalink / raw)
To: joel
Cc: Frederic Weisbecker, linux-kernel, Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), fweisbec,
neeraj.iitr10
[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, joel@joelfernandes.org 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
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-17 13:29 ` Frederic Weisbecker
@ 2020-10-18 0:35 ` joel
2020-10-19 12:37 ` Frederic Weisbecker
0 siblings, 1 reply; 25+ messages in thread
From: joel @ 2020-10-18 0:35 UTC (permalink / raw)
To: Frederic Weisbecker
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10,
stern
On Sat, Oct 17, 2020 at 03:29:54PM +0200, Frederic Weisbecker wrote:
> On Fri, Oct 16, 2020 at 11:19:41PM -0400, joel@joelfernandes.org wrote:
> > On Fri, Oct 16, 2020 at 09:27:53PM -0400, joel@joelfernandes.org 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
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-17 14:31 ` Alan Stern
@ 2020-10-18 20:16 ` Joel Fernandes
0 siblings, 0 replies; 25+ messages in thread
From: Joel Fernandes @ 2020-10-18 20:16 UTC (permalink / raw)
To: Alan Stern
Cc: Frederic Weisbecker, LKML, Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), Frederic Weisbecker,
Neeraj upadhyay
On Sat, Oct 17, 2020 at 7:31 AM Alan Stern <stern@rowland.harvard.edu> wrote:
>
> On Fri, Oct 16, 2020 at 09:27:53PM -0400, joel@joelfernandes.org 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
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-17 20:24 ` Alan Stern
@ 2020-10-18 20:45 ` Joel Fernandes
2020-10-18 21:15 ` Alan Stern
0 siblings, 1 reply; 25+ messages in thread
From: Joel Fernandes @ 2020-10-18 20:45 UTC (permalink / raw)
To: Alan Stern
Cc: Frederic Weisbecker, LKML, Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), Frederic Weisbecker,
Neeraj upadhyay
Hi,
Thanks Alan for your replies.
On Sat, Oct 17, 2020 at 1:24 PM Alan Stern <stern@rowland.harvard.edu> 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, joel@joelfernandes.org 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
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-18 20:45 ` Joel Fernandes
@ 2020-10-18 21:15 ` Alan Stern
0 siblings, 0 replies; 25+ messages in thread
From: Alan Stern @ 2020-10-18 21:15 UTC (permalink / raw)
To: Joel Fernandes
Cc: Frederic Weisbecker, LKML, Ingo Molnar, Josh Triplett,
Lai Jiangshan, Marco Elver, Mathieu Desnoyers, Paul E. McKenney,
rcu, Steven Rostedt, Uladzislau Rezki (Sony), Frederic Weisbecker,
Neeraj upadhyay
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
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-18 0:35 ` joel
@ 2020-10-19 12:37 ` Frederic Weisbecker
2020-10-21 18:57 ` Joel Fernandes
0 siblings, 1 reply; 25+ messages in thread
From: Frederic Weisbecker @ 2020-10-19 12:37 UTC (permalink / raw)
To: joel
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10,
stern
On Sat, Oct 17, 2020 at 08:35:56PM -0400, joel@joelfernandes.org 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.
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure
2020-10-15 12:21 ` Frederic Weisbecker
2020-10-17 1:31 ` joel
@ 2020-10-21 15:33 ` joel
2020-10-21 21:53 ` Frederic Weisbecker
1 sibling, 1 reply; 25+ messages in thread
From: joel @ 2020-10-21 15:33 UTC (permalink / raw)
To: Frederic Weisbecker
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10
On Thu, Oct 15, 2020 at 02:21:58PM +0200, Frederic Weisbecker wrote:
> On Wed, Oct 14, 2020 at 08:22:57PM -0400, Joel Fernandes (Google) wrote:
> > 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) <joel@joelfernandes.org>
> > ---
> > include/linux/rcu_segcblist.h | 2 +
> > kernel/rcu/rcu_segcblist.c | 133 +++++++++++++++++++++++-----------
> > kernel/rcu/rcu_segcblist.h | 2 -
> > 3 files changed, 92 insertions(+), 45 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];
>
> Also does it really need to be atomic?
Yes, it need not be. I will make the change for ->seglen.
BTW, for the existing ->len field, doesn't the following need to acquire nocb
lock?
rcu_nocb_try_bypass -> rcu_segcblist_inc_len
It seems that will do a lock-less non-atomic RMW on a nocb offloaded list,
otherwise.
Certainly rcu_nocb_do_flush_bypass() does do it so maybe it was missed?
> > @@ -245,7 +280,7 @@ void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
> > struct rcu_head *rhp)
> > {
> > rcu_segcblist_inc_len(rsclp);
> > - smp_mb(); /* Ensure counts are updated before callback is enqueued. */
>
> That's a significant change that shouldn't be hidden and unexplained in an unrelated
> patch or it may be easily missed. I'd suggest to move this line together in
> "rcu/tree: Remove redundant smp_mb() in rcu_do_batch" (with the title updated perhaps)
> and maybe put it in the beginning of the series?
Will do as you suggest, makes sense.
> > + 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);
> [...]
> > @@ -330,11 +353,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);
> > + }
>
> So, that's probably just a matter of personal preference, so feel free to
> ignore but I'd rather do:
>
> rclp->len += rcu_segcblist_get_seglen(rsclp, i);
> rcu_segcblist_set_seglen(rsclp, i, 0);
>
> instead of the big addition above. That way, if a new index ever gets added/renamed
> to the segcblist, we'll take it into account. Also that spares a few lines.
Makes senes, will do.
thanks,
- Joel
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-19 12:37 ` Frederic Weisbecker
@ 2020-10-21 18:57 ` Joel Fernandes
2020-10-21 21:16 ` Frederic Weisbecker
0 siblings, 1 reply; 25+ messages in thread
From: Joel Fernandes @ 2020-10-21 18:57 UTC (permalink / raw)
To: Frederic Weisbecker
Cc: LKML, Ingo Molnar, Josh Triplett, Lai Jiangshan, Marco Elver,
Mathieu Desnoyers, Paul E. McKenney, rcu, Steven Rostedt,
Uladzislau Rezki (Sony), Frederic Weisbecker, Neeraj upadhyay,
Alan Stern
On Mon, Oct 19, 2020 at 5:37 AM Frederic Weisbecker <frederic@kernel.org> 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
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb()
2020-10-21 18:57 ` Joel Fernandes
@ 2020-10-21 21:16 ` Frederic Weisbecker
0 siblings, 0 replies; 25+ messages in thread
From: Frederic Weisbecker @ 2020-10-21 21:16 UTC (permalink / raw)
To: Joel Fernandes
Cc: LKML, Ingo Molnar, Josh Triplett, Lai Jiangshan, Marco Elver,
Mathieu Desnoyers, Paul E. McKenney, rcu, Steven Rostedt,
Uladzislau Rezki (Sony), Frederic Weisbecker, Neeraj upadhyay,
Alan Stern
On Wed, Oct 21, 2020 at 11:57:04AM -0700, Joel Fernandes wrote:
> On Mon, Oct 19, 2020 at 5:37 AM Frederic Weisbecker <frederic@kernel.org> 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!
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure
2020-10-21 15:33 ` joel
@ 2020-10-21 21:53 ` Frederic Weisbecker
2020-10-21 22:31 ` Joel Fernandes
0 siblings, 1 reply; 25+ messages in thread
From: Frederic Weisbecker @ 2020-10-21 21:53 UTC (permalink / raw)
To: joel
Cc: linux-kernel, Ingo Molnar, Josh Triplett, Lai Jiangshan,
Marco Elver, Mathieu Desnoyers, Paul E. McKenney, rcu,
Steven Rostedt, Uladzislau Rezki (Sony), fweisbec, neeraj.iitr10
On Wed, Oct 21, 2020 at 11:33:14AM -0400, joel@joelfernandes.org wrote:
> On Thu, Oct 15, 2020 at 02:21:58PM +0200, Frederic Weisbecker wrote:
> > On Wed, Oct 14, 2020 at 08:22:57PM -0400, Joel Fernandes (Google) wrote:
> > > 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) <joel@joelfernandes.org>
> > > ---
> > > include/linux/rcu_segcblist.h | 2 +
> > > kernel/rcu/rcu_segcblist.c | 133 +++++++++++++++++++++++-----------
> > > kernel/rcu/rcu_segcblist.h | 2 -
> > > 3 files changed, 92 insertions(+), 45 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];
> >
> > Also does it really need to be atomic?
>
> Yes, it need not be. I will make the change for ->seglen.
>
> BTW, for the existing ->len field, doesn't the following need to acquire nocb
> lock?
> rcu_nocb_try_bypass -> rcu_segcblist_inc_len
>
> It seems that will do a lock-less non-atomic RMW on a nocb offloaded list,
> otherwise.
I believe it shouldn't be necessary. That's an atomic add and the kthreads
manipulating it shouldn't have any trouble concurrently. None that I can
imagine tonight at least...
> Certainly rcu_nocb_do_flush_bypass() does do it so maybe it was missed?
I believe it increments under the lock here because the inc happens to be on the way
to the insertion of the callbacks :o)
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure
2020-10-21 21:53 ` Frederic Weisbecker
@ 2020-10-21 22:31 ` Joel Fernandes
0 siblings, 0 replies; 25+ messages in thread
From: Joel Fernandes @ 2020-10-21 22:31 UTC (permalink / raw)
To: Frederic Weisbecker
Cc: LKML, Ingo Molnar, Josh Triplett, Lai Jiangshan, Marco Elver,
Mathieu Desnoyers, Paul E. McKenney, rcu, Steven Rostedt,
Uladzislau Rezki (Sony), Frederic Weisbecker, Neeraj upadhyay
On Wed, Oct 21, 2020 at 2:53 PM Frederic Weisbecker <frederic@kernel.org> wrote:
>
> On Wed, Oct 21, 2020 at 11:33:14AM -0400, joel@joelfernandes.org wrote:
> > On Thu, Oct 15, 2020 at 02:21:58PM +0200, Frederic Weisbecker wrote:
> > > On Wed, Oct 14, 2020 at 08:22:57PM -0400, Joel Fernandes (Google) wrote:
> > > > 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) <joel@joelfernandes.org>
> > > > ---
> > > > include/linux/rcu_segcblist.h | 2 +
> > > > kernel/rcu/rcu_segcblist.c | 133 +++++++++++++++++++++++-----------
> > > > kernel/rcu/rcu_segcblist.h | 2 -
> > > > 3 files changed, 92 insertions(+), 45 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];
> > >
> > > Also does it really need to be atomic?
> >
> > Yes, it need not be. I will make the change for ->seglen.
> >
> > BTW, for the existing ->len field, doesn't the following need to acquire nocb
> > lock?
> > rcu_nocb_try_bypass -> rcu_segcblist_inc_len
> >
> > It seems that will do a lock-less non-atomic RMW on a nocb offloaded list,
> > otherwise.
>
> I believe it shouldn't be necessary. That's an atomic add and the kthreads
> manipulating it shouldn't have any trouble concurrently. None that I can
> imagine tonight at least...
Ah yeah, of course. I got confused! Thanks.
> > Certainly rcu_nocb_do_flush_bypass() does do it so maybe it was missed?
>
> I believe it increments under the lock here because the inc happens to be on the way
> to the insertion of the callbacks :o)
Makes sense :)
thanks,
- Joel
^ permalink raw reply [flat|nested] 25+ messages in thread
end of thread, other threads:[~2020-10-21 22:31 UTC | newest]
Thread overview: 25+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2020-10-15 0:22 [PATCH v7 0/6] Add support for length of each segment in the segcblist Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 1/6] rcu/tree: Make rcu_do_batch count how many callbacks were executed Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 2/6] rcu/segcblist: Add counters to segcblist datastructure Joel Fernandes (Google)
2020-10-15 12:21 ` Frederic Weisbecker
2020-10-17 1:31 ` joel
2020-10-21 15:33 ` joel
2020-10-21 21:53 ` Frederic Weisbecker
2020-10-21 22:31 ` Joel Fernandes
2020-10-15 0:22 ` [PATCH v7 3/6] rcu/trace: Add tracing for how segcb list changes Joel Fernandes (Google)
2020-10-15 0:22 ` [PATCH v7 4/6] rcu/segcblist: Remove useless rcupdate.h include Joel Fernandes (Google)
2020-10-15 0:23 ` [PATCH v7 5/6] rcu/tree: Remove redundant smp_mb() in rcu_do_batch Joel Fernandes (Google)
2020-10-15 0:23 ` [PATCH v7 6/6] rcu/segcblist: Add additional comments to explain smp_mb() Joel Fernandes (Google)
2020-10-15 13:35 ` Frederic Weisbecker
2020-10-17 1:27 ` joel
2020-10-17 3:19 ` joel
2020-10-17 13:29 ` Frederic Weisbecker
2020-10-18 0:35 ` joel
2020-10-19 12:37 ` Frederic Weisbecker
2020-10-21 18:57 ` Joel Fernandes
2020-10-21 21:16 ` Frederic Weisbecker
2020-10-17 20:24 ` Alan Stern
2020-10-18 20:45 ` Joel Fernandes
2020-10-18 21:15 ` Alan Stern
2020-10-17 14:31 ` Alan Stern
2020-10-18 20:16 ` Joel Fernandes
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).