Loading...
--- xnu/xnu-12377.121.6/iokit/DriverKit/queue_implementation.h
+++ xnu/xnu-8792.61.2/iokit/DriverKit/queue_implementation.h
@@ -82,7 +82,7 @@
/*
* Queue Management APIs
*
- * There are currently two subtly different methods of maintaining
+ * There are currently two subtly different methods of maintining
* a queue of objects. Both APIs are contained in this file, and
* unfortunately overlap.
* (there is also a third way maintained in bsd/sys/queue.h)
@@ -201,21 +201,32 @@
struct queue_entry {
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
+ * negligible.
+ */
+} __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;
-#if defined(KERNEL_PRIVATE) || DRIVERKIT_FRAMEWORK_INCLUDE
-
-#if KERNEL_PRIVATE
-#define __queue_element_linkage_invalid(e) \
- ml_fatal_trap_invalid_list_linkage((unsigned long)(e))
+#if defined(XNU_KERNEL_PRIVATE) || DRIVERKIT_FRAMEWORK_INCLUDE
+
+#if KERNEL
+__abortlike
+extern void __queue_element_linkage_invalid(queue_entry_t e);
#else
-#define __queue_element_linkage_invalid(e) \
- __builtin_trap()
+#define __queue_element_linkage_invalid(e) __builtin_trap()
#endif
static inline void
@@ -226,30 +237,6 @@
}
}
-static inline queue_entry_t
-__QUEUE_ELT_VALIDATE_NEXT(queue_entry_t elt)
-{
- queue_entry_t __next = elt->next;
-
- if (__next->prev != elt) {
- __queue_element_linkage_invalid(elt);
- }
-
- return __next;
-}
-
-static inline queue_entry_t
-__QUEUE_ELT_VALIDATE_PREV(queue_entry_t elt)
-{
- queue_entry_t __prev = elt->prev;
-
- if (__prev->next != elt) {
- __queue_element_linkage_invalid(elt);
- }
-
- return __prev;
-}
-
static inline void
__DEQUEUE_ELT_CLEANUP(queue_entry_t elt)
{
@@ -257,10 +244,7 @@
}
#else
#define __QUEUE_ELT_VALIDATE(elt) ((void)0)
-#define __QUEUE_ELT_VALIDATE_NEXT(elt) ((elt)->next)
-#define __QUEUE_ELT_VALIDATE_PREV(elt) ((elt)->prev)
#define __DEQUEUE_ELT_CLEANUP(elt) ((void)0)
-#define __queue_element_linkage_invalid(e) ((void)0)
#endif /* !(XNU_KERNEL_PRIVATE || DRIVERKIT_FRAMEWORK_INCLUDE)*/
/*
@@ -281,7 +265,8 @@
{
queue_entry_t old_head;
- old_head = __QUEUE_ELT_VALIDATE_NEXT(que);
+ __QUEUE_ELT_VALIDATE((queue_entry_t)que);
+ old_head = que->next;
elt->next = old_head;
elt->prev = que;
old_head->prev = elt;
@@ -295,7 +280,8 @@
{
queue_entry_t old_tail;
- old_tail = __QUEUE_ELT_VALIDATE_PREV(que);
+ __QUEUE_ELT_VALIDATE((queue_entry_t)que);
+ old_tail = que->prev;
elt->next = que;
elt->prev = old_tail;
old_tail->next = elt;
@@ -361,7 +347,8 @@
{
queue_entry_t successor;
- successor = __QUEUE_ELT_VALIDATE_NEXT(pred);
+ __QUEUE_ELT_VALIDATE(pred);
+ successor = pred->next;
entry->next = successor;
entry->prev = pred;
successor->prev = entry;
@@ -539,7 +526,7 @@
&((elt)->field) != (head); \
elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
-#if (defined(XNU_KERNEL_PRIVATE) || SCHED_TEST_HARNESS)
+#ifdef XNU_KERNEL_PRIVATE
/* Dequeue an element from head, or return NULL if the queue is empty */
#define qe_dequeue_head(head, type, field) ({ \
@@ -595,7 +582,7 @@
_tmp_element; \
})
-#endif /* XNU_KERNEL_PRIVATE || SCHED_TEST_HARNESS */
+#endif /* XNU_KERNEL_PRIVATE */
/*
* Macro: QUEUE_HEAD_INITIALIZER()
@@ -752,57 +739,6 @@
* may be more than one chain.
*/
-/* check __prev->next == __elt */
-#define __QUEUE2_CHECK_NEXT(__fail, __elt, __prev, __head, type, field) \
-MACRO_BEGIN \
- if (__prev == __head) { \
- __fail |= __head->next != (queue_entry_t)__elt; \
- } else { \
- __fail |= ((type)(void *)__prev)->field.next != \
- (queue_entry_t)__elt; \
- } \
-MACRO_END
-
-/* check __next->prev == __elt */
-#define __QUEUE2_CHECK_PREV(__fail, __elt, __next, __head, type, field) \
-MACRO_BEGIN \
- if (__next == __head) { \
- __fail |= __head->prev != (queue_entry_t)__elt; \
- } else { \
- __fail |= ((type)(void *)__next)->field.prev != \
- (queue_entry_t)__elt; \
- } \
-MACRO_END
-
-#define __QUEUE2_CHECK_FAIL(__fail, __elt) \
-MACRO_BEGIN \
- if (__improbable(__fail)) { \
- __queue_element_linkage_invalid(__elt); \
- } \
-MACRO_END
-
-/* sets __prev->next to __elt */
-#define __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field) \
-MACRO_BEGIN \
- if (__head == __prev) { \
- __head->next = (queue_entry_t)__elt; \
- } else { \
- ((type)(void *)__prev)->field.next = (queue_entry_t)__elt; \
- } \
-MACRO_END
-
-/* sets __next->prev to __elt */
-#define __QUEUE2_SET_PREV(__next, __elt, __head, type, field) \
-MACRO_BEGIN \
- if (__head == __next) { \
- __head->prev = (queue_entry_t)__elt; \
- } else { \
- ((type)(void *)__next)->field.prev = (queue_entry_t)__elt; \
- } \
-MACRO_END
-
-
-
/*
* Macro: queue_enter
* Function:
@@ -825,24 +761,22 @@
* could cause stackshot to trip over an inconsistent queue during
* iteration.
*/
-#define queue_enter(head, elt, type, field) \
-MACRO_BEGIN \
- queue_entry_t __head, __prev; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __head = (head); \
- __prev = __head->prev; \
- \
- __QUEUE2_CHECK_NEXT(__fail, __head, __prev, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __elt->field.prev = __prev; \
- __elt->field.next = __head; \
- __compiler_barrier(); \
- __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field); \
- __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
/*
@@ -858,24 +792,21 @@
* 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 __head, __next; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __head = (head); \
- __next = __head->next; \
- \
- __QUEUE2_CHECK_PREV(__fail, __head, __next, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __elt->field.next = __next; \
- __elt->field.prev = __head; \
- __compiler_barrier(); \
- __QUEUE2_SET_PREV(__next, __elt, __head, type, field); \
- __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
/*
@@ -892,30 +823,34 @@
* 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 __head, __cur, __prev; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __cur = (queue_entry_t)(cur); \
- __head = (head); \
- \
- if (__head == __cur) { \
- __prev = __head->prev; \
- } else { \
- __prev = ((type)(void *)__cur)->field.prev; \
- } \
- \
- __QUEUE2_CHECK_NEXT(__fail, __cur, __prev, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __elt->field.prev = __prev; \
- __elt->field.next = __cur; \
- __compiler_barrier(); \
- __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field); \
- __QUEUE2_SET_PREV(__cur, __elt, __head, type, field); \
+#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
/*
@@ -932,30 +867,34 @@
* 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 __head, __cur, __next; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __cur = (queue_entry_t)(cur); \
- __head = (head); \
- \
- if (__head == __cur) { \
- __next = __head->next; \
- } else { \
- __next = ((type)(void *)__cur)->field.next; \
- } \
- \
- __QUEUE2_CHECK_PREV(__fail, __cur, __next, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __elt->field.prev = __cur; \
- __elt->field.next = __next; \
- __compiler_barrier(); \
- __QUEUE2_SET_NEXT(__cur, __elt, __head, type, field); \
- __QUEUE2_SET_PREV(__next, __elt, __head, type, field); \
+#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
/*
@@ -979,26 +918,25 @@
* 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 __head, __next, __prev; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __head = (head); \
- __next = __elt->field.next; \
- __prev = __elt->field.prev; \
- \
- __QUEUE2_CHECK_PREV(__fail, __elt, __next, __head, type, field); \
- __QUEUE2_CHECK_NEXT(__fail, __elt, __prev, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __QUEUE2_SET_PREV(__next, __prev, __head, type, field); \
- __QUEUE2_SET_NEXT(__prev, __next, __head, type, field); \
- __compiler_barrier(); \
- __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
/*
@@ -1014,16 +952,19 @@
*/
#define queue_remove_first(head, entry, type, field) \
MACRO_BEGIN \
- queue_entry_t __hd; \
- type __entry; \
- \
- __hd = (head); \
- __entry = (type)(void *)__hd->next; \
- \
- if ((queue_entry_t)__entry != __hd) { \
- queue_remove(__hd, __entry, type, field); \
- } \
- (entry) = __entry; \
+ 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
/*
@@ -1039,16 +980,19 @@
*/
#define queue_remove_last(head, entry, type, field) \
MACRO_BEGIN \
- queue_entry_t __hd; \
- type __entry; \
- \
- __hd = (head); \
- __entry = (type)(void *)__hd->prev; \
- \
- if ((queue_entry_t)__entry != __hd) { \
- queue_remove(__hd, __entry, type, field); \
- } \
- (entry) = __entry; \
+ 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
/*
@@ -1090,56 +1034,6 @@
MACRO_END
/*
- * Macro: queue_extend_last
- * Function:
- * Move the elements of a source queue to the end of a destination queue.
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_extend_last(dst, src, type, field) \
-MACRO_BEGIN \
- queue_entry_t __src = (src); \
- queue_entry_t __dst = (dst); \
- if (queue_empty(__dst)) { \
- queue_new_head(__src, __dst, type, field); \
- queue_init(__src); \
- } else if (!queue_empty(__src)) { \
- ((type)(void *)queue_first(__src))->field.prev = \
- queue_last(__dst); \
- ((type)(void *)queue_last(__dst))->field.next = \
- queue_first(__src); \
- queue_last(__dst) = queue_last(__src); \
- ((type)(void *)queue_last(__dst))->field.next = __dst; \
- queue_init(__src); \
- } \
-MACRO_END
-
-/*
- * Macro: queue_extend_first
- * Function:
- * Move the elements of a source queue to the beginning of a destination queue.
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_extend_first(dst, src, type, field) \
-MACRO_BEGIN \
- queue_entry_t __src = (src); \
- queue_entry_t __dst = (dst); \
- if (queue_empty(__dst)) { \
- queue_new_head(__src, __dst, type, field); \
- queue_init(__src); \
- } else if (!queue_empty(__src)) { \
- ((type)(void *)queue_first(__dst))->field.prev = \
- queue_last(__src); \
- ((type)(void *)queue_last(__src))->field.next = \
- queue_first(__dst); \
- queue_first(__dst) = queue_first(__src); \
- ((type)(void *)queue_first(__dst))->field.prev = __dst; \
- queue_init(__src); \
- } \
-MACRO_END
-
-/*
* Macro: queue_iterate
* Function:
* iterate over each item in the queue.