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