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