On Wed, Dec 11, 2024 at 03:44:34PM -0800, Paul E. McKenney wrote:
> 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.
Aha, thank you for the explanation!
>
> 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.
Yes, I agree.
>
> 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?
No, I don't think so. I just need the ability to walk somewhere from the
middle but not the whole list from the end to the beginning... yet... I
don't want to make promises I can't keep. :)
>
> Details aside, it is eminently implementable. How would you like to
> proceed?
I will try and add list_del_bidir_rcu() and list_prev_bidir_rcu().
I'll Cc you on the series.
Thank you, Paul!
