Added support for RHEL6.5
[compat-rdma/compat.git] / include / linux / llist.h
1 #include <linux/version.h>
2 #if (LINUX_VERSION_CODE >= KERNEL_VERSION(3,2,0))
3 #include_next <linux/llist.h>
4
5 #elif (LINUX_VERSION_CODE >= KERNEL_VERSION(3,1,0))
6 #include_next <linux/llist.h>
7 #define llist_add_batch LINUX_BACKPORT(llist_add_batch)
8 extern bool llist_add_batch(struct llist_node *new_first,
9                             struct llist_node *new_last,
10                             struct llist_head *head);
11 #define llist_del_first LINUX_BACKPORT(llist_del_first)
12 extern struct llist_node *llist_del_first(struct llist_head *head);
13 #else
14
15 #if (defined(CONFIG_COMPAT_SLES_11_2) || defined(CONFIG_COMPAT_SLES_11_3))
16 #include_next <linux/llist.h>
17 #else
18
19 #ifndef LLIST_H
20 #define LLIST_H
21 /*
22  * Lock-less NULL terminated single linked list
23  *
24  * If there are multiple producers and multiple consumers, llist_add
25  * can be used in producers and llist_del_all can be used in
26  * consumers.  They can work simultaneously without lock.  But
27  * llist_del_first can not be used here.  Because llist_del_first
28  * depends on list->first->next does not changed if list->first is not
29  * changed during its operation, but llist_del_first, llist_add,
30  * llist_add (or llist_del_all, llist_add, llist_add) sequence in
31  * another consumer may violate that.
32  *
33  * If there are multiple producers and one consumer, llist_add can be
34  * used in producers and llist_del_all or llist_del_first can be used
35  * in the consumer.
36  *
37  * This can be summarized as follow:
38  *
39  *           |   add    | del_first |  del_all
40  * add       |    -     |     -     |     -
41  * del_first |          |     L     |     L
42  * del_all   |          |           |     -
43  *
44  * Where "-" stands for no lock is needed, while "L" stands for lock
45  * is needed.
46  *
47  * The list entries deleted via llist_del_all can be traversed with
48  * traversing function such as llist_for_each etc.  But the list
49  * entries can not be traversed safely before deleted from the list.
50  * The order of deleted entries is from the newest to the oldest added
51  * one.  If you want to traverse from the oldest to the newest, you
52  * must reverse the order by yourself before traversing.
53  *
54  * The basic atomic operation of this list is cmpxchg on long.  On
55  * architectures that don't have NMI-safe cmpxchg implementation, the
56  * list can NOT be used in NMI handlers.  So code that uses the list in
57  * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
58  *
59  * Copyright 2010,2011 Intel Corp.
60  *   Author: Huang Ying <ying.huang@intel.com>
61  *
62  * This program is free software; you can redistribute it and/or
63  * modify it under the terms of the GNU General Public License version
64  * 2 as published by the Free Software Foundation;
65  *
66  * This program is distributed in the hope that it will be useful,
67  * but WITHOUT ANY WARRANTY; without even the implied warranty of
68  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
69  * GNU General Public License for more details.
70  *
71  * You should have received a copy of the GNU General Public License
72  * along with this program; if not, write to the Free Software
73  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
74  */
75
76 #include <linux/kernel.h>
77 #include <asm/system.h>
78 #include <asm/processor.h>
79
80 struct llist_head {
81         struct llist_node *first;
82 };
83
84 struct llist_node {
85         struct llist_node *next;
86 };
87
88 #define LLIST_HEAD_INIT(name)   { NULL }
89 #define LLIST_HEAD(name)        struct llist_head name = LLIST_HEAD_INIT(name)
90
91 /**
92  * init_llist_head - initialize lock-less list head
93  * @head:       the head for your lock-less list
94  */
95 #define init_llist_head LINUX_BACKPORT(init_llist_head)
96 static inline void init_llist_head(struct llist_head *list)
97 {
98         list->first = NULL;
99 }
100
101 /**
102  * llist_entry - get the struct of this entry
103  * @ptr:        the &struct llist_node pointer.
104  * @type:       the type of the struct this is embedded in.
105  * @member:     the name of the llist_node within the struct.
106  */
107 #ifndef llist_entry
108 #define llist_entry(ptr, type, member)          \
109         container_of(ptr, type, member)
110 #endif
111
112 /**
113  * llist_for_each - iterate over some deleted entries of a lock-less list
114  * @pos:        the &struct llist_node to use as a loop cursor
115  * @node:       the first entry of deleted list entries
116  *
117  * In general, some entries of the lock-less list can be traversed
118  * safely only after being deleted from list, so start with an entry
119  * instead of list head.
120  *
121  * If being used on entries deleted from lock-less list directly, the
122  * traverse order is from the newest to the oldest added entry.  If
123  * you want to traverse from the oldest to the newest, you must
124  * reverse the order by yourself before traversing.
125  */
126 #ifndef llist_for_each
127 #define llist_for_each(pos, node)                       \
128         for ((pos) = (node); pos; (pos) = (pos)->next)
129 #endif
130
131 /**
132  * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type
133  * @pos:        the type * to use as a loop cursor.
134  * @node:       the fist entry of deleted list entries.
135  * @member:     the name of the llist_node with the struct.
136  *
137  * In general, some entries of the lock-less list can be traversed
138  * safely only after being removed from list, so start with an entry
139  * instead of list head.
140  *
141  * If being used on entries deleted from lock-less list directly, the
142  * traverse order is from the newest to the oldest added entry.  If
143  * you want to traverse from the oldest to the newest, you must
144  * reverse the order by yourself before traversing.
145  */
146 #ifndef llist_for_each_entry
147 #define llist_for_each_entry(pos, node, member)                         \
148         for ((pos) = llist_entry((node), typeof(*(pos)), member);       \
149              &(pos)->member != NULL;                                    \
150              (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
151 #endif
152
153 /**
154  * llist_empty - tests whether a lock-less list is empty
155  * @head:       the list to test
156  *
157  * Not guaranteed to be accurate or up to date.  Just a quick way to
158  * test whether the list is empty without deleting something from the
159  * list.
160  */
161 #define llist_empty LINUX_BACKPORT(llist_empty)
162 static inline bool llist_empty(const struct llist_head *head)
163 {
164         return ACCESS_ONCE(head->first) == NULL;
165 }
166
167 #define llist_next LINUX_BACKPORT(llist_next)
168 static inline struct llist_node *llist_next(struct llist_node *node)
169 {
170         return node->next;
171 }
172
173 /**
174  * llist_add - add a new entry
175  * @new:        new entry to be added
176  * @head:       the head for your lock-less list
177  *
178  * Returns true if the list was empty prior to adding this entry.
179  */
180 #define llist_add LINUX_BACKPORT(llist_add)
181 static inline bool llist_add(struct llist_node *new, struct llist_head *head)
182 {
183         struct llist_node *entry, *old_entry;
184
185         entry = head->first;
186         for (;;) {
187                 old_entry = entry;
188                 new->next = entry;
189                 entry = cmpxchg(&head->first, old_entry, new);
190                 if (entry == old_entry)
191                         break;
192         }
193
194         return old_entry == NULL;
195 }
196
197 /**
198  * llist_del_all - delete all entries from lock-less list
199  * @head:       the head of lock-less list to delete all entries
200  *
201  * If list is empty, return NULL, otherwise, delete all entries and
202  * return the pointer to the first entry.  The order of entries
203  * deleted is from the newest to the oldest added one.
204  */
205 #define llist_del_all LINUX_BACKPORT(llist_del_all)
206 static inline struct llist_node *llist_del_all(struct llist_head *head)
207 {
208         return xchg(&head->first, NULL);
209 }
210
211 #define llist_add_batch LINUX_BACKPORT(llist_add_batch)
212 extern bool llist_add_batch(struct llist_node *new_first,
213                             struct llist_node *new_last,
214                             struct llist_head *head);
215
216 #define llist_del_first LINUX_BACKPORT(llist_del_first)
217 extern struct llist_node *llist_del_first(struct llist_head *head);
218
219 #endif /* (defined(CONFIG_COMPAT_SLES_11_2) || defined(CONFIG_COMPAT_SLES_11_3)) */
220 #endif /* LLIST_H */
221 #endif /* (LINUX_VERSION_CODE >= KERNEL_VERSION(3,2,0) */