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