bsd/kern/kern_lock.c

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