[PATCH v2] srcu: Add try_synchronize_srcu() for callers which can prove readers absent

For a dedicated srcu_struct whose read-side critical sections are
short, atomic, and usually absent — such as one converted from a
spinning lock — the common case at synchronize time is that there are
no readers at all. Even synchronize_srcu_expedited() still costs the
caller an unconditional sleep and two trips through the SRCU workqueue
to discover that: tens of microseconds of machinery to wait for
nothing. And synchronize_srcu()'s auto-expedite heuristic explicitly
declines to expedite within exp_holdoff (25µs) of the previous grace
period, which is exactly the regime a burst of back-to-back
invalidations puts such a domain in.

Provide try_synchronize_srcu(), which proves the no-readers case
inline and returns true without sleeping, without the workqueue, and
without advancing the grace-period sequence. A successful return
provides the caller the full happens-before guarantee of
synchronize_srcu(), but is not a grace-period completion for the
state and callback APIs: cookies from get_state_synchronize_srcu()
remain unfinished and queued callbacks are not invoked. If the proof
fails, it returns false and the caller falls back:

	if (!try_synchronize_srcu(ssp))
		synchronize_srcu_expedited(ssp);

For Tree SRCU the proof sums both epochs' unlock counters, executes a
full barrier, then sums both epochs' lock counters. Equality proves a
moment within this function at which no reader existed: a reader
entering between the sums inflates only the lock sum (spurious
fallback, safe), and a reader whose increment is unobserved has not
yet returned from srcu_read_lock() — the barrier pairing with
__srcu_read_lock() guarantees such a reader sees every store the
caller made beforehand, so it is not a reader the caller is obliged
to wait for. Summing both epochs means no index flip is required, and
without a flip the counter-wrap concerns of
srcu_readers_active_idx_check() do not arise. Readers of the _fast()
flavors elide the read-side barrier this depends on; any sign of them
(in the unlock-side rdm mask, which is gathered unconditionally)
disqualifies the fast path.

For Tiny SRCU (!SMP) both nesting counts being zero already proves no
reader exists — a mid-section reader could only be preempted or in an
interrupt, either of which leaves its count visibly elevated — and
program order on the sole CPU provides all the required ordering.

The immediate motivation is a proposed conversion of KVM's
gfn_to_pfn_cache to use SRCU¹, where the mmu_notifier invalidation
path must drain readers of a cache (in the manner of a TLB shootdown)
before the primary MMU zaps the backing page. Those readers are short
non-sleeping fast paths, some in contexts which cannot sleep (hardirq
event channel delivery, the scheduler's sched-out hook); measurement
under a worst-case invalidation flood shows 98.8% of drains complete
inline in 4-16µs where the expedited grace period took 32-128µs, with
the wait dominated by workqueue round-trip latency, not by readers.

¹ https://lore.kernel.org/all/[email protected]/

More potential use cases already exist in the tree with the same
no-readers-common-case profile: kvm->irq_srcu takes half a dozen
expedited grace periods in the irqfd and routing-update paths (bursts
of which, at VM boot, fall inside the exp_holdoff window), and mshv's
pt_irq_srcu is the same shape.

Signed-off-by: David Woodhouse <[email protected]>
Assisted-by: Claude:claude-mythos-5
---
v2 (all per Kunwu Chan's review):
 - Rebase onto rcu/dev (check_init_srcu_struct() is_atomic argument).
 - Drop the leading smp_mb(): the middle barrier already orders the
   caller's prior stores before the lock-counter reads, which is the
   only edge the store-buffering pairing needs; document the middle
   barrier's double duty (matching srcu_readers_active_idx_check(),
   which likewise has no barrier before its unlock reads).
 - Add the same-type-read-side RCU_LOCKDEP_WARN() as in
   synchronize_srcu(), to both Tree and Tiny variants.
 - Document that success is not a grace-period completion for the
   cookie/callback APIs.

Compile-tested for Tiny SRCU (tinyconfig); the Tree version has had
the KVM gfn_to_pfn_cache conversion soaking on it under an adversarial
invalidation flood (48h KASAN+lockdep clean, though of the v1 barrier
arrangement; the v2 change only removes a barrier proven redundant).
---
 include/linux/srcu.h  |  1 +
 kernel/rcu/srcutiny.c | 29 ++++++++++++++++
 kernel/rcu/srcutree.c | 81 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 111 insertions(+)

diff --git a/include/linux/srcu.h b/include/linux/srcu.h
index 60100d8a2671..ee32c2583b30 100644
--- a/include/linux/srcu.h
+++ b/include/linux/srcu.h
@@ -105,6 +105,7 @@ void call_srcu(struct srcu_struct *ssp, struct rcu_head *head,
 void cleanup_srcu_struct(struct srcu_struct *ssp);
 void synchronize_srcu(struct srcu_struct *ssp);
 void synchronize_srcu_atomic(struct srcu_struct *ssp);
+bool try_synchronize_srcu(struct srcu_struct *ssp);
 
 #define SRCU_GET_STATE_COMPLETED 0x1
 
diff --git a/kernel/rcu/srcutiny.c b/kernel/rcu/srcutiny.c
index 32b37d63d58a..eb8beb365c1f 100644
--- a/kernel/rcu/srcutiny.c
+++ b/kernel/rcu/srcutiny.c
@@ -347,6 +347,35 @@ void srcu_barrier(struct srcu_struct *ssp)
 }
 EXPORT_SYMBOL_GPL(srcu_barrier);
 
+/**
+ * try_synchronize_srcu - inline grace period for a reader-free srcu_struct
+ * @ssp: srcu_struct with which to synchronize.
+ *
+ * If @ssp provably has no readers in either epoch, provide the
+ * synchronize_srcu() guarantee to the caller immediately, without
+ * sleeping. Returns true on success; on failure the caller must fall
+ * back to synchronize_srcu().
+ *
+ * On !SMP a reader can only be mid-critical-section if it was
+ * preempted (or is running in an interrupt which preempted us), in
+ * which case its nesting count is visibly non-zero. Both counts being
+ * zero therefore proves that no reader exists, and any reader which
+ * begins after this function returns will, by program order on this
+ * sole CPU, observe every store the caller made before calling it.
+ */
+bool try_synchronize_srcu(struct srcu_struct *ssp)
+{
+	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
+			lock_is_held(&rcu_bh_lock_map) ||
+			lock_is_held(&rcu_lock_map) ||
+			lock_is_held(&rcu_sched_lock_map),
+			"Illegal try_synchronize_srcu() in same-type SRCU (or in RCU) read-side critical section");
+
+	return !READ_ONCE(ssp->srcu_lock_nesting[0]) &&
+	       !READ_ONCE(ssp->srcu_lock_nesting[1]);
+}
+EXPORT_SYMBOL_GPL(try_synchronize_srcu);
+
 /*
  * get_state_synchronize_srcu - Provide an end-of-grace-period cookie
  */
diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index e44763e198e3..c3a2170d05db 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -1714,6 +1714,87 @@ void synchronize_srcu(struct srcu_struct *ssp)
 }
 EXPORT_SYMBOL_GPL(synchronize_srcu);
 
+/**
+ * try_synchronize_srcu - inline grace period for a reader-free srcu_struct
+ * @ssp: srcu_struct with which to synchronize.
+ *
+ * If @ssp provably has no readers in either epoch, provide the
+ * synchronize_srcu() guarantee to the caller immediately: without
+ * sleeping, without a trip through the SRCU workqueue, and without
+ * advancing the grace-period sequence. Returns true on success; on
+ * failure the caller must fall back to synchronize_srcu() or
+ * synchronize_srcu_expedited().
+ *
+ * This serves dedicated srcu_struct structures whose read-side critical
+ * sections are short, atomic, and usually absent — where even an
+ * expedited grace period costs two trips through the workqueue and an
+ * unconditional sleep of the caller, three orders of magnitude more
+ * than the check below.
+ *
+ * Only readers of the srcu_read_lock() and srcu_read_lock_nmisafe()
+ * flavors are compatible with this proof; if the _fast() flavors have
+ * ever been used on @ssp, this function always returns false.
+ *
+ * Note that a successful return provides the caller the full
+ * happens-before guarantee of synchronize_srcu(), but does NOT
+ * constitute a grace-period completion for the state and callback
+ * APIs: the grace-period sequence is not advanced, so cookies from
+ * get_state_synchronize_srcu() remain unfinished and queued callbacks
+ * are not invoked.
+ */
+bool try_synchronize_srcu(struct srcu_struct *ssp)
+{
+	unsigned long unlocks0, unlocks1;
+	unsigned long rdm0, rdm1;
+
+	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
+			 lock_is_held(&rcu_bh_lock_map) ||
+			 lock_is_held(&rcu_lock_map) ||
+			 lock_is_held(&rcu_sched_lock_map),
+			 "Illegal try_synchronize_srcu() in same-type SRCU (or in RCU) read-side critical section");
+
+	check_init_srcu_struct(ssp, false);
+
+	unlocks0 = srcu_readers_unlock_idx(ssp, 0, &rdm0);
+	unlocks1 = srcu_readers_unlock_idx(ssp, 1, &rdm1);
+
+	/*
+	 * Reader flavors which elide the read-side smp_mb() that the
+	 * pairings below depend on cannot be proven absent this way;
+	 * they need a real grace period.
+	 */
+	if ((rdm0 | rdm1) & SRCU_READ_FLAVOR_SLOWGP)
+		return false;
+
+	/*
+	 * As in srcu_readers_active_idx_check(), this barrier serves two
+	 * purposes. First, it ensures that a lock is always counted if
+	 * the corresponding unlock is counted, so that a reader racing
+	 * with these sums can only inflate the lock sum and force the
+	 * (safe) fallback. Second, it orders the caller's prior stores
+	 * before the lock-counter reads: pairing (store-buffering
+	 * pattern) with the smp_mb() in __srcu_read_lock(), any reader
+	 * whose lock increment is not observed by the sums below is
+	 * guaranteed to observe, within its critical section, every
+	 * store the caller made before calling this function.
+	 *
+	 * Summing both epochs means no index flip is needed: a stable
+	 * equality proves there was a moment in this function at which
+	 * no readers existed at all.
+	 */
+	smp_mb();
+
+	if (!srcu_readers_lock_idx(ssp, 0, false, unlocks0))
+		return false;
+	if (!srcu_readers_lock_idx(ssp, 1, false, unlocks1))
+		return false;
+
+	/* Order the caller's subsequent accesses after the proof. */
+	smp_mb();
+	return true;
+}
+EXPORT_SYMBOL_GPL(try_synchronize_srcu);
+
 /**
  * get_state_synchronize_srcu - Provide an end-of-grace-period cookie
  * @ssp: srcu_struct to provide cookie for.
-- 
2.43.0