On Thu, Dec 12, 2024 at 07:18:44AM -0800, Paul E. McKenney wrote:
> On Thu, Dec 12, 2024 at 12:56:03PM +0100, Christian Brauner wrote:
> > Currently there is no primite for retrieving the previous list member.
>
> s/primite/primitive/g
>
> To my surprise, there is an English word "primite". According to Merriam
> Webster, this is "the anterior member of a pair of gregarines in syzygy".
> I fervently hope not to have much opportunity to use this word, especially
> in reference to myself. But I cannot escape the suspicion that Merriam
> Webster might be engaging in a little trolling. ;-)
:)
>
> > To do this we need a new deletion primite that doesn't poison the prev
> > pointer and a corresponding retrieval helper. Note that it is not valid
> > to ues both list_del_rcu() and list_bidir_del_rcu() on the same list.
> >
> > Suggested-by: "Paul E. McKenney" <paulmck@xxxxxxxxxx>
> > Signed-off-by: Christian Brauner <brauner@xxxxxxxxxx>
>
> Looks good! I have a few suggestions below, mostly grammar nits.
Yes to all.
>
> Thanx, Paul
>
> > ---
> > include/linux/rculist.h | 43 +++++++++++++++++++++++++++++++++++++++++++
> > 1 file changed, 43 insertions(+)
> >
> > diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> > index 14dfa6008467e803d57f98cfa0275569f1c6a181..c81f9e5a789928ae6825c89325396d638b3e48c5 100644
> > --- a/include/linux/rculist.h
> > +++ b/include/linux/rculist.h
> > @@ -30,6 +30,14 @@ static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
> > * way, we must not access it directly
> > */
> > #define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
> > +/*
> > + * Return the ->prev pointer of a list_head in an rcu safe way. Don't
> > + * access it directly.
> > + *
> > + * In order to use list_bidir_prev_rcu() deletions must only be done via
> > + * list_bidir_del() to avoid poisoning the ->prev pointer.
>
> This should be list_bidir_del_rcu(), right? If so, I suggest wording
> this as follows or similar:
>
> * Any list traversed with list_bidir_prev_rcu() must never use
> * list_del_rcu(). Doing so will poison the ->prev pointer that
> * list_bidir_prev_rcu() relies on, which will result in segfaults.
> * To prevent these segfaults, use list_bidir_del_rcu() instead
> * of list_del_rcu().
>
> > + */
> > +#define list_bidir_prev_rcu(list) (*((struct list_head __rcu **)(&(list)->prev)))
>
> We need a rcu_dereference() in there somewhere, otherwise the compiler
> might ruin your day.
>
> Huh. You (quite reasonably) copy-pasta'd list_next_rcu(). So the
I expect the caller to do the rcu_dereference() just like with
list_next_rcu():
At first I made it include a rcu_dereference. But then I realized that
the api becomes rather wonky because list_next_rcu() would have to be
called with rcu_dereference() (most caller's do) and
list_bidir_prev_rcu() wouldn't.
That seemed very confusing to me so I just kept it aligned with
list_next_rcu(). Now, the correct follow-up cleanup would obviously be
to port both helpers to include the rcu_dereference() and thereby simply
all callers. For the few (mostly inside the header itself) we could just
add a __list_next_rcu() thing that doesn't include the
rcu_dereference().
> restriction is the same, the caller must use rcu_dereference. Unless,
> like seq_list_next_rcu(), you are never dereferencing it. That said,
> I am not so sure about the callers of unloaded_tainted_modules_seq_next()
> and rxrpc_call_seq_next(), which inherit the same restriction.
>
> If those two are used properly with rcu_dereference(), we have empirical
> evidence indicating that things might be OK. Otherwise, both need at
> least an upgrade of their header comments. ;-)
>
> > /**
> > * list_tail_rcu - returns the prev pointer of the head of the list
> > @@ -158,6 +166,41 @@ static inline void list_del_rcu(struct list_head *entry)
> > entry->prev = LIST_POISON2;
> > }
> >
> > +/**
> > + * list_bidir_del_rcu - deletes entry from list without re-initialization
> > + * @entry: the element to delete from the list.
> > + *
> > + * In contrat to list_del_rcu() doesn't poison the previous pointer thus
>
> Looks good, but while I am here, I might as well nitpick...
>
> "In constrast".
>
> > + * allowing to go backwards via list_prev_bidir_rcu().
>
> "allowing backwards traversal via"
>
> > + * Note: list_empty() on entry does not return true after this,
> > + * the entry is in an undefined state. It is useful for RCU based
>
> "because the entry is in a special undefined state that permits
> RCU-based lockfree reverse traversal."
>
> > + * lockfree traversal.
>
> At which point, you don't need this paragraph break.
>
> > + * In particular, it means that we can not poison the forward
>
> "this means that ... forward and backwards"
>
> > + * pointers that may still be used for walking the list.
> > + *
> > + * The caller must take whatever precautions are necessary
> > + * (such as holding appropriate locks) to avoid racing
> > + * with another list-mutation primitive, such as list_bidir_del_rcu()
> > + * or list_add_rcu(), running on this same list.
> > + * However, it is perfectly legal to run concurrently with
> > + * the _rcu list-traversal primitives, such as
> > + * list_for_each_entry_rcu().
> > + *
> > + * Noe that the it is not allowed to use list_del_rcu() and
>
> "Note that list_del_rcu() and list_bidir_del_rcu() must not be used on
> the same list at the same time."
>
> If you want to leave off the "at the same time", I am good. One could
> argue that we should not call attention to the possibility of adding
> this sort of complexity. Let them need it badly first. ;-)
>
> > + * list_bidir_del_rcu() on the same list.
> > + *
> > + * Note that the caller is not permitted to immediately free
> > + * the newly deleted entry. Instead, either synchronize_rcu()
> > + * or call_rcu() must be used to defer freeing until an RCU
> > + * grace period has elapsed.
> > + */
> > +static inline void list_bidir_del_rcu(struct list_head *entry)
> > +{
> > + __list_del_entry(entry);
> > +}
> > +
> > /**
> > * hlist_del_init_rcu - deletes entry from hash list with re-initialization
> > * @n: the element to delete from the hash list.
> >
> > --
> > 2.45.2
> >
