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