1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef _LINUX_LIST_H
3 #define _LINUX_LIST_H
4 
5 #include <linux/container_of.h>
6 #include <linux/types.h>
7 #include <linux/stddef.h>
8 #include <linux/poison.h>
9 #include <linux/const.h>
10 
11 #include <asm/barrier.h>
12 
13 /*
14  * Circular doubly linked list implementation.
15  *
16  * Some of the internal functions ("__xxx") are useful when
17  * manipulating whole lists rather than single entries, as
18  * sometimes we already know the next/prev entries and we can
19  * generate better code by using them directly rather than
20  * using the generic single-entry routines.
21  */
22 
23 #define LIST_HEAD_INIT(name) { &(name), &(name) }
24 
25 #define LIST_HEAD(name) \
26 	struct list_head name = LIST_HEAD_INIT(name)
27 
28 /**
29  * INIT_LIST_HEAD - Initialize a list_head structure
30  * @list: list_head structure to be initialized.
31  *
32  * Initializes the list_head to point to itself.  If it is a list header,
33  * the result is an empty list.
34  */
INIT_LIST_HEAD(struct list_head * list)35 static inline void INIT_LIST_HEAD(struct list_head *list)
36 {
37 	WRITE_ONCE(list->next, list);
38 	WRITE_ONCE(list->prev, list);
39 }
40 
41 #ifdef CONFIG_LIST_HARDENED
42 
43 #ifdef CONFIG_DEBUG_LIST
44 # define __list_valid_slowpath
45 #else
46 # define __list_valid_slowpath __cold __preserve_most
47 #endif
48 
49 /*
50  * Performs the full set of list corruption checks before __list_add().
51  * On list corruption reports a warning, and returns false.
52  */
53 extern bool __list_valid_slowpath __list_add_valid_or_report(struct list_head *new,
54 							     struct list_head *prev,
55 							     struct list_head *next);
56 
57 /*
58  * Performs list corruption checks before __list_add(). Returns false if a
59  * corruption is detected, true otherwise.
60  *
61  * With CONFIG_LIST_HARDENED only, performs minimal list integrity checking
62  * inline to catch non-faulting corruptions, and only if a corruption is
63  * detected calls the reporting function __list_add_valid_or_report().
64  */
__list_add_valid(struct list_head * new,struct list_head * prev,struct list_head * next)65 static __always_inline bool __list_add_valid(struct list_head *new,
66 					     struct list_head *prev,
67 					     struct list_head *next)
68 {
69 	bool ret = true;
70 
71 	if (!IS_ENABLED(CONFIG_DEBUG_LIST)) {
72 		/*
73 		 * With the hardening version, elide checking if next and prev
74 		 * are NULL, since the immediate dereference of them below would
75 		 * result in a fault if NULL.
76 		 *
77 		 * With the reduced set of checks, we can afford to inline the
78 		 * checks, which also gives the compiler a chance to elide some
79 		 * of them completely if they can be proven at compile-time. If
80 		 * one of the pre-conditions does not hold, the slow-path will
81 		 * show a report which pre-condition failed.
82 		 */
83 		if (likely(next->prev == prev && prev->next == next && new != prev && new != next))
84 			return true;
85 		ret = false;
86 	}
87 
88 	ret &= __list_add_valid_or_report(new, prev, next);
89 	return ret;
90 }
91 
92 /*
93  * Performs the full set of list corruption checks before __list_del_entry().
94  * On list corruption reports a warning, and returns false.
95  */
96 extern bool __list_valid_slowpath __list_del_entry_valid_or_report(struct list_head *entry);
97 
98 /*
99  * Performs list corruption checks before __list_del_entry(). Returns false if a
100  * corruption is detected, true otherwise.
101  *
102  * With CONFIG_LIST_HARDENED only, performs minimal list integrity checking
103  * inline to catch non-faulting corruptions, and only if a corruption is
104  * detected calls the reporting function __list_del_entry_valid_or_report().
105  */
__list_del_entry_valid(struct list_head * entry)106 static __always_inline bool __list_del_entry_valid(struct list_head *entry)
107 {
108 	bool ret = true;
109 
110 	if (!IS_ENABLED(CONFIG_DEBUG_LIST)) {
111 		struct list_head *prev = entry->prev;
112 		struct list_head *next = entry->next;
113 
114 		/*
115 		 * With the hardening version, elide checking if next and prev
116 		 * are NULL, LIST_POISON1 or LIST_POISON2, since the immediate
117 		 * dereference of them below would result in a fault.
118 		 */
119 		if (likely(prev->next == entry && next->prev == entry))
120 			return true;
121 		ret = false;
122 	}
123 
124 	ret &= __list_del_entry_valid_or_report(entry);
125 	return ret;
126 }
127 #else
__list_add_valid(struct list_head * new,struct list_head * prev,struct list_head * next)128 static inline bool __list_add_valid(struct list_head *new,
129 				struct list_head *prev,
130 				struct list_head *next)
131 {
132 	return true;
133 }
__list_del_entry_valid(struct list_head * entry)134 static inline bool __list_del_entry_valid(struct list_head *entry)
135 {
136 	return true;
137 }
138 #endif
139 
140 /*
141  * Insert a new entry between two known consecutive entries.
142  *
143  * This is only for internal list manipulation where we know
144  * the prev/next entries already!
145  */
__list_add(struct list_head * new,struct list_head * prev,struct list_head * next)146 static inline void __list_add(struct list_head *new,
147 			      struct list_head *prev,
148 			      struct list_head *next)
149 {
150 	if (!__list_add_valid(new, prev, next))
151 		return;
152 
153 	next->prev = new;
154 	new->next = next;
155 	new->prev = prev;
156 	WRITE_ONCE(prev->next, new);
157 }
158 
159 /**
160  * list_add - add a new entry
161  * @new: new entry to be added
162  * @head: list head to add it after
163  *
164  * Insert a new entry after the specified head.
165  * This is good for implementing stacks.
166  */
list_add(struct list_head * new,struct list_head * head)167 static inline void list_add(struct list_head *new, struct list_head *head)
168 {
169 	__list_add(new, head, head->next);
170 }
171 
172 
173 /**
174  * list_add_tail - add a new entry
175  * @new: new entry to be added
176  * @head: list head to add it before
177  *
178  * Insert a new entry before the specified head.
179  * This is useful for implementing queues.
180  */
list_add_tail(struct list_head * new,struct list_head * head)181 static inline void list_add_tail(struct list_head *new, struct list_head *head)
182 {
183 	__list_add(new, head->prev, head);
184 }
185 
186 /*
187  * Delete a list entry by making the prev/next entries
188  * point to each other.
189  *
190  * This is only for internal list manipulation where we know
191  * the prev/next entries already!
192  */
__list_del(struct list_head * prev,struct list_head * next)193 static inline void __list_del(struct list_head * prev, struct list_head * next)
194 {
195 	next->prev = prev;
196 	WRITE_ONCE(prev->next, next);
197 }
198 
199 /*
200  * Delete a list entry and clear the 'prev' pointer.
201  *
202  * This is a special-purpose list clearing method used in the networking code
203  * for lists allocated as per-cpu, where we don't want to incur the extra
204  * WRITE_ONCE() overhead of a regular list_del_init(). The code that uses this
205  * needs to check the node 'prev' pointer instead of calling list_empty().
206  */
__list_del_clearprev(struct list_head * entry)207 static inline void __list_del_clearprev(struct list_head *entry)
208 {
209 	__list_del(entry->prev, entry->next);
210 	entry->prev = NULL;
211 }
212 
__list_del_entry(struct list_head * entry)213 static inline void __list_del_entry(struct list_head *entry)
214 {
215 	if (!__list_del_entry_valid(entry))
216 		return;
217 
218 	__list_del(entry->prev, entry->next);
219 }
220 
221 /**
222  * list_del - deletes entry from list.
223  * @entry: the element to delete from the list.
224  * Note: list_empty() on entry does not return true after this, the entry is
225  * in an undefined state.
226  */
list_del(struct list_head * entry)227 static inline void list_del(struct list_head *entry)
228 {
229 	__list_del_entry(entry);
230 	entry->next = LIST_POISON1;
231 	entry->prev = LIST_POISON2;
232 }
233 
234 /**
235  * list_replace - replace old entry by new one
236  * @old : the element to be replaced
237  * @new : the new element to insert
238  *
239  * If @old was empty, it will be overwritten.
240  */
list_replace(struct list_head * old,struct list_head * new)241 static inline void list_replace(struct list_head *old,
242 				struct list_head *new)
243 {
244 	new->next = old->next;
245 	new->next->prev = new;
246 	new->prev = old->prev;
247 	new->prev->next = new;
248 }
249 
250 /**
251  * list_replace_init - replace old entry by new one and initialize the old one
252  * @old : the element to be replaced
253  * @new : the new element to insert
254  *
255  * If @old was empty, it will be overwritten.
256  */
list_replace_init(struct list_head * old,struct list_head * new)257 static inline void list_replace_init(struct list_head *old,
258 				     struct list_head *new)
259 {
260 	list_replace(old, new);
261 	INIT_LIST_HEAD(old);
262 }
263 
264 /**
265  * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
266  * @entry1: the location to place entry2
267  * @entry2: the location to place entry1
268  */
list_swap(struct list_head * entry1,struct list_head * entry2)269 static inline void list_swap(struct list_head *entry1,
270 			     struct list_head *entry2)
271 {
272 	struct list_head *pos = entry2->prev;
273 
274 	list_del(entry2);
275 	list_replace(entry1, entry2);
276 	if (pos == entry1)
277 		pos = entry2;
278 	list_add(entry1, pos);
279 }
280 
281 /**
282  * list_del_init - deletes entry from list and reinitialize it.
283  * @entry: the element to delete from the list.
284  */
list_del_init(struct list_head * entry)285 static inline void list_del_init(struct list_head *entry)
286 {
287 	__list_del_entry(entry);
288 	INIT_LIST_HEAD(entry);
289 }
290 
291 /**
292  * list_move - delete from one list and add as another's head
293  * @list: the entry to move
294  * @head: the head that will precede our entry
295  */
list_move(struct list_head * list,struct list_head * head)296 static inline void list_move(struct list_head *list, struct list_head *head)
297 {
298 	__list_del_entry(list);
299 	list_add(list, head);
300 }
301 
302 /**
303  * list_move_tail - delete from one list and add as another's tail
304  * @list: the entry to move
305  * @head: the head that will follow our entry
306  */
list_move_tail(struct list_head * list,struct list_head * head)307 static inline void list_move_tail(struct list_head *list,
308 				  struct list_head *head)
309 {
310 	__list_del_entry(list);
311 	list_add_tail(list, head);
312 }
313 
314 /**
315  * list_bulk_move_tail - move a subsection of a list to its tail
316  * @head: the head that will follow our entry
317  * @first: first entry to move
318  * @last: last entry to move, can be the same as first
319  *
320  * Move all entries between @first and including @last before @head.
321  * All three entries must belong to the same linked list.
322  */
list_bulk_move_tail(struct list_head * head,struct list_head * first,struct list_head * last)323 static inline void list_bulk_move_tail(struct list_head *head,
324 				       struct list_head *first,
325 				       struct list_head *last)
326 {
327 	first->prev->next = last->next;
328 	last->next->prev = first->prev;
329 
330 	head->prev->next = first;
331 	first->prev = head->prev;
332 
333 	last->next = head;
334 	head->prev = last;
335 }
336 
337 /**
338  * list_is_first -- tests whether @list is the first entry in list @head
339  * @list: the entry to test
340  * @head: the head of the list
341  */
list_is_first(const struct list_head * list,const struct list_head * head)342 static inline int list_is_first(const struct list_head *list, const struct list_head *head)
343 {
344 	return list->prev == head;
345 }
346 
347 /**
348  * list_is_last - tests whether @list is the last entry in list @head
349  * @list: the entry to test
350  * @head: the head of the list
351  */
list_is_last(const struct list_head * list,const struct list_head * head)352 static inline int list_is_last(const struct list_head *list, const struct list_head *head)
353 {
354 	return list->next == head;
355 }
356 
357 /**
358  * list_is_head - tests whether @list is the list @head
359  * @list: the entry to test
360  * @head: the head of the list
361  */
list_is_head(const struct list_head * list,const struct list_head * head)362 static inline int list_is_head(const struct list_head *list, const struct list_head *head)
363 {
364 	return list == head;
365 }
366 
367 /**
368  * list_empty - tests whether a list is empty
369  * @head: the list to test.
370  */
list_empty(const struct list_head * head)371 static inline int list_empty(const struct list_head *head)
372 {
373 	return READ_ONCE(head->next) == head;
374 }
375 
376 /**
377  * list_del_init_careful - deletes entry from list and reinitialize it.
378  * @entry: the element to delete from the list.
379  *
380  * This is the same as list_del_init(), except designed to be used
381  * together with list_empty_careful() in a way to guarantee ordering
382  * of other memory operations.
383  *
384  * Any memory operations done before a list_del_init_careful() are
385  * guaranteed to be visible after a list_empty_careful() test.
386  */
list_del_init_careful(struct list_head * entry)387 static inline void list_del_init_careful(struct list_head *entry)
388 {
389 	__list_del_entry(entry);
390 	WRITE_ONCE(entry->prev, entry);
391 	smp_store_release(&entry->next, entry);
392 }
393 
394 /**
395  * list_empty_careful - tests whether a list is empty and not being modified
396  * @head: the list to test
397  *
398  * Description:
399  * tests whether a list is empty _and_ checks that no other CPU might be
400  * in the process of modifying either member (next or prev)
401  *
402  * NOTE: using list_empty_careful() without synchronization
403  * can only be safe if the only activity that can happen
404  * to the list entry is list_del_init(). Eg. it cannot be used
405  * if another CPU could re-list_add() it.
406  */
list_empty_careful(const struct list_head * head)407 static inline int list_empty_careful(const struct list_head *head)
408 {
409 	struct list_head *next = smp_load_acquire(&head->next);
410 	return list_is_head(next, head) && (next == READ_ONCE(head->prev));
411 }
412 
413 /**
414  * list_rotate_left - rotate the list to the left
415  * @head: the head of the list
416  */
list_rotate_left(struct list_head * head)417 static inline void list_rotate_left(struct list_head *head)
418 {
419 	struct list_head *first;
420 
421 	if (!list_empty(head)) {
422 		first = head->next;
423 		list_move_tail(first, head);
424 	}
425 }
426 
427 /**
428  * list_rotate_to_front() - Rotate list to specific item.
429  * @list: The desired new front of the list.
430  * @head: The head of the list.
431  *
432  * Rotates list so that @list becomes the new front of the list.
433  */
list_rotate_to_front(struct list_head * list,struct list_head * head)434 static inline void list_rotate_to_front(struct list_head *list,
435 					struct list_head *head)
436 {
437 	/*
438 	 * Deletes the list head from the list denoted by @head and
439 	 * places it as the tail of @list, this effectively rotates the
440 	 * list so that @list is at the front.
441 	 */
442 	list_move_tail(head, list);
443 }
444 
445 /**
446  * list_is_singular - tests whether a list has just one entry.
447  * @head: the list to test.
448  */
list_is_singular(const struct list_head * head)449 static inline int list_is_singular(const struct list_head *head)
450 {
451 	return !list_empty(head) && (head->next == head->prev);
452 }
453 
__list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)454 static inline void __list_cut_position(struct list_head *list,
455 		struct list_head *head, struct list_head *entry)
456 {
457 	struct list_head *new_first = entry->next;
458 	list->next = head->next;
459 	list->next->prev = list;
460 	list->prev = entry;
461 	entry->next = list;
462 	head->next = new_first;
463 	new_first->prev = head;
464 }
465 
466 /**
467  * list_cut_position - cut a list into two
468  * @list: a new list to add all removed entries
469  * @head: a list with entries
470  * @entry: an entry within head, could be the head itself
471  *	and if so we won't cut the list
472  *
473  * This helper moves the initial part of @head, up to and
474  * including @entry, from @head to @list. You should
475  * pass on @entry an element you know is on @head. @list
476  * should be an empty list or a list you do not care about
477  * losing its data.
478  *
479  */
list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)480 static inline void list_cut_position(struct list_head *list,
481 		struct list_head *head, struct list_head *entry)
482 {
483 	if (list_empty(head))
484 		return;
485 	if (list_is_singular(head) && !list_is_head(entry, head) && (entry != head->next))
486 		return;
487 	if (list_is_head(entry, head))
488 		INIT_LIST_HEAD(list);
489 	else
490 		__list_cut_position(list, head, entry);
491 }
492 
493 /**
494  * list_cut_before - cut a list into two, before given entry
495  * @list: a new list to add all removed entries
496  * @head: a list with entries
497  * @entry: an entry within head, could be the head itself
498  *
499  * This helper moves the initial part of @head, up to but
500  * excluding @entry, from @head to @list.  You should pass
501  * in @entry an element you know is on @head.  @list should
502  * be an empty list or a list you do not care about losing
503  * its data.
504  * If @entry == @head, all entries on @head are moved to
505  * @list.
506  */
list_cut_before(struct list_head * list,struct list_head * head,struct list_head * entry)507 static inline void list_cut_before(struct list_head *list,
508 				   struct list_head *head,
509 				   struct list_head *entry)
510 {
511 	if (head->next == entry) {
512 		INIT_LIST_HEAD(list);
513 		return;
514 	}
515 	list->next = head->next;
516 	list->next->prev = list;
517 	list->prev = entry->prev;
518 	list->prev->next = list;
519 	head->next = entry;
520 	entry->prev = head;
521 }
522 
__list_splice(const struct list_head * list,struct list_head * prev,struct list_head * next)523 static inline void __list_splice(const struct list_head *list,
524 				 struct list_head *prev,
525 				 struct list_head *next)
526 {
527 	struct list_head *first = list->next;
528 	struct list_head *last = list->prev;
529 
530 	first->prev = prev;
531 	prev->next = first;
532 
533 	last->next = next;
534 	next->prev = last;
535 }
536 
537 /**
538  * list_splice - join two lists, this is designed for stacks
539  * @list: the new list to add.
540  * @head: the place to add it in the first list.
541  */
list_splice(const struct list_head * list,struct list_head * head)542 static inline void list_splice(const struct list_head *list,
543 				struct list_head *head)
544 {
545 	if (!list_empty(list))
546 		__list_splice(list, head, head->next);
547 }
548 
549 /**
550  * list_splice_tail - join two lists, each list being a queue
551  * @list: the new list to add.
552  * @head: the place to add it in the first list.
553  */
list_splice_tail(struct list_head * list,struct list_head * head)554 static inline void list_splice_tail(struct list_head *list,
555 				struct list_head *head)
556 {
557 	if (!list_empty(list))
558 		__list_splice(list, head->prev, head);
559 }
560 
561 /**
562  * list_splice_init - join two lists and reinitialise the emptied list.
563  * @list: the new list to add.
564  * @head: the place to add it in the first list.
565  *
566  * The list at @list is reinitialised
567  */
list_splice_init(struct list_head * list,struct list_head * head)568 static inline void list_splice_init(struct list_head *list,
569 				    struct list_head *head)
570 {
571 	if (!list_empty(list)) {
572 		__list_splice(list, head, head->next);
573 		INIT_LIST_HEAD(list);
574 	}
575 }
576 
577 /**
578  * list_splice_tail_init - join two lists and reinitialise the emptied list
579  * @list: the new list to add.
580  * @head: the place to add it in the first list.
581  *
582  * Each of the lists is a queue.
583  * The list at @list is reinitialised
584  */
list_splice_tail_init(struct list_head * list,struct list_head * head)585 static inline void list_splice_tail_init(struct list_head *list,
586 					 struct list_head *head)
587 {
588 	if (!list_empty(list)) {
589 		__list_splice(list, head->prev, head);
590 		INIT_LIST_HEAD(list);
591 	}
592 }
593 
594 /**
595  * list_entry - get the struct for this entry
596  * @ptr:	the &struct list_head pointer.
597  * @type:	the type of the struct this is embedded in.
598  * @member:	the name of the list_head within the struct.
599  */
600 #define list_entry(ptr, type, member) \
601 	container_of(ptr, type, member)
602 
603 /**
604  * list_first_entry - get the first element from a list
605  * @ptr:	the list head to take the element from.
606  * @type:	the type of the struct this is embedded in.
607  * @member:	the name of the list_head within the struct.
608  *
609  * Note, that list is expected to be not empty.
610  */
611 #define list_first_entry(ptr, type, member) \
612 	list_entry((ptr)->next, type, member)
613 
614 /**
615  * list_last_entry - get the last element from a list
616  * @ptr:	the list head to take the element from.
617  * @type:	the type of the struct this is embedded in.
618  * @member:	the name of the list_head within the struct.
619  *
620  * Note, that list is expected to be not empty.
621  */
622 #define list_last_entry(ptr, type, member) \
623 	list_entry((ptr)->prev, type, member)
624 
625 /**
626  * list_first_entry_or_null - get the first element from a list
627  * @ptr:	the list head to take the element from.
628  * @type:	the type of the struct this is embedded in.
629  * @member:	the name of the list_head within the struct.
630  *
631  * Note that if the list is empty, it returns NULL.
632  */
633 #define list_first_entry_or_null(ptr, type, member) ({ \
634 	struct list_head *head__ = (ptr); \
635 	struct list_head *pos__ = READ_ONCE(head__->next); \
636 	pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
637 })
638 
639 /**
640  * list_next_entry - get the next element in list
641  * @pos:	the type * to cursor
642  * @member:	the name of the list_head within the struct.
643  */
644 #define list_next_entry(pos, member) \
645 	list_entry((pos)->member.next, typeof(*(pos)), member)
646 
647 /**
648  * list_next_entry_circular - get the next element in list
649  * @pos:	the type * to cursor.
650  * @head:	the list head to take the element from.
651  * @member:	the name of the list_head within the struct.
652  *
653  * Wraparound if pos is the last element (return the first element).
654  * Note, that list is expected to be not empty.
655  */
656 #define list_next_entry_circular(pos, head, member) \
657 	(list_is_last(&(pos)->member, head) ? \
658 	list_first_entry(head, typeof(*(pos)), member) : list_next_entry(pos, member))
659 
660 /**
661  * list_prev_entry - get the prev element in list
662  * @pos:	the type * to cursor
663  * @member:	the name of the list_head within the struct.
664  */
665 #define list_prev_entry(pos, member) \
666 	list_entry((pos)->member.prev, typeof(*(pos)), member)
667 
668 /**
669  * list_prev_entry_circular - get the prev element in list
670  * @pos:	the type * to cursor.
671  * @head:	the list head to take the element from.
672  * @member:	the name of the list_head within the struct.
673  *
674  * Wraparound if pos is the first element (return the last element).
675  * Note, that list is expected to be not empty.
676  */
677 #define list_prev_entry_circular(pos, head, member) \
678 	(list_is_first(&(pos)->member, head) ? \
679 	list_last_entry(head, typeof(*(pos)), member) : list_prev_entry(pos, member))
680 
681 /**
682  * list_for_each	-	iterate over a list
683  * @pos:	the &struct list_head to use as a loop cursor.
684  * @head:	the head for your list.
685  */
686 #define list_for_each(pos, head) \
687 	for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
688 
689 /**
690  * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
691  * @pos:	the &struct list_head to use as a loop cursor.
692  * @head:	the head for your list.
693  */
694 #define list_for_each_rcu(pos, head)		  \
695 	for (pos = rcu_dereference((head)->next); \
696 	     !list_is_head(pos, (head)); \
697 	     pos = rcu_dereference(pos->next))
698 
699 /**
700  * list_for_each_continue - continue iteration over a list
701  * @pos:	the &struct list_head to use as a loop cursor.
702  * @head:	the head for your list.
703  *
704  * Continue to iterate over a list, continuing after the current position.
705  */
706 #define list_for_each_continue(pos, head) \
707 	for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)
708 
709 /**
710  * list_for_each_prev	-	iterate over a list backwards
711  * @pos:	the &struct list_head to use as a loop cursor.
712  * @head:	the head for your list.
713  */
714 #define list_for_each_prev(pos, head) \
715 	for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)
716 
717 /**
718  * list_for_each_safe - iterate over a list safe against removal of list entry
719  * @pos:	the &struct list_head to use as a loop cursor.
720  * @n:		another &struct list_head to use as temporary storage
721  * @head:	the head for your list.
722  */
723 #define list_for_each_safe(pos, n, head) \
724 	for (pos = (head)->next, n = pos->next; \
725 	     !list_is_head(pos, (head)); \
726 	     pos = n, n = pos->next)
727 
728 /**
729  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
730  * @pos:	the &struct list_head to use as a loop cursor.
731  * @n:		another &struct list_head to use as temporary storage
732  * @head:	the head for your list.
733  */
734 #define list_for_each_prev_safe(pos, n, head) \
735 	for (pos = (head)->prev, n = pos->prev; \
736 	     !list_is_head(pos, (head)); \
737 	     pos = n, n = pos->prev)
738 
739 /**
740  * list_count_nodes - count nodes in the list
741  * @head:	the head for your list.
742  */
list_count_nodes(struct list_head * head)743 static inline size_t list_count_nodes(struct list_head *head)
744 {
745 	struct list_head *pos;
746 	size_t count = 0;
747 
748 	list_for_each(pos, head)
749 		count++;
750 
751 	return count;
752 }
753 
754 /**
755  * list_entry_is_head - test if the entry points to the head of the list
756  * @pos:	the type * to cursor
757  * @head:	the head for your list.
758  * @member:	the name of the list_head within the struct.
759  */
760 #define list_entry_is_head(pos, head, member)				\
761 	(&pos->member == (head))
762 
763 /**
764  * list_for_each_entry	-	iterate over list of given type
765  * @pos:	the type * to use as a loop cursor.
766  * @head:	the head for your list.
767  * @member:	the name of the list_head within the struct.
768  */
769 #define list_for_each_entry(pos, head, member)				\
770 	for (pos = list_first_entry(head, typeof(*pos), member);	\
771 	     !list_entry_is_head(pos, head, member);			\
772 	     pos = list_next_entry(pos, member))
773 
774 /**
775  * list_for_each_entry_reverse - iterate backwards over list of given type.
776  * @pos:	the type * to use as a loop cursor.
777  * @head:	the head for your list.
778  * @member:	the name of the list_head within the struct.
779  */
780 #define list_for_each_entry_reverse(pos, head, member)			\
781 	for (pos = list_last_entry(head, typeof(*pos), member);		\
782 	     !list_entry_is_head(pos, head, member); 			\
783 	     pos = list_prev_entry(pos, member))
784 
785 /**
786  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
787  * @pos:	the type * to use as a start point
788  * @head:	the head of the list
789  * @member:	the name of the list_head within the struct.
790  *
791  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
792  */
793 #define list_prepare_entry(pos, head, member) \
794 	((pos) ? : list_entry(head, typeof(*pos), member))
795 
796 /**
797  * list_for_each_entry_continue - continue iteration over list of given type
798  * @pos:	the type * to use as a loop cursor.
799  * @head:	the head for your list.
800  * @member:	the name of the list_head within the struct.
801  *
802  * Continue to iterate over list of given type, continuing after
803  * the current position.
804  */
805 #define list_for_each_entry_continue(pos, head, member) 		\
806 	for (pos = list_next_entry(pos, member);			\
807 	     !list_entry_is_head(pos, head, member);			\
808 	     pos = list_next_entry(pos, member))
809 
810 /**
811  * list_for_each_entry_continue_reverse - iterate backwards from the given point
812  * @pos:	the type * to use as a loop cursor.
813  * @head:	the head for your list.
814  * @member:	the name of the list_head within the struct.
815  *
816  * Start to iterate over list of given type backwards, continuing after
817  * the current position.
818  */
819 #define list_for_each_entry_continue_reverse(pos, head, member)		\
820 	for (pos = list_prev_entry(pos, member);			\
821 	     !list_entry_is_head(pos, head, member);			\
822 	     pos = list_prev_entry(pos, member))
823 
824 /**
825  * list_for_each_entry_from - iterate over list of given type from the current point
826  * @pos:	the type * to use as a loop cursor.
827  * @head:	the head for your list.
828  * @member:	the name of the list_head within the struct.
829  *
830  * Iterate over list of given type, continuing from current position.
831  */
832 #define list_for_each_entry_from(pos, head, member) 			\
833 	for (; !list_entry_is_head(pos, head, member);			\
834 	     pos = list_next_entry(pos, member))
835 
836 /**
837  * list_for_each_entry_from_reverse - iterate backwards over list of given type
838  *                                    from the current point
839  * @pos:	the type * to use as a loop cursor.
840  * @head:	the head for your list.
841  * @member:	the name of the list_head within the struct.
842  *
843  * Iterate backwards over list of given type, continuing from current position.
844  */
845 #define list_for_each_entry_from_reverse(pos, head, member)		\
846 	for (; !list_entry_is_head(pos, head, member);			\
847 	     pos = list_prev_entry(pos, member))
848 
849 /**
850  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
851  * @pos:	the type * to use as a loop cursor.
852  * @n:		another type * to use as temporary storage
853  * @head:	the head for your list.
854  * @member:	the name of the list_head within the struct.
855  */
856 #define list_for_each_entry_safe(pos, n, head, member)			\
857 	for (pos = list_first_entry(head, typeof(*pos), member),	\
858 		n = list_next_entry(pos, member);			\
859 	     !list_entry_is_head(pos, head, member); 			\
860 	     pos = n, n = list_next_entry(n, member))
861 
862 /**
863  * list_for_each_entry_safe_continue - continue list iteration safe against removal
864  * @pos:	the type * to use as a loop cursor.
865  * @n:		another type * to use as temporary storage
866  * @head:	the head for your list.
867  * @member:	the name of the list_head within the struct.
868  *
869  * Iterate over list of given type, continuing after current point,
870  * safe against removal of list entry.
871  */
872 #define list_for_each_entry_safe_continue(pos, n, head, member) 		\
873 	for (pos = list_next_entry(pos, member), 				\
874 		n = list_next_entry(pos, member);				\
875 	     !list_entry_is_head(pos, head, member);				\
876 	     pos = n, n = list_next_entry(n, member))
877 
878 /**
879  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
880  * @pos:	the type * to use as a loop cursor.
881  * @n:		another type * to use as temporary storage
882  * @head:	the head for your list.
883  * @member:	the name of the list_head within the struct.
884  *
885  * Iterate over list of given type from current point, safe against
886  * removal of list entry.
887  */
888 #define list_for_each_entry_safe_from(pos, n, head, member) 			\
889 	for (n = list_next_entry(pos, member);					\
890 	     !list_entry_is_head(pos, head, member);				\
891 	     pos = n, n = list_next_entry(n, member))
892 
893 /**
894  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
895  * @pos:	the type * to use as a loop cursor.
896  * @n:		another type * to use as temporary storage
897  * @head:	the head for your list.
898  * @member:	the name of the list_head within the struct.
899  *
900  * Iterate backwards over list of given type, safe against removal
901  * of list entry.
902  */
903 #define list_for_each_entry_safe_reverse(pos, n, head, member)		\
904 	for (pos = list_last_entry(head, typeof(*pos), member),		\
905 		n = list_prev_entry(pos, member);			\
906 	     !list_entry_is_head(pos, head, member); 			\
907 	     pos = n, n = list_prev_entry(n, member))
908 
909 /**
910  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
911  * @pos:	the loop cursor used in the list_for_each_entry_safe loop
912  * @n:		temporary storage used in list_for_each_entry_safe
913  * @member:	the name of the list_head within the struct.
914  *
915  * list_safe_reset_next is not safe to use in general if the list may be
916  * modified concurrently (eg. the lock is dropped in the loop body). An
917  * exception to this is if the cursor element (pos) is pinned in the list,
918  * and list_safe_reset_next is called after re-taking the lock and before
919  * completing the current iteration of the loop body.
920  */
921 #define list_safe_reset_next(pos, n, member)				\
922 	n = list_next_entry(pos, member)
923 
924 /*
925  * Double linked lists with a single pointer list head.
926  * Mostly useful for hash tables where the two pointer list head is
927  * too wasteful.
928  * You lose the ability to access the tail in O(1).
929  */
930 
931 #define HLIST_HEAD_INIT { .first = NULL }
932 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
933 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
INIT_HLIST_NODE(struct hlist_node * h)934 static inline void INIT_HLIST_NODE(struct hlist_node *h)
935 {
936 	h->next = NULL;
937 	h->pprev = NULL;
938 }
939 
940 /**
941  * hlist_unhashed - Has node been removed from list and reinitialized?
942  * @h: Node to be checked
943  *
944  * Not that not all removal functions will leave a node in unhashed
945  * state.  For example, hlist_nulls_del_init_rcu() does leave the
946  * node in unhashed state, but hlist_nulls_del() does not.
947  */
hlist_unhashed(const struct hlist_node * h)948 static inline int hlist_unhashed(const struct hlist_node *h)
949 {
950 	return !h->pprev;
951 }
952 
953 /**
954  * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
955  * @h: Node to be checked
956  *
957  * This variant of hlist_unhashed() must be used in lockless contexts
958  * to avoid potential load-tearing.  The READ_ONCE() is paired with the
959  * various WRITE_ONCE() in hlist helpers that are defined below.
960  */
hlist_unhashed_lockless(const struct hlist_node * h)961 static inline int hlist_unhashed_lockless(const struct hlist_node *h)
962 {
963 	return !READ_ONCE(h->pprev);
964 }
965 
966 /**
967  * hlist_empty - Is the specified hlist_head structure an empty hlist?
968  * @h: Structure to check.
969  */
hlist_empty(const struct hlist_head * h)970 static inline int hlist_empty(const struct hlist_head *h)
971 {
972 	return !READ_ONCE(h->first);
973 }
974 
__hlist_del(struct hlist_node * n)975 static inline void __hlist_del(struct hlist_node *n)
976 {
977 	struct hlist_node *next = n->next;
978 	struct hlist_node **pprev = n->pprev;
979 
980 	WRITE_ONCE(*pprev, next);
981 	if (next)
982 		WRITE_ONCE(next->pprev, pprev);
983 }
984 
985 /**
986  * hlist_del - Delete the specified hlist_node from its list
987  * @n: Node to delete.
988  *
989  * Note that this function leaves the node in hashed state.  Use
990  * hlist_del_init() or similar instead to unhash @n.
991  */
hlist_del(struct hlist_node * n)992 static inline void hlist_del(struct hlist_node *n)
993 {
994 	__hlist_del(n);
995 	n->next = LIST_POISON1;
996 	n->pprev = LIST_POISON2;
997 }
998 
999 /**
1000  * hlist_del_init - Delete the specified hlist_node from its list and initialize
1001  * @n: Node to delete.
1002  *
1003  * Note that this function leaves the node in unhashed state.
1004  */
hlist_del_init(struct hlist_node * n)1005 static inline void hlist_del_init(struct hlist_node *n)
1006 {
1007 	if (!hlist_unhashed(n)) {
1008 		__hlist_del(n);
1009 		INIT_HLIST_NODE(n);
1010 	}
1011 }
1012 
1013 /**
1014  * hlist_add_head - add a new entry at the beginning of the hlist
1015  * @n: new entry to be added
1016  * @h: hlist head to add it after
1017  *
1018  * Insert a new entry after the specified head.
1019  * This is good for implementing stacks.
1020  */
hlist_add_head(struct hlist_node * n,struct hlist_head * h)1021 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
1022 {
1023 	struct hlist_node *first = h->first;
1024 	WRITE_ONCE(n->next, first);
1025 	if (first)
1026 		WRITE_ONCE(first->pprev, &n->next);
1027 	WRITE_ONCE(h->first, n);
1028 	WRITE_ONCE(n->pprev, &h->first);
1029 }
1030 
1031 /**
1032  * hlist_add_before - add a new entry before the one specified
1033  * @n: new entry to be added
1034  * @next: hlist node to add it before, which must be non-NULL
1035  */
hlist_add_before(struct hlist_node * n,struct hlist_node * next)1036 static inline void hlist_add_before(struct hlist_node *n,
1037 				    struct hlist_node *next)
1038 {
1039 	WRITE_ONCE(n->pprev, next->pprev);
1040 	WRITE_ONCE(n->next, next);
1041 	WRITE_ONCE(next->pprev, &n->next);
1042 	WRITE_ONCE(*(n->pprev), n);
1043 }
1044 
1045 /**
1046  * hlist_add_behind - add a new entry after the one specified
1047  * @n: new entry to be added
1048  * @prev: hlist node to add it after, which must be non-NULL
1049  */
hlist_add_behind(struct hlist_node * n,struct hlist_node * prev)1050 static inline void hlist_add_behind(struct hlist_node *n,
1051 				    struct hlist_node *prev)
1052 {
1053 	WRITE_ONCE(n->next, prev->next);
1054 	WRITE_ONCE(prev->next, n);
1055 	WRITE_ONCE(n->pprev, &prev->next);
1056 
1057 	if (n->next)
1058 		WRITE_ONCE(n->next->pprev, &n->next);
1059 }
1060 
1061 /**
1062  * hlist_add_fake - create a fake hlist consisting of a single headless node
1063  * @n: Node to make a fake list out of
1064  *
1065  * This makes @n appear to be its own predecessor on a headless hlist.
1066  * The point of this is to allow things like hlist_del() to work correctly
1067  * in cases where there is no list.
1068  */
hlist_add_fake(struct hlist_node * n)1069 static inline void hlist_add_fake(struct hlist_node *n)
1070 {
1071 	n->pprev = &n->next;
1072 }
1073 
1074 /**
1075  * hlist_fake: Is this node a fake hlist?
1076  * @h: Node to check for being a self-referential fake hlist.
1077  */
hlist_fake(struct hlist_node * h)1078 static inline bool hlist_fake(struct hlist_node *h)
1079 {
1080 	return h->pprev == &h->next;
1081 }
1082 
1083 /**
1084  * hlist_is_singular_node - is node the only element of the specified hlist?
1085  * @n: Node to check for singularity.
1086  * @h: Header for potentially singular list.
1087  *
1088  * Check whether the node is the only node of the head without
1089  * accessing head, thus avoiding unnecessary cache misses.
1090  */
1091 static inline bool
hlist_is_singular_node(struct hlist_node * n,struct hlist_head * h)1092 hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
1093 {
1094 	return !n->next && n->pprev == &h->first;
1095 }
1096 
1097 /**
1098  * hlist_move_list - Move an hlist
1099  * @old: hlist_head for old list.
1100  * @new: hlist_head for new list.
1101  *
1102  * Move a list from one list head to another. Fixup the pprev
1103  * reference of the first entry if it exists.
1104  */
hlist_move_list(struct hlist_head * old,struct hlist_head * new)1105 static inline void hlist_move_list(struct hlist_head *old,
1106 				   struct hlist_head *new)
1107 {
1108 	new->first = old->first;
1109 	if (new->first)
1110 		new->first->pprev = &new->first;
1111 	old->first = NULL;
1112 }
1113 
1114 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
1115 
1116 #define hlist_for_each(pos, head) \
1117 	for (pos = (head)->first; pos ; pos = pos->next)
1118 
1119 #define hlist_for_each_safe(pos, n, head) \
1120 	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
1121 	     pos = n)
1122 
1123 #define hlist_entry_safe(ptr, type, member) \
1124 	({ typeof(ptr) ____ptr = (ptr); \
1125 	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
1126 	})
1127 
1128 /**
1129  * hlist_for_each_entry	- iterate over list of given type
1130  * @pos:	the type * to use as a loop cursor.
1131  * @head:	the head for your list.
1132  * @member:	the name of the hlist_node within the struct.
1133  */
1134 #define hlist_for_each_entry(pos, head, member)				\
1135 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
1136 	     pos;							\
1137 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1138 
1139 /**
1140  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1141  * @pos:	the type * to use as a loop cursor.
1142  * @member:	the name of the hlist_node within the struct.
1143  */
1144 #define hlist_for_each_entry_continue(pos, member)			\
1145 	for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1146 	     pos;							\
1147 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1148 
1149 /**
1150  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1151  * @pos:	the type * to use as a loop cursor.
1152  * @member:	the name of the hlist_node within the struct.
1153  */
1154 #define hlist_for_each_entry_from(pos, member)				\
1155 	for (; pos;							\
1156 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1157 
1158 /**
1159  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1160  * @pos:	the type * to use as a loop cursor.
1161  * @n:		a &struct hlist_node to use as temporary storage
1162  * @head:	the head for your list.
1163  * @member:	the name of the hlist_node within the struct.
1164  */
1165 #define hlist_for_each_entry_safe(pos, n, head, member) 		\
1166 	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1167 	     pos && ({ n = pos->member.next; 1; });			\
1168 	     pos = hlist_entry_safe(n, typeof(*pos), member))
1169 
1170 #endif
1171