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.3 (Berkeley) 03/19/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 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 out: 251 #ifdef LOCKF_DEBUG 252 if (lockf_debug & 1) { 253 lf_print("lf_setlock: got the lock", lock); 254 lf_printlist("lf_setlock", lock); 255 } 256 #endif /* LOCKF_DEBUG */ 257 return (0); 258 } 259 260 /* 261 * Remove a byte-range lock on an inode. 262 * 263 * Generally, find the lock (or an overlap to that lock) 264 * and remove it (or shrink it), then wakeup anyone we can. 265 */ 266 lf_clearlock(unlock) 267 register struct lockf *unlock; 268 { 269 struct inode *ip = unlock->lf_inode; 270 register struct lockf *lf = ip->i_lockf; 271 struct lockf *overlap, **prev; 272 int ovcase; 273 274 if (lf == NOLOCKF) 275 return (0); 276 #ifdef LOCKF_DEBUG 277 if (unlock->lf_type != F_UNLCK) 278 panic("lf_clearlock: bad type"); 279 if (lockf_debug & 1) 280 lf_print("lf_clearlock", unlock); 281 #endif /* LOCKF_DEBUG */ 282 prev = &ip->i_lockf; 283 while (ovcase = lf_findoverlap(lf, unlock, SELF, &prev, &overlap)) { 284 /* 285 * Wakeup the list of locks to be retried. 286 */ 287 lf_wakelock(overlap); 288 289 switch (ovcase) { 290 291 case 1: /* overlap == lock */ 292 *prev = overlap->lf_next; 293 FREE(overlap, M_LOCKF); 294 break; 295 296 case 2: /* overlap contains lock: split it */ 297 if (overlap->lf_start == unlock->lf_start) { 298 overlap->lf_start = unlock->lf_end + 1; 299 break; 300 } 301 lf_split(overlap, unlock); 302 overlap->lf_next = unlock->lf_next; 303 break; 304 305 case 3: /* lock contains overlap */ 306 *prev = overlap->lf_next; 307 lf = overlap->lf_next; 308 free(overlap, M_LOCKF); 309 continue; 310 311 case 4: /* overlap starts before lock */ 312 overlap->lf_end = unlock->lf_start - 1; 313 prev = &overlap->lf_next; 314 lf = overlap->lf_next; 315 continue; 316 317 case 5: /* overlap ends after lock */ 318 overlap->lf_start = unlock->lf_end + 1; 319 break; 320 } 321 break; 322 } 323 #ifdef LOCKF_DEBUG 324 if (lockf_debug & 1) 325 lf_printlist("lf_clearlock", unlock); 326 #endif /* LOCKF_DEBUG */ 327 return (0); 328 } 329 330 /* 331 * Check whether there is a blocking lock, 332 * and if so return its process identifier. 333 */ 334 lf_getlock(lock, fl) 335 register struct lockf *lock; 336 register struct flock *fl; 337 { 338 register struct lockf *block; 339 off_t start, end; 340 341 #ifdef LOCKF_DEBUG 342 if (lockf_debug & 1) 343 lf_print("lf_getlock", lock); 344 #endif /* LOCKF_DEBUG */ 345 346 if (block = lf_getblock(lock)) { 347 fl->l_type = block->lf_type; 348 fl->l_whence = SEEK_SET; 349 fl->l_start = block->lf_start; 350 if (block->lf_end == -1) 351 fl->l_len = 0; 352 else 353 fl->l_len = block->lf_end - block->lf_start + 1; 354 if (block->lf_flags & F_POSIX) 355 fl->l_pid = ((struct proc *)(block->lf_id))->p_pid; 356 else 357 fl->l_pid = -1; 358 } 359 return (0); 360 } 361 362 /* 363 * Walk the list of locks for an inode and 364 * return the first blocking lock. 365 */ 366 struct lockf * 367 lf_getblock(lock) 368 register struct lockf *lock; 369 { 370 struct lockf **prev, *overlap, *lf = lock->lf_inode->i_lockf; 371 int ovcase; 372 373 prev = &lock->lf_inode->i_lockf; 374 while (ovcase = lf_findoverlap(lf, lock, OTHERS, &prev, &overlap)) { 375 /* 376 * We've found an overlap, see if it blocks us 377 */ 378 if ((lock->lf_type == F_WRLCK || overlap->lf_type == F_WRLCK)) 379 return (overlap); 380 /* 381 * Nope, point to the next one on the list and 382 * see if it blocks us 383 */ 384 lf = overlap->lf_next; 385 } 386 return (NOLOCKF); 387 } 388 389 /* 390 * Walk the list of locks for an inode to 391 * find an overlapping lock (if any). 392 * 393 * NOTE: this returns only the FIRST overlapping lock. There 394 * may be more than one. 395 */ 396 lf_findoverlap(lf, lock, type, prev, overlap) 397 register struct lockf *lf; 398 struct lockf *lock; 399 int type; 400 struct lockf ***prev; 401 struct lockf **overlap; 402 { 403 off_t start, end; 404 405 *overlap = lf; 406 if (lf == NOLOCKF) 407 return (0); 408 #ifdef LOCKF_DEBUG 409 if (lockf_debug & 2) 410 lf_print("lf_findoverlap: looking for overlap in", lock); 411 #endif /* LOCKF_DEBUG */ 412 start = lock->lf_start; 413 end = lock->lf_end; 414 while (lf != NOLOCKF) { 415 if (((type & SELF) && lf->lf_id != lock->lf_id) || 416 ((type & OTHERS) && lf->lf_id == lock->lf_id)) { 417 *prev = &lf->lf_next; 418 *overlap = lf = lf->lf_next; 419 continue; 420 } 421 #ifdef LOCKF_DEBUG 422 if (lockf_debug & 2) 423 lf_print("\tchecking", lf); 424 #endif /* LOCKF_DEBUG */ 425 /* 426 * OK, check for overlap 427 * 428 * Six cases: 429 * 0) no overlap 430 * 1) overlap == lock 431 * 2) overlap contains lock 432 * 3) lock contains overlap 433 * 4) overlap starts before lock 434 * 5) overlap ends after lock 435 */ 436 if ((lf->lf_end != -1 && start > lf->lf_end) || 437 (end != -1 && lf->lf_start > end)) { 438 /* Case 0 */ 439 #ifdef LOCKF_DEBUG 440 if (lockf_debug & 2) 441 printf("no overlap\n"); 442 #endif /* LOCKF_DEBUG */ 443 if ((type & SELF) && end != -1 && lf->lf_start > end) 444 return (0); 445 *prev = &lf->lf_next; 446 *overlap = lf = lf->lf_next; 447 continue; 448 } 449 if ((lf->lf_start == start) && (lf->lf_end == end)) { 450 /* Case 1 */ 451 #ifdef LOCKF_DEBUG 452 if (lockf_debug & 2) 453 printf("overlap == lock\n"); 454 #endif /* LOCKF_DEBUG */ 455 return (1); 456 } 457 if ((lf->lf_start <= start) && 458 (end != -1) && 459 ((lf->lf_end >= end) || (lf->lf_end == -1))) { 460 /* Case 2 */ 461 #ifdef LOCKF_DEBUG 462 if (lockf_debug & 2) 463 printf("overlap contains lock\n"); 464 #endif /* LOCKF_DEBUG */ 465 return (2); 466 } 467 if (start <= lf->lf_start && 468 (end == -1 || 469 (lf->lf_end != -1 && end >= lf->lf_end))) { 470 /* Case 3 */ 471 #ifdef LOCKF_DEBUG 472 if (lockf_debug & 2) 473 printf("lock contains overlap\n"); 474 #endif /* LOCKF_DEBUG */ 475 return (3); 476 } 477 if ((lf->lf_start < start) && 478 ((lf->lf_end >= start) || (lf->lf_end == -1))) { 479 /* Case 4 */ 480 #ifdef LOCKF_DEBUG 481 if (lockf_debug & 2) 482 printf("overlap starts before lock\n"); 483 #endif /* LOCKF_DEBUG */ 484 return (4); 485 } 486 if ((lf->lf_start > start) && 487 (end != -1) && 488 ((lf->lf_end > end) || (lf->lf_end == -1))) { 489 /* Case 5 */ 490 #ifdef LOCKF_DEBUG 491 if (lockf_debug & 2) 492 printf("overlap ends after lock\n"); 493 #endif /* LOCKF_DEBUG */ 494 return (5); 495 } 496 panic("lf_findoverlap: default"); 497 } 498 return (0); 499 } 500 501 /* 502 * Add a lock to the end of the blocked list. 503 */ 504 lf_addblock(lock, blocked) 505 struct lockf *lock; 506 struct lockf *blocked; 507 { 508 register struct lockf *lf; 509 510 if (blocked == NOLOCKF) 511 return; 512 #ifdef LOCKF_DEBUG 513 if (lockf_debug & 2) { 514 lf_print("addblock: adding", blocked); 515 lf_print("to blocked list of", lock); 516 } 517 #endif /* LOCKF_DEBUG */ 518 if ((lf = lock->lf_block) == NOLOCKF) { 519 lock->lf_block = blocked; 520 return; 521 } 522 while (lf->lf_block != NOLOCKF) 523 lf = lf->lf_block; 524 lf->lf_block = blocked; 525 return; 526 } 527 528 /* 529 * Split a lock and a contained region into 530 * two or three locks as necessary. 531 */ 532 lf_split(lock1, lock2) 533 register struct lockf *lock1; 534 register struct lockf *lock2; 535 { 536 register struct lockf *splitlock; 537 538 #ifdef LOCKF_DEBUG 539 if (lockf_debug & 2) { 540 lf_print("lf_split", lock1); 541 lf_print("splitting from", lock2); 542 } 543 #endif /* LOCKF_DEBUG */ 544 /* 545 * Check to see if spliting into only two pieces. 546 */ 547 if (lock1->lf_start == lock2->lf_start) { 548 lock1->lf_start = lock2->lf_end + 1; 549 lock2->lf_next = lock1; 550 return; 551 } 552 if (lock1->lf_end == lock2->lf_end) { 553 lock1->lf_end = lock2->lf_start - 1; 554 lock2->lf_next = lock1->lf_next; 555 lock1->lf_next = lock2; 556 return; 557 } 558 /* 559 * Make a new lock consisting of the last part of 560 * the encompassing lock 561 */ 562 MALLOC(splitlock, struct lockf *, sizeof *splitlock, M_LOCKF, M_WAITOK); 563 bcopy((caddr_t)lock1, (caddr_t)splitlock, sizeof *splitlock); 564 splitlock->lf_start = lock2->lf_end + 1; 565 splitlock->lf_block = NOLOCKF; 566 lock1->lf_end = lock2->lf_start - 1; 567 /* 568 * OK, now link it in 569 */ 570 splitlock->lf_next = lock1->lf_next; 571 lock2->lf_next = splitlock; 572 lock1->lf_next = lock2; 573 } 574 575 /* 576 * Wakeup a blocklist 577 */ 578 lf_wakelock(listhead) 579 struct lockf *listhead; 580 { 581 register struct lockf *blocklist, *wakelock; 582 583 blocklist = listhead->lf_block; 584 listhead->lf_block = NOLOCKF; 585 while (blocklist != NOLOCKF) { 586 wakelock = blocklist; 587 blocklist = blocklist->lf_block; 588 wakelock->lf_block = NOLOCKF; 589 wakelock->lf_next = NOLOCKF; 590 #ifdef LOCKF_DEBUG 591 if (lockf_debug & 2) 592 lf_print("lf_wakelock: awakening", wakelock); 593 #endif /* LOCKF_DEBUG */ 594 wakeup((caddr_t)wakelock); 595 } 596 } 597 598 #ifdef LOCKF_DEBUG 599 /* 600 * Print out a lock. 601 */ 602 lf_print(tag, lock) 603 char *tag; 604 register struct lockf *lock; 605 { 606 607 printf("%s: lock 0x%X for ", tag, lock); 608 if (lock->lf_flags & F_POSIX) 609 printf("proc %d", ((struct proc *)(lock->lf_id))->p_pid); 610 else 611 printf("id 0x%x", lock->lf_id); 612 printf(" in ino %d on dev <%d, %d>, %s, start %d, end %d", 613 lock->lf_inode->i_number, 614 major(lock->lf_inode->i_dev), 615 minor(lock->lf_inode->i_dev), 616 lock->lf_type == F_RDLCK ? "shared" : 617 lock->lf_type == F_WRLCK ? "exclusive" : 618 lock->lf_type == F_UNLCK ? "unlock" : 619 "unknown", lock->lf_start, lock->lf_end); 620 if (lock->lf_block) 621 printf(" block 0x%x\n", lock->lf_block); 622 else 623 printf("\n"); 624 } 625 626 lf_printlist(tag, lock) 627 char *tag; 628 struct lockf *lock; 629 { 630 register struct lockf *lf; 631 632 printf("%s: Lock list for ino %d on dev <%d, %d>:\n", 633 tag, lock->lf_inode->i_number, 634 major(lock->lf_inode->i_dev), 635 minor(lock->lf_inode->i_dev)); 636 for (lf = lock->lf_inode->i_lockf; lf; lf = lf->lf_next) { 637 printf("\tlock 0x%X for ", lf); 638 if (lf->lf_flags & F_POSIX) 639 printf("proc %d", ((struct proc *)(lf->lf_id))->p_pid); 640 else 641 printf("id 0x%x", lf->lf_id); 642 printf(", %s, start %d, end %d", 643 lf->lf_type == F_RDLCK ? "shared" : 644 lf->lf_type == F_WRLCK ? "exclusive" : 645 lf->lf_type == F_UNLCK ? "unlock" : 646 "unknown", lf->lf_start, lf->lf_end); 647 if (lf->lf_block) 648 printf(" block 0x%x\n", lf->lf_block); 649 else 650 printf("\n"); 651 } 652 } 653 #endif /* LOCKF_DEBUG */ 654