linked-list updates for 4.5
Subsystems (2)
cover linked-list updates for 4.5
Hello!
This series contains a few linked-list updates:
1. Use WRITE_ONCE() when adding to lists and hlists (reported
by KTSAN).
2. Use READ_ONCE() when testing for empty lists (reported by
KTSAN).
3. Introduce generic list_splice_tail_init_rcu(), courtesy of
Petko Manolov.
4. Use WRITE_ONCE() when initializing list_head structures (reported
by KTSAN).
Thanx, Paul
------------------------------------------------------------------------
b/include/linux/list.h | 14 ++++---- b/include/linux/list_bl.h | 2 - b/include/linux/list_nulls.h | 2 - b/include/linux/rculist.h | 69 ++++++++++++++++++++++++++++++------------- b/lib/list_debug.c | 2 - 5 files changed, 59 insertions(+), 30 deletions(-)
PATCH 1/4 list: Use WRITE_ONCE() when adding to lists and hlists
Code that does lockless emptiness testing of non-RCU lists is relying on the list-addition code to write the list head's ->next pointer atomically. This commit therefore adds WRITE_ONCE() to list-addition pointer stores that could affect the head's ->next pointer.
--- include/linux/list.h | 8 ++++---- lib/list_debug.c | 2 +- 2 files changed, 5 insertions(+), 5 deletions(-)
include/linux/list.h +4 -4
@@ -42,7 +42,7 @@ static inline void __list_add(struct list_head *new, next->prev = new; new->next = next; new->prev = prev; - prev->next = new; +WRITE_ONCE (prev->next, new); }#else extern void __list_add(struct list_head *new,
@@ -642,7 +642,7 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) n->next = first;if (first) first->pprev = &n->next; - h->first = n; +WRITE_ONCE (h->first, n); n->pprev = &h->first; }
@@ -653,14 +653,14 @@ static inline void hlist_add_before(struct hlist_node *n, n->pprev = next->pprev; n->next = next; next->pprev = &n->next; - *(n->pprev) = n; +WRITE_ONCE (*(n->pprev), n); }static inline void hlist_add_behind (struct hlist_node *n,struct hlist_node *prev) { n->next = prev->next; - prev->next = n; +WRITE_ONCE (prev->next, n); n->pprev = &prev->next;if (n->next)
lib/list_debug.c +1 -1
@@ -37,7 +37,7 @@ void __list_add(struct list_head *new, next->prev = new; new->next = next; new->prev = prev; - prev->next = new; +WRITE_ONCE (prev->next, new); }EXPORT_SYMBOL (__list_add);
Signature · 1 line
2.5.2
PATCH 2/4 list: Use READ_ONCE() when testing for empty lists
In reply to Paul E. McKenneyMost of the list-empty-check macros (list_empty(), hlist_empty(), hlist_bl_empty(), hlist_nulls_empty(), and hlist_nulls_empty()) use an unadorned load to check the list header. Given that these macros are sometimes invoked without the protection of a lock, this is not sufficient. This commit therefore adds READ_ONCE() calls to them. This commit does not touch llist_empty() because it already has the needed ACCESS_ONCE().
--- include/linux/list.h | 4 ++-- include/linux/list_bl.h | 2 +- include/linux/list_nulls.h | 2 +- 3 files changed, 4 insertions(+), 4 deletions(-)
include/linux/list.h +2 -2
@@ -186,7 +186,7 @@ static inline int list_is_last(const struct list_head *list,*/ static inline int list_empty (const struct list_head *head) { -return head->next == head; +return READ_ONCE (head->next) == head; }/**
@@ -608,7 +608,7 @@ static inline int hlist_unhashed(const struct hlist_node *h)static inline int hlist_empty (const struct hlist_head *h) { -return !h->first; +return !READ_ONCE (h->first); }static inline void __hlist_del (struct hlist_node *n)
include/linux/list_bl.h +1 -1
@@ -70,7 +70,7 @@ static inline void hlist_bl_set_first(struct hlist_bl_head *h,static inline int hlist_bl_empty (const struct hlist_bl_head *h) { -return !((unsigned long )h->first & ~LIST_BL_LOCKMASK ); +return !((unsigned long )READ_ONCE (h->first) & ~LIST_BL_LOCKMASK ); } static inline void hlist_bl_add_head(struct hlist_bl_node *n,
include/linux/list_nulls.h +1 -1
@@ -57,7 +57,7 @@ static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h)static inline int hlist_nulls_empty (const struct hlist_nulls_head *h) { -return is_a_nulls (h->first); +return is_a_nulls (READ_ONCE (h->first)); } static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
Signature · 1 line
2.5.2
PATCH 3/4 list: Introduces generic list_splice_tail_init_rcu()
In reply to Paul E. McKenneyFrom: Petko Manolov <[email protected]>
The list_splice_init_rcu() can be used as a stack onto which full lists are pushed, but queue-like behavior is now needed by some security policies. This requires a list_splice_tail_init_rcu().
This commit therefore supplies a list_splice_tail_init_rcu() by pulling code common it and to list_splice_init_rcu() into a new __list_splice_init_rcu() function. This new function is based on the existing list_splice_init_rcu() implementation.
--- include/linux/rculist.h | 69 +++++++++++++++++++++++++++++++++++-------------- 1 file changed, 49 insertions(+), 20 deletions(-)
include/linux/rculist.h +49 -20
@@ -179,32 +179,31 @@ static inline void list_replace_rcu(struct list_head *old, }/** -* list_splice_init_rcu - splice an RCU-protected list into an existing list. +* __list_splice_init_rcu - join an RCU-protected list into an existing list. * @list: the RCU-protected list to splice -* @head: the place in the list to splice the first list into +* @prev: points to the last element of the existing list +* @next: points to the first element of the existing list * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ... * -* @head can be RCU-read traversed concurrently with this function. +* The list pointed to by @prev and @next can be RCU-read traversed +* concurrently with this function. * * Note that this function blocks. * -* Important note: the caller must take whatever action is necessary to -* prevent any other updates to @head. In principle, it is possible -* to modify the list as soon as sync() begins execution. -* If this sort of thing becomes necessary, an alternative version -* based on call_rcu() could be created. But only if -really- -* needed -- there is no shortage of RCU API members. +* Important note: the caller must take whatever action is necessary to prevent +* any other updates to the existing list. In principle, it is possible to +* modify the list as soon as sync() begins execution. If this sort of thing +* becomes necessary, an alternative version based on call_rcu() could be +* created. But only if -really- needed -- there is no shortage of RCU API +* members. */ -static inline void list_splice_init_rcu (struct list_head *list, -struct list_head *head, -void (*sync)(void )) +static inline void __list_splice_init_rcu (struct list_head *list, +struct list_head *prev, +struct list_head *next, +void (*sync)(void )) {struct list_head *first = list->next;struct list_head *last = list->prev; -struct list_head *at = head->next; - -if (list_empty (list)) -return ;/* * "first" and "last" tracking list, so initialize it. RCU readers
@@ -231,10 +230,40 @@ static inline void list_splice_init_rcu(struct list_head *list,* this function. */ - last->next = at; -rcu_assign_pointer (list_next_rcu (head), first); - first->prev = head; - at->prev = last; + last->next = next; +rcu_assign_pointer (list_next_rcu (prev), first); + first->prev = prev; + next->prev = last; +} + +/** +* list_splice_init_rcu - splice an RCU-protected list into an existing list, +* designed for stacks. +* @list: the RCU-protected list to splice +* @head: the place in the existing list to splice the first list into +* @sync: function to sync: synchronize_rcu(), synchronize_sched(), ... +*/ +static inline void list_splice_init_rcu (struct list_head *list, +struct list_head *head, +void (*sync)(void )) +{ +if (!list_empty (list)) +__list_splice_init_rcu (list, head, head->next, sync); +} + +/** +* list_splice_tail_init_rcu - splice an RCU-protected list into an existing +* list, designed for queues. +* @list: the RCU-protected list to splice +* @head: the place in the existing list to splice the first list into +* @sync: function to sync: synchronize_rcu(), synchronize_sched(), ... +*/ +static inline void list_splice_tail_init_rcu (struct list_head *list, +struct list_head *head, +void (*sync)(void )) +{ +if (!list_empty (list)) +__list_splice_init_rcu (list, head->prev, head, sync); }/**
Signature · 1 line
2.5.2
PATCH 4/4 list: Use WRITE_ONCE() when initializing list_head structures
In reply to Paul E. McKenneyCode that does lockless emptiness testing of non-RCU lists is relying on INIT_LIST_HEAD() to write the list head's ->next pointer atomically, particularly when INIT_LIST_HEAD() is invoked from list_del_init(). This commit therefore adds WRITE_ONCE() to this function's pointer stores that could affect the head's ->next pointer.
--- include/linux/list.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/list.h +1 -1
@@ -24,7 +24,7 @@static inline void INIT_LIST_HEAD (struct list_head *list) { - list->next = list; +WRITE_ONCE (list->next, list); list->prev = list; }
Signature · 1 line
2.5.2