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