2 * SPDX-License-Identifier: BSD-3-Clause
4 * Copyright (c) 2008 Isilon Inc http://www.isilon.com/
5 * Authors: Doug Rabson <dfr@rabson.org>
6 * Developed with Red Inc: Alfred Perlstein <alfred@freebsd.org>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * Copyright (c) 1982, 1986, 1989, 1993
31 * The Regents of the University of California. All rights reserved.
33 * This code is derived from software contributed to Berkeley by
34 * Scooter Morris at Genentech Inc.
36 * Redistribution and use in source and binary forms, with or without
37 * modification, are permitted provided that the following conditions
39 * 1. Redistributions of source code must retain the above copyright
40 * notice, this list of conditions and the following disclaimer.
41 * 2. Redistributions in binary form must reproduce the above copyright
42 * notice, this list of conditions and the following disclaimer in the
43 * documentation and/or other materials provided with the distribution.
44 * 3. Neither the name of the University nor the names of its contributors
45 * may be used to endorse or promote products derived from this software
46 * without specific prior written permission.
48 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
49 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
50 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
51 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
52 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
53 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
54 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
56 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
57 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
61 #include <sys/cdefs.h>
62 #include "opt_debug_lockf.h"
64 #include <sys/param.h>
65 #include <sys/systm.h>
68 #include <sys/kernel.h>
69 #include <sys/limits.h>
71 #include <sys/mount.h>
72 #include <sys/mutex.h>
77 #include <sys/unistd.h>
79 #include <sys/vnode.h>
80 #include <sys/malloc.h>
81 #include <sys/fcntl.h>
82 #include <sys/lockf.h>
83 #include <sys/taskqueue.h>
86 #include <sys/sysctl.h>
88 static int lockf_debug = 0; /* control debug output */
89 SYSCTL_INT(_debug, OID_AUTO, lockf_debug, CTLFLAG_RW, &lockf_debug, 0, "");
92 static MALLOC_DEFINE(M_LOCKF, "lockf", "Byte-range locking structures");
96 struct owner_vertex_list;
99 #define NOLOCKF (struct lockf_entry *)0
102 static void lf_init(void *);
103 static int lf_hash_owner(caddr_t, struct vnode *, struct flock *, int);
104 static int lf_owner_matches(struct lock_owner *, caddr_t, struct flock *,
106 static struct lockf_entry *
107 lf_alloc_lock(struct lock_owner *);
108 static int lf_free_lock(struct lockf_entry *);
109 static int lf_clearlock(struct lockf *, struct lockf_entry *);
110 static int lf_overlaps(struct lockf_entry *, struct lockf_entry *);
111 static int lf_blocks(struct lockf_entry *, struct lockf_entry *);
112 static void lf_free_edge(struct lockf_edge *);
113 static struct lockf_edge *
115 static void lf_alloc_vertex(struct lockf_entry *);
116 static int lf_add_edge(struct lockf_entry *, struct lockf_entry *);
117 static void lf_remove_edge(struct lockf_edge *);
118 static void lf_remove_outgoing(struct lockf_entry *);
119 static void lf_remove_incoming(struct lockf_entry *);
120 static int lf_add_outgoing(struct lockf *, struct lockf_entry *);
121 static int lf_add_incoming(struct lockf *, struct lockf_entry *);
122 static int lf_findoverlap(struct lockf_entry **, struct lockf_entry *,
124 static struct lockf_entry *
125 lf_getblock(struct lockf *, struct lockf_entry *);
126 static int lf_getlock(struct lockf *, struct lockf_entry *, struct flock *);
127 static void lf_insert_lock(struct lockf *, struct lockf_entry *);
128 static void lf_wakeup_lock(struct lockf *, struct lockf_entry *);
129 static void lf_update_dependancies(struct lockf *, struct lockf_entry *,
130 int all, struct lockf_entry_list *);
131 static void lf_set_start(struct lockf *, struct lockf_entry *, off_t,
132 struct lockf_entry_list*);
133 static void lf_set_end(struct lockf *, struct lockf_entry *, off_t,
134 struct lockf_entry_list*);
135 static int lf_setlock(struct lockf *, struct lockf_entry *,
136 struct vnode *, void **cookiep);
137 static int lf_cancel(struct lockf *, struct lockf_entry *, void *);
138 static void lf_split(struct lockf *, struct lockf_entry *,
139 struct lockf_entry *, struct lockf_entry_list *);
141 static int graph_reaches(struct owner_vertex *x, struct owner_vertex *y,
142 struct owner_vertex_list *path);
143 static void graph_check(struct owner_graph *g, int checkorder);
144 static void graph_print_vertices(struct owner_vertex_list *set);
146 static int graph_delta_forward(struct owner_graph *g,
147 struct owner_vertex *x, struct owner_vertex *y,
148 struct owner_vertex_list *delta);
149 static int graph_delta_backward(struct owner_graph *g,
150 struct owner_vertex *x, struct owner_vertex *y,
151 struct owner_vertex_list *delta);
152 static int graph_add_indices(int *indices, int n,
153 struct owner_vertex_list *set);
154 static int graph_assign_indices(struct owner_graph *g, int *indices,
155 int nextunused, struct owner_vertex_list *set);
156 static int graph_add_edge(struct owner_graph *g,
157 struct owner_vertex *x, struct owner_vertex *y);
158 static void graph_remove_edge(struct owner_graph *g,
159 struct owner_vertex *x, struct owner_vertex *y);
160 static struct owner_vertex *graph_alloc_vertex(struct owner_graph *g,
161 struct lock_owner *lo);
162 static void graph_free_vertex(struct owner_graph *g,
163 struct owner_vertex *v);
164 static struct owner_graph * graph_init(struct owner_graph *g);
166 static void lf_print(char *, struct lockf_entry *);
167 static void lf_printlist(char *, struct lockf_entry *);
168 static void lf_print_owner(struct lock_owner *);
172 * This structure is used to keep track of both local and remote lock
173 * owners. The lf_owner field of the struct lockf_entry points back at
174 * the lock owner structure. Each possible lock owner (local proc for
175 * POSIX fcntl locks, local file for BSD flock locks or <pid,sysid>
176 * pair for remote locks) is represented by a unique instance of
179 * If a lock owner has a lock that blocks some other lock or a lock
180 * that is waiting for some other lock, it also has a vertex in the
184 * (s) locked by state->ls_lock
185 * (S) locked by lf_lock_states_lock
186 * (g) locked by lf_owner_graph_lock
187 * (c) const until freeing
189 #define LOCK_OWNER_HASH_SIZE 256
192 LIST_ENTRY(lock_owner) lo_link; /* (l) hash chain */
193 int lo_refs; /* (l) Number of locks referring to this */
194 int lo_flags; /* (c) Flags passed to lf_advlock */
195 caddr_t lo_id; /* (c) Id value passed to lf_advlock */
196 pid_t lo_pid; /* (c) Process Id of the lock owner */
197 int lo_sysid; /* (c) System Id of the lock owner */
198 int lo_hash; /* (c) Used to lock the appropriate chain */
199 struct owner_vertex *lo_vertex; /* (g) entry in deadlock graph */
202 LIST_HEAD(lock_owner_list, lock_owner);
204 struct lock_owner_chain {
206 struct lock_owner_list list;
209 static struct sx lf_lock_states_lock;
210 static struct lockf_list lf_lock_states; /* (S) */
211 static struct lock_owner_chain lf_lock_owners[LOCK_OWNER_HASH_SIZE];
214 * Structures for deadlock detection.
216 * We have two types of directed graph, the first is the set of locks,
217 * both active and pending on a vnode. Within this graph, active locks
218 * are terminal nodes in the graph (i.e. have no out-going
219 * edges). Pending locks have out-going edges to each blocking active
220 * lock that prevents the lock from being granted and also to each
221 * older pending lock that would block them if it was active. The
222 * graph for each vnode is naturally acyclic; new edges are only ever
223 * added to or from new nodes (either new pending locks which only add
224 * out-going edges or new active locks which only add in-coming edges)
225 * therefore they cannot create loops in the lock graph.
227 * The second graph is a global graph of lock owners. Each lock owner
228 * is a vertex in that graph and an edge is added to the graph
229 * whenever an edge is added to a vnode graph, with end points
230 * corresponding to owner of the new pending lock and the owner of the
231 * lock upon which it waits. In order to prevent deadlock, we only add
232 * an edge to this graph if the new edge would not create a cycle.
234 * The lock owner graph is topologically sorted, i.e. if a node has
235 * any outgoing edges, then it has an order strictly less than any
236 * node to which it has an outgoing edge. We preserve this ordering
237 * (and detect cycles) on edge insertion using Algorithm PK from the
238 * paper "A Dynamic Topological Sort Algorithm for Directed Acyclic
239 * Graphs" (ACM Journal of Experimental Algorithms, Vol 11, Article
245 LIST_ENTRY(owner_edge) e_outlink; /* (g) link from's out-edge list */
246 LIST_ENTRY(owner_edge) e_inlink; /* (g) link to's in-edge list */
247 int e_refs; /* (g) number of times added */
248 struct owner_vertex *e_from; /* (c) out-going from here */
249 struct owner_vertex *e_to; /* (c) in-coming to here */
251 LIST_HEAD(owner_edge_list, owner_edge);
253 struct owner_vertex {
254 TAILQ_ENTRY(owner_vertex) v_link; /* (g) workspace for edge insertion */
255 uint32_t v_gen; /* (g) workspace for edge insertion */
256 int v_order; /* (g) order of vertex in graph */
257 struct owner_edge_list v_outedges;/* (g) list of out-edges */
258 struct owner_edge_list v_inedges; /* (g) list of in-edges */
259 struct lock_owner *v_owner; /* (c) corresponding lock owner */
261 TAILQ_HEAD(owner_vertex_list, owner_vertex);
264 struct owner_vertex** g_vertices; /* (g) pointers to vertices */
265 int g_size; /* (g) number of vertices */
266 int g_space; /* (g) space allocated for vertices */
267 int *g_indexbuf; /* (g) workspace for loop detection */
268 uint32_t g_gen; /* (g) increment when re-ordering */
271 static struct sx lf_owner_graph_lock;
272 static struct owner_graph lf_owner_graph;
275 * Initialise various structures and locks.
282 sx_init(&lf_lock_states_lock, "lock states lock");
283 LIST_INIT(&lf_lock_states);
285 for (i = 0; i < LOCK_OWNER_HASH_SIZE; i++) {
286 sx_init(&lf_lock_owners[i].lock, "lock owners lock");
287 LIST_INIT(&lf_lock_owners[i].list);
290 sx_init(&lf_owner_graph_lock, "owner graph lock");
291 graph_init(&lf_owner_graph);
293 SYSINIT(lf_init, SI_SUB_LOCK, SI_ORDER_FIRST, lf_init, NULL);
296 * Generate a hash value for a lock owner.
299 lf_hash_owner(caddr_t id, struct vnode *vp, struct flock *fl, int flags)
303 if (flags & F_REMOTE) {
304 h = HASHSTEP(0, fl->l_pid);
305 h = HASHSTEP(h, fl->l_sysid);
306 } else if (flags & F_FLOCK) {
307 h = ((uintptr_t) id) >> 7;
309 h = ((uintptr_t) vp) >> 7;
312 return (h % LOCK_OWNER_HASH_SIZE);
316 * Return true if a lock owner matches the details passed to
320 lf_owner_matches(struct lock_owner *lo, caddr_t id, struct flock *fl,
323 if (flags & F_REMOTE) {
324 return lo->lo_pid == fl->l_pid
325 && lo->lo_sysid == fl->l_sysid;
327 return lo->lo_id == id;
331 static struct lockf_entry *
332 lf_alloc_lock(struct lock_owner *lo)
334 struct lockf_entry *lf;
336 lf = malloc(sizeof(struct lockf_entry), M_LOCKF, M_WAITOK|M_ZERO);
340 printf("Allocated lock %p\n", lf);
343 sx_xlock(&lf_lock_owners[lo->lo_hash].lock);
345 sx_xunlock(&lf_lock_owners[lo->lo_hash].lock);
353 lf_free_lock(struct lockf_entry *lock)
355 struct sx *chainlock;
357 KASSERT(lock->lf_refs > 0, ("lockf_entry negative ref count %p", lock));
358 if (--lock->lf_refs > 0)
361 * Adjust the lock_owner reference count and
362 * reclaim the entry if this is the last lock
365 struct lock_owner *lo = lock->lf_owner;
367 KASSERT(LIST_EMPTY(&lock->lf_outedges),
368 ("freeing lock with dependencies"));
369 KASSERT(LIST_EMPTY(&lock->lf_inedges),
370 ("freeing lock with dependants"));
371 chainlock = &lf_lock_owners[lo->lo_hash].lock;
373 KASSERT(lo->lo_refs > 0, ("lock owner refcount"));
375 if (lo->lo_refs == 0) {
378 printf("lf_free_lock: freeing lock owner %p\n",
382 sx_xlock(&lf_owner_graph_lock);
383 graph_free_vertex(&lf_owner_graph,
385 sx_xunlock(&lf_owner_graph_lock);
387 LIST_REMOVE(lo, lo_link);
391 printf("Freed lock owner %p\n", lo);
394 sx_unlock(chainlock);
396 if ((lock->lf_flags & F_REMOTE) && lock->lf_vnode) {
397 vrele(lock->lf_vnode);
398 lock->lf_vnode = NULL;
402 printf("Freed lock %p\n", lock);
409 * Advisory record locking support
412 lf_advlockasync(struct vop_advlockasync_args *ap, struct lockf **statep,
416 struct flock *fl = ap->a_fl;
417 struct lockf_entry *lock;
418 struct vnode *vp = ap->a_vp;
419 caddr_t id = ap->a_id;
420 int flags = ap->a_flags;
422 struct lock_owner *lo;
423 off_t start, end, oadd;
427 * Handle the F_UNLKSYS case first - no need to mess about
428 * creating a lock owner for this one.
430 if (ap->a_op == F_UNLCKSYS) {
431 lf_clearremotesys(fl->l_sysid);
436 * Convert the flock structure into a start and end.
438 switch (fl->l_whence) {
442 * Caller is responsible for adding any necessary offset
443 * when SEEK_CUR is used.
449 if (size > OFF_MAX ||
450 (fl->l_start > 0 && size > OFF_MAX - fl->l_start))
452 start = size + fl->l_start;
467 } else if (fl->l_len == 0) {
470 oadd = fl->l_len - 1;
471 if (oadd > OFF_MAX - start)
479 * Avoid the common case of unlocking when inode has no locks.
481 if (ap->a_op != F_SETLK && (*statep) == NULL) {
483 if ((*statep) == NULL) {
484 fl->l_type = F_UNLCK;
492 * Map our arguments to an existing lock owner or create one
493 * if this is the first time we have seen this owner.
495 hash = lf_hash_owner(id, vp, fl, flags);
496 sx_xlock(&lf_lock_owners[hash].lock);
497 LIST_FOREACH(lo, &lf_lock_owners[hash].list, lo_link)
498 if (lf_owner_matches(lo, id, fl, flags))
502 * We initialise the lock with a reference
503 * count which matches the new lockf_entry
504 * structure created below.
506 lo = malloc(sizeof(struct lock_owner), M_LOCKF,
510 printf("Allocated lock owner %p\n", lo);
514 lo->lo_flags = flags;
517 if (flags & F_REMOTE) {
518 lo->lo_pid = fl->l_pid;
519 lo->lo_sysid = fl->l_sysid;
520 } else if (flags & F_FLOCK) {
524 struct proc *p = (struct proc *) id;
525 lo->lo_pid = p->p_pid;
528 lo->lo_vertex = NULL;
531 if (lockf_debug & 1) {
532 printf("lf_advlockasync: new lock owner %p ", lo);
538 LIST_INSERT_HEAD(&lf_lock_owners[hash].list, lo, lo_link);
541 * We have seen this lock owner before, increase its
542 * reference count to account for the new lockf_entry
543 * structure we create below.
547 sx_xunlock(&lf_lock_owners[hash].lock);
550 * Create the lockf structure. We initialise the lf_owner
551 * field here instead of in lf_alloc_lock() to avoid paying
552 * the lf_lock_owners_lock tax twice.
554 lock = lf_alloc_lock(NULL);
556 lock->lf_start = start;
560 if (flags & F_REMOTE) {
562 * For remote locks, the caller may release its ref to
563 * the vnode at any time - we have to ref it here to
564 * prevent it from being recycled unexpectedly.
569 lock->lf_type = fl->l_type;
570 LIST_INIT(&lock->lf_outedges);
571 LIST_INIT(&lock->lf_inedges);
572 lock->lf_async_task = ap->a_task;
573 lock->lf_flags = ap->a_flags;
576 * Do the requested operation. First find our state structure
577 * and create a new one if necessary - the caller's *statep
578 * variable and the state's ls_threads count is protected by
579 * the vnode interlock.
582 if (VN_IS_DOOMED(vp)) {
589 * Allocate a state structure if necessary.
597 ls = malloc(sizeof(struct lockf), M_LOCKF, M_WAITOK|M_ZERO);
598 sx_init(&ls->ls_lock, "ls_lock");
599 LIST_INIT(&ls->ls_active);
600 LIST_INIT(&ls->ls_pending);
603 sx_xlock(&lf_lock_states_lock);
604 LIST_INSERT_HEAD(&lf_lock_states, ls, ls_link);
605 sx_xunlock(&lf_lock_states_lock);
608 * Cope if we lost a race with some other thread while
609 * trying to allocate memory.
612 if (VN_IS_DOOMED(vp)) {
614 sx_xlock(&lf_lock_states_lock);
615 LIST_REMOVE(ls, ls_link);
616 sx_xunlock(&lf_lock_states_lock);
617 sx_destroy(&ls->ls_lock);
622 if ((*statep) == NULL) {
623 state = *statep = ls;
627 MPASS(state->ls_threads >= 0);
631 sx_xlock(&lf_lock_states_lock);
632 LIST_REMOVE(ls, ls_link);
633 sx_xunlock(&lf_lock_states_lock);
634 sx_destroy(&ls->ls_lock);
638 MPASS(state->ls_threads >= 0);
643 sx_xlock(&state->ls_lock);
645 * Recheck the doomed vnode after state->ls_lock is
646 * locked. lf_purgelocks() requires that no new threads add
647 * pending locks when vnode is marked by VIRF_DOOMED flag.
649 if (VN_IS_DOOMED(vp)) {
651 MPASS(state->ls_threads > 0);
655 sx_xunlock(&state->ls_lock);
662 error = lf_setlock(state, lock, vp, ap->a_cookiep);
666 error = lf_clearlock(state, lock);
671 error = lf_getlock(state, lock, fl);
677 error = lf_cancel(state, lock, *ap->a_cookiep);
691 * Check for some can't happen stuff. In this case, the active
692 * lock list becoming disordered or containing mutually
693 * blocking locks. We also check the pending list for locks
694 * which should be active (i.e. have no out-going edges).
696 LIST_FOREACH(lock, &state->ls_active, lf_link) {
697 struct lockf_entry *lf;
698 if (LIST_NEXT(lock, lf_link))
699 KASSERT((lock->lf_start
700 <= LIST_NEXT(lock, lf_link)->lf_start),
701 ("locks disordered"));
702 LIST_FOREACH(lf, &state->ls_active, lf_link) {
705 KASSERT(!lf_blocks(lock, lf),
706 ("two conflicting active locks"));
707 if (lock->lf_owner == lf->lf_owner)
708 KASSERT(!lf_overlaps(lock, lf),
709 ("two overlapping locks from same owner"));
712 LIST_FOREACH(lock, &state->ls_pending, lf_link) {
713 KASSERT(!LIST_EMPTY(&lock->lf_outedges),
714 ("pending lock which should be active"));
717 sx_xunlock(&state->ls_lock);
720 MPASS(state->ls_threads > 0);
722 if (state->ls_threads != 0) {
727 if (error == EDOOFUS) {
728 KASSERT(ap->a_op == F_SETLK, ("EDOOFUS"));
735 lf_advlock(struct vop_advlock_args *ap, struct lockf **statep, u_quad_t size)
737 struct vop_advlockasync_args a;
743 a.a_flags = ap->a_flags;
747 return (lf_advlockasync(&a, statep, size));
751 lf_purgelocks(struct vnode *vp, struct lockf **statep)
754 struct lockf_entry *lock, *nlock;
757 * For this to work correctly, the caller must ensure that no
758 * other threads enter the locking system for this vnode,
759 * e.g. by checking VIRF_DOOMED. We wake up any threads that are
760 * sleeping waiting for locks on this vnode and then free all
761 * the remaining locks.
763 KASSERT(VN_IS_DOOMED(vp),
764 ("lf_purgelocks: vp %p has not vgone yet", vp));
771 if (LIST_EMPTY(&state->ls_active) && state->ls_threads == 0) {
772 KASSERT(LIST_EMPTY(&state->ls_pending),
773 ("freeing state with pending locks"));
777 MPASS(state->ls_threads >= 0);
781 sx_xlock(&state->ls_lock);
782 sx_xlock(&lf_owner_graph_lock);
783 LIST_FOREACH_SAFE(lock, &state->ls_pending, lf_link, nlock) {
784 LIST_REMOVE(lock, lf_link);
785 lf_remove_outgoing(lock);
786 lf_remove_incoming(lock);
789 * If its an async lock, we can just free it
790 * here, otherwise we let the sleeping thread
793 if (lock->lf_async_task) {
796 lock->lf_flags |= F_INTR;
800 sx_xunlock(&lf_owner_graph_lock);
801 sx_xunlock(&state->ls_lock);
804 * Wait for all other threads, sleeping and otherwise
808 while (state->ls_threads > 1)
809 msleep(state, VI_MTX(vp), 0, "purgelocks", 0);
813 * We can just free all the active locks since they
814 * will have no dependencies (we removed them all
815 * above). We don't need to bother locking since we
816 * are the last thread using this state structure.
818 KASSERT(LIST_EMPTY(&state->ls_pending),
819 ("lock pending for %p", state));
820 LIST_FOREACH_SAFE(lock, &state->ls_active, lf_link, nlock) {
821 LIST_REMOVE(lock, lf_link);
825 sx_xlock(&lf_lock_states_lock);
826 LIST_REMOVE(state, ls_link);
827 sx_xunlock(&lf_lock_states_lock);
828 sx_destroy(&state->ls_lock);
829 free(state, M_LOCKF);
833 * Return non-zero if locks 'x' and 'y' overlap.
836 lf_overlaps(struct lockf_entry *x, struct lockf_entry *y)
839 return (x->lf_start <= y->lf_end && x->lf_end >= y->lf_start);
843 * Return non-zero if lock 'x' is blocked by lock 'y' (or vice versa).
846 lf_blocks(struct lockf_entry *x, struct lockf_entry *y)
849 return x->lf_owner != y->lf_owner
850 && (x->lf_type == F_WRLCK || y->lf_type == F_WRLCK)
851 && lf_overlaps(x, y);
855 * Allocate a lock edge from the free list
857 static struct lockf_edge *
861 return (malloc(sizeof(struct lockf_edge), M_LOCKF, M_WAITOK|M_ZERO));
868 lf_free_edge(struct lockf_edge *e)
875 * Ensure that the lock's owner has a corresponding vertex in the
879 lf_alloc_vertex(struct lockf_entry *lock)
881 struct owner_graph *g = &lf_owner_graph;
883 if (!lock->lf_owner->lo_vertex)
884 lock->lf_owner->lo_vertex =
885 graph_alloc_vertex(g, lock->lf_owner);
889 * Attempt to record an edge from lock x to lock y. Return EDEADLK if
890 * the new edge would cause a cycle in the owner graph.
893 lf_add_edge(struct lockf_entry *x, struct lockf_entry *y)
895 struct owner_graph *g = &lf_owner_graph;
896 struct lockf_edge *e;
900 LIST_FOREACH(e, &x->lf_outedges, le_outlink)
901 KASSERT(e->le_to != y, ("adding lock edge twice"));
905 * Make sure the two owners have entries in the owner graph.
910 error = graph_add_edge(g, x->lf_owner->lo_vertex,
911 y->lf_owner->lo_vertex);
916 LIST_INSERT_HEAD(&x->lf_outedges, e, le_outlink);
917 LIST_INSERT_HEAD(&y->lf_inedges, e, le_inlink);
925 * Remove an edge from the lock graph.
928 lf_remove_edge(struct lockf_edge *e)
930 struct owner_graph *g = &lf_owner_graph;
931 struct lockf_entry *x = e->le_from;
932 struct lockf_entry *y = e->le_to;
934 graph_remove_edge(g, x->lf_owner->lo_vertex, y->lf_owner->lo_vertex);
935 LIST_REMOVE(e, le_outlink);
936 LIST_REMOVE(e, le_inlink);
943 * Remove all out-going edges from lock x.
946 lf_remove_outgoing(struct lockf_entry *x)
948 struct lockf_edge *e;
950 while ((e = LIST_FIRST(&x->lf_outedges)) != NULL) {
956 * Remove all in-coming edges from lock x.
959 lf_remove_incoming(struct lockf_entry *x)
961 struct lockf_edge *e;
963 while ((e = LIST_FIRST(&x->lf_inedges)) != NULL) {
969 * Walk the list of locks for the file and create an out-going edge
970 * from lock to each blocking lock.
973 lf_add_outgoing(struct lockf *state, struct lockf_entry *lock)
975 struct lockf_entry *overlap;
978 LIST_FOREACH(overlap, &state->ls_active, lf_link) {
980 * We may assume that the active list is sorted by
983 if (overlap->lf_start > lock->lf_end)
985 if (!lf_blocks(lock, overlap))
989 * We've found a blocking lock. Add the corresponding
990 * edge to the graphs and see if it would cause a
993 error = lf_add_edge(lock, overlap);
996 * The only error that lf_add_edge returns is EDEADLK.
997 * Remove any edges we added and return the error.
1000 lf_remove_outgoing(lock);
1006 * We also need to add edges to sleeping locks that block
1007 * us. This ensures that lf_wakeup_lock cannot grant two
1008 * mutually blocking locks simultaneously and also enforces a
1009 * 'first come, first served' fairness model. Note that this
1010 * only happens if we are blocked by at least one active lock
1011 * due to the call to lf_getblock in lf_setlock below.
1013 LIST_FOREACH(overlap, &state->ls_pending, lf_link) {
1014 if (!lf_blocks(lock, overlap))
1017 * We've found a blocking lock. Add the corresponding
1018 * edge to the graphs and see if it would cause a
1021 error = lf_add_edge(lock, overlap);
1024 * The only error that lf_add_edge returns is EDEADLK.
1025 * Remove any edges we added and return the error.
1028 lf_remove_outgoing(lock);
1037 * Walk the list of pending locks for the file and create an in-coming
1038 * edge from lock to each blocking lock.
1041 lf_add_incoming(struct lockf *state, struct lockf_entry *lock)
1043 struct lockf_entry *overlap;
1046 sx_assert(&state->ls_lock, SX_XLOCKED);
1047 if (LIST_EMPTY(&state->ls_pending))
1051 sx_xlock(&lf_owner_graph_lock);
1052 LIST_FOREACH(overlap, &state->ls_pending, lf_link) {
1053 if (!lf_blocks(lock, overlap))
1057 * We've found a blocking lock. Add the corresponding
1058 * edge to the graphs and see if it would cause a
1061 error = lf_add_edge(overlap, lock);
1064 * The only error that lf_add_edge returns is EDEADLK.
1065 * Remove any edges we added and return the error.
1068 lf_remove_incoming(lock);
1072 sx_xunlock(&lf_owner_graph_lock);
1077 * Insert lock into the active list, keeping list entries ordered by
1078 * increasing values of lf_start.
1081 lf_insert_lock(struct lockf *state, struct lockf_entry *lock)
1083 struct lockf_entry *lf, *lfprev;
1085 if (LIST_EMPTY(&state->ls_active)) {
1086 LIST_INSERT_HEAD(&state->ls_active, lock, lf_link);
1091 LIST_FOREACH(lf, &state->ls_active, lf_link) {
1092 if (lf->lf_start > lock->lf_start) {
1093 LIST_INSERT_BEFORE(lf, lock, lf_link);
1098 LIST_INSERT_AFTER(lfprev, lock, lf_link);
1102 * Wake up a sleeping lock and remove it from the pending list now
1103 * that all its dependencies have been resolved. The caller should
1104 * arrange for the lock to be added to the active list, adjusting any
1105 * existing locks for the same owner as needed.
1108 lf_wakeup_lock(struct lockf *state, struct lockf_entry *wakelock)
1112 * Remove from ls_pending list and wake up the caller
1113 * or start the async notification, as appropriate.
1115 LIST_REMOVE(wakelock, lf_link);
1117 if (lockf_debug & 1)
1118 lf_print("lf_wakeup_lock: awakening", wakelock);
1119 #endif /* LOCKF_DEBUG */
1120 if (wakelock->lf_async_task) {
1121 taskqueue_enqueue(taskqueue_thread, wakelock->lf_async_task);
1128 * Re-check all dependent locks and remove edges to locks that we no
1129 * longer block. If 'all' is non-zero, the lock has been removed and
1130 * we must remove all the dependencies, otherwise it has simply been
1131 * reduced but remains active. Any pending locks which have been been
1132 * unblocked are added to 'granted'
1135 lf_update_dependancies(struct lockf *state, struct lockf_entry *lock, int all,
1136 struct lockf_entry_list *granted)
1138 struct lockf_edge *e, *ne;
1139 struct lockf_entry *deplock;
1141 LIST_FOREACH_SAFE(e, &lock->lf_inedges, le_inlink, ne) {
1142 deplock = e->le_from;
1143 if (all || !lf_blocks(lock, deplock)) {
1144 sx_xlock(&lf_owner_graph_lock);
1146 sx_xunlock(&lf_owner_graph_lock);
1147 if (LIST_EMPTY(&deplock->lf_outedges)) {
1148 lf_wakeup_lock(state, deplock);
1149 LIST_INSERT_HEAD(granted, deplock, lf_link);
1156 * Set the start of an existing active lock, updating dependencies and
1157 * adding any newly woken locks to 'granted'.
1160 lf_set_start(struct lockf *state, struct lockf_entry *lock, off_t new_start,
1161 struct lockf_entry_list *granted)
1164 KASSERT(new_start >= lock->lf_start, ("can't increase lock"));
1165 lock->lf_start = new_start;
1166 LIST_REMOVE(lock, lf_link);
1167 lf_insert_lock(state, lock);
1168 lf_update_dependancies(state, lock, FALSE, granted);
1172 * Set the end of an existing active lock, updating dependencies and
1173 * adding any newly woken locks to 'granted'.
1176 lf_set_end(struct lockf *state, struct lockf_entry *lock, off_t new_end,
1177 struct lockf_entry_list *granted)
1180 KASSERT(new_end <= lock->lf_end, ("can't increase lock"));
1181 lock->lf_end = new_end;
1182 lf_update_dependancies(state, lock, FALSE, granted);
1186 * Add a lock to the active list, updating or removing any current
1187 * locks owned by the same owner and processing any pending locks that
1188 * become unblocked as a result. This code is also used for unlock
1189 * since the logic for updating existing locks is identical.
1191 * As a result of processing the new lock, we may unblock existing
1192 * pending locks as a result of downgrading/unlocking. We simply
1193 * activate the newly granted locks by looping.
1195 * Since the new lock already has its dependencies set up, we always
1196 * add it to the list (unless its an unlock request). This may
1197 * fragment the lock list in some pathological cases but its probably
1198 * not a real problem.
1201 lf_activate_lock(struct lockf *state, struct lockf_entry *lock)
1203 struct lockf_entry *overlap, *lf;
1204 struct lockf_entry_list granted;
1207 LIST_INIT(&granted);
1208 LIST_INSERT_HEAD(&granted, lock, lf_link);
1210 while (!LIST_EMPTY(&granted)) {
1211 lock = LIST_FIRST(&granted);
1212 LIST_REMOVE(lock, lf_link);
1215 * Skip over locks owned by other processes. Handle
1216 * any locks that overlap and are owned by ourselves.
1218 overlap = LIST_FIRST(&state->ls_active);
1220 ovcase = lf_findoverlap(&overlap, lock, SELF);
1223 if (ovcase && (lockf_debug & 2)) {
1224 printf("lf_setlock: overlap %d", ovcase);
1225 lf_print("", overlap);
1231 * 1) overlap == lock
1232 * 2) overlap contains lock
1233 * 3) lock contains overlap
1234 * 4) overlap starts before lock
1235 * 5) overlap ends after lock
1238 case 0: /* no overlap */
1241 case 1: /* overlap == lock */
1243 * We have already setup the
1244 * dependants for the new lock, taking
1245 * into account a possible downgrade
1246 * or unlock. Remove the old lock.
1248 LIST_REMOVE(overlap, lf_link);
1249 lf_update_dependancies(state, overlap, TRUE,
1251 lf_free_lock(overlap);
1254 case 2: /* overlap contains lock */
1256 * Just split the existing lock.
1258 lf_split(state, overlap, lock, &granted);
1261 case 3: /* lock contains overlap */
1263 * Delete the overlap and advance to
1264 * the next entry in the list.
1266 lf = LIST_NEXT(overlap, lf_link);
1267 LIST_REMOVE(overlap, lf_link);
1268 lf_update_dependancies(state, overlap, TRUE,
1270 lf_free_lock(overlap);
1274 case 4: /* overlap starts before lock */
1276 * Just update the overlap end and
1279 lf_set_end(state, overlap, lock->lf_start - 1,
1281 overlap = LIST_NEXT(overlap, lf_link);
1284 case 5: /* overlap ends after lock */
1286 * Change the start of overlap and
1289 lf_set_start(state, overlap, lock->lf_end + 1,
1296 if (lockf_debug & 1) {
1297 if (lock->lf_type != F_UNLCK)
1298 lf_print("lf_activate_lock: activated", lock);
1300 lf_print("lf_activate_lock: unlocked", lock);
1301 lf_printlist("lf_activate_lock", lock);
1303 #endif /* LOCKF_DEBUG */
1304 if (lock->lf_type != F_UNLCK)
1305 lf_insert_lock(state, lock);
1310 * Cancel a pending lock request, either as a result of a signal or a
1311 * cancel request for an async lock.
1314 lf_cancel_lock(struct lockf *state, struct lockf_entry *lock)
1316 struct lockf_entry_list granted;
1319 * Note it is theoretically possible that cancelling this lock
1320 * may allow some other pending lock to become
1321 * active. Consider this case:
1323 * Owner Action Result Dependencies
1325 * A: lock [0..0] succeeds
1326 * B: lock [2..2] succeeds
1327 * C: lock [1..2] blocked C->B
1328 * D: lock [0..1] blocked C->B,D->A,D->C
1329 * A: unlock [0..0] C->B,D->C
1333 LIST_REMOVE(lock, lf_link);
1336 * Removing out-going edges is simple.
1338 sx_xlock(&lf_owner_graph_lock);
1339 lf_remove_outgoing(lock);
1340 sx_xunlock(&lf_owner_graph_lock);
1343 * Removing in-coming edges may allow some other lock to
1344 * become active - we use lf_update_dependancies to figure
1347 LIST_INIT(&granted);
1348 lf_update_dependancies(state, lock, TRUE, &granted);
1352 * Feed any newly active locks to lf_activate_lock.
1354 while (!LIST_EMPTY(&granted)) {
1355 lock = LIST_FIRST(&granted);
1356 LIST_REMOVE(lock, lf_link);
1357 lf_activate_lock(state, lock);
1362 * Set a byte-range lock.
1365 lf_setlock(struct lockf *state, struct lockf_entry *lock, struct vnode *vp,
1368 static char lockstr[] = "lockf";
1369 int error, priority, stops_deferred;
1372 if (lockf_debug & 1)
1373 lf_print("lf_setlock", lock);
1374 #endif /* LOCKF_DEBUG */
1380 if (lock->lf_type == F_WRLCK)
1382 if (!(lock->lf_flags & F_NOINTR))
1385 * Scan lock list for this file looking for locks that would block us.
1387 if (lf_getblock(state, lock)) {
1389 * Free the structure and return if nonblocking.
1391 if ((lock->lf_flags & F_WAIT) == 0
1392 && lock->lf_async_task == NULL) {
1399 * For flock type locks, we must first remove
1400 * any shared locks that we hold before we sleep
1401 * waiting for an exclusive lock.
1403 if ((lock->lf_flags & F_FLOCK) &&
1404 lock->lf_type == F_WRLCK) {
1405 lock->lf_type = F_UNLCK;
1406 lf_activate_lock(state, lock);
1407 lock->lf_type = F_WRLCK;
1411 * We are blocked. Create edges to each blocking lock,
1412 * checking for deadlock using the owner graph. For
1413 * simplicity, we run deadlock detection for all
1414 * locks, posix and otherwise.
1416 sx_xlock(&lf_owner_graph_lock);
1417 error = lf_add_outgoing(state, lock);
1418 sx_xunlock(&lf_owner_graph_lock);
1422 if (lockf_debug & 1)
1423 lf_print("lf_setlock: deadlock", lock);
1430 * We have added edges to everything that blocks
1431 * us. Sleep until they all go away.
1433 LIST_INSERT_HEAD(&state->ls_pending, lock, lf_link);
1435 if (lockf_debug & 1) {
1436 struct lockf_edge *e;
1437 LIST_FOREACH(e, &lock->lf_outedges, le_outlink) {
1438 lf_print("lf_setlock: blocking on", e->le_to);
1439 lf_printlist("lf_setlock", e->le_to);
1442 #endif /* LOCKF_DEBUG */
1444 if ((lock->lf_flags & F_WAIT) == 0) {
1446 * The caller requested async notification -
1447 * this callback happens when the blocking
1448 * lock is released, allowing the caller to
1449 * make another attempt to take the lock.
1451 *cookiep = (void *) lock;
1452 error = EINPROGRESS;
1457 stops_deferred = sigdeferstop(SIGDEFERSTOP_ERESTART);
1458 error = sx_sleep(lock, &state->ls_lock, priority, lockstr, 0);
1459 sigallowstop(stops_deferred);
1460 if (lf_free_lock(lock)) {
1466 * We may have been awakened by a signal and/or by a
1467 * debugger continuing us (in which cases we must
1468 * remove our lock graph edges) and/or by another
1469 * process releasing a lock (in which case our edges
1470 * have already been removed and we have been moved to
1471 * the active list). We may also have been woken by
1472 * lf_purgelocks which we report to the caller as
1473 * EINTR. In that case, lf_purgelocks will have
1474 * removed our lock graph edges.
1476 * Note that it is possible to receive a signal after
1477 * we were successfully woken (and moved to the active
1478 * list) but before we resumed execution. In this
1479 * case, our lf_outedges list will be clear. We
1480 * pretend there was no error.
1482 * Note also, if we have been sleeping long enough, we
1483 * may now have incoming edges from some newer lock
1484 * which is waiting behind us in the queue.
1486 if (lock->lf_flags & F_INTR) {
1491 if (LIST_EMPTY(&lock->lf_outedges)) {
1494 lf_cancel_lock(state, lock);
1498 if (lockf_debug & 1) {
1499 lf_print("lf_setlock: granted", lock);
1505 * It looks like we are going to grant the lock. First add
1506 * edges from any currently pending lock that the new lock
1509 error = lf_add_incoming(state, lock);
1512 if (lockf_debug & 1)
1513 lf_print("lf_setlock: deadlock", lock);
1520 * No blocks!! Add the lock. Note that we will
1521 * downgrade or upgrade any overlapping locks this
1522 * process already owns.
1524 lf_activate_lock(state, lock);
1531 * Remove a byte-range lock on an inode.
1533 * Generally, find the lock (or an overlap to that lock)
1534 * and remove it (or shrink it), then wakeup anyone we can.
1537 lf_clearlock(struct lockf *state, struct lockf_entry *unlock)
1539 struct lockf_entry *overlap;
1541 overlap = LIST_FIRST(&state->ls_active);
1543 if (overlap == NOLOCKF)
1546 if (unlock->lf_type != F_UNLCK)
1547 panic("lf_clearlock: bad type");
1548 if (lockf_debug & 1)
1549 lf_print("lf_clearlock", unlock);
1550 #endif /* LOCKF_DEBUG */
1552 lf_activate_lock(state, unlock);
1558 * Check whether there is a blocking lock, and if so return its
1562 lf_getlock(struct lockf *state, struct lockf_entry *lock, struct flock *fl)
1564 struct lockf_entry *block;
1567 if (lockf_debug & 1)
1568 lf_print("lf_getlock", lock);
1569 #endif /* LOCKF_DEBUG */
1571 if ((block = lf_getblock(state, lock))) {
1572 fl->l_type = block->lf_type;
1573 fl->l_whence = SEEK_SET;
1574 fl->l_start = block->lf_start;
1575 if (block->lf_end == OFF_MAX)
1578 fl->l_len = block->lf_end - block->lf_start + 1;
1579 fl->l_pid = block->lf_owner->lo_pid;
1580 fl->l_sysid = block->lf_owner->lo_sysid;
1582 fl->l_type = F_UNLCK;
1588 * Cancel an async lock request.
1591 lf_cancel(struct lockf *state, struct lockf_entry *lock, void *cookie)
1593 struct lockf_entry *reallock;
1596 * We need to match this request with an existing lock
1599 LIST_FOREACH(reallock, &state->ls_pending, lf_link) {
1600 if ((void *) reallock == cookie) {
1602 * Double-check that this lock looks right
1603 * (maybe use a rolling ID for the cancel
1606 if (!(reallock->lf_vnode == lock->lf_vnode
1607 && reallock->lf_start == lock->lf_start
1608 && reallock->lf_end == lock->lf_end)) {
1613 * Make sure this lock was async and then just
1614 * remove it from its wait lists.
1616 if (!reallock->lf_async_task) {
1621 * Note that since any other thread must take
1622 * state->ls_lock before it can possibly
1623 * trigger the async callback, we are safe
1624 * from a race with lf_wakeup_lock, i.e. we
1625 * can free the lock (actually our caller does
1628 lf_cancel_lock(state, reallock);
1634 * We didn't find a matching lock - not much we can do here.
1640 * Walk the list of locks for an inode and
1641 * return the first blocking lock.
1643 static struct lockf_entry *
1644 lf_getblock(struct lockf *state, struct lockf_entry *lock)
1646 struct lockf_entry *overlap;
1648 LIST_FOREACH(overlap, &state->ls_active, lf_link) {
1650 * We may assume that the active list is sorted by
1653 if (overlap->lf_start > lock->lf_end)
1655 if (!lf_blocks(lock, overlap))
1663 * Walk the list of locks for an inode to find an overlapping lock (if
1664 * any) and return a classification of that overlap.
1667 * *overlap The place in the lock list to start looking
1668 * lock The lock which is being tested
1669 * type Pass 'SELF' to test only locks with the same
1670 * owner as lock, or 'OTHER' to test only locks
1671 * with a different owner
1673 * Returns one of six values:
1675 * 1) overlap == lock
1676 * 2) overlap contains lock
1677 * 3) lock contains overlap
1678 * 4) overlap starts before lock
1679 * 5) overlap ends after lock
1681 * If there is an overlapping lock, '*overlap' is set to point at the
1684 * NOTE: this returns only the FIRST overlapping lock. There
1685 * may be more than one.
1688 lf_findoverlap(struct lockf_entry **overlap, struct lockf_entry *lock, int type)
1690 struct lockf_entry *lf;
1694 if ((*overlap) == NOLOCKF) {
1698 if (lockf_debug & 2)
1699 lf_print("lf_findoverlap: looking for overlap in", lock);
1700 #endif /* LOCKF_DEBUG */
1701 start = lock->lf_start;
1706 if (lf->lf_start > end)
1708 if (((type & SELF) && lf->lf_owner != lock->lf_owner) ||
1709 ((type & OTHERS) && lf->lf_owner == lock->lf_owner)) {
1710 *overlap = LIST_NEXT(lf, lf_link);
1714 if (lockf_debug & 2)
1715 lf_print("\tchecking", lf);
1716 #endif /* LOCKF_DEBUG */
1718 * OK, check for overlap
1722 * 1) overlap == lock
1723 * 2) overlap contains lock
1724 * 3) lock contains overlap
1725 * 4) overlap starts before lock
1726 * 5) overlap ends after lock
1728 if (start > lf->lf_end) {
1731 if (lockf_debug & 2)
1732 printf("no overlap\n");
1733 #endif /* LOCKF_DEBUG */
1734 *overlap = LIST_NEXT(lf, lf_link);
1737 if (lf->lf_start == start && lf->lf_end == end) {
1740 if (lockf_debug & 2)
1741 printf("overlap == lock\n");
1742 #endif /* LOCKF_DEBUG */
1746 if (lf->lf_start <= start && lf->lf_end >= end) {
1749 if (lockf_debug & 2)
1750 printf("overlap contains lock\n");
1751 #endif /* LOCKF_DEBUG */
1755 if (start <= lf->lf_start && end >= lf->lf_end) {
1758 if (lockf_debug & 2)
1759 printf("lock contains overlap\n");
1760 #endif /* LOCKF_DEBUG */
1764 if (lf->lf_start < start && lf->lf_end >= start) {
1767 if (lockf_debug & 2)
1768 printf("overlap starts before lock\n");
1769 #endif /* LOCKF_DEBUG */
1773 if (lf->lf_start > start && lf->lf_end > end) {
1776 if (lockf_debug & 2)
1777 printf("overlap ends after lock\n");
1778 #endif /* LOCKF_DEBUG */
1782 panic("lf_findoverlap: default");
1788 * Split an the existing 'lock1', based on the extent of the lock
1789 * described by 'lock2'. The existing lock should cover 'lock2'
1792 * Any pending locks which have been been unblocked are added to
1796 lf_split(struct lockf *state, struct lockf_entry *lock1,
1797 struct lockf_entry *lock2, struct lockf_entry_list *granted)
1799 struct lockf_entry *splitlock;
1802 if (lockf_debug & 2) {
1803 lf_print("lf_split", lock1);
1804 lf_print("splitting from", lock2);
1806 #endif /* LOCKF_DEBUG */
1808 * Check to see if we don't need to split at all.
1810 if (lock1->lf_start == lock2->lf_start) {
1811 lf_set_start(state, lock1, lock2->lf_end + 1, granted);
1814 if (lock1->lf_end == lock2->lf_end) {
1815 lf_set_end(state, lock1, lock2->lf_start - 1, granted);
1819 * Make a new lock consisting of the last part of
1820 * the encompassing lock.
1822 splitlock = lf_alloc_lock(lock1->lf_owner);
1823 memcpy(splitlock, lock1, sizeof *splitlock);
1824 splitlock->lf_refs = 1;
1825 if (splitlock->lf_flags & F_REMOTE)
1826 vref(splitlock->lf_vnode);
1829 * This cannot cause a deadlock since any edges we would add
1830 * to splitlock already exist in lock1. We must be sure to add
1831 * necessary dependencies to splitlock before we reduce lock1
1832 * otherwise we may accidentally grant a pending lock that
1833 * was blocked by the tail end of lock1.
1835 splitlock->lf_start = lock2->lf_end + 1;
1836 LIST_INIT(&splitlock->lf_outedges);
1837 LIST_INIT(&splitlock->lf_inedges);
1838 lf_add_incoming(state, splitlock);
1840 lf_set_end(state, lock1, lock2->lf_start - 1, granted);
1843 * OK, now link it in
1845 lf_insert_lock(state, splitlock);
1849 STAILQ_ENTRY(lockdesc) link;
1853 STAILQ_HEAD(lockdesclist, lockdesc);
1856 lf_iteratelocks_sysid(int sysid, lf_iterator *fn, void *arg)
1859 struct lockf_entry *lf;
1860 struct lockdesc *ldesc;
1861 struct lockdesclist locks;
1865 * In order to keep the locking simple, we iterate over the
1866 * active lock lists to build a list of locks that need
1867 * releasing. We then call the iterator for each one in turn.
1869 * We take an extra reference to the vnode for the duration to
1870 * make sure it doesn't go away before we are finished.
1872 STAILQ_INIT(&locks);
1873 sx_xlock(&lf_lock_states_lock);
1874 LIST_FOREACH(ls, &lf_lock_states, ls_link) {
1875 sx_xlock(&ls->ls_lock);
1876 LIST_FOREACH(lf, &ls->ls_active, lf_link) {
1877 if (lf->lf_owner->lo_sysid != sysid)
1880 ldesc = malloc(sizeof(struct lockdesc), M_LOCKF,
1882 ldesc->vp = lf->lf_vnode;
1884 ldesc->fl.l_start = lf->lf_start;
1885 if (lf->lf_end == OFF_MAX)
1886 ldesc->fl.l_len = 0;
1889 lf->lf_end - lf->lf_start + 1;
1890 ldesc->fl.l_whence = SEEK_SET;
1891 ldesc->fl.l_type = F_UNLCK;
1892 ldesc->fl.l_pid = lf->lf_owner->lo_pid;
1893 ldesc->fl.l_sysid = sysid;
1894 STAILQ_INSERT_TAIL(&locks, ldesc, link);
1896 sx_xunlock(&ls->ls_lock);
1898 sx_xunlock(&lf_lock_states_lock);
1901 * Call the iterator function for each lock in turn. If the
1902 * iterator returns an error code, just free the rest of the
1903 * lockdesc structures.
1906 while ((ldesc = STAILQ_FIRST(&locks)) != NULL) {
1907 STAILQ_REMOVE_HEAD(&locks, link);
1909 error = fn(ldesc->vp, &ldesc->fl, arg);
1911 free(ldesc, M_LOCKF);
1918 lf_iteratelocks_vnode(struct vnode *vp, lf_iterator *fn, void *arg)
1921 struct lockf_entry *lf;
1922 struct lockdesc *ldesc;
1923 struct lockdesclist locks;
1927 * In order to keep the locking simple, we iterate over the
1928 * active lock lists to build a list of locks that need
1929 * releasing. We then call the iterator for each one in turn.
1931 * We take an extra reference to the vnode for the duration to
1932 * make sure it doesn't go away before we are finished.
1934 STAILQ_INIT(&locks);
1941 MPASS(ls->ls_threads >= 0);
1945 sx_xlock(&ls->ls_lock);
1946 LIST_FOREACH(lf, &ls->ls_active, lf_link) {
1947 ldesc = malloc(sizeof(struct lockdesc), M_LOCKF,
1949 ldesc->vp = lf->lf_vnode;
1951 ldesc->fl.l_start = lf->lf_start;
1952 if (lf->lf_end == OFF_MAX)
1953 ldesc->fl.l_len = 0;
1956 lf->lf_end - lf->lf_start + 1;
1957 ldesc->fl.l_whence = SEEK_SET;
1958 ldesc->fl.l_type = F_UNLCK;
1959 ldesc->fl.l_pid = lf->lf_owner->lo_pid;
1960 ldesc->fl.l_sysid = lf->lf_owner->lo_sysid;
1961 STAILQ_INSERT_TAIL(&locks, ldesc, link);
1963 sx_xunlock(&ls->ls_lock);
1965 MPASS(ls->ls_threads > 0);
1971 * Call the iterator function for each lock in turn. If the
1972 * iterator returns an error code, just free the rest of the
1973 * lockdesc structures.
1976 while ((ldesc = STAILQ_FIRST(&locks)) != NULL) {
1977 STAILQ_REMOVE_HEAD(&locks, link);
1979 error = fn(ldesc->vp, &ldesc->fl, arg);
1981 free(ldesc, M_LOCKF);
1988 lf_clearremotesys_iterator(struct vnode *vp, struct flock *fl, void *arg)
1991 VOP_ADVLOCK(vp, 0, F_UNLCK, fl, F_REMOTE);
1996 lf_clearremotesys(int sysid)
1999 KASSERT(sysid != 0, ("Can't clear local locks with F_UNLCKSYS"));
2000 lf_iteratelocks_sysid(sysid, lf_clearremotesys_iterator, NULL);
2004 lf_countlocks(int sysid)
2007 struct lock_owner *lo;
2011 for (i = 0; i < LOCK_OWNER_HASH_SIZE; i++) {
2012 sx_xlock(&lf_lock_owners[i].lock);
2013 LIST_FOREACH(lo, &lf_lock_owners[i].list, lo_link)
2014 if (lo->lo_sysid == sysid)
2015 count += lo->lo_refs;
2016 sx_xunlock(&lf_lock_owners[i].lock);
2025 * Return non-zero if y is reachable from x using a brute force
2026 * search. If reachable and path is non-null, return the route taken
2030 graph_reaches(struct owner_vertex *x, struct owner_vertex *y,
2031 struct owner_vertex_list *path)
2033 struct owner_edge *e;
2037 TAILQ_INSERT_HEAD(path, x, v_link);
2041 LIST_FOREACH(e, &x->v_outedges, e_outlink) {
2042 if (graph_reaches(e->e_to, y, path)) {
2044 TAILQ_INSERT_HEAD(path, x, v_link);
2052 * Perform consistency checks on the graph. Make sure the values of
2053 * v_order are correct. If checkorder is non-zero, check no vertex can
2054 * reach any other vertex with a smaller order.
2057 graph_check(struct owner_graph *g, int checkorder)
2061 for (i = 0; i < g->g_size; i++) {
2062 if (!g->g_vertices[i]->v_owner)
2064 KASSERT(g->g_vertices[i]->v_order == i,
2065 ("lock graph vertices disordered"));
2067 for (j = 0; j < i; j++) {
2068 if (!g->g_vertices[j]->v_owner)
2070 KASSERT(!graph_reaches(g->g_vertices[i],
2071 g->g_vertices[j], NULL),
2072 ("lock graph vertices disordered"));
2079 graph_print_vertices(struct owner_vertex_list *set)
2081 struct owner_vertex *v;
2084 TAILQ_FOREACH(v, set, v_link) {
2085 printf("%d:", v->v_order);
2086 lf_print_owner(v->v_owner);
2087 if (TAILQ_NEXT(v, v_link))
2096 * Calculate the sub-set of vertices v from the affected region [y..x]
2097 * where v is reachable from y. Return -1 if a loop was detected
2098 * (i.e. x is reachable from y, otherwise the number of vertices in
2102 graph_delta_forward(struct owner_graph *g, struct owner_vertex *x,
2103 struct owner_vertex *y, struct owner_vertex_list *delta)
2106 struct owner_vertex *v;
2107 struct owner_edge *e;
2111 * We start with a set containing just y. Then for each vertex
2112 * v in the set so far unprocessed, we add each vertex that v
2113 * has an out-edge to and that is within the affected region
2114 * [y..x]. If we see the vertex x on our travels, stop
2118 TAILQ_INSERT_TAIL(delta, y, v_link);
2123 LIST_FOREACH(e, &v->v_outedges, e_outlink) {
2126 if (e->e_to->v_order < x->v_order
2127 && e->e_to->v_gen != gen) {
2128 e->e_to->v_gen = gen;
2129 TAILQ_INSERT_TAIL(delta, e->e_to, v_link);
2133 v = TAILQ_NEXT(v, v_link);
2140 * Calculate the sub-set of vertices v from the affected region [y..x]
2141 * where v reaches x. Return the number of vertices in this subset.
2144 graph_delta_backward(struct owner_graph *g, struct owner_vertex *x,
2145 struct owner_vertex *y, struct owner_vertex_list *delta)
2148 struct owner_vertex *v;
2149 struct owner_edge *e;
2153 * We start with a set containing just x. Then for each vertex
2154 * v in the set so far unprocessed, we add each vertex that v
2155 * has an in-edge from and that is within the affected region
2159 TAILQ_INSERT_TAIL(delta, x, v_link);
2164 LIST_FOREACH(e, &v->v_inedges, e_inlink) {
2165 if (e->e_from->v_order > y->v_order
2166 && e->e_from->v_gen != gen) {
2167 e->e_from->v_gen = gen;
2168 TAILQ_INSERT_HEAD(delta, e->e_from, v_link);
2172 v = TAILQ_PREV(v, owner_vertex_list, v_link);
2179 graph_add_indices(int *indices, int n, struct owner_vertex_list *set)
2181 struct owner_vertex *v;
2184 TAILQ_FOREACH(v, set, v_link) {
2186 i > 0 && indices[i - 1] > v->v_order; i--)
2188 for (j = n - 1; j >= i; j--)
2189 indices[j + 1] = indices[j];
2190 indices[i] = v->v_order;
2198 graph_assign_indices(struct owner_graph *g, int *indices, int nextunused,
2199 struct owner_vertex_list *set)
2201 struct owner_vertex *v, *vlowest;
2203 while (!TAILQ_EMPTY(set)) {
2205 TAILQ_FOREACH(v, set, v_link) {
2206 if (!vlowest || v->v_order < vlowest->v_order)
2209 TAILQ_REMOVE(set, vlowest, v_link);
2210 vlowest->v_order = indices[nextunused];
2211 g->g_vertices[vlowest->v_order] = vlowest;
2215 return (nextunused);
2219 graph_add_edge(struct owner_graph *g, struct owner_vertex *x,
2220 struct owner_vertex *y)
2222 struct owner_edge *e;
2223 struct owner_vertex_list deltaF, deltaB;
2228 sx_assert(&lf_owner_graph_lock, SX_XLOCKED);
2230 LIST_FOREACH(e, &x->v_outedges, e_outlink) {
2238 if (lockf_debug & 8) {
2239 printf("adding edge %d:", x->v_order);
2240 lf_print_owner(x->v_owner);
2241 printf(" -> %d:", y->v_order);
2242 lf_print_owner(y->v_owner);
2246 if (y->v_order < x->v_order) {
2248 * The new edge violates the order. First find the set
2249 * of affected vertices reachable from y (deltaF) and
2250 * the set of affect vertices affected that reach x
2251 * (deltaB), using the graph generation number to
2252 * detect whether we have visited a given vertex
2253 * already. We re-order the graph so that each vertex
2254 * in deltaB appears before each vertex in deltaF.
2256 * If x is a member of deltaF, then the new edge would
2257 * create a cycle. Otherwise, we may assume that
2258 * deltaF and deltaB are disjoint.
2261 if (g->g_gen == 0) {
2265 for (vi = 0; vi < g->g_size; vi++) {
2266 g->g_vertices[vi]->v_gen = 0;
2270 nF = graph_delta_forward(g, x, y, &deltaF);
2273 if (lockf_debug & 8) {
2274 struct owner_vertex_list path;
2275 printf("deadlock: ");
2277 graph_reaches(y, x, &path);
2278 graph_print_vertices(&path);
2285 if (lockf_debug & 8) {
2286 printf("re-ordering graph vertices\n");
2287 printf("deltaF = ");
2288 graph_print_vertices(&deltaF);
2292 nB = graph_delta_backward(g, x, y, &deltaB);
2295 if (lockf_debug & 8) {
2296 printf("deltaB = ");
2297 graph_print_vertices(&deltaB);
2302 * We first build a set of vertex indices (vertex
2303 * order values) that we may use, then we re-assign
2304 * orders first to those vertices in deltaB, then to
2305 * deltaF. Note that the contents of deltaF and deltaB
2306 * may be partially disordered - we perform an
2307 * insertion sort while building our index set.
2309 indices = g->g_indexbuf;
2310 n = graph_add_indices(indices, 0, &deltaF);
2311 graph_add_indices(indices, n, &deltaB);
2314 * We must also be sure to maintain the relative
2315 * ordering of deltaF and deltaB when re-assigning
2316 * vertices. We do this by iteratively removing the
2317 * lowest ordered element from the set and assigning
2318 * it the next value from our new ordering.
2320 i = graph_assign_indices(g, indices, 0, &deltaB);
2321 graph_assign_indices(g, indices, i, &deltaF);
2324 if (lockf_debug & 8) {
2325 struct owner_vertex_list set;
2327 for (i = 0; i < nB + nF; i++)
2328 TAILQ_INSERT_TAIL(&set,
2329 g->g_vertices[indices[i]], v_link);
2330 printf("new ordering = ");
2331 graph_print_vertices(&set);
2336 KASSERT(x->v_order < y->v_order, ("Failed to re-order graph"));
2339 if (lockf_debug & 8) {
2340 graph_check(g, TRUE);
2344 e = malloc(sizeof(struct owner_edge), M_LOCKF, M_WAITOK);
2346 LIST_INSERT_HEAD(&x->v_outedges, e, e_outlink);
2347 LIST_INSERT_HEAD(&y->v_inedges, e, e_inlink);
2356 * Remove an edge x->y from the graph.
2359 graph_remove_edge(struct owner_graph *g, struct owner_vertex *x,
2360 struct owner_vertex *y)
2362 struct owner_edge *e;
2364 sx_assert(&lf_owner_graph_lock, SX_XLOCKED);
2366 LIST_FOREACH(e, &x->v_outedges, e_outlink) {
2370 KASSERT(e, ("Removing non-existent edge from deadlock graph"));
2373 if (e->e_refs == 0) {
2375 if (lockf_debug & 8) {
2376 printf("removing edge %d:", x->v_order);
2377 lf_print_owner(x->v_owner);
2378 printf(" -> %d:", y->v_order);
2379 lf_print_owner(y->v_owner);
2383 LIST_REMOVE(e, e_outlink);
2384 LIST_REMOVE(e, e_inlink);
2390 * Allocate a vertex from the free list. Return ENOMEM if there are
2393 static struct owner_vertex *
2394 graph_alloc_vertex(struct owner_graph *g, struct lock_owner *lo)
2396 struct owner_vertex *v;
2398 sx_assert(&lf_owner_graph_lock, SX_XLOCKED);
2400 v = malloc(sizeof(struct owner_vertex), M_LOCKF, M_WAITOK);
2401 if (g->g_size == g->g_space) {
2402 g->g_vertices = realloc(g->g_vertices,
2403 2 * g->g_space * sizeof(struct owner_vertex *),
2405 free(g->g_indexbuf, M_LOCKF);
2406 g->g_indexbuf = malloc(2 * g->g_space * sizeof(int),
2408 g->g_space = 2 * g->g_space;
2410 v->v_order = g->g_size;
2411 v->v_gen = g->g_gen;
2412 g->g_vertices[g->g_size] = v;
2415 LIST_INIT(&v->v_outedges);
2416 LIST_INIT(&v->v_inedges);
2423 graph_free_vertex(struct owner_graph *g, struct owner_vertex *v)
2425 struct owner_vertex *w;
2428 sx_assert(&lf_owner_graph_lock, SX_XLOCKED);
2430 KASSERT(LIST_EMPTY(&v->v_outedges), ("Freeing vertex with edges"));
2431 KASSERT(LIST_EMPTY(&v->v_inedges), ("Freeing vertex with edges"));
2434 * Remove from the graph's array and close up the gap,
2435 * renumbering the other vertices.
2437 for (i = v->v_order + 1; i < g->g_size; i++) {
2438 w = g->g_vertices[i];
2440 g->g_vertices[i - 1] = w;
2447 static struct owner_graph *
2448 graph_init(struct owner_graph *g)
2451 g->g_vertices = malloc(10 * sizeof(struct owner_vertex *),
2455 g->g_indexbuf = malloc(g->g_space * sizeof(int), M_LOCKF, M_WAITOK);
2461 struct kinfo_lockf_linked {
2462 struct kinfo_lockf kl;
2464 STAILQ_ENTRY(kinfo_lockf_linked) link;
2468 vfs_report_lockf(struct mount *mp, struct sbuf *sb)
2471 struct lockf_entry *lf;
2472 struct kinfo_lockf_linked *klf;
2474 struct ucred *ucred;
2475 char *fullpath, *freepath;
2477 STAILQ_HEAD(, kinfo_lockf_linked) locks;
2480 STAILQ_INIT(&locks);
2481 sx_slock(&lf_lock_states_lock);
2482 LIST_FOREACH(ls, &lf_lock_states, ls_link) {
2483 sx_slock(&ls->ls_lock);
2484 LIST_FOREACH(lf, &ls->ls_active, lf_link) {
2486 if (VN_IS_DOOMED(vp) || vp->v_mount != mp)
2489 klf = malloc(sizeof(struct kinfo_lockf_linked),
2490 M_LOCKF, M_WAITOK | M_ZERO);
2492 klf->kl.kl_structsize = sizeof(struct kinfo_lockf);
2493 klf->kl.kl_start = lf->lf_start;
2494 klf->kl.kl_len = lf->lf_end == OFF_MAX ? 0 :
2495 lf->lf_end - lf->lf_start + 1;
2496 klf->kl.kl_rw = lf->lf_type == F_RDLCK ?
2497 KLOCKF_RW_READ : KLOCKF_RW_WRITE;
2498 if (lf->lf_owner->lo_sysid != 0) {
2499 klf->kl.kl_pid = lf->lf_owner->lo_pid;
2500 klf->kl.kl_sysid = lf->lf_owner->lo_sysid;
2501 klf->kl.kl_type = KLOCKF_TYPE_REMOTE;
2502 } else if (lf->lf_owner->lo_pid == -1) {
2503 klf->kl.kl_pid = -1;
2504 klf->kl.kl_sysid = 0;
2505 klf->kl.kl_type = KLOCKF_TYPE_FLOCK;
2507 klf->kl.kl_pid = lf->lf_owner->lo_pid;
2508 klf->kl.kl_sysid = 0;
2509 klf->kl.kl_type = KLOCKF_TYPE_PID;
2511 STAILQ_INSERT_TAIL(&locks, klf, link);
2513 sx_sunlock(&ls->ls_lock);
2515 sx_sunlock(&lf_lock_states_lock);
2518 ucred = curthread->td_ucred;
2519 while ((klf = STAILQ_FIRST(&locks)) != NULL) {
2520 STAILQ_REMOVE_HEAD(&locks, link);
2522 if (gerror == 0 && vn_lock(vp, LK_SHARED) == 0) {
2523 error = prison_canseemount(ucred, vp->v_mount);
2525 error = VOP_STAT(vp, &stt, ucred, NOCRED);
2528 klf->kl.kl_file_fsid = stt.st_dev;
2529 klf->kl.kl_file_rdev = stt.st_rdev;
2530 klf->kl.kl_file_fileid = stt.st_ino;
2533 error = vn_fullpath(vp, &fullpath, &freepath);
2535 strlcpy(klf->kl.kl_path, fullpath,
2536 sizeof(klf->kl.kl_path));
2537 free(freepath, M_TEMP);
2538 if (sbuf_bcat(sb, &klf->kl,
2539 klf->kl.kl_structsize) != 0) {
2540 gerror = sbuf_error(sb);
2552 sysctl_kern_lockf_run(struct sbuf *sb)
2558 mtx_lock(&mountlist_mtx);
2559 TAILQ_FOREACH(mp, &mountlist, mnt_list) {
2560 error = vfs_busy(mp, MBF_MNTLSTLOCK);
2563 error = mp->mnt_op->vfs_report_lockf(mp, sb);
2564 mtx_lock(&mountlist_mtx);
2569 mtx_unlock(&mountlist_mtx);
2574 sysctl_kern_lockf(SYSCTL_HANDLER_ARGS)
2579 sbuf_new_for_sysctl(&sb, NULL, sizeof(struct kinfo_lockf) * 5, req);
2580 sbuf_clear_flags(&sb, SBUF_INCLUDENUL);
2581 error = sysctl_kern_lockf_run(&sb);
2582 error2 = sbuf_finish(&sb);
2584 return (error != 0 ? error : error2);
2586 SYSCTL_PROC(_kern, KERN_LOCKF, lockf,
2587 CTLTYPE_OPAQUE | CTLFLAG_RD | CTLFLAG_MPSAFE,
2588 0, 0, sysctl_kern_lockf, "S,lockf",
2589 "Advisory locks table");
2593 * Print description of a lock owner
2596 lf_print_owner(struct lock_owner *lo)
2599 if (lo->lo_flags & F_REMOTE) {
2600 printf("remote pid %d, system %d",
2601 lo->lo_pid, lo->lo_sysid);
2602 } else if (lo->lo_flags & F_FLOCK) {
2603 printf("file %p", lo->lo_id);
2605 printf("local pid %d", lo->lo_pid);
2613 lf_print(char *tag, struct lockf_entry *lock)
2616 printf("%s: lock %p for ", tag, (void *)lock);
2617 lf_print_owner(lock->lf_owner);
2618 printf("\nvnode %p", lock->lf_vnode);
2619 VOP_PRINT(lock->lf_vnode);
2620 printf(" %s, start %jd, end ",
2621 lock->lf_type == F_RDLCK ? "shared" :
2622 lock->lf_type == F_WRLCK ? "exclusive" :
2623 lock->lf_type == F_UNLCK ? "unlock" : "unknown",
2624 (intmax_t)lock->lf_start);
2625 if (lock->lf_end == OFF_MAX)
2628 printf("%jd", (intmax_t)lock->lf_end);
2629 if (!LIST_EMPTY(&lock->lf_outedges))
2630 printf(" block %p\n",
2631 (void *)LIST_FIRST(&lock->lf_outedges)->le_to);
2637 lf_printlist(char *tag, struct lockf_entry *lock)
2639 struct lockf_entry *lf, *blk;
2640 struct lockf_edge *e;
2642 printf("%s: Lock list for vnode %p:\n", tag, lock->lf_vnode);
2643 LIST_FOREACH(lf, &lock->lf_vnode->v_lockf->ls_active, lf_link) {
2644 printf("\tlock %p for ",(void *)lf);
2645 lf_print_owner(lock->lf_owner);
2646 printf(", %s, start %jd, end %jd",
2647 lf->lf_type == F_RDLCK ? "shared" :
2648 lf->lf_type == F_WRLCK ? "exclusive" :
2649 lf->lf_type == F_UNLCK ? "unlock" :
2650 "unknown", (intmax_t)lf->lf_start, (intmax_t)lf->lf_end);
2651 LIST_FOREACH(e, &lf->lf_outedges, le_outlink) {
2653 printf("\n\t\tlock request %p for ", (void *)blk);
2654 lf_print_owner(blk->lf_owner);
2655 printf(", %s, start %jd, end %jd",
2656 blk->lf_type == F_RDLCK ? "shared" :
2657 blk->lf_type == F_WRLCK ? "exclusive" :
2658 blk->lf_type == F_UNLCK ? "unlock" :
2659 "unknown", (intmax_t)blk->lf_start,
2660 (intmax_t)blk->lf_end);
2661 if (!LIST_EMPTY(&blk->lf_inedges))
2662 panic("lf_printlist: bad list");
2667 #endif /* LOCKF_DEBUG */