sys/kern/kern_sx.c

   1 /*-
   2  * Copyright (c) 2007 Attilio Rao <attilio@freebsd.org>
   3  * Copyright (c) 2001 Jason Evans <jasone@freebsd.org>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice(s), this list of conditions and the following disclaimer as
  11  *    the first lines of this file unmodified other than the possible
  12  *    addition of one or more copyright notices.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice(s), this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
  18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  20  * DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE LIABLE FOR ANY
  21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  24  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
  27  * DAMAGE.
  28  */
  29
  30 /*
  31  * Shared/exclusive locks.  This implementation attempts to ensure
  32  * deterministic lock granting behavior, so that slocks and xlocks are
  33  * interleaved.
  34  *
  35  * Priority propagation will not generally raise the priority of lock holders,
  36  * so should not be relied upon in combination with sx locks.
  37  */
  38
  39 #include "opt_adaptive_sx.h"
  40 #include "opt_ddb.h"
  41
  42 #include <sys/cdefs.h>
  43 __FBSDID("$FreeBSD$");
  44
  45 #include <sys/param.h>
  46 #include <sys/ktr.h>
  47 #include <sys/lock.h>
  48 #include <sys/lock_profile.h>
  49 #include <sys/mutex.h>
  50 #include <sys/proc.h>
  51 #include <sys/sleepqueue.h>
  52 #include <sys/sx.h>
  53 #include <sys/systm.h>
  54
  55 #ifdef ADAPTIVE_SX
  56 #include <machine/cpu.h>
  57 #endif
  58
  59 #ifdef DDB
  60 #include <ddb/ddb.h>
  61 #endif
  62
  63 #if !defined(SMP) && defined(ADAPTIVE_SX)
  64 #error "You must have SMP to enable the ADAPTIVE_SX option"
  65 #endif
  66
  67 /* Handy macros for sleep queues. */
  68 #define SQ_EXCLUSIVE_QUEUE      0
  69 #define SQ_SHARED_QUEUE         1
  70
  71 /*
  72  * Variations on DROP_GIANT()/PICKUP_GIANT() for use in this file.  We
  73  * drop Giant anytime we have to sleep or if we adaptively spin.
  74  */
  75 #define GIANT_DECLARE                                                   \
  76         int _giantcnt = 0;                                              \
  77         WITNESS_SAVE_DECL(Giant)                                        \
  78
  79 #define GIANT_SAVE() do {                                               \
  80         if (mtx_owned(&Giant)) {                                        \
  81                 WITNESS_SAVE(&Giant.lock_object, Giant);                \
  82                 while (mtx_owned(&Giant)) {                             \
  83                         _giantcnt++;                                    \
  84                         mtx_unlock(&Giant);                             \
  85                 }                                                       \
  86         }                                                               \
  87 } while (0)
  88
  89 #define GIANT_RESTORE() do {                                            \
  90         if (_giantcnt > 0) {                                            \
  91                 mtx_assert(&Giant, MA_NOTOWNED);                        \
  92                 while (_giantcnt--)                                     \
  93                         mtx_lock(&Giant);                               \
  94                 WITNESS_RESTORE(&Giant.lock_object, Giant);             \
  95         }                                                               \
  96 } while (0)
  97
  98 /*
  99  * Returns true if an exclusive lock is recursed.  It assumes
 100  * curthread currently has an exclusive lock.
 101  */
 102 #define sx_recursed(sx)         ((sx)->sx_recurse != 0)
 103
 104 /*
 105  * Return a pointer to the owning thread if the lock is exclusively
 106  * locked.
 107  */
 108 #define sx_xholder(sx)                                                  \
 109         ((sx)->sx_lock & SX_LOCK_SHARED ? NULL :                        \
 110         (struct thread *)SX_OWNER((sx)->sx_lock))
 111
 112 #ifdef DDB
 113 static void     db_show_sx(struct lock_object *lock);
 114 #endif
 115 static void     lock_sx(struct lock_object *lock, int how);
 116 static int      unlock_sx(struct lock_object *lock);
 117
 118 struct lock_class lock_class_sx = {
 119         .lc_name = "sx",
 120         .lc_flags = LC_SLEEPLOCK | LC_SLEEPABLE | LC_RECURSABLE | LC_UPGRADABLE,
 121 #ifdef DDB
 122         .lc_ddb_show = db_show_sx,
 123 #endif
 124         .lc_lock = lock_sx,
 125         .lc_unlock = unlock_sx,
 126 };
 127
 128 #ifndef INVARIANTS
 129 #define _sx_assert(sx, what, file, line)
 130 #endif
 131
 132 void
 133 lock_sx(struct lock_object *lock, int how)
 134 {
 135         struct sx *sx;
 136
 137         sx = (struct sx *)lock;
 138         if (how)
 139                 sx_xlock(sx);
 140         else
 141                 sx_slock(sx);
 142 }
 143
 144 int
 145 unlock_sx(struct lock_object *lock)
 146 {
 147         struct sx *sx;
 148
 149         sx = (struct sx *)lock;
 150         sx_assert(sx, SX_LOCKED | SX_NOTRECURSED);
 151         if (sx_xlocked(sx)) {
 152                 sx_xunlock(sx);
 153                 return (1);
 154         } else {
 155                 sx_sunlock(sx);
 156                 return (0);
 157         }
 158 }
 159
 160 void
 161 sx_sysinit(void *arg)
 162 {
 163         struct sx_args *sargs = arg;
 164
 165         sx_init(sargs->sa_sx, sargs->sa_desc);
 166 }
 167
 168 void
 169 sx_init_flags(struct sx *sx, const char *description, int opts)
 170 {
 171         int flags;
 172
 173         MPASS((opts & ~(SX_QUIET | SX_RECURSE | SX_NOWITNESS | SX_DUPOK |
 174             SX_NOPROFILE | SX_ADAPTIVESPIN)) == 0);
 175
 176         flags = LO_SLEEPABLE | LO_UPGRADABLE | LO_RECURSABLE;
 177         if (opts & SX_DUPOK)
 178                 flags |= LO_DUPOK;
 179         if (opts & SX_NOPROFILE)
 180                 flags |= LO_NOPROFILE;
 181         if (!(opts & SX_NOWITNESS))
 182                 flags |= LO_WITNESS;
 183         if (opts & SX_QUIET)
 184                 flags |= LO_QUIET;
 185
 186         flags |= opts & (SX_ADAPTIVESPIN | SX_RECURSE);
 187         sx->sx_lock = SX_LOCK_UNLOCKED;
 188         sx->sx_recurse = 0;
 189         lock_init(&sx->lock_object, &lock_class_sx, description, NULL, flags);
 190 }
 191
 192 void
 193 sx_destroy(struct sx *sx)
 194 {
 195
 196         KASSERT(sx->sx_lock == SX_LOCK_UNLOCKED, ("sx lock still held"));
 197         KASSERT(sx->sx_recurse == 0, ("sx lock still recursed"));
 198         sx->sx_lock = SX_LOCK_DESTROYED;
 199         lock_destroy(&sx->lock_object);
 200 }
 201
 202 void
 203 _sx_slock(struct sx *sx, const char *file, int line)
 204 {
 205
 206         MPASS(curthread != NULL);
 207         KASSERT(sx->sx_lock != SX_LOCK_DESTROYED,
 208             ("sx_slock() of destroyed sx @ %s:%d", file, line));
 209         WITNESS_CHECKORDER(&sx->lock_object, LOP_NEWORDER, file, line);
 210         __sx_slock(sx, file, line);
 211         LOCK_LOG_LOCK("SLOCK", &sx->lock_object, 0, 0, file, line);
 212         WITNESS_LOCK(&sx->lock_object, 0, file, line);
 213         curthread->td_locks++;
 214 }
 215
 216 int
 217 _sx_try_slock(struct sx *sx, const char *file, int line)
 218 {
 219         uintptr_t x;
 220
 221         x = sx->sx_lock;
 222         KASSERT(x != SX_LOCK_DESTROYED,
 223             ("sx_try_slock() of destroyed sx @ %s:%d", file, line));
 224         if ((x & SX_LOCK_SHARED) && atomic_cmpset_acq_ptr(&sx->sx_lock, x,
 225             x + SX_ONE_SHARER)) {
 226                 LOCK_LOG_TRY("SLOCK", &sx->lock_object, 0, 1, file, line);
 227                 WITNESS_LOCK(&sx->lock_object, LOP_TRYLOCK, file, line);
 228                 curthread->td_locks++;
 229                 return (1);
 230         }
 231
 232         LOCK_LOG_TRY("SLOCK", &sx->lock_object, 0, 0, file, line);
 233         return (0);
 234 }
 235
 236 void
 237 _sx_xlock(struct sx *sx, const char *file, int line)
 238 {
 239
 240         MPASS(curthread != NULL);
 241         KASSERT(sx->sx_lock != SX_LOCK_DESTROYED,
 242             ("sx_xlock() of destroyed sx @ %s:%d", file, line));
 243         WITNESS_CHECKORDER(&sx->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE, file,
 244             line);
 245         __sx_xlock(sx, curthread, file, line);
 246         LOCK_LOG_LOCK("XLOCK", &sx->lock_object, 0, sx->sx_recurse, file, line);
 247         WITNESS_LOCK(&sx->lock_object, LOP_EXCLUSIVE, file, line);
 248         curthread->td_locks++;
 249 }
 250
 251 int
 252 _sx_try_xlock(struct sx *sx, const char *file, int line)
 253 {
 254         int rval;
 255
 256         MPASS(curthread != NULL);
 257         KASSERT(sx->sx_lock != SX_LOCK_DESTROYED,
 258             ("sx_try_xlock() of destroyed sx @ %s:%d", file, line));
 259
 260         if (sx_xlocked(sx) && (sx->lock_object.lo_flags & SX_RECURSE) != 0) {
 261                 sx->sx_recurse++;
 262                 atomic_set_ptr(&sx->sx_lock, SX_LOCK_RECURSED);
 263                 rval = 1;
 264         } else
 265                 rval = atomic_cmpset_acq_ptr(&sx->sx_lock, SX_LOCK_UNLOCKED,
 266                     (uintptr_t)curthread);
 267         LOCK_LOG_TRY("XLOCK", &sx->lock_object, 0, rval, file, line);
 268         if (rval) {
 269                 WITNESS_LOCK(&sx->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK,
 270                     file, line);
 271                 curthread->td_locks++;
 272         }
 273
 274         return (rval);
 275 }
 276
 277 void
 278 _sx_sunlock(struct sx *sx, const char *file, int line)
 279 {
 280
 281         MPASS(curthread != NULL);
 282         KASSERT(sx->sx_lock != SX_LOCK_DESTROYED,
 283             ("sx_sunlock() of destroyed sx @ %s:%d", file, line));
 284         _sx_assert(sx, SX_SLOCKED, file, line);
 285         curthread->td_locks--;
 286         WITNESS_UNLOCK(&sx->lock_object, 0, file, line);
 287         LOCK_LOG_LOCK("SUNLOCK", &sx->lock_object, 0, 0, file, line);
 288         if (SX_SHARERS(sx->sx_lock) == 0)
 289                 lock_profile_release_lock(&sx->lock_object);
 290         __sx_sunlock(sx, file, line);
 291 }
 292
 293 void
 294 _sx_xunlock(struct sx *sx, const char *file, int line)
 295 {
 296
 297         MPASS(curthread != NULL);
 298         KASSERT(sx->sx_lock != SX_LOCK_DESTROYED,
 299             ("sx_xunlock() of destroyed sx @ %s:%d", file, line));
 300         _sx_assert(sx, SX_XLOCKED, file, line);
 301         curthread->td_locks--;
 302         WITNESS_UNLOCK(&sx->lock_object, LOP_EXCLUSIVE, file, line);
 303         LOCK_LOG_LOCK("XUNLOCK", &sx->lock_object, 0, sx->sx_recurse, file,
 304             line);
 305         if (!sx_recursed(sx))
 306                 lock_profile_release_lock(&sx->lock_object);
 307         __sx_xunlock(sx, curthread, file, line);
 308 }
 309
 310 /*
 311  * Try to do a non-blocking upgrade from a shared lock to an exclusive lock.
 312  * This will only succeed if this thread holds a single shared lock.
 313  * Return 1 if if the upgrade succeed, 0 otherwise.
 314  */
 315 int
 316 _sx_try_upgrade(struct sx *sx, const char *file, int line)
 317 {
 318         uintptr_t x;
 319         int success;
 320
 321         KASSERT(sx->sx_lock != SX_LOCK_DESTROYED,
 322             ("sx_try_upgrade() of destroyed sx @ %s:%d", file, line));
 323         _sx_assert(sx, SX_SLOCKED, file, line);
 324
 325         /*
 326          * Try to switch from one shared lock to an exclusive lock.  We need
 327          * to maintain the SX_LOCK_EXCLUSIVE_WAITERS flag if set so that
 328          * we will wake up the exclusive waiters when we drop the lock.
 329          */
 330         x = sx->sx_lock & SX_LOCK_EXCLUSIVE_WAITERS;
 331         success = atomic_cmpset_ptr(&sx->sx_lock, SX_SHARERS_LOCK(1) | x,
 332             (uintptr_t)curthread | x);
 333         LOCK_LOG_TRY("XUPGRADE", &sx->lock_object, 0, success, file, line);
 334         if (success)
 335                 WITNESS_UPGRADE(&sx->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK,
 336                     file, line);
 337         return (success);
 338 }
 339
 340 /*
 341  * Downgrade an unrecursed exclusive lock into a single shared lock.
 342  */
 343 void
 344 _sx_downgrade(struct sx *sx, const char *file, int line)
 345 {
 346         uintptr_t x;
 347
 348         KASSERT(sx->sx_lock != SX_LOCK_DESTROYED,
 349             ("sx_downgrade() of destroyed sx @ %s:%d", file, line));
 350         _sx_assert(sx, SX_XLOCKED | SX_NOTRECURSED, file, line);
 351 #ifndef INVARIANTS
 352         if (sx_recursed(sx))
 353                 panic("downgrade of a recursed lock");
 354 #endif
 355
 356         WITNESS_DOWNGRADE(&sx->lock_object, 0, file, line);
 357
 358         /*
 359          * Try to switch from an exclusive lock with no shared waiters
 360          * to one sharer with no shared waiters.  If there are
 361          * exclusive waiters, we don't need to lock the sleep queue so
 362          * long as we preserve the flag.  We do one quick try and if
 363          * that fails we grab the sleepq lock to keep the flags from
 364          * changing and do it the slow way.
 365          *
 366          * We have to lock the sleep queue if there are shared waiters
 367          * so we can wake them up.
 368          */
 369         x = sx->sx_lock;
 370         if (!(x & SX_LOCK_SHARED_WAITERS) &&
 371             atomic_cmpset_rel_ptr(&sx->sx_lock, x, SX_SHARERS_LOCK(1) |
 372             (x & SX_LOCK_EXCLUSIVE_WAITERS))) {
 373                 LOCK_LOG_LOCK("XDOWNGRADE", &sx->lock_object, 0, 0, file, line);
 374                 return;
 375         }
 376
 377         /*
 378          * Lock the sleep queue so we can read the waiters bits
 379          * without any races and wakeup any shared waiters.
 380          */
 381         sleepq_lock(&sx->lock_object);
 382
 383         /*
 384          * Preserve SX_LOCK_EXCLUSIVE_WAITERS while downgraded to a single
 385          * shared lock.  If there are any shared waiters, wake them up.
 386          */
 387         x = sx->sx_lock;
 388         atomic_store_rel_ptr(&sx->sx_lock, SX_SHARERS_LOCK(1) |
 389             (x & SX_LOCK_EXCLUSIVE_WAITERS));
 390         if (x & SX_LOCK_SHARED_WAITERS)
 391                 sleepq_broadcast(&sx->lock_object, SLEEPQ_SX, -1,
 392                     SQ_SHARED_QUEUE);
 393         else
 394                 sleepq_release(&sx->lock_object);
 395
 396         LOCK_LOG_LOCK("XDOWNGRADE", &sx->lock_object, 0, 0, file, line);
 397 }
 398
 399 /*
 400  * This function represents the so-called 'hard case' for sx_xlock
 401  * operation.  All 'easy case' failures are redirected to this.  Note
 402  * that ideally this would be a static function, but it needs to be
 403  * accessible from at least sx.h.
 404  */
 405 void
 406 _sx_xlock_hard(struct sx *sx, uintptr_t tid, const char *file, int line)
 407 {
 408         GIANT_DECLARE;
 409 #ifdef ADAPTIVE_SX
 410         volatile struct thread *owner;
 411 #endif
 412         uintptr_t x;
 413         int contested = 0;
 414         uint64_t waitstart = 0;
 415
 416         /* If we already hold an exclusive lock, then recurse. */
 417         if (sx_xlocked(sx)) {
 418                 KASSERT((sx->lock_object.lo_flags & SX_RECURSE) != 0,
 419             ("_sx_xlock_hard: recursed on non-recursive sx %s @ %s:%d\n",
 420                     sx->lock_object.lo_name, file, line));
 421                 sx->sx_recurse++;
 422                 atomic_set_ptr(&sx->sx_lock, SX_LOCK_RECURSED);
 423                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 424                         CTR2(KTR_LOCK, "%s: %p recursing", __func__, sx);
 425                 return;
 426         }
 427         lock_profile_obtain_lock_failed(&(sx)->lock_object,
 428             &contested, &waitstart);
 429
 430         if (LOCK_LOG_TEST(&sx->lock_object, 0))
 431                 CTR5(KTR_LOCK, "%s: %s contested (lock=%p) at %s:%d", __func__,
 432                     sx->lock_object.lo_name, (void *)sx->sx_lock, file, line);
 433
 434         while (!atomic_cmpset_acq_ptr(&sx->sx_lock, SX_LOCK_UNLOCKED, tid)) {
 435 #ifdef ADAPTIVE_SX
 436                 /*
 437                  * If the lock is write locked and the owner is
 438                  * running on another CPU, spin until the owner stops
 439                  * running or the state of the lock changes.
 440                  */
 441                 x = sx->sx_lock;
 442                 if (!(x & SX_LOCK_SHARED) &&
 443                     (sx->lock_object.lo_flags & SX_ADAPTIVESPIN)) {
 444                         x = SX_OWNER(x);
 445                         owner = (struct thread *)x;
 446                         if (TD_IS_RUNNING(owner)) {
 447                                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 448                                         CTR3(KTR_LOCK,
 449                                             "%s: spinning on %p held by %p",
 450                                             __func__, sx, owner);
 451                                 GIANT_SAVE();
 452                                 while (SX_OWNER(sx->sx_lock) == x &&
 453                                     TD_IS_RUNNING(owner))
 454                                         cpu_spinwait();
 455                                 continue;
 456                         }
 457                 }
 458 #endif
 459
 460                 sleepq_lock(&sx->lock_object);
 461                 x = sx->sx_lock;
 462
 463                 /*
 464                  * If the lock was released while spinning on the
 465                  * sleep queue chain lock, try again.
 466                  */
 467                 if (x == SX_LOCK_UNLOCKED) {
 468                         sleepq_release(&sx->lock_object);
 469                         continue;
 470                 }
 471
 472 #ifdef ADAPTIVE_SX
 473                 /*
 474                  * The current lock owner might have started executing
 475                  * on another CPU (or the lock could have changed
 476                  * owners) while we were waiting on the sleep queue
 477                  * chain lock.  If so, drop the sleep queue lock and try
 478                  * again.
 479                  */
 480                 if (!(x & SX_LOCK_SHARED) &&
 481                     (sx->lock_object.lo_flags & SX_ADAPTIVESPIN)) {
 482                         owner = (struct thread *)SX_OWNER(x);
 483                         if (TD_IS_RUNNING(owner)) {
 484                                 sleepq_release(&sx->lock_object);
 485                                 continue;
 486                         }
 487                 }
 488 #endif
 489
 490                 /*
 491                  * If an exclusive lock was released with both shared
 492                  * and exclusive waiters and a shared waiter hasn't
 493                  * woken up and acquired the lock yet, sx_lock will be
 494                  * set to SX_LOCK_UNLOCKED | SX_LOCK_EXCLUSIVE_WAITERS.
 495                  * If we see that value, try to acquire it once.  Note
 496                  * that we have to preserve SX_LOCK_EXCLUSIVE_WAITERS
 497                  * as there are other exclusive waiters still.  If we
 498                  * fail, restart the loop.
 499                  */
 500                 if (x == (SX_LOCK_UNLOCKED | SX_LOCK_EXCLUSIVE_WAITERS)) {
 501                         if (atomic_cmpset_acq_ptr(&sx->sx_lock,
 502                             SX_LOCK_UNLOCKED | SX_LOCK_EXCLUSIVE_WAITERS,
 503                             tid | SX_LOCK_EXCLUSIVE_WAITERS)) {
 504                                 sleepq_release(&sx->lock_object);
 505                                 CTR2(KTR_LOCK, "%s: %p claimed by new writer",
 506                                     __func__, sx);
 507                                 break;
 508                         }
 509                         sleepq_release(&sx->lock_object);
 510                         continue;
 511                 }
 512
 513                 /*
 514                  * Try to set the SX_LOCK_EXCLUSIVE_WAITERS.  If we fail,
 515                  * than loop back and retry.
 516                  */
 517                 if (!(x & SX_LOCK_EXCLUSIVE_WAITERS)) {
 518                         if (!atomic_cmpset_ptr(&sx->sx_lock, x,
 519                             x | SX_LOCK_EXCLUSIVE_WAITERS)) {
 520                                 sleepq_release(&sx->lock_object);
 521                                 continue;
 522                         }
 523                         if (LOCK_LOG_TEST(&sx->lock_object, 0))
 524                                 CTR2(KTR_LOCK, "%s: %p set excl waiters flag",
 525                                     __func__, sx);
 526                 }
 527
 528                 /*
 529                  * Since we have been unable to acquire the exclusive
 530                  * lock and the exclusive waiters flag is set, we have
 531                  * to sleep.
 532                  */
 533                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 534                         CTR2(KTR_LOCK, "%s: %p blocking on sleep queue",
 535                             __func__, sx);
 536
 537                 GIANT_SAVE();
 538                 sleepq_add(&sx->lock_object, NULL, sx->lock_object.lo_name,
 539                     SLEEPQ_SX, SQ_EXCLUSIVE_QUEUE);
 540                 sleepq_wait(&sx->lock_object);
 541
 542                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 543                         CTR2(KTR_LOCK, "%s: %p resuming from sleep queue",
 544                             __func__, sx);
 545         }
 546
 547         GIANT_RESTORE();
 548         lock_profile_obtain_lock_success(&(sx)->lock_object, contested,
 549             waitstart, file, line);
 550 }
 551
 552 /*
 553  * This function represents the so-called 'hard case' for sx_xunlock
 554  * operation.  All 'easy case' failures are redirected to this.  Note
 555  * that ideally this would be a static function, but it needs to be
 556  * accessible from at least sx.h.
 557  */
 558 void
 559 _sx_xunlock_hard(struct sx *sx, uintptr_t tid, const char *file, int line)
 560 {
 561         uintptr_t x;
 562         int queue;
 563
 564         MPASS(!(sx->sx_lock & SX_LOCK_SHARED));
 565
 566         /* If the lock is recursed, then unrecurse one level. */
 567         if (sx_xlocked(sx) && sx_recursed(sx)) {
 568                 if ((--sx->sx_recurse) == 0)
 569                         atomic_clear_ptr(&sx->sx_lock, SX_LOCK_RECURSED);
 570                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 571                         CTR2(KTR_LOCK, "%s: %p unrecursing", __func__, sx);
 572                 return;
 573         }
 574         MPASS(sx->sx_lock & (SX_LOCK_SHARED_WAITERS |
 575             SX_LOCK_EXCLUSIVE_WAITERS));
 576         if (LOCK_LOG_TEST(&sx->lock_object, 0))
 577                 CTR2(KTR_LOCK, "%s: %p contested", __func__, sx);
 578
 579         sleepq_lock(&sx->lock_object);
 580         x = SX_LOCK_UNLOCKED;
 581
 582         /*
 583          * The wake up algorithm here is quite simple and probably not
 584          * ideal.  It gives precedence to shared waiters if they are
 585          * present.  For this condition, we have to preserve the
 586          * state of the exclusive waiters flag.
 587          */
 588         if (sx->sx_lock & SX_LOCK_SHARED_WAITERS) {
 589                 queue = SQ_SHARED_QUEUE;
 590                 x |= (sx->sx_lock & SX_LOCK_EXCLUSIVE_WAITERS);
 591         } else
 592                 queue = SQ_EXCLUSIVE_QUEUE;
 593
 594         /* Wake up all the waiters for the specific queue. */
 595         if (LOCK_LOG_TEST(&sx->lock_object, 0))
 596                 CTR3(KTR_LOCK, "%s: %p waking up all threads on %s queue",
 597                     __func__, sx, queue == SQ_SHARED_QUEUE ? "shared" :
 598                     "exclusive");
 599         atomic_store_rel_ptr(&sx->sx_lock, x);
 600         sleepq_broadcast(&sx->lock_object, SLEEPQ_SX, -1, queue);
 601 }
 602
 603 /*
 604  * This function represents the so-called 'hard case' for sx_slock
 605  * operation.  All 'easy case' failures are redirected to this.  Note
 606  * that ideally this would be a static function, but it needs to be
 607  * accessible from at least sx.h.
 608  */
 609 void
 610 _sx_slock_hard(struct sx *sx, const char *file, int line)
 611 {
 612         GIANT_DECLARE;
 613 #ifdef ADAPTIVE_SX
 614         volatile struct thread *owner;
 615 #endif
 616         uintptr_t x;
 617         uint64_t waitstart = 0;
 618         int contested = 0;
 619         /*
 620          * As with rwlocks, we don't make any attempt to try to block
 621          * shared locks once there is an exclusive waiter.
 622          */
 623
 624         for (;;) {
 625                 x = sx->sx_lock;
 626
 627                 /*
 628                  * If no other thread has an exclusive lock then try to bump up
 629                  * the count of sharers.  Since we have to preserve the state
 630                  * of SX_LOCK_EXCLUSIVE_WAITERS, if we fail to acquire the
 631                  * shared lock loop back and retry.
 632                  */
 633                 if (x & SX_LOCK_SHARED) {
 634                         MPASS(!(x & SX_LOCK_SHARED_WAITERS));
 635                         if (atomic_cmpset_acq_ptr(&sx->sx_lock, x,
 636                             x + SX_ONE_SHARER)) {
 637                                 if (SX_SHARERS(x) == 0)
 638                                         lock_profile_obtain_lock_success(
 639                                             &sx->lock_object, contested,
 640                                             waitstart, file, line);
 641                                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 642                                         CTR4(KTR_LOCK,
 643                                             "%s: %p succeed %p -> %p", __func__,
 644                                             sx, (void *)x,
 645                                             (void *)(x + SX_ONE_SHARER));
 646                                 break;
 647                         }
 648                         lock_profile_obtain_lock_failed(&sx->lock_object, &contested,
 649                             &waitstart);
 650
 651                         continue;
 652                 }
 653
 654 #ifdef ADAPTIVE_SX
 655                 /*
 656                  * If the owner is running on another CPU, spin until
 657                  * the owner stops running or the state of the lock
 658                  * changes.
 659                  */
 660                 else if (sx->lock_object.lo_flags & SX_ADAPTIVESPIN) {
 661                         x = SX_OWNER(x);
 662                         owner = (struct thread *)x;
 663                         if (TD_IS_RUNNING(owner)) {
 664                                 lock_profile_obtain_lock_failed(&sx->lock_object, &contested,
 665                                     &waitstart);
 666                                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 667                                         CTR3(KTR_LOCK,
 668                                             "%s: spinning on %p held by %p",
 669                                             __func__, sx, owner);
 670                                 GIANT_SAVE();
 671                                 while (SX_OWNER(sx->sx_lock) == x &&
 672                                     TD_IS_RUNNING(owner))
 673                                         cpu_spinwait();
 674                                 continue;
 675                         }
 676                 }
 677 #endif
 678                 else
 679                         lock_profile_obtain_lock_failed(&sx->lock_object, &contested,
 680                             &waitstart);
 681
 682                 /*
 683                  * Some other thread already has an exclusive lock, so
 684                  * start the process of blocking.
 685                  */
 686                 sleepq_lock(&sx->lock_object);
 687                 x = sx->sx_lock;
 688
 689                 /*
 690                  * The lock could have been released while we spun.
 691                  * In this case loop back and retry.
 692                  */
 693                 if (x & SX_LOCK_SHARED) {
 694                         sleepq_release(&sx->lock_object);
 695                         continue;
 696                 }
 697
 698 #ifdef ADAPTIVE_SX
 699                 /*
 700                  * If the owner is running on another CPU, spin until
 701                  * the owner stops running or the state of the lock
 702                  * changes.
 703                  */
 704                 if (!(x & SX_LOCK_SHARED) &&
 705                     (sx->lock_object.lo_flags & SX_ADAPTIVESPIN)) {
 706                         owner = (struct thread *)SX_OWNER(x);
 707                         if (TD_IS_RUNNING(owner)) {
 708                                 sleepq_release(&sx->lock_object);
 709                                 continue;
 710                         }
 711                 }
 712 #endif
 713
 714                 /*
 715                  * Try to set the SX_LOCK_SHARED_WAITERS flag.  If we
 716                  * fail to set it drop the sleep queue lock and loop
 717                  * back.
 718                  */
 719                 if (!(x & SX_LOCK_SHARED_WAITERS)) {
 720                         if (!atomic_cmpset_ptr(&sx->sx_lock, x,
 721                             x | SX_LOCK_SHARED_WAITERS)) {
 722                                 sleepq_release(&sx->lock_object);
 723                                 continue;
 724                         }
 725                         if (LOCK_LOG_TEST(&sx->lock_object, 0))
 726                                 CTR2(KTR_LOCK, "%s: %p set shared waiters flag",
 727                                     __func__, sx);
 728                 }
 729
 730                 /*
 731                  * Since we have been unable to acquire the shared lock,
 732                  * we have to sleep.
 733                  */
 734                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 735                         CTR2(KTR_LOCK, "%s: %p blocking on sleep queue",
 736                             __func__, sx);
 737
 738                 GIANT_SAVE();
 739                 sleepq_add(&sx->lock_object, NULL, sx->lock_object.lo_name,
 740                     SLEEPQ_SX, SQ_SHARED_QUEUE);
 741                 sleepq_wait(&sx->lock_object);
 742
 743                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 744                         CTR2(KTR_LOCK, "%s: %p resuming from sleep queue",
 745                             __func__, sx);
 746         }
 747
 748         GIANT_RESTORE();
 749 }
 750
 751 /*
 752  * This function represents the so-called 'hard case' for sx_sunlock
 753  * operation.  All 'easy case' failures are redirected to this.  Note
 754  * that ideally this would be a static function, but it needs to be
 755  * accessible from at least sx.h.
 756  */
 757 void
 758 _sx_sunlock_hard(struct sx *sx, const char *file, int line)
 759 {
 760         uintptr_t x;
 761
 762         for (;;) {
 763                 x = sx->sx_lock;
 764
 765                 /*
 766                  * We should never have sharers while at least one thread
 767                  * holds a shared lock.
 768                  */
 769                 KASSERT(!(x & SX_LOCK_SHARED_WAITERS),
 770                     ("%s: waiting sharers", __func__));
 771
 772                 /*
 773                  * See if there is more than one shared lock held.  If
 774                  * so, just drop one and return.
 775                  */
 776                 if (SX_SHARERS(x) > 1) {
 777                         if (atomic_cmpset_ptr(&sx->sx_lock, x,
 778                             x - SX_ONE_SHARER)) {
 779                                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 780                                         CTR4(KTR_LOCK,
 781                                             "%s: %p succeeded %p -> %p",
 782                                             __func__, sx, (void *)x,
 783                                             (void *)(x - SX_ONE_SHARER));
 784                                 break;
 785                         }
 786                         continue;
 787                 }
 788
 789                 /*
 790                  * If there aren't any waiters for an exclusive lock,
 791                  * then try to drop it quickly.
 792                  */
 793                 if (!(x & SX_LOCK_EXCLUSIVE_WAITERS)) {
 794                         MPASS(x == SX_SHARERS_LOCK(1));
 795                         if (atomic_cmpset_ptr(&sx->sx_lock, SX_SHARERS_LOCK(1),
 796                             SX_LOCK_UNLOCKED)) {
 797                                 lock_profile_release_lock(&sx->lock_object);
 798                                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 799                                         CTR2(KTR_LOCK, "%s: %p last succeeded",
 800                                             __func__, sx);
 801                                 break;
 802                         }
 803                         continue;
 804                 }
 805
 806                 /*
 807                  * At this point, there should just be one sharer with
 808                  * exclusive waiters.
 809                  */
 810                 MPASS(x == (SX_SHARERS_LOCK(1) | SX_LOCK_EXCLUSIVE_WAITERS));
 811
 812                 lock_profile_release_lock(&sx->lock_object);
 813                 sleepq_lock(&sx->lock_object);
 814
 815                 /*
 816                  * Wake up semantic here is quite simple:
 817                  * Just wake up all the exclusive waiters.
 818                  * Note that the state of the lock could have changed,
 819                  * so if it fails loop back and retry.
 820                  */
 821                 if (!atomic_cmpset_ptr(&sx->sx_lock,
 822                     SX_SHARERS_LOCK(1) | SX_LOCK_EXCLUSIVE_WAITERS,
 823                     SX_LOCK_UNLOCKED)) {
 824                         sleepq_release(&sx->lock_object);
 825                         continue;
 826                 }
 827                 if (LOCK_LOG_TEST(&sx->lock_object, 0))
 828                         CTR2(KTR_LOCK, "%s: %p waking up all thread on"
 829                             "exclusive queue", __func__, sx);
 830                 sleepq_broadcast(&sx->lock_object, SLEEPQ_SX, -1,
 831                     SQ_EXCLUSIVE_QUEUE);
 832                 break;
 833         }
 834 }
 835
 836 #ifdef INVARIANT_SUPPORT
 837 #ifndef INVARIANTS
 838 #undef  _sx_assert
 839 #endif
 840
 841 /*
 842  * In the non-WITNESS case, sx_assert() can only detect that at least
 843  * *some* thread owns an slock, but it cannot guarantee that *this*
 844  * thread owns an slock.
 845  */
 846 void
 847 _sx_assert(struct sx *sx, int what, const char *file, int line)
 848 {
 849 #ifndef WITNESS
 850         int slocked = 0;
 851 #endif
 852
 853         if (panicstr != NULL)
 854                 return;
 855         switch (what) {
 856         case SX_SLOCKED:
 857         case SX_SLOCKED | SX_NOTRECURSED:
 858         case SX_SLOCKED | SX_RECURSED:
 859 #ifndef WITNESS
 860                 slocked = 1;
 861                 /* FALLTHROUGH */
 862 #endif
 863         case SX_LOCKED:
 864         case SX_LOCKED | SX_NOTRECURSED:
 865         case SX_LOCKED | SX_RECURSED:
 866 #ifdef WITNESS
 867                 witness_assert(&sx->lock_object, what, file, line);
 868 #else
 869                 /*
 870                  * If some other thread has an exclusive lock or we
 871                  * have one and are asserting a shared lock, fail.
 872                  * Also, if no one has a lock at all, fail.
 873                  */
 874                 if (sx->sx_lock == SX_LOCK_UNLOCKED ||
 875                     (!(sx->sx_lock & SX_LOCK_SHARED) && (slocked ||
 876                     sx_xholder(sx) != curthread)))
 877                         panic("Lock %s not %slocked @ %s:%d\n",
 878                             sx->lock_object.lo_name, slocked ? "share " : "",
 879                             file, line);
 880
 881                 if (!(sx->sx_lock & SX_LOCK_SHARED)) {
 882                         if (sx_recursed(sx)) {
 883                                 if (what & SX_NOTRECURSED)
 884                                         panic("Lock %s recursed @ %s:%d\n",
 885                                             sx->lock_object.lo_name, file,
 886                                             line);
 887                         } else if (what & SX_RECURSED)
 888                                 panic("Lock %s not recursed @ %s:%d\n",
 889                                     sx->lock_object.lo_name, file, line);
 890                 }
 891 #endif
 892                 break;
 893         case SX_XLOCKED:
 894         case SX_XLOCKED | SX_NOTRECURSED:
 895         case SX_XLOCKED | SX_RECURSED:
 896                 if (sx_xholder(sx) != curthread)
 897                         panic("Lock %s not exclusively locked @ %s:%d\n",
 898                             sx->lock_object.lo_name, file, line);
 899                 if (sx_recursed(sx)) {
 900                         if (what & SX_NOTRECURSED)
 901                                 panic("Lock %s recursed @ %s:%d\n",
 902                                     sx->lock_object.lo_name, file, line);
 903                 } else if (what & SX_RECURSED)
 904                         panic("Lock %s not recursed @ %s:%d\n",
 905                             sx->lock_object.lo_name, file, line);
 906                 break;
 907         case SX_UNLOCKED:
 908 #ifdef WITNESS
 909                 witness_assert(&sx->lock_object, what, file, line);
 910 #else
 911                 /*
 912                  * If we hold an exclusve lock fail.  We can't
 913                  * reliably check to see if we hold a shared lock or
 914                  * not.
 915                  */
 916                 if (sx_xholder(sx) == curthread)
 917                         panic("Lock %s exclusively locked @ %s:%d\n",
 918                             sx->lock_object.lo_name, file, line);
 919 #endif
 920                 break;
 921         default:
 922                 panic("Unknown sx lock assertion: %d @ %s:%d", what, file,
 923                     line);
 924         }
 925 }
 926 #endif  /* INVARIANT_SUPPORT */
 927
 928 #ifdef DDB
 929 static void
 930 db_show_sx(struct lock_object *lock)
 931 {
 932         struct thread *td;
 933         struct sx *sx;
 934
 935         sx = (struct sx *)lock;
 936
 937         db_printf(" state: ");
 938         if (sx->sx_lock == SX_LOCK_UNLOCKED)
 939                 db_printf("UNLOCKED\n");
 940         else if (sx->sx_lock == SX_LOCK_DESTROYED) {
 941                 db_printf("DESTROYED\n");
 942                 return;
 943         } else if (sx->sx_lock & SX_LOCK_SHARED)
 944                 db_printf("SLOCK: %ju\n", (uintmax_t)SX_SHARERS(sx->sx_lock));
 945         else {
 946                 td = sx_xholder(sx);
 947                 db_printf("XLOCK: %p (tid %d, pid %d, \"%s\")\n", td,
 948                     td->td_tid, td->td_proc->p_pid, td->td_proc->p_comm);
 949                 if (sx_recursed(sx))
 950                         db_printf(" recursed: %d\n", sx->sx_recurse);
 951         }
 952
 953         db_printf(" waiters: ");
 954         switch(sx->sx_lock &
 955             (SX_LOCK_SHARED_WAITERS | SX_LOCK_EXCLUSIVE_WAITERS)) {
 956         case SX_LOCK_SHARED_WAITERS:
 957                 db_printf("shared\n");
 958                 break;
 959         case SX_LOCK_EXCLUSIVE_WAITERS:
 960                 db_printf("exclusive\n");
 961                 break;
 962         case SX_LOCK_SHARED_WAITERS | SX_LOCK_EXCLUSIVE_WAITERS:
 963                 db_printf("exclusive and shared\n");
 964                 break;
 965         default:
 966                 db_printf("none\n");
 967         }
 968 }
 969
 970 /*
 971  * Check to see if a thread that is blocked on a sleep queue is actually
 972  * blocked on an sx lock.  If so, output some details and return true.
 973  * If the lock has an exclusive owner, return that in *ownerp.
 974  */
 975 int
 976 sx_chain(struct thread *td, struct thread **ownerp)
 977 {
 978         struct sx *sx;
 979
 980         /*
 981          * Check to see if this thread is blocked on an sx lock.
 982          * First, we check the lock class.  If that is ok, then we
 983          * compare the lock name against the wait message.
 984          */
 985         sx = td->td_wchan;
 986         if (LOCK_CLASS(&sx->lock_object) != &lock_class_sx ||
 987             sx->lock_object.lo_name != td->td_wmesg)
 988                 return (0);
 989
 990         /* We think we have an sx lock, so output some details. */
 991         db_printf("blocked on sx \"%s\" ", td->td_wmesg);
 992         *ownerp = sx_xholder(sx);
 993         if (sx->sx_lock & SX_LOCK_SHARED)
 994                 db_printf("SLOCK (count %ju)\n",
 995                     (uintmax_t)SX_SHARERS(sx->sx_lock));
 996         else
 997                 db_printf("XLOCK\n");
 998         return (1);
 999 }
1000 #endif