X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/378393581903b274cb7a4d18e0d978071a6b592d..fe8ab488e9161c46dd9885d58fc52996dc0249ff:/osfmk/kern/queue.h diff --git a/osfmk/kern/queue.h b/osfmk/kern/queue.h index 98effaac4..338395b17 100644 --- a/osfmk/kern/queue.h +++ b/osfmk/kern/queue.h @@ -1,23 +1,29 @@ /* - * Copyright (c) 2000-2005 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@ @@ -64,6 +70,10 @@ #include #include +#include + +__BEGIN_DECLS + /* * Queue of abstract objects. Queue is maintained * within that object. @@ -100,61 +110,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__) - -#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_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); - -__END_DECLS +#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); + } +} -#else /* !__GNUC__ */ +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; } @@ -163,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; } @@ -173,12 +181,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); @@ -188,12 +200,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); @@ -201,11 +217,16 @@ dequeue_tail( static __inline__ void remqueue( - __unused 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 @@ -213,24 +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__ integer_t +static __inline__ void remque( - register queue_entry_t elt) + queue_entry_t elt) { - (elt->next)->prev = elt->prev; - (elt->prev)->next = elt->next; - - return((integer_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); } -#endif /* !__GNUC__ */ - /* * Macro: queue_init * Function: @@ -328,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; \ @@ -355,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; \ @@ -383,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); \ @@ -392,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 { \ @@ -403,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); \ } \ @@ -423,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); \ @@ -432,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 { \ @@ -443,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); \ } \ @@ -456,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 @@ -468,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; \ @@ -476,12 +509,15 @@ 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; \ MACRO_END /* @@ -495,16 +531,19 @@ 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; \ + (entry)->field.prev = NULL; \ MACRO_END /* @@ -518,16 +557,19 @@ 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; \ + (entry)->field.prev = NULL; \ MACRO_END /* @@ -535,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 @@ -555,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); \ } \ @@ -576,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 /*----------------------------------------------------------------*/ /* @@ -590,36 +634,65 @@ MACRO_END */ 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; +#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; #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); \ + 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); \ - simple_lock_init(&(q)->lock, 0); \ + lck_spin_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 */ +__END_DECLS + #endif /* _KERN_QUEUE_H_ */