linux/include/linux/rculist.h
<<
>>
Prefs
   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
  34static 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
  43extern 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 */
  63static 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 */
  84static 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 */
 114static 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 */
 140static 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 */
 156static 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 */
 183static 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 __rcu *__next = list_next_rcu(__ptr); \
 271          likely(__ptr != __next) ? container_of(__next, type, member) : NULL; \
 272        })
 273
 274/**
 275 * list_for_each_entry_rcu      -       iterate over rcu list of given type
 276 * @pos:        the type * to use as a loop cursor.
 277 * @head:       the head for your list.
 278 * @member:     the name of the list_struct within the struct.
 279 *
 280 * This list-traversal primitive may safely run concurrently with
 281 * the _rcu list-mutation primitives such as list_add_rcu()
 282 * as long as the traversal is guarded by rcu_read_lock().
 283 */
 284#define list_for_each_entry_rcu(pos, head, member) \
 285        for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
 286                &pos->member != (head); \
 287                pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 288
 289/**
 290 * list_for_each_entry_continue_rcu - continue iteration over list of given type
 291 * @pos:        the type * to use as a loop cursor.
 292 * @head:       the head for your list.
 293 * @member:     the name of the list_struct within the struct.
 294 *
 295 * Continue to iterate over list of given type, continuing after
 296 * the current position.
 297 */
 298#define list_for_each_entry_continue_rcu(pos, head, member)             \
 299        for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
 300             &pos->member != (head);    \
 301             pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 302
 303/**
 304 * hlist_del_rcu - deletes entry from hash list without re-initialization
 305 * @n: the element to delete from the hash list.
 306 *
 307 * Note: list_unhashed() on entry does not return true after this,
 308 * the entry is in an undefined state. It is useful for RCU based
 309 * lockfree traversal.
 310 *
 311 * In particular, it means that we can not poison the forward
 312 * pointers that may still be used for walking the hash list.
 313 *
 314 * The caller must take whatever precautions are necessary
 315 * (such as holding appropriate locks) to avoid racing
 316 * with another list-mutation primitive, such as hlist_add_head_rcu()
 317 * or hlist_del_rcu(), running on this same list.
 318 * However, it is perfectly legal to run concurrently with
 319 * the _rcu list-traversal primitives, such as
 320 * hlist_for_each_entry().
 321 */
 322static inline void hlist_del_rcu(struct hlist_node *n)
 323{
 324        __hlist_del(n);
 325        n->pprev = LIST_POISON2;
 326}
 327
 328/**
 329 * hlist_replace_rcu - replace old entry by new one
 330 * @old : the element to be replaced
 331 * @new : the new element to insert
 332 *
 333 * The @old entry will be replaced with the @new entry atomically.
 334 */
 335static inline void hlist_replace_rcu(struct hlist_node *old,
 336                                        struct hlist_node *new)
 337{
 338        struct hlist_node *next = old->next;
 339
 340        new->next = next;
 341        new->pprev = old->pprev;
 342        rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
 343        if (next)
 344                new->next->pprev = &new->next;
 345        old->pprev = LIST_POISON2;
 346}
 347
 348/*
 349 * return the first or the next element in an RCU protected hlist
 350 */
 351#define hlist_first_rcu(head)   (*((struct hlist_node __rcu **)(&(head)->first)))
 352#define hlist_next_rcu(node)    (*((struct hlist_node __rcu **)(&(node)->next)))
 353#define hlist_pprev_rcu(node)   (*((struct hlist_node __rcu **)((node)->pprev)))
 354
 355/**
 356 * hlist_add_head_rcu
 357 * @n: the element to add to the hash list.
 358 * @h: the list to add to.
 359 *
 360 * Description:
 361 * Adds the specified element to the specified hlist,
 362 * while permitting racing traversals.
 363 *
 364 * The caller must take whatever precautions are necessary
 365 * (such as holding appropriate locks) to avoid racing
 366 * with another list-mutation primitive, such as hlist_add_head_rcu()
 367 * or hlist_del_rcu(), running on this same list.
 368 * However, it is perfectly legal to run concurrently with
 369 * the _rcu list-traversal primitives, such as
 370 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 371 * problems on Alpha CPUs.  Regardless of the type of CPU, the
 372 * list-traversal primitive must be guarded by rcu_read_lock().
 373 */
 374static inline void hlist_add_head_rcu(struct hlist_node *n,
 375                                        struct hlist_head *h)
 376{
 377        struct hlist_node *first = h->first;
 378
 379        n->next = first;
 380        n->pprev = &h->first;
 381        rcu_assign_pointer(hlist_first_rcu(h), n);
 382        if (first)
 383                first->pprev = &n->next;
 384}
 385
 386/**
 387 * hlist_add_before_rcu
 388 * @n: the new element to add to the hash list.
 389 * @next: the existing element to add the new element before.
 390 *
 391 * Description:
 392 * Adds the specified element to the specified hlist
 393 * before the specified node while permitting racing traversals.
 394 *
 395 * The caller must take whatever precautions are necessary
 396 * (such as holding appropriate locks) to avoid racing
 397 * with another list-mutation primitive, such as hlist_add_head_rcu()
 398 * or hlist_del_rcu(), running on this same list.
 399 * However, it is perfectly legal to run concurrently with
 400 * the _rcu list-traversal primitives, such as
 401 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 402 * problems on Alpha CPUs.
 403 */
 404static inline void hlist_add_before_rcu(struct hlist_node *n,
 405                                        struct hlist_node *next)
 406{
 407        n->pprev = next->pprev;
 408        n->next = next;
 409        rcu_assign_pointer(hlist_pprev_rcu(n), n);
 410        next->pprev = &n->next;
 411}
 412
 413/**
 414 * hlist_add_after_rcu
 415 * @prev: the existing element to add the new element after.
 416 * @n: the new element to add to the hash list.
 417 *
 418 * Description:
 419 * Adds the specified element to the specified hlist
 420 * after the specified node while permitting racing traversals.
 421 *
 422 * The caller must take whatever precautions are necessary
 423 * (such as holding appropriate locks) to avoid racing
 424 * with another list-mutation primitive, such as hlist_add_head_rcu()
 425 * or hlist_del_rcu(), running on this same list.
 426 * However, it is perfectly legal to run concurrently with
 427 * the _rcu list-traversal primitives, such as
 428 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 429 * problems on Alpha CPUs.
 430 */
 431static inline void hlist_add_after_rcu(struct hlist_node *prev,
 432                                       struct hlist_node *n)
 433{
 434        n->next = prev->next;
 435        n->pprev = &prev->next;
 436        rcu_assign_pointer(hlist_next_rcu(prev), n);
 437        if (n->next)
 438                n->next->pprev = &n->next;
 439}
 440
 441#define __hlist_for_each_rcu(pos, head)                         \
 442        for (pos = rcu_dereference(hlist_first_rcu(head));      \
 443             pos;                                               \
 444             pos = rcu_dereference(hlist_next_rcu(pos)))
 445
 446/**
 447 * hlist_for_each_entry_rcu - iterate over rcu list of given type
 448 * @pos:        the type * to use as a loop cursor.
 449 * @head:       the head for your list.
 450 * @member:     the name of the hlist_node within the struct.
 451 *
 452 * This list-traversal primitive may safely run concurrently with
 453 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 454 * as long as the traversal is guarded by rcu_read_lock().
 455 */
 456#define hlist_for_each_entry_rcu(pos, head, member)                     \
 457        for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
 458                        typeof(*(pos)), member);                        \
 459                pos;                                                    \
 460                pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
 461                        &(pos)->member)), typeof(*(pos)), member))
 462
 463/**
 464 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
 465 * @pos:        the type * to use as a loop cursor.
 466 * @head:       the head for your list.
 467 * @member:     the name of the hlist_node within the struct.
 468 *
 469 * This list-traversal primitive may safely run concurrently with
 470 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 471 * as long as the traversal is guarded by rcu_read_lock().
 472 */
 473#define hlist_for_each_entry_rcu_bh(pos, head, member)                  \
 474        for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
 475                        typeof(*(pos)), member);                        \
 476                pos;                                                    \
 477                pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
 478                        &(pos)->member)), typeof(*(pos)), member))
 479
 480/**
 481 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
 482 * @pos:        the type * to use as a loop cursor.
 483 * @member:     the name of the hlist_node within the struct.
 484 */
 485#define hlist_for_each_entry_continue_rcu(pos, member)                  \
 486        for (pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\
 487                        typeof(*(pos)), member);                        \
 488             pos;                                                       \
 489             pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\
 490                        typeof(*(pos)), member))
 491
 492/**
 493 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
 494 * @pos:        the type * to use as a loop cursor.
 495 * @member:     the name of the hlist_node within the struct.
 496 */
 497#define hlist_for_each_entry_continue_rcu_bh(pos, member)               \
 498        for (pos = hlist_entry_safe(rcu_dereference_bh((pos)->member.next),\
 499                        typeof(*(pos)), member);                        \
 500             pos;                                                       \
 501             pos = hlist_entry_safe(rcu_dereference_bh((pos)->member.next),\
 502                        typeof(*(pos)), member))
 503
 504
 505#endif  /* __KERNEL__ */
 506#endif
 507
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.