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