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 96struct queue_entry { 97 struct queue_entry *next; /* next element */ 98 struct queue_entry *prev; /* previous element */ 99}; 100 101typedef struct queue_entry *queue_t; 102typedef struct queue_entry queue_head_t; 103typedef struct queue_entry queue_chain_t; 104typedef 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 */ 121extern void enqueue_head( 122 queue_t que, 123 queue_entry_t elt); 124 125/* Enqueue element to tail of queue */ 126extern void enqueue_tail( 127 queue_t que, 128 queue_entry_t elt); 129 130/* Dequeue element from head of queue */ 131extern queue_entry_t dequeue_head( 132 queue_t que); 133 134/* Dequeue element from tail of queue */ 135extern queue_entry_t dequeue_tail( 136 queue_t que); 137 138/* Dequeue element */ 139extern void remqueue( 140 queue_entry_t elt); 141 142/* Enqueue element after a particular elem */ 143extern void insque( 144 queue_entry_t entry, 145 queue_entry_t pred); 146 147/* Dequeue element */ 148extern 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 164static __inline__ void 165enqueue_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 175static __inline__ void 176enqueue_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 186static __inline__ queue_entry_t 187dequeue_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 202static __inline__ queue_entry_t 203dequeue_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 218static __inline__ void 219remqueue( 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 227static __inline__ void 228insque( 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 238static __inline__ void 239remque( 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) \ 258MACRO_BEGIN \ 259 (q)->next = (q);\ 260 (q)->prev = (q);\ 261MACRO_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) \ 345MACRO_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)(void *)__prev)->field.next = \ 354 (queue_entry_t)(elt); \ 355 } \ 356 (elt)->field.prev = __prev; \ 357 (elt)->field.next = head; \ 358 (head)->prev = (queue_entry_t) elt; \ 359MACRO_END 360 361/* 362 * Macro: queue_enter_first 363 * Function: 364 * Insert a new element at the head of the queue. 365 * Header: 366 * void queue_enter_first(q, elt, type, field) 367 * queue_t q; 368 * <type> elt; 369 * <type> is what's in our queue 370 * <field> is the chain field in (*<type>) 371 */ 372#define queue_enter_first(head, elt, type, field) \ 373MACRO_BEGIN \ 374 register queue_entry_t __next; \ 375 \ 376 __next = (head)->next; \ 377 if ((head) == __next) { \ 378 (head)->prev = (queue_entry_t) (elt); \ 379 } \ 380 else { \ 381 ((type)(void *)__next)->field.prev = \ 382 (queue_entry_t)(elt); \ 383 } \ 384 (elt)->field.next = __next; \ 385 (elt)->field.prev = head; \ 386 (head)->next = (queue_entry_t) elt; \ 387MACRO_END 388 389/* 390 * Macro: queue_insert_before 391 * Function: 392 * Insert a new element before a given element. 393 * Header: 394 * void queue_insert_before(q, elt, cur, type, field) 395 * queue_t q; 396 * <type> elt; 397 * <type> cur; 398 * <type> is what's in our queue 399 * <field> is the chain field in (*<type>) 400 */ 401#define queue_insert_before(head, elt, cur, type, field) \ 402MACRO_BEGIN \ 403 register queue_entry_t __prev; \ 404 \ 405 if ((head) == (queue_entry_t)(cur)) { \ 406 (elt)->field.next = (head); \ 407 if ((head)->next == (head)) { /* only element */ \ 408 (elt)->field.prev = (head); \ 409 (head)->next = (queue_entry_t)(elt); \ 410 } else { /* last element */ \ 411 __prev = (elt)->field.prev = (head)->prev; \ 412 ((type)(void *)__prev)->field.next = \ 413 (queue_entry_t)(elt); \ 414 } \ 415 (head)->prev = (queue_entry_t)(elt); \ 416 } else { \ 417 (elt)->field.next = (queue_entry_t)(cur); \ 418 if ((head)->next == (queue_entry_t)(cur)) { \ 419 /* first element */ \ 420 (elt)->field.prev = (head); \ 421 (head)->next = (queue_entry_t)(elt); \ 422 } else { /* middle element */ \ 423 __prev = (elt)->field.prev = (cur)->field.prev; \ 424 ((type)(void *)__prev)->field.next = \ 425 (queue_entry_t)(elt); \ 426 } \ 427 (cur)->field.prev = (queue_entry_t)(elt); \ 428 } \ 429MACRO_END 430 431/* 432 * Macro: queue_insert_after 433 * Function: 434 * Insert a new element after a given element. 435 * Header: 436 * void queue_insert_after(q, elt, cur, type, field) 437 * queue_t q; 438 * <type> elt; 439 * <type> cur; 440 * <type> is what's in our queue 441 * <field> is the chain field in (*<type>) 442 */ 443#define queue_insert_after(head, elt, cur, type, field) \ 444MACRO_BEGIN \ 445 register queue_entry_t __next; \ 446 \ 447 if ((head) == (queue_entry_t)(cur)) { \ 448 (elt)->field.prev = (head); \ 449 if ((head)->next == (head)) { /* only element */ \ 450 (elt)->field.next = (head); \ 451 (head)->prev = (queue_entry_t)(elt); \ 452 } else { /* first element */ \ 453 __next = (elt)->field.next = (head)->next; \ 454 ((type)(void *)__next)->field.prev = \ 455 (queue_entry_t)(elt); \ 456 } \ 457 (head)->next = (queue_entry_t)(elt); \ 458 } else { \ 459 (elt)->field.prev = (queue_entry_t)(cur); \ 460 if ((head)->prev == (queue_entry_t)(cur)) { \ 461 /* last element */ \ 462 (elt)->field.next = (head); \ 463 (head)->prev = (queue_entry_t)(elt); \ 464 } else { /* middle element */ \ 465 __next = (elt)->field.next = (cur)->field.next; \ 466 ((type)(void *)__next)->field.prev = \ 467 (queue_entry_t)(elt); \ 468 } \ 469 (cur)->field.next = (queue_entry_t)(elt); \ 470 } \ 471MACRO_END 472 473/* 474 * Macro: queue_field [internal use only] 475 * Function: 476 * Find the queue_chain_t (or queue_t) for the 477 * given element (thing) in the given queue (head) 478 */ 479#define queue_field(head, thing, type, field) \ 480 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field) 481 482/* 483 * Macro: queue_remove 484 * Function: 485 * Remove an arbitrary item from the queue. 486 * Header: 487 * void queue_remove(q, qe, type, field) 488 * arguments as in queue_enter 489 */ 490#define queue_remove(head, elt, type, field) \ 491MACRO_BEGIN \ 492 register queue_entry_t __next, __prev; \ 493 \ 494 __next = (elt)->field.next; \ 495 __prev = (elt)->field.prev; \ 496 \ 497 if ((head) == __next) \ 498 (head)->prev = __prev; \ 499 else \ 500 ((type)(void *)__next)->field.prev = __prev; \ 501 \ 502 if ((head) == __prev) \ 503 (head)->next = __next; \ 504 else \ 505 ((type)(void *)__prev)->field.next = __next; \ 506 \ 507 (elt)->field.next = NULL; \ 508 (elt)->field.prev = NULL; \ 509MACRO_END 510 511/* 512 * Macro: queue_remove_first 513 * Function: 514 * Remove and return the entry at the head of 515 * the queue. 516 * Header: 517 * queue_remove_first(head, entry, type, field) 518 * entry is returned by reference 519 */ 520#define queue_remove_first(head, entry, type, field) \ 521MACRO_BEGIN \ 522 register queue_entry_t __next; \ 523 \ 524 (entry) = (type)(void *) ((head)->next); \ 525 __next = (entry)->field.next; \ 526 \ 527 if ((head) == __next) \ 528 (head)->prev = (head); \ 529 else \ 530 ((type)(void *)(__next))->field.prev = (head); \ 531 (head)->next = __next; \ 532 \ 533 (entry)->field.next = NULL; \ 534 (entry)->field.prev = NULL; \ 535MACRO_END 536 537/* 538 * Macro: queue_remove_last 539 * Function: 540 * Remove and return the entry at the tail of 541 * the queue. 542 * Header: 543 * queue_remove_last(head, entry, type, field) 544 * entry is returned by reference 545 */ 546#define queue_remove_last(head, entry, type, field) \ 547MACRO_BEGIN \ 548 register queue_entry_t __prev; \ 549 \ 550 (entry) = (type)(void *) ((head)->prev); \ 551 __prev = (entry)->field.prev; \ 552 \ 553 if ((head) == __prev) \ 554 (head)->next = (head); \ 555 else \ 556 ((type)(void *)(__prev))->field.next = (head); \ 557 (head)->prev = __prev; \ 558 \ 559 (entry)->field.next = NULL; \ 560 (entry)->field.prev = NULL; \ 561MACRO_END 562 563/* 564 * Macro: queue_assign 565 */ 566#define queue_assign(to, from, type, field) \ 567MACRO_BEGIN \ 568 ((type)(void *)((from)->prev))->field.next = (to); \ 569 ((type)(void *)((from)->next))->field.prev = (to); \ 570 *to = *from; \ 571MACRO_END 572 573/* 574 * Macro: queue_new_head 575 * Function: 576 * rebase old queue to new queue head 577 * Header: 578 * queue_new_head(old, new, type, field) 579 * queue_t old; 580 * queue_t new; 581 * <type> is what's in our queue 582 * <field> is the chain field in (*<type>) 583 */ 584#define queue_new_head(old, new, type, field) \ 585MACRO_BEGIN \ 586 if (!queue_empty(old)) { \ 587 *(new) = *(old); \ 588 ((type)(void *)((new)->next))->field.prev = \ 589 (new); \ 590 ((type)(void *)((new)->prev))->field.next = \ 591 (new); \ 592 } else { \ 593 queue_init(new); \ 594 } \ 595MACRO_END 596 597/* 598 * Macro: queue_iterate 599 * Function: 600 * iterate over each item in the queue. 601 * Generates a 'for' loop, setting elt to 602 * each item in turn (by reference). 603 * Header: 604 * queue_iterate(q, elt, type, field) 605 * queue_t q; 606 * <type> elt; 607 * <type> is what's in our queue 608 * <field> is the chain field in (*<type>) 609 */ 610#define queue_iterate(head, elt, type, field) \ 611 for ((elt) = (type)(void *) queue_first(head); \ 612 !queue_end((head), (queue_entry_t)(elt)); \ 613 (elt) = (type)(void *) queue_next(&(elt)->field)) 614 615#ifdef MACH_KERNEL_PRIVATE 616 617#include <kern/lock.h> 618 619/*----------------------------------------------------------------*/ 620/* 621 * Define macros for queues with locks. 622 */ 623struct mpqueue_head { 624 struct queue_entry head; /* header for queue */ 625 uint64_t earliest_soft_deadline; 626 uint64_t count; 627#if defined(__i386__) || defined(__x86_64__) 628 lck_mtx_t lock_data; 629 lck_mtx_ext_t lock_data_ext; 630#else 631 lck_spin_t lock_data; 632#endif 633}; 634 635typedef struct mpqueue_head mpqueue_head_t; 636 637#define round_mpq(size) (size) 638 639 640#if defined(__i386__) || defined(__x86_64__) 641 642#define mpqueue_init(q, lck_grp, lck_attr) \ 643MACRO_BEGIN \ 644 queue_init(&(q)->head); \ 645 lck_mtx_init_ext(&(q)->lock_data, \ 646 &(q)->lock_data_ext, \ 647 lck_grp, \ 648 lck_attr); \ 649 (q)->earliest_soft_deadline = UINT64_MAX; \ 650 (q)->count = 0; \ 651MACRO_END 652 653#else 654 655#define mpqueue_init(q, lck_grp, lck_attr) \ 656MACRO_BEGIN \ 657 queue_init(&(q)->head); \ 658 lck_spin_init(&(q)->lock_data, \ 659 lck_grp, \ 660 lck_attr); \ 661MACRO_END 662#endif 663 664 665#define mpenqueue_tail(q, elt) \ 666MACRO_BEGIN \ 667 lck_mtx_lock_spin_always(&(q)->lock_data); \ 668 enqueue_tail(&(q)->head, elt); \ 669 lck_mtx_unlock_always(&(q)->lock_data); \ 670MACRO_END 671 672#define mpdequeue_head(q, elt) \ 673MACRO_BEGIN \ 674 lck_mtx_lock_spin_always(&(q)->lock_data); \ 675 if (queue_empty(&(q)->head)) \ 676 *(elt) = 0; \ 677 else \ 678 *(elt) = dequeue_head(&(q)->head); \ 679 lck_mtx_unlock_always(&(q)->lock_data); \ 680MACRO_END 681 682#endif /* MACH_KERNEL_PRIVATE */ 683 684#endif /* _KERN_QUEUE_H_ */ 685