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

Cache object: e6370c0e7914236e31b901239fc03502


[ 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.