The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/kern_rwlock.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: da50a46feeacacddafe0d1271cbb5fb8


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.