include/linux/rculist.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 #ifndef _LINUX_RCULIST_H
   3 #define _LINUX_RCULIST_H
   4
   5 #ifdef __KERNEL__
   6
   7 /*
   8  * RCU-protected list version
   9  */
  10 #include <linux/list.h>
  11 #include <linux/rcupdate.h>
  12
  13 /*
  14  * Why is there no list_empty_rcu()?  Because list_empty() serves this
  15  * purpose.  The list_empty() function fetches the RCU-protected pointer
  16  * and compares it to the address of the list head, but neither dereferences
  17  * this pointer itself nor provides this pointer to the caller.  Therefore,
  18  * it is not necessary to use rcu_dereference(), so that list_empty() can
  19  * be used anywhere you would want to use a list_empty_rcu().
  20  */
  21
  22 /*
  23  * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
  24  * @list: list to be initialized
  25  *
  26  * You should instead use INIT_LIST_HEAD() for normal initialization and
  27  * cleanup tasks, when readers have no access to the list being initialized.
  28  * However, if the list being initialized is visible to readers, you
  29  * need to keep the compiler from being too mischievous.
  30  */
  31 static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
  32 {
  33         WRITE_ONCE(list->next, list);
  34         WRITE_ONCE(list->prev, list);
  35 }
  36
  37 /*
  38  * return the ->next pointer of a list_head in an rcu safe
  39  * way, we must not access it directly
  40  */
  41 #define list_next_rcu(list)     (*((struct list_head __rcu **)(&(list)->next)))
  42
  43 /**
  44  * list_tail_rcu - returns the prev pointer of the head of the list
  45  * @head: the head of the list
  46  *
  47  * Note: This should only be used with the list header, and even then
  48  * only if list_del() and similar primitives are not also used on the
  49  * list header.
  50  */
  51 #define list_tail_rcu(head)     (*((struct list_head __rcu **)(&(head)->prev)))
  52
  53 /*
  54  * Check during list traversal that we are within an RCU reader
  55  */
  56
  57 #define check_arg_count_one(dummy)
  58
  59 #ifdef CONFIG_PROVE_RCU_LIST
  60 #define __list_check_rcu(dummy, cond, extra...)                         \
  61         ({                                                              \
  62         check_arg_count_one(extra);                                     \
  63         RCU_LOCKDEP_WARN(!(cond) && !rcu_read_lock_any_held(),          \
  64                          "RCU-list traversed in non-reader section!");  \
  65         })
  66
  67 #define __list_check_srcu(cond)                                  \
  68         ({                                                               \
  69         RCU_LOCKDEP_WARN(!(cond),                                        \
  70                 "RCU-list traversed without holding the required lock!");\
  71         })
  72 #else
  73 #define __list_check_rcu(dummy, cond, extra...)                         \
  74         ({ check_arg_count_one(extra); })
  75
  76 #define __list_check_srcu(cond) ({ })
  77 #endif
  78
  79 /*
  80  * Insert a new entry between two known consecutive entries.
  81  *
  82  * This is only for internal list manipulation where we know
  83  * the prev/next entries already!
  84  */
  85 static inline void __list_add_rcu(struct list_head *new,
  86                 struct list_head *prev, struct list_head *next)
  87 {
  88         if (!__list_add_valid(new, prev, next))
  89                 return;
  90
  91         new->next = next;
  92         new->prev = prev;
  93         rcu_assign_pointer(list_next_rcu(prev), new);
  94         next->prev = new;
  95 }
  96
  97 /**
  98  * list_add_rcu - add a new entry to rcu-protected list
  99  * @new: new entry to be added
 100  * @head: list head to add it after
 101  *
 102  * Insert a new entry after the specified head.
 103  * This is good for implementing stacks.
 104  *
 105  * The caller must take whatever precautions are necessary
 106  * (such as holding appropriate locks) to avoid racing
 107  * with another list-mutation primitive, such as list_add_rcu()
 108  * or list_del_rcu(), running on this same list.
 109  * However, it is perfectly legal to run concurrently with
 110  * the _rcu list-traversal primitives, such as
 111  * list_for_each_entry_rcu().
 112  */
 113 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
 114 {
 115         __list_add_rcu(new, head, head->next);
 116 }
 117
 118 /**
 119  * list_add_tail_rcu - add a new entry to rcu-protected list
 120  * @new: new entry to be added
 121  * @head: list head to add it before
 122  *
 123  * Insert a new entry before the specified head.
 124  * This is useful for implementing queues.
 125  *
 126  * The caller must take whatever precautions are necessary
 127  * (such as holding appropriate locks) to avoid racing
 128  * with another list-mutation primitive, such as list_add_tail_rcu()
 129  * or list_del_rcu(), running on this same list.
 130  * However, it is perfectly legal to run concurrently with
 131  * the _rcu list-traversal primitives, such as
 132  * list_for_each_entry_rcu().
 133  */
 134 static inline void list_add_tail_rcu(struct list_head *new,
 135                                         struct list_head *head)
 136 {
 137         __list_add_rcu(new, head->prev, head);
 138 }
 139
 140 /**
 141  * list_del_rcu - deletes entry from list without re-initialization
 142  * @entry: the element to delete from the list.
 143  *
 144  * Note: list_empty() on entry does not return true after this,
 145  * the entry is in an undefined state. It is useful for RCU based
 146  * lockfree traversal.
 147  *
 148  * In particular, it means that we can not poison the forward
 149  * pointers that may still be used for walking the list.
 150  *
 151  * The caller must take whatever precautions are necessary
 152  * (such as holding appropriate locks) to avoid racing
 153  * with another list-mutation primitive, such as list_del_rcu()
 154  * or list_add_rcu(), running on this same list.
 155  * However, it is perfectly legal to run concurrently with
 156  * the _rcu list-traversal primitives, such as
 157  * list_for_each_entry_rcu().
 158  *
 159  * Note that the caller is not permitted to immediately free
 160  * the newly deleted entry.  Instead, either synchronize_rcu()
 161  * or call_rcu() must be used to defer freeing until an RCU
 162  * grace period has elapsed.
 163  */
 164 static inline void list_del_rcu(struct list_head *entry)
 165 {
 166         __list_del_entry(entry);
 167         entry->prev = LIST_POISON2;
 168 }
 169
 170 /**
 171  * hlist_del_init_rcu - deletes entry from hash list with re-initialization
 172  * @n: the element to delete from the hash list.
 173  *
 174  * Note: list_unhashed() on the node return true after this. It is
 175  * useful for RCU based read lockfree traversal if the writer side
 176  * must know if the list entry is still hashed or already unhashed.
 177  *
 178  * In particular, it means that we can not poison the forward pointers
 179  * that may still be used for walking the hash list and we can only
 180  * zero the pprev pointer so list_unhashed() will return true after
 181  * this.
 182  *
 183  * The caller must take whatever precautions are necessary (such as
 184  * holding appropriate locks) to avoid racing with another
 185  * list-mutation primitive, such as hlist_add_head_rcu() or
 186  * hlist_del_rcu(), running on this same list.  However, it is
 187  * perfectly legal to run concurrently with the _rcu list-traversal
 188  * primitives, such as hlist_for_each_entry_rcu().
 189  */
 190 static inline void hlist_del_init_rcu(struct hlist_node *n)
 191 {
 192         if (!hlist_unhashed(n)) {
 193                 __hlist_del(n);
 194                 WRITE_ONCE(n->pprev, NULL);
 195         }
 196 }
 197
 198 /**
 199  * list_replace_rcu - replace old entry by new one
 200  * @old : the element to be replaced
 201  * @new : the new element to insert
 202  *
 203  * The @old entry will be replaced with the @new entry atomically.
 204  * Note: @old should not be empty.
 205  */
 206 static inline void list_replace_rcu(struct list_head *old,
 207                                 struct list_head *new)
 208 {
 209         new->next = old->next;
 210         new->prev = old->prev;
 211         rcu_assign_pointer(list_next_rcu(new->prev), new);
 212         new->next->prev = new;
 213         old->prev = LIST_POISON2;
 214 }
 215
 216 /**
 217  * __list_splice_init_rcu - join an RCU-protected list into an existing list.
 218  * @list:       the RCU-protected list to splice
 219  * @prev:       points to the last element of the existing list
 220  * @next:       points to the first element of the existing list
 221  * @sync:       synchronize_rcu, synchronize_rcu_expedited, ...
 222  *
 223  * The list pointed to by @prev and @next can be RCU-read traversed
 224  * concurrently with this function.
 225  *
 226  * Note that this function blocks.
 227  *
 228  * Important note: the caller must take whatever action is necessary to prevent
 229  * any other updates to the existing list.  In principle, it is possible to
 230  * modify the list as soon as sync() begins execution. If this sort of thing
 231  * becomes necessary, an alternative version based on call_rcu() could be
 232  * created.  But only if -really- needed -- there is no shortage of RCU API
 233  * members.
 234  */
 235 static inline void __list_splice_init_rcu(struct list_head *list,
 236                                           struct list_head *prev,
 237                                           struct list_head *next,
 238                                           void (*sync)(void))
 239 {
 240         struct list_head *first = list->next;
 241         struct list_head *last = list->prev;
 242
 243         /*
 244          * "first" and "last" tracking list, so initialize it.  RCU readers
 245          * have access to this list, so we must use INIT_LIST_HEAD_RCU()
 246          * instead of INIT_LIST_HEAD().
 247          */
 248
 249         INIT_LIST_HEAD_RCU(list);
 250
 251         /*
 252          * At this point, the list body still points to the source list.
 253          * Wait for any readers to finish using the list before splicing
 254          * the list body into the new list.  Any new readers will see
 255          * an empty list.
 256          */
 257
 258         sync();
 259         ASSERT_EXCLUSIVE_ACCESS(*first);
 260         ASSERT_EXCLUSIVE_ACCESS(*last);
 261
 262         /*
 263          * Readers are finished with the source list, so perform splice.
 264          * The order is important if the new list is global and accessible
 265          * to concurrent RCU readers.  Note that RCU readers are not
 266          * permitted to traverse the prev pointers without excluding
 267          * this function.
 268          */
 269
 270         last->next = next;
 271         rcu_assign_pointer(list_next_rcu(prev), first);
 272         first->prev = prev;
 273         next->prev = last;
 274 }
 275
 276 /**
 277  * list_splice_init_rcu - splice an RCU-protected list into an existing list,
 278  *                        designed for stacks.
 279  * @list:       the RCU-protected list to splice
 280  * @head:       the place in the existing list to splice the first list into
 281  * @sync:       synchronize_rcu, synchronize_rcu_expedited, ...
 282  */
 283 static inline void list_splice_init_rcu(struct list_head *list,
 284                                         struct list_head *head,
 285                                         void (*sync)(void))
 286 {
 287         if (!list_empty(list))
 288                 __list_splice_init_rcu(list, head, head->next, sync);
 289 }
 290
 291 /**
 292  * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
 293  *                             list, designed for queues.
 294  * @list:       the RCU-protected list to splice
 295  * @head:       the place in the existing list to splice the first list into
 296  * @sync:       synchronize_rcu, synchronize_rcu_expedited, ...
 297  */
 298 static inline void list_splice_tail_init_rcu(struct list_head *list,
 299                                              struct list_head *head,
 300                                              void (*sync)(void))
 301 {
 302         if (!list_empty(list))
 303                 __list_splice_init_rcu(list, head->prev, head, sync);
 304 }
 305
 306 /**
 307  * list_entry_rcu - get the struct for this entry
 308  * @ptr:        the &struct list_head pointer.
 309  * @type:       the type of the struct this is embedded in.
 310  * @member:     the name of the list_head within the struct.
 311  *
 312  * This primitive may safely run concurrently with the _rcu list-mutation
 313  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
 314  */
 315 #define list_entry_rcu(ptr, type, member) \
 316         container_of(READ_ONCE(ptr), type, member)
 317
 318 /*
 319  * Where are list_empty_rcu() and list_first_entry_rcu()?
 320  *
 321  * Implementing those functions following their counterparts list_empty() and
 322  * list_first_entry() is not advisable because they lead to subtle race
 323  * conditions as the following snippet shows:
 324  *
 325  * if (!list_empty_rcu(mylist)) {
 326  *      struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
 327  *      do_something(bar);
 328  * }
 329  *
 330  * The list may not be empty when list_empty_rcu checks it, but it may be when
 331  * list_first_entry_rcu rereads the ->next pointer.
 332  *
 333  * Rereading the ->next pointer is not a problem for list_empty() and
 334  * list_first_entry() because they would be protected by a lock that blocks
 335  * writers.
 336  *
 337  * See list_first_or_null_rcu for an alternative.
 338  */
 339
 340 /**
 341  * list_first_or_null_rcu - get the first element from a list
 342  * @ptr:        the list head to take the element from.
 343  * @type:       the type of the struct this is embedded in.
 344  * @member:     the name of the list_head within the struct.
 345  *
 346  * Note that if the list is empty, it returns NULL.
 347  *
 348  * This primitive may safely run concurrently with the _rcu list-mutation
 349  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
 350  */
 351 #define list_first_or_null_rcu(ptr, type, member) \
 352 ({ \
 353         struct list_head *__ptr = (ptr); \
 354         struct list_head *__next = READ_ONCE(__ptr->next); \
 355         likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
 356 })
 357
 358 /**
 359  * list_next_or_null_rcu - get the first element from a list
 360  * @head:       the head for the list.
 361  * @ptr:        the list head to take the next element from.
 362  * @type:       the type of the struct this is embedded in.
 363  * @member:     the name of the list_head within the struct.
 364  *
 365  * Note that if the ptr is at the end of the list, NULL is returned.
 366  *
 367  * This primitive may safely run concurrently with the _rcu list-mutation
 368  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
 369  */
 370 #define list_next_or_null_rcu(head, ptr, type, member) \
 371 ({ \
 372         struct list_head *__head = (head); \
 373         struct list_head *__ptr = (ptr); \
 374         struct list_head *__next = READ_ONCE(__ptr->next); \
 375         likely(__next != __head) ? list_entry_rcu(__next, type, \
 376                                                   member) : NULL; \
 377 })
 378
 379 /**
 380  * list_for_each_entry_rcu      -       iterate over rcu list of given type
 381  * @pos:        the type * to use as a loop cursor.
 382  * @head:       the head for your list.
 383  * @member:     the name of the list_head within the struct.
 384  * @cond:       optional lockdep expression if called from non-RCU protection.
 385  *
 386  * This list-traversal primitive may safely run concurrently with
 387  * the _rcu list-mutation primitives such as list_add_rcu()
 388  * as long as the traversal is guarded by rcu_read_lock().
 389  */
 390 #define list_for_each_entry_rcu(pos, head, member, cond...)             \
 391         for (__list_check_rcu(dummy, ## cond, 0),                       \
 392              pos = list_entry_rcu((head)->next, typeof(*pos), member);  \
 393                 &pos->member != (head);                                 \
 394                 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 395
 396 /**
 397  * list_for_each_entry_srcu     -       iterate over rcu list of given type
 398  * @pos:        the type * to use as a loop cursor.
 399  * @head:       the head for your list.
 400  * @member:     the name of the list_head within the struct.
 401  * @cond:       lockdep expression for the lock required to traverse the list.
 402  *
 403  * This list-traversal primitive may safely run concurrently with
 404  * the _rcu list-mutation primitives such as list_add_rcu()
 405  * as long as the traversal is guarded by srcu_read_lock().
 406  * The lockdep expression srcu_read_lock_held() can be passed as the
 407  * cond argument from read side.
 408  */
 409 #define list_for_each_entry_srcu(pos, head, member, cond)               \
 410         for (__list_check_srcu(cond),                                   \
 411              pos = list_entry_rcu((head)->next, typeof(*pos), member);  \
 412                 &pos->member != (head);                                 \
 413                 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 414
 415 /**
 416  * list_entry_lockless - get the struct for this entry
 417  * @ptr:        the &struct list_head pointer.
 418  * @type:       the type of the struct this is embedded in.
 419  * @member:     the name of the list_head within the struct.
 420  *
 421  * This primitive may safely run concurrently with the _rcu
 422  * list-mutation primitives such as list_add_rcu(), but requires some
 423  * implicit RCU read-side guarding.  One example is running within a special
 424  * exception-time environment where preemption is disabled and where lockdep
 425  * cannot be invoked.  Another example is when items are added to the list,
 426  * but never deleted.
 427  */
 428 #define list_entry_lockless(ptr, type, member) \
 429         container_of((typeof(ptr))READ_ONCE(ptr), type, member)
 430
 431 /**
 432  * list_for_each_entry_lockless - iterate over rcu list of given type
 433  * @pos:        the type * to use as a loop cursor.
 434  * @head:       the head for your list.
 435  * @member:     the name of the list_struct within the struct.
 436  *
 437  * This primitive may safely run concurrently with the _rcu
 438  * list-mutation primitives such as list_add_rcu(), but requires some
 439  * implicit RCU read-side guarding.  One example is running within a special
 440  * exception-time environment where preemption is disabled and where lockdep
 441  * cannot be invoked.  Another example is when items are added to the list,
 442  * but never deleted.
 443  */
 444 #define list_for_each_entry_lockless(pos, head, member) \
 445         for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
 446              &pos->member != (head); \
 447              pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
 448
 449 /**
 450  * list_for_each_entry_continue_rcu - continue iteration over list of given type
 451  * @pos:        the type * to use as a loop cursor.
 452  * @head:       the head for your list.
 453  * @member:     the name of the list_head within the struct.
 454  *
 455  * Continue to iterate over list of given type, continuing after
 456  * the current position which must have been in the list when the RCU read
 457  * lock was taken.
 458  * This would typically require either that you obtained the node from a
 459  * previous walk of the list in the same RCU read-side critical section, or
 460  * that you held some sort of non-RCU reference (such as a reference count)
 461  * to keep the node alive *and* in the list.
 462  *
 463  * This iterator is similar to list_for_each_entry_from_rcu() except
 464  * this starts after the given position and that one starts at the given
 465  * position.
 466  */
 467 #define list_for_each_entry_continue_rcu(pos, head, member)             \
 468         for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
 469              &pos->member != (head);    \
 470              pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 471
 472 /**
 473  * list_for_each_entry_from_rcu - iterate over a list from current point
 474  * @pos:        the type * to use as a loop cursor.
 475  * @head:       the head for your list.
 476  * @member:     the name of the list_node within the struct.
 477  *
 478  * Iterate over the tail of a list starting from a given position,
 479  * which must have been in the list when the RCU read lock was taken.
 480  * This would typically require either that you obtained the node from a
 481  * previous walk of the list in the same RCU read-side critical section, or
 482  * that you held some sort of non-RCU reference (such as a reference count)
 483  * to keep the node alive *and* in the list.
 484  *
 485  * This iterator is similar to list_for_each_entry_continue_rcu() except
 486  * this starts from the given position and that one starts from the position
 487  * after the given position.
 488  */
 489 #define list_for_each_entry_from_rcu(pos, head, member)                 \
 490         for (; &(pos)->member != (head);                                        \
 491                 pos = list_entry_rcu(pos->member.next, typeof(*(pos)), member))
 492
 493 /**
 494  * hlist_del_rcu - deletes entry from hash list without re-initialization
 495  * @n: the element to delete from the hash list.
 496  *
 497  * Note: list_unhashed() on entry does not return true after this,
 498  * the entry is in an undefined state. It is useful for RCU based
 499  * lockfree traversal.
 500  *
 501  * In particular, it means that we can not poison the forward
 502  * pointers that may still be used for walking the hash list.
 503  *
 504  * The caller must take whatever precautions are necessary
 505  * (such as holding appropriate locks) to avoid racing
 506  * with another list-mutation primitive, such as hlist_add_head_rcu()
 507  * or hlist_del_rcu(), running on this same list.
 508  * However, it is perfectly legal to run concurrently with
 509  * the _rcu list-traversal primitives, such as
 510  * hlist_for_each_entry().
 511  */
 512 static inline void hlist_del_rcu(struct hlist_node *n)
 513 {
 514         __hlist_del(n);
 515         WRITE_ONCE(n->pprev, LIST_POISON2);
 516 }
 517
 518 /**
 519  * hlist_replace_rcu - replace old entry by new one
 520  * @old : the element to be replaced
 521  * @new : the new element to insert
 522  *
 523  * The @old entry will be replaced with the @new entry atomically.
 524  */
 525 static inline void hlist_replace_rcu(struct hlist_node *old,
 526                                         struct hlist_node *new)
 527 {
 528         struct hlist_node *next = old->next;
 529
 530         new->next = next;
 531         WRITE_ONCE(new->pprev, old->pprev);
 532         rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
 533         if (next)
 534                 WRITE_ONCE(new->next->pprev, &new->next);
 535         WRITE_ONCE(old->pprev, LIST_POISON2);
 536 }
 537
 538 /**
 539  * hlists_swap_heads_rcu - swap the lists the hlist heads point to
 540  * @left:  The hlist head on the left
 541  * @right: The hlist head on the right
 542  *
 543  * The lists start out as [@left  ][node1 ... ] and
 544  *                        [@right ][node2 ... ]
 545  * The lists end up as    [@left  ][node2 ... ]
 546  *                        [@right ][node1 ... ]
 547  */
 548 static inline void hlists_swap_heads_rcu(struct hlist_head *left, struct hlist_head *right)
 549 {
 550         struct hlist_node *node1 = left->first;
 551         struct hlist_node *node2 = right->first;
 552
 553         rcu_assign_pointer(left->first, node2);
 554         rcu_assign_pointer(right->first, node1);
 555         WRITE_ONCE(node2->pprev, &left->first);
 556         WRITE_ONCE(node1->pprev, &right->first);
 557 }
 558
 559 /*
 560  * return the first or the next element in an RCU protected hlist
 561  */
 562 #define hlist_first_rcu(head)   (*((struct hlist_node __rcu **)(&(head)->first)))
 563 #define hlist_next_rcu(node)    (*((struct hlist_node __rcu **)(&(node)->next)))
 564 #define hlist_pprev_rcu(node)   (*((struct hlist_node __rcu **)((node)->pprev)))
 565
 566 /**
 567  * hlist_add_head_rcu
 568  * @n: the element to add to the hash list.
 569  * @h: the list to add to.
 570  *
 571  * Description:
 572  * Adds the specified element to the specified hlist,
 573  * while permitting racing traversals.
 574  *
 575  * The caller must take whatever precautions are necessary
 576  * (such as holding appropriate locks) to avoid racing
 577  * with another list-mutation primitive, such as hlist_add_head_rcu()
 578  * or hlist_del_rcu(), running on this same list.
 579  * However, it is perfectly legal to run concurrently with
 580  * the _rcu list-traversal primitives, such as
 581  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 582  * problems on Alpha CPUs.  Regardless of the type of CPU, the
 583  * list-traversal primitive must be guarded by rcu_read_lock().
 584  */
 585 static inline void hlist_add_head_rcu(struct hlist_node *n,
 586                                         struct hlist_head *h)
 587 {
 588         struct hlist_node *first = h->first;
 589
 590         n->next = first;
 591         WRITE_ONCE(n->pprev, &h->first);
 592         rcu_assign_pointer(hlist_first_rcu(h), n);
 593         if (first)
 594                 WRITE_ONCE(first->pprev, &n->next);
 595 }
 596
 597 /**
 598  * hlist_add_tail_rcu
 599  * @n: the element to add to the hash list.
 600  * @h: the list to add to.
 601  *
 602  * Description:
 603  * Adds the specified element to the specified hlist,
 604  * while permitting racing traversals.
 605  *
 606  * The caller must take whatever precautions are necessary
 607  * (such as holding appropriate locks) to avoid racing
 608  * with another list-mutation primitive, such as hlist_add_head_rcu()
 609  * or hlist_del_rcu(), running on this same list.
 610  * However, it is perfectly legal to run concurrently with
 611  * the _rcu list-traversal primitives, such as
 612  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 613  * problems on Alpha CPUs.  Regardless of the type of CPU, the
 614  * list-traversal primitive must be guarded by rcu_read_lock().
 615  */
 616 static inline void hlist_add_tail_rcu(struct hlist_node *n,
 617                                       struct hlist_head *h)
 618 {
 619         struct hlist_node *i, *last = NULL;
 620
 621         /* Note: write side code, so rcu accessors are not needed. */
 622         for (i = h->first; i; i = i->next)
 623                 last = i;
 624
 625         if (last) {
 626                 n->next = last->next;
 627                 WRITE_ONCE(n->pprev, &last->next);
 628                 rcu_assign_pointer(hlist_next_rcu(last), n);
 629         } else {
 630                 hlist_add_head_rcu(n, h);
 631         }
 632 }
 633
 634 /**
 635  * hlist_add_before_rcu
 636  * @n: the new element to add to the hash list.
 637  * @next: the existing element to add the new element before.
 638  *
 639  * Description:
 640  * Adds the specified element to the specified hlist
 641  * before the specified node while permitting racing traversals.
 642  *
 643  * The caller must take whatever precautions are necessary
 644  * (such as holding appropriate locks) to avoid racing
 645  * with another list-mutation primitive, such as hlist_add_head_rcu()
 646  * or hlist_del_rcu(), running on this same list.
 647  * However, it is perfectly legal to run concurrently with
 648  * the _rcu list-traversal primitives, such as
 649  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 650  * problems on Alpha CPUs.
 651  */
 652 static inline void hlist_add_before_rcu(struct hlist_node *n,
 653                                         struct hlist_node *next)
 654 {
 655         WRITE_ONCE(n->pprev, next->pprev);
 656         n->next = next;
 657         rcu_assign_pointer(hlist_pprev_rcu(n), n);
 658         WRITE_ONCE(next->pprev, &n->next);
 659 }
 660
 661 /**
 662  * hlist_add_behind_rcu
 663  * @n: the new element to add to the hash list.
 664  * @prev: the existing element to add the new element after.
 665  *
 666  * Description:
 667  * Adds the specified element to the specified hlist
 668  * after the specified node while permitting racing traversals.
 669  *
 670  * The caller must take whatever precautions are necessary
 671  * (such as holding appropriate locks) to avoid racing
 672  * with another list-mutation primitive, such as hlist_add_head_rcu()
 673  * or hlist_del_rcu(), running on this same list.
 674  * However, it is perfectly legal to run concurrently with
 675  * the _rcu list-traversal primitives, such as
 676  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 677  * problems on Alpha CPUs.
 678  */
 679 static inline void hlist_add_behind_rcu(struct hlist_node *n,
 680                                         struct hlist_node *prev)
 681 {
 682         n->next = prev->next;
 683         WRITE_ONCE(n->pprev, &prev->next);
 684         rcu_assign_pointer(hlist_next_rcu(prev), n);
 685         if (n->next)
 686                 WRITE_ONCE(n->next->pprev, &n->next);
 687 }
 688
 689 #define __hlist_for_each_rcu(pos, head)                         \
 690         for (pos = rcu_dereference(hlist_first_rcu(head));      \
 691              pos;                                               \
 692              pos = rcu_dereference(hlist_next_rcu(pos)))
 693
 694 /**
 695  * hlist_for_each_entry_rcu - iterate over rcu list of given type
 696  * @pos:        the type * to use as a loop cursor.
 697  * @head:       the head for your list.
 698  * @member:     the name of the hlist_node within the struct.
 699  * @cond:       optional lockdep expression if called from non-RCU protection.
 700  *
 701  * This list-traversal primitive may safely run concurrently with
 702  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 703  * as long as the traversal is guarded by rcu_read_lock().
 704  */
 705 #define hlist_for_each_entry_rcu(pos, head, member, cond...)            \
 706         for (__list_check_rcu(dummy, ## cond, 0),                       \
 707              pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
 708                         typeof(*(pos)), member);                        \
 709                 pos;                                                    \
 710                 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
 711                         &(pos)->member)), typeof(*(pos)), member))
 712
 713 /**
 714  * hlist_for_each_entry_srcu - iterate over rcu list of given type
 715  * @pos:        the type * to use as a loop cursor.
 716  * @head:       the head for your list.
 717  * @member:     the name of the hlist_node within the struct.
 718  * @cond:       lockdep expression for the lock required to traverse the list.
 719  *
 720  * This list-traversal primitive may safely run concurrently with
 721  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 722  * as long as the traversal is guarded by srcu_read_lock().
 723  * The lockdep expression srcu_read_lock_held() can be passed as the
 724  * cond argument from read side.
 725  */
 726 #define hlist_for_each_entry_srcu(pos, head, member, cond)              \
 727         for (__list_check_srcu(cond),                                   \
 728              pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
 729                         typeof(*(pos)), member);                        \
 730                 pos;                                                    \
 731                 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
 732                         &(pos)->member)), typeof(*(pos)), member))
 733
 734 /**
 735  * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
 736  * @pos:        the type * to use as a loop cursor.
 737  * @head:       the head for your list.
 738  * @member:     the name of the hlist_node within the struct.
 739  *
 740  * This list-traversal primitive may safely run concurrently with
 741  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 742  * as long as the traversal is guarded by rcu_read_lock().
 743  *
 744  * This is the same as hlist_for_each_entry_rcu() except that it does
 745  * not do any RCU debugging or tracing.
 746  */
 747 #define hlist_for_each_entry_rcu_notrace(pos, head, member)                     \
 748         for (pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_first_rcu(head)),\
 749                         typeof(*(pos)), member);                        \
 750                 pos;                                                    \
 751                 pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_next_rcu(\
 752                         &(pos)->member)), typeof(*(pos)), member))
 753
 754 /**
 755  * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
 756  * @pos:        the type * to use as a loop cursor.
 757  * @head:       the head for your list.
 758  * @member:     the name of the hlist_node within the struct.
 759  *
 760  * This list-traversal primitive may safely run concurrently with
 761  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 762  * as long as the traversal is guarded by rcu_read_lock().
 763  */
 764 #define hlist_for_each_entry_rcu_bh(pos, head, member)                  \
 765         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
 766                         typeof(*(pos)), member);                        \
 767                 pos;                                                    \
 768                 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
 769                         &(pos)->member)), typeof(*(pos)), member))
 770
 771 /**
 772  * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
 773  * @pos:        the type * to use as a loop cursor.
 774  * @member:     the name of the hlist_node within the struct.
 775  */
 776 #define hlist_for_each_entry_continue_rcu(pos, member)                  \
 777         for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
 778                         &(pos)->member)), typeof(*(pos)), member);      \
 779              pos;                                                       \
 780              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
 781                         &(pos)->member)), typeof(*(pos)), member))
 782
 783 /**
 784  * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
 785  * @pos:        the type * to use as a loop cursor.
 786  * @member:     the name of the hlist_node within the struct.
 787  */
 788 #define hlist_for_each_entry_continue_rcu_bh(pos, member)               \
 789         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
 790                         &(pos)->member)), typeof(*(pos)), member);      \
 791              pos;                                                       \
 792              pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
 793                         &(pos)->member)), typeof(*(pos)), member))
 794
 795 /**
 796  * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
 797  * @pos:        the type * to use as a loop cursor.
 798  * @member:     the name of the hlist_node within the struct.
 799  */
 800 #define hlist_for_each_entry_from_rcu(pos, member)                      \
 801         for (; pos;                                                     \
 802              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
 803                         &(pos)->member)), typeof(*(pos)), member))
 804
 805 #endif  /* __KERNEL__ */
 806 #endif