vfs_lockf.c revision 1.40
1/* $NetBSD: vfs_lockf.c,v 1.40 2005/05/07 17:42:09 christos Exp $ */ 2 3/* 4 * Copyright (c) 1982, 1986, 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Scooter Morris at Genentech Inc. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 * 34 * @(#)ufs_lockf.c 8.4 (Berkeley) 10/26/94 35 */ 36 37#include <sys/cdefs.h> 38__KERNEL_RCSID(0, "$NetBSD: vfs_lockf.c,v 1.40 2005/05/07 17:42:09 christos Exp $"); 39 40#include <sys/param.h> 41#include <sys/systm.h> 42#include <sys/kernel.h> 43#include <sys/file.h> 44#include <sys/proc.h> 45#include <sys/vnode.h> 46#include <sys/pool.h> 47#include <sys/fcntl.h> 48#include <sys/lockf.h> 49 50POOL_INIT(lockfpool, sizeof(struct lockf), 0, 0, 0, "lockfpl", 51 &pool_allocator_nointr); 52 53/* 54 * This variable controls the maximum number of processes that will 55 * be checked in doing deadlock detection. 56 */ 57int maxlockdepth = MAXDEPTH; 58 59#ifdef LOCKF_DEBUG 60int lockf_debug = 0; 61#endif 62 63#define NOLOCKF (struct lockf *)0 64#define SELF 0x1 65#define OTHERS 0x2 66 67static int lf_clearlock(struct lockf *, struct lockf **); 68static int lf_findoverlap(struct lockf *, 69 struct lockf *, int, struct lockf ***, struct lockf **); 70static struct lockf *lf_getblock(struct lockf *); 71static int lf_getlock(struct lockf *, struct flock *); 72static int lf_setlock(struct lockf *, struct lockf **, struct simplelock *); 73static void lf_split(struct lockf *, struct lockf *, struct lockf **); 74static void lf_wakelock(struct lockf *); 75static struct lockf *lf_alloc(uid_t, int); 76static void lf_free(struct lockf *); 77 78 79#ifdef LOCKF_DEBUG 80static void lf_print(char *, struct lockf *); 81static void lf_printlist(char *, struct lockf *); 82#endif 83 84/* 85 * XXX TODO 86 * Misc cleanups: "caddr_t id" should be visible in the API as a 87 * "struct proc *". 88 * (This requires rototilling all VFS's which support advisory locking). 89 */ 90 91/* 92 * If there's a lot of lock contention on a single vnode, locking 93 * schemes which allow for more paralleism would be needed. Given how 94 * infrequently byte-range locks are actually used in typical BSD 95 * code, a more complex approach probably isn't worth it. 96 */ 97 98/* 99 * We enforce a limit on locks by uid, so that a single user cannot 100 * run the kernel out of memory. For now, the limit is pretty coarse. 101 * There is no limit on root. 102 * 103 * Splitting a lock will always succeed, regardless of current allocations. 104 * If you're slightly above the limit, we still have to permit an allocation 105 * so that the unlock can succeed. If the unlocking causes too many splits, 106 * however, you're totally cutoff. 107 */ 108int maxlocksperuid = 1024; 109 110/* 111 * 3 options for allowfail. 112 * 0 - always allocate. 1 - cutoff at limit. 2 - cutoff at double limit. 113 */ 114struct lockf * 115lf_alloc(uid_t uid, int allowfail) 116{ 117 struct uidinfo *uip; 118 struct lockf *lock; 119 120 uip = uid_find(uid); 121 simple_lock(&uip->ui_slock); 122 if (uid && allowfail && uip->ui_lockcnt > 123 (allowfail == 1 ? maxlocksperuid : (maxlocksperuid * 2))) { 124 simple_unlock(&uip->ui_slock); 125 return NULL; 126 } 127 uip->ui_lockcnt++; 128 simple_unlock(&uip->ui_slock); 129 lock = pool_get(&lockfpool, PR_WAITOK); 130 lock->lf_uid = uid; 131 return lock; 132} 133 134void 135lf_free(struct lockf *lock) 136{ 137 struct uidinfo *uip; 138 139 uip = uid_find(lock->lf_uid); 140 simple_lock(&uip->ui_slock); 141 uip->ui_lockcnt--; 142 simple_unlock(&uip->ui_slock); 143 pool_put(&lockfpool, lock); 144} 145 146/* 147 * Do an advisory lock operation. 148 */ 149int 150lf_advlock(struct vop_advlock_args *ap, struct lockf **head, off_t size) 151{ 152 struct proc *p = curproc; 153 struct flock *fl = ap->a_fl; 154 struct lockf *lock = NULL; 155 struct lockf *sparelock; 156 struct simplelock *interlock = &ap->a_vp->v_interlock; 157 off_t start, end; 158 int error = 0; 159 160 /* 161 * Convert the flock structure into a start and end. 162 */ 163 switch (fl->l_whence) { 164 case SEEK_SET: 165 case SEEK_CUR: 166 /* 167 * Caller is responsible for adding any necessary offset 168 * when SEEK_CUR is used. 169 */ 170 start = fl->l_start; 171 break; 172 173 case SEEK_END: 174 start = size + fl->l_start; 175 break; 176 177 default: 178 return EINVAL; 179 } 180 if (start < 0) 181 return EINVAL; 182 183 /* 184 * allocate locks before acquire simple lock. 185 * we need two locks in the worst case. 186 */ 187 switch (ap->a_op) { 188 case F_SETLK: 189 case F_UNLCK: 190 /* 191 * XXX for F_UNLCK case, we can re-use lock. 192 */ 193 if ((fl->l_type & F_FLOCK) == 0) { 194 /* 195 * byte-range lock might need one more lock. 196 */ 197 sparelock = lf_alloc(p->p_ucred->cr_uid, 0); 198 if (sparelock == NULL) { 199 error = ENOMEM; 200 goto quit; 201 } 202 break; 203 } 204 /* FALLTHROUGH */ 205 206 case F_GETLK: 207 sparelock = NULL; 208 break; 209 210 default: 211 return EINVAL; 212 } 213 214 lock = lf_alloc(p->p_ucred->cr_uid, ap->a_op != F_UNLCK ? 1 : 2); 215 if (lock == NULL) { 216 error = ENOMEM; 217 goto quit; 218 } 219 220 simple_lock(interlock); 221 222 /* 223 * Avoid the common case of unlocking when inode has no locks. 224 */ 225 if (*head == (struct lockf *)0) { 226 if (ap->a_op != F_SETLK) { 227 fl->l_type = F_UNLCK; 228 error = 0; 229 goto quit_unlock; 230 } 231 } 232 233 if (fl->l_len == 0) 234 end = -1; 235 else 236 end = start + fl->l_len - 1; 237 /* 238 * Create the lockf structure. 239 */ 240 lock->lf_start = start; 241 lock->lf_end = end; 242 /* XXX NJWLWP 243 * I don't want to make the entire VFS universe use LWPs, because 244 * they don't need them, for the most part. This is an exception, 245 * and a kluge. 246 */ 247 248 lock->lf_head = head; 249 lock->lf_type = fl->l_type; 250 lock->lf_next = (struct lockf *)0; 251 TAILQ_INIT(&lock->lf_blkhd); 252 lock->lf_flags = ap->a_flags; 253 if (lock->lf_flags & F_POSIX) { 254 KASSERT(curproc == (struct proc *)ap->a_id); 255 } 256 lock->lf_id = (struct proc *)ap->a_id; 257 lock->lf_lwp = curlwp; 258 259 /* 260 * Do the requested operation. 261 */ 262 switch (ap->a_op) { 263 264 case F_SETLK: 265 error = lf_setlock(lock, &sparelock, interlock); 266 lock = NULL; /* lf_setlock freed it */ 267 break; 268 269 case F_UNLCK: 270 error = lf_clearlock(lock, &sparelock); 271 break; 272 273 case F_GETLK: 274 error = lf_getlock(lock, fl); 275 break; 276 277 default: 278 break; 279 /* NOTREACHED */ 280 } 281 282quit_unlock: 283 simple_unlock(interlock); 284quit: 285 if (lock) 286 lf_free(lock); 287 if (sparelock) 288 lf_free(sparelock); 289 290 return error; 291} 292 293/* 294 * Set a byte-range lock. 295 */ 296static int 297lf_setlock(struct lockf *lock, struct lockf **sparelock, 298 struct simplelock *interlock) 299{ 300 struct lockf *block; 301 struct lockf **head = lock->lf_head; 302 struct lockf **prev, *overlap, *ltmp; 303 static char lockstr[] = "lockf"; 304 int ovcase, priority, needtolink, error; 305 306#ifdef LOCKF_DEBUG 307 if (lockf_debug & 1) 308 lf_print("lf_setlock", lock); 309#endif /* LOCKF_DEBUG */ 310 311 /* 312 * Set the priority 313 */ 314 priority = PLOCK; 315 if (lock->lf_type == F_WRLCK) 316 priority += 4; 317 priority |= PCATCH; 318 /* 319 * Scan lock list for this file looking for locks that would block us. 320 */ 321 while ((block = lf_getblock(lock)) != NULL) { 322 /* 323 * Free the structure and return if nonblocking. 324 */ 325 if ((lock->lf_flags & F_WAIT) == 0) { 326 lf_free(lock); 327 return EAGAIN; 328 } 329 /* 330 * We are blocked. Since flock style locks cover 331 * the whole file, there is no chance for deadlock. 332 * For byte-range locks we must check for deadlock. 333 * 334 * Deadlock detection is done by looking through the 335 * wait channels to see if there are any cycles that 336 * involve us. MAXDEPTH is set just to make sure we 337 * do not go off into neverneverland. 338 */ 339 if ((lock->lf_flags & F_POSIX) && 340 (block->lf_flags & F_POSIX)) { 341 struct lwp *wlwp; 342 struct lockf *waitblock; 343 int i = 0; 344 345 /* 346 * The block is waiting on something. if_lwp will be 347 * 0 once the lock is granted, so we terminate the 348 * loop if we find this. 349 */ 350 wlwp = block->lf_lwp; 351 while (wlwp && (i++ < maxlockdepth)) { 352 waitblock = (struct lockf *)wlwp->l_wchan; 353 /* Get the owner of the blocking lock */ 354 waitblock = waitblock->lf_next; 355 if ((waitblock->lf_flags & F_POSIX) == 0) 356 break; 357 wlwp = waitblock->lf_lwp; 358 if (wlwp == lock->lf_lwp) { 359 lf_free(lock); 360 return EDEADLK; 361 } 362 } 363 /* 364 * If we're still following a dependency chain 365 * after maxlockdepth iterations, assume we're in 366 * a cycle to be safe. 367 */ 368 if (i >= maxlockdepth) { 369 lf_free(lock); 370 return EDEADLK; 371 } 372 } 373 /* 374 * For flock type locks, we must first remove 375 * any shared locks that we hold before we sleep 376 * waiting for an exclusive lock. 377 */ 378 if ((lock->lf_flags & F_FLOCK) && 379 lock->lf_type == F_WRLCK) { 380 lock->lf_type = F_UNLCK; 381 (void) lf_clearlock(lock, NULL); 382 lock->lf_type = F_WRLCK; 383 } 384 /* 385 * Add our lock to the blocked list and sleep until we're free. 386 * Remember who blocked us (for deadlock detection). 387 */ 388 lock->lf_next = block; 389 TAILQ_INSERT_TAIL(&block->lf_blkhd, lock, lf_block); 390#ifdef LOCKF_DEBUG 391 if (lockf_debug & 1) { 392 lf_print("lf_setlock: blocking on", block); 393 lf_printlist("lf_setlock", block); 394 } 395#endif /* LOCKF_DEBUG */ 396 error = ltsleep(lock, priority, lockstr, 0, interlock); 397 398 /* 399 * We may have been awakened by a signal (in 400 * which case we must remove ourselves from the 401 * blocked list) and/or by another process 402 * releasing a lock (in which case we have already 403 * been removed from the blocked list and our 404 * lf_next field set to NOLOCKF). 405 */ 406 if (lock->lf_next != NOLOCKF) { 407 TAILQ_REMOVE(&lock->lf_next->lf_blkhd, lock, lf_block); 408 lock->lf_next = NOLOCKF; 409 } 410 if (error) { 411 lf_free(lock); 412 return error; 413 } 414 } 415 /* 416 * No blocks!! Add the lock. Note that we will 417 * downgrade or upgrade any overlapping locks this 418 * process already owns. 419 * 420 * Skip over locks owned by other processes. 421 * Handle any locks that overlap and are owned by ourselves. 422 */ 423 lock->lf_lwp = 0; 424 prev = head; 425 block = *head; 426 needtolink = 1; 427 for (;;) { 428 ovcase = lf_findoverlap(block, lock, SELF, &prev, &overlap); 429 if (ovcase) 430 block = overlap->lf_next; 431 /* 432 * Six cases: 433 * 0) no overlap 434 * 1) overlap == lock 435 * 2) overlap contains lock 436 * 3) lock contains overlap 437 * 4) overlap starts before lock 438 * 5) overlap ends after lock 439 */ 440 switch (ovcase) { 441 case 0: /* no overlap */ 442 if (needtolink) { 443 *prev = lock; 444 lock->lf_next = overlap; 445 } 446 break; 447 448 case 1: /* overlap == lock */ 449 /* 450 * If downgrading lock, others may be 451 * able to acquire it. 452 */ 453 if (lock->lf_type == F_RDLCK && 454 overlap->lf_type == F_WRLCK) 455 lf_wakelock(overlap); 456 overlap->lf_type = lock->lf_type; 457 lf_free(lock); 458 lock = overlap; /* for debug output below */ 459 break; 460 461 case 2: /* overlap contains lock */ 462 /* 463 * Check for common starting point and different types. 464 */ 465 if (overlap->lf_type == lock->lf_type) { 466 lf_free(lock); 467 lock = overlap; /* for debug output below */ 468 break; 469 } 470 if (overlap->lf_start == lock->lf_start) { 471 *prev = lock; 472 lock->lf_next = overlap; 473 overlap->lf_start = lock->lf_end + 1; 474 } else 475 lf_split(overlap, lock, sparelock); 476 lf_wakelock(overlap); 477 break; 478 479 case 3: /* lock contains overlap */ 480 /* 481 * If downgrading lock, others may be able to 482 * acquire it, otherwise take the list. 483 */ 484 if (lock->lf_type == F_RDLCK && 485 overlap->lf_type == F_WRLCK) { 486 lf_wakelock(overlap); 487 } else { 488 while ((ltmp = TAILQ_FIRST(&overlap->lf_blkhd))) { 489 KASSERT(ltmp->lf_next == overlap); 490 TAILQ_REMOVE(&overlap->lf_blkhd, ltmp, 491 lf_block); 492 ltmp->lf_next = lock; 493 TAILQ_INSERT_TAIL(&lock->lf_blkhd, 494 ltmp, lf_block); 495 } 496 } 497 /* 498 * Add the new lock if necessary and delete the overlap. 499 */ 500 if (needtolink) { 501 *prev = lock; 502 lock->lf_next = overlap->lf_next; 503 prev = &lock->lf_next; 504 needtolink = 0; 505 } else 506 *prev = overlap->lf_next; 507 lf_free(overlap); 508 continue; 509 510 case 4: /* overlap starts before lock */ 511 /* 512 * Add lock after overlap on the list. 513 */ 514 lock->lf_next = overlap->lf_next; 515 overlap->lf_next = lock; 516 overlap->lf_end = lock->lf_start - 1; 517 prev = &lock->lf_next; 518 lf_wakelock(overlap); 519 needtolink = 0; 520 continue; 521 522 case 5: /* overlap ends after lock */ 523 /* 524 * Add the new lock before overlap. 525 */ 526 if (needtolink) { 527 *prev = lock; 528 lock->lf_next = overlap; 529 } 530 overlap->lf_start = lock->lf_end + 1; 531 lf_wakelock(overlap); 532 break; 533 } 534 break; 535 } 536#ifdef LOCKF_DEBUG 537 if (lockf_debug & 1) { 538 lf_print("lf_setlock: got the lock", lock); 539 lf_printlist("lf_setlock", lock); 540 } 541#endif /* LOCKF_DEBUG */ 542 return 0; 543} 544 545/* 546 * Remove a byte-range lock on an inode. 547 * 548 * Generally, find the lock (or an overlap to that lock) 549 * and remove it (or shrink it), then wakeup anyone we can. 550 */ 551static int 552lf_clearlock(struct lockf *unlock, struct lockf **sparelock) 553{ 554 struct lockf **head = unlock->lf_head; 555 struct lockf *lf = *head; 556 struct lockf *overlap, **prev; 557 int ovcase; 558 559 if (lf == NOLOCKF) 560 return 0; 561#ifdef LOCKF_DEBUG 562 if (unlock->lf_type != F_UNLCK) 563 panic("lf_clearlock: bad type"); 564 if (lockf_debug & 1) 565 lf_print("lf_clearlock", unlock); 566#endif /* LOCKF_DEBUG */ 567 prev = head; 568 while ((ovcase = lf_findoverlap(lf, unlock, SELF, 569 &prev, &overlap)) != 0) { 570 /* 571 * Wakeup the list of locks to be retried. 572 */ 573 lf_wakelock(overlap); 574 575 switch (ovcase) { 576 577 case 1: /* overlap == lock */ 578 *prev = overlap->lf_next; 579 lf_free(overlap); 580 break; 581 582 case 2: /* overlap contains lock: split it */ 583 if (overlap->lf_start == unlock->lf_start) { 584 overlap->lf_start = unlock->lf_end + 1; 585 break; 586 } 587 lf_split(overlap, unlock, sparelock); 588 overlap->lf_next = unlock->lf_next; 589 break; 590 591 case 3: /* lock contains overlap */ 592 *prev = overlap->lf_next; 593 lf = overlap->lf_next; 594 lf_free(overlap); 595 continue; 596 597 case 4: /* overlap starts before lock */ 598 overlap->lf_end = unlock->lf_start - 1; 599 prev = &overlap->lf_next; 600 lf = overlap->lf_next; 601 continue; 602 603 case 5: /* overlap ends after lock */ 604 overlap->lf_start = unlock->lf_end + 1; 605 break; 606 } 607 break; 608 } 609#ifdef LOCKF_DEBUG 610 if (lockf_debug & 1) 611 lf_printlist("lf_clearlock", unlock); 612#endif /* LOCKF_DEBUG */ 613 return 0; 614} 615 616/* 617 * Check whether there is a blocking lock, 618 * and if so return its process identifier. 619 */ 620static int 621lf_getlock(struct lockf *lock, struct flock *fl) 622{ 623 struct lockf *block; 624 625#ifdef LOCKF_DEBUG 626 if (lockf_debug & 1) 627 lf_print("lf_getlock", lock); 628#endif /* LOCKF_DEBUG */ 629 630 if ((block = lf_getblock(lock)) != NULL) { 631 fl->l_type = block->lf_type; 632 fl->l_whence = SEEK_SET; 633 fl->l_start = block->lf_start; 634 if (block->lf_end == -1) 635 fl->l_len = 0; 636 else 637 fl->l_len = block->lf_end - block->lf_start + 1; 638 if (block->lf_flags & F_POSIX) 639 fl->l_pid = ((struct proc *)block->lf_id)->p_pid; 640 else 641 fl->l_pid = -1; 642 } else { 643 fl->l_type = F_UNLCK; 644 } 645 return 0; 646} 647 648/* 649 * Walk the list of locks for an inode and 650 * return the first blocking lock. 651 */ 652static struct lockf * 653lf_getblock(struct lockf *lock) 654{ 655 struct lockf **prev, *overlap, *lf = *(lock->lf_head); 656 657 prev = lock->lf_head; 658 while (lf_findoverlap(lf, lock, OTHERS, &prev, &overlap) != 0) { 659 /* 660 * We've found an overlap, see if it blocks us 661 */ 662 if ((lock->lf_type == F_WRLCK || overlap->lf_type == F_WRLCK)) 663 return overlap; 664 /* 665 * Nope, point to the next one on the list and 666 * see if it blocks us 667 */ 668 lf = overlap->lf_next; 669 } 670 return NOLOCKF; 671} 672 673/* 674 * Walk the list of locks for an inode to 675 * find an overlapping lock (if any). 676 * 677 * NOTE: this returns only the FIRST overlapping lock. There 678 * may be more than one. 679 */ 680static int 681lf_findoverlap(struct lockf *lf, struct lockf *lock, int type, 682 struct lockf ***prev, struct lockf **overlap) 683{ 684 off_t start, end; 685 686 *overlap = lf; 687 if (lf == NOLOCKF) 688 return 0; 689#ifdef LOCKF_DEBUG 690 if (lockf_debug & 2) 691 lf_print("lf_findoverlap: looking for overlap in", lock); 692#endif /* LOCKF_DEBUG */ 693 start = lock->lf_start; 694 end = lock->lf_end; 695 while (lf != NOLOCKF) { 696 if (((type == SELF) && lf->lf_id != lock->lf_id) || 697 ((type == OTHERS) && lf->lf_id == lock->lf_id)) { 698 *prev = &lf->lf_next; 699 *overlap = lf = lf->lf_next; 700 continue; 701 } 702#ifdef LOCKF_DEBUG 703 if (lockf_debug & 2) 704 lf_print("\tchecking", lf); 705#endif /* LOCKF_DEBUG */ 706 /* 707 * OK, check for overlap 708 * 709 * Six cases: 710 * 0) no overlap 711 * 1) overlap == lock 712 * 2) overlap contains lock 713 * 3) lock contains overlap 714 * 4) overlap starts before lock 715 * 5) overlap ends after lock 716 */ 717 if ((lf->lf_end != -1 && start > lf->lf_end) || 718 (end != -1 && lf->lf_start > end)) { 719 /* Case 0 */ 720#ifdef LOCKF_DEBUG 721 if (lockf_debug & 2) 722 printf("no overlap\n"); 723#endif /* LOCKF_DEBUG */ 724 if ((type & SELF) && end != -1 && lf->lf_start > end) 725 return 0; 726 *prev = &lf->lf_next; 727 *overlap = lf = lf->lf_next; 728 continue; 729 } 730 if ((lf->lf_start == start) && (lf->lf_end == end)) { 731 /* Case 1 */ 732#ifdef LOCKF_DEBUG 733 if (lockf_debug & 2) 734 printf("overlap == lock\n"); 735#endif /* LOCKF_DEBUG */ 736 return 1; 737 } 738 if ((lf->lf_start <= start) && 739 (end != -1) && 740 ((lf->lf_end >= end) || (lf->lf_end == -1))) { 741 /* Case 2 */ 742#ifdef LOCKF_DEBUG 743 if (lockf_debug & 2) 744 printf("overlap contains lock\n"); 745#endif /* LOCKF_DEBUG */ 746 return 2; 747 } 748 if (start <= lf->lf_start && 749 (end == -1 || 750 (lf->lf_end != -1 && end >= lf->lf_end))) { 751 /* Case 3 */ 752#ifdef LOCKF_DEBUG 753 if (lockf_debug & 2) 754 printf("lock contains overlap\n"); 755#endif /* LOCKF_DEBUG */ 756 return 3; 757 } 758 if ((lf->lf_start < start) && 759 ((lf->lf_end >= start) || (lf->lf_end == -1))) { 760 /* Case 4 */ 761#ifdef LOCKF_DEBUG 762 if (lockf_debug & 2) 763 printf("overlap starts before lock\n"); 764#endif /* LOCKF_DEBUG */ 765 return 4; 766 } 767 if ((lf->lf_start > start) && 768 (end != -1) && 769 ((lf->lf_end > end) || (lf->lf_end == -1))) { 770 /* Case 5 */ 771#ifdef LOCKF_DEBUG 772 if (lockf_debug & 2) 773 printf("overlap ends after lock\n"); 774#endif /* LOCKF_DEBUG */ 775 return 5; 776 } 777 panic("lf_findoverlap: default"); 778 } 779 return 0; 780} 781 782/* 783 * Split a lock and a contained region into 784 * two or three locks as necessary. 785 */ 786static void 787lf_split(struct lockf *lock1, struct lockf *lock2, struct lockf **sparelock) 788{ 789 struct lockf *splitlock; 790 791#ifdef LOCKF_DEBUG 792 if (lockf_debug & 2) { 793 lf_print("lf_split", lock1); 794 lf_print("splitting from", lock2); 795 } 796#endif /* LOCKF_DEBUG */ 797 /* 798 * Check to see if spliting into only two pieces. 799 */ 800 if (lock1->lf_start == lock2->lf_start) { 801 lock1->lf_start = lock2->lf_end + 1; 802 lock2->lf_next = lock1; 803 return; 804 } 805 if (lock1->lf_end == lock2->lf_end) { 806 lock1->lf_end = lock2->lf_start - 1; 807 lock2->lf_next = lock1->lf_next; 808 lock1->lf_next = lock2; 809 return; 810 } 811 /* 812 * Make a new lock consisting of the last part of 813 * the encompassing lock 814 */ 815 splitlock = *sparelock; 816 *sparelock = NULL; 817 memcpy(splitlock, lock1, sizeof(*splitlock)); 818 splitlock->lf_start = lock2->lf_end + 1; 819 TAILQ_INIT(&splitlock->lf_blkhd); 820 lock1->lf_end = lock2->lf_start - 1; 821 /* 822 * OK, now link it in 823 */ 824 splitlock->lf_next = lock1->lf_next; 825 lock2->lf_next = splitlock; 826 lock1->lf_next = lock2; 827} 828 829/* 830 * Wakeup a blocklist 831 */ 832static void 833lf_wakelock(struct lockf *listhead) 834{ 835 struct lockf *wakelock; 836 837 while ((wakelock = TAILQ_FIRST(&listhead->lf_blkhd))) { 838 KASSERT(wakelock->lf_next == listhead); 839 TAILQ_REMOVE(&listhead->lf_blkhd, wakelock, lf_block); 840 wakelock->lf_next = NOLOCKF; 841#ifdef LOCKF_DEBUG 842 if (lockf_debug & 2) 843 lf_print("lf_wakelock: awakening", wakelock); 844#endif 845 wakeup(wakelock); 846 } 847} 848 849#ifdef LOCKF_DEBUG 850/* 851 * Print out a lock. 852 */ 853static void 854lf_print(char *tag, struct lockf *lock) 855{ 856 857 printf("%s: lock %p for ", tag, lock); 858 if (lock->lf_flags & F_POSIX) 859 printf("proc %d", ((struct proc *)lock->lf_id)->p_pid); 860 else 861 printf("file 0x%p", (struct file *)lock->lf_id); 862 printf(" %s, start %qx, end %qx", 863 lock->lf_type == F_RDLCK ? "shared" : 864 lock->lf_type == F_WRLCK ? "exclusive" : 865 lock->lf_type == F_UNLCK ? "unlock" : 866 "unknown", lock->lf_start, lock->lf_end); 867 if (TAILQ_FIRST(&lock->lf_blkhd)) 868 printf(" block %p\n", TAILQ_FIRST(&lock->lf_blkhd)); 869 else 870 printf("\n"); 871} 872 873static void 874lf_printlist(char *tag, struct lockf *lock) 875{ 876 struct lockf *lf, *blk; 877 878 printf("%s: Lock list:\n", tag); 879 for (lf = *lock->lf_head; lf; lf = lf->lf_next) { 880 printf("\tlock %p for ", lf); 881 if (lf->lf_flags & F_POSIX) 882 printf("proc %d", ((struct proc *)lf->lf_id)->p_pid); 883 else 884 printf("file 0x%p", (struct file *)lf->lf_id); 885 printf(", %s, start %qx, end %qx", 886 lf->lf_type == F_RDLCK ? "shared" : 887 lf->lf_type == F_WRLCK ? "exclusive" : 888 lf->lf_type == F_UNLCK ? "unlock" : 889 "unknown", lf->lf_start, lf->lf_end); 890 TAILQ_FOREACH(blk, &lf->lf_blkhd, lf_block) { 891 if (blk->lf_flags & F_POSIX) 892 printf("proc %d", 893 ((struct proc *)blk->lf_id)->p_pid); 894 else 895 printf("file 0x%p", (struct file *)blk->lf_id); 896 printf(", %s, start %qx, end %qx", 897 blk->lf_type == F_RDLCK ? "shared" : 898 blk->lf_type == F_WRLCK ? "exclusive" : 899 blk->lf_type == F_UNLCK ? "unlock" : 900 "unknown", blk->lf_start, blk->lf_end); 901 if (TAILQ_FIRST(&blk->lf_blkhd)) 902 panic("lf_printlist: bad list"); 903 } 904 printf("\n"); 905 } 906} 907#endif /* LOCKF_DEBUG */ 908