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