xnu-6153.81.5.tar.gz

[apple/xnu.git] / osfmk / kern / queue.h

diff --git a/osfmk/kern/queue.h b/osfmk/kern/queue.h
index f45899ce220e4fbeeb2b40c719f49c0c8150373e..68032cbe7f7414bd19c7ab467bc16faeaf6b881b 100644 (file)
--- a/osfmk/kern/queue.h
+++ b/osfmk/kern/queue.h
@@ -2,7 +2,7 @@
  * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@

- * 
+ *

  * 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
  * 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


@@ -11,10 +11,10 @@
  * 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.
  * 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.

- * 
+ *

  * Please obtain a copy of the License at
  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  * 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,
  * 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,


@@ -22,27 +22,27 @@
  * 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.
  * 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_OSREFERENCE_LICENSE_HEADER_END@
  */
 /*
  * @OSF_COPYRIGHT@
  */
  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  */
 /*
  * @OSF_COPYRIGHT@
  */

-/* 
+/*

  * Mach Operating System
  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
  * All Rights Reserved.
  * Mach Operating System
  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
  * All Rights Reserved.

- * 
+ *

  * Permission to use, copy, modify and distribute this software and its
  * documentation is hereby granted, provided that both the copyright
  * notice and this permission notice appear in all copies of the
  * software, derivative works or modified versions, and any portions
  * thereof, and that both notices appear in supporting documentation.
  * Permission to use, copy, modify and distribute this software and its
  * documentation is hereby granted, provided that both the copyright
  * notice and this permission notice appear in all copies of the
  * software, derivative works or modified versions, and any portions
  * thereof, and that both notices appear in supporting documentation.

- * 
+ *

  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.

- * 
+ *

  * Carnegie Mellon requests users of this software to return to
  *
  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  * Carnegie Mellon requests users of this software to return to
  *
  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU


@@ -64,13 +64,14 @@
  *
  */
 
  *
  */
 

-#ifndef        _KERN_QUEUE_H_
-#define        _KERN_QUEUE_H_
+#ifndef _KERN_QUEUE_H_
+#define _KERN_QUEUE_H_

 
 #include <mach/mach_types.h>
 #include <kern/macro_help.h>
 
 #include <sys/cdefs.h>
 
 #include <mach/mach_types.h>
 #include <kern/macro_help.h>
 
 #include <sys/cdefs.h>

+#include <string.h>

 
 __BEGIN_DECLS
 
 
 __BEGIN_DECLS
 


@@ -83,110 +84,110 @@ __BEGIN_DECLS
  * (there is also a third way maintained in bsd/sys/queue.h)
  *
  * Both methods use a common queue head and linkage pattern:
  * (there is also a third way maintained in bsd/sys/queue.h)
  *
  * Both methods use a common queue head and linkage pattern:

- *     The head of a queue is declared as:
- *             queue_head_t q_head;
+ *      The head of a queue is declared as:
+ *              queue_head_t q_head;

  *
  *

