gdunlap/sched-sim.hg

view list.h @ 17:03ad237559b4

Fix-up options, scheduler list
author George Dunlap <george.dunlap@eu.citrix.com>
date Fri Jul 16 11:58:53 2010 +0100 (2010-07-16)
parents d27bb3c56e71
children
line source
1 /******************************************************************************
2 * list.h
3 *
4 * Useful linked-list definitions taken from the Linux kernel (2.6.18).
5 */
7 #ifndef __XEN_LIST_H__
8 #define __XEN_LIST_H__
10 #if __GNUC__ > 3
11 #define offsetof(a,b) __builtin_offsetof(a,b)
12 #else
13 #define offsetof(a,b) ((unsigned long)&(((a *)0)->b))
14 #endif
16 /**
17 * container_of - cast a member of a structure out to the containing structure
18 *
19 * @ptr: the pointer to the member.
20 * @type: the type of the container struct this is embedded in.
21 * @member: the name of the member within the struct.
22 *
23 */
24 #define container_of(ptr, type, member) ({ \
25 typeof( ((type *)0)->member ) *__mptr = (ptr); \
26 (type *)( (char *)__mptr - offsetof(type,member) );})
28 #define prefetch(_x) (_x)
30 /* These are non-NULL pointers that will result in page faults
31 * under normal circumstances, used to verify that nobody uses
32 * non-initialized list entries.
33 */
34 #define LIST_POISON1 ((void *) 0x00100100)
35 #define LIST_POISON2 ((void *) 0x00200200)
37 /*
38 * Simple doubly linked list implementation.
39 *
40 * Some of the internal functions ("__xxx") are useful when
41 * manipulating whole lists rather than single entries, as
42 * sometimes we already know the next/prev entries and we can
43 * generate better code by using them directly rather than
44 * using the generic single-entry routines.
45 */
47 struct list_head {
48 struct list_head *next, *prev;
49 };
51 #define LIST_HEAD_INIT(name) { &(name), &(name) }
53 #define LIST_HEAD(name) \
54 struct list_head name = LIST_HEAD_INIT(name)
56 static inline void INIT_LIST_HEAD(struct list_head *list)
57 {
58 list->next = list;
59 list->prev = list;
60 }
62 /*
63 * Insert a new entry between two known consecutive entries.
64 *
65 * This is only for internal list manipulation where we know
66 * the prev/next entries already!
67 */
68 static inline void __list_add(struct list_head *new,
69 struct list_head *prev,
70 struct list_head *next)
71 {
72 next->prev = new;
73 new->next = next;
74 new->prev = prev;
75 prev->next = new;
76 }
78 /**
79 * list_add - add a new entry
80 * @new: new entry to be added
81 * @head: list head to add it after
82 *
83 * Insert a new entry after the specified head.
84 * This is good for implementing stacks.
85 */
86 static inline void list_add(struct list_head *new, struct list_head *head)
87 {
88 __list_add(new, head, head->next);
89 }
91 /**
92 * list_add_tail - add a new entry
93 * @new: new entry to be added
94 * @head: list head to add it before
95 *
96 * Insert a new entry before the specified head.
97 * This is useful for implementing queues.
98 */
99 static inline void list_add_tail(struct list_head *new, struct list_head *head)
100 {
101 __list_add(new, head->prev, head);
102 }
104 /*
105 * Insert a new entry between two known consecutive entries.
106 *
107 * This is only for internal list manipulation where we know
108 * the prev/next entries already!
109 */
110 static inline void __list_add_rcu(struct list_head *new,
111 struct list_head *prev,
112 struct list_head *next)
113 {
114 new->next = next;
115 new->prev = prev;
116 next->prev = new;
117 prev->next = new;
118 }
120 /**
121 * list_add_rcu - add a new entry to rcu-protected list
122 * @new: new entry to be added
123 * @head: list head to add it after
124 *
125 * Insert a new entry after the specified head.
126 * This is good for implementing stacks.
127 *
128 * The caller must take whatever precautions are necessary
129 * (such as holding appropriate locks) to avoid racing
130 * with another list-mutation primitive, such as list_add_rcu()
131 * or list_del_rcu(), running on this same list.
132 * However, it is perfectly legal to run concurrently with
133 * the _rcu list-traversal primitives, such as
134 * list_for_each_entry_rcu().
135 */
136 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
137 {
138 __list_add_rcu(new, head, head->next);
139 }
141 /**
142 * list_add_tail_rcu - add a new entry to rcu-protected list
143 * @new: new entry to be added
144 * @head: list head to add it before
145 *
146 * Insert a new entry before the specified head.
147 * This is useful for implementing queues.
148 *
149 * The caller must take whatever precautions are necessary
150 * (such as holding appropriate locks) to avoid racing
151 * with another list-mutation primitive, such as list_add_tail_rcu()
152 * or list_del_rcu(), running on this same list.
153 * However, it is perfectly legal to run concurrently with
154 * the _rcu list-traversal primitives, such as
155 * list_for_each_entry_rcu().
156 */
157 static inline void list_add_tail_rcu(struct list_head *new,
158 struct list_head *head)
159 {
160 __list_add_rcu(new, head->prev, head);
161 }
163 /*
164 * Delete a list entry by making the prev/next entries
165 * point to each other.
166 *
167 * This is only for internal list manipulation where we know
168 * the prev/next entries already!
169 */
170 static inline void __list_del(struct list_head *prev,
171 struct list_head *next)
172 {
173 next->prev = prev;
174 prev->next = next;
175 }
177 /**
178 * list_del - deletes entry from list.
179 * @entry: the element to delete from the list.
180 * Note: list_empty on entry does not return true after this, the entry is
181 * in an undefined state.
182 */
183 static inline void list_del(struct list_head *entry)
184 {
185 ASSERT(entry->next->prev == entry);
186 ASSERT(entry->prev->next == entry);
187 __list_del(entry->prev, entry->next);
188 entry->next = LIST_POISON1;
189 entry->prev = LIST_POISON2;
190 }
192 /**
193 * list_del_rcu - deletes entry from list without re-initialization
194 * @entry: the element to delete from the list.
195 *
196 * Note: list_empty on entry does not return true after this,
197 * the entry is in an undefined state. It is useful for RCU based
198 * lockfree traversal.
199 *
200 * In particular, it means that we can not poison the forward
201 * pointers that may still be used for walking the list.
202 *
203 * The caller must take whatever precautions are necessary
204 * (such as holding appropriate locks) to avoid racing
205 * with another list-mutation primitive, such as list_del_rcu()
206 * or list_add_rcu(), running on this same list.
207 * However, it is perfectly legal to run concurrently with
208 * the _rcu list-traversal primitives, such as
209 * list_for_each_entry_rcu().
210 *
211 * Note that the caller is not permitted to immediately free
212 * the newly deleted entry. Instead, either synchronize_rcu()
213 * or call_rcu() must be used to defer freeing until an RCU
214 * grace period has elapsed.
215 */
216 static inline void list_del_rcu(struct list_head *entry)
217 {
218 __list_del(entry->prev, entry->next);
219 entry->prev = LIST_POISON2;
220 }
222 /**
223 * list_replace - replace old entry by new one
224 * @old : the element to be replaced
225 * @new : the new element to insert
226 * Note: if 'old' was empty, it will be overwritten.
227 */
228 static inline void list_replace(struct list_head *old,
229 struct list_head *new)
230 {
231 new->next = old->next;
232 new->next->prev = new;
233 new->prev = old->prev;
234 new->prev->next = new;
235 }
237 static inline void list_replace_init(struct list_head *old,
238 struct list_head *new)
239 {
240 list_replace(old, new);
241 INIT_LIST_HEAD(old);
242 }
244 /*
245 * list_replace_rcu - replace old entry by new one
246 * @old : the element to be replaced
247 * @new : the new element to insert
248 *
249 * The old entry will be replaced with the new entry atomically.
250 * Note: 'old' should not be empty.
251 */
252 static inline void list_replace_rcu(struct list_head *old,
253 struct list_head *new)
254 {
255 new->next = old->next;
256 new->prev = old->prev;
257 new->next->prev = new;
258 new->prev->next = new;
259 old->prev = LIST_POISON2;
260 }
262 /**
263 * list_del_init - deletes entry from list and reinitialize it.
264 * @entry: the element to delete from the list.
265 */
266 static inline void list_del_init(struct list_head *entry)
267 {
268 __list_del(entry->prev, entry->next);
269 INIT_LIST_HEAD(entry);
270 }
272 /**
273 * list_move - delete from one list and add as another's head
274 * @list: the entry to move
275 * @head: the head that will precede our entry
276 */
277 static inline void list_move(struct list_head *list, struct list_head *head)
278 {
279 __list_del(list->prev, list->next);
280 list_add(list, head);
281 }
283 /**
284 * list_move_tail - delete from one list and add as another's tail
285 * @list: the entry to move
286 * @head: the head that will follow our entry
287 */
288 static inline void list_move_tail(struct list_head *list,
289 struct list_head *head)
290 {
291 __list_del(list->prev, list->next);
292 list_add_tail(list, head);
293 }
295 /**
296 * list_is_last - tests whether @list is the last entry in list @head
297 * @list: the entry to test
298 * @head: the head of the list
299 */
300 static inline int list_is_last(const struct list_head *list,
301 const struct list_head *head)
302 {
303 return list->next == head;
304 }
306 /**
307 * list_empty - tests whether a list is empty
308 * @head: the list to test.
309 */
310 static inline int list_empty(const struct list_head *head)
311 {
312 return head->next == head;
313 }
315 /**
316 * list_empty_careful - tests whether a list is empty and not being modified
317 * @head: the list to test
318 *
319 * Description:
320 * tests whether a list is empty _and_ checks that no other CPU might be
321 * in the process of modifying either member (next or prev)
322 *
323 * NOTE: using list_empty_careful() without synchronization
324 * can only be safe if the only activity that can happen
325 * to the list entry is list_del_init(). Eg. it cannot be used
326 * if another CPU could re-list_add() it.
327 */
328 static inline int list_empty_careful(const struct list_head *head)
329 {
330 struct list_head *next = head->next;
331 return (next == head) && (next == head->prev);
332 }
334 static inline void __list_splice(struct list_head *list,
335 struct list_head *head)
336 {
337 struct list_head *first = list->next;
338 struct list_head *last = list->prev;
339 struct list_head *at = head->next;
341 first->prev = head;
342 head->next = first;
344 last->next = at;
345 at->prev = last;
346 }
348 /**
349 * list_splice - join two lists
350 * @list: the new list to add.
351 * @head: the place to add it in the first list.
352 */
353 static inline void list_splice(struct list_head *list, struct list_head *head)
354 {
355 if (!list_empty(list))
356 __list_splice(list, head);
357 }
359 /**
360 * list_splice_init - join two lists and reinitialise the emptied list.
361 * @list: the new list to add.
362 * @head: the place to add it in the first list.
363 *
364 * The list at @list is reinitialised
365 */
366 static inline void list_splice_init(struct list_head *list,
367 struct list_head *head)
368 {
369 if (!list_empty(list)) {
370 __list_splice(list, head);
371 INIT_LIST_HEAD(list);
372 }
373 }
375 /**
376 * list_entry - get the struct for this entry
377 * @ptr: the &struct list_head pointer.
378 * @type: the type of the struct this is embedded in.
379 * @member: the name of the list_struct within the struct.
380 */
381 #define list_entry(ptr, type, member) \
382 container_of(ptr, type, member)
384 /**
385 * list_for_each - iterate over a list
386 * @pos: the &struct list_head to use as a loop cursor.
387 * @head: the head for your list.
388 */
389 #define list_for_each(pos, head) \
390 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
391 pos = pos->next)
393 /**
394 * __list_for_each - iterate over a list
395 * @pos: the &struct list_head to use as a loop cursor.
396 * @head: the head for your list.
397 *
398 * This variant differs from list_for_each() in that it's the
399 * simplest possible list iteration code, no prefetching is done.
400 * Use this for code that knows the list to be very short (empty
401 * or 1 entry) most of the time.
402 */
403 #define __list_for_each(pos, head) \
404 for (pos = (head)->next; pos != (head); pos = pos->next)
406 /**
407 * list_for_each_prev - iterate over a list backwards
408 * @pos: the &struct list_head to use as a loop cursor.
409 * @head: the head for your list.
410 */
411 #define list_for_each_prev(pos, head) \
412 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
413 pos = pos->prev)
415 /**
416 * list_for_each_safe - iterate over a list safe against removal of list entry
417 * @pos: the &struct list_head to use as a loop cursor.
418 * @n: another &struct list_head to use as temporary storage
419 * @head: the head for your list.
420 */
421 #define list_for_each_safe(pos, n, head) \
422 for (pos = (head)->next, n = pos->next; pos != (head); \
423 pos = n, n = pos->next)
425 /**
426 * list_for_each_backwards_safe - iterate backwards over a list safe
427 * against removal of list entry
428 * @pos: the &struct list_head to use as a loop counter.
429 * @n: another &struct list_head to use as temporary storage
430 * @head: the head for your list.
431 */
432 #define list_for_each_backwards_safe(pos, n, head) \
433 for ( pos = (head)->prev, n = pos->prev; pos != (head); \
434 pos = n, n = pos->prev )
436 /**
437 * list_for_each_entry - iterate over list of given type
438 * @pos: the type * to use as a loop cursor.
439 * @head: the head for your list.
440 * @member: the name of the list_struct within the struct.
441 */
442 #define list_for_each_entry(pos, head, member) \
443 for (pos = list_entry((head)->next, typeof(*pos), member); \
444 prefetch(pos->member.next), &pos->member != (head); \
445 pos = list_entry(pos->member.next, typeof(*pos), member))
447 /**
448 * list_for_each_entry_reverse - iterate backwards over list of given type.
449 * @pos: the type * to use as a loop cursor.
450 * @head: the head for your list.
451 * @member: the name of the list_struct within the struct.
452 */
453 #define list_for_each_entry_reverse(pos, head, member) \
454 for (pos = list_entry((head)->prev, typeof(*pos), member); \
455 prefetch(pos->member.prev), &pos->member != (head); \
456 pos = list_entry(pos->member.prev, typeof(*pos), member))
458 /**
459 * list_prepare_entry - prepare a pos entry for use in
460 * list_for_each_entry_continue
461 * @pos: the type * to use as a start point
462 * @head: the head of the list
463 * @member: the name of the list_struct within the struct.
464 *
465 * Prepares a pos entry for use as a start point in
466 * list_for_each_entry_continue.
467 */
468 #define list_prepare_entry(pos, head, member) \
469 ((pos) ? : list_entry(head, typeof(*pos), member))
471 /**
472 * list_for_each_entry_continue - continue iteration over list of given type
473 * @pos: the type * to use as a loop cursor.
474 * @head: the head for your list.
475 * @member: the name of the list_struct within the struct.
476 *
477 * Continue to iterate over list of given type, continuing after
478 * the current position.
479 */
480 #define list_for_each_entry_continue(pos, head, member) \
481 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
482 prefetch(pos->member.next), &pos->member != (head); \
483 pos = list_entry(pos->member.next, typeof(*pos), member))
485 /**
486 * list_for_each_entry_from - iterate over list of given type from the
487 * current point
488 * @pos: the type * to use as a loop cursor.
489 * @head: the head for your list.
490 * @member: the name of the list_struct within the struct.
491 *
492 * Iterate over list of given type, continuing from current position.
493 */
494 #define list_for_each_entry_from(pos, head, member) \
495 for (; prefetch(pos->member.next), &pos->member != (head); \
496 pos = list_entry(pos->member.next, typeof(*pos), member))
498 /**
499 * list_for_each_entry_safe - iterate over list of given type safe
500 * against removal of list entry
501 * @pos: the type * to use as a loop cursor.
502 * @n: another type * to use as temporary storage
503 * @head: the head for your list.
504 * @member: the name of the list_struct within the struct.
505 */
506 #define list_for_each_entry_safe(pos, n, head, member) \
507 for (pos = list_entry((head)->next, typeof(*pos), member), \
508 n = list_entry(pos->member.next, typeof(*pos), member); \
509 &pos->member != (head); \
510 pos = n, n = list_entry(n->member.next, typeof(*n), member))
512 /**
513 * list_for_each_entry_safe_continue
514 * @pos: the type * to use as a loop cursor.
515 * @n: another type * to use as temporary storage
516 * @head: the head for your list.
517 * @member: the name of the list_struct within the struct.
518 *
519 * Iterate over list of given type, continuing after current point,
520 * safe against removal of list entry.
521 */
522 #define list_for_each_entry_safe_continue(pos, n, head, member) \
523 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
524 n = list_entry(pos->member.next, typeof(*pos), member); \
525 &pos->member != (head); \
526 pos = n, n = list_entry(n->member.next, typeof(*n), member))
528 /**
529 * list_for_each_entry_safe_from
530 * @pos: the type * to use as a loop cursor.
531 * @n: another type * to use as temporary storage
532 * @head: the head for your list.
533 * @member: the name of the list_struct within the struct.
534 *
535 * Iterate over list of given type from current point, safe against
536 * removal of list entry.
537 */
538 #define list_for_each_entry_safe_from(pos, n, head, member) \
539 for (n = list_entry(pos->member.next, typeof(*pos), member); \
540 &pos->member != (head); \
541 pos = n, n = list_entry(n->member.next, typeof(*n), member))
543 /**
544 * list_for_each_entry_safe_reverse
545 * @pos: the type * to use as a loop cursor.
546 * @n: another type * to use as temporary storage
547 * @head: the head for your list.
548 * @member: the name of the list_struct within the struct.
549 *
550 * Iterate backwards over list of given type, safe against removal
551 * of list entry.
552 */
553 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
554 for (pos = list_entry((head)->prev, typeof(*pos), member), \
555 n = list_entry(pos->member.prev, typeof(*pos), member); \
556 &pos->member != (head); \
557 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
559 /**
560 * list_for_each_rcu - iterate over an rcu-protected list
561 * @pos: the &struct list_head to use as a loop cursor.
562 * @head: the head for your list.
563 *
564 * This list-traversal primitive may safely run concurrently with
565 * the _rcu list-mutation primitives such as list_add_rcu()
566 * as long as the traversal is guarded by rcu_read_lock().
567 */
568 #define list_for_each_rcu(pos, head) \
569 for (pos = (head)->next; \
570 prefetch(rcu_dereference(pos)->next), pos != (head); \
571 pos = pos->next)
573 #define __list_for_each_rcu(pos, head) \
574 for (pos = (head)->next; \
575 rcu_dereference(pos) != (head); \
576 pos = pos->next)
578 /**
579 * list_for_each_safe_rcu
580 * @pos: the &struct list_head to use as a loop cursor.
581 * @n: another &struct list_head to use as temporary storage
582 * @head: the head for your list.
583 *
584 * Iterate over an rcu-protected list, safe against removal of list entry.
585 *
586 * This list-traversal primitive may safely run concurrently with
587 * the _rcu list-mutation primitives such as list_add_rcu()
588 * as long as the traversal is guarded by rcu_read_lock().
589 */
590 #define list_for_each_safe_rcu(pos, n, head) \
591 for (pos = (head)->next; \
592 n = rcu_dereference(pos)->next, pos != (head); \
593 pos = n)
595 /**
596 * list_for_each_entry_rcu - iterate over rcu list of given type
597 * @pos: the type * to use as a loop cursor.
598 * @head: the head for your list.
599 * @member: the name of the list_struct within the struct.
600 *
601 * This list-traversal primitive may safely run concurrently with
602 * the _rcu list-mutation primitives such as list_add_rcu()
603 * as long as the traversal is guarded by rcu_read_lock().
604 */
605 #define list_for_each_entry_rcu(pos, head, member) \
606 for (pos = list_entry((head)->next, typeof(*pos), member); \
607 prefetch(rcu_dereference(pos)->member.next), \
608 &pos->member != (head); \
609 pos = list_entry(pos->member.next, typeof(*pos), member))
611 /**
612 * list_for_each_continue_rcu
613 * @pos: the &struct list_head to use as a loop cursor.
614 * @head: the head for your list.
615 *
616 * Iterate over an rcu-protected list, continuing after current point.
617 *
618 * This list-traversal primitive may safely run concurrently with
619 * the _rcu list-mutation primitives such as list_add_rcu()
620 * as long as the traversal is guarded by rcu_read_lock().
621 */
622 #define list_for_each_continue_rcu(pos, head) \
623 for ((pos) = (pos)->next; \
624 prefetch(rcu_dereference((pos))->next), (pos) != (head); \
625 (pos) = (pos)->next)
627 /*
628 * Double linked lists with a single pointer list head.
629 * Mostly useful for hash tables where the two pointer list head is
630 * too wasteful.
631 * You lose the ability to access the tail in O(1).
632 */
634 struct hlist_head {
635 struct hlist_node *first;
636 };
638 struct hlist_node {
639 struct hlist_node *next, **pprev;
640 };
642 #define HLIST_HEAD_INIT { .first = NULL }
643 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
644 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
645 static inline void INIT_HLIST_NODE(struct hlist_node *h)
646 {
647 h->next = NULL;
648 h->pprev = NULL;
649 }
651 static inline int hlist_unhashed(const struct hlist_node *h)
652 {
653 return !h->pprev;
654 }
656 static inline int hlist_empty(const struct hlist_head *h)
657 {
658 return !h->first;
659 }
661 static inline void __hlist_del(struct hlist_node *n)
662 {
663 struct hlist_node *next = n->next;
664 struct hlist_node **pprev = n->pprev;
665 *pprev = next;
666 if (next)
667 next->pprev = pprev;
668 }
670 static inline void hlist_del(struct hlist_node *n)
671 {
672 __hlist_del(n);
673 n->next = LIST_POISON1;
674 n->pprev = LIST_POISON2;
675 }
677 /**
678 * hlist_del_rcu - deletes entry from hash list without re-initialization
679 * @n: the element to delete from the hash list.
680 *
681 * Note: list_unhashed() on entry does not return true after this,
682 * the entry is in an undefined state. It is useful for RCU based
683 * lockfree traversal.
684 *
685 * In particular, it means that we can not poison the forward
686 * pointers that may still be used for walking the hash list.
687 *
688 * The caller must take whatever precautions are necessary
689 * (such as holding appropriate locks) to avoid racing
690 * with another list-mutation primitive, such as hlist_add_head_rcu()
691 * or hlist_del_rcu(), running on this same list.
692 * However, it is perfectly legal to run concurrently with
693 * the _rcu list-traversal primitives, such as
694 * hlist_for_each_entry().
695 */
696 static inline void hlist_del_rcu(struct hlist_node *n)
697 {
698 __hlist_del(n);
699 n->pprev = LIST_POISON2;
700 }
702 static inline void hlist_del_init(struct hlist_node *n)
703 {
704 if (!hlist_unhashed(n)) {
705 __hlist_del(n);
706 INIT_HLIST_NODE(n);
707 }
708 }
710 /*
711 * hlist_replace_rcu - replace old entry by new one
712 * @old : the element to be replaced
713 * @new : the new element to insert
714 *
715 * The old entry will be replaced with the new entry atomically.
716 */
717 static inline void hlist_replace_rcu(struct hlist_node *old,
718 struct hlist_node *new)
719 {
720 struct hlist_node *next = old->next;
722 new->next = next;
723 new->pprev = old->pprev;
724 if (next)
725 new->next->pprev = &new->next;
726 *new->pprev = new;
727 old->pprev = LIST_POISON2;
728 }
730 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
731 {
732 struct hlist_node *first = h->first;
733 n->next = first;
734 if (first)
735 first->pprev = &n->next;
736 h->first = n;
737 n->pprev = &h->first;
738 }
740 /**
741 * hlist_add_head_rcu
742 * @n: the element to add to the hash list.
743 * @h: the list to add to.
744 *
745 * Description:
746 * Adds the specified element to the specified hlist,
747 * while permitting racing traversals.
748 *
749 * The caller must take whatever precautions are necessary
750 * (such as holding appropriate locks) to avoid racing
751 * with another list-mutation primitive, such as hlist_add_head_rcu()
752 * or hlist_del_rcu(), running on this same list.
753 * However, it is perfectly legal to run concurrently with
754 * the _rcu list-traversal primitives, such as
755 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
756 * problems on Alpha CPUs. Regardless of the type of CPU, the
757 * list-traversal primitive must be guarded by rcu_read_lock().
758 */
759 static inline void hlist_add_head_rcu(struct hlist_node *n,
760 struct hlist_head *h)
761 {
762 struct hlist_node *first = h->first;
763 n->next = first;
764 n->pprev = &h->first;
765 if (first)
766 first->pprev = &n->next;
767 h->first = n;
768 }
770 /* next must be != NULL */
771 static inline void hlist_add_before(struct hlist_node *n,
772 struct hlist_node *next)
773 {
774 n->pprev = next->pprev;
775 n->next = next;
776 next->pprev = &n->next;
777 *(n->pprev) = n;
778 }
780 static inline void hlist_add_after(struct hlist_node *n,
781 struct hlist_node *next)
782 {
783 next->next = n->next;
784 n->next = next;
785 next->pprev = &n->next;
787 if(next->next)
788 next->next->pprev = &next->next;
789 }
791 /**
792 * hlist_add_before_rcu
793 * @n: the new element to add to the hash list.
794 * @next: the existing element to add the new element before.
795 *
796 * Description:
797 * Adds the specified element to the specified hlist
798 * before the specified node while permitting racing traversals.
799 *
800 * The caller must take whatever precautions are necessary
801 * (such as holding appropriate locks) to avoid racing
802 * with another list-mutation primitive, such as hlist_add_head_rcu()
803 * or hlist_del_rcu(), running on this same list.
804 * However, it is perfectly legal to run concurrently with
805 * the _rcu list-traversal primitives, such as
806 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
807 * problems on Alpha CPUs.
808 */
809 static inline void hlist_add_before_rcu(struct hlist_node *n,
810 struct hlist_node *next)
811 {
812 n->pprev = next->pprev;
813 n->next = next;
814 next->pprev = &n->next;
815 *(n->pprev) = n;
816 }
818 /**
819 * hlist_add_after_rcu
820 * @prev: the existing element to add the new element after.
821 * @n: the new element to add to the hash list.
822 *
823 * Description:
824 * Adds the specified element to the specified hlist
825 * after the specified node while permitting racing traversals.
826 *
827 * The caller must take whatever precautions are necessary
828 * (such as holding appropriate locks) to avoid racing
829 * with another list-mutation primitive, such as hlist_add_head_rcu()
830 * or hlist_del_rcu(), running on this same list.
831 * However, it is perfectly legal to run concurrently with
832 * the _rcu list-traversal primitives, such as
833 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
834 * problems on Alpha CPUs.
835 */
836 static inline void hlist_add_after_rcu(struct hlist_node *prev,
837 struct hlist_node *n)
838 {
839 n->next = prev->next;
840 n->pprev = &prev->next;
841 prev->next = n;
842 if (n->next)
843 n->next->pprev = &n->next;
844 }
846 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
848 #define hlist_for_each(pos, head) \
849 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
850 pos = pos->next)
852 #define hlist_for_each_safe(pos, n, head) \
853 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
854 pos = n)
856 /**
857 * hlist_for_each_entry - iterate over list of given type
858 * @tpos: the type * to use as a loop cursor.
859 * @pos: the &struct hlist_node to use as a loop cursor.
860 * @head: the head for your list.
861 * @member: the name of the hlist_node within the struct.
862 */
863 #define hlist_for_each_entry(tpos, pos, head, member) \
864 for (pos = (head)->first; \
865 pos && ({ prefetch(pos->next); 1;}) && \
866 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
867 pos = pos->next)
869 /**
870 * hlist_for_each_entry_continue - iterate over a hlist continuing
871 * after current point
872 * @tpos: the type * to use as a loop cursor.
873 * @pos: the &struct hlist_node to use as a loop cursor.
874 * @member: the name of the hlist_node within the struct.
875 */
876 #define hlist_for_each_entry_continue(tpos, pos, member) \
877 for (pos = (pos)->next; \
878 pos && ({ prefetch(pos->next); 1;}) && \
879 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
880 pos = pos->next)
882 /**
883 * hlist_for_each_entry_from - iterate over a hlist continuing from
884 * current point
885 * @tpos: the type * to use as a loop cursor.
886 * @pos: the &struct hlist_node to use as a loop cursor.
887 * @member: the name of the hlist_node within the struct.
888 */
889 #define hlist_for_each_entry_from(tpos, pos, member) \
890 for (; pos && ({ prefetch(pos->next); 1;}) && \
891 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
892 pos = pos->next)
894 /**
895 * hlist_for_each_entry_safe - iterate over list of given type safe
896 * against removal of list entry
897 * @tpos: the type * to use as a loop cursor.
898 * @pos: the &struct hlist_node to use as a loop cursor.
899 * @n: another &struct hlist_node to use as temporary storage
900 * @head: the head for your list.
901 * @member: the name of the hlist_node within the struct.
902 */
903 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
904 for (pos = (head)->first; \
905 pos && ({ n = pos->next; 1; }) && \
906 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
907 pos = n)
910 /**
911 * hlist_for_each_entry_rcu - iterate over rcu list of given type
912 * @tpos: the type * to use as a loop cursor.
913 * @pos: the &struct hlist_node to use as a loop cursor.
914 * @head: the head for your list.
915 * @member: the name of the hlist_node within the struct.
916 *
917 * This list-traversal primitive may safely run concurrently with
918 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
919 * as long as the traversal is guarded by rcu_read_lock().
920 */
921 #define hlist_for_each_entry_rcu(tpos, pos, head, member) \
922 for (pos = (head)->first; \
923 rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) && \
924 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
925 pos = pos->next)
927 #endif /* __XEN_LIST_H__ */