X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/8ad349bb6ed4a0be06e34c92be0d98b92e078db4..HEAD:/osfmk/kern/queue.h diff --git a/osfmk/kern/queue.h b/osfmk/kern/queue.h index 3d32db7a8..ac758f79e 100644 --- a/osfmk/kern/queue.h +++ b/osfmk/kern/queue.h @@ -1,50 +1,48 @@ /* - * Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2000-2009 Apple Inc. All rights reserved. * - * @APPLE_LICENSE_OSREFERENCE_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 - * 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. + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * - * Please obtain a copy of the License at - * http://www.opensource.apple.com/apsl/ 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. * - * 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, QUIET ENJOYMENT OR NON-INFRINGEMENT. - * Please see the License for the specific language governing rights and + * 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, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and * limitations under the License. * - * @APPLE_LICENSE_OSREFERENCE_HEADER_END@ + * @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 @@ -66,29 +64,130 @@ * */ -#ifndef _KERN_QUEUE_H_ -#define _KERN_QUEUE_H_ +#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. + * + * 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 + * + * [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. * - * Supports fast removal from within the queue. + * 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. * - * 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. + * [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 * - * 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. + * 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) */ /* @@ -96,148 +195,403 @@ */ 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". * 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__) - -#include -__BEGIN_DECLS - -/* 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); +#define enqueue(queue, elt) enqueue_tail(queue, elt) +#define dequeue(queue) dequeue_head(queue) -/* 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); +#ifdef XNU_KERNEL_PRIVATE +#include +static inline void +__QUEUE_ELT_VALIDATE(queue_entry_t elt) +{ + queue_entry_t elt_next, elt_prev; -/* Enqueue element after a particular elem */ -extern void insque( - queue_entry_t entry, - queue_entry_t pred); + if (__improbable(elt == (queue_entry_t)NULL)) { + panic("Invalid queue element %p", elt); + } -/* Dequeue element */ -extern int remque( - queue_entry_t elt); + elt_next = elt->next; + elt_prev = elt->prev; -__END_DECLS + 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); + } +} -#else /* !__GNUC__ */ +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) +#define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0) +#endif /* !XNU_KERNEL_PRIVATE */ static __inline__ void enqueue_head( - queue_t que, - queue_entry_t elt) + 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; } 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_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; } static __inline__ queue_entry_t dequeue_head( - queue_t que) + queue_t que) { - register queue_entry_t elt = (queue_entry_t) 0; + queue_entry_t elt = (queue_entry_t)NULL; + 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); + return elt; } static __inline__ queue_entry_t dequeue_tail( - queue_t que) + queue_t que) { - register queue_entry_t elt = (queue_entry_t) 0; + queue_entry_t elt = (queue_entry_t)NULL; + 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); + return elt; } static __inline__ void remqueue( - __unused queue_t que, - queue_entry_t elt) + 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 insque( - queue_entry_t entry, - queue_entry_t pred) + 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) +{ + remqueue(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; + + __QUEUE_ELT_VALIDATE(elt); + __QUEUE_ELT_VALIDATE((queue_entry_t)que); - return((integer_t)elt); + /* 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 /* !__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) __container_of(qe, 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; \ +}) + +/* 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 @@ -247,12 +601,34 @@ remque( * 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 +/* + * 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: @@ -261,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 @@ -271,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 @@ -281,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 @@ -291,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 @@ -303,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 @@ -313,8 +689,49 @@ 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 + * 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); +} /*----------------------------------------------------------------*/ /* @@ -333,21 +750,34 @@ 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) + * + * 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 \ - register queue_entry_t __prev; \ - \ - __prev = (head)->prev; \ - if ((head) == __prev) { \ - (head)->next = (queue_entry_t) (elt); \ - } \ - else { \ - ((type)__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 /* @@ -360,21 +790,24 @@ 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; \ - \ - __next = (head)->next; \ - if ((head) == __next) { \ - (head)->prev = (queue_entry_t) (elt); \ - } \ - else { \ - ((type)__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 /* @@ -388,33 +821,37 @@ 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; \ - \ - 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)__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)__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 /* @@ -428,33 +865,37 @@ 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; \ - \ - 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)__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)__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 /* @@ -462,9 +903,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) +#define queue_field(head, thing, type, field) \ + (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field) /* * Macro: queue_remove @@ -473,23 +916,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; \ - \ - __next = (elt)->field.next; \ - __prev = (elt)->field.prev; \ - \ - if ((head) == __next) \ - (head)->prev = __prev; \ - else \ - ((type)__next)->field.prev = __prev; \ - \ - if ((head) == __prev) \ - (head)->next = __next; \ - else \ - ((type)__prev)->field.next = __next; \ +#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 /* @@ -500,19 +948,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; \ - \ - (entry) = (type) ((head)->next); \ - __next = (entry)->field.next; \ - \ - if ((head) == __next) \ - (head)->prev = (head); \ - else \ - ((type)(__next))->field.prev = (head); \ - (head)->next = __next; \ +#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 /* @@ -523,29 +976,36 @@ 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; \ - \ - (entry) = (type) ((head)->prev); \ - __prev = (entry)->field.prev; \ - \ - if ((head) == __prev) \ - (head)->next = (head); \ - else \ - ((type)(__prev))->field.next = (head); \ - (head)->prev = __prev; \ +#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 /* * 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); \ - *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 /* @@ -558,16 +1018,20 @@ 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(old)) { \ - *(new) = *(old); \ - ((type)((new)->next))->field.prev = (new); \ - ((type)((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 /* @@ -582,52 +1046,15 @@ 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); \ - !queue_end((head), (queue_entry_t)(elt)); \ - (elt) = (type) 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 */ - decl_simple_lock_data(, lock) /* lock for queue */ -}; +#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)) -typedef struct mpqueue_head mpqueue_head_t; -#define round_mpq(size) (size) - -#define mpqueue_init(q) \ -MACRO_BEGIN \ - queue_init(&(q)->head); \ - simple_lock_init(&(q)->lock, 0); \ -MACRO_END - -#define mpenqueue_tail(q, elt) \ -MACRO_BEGIN \ - simple_lock(&(q)->lock); \ - enqueue_tail(&(q)->head, elt); \ - simple_unlock(&(q)->lock); \ -MACRO_END - -#define mpdequeue_head(q, elt) \ -MACRO_BEGIN \ - simple_lock(&(q)->lock); \ - if (queue_empty(&(q)->head)) \ - *(elt) = 0; \ - else \ - *(elt) = dequeue_head(&(q)->head); \ - simple_unlock(&(q)->lock); \ -MACRO_END - -#endif /* MACH_KERNEL_PRIVATE */ +__END_DECLS -#endif /* _KERN_QUEUE_H_ */ +#endif /* _KERN_QUEUE_H_ */