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 #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