1 /*
2 * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28 /*
29 * @OSF_COPYRIGHT@
30 */
31 /*
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
34 * All Rights Reserved.
35 *
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
41 *
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 * Software Distribution Coordinator or [email protected]
49 * School of Computer Science
50 * Carnegie Mellon University
51 * Pittsburgh PA 15213-3890
52 *
53 * any improvements or extensions that they make and grant Carnegie Mellon rights
54 * to redistribute these changes.
55 */
56 /*
57 */
58 /*
59 * File: queue.h
60 * Author: Avadis Tevanian, Jr.
61 * Date: 1985
62 *
63 * Type definitions for generic queues.
64 *
65 */
66
67 #ifndef _KERN_QUEUE_H_
68 #define _KERN_QUEUE_H_
69
70 #if DRIVERKIT_FRAMEWORK_INCLUDE
71 #include <DriverKit/macro_help.h>
72 #else
73 #include <mach/mach_types.h>
74 #include <kern/macro_help.h>
75 #endif /* DRIVERKIT_FRAMEWORK_INCLUDE */
76
77 #include <sys/cdefs.h>
78 #include <string.h>
79
80 __BEGIN_DECLS
81
82 /*
83 * Queue Management APIs
84 *
85 * There are currently two subtly different methods of maintaining
86 * a queue of objects. Both APIs are contained in this file, and
87 * unfortunately overlap.
88 * (there is also a third way maintained in bsd/sys/queue.h)
89 *
90 * Both methods use a common queue head and linkage pattern:
91 * The head of a queue is declared as:
92 * queue_head_t q_head;
93 *
94 * Elements in this queue are chained together using
95 * struct queue_entry objects embedded within a structure:
96 * struct some_data {
97 * int field1;
98 * int field2;
99 * ...
100 * queue_chain_t link;
101 * ...
102 * int last_field;
103 * };
104 * struct some_data is referred to as the queue "element."
105 * (note that queue_chain_t is typedef'd to struct queue_entry)
106 *
107 * IMPORTANT: The two queue iteration methods described below are not
108 * compatible with one another. You must choose one and be careful
109 * to use only the supported APIs for that method.
110 *
111 * Method 1: chaining of queue_chain_t (linkage chains)
112 * This method uses the next and prev pointers of the struct queue_entry
113 * linkage object embedded in a queue element to point to the next or
114 * previous queue_entry structure in the chain. The head of the queue
115 * (the queue_head_t object) will point to the first and last
116 * struct queue_entry object, and both the next and prev pointer will
117 * point back to the head if the queue is empty.
118 *
119 * This method is the most flexible method of chaining objects together
120 * as it allows multiple chains through a given object, by embedding
121 * multiple queue_chain_t objects in the structure, while simultaneously
122 * providing fast removal and insertion into the queue using only
123 * struct queue_entry object pointers.
124 *
125 * ++ Valid APIs for this style queue ++
126 * -------------------------------------
127 * [C] queue_init
128 * [C] queue_first
129 * [C] queue_next
130 * [C] queue_last
131 * [C] queue_prev
132 * [C] queue_end
133 * [C] queue_empty
134 *
135 * [1] enqueue
136 * [1] dequeue
137 * [1] enqueue_head
138 * [1] enqueue_tail
139 * [1] dequeue_head
140 * [1] dequeue_tail
141 * [1] remqueue
142 * [1] insque
143 * [1] remque
144 * [1] re_queue_head
145 * [1] re_queue_tail
146 * [1] movqueue
147 * [1] qe_element
148 * [1] qe_foreach
149 * [1] qe_foreach_safe
150 * [1] qe_foreach_element
151 * [1] qe_foreach_element_safe
152 *
153 * Method 2: chaining of elements (element chains)
154 * This method uses the next and prev pointers of the struct queue_entry
155 * linkage object embedded in a queue element to point to the next or
156 * previous queue element (not another queue_entry). The head of the
157 * queue will point to the first and last queue element (struct some_data
158 * from the above example) NOT the embedded queue_entry structure. The
159 * first queue element will have a prev pointer that points to the
160 * queue_head_t, and the last queue element will have a next pointer
161 * that points to the queue_head_t.
162 *
163 * This method requires knowledge of the queue_head_t of the queue on
164 * which an element resides in order to remove the element. Iterating
165 * through the elements of the queue is also more cumbersome because
166 * a check against the head pointer plus a cast then offset operation
167 * must be performed at each step of the iteration.
168 *
169 * ++ Valid APIs for this style queue ++
170 * -------------------------------------
171 * [C] queue_init
172 * [C] queue_first
173 * [C] queue_next
174 * [C] queue_last
175 * [C] queue_prev
176 * [C] queue_end
177 * [C] queue_empty
178 *
179 * [2] queue_enter
180 * [2] queue_enter_first
181 * [2] queue_insert_before
182 * [2] queue_insert_after
183 * [2] queue_field
184 * [2] queue_remove
185 * [2] queue_remove_first
186 * [2] queue_remove_last
187 * [2] queue_assign
188 * [2] queue_new_head
189 * [2] queue_iterate
190 *
191 * Legend:
192 * [C] -> API common to both methods
193 * [1] -> API used only in method 1 (linkage chains)
194 * [2] -> API used only in method 2 (element chains)
195 */
196
197 /*
198 * A generic doubly-linked list (queue).
199 */
200
201 struct queue_entry {
202 struct queue_entry *next; /* next element */
203 struct queue_entry *prev; /* previous element */
204 };
205
206 typedef struct queue_entry *queue_t;
207 typedef struct queue_entry queue_head_t;
208 typedef struct queue_entry queue_chain_t;
209 typedef struct queue_entry *queue_entry_t;
210
211 #if defined(KERNEL_PRIVATE) || DRIVERKIT_FRAMEWORK_INCLUDE
212
213 #if KERNEL_PRIVATE
214 #define __queue_element_linkage_invalid(e) \
215 ml_fatal_trap_invalid_list_linkage((unsigned long)(e))
216 #else
217 #define __queue_element_linkage_invalid(e) \
218 __builtin_trap()
219 #endif
220
221 static inline void
__QUEUE_ELT_VALIDATE(queue_entry_t elt)222 __QUEUE_ELT_VALIDATE(queue_entry_t elt)
223 {
224 if (elt->prev->next != elt || elt->next->prev != elt) {
225 __queue_element_linkage_invalid(elt);
226 }
227 }
228
229 static inline queue_entry_t
__QUEUE_ELT_VALIDATE_NEXT(queue_entry_t elt)230 __QUEUE_ELT_VALIDATE_NEXT(queue_entry_t elt)
231 {
232 queue_entry_t __next = elt->next;
233
234 if (__next->prev != elt) {
235 __queue_element_linkage_invalid(elt);
236 }
237
238 return __next;
239 }
240
241 static inline queue_entry_t
__QUEUE_ELT_VALIDATE_PREV(queue_entry_t elt)242 __QUEUE_ELT_VALIDATE_PREV(queue_entry_t elt)
243 {
244 queue_entry_t __prev = elt->prev;
245
246 if (__prev->next != elt) {
247 __queue_element_linkage_invalid(elt);
248 }
249
250 return __prev;
251 }
252
253 static inline void
__DEQUEUE_ELT_CLEANUP(queue_entry_t elt)254 __DEQUEUE_ELT_CLEANUP(queue_entry_t elt)
255 {
256 elt->next = elt->prev = (queue_entry_t)NULL;
257 }
258 #else
259 #define __QUEUE_ELT_VALIDATE(elt) ((void)0)
260 #define __QUEUE_ELT_VALIDATE_NEXT(elt) ((elt)->next)
261 #define __QUEUE_ELT_VALIDATE_PREV(elt) ((elt)->prev)
262 #define __DEQUEUE_ELT_CLEANUP(elt) ((void)0)
263 #define __queue_element_linkage_invalid(e) ((void)0)
264 #endif /* !(XNU_KERNEL_PRIVATE || DRIVERKIT_FRAMEWORK_INCLUDE)*/
265
266 /*
267 * enqueue puts "elt" on the "queue".
268 * dequeue returns the first element in the "queue".
269 * remqueue removes the specified "elt" from its queue.
270 */
271
272 #if !DRIVERKIT_FRAMEWORK_INCLUDE
273 #define enqueue(queue, elt) enqueue_tail(queue, elt)
274 #define dequeue(queue) dequeue_head(queue)
275 #endif
276
277 static __inline__ void
enqueue_head(queue_t que,queue_entry_t elt)278 enqueue_head(
279 queue_t que,
280 queue_entry_t elt)
281 {
282 queue_entry_t old_head;
283
284 old_head = __QUEUE_ELT_VALIDATE_NEXT(que);
285 elt->next = old_head;
286 elt->prev = que;
287 old_head->prev = elt;
288 que->next = elt;
289 }
290
291 static __inline__ void
enqueue_tail(queue_t que,queue_entry_t elt)292 enqueue_tail(
293 queue_t que,
294 queue_entry_t elt)
295 {
296 queue_entry_t old_tail;
297
298 old_tail = __QUEUE_ELT_VALIDATE_PREV(que);
299 elt->next = que;
300 elt->prev = old_tail;
301 old_tail->next = elt;
302 que->prev = elt;
303 }
304
305 static __inline__ queue_entry_t
dequeue_head(queue_t que)306 dequeue_head(
307 queue_t que)
308 {
309 queue_entry_t elt = (queue_entry_t)NULL;
310 queue_entry_t new_head;
311
312 if (que->next != que) {
313 elt = que->next;
314 __QUEUE_ELT_VALIDATE(elt);
315 new_head = elt->next; /* new_head may point to que if elt was the only element */
316 new_head->prev = que;
317 que->next = new_head;
318 __DEQUEUE_ELT_CLEANUP(elt);
319 }
320
321 return elt;
322 }
323
324 static __inline__ queue_entry_t
dequeue_tail(queue_t que)325 dequeue_tail(
326 queue_t que)
327 {
328 queue_entry_t elt = (queue_entry_t)NULL;
329 queue_entry_t new_tail;
330
331 if (que->prev != que) {
332 elt = que->prev;
333 __QUEUE_ELT_VALIDATE(elt);
334 new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */
335 new_tail->next = que;
336 que->prev = new_tail;
337 __DEQUEUE_ELT_CLEANUP(elt);
338 }
339
340 return elt;
341 }
342
343 static __inline__ void
remqueue(queue_entry_t elt)344 remqueue(
345 queue_entry_t elt)
346 {
347 queue_entry_t next_elt, prev_elt;
348
349 __QUEUE_ELT_VALIDATE(elt);
350 next_elt = elt->next;
351 prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
352 next_elt->prev = prev_elt;
353 prev_elt->next = next_elt;
354 __DEQUEUE_ELT_CLEANUP(elt);
355 }
356
357 static __inline__ void
insque(queue_entry_t entry,queue_entry_t pred)358 insque(
359 queue_entry_t entry,
360 queue_entry_t pred)
361 {
362 queue_entry_t successor;
363
364 successor = __QUEUE_ELT_VALIDATE_NEXT(pred);
365 entry->next = successor;
366 entry->prev = pred;
367 successor->prev = entry;
368 pred->next = entry;
369 }
370
371 static __inline__ void
remque(queue_entry_t elt)372 remque(
373 queue_entry_t elt)
374 {
375 remqueue(elt);
376 }
377
378 /*
379 * Function: re_queue_head
380 * Parameters:
381 * queue_t que : queue onto which elt will be pre-pended
382 * queue_entry_t elt : element to re-queue
383 * Description:
384 * Remove elt from its current queue and put it onto the
385 * head of a new queue
386 * Note:
387 * This should only be used with Method 1 queue iteration (linkage chains)
388 */
389 static __inline__ void
re_queue_head(queue_t que,queue_entry_t elt)390 re_queue_head(queue_t que, queue_entry_t elt)
391 {
392 queue_entry_t n_elt, p_elt;
393
394 __QUEUE_ELT_VALIDATE(elt);
395 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
396
397 /* remqueue */
398 n_elt = elt->next;
399 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
400 n_elt->prev = p_elt;
401 p_elt->next = n_elt;
402
403 /* enqueue_head */
404 n_elt = que->next;
405 elt->next = n_elt;
406 elt->prev = que;
407 n_elt->prev = elt;
408 que->next = elt;
409 }
410
411 /*
412 * Function: re_queue_tail
413 * Parameters:
414 * queue_t que : queue onto which elt will be appended
415 * queue_entry_t elt : element to re-queue
416 * Description:
417 * Remove elt from its current queue and put it onto the
418 * end of a new queue
419 * Note:
420 * This should only be used with Method 1 queue iteration (linkage chains)
421 */
422 static __inline__ void
re_queue_tail(queue_t que,queue_entry_t elt)423 re_queue_tail(queue_t que, queue_entry_t elt)
424 {
425 queue_entry_t n_elt, p_elt;
426
427 __QUEUE_ELT_VALIDATE(elt);
428 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
429
430 /* remqueue */
431 n_elt = elt->next;
432 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
433 n_elt->prev = p_elt;
434 p_elt->next = n_elt;
435
436 /* enqueue_tail */
437 p_elt = que->prev;
438 elt->next = que;
439 elt->prev = p_elt;
440 p_elt->next = elt;
441 que->prev = elt;
442 }
443
444 /*
445 * Macro: qe_element
446 * Function:
447 * Convert a queue_entry_t to a queue element pointer.
448 * Get a pointer to the user-defined element containing
449 * a given queue_entry_t
450 * Header:
451 * <type> * qe_element(queue_entry_t qe, <type>, field)
452 * qe - queue entry to convert
453 * <type> - what's in the queue (e.g., struct some_data)
454 * <field> - is the chain field in <type>
455 * Note:
456 * Do not use pointer types for <type>
457 */
458 #define qe_element(qe, type, field) __container_of(qe, type, field)
459
460 /*
461 * Macro: qe_foreach
462 * Function:
463 * Iterate over each queue_entry_t structure.
464 * Generates a 'for' loop, setting 'qe' to
465 * each queue_entry_t in the queue.
466 * Header:
467 * qe_foreach(queue_entry_t qe, queue_t head)
468 * qe - iteration variable
469 * head - pointer to queue_head_t (head of queue)
470 * Note:
471 * This should only be used with Method 1 queue iteration (linkage chains)
472 */
473 #define qe_foreach(qe, head) \
474 for (qe = (head)->next; qe != (head); qe = (qe)->next)
475
476 /*
477 * Macro: qe_foreach_safe
478 * Function:
479 * Safely iterate over each queue_entry_t structure.
480 *
481 * Use this iterator macro if you plan to remove the
482 * queue_entry_t, qe, from the queue during the
483 * iteration.
484 * Header:
485 * qe_foreach_safe(queue_entry_t qe, queue_t head)
486 * qe - iteration variable
487 * head - pointer to queue_head_t (head of queue)
488 * Note:
489 * This should only be used with Method 1 queue iteration (linkage chains)
490 */
491 #define qe_foreach_safe(qe, head) \
492 for (queue_entry_t _ne = ((head)->next)->next, \
493 __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \
494 qe != (head); \
495 qe = _ne, _ne = (qe)->next)
496
497 /*
498 * Macro: qe_foreach_element
499 * Function:
500 * Iterate over each _element_ in a queue
501 * where each queue_entry_t points to another
502 * queue_entry_t, i.e., managed by the [de|en]queue_head/
503 * [de|en]queue_tail / remqueue / etc. function.
504 * Header:
505 * qe_foreach_element(<type> *elt, queue_t head, <field>)
506 * elt - iteration variable
507 * <type> - what's in the queue (e.g., struct some_data)
508 * <field> - is the chain field in <type>
509 * Note:
510 * This should only be used with Method 1 queue iteration (linkage chains)
511 */
512 #define qe_foreach_element(elt, head, field) \
513 for (elt = qe_element((head)->next, typeof(*(elt)), field); \
514 &((elt)->field) != (head); \
515 elt = qe_element((elt)->field.next, typeof(*(elt)), field))
516
517 /*
518 * Macro: qe_foreach_element_safe
519 * Function:
520 * Safely iterate over each _element_ in a queue
521 * where each queue_entry_t points to another
522 * queue_entry_t, i.e., managed by the [de|en]queue_head/
523 * [de|en]queue_tail / remqueue / etc. function.
524 *
525 * Use this iterator macro if you plan to remove the
526 * element, elt, from the queue during the iteration.
527 * Header:
528 * qe_foreach_element_safe(<type> *elt, queue_t head, <field>)
529 * elt - iteration variable
530 * <type> - what's in the queue (e.g., struct some_data)
531 * <field> - is the chain field in <type>
532 * Note:
533 * This should only be used with Method 1 queue iteration (linkage chains)
534 */
535 #define qe_foreach_element_safe(elt, head, field) \
536 for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \
537 *__ ## elt ## _unused_shadow __unused = \
538 (elt = qe_element((head)->next, typeof(*(elt)), field)); \
539 &((elt)->field) != (head); \
540 elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
541
542 #ifdef XNU_KERNEL_PRIVATE
543
544 /* Dequeue an element from head, or return NULL if the queue is empty */
545 #define qe_dequeue_head(head, type, field) ({ \
546 queue_entry_t _tmp_entry = dequeue_head((head)); \
547 type *_tmp_element = (type*) NULL; \
548 if (_tmp_entry != (queue_entry_t) NULL) \
549 _tmp_element = qe_element(_tmp_entry, type, field); \
550 _tmp_element; \
551 })
552
553 /* Dequeue an element from tail, or return NULL if the queue is empty */
554 #define qe_dequeue_tail(head, type, field) ({ \
555 queue_entry_t _tmp_entry = dequeue_tail((head)); \
556 type *_tmp_element = (type*) NULL; \
557 if (_tmp_entry != (queue_entry_t) NULL) \
558 _tmp_element = qe_element(_tmp_entry, type, field); \
559 _tmp_element; \
560 })
561
562 /* Peek at the first element, or return NULL if the queue is empty */
563 #define qe_queue_first(head, type, field) ({ \
564 queue_entry_t _tmp_entry = queue_first((head)); \
565 type *_tmp_element = (type*) NULL; \
566 if (_tmp_entry != (queue_entry_t) head) \
567 _tmp_element = qe_element(_tmp_entry, type, field); \
568 _tmp_element; \
569 })
570
571 /* Peek at the last element, or return NULL if the queue is empty */
572 #define qe_queue_last(head, type, field) ({ \
573 queue_entry_t _tmp_entry = queue_last((head)); \
574 type *_tmp_element = (type*) NULL; \
575 if (_tmp_entry != (queue_entry_t) head) \
576 _tmp_element = qe_element(_tmp_entry, type, field); \
577 _tmp_element; \
578 })
579
580 /* Peek at the next element, or return NULL if the next element is head (indicating queue_end) */
581 #define qe_queue_next(head, element, type, field) ({ \
582 queue_entry_t _tmp_entry = queue_next(&(element)->field); \
583 type *_tmp_element = (type*) NULL; \
584 if (_tmp_entry != (queue_entry_t) head) \
585 _tmp_element = qe_element(_tmp_entry, type, field); \
586 _tmp_element; \
587 })
588
589 /* Peek at the prev element, or return NULL if the prev element is head (indicating queue_end) */
590 #define qe_queue_prev(head, element, type, field) ({ \
591 queue_entry_t _tmp_entry = queue_prev(&(element)->field); \
592 type *_tmp_element = (type*) NULL; \
593 if (_tmp_entry != (queue_entry_t) head) \
594 _tmp_element = qe_element(_tmp_entry, type, field); \
595 _tmp_element; \
596 })
597
598 #endif /* XNU_KERNEL_PRIVATE */
599
600 /*
601 * Macro: QUEUE_HEAD_INITIALIZER()
602 * Function:
603 * Static queue head initializer
604 */
605 #define QUEUE_HEAD_INITIALIZER(name) \
606 { &name, &name }
607
608 /*
609 * Macro: queue_init
610 * Function:
611 * Initialize the given queue.
612 * Header:
613 * void queue_init(q)
614 * queue_t q; \* MODIFIED *\
615 */
616 #define queue_init(q) \
617 MACRO_BEGIN \
618 (q)->next = (q);\
619 (q)->prev = (q);\
620 MACRO_END
621
622 /*
623 * Macro: queue_head_init
624 * Function:
625 * Initialize the given queue head
626 * Header:
627 * void queue_head_init(q)
628 * queue_head_t q; \* MODIFIED *\
629 */
630 #define queue_head_init(q) \
631 queue_init(&(q))
632
633 /*
634 * Macro: queue_chain_init
635 * Function:
636 * Initialize the given queue chain element
637 * Header:
638 * void queue_chain_init(q)
639 * queue_chain_t q; \* MODIFIED *\
640 */
641 #define queue_chain_init(q) \
642 queue_init(&(q))
643
644 /*
645 * Macro: queue_first
646 * Function:
647 * Returns the first entry in the queue,
648 * Header:
649 * queue_entry_t queue_first(q)
650 * queue_t q; \* IN *\
651 */
652 #define queue_first(q) ((q)->next)
653
654 /*
655 * Macro: queue_next
656 * Function:
657 * Returns the entry after an item in the queue.
658 * Header:
659 * queue_entry_t queue_next(qc)
660 * queue_t qc;
661 */
662 #define queue_next(qc) ((qc)->next)
663
664 /*
665 * Macro: queue_last
666 * Function:
667 * Returns the last entry in the queue.
668 * Header:
669 * queue_entry_t queue_last(q)
670 * queue_t q; \* IN *\
671 */
672 #define queue_last(q) ((q)->prev)
673
674 /*
675 * Macro: queue_prev
676 * Function:
677 * Returns the entry before an item in the queue.
678 * Header:
679 * queue_entry_t queue_prev(qc)
680 * queue_t qc;
681 */
682 #define queue_prev(qc) ((qc)->prev)
683
684 /*
685 * Macro: queue_end
686 * Function:
687 * Tests whether a new entry is really the end of
688 * the queue.
689 * Header:
690 * boolean_t queue_end(q, qe)
691 * queue_t q;
692 * queue_entry_t qe;
693 */
694 #define queue_end(q, qe) ((q) == (qe))
695
696 /*
697 * Macro: queue_empty
698 * Function:
699 * Tests whether a queue is empty.
700 * Header:
701 * boolean_t queue_empty(q)
702 * queue_t q;
703 */
704 #define queue_empty(q) queue_end((q), queue_first(q))
705
706 /*
707 * Function: movqueue
708 * Parameters:
709 * queue_t _old : head of a queue whose items will be moved
710 * queue_t _new : new queue head onto which items will be moved
711 * Description:
712 * Rebase queue items in _old onto _new then re-initialize
713 * the _old object to an empty queue.
714 * Equivalent to the queue_new_head Method 2 macro
715 * Note:
716 * Similar to the queue_new_head macro, this macros is intented
717 * to function as an initializer method for '_new' and thus may
718 * leak any list items that happen to be on the '_new' list.
719 * This should only be used with Method 1 queue iteration (linkage chains)
720 */
721 static __inline__ void
movqueue(queue_t _old,queue_t _new)722 movqueue(queue_t _old, queue_t _new)
723 {
724 queue_entry_t next_elt, prev_elt;
725
726 __QUEUE_ELT_VALIDATE((queue_entry_t)_old);
727
728 if (queue_empty(_old)) {
729 queue_init(_new);
730 return;
731 }
732
733 /*
734 * move the queue at _old to _new
735 * and re-initialize _old
736 */
737 next_elt = _old->next;
738 prev_elt = _old->prev;
739
740 _new->next = next_elt;
741 _new->prev = prev_elt;
742 next_elt->prev = _new;
743 prev_elt->next = _new;
744
745 queue_init(_old);
746 }
747
748 /*----------------------------------------------------------------*/
749 /*
750 * Macros that operate on generic structures. The queue
751 * chain may be at any location within the structure, and there
752 * may be more than one chain.
753 */
754
755 /* check __prev->next == __elt */
756 #define __QUEUE2_CHECK_NEXT(__fail, __elt, __prev, __head, type, field) \
757 MACRO_BEGIN \
758 if (__prev == __head) { \
759 __fail |= __head->next != (queue_entry_t)__elt; \
760 } else { \
761 __fail |= ((type)(void *)__prev)->field.next != \
762 (queue_entry_t)__elt; \
763 } \
764 MACRO_END
765
766 /* check __next->prev == __elt */
767 #define __QUEUE2_CHECK_PREV(__fail, __elt, __next, __head, type, field) \
768 MACRO_BEGIN \
769 if (__next == __head) { \
770 __fail |= __head->prev != (queue_entry_t)__elt; \
771 } else { \
772 __fail |= ((type)(void *)__next)->field.prev != \
773 (queue_entry_t)__elt; \
774 } \
775 MACRO_END
776
777 #define __QUEUE2_CHECK_FAIL(__fail, __elt) \
778 MACRO_BEGIN \
779 if (__improbable(__fail)) { \
780 __queue_element_linkage_invalid(__elt); \
781 } \
782 MACRO_END
783
784 /* sets __prev->next to __elt */
785 #define __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field) \
786 MACRO_BEGIN \
787 if (__head == __prev) { \
788 __head->next = (queue_entry_t)__elt; \
789 } else { \
790 ((type)(void *)__prev)->field.next = (queue_entry_t)__elt; \
791 } \
792 MACRO_END
793
794 /* sets __next->prev to __elt */
795 #define __QUEUE2_SET_PREV(__next, __elt, __head, type, field) \
796 MACRO_BEGIN \
797 if (__head == __next) { \
798 __head->prev = (queue_entry_t)__elt; \
799 } else { \
800 ((type)(void *)__next)->field.prev = (queue_entry_t)__elt; \
801 } \
802 MACRO_END
803
804
805
806 /*
807 * Macro: queue_enter
808 * Function:
809 * Insert a new element at the tail of the queue.
810 * Header:
811 * void queue_enter(q, elt, type, field)
812 * queue_t q;
813 * <type> elt;
814 * <type> is what's in our queue
815 * <field> is the chain field in (*<type>)
816 * Note:
817 * This should only be used with Method 2 queue iteration (element chains)
818 *
819 * We insert a compiler barrier after setting the fields in the element
820 * to ensure that the element is updated before being added to the queue,
821 * which is especially important because stackshot, which operates from
822 * debugger context, iterates several queues that use this macro (the tasks
823 * lists and threads lists) without locks. Without this barrier, the
824 * compiler may re-order the instructions for this macro in a way that
825 * could cause stackshot to trip over an inconsistent queue during
826 * iteration.
827 */
828 #define queue_enter(head, elt, type, field) \
829 MACRO_BEGIN \
830 queue_entry_t __head, __prev; \
831 type __elt; \
832 int __fail = 0; \
833 \
834 __elt = (elt); \
835 __head = (head); \
836 __prev = __head->prev; \
837 \
838 __QUEUE2_CHECK_NEXT(__fail, __head, __prev, __head, type, field); \
839 __QUEUE2_CHECK_FAIL(__fail, __head); \
840 \
841 __elt->field.prev = __prev; \
842 __elt->field.next = __head; \
843 __compiler_barrier(); \
844 __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field); \
845 __head->prev = (queue_entry_t)__elt; \
846 MACRO_END
847
848 /*
849 * Macro: queue_enter_first
850 * Function:
851 * Insert a new element at the head of the queue.
852 * Header:
853 * void queue_enter_first(q, elt, type, field)
854 * queue_t q;
855 * <type> elt;
856 * <type> is what's in our queue
857 * <field> is the chain field in (*<type>)
858 * Note:
859 * This should only be used with Method 2 queue iteration (element chains)
860 */
861 #define queue_enter_first(head, elt, type, field) \
862 MACRO_BEGIN \
863 queue_entry_t __head, __next; \
864 type __elt; \
865 int __fail = 0; \
866 \
867 __elt = (elt); \
868 __head = (head); \
869 __next = __head->next; \
870 \
871 __QUEUE2_CHECK_PREV(__fail, __head, __next, __head, type, field); \
872 __QUEUE2_CHECK_FAIL(__fail, __head); \
873 \
874 __elt->field.next = __next; \
875 __elt->field.prev = __head; \
876 __compiler_barrier(); \
877 __QUEUE2_SET_PREV(__next, __elt, __head, type, field); \
878 __head->next = (queue_entry_t)__elt; \
879 MACRO_END
880
881 /*
882 * Macro: queue_insert_before
883 * Function:
884 * Insert a new element before a given element.
885 * Header:
886 * void queue_insert_before(q, elt, cur, type, field)
887 * queue_t q;
888 * <type> elt;
889 * <type> cur;
890 * <type> is what's in our queue
891 * <field> is the chain field in (*<type>)
892 * Note:
893 * This should only be used with Method 2 queue iteration (element chains)
894 */
895 #define queue_insert_before(head, elt, cur, type, field) \
896 MACRO_BEGIN \
897 queue_entry_t __head, __cur, __prev; \
898 type __elt; \
899 int __fail = 0; \
900 \
901 __elt = (elt); \
902 __cur = (queue_entry_t)(cur); \
903 __head = (head); \
904 \
905 if (__head == __cur) { \
906 __prev = __head->prev; \
907 } else { \
908 __prev = ((type)(void *)__cur)->field.prev; \
909 } \
910 \
911 __QUEUE2_CHECK_NEXT(__fail, __cur, __prev, __head, type, field); \
912 __QUEUE2_CHECK_FAIL(__fail, __head); \
913 \
914 __elt->field.prev = __prev; \
915 __elt->field.next = __cur; \
916 __compiler_barrier(); \
917 __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field); \
918 __QUEUE2_SET_PREV(__cur, __elt, __head, type, field); \
919 MACRO_END
920
921 /*
922 * Macro: queue_insert_after
923 * Function:
924 * Insert a new element after a given element.
925 * Header:
926 * void queue_insert_after(q, elt, cur, type, field)
927 * queue_t q;
928 * <type> elt;
929 * <type> cur;
930 * <type> is what's in our queue
931 * <field> is the chain field in (*<type>)
932 * Note:
933 * This should only be used with Method 2 queue iteration (element chains)
934 */
935 #define queue_insert_after(head, elt, cur, type, field) \
936 MACRO_BEGIN \
937 queue_entry_t __head, __cur, __next; \
938 type __elt; \
939 int __fail = 0; \
940 \
941 __elt = (elt); \
942 __cur = (queue_entry_t)(cur); \
943 __head = (head); \
944 \
945 if (__head == __cur) { \
946 __next = __head->next; \
947 } else { \
948 __next = ((type)(void *)__cur)->field.next; \
949 } \
950 \
951 __QUEUE2_CHECK_PREV(__fail, __cur, __next, __head, type, field); \
952 __QUEUE2_CHECK_FAIL(__fail, __head); \
953 \
954 __elt->field.prev = __cur; \
955 __elt->field.next = __next; \
956 __compiler_barrier(); \
957 __QUEUE2_SET_NEXT(__cur, __elt, __head, type, field); \
958 __QUEUE2_SET_PREV(__next, __elt, __head, type, field); \
959 MACRO_END
960
961 /*
962 * Macro: queue_field [internal use only]
963 * Function:
964 * Find the queue_chain_t (or queue_t) for the
965 * given element (thing) in the given queue (head)
966 * Note:
967 * This should only be used with Method 2 queue iteration (element chains)
968 */
969 #define queue_field(head, thing, type, field) \
970 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
971
972 /*
973 * Macro: queue_remove
974 * Function:
975 * Remove an arbitrary item from the queue.
976 * Header:
977 * void queue_remove(q, qe, type, field)
978 * arguments as in queue_enter
979 * Note:
980 * This should only be used with Method 2 queue iteration (element chains)
981 */
982 #define queue_remove(head, elt, type, field) \
983 MACRO_BEGIN \
984 queue_entry_t __head, __next, __prev; \
985 type __elt; \
986 int __fail = 0; \
987 \
988 __elt = (elt); \
989 __head = (head); \
990 __next = __elt->field.next; \
991 __prev = __elt->field.prev; \
992 \
993 __QUEUE2_CHECK_PREV(__fail, __elt, __next, __head, type, field); \
994 __QUEUE2_CHECK_NEXT(__fail, __elt, __prev, __head, type, field); \
995 __QUEUE2_CHECK_FAIL(__fail, __head); \
996 \
997 __QUEUE2_SET_PREV(__next, __prev, __head, type, field); \
998 __QUEUE2_SET_NEXT(__prev, __next, __head, type, field); \
999 __compiler_barrier(); \
1000 __elt->field.next = NULL; \
1001 __elt->field.prev = NULL; \
1002 MACRO_END
1003
1004 /*
1005 * Macro: queue_remove_first
1006 * Function:
1007 * Remove and return the entry at the head of
1008 * the queue.
1009 * Header:
1010 * queue_remove_first(head, entry, type, field)
1011 * entry is returned by reference
1012 * Note:
1013 * This should only be used with Method 2 queue iteration (element chains)
1014 */
1015 #define queue_remove_first(head, entry, type, field) \
1016 MACRO_BEGIN \
1017 queue_entry_t __hd; \
1018 type __entry; \
1019 \
1020 __hd = (head); \
1021 __entry = (type)(void *)__hd->next; \
1022 \
1023 if ((queue_entry_t)__entry != __hd) { \
1024 queue_remove(__hd, __entry, type, field); \
1025 } \
1026 (entry) = __entry; \
1027 MACRO_END
1028
1029 /*
1030 * Macro: queue_remove_last
1031 * Function:
1032 * Remove and return the entry at the tail of
1033 * the queue.
1034 * Header:
1035 * queue_remove_last(head, entry, type, field)
1036 * entry is returned by reference
1037 * Note:
1038 * This should only be used with Method 2 queue iteration (element chains)
1039 */
1040 #define queue_remove_last(head, entry, type, field) \
1041 MACRO_BEGIN \
1042 queue_entry_t __hd; \
1043 type __entry; \
1044 \
1045 __hd = (head); \
1046 __entry = (type)(void *)__hd->prev; \
1047 \
1048 if ((queue_entry_t)__entry != __hd) { \
1049 queue_remove(__hd, __entry, type, field); \
1050 } \
1051 (entry) = __entry; \
1052 MACRO_END
1053
1054 /*
1055 * Macro: queue_assign
1056 * Note:
1057 * This should only be used with Method 2 queue iteration (element chains)
1058 */
1059 #define queue_assign(to, from, type, field) \
1060 MACRO_BEGIN \
1061 ((type)(void *)((from)->prev))->field.next = (to); \
1062 ((type)(void *)((from)->next))->field.prev = (to); \
1063 *to = *from; \
1064 MACRO_END
1065
1066 /*
1067 * Macro: queue_new_head
1068 * Function:
1069 * rebase old queue to new queue head
1070 * Header:
1071 * queue_new_head(old, new, type, field)
1072 * queue_t old;
1073 * queue_t new;
1074 * <type> is what's in our queue
1075 * <field> is the chain field in (*<type>)
1076 * Note:
1077 * This should only be used with Method 2 queue iteration (element chains)
1078 */
1079 #define queue_new_head(old, new, type, field) \
1080 MACRO_BEGIN \
1081 if (!queue_empty(old)) { \
1082 *(new) = *(old); \
1083 ((type)(void *)((new)->next))->field.prev = \
1084 (new); \
1085 ((type)(void *)((new)->prev))->field.next = \
1086 (new); \
1087 } else { \
1088 queue_init(new); \
1089 } \
1090 MACRO_END
1091
1092 /*
1093 * Macro: queue_iterate
1094 * Function:
1095 * iterate over each item in the queue.
1096 * Generates a 'for' loop, setting elt to
1097 * each item in turn (by reference).
1098 * Header:
1099 * queue_iterate(q, elt, type, field)
1100 * queue_t q;
1101 * <type> elt;
1102 * <type> is what's in our queue
1103 * <field> is the chain field in (*<type>)
1104 * Note:
1105 * This should only be used with Method 2 queue iteration (element chains)
1106 */
1107 #define queue_iterate(head, elt, type, field) \
1108 for ((elt) = (type)(void *) queue_first(head); \
1109 !queue_end((head), (queue_entry_t)(elt)); \
1110 (elt) = (type)(void *) queue_next(&(elt)->field))
1111
1112
1113 __END_DECLS
1114
1115 #endif /* _KERN_QUEUE_H_ */
1116