X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/3903760236c30e3b5ace7a4eefac3a269d68957c..refs/heads/master:/osfmk/kern/queue.h diff --git a/osfmk/kern/queue.h b/osfmk/kern/queue.h index dc99d000f..ac758f79e 100644 --- a/osfmk/kern/queue.h +++ b/osfmk/kern/queue.h @@ -2,7 +2,7 @@ * Copyright (c) 2000-2009 Apple Inc. All rights reserved. * * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ - * + * * This file contains Original Code and/or Modifications of Original Code * as defined in and that are subject to the Apple Public Source License * Version 2.0 (the 'License'). You may not use this file except in @@ -11,10 +11,10 @@ * unlawful or unlicensed copies of an Apple operating system, or to * circumvent, violate, or enable the circumvention or violation of, any * terms of an Apple operating system software license agreement. - * + * * Please obtain a copy of the License at * http://www.opensource.apple.com/apsl/ and read it before using this file. - * + * * The Original Code and all software distributed under the License are * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, @@ -22,27 +22,27 @@ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. * Please see the License for the specific language governing rights and * limitations under the License. - * + * * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ /* * @OSF_COPYRIGHT@ */ -/* +/* * Mach Operating System * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University * All Rights Reserved. - * + * * Permission to use, copy, modify and distribute this software and its * documentation is hereby granted, provided that both the copyright * notice and this permission notice appear in all copies of the * software, derivative works or modified versions, and any portions * thereof, and that both notices appear in supporting documentation. - * + * * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. - * + * * Carnegie Mellon requests users of this software to return to * * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU @@ -64,13 +64,14 @@ * */ -#ifndef _KERN_QUEUE_H_ -#define _KERN_QUEUE_H_ +#ifndef _KERN_QUEUE_H_ +#define _KERN_QUEUE_H_ #include #include #include +#include __BEGIN_DECLS @@ -83,110 +84,110 @@ __BEGIN_DECLS * (there is also a third way maintained in bsd/sys/queue.h) * * Both methods use a common queue head and linkage pattern: - * The head of a queue is declared as: - * queue_head_t q_head; + * The head of a queue is declared as: + * queue_head_t q_head; * - * Elements in this queue are chained together using - * struct queue_entry objects embedded within a structure: - * struct some_data { - * int field1; - * int field2; - * ... - * queue_chain_t link; - * ... - * int last_field; - * }; - * struct some_data is referred to as the queue "element." - * (note that queue_chain_t is typedef'd to struct queue_entry) + * Elements in this queue are chained together using + * struct queue_entry objects embedded within a structure: + * struct some_data { + * int field1; + * int field2; + * ... + * queue_chain_t link; + * ... + * int last_field; + * }; + * struct some_data is referred to as the queue "element." + * (note that queue_chain_t is typedef'd to struct queue_entry) * * IMPORTANT: The two queue iteration methods described below are not * compatible with one another. You must choose one and be careful * to use only the supported APIs for that method. * * Method 1: chaining of queue_chain_t (linkage chains) - * This method uses the next and prev pointers of the struct queue_entry - * linkage object embedded in a queue element to point to the next or - * previous queue_entry structure in the chain. The head of the queue - * (the queue_head_t object) will point to the first and last - * struct queue_entry object, and both the next and prev pointer will - * point back to the head if the queue is empty. + * This method uses the next and prev pointers of the struct queue_entry + * linkage object embedded in a queue element to point to the next or + * previous queue_entry structure in the chain. The head of the queue + * (the queue_head_t object) will point to the first and last + * struct queue_entry object, and both the next and prev pointer will + * point back to the head if the queue is empty. * - * This method is the most flexible method of chaining objects together - * as it allows multiple chains through a given object, by embedding - * multiple queue_chain_t objects in the structure, while simultaneously - * providing fast removal and insertion into the queue using only - * struct queue_entry object pointers. + * This method is the most flexible method of chaining objects together + * as it allows multiple chains through a given object, by embedding + * multiple queue_chain_t objects in the structure, while simultaneously + * providing fast removal and insertion into the queue using only + * struct queue_entry object pointers. * - * ++ Valid APIs for this style queue ++ - * ------------------------------------- - * [C] queue_init - * [C] queue_first - * [C] queue_next - * [C] queue_last - * [C] queue_prev - * [C] queue_end - * [C] queue_empty + * ++ Valid APIs for this style queue ++ + * ------------------------------------- + * [C] queue_init + * [C] queue_first + * [C] queue_next + * [C] queue_last + * [C] queue_prev + * [C] queue_end + * [C] queue_empty * - * [1] enqueue - * [1] dequeue - * [1] enqueue_head - * [1] enqueue_tail - * [1] dequeue_head - * [1] dequeue_tail - * [1] remqueue - * [1] insque - * [1] remque - * [1] re_queue_head - * [1] re_queue_tail - * [1] movqueue - * [1] qe_element - * [1] qe_foreach - * [1] qe_foreach_safe - * [1] qe_foreach_element - * [1] qe_foreach_element_safe + * [1] enqueue + * [1] dequeue + * [1] enqueue_head + * [1] enqueue_tail + * [1] dequeue_head + * [1] dequeue_tail + * [1] remqueue + * [1] insque + * [1] remque + * [1] re_queue_head + * [1] re_queue_tail + * [1] movqueue + * [1] qe_element + * [1] qe_foreach + * [1] qe_foreach_safe + * [1] qe_foreach_element + * [1] qe_foreach_element_safe * * Method 2: chaining of elements (element chains) - * This method uses the next and prev pointers of the struct queue_entry - * linkage object embedded in a queue element to point to the next or - * previous queue element (not another queue_entry). The head of the - * queue will point to the first and last queue element (struct some_data - * from the above example) NOT the embedded queue_entry structure. The - * first queue element will have a prev pointer that points to the - * queue_head_t, and the last queue element will have a next pointer - * that points to the queue_head_t. + * This method uses the next and prev pointers of the struct queue_entry + * linkage object embedded in a queue element to point to the next or + * previous queue element (not another queue_entry). The head of the + * queue will point to the first and last queue element (struct some_data + * from the above example) NOT the embedded queue_entry structure. The + * first queue element will have a prev pointer that points to the + * queue_head_t, and the last queue element will have a next pointer + * that points to the queue_head_t. * - * This method requires knowledge of the queue_head_t of the queue on - * which an element resides in order to remove the element. Iterating - * through the elements of the queue is also more cumbersome because - * a check against the head pointer plus a cast then offset operation - * must be performed at each step of the iteration. + * This method requires knowledge of the queue_head_t of the queue on + * which an element resides in order to remove the element. Iterating + * through the elements of the queue is also more cumbersome because + * a check against the head pointer plus a cast then offset operation + * must be performed at each step of the iteration. * - * ++ Valid APIs for this style queue ++ - * ------------------------------------- - * [C] queue_init - * [C] queue_first - * [C] queue_next - * [C] queue_last - * [C] queue_prev - * [C] queue_end - * [C] queue_empty + * ++ Valid APIs for this style queue ++ + * ------------------------------------- + * [C] queue_init + * [C] queue_first + * [C] queue_next + * [C] queue_last + * [C] queue_prev + * [C] queue_end + * [C] queue_empty * - * [2] queue_enter - * [2] queue_enter_first - * [2] queue_insert_before - * [2] queue_insert_after - * [2] queue_field - * [2] queue_remove - * [2] queue_remove_first - * [2] queue_remove_last - * [2] queue_assign - * [2] queue_new_head - * [2] queue_iterate + * [2] queue_enter + * [2] queue_enter_first + * [2] queue_insert_before + * [2] queue_insert_after + * [2] queue_field + * [2] queue_remove + * [2] queue_remove_first + * [2] queue_remove_last + * [2] queue_assign + * [2] queue_new_head + * [2] queue_iterate * * Legend: - * [C] -> API common to both methods - * [1] -> API used only in method 1 (linkage chains) - * [2] -> API used only in method 2 (element chains) + * [C] -> API common to both methods + * [1] -> API used only in method 1 (linkage chains) + * [2] -> API used only in method 2 (element chains) */ /* @@ -194,15 +195,26 @@ __BEGIN_DECLS */ struct queue_entry { - struct queue_entry *next; /* next element */ - struct queue_entry *prev; /* previous element */ - + struct queue_entry *next; /* next element */ + struct queue_entry *prev; /* previous element */ + +#if __arm__ && (__BIGGEST_ALIGNMENT__ > 4) +/* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers + * are 32-bit: + * Since this type is so often cast to various 64-bit aligned types + * aligning it to 64-bits will avoid -wcast-align without needing + * to disable it entirely. The impact on memory footprint should be + * negligible. + */ +} __attribute__ ((aligned(8))); +#else }; +#endif -typedef struct queue_entry *queue_t; -typedef struct queue_entry queue_head_t; -typedef struct queue_entry queue_chain_t; -typedef struct queue_entry *queue_entry_t; +typedef struct queue_entry *queue_t; +typedef struct queue_entry queue_head_t; +typedef struct queue_entry queue_chain_t; +typedef struct queue_entry *queue_entry_t; /* * enqueue puts "elt" on the "queue". @@ -210,34 +222,37 @@ typedef struct queue_entry *queue_entry_t; * remqueue removes the specified "elt" from its queue. */ -#define enqueue(queue,elt) enqueue_tail(queue, elt) -#define dequeue(queue) dequeue_head(queue) +#define enqueue(queue, elt) enqueue_tail(queue, elt) +#define dequeue(queue) dequeue_head(queue) #ifdef XNU_KERNEL_PRIVATE #include -#include -static inline void __QUEUE_ELT_VALIDATE(queue_entry_t elt) { - queue_entry_t elt_next, elt_prev; - - if (__improbable(elt == (queue_entry_t)0)) { +static inline void +__QUEUE_ELT_VALIDATE(queue_entry_t elt) +{ + queue_entry_t elt_next, elt_prev; + + if (__improbable(elt == (queue_entry_t)NULL)) { panic("Invalid queue element %p", elt); } - + elt_next = elt->next; elt_prev = elt->prev; - - if (__improbable(elt_next == (queue_entry_t)0 || elt_prev == (queue_entry_t)0)) { + + if (__improbable(elt_next == (queue_entry_t)NULL || elt_prev == (queue_entry_t)NULL)) { panic("Invalid queue element pointers for %p: next %p prev %p", elt, elt_next, elt_prev); } if (__improbable(elt_next->prev != elt || elt_prev->next != elt)) { - panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p", - elt, elt_next, elt_next->prev, elt_prev, elt_prev->next); + panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p", + elt, elt_next, elt_next->prev, elt_prev, elt_prev->next); } } -static inline void __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) { - (elt)->next = (queue_entry_t) 0; - (elt)->prev = (queue_entry_t) 0; +static inline void +__DEQUEUE_ELT_CLEANUP(queue_entry_t elt) +{ + (elt)->next = (queue_entry_t)NULL; + (elt)->prev = (queue_entry_t)NULL; } #else #define __QUEUE_ELT_VALIDATE(elt) do { } while (0) @@ -246,10 +261,10 @@ static inline void __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) { static __inline__ void enqueue_head( - queue_t que, - queue_entry_t elt) + queue_t que, + queue_entry_t elt) { - queue_entry_t old_head; + queue_entry_t old_head; __QUEUE_ELT_VALIDATE((queue_entry_t)que); old_head = que->next; @@ -261,10 +276,10 @@ enqueue_head( static __inline__ void enqueue_tail( - queue_t que, - queue_entry_t elt) + queue_t que, + queue_entry_t elt) { - queue_entry_t old_tail; + queue_entry_t old_tail; __QUEUE_ELT_VALIDATE((queue_entry_t)que); old_tail = que->prev; @@ -276,10 +291,10 @@ enqueue_tail( static __inline__ queue_entry_t dequeue_head( - queue_t que) + queue_t que) { - queue_entry_t elt = (queue_entry_t) 0; - queue_entry_t new_head; + queue_entry_t elt = (queue_entry_t)NULL; + queue_entry_t new_head; if (que->next != que) { elt = que->next; @@ -290,15 +305,15 @@ dequeue_head( __DEQUEUE_ELT_CLEANUP(elt); } - return (elt); + return elt; } static __inline__ queue_entry_t dequeue_tail( - queue_t que) + queue_t que) { - queue_entry_t elt = (queue_entry_t) 0; - queue_entry_t new_tail; + queue_entry_t elt = (queue_entry_t)NULL; + queue_entry_t new_tail; if (que->prev != que) { elt = que->prev; @@ -309,14 +324,14 @@ dequeue_tail( __DEQUEUE_ELT_CLEANUP(elt); } - return (elt); + return elt; } static __inline__ void remqueue( - queue_entry_t elt) + queue_entry_t elt) { - queue_entry_t next_elt, prev_elt; + queue_entry_t next_elt, prev_elt; __QUEUE_ELT_VALIDATE(elt); next_elt = elt->next; @@ -328,10 +343,10 @@ remqueue( static __inline__ void insque( - queue_entry_t entry, - queue_entry_t pred) + queue_entry_t entry, + queue_entry_t pred) { - queue_entry_t successor; + queue_entry_t successor; __QUEUE_ELT_VALIDATE(pred); successor = pred->next; @@ -345,14 +360,7 @@ static __inline__ void remque( queue_entry_t elt) { - queue_entry_t next_elt, prev_elt; - - __QUEUE_ELT_VALIDATE(elt); - next_elt = elt->next; - prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ - next_elt->prev = prev_elt; - prev_elt->next = next_elt; - __DEQUEUE_ELT_CLEANUP(elt); + remqueue(elt); } /* @@ -369,7 +377,7 @@ remque( static __inline__ void re_queue_head(queue_t que, queue_entry_t elt) { - queue_entry_t n_elt, p_elt; + queue_entry_t n_elt, p_elt; __QUEUE_ELT_VALIDATE(elt); __QUEUE_ELT_VALIDATE((queue_entry_t)que); @@ -402,7 +410,7 @@ re_queue_head(queue_t que, queue_entry_t elt) static __inline__ void re_queue_tail(queue_t que, queue_entry_t elt) { - queue_entry_t n_elt, p_elt; + queue_entry_t n_elt, p_elt; __QUEUE_ELT_VALIDATE(elt); __QUEUE_ELT_VALIDATE((queue_entry_t)que); @@ -435,8 +443,7 @@ re_queue_tail(queue_t que, queue_entry_t elt) * Note: * Do not use pointer types for */ -#define qe_element(qe, type, field) \ - ((type *)((void *)((char *)(qe) - __offsetof(type, field)))) +#define qe_element(qe, type, field) __container_of(qe, type, field) /* * Macro: qe_foreach @@ -527,7 +534,7 @@ re_queue_tail(queue_t que, queue_entry_t elt) queue_entry_t _tmp_entry = dequeue_head((head)); \ type *_tmp_element = (type*) NULL; \ if (_tmp_entry != (queue_entry_t) NULL) \ - _tmp_element = qe_element(_tmp_entry, type, field); \ + _tmp_element = qe_element(_tmp_entry, type, field); \ _tmp_element; \ }) @@ -536,7 +543,7 @@ re_queue_tail(queue_t que, queue_entry_t elt) queue_entry_t _tmp_entry = dequeue_tail((head)); \ type *_tmp_element = (type*) NULL; \ if (_tmp_entry != (queue_entry_t) NULL) \ - _tmp_element = qe_element(_tmp_entry, type, field); \ + _tmp_element = qe_element(_tmp_entry, type, field); \ _tmp_element; \ }) @@ -545,7 +552,7 @@ re_queue_tail(queue_t que, queue_entry_t elt) queue_entry_t _tmp_entry = queue_first((head)); \ type *_tmp_element = (type*) NULL; \ if (_tmp_entry != (queue_entry_t) head) \ - _tmp_element = qe_element(_tmp_entry, type, field); \ + _tmp_element = qe_element(_tmp_entry, type, field); \ _tmp_element; \ }) @@ -554,12 +561,38 @@ re_queue_tail(queue_t que, queue_entry_t elt) queue_entry_t _tmp_entry = queue_last((head)); \ type *_tmp_element = (type*) NULL; \ if (_tmp_entry != (queue_entry_t) head) \ - _tmp_element = qe_element(_tmp_entry, type, field); \ + _tmp_element = qe_element(_tmp_entry, type, field); \ + _tmp_element; \ +}) + +/* Peek at the next element, or return NULL if the next element is head (indicating queue_end) */ +#define qe_queue_next(head, element, type, field) ({ \ + queue_entry_t _tmp_entry = queue_next(&(element)->field); \ + type *_tmp_element = (type*) NULL; \ + if (_tmp_entry != (queue_entry_t) head) \ + _tmp_element = qe_element(_tmp_entry, type, field); \ + _tmp_element; \ +}) + +/* Peek at the prev element, or return NULL if the prev element is head (indicating queue_end) */ +#define qe_queue_prev(head, element, type, field) ({ \ + queue_entry_t _tmp_entry = queue_prev(&(element)->field); \ + type *_tmp_element = (type*) NULL; \ + if (_tmp_entry != (queue_entry_t) head) \ + _tmp_element = qe_element(_tmp_entry, type, field); \ _tmp_element; \ }) #endif /* XNU_KERNEL_PRIVATE */ +/* + * Macro: QUEUE_HEAD_INITIALIZER() + * Function: + * Static queue head initializer + */ +#define QUEUE_HEAD_INITIALIZER(name) \ + { &name, &name } + /* * Macro: queue_init * Function: @@ -568,8 +601,8 @@ re_queue_tail(queue_t que, queue_entry_t elt) * void queue_init(q) * queue_t q; \* MODIFIED *\ */ -#define queue_init(q) \ -MACRO_BEGIN \ +#define queue_init(q) \ +MACRO_BEGIN \ (q)->next = (q);\ (q)->prev = (q);\ MACRO_END @@ -604,7 +637,7 @@ MACRO_END * queue_entry_t queue_first(q) * queue_t q; \* IN *\ */ -#define queue_first(q) ((q)->next) +#define queue_first(q) ((q)->next) /* * Macro: queue_next @@ -614,7 +647,7 @@ MACRO_END * queue_entry_t queue_next(qc) * queue_t qc; */ -#define queue_next(qc) ((qc)->next) +#define queue_next(qc) ((qc)->next) /* * Macro: queue_last @@ -624,7 +657,7 @@ MACRO_END * queue_entry_t queue_last(q) * queue_t q; \* IN *\ */ -#define queue_last(q) ((q)->prev) +#define queue_last(q) ((q)->prev) /* * Macro: queue_prev @@ -634,7 +667,7 @@ MACRO_END * queue_entry_t queue_prev(qc) * queue_t qc; */ -#define queue_prev(qc) ((qc)->prev) +#define queue_prev(qc) ((qc)->prev) /* * Macro: queue_end @@ -646,7 +679,7 @@ MACRO_END * queue_t q; * queue_entry_t qe; */ -#define queue_end(q, qe) ((q) == (qe)) +#define queue_end(q, qe) ((q) == (qe)) /* * Macro: queue_empty @@ -656,7 +689,7 @@ MACRO_END * boolean_t queue_empty(q) * queue_t q; */ -#define queue_empty(q) queue_end((q), queue_first(q)) +#define queue_empty(q) queue_end((q), queue_first(q)) /* * Function: movqueue @@ -676,7 +709,7 @@ MACRO_END static __inline__ void movqueue(queue_t _old, queue_t _new) { - queue_entry_t next_elt, prev_elt; + queue_entry_t next_elt, prev_elt; __QUEUE_ELT_VALIDATE((queue_entry_t)_old); @@ -719,22 +752,32 @@ movqueue(queue_t _old, queue_t _new) * is the chain field in (*) * Note: * This should only be used with Method 2 queue iteration (element chains) + * + * We insert a compiler barrier after setting the fields in the element + * to ensure that the element is updated before being added to the queue, + * which is especially important because stackshot, which operates from + * debugger context, iterates several queues that use this macro (the tasks + * lists and threads lists) without locks. Without this barrier, the + * compiler may re-order the instructions for this macro in a way that + * could cause stackshot to trip over an inconsistent queue during + * iteration. */ -#define queue_enter(head, elt, type, field) \ -MACRO_BEGIN \ - queue_entry_t __prev; \ - \ - __prev = (head)->prev; \ - if ((head) == __prev) { \ - (head)->next = (queue_entry_t) (elt); \ - } \ - else { \ - ((type)(void *)__prev)->field.next = \ - (queue_entry_t)(elt); \ - } \ - (elt)->field.prev = __prev; \ - (elt)->field.next = head; \ - (head)->prev = (queue_entry_t) elt; \ +#define queue_enter(head, elt, type, field) \ +MACRO_BEGIN \ + queue_entry_t __prev; \ + \ + __prev = (head)->prev; \ + (elt)->field.prev = __prev; \ + (elt)->field.next = head; \ + __compiler_barrier(); \ + if ((head) == __prev) { \ + (head)->next = (queue_entry_t) (elt); \ + } \ + else { \ + ((type)(void *)__prev)->field.next = \ + (queue_entry_t)(elt); \ + } \ + (head)->prev = (queue_entry_t) elt; \ MACRO_END /* @@ -750,21 +793,21 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_enter_first(head, elt, type, field) \ -MACRO_BEGIN \ - queue_entry_t __next; \ - \ - __next = (head)->next; \ - if ((head) == __next) { \ - (head)->prev = (queue_entry_t) (elt); \ - } \ - else { \ - ((type)(void *)__next)->field.prev = \ - (queue_entry_t)(elt); \ - } \ - (elt)->field.next = __next; \ - (elt)->field.prev = head; \ - (head)->next = (queue_entry_t) elt; \ +#define queue_enter_first(head, elt, type, field) \ +MACRO_BEGIN \ + queue_entry_t __next; \ + \ + __next = (head)->next; \ + if ((head) == __next) { \ + (head)->prev = (queue_entry_t) (elt); \ + } \ + else { \ + ((type)(void *)__next)->field.prev = \ + (queue_entry_t)(elt); \ + } \ + (elt)->field.next = __next; \ + (elt)->field.prev = head; \ + (head)->next = (queue_entry_t) elt; \ MACRO_END /* @@ -781,34 +824,34 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_insert_before(head, elt, cur, type, field) \ -MACRO_BEGIN \ - queue_entry_t __prev; \ - \ - if ((head) == (queue_entry_t)(cur)) { \ - (elt)->field.next = (head); \ - if ((head)->next == (head)) { /* only element */ \ - (elt)->field.prev = (head); \ - (head)->next = (queue_entry_t)(elt); \ - } else { /* last element */ \ - __prev = (elt)->field.prev = (head)->prev; \ - ((type)(void *)__prev)->field.next = \ - (queue_entry_t)(elt); \ - } \ - (head)->prev = (queue_entry_t)(elt); \ - } else { \ - (elt)->field.next = (queue_entry_t)(cur); \ - if ((head)->next == (queue_entry_t)(cur)) { \ - /* first element */ \ - (elt)->field.prev = (head); \ - (head)->next = (queue_entry_t)(elt); \ - } else { /* middle element */ \ - __prev = (elt)->field.prev = (cur)->field.prev; \ - ((type)(void *)__prev)->field.next = \ - (queue_entry_t)(elt); \ - } \ - (cur)->field.prev = (queue_entry_t)(elt); \ - } \ +#define queue_insert_before(head, elt, cur, type, field) \ +MACRO_BEGIN \ + queue_entry_t __prev; \ + \ + if ((head) == (queue_entry_t)(cur)) { \ + (elt)->field.next = (head); \ + if ((head)->next == (head)) { /* only element */ \ + (elt)->field.prev = (head); \ + (head)->next = (queue_entry_t)(elt); \ + } else { /* last element */ \ + __prev = (elt)->field.prev = (head)->prev; \ + ((type)(void *)__prev)->field.next = \ + (queue_entry_t)(elt); \ + } \ + (head)->prev = (queue_entry_t)(elt); \ + } else { \ + (elt)->field.next = (queue_entry_t)(cur); \ + if ((head)->next == (queue_entry_t)(cur)) { \ + /* first element */ \ + (elt)->field.prev = (head); \ + (head)->next = (queue_entry_t)(elt); \ + } else { /* middle element */ \ + __prev = (elt)->field.prev = (cur)->field.prev; \ + ((type)(void *)__prev)->field.next = \ + (queue_entry_t)(elt); \ + } \ + (cur)->field.prev = (queue_entry_t)(elt); \ + } \ MACRO_END /* @@ -825,34 +868,34 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_insert_after(head, elt, cur, type, field) \ -MACRO_BEGIN \ - queue_entry_t __next; \ - \ - if ((head) == (queue_entry_t)(cur)) { \ - (elt)->field.prev = (head); \ - if ((head)->next == (head)) { /* only element */ \ - (elt)->field.next = (head); \ - (head)->prev = (queue_entry_t)(elt); \ - } else { /* first element */ \ - __next = (elt)->field.next = (head)->next; \ - ((type)(void *)__next)->field.prev = \ - (queue_entry_t)(elt); \ - } \ - (head)->next = (queue_entry_t)(elt); \ - } else { \ - (elt)->field.prev = (queue_entry_t)(cur); \ - if ((head)->prev == (queue_entry_t)(cur)) { \ - /* last element */ \ - (elt)->field.next = (head); \ - (head)->prev = (queue_entry_t)(elt); \ - } else { /* middle element */ \ - __next = (elt)->field.next = (cur)->field.next; \ - ((type)(void *)__next)->field.prev = \ - (queue_entry_t)(elt); \ - } \ - (cur)->field.next = (queue_entry_t)(elt); \ - } \ +#define queue_insert_after(head, elt, cur, type, field) \ +MACRO_BEGIN \ + queue_entry_t __next; \ + \ + if ((head) == (queue_entry_t)(cur)) { \ + (elt)->field.prev = (head); \ + if ((head)->next == (head)) { /* only element */ \ + (elt)->field.next = (head); \ + (head)->prev = (queue_entry_t)(elt); \ + } else { /* first element */ \ + __next = (elt)->field.next = (head)->next; \ + ((type)(void *)__next)->field.prev = \ + (queue_entry_t)(elt); \ + } \ + (head)->next = (queue_entry_t)(elt); \ + } else { \ + (elt)->field.prev = (queue_entry_t)(cur); \ + if ((head)->prev == (queue_entry_t)(cur)) { \ + /* last element */ \ + (elt)->field.next = (head); \ + (head)->prev = (queue_entry_t)(elt); \ + } else { /* middle element */ \ + __next = (elt)->field.next = (cur)->field.next; \ + ((type)(void *)__next)->field.prev = \ + (queue_entry_t)(elt); \ + } \ + (cur)->field.next = (queue_entry_t)(elt); \ + } \ MACRO_END /* @@ -863,8 +906,8 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_field(head, thing, type, field) \ - (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field) +#define queue_field(head, thing, type, field) \ + (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field) /* * Macro: queue_remove @@ -876,25 +919,25 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_remove(head, elt, type, field) \ -MACRO_BEGIN \ - queue_entry_t __next, __prev; \ - \ - __next = (elt)->field.next; \ - __prev = (elt)->field.prev; \ - \ - if ((head) == __next) \ - (head)->prev = __prev; \ - else \ - ((type)(void *)__next)->field.prev = __prev; \ - \ - if ((head) == __prev) \ - (head)->next = __next; \ - else \ - ((type)(void *)__prev)->field.next = __next; \ - \ - (elt)->field.next = NULL; \ - (elt)->field.prev = NULL; \ +#define queue_remove(head, elt, type, field) \ +MACRO_BEGIN \ + queue_entry_t __next, __prev; \ + \ + __next = (elt)->field.next; \ + __prev = (elt)->field.prev; \ + \ + if ((head) == __next) \ + (head)->prev = __prev; \ + else \ + ((type)(void *)__next)->field.prev = __prev; \ + \ + if ((head) == __prev) \ + (head)->next = __next; \ + else \ + ((type)(void *)__prev)->field.next = __next; \ + \ + (elt)->field.next = NULL; \ + (elt)->field.prev = NULL; \ MACRO_END /* @@ -908,21 +951,21 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_remove_first(head, entry, type, field) \ -MACRO_BEGIN \ - queue_entry_t __next; \ - \ - (entry) = (type)(void *) ((head)->next); \ - __next = (entry)->field.next; \ - \ - if ((head) == __next) \ - (head)->prev = (head); \ - else \ - ((type)(void *)(__next))->field.prev = (head); \ - (head)->next = __next; \ - \ - (entry)->field.next = NULL; \ - (entry)->field.prev = NULL; \ +#define queue_remove_first(head, entry, type, field) \ +MACRO_BEGIN \ + queue_entry_t __next; \ + \ + (entry) = (type)(void *) ((head)->next); \ + __next = (entry)->field.next; \ + \ + if ((head) == __next) \ + (head)->prev = (head); \ + else \ + ((type)(void *)(__next))->field.prev = (head); \ + (head)->next = __next; \ + \ + (entry)->field.next = NULL; \ + (entry)->field.prev = NULL; \ MACRO_END /* @@ -936,21 +979,21 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_remove_last(head, entry, type, field) \ -MACRO_BEGIN \ - queue_entry_t __prev; \ - \ - (entry) = (type)(void *) ((head)->prev); \ - __prev = (entry)->field.prev; \ - \ - if ((head) == __prev) \ - (head)->next = (head); \ - else \ - ((type)(void *)(__prev))->field.next = (head); \ - (head)->prev = __prev; \ - \ - (entry)->field.next = NULL; \ - (entry)->field.prev = NULL; \ +#define queue_remove_last(head, entry, type, field) \ +MACRO_BEGIN \ + queue_entry_t __prev; \ + \ + (entry) = (type)(void *) ((head)->prev); \ + __prev = (entry)->field.prev; \ + \ + if ((head) == __prev) \ + (head)->next = (head); \ + else \ + ((type)(void *)(__prev))->field.next = (head); \ + (head)->prev = __prev; \ + \ + (entry)->field.next = NULL; \ + (entry)->field.prev = NULL; \ MACRO_END /* @@ -958,11 +1001,11 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_assign(to, from, type, field) \ -MACRO_BEGIN \ - ((type)(void *)((from)->prev))->field.next = (to); \ - ((type)(void *)((from)->next))->field.prev = (to); \ - *to = *from; \ +#define queue_assign(to, from, type, field) \ +MACRO_BEGIN \ + ((type)(void *)((from)->prev))->field.next = (to); \ + ((type)(void *)((from)->next))->field.prev = (to); \ + *to = *from; \ MACRO_END /* @@ -978,17 +1021,17 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_new_head(old, new, type, field) \ -MACRO_BEGIN \ - if (!queue_empty(old)) { \ - *(new) = *(old); \ - ((type)(void *)((new)->next))->field.prev = \ - (new); \ - ((type)(void *)((new)->prev))->field.next = \ - (new); \ - } else { \ - queue_init(new); \ - } \ +#define queue_new_head(old, new, type, field) \ +MACRO_BEGIN \ + if (!queue_empty(old)) { \ + *(new) = *(old); \ + ((type)(void *)((new)->next))->field.prev = \ + (new); \ + ((type)(void *)((new)->prev))->field.next = \ + (new); \ + } else { \ + queue_init(new); \ + } \ MACRO_END /* @@ -1006,78 +1049,12 @@ MACRO_END * Note: * This should only be used with Method 2 queue iteration (element chains) */ -#define queue_iterate(head, elt, type, field) \ - for ((elt) = (type)(void *) queue_first(head); \ - !queue_end((head), (queue_entry_t)(elt)); \ +#define queue_iterate(head, elt, type, field) \ + for ((elt) = (type)(void *) queue_first(head); \ + !queue_end((head), (queue_entry_t)(elt)); \ (elt) = (type)(void *) queue_next(&(elt)->field)) -#ifdef MACH_KERNEL_PRIVATE - -#include - -/*----------------------------------------------------------------*/ -/* - * Define macros for queues with locks. - */ -struct mpqueue_head { - struct queue_entry head; /* header for queue */ - uint64_t earliest_soft_deadline; - uint64_t count; - lck_mtx_t lock_data; -#if defined(__i386__) || defined(__x86_64__) - lck_mtx_ext_t lock_data_ext; -#endif -}; - -typedef struct mpqueue_head mpqueue_head_t; - -#define round_mpq(size) (size) - - -#if defined(__i386__) || defined(__x86_64__) - -#define mpqueue_init(q, lck_grp, lck_attr) \ -MACRO_BEGIN \ - queue_init(&(q)->head); \ - lck_mtx_init_ext(&(q)->lock_data, \ - &(q)->lock_data_ext, \ - lck_grp, \ - lck_attr); \ - (q)->earliest_soft_deadline = UINT64_MAX; \ - (q)->count = 0; \ -MACRO_END - -#else - -#define mpqueue_init(q, lck_grp, lck_attr) \ -MACRO_BEGIN \ - queue_init(&(q)->head); \ - lck_mtx_init(&(q)->lock_data, \ - lck_grp, \ - lck_attr); \ -MACRO_END -#endif - - -#define mpenqueue_tail(q, elt) \ -MACRO_BEGIN \ - lck_mtx_lock_spin_always(&(q)->lock_data); \ - enqueue_tail(&(q)->head, elt); \ - lck_mtx_unlock_always(&(q)->lock_data); \ -MACRO_END - -#define mpdequeue_head(q, elt) \ -MACRO_BEGIN \ - lck_mtx_lock_spin_always(&(q)->lock_data); \ - if (queue_empty(&(q)->head)) \ - *(elt) = 0; \ - else \ - *(elt) = dequeue_head(&(q)->head); \ - lck_mtx_unlock_always(&(q)->lock_data); \ -MACRO_END - -#endif /* MACH_KERNEL_PRIVATE */ __END_DECLS -#endif /* _KERN_QUEUE_H_ */ +#endif /* _KERN_QUEUE_H_ */