X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/6d2010ae8f7a6078e10b361c6962983bab233e0f..fe8ab488e9161c46dd9885d58fc52996dc0249ff:/osfmk/kern/queue.h diff --git a/osfmk/kern/queue.h b/osfmk/kern/queue.h index 836b55293..338395b17 100644 --- a/osfmk/kern/queue.h +++ b/osfmk/kern/queue.h @@ -70,6 +70,10 @@ #include #include +#include + +__BEGIN_DECLS + /* * Queue of abstract objects. Queue is maintained * within that object. @@ -112,52 +116,34 @@ typedef struct queue_entry *queue_entry_t; #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); - -/* 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 +#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 */ @@ -166,9 +152,13 @@ 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; } @@ -177,9 +167,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; } @@ -187,12 +181,15 @@ 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); } @@ -203,12 +200,15 @@ 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); } @@ -219,8 +219,13 @@ static __inline__ void 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); } @@ -229,23 +234,30 @@ 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__ 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: @@ -343,14 +355,15 @@ MACRO_END */ #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; \ @@ -370,14 +383,15 @@ MACRO_END */ #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; \ @@ -398,7 +412,7 @@ MACRO_END */ #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); \ @@ -407,7 +421,8 @@ MACRO_BEGIN \ (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 { \ @@ -418,7 +433,8 @@ MACRO_BEGIN \ (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); \ } \ @@ -438,7 +454,7 @@ MACRO_END */ #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); \ @@ -447,7 +463,8 @@ MACRO_BEGIN \ (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 { \ @@ -458,7 +475,8 @@ MACRO_BEGIN \ (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); \ } \ @@ -471,7 +489,7 @@ MACRO_END * 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 @@ -483,7 +501,7 @@ MACRO_END */ #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; \ @@ -491,12 +509,12 @@ MACRO_BEGIN \ 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; \ @@ -513,15 +531,15 @@ MACRO_END */ #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; \ @@ -539,15 +557,15 @@ MACRO_END */ #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; \ @@ -559,8 +577,8 @@ MACRO_END */ #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 @@ -579,8 +597,10 @@ 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); \ } \ @@ -600,13 +620,13 @@ MACRO_END * is the chain field in (*) */ #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 +#include /*----------------------------------------------------------------*/ /* @@ -614,8 +634,14 @@ MACRO_END */ 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; @@ -632,6 +658,8 @@ MACRO_BEGIN \ &(q)->lock_data_ext, \ lck_grp, \ lck_attr); \ + (q)->earliest_soft_deadline = UINT64_MAX; \ + (q)->count = 0; \ MACRO_END #else @@ -665,4 +693,6 @@ MACRO_END #endif /* MACH_KERNEL_PRIVATE */ +__END_DECLS + #endif /* _KERN_QUEUE_H_ */