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