1 /* 2 * Copyright (c) 1982, 1986, 1989 Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Scooter Morris at Genentech Inc. 7 * 8 * %sccs.include.redist.c% 9 * 10 * @(#)ufs_lockf.c 7.9.1.1 (Berkeley) 12/19/91 11 */ 12 13 #include <sys/param.h> 14 #include <sys/systm.h> 15 #include <sys/kernel.h> 16 #include <sys/file.h> 17 #include <sys/proc.h> 18 #include <sys/vnode.h> 19 #include <sys/malloc.h> 20 #include <sys/fcntl.h> 21 22 #include <ufs/ufs/lockf.h> 23 #include <ufs/ufs/quota.h> 24 #include <ufs/ufs/inode.h> 25 #include <ufs/ufs/ufs_extern.h> 26 27 /* 28 * This variable controls the maximum number of processes that will 29 * be checked in doing deadlock detection. 30 */ 31 int maxlockdepth = MAXDEPTH; 32 33 #ifdef LOCKF_DEBUG 34 int lockf_debug = 0; 35 #endif 36 37 #define NOLOCKF (struct lockf *)0 38 #define SELF 0x1 39 #define OTHERS 0x2 40 41 #define HASBLOCK 0x100 42 43 /* 44 * Set a byte-range lock. 45 */ 46 int 47 lf_setlock(lock) 48 register struct lockf *lock; 49 { 50 register struct lockf *block; 51 struct inode *ip = lock->lf_inode; 52 struct lockf **prev, *overlap, *ltmp; 53 static char lockstr[] = "lockf"; 54 int ovcase, priority, needtolink, error; 55 56 #ifdef LOCKF_DEBUG 57 if (lockf_debug & 1) 58 lf_print("lf_setlock", lock); 59 #endif /* LOCKF_DEBUG */ 60 61 /* 62 * Set the priority 63 */ 64 priority = PLOCK; 65 if (lock->lf_type == F_WRLCK) 66 priority += 4; 67 priority |= PCATCH; 68 /* 69 * Scan lock list for this file looking for locks that would block us. 70 */ 71 while (block = lf_getblock(lock)) { 72 /* 73 * Free the structure and return if nonblocking. 74 */ 75 if ((lock->lf_flags & F_WAIT) == 0) { 76 FREE(lock, M_LOCKF); 77 return (EAGAIN); 78 } 79 /* 80 * We are blocked. Since flock style locks cover 81 * the whole file, there is no chance for deadlock. 82 * For byte-range locks we must check for deadlock. 83 * 84 * Deadlock detection is done by looking through the 85 * wait channels to see if there are any cycles that 86 * involve us. MAXDEPTH is set just to make sure we 87 * do not go off into neverland. 88 */ 89 if ((lock->lf_flags & F_POSIX) && 90 (block->lf_flags & F_POSIX)) { 91 register struct proc *wproc; 92 register struct lockf *waitblock; 93 int i = 0; 94 95 /* The block is waiting on something */ 96 wproc = (struct proc *)block->lf_id; 97 while (wproc->p_wchan && 98 (wproc->p_wmesg == lockstr) && 99 (i++ < maxlockdepth)) { 100 waitblock = (struct lockf *)wproc->p_wchan; 101 /* Get the owner of the blocking lock */ 102 waitblock = waitblock->lf_next; 103 if ((waitblock->lf_flags & F_POSIX) == 0) 104 break; 105 wproc = (struct proc *)waitblock->lf_id; 106 if (wproc == (struct proc *)lock->lf_id) { 107 free(lock, M_LOCKF); 108 return (EDEADLK); 109 } 110 } 111 } 112 /* 113 * For flock type locks, we must first remove 114 * any shared locks that we hold before we sleep 115 * waiting for an exclusive lock. 116 */ 117 if ((lock->lf_flags & F_FLOCK) && 118 lock->lf_type == F_WRLCK) { 119 lock->lf_type = F_UNLCK; 120 (void) lf_clearlock(lock); 121 lock->lf_type = F_WRLCK; 122 } 123 /* 124 * Add our lock to the blocked list and sleep until we're free. 125 * Remember who blocked us (for deadlock detection). 126 */ 127 lock->lf_next = block; 128 lf_addblock(block, lock); 129 #ifdef LOCKF_DEBUG 130 if (lockf_debug & 1) { 131 lf_print("lf_setlock: blocking on", block); 132 lf_printlist("lf_setlock", block); 133 } 134 #endif /* LOCKF_DEBUG */ 135 if (error = tsleep((caddr_t)lock, priority, lockstr, 0)) { 136 /* 137 * Delete ourselves from the waiting to lock list. 138 */ 139 for (block = lock->lf_next; 140 block != NOLOCKF; 141 block = block->lf_block) { 142 if (block->lf_block != lock) 143 continue; 144 block->lf_block = block->lf_block->lf_block; 145 block->lf_spare = block->lf_block->lf_block; 146 if ((block->lf_block->lf_flags & HASBLOCK) == 0) 147 block->lf_flags &= ~HASBLOCK; 148 free(lock, M_LOCKF); 149 return (error); 150 } 151 panic("lf_setlock: lost lock"); 152 } 153 } 154 /* 155 * No blocks!! Add the lock. Note that we will 156 * downgrade or upgrade any overlapping locks this 157 * process already owns. 158 * 159 * Skip over locks owned by other processes. 160 * Handle any locks that overlap and are owned by ourselves. 161 */ 162 prev = &ip->i_lockf; 163 block = ip->i_lockf; 164 needtolink = 1; 165 for (;;) { 166 if (ovcase = lf_findoverlap(block, lock, SELF, &prev, &overlap)) 167 block = overlap->lf_next; 168 /* 169 * Six cases: 170 * 0) no overlap 171 * 1) overlap == lock 172 * 2) overlap contains lock 173 * 3) lock contains overlap 174 * 4) overlap starts before lock 175 * 5) overlap ends after lock 176 */ 177 switch (ovcase) { 178 case 0: /* no overlap */ 179 if (needtolink) { 180 *prev = lock; 181 lock->lf_next = overlap; 182 } 183 break; 184 185 case 1: /* overlap == lock */ 186 /* 187 * If downgrading lock, others may be 188 * able to acquire it. 189 */ 190 if (lock->lf_type == F_RDLCK && 191 overlap->lf_type == F_WRLCK) 192 lf_wakelock(overlap); 193 overlap->lf_type = lock->lf_type; 194 FREE(lock, M_LOCKF); 195 lock = overlap; /* for debug output below */ 196 break; 197 198 case 2: /* overlap contains lock */ 199 /* 200 * Check for common starting point and different types. 201 */ 202 if (overlap->lf_type == lock->lf_type) { 203 free(lock, M_LOCKF); 204 lock = overlap; /* for debug output below */ 205 break; 206 } 207 if (overlap->lf_start == lock->lf_start) { 208 *prev = lock; 209 lock->lf_next = overlap; 210 overlap->lf_start = lock->lf_end + 1; 211 } else 212 lf_split(overlap, lock); 213 lf_wakelock(overlap); 214 break; 215 216 case 3: /* lock contains overlap */ 217 /* 218 * If downgrading lock, others may be able to 219 * acquire it, otherwise take the list. 220 */ 221 if (lock->lf_type == F_RDLCK && 222 overlap->lf_type == F_WRLCK) { 223 lf_wakelock(overlap); 224 } else { 225 ltmp = lock->lf_block; 226 lock->lf_block = overlap->lf_block; 227 lf_addblock(lock, ltmp); 228 } 229 /* 230 * Add the new lock if necessary and delete the overlap. 231 */ 232 if (needtolink) { 233 *prev = lock; 234 lock->lf_next = overlap->lf_next; 235 prev = &lock->lf_next; 236 needtolink = 0; 237 } else 238 *prev = overlap->lf_next; 239 free(overlap, M_LOCKF); 240 continue; 241 242 case 4: /* overlap starts before lock */ 243 /* 244 * Add lock after overlap on the list. 245 */ 246 lock->lf_next = overlap->lf_next; 247 overlap->lf_next = lock; 248 overlap->lf_end = lock->lf_start - 1; 249 prev = &lock->lf_next; 250 lf_wakelock(overlap); 251 needtolink = 0; 252 continue; 253 254 case 5: /* overlap ends after lock */ 255 /* 256 * Add the new lock before overlap. 257 */ 258 if (needtolink) { 259 *prev = lock; 260 lock->lf_next = overlap; 261 } 262 overlap->lf_start = lock->lf_end + 1; 263 lf_wakelock(overlap); 264 break; 265 } 266 break; 267 } 268 #ifdef LOCKF_DEBUG 269 if (lockf_debug & 1) { 270 lf_print("lf_setlock: got the lock", lock); 271 lf_printlist("lf_setlock", lock); 272 } 273 #endif /* LOCKF_DEBUG */ 274 return (0); 275 } 276 277 /* 278 * Remove a byte-range lock on an inode. 279 * 280 * Generally, find the lock (or an overlap to that lock) 281 * and remove it (or shrink it), then wakeup anyone we can. 282 */ 283 int 284 lf_clearlock(unlock) 285 register struct lockf *unlock; 286 { 287 struct inode *ip = unlock->lf_inode; 288 register struct lockf *lf = ip->i_lockf; 289 struct lockf *overlap, **prev; 290 int ovcase; 291 292 if (lf == NOLOCKF) 293 return (0); 294 #ifdef LOCKF_DEBUG 295 if (unlock->lf_type != F_UNLCK) 296 panic("lf_clearlock: bad type"); 297 if (lockf_debug & 1) 298 lf_print("lf_clearlock", unlock); 299 #endif /* LOCKF_DEBUG */ 300 prev = &ip->i_lockf; 301 while (ovcase = lf_findoverlap(lf, unlock, SELF, &prev, &overlap)) { 302 /* 303 * Wakeup the list of locks to be retried. 304 */ 305 lf_wakelock(overlap); 306 307 switch (ovcase) { 308 309 case 1: /* overlap == lock */ 310 *prev = overlap->lf_next; 311 FREE(overlap, M_LOCKF); 312 break; 313 314 case 2: /* overlap contains lock: split it */ 315 if (overlap->lf_start == unlock->lf_start) { 316 overlap->lf_start = unlock->lf_end + 1; 317 break; 318 } 319 lf_split(overlap, unlock); 320 overlap->lf_next = unlock->lf_next; 321 break; 322 323 case 3: /* lock contains overlap */ 324 *prev = overlap->lf_next; 325 lf = overlap->lf_next; 326 free(overlap, M_LOCKF); 327 continue; 328 329 case 4: /* overlap starts before lock */ 330 overlap->lf_end = unlock->lf_start - 1; 331 prev = &overlap->lf_next; 332 lf = overlap->lf_next; 333 continue; 334 335 case 5: /* overlap ends after lock */ 336 overlap->lf_start = unlock->lf_end + 1; 337 break; 338 } 339 break; 340 } 341 #ifdef LOCKF_DEBUG 342 if (lockf_debug & 1) 343 lf_printlist("lf_clearlock", unlock); 344 #endif /* LOCKF_DEBUG */ 345 return (0); 346 } 347 348 /* 349 * Check whether there is a blocking lock, 350 * and if so return its process identifier. 351 */ 352 int 353 lf_getlock(lock, fl) 354 register struct lockf *lock; 355 register struct flock *fl; 356 { 357 register struct lockf *block; 358 off_t start, end; 359 360 #ifdef LOCKF_DEBUG 361 if (lockf_debug & 1) 362 lf_print("lf_getlock", lock); 363 #endif /* LOCKF_DEBUG */ 364 365 if (block = lf_getblock(lock)) { 366 fl->l_type = block->lf_type; 367 fl->l_whence = SEEK_SET; 368 fl->l_start = block->lf_start; 369 if (block->lf_end == -1) 370 fl->l_len = 0; 371 else 372 fl->l_len = block->lf_end - block->lf_start + 1; 373 if (block->lf_flags & F_POSIX) 374 fl->l_pid = ((struct proc *)(block->lf_id))->p_pid; 375 else 376 fl->l_pid = -1; 377 } else { 378 fl->l_type = F_UNLCK; 379 } 380 return (0); 381 } 382 383 /* 384 * Walk the list of locks for an inode and 385 * return the first blocking lock. 386 */ 387 struct lockf * 388 lf_getblock(lock) 389 register struct lockf *lock; 390 { 391 struct lockf **prev, *overlap, *lf = lock->lf_inode->i_lockf; 392 int ovcase; 393 394 prev = &lock->lf_inode->i_lockf; 395 while (ovcase = lf_findoverlap(lf, lock, OTHERS, &prev, &overlap)) { 396 /* 397 * We've found an overlap, see if it blocks us 398 */ 399 if ((lock->lf_type == F_WRLCK || overlap->lf_type == F_WRLCK)) 400 return (overlap); 401 /* 402 * Nope, point to the next one on the list and 403 * see if it blocks us 404 */ 405 lf = overlap->lf_next; 406 } 407 return (NOLOCKF); 408 } 409 410 /* 411 * Walk the list of locks for an inode to 412 * find an overlapping lock (if any). 413 * 414 * NOTE: this returns only the FIRST overlapping lock. There 415 * may be more than one. 416 */ 417 int 418 lf_findoverlap(lf, lock, type, prev, overlap) 419 register struct lockf *lf; 420 struct lockf *lock; 421 int type; 422 struct lockf ***prev; 423 struct lockf **overlap; 424 { 425 off_t start, end; 426 427 *overlap = lf; 428 if (lf == NOLOCKF) 429 return (0); 430 #ifdef LOCKF_DEBUG 431 if (lockf_debug & 2) 432 lf_print("lf_findoverlap: looking for overlap in", lock); 433 #endif /* LOCKF_DEBUG */ 434 start = lock->lf_start; 435 end = lock->lf_end; 436 while (lf != NOLOCKF) { 437 if (((type & SELF) && lf->lf_id != lock->lf_id) || 438 ((type & OTHERS) && lf->lf_id == lock->lf_id)) { 439 *prev = &lf->lf_next; 440 *overlap = lf = lf->lf_next; 441 continue; 442 } 443 #ifdef LOCKF_DEBUG 444 if (lockf_debug & 2) 445 lf_print("\tchecking", lf); 446 #endif /* LOCKF_DEBUG */ 447 /* 448 * OK, check for overlap 449 * 450 * Six cases: 451 * 0) no overlap 452 * 1) overlap == lock 453 * 2) overlap contains lock 454 * 3) lock contains overlap 455 * 4) overlap starts before lock 456 * 5) overlap ends after lock 457 */ 458 if ((lf->lf_end != -1 && start > lf->lf_end) || 459 (end != -1 && lf->lf_start > end)) { 460 /* Case 0 */ 461 #ifdef LOCKF_DEBUG 462 if (lockf_debug & 2) 463 printf("no overlap\n"); 464 #endif /* LOCKF_DEBUG */ 465 if ((type & SELF) && end != -1 && lf->lf_start > end) 466 return (0); 467 *prev = &lf->lf_next; 468 *overlap = lf = lf->lf_next; 469 continue; 470 } 471 if ((lf->lf_start == start) && (lf->lf_end == end)) { 472 /* Case 1 */ 473 #ifdef LOCKF_DEBUG 474 if (lockf_debug & 2) 475 printf("overlap == lock\n"); 476 #endif /* LOCKF_DEBUG */ 477 return (1); 478 } 479 if ((lf->lf_start <= start) && 480 (end != -1) && 481 ((lf->lf_end >= end) || (lf->lf_end == -1))) { 482 /* Case 2 */ 483 #ifdef LOCKF_DEBUG 484 if (lockf_debug & 2) 485 printf("overlap contains lock\n"); 486 #endif /* LOCKF_DEBUG */ 487 return (2); 488 } 489 if (start <= lf->lf_start && 490 (end == -1 || 491 (lf->lf_end != -1 && end >= lf->lf_end))) { 492 /* Case 3 */ 493 #ifdef LOCKF_DEBUG 494 if (lockf_debug & 2) 495 printf("lock contains overlap\n"); 496 #endif /* LOCKF_DEBUG */ 497 return (3); 498 } 499 if ((lf->lf_start < start) && 500 ((lf->lf_end >= start) || (lf->lf_end == -1))) { 501 /* Case 4 */ 502 #ifdef LOCKF_DEBUG 503 if (lockf_debug & 2) 504 printf("overlap starts before lock\n"); 505 #endif /* LOCKF_DEBUG */ 506 return (4); 507 } 508 if ((lf->lf_start > start) && 509 (end != -1) && 510 ((lf->lf_end > end) || (lf->lf_end == -1))) { 511 /* Case 5 */ 512 #ifdef LOCKF_DEBUG 513 if (lockf_debug & 2) 514 printf("overlap ends after lock\n"); 515 #endif /* LOCKF_DEBUG */ 516 return (5); 517 } 518 panic("lf_findoverlap: default"); 519 } 520 return (0); 521 } 522 523 /* 524 * Add a lock to the end of the blocked list. 525 */ 526 void 527 lf_addblock(lock, blocked) 528 struct lockf *lock; 529 struct lockf *blocked; 530 { 531 register struct lockf *lf; 532 533 if (blocked == NOLOCKF) 534 return; 535 #ifdef LOCKF_DEBUG 536 if (lockf_debug & 2) { 537 lf_print("addblock: adding", blocked); 538 lf_print("to blocked list of", lock); 539 } 540 #endif /* LOCKF_DEBUG */ 541 if ((lf = lock->lf_block) == NOLOCKF) { 542 lock->lf_block = blocked; 543 lock->lf_spare = blocked; 544 lock->lf_flags |= HASBLOCK; 545 return; 546 } 547 while (lf->lf_block != NOLOCKF) 548 lf = lf->lf_block; 549 lf->lf_block = blocked; 550 lf->lf_spare = blocked; 551 lf->lf_flags |= HASBLOCK; 552 return; 553 } 554 555 /* 556 * Split a lock and a contained region into 557 * two or three locks as necessary. 558 */ 559 void 560 lf_split(lock1, lock2) 561 register struct lockf *lock1; 562 register struct lockf *lock2; 563 { 564 register struct lockf *splitlock; 565 566 #ifdef LOCKF_DEBUG 567 if (lockf_debug & 2) { 568 lf_print("lf_split", lock1); 569 lf_print("splitting from", lock2); 570 } 571 #endif /* LOCKF_DEBUG */ 572 /* 573 * Check to see if spliting into only two pieces. 574 */ 575 if (lock1->lf_start == lock2->lf_start) { 576 lock1->lf_start = lock2->lf_end + 1; 577 lock2->lf_next = lock1; 578 return; 579 } 580 if (lock1->lf_end == lock2->lf_end) { 581 lock1->lf_end = lock2->lf_start - 1; 582 lock2->lf_next = lock1->lf_next; 583 lock1->lf_next = lock2; 584 return; 585 } 586 /* 587 * Make a new lock consisting of the last part of 588 * the encompassing lock 589 */ 590 MALLOC(splitlock, struct lockf *, sizeof *splitlock, M_LOCKF, M_WAITOK); 591 bcopy((caddr_t)lock1, (caddr_t)splitlock, sizeof *splitlock); 592 splitlock->lf_start = lock2->lf_end + 1; 593 splitlock->lf_block = NOLOCKF; 594 splitlock->lf_spare = NOLOCKF; 595 lock1->lf_end = lock2->lf_start - 1; 596 /* 597 * OK, now link it in 598 */ 599 splitlock->lf_next = lock1->lf_next; 600 lock2->lf_next = splitlock; 601 lock1->lf_next = lock2; 602 } 603 604 /* 605 * Wakeup a blocklist 606 */ 607 void 608 lf_wakelock(listhead) 609 struct lockf *listhead; 610 { 611 register struct lockf *blocklist, *wakelock; 612 613 if (listhead->lf_block != NOLOCKF) { 614 if ((listhead->lf_flags & HASBLOCK) == 0) 615 panic("lf_wakelock: listhead unexpected ptr"); 616 if (listhead->lf_block != listhead->lf_spare) 617 panic("lf_wakelock: listhead corrupted ptr"); 618 } 619 blocklist = listhead->lf_block; 620 while (blocklist != NOLOCKF) { 621 wakelock = blocklist; 622 blocklist = blocklist->lf_block; 623 if (blocklist != NOLOCKF) { 624 if ((wakelock->lf_flags & HASBLOCK) == 0) 625 panic("lf_wakelock: unexpected ptr"); 626 if (wakelock->lf_block != wakelock->lf_spare) 627 panic("lf_wakelock: corrupted ptr"); 628 } 629 wakelock->lf_flags &= ~HASBLOCK; 630 wakelock->lf_spare = NOLOCKF; 631 wakelock->lf_block = NOLOCKF; 632 wakelock->lf_next = NOLOCKF; 633 #ifdef LOCKF_DEBUG 634 if (lockf_debug & 2) 635 lf_print("lf_wakelock: awakening", wakelock); 636 #endif /* LOCKF_DEBUG */ 637 wakeup((caddr_t)wakelock); 638 } 639 listhead->lf_flags &= ~HASBLOCK; 640 listhead->lf_spare = NOLOCKF; 641 listhead->lf_block = NOLOCKF; 642 } 643 644 #ifdef LOCKF_DEBUG 645 /* 646 * Print out a lock. 647 */ 648 void 649 lf_print(tag, lock) 650 char *tag; 651 register struct lockf *lock; 652 { 653 654 printf("%s: lock 0x%lx for ", tag, lock); 655 if (lock->lf_flags & F_POSIX) 656 printf("proc %d", ((struct proc *)(lock->lf_id))->p_pid); 657 else 658 printf("id 0x%x", lock->lf_id); 659 printf(" in ino %d on dev <%d, %d>, %s, start %d, end %d", 660 lock->lf_inode->i_number, 661 major(lock->lf_inode->i_dev), 662 minor(lock->lf_inode->i_dev), 663 lock->lf_type == F_RDLCK ? "shared" : 664 lock->lf_type == F_WRLCK ? "exclusive" : 665 lock->lf_type == F_UNLCK ? "unlock" : 666 "unknown", lock->lf_start, lock->lf_end); 667 if (lock->lf_block) 668 printf(" block 0x%x\n", lock->lf_block); 669 else 670 printf("\n"); 671 } 672 673 void 674 lf_printlist(tag, lock) 675 char *tag; 676 struct lockf *lock; 677 { 678 register struct lockf *lf; 679 680 printf("%s: Lock list for ino %d on dev <%d, %d>:\n", 681 tag, lock->lf_inode->i_number, 682 major(lock->lf_inode->i_dev), 683 minor(lock->lf_inode->i_dev)); 684 for (lf = lock->lf_inode->i_lockf; lf; lf = lf->lf_next) { 685 printf("\tlock 0x%lx for ", lf); 686 if (lf->lf_flags & F_POSIX) 687 printf("proc %d", ((struct proc *)(lf->lf_id))->p_pid); 688 else 689 printf("id 0x%x", lf->lf_id); 690 printf(", %s, start %d, end %d", 691 lf->lf_type == F_RDLCK ? "shared" : 692 lf->lf_type == F_WRLCK ? "exclusive" : 693 lf->lf_type == F_UNLCK ? "unlock" : 694 "unknown", lf->lf_start, lf->lf_end); 695 if (lf->lf_block) 696 printf(" block 0x%x\n", lf->lf_block); 697 else 698 printf("\n"); 699 } 700 } 701 #endif /* LOCKF_DEBUG */ 702