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 <[email protected]>
---
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 <[email protected]>
S: Maintained
F: drivers/media/rc/ir-rcmm-decoder.c
+RCU PSEUDO-TRANSACTIONS
+M: Mathieu Desnoyers <[email protected]>
+L: [email protected]
+S: Maintained
+F: include/linux/rcu_txn*.h
+F: lib/rcu_txn*
+
RCUTORTURE TEST FRAMEWORK
M: "Paul E. McKenney" <[email protected]>
M: Josh Triplett <[email protected]>
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 <[email protected]>
+ */
+#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 <[email protected]>
+ *
+ * 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 <[email protected]>
+ */
+#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
