[PATCH] rculist : Introduce list/hlist_for_each_entry_srcu() macros

[PATCH] rculist : Introduce list/hlist_for_each_entry_srcu() macros

[madhuparnabhowmik10]

From: Madhuparna Bhowmik <madhuparnabhowmik10@gmail.com>

list/hlist_for_each_entry_rcu() provides an optional cond argument
to specify the lock held in the updater side.
However for SRCU read side, not providing the cond argument results
into false positive as whether srcu_read_lock is held or not is not
checked implicitly. Therefore, on read side the lockdep expression
srcu_read_lock_held(srcu struct) can solve this issue.

However, the function still fails to check the cases where srcu
protected list is traversed with rcu_read_lock() instead of
srcu_read_lock(). Therefore, to remove the false negative,
this patch introduces two new list traversal primitives :
list_for_each_entry_srcu() and hlist_for_each_entry_srcu().

Both of the functions have non-optional cond argument
as it is required for both read and update side, and simply checks
if the cond is true.

Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Madhuparna Bhowmik <madhuparnabhowmik10@gmail.com>
---
 include/linux/rculist.h | 44 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)

diff --git a/include/linux/rculist.h b/include/linux/rculist.h
index df587d181844..04a7e5791c39 100644
--- a/include/linux/rculist.h
+++ b/include/linux/rculist.h
@@ -63,9 +63,17 @@ static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
 	RCU_LOCKDEP_WARN(!(cond) && !rcu_read_lock_any_held(),		\
 			 "RCU-list traversed in non-reader section!");	\
 	})
+
+#define __list_check_srcu(cond)					 \
+	({								 \
+	RCU_LOCKDEP_WARN(!(cond),					 \
+		"RCU-list traversed without holding the required lock!");\
+	})
 #else
 #define __list_check_rcu(dummy, cond, extra...)				\
 	({ check_arg_count_one(extra); })
+
+#define __list_check_srcu(cond)
 #endif
 
 /*
@@ -383,6 +391,23 @@ static inline void list_splice_tail_init_rcu(struct list_head *list,
 		&pos->member != (head);					\
 		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 
+/**
+ * list_for_each_entry_srcu	-	iterate over rcu list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ * @cond:	lockdep expression for the lock required to traverse the list.
+ *
+ * This list-traversal primitive may safely run concurrently with
+ * the _rcu list-mutation primitives such as list_add_rcu()
+ * as long as the traversal is guarded by srcu_read_lock().
+ */
+#define list_for_each_entry_srcu(pos, head, member, cond)		\
+	for (__list_check_srcu(cond),					\
+	     pos = list_entry_rcu((head)->next, typeof(*pos), member);	\
+		&pos->member != (head);					\
+		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
+
 /**
  * list_entry_lockless - get the struct for this entry
  * @ptr:        the &struct list_head pointer.
@@ -681,6 +706,25 @@ static inline void hlist_add_behind_rcu(struct hlist_node *n,
 		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
 			&(pos)->member)), typeof(*(pos)), member))
 
+/**
+ * hlist_for_each_entry_srcu - iterate over rcu list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the hlist_node within the struct.
+ * @cond:	lockdep expression for the lock required to traverse the list.
+ *
+ * This list-traversal primitive may safely run concurrently with
+ * the _rcu list-mutation primitives such as hlist_add_head_rcu()
+ * as long as the traversal is guarded by srcu_read_lock().
+ */
+#define hlist_for_each_entry_srcu(pos, head, member, cond)		\
+	for (__list_check_srcu(cond),					\
+	     pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
+			typeof(*(pos)), member);			\
+		pos;							\
+		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
+			&(pos)->member)), typeof(*(pos)), member))
+
 /**
  * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
  * @pos:	the type * to use as a loop cursor.
-- 
2.17.1

Re: [PATCH] rculist : Introduce list/hlist_for_each_entry_srcu() macros

[joel]

On July 3, 2020 10:08:28 AM EDT, madhuparnabhowmik10@gmail.com wrote:
>From: Madhuparna Bhowmik <madhuparnabhowmik10@gmail.com>
>
>list/hlist_for_each_entry_rcu() provides an optional cond argument
>to specify the lock held in the updater side.
>However for SRCU read side, not providing the cond argument results
>into false positive as whether srcu_read_lock is held or not is not
>checked implicitly. Therefore, on read side the lockdep expression
>srcu_read_lock_held(srcu struct) can solve this issue.
>
>However, the function still fails to check the cases where srcu
>protected list is traversed with rcu_read_lock() instead of
>srcu_read_lock(). Therefore, to remove the false negative,
>this patch introduces two new list traversal primitives :
>list_for_each_entry_srcu() and hlist_for_each_entry_srcu().
>
>Both of the functions have non-optional cond argument
>as it is required for both read and update side, and simply checks
>if the cond is true.

Looks ok to me. Could you update the comment below to also clarify that in regular read side usage, the traversal can be done by also passing the expression srcu_read_lock_held which is also a lockdep expression.

Could you post the user-patches along with it? That gives more context to reviewers.

Thanks!

- Joel


>
>Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
>Signed-off-by: Madhuparna Bhowmik <madhuparnabhowmik10@gmail.com>
>---
> include/linux/rculist.h | 44 +++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 44 insertions(+)
>
>diff --git a/include/linux/rculist.h b/include/linux/rculist.h
>index df587d181844..04a7e5791c39 100644
>--- a/include/linux/rculist.h
>+++ b/include/linux/rculist.h
>@@ -63,9 +63,17 @@ static inline void INIT_LIST_HEAD_RCU(struct
>list_head *list)
> 	RCU_LOCKDEP_WARN(!(cond) && !rcu_read_lock_any_held(),		\
> 			 "RCU-list traversed in non-reader section!");	\
> 	})
>+
>+#define __list_check_srcu(cond)					 \
>+	({								 \
>+	RCU_LOCKDEP_WARN(!(cond),					 \
>+		"RCU-list traversed without holding the required lock!");\
>+	})
> #else
> #define __list_check_rcu(dummy, cond, extra...)				\
> 	({ check_arg_count_one(extra); })
>+
>+#define __list_check_srcu(cond)
> #endif
> 
> /*
>@@ -383,6 +391,23 @@ static inline void
>list_splice_tail_init_rcu(struct list_head *list,
> 		&pos->member != (head);					\
> 		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
> 
>+/**
>+ * list_for_each_entry_srcu	-	iterate over rcu list of given type
>+ * @pos:	the type * to use as a loop cursor.
>+ * @head:	the head for your list.
>+ * @member:	the name of the list_head within the struct.
>+ * @cond:	lockdep expression for the lock required to traverse the
>list.
>+ *
>+ * This list-traversal primitive may safely run concurrently with
>+ * the _rcu list-mutation primitives such as list_add_rcu()
>+ * as long as the traversal is guarded by srcu_read_lock().
>+ */
>+#define list_for_each_entry_srcu(pos, head, member, cond)		\
>+	for (__list_check_srcu(cond),					\
>+	     pos = list_entry_rcu((head)->next, typeof(*pos), member);	\
>+		&pos->member != (head);					\
>+		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
>+
> /**
>  * list_entry_lockless - get the struct for this entry
>  * @ptr:        the &struct list_head pointer.
>@@ -681,6 +706,25 @@ static inline void hlist_add_behind_rcu(struct
>hlist_node *n,
> 		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
> 			&(pos)->member)), typeof(*(pos)), member))
> 
>+/**
>+ * hlist_for_each_entry_srcu - iterate over rcu list of given type
>+ * @pos:	the type * to use as a loop cursor.
>+ * @head:	the head for your list.
>+ * @member:	the name of the hlist_node within the struct.
>+ * @cond:	lockdep expression for the lock required to traverse the
>list.
>+ *
>+ * This list-traversal primitive may safely run concurrently with
>+ * the _rcu list-mutation primitives such as hlist_add_head_rcu()
>+ * as long as the traversal is guarded by srcu_read_lock().
>+ */
>+#define hlist_for_each_entry_srcu(pos, head, member, cond)		\
>+	for (__list_check_srcu(cond),					\
>+	     pos =
>hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
>+			typeof(*(pos)), member);			\
>+		pos;							\
>+		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
>+			&(pos)->member)), typeof(*(pos)), member))
>+
> /**
>* hlist_for_each_entry_rcu_notrace - iterate over rcu list of given
>type (for tracing)
>  * @pos:	the type * to use as a loop cursor.

-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Re: [PATCH] rculist : Introduce list/hlist_for_each_entry_srcu() macros

[Madhuparna Bhowmik]

On Wed, Jul 08, 2020 at 08:33:49AM -0400, joel@joelfernandes.org wrote:
> 
> 
> On July 3, 2020 10:08:28 AM EDT, madhuparnabhowmik10@gmail.com wrote:
> >From: Madhuparna Bhowmik <madhuparnabhowmik10@gmail.com>
> >
> >list/hlist_for_each_entry_rcu() provides an optional cond argument
> >to specify the lock held in the updater side.
> >However for SRCU read side, not providing the cond argument results
> >into false positive as whether srcu_read_lock is held or not is not
> >checked implicitly. Therefore, on read side the lockdep expression
> >srcu_read_lock_held(srcu struct) can solve this issue.
> >
> >However, the function still fails to check the cases where srcu
> >protected list is traversed with rcu_read_lock() instead of
> >srcu_read_lock(). Therefore, to remove the false negative,
> >this patch introduces two new list traversal primitives :
> >list_for_each_entry_srcu() and hlist_for_each_entry_srcu().
> >
> >Both of the functions have non-optional cond argument
> >as it is required for both read and update side, and simply checks
> >if the cond is true.
> 
> Looks ok to me. Could you update the comment below to also clarify that in regular read side usage, the traversal can be done by also passing the expression srcu_read_lock_held which is also a lockdep expression.
> 
> Could you post the user-patches along with it? That gives more context to reviewers.
>
Thank you for reviewing the patch, I will make the changes suggested and
send the patch along with the user patches.

Regards,
Madhuparna

> Thanks!
> 
> - Joel
> 
> 
> >
> >Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
> >Signed-off-by: Madhuparna Bhowmik <madhuparnabhowmik10@gmail.com>
> >---
> > include/linux/rculist.h | 44 +++++++++++++++++++++++++++++++++++++++++
> > 1 file changed, 44 insertions(+)
> >
> >diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> >index df587d181844..04a7e5791c39 100644
> >--- a/include/linux/rculist.h
> >+++ b/include/linux/rculist.h
> >@@ -63,9 +63,17 @@ static inline void INIT_LIST_HEAD_RCU(struct
> >list_head *list)
> > 	RCU_LOCKDEP_WARN(!(cond) && !rcu_read_lock_any_held(),		\
> > 			 "RCU-list traversed in non-reader section!");	\
> > 	})
> >+
> >+#define __list_check_srcu(cond)					 \
> >+	({								 \
> >+	RCU_LOCKDEP_WARN(!(cond),					 \
> >+		"RCU-list traversed without holding the required lock!");\
> >+	})
> > #else
> > #define __list_check_rcu(dummy, cond, extra...)				\
> > 	({ check_arg_count_one(extra); })
> >+
> >+#define __list_check_srcu(cond)
> > #endif
> > 
> > /*
> >@@ -383,6 +391,23 @@ static inline void
> >list_splice_tail_init_rcu(struct list_head *list,
> > 		&pos->member != (head);					\
> > 		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
> > 
> >+/**
> >+ * list_for_each_entry_srcu	-	iterate over rcu list of given type
> >+ * @pos:	the type * to use as a loop cursor.
> >+ * @head:	the head for your list.
> >+ * @member:	the name of the list_head within the struct.
> >+ * @cond:	lockdep expression for the lock required to traverse the
> >list.
> >+ *
> >+ * This list-traversal primitive may safely run concurrently with
> >+ * the _rcu list-mutation primitives such as list_add_rcu()
> >+ * as long as the traversal is guarded by srcu_read_lock().
> >+ */
> >+#define list_for_each_entry_srcu(pos, head, member, cond)		\
> >+	for (__list_check_srcu(cond),					\
> >+	     pos = list_entry_rcu((head)->next, typeof(*pos), member);	\
> >+		&pos->member != (head);					\
> >+		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
> >+
> > /**
> >  * list_entry_lockless - get the struct for this entry
> >  * @ptr:        the &struct list_head pointer.
> >@@ -681,6 +706,25 @@ static inline void hlist_add_behind_rcu(struct
> >hlist_node *n,
> > 		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
> > 			&(pos)->member)), typeof(*(pos)), member))
> > 
> >+/**
> >+ * hlist_for_each_entry_srcu - iterate over rcu list of given type
> >+ * @pos:	the type * to use as a loop cursor.
> >+ * @head:	the head for your list.
> >+ * @member:	the name of the hlist_node within the struct.
> >+ * @cond:	lockdep expression for the lock required to traverse the
> >list.
> >+ *
> >+ * This list-traversal primitive may safely run concurrently with
> >+ * the _rcu list-mutation primitives such as hlist_add_head_rcu()
> >+ * as long as the traversal is guarded by srcu_read_lock().
> >+ */
> >+#define hlist_for_each_entry_srcu(pos, head, member, cond)		\
> >+	for (__list_check_srcu(cond),					\
> >+	     pos =
> >hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
> >+			typeof(*(pos)), member);			\
> >+		pos;							\
> >+		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
> >+			&(pos)->member)), typeof(*(pos)), member))
> >+
> > /**
> >* hlist_for_each_entry_rcu_notrace - iterate over rcu list of given
> >type (for tracing)
> >  * @pos:	the type * to use as a loop cursor.
> 
> -- 
> Sent from my Android device with K-9 Mail. Please excuse my brevity.