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 Management APIs
  79  *
  80  * There are currently two subtly different methods of maintining
  81  * a queue of objects. Both APIs are contained in this file, and
  82  * unfortunately overlap.
  83  * (there is also a third way maintained in bsd/sys/queue.h)
  84  *
  85  * Both methods use a common queue head and linkage pattern:
  86  *      The head of a queue is declared as:
  87  *              queue_head_t q_head;
  88  *
  89  *      Elements in this queue are chained together using
  90  *      struct queue_entry objects embedded within a structure:
  91  *              struct some_data {
  92  *                      int field1;
  93  *                      int field2;
  94  *                      ...
  95  *                      queue_chain_t link;
  96  *                      ...
  97  *                      int last_field;
  98  *              };
  99  *      struct some_data is referred to as the queue "element."
 100  *      (note that queue_chain_t is typedef'd to struct queue_entry)
 101  *
 102  * IMPORTANT: The two queue iteration methods described below are not
 103  *            compatible with one another. You must choose one and be careful
 104  *            to use only the supported APIs for that method.
 105  *
 106  * Method 1: chaining of queue_chain_t (linkage chains)
 107  *      This method uses the next and prev pointers of the struct queue_entry
 108  *      linkage object embedded in a queue element to point to the next or
 109  *      previous queue_entry structure in the chain. The head of the queue
 110  *      (the queue_head_t object) will point to the first and last
 111  *      struct queue_entry object, and both the next and prev pointer will
 112  *      point back to the head if the queue is empty.
 113  *
 114  *      This method is the most flexible method of chaining objects together
 115  *      as it allows multiple chains through a given object, by embedding
 116  *      multiple queue_chain_t objects in the structure, while simultaneously
 117  *      providing fast removal and insertion into the queue using only
 118  *      struct queue_entry object pointers.
 119  *
 120  *      ++ Valid APIs for this style queue ++
 121  *      -------------------------------------
 122  *              [C] queue_init
 123  *              [C] queue_first
 124  *              [C] queue_next
 125  *              [C] queue_last
 126  *              [C] queue_prev
 127  *              [C] queue_end
 128  *              [C] queue_empty
 129  *
 130  *              [1] enqueue
 131  *              [1] dequeue
 132  *              [1] enqueue_head
 133  *              [1] enqueue_tail
 134  *              [1] dequeue_head
 135  *              [1] dequeue_tail
 136  *              [1] remqueue
 137  *              [1] insque
 138  *              [1] remque
 139  *              [1] re_queue_head
 140  *              [1] re_queue_tail
 141  *              [1] movqueue
 142  *              [1] qe_element
 143  *              [1] qe_foreach
 144  *              [1] qe_foreach_safe
 145  *              [1] qe_foreach_element
 146  *              [1] qe_foreach_element_safe
 147  *
 148  * Method 2: chaining of elements (element chains)
 149  *      This method uses the next and prev pointers of the struct queue_entry
 150  *      linkage object embedded in a queue element to point to the next or
 151  *      previous queue element (not another queue_entry). The head of the
 152  *      queue will point to the first and last queue element (struct some_data
 153  *      from the above example) NOT the embedded queue_entry structure. The
 154  *      first queue element will have a prev pointer that points to the
 155  *      queue_head_t, and the last queue element will have a next pointer
 156  *      that points to the queue_head_t.
 157  *
 158  *      This method requires knowledge of the queue_head_t of the queue on
 159  *      which an element resides in order to remove the element. Iterating
 160  *      through the elements of the queue is also more cumbersome because
 161  *      a check against the head pointer plus a cast then offset operation
 162  *      must be performed at each step of the iteration.
 163  *
 164  *      ++ Valid APIs for this style queue ++
 165  *      -------------------------------------
 166  *              [C] queue_init
 167  *              [C] queue_first
 168  *              [C] queue_next
 169  *              [C] queue_last
 170  *              [C] queue_prev
 171  *              [C] queue_end
 172  *              [C] queue_empty
 173  *
 174  *              [2] queue_enter
 175  *              [2] queue_enter_first
 176  *              [2] queue_insert_before
 177  *              [2] queue_insert_after
 178  *              [2] queue_field
 179  *              [2] queue_remove
 180  *              [2] queue_remove_first
 181  *              [2] queue_remove_last
 182  *              [2] queue_assign
 183  *              [2] queue_new_head
 184  *              [2] queue_iterate
 185  *
 186  * Legend:
 187  *      [C] -> API common to both methods
 188  *      [1] -> API used only in method 1 (linkage chains)
 189  *      [2] -> API used only in method 2 (element chains)
 190  */
 191
 192 /*
 193  *      A generic doubly-linked list (queue).
 194  */
 195
 196 struct queue_entry {
 197         struct queue_entry      *next;          /* next element */
 198         struct queue_entry      *prev;          /* previous element */
 199
 200 #if __arm__ && (__BIGGEST_ALIGNMENT__ > 4)
 201 /* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers
 202  * are 32-bit:
 203  * Since this type is so often cast to various 64-bit aligned types
 204  * aligning it to 64-bits will avoid -wcast-align without needing
 205  * to disable it entirely. The impact on memory footprint should be
 206  * negligible.
 207  */
 208 } __attribute__ ((aligned (8)));
 209 #else
 210 };
 211 #endif
 212
 213 typedef struct queue_entry      *queue_t;
 214 typedef struct queue_entry      queue_head_t;
 215 typedef struct queue_entry      queue_chain_t;
 216 typedef struct queue_entry      *queue_entry_t;
 217
 218 /*
 219  *      enqueue puts "elt" on the "queue".
 220  *      dequeue returns the first element in the "queue".
 221  *      remqueue removes the specified "elt" from its queue.
 222  */
 223
 224 #define enqueue(queue,elt)      enqueue_tail(queue, elt)
 225 #define dequeue(queue)          dequeue_head(queue)
 226
 227 #ifdef XNU_KERNEL_PRIVATE
 228 #include <kern/debug.h>
 229 #include <mach/branch_predicates.h>
 230 static inline void __QUEUE_ELT_VALIDATE(queue_entry_t elt) {
 231         queue_entry_t   elt_next, elt_prev;
 232
 233         if (__improbable(elt == (queue_entry_t)0)) {
 234                 panic("Invalid queue element %p", elt);
 235         }
 236
 237         elt_next = elt->next;
 238         elt_prev = elt->prev;
 239
 240         if (__improbable(elt_next == (queue_entry_t)0 || elt_prev == (queue_entry_t)0)) {
 241                 panic("Invalid queue element pointers for %p: next %p prev %p", elt, elt_next, elt_prev);
 242         }
 243         if (__improbable(elt_next->prev != elt || elt_prev->next != elt)) {
 244                 panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p",
 245                           elt, elt_next, elt_next->prev, elt_prev, elt_prev->next);
 246         }
 247 }
 248
 249 static inline void __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) {
 250         (elt)->next = (queue_entry_t) 0;
 251         (elt)->prev = (queue_entry_t) 0;
 252 }
 253 #else
 254 #define __QUEUE_ELT_VALIDATE(elt) do { } while (0)
 255 #define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0)
 256 #endif /* !XNU_KERNEL_PRIVATE */
 257
 258 static __inline__ void
 259 enqueue_head(
 260         queue_t         que,
 261         queue_entry_t   elt)
 262 {
 263         queue_entry_t   old_head;
 264
 265         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 266         old_head = que->next;
 267         elt->next = old_head;
 268         elt->prev = que;
 269         old_head->prev = elt;
 270         que->next = elt;
 271 }
 272
 273 static __inline__ void
 274 enqueue_tail(
 275                 queue_t         que,
 276                 queue_entry_t   elt)
 277 {
 278         queue_entry_t   old_tail;
 279
 280         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 281         old_tail = que->prev;
 282         elt->next = que;
 283         elt->prev = old_tail;
 284         old_tail->next = elt;
 285         que->prev = elt;
 286 }
 287
 288 static __inline__ queue_entry_t
 289 dequeue_head(
 290         queue_t que)
 291 {
 292         queue_entry_t   elt = (queue_entry_t) 0;
 293         queue_entry_t   new_head;
 294
 295         if (que->next != que) {
 296                 elt = que->next;
 297                 __QUEUE_ELT_VALIDATE(elt);
 298                 new_head = elt->next; /* new_head may point to que if elt was the only element */
 299                 new_head->prev = que;
 300                 que->next = new_head;
 301                 __DEQUEUE_ELT_CLEANUP(elt);
 302         }
 303
 304         return (elt);
 305 }
 306
 307 static __inline__ queue_entry_t
 308 dequeue_tail(
 309         queue_t que)
 310 {
 311         queue_entry_t   elt = (queue_entry_t) 0;
 312         queue_entry_t   new_tail;
 313
 314         if (que->prev != que) {
 315                 elt = que->prev;
 316                 __QUEUE_ELT_VALIDATE(elt);
 317                 new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */
 318                 new_tail->next = que;
 319                 que->prev = new_tail;
 320                 __DEQUEUE_ELT_CLEANUP(elt);
 321         }
 322
 323         return (elt);
 324 }
 325
 326 static __inline__ void
 327 remqueue(
 328         queue_entry_t   elt)
 329 {
 330         queue_entry_t   next_elt, prev_elt;
 331
 332         __QUEUE_ELT_VALIDATE(elt);
 333         next_elt = elt->next;
 334         prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 335         next_elt->prev = prev_elt;
 336         prev_elt->next = next_elt;
 337         __DEQUEUE_ELT_CLEANUP(elt);
 338 }
 339
 340 static __inline__ void
 341 insque(
 342         queue_entry_t   entry,
 343         queue_entry_t   pred)
 344 {
 345         queue_entry_t   successor;
 346
 347         __QUEUE_ELT_VALIDATE(pred);
 348         successor = pred->next;
 349         entry->next = successor;
 350         entry->prev = pred;
 351         successor->prev = entry;
 352         pred->next = entry;
 353 }
 354
 355 static __inline__ void
 356 remque(
 357         queue_entry_t elt)
 358 {
 359         queue_entry_t   next_elt, prev_elt;
 360
 361         __QUEUE_ELT_VALIDATE(elt);
 362         next_elt = elt->next;
 363         prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 364         next_elt->prev = prev_elt;
 365         prev_elt->next = next_elt;
 366         __DEQUEUE_ELT_CLEANUP(elt);
 367 }
 368
 369 /*
 370  *      Function:       re_queue_head
 371  *      Parameters:
 372  *              queue_t que       : queue onto which elt will be pre-pended
 373  *              queue_entry_t elt : element to re-queue
 374  *      Description:
 375  *              Remove elt from its current queue and put it onto the
 376  *              head of a new queue
 377  *      Note:
 378  *              This should only be used with Method 1 queue iteration (linkage chains)
 379  */
 380 static __inline__ void
 381 re_queue_head(queue_t que, queue_entry_t elt)
 382 {
 383         queue_entry_t   n_elt, p_elt;
 384
 385         __QUEUE_ELT_VALIDATE(elt);
 386         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 387
 388         /* remqueue */
 389         n_elt = elt->next;
 390         p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 391         n_elt->prev = p_elt;
 392         p_elt->next = n_elt;
 393
 394         /* enqueue_head */
 395         n_elt = que->next;
 396         elt->next = n_elt;
 397         elt->prev = que;
 398         n_elt->prev = elt;
 399         que->next = elt;
 400 }
 401
 402 /*
 403  *      Function:       re_queue_tail
 404  *      Parameters:
 405  *              queue_t que       : queue onto which elt will be appended
 406  *              queue_entry_t elt : element to re-queue
 407  *      Description:
 408  *              Remove elt from its current queue and put it onto the
 409  *              end of a new queue
 410  *      Note:
 411  *              This should only be used with Method 1 queue iteration (linkage chains)
 412  */
 413 static __inline__ void
 414 re_queue_tail(queue_t que, queue_entry_t elt)
 415 {
 416         queue_entry_t   n_elt, p_elt;
 417
 418         __QUEUE_ELT_VALIDATE(elt);
 419         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 420
 421         /* remqueue */
 422         n_elt = elt->next;
 423         p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 424         n_elt->prev = p_elt;
 425         p_elt->next = n_elt;
 426
 427         /* enqueue_tail */
 428         p_elt = que->prev;
 429         elt->next = que;
 430         elt->prev = p_elt;
 431         p_elt->next = elt;
 432         que->prev = elt;
 433 }
 434
 435 /*
 436  *      Macro:          qe_element
 437  *      Function:
 438  *              Convert a queue_entry_t to a queue element pointer.
 439  *              Get a pointer to the user-defined element containing
 440  *              a given queue_entry_t
 441  *      Header:
 442  *              <type> * qe_element(queue_entry_t qe, <type>, field)
 443  *                      qe      - queue entry to convert
 444  *                      <type>  - what's in the queue (e.g., struct some_data)
 445  *                      <field> - is the chain field in <type>
 446  *      Note:
 447  *              Do not use pointer types for <type>
 448  */
 449 #define qe_element(qe, type, field) \
 450         ((type *)((void *)((char *)(qe) - __offsetof(type, field))))
 451
 452 /*
 453  *      Macro:          qe_foreach
 454  *      Function:
 455  *              Iterate over each queue_entry_t structure.
 456  *              Generates a 'for' loop, setting 'qe' to
 457  *              each queue_entry_t in the queue.
 458  *      Header:
 459  *              qe_foreach(queue_entry_t qe, queue_t head)
 460  *                      qe   - iteration variable
 461  *                      head - pointer to queue_head_t (head of queue)
 462  *      Note:
 463  *              This should only be used with Method 1 queue iteration (linkage chains)
 464  */
 465 #define qe_foreach(qe, head) \
 466         for (qe = (head)->next; qe != (head); qe = (qe)->next)
 467
 468 /*
 469  *      Macro:          qe_foreach_safe
 470  *      Function:
 471  *              Safely iterate over each queue_entry_t structure.
 472  *
 473  *              Use this iterator macro if you plan to remove the
 474  *              queue_entry_t, qe, from the queue during the
 475  *              iteration.
 476  *      Header:
 477  *              qe_foreach_safe(queue_entry_t qe, queue_t head)
 478  *                      qe   - iteration variable
 479  *                      head - pointer to queue_head_t (head of queue)
 480  *      Note:
 481  *              This should only be used with Method 1 queue iteration (linkage chains)
 482  */
 483 #define qe_foreach_safe(qe, head) \
 484         for (queue_entry_t _ne = ((head)->next)->next, \
 485                  __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \
 486              qe != (head); \
 487              qe = _ne, _ne = (qe)->next)
 488
 489 /*
 490  *      Macro:          qe_foreach_element
 491  *      Function:
 492  *              Iterate over each _element_ in a queue
 493  *              where each queue_entry_t points to another
 494  *              queue_entry_t, i.e., managed by the [de|en]queue_head/
 495  *              [de|en]queue_tail / remqueue / etc. function.
 496  *      Header:
 497  *              qe_foreach_element(<type> *elt, queue_t head, <field>)
 498  *                      elt     - iteration variable
 499  *                      <type>  - what's in the queue (e.g., struct some_data)
 500  *                      <field> - is the chain field in <type>
 501  *      Note:
 502  *              This should only be used with Method 1 queue iteration (linkage chains)
 503  */
 504 #define qe_foreach_element(elt, head, field) \
 505         for (elt = qe_element((head)->next, typeof(*(elt)), field); \
 506              &((elt)->field) != (head); \
 507              elt = qe_element((elt)->field.next, typeof(*(elt)), field))
 508
 509 /*
 510  *      Macro:          qe_foreach_element_safe
 511  *      Function:
 512  *              Safely iterate over each _element_ in a queue
 513  *              where each queue_entry_t points to another
 514  *              queue_entry_t, i.e., managed by the [de|en]queue_head/
 515  *              [de|en]queue_tail / remqueue / etc. function.
 516  *
 517  *              Use this iterator macro if you plan to remove the
 518  *              element, elt, from the queue during the iteration.
 519  *      Header:
 520  *              qe_foreach_element_safe(<type> *elt, queue_t head, <field>)
 521  *                      elt     - iteration variable
 522  *                      <type>  - what's in the queue (e.g., struct some_data)
 523  *                      <field> - is the chain field in <type>
 524  *      Note:
 525  *              This should only be used with Method 1 queue iteration (linkage chains)
 526  */
 527 #define qe_foreach_element_safe(elt, head, field) \
 528         for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \
 529              *__ ## elt ## _unused_shadow __unused = \
 530                  (elt = qe_element((head)->next, typeof(*(elt)), field)); \
 531              &((elt)->field) != (head); \
 532              elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
 533
 534 #ifdef XNU_KERNEL_PRIVATE
 535
 536 /* Dequeue an element from head, or return NULL if the queue is empty */
 537 #define qe_dequeue_head(head, type, field) ({ \
 538         queue_entry_t _tmp_entry = dequeue_head((head)); \
 539         type *_tmp_element = (type*) NULL; \
 540         if (_tmp_entry != (queue_entry_t) NULL) \
 541                 _tmp_element = qe_element(_tmp_entry, type, field); \
 542         _tmp_element; \
 543 })
 544
 545 /* Dequeue an element from tail, or return NULL if the queue is empty */
 546 #define qe_dequeue_tail(head, type, field) ({ \
 547         queue_entry_t _tmp_entry = dequeue_tail((head)); \
 548         type *_tmp_element = (type*) NULL; \
 549         if (_tmp_entry != (queue_entry_t) NULL) \
 550                 _tmp_element = qe_element(_tmp_entry, type, field); \
 551         _tmp_element; \
 552 })
 553
 554 /* Peek at the first element, or return NULL if the queue is empty */
 555 #define qe_queue_first(head, type, field) ({ \
 556         queue_entry_t _tmp_entry = queue_first((head)); \
 557         type *_tmp_element = (type*) NULL; \
 558         if (_tmp_entry != (queue_entry_t) head) \
 559                 _tmp_element = qe_element(_tmp_entry, type, field); \
 560         _tmp_element; \
 561 })
 562
 563 /* Peek at the last element, or return NULL if the queue is empty */
 564 #define qe_queue_last(head, type, field) ({ \
 565         queue_entry_t _tmp_entry = queue_last((head)); \
 566         type *_tmp_element = (type*) NULL; \
 567         if (_tmp_entry != (queue_entry_t) head) \
 568                 _tmp_element = qe_element(_tmp_entry, type, field); \
 569         _tmp_element; \
 570 })
 571
 572 #endif /* XNU_KERNEL_PRIVATE */
 573
 574 /*
 575  *      Macro:          queue_init
 576  *      Function:
 577  *              Initialize the given queue.
 578  *      Header:
 579  *              void queue_init(q)
 580  *                      queue_t         q;      \* MODIFIED *\
 581  */
 582 #define queue_init(q)   \
 583 MACRO_BEGIN             \
 584         (q)->next = (q);\
 585         (q)->prev = (q);\
 586 MACRO_END
 587
 588 /*
 589  *      Macro:          queue_head_init
 590  *      Function:
 591  *              Initialize the given queue head
 592  *      Header:
 593  *              void queue_head_init(q)
 594  *                      queue_head_t    q;      \* MODIFIED *\
 595  */
 596 #define queue_head_init(q) \
 597         queue_init(&(q))
 598
 599 /*
 600  *      Macro:          queue_chain_init
 601  *      Function:
 602  *              Initialize the given queue chain element
 603  *      Header:
 604  *              void queue_chain_init(q)
 605  *                      queue_chain_t   q;      \* MODIFIED *\
 606  */
 607 #define queue_chain_init(q) \
 608         queue_init(&(q))
 609
 610 /*
 611  *      Macro:          queue_first
 612  *      Function:
 613  *              Returns the first entry in the queue,
 614  *      Header:
 615  *              queue_entry_t queue_first(q)
 616  *                      queue_t q;              \* IN *\
 617  */
 618 #define queue_first(q)  ((q)->next)
 619
 620 /*
 621  *      Macro:          queue_next
 622  *      Function:
 623  *              Returns the entry after an item in the queue.
 624  *      Header:
 625  *              queue_entry_t queue_next(qc)
 626  *                      queue_t qc;
 627  */
 628 #define queue_next(qc)  ((qc)->next)
 629
 630 /*
 631  *      Macro:          queue_last
 632  *      Function:
 633  *              Returns the last entry in the queue.
 634  *      Header:
 635  *              queue_entry_t queue_last(q)
 636  *                      queue_t q;              \* IN *\
 637  */
 638 #define queue_last(q)   ((q)->prev)
 639
 640 /*
 641  *      Macro:          queue_prev
 642  *      Function:
 643  *              Returns the entry before an item in the queue.
 644  *      Header:
 645  *              queue_entry_t queue_prev(qc)
 646  *                      queue_t qc;
 647  */
 648 #define queue_prev(qc)  ((qc)->prev)
 649
 650 /*
 651  *      Macro:          queue_end
 652  *      Function:
 653  *              Tests whether a new entry is really the end of
 654  *              the queue.
 655  *      Header:
 656  *              boolean_t queue_end(q, qe)
 657  *                      queue_t q;
 658  *                      queue_entry_t qe;
 659  */
 660 #define queue_end(q, qe)        ((q) == (qe))
 661
 662 /*
 663  *      Macro:          queue_empty
 664  *      Function:
 665  *              Tests whether a queue is empty.
 666  *      Header:
 667  *              boolean_t queue_empty(q)
 668  *                      queue_t q;
 669  */
 670 #define queue_empty(q)          queue_end((q), queue_first(q))
 671
 672 /*
 673  *      Function:       movqueue
 674  *      Parameters:
 675  *              queue_t _old : head of a queue whose items will be moved
 676  *              queue_t _new : new queue head onto which items will be moved
 677  *      Description:
 678  *              Rebase queue items in _old onto _new then re-initialize
 679  *              the _old object to an empty queue.
 680  *              Equivalent to the queue_new_head Method 2 macro
 681  *      Note:
 682  *              Similar to the queue_new_head macro, this macros is intented
 683  *              to function as an initializer method for '_new' and thus may
 684  *              leak any list items that happen to be on the '_new' list.
 685  *              This should only be used with Method 1 queue iteration (linkage chains)
 686  */
 687 static __inline__ void
 688 movqueue(queue_t _old, queue_t _new)
 689 {
 690         queue_entry_t   next_elt, prev_elt;
 691
 692         __QUEUE_ELT_VALIDATE((queue_entry_t)_old);
 693
 694         if (queue_empty(_old)) {
 695                 queue_init(_new);
 696                 return;
 697         }
 698
 699         /*
 700          * move the queue at _old to _new
 701          * and re-initialize _old
 702          */
 703         next_elt = _old->next;
 704         prev_elt = _old->prev;
 705
 706         _new->next = next_elt;
 707         _new->prev = prev_elt;
 708         next_elt->prev = _new;
 709         prev_elt->next = _new;
 710
 711         queue_init(_old);
 712 }
 713
 714 /*----------------------------------------------------------------*/
 715 /*
 716  * Macros that operate on generic structures.  The queue
 717  * chain may be at any location within the structure, and there
 718  * may be more than one chain.
 719  */
 720
 721 /*
 722  *      Macro:          queue_enter
 723  *      Function:
 724  *              Insert a new element at the tail of the queue.
 725  *      Header:
 726  *              void queue_enter(q, elt, type, field)
 727  *                      queue_t q;
 728  *                      <type> elt;
 729  *                      <type> is what's in our queue
 730  *                      <field> is the chain field in (*<type>)
 731  *      Note:
 732  *              This should only be used with Method 2 queue iteration (element chains)
 733  */
 734 #define queue_enter(head, elt, type, field)                     \
 735 MACRO_BEGIN                                                     \
 736         queue_entry_t __prev;                                   \
 737                                                                 \
 738         __prev = (head)->prev;                                  \
 739         if ((head) == __prev) {                                 \
 740                 (head)->next = (queue_entry_t) (elt);           \
 741         }                                                       \
 742         else {                                                  \
 743                 ((type)(void *)__prev)->field.next =            \
 744                         (queue_entry_t)(elt);                   \
 745         }                                                       \
 746         (elt)->field.prev = __prev;                             \
 747         (elt)->field.next = head;                               \
 748         (head)->prev = (queue_entry_t) elt;                     \
 749 MACRO_END
 750
 751 /*
 752  *      Macro:          queue_enter_first
 753  *      Function:
 754  *              Insert a new element at the head of the queue.
 755  *      Header:
 756  *              void queue_enter_first(q, elt, type, field)
 757  *                      queue_t q;
 758  *                      <type> elt;
 759  *                      <type> is what's in our queue
 760  *                      <field> is the chain field in (*<type>)
 761  *      Note:
 762  *              This should only be used with Method 2 queue iteration (element chains)
 763  */
 764 #define queue_enter_first(head, elt, type, field)               \
 765 MACRO_BEGIN                                                     \
 766         queue_entry_t __next;                                   \
 767                                                                 \
 768         __next = (head)->next;                                  \
 769         if ((head) == __next) {                                 \
 770                 (head)->prev = (queue_entry_t) (elt);           \
 771         }                                                       \
 772         else {                                                  \
 773                 ((type)(void *)__next)->field.prev =            \
 774                         (queue_entry_t)(elt);                   \
 775         }                                                       \
 776         (elt)->field.next = __next;                             \
 777         (elt)->field.prev = head;                               \
 778         (head)->next = (queue_entry_t) elt;                     \
 779 MACRO_END
 780
 781 /*
 782  *      Macro:          queue_insert_before
 783  *      Function:
 784  *              Insert a new element before a given element.
 785  *      Header:
 786  *              void queue_insert_before(q, elt, cur, type, field)
 787  *                      queue_t q;
 788  *                      <type> elt;
 789  *                      <type> cur;
 790  *                      <type> is what's in our queue
 791  *                      <field> is the chain field in (*<type>)
 792  *      Note:
 793  *              This should only be used with Method 2 queue iteration (element chains)
 794  */
 795 #define queue_insert_before(head, elt, cur, type, field)                \
 796 MACRO_BEGIN                                                             \
 797         queue_entry_t __prev;                                           \
 798                                                                         \
 799         if ((head) == (queue_entry_t)(cur)) {                           \
 800                 (elt)->field.next = (head);                             \
 801                 if ((head)->next == (head)) {   /* only element */      \
 802                         (elt)->field.prev = (head);                     \
 803                         (head)->next = (queue_entry_t)(elt);            \
 804                 } else {                        /* last element */      \
 805                         __prev = (elt)->field.prev = (head)->prev;      \
 806                         ((type)(void *)__prev)->field.next =            \
 807                                 (queue_entry_t)(elt);                   \
 808                 }                                                       \
 809                 (head)->prev = (queue_entry_t)(elt);                    \
 810         } else {                                                        \
 811                 (elt)->field.next = (queue_entry_t)(cur);               \
 812                 if ((head)->next == (queue_entry_t)(cur)) {             \
 813                                                 /* first element */     \
 814                         (elt)->field.prev = (head);                     \
 815                         (head)->next = (queue_entry_t)(elt);            \
 816                 } else {                        /* middle element */    \
 817                         __prev = (elt)->field.prev = (cur)->field.prev; \
 818                         ((type)(void *)__prev)->field.next =            \
 819                                 (queue_entry_t)(elt);                   \
 820                 }                                                       \
 821                 (cur)->field.prev = (queue_entry_t)(elt);               \
 822         }                                                               \
 823 MACRO_END
 824
 825 /*
 826  *      Macro:          queue_insert_after
 827  *      Function:
 828  *              Insert a new element after a given element.
 829  *      Header:
 830  *              void queue_insert_after(q, elt, cur, type, field)
 831  *                      queue_t q;
 832  *                      <type> elt;
 833  *                      <type> cur;
 834  *                      <type> is what's in our queue
 835  *                      <field> is the chain field in (*<type>)
 836  *      Note:
 837  *              This should only be used with Method 2 queue iteration (element chains)
 838  */
 839 #define queue_insert_after(head, elt, cur, type, field)                 \
 840 MACRO_BEGIN                                                             \
 841         queue_entry_t __next;                                           \
 842                                                                         \
 843         if ((head) == (queue_entry_t)(cur)) {                           \
 844                 (elt)->field.prev = (head);                             \
 845                 if ((head)->next == (head)) {   /* only element */      \
 846                         (elt)->field.next = (head);                     \
 847                         (head)->prev = (queue_entry_t)(elt);            \
 848                 } else {                        /* first element */     \
 849                         __next = (elt)->field.next = (head)->next;      \
 850                         ((type)(void *)__next)->field.prev =            \
 851                                 (queue_entry_t)(elt);                   \
 852                 }                                                       \
 853                 (head)->next = (queue_entry_t)(elt);                    \
 854         } else {                                                        \
 855                 (elt)->field.prev = (queue_entry_t)(cur);               \
 856                 if ((head)->prev == (queue_entry_t)(cur)) {             \
 857                                                 /* last element */      \
 858                         (elt)->field.next = (head);                     \
 859                         (head)->prev = (queue_entry_t)(elt);            \
 860                 } else {                        /* middle element */    \
 861                         __next = (elt)->field.next = (cur)->field.next; \
 862                         ((type)(void *)__next)->field.prev =            \
 863                                 (queue_entry_t)(elt);                   \
 864                 }                                                       \
 865                 (cur)->field.next = (queue_entry_t)(elt);               \
 866         }                                                               \
 867 MACRO_END
 868
 869 /*
 870  *      Macro:          queue_field [internal use only]
 871  *      Function:
 872  *              Find the queue_chain_t (or queue_t) for the
 873  *              given element (thing) in the given queue (head)
 874  *      Note:
 875  *              This should only be used with Method 2 queue iteration (element chains)
 876  */
 877 #define queue_field(head, thing, type, field)                   \
 878                 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
 879
 880 /*
 881  *      Macro:          queue_remove
 882  *      Function:
 883  *              Remove an arbitrary item from the queue.
 884  *      Header:
 885  *              void queue_remove(q, qe, type, field)
 886  *                      arguments as in queue_enter
 887  *      Note:
 888  *              This should only be used with Method 2 queue iteration (element chains)
 889  */
 890 #define queue_remove(head, elt, type, field)                    \
 891 MACRO_BEGIN                                                     \
 892         queue_entry_t   __next, __prev;                         \
 893                                                                 \
 894         __next = (elt)->field.next;                             \
 895         __prev = (elt)->field.prev;                             \
 896                                                                 \
 897         if ((head) == __next)                                   \
 898                 (head)->prev = __prev;                          \
 899         else                                                    \
 900                 ((type)(void *)__next)->field.prev = __prev;    \
 901                                                                 \
 902         if ((head) == __prev)                                   \
 903                 (head)->next = __next;                          \
 904         else                                                    \
 905                 ((type)(void *)__prev)->field.next = __next;    \
 906                                                                 \
 907         (elt)->field.next = NULL;                               \
 908         (elt)->field.prev = NULL;                               \
 909 MACRO_END
 910
 911 /*
 912  *      Macro:          queue_remove_first
 913  *      Function:
 914  *              Remove and return the entry at the head of
 915  *              the queue.
 916  *      Header:
 917  *              queue_remove_first(head, entry, type, field)
 918  *              entry is returned by reference
 919  *      Note:
 920  *              This should only be used with Method 2 queue iteration (element chains)
 921  */
 922 #define queue_remove_first(head, entry, type, field)            \
 923 MACRO_BEGIN                                                     \
 924         queue_entry_t   __next;                                 \
 925                                                                 \
 926         (entry) = (type)(void *) ((head)->next);                \
 927         __next = (entry)->field.next;                           \
 928                                                                 \
 929         if ((head) == __next)                                   \
 930                 (head)->prev = (head);                          \
 931         else                                                    \
 932                 ((type)(void *)(__next))->field.prev = (head);  \
 933         (head)->next = __next;                                  \
 934                                                                 \
 935         (entry)->field.next = NULL;                             \
 936         (entry)->field.prev = NULL;                             \
 937 MACRO_END
 938
 939 /*
 940  *      Macro:          queue_remove_last
 941  *      Function:
 942  *              Remove and return the entry at the tail of
 943  *              the queue.
 944  *      Header:
 945  *              queue_remove_last(head, entry, type, field)
 946  *              entry is returned by reference
 947  *      Note:
 948  *              This should only be used with Method 2 queue iteration (element chains)
 949  */
 950 #define queue_remove_last(head, entry, type, field)             \
 951 MACRO_BEGIN                                                     \
 952         queue_entry_t   __prev;                                 \
 953                                                                 \
 954         (entry) = (type)(void *) ((head)->prev);                \
 955         __prev = (entry)->field.prev;                           \
 956                                                                 \
 957         if ((head) == __prev)                                   \
 958                 (head)->next = (head);                          \
 959         else                                                    \
 960                 ((type)(void *)(__prev))->field.next = (head);  \
 961         (head)->prev = __prev;                                  \
 962                                                                 \
 963         (entry)->field.next = NULL;                             \
 964         (entry)->field.prev = NULL;                             \
 965 MACRO_END
 966
 967 /*
 968  *      Macro:          queue_assign
 969  *      Note:
 970  *              This should only be used with Method 2 queue iteration (element chains)
 971  */
 972 #define queue_assign(to, from, type, field)                     \
 973 MACRO_BEGIN                                                     \
 974         ((type)(void *)((from)->prev))->field.next = (to);      \
 975         ((type)(void *)((from)->next))->field.prev = (to);      \
 976         *to = *from;                                            \
 977 MACRO_END
 978
 979 /*
 980  *      Macro:          queue_new_head
 981  *      Function:
 982  *              rebase old queue to new queue head
 983  *      Header:
 984  *              queue_new_head(old, new, type, field)
 985  *                      queue_t old;
 986  *                      queue_t new;
 987  *                      <type> is what's in our queue
 988  *                      <field> is the chain field in (*<type>)
 989  *      Note:
 990  *              This should only be used with Method 2 queue iteration (element chains)
 991  */
 992 #define queue_new_head(old, new, type, field)                   \
 993 MACRO_BEGIN                                                     \
 994         if (!queue_empty(old)) {                                \
 995                 *(new) = *(old);                                \
 996                 ((type)(void *)((new)->next))->field.prev =     \
 997                         (new);                                  \
 998                 ((type)(void *)((new)->prev))->field.next =     \
 999                         (new);                                  \
1000         } else {                                                \
1001                 queue_init(new);                                \
1002         }                                                       \
1003 MACRO_END
1004
1005 /*
1006  *      Macro:          queue_iterate
1007  *      Function:
1008  *              iterate over each item in the queue.
1009  *              Generates a 'for' loop, setting elt to
1010  *              each item in turn (by reference).
1011  *      Header:
1012  *              queue_iterate(q, elt, type, field)
1013  *                      queue_t q;
1014  *                      <type> elt;
1015  *                      <type> is what's in our queue
1016  *                      <field> is the chain field in (*<type>)
1017  *      Note:
1018  *              This should only be used with Method 2 queue iteration (element chains)
1019  */
1020 #define queue_iterate(head, elt, type, field)                   \
1021         for ((elt) = (type)(void *) queue_first(head);          \
1022              !queue_end((head), (queue_entry_t)(elt));          \
1023              (elt) = (type)(void *) queue_next(&(elt)->field))
1024
1025 #ifdef  MACH_KERNEL_PRIVATE
1026
1027 #include <kern/locks.h>
1028
1029 /*----------------------------------------------------------------*/
1030 /*
1031  *      Define macros for queues with locks.
1032  */
1033 struct mpqueue_head {
1034         struct queue_entry      head;           /* header for queue */
1035         uint64_t                earliest_soft_deadline;
1036         uint64_t                count;
1037         lck_mtx_t               lock_data;
1038 #if defined(__i386__) || defined(__x86_64__)
1039         lck_mtx_ext_t           lock_data_ext;
1040 #endif
1041 };
1042
1043 typedef struct mpqueue_head     mpqueue_head_t;
1044
1045 #define round_mpq(size)         (size)
1046
1047
1048 #if defined(__i386__) || defined(__x86_64__)
1049
1050 #define mpqueue_init(q, lck_grp, lck_attr)              \
1051 MACRO_BEGIN                                             \
1052         queue_init(&(q)->head);                         \
1053         lck_mtx_init_ext(&(q)->lock_data,               \
1054                          &(q)->lock_data_ext,           \
1055                          lck_grp,                       \
1056                          lck_attr);                     \
1057         (q)->earliest_soft_deadline = UINT64_MAX;       \
1058         (q)->count = 0;                                 \
1059 MACRO_END
1060
1061 #else
1062
1063 #define mpqueue_init(q, lck_grp, lck_attr)              \
1064 MACRO_BEGIN                                             \
1065         queue_init(&(q)->head);                         \
1066         lck_mtx_init(&(q)->lock_data,                   \
1067                       lck_grp,                          \
1068                       lck_attr);                        \
1069 MACRO_END
1070 #endif
1071
1072
1073 #define mpenqueue_tail(q, elt)                          \
1074 MACRO_BEGIN                                             \
1075         lck_mtx_lock_spin_always(&(q)->lock_data);      \
1076         enqueue_tail(&(q)->head, elt);                  \
1077         lck_mtx_unlock_always(&(q)->lock_data);         \
1078 MACRO_END
1079
1080 #define mpdequeue_head(q, elt)                          \
1081 MACRO_BEGIN                                             \
1082         lck_mtx_lock_spin_always(&(q)->lock_data);      \
1083         if (queue_empty(&(q)->head))                    \
1084                 *(elt) = 0;                             \
1085         else                                            \
1086                 *(elt) = dequeue_head(&(q)->head);      \
1087         lck_mtx_unlock_always(&(q)->lock_data);         \
1088 MACRO_END
1089
1090 #endif  /* MACH_KERNEL_PRIVATE */
1091
1092 __END_DECLS
1093
1094 #endif  /* _KERN_QUEUE_H_ */