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