- *     Elements in this queue are chained together using
- *     struct queue_entry objects embedded within a structure:
- *             struct some_data {
- *                     int field1;
- *                     int field2;
- *                     ...
- *                     queue_chain_t link;
- *                     ...
- *                     int last_field;
- *             };
- *     struct some_data is referred to as the queue "element."
- *     (note that queue_chain_t is typedef'd to struct queue_entry)
+ *      Elements in this queue are chained together using
+ *      struct queue_entry objects embedded within a structure:
+ *              struct some_data {
+ *                      int field1;
+ *                      int field2;
+ *                      ...
+ *                      queue_chain_t link;
+ *                      ...
+ *                      int last_field;
+ *              };
+ *      struct some_data is referred to as the queue "element."
+ *      (note that queue_chain_t is typedef'd to struct queue_entry)

  *
  * IMPORTANT: The two queue iteration methods described below are not
  *            compatible with one another. You must choose one and be careful
  *            to use only the supported APIs for that method.
  *
  * Method 1: chaining of queue_chain_t (linkage chains)
  *
  * IMPORTANT: The two queue iteration methods described below are not
  *            compatible with one another. You must choose one and be careful
  *            to use only the supported APIs for that method.
  *
  * Method 1: chaining of queue_chain_t (linkage chains)

- *     This method uses the next and prev pointers of the struct queue_entry
- *     linkage object embedded in a queue element to point to the next or
- *     previous queue_entry structure in the chain. The head of the queue
- *     (the queue_head_t object) will point to the first and last
- *     struct queue_entry object, and both the next and prev pointer will
- *     point back to the head if the queue is empty.
+ *      This method uses the next and prev pointers of the struct queue_entry
+ *      linkage object embedded in a queue element to point to the next or
+ *      previous queue_entry structure in the chain. The head of the queue
+ *      (the queue_head_t object) will point to the first and last
+ *      struct queue_entry object, and both the next and prev pointer will
+ *      point back to the head if the queue is empty.

  *
  *

- *     This method is the most flexible method of chaining objects together
- *     as it allows multiple chains through a given object, by embedding
- *     multiple queue_chain_t objects in the structure, while simultaneously
- *     providing fast removal and insertion into the queue using only
- *     struct queue_entry object pointers.
+ *      This method is the most flexible method of chaining objects together
+ *      as it allows multiple chains through a given object, by embedding
+ *      multiple queue_chain_t objects in the structure, while simultaneously
+ *      providing fast removal and insertion into the queue using only
+ *      struct queue_entry object pointers.

  *
  *

- *     ++ Valid APIs for this style queue ++
- *     -------------------------------------
- *             [C] queue_init
- *             [C] queue_first
- *             [C] queue_next
- *             [C] queue_last
- *             [C] queue_prev
- *             [C] queue_end
- *             [C] queue_empty
+ *      ++ Valid APIs for this style queue ++
+ *      -------------------------------------
+ *              [C] queue_init
+ *              [C] queue_first
+ *              [C] queue_next
+ *              [C] queue_last
+ *              [C] queue_prev
+ *              [C] queue_end
+ *              [C] queue_empty

  *
  *

- *             [1] enqueue
- *             [1] dequeue
- *             [1] enqueue_head
- *             [1] enqueue_tail
- *             [1] dequeue_head
- *             [1] dequeue_tail
- *             [1] remqueue
- *             [1] insque
- *             [1] remque
- *             [1] re_queue
- *             [1] re_queue_tail
- *             [1] movqueue
- *             [1] qe_element
- *             [1] qe_foreach
- *             [1] qe_foreach_safe
- *             [1] qe_foreach_element
- *             [1] qe_foreach_element_safe
+ *              [1] enqueue
+ *              [1] dequeue
+ *              [1] enqueue_head
+ *              [1] enqueue_tail
+ *              [1] dequeue_head
+ *              [1] dequeue_tail
+ *              [1] remqueue
+ *              [1] insque
+ *              [1] remque
+ *              [1] re_queue_head
+ *              [1] re_queue_tail
+ *              [1] movqueue
+ *              [1] qe_element
+ *              [1] qe_foreach
+ *              [1] qe_foreach_safe
+ *              [1] qe_foreach_element
+ *              [1] qe_foreach_element_safe

  *
  * Method 2: chaining of elements (element chains)
  *
  * Method 2: chaining of elements (element chains)

- *     This method uses the next and prev pointers of the struct queue_entry
- *     linkage object embedded in a queue element to point to the next or
- *     previous queue element (not another queue_entry). The head of the
- *     queue will point to the first and last queue element (struct some_data
- *     from the above example) NOT the embedded queue_entry structure. The
- *     first queue element will have a prev pointer that points to the
- *     queue_head_t, and the last queue element will have a next pointer
- *     that points to the queue_head_t.
+ *      This method uses the next and prev pointers of the struct queue_entry
+ *      linkage object embedded in a queue element to point to the next or
+ *      previous queue element (not another queue_entry). The head of the
+ *      queue will point to the first and last queue element (struct some_data
+ *      from the above example) NOT the embedded queue_entry structure. The
+ *      first queue element will have a prev pointer that points to the
+ *      queue_head_t, and the last queue element will have a next pointer
+ *      that points to the queue_head_t.

  *
  *

- *     This method requires knowledge of the queue_head_t of the queue on
- *     which an element resides in order to remove the element. Iterating
- *     through the elements of the queue is also more cumbersome because
- *     a check against the head pointer plus a cast then offset operation
- *     must be performed at each step of the iteration.
+ *      This method requires knowledge of the queue_head_t of the queue on
+ *      which an element resides in order to remove the element. Iterating
+ *      through the elements of the queue is also more cumbersome because
+ *      a check against the head pointer plus a cast then offset operation
+ *      must be performed at each step of the iteration.

  *
  *

- *     ++ Valid APIs for this style queue ++
- *     -------------------------------------
- *             [C] queue_init
- *             [C] queue_first
- *             [C] queue_next
- *             [C] queue_last
- *             [C] queue_prev
- *             [C] queue_end
- *             [C] queue_empty
+ *      ++ Valid APIs for this style queue ++
+ *      -------------------------------------
+ *              [C] queue_init
+ *              [C] queue_first
+ *              [C] queue_next
+ *              [C] queue_last
+ *              [C] queue_prev
+ *              [C] queue_end
+ *              [C] queue_empty

  *
  *

- *             [2] queue_enter
- *             [2] queue_enter_first
- *             [2] queue_insert_before
- *             [2] queue_insert_after
- *             [2] queue_field
- *             [2] queue_remove
- *             [2] queue_remove_first
- *             [2] queue_remove_last
- *             [2] queue_assign
- *             [2] queue_new_head
- *             [2] queue_iterate
+ *              [2] queue_enter
+ *              [2] queue_enter_first
+ *              [2] queue_insert_before
+ *              [2] queue_insert_after
+ *              [2] queue_field
+ *              [2] queue_remove
+ *              [2] queue_remove_first
+ *              [2] queue_remove_last
+ *              [2] queue_assign
+ *              [2] queue_new_head
+ *              [2] queue_iterate

  *
  * Legend:
  *
  * Legend:

- *     [C] -> API common to both methods
- *     [1] -> API used only in method 1 (linkage chains)
- *     [2] -> API used only in method 2 (element chains)
+ *      [C] -> API common to both methods
+ *      [1] -> API used only in method 1 (linkage chains)
+ *      [2] -> API used only in method 2 (element chains)

  */
 
 /*
  */
 
 /*


@@ -194,15 +195,26 @@ __BEGIN_DECLS
  */
 
 struct queue_entry {
  */
 
 struct queue_entry {

-       struct queue_entry      *next;          /* next element */
-       struct queue_entry      *prev;          /* previous element */
-
+       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;
+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;

 
 /*
  *     enqueue puts "elt" on the "queue".
 
 /*
  *     enqueue puts "elt" on the "queue".


@@ -210,34 +222,37 @@ typedef   struct queue_entry      *queue_entry_t;
  *     remqueue removes the specified "elt" from its queue.
  */
 
  *     remqueue removes the specified "elt" from its queue.
  */
 

-#define enqueue(queue,elt)     enqueue_tail(queue, elt)
-#define        dequeue(queue)          dequeue_head(queue)
+#define enqueue(queue, elt)      enqueue_tail(queue, elt)
+#define dequeue(queue)          dequeue_head(queue)

 
 #ifdef XNU_KERNEL_PRIVATE
 #include <kern/debug.h>
 
 #ifdef XNU_KERNEL_PRIVATE
 #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)) {
+static inline void
+__QUEUE_ELT_VALIDATE(queue_entry_t elt)
+{
+       queue_entry_t   elt_next, elt_prev;
+
+       if (__improbable(elt == (queue_entry_t)NULL)) {

                panic("Invalid queue element %p", elt);
        }
                panic("Invalid queue element %p", elt);
        }

-       
+

        elt_next = elt->next;
        elt_prev = elt->prev;
        elt_next = elt->next;
        elt_prev = elt->prev;

-       
-       if (__improbable(elt_next == (queue_entry_t)0 || elt_prev == (queue_entry_t)0)) {
+
+       if (__improbable(elt_next == (queue_entry_t)NULL || elt_prev == (queue_entry_t)NULL)) {

                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 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);
+               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;
+static inline void
+__DEQUEUE_ELT_CLEANUP(queue_entry_t elt)
+{
+       (elt)->next = (queue_entry_t)NULL;
+       (elt)->prev = (queue_entry_t)NULL;

 }
 #else
 #define __QUEUE_ELT_VALIDATE(elt) do { } while (0)
 }
 #else
 #define __QUEUE_ELT_VALIDATE(elt) do { } while (0)


@@ -246,10 +261,10 @@ static inline void __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) {
 
 static __inline__ void
 enqueue_head(
 
 static __inline__ void
 enqueue_head(

-       queue_t         que,
-       queue_entry_t   elt)
+       queue_t         que,
+       queue_entry_t   elt)

 {
 {

-       queue_entry_t   old_head;
+       queue_entry_t   old_head;

 
        __QUEUE_ELT_VALIDATE((queue_entry_t)que);
        old_head = que->next;
 
        __QUEUE_ELT_VALIDATE((queue_entry_t)que);
        old_head = que->next;


@@ -261,10 +276,10 @@ enqueue_head(
 
 static __inline__ void
 enqueue_tail(
 
 static __inline__ void
 enqueue_tail(

-               queue_t         que,
-               queue_entry_t   elt)
+       queue_t         que,
+       queue_entry_t   elt)

 {
 {

-       queue_entry_t   old_tail;
+       queue_entry_t   old_tail;

 
        __QUEUE_ELT_VALIDATE((queue_entry_t)que);
        old_tail = que->prev;
 
        __QUEUE_ELT_VALIDATE((queue_entry_t)que);
        old_tail = que->prev;


@@ -276,10 +291,10 @@ enqueue_tail(
 
 static __inline__ queue_entry_t
 dequeue_head(
 
 static __inline__ queue_entry_t
 dequeue_head(

-       queue_t que)
+       queue_t que)

 {
 {

-       queue_entry_t   elt = (queue_entry_t) 0;
-       queue_entry_t   new_head;
+       queue_entry_t   elt = (queue_entry_t)NULL;
+       queue_entry_t   new_head;

 
        if (que->next != que) {
                elt = que->next;
 
        if (que->next != que) {
                elt = que->next;


@@ -290,15 +305,15 @@ dequeue_head(
                __DEQUEUE_ELT_CLEANUP(elt);
        }
 
                __DEQUEUE_ELT_CLEANUP(elt);
        }
 

-       return (elt);
+       return elt;

 }
 
 static __inline__ queue_entry_t
 dequeue_tail(
 }
 
 static __inline__ queue_entry_t
 dequeue_tail(

-       queue_t que)
+       queue_t que)

 {
 {

-       queue_entry_t   elt = (queue_entry_t) 0;
-       queue_entry_t   new_tail;
+       queue_entry_t   elt = (queue_entry_t)NULL;
+       queue_entry_t   new_tail;

 
        if (que->prev != que) {
                elt = que->prev;
 
        if (que->prev != que) {
                elt = que->prev;


@@ -309,14 +324,14 @@ dequeue_tail(
                __DEQUEUE_ELT_CLEANUP(elt);
        }
 
                __DEQUEUE_ELT_CLEANUP(elt);
        }
 

-       return (elt);
+       return elt;

 }
 
 static __inline__ void
 remqueue(
 }
 
 static __inline__ void
 remqueue(

-       queue_entry_t   elt)
+       queue_entry_t   elt)

 {
 {

-       queue_entry_t   next_elt, prev_elt;
+       queue_entry_t   next_elt, prev_elt;

 
        __QUEUE_ELT_VALIDATE(elt);
        next_elt = elt->next;
 
        __QUEUE_ELT_VALIDATE(elt);
        next_elt = elt->next;


@@ -328,10 +343,10 @@ remqueue(
 
 static __inline__ void
 insque(
 
 static __inline__ void
 insque(

-       queue_entry_t   entry,
-       queue_entry_t   pred)
+       queue_entry_t   entry,
+       queue_entry_t   pred)

 {
 {

-       queue_entry_t   successor;
+       queue_entry_t   successor;

 
        __QUEUE_ELT_VALIDATE(pred);
        successor = pred->next;
 
        __QUEUE_ELT_VALIDATE(pred);
        successor = pred->next;


@@ -345,7 +360,7 @@ static __inline__ void
 remque(
        queue_entry_t elt)
 {
 remque(
        queue_entry_t elt)
 {

-       queue_entry_t   next_elt, prev_elt;
+       queue_entry_t   next_elt, prev_elt;

 
        __QUEUE_ELT_VALIDATE(elt);
        next_elt = elt->next;
 
        __QUEUE_ELT_VALIDATE(elt);
        next_elt = elt->next;


@@ -369,7 +384,7 @@ remque(
 static __inline__ void
 re_queue_head(queue_t que, queue_entry_t elt)
 {
 static __inline__ void
 re_queue_head(queue_t que, queue_entry_t elt)
 {

-       queue_entry_t   n_elt, p_elt;
+       queue_entry_t   n_elt, p_elt;

 
        __QUEUE_ELT_VALIDATE(elt);
        __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 
        __QUEUE_ELT_VALIDATE(elt);
        __QUEUE_ELT_VALIDATE((queue_entry_t)que);


@@ -402,7 +417,7 @@ re_queue_head(queue_t que, queue_entry_t elt)
 static __inline__ void
 re_queue_tail(queue_t que, queue_entry_t elt)
 {
 static __inline__ void
 re_queue_tail(queue_t que, queue_entry_t elt)
 {

-       queue_entry_t   n_elt, p_elt;
+       queue_entry_t   n_elt, p_elt;

 
        __QUEUE_ELT_VALIDATE(elt);
        __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 
        __QUEUE_ELT_VALIDATE(elt);
        __QUEUE_ELT_VALIDATE((queue_entry_t)que);


@@ -435,8 +450,7 @@ re_queue_tail(queue_t que, queue_entry_t elt)
  *     Note:
  *             Do not use pointer types for <type>
  */
  *     Note:
  *             Do not use pointer types for <type>
  */

-#define        qe_element(qe, type, field) \
-       ((type *)((void *)((char *)(qe) - __offsetof(type, field))))
+#define qe_element(qe, type, field) __container_of(qe, type, field)

 
 /*
  *     Macro:          qe_foreach
 
 /*
  *     Macro:          qe_foreach


@@ -520,6 +534,46 @@ re_queue_tail(queue_t que, queue_entry_t elt)
             &((elt)->field) != (head); \
             elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
 
             &((elt)->field) != (head); \
             elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
 

+#ifdef XNU_KERNEL_PRIVATE
+
+/* Dequeue an element from head, or return NULL if the queue is empty */
+#define qe_dequeue_head(head, type, field) ({ \
+       queue_entry_t _tmp_entry = dequeue_head((head)); \
+       type *_tmp_element = (type*) NULL; \
+       if (_tmp_entry != (queue_entry_t) NULL) \
+               _tmp_element = qe_element(_tmp_entry, type, field); \
+       _tmp_element; \
+})
+
+/* Dequeue an element from tail, or return NULL if the queue is empty */
+#define qe_dequeue_tail(head, type, field) ({ \
+       queue_entry_t _tmp_entry = dequeue_tail((head)); \
+       type *_tmp_element = (type*) NULL; \
+       if (_tmp_entry != (queue_entry_t) NULL) \
+               _tmp_element = qe_element(_tmp_entry, type, field); \
+       _tmp_element; \
+})
+
+/* Peek at the first element, or return NULL if the queue is empty */
+#define qe_queue_first(head, type, field) ({ \
+       queue_entry_t _tmp_entry = queue_first((head)); \
+       type *_tmp_element = (type*) NULL; \
+       if (_tmp_entry != (queue_entry_t) head) \
+               _tmp_element = qe_element(_tmp_entry, type, field); \
+       _tmp_element; \
+})
+
+/* Peek at the last element, or return NULL if the queue is empty */
+#define qe_queue_last(head, type, field) ({ \
+       queue_entry_t _tmp_entry = queue_last((head)); \
+       type *_tmp_element = (type*) NULL; \
+       if (_tmp_entry != (queue_entry_t) head) \
+               _tmp_element = qe_element(_tmp_entry, type, field); \
+       _tmp_element; \
+})
+
+#endif /* XNU_KERNEL_PRIVATE */
+

 /*
  *     Macro:          queue_init
  *     Function:
 /*
  *     Macro:          queue_init
  *     Function:


@@ -528,8 +582,8 @@ re_queue_tail(queue_t que, queue_entry_t elt)
  *             void queue_init(q)
  *                     queue_t         q;      \* MODIFIED *\
  */
  *             void queue_init(q)
  *                     queue_t         q;      \* MODIFIED *\
  */

-#define queue_init(q)  \
-MACRO_BEGIN            \
+#define queue_init(q)   \
+MACRO_BEGIN             \

        (q)->next = (q);\
        (q)->prev = (q);\
 MACRO_END
        (q)->next = (q);\
        (q)->prev = (q);\
 MACRO_END


@@ -564,7 +618,7 @@ MACRO_END
  *             queue_entry_t queue_first(q)
  *                     queue_t q;              \* IN *\
  */
  *             queue_entry_t queue_first(q)
  *                     queue_t q;              \* IN *\
  */

-#define        queue_first(q)  ((q)->next)
+#define queue_first(q)  ((q)->next)

 
 /*
  *     Macro:          queue_next
 
 /*
  *     Macro:          queue_next


@@ -574,7 +628,7 @@ MACRO_END
  *             queue_entry_t queue_next(qc)
  *                     queue_t qc;
  */
  *             queue_entry_t queue_next(qc)
  *                     queue_t qc;
  */

-#define        queue_next(qc)  ((qc)->next)
+#define queue_next(qc)  ((qc)->next)

 
 /*
  *     Macro:          queue_last
 
 /*
  *     Macro:          queue_last


@@ -584,7 +638,7 @@ MACRO_END
  *             queue_entry_t queue_last(q)
  *                     queue_t q;              \* IN *\
  */
  *             queue_entry_t queue_last(q)
  *                     queue_t q;              \* IN *\
  */

-#define        queue_last(q)   ((q)->prev)
+#define queue_last(q)   ((q)->prev)

 
 /*
  *     Macro:          queue_prev
 
 /*
  *     Macro:          queue_prev


@@ -594,7 +648,7 @@ MACRO_END
  *             queue_entry_t queue_prev(qc)
  *                     queue_t qc;
  */
  *             queue_entry_t queue_prev(qc)
  *                     queue_t qc;
  */

-#define        queue_prev(qc)  ((qc)->prev)
+#define queue_prev(qc)  ((qc)->prev)

 
 /*
  *     Macro:          queue_end
 
 /*
  *     Macro:          queue_end


@@ -606,7 +660,7 @@ MACRO_END
  *                     queue_t q;
  *                     queue_entry_t qe;
  */
  *                     queue_t q;
  *                     queue_entry_t qe;
  */

-#define        queue_end(q, qe)        ((q) == (qe))
+#define queue_end(q, qe)        ((q) == (qe))

 
 /*
  *     Macro:          queue_empty
 
 /*
  *     Macro:          queue_empty


@@ -616,7 +670,7 @@ MACRO_END
  *             boolean_t queue_empty(q)
  *                     queue_t q;
  */
  *             boolean_t queue_empty(q)
  *                     queue_t q;
  */

-#define        queue_empty(q)          queue_end((q), queue_first(q))
+#define queue_empty(q)          queue_end((q), queue_first(q))

 
 /*
  *     Function:       movqueue
 
 /*
  *     Function:       movqueue


@@ -636,7 +690,7 @@ MACRO_END
 static __inline__ void
 movqueue(queue_t _old, queue_t _new)
 {
 static __inline__ void
 movqueue(queue_t _old, queue_t _new)
 {

-       queue_entry_t   next_elt, prev_elt;
+       queue_entry_t   next_elt, prev_elt;

 
        __QUEUE_ELT_VALIDATE((queue_entry_t)_old);
 
 
        __QUEUE_ELT_VALIDATE((queue_entry_t)_old);
 


@@ -679,22 +733,32 @@ movqueue(queue_t _old, queue_t _new)
  *                     <field> is the chain field in (*<type>)
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  *                     <field> is the chain field in (*<type>)
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)

+ *
+ *             We insert a compiler barrier after setting the fields in the element
+ *             to ensure that the element is updated before being added to the queue,
+ *             which is especially important because stackshot, which operates from
+ *             debugger context, iterates several queues that use this macro (the tasks
+ *             lists and threads lists) without locks. Without this barrier, the
+ *             compiler may re-order the instructions for this macro in a way that
+ *             could cause stackshot to trip over an inconsistent queue during
+ *             iteration.

  */
  */

-#define queue_enter(head, elt, type, field)                    \
-MACRO_BEGIN                                                    \
-       queue_entry_t __prev;                                   \
-                                                               \
-       __prev = (head)->prev;                                  \
-       if ((head) == __prev) {                                 \
-               (head)->next = (queue_entry_t) (elt);           \
-       }                                                       \
-       else {                                                  \
-               ((type)(void *)__prev)->field.next =            \
-                       (queue_entry_t)(elt);                   \
-       }                                                       \
-       (elt)->field.prev = __prev;                             \
-       (elt)->field.next = head;                               \
-       (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
 
 /*
 MACRO_END
 
 /*


@@ -710,21 +774,21 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     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 __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;                     \
+#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
 
 /*
 MACRO_END
 
 /*


@@ -741,34 +805,34 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     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 __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);               \
-       }                                                               \
+#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
 
 /*
 MACRO_END
 
 /*


@@ -785,34 +849,34 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     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 __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);               \
-       }                                                               \
+#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
 
 /*
 MACRO_END
 
 /*


@@ -823,8 +887,8 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */

-#define        queue_field(head, thing, type, field)                   \
-               (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
+#define queue_field(head, thing, type, field)                   \
+               (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)

 
 /*
  *     Macro:          queue_remove
 
 /*
  *     Macro:          queue_remove


@@ -836,25 +900,25 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     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   __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;                               \
+#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
 
 /*
 MACRO_END
 
 /*


@@ -868,21 +932,21 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */

-#define        queue_remove_first(head, entry, type, field)            \
-MACRO_BEGIN                                                    \
-       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;                             \
+#define queue_remove_first(head, entry, type, field)            \
+MACRO_BEGIN                                                     \
+       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
 
 /*
 MACRO_END
 
 /*


@@ -896,21 +960,21 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */

-#define        queue_remove_last(head, entry, type, field)             \
-MACRO_BEGIN                                                    \
-       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;                             \
+#define queue_remove_last(head, entry, type, field)             \
+MACRO_BEGIN                                                     \
+       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
 
 /*
 MACRO_END
 
 /*


@@ -918,11 +982,11 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */

-#define        queue_assign(to, from, type, field)                     \
-MACRO_BEGIN                                                    \
-       ((type)(void *)((from)->prev))->field.next = (to);      \
-       ((type)(void *)((from)->next))->field.prev = (to);      \
-       *to = *from;                                            \
+#define queue_assign(to, from, type, field)                     \
+MACRO_BEGIN                                                     \
+       ((type)(void *)((from)->prev))->field.next = (to);      \
+       ((type)(void *)((from)->next))->field.prev = (to);      \
+       *to = *from;                                            \

 MACRO_END
 
 /*
 MACRO_END
 
 /*


@@ -938,17 +1002,17 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */

-#define queue_new_head(old, new, type, field)                  \
-MACRO_BEGIN                                                    \
-       if (!queue_empty(old)) {                                \
-               *(new) = *(old);                                \
-               ((type)(void *)((new)->next))->field.prev =     \
-                       (new);                                  \
-               ((type)(void *)((new)->prev))->field.next =     \
-                       (new);                                  \
-       } else {                                                \
-               queue_init(new);                                \
-       }                                                       \
+#define queue_new_head(old, new, type, field)                   \
+MACRO_BEGIN                                                     \
+       if (!queue_empty(old)) {                                \
+               *(new) = *(old);                                \
+               ((type)(void *)((new)->next))->field.prev =     \
+                       (new);                                  \
+               ((type)(void *)((new)->prev))->field.next =     \
+                       (new);                                  \
+       } else {                                                \
+               queue_init(new);                                \
+       }                                                       \

 MACRO_END
 
 /*
 MACRO_END
 
 /*


@@ -966,80 +1030,12 @@ MACRO_END
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */
  *     Note:
  *             This should only be used with Method 2 queue iteration (element chains)
  */

-#define queue_iterate(head, elt, type, field)                  \
-       for ((elt) = (type)(void *) queue_first(head);          \
-            !queue_end((head), (queue_entry_t)(elt));          \
+#define queue_iterate(head, elt, type, field)                   \
+       for ((elt) = (type)(void *) queue_first(head);          \
+            !queue_end((head), (queue_entry_t)(elt));          \

             (elt) = (type)(void *) queue_next(&(elt)->field))
 
             (elt) = (type)(void *) queue_next(&(elt)->field))
 

-#ifdef MACH_KERNEL_PRIVATE
-
-#include <kern/locks.h>
-
-/*----------------------------------------------------------------*/
-/*
- *     Define macros for queues with locks.
- */
-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;
-
-#define        round_mpq(size)         (size)
-
-
-#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);                         \
-        lck_spin_init(&(q)->lock_data,                 \
-                     lck_grp,                          \
-                     lck_attr);                        \
-MACRO_END
-#endif
-
-
-#define mpenqueue_tail(q, elt)                         \
-MACRO_BEGIN                                            \
-        lck_mtx_lock_spin_always(&(q)->lock_data);     \
-       enqueue_tail(&(q)->head, elt);                  \
-       lck_mtx_unlock_always(&(q)->lock_data);         \
-MACRO_END
-
-#define mpdequeue_head(q, elt)                         \
-MACRO_BEGIN                                            \
-        lck_mtx_lock_spin_always(&(q)->lock_data);     \
-       if (queue_empty(&(q)->head))                    \
-               *(elt) = 0;                             \
-       else                                            \
-               *(elt) = dequeue_head(&(q)->head);      \
-       lck_mtx_unlock_always(&(q)->lock_data);         \
-MACRO_END
-
-#endif /* MACH_KERNEL_PRIVATE */

 
 __END_DECLS
 
 
 __END_DECLS
 

-#endif /* _KERN_QUEUE_H_ */
+#endif  /* _KERN_QUEUE_H_ */