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

[Puranjay Mohan <puranjay@kernel.org>]

On Fri, Oct 16, 2026 at 09:33:13AM -0400, Mathieu Desnoyers wrote:
[...]

> +/*
> + * rcu_txn_list: a circular doubly-linked list whose forward and backward
> + * chains stay mutually coherent under concurrent RCU readers.  A reader may
> + * iterate in either direction, or reverse direction mid-traversal, and never
> + * observe the two directions disagree.
> + *

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.

[...]

> + * See rcu_txn_list_add_after_prepare().  Six edges switch together: the two
> + * that unlink @elem, the two that link it after @pos, and @elem's own next and
> + * prev, so that a reader standing on @elem leaves it by its old neighbours
> + * until the commit and by its new ones from then on.  The add forms cannot

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.  With H -> A -> B -> C, a reader on A when A moves after C steps
straight to H and never sees B or C, and a reader on C when C moves to
the front walks A and B again.  I checked both with sequential KUnit
cases.  LRU second chances are exactly this pattern.

[...]

> +/* Move @elem to the head of the list (just after @head). */
> +static inline int rcu_txn_list_move_rcu(struct rcu_txn_list_node *elem,
> +					struct rcu_txn_list_head *head,
> +					gfp_t gfp)
> +{
> +	return rcu_txn_list_move_after_rcu(elem, &head->node, gfp);
> +}

This looks like list_move(), whose kerneldoc is literally "delete from
one list and add as another's head", and nothing here says @head has to
be @elem's own list.  If it isn't, a reader standing on @elem follows
its new ->next into the other list and never gets back to its own
head, so rcu_txn_list_for_each_entry_rcu() never terminates and treats
the other list's head as an entry.  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.

Thanks,
Puranjay