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