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.1 (Berkeley) 06/11/93 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 off_t start, end; 354 355 #ifdef LOCKF_DEBUG 356 if (lockf_debug & 1) 357 lf_print("lf_getlock", lock); 358 #endif /* LOCKF_DEBUG */ 359 360 if (block = lf_getblock(lock)) { 361 fl->l_type = block->lf_type; 362 fl->l_whence = SEEK_SET; 363 fl->l_start = block->lf_start; 364 if (block->lf_end == -1) 365 fl->l_len = 0; 366 else 367 fl->l_len = block->lf_end - block->lf_start + 1; 368 if (block->lf_flags & F_POSIX) 369 fl->l_pid = ((struct proc *)(block->lf_id))->p_pid; 370 else 371 fl->l_pid = -1; 372 } else { 373 fl->l_type = F_UNLCK; 374 } 375 return (0); 376 } 377 378 /* 379 * Walk the list of locks for an inode and 380 * return the first blocking lock. 381 */ 382 struct lockf * 383 lf_getblock(lock) 384 register struct lockf *lock; 385 { 386 struct lockf **prev, *overlap, *lf = lock->lf_inode->i_lockf; 387 int ovcase; 388 389 prev = &lock->lf_inode->i_lockf; 390 while (ovcase = lf_findoverlap(lf, lock, OTHERS, &prev, &overlap)) { 391 /* 392 * We've found an overlap, see if it blocks us 393 */ 394 if ((lock->lf_type == F_WRLCK || overlap->lf_type == F_WRLCK)) 395 return (overlap); 396 /* 397 * Nope, point to the next one on the list and 398 * see if it blocks us 399 */ 400 lf = overlap->lf_next; 401 } 402 return (NOLOCKF); 403 } 404 405 /* 406 * Walk the list of locks for an inode to 407 * find an overlapping lock (if any). 408 * 409 * NOTE: this returns only the FIRST overlapping lock. There 410 * may be more than one. 411 */ 412 int 413 lf_findoverlap(lf, lock, type, prev, overlap) 414 register struct lockf *lf; 415 struct lockf *lock; 416 int type; 417 struct lockf ***prev; 418 struct lockf **overlap; 419 { 420 off_t start, end; 421 422 *overlap = lf; 423 if (lf == NOLOCKF) 424 return (0); 425 #ifdef LOCKF_DEBUG 426 if (lockf_debug & 2) 427 lf_print("lf_findoverlap: looking for overlap in", lock); 428 #endif /* LOCKF_DEBUG */ 429 start = lock->lf_start; 430 end = lock->lf_end; 431 while (lf != NOLOCKF) { 432 if (((type & SELF) && lf->lf_id != lock->lf_id) || 433 ((type & OTHERS) && lf->lf_id == lock->lf_id)) { 434 *prev = &lf->lf_next; 435 *overlap = lf = lf->lf_next; 436 continue; 437 } 438 #ifdef LOCKF_DEBUG 439 if (lockf_debug & 2) 440 lf_print("\tchecking", lf); 441 #endif /* LOCKF_DEBUG */ 442 /* 443 * OK, check for overlap 444 * 445 * Six cases: 446 * 0) no overlap 447 * 1) overlap == lock 448 * 2) overlap contains lock 449 * 3) lock contains overlap 450 * 4) overlap starts before lock 451 * 5) overlap ends after lock 452 */ 453 if ((lf->lf_end != -1 && start > lf->lf_end) || 454 (end != -1 && lf->lf_start > end)) { 455 /* Case 0 */ 456 #ifdef LOCKF_DEBUG 457 if (lockf_debug & 2) 458 printf("no overlap\n"); 459 #endif /* LOCKF_DEBUG */ 460 if ((type & SELF) && end != -1 && lf->lf_start > end) 461 return (0); 462 *prev = &lf->lf_next; 463 *overlap = lf = lf->lf_next; 464 continue; 465 } 466 if ((lf->lf_start == start) && (lf->lf_end == end)) { 467 /* Case 1 */ 468 #ifdef LOCKF_DEBUG 469 if (lockf_debug & 2) 470 printf("overlap == lock\n"); 471 #endif /* LOCKF_DEBUG */ 472 return (1); 473 } 474 if ((lf->lf_start <= start) && 475 (end != -1) && 476 ((lf->lf_end >= end) || (lf->lf_end == -1))) { 477 /* Case 2 */ 478 #ifdef LOCKF_DEBUG 479 if (lockf_debug & 2) 480 printf("overlap contains lock\n"); 481 #endif /* LOCKF_DEBUG */ 482 return (2); 483 } 484 if (start <= lf->lf_start && 485 (end == -1 || 486 (lf->lf_end != -1 && end >= lf->lf_end))) { 487 /* Case 3 */ 488 #ifdef LOCKF_DEBUG 489 if (lockf_debug & 2) 490 printf("lock contains overlap\n"); 491 #endif /* LOCKF_DEBUG */ 492 return (3); 493 } 494 if ((lf->lf_start < start) && 495 ((lf->lf_end >= start) || (lf->lf_end == -1))) { 496 /* Case 4 */ 497 #ifdef LOCKF_DEBUG 498 if (lockf_debug & 2) 499 printf("overlap starts before lock\n"); 500 #endif /* LOCKF_DEBUG */ 501 return (4); 502 } 503 if ((lf->lf_start > start) && 504 (end != -1) && 505 ((lf->lf_end > end) || (lf->lf_end == -1))) { 506 /* Case 5 */ 507 #ifdef LOCKF_DEBUG 508 if (lockf_debug & 2) 509 printf("overlap ends after lock\n"); 510 #endif /* LOCKF_DEBUG */ 511 return (5); 512 } 513 panic("lf_findoverlap: default"); 514 } 515 return (0); 516 } 517 518 /* 519 * Add a lock to the end of the blocked list. 520 */ 521 void 522 lf_addblock(lock, blocked) 523 struct lockf *lock; 524 struct lockf *blocked; 525 { 526 register struct lockf *lf; 527 528 if (blocked == NOLOCKF) 529 return; 530 #ifdef LOCKF_DEBUG 531 if (lockf_debug & 2) { 532 lf_print("addblock: adding", blocked); 533 lf_print("to blocked list of", lock); 534 } 535 #endif /* LOCKF_DEBUG */ 536 if ((lf = lock->lf_block) == NOLOCKF) { 537 lock->lf_block = blocked; 538 return; 539 } 540 while (lf->lf_block != NOLOCKF) 541 lf = lf->lf_block; 542 lf->lf_block = blocked; 543 return; 544 } 545 546 /* 547 * Split a lock and a contained region into 548 * two or three locks as necessary. 549 */ 550 void 551 lf_split(lock1, lock2) 552 register struct lockf *lock1; 553 register struct lockf *lock2; 554 { 555 register struct lockf *splitlock; 556 557 #ifdef LOCKF_DEBUG 558 if (lockf_debug & 2) { 559 lf_print("lf_split", lock1); 560 lf_print("splitting from", lock2); 561 } 562 #endif /* LOCKF_DEBUG */ 563 /* 564 * Check to see if spliting into only two pieces. 565 */ 566 if (lock1->lf_start == lock2->lf_start) { 567 lock1->lf_start = lock2->lf_end + 1; 568 lock2->lf_next = lock1; 569 return; 570 } 571 if (lock1->lf_end == lock2->lf_end) { 572 lock1->lf_end = lock2->lf_start - 1; 573 lock2->lf_next = lock1->lf_next; 574 lock1->lf_next = lock2; 575 return; 576 } 577 /* 578 * Make a new lock consisting of the last part of 579 * the encompassing lock 580 */ 581 MALLOC(splitlock, struct lockf *, sizeof *splitlock, M_LOCKF, M_WAITOK); 582 bcopy((caddr_t)lock1, (caddr_t)splitlock, sizeof *splitlock); 583 splitlock->lf_start = lock2->lf_end + 1; 584 splitlock->lf_block = NOLOCKF; 585 lock1->lf_end = lock2->lf_start - 1; 586 /* 587 * OK, now link it in 588 */ 589 splitlock->lf_next = lock1->lf_next; 590 lock2->lf_next = splitlock; 591 lock1->lf_next = lock2; 592 } 593 594 /* 595 * Wakeup a blocklist 596 */ 597 void 598 lf_wakelock(listhead) 599 struct lockf *listhead; 600 { 601 register struct lockf *blocklist, *wakelock; 602 603 blocklist = listhead->lf_block; 604 listhead->lf_block = NOLOCKF; 605 while (blocklist != NOLOCKF) { 606 wakelock = blocklist; 607 blocklist = blocklist->lf_block; 608 wakelock->lf_block = NOLOCKF; 609 wakelock->lf_next = NOLOCKF; 610 #ifdef LOCKF_DEBUG 611 if (lockf_debug & 2) 612 lf_print("lf_wakelock: awakening", wakelock); 613 #endif /* LOCKF_DEBUG */ 614 wakeup((caddr_t)wakelock); 615 } 616 } 617 618 #ifdef LOCKF_DEBUG 619 /* 620 * Print out a lock. 621 */ 622 void 623 lf_print(tag, lock) 624 char *tag; 625 register struct lockf *lock; 626 { 627 628 printf("%s: lock 0x%lx for ", tag, lock); 629 if (lock->lf_flags & F_POSIX) 630 printf("proc %d", ((struct proc *)(lock->lf_id))->p_pid); 631 else 632 printf("id 0x%x", lock->lf_id); 633 printf(" in ino %d on dev <%d, %d>, %s, start %d, end %d", 634 lock->lf_inode->i_number, 635 major(lock->lf_inode->i_dev), 636 minor(lock->lf_inode->i_dev), 637 lock->lf_type == F_RDLCK ? "shared" : 638 lock->lf_type == F_WRLCK ? "exclusive" : 639 lock->lf_type == F_UNLCK ? "unlock" : 640 "unknown", lock->lf_start, lock->lf_end); 641 if (lock->lf_block) 642 printf(" block 0x%x\n", lock->lf_block); 643 else 644 printf("\n"); 645 } 646 647 void 648 lf_printlist(tag, lock) 649 char *tag; 650 struct lockf *lock; 651 { 652 register struct lockf *lf; 653 654 printf("%s: Lock list for ino %d on dev <%d, %d>:\n", 655 tag, lock->lf_inode->i_number, 656 major(lock->lf_inode->i_dev), 657 minor(lock->lf_inode->i_dev)); 658 for (lf = lock->lf_inode->i_lockf; lf; lf = lf->lf_next) { 659 printf("\tlock 0x%lx for ", lf); 660 if (lf->lf_flags & F_POSIX) 661 printf("proc %d", ((struct proc *)(lf->lf_id))->p_pid); 662 else 663 printf("id 0x%x", lf->lf_id); 664 printf(", %s, start %d, end %d", 665 lf->lf_type == F_RDLCK ? "shared" : 666 lf->lf_type == F_WRLCK ? "exclusive" : 667 lf->lf_type == F_UNLCK ? "unlock" : 668 "unknown", lf->lf_start, lf->lf_end); 669 if (lf->lf_block) 670 printf(" block 0x%x\n", lf->lf_block); 671 else 672 printf("\n"); 673 } 674 } 675 #endif /* LOCKF_DEBUG */ 676