2 * Copyright (c) 2004 Joerg Sonnenberger <joerg@bec.de>. All rights reserved.
3 * Copyright (c) 2006 Matthew Dillon <dillon@backplane.com>. All rights reserved.
5 * Copyright (c) 1982, 1986, 1989, 1993
6 * The Regents of the University of California. All rights reserved.
8 * This code is derived from software contributed to Berkeley by
9 * Scooter Morris at Genentech Inc.
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * @(#)ufs_lockf.c 8.3 (Berkeley) 1/6/94
36 * $FreeBSD: src/sys/kern/kern_lockf.c,v 1.25 1999/11/16 16:28:56 phk Exp $
39 #include "opt_debug_lockf.h"
41 #include <sys/param.h>
42 #include <sys/systm.h>
43 #include <sys/kernel.h>
46 #include <sys/unistd.h>
47 #include <sys/vnode.h>
48 #include <sys/malloc.h>
49 #include <sys/fcntl.h>
50 #include <sys/resourcevar.h>
52 #include <sys/lockf.h>
53 #include <machine/limits.h> /* for LLONG_MAX */
54 #include <machine/stdarg.h>
56 #include <sys/spinlock2.h>
59 int lf_global_counter = 0;
63 int lf_print_ranges = 0;
65 static void _lf_print_lock(const struct lockf *);
66 static void _lf_printf(const char *, ...);
68 #define lf_print_lock(lock) if (lf_print_ranges) _lf_print_lock(lock)
69 #define lf_printf(ctl, args...) if (lf_print_ranges) _lf_printf(ctl, args)
71 #define lf_print_lock(lock)
72 #define lf_printf(ctl, args...)
75 static MALLOC_DEFINE(M_LOCKF, "lockf", "Byte-range locking structures");
77 static void lf_wakeup(struct lockf *, off_t, off_t);
78 static struct lockf_range *lf_alloc_range(void);
79 static void lf_create_range(struct lockf_range *, struct proc *, int, int,
81 static void lf_insert(struct lockf_range_list *list,
82 struct lockf_range *elm,
83 struct lockf_range *insert_point);
84 static void lf_destroy_range(struct lockf_range *);
86 static int lf_setlock(struct lockf *, struct proc *, int, int,
88 static int lf_getlock(struct flock *, struct lockf *, struct proc *,
89 int, int, off_t, off_t);
91 static int lf_count_change(struct proc *, int);
94 * Return TRUE (non-zero) if the type and posix flags match.
98 lf_match(struct lockf_range *range, int type, int flags)
100 if (range->lf_type != type)
102 if ((range->lf_flags ^ flags) & F_POSIX)
108 * Check whether range and [start, end] overlap.
112 lf_overlap(const struct lockf_range *range, off_t start, off_t end)
114 if (range->lf_start >= start && range->lf_start <= end)
116 else if (start >= range->lf_start && start <= range->lf_end)
124 * Change the POSIX lock accounting for the given process.
127 lf_count_adjust(struct proc *p, int increase)
133 uip = p->p_ucred->cr_uidinfo;
134 spin_lock(&uip->ui_lock);
137 uip->ui_posixlocks += p->p_numposixlocks;
139 uip->ui_posixlocks -= p->p_numposixlocks;
141 KASSERT(uip->ui_posixlocks >= 0,
142 ("Negative number of POSIX locks held by %s user: %d.",
143 increase ? "new" : "old", uip->ui_posixlocks));
144 spin_unlock(&uip->ui_lock);
148 lf_count_change(struct proc *owner, int diff)
153 /* we might actually not have a process context */
157 uip = owner->p_ucred->cr_uidinfo;
159 max = MIN(owner->p_rlimit[RLIMIT_POSIXLOCKS].rlim_cur,
160 maxposixlocksperuid);
162 spin_lock(&uip->ui_lock);
163 if (diff > 0 && owner->p_ucred->cr_uid != 0 && max != -1 &&
164 uip->ui_posixlocks >= max ) {
167 uip->ui_posixlocks += diff;
168 owner->p_numposixlocks += diff;
169 KASSERT(uip->ui_posixlocks >= 0,
170 ("Negative number of POSIX locks held by user: %d.",
171 uip->ui_posixlocks));
172 KASSERT(owner->p_numposixlocks >= 0,
173 ("Negative number of POSIX locks held by proc: %d.",
174 uip->ui_posixlocks));
177 spin_unlock(&uip->ui_lock);
182 * Advisory record locking support
185 lf_advlock(struct vop_advlock_args *ap, struct lockf *lock, u_quad_t size)
187 struct flock *fl = ap->a_fl;
190 int type, flags, error;
194 * Convert the flock structure into a start and end.
196 switch (fl->l_whence) {
200 * Caller is responsible for adding any necessary offset
201 * when SEEK_CUR is used.
207 start = size + fl->l_start;
217 if (fl->l_len == 0) {
220 } else if (fl->l_len < 0) {
223 end = start + fl->l_len - 1;
230 * This isn't really correct for flock-style locks,
231 * but the current handling is somewhat broken anyway.
233 owner = (struct proc *)ap->a_id;
236 * Do the requested operation.
238 token = lwkt_getpooltoken(lock);
240 if (lock->init_done == 0) {
241 TAILQ_INIT(&lock->lf_range);
242 TAILQ_INIT(&lock->lf_blocked);
249 * NOTE: It is possible for both lf_range and lf_blocked to
250 * be empty if we block and get woken up, but another process
251 * then gets in and issues an unlock. So VMAYHAVELOCKS must
252 * be set after the lf_setlock() operation completes rather
255 error = lf_setlock(lock, owner, type, flags, start, end);
256 vsetflags(ap->a_vp, VMAYHAVELOCKS);
260 error = lf_setlock(lock, owner, type, flags, start, end);
261 if (TAILQ_EMPTY(&lock->lf_range) &&
262 TAILQ_EMPTY(&lock->lf_blocked)) {
263 vclrflags(ap->a_vp, VMAYHAVELOCKS);
268 error = lf_getlock(fl, lock, owner, type, flags, start, end);
275 lwkt_reltoken(token);
280 lf_setlock(struct lockf *lock, struct proc *owner, int type, int flags,
281 off_t start, off_t end)
283 struct lockf_range *range;
284 struct lockf_range *brange;
285 struct lockf_range *next;
286 struct lockf_range *first_match;
287 struct lockf_range *last_match;
288 struct lockf_range *insert_point;
289 struct lockf_range *new_range1;
290 struct lockf_range *new_range2;
296 struct lockf_range_list deadlist;
304 * Preallocate two ranges so we don't have to worry about blocking
305 * in the middle of the lock code.
307 if (new_range1 == NULL)
308 new_range1 = lf_alloc_range();
309 if (new_range2 == NULL)
310 new_range2 = lf_alloc_range();
319 * Locate the insertion point for the new lock (the first range
320 * with an lf_start >= start).
322 * Locate the first and latch ranges owned by us that overlap
323 * the requested range.
325 TAILQ_FOREACH(range, &lock->lf_range, lf_link) {
326 if (insert_point == NULL && range->lf_start >= start)
327 insert_point = range;
330 * Skip non-overlapping locks. Locks are sorted by lf_start
331 * So we can terminate the search when lf_start exceeds the
332 * requested range (insert_point is still guarenteed to be
335 if (range->lf_end < start)
337 if (range->lf_start > end) {
343 * Overlapping lock. Set first_match and last_match if we
346 if (range->lf_owner == owner) {
347 if (first_match == NULL)
354 * If we aren't the owner check for a conflicting lock. Only
357 if (type != F_UNLCK) {
358 if (type == F_WRLCK || range->lf_type == F_WRLCK)
364 * If a conflicting lock was observed, block or fail as appropriate.
365 * (this code is skipped when unlocking)
368 if ((flags & F_WAIT) == 0) {
374 * We are blocked. For POSIX locks we have to check
375 * for deadlocks and return with EDEADLK. This is done
376 * by checking whether range->lf_owner is already
379 * Since flock-style locks cover the whole file, a
380 * deadlock between those is nearly impossible.
381 * This can only occur if a process tries to lock the
382 * same inode exclusively while holding a shared lock
383 * with another descriptor.
384 * XXX How can we cleanly detect this?
385 * XXX The current mixing of flock & fcntl/lockf is evil.
387 * Handle existing locks of flock-style like POSIX locks.
389 if (flags & F_POSIX) {
390 TAILQ_FOREACH(brange, &lock->lf_blocked, lf_link) {
391 if (brange->lf_owner == range->lf_owner) {
399 * For flock-style locks, we must first remove
400 * any shared locks that we hold before we sleep
401 * waiting for an exclusive lock.
403 if ((flags & F_POSIX) == 0 && type == F_WRLCK)
404 lf_setlock(lock, owner, F_UNLCK, 0, start, end);
408 lf_create_range(brange, owner, type, 0, start, end);
409 TAILQ_INSERT_TAIL(&lock->lf_blocked, brange, lf_link);
410 error = tsleep(brange, PCATCH, "lockf", 0);
413 * We may have been awaked by a signal and/or by a
414 * debugger continuing us (in which case we must remove
415 * ourselves from the blocked list) and/or by another
416 * process releasing/downgrading a lock (in which case
417 * we have already been removed from the blocked list
418 * and our lf_flags field is 1).
420 * Sleep if it looks like we might be livelocking.
422 if (brange->lf_flags == 0)
423 TAILQ_REMOVE(&lock->lf_blocked, brange, lf_link);
425 tsleep(brange, 0, "lockfz", 2);
428 lf_destroy_range(brange);
436 * If there are no overlapping locks owned by us then creating
437 * the new lock is easy. This is the most common case.
439 if (first_match == NULL) {
442 if (flags & F_POSIX) {
443 if (lf_count_change(owner, 1)) {
450 lf_create_range(range, owner, type, flags, start, end);
451 lf_insert(&lock->lf_range, range, insert_point);
456 * double_clip - Calculate a special case where TWO locks may have
457 * to be added due to the new lock breaking up an
458 * existing incompatible lock in the middle.
460 * unlock_override - Calculate a special case where NO locks
461 * need to be created. This occurs when an unlock
462 * does not clip any locks at the front and rear.
464 * WARNING! closef() and fdrop() assume that an F_UNLCK of the
465 * entire range will always succeed so the unlock_override
470 if (first_match->lf_start < start) {
471 if (first_match == last_match && last_match->lf_end > end)
473 } else if (type == F_UNLCK && last_match->lf_end <= end) {
478 * Figure out the worst case net increase in POSIX locks and account
479 * for it now before we start modifying things. If neither the
480 * first or last locks match we have an issue. If there is only
481 * one overlapping range which needs to be clipped on both ends
482 * we wind up having to create up to two new locks, else only one.
484 * When unlocking the worst case is always 1 new lock if our
485 * unlock request cuts the middle out of an existing lock range.
487 * count represents the 'cleanup' adjustment needed. It starts
488 * negative, is incremented whenever we create a new POSIX lock,
489 * and decremented whenever we delete an existing one. At the
490 * end of the day it had better be <= 0 or we didn't calculate the
491 * worse case properly here.
494 if ((flags & F_POSIX) && !unlock_override) {
495 if (!lf_match(first_match, type, flags) &&
496 !lf_match(last_match, type, flags)
498 if (double_clip && type != F_UNLCK)
503 if (count && lf_count_change(owner, -count)) {
508 /* else flock style lock which encompasses entire range */
511 * Create and insert the lock represented the requested range.
512 * Adjust the net POSIX lock count. We have to move our insertion
513 * point since brange now represents the first record >= start.
515 * When unlocking, no new lock is inserted but we still clip.
517 if (type != F_UNLCK) {
520 lf_create_range(brange, owner, type, flags, start, end);
521 lf_insert(&lock->lf_range, brange, insert_point);
522 insert_point = brange;
530 * Handle the double_clip case. This is the only case where
531 * we wind up having to add TWO locks.
534 KKASSERT(first_match == last_match);
535 last_match = new_range2;
537 lf_create_range(last_match, first_match->lf_owner,
538 first_match->lf_type, first_match->lf_flags,
539 end + 1, first_match->lf_end);
540 first_match->lf_end = start - 1;
541 first_match->lf_flags &= ~F_NOEND;
544 * Figure out where to insert the right side clip.
546 lf_insert(&lock->lf_range, last_match, first_match);
547 if (last_match->lf_flags & F_POSIX)
552 * Clip or destroy the locks between first_match and last_match,
553 * inclusive. Ignore the primary lock we created (brange). Note
554 * that if double-clipped, first_match and last_match will be
555 * outside our clipping range. Otherwise first_match and last_match
558 * We have already taken care of any double clipping.
560 * The insert_point may become invalid as we delete records, do not
561 * use that pointer any more. Also, when removing something other
562 * then 'range' we have to check to see if the item we are removing
563 * is 'next' and adjust 'next' properly.
565 * NOTE: brange will be NULL if F_UNLCKing.
567 TAILQ_INIT(&deadlist);
570 while ((range = next) != NULL) {
571 next = TAILQ_NEXT(range, lf_link);
574 * Ignore elements that we do not own and ignore the
575 * primary request range which we just created.
577 if (range->lf_owner != owner || range == brange)
581 * We may have to wakeup a waiter when downgrading a lock.
585 if (type == F_RDLCK && range->lf_type == F_WRLCK)
589 * Clip left. This can only occur on first_match.
591 * Merge the left clip with brange if possible. This must
592 * be done specifically, not in the optimized merge heuristic
593 * below, since we may have counted on it in our 'count'
596 if (range->lf_start < start) {
597 KKASSERT(range == first_match);
599 range->lf_end >= start - 1 &&
600 lf_match(range, type, flags)) {
601 range->lf_end = brange->lf_end;
602 range->lf_flags |= brange->lf_flags & F_NOEND;
604 * Removing something other then 'range',
605 * adjust 'next' if necessary.
608 next = TAILQ_NEXT(next, lf_link);
609 TAILQ_REMOVE(&lock->lf_range, brange, lf_link);
610 if (brange->lf_flags & F_POSIX)
612 TAILQ_INSERT_TAIL(&deadlist, brange, lf_link);
614 } else if (range->lf_end >= start) {
615 range->lf_end = start - 1;
617 range->lf_flags &= ~F_NOEND;
619 if (range == last_match)
625 * Clip right. This can only occur on last_match.
627 * Merge the right clip if possible. This must be done
628 * specifically, not in the optimized merge heuristic
629 * below, since we may have counted on it in our 'count'
632 * Since we are adjusting lf_start, we have to move the
633 * record to maintain the sorted list. Since lf_start is
634 * only getting larger we can use the next element as the
635 * insert point (we don't have to backtrack).
637 if (range->lf_end > end) {
638 KKASSERT(range == last_match);
640 range->lf_start <= end + 1 &&
641 lf_match(range, type, flags)) {
642 brange->lf_end = range->lf_end;
643 brange->lf_flags |= range->lf_flags & F_NOEND;
644 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
645 if (range->lf_flags & F_POSIX)
647 TAILQ_INSERT_TAIL(&deadlist, range, lf_link);
648 } else if (range->lf_start <= end) {
649 range->lf_start = end + 1;
650 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
651 lf_insert(&lock->lf_range, range, next);
653 /* range == last_match, we are done */
658 * The record must be entirely enclosed. Note that the
659 * record could be first_match or last_match, and will be
662 KKASSERT(range->lf_start >= start && range->lf_end <= end);
663 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
664 if (range->lf_flags & F_POSIX)
666 TAILQ_INSERT_TAIL(&deadlist, range, lf_link);
667 if (range == last_match)
672 * Attempt to merge locks adjacent to brange. For example, we may
673 * have had to clip first_match and/or last_match, and they might
674 * be adjacent. Or there might simply have been an adjacent lock
677 * Don't get fancy, just check adjacent elements in the list if they
678 * happen to be owned by us.
680 * This case only gets hit if we have a situation where a shared
681 * and exclusive lock are adjacent, and the exclusive lock is
682 * downgraded to shared or the shared lock is upgraded to exclusive.
685 range = TAILQ_PREV(brange, lockf_range_list, lf_link);
687 range->lf_owner == owner &&
688 range->lf_end == brange->lf_start - 1 &&
689 lf_match(range, type, flags)
692 * Extend range to cover brange and scrap brange.
694 range->lf_end = brange->lf_end;
695 range->lf_flags |= brange->lf_flags & F_NOEND;
696 TAILQ_REMOVE(&lock->lf_range, brange, lf_link);
697 if (brange->lf_flags & F_POSIX)
699 TAILQ_INSERT_TAIL(&deadlist, brange, lf_link);
702 range = TAILQ_NEXT(brange, lf_link);
704 range->lf_owner == owner &&
705 range->lf_start == brange->lf_end + 1 &&
706 lf_match(range, type, flags)
709 * Extend brange to cover range and scrap range.
711 brange->lf_end = range->lf_end;
712 brange->lf_flags |= range->lf_flags & F_NOEND;
713 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
714 if (range->lf_flags & F_POSIX)
716 TAILQ_INSERT_TAIL(&deadlist, range, lf_link);
721 * Destroy deleted elements. We didn't want to do it in the loop
722 * because the free() might have blocked.
724 * Adjust the count for any posix locks we thought we might create
727 while ((range = TAILQ_FIRST(&deadlist)) != NULL) {
728 TAILQ_REMOVE(&deadlist, range, lf_link);
729 lf_destroy_range(range);
732 KKASSERT(count <= 0);
734 lf_count_change(owner, count);
738 lf_wakeup(lock, start, end);
741 if (new_range1 != NULL)
742 lf_destroy_range(new_range1);
743 if (new_range2 != NULL)
744 lf_destroy_range(new_range2);
749 * Check whether there is a blocking lock,
750 * and if so return its process identifier.
753 lf_getlock(struct flock *fl, struct lockf *lock, struct proc *owner,
754 int type, int flags, off_t start, off_t end)
756 struct lockf_range *range;
758 TAILQ_FOREACH(range, &lock->lf_range, lf_link)
759 if (range->lf_owner != owner &&
760 lf_overlap(range, start, end) &&
761 (type == F_WRLCK || range->lf_type == F_WRLCK))
764 fl->l_type = F_UNLCK;
767 fl->l_type = range->lf_type;
768 fl->l_whence = SEEK_SET;
769 fl->l_start = range->lf_start;
770 if (range->lf_flags & F_NOEND)
773 fl->l_len = range->lf_end - range->lf_start + 1;
774 if (range->lf_owner != NULL && (range->lf_flags & F_POSIX))
775 fl->l_pid = range->lf_owner->p_pid;
782 * Wakeup pending lock attempts. Theoretically we can stop as soon as
783 * we encounter an exclusive request that covers the whole range (at least
784 * insofar as the sleep code above calls lf_wakeup() if it would otherwise
785 * exit instead of loop), but for now just wakeup all overlapping
789 lf_wakeup(struct lockf *lock, off_t start, off_t end)
791 struct lockf_range *range, *nrange;
793 TAILQ_FOREACH_MUTABLE(range, &lock->lf_blocked, lf_link, nrange) {
794 if (lf_overlap(range, start, end) == 0)
796 TAILQ_REMOVE(&lock->lf_blocked, range, lf_link);
803 * Allocate a range structure and initialize it sufficiently such that
804 * lf_destroy_range() does not barf.
806 static struct lockf_range *
809 struct lockf_range *range;
812 atomic_add_int(&lf_global_counter, 1);
814 range = kmalloc(sizeof(struct lockf_range), M_LOCKF, M_WAITOK);
815 range->lf_owner = NULL;
820 lf_insert(struct lockf_range_list *list, struct lockf_range *elm,
821 struct lockf_range *insert_point)
823 while (insert_point && insert_point->lf_start < elm->lf_start)
824 insert_point = TAILQ_NEXT(insert_point, lf_link);
825 if (insert_point != NULL)
826 TAILQ_INSERT_BEFORE(insert_point, elm, lf_link);
828 TAILQ_INSERT_TAIL(list, elm, lf_link);
832 lf_create_range(struct lockf_range *range, struct proc *owner, int type,
833 int flags, off_t start, off_t end)
835 KKASSERT(start <= end);
836 range->lf_type = type;
837 range->lf_flags = flags;
838 range->lf_start = start;
840 range->lf_owner = owner;
842 lf_printf("lf_create_range: %lld..%lld\n",
843 range->lf_start, range->lf_end);
847 lf_destroy_range(struct lockf_range *range)
849 lf_printf("lf_destroy_range: %lld..%lld\n",
850 range->lf_start, range->lf_end);
851 kfree(range, M_LOCKF);
853 atomic_add_int(&lf_global_counter, -1);
854 KKASSERT(lf_global_counter >= 0);
861 _lf_printf(const char *ctl, ...)
866 if (lf_print_ranges) {
867 if ((p = curproc) != NULL)
868 kprintf("pid %d (%s): ", p->p_pid, p->p_comm);
876 _lf_print_lock(const struct lockf *lock)
878 struct lockf_range *range;
880 if (lf_print_ranges == 0)
883 if (TAILQ_EMPTY(&lock->lf_range)) {
884 lf_printf("lockf %p: no ranges locked\n", lock);
886 lf_printf("lockf %p:\n", lock);
888 TAILQ_FOREACH(range, &lock->lf_range, lf_link)
889 kprintf("\t%jd..%jd type %s owned by %d\n",
890 (uintmax_t)range->lf_start, (uintmax_t)range->lf_end,
891 range->lf_type == F_RDLCK ? "shared" : "exclusive",
892 range->lf_flags & F_POSIX ? range->lf_owner->p_pid : -1);
893 if (TAILQ_EMPTY(&lock->lf_blocked))
894 kprintf("no process waiting for range\n");
896 kprintf("blocked locks:");
897 TAILQ_FOREACH(range, &lock->lf_blocked, lf_link)
898 kprintf("\t%jd..%jd type %s waiting on %p\n",
899 (uintmax_t)range->lf_start, (uintmax_t)range->lf_end,
900 range->lf_type == F_RDLCK ? "shared" : "exclusive",
903 #endif /* LOCKF_DEBUG */