Re: [RFC PATCH 00/12] RCU pseudo-transactions
From: Mathieu Desnoyers
Date: Tue Nov 10 2026 - 11:23:33 EST
Hi Puranjay,
On 2026-10-23 14:19, Puranjay Mohan wrote:
[...]
I found two bugs, details in the replies to the patches:
Thanks for finding them, and for the reproducers. Fixes for both bugs
are planned for the next version. I answered each point of your patch
replies in its own thread. Here are the answers to the rest of this
mail.
Location: either works for me, but CONFIG_RCU_TXN is in lib/Kconfig and
CONFIG_DEBUG_RCU_TXN in kernel/rcu/Kconfig.debug; I'd keep them
together.
Planned for the next version. DEBUG_RCU_TXN will move to
lib/Kconfig.debug, next to RCU_TXN_KUNIT_TEST.
Bloom filter knob: I wouldn't add one.[...]
I'd drop patch 3 until something needs it.
Agreed. Dropping patch 3 is planned for the next version. Your size
table settled it.
API shape: every rcu_txn_list add, delete and replace allocates a
descriptor and frees it with kfree_rcu(), so all of them can fail with
-ENOMEM, delete included. That is hard to use on teardown paths, and
reserving first only moves the failure. Since a descriptor can be
reused a grace period after its commit, have you considered a small
cache of them, tagged with start_poll_synchronize_rcu() and checked with
poll_state_synchronize_rcu()?
The next version will implement the design of my second reply. It is
planned as three new patches:
- Readers resolve a proxy only within a resolve section. This
is a short section with interrupts off, counted per CPU. A writer can
wait for the sections in flight without sleeping.
- A local transaction takes its descriptor from a per-CPU
pool. The pool holds 16 descriptors of 6 records, 5920 bytes per CPU.
Preemption stays off from init to commit.
- The _rcu forms of rcu_txn_list run a local transaction. They take
no gfp_t and return nothing.
A cache alone does not cover a burst. A CPU can run more operations
within a grace period than its pool holds. When its pool is empty, the
CPU steals its own descriptors back. It waits for the resolve sections
in flight, then reuses them. So a delete never fails and never sleeps.
In the steady state, descriptors go back to the pool through
call_rcu_hurry(), with one rcu_head per batch. With CONFIG_RCU_LAZY,
call_rcu() can hold a callback back for up to 10 seconds. The
descriptors would stay out of the pool that long, and the CPU would
steal more often. I chose a callback over start_poll_synchronize_rcu()
because start_poll takes the leaf rcu_node lock on every call.
Separately, a one-record transaction
never installs a proxy but still allocates a descriptor, 256 bytes
unless reserved smaller; keeping the first record inline in struct
rcu_txn would avoid that.
I would rather handle this in the users than in rcu_txn. A user knows
which of the pointers it writes are followed by readers. An update that
re-points a single such slot needs no transaction. The writers are
excluded, and every commit settles its slots before it returns, so the
slot holds no proxy. rcu_assign_pointer() then publishes the update.
This covers more than one-record transactions. Each _rcu operation of
rcu_txn_hlist writes several pointers, but readers follow only one
edge. That edge is published with rcu_assign_pointer(), and pprev and
the new node's links take plain stores. So none of them creates a
transaction. Recorded through rcu_txn, the same update would take two
or three records, and an inline first record would not cover it.
Patch 7 documents this in Documentation/RCU/rcu_txn.rst.
The rcu_txn_list operations change at least two slots that readers
follow, so they need a descriptor. With the pool, they will allocate
nothing either.
Subsystems: in dcache the hash buckets are hlist_bl, with bit 0 of the
head as the lock, and d_unhashed() tests for a NULL pprev.
rcu_txn_hlist hard-codes bit 0 as its tag and has no unhashed state, so
I'm curious how your userspace port deals with both.
The hlist of this series is for tables locked some other way, as in the
samples. A bucket with a bit lock gets an rcu_txn_hlist_bl:
- The lock keeps bit 0, as in list_bl.h.
- The proxy tag takes bit 1.
- A record of the head carries the lock bit in its tag and in both of
its values. So the head stays locked from install to settle.
- Readers strip the lock bit. The engine is unchanged.
It is not part of this series. It exists on my branch that converts
the dentry cache to rcu_txn. The userspace port does the same with
other bits: tag in bit 0, lock in bit 2.
For d_unhashed(), the unhashed state you asked for in patch 5 is
planned for the next version. A removed node will have a NULL pprev.
Also, the only
in-tree user of list_bidir_prev_rcu(), kernel/nstree.c, walks either way
but never forward and then back in one walk, so a user that needs that
guarantee would help make the case for patch 6.
The node-lock sample (patch 12) is such a user. An eviction walks
back from the head to the tail. Then cache_lock_entry() reads the
tail's prev and next, to lock its neighbours. cache_plan_holds()
re-checks the four edges in both directions. If the backward chain
disagreed with the forward one, the writer would lock the wrong nodes.
Your reply to patch 6 makes the same point about LRU second chances.
I can send my KUnit reproducers as patches if they're useful.
Yes, please. They can go on top of the next version.
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com