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