osfmk/kern/queue.h

   1 /*
   2  * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /*
  29  * @OSF_COPYRIGHT@
  30  */
  31 /*
  32  * Mach Operating System
  33  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
  34  * All Rights Reserved.
  35  *
  36  * Permission to use, copy, modify and distribute this software and its
  37  * documentation is hereby granted, provided that both the copyright
  38  * notice and this permission notice appear in all copies of the
  39  * software, derivative works or modified versions, and any portions
  40  * thereof, and that both notices appear in supporting documentation.
  41  *
  42  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  43  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  44  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  45  *
  46  * Carnegie Mellon requests users of this software to return to
  47  *
  48  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  49  *  School of Computer Science
  50  *  Carnegie Mellon University
  51  *  Pittsburgh PA 15213-3890
  52  *
  53  * any improvements or extensions that they make and grant Carnegie Mellon rights
  54  * to redistribute these changes.
  55  */
  56 /*
  57  */
  58 /*
  59  *      File:   queue.h
  60  *      Author: Avadis Tevanian, Jr.
  61  *      Date:   1985
  62  *
  63  *      Type definitions for generic queues.
  64  *
  65  */
  66
  67 #ifndef _KERN_QUEUE_H_
  68 #define _KERN_QUEUE_H_
  69
  70 #include <mach/mach_types.h>
  71 #include <kern/macro_help.h>
  72
  73 #include <sys/cdefs.h>
  74
  75 __BEGIN_DECLS
  76
  77 /*
  78  *      Queue of abstract objects.  Queue is maintained
  79  *      within that object.
  80  *
  81  *      Supports fast removal from within the queue.
  82  *
  83  *      How to declare a queue of elements of type "foo_t":
  84  *              In the "*foo_t" type, you must have a field of
  85  *              type "queue_chain_t" to hold together this queue.
  86  *              There may be more than one chain through a
  87  *              "foo_t", for use by different queues.
  88  *
  89  *              Declare the queue as a "queue_t" type.
  90  *
  91  *              Elements of the queue (of type "foo_t", that is)
  92  *              are referred to by reference, and cast to type
  93  *              "queue_entry_t" within this module.
  94  */
  95
  96 /*
  97  *      A generic doubly-linked list (queue).
  98  */
  99
 100 struct queue_entry {
 101         struct queue_entry      *next;          /* next element */
 102         struct queue_entry      *prev;          /* previous element */
 103 };
 104
 105 typedef struct queue_entry      *queue_t;
 106 typedef struct queue_entry      queue_head_t;
 107 typedef struct queue_entry      queue_chain_t;
 108 typedef struct queue_entry      *queue_entry_t;
 109
 110 /*
 111  *      enqueue puts "elt" on the "queue".
 112  *      dequeue returns the first element in the "queue".
 113  *      remqueue removes the specified "elt" from its queue.
 114  */
 115
 116 #define enqueue(queue,elt)      enqueue_tail(queue, elt)
 117 #define dequeue(queue)          dequeue_head(queue)
 118
 119 #ifdef XNU_KERNEL_PRIVATE
 120 #include <kern/debug.h>
 121 #include <mach/branch_predicates.h>
 122 static inline void __QUEUE_ELT_VALIDATE(queue_entry_t elt) {
 123         queue_entry_t   elt_next, elt_prev;
 124
 125         if (__improbable(elt == (queue_entry_t)0)) {
 126                 panic("Invalid queue element %p", elt);
 127         }
 128
 129         elt_next = elt->next;
 130         elt_prev = elt->prev;
 131
 132         if (__improbable(elt_next == (queue_entry_t)0 || elt_prev == (queue_entry_t)0)) {
 133                 panic("Invalid queue element pointers for %p: next %p prev %p", elt, elt_next, elt_prev);
 134         }
 135         if (__improbable(elt_next->prev != elt || elt_prev->next != elt)) {
 136                 panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p",
 137                           elt, elt_next, elt_next->prev, elt_prev, elt_prev->next);
 138         }
 139 }
 140
 141 static inline void __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) {
 142         (elt)->next = (queue_entry_t) 0;
 143         (elt)->prev = (queue_entry_t) 0;
 144 }
 145 #else
 146 #define __QUEUE_ELT_VALIDATE(elt) do { } while (0)
 147 #define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0)
 148 #endif /* !XNU_KERNEL_PRIVATE */
 149
 150 static __inline__ void
 151 enqueue_head(
 152         queue_t         que,
 153         queue_entry_t   elt)
 154 {
 155         queue_entry_t   old_head;
 156
 157         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 158         old_head = que->next;
 159         elt->next = old_head;
 160         elt->prev = que;
 161         old_head->prev = elt;
 162         que->next = elt;
 163 }
 164
 165 static __inline__ void
 166 enqueue_tail(
 167                 queue_t         que,
 168                 queue_entry_t   elt)
 169 {
 170         queue_entry_t   old_tail;
 171
 172         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 173         old_tail = que->prev;
 174         elt->next = que;
 175         elt->prev = old_tail;
 176         old_tail->next = elt;
 177         que->prev = elt;
 178 }
 179
 180 static __inline__ queue_entry_t
 181 dequeue_head(
 182         queue_t que)
 183 {
 184         queue_entry_t   elt = (queue_entry_t) 0;
 185         queue_entry_t   new_head;
 186
 187         if (que->next != que) {
 188                 elt = que->next;
 189                 __QUEUE_ELT_VALIDATE(elt);
 190                 new_head = elt->next; /* new_head may point to que if elt was the only element */
 191                 new_head->prev = que;
 192                 que->next = new_head;
 193                 __DEQUEUE_ELT_CLEANUP(elt);
 194         }
 195
 196         return (elt);
 197 }
 198
 199 static __inline__ queue_entry_t
 200 dequeue_tail(
 201         queue_t que)
 202 {
 203         queue_entry_t   elt = (queue_entry_t) 0;
 204         queue_entry_t   new_tail;
 205
 206         if (que->prev != que) {
 207                 elt = que->prev;
 208                 __QUEUE_ELT_VALIDATE(elt);
 209                 new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */
 210                 new_tail->next = que;
 211                 que->prev = new_tail;
 212                 __DEQUEUE_ELT_CLEANUP(elt);
 213         }
 214
 215         return (elt);
 216 }
 217
 218 static __inline__ void
 219 remqueue(
 220         queue_entry_t   elt)
 221 {
 222         queue_entry_t   next_elt, prev_elt;
 223
 224         __QUEUE_ELT_VALIDATE(elt);
 225         next_elt = elt->next;
 226         prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 227         next_elt->prev = prev_elt;
 228         prev_elt->next = next_elt;
 229         __DEQUEUE_ELT_CLEANUP(elt);
 230 }
 231
 232 static __inline__ void
 233 insque(
 234         queue_entry_t   entry,
 235         queue_entry_t   pred)
 236 {
 237         queue_entry_t   successor;
 238
 239         __QUEUE_ELT_VALIDATE(pred);
 240         successor = pred->next;
 241         entry->next = successor;
 242         entry->prev = pred;
 243         successor->prev = entry;
 244         pred->next = entry;
 245 }
 246
 247 static __inline__ void
 248 remque(
 249         queue_entry_t elt)
 250 {
 251         queue_entry_t   next_elt, prev_elt;
 252
 253         __QUEUE_ELT_VALIDATE(elt);
 254         next_elt = elt->next;
 255         prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 256         next_elt->prev = prev_elt;
 257         prev_elt->next = next_elt;
 258         __DEQUEUE_ELT_CLEANUP(elt);
 259 }
 260
 261 /*
 262  *      Macro:          queue_init
 263  *      Function:
 264  *              Initialize the given queue.
 265  *      Header:
 266  *              void queue_init(q)
 267  *                      queue_t         q;      \* MODIFIED *\
 268  */
 269 #define queue_init(q)   \
 270 MACRO_BEGIN             \
 271         (q)->next = (q);\
 272         (q)->prev = (q);\
 273 MACRO_END
 274
 275 /*
 276  *      Macro:          queue_first
 277  *      Function:
 278  *              Returns the first entry in the queue,
 279  *      Header:
 280  *              queue_entry_t queue_first(q)
 281  *                      queue_t q;              \* IN *\
 282  */
 283 #define queue_first(q)  ((q)->next)
 284
 285 /*
 286  *      Macro:          queue_next
 287  *      Function:
 288  *              Returns the entry after an item in the queue.
 289  *      Header:
 290  *              queue_entry_t queue_next(qc)
 291  *                      queue_t qc;
 292  */
 293 #define queue_next(qc)  ((qc)->next)
 294
 295 /*
 296  *      Macro:          queue_last
 297  *      Function:
 298  *              Returns the last entry in the queue.
 299  *      Header:
 300  *              queue_entry_t queue_last(q)
 301  *                      queue_t q;              \* IN *\
 302  */
 303 #define queue_last(q)   ((q)->prev)
 304
 305 /*
 306  *      Macro:          queue_prev
 307  *      Function:
 308  *              Returns the entry before an item in the queue.
 309  *      Header:
 310  *              queue_entry_t queue_prev(qc)
 311  *                      queue_t qc;
 312  */
 313 #define queue_prev(qc)  ((qc)->prev)
 314
 315 /*
 316  *      Macro:          queue_end
 317  *      Function:
 318  *              Tests whether a new entry is really the end of
 319  *              the queue.
 320  *      Header:
 321  *              boolean_t queue_end(q, qe)
 322  *                      queue_t q;
 323  *                      queue_entry_t qe;
 324  */
 325 #define queue_end(q, qe)        ((q) == (qe))
 326
 327 /*
 328  *      Macro:          queue_empty
 329  *      Function:
 330  *              Tests whether a queue is empty.
 331  *      Header:
 332  *              boolean_t queue_empty(q)
 333  *                      queue_t q;
 334  */
 335 #define queue_empty(q)          queue_end((q), queue_first(q))
 336
 337
 338 /*----------------------------------------------------------------*/
 339 /*
 340  * Macros that operate on generic structures.  The queue
 341  * chain may be at any location within the structure, and there
 342  * may be more than one chain.
 343  */
 344
 345 /*
 346  *      Macro:          queue_enter
 347  *      Function:
 348  *              Insert a new element at the tail of the queue.
 349  *      Header:
 350  *              void queue_enter(q, elt, type, field)
 351  *                      queue_t q;
 352  *                      <type> elt;
 353  *                      <type> is what's in our queue
 354  *                      <field> is the chain field in (*<type>)
 355  */
 356 #define queue_enter(head, elt, type, field)                     \
 357 MACRO_BEGIN                                                     \
 358         queue_entry_t __prev;                                   \
 359                                                                 \
 360         __prev = (head)->prev;                                  \
 361         if ((head) == __prev) {                                 \
 362                 (head)->next = (queue_entry_t) (elt);           \
 363         }                                                       \
 364         else {                                                  \
 365                 ((type)(void *)__prev)->field.next =            \
 366                         (queue_entry_t)(elt);                   \
 367         }                                                       \
 368         (elt)->field.prev = __prev;                             \
 369         (elt)->field.next = head;                               \
 370         (head)->prev = (queue_entry_t) elt;                     \
 371 MACRO_END
 372
 373 /*
 374  *      Macro:          queue_enter_first
 375  *      Function:
 376  *              Insert a new element at the head of the queue.
 377  *      Header:
 378  *              void queue_enter_first(q, elt, type, field)
 379  *                      queue_t q;
 380  *                      <type> elt;
 381  *                      <type> is what's in our queue
 382  *                      <field> is the chain field in (*<type>)
 383  */
 384 #define queue_enter_first(head, elt, type, field)               \
 385 MACRO_BEGIN                                                     \
 386         queue_entry_t __next;                                   \
 387                                                                 \
 388         __next = (head)->next;                                  \
 389         if ((head) == __next) {                                 \
 390                 (head)->prev = (queue_entry_t) (elt);           \
 391         }                                                       \
 392         else {                                                  \
 393                 ((type)(void *)__next)->field.prev =            \
 394                         (queue_entry_t)(elt);                   \
 395         }                                                       \
 396         (elt)->field.next = __next;                             \
 397         (elt)->field.prev = head;                               \
 398         (head)->next = (queue_entry_t) elt;                     \
 399 MACRO_END
 400
 401 /*
 402  *      Macro:          queue_insert_before
 403  *      Function:
 404  *              Insert a new element before a given element.
 405  *      Header:
 406  *              void queue_insert_before(q, elt, cur, type, field)
 407  *                      queue_t q;
 408  *                      <type> elt;
 409  *                      <type> cur;
 410  *                      <type> is what's in our queue
 411  *                      <field> is the chain field in (*<type>)
 412  */
 413 #define queue_insert_before(head, elt, cur, type, field)                \
 414 MACRO_BEGIN                                                             \
 415         queue_entry_t __prev;                                           \
 416                                                                         \
 417         if ((head) == (queue_entry_t)(cur)) {                           \
 418                 (elt)->field.next = (head);                             \
 419                 if ((head)->next == (head)) {   /* only element */      \
 420                         (elt)->field.prev = (head);                     \
 421                         (head)->next = (queue_entry_t)(elt);            \
 422                 } else {                        /* last element */      \
 423                         __prev = (elt)->field.prev = (head)->prev;      \
 424                         ((type)(void *)__prev)->field.next =            \
 425                                 (queue_entry_t)(elt);                   \
 426                 }                                                       \
 427                 (head)->prev = (queue_entry_t)(elt);                    \
 428         } else {                                                        \
 429                 (elt)->field.next = (queue_entry_t)(cur);               \
 430                 if ((head)->next == (queue_entry_t)(cur)) {             \
 431                                                 /* first element */     \
 432                         (elt)->field.prev = (head);                     \
 433                         (head)->next = (queue_entry_t)(elt);            \
 434                 } else {                        /* middle element */    \
 435                         __prev = (elt)->field.prev = (cur)->field.prev; \
 436                         ((type)(void *)__prev)->field.next =            \
 437                                 (queue_entry_t)(elt);                   \
 438                 }                                                       \
 439                 (cur)->field.prev = (queue_entry_t)(elt);               \
 440         }                                                               \
 441 MACRO_END
 442
 443 /*
 444  *      Macro:          queue_insert_after
 445  *      Function:
 446  *              Insert a new element after a given element.
 447  *      Header:
 448  *              void queue_insert_after(q, elt, cur, type, field)
 449  *                      queue_t q;
 450  *                      <type> elt;
 451  *                      <type> cur;
 452  *                      <type> is what's in our queue
 453  *                      <field> is the chain field in (*<type>)
 454  */
 455 #define queue_insert_after(head, elt, cur, type, field)                 \
 456 MACRO_BEGIN                                                             \
 457         queue_entry_t __next;                                           \
 458                                                                         \
 459         if ((head) == (queue_entry_t)(cur)) {                           \
 460                 (elt)->field.prev = (head);                             \
 461                 if ((head)->next == (head)) {   /* only element */      \
 462                         (elt)->field.next = (head);                     \
 463                         (head)->prev = (queue_entry_t)(elt);            \
 464                 } else {                        /* first element */     \
 465                         __next = (elt)->field.next = (head)->next;      \
 466                         ((type)(void *)__next)->field.prev =            \
 467                                 (queue_entry_t)(elt);                   \
 468                 }                                                       \
 469                 (head)->next = (queue_entry_t)(elt);                    \
 470         } else {                                                        \
 471                 (elt)->field.prev = (queue_entry_t)(cur);               \
 472                 if ((head)->prev == (queue_entry_t)(cur)) {             \
 473                                                 /* last element */      \
 474                         (elt)->field.next = (head);                     \
 475                         (head)->prev = (queue_entry_t)(elt);            \
 476                 } else {                        /* middle element */    \
 477                         __next = (elt)->field.next = (cur)->field.next; \
 478                         ((type)(void *)__next)->field.prev =            \
 479                                 (queue_entry_t)(elt);                   \
 480                 }                                                       \
 481                 (cur)->field.next = (queue_entry_t)(elt);               \
 482         }                                                               \
 483 MACRO_END
 484
 485 /*
 486  *      Macro:          queue_field [internal use only]
 487  *      Function:
 488  *              Find the queue_chain_t (or queue_t) for the
 489  *              given element (thing) in the given queue (head)
 490  */
 491 #define queue_field(head, thing, type, field)                   \
 492                 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
 493
 494 /*
 495  *      Macro:          queue_remove
 496  *      Function:
 497  *              Remove an arbitrary item from the queue.
 498  *      Header:
 499  *              void queue_remove(q, qe, type, field)
 500  *                      arguments as in queue_enter
 501  */
 502 #define queue_remove(head, elt, type, field)                    \
 503 MACRO_BEGIN                                                     \
 504         queue_entry_t   __next, __prev;                         \
 505                                                                 \
 506         __next = (elt)->field.next;                             \
 507         __prev = (elt)->field.prev;                             \
 508                                                                 \
 509         if ((head) == __next)                                   \
 510                 (head)->prev = __prev;                          \
 511         else                                                    \
 512                 ((type)(void *)__next)->field.prev = __prev;    \
 513                                                                 \
 514         if ((head) == __prev)                                   \
 515                 (head)->next = __next;                          \
 516         else                                                    \
 517                 ((type)(void *)__prev)->field.next = __next;    \
 518                                                                 \
 519         (elt)->field.next = NULL;                               \
 520         (elt)->field.prev = NULL;                               \
 521 MACRO_END
 522
 523 /*
 524  *      Macro:          queue_remove_first
 525  *      Function:
 526  *              Remove and return the entry at the head of
 527  *              the queue.
 528  *      Header:
 529  *              queue_remove_first(head, entry, type, field)
 530  *              entry is returned by reference
 531  */
 532 #define queue_remove_first(head, entry, type, field)            \
 533 MACRO_BEGIN                                                     \
 534         queue_entry_t   __next;                                 \
 535                                                                 \
 536         (entry) = (type)(void *) ((head)->next);                \
 537         __next = (entry)->field.next;                           \
 538                                                                 \
 539         if ((head) == __next)                                   \
 540                 (head)->prev = (head);                          \
 541         else                                                    \
 542                 ((type)(void *)(__next))->field.prev = (head);  \
 543         (head)->next = __next;                                  \
 544                                                                 \
 545         (entry)->field.next = NULL;                             \
 546         (entry)->field.prev = NULL;                             \
 547 MACRO_END
 548
 549 /*
 550  *      Macro:          queue_remove_last
 551  *      Function:
 552  *              Remove and return the entry at the tail of
 553  *              the queue.
 554  *      Header:
 555  *              queue_remove_last(head, entry, type, field)
 556  *              entry is returned by reference
 557  */
 558 #define queue_remove_last(head, entry, type, field)             \
 559 MACRO_BEGIN                                                     \
 560         queue_entry_t   __prev;                                 \
 561                                                                 \
 562         (entry) = (type)(void *) ((head)->prev);                \
 563         __prev = (entry)->field.prev;                           \
 564                                                                 \
 565         if ((head) == __prev)                                   \
 566                 (head)->next = (head);                          \
 567         else                                                    \
 568                 ((type)(void *)(__prev))->field.next = (head);  \
 569         (head)->prev = __prev;                                  \
 570                                                                 \
 571         (entry)->field.next = NULL;                             \
 572         (entry)->field.prev = NULL;                             \
 573 MACRO_END
 574
 575 /*
 576  *      Macro:          queue_assign
 577  */
 578 #define queue_assign(to, from, type, field)                     \
 579 MACRO_BEGIN                                                     \
 580         ((type)(void *)((from)->prev))->field.next = (to);      \
 581         ((type)(void *)((from)->next))->field.prev = (to);      \
 582         *to = *from;                                            \
 583 MACRO_END
 584
 585 /*
 586  *      Macro:          queue_new_head
 587  *      Function:
 588  *              rebase old queue to new queue head
 589  *      Header:
 590  *              queue_new_head(old, new, type, field)
 591  *                      queue_t old;
 592  *                      queue_t new;
 593  *                      <type> is what's in our queue
 594  *                      <field> is the chain field in (*<type>)
 595  */
 596 #define queue_new_head(old, new, type, field)                   \
 597 MACRO_BEGIN                                                     \
 598         if (!queue_empty(old)) {                                \
 599                 *(new) = *(old);                                \
 600                 ((type)(void *)((new)->next))->field.prev =     \
 601                         (new);                                  \
 602                 ((type)(void *)((new)->prev))->field.next =     \
 603                         (new);                                  \
 604         } else {                                                \
 605                 queue_init(new);                                \
 606         }                                                       \
 607 MACRO_END
 608
 609 /*
 610  *      Macro:          queue_iterate
 611  *      Function:
 612  *              iterate over each item in the queue.
 613  *              Generates a 'for' loop, setting elt to
 614  *              each item in turn (by reference).
 615  *      Header:
 616  *              queue_iterate(q, elt, type, field)
 617  *                      queue_t q;
 618  *                      <type> elt;
 619  *                      <type> is what's in our queue
 620  *                      <field> is the chain field in (*<type>)
 621  */
 622 #define queue_iterate(head, elt, type, field)                   \
 623         for ((elt) = (type)(void *) queue_first(head);          \
 624              !queue_end((head), (queue_entry_t)(elt));          \
 625              (elt) = (type)(void *) queue_next(&(elt)->field))
 626
 627 #ifdef  MACH_KERNEL_PRIVATE
 628
 629 #include <kern/locks.h>
 630
 631 /*----------------------------------------------------------------*/
 632 /*
 633  *      Define macros for queues with locks.
 634  */
 635 struct mpqueue_head {
 636         struct queue_entry      head;           /* header for queue */
 637         uint64_t                earliest_soft_deadline;
 638         uint64_t                count;
 639 #if defined(__i386__) || defined(__x86_64__)
 640         lck_mtx_t               lock_data;
 641         lck_mtx_ext_t           lock_data_ext;
 642 #else
 643         lck_spin_t              lock_data;
 644 #endif
 645 };
 646
 647 typedef struct mpqueue_head     mpqueue_head_t;
 648
 649 #define round_mpq(size)         (size)
 650
 651
 652 #if defined(__i386__) || defined(__x86_64__)
 653
 654 #define mpqueue_init(q, lck_grp, lck_attr)              \
 655 MACRO_BEGIN                                             \
 656         queue_init(&(q)->head);                         \
 657         lck_mtx_init_ext(&(q)->lock_data,               \
 658                          &(q)->lock_data_ext,           \
 659                          lck_grp,                       \
 660                          lck_attr);                     \
 661         (q)->earliest_soft_deadline = UINT64_MAX;       \
 662         (q)->count = 0;                                 \
 663 MACRO_END
 664
 665 #else
 666
 667 #define mpqueue_init(q, lck_grp, lck_attr)              \
 668 MACRO_BEGIN                                             \
 669         queue_init(&(q)->head);                         \
 670         lck_spin_init(&(q)->lock_data,                  \
 671                       lck_grp,                          \
 672                       lck_attr);                        \
 673 MACRO_END
 674 #endif
 675
 676
 677 #define mpenqueue_tail(q, elt)                          \
 678 MACRO_BEGIN                                             \
 679         lck_mtx_lock_spin_always(&(q)->lock_data);      \
 680         enqueue_tail(&(q)->head, elt);                  \
 681         lck_mtx_unlock_always(&(q)->lock_data);         \
 682 MACRO_END
 683
 684 #define mpdequeue_head(q, elt)                          \
 685 MACRO_BEGIN                                             \
 686         lck_mtx_lock_spin_always(&(q)->lock_data);      \
 687         if (queue_empty(&(q)->head))                    \
 688                 *(elt) = 0;                             \
 689         else                                            \
 690                 *(elt) = dequeue_head(&(q)->head);      \
 691         lck_mtx_unlock_always(&(q)->lock_data);         \
 692 MACRO_END
 693
 694 #endif  /* MACH_KERNEL_PRIVATE */
 695
 696 __END_DECLS
 697
 698 #endif  /* _KERN_QUEUE_H_ */