BKL: remove extraneous #include <smp_lock.h>
[linux-3.10.git] / include / linux / rculist.h
index aa9b3eb..f31ef61 100644 (file)
@@ -7,6 +7,22 @@
  * RCU-protected list version
  */
 #include <linux/list.h>
+#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
+ */
+#define list_next_rcu(list)    (*((struct list_head __rcu **)(&(list)->next)))
 
 /*
  * Insert a new entry between two known consecutive entries.
@@ -19,9 +35,8 @@ static inline void __list_add_rcu(struct list_head *new,
 {
        new->next = next;
        new->prev = prev;
-       smp_wmb();
+       rcu_assign_pointer(list_next_rcu(prev), new);
        next->prev = new;
-       prev->next = new;
 }
 
 /**
@@ -98,6 +113,34 @@ static inline void list_del_rcu(struct list_head *entry)
 }
 
 /**
+ * hlist_del_init_rcu - deletes entry from hash list with re-initialization
+ * @n: the element to delete from the hash list.
+ *
+ * Note: list_unhashed() on the node return true after this. It is
+ * useful for RCU based read lockfree traversal if the writer side
+ * must know if the list entry is still hashed or already unhashed.
+ *
+ * In particular, it means that we can not poison the forward pointers
+ * that may still be used for walking the hash list and we can only
+ * zero the pprev pointer so list_unhashed() will return true after
+ * this.
+ *
+ * The caller must take whatever precautions are necessary (such as
+ * holding appropriate locks) to avoid racing with another
+ * list-mutation primitive, such as hlist_add_head_rcu() or
+ * hlist_del_rcu(), running on this same list.  However, it is
+ * perfectly legal to run concurrently with the _rcu list-traversal
+ * primitives, such as hlist_for_each_entry_rcu().
+ */
+static inline void hlist_del_init_rcu(struct hlist_node *n)
+{
+       if (!hlist_unhashed(n)) {
+               __hlist_del(n);
+               n->pprev = NULL;
+       }
+}
+
+/**
  * list_replace_rcu - replace old entry by new one
  * @old : the element to be replaced
  * @new : the new element to insert
@@ -110,9 +153,8 @@ static inline void list_replace_rcu(struct list_head *old,
 {
        new->next = old->next;
        new->prev = old->prev;
-       smp_wmb();
+       rcu_assign_pointer(list_next_rcu(new->prev), new);
        new->next->prev = new;
-       new->prev->next = new;
        old->prev = LIST_POISON2;
 }
 
@@ -166,47 +208,43 @@ static inline void list_splice_init_rcu(struct list_head *list,
         */
 
        last->next = at;
-       smp_wmb();
-       head->next = first;
+       rcu_assign_pointer(list_next_rcu(head), first);
        first->prev = head;
        at->prev = last;
 }
 
 /**
- * list_for_each_rcu   -       iterate over an rcu-protected list
- * @pos:       the &struct list_head to use as a loop cursor.
- * @head:      the head for your list.
+ * list_entry_rcu - get the struct for this entry
+ * @ptr:        the &struct list_head pointer.
+ * @type:       the type of the struct this is embedded in.
+ * @member:     the name of the list_struct within the struct.
  *
- * 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().
+ * 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_for_each_rcu(pos, head) \
-       for (pos = (head)->next; \
-               prefetch(rcu_dereference(pos)->next), pos != (head); \
-               pos = pos->next)
-
-#define __list_for_each_rcu(pos, head) \
-       for (pos = (head)->next; \
-               rcu_dereference(pos) != (head); \
-               pos = pos->next)
+#define list_entry_rcu(ptr, type, member) \
+       ({typeof (*ptr) __rcu *__ptr = (typeof (*ptr) __rcu __force *)ptr; \
+        container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \
+       })
 
 /**
- * list_for_each_safe_rcu
- * @pos:       the &struct list_head to use as a loop cursor.
- * @n:         another &struct list_head to use as temporary storage
- * @head:      the head for your list.
+ * list_first_entry_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.
  *
- * Iterate over an rcu-protected list, safe against removal of list entry.
+ * Note, that list is expected to be not empty.
  *
- * 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().
+ * 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_for_each_safe_rcu(pos, n, head) \
-       for (pos = (head)->next; \
-               n = rcu_dereference(pos)->next, pos != (head); \
-               pos = n)
+#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)))
 
 /**
  * list_for_each_entry_rcu     -       iterate over rcu list of given type
@@ -219,10 +257,9 @@ static inline void list_splice_init_rcu(struct list_head *list,
  * as long as the traversal is guarded by rcu_read_lock().
  */
 #define list_for_each_entry_rcu(pos, head, member) \
-       for (pos = list_entry((head)->next, typeof(*pos), member); \
-               prefetch(rcu_dereference(pos)->member.next), \
-                       &pos->member != (head); \
-               pos = list_entry(pos->member.next, typeof(*pos), member))
+       for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
+               prefetch(pos->member.next), &pos->member != (head); \
+               pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 
 
 /**
@@ -237,9 +274,23 @@ static inline void list_splice_init_rcu(struct list_head *list,
  * as long as the traversal is guarded by rcu_read_lock().
  */
 #define list_for_each_continue_rcu(pos, head) \
