include/linux/rculist.h

   1 #ifndef _LINUX_RCULIST_H
   2 #define _LINUX_RCULIST_H
   3
   4 #ifdef __KERNEL__
   5
   6 /*
   7  * RCU-protected list version
   8  */
   9 #include <linux/list.h>
  10 #include <linux/rcupdate.h>
  11
  12 /*
  13  * Why is there no list_empty_rcu()?  Because list_empty() serves this
  14  * purpose.  The list_empty() function fetches the RCU-protected pointer
  15  * and compares it to the address of the list head, but neither dereferences
  16  * this pointer itself nor provides this pointer to the caller.  Therefore,
  17  * it is not necessary to use rcu_dereference(), so that list_empty() can
  18  * be used anywhere you would want to use a list_empty_rcu().
  19  */
  20
  21 /*
  22  * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
  23  * @list: list to be initialized
  24  *
  25  * You should instead use INIT_LIST_HEAD() for normal initialization and
  26  * cleanup tasks, when readers have no access to the list being initialized.
  27  * However, if the list being initialized is visible to readers, you
  28  * need to keep the compiler from being too mischievous.
  29  */
  30 static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
  31 {
  32         WRITE_ONCE(list->next, list);
  33         WRITE_ONCE(list->prev, list);
  34 }
  35
  36 /*
  37  * return the ->next pointer of a list_head in an rcu safe
  38  * way, we must not access it directly
  39  */
  40 #define list_next_rcu(list)     (*((struct list_head __rcu **)(&(list)->next)))
  41
  42 /*
  43  * Insert a new entry between two known consecutive entries.
  44  *
  45  * This is only for internal list manipulation where we know
  46  * the prev/next entries already!
  47  */
  48 #ifndef CONFIG_DEBUG_LIST
  49 static inline void __list_add_rcu(struct list_head *new,
  50                 struct list_head *prev, struct list_head *next)
  51 {
  52         new->next = next;
  53         new->prev = prev;
  54         rcu_assign_pointer(list_next_rcu(prev), new);
  55         next->prev = new;
  56 }
  57 #else
  58 void __list_add_rcu(struct list_head *new,
  59                     struct list_head *prev, struct list_head *next);
  60 #endif
  61
  62 /**
  63  * list_add_rcu - add a new entry to rcu-protected list
  64  * @new: new entry to be added
  65  * @head: list head to add it after
  66  *
  67  * Insert a new entry after the specified head.
  68  * This is good for implementing stacks.
  69  *
  70  * The caller must take whatever precautions are necessary
  71  * (such as holding appropriate locks) to avoid racing
  72  * with another list-mutation primitive, such as list_add_rcu()
  73  * or list_del_rcu(), running on this same list.
  74  * However, it is perfectly legal to run concurrently with
  75  * the _rcu list-traversal primitives, such as
  76  * list_for_each_entry_rcu().
  77  */
  78 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
  79 {
  80         __list_add_rcu(new, head, head->next);
  81 }
  82
  83 /**
  84  * list_add_tail_rcu - add a new entry to rcu-protected list
  85  * @new: new entry to be added
  86  * @head: list head to add it before
  87  *
  88  * Insert a new entry before the specified head.
  89  * This is useful for implementing queues.
  90  *
  91  * The caller must take whatever precautions are necessary
  92  * (such as holding appropriate locks) to avoid racing
  93  * with another list-mutation primitive, such as list_add_tail_rcu()
  94  * or list_del_rcu(), running on this same list.
  95  * However, it is perfectly legal to run concurrently with
  96  * the _rcu list-traversal primitives, such as
  97  * list_for_each_entry_rcu().
  98  */
  99 static inline void list_add_tail_rcu(struct list_head *new,
 100                                         struct list_head *head)
 101 {
 102         __list_add_rcu(new, head->prev, head);
 103 }
 104
 105 /**
 106  * list_del_rcu - deletes entry from list without re-initialization
 107  * @entry: the element to delete from the list.
 108  *
 109  * Note: list_empty() on entry does not return true after this,
 110  * the entry is in an undefined state. It is useful for RCU based
 111  * lockfree traversal.
 112  *
 113  * In particular, it means that we can not poison the forward
 114  * pointers that may still be used for walking the list.
 115  *
 116  * The caller must take whatever precautions are necessary
 117  * (such as holding appropriate locks) to avoid racing
 118  * with another list-mutation primitive, such as list_del_rcu()
 119  * or list_add_rcu(), running on this same list.
 120  * However, it is perfectly legal to run concurrently with
 121  * the _rcu list-traversal primitives, such as
 122  * list_for_each_entry_rcu().
 123  *
 124  * Note that the caller is not permitted to immediately free
 125  * the newly deleted entry.  Instead, either synchronize_rcu()
 126  * or call_rcu() must be used to defer freeing until an RCU
 127  * grace period has elapsed.
 128  */
 129 static inline void list_del_rcu(struct list_head *entry)
 130 {
 131         __list_del_entry(entry);
 132         entry->prev = LIST_POISON2;
 133 }
 134
 135 /**
 136  * hlist_del_init_rcu - deletes entry from hash list with re-initialization
 137  * @n: the element to delete from the hash list.
 138  *
 139  * Note: list_unhashed() on the node return true after this. It is
 140  * useful for RCU based read lockfree traversal if the writer side
 141  * must know if the list entry is still hashed or already unhashed.
 142  *
 143  * In particular, it means that we can not poison the forward pointers
 144  * that may still be used for walking the hash list and we can only
 145  * zero the pprev pointer so list_unhashed() will return true after
 146  * this.
 147  *
 148  * The caller must take whatever precautions are necessary (such as
 149  * holding appropriate locks) to avoid racing with another
 150  * list-mutation primitive, such as hlist_add_head_rcu() or
 151  * hlist_del_rcu(), running on this same list.  However, it is
 152  * perfectly legal to run concurrently with the _rcu list-traversal
 153  * primitives, such as hlist_for_each_entry_rcu().
 154  */
 155 static inline void hlist_del_init_rcu(struct hlist_node *n)
 156 {
 157         if (!hlist_unhashed(n)) {
 158                 __hlist_del(n);
 159                 n->pprev = NULL;
 160         }
 161 }
 162
 163 /**
 164  * list_replace_rcu - replace old entry by new one
 165  * @old : the element to be replaced
 166  * @new : the new element to insert
 167  *
 168  * The @old entry will be replaced with the @new entry atomically.
 169  * Note: @old should not be empty.
 170  */
 171 static inline void list_replace_rcu(struct list_head *old,
 172                                 struct list_head *new)
 173 {
 174         new->next = old->next;
 175         new->prev = old->prev;
 176         rcu_assign_pointer(list_next_rcu(new->prev), new);
 177         new->next->prev = new;
 178         old->prev = LIST_POISON2;
 179 }
 180
 181 /**
 182  * list_splice_init_rcu - splice an RCU-protected list into an existing list.
 183  * @list:       the RCU-protected list to splice
 184  * @head:       the place in the list to splice the first list into
 185  * @sync:       function to sync: synchronize_rcu(), synchronize_sched(), ...
 186  *
 187  * @head can be RCU-read traversed concurrently with this function.
 188  *
 189  * Note that this function blocks.
 190  *
 191  * Important note: the caller must take whatever action is necessary to
 192  *      prevent any other updates to @head.  In principle, it is possible
 193  *      to modify the list as soon as sync() begins execution.
 194  *      If this sort of thing becomes necessary, an alternative version
 195  *      based on call_rcu() could be created.  But only if -really-
 196  *      needed -- there is no shortage of RCU API members.
 197  */
 198 static inline void list_splice_init_rcu(struct list_head *list,
 199                                         struct list_head *head,
 200                                         void (*sync)(void))
 201 {
 202         struct list_head *first = list->next;
 203         struct list_head *last = list->prev;
 204         struct list_head *at = head->next;
 205
 206         if (list_empty(list))
 207                 return;
 208
 209         /*
 210          * "first" and "last" tracking list, so initialize it.  RCU readers
 211          * have access to this list, so we must use INIT_LIST_HEAD_RCU()
 212          * instead of INIT_LIST_HEAD().
 213          */
 214
 215         INIT_LIST_HEAD_RCU(list);
 216
 217         /*
 218          * At this point, the list body still points to the source list.
 219          * Wait for any readers to finish using the list before splicing
 220          * the list body into the new list.  Any new readers will see
 221          * an empty list.
 222          */
 223
 224         sync();
 225
 226         /*
 227          * Readers are finished with the source list, so perform splice.
 228          * The order is important if the new list is global and accessible
 229          * to concurrent RCU readers.  Note that RCU readers are not
 230          * permitted to traverse the prev pointers without excluding
 231          * this function.
 232          */
 233
 234         last->next = at;
 235         rcu_assign_pointer(list_next_rcu(head), first);
 236         first->prev = head;
 237         at->prev = last;
 238 }
 239
 240 /**
 241  * list_entry_rcu - get the struct for this entry
 242  * @ptr:        the &struct list_head pointer.
 243  * @type:       the type of the struct this is embedded in.
 244  * @member:     the name of the list_head within the struct.
 245  *
 246  * This primitive may safely run concurrently with the _rcu list-mutation
 247  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
 248  */
 249 #define list_entry_rcu(ptr, type, member) \
 250         container_of(lockless_dereference(ptr), type, member)
 251
 252 /**
 253  * Where are list_empty_rcu() and list_first_entry_rcu()?
 254  *
 255  * Implementing those functions following their counterparts list_empty() and
 256  * list_first_entry() is not advisable because they lead to subtle race
 257  * conditions as the following snippet shows:
 258  *
 259  * if (!list_empty_rcu(mylist)) {
 260  *      struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
 261  *      do_something(bar);
 262  * }
 263  *
 264  * The list may not be empty when list_empty_rcu checks it, but it may be when
 265  * list_first_entry_rcu rereads the ->next pointer.
 266  *
 267  * Rereading the ->next pointer is not a problem for list_empty() and
 268  * list_first_entry() because they would be protected by a lock that blocks
 269  * writers.
 270  *
 271  * See list_first_or_null_rcu for an alternative.
 272  */
 273
 274 /**
 275  * list_first_or_null_rcu - get the first element from a list
 276  * @ptr:        the list head to take the element from.
 277  * @type:       the type of the struct this is embedded in.
 278  * @member:     the name of the list_head within the struct.
 279  *
 280  * Note that if the list is empty, it returns NULL.
 281  *
 282  * This primitive may safely run concurrently with the _rcu list-mutation
 283  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
 284  */
 285 #define list_first_or_null_rcu(ptr, type, member) \
 286 ({ \
 287         struct list_head *__ptr = (ptr); \
 288         struct list_head *__next = READ_ONCE(__ptr->next); \
 289         likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
 290 })
 291
 292 /**
 293  * list_for_each_entry_rcu      -       iterate over rcu list of given type
 294  * @pos:        the type * to use as a loop cursor.
 295  * @head:       the head for your list.
 296  * @member:     the name of the list_head within the struct.
 297  *
 298  * This list-traversal primitive may safely run concurrently with
 299  * the _rcu list-mutation primitives such as list_add_rcu()
 300  * as long as the traversal is guarded by rcu_read_lock().
 301  */
 302 #define list_for_each_entry_rcu(pos, head, member) \
 303         for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
 304                 &pos->member != (head); \
 305                 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 306
 307 /**
 308  * list_for_each_entry_continue_rcu - continue iteration over list of given type
 309  * @pos:        the type * to use as a loop cursor.
 310  * @head:       the head for your list.
 311  * @member:     the name of the list_head within the struct.
 312  *
 313  * Continue to iterate over list of given type, continuing after
 314  * the current position.
 315  */
 316 #define list_for_each_entry_continue_rcu(pos, head, member)             \
 317         for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
 318              &pos->member != (head);    \
 319              pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 320
 321 /**
 322  * hlist_del_rcu - deletes entry from hash list without re-initialization
 323  * @n: the element to delete from the hash list.
 324  *
 325  * Note: list_unhashed() on entry does not return true after this,
 326  * the entry is in an undefined state. It is useful for RCU based
 327  * lockfree traversal.
 328  *
 329  * In particular, it means that we can not poison the forward
 330  * pointers that may still be used for walking the hash list.
 331  *
 332  * The caller must take whatever precautions are necessary
 333  * (such as holding appropriate locks) to avoid racing
 334  * with another list-mutation primitive, such as hlist_add_head_rcu()
 335  * or hlist_del_rcu(), running on this same list.
 336  * However, it is perfectly legal to run concurrently with
 337  * the _rcu list-traversal primitives, such as
 338  * hlist_for_each_entry().
 339  */
 340 static inline void hlist_del_rcu(struct hlist_node *n)
 341 {
 342         __hlist_del(n);
 343         n->pprev = LIST_POISON2;
 344 }
 345
 346 /**
 347  * hlist_replace_rcu - replace old entry by new one
 348  * @old : the element to be replaced
 349  * @new : the new element to insert
 350  *
 351  * The @old entry will be replaced with the @new entry atomically.
 352  */
 353 static inline void hlist_replace_rcu(struct hlist_node *old,
 354                                         struct hlist_node *new)
 355 {
 356         struct hlist_node *next = old->next;
 357
 358         new->next = next;
 359         new->pprev = old->pprev;
 360         rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
 361         if (next)
 362                 new->next->pprev = &new->next;
 363         old->pprev = LIST_POISON2;
 364 }
 365
 366 /*
 367  * return the first or the next element in an RCU protected hlist
 368  */
 369 #define hlist_first_rcu(head)   (*((struct hlist_node __rcu **)(&(head)->first)))
 370 #define hlist_next_rcu(node)    (*((struct hlist_node __rcu **)(&(node)->next)))
 371 #define hlist_pprev_rcu(node)   (*((struct hlist_node __rcu **)((node)->pprev)))
 372
 373 /**
 374  * hlist_add_head_rcu
 375  * @n: the element to add to the hash list.
 376  * @h: the list to add to.
 377  *
 378  * Description:
 379  * Adds the specified element to the specified hlist,
 380  * while permitting racing traversals.
 381  *
 382  * The caller must take whatever precautions are necessary
 383  * (such as holding appropriate locks) to avoid racing
 384  * with another list-mutation primitive, such as hlist_add_head_rcu()
 385  * or hlist_del_rcu(), running on this same list.
 386  * However, it is perfectly legal to run concurrently with
 387  * the _rcu list-traversal primitives, such as
 388  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 389  * problems on Alpha CPUs.  Regardless of the type of CPU, the
 390  * list-traversal primitive must be guarded by rcu_read_lock().
 391  */
 392 static inline void hlist_add_head_rcu(struct hlist_node *n,
 393                                         struct hlist_head *h)
 394 {
 395         struct hlist_node *first = h->first;
 396
 397         n->next = first;
 398         n->pprev = &h->first;
 399         rcu_assign_pointer(hlist_first_rcu(h), n);
 400         if (first)
 401                 first->pprev = &n->next;
 402 }
 403
 404 /**
 405  * hlist_add_before_rcu
 406  * @n: the new element to add to the hash list.
 407  * @next: the existing element to add the new element before.
 408  *
 409  * Description:
 410  * Adds the specified element to the specified hlist
 411  * before the specified node while permitting racing traversals.
 412  *
 413  * The caller must take whatever precautions are necessary
 414  * (such as holding appropriate locks) to avoid racing
 415  * with another list-mutation primitive, such as hlist_add_head_rcu()
 416  * or hlist_del_rcu(), running on this same list.
 417  * However, it is perfectly legal to run concurrently with
 418  * the _rcu list-traversal primitives, such as
 419  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 420  * problems on Alpha CPUs.
 421  */
 422 static inline void hlist_add_before_rcu(struct hlist_node *n,
 423                                         struct hlist_node *next)
 424 {
 425         n->pprev = next->pprev;
 426         n->next = next;
 427         rcu_assign_pointer(hlist_pprev_rcu(n), n);
 428         next->pprev = &n->next;
 429 }
 430
 431 /**
 432  * hlist_add_behind_rcu
 433  * @n: the new element to add to the hash list.
 434  * @prev: the existing element to add the new element after.
 435  *
 436  * Description:
 437  * Adds the specified element to the specified hlist
 438  * after the specified node while permitting racing traversals.
 439  *
 440  * The caller must take whatever precautions are necessary
 441  * (such as holding appropriate locks) to avoid racing
 442  * with another list-mutation primitive, such as hlist_add_head_rcu()
 443  * or hlist_del_rcu(), running on this same list.
 444  * However, it is perfectly legal to run concurrently with
 445  * the _rcu list-traversal primitives, such as
 446  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 447  * problems on Alpha CPUs.
 448  */
 449 static inline void hlist_add_behind_rcu(struct hlist_node *n,
 450                                         struct hlist_node *prev)
 451 {
 452         n->next = prev->next;
 453         n->pprev = &prev->next;
 454         rcu_assign_pointer(hlist_next_rcu(prev), n);
 455         if (n->next)
 456                 n->next->pprev = &n->next;
 457 }
 458
 459 #define __hlist_for_each_rcu(pos, head)                         \
 460         for (pos = rcu_dereference(hlist_first_rcu(head));      \
 461              pos;                                               \
 462              pos = rcu_dereference(hlist_next_rcu(pos)))
 463
 464 /**
 465  * hlist_for_each_entry_rcu - iterate over rcu list of given type
 466  * @pos:        the type * to use as a loop cursor.
 467  * @head:       the head for your list.
 468  * @member:     the name of the hlist_node within the struct.
 469  *
 470  * This list-traversal primitive may safely run concurrently with
 471  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 472  * as long as the traversal is guarded by rcu_read_lock().
 473  */
 474 #define hlist_for_each_entry_rcu(pos, head, member)                     \
 475         for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
 476                         typeof(*(pos)), member);                        \
 477                 pos;                                                    \
 478                 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
 479                         &(pos)->member)), typeof(*(pos)), member))
 480
 481 /**
 482  * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
 483  * @pos:        the type * to use as a loop cursor.
 484  * @head:       the head for your list.
 485  * @member:     the name of the hlist_node within the struct.
 486  *
 487  * This list-traversal primitive may safely run concurrently with
 488  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 489  * as long as the traversal is guarded by rcu_read_lock().
 490  *
 491  * This is the same as hlist_for_each_entry_rcu() except that it does
 492  * not do any RCU debugging or tracing.
 493  */
 494 #define hlist_for_each_entry_rcu_notrace(pos, head, member)                     \
 495         for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\
 496                         typeof(*(pos)), member);                        \
 497                 pos;                                                    \
 498                 pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\
 499                         &(pos)->member)), typeof(*(pos)), member))
 500
 501 /**
 502  * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
 503  * @pos:        the type * to use as a loop cursor.
 504  * @head:       the head for your list.
 505  * @member:     the name of the hlist_node within the struct.
 506  *
 507  * This list-traversal primitive may safely run concurrently with
 508  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 509  * as long as the traversal is guarded by rcu_read_lock().
 510  */
 511 #define hlist_for_each_entry_rcu_bh(pos, head, member)                  \
 512         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
 513                         typeof(*(pos)), member);                        \
 514                 pos;                                                    \
 515                 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
 516                         &(pos)->member)), typeof(*(pos)), member))
 517
 518 /**
 519  * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
 520  * @pos:        the type * to use as a loop cursor.
 521  * @member:     the name of the hlist_node within the struct.
 522  */
 523 #define hlist_for_each_entry_continue_rcu(pos, member)                  \
 524         for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
 525                         &(pos)->member)), typeof(*(pos)), member);      \
 526              pos;                                                       \
 527              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
 528                         &(pos)->member)), typeof(*(pos)), member))
 529
 530 /**
 531  * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
 532  * @pos:        the type * to use as a loop cursor.
 533  * @member:     the name of the hlist_node within the struct.
 534  */
 535 #define hlist_for_each_entry_continue_rcu_bh(pos, member)               \
 536         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
 537                         &(pos)->member)), typeof(*(pos)), member);      \
 538              pos;                                                       \
 539              pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
 540                         &(pos)->member)), typeof(*(pos)), member))
 541
 542 /**
 543  * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
 544  * @pos:        the type * to use as a loop cursor.
 545  * @member:     the name of the hlist_node within the struct.
 546  */
 547 #define hlist_for_each_entry_from_rcu(pos, member)                      \
 548         for (; pos;                                                     \
 549              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
 550                         &(pos)->member)), typeof(*(pos)), member))
 551
 552 #endif  /* __KERNEL__ */
 553 #endif