gdunlap/sched-sim.hg

diff list.h @ 0:d27bb3c56e71

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