Palacios Public Git Repository

To checkout Palacios execute

  git clone http://v3vee.org/palacios/palacios.web/palacios.git
This will give you the master branch. You probably want the devel branch or one of the release branches. To switch to the devel branch, simply execute
  cd palacios
  git checkout --track -b devel origin/devel
The other branches are similar.


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