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  * Returns 0 on success, or the tsleep() return code on failure.
  74  * An error can only be returned if PCATCH is specified in the flags.
  75  */
  76 static __inline int
  77 __mtx_lock_ex(mtx_t mtx, const char *ident, int flags, int to)
  78 {
  79         u_int   lock;
  80         u_int   nlock;
  81         int     error;
  82
  83         for (;;) {
  84                 lock = mtx->mtx_lock;
  85                 if (lock == 0) {
  86                         nlock = MTX_EXCLUSIVE | 1;
  87                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
  88                                 mtx->mtx_owner = curthread;
  89                                 error = 0;
  90                                 break;
  91                         }
  92                 } else if ((lock & MTX_EXCLUSIVE) &&
  93                            mtx->mtx_owner == curthread) {
  94                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
  95                         nlock = (lock + 1);
  96                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
  97                                 error = 0;
  98                                 break;
  99                         }
 100                 } else {
 101                         nlock = lock | MTX_EXWANTED;
 102                         tsleep_interlock(&mtx->mtx_owner, 0);
 103                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 104                                 error = tsleep(&mtx->mtx_owner, flags,
 105                                                ident, to);
 106                                 ++mtx_contention_count;
 107                                 if (error) {
 108                                         ++mtx_wakeup_count;
 109                                         wakeup_one(&mtx->mtx_owner);
 110                                         break;
 111                                 }
 112                         } else {
 113                                 tsleep_remove(curthread);
 114                         }
 115                 }
 116                 ++mtx_collision_count;
 117         }
 118         return (error);
 119 }
 120
 121 int
 122 _mtx_lock_ex(mtx_t mtx, const char *ident, int flags, int to)
 123 {
 124         return(__mtx_lock_ex(mtx, ident, flags, to));
 125 }
 126
 127 int
 128 _mtx_lock_ex_quick(mtx_t mtx, const char *ident)
 129 {
 130         return(__mtx_lock_ex(mtx, ident, 0, 0));
 131 }
 132
 133 /*
 134  * Share-lock a mutex, block until acquired.  Recursion is allowed.
 135  *
 136  * Returns 0 on success, or the tsleep() return code on failure.
 137  * An error can only be returned if PCATCH is specified in the flags.
 138  */
 139 static __inline int
 140 __mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
 141 {
 142         u_int   lock;
 143         u_int   nlock;
 144         int     error;
 145
 146         for (;;) {
 147                 lock = mtx->mtx_lock;
 148                 if ((lock & MTX_EXCLUSIVE) == 0) {
 149                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 150                         nlock = lock + 1;
 151                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 152                                 error = 0;
 153                                 break;
 154                         }
 155                 } else {
 156                         nlock = lock | MTX_SHWANTED;
 157                         tsleep_interlock(mtx, 0);
 158                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 159                                 error = tsleep(mtx, flags, ident, to);
 160                                 if (error)
 161                                         break;
 162                                 ++mtx_contention_count;
 163                         } else {
 164                                 tsleep_remove(curthread);
 165                         }
 166                 }
 167                 ++mtx_collision_count;
 168         }
 169         return (error);
 170 }
 171
 172 int
 173 _mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
 174 {
 175         return (__mtx_lock_sh(mtx, ident, flags, to));
 176 }
 177
 178 int
 179 _mtx_lock_sh_quick(mtx_t mtx, const char *ident)
 180 {
 181         return (__mtx_lock_sh(mtx, ident, 0, 0));
 182 }
 183
 184 void
 185 _mtx_spinlock_ex(mtx_t mtx)
 186 {
 187         u_int   lock;
 188         u_int   nlock;
 189         int     bb = 1;
 190         int     bo;
 191
 192         for (;;) {
 193                 lock = mtx->mtx_lock;
 194                 if (lock == 0) {
 195                         nlock = MTX_EXCLUSIVE | 1;
 196                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 197                                 /* mtx_owner set by caller */
 198                                 return;
 199                         }
 200                 } else if ((lock & MTX_EXCLUSIVE) &&
 201                            mtx->mtx_owner == curthread) {
 202                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 203                         nlock = (lock + 1);
 204                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock))
 205                                 return;
 206                 } else {
 207                         /* MWAIT here */
 208                         if (bb < 1000)
 209                                 ++bb;
 210                         cpu_pause();
 211                         for (bo = 0; bo < bb; ++bo)
 212                                 ;
 213                         ++mtx_contention_count;
 214                 }
 215                 ++mtx_collision_count;
 216         }
 217 }
 218
 219 void
 220 _mtx_spinlock_sh(mtx_t mtx)
 221 {
 222         u_int   lock;
 223         u_int   nlock;
 224         int     bb = 1;
 225         int     bo;
 226
 227         for (;;) {
 228                 lock = mtx->mtx_lock;
 229                 if ((lock & MTX_EXCLUSIVE) == 0) {
 230                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 231                         nlock = lock + 1;
 232                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 233                                 return;
 234                 } else {
 235                         /* MWAIT here */
 236                         if (bb < 1000)
 237                                 ++bb;
 238                         cpu_pause();
 239                         for (bo = 0; bo < bb; ++bo)
 240                                 ;
 241                         ++mtx_contention_count;
 242                 }
 243                 ++mtx_collision_count;
 244         }
 245 }
 246
 247 int
 248 _mtx_lock_ex_try(mtx_t mtx)
 249 {
 250         u_int   lock;
 251         u_int   nlock;
 252         int     error = 0;
 253
 254         for (;;) {
 255                 lock = mtx->mtx_lock;
 256                 if (lock == 0) {
 257                         nlock = MTX_EXCLUSIVE | 1;
 258                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
 259                                 /* mtx_owner set by caller */
 260                                 break;
 261                         }
 262                 } else if ((lock & MTX_EXCLUSIVE) &&
 263                            mtx->mtx_owner == curthread) {
 264                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 265                         nlock = (lock + 1);
 266                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock))
 267                                 break;
 268                 } else {
 269                         error = EAGAIN;
 270                         break;
 271                 }
 272                 ++mtx_collision_count;
 273         }
 274         return (error);
 275 }
 276
 277 int
 278 _mtx_lock_sh_try(mtx_t mtx)
 279 {
 280         u_int   lock;
 281         u_int   nlock;
 282         int     error = 0;
 283
 284         for (;;) {
 285                 lock = mtx->mtx_lock;
 286                 if ((lock & MTX_EXCLUSIVE) == 0) {
 287                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
 288                         nlock = lock + 1;
 289                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 290                                 break;
 291                 } else {
 292                         error = EAGAIN;
 293                         break;
 294                 }
 295                 ++mtx_collision_count;
 296         }
 297         return (error);
 298 }
 299
 300 /*
 301  * If the lock is held exclusively it must be owned by the caller.  If the
 302  * lock is already a shared lock this operation is a NOP.  A panic will
 303  * occur if the lock is not held either shared or exclusive.
 304  *
 305  * The exclusive count is converted to a shared count.
 306  */
 307 void
 308 _mtx_downgrade(mtx_t mtx)
 309 {
 310         u_int   lock;
 311         u_int   nlock;
 312
 313         for (;;) {
 314                 lock = mtx->mtx_lock;
 315                 if ((lock & MTX_EXCLUSIVE) == 0) {
 316                         KKASSERT((lock & MTX_MASK) > 0);
 317                         break;
 318                 }
 319                 KKASSERT(mtx->mtx_owner == curthread);
 320                 nlock = lock & ~(MTX_EXCLUSIVE | MTX_SHWANTED);
 321                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 322                         if (lock & MTX_SHWANTED) {
 323                                 wakeup(mtx);
 324                                 ++mtx_wakeup_count;
 325                         }
 326                         break;
 327                 }
 328                 ++mtx_collision_count;
 329         }
 330 }
 331
 332 /*
 333  * Upgrade a shared lock to an exclusive lock.  The upgrade will fail if
 334  * the shared lock has a count other then 1.  Optimize the most likely case
 335  * but note that a single cmpset can fail due to WANTED races.
 336  *
 337  * If the lock is held exclusively it must be owned by the caller and
 338  * this function will simply return without doing anything.   A panic will
 339  * occur if the lock is held exclusively by someone other then the caller.
 340  *
 341  * Returns 0 on success, EDEADLK on failure.
 342  */
 343 int
 344 _mtx_upgrade_try(mtx_t mtx)
 345 {
 346         u_int   lock;
 347         u_int   nlock;
 348         int     error = 0;
 349
 350         for (;;) {
 351                 lock = mtx->mtx_lock;
 352
 353                 if ((lock & ~MTX_EXWANTED) == 1) {
 354                         nlock = lock | MTX_EXCLUSIVE;
 355                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
 356                                 mtx->mtx_owner = curthread;
 357                                 break;
 358                         }
 359                 } else if (lock & MTX_EXCLUSIVE) {
 360                         KKASSERT(mtx->mtx_owner == curthread);
 361                         break;
 362                 } else {
 363                         error = EDEADLK;
 364                         break;
 365                 }
 366                 ++mtx_collision_count;
 367         }
 368         return (error);
 369 }
 370
 371 /*
 372  * Unlock a lock.  The caller must hold the lock either shared or exclusive.
 373  */
 374 void
 375 _mtx_unlock(mtx_t mtx)
 376 {
 377         u_int   lock;
 378         u_int   nlock;
 379
 380         for (;;) {
 381                 lock = mtx->mtx_lock;
 382                 nlock = (lock & (MTX_EXCLUSIVE | MTX_MASK)) - 1;
 383                 if (nlock == 0) {
 384                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0)) {
 385                                 if (lock & MTX_SHWANTED) {
 386                                         wakeup(mtx);
 387                                         ++mtx_wakeup_count;
 388                                 }
 389                                 if (lock & MTX_EXWANTED) {
 390                                         wakeup_one(&mtx->mtx_owner);
 391                                         ++mtx_wakeup_count;
 392                                 }
 393                         }
 394                 } else if (nlock == MTX_EXCLUSIVE) {
 395                         mtx->mtx_owner = NULL;
 396                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0)) {
 397                                 if (lock & MTX_SHWANTED) {
 398                                         wakeup(mtx);
 399                                         ++mtx_wakeup_count;
 400                                 }
 401                                 if (lock & MTX_EXWANTED) {
 402                                         wakeup_one(&mtx->mtx_owner);
 403                                         ++mtx_wakeup_count;
 404                                 }
 405                                 break;
 406                         }
 407                 } else {
 408                         nlock = lock - 1;
 409                         KKASSERT((nlock & MTX_MASK) != MTX_MASK);
 410                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
 411                                 break;
 412                 }
 413                 ++mtx_collision_count;
 414         }
 415 }