sys/kern/kern_rwlock.c

   1 /*-
   2  * Copyright (c) 2006 John Baldwin <jhb@FreeBSD.org>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the author nor the names of any co-contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER 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
  27  * SUCH DAMAGE.
  28  */
  29
  30 /*
  31  * Machine independent bits of reader/writer lock implementation.
  32  */
  33
  34 #include <sys/cdefs.h>
  35 __FBSDID("$FreeBSD$");
  36
  37 #include "opt_ddb.h"
  38 #include "opt_no_adaptive_rwlocks.h"
  39
  40 #include <sys/param.h>
  41 #include <sys/ktr.h>
  42 #include <sys/lock.h>
  43 #include <sys/mutex.h>
  44 #include <sys/proc.h>
  45 #include <sys/rwlock.h>
  46 #include <sys/systm.h>
  47 #include <sys/turnstile.h>
  48
  49 #include <machine/cpu.h>
  50
  51 CTASSERT((RW_RECURSE & LO_CLASSFLAGS) == RW_RECURSE);
  52
  53 #if defined(SMP) && !defined(NO_ADAPTIVE_RWLOCKS)
  54 #define ADAPTIVE_RWLOCKS
  55 #endif
  56
  57 #ifdef DDB
  58 #include <ddb/ddb.h>
  59
  60 static void     db_show_rwlock(struct lock_object *lock);
  61 #endif
  62
  63 struct lock_class lock_class_rw = {
  64         .lc_name = "rw",
  65         .lc_flags = LC_SLEEPLOCK | LC_RECURSABLE | LC_UPGRADABLE,
  66 #ifdef DDB
  67         .lc_ddb_show = db_show_rwlock,
  68 #endif
  69 };
  70
  71 /*
  72  * Return a pointer to the owning thread if the lock is write-locked or
  73  * NULL if the lock is unlocked or read-locked.
  74  */
  75 #define rw_wowner(rw)                                                   \
  76         ((rw)->rw_lock & RW_LOCK_READ ? NULL :                          \
  77             (struct thread *)RW_OWNER((rw)->rw_lock))
  78
  79 /*
  80  * Returns if a write owner is recursed.  Write ownership is not assured
  81  * here and should be previously checked.
  82  */
  83 #define rw_recursed(rw)         ((rw)->rw_recurse != 0)
  84
  85 /*
  86  * Return true if curthread helds the lock.
  87  */
  88 #define rw_wlocked(rw)          (rw_wowner((rw)) == curthread)
  89
  90 /*
  91  * Return a pointer to the owning thread for this lock who should receive
  92  * any priority lent by threads that block on this lock.  Currently this
  93  * is identical to rw_wowner().
  94  */
  95 #define rw_owner(rw)            rw_wowner(rw)
  96
  97 #ifndef INVARIANTS
  98 #define _rw_assert(rw, what, file, line)
  99 #endif
 100
 101 void
 102 rw_init_flags(struct rwlock *rw, const char *name, int opts)
 103 {
 104         int flags;
 105
 106         MPASS((opts & ~(RW_DUPOK | RW_NOPROFILE | RW_NOWITNESS | RW_QUIET |
 107             RW_RECURSE)) == 0);
 108
 109         flags = LO_UPGRADABLE | LO_RECURSABLE;
 110         if (opts & RW_DUPOK)
 111                 flags |= LO_DUPOK;
 112         if (!(opts & RW_NOWITNESS))
 113                 flags |= LO_WITNESS;
 114         if (opts & RW_QUIET)
 115                 flags |= LO_QUIET;
 116         flags |= opts & RW_RECURSE;
 117
 118         rw->rw_lock = RW_UNLOCKED;
 119         rw->rw_recurse = 0;
 120         lock_init(&rw->lock_object, &lock_class_rw, name, NULL, flags);
 121 }
 122
 123 void
 124 rw_destroy(struct rwlock *rw)
 125 {
 126
 127         KASSERT(rw->rw_lock == RW_UNLOCKED, ("rw lock not unlocked"));
 128         KASSERT(rw->rw_recurse == 0, ("rw lock still recursed"));
 129         rw->rw_lock = RW_DESTROYED;
 130         lock_destroy(&rw->lock_object);
 131 }
 132
 133 void
 134 rw_sysinit(void *arg)
 135 {
 136         struct rw_args *args = arg;
 137
 138         rw_init(args->ra_rw, args->ra_desc);
 139 }
 140
 141 int
 142 rw_wowned(struct rwlock *rw)
 143 {
 144
 145         return (rw_wowner(rw) == curthread);
 146 }
 147
 148 void
 149 _rw_wlock(struct rwlock *rw, const char *file, int line)
 150 {
 151
 152         MPASS(curthread != NULL);
 153         KASSERT(rw->rw_lock != RW_DESTROYED,
 154             ("rw_wlock() of destroyed rwlock @ %s:%d", file, line));
 155         KASSERT(rw_wowner(rw) != curthread,
 156             ("%s (%s): wlock already held @ %s:%d", __func__,
 157             rw->lock_object.lo_name, file, line));
 158         WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE, file,
 159             line);
 160         __rw_wlock(rw, curthread, file, line);
 161         LOCK_LOG_LOCK("WLOCK", &rw->lock_object, 0, rw->rw_recurse, file, line);
 162         WITNESS_LOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line);
 163         curthread->td_locks++;
 164 }
 165
 166 void
 167 _rw_wunlock(struct rwlock *rw, const char *file, int line)
 168 {
 169
 170         MPASS(curthread != NULL);
 171         KASSERT(rw->rw_lock != RW_DESTROYED,
 172             ("rw_wunlock() of destroyed rwlock @ %s:%d", file, line));
 173         _rw_assert(rw, RA_WLOCKED, file, line);
 174         curthread->td_locks--;
 175         WITNESS_UNLOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line);
 176         LOCK_LOG_LOCK("WUNLOCK", &rw->lock_object, 0, rw->rw_recurse, file,
 177             line);
 178         if (!rw_recursed(rw))
 179                 lock_profile_release_lock(&rw->lock_object);
 180         __rw_wunlock(rw, curthread, file, line);
 181 }
 182
 183 void
 184 _rw_rlock(struct rwlock *rw, const char *file, int line)
 185 {
 186 #ifdef ADAPTIVE_RWLOCKS
 187         volatile struct thread *owner;
 188 #endif
 189         //uint64_t waittime = 0; /* XXX: notsup */
 190         //int contested = 0; /* XXX: notsup */
 191         uintptr_t x;
 192
 193         KASSERT(rw->rw_lock != RW_DESTROYED,
 194             ("rw_rlock() of destroyed rwlock @ %s:%d", file, line));
 195         KASSERT(rw_wowner(rw) != curthread,
 196             ("%s (%s): wlock already held @ %s:%d", __func__,
 197             rw->lock_object.lo_name, file, line));
 198         WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER, file, line);
 199
 200         /*
 201          * Note that we don't make any attempt to try to block read
 202          * locks once a writer has blocked on the lock.  The reason is
 203          * that we currently allow for read locks to recurse and we
 204          * don't keep track of all the holders of read locks.  Thus, if
 205          * we were to block readers once a writer blocked and a reader
 206          * tried to recurse on their reader lock after a writer had
 207          * blocked we would end up in a deadlock since the reader would
 208          * be blocked on the writer, and the writer would be blocked
 209          * waiting for the reader to release its original read lock.
 210          */
 211         for (;;) {
 212                 /*
 213                  * Handle the easy case.  If no other thread has a write
 214                  * lock, then try to bump up the count of read locks.  Note
 215                  * that we have to preserve the current state of the
 216                  * RW_LOCK_WRITE_WAITERS flag.  If we fail to acquire a
 217                  * read lock, then rw_lock must have changed, so restart
 218                  * the loop.  Note that this handles the case of a
 219                  * completely unlocked rwlock since such a lock is encoded
 220                  * as a read lock with no waiters.
 221                  */
 222                 x = rw->rw_lock;
 223                 if (x & RW_LOCK_READ) {
 224
 225                         /*
 226                          * The RW_LOCK_READ_WAITERS flag should only be set
 227                          * if another thread currently holds a write lock,
 228                          * and in that case RW_LOCK_READ should be clear.
 229                          */
 230                         MPASS((x & RW_LOCK_READ_WAITERS) == 0);
 231                         if (atomic_cmpset_acq_ptr(&rw->rw_lock, x,
 232                             x + RW_ONE_READER)) {
 233                                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 234                                         CTR4(KTR_LOCK,
 235                                             "%s: %p succeed %p -> %p", __func__,
 236                                             rw, (void *)x,
 237                                             (void *)(x + RW_ONE_READER));
 238                                 if (RW_READERS(x) == 0)
 239                                         lock_profile_obtain_lock_success(
 240                                             &rw->lock_object, contested, waittime,
 241                                             file, line);
 242                                 break;
 243                         }
 244                         cpu_spinwait();
 245                         continue;
 246                 }
 247                 lock_profile_obtain_lock_failed(&rw->lock_object, &contested,
 248                     &waittime);
 249
 250                 /*
 251                  * Okay, now it's the hard case.  Some other thread already
 252                  * has a write lock, so acquire the turnstile lock so we can
 253                  * begin the process of blocking.
 254                  */
 255                 turnstile_lock(&rw->lock_object);
 256
 257                 /*
 258                  * The lock might have been released while we spun, so
 259                  * recheck its state and restart the loop if there is no
 260                  * longer a write lock.
 261                  */
 262                 x = rw->rw_lock;
 263                 if (x & RW_LOCK_READ) {
 264                         turnstile_release(&rw->lock_object);
 265                         cpu_spinwait();
 266                         continue;
 267                 }
 268
 269                 /*
 270                  * Ok, it's still a write lock.  If the RW_LOCK_READ_WAITERS
 271                  * flag is already set, then we can go ahead and block.  If
 272                  * it is not set then try to set it.  If we fail to set it
 273                  * drop the turnstile lock and restart the loop.
 274                  */
 275                 if (!(x & RW_LOCK_READ_WAITERS)) {
 276                         if (!atomic_cmpset_ptr(&rw->rw_lock, x,
 277                             x | RW_LOCK_READ_WAITERS)) {
 278                                 turnstile_release(&rw->lock_object);
 279                                 cpu_spinwait();
 280                                 continue;
 281                         }
 282                         if (LOCK_LOG_TEST(&rw->lock_object, 0))
 283                                 CTR2(KTR_LOCK, "%s: %p set read waiters flag",
 284                                     __func__, rw);
 285                 }
 286
 287 #ifdef ADAPTIVE_RWLOCKS
 288                 /*
 289                  * If the owner is running on another CPU, spin until
 290                  * the owner stops running or the state of the lock
 291                  * changes.
 292                  */
 293                 owner = (struct thread *)RW_OWNER(x);
 294                 if (TD_IS_RUNNING(owner)) {
 295                         turnstile_release(&rw->lock_object);
 296                         if (LOCK_LOG_TEST(&rw->lock_object, 0))
 297                                 CTR3(KTR_LOCK, "%s: spinning on %p held by %p",
 298                                     __func__, rw, owner);
 299                         while ((struct thread*)RW_OWNER(rw->rw_lock)== owner &&
 300                             TD_IS_RUNNING(owner))
 301                                 cpu_spinwait();
 302                         continue;
 303                 }
 304 #endif
 305
 306                 /*
 307                  * We were unable to acquire the lock and the read waiters
 308                  * flag is set, so we must block on the turnstile.
 309                  */
 310                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 311                         CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__,
 312                             rw);
 313                 turnstile_wait(&rw->lock_object, rw_owner(rw),
 314                     TS_SHARED_QUEUE);
 315                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 316                         CTR2(KTR_LOCK, "%s: %p resuming from turnstile",
 317                             __func__, rw);
 318         }
 319
 320         /*
 321          * TODO: acquire "owner of record" here.  Here be turnstile dragons
 322          * however.  turnstiles don't like owners changing between calls to
 323          * turnstile_wait() currently.
 324          */
 325
 326         LOCK_LOG_LOCK("RLOCK", &rw->lock_object, 0, 0, file, line);
 327         WITNESS_LOCK(&rw->lock_object, 0, file, line);
 328         curthread->td_locks++;
 329 }
 330
 331 void
 332 _rw_runlock(struct rwlock *rw, const char *file, int line)
 333 {
 334         struct turnstile *ts;
 335         uintptr_t x;
 336
 337         KASSERT(rw->rw_lock != RW_DESTROYED,
 338             ("rw_runlock() of destroyed rwlock @ %s:%d", file, line));
 339         _rw_assert(rw, RA_RLOCKED, file, line);
 340         curthread->td_locks--;
 341         WITNESS_UNLOCK(&rw->lock_object, 0, file, line);
 342         LOCK_LOG_LOCK("RUNLOCK", &rw->lock_object, 0, 0, file, line);
 343
 344         /* TODO: drop "owner of record" here. */
 345
 346         for (;;) {
 347                 /*
 348                  * See if there is more than one read lock held.  If so,
 349                  * just drop one and return.
 350                  */
 351                 x = rw->rw_lock;
 352                 if (RW_READERS(x) > 1) {
 353                         if (atomic_cmpset_ptr(&rw->rw_lock, x,
 354                             x - RW_ONE_READER)) {
 355                                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 356                                         CTR4(KTR_LOCK,
 357                                             "%s: %p succeeded %p -> %p",
 358                                             __func__, rw, (void *)x,
 359                                             (void *)(x - RW_ONE_READER));
 360                                 break;
 361                         }
 362                         continue;
 363                 }
 364
 365
 366                 /*
 367                  * We should never have read waiters while at least one
 368                  * thread holds a read lock.  (See note above)
 369                  */
 370                 KASSERT(!(x & RW_LOCK_READ_WAITERS),
 371                     ("%s: waiting readers", __func__));
 372
 373                 /*
 374                  * If there aren't any waiters for a write lock, then try
 375                  * to drop it quickly.
 376                  */
 377                 if (!(x & RW_LOCK_WRITE_WAITERS)) {
 378
 379                         /*
 380                          * There shouldn't be any flags set and we should
 381                          * be the only read lock.  If we fail to release
 382                          * the single read lock, then another thread might
 383                          * have just acquired a read lock, so go back up
 384                          * to the multiple read locks case.
 385                          */
 386                         MPASS(x == RW_READERS_LOCK(1));
 387                         if (atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1),
 388                             RW_UNLOCKED)) {
 389                                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 390                                         CTR2(KTR_LOCK, "%s: %p last succeeded",
 391                                             __func__, rw);
 392                                 break;
 393                         }
 394                         continue;
 395                 }
 396
 397                 /*
 398                  * There should just be one reader with one or more
 399                  * writers waiting.
 400                  */
 401                 MPASS(x == (RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS));
 402
 403                 /*
 404                  * Ok, we know we have a waiting writer and we think we
 405                  * are the last reader, so grab the turnstile lock.
 406                  */
 407                 turnstile_lock(&rw->lock_object);
 408
 409                 /*
 410                  * Try to drop our lock leaving the lock in a unlocked
 411                  * state.
 412                  *
 413                  * If you wanted to do explicit lock handoff you'd have to
 414                  * do it here.  You'd also want to use turnstile_signal()
 415                  * and you'd have to handle the race where a higher
 416                  * priority thread blocks on the write lock before the
 417                  * thread you wakeup actually runs and have the new thread
 418                  * "steal" the lock.  For now it's a lot simpler to just
 419                  * wakeup all of the waiters.
 420                  *
 421                  * As above, if we fail, then another thread might have
 422                  * acquired a read lock, so drop the turnstile lock and
 423                  * restart.
 424                  */
 425                 if (!atomic_cmpset_ptr(&rw->rw_lock,
 426                     RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS, RW_UNLOCKED)) {
 427                         turnstile_release(&rw->lock_object);
 428                         continue;
 429                 }
 430                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 431                         CTR2(KTR_LOCK, "%s: %p last succeeded with waiters",
 432                             __func__, rw);
 433
 434                 /*
 435                  * Ok.  The lock is released and all that's left is to
 436                  * wake up the waiters.  Note that the lock might not be
 437                  * free anymore, but in that case the writers will just
 438                  * block again if they run before the new lock holder(s)
 439                  * release the lock.
 440                  */
 441                 ts = turnstile_lookup(&rw->lock_object);
 442                 MPASS(ts != NULL);
 443                 turnstile_broadcast(ts, TS_EXCLUSIVE_QUEUE);
 444                 turnstile_unpend(ts, TS_SHARED_LOCK);
 445                 break;
 446         }
 447         lock_profile_release_lock(&rw->lock_object);
 448 }
 449
 450 /*
 451  * This function is called when we are unable to obtain a write lock on the
 452  * first try.  This means that at least one other thread holds either a
 453  * read or write lock.
 454  */
 455 void
 456 _rw_wlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line)
 457 {
 458 #ifdef ADAPTIVE_RWLOCKS
 459         volatile struct thread *owner;
 460 #endif
 461         uintptr_t v;
 462
 463         if (rw_wlocked(rw)) {
 464                 KASSERT(rw->lock_object.lo_flags & RW_RECURSE,
 465                     ("%s: recursing but non-recursive rw %s @ %s:%d\n",
 466                     __func__, rw->lock_object.lo_name, file, line));
 467                 rw->rw_recurse++;
 468                 atomic_set_ptr(&rw->rw_lock, RW_LOCK_RECURSED);
 469                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 470                         CTR2(KTR_LOCK, "%s: %p recursing", __func__, rw);
 471                 return;
 472         }
 473
 474         if (LOCK_LOG_TEST(&rw->lock_object, 0))
 475                 CTR5(KTR_LOCK, "%s: %s contested (lock=%p) at %s:%d", __func__,
 476                     rw->lock_object.lo_name, (void *)rw->rw_lock, file, line);
 477
 478         while (!_rw_write_lock(rw, tid)) {
 479                 turnstile_lock(&rw->lock_object);
 480                 v = rw->rw_lock;
 481
 482                 /*
 483                  * If the lock was released while spinning on the
 484                  * turnstile chain lock, try again.
 485                  */
 486                 if (v == RW_UNLOCKED) {
 487                         turnstile_release(&rw->lock_object);
 488                         cpu_spinwait();
 489                         continue;
 490                 }
 491
 492                 /*
 493                  * If the lock was released by a writer with both readers
 494                  * and writers waiting and a reader hasn't woken up and
 495                  * acquired the lock yet, rw_lock will be set to the
 496                  * value RW_UNLOCKED | RW_LOCK_WRITE_WAITERS.  If we see
 497                  * that value, try to acquire it once.  Note that we have
 498                  * to preserve the RW_LOCK_WRITE_WAITERS flag as there are
 499                  * other writers waiting still.  If we fail, restart the
 500                  * loop.
 501                  */
 502                 if (v == (RW_UNLOCKED | RW_LOCK_WRITE_WAITERS)) {
 503                         if (atomic_cmpset_acq_ptr(&rw->rw_lock,
 504                             RW_UNLOCKED | RW_LOCK_WRITE_WAITERS,
 505                             tid | RW_LOCK_WRITE_WAITERS)) {
 506                                 turnstile_claim(&rw->lock_object);
 507                                 CTR2(KTR_LOCK, "%s: %p claimed by new writer",
 508                                     __func__, rw);
 509                                 break;
 510                         }
 511                         turnstile_release(&rw->lock_object);
 512                         cpu_spinwait();
 513                         continue;
 514                 }
 515
 516                 /*
 517                  * If the RW_LOCK_WRITE_WAITERS flag isn't set, then try to
 518                  * set it.  If we fail to set it, then loop back and try
 519                  * again.
 520                  */
 521                 if (!(v & RW_LOCK_WRITE_WAITERS)) {
 522                         if (!atomic_cmpset_ptr(&rw->rw_lock, v,
 523                             v | RW_LOCK_WRITE_WAITERS)) {
 524                                 turnstile_release(&rw->lock_object);
 525                                 cpu_spinwait();
 526                                 continue;
 527                         }
 528                         if (LOCK_LOG_TEST(&rw->lock_object, 0))
 529                                 CTR2(KTR_LOCK, "%s: %p set write waiters flag",
 530                                     __func__, rw);
 531                 }
 532
 533 #ifdef ADAPTIVE_RWLOCKS
 534                 /*
 535                  * If the lock is write locked and the owner is
 536                  * running on another CPU, spin until the owner stops
 537                  * running or the state of the lock changes.
 538                  */
 539                 owner = (struct thread *)RW_OWNER(v);
 540                 if (!(v & RW_LOCK_READ) && TD_IS_RUNNING(owner)) {
 541                         turnstile_release(&rw->lock_object);
 542                         if (LOCK_LOG_TEST(&rw->lock_object, 0))
 543                                 CTR3(KTR_LOCK, "%s: spinning on %p held by %p",
 544                                     __func__, rw, owner);
 545                         while ((struct thread*)RW_OWNER(rw->rw_lock)== owner &&
 546                             TD_IS_RUNNING(owner))
 547                                 cpu_spinwait();
 548                         continue;
 549                 }
 550 #endif
 551
 552                 /*
 553                  * We were unable to acquire the lock and the write waiters
 554                  * flag is set, so we must block on the turnstile.
 555                  */
 556                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 557                         CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__,
 558                             rw);
 559                 turnstile_wait(&rw->lock_object, rw_owner(rw),
 560                     TS_EXCLUSIVE_QUEUE);
 561                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 562                         CTR2(KTR_LOCK, "%s: %p resuming from turnstile",
 563                             __func__, rw);
 564         }
 565 }
 566
 567 /*
 568  * This function is called if the first try at releasing a write lock failed.
 569  * This means that one of the 2 waiter bits must be set indicating that at
 570  * least one thread is waiting on this lock.
 571  */
 572 void
 573 _rw_wunlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line)
 574 {
 575         struct turnstile *ts;
 576         uintptr_t v;
 577         int queue;
 578
 579         if (rw_wlocked(rw) && rw_recursed(rw)) {
 580                 if ((--rw->rw_recurse) == 0)
 581                         atomic_clear_ptr(&rw->rw_lock, RW_LOCK_RECURSED);
 582                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 583                         CTR2(KTR_LOCK, "%s: %p unrecursing", __func__, rw);
 584                 return;
 585         }
 586
 587         KASSERT(rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS),
 588             ("%s: neither of the waiter flags are set", __func__));
 589
 590         if (LOCK_LOG_TEST(&rw->lock_object, 0))
 591                 CTR2(KTR_LOCK, "%s: %p contested", __func__, rw);
 592
 593         turnstile_lock(&rw->lock_object);
 594         ts = turnstile_lookup(&rw->lock_object);
 595
 596 #ifdef ADAPTIVE_RWLOCKS
 597         /*
 598          * There might not be a turnstile for this lock if all of
 599          * the waiters are adaptively spinning.  In that case, just
 600          * reset the lock to the unlocked state and return.
 601          */
 602         if (ts == NULL) {
 603                 atomic_store_rel_ptr(&rw->rw_lock, RW_UNLOCKED);
 604                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 605                         CTR2(KTR_LOCK, "%s: %p no sleepers", __func__, rw);
 606                 turnstile_release(&rw->lock_object);
 607                 return;
 608         }
 609 #else
 610         MPASS(ts != NULL);
 611 #endif
 612
 613         /*
 614          * Use the same algo as sx locks for now.  Prefer waking up shared
 615          * waiters if we have any over writers.  This is probably not ideal.
 616          *
 617          * 'v' is the value we are going to write back to rw_lock.  If we
 618          * have waiters on both queues, we need to preserve the state of
 619          * the waiter flag for the queue we don't wake up.  For now this is
 620          * hardcoded for the algorithm mentioned above.
 621          *
 622          * In the case of both readers and writers waiting we wakeup the
 623          * readers but leave the RW_LOCK_WRITE_WAITERS flag set.  If a
 624          * new writer comes in before a reader it will claim the lock up
 625          * above.  There is probably a potential priority inversion in
 626          * there that could be worked around either by waking both queues
 627          * of waiters or doing some complicated lock handoff gymnastics.
 628          *
 629          * Note that in the ADAPTIVE_RWLOCKS case, if both flags are
 630          * set, there might not be any actual writers on the turnstile
 631          * as they might all be spinning.  In that case, we don't want
 632          * to preserve the RW_LOCK_WRITE_WAITERS flag as the turnstile
 633          * is going to go away once we wakeup all the readers.
 634          */
 635         v = RW_UNLOCKED;
 636         if (rw->rw_lock & RW_LOCK_READ_WAITERS) {
 637                 queue = TS_SHARED_QUEUE;
 638 #ifdef ADAPTIVE_RWLOCKS
 639                 if (rw->rw_lock & RW_LOCK_WRITE_WAITERS &&
 640                     !turnstile_empty(ts, TS_EXCLUSIVE_QUEUE))
 641                         v |= RW_LOCK_WRITE_WAITERS;
 642 #else
 643                 v |= (rw->rw_lock & RW_LOCK_WRITE_WAITERS);
 644 #endif
 645         } else
 646                 queue = TS_EXCLUSIVE_QUEUE;
 647
 648 #ifdef ADAPTIVE_RWLOCKS
 649         /*
 650          * We have to make sure that we actually have waiters to
 651          * wakeup.  If they are all spinning, then we just need to
 652          * disown the turnstile and return.
 653          */
 654         if (turnstile_empty(ts, queue)) {
 655                 if (LOCK_LOG_TEST(&rw->lock_object, 0))
 656                         CTR2(KTR_LOCK, "%s: %p no sleepers 2", __func__, rw);
 657                 atomic_store_rel_ptr(&rw->rw_lock, v);
 658                 turnstile_disown(ts);
 659                 turnstile_release(&rw->lock_object);
 660                 return;
 661         }
 662 #endif
 663
 664         /* Wake up all waiters for the specific queue. */
 665         if (LOCK_LOG_TEST(&rw->lock_object, 0))
 666                 CTR3(KTR_LOCK, "%s: %p waking up %s waiters", __func__, rw,
 667                     queue == TS_SHARED_QUEUE ? "read" : "write");
 668         turnstile_broadcast(ts, queue);
 669         atomic_store_rel_ptr(&rw->rw_lock, v);
 670         turnstile_unpend(ts, TS_EXCLUSIVE_LOCK);
 671 }
 672
 673 /*
 674  * Attempt to do a non-blocking upgrade from a read lock to a write
 675  * lock.  This will only succeed if this thread holds a single read
 676  * lock.  Returns true if the upgrade succeeded and false otherwise.
 677  */
 678 int
 679 _rw_try_upgrade(struct rwlock *rw, const char *file, int line)
 680 {
 681         uintptr_t v, tid;
 682         int success;
 683
 684         KASSERT(rw->rw_lock != RW_DESTROYED,
 685             ("rw_try_upgrade() of destroyed rwlock @ %s:%d", file, line));
 686         _rw_assert(rw, RA_RLOCKED, file, line);
 687
 688         /*
 689          * Attempt to switch from one reader to a writer.  If there
 690          * are any write waiters, then we will have to lock the
 691          * turnstile first to prevent races with another writer
 692          * calling turnstile_wait() before we have claimed this
 693          * turnstile.  So, do the simple case of no waiters first.
 694          */
 695         tid = (uintptr_t)curthread;
 696         if (!(rw->rw_lock & RW_LOCK_WRITE_WAITERS)) {
 697                 success = atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1),
 698                     tid);
 699                 goto out;
 700         }
 701
 702         /*
 703          * Ok, we think we have write waiters, so lock the
 704          * turnstile.
 705          */
 706         turnstile_lock(&rw->lock_object);
 707
 708         /*
 709          * Try to switch from one reader to a writer again.  This time
 710          * we honor the current state of the RW_LOCK_WRITE_WAITERS
 711          * flag.  If we obtain the lock with the flag set, then claim
 712          * ownership of the turnstile.  In the ADAPTIVE_RWLOCKS case
 713          * it is possible for there to not be an associated turnstile
 714          * even though there are waiters if all of the waiters are
 715          * spinning.
 716          */
 717         v = rw->rw_lock & RW_LOCK_WRITE_WAITERS;
 718         success = atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | v,
 719             tid | v);
 720 #ifdef ADAPTIVE_RWLOCKS
 721         if (success && v && turnstile_lookup(&rw->lock_object) != NULL)
 722 #else
 723         if (success && v)
 724 #endif
 725                 turnstile_claim(&rw->lock_object);
 726         else
 727                 turnstile_release(&rw->lock_object);
 728 out:
 729         LOCK_LOG_TRY("WUPGRADE", &rw->lock_object, 0, success, file, line);
 730         if (success)
 731                 WITNESS_UPGRADE(&rw->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK,
 732                     file, line);
 733         return (success);
 734 }
 735
 736 /*
 737  * Downgrade a write lock into a single read lock.
 738  */
 739 void
 740 _rw_downgrade(struct rwlock *rw, const char *file, int line)
 741 {
 742         struct turnstile *ts;
 743         uintptr_t tid, v;
 744
 745         KASSERT(rw->rw_lock != RW_DESTROYED,
 746             ("rw_downgrade() of destroyed rwlock @ %s:%d", file, line));
 747         _rw_assert(rw, RA_WLOCKED | RA_NOTRECURSED, file, line);
 748 #ifndef INVARIANTS
 749         if (rw_recursed(rw))
 750                 panic("downgrade of a recursed lock");
 751 #endif
 752
 753         WITNESS_DOWNGRADE(&rw->lock_object, 0, file, line);
 754
 755         /*
 756          * Convert from a writer to a single reader.  First we handle
 757          * the easy case with no waiters.  If there are any waiters, we
 758          * lock the turnstile, "disown" the lock, and awaken any read
 759          * waiters.
 760          */
 761         tid = (uintptr_t)curthread;
 762         if (atomic_cmpset_rel_ptr(&rw->rw_lock, tid, RW_READERS_LOCK(1)))
 763                 goto out;
 764
 765         /*
 766          * Ok, we think we have waiters, so lock the turnstile so we can
 767          * read the waiter flags without any races.
 768          */
 769         turnstile_lock(&rw->lock_object);
 770         v = rw->rw_lock;
 771         MPASS(v & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS));
 772
 773         /*
 774          * Downgrade from a write lock while preserving
 775          * RW_LOCK_WRITE_WAITERS and give up ownership of the
 776          * turnstile.  If there are any read waiters, wake them up.
 777          *
 778          * For ADAPTIVE_RWLOCKS, we have to allow for the fact that
 779          * all of the read waiters might be spinning.  In that case,
 780          * act as if RW_LOCK_READ_WAITERS is not set.  Also, only
 781          * preserve the RW_LOCK_WRITE_WAITERS flag if at least one
 782          * writer is blocked on the turnstile.
 783          */
 784         ts = turnstile_lookup(&rw->lock_object);
 785 #ifdef ADAPTIVE_RWLOCKS
 786         if (ts == NULL)
 787                 v &= ~(RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS);
 788         else if (v & RW_LOCK_READ_WAITERS &&
 789             turnstile_empty(ts, TS_SHARED_QUEUE))
 790                 v &= ~RW_LOCK_READ_WAITERS;
 791         else if (v & RW_LOCK_WRITE_WAITERS &&
 792             turnstile_empty(ts, TS_EXCLUSIVE_QUEUE))
 793                 v &= ~RW_LOCK_WRITE_WAITERS;
 794 #else
 795         MPASS(ts != NULL);
 796 #endif
 797         if (v & RW_LOCK_READ_WAITERS)
 798                 turnstile_broadcast(ts, TS_SHARED_QUEUE);
 799         atomic_store_rel_ptr(&rw->rw_lock, RW_READERS_LOCK(1) |
 800             (v & RW_LOCK_WRITE_WAITERS));
 801         if (v & RW_LOCK_READ_WAITERS) {
 802                 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK);
 803         } else if (ts) {
 804                 turnstile_disown(ts);
 805                 turnstile_release(&rw->lock_object);
 806         }
 807 out:
 808         LOCK_LOG_LOCK("WDOWNGRADE", &rw->lock_object, 0, 0, file, line);
 809 }
 810
 811 #ifdef INVARIANT_SUPPORT
 812 #ifndef INVARIANTS
 813 #undef _rw_assert
 814 #endif
 815
 816 /*
 817  * In the non-WITNESS case, rw_assert() can only detect that at least
 818  * *some* thread owns an rlock, but it cannot guarantee that *this*
 819  * thread owns an rlock.
 820  */
 821 void
 822 _rw_assert(struct rwlock *rw, int what, const char *file, int line)
 823 {
 824
 825         if (panicstr != NULL)
 826                 return;
 827         switch (what) {
 828         case RA_LOCKED:
 829         case RA_LOCKED | RA_RECURSED:
 830         case RA_LOCKED | RA_NOTRECURSED:
 831         case RA_RLOCKED:
 832 #ifdef WITNESS
 833                 witness_assert(&rw->lock_object, what, file, line);
 834 #else
 835                 /*
 836                  * If some other thread has a write lock or we have one
 837                  * and are asserting a read lock, fail.  Also, if no one
 838                  * has a lock at all, fail.
 839                  */
 840                 if (rw->rw_lock == RW_UNLOCKED ||
 841                     (!(rw->rw_lock & RW_LOCK_READ) && (what == RA_RLOCKED ||
 842                     rw_wowner(rw) != curthread)))
 843                         panic("Lock %s not %slocked @ %s:%d\n",
 844                             rw->lock_object.lo_name, (what == RA_RLOCKED) ?
 845                             "read " : "", file, line);
 846
 847                 if (!(rw->rw_lock & RW_LOCK_READ)) {
 848                         if (rw_recursed(rw)) {
 849                                 if (what & RA_NOTRECURSED)
 850                                         panic("Lock %s recursed @ %s:%d\n",
 851                                             rw->lock_object.lo_name, file,
 852                                             line);
 853                         } else if (what & RA_RECURSED)
 854                                 panic("Lock %s not recursed @ %s:%d\n",
 855                                     rw->lock_object.lo_name, file, line);
 856                 }
 857 #endif
 858                 break;
 859         case RA_WLOCKED:
 860         case RA_WLOCKED | RA_RECURSED:
 861         case RA_WLOCKED | RA_NOTRECURSED:
 862                 if (rw_wowner(rw) != curthread)
 863                         panic("Lock %s not exclusively locked @ %s:%d\n",
 864                             rw->lock_object.lo_name, file, line);
 865                 if (rw_recursed(rw)) {
 866                         if (what & RA_NOTRECURSED)
 867                                 panic("Lock %s recursed @ %s:%d\n",
 868                                     rw->lock_object.lo_name, file, line);
 869                 } else if (what & RA_RECURSED)
 870                         panic("Lock %s not recursed @ %s:%d\n",
 871                             rw->lock_object.lo_name, file, line);
 872                 break;
 873         case RA_UNLOCKED:
 874 #ifdef WITNESS
 875                 witness_assert(&rw->lock_object, what, file, line);
 876 #else
 877                 /*
 878                  * If we hold a write lock fail.  We can't reliably check
 879                  * to see if we hold a read lock or not.
 880                  */
 881                 if (rw_wowner(rw) == curthread)
 882                         panic("Lock %s exclusively locked @ %s:%d\n",
 883                             rw->lock_object.lo_name, file, line);
 884 #endif
 885                 break;
 886         default:
 887                 panic("Unknown rw lock assertion: %d @ %s:%d", what, file,
 888                     line);
 889         }
 890 }
 891 #endif /* INVARIANT_SUPPORT */
 892
 893 #ifdef DDB
 894 void
 895 db_show_rwlock(struct lock_object *lock)
 896 {
 897         struct rwlock *rw;
 898         struct thread *td;
 899
 900         rw = (struct rwlock *)lock;
 901
 902         db_printf(" state: ");
 903         if (rw->rw_lock == RW_UNLOCKED)
 904                 db_printf("UNLOCKED\n");
 905         else if (rw->rw_lock == RW_DESTROYED) {
 906                 db_printf("DESTROYED\n");
 907                 return;
 908         } else if (rw->rw_lock & RW_LOCK_READ)
 909                 db_printf("RLOCK: %ju locks\n",
 910                     (uintmax_t)(RW_READERS(rw->rw_lock)));
 911         else {
 912                 td = rw_wowner(rw);
 913                 db_printf("WLOCK: %p (tid %d, pid %d, \"%s\")\n", td,
 914                     td->td_tid, td->td_proc->p_pid, td->td_proc->p_comm);
 915                 if (rw_recursed(rw))
 916                         db_printf(" recursed: %u\n", rw->rw_recurse);
 917         }
 918         db_printf(" waiters: ");
 919         switch (rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)) {
 920         case RW_LOCK_READ_WAITERS:
 921                 db_printf("readers\n");
 922                 break;
 923         case RW_LOCK_WRITE_WAITERS:
 924                 db_printf("writers\n");
 925                 break;
 926         case RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS:
 927                 db_printf("readers and writers\n");
 928                 break;
 929         default:
 930                 db_printf("none\n");
 931                 break;
 932         }
 933 }
 934
 935 #endif