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 /*
  74  *      Queue of abstract objects.  Queue is maintained
  75  *      within that object.
  76  *
  77  *      Supports fast removal from within the queue.
  78  *
  79  *      How to declare a queue of elements of type "foo_t":
  80  *              In the "*foo_t" type, you must have a field of
  81  *              type "queue_chain_t" to hold together this queue.
  82  *              There may be more than one chain through a
  83  *              "foo_t", for use by different queues.
  84  *
  85  *              Declare the queue as a "queue_t" type.
  86  *
  87  *              Elements of the queue (of type "foo_t", that is)
  88  *              are referred to by reference, and cast to type
  89  *              "queue_entry_t" within this module.
  90  */
  91
  92 /*
  93  *      A generic doubly-linked list (queue).
  94  */
  95
  96 struct queue_entry {
  97         struct queue_entry      *next;          /* next element */
  98         struct queue_entry      *prev;          /* previous element */
  99 };
 100
 101 typedef struct queue_entry      *queue_t;
 102 typedef struct queue_entry      queue_head_t;
 103 typedef struct queue_entry      queue_chain_t;
 104 typedef struct queue_entry      *queue_entry_t;
 105
 106 /*
 107  *      enqueue puts "elt" on the "queue".
 108  *      dequeue returns the first element in the "queue".
 109  *      remqueue removes the specified "elt" from its queue.
 110  */
 111
 112 #define enqueue(queue,elt)      enqueue_tail(queue, elt)
 113 #define dequeue(queue)          dequeue_head(queue)
 114
 115 #if     !defined(__GNUC__)
 116
 117 #include <sys/cdefs.h>
 118 __BEGIN_DECLS
 119
 120 /* Enqueue element to head of queue */
 121 extern void             enqueue_head(
 122                                 queue_t         que,
 123                                 queue_entry_t   elt);
 124
 125 /* Enqueue element to tail of queue */
 126 extern void             enqueue_tail(
 127                                 queue_t         que,
 128                                 queue_entry_t   elt);
 129
 130 /* Dequeue element from head of queue */
 131 extern queue_entry_t    dequeue_head(
 132                                 queue_t que);
 133
 134 /* Dequeue element from tail of queue */
 135 extern queue_entry_t    dequeue_tail(
 136                                 queue_t que);
 137
 138 /* Dequeue element */
 139 extern void             remqueue(
 140                                 queue_entry_t   elt);
 141
 142 /* Enqueue element after a particular elem */
 143 extern void             insque(
 144                                 queue_entry_t   entry,
 145                                 queue_entry_t   pred);
 146
 147 /* Dequeue element */
 148 extern void             remque(
 149                                 queue_entry_t elt);
 150
 151 __END_DECLS
 152
 153 #else   /* !__GNUC__ */
 154
 155 #ifdef XNU_KERNEL_PRIVATE
 156 #define __DEQUEUE_ELT_CLEANUP(elt) do { \
 157                 (elt)->next = (queue_entry_t) 0; \
 158                 (elt)->prev = (queue_entry_t) 0; \
 159         } while (0)
 160 #else
 161 #define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0)
 162 #endif /* !XNU_KERNEL_PRIVATE */
 163
 164 static __inline__ void
 165 enqueue_head(
 166         queue_t         que,
 167         queue_entry_t   elt)
 168 {
 169         elt->next = que->next;
 170         elt->prev = que;
 171         elt->next->prev = elt;
 172         que->next = elt;
 173 }
 174
 175 static __inline__ void
 176 enqueue_tail(
 177                 queue_t         que,
 178                 queue_entry_t   elt)
 179 {
 180         elt->next = que;
 181         elt->prev = que->prev;
 182         elt->prev->next = elt;
 183         que->prev = elt;
 184 }
 185
 186 static __inline__ queue_entry_t
 187 dequeue_head(
 188         queue_t que)
 189 {
 190         register queue_entry_t  elt = (queue_entry_t) 0;
 191
 192         if (que->next != que) {
 193                 elt = que->next;
 194                 elt->next->prev = que;
 195                 que->next = elt->next;
 196                 __DEQUEUE_ELT_CLEANUP(elt);
 197         }
 198
 199         return (elt);
 200 }
 201
 202 static __inline__ queue_entry_t
 203 dequeue_tail(
 204         queue_t que)
 205 {
 206         register queue_entry_t  elt = (queue_entry_t) 0;
 207
 208         if (que->prev != que) {
 209                 elt = que->prev;
 210                 elt->prev->next = que;
 211                 que->prev = elt->prev;
 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         elt->next->prev = elt->prev;
 223         elt->prev->next = elt->next;
 224         __DEQUEUE_ELT_CLEANUP(elt);
 225 }
 226
 227 static __inline__ void
 228 insque(
 229         queue_entry_t   entry,
 230         queue_entry_t   pred)
 231 {
 232         entry->next = pred->next;
 233         entry->prev = pred;
 234         (pred->next)->prev = entry;
 235         pred->next = entry;
 236 }
 237
 238 static __inline__ void
 239 remque(
 240         register queue_entry_t elt)
 241 {
 242         (elt->next)->prev = elt->prev;
 243         (elt->prev)->next = elt->next;
 244         __DEQUEUE_ELT_CLEANUP(elt);
 245 }
 246
 247 #endif  /* !__GNUC__ */
 248
 249 /*
 250  *      Macro:          queue_init
 251  *      Function:
 252  *              Initialize the given queue.
 253  *      Header:
 254  *              void queue_init(q)
 255  *                      queue_t         q;      \* MODIFIED *\
 256  */
 257 #define queue_init(q)   \
 258 MACRO_BEGIN             \
 259         (q)->next = (q);\
 260         (q)->prev = (q);\
 261 MACRO_END
 262
 263 /*
 264  *      Macro:          queue_first
 265  *      Function:
 266  *              Returns the first entry in the queue,
 267  *      Header:
 268  *              queue_entry_t queue_first(q)
 269  *                      queue_t q;              \* IN *\
 270  */
 271 #define queue_first(q)  ((q)->next)
 272
 273 /*
 274  *      Macro:          queue_next
 275  *      Function:
 276  *              Returns the entry after an item in the queue.
 277  *      Header:
 278  *              queue_entry_t queue_next(qc)
 279  *                      queue_t qc;
 280  */
 281 #define queue_next(qc)  ((qc)->next)
 282
 283 /*
 284  *      Macro:          queue_last
 285  *      Function:
 286  *              Returns the last entry in the queue.
 287  *      Header:
 288  *              queue_entry_t queue_last(q)
 289  *                      queue_t q;              \* IN *\
 290  */
 291 #define queue_last(q)   ((q)->prev)
 292
 293 /*
 294  *      Macro:          queue_prev
 295  *      Function:
 296  *              Returns the entry before an item in the queue.
 297  *      Header:
 298  *              queue_entry_t queue_prev(qc)
 299  *                      queue_t qc;
 300  */
 301 #define queue_prev(qc)  ((qc)->prev)
 302
 303 /*
 304  *      Macro:          queue_end
 305  *      Function:
 306  *              Tests whether a new entry is really the end of
 307  *              the queue.
 308  *      Header:
 309  *              boolean_t queue_end(q, qe)
 310  *                      queue_t q;
 311  *                      queue_entry_t qe;
 312  */
 313 #define queue_end(q, qe)        ((q) == (qe))
 314
 315 /*
 316  *      Macro:          queue_empty
 317  *      Function:
 318  *              Tests whether a queue is empty.
 319  *      Header:
 320  *              boolean_t queue_empty(q)
 321  *                      queue_t q;
 322  */
 323 #define queue_empty(q)          queue_end((q), queue_first(q))
 324
 325
 326 /*----------------------------------------------------------------*/
 327 /*
 328  * Macros that operate on generic structures.  The queue
 329  * chain may be at any location within the structure, and there
 330  * may be more than one chain.
 331  */
 332
 333 /*
 334  *      Macro:          queue_enter
 335  *      Function:
 336  *              Insert a new element at the tail of the queue.
 337  *      Header:
 338  *              void queue_enter(q, elt, type, field)
 339  *                      queue_t q;
 340  *                      <type> elt;
 341  *                      <type> is what's in our queue
 342  *                      <field> is the chain field in (*<type>)
 343  */
 344 #define queue_enter(head, elt, type, field)                     \
 345 MACRO_BEGIN                                                     \
 346         register queue_entry_t __prev;                          \
 347                                                                 \
 348         __prev = (head)->prev;                                  \
 349         if ((head) == __prev) {                                 \
 350                 (head)->next = (queue_entry_t) (elt);           \
 351         }                                                       \
 352         else {                                                  \
 353                 ((type)__prev)->field.next = (queue_entry_t)(elt);\
 354         }                                                       \
 355         (elt)->field.prev = __prev;                             \
 356         (elt)->field.next = head;                               \
 357         (head)->prev = (queue_entry_t) elt;                     \
 358 MACRO_END
 359
 360 /*
 361  *      Macro:          queue_enter_first
 362  *      Function:
 363  *              Insert a new element at the head of the queue.
 364  *      Header:
 365  *              void queue_enter_first(q, elt, type, field)
 366  *                      queue_t q;
 367  *                      <type> elt;
 368  *                      <type> is what's in our queue
 369  *                      <field> is the chain field in (*<type>)
 370  */
 371 #define queue_enter_first(head, elt, type, field)               \
 372 MACRO_BEGIN                                                     \
 373         register queue_entry_t __next;                          \
 374                                                                 \
 375         __next = (head)->next;                                  \
 376         if ((head) == __next) {                                 \
 377                 (head)->prev = (queue_entry_t) (elt);           \
 378         }                                                       \
 379         else {                                                  \
 380                 ((type)__next)->field.prev = (queue_entry_t)(elt);\
 381         }                                                       \
 382         (elt)->field.next = __next;                             \
 383         (elt)->field.prev = head;                               \
 384         (head)->next = (queue_entry_t) elt;                     \
 385 MACRO_END
 386
 387 /*
 388  *      Macro:          queue_insert_before
 389  *      Function:
 390  *              Insert a new element before a given element.
 391  *      Header:
 392  *              void queue_insert_before(q, elt, cur, type, field)
 393  *                      queue_t q;
 394  *                      <type> elt;
 395  *                      <type> cur;
 396  *                      <type> is what's in our queue
 397  *                      <field> is the chain field in (*<type>)
 398  */
 399 #define queue_insert_before(head, elt, cur, type, field)                \
 400 MACRO_BEGIN                                                             \
 401         register queue_entry_t __prev;                                  \
 402                                                                         \
 403         if ((head) == (queue_entry_t)(cur)) {                           \
 404                 (elt)->field.next = (head);                             \
 405                 if ((head)->next == (head)) {   /* only element */      \
 406                         (elt)->field.prev = (head);                     \
 407                         (head)->next = (queue_entry_t)(elt);            \
 408                 } else {                        /* last element */      \
 409                         __prev = (elt)->field.prev = (head)->prev;      \
 410                         ((type)__prev)->field.next = (queue_entry_t)(elt);\
 411                 }                                                       \
 412                 (head)->prev = (queue_entry_t)(elt);                    \
 413         } else {                                                        \
 414                 (elt)->field.next = (queue_entry_t)(cur);               \
 415                 if ((head)->next == (queue_entry_t)(cur)) {             \
 416                                                 /* first element */     \
 417                         (elt)->field.prev = (head);                     \
 418                         (head)->next = (queue_entry_t)(elt);            \
 419                 } else {                        /* middle element */    \
 420                         __prev = (elt)->field.prev = (cur)->field.prev; \
 421                         ((type)__prev)->field.next = (queue_entry_t)(elt);\
 422                 }                                                       \
 423                 (cur)->field.prev = (queue_entry_t)(elt);               \
 424         }                                                               \
 425 MACRO_END
 426
 427 /*
 428  *      Macro:          queue_insert_after
 429  *      Function:
 430  *              Insert a new element after a given element.
 431  *      Header:
 432  *              void queue_insert_after(q, elt, cur, type, field)
 433  *                      queue_t q;
 434  *                      <type> elt;
 435  *                      <type> cur;
 436  *                      <type> is what's in our queue
 437  *                      <field> is the chain field in (*<type>)
 438  */
 439 #define queue_insert_after(head, elt, cur, type, field)                 \
 440 MACRO_BEGIN                                                             \
 441         register queue_entry_t __next;                                  \
 442                                                                         \
 443         if ((head) == (queue_entry_t)(cur)) {                           \
 444                 (elt)->field.prev = (head);                             \
 445                 if ((head)->next == (head)) {   /* only element */      \
 446                         (elt)->field.next = (head);                     \
 447                         (head)->prev = (queue_entry_t)(elt);            \
 448                 } else {                        /* first element */     \
 449                         __next = (elt)->field.next = (head)->next;      \
 450                         ((type)__next)->field.prev = (queue_entry_t)(elt);\
 451                 }                                                       \
 452                 (head)->next = (queue_entry_t)(elt);                    \
 453         } else {                                                        \
 454                 (elt)->field.prev = (queue_entry_t)(cur);               \
 455                 if ((head)->prev == (queue_entry_t)(cur)) {             \
 456                                                 /* last element */      \
 457                         (elt)->field.next = (head);                     \
 458                         (head)->prev = (queue_entry_t)(elt);            \
 459                 } else {                        /* middle element */    \
 460                         __next = (elt)->field.next = (cur)->field.next; \
 461                         ((type)__next)->field.prev = (queue_entry_t)(elt);\
 462                 }                                                       \
 463                 (cur)->field.next = (queue_entry_t)(elt);               \
 464         }                                                               \
 465 MACRO_END
 466
 467 /*
 468  *      Macro:          queue_field [internal use only]
 469  *      Function:
 470  *              Find the queue_chain_t (or queue_t) for the
 471  *              given element (thing) in the given queue (head)
 472  */
 473 #define queue_field(head, thing, type, field)                   \
 474                 (((head) == (thing)) ? (head) : &((type)(thing))->field)
 475
 476 /*
 477  *      Macro:          queue_remove
 478  *      Function:
 479  *              Remove an arbitrary item from the queue.
 480  *      Header:
 481  *              void queue_remove(q, qe, type, field)
 482  *                      arguments as in queue_enter
 483  */
 484 #define queue_remove(head, elt, type, field)                    \
 485 MACRO_BEGIN                                                     \
 486         register queue_entry_t  __next, __prev;                 \
 487                                                                 \
 488         __next = (elt)->field.next;                             \
 489         __prev = (elt)->field.prev;                             \
 490                                                                 \
 491         if ((head) == __next)                                   \
 492                 (head)->prev = __prev;                          \
 493         else                                                    \
 494                 ((type)__next)->field.prev = __prev;            \
 495                                                                 \
 496         if ((head) == __prev)                                   \
 497                 (head)->next = __next;                          \
 498         else                                                    \
 499                 ((type)__prev)->field.next = __next;            \
 500                                                                 \
 501         (elt)->field.next = NULL;                               \
 502         (elt)->field.prev = NULL;                               \
 503 MACRO_END
 504
 505 /*
 506  *      Macro:          queue_remove_first
 507  *      Function:
 508  *              Remove and return the entry at the head of
 509  *              the queue.
 510  *      Header:
 511  *              queue_remove_first(head, entry, type, field)
 512  *              entry is returned by reference
 513  */
 514 #define queue_remove_first(head, entry, type, field)            \
 515 MACRO_BEGIN                                                     \
 516         register queue_entry_t  __next;                         \
 517                                                                 \
 518         (entry) = (type) ((head)->next);                        \
 519         __next = (entry)->field.next;                           \
 520                                                                 \
 521         if ((head) == __next)                                   \
 522                 (head)->prev = (head);                          \
 523         else                                                    \
 524                 ((type)(__next))->field.prev = (head);          \
 525         (head)->next = __next;                                  \
 526                                                                 \
 527         (entry)->field.next = NULL;                             \
 528         (entry)->field.prev = NULL;                             \
 529 MACRO_END
 530
 531 /*
 532  *      Macro:          queue_remove_last
 533  *      Function:
 534  *              Remove and return the entry at the tail of
 535  *              the queue.
 536  *      Header:
 537  *              queue_remove_last(head, entry, type, field)
 538  *              entry is returned by reference
 539  */
 540 #define queue_remove_last(head, entry, type, field)             \
 541 MACRO_BEGIN                                                     \
 542         register queue_entry_t  __prev;                         \
 543                                                                 \
 544         (entry) = (type) ((head)->prev);                        \
 545         __prev = (entry)->field.prev;                           \
 546                                                                 \
 547         if ((head) == __prev)                                   \
 548                 (head)->next = (head);                          \
 549         else                                                    \
 550                 ((type)(__prev))->field.next = (head);          \
 551         (head)->prev = __prev;                                  \
 552                                                                 \
 553         (entry)->field.next = NULL;                             \
 554         (entry)->field.prev = NULL;                             \
 555 MACRO_END
 556
 557 /*
 558  *      Macro:          queue_assign
 559  */
 560 #define queue_assign(to, from, type, field)                     \
 561 MACRO_BEGIN                                                     \
 562         ((type)((from)->prev))->field.next = (to);              \
 563         ((type)((from)->next))->field.prev = (to);              \
 564         *to = *from;                                            \
 565 MACRO_END
 566
 567 /*
 568  *      Macro:          queue_new_head
 569  *      Function:
 570  *              rebase old queue to new queue head
 571  *      Header:
 572  *              queue_new_head(old, new, type, field)
 573  *                      queue_t old;
 574  *                      queue_t new;
 575  *                      <type> is what's in our queue
 576  *                      <field> is the chain field in (*<type>)
 577  */
 578 #define queue_new_head(old, new, type, field)                   \
 579 MACRO_BEGIN                                                     \
 580         if (!queue_empty(old)) {                                \
 581                 *(new) = *(old);                                \
 582                 ((type)((new)->next))->field.prev = (new);      \
 583                 ((type)((new)->prev))->field.next = (new);      \
 584         } else {                                                \
 585                 queue_init(new);                                \
 586         }                                                       \
 587 MACRO_END
 588
 589 /*
 590  *      Macro:          queue_iterate
 591  *      Function:
 592  *              iterate over each item in the queue.
 593  *              Generates a 'for' loop, setting elt to
 594  *              each item in turn (by reference).
 595  *      Header:
 596  *              queue_iterate(q, elt, type, field)
 597  *                      queue_t q;
 598  *                      <type> elt;
 599  *                      <type> is what's in our queue
 600  *                      <field> is the chain field in (*<type>)
 601  */
 602 #define queue_iterate(head, elt, type, field)                   \
 603         for ((elt) = (type) queue_first(head);                  \
 604              !queue_end((head), (queue_entry_t)(elt));          \
 605              (elt) = (type) queue_next(&(elt)->field))
 606
 607 #ifdef  MACH_KERNEL_PRIVATE
 608
 609 #include <kern/lock.h>
 610
 611 /*----------------------------------------------------------------*/
 612 /*
 613  *      Define macros for queues with locks.
 614  */
 615 struct mpqueue_head {
 616         struct queue_entry      head;           /* header for queue */
 617         lck_mtx_t               lock_data;
 618         lck_mtx_ext_t           lock_data_ext;
 619 };
 620
 621 typedef struct mpqueue_head     mpqueue_head_t;
 622
 623 #define round_mpq(size)         (size)
 624
 625
 626 #if defined(__i386__) || defined(__x86_64__)
 627
 628 #define mpqueue_init(q, lck_grp, lck_attr)              \
 629 MACRO_BEGIN                                             \
 630         queue_init(&(q)->head);                         \
 631         lck_mtx_init_ext(&(q)->lock_data,               \
 632                          &(q)->lock_data_ext,           \
 633                          lck_grp,                       \
 634                          lck_attr);                     \
 635 MACRO_END
 636
 637 #else
 638
 639 #define mpqueue_init(q, lck_grp, lck_attr)              \
 640 MACRO_BEGIN                                             \
 641         queue_init(&(q)->head);                         \
 642         lck_spin_init(&(q)->lock_data,                  \
 643                       lck_grp,                          \
 644                       lck_attr);                        \
 645 MACRO_END
 646 #endif
 647
 648
 649 #define mpenqueue_tail(q, elt)                          \
 650 MACRO_BEGIN                                             \
 651         lck_mtx_lock_spin_always(&(q)->lock_data);      \
 652         enqueue_tail(&(q)->head, elt);                  \
 653         lck_mtx_unlock_always(&(q)->lock_data);         \
 654 MACRO_END
 655
 656 #define mpdequeue_head(q, elt)                          \
 657 MACRO_BEGIN                                             \
 658         lck_mtx_lock_spin_always(&(q)->lock_data);      \
 659         if (queue_empty(&(q)->head))                    \
 660                 *(elt) = 0;                             \
 661         else                                            \
 662                 *(elt) = dequeue_head(&(q)->head);      \
 663         lck_mtx_unlock_always(&(q)->lock_data);         \
 664 MACRO_END
 665
 666 #endif  /* MACH_KERNEL_PRIVATE */
 667
 668 #endif  /* _KERN_QUEUE_H_ */