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