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