1 /* $OpenBSD: vfs_lockf.c,v 1.43 2019/05/12 19:43:34 anton 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 (fl->l_start + fl->l_len < 0) 256 return (EINVAL); 257 end = fl->l_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 KERNEL_LOCK(); 384 error = rwsleep(lock, &lockf_lock, priority, "lockf", 0); 385 KERNEL_UNLOCK(); 386 TAILQ_REMOVE(&lock->lf_state->ls_pending, lock, lf_entry); 387 wakeup_one(lock->lf_state); 388 if (lock->lf_blk != NULL) { 389 TAILQ_REMOVE(&lock->lf_blk->lf_blkhd, lock, lf_block); 390 lock->lf_blk = NULL; 391 } 392 if (error) { 393 lf_free(lock); 394 return (error); 395 } 396 if (lock->lf_flags & F_INTR) { 397 lf_free(lock); 398 return (EINTR); 399 } 400 } 401 /* 402 * No blocks!! Add the lock. Note that we will 403 * downgrade or upgrade any overlapping locks this 404 * process already owns. 405 * 406 * Skip over locks owned by other processes. 407 * Handle any locks that overlap and are owned by ourselves. 408 */ 409 block = TAILQ_FIRST(&lock->lf_state->ls_locks); 410 overlap = NULL; 411 needtolink = 1; 412 for (;;) { 413 ovcase = lf_findoverlap(block, lock, SELF, &overlap); 414 if (ovcase) 415 block = TAILQ_NEXT(overlap, lf_entry); 416 /* 417 * Six cases: 418 * 0) no overlap 419 * 1) overlap == lock 420 * 2) overlap contains lock 421 * 3) lock contains overlap 422 * 4) overlap starts before lock 423 * 5) overlap ends after lock 424 */ 425 switch (ovcase) { 426 case 0: /* no overlap */ 427 if (needtolink) { 428 if (overlap) /* insert before overlap */ 429 TAILQ_INSERT_BEFORE(overlap, lock, 430 lf_entry); 431 else /* first or last lock in list */ 432 TAILQ_INSERT_TAIL(&lock->lf_state->ls_locks, 433 lock, lf_entry); 434 } 435 break; 436 case 1: /* overlap == lock */ 437 /* 438 * If downgrading lock, others may be 439 * able to acquire it. 440 */ 441 if (lock->lf_type == F_RDLCK && 442 overlap->lf_type == F_WRLCK) 443 lf_wakelock(overlap, 0); 444 overlap->lf_type = lock->lf_type; 445 lf_free(lock); 446 lock = overlap; /* for debug output below */ 447 break; 448 case 2: /* overlap contains lock */ 449 /* 450 * Check for common starting point and different types. 451 */ 452 if (overlap->lf_type == lock->lf_type) { 453 lf_free(lock); 454 lock = overlap; /* for debug output below */ 455 break; 456 } 457 if (overlap->lf_start == lock->lf_start) { 458 if (!needtolink) 459 TAILQ_REMOVE(&lock->lf_state->ls_locks, 460 lock, lf_entry); 461 TAILQ_INSERT_BEFORE(overlap, lock, lf_entry); 462 overlap->lf_start = lock->lf_end + 1; 463 } else 464 lf_split(overlap, lock); 465 lf_wakelock(overlap, 0); 466 break; 467 case 3: /* lock contains overlap */ 468 /* 469 * If downgrading lock, others may be able to 470 * acquire it, otherwise take the list. 471 */ 472 if (lock->lf_type == F_RDLCK && 473 overlap->lf_type == F_WRLCK) { 474 lf_wakelock(overlap, 0); 475 } else { 476 while ((ltmp = 477 TAILQ_FIRST(&overlap->lf_blkhd))) { 478 TAILQ_REMOVE(&overlap->lf_blkhd, ltmp, 479 lf_block); 480 ltmp->lf_blk = lock; 481 TAILQ_INSERT_TAIL(&lock->lf_blkhd, 482 ltmp, lf_block); 483 } 484 } 485 /* 486 * Add the new lock if necessary and delete the overlap. 487 */ 488 if (needtolink) { 489 TAILQ_INSERT_BEFORE(overlap, lock, lf_entry); 490 needtolink = 0; 491 } 492 TAILQ_REMOVE(&lock->lf_state->ls_locks, overlap, lf_entry); 493 lf_free(overlap); 494 continue; 495 case 4: /* overlap starts before lock */ 496 /* 497 * Add lock after overlap on the list. 498 */ 499 if (!needtolink) 500 TAILQ_REMOVE(&lock->lf_state->ls_locks, lock, 501 lf_entry); 502 TAILQ_INSERT_AFTER(&lock->lf_state->ls_locks, overlap, 503 lock, lf_entry); 504 overlap->lf_end = lock->lf_start - 1; 505 lf_wakelock(overlap, 0); 506 needtolink = 0; 507 continue; 508 case 5: /* overlap ends after lock */ 509 /* 510 * Add the new lock before overlap. 511 */ 512 if (needtolink) 513 TAILQ_INSERT_BEFORE(overlap, lock, lf_entry); 514 overlap->lf_start = lock->lf_end + 1; 515 lf_wakelock(overlap, 0); 516 break; 517 } 518 break; 519 } 520 LFPRINT(("lf_setlock: got the lock", lock), DEBUG_SETLOCK); 521 return (0); 522 } 523 524 /* 525 * Remove a byte-range lock on an inode. 526 * 527 * Generally, find the lock (or an overlap to that lock) 528 * and remove it (or shrink it), then wakeup anyone we can. 529 */ 530 int 531 lf_clearlock(struct lockf *lock) 532 { 533 struct lockf *lf, *overlap; 534 int ovcase; 535 536 rw_assert_wrlock(&lockf_lock); 537 538 lf = TAILQ_FIRST(&lock->lf_state->ls_locks); 539 if (lf == NULL) 540 return (0); 541 542 LFPRINT(("lf_clearlock", lock), DEBUG_CLEARLOCK); 543 while ((ovcase = lf_findoverlap(lf, lock, SELF, &overlap))) { 544 lf_wakelock(overlap, 0); 545 546 switch (ovcase) { 547 case 1: /* overlap == lock */ 548 TAILQ_REMOVE(&lock->lf_state->ls_locks, overlap, 549 lf_entry); 550 lf_free(overlap); 551 break; 552 case 2: /* overlap contains lock: split it */ 553 if (overlap->lf_start == lock->lf_start) { 554 overlap->lf_start = lock->lf_end + 1; 555 break; 556 } 557 lf_split(overlap, lock); 558 /* 559 * The lock is now part of the list, lf_clearlock() must 560 * ensure that the lock remains detached from the list. 561 */ 562 TAILQ_REMOVE(&lock->lf_state->ls_locks, lock, lf_entry); 563 break; 564 case 3: /* lock contains overlap */ 565 lf = TAILQ_NEXT(overlap, lf_entry); 566 TAILQ_REMOVE(&lock->lf_state->ls_locks, overlap, 567 lf_entry); 568 lf_free(overlap); 569 continue; 570 case 4: /* overlap starts before lock */ 571 overlap->lf_end = lock->lf_start - 1; 572 lf = TAILQ_NEXT(overlap, lf_entry); 573 continue; 574 case 5: /* overlap ends after lock */ 575 overlap->lf_start = lock->lf_end + 1; 576 break; 577 } 578 break; 579 } 580 return (0); 581 } 582 583 /* 584 * Check whether there is a blocking lock, 585 * and if so return its process identifier. 586 */ 587 int 588 lf_getlock(struct lockf *lock, struct flock *fl) 589 { 590 struct lockf *block, *lf; 591 592 rw_assert_wrlock(&lockf_lock); 593 594 LFPRINT(("lf_getlock", lock), DEBUG_CLEARLOCK); 595 596 lf = TAILQ_FIRST(&lock->lf_state->ls_locks); 597 if ((block = lf_getblock(lf, lock)) != NULL) { 598 fl->l_type = block->lf_type; 599 fl->l_whence = SEEK_SET; 600 fl->l_start = block->lf_start; 601 if (block->lf_end == -1) 602 fl->l_len = 0; 603 else 604 fl->l_len = block->lf_end - block->lf_start + 1; 605 fl->l_pid = block->lf_pid; 606 } else { 607 fl->l_type = F_UNLCK; 608 } 609 return (0); 610 } 611 612 /* 613 * Walk the list of locks for an inode and 614 * return the first blocking lock. 615 */ 616 struct lockf * 617 lf_getblock(struct lockf *lf, struct lockf *lock) 618 { 619 struct lockf *overlap; 620 621 rw_assert_wrlock(&lockf_lock); 622 623 while (lf_findoverlap(lf, lock, OTHERS, &overlap) != 0) { 624 /* 625 * We've found an overlap, see if it blocks us 626 */ 627 if ((lock->lf_type == F_WRLCK || overlap->lf_type == F_WRLCK)) 628 return (overlap); 629 /* 630 * Nope, point to the next one on the list and 631 * see if it blocks us 632 */ 633 lf = TAILQ_NEXT(overlap, lf_entry); 634 } 635 return (NULL); 636 } 637 638 /* 639 * Walk the list of locks for an inode to 640 * find an overlapping lock (if any). 641 * 642 * NOTE: this returns only the FIRST overlapping lock. There 643 * may be more than one. 644 */ 645 int 646 lf_findoverlap(struct lockf *lf, struct lockf *lock, int type, 647 struct lockf **overlap) 648 { 649 off_t start, end; 650 651 rw_assert_wrlock(&lockf_lock); 652 653 LFPRINT(("lf_findoverlap: looking for overlap in", lock), DEBUG_FINDOVR); 654 655 *overlap = lf; 656 start = lock->lf_start; 657 end = lock->lf_end; 658 while (lf != NULL) { 659 if (((type & SELF) && lf->lf_id != lock->lf_id) || 660 ((type & OTHERS) && lf->lf_id == lock->lf_id)) { 661 *overlap = lf = TAILQ_NEXT(lf, lf_entry); 662 continue; 663 } 664 LFPRINT(("\tchecking", lf), DEBUG_FINDOVR); 665 /* 666 * OK, check for overlap 667 * 668 * Six cases: 669 * 0) no overlap 670 * 1) overlap == lock 671 * 2) overlap contains lock 672 * 3) lock contains overlap 673 * 4) overlap starts before lock 674 * 5) overlap ends after lock 675 */ 676 677 /* Case 0 */ 678 if ((lf->lf_end != -1 && start > lf->lf_end) || 679 (end != -1 && lf->lf_start > end)) { 680 DPRINTF(("no overlap\n"), DEBUG_FINDOVR); 681 if ((type & SELF) && end != -1 && lf->lf_start > end) 682 return (0); 683 *overlap = lf = TAILQ_NEXT(lf, lf_entry); 684 continue; 685 } 686 /* Case 1 */ 687 if ((lf->lf_start == start) && (lf->lf_end == end)) { 688 DPRINTF(("overlap == lock\n"), DEBUG_FINDOVR); 689 return (1); 690 } 691 /* Case 2 */ 692 if ((lf->lf_start <= start) && 693 (lf->lf_end == -1 || (end != -1 && lf->lf_end >= end))) { 694 DPRINTF(("overlap contains lock\n"), DEBUG_FINDOVR); 695 return (2); 696 } 697 /* Case 3 */ 698 if (start <= lf->lf_start && 699 (end == -1 || (lf->lf_end != -1 && end >= lf->lf_end))) { 700 DPRINTF(("lock contains overlap\n"), DEBUG_FINDOVR); 701 return (3); 702 } 703 /* Case 4 */ 704 if ((lf->lf_start < start) && 705 ((lf->lf_end >= start) || (lf->lf_end == -1))) { 706 DPRINTF(("overlap starts before lock\n"), 707 DEBUG_FINDOVR); 708 return (4); 709 } 710 /* Case 5 */ 711 if ((lf->lf_start > start) && (end != -1) && 712 ((lf->lf_end > end) || (lf->lf_end == -1))) { 713 DPRINTF(("overlap ends after lock\n"), DEBUG_FINDOVR); 714 return (5); 715 } 716 panic("lf_findoverlap: default"); 717 } 718 return (0); 719 } 720 721 /* 722 * Purge all locks associated with the given lock state. 723 */ 724 void 725 lf_purgelocks(struct lockf_state **state) 726 { 727 struct lockf_state *ls; 728 struct lockf *lock; 729 730 rw_enter_write(&lockf_lock); 731 732 ls = *state; 733 if (ls == NULL) 734 goto out; 735 736 ls_ref(ls); 737 738 /* Interrupt blocked locks and wait for all of them to finish. */ 739 TAILQ_FOREACH(lock, &ls->ls_locks, lf_entry) { 740 LFPRINT(("lf_purgelocks: wakeup", lock), DEBUG_SETLOCK); 741 lf_wakelock(lock, F_INTR); 742 } 743 while (!TAILQ_EMPTY(&ls->ls_pending)) { 744 KERNEL_LOCK(); 745 rwsleep(ls, &lockf_lock, PLOCK, "lockfp", 0); 746 KERNEL_UNLOCK(); 747 } 748 749 /* 750 * Any remaining locks cannot block other locks at this point and can 751 * safely be removed. 752 */ 753 while ((lock = TAILQ_FIRST(&ls->ls_locks))) { 754 TAILQ_REMOVE(&ls->ls_locks, lock, lf_entry); 755 lf_free(lock); 756 } 757 758 /* This is the last expected thread to hold a lock state reference. */ 759 #ifdef LOCKF_DIAGNOSTIC 760 KASSERT(ls->ls_refs == 1); 761 #endif 762 ls_rele(ls); 763 764 out: 765 rw_exit_write(&lockf_lock); 766 } 767 768 /* 769 * Split a lock and a contained region into 770 * two or three locks as necessary. 771 */ 772 void 773 lf_split(struct lockf *lock1, struct lockf *lock2) 774 { 775 struct lockf *splitlock; 776 777 rw_assert_wrlock(&lockf_lock); 778 779 LFPRINT(("lf_split", lock1), DEBUG_SPLIT); 780 LFPRINT(("splitting from", lock2), DEBUG_SPLIT); 781 782 /* 783 * Check to see if splitting into only two pieces. 784 */ 785 if (lock1->lf_start == lock2->lf_start) { 786 lock1->lf_start = lock2->lf_end + 1; 787 TAILQ_INSERT_BEFORE(lock1, lock2, lf_entry); 788 return; 789 } 790 if (lock1->lf_end == lock2->lf_end) { 791 lock1->lf_end = lock2->lf_start - 1; 792 TAILQ_INSERT_AFTER(&lock1->lf_state->ls_locks, lock1, lock2, 793 lf_entry); 794 return; 795 } 796 /* 797 * Make a new lock consisting of the last part of 798 * the encompassing lock 799 */ 800 splitlock = lf_alloc(lock1->lf_uid, 0); 801 splitlock->lf_flags = lock1->lf_flags; 802 splitlock->lf_type = lock1->lf_type; 803 splitlock->lf_start = lock2->lf_end + 1; 804 splitlock->lf_end = lock1->lf_end; 805 splitlock->lf_id = lock1->lf_id; 806 splitlock->lf_state = lock1->lf_state; 807 splitlock->lf_blk = NULL; 808 splitlock->lf_pid = lock1->lf_pid; 809 TAILQ_INIT(&splitlock->lf_blkhd); 810 ls_ref(splitlock->lf_state); 811 lock1->lf_end = lock2->lf_start - 1; 812 813 TAILQ_INSERT_AFTER(&lock1->lf_state->ls_locks, lock1, lock2, lf_entry); 814 TAILQ_INSERT_AFTER(&lock1->lf_state->ls_locks, lock2, splitlock, 815 lf_entry); 816 } 817 818 /* 819 * Wakeup a blocklist 820 */ 821 void 822 lf_wakelock(struct lockf *lock, int flags) 823 { 824 struct lockf *wakelock; 825 826 rw_assert_wrlock(&lockf_lock); 827 828 while ((wakelock = TAILQ_FIRST(&lock->lf_blkhd))) { 829 TAILQ_REMOVE(&lock->lf_blkhd, wakelock, lf_block); 830 wakelock->lf_blk = NULL; 831 wakelock->lf_flags |= flags; 832 wakeup_one(wakelock); 833 } 834 } 835 836 /* 837 * Returns non-zero if the given lock would cause a deadlock. 838 */ 839 int 840 lf_deadlock(struct lockf *lock) 841 { 842 struct lockf *block, *lf, *pending; 843 844 lf = TAILQ_FIRST(&lock->lf_state->ls_locks); 845 for (; (block = lf_getblock(lf, lock)) != NULL; 846 lf = TAILQ_NEXT(block, lf_entry)) { 847 if ((block->lf_flags & F_POSIX) == 0) 848 continue; 849 850 TAILQ_FOREACH(pending, &lock->lf_state->ls_pending, lf_entry) { 851 if (pending->lf_blk == NULL) 852 continue; /* lock already unblocked */ 853 854 if (pending->lf_pid == block->lf_pid && 855 pending->lf_blk->lf_pid == lock->lf_pid) 856 return (1); 857 } 858 } 859 860 return (0); 861 } 862 863 #ifdef LOCKF_DEBUG 864 /* 865 * Print out a lock. 866 */ 867 void 868 lf_print(const char *tag, struct lockf *lock) 869 { 870 struct lockf *block; 871 872 if (tag) 873 printf("%s: ", tag); 874 printf("lock %p", lock); 875 if (lock == NULL) { 876 printf("\n"); 877 return; 878 } 879 printf(", %s %p %s, start %lld, end %lld", 880 lock->lf_flags & F_POSIX ? "posix" : "flock", 881 lock->lf_id, 882 lock->lf_type == F_RDLCK ? "shared" : 883 lock->lf_type == F_WRLCK ? "exclusive" : 884 lock->lf_type == F_UNLCK ? "unlock" : 885 "unknown", lock->lf_start, lock->lf_end); 886 printf(", next %p, state %p", 887 TAILQ_NEXT(lock, lf_entry), lock->lf_state); 888 block = TAILQ_FIRST(&lock->lf_blkhd); 889 if (block) 890 printf(", block"); 891 TAILQ_FOREACH(block, &lock->lf_blkhd, lf_block) 892 printf(" %p,", block); 893 printf("\n"); 894 } 895 896 void 897 lf_printlist(const char *tag, struct lockf *lock) 898 { 899 struct lockf *lf; 900 901 printf("%s: Lock list:\n", tag); 902 TAILQ_FOREACH(lf, &lock->lf_state->ls_locks, lf_entry) { 903 if (lock == lf) 904 printf(" * "); 905 else 906 printf(" "); 907 lf_print(NULL, lf); 908 } 909 } 910 #endif /* LOCKF_DEBUG */ 911