#include <mach/mach_types.h>
#include <kern/macro_help.h>
+#include <sys/cdefs.h>
+
+__BEGIN_DECLS
+
/*
* Queue of abstract objects. Queue is maintained
* within that object.
#define enqueue(queue,elt) enqueue_tail(queue, elt)
#define dequeue(queue) dequeue_head(queue)
-#if !defined(__GNUC__)
-
-#include <sys/cdefs.h>
-__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);
-
-/* Dequeue element from tail of queue */
-extern queue_entry_t dequeue_tail(
- queue_t que);
-
-/* Dequeue element */
-extern void remqueue(
- queue_entry_t elt);
-
-/* Enqueue element after a particular elem */
-extern void insque(
- queue_entry_t entry,
- queue_entry_t pred);
-
-/* Dequeue element */
-extern void remque(
- queue_entry_t elt);
-
-__END_DECLS
-
-#else /* !__GNUC__ */
-
#ifdef XNU_KERNEL_PRIVATE
-#define __DEQUEUE_ELT_CLEANUP(elt) do { \
- (elt)->next = (queue_entry_t) 0; \
- (elt)->prev = (queue_entry_t) 0; \
- } while (0)
+#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)) {
+ 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 */
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;
}
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;
}
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);
}
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);
}
remqueue(
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);
}
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__ void
remque(
- register 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);
}
-#endif /* !__GNUC__ */
-
/*
* Macro: queue_init
* Function:
*/
#define queue_enter(head, elt, type, field) \
MACRO_BEGIN \
- register queue_entry_t __prev; \
+ 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);\
+ ((type)(void *)__prev)->field.next = \
+ (queue_entry_t)(elt); \
} \
(elt)->field.prev = __prev; \
(elt)->field.next = head; \
*/
#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) { \
(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.prev = head; \
*/
#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); \
(head)->next = (queue_entry_t)(elt); \
} else { /* last element */ \
__prev = (elt)->field.prev = (head)->prev; \
- ((type)__prev)->field.next = (queue_entry_t)(elt);\
+ ((type)(void *)__prev)->field.next = \
+ (queue_entry_t)(elt); \
} \
(head)->prev = (queue_entry_t)(elt); \
} else { \
(head)->next = (queue_entry_t)(elt); \
} else { /* middle element */ \
__prev = (elt)->field.prev = (cur)->field.prev; \
- ((type)__prev)->field.next = (queue_entry_t)(elt);\
+ ((type)(void *)__prev)->field.next = \
+ (queue_entry_t)(elt); \
} \
(cur)->field.prev = (queue_entry_t)(elt); \
} \
*/
#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); \
(head)->prev = (queue_entry_t)(elt); \
} else { /* first element */ \
__next = (elt)->field.next = (head)->next; \
- ((type)__next)->field.prev = (queue_entry_t)(elt);\
+ ((type)(void *)__next)->field.prev = \
+ (queue_entry_t)(elt); \
} \
(head)->next = (queue_entry_t)(elt); \
} else { \
(head)->prev = (queue_entry_t)(elt); \
} else { /* middle element */ \
__next = (elt)->field.next = (cur)->field.next; \
- ((type)__next)->field.prev = (queue_entry_t)(elt);\
+ ((type)(void *)__next)->field.prev = \
+ (queue_entry_t)(elt); \
} \
(cur)->field.next = (queue_entry_t)(elt); \
} \
* given element (thing) in the given queue (head)
*/
#define queue_field(head, thing, type, field) \
- (((head) == (thing)) ? (head) : &((type)(thing))->field)
+ (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
/*
* Macro: queue_remove
*/
#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; \
if ((head) == __next) \
(head)->prev = __prev; \
else \
- ((type)__next)->field.prev = __prev; \
+ ((type)(void *)__next)->field.prev = __prev; \
\
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; \
*/
#define queue_remove_first(head, entry, type, field) \
MACRO_BEGIN \
- register queue_entry_t __next; \
+ queue_entry_t __next; \
\
- (entry) = (type) ((head)->next); \
+ (entry) = (type)(void *) ((head)->next); \
__next = (entry)->field.next; \
\
if ((head) == __next) \
(head)->prev = (head); \
else \
- ((type)(__next))->field.prev = (head); \
+ ((type)(void *)(__next))->field.prev = (head); \
(head)->next = __next; \
\
(entry)->field.next = NULL; \
*/
#define queue_remove_last(head, entry, type, field) \
MACRO_BEGIN \
- register queue_entry_t __prev; \
+ queue_entry_t __prev; \
\
- (entry) = (type) ((head)->prev); \
+ (entry) = (type)(void *) ((head)->prev); \
__prev = (entry)->field.prev; \
\
if ((head) == __prev) \
(head)->next = (head); \
else \
- ((type)(__prev))->field.next = (head); \
+ ((type)(void *)(__prev))->field.next = (head); \
(head)->prev = __prev; \
\
(entry)->field.next = NULL; \
*/
#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
MACRO_BEGIN \
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); \
} \
* <field> is the chain field in (*<type>)
*/
#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 <kern/lock.h>
+#include <kern/locks.h>
/*----------------------------------------------------------------*/
/*
*/
struct mpqueue_head {
struct queue_entry head; /* header for queue */
+ uint64_t earliest_soft_deadline;
+ uint64_t count;
+#if defined(__i386__) || defined(__x86_64__)
lck_mtx_t lock_data;
lck_mtx_ext_t lock_data_ext;
+#else
+ lck_spin_t lock_data;
+#endif
};
typedef struct mpqueue_head mpqueue_head_t;
&(q)->lock_data_ext, \
lck_grp, \
lck_attr); \
+ (q)->earliest_soft_deadline = UINT64_MAX; \
+ (q)->count = 0; \
MACRO_END
#else
#endif /* MACH_KERNEL_PRIVATE */
+__END_DECLS
+
#endif /* _KERN_QUEUE_H_ */
projects / apple / xnu.git / blobdiff