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