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

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

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