Re: [RFC PATCH 00/12] RCU pseudo-transactions

[Joel Fernandes <joelagnelf@nvidia.com>]

On Fri, Oct 16, 2026 at 09:33:07AM -0400, Mathieu Desnoyers wrote:
> Hi,
> 
> Earlier this year, I came up with a neat trick which reduces the mental
> challenge of adapting data structures to RCU.  It turns out that it also
> widens the applicability of RCU to additional classes of data
> structures.
> 
> This is done by a low-overhead abstraction which I'm naming
> "RCU Pseudo-Transactions" [1, 2]. I name this "pseudo" because unlike
> classic transactions, the writers exclude each other, readers get no
> snapshot, and there is no abort.

Cool idea! Instead of tagging the pointer, perhaps alternatively the proxy
object can be allocated in specific dedicated parts of kernel address space?
Might be slower to test against though. But perhaps will make it usable by any
users who use lower bits for other purposes.

Btw, Pseudo-Transactions sounds long and weird, maybe "RCU proxy"? :-)

thanks,

Joel Fernandes


> 
> How it works:
> 
> - Reader (rcu_txn_dereference()):
>   - Load (rcu_dereference()) pointer from slot.
>   - Fast path (no proxy installed): unlikely low-bit tag test and
>     conditional branch (not taken).
>   - Slow path (proxy installed): low-bit tag test, taken branch,
>     the proxy points at the slot's record, select old or new via the
>     group selector word (0/1) (load-acquire).  Still wait-free.
>   - Pointer constraint: Slots must hold pointers which are at least
>     2-byte aligned when using the low bit as tag and must not use
>     the low bit for anything else. NULL is handled as a plain value.
> 
> - Updater (caller provides mutual exclusion):
>   - Allocate a transaction descriptor (gfp flags provided by the caller).
>   - Append records to the descriptor.  (each slot appears at most once
>     per transaction)
>   - Commit (works in atomic context):
>     - Install proxy pointers into each slot. (store-release)
>     - Commit (flip group selector from 0 to 1). (store-release)
>     - Settle (each slot loses the proxy, gets the new pointer value).
>       (store-release)
>   - kfree_rcu the transaction descriptor.
> 
> Here are the key highlights:
> 
> - It enables atomic publication of multiple pointers observed by
>   concurrent RCU readers. It removes the tricky "but what if a
>   reader observes this intermediate state" conundrum typically present
>   when porting a data structure to RCU.  A reader that loads one slot
>   before the commit and another after it sees old then new values,
>   never the reverse along a chain of dependent loads (or with an acquire
>   between them).
> 
> - It allows composing data structures: a node can be published
>   atomically into many data structures (e.g. hash bucket list and
>   LRU list).
> 
> - It removes ordering requirements on multiple object publication
>   with respect to RCU traversal order.
> 
> - Can be used as a building block for fine-grained data structure
>   locking (see the second example in this series).
> 
> - It enables RCU traversals of cyclic graphs with arbitrary traversal
>   order.
> 
> - It allows replacing sequence locks and reader-writer locks in many
>   use-cases, providing read-side wait-free progress guarantees, in
>   scenarios where readers need a coherent walk rather than a snapshot of
>   several fields.
> 
> - It removes the need to copy data structure nodes for updates:
>   multiple pointer (and data field) updates can be performed
>   in-place on memory that cannot be reallocated.
> 
> I have presented it at LPC [1] and uploaded an article [2] detailing
> the idea as a defensive publication.  There are no patent claims on this
> work.
> 
> In this RFC, I'm presenting a port of rcu_txn to the Linux kernel,
> along with a list and hlist API built on top of it. You will also
> find composed hash bucket list and LRU list examples near the end
> of the series. I've implemented one example with a single mutex, and the
> other using RCU for neighborhood lookup and fine-grained per-node
> locking.
> 
> I considered various alternatives such as Paul McKenney's "existence
> guarantees" work (2015), seqlock, rwlocks, RLU, MV-RLU, and k-CAS (all
> discussed in the paper), but RCU pseudo-transactions performed better
> than the alternatives in my benchmarks due to smaller cache footprint
> and fewer read-side fast path instructions.  I have applied this to a
> partial port of the dentry cache to userspace; compared to a straight
> userspace port of the current kernel scheme, the rcu_txn variant shows
> up to 6.75x speedup for reverse walk under concurrent renames, and up to
> 21.56x speedup on writer throughput when scaling to 8 writers with 184
> concurrent readers under a leaf name exchange workload (see LPC slides).
> 
> About the development process of this feature: I have used an LLM coding
> assistant (Claude) throughout the development of this feature. The novel
> ideas are my own, and I have carefully followed its progress, guided it
> towards acceptable solutions when it was hitting walls, and reviewed the
> resulting code.
> 
> Origin story: I came up with this idea while working on a userspace RCU
> trie data structure which I named Fractal Trie (still in development),
> and I needed to be able to atomically publish parent/child pointer
> updates on nodes which were controlled by the application (therefore not
> mine to reallocate).
> 
> The series is based on v7.3-rc7.
> 
> - Patch 1: rcu_txn core API.
> - Patch 2: KUnit tests for the core API.
> - Patch 3: Bloom filter so appending a record to a large transaction
>            does not require an O(n) scan for an existing record for that
>            slot (O(n^2) overall).
> - Patch 4: rcu_txn_adopt, debug config option for internal consistency
>            checks.
> - Patches 5-6: composable singly and doubly linked lists on top of rcu_txn.
> - Patch 7: documentation.
> - Patch 8: litmus tests.
> - Patch 9: list writer stress test.
> - Patch 10: test of commit in atomic context.
> - Patches 11-12: usage example for composed data structures: a cache
>                  whose nodes are present in both a bucket hlist and an
>                  LRU list, one variant with a single mutex, the other
>                  with RCU neighborhood lookup and per-node locking.
> 
> There are a few areas where I suspect this abstraction could help in the
> Linux kernel, namely the VFS layer and mm_struct VMA tree / per-VMA
> locking.  I'm interested to hear whether this is useful in other
> subsystems.
> 
> I'd specifically like feedback on:
> 
> - Where this should live (kernel/rcu/, lib/?),
> 
> - Naming and API shape (descriptor + records),
> 
> - Whether the Bloom filter threshold should be a config knob,
> 
> - Subsystems where this could apply.
> 
> Enjoy!
> 
> Mathieu
> 
> References:
> [1] "RCU Pseudo-Transactions: Bridging the gap between RCU and STM",
>     Mathieu Desnoyers,
>     Linux Plumbers Conference 2026 Refereed Track, October 2026.
>     https://lpc.events/event/20/contributions/2348/
> 
> [2] "RCU Pseudo-Transactions and the Single-Writer Flip-Latch:
>     Atomic Multi-Slot Publication for Read-Copy-Update Data Structures",
>     Mathieu Desnoyers, October 2026.
>     https://www.efficios.com/pub/rcu-txn/mathieu-desnoyers-rcu-pseudo-transactions.pdf
> 
> Mathieu Desnoyers (12):
>   rcu_txn: Add single-writer RCU pseudo-transactions
>   rcu_txn: Add KUnit tests
>   rcu_txn: Skip the record lookup with a Bloom filter
>   rcu_txn: Add CONFIG_DEBUG_RCU_TXN
>   rcu_txn: Add an hlist edited through transactions
>   rcu_txn: Add a doubly-linked list coherent in both directions
>   Documentation/RCU: Describe RCU pseudo-transactions
>   Documentation/litmus-tests: Add RCU pseudo-transaction tests
>   rcu_txn: Test a list writer against concurrent readers
>   rcu_txn: Test a commit from atomic context
>   samples: Add a cache on RCU pseudo-transactions under one mutex
>   samples: Add a cache on RCU pseudo-transactions with a lock per node
> 
>  Documentation/RCU/index.rst                   |    1 +
>  Documentation/RCU/rcu_txn.rst                 |  255 ++
>  Documentation/litmus-tests/README             |   37 +
>  .../rcu/RCU-txn+install+once-install.litmus   |   55 +
>  .../litmus-tests/rcu/RCU-txn+install.litmus   |   66 +
>  .../RCU-txn+list+step-back+once-flip.litmus   |   78 +
>  .../RCU-txn+list+step-back+once-settle.litmus |   78 +
>  .../rcu/RCU-txn+list+step-back.litmus         |   85 +
>  ...-txn+monotonic+acquire+once-resolve.litmus |   79 +
>  .../rcu/RCU-txn+monotonic+acquire.litmus      |   81 +
>  .../RCU-txn+monotonic+dep+once-flip.litmus    |   77 +
>  .../RCU-txn+monotonic+dep+once-settle.litmus  |   77 +
>  .../rcu/RCU-txn+monotonic+dep.litmus          |   83 +
>  .../rcu/RCU-txn+monotonic+unordered.litmus    |   84 +
>  .../rcu/RCU-txn+publish+once-install.litmus   |   60 +
>  .../rcu/RCU-txn+publish+once-settle.litmus    |   60 +
>  .../litmus-tests/rcu/RCU-txn+publish.litmus   |   71 +
>  .../rcu/RCU-txn+remove+nolock.litmus          |   64 +
>  .../rcu/RCU-txn+remove+nosync.litmus          |   64 +
>  .../rcu/RCU-txn+remove+once-install.litmus    |   65 +
>  .../litmus-tests/rcu/RCU-txn+remove.litmus    |   72 +
>  .../rcu/RCU-txn+sync+free+nolock.litmus       |   55 +
>  .../rcu/RCU-txn+sync+free+nosync.litmus       |   55 +
>  .../litmus-tests/rcu/RCU-txn+sync+free.litmus |   60 +
>  MAINTAINERS                                   |   11 +
>  include/linux/rcu_txn.h                       | 1036 ++++++++
>  include/linux/rcu_txn_bloom.h                 |  110 +
>  include/linux/rcu_txn_hlist.h                 |  486 ++++
>  include/linux/rcu_txn_list.h                  |  544 +++++
>  kernel/rcu/Kconfig.debug                      |   16 +
>  lib/Kconfig                                   |    3 +
>  lib/Kconfig.debug                             |   13 +
>  lib/Makefile                                  |    2 +
>  lib/rcu_txn.c                                 |  142 ++
>  lib/rcu_txn_internal.h                        |  129 +
>  lib/tests/Makefile                            |    1 +
>  lib/tests/rcu_txn_kunit.c                     | 2150 +++++++++++++++++
>  samples/Kconfig                               |   13 +
>  samples/Makefile                              |    1 +
>  samples/rcu_txn/Makefile                      |    2 +
>  samples/rcu_txn/rcu_txn_cache_mutex.c         |  354 +++
>  samples/rcu_txn/rcu_txn_cache_node_lock.c     |  713 ++++++
>  42 files changed, 7488 insertions(+)
>  create mode 100644 Documentation/RCU/rcu_txn.rst
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+install+once-install.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+install.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+list+step-back+once-flip.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+list+step-back+once-settle.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+list+step-back.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+monotonic+acquire+once-resolve.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+monotonic+acquire.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+monotonic+dep+once-flip.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+monotonic+dep+once-settle.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+monotonic+dep.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+monotonic+unordered.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+publish+once-install.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+publish+once-settle.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+publish.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+remove+nolock.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+remove+nosync.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+remove+once-install.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+remove.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+sync+free+nolock.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+sync+free+nosync.litmus
>  create mode 100644 Documentation/litmus-tests/rcu/RCU-txn+sync+free.litmus
>  create mode 100644 include/linux/rcu_txn.h
>  create mode 100644 include/linux/rcu_txn_bloom.h
>  create mode 100644 include/linux/rcu_txn_hlist.h
>  create mode 100644 include/linux/rcu_txn_list.h
>  create mode 100644 lib/rcu_txn.c
>  create mode 100644 lib/rcu_txn_internal.h
>  create mode 100644 lib/tests/rcu_txn_kunit.c
>  create mode 100644 samples/rcu_txn/Makefile
>  create mode 100644 samples/rcu_txn/rcu_txn_cache_mutex.c
>  create mode 100644 samples/rcu_txn/rcu_txn_cache_node_lock.c
> 
> 
> base-commit: 24a19b953e2a3d0ea5a8c4951a0ab8f32720c907
> -- 
> 2.47.3
>