* 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
* 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,
* 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
*
*/
-#ifndef _KERN_QUEUE_H_
-#define _KERN_QUEUE_H_
+#ifndef _KERN_QUEUE_H_
+#define _KERN_QUEUE_H_
#include <mach/mach_types.h>
#include <kern/macro_help.h>
#include <sys/cdefs.h>
+#include <string.h>
__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)
*/
/*
*/
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
+ * to disable it entirely. The impact on memory footprint should be
* negligible.
*/
-} __attribute__ ((aligned (8)));
+} __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".
* 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 <kern/debug.h>
-#include <mach/branch_predicates.h>
-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)
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;
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;
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;
__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;
__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;
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;
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);
}
/*
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);
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);
* Note:
* Do not use pointer types for <type>
*/
-#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
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; \
})
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; \
})
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; \
})
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:
* 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
* 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
* queue_entry_t queue_next(qc)
* queue_t qc;
*/
-#define queue_next(qc) ((qc)->next)
+#define queue_next(qc) ((qc)->next)
/*
* Macro: queue_last
* 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
* queue_entry_t queue_prev(qc)
* queue_t qc;
*/
-#define queue_prev(qc) ((qc)->prev)
+#define queue_prev(qc) ((qc)->prev)
/*
* Macro: queue_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
* 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
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);
* <field> is the chain field in (*<type>)
* 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
/*
* 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
/*
* 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
/*
* 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
/*
* 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
* 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
/*
* 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
/*
* 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
/*
* 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
/*
* 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
/*
* 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 <kern/locks.h>
-
-/*----------------------------------------------------------------*/
-/*
- * 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_ */
projects / apple / xnu.git / blobdiff