sys/kern/kern_mutex.c

   1 /*
   2  * Copyright (c) 2009 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34 /*
  35  * Implement fast persistent locks based on atomic_cmpset_int() with
  36  * semantics similar to lockmgr locks but faster and taking up much less
  37  * space.  Taken from HAMMER's lock implementation.
  38  *
  39  * These are meant to complement our LWKT tokens.  Tokens are only held
  40  * while the thread is running.  Mutexes can be held across blocking
  41  * conditions.
  42  *
  43  * Most of the support is in sys/mutex[2].h.  We mostly provide backoff
  44  * functions here.
  45  */
  46
  47 #include <sys/param.h>
  48 #include <sys/systm.h>
  49 #include <sys/kernel.h>
  50 #include <sys/sysctl.h>
  51 #include <sys/thread.h>
  52
  53 #include <machine/cpufunc.h>
  54
  55 #include <sys/thread2.h>
  56 #include <sys/mutex2.h>
  57
  58 static __int64_t mtx_contention_count;
  59 static __int64_t mtx_collision_count;
  60 static __int64_t mtx_wakeup_count;
  61
  62 SYSCTL_QUAD(_kern, OID_AUTO, mtx_contention_count, CTLFLAG_RW,
  63             &mtx_contention_count, 0, "");
  64 SYSCTL_QUAD(_kern, OID_AUTO, mtx_collision_count, CTLFLAG_RW,
  65             &mtx_collision_count, 0, "");
  66 SYSCTL_QUAD(_kern, OID_AUTO, mtx_wakeup_count, CTLFLAG_RW,
  67             &mtx_wakeup_count, 0, "");
  68
  69 static void mtx_chain_link(mtx_t mtx);
  70 static void mtx_delete_link(mtx_t mtx, mtx_link_t link);
  71
  72 /*
  73  * Exclusive-lock a mutex, block until acquired.  Recursion is allowed.
  74  *
  75  * Returns 0 on success, or the tsleep() return code on failure.
  76  * An error can only be returned if PCATCH is specified in the flags.
  77  */
  78 static __inline int
  79 __mtx_lock_ex(mtx_t mtx, mtx_link_t link, const char *ident, int flags, int to)
  80 {
  81         u_int   lock;
  82         u_int   nlock;
  83         int     error;
  84
  85         for (;;) {
  86                 lock = mtx->mtx_lock;
  87                 if (lock == 0) {
  88                         nlock = MTX_EXCLUSIVE | 1;
  89                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
  90                                 mtx->mtx_owner = curthread;
  91                                 error = 0;
  92                                 break;
  93                         }
  94                 } else if ((lock & MTX_EXCLUSIVE) &&
  95                            mtx->mtx_owner == curthread) {
  96                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  97                         nlock = lock + 1;
  98                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  99                                 error = 0;
 100                                 break;
 101                         }
 102                 } else {
 103                         /*
 104                          * Clearing MTX_EXLINK in lock causes us to loop until
 105                          * MTX_EXLINK is available.  However, to avoid
 106                          * unnecessary cpu cache traffic we poll instead.
 107                          *
 108                          * Setting MTX_EXLINK in nlock causes us to loop until
 109                          * we can acquire MTX_EXLINK.
 110                          *
 111                          * Also set MTX_EXWANTED coincident with EXLINK, if
 112                          * not already set.
 113                          */
 114                         thread_t td;
 115
 116                         if (lock & MTX_EXLINK) {
 117                                 cpu_pause();
 118                                 ++mtx_collision_count;
 119                                 continue;
 120                         }
 121                         td = curthread;
 122                         /*lock &= ~MTX_EXLINK;*/
 123                         nlock = lock | MTX_EXWANTED | MTX_EXLINK;
 124                         ++td->td_critcount;
 125                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 126                                 /*
 127                                  * Check for early abort
 128                                  */
 129                                 if (link->state == MTX_LINK_ABORTED) {
 130                                         atomic_clear_int(&mtx->mtx_lock,
 131                                                          MTX_EXLINK);
 132                                         --td->td_critcount;
 133                                         error = ENOLCK;
 134                                         if (mtx->mtx_link == NULL) {
 135                                                 atomic_clear_int(&mtx->mtx_lock,
 136                                                                  MTX_EXWANTED);
 137                                         }
 138                                         break;
 139                                 }
 140
 141                                 /*
 142                                  * Success.  Link in our structure then
 143                                  * release EXLINK and sleep.
 144                                  */
 145                                 link->owner = td;
 146                                 link->state = MTX_LINK_LINKED;
 147                                 if (mtx->mtx_link) {
 148                                         link->next = mtx->mtx_link;
 149                                         link->prev = link->next->prev;
 150                                         link->next->prev = link;
 151                                         link->prev->next = link;
 152                                 } else {
 153                                         link->next = link;
 154                                         link->prev = link;
 155                                         mtx->mtx_link = link;
 156                                 }
 157                                 tsleep_interlock(link, 0);
 158                                 atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
 159                                 --td->td_critcount;
 160
 161                                 error = tsleep(link, flags | PINTERLOCKED,
 162                                                ident, to);
 163                                 ++mtx_contention_count;
 164
 165                                 /*
 166                                  * Normal unlink, we should own the exclusive
 167                                  * lock now.
 168                                  */
 169                                 if (link->state == MTX_LINK_LINKED)
 170                                         mtx_delete_link(mtx, link);
 171                                 if (link->state == MTX_LINK_ACQUIRED) {
 172                                         KKASSERT(mtx->mtx_owner == link->owner);
 173                                         error = 0;
 174                                         break;
 175                                 }
 176
 177                                 /*
 178                                  * Aborted lock (mtx_abort_ex called).
 179                                  */
 180                                 if (link->state == MTX_LINK_ABORTED) {
 181                                         error = ENOLCK;
 182                                         break;
 183                                 }
 184
 185                                 /*
 186                                  * tsleep error, else retry.
 187                                  */
 188                                 if (error)
 189                                         break;
 190                         } else {
 191                                 --td->td_critcount;
 192                         }
 193                 }
 194                 ++mtx_collision_count;
 195         }
 196         return (error);
 197 }
 198
 199 int
 200 _mtx_lock_ex_link(mtx_t mtx, mtx_link_t link,
 201                   const char *ident, int flags, int to)
 202 {
 203         return(__mtx_lock_ex(mtx, link, ident, flags, to));
 204 }
 205
 206 int
 207 _mtx_lock_ex(mtx_t mtx, const char *ident, int flags, int to)
 208 {
 209         struct mtx_link link;
 210
 211         mtx_link_init(&link);
 212         return(__mtx_lock_ex(mtx, &link, ident, flags, to));
 213 }
 214
 215 int
 216 _mtx_lock_ex_quick(mtx_t mtx, const char *ident)
 217 {
 218         struct mtx_link link;
 219
 220         mtx_link_init(&link);
 221         return(__mtx_lock_ex(mtx, &link, ident, 0, 0));
 222 }
 223
 224 /*
 225  * Share-lock a mutex, block until acquired.  Recursion is allowed.
 226  *
 227  * Returns 0 on success, or the tsleep() return code on failure.
 228  * An error can only be returned if PCATCH is specified in the flags.
 229  *
 230  * NOTE: Shared locks get a mass-wakeup so if the tsleep fails we
 231  *       do not have to chain the wakeup().
 232  */
 233 static __inline int
 234 __mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
 235 {
 236         u_int   lock;
 237         u_int   nlock;
 238         int     error;
 239
 240         for (;;) {
 241                 lock = mtx->mtx_lock;
 242                 if ((lock & MTX_EXCLUSIVE) == 0) {
 243                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 244                         nlock = lock + 1;
 245                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 246                                 error = 0;
 247                                 break;
 248                         }
 249                 } else {
 250                         nlock = lock | MTX_SHWANTED;
 251                         tsleep_interlock(mtx, 0);
 252                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 253                                 error = tsleep(mtx, flags | PINTERLOCKED,
 254                                                ident, to);
 255                                 if (error)
 256                                         break;
 257                                 ++mtx_contention_count;
 258                                 /* retry */
 259                         } else {
 260                                 crit_enter();
 261                                 tsleep_remove(curthread);
 262                                 crit_exit();
 263                         }
 264                 }
 265                 ++mtx_collision_count;
 266         }
 267         return (error);
 268 }
 269
 270 int
 271 _mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
 272 {
 273         return (__mtx_lock_sh(mtx, ident, flags, to));
 274 }
 275
 276 int
 277 _mtx_lock_sh_quick(mtx_t mtx, const char *ident)
 278 {
 279         return (__mtx_lock_sh(mtx, ident, 0, 0));
 280 }
 281
 282 /*
 283  * Get an exclusive spinlock the hard way.
 284  */
 285 void
 286 _mtx_spinlock(mtx_t mtx)
 287 {
 288         u_int   lock;
 289         u_int   nlock;
 290         int     bb = 1;
 291         int     bo;
 292
 293         for (;;) {
 294                 lock = mtx->mtx_lock;
 295                 if (lock == 0) {
 296                         nlock = MTX_EXCLUSIVE | 1;
 297                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 298                                 mtx->mtx_owner = curthread;
 299                                 break;
 300                         }
 301                 } else if ((lock & MTX_EXCLUSIVE) &&
 302                            mtx->mtx_owner == curthread) {
 303                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 304                         nlock = lock + 1;
 305                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 306                                 break;
 307                 } else {
 308                         /* MWAIT here */
 309                         if (bb < 1000)
 310                                 ++bb;
 311                         cpu_pause();
 312                         for (bo = 0; bo < bb; ++bo)
 313                                 ;
 314                         ++mtx_contention_count;
 315                 }
 316                 cpu_pause();
 317                 ++mtx_collision_count;
 318         }
 319 }
 320
 321 /*
 322  * Attempt to acquire a spinlock, if we fail we must undo the
 323  * gd->gd_spinlocks/gd->gd_curthead->td_critcount predisposition.
 324  *
 325  * Returns 0 on success, EAGAIN on failure.
 326  */
 327 int
 328 _mtx_spinlock_try(mtx_t mtx)
 329 {
 330         globaldata_t gd = mycpu;
 331         u_int   lock;
 332         u_int   nlock;
 333         int     res = 0;
 334
 335         for (;;) {
 336                 lock = mtx->mtx_lock;
 337                 if (lock == 0) {
 338                         nlock = MTX_EXCLUSIVE | 1;
 339                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 340                                 mtx->mtx_owner = gd->gd_curthread;
 341                                 break;
 342                         }
 343                 } else if ((lock & MTX_EXCLUSIVE) &&
 344                            mtx->mtx_owner == gd->gd_curthread) {
 345                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 346                         nlock = lock + 1;
 347                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 348                                 break;
 349                 } else {
 350                         --gd->gd_spinlocks;
 351                         cpu_ccfence();
 352                         --gd->gd_curthread->td_critcount;
 353                         res = EAGAIN;
 354                         break;
 355                 }
 356                 cpu_pause();
 357                 ++mtx_collision_count;
 358         }
 359         return res;
 360 }
 361
 362 #if 0
 363
 364 void
 365 _mtx_spinlock_sh(mtx_t mtx)
 366 {
 367         u_int   lock;
 368         u_int   nlock;
 369         int     bb = 1;
 370         int     bo;
 371
 372         for (;;) {
 373                 lock = mtx->mtx_lock;
 374                 if ((lock & MTX_EXCLUSIVE) == 0) {
 375                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 376                         nlock = lock + 1;
 377                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 378                                 break;
 379                 } else {
 380                         /* MWAIT here */
 381                         if (bb < 1000)
 382                                 ++bb;
 383                         cpu_pause();
 384                         for (bo = 0; bo < bb; ++bo)
 385                                 ;
 386                         ++mtx_contention_count;
 387                 }
 388                 cpu_pause();
 389                 ++mtx_collision_count;
 390         }
 391 }
 392
 393 #endif
 394
 395 int
 396 _mtx_lock_ex_try(mtx_t mtx)
 397 {
 398         u_int   lock;
 399         u_int   nlock;
 400         int     error = 0;
 401
 402         for (;;) {
 403                 lock = mtx->mtx_lock;
 404                 if (lock == 0) {
 405                         nlock = MTX_EXCLUSIVE | 1;
 406                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 407                                 mtx->mtx_owner = curthread;
 408                                 break;
 409                         }
 410                 } else if ((lock & MTX_EXCLUSIVE) &&
 411                            mtx->mtx_owner == curthread) {
 412                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 413                         nlock = lock + 1;
 414                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 415                                 break;
 416                 } else {
 417                         error = EAGAIN;
 418                         break;
 419                 }
 420                 cpu_pause();
 421                 ++mtx_collision_count;
 422         }
 423         return (error);
 424 }
 425
 426 int
 427 _mtx_lock_sh_try(mtx_t mtx)
 428 {
 429         u_int   lock;
 430         u_int   nlock;
 431         int     error = 0;
 432
 433         for (;;) {
 434                 lock = mtx->mtx_lock;
 435                 if ((lock & MTX_EXCLUSIVE) == 0) {
 436                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 437                         nlock = lock + 1;
 438                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 439                                 break;
 440                 } else {
 441                         error = EAGAIN;
 442                         break;
 443                 }
 444                 cpu_pause();
 445                 ++mtx_collision_count;
 446         }
 447         return (error);
 448 }
 449
 450 /*
 451  * If the lock is held exclusively it must be owned by the caller.  If the
 452  * lock is already a shared lock this operation is a NOP.  A panic will
 453  * occur if the lock is not held either shared or exclusive.
 454  *
 455  * The exclusive count is converted to a shared count.
 456  */
 457 void
 458 _mtx_downgrade(mtx_t mtx)
 459 {
 460         u_int   lock;
 461         u_int   nlock;
 462
 463         for (;;) {
 464                 lock = mtx->mtx_lock;
 465                 if ((lock & MTX_EXCLUSIVE) == 0) {
 466                         KKASSERT((lock & MTX_MASK) > 0);
 467                         break;
 468                 }
 469                 KKASSERT(mtx->mtx_owner == curthread);
 470                 nlock = lock & ~(MTX_EXCLUSIVE | MTX_SHWANTED);
 471                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 472                         if (lock & MTX_SHWANTED) {
 473                                 wakeup(mtx);
 474                                 ++mtx_wakeup_count;
 475                         }
 476                         break;
 477                 }
 478                 cpu_pause();
 479                 ++mtx_collision_count;
 480         }
 481 }
 482
 483 /*
 484  * Upgrade a shared lock to an exclusive lock.  The upgrade will fail if
 485  * the shared lock has a count other then 1.  Optimize the most likely case
 486  * but note that a single cmpset can fail due to WANTED races.
 487  *
 488  * If the lock is held exclusively it must be owned by the caller and
 489  * this function will simply return without doing anything.   A panic will
 490  * occur if the lock is held exclusively by someone other then the caller.
 491  *
 492  * Returns 0 on success, EDEADLK on failure.
 493  */
 494 int
 495 _mtx_upgrade_try(mtx_t mtx)
 496 {
 497         u_int   lock;
 498         u_int   nlock;
 499         int     error = 0;
 500
 501         for (;;) {
 502                 lock = mtx->mtx_lock;
 503
 504                 if ((lock & ~MTX_EXWANTED) == 1) {
 505                         nlock = lock | MTX_EXCLUSIVE;
 506                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 507                                 mtx->mtx_owner = curthread;
 508                                 break;
 509                         }
 510                 } else if (lock & MTX_EXCLUSIVE) {
 511                         KKASSERT(mtx->mtx_owner == curthread);
 512                         break;
 513                 } else {
 514                         error = EDEADLK;
 515                         break;
 516                 }
 517                 cpu_pause();
 518                 ++mtx_collision_count;
 519         }
 520         return (error);
 521 }
 522
 523 /*
 524  * Unlock a lock.  The caller must hold the lock either shared or exclusive.
 525  *
 526  * Any release which makes the lock available when others want an exclusive
 527  * lock causes us to chain the owner to the next exclusive lock instead of
 528  * releasing the lock.
 529  */
 530 void
 531 _mtx_unlock(mtx_t mtx)
 532 {
 533         u_int   lock;
 534         u_int   nlock;
 535
 536         for (;;) {
 537                 lock = mtx->mtx_lock;
 538                 nlock = lock & ~(MTX_SHWANTED | MTX_EXLINK);
 539
 540                 if (nlock == 1) {
 541                         /*
 542                          * Last release, shared lock, no exclusive waiters.
 543                          */
 544                         nlock = lock & MTX_EXLINK;
 545                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 546                                 break;
 547                 } else if (nlock == (MTX_EXCLUSIVE | 1)) {
 548                         /*
 549                          * Last release, exclusive lock, no exclusive waiters.
 550                          * Wake up any shared waiters.
 551                          */
 552                         mtx->mtx_owner = NULL;
 553                         nlock = lock & MTX_EXLINK;
 554                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 555                                 if (lock & MTX_SHWANTED) {
 556                                         wakeup(mtx);
 557                                         ++mtx_wakeup_count;
 558                                 }
 559                                 break;
 560                         }
 561                 } else if (nlock == (MTX_EXWANTED | 1)) {
 562                         /*
 563                          * Last release, shared lock, with exclusive
 564                          * waiters.
 565                          *
 566                          * Wait for EXLINK to clear, then acquire it.
 567                          * We could use the cmpset for this but polling
 568                          * is better on the cpu caches.
 569                          *
 570                          * Acquire an exclusive lock leaving the lockcount
 571                          * set to 1, and get EXLINK for access to mtx_link.
 572                          */
 573                         thread_t td;
 574
 575                         if (lock & MTX_EXLINK) {
 576                                 cpu_pause();
 577                                 ++mtx_collision_count;
 578                                 continue;
 579                         }
 580                         td = curthread;
 581                         /*lock &= ~MTX_EXLINK;*/
 582                         nlock |= MTX_EXLINK | MTX_EXCLUSIVE;
 583                         nlock |= (lock & MTX_SHWANTED);
 584                         ++td->td_critcount;
 585                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 586                                 mtx_chain_link(mtx);
 587                                 --td->td_critcount;
 588                                 break;
 589                         }
 590                         --td->td_critcount;
 591                 } else if (nlock == (MTX_EXCLUSIVE | MTX_EXWANTED | 1)) {
 592                         /*
 593                          * Last release, exclusive lock, with exclusive
 594                          * waiters.
 595                          *
 596                          * leave the exclusive lock intact and the lockcount
 597                          * set to 1, and get EXLINK for access to mtx_link.
 598                          */
 599                         thread_t td;
 600
 601                         if (lock & MTX_EXLINK) {
 602                                 cpu_pause();
 603                                 ++mtx_collision_count;
 604                                 continue;
 605                         }
 606                         td = curthread;
 607                         /*lock &= ~MTX_EXLINK;*/
 608                         nlock |= MTX_EXLINK;
 609                         nlock |= (lock & MTX_SHWANTED);
 610                         ++td->td_critcount;
 611                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 612                                 mtx_chain_link(mtx);
 613                                 --td->td_critcount;
 614                                 break;
 615                         }
 616                         --td->td_critcount;
 617                 } else {
 618                         /*
 619                          * Not the last release (shared or exclusive)
 620                          */
 621                         nlock = lock - 1;
 622                         KKASSERT((nlock & MTX_MASK) != MTX_MASK);
 623                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 624                                 break;
 625                 }
 626                 cpu_pause();
 627                 ++mtx_collision_count;
 628         }
 629 }
 630
 631 /*
 632  * Chain mtx_chain_link.  Called with the lock held exclusively with a
 633  * single ref count, and also with MTX_EXLINK held.
 634  */
 635 static void
 636 mtx_chain_link(mtx_t mtx)
 637 {
 638         mtx_link_t link;
 639         u_int   lock;
 640         u_int   nlock;
 641         u_int   clock;  /* bits we own and want to clear */
 642
 643         /*
 644          * Chain the exclusive lock to the next link.  The caller cleared
 645          * SHWANTED so if there is no link we have to wake up any shared
 646          * waiters.
 647          */
 648         clock = MTX_EXLINK;
 649         if ((link = mtx->mtx_link) != NULL) {
 650                 KKASSERT(link->state == MTX_LINK_LINKED);
 651                 if (link->next == link) {
 652                         mtx->mtx_link = NULL;
 653                         clock |= MTX_EXWANTED;
 654                 } else {
 655                         mtx->mtx_link = link->next;
 656                         link->next->prev = link->prev;
 657                         link->prev->next = link->next;
 658                 }
 659                 link->state = MTX_LINK_ACQUIRED;
 660                 mtx->mtx_owner = link->owner;
 661         } else {
 662                 /*
 663                  * Chain was empty, release the exclusive lock's last count
 664                  * as well the bits shown.
 665                  */
 666                 clock |= MTX_EXCLUSIVE | MTX_EXWANTED | MTX_SHWANTED | 1;
 667         }
 668
 669         /*
 670          * We have to uset cmpset here to deal with MTX_SHWANTED.  If
 671          * we just clear the bits we can miss a wakeup or, worse,
 672          * leave mtx_lock unlocked with MTX_SHWANTED still set.
 673          */
 674         for (;;) {
 675                 lock = mtx->mtx_lock;
 676                 nlock = lock & ~clock;
 677
 678                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 679                         if (link) {
 680                                 /*
 681                                  * Wakeup new exclusive holder.  Leave
 682                                  * SHWANTED intact.
 683                                  */
 684                                 wakeup(link);
 685                         } else if (lock & MTX_SHWANTED) {
 686                                 /*
 687                                  * Signal any shared waiters (and we also
 688                                  * clear SHWANTED).
 689                                  */
 690                                 mtx->mtx_owner = NULL;
 691                                 wakeup(mtx);
 692                                 ++mtx_wakeup_count;
 693                         }
 694                         break;
 695                 }
 696                 cpu_pause();
 697                 ++mtx_collision_count;
 698         }
 699 }
 700
 701 /*
 702  * Delete a link structure after tsleep has failed.  This code is not
 703  * in the critical path as most exclusive waits are chained.
 704  */
 705 static
 706 void
 707 mtx_delete_link(mtx_t mtx, mtx_link_t link)
 708 {
 709         thread_t td = curthread;
 710         u_int   lock;
 711         u_int   nlock;
 712
 713         /*
 714          * Acquire MTX_EXLINK.
 715          *
 716          * Do not use cmpxchg to wait for EXLINK to clear as this might
 717          * result in too much cpu cache traffic.
 718          */
 719         ++td->td_critcount;
 720         for (;;) {
 721                 lock = mtx->mtx_lock;
 722                 if (lock & MTX_EXLINK) {
 723                         cpu_pause();
 724                         ++mtx_collision_count;
 725                         continue;
 726                 }
 727                 /* lock &= ~MTX_EXLINK; */
 728                 nlock = lock | MTX_EXLINK;
 729                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 730                         break;
 731                 cpu_pause();
 732                 ++mtx_collision_count;
 733         }
 734
 735         /*
 736          * Delete the link and release EXLINK.
 737          */
 738         if (link->state == MTX_LINK_LINKED) {
 739                 if (link->next == link) {
 740                         mtx->mtx_link = NULL;
 741                 } else {
 742                         mtx->mtx_link = link->next;
 743                         link->next->prev = link->prev;
 744                         link->prev->next = link->next;
 745                 }
 746                 link->state = MTX_LINK_IDLE;
 747         }
 748         atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
 749         --td->td_critcount;
 750 }
 751
 752 /*
 753  * Abort a mutex locking operation, causing mtx_lock_ex_link() to
 754  * return ENOLCK.  This may be called at any time after the
 755  * mtx_link is initialized, including both before and after the call
 756  * to mtx_lock_ex_link().
 757  */
 758 void
 759 mtx_abort_ex_link(mtx_t mtx, mtx_link_t link)
 760 {
 761         thread_t td = curthread;
 762         u_int   lock;
 763         u_int   nlock;
 764
 765         /*
 766          * Acquire MTX_EXLINK
 767          */
 768         ++td->td_critcount;
 769         for (;;) {
 770                 lock = mtx->mtx_lock;
 771                 if (lock & MTX_EXLINK) {
 772                         cpu_pause();
 773                         ++mtx_collision_count;
 774                         continue;
 775                 }
 776                 /* lock &= ~MTX_EXLINK; */
 777                 nlock = lock | MTX_EXLINK;
 778                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 779                         break;
 780                 cpu_pause();
 781                 ++mtx_collision_count;
 782         }
 783
 784         /*
 785          * Do the abort
 786          */
 787         switch(link->state) {
 788         case MTX_LINK_IDLE:
 789                 /*
 790                  * Link not started yet
 791                  */
 792                 link->state = MTX_LINK_ABORTED;
 793                 break;
 794         case MTX_LINK_LINKED:
 795                 /*
 796                  * de-link, mark aborted, and wakeup the thread.
 797                  */
 798                 if (link->next == link) {
 799                         mtx->mtx_link = NULL;
 800                 } else {
 801                         mtx->mtx_link = link->next;
 802                         link->next->prev = link->prev;
 803                         link->prev->next = link->next;
 804                 }
 805                 link->state = MTX_LINK_ABORTED;
 806                 wakeup(link);
 807                 break;
 808         case MTX_LINK_ACQUIRED:
 809                 /*
 810                  * Too late, the lock was acquired.  Let it complete.
 811                  */
 812                 break;
 813         default:
 814                 /*
 815                  * link already aborted, do nothing.
 816                  */
 817                 break;
 818         }
 819         atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
 820         --td->td_critcount;
 821 }