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