ia64/xen-unstable

view xen/include/xen/list.h @ 19800:78962f85c562

IOMMU: Add two generic functions to vendor neutral interface

Add 2 generic functions into the vendor neutral iommu interface, The
reason is that from changeset 19732, there is only one global flag
"iommu_enabled" that controls iommu enablement for both vtd and amd
systems, so we need different code paths for vtd and amd iommu systems
if this flag has been turned on. Also, the early checking of
"iommu_enabled" in iommu_setup() is removed to prevent iommu
functionalities from been disabled on amd systems.

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