1 /* SPDX-License-Identifier: GPL-2.0-only */
2 #ifndef LLIST_H
3 #define LLIST_H
4 /*
5  * Lock-less NULL terminated single linked list
6  *
7  * Cases where locking is not needed:
8  * If there are multiple producers and multiple consumers, llist_add can be
9  * used in producers and llist_del_all can be used in consumers simultaneously
10  * without locking. Also a single consumer can use llist_del_first while
11  * multiple producers simultaneously use llist_add, without any locking.
12  *
13  * Cases where locking is needed:
14  * If we have multiple consumers with llist_del_first used in one consumer, and
15  * llist_del_first or llist_del_all used in other consumers, then a lock is
16  * needed.  This is because llist_del_first depends on list->first->next not
17  * changing, but without lock protection, there's no way to be sure about that
18  * if a preemption happens in the middle of the delete operation and on being
19  * preempted back, the list->first is the same as before causing the cmpxchg in
20  * llist_del_first to succeed. For example, while a llist_del_first operation
21  * is in progress in one consumer, then a llist_del_first, llist_add,
22  * llist_add (or llist_del_all, llist_add, llist_add) sequence in another
23  * consumer may cause violations.
24  *
25  * This can be summarized as follows:
26  *
27  *           |   add    | del_first |  del_all
28  * add       |    -     |     -     |     -
29  * del_first |          |     L     |     L
30  * del_all   |          |           |     -
31  *
32  * Where, a particular row's operation can happen concurrently with a column's
33  * operation, with "-" being no lock needed, while "L" being lock is needed.
34  *
35  * The list entries deleted via llist_del_all can be traversed with
36  * traversing function such as llist_for_each etc.  But the list
37  * entries can not be traversed safely before deleted from the list.
38  * The order of deleted entries is from the newest to the oldest added
39  * one.  If you want to traverse from the oldest to the newest, you
40  * must reverse the order by yourself before traversing.
41  *
42  * The basic atomic operation of this list is cmpxchg on long.  On
43  * architectures that don't have NMI-safe cmpxchg implementation, the
44  * list can NOT be used in NMI handlers.  So code that uses the list in
45  * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
46  *
47  * Copyright 2010,2011 Intel Corp.
48  *   Author: Huang Ying <ying.huang@intel.com>
49  */
50 
51 #include <linux/atomic.h>
52 #include <linux/container_of.h>
53 #include <linux/stddef.h>
54 #include <linux/types.h>
55 
56 struct llist_head {
57 	struct llist_node *first;
58 };
59 
60 struct llist_node {
61 	struct llist_node *next;
62 };
63 
64 #define LLIST_HEAD_INIT(name)	{ NULL }
65 #define LLIST_HEAD(name)	struct llist_head name = LLIST_HEAD_INIT(name)
66 
67 /**
68  * init_llist_head - initialize lock-less list head
69  * @head:	the head for your lock-less list
70  */
init_llist_head(struct llist_head * list)71 static inline void init_llist_head(struct llist_head *list)
72 {
73 	list->first = NULL;
74 }
75 
76 /**
77  * llist_entry - get the struct of this entry
78  * @ptr:	the &struct llist_node pointer.
79  * @type:	the type of the struct this is embedded in.
80  * @member:	the name of the llist_node within the struct.
81  */
82 #define llist_entry(ptr, type, member)		\
83 	container_of(ptr, type, member)
84 
85 /**
86  * member_address_is_nonnull - check whether the member address is not NULL
87  * @ptr:	the object pointer (struct type * that contains the llist_node)
88  * @member:	the name of the llist_node within the struct.
89  *
90  * This macro is conceptually the same as
91  *	&ptr->member != NULL
92  * but it works around the fact that compilers can decide that taking a member
93  * address is never a NULL pointer.
94  *
95  * Real objects that start at a high address and have a member at NULL are
96  * unlikely to exist, but such pointers may be returned e.g. by the
97  * container_of() macro.
98  */
99 #define member_address_is_nonnull(ptr, member)	\
100 	((uintptr_t)(ptr) + offsetof(typeof(*(ptr)), member) != 0)
101 
102 /**
103  * llist_for_each - iterate over some deleted entries of a lock-less list
104  * @pos:	the &struct llist_node to use as a loop cursor
105  * @node:	the first entry of deleted list entries
106  *
107  * In general, some entries of the lock-less list can be traversed
108  * safely only after being deleted from list, so start with an entry
109  * instead of list head.
110  *
111  * If being used on entries deleted from lock-less list directly, the
112  * traverse order is from the newest to the oldest added entry.  If
113  * you want to traverse from the oldest to the newest, you must
114  * reverse the order by yourself before traversing.
115  */
116 #define llist_for_each(pos, node)			\
117 	for ((pos) = (node); pos; (pos) = (pos)->next)
118 
119 /**
120  * llist_for_each_safe - iterate over some deleted entries of a lock-less list
121  *			 safe against removal of list entry
122  * @pos:	the &struct llist_node to use as a loop cursor
123  * @n:		another &struct llist_node to use as temporary storage
124  * @node:	the first entry of deleted list entries
125  *
126  * In general, some entries of the lock-less list can be traversed
127  * safely only after being deleted from list, so start with an entry
128  * instead of list head.
129  *
130  * If being used on entries deleted from lock-less list directly, the
131  * traverse order is from the newest to the oldest added entry.  If
132  * you want to traverse from the oldest to the newest, you must
133  * reverse the order by yourself before traversing.
134  */
135 #define llist_for_each_safe(pos, n, node)			\
136 	for ((pos) = (node); (pos) && ((n) = (pos)->next, true); (pos) = (n))
137 
138 /**
139  * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type
140  * @pos:	the type * to use as a loop cursor.
141  * @node:	the fist entry of deleted list entries.
142  * @member:	the name of the llist_node with the struct.
143  *
144  * In general, some entries of the lock-less list can be traversed
145  * safely only after being removed from list, so start with an entry
146  * instead of list head.
147  *
148  * If being used on entries deleted from lock-less list directly, the
149  * traverse order is from the newest to the oldest added entry.  If
150  * you want to traverse from the oldest to the newest, you must
151  * reverse the order by yourself before traversing.
152  */
153 #define llist_for_each_entry(pos, node, member)				\
154 	for ((pos) = llist_entry((node), typeof(*(pos)), member);	\
155 	     member_address_is_nonnull(pos, member);			\
156 	     (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
157 
158 /**
159  * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type
160  *			       safe against removal of list entry
161  * @pos:	the type * to use as a loop cursor.
162  * @n:		another type * to use as temporary storage
163  * @node:	the first entry of deleted list entries.
164  * @member:	the name of the llist_node with the struct.
165  *
166  * In general, some entries of the lock-less list can be traversed
167  * safely only after being removed from list, so start with an entry
168  * instead of list head.
169  *
170  * If being used on entries deleted from lock-less list directly, the
171  * traverse order is from the newest to the oldest added entry.  If
172  * you want to traverse from the oldest to the newest, you must
173  * reverse the order by yourself before traversing.
174  */
175 #define llist_for_each_entry_safe(pos, n, node, member)			       \
176 	for (pos = llist_entry((node), typeof(*pos), member);		       \
177 	     member_address_is_nonnull(pos, member) &&			       \
178 	        (n = llist_entry(pos->member.next, typeof(*n), member), true); \
179 	     pos = n)
180 
181 /**
182  * llist_empty - tests whether a lock-less list is empty
183  * @head:	the list to test
184  *
185  * Not guaranteed to be accurate or up to date.  Just a quick way to
186  * test whether the list is empty without deleting something from the
187  * list.
188  */
llist_empty(const struct llist_head * head)189 static inline bool llist_empty(const struct llist_head *head)
190 {
191 	return READ_ONCE(head->first) == NULL;
192 }
193 
llist_next(struct llist_node * node)194 static inline struct llist_node *llist_next(struct llist_node *node)
195 {
196 	return node->next;
197 }
198 
199 extern bool llist_add_batch(struct llist_node *new_first,
200 			    struct llist_node *new_last,
201 			    struct llist_head *head);
202 
__llist_add_batch(struct llist_node * new_first,struct llist_node * new_last,struct llist_head * head)203 static inline bool __llist_add_batch(struct llist_node *new_first,
204 				     struct llist_node *new_last,
205 				     struct llist_head *head)
206 {
207 	new_last->next = head->first;
208 	head->first = new_first;
209 	return new_last->next == NULL;
210 }
211 
212 /**
213  * llist_add - add a new entry
214  * @new:	new entry to be added
215  * @head:	the head for your lock-less list
216  *
217  * Returns true if the list was empty prior to adding this entry.
218  */
llist_add(struct llist_node * new,struct llist_head * head)219 static inline bool llist_add(struct llist_node *new, struct llist_head *head)
220 {
221 	return llist_add_batch(new, new, head);
222 }
223 
__llist_add(struct llist_node * new,struct llist_head * head)224 static inline bool __llist_add(struct llist_node *new, struct llist_head *head)
225 {
226 	return __llist_add_batch(new, new, head);
227 }
228 
229 /**
230  * llist_del_all - delete all entries from lock-less list
231  * @head:	the head of lock-less list to delete all entries
232  *
233  * If list is empty, return NULL, otherwise, delete all entries and
234  * return the pointer to the first entry.  The order of entries
235  * deleted is from the newest to the oldest added one.
236  */
llist_del_all(struct llist_head * head)237 static inline struct llist_node *llist_del_all(struct llist_head *head)
238 {
239 	return xchg(&head->first, NULL);
240 }
241 
__llist_del_all(struct llist_head * head)242 static inline struct llist_node *__llist_del_all(struct llist_head *head)
243 {
244 	struct llist_node *first = head->first;
245 
246 	head->first = NULL;
247 	return first;
248 }
249 
250 extern struct llist_node *llist_del_first(struct llist_head *head);
251 
252 struct llist_node *llist_reverse_order(struct llist_node *head);
253 
254 #endif /* LLIST_H */
255