-       for ((pos) = (pos)->next; \
-               prefetch(rcu_dereference((pos))->next), (pos) != (head); \
-               (pos) = (pos)->next)
+       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.
+ * @head:      the head for your list.
+ * @member:    the name of the list_struct within the struct.
+ *
+ * Continue to iterate over list of given type, continuing after
+ * the current position.
+ */
+#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 = list_entry_rcu(pos->member.next, typeof(*pos), member))
 
 /**
  * hlist_del_rcu - deletes entry from hash list without re-initialization
@@ -280,13 +331,19 @@ static inline void hlist_replace_rcu(struct hlist_node *old,
 
        new->next = next;
        new->pprev = old->pprev;
-       smp_wmb();
+       rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
        if (next)
                new->next->pprev = &new->next;
-       *new->pprev = new;
        old->pprev = LIST_POISON2;
 }
 
+/*
+ * return the first or the next element in an RCU protected hlist
+ */
+#define hlist_first_rcu(head)  (*((struct hlist_node __rcu **)(&(head)->first)))
+#define hlist_next_rcu(node)   (*((struct hlist_node __rcu **)(&(node)->next)))
+#define hlist_pprev_rcu(node)  (*((struct hlist_node __rcu **)((node)->pprev)))
+
 /**
  * hlist_add_head_rcu
  * @n: the element to add to the hash list.
@@ -310,12 +367,12 @@ static inline void hlist_add_head_rcu(struct hlist_node *n,
                                        struct hlist_head *h)
 {
        struct hlist_node *first = h->first;
+
        n->next = first;
        n->pprev = &h->first;
-       smp_wmb();
+       rcu_assign_pointer(hlist_first_rcu(h), n);
        if (first)
                first->pprev = &n->next;
-       h->first = n;
 }
 
 /**
@@ -341,9 +398,8 @@ static inline void hlist_add_before_rcu(struct hlist_node *n,
 {
        n->pprev = next->pprev;
        n->next = next;
-       smp_wmb();
+       rcu_assign_pointer(hlist_pprev_rcu(n), n);
        next->pprev = &n->next;
-       *(n->pprev) = n;
 }
 
 /**
@@ -369,12 +425,16 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
 {
        n->next = prev->next;
        n->pprev = &prev->next;
-       smp_wmb();
-       prev->next = n;
+       rcu_assign_pointer(hlist_next_rcu(prev), n);
        if (n->next)
                n->next->pprev = &n->next;
 }
 
+#define __hlist_for_each_rcu(pos, head)                                \
+       for (pos = rcu_dereference(hlist_first_rcu(head));      \
+            pos && ({ prefetch(pos->next); 1; });              \
+            pos = rcu_dereference(hlist_next_rcu(pos)))
+
 /**
  * hlist_for_each_entry_rcu - iterate over rcu list of given type
  * @tpos:      the type * to use as a loop cursor.
@@ -386,11 +446,53 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
  * as long as the traversal is guarded by rcu_read_lock().
  */
-#define hlist_for_each_entry_rcu(tpos, pos, head, member)               \
-       for (pos = (head)->first;                                        \
-            rcu_dereference(pos) && ({ prefetch(pos->next); 1; }) &&    \
+#define hlist_for_each_entry_rcu(tpos, pos, head, member)              \
+       for (pos = rcu_dereference_raw(hlist_first_rcu(head));          \
+               pos && ({ prefetch(pos->next); 1; }) &&                  \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
-            pos = pos->next)
+               pos = rcu_dereference_raw(hlist_next_rcu(pos)))
+
+/**
+ * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
+ * @tpos:      the type * to use as a loop cursor.
+ * @pos:       the &struct hlist_node to use as a loop cursor.
+ * @head:      the head for your list.
+ * @member:    the name of the hlist_node within the struct.
+ *
+ * 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 rcu_read_lock().
+ */
+#define hlist_for_each_entry_rcu_bh(tpos, pos, head, member)            \
+       for (pos = rcu_dereference_bh((head)->first);                    \
+               pos && ({ prefetch(pos->next); 1; }) &&                  \
+               ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
+               pos = rcu_dereference_bh(pos->next))
+
+/**
+ * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
+ * @tpos:      the type * to use as a loop cursor.
+ * @pos:       the &struct hlist_node to use as a loop cursor.
+ * @member:    the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry_continue_rcu(tpos, pos, member)           \
+       for (pos = rcu_dereference((pos)->next);                        \
+            pos && ({ prefetch(pos->next); 1; }) &&                    \
+            ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });  \
+            pos = rcu_dereference(pos->next))
+
+/**
+ * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
+ * @tpos:      the type * to use as a loop cursor.
+ * @pos:       the &struct hlist_node to use as a loop cursor.
+ * @member:    the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry_continue_rcu_bh(tpos, pos, member)                \
+       for (pos = rcu_dereference_bh((pos)->next);                     \
+            pos && ({ prefetch(pos->next); 1; }) &&                    \
+            ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });  \
+            pos = rcu_dereference_bh(pos->next))
+
 
 #endif /* __KERNEL__ */
 #endif