Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
llist.h
Go to the documentation of this file.
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 handlers. So code that uses the list in
39  * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
40  *
41  * Copyright 2010,2011 Intel Corp.
42  * Author: Huang Ying <[email protected]>
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/cmpxchg.h>
60 
61 struct llist_head {
62  struct llist_node *first;
63 };
64 
65 struct llist_node {
66  struct llist_node *next;
67 };
68 
69 #define LLIST_HEAD_INIT(name) { NULL }
70 #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name)
71 
76 static inline void init_llist_head(struct llist_head *list)
77 {
78  list->first = NULL;
79 }
80 
87 #define llist_entry(ptr, type, member) \
88  container_of(ptr, type, member)
89 
104 #define llist_for_each(pos, node) \
105  for ((pos) = (node); pos; (pos) = (pos)->next)
106 
122 #define llist_for_each_entry(pos, node, member) \
123  for ((pos) = llist_entry((node), typeof(*(pos)), member); \
124  &(pos)->member != NULL; \
125  (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
126 
135 static inline bool llist_empty(const struct llist_head *head)
136 {
137  return ACCESS_ONCE(head->first) == NULL;
138 }
139 
140 static inline struct llist_node *llist_next(struct llist_node *node)
141 {
142  return node->next;
143 }
144 
152 static inline bool llist_add(struct llist_node *new, struct llist_head *head)
153 {
154  struct llist_node *entry, *old_entry;
155 
156  entry = head->first;
157  for (;;) {
158  old_entry = entry;
159  new->next = entry;
160  entry = cmpxchg(&head->first, old_entry, new);
161  if (entry == old_entry)
162  break;
163  }
164 
165  return old_entry == NULL;
166 }
167 
176 static inline struct llist_node *llist_del_all(struct llist_head *head)
177 {
178  return xchg(&head->first, NULL);
179 }
180 
181 extern bool llist_add_batch(struct llist_node *new_first,
182  struct llist_node *new_last,
183  struct llist_head *head);
184 extern struct llist_node *llist_del_first(struct llist_head *head);
185 
186 #endif /* LLIST_H */