urcu/rculist.h

   1 #ifndef _KCOMPAT_RCULIST_H
   2 #define _KCOMPAT_RCULIST_H
   3
   4 /*
   5  * RCU-protected list version
   6  *
   7  * 2002-10-18 19:01:25-07:00, dipankar@in.ibm.com
   8  *  [PATCH] RCU helper patchset 2/2
   9  *
  10  *  This adds a set of list macros that make handling of list protected
  11  *  by RCU simpler. The interfaces added are -
  12  *
  13  *  list_add_rcu
  14  *  list_add_tail_rcu
  15  *        - Adds an element by taking care of memory barrier (wmb()).
  16  *
  17  *  list_del_rcu
  18  *        - Deletes an element but doesn't re-initialize the pointers in
  19  *          the element for supporting RCU based traversal.
  20  *
  21  *  list_for_each_rcu
  22  *  __list_for_each_rcu
  23  *        - Traversal of RCU protected list - takes care of memory barriers
  24  *          transparently.
  25  *
  26  */
  27
  28 #define _LGPL_SOURCE
  29 #include <urcu.h>
  30 #include <kcompat/list.h>
  31
  32 /*
  33  * Insert a new entry between two known consecutive entries.
  34  *
  35  * This is only for internal list manipulation where we know
  36  * the prev/next entries already!
  37  */
  38 static __inline__ void __list_add_rcu(struct list_head * new,
  39                                       struct list_head * prev,
  40                                       struct list_head * next)
  41 {
  42         new->next = next;
  43         new->prev = prev;
  44         smp_wmb();
  45         next->prev = new;
  46         prev->next = new;
  47 }
  48
  49 /**
  50  * list_add_rcu - add a new entry to rcu-protected list
  51  * @new: new entry to be added
  52  * @head: list head to add it after
  53  *
  54  * Insert a new entry after the specified head.
  55  * This is good for implementing stacks.
  56  *
  57  * The caller must take whatever precautions are necessary
  58  * (such as holding appropriate locks) to avoid racing
  59  * with another list-mutation primitive, such as list_add_rcu()
  60  * or list_del_rcu(), running on this same list.
  61  * However, it is perfectly legal to run concurrently with
  62  * the _rcu list-traversal primitives, such as
  63  * list_for_each_entry_rcu().
  64  */
  65 static __inline__ void list_add_rcu(struct list_head *new,
  66                                     struct list_head *head)
  67 {
  68         __list_add_rcu(new, head, head->next);
  69 }
  70
  71 /**
  72  * list_add_tail_rcu - add a new entry to rcu-protected list
  73  * @new: new entry to be added
  74  * @head: list head to add it before
  75  *
  76  * Insert a new entry before the specified head.
  77  * This is useful for implementing queues.
  78  *
  79  * The caller must take whatever precautions are necessary
  80  * (such as holding appropriate locks) to avoid racing
  81  * with another list-mutation primitive, such as list_add_tail_rcu()
  82  * or list_del_rcu(), running on this same list.
  83  * However, it is perfectly legal to run concurrently with
  84  * the _rcu list-traversal primitives, such as
  85  * list_for_each_entry_rcu().
  86  */
  87 static __inline__ void list_add_tail_rcu(struct list_head *new,
  88                                          struct list_head *head)
  89 {
  90         __list_add_rcu(new, head->prev, head);
  91 }
  92
  93 /**
  94  * list_del_rcu - deletes entry from list without re-initialization
  95  * @entry: the element to delete from the list.
  96  *
  97  * Note: list_empty on entry does not return true after this,
  98  * the entry is in an undefined state. It is useful for RCU based
  99  * lockfree traversal.
 100  *
 101  * The caller must take whatever precautions are necessary
 102  * (such as holding appropriate locks) to avoid racing
 103  * with another list-mutation primitive, such as list_del_rcu()
 104  * or list_add_rcu(), running on this same list.
 105  * However, it is perfectly legal to run concurrently with
 106  * the _rcu list-traversal primitives, such as
 107  * list_for_each_entry_rcu().
 108  *
 109  * Note that the caller is not permitted to immediately free
 110  * the newly deleted entry.  Instead, either synchronize_kernel()
 111  * or call_rcu() must be used to defer freeing until an RCU
 112  * grace period has elapsed.
 113  */
 114 static inline void list_del_rcu(struct list_head *entry)
 115 {
 116         __list_del(entry->prev, entry->next);
 117 }
 118
 119 /**
 120  * list_for_each_rcu    -       iterate over an rcu-protected list
 121  * @pos:        the &struct list_head to use as a loop counter.
 122  * @head:       the head for your list.
 123  *
 124  * This list-traversal primitive may safely run concurrently with
 125  * the _rcu list-mutation primitives such as list_add_rcu()
 126  * as long as the traversal is guarded by rcu_read_lock().
 127  */
 128 #define list_for_each_rcu(pos, head)                                    \
 129         for (pos = rcu_dereference((head)->next);                       \
 130              prefetch(pos->next), pos != (head);                        \
 131              pos = rcu_dereference(pos->next))
 132
 133 #define __list_for_each_rcu(pos, head)                                  \
 134         for (pos = rcu_dereference((head)->next);                       \
 135              pos != (head);                                             \
 136              pos = rcu_dereference(pos->next))
 137
 138 /**
 139  * list_for_each_entry_rcu - iterate over a rcu-protected list
 140  * @pos: the struct type pointer to use as a loop counter
 141  * @head: the head for your list
 142  * @member: the name of the struct list_head element in your struct type
 143  *
 144  * This list-traversal primitive may safely run concurrently with
 145  * the _rcu list-mutation primitives such as list_add_rcu()
 146  * as long as the traversal is guarded by rcu_read_lock().
 147  */
 148 #define list_for_each_entry_rcu(pos, head, member)                      \
 149         for (pos = list_entry(rcu_dereference((head)->next), typeof(*pos), \
 150                               member);                                  \
 151              prefetch(pos->member.next), &pos->member != (head);        \
 152              pos = list_entry(rcu_dereference(pos->member.next),typeof(*pos), \
 153                               member))
 154
 155 #endif /* _KCOMPAT_RCULIST_H */