osfmk/kern/locks.c

   1 /*
   2  * Copyright (c) 2000-2007 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
  54  * the rights to redistribute these changes.
  55  */
  56 #include <mach_kdb.h>
  57 #include <mach_ldebug.h>
  58 #include <debug.h>
  59
  60 #include <mach/kern_return.h>
  61 #include <mach/mach_host_server.h>
  62 #include <mach_debug/lockgroup_info.h>
  63
  64 #include <kern/locks.h>
  65 #include <kern/misc_protos.h>
  66 #include <kern/kalloc.h>
  67 #include <kern/thread.h>
  68 #include <kern/processor.h>
  69 #include <kern/sched_prim.h>
  70 #include <kern/debug.h>
  71 #include <string.h>
  72
  73
  74 #include <sys/kdebug.h>
  75
  76 #if     CONFIG_DTRACE
  77 /*
  78  * We need only enough declarations from the BSD-side to be able to
  79  * test if our probe is active, and to call __dtrace_probe().  Setting
  80  * NEED_DTRACE_DEFS gets a local copy of those definitions pulled in.
  81  */
  82 #define NEED_DTRACE_DEFS
  83 #include <../bsd/sys/lockstat.h>
  84 #endif
  85
  86 #define LCK_MTX_SLEEP_CODE              0
  87 #define LCK_MTX_SLEEP_DEADLINE_CODE     1
  88 #define LCK_MTX_LCK_WAIT_CODE           2
  89 #define LCK_MTX_UNLCK_WAKEUP_CODE       3
  90
  91
  92 static queue_head_t     lck_grp_queue;
  93 static unsigned int     lck_grp_cnt;
  94
  95 decl_lck_mtx_data(static,lck_grp_lock)
  96 static lck_mtx_ext_t lck_grp_lock_ext;
  97
  98 lck_grp_attr_t  LockDefaultGroupAttr;
  99 lck_grp_t               LockCompatGroup;
 100 lck_attr_t              LockDefaultLckAttr;
 101
 102 /*
 103  * Routine:     lck_mod_init
 104  */
 105
 106 void
 107 lck_mod_init(
 108         void)
 109 {
 110         /*
 111          * Obtain "lcks" options:this currently controls lock statistics
 112          */
 113         if (!PE_parse_boot_argn("lcks", &LcksOpts, sizeof (LcksOpts)))
 114                 LcksOpts = 0;
 115
 116         queue_init(&lck_grp_queue);
 117
 118         /*
 119          * Need to bootstrap the LockCompatGroup instead of calling lck_grp_init() here. This avoids
 120          * grabbing the lck_grp_lock before it is initialized.
 121          */
 122
 123         bzero(&LockCompatGroup, sizeof(lck_grp_t));
 124         (void) strncpy(LockCompatGroup.lck_grp_name, "Compatibility APIs", LCK_GRP_MAX_NAME);
 125
 126         if (LcksOpts & enaLkStat)
 127                 LockCompatGroup.lck_grp_attr = LCK_GRP_ATTR_STAT;
 128     else
 129                 LockCompatGroup.lck_grp_attr = LCK_ATTR_NONE;
 130
 131         LockCompatGroup.lck_grp_refcnt = 1;
 132
 133         enqueue_tail(&lck_grp_queue, (queue_entry_t)&LockCompatGroup);
 134         lck_grp_cnt = 1;
 135
 136         lck_grp_attr_setdefault(&LockDefaultGroupAttr);
 137         lck_attr_setdefault(&LockDefaultLckAttr);
 138
 139         lck_mtx_init_ext(&lck_grp_lock, &lck_grp_lock_ext, &LockCompatGroup, &LockDefaultLckAttr);
 140
 141 }
 142
 143 /*
 144  * Routine:     lck_grp_attr_alloc_init
 145  */
 146
 147 lck_grp_attr_t  *
 148 lck_grp_attr_alloc_init(
 149         void)
 150 {
 151         lck_grp_attr_t  *attr;
 152
 153         if ((attr = (lck_grp_attr_t *)kalloc(sizeof(lck_grp_attr_t))) != 0)
 154                 lck_grp_attr_setdefault(attr);
 155
 156         return(attr);
 157 }
 158
 159
 160 /*
 161  * Routine:     lck_grp_attr_setdefault
 162  */
 163
 164 void
 165 lck_grp_attr_setdefault(
 166         lck_grp_attr_t  *attr)
 167 {
 168         if (LcksOpts & enaLkStat)
 169                 attr->grp_attr_val = LCK_GRP_ATTR_STAT;
 170         else
 171                 attr->grp_attr_val = 0;
 172 }
 173
 174
 175 /*
 176  * Routine:     lck_grp_attr_setstat
 177  */
 178
 179 void
 180 lck_grp_attr_setstat(
 181         lck_grp_attr_t  *attr)
 182 {
 183         (void)hw_atomic_or(&attr->grp_attr_val, LCK_GRP_ATTR_STAT);
 184 }
 185
 186
 187 /*
 188  * Routine:     lck_grp_attr_free
 189  */
 190
 191 void
 192 lck_grp_attr_free(
 193         lck_grp_attr_t  *attr)
 194 {
 195         kfree(attr, sizeof(lck_grp_attr_t));
 196 }
 197
 198
 199 /*
 200  * Routine:     lck_grp_alloc_init
 201  */
 202
 203 lck_grp_t *
 204 lck_grp_alloc_init(
 205         const char*     grp_name,
 206         lck_grp_attr_t  *attr)
 207 {
 208         lck_grp_t       *grp;
 209
 210         if ((grp = (lck_grp_t *)kalloc(sizeof(lck_grp_t))) != 0)
 211                 lck_grp_init(grp, grp_name, attr);
 212
 213         return(grp);
 214 }
 215
 216
 217 /*
 218  * Routine:     lck_grp_init
 219  */
 220
 221 void
 222 lck_grp_init(
 223         lck_grp_t               *grp,
 224         const char*             grp_name,
 225         lck_grp_attr_t  *attr)
 226 {
 227         bzero((void *)grp, sizeof(lck_grp_t));
 228
 229         (void) strncpy(grp->lck_grp_name, grp_name, LCK_GRP_MAX_NAME);
 230
 231         if (attr != LCK_GRP_ATTR_NULL)
 232                 grp->lck_grp_attr = attr->grp_attr_val;
 233         else if (LcksOpts & enaLkStat)
 234                 grp->lck_grp_attr = LCK_GRP_ATTR_STAT;
 235         else
 236                 grp->lck_grp_attr = LCK_ATTR_NONE;
 237
 238         grp->lck_grp_refcnt = 1;
 239
 240         lck_mtx_lock(&lck_grp_lock);
 241         enqueue_tail(&lck_grp_queue, (queue_entry_t)grp);
 242         lck_grp_cnt++;
 243         lck_mtx_unlock(&lck_grp_lock);
 244
 245 }
 246
 247
 248 /*
 249  * Routine:     lck_grp_free
 250  */
 251
 252 void
 253 lck_grp_free(
 254         lck_grp_t       *grp)
 255 {
 256         lck_mtx_lock(&lck_grp_lock);
 257         lck_grp_cnt--;
 258         (void)remque((queue_entry_t)grp);
 259         lck_mtx_unlock(&lck_grp_lock);
 260         lck_grp_deallocate(grp);
 261 }
 262
 263
 264 /*
 265  * Routine:     lck_grp_reference
 266  */
 267
 268 void
 269 lck_grp_reference(
 270         lck_grp_t       *grp)
 271 {
 272         (void)hw_atomic_add(&grp->lck_grp_refcnt, 1);
 273 }
 274
 275
 276 /*
 277  * Routine:     lck_grp_deallocate
 278  */
 279
 280 void
 281 lck_grp_deallocate(
 282         lck_grp_t       *grp)
 283 {
 284         if (hw_atomic_sub(&grp->lck_grp_refcnt, 1) == 0)
 285                 kfree(grp, sizeof(lck_grp_t));
 286 }
 287
 288 /*
 289  * Routine:     lck_grp_lckcnt_incr
 290  */
 291
 292 void
 293 lck_grp_lckcnt_incr(
 294         lck_grp_t       *grp,
 295         lck_type_t      lck_type)
 296 {
 297         unsigned int    *lckcnt;
 298
 299         switch (lck_type) {
 300         case LCK_TYPE_SPIN:
 301                 lckcnt = &grp->lck_grp_spincnt;
 302                 break;
 303         case LCK_TYPE_MTX:
 304                 lckcnt = &grp->lck_grp_mtxcnt;
 305                 break;
 306         case LCK_TYPE_RW:
 307                 lckcnt = &grp->lck_grp_rwcnt;
 308                 break;
 309         default:
 310                 return panic("lck_grp_lckcnt_incr(): invalid lock type: %d\n", lck_type);
 311         }
 312
 313         (void)hw_atomic_add(lckcnt, 1);
 314 }
 315
 316 /*
 317  * Routine:     lck_grp_lckcnt_decr
 318  */
 319
 320 void
 321 lck_grp_lckcnt_decr(
 322         lck_grp_t       *grp,
 323         lck_type_t      lck_type)
 324 {
 325         unsigned int    *lckcnt;
 326
 327         switch (lck_type) {
 328         case LCK_TYPE_SPIN:
 329                 lckcnt = &grp->lck_grp_spincnt;
 330                 break;
 331         case LCK_TYPE_MTX:
 332                 lckcnt = &grp->lck_grp_mtxcnt;
 333                 break;
 334         case LCK_TYPE_RW:
 335                 lckcnt = &grp->lck_grp_rwcnt;
 336                 break;
 337         default:
 338                 return panic("lck_grp_lckcnt_decr(): invalid lock type: %d\n", lck_type);
 339         }
 340
 341         (void)hw_atomic_sub(lckcnt, 1);
 342 }
 343
 344 /*
 345  * Routine:     lck_attr_alloc_init
 346  */
 347
 348 lck_attr_t *
 349 lck_attr_alloc_init(
 350         void)
 351 {
 352         lck_attr_t      *attr;
 353
 354         if ((attr = (lck_attr_t *)kalloc(sizeof(lck_attr_t))) != 0)
 355                 lck_attr_setdefault(attr);
 356
 357         return(attr);
 358 }
 359
 360
 361 /*
 362  * Routine:     lck_attr_setdefault
 363  */
 364
 365 void
 366 lck_attr_setdefault(
 367         lck_attr_t      *attr)
 368 {
 369 #if     !DEBUG
 370         if (LcksOpts & enaLkDeb)
 371                 attr->lck_attr_val =  LCK_ATTR_DEBUG;
 372         else
 373                 attr->lck_attr_val =  LCK_ATTR_NONE;
 374 #else
 375         attr->lck_attr_val =  LCK_ATTR_DEBUG;
 376 #endif  /* !DEBUG */
 377 }
 378
 379
 380 /*
 381  * Routine:     lck_attr_setdebug
 382  */
 383 void
 384 lck_attr_setdebug(
 385         lck_attr_t      *attr)
 386 {
 387         (void)hw_atomic_or(&attr->lck_attr_val, LCK_ATTR_DEBUG);
 388 }
 389
 390 /*
 391  * Routine:     lck_attr_setdebug
 392  */
 393 void
 394 lck_attr_cleardebug(
 395         lck_attr_t      *attr)
 396 {
 397         (void)hw_atomic_and(&attr->lck_attr_val, ~LCK_ATTR_DEBUG);
 398 }
 399
 400
 401 /*
 402  * Routine:     lck_attr_rw_shared_priority
 403  */
 404 void
 405 lck_attr_rw_shared_priority(
 406         lck_attr_t      *attr)
 407 {
 408         (void)hw_atomic_or(&attr->lck_attr_val, LCK_ATTR_RW_SHARED_PRIORITY);
 409 }
 410
 411
 412 /*
 413  * Routine:     lck_attr_free
 414  */
 415 void
 416 lck_attr_free(
 417         lck_attr_t      *attr)
 418 {
 419         kfree(attr, sizeof(lck_attr_t));
 420 }
 421
 422
 423 /*
 424  * Routine:     lck_spin_sleep
 425  */
 426 wait_result_t
 427 lck_spin_sleep(
 428         lck_spin_t              *lck,
 429         lck_sleep_action_t      lck_sleep_action,
 430         event_t                 event,
 431         wait_interrupt_t        interruptible)
 432 {
 433         wait_result_t   res;
 434
 435         if ((lck_sleep_action & ~LCK_SLEEP_MASK) != 0)
 436                 panic("Invalid lock sleep action %x\n", lck_sleep_action);
 437
 438         res = assert_wait(event, interruptible);
 439         if (res == THREAD_WAITING) {
 440                 lck_spin_unlock(lck);
 441                 res = thread_block(THREAD_CONTINUE_NULL);
 442                 if (!(lck_sleep_action & LCK_SLEEP_UNLOCK))
 443                         lck_spin_lock(lck);
 444         }
 445         else
 446         if (lck_sleep_action & LCK_SLEEP_UNLOCK)
 447                 lck_spin_unlock(lck);
 448
 449         return res;
 450 }
 451
 452
 453 /*
 454  * Routine:     lck_spin_sleep_deadline
 455  */
 456 wait_result_t
 457 lck_spin_sleep_deadline(
 458         lck_spin_t              *lck,
 459         lck_sleep_action_t      lck_sleep_action,
 460         event_t                 event,
 461         wait_interrupt_t        interruptible,
 462         uint64_t                deadline)
 463 {
 464         wait_result_t   res;
 465
 466         if ((lck_sleep_action & ~LCK_SLEEP_MASK) != 0)
 467                 panic("Invalid lock sleep action %x\n", lck_sleep_action);
 468
 469         res = assert_wait_deadline(event, interruptible, deadline);
 470         if (res == THREAD_WAITING) {
 471                 lck_spin_unlock(lck);
 472                 res = thread_block(THREAD_CONTINUE_NULL);
 473                 if (!(lck_sleep_action & LCK_SLEEP_UNLOCK))
 474                         lck_spin_lock(lck);
 475         }
 476         else
 477         if (lck_sleep_action & LCK_SLEEP_UNLOCK)
 478                 lck_spin_unlock(lck);
 479
 480         return res;
 481 }
 482
 483
 484 /*
 485  * Routine:     lck_mtx_sleep
 486  */
 487 wait_result_t
 488 lck_mtx_sleep(
 489         lck_mtx_t               *lck,
 490         lck_sleep_action_t      lck_sleep_action,
 491         event_t                 event,
 492         wait_interrupt_t        interruptible)
 493 {
 494         wait_result_t   res;
 495
 496         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_SLEEP_CODE) | DBG_FUNC_START,
 497                      (int)lck, (int)lck_sleep_action, (int)event, (int)interruptible, 0);
 498
 499         if ((lck_sleep_action & ~LCK_SLEEP_MASK) != 0)
 500                 panic("Invalid lock sleep action %x\n", lck_sleep_action);
 501
 502         res = assert_wait(event, interruptible);
 503         if (res == THREAD_WAITING) {
 504                 lck_mtx_unlock(lck);
 505                 res = thread_block(THREAD_CONTINUE_NULL);
 506                 if (!(lck_sleep_action & LCK_SLEEP_UNLOCK)) {
 507                         if ((lck_sleep_action & LCK_SLEEP_SPIN))
 508                                 lck_mtx_lock_spin(lck);
 509                         else
 510                                 lck_mtx_lock(lck);
 511                 }
 512         }
 513         else
 514         if (lck_sleep_action & LCK_SLEEP_UNLOCK)
 515                 lck_mtx_unlock(lck);
 516
 517         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_SLEEP_CODE) | DBG_FUNC_END, (int)res, 0, 0, 0, 0);
 518
 519         return res;
 520 }
 521
 522
 523 /*
 524  * Routine:     lck_mtx_sleep_deadline
 525  */
 526 wait_result_t
 527 lck_mtx_sleep_deadline(
 528         lck_mtx_t               *lck,
 529         lck_sleep_action_t      lck_sleep_action,
 530         event_t                 event,
 531         wait_interrupt_t        interruptible,
 532         uint64_t                deadline)
 533 {
 534         wait_result_t   res;
 535
 536         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_SLEEP_DEADLINE_CODE) | DBG_FUNC_START,
 537                      (int)lck, (int)lck_sleep_action, (int)event, (int)interruptible, 0);
 538
 539         if ((lck_sleep_action & ~LCK_SLEEP_MASK) != 0)
 540                 panic("Invalid lock sleep action %x\n", lck_sleep_action);
 541
 542         res = assert_wait_deadline(event, interruptible, deadline);
 543         if (res == THREAD_WAITING) {
 544                 lck_mtx_unlock(lck);
 545                 res = thread_block(THREAD_CONTINUE_NULL);
 546                 if (!(lck_sleep_action & LCK_SLEEP_UNLOCK)) {
 547                         if ((lck_sleep_action & LCK_SLEEP_SPIN))
 548                                 lck_mtx_lock_spin(lck);
 549                         else
 550                                 lck_mtx_lock(lck);
 551                 }
 552         }
 553         else
 554         if (lck_sleep_action & LCK_SLEEP_UNLOCK)
 555                 lck_mtx_unlock(lck);
 556
 557         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_SLEEP_DEADLINE_CODE) | DBG_FUNC_END, (int)res, 0, 0, 0, 0);
 558
 559         return res;
 560 }
 561
 562 /*
 563  * Routine:     lck_mtx_lock_wait
 564  *
 565  * Invoked in order to wait on contention.
 566  *
 567  * Called with the interlock locked and
 568  * returns it unlocked.
 569  */
 570 void
 571 lck_mtx_lock_wait (
 572         lck_mtx_t                       *lck,
 573         thread_t                        holder)
 574 {
 575         thread_t                self = current_thread();
 576         lck_mtx_t               *mutex;
 577         integer_t               priority;
 578         spl_t                   s = splsched();
 579 #if     CONFIG_DTRACE
 580         uint64_t                sleep_start = 0;
 581
 582         if (lockstat_probemap[LS_LCK_MTX_LOCK_BLOCK] || lockstat_probemap[LS_LCK_MTX_EXT_LOCK_BLOCK]) {
 583                 sleep_start = mach_absolute_time();
 584         }
 585 #endif
 586
 587         if (lck->lck_mtx_tag != LCK_MTX_TAG_INDIRECT)
 588                 mutex = lck;
 589         else
 590                 mutex = &lck->lck_mtx_ptr->lck_mtx;
 591
 592         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_LCK_WAIT_CODE) | DBG_FUNC_START, (int)lck, (int)holder, 0, 0, 0);
 593
 594         priority = self->sched_pri;
 595         if (priority < self->priority)
 596                 priority = self->priority;
 597         if (priority < BASEPRI_DEFAULT)
 598                 priority = BASEPRI_DEFAULT;
 599
 600         thread_lock(holder);
 601         if (mutex->lck_mtx_pri == 0)
 602                 holder->promotions++;
 603         holder->sched_flags |= TH_SFLAG_PROMOTED;
 604         if (            mutex->lck_mtx_pri < priority   &&
 605                                 holder->sched_pri < priority            ) {
 606                 KERNEL_DEBUG_CONSTANT(
 607                         MACHDBG_CODE(DBG_MACH_SCHED,MACH_PROMOTE) | DBG_FUNC_NONE,
 608                                         holder->sched_pri, priority, holder, lck, 0);
 609
 610                 set_sched_pri(holder, priority);
 611         }
 612         thread_unlock(holder);
 613         splx(s);
 614
 615         if (mutex->lck_mtx_pri < priority)
 616                 mutex->lck_mtx_pri = priority;
 617         if (self->pending_promoter[self->pending_promoter_index] == NULL) {
 618                 self->pending_promoter[self->pending_promoter_index] = mutex;
 619                 mutex->lck_mtx_waiters++;
 620         }
 621         else
 622         if (self->pending_promoter[self->pending_promoter_index] != mutex) {
 623                 self->pending_promoter[++self->pending_promoter_index] = mutex;
 624                 mutex->lck_mtx_waiters++;
 625         }
 626
 627         assert_wait((event_t)(((unsigned int*)lck)+((sizeof(lck_mtx_t)-1)/sizeof(unsigned int))), THREAD_UNINT);
 628         lck_mtx_ilk_unlock(mutex);
 629
 630         thread_block(THREAD_CONTINUE_NULL);
 631
 632         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_LCK_WAIT_CODE) | DBG_FUNC_END, 0, 0, 0, 0, 0);
 633 #if     CONFIG_DTRACE
 634         /*
 635          * Record the Dtrace lockstat probe for blocking, block time
 636          * measured from when we were entered.
 637          */
 638         if (sleep_start) {
 639                 if (lck->lck_mtx_tag != LCK_MTX_TAG_INDIRECT) {
 640                         LOCKSTAT_RECORD(LS_LCK_MTX_LOCK_BLOCK, lck,
 641                             mach_absolute_time() - sleep_start);
 642                 } else {
 643                         LOCKSTAT_RECORD(LS_LCK_MTX_EXT_LOCK_BLOCK, lck,
 644                             mach_absolute_time() - sleep_start);
 645                 }
 646         }
 647 #endif
 648 }
 649
 650 /*
 651  * Routine:     lck_mtx_lock_acquire
 652  *
 653  * Invoked on acquiring the mutex when there is
 654  * contention.
 655  *
 656  * Returns the current number of waiters.
 657  *
 658  * Called with the interlock locked.
 659  */
 660 int
 661 lck_mtx_lock_acquire(
 662         lck_mtx_t               *lck)
 663 {
 664         thread_t                thread = current_thread();
 665         lck_mtx_t               *mutex;
 666
 667         if (lck->lck_mtx_tag != LCK_MTX_TAG_INDIRECT)
 668                 mutex = lck;
 669         else
 670                 mutex = &lck->lck_mtx_ptr->lck_mtx;
 671
 672         if (thread->pending_promoter[thread->pending_promoter_index] == mutex) {
 673                 thread->pending_promoter[thread->pending_promoter_index] = NULL;
 674                 if (thread->pending_promoter_index > 0)
 675                         thread->pending_promoter_index--;
 676                 mutex->lck_mtx_waiters--;
 677         }
 678
 679         if (mutex->lck_mtx_waiters > 0) {
 680                 integer_t               priority = mutex->lck_mtx_pri;
 681                 spl_t                   s = splsched();
 682
 683                 thread_lock(thread);
 684                 thread->promotions++;
 685                 thread->sched_flags |= TH_SFLAG_PROMOTED;
 686                 if (thread->sched_pri < priority) {
 687                         KERNEL_DEBUG_CONSTANT(
 688                                 MACHDBG_CODE(DBG_MACH_SCHED,MACH_PROMOTE) | DBG_FUNC_NONE,
 689                                                 thread->sched_pri, priority, 0, lck, 0);
 690
 691                         set_sched_pri(thread, priority);
 692                 }
 693                 thread_unlock(thread);
 694                 splx(s);
 695         }
 696         else
 697                 mutex->lck_mtx_pri = 0;
 698
 699         return (mutex->lck_mtx_waiters);
 700 }
 701
 702 /*
 703  * Routine:     lck_mtx_unlock_wakeup
 704  *
 705  * Invoked on unlock when there is contention.
 706  *
 707  * Called with the interlock locked.
 708  */
 709 void
 710 lck_mtx_unlock_wakeup (
 711         lck_mtx_t                       *lck,
 712         thread_t                        holder)
 713 {
 714         thread_t                thread = current_thread();
 715         lck_mtx_t               *mutex;
 716
 717         if (lck->lck_mtx_tag != LCK_MTX_TAG_INDIRECT)
 718                 mutex = lck;
 719         else
 720                 mutex = &lck->lck_mtx_ptr->lck_mtx;
 721
 722         if (thread != holder)
 723                 panic("lck_mtx_unlock_wakeup: mutex %p holder %p\n", mutex, holder);
 724
 725         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_UNLCK_WAKEUP_CODE) | DBG_FUNC_START, (int)lck, (int)holder, 0, 0, 0);
 726
 727         assert(mutex->lck_mtx_waiters > 0);
 728         thread_wakeup_one((event_t)(((unsigned int*)lck)+(sizeof(lck_mtx_t)-1)/sizeof(unsigned int)));
 729
 730         if (thread->promotions > 0) {
 731                 spl_t           s = splsched();
 732
 733                 thread_lock(thread);
 734                 if (    --thread->promotions == 0                               &&
 735                                 (thread->sched_flags & TH_SFLAG_PROMOTED)               ) {
 736                         thread->sched_flags &= ~TH_SFLAG_PROMOTED;
 737                         if (thread->sched_flags & TH_SFLAG_DEPRESSED_MASK) {
 738                                 KERNEL_DEBUG_CONSTANT(
 739                                         MACHDBG_CODE(DBG_MACH_SCHED,MACH_DEMOTE) | DBG_FUNC_NONE,
 740                                                   thread->sched_pri, DEPRESSPRI, 0, lck, 0);
 741
 742                                 set_sched_pri(thread, DEPRESSPRI);
 743                         }
 744                         else {
 745                                 if (thread->priority < thread->sched_pri) {
 746                                         KERNEL_DEBUG_CONSTANT(
 747                                                 MACHDBG_CODE(DBG_MACH_SCHED,MACH_DEMOTE) |
 748                                                                                                                         DBG_FUNC_NONE,
 749                                                         thread->sched_pri, thread->priority,
 750                                                                         0, lck, 0);
 751                                 }
 752
 753                                 SCHED(compute_priority)(thread, FALSE);
 754                         }
 755                 }
 756                 thread_unlock(thread);
 757                 splx(s);
 758         }
 759
 760         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_UNLCK_WAKEUP_CODE) | DBG_FUNC_END, 0, 0, 0, 0, 0);
 761 }
 762
 763 void
 764 lck_mtx_unlockspin_wakeup (
 765         lck_mtx_t                       *lck)
 766 {
 767         assert(lck->lck_mtx_waiters > 0);
 768         thread_wakeup_one((event_t)(((unsigned int*)lck)+(sizeof(lck_mtx_t)-1)/sizeof(unsigned int)));
 769
 770         KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_LOCKS, LCK_MTX_UNLCK_WAKEUP_CODE) | DBG_FUNC_NONE, (int)lck, 0, 0, 1, 0);
 771 #if CONFIG_DTRACE
 772         /*
 773          * When there are waiters, we skip the hot-patch spot in the
 774          * fastpath, so we record it here.
 775          */
 776         LOCKSTAT_RECORD(LS_LCK_MTX_UNLOCK_RELEASE, lck, 0);
 777 #endif
 778 }
 779
 780
 781 /*
 782  * Routine:     mutex_pause
 783  *
 784  * Called by former callers of simple_lock_pause().
 785  */
 786 #define MAX_COLLISION_COUNTS    32
 787 #define MAX_COLLISION   8
 788
 789 unsigned int max_collision_count[MAX_COLLISION_COUNTS];
 790
 791 uint32_t collision_backoffs[MAX_COLLISION] = {
 792         10, 50, 100, 200, 400, 600, 800, 1000
 793 };
 794
 795
 796 void
 797 mutex_pause(uint32_t collisions)
 798 {
 799         wait_result_t wait_result;
 800         uint32_t        back_off;
 801
 802         if (collisions >= MAX_COLLISION_COUNTS)
 803                 collisions = MAX_COLLISION_COUNTS - 1;
 804         max_collision_count[collisions]++;
 805
 806         if (collisions >= MAX_COLLISION)
 807                 collisions = MAX_COLLISION - 1;
 808         back_off = collision_backoffs[collisions];
 809
 810         wait_result = assert_wait_timeout((event_t)mutex_pause, THREAD_UNINT, back_off, NSEC_PER_USEC);
 811         assert(wait_result == THREAD_WAITING);
 812
 813         wait_result = thread_block(THREAD_CONTINUE_NULL);
 814         assert(wait_result == THREAD_TIMED_OUT);
 815 }
 816
 817
 818 unsigned int mutex_yield_wait = 0;
 819 unsigned int mutex_yield_no_wait = 0;
 820
 821 void
 822 lck_mtx_yield(
 823             lck_mtx_t   *lck)
 824 {
 825         int     waiters;
 826
 827 #if DEBUG
 828         lck_mtx_assert(lck, LCK_MTX_ASSERT_OWNED);
 829 #endif /* DEBUG */
 830
 831         if (lck->lck_mtx_tag == LCK_MTX_TAG_INDIRECT)
 832                 waiters = lck->lck_mtx_ptr->lck_mtx.lck_mtx_waiters;
 833         else
 834                 waiters = lck->lck_mtx_waiters;
 835
 836         if ( !waiters) {
 837                 mutex_yield_no_wait++;
 838         } else {
 839                 mutex_yield_wait++;
 840                 lck_mtx_unlock(lck);
 841                 mutex_pause(0);
 842                 lck_mtx_lock(lck);
 843         }
 844 }
 845
 846
 847 /*
 848  * Routine:     lck_rw_sleep
 849  */
 850 wait_result_t
 851 lck_rw_sleep(
 852         lck_rw_t                *lck,
 853         lck_sleep_action_t      lck_sleep_action,
 854         event_t                 event,
 855         wait_interrupt_t        interruptible)
 856 {
 857         wait_result_t   res;
 858         lck_rw_type_t   lck_rw_type;
 859
 860         if ((lck_sleep_action & ~LCK_SLEEP_MASK) != 0)
 861                 panic("Invalid lock sleep action %x\n", lck_sleep_action);
 862
 863         res = assert_wait(event, interruptible);
 864         if (res == THREAD_WAITING) {
 865                 lck_rw_type = lck_rw_done(lck);
 866                 res = thread_block(THREAD_CONTINUE_NULL);
 867                 if (!(lck_sleep_action & LCK_SLEEP_UNLOCK)) {
 868                         if (!(lck_sleep_action & (LCK_SLEEP_SHARED|LCK_SLEEP_EXCLUSIVE)))
 869                                 lck_rw_lock(lck, lck_rw_type);
 870                         else if (lck_sleep_action & LCK_SLEEP_EXCLUSIVE)
 871                                 lck_rw_lock_exclusive(lck);
 872                         else
 873                                 lck_rw_lock_shared(lck);
 874                 }
 875         }
 876         else
 877         if (lck_sleep_action & LCK_SLEEP_UNLOCK)
 878                 (void)lck_rw_done(lck);
 879
 880         return res;
 881 }
 882
 883
 884 /*
 885  * Routine:     lck_rw_sleep_deadline
 886  */
 887 wait_result_t
 888 lck_rw_sleep_deadline(
 889         lck_rw_t                *lck,
 890         lck_sleep_action_t      lck_sleep_action,
 891         event_t                 event,
 892         wait_interrupt_t        interruptible,
 893         uint64_t                deadline)
 894 {
 895         wait_result_t   res;
 896         lck_rw_type_t   lck_rw_type;
 897
 898         if ((lck_sleep_action & ~LCK_SLEEP_MASK) != 0)
 899                 panic("Invalid lock sleep action %x\n", lck_sleep_action);
 900
 901         res = assert_wait_deadline(event, interruptible, deadline);
 902         if (res == THREAD_WAITING) {
 903                 lck_rw_type = lck_rw_done(lck);
 904                 res = thread_block(THREAD_CONTINUE_NULL);
 905                 if (!(lck_sleep_action & LCK_SLEEP_UNLOCK)) {
 906                         if (!(lck_sleep_action & (LCK_SLEEP_SHARED|LCK_SLEEP_EXCLUSIVE)))
 907                                 lck_rw_lock(lck, lck_rw_type);
 908                         else if (lck_sleep_action & LCK_SLEEP_EXCLUSIVE)
 909                                 lck_rw_lock_exclusive(lck);
 910                         else
 911                                 lck_rw_lock_shared(lck);
 912                 }
 913         }
 914         else
 915         if (lck_sleep_action & LCK_SLEEP_UNLOCK)
 916                 (void)lck_rw_done(lck);
 917
 918         return res;
 919 }
 920
 921 kern_return_t
 922 host_lockgroup_info(
 923         host_t                                  host,
 924         lockgroup_info_array_t  *lockgroup_infop,
 925         mach_msg_type_number_t  *lockgroup_infoCntp)
 926 {
 927         lockgroup_info_t        *lockgroup_info_base;
 928         lockgroup_info_t        *lockgroup_info;
 929         vm_offset_t                     lockgroup_info_addr;
 930         vm_size_t                       lockgroup_info_size;
 931         lck_grp_t                       *lck_grp;
 932         unsigned int            i;
 933         vm_size_t                       used;
 934         vm_map_copy_t           copy;
 935         kern_return_t           kr;
 936
 937         if (host == HOST_NULL)
 938                 return KERN_INVALID_HOST;
 939
 940         lck_mtx_lock(&lck_grp_lock);
 941
 942         lockgroup_info_size = round_page(lck_grp_cnt * sizeof *lockgroup_info);
 943         kr = kmem_alloc_pageable(ipc_kernel_map,
 944                                                  &lockgroup_info_addr, lockgroup_info_size);
 945         if (kr != KERN_SUCCESS) {
 946                 lck_mtx_unlock(&lck_grp_lock);
 947                 return(kr);
 948         }
 949
 950         lockgroup_info_base = (lockgroup_info_t *) lockgroup_info_addr;
 951         lck_grp = (lck_grp_t *)queue_first(&lck_grp_queue);
 952         lockgroup_info = lockgroup_info_base;
 953
 954         for (i = 0; i < lck_grp_cnt; i++) {
 955
 956                 lockgroup_info->lock_spin_cnt = lck_grp->lck_grp_spincnt;
 957                 lockgroup_info->lock_spin_util_cnt = lck_grp->lck_grp_stat.lck_grp_spin_stat.lck_grp_spin_util_cnt;
 958                 lockgroup_info->lock_spin_held_cnt = lck_grp->lck_grp_stat.lck_grp_spin_stat.lck_grp_spin_held_cnt;
 959                 lockgroup_info->lock_spin_miss_cnt = lck_grp->lck_grp_stat.lck_grp_spin_stat.lck_grp_spin_miss_cnt;
 960                 lockgroup_info->lock_spin_held_max = lck_grp->lck_grp_stat.lck_grp_spin_stat.lck_grp_spin_held_max;
 961                 lockgroup_info->lock_spin_held_cum = lck_grp->lck_grp_stat.lck_grp_spin_stat.lck_grp_spin_held_cum;
 962
 963                 lockgroup_info->lock_mtx_cnt = lck_grp->lck_grp_mtxcnt;
 964                 lockgroup_info->lock_mtx_util_cnt = lck_grp->lck_grp_stat.lck_grp_mtx_stat.lck_grp_mtx_util_cnt;
 965                 lockgroup_info->lock_mtx_held_cnt = lck_grp->lck_grp_stat.lck_grp_mtx_stat.lck_grp_mtx_held_cnt;
 966                 lockgroup_info->lock_mtx_miss_cnt = lck_grp->lck_grp_stat.lck_grp_mtx_stat.lck_grp_mtx_miss_cnt;
 967                 lockgroup_info->lock_mtx_wait_cnt = lck_grp->lck_grp_stat.lck_grp_mtx_stat.lck_grp_mtx_wait_cnt;
 968                 lockgroup_info->lock_mtx_held_max = lck_grp->lck_grp_stat.lck_grp_mtx_stat.lck_grp_mtx_held_max;
 969                 lockgroup_info->lock_mtx_held_cum = lck_grp->lck_grp_stat.lck_grp_mtx_stat.lck_grp_mtx_held_cum;
 970                 lockgroup_info->lock_mtx_wait_max = lck_grp->lck_grp_stat.lck_grp_mtx_stat.lck_grp_mtx_wait_max;
 971                 lockgroup_info->lock_mtx_wait_cum = lck_grp->lck_grp_stat.lck_grp_mtx_stat.lck_grp_mtx_wait_cum;
 972
 973                 lockgroup_info->lock_rw_cnt = lck_grp->lck_grp_rwcnt;
 974                 lockgroup_info->lock_rw_util_cnt = lck_grp->lck_grp_stat.lck_grp_rw_stat.lck_grp_rw_util_cnt;
 975                 lockgroup_info->lock_rw_held_cnt = lck_grp->lck_grp_stat.lck_grp_rw_stat.lck_grp_rw_held_cnt;
 976                 lockgroup_info->lock_rw_miss_cnt = lck_grp->lck_grp_stat.lck_grp_rw_stat.lck_grp_rw_miss_cnt;
 977                 lockgroup_info->lock_rw_wait_cnt = lck_grp->lck_grp_stat.lck_grp_rw_stat.lck_grp_rw_wait_cnt;
 978                 lockgroup_info->lock_rw_held_max = lck_grp->lck_grp_stat.lck_grp_rw_stat.lck_grp_rw_held_max;
 979                 lockgroup_info->lock_rw_held_cum = lck_grp->lck_grp_stat.lck_grp_rw_stat.lck_grp_rw_held_cum;
 980                 lockgroup_info->lock_rw_wait_max = lck_grp->lck_grp_stat.lck_grp_rw_stat.lck_grp_rw_wait_max;
 981                 lockgroup_info->lock_rw_wait_cum = lck_grp->lck_grp_stat.lck_grp_rw_stat.lck_grp_rw_wait_cum;
 982
 983                 (void) strncpy(lockgroup_info->lockgroup_name,lck_grp->lck_grp_name, LOCKGROUP_MAX_NAME);
 984
 985                 lck_grp = (lck_grp_t *)(queue_next((queue_entry_t)(lck_grp)));
 986                 lockgroup_info++;
 987         }
 988
 989         *lockgroup_infoCntp = lck_grp_cnt;
 990         lck_mtx_unlock(&lck_grp_lock);
 991
 992         used = (*lockgroup_infoCntp) * sizeof *lockgroup_info;
 993
 994         if (used != lockgroup_info_size)
 995                 bzero((char *) lockgroup_info, lockgroup_info_size - used);
 996
 997         kr = vm_map_copyin(ipc_kernel_map, (vm_map_address_t)lockgroup_info_addr,
 998                            (vm_map_size_t)lockgroup_info_size, TRUE, &copy);
 999         assert(kr == KERN_SUCCESS);
1000
1001         *lockgroup_infop = (lockgroup_info_t *) copy;
1002
1003         return(KERN_SUCCESS);
1004 }
1005
1006 /*
1007  * Compatibility module
1008  */
1009
1010 extern lck_rw_t         *lock_alloc_EXT( boolean_t can_sleep, unsigned short  tag0, unsigned short  tag1);
1011 extern void             lock_done_EXT(lck_rw_t *lock);
1012 extern void             lock_free_EXT(lck_rw_t *lock);
1013 extern void             lock_init_EXT(lck_rw_t *lock, boolean_t can_sleep, unsigned short tag0, unsigned short tag1);
1014 extern void             lock_read_EXT(lck_rw_t *lock);
1015 extern boolean_t        lock_read_to_write_EXT(lck_rw_t *lock);
1016 extern void             lock_write_EXT(lck_rw_t *lock);
1017 extern void             lock_write_to_read_EXT(lck_rw_t *lock);
1018 extern wait_result_t    thread_sleep_lock_write_EXT(
1019                                 event_t event, lck_rw_t *lock, wait_interrupt_t interruptible);
1020
1021 extern void             usimple_lock_EXT(lck_spin_t *lock);
1022 extern void             usimple_lock_init_EXT(lck_spin_t *lock, unsigned short tag);
1023 extern unsigned int     usimple_lock_try_EXT(lck_spin_t *lock);
1024 extern void             usimple_unlock_EXT(lck_spin_t *lock);
1025 extern wait_result_t    thread_sleep_usimple_lock_EXT(event_t event, lck_spin_t *lock, wait_interrupt_t interruptible);
1026
1027
1028 lck_mtx_t*              mutex_alloc_EXT(__unused unsigned short tag);
1029 void                    mutex_free_EXT(lck_mtx_t *mutex);
1030 void                    mutex_init_EXT(lck_mtx_t *mutex, __unused unsigned short tag);
1031 wait_result_t           thread_sleep_mutex_EXT(event_t event, lck_mtx_t *mutex, wait_interrupt_t interruptible);
1032 wait_result_t           thread_sleep_mutex_deadline_EXT(event_t event, lck_mtx_t *mutex, uint64_t deadline, wait_interrupt_t interruptible);
1033
1034 lck_rw_t *
1035 lock_alloc_EXT(
1036         __unused boolean_t       can_sleep,
1037         __unused unsigned short  tag0,
1038         __unused unsigned short  tag1)
1039 {
1040         return( lck_rw_alloc_init( &LockCompatGroup, LCK_ATTR_NULL));
1041 }
1042
1043 void
1044 lock_done_EXT(
1045         lck_rw_t        *lock)
1046 {
1047         (void) lck_rw_done(lock);
1048 }
1049
1050 void
1051 lock_free_EXT(
1052         lck_rw_t        *lock)
1053 {
1054         lck_rw_free(lock, &LockCompatGroup);
1055 }
1056
1057 void
1058 lock_init_EXT(
1059         lck_rw_t        *lock,
1060         __unused boolean_t      can_sleep,
1061         __unused unsigned short tag0,
1062         __unused unsigned short tag1)
1063 {
1064         lck_rw_init(lock, &LockCompatGroup, LCK_ATTR_NULL);
1065 }
1066
1067 void
1068 lock_read_EXT(
1069         lck_rw_t        *lock)
1070 {
1071         lck_rw_lock_shared( lock);
1072 }
1073
1074 boolean_t
1075 lock_read_to_write_EXT(
1076         lck_rw_t        *lock)
1077 {
1078         return( lck_rw_lock_shared_to_exclusive(lock));
1079 }
1080
1081 void
1082 lock_write_EXT(
1083         lck_rw_t        *lock)
1084 {
1085         lck_rw_lock_exclusive(lock);
1086 }
1087
1088 void
1089 lock_write_to_read_EXT(
1090         lck_rw_t        *lock)
1091 {
1092         lck_rw_lock_exclusive_to_shared(lock);
1093 }
1094
1095 wait_result_t
1096 thread_sleep_lock_write_EXT(
1097         event_t                 event,
1098         lck_rw_t                *lock,
1099         wait_interrupt_t        interruptible)
1100 {
1101         return( lck_rw_sleep(lock, LCK_SLEEP_EXCLUSIVE, event, interruptible));
1102 }
1103
1104 void
1105 usimple_lock_EXT(
1106         lck_spin_t              *lock)
1107 {
1108         lck_spin_lock(lock);
1109 }
1110
1111 void
1112 usimple_lock_init_EXT(
1113         lck_spin_t              *lock,
1114         __unused unsigned short tag)
1115 {
1116         lck_spin_init(lock, &LockCompatGroup, LCK_ATTR_NULL);
1117 }
1118
1119 unsigned int
1120 usimple_lock_try_EXT(
1121         lck_spin_t              *lock)
1122 {
1123         return(lck_spin_try_lock(lock));
1124 }
1125
1126 void
1127 usimple_unlock_EXT(
1128         lck_spin_t              *lock)
1129 {
1130         lck_spin_unlock(lock);
1131 }
1132
1133 wait_result_t
1134 thread_sleep_usimple_lock_EXT(
1135         event_t                 event,
1136         lck_spin_t              *lock,
1137         wait_interrupt_t        interruptible)
1138 {
1139         return( lck_spin_sleep(lock, LCK_SLEEP_DEFAULT, event, interruptible));
1140 }
1141 lck_mtx_t *
1142 mutex_alloc_EXT(
1143         __unused unsigned short         tag)
1144 {
1145         return(lck_mtx_alloc_init(&LockCompatGroup, LCK_ATTR_NULL));
1146 }
1147
1148 void
1149 mutex_free_EXT(
1150         lck_mtx_t               *mutex)
1151 {
1152         lck_mtx_free(mutex, &LockCompatGroup);
1153 }
1154
1155 void
1156 mutex_init_EXT(
1157         lck_mtx_t               *mutex,
1158         __unused unsigned short tag)
1159 {
1160         lck_mtx_init(mutex, &LockCompatGroup, LCK_ATTR_NULL);
1161 }
1162
1163 wait_result_t
1164 thread_sleep_mutex_EXT(
1165         event_t                 event,
1166         lck_mtx_t               *mutex,
1167         wait_interrupt_t        interruptible)
1168 {
1169         return( lck_mtx_sleep(mutex, LCK_SLEEP_DEFAULT, event, interruptible));
1170 }
1171
1172 wait_result_t
1173 thread_sleep_mutex_deadline_EXT(
1174         event_t                 event,
1175         lck_mtx_t               *mutex,
1176         uint64_t                deadline,
1177         wait_interrupt_t        interruptible)
1178 {
1179         return( lck_mtx_sleep_deadline(mutex, LCK_SLEEP_DEFAULT, event, interruptible, deadline));
1180 }