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 */
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 */
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 */
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
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 }
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 */
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 */
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 */
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 */
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 */
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
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
449 static inline int list_is_singular(const struct list_head *head)
450 {
451 return !list_empty(head) && (head->next == head->prev);
452 }
453
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 */
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 */
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
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 */
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 */
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 */
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 */
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_reverse - iterate backwards over a list
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_reverse(pos, head) \
695 for (pos = (head)->prev; pos != (head); pos = pos->prev)
696
697 /**
698 * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
699 * @pos: the &struct list_head to use as a loop cursor.
700 * @head: the head for your list.
701 */
702 #define list_for_each_rcu(pos, head) \
703 for (pos = rcu_dereference((head)->next); \
704 !list_is_head(pos, (head)); \
705 pos = rcu_dereference(pos->next))
706
707 /**
708 * list_for_each_continue - continue iteration over a list
709 * @pos: the &struct list_head to use as a loop cursor.
710 * @head: the head for your list.
711 *
712 * Continue to iterate over a list, continuing after the current position.
713 */
714 #define list_for_each_continue(pos, head) \
715 for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)
716
717 /**
718 * list_for_each_prev - iterate over a list backwards
719 * @pos: the &struct list_head to use as a loop cursor.
720 * @head: the head for your list.
721 */
722 #define list_for_each_prev(pos, head) \
723 for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)
724
725 /**
726 * list_for_each_safe - iterate over a list safe against removal of list entry
727 * @pos: the &struct list_head to use as a loop cursor.
728 * @n: another &struct list_head to use as temporary storage
729 * @head: the head for your list.
730 */
731 #define list_for_each_safe(pos, n, head) \
732 for (pos = (head)->next, n = pos->next; \
733 !list_is_head(pos, (head)); \
734 pos = n, n = pos->next)
735
736 /**
737 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
738 * @pos: the &struct list_head to use as a loop cursor.
739 * @n: another &struct list_head to use as temporary storage
740 * @head: the head for your list.
741 */
742 #define list_for_each_prev_safe(pos, n, head) \
743 for (pos = (head)->prev, n = pos->prev; \
744 !list_is_head(pos, (head)); \
745 pos = n, n = pos->prev)
746
747 /**
748 * list_count_nodes - count nodes in the list
749 * @head: the head for your list.
750 */
751 static inline size_t list_count_nodes(struct list_head *head)
752 {
753 struct list_head *pos;
754 size_t count = 0;
755
756 list_for_each(pos, head)
757 count++;
758
759 return count;
760 }
761
762 /**
763 * list_entry_is_head - test if the entry points to the head of the list
764 * @pos: the type * to cursor
765 * @head: the head for your list.
766 * @member: the name of the list_head within the struct.
767 */
768 #define list_entry_is_head(pos, head, member) \
769 list_is_head(&pos->member, (head))
770
771 /**
772 * list_for_each_entry - iterate over 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 list_head within the struct.
776 */
777 #define list_for_each_entry(pos, head, member) \
778 for (pos = list_first_entry(head, typeof(*pos), member); \
779 !list_entry_is_head(pos, head, member); \
780 pos = list_next_entry(pos, member))
781
782 /**
783 * list_for_each_entry_reverse - iterate backwards over list of given type.
784 * @pos: the type * to use as a loop cursor.
785 * @head: the head for your list.
786 * @member: the name of the list_head within the struct.
787 */
788 #define list_for_each_entry_reverse(pos, head, member) \
789 for (pos = list_last_entry(head, typeof(*pos), member); \
790 !list_entry_is_head(pos, head, member); \
791 pos = list_prev_entry(pos, member))
792
793 /**
794 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
795 * @pos: the type * to use as a start point
796 * @head: the head of the list
797 * @member: the name of the list_head within the struct.
798 *
799 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
800 */
801 #define list_prepare_entry(pos, head, member) \
802 ((pos) ? : list_entry(head, typeof(*pos), member))
803
804 /**
805 * list_for_each_entry_continue - continue iteration over list of given type
806 * @pos: the type * to use as a loop cursor.
807 * @head: the head for your list.
808 * @member: the name of the list_head within the struct.
809 *
810 * Continue to iterate over list of given type, continuing after
811 * the current position.
812 */
813 #define list_for_each_entry_continue(pos, head, member) \
814 for (pos = list_next_entry(pos, member); \
815 !list_entry_is_head(pos, head, member); \
816 pos = list_next_entry(pos, member))
817
818 /**
819 * list_for_each_entry_continue_reverse - iterate backwards from the given point
820 * @pos: the type * to use as a loop cursor.
821 * @head: the head for your list.
822 * @member: the name of the list_head within the struct.
823 *
824 * Start to iterate over list of given type backwards, continuing after
825 * the current position.
826 */
827 #define list_for_each_entry_continue_reverse(pos, head, member) \
828 for (pos = list_prev_entry(pos, member); \
829 !list_entry_is_head(pos, head, member); \
830 pos = list_prev_entry(pos, member))
831
832 /**
833 * list_for_each_entry_from - iterate over list of given type from the current point
834 * @pos: the type * to use as a loop cursor.
835 * @head: the head for your list.
836 * @member: the name of the list_head within the struct.
837 *
838 * Iterate over list of given type, continuing from current position.
839 */
840 #define list_for_each_entry_from(pos, head, member) \
841 for (; !list_entry_is_head(pos, head, member); \
842 pos = list_next_entry(pos, member))
843
844 /**
845 * list_for_each_entry_from_reverse - iterate backwards over list of given type
846 * from the current point
847 * @pos: the type * to use as a loop cursor.
848 * @head: the head for your list.
849 * @member: the name of the list_head within the struct.
850 *
851 * Iterate backwards over list of given type, continuing from current position.
852 */
853 #define list_for_each_entry_from_reverse(pos, head, member) \
854 for (; !list_entry_is_head(pos, head, member); \
855 pos = list_prev_entry(pos, member))
856
857 /**
858 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
859 * @pos: the type * to use as a loop cursor.
860 * @n: another type * to use as temporary storage
861 * @head: the head for your list.
862 * @member: the name of the list_head within the struct.
863 */
864 #define list_for_each_entry_safe(pos, n, head, member) \
865 for (pos = list_first_entry(head, typeof(*pos), member), \
866 n = list_next_entry(pos, member); \
867 !list_entry_is_head(pos, head, member); \
868 pos = n, n = list_next_entry(n, member))
869
870 /**
871 * list_for_each_entry_safe_continue - continue list iteration safe against removal
872 * @pos: the type * to use as a loop cursor.
873 * @n: another type * to use as temporary storage
874 * @head: the head for your list.
875 * @member: the name of the list_head within the struct.
876 *
877 * Iterate over list of given type, continuing after current point,
878 * safe against removal of list entry.
879 */
880 #define list_for_each_entry_safe_continue(pos, n, head, member) \
881 for (pos = list_next_entry(pos, member), \
882 n = list_next_entry(pos, member); \
883 !list_entry_is_head(pos, head, member); \
884 pos = n, n = list_next_entry(n, member))
885
886 /**
887 * list_for_each_entry_safe_from - iterate over list from current point safe against removal
888 * @pos: the type * to use as a loop cursor.
889 * @n: another type * to use as temporary storage
890 * @head: the head for your list.
891 * @member: the name of the list_head within the struct.
892 *
893 * Iterate over list of given type from current point, safe against
894 * removal of list entry.
895 */
896 #define list_for_each_entry_safe_from(pos, n, head, member) \
897 for (n = list_next_entry(pos, member); \
898 !list_entry_is_head(pos, head, member); \
899 pos = n, n = list_next_entry(n, member))
900
901 /**
902 * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
903 * @pos: the type * to use as a loop cursor.
904 * @n: another type * to use as temporary storage
905 * @head: the head for your list.
906 * @member: the name of the list_head within the struct.
907 *
908 * Iterate backwards over list of given type, safe against removal
909 * of list entry.
910 */
911 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
912 for (pos = list_last_entry(head, typeof(*pos), member), \
913 n = list_prev_entry(pos, member); \
914 !list_entry_is_head(pos, head, member); \
915 pos = n, n = list_prev_entry(n, member))
916
917 /**
918 * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
919 * @pos: the loop cursor used in the list_for_each_entry_safe loop
920 * @n: temporary storage used in list_for_each_entry_safe
921 * @member: the name of the list_head within the struct.
922 *
923 * list_safe_reset_next is not safe to use in general if the list may be
924 * modified concurrently (eg. the lock is dropped in the loop body). An
925 * exception to this is if the cursor element (pos) is pinned in the list,
926 * and list_safe_reset_next is called after re-taking the lock and before
927 * completing the current iteration of the loop body.
928 */
929 #define list_safe_reset_next(pos, n, member) \
930 n = list_next_entry(pos, member)
931
932 /*
933 * Double linked lists with a single pointer list head.
934 * Mostly useful for hash tables where the two pointer list head is
935 * too wasteful.
936 * You lose the ability to access the tail in O(1).
937 */
938
939 #define HLIST_HEAD_INIT { .first = NULL }
940 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
941 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
942 static inline void INIT_HLIST_NODE(struct hlist_node *h)
943 {
944 h->next = NULL;
945 h->pprev = NULL;
946 }
947
948 /**
949 * hlist_unhashed - Has node been removed from list and reinitialized?
950 * @h: Node to be checked
951 *
952 * Not that not all removal functions will leave a node in unhashed
953 * state. For example, hlist_nulls_del_init_rcu() does leave the
954 * node in unhashed state, but hlist_nulls_del() does not.
955 */
956 static inline int hlist_unhashed(const struct hlist_node *h)
957 {
958 return !h->pprev;
959 }
960
961 /**
962 * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
963 * @h: Node to be checked
964 *
965 * This variant of hlist_unhashed() must be used in lockless contexts
966 * to avoid potential load-tearing. The READ_ONCE() is paired with the
967 * various WRITE_ONCE() in hlist helpers that are defined below.
968 */
969 static inline int hlist_unhashed_lockless(const struct hlist_node *h)
970 {
971 return !READ_ONCE(h->pprev);
972 }
973
974 /**
975 * hlist_empty - Is the specified hlist_head structure an empty hlist?
976 * @h: Structure to check.
977 */
978 static inline int hlist_empty(const struct hlist_head *h)
979 {
980 return !READ_ONCE(h->first);
981 }
982
983 static inline void __hlist_del(struct hlist_node *n)
984 {
985 struct hlist_node *next = n->next;
986 struct hlist_node **pprev = n->pprev;
987
988 WRITE_ONCE(*pprev, next);
989 if (next)
990 WRITE_ONCE(next->pprev, pprev);
991 }
992
993 /**
994 * hlist_del - Delete the specified hlist_node from its list
995 * @n: Node to delete.
996 *
997 * Note that this function leaves the node in hashed state. Use
998 * hlist_del_init() or similar instead to unhash @n.
999 */
1000 static inline void hlist_del(struct hlist_node *n)
1001 {
1002 __hlist_del(n);
1003 n->next = LIST_POISON1;
1004 n->pprev = LIST_POISON2;
1005 }
1006
1007 /**
1008 * hlist_del_init - Delete the specified hlist_node from its list and initialize
1009 * @n: Node to delete.
1010 *
1011 * Note that this function leaves the node in unhashed state.
1012 */
1013 static inline void hlist_del_init(struct hlist_node *n)
1014 {
1015 if (!hlist_unhashed(n)) {
1016 __hlist_del(n);
1017 INIT_HLIST_NODE(n);
1018 }
1019 }
1020
1021 /**
1022 * hlist_add_head - add a new entry at the beginning of the hlist
1023 * @n: new entry to be added
1024 * @h: hlist head to add it after
1025 *
1026 * Insert a new entry after the specified head.
1027 * This is good for implementing stacks.
1028 */
1029 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
1030 {
1031 struct hlist_node *first = h->first;
1032 WRITE_ONCE(n->next, first);
1033 if (first)
1034 WRITE_ONCE(first->pprev, &n->next);
1035 WRITE_ONCE(h->first, n);
1036 WRITE_ONCE(n->pprev, &h->first);
1037 }
1038
1039 /**
1040 * hlist_add_before - add a new entry before the one specified
1041 * @n: new entry to be added
1042 * @next: hlist node to add it before, which must be non-NULL
1043 */
1044 static inline void hlist_add_before(struct hlist_node *n,
1045 struct hlist_node *next)
1046 {
1047 WRITE_ONCE(n->pprev, next->pprev);
1048 WRITE_ONCE(n->next, next);
1049 WRITE_ONCE(next->pprev, &n->next);
1050 WRITE_ONCE(*(n->pprev), n);
1051 }
1052
1053 /**
1054 * hlist_add_behind - add a new entry after the one specified
1055 * @n: new entry to be added
1056 * @prev: hlist node to add it after, which must be non-NULL
1057 */
1058 static inline void hlist_add_behind(struct hlist_node *n,
1059 struct hlist_node *prev)
1060 {
1061 WRITE_ONCE(n->next, prev->next);
1062 WRITE_ONCE(prev->next, n);
1063 WRITE_ONCE(n->pprev, &prev->next);
1064
1065 if (n->next)
1066 WRITE_ONCE(n->next->pprev, &n->next);
1067 }
1068
1069 /**
1070 * hlist_add_fake - create a fake hlist consisting of a single headless node
1071 * @n: Node to make a fake list out of
1072 *
1073 * This makes @n appear to be its own predecessor on a headless hlist.
1074 * The point of this is to allow things like hlist_del() to work correctly
1075 * in cases where there is no list.
1076 */
1077 static inline void hlist_add_fake(struct hlist_node *n)
1078 {
1079 n->pprev = &n->next;
1080 }
1081
1082 /**
1083 * hlist_fake: Is this node a fake hlist?
1084 * @h: Node to check for being a self-referential fake hlist.
1085 */
1086 static inline bool hlist_fake(struct hlist_node *h)
1087 {
1088 return h->pprev == &h->next;
1089 }
1090
1091 /**
1092 * hlist_is_singular_node - is node the only element of the specified hlist?
1093 * @n: Node to check for singularity.
1094 * @h: Header for potentially singular list.
1095 *
1096 * Check whether the node is the only node of the head without
1097 * accessing head, thus avoiding unnecessary cache misses.
1098 */
1099 static inline bool
1100 hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
1101 {
1102 return !n->next && n->pprev == &h->first;
1103 }
1104
1105 /**
1106 * hlist_move_list - Move an hlist
1107 * @old: hlist_head for old list.
1108 * @new: hlist_head for new list.
1109 *
1110 * Move a list from one list head to another. Fixup the pprev
1111 * reference of the first entry if it exists.
1112 */
1113 static inline void hlist_move_list(struct hlist_head *old,
1114 struct hlist_head *new)
1115 {
1116 new->first = old->first;
1117 if (new->first)
1118 new->first->pprev = &new->first;
1119 old->first = NULL;
1120 }
1121
1122 /**
1123 * hlist_splice_init() - move all entries from one list to another
1124 * @from: hlist_head from which entries will be moved
1125 * @last: last entry on the @from list
1126 * @to: hlist_head to which entries will be moved
1127 *
1128 * @to can be empty, @from must contain at least @last.
1129 */
1130 static inline void hlist_splice_init(struct hlist_head *from,
1131 struct hlist_node *last,
1132 struct hlist_head *to)
1133 {
1134 if (to->first)
1135 to->first->pprev = &last->next;
1136 last->next = to->first;
1137 to->first = from->first;
1138 from->first->pprev = &to->first;
1139 from->first = NULL;
1140 }
1141
1142 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
1143
1144 #define hlist_for_each(pos, head) \
1145 for (pos = (head)->first; pos ; pos = pos->next)
1146
1147 #define hlist_for_each_safe(pos, n, head) \
1148 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
1149 pos = n)
1150
1151 #define hlist_entry_safe(ptr, type, member) \
1152 ({ typeof(ptr) ____ptr = (ptr); \
1153 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
1154 })
1155
1156 /**
1157 * hlist_for_each_entry - iterate over list of given type
1158 * @pos: the type * to use as a loop cursor.
1159 * @head: the head for your list.
1160 * @member: the name of the hlist_node within the struct.
1161 */
1162 #define hlist_for_each_entry(pos, head, member) \
1163 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
1164 pos; \
1165 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1166
1167 /**
1168 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1169 * @pos: the type * to use as a loop cursor.
1170 * @member: the name of the hlist_node within the struct.
1171 */
1172 #define hlist_for_each_entry_continue(pos, member) \
1173 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1174 pos; \
1175 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1176
1177 /**
1178 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1179 * @pos: the type * to use as a loop cursor.
1180 * @member: the name of the hlist_node within the struct.
1181 */
1182 #define hlist_for_each_entry_from(pos, member) \
1183 for (; pos; \
1184 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1185
1186 /**
1187 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1188 * @pos: the type * to use as a loop cursor.
1189 * @n: a &struct hlist_node to use as temporary storage
1190 * @head: the head for your list.
1191 * @member: the name of the hlist_node within the struct.
1192 */
1193 #define hlist_for_each_entry_safe(pos, n, head, member) \
1194 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1195 pos && ({ n = pos->member.next; 1; }); \
1196 pos = hlist_entry_safe(n, typeof(*pos), member))
1197
1198 /**
1199 * hlist_count_nodes - count nodes in the hlist
1200 * @head: the head for your hlist.
1201 */
1202 static inline size_t hlist_count_nodes(struct hlist_head *head)
1203 {
1204 struct hlist_node *pos;
1205 size_t count = 0;
1206
1207 hlist_for_each(pos, head)
1208 count++;
1209
1210 return count;
1211 }
1212
1213 #endif
1214
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.