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

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

On 2026-10-23 14:19, Puranjay Mohan wrote:
> Hi Mathieu,
> 
> On Fri, Oct 16, 2026 at 09:33:07AM -0400, Mathieu Desnoyers wrote:
>> 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.
> 
> I went through the series and ran the KUnit suite on arm64 (QEMU/KVM)
> with PROVE_LOCKING, PROVE_RAW_LOCK_NESTING and DEBUG_RCU_TXN.  All 59
> cases pass, and herd7 agrees with all 21 litmus tests.  The
> install/flip/settle ordering and the descriptor lifetime look right to
> me.


Thank you for the review and testing!

[...]

> 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()?

This question is really the crux of your feedback. There are many options
to explore here, and it all depends on the user expectations. Let's focus
on this one and keep your other questions for separate replies.

First, I suspect that the "add" and "replace" cases could fail with -ENOMEM
without too much problem, which really leaves "remove" as problematic.

The problem with the cache of descriptors (which I've done in my userspace
implementation already, a per-cpu "txn slab cache") is that it does not
fully address your concern: a thread doing a batch list removal in a huge
linked list can run out of pre-allocated descriptors before the grace period
ends and the descriptors are freed. How should we handle that ?

We should consider the way struct rcu_head is designed for call_rcu as a
precedent here. The tradeoff is to accept a waste of 16 bytes within
objects to make sure there is no memory allocation needed when call_rcu
is invoked. This ensures there is no situation where the caller may need
to block and wait for memory to be freed when invoking call_rcu, e.g. in
teardown scenarios.

The basic question is whether there is a _hard_ requirement on making sure
a list removal operation *never* sleeps due to memory allocation.

Another open question is whether what we want to prevent here is only memory
allocation, or do we also want to prevent blocking that waits for a RCU
grace period to complete ? Or RCU deferral the culprit of the issue here ?

Here are a few takes on what the user requirement could look like:


A) Allocate on object creation, no allocation on removal (hard requirement)

If there is a hard requirement on never allocating memory on list removal
(not even GFP_ATOMIC), here is one possible option:

We could embed 2x struct rcu_txn_record into each list node, so it's already
available for the eventual removal. We could then change the txn descriptor
from a flat array into a piecewise scattered set of 2 entries records
(one pair of records per pre-planned removal operation).

This wastes memory during the entire object lifetime. This could sit on
cache lines separate from the hot object cache lines. These objects would
need to plan space for the rcu_txn_group (the selector) so there is really
no rcu-reclaimed memory allocated for the transaction descriptor on removal.

The space overhead would be 4x larger than for rcu_head though, we're talking
about roughly one cache line (64 bytes)­ per object for list removal (2 records).


B) Use a preallocated per-cpu rcu-txn slab, allocate GFP_ATOMIC when slab is empty

Another option is to consider using a per-cpu slab of preallocated txn
descriptors. This suffers from the basic problem that if a user pushes
hard and depletes the reserve, we end up in a scenario where we still
need to allocate from that context.

Relying on GFP_ATOMIC allocation could help, up to a point, but this is not
bulletproof, as a user could also theoretically empty the atomic emergency
reserve as well.


C) Require user to pre-reserve txn descriptors in contexts able to handle allocation error

I've actually used that approach in my userspace fractal trie implementation to facilitate
error handling: each mutation operation first reserves all the memory it needs for
the rcu txns it will need to perform throughout the entire operation (e.g.
insertion, removal, rekey, graft...) so ENOMEM can be handled early before any
externally observable side-effect is done. This requires to carefully design the
data structure mutations so they are split into a planning, allocation and commit
stages.

I find that this approach was a good fit for userspace, but it does require to
allow "removal" operations to fail with ENOMEM if there is no memory available,
so I'm not sure how applicable it is for the kernel.


D) Use a preallocated per-cpu rcu-txn slab, synchronize_rcu when slab is empty
    (sleepable caller)

I would expect users to remove list items from within RCU read-side critical sections,
so calling synchronize_rcu() on the same RCU grace period "domain" would break this.

One alternative there is to consider having a different RCU grace period "domain" for
RCU txn, and wrap all accesses to the txn descriptors within that RCU domain read-side.
This way we could handle OOM by enqueuing the thread hitting OOM on a waitqueue associated
with the rcu-txn slab, which would necessarily be woken up when RCU readers of that
rcu-txn domain complete (typically in a short time frame), and the call-rcu worker moves
the memory back to the rcu-txn slab, and issues the wakeup.


E) Use a preallocated per-cpu rcu-txn slab, synchronize txn descriptor reclaim with
    RCU (steady state) and hazard pointers (OOM)

This is basically just pushing idea (D) further to remove the need for sleepable callers.
We surround the rcu txn proxy pointer resolve with both a RCU read-side critical section
and a hazard pointer slab address guard, thus protecting the use of the txn descriptor
with two types of critical sections. The resolve would run with interrupts disabled.
The "resolve" path of txn proxy is not a fast path, so we don't mind the extra overhead
too much.

On the "remove" side, we typically have plenty of preallocated rcu-txn from the slab.
In the common case, we keep using RCU deferral to free the rcu-txn in batches. This
would implement a custom per-cpu pending list to enable the following "stealing"
scheme.

In the rare cases where a user empties the slab, we move to a more aggressive
mechanism based on synchronize_hazptr: we "steal" the batched in-flight RCU txn
reclaims so we can fast-track their reclaim after a hazptr synchronize. This would
all be using busy-wait and the only contexts we'd wait against have irqs disabled.

The motivation for handling the steady-state with RCU is throughput (no synchronize_hazptr
on the typical "remove" case). Hazard pointers then handle the OOM corner case without
requiring sleepable callers.

Thoughts ?

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com