X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/6601e61aa18bf4f09af135ff61fc7f4771d23b06..15129b1c8dbb3650c63b70adb1cad9af601c6c17:/osfmk/kern/queue.h

diff --git a/osfmk/kern/queue.h b/osfmk/kern/queue.h
index 98effaac4..db7377840 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@
@@ -100,7 +106,7 @@ 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)
@@ -131,7 +137,6 @@ extern queue_entry_t	dequeue_tail(
 
 /* Dequeue element */
 extern void		remqueue(
-				queue_t		que,
 				queue_entry_t	elt);
 
 /* Enqueue element after a particular elem */
@@ -140,13 +145,22 @@ extern void		insque(
 				queue_entry_t	pred);
 
 /* Dequeue element */
-extern int		remque(
+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)
+#else
+#define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0)
+#endif /* !XNU_KERNEL_PRIVATE */
+
 static __inline__ void
 enqueue_head(
 	queue_t		que,
@@ -179,6 +193,7 @@ dequeue_head(
 		elt = que->next;
 		elt->next->prev = que;
 		que->next = elt->next;
+		__DEQUEUE_ELT_CLEANUP(elt);
 	}
 
 	return (elt);
@@ -194,6 +209,7 @@ dequeue_tail(
 		elt = que->prev;
 		elt->prev->next = que;
 		que->prev = elt->prev;
+		__DEQUEUE_ELT_CLEANUP(elt);
 	}
 
 	return (elt);
@@ -201,11 +217,11 @@ dequeue_tail(
 
 static __inline__ void
 remqueue(
-	__unused queue_t		que,
 	queue_entry_t	elt)
 {
 	elt->next->prev = elt->prev;
 	elt->prev->next = elt->next;
+	__DEQUEUE_ELT_CLEANUP(elt);
 }
 
 static __inline__ void
@@ -219,14 +235,13 @@ insque(
 	pred->next = entry;
 }
 
-static __inline__ integer_t
+static __inline__ void
 remque(
 	register queue_entry_t elt)
 {
 	(elt->next)->prev = elt->prev;
 	(elt->prev)->next = elt->next;
-
-	return((integer_t)elt);
+	__DEQUEUE_ELT_CLEANUP(elt);
 }
 
 #endif	/* !__GNUC__ */
@@ -335,7 +350,8 @@ MACRO_BEGIN							\
 		(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;				\
@@ -362,7 +378,8 @@ MACRO_BEGIN							\
 		(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;				\
@@ -392,7 +409,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 +421,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);		\
 	}								\
@@ -432,7 +451,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 +463,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 +477,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
@@ -476,12 +497,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
 
 /*
@@ -497,14 +521,17 @@ MACRO_END
 MACRO_BEGIN							\
 	register 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
 
 /*
@@ -520,14 +547,17 @@ MACRO_END
 MACRO_BEGIN							\
 	register 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 +565,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 +585,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,9 +608,9 @@ MACRO_END
  *			<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
 
@@ -590,34 +622,61 @@ 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 */