[RFC PATCH 01/12] rcu_txn: Add single-writer RCU pseudo-transactions

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

rcu_assign_pointer() publishes one pointer atomically.  An update that
re-points several pointers exposes its intermediate states to RCU
readers: a reader that loads two of them may see the new value of one
and then the old value of the other.  Moving an object between two hash
buckets and editing a doubly-linked list are such updates.

Add RCU pseudo-transactions, which switch a set of RCU-protected
pointers from their old to their new values with a single store, as
observed by readers.  The writer records one {slot, old, new} triple per
pointer, then commits:

 1. Install: each slot is made to point at its record, tagged so that
    readers recognise a proxy.  A proxy resolves through a selector
    shared by the records of the transaction, to its old target.
 2. Commit: one store to the selector makes every proxy resolve to its
    new target.
 3. Settle: each slot is overwritten with its new target, and the
    records are freed after a grace period.

Readers use rcu_txn_dereference() in place of rcu_dereference().  On a
slot that holds no proxy, it adds a test of the tag bits.

Writers of a slot are excluded by the caller, as for any RCU update.
The transaction has no read set, no conflict detection and no abort, and
readers get no snapshot, hence "pseudo".

A transaction of a single record installs no proxy and commits with one
rcu_assign_pointer().  A writer that may write the same slot twice reads
it back with rcu_txn_load() and records with rcu_txn_record_chain(),
which keeps one record per slot.  The lookup is a linear scan of the
records, which rcu_txn_declare_disjoint() turns off.

The records and the selector live in one descriptor, allocated with the
gfp_t given to rcu_txn_init() and freed with kfree_rcu() after a commit
that installed proxies.  A descriptor that installed none, after a
commit of one record or a cancel, owes no grace period: it is freed with
kfree() or, on PREEMPT_RT, with kfree_rcu(): rcu_txn_commit() and
rcu_txn_cancel() may then be called under a raw or a bit spinlock on
every kernel, as a hash table with hlist_bl buckets does.  An allocation
failure is sticky and reported by rcu_txn_commit(), which then publishes
nothing.  Slots are __rcu pointers, handed over as void __rcu ** through
rcu_txn_slot() so that sparse checks the annotation.

The inline paths are in <linux/rcu_txn.h>.  What allocates or frees a
descriptor, and the commit of two records or more, are in lib/rcu_txn.c,
built with the hidden CONFIG_RCU_TXN that users select; the header does
not include <linux/slab.h>.

Add a MAINTAINERS entry for the new files.

Assisted-by: LLM
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 MAINTAINERS             |   7 +
 include/linux/rcu_txn.h | 765 ++++++++++++++++++++++++++++++++++++++++
 lib/Kconfig             |   3 +
 lib/Makefile            |   2 +
 lib/rcu_txn.c           | 105 ++++++
 lib/rcu_txn_internal.h  |  50 +++
 6 files changed, 932 insertions(+)
 create mode 100644 include/linux/rcu_txn.h
 create mode 100644 lib/rcu_txn.c
 create mode 100644 lib/rcu_txn_internal.h

diff --git a/MAINTAINERS b/MAINTAINERS
index f53047aa8d3c..a5dc2eda633f 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -22853,6 +22853,13 @@ M:	Patrick Lerda <patrick9876@free.fr>
 S:	Maintained
 F:	drivers/media/rc/ir-rcmm-decoder.c
 
+RCU PSEUDO-TRANSACTIONS
+M:	Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+L:	rcu@vger.kernel.org
+S:	Maintained
+F:	include/linux/rcu_txn*.h
+F:	lib/rcu_txn*
+
 RCUTORTURE TEST FRAMEWORK
 M:	"Paul E. McKenney" <paulmck@kernel.org>
 M:	Josh Triplett <josh@joshtriplett.org>
diff --git a/include/linux/rcu_txn.h b/include/linux/rcu_txn.h
new file mode 100644
index 000000000000..48e87ea2d90b
--- /dev/null
+++ b/include/linux/rcu_txn.h
@@ -0,0 +1,765 @@
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+/*
+ * Single-writer RCU pseudo-transactions
+ *
+ * Copyright (C) 2026 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ */
+#ifndef _LINUX_RCU_TXN_H
+#define _LINUX_RCU_TXN_H
+
+/*
+ * Single-writer RCU pseudo-transactions switch a set of RCU-protected pointers,
+ * the slots, from their old to their new targets with a single store, as
+ * observed by concurrent RCU readers: at any instant, every slot of the set
+ * resolves to its old target, or every slot to its new one.
+ *
+ * The slots are the edges of the data structure that an update re-points; the
+ * writer records each edge as its slot with the slot's old and new targets.
+ *
+ * Each slot is made to hold a tagged pointer to a record of the transaction, a
+ * proxy, which resolves to the slot's old target while the selector of the
+ * transaction's flip group is 0, and to its new target once it is 1.
+ * rcu_txn_commit() installs the proxies, stores 1 to the selector, then settles
+ * each slot to its new target and frees the records after a grace period.
+ *
+ * The embedding data structure is responsible for:
+ *   - excluding concurrent writers from the slots a transaction commits;
+ *   - choosing the tag that marks a proxy pointer so its readers recognise
+ *     it (a spare low bit, or a reserved type code in an already-tagged
+ *     pointer), and never storing a live value that carries it;
+ *   - routing its readers' slot loads through rcu_txn_resolve(), within an
+ *     RCU read-side critical section.
+ *
+ * Store-release / load-acquire pairs
+ * ----------------------------------
+ * What each of the writer's store-release orders, and against which load:
+ *
+ *   - Install.  The store-release of the tagged proxy into the slot
+ *     (rcu_assign_pointer()) pairs with the reader's rcu_dereference() of
+ *     that slot.  It orders the writer's earlier stores before the reader's
+ *     loads through the proxy: the record's {old, new, group}, the selector's
+ *     initialization to 0, and the new data being published, which the
+ *     embedder builds before the commit.  A reader that finds the proxy thus
+ *     sees the new data built, whatever the selector holds.
+ *
+ *   - Commit.  The store-release of the selector (0 -> 1) pairs with the
+ *     load-acquire of the selector in __rcu_txn_proxy_resolve().  It orders
+ *     every install of the transaction before the flip, so that a reader that
+ *     resolves one proxy to its new target, then loads another slot of the
+ *     transaction, ordered after that resolution, finds that slot's proxy or
+ *     its new target, never its old one.
+ *
+ *   - Settle.  The store-release of the new target into the slot pairs with
+ *     the reader's rcu_dereference() of that slot: the usual RCU publication
+ *     guarantee, for a reader that finds the new target settled.
+ *
+ * A single-record commit installs no proxy: it is the settle store alone.
+ *
+ * Ordering / monotonicity
+ * ------------------------
+ * The selector is written exactly once (0 -> 1) and never back, so a
+ * reader resolving several proxy records over time observes a monotone
+ * old...old,new...new sequence -- never new-then-old.  Embedders can rely
+ * on this together with a fixed read order to avoid a per-traversal
+ * snapshot: a reader that follows a forward edge of a transaction to its new
+ * target, then a back edge of the same transaction from that node, finds the
+ * back edge's new target, never its old one.
+ *
+ * Scope of "never new-then-old":  Monotonicity of the selector is
+ * unconditional.  It is one word, stored once.  What a reader's sequence of
+ * resolutions inherits from it depends on how the reader got from one slot to
+ * the next.  A dependency-chained traversal (each hop's address derived from
+ * the value the previous hop loaded) carries the order with rcu_dereference().
+ * A reader that hops without that chain -- re-reading a pointer it cached
+ * earlier, or walking prev-then-next between two independently-reached slots --
+ * has no such edge: on weakly-ordered hardware its two loads may be reordered,
+ * and it can observe the new selector's effect on the later slot and the old on
+ * the earlier one.  Such a reader owes itself an explicit acquire (or a
+ * dependency).
+ *
+ * Readers and reclaim
+ * -------------------
+ * rcu_txn_commit() reclaims the transaction descriptor with kfree_rcu().  A
+ * reader must therefore load a slot and resolve what it loaded within one RCU
+ * read-side critical section.
+ *
+ * Allocation
+ * ----------
+ * The descriptor is allocated with the gfp_t given to rcu_txn_init(), by
+ * rcu_txn_reserve() or by an rcu_txn_record() that finds the handle full.  A
+ * writer that records under a spinlock either initializes the handle with a
+ * non-sleeping gfp_t, or reserves its record bound before it takes the lock.
+ * Under a raw or a bit spinlock only the reserve will do: on PREEMPT_RT the
+ * allocator cannot be called there.
+ *
+ * rcu_txn_commit() and rcu_txn_cancel() allocate nothing, do not sleep, and
+ * may be called under a raw or a bit spinlock.
+ */
+
+#include <linux/bug.h>
+#include <linux/build_bug.h>
+#include <linux/compiler.h>
+#include <linux/errno.h>
+#include <linux/gfp_types.h>
+#include <linux/rcupdate.h>
+#include <linux/stddef.h>
+#include <linux/string.h>
+#include <linux/types.h>
+
+/*
+ * First capacity of an unreserved handle: with its header, such a descriptor
+ * fits a 256-byte allocation.  A transaction that records more should
+ * rcu_txn_reserve() its bound rather than grow to it.
+ */
+#define RCU_TXN_CAP	4
+
+/*
+ * RCU pseudo-transaction (struct rcu_txn)
+ * =======================================
+ *
+ * A growable transaction over a set of slots.  The handle is a small on-stack
+ * object the embedder declares and initializes with rcu_txn_init().  Nothing
+ * is allocated before the first record() or reserve(), so init cannot fail.
+ *
+ *   init() --> PREPARE --commit() or cancel()--> DONE
+ *                 |                               ^
+ *                 | reserve() or record()         |
+ *                 | cannot allocate               |
+ *                 v                               |
+ *                OOM ---commit() or cancel()------+
+ *
+ * record() appends a record {slot, old, new} to the transaction's descriptor
+ * and installs nothing, so the descriptor may still move as it grows.  The
+ * record set is frozen once commit() installs the proxies.  Records must target
+ * pairwise-distinct slots: see rcu_txn_record().
+ *
+ * A handle ends in commit(), which publishes the record set, or in cancel(),
+ * which drops it.  Either consumes the handle, which must be initialized again
+ * before it is reused.
+ *
+ * OOM is sticky.  Once a reserve() or a record() has failed to allocate, later
+ * ones do nothing and commit() publishes nothing and returns -ENOMEM.  An
+ * embedder may therefore ignore their return values and test only commit()'s.
+ *
+ * Each record carries its own tag: the bits OR'd into the proxy value installed
+ * in its slot, by which the slot's readers recognise a proxy (a reserved type
+ * code, for instance).  It must be within RCU_TXN_TAG_MASK.
+ */
+
+enum rcu_txn_state {
+	RCU_TXN_PREPARE = 0,
+	RCU_TXN_OOM,			/* sticky: commit() returns -ENOMEM */
+	/*
+	 * Terminal: commit() or cancel() consumed the handle.  Using it again
+	 * without initializing it warns.
+	 */
+	RCU_TXN_DONE,
+};
+
+/*
+ * Shared selector for a flip group.  selector == 0 -> records resolve to
+ * old_ptr; selector == 1 -> new_ptr.  Written once (0 -> 1) with a
+ * store-release by __rcu_txn_group_commit(); read with a load-acquire by
+ * __rcu_txn_proxy_resolve().
+ */
+struct rcu_txn_group {
+	unsigned long selector;
+};
+
+/*
+ * Records are aligned on RCU_TXN_RECORD_ALIGN bytes, which leaves the low bits
+ * of a record's address, RCU_TXN_TAG_MASK, free for the tag that marks an
+ * installed proxy.
+ */
+#define RCU_TXN_RECORD_ALIGN	16
+#define RCU_TXN_TAG_MASK	(RCU_TXN_RECORD_ALIGN - 1UL)
+
+struct rcu_txn_record {
+	void *ptr[2];			/* [0] old, [1] new; selector-indexed */
+	struct rcu_txn_group *group;
+	void __rcu **slot;		/* install / settle target */
+	/*
+	 * Tag bits OR'd into the proxy value installed in @slot.  Per record,
+	 * so that slots tagged differently (a 0xF type code, a list's bit 0)
+	 * can share one transaction.
+	 */
+	unsigned long tag;
+} __aligned(RCU_TXN_RECORD_ALIGN);
+
+/*
+ * Transaction descriptor: the single allocation that carries a committed
+ * transaction across its grace period.  It holds the flip group every installed
+ * proxy reads, the rcu_head that defers its reclaim, and the records, which are
+ * the proxies.  The first record() or reserve() allocates it, and it may move
+ * as it grows in PREPARE, no proxy being installed yet.
+ */
+struct rcu_txn_desc {
+	struct rcu_txn_group group;		/* read by installed proxies */
+	struct rcu_head rcu_head;		/* deferred-free handle */
+	unsigned int cap;			/* records it can hold */
+	struct rcu_txn_record records[] __counted_by(cap);
+};
+
+/*
+ * A descriptor's size is then a multiple of a record's alignment, which is
+ * what makes kmalloc() return it aligned that much: see rcu_txn_desc_alloc().
+ */
+static_assert(!(offsetof(struct rcu_txn_desc, records) % RCU_TXN_RECORD_ALIGN));
+static_assert(!(sizeof(struct rcu_txn_record) % RCU_TXN_RECORD_ALIGN));
+
+/*
+ * Transaction handle: a small on-stack object, private to one writer.
+ */
+struct rcu_txn {
+	struct rcu_txn_record *records;	/* @desc's, NULL until allocated */
+	struct rcu_txn_desc *desc;	/* NULL until first allocated */
+	unsigned int nr;
+	unsigned int cap;
+	gfp_t gfp;			/* for the descriptor */
+	enum rcu_txn_state state;
+	bool disjoint;			/* declared slot-disjoint */
+};
+
+/*
+ * Reader side
+ * ===========
+ *
+ * A reader loads a transacted slot with rcu_dereference() and passes the value
+ * to rcu_txn_resolve().  rcu_txn_dereference() does both.
+ */
+
+/**
+ * rcu_txn_is_proxy() - is a slot's value an installed proxy?
+ * @v: value loaded from a transacted slot
+ * @tag: the slot's proxy tag
+ *
+ * No live value an embedder stores in a transacted slot may carry all of
+ * @tag's bits: see rcu_txn_record().
+ *
+ * Return: true if @v carries all of @tag's bits.
+ */
+static inline bool rcu_txn_is_proxy(const void *v, unsigned long tag)
+{
+	return ((unsigned long)v & tag) == tag;
+}
+
+/*
+ * Recover the record's address from a slot value that holds an installed proxy.
+ *
+ * Subtracting the tag is equivalent to masking it off, since
+ * rcu_txn_is_proxy() has shown every tag bit set in @v.  It lets the compiler
+ * fold a constant @tag into the displacement of the loads that follow, where a
+ * mask would be one more operation in the reader's chain of dependent loads.
+ */
+static inline struct rcu_txn_record *__rcu_txn_untag(void *v, unsigned long tag)
+{
+	return (struct rcu_txn_record *)((unsigned long)v - tag);
+}
+
+/*
+ * Resolve a proxy to its current target.
+ *
+ * @proxy must come from an rcu_dereference() of the slot that holds it.  What
+ * orders the loads below is described under "Store-release / load-acquire
+ * pairs" at the top of this file.
+ *
+ * The selector indexes proxy->ptr[] directly, so resolution is a data
+ * dependency rather than a conditional branch.
+ */
+static inline void *__rcu_txn_proxy_resolve(const struct rcu_txn_record *proxy)
+{
+	/*
+	 * Load-acquire (A) pairs with the store-release (B) of
+	 * __rcu_txn_group_commit().
+	 */
+	return proxy->ptr[smp_load_acquire(&proxy->group->selector)];
+}
+
+/**
+ * rcu_txn_resolve() - resolve a value loaded from a transacted slot
+ * @v: value returned by rcu_dereference() on the slot
+ * @tag: the slot's proxy tag
+ *
+ * A plain value is returned as is.  An installed proxy resolves through its
+ * flip group's selector, to the slot's old target until the transaction
+ * commits and to its new target from then on.
+ *
+ * Context: RCU read-side critical section, the one @v was loaded in.
+ * Return: the slot's target.
+ */
+static inline void *rcu_txn_resolve(void *v, unsigned long tag)
+{
+	if (likely(!rcu_txn_is_proxy(v, tag)))
+		return v;
+	return __rcu_txn_proxy_resolve(__rcu_txn_untag(v, tag));
+}
+
+/**
+ * rcu_txn_dereference_check() - load and resolve a transacted pointer
+ * @p: the RCU-protected pointer, a transacted slot
+ * @tag: the slot's proxy tag
+ * @c: condition under which the load is also legal, as for
+ *     rcu_dereference_check()
+ *
+ * Return: the slot's target, with the type @p points to.
+ */
+#define rcu_txn_dereference_check(p, tag, c)				\
+({									\
+	void *__rcu_txn_v = rcu_dereference_check(p, c);		\
+									\
+	(typeof(*(p)) __force __kernel *)rcu_txn_resolve(__rcu_txn_v, tag); \
+})
+
+/**
+ * rcu_txn_dereference() - load and resolve a transacted pointer
+ * @p: the RCU-protected pointer, a transacted slot
+ * @tag: the slot's proxy tag
+ *
+ * rcu_dereference() followed by rcu_txn_resolve().  A writer that excludes
+ * the slot's other writers never finds a proxy there outside of its own
+ * rcu_txn_commit(), and may use rcu_dereference_protected() as is.
+ *
+ * Context: RCU read-side critical section.
+ * Return: the slot's target, with the type @p points to.
+ */
+#define rcu_txn_dereference(p, tag)	rcu_txn_dereference_check(p, tag, 0)
+
+/**
+ * rcu_txn_slot() - the engine's view of an RCU-protected pointer's address
+ * @pp: address of an __rcu pointer, of any type
+ *
+ * The engine takes every slot as a ``void __rcu **``.  This converts the
+ * address of an embedder's typed pointer, after sparse has checked that the
+ * pointer is __rcu.
+ *
+ * Return: @pp as a ``void __rcu **``.
+ */
+#define rcu_txn_slot(pp)						\
+({									\
+	typeof(pp) __rcu_txn_pp = (pp);					\
+									\
+	rcu_check_sparse(*__rcu_txn_pp, __rcu);				\
+	(void __rcu **)__rcu_txn_pp;					\
+})
+
+/*
+ * Record primitives
+ * =================
+ *
+ * What the inline paths need: record(), and the commit of a single record.  A
+ * record is installed and a group committed in lib/rcu_txn.c: see
+ * __rcu_txn_commit_desc().
+ */
+
+/*
+ * Set a record's {old, new, slot, tag}; its group is bound at install.
+ */
+static inline void __rcu_txn_record_set(struct rcu_txn_record *r,
+					void __rcu **slot, void *old_ptr,
+					void *new_ptr, unsigned long tag)
+{
+	r->ptr[0] = old_ptr;
+	r->ptr[1] = new_ptr;
+	r->slot = slot;
+	r->tag = tag;
+}
+
+/*
+ * Settle record @r's slot: store its new target there, over the proxy.  For a
+ * transaction of one record, which installs no proxy, this store is the whole
+ * commit.
+ */
+static inline void __rcu_txn_record_settle(struct rcu_txn_record *r)
+{
+	/* Store-release of slot pairs with rcu_dereference(). */
+	rcu_assign_pointer(*r->slot, r->ptr[1]);
+}
+
+/*
+ * Writer side
+ * ===========
+ *
+ * The handle's contract is stated under "RCU pseudo-transaction" above.
+ */
+
+/**
+ * rcu_txn_init() - initialize a transaction handle
+ * @t: the handle
+ * @gfp: allocation flags for the transaction's descriptor
+ *
+ * Allocates nothing, so it cannot fail.  @gfp is used by rcu_txn_reserve()
+ * and by an rcu_txn_record() that finds the handle full.
+ */
+static inline void rcu_txn_init(struct rcu_txn *t, gfp_t gfp)
+{
+	memset(t, 0, sizeof(*t));
+	t->state = RCU_TXN_PREPARE;
+	t->gfp = gfp;
+}
+
+/*
+ * Move the handle's records to a new descriptor holding at least @cap of them.
+ * PREPARE only: no proxy is installed yet, so the records may move.  Returns
+ * false if it cannot allocate, leaving the handle in the RCU_TXN_OOM state.
+ */
+bool __rcu_txn_resize(struct rcu_txn *t, unsigned int cap);
+
+/**
+ * rcu_txn_reserve() - give the handle a descriptor for a number of records
+ * @t: the handle
+ * @cap: number of records the descriptor must hold
+ *
+ * Optional: record() grows the descriptor on demand.  An embedder whose record
+ * count is bounded can reserve that bound up front, where a failure is easy to
+ * handle and where it may sleep; every later record() then appends without
+ * allocating and cannot fail.
+ *
+ * RCU_TXN_CAP is not a floor: it is only where an unreserved handle starts.
+ * Reserving less than the transaction goes on to record is correct, and costs
+ * the grow that a reserve exists to avoid.
+ *
+ * Call after init and before commit.  A handle that already buffers records
+ * grows to fit @cap.
+ *
+ * Context: May sleep if the handle's gfp_t allows it.
+ * Return: true, or false if it cannot allocate, which is sticky.
+ */
+static inline bool rcu_txn_reserve(struct rcu_txn *t, unsigned int cap)
+{
+	if (unlikely(t->state != RCU_TXN_PREPARE)) {
+		/* OOM is sticky.  DONE: commit() consumed the handle. */
+		WARN_ON_ONCE(t->state != RCU_TXN_OOM);
+		return false;
+	}
+	if (t->records && cap <= t->cap)
+		return true;		/* already large enough */
+	return __rcu_txn_resize(t, cap);
+}
+
+/* Free a descriptor that installed no proxy: see lib/rcu_txn.c. */
+void __rcu_txn_free_desc(struct rcu_txn_desc *desc);
+
+/*
+ * Release the handle's descriptor, if it has one.  No proxy of it was
+ * installed, so no grace period is owed.
+ */
+static inline void __rcu_txn_release_desc(struct rcu_txn *t)
+{
+	if (t->desc)
+		__rcu_txn_free_desc(t->desc);
+}
+
+/*
+ * Mark the handle consumed, by commit() or by cancel(): it no longer owns a
+ * descriptor, and must be initialized again before it is reused.
+ */
+static inline void __rcu_txn_done(struct rcu_txn *t)
+{
+	t->desc = NULL;
+	t->records = NULL;
+	t->nr = 0;
+	t->state = RCU_TXN_DONE;
+}
+
+/*
+ * Scan this transaction's records for @slot, or NULL.  Linear, so O(nr) per
+ * call and O(nr^2) to build a write set.  The returned pointer is invalidated
+ * by the next record() (a grow may move the records), so use it before
+ * recording again.
+ */
+static inline struct rcu_txn_record *__rcu_txn_scan(const struct rcu_txn *t,
+						    void __rcu **slot)
+{
+	unsigned int i;
+
+	for (i = 0; i < t->nr; i++)
+		if (t->records[i].slot == slot)
+			return &t->records[i];
+	return NULL;
+}
+
+/*
+ * Grow a full handle: double its capacity, or give an unreserved handle its
+ * first RCU_TXN_CAP records.  Returns false if it cannot allocate.
+ *
+ * Out of line: with this path in its body, the compiler does not inline
+ * rcu_txn_record(), and every recorded edge pays a call for an append that is
+ * five stores.
+ */
+bool __rcu_txn_grow(struct rcu_txn *t);
+
+/**
+ * rcu_txn_record() - record one edge of a transaction
+ * @t: the handle
+ * @slot: the slot to switch
+ * @old_ptr: the slot's current target
+ * @new_ptr: the target the transaction gives it
+ * @tag: the slot's proxy tag
+ *
+ * Record that the transaction switches @slot from @old_ptr to @new_ptr.  @tag
+ * is OR'd into the proxy value installed in @slot, so that the slot's readers
+ * recognise the proxy and route its resolution (a reserved type code, or a
+ * list's bit 0).  Neither @old_ptr nor @new_ptr may carry all of @tag's bits:
+ * after settle the slot holds @new_ptr directly, and a reader would resolve it
+ * as a proxy.
+ *
+ * PREPARE only: the record set is frozen once proxies are installed, so this
+ * must run before commit().  Nothing is installed here.
+ *
+ * Records must target pairwise-distinct slots.  record() appends without
+ * looking for an earlier record of the same slot; recording a slot twice
+ * installs two proxies on it and settles both in record order, so the earlier
+ * edit is lost.  Use rcu_txn_record_chain() when the same slot may be written
+ * twice.
+ *
+ * Context: The caller excludes other writers of @slot.  May sleep if the
+ * handle is full and its gfp_t allows it.
+ * Return: true, or false if it cannot allocate, which is sticky.
+ */
+static inline bool rcu_txn_record(struct rcu_txn *t, void __rcu **slot,
+				  void *old_ptr, void *new_ptr,
+				  unsigned long tag)
+{
+	struct rcu_txn_record *r;
+
+	if (unlikely(t->state != RCU_TXN_PREPARE)) {
+		/* OOM is sticky.  DONE: commit() consumed the handle. */
+		WARN_ON_ONCE(t->state != RCU_TXN_OOM);
+		return false;
+	}
+	if (unlikely(t->nr == t->cap) && !__rcu_txn_grow(t))
+		return false;			/* OOM, now sticky */
+	r = &t->records[t->nr++];
+	__rcu_txn_record_set(r, slot, old_ptr, new_ptr, tag);
+	return true;
+}
+
+/*
+ * Read-your-own-writes pair (rcu_txn_load() / rcu_txn_record_chain())
+ * ====================================================================
+ *
+ * rcu_txn_record() requires pairwise-distinct slots.  This suits an embedder
+ * whose slots are distinct by construction, such as a list operation recording
+ * two edges: it pays no scan per store.
+ *
+ * An embedder whose write sites can coincide needs the opposite.  Deleting two
+ * adjacent nodes of a list in one transaction writes the predecessor's next
+ * slot twice, first to skip the one node and then the other, and the second
+ * store must fuse with the pending one rather than duplicate it.  This pair
+ * does that:
+ *
+ *     old = rcu_txn_load(t, slot, TAG);
+ *     rcu_txn_record_chain(t, slot, old, f(old), TAG);
+ *
+ * The transaction then keeps at most one record per slot.  There is no read
+ * set: a load records nothing and is not validated, since a single writer has
+ * nothing to validate against.
+ *
+ * Scope.  The pair fuses same-slot stores.  It does not make every composition
+ * sound: an embedder whose new value is a neighbour's pointer (a list) can
+ * still build its write set from stale reads of distinct slots, unless its
+ * traversal also reads through rcu_txn_load().
+ *
+ * After an OOM the pair no longer reads its own writes: the failed record()
+ * appended nothing, so a later load() of that slot returns the committed value.
+ * commit() then publishes nothing, but an embedder that changes state outside
+ * the transaction as it records must not derive it from such a load.
+ */
+
+/**
+ * rcu_txn_declare_disjoint() - declare the write set slot-disjoint
+ * @t: the handle
+ *
+ * Declare that no slot is recorded twice.  rcu_txn_load() then returns the
+ * committed value without looking for a pending one, and
+ * rcu_txn_record_chain() appends without looking for an earlier record.
+ *
+ * Distinctness is a property of the slot address, not of the nodes edited: two
+ * operations on distinct nodes, such as the deletion of two adjacent nodes of
+ * a list, may write the same slot.
+ *
+ * This skips the lookup among the records so far on every load and record, a
+ * scan: a small saving from the second record on.
+ *
+ * Recording a slot twice on such a handle breaks the rule of rcu_txn_record(),
+ * with the consequence stated there.
+ *
+ * Call after init and before the first record().  On a handle whose reserve()
+ * failed it does nothing: the failure is sticky, and commit() reports it.
+ */
+static inline void rcu_txn_declare_disjoint(struct rcu_txn *t)
+{
+	if (t->state == RCU_TXN_OOM)
+		return;
+	/* Later, the records so far would no longer be looked up. */
+	if (WARN_ON_ONCE(t->state != RCU_TXN_PREPARE || t->nr))
+		return;
+	t->disjoint = true;
+}
+
+/**
+ * rcu_txn_load() - load a slot as the transaction will leave it
+ * @t: the handle
+ * @slot: the slot
+ * @tag: the slot's proxy tag
+ *
+ * On a handle declared disjoint, this returns the committed value without
+ * looking for a pending one.
+ *
+ * Context: The caller excludes other writers of @slot.
+ * Return: the pending new value of the transaction's record for @slot if it
+ * has one, else the slot's current value.
+ */
+static inline void *rcu_txn_load(struct rcu_txn *t, void __rcu **slot,
+				 unsigned long tag)
+{
+	struct rcu_txn_record *r;
+	void *v;
+
+	/* A consumed handle has no record left: it reads committed values. */
+	WARN_ON_ONCE(t->state == RCU_TXN_DONE);
+	if (!t->disjoint) {
+		r = __rcu_txn_scan(t, slot);
+		if (r)
+			return r->ptr[1];	/* our own pending write */
+	}
+	v = rcu_dereference_protected(*slot, 1);
+	return v;
+}
+
+/*
+ * The read-your-own-writes half of rcu_txn_record_chain(): chain onto this
+ * transaction's record for @slot, or append one if it has none.
+ */
+static inline bool __rcu_txn_chain(struct rcu_txn *t, void __rcu **slot,
+				   void *old_ptr, void *new_ptr,
+				   unsigned long tag)
+{
+	struct rcu_txn_record *r;
+
+	r = __rcu_txn_scan(t, slot);
+	if (!r)
+		return rcu_txn_record(t, slot, old_ptr, new_ptr, tag);
+	r->ptr[1] = new_ptr;		/* committed old preserved */
+	return true;
+}
+
+/**
+ * rcu_txn_record_chain() - record an edge on a slot that may repeat
+ * @t: the handle
+ * @slot: the slot to switch
+ * @old_ptr: what rcu_txn_load() returned for @slot
+ * @new_ptr: the target the transaction gives it
+ * @tag: the slot's proxy tag
+ *
+ * Record that the transaction switches @slot from @old_ptr to @new_ptr,
+ * chaining onto this transaction's record for @slot if it has one: that record
+ * keeps its committed old and takes @new_ptr.  Otherwise append, as
+ * rcu_txn_record() does.  See the pair's contract above.
+ *
+ * On the chain path @old_ptr is the record's pending value, and a different
+ * @old_ptr means the caller computed @new_ptr from a stale read.
+ *
+ * Context: As rcu_txn_record().
+ * Return: As rcu_txn_record().
+ */
+static inline bool rcu_txn_record_chain(struct rcu_txn *t, void __rcu **slot,
+					void *old_ptr, void *new_ptr,
+					unsigned long tag)
+{
+	if (unlikely(t->state != RCU_TXN_PREPARE)) {
+		/* OOM is sticky.  DONE: commit() consumed the handle. */
+		WARN_ON_ONCE(t->state != RCU_TXN_OOM);
+		return false;
+	}
+	if (t->disjoint) {		/* no slot repeats: skip the lookup */
+		return rcu_txn_record(t, slot, old_ptr, new_ptr, tag);
+	}
+	return __rcu_txn_chain(t, slot, old_ptr, new_ptr, tag);
+}
+
+/**
+ * rcu_txn_cancel() - drop a transaction instead of committing it
+ * @t: the handle
+ *
+ * No proxy was installed, so nothing is published, and no grace period is
+ * owed: the descriptor is freed with kfree(), or with kfree_rcu() on
+ * PREEMPT_RT (see lib/rcu_txn.c).  Like commit(), it consumes the handle, which
+ * must be initialized again before it is reused.
+ *
+ * A handle ends in commit() or in cancel(): one that is merely dropped leaks
+ * its descriptor.  A handle in the OOM state may be cancelled as well.
+ *
+ * Only the records are dropped: what an embedder changed outside the
+ * transaction as it recorded is not rolled back.
+ */
+static inline void rcu_txn_cancel(struct rcu_txn *t)
+{
+	/* A consumed handle must be initialized again before reuse. */
+	if (WARN_ON_ONCE(t->state == RCU_TXN_DONE))
+		return;
+	__rcu_txn_release_desc(t);	/* no proxy: free now */
+	__rcu_txn_done(t);
+}
+
+/*
+ * Install, flip, settle and retire the first @nr records of @desc: the commit
+ * of a transaction that installs proxies, which takes two records or more.
+ */
+void __rcu_txn_commit_desc(struct rcu_txn_desc *desc, unsigned int nr);
+
+/**
+ * rcu_txn_commit() - commit a transaction
+ * @t: the handle
+ *
+ * Install every record's proxy, flip the group so that every proxy resolves
+ * to new atomically, then settle each slot to its new value.  commit() owns
+ * reclaim and consumes the handle, which must be initialized again before it
+ * is reused.
+ *
+ * With one record, a lone store-release to the slot is already an atomic
+ * commit.  No proxy is installed, so no reader can hold one: no grace period is
+ * owed, and the descriptor is freed as by rcu_txn_cancel().  The common
+ * one-pointer publish thus needs no install and no settle.  An empty
+ * transaction publishes nothing.
+ *
+ * With two or more records, the descriptor's reclaim is deferred with
+ * kfree_rcu(): a reader may still hold a proxy.
+ *
+ * Context: The caller excludes other writers of the recorded slots.  Does not
+ * sleep, and may be called under a raw or a bit spinlock.
+ * Return: 0, or -ENOMEM if a reserve() or a record() of this transaction
+ * failed, in which case nothing is published.  -EINVAL, with a warning,
+ * for a handle that was already consumed.
+ */
+static inline int rcu_txn_commit(struct rcu_txn *t)
+{
+	const unsigned int nr = t->nr;
+
+	/* A consumed handle must be initialized again before reuse. */
+	if (WARN_ON_ONCE(t->state == RCU_TXN_DONE))
+		return -EINVAL;
+	if (unlikely(t->state == RCU_TXN_OOM)) {
+		rcu_txn_cancel(t);
+		return -ENOMEM;
+	}
+	if (nr <= 1) {
+		if (nr == 1) {
+			struct rcu_txn_record *r = &t->records[0];
+
+			/* One record: its settle store is the whole commit. */
+			__rcu_txn_record_settle(r);
+		}
+		__rcu_txn_release_desc(t);	/* no proxy: free now */
+	} else {
+		/*
+		 * The proxies live in the descriptor, which is reclaimed after
+		 * a grace period.
+		 */
+		__rcu_txn_commit_desc(t->desc, nr);
+	}
+	__rcu_txn_done(t);
+	return 0;
+}
+
+#endif /* _LINUX_RCU_TXN_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 4e6b34c3346d..c03dff4b4ed6 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -366,6 +366,9 @@ config ASSOCIATIVE_ARRAY
 config CLOSURES
 	bool
 
+config RCU_TXN
+	bool
+
 config HAS_IOMEM
 	bool
 	depends on !NO_IOMEM
diff --git a/lib/Makefile b/lib/Makefile
index dfab958327c5..ef01dc3182e5 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -223,6 +223,8 @@ obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o
 
 obj-$(CONFIG_CLOSURES) += closure.o
 
+obj-$(CONFIG_RCU_TXN) += rcu_txn.o
+
 obj-$(CONFIG_DQL) += dynamic_queue_limits.o
 
 obj-$(CONFIG_GLOB) += glob.o
diff --git a/lib/rcu_txn.c b/lib/rcu_txn.c
new file mode 100644
index 000000000000..232ad715468a
--- /dev/null
+++ b/lib/rcu_txn.c
@@ -0,0 +1,105 @@
+// SPDX-License-Identifier: LGPL-2.1-or-later
+/*
+ * Single-writer RCU pseudo-transactions: the out-of-line paths
+ *
+ * Copyright (C) 2026 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ *
+ * The engine is inline in <linux/rcu_txn.h>.  What lives here is what allocates
+ * a transaction's descriptor, and the commit that installs proxies.
+ */
+
+#include <linux/export.h>
+#include <linux/overflow.h>
+#include <linux/rcu_txn.h>
+#include <linux/rcupdate.h>
+#include <linux/slab.h>
+#include <linux/string.h>
+
+#include "rcu_txn_internal.h"
+
+/*
+ * Allocate a transaction descriptor for at least @cap records, with its flip
+ * group initialized.  Its capacity is what the allocation holds, which may be
+ * more.  Returns NULL if it cannot allocate.
+ *
+ * The records need RCU_TXN_RECORD_ALIGN.  kmalloc() aligns an object on the
+ * largest power of two that divides its size, and the size of a descriptor is a
+ * multiple of that alignment, as is every size kmalloc_size_roundup() returns
+ * for it.
+ */
+static struct rcu_txn_desc *rcu_txn_desc_alloc(unsigned int cap, gfp_t gfp)
+{
+	struct rcu_txn_desc *desc;
+	size_t size;
+
+	size = kmalloc_size_roundup(struct_size(desc, records, cap));
+	desc = kmalloc(size, gfp);
+	if (!desc)
+		return NULL;
+	__rcu_txn_group_init(&desc->group);
+	desc->cap = (size - sizeof(*desc)) / sizeof(desc->records[0]);
+	return desc;
+}
+
+/*
+ * Free a descriptor that installed no proxy, which owes no grace period.
+ * commit() and cancel() may run under a raw or a bit spinlock, where
+ * PREEMPT_RT does not allow kfree().  It does allow kfree_rcu().
+ */
+void __rcu_txn_free_desc(struct rcu_txn_desc *desc)
+{
+	if (IS_ENABLED(CONFIG_PREEMPT_RT))
+		kfree_rcu(desc, rcu_head);
+	else
+		kfree(desc);
+}
+EXPORT_SYMBOL_GPL(__rcu_txn_free_desc);
+
+/* See <linux/rcu_txn.h>. */
+bool __rcu_txn_resize(struct rcu_txn *t, unsigned int cap)
+{
+	struct rcu_txn_desc *desc;
+
+	desc = rcu_txn_desc_alloc(cap, t->gfp);
+	if (!desc)
+		goto fail;
+	if (t->nr)		/* @records is NULL until first allocated */
+		memcpy(desc->records, t->records,
+		       (size_t)t->nr * sizeof(*desc->records));
+	kfree(t->desc);		/* NULL if it had none */
+	t->desc = desc;
+	t->records = desc->records;
+	t->cap = desc->cap;
+	return true;
+
+fail:
+	t->state = RCU_TXN_OOM;	/* sticky */
+	return false;
+}
+EXPORT_SYMBOL_GPL(__rcu_txn_resize);
+
+/* See <linux/rcu_txn.h>. */
+bool __rcu_txn_grow(struct rcu_txn *t)
+{
+	return __rcu_txn_resize(t, t->cap ? t->cap * 2 : RCU_TXN_CAP);
+}
+EXPORT_SYMBOL_GPL(__rcu_txn_grow);
+
+/* See <linux/rcu_txn.h>. */
+void __rcu_txn_commit_desc(struct rcu_txn_desc *desc, unsigned int nr)
+{
+	struct rcu_txn_record *records = desc->records;
+	unsigned int i;
+
+	/* Install: readers still resolve to old, the selector being 0. */
+	for (i = 0; i < nr; i++)
+		__rcu_txn_record_install(&desc->group, &records[i]);
+	/* Flip: every proxy resolves to new. */
+	__rcu_txn_group_commit(&desc->group);
+	/* Settle. */
+	for (i = 0; i < nr; i++)
+		__rcu_txn_record_settle(&records[i]);
+	/* A reader may still hold a proxy, which lives in the descriptor. */
+	kfree_rcu(desc, rcu_head);
+}
+EXPORT_SYMBOL_GPL(__rcu_txn_commit_desc);
diff --git a/lib/rcu_txn_internal.h b/lib/rcu_txn_internal.h
new file mode 100644
index 000000000000..7e79a48697a8
--- /dev/null
+++ b/lib/rcu_txn_internal.h
@@ -0,0 +1,50 @@
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+/*
+ * Single-writer RCU pseudo-transactions: the steps of a commit
+ *
+ * Copyright (C) 2026 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ */
+#ifndef _LIB_RCU_TXN_INTERNAL_H
+#define _LIB_RCU_TXN_INTERNAL_H
+
+/*
+ * The steps of a commit that installs proxies: see __rcu_txn_commit_desc() in
+ * rcu_txn.c.  The KUnit tests include this as well, to stage a transaction
+ * between two steps.
+ */
+
+#include <linux/rcu_txn.h>
+
+static inline void __rcu_txn_group_init(struct rcu_txn_group *group)
+{
+	group->selector = 0;
+}
+
+/*
+ * Commit the flip group: switch every record in the transaction from old to new
+ * with a single store-release.  Must be called once every record is installed:
+ * the store-release orders the installs before the flip.
+ */
+static inline void __rcu_txn_group_commit(struct rcu_txn_group *group)
+{
+	/*
+	 * Store-release (B) pairs with the load-acquire (A) of
+	 * __rcu_txn_proxy_resolve().
+	 */
+	smp_store_release(&group->selector, 1);
+}
+
+/*
+ * Install record @r's tagged proxy into its slot, bound to flip group @group.
+ * Readers resolve it to old until the group commits.  The installed value is
+ * @r's address OR'd with the record's tag.
+ */
+static inline void __rcu_txn_record_install(struct rcu_txn_group *group,
+					    struct rcu_txn_record *r)
+{
+	r->group = group;
+	/* Store-release of slot pairs with rcu_dereference(). */
+	rcu_assign_pointer(*r->slot, (void *)((unsigned long)r | r->tag));
+}
+
+#endif /* _LIB_RCU_TXN_INTERNAL_H */
-- 
2.47.3