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