X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/1c79356b52d46aa6b508fb032f5ae709b1f2897b..3903760236c30e3b5ace7a4eefac3a269d68957c:/osfmk/kern/queue.h diff --git a/osfmk/kern/queue.h b/osfmk/kern/queue.h index 541eef456..dc99d000f 100644 --- a/osfmk/kern/queue.h +++ b/osfmk/kern/queue.h @@ -1,23 +1,29 @@ /* - * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2000-2009 Apple Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * - * The contents of this file constitute Original Code as defined in and - * are subject to the Apple Public Source License Version 1.1 (the - * "License"). You may not use this file except in compliance with the - * License. Please obtain a copy of the License at - * http://www.apple.com/publicsource and read it before using this file. + * 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 + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * 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. * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * 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, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the - * License for the specific language governing rights and limitations - * under the License. + * 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_LICENSE_HEADER_END@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ /* * @OSF_COPYRIGHT@ @@ -61,26 +67,126 @@ #ifndef _KERN_QUEUE_H_ #define _KERN_QUEUE_H_ -#include +#include #include +#include + +__BEGIN_DECLS + /* - * Queue of abstract objects. Queue is maintained - * within that object. + * Queue Management APIs + * + * There are currently two subtly different methods of maintining + * a queue of objects. Both APIs are contained in this file, and + * unfortunately overlap. + * (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; + * + * 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. * - * Supports fast removal from within the queue. + * 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. * - * How to declare a queue of elements of type "foo_t": - * In the "*foo_t" type, you must have a field of - * type "queue_chain_t" to hold together this queue. - * There may be more than one chain through a - * "foo_t", for use by different queues. + * ++ 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 * - * Declare the queue as a "queue_t" type. + * [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 * - * Elements of the queue (of type "foo_t", that is) - * are referred to by reference, and cast to type - * "queue_entry_t" within this module. + * 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 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 + * + * [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) */ /* @@ -90,6 +196,7 @@ struct queue_entry { struct queue_entry *next; /* next element */ struct queue_entry *prev; /* previous element */ + }; typedef struct queue_entry *queue_t; @@ -100,56 +207,55 @@ typedef struct queue_entry *queue_entry_t; /* * enqueue puts "elt" on the "queue". * dequeue returns the first element in the "queue". - * remqueue removes the specified "elt" from the specified "queue". + * remqueue removes the specified "elt" from its queue. */ #define enqueue(queue,elt) enqueue_tail(queue, elt) #define dequeue(queue) dequeue_head(queue) -#if !defined(__GNUC__) - -/* Enqueue element to head of queue */ -extern void enqueue_head( - queue_t que, - queue_entry_t elt); - -/* Enqueue element to tail of queue */ -extern void enqueue_tail( - queue_t que, - queue_entry_t elt); - -/* Dequeue element from head of queue */ -extern queue_entry_t dequeue_head( - queue_t que); - -/* Dequeue element from tail of queue */ -extern queue_entry_t dequeue_tail( - queue_t que); - -/* Dequeue element */ -extern void remqueue( - queue_t que, - queue_entry_t elt); - -/* Enqueue element after a particular elem */ -extern void insque( - queue_entry_t entry, - queue_entry_t pred); - -/* Dequeue element */ -extern int remque( - queue_entry_t elt); +#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)) { + 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)) { + 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); + } +} +static inline void __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) { + (elt)->next = (queue_entry_t) 0; + (elt)->prev = (queue_entry_t) 0; +} #else +#define __QUEUE_ELT_VALIDATE(elt) do { } while (0) +#define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0) +#endif /* !XNU_KERNEL_PRIVATE */ static __inline__ void enqueue_head( queue_t que, queue_entry_t elt) { - elt->next = que->next; + queue_entry_t old_head; + + __QUEUE_ELT_VALIDATE((queue_entry_t)que); + old_head = que->next; + elt->next = old_head; elt->prev = que; - elt->next->prev = elt; + old_head->prev = elt; que->next = elt; } @@ -158,9 +264,13 @@ enqueue_tail( queue_t que, queue_entry_t elt) { + queue_entry_t old_tail; + + __QUEUE_ELT_VALIDATE((queue_entry_t)que); + old_tail = que->prev; elt->next = que; - elt->prev = que->prev; - elt->prev->next = elt; + elt->prev = old_tail; + old_tail->next = elt; que->prev = elt; } @@ -168,12 +278,16 @@ static __inline__ queue_entry_t dequeue_head( queue_t que) { - register queue_entry_t elt = (queue_entry_t) 0; + queue_entry_t elt = (queue_entry_t) 0; + queue_entry_t new_head; if (que->next != que) { elt = que->next; - elt->next->prev = que; - que->next = elt->next; + __QUEUE_ELT_VALIDATE(elt); + new_head = elt->next; /* new_head may point to que if elt was the only element */ + new_head->prev = que; + que->next = new_head; + __DEQUEUE_ELT_CLEANUP(elt); } return (elt); @@ -183,12 +297,16 @@ static __inline__ queue_entry_t dequeue_tail( queue_t que) { - register queue_entry_t elt = (queue_entry_t) 0; + queue_entry_t elt = (queue_entry_t) 0; + queue_entry_t new_tail; if (que->prev != que) { elt = que->prev; - elt->prev->next = que; - que->prev = elt->prev; + __QUEUE_ELT_VALIDATE(elt); + new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */ + new_tail->next = que; + que->prev = new_tail; + __DEQUEUE_ELT_CLEANUP(elt); } return (elt); @@ -196,11 +314,16 @@ dequeue_tail( static __inline__ void remqueue( - queue_t que, queue_entry_t elt) { - elt->next->prev = elt->prev; - elt->prev->next = elt->next; + 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); } static __inline__ void @@ -208,23 +331,234 @@ insque( queue_entry_t entry, queue_entry_t pred) { - entry->next = pred->next; + queue_entry_t successor; + + __QUEUE_ELT_VALIDATE(pred); + successor = pred->next; + entry->next = successor; entry->prev = pred; - (pred->next)->prev = entry; + successor->prev = entry; pred->next = entry; } -static __inline__ integer_t +static __inline__ void remque( - register queue_entry_t elt) + 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); +} + +/* + * Function: re_queue_head + * Parameters: + * queue_t que : queue onto which elt will be pre-pended + * queue_entry_t elt : element to re-queue + * Description: + * Remove elt from its current queue and put it onto the + * head of a new queue + * Note: + * This should only be used with Method 1 queue iteration (linkage chains) + */ +static __inline__ void +re_queue_head(queue_t que, queue_entry_t elt) +{ + queue_entry_t n_elt, p_elt; + + __QUEUE_ELT_VALIDATE(elt); + __QUEUE_ELT_VALIDATE((queue_entry_t)que); + + /* remqueue */ + n_elt = elt->next; + p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ + n_elt->prev = p_elt; + p_elt->next = n_elt; + + /* enqueue_head */ + n_elt = que->next; + elt->next = n_elt; + elt->prev = que; + n_elt->prev = elt; + que->next = elt; +} + +/* + * Function: re_queue_tail + * Parameters: + * queue_t que : queue onto which elt will be appended + * queue_entry_t elt : element to re-queue + * Description: + * Remove elt from its current queue and put it onto the + * end of a new queue + * Note: + * This should only be used with Method 1 queue iteration (linkage chains) + */ +static __inline__ void +re_queue_tail(queue_t que, queue_entry_t elt) { - (elt->next)->prev = elt->prev; - (elt->prev)->next = elt->next; + queue_entry_t n_elt, p_elt; - return((integer_t)elt); + __QUEUE_ELT_VALIDATE(elt); + __QUEUE_ELT_VALIDATE((queue_entry_t)que); + + /* remqueue */ + n_elt = elt->next; + p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ + n_elt->prev = p_elt; + p_elt->next = n_elt; + + /* enqueue_tail */ + p_elt = que->prev; + elt->next = que; + elt->prev = p_elt; + p_elt->next = elt; + que->prev = elt; } -#endif /* defined(__GNUC__) */ +/* + * Macro: qe_element + * Function: + * Convert a queue_entry_t to a queue element pointer. + * Get a pointer to the user-defined element containing + * a given queue_entry_t + * Header: + * * qe_element(queue_entry_t qe, , field) + * qe - queue entry to convert + * - what's in the queue (e.g., struct some_data) + * - is the chain field in + * Note: + * Do not use pointer types for + */ +#define qe_element(qe, type, field) \ + ((type *)((void *)((char *)(qe) - __offsetof(type, field)))) + +/* + * Macro: qe_foreach + * Function: + * Iterate over each queue_entry_t structure. + * Generates a 'for' loop, setting 'qe' to + * each queue_entry_t in the queue. + * Header: + * qe_foreach(queue_entry_t qe, queue_t head) + * qe - iteration variable + * head - pointer to queue_head_t (head of queue) + * Note: + * This should only be used with Method 1 queue iteration (linkage chains) + */ +#define qe_foreach(qe, head) \ + for (qe = (head)->next; qe != (head); qe = (qe)->next) + +/* + * Macro: qe_foreach_safe + * Function: + * Safely iterate over each queue_entry_t structure. + * + * Use this iterator macro if you plan to remove the + * queue_entry_t, qe, from the queue during the + * iteration. + * Header: + * qe_foreach_safe(queue_entry_t qe, queue_t head) + * qe - iteration variable + * head - pointer to queue_head_t (head of queue) + * Note: + * This should only be used with Method 1 queue iteration (linkage chains) + */ +#define qe_foreach_safe(qe, head) \ + for (queue_entry_t _ne = ((head)->next)->next, \ + __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \ + qe != (head); \ + qe = _ne, _ne = (qe)->next) + +/* + * Macro: qe_foreach_element + * Function: + * Iterate over each _element_ in a queue + * where each queue_entry_t points to another + * queue_entry_t, i.e., managed by the [de|en]queue_head/ + * [de|en]queue_tail / remqueue / etc. function. + * Header: + * qe_foreach_element( *elt, queue_t head, ) + * elt - iteration variable + * - what's in the queue (e.g., struct some_data) + * - is the chain field in + * Note: + * This should only be used with Method 1 queue iteration (linkage chains) + */ +#define qe_foreach_element(elt, head, field) \ + for (elt = qe_element((head)->next, typeof(*(elt)), field); \ + &((elt)->field) != (head); \ + elt = qe_element((elt)->field.next, typeof(*(elt)), field)) + +/* + * Macro: qe_foreach_element_safe + * Function: + * Safely iterate over each _element_ in a queue + * where each queue_entry_t points to another + * queue_entry_t, i.e., managed by the [de|en]queue_head/ + * [de|en]queue_tail / remqueue / etc. function. + * + * Use this iterator macro if you plan to remove the + * element, elt, from the queue during the iteration. + * Header: + * qe_foreach_element_safe( *elt, queue_t head, ) + * elt - iteration variable + * - what's in the queue (e.g., struct some_data) + * - is the chain field in + * Note: + * This should only be used with Method 1 queue iteration (linkage chains) + */ +#define qe_foreach_element_safe(elt, head, field) \ + for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \ + *__ ## elt ## _unused_shadow __unused = \ + (elt = qe_element((head)->next, typeof(*(elt)), field)); \ + &((elt)->field) != (head); \ + elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \ + +#ifdef XNU_KERNEL_PRIVATE + +/* Dequeue an element from head, or return NULL if the queue is empty */ +#define qe_dequeue_head(head, type, field) ({ \ + 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; \ +}) + +/* Dequeue an element from tail, or return NULL if the queue is empty */ +#define qe_dequeue_tail(head, type, field) ({ \ + 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; \ +}) + +/* Peek at the first element, or return NULL if the queue is empty */ +#define qe_queue_first(head, type, field) ({ \ + 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; \ +}) + +/* Peek at the last element, or return NULL if the queue is empty */ +#define qe_queue_last(head, type, field) ({ \ + 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; \ +}) + +#endif /* XNU_KERNEL_PRIVATE */ /* * Macro: queue_init @@ -240,6 +574,28 @@ MACRO_BEGIN \ (q)->prev = (q);\ MACRO_END +/* + * Macro: queue_head_init + * Function: + * Initialize the given queue head + * Header: + * void queue_head_init(q) + * queue_head_t q; \* MODIFIED *\ + */ +#define queue_head_init(q) \ + queue_init(&(q)) + +/* + * Macro: queue_chain_init + * Function: + * Initialize the given queue chain element + * Header: + * void queue_chain_init(q) + * queue_chain_t q; \* MODIFIED *\ + */ +#define queue_chain_init(q) \ + queue_init(&(q)) + /* * Macro: queue_first * Function: @@ -302,6 +658,47 @@ MACRO_END */ #define queue_empty(q) queue_end((q), queue_first(q)) +/* + * Function: movqueue + * Parameters: + * queue_t _old : head of a queue whose items will be moved + * queue_t _new : new queue head onto which items will be moved + * Description: + * Rebase queue items in _old onto _new then re-initialize + * the _old object to an empty queue. + * Equivalent to the queue_new_head Method 2 macro + * Note: + * Similar to the queue_new_head macro, this macros is intented + * to function as an initializer method for '_new' and thus may + * leak any list items that happen to be on the '_new' list. + * This should only be used with Method 1 queue iteration (linkage chains) + */ +static __inline__ void +movqueue(queue_t _old, queue_t _new) +{ + queue_entry_t next_elt, prev_elt; + + __QUEUE_ELT_VALIDATE((queue_entry_t)_old); + + if (queue_empty(_old)) { + queue_init(_new); + return; + } + + /* + * move the queue at _old to _new + * and re-initialize _old + */ + next_elt = _old->next; + prev_elt = _old->prev; + + _new->next = next_elt; + _new->prev = prev_elt; + next_elt->prev = _new; + prev_elt->next = _new; + + queue_init(_old); +} /*----------------------------------------------------------------*/ /* @@ -320,19 +717,22 @@ MACRO_END * elt; * is what's in our queue * is the chain field in (*) + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_enter(head, elt, type, field) \ MACRO_BEGIN \ - register queue_entry_t prev; \ + queue_entry_t __prev; \ \ - prev = (head)->prev; \ - if ((head) == prev) { \ + __prev = (head)->prev; \ + if ((head) == __prev) { \ (head)->next = (queue_entry_t) (elt); \ } \ else { \ - ((type)prev)->field.next = (queue_entry_t)(elt);\ + ((type)(void *)__prev)->field.next = \ + (queue_entry_t)(elt); \ } \ - (elt)->field.prev = prev; \ + (elt)->field.prev = __prev; \ (elt)->field.next = head; \ (head)->prev = (queue_entry_t) elt; \ MACRO_END @@ -347,19 +747,22 @@ MACRO_END * elt; * is what's in our queue * is the chain field in (*) + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_enter_first(head, elt, type, field) \ MACRO_BEGIN \ - register queue_entry_t next; \ + queue_entry_t __next; \ \ - next = (head)->next; \ - if ((head) == next) { \ + __next = (head)->next; \ + if ((head) == __next) { \ (head)->prev = (queue_entry_t) (elt); \ } \ else { \ - ((type)next)->field.prev = (queue_entry_t)(elt);\ + ((type)(void *)__next)->field.prev = \ + (queue_entry_t)(elt); \ } \ - (elt)->field.next = next; \ + (elt)->field.next = __next; \ (elt)->field.prev = head; \ (head)->next = (queue_entry_t) elt; \ MACRO_END @@ -375,10 +778,12 @@ MACRO_END * cur; * is what's in our queue * is the chain field in (*) + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_insert_before(head, elt, cur, type, field) \ MACRO_BEGIN \ - register queue_entry_t prev; \ + queue_entry_t __prev; \ \ if ((head) == (queue_entry_t)(cur)) { \ (elt)->field.next = (head); \ @@ -386,8 +791,9 @@ MACRO_BEGIN \ (elt)->field.prev = (head); \ (head)->next = (queue_entry_t)(elt); \ } else { /* last element */ \ - prev = (elt)->field.prev = (head)->prev; \ - ((type)prev)->field.next = (queue_entry_t)(elt);\ + __prev = (elt)->field.prev = (head)->prev; \ + ((type)(void *)__prev)->field.next = \ + (queue_entry_t)(elt); \ } \ (head)->prev = (queue_entry_t)(elt); \ } else { \ @@ -397,8 +803,9 @@ MACRO_BEGIN \ (elt)->field.prev = (head); \ (head)->next = (queue_entry_t)(elt); \ } else { /* middle element */ \ - prev = (elt)->field.prev = (cur)->field.prev; \ - ((type)prev)->field.next = (queue_entry_t)(elt);\ + __prev = (elt)->field.prev = (cur)->field.prev; \ + ((type)(void *)__prev)->field.next = \ + (queue_entry_t)(elt); \ } \ (cur)->field.prev = (queue_entry_t)(elt); \ } \ @@ -415,10 +822,12 @@ MACRO_END * cur; * is what's in our queue * is the chain field in (*) + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_insert_after(head, elt, cur, type, field) \ MACRO_BEGIN \ - register queue_entry_t next; \ + queue_entry_t __next; \ \ if ((head) == (queue_entry_t)(cur)) { \ (elt)->field.prev = (head); \ @@ -426,8 +835,9 @@ MACRO_BEGIN \ (elt)->field.next = (head); \ (head)->prev = (queue_entry_t)(elt); \ } else { /* first element */ \ - next = (elt)->field.next = (head)->next; \ - ((type)next)->field.prev = (queue_entry_t)(elt);\ + __next = (elt)->field.next = (head)->next; \ + ((type)(void *)__next)->field.prev = \ + (queue_entry_t)(elt); \ } \ (head)->next = (queue_entry_t)(elt); \ } else { \ @@ -437,8 +847,9 @@ MACRO_BEGIN \ (elt)->field.next = (head); \ (head)->prev = (queue_entry_t)(elt); \ } else { /* middle element */ \ - next = (elt)->field.next = (cur)->field.next; \ - ((type)next)->field.prev = (queue_entry_t)(elt);\ + __next = (elt)->field.next = (cur)->field.next; \ + ((type)(void *)__next)->field.prev = \ + (queue_entry_t)(elt); \ } \ (cur)->field.next = (queue_entry_t)(elt); \ } \ @@ -449,9 +860,11 @@ MACRO_END * Function: * Find the queue_chain_t (or queue_t) for the * given element (thing) in the given queue (head) + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_field(head, thing, type, field) \ - (((head) == (thing)) ? (head) : &((type)(thing))->field) + (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field) /* * Macro: queue_remove @@ -460,23 +873,28 @@ MACRO_END * Header: * void queue_remove(q, qe, type, field) * arguments as in queue_enter + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_remove(head, elt, type, field) \ MACRO_BEGIN \ - register queue_entry_t next, prev; \ + queue_entry_t __next, __prev; \ \ - next = (elt)->field.next; \ - prev = (elt)->field.prev; \ + __next = (elt)->field.next; \ + __prev = (elt)->field.prev; \ \ - if ((head) == next) \ - (head)->prev = prev; \ + if ((head) == __next) \ + (head)->prev = __prev; \ else \ - ((type)next)->field.prev = prev; \ + ((type)(void *)__next)->field.prev = __prev; \ \ - if ((head) == prev) \ - (head)->next = next; \ + if ((head) == __prev) \ + (head)->next = __next; \ else \ - ((type)prev)->field.next = next; \ + ((type)(void *)__prev)->field.next = __next; \ + \ + (elt)->field.next = NULL; \ + (elt)->field.prev = NULL; \ MACRO_END /* @@ -487,19 +905,24 @@ MACRO_END * Header: * queue_remove_first(head, entry, type, field) * entry is returned by reference + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_remove_first(head, entry, type, field) \ MACRO_BEGIN \ - register queue_entry_t next; \ + queue_entry_t __next; \ \ - (entry) = (type) ((head)->next); \ - next = (entry)->field.next; \ + (entry) = (type)(void *) ((head)->next); \ + __next = (entry)->field.next; \ \ - if ((head) == next) \ + if ((head) == __next) \ (head)->prev = (head); \ else \ - ((type)(next))->field.prev = (head); \ - (head)->next = next; \ + ((type)(void *)(__next))->field.prev = (head); \ + (head)->next = __next; \ + \ + (entry)->field.next = NULL; \ + (entry)->field.prev = NULL; \ MACRO_END /* @@ -510,28 +933,35 @@ MACRO_END * Header: * queue_remove_last(head, entry, type, field) * entry is returned by reference + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_remove_last(head, entry, type, field) \ MACRO_BEGIN \ - register queue_entry_t prev; \ + queue_entry_t __prev; \ \ - (entry) = (type) ((head)->prev); \ - prev = (entry)->field.prev; \ + (entry) = (type)(void *) ((head)->prev); \ + __prev = (entry)->field.prev; \ \ - if ((head) == prev) \ + if ((head) == __prev) \ (head)->next = (head); \ else \ - ((type)(prev))->field.next = (head); \ - (head)->prev = prev; \ + ((type)(void *)(__prev))->field.next = (head); \ + (head)->prev = __prev; \ + \ + (entry)->field.next = NULL; \ + (entry)->field.prev = NULL; \ MACRO_END /* * Macro: queue_assign + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_assign(to, from, type, field) \ MACRO_BEGIN \ - ((type)((from)->prev))->field.next = (to); \ - ((type)((from)->next))->field.prev = (to); \ + ((type)(void *)((from)->prev))->field.next = (to); \ + ((type)(void *)((from)->next))->field.prev = (to); \ *to = *from; \ MACRO_END @@ -545,13 +975,17 @@ MACRO_END * queue_t new; * is what's in our queue * is the chain field in (*) + * 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(new)) { \ + if (!queue_empty(old)) { \ *(new) = *(old); \ - ((type)((new)->next))->field.prev = (new); \ - ((type)((new)->prev))->field.next = (new); \ + ((type)(void *)((new)->next))->field.prev = \ + (new); \ + ((type)(void *)((new)->prev))->field.next = \ + (new); \ } else { \ queue_init(new); \ } \ @@ -569,50 +1003,81 @@ MACRO_END * elt; * is what's in our queue * is the chain field in (*) + * Note: + * This should only be used with Method 2 queue iteration (element chains) */ #define queue_iterate(head, elt, type, field) \ - for ((elt) = (type) queue_first(head); \ + for ((elt) = (type)(void *) queue_first(head); \ !queue_end((head), (queue_entry_t)(elt)); \ - (elt) = (type) queue_next(&(elt)->field)) + (elt) = (type)(void *) queue_next(&(elt)->field)) +#ifdef MACH_KERNEL_PRIVATE + +#include -#ifdef MACH_KERNEL_PRIVATE /*----------------------------------------------------------------*/ /* * Define macros for queues with locks. */ struct mpqueue_head { struct queue_entry head; /* header for queue */ - decl_simple_lock_data(, lock) /* lock 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) -#define mpqueue_init(q) \ + +#if defined(__i386__) || defined(__x86_64__) + +#define mpqueue_init(q, lck_grp, lck_attr) \ MACRO_BEGIN \ queue_init(&(q)->head); \ - simple_lock_init(&(q)->lock, ETAP_MISC_Q); \ + 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 \ - simple_lock(&(q)->lock); \ + lck_mtx_lock_spin_always(&(q)->lock_data); \ enqueue_tail(&(q)->head, elt); \ - simple_unlock(&(q)->lock); \ + lck_mtx_unlock_always(&(q)->lock_data); \ MACRO_END #define mpdequeue_head(q, elt) \ MACRO_BEGIN \ - simple_lock(&(q)->lock); \ + lck_mtx_lock_spin_always(&(q)->lock_data); \ if (queue_empty(&(q)->head)) \ *(elt) = 0; \ else \ *(elt) = dequeue_head(&(q)->head); \ - simple_unlock(&(q)->lock); \ + lck_mtx_unlock_always(&(q)->lock_data); \ MACRO_END -#endif /* MACH_KERNEL_PRIVATE */ +#endif /* MACH_KERNEL_PRIVATE */ + +__END_DECLS #endif /* _KERN_QUEUE_H_ */