Re: [RFC PATCH 06/12] rcu_txn: Add a doubly-linked list coherent in both directions

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

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