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