palacios/include/palacios/vmm_list.h

   1 #ifndef _VMM_LIST_H
   2 #define _VMM_LIST_H
   3
   4 #include <palacios/vmm_string.h>
   5
   6 #undef offsetof
   7 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
   8
   9
  10 #define container_of(ptr, type, member) ({                      \
  11         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  12         (type *)( (char *)__mptr - offsetof(type,member) );})
  13
  14
  15 static inline void prefetch(const void *x) {;}
  16
  17 /*
  18  * These are non-NULL pointers that will result in page faults
  19  * under normal circumstances, used to verify that nobody uses
  20  * non-initialized list entries.
  21  */
  22 #define LIST_POISON1  ((void *) 0x00100100)
  23 #define LIST_POISON2  ((void *) 0x00200200)
  24
  25 /*
  26  * Simple doubly linked list implementation.
  27  *
  28  * Some of the internal functions ("__xxx") are useful when
  29  * manipulating whole lists rather than single entries, as
  30  * sometimes we already know the next/prev entries and we can
  31  * generate better code by using them directly rather than
  32  * using the generic single-entry routines.
  33  */
  34
  35 struct list_head {
  36         struct list_head *next, *prev;
  37 };
  38
  39 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  40
  41 #define LIST_HEAD(name) \
  42         struct list_head name = LIST_HEAD_INIT(name)
  43
  44 static inline void INIT_LIST_HEAD(struct list_head *list)
  45 {
  46         list->next = list;
  47         list->prev = list;
  48 }
  49
  50 /*
  51  * Insert a new entry between two known consecutive entries.
  52  *
  53  * This is only for internal list manipulation where we know
  54  * the prev/next entries already!
  55  */
  56 static inline void __list_add(struct list_head *new,
  57                               struct list_head *prev,
  58                               struct list_head *next)
  59 {
  60         next->prev = new;
  61         new->next = next;
  62         new->prev = prev;
  63         prev->next = new;
  64 }
  65
  66 /**
  67  * list_add - add a new entry
  68  * @new: new entry to be added
  69  * @head: list head to add it after
  70  *
  71  * Insert a new entry after the specified head.
  72  * This is good for implementing stacks.
  73  */
  74 static inline void list_add(struct list_head *new, struct list_head *head)
  75 {
  76         __list_add(new, head, head->next);
  77 }
  78
  79 /**
  80  * list_add_tail - add a new entry
  81  * @new: new entry to be added
  82  * @head: list head to add it before
  83  *
  84  * Insert a new entry before the specified head.
  85  * This is useful for implementing queues.
  86  */
  87 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  88 {
  89         __list_add(new, head->prev, head);
  90 }
  91
  92 /*
  93  * Delete a list entry by making the prev/next entries
  94  * point to each other.
  95  *
  96  * This is only for internal list manipulation where we know
  97  * the prev/next entries already!
  98  */
  99 static inline void __list_del(struct list_head * prev, struct list_head * next)
 100 {
 101         next->prev = prev;
 102         prev->next = next;
 103 }
 104
 105 /**
 106  * list_del - deletes entry from list.
 107  * @entry: the element to delete from the list.
 108  * Note: list_empty on entry does not return true after this, the entry is
 109  * in an undefined state.
 110  */
 111 static inline void list_del(struct list_head *entry)
 112 {
 113         __list_del(entry->prev, entry->next);
 114         entry->next = LIST_POISON1;
 115         entry->prev = LIST_POISON2;
 116 }
 117
 118 /**
 119  * list_del_init - deletes entry from list and reinitialize it.
 120  * @entry: the element to delete from the list.
 121  */
 122 static inline void list_del_init(struct list_head *entry)
 123 {
 124         __list_del(entry->prev, entry->next);
 125         INIT_LIST_HEAD(entry);
 126 }
 127
 128 /**
 129  * list_move - delete from one list and add as another's head
 130  * @list: the entry to move
 131  * @head: the head that will precede our entry
 132  */
 133 static inline void list_move(struct list_head *list, struct list_head *head)
 134 {
 135         __list_del(list->prev, list->next);
 136         list_add(list, head);
 137 }
 138
 139 /**
 140  * list_move_tail - delete from one list and add as another's tail
 141  * @list: the entry to move
 142  * @head: the head that will follow our entry
 143  */
 144 static inline void list_move_tail(struct list_head *list,
 145                                   struct list_head *head)
 146 {
 147         __list_del(list->prev, list->next);
 148         list_add_tail(list, head);
 149 }
 150
 151 /**
 152  * list_empty - tests whether a list is empty
 153  * @head: the list to test.
 154  */
 155 static inline int list_empty(const struct list_head *head)
 156 {
 157         return head->next == head;
 158 }
 159
 160 /**
 161  * list_empty_careful - tests whether a list is
 162  * empty _and_ checks that no other CPU might be
 163  * in the process of still modifying either member
 164  *
 165  * NOTE: using list_empty_careful() without synchronization
 166  * can only be safe if the only activity that can happen
 167  * to the list entry is list_del_init(). Eg. it cannot be used
 168  * if another CPU could re-list_add() it.
 169  *
 170  * @head: the list to test.
 171  */
 172 static inline int list_empty_careful(const struct list_head *head)
 173 {
 174         struct list_head *next = head->next;
 175         return (next == head) && (next == head->prev);
 176 }
 177
 178 static inline void __list_splice(struct list_head *list,
 179                                  struct list_head *head)
 180 {
 181         struct list_head *first = list->next;
 182         struct list_head *last = list->prev;
 183         struct list_head *at = head->next;
 184
 185         first->prev = head;
 186         head->next = first;
 187
 188         last->next = at;
 189         at->prev = last;
 190 }
 191
 192 /**
 193  * list_splice - join two lists
 194  * @list: the new list to add.
 195  * @head: the place to add it in the first list.
 196  */
 197 static inline void list_splice(struct list_head *list, struct list_head *head)
 198 {
 199         if (!list_empty(list))
 200                 __list_splice(list, head);
 201 }
 202
 203 /**
 204  * list_splice_init - join two lists and reinitialise the emptied list.
 205  * @list: the new list to add.
 206  * @head: the place to add it in the first list.
 207  *
 208  * The list at @list is reinitialised
 209  */
 210 static inline void list_splice_init(struct list_head *list,
 211                                     struct list_head *head)
 212 {
 213         if (!list_empty(list)) {
 214                 __list_splice(list, head);
 215                 INIT_LIST_HEAD(list);
 216         }
 217 }
 218
 219 /**
 220  * list_entry - get the struct for this entry
 221  * @ptr:        the &struct list_head pointer.
 222  * @type:       the type of the struct this is embedded in.
 223  * @member:     the name of the list_struct within the struct.
 224  */
 225 #define list_entry(ptr, type, member) \
 226         container_of(ptr, type, member)
 227
 228 /**
 229  * list_for_each        -       iterate over a list
 230  * @pos:        the &struct list_head to use as a loop counter.
 231  * @head:       the head for your list.
 232  */
 233 #define list_for_each(pos, head) \
 234         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 235                 pos = pos->next)
 236
 237 /**
 238  * __list_for_each      -       iterate over a list
 239  * @pos:        the &struct list_head to use as a loop counter.
 240  * @head:       the head for your list.
 241  *
 242  * This variant differs from list_for_each() in that it's the
 243  * simplest possible list iteration code, no prefetching is done.
 244  * Use this for code that knows the list to be very short (empty
 245  * or 1 entry) most of the time.
 246  */
 247 #define __list_for_each(pos, head) \
 248         for (pos = (head)->next; pos != (head); pos = pos->next)
 249
 250 /**
 251  * list_for_each_prev   -       iterate over a list backwards
 252  * @pos:        the &struct list_head to use as a loop counter.
 253  * @head:       the head for your list.
 254  */
 255 #define list_for_each_prev(pos, head) \
 256         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
 257                 pos = pos->prev)
 258
 259 /**
 260  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 261  * @pos:        the &struct list_head to use as a loop counter.
 262  * @n:          another &struct list_head to use as temporary storage
 263  * @head:       the head for your list.
 264  */
 265 #define list_for_each_safe(pos, n, head) \
 266         for (pos = (head)->next, n = pos->next; pos != (head); \
 267                 pos = n, n = pos->next)
 268
 269 /**
 270  * list_for_each_entry  -       iterate over list of given type
 271  * @pos:        the type * to use as a loop counter.
 272  * @head:       the head for your list.
 273  * @member:     the name of the list_struct within the struct.
 274  */
 275 #define list_for_each_entry(pos, head, member)                          \
 276         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 277              prefetch(pos->member.next), &pos->member != (head);        \
 278              pos = list_entry(pos->member.next, typeof(*pos), member))
 279
 280 /**
 281  * list_for_each_entry_reverse - iterate backwards over list of given type.
 282  * @pos:        the type * to use as a loop counter.
 283  * @head:       the head for your list.
 284  * @member:     the name of the list_struct within the struct.
 285  */
 286 #define list_for_each_entry_reverse(pos, head, member)                  \
 287         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 288              prefetch(pos->member.prev), &pos->member != (head);        \
 289              pos = list_entry(pos->member.prev, typeof(*pos), member))
 290
 291 /**
 292  * list_prepare_entry - prepare a pos entry for use as a start point in
 293  *                      list_for_each_entry_continue
 294  * @pos:        the type * to use as a start point
 295  * @head:       the head of the list
 296  * @member:     the name of the list_struct within the struct.
 297  */
 298 #define list_prepare_entry(pos, head, member) \
 299         ((pos) ? : list_entry(head, typeof(*pos), member))
 300
 301 /**
 302  * list_for_each_entry_continue -       iterate over list of given type
 303  *                      continuing after existing point
 304  * @pos:        the type * to use as a loop counter.
 305  * @head:       the head for your list.
 306  * @member:     the name of the list_struct within the struct.
 307  */
 308 #define list_for_each_entry_continue(pos, head, member)                 \
 309         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 310              prefetch(pos->member.next), &pos->member != (head);        \
 311              pos = list_entry(pos->member.next, typeof(*pos), member))
 312
 313 /**
 314  * list_for_each_entry_from -   iterate over list of given type
 315  *                      continuing from existing point
 316  * @pos:        the type * to use as a loop counter.
 317  * @head:       the head for your list.
 318  * @member:     the name of the list_struct within the struct.
 319  */
 320 #define list_for_each_entry_from(pos, head, member)                     \
 321         for (; prefetch(pos->member.next), &pos->member != (head);      \
 322              pos = list_entry(pos->member.next, typeof(*pos), member))
 323
 324 /**
 325  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 326  * @pos:        the type * to use as a loop counter.
 327  * @n:          another type * to use as temporary storage
 328  * @head:       the head for your list.
 329  * @member:     the name of the list_struct within the struct.
 330  */
 331 #define list_for_each_entry_safe(pos, n, head, member)                  \
 332         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 333                 n = list_entry(pos->member.next, typeof(*pos), member); \
 334              &pos->member != (head);                                    \
 335              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 336
 337 /**
 338  * list_for_each_entry_safe_continue -  iterate over list of given type
 339  *                      continuing after existing point safe against removal of list entry
 340  * @pos:        the type * to use as a loop counter.
 341  * @n:          another type * to use as temporary storage
 342  * @head:       the head for your list.
 343  * @member:     the name of the list_struct within the struct.
 344  */
 345 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 346         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
 347                 n = list_entry(pos->member.next, typeof(*pos), member);         \
 348              &pos->member != (head);                                            \
 349              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 350
 351 /**
 352  * list_for_each_entry_safe_from - iterate over list of given type
 353  *                      from existing point safe against removal of list entry
 354  * @pos:        the type * to use as a loop counter.
 355  * @n:          another type * to use as temporary storage
 356  * @head:       the head for your list.
 357  * @member:     the name of the list_struct within the struct.
 358  */
 359 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 360         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
 361              &pos->member != (head);                                            \
 362              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 363
 364 /**
 365  * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
 366  *                                    removal of list entry
 367  * @pos:        the type * to use as a loop counter.
 368  * @n:          another type * to use as temporary storage
 369  * @head:       the head for your list.
 370  * @member:     the name of the list_struct within the struct.
 371  */
 372 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 373         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 374                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 375              &pos->member != (head);                                    \
 376              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 377
 378 /*
 379  * Double linked lists with a single pointer list head.
 380  * Mostly useful for hash tables where the two pointer list head is
 381  * too wasteful.
 382  * You lose the ability to access the tail in O(1).
 383  */
 384
 385 struct hlist_head {
 386         struct hlist_node *first;
 387 };
 388
 389 struct hlist_node {
 390         struct hlist_node *next, **pprev;
 391 };
 392
 393 #define HLIST_HEAD_INIT { .first = NULL }
 394 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 395 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 396 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 397 {
 398         h->next = NULL;
 399         h->pprev = NULL;
 400 }
 401
 402 static inline int hlist_unhashed(const struct hlist_node *h)
 403 {
 404         return !h->pprev;
 405 }
 406
 407 static inline int hlist_empty(const struct hlist_head *h)
 408 {
 409         return !h->first;
 410 }
 411
 412 static inline void __hlist_del(struct hlist_node *n)
 413 {
 414         struct hlist_node *next = n->next;
 415         struct hlist_node **pprev = n->pprev;
 416         *pprev = next;
 417         if (next)
 418                 next->pprev = pprev;
 419 }
 420
 421 static inline void hlist_del(struct hlist_node *n)
 422 {
 423         __hlist_del(n);
 424         n->next = LIST_POISON1;
 425         n->pprev = LIST_POISON2;
 426 }
 427
 428 static inline void hlist_del_init(struct hlist_node *n)
 429 {
 430         if (!hlist_unhashed(n)) {
 431                 __hlist_del(n);
 432                 INIT_HLIST_NODE(n);
 433         }
 434 }
 435
 436 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 437 {
 438         struct hlist_node *first = h->first;
 439         n->next = first;
 440         if (first)
 441                 first->pprev = &n->next;
 442         h->first = n;
 443         n->pprev = &h->first;
 444 }
 445
 446 /* next must be != NULL */
 447 static inline void hlist_add_before(struct hlist_node *n,
 448                                         struct hlist_node *next)
 449 {
 450         n->pprev = next->pprev;
 451         n->next = next;
 452         next->pprev = &n->next;
 453         *(n->pprev) = n;
 454 }
 455
 456 static inline void hlist_add_after(struct hlist_node *n,
 457                                         struct hlist_node *next)
 458 {
 459         next->next = n->next;
 460         n->next = next;
 461         next->pprev = &n->next;
 462
 463         if(next->next)
 464                 next->next->pprev  = &next->next;
 465 }
 466
 467 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 468
 469 #define hlist_for_each(pos, head) \
 470         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 471              pos = pos->next)
 472
 473 #define hlist_for_each_safe(pos, n, head) \
 474         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 475              pos = n)
 476
 477 /**
 478  * hlist_for_each_entry - iterate over list of given type
 479  * @tpos:       the type * to use as a loop counter.
 480  * @pos:        the &struct hlist_node to use as a loop counter.
 481  * @head:       the head for your list.
 482  * @member:     the name of the hlist_node within the struct.
 483  */
 484 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 485         for (pos = (head)->first;                                        \
 486              pos && ({ prefetch(pos->next); 1;}) &&                      \
 487                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 488              pos = pos->next)
 489
 490 /**
 491  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
 492  * @tpos:       the type * to use as a loop counter.
 493  * @pos:        the &struct hlist_node to use as a loop counter.
 494  * @member:     the name of the hlist_node within the struct.
 495  */
 496 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 497         for (pos = (pos)->next;                                          \
 498              pos && ({ prefetch(pos->next); 1;}) &&                      \
 499                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 500              pos = pos->next)
 501
 502 /**
 503  * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
 504  * @tpos:       the type * to use as a loop counter.
 505  * @pos:        the &struct hlist_node to use as a loop counter.
 506  * @member:     the name of the hlist_node within the struct.
 507  */
 508 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 509         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 510                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 511              pos = pos->next)
 512
 513 /**
 514  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 515  * @tpos:       the type * to use as a loop counter.
 516  * @pos:        the &struct hlist_node to use as a loop counter.
 517  * @n:          another &struct hlist_node to use as temporary storage
 518  * @head:       the head for your list.
 519  * @member:     the name of the hlist_node within the struct.
 520  */
 521 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 522         for (pos = (head)->first;                                        \
 523              pos && ({ n = pos->next; 1; }) &&                           \
 524                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 525              pos = n)
 526
 527
 528 #endif