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