rculist.h

  1/* SPDX-License-Identifier: GPL-2.0 */
  2#ifndef _LINUX_RCULIST_H
  3#define _LINUX_RCULIST_H
  4
  5#ifdef __KERNEL__
  6
  7/*
  8 * RCU-protected list version
  9 */
 10#include <linux/list.h>
 11#include <linux/rcupdate.h>
 12
 13/*
 14 * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
 15 * @list: list to be initialized
 16 *
 17 * You should instead use INIT_LIST_HEAD() for normal initialization and
 18 * cleanup tasks, when readers have no access to the list being initialized.
 19 * However, if the list being initialized is visible to readers, you
 20 * need to keep the compiler from being too mischievous.
 21 */
 22static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
 23{
 24	WRITE_ONCE(list->next, list);
 25	WRITE_ONCE(list->prev, list);
 26}
 27
 28/*
 29 * return the ->next pointer of a list_head in an rcu safe
 30 * way, we must not access it directly
 31 */
 32#define list_next_rcu(list)	(*((struct list_head __rcu **)(&(list)->next)))
 33/*
 34 * Return the ->prev pointer of a list_head in an rcu safe way. Don't
 35 * access it directly.
 36 *
 37 * Any list traversed with list_bidir_prev_rcu() must never use
 38 * list_del_rcu().  Doing so will poison the ->prev pointer that
 39 * list_bidir_prev_rcu() relies on, which will result in segfaults.
 40 * To prevent these segfaults, use list_bidir_del_rcu() instead
 41 * of list_del_rcu().
 42 */
 43#define list_bidir_prev_rcu(list) (*((struct list_head __rcu **)(&(list)->prev)))
 44
 45/**
 46 * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
 47 * @pos:	the &struct list_head to use as a loop cursor.
 48 * @head:	the head for your list.
 49 */
 50#define list_for_each_rcu(pos, head)		  \
 51	for (pos = rcu_dereference((head)->next); \
 52	     !list_is_head(pos, (head)); \
 53	     pos = rcu_dereference(pos->next))
 54
 55/**
 56 * list_tail_rcu - returns the prev pointer of the head of the list
 57 * @head: the head of the list
 58 *
 59 * Note: This should only be used with the list header, and even then
 60 * only if list_del() and similar primitives are not also used on the
 61 * list header.
 62 */
 63#define list_tail_rcu(head)	(*((struct list_head __rcu **)(&(head)->prev)))
 64
 65/*
 66 * Check during list traversal that we are within an RCU reader
 67 */
 68
 69#define check_arg_count_one(dummy)
 70
 71#ifdef CONFIG_PROVE_RCU_LIST
 72#define __list_check_rcu(dummy, cond, extra...)				\
 73	({								\
 74	check_arg_count_one(extra);					\
 75	RCU_LOCKDEP_WARN(!(cond) && !rcu_read_lock_any_held(),		\
 76			 "RCU-list traversed in non-reader section!");	\
 77	})
 78
 79#define __list_check_srcu(cond)					 \
 80	({								 \
 81	RCU_LOCKDEP_WARN(!(cond),					 \
 82		"RCU-list traversed without holding the required lock!");\
 83	})
 84#else
 85#define __list_check_rcu(dummy, cond, extra...)				\
 86	({ check_arg_count_one(extra); })
 87
 88#define __list_check_srcu(cond) ({ })
 89#endif
 90
 91/*
 92 * Insert a new entry between two known consecutive entries.
 93 *
 94 * This is only for internal list manipulation where we know
 95 * the prev/next entries already!
 96 */
 97static inline void __list_add_rcu(struct list_head *new,
 98		struct list_head *prev, struct list_head *next)
 99{
100	if (!__list_add_valid(new, prev, next))
101		return;
102
103	new->next = next;
104	new->prev = prev;
105	rcu_assign_pointer(list_next_rcu(prev), new);
106	next->prev = new;
107}
108
109/**
110 * list_add_rcu - add a new entry to rcu-protected list
111 * @new: new entry to be added
112 * @head: list head to add it after
113 *
114 * Insert a new entry after the specified head.
115 * This is good for implementing stacks.
116 *
117 * The caller must take whatever precautions are necessary
118 * (such as holding appropriate locks) to avoid racing
119 * with another list-mutation primitive, such as list_add_rcu()
120 * or list_del_rcu(), running on this same list.
121 * However, it is perfectly legal to run concurrently with
122 * the _rcu list-traversal primitives, such as
123 * list_for_each_entry_rcu().
124 */
125static inline void list_add_rcu(struct list_head *new, struct list_head *head)
126{
127	__list_add_rcu(new, head, head->next);
128}
129
130/**
131 * list_add_tail_rcu - add a new entry to rcu-protected list
132 * @new: new entry to be added
133 * @head: list head to add it before
134 *
135 * Insert a new entry before the specified head.
136 * This is useful for implementing queues.
137 *
138 * The caller must take whatever precautions are necessary
139 * (such as holding appropriate locks) to avoid racing
140 * with another list-mutation primitive, such as list_add_tail_rcu()
141 * or list_del_rcu(), running on this same list.
142 * However, it is perfectly legal to run concurrently with
143 * the _rcu list-traversal primitives, such as
144 * list_for_each_entry_rcu().
145 */
146static inline void list_add_tail_rcu(struct list_head *new,
147					struct list_head *head)
148{
149	__list_add_rcu(new, head->prev, head);
150}
151
152/**
153 * list_del_rcu - deletes entry from list without re-initialization
154 * @entry: the element to delete from the list.
155 *
156 * Note: list_empty() on entry does not return true after this,
157 * the entry is in an undefined state. It is useful for RCU based
158 * lockfree traversal.
159 *
160 * In particular, it means that we can not poison the forward
161 * pointers that may still be used for walking the list.
162 *
163 * The caller must take whatever precautions are necessary
164 * (such as holding appropriate locks) to avoid racing
165 * with another list-mutation primitive, such as list_del_rcu()
166 * or list_add_rcu(), running on this same list.
167 * However, it is perfectly legal to run concurrently with
168 * the _rcu list-traversal primitives, such as
169 * list_for_each_entry_rcu().
170 *
171 * Note that the caller is not permitted to immediately free
172 * the newly deleted entry.  Instead, either synchronize_rcu()
173 * or call_rcu() must be used to defer freeing until an RCU
174 * grace period has elapsed.
175 */
176static inline void list_del_rcu(struct list_head *entry)
177{
178	__list_del_entry(entry);
179	entry->prev = LIST_POISON2;
180}
181
182/**
183 * list_bidir_del_rcu - deletes entry from list without re-initialization
184 * @entry: the element to delete from the list.
185 *
186 * In contrast to list_del_rcu() doesn't poison the prev pointer thus
187 * allowing backwards traversal via list_bidir_prev_rcu().
188 *
189 * Note: list_empty() on entry does not return true after this because
190 * the entry is in a special undefined state that permits RCU-based
191 * lockfree reverse traversal. In particular this means that we can not
192 * poison the forward and backwards pointers that may still be used for
193 * walking the list.
194 *
195 * The caller must take whatever precautions are necessary (such as
196 * holding appropriate locks) to avoid racing with another list-mutation
197 * primitive, such as list_bidir_del_rcu() or list_add_rcu(), running on
198 * this same list. However, it is perfectly legal to run concurrently
199 * with the _rcu list-traversal primitives, such as
200 * list_for_each_entry_rcu().
201 *
202 * Note that list_del_rcu() and list_bidir_del_rcu() must not be used on
203 * the same list.
204 *
205 * Note that the caller is not permitted to immediately free
206 * the newly deleted entry.  Instead, either synchronize_rcu()
207 * or call_rcu() must be used to defer freeing until an RCU
208 * grace period has elapsed.
209 */
210static inline void list_bidir_del_rcu(struct list_head *entry)
211{
212	__list_del_entry(entry);
213}
214
215/**
216 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
217 * @n: the element to delete from the hash list.
218 *
219 * Note: list_unhashed() on the node return true after this. It is
220 * useful for RCU based read lockfree traversal if the writer side
221 * must know if the list entry is still hashed or already unhashed.
222 *
223 * In particular, it means that we can not poison the forward pointers
224 * that may still be used for walking the hash list and we can only
225 * zero the pprev pointer so list_unhashed() will return true after
226 * this.
227 *
228 * The caller must take whatever precautions are necessary (such as
229 * holding appropriate locks) to avoid racing with another
230 * list-mutation primitive, such as hlist_add_head_rcu() or
231 * hlist_del_rcu(), running on this same list.  However, it is
232 * perfectly legal to run concurrently with the _rcu list-traversal
233 * primitives, such as hlist_for_each_entry_rcu().
234 */
235static inline void hlist_del_init_rcu(struct hlist_node *n)
236{
237	if (!hlist_unhashed(n)) {
238		__hlist_del(n);
239		WRITE_ONCE(n->pprev, NULL);
240	}
241}
242
243/**
244 * list_replace_rcu - replace old entry by new one
245 * @old : the element to be replaced
246 * @new : the new element to insert
247 *
248 * The @old entry will be replaced with the @new entry atomically from
249 * the perspective of concurrent readers.  It is the caller's responsibility
250 * to synchronize with concurrent updaters, if any.
251 *
252 * Note: @old should not be empty.
253 */
254static inline void list_replace_rcu(struct list_head *old,
255				struct list_head *new)
256{
257	new->next = old->next;
258	new->prev = old->prev;
259	rcu_assign_pointer(list_next_rcu(new->prev), new);
260	new->next->prev = new;
261	old->prev = LIST_POISON2;
262}
263
264/**
265 * __list_splice_init_rcu - join an RCU-protected list into an existing list.
266 * @list:	the RCU-protected list to splice
267 * @prev:	points to the last element of the existing list
268 * @next:	points to the first element of the existing list
269 * @sync:	synchronize_rcu, synchronize_rcu_expedited, ...
270 *
271 * The list pointed to by @prev and @next can be RCU-read traversed
272 * concurrently with this function.
273 *
274 * Note that this function blocks.
275 *
276 * Important note: the caller must take whatever action is necessary to prevent
277 * any other updates to the existing list.  In principle, it is possible to
278 * modify the list as soon as sync() begins execution. If this sort of thing
279 * becomes necessary, an alternative version based on call_rcu() could be
280 * created.  But only if -really- needed -- there is no shortage of RCU API
281 * members.
282 */
283static inline void __list_splice_init_rcu(struct list_head *list,
284					  struct list_head *prev,
285					  struct list_head *next,
286					  void (*sync)(void))
287{
288	struct list_head *first = list->next;
289	struct list_head *last = list->prev;
290
291	/*
292	 * "first" and "last" tracking list, so initialize it.  RCU readers
293	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
294	 * instead of INIT_LIST_HEAD().
295	 */
296
297	INIT_LIST_HEAD_RCU(list);
298
299	/*
300	 * At this point, the list body still points to the source list.
301	 * Wait for any readers to finish using the list before splicing
302	 * the list body into the new list.  Any new readers will see
303	 * an empty list.
304	 */
305
306	sync();
307	ASSERT_EXCLUSIVE_ACCESS(*first);
308	ASSERT_EXCLUSIVE_ACCESS(*last);
309
310	/*
311	 * Readers are finished with the source list, so perform splice.
312	 * The order is important if the new list is global and accessible
313	 * to concurrent RCU readers.  Note that RCU readers are not
314	 * permitted to traverse the prev pointers without excluding
315	 * this function.
316	 */
317
318	last->next = next;
319	rcu_assign_pointer(list_next_rcu(prev), first);
320	first->prev = prev;
321	next->prev = last;
322}
323
324/**
325 * list_splice_init_rcu - splice an RCU-protected list into an existing list,
326 *                        designed for stacks.
327 * @list:	the RCU-protected list to splice
328 * @head:	the place in the existing list to splice the first list into
329 * @sync:	synchronize_rcu, synchronize_rcu_expedited, ...
330 */
331static inline void list_splice_init_rcu(struct list_head *list,
332					struct list_head *head,
333					void (*sync)(void))
334{
335	if (!list_empty(list))
336		__list_splice_init_rcu(list, head, head->next, sync);
337}
338
339/**
340 * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
341 *                             list, designed for queues.
342 * @list:	the RCU-protected list to splice
343 * @head:	the place in the existing list to splice the first list into
344 * @sync:	synchronize_rcu, synchronize_rcu_expedited, ...
345 */
346static inline void list_splice_tail_init_rcu(struct list_head *list,
347					     struct list_head *head,
348					     void (*sync)(void))
349{
350	if (!list_empty(list))
351		__list_splice_init_rcu(list, head->prev, head, sync);
352}
353
354/**
355 * list_entry_rcu - get the struct for this entry
356 * @ptr:        the &struct list_head pointer.
357 * @type:       the type of the struct this is embedded in.
358 * @member:     the name of the list_head within the struct.
359 *
360 * This primitive may safely run concurrently with the _rcu list-mutation
361 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
362 */
363#define list_entry_rcu(ptr, type, member) \
364	container_of(READ_ONCE(ptr), type, member)
365
366/*
367 * Where are list_empty_rcu() and list_first_entry_rcu()?
368 *
369 * They do not exist because they would lead to subtle race conditions:
370 *
371 * if (!list_empty_rcu(mylist)) {
372 *	struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
373 *	do_something(bar);
374 * }
375 *
376 * The list might be non-empty when list_empty_rcu() checks it, but it
377 * might have become empty by the time that list_first_entry_rcu() rereads
378 * the ->next pointer, which would result in a SEGV.
379 *
380 * When not using RCU, it is OK for list_first_entry() to re-read that
381 * pointer because both functions should be protected by some lock that
382 * blocks writers.
383 *
384 * When using RCU, list_empty() uses READ_ONCE() to fetch the
385 * RCU-protected ->next pointer and then compares it to the address of the
386 * list head.  However, it neither dereferences this pointer nor provides
387 * this pointer to its caller.  Thus, READ_ONCE() suffices (that is,
388 * rcu_dereference() is not needed), which means that list_empty() can be
389 * used anywhere you would want to use list_empty_rcu().  Just don't
390 * expect anything useful to happen if you do a subsequent lockless
391 * call to list_first_entry_rcu()!!!
392 *
393 * See list_first_or_null_rcu for an alternative.
394 */
395
396/**
397 * list_first_or_null_rcu - get the first element from a list
398 * @ptr:        the list head to take the element from.
399 * @type:       the type of the struct this is embedded in.
400 * @member:     the name of the list_head within the struct.
401 *
402 * Note that if the list is empty, it returns NULL.
403 *
404 * This primitive may safely run concurrently with the _rcu list-mutation
405 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
406 */
407#define list_first_or_null_rcu(ptr, type, member) \
408({ \
409	struct list_head *__ptr = (ptr); \
410	struct list_head *__next = READ_ONCE(__ptr->next); \
411	likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
412})
413
414/**
415 * list_next_or_null_rcu - get the next element from a list
416 * @head:	the head for the list.
417 * @ptr:        the list head to take the next element from.
418 * @type:       the type of the struct this is embedded in.
419 * @member:     the name of the list_head within the struct.
420 *
421 * Note that if the ptr is at the end of the list, NULL is returned.
422 *
423 * This primitive may safely run concurrently with the _rcu list-mutation
424 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
425 */
426#define list_next_or_null_rcu(head, ptr, type, member) \
427({ \
428	struct list_head *__head = (head); \
429	struct list_head *__ptr = (ptr); \
430	struct list_head *__next = READ_ONCE(__ptr->next); \
431	likely(__next != __head) ? list_entry_rcu(__next, type, \
432						  member) : NULL; \
433})
434
435/**
436 * list_for_each_entry_rcu	-	iterate over rcu list of given type
437 * @pos:	the type * to use as a loop cursor.
438 * @head:	the head for your list.
439 * @member:	the name of the list_head within the struct.
440 * @cond:	optional lockdep expression if called from non-RCU protection.
441 *
442 * This list-traversal primitive may safely run concurrently with
443 * the _rcu list-mutation primitives such as list_add_rcu()
444 * as long as the traversal is guarded by rcu_read_lock().
445 */
446#define list_for_each_entry_rcu(pos, head, member, cond...)		\
447	for (__list_check_rcu(dummy, ## cond, 0),			\
448	     pos = list_entry_rcu((head)->next, typeof(*pos), member);	\
449		&pos->member != (head);					\
450		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
451
452/**
453 * list_for_each_entry_srcu	-	iterate over rcu list of given type
454 * @pos:	the type * to use as a loop cursor.
455 * @head:	the head for your list.
456 * @member:	the name of the list_head within the struct.
457 * @cond:	lockdep expression for the lock required to traverse the list.
458 *
459 * This list-traversal primitive may safely run concurrently with
460 * the _rcu list-mutation primitives such as list_add_rcu()
461 * as long as the traversal is guarded by srcu_read_lock().
462 * The lockdep expression srcu_read_lock_held() can be passed as the
463 * cond argument from read side.
464 */
465#define list_for_each_entry_srcu(pos, head, member, cond)		\
466	for (__list_check_srcu(cond),					\
467	     pos = list_entry_rcu((head)->next, typeof(*pos), member);	\
468		&pos->member != (head);					\
469		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
470
471/**
472 * list_entry_lockless - get the struct for this entry
473 * @ptr:        the &struct list_head pointer.
474 * @type:       the type of the struct this is embedded in.
475 * @member:     the name of the list_head within the struct.
476 *
477 * This primitive may safely run concurrently with the _rcu
478 * list-mutation primitives such as list_add_rcu(), but requires some
479 * implicit RCU read-side guarding.  One example is running within a special
480 * exception-time environment where preemption is disabled and where lockdep
481 * cannot be invoked.  Another example is when items are added to the list,
482 * but never deleted.
483 */
484#define list_entry_lockless(ptr, type, member) \
485	container_of((typeof(ptr))READ_ONCE(ptr), type, member)
486
487/**
488 * list_for_each_entry_lockless - iterate over rcu list of given type
489 * @pos:	the type * to use as a loop cursor.
490 * @head:	the head for your list.
491 * @member:	the name of the list_struct within the struct.
492 *
493 * This primitive may safely run concurrently with the _rcu
494 * list-mutation primitives such as list_add_rcu(), but requires some
495 * implicit RCU read-side guarding.  One example is running within a special
496 * exception-time environment where preemption is disabled and where lockdep
497 * cannot be invoked.  Another example is when items are added to the list,
498 * but never deleted.
499 */
500#define list_for_each_entry_lockless(pos, head, member) \
501	for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
502	     &pos->member != (head); \
503	     pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
504
505/**
506 * list_for_each_entry_continue_rcu - continue iteration over list of given type
507 * @pos:	the type * to use as a loop cursor.
508 * @head:	the head for your list.
509 * @member:	the name of the list_head within the struct.
510 *
511 * Continue to iterate over list of given type, continuing after
512 * the current position which must have been in the list when the RCU read
513 * lock was taken.
514 * This would typically require either that you obtained the node from a
515 * previous walk of the list in the same RCU read-side critical section, or
516 * that you held some sort of non-RCU reference (such as a reference count)
517 * to keep the node alive *and* in the list.
518 *
519 * This iterator is similar to list_for_each_entry_from_rcu() except
520 * this starts after the given position and that one starts at the given
521 * position.
522 */
523#define list_for_each_entry_continue_rcu(pos, head, member) 		\
524	for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
525	     &pos->member != (head);	\
526	     pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
527
528/**
529 * list_for_each_entry_from_rcu - iterate over a list from current point
530 * @pos:	the type * to use as a loop cursor.
531 * @head:	the head for your list.
532 * @member:	the name of the list_node within the struct.
533 *
534 * Iterate over the tail of a list starting from a given position,
535 * which must have been in the list when the RCU read lock was taken.
536 * This would typically require either that you obtained the node from a
537 * previous walk of the list in the same RCU read-side critical section, or
538 * that you held some sort of non-RCU reference (such as a reference count)
539 * to keep the node alive *and* in the list.
540 *
541 * This iterator is similar to list_for_each_entry_continue_rcu() except
542 * this starts from the given position and that one starts from the position
543 * after the given position.
544 */
545#define list_for_each_entry_from_rcu(pos, head, member)			\
546	for (; &(pos)->member != (head);					\
547		pos = list_entry_rcu(pos->member.next, typeof(*(pos)), member))
548
549/**
550 * hlist_del_rcu - deletes entry from hash list without re-initialization
551 * @n: the element to delete from the hash list.
552 *
553 * Note: list_unhashed() on entry does not return true after this,
554 * the entry is in an undefined state. It is useful for RCU based
555 * lockfree traversal.
556 *
557 * In particular, it means that we can not poison the forward
558 * pointers that may still be used for walking the hash list.
559 *
560 * The caller must take whatever precautions are necessary
561 * (such as holding appropriate locks) to avoid racing
562 * with another list-mutation primitive, such as hlist_add_head_rcu()
563 * or hlist_del_rcu(), running on this same list.
564 * However, it is perfectly legal to run concurrently with
565 * the _rcu list-traversal primitives, such as
566 * hlist_for_each_entry().
567 */
568static inline void hlist_del_rcu(struct hlist_node *n)
569{
570	__hlist_del(n);
571	WRITE_ONCE(n->pprev, LIST_POISON2);
572}
573
574/**
575 * hlist_replace_rcu - replace old entry by new one
576 * @old : the element to be replaced
577 * @new : the new element to insert
578 *
579 * The @old entry will be replaced with the @new entry atomically from
580 * the perspective of concurrent readers.  It is the caller's responsibility
581 * to synchronize with concurrent updaters, if any.
582 */
583static inline void hlist_replace_rcu(struct hlist_node *old,
584					struct hlist_node *new)
585{
586	struct hlist_node *next = old->next;
587
588	new->next = next;
589	WRITE_ONCE(new->pprev, old->pprev);
590	rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
591	if (next)
592		WRITE_ONCE(new->next->pprev, &new->next);
593	WRITE_ONCE(old->pprev, LIST_POISON2);
594}
595
596/**
597 * hlists_swap_heads_rcu - swap the lists the hlist heads point to
598 * @left:  The hlist head on the left
599 * @right: The hlist head on the right
600 *
601 * The lists start out as [@left  ][node1 ... ] and
602 *                        [@right ][node2 ... ]
603 * The lists end up as    [@left  ][node2 ... ]
604 *                        [@right ][node1 ... ]
605 */
606static inline void hlists_swap_heads_rcu(struct hlist_head *left, struct hlist_head *right)
607{
608	struct hlist_node *node1 = left->first;
609	struct hlist_node *node2 = right->first;
610
611	rcu_assign_pointer(left->first, node2);
612	rcu_assign_pointer(right->first, node1);
613	WRITE_ONCE(node2->pprev, &left->first);
614	WRITE_ONCE(node1->pprev, &right->first);
615}
616
617/*
618 * return the first or the next element in an RCU protected hlist
619 */
620#define hlist_first_rcu(head)	(*((struct hlist_node __rcu **)(&(head)->first)))
621#define hlist_next_rcu(node)	(*((struct hlist_node __rcu **)(&(node)->next)))
622#define hlist_pprev_rcu(node)	(*((struct hlist_node __rcu **)((node)->pprev)))
623
624/**
625 * hlist_add_head_rcu
626 * @n: the element to add to the hash list.
627 * @h: the list to add to.
628 *
629 * Description:
630 * Adds the specified element to the specified hlist,
631 * while permitting racing traversals.
632 *
633 * The caller must take whatever precautions are necessary
634 * (such as holding appropriate locks) to avoid racing
635 * with another list-mutation primitive, such as hlist_add_head_rcu()
636 * or hlist_del_rcu(), running on this same list.
637 * However, it is perfectly legal to run concurrently with
638 * the _rcu list-traversal primitives, such as
639 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
640 * problems on Alpha CPUs.  Regardless of the type of CPU, the
641 * list-traversal primitive must be guarded by rcu_read_lock().
642 */
643static inline void hlist_add_head_rcu(struct hlist_node *n,
644					struct hlist_head *h)
645{
646	struct hlist_node *first = h->first;
647
648	n->next = first;
649	WRITE_ONCE(n->pprev, &h->first);
650	rcu_assign_pointer(hlist_first_rcu(h), n);
651	if (first)
652		WRITE_ONCE(first->pprev, &n->next);
653}
654
655/**
656 * hlist_add_tail_rcu
657 * @n: the element to add to the hash list.
658 * @h: the list to add to.
659 *
660 * Description:
661 * Adds the specified element to the specified hlist,
662 * while permitting racing traversals.
663 *
664 * The caller must take whatever precautions are necessary
665 * (such as holding appropriate locks) to avoid racing
666 * with another list-mutation primitive, such as hlist_add_head_rcu()
667 * or hlist_del_rcu(), running on this same list.
668 * However, it is perfectly legal to run concurrently with
669 * the _rcu list-traversal primitives, such as
670 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
671 * problems on Alpha CPUs.  Regardless of the type of CPU, the
672 * list-traversal primitive must be guarded by rcu_read_lock().
673 */
674static inline void hlist_add_tail_rcu(struct hlist_node *n,
675				      struct hlist_head *h)
676{
677	struct hlist_node *i, *last = NULL;
678
679	/* Note: write side code, so rcu accessors are not needed. */
680	for (i = h->first; i; i = i->next)
681		last = i;
682
683	if (last) {
684		n->next = last->next;
685		WRITE_ONCE(n->pprev, &last->next);
686		rcu_assign_pointer(hlist_next_rcu(last), n);
687	} else {
688		hlist_add_head_rcu(n, h);
689	}
690}
691
692/**
693 * hlist_add_before_rcu
694 * @n: the new element to add to the hash list.
695 * @next: the existing element to add the new element before.
696 *
697 * Description:
698 * Adds the specified element to the specified hlist
699 * before the specified node while permitting racing traversals.
700 *
701 * The caller must take whatever precautions are necessary
702 * (such as holding appropriate locks) to avoid racing
703 * with another list-mutation primitive, such as hlist_add_head_rcu()
704 * or hlist_del_rcu(), running on this same list.
705 * However, it is perfectly legal to run concurrently with
706 * the _rcu list-traversal primitives, such as
707 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
708 * problems on Alpha CPUs.
709 */
710static inline void hlist_add_before_rcu(struct hlist_node *n,
711					struct hlist_node *next)
712{
713	WRITE_ONCE(n->pprev, next->pprev);
714	n->next = next;
715	rcu_assign_pointer(hlist_pprev_rcu(n), n);
716	WRITE_ONCE(next->pprev, &n->next);
717}
718
719/**
720 * hlist_add_behind_rcu
721 * @n: the new element to add to the hash list.
722 * @prev: the existing element to add the new element after.
723 *
724 * Description:
725 * Adds the specified element to the specified hlist
726 * after the specified node while permitting racing traversals.
727 *
728 * The caller must take whatever precautions are necessary
729 * (such as holding appropriate locks) to avoid racing
730 * with another list-mutation primitive, such as hlist_add_head_rcu()
731 * or hlist_del_rcu(), running on this same list.
732 * However, it is perfectly legal to run concurrently with
733 * the _rcu list-traversal primitives, such as
734 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
735 * problems on Alpha CPUs.
736 */
737static inline void hlist_add_behind_rcu(struct hlist_node *n,
738					struct hlist_node *prev)
739{
740	n->next = prev->next;
741	WRITE_ONCE(n->pprev, &prev->next);
742	rcu_assign_pointer(hlist_next_rcu(prev), n);
743	if (n->next)
744		WRITE_ONCE(n->next->pprev, &n->next);
745}
746
747#define __hlist_for_each_rcu(pos, head)				\
748	for (pos = rcu_dereference(hlist_first_rcu(head));	\
749	     pos;						\
750	     pos = rcu_dereference(hlist_next_rcu(pos)))
751
752/**
753 * hlist_for_each_entry_rcu - iterate over rcu list of given type
754 * @pos:	the type * to use as a loop cursor.
755 * @head:	the head for your list.
756 * @member:	the name of the hlist_node within the struct.
757 * @cond:	optional lockdep expression if called from non-RCU protection.
758 *
759 * This list-traversal primitive may safely run concurrently with
760 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
761 * as long as the traversal is guarded by rcu_read_lock().
762 */
763#define hlist_for_each_entry_rcu(pos, head, member, cond...)		\
764	for (__list_check_rcu(dummy, ## cond, 0),			\
765	     pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
766			typeof(*(pos)), member);			\
767		pos;							\
768		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
769			&(pos)->member)), typeof(*(pos)), member))
770
771/**
772 * hlist_for_each_entry_srcu - iterate over rcu list of given type
773 * @pos:	the type * to use as a loop cursor.
774 * @head:	the head for your list.
775 * @member:	the name of the hlist_node within the struct.
776 * @cond:	lockdep expression for the lock required to traverse the list.
777 *
778 * This list-traversal primitive may safely run concurrently with
779 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
780 * as long as the traversal is guarded by srcu_read_lock().
781 * The lockdep expression srcu_read_lock_held() can be passed as the
782 * cond argument from read side.
783 */
784#define hlist_for_each_entry_srcu(pos, head, member, cond)		\
785	for (__list_check_srcu(cond),					\
786	     pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
787			typeof(*(pos)), member);			\
788		pos;							\
789		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
790			&(pos)->member)), typeof(*(pos)), member))
791
792/**
793 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
794 * @pos:	the type * to use as a loop cursor.
795 * @head:	the head for your list.
796 * @member:	the name of the hlist_node within the struct.
797 *
798 * This list-traversal primitive may safely run concurrently with
799 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
800 * as long as the traversal is guarded by rcu_read_lock().
801 *
802 * This is the same as hlist_for_each_entry_rcu() except that it does
803 * not do any RCU debugging or tracing.
804 */
805#define hlist_for_each_entry_rcu_notrace(pos, head, member)			\
806	for (pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_first_rcu(head)),\
807			typeof(*(pos)), member);			\
808		pos;							\
809		pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_next_rcu(\
810			&(pos)->member)), typeof(*(pos)), member))
811
812/**
813 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
814 * @pos:	the type * to use as a loop cursor.
815 * @head:	the head for your list.
816 * @member:	the name of the hlist_node within the struct.
817 *
818 * This list-traversal primitive may safely run concurrently with
819 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
820 * as long as the traversal is guarded by rcu_read_lock().
821 */
822#define hlist_for_each_entry_rcu_bh(pos, head, member)			\
823	for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
824			typeof(*(pos)), member);			\
825		pos;							\
826		pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
827			&(pos)->member)), typeof(*(pos)), member))
828
829/**
830 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
831 * @pos:	the type * to use as a loop cursor.
832 * @member:	the name of the hlist_node within the struct.
833 */
834#define hlist_for_each_entry_continue_rcu(pos, member)			\
835	for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
836			&(pos)->member)), typeof(*(pos)), member);	\
837	     pos;							\
838	     pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(	\
839			&(pos)->member)), typeof(*(pos)), member))
840
841/**
842 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
843 * @pos:	the type * to use as a loop cursor.
844 * @member:	the name of the hlist_node within the struct.
845 */
846#define hlist_for_each_entry_continue_rcu_bh(pos, member)		\
847	for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
848			&(pos)->member)), typeof(*(pos)), member);	\
849	     pos;							\
850	     pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(	\
851			&(pos)->member)), typeof(*(pos)), member))
852
853/**
854 * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
855 * @pos:	the type * to use as a loop cursor.
856 * @member:	the name of the hlist_node within the struct.
857 */
858#define hlist_for_each_entry_from_rcu(pos, member)			\
859	for (; pos;							\
860	     pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(	\
861			&(pos)->member)), typeof(*(pos)), member))
862
863#endif	/* __KERNEL__ */
864#endif