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_internal.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                         for (i = lock_wait_time; i > 0; i--)            \
  95                                 if (!(wanted))                          \
  96                                         break;                          \
  97                 }                                                       \
  98                 if (!(wanted))                                          \
  99                         break;
 100
 101 #else /* NCPUS == 1 */
 102
 103 /*
 104  * It is an error to spin on a uniprocessor as nothing will ever cause
 105  * the simple lock to clear while we are executing.
 106  */
 107 #define PAUSE(lkp, wanted)
 108
 109 #endif /* NCPUS == 1 */
 110
 111 /*
 112  * Acquire a resource.
 113  */
 114 #define ACQUIRE(lkp, error, extflags, wanted)                           \
 115         PAUSE(lkp, wanted);                                             \
 116         for (error = 0; wanted; ) {                                     \
 117                 (lkp)->lk_waitcount++;                                  \
 118                 error = tsleep((void *)lkp, (lkp)->lk_prio,             \
 119                     (lkp)->lk_wmesg, (lkp)->lk_timo);                   \
 120                 (lkp)->lk_waitcount--;                                  \
 121                 if (error)                                              \
 122                         break;                                          \
 123                 if ((extflags) & LK_SLEEPFAIL) {                        \
 124                         error = ENOLCK;                                 \
 125                         break;                                          \
 126                 }                                                       \
 127         }
 128
 129 /*
 130  * Initialize a lock; required before use.
 131  */
 132 void
 133 lockinit(lkp, prio, wmesg, timo, flags)
 134         struct lock__bsd__ *lkp;
 135         int prio;
 136         const char *wmesg;
 137         int timo;
 138         int flags;
 139 {
 140
 141         bzero(lkp, sizeof(struct lock__bsd__));
 142         lkp->lk_flags = flags & LK_EXTFLG_MASK;
 143         lkp->lk_prio = prio;
 144         lkp->lk_timo = timo;
 145         lkp->lk_wmesg = wmesg;
 146         lkp->lk_lockholder = LK_NOPROC;
 147         lkp->lk_lockthread = 0;
 148 }
 149
 150 /*
 151  * Determine the status of a lock.
 152  */
 153 int
 154 lockstatus(lkp)
 155         struct lock__bsd__ *lkp;
 156 {
 157         int lock_type = 0;
 158
 159         if (lkp->lk_exclusivecount != 0)
 160                 lock_type = LK_EXCLUSIVE;
 161         else if (lkp->lk_sharecount != 0)
 162                 lock_type = LK_SHARED;
 163         return (lock_type);
 164 }
 165
 166 /*
 167  * Set, change, or release a lock.
 168  *
 169  * Shared requests increment the shared count. Exclusive requests set the
 170  * LK_WANT_EXCL flag (preventing further shared locks), and wait for already
 171  * accepted shared locks and shared-to-exclusive upgrades to go away.
 172  */
 173 int
 174 lockmgr(lkp, flags, interlkp, p)
 175         struct lock__bsd__ *lkp;
 176         u_int flags;
 177         void * interlkp;
 178         struct proc *p;
 179 {
 180         int error;
 181         pid_t pid;
 182         int extflags;
 183         void *self;
 184
 185         error = 0; self = current_thread();
 186         if (p)
 187                 pid = p->p_pid;
 188         else
 189                 pid = LK_KERNPROC;
 190         extflags = (flags | lkp->lk_flags) & LK_EXTFLG_MASK;
 191 #if 0
 192         /*
 193          * Once a lock has drained, the LK_DRAINING flag is set and an
 194          * exclusive lock is returned. The only valid operation thereafter
 195          * is a single release of that exclusive lock. This final release
 196          * clears the LK_DRAINING flag and sets the LK_DRAINED flag. Any
 197          * further requests of any sort will result in a panic. The bits
 198          * selected for these two flags are chosen so that they will be set
 199          * in memory that is freed (freed memory is filled with 0xdeadbeef).
 200          * The final release is permitted to give a new lease on life to
 201          * the lock by specifying LK_REENABLE.
 202          */
 203         if (lkp->lk_flags & (LK_DRAINING|LK_DRAINED)) {
 204                 if (lkp->lk_flags & LK_DRAINED)
 205                         panic("lockmgr: using decommissioned lock");
 206                 if ((flags & LK_TYPE_MASK) != LK_RELEASE ||
 207                     (lkp->lk_lockholder != pid && lkp->lk_lockthread != self)
 208                         panic("lockmgr: non-release on draining lock: %d\n",
 209                             flags & LK_TYPE_MASK);
 210                 lkp->lk_flags &= ~LK_DRAINING;
 211                 if ((flags & LK_REENABLE) == 0)
 212                         lkp->lk_flags |= LK_DRAINED;
 213         }
 214 #endif
 215
 216         switch (flags & LK_TYPE_MASK) {
 217
 218         case LK_SHARED:
 219                 if (lkp->lk_lockholder != pid || lkp->lk_lockthread != self) {
 220                         /*
 221                          * If just polling, check to see if we will block.
 222                          */
 223                         if ((extflags & LK_NOWAIT) && (lkp->lk_flags &
 224                             (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE))) {
 225                                 error = EBUSY;
 226                                 break;
 227                         }
 228                         /*
 229                          * Wait for exclusive locks and upgrades to clear.
 230                          */
 231                         ACQUIRE(lkp, error, extflags, lkp->lk_flags &
 232                             (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE));
 233                         if (error)
 234                                 break;
 235                         lkp->lk_sharecount++;
 236                         COUNT(p, 1);
 237                         break;
 238                 }
 239                 /*
 240                  * We hold an exclusive lock, so downgrade it to shared.
 241                  * An alternative would be to fail with EDEADLK.
 242                  */
 243                 lkp->lk_sharecount++;
 244                 COUNT(p, 1);
 245                 /* fall into downgrade */
 246
 247         case LK_DOWNGRADE:
 248                 if (lkp->lk_lockholder != pid ||
 249                                 lkp->lk_lockthread != self ||
 250                                         lkp->lk_exclusivecount == 0)
 251                         panic("lockmgr: not holding exclusive lock");
 252                 lkp->lk_sharecount += lkp->lk_exclusivecount;
 253                 lkp->lk_exclusivecount = 0;
 254                 lkp->lk_flags &= ~LK_HAVE_EXCL;
 255                 lkp->lk_lockholder = LK_NOPROC;
 256                 lkp->lk_lockthread = 0;
 257                 if (lkp->lk_waitcount)
 258                         wakeup((void *)lkp);
 259                 break;
 260
 261         case LK_EXCLUPGRADE:
 262                 /*
 263                  * If another process is ahead of us to get an upgrade,
 264                  * then we want to fail rather than have an intervening
 265                  * exclusive access.
 266                  */
 267                 if (lkp->lk_flags & LK_WANT_UPGRADE) {
 268                         lkp->lk_sharecount--;
 269                         COUNT(p, -1);
 270                         error = EBUSY;
 271                         break;
 272                 }
 273                 /* fall into normal upgrade */
 274
 275         case LK_UPGRADE:
 276                 /*
 277                  * Upgrade a shared lock to an exclusive one. If another
 278                  * shared lock has already requested an upgrade to an
 279                  * exclusive lock, our shared lock is released and an
 280                  * exclusive lock is requested (which will be granted
 281                  * after the upgrade). If we return an error, the file
 282                  * will always be unlocked.
 283                  */
 284                 if ((lkp->lk_lockholder == pid &&
 285                                 lkp->lk_lockthread == self) ||
 286                                                 lkp->lk_sharecount <= 0)
 287                         panic("lockmgr: upgrade exclusive lock");
 288                 lkp->lk_sharecount--;
 289                 COUNT(p, -1);
 290                 /*
 291                  * If we are just polling, check to see if we will block.
 292                  */
 293                 if ((extflags & LK_NOWAIT) &&
 294                     ((lkp->lk_flags & LK_WANT_UPGRADE) ||
 295                      lkp->lk_sharecount > 1)) {
 296                         error = EBUSY;
 297                         break;
 298                 }
 299                 if ((lkp->lk_flags & LK_WANT_UPGRADE) == 0) {
 300                         /*
 301                          * We are first shared lock to request an upgrade, so
 302                          * request upgrade and wait for the shared count to
 303                          * drop to zero, then take exclusive lock.
 304                          */
 305                         lkp->lk_flags |= LK_WANT_UPGRADE;
 306                         ACQUIRE(lkp, error, extflags, lkp->lk_sharecount);
 307                         lkp->lk_flags &= ~LK_WANT_UPGRADE;
 308                         if (error)
 309                                 break;
 310                         lkp->lk_flags |= LK_HAVE_EXCL;
 311                         lkp->lk_lockholder = pid;
 312                         lkp->lk_lockthread = self;
 313                         if (lkp->lk_exclusivecount != 0)
 314                                 panic("lockmgr: non-zero exclusive count");
 315                         lkp->lk_exclusivecount = 1;
 316                         COUNT(p, 1);
 317                         break;
 318                 }
 319                 /*
 320                  * Someone else has requested upgrade. Release our shared
 321                  * lock, awaken upgrade requestor if we are the last shared
 322                  * lock, then request an exclusive lock.
 323                  */
 324                 if (lkp->lk_sharecount == 0 && lkp->lk_waitcount)
 325                         wakeup((void *)lkp);
 326                 /* fall into exclusive request */
 327
 328         case LK_EXCLUSIVE:
 329                 if (lkp->lk_lockholder == pid && lkp->lk_lockthread == self) {
 330                         /*
 331                          *      Recursive lock.
 332                          */
 333                         if ((extflags & LK_CANRECURSE) == 0)
 334                                 panic("lockmgr: locking against myself");
 335                         lkp->lk_exclusivecount++;
 336                         COUNT(p, 1);
 337                         break;
 338                 }
 339                 /*
 340                  * If we are just polling, check to see if we will sleep.
 341                  */
 342                 if ((extflags & LK_NOWAIT) && ((lkp->lk_flags &
 343                      (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) ||
 344                      lkp->lk_sharecount != 0)) {
 345                         error = EBUSY;
 346                         break;
 347                 }
 348                 /*
 349                  * Try to acquire the want_exclusive flag.
 350                  */
 351                 ACQUIRE(lkp, error, extflags, lkp->lk_flags &
 352                     (LK_HAVE_EXCL | LK_WANT_EXCL));
 353                 if (error)
 354                         break;
 355                 lkp->lk_flags |= LK_WANT_EXCL;
 356                 /*
 357                  * Wait for shared locks and upgrades to finish.
 358                  */
 359                 ACQUIRE(lkp, error, extflags, lkp->lk_sharecount != 0 ||
 360                        (lkp->lk_flags & LK_WANT_UPGRADE));
 361                 lkp->lk_flags &= ~LK_WANT_EXCL;
 362                 if (error)
 363                         break;
 364                 lkp->lk_flags |= LK_HAVE_EXCL;
 365                 lkp->lk_lockholder = pid;
 366                 lkp->lk_lockthread = self;
 367                 if (lkp->lk_exclusivecount != 0)
 368                         panic("lockmgr: non-zero exclusive count");
 369                 lkp->lk_exclusivecount = 1;
 370                 COUNT(p, 1);
 371                 break;
 372
 373         case LK_RELEASE:
 374                 if (lkp->lk_exclusivecount != 0) {
 375                         if (pid != lkp->lk_lockholder ||
 376                                         lkp->lk_lockthread != self)
 377                                 panic("lockmgr: pid %d, thread 0x%8x,"
 378                                         " not exclusive lock holder pid %d"
 379                                         " thread 0x%8x unlocking, exclusive count %d",
 380                                     pid, self, lkp->lk_lockholder,
 381                                         lkp->lk_lockthread, lkp->lk_exclusivecount);
 382                         lkp->lk_exclusivecount--;
 383                         COUNT(p, -1);
 384                         if (lkp->lk_exclusivecount == 0) {
 385                                 lkp->lk_flags &= ~LK_HAVE_EXCL;
 386                                 lkp->lk_lockholder = LK_NOPROC;
 387                                 lkp->lk_lockthread = 0;
 388                         }
 389                 } else if (lkp->lk_sharecount != 0) {
 390                         lkp->lk_sharecount--;
 391                         COUNT(p, -1);
 392                 }
 393                 if (lkp->lk_waitcount)
 394                         wakeup((void *)lkp);
 395                 break;
 396
 397         case LK_DRAIN:
 398                 /*
 399                  * Check that we do not already hold the lock, as it can
 400                  * never drain if we do. Unfortunately, we have no way to
 401                  * check for holding a shared lock, but at least we can
 402                  * check for an exclusive one.
 403                  */
 404                 if (lkp->lk_lockholder == pid && lkp->lk_lockthread == self)
 405                         panic("lockmgr: draining against myself");
 406                 /*
 407                  * If we are just polling, check to see if we will sleep.
 408                  */
 409                 if ((extflags & LK_NOWAIT) && ((lkp->lk_flags &
 410                      (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) ||
 411                      lkp->lk_sharecount != 0 || lkp->lk_waitcount != 0)) {
 412                         error = EBUSY;
 413                         break;
 414                 }
 415                 PAUSE(lkp, ((lkp->lk_flags &
 416                      (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) ||
 417                      lkp->lk_sharecount != 0 || lkp->lk_waitcount != 0));
 418                 for (error = 0; ((lkp->lk_flags &
 419                      (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) ||
 420                      lkp->lk_sharecount != 0 || lkp->lk_waitcount != 0); ) {
 421                         lkp->lk_flags |= LK_WAITDRAIN;
 422                         if (error = tsleep((void *)&lkp->lk_flags, lkp->lk_prio,
 423                             lkp->lk_wmesg, lkp->lk_timo))
 424                                 return (error);
 425                         if ((extflags) & LK_SLEEPFAIL)
 426                                 return (ENOLCK);
 427                 }
 428                 lkp->lk_flags |= LK_DRAINING | LK_HAVE_EXCL;
 429                 lkp->lk_lockholder = pid;
 430                 lkp->lk_lockthread = self;
 431                 lkp->lk_exclusivecount = 1;
 432                 COUNT(p, 1);
 433                 break;
 434
 435         default:
 436                 panic("lockmgr: unknown locktype request %d",
 437                     flags & LK_TYPE_MASK);
 438                 /* NOTREACHED */
 439         }
 440         if ((lkp->lk_flags & LK_WAITDRAIN) && ((lkp->lk_flags &
 441              (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE)) == 0 &&
 442              lkp->lk_sharecount == 0 && lkp->lk_waitcount == 0)) {
 443                 lkp->lk_flags &= ~LK_WAITDRAIN;
 444                 wakeup((void *)&lkp->lk_flags);
 445         }
 446         return (error);
 447 }
 448
 449 /*
 450  * Print out information about state of a lock. Used by VOP_PRINT
 451  * routines to display ststus about contained locks.
 452  */
 453 void
 454 lockmgr_printinfo(lkp)
 455         struct lock__bsd__ *lkp;
 456 {
 457
 458         if (lkp->lk_sharecount)
 459                 printf(" lock type %s: SHARED (count %d)", lkp->lk_wmesg,
 460                     lkp->lk_sharecount);
 461         else if (lkp->lk_flags & LK_HAVE_EXCL)
 462                 printf(" lock type %s: EXCL (count %d) by pid %d",
 463                     lkp->lk_wmesg, lkp->lk_exclusivecount, lkp->lk_lockholder);
 464         if (lkp->lk_waitcount > 0)
 465                 printf(" with %d pending", lkp->lk_waitcount);
 466 }