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