sys/kern/kern_mutex.c

   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 #include <sys/mutex.h>
  53
  54 #include <machine/cpufunc.h>
  55
  56 #include <sys/thread2.h>
  57 #include <sys/mutex2.h>
  58
  59 static __int64_t mtx_contention_count;
  60 static __int64_t mtx_collision_count;
  61 static __int64_t mtx_wakeup_count;
  62
  63 SYSCTL_QUAD(_kern, OID_AUTO, mtx_contention_count, CTLFLAG_RW,
  64             &mtx_contention_count, 0, "");
  65 SYSCTL_QUAD(_kern, OID_AUTO, mtx_collision_count, CTLFLAG_RW,
  66             &mtx_collision_count, 0, "");
  67 SYSCTL_QUAD(_kern, OID_AUTO, mtx_wakeup_count, CTLFLAG_RW,
  68             &mtx_wakeup_count, 0, "");
  69
  70 /*
  71  * Exclusive-lock a mutex, block until acquired.  Recursion is allowed.
  72  */
  73 void
  74 _mtx_lock_ex(mtx_t mtx, const char *ident, int flags)
  75 {
  76         u_int   lock;
  77         u_int   nlock;
  78
  79         for (;;) {
  80                 lock = mtx->mtx_lock;
  81                 if (lock == 0) {
  82                         nlock = MTX_EXCLUSIVE | 1;
  83                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
  84                                 /* mtx_owner set by caller */
  85                                 return;
  86                         }
  87                 } else if ((lock & MTX_EXCLUSIVE) &&
  88                            mtx->mtx_owner == curthread) {
  89                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  90                         nlock = (lock + 1);
  91                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock))
  92                                 return;
  93                 } else {
  94                         nlock = lock | MTX_EXWANTED;
  95                         tsleep_interlock(mtx, 0);
  96                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
  97                                 ++mtx_contention_count;
  98                                 tsleep(mtx, flags, ident, 0);
  99                         }
 100                 }
 101                 ++mtx_collision_count;
 102         }
 103 }
 104
 105 /*
 106  * Share-lock a mutex, block until acquired.  Recursion is allowed.
 107  */
 108 void
 109 _mtx_lock_sh(mtx_t mtx, const char *ident, int flags)
 110 {
 111         u_int   lock;
 112         u_int   nlock;
 113
 114         for (;;) {
 115                 lock = mtx->mtx_lock;
 116                 if ((lock & MTX_EXCLUSIVE) == 0) {
 117                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 118                         nlock = lock + 1;
 119                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 120                                 return;
 121                 } else {
 122                         nlock = lock | MTX_SHWANTED;
 123                         tsleep_interlock(mtx, 0);
 124                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 125                                 ++mtx_contention_count;
 126                                 tsleep(mtx, flags, ident, 0);
 127                         }
 128                 }
 129                 ++mtx_collision_count;
 130         }
 131 }
 132
 133 void
 134 _mtx_spinlock_ex(mtx_t mtx)
 135 {
 136         u_int   lock;
 137         u_int   nlock;
 138         int     bb = 1;
 139         int     bo;
 140
 141         for (;;) {
 142                 lock = mtx->mtx_lock;
 143                 if (lock == 0) {
 144                         nlock = MTX_EXCLUSIVE | 1;
 145                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 146                                 /* mtx_owner set by caller */
 147                                 return;
 148                         }
 149                 } else if ((lock & MTX_EXCLUSIVE) &&
 150                            mtx->mtx_owner == curthread) {
 151                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 152                         nlock = (lock + 1);
 153                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock))
 154                                 return;
 155                 } else {
 156                         /* MWAIT here */
 157                         if (bb < 1000)
 158                                 ++bb;
 159                         cpu_pause();
 160                         for (bo = 0; bo < bb; ++bo)
 161                                 ;
 162                         ++mtx_contention_count;
 163                 }
 164                 ++mtx_collision_count;
 165         }
 166 }
 167
 168 void
 169 _mtx_spinlock_sh(mtx_t mtx)
 170 {
 171         u_int   lock;
 172         u_int   nlock;
 173         int     bb = 1;
 174         int     bo;
 175
 176         for (;;) {
 177                 lock = mtx->mtx_lock;
 178                 if ((lock & MTX_EXCLUSIVE) == 0) {
 179                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 180                         nlock = lock + 1;
 181                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 182                                 return;
 183                 } else {
 184                         /* MWAIT here */
 185                         if (bb < 1000)
 186                                 ++bb;
 187                         cpu_pause();
 188                         for (bo = 0; bo < bb; ++bo)
 189                                 ;
 190                         ++mtx_contention_count;
 191                 }
 192                 ++mtx_collision_count;
 193         }
 194 }
 195
 196 int
 197 _mtx_lock_ex_try(mtx_t mtx)
 198 {
 199         u_int   lock;
 200         u_int   nlock;
 201         int     error = 0;
 202
 203         for (;;) {
 204                 lock = mtx->mtx_lock;
 205                 if (lock == 0) {
 206                         nlock = MTX_EXCLUSIVE | 1;
 207                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 208                                 /* mtx_owner set by caller */
 209                                 break;
 210                         }
 211                 } else if ((lock & MTX_EXCLUSIVE) &&
 212                            mtx->mtx_owner == curthread) {
 213                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 214                         nlock = (lock + 1);
 215                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock))
 216                                 break;
 217                 } else {
 218                         error = EAGAIN;
 219                         break;
 220                 }
 221                 ++mtx_collision_count;
 222         }
 223         return (error);
 224 }
 225
 226 int
 227 _mtx_lock_sh_try(mtx_t mtx)
 228 {
 229         u_int   lock;
 230         u_int   nlock;
 231         int     error = 0;
 232
 233         for (;;) {
 234                 lock = mtx->mtx_lock;
 235                 if ((lock & MTX_EXCLUSIVE) == 0) {
 236                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 237                         nlock = lock + 1;
 238                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 239                                 break;
 240                 } else {
 241                         error = EAGAIN;
 242                         break;
 243                 }
 244                 ++mtx_collision_count;
 245         }
 246         return (error);
 247 }
 248
 249 /*
 250  * If the lock is held exclusively it must be owned by the caller.  If the
 251  * lock is already a shared lock this operation is a NOP.  A panic will
 252  * occur if the lock is not held either shared or exclusive.
 253  *
 254  * The exclusive count is converted to a shared count.
 255  */
 256 void
 257 _mtx_downgrade(mtx_t mtx)
 258 {
 259         u_int   lock;
 260         u_int   nlock;
 261
 262         for (;;) {
 263                 lock = mtx->mtx_lock;
 264                 if ((lock & MTX_EXCLUSIVE) == 0) {
 265                         KKASSERT((lock & MTX_MASK) > 0);
 266                         break;
 267                 }
 268                 KKASSERT(mtx->mtx_owner == curthread);
 269                 nlock = lock & ~(MTX_EXCLUSIVE | MTX_SHWANTED);
 270                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 271                         if (lock & MTX_SHWANTED) {
 272                                 ++mtx_wakeup_count;
 273                                 wakeup(mtx);
 274                         }
 275                         break;
 276                 }
 277                 ++mtx_collision_count;
 278         }
 279 }
 280
 281 /*
 282  * Upgrade a shared lock to an exclusive lock.  The upgrade will fail if
 283  * the shared lock has a count other then 1.  Optimize the most likely case
 284  * but note that a single cmpset can fail due to WANTED races.
 285  *
 286  * If the lock is held exclusively it must be owned by the caller and
 287  * this function will simply return without doing anything.   A panic will
 288  * occur if the lock is held exclusively by someone other then the caller.
 289  *
 290  * Returns 0 on success, EDEADLK on failure.
 291  */
 292 int
 293 _mtx_upgrade_try(mtx_t mtx)
 294 {
 295         u_int   lock;
 296         u_int   nlock;
 297         int     error = 0;
 298
 299         for (;;) {
 300                 lock = mtx->mtx_lock;
 301
 302                 if ((lock & ~MTX_EXWANTED) == 1) {
 303                         nlock = lock | MTX_EXCLUSIVE;
 304                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 305                                 mtx->mtx_owner = curthread;
 306                                 break;
 307                         }
 308                 } else if (lock & MTX_EXCLUSIVE) {
 309                         KKASSERT(mtx->mtx_owner == curthread);
 310                         break;
 311                 } else {
 312                         error = EDEADLK;
 313                         break;
 314                 }
 315                 ++mtx_collision_count;
 316         }
 317         return (error);
 318 }
 319
 320 /*
 321  * Unlock a lock.  The caller must hold the lock either shared or exclusive.
 322  */
 323 void
 324 _mtx_unlock(mtx_t mtx)
 325 {
 326         u_int   lock;
 327         u_int   nlock;
 328
 329         for (;;) {
 330                 lock = mtx->mtx_lock;
 331                 nlock = (lock & (MTX_EXCLUSIVE | MTX_MASK)) - 1;
 332                 if (nlock == 0) {
 333                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0)) {
 334                                 if (lock & (MTX_SHWANTED | MTX_EXWANTED)) {
 335                                         ++mtx_wakeup_count;
 336                                         wakeup(mtx);
 337                                 }
 338                         }
 339                 } else if (nlock == MTX_EXCLUSIVE) {
 340                         mtx->mtx_owner = NULL;
 341                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0)) {
 342                                 if (lock & (MTX_SHWANTED | MTX_EXWANTED)) {
 343                                         ++mtx_wakeup_count;
 344                                         wakeup(mtx);
 345                                 }
 346                                 break;
 347                         }
 348                 } else {
 349                         nlock = lock - 1;
 350                         KKASSERT((nlock & MTX_MASK) != MTX_MASK);
 351                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 352                                 break;
 353                 }
 354                 ++mtx_collision_count;
 355         }
 356 }