[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().

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