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, ident, to);
 162                                 ++mtx_contention_count;
 163
 164                                 /*
 165                                  * Normal unlink, we should own the exclusive
 166                                  * lock now.
 167                                  */
 168                                 if (link->state == MTX_LINK_LINKED)
 169                                         mtx_delete_link(mtx, link);
 170                                 if (link->state == MTX_LINK_ACQUIRED) {
 171                                         KKASSERT(mtx->mtx_owner == link->owner);
 172                                         error = 0;
 173                                         break;
 174                                 }
 175
 176                                 /*
 177                                  * Aborted lock (mtx_abort_ex called).
 178                                  */
 179                                 if (link->state == MTX_LINK_ABORTED) {
 180                                         error = ENOLCK;
 181                                         break;
 182                                 }
 183
 184                                 /*
 185                                  * tsleep error, else retry.
 186                                  */
 187                                 if (error)
 188                                         break;
 189                         } else {
 190                                 --td->td_critcount;
 191                         }
 192                 }
 193                 ++mtx_collision_count;
 194         }
 195         return (error);
 196 }
 197
 198 int
 199 _mtx_lock_ex_link(mtx_t mtx, mtx_link_t link,
 200                   const char *ident, int flags, int to)
 201 {
 202         return(__mtx_lock_ex(mtx, link, ident, flags, to));
 203 }
 204
 205 int
 206 _mtx_lock_ex(mtx_t mtx, const char *ident, int flags, int to)
 207 {
 208         struct mtx_link link;
 209
 210         mtx_link_init(&link);
 211         return(__mtx_lock_ex(mtx, &link, ident, flags, to));
 212 }
 213
 214 int
 215 _mtx_lock_ex_quick(mtx_t mtx, const char *ident)
 216 {
 217         struct mtx_link link;
 218
 219         mtx_link_init(&link);
 220         return(__mtx_lock_ex(mtx, &link, ident, 0, 0));
 221 }
 222
 223 /*
 224  * Share-lock a mutex, block until acquired.  Recursion is allowed.
 225  *
 226  * Returns 0 on success, or the tsleep() return code on failure.
 227  * An error can only be returned if PCATCH is specified in the flags.
 228  *
 229  * NOTE: Shared locks get a mass-wakeup so if the tsleep fails we
 230  *       do not have to chain the wakeup().
 231  */
 232 static __inline int
 233 __mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
 234 {
 235         u_int   lock;
 236         u_int   nlock;
 237         int     error;
 238
 239         for (;;) {
 240                 lock = mtx->mtx_lock;
 241                 if ((lock & MTX_EXCLUSIVE) == 0) {
 242                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 243                         nlock = lock + 1;
 244                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 245                                 error = 0;
 246                                 break;
 247                         }
 248                 } else {
 249                         nlock = lock | MTX_SHWANTED;
 250                         tsleep_interlock(mtx, 0);
 251                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 252                                 error = tsleep(mtx, flags, ident, to);
 253                                 if (error)
 254                                         break;
 255                                 ++mtx_contention_count;
 256                                 /* retry */
 257                         } else {
 258                                 crit_enter();
 259                                 tsleep_remove(curthread);
 260                                 crit_exit();
 261                         }
 262                 }
 263                 ++mtx_collision_count;
 264         }
 265         return (error);
 266 }
 267
 268 int
 269 _mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
 270 {
 271         return (__mtx_lock_sh(mtx, ident, flags, to));
 272 }
 273
 274 int
 275 _mtx_lock_sh_quick(mtx_t mtx, const char *ident)
 276 {
 277         return (__mtx_lock_sh(mtx, ident, 0, 0));
 278 }
 279
 280 /*
 281  * Get an exclusive spinlock the hard way.
 282  */
 283 void
 284 _mtx_spinlock(mtx_t mtx)
 285 {
 286         u_int   lock;
 287         u_int   nlock;
 288         int     bb = 1;
 289         int     bo;
 290
 291         for (;;) {
 292                 lock = mtx->mtx_lock;
 293                 if (lock == 0) {
 294                         nlock = MTX_EXCLUSIVE | 1;
 295                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 296                                 mtx->mtx_owner = curthread;
 297                                 break;
 298                         }
 299                 } else if ((lock & MTX_EXCLUSIVE) &&
 300                            mtx->mtx_owner == curthread) {
 301                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 302                         nlock = lock + 1;
 303                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 304                                 break;
 305                 } else {
 306                         /* MWAIT here */
 307                         if (bb < 1000)
 308                                 ++bb;
 309                         cpu_pause();
 310                         for (bo = 0; bo < bb; ++bo)
 311                                 ;
 312                         ++mtx_contention_count;
 313                 }
 314                 cpu_pause();
 315                 ++mtx_collision_count;
 316         }
 317 }
 318
 319 /*
 320  * Attempt to acquire a spinlock, if we fail we must undo the
 321  * gd->gd_spinlocks_wr/gd->gd_curthead->td_critcount predisposition.
 322  *
 323  * Returns 0 on success, EAGAIN on failure.
 324  */
 325 int
 326 _mtx_spinlock_try(mtx_t mtx)
 327 {
 328         globaldata_t gd = mycpu;
 329         u_int   lock;
 330         u_int   nlock;
 331         int     res = 0;
 332
 333         for (;;) {
 334                 lock = mtx->mtx_lock;
 335                 if (lock == 0) {
 336                         nlock = MTX_EXCLUSIVE | 1;
 337                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 338                                 mtx->mtx_owner = gd->gd_curthread;
 339                                 break;
 340                         }
 341                 } else if ((lock & MTX_EXCLUSIVE) &&
 342                            mtx->mtx_owner == gd->gd_curthread) {
 343                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 344                         nlock = lock + 1;
 345                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 346                                 break;
 347                 } else {
 348                         --gd->gd_spinlocks_wr;
 349                         cpu_ccfence();
 350                         --gd->gd_curthread->td_critcount;
 351                         res = EAGAIN;
 352                         break;
 353                 }
 354                 cpu_pause();
 355                 ++mtx_collision_count;
 356         }
 357         return res;
 358 }
 359
 360 #if 0
 361
 362 void
 363 _mtx_spinlock_sh(mtx_t mtx)
 364 {
 365         u_int   lock;
 366         u_int   nlock;
 367         int     bb = 1;
 368         int     bo;
 369
 370         for (;;) {
 371                 lock = mtx->mtx_lock;
 372                 if ((lock & MTX_EXCLUSIVE) == 0) {
 373                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 374                         nlock = lock + 1;
 375                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 376                                 break;
 377                 } else {
 378                         /* MWAIT here */
 379                         if (bb < 1000)
 380                                 ++bb;
 381                         cpu_pause();
 382                         for (bo = 0; bo < bb; ++bo)
 383                                 ;
 384                         ++mtx_contention_count;
 385                 }
 386                 cpu_pause();
 387                 ++mtx_collision_count;
 388         }
 389 }
 390
 391 #endif
 392
 393 int
 394 _mtx_lock_ex_try(mtx_t mtx)
 395 {
 396         u_int   lock;
 397         u_int   nlock;
 398         int     error = 0;
 399
 400         for (;;) {
 401                 lock = mtx->mtx_lock;
 402                 if (lock == 0) {
 403                         nlock = MTX_EXCLUSIVE | 1;
 404                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 405                                 mtx->mtx_owner = curthread;
 406                                 break;
 407                         }
 408                 } else if ((lock & MTX_EXCLUSIVE) &&
 409                            mtx->mtx_owner == curthread) {
 410                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 411                         nlock = lock + 1;
 412                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 413                                 break;
 414                 } else {
 415                         error = EAGAIN;
 416                         break;
 417                 }
 418                 cpu_pause();
 419                 ++mtx_collision_count;
 420         }
 421         return (error);
 422 }
 423
 424 int
 425 _mtx_lock_sh_try(mtx_t mtx)
 426 {
 427         u_int   lock;
 428         u_int   nlock;
 429         int     error = 0;
 430
 431         for (;;) {
 432                 lock = mtx->mtx_lock;
 433                 if ((lock & MTX_EXCLUSIVE) == 0) {
 434                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 435                         nlock = lock + 1;
 436                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 437                                 break;
 438                 } else {
 439                         error = EAGAIN;
 440                         break;
 441                 }
 442                 cpu_pause();
 443                 ++mtx_collision_count;
 444         }
 445         return (error);
 446 }
 447
 448 /*
 449  * If the lock is held exclusively it must be owned by the caller.  If the
 450  * lock is already a shared lock this operation is a NOP.  A panic will
 451  * occur if the lock is not held either shared or exclusive.
 452  *
 453  * The exclusive count is converted to a shared count.
 454  */
 455 void
 456 _mtx_downgrade(mtx_t mtx)
 457 {
 458         u_int   lock;
 459         u_int   nlock;
 460
 461         for (;;) {
 462                 lock = mtx->mtx_lock;
 463                 if ((lock & MTX_EXCLUSIVE) == 0) {
 464                         KKASSERT((lock & MTX_MASK) > 0);
 465                         break;
 466                 }
 467                 KKASSERT(mtx->mtx_owner == curthread);
 468                 nlock = lock & ~(MTX_EXCLUSIVE | MTX_SHWANTED);
 469                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 470                         if (lock & MTX_SHWANTED) {
 471                                 wakeup(mtx);
 472                                 ++mtx_wakeup_count;
 473                         }
 474                         break;
 475                 }
 476                 cpu_pause();
 477                 ++mtx_collision_count;
 478         }
 479 }
 480
 481 /*
 482  * Upgrade a shared lock to an exclusive lock.  The upgrade will fail if
 483  * the shared lock has a count other then 1.  Optimize the most likely case
 484  * but note that a single cmpset can fail due to WANTED races.
 485  *
 486  * If the lock is held exclusively it must be owned by the caller and
 487  * this function will simply return without doing anything.   A panic will
 488  * occur if the lock is held exclusively by someone other then the caller.
 489  *
 490  * Returns 0 on success, EDEADLK on failure.
 491  */
 492 int
 493 _mtx_upgrade_try(mtx_t mtx)
 494 {
 495         u_int   lock;
 496         u_int   nlock;
 497         int     error = 0;
 498
 499         for (;;) {
 500                 lock = mtx->mtx_lock;
 501
 502                 if ((lock & ~MTX_EXWANTED) == 1) {
 503                         nlock = lock | MTX_EXCLUSIVE;
 504                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 505                                 mtx->mtx_owner = curthread;
 506                                 break;
 507                         }
 508                 } else if (lock & MTX_EXCLUSIVE) {
 509                         KKASSERT(mtx->mtx_owner == curthread);
 510                         break;
 511                 } else {
 512                         error = EDEADLK;
 513                         break;
 514                 }
 515                 cpu_pause();
 516                 ++mtx_collision_count;
 517         }
 518         return (error);
 519 }
 520
 521 /*
 522  * Unlock a lock.  The caller must hold the lock either shared or exclusive.
 523  *
 524  * Any release which makes the lock available when others want an exclusive
 525  * lock causes us to chain the owner to the next exclusive lock instead of
 526  * releasing the lock.
 527  */
 528 void
 529 _mtx_unlock(mtx_t mtx)
 530 {
 531         u_int   lock;
 532         u_int   nlock;
 533
 534         for (;;) {
 535                 lock = mtx->mtx_lock;
 536                 nlock = lock & ~(MTX_SHWANTED | MTX_EXLINK);
 537
 538                 if (nlock == 1) {
 539                         /*
 540                          * Last release, shared lock, no exclusive waiters.
 541                          */
 542                         nlock = lock & MTX_EXLINK;
 543                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 544                                 break;
 545                 } else if (nlock == (MTX_EXCLUSIVE | 1)) {
 546                         /*
 547                          * Last release, exclusive lock, no exclusive waiters.
 548                          * Wake up any shared waiters.
 549                          */
 550                         mtx->mtx_owner = NULL;
 551                         nlock = lock & MTX_EXLINK;
 552                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 553                                 if (lock & MTX_SHWANTED) {
 554                                         wakeup(mtx);
 555                                         ++mtx_wakeup_count;
 556                                 }
 557                                 break;
 558                         }
 559                 } else if (nlock == (MTX_EXWANTED | 1)) {
 560                         /*
 561                          * Last release, shared lock, with exclusive
 562                          * waiters.
 563                          *
 564                          * Wait for EXLINK to clear, then acquire it.
 565                          * We could use the cmpset for this but polling
 566                          * is better on the cpu caches.
 567                          *
 568                          * Acquire an exclusive lock leaving the lockcount
 569                          * set to 1, and get EXLINK for access to mtx_link.
 570                          */
 571                         thread_t td;
 572
 573                         if (lock & MTX_EXLINK) {
 574                                 cpu_pause();
 575                                 ++mtx_collision_count;
 576                                 continue;
 577                         }
 578                         td = curthread;
 579                         /*lock &= ~MTX_EXLINK;*/
 580                         nlock |= MTX_EXLINK | MTX_EXCLUSIVE;
 581                         nlock |= (lock & MTX_SHWANTED);
 582                         ++td->td_critcount;
 583                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 584                                 mtx_chain_link(mtx);
 585                                 --td->td_critcount;
 586                                 break;
 587                         }
 588                         --td->td_critcount;
 589                 } else if (nlock == (MTX_EXCLUSIVE | MTX_EXWANTED | 1)) {
 590                         /*
 591                          * Last release, exclusive lock, with exclusive
 592                          * waiters.
 593                          *
 594                          * leave the exclusive lock intact and the lockcount
 595                          * set to 1, and get EXLINK for access to mtx_link.
 596                          */
 597                         thread_t td;
 598
 599                         if (lock & MTX_EXLINK) {
 600                                 cpu_pause();
 601                                 ++mtx_collision_count;
 602                                 continue;
 603                         }
 604                         td = curthread;
 605                         /*lock &= ~MTX_EXLINK;*/
 606                         nlock |= MTX_EXLINK;
 607                         nlock |= (lock & MTX_SHWANTED);
 608                         ++td->td_critcount;
 609                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 610                                 mtx_chain_link(mtx);
 611                                 --td->td_critcount;
 612                                 break;
 613                         }
 614                         --td->td_critcount;
 615                 } else {
 616                         /*
 617                          * Not the last release (shared or exclusive)
 618                          */
 619                         nlock = lock - 1;
 620                         KKASSERT((nlock & MTX_MASK) != MTX_MASK);
 621                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 622                                 break;
 623                 }
 624                 cpu_pause();
 625                 ++mtx_collision_count;
 626         }
 627 }
 628
 629 /*
 630  * Chain mtx_chain_link.  Called with the lock held exclusively with a
 631  * single ref count, and also with MTX_EXLINK held.
 632  */
 633 static void
 634 mtx_chain_link(mtx_t mtx)
 635 {
 636         mtx_link_t link;
 637         u_int   lock;
 638         u_int   nlock;
 639         u_int   clock;  /* bits we own and want to clear */
 640
 641         /*
 642          * Chain the exclusive lock to the next link.  The caller cleared
 643          * SHWANTED so if there is no link we have to wake up any shared
 644          * waiters.
 645          */
 646         clock = MTX_EXLINK;
 647         if ((link = mtx->mtx_link) != NULL) {
 648                 KKASSERT(link->state == MTX_LINK_LINKED);
 649                 if (link->next == link) {
 650                         mtx->mtx_link = NULL;
 651                         clock |= MTX_EXWANTED;
 652                 } else {
 653                         mtx->mtx_link = link->next;
 654                         link->next->prev = link->prev;
 655                         link->prev->next = link->next;
 656                 }
 657                 link->state = MTX_LINK_ACQUIRED;
 658                 mtx->mtx_owner = link->owner;
 659         } else {
 660                 /*
 661                  * Chain was empty, release the exclusive lock's last count
 662                  * as well the bits shown.
 663                  */
 664                 clock |= MTX_EXCLUSIVE | MTX_EXWANTED | MTX_SHWANTED | 1;
 665         }
 666
 667         /*
 668          * We have to uset cmpset here to deal with MTX_SHWANTED.  If
 669          * we just clear the bits we can miss a wakeup or, worse,
 670          * leave mtx_lock unlocked with MTX_SHWANTED still set.
 671          */
 672         for (;;) {
 673                 lock = mtx->mtx_lock;
 674                 nlock = lock & ~clock;
 675
 676                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 677                         if (link) {
 678                                 /*
 679                                  * Wakeup new exclusive holder.  Leave
 680                                  * SHWANTED intact.
 681                                  */
 682                                 wakeup(link);
 683                         } else if (lock & MTX_SHWANTED) {
 684                                 /*
 685                                  * Signal any shared waiters (and we also
 686                                  * clear SHWANTED).
 687                                  */
 688                                 mtx->mtx_owner = NULL;
 689                                 wakeup(mtx);
 690                                 ++mtx_wakeup_count;
 691                         }
 692                         break;
 693                 }
 694                 cpu_pause();
 695                 ++mtx_collision_count;
 696         }
 697 }
 698
 699 /*
 700  * Delete a link structure after tsleep has failed.  This code is not
 701  * in the critical path as most exclusive waits are chained.
 702  */
 703 static
 704 void
 705 mtx_delete_link(mtx_t mtx, mtx_link_t link)
 706 {
 707         thread_t td = curthread;
 708         u_int   lock;
 709         u_int   nlock;
 710
 711         /*
 712          * Acquire MTX_EXLINK.
 713          *
 714          * Do not use cmpxchg to wait for EXLINK to clear as this might
 715          * result in too much cpu cache traffic.
 716          */
 717         ++td->td_critcount;
 718         for (;;) {
 719                 lock = mtx->mtx_lock;
 720                 if (lock & MTX_EXLINK) {
 721                         cpu_pause();
 722                         ++mtx_collision_count;
 723                         continue;
 724                 }
 725                 /* lock &= ~MTX_EXLINK; */
 726                 nlock = lock | MTX_EXLINK;
 727                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 728                         break;
 729                 cpu_pause();
 730                 ++mtx_collision_count;
 731         }
 732
 733         /*
 734          * Delete the link and release EXLINK.
 735          */
 736         if (link->state == MTX_LINK_LINKED) {
 737                 if (link->next == link) {
 738                         mtx->mtx_link = NULL;
 739                 } else {
 740                         mtx->mtx_link = link->next;
 741                         link->next->prev = link->prev;
 742                         link->prev->next = link->next;
 743                 }
 744                 link->state = MTX_LINK_IDLE;
 745         }
 746         atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
 747         --td->td_critcount;
 748 }
 749
 750 /*
 751  * Abort a mutex locking operation, causing mtx_lock_ex_link() to
 752  * return ENOLCK.  This may be called at any time after the
 753  * mtx_link is initialized, including both before and after the call
 754  * to mtx_lock_ex_link().
 755  */
 756 void
 757 mtx_abort_ex_link(mtx_t mtx, mtx_link_t link)
 758 {
 759         thread_t td = curthread;
 760         u_int   lock;
 761         u_int   nlock;
 762
 763         /*
 764          * Acquire MTX_EXLINK
 765          */
 766         ++td->td_critcount;
 767         for (;;) {
 768                 lock = mtx->mtx_lock;
 769                 if (lock & MTX_EXLINK) {
 770                         cpu_pause();
 771                         ++mtx_collision_count;
 772                         continue;
 773                 }
 774                 /* lock &= ~MTX_EXLINK; */
 775                 nlock = lock | MTX_EXLINK;
 776                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 777                         break;
 778                 cpu_pause();
 779                 ++mtx_collision_count;
 780         }
 781
 782         /*
 783          * Do the abort
 784          */
 785         switch(link->state) {
 786         case MTX_LINK_IDLE:
 787                 /*
 788                  * Link not started yet
 789                  */
 790                 link->state = MTX_LINK_ABORTED;
 791                 break;
 792         case MTX_LINK_LINKED:
 793                 /*
 794                  * de-link, mark aborted, and wakeup the thread.
 795                  */
 796                 if (link->next == link) {
 797                         mtx->mtx_link = NULL;
 798                 } else {
 799                         mtx->mtx_link = link->next;
 800                         link->next->prev = link->prev;
 801                         link->prev->next = link->next;
 802                 }
 803                 link->state = MTX_LINK_ABORTED;
 804                 wakeup(link);
 805                 break;
 806         case MTX_LINK_ACQUIRED:
 807                 /*
 808                  * Too late, the lock was acquired.  Let it complete.
 809                  */
 810                 break;
 811         default:
 812                 /*
 813                  * link already aborted, do nothing.
 814                  */
 815                 break;
 816         }
 817         atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
 818         --td->td_critcount;
 819 }