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