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