[PATCH] list.h: add list_for_each_entry_continue_rcu

[PATCH] list.h: add list_for_each_entry_continue_rcu

[Johannes Berg]

To implement the multicast list callback in mac80211 we need to
do partial list iteration. Since I want to convert the interface
list to an RCU list, I need a new list walking primitive:
list_for_each_entry_continue_rcu().

Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
Cc: linux-kernel@vger.kernel.org
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: Randy Dunlap <randy.dunlap@oracle.com>
Cc: Pavel Emelianov <xemul@openvz.org>
Cc: Zach Brown <zach.brown@oracle.com>
Cc: Dave Jones <davej@redhat.com>
Cc: Oleg Nesterov <oleg@tv-sign.ru>

---
How do we want to handle this? Is it ok to push this via net-2.6.24 so
we can merge it along with the fix that needs it?

 include/linux/list.h |   20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

--- wireless-dev.orig/include/linux/list.h	2007-09-07 00:16:07.374444290 +0200
+++ wireless-dev/include/linux/list.h	2007-08-29 21:08:14.802054000 +0200
@@ -665,6 +665,26 @@ static inline void list_splice_init_rcu(
 		prefetch(rcu_dereference((pos))->next), (pos) != (head); \
         	(pos) = (pos)->next)
 
+
+/**
+ * list_for_each_entry_continue_rcu - continue iteration over rcu list
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Continue to iterate over rcu list of given type, continuing after
+ * the current position.
+ *
+ * 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 rcu_read_lock().
+ */
+#define list_for_each_entry_continue_rcu(pos, head, member) \
+	for ((pos) = list_entry((pos)->member.next, typeof(*pos), member); \
+		prefetch(rcu_dereference((pos))->member.next), \
+			 &pos->member != (head); \
+        	(pos) = list_entry(pos->member.next, typeof(*pos), member))
+
 /*
  * Double linked lists with a single pointer list head.
  * Mostly useful for hash tables where the two pointer list head is

Re: [PATCH] list.h: add list_for_each_entry_continue_rcu

[Paul E. McKenney]

On Fri, Sep 07, 2007 at 04:34:48PM +0200, Johannes Berg wrote:
> To implement the multicast list callback in mac80211 we need to
> do partial list iteration. Since I want to convert the interface
> list to an RCU list, I need a new list walking primitive:
> list_for_each_entry_continue_rcu().
> 
> Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
> Cc: linux-kernel@vger.kernel.org
> Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Cc: Herbert Xu <herbert@gondor.apana.org.au>
> Cc: Randy Dunlap <randy.dunlap@oracle.com>
> Cc: Pavel Emelianov <xemul@openvz.org>
> Cc: Zach Brown <zach.brown@oracle.com>
> Cc: Dave Jones <davej@redhat.com>
> Cc: Oleg Nesterov <oleg@tv-sign.ru>
> 
> ---
> How do we want to handle this? Is it ok to push this via net-2.6.24 so
> we can merge it along with the fix that needs it?
> 
>  include/linux/list.h |   20 ++++++++++++++++++++
>  1 file changed, 20 insertions(+)
> 
> --- wireless-dev.orig/include/linux/list.h	2007-09-07 00:16:07.374444290 +0200
> +++ wireless-dev/include/linux/list.h	2007-08-29 21:08:14.802054000 +0200
> @@ -665,6 +665,26 @@ static inline void list_splice_init_rcu(
>  		prefetch(rcu_dereference((pos))->next), (pos) != (head); \
>          	(pos) = (pos)->next)
> 
> +
> +/**
> + * list_for_each_entry_continue_rcu - continue iteration over rcu list
> + * @pos:	the type * to use as a loop cursor.
> + * @head:	the head for your list.
> + * @member:	the name of the list_struct within the struct.
> + *
> + * Continue to iterate over rcu list of given type, continuing after
> + * the current position.

Please add something like the following to this comment:

	Note that the caller is responsible for making sure that
	the element remains in place between the earlier iterator
	and this one.  One way to do this is to ensure that
	both iterators are covered by the same rcu_read_lock(),
	while others involve reference counts, flags, or mutexes.

						Thanx, Paul

> + *
> + * 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 rcu_read_lock().
> + */
> +#define list_for_each_entry_continue_rcu(pos, head, member) \
> +	for ((pos) = list_entry((pos)->member.next, typeof(*pos), member); \
> +		prefetch(rcu_dereference((pos))->member.next), \
> +			 &pos->member != (head); \
> +        	(pos) = list_entry(pos->member.next, typeof(*pos), member))
> +
>  /*
>   * Double linked lists with a single pointer list head.
>   * Mostly useful for hash tables where the two pointer list head is
> 
> 

Re: [PATCH] list.h: add list_for_each_entry_continue_rcu

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 637 bytes --]

On Fri, 2007-09-07 at 08:34 -0700, Paul E. McKenney wrote:

> > + * Continue to iterate over rcu list of given type, continuing after
> > + * the current position.
> 
> Please add something like the following to this comment:
> 
> 	Note that the caller is responsible for making sure that
> 	the element remains in place between the earlier iterator
> 	and this one.  One way to do this is to ensure that
> 	both iterators are covered by the same rcu_read_lock(),
> 	while others involve reference counts, flags, or mutexes.

Sure, will do. Should this comment also be added to
list_for_each_continue_rcu()?

johannes


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

Re: [PATCH] list.h: add list_for_each_entry_continue_rcu

[Paul E. McKenney]

On Fri, Sep 07, 2007 at 09:09:52PM +0200, Johannes Berg wrote:
> On Fri, 2007-09-07 at 08:34 -0700, Paul E. McKenney wrote:
> 
> > > + * Continue to iterate over rcu list of given type, continuing after
> > > + * the current position.
> > 
> > Please add something like the following to this comment:
> > 
> > 	Note that the caller is responsible for making sure that
> > 	the element remains in place between the earlier iterator
> > 	and this one.  One way to do this is to ensure that
> > 	both iterators are covered by the same rcu_read_lock(),
> > 	while others involve reference counts, flags, or mutexes.
> 
> Sure, will do. Should this comment also be added to
> list_for_each_continue_rcu()?

Actually, list_for_each_continue_rcu() needs to be removed in favor of
your new list_for_each_entry_continue_rcu().  There are currently only
two users as of 2.6.22.  One of them immediately does a list_entry(),
and the other would convert easily as well.  So please let me know
when this gets accepted!  ;-)

						Thanx, Paul

Re: [PATCH] list.h: add list_for_each_entry_continue_rcu

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 700 bytes --]

On Fri, 2007-09-07 at 12:57 -0700, Paul E. McKenney wrote:

> Actually, list_for_each_continue_rcu() needs to be removed in favor of
> your new list_for_each_entry_continue_rcu().  There are currently only
> two users as of 2.6.22.  One of them immediately does a list_entry(),
> and the other would convert easily as well.  So please let me know
> when this gets accepted!  ;-)

Heh, ok, I won't add the text to that macro if you want to remove it
anyway. I guess I'll add your paragraph and ... hmm. what do I do with
it? Who's responsible for list.h? Can I push this through John Linville
and Dave Miller so I can get the fix into his tree easily without
synchronisation?

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

[PATCH] list.h: add list_for_each_entry_continue_rcu

[Johannes Berg]

To implement the multicast list callback in mac80211 we need to
do partial list iteration. Since I want to convert the interface
list to an RCU list, I need a new list walking primitive:
list_for_each_entry_continue_rcu().

Additional help text was provided by Paul McKenney.

Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
Cc: linux-kernel@vger.kernel.org
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

---
John, I don't know if you want to merge this or not. There's no clear
list.h maintainer and this patch is requisite for the bugfix I'm going
to send in a minute so it'd probably be best if this goes into the tree
together.
If you don't want to take it, however, I have no idea how to handle the
situation :)

 include/linux/list.h |   26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

--- wireless-dev.orig/include/linux/list.h	2007-09-07 22:00:41.234425862 +0200
+++ wireless-dev/include/linux/list.h	2007-09-07 22:05:08.184425862 +0200
@@ -665,6 +665,32 @@ static inline void list_splice_init_rcu(
 		prefetch(rcu_dereference((pos))->next), (pos) != (head); \
         	(pos) = (pos)->next)
 
+
+/**
+ * list_for_each_entry_continue_rcu - continue iteration over rcu list
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Continue to iterate over rcu list of given type, continuing after
+ * the current position.
+ *
+ * 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 rcu_read_lock().
+ *
+ * Note that the caller is responsible for making sure that
+ * the element remains in place between the earlier iterator
+ * and this one.  One way to do this is to ensure that
+ * both iterators are covered by the same rcu_read_lock(),
+ * while others involve reference counts, flags, or mutexes.
+ */
+#define list_for_each_entry_continue_rcu(pos, head, member) \
+	for ((pos) = list_entry((pos)->member.next, typeof(*pos), member); \
+		prefetch(rcu_dereference((pos))->member.next), \
+			 &pos->member != (head); \
+        	(pos) = list_entry(pos->member.next, typeof(*pos), member))
+
 /*
  * Double linked lists with a single pointer list head.
  * Mostly useful for hash tables where the two pointer list head is

Re: [PATCH] list.h: add list_for_each_entry_continue_rcu

[Paul E. McKenney]

On Mon, Sep 10, 2007 at 02:05:47PM +0200, Johannes Berg wrote:
> To implement the multicast list callback in mac80211 we need to
> do partial list iteration. Since I want to convert the interface
> list to an RCU list, I need a new list walking primitive:
> list_for_each_entry_continue_rcu().
> 
> Additional help text was provided by Paul McKenney.

Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

> Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
> Cc: linux-kernel@vger.kernel.org
> Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> 
> ---
> John, I don't know if you want to merge this or not. There's no clear
> list.h maintainer and this patch is requisite for the bugfix I'm going
> to send in a minute so it'd probably be best if this goes into the tree
> together.
> If you don't want to take it, however, I have no idea how to handle the
> situation :)
> 
>  include/linux/list.h |   26 ++++++++++++++++++++++++++
>  1 file changed, 26 insertions(+)
> 
> --- wireless-dev.orig/include/linux/list.h	2007-09-07 22:00:41.234425862 +0200
> +++ wireless-dev/include/linux/list.h	2007-09-07 22:05:08.184425862 +0200
> @@ -665,6 +665,32 @@ static inline void list_splice_init_rcu(
>  		prefetch(rcu_dereference((pos))->next), (pos) != (head); \
>          	(pos) = (pos)->next)
> 
> +
> +/**
> + * list_for_each_entry_continue_rcu - continue iteration over rcu list
> + * @pos:	the type * to use as a loop cursor.
> + * @head:	the head for your list.
> + * @member:	the name of the list_struct within the struct.
> + *
> + * Continue to iterate over rcu list of given type, continuing after
> + * the current position.
> + *
> + * 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 rcu_read_lock().
> + *
> + * Note that the caller is responsible for making sure that
> + * the element remains in place between the earlier iterator
> + * and this one.  One way to do this is to ensure that
> + * both iterators are covered by the same rcu_read_lock(),
> + * while others involve reference counts, flags, or mutexes.
> + */
> +#define list_for_each_entry_continue_rcu(pos, head, member) \
> +	for ((pos) = list_entry((pos)->member.next, typeof(*pos), member); \
> +		prefetch(rcu_dereference((pos))->member.next), \
> +			 &pos->member != (head); \
> +        	(pos) = list_entry(pos->member.next, typeof(*pos), member))
> +
>  /*
>   * Double linked lists with a single pointer list head.
>   * Mostly useful for hash tables where the two pointer list head is
> 
> 

Re: [PATCH] list.h: add list_for_each_entry_continue_rcu

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 547 bytes --]

On Mon, 2007-09-10 at 10:39 -0700, Paul E. McKenney wrote:
> On Mon, Sep 10, 2007 at 02:05:47PM +0200, Johannes Berg wrote:
> > To implement the multicast list callback in mac80211 we need to
> > do partial list iteration. Since I want to convert the interface
> > list to an RCU list, I need a new list walking primitive:
> > list_for_each_entry_continue_rcu().

Hah. Turns out if I do the right thing with dev_mc_sync() I no longer
need this. Paul, do you want to push it to akpm or such? My bugfix no
longer relies on it.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

Re: [PATCH] list.h: add list_for_each_entry_continue_rcu

[Paul E. McKenney]

On Fri, Sep 14, 2007 at 11:14:58PM +0200, Johannes Berg wrote:
> On Mon, 2007-09-10 at 10:39 -0700, Paul E. McKenney wrote:
> > On Mon, Sep 10, 2007 at 02:05:47PM +0200, Johannes Berg wrote:
> > > To implement the multicast list callback in mac80211 we need to
> > > do partial list iteration. Since I want to convert the interface
> > > list to an RCU list, I need a new list walking primitive:
> > > list_for_each_entry_continue_rcu().
> 
> Hah. Turns out if I do the right thing with dev_mc_sync() I no longer
> need this. Paul, do you want to push it to akpm or such? My bugfix no
> longer relies on it.

OK, will push it when I convert list_for_each_continue_rcu().

						Thanx, Paul