kern_mutex.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*
    2  * Copyright (c) 2009 The DragonFly Project.  All rights reserved.
    3  *
    4  * This code is derived from software contributed to The DragonFly Project
    5  * by Matthew Dillon <dillon@backplane.com>
    6  *
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  *
   11  * 1. Redistributions of source code must retain the above copyright
   12  *    notice, this list of conditions and the following disclaimer.
   13  * 2. Redistributions in binary form must reproduce the above copyright
   14  *    notice, this list of conditions and the following disclaimer in
   15  *    the documentation and/or other materials provided with the
   16  *    distribution.
   17  * 3. Neither the name of The DragonFly Project nor the names of its
   18  *    contributors may be used to endorse or promote products derived
   19  *    from this software without specific, prior written permission.
   20  *
   21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
   25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
   27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
   29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   32  * SUCH DAMAGE.
   33  */
   34 /*
   35  * Implement fast persistent locks based on atomic_cmpset_int() with
   36  * semantics similar to lockmgr locks but faster and taking up much less
   37  * space.  Taken from HAMMER's lock implementation.
   38  *
   39  * These are meant to complement our LWKT tokens.  Tokens are only held
   40  * while the thread is running.  Mutexes can be held across blocking
   41  * conditions.
   42  *
   43  * Most of the support is in sys/mutex[2].h.  We mostly provide backoff
   44  * functions here.
   45  */
   46 
   47 #include <sys/param.h>
   48 #include <sys/systm.h>
   49 #include <sys/kernel.h>
   50 #include <sys/sysctl.h>
   51 #include <sys/thread.h>
   52 
   53 #include <machine/cpufunc.h>
   54 
   55 #include <sys/thread2.h>
   56 #include <sys/mutex2.h>
   57 
   58 static __int64_t mtx_contention_count;
   59 static __int64_t mtx_collision_count;
   60 static __int64_t mtx_wakeup_count;
   61 
   62 SYSCTL_QUAD(_kern, OID_AUTO, mtx_contention_count, CTLFLAG_RW,
   63             &mtx_contention_count, 0, "");
   64 SYSCTL_QUAD(_kern, OID_AUTO, mtx_collision_count, CTLFLAG_RW,
   65             &mtx_collision_count, 0, "");
   66 SYSCTL_QUAD(_kern, OID_AUTO, mtx_wakeup_count, CTLFLAG_RW,
   67             &mtx_wakeup_count, 0, "");
   68 
   69 static void mtx_chain_link(mtx_t mtx);
   70 static void mtx_delete_link(mtx_t mtx, mtx_link_t link);
   71 
   72 /*
   73  * Exclusive-lock a mutex, block until acquired.  Recursion is allowed.
   74  *
   75  * Returns 0 on success, or the tsleep() return code on failure.
   76  * An error can only be returned if PCATCH is specified in the flags.
   77  */
   78 static __inline int
   79 __mtx_lock_ex(mtx_t mtx, mtx_link_t link, const char *ident, int flags, int to)
   80 {
   81         u_int   lock;
   82         u_int   nlock;
   83         int     error;
   84 
   85         for (;;) {
   86                 lock = mtx->mtx_lock;
   87                 if (lock == 0) {
   88                         nlock = MTX_EXCLUSIVE | 1;
   89                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
   90                                 mtx->mtx_owner = curthread;
   91                                 error = 0;
   92                                 break;
   93                         }
   94                 } else if ((lock & MTX_EXCLUSIVE) &&
   95                            mtx->mtx_owner == curthread) {
   96                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
   97                         nlock = lock + 1;
   98                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
   99                                 error = 0;
  100                                 break;
  101                         }
  102                 } else {
  103                         /*
  104                          * Clearing MTX_EXLINK in lock causes us to loop until
  105                          * MTX_EXLINK is available.  However, to avoid
  106                          * unnecessary cpu cache traffic we poll instead.
  107                          *
  108                          * Setting MTX_EXLINK in nlock causes us to loop until
  109                          * we can acquire MTX_EXLINK.
  110                          *
  111                          * Also set MTX_EXWANTED coincident with EXLINK, if
  112                          * not already set.
  113                          */
  114                         thread_t td;
  115 
  116                         if (lock & MTX_EXLINK) {
  117                                 cpu_pause();
  118                                 ++mtx_collision_count;
  119                                 continue;
  120                         }
  121                         td = curthread;
  122                         /*lock &= ~MTX_EXLINK;*/
  123                         nlock = lock | MTX_EXWANTED | MTX_EXLINK;
  124                         ++td->td_critcount;
  125                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  126                                 /*
  127                                  * Check for early abort
  128                                  */
  129                                 if (link->state == MTX_LINK_ABORTED) {
  130                                         atomic_clear_int(&mtx->mtx_lock,
  131                                                          MTX_EXLINK);
  132                                         --td->td_critcount;
  133                                         error = ENOLCK;
  134                                         if (mtx->mtx_link == NULL) {
  135                                                 atomic_clear_int(&mtx->mtx_lock,
  136                                                                  MTX_EXWANTED);
  137                                         }
  138                                         break;
  139                                 }
  140 
  141                                 /*
  142                                  * Success.  Link in our structure then
  143                                  * release EXLINK and sleep.
  144                                  */
  145                                 link->owner = td;
  146                                 link->state = MTX_LINK_LINKED;
  147                                 if (mtx->mtx_link) {
  148                                         link->next = mtx->mtx_link;
  149                                         link->prev = link->next->prev;
  150                                         link->next->prev = link;
  151                                         link->prev->next = link;
  152                                 } else {
  153                                         link->next = link;
  154                                         link->prev = link;
  155                                         mtx->mtx_link = link;
  156                                 }
  157                                 tsleep_interlock(link, 0);
  158                                 atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
  159                                 --td->td_critcount;
  160 
  161                                 mycpu->gd_cnt.v_lock_name[0] = 'X';
  162                                 strncpy(mycpu->gd_cnt.v_lock_name + 1,
  163                                         ident,
  164                                         sizeof(mycpu->gd_cnt.v_lock_name) - 2);
  165                                 ++mycpu->gd_cnt.v_lock_colls;
  166 
  167                                 error = tsleep(link, flags | PINTERLOCKED,
  168                                                ident, to);
  169                                 ++mtx_contention_count;
  170 
  171                                 /*
  172                                  * Normal unlink, we should own the exclusive
  173                                  * lock now.
  174                                  */
  175                                 if (link->state == MTX_LINK_LINKED)
  176                                         mtx_delete_link(mtx, link);
  177                                 if (link->state == MTX_LINK_ACQUIRED) {
  178                                         KKASSERT(mtx->mtx_owner == link->owner);
  179                                         error = 0;
  180                                         break;
  181                                 }
  182 
  183                                 /*
  184                                  * Aborted lock (mtx_abort_ex called).
  185                                  */
  186                                 if (link->state == MTX_LINK_ABORTED) {
  187                                         error = ENOLCK;
  188                                         break;
  189                                 }
  190 
  191                                 /*
  192                                  * tsleep error, else retry.
  193                                  */
  194                                 if (error)
  195                                         break;
  196                         } else {
  197                                 --td->td_critcount;
  198                         }
  199                 }
  200                 ++mtx_collision_count;
  201         }
  202         return (error);
  203 }
  204 
  205 int
  206 _mtx_lock_ex_link(mtx_t mtx, mtx_link_t link,
  207                   const char *ident, int flags, int to)
  208 {
  209         return(__mtx_lock_ex(mtx, link, ident, flags, to));
  210 }
  211 
  212 int
  213 _mtx_lock_ex(mtx_t mtx, const char *ident, int flags, int to)
  214 {
  215         struct mtx_link link;
  216 
  217         mtx_link_init(&link);
  218         return(__mtx_lock_ex(mtx, &link, ident, flags, to));
  219 }
  220 
  221 int
  222 _mtx_lock_ex_quick(mtx_t mtx, const char *ident)
  223 {
  224         struct mtx_link link;
  225 
  226         mtx_link_init(&link);
  227         return(__mtx_lock_ex(mtx, &link, ident, 0, 0));
  228 }
  229 
  230 /*
  231  * Share-lock a mutex, block until acquired.  Recursion is allowed.
  232  *
  233  * Returns 0 on success, or the tsleep() return code on failure.
  234  * An error can only be returned if PCATCH is specified in the flags.
  235  *
  236  * NOTE: Shared locks get a mass-wakeup so if the tsleep fails we
  237  *       do not have to chain the wakeup().
  238  */
  239 static __inline int
  240 __mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
  241 {
  242         u_int   lock;
  243         u_int   nlock;
  244         int     error;
  245 
  246         for (;;) {
  247                 lock = mtx->mtx_lock;
  248                 if ((lock & MTX_EXCLUSIVE) == 0) {
  249                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  250                         nlock = lock + 1;
  251                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  252                                 error = 0;
  253                                 break;
  254                         }
  255                 } else {
  256                         nlock = lock | MTX_SHWANTED;
  257                         tsleep_interlock(mtx, 0);
  258                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  259 
  260                                 mycpu->gd_cnt.v_lock_name[0] = 'S';
  261                                 strncpy(mycpu->gd_cnt.v_lock_name + 1,
  262                                         ident,
  263                                         sizeof(mycpu->gd_cnt.v_lock_name) - 2);
  264                                 ++mycpu->gd_cnt.v_lock_colls;
  265 
  266                                 error = tsleep(mtx, flags | PINTERLOCKED,
  267                                                ident, to);
  268                                 if (error)
  269                                         break;
  270                                 ++mtx_contention_count;
  271                                 /* retry */
  272                         } else {
  273                                 crit_enter();
  274                                 tsleep_remove(curthread);
  275                                 crit_exit();
  276                         }
  277                 }
  278                 ++mtx_collision_count;
  279         }
  280         return (error);
  281 }
  282 
  283 int
  284 _mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
  285 {
  286         return (__mtx_lock_sh(mtx, ident, flags, to));
  287 }
  288 
  289 int
  290 _mtx_lock_sh_quick(mtx_t mtx, const char *ident)
  291 {
  292         return (__mtx_lock_sh(mtx, ident, 0, 0));
  293 }
  294 
  295 /*
  296  * Get an exclusive spinlock the hard way.
  297  */
  298 void
  299 _mtx_spinlock(mtx_t mtx)
  300 {
  301         u_int   lock;
  302         u_int   nlock;
  303         int     bb = 1;
  304         int     bo;
  305 
  306         for (;;) {
  307                 lock = mtx->mtx_lock;
  308                 if (lock == 0) {
  309                         nlock = MTX_EXCLUSIVE | 1;
  310                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
  311                                 mtx->mtx_owner = curthread;
  312                                 break;
  313                         }
  314                 } else if ((lock & MTX_EXCLUSIVE) &&
  315                            mtx->mtx_owner == curthread) {
  316                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  317                         nlock = lock + 1;
  318                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  319                                 break;
  320                 } else {
  321                         /* MWAIT here */
  322                         if (bb < 1000)
  323                                 ++bb;
  324                         cpu_pause();
  325                         for (bo = 0; bo < bb; ++bo)
  326                                 ;
  327                         ++mtx_contention_count;
  328                 }
  329                 cpu_pause();
  330                 ++mtx_collision_count;
  331         }
  332 }
  333 
  334 /*
  335  * Attempt to acquire a spinlock, if we fail we must undo the
  336  * gd->gd_spinlocks/gd->gd_curthead->td_critcount predisposition.
  337  *
  338  * Returns 0 on success, EAGAIN on failure.
  339  */
  340 int
  341 _mtx_spinlock_try(mtx_t mtx)
  342 {
  343         globaldata_t gd = mycpu;
  344         u_int   lock;
  345         u_int   nlock;
  346         int     res = 0;
  347 
  348         for (;;) {
  349                 lock = mtx->mtx_lock;
  350                 if (lock == 0) {
  351                         nlock = MTX_EXCLUSIVE | 1;
  352                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
  353                                 mtx->mtx_owner = gd->gd_curthread;
  354                                 break;
  355                         }
  356                 } else if ((lock & MTX_EXCLUSIVE) &&
  357                            mtx->mtx_owner == gd->gd_curthread) {
  358                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  359                         nlock = lock + 1;
  360                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  361                                 break;
  362                 } else {
  363                         --gd->gd_spinlocks;
  364                         cpu_ccfence();
  365                         --gd->gd_curthread->td_critcount;
  366                         res = EAGAIN;
  367                         break;
  368                 }
  369                 cpu_pause();
  370                 ++mtx_collision_count;
  371         }
  372         return res;
  373 }
  374 
  375 #if 0
  376 
  377 void
  378 _mtx_spinlock_sh(mtx_t mtx)
  379 {
  380         u_int   lock;
  381         u_int   nlock;
  382         int     bb = 1;
  383         int     bo;
  384 
  385         for (;;) {
  386                 lock = mtx->mtx_lock;
  387                 if ((lock & MTX_EXCLUSIVE) == 0) {
  388                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  389                         nlock = lock + 1;
  390                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  391                                 break;
  392                 } else {
  393                         /* MWAIT here */
  394                         if (bb < 1000)
  395                                 ++bb;
  396                         cpu_pause();
  397                         for (bo = 0; bo < bb; ++bo)
  398                                 ;
  399                         ++mtx_contention_count;
  400                 }
  401                 cpu_pause();
  402                 ++mtx_collision_count;
  403         }
  404 }
  405 
  406 #endif
  407 
  408 int
  409 _mtx_lock_ex_try(mtx_t mtx)
  410 {
  411         u_int   lock;
  412         u_int   nlock;
  413         int     error = 0;
  414 
  415         for (;;) {
  416                 lock = mtx->mtx_lock;
  417                 if (lock == 0) {
  418                         nlock = MTX_EXCLUSIVE | 1;
  419                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
  420                                 mtx->mtx_owner = curthread;
  421                                 break;
  422                         }
  423                 } else if ((lock & MTX_EXCLUSIVE) &&
  424                            mtx->mtx_owner == curthread) {
  425                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  426                         nlock = lock + 1;
  427                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  428                                 break;
  429                 } else {
  430                         error = EAGAIN;
  431                         break;
  432                 }
  433                 cpu_pause();
  434                 ++mtx_collision_count;
  435         }
  436         return (error);
  437 }
  438 
  439 int
  440 _mtx_lock_sh_try(mtx_t mtx)
  441 {
  442         u_int   lock;
  443         u_int   nlock;
  444         int     error = 0;
  445 
  446         for (;;) {
  447                 lock = mtx->mtx_lock;
  448                 if ((lock & MTX_EXCLUSIVE) == 0) {
  449                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  450                         nlock = lock + 1;
  451                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  452                                 break;
  453                 } else {
  454                         error = EAGAIN;
  455                         break;
  456                 }
  457                 cpu_pause();
  458                 ++mtx_collision_count;
  459         }
  460         return (error);
  461 }
  462 
  463 /*
  464  * If the lock is held exclusively it must be owned by the caller.  If the
  465  * lock is already a shared lock this operation is a NOP.  A panic will
  466  * occur if the lock is not held either shared or exclusive.
  467  *
  468  * The exclusive count is converted to a shared count.
  469  */
  470 void
  471 _mtx_downgrade(mtx_t mtx)
  472 {
  473         u_int   lock;
  474         u_int   nlock;
  475 
  476         for (;;) {
  477                 lock = mtx->mtx_lock;
  478                 if ((lock & MTX_EXCLUSIVE) == 0) {
  479                         KKASSERT((lock & MTX_MASK) > 0);
  480                         break;
  481                 }
  482                 KKASSERT(mtx->mtx_owner == curthread);
  483                 nlock = lock & ~(MTX_EXCLUSIVE | MTX_SHWANTED);
  484                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  485                         if (lock & MTX_SHWANTED) {
  486                                 wakeup(mtx);
  487                                 ++mtx_wakeup_count;
  488                         }
  489                         break;
  490                 }
  491                 cpu_pause();
  492                 ++mtx_collision_count;
  493         }
  494 }
  495 
  496 /*
  497  * Upgrade a shared lock to an exclusive lock.  The upgrade will fail if
  498  * the shared lock has a count other then 1.  Optimize the most likely case
  499  * but note that a single cmpset can fail due to WANTED races.
  500  *
  501  * If the lock is held exclusively it must be owned by the caller and
  502  * this function will simply return without doing anything.   A panic will
  503  * occur if the lock is held exclusively by someone other then the caller.
  504  *
  505  * Returns 0 on success, EDEADLK on failure.
  506  */
  507 int
  508 _mtx_upgrade_try(mtx_t mtx)
  509 {
  510         u_int   lock;
  511         u_int   nlock;
  512         int     error = 0;
  513 
  514         for (;;) {
  515                 lock = mtx->mtx_lock;
  516 
  517                 if ((lock & ~MTX_EXWANTED) == 1) {
  518                         nlock = lock | MTX_EXCLUSIVE;
  519                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  520                                 mtx->mtx_owner = curthread;
  521                                 break;
  522                         }
  523                 } else if (lock & MTX_EXCLUSIVE) {
  524                         KKASSERT(mtx->mtx_owner == curthread);
  525                         break;
  526                 } else {
  527                         error = EDEADLK;
  528                         break;
  529                 }
  530                 cpu_pause();
  531                 ++mtx_collision_count;
  532         }
  533         return (error);
  534 }
  535 
  536 /*
  537  * Unlock a lock.  The caller must hold the lock either shared or exclusive.
  538  *
  539  * Any release which makes the lock available when others want an exclusive
  540  * lock causes us to chain the owner to the next exclusive lock instead of
  541  * releasing the lock.
  542  */
  543 void
  544 _mtx_unlock(mtx_t mtx)
  545 {
  546         u_int   lock;
  547         u_int   nlock;
  548 
  549         for (;;) {
  550                 lock = mtx->mtx_lock;
  551                 nlock = lock & ~(MTX_SHWANTED | MTX_EXLINK);
  552 
  553                 if (nlock == 1) {
  554                         /*
  555                          * Last release, shared lock, no exclusive waiters.
  556                          */
  557                         nlock = lock & MTX_EXLINK;
  558                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  559                                 break;
  560                 } else if (nlock == (MTX_EXCLUSIVE | 1)) {
  561                         /*
  562                          * Last release, exclusive lock, no exclusive waiters.
  563                          * Wake up any shared waiters.
  564                          */
  565                         mtx->mtx_owner = NULL;
  566                         nlock = lock & MTX_EXLINK;
  567                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  568                                 if (lock & MTX_SHWANTED) {
  569                                         wakeup(mtx);
  570                                         ++mtx_wakeup_count;
  571                                 }
  572                                 break;
  573                         }
  574                 } else if (nlock == (MTX_EXWANTED | 1)) {
  575                         /*
  576                          * Last release, shared lock, with exclusive
  577                          * waiters.
  578                          *
  579                          * Wait for EXLINK to clear, then acquire it.
  580                          * We could use the cmpset for this but polling
  581                          * is better on the cpu caches.
  582                          *
  583                          * Acquire an exclusive lock leaving the lockcount
  584                          * set to 1, and get EXLINK for access to mtx_link.
  585                          */
  586                         thread_t td;
  587 
  588                         if (lock & MTX_EXLINK) {
  589                                 cpu_pause();
  590                                 ++mtx_collision_count;
  591                                 continue;
  592                         }
  593                         td = curthread;
  594                         /*lock &= ~MTX_EXLINK;*/
  595                         nlock |= MTX_EXLINK | MTX_EXCLUSIVE;
  596                         nlock |= (lock & MTX_SHWANTED);
  597                         ++td->td_critcount;
  598                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  599                                 mtx_chain_link(mtx);
  600                                 --td->td_critcount;
  601                                 break;
  602                         }
  603                         --td->td_critcount;
  604                 } else if (nlock == (MTX_EXCLUSIVE | MTX_EXWANTED | 1)) {
  605                         /*
  606                          * Last release, exclusive lock, with exclusive
  607                          * waiters.
  608                          *
  609                          * leave the exclusive lock intact and the lockcount
  610                          * set to 1, and get EXLINK for access to mtx_link.
  611                          */
  612                         thread_t td;
  613 
  614                         if (lock & MTX_EXLINK) {
  615                                 cpu_pause();
  616                                 ++mtx_collision_count;
  617                                 continue;
  618                         }
  619                         td = curthread;
  620                         /*lock &= ~MTX_EXLINK;*/
  621                         nlock |= MTX_EXLINK;
  622                         nlock |= (lock & MTX_SHWANTED);
  623                         ++td->td_critcount;
  624                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  625                                 mtx_chain_link(mtx);
  626                                 --td->td_critcount;
  627                                 break;
  628                         }
  629                         --td->td_critcount;
  630                 } else {
  631                         /*
  632                          * Not the last release (shared or exclusive)
  633                          */
  634                         nlock = lock - 1;
  635                         KKASSERT((nlock & MTX_MASK) != MTX_MASK);
  636                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  637                                 break;
  638                 }
  639                 cpu_pause();
  640                 ++mtx_collision_count;
  641         }
  642 }
  643 
  644 /*
  645  * Chain mtx_chain_link.  Called with the lock held exclusively with a
  646  * single ref count, and also with MTX_EXLINK held.
  647  */
  648 static void
  649 mtx_chain_link(mtx_t mtx)
  650 {
  651         mtx_link_t link;
  652         u_int   lock;
  653         u_int   nlock;
  654         u_int   clock;  /* bits we own and want to clear */
  655 
  656         /*
  657          * Chain the exclusive lock to the next link.  The caller cleared
  658          * SHWANTED so if there is no link we have to wake up any shared
  659          * waiters.
  660          */
  661         clock = MTX_EXLINK;
  662         if ((link = mtx->mtx_link) != NULL) {
  663                 KKASSERT(link->state == MTX_LINK_LINKED);
  664                 if (link->next == link) {
  665                         mtx->mtx_link = NULL;
  666                         clock |= MTX_EXWANTED;
  667                 } else {
  668                         mtx->mtx_link = link->next;
  669                         link->next->prev = link->prev;
  670                         link->prev->next = link->next;
  671                 }
  672                 link->state = MTX_LINK_ACQUIRED;
  673                 mtx->mtx_owner = link->owner;
  674         } else {
  675                 /*
  676                  * Chain was empty, release the exclusive lock's last count
  677                  * as well the bits shown.
  678                  */
  679                 clock |= MTX_EXCLUSIVE | MTX_EXWANTED | MTX_SHWANTED | 1;
  680         }
  681 
  682         /*
  683          * We have to uset cmpset here to deal with MTX_SHWANTED.  If
  684          * we just clear the bits we can miss a wakeup or, worse,
  685          * leave mtx_lock unlocked with MTX_SHWANTED still set.
  686          */
  687         for (;;) {
  688                 lock = mtx->mtx_lock;
  689                 nlock = lock & ~clock;
  690 
  691                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
  692                         if (link) {
  693                                 /*
  694                                  * Wakeup new exclusive holder.  Leave
  695                                  * SHWANTED intact.
  696                                  */
  697                                 wakeup(link);
  698                         } else if (lock & MTX_SHWANTED) {
  699                                 /*
  700                                  * Signal any shared waiters (and we also
  701                                  * clear SHWANTED).
  702                                  */
  703                                 mtx->mtx_owner = NULL;
  704                                 wakeup(mtx);
  705                                 ++mtx_wakeup_count;
  706                         }
  707                         break;
  708                 }
  709                 cpu_pause();
  710                 ++mtx_collision_count;
  711         }
  712 }
  713 
  714 /*
  715  * Delete a link structure after tsleep has failed.  This code is not
  716  * in the critical path as most exclusive waits are chained.
  717  */
  718 static
  719 void
  720 mtx_delete_link(mtx_t mtx, mtx_link_t link)
  721 {
  722         thread_t td = curthread;
  723         u_int   lock;
  724         u_int   nlock;
  725 
  726         /*
  727          * Acquire MTX_EXLINK.
  728          *
  729          * Do not use cmpxchg to wait for EXLINK to clear as this might
  730          * result in too much cpu cache traffic.
  731          */
  732         ++td->td_critcount;
  733         for (;;) {
  734                 lock = mtx->mtx_lock;
  735                 if (lock & MTX_EXLINK) {
  736                         cpu_pause();
  737                         ++mtx_collision_count;
  738                         continue;
  739                 }
  740                 /* lock &= ~MTX_EXLINK; */
  741                 nlock = lock | MTX_EXLINK;
  742                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  743                         break;
  744                 cpu_pause();
  745                 ++mtx_collision_count;
  746         }
  747 
  748         /*
  749          * Delete the link and release EXLINK.
  750          */
  751         if (link->state == MTX_LINK_LINKED) {
  752                 if (link->next == link) {
  753                         mtx->mtx_link = NULL;
  754                 } else {
  755                         mtx->mtx_link = link->next;
  756                         link->next->prev = link->prev;
  757                         link->prev->next = link->next;
  758                 }
  759                 link->state = MTX_LINK_IDLE;
  760         }
  761         atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
  762         --td->td_critcount;
  763 }
  764 
  765 /*
  766  * Abort a mutex locking operation, causing mtx_lock_ex_link() to
  767  * return ENOLCK.  This may be called at any time after the
  768  * mtx_link is initialized, including both before and after the call
  769  * to mtx_lock_ex_link().
  770  */
  771 void
  772 mtx_abort_ex_link(mtx_t mtx, mtx_link_t link)
  773 {
  774         thread_t td = curthread;
  775         u_int   lock;
  776         u_int   nlock;
  777 
  778         /*
  779          * Acquire MTX_EXLINK
  780          */
  781         ++td->td_critcount;
  782         for (;;) {
  783                 lock = mtx->mtx_lock;
  784                 if (lock & MTX_EXLINK) {
  785                         cpu_pause();
  786                         ++mtx_collision_count;
  787                         continue;
  788                 }
  789                 /* lock &= ~MTX_EXLINK; */
  790                 nlock = lock | MTX_EXLINK;
  791                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
  792                         break;
  793                 cpu_pause();
  794                 ++mtx_collision_count;
  795         }
  796 
  797         /*
  798          * Do the abort
  799          */
  800         switch(link->state) {
  801         case MTX_LINK_IDLE:
  802                 /*
  803                  * Link not started yet
  804                  */
  805                 link->state = MTX_LINK_ABORTED;
  806                 break;
  807         case MTX_LINK_LINKED:
  808                 /*
  809                  * de-link, mark aborted, and wakeup the thread.
  810                  */
  811                 if (link->next == link) {
  812                         mtx->mtx_link = NULL;
  813                 } else {
  814                         mtx->mtx_link = link->next;
  815                         link->next->prev = link->prev;
  816                         link->prev->next = link->next;
  817                 }
  818                 link->state = MTX_LINK_ABORTED;
  819                 wakeup(link);
  820                 break;
  821         case MTX_LINK_ACQUIRED:
  822                 /*
  823                  * Too late, the lock was acquired.  Let it complete.
  824                  */
  825                 break;
  826         default:
  827                 /*
  828                  * link already aborted, do nothing.
  829                  */
  830                 break;
  831         }
  832         atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
  833         --td->td_critcount;
  834 }
Cache object: c8e05105f1eacd8ad2c62386295ffc72
[ 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.
FreeBSD/Linux Kernel Cross Reference sys/kern/kern_mutex.c

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