palacios/include/palacios/vmm_list.h

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