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