![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to wait_queue.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / osfmk / kern|
Return to wait_queue.c CVS log | Up to [Apple XNU] / XNU / osfmk / kern |
1.1 ! root 1: /* ! 2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. ! 3: * ! 4: * @APPLE_LICENSE_HEADER_START@ ! 5: * ! 6: * The contents of this file constitute Original Code as defined in and ! 7: * are subject to the Apple Public Source License Version 1.1 (the ! 8: * "License"). You may not use this file except in compliance with the ! 9: * License. Please obtain a copy of the License at ! 10: * http://www.apple.com/publicsource and read it before using this file. ! 11: * ! 12: * This Original Code and all software distributed under the License are ! 13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER ! 14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, ! 15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, ! 16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the ! 17: * License for the specific language governing rights and limitations ! 18: * under the License. ! 19: * ! 20: * @APPLE_LICENSE_HEADER_END@ ! 21: */ ! 22: /* ! 23: * @OSF_FREE_COPYRIGHT@ ! 24: */ ! 25: /* ! 26: * Mach Operating System ! 27: * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University ! 28: * All Rights Reserved. ! 29: * ! 30: * Permission to use, copy, modify and distribute this software and its ! 31: * documentation is hereby granted, provided that both the copyright ! 32: * notice and this permission notice appear in all copies of the ! 33: * software, derivative works or modified versions, and any portions ! 34: * thereof, and that both notices appear in supporting documentation. ! 35: * ! 36: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" ! 37: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR ! 38: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. ! 39: * ! 40: * Carnegie Mellon requests users of this software to return to ! 41: * ! 42: * Software Distribution Coordinator or [email protected] ! 43: * School of Computer Science ! 44: * Carnegie Mellon University ! 45: * Pittsburgh PA 15213-3890 ! 46: * ! 47: * any improvements or extensions that they make and grant Carnegie Mellon ! 48: * the rights to redistribute these changes. ! 49: */ ! 50: /* ! 51: */ ! 52: /* ! 53: * File: wait_queue.c (adapted from sched_prim.c) ! 54: * Author: Avadis Tevanian, Jr. ! 55: * Date: 1986 ! 56: * ! 57: * Primitives for manipulating wait queues: either global ! 58: * ones from sched_prim.c, or private ones associated with ! 59: * particular structures(pots, semaphores, etc..). ! 60: */ ! 61: ! 62: #include <kern/kern_types.h> ! 63: #include <kern/simple_lock.h> ! 64: #include <kern/queue.h> ! 65: #include <kern/spl.h> ! 66: ! 67: #include <mach/sync_policy.h> ! 68: ! 69: #include <kern/sched_prim.h> ! 70: #include <kern/wait_queue.h> ! 71: ! 72: void ! 73: wait_queue_init( ! 74: wait_queue_t wq, ! 75: int policy) ! 76: { ! 77: wq->wq_fifo = (policy == SYNC_POLICY_FIFO); ! 78: wq->wq_issub = FALSE; ! 79: queue_init(&wq->wq_queue); ! 80: hw_lock_init(&wq->wq_interlock); ! 81: } ! 82: ! 83: void ! 84: wait_queue_sub_init( ! 85: wait_queue_sub_t wqsub, ! 86: int policy) ! 87: { ! 88: wait_queue_init(&wqsub->wqs_wait_queue, policy); ! 89: wqsub->wqs_wait_queue.wq_issub = TRUE; ! 90: queue_init(&wqsub->wqs_sublinks); ! 91: } ! 92: ! 93: void ! 94: wait_queue_link_init( ! 95: wait_queue_link_t wql) ! 96: { ! 97: queue_init(&wql->wql_links); ! 98: queue_init(&wql->wql_sublinks); ! 99: wql->wql_queue = WAIT_QUEUE_NULL; ! 100: wql->wql_subqueue = WAIT_QUEUE_SUB_NULL; ! 101: wql->wql_event = NO_EVENT; ! 102: } ! 103: ! 104: ! 105: /* ! 106: * Routine: wait_queue_lock ! 107: * Purpose: ! 108: * Lock the wait queue. ! 109: * Conditions: ! 110: * the appropriate spl level (if any) is already raised. ! 111: */ ! 112: void ! 113: wait_queue_lock( ! 114: wait_queue_t wq) ! 115: { ! 116: #ifdef __ppc__ ! 117: vm_offset_t pc; ! 118: ! 119: pc = GET_RETURN_PC(&wq); ! 120: if (!hw_lock_to(&wq->wq_interlock, LockTimeOut)) { ! 121: panic("wait queue deadlock detection - wq=0x%x, cpu=%d, ret=0x%x\n", wq, cpu_number(), pc); ! 122: } ! 123: #else ! 124: hw_lock_lock(&wq->wq_interlock); ! 125: #endif ! 126: } ! 127: ! 128: /* ! 129: * Routine: wait_queue_lock_try ! 130: * Purpose: ! 131: * Try to lock the wait queue without waiting ! 132: * Conditions: ! 133: * the appropriate spl level (if any) is already raised. ! 134: * Returns: ! 135: * TRUE if the lock was acquired ! 136: * FALSE if we would have needed to wait ! 137: */ ! 138: boolean_t ! 139: wait_queue_lock_try( ! 140: wait_queue_t wq) ! 141: { ! 142: return hw_lock_try(&wq->wq_interlock); ! 143: } ! 144: ! 145: /* ! 146: * Routine: wait_queue_unlock ! 147: * Purpose: ! 148: * unlock the wait queue ! 149: * Conditions: ! 150: * The wait queue is assumed locked. ! 151: * appropriate spl level is still maintained ! 152: */ ! 153: void ! 154: wait_queue_unlock( ! 155: wait_queue_t wq) ! 156: { ! 157: assert(hw_lock_held(&wq->wq_interlock)); ! 158: ! 159: hw_lock_unlock(&wq->wq_interlock); ! 160: } ! 161: ! 162: int _wait_queue_subordinate; /* phoney event for subordinate wait q elements */ ! 163: ! 164: ! 165: /* ! 166: * Routine: wait_queue_member_locked ! 167: * Purpose: ! 168: * Indicate if this sub queue is a member of the queue ! 169: * Conditions: ! 170: * The wait queue is locked ! 171: * The sub queue is just that, a sub queue ! 172: */ ! 173: boolean_t ! 174: wait_queue_member_locked( ! 175: wait_queue_t wq, ! 176: wait_queue_sub_t wq_sub) ! 177: { ! 178: wait_queue_element_t wq_element; ! 179: queue_t q; ! 180: ! 181: assert(wait_queue_held(wq)); ! 182: assert(wait_queue_is_sub(wq_sub)); ! 183: ! 184: q = &wq->wq_queue; ! 185: ! 186: wq_element = (wait_queue_element_t) queue_first(q); ! 187: while (!queue_end(q, (queue_entry_t)wq_element)) { ! 188: ! 189: if ((wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE)) { ! 190: wait_queue_link_t wql = (wait_queue_link_t)wq_element; ! 191: ! 192: if (wql->wql_subqueue == wq_sub) ! 193: return TRUE; ! 194: } ! 195: wq_element = (wait_queue_element_t) ! 196: queue_next((queue_t) wq_element); ! 197: } ! 198: return FALSE; ! 199: } ! 200: ! 201: ! 202: /* ! 203: * Routine: wait_queue_member ! 204: * Purpose: ! 205: * Indicate if this sub queue is a member of the queue ! 206: * Conditions: ! 207: * The sub queue is just that, a sub queue ! 208: */ ! 209: boolean_t ! 210: wait_queue_member( ! 211: wait_queue_t wq, ! 212: wait_queue_sub_t wq_sub) ! 213: { ! 214: boolean_t ret; ! 215: ! 216: assert(wait_queue_is_sub(wq_sub)); ! 217: ! 218: wait_queue_lock(wq); ! 219: ret = wait_queue_member_locked(wq, wq_sub); ! 220: wait_queue_unlock(wq); ! 221: return ret; ! 222: } ! 223: ! 224: /* ! 225: * Routine: wait_queue_link ! 226: * Purpose: ! 227: * Insert a subordinate wait queue into a wait queue. This ! 228: * requires us to link the two together using a wait_queue_link ! 229: * structure that we allocate. ! 230: * Conditions: ! 231: * The wait queue being inserted must be inited as a sub queue ! 232: * The sub waitq is not already linked ! 233: * ! 234: */ ! 235: kern_return_t ! 236: wait_queue_link( ! 237: wait_queue_t wq, ! 238: wait_queue_sub_t wq_sub) ! 239: { ! 240: wait_queue_link_t wql; ! 241: ! 242: assert(wait_queue_is_sub(wq_sub)); ! 243: assert(!wait_queue_member(wq, wq_sub)); ! 244: ! 245: wql = (wait_queue_link_t) kalloc(sizeof(struct wait_queue_link)); ! 246: if (wql == WAIT_QUEUE_LINK_NULL) ! 247: return KERN_RESOURCE_SHORTAGE; ! 248: ! 249: wait_queue_link_init(wql); ! 250: ! 251: wait_queue_lock(wq); ! 252: wqs_lock(wq_sub); ! 253: ! 254: wql->wql_queue = wq; ! 255: wql->wql_subqueue = wq_sub; ! 256: wql->wql_event = WAIT_QUEUE_SUBORDINATE; ! 257: queue_enter(&wq->wq_queue, wql, wait_queue_link_t, wql_links); ! 258: queue_enter(&wq_sub->wqs_sublinks, wql, wait_queue_link_t, wql_sublinks); ! 259: ! 260: wqs_unlock(wq_sub); ! 261: wait_queue_unlock(wq); ! 262: ! 263: return KERN_SUCCESS; ! 264: } ! 265: ! 266: /* ! 267: * Routine: wait_queue_unlink ! 268: * Purpose: ! 269: * Remove the linkage between a wait queue and its subordinate. ! 270: * Conditions: ! 271: * The wait queue being must be a member sub queue ! 272: */ ! 273: kern_return_t ! 274: wait_queue_unlink( ! 275: wait_queue_t wq, ! 276: wait_queue_sub_t wq_sub) ! 277: { ! 278: wait_queue_element_t wq_element; ! 279: queue_t q; ! 280: ! 281: assert(wait_queue_is_sub(wq_sub)); ! 282: assert(wait_queue_member(wq, wq_sub)); ! 283: ! 284: wait_queue_lock(wq); ! 285: wqs_lock(wq_sub); ! 286: ! 287: q = &wq->wq_queue; ! 288: ! 289: wq_element = (wait_queue_element_t) queue_first(q); ! 290: while (!queue_end(q, (queue_entry_t)wq_element)) { ! 291: ! 292: if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) { ! 293: wait_queue_link_t wql = (wait_queue_link_t)wq_element; ! 294: queue_t sq; ! 295: ! 296: if (wql->wql_subqueue == wq_sub) { ! 297: sq = &wq_sub->wqs_sublinks; ! 298: queue_remove(q, wql, wait_queue_link_t, wql_links); ! 299: queue_remove(sq, wql, wait_queue_link_t, wql_sublinks); ! 300: wqs_unlock(wq_sub); ! 301: wait_queue_unlock(wq); ! 302: kfree((vm_offset_t)wql,sizeof(struct wait_queue_link)); ! 303: return; ! 304: } ! 305: } ! 306: ! 307: wq_element = (wait_queue_element_t) ! 308: queue_next((queue_t) wq_element); ! 309: } ! 310: panic("wait_queue_unlink"); ! 311: } ! 312: ! 313: /* ! 314: * Routine: wait_queue_unlink_one ! 315: * Purpose: ! 316: * Find and unlink one subordinate wait queue ! 317: * Conditions: ! 318: * Nothing of interest locked. ! 319: */ ! 320: void ! 321: wait_queue_unlink_one( ! 322: wait_queue_t wq, ! 323: wait_queue_sub_t *wq_subp) ! 324: { ! 325: wait_queue_element_t wq_element; ! 326: queue_t q; ! 327: ! 328: wait_queue_lock(wq); ! 329: ! 330: q = &wq->wq_queue; ! 331: ! 332: wq_element = (wait_queue_element_t) queue_first(q); ! 333: while (!queue_end(q, (queue_entry_t)wq_element)) { ! 334: ! 335: if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) { ! 336: wait_queue_link_t wql = (wait_queue_link_t)wq_element; ! 337: wait_queue_sub_t wq_sub = wql->wql_subqueue; ! 338: queue_t sq; ! 339: ! 340: wqs_lock(wq_sub); ! 341: sq = &wq_sub->wqs_sublinks; ! 342: queue_remove(q, wql, wait_queue_link_t, wql_links); ! 343: queue_remove(sq, wql, wait_queue_link_t, wql_sublinks); ! 344: wqs_unlock(wq_sub); ! 345: wait_queue_unlock(wq); ! 346: kfree((vm_offset_t)wql,sizeof(struct wait_queue_link)); ! 347: *wq_subp = wq_sub; ! 348: return; ! 349: } ! 350: ! 351: wq_element = (wait_queue_element_t) ! 352: queue_next((queue_t) wq_element); ! 353: } ! 354: wait_queue_unlock(wq); ! 355: *wq_subp = WAIT_QUEUE_SUB_NULL; ! 356: } ! 357: ! 358: /* ! 359: * Routine: wait_queue_assert_wait_locked ! 360: * Purpose: ! 361: * Insert the current thread into the supplied wait queue ! 362: * waiting for a particular event to be posted to that queue. ! 363: * ! 364: * Conditions: ! 365: * The wait queue is assumed locked. ! 366: * ! 367: */ ! 368: void ! 369: wait_queue_assert_wait_locked( ! 370: wait_queue_t wq, ! 371: event_t event, ! 372: int interruptible, ! 373: boolean_t unlock) ! 374: { ! 375: thread_t thread = current_thread(); ! 376: spl_t s; ! 377: ! 378: s = splsched(); ! 379: thread_lock(thread); ! 380: ! 381: /* ! 382: * This is the extent to which we currently take scheduling attributes ! 383: * into account. If the thread is vm priviledged, we stick it at ! 384: * the front of the queue. Later, these queues will honor the policy ! 385: * value set at wait_queue_init time. ! 386: */ ! 387: if (thread->vm_privilege) ! 388: enqueue_head(&wq->wq_queue, (queue_entry_t) thread); ! 389: else ! 390: enqueue_tail(&wq->wq_queue, (queue_entry_t) thread); ! 391: thread->wait_event = event; ! 392: thread->wait_queue = wq; ! 393: thread_mark_wait_locked(thread, interruptible); ! 394: thread_unlock(thread); ! 395: splx(s); ! 396: if (unlock) ! 397: wait_queue_unlock(wq); ! 398: } ! 399: ! 400: /* ! 401: * Routine: wait_queue_assert_wait ! 402: * Purpose: ! 403: * Insert the current thread into the supplied wait queue ! 404: * waiting for a particular event to be posted to that queue. ! 405: * ! 406: * Conditions: ! 407: * nothing of interest locked. ! 408: */ ! 409: void ! 410: wait_queue_assert_wait( ! 411: wait_queue_t wq, ! 412: event_t event, ! 413: int interruptible) ! 414: { ! 415: spl_t s; ! 416: ! 417: s = splsched(); ! 418: wait_queue_lock(wq); ! 419: wait_queue_assert_wait_locked(wq, event, interruptible, TRUE); ! 420: /* wait queue unlocked */ ! 421: splx(s); ! 422: } ! 423: ! 424: ! 425: /* ! 426: * Routine: wait_queue_select_all ! 427: * Purpose: ! 428: * Select all threads off a wait queue that meet the ! 429: * supplied criteria. ! 430: * ! 431: * Conditions: ! 432: * at splsched ! 433: * wait queue locked ! 434: * wake_queue initialized and ready for insertion ! 435: * possibly recursive ! 436: * ! 437: * Returns: ! 438: * a queue of locked threads ! 439: */ ! 440: void ! 441: _wait_queue_select_all( ! 442: wait_queue_t wq, ! 443: event_t event, ! 444: queue_t wake_queue) ! 445: { ! 446: wait_queue_element_t wq_element; ! 447: wait_queue_element_t wqe_next; ! 448: queue_t q; ! 449: ! 450: q = &wq->wq_queue; ! 451: ! 452: wq_element = (wait_queue_element_t) queue_first(q); ! 453: while (!queue_end(q, (queue_entry_t)wq_element)) { ! 454: wqe_next = (wait_queue_element_t) ! 455: queue_next((queue_t) wq_element); ! 456: ! 457: /* ! 458: * We may have to recurse if this is a compound wait queue. ! 459: */ ! 460: if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) { ! 461: wait_queue_link_t wql = (wait_queue_link_t)wq_element; ! 462: wait_queue_t sub_queue; ! 463: ! 464: /* ! 465: * We have to check the subordinate wait queue. ! 466: */ ! 467: sub_queue = (wait_queue_t)wql->wql_subqueue; ! 468: wait_queue_lock(sub_queue); ! 469: if (! wait_queue_empty(sub_queue)) ! 470: _wait_queue_select_all(sub_queue, event, wake_queue); ! 471: wait_queue_unlock(sub_queue); ! 472: } else { ! 473: ! 474: /* ! 475: * Otherwise, its a thread. If it is waiting on ! 476: * the event we are posting to this queue, pull ! 477: * it off the queue and stick it in out wake_queue. ! 478: */ ! 479: thread_t t = (thread_t)wq_element; ! 480: ! 481: if (t->wait_event == event) { ! 482: thread_lock(t); ! 483: remqueue(q, (queue_entry_t) t); ! 484: enqueue (wake_queue, (queue_entry_t) t); ! 485: t->wait_queue = WAIT_QUEUE_NULL; ! 486: t->wait_event = NO_EVENT; ! 487: t->at_safe_point = FALSE; ! 488: /* returned locked */ ! 489: } ! 490: } ! 491: wq_element = wqe_next; ! 492: } ! 493: } ! 494: ! 495: /* ! 496: * Routine: wait_queue_wakeup_all_locked ! 497: * Purpose: ! 498: * Wakeup some number of threads that are in the specified ! 499: * wait queue and waiting on the specified event. ! 500: * Conditions: ! 501: * wait queue already locked (may be released). ! 502: * Returns: ! 503: * KERN_SUCCESS - Threads were woken up ! 504: * KERN_NOT_WAITING - No threads were waiting <wq,event> pair ! 505: */ ! 506: kern_return_t ! 507: wait_queue_wakeup_all_locked( ! 508: wait_queue_t wq, ! 509: event_t event, ! 510: int result, ! 511: boolean_t unlock) ! 512: { ! 513: queue_head_t wake_queue_head; ! 514: queue_t q = &wake_queue_head; ! 515: kern_return_t ret = KERN_NOT_WAITING; ! 516: spl_t s; ! 517: ! 518: assert(wait_queue_held(wq)); ! 519: ! 520: queue_init(q); ! 521: ! 522: /* ! 523: * Select the threads that we will wake up. The threads ! 524: * are returned to us locked and cleanly removed from the ! 525: * wait queue. ! 526: */ ! 527: s = splsched(); ! 528: _wait_queue_select_all(wq, event, q); ! 529: if (unlock) ! 530: wait_queue_unlock(wq); ! 531: ! 532: /* ! 533: * For each thread, set it running. ! 534: */ ! 535: while (!queue_empty (q)) { ! 536: thread_t thread = (thread_t) dequeue(q); ! 537: thread_go_locked(thread, result); ! 538: thread_unlock(thread); ! 539: ret = KERN_SUCCESS; ! 540: } ! 541: splx(s); ! 542: return ret; ! 543: } ! 544: ! 545: ! 546: /* ! 547: * Routine: wait_queue_wakeup_all ! 548: * Purpose: ! 549: * Wakeup some number of threads that are in the specified ! 550: * wait queue and waiting on the specified event. ! 551: * ! 552: * Conditions: ! 553: * Nothing locked ! 554: * ! 555: * Returns: ! 556: * KERN_SUCCESS - Threads were woken up ! 557: * KERN_NOT_WAITING - No threads were waiting <wq,event> pair ! 558: */ ! 559: kern_return_t ! 560: wait_queue_wakeup_all( ! 561: wait_queue_t wq, ! 562: event_t event, ! 563: int result) ! 564: { ! 565: kern_return_t ret; ! 566: spl_t s; ! 567: ! 568: s = splsched(); ! 569: wait_queue_lock(wq); ! 570: ret = wait_queue_wakeup_all_locked(wq, event, result, TRUE); ! 571: /* lock released */ ! 572: splx(s); ! 573: ! 574: return ret; ! 575: } ! 576: ! 577: /* ! 578: * Routine: wait_queue_select_one ! 579: * Purpose: ! 580: * Select the best thread off a wait queue that meet the ! 581: * supplied criteria. ! 582: * Conditions: ! 583: * at splsched ! 584: * wait queue locked ! 585: * possibly recursive ! 586: * Returns: ! 587: * a locked thread - if one found ! 588: * Note: ! 589: * This is where the sync policy of the wait queue comes ! 590: * into effect. For now, we just assume FIFO. ! 591: */ ! 592: thread_t ! 593: _wait_queue_select_one( ! 594: wait_queue_t wq, ! 595: event_t event) ! 596: { ! 597: wait_queue_element_t wq_element; ! 598: wait_queue_element_t wqe_next; ! 599: thread_t t = THREAD_NULL; ! 600: queue_t q; ! 601: ! 602: assert(wq->wq_fifo); ! 603: ! 604: q = &wq->wq_queue; ! 605: ! 606: wq_element = (wait_queue_element_t) queue_first(q); ! 607: while (!queue_end(q, (queue_entry_t)wq_element)) { ! 608: wqe_next = (wait_queue_element_t) ! 609: queue_next((queue_t) wq_element); ! 610: ! 611: /* ! 612: * We may have to recurse if this is a compound wait queue. ! 613: */ ! 614: if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) { ! 615: wait_queue_link_t wql = (wait_queue_link_t)wq_element; ! 616: wait_queue_t sub_queue; ! 617: ! 618: /* ! 619: * We have to check the subordinate wait queue. ! 620: */ ! 621: sub_queue = (wait_queue_t)wql->wql_subqueue; ! 622: wait_queue_lock(sub_queue); ! 623: if (! wait_queue_empty(sub_queue)) { ! 624: t = _wait_queue_select_one(sub_queue, event); ! 625: } ! 626: wait_queue_unlock(sub_queue); ! 627: if (t != THREAD_NULL) ! 628: return t; ! 629: } else { ! 630: ! 631: /* ! 632: * Otherwise, its a thread. If it is waiting on ! 633: * the event we are posting to this queue, pull ! 634: * it off the queue and stick it in out wake_queue. ! 635: */ ! 636: thread_t t = (thread_t)wq_element; ! 637: ! 638: if (t->wait_event == event) { ! 639: thread_lock(t); ! 640: remqueue(q, (queue_entry_t) t); ! 641: t->wait_queue = WAIT_QUEUE_NULL; ! 642: t->wait_event = NO_EVENT; ! 643: t->at_safe_point = FALSE; ! 644: return t; /* still locked */ ! 645: } ! 646: } ! 647: wq_element = wqe_next; ! 648: } ! 649: return THREAD_NULL; ! 650: } ! 651: ! 652: /* ! 653: * Routine: wait_queue_peek_locked ! 654: * Purpose: ! 655: * Select the best thread from a wait queue that meet the ! 656: * supplied criteria, but leave it on the queue you it was ! 657: * found on. The thread, and the actual wait_queue the ! 658: * thread was found on are identified. ! 659: * Conditions: ! 660: * at splsched ! 661: * wait queue locked ! 662: * possibly recursive ! 663: * Returns: ! 664: * a locked thread - if one found ! 665: * a locked waitq - the one the thread was found on ! 666: * Note: ! 667: * Only the waitq the thread was actually found on is locked ! 668: * after this. ! 669: */ ! 670: void ! 671: wait_queue_peek_locked( ! 672: wait_queue_t wq, ! 673: event_t event, ! 674: thread_t *tp, ! 675: wait_queue_t *wqp) ! 676: { ! 677: wait_queue_element_t wq_element; ! 678: wait_queue_element_t wqe_next; ! 679: thread_t t; ! 680: queue_t q; ! 681: ! 682: assert(wq->wq_fifo); ! 683: ! 684: *tp = THREAD_NULL; ! 685: ! 686: q = &wq->wq_queue; ! 687: ! 688: wq_element = (wait_queue_element_t) queue_first(q); ! 689: while (!queue_end(q, (queue_entry_t)wq_element)) { ! 690: wqe_next = (wait_queue_element_t) ! 691: queue_next((queue_t) wq_element); ! 692: ! 693: /* ! 694: * We may have to recurse if this is a compound wait queue. ! 695: */ ! 696: if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) { ! 697: wait_queue_link_t wql = (wait_queue_link_t)wq_element; ! 698: wait_queue_t sub_queue; ! 699: ! 700: /* ! 701: * We have to check the subordinate wait queue. ! 702: */ ! 703: sub_queue = (wait_queue_t)wql->wql_subqueue; ! 704: wait_queue_lock(sub_queue); ! 705: if (! wait_queue_empty(sub_queue)) { ! 706: wait_queue_peek_locked(sub_queue, event, tp, wqp); ! 707: } ! 708: if (*tp != THREAD_NULL) ! 709: return; /* thread and its waitq locked */ ! 710: ! 711: wait_queue_unlock(sub_queue); ! 712: } else { ! 713: ! 714: /* ! 715: * Otherwise, its a thread. If it is waiting on ! 716: * the event we are posting to this queue, return ! 717: * it locked, but leave it on the queue. ! 718: */ ! 719: thread_t t = (thread_t)wq_element; ! 720: ! 721: if (t->wait_event == event) { ! 722: thread_lock(t); ! 723: *tp = t; ! 724: *wqp = wq; ! 725: return; ! 726: } ! 727: } ! 728: wq_element = wqe_next; ! 729: } ! 730: } ! 731: ! 732: /* ! 733: * Routine: wait_queue_pull_thread_locked ! 734: * Purpose: ! 735: * Pull a thread that was previously "peeked" off the wait ! 736: * queue and (possibly) unlock the waitq. ! 737: * Conditions: ! 738: * at splsched ! 739: * wait queue locked ! 740: * thread locked ! 741: * Returns: ! 742: * with the thread still locked. ! 743: */ ! 744: void ! 745: wait_queue_pull_thread_locked( ! 746: wait_queue_t waitq, ! 747: thread_t thread, ! 748: boolean_t unlock) ! 749: { ! 750: ! 751: assert(thread->wait_queue == waitq); ! 752: ! 753: remqueue(&waitq->wq_queue, (queue_entry_t)thread ); ! 754: thread->wait_queue = WAIT_QUEUE_NULL; ! 755: thread->wait_event = NO_EVENT; ! 756: thread->at_safe_point = FALSE; ! 757: if (unlock) ! 758: wait_queue_unlock(waitq); ! 759: } ! 760: ! 761: ! 762: /* ! 763: * Routine: wait_queue_select_thread ! 764: * Purpose: ! 765: * Look for a thread and remove it from the queues, if ! 766: * (and only if) the thread is waiting on the supplied ! 767: * <wait_queue, event> pair. ! 768: * Conditions: ! 769: * at splsched ! 770: * wait queue locked ! 771: * possibly recursive ! 772: * Returns: ! 773: * KERN_NOT_WAITING: Thread is not waiting here. ! 774: * KERN_SUCCESS: It was, and is now removed (returned locked) ! 775: */ ! 776: kern_return_t ! 777: _wait_queue_select_thread( ! 778: wait_queue_t wq, ! 779: event_t event, ! 780: thread_t thread) ! 781: { ! 782: wait_queue_element_t wq_element; ! 783: wait_queue_element_t wqe_next; ! 784: kern_return_t res = KERN_NOT_WAITING; ! 785: queue_t q = &wq->wq_queue; ! 786: ! 787: assert(wq->wq_fifo); ! 788: ! 789: thread_lock(thread); ! 790: if ((thread->wait_queue == wq) && (thread->wait_event == event)) { ! 791: remqueue(q, (queue_entry_t) thread); ! 792: thread->at_safe_point = FALSE; ! 793: thread->wait_event = NO_EVENT; ! 794: thread->wait_queue = WAIT_QUEUE_NULL; ! 795: /* thread still locked */ ! 796: return KERN_SUCCESS; ! 797: } ! 798: thread_unlock(thread); ! 799: ! 800: /* ! 801: * The wait_queue associated with the thread may be one of this ! 802: * wait queue's subordinates. Go see. If so, removing it from ! 803: * there is like removing it from here. ! 804: */ ! 805: wq_element = (wait_queue_element_t) queue_first(q); ! 806: while (!queue_end(q, (queue_entry_t)wq_element)) { ! 807: wqe_next = (wait_queue_element_t) ! 808: queue_next((queue_t) wq_element); ! 809: ! 810: if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) { ! 811: wait_queue_link_t wql = (wait_queue_link_t)wq_element; ! 812: wait_queue_t sub_queue; ! 813: ! 814: sub_queue = (wait_queue_t)wql->wql_subqueue; ! 815: wait_queue_lock(sub_queue); ! 816: if (! wait_queue_empty(sub_queue)) { ! 817: res = _wait_queue_select_thread(sub_queue, ! 818: event, ! 819: thread); ! 820: } ! 821: wait_queue_unlock(sub_queue); ! 822: if (res == KERN_SUCCESS) ! 823: return KERN_SUCCESS; ! 824: } ! 825: wq_element = wqe_next; ! 826: } ! 827: return res; ! 828: } ! 829: ! 830: ! 831: /* ! 832: * Routine: wait_queue_wakeup_identity_locked ! 833: * Purpose: ! 834: * Select a single thread that is most-eligible to run and set ! 835: * set it running. But return the thread locked. ! 836: * ! 837: * Conditions: ! 838: * at splsched ! 839: * wait queue locked ! 840: * possibly recursive ! 841: * Returns: ! 842: * a pointer to the locked thread that was awoken ! 843: */ ! 844: thread_t ! 845: wait_queue_wakeup_identity_locked( ! 846: wait_queue_t wq, ! 847: event_t event, ! 848: int result, ! 849: boolean_t unlock) ! 850: { ! 851: thread_t thread; ! 852: spl_t s; ! 853: ! 854: assert(wait_queue_held(wq)); ! 855: ! 856: s = splsched(); ! 857: thread = _wait_queue_select_one(wq, event); ! 858: if (unlock) ! 859: wait_queue_unlock(wq); ! 860: ! 861: if (thread) { ! 862: thread_go_locked(thread, result); ! 863: splx(s); ! 864: return thread; /* still locked */ ! 865: } ! 866: splx(s); ! 867: return THREAD_NULL; ! 868: } ! 869: ! 870: ! 871: /* ! 872: * Routine: wait_queue_wakeup_one_locked ! 873: * Purpose: ! 874: * Select a single thread that is most-eligible to run and set ! 875: * set it runnings. ! 876: * ! 877: * Conditions: ! 878: * at splsched ! 879: * wait queue locked ! 880: * possibly recursive ! 881: * Returns: ! 882: * KERN_SUCCESS: It was, and is, now removed. ! 883: * KERN_NOT_WAITING - No thread was waiting <wq,event> pair ! 884: */ ! 885: kern_return_t ! 886: wait_queue_wakeup_one_locked( ! 887: wait_queue_t wq, ! 888: event_t event, ! 889: int result, ! 890: boolean_t unlock) ! 891: { ! 892: thread_t thread; ! 893: spl_t s; ! 894: ! 895: assert(wait_queue_held(wq)); ! 896: ! 897: s = splsched(); ! 898: thread = _wait_queue_select_one(wq, event); ! 899: if (unlock) ! 900: wait_queue_unlock(wq); ! 901: ! 902: if (thread) { ! 903: thread_go_locked(thread, result); ! 904: thread_unlock(thread); ! 905: splx(s); ! 906: return KERN_SUCCESS; ! 907: } ! 908: ! 909: splx(s); ! 910: return KERN_NOT_WAITING; ! 911: } ! 912: ! 913: /* ! 914: * Routine: wait_queue_wakeup_one ! 915: * Purpose: ! 916: * Wakeup the most appropriate thread that is in the specified ! 917: * wait queue for the specified event. ! 918: * ! 919: * Conditions: ! 920: * Nothing locked ! 921: * ! 922: * Returns: ! 923: * KERN_SUCCESS - Thread was woken up ! 924: * KERN_NOT_WAITING - No thread was waiting <wq,event> pair ! 925: */ ! 926: kern_return_t ! 927: wait_queue_wakeup_one( ! 928: wait_queue_t wq, ! 929: event_t event, ! 930: int result) ! 931: { ! 932: thread_t thread; ! 933: spl_t s; ! 934: ! 935: s = splsched(); ! 936: wait_queue_lock(wq); ! 937: thread = _wait_queue_select_one(wq, event); ! 938: wait_queue_unlock(wq); ! 939: ! 940: if (thread) { ! 941: thread_go_locked(thread, result); ! 942: thread_unlock(thread); ! 943: splx(s); ! 944: return KERN_SUCCESS; ! 945: } ! 946: ! 947: splx(s); ! 948: return KERN_NOT_WAITING; ! 949: } ! 950: ! 951: ! 952: ! 953: /* ! 954: * Routine: wait_queue_wakeup_thread_locked ! 955: * Purpose: ! 956: * Wakeup the particular thread that was specified if and only ! 957: * it was in this wait queue (or one of it's subordinate queues) ! 958: * and waiting on the specified event. ! 959: * ! 960: * This is much safer than just removing the thread from ! 961: * whatever wait queue it happens to be on. For instance, it ! 962: * may have already been awoken from the wait you intended to ! 963: * interrupt and waited on something else (like another ! 964: * semaphore). ! 965: * Conditions: ! 966: * wait queue already locked (may be released). ! 967: * Returns: ! 968: * KERN_SUCCESS - the thread was found waiting and awakened ! 969: * KERN_NOT_WAITING - the thread was not waiting here ! 970: */ ! 971: kern_return_t ! 972: wait_queue_wakeup_thread_locked( ! 973: wait_queue_t wq, ! 974: event_t event, ! 975: thread_t thread, ! 976: int result, ! 977: boolean_t unlock) ! 978: { ! 979: kern_return_t res; ! 980: spl_t s; ! 981: ! 982: assert(wait_queue_held(wq)); ! 983: ! 984: /* ! 985: * See if the thread was still waiting there. If so, it got ! 986: * dequeued and returned locked. ! 987: */ ! 988: s = splsched(); ! 989: res = _wait_queue_select_thread(wq, event, thread); ! 990: if (unlock) ! 991: wait_queue_unlock(wq); ! 992: ! 993: if (res != KERN_SUCCESS) { ! 994: splx(s); ! 995: return KERN_NOT_WAITING; ! 996: } ! 997: ! 998: thread_go_locked(thread, result); ! 999: thread_unlock(thread); ! 1000: splx(s); ! 1001: return KERN_SUCCESS; ! 1002: } ! 1003: ! 1004: /* ! 1005: * Routine: wait_queue_wakeup_thread ! 1006: * Purpose: ! 1007: * Wakeup the particular thread that was specified if and only ! 1008: * it was in this wait queue (or one of it's subordinate queues) ! 1009: * and waiting on the specified event. ! 1010: * ! 1011: * This is much safer than just removing the thread from ! 1012: * whatever wait queue it happens to be on. For instance, it ! 1013: * may have already been awoken from the wait you intended to ! 1014: * interrupt and waited on something else (like another ! 1015: * semaphore). ! 1016: * Conditions: ! 1017: * nothing of interest locked ! 1018: * we need to assume spl needs to be raised ! 1019: * Returns: ! 1020: * KERN_SUCCESS - the thread was found waiting and awakened ! 1021: * KERN_NOT_WAITING - the thread was not waiting here ! 1022: */ ! 1023: kern_return_t ! 1024: wait_queue_wakeup_thread( ! 1025: wait_queue_t wq, ! 1026: event_t event, ! 1027: thread_t thread, ! 1028: int result) ! 1029: { ! 1030: kern_return_t res; ! 1031: spl_t s; ! 1032: ! 1033: s = splsched(); ! 1034: wait_queue_lock(wq); ! 1035: res = _wait_queue_select_thread(wq, event, thread); ! 1036: wait_queue_unlock(wq); ! 1037: ! 1038: if (res == KERN_SUCCESS) { ! 1039: thread_go_locked(thread, result); ! 1040: thread_unlock(thread); ! 1041: splx(s); ! 1042: return KERN_SUCCESS; ! 1043: } ! 1044: splx(s); ! 1045: return KERN_NOT_WAITING; ! 1046: } ! 1047: ! 1048: ! 1049: /* ! 1050: * Routine: wait_queue_remove ! 1051: * Purpose: ! 1052: * Normal removal operations from wait queues drive from the ! 1053: * wait queue to select a thread. However, if a thread is ! 1054: * interrupted out of a wait, this routine is called to ! 1055: * remove it from whatever wait queue it may be in. ! 1056: * ! 1057: * Conditions: ! 1058: * splsched ! 1059: * thread locked on entry and exit, but may be dropped. ! 1060: * ! 1061: * Returns: ! 1062: * KERN_SUCCESS - if thread was in a wait queue ! 1063: * KERN_NOT_WAITING - it was not ! 1064: */ ! 1065: kern_return_t ! 1066: wait_queue_remove( ! 1067: thread_t thread) ! 1068: { ! 1069: wait_queue_t wq = thread->wait_queue; ! 1070: ! 1071: if (wq == WAIT_QUEUE_NULL) ! 1072: return KERN_NOT_WAITING; ! 1073: ! 1074: /* ! 1075: * have to get the locks again in the right order. ! 1076: */ ! 1077: thread_unlock(thread); ! 1078: wait_queue_lock(wq); ! 1079: thread_lock(thread); ! 1080: ! 1081: if (thread->wait_queue == wq) { ! 1082: remqueue(&wq->wq_queue, (queue_entry_t)thread); ! 1083: thread->wait_queue = WAIT_QUEUE_NULL; ! 1084: thread->wait_event = NO_EVENT; ! 1085: thread->at_safe_point = FALSE; ! 1086: wait_queue_unlock(wq); ! 1087: return KERN_SUCCESS; ! 1088: } else { ! 1089: wait_queue_unlock(wq); ! 1090: return KERN_NOT_WAITING; /* anymore */ ! 1091: } ! 1092: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.