[RFC PATCH 07/12] Documentation/RCU: Describe RCU pseudo-transactions

[Mathieu Desnoyers]

Add a page on the RCU pseudo-transactions to the RCU handbook: when they
apply and what they cost, how a commit proceeds, what readers and
writers call, how a transaction allocates, and the two data structures
built on them.  It ends with the API reference extracted from the
headers.  The overview at the top of <linux/rcu_txn.h> points to it.

Assisted-by: LLM
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
---
 Documentation/RCU/index.rst   |   1 +
 Documentation/RCU/rcu_txn.rst | 230 ++++++++++++++++++++++++++++++++++
 MAINTAINERS                   |   1 +
 include/linux/rcu_txn.h       |   2 +
 4 files changed, 234 insertions(+)
 create mode 100644 Documentation/RCU/rcu_txn.rst

diff --git a/Documentation/RCU/index.rst b/Documentation/RCU/index.rst
index 035871687ee2..4bca16c8573b 100644
--- a/Documentation/RCU/index.rst
+++ b/Documentation/RCU/index.rst
@@ -18,6 +18,7 @@ RCU Handbook
    rcu
    rculist_nulls
    rcuref
+   rcu_txn
    torture
    stallwarn
    listRCU
diff --git a/Documentation/RCU/rcu_txn.rst b/Documentation/RCU/rcu_txn.rst
new file mode 100644
index 000000000000..6e48306ebc19
--- /dev/null
+++ b/Documentation/RCU/rcu_txn.rst
@@ -0,0 +1,230 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+=====================================
+Single-writer RCU pseudo-transactions
+=====================================
+
+An RCU pseudo-transaction switches a *set* of RCU-protected pointers from
+their old values to their new values with a single store, as observed by
+concurrent RCU readers: at any instant, every pointer of the set reads old, or
+every pointer reads new.  A reader that follows several of them, each load
+depending on the previous one, sees old values, then new ones, and never an
+old value after a new one.
+
+The implementation is in ``include/linux/rcu_txn.h`` and ``lib/rcu_txn.c``.
+Code that uses it selects ``CONFIG_RCU_TXN``.
+
+When to use it
+==============
+
+``rcu_assign_pointer()`` publishes one pointer atomically.  An update that
+re-points several pointers one at a time exposes its intermediate states: a
+reader that loads two of them may get the new value of one and then the old
+value of the other.  Moving an object between two hash buckets is such an
+update, and so is every insertion into or removal from a doubly-linked list.
+
+A pseudo-transaction removes the intermediate states.  It does not replace the
+update-side lock: the writers of a slot are excluded by the caller, and the
+transaction neither detects nor resolves conflicts between them.  It is
+"pseudo" in that sense: there is no read set and no abort, and readers get no
+snapshot.
+
+A pseudo-transaction is not free, on the update side above all.  The writer
+allocates a descriptor for each transaction, with the ``gfp_t`` given to
+``rcu_txn_init()``, and a transaction that switches two pointers or more frees
+it with ``kfree_rcu()``, a grace period after its commit, as readers may still
+be reading it: an allocation, which can fail, and a deferred free for every
+update, where ``rcu_assign_pointer()`` needs neither.  The reader pays a test of
+the low bits of every pointer it loads, which is nearly free: only while a
+commit is in flight on that pointer does the reader also read the descriptor,
+with three more loads, one of them an acquire.
+
+How it works
+============
+
+The pointers a transaction switches are called *slots*: they are the *edges* of
+the data structure that the update re-points.  The writer builds a *record* per
+slot, holding the slot's old and new targets, and commits in three steps:
+
+1. *Install.*  Each slot is made to point at its record, with tag bits set that
+   mark the value as a *proxy* rather than a target.  A reader that finds a
+   proxy resolves it through the record, which still answers with the old
+   target.
+
+2. *Commit.*  The records of a transaction share one word, the *selector* of
+   their *flip group*.  The writer stores 1 to it.  From then on every proxy of
+   the transaction resolves to its new target.
+
+3. *Settle.*  Each slot is overwritten with its new target, and the records
+   are freed after a grace period.
+
+The selector is written once, from 0 to 1, so a reader that resolves several
+slots of a transaction over time sees old targets, then new targets, and never
+an old target after a new one, provided that each of its loads depends on the
+previous one.  The header describes the memory ordering in detail.
+
+A transaction of a single record installs no proxy: its commit is one
+``rcu_assign_pointer()``.
+
+Tags
+====
+
+The embedder chooses the tag that marks a proxy in its slots: typically bit 0,
+or a reserved value of a type code that its pointers already carry.  The tag
+must be within ``RCU_TXN_TAG_MASK``, the low bits that the alignment of a
+record leaves clear, and no value that the embedder stores in a slot may carry
+all of the tag's bits.
+
+Readers
+=======
+
+A reader loads a slot with ``rcu_txn_dereference()`` instead of
+``rcu_dereference()``::
+
+	rcu_read_lock();
+	child = rcu_txn_dereference(node->left, FOO_TAG);
+	if (child)
+		do_something_with(child);
+	rcu_read_unlock();
+
+``rcu_txn_dereference()`` is ``rcu_dereference()`` followed by
+``rcu_txn_resolve()``.  A reader that already has the loaded value, for
+instance because it tests other bits of it, calls ``rcu_txn_resolve()``
+itself.
+
+The load and the resolution must happen in one RCU read-side critical section:
+the record a proxy points at is freed with ``kfree_rcu()``.
+
+Writers
+=======
+
+The writer declares a handle on its stack, records the edges of the update and
+commits them::
+
+	struct rcu_txn txn;
+	struct foo *child;
+	int err;
+
+	rcu_txn_init(&txn, GFP_KERNEL);
+	rcu_txn_reserve(&txn, 2);
+
+	spin_lock(&foo_lock);
+	child = rcu_dereference_protected(a->left, lockdep_is_held(&foo_lock));
+	rcu_txn_record(&txn, rcu_txn_slot(&a->left), child, NULL, FOO_TAG);
+	rcu_txn_record(&txn, rcu_txn_slot(&b->right), NULL, child, FOO_TAG);
+	err = rcu_txn_commit(&txn);
+	spin_unlock(&foo_lock);
+
+Here ``child`` moves from ``a->left`` to an empty ``b->right``: at any instant
+it is in exactly one of the two places.
+
+Slots are ``__rcu`` pointers.  ``rcu_txn_slot()`` converts the address of one,
+of any type, to the ``void __rcu **`` the engine takes, and lets sparse check
+the annotation.
+
+A handle ends in ``rcu_txn_commit()`` or in ``rcu_txn_cancel()``.  Either
+consumes it, and it must be initialized again before it is reused.
+
+Allocation
+----------
+
+A transaction allocates a descriptor, with the ``gfp_t`` given to
+``rcu_txn_init()``.  ``rcu_txn_reserve()`` allocates it for a given number of
+records; otherwise the first ``rcu_txn_record()`` does, even for a single
+record, and a later one may grow it.
+
+A failed allocation is sticky: later records do nothing, and
+``rcu_txn_commit()`` publishes nothing and returns ``-ENOMEM``.  A writer may
+therefore ignore the return values of ``rcu_txn_reserve()`` and
+``rcu_txn_record()`` and check that of ``rcu_txn_commit()`` only, as in the
+example above.
+
+A writer that records under a spinlock reserves its record bound before it
+takes the lock, as above, or initializes the handle with a non-sleeping
+``gfp_t``.  Under a raw or a bit spinlock only the reserve will do, since
+``PREEMPT_RT`` does not allow the allocator there.  ``rcu_txn_commit()`` and
+``rcu_txn_cancel()`` allocate nothing, do not sleep, and may be called under
+such a lock.
+
+An update that re-points a single slot needs no transaction.  Every
+transaction settles its slots before its commit returns, and the writers of the
+slot are excluded, so the slot holds no proxy: ``rcu_assign_pointer()``
+publishes the update, as the ``_rcu`` operations of ``rcu_txn_hlist`` do.
+
+Writing a slot twice
+--------------------
+
+``rcu_txn_record()`` requires the records of a transaction to target distinct
+slots.  A writer that may write the same slot twice in one transaction reads
+the slot with ``rcu_txn_load()``, which returns the transaction's pending value
+for it, and records with ``rcu_txn_record_chain()``, which updates the record
+the slot already has::
+
+	old = rcu_txn_load(&txn, slot, FOO_TAG);
+	rcu_txn_record_chain(&txn, slot, old, new, FOO_TAG);
+
+This is what allows several operations on one data structure to be composed in
+one transaction.  The lookup among the transaction's records is a linear scan,
+behind a Bloom filter once the transaction holds enough of them.
+``rcu_txn_declare_disjoint()`` turns the lookup off for a transaction whose
+slots are known to be distinct.
+
+Data structures
+===============
+
+Two data structures are built on the engine.  Each provides ``_prepare``
+operations, which record into a transaction owned by the caller, and ``_rcu``
+operations, which carry out a single operation by themselves.
+Readers walk them with ``_rcu`` iterators.  A writer that excludes the others
+walks them with the same iterators outside of an RCU read-side critical
+section, if it passes them a lockdep condition for that exclusion, such as
+``lockdep_is_held()`` of its lock, as with ``list_for_each_entry_rcu()``.
+
+``include/linux/rcu_txn_hlist.h``
+	A list with a single-pointer head, like ``hlist``.  Its ``_prepare``
+	operations compose: several nodes can be added to or removed from one
+	or several lists atomically.  An ``_rcu`` operation publishes its
+	update with one ``rcu_assign_pointer()`` and allocates nothing.
+
+``include/linux/rcu_txn_list.h``
+	A circular doubly-linked list whose forward and backward chains are
+	mutually coherent at every instant, which allows readers to walk it in
+	both directions.  An insertion or a removal switches a forward and a
+	backward edge, and a move six, the moved node's own included: each
+	allocates a descriptor.
+
+Debugging
+=========
+
+``CONFIG_DEBUG_RCU_TXN`` enables the checks that cost more than a test of the
+handle's state.  It validates the tags, reports a slot recorded twice, and
+validates the single-writer contract: it warns when a handle is driven by a
+task other than the one that initialized it, and when a slot that a transaction
+records, installs to or settles was changed by another writer in the meantime.
+A task that takes over a handle which another got ready, with nothing recorded
+yet, calls ``rcu_txn_adopt()`` first, which makes it the task the check
+expects.
+
+Misuse of a handle, such as recording into one that was already committed,
+warns in every build.
+
+Testing
+=======
+
+``CONFIG_RCU_TXN_KUNIT_TEST`` builds the KUnit suite ``rcu_txn``, which covers
+the engine, both data structures and the debug checks::
+
+	./tools/testing/kunit/kunit.py run --arch=x86_64 \
+		--kconfig_add CONFIG_RCU_TXN_KUNIT_TEST=y \
+		--kconfig_add CONFIG_DEBUG_KERNEL=y \
+		--kconfig_add CONFIG_DEBUG_RCU_TXN=y \
+		'rcu_txn*'
+
+API
+===
+
+.. kernel-doc:: include/linux/rcu_txn.h
+
+.. kernel-doc:: include/linux/rcu_txn_hlist.h
+
+.. kernel-doc:: include/linux/rcu_txn_list.h
diff --git a/MAINTAINERS b/MAINTAINERS
index 5126f4ece4e7..f34040369eb4 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -22857,6 +22857,7 @@ RCU PSEUDO-TRANSACTIONS
 M:	Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
 L:	rcu@xxxxxxxxxxxxxxx
 S:	Maintained
+F:	Documentation/RCU/rcu_txn.rst
 F:	include/linux/rcu_txn*.h
 F:	lib/rcu_txn*
 F:	lib/tests/rcu_txn_kunit.c
diff --git a/include/linux/rcu_txn.h b/include/linux/rcu_txn.h
index b9ee242a01ce..19f1365ae8ae 100644
--- a/include/linux/rcu_txn.h
+++ b/include/linux/rcu_txn.h
@@ -12,6 +12,8 @@
  * 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.
+ * Documentation/RCU/rcu_txn.rst says when to use them, and describes the data
+ * structures built on them.
  *
  * 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.
-- 
2.47.3