ia64/xen-unstable

changeset 14628:c16e258fcac5

xen: Sync the list.h macros to Linux 2.6.18.
This also pulls in RCU-related functions, superceding a patch from Mike Day.
Signed-off-by: Keir Fraser <keir@xensource.com>
author kfraser@localhost.localdomain
date Wed Mar 28 14:43:41 2007 +0100 (2007-03-28)
parents 72ea3ff64ad8
children 41b8af05cb68
files xen/include/xen/list.h
line diff
     1.1 --- a/xen/include/xen/list.h	Wed Mar 28 14:42:54 2007 +0100
     1.2 +++ b/xen/include/xen/list.h	Wed Mar 28 14:43:41 2007 +0100
     1.3 @@ -1,13 +1,21 @@
     1.4  /******************************************************************************
     1.5   * list.h
     1.6   * 
     1.7 - * Useful linked-list definitions taken from the Linux kernel.
     1.8 + * Useful linked-list definitions taken from the Linux kernel (2.6.18).
     1.9   */
    1.10  
    1.11  #ifndef __XEN_LIST_H__
    1.12  #define __XEN_LIST_H__
    1.13  
    1.14  #include <xen/lib.h>
    1.15 +#include <asm/system.h>
    1.16 +
    1.17 +/* These are non-NULL pointers that will result in page faults
    1.18 + * under normal circumstances, used to verify that nobody uses
    1.19 + * non-initialized list entries.
    1.20 + */
    1.21 +#define LIST_POISON1  ((void *) 0x00100100)
    1.22 +#define LIST_POISON2  ((void *) 0x00200200)
    1.23  
    1.24  /*
    1.25   * Simple doubly linked list implementation.
    1.26 @@ -28,9 +36,11 @@ struct list_head {
    1.27  #define LIST_HEAD(name) \
    1.28      struct list_head name = LIST_HEAD_INIT(name)
    1.29  
    1.30 -#define INIT_LIST_HEAD(ptr) do { \
    1.31 -    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
    1.32 -} while (0)
    1.33 +static inline void INIT_LIST_HEAD(struct list_head *list)
    1.34 +{
    1.35 +    list->next = list;
    1.36 +    list->prev = list;
    1.37 +}
    1.38  
    1.39  /*
    1.40   * Insert a new entry between two known consecutive entries. 
    1.41 @@ -38,9 +48,9 @@ struct list_head {
    1.42   * This is only for internal list manipulation where we know
    1.43   * the prev/next entries already!
    1.44   */
    1.45 -static inline void __list_add(struct list_head * new,
    1.46 -    struct list_head * prev,
    1.47 -    struct list_head * next)
    1.48 +static inline void __list_add(struct list_head *new,
    1.49 +                              struct list_head *prev,
    1.50 +                              struct list_head *next)
    1.51  {
    1.52      next->prev = new;
    1.53      new->next = next;
    1.54 @@ -75,14 +85,74 @@ static inline void list_add_tail(struct 
    1.55  }
    1.56  
    1.57  /*
    1.58 + * Insert a new entry between two known consecutive entries.
    1.59 + *
    1.60 + * This is only for internal list manipulation where we know
    1.61 + * the prev/next entries already!
    1.62 + */
    1.63 +static inline void __list_add_rcu(struct list_head *new,
    1.64 +                                  struct list_head *prev,
    1.65 +                                  struct list_head *next)
    1.66 +{
    1.67 +    new->next = next;
    1.68 +    new->prev = prev;
    1.69 +    smp_wmb();
    1.70 +    next->prev = new;
    1.71 +    prev->next = new;
    1.72 +}
    1.73 +
    1.74 +/**
    1.75 + * list_add_rcu - add a new entry to rcu-protected list
    1.76 + * @new: new entry to be added
    1.77 + * @head: list head to add it after
    1.78 + *
    1.79 + * Insert a new entry after the specified head.
    1.80 + * This is good for implementing stacks.
    1.81 + *
    1.82 + * The caller must take whatever precautions are necessary
    1.83 + * (such as holding appropriate locks) to avoid racing
    1.84 + * with another list-mutation primitive, such as list_add_rcu()
    1.85 + * or list_del_rcu(), running on this same list.
    1.86 + * However, it is perfectly legal to run concurrently with
    1.87 + * the _rcu list-traversal primitives, such as
    1.88 + * list_for_each_entry_rcu().
    1.89 + */
    1.90 +static inline void list_add_rcu(struct list_head *new, struct list_head *head)
    1.91 +{
    1.92 +    __list_add_rcu(new, head, head->next);
    1.93 +}
    1.94 +
    1.95 +/**
    1.96 + * list_add_tail_rcu - add a new entry to rcu-protected list
    1.97 + * @new: new entry to be added
    1.98 + * @head: list head to add it before
    1.99 + *
   1.100 + * Insert a new entry before the specified head.
   1.101 + * This is useful for implementing queues.
   1.102 + *
   1.103 + * The caller must take whatever precautions are necessary
   1.104 + * (such as holding appropriate locks) to avoid racing
   1.105 + * with another list-mutation primitive, such as list_add_tail_rcu()
   1.106 + * or list_del_rcu(), running on this same list.
   1.107 + * However, it is perfectly legal to run concurrently with
   1.108 + * the _rcu list-traversal primitives, such as
   1.109 + * list_for_each_entry_rcu().
   1.110 + */
   1.111 +static inline void list_add_tail_rcu(struct list_head *new,
   1.112 +                                     struct list_head *head)
   1.113 +{
   1.114 +    __list_add_rcu(new, head->prev, head);
   1.115 +}
   1.116 +
   1.117 +/*
   1.118   * Delete a list entry by making the prev/next entries
   1.119   * point to each other.
   1.120   *
   1.121   * This is only for internal list manipulation where we know
   1.122   * the prev/next entries already!
   1.123   */
   1.124 -static inline void __list_del(struct list_head * prev,
   1.125 -                              struct list_head * next)
   1.126 +static inline void __list_del(struct list_head *prev,
   1.127 +                              struct list_head *next)
   1.128  {
   1.129      next->prev = prev;
   1.130      prev->next = next;
   1.131 @@ -99,6 +169,79 @@ static inline void list_del(struct list_
   1.132      ASSERT(entry->next->prev == entry);
   1.133      ASSERT(entry->prev->next == entry);
   1.134      __list_del(entry->prev, entry->next);
   1.135 +    entry->next = LIST_POISON1;
   1.136 +    entry->prev = LIST_POISON2;
   1.137 +}
   1.138 +
   1.139 +/**
   1.140 + * list_del_rcu - deletes entry from list without re-initialization
   1.141 + * @entry: the element to delete from the list.
   1.142 + *
   1.143 + * Note: list_empty on entry does not return true after this,
   1.144 + * the entry is in an undefined state. It is useful for RCU based
   1.145 + * lockfree traversal.
   1.146 + *
   1.147 + * In particular, it means that we can not poison the forward
   1.148 + * pointers that may still be used for walking the list.
   1.149 + *
   1.150 + * The caller must take whatever precautions are necessary
   1.151 + * (such as holding appropriate locks) to avoid racing
   1.152 + * with another list-mutation primitive, such as list_del_rcu()
   1.153 + * or list_add_rcu(), running on this same list.
   1.154 + * However, it is perfectly legal to run concurrently with
   1.155 + * the _rcu list-traversal primitives, such as
   1.156 + * list_for_each_entry_rcu().
   1.157 + *
   1.158 + * Note that the caller is not permitted to immediately free
   1.159 + * the newly deleted entry.  Instead, either synchronize_rcu()
   1.160 + * or call_rcu() must be used to defer freeing until an RCU
   1.161 + * grace period has elapsed.
   1.162 + */
   1.163 +static inline void list_del_rcu(struct list_head *entry)
   1.164 +{
   1.165 +    __list_del(entry->prev, entry->next);
   1.166 +    entry->prev = LIST_POISON2;
   1.167 +}
   1.168 +
   1.169 +/**
   1.170 + * list_replace - replace old entry by new one
   1.171 + * @old : the element to be replaced
   1.172 + * @new : the new element to insert
   1.173 + * Note: if 'old' was empty, it will be overwritten.
   1.174 + */
   1.175 +static inline void list_replace(struct list_head *old,
   1.176 +                                struct list_head *new)
   1.177 +{
   1.178 +    new->next = old->next;
   1.179 +    new->next->prev = new;
   1.180 +    new->prev = old->prev;
   1.181 +    new->prev->next = new;
   1.182 +}
   1.183 +
   1.184 +static inline void list_replace_init(struct list_head *old,
   1.185 +                                     struct list_head *new)
   1.186 +{
   1.187 +    list_replace(old, new);
   1.188 +    INIT_LIST_HEAD(old);
   1.189 +}
   1.190 +
   1.191 +/*
   1.192 + * list_replace_rcu - replace old entry by new one
   1.193 + * @old : the element to be replaced
   1.194 + * @new : the new element to insert
   1.195 + *
   1.196 + * The old entry will be replaced with the new entry atomically.
   1.197 + * Note: 'old' should not be empty.
   1.198 + */
   1.199 +static inline void list_replace_rcu(struct list_head *old,
   1.200 +                                    struct list_head *new)
   1.201 +{
   1.202 +    new->next = old->next;
   1.203 +    new->prev = old->prev;
   1.204 +    smp_wmb();
   1.205 +    new->next->prev = new;
   1.206 +    new->prev->next = new;
   1.207 +    old->prev = LIST_POISON2;
   1.208  }
   1.209  
   1.210  /**
   1.211 @@ -112,33 +255,105 @@ static inline void list_del_init(struct 
   1.212  }
   1.213  
   1.214  /**
   1.215 + * list_move - delete from one list and add as another's head
   1.216 + * @list: the entry to move
   1.217 + * @head: the head that will precede our entry
   1.218 + */
   1.219 +static inline void list_move(struct list_head *list, struct list_head *head)
   1.220 +{
   1.221 +    __list_del(list->prev, list->next);
   1.222 +    list_add(list, head);
   1.223 +}
   1.224 +
   1.225 +/**
   1.226 + * list_move_tail - delete from one list and add as another's tail
   1.227 + * @list: the entry to move
   1.228 + * @head: the head that will follow our entry
   1.229 + */
   1.230 +static inline void list_move_tail(struct list_head *list,
   1.231 +                                  struct list_head *head)
   1.232 +{
   1.233 +    __list_del(list->prev, list->next);
   1.234 +    list_add_tail(list, head);
   1.235 +}
   1.236 +
   1.237 +/**
   1.238 + * list_is_last - tests whether @list is the last entry in list @head
   1.239 + * @list: the entry to test
   1.240 + * @head: the head of the list
   1.241 + */
   1.242 +static inline int list_is_last(const struct list_head *list,
   1.243 +                               const struct list_head *head)
   1.244 +{
   1.245 +    return list->next == head;
   1.246 +}
   1.247 +
   1.248 +/**
   1.249   * list_empty - tests whether a list is empty
   1.250   * @head: the list to test.
   1.251   */
   1.252 -static inline int list_empty(struct list_head *head)
   1.253 +static inline int list_empty(const struct list_head *head)
   1.254  {
   1.255      return head->next == head;
   1.256  }
   1.257  
   1.258  /**
   1.259 + * list_empty_careful - tests whether a list is empty and not being modified
   1.260 + * @head: the list to test
   1.261 + *
   1.262 + * Description:
   1.263 + * tests whether a list is empty _and_ checks that no other CPU might be
   1.264 + * in the process of modifying either member (next or prev)
   1.265 + *
   1.266 + * NOTE: using list_empty_careful() without synchronization
   1.267 + * can only be safe if the only activity that can happen
   1.268 + * to the list entry is list_del_init(). Eg. it cannot be used
   1.269 + * if another CPU could re-list_add() it.
   1.270 + */
   1.271 +static inline int list_empty_careful(const struct list_head *head)
   1.272 +{
   1.273 +    struct list_head *next = head->next;
   1.274 +    return (next == head) && (next == head->prev);
   1.275 +}
   1.276 +
   1.277 +static inline void __list_splice(struct list_head *list,
   1.278 +                                 struct list_head *head)
   1.279 +{
   1.280 +    struct list_head *first = list->next;
   1.281 +    struct list_head *last = list->prev;
   1.282 +    struct list_head *at = head->next;
   1.283 +
   1.284 +    first->prev = head;
   1.285 +    head->next = first;
   1.286 +
   1.287 +    last->next = at;
   1.288 +    at->prev = last;
   1.289 +}
   1.290 +
   1.291 +/**
   1.292   * list_splice - join two lists
   1.293   * @list: the new list to add.
   1.294   * @head: the place to add it in the first list.
   1.295   */
   1.296  static inline void list_splice(struct list_head *list, struct list_head *head)
   1.297  {
   1.298 -    struct list_head *first = list->next;
   1.299 +    if (!list_empty(list))
   1.300 +        __list_splice(list, head);
   1.301 +}
   1.302  
   1.303 -    if ( first != list )
   1.304 -    {
   1.305 -        struct list_head *last = list->prev;
   1.306 -        struct list_head *at = head->next;
   1.307 -
   1.308 -        first->prev = head;
   1.309 -        head->next = first;
   1.310 -
   1.311 -        last->next = at;
   1.312 -        at->prev = last;
   1.313 +/**
   1.314 + * list_splice_init - join two lists and reinitialise the emptied list.
   1.315 + * @list: the new list to add.
   1.316 + * @head: the place to add it in the first list.
   1.317 + *
   1.318 + * The list at @list is reinitialised
   1.319 + */
   1.320 +static inline void list_splice_init(struct list_head *list,
   1.321 +                                    struct list_head *head)
   1.322 +{
   1.323 +    if (!list_empty(list)) {
   1.324 +        __list_splice(list, head);
   1.325 +        INIT_LIST_HEAD(list);
   1.326      }
   1.327  }
   1.328  
   1.329 @@ -149,64 +364,250 @@ static inline void list_splice(struct li
   1.330   * @member:    the name of the list_struct within the struct.
   1.331   */
   1.332  #define list_entry(ptr, type, member) \
   1.333 -    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
   1.334 +    container_of(ptr, type, member)
   1.335  
   1.336  /**
   1.337   * list_for_each    -    iterate over a list
   1.338 - * @pos:    the &struct list_head to use as a loop counter.
   1.339 + * @pos:    the &struct list_head to use as a loop cursor.
   1.340   * @head:    the head for your list.
   1.341   */
   1.342 -#define list_for_each(pos, head)                                \
   1.343 -    for ( pos = (head)->next; pos != (head); pos = pos->next )
   1.344 +#define list_for_each(pos, head)                                        \
   1.345 +    for (pos = (head)->next; prefetch(pos->next), pos != (head);        \
   1.346 +         pos = pos->next)
   1.347  
   1.348  /**
   1.349 - * list_for_each_safe    -    iterate over a list safe against removal
   1.350 - *                            of list entry
   1.351 - * @pos:    the &struct list_head to use as a loop counter.
   1.352 - * @n:        another &struct list_head to use as temporary storage
   1.353 - * @head:    the head for your list.
   1.354 + * __list_for_each - iterate over a list
   1.355 + * @pos:    the &struct list_head to use as a loop cursor.
   1.356 + * @head:   the head for your list.
   1.357 + *
   1.358 + * This variant differs from list_for_each() in that it's the
   1.359 + * simplest possible list iteration code, no prefetching is done.
   1.360 + * Use this for code that knows the list to be very short (empty
   1.361 + * or 1 entry) most of the time.
   1.362 + */
   1.363 +#define __list_for_each(pos, head)                              \
   1.364 +    for (pos = (head)->next; pos != (head); pos = pos->next)
   1.365 +
   1.366 +/**
   1.367 + * list_for_each_prev - iterate over a list backwards
   1.368 + * @pos:    the &struct list_head to use as a loop cursor.
   1.369 + * @head:   the head for your list.
   1.370 + */
   1.371 +#define list_for_each_prev(pos, head)                                   \
   1.372 +    for (pos = (head)->prev; prefetch(pos->prev), pos != (head);        \
   1.373 +         pos = pos->prev)
   1.374 +
   1.375 +/**
   1.376 + * list_for_each_safe - iterate over a list safe against removal of list entry
   1.377 + * @pos:    the &struct list_head to use as a loop cursor.
   1.378 + * @n:      another &struct list_head to use as temporary storage
   1.379 + * @head:   the head for your list.
   1.380   */
   1.381  #define list_for_each_safe(pos, n, head)                        \
   1.382 -    for ( pos = (head)->next, n = pos->next; pos != (head);     \
   1.383 -          pos = n, n = pos->next )
   1.384 +    for (pos = (head)->next, n = pos->next; pos != (head);      \
   1.385 +         pos = n, n = pos->next)
   1.386  
   1.387  /**
   1.388   * list_for_each_backwards_safe    -    iterate backwards over a list safe
   1.389   *                                      against removal of list entry
   1.390   * @pos:    the &struct list_head to use as a loop counter.
   1.391 - * @n:        another &struct list_head to use as temporary storage
   1.392 - * @head:    the head for your list.
   1.393 + * @n:      another &struct list_head to use as temporary storage
   1.394 + * @head:   the head for your list.
   1.395   */
   1.396  #define list_for_each_backwards_safe(pos, n, head)              \
   1.397      for ( pos = (head)->prev, n = pos->prev; pos != (head);     \
   1.398            pos = n, n = pos->prev )
   1.399  
   1.400  /**
   1.401 - * list_for_each_entry    -    iterate over list of given type
   1.402 - * @pos:    the type * to use as a loop counter.
   1.403 - * @head:    the head for your list.
   1.404 - * @member:    the name of the list_struct within the struct.
   1.405 + * list_for_each_entry - iterate over list of given type
   1.406 + * @pos:    the type * to use as a loop cursor.
   1.407 + * @head:   the head for your list.
   1.408 + * @member: the name of the list_struct within the struct.
   1.409   */
   1.410  #define list_for_each_entry(pos, head, member)                          \
   1.411 -    for ( pos = list_entry((head)->next, typeof(*pos), member),         \
   1.412 -          prefetch(pos->member.next);                                   \
   1.413 -          &pos->member != (head);                                       \
   1.414 -          pos = list_entry(pos->member.next, typeof(*pos), member),     \
   1.415 -          prefetch(pos->member.next) )
   1.416 +    for (pos = list_entry((head)->next, typeof(*pos), member);          \
   1.417 +         prefetch(pos->member.next), &pos->member != (head);            \
   1.418 +         pos = list_entry(pos->member.next, typeof(*pos), member))
   1.419 +
   1.420 +/**
   1.421 + * list_for_each_entry_reverse - iterate backwards over list of given type.
   1.422 + * @pos:    the type * to use as a loop cursor.
   1.423 + * @head:   the head for your list.
   1.424 + * @member: the name of the list_struct within the struct.
   1.425 + */
   1.426 +#define list_for_each_entry_reverse(pos, head, member)                  \
   1.427 +    for (pos = list_entry((head)->prev, typeof(*pos), member);          \
   1.428 +         prefetch(pos->member.prev), &pos->member != (head);            \
   1.429 +         pos = list_entry(pos->member.prev, typeof(*pos), member))
   1.430 +
   1.431 +/**
   1.432 + * list_prepare_entry - prepare a pos entry for use in
   1.433 + *                      list_for_each_entry_continue
   1.434 + * @pos:    the type * to use as a start point
   1.435 + * @head:   the head of the list
   1.436 + * @member: the name of the list_struct within the struct.
   1.437 + *
   1.438 + * Prepares a pos entry for use as a start point in
   1.439 + * list_for_each_entry_continue.
   1.440 + */
   1.441 +#define list_prepare_entry(pos, head, member)           \
   1.442 +    ((pos) ? : list_entry(head, typeof(*pos), member))
   1.443 +
   1.444 +/**
   1.445 + * list_for_each_entry_continue - continue iteration over list of given type
   1.446 + * @pos:    the type * to use as a loop cursor.
   1.447 + * @head:   the head for your list.
   1.448 + * @member: the name of the list_struct within the struct.
   1.449 + *
   1.450 + * Continue to iterate over list of given type, continuing after
   1.451 + * the current position.
   1.452 + */
   1.453 +#define list_for_each_entry_continue(pos, head, member)                 \
   1.454 +    for (pos = list_entry(pos->member.next, typeof(*pos), member);      \
   1.455 +         prefetch(pos->member.next), &pos->member != (head);            \
   1.456 +         pos = list_entry(pos->member.next, typeof(*pos), member))
   1.457 +
   1.458 +/**
   1.459 + * list_for_each_entry_from - iterate over list of given type from the
   1.460 + *                            current point
   1.461 + * @pos:    the type * to use as a loop cursor.
   1.462 + * @head:   the head for your list.
   1.463 + * @member: the name of the list_struct within the struct.
   1.464 + *
   1.465 + * Iterate over list of given type, continuing from current position.
   1.466 + */
   1.467 +#define list_for_each_entry_from(pos, head, member)                     \
   1.468 +    for (; prefetch(pos->member.next), &pos->member != (head);          \
   1.469 +         pos = list_entry(pos->member.next, typeof(*pos), member))
   1.470  
   1.471  /**
   1.472   * list_for_each_entry_safe - iterate over list of given type safe
   1.473   *                            against removal of list entry
   1.474 - * @pos:    the type * to use as a loop counter.
   1.475 - * @n:        another type * to use as temporary storage
   1.476 - * @head:    the head for your list.
   1.477 - * @member:    the name of the list_struct within the struct.
   1.478 + * @pos:    the type * to use as a loop cursor.
   1.479 + * @n:      another type * to use as temporary storage
   1.480 + * @head:   the head for your list.
   1.481 + * @member: the name of the list_struct within the struct.
   1.482   */
   1.483  #define list_for_each_entry_safe(pos, n, head, member)                  \
   1.484 -    for ( pos = list_entry((head)->next, typeof(*pos), member),         \
   1.485 -          n = list_entry(pos->member.next, typeof(*pos), member);       \
   1.486 -          &pos->member != (head);                                       \
   1.487 -          pos = n, n = list_entry(n->member.next, typeof(*n), member) )
   1.488 +    for (pos = list_entry((head)->next, typeof(*pos), member),          \
   1.489 +         n = list_entry(pos->member.next, typeof(*pos), member);        \
   1.490 +         &pos->member != (head);                                        \
   1.491 +         pos = n, n = list_entry(n->member.next, typeof(*n), member))
   1.492 +
   1.493 +/**
   1.494 + * list_for_each_entry_safe_continue
   1.495 + * @pos:    the type * to use as a loop cursor.
   1.496 + * @n:      another type * to use as temporary storage
   1.497 + * @head:   the head for your list.
   1.498 + * @member: the name of the list_struct within the struct.
   1.499 + *
   1.500 + * Iterate over list of given type, continuing after current point,
   1.501 + * safe against removal of list entry.
   1.502 + */
   1.503 +#define list_for_each_entry_safe_continue(pos, n, head, member)         \
   1.504 +    for (pos = list_entry(pos->member.next, typeof(*pos), member),      \
   1.505 +         n = list_entry(pos->member.next, typeof(*pos), member);        \
   1.506 +         &pos->member != (head);                                        \
   1.507 +         pos = n, n = list_entry(n->member.next, typeof(*n), member))
   1.508 +
   1.509 +/**
   1.510 + * list_for_each_entry_safe_from
   1.511 + * @pos:    the type * to use as a loop cursor.
   1.512 + * @n:      another type * to use as temporary storage
   1.513 + * @head:   the head for your list.
   1.514 + * @member: the name of the list_struct within the struct.
   1.515 + *
   1.516 + * Iterate over list of given type from current point, safe against
   1.517 + * removal of list entry.
   1.518 + */
   1.519 +#define list_for_each_entry_safe_from(pos, n, head, member)             \
   1.520 +    for (n = list_entry(pos->member.next, typeof(*pos), member);        \
   1.521 +         &pos->member != (head);                                        \
   1.522 +         pos = n, n = list_entry(n->member.next, typeof(*n), member))
   1.523 +
   1.524 +/**
   1.525 + * list_for_each_entry_safe_reverse
   1.526 + * @pos:    the type * to use as a loop cursor.
   1.527 + * @n:      another type * to use as temporary storage
   1.528 + * @head:   the head for your list.
   1.529 + * @member: the name of the list_struct within the struct.
   1.530 + *
   1.531 + * Iterate backwards over list of given type, safe against removal
   1.532 + * of list entry.
   1.533 + */
   1.534 +#define list_for_each_entry_safe_reverse(pos, n, head, member)          \
   1.535 +    for (pos = list_entry((head)->prev, typeof(*pos), member),          \
   1.536 +         n = list_entry(pos->member.prev, typeof(*pos), member);        \
   1.537 +         &pos->member != (head);                                        \
   1.538 +         pos = n, n = list_entry(n->member.prev, typeof(*n), member))
   1.539 +
   1.540 +/**
   1.541 + * list_for_each_rcu - iterate over an rcu-protected list
   1.542 + * @pos:  the &struct list_head to use as a loop cursor.
   1.543 + * @head: the head for your list.
   1.544 + *
   1.545 + * This list-traversal primitive may safely run concurrently with
   1.546 + * the _rcu list-mutation primitives such as list_add_rcu()
   1.547 + * as long as the traversal is guarded by rcu_read_lock().
   1.548 + */
   1.549 +#define list_for_each_rcu(pos, head)                            \
   1.550 +    for (pos = (head)->next;                                    \
   1.551 +         prefetch(rcu_dereference(pos)->next), pos != (head);   \
   1.552 +         pos = pos->next)
   1.553 +
   1.554 +#define __list_for_each_rcu(pos, head)          \
   1.555 +    for (pos = (head)->next;                    \
   1.556 +         rcu_dereference(pos) != (head);        \
   1.557 +         pos = pos->next)
   1.558 +
   1.559 +/**
   1.560 + * list_for_each_safe_rcu
   1.561 + * @pos:   the &struct list_head to use as a loop cursor.
   1.562 + * @n:     another &struct list_head to use as temporary storage
   1.563 + * @head:  the head for your list.
   1.564 + *
   1.565 + * Iterate over an rcu-protected list, safe against removal of list entry.
   1.566 + *
   1.567 + * This list-traversal primitive may safely run concurrently with
   1.568 + * the _rcu list-mutation primitives such as list_add_rcu()
   1.569 + * as long as the traversal is guarded by rcu_read_lock().
   1.570 + */
   1.571 +#define list_for_each_safe_rcu(pos, n, head)            \
   1.572 +    for (pos = (head)->next;                            \
   1.573 +         n = rcu_dereference(pos)->next, pos != (head); \
   1.574 +         pos = n)
   1.575 +
   1.576 +/**
   1.577 + * list_for_each_entry_rcu - iterate over rcu list of given type
   1.578 + * @pos:    the type * to use as a loop cursor.
   1.579 + * @head:   the head for your list.
   1.580 + * @member: the name of the list_struct within the struct.
   1.581 + *
   1.582 + * This list-traversal primitive may safely run concurrently with
   1.583 + * the _rcu list-mutation primitives such as list_add_rcu()
   1.584 + * as long as the traversal is guarded by rcu_read_lock().
   1.585 + */
   1.586 +#define list_for_each_entry_rcu(pos, head, member)                      \
   1.587 +    for (pos = list_entry((head)->next, typeof(*pos), member);          \
   1.588 +         prefetch(rcu_dereference(pos)->member.next),                   \
   1.589 +         &pos->member != (head);                                        \
   1.590 +         pos = list_entry(pos->member.next, typeof(*pos), member))
   1.591 +
   1.592 +/**
   1.593 + * list_for_each_continue_rcu
   1.594 + * @pos:    the &struct list_head to use as a loop cursor.
   1.595 + * @head:   the head for your list.
   1.596 + *
   1.597 + * Iterate over an rcu-protected list, continuing after current point.
   1.598 + *
   1.599 + * This list-traversal primitive may safely run concurrently with
   1.600 + * the _rcu list-mutation primitives such as list_add_rcu()
   1.601 + * as long as the traversal is guarded by rcu_read_lock().
   1.602 + */
   1.603 +#define list_for_each_continue_rcu(pos, head)                           \
   1.604 +    for ((pos) = (pos)->next;                                           \
   1.605 +         prefetch(rcu_dereference((pos))->next), (pos) != (head);       \
   1.606 +         (pos) = (pos)->next)
   1.607  
   1.608  /*
   1.609   * Double linked lists with a single pointer list head.
   1.610 @@ -247,34 +648,112 @@ static inline void __hlist_del(struct hl
   1.611      struct hlist_node *next = n->next;
   1.612      struct hlist_node **pprev = n->pprev;
   1.613      *pprev = next;
   1.614 -    if ( next )
   1.615 +    if (next)
   1.616          next->pprev = pprev;
   1.617  }
   1.618  
   1.619  static inline void hlist_del(struct hlist_node *n)
   1.620  {
   1.621      __hlist_del(n);
   1.622 +    n->next = LIST_POISON1;
   1.623 +    n->pprev = LIST_POISON2;
   1.624 +}
   1.625 +
   1.626 +/**
   1.627 + * hlist_del_rcu - deletes entry from hash list without re-initialization
   1.628 + * @n: the element to delete from the hash list.
   1.629 + *
   1.630 + * Note: list_unhashed() on entry does not return true after this,
   1.631 + * the entry is in an undefined state. It is useful for RCU based
   1.632 + * lockfree traversal.
   1.633 + *
   1.634 + * In particular, it means that we can not poison the forward
   1.635 + * pointers that may still be used for walking the hash list.
   1.636 + *
   1.637 + * The caller must take whatever precautions are necessary
   1.638 + * (such as holding appropriate locks) to avoid racing
   1.639 + * with another list-mutation primitive, such as hlist_add_head_rcu()
   1.640 + * or hlist_del_rcu(), running on this same list.
   1.641 + * However, it is perfectly legal to run concurrently with
   1.642 + * the _rcu list-traversal primitives, such as
   1.643 + * hlist_for_each_entry().
   1.644 + */
   1.645 +static inline void hlist_del_rcu(struct hlist_node *n)
   1.646 +{
   1.647 +    __hlist_del(n);
   1.648 +    n->pprev = LIST_POISON2;
   1.649  }
   1.650  
   1.651  static inline void hlist_del_init(struct hlist_node *n)
   1.652  {
   1.653 -    if ( !hlist_unhashed(n) )
   1.654 -    {
   1.655 +    if (!hlist_unhashed(n)) {
   1.656          __hlist_del(n);
   1.657          INIT_HLIST_NODE(n);
   1.658      }
   1.659  }
   1.660  
   1.661 +/*
   1.662 + * hlist_replace_rcu - replace old entry by new one
   1.663 + * @old : the element to be replaced
   1.664 + * @new : the new element to insert
   1.665 + *
   1.666 + * The old entry will be replaced with the new entry atomically.
   1.667 + */
   1.668 +static inline void hlist_replace_rcu(struct hlist_node *old,
   1.669 +                                     struct hlist_node *new)
   1.670 +{
   1.671 +    struct hlist_node *next = old->next;
   1.672 +
   1.673 +    new->next = next;
   1.674 +    new->pprev = old->pprev;
   1.675 +    smp_wmb();
   1.676 +    if (next)
   1.677 +        new->next->pprev = &new->next;
   1.678 +    *new->pprev = new;
   1.679 +    old->pprev = LIST_POISON2;
   1.680 +}
   1.681 +
   1.682  static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
   1.683  {
   1.684      struct hlist_node *first = h->first;
   1.685      n->next = first;
   1.686 -    if ( first )
   1.687 +    if (first)
   1.688          first->pprev = &n->next;
   1.689      h->first = n;
   1.690      n->pprev = &h->first;
   1.691  }
   1.692  
   1.693 +/**
   1.694 + * hlist_add_head_rcu
   1.695 + * @n: the element to add to the hash list.
   1.696 + * @h: the list to add to.
   1.697 + *
   1.698 + * Description:
   1.699 + * Adds the specified element to the specified hlist,
   1.700 + * while permitting racing traversals.
   1.701 + *
   1.702 + * The caller must take whatever precautions are necessary
   1.703 + * (such as holding appropriate locks) to avoid racing
   1.704 + * with another list-mutation primitive, such as hlist_add_head_rcu()
   1.705 + * or hlist_del_rcu(), running on this same list.
   1.706 + * However, it is perfectly legal to run concurrently with
   1.707 + * the _rcu list-traversal primitives, such as
   1.708 + * hlist_for_each_entry_rcu(), used to prevent memory-consistency
   1.709 + * problems on Alpha CPUs.  Regardless of the type of CPU, the
   1.710 + * list-traversal primitive must be guarded by rcu_read_lock().
   1.711 + */
   1.712 +static inline void hlist_add_head_rcu(struct hlist_node *n,
   1.713 +                                      struct hlist_head *h)
   1.714 +{
   1.715 +    struct hlist_node *first = h->first;
   1.716 +    n->next = first;
   1.717 +    n->pprev = &h->first;
   1.718 +    smp_wmb();
   1.719 +    if (first)
   1.720 +        first->pprev = &n->next;
   1.721 +    h->first = n;
   1.722 +}
   1.723 +
   1.724  /* next must be != NULL */
   1.725  static inline void hlist_add_before(struct hlist_node *n,
   1.726                      struct hlist_node *next)
   1.727 @@ -292,10 +771,67 @@ static inline void hlist_add_after(struc
   1.728      n->next = next;
   1.729      next->pprev = &n->next;
   1.730  
   1.731 -    if ( next->next )
   1.732 +    if(next->next)
   1.733          next->next->pprev  = &next->next;
   1.734  }
   1.735  
   1.736 +/**
   1.737 + * hlist_add_before_rcu
   1.738 + * @n: the new element to add to the hash list.
   1.739 + * @next: the existing element to add the new element before.
   1.740 + *
   1.741 + * Description:
   1.742 + * Adds the specified element to the specified hlist
   1.743 + * before the specified node while permitting racing traversals.
   1.744 + *
   1.745 + * The caller must take whatever precautions are necessary
   1.746 + * (such as holding appropriate locks) to avoid racing
   1.747 + * with another list-mutation primitive, such as hlist_add_head_rcu()
   1.748 + * or hlist_del_rcu(), running on this same list.
   1.749 + * However, it is perfectly legal to run concurrently with
   1.750 + * the _rcu list-traversal primitives, such as
   1.751 + * hlist_for_each_entry_rcu(), used to prevent memory-consistency
   1.752 + * problems on Alpha CPUs.
   1.753 + */
   1.754 +static inline void hlist_add_before_rcu(struct hlist_node *n,
   1.755 +                                        struct hlist_node *next)
   1.756 +{
   1.757 +    n->pprev = next->pprev;
   1.758 +    n->next = next;
   1.759 +    smp_wmb();
   1.760 +    next->pprev = &n->next;
   1.761 +    *(n->pprev) = n;
   1.762 +}
   1.763 +
   1.764 +/**
   1.765 + * hlist_add_after_rcu
   1.766 + * @prev: the existing element to add the new element after.
   1.767 + * @n: the new element to add to the hash list.
   1.768 + *
   1.769 + * Description:
   1.770 + * Adds the specified element to the specified hlist
   1.771 + * after the specified node while permitting racing traversals.
   1.772 + *
   1.773 + * The caller must take whatever precautions are necessary
   1.774 + * (such as holding appropriate locks) to avoid racing
   1.775 + * with another list-mutation primitive, such as hlist_add_head_rcu()
   1.776 + * or hlist_del_rcu(), running on this same list.
   1.777 + * However, it is perfectly legal to run concurrently with
   1.778 + * the _rcu list-traversal primitives, such as
   1.779 + * hlist_for_each_entry_rcu(), used to prevent memory-consistency
   1.780 + * problems on Alpha CPUs.
   1.781 + */
   1.782 +static inline void hlist_add_after_rcu(struct hlist_node *prev,
   1.783 +                                       struct hlist_node *n)
   1.784 +{
   1.785 +    n->next = prev->next;
   1.786 +    n->pprev = &prev->next;
   1.787 +    smp_wmb();
   1.788 +    prev->next = n;
   1.789 +    if (n->next)
   1.790 +        n->next->pprev = &n->next;
   1.791 +}
   1.792 +
   1.793  #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
   1.794  
   1.795  #define hlist_for_each(pos, head)                                       \
   1.796 @@ -303,8 +839,8 @@ static inline void hlist_add_after(struc
   1.797           pos = pos->next)
   1.798  
   1.799  #define hlist_for_each_safe(pos, n, head)                       \
   1.800 -    for ( pos = (head)->first; pos && ({ n = pos->next; 1; });  \
   1.801 -          pos = n )
   1.802 +    for (pos = (head)->first; pos && ({ n = pos->next; 1; });   \
   1.803 +         pos = n)
   1.804  
   1.805  /**
   1.806   * hlist_for_each_entry    - iterate over list of given type
   1.807 @@ -314,10 +850,10 @@ static inline void hlist_add_after(struc
   1.808   * @member:    the name of the hlist_node within the struct.
   1.809   */
   1.810  #define hlist_for_each_entry(tpos, pos, head, member)                   \
   1.811 -    for ( pos = (head)->first;                                          \
   1.812 -          pos && ({ prefetch(pos->next); 1;}) &&                        \
   1.813 -          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   1.814 -          pos = pos->next )
   1.815 +    for (pos = (head)->first;                                           \
   1.816 +         pos && ({ prefetch(pos->next); 1;}) &&                         \
   1.817 +         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
   1.818 +         pos = pos->next)
   1.819  
   1.820  /**
   1.821   * hlist_for_each_entry_continue - iterate over a hlist continuing
   1.822 @@ -327,10 +863,10 @@ static inline void hlist_add_after(struc
   1.823   * @member:    the name of the hlist_node within the struct.
   1.824   */
   1.825  #define hlist_for_each_entry_continue(tpos, pos, member)                \
   1.826 -    for ( pos = (pos)->next;                                            \
   1.827 -          pos && ({ prefetch(pos->next); 1;}) &&                        \
   1.828 -          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   1.829 -          pos = pos->next )
   1.830 +    for (pos = (pos)->next;                                             \
   1.831 +         pos && ({ prefetch(pos->next); 1;}) &&                         \
   1.832 +         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
   1.833 +         pos = pos->next)
   1.834  
   1.835  /**
   1.836   * hlist_for_each_entry_from - iterate over a hlist continuing from
   1.837 @@ -340,9 +876,9 @@ static inline void hlist_add_after(struc
   1.838   * @member:    the name of the hlist_node within the struct.
   1.839   */
   1.840  #define hlist_for_each_entry_from(tpos, pos, member)                    \
   1.841 -    for ( ; pos && ({ prefetch(pos->next); 1;}) &&                      \
   1.842 -          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   1.843 -          pos = pos->next )
   1.844 +    for (; pos && ({ prefetch(pos->next); 1;}) &&                       \
   1.845 +         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
   1.846 +         pos = pos->next)
   1.847  
   1.848  /**
   1.849   * hlist_for_each_entry_safe - iterate over list of given type safe
   1.850 @@ -354,10 +890,28 @@ static inline void hlist_add_after(struc
   1.851   * @member:    the name of the hlist_node within the struct.
   1.852   */
   1.853  #define hlist_for_each_entry_safe(tpos, pos, n, head, member)           \
   1.854 -    for ( pos = (head)->first;                                          \
   1.855 -          pos && ({ n = pos->next; 1; }) &&                             \
   1.856 +    for (pos = (head)->first;                                           \
   1.857 +         pos && ({ n = pos->next; 1; }) &&                              \
   1.858 +         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
   1.859 +         pos = n)
   1.860 +
   1.861 +
   1.862 +/**
   1.863 + * hlist_for_each_entry_rcu - iterate over rcu list of given type
   1.864 + * @tpos:   the type * to use as a loop cursor.
   1.865 + * @pos:    the &struct hlist_node to use as a loop cursor.
   1.866 + * @head:   the head for your list.
   1.867 + * @member: the name of the hlist_node within the struct.
   1.868 + *
   1.869 + * This list-traversal primitive may safely run concurrently with
   1.870 + * the _rcu list-mutation primitives such as hlist_add_head_rcu()
   1.871 + * as long as the traversal is guarded by rcu_read_lock().
   1.872 + */
   1.873 +#define hlist_for_each_entry_rcu(tpos, pos, head, member)               \
   1.874 +     for (pos = (head)->first;                                          \
   1.875 +          rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&       \
   1.876            ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   1.877 -          pos = n )
   1.878 +          pos = pos->next)
   1.879  
   1.880  #endif /* __XEN_LIST_H__ */
   1.881