1#ifndef _LINUX_RCULIST_H
2#define _LINUX_RCULIST_H
3
4#ifdef __KERNEL__
5
6/*
7 * RCU-protected list version
8 */
9#include <linux/list.h>
10#include <linux/rcupdate.h>
11
12/*
13 * Why is there no list_empty_rcu()?  Because list_empty() serves this
14 * purpose.  The list_empty() function fetches the RCU-protected pointer
15 * and compares it to the address of the list head, but neither dereferences
16 * this pointer itself nor provides this pointer to the caller.  Therefore,
17 * it is not necessary to use rcu_dereference(), so that list_empty() can
18 * be used anywhere you would want to use a list_empty_rcu().
19 */
20
21/*
22 * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
23 * @list: list to be initialized
24 *
25 * You should instead use INIT_LIST_HEAD() for normal initialization and
26 * cleanup tasks, when readers have no access to the list being initialized.
27 * However, if the list being initialized is visible to readers, you
28 * need to keep the compiler from being too mischievous.
29 */
30static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
31{
32	ACCESS_ONCE(list->next) = list;
33	ACCESS_ONCE(list->prev) = list;
34}
35
36/*
37 * return the ->next pointer of a list_head in an rcu safe
38 * way, we must not access it directly
39 */
40#define list_next_rcu(list)	(*((struct list_head __rcu **)(&(list)->next)))
41
42/*
43 * Insert a new entry between two known consecutive entries.
44 *
45 * This is only for internal list manipulation where we know
46 * the prev/next entries already!
47 */
48#ifndef CONFIG_DEBUG_LIST
49static inline void __list_add_rcu(struct list_head *new,
50		struct list_head *prev, struct list_head *next)
51{
52	new->next = next;
53	new->prev = prev;
54	rcu_assign_pointer(list_next_rcu(prev), new);
55	next->prev = new;
56}
57#else
58void __list_add_rcu(struct list_head *new,
59		    struct list_head *prev, struct list_head *next);
60#endif
61
62/**
63 * list_add_rcu - add a new entry to rcu-protected list
64 * @new: new entry to be added
65 * @head: list head to add it after
66 *
67 * Insert a new entry after the specified head.
68 * This is good for implementing stacks.
69 *
70 * The caller must take whatever precautions are necessary
71 * (such as holding appropriate locks) to avoid racing
72 * with another list-mutation primitive, such as list_add_rcu()
73 * or list_del_rcu(), running on this same list.
74 * However, it is perfectly legal to run concurrently with
75 * the _rcu list-traversal primitives, such as
76 * list_for_each_entry_rcu().
77 */
78static inline void list_add_rcu(struct list_head *new, struct list_head *head)
79{
80	__list_add_rcu(new, head, head->next);
81}
82
83/**
84 * list_add_tail_rcu - add a new entry to rcu-protected list
85 * @new: new entry to be added
86 * @head: list head to add it before
87 *
88 * Insert a new entry before the specified head.
89 * This is useful for implementing queues.
90 *
91 * The caller must take whatever precautions are necessary
92 * (such as holding appropriate locks) to avoid racing
93 * with another list-mutation primitive, such as list_add_tail_rcu()
94 * or list_del_rcu(), running on this same list.
95 * However, it is perfectly legal to run concurrently with
96 * the _rcu list-traversal primitives, such as
97 * list_for_each_entry_rcu().
98 */
99static inline void list_add_tail_rcu(struct list_head *new,
100					struct list_head *head)
101{
102	__list_add_rcu(new, head->prev, head);
103}
104
105/**
106 * list_del_rcu - deletes entry from list without re-initialization
107 * @entry: the element to delete from the list.
108 *
109 * Note: list_empty() on entry does not return true after this,
110 * the entry is in an undefined state. It is useful for RCU based
111 * lockfree traversal.
112 *
113 * In particular, it means that we can not poison the forward
114 * pointers that may still be used for walking the list.
115 *
116 * The caller must take whatever precautions are necessary
117 * (such as holding appropriate locks) to avoid racing
118 * with another list-mutation primitive, such as list_del_rcu()
119 * or list_add_rcu(), running on this same list.
120 * However, it is perfectly legal to run concurrently with
121 * the _rcu list-traversal primitives, such as
122 * list_for_each_entry_rcu().
123 *
124 * Note that the caller is not permitted to immediately free
125 * the newly deleted entry.  Instead, either synchronize_rcu()
126 * or call_rcu() must be used to defer freeing until an RCU
127 * grace period has elapsed.
128 */
129static inline void list_del_rcu(struct list_head *entry)
130{
131	__list_del_entry(entry);
132	entry->prev = LIST_POISON2;
133}
134
135/**
136 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
137 * @n: the element to delete from the hash list.
138 *
139 * Note: list_unhashed() on the node return true after this. It is
140 * useful for RCU based read lockfree traversal if the writer side
141 * must know if the list entry is still hashed or already unhashed.
142 *
143 * In particular, it means that we can not poison the forward pointers
144 * that may still be used for walking the hash list and we can only
145 * zero the pprev pointer so list_unhashed() will return true after
146 * this.
147 *
148 * The caller must take whatever precautions are necessary (such as
149 * holding appropriate locks) to avoid racing with another
150 * list-mutation primitive, such as hlist_add_head_rcu() or
151 * hlist_del_rcu(), running on this same list.  However, it is
152 * perfectly legal to run concurrently with the _rcu list-traversal
153 * primitives, such as hlist_for_each_entry_rcu().
154 */
155static inline void hlist_del_init_rcu(struct hlist_node *n)
156{
157	if (!hlist_unhashed(n)) {
158		__hlist_del(n);
159		n->pprev = NULL;
160	}
161}
162
163/**
164 * list_replace_rcu - replace old entry by new one
165 * @old : the element to be replaced
166 * @new : the new element to insert
167 *
168 * The @old entry will be replaced with the @new entry atomically.
169 * Note: @old should not be empty.
170 */
171static inline void list_replace_rcu(struct list_head *old,
172				struct list_head *new)
173{
174	new->next = old->next;
175	new->prev = old->prev;
176	rcu_assign_pointer(list_next_rcu(new->prev), new);
177	new->next->prev = new;
178	old->prev = LIST_POISON2;
179}
180
181/**
182 * list_splice_init_rcu - splice an RCU-protected list into an existing list.
183 * @list:	the RCU-protected list to splice
184 * @head:	the place in the list to splice the first list into
185 * @sync:	function to sync: synchronize_rcu(), synchronize_sched(), ...
186 *
187 * @head can be RCU-read traversed concurrently with this function.
188 *
189 * Note that this function blocks.
190 *
191 * Important note: the caller must take whatever action is necessary to
192 *	prevent any other updates to @head.  In principle, it is possible
193 *	to modify the list as soon as sync() begins execution.
194 *	If this sort of thing becomes necessary, an alternative version
195 *	based on call_rcu() could be created.  But only if -really-
196 *	needed -- there is no shortage of RCU API members.
197 */
198static inline void list_splice_init_rcu(struct list_head *list,
199					struct list_head *head,
200					void (*sync)(void))
201{
202	struct list_head *first = list->next;
203	struct list_head *last = list->prev;
204	struct list_head *at = head->next;
205
206	if (list_empty(list))
207		return;
208
209	/*
210	 * "first" and "last" tracking list, so initialize it.  RCU readers
211	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
212	 * instead of INIT_LIST_HEAD().
213	 */
214
215	INIT_LIST_HEAD_RCU(list);
216
217	/*
218	 * At this point, the list body still points to the source list.
219	 * Wait for any readers to finish using the list before splicing
220	 * the list body into the new list.  Any new readers will see
221	 * an empty list.
222	 */
223
224	sync();
225
226	/*
227	 * Readers are finished with the source list, so perform splice.
228	 * The order is important if the new list is global and accessible
229	 * to concurrent RCU readers.  Note that RCU readers are not
230	 * permitted to traverse the prev pointers without excluding
231	 * this function.
232	 */
233
234	last->next = at;
235	rcu_assign_pointer(list_next_rcu(head), first);
236	first->prev = head;
237	at->prev = last;
238}
239
240/**
241 * list_entry_rcu - get the struct for this entry
242 * @ptr:        the &struct list_head pointer.
243 * @type:       the type of the struct this is embedded in.
244 * @member:     the name of the list_head within the struct.
245 *
246 * This primitive may safely run concurrently with the _rcu list-mutation
247 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
248 */
249#define list_entry_rcu(ptr, type, member) \
250({ \
251	typeof(*ptr) __rcu *__ptr = (typeof(*ptr) __rcu __force *)ptr; \
252	container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \
253})
254
255/**
256 * Where are list_empty_rcu() and list_first_entry_rcu()?
257 *
258 * Implementing those functions following their counterparts list_empty() and
259 * list_first_entry() is not advisable because they lead to subtle race
260 * conditions as the following snippet shows:
261 *
262 * if (!list_empty_rcu(mylist)) {
263 *	struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
264 *	do_something(bar);
265 * }
266 *
267 * The list may not be empty when list_empty_rcu checks it, but it may be when
268 * list_first_entry_rcu rereads the ->next pointer.
269 *
270 * Rereading the ->next pointer is not a problem for list_empty() and
271 * list_first_entry() because they would be protected by a lock that blocks
272 * writers.
273 *
274 * See list_first_or_null_rcu for an alternative.
275 */
276
277/**
278 * list_first_or_null_rcu - get the first element from a list
279 * @ptr:        the list head to take the element from.
280 * @type:       the type of the struct this is embedded in.
281 * @member:     the name of the list_head within the struct.
282 *
283 * Note that if the list is empty, it returns NULL.
284 *
285 * This primitive may safely run concurrently with the _rcu list-mutation
286 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
287 */
288#define list_first_or_null_rcu(ptr, type, member) \
289({ \
290	struct list_head *__ptr = (ptr); \
291	struct list_head *__next = ACCESS_ONCE(__ptr->next); \
292	likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
293})
294
295/**
296 * list_for_each_entry_rcu	-	iterate over rcu list of given type
297 * @pos:	the type * to use as a loop cursor.
298 * @head:	the head for your list.
299 * @member:	the name of the list_head within the struct.
300 *
301 * This list-traversal primitive may safely run concurrently with
302 * the _rcu list-mutation primitives such as list_add_rcu()
303 * as long as the traversal is guarded by rcu_read_lock().
304 */
305#define list_for_each_entry_rcu(pos, head, member) \
306	for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
307		&pos->member != (head); \
308		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
309
310/**
311 * list_for_each_entry_continue_rcu - continue iteration over list of given type
312 * @pos:	the type * to use as a loop cursor.
313 * @head:	the head for your list.
314 * @member:	the name of the list_head within the struct.
315 *
316 * Continue to iterate over list of given type, continuing after
317 * the current position.
318 */
319#define list_for_each_entry_continue_rcu(pos, head, member) 		\
320	for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
321	     &pos->member != (head);	\
322	     pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
323
324/**
325 * hlist_del_rcu - deletes entry from hash list without re-initialization
326 * @n: the element to delete from the hash list.
327 *
328 * Note: list_unhashed() on entry does not return true after this,
329 * the entry is in an undefined state. It is useful for RCU based
330 * lockfree traversal.
331 *
332 * In particular, it means that we can not poison the forward
333 * pointers that may still be used for walking the hash list.
334 *
335 * The caller must take whatever precautions are necessary
336 * (such as holding appropriate locks) to avoid racing
337 * with another list-mutation primitive, such as hlist_add_head_rcu()
338 * or hlist_del_rcu(), running on this same list.
339 * However, it is perfectly legal to run concurrently with
340 * the _rcu list-traversal primitives, such as
341 * hlist_for_each_entry().
342 */
343static inline void hlist_del_rcu(struct hlist_node *n)
344{
345	__hlist_del(n);
346	n->pprev = LIST_POISON2;
347}
348
349/**
350 * hlist_replace_rcu - replace old entry by new one
351 * @old : the element to be replaced
352 * @new : the new element to insert
353 *
354 * The @old entry will be replaced with the @new entry atomically.
355 */
356static inline void hlist_replace_rcu(struct hlist_node *old,
357					struct hlist_node *new)
358{
359	struct hlist_node *next = old->next;
360
361	new->next = next;
362	new->pprev = old->pprev;
363	rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
364	if (next)
365		new->next->pprev = &new->next;
366	old->pprev = LIST_POISON2;
367}
368
369/*
370 * return the first or the next element in an RCU protected hlist
371 */
372#define hlist_first_rcu(head)	(*((struct hlist_node __rcu **)(&(head)->first)))
373#define hlist_next_rcu(node)	(*((struct hlist_node __rcu **)(&(node)->next)))
374#define hlist_pprev_rcu(node)	(*((struct hlist_node __rcu **)((node)->pprev)))
375
376/**
377 * hlist_add_head_rcu
378 * @n: the element to add to the hash list.
379 * @h: the list to add to.
380 *
381 * Description:
382 * Adds the specified element to the specified hlist,
383 * while permitting racing traversals.
384 *
385 * The caller must take whatever precautions are necessary
386 * (such as holding appropriate locks) to avoid racing
387 * with another list-mutation primitive, such as hlist_add_head_rcu()
388 * or hlist_del_rcu(), running on this same list.
389 * However, it is perfectly legal to run concurrently with
390 * the _rcu list-traversal primitives, such as
391 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
392 * problems on Alpha CPUs.  Regardless of the type of CPU, the
393 * list-traversal primitive must be guarded by rcu_read_lock().
394 */
395static inline void hlist_add_head_rcu(struct hlist_node *n,
396					struct hlist_head *h)
397{
398	struct hlist_node *first = h->first;
399
400	n->next = first;
401	n->pprev = &h->first;
402	rcu_assign_pointer(hlist_first_rcu(h), n);
403	if (first)
404		first->pprev = &n->next;
405}
406
407/**
408 * hlist_add_before_rcu
409 * @n: the new element to add to the hash list.
410 * @next: the existing element to add the new element before.
411 *
412 * Description:
413 * Adds the specified element to the specified hlist
414 * before the specified node while permitting racing traversals.
415 *
416 * The caller must take whatever precautions are necessary
417 * (such as holding appropriate locks) to avoid racing
418 * with another list-mutation primitive, such as hlist_add_head_rcu()
419 * or hlist_del_rcu(), running on this same list.
420 * However, it is perfectly legal to run concurrently with
421 * the _rcu list-traversal primitives, such as
422 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
423 * problems on Alpha CPUs.
424 */
425static inline void hlist_add_before_rcu(struct hlist_node *n,
426					struct hlist_node *next)
427{
428	n->pprev = next->pprev;
429	n->next = next;
430	rcu_assign_pointer(hlist_pprev_rcu(n), n);
431	next->pprev = &n->next;
432}
433
434/**
435 * hlist_add_behind_rcu
436 * @n: the new element to add to the hash list.
437 * @prev: the existing element to add the new element after.
438 *
439 * Description:
440 * Adds the specified element to the specified hlist
441 * after the specified node while permitting racing traversals.
442 *
443 * The caller must take whatever precautions are necessary
444 * (such as holding appropriate locks) to avoid racing
445 * with another list-mutation primitive, such as hlist_add_head_rcu()
446 * or hlist_del_rcu(), running on this same list.
447 * However, it is perfectly legal to run concurrently with
448 * the _rcu list-traversal primitives, such as
449 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
450 * problems on Alpha CPUs.
451 */
452static inline void hlist_add_behind_rcu(struct hlist_node *n,
453					struct hlist_node *prev)
454{
455	n->next = prev->next;
456	n->pprev = &prev->next;
457	rcu_assign_pointer(hlist_next_rcu(prev), n);
458	if (n->next)
459		n->next->pprev = &n->next;
460}
461
462#define __hlist_for_each_rcu(pos, head)				\
463	for (pos = rcu_dereference(hlist_first_rcu(head));	\
464	     pos;						\
465	     pos = rcu_dereference(hlist_next_rcu(pos)))
466
467/**
468 * hlist_for_each_entry_rcu - iterate over rcu list of given type
469 * @pos:	the type * to use as a loop cursor.
470 * @head:	the head for your list.
471 * @member:	the name of the hlist_node within the struct.
472 *
473 * This list-traversal primitive may safely run concurrently with
474 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
475 * as long as the traversal is guarded by rcu_read_lock().
476 */
477#define hlist_for_each_entry_rcu(pos, head, member)			\
478	for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
479			typeof(*(pos)), member);			\
480		pos;							\
481		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
482			&(pos)->member)), typeof(*(pos)), member))
483
484/**
485 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
486 * @pos:	the type * to use as a loop cursor.
487 * @head:	the head for your list.
488 * @member:	the name of the hlist_node within the struct.
489 *
490 * This list-traversal primitive may safely run concurrently with
491 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
492 * as long as the traversal is guarded by rcu_read_lock().
493 *
494 * This is the same as hlist_for_each_entry_rcu() except that it does
495 * not do any RCU debugging or tracing.
496 */
497#define hlist_for_each_entry_rcu_notrace(pos, head, member)			\
498	for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\
499			typeof(*(pos)), member);			\
500		pos;							\
501		pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\
502			&(pos)->member)), typeof(*(pos)), member))
503
504/**
505 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
506 * @pos:	the type * to use as a loop cursor.
507 * @head:	the head for your list.
508 * @member:	the name of the hlist_node within the struct.
509 *
510 * This list-traversal primitive may safely run concurrently with
511 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
512 * as long as the traversal is guarded by rcu_read_lock().
513 */
514#define hlist_for_each_entry_rcu_bh(pos, head, member)			\
515	for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
516			typeof(*(pos)), member);			\
517		pos;							\
518		pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
519			&(pos)->member)), typeof(*(pos)), member))
520
521/**
522 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
523 * @pos:	the type * to use as a loop cursor.
524 * @member:	the name of the hlist_node within the struct.
525 */
526#define hlist_for_each_entry_continue_rcu(pos, member)			\
527	for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
528			&(pos)->member)), typeof(*(pos)), member);	\
529	     pos;							\
530	     pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(	\
531			&(pos)->member)), typeof(*(pos)), member))
532
533/**
534 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
535 * @pos:	the type * to use as a loop cursor.
536 * @member:	the name of the hlist_node within the struct.
537 */
538#define hlist_for_each_entry_continue_rcu_bh(pos, member)		\
539	for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
540			&(pos)->member)), typeof(*(pos)), member);	\
541	     pos;							\
542	     pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(	\
543			&(pos)->member)), typeof(*(pos)), member))
544
545/**
546 * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
547 * @pos:	the type * to use as a loop cursor.
548 * @member:	the name of the hlist_node within the struct.
549 */
550#define hlist_for_each_entry_from_rcu(pos, member)			\
551	for (; pos;							\
552	     pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\
553			typeof(*(pos)), member))
554
555#endif	/* __KERNEL__ */
556#endif
557