Re: [RFC PATCH 06/12] rcu_txn: Add a doubly-linked list coherent in both directions
From: Mathieu Desnoyers
Date: Tue Nov 10 2026 - 10:23:52 EST
On 2026-10-23 14:22, Puranjay Mohan wrote:
[...]
This overstates it a bit: a reader can read P->next == N and then, once
an insertion of E between them commits, read N->prev == E. The commit
message puts it accurately ("never finds the new value of an edge and
then the old value of the other"), so I'd use that wording here too.
Agreed. The next version will use the wording of the commit message in
the header.
Your points show two levels of coherence, and the header should name
both:
- Per-node coherence: a reader never finds the new value of an edge,
then the old value of the other. Every operation of rcu_txn_list
gives it.
- Per-walk coherence: a walk visits every node that is not moved
exactly once, and ends at its own head. A move does not give it,
as your examples show.
[...]
That has a consequence for iterators, which should be documented: a
reader standing on the moved node can skip or revisit nodes that never
moved.
Agreed. The next version will document it on the iterators and on the
move forms.
So the next version will present two ways to move a node, and the
caller picks by what its readers need.
The move itself never fails, never sleeps, and never waits for a grace
period. Its descriptor goes back to the per-CPU pool through
call_rcu_hurry(). It keeps per-node coherence, which an RCU list cannot
give for a move: a delete then an add are two updates that readers
observe separately. The move fits:
- readers that take the first or last entry, or that reach a node
through another index, then read its neighbours;
- walkers that tolerate a skipped or repeated node, like an LRU scan,
when the node moves within the same list. A walker standing on a
node moved to another list would never reach its own head;
- writers that cannot sleep, like a second chance under a spinlock;
- moves composed with other edits in one commit, through
rcu_txn_list_move_after_prepare().
A writer whose readers need per-walk coherence can instead delete the
node, wait for a grace period, then add it back. A deleted node keeps
its next and prev, so a reader standing on it leaves in the old order.
The add comes after every reader that saw the node at its old place. So
a walk sees every other node exactly once, and the moved node at most
once. The cost is a writer that sleeps for a grace period, and a node
that readers do not find during that time.
With this sequence, your reader on A walks H -> A -> B -> C -> H. So
does your reader on C.
[...]
Either document on every move form that the destination must be in
the same list, or give readers a way to detect it, like hlist_nulls
does.
The next version will document it on every move form, with the
reason. A move to another list can use the same sequence. A reader
standing on the node finishes its own list, and ends at its own head.
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com