sys/kern/kern_mutex.c

   1 /*-
   2  * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  * 3. Berkeley Software Design Inc's name may not be used to endorse or
  13  *    promote products derived from this software without specific prior
  14  *    written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  *
  28  *      from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
  29  *      and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
  30  */
  31
  32 /*
  33  * Machine independent bits of mutex implementation.
  34  */
  35
  36 #include <sys/cdefs.h>
  37 __FBSDID("$FreeBSD$");
  38
  39 #include "opt_adaptive_mutexes.h"
  40 #include "opt_ddb.h"
  41 #include "opt_mprof.h"
  42 #include "opt_mutex_wake_all.h"
  43 #include "opt_sched.h"
  44
  45 #include <sys/param.h>
  46 #include <sys/systm.h>
  47 #include <sys/bus.h>
  48 #include <sys/kdb.h>
  49 #include <sys/kernel.h>
  50 #include <sys/ktr.h>
  51 #include <sys/lock.h>
  52 #include <sys/malloc.h>
  53 #include <sys/mutex.h>
  54 #include <sys/proc.h>
  55 #include <sys/resourcevar.h>
  56 #include <sys/sched.h>
  57 #include <sys/sbuf.h>
  58 #include <sys/sysctl.h>
  59 #include <sys/turnstile.h>
  60 #include <sys/vmmeter.h>
  61
  62 #include <machine/atomic.h>
  63 #include <machine/bus.h>
  64 #include <machine/clock.h>
  65 #include <machine/cpu.h>
  66
  67 #include <ddb/ddb.h>
  68
  69 #include <vm/vm.h>
  70 #include <vm/vm_extern.h>
  71
  72 /*
  73  * Force MUTEX_WAKE_ALL for now.
  74  * single thread wakeup needs fixes to avoid race conditions with
  75  * priority inheritance.
  76  */
  77 #ifndef MUTEX_WAKE_ALL
  78 #define MUTEX_WAKE_ALL
  79 #endif
  80
  81 /*
  82  * Internal utility macros.
  83  */
  84 #define mtx_unowned(m)  ((m)->mtx_lock == MTX_UNOWNED)
  85
  86 #define mtx_owner(m)    (mtx_unowned((m)) ? NULL \
  87         : (struct thread *)((m)->mtx_lock & MTX_FLAGMASK))
  88
  89 /*
  90  * Lock classes for sleep and spin mutexes.
  91  */
  92 struct lock_class lock_class_mtx_sleep = {
  93         "sleep mutex",
  94         LC_SLEEPLOCK | LC_RECURSABLE
  95 };
  96 struct lock_class lock_class_mtx_spin = {
  97         "spin mutex",
  98         LC_SPINLOCK | LC_RECURSABLE
  99 };
 100
 101 /*
 102  * System-wide mutexes
 103  */
 104 struct mtx sched_lock;
 105 struct mtx Giant;
 106
 107 #ifdef MUTEX_PROFILING
 108 SYSCTL_NODE(_debug, OID_AUTO, mutex, CTLFLAG_RD, NULL, "mutex debugging");
 109 SYSCTL_NODE(_debug_mutex, OID_AUTO, prof, CTLFLAG_RD, NULL, "mutex profiling");
 110 static int mutex_prof_enable = 0;
 111 SYSCTL_INT(_debug_mutex_prof, OID_AUTO, enable, CTLFLAG_RW,
 112     &mutex_prof_enable, 0, "Enable tracing of mutex holdtime");
 113
 114 struct mutex_prof {
 115         const char      *name;
 116         const char      *file;
 117         int             line;
 118         uintmax_t       cnt_max;
 119         uintmax_t       cnt_tot;
 120         uintmax_t       cnt_cur;
 121         uintmax_t       cnt_contest_holding;
 122         uintmax_t       cnt_contest_locking;
 123         struct mutex_prof *next;
 124 };
 125
 126 /*
 127  * mprof_buf is a static pool of profiling records to avoid possible
 128  * reentrance of the memory allocation functions.
 129  *
 130  * Note: NUM_MPROF_BUFFERS must be smaller than MPROF_HASH_SIZE.
 131  */
 132 #ifdef MPROF_BUFFERS
 133 #define NUM_MPROF_BUFFERS       MPROF_BUFFERS
 134 #else
 135 #define NUM_MPROF_BUFFERS       1000
 136 #endif
 137 static struct mutex_prof mprof_buf[NUM_MPROF_BUFFERS];
 138 static int first_free_mprof_buf;
 139 #ifndef MPROF_HASH_SIZE
 140 #define MPROF_HASH_SIZE         1009
 141 #endif
 142 #if NUM_MPROF_BUFFERS >= MPROF_HASH_SIZE
 143 #error MPROF_BUFFERS must be larger than MPROF_HASH_SIZE
 144 #endif
 145 static struct mutex_prof *mprof_hash[MPROF_HASH_SIZE];
 146 /* SWAG: sbuf size = avg stat. line size * number of locks */
 147 #define MPROF_SBUF_SIZE         256 * 400
 148
 149 static int mutex_prof_acquisitions;
 150 SYSCTL_INT(_debug_mutex_prof, OID_AUTO, acquisitions, CTLFLAG_RD,
 151     &mutex_prof_acquisitions, 0, "Number of mutex acquistions recorded");
 152 static int mutex_prof_records;
 153 SYSCTL_INT(_debug_mutex_prof, OID_AUTO, records, CTLFLAG_RD,
 154     &mutex_prof_records, 0, "Number of profiling records");
 155 static int mutex_prof_maxrecords = NUM_MPROF_BUFFERS;
 156 SYSCTL_INT(_debug_mutex_prof, OID_AUTO, maxrecords, CTLFLAG_RD,
 157     &mutex_prof_maxrecords, 0, "Maximum number of profiling records");
 158 static int mutex_prof_rejected;
 159 SYSCTL_INT(_debug_mutex_prof, OID_AUTO, rejected, CTLFLAG_RD,
 160     &mutex_prof_rejected, 0, "Number of rejected profiling records");
 161 static int mutex_prof_hashsize = MPROF_HASH_SIZE;
 162 SYSCTL_INT(_debug_mutex_prof, OID_AUTO, hashsize, CTLFLAG_RD,
 163     &mutex_prof_hashsize, 0, "Hash size");
 164 static int mutex_prof_collisions = 0;
 165 SYSCTL_INT(_debug_mutex_prof, OID_AUTO, collisions, CTLFLAG_RD,
 166     &mutex_prof_collisions, 0, "Number of hash collisions");
 167
 168 /*
 169  * mprof_mtx protects the profiling buffers and the hash.
 170  */
 171 static struct mtx mprof_mtx;
 172 MTX_SYSINIT(mprof, &mprof_mtx, "mutex profiling lock", MTX_SPIN | MTX_QUIET);
 173
 174 static u_int64_t
 175 nanoseconds(void)
 176 {
 177         struct timespec tv;
 178
 179         nanotime(&tv);
 180         return (tv.tv_sec * (u_int64_t)1000000000 + tv.tv_nsec);
 181 }
 182
 183 static int
 184 dump_mutex_prof_stats(SYSCTL_HANDLER_ARGS)
 185 {
 186         struct sbuf *sb;
 187         int error, i;
 188         static int multiplier = 1;
 189
 190         if (first_free_mprof_buf == 0)
 191                 return (SYSCTL_OUT(req, "No locking recorded",
 192                     sizeof("No locking recorded")));
 193
 194 retry_sbufops:
 195         sb = sbuf_new(NULL, NULL, MPROF_SBUF_SIZE * multiplier, SBUF_FIXEDLEN);
 196         sbuf_printf(sb, "\n%6s %12s %11s %5s %12s %12s %s\n",
 197             "max", "total", "count", "avg", "cnt_hold", "cnt_lock", "name");
 198         /*
 199          * XXX this spinlock seems to be by far the largest perpetrator
 200          * of spinlock latency (1.6 msec on an Athlon1600 was recorded
 201          * even before I pessimized it further by moving the average
 202          * computation here).
 203          */
 204         mtx_lock_spin(&mprof_mtx);
 205         for (i = 0; i < first_free_mprof_buf; ++i) {
 206                 sbuf_printf(sb, "%6ju %12ju %11ju %5ju %12ju %12ju %s:%d (%s)\n",
 207                     mprof_buf[i].cnt_max / 1000,
 208                     mprof_buf[i].cnt_tot / 1000,
 209                     mprof_buf[i].cnt_cur,
 210                     mprof_buf[i].cnt_cur == 0 ? (uintmax_t)0 :
 211                         mprof_buf[i].cnt_tot / (mprof_buf[i].cnt_cur * 1000),
 212                     mprof_buf[i].cnt_contest_holding,
 213                     mprof_buf[i].cnt_contest_locking,
 214                     mprof_buf[i].file, mprof_buf[i].line, mprof_buf[i].name);
 215                 if (sbuf_overflowed(sb)) {
 216                         mtx_unlock_spin(&mprof_mtx);
 217                         sbuf_delete(sb);
 218                         multiplier++;
 219                         goto retry_sbufops;
 220                 }
 221         }
 222         mtx_unlock_spin(&mprof_mtx);
 223         sbuf_finish(sb);
 224         error = SYSCTL_OUT(req, sbuf_data(sb), sbuf_len(sb) + 1);
 225         sbuf_delete(sb);
 226         return (error);
 227 }
 228 SYSCTL_PROC(_debug_mutex_prof, OID_AUTO, stats, CTLTYPE_STRING | CTLFLAG_RD,
 229     NULL, 0, dump_mutex_prof_stats, "A", "Mutex profiling statistics");
 230
 231 static int
 232 reset_mutex_prof_stats(SYSCTL_HANDLER_ARGS)
 233 {
 234         int error, v;
 235
 236         if (first_free_mprof_buf == 0)
 237                 return (0);
 238
 239         v = 0;
 240         error = sysctl_handle_int(oidp, &v, 0, req);
 241         if (error)
 242                 return (error);
 243         if (req->newptr == NULL)
 244                 return (error);
 245         if (v == 0)
 246                 return (0);
 247
 248         mtx_lock_spin(&mprof_mtx);
 249         bzero(mprof_buf, sizeof(*mprof_buf) * first_free_mprof_buf);
 250         bzero(mprof_hash, sizeof(struct mtx *) * MPROF_HASH_SIZE);
 251         first_free_mprof_buf = 0;
 252         mtx_unlock_spin(&mprof_mtx);
 253         return (0);
 254 }
 255 SYSCTL_PROC(_debug_mutex_prof, OID_AUTO, reset, CTLTYPE_INT | CTLFLAG_RW,
 256     NULL, 0, reset_mutex_prof_stats, "I", "Reset mutex profiling statistics");
 257 #endif
 258
 259 /*
 260  * Function versions of the inlined __mtx_* macros.  These are used by
 261  * modules and can also be called from assembly language if needed.
 262  */
 263 void
 264 _mtx_lock_flags(struct mtx *m, int opts, const char *file, int line)
 265 {
 266
 267         MPASS(curthread != NULL);
 268         KASSERT(m->mtx_object.lo_class == &lock_class_mtx_sleep,
 269             ("mtx_lock() of spin mutex %s @ %s:%d", m->mtx_object.lo_name,
 270             file, line));
 271         WITNESS_CHECKORDER(&m->mtx_object, opts | LOP_NEWORDER | LOP_EXCLUSIVE,
 272             file, line);
 273         _get_sleep_lock(m, curthread, opts, file, line);
 274         LOCK_LOG_LOCK("LOCK", &m->mtx_object, opts, m->mtx_recurse, file,
 275             line);
 276         WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line);
 277 #ifdef MUTEX_PROFILING
 278         /* don't reset the timer when/if recursing */
 279         if (m->mtx_acqtime == 0) {
 280                 m->mtx_filename = file;
 281                 m->mtx_lineno = line;
 282                 m->mtx_acqtime = mutex_prof_enable ? nanoseconds() : 0;
 283                 ++mutex_prof_acquisitions;
 284         }
 285 #endif
 286 }
 287
 288 void
 289 _mtx_unlock_flags(struct mtx *m, int opts, const char *file, int line)
 290 {
 291
 292         MPASS(curthread != NULL);
 293         KASSERT(m->mtx_object.lo_class == &lock_class_mtx_sleep,
 294             ("mtx_unlock() of spin mutex %s @ %s:%d", m->mtx_object.lo_name,
 295             file, line));
 296         WITNESS_UNLOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line);
 297         LOCK_LOG_LOCK("UNLOCK", &m->mtx_object, opts, m->mtx_recurse, file,
 298             line);
 299         mtx_assert(m, MA_OWNED);
 300 #ifdef MUTEX_PROFILING
 301         if (m->mtx_acqtime != 0) {
 302                 static const char *unknown = "(unknown)";
 303                 struct mutex_prof *mpp;
 304                 u_int64_t acqtime, now;
 305                 const char *p, *q;
 306                 volatile u_int hash;
 307
 308                 now = nanoseconds();
 309                 acqtime = m->mtx_acqtime;
 310                 m->mtx_acqtime = 0;
 311                 if (now <= acqtime)
 312                         goto out;
 313                 for (p = m->mtx_filename;
 314                     p != NULL && strncmp(p, "../", 3) == 0; p += 3)
 315                         /* nothing */ ;
 316                 if (p == NULL || *p == '\0')
 317                         p = unknown;
 318                 for (hash = m->mtx_lineno, q = p; *q != '\0'; ++q)
 319                         hash = (hash * 2 + *q) % MPROF_HASH_SIZE;
 320                 mtx_lock_spin(&mprof_mtx);
 321                 for (mpp = mprof_hash[hash]; mpp != NULL; mpp = mpp->next)
 322                         if (mpp->line == m->mtx_lineno &&
 323                             strcmp(mpp->file, p) == 0)
 324                                 break;
 325                 if (mpp == NULL) {
 326                         /* Just exit if we cannot get a trace buffer */
 327                         if (first_free_mprof_buf >= NUM_MPROF_BUFFERS) {
 328                                 ++mutex_prof_rejected;
 329                                 goto unlock;
 330                         }
 331                         mpp = &mprof_buf[first_free_mprof_buf++];
 332                         mpp->name = mtx_name(m);
 333                         mpp->file = p;
 334                         mpp->line = m->mtx_lineno;
 335                         mpp->next = mprof_hash[hash];
 336                         if (mprof_hash[hash] != NULL)
 337                                 ++mutex_prof_collisions;
 338                         mprof_hash[hash] = mpp;
 339                         ++mutex_prof_records;
 340                 }
 341                 /*
 342                  * Record if the mutex has been held longer now than ever
 343                  * before.
 344                  */
 345                 if (now - acqtime > mpp->cnt_max)
 346                         mpp->cnt_max = now - acqtime;
 347                 mpp->cnt_tot += now - acqtime;
 348                 mpp->cnt_cur++;
 349                 /*
 350                  * There's a small race, really we should cmpxchg
 351                  * 0 with the current value, but that would bill
 352                  * the contention to the wrong lock instance if
 353                  * it followed this also.
 354                  */
 355                 mpp->cnt_contest_holding += m->mtx_contest_holding;
 356                 m->mtx_contest_holding = 0;
 357                 mpp->cnt_contest_locking += m->mtx_contest_locking;
 358                 m->mtx_contest_locking = 0;
 359 unlock:
 360                 mtx_unlock_spin(&mprof_mtx);
 361         }
 362 out:
 363 #endif
 364         _rel_sleep_lock(m, curthread, opts, file, line);
 365 }
 366
 367 void
 368 _mtx_lock_spin_flags(struct mtx *m, int opts, const char *file, int line)
 369 {
 370
 371         MPASS(curthread != NULL);
 372         KASSERT(m->mtx_object.lo_class == &lock_class_mtx_spin,
 373             ("mtx_lock_spin() of sleep mutex %s @ %s:%d",
 374             m->mtx_object.lo_name, file, line));
 375         WITNESS_CHECKORDER(&m->mtx_object, opts | LOP_NEWORDER | LOP_EXCLUSIVE,
 376             file, line);
 377         _get_spin_lock(m, curthread, opts, file, line);
 378         LOCK_LOG_LOCK("LOCK", &m->mtx_object, opts, m->mtx_recurse, file,
 379             line);
 380         WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line);
 381 }
 382
 383 void
 384 _mtx_unlock_spin_flags(struct mtx *m, int opts, const char *file, int line)
 385 {
 386
 387         MPASS(curthread != NULL);
 388         KASSERT(m->mtx_object.lo_class == &lock_class_mtx_spin,
 389             ("mtx_unlock_spin() of sleep mutex %s @ %s:%d",
 390             m->mtx_object.lo_name, file, line));
 391         WITNESS_UNLOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line);
 392         LOCK_LOG_LOCK("UNLOCK", &m->mtx_object, opts, m->mtx_recurse, file,
 393             line);
 394         mtx_assert(m, MA_OWNED);
 395         _rel_spin_lock(m);
 396 }
 397
 398 /*
 399  * The important part of mtx_trylock{,_flags}()
 400  * Tries to acquire lock `m.'  If this function is called on a mutex that
 401  * is already owned, it will recursively acquire the lock.
 402  */
 403 int
 404 _mtx_trylock(struct mtx *m, int opts, const char *file, int line)
 405 {
 406         int rval;
 407
 408         MPASS(curthread != NULL);
 409
 410         if (mtx_owned(m) && (m->mtx_object.lo_flags & LO_RECURSABLE) != 0) {
 411                 m->mtx_recurse++;
 412                 atomic_set_ptr(&m->mtx_lock, MTX_RECURSED);
 413                 rval = 1;
 414         } else
 415                 rval = _obtain_lock(m, curthread);
 416
 417         LOCK_LOG_TRY("LOCK", &m->mtx_object, opts, rval, file, line);
 418         if (rval)
 419                 WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE | LOP_TRYLOCK,
 420                     file, line);
 421
 422         return (rval);
 423 }
 424
 425 /*
 426  * _mtx_lock_sleep: the tougher part of acquiring an MTX_DEF lock.
 427  *
 428  * We call this if the lock is either contested (i.e. we need to go to
 429  * sleep waiting for it), or if we need to recurse on it.
 430  */
 431 void
 432 _mtx_lock_sleep(struct mtx *m, struct thread *td, int opts, const char *file,
 433     int line)
 434 {
 435 #if defined(SMP) && !defined(NO_ADAPTIVE_MUTEXES)
 436         struct thread *owner;
 437 #endif
 438         uintptr_t v;
 439 #ifdef KTR
 440         int cont_logged = 0;
 441 #endif
 442 #ifdef MUTEX_PROFILING
 443         int contested;
 444 #endif
 445
 446         if (mtx_owned(m)) {
 447                 KASSERT((m->mtx_object.lo_flags & LO_RECURSABLE) != 0,
 448             ("_mtx_lock_sleep: recursed on non-recursive mutex %s @ %s:%d\n",
 449                     m->mtx_object.lo_name, file, line));
 450                 m->mtx_recurse++;
 451                 atomic_set_ptr(&m->mtx_lock, MTX_RECURSED);
 452                 if (LOCK_LOG_TEST(&m->mtx_object, opts))
 453                         CTR1(KTR_LOCK, "_mtx_lock_sleep: %p recursing", m);
 454                 return;
 455         }
 456
 457         if (LOCK_LOG_TEST(&m->mtx_object, opts))
 458                 CTR4(KTR_LOCK,
 459                     "_mtx_lock_sleep: %s contested (lock=%p) at %s:%d",
 460                     m->mtx_object.lo_name, (void *)m->mtx_lock, file, line);
 461
 462 #ifdef MUTEX_PROFILING
 463         contested = 0;
 464 #endif
 465         while (!_obtain_lock(m, td)) {
 466 #ifdef MUTEX_PROFILING
 467                 contested = 1;
 468                 atomic_add_int(&m->mtx_contest_holding, 1);
 469 #endif
 470                 turnstile_lock(&m->mtx_object);
 471                 v = m->mtx_lock;
 472
 473                 /*
 474                  * Check if the lock has been released while spinning for
 475                  * the turnstile chain lock.
 476                  */
 477                 if (v == MTX_UNOWNED) {
 478                         turnstile_release(&m->mtx_object);
 479                         cpu_spinwait();
 480                         continue;
 481                 }
 482
 483 #ifdef MUTEX_WAKE_ALL
 484                 MPASS(v != MTX_CONTESTED);
 485 #else
 486                 /*
 487                  * The mutex was marked contested on release. This means that
 488                  * there are other threads blocked on it.  Grab ownership of
 489                  * it and propagate its priority to the current thread if
 490                  * necessary.
 491                  */
 492                 if (v == MTX_CONTESTED) {
 493                         m->mtx_lock = (uintptr_t)td | MTX_CONTESTED;
 494                         turnstile_claim(&m->mtx_object);
 495                         break;
 496                 }
 497 #endif
 498
 499                 /*
 500                  * If the mutex isn't already contested and a failure occurs
 501                  * setting the contested bit, the mutex was either released
 502                  * or the state of the MTX_RECURSED bit changed.
 503                  */
 504                 if ((v & MTX_CONTESTED) == 0 &&
 505                     !atomic_cmpset_ptr(&m->mtx_lock, (void *)v,
 506                         (void *)(v | MTX_CONTESTED))) {
 507                         turnstile_release(&m->mtx_object);
 508                         cpu_spinwait();
 509                         continue;
 510                 }
 511
 512 #if defined(SMP) && !defined(NO_ADAPTIVE_MUTEXES)
 513                 /*
 514                  * If the current owner of the lock is executing on another
 515                  * CPU, spin instead of blocking.
 516                  */
 517                 owner = (struct thread *)(v & MTX_FLAGMASK);
 518 #ifdef ADAPTIVE_GIANT
 519                 if (TD_IS_RUNNING(owner)) {
 520 #else
 521                 if (m != &Giant && TD_IS_RUNNING(owner)) {
 522 #endif
 523                         turnstile_release(&m->mtx_object);
 524                         while (mtx_owner(m) == owner && TD_IS_RUNNING(owner)) {
 525                                 cpu_spinwait();
 526                         }
 527                         continue;
 528                 }
 529 #endif  /* SMP && !NO_ADAPTIVE_MUTEXES */
 530
 531                 /*
 532                  * We definitely must sleep for this lock.
 533                  */
 534                 mtx_assert(m, MA_NOTOWNED);
 535
 536 #ifdef KTR
 537                 if (!cont_logged) {
 538                         CTR6(KTR_CONTENTION,
 539                             "contention: %p at %s:%d wants %s, taken by %s:%d",
 540                             td, file, line, m->mtx_object.lo_name,
 541                             WITNESS_FILE(&m->mtx_object),
 542                             WITNESS_LINE(&m->mtx_object));
 543                         cont_logged = 1;
 544                 }
 545 #endif
 546
 547                 /*
 548                  * Block on the turnstile.
 549                  */
 550                 turnstile_wait(&m->mtx_object, mtx_owner(m));
 551         }
 552
 553 #ifdef KTR
 554         if (cont_logged) {
 555                 CTR4(KTR_CONTENTION,
 556                     "contention end: %s acquired by %p at %s:%d",
 557                     m->mtx_object.lo_name, td, file, line);
 558         }
 559 #endif
 560 #ifdef MUTEX_PROFILING
 561         if (contested)
 562                 m->mtx_contest_locking++;
 563         m->mtx_contest_holding = 0;
 564 #endif
 565         return;
 566 }
 567
 568 #ifdef SMP
 569 /*
 570  * _mtx_lock_spin: the tougher part of acquiring an MTX_SPIN lock.
 571  *
 572  * This is only called if we need to actually spin for the lock. Recursion
 573  * is handled inline.
 574  */
 575 void
 576 _mtx_lock_spin(struct mtx *m, struct thread *td, int opts, const char *file,
 577     int line)
 578 {
 579         int i = 0;
 580
 581         if (LOCK_LOG_TEST(&m->mtx_object, opts))
 582                 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spinning", m);
 583
 584         for (;;) {
 585                 if (_obtain_lock(m, td))
 586                         break;
 587
 588                 /* Give interrupts a chance while we spin. */
 589                 spinlock_exit();
 590                 while (m->mtx_lock != MTX_UNOWNED) {
 591                         if (i++ < 10000000) {
 592                                 cpu_spinwait();
 593                                 continue;
 594                         }
 595                         if (i < 60000000)
 596                                 DELAY(1);
 597                         else if (!kdb_active) {
 598                                 printf("spin lock %s held by %p for > 5 seconds\n",
 599                                     m->mtx_object.lo_name, (void *)m->mtx_lock);
 600 #ifdef WITNESS
 601                                 witness_display_spinlock(&m->mtx_object,
 602                                     mtx_owner(m));
 603 #endif
 604                                 panic("spin lock held too long");
 605                         }
 606                         cpu_spinwait();
 607                 }
 608                 spinlock_enter();
 609         }
 610
 611         if (LOCK_LOG_TEST(&m->mtx_object, opts))
 612                 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spin done", m);
 613
 614         return;
 615 }
 616 #endif /* SMP */
 617
 618 /*
 619  * _mtx_unlock_sleep: the tougher part of releasing an MTX_DEF lock.
 620  *
 621  * We are only called here if the lock is recursed or contested (i.e. we
 622  * need to wake up a blocked thread).
 623  */
 624 void
 625 _mtx_unlock_sleep(struct mtx *m, int opts, const char *file, int line)
 626 {
 627         struct turnstile *ts;
 628 #ifndef PREEMPTION
 629         struct thread *td, *td1;
 630 #endif
 631
 632         if (mtx_recursed(m)) {
 633                 if (--(m->mtx_recurse) == 0)
 634                         atomic_clear_ptr(&m->mtx_lock, MTX_RECURSED);
 635                 if (LOCK_LOG_TEST(&m->mtx_object, opts))
 636                         CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p unrecurse", m);
 637                 return;
 638         }
 639
 640         turnstile_lock(&m->mtx_object);
 641         ts = turnstile_lookup(&m->mtx_object);
 642         if (LOCK_LOG_TEST(&m->mtx_object, opts))
 643                 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p contested", m);
 644
 645 #if defined(SMP) && !defined(NO_ADAPTIVE_MUTEXES)
 646         if (ts == NULL) {
 647                 _release_lock_quick(m);
 648                 if (LOCK_LOG_TEST(&m->mtx_object, opts))
 649                         CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p no sleepers", m);
 650                 turnstile_release(&m->mtx_object);
 651                 return;
 652         }
 653 #else
 654         MPASS(ts != NULL);
 655 #endif
 656 #ifndef PREEMPTION
 657         /* XXX */
 658         td1 = turnstile_head(ts);
 659 #endif
 660 #ifdef MUTEX_WAKE_ALL
 661         turnstile_broadcast(ts);
 662         _release_lock_quick(m);
 663 #else
 664         if (turnstile_signal(ts)) {
 665                 _release_lock_quick(m);
 666                 if (LOCK_LOG_TEST(&m->mtx_object, opts))
 667                         CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p not held", m);
 668         } else {
 669                 m->mtx_lock = MTX_CONTESTED;
 670                 if (LOCK_LOG_TEST(&m->mtx_object, opts))
 671                         CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p still contested",
 672                             m);
 673         }
 674 #endif
 675         turnstile_unpend(ts);
 676
 677 #ifndef PREEMPTION
 678         /*
 679          * XXX: This is just a hack until preemption is done.  However,
 680          * once preemption is done we need to either wrap the
 681          * turnstile_signal() and release of the actual lock in an
 682          * extra critical section or change the preemption code to
 683          * always just set a flag and never do instant-preempts.
 684          */
 685         td = curthread;
 686         if (td->td_critnest > 0 || td1->td_priority >= td->td_priority)
 687                 return;
 688         mtx_lock_spin(&sched_lock);
 689         if (!TD_IS_RUNNING(td1)) {
 690 #ifdef notyet
 691                 if (td->td_ithd != NULL) {
 692                         struct ithd *it = td->td_ithd;
 693
 694                         if (it->it_interrupted) {
 695                                 if (LOCK_LOG_TEST(&m->mtx_object, opts))
 696                                         CTR2(KTR_LOCK,
 697                                     "_mtx_unlock_sleep: %p interrupted %p",
 698                                             it, it->it_interrupted);
 699                                 intr_thd_fixup(it);
 700                         }
 701                 }
 702 #endif
 703                 if (LOCK_LOG_TEST(&m->mtx_object, opts))
 704                         CTR2(KTR_LOCK,
 705                             "_mtx_unlock_sleep: %p switching out lock=%p", m,
 706                             (void *)m->mtx_lock);
 707
 708                 mi_switch(SW_INVOL, NULL);
 709                 if (LOCK_LOG_TEST(&m->mtx_object, opts))
 710                         CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p resuming lock=%p",
 711                             m, (void *)m->mtx_lock);
 712         }
 713         mtx_unlock_spin(&sched_lock);
 714 #endif
 715
 716         return;
 717 }
 718
 719 /*
 720  * All the unlocking of MTX_SPIN locks is done inline.
 721  * See the _rel_spin_lock() macro for the details.
 722  */
 723
 724 /*
 725  * The backing function for the INVARIANTS-enabled mtx_assert()
 726  */
 727 #ifdef INVARIANT_SUPPORT
 728 void
 729 _mtx_assert(struct mtx *m, int what, const char *file, int line)
 730 {
 731
 732         if (panicstr != NULL)
 733                 return;
 734         switch (what) {
 735         case MA_OWNED:
 736         case MA_OWNED | MA_RECURSED:
 737         case MA_OWNED | MA_NOTRECURSED:
 738                 if (!mtx_owned(m))
 739                         panic("mutex %s not owned at %s:%d",
 740                             m->mtx_object.lo_name, file, line);
 741                 if (mtx_recursed(m)) {
 742                         if ((what & MA_NOTRECURSED) != 0)
 743                                 panic("mutex %s recursed at %s:%d",
 744                                     m->mtx_object.lo_name, file, line);
 745                 } else if ((what & MA_RECURSED) != 0) {
 746                         panic("mutex %s unrecursed at %s:%d",
 747                             m->mtx_object.lo_name, file, line);
 748                 }
 749                 break;
 750         case MA_NOTOWNED:
 751                 if (mtx_owned(m))
 752                         panic("mutex %s owned at %s:%d",
 753                             m->mtx_object.lo_name, file, line);
 754                 break;
 755         default:
 756                 panic("unknown mtx_assert at %s:%d", file, line);
 757         }
 758 }
 759 #endif
 760
 761 /*
 762  * The MUTEX_DEBUG-enabled mtx_validate()
 763  *
 764  * Most of these checks have been moved off into the LO_INITIALIZED flag
 765  * maintained by the witness code.
 766  */
 767 #ifdef MUTEX_DEBUG
 768
 769 void    mtx_validate(struct mtx *);
 770
 771 void
 772 mtx_validate(struct mtx *m)
 773 {
 774
 775 /*
 776  * XXX: When kernacc() does not require Giant we can reenable this check
 777  */
 778 #ifdef notyet
 779 /*
 780  * XXX - When kernacc() is fixed on the alpha to handle K0_SEG memory properly
 781  * we can re-enable the kernacc() checks.
 782  */
 783 #ifndef __alpha__
 784         /*
 785          * Can't call kernacc() from early init386(), especially when
 786          * initializing Giant mutex, because some stuff in kernacc()
 787          * requires Giant itself.
 788          */
 789         if (!cold)
 790                 if (!kernacc((caddr_t)m, sizeof(m),
 791                     VM_PROT_READ | VM_PROT_WRITE))
 792                         panic("Can't read and write to mutex %p", m);
 793 #endif
 794 #endif
 795 }
 796 #endif
 797
 798 /*
 799  * General init routine used by the MTX_SYSINIT() macro.
 800  */
 801 void
 802 mtx_sysinit(void *arg)
 803 {
 804         struct mtx_args *margs = arg;
 805
 806         mtx_init(margs->ma_mtx, margs->ma_desc, NULL, margs->ma_opts);
 807 }
 808
 809 /*
 810  * Mutex initialization routine; initialize lock `m' of type contained in
 811  * `opts' with options contained in `opts' and name `name.'  The optional
 812  * lock type `type' is used as a general lock category name for use with
 813  * witness.
 814  */
 815 void
 816 mtx_init(struct mtx *m, const char *name, const char *type, int opts)
 817 {
 818         struct lock_object *lock;
 819
 820         MPASS((opts & ~(MTX_SPIN | MTX_QUIET | MTX_RECURSE |
 821             MTX_NOWITNESS | MTX_DUPOK)) == 0);
 822
 823 #ifdef MUTEX_DEBUG
 824         /* Diagnostic and error correction */
 825         mtx_validate(m);
 826 #endif
 827
 828         lock = &m->mtx_object;
 829         KASSERT((lock->lo_flags & LO_INITIALIZED) == 0,
 830             ("mutex \"%s\" %p already initialized", name, m));
 831         bzero(m, sizeof(*m));
 832         if (opts & MTX_SPIN)
 833                 lock->lo_class = &lock_class_mtx_spin;
 834         else
 835                 lock->lo_class = &lock_class_mtx_sleep;
 836         lock->lo_name = name;
 837         lock->lo_type = type != NULL ? type : name;
 838         if (opts & MTX_QUIET)
 839                 lock->lo_flags = LO_QUIET;
 840         if (opts & MTX_RECURSE)
 841                 lock->lo_flags |= LO_RECURSABLE;
 842         if ((opts & MTX_NOWITNESS) == 0)
 843                 lock->lo_flags |= LO_WITNESS;
 844         if (opts & MTX_DUPOK)
 845                 lock->lo_flags |= LO_DUPOK;
 846
 847         m->mtx_lock = MTX_UNOWNED;
 848
 849         LOCK_LOG_INIT(lock, opts);
 850
 851         WITNESS_INIT(lock);
 852 }
 853
 854 /*
 855  * Remove lock `m' from all_mtx queue.  We don't allow MTX_QUIET to be
 856  * passed in as a flag here because if the corresponding mtx_init() was
 857  * called with MTX_QUIET set, then it will already be set in the mutex's
 858  * flags.
 859  */
 860 void
 861 mtx_destroy(struct mtx *m)
 862 {
 863
 864         LOCK_LOG_DESTROY(&m->mtx_object, 0);
 865
 866         if (!mtx_owned(m))
 867                 MPASS(mtx_unowned(m));
 868         else {
 869                 MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0);
 870
 871                 /* Tell witness this isn't locked to make it happy. */
 872                 WITNESS_UNLOCK(&m->mtx_object, LOP_EXCLUSIVE, __FILE__,
 873                     __LINE__);
 874         }
 875
 876         WITNESS_DESTROY(&m->mtx_object);
 877 }
 878
 879 /*
 880  * Intialize the mutex code and system mutexes.  This is called from the MD
 881  * startup code prior to mi_startup().  The per-CPU data space needs to be
 882  * setup before this is called.
 883  */
 884 void
 885 mutex_init(void)
 886 {
 887
 888         /* Setup thread0 so that mutexes work. */
 889         LIST_INIT(&thread0.td_contested);
 890
 891         /* Setup turnstiles so that sleep mutexes work. */
 892         init_turnstiles();
 893
 894         /*
 895          * Initialize mutexes.
 896          */
 897         mtx_init(&Giant, "Giant", NULL, MTX_DEF | MTX_RECURSE);
 898         mtx_init(&sched_lock, "sched lock", NULL, MTX_SPIN | MTX_RECURSE);
 899         mtx_init(&proc0.p_mtx, "process lock", NULL, MTX_DEF | MTX_DUPOK);
 900         mtx_lock(&Giant);
 901 }