On Thu, Dec 12, 2024 at 12:25:42AM +0100, Christian Brauner wrote:
> Hey Paul,
>
> I have a rather dumb question...
>
> I'm keeping a very boring:
>
> static LIST_HEAD(mnt_ns_list);
>
> of mount namespaces. Userspace can pass a file descriptor for a mount
> namespace in that list to the kernel and then open a file descriptor to
> the next or previous mount namespace.
>
> As I was working on that I found list_next_rcu() but no
> list_prev_rcu(). Which made me curious and then I saw the comment in
> commit afa47fdfa29f ("rculist.h: Add list_tail_rcu()").
>
> /**
> * list_tail_rcu - returns the prev pointer of the head of the list
> * @head: the head of the list
> *
> * Note: This should only be used with the list header, and even then
> * only if list_del() and similar primitives are not also used on the
> * list header.
> */
>
> That comment strongly suggests that list_prev_rcu() somehow isn't
> generally safe to do? Is that the case and if so why? And what are
> possible ways to safely get to the previous list entry under rcu?
>
> (I'm currently doing this in an rbtree via rb_prev() and rb_next() but I
> can't do either of those locklessly which is why I want to keep a list
> in parallel as well.)
This is a design choice. It would be easy to create an RCU-protected list
that allowed readers to iterate in both the ->next and ->prev directions.
Why the forward-only restriction?
Because most use cases only need to traverse forward. Prohibiting
backwards traversal permits list_del_rcu() to poison the ->prev pointers,
which arguably makes for better error detection and debuggability.
If you need an RCU-protected bidirectional list, one way to supply
one would be to add list_del_bidir_rcu() and list_prev_bidir_rcu()
to the current list_head API, with the former dispensing with ->prev
poisoning and the latter adding rcu_dereference(). Note well that
p->lh.next->lh.prev will not necessarily be equal to p. This is because
there might have been a concurrent insertion or deletion, which would
instead result in p->lh.next or p->lh.prev, respectively.
One alternative is to supply a different list_head structure that has
a full API. But unless there is a strong reason for exploding the
API in the manner, adding the API members mentioned above seems like
it would be a better choice.
But in that case, there might need to be some sort of debugging features
prohibiting use of list_del_rcu() and list_prev_bidir_rcu() on the
same list.
Do you also need reverse-direction list iterators as well?
Details aside, it is eminently implementable. How would you like to
proceed?
Thanx, Paul
