1 /* 2 * Copyright (c) 2004 Joerg Sonnenberger <joerg@bec.de>. All rights reserved. 3 * Copyright (c) 2006 Matthew Dillon <dillon@backplane.com>. All rights reserved. 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 * $FreeBSD: src/sys/kern/kern_lockf.c,v 1.25 1999/11/16 16:28:56 phk Exp $ 37 */ 38 39 #include "opt_debug_lockf.h" 40 41 #include <sys/param.h> 42 #include <sys/systm.h> 43 #include <sys/kernel.h> 44 #include <sys/lock.h> 45 #include <sys/proc.h> 46 #include <sys/unistd.h> 47 #include <sys/vnode.h> 48 #include <sys/malloc.h> 49 #include <sys/fcntl.h> 50 #include <sys/resourcevar.h> 51 52 #include <sys/lockf.h> 53 #include <machine/limits.h> /* for LLONG_MAX */ 54 #include <machine/stdarg.h> 55 56 #include <sys/spinlock2.h> 57 58 #ifdef INVARIANTS 59 int lf_global_counter = 0; 60 #endif 61 62 #ifdef LOCKF_DEBUG 63 int lf_print_ranges = 0; 64 65 static void _lf_print_lock(const struct lockf *); 66 static void _lf_printf(const char *, ...) __printflike(1, 2); 67 68 #define lf_print_lock(lock) if (lf_print_ranges) _lf_print_lock(lock) 69 #define lf_printf(ctl, args...) if (lf_print_ranges) _lf_printf(ctl, args) 70 #else 71 #define lf_print_lock(lock) 72 #define lf_printf(ctl, args...) 73 #endif 74 75 static MALLOC_DEFINE(M_LOCKF, "lockf", "Byte-range locking structures"); 76 77 static void lf_wakeup(struct lockf *, off_t, off_t); 78 static struct lockf_range *lf_alloc_range(void); 79 static void lf_create_range(struct lockf_range *, struct proc *, int, int, 80 off_t, off_t); 81 static void lf_insert(struct lockf_range_list *list, 82 struct lockf_range *elm, 83 struct lockf_range *insert_point); 84 static void lf_destroy_range(struct lockf_range *); 85 86 static int lf_setlock(struct lockf *, struct proc *, int, int, 87 off_t, off_t); 88 static int lf_getlock(struct flock *, struct lockf *, struct proc *, 89 int, int, off_t, off_t); 90 91 static int lf_count_change(struct proc *, int); 92 93 /* 94 * Return TRUE (non-zero) if the type and posix flags match. 95 */ 96 static __inline 97 int 98 lf_match(struct lockf_range *range, int type, int flags) 99 { 100 if (range->lf_type != type) 101 return(0); 102 if ((range->lf_flags ^ flags) & F_POSIX) 103 return(0); 104 return(1); 105 } 106 107 /* 108 * Check whether range and [start, end] overlap. 109 */ 110 static __inline 111 int 112 lf_overlap(const struct lockf_range *range, off_t start, off_t end) 113 { 114 if (range->lf_start >= start && range->lf_start <= end) 115 return(1); 116 else if (start >= range->lf_start && start <= range->lf_end) 117 return(1); 118 else 119 return(0); 120 } 121 122 123 /* 124 * Change the POSIX lock accounting for the given process. 125 */ 126 void 127 lf_count_adjust(struct proc *p, int increase) 128 { 129 struct uidinfo *uip; 130 131 KKASSERT(p != NULL); 132 133 uip = p->p_ucred->cr_uidinfo; 134 if (increase) 135 atomic_add_int(&uip->ui_posixlocks, p->p_numposixlocks); 136 else 137 atomic_add_int(&uip->ui_posixlocks, -p->p_numposixlocks); 138 139 KASSERT(uip->ui_posixlocks >= 0, 140 ("Negative number of POSIX locks held by %s user: %d.", 141 increase ? "new" : "old", uip->ui_posixlocks)); 142 } 143 144 static int 145 lf_count_change(struct proc *owner, int diff) 146 { 147 struct uidinfo *uip; 148 int max, ret; 149 150 /* we might actually not have a process context */ 151 if (owner == NULL) 152 return(0); 153 154 uip = owner->p_ucred->cr_uidinfo; 155 156 max = MIN(owner->p_rlimit[RLIMIT_POSIXLOCKS].rlim_cur, 157 maxposixlocksperuid); 158 159 if (diff > 0 && owner->p_ucred->cr_uid != 0 && max != -1 && 160 uip->ui_posixlocks >= max ) { 161 ret = 1; 162 } else { 163 atomic_add_int(&uip->ui_posixlocks, diff); 164 atomic_add_int(&owner->p_numposixlocks, diff); 165 KASSERT(uip->ui_posixlocks >= 0, 166 ("Negative number of POSIX locks held by user: %d.", 167 uip->ui_posixlocks)); 168 KASSERT(owner->p_numposixlocks >= 0, 169 ("Negative number of POSIX locks held by proc: %d.", 170 uip->ui_posixlocks)); 171 ret = 0; 172 } 173 return ret; 174 } 175 176 /* 177 * Advisory record locking support 178 */ 179 int 180 lf_advlock(struct vop_advlock_args *ap, struct lockf *lock, u_quad_t size) 181 { 182 struct flock *fl = ap->a_fl; 183 struct proc *owner; 184 off_t start, end; 185 int type, flags, error; 186 lwkt_token_t token; 187 188 /* 189 * Convert the flock structure into a start and end. 190 */ 191 switch (fl->l_whence) { 192 case SEEK_SET: 193 case SEEK_CUR: 194 /* 195 * Caller is responsible for adding any necessary offset 196 * when SEEK_CUR is used. 197 */ 198 start = fl->l_start; 199 break; 200 201 case SEEK_END: 202 start = size + fl->l_start; 203 break; 204 205 default: 206 return(EINVAL); 207 } 208 209 flags = ap->a_flags; 210 if (start < 0) 211 return(EINVAL); 212 if (fl->l_len == 0) { 213 flags |= F_NOEND; 214 end = LLONG_MAX; 215 } else if (fl->l_len < 0) { 216 return(EINVAL); 217 } else { 218 end = start + fl->l_len - 1; 219 if (end < start) 220 return(EINVAL); 221 } 222 223 type = fl->l_type; 224 /* 225 * This isn't really correct for flock-style locks, 226 * but the current handling is somewhat broken anyway. 227 */ 228 owner = (struct proc *)ap->a_id; 229 230 /* 231 * Do the requested operation. 232 */ 233 token = lwkt_getpooltoken(lock); 234 235 if (lock->init_done == 0) { 236 TAILQ_INIT(&lock->lf_range); 237 TAILQ_INIT(&lock->lf_blocked); 238 lock->init_done = 1; 239 } 240 241 switch(ap->a_op) { 242 case F_SETLK: 243 /* 244 * NOTE: It is possible for both lf_range and lf_blocked to 245 * be empty if we block and get woken up, but another process 246 * then gets in and issues an unlock. So VMAYHAVELOCKS must 247 * be set after the lf_setlock() operation completes rather 248 * then before. 249 */ 250 error = lf_setlock(lock, owner, type, flags, start, end); 251 vsetflags(ap->a_vp, VMAYHAVELOCKS); 252 break; 253 254 case F_UNLCK: 255 error = lf_setlock(lock, owner, type, flags, start, end); 256 if (TAILQ_EMPTY(&lock->lf_range) && 257 TAILQ_EMPTY(&lock->lf_blocked)) { 258 vclrflags(ap->a_vp, VMAYHAVELOCKS); 259 } 260 break; 261 262 case F_GETLK: 263 error = lf_getlock(fl, lock, owner, type, flags, start, end); 264 break; 265 266 default: 267 error = EINVAL; 268 break; 269 } 270 lwkt_reltoken(token); 271 return(error); 272 } 273 274 static int 275 lf_setlock(struct lockf *lock, struct proc *owner, int type, int flags, 276 off_t start, off_t end) 277 { 278 struct lockf_range *range; 279 struct lockf_range *brange; 280 struct lockf_range *next; 281 struct lockf_range *first_match; 282 struct lockf_range *last_match; 283 struct lockf_range *insert_point; 284 struct lockf_range *new_range1; 285 struct lockf_range *new_range2; 286 int wakeup_needed; 287 int double_clip; 288 int unlock_override; 289 int error = 0; 290 int count; 291 struct lockf_range_list deadlist; 292 293 new_range1 = NULL; 294 new_range2 = NULL; 295 count = 0; 296 297 restart: 298 /* 299 * Preallocate two ranges so we don't have to worry about blocking 300 * in the middle of the lock code. 301 */ 302 if (new_range1 == NULL) 303 new_range1 = lf_alloc_range(); 304 if (new_range2 == NULL) 305 new_range2 = lf_alloc_range(); 306 first_match = NULL; 307 last_match = NULL; 308 insert_point = NULL; 309 wakeup_needed = 0; 310 311 lf_print_lock(lock); 312 313 /* 314 * Locate the insertion point for the new lock (the first range 315 * with an lf_start >= start). 316 * 317 * Locate the first and latch ranges owned by us that overlap 318 * the requested range. 319 */ 320 TAILQ_FOREACH(range, &lock->lf_range, lf_link) { 321 if (insert_point == NULL && range->lf_start >= start) 322 insert_point = range; 323 324 /* 325 * Skip non-overlapping locks. Locks are sorted by lf_start 326 * So we can terminate the search when lf_start exceeds the 327 * requested range (insert_point is still guarenteed to be 328 * set properly). 329 */ 330 if (range->lf_end < start) 331 continue; 332 if (range->lf_start > end) { 333 range = NULL; 334 break; 335 } 336 337 /* 338 * Overlapping lock. Set first_match and last_match if we 339 * are the owner. 340 */ 341 if (range->lf_owner == owner) { 342 if (first_match == NULL) 343 first_match = range; 344 last_match = range; 345 continue; 346 } 347 348 /* 349 * If we aren't the owner check for a conflicting lock. Only 350 * if not unlocking. 351 */ 352 if (type != F_UNLCK) { 353 if (type == F_WRLCK || range->lf_type == F_WRLCK) 354 break; 355 } 356 } 357 358 /* 359 * If a conflicting lock was observed, block or fail as appropriate. 360 * (this code is skipped when unlocking) 361 */ 362 if (range != NULL) { 363 if ((flags & F_WAIT) == 0) { 364 error = EAGAIN; 365 goto do_cleanup; 366 } 367 368 /* 369 * We are blocked. For POSIX locks we have to check 370 * for deadlocks and return with EDEADLK. This is done 371 * by checking whether range->lf_owner is already 372 * blocked. 373 * 374 * Since flock-style locks cover the whole file, a 375 * deadlock between those is nearly impossible. 376 * This can only occur if a process tries to lock the 377 * same inode exclusively while holding a shared lock 378 * with another descriptor. 379 * XXX How can we cleanly detect this? 380 * XXX The current mixing of flock & fcntl/lockf is evil. 381 * 382 * Handle existing locks of flock-style like POSIX locks. 383 */ 384 if (flags & F_POSIX) { 385 TAILQ_FOREACH(brange, &lock->lf_blocked, lf_link) { 386 if (brange->lf_owner == range->lf_owner) { 387 error = EDEADLK; 388 goto do_cleanup; 389 } 390 } 391 } 392 393 /* 394 * For flock-style locks, we must first remove 395 * any shared locks that we hold before we sleep 396 * waiting for an exclusive lock. 397 */ 398 if ((flags & F_POSIX) == 0 && type == F_WRLCK) 399 lf_setlock(lock, owner, F_UNLCK, 0, start, end); 400 401 brange = new_range1; 402 new_range1 = NULL; 403 lf_create_range(brange, owner, type, 0, start, end); 404 TAILQ_INSERT_TAIL(&lock->lf_blocked, brange, lf_link); 405 error = tsleep(brange, PCATCH, "lockf", 0); 406 407 /* 408 * We may have been awaked by a signal and/or by a 409 * debugger continuing us (in which case we must remove 410 * ourselves from the blocked list) and/or by another 411 * process releasing/downgrading a lock (in which case 412 * we have already been removed from the blocked list 413 * and our lf_flags field is 1). 414 * 415 * Sleep if it looks like we might be livelocking. 416 */ 417 if (brange->lf_flags == 0) 418 TAILQ_REMOVE(&lock->lf_blocked, brange, lf_link); 419 if (count == 2) 420 tsleep(brange, 0, "lockfz", 2); 421 else 422 ++count; 423 lf_destroy_range(brange); 424 425 if (error) 426 goto do_cleanup; 427 goto restart; 428 } 429 430 /* 431 * If there are no overlapping locks owned by us then creating 432 * the new lock is easy. This is the most common case. 433 */ 434 if (first_match == NULL) { 435 if (type == F_UNLCK) 436 goto do_wakeup; 437 if (flags & F_POSIX) { 438 if (lf_count_change(owner, 1)) { 439 error = ENOLCK; 440 goto do_cleanup; 441 } 442 } 443 range = new_range1; 444 new_range1 = NULL; 445 lf_create_range(range, owner, type, flags, start, end); 446 lf_insert(&lock->lf_range, range, insert_point); 447 goto do_wakeup; 448 } 449 450 /* 451 * double_clip - Calculate a special case where TWO locks may have 452 * to be added due to the new lock breaking up an 453 * existing incompatible lock in the middle. 454 * 455 * unlock_override - Calculate a special case where NO locks 456 * need to be created. This occurs when an unlock 457 * does not clip any locks at the front and rear. 458 * 459 * WARNING! closef() and fdrop() assume that an F_UNLCK of the 460 * entire range will always succeed so the unlock_override 461 * case is mandatory. 462 */ 463 double_clip = 0; 464 unlock_override = 0; 465 if (first_match->lf_start < start) { 466 if (first_match == last_match && last_match->lf_end > end) 467 double_clip = 1; 468 } else if (type == F_UNLCK && last_match->lf_end <= end) { 469 unlock_override = 1; 470 } 471 472 /* 473 * Figure out the worst case net increase in POSIX locks and account 474 * for it now before we start modifying things. If neither the 475 * first or last locks match we have an issue. If there is only 476 * one overlapping range which needs to be clipped on both ends 477 * we wind up having to create up to two new locks, else only one. 478 * 479 * When unlocking the worst case is always 1 new lock if our 480 * unlock request cuts the middle out of an existing lock range. 481 * 482 * count represents the 'cleanup' adjustment needed. It starts 483 * negative, is incremented whenever we create a new POSIX lock, 484 * and decremented whenever we delete an existing one. At the 485 * end of the day it had better be <= 0 or we didn't calculate the 486 * worse case properly here. 487 */ 488 count = 0; 489 if ((flags & F_POSIX) && !unlock_override) { 490 if (!lf_match(first_match, type, flags) && 491 !lf_match(last_match, type, flags) 492 ) { 493 if (double_clip && type != F_UNLCK) 494 count = -2; 495 else 496 count = -1; 497 } 498 if (count && lf_count_change(owner, -count)) { 499 error = ENOLCK; 500 goto do_cleanup; 501 } 502 } 503 /* else flock style lock which encompasses entire range */ 504 505 /* 506 * Create and insert the lock represented the requested range. 507 * Adjust the net POSIX lock count. We have to move our insertion 508 * point since brange now represents the first record >= start. 509 * 510 * When unlocking, no new lock is inserted but we still clip. 511 */ 512 if (type != F_UNLCK) { 513 brange = new_range1; 514 new_range1 = NULL; 515 lf_create_range(brange, owner, type, flags, start, end); 516 lf_insert(&lock->lf_range, brange, insert_point); 517 insert_point = brange; 518 if (flags & F_POSIX) 519 ++count; 520 } else { 521 brange = NULL; 522 } 523 524 /* 525 * Handle the double_clip case. This is the only case where 526 * we wind up having to add TWO locks. 527 */ 528 if (double_clip) { 529 KKASSERT(first_match == last_match); 530 last_match = new_range2; 531 new_range2 = NULL; 532 lf_create_range(last_match, first_match->lf_owner, 533 first_match->lf_type, first_match->lf_flags, 534 end + 1, first_match->lf_end); 535 first_match->lf_end = start - 1; 536 first_match->lf_flags &= ~F_NOEND; 537 538 /* 539 * Figure out where to insert the right side clip. 540 */ 541 lf_insert(&lock->lf_range, last_match, first_match); 542 if (last_match->lf_flags & F_POSIX) 543 ++count; 544 } 545 546 /* 547 * Clip or destroy the locks between first_match and last_match, 548 * inclusive. Ignore the primary lock we created (brange). Note 549 * that if double-clipped, first_match and last_match will be 550 * outside our clipping range. Otherwise first_match and last_match 551 * will be deleted. 552 * 553 * We have already taken care of any double clipping. 554 * 555 * The insert_point may become invalid as we delete records, do not 556 * use that pointer any more. Also, when removing something other 557 * then 'range' we have to check to see if the item we are removing 558 * is 'next' and adjust 'next' properly. 559 * 560 * NOTE: brange will be NULL if F_UNLCKing. 561 */ 562 TAILQ_INIT(&deadlist); 563 next = first_match; 564 565 while ((range = next) != NULL) { 566 next = TAILQ_NEXT(range, lf_link); 567 568 /* 569 * Ignore elements that we do not own and ignore the 570 * primary request range which we just created. 571 */ 572 if (range->lf_owner != owner || range == brange) 573 continue; 574 575 /* 576 * We may have to wakeup a waiter when downgrading a lock. 577 */ 578 if (type == F_UNLCK) 579 wakeup_needed = 1; 580 if (type == F_RDLCK && range->lf_type == F_WRLCK) 581 wakeup_needed = 1; 582 583 /* 584 * Clip left. This can only occur on first_match. 585 * 586 * Merge the left clip with brange if possible. This must 587 * be done specifically, not in the optimized merge heuristic 588 * below, since we may have counted on it in our 'count' 589 * calculation above. 590 */ 591 if (range->lf_start < start) { 592 KKASSERT(range == first_match); 593 if (brange && 594 range->lf_end >= start - 1 && 595 lf_match(range, type, flags)) { 596 range->lf_end = brange->lf_end; 597 range->lf_flags |= brange->lf_flags & F_NOEND; 598 /* 599 * Removing something other then 'range', 600 * adjust 'next' if necessary. 601 */ 602 if (next == brange) 603 next = TAILQ_NEXT(next, lf_link); 604 TAILQ_REMOVE(&lock->lf_range, brange, lf_link); 605 if (brange->lf_flags & F_POSIX) 606 --count; 607 TAILQ_INSERT_TAIL(&deadlist, brange, lf_link); 608 brange = range; 609 } else if (range->lf_end >= start) { 610 range->lf_end = start - 1; 611 if (type != F_UNLCK) 612 range->lf_flags &= ~F_NOEND; 613 } 614 if (range == last_match) 615 break; 616 continue; 617 } 618 619 /* 620 * Clip right. This can only occur on last_match. 621 * 622 * Merge the right clip if possible. This must be done 623 * specifically, not in the optimized merge heuristic 624 * below, since we may have counted on it in our 'count' 625 * calculation. 626 * 627 * Since we are adjusting lf_start, we have to move the 628 * record to maintain the sorted list. Since lf_start is 629 * only getting larger we can use the next element as the 630 * insert point (we don't have to backtrack). 631 */ 632 if (range->lf_end > end) { 633 KKASSERT(range == last_match); 634 if (brange && 635 range->lf_start <= end + 1 && 636 lf_match(range, type, flags)) { 637 brange->lf_end = range->lf_end; 638 brange->lf_flags |= range->lf_flags & F_NOEND; 639 TAILQ_REMOVE(&lock->lf_range, range, lf_link); 640 if (range->lf_flags & F_POSIX) 641 --count; 642 TAILQ_INSERT_TAIL(&deadlist, range, lf_link); 643 } else if (range->lf_start <= end) { 644 range->lf_start = end + 1; 645 TAILQ_REMOVE(&lock->lf_range, range, lf_link); 646 lf_insert(&lock->lf_range, range, next); 647 } 648 /* range == last_match, we are done */ 649 break; 650 } 651 652 /* 653 * The record must be entirely enclosed. Note that the 654 * record could be first_match or last_match, and will be 655 * deleted. 656 */ 657 KKASSERT(range->lf_start >= start && range->lf_end <= end); 658 TAILQ_REMOVE(&lock->lf_range, range, lf_link); 659 if (range->lf_flags & F_POSIX) 660 --count; 661 TAILQ_INSERT_TAIL(&deadlist, range, lf_link); 662 if (range == last_match) 663 break; 664 } 665 666 /* 667 * Attempt to merge locks adjacent to brange. For example, we may 668 * have had to clip first_match and/or last_match, and they might 669 * be adjacent. Or there might simply have been an adjacent lock 670 * already there. 671 * 672 * Don't get fancy, just check adjacent elements in the list if they 673 * happen to be owned by us. 674 * 675 * This case only gets hit if we have a situation where a shared 676 * and exclusive lock are adjacent, and the exclusive lock is 677 * downgraded to shared or the shared lock is upgraded to exclusive. 678 */ 679 if (brange) { 680 range = TAILQ_PREV(brange, lockf_range_list, lf_link); 681 if (range && 682 range->lf_owner == owner && 683 range->lf_end == brange->lf_start - 1 && 684 lf_match(range, type, flags) 685 ) { 686 /* 687 * Extend range to cover brange and scrap brange. 688 */ 689 range->lf_end = brange->lf_end; 690 range->lf_flags |= brange->lf_flags & F_NOEND; 691 TAILQ_REMOVE(&lock->lf_range, brange, lf_link); 692 if (brange->lf_flags & F_POSIX) 693 --count; 694 TAILQ_INSERT_TAIL(&deadlist, brange, lf_link); 695 brange = range; 696 } 697 range = TAILQ_NEXT(brange, lf_link); 698 if (range && 699 range->lf_owner == owner && 700 range->lf_start == brange->lf_end + 1 && 701 lf_match(range, type, flags) 702 ) { 703 /* 704 * Extend brange to cover range and scrap range. 705 */ 706 brange->lf_end = range->lf_end; 707 brange->lf_flags |= range->lf_flags & F_NOEND; 708 TAILQ_REMOVE(&lock->lf_range, range, lf_link); 709 if (range->lf_flags & F_POSIX) 710 --count; 711 TAILQ_INSERT_TAIL(&deadlist, range, lf_link); 712 } 713 } 714 715 /* 716 * Destroy deleted elements. We didn't want to do it in the loop 717 * because the free() might have blocked. 718 * 719 * Adjust the count for any posix locks we thought we might create 720 * but didn't. 721 */ 722 while ((range = TAILQ_FIRST(&deadlist)) != NULL) { 723 TAILQ_REMOVE(&deadlist, range, lf_link); 724 lf_destroy_range(range); 725 } 726 727 KKASSERT(count <= 0); 728 if (count < 0) 729 lf_count_change(owner, count); 730 do_wakeup: 731 lf_print_lock(lock); 732 if (wakeup_needed) 733 lf_wakeup(lock, start, end); 734 error = 0; 735 do_cleanup: 736 if (new_range1 != NULL) 737 lf_destroy_range(new_range1); 738 if (new_range2 != NULL) 739 lf_destroy_range(new_range2); 740 return(error); 741 } 742 743 /* 744 * Check whether there is a blocking lock, 745 * and if so return its process identifier. 746 */ 747 static int 748 lf_getlock(struct flock *fl, struct lockf *lock, struct proc *owner, 749 int type, int flags, off_t start, off_t end) 750 { 751 struct lockf_range *range; 752 753 TAILQ_FOREACH(range, &lock->lf_range, lf_link) 754 if (range->lf_owner != owner && 755 lf_overlap(range, start, end) && 756 (type == F_WRLCK || range->lf_type == F_WRLCK)) 757 break; 758 if (range == NULL) { 759 fl->l_type = F_UNLCK; 760 return(0); 761 } 762 fl->l_type = range->lf_type; 763 fl->l_whence = SEEK_SET; 764 fl->l_start = range->lf_start; 765 if (range->lf_flags & F_NOEND) 766 fl->l_len = 0; 767 else 768 fl->l_len = range->lf_end - range->lf_start + 1; 769 if (range->lf_owner != NULL && (range->lf_flags & F_POSIX)) 770 fl->l_pid = range->lf_owner->p_pid; 771 else 772 fl->l_pid = -1; 773 return(0); 774 } 775 776 /* 777 * Wakeup pending lock attempts. Theoretically we can stop as soon as 778 * we encounter an exclusive request that covers the whole range (at least 779 * insofar as the sleep code above calls lf_wakeup() if it would otherwise 780 * exit instead of loop), but for now just wakeup all overlapping 781 * requests. XXX 782 */ 783 static void 784 lf_wakeup(struct lockf *lock, off_t start, off_t end) 785 { 786 struct lockf_range *range, *nrange; 787 788 TAILQ_FOREACH_MUTABLE(range, &lock->lf_blocked, lf_link, nrange) { 789 if (lf_overlap(range, start, end) == 0) 790 continue; 791 TAILQ_REMOVE(&lock->lf_blocked, range, lf_link); 792 range->lf_flags = 1; 793 wakeup(range); 794 } 795 } 796 797 /* 798 * Allocate a range structure and initialize it sufficiently such that 799 * lf_destroy_range() does not barf. 800 */ 801 static struct lockf_range * 802 lf_alloc_range(void) 803 { 804 struct lockf_range *range; 805 806 #ifdef INVARIANTS 807 atomic_add_int(&lf_global_counter, 1); 808 #endif 809 range = kmalloc(sizeof(struct lockf_range), M_LOCKF, M_WAITOK); 810 range->lf_owner = NULL; 811 return(range); 812 } 813 814 static void 815 lf_insert(struct lockf_range_list *list, struct lockf_range *elm, 816 struct lockf_range *insert_point) 817 { 818 while (insert_point && insert_point->lf_start < elm->lf_start) 819 insert_point = TAILQ_NEXT(insert_point, lf_link); 820 if (insert_point != NULL) 821 TAILQ_INSERT_BEFORE(insert_point, elm, lf_link); 822 else 823 TAILQ_INSERT_TAIL(list, elm, lf_link); 824 } 825 826 static void 827 lf_create_range(struct lockf_range *range, struct proc *owner, int type, 828 int flags, off_t start, off_t end) 829 { 830 KKASSERT(start <= end); 831 range->lf_type = type; 832 range->lf_flags = flags; 833 range->lf_start = start; 834 range->lf_end = end; 835 range->lf_owner = owner; 836 837 lf_printf("lf_create_range: %ju..%ju\n", 838 (uintmax_t)range->lf_start, (uintmax_t)range->lf_end); 839 } 840 841 static void 842 lf_destroy_range(struct lockf_range *range) 843 { 844 lf_printf("lf_destroy_range: %ju..%ju\n", 845 (uintmax_t)range->lf_start, (uintmax_t)range->lf_end); 846 kfree(range, M_LOCKF); 847 #ifdef INVARIANTS 848 atomic_add_int(&lf_global_counter, -1); 849 KKASSERT(lf_global_counter >= 0); 850 #endif 851 } 852 853 #ifdef LOCKF_DEBUG 854 855 static void 856 _lf_printf(const char *ctl, ...) 857 { 858 struct proc *p; 859 __va_list va; 860 861 if (lf_print_ranges) { 862 if ((p = curproc) != NULL) 863 kprintf("pid %d (%s): ", p->p_pid, p->p_comm); 864 } 865 __va_start(va, ctl); 866 kvprintf(ctl, va); 867 __va_end(va); 868 } 869 870 static void 871 _lf_print_lock(const struct lockf *lock) 872 { 873 struct lockf_range *range; 874 875 if (lf_print_ranges == 0) 876 return; 877 878 if (TAILQ_EMPTY(&lock->lf_range)) { 879 lf_printf("lockf %p: no ranges locked\n", lock); 880 } else { 881 lf_printf("lockf %p:\n", lock); 882 } 883 TAILQ_FOREACH(range, &lock->lf_range, lf_link) 884 kprintf("\t%jd..%jd type %s owned by %d\n", 885 (uintmax_t)range->lf_start, (uintmax_t)range->lf_end, 886 range->lf_type == F_RDLCK ? "shared" : "exclusive", 887 range->lf_flags & F_POSIX ? range->lf_owner->p_pid : -1); 888 if (TAILQ_EMPTY(&lock->lf_blocked)) 889 kprintf("no process waiting for range\n"); 890 else 891 kprintf("blocked locks:"); 892 TAILQ_FOREACH(range, &lock->lf_blocked, lf_link) 893 kprintf("\t%jd..%jd type %s waiting on %p\n", 894 (uintmax_t)range->lf_start, (uintmax_t)range->lf_end, 895 range->lf_type == F_RDLCK ? "shared" : "exclusive", 896 range); 897 } 898 #endif /* LOCKF_DEBUG */ 899