rcu: Remove list_for_each_continue_rcu()
[linux-3.10.git] / include / linux / rculist.h
index c10b105..c92dd28 100644 (file)
 #include <linux/rcupdate.h>
 
 /*
+ * Why is there no list_empty_rcu()?  Because list_empty() serves this
+ * purpose.  The list_empty() function fetches the RCU-protected pointer
+ * and compares it to the address of the list head, but neither dereferences
+ * this pointer itself nor provides this pointer to the caller.  Therefore,
+ * it is not necessary to use rcu_dereference(), so that list_empty() can
+ * be used anywhere you would want to use a list_empty_rcu().
+ */
+
+/*
  * return the ->next pointer of a list_head in an rcu safe
  * way, we must not access it directly
  */
@@ -21,6 +30,7 @@
  * This is only for internal list manipulation where we know
  * the prev/next entries already!
  */
+#ifndef CONFIG_DEBUG_LIST
 static inline void __list_add_rcu(struct list_head *new,
                struct list_head *prev, struct list_head *next)
 {
@@ -29,6 +39,10 @@ static inline void __list_add_rcu(struct list_head *new,
        rcu_assign_pointer(list_next_rcu(prev), new);
        next->prev = new;
 }
+#else
+extern void __list_add_rcu(struct list_head *new,
+               struct list_head *prev, struct list_head *next);
+#endif
 
 /**
  * list_add_rcu - add a new entry to rcu-protected list
@@ -99,7 +113,7 @@ static inline void list_add_tail_rcu(struct list_head *new,
  */
 static inline void list_del_rcu(struct list_head *entry)
 {
-       __list_del(entry->prev, entry->next);
+       __list_del_entry(entry);
        entry->prev = LIST_POISON2;
 }
 
@@ -174,7 +188,7 @@ static inline void list_splice_init_rcu(struct list_head *list,
        struct list_head *last = list->prev;
        struct list_head *at = head->next;
 
-       if (list_empty(head))
+       if (list_empty(list))
                return;
 
        /* "first" and "last" tracking list, so initialize it. */
@@ -219,23 +233,43 @@ static inline void list_splice_init_rcu(struct list_head *list,
        })
 
 /**
- * list_first_entry_rcu - get the first element from a list
+ * Where are list_empty_rcu() and list_first_entry_rcu()?
+ *
+ * Implementing those functions following their counterparts list_empty() and
+ * list_first_entry() is not advisable because they lead to subtle race
+ * conditions as the following snippet shows:
+ *
+ * if (!list_empty_rcu(mylist)) {
+ *     struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
+ *     do_something(bar);
+ * }
+ *
+ * The list may not be empty when list_empty_rcu checks it, but it may be when
+ * list_first_entry_rcu rereads the ->next pointer.
+ *
+ * Rereading the ->next pointer is not a problem for list_empty() and
+ * list_first_entry() because they would be protected by a lock that blocks
+ * writers.
+ *
+ * See list_first_or_null_rcu for an alternative.
+ */
+
+/**
+ * list_first_or_null_rcu - get the first element from a list
  * @ptr:        the list head to take the element from.
  * @type:       the type of the struct this is embedded in.
  * @member:     the name of the list_struct within the struct.
  *
- * Note, that list is expected to be not empty.
+ * Note that if the list is empty, it returns NULL.
  *
  * This primitive may safely run concurrently with the _rcu list-mutation
  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
  */
-#define list_first_entry_rcu(ptr, type, member) \
-       list_entry_rcu((ptr)->next, type, member)
-
-#define __list_for_each_rcu(pos, head) \
-       for (pos = rcu_dereference_raw(list_next_rcu(head)); \
-               pos != (head); \
-               pos = rcu_dereference_raw(list_next_rcu((pos)))
+#define list_first_or_null_rcu(ptr, type, member) \
+       ({struct list_head *__ptr = (ptr); \
+         struct list_head __rcu *__next = list_next_rcu(__ptr); \
+         likely(__ptr != __next) ? container_of(__next, type, member) : NULL; \
+       })
 
 /**
  * list_for_each_entry_rcu     -       iterate over rcu list of given type
@@ -249,26 +283,9 @@ static inline void list_splice_init_rcu(struct list_head *list,
  */
 #define list_for_each_entry_rcu(pos, head, member) \
        for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
-               prefetch(pos->member.next), &pos->member != (head); \
+               &pos->member != (head); \
                pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 
-
-/**
- * list_for_each_continue_rcu
- * @pos:       the &struct list_head to use as a loop cursor.
- * @head:      the head for your list.
- *
- * Iterate over an rcu-protected list, continuing after current point.
- *
- * 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_continue_rcu(pos, head) \
-       for ((pos) = rcu_dereference_raw(list_next_rcu(pos)); \
-               prefetch((pos)->next), (pos) != (head); \
-               (pos) = rcu_dereference_raw(list_next_rcu(pos)))
-
 /**
  * list_for_each_entry_continue_rcu - continue iteration over list of given type
  * @pos:       the type * to use as a loop cursor.
@@ -280,7 +297,7 @@ static inline void list_splice_init_rcu(struct list_head *list,
  */
 #define list_for_each_entry_continue_rcu(pos, head, member)            \
        for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
-            prefetch(pos->member.next), &pos->member != (head);        \
+            &pos->member != (head);    \
             pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 
 /**
@@ -423,7 +440,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
 
 #define __hlist_for_each_rcu(pos, head)                                \
        for (pos = rcu_dereference(hlist_first_rcu(head));      \
-            pos && ({ prefetch(pos->next); 1; });              \
+            pos;                                               \
             pos = rcu_dereference(hlist_next_rcu(pos)))
 
 /**
@@ -439,7 +456,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  */
 #define hlist_for_each_entry_rcu(tpos, pos, head, member)              \
        for (pos = rcu_dereference_raw(hlist_first_rcu(head));          \
-               pos && ({ prefetch(pos->next); 1; }) &&                  \
+               pos &&                                                   \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
                pos = rcu_dereference_raw(hlist_next_rcu(pos)))
 
@@ -456,7 +473,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  */
 #define hlist_for_each_entry_rcu_bh(tpos, pos, head, member)            \
        for (pos = rcu_dereference_bh((head)->first);                    \
-               pos && ({ prefetch(pos->next); 1; }) &&                  \
+               pos &&                                                   \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
                pos = rcu_dereference_bh(pos->next))
 
@@ -468,7 +485,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  */
 #define hlist_for_each_entry_continue_rcu(tpos, pos, member)           \
        for (pos = rcu_dereference((pos)->next);                        \
-            pos && ({ prefetch(pos->next); 1; }) &&                    \
+            pos &&                                                     \
             ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });  \
             pos = rcu_dereference(pos->next))
 
@@ -480,7 +497,7 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  */
 #define hlist_for_each_entry_continue_rcu_bh(tpos, pos, member)                \
        for (pos = rcu_dereference_bh((pos)->next);                     \
-            pos && ({ prefetch(pos->next); 1; }) &&                    \
+            pos &&                                                     \
             ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });  \
             pos = rcu_dereference_bh(pos->next))