| Message ID | 20241213-work-mount-rbtree-lockless-v3-4-6e3cdaf9b280@kernel.org (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | fs: lockless mntns lookup | expand |
On Fri, Dec 13, 2024 at 12:03:43AM +0100, Christian Brauner wrote: > Currently there is no primitive for retrieving the previous list member. > To do this we need a new deletion primitive 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@kernel.org> > Signed-off-by: Christian Brauner <brauner@kernel.org> One additional nit below. With that fixed: Reviewed-by: Paul E. McKenney <paulmck@kernel.org> > --- > include/linux/rculist.h | 47 +++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 47 insertions(+) > > diff --git a/include/linux/rculist.h b/include/linux/rculist.h > index 14dfa6008467e803d57f98cfa0275569f1c6a181..270a9ee2f7976b1736545667973265a3bfb7ec41 100644 > --- a/include/linux/rculist.h > +++ b/include/linux/rculist.h > @@ -30,6 +30,17 @@ 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. > + * > + * 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))) > > /** > * list_tail_rcu - returns the prev pointer of the head of the list > @@ -158,6 +169,42 @@ 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 contrast to list_del_rcu() doesn't poison the prev pointer thus > + * allowing backwards traversal via list_bidir_prev_rcu(). > + * > + * Note: list_empty() on entry does not return true after this because > + * the entry is in a special undefined state that permits RCU-based > + * lockfree reverse traversal. In particular this means that we can not > + * poison the 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 > + * list_bidir_del_rcu() on the same list. I am guessing that the above paragraph is a leftover? > + * Note that list_del_rcu() and list_bidir_del_rcu() must not be used 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 >
On Thu, Dec 12, 2024 at 04:42:54PM -0800, Paul E. McKenney wrote: > On Fri, Dec 13, 2024 at 12:03:43AM +0100, Christian Brauner wrote: > > Currently there is no primitive for retrieving the previous list member. > > To do this we need a new deletion primitive 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@kernel.org> > > Signed-off-by: Christian Brauner <brauner@kernel.org> > > One additional nit below. With that fixed: > > Reviewed-by: Paul E. McKenney <paulmck@kernel.org> Thansk, Paul! > > > --- > > include/linux/rculist.h | 47 +++++++++++++++++++++++++++++++++++++++++++++++ > > 1 file changed, 47 insertions(+) > > > > diff --git a/include/linux/rculist.h b/include/linux/rculist.h > > index 14dfa6008467e803d57f98cfa0275569f1c6a181..270a9ee2f7976b1736545667973265a3bfb7ec41 100644 > > --- a/include/linux/rculist.h > > +++ b/include/linux/rculist.h > > @@ -30,6 +30,17 @@ 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. > > + * > > + * 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))) > > > > /** > > * list_tail_rcu - returns the prev pointer of the head of the list > > @@ -158,6 +169,42 @@ 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 contrast to list_del_rcu() doesn't poison the prev pointer thus > > + * allowing backwards traversal via list_bidir_prev_rcu(). > > + * > > + * Note: list_empty() on entry does not return true after this because > > + * the entry is in a special undefined state that permits RCU-based > > + * lockfree reverse traversal. In particular this means that we can not > > + * poison the 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 > > + * list_bidir_del_rcu() on the same list. > > I am guessing that the above paragraph is a leftover? Indeed, fixed!
diff --git a/include/linux/rculist.h b/include/linux/rculist.h index 14dfa6008467e803d57f98cfa0275569f1c6a181..270a9ee2f7976b1736545667973265a3bfb7ec41 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -30,6 +30,17 @@ 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. + * + * 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))) /** * list_tail_rcu - returns the prev pointer of the head of the list @@ -158,6 +169,42 @@ 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 contrast to list_del_rcu() doesn't poison the prev pointer thus + * allowing backwards traversal via list_bidir_prev_rcu(). + * + * Note: list_empty() on entry does not return true after this because + * the entry is in a special undefined state that permits RCU-based + * lockfree reverse traversal. In particular this means that we can not + * poison the 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 + * list_bidir_del_rcu() on the same list. + * + * Note that list_del_rcu() and list_bidir_del_rcu() must not be used 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.
Currently there is no primitive for retrieving the previous list member. To do this we need a new deletion primitive 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@kernel.org> Signed-off-by: Christian Brauner <brauner@kernel.org> --- include/linux/rculist.h | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+)