bsd/kern/kern_lock.c

   1 /*
   2  * Copyright (c) 2000-2001 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /* Copyright (c) 1995, 1997 Apple Computer, Inc. All Rights Reserved */
  23 /*
  24  * Copyright (c) 1995
  25  *      The Regents of the University of California.  All rights reserved.
  26  *
  27  * This code contains ideas from software contributed to Berkeley by
  28  * Avadis Tevanian, Jr., Michael Wayne Young, and the Mach Operating
  29  * System project at Carnegie-Mellon University.
  30  *
  31  * Redistribution and use in source and binary forms, with or without
  32  * modification, are permitted provided that the following conditions
  33  * are met:
  34  * 1. Redistributions of source code must retain the above copyright
  35  *    notice, this list of conditions and the following disclaimer.
  36  * 2. Redistributions in binary form must reproduce the above copyright
  37  *    notice, this list of conditions and the following disclaimer in the
  38  *    documentation and/or other materials provided with the distribution.
  39  * 3. All advertising materials mentioning features or use of this software
  40  *    must display the following acknowledgement:
  41  *      This product includes software developed by the University of
  42  *      California, Berkeley and its contributors.
  43  * 4. Neither the name of the University nor the names of its contributors
  44  *    may be used to endorse or promote products derived from this software
  45  *    without specific prior written permission.
  46  *
  47  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  48  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  49  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  50  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  51  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  52  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  53  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  54  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  55  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  56  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  57  * SUCH DAMAGE.
  58  *
  59  *      @(#)kern_lock.c 8.18 (Berkeley) 5/21/95
  60  */
  61
  62 #include <sys/param.h>
  63 #include <sys/proc.h>
  64 #include <sys/lock.h>
  65 #include <kern/cpu_number.h>
  66 #include <kern/thread.h>
  67
  68 #include <mach/mach_types.h>
  69
  70 /*
  71  * Locking primitives implementation.
  72  * Locks provide shared/exclusive sychronization.
  73  */
  74
  75 #if 0
  76 #define COUNT(p, x) if (p) (p)->p_locks += (x)
  77 #else
  78 #define COUNT(p, x)
  79 #endif
  80
  81 #if NCPUS > 1
  82
  83 /*
  84  * For multiprocessor system, try spin lock first.
  85  *
  86  * This should be inline expanded below, but we cannot have #if
  87  * inside a multiline define.
  88  */
  89 int lock_wait_time = 100;
  90 #define PAUSE(lkp, wanted)                                              \
  91                 if (lock_wait_time > 0) {                               \
  92                         int i;                                          \
  93                                                                         \
  94                         simple_unlock(&lkp->lk_interlock);              \
  95                         for (i = lock_wait_time; i > 0; i--)            \
  96                                 if (!(wanted))                          \
  97                                         break;                          \
  98                         simple_lock(&lkp->lk_interlock);                \
  99                 }                                                       \
 100                 if (!(wanted))                                          \
 101                         break;
 102
 103 #else /* NCPUS == 1 */
 104
 105 /*
 106  * It is an error to spin on a uniprocessor as nothing will ever cause
 107  * the simple lock to clear while we are executing.
 108  */
 109 #define PAUSE(lkp, wanted)
 110
 111 #endif /* NCPUS == 1 */
 112
 113 /*
 114  * Acquire a resource.
 115  */
 116 #define ACQUIRE(lkp, error, extflags, wanted)                           \
 117         PAUSE(lkp, wanted);                                             \
 118         for (error = 0; wanted; ) {                                     \
 119                 (lkp)->lk_waitcount++;                                  \
 120                 simple_unlock(&(lkp)->lk_interlock);                    \
 121                 error = tsleep((void *)lkp, (lkp)->lk_prio,             \
 122                     (lkp)->lk_wmesg, (lkp)->lk_timo);                   \
 123                 simple_lock(&(lkp)->lk_interlock);                      \
 124                 (lkp)->lk_waitcount--;                                  \
 125                 if (error)                                              \
 126                         break;                                          \
 127                 if ((extflags) & LK_SLEEPFAIL) {                        \
 128                         error = ENOLCK;                                 \
 129                         break;                                          \
 130                 }                                                       \
 131         }
 132
 133 /*
 134  * Initialize a lock; required before use.
 135  */
 136 void
 137 lockinit(lkp, prio, wmesg, timo, flags)
 138         struct lock__bsd__ *lkp;
 139         int prio;
 140         char *wmesg;
 141         int timo;
 142         int flags;
 143 {
 144
 145         bzero(lkp, sizeof(struct lock__bsd__));
 146         simple_lock_init(&lkp->lk_interlock);
 147         lkp->lk_flags = flags & LK_EXTFLG_MASK;
 148         lkp->lk_prio = prio;
 149         lkp->lk_timo = timo;
 150         lkp->lk_wmesg = wmesg;
 151         lkp->lk_lockholder = LK_NOPROC;
 152         lkp->lk_lockthread = 0;
 153 }
 154
 155 /*
 156  * Determine the status of a lock.
 157  */
 158 int
 159 lockstatus(lkp)
 160         struct lock__bsd__ *lkp;
 161 {
 162         int lock_type = 0;
 163
 164         simple_lock(&lkp->lk_interlock);
 165         if (lkp->lk_exclusivecount != 0)
 166                 lock_type = LK_EXCLUSIVE;
 167         else if (lkp->lk_sharecount != 0)
 168                 lock_type = LK_SHARED;
 169         simple_unlock(&lkp->lk_interlock);
 170         return (lock_type);
 171 }
 172
 173 /*
 174  * Set, change, or release a lock.
 175  *
 176  * Shared requests increment the shared count. Exclusive requests set the
 177  * LK_WANT_EXCL flag (preventing further shared locks), and wait for already
 178  * accepted shared locks and shared-to-exclusive upgrades to go away.
 179  */
 180 int
 181 lockmgr(lkp, flags, interlkp, p)
 182         struct lock__bsd__ *lkp;
 183         u_int flags;
 184         simple_lock_t interlkp;
 185         struct proc *p;
 186 {
 187         int error;
 188         pid_t pid;
 189         int extflags;
 190         void *self;
 191
 192         error = 0; self = current_thread();
 193         if (p)
 194                 pid = p->p_pid;
 195         else
 196                 pid = LK_KERNPROC;
 197         simple_lock(&lkp->lk_interlock);
 198         if (flags & LK_INTERLOCK)
 199                 simple_unlock(interlkp);
 200         extflags = (flags | lkp->lk_flags) & LK_EXTFLG_MASK;
 201 #if 0
 202         /*
 203          * Once a lock has drained, the LK_DRAINING flag is set and an
 204          * exclusive lock is returned. The only valid operation thereafter
 205          * is a single release of that exclusive lock. This final release
 206          * clears the LK_DRAINING flag and sets the LK_DRAINED flag. Any
 207          * further requests of any sort will result in a panic. The bits
 208          * selected for these two flags are chosen so that they will be set
 209          * in memory that is freed (freed memory is filled with 0xdeadbeef).
 210          * The final release is permitted to give a new lease on life to
 211          * the lock by specifying LK_REENABLE.
 212          */
 213         if (lkp->lk_flags & (LK_DRAINING|LK_DRAINED)) {
 214                 if (lkp->lk_flags & LK_DRAINED)
 215                         panic("lockmgr: using decommissioned lock");
 216                 if ((flags & LK_TYPE_MASK) != LK_RELEASE ||
 217                     (lkp->lk_lockholder != pid && lkp->lk_lockthread != self)
 218                         panic("lockmgr: non-release on draining lock: %d\n",
 219                             flags & LK_TYPE_MASK);
 220                 lkp->lk_flags &= ~LK_DRAINING;
 221                 if ((flags & LK_REENABLE) == 0)
 222                         lkp->lk_flags |= LK_DRAINED;
 223         }
 224 #endif
 225
 226         switch (flags & LK_TYPE_MASK) {
 227
 228         case LK_SHARED:
 229                 if (lkp->lk_lockholder != pid || lkp->lk_lockthread != self) {
 230                         /*
 231                          * If just polling, check to see if we will block.
 232                          */
 233                         if ((extflags & LK_NOWAIT) && (lkp->lk_flags &
 234                             (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE))) {
 235                                 error = EBUSY;
 236                                 break;
 237                         }
 238                         /*
 239                          * Wait for exclusive locks and upgrades to clear.
 240                          */
 241                         ACQUIRE(lkp, error, extflags, lkp->lk_flags &
 242                             (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE));
 243                         if (error)
 244                                 break;
 245                         lkp->lk_sharecount++;
 246                         COUNT(p, 1);
 247                         break;
 248                 }
 249                 /*
 250                  * We hold an exclusive lock, so downgrade it to shared.
 251                  * An alternative would be to fail with EDEADLK.
 252                  */
 253                 lkp->lk_sharecount++;
 254                 COUNT(p, 1);
 255                 /* fall into downgrade */
 256
 257         case LK_DOWNGRADE:
 258                 if (lkp->lk_lockholder != pid ||
 259                                 lkp->lk_lockthread != self ||
 260                                         lkp->lk_exclusivecount == 0)
 261                         panic("lockmgr: not holding exclusive lock");
 262                 lkp->lk_sharecount += lkp->lk_exclusivecount;
 263                 lkp->lk_exclusivecount = 0;
 264                 lkp->lk_flags &= ~LK_HAVE_EXCL;
 265                 lkp->lk_lockholder = LK_NOPROC;
 266                 lkp->lk_lockthread = 0;
 267                 if (lkp->lk_waitcount)
 268                         wakeup((void *)lkp);
 269                 break;
 270
 271         case LK_EXCLUPGRADE:
 272                 /*
 273                  * If another process is ahead of us to get an upgrade,
 274                  * then we want to fail rather than have an intervening
 275                  * exclusive access.
 276                  */
 277                 if (lkp->lk_flags & LK_WANT_UPGRADE) {
 278                         lkp->lk_sharecount--;
 279                         COUNT(p, -1);
 280                         error = EBUSY;
 281                         break;
 282                 }
 283                 /* fall into normal upgrade */
 284
 285         case LK_UPGRADE:
 286                 /*
 287                  * Upgrade a shared lock to an exclusive one. If another
 288                  * shared lock has already requested an upgrade to an
 289                  * exclusive lock, our shared lock is released and an
 290                  * exclusive lock is requested (which will be granted
 291                  * after the upgrade). If we return an error, the file
 292                  * will always be unlocked.
 293                  */
 294                 if ((lkp->lk_lockholder == pid &&
 295                                 lkp->lk_lockthread == self) ||
 296                                                 lkp->lk_sharecount <= 0)
 297                         panic("lockmgr: upgrade exclusive lock");
 298                 lkp->lk_sharecount--;
 299                 COUNT(p, -1);
 300                 /*
 301                  * If we are just polling, check to see if we will block.
 302                  */
 303                 if ((extflags & LK_NOWAIT) &&
 304                     ((lkp->lk_flags & LK_WANT_UPGRADE) ||
 305                      lkp->lk_sharecount > 1)) {
 306                         error = EBUSY;
 307                         break;
 308                 }
 309                 if ((lkp->lk_flags & LK_WANT_UPGRADE) == 0) {
 310                         /*
 311                          * We are first shared lock to request an upgrade, so
 312                          * request upgrade and wait for the shared count to
 313                          * drop to zero, then take exclusive lock.
 314                          */
 315                         lkp->lk_flags |= LK_WANT_UPGRADE;
 316                         ACQUIRE(lkp, error, extflags, lkp->lk_sharecount);
 317                         lkp->lk_flags &= ~LK_WANT_UPGRADE;
 318                         if (error)
 319                                 break;
 320                         lkp->lk_flags |= LK_HAVE_EXCL;
 321                         lkp->lk_lockholder = pid;
 322                         lkp->lk_lockthread = self;
 323                         if (lkp->lk_exclusivecount != 0)
 324                                 panic("lockmgr: non-zero exclusive count");
 325                         lkp->lk_exclusivecount = 1;
 326                         COUNT(p, 1);
 327                         break;
 328                 }
 329                 /*
 330                  * Someone else has requested upgrade. Release our shared
 331                  * lock, awaken upgrade requestor if we are the last shared
 332                  * lock, then request an exclusive lock.
 333                  */
 334                 if (lkp->lk_sharecount == 0 && lkp->lk_waitcount)
 335                         wakeup((void *)lkp);
 336                 /* fall into exclusive request */
 337
 338         case LK_EXCLUSIVE:
 339                 if (lkp->lk_lockholder == pid && lkp->lk_lockthread == self) {
 340                         /*
 341                          *      Recursive lock.
 342                          */
 343                         if ((extflags & LK_CANRECURSE) == 0)
 344                                 panic("lockmgr: locking against myself");
 345                         lkp->lk_exclusivecount++;
 346                         COUNT(p, 1);
 347                         break;
 348                 }
 349                 /*
 350                  * If we are just polling, check to see if we will sleep.
 351                  */
 352                 if ((extflags & LK_NOWAIT) && ((lkp->lk_flags &
 353                      (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) ||
 354                      lkp->lk_sharecount != 0)) {
 355                         error = EBUSY;
 356                         break;
 357                 }
 358                 /*
 359                  * Try to acquire the want_exclusive flag.
 360                  */
 361                 ACQUIRE(lkp, error, extflags, lkp->lk_flags &
 362                     (LK_HAVE_EXCL | LK_WANT_EXCL));
 363                 if (error)
 364                         break;
 365                 lkp->lk_flags |= LK_WANT_EXCL;
 366                 /*
 367                  * Wait for shared locks and upgrades to finish.
 368                  */
 369                 ACQUIRE(lkp, error, extflags, lkp->lk_sharecount != 0 ||
 370                        (lkp->lk_flags & LK_WANT_UPGRADE));
 371                 lkp->lk_flags &= ~LK_WANT_EXCL;
 372                 if (error)
 373                         break;
 374                 lkp->lk_flags |= LK_HAVE_EXCL;
 375                 lkp->lk_lockholder = pid;
 376                 lkp->lk_lockthread = self;
 377                 if (lkp->lk_exclusivecount != 0)
 378                         panic("lockmgr: non-zero exclusive count");
 379                 lkp->lk_exclusivecount = 1;
 380                 COUNT(p, 1);
 381                 break;
 382
 383         case LK_RELEASE:
 384                 if (lkp->lk_exclusivecount != 0) {
 385                         if (pid != lkp->lk_lockholder ||
 386                                         lkp->lk_lockthread != self)
 387                                 panic("lockmgr: pid %d, thread 0x%8x,"
 388                                         " not exclusive lock holder pid %d"
 389                                         " thread 0x%8x unlocking, exclusive count %d",
 390                                     pid, self, lkp->lk_lockholder,
 391                                         lkp->lk_lockthread, lkp->lk_exclusivecount);
 392                         lkp->lk_exclusivecount--;
 393                         COUNT(p, -1);
 394                         if (lkp->lk_exclusivecount == 0) {
 395                                 lkp->lk_flags &= ~LK_HAVE_EXCL;
 396                                 lkp->lk_lockholder = LK_NOPROC;
 397                                 lkp->lk_lockthread = 0;
 398                         }
 399                 } else if (lkp->lk_sharecount != 0) {
 400                         lkp->lk_sharecount--;
 401                         COUNT(p, -1);
 402                 }
 403                 if (lkp->lk_waitcount)
 404                         wakeup((void *)lkp);
 405                 break;
 406
 407         case LK_DRAIN:
 408                 /*
 409                  * Check that we do not already hold the lock, as it can
 410                  * never drain if we do. Unfortunately, we have no way to
 411                  * check for holding a shared lock, but at least we can
 412                  * check for an exclusive one.
 413                  */
 414                 if (lkp->lk_lockholder == pid && lkp->lk_lockthread == self)
 415                         panic("lockmgr: draining against myself");
 416                 /*
 417                  * If we are just polling, check to see if we will sleep.
 418                  */
 419                 if ((extflags & LK_NOWAIT) && ((lkp->lk_flags &
 420                      (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) ||
 421                      lkp->lk_sharecount != 0 || lkp->lk_waitcount != 0)) {
 422                         error = EBUSY;
 423                         break;
 424                 }
 425                 PAUSE(lkp, ((lkp->lk_flags &
 426                      (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) ||
 427                      lkp->lk_sharecount != 0 || lkp->lk_waitcount != 0));
 428                 for (error = 0; ((lkp->lk_flags &
 429                      (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) ||
 430                      lkp->lk_sharecount != 0 || lkp->lk_waitcount != 0); ) {
 431                         lkp->lk_flags |= LK_WAITDRAIN;
 432                         simple_unlock(&lkp->lk_interlock);
 433                         if (error = tsleep((void *)&lkp->lk_flags, lkp->lk_prio,
 434                             lkp->lk_wmesg, lkp->lk_timo))
 435                                 return (error);
 436                         if ((extflags) & LK_SLEEPFAIL)
 437                                 return (ENOLCK);
 438                         simple_lock(&lkp->lk_interlock);
 439                 }
 440                 lkp->lk_flags |= LK_DRAINING | LK_HAVE_EXCL;
 441                 lkp->lk_lockholder = pid;
 442                 lkp->lk_lockthread = self;
 443                 lkp->lk_exclusivecount = 1;
 444                 COUNT(p, 1);
 445                 break;
 446
 447         default:
 448                 simple_unlock(&lkp->lk_interlock);
 449                 panic("lockmgr: unknown locktype request %d",
 450                     flags & LK_TYPE_MASK);
 451                 /* NOTREACHED */
 452         }
 453         if ((lkp->lk_flags & LK_WAITDRAIN) && ((lkp->lk_flags &
 454              (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) == 0 &&
 455              lkp->lk_sharecount == 0 && lkp->lk_waitcount == 0)) {
 456                 lkp->lk_flags &= ~LK_WAITDRAIN;
 457                 wakeup((void *)&lkp->lk_flags);
 458         }
 459         simple_unlock(&lkp->lk_interlock);
 460         return (error);
 461 }
 462
 463 /*
 464  * Print out information about state of a lock. Used by VOP_PRINT
 465  * routines to display ststus about contained locks.
 466  */
 467 lockmgr_printinfo(lkp)
 468         struct lock__bsd__ *lkp;
 469 {
 470
 471         if (lkp->lk_sharecount)
 472                 printf(" lock type %s: SHARED (count %d)", lkp->lk_wmesg,
 473                     lkp->lk_sharecount);
 474         else if (lkp->lk_flags & LK_HAVE_EXCL)
 475                 printf(" lock type %s: EXCL (count %d) by pid %d",
 476                     lkp->lk_wmesg, lkp->lk_exclusivecount, lkp->lk_lockholder);
 477         if (lkp->lk_waitcount > 0)
 478                 printf(" with %d pending", lkp->lk_waitcount);
 479 }