include/linux/list.h

   1 #ifndef _LINUX_LIST_H
   2 #define _LINUX_LIST_H
   3
   4 #ifdef __KERNEL__
   5
   6 #include <linux/stddef.h>
   7 #include <linux/prefetch.h>
   8 #include <linux/kernel.h>
   9 #include <asm/system.h>
  10 #include <asm/bug.h>
  11
  12 /*
  13  * These are non-NULL pointers that will result in page faults
  14  * under normal circumstances, used to verify that nobody uses
  15  * non-initialized list entries.
  16  */
  17 #define LIST_POISON1  ((void *) 0x00100100)
  18 #define LIST_POISON2  ((void *) 0x00200200)
  19
  20 /*
  21  * Simple doubly linked list implementation.
  22  *
  23  * Some of the internal functions ("__xxx") are useful when
  24  * manipulating whole lists rather than single entries, as
  25  * sometimes we already know the next/prev entries and we can
  26  * generate better code by using them directly rather than
  27  * using the generic single-entry routines.
  28  */
  29
  30 struct list_head {
  31         struct list_head *next, *prev;
  32 };
  33
  34 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  35
  36 #define LIST_HEAD(name) \
  37         struct list_head name = LIST_HEAD_INIT(name)
  38
  39 static inline void INIT_LIST_HEAD(struct list_head *list)
  40 {
  41         list->next = list;
  42         list->prev = list;
  43 }
  44
  45 /*
  46  * Insert a new entry between two known consecutive entries.
  47  *
  48  * This is only for internal list manipulation where we know
  49  * the prev/next entries already!
  50  */
  51 static inline void __list_add(struct list_head *new,
  52                               struct list_head *prev,
  53                               struct list_head *next)
  54 {
  55         if (next->prev != prev) {
  56                 printk("List corruption. next->prev should be %p, but was %p\n",
  57                                 prev, next->prev);
  58                 BUG();
  59         }
  60         if (prev->next != next) {
  61                 printk("List corruption. prev->next should be %p, but was %p\n",
  62                                 next, prev->next);
  63                 BUG();
  64         }
  65         next->prev = new;
  66         new->next = next;
  67         new->prev = prev;
  68         prev->next = new;
  69 }
  70
  71 /**
  72  * list_add - add a new entry
  73  * @new: new entry to be added
  74  * @head: list head to add it after
  75  *
  76  * Insert a new entry after the specified head.
  77  * This is good for implementing stacks.
  78  */
  79 static inline void list_add(struct list_head *new, struct list_head *head)
  80 {
  81         __list_add(new, head, head->next);
  82 }
  83
  84 /**
  85  * list_add_tail - add a new entry
  86  * @new: new entry to be added
  87  * @head: list head to add it before
  88  *
  89  * Insert a new entry before the specified head.
  90  * This is useful for implementing queues.
  91  */
  92 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  93 {
  94         __list_add(new, head->prev, head);
  95 }
  96
  97 /*
  98  * Insert a new entry between two known consecutive entries.
  99  *
 100  * This is only for internal list manipulation where we know
 101  * the prev/next entries already!
 102  */
 103 static inline void __list_add_rcu(struct list_head * new,
 104                 struct list_head * prev, struct list_head * next)
 105 {
 106         new->next = next;
 107         new->prev = prev;
 108         smp_wmb();
 109         next->prev = new;
 110         prev->next = new;
 111 }
 112
 113 /**
 114  * list_add_rcu - add a new entry to rcu-protected list
 115  * @new: new entry to be added
 116  * @head: list head to add it after
 117  *
 118  * Insert a new entry after the specified head.
 119  * This is good for implementing stacks.
 120  *
 121  * The caller must take whatever precautions are necessary
 122  * (such as holding appropriate locks) to avoid racing
 123  * with another list-mutation primitive, such as list_add_rcu()
 124  * or list_del_rcu(), running on this same list.
 125  * However, it is perfectly legal to run concurrently with
 126  * the _rcu list-traversal primitives, such as
 127  * list_for_each_entry_rcu().
 128  */
 129 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
 130 {
 131         __list_add_rcu(new, head, head->next);
 132 }
 133
 134 /**
 135  * list_add_tail_rcu - add a new entry to rcu-protected list
 136  * @new: new entry to be added
 137  * @head: list head to add it before
 138  *
 139  * Insert a new entry before the specified head.
 140  * This is useful for implementing queues.
 141  *
 142  * The caller must take whatever precautions are necessary
 143  * (such as holding appropriate locks) to avoid racing
 144  * with another list-mutation primitive, such as list_add_tail_rcu()
 145  * or list_del_rcu(), running on this same list.
 146  * However, it is perfectly legal to run concurrently with
 147  * the _rcu list-traversal primitives, such as
 148  * list_for_each_entry_rcu().
 149  */
 150 static inline void list_add_tail_rcu(struct list_head *new,
 151                                         struct list_head *head)
 152 {
 153         __list_add_rcu(new, head->prev, head);
 154 }
 155
 156 /*
 157  * Delete a list entry by making the prev/next entries
 158  * point to each other.
 159  *
 160  * This is only for internal list manipulation where we know
 161  * the prev/next entries already!
 162  */
 163 static inline void __list_del(struct list_head * prev, struct list_head * next)
 164 {
 165         next->prev = prev;
 166         prev->next = next;
 167 }
 168
 169 /**
 170  * list_del - deletes entry from list.
 171  * @entry: the element to delete from the list.
 172  * Note: list_empty on entry does not return true after this, the entry is
 173  * in an undefined state.
 174  */
 175 static inline void list_del(struct list_head *entry)
 176 {
 177         if (entry->prev->next != entry) {
 178                 printk("List corruption. prev->next should be %p, but was %p\n",
 179                                 entry, entry->prev->next);
 180                 BUG();
 181         }
 182         if (entry->next->prev != entry) {
 183                 printk("List corruption. next->prev should be %p, but was %p\n",
 184                                 entry, entry->next->prev);
 185                 BUG();
 186         }
 187         __list_del(entry->prev, entry->next);
 188         entry->next = LIST_POISON1;
 189         entry->prev = LIST_POISON2;
 190 }
 191
 192 /**
 193  * list_del_rcu - deletes entry from list without re-initialization
 194  * @entry: the element to delete from the list.
 195  *
 196  * Note: list_empty on entry does not return true after this,
 197  * the entry is in an undefined state. It is useful for RCU based
 198  * lockfree traversal.
 199  *
 200  * In particular, it means that we can not poison the forward
 201  * pointers that may still be used for walking the list.
 202  *
 203  * The caller must take whatever precautions are necessary
 204  * (such as holding appropriate locks) to avoid racing
 205  * with another list-mutation primitive, such as list_del_rcu()
 206  * or list_add_rcu(), running on this same list.
 207  * However, it is perfectly legal to run concurrently with
 208  * the _rcu list-traversal primitives, such as
 209  * list_for_each_entry_rcu().
 210  *
 211  * Note that the caller is not permitted to immediately free
 212  * the newly deleted entry.  Instead, either synchronize_rcu()
 213  * or call_rcu() must be used to defer freeing until an RCU
 214  * grace period has elapsed.
 215  */
 216 static inline void list_del_rcu(struct list_head *entry)
 217 {
 218         __list_del(entry->prev, entry->next);
 219         entry->prev = LIST_POISON2;
 220 }
 221
 222 /*
 223  * list_replace_rcu - replace old entry by new one
 224  * @old : the element to be replaced
 225  * @new : the new element to insert
 226  *
 227  * The old entry will be replaced with the new entry atomically.
 228  */
 229 static inline void list_replace_rcu(struct list_head *old,
 230                                 struct list_head *new)
 231 {
 232         new->next = old->next;
 233         new->prev = old->prev;
 234         smp_wmb();
 235         new->next->prev = new;
 236         new->prev->next = new;
 237         old->prev = LIST_POISON2;
 238 }
 239
 240 /**
 241  * list_del_init - deletes entry from list and reinitialize it.
 242  * @entry: the element to delete from the list.
 243  */
 244 static inline void list_del_init(struct list_head *entry)
 245 {
 246         __list_del(entry->prev, entry->next);
 247         INIT_LIST_HEAD(entry);
 248 }
 249
 250 /**
 251  * list_move - delete from one list and add as another's head
 252  * @list: the entry to move
 253  * @head: the head that will precede our entry
 254  */
 255 static inline void list_move(struct list_head *list, struct list_head *head)
 256 {
 257         __list_del(list->prev, list->next);
 258         list_add(list, head);
 259 }
 260
 261 /**
 262  * list_move_tail - delete from one list and add as another's tail
 263  * @list: the entry to move
 264  * @head: the head that will follow our entry
 265  */
 266 static inline void list_move_tail(struct list_head *list,
 267                                   struct list_head *head)
 268 {
 269         __list_del(list->prev, list->next);
 270         list_add_tail(list, head);
 271 }
 272
 273 /**
 274  * list_empty - tests whether a list is empty
 275  * @head: the list to test.
 276  */
 277 static inline int list_empty(const struct list_head *head)
 278 {
 279         return head->next == head;
 280 }
 281
 282 /**
 283  * list_empty_careful - tests whether a list is
 284  * empty _and_ checks that no other CPU might be
 285  * in the process of still modifying either member
 286  *
 287  * NOTE: using list_empty_careful() without synchronization
 288  * can only be safe if the only activity that can happen
 289  * to the list entry is list_del_init(). Eg. it cannot be used
 290  * if another CPU could re-list_add() it.
 291  *
 292  * @head: the list to test.
 293  */
 294 static inline int list_empty_careful(const struct list_head *head)
 295 {
 296         struct list_head *next = head->next;
 297         return (next == head) && (next == head->prev);
 298 }
 299
 300 static inline void __list_splice(struct list_head *list,
 301                                  struct list_head *head)
 302 {
 303         struct list_head *first = list->next;
 304         struct list_head *last = list->prev;
 305         struct list_head *at = head->next;
 306
 307         first->prev = head;
 308         head->next = first;
 309
 310         last->next = at;
 311         at->prev = last;
 312 }
 313
 314 /**
 315  * list_splice - join two lists
 316  * @list: the new list to add.
 317  * @head: the place to add it in the first list.
 318  */
 319 static inline void list_splice(struct list_head *list, struct list_head *head)
 320 {
 321         if (!list_empty(list))
 322                 __list_splice(list, head);
 323 }
 324
 325 /**
 326  * list_splice_init - join two lists and reinitialise the emptied list.
 327  * @list: the new list to add.
 328  * @head: the place to add it in the first list.
 329  *
 330  * The list at @list is reinitialised
 331  */
 332 static inline void list_splice_init(struct list_head *list,
 333                                     struct list_head *head)
 334 {
 335         if (!list_empty(list)) {
 336                 __list_splice(list, head);
 337                 INIT_LIST_HEAD(list);
 338         }
 339 }
 340
 341 /**
 342  * list_entry - get the struct for this entry
 343  * @ptr:        the &struct list_head pointer.
 344  * @type:       the type of the struct this is embedded in.
 345  * @member:     the name of the list_struct within the struct.
 346  */
 347 #define list_entry(ptr, type, member) \
 348         container_of(ptr, type, member)
 349
 350 /**
 351  * list_for_each        -       iterate over a list
 352  * @pos:        the &struct list_head to use as a loop counter.
 353  * @head:       the head for your list.
 354  */
 355 #define list_for_each(pos, head) \
 356         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 357                 pos = pos->next)
 358
 359 /**
 360  * __list_for_each      -       iterate over a list
 361  * @pos:        the &struct list_head to use as a loop counter.
 362  * @head:       the head for your list.
 363  *
 364  * This variant differs from list_for_each() in that it's the
 365  * simplest possible list iteration code, no prefetching is done.
 366  * Use this for code that knows the list to be very short (empty
 367  * or 1 entry) most of the time.
 368  */
 369 #define __list_for_each(pos, head) \
 370         for (pos = (head)->next; pos != (head); pos = pos->next)
 371
 372 /**
 373  * list_for_each_prev   -       iterate over a list backwards
 374  * @pos:        the &struct list_head to use as a loop counter.
 375  * @head:       the head for your list.
 376  */
 377 #define list_for_each_prev(pos, head) \
 378         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
 379                 pos = pos->prev)
 380
 381 /**
 382  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 383  * @pos:        the &struct list_head to use as a loop counter.
 384  * @n:          another &struct list_head to use as temporary storage
 385  * @head:       the head for your list.
 386  */
 387 #define list_for_each_safe(pos, n, head) \
 388         for (pos = (head)->next, n = pos->next; pos != (head); \
 389                 pos = n, n = pos->next)
 390
 391 /**
 392  * list_for_each_entry  -       iterate over list of given type
 393  * @pos:        the type * to use as a loop counter.
 394  * @head:       the head for your list.
 395  * @member:     the name of the list_struct within the struct.
 396  */
 397 #define list_for_each_entry(pos, head, member)                          \
 398         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 399              prefetch(pos->member.next), &pos->member != (head);        \
 400              pos = list_entry(pos->member.next, typeof(*pos), member))
 401
 402 /**
 403  * list_for_each_entry_reverse - iterate backwards over list of given type.
 404  * @pos:        the type * to use as a loop counter.
 405  * @head:       the head for your list.
 406  * @member:     the name of the list_struct within the struct.
 407  */
 408 #define list_for_each_entry_reverse(pos, head, member)                  \
 409         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 410              prefetch(pos->member.prev), &pos->member != (head);        \
 411              pos = list_entry(pos->member.prev, typeof(*pos), member))
 412
 413 /**
 414  * list_prepare_entry - prepare a pos entry for use as a start point in
 415  *                      list_for_each_entry_continue
 416  * @pos:        the type * to use as a start point
 417  * @head:       the head of the list
 418  * @member:     the name of the list_struct within the struct.
 419  */
 420 #define list_prepare_entry(pos, head, member) \
 421         ((pos) ? : list_entry(head, typeof(*pos), member))
 422
 423 /**
 424  * list_for_each_entry_continue -       iterate over list of given type
 425  *                      continuing after existing point
 426  * @pos:        the type * to use as a loop counter.
 427  * @head:       the head for your list.
 428  * @member:     the name of the list_struct within the struct.
 429  */
 430 #define list_for_each_entry_continue(pos, head, member)                 \
 431         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 432              prefetch(pos->member.next), &pos->member != (head);        \
 433              pos = list_entry(pos->member.next, typeof(*pos), member))
 434
 435 /**
 436  * list_for_each_entry_from -   iterate over list of given type
 437  *                      continuing from existing point
 438  * @pos:        the type * to use as a loop counter.
 439  * @head:       the head for your list.
 440  * @member:     the name of the list_struct within the struct.
 441  */
 442 #define list_for_each_entry_from(pos, head, member)                     \
 443         for (; prefetch(pos->member.next), &pos->member != (head);      \
 444              pos = list_entry(pos->member.next, typeof(*pos), member))
 445
 446 /**
 447  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 448  * @pos:        the type * to use as a loop counter.
 449  * @n:          another type * to use as temporary storage
 450  * @head:       the head for your list.
 451  * @member:     the name of the list_struct within the struct.
 452  */
 453 #define list_for_each_entry_safe(pos, n, head, member)                  \
 454         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 455                 n = list_entry(pos->member.next, typeof(*pos), member); \
 456              &pos->member != (head);                                    \
 457              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 458
 459 /**
 460  * list_for_each_entry_safe_continue -  iterate over list of given type
 461  *                      continuing after existing point safe against removal of list entry
 462  * @pos:        the type * to use as a loop counter.
 463  * @n:          another type * to use as temporary storage
 464  * @head:       the head for your list.
 465  * @member:     the name of the list_struct within the struct.
 466  */
 467 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 468         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
 469                 n = list_entry(pos->member.next, typeof(*pos), member);         \
 470              &pos->member != (head);                                            \
 471              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 472
 473 /**
 474  * list_for_each_entry_safe_from - iterate over list of given type
 475  *                      from existing point safe against removal of list entry
 476  * @pos:        the type * to use as a loop counter.
 477  * @n:          another type * to use as temporary storage
 478  * @head:       the head for your list.
 479  * @member:     the name of the list_struct within the struct.
 480  */
 481 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 482         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
 483              &pos->member != (head);                                            \
 484              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 485
 486 /**
 487  * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
 488  *                                    removal of list entry
 489  * @pos:        the type * to use as a loop counter.
 490  * @n:          another type * to use as temporary storage
 491  * @head:       the head for your list.
 492  * @member:     the name of the list_struct within the struct.
 493  */
 494 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 495         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 496                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 497              &pos->member != (head);                                    \
 498              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 499
 500 /**
 501  * list_for_each_rcu    -       iterate over an rcu-protected list
 502  * @pos:        the &struct list_head to use as a loop counter.
 503  * @head:       the head for your list.
 504  *
 505  * This list-traversal primitive may safely run concurrently with
 506  * the _rcu list-mutation primitives such as list_add_rcu()
 507  * as long as the traversal is guarded by rcu_read_lock().
 508  */
 509 #define list_for_each_rcu(pos, head) \
 510         for (pos = (head)->next; \
 511                 prefetch(rcu_dereference(pos)->next), pos != (head); \
 512                 pos = pos->next)
 513
 514 #define __list_for_each_rcu(pos, head) \
 515         for (pos = (head)->next; \
 516                 rcu_dereference(pos) != (head); \
 517                 pos = pos->next)
 518
 519 /**
 520  * list_for_each_safe_rcu       -       iterate over an rcu-protected list safe
 521  *                                      against removal of list entry
 522  * @pos:        the &struct list_head to use as a loop counter.
 523  * @n:          another &struct list_head to use as temporary storage
 524  * @head:       the head for your list.
 525  *
 526  * This list-traversal primitive may safely run concurrently with
 527  * the _rcu list-mutation primitives such as list_add_rcu()
 528  * as long as the traversal is guarded by rcu_read_lock().
 529  */
 530 #define list_for_each_safe_rcu(pos, n, head) \
 531         for (pos = (head)->next; \
 532                 n = rcu_dereference(pos)->next, pos != (head); \
 533                 pos = n)
 534
 535 /**
 536  * list_for_each_entry_rcu      -       iterate over rcu list of given type
 537  * @pos:        the type * to use as a loop counter.
 538  * @head:       the head for your list.
 539  * @member:     the name of the list_struct within the struct.
 540  *
 541  * This list-traversal primitive may safely run concurrently with
 542  * the _rcu list-mutation primitives such as list_add_rcu()
 543  * as long as the traversal is guarded by rcu_read_lock().
 544  */
 545 #define list_for_each_entry_rcu(pos, head, member) \
 546         for (pos = list_entry((head)->next, typeof(*pos), member); \
 547                 prefetch(rcu_dereference(pos)->member.next), \
 548                         &pos->member != (head); \
 549                 pos = list_entry(pos->member.next, typeof(*pos), member))
 550
 551
 552 /**
 553  * list_for_each_continue_rcu   -       iterate over an rcu-protected list
 554  *                      continuing after existing point.
 555  * @pos:        the &struct list_head to use as a loop counter.
 556  * @head:       the head for your list.
 557  *
 558  * This list-traversal primitive may safely run concurrently with
 559  * the _rcu list-mutation primitives such as list_add_rcu()
 560  * as long as the traversal is guarded by rcu_read_lock().
 561  */
 562 #define list_for_each_continue_rcu(pos, head) \
 563         for ((pos) = (pos)->next; \
 564                 prefetch(rcu_dereference((pos))->next), (pos) != (head); \
 565                 (pos) = (pos)->next)
 566
 567 /*
 568  * Double linked lists with a single pointer list head.
 569  * Mostly useful for hash tables where the two pointer list head is
 570  * too wasteful.
 571  * You lose the ability to access the tail in O(1).
 572  */
 573
 574 struct hlist_head {
 575         struct hlist_node *first;
 576 };
 577
 578 struct hlist_node {
 579         struct hlist_node *next, **pprev;
 580 };
 581
 582 #define HLIST_HEAD_INIT { .first = NULL }
 583 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 584 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 585 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 586 {
 587         h->next = NULL;
 588         h->pprev = NULL;
 589 }
 590
 591 static inline int hlist_unhashed(const struct hlist_node *h)
 592 {
 593         return !h->pprev;
 594 }
 595
 596 static inline int hlist_empty(const struct hlist_head *h)
 597 {
 598         return !h->first;
 599 }
 600
 601 static inline void __hlist_del(struct hlist_node *n)
 602 {
 603         struct hlist_node *next = n->next;
 604         struct hlist_node **pprev = n->pprev;
 605         *pprev = next;
 606         if (next)
 607                 next->pprev = pprev;
 608 }
 609
 610 static inline void hlist_del(struct hlist_node *n)
 611 {
 612         __hlist_del(n);
 613         n->next = LIST_POISON1;
 614         n->pprev = LIST_POISON2;
 615 }
 616
 617 /**
 618  * hlist_del_rcu - deletes entry from hash list without re-initialization
 619  * @n: the element to delete from the hash list.
 620  *
 621  * Note: list_unhashed() on entry does not return true after this,
 622  * the entry is in an undefined state. It is useful for RCU based
 623  * lockfree traversal.
 624  *
 625  * In particular, it means that we can not poison the forward
 626  * pointers that may still be used for walking the hash list.
 627  *
 628  * The caller must take whatever precautions are necessary
 629  * (such as holding appropriate locks) to avoid racing
 630  * with another list-mutation primitive, such as hlist_add_head_rcu()
 631  * or hlist_del_rcu(), running on this same list.
 632  * However, it is perfectly legal to run concurrently with
 633  * the _rcu list-traversal primitives, such as
 634  * hlist_for_each_entry().
 635  */
 636 static inline void hlist_del_rcu(struct hlist_node *n)
 637 {
 638         __hlist_del(n);
 639         n->pprev = LIST_POISON2;
 640 }
 641
 642 static inline void hlist_del_init(struct hlist_node *n)
 643 {
 644         if (!hlist_unhashed(n)) {
 645                 __hlist_del(n);
 646                 INIT_HLIST_NODE(n);
 647         }
 648 }
 649
 650 /*
 651  * hlist_replace_rcu - replace old entry by new one
 652  * @old : the element to be replaced
 653  * @new : the new element to insert
 654  *
 655  * The old entry will be replaced with the new entry atomically.
 656  */
 657 static inline void hlist_replace_rcu(struct hlist_node *old,
 658                                         struct hlist_node *new)
 659 {
 660         struct hlist_node *next = old->next;
 661
 662         new->next = next;
 663         new->pprev = old->pprev;
 664         smp_wmb();
 665         if (next)
 666                 new->next->pprev = &new->next;
 667         *new->pprev = new;
 668         old->pprev = LIST_POISON2;
 669 }
 670
 671 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 672 {
 673         struct hlist_node *first = h->first;
 674         n->next = first;
 675         if (first)
 676                 first->pprev = &n->next;
 677         h->first = n;
 678         n->pprev = &h->first;
 679 }
 680
 681
 682 /**
 683  * hlist_add_head_rcu - adds the specified element to the specified hlist,
 684  * while permitting racing traversals.
 685  * @n: the element to add to the hash list.
 686  * @h: the list to add to.
 687  *
 688  * The caller must take whatever precautions are necessary
 689  * (such as holding appropriate locks) to avoid racing
 690  * with another list-mutation primitive, such as hlist_add_head_rcu()
 691  * or hlist_del_rcu(), running on this same list.
 692  * However, it is perfectly legal to run concurrently with
 693  * the _rcu list-traversal primitives, such as
 694  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 695  * problems on Alpha CPUs.  Regardless of the type of CPU, the
 696  * list-traversal primitive must be guarded by rcu_read_lock().
 697  */
 698 static inline void hlist_add_head_rcu(struct hlist_node *n,
 699                                         struct hlist_head *h)
 700 {
 701         struct hlist_node *first = h->first;
 702         n->next = first;
 703         n->pprev = &h->first;
 704         smp_wmb();
 705         if (first)
 706                 first->pprev = &n->next;
 707         h->first = n;
 708 }
 709
 710 /* next must be != NULL */
 711 static inline void hlist_add_before(struct hlist_node *n,
 712                                         struct hlist_node *next)
 713 {
 714         n->pprev = next->pprev;
 715         n->next = next;
 716         next->pprev = &n->next;
 717         *(n->pprev) = n;
 718 }
 719
 720 static inline void hlist_add_after(struct hlist_node *n,
 721                                         struct hlist_node *next)
 722 {
 723         next->next = n->next;
 724         n->next = next;
 725         next->pprev = &n->next;
 726
 727         if(next->next)
 728                 next->next->pprev  = &next->next;
 729 }
 730
 731 /**
 732  * hlist_add_before_rcu - adds the specified element to the specified hlist
 733  * before the specified node while permitting racing traversals.
 734  * @n: the new element to add to the hash list.
 735  * @next: the existing element to add the new element before.
 736  *
 737  * The caller must take whatever precautions are necessary
 738  * (such as holding appropriate locks) to avoid racing
 739  * with another list-mutation primitive, such as hlist_add_head_rcu()
 740  * or hlist_del_rcu(), running on this same list.
 741  * However, it is perfectly legal to run concurrently with
 742  * the _rcu list-traversal primitives, such as
 743  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 744  * problems on Alpha CPUs.
 745  */
 746 static inline void hlist_add_before_rcu(struct hlist_node *n,
 747                                         struct hlist_node *next)
 748 {
 749         n->pprev = next->pprev;
 750         n->next = next;
 751         smp_wmb();
 752         next->pprev = &n->next;
 753         *(n->pprev) = n;
 754 }
 755
 756 /**
 757  * hlist_add_after_rcu - adds the specified element to the specified hlist
 758  * after the specified node while permitting racing traversals.
 759  * @prev: the existing element to add the new element after.
 760  * @n: the new element to add to the hash list.
 761  *
 762  * The caller must take whatever precautions are necessary
 763  * (such as holding appropriate locks) to avoid racing
 764  * with another list-mutation primitive, such as hlist_add_head_rcu()
 765  * or hlist_del_rcu(), running on this same list.
 766  * However, it is perfectly legal to run concurrently with
 767  * the _rcu list-traversal primitives, such as
 768  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 769  * problems on Alpha CPUs.
 770  */
 771 static inline void hlist_add_after_rcu(struct hlist_node *prev,
 772                                        struct hlist_node *n)
 773 {
 774         n->next = prev->next;
 775         n->pprev = &prev->next;
 776         smp_wmb();
 777         prev->next = n;
 778         if (n->next)
 779                 n->next->pprev = &n->next;
 780 }
 781
 782 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 783
 784 #define hlist_for_each(pos, head) \
 785         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 786              pos = pos->next)
 787
 788 #define hlist_for_each_safe(pos, n, head) \
 789         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 790              pos = n)
 791
 792 /**
 793  * hlist_for_each_entry - iterate over list of given type
 794  * @tpos:       the type * to use as a loop counter.
 795  * @pos:        the &struct hlist_node to use as a loop counter.
 796  * @head:       the head for your list.
 797  * @member:     the name of the hlist_node within the struct.
 798  */
 799 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 800         for (pos = (head)->first;                                        \
 801              pos && ({ prefetch(pos->next); 1;}) &&                      \
 802                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 803              pos = pos->next)
 804
 805 /**
 806  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
 807  * @tpos:       the type * to use as a loop counter.
 808  * @pos:        the &struct hlist_node to use as a loop counter.
 809  * @member:     the name of the hlist_node within the struct.
 810  */
 811 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 812         for (pos = (pos)->next;                                          \
 813              pos && ({ prefetch(pos->next); 1;}) &&                      \
 814                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 815              pos = pos->next)
 816
 817 /**
 818  * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
 819  * @tpos:       the type * to use as a loop counter.
 820  * @pos:        the &struct hlist_node to use as a loop counter.
 821  * @member:     the name of the hlist_node within the struct.
 822  */
 823 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 824         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 825                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 826              pos = pos->next)
 827
 828 /**
 829  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 830  * @tpos:       the type * to use as a loop counter.
 831  * @pos:        the &struct hlist_node to use as a loop counter.
 832  * @n:          another &struct hlist_node to use as temporary storage
 833  * @head:       the head for your list.
 834  * @member:     the name of the hlist_node within the struct.
 835  */
 836 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 837         for (pos = (head)->first;                                        \
 838              pos && ({ n = pos->next; 1; }) &&                           \
 839                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 840              pos = n)
 841
 842 /**
 843  * hlist_for_each_entry_rcu - iterate over rcu list of given type
 844  * @tpos:       the type * to use as a loop counter.
 845  * @pos:        the &struct hlist_node to use as a loop counter.
 846  * @head:       the head for your list.
 847  * @member:     the name of the hlist_node within the struct.
 848  *
 849  * This list-traversal primitive may safely run concurrently with
 850  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 851  * as long as the traversal is guarded by rcu_read_lock().
 852  */
 853 #define hlist_for_each_entry_rcu(tpos, pos, head, member)                \
 854         for (pos = (head)->first;                                        \
 855              rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&     \
 856                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 857              pos = pos->next)
 858
 859 #else
 860 #warning "don't include kernel headers in userspace"
 861 #endif /* __KERNEL__ */
 862 #endif