FreeBSD/Linux Kernel Cross Reference
sys/kern/kern_lockf.c
1 /*-
2 * Copyright (c) 2008 Isilon Inc http://www.isilon.com/
3 * Authors: Doug Rabson <dfr@rabson.org>
4 * Developed with Red Inc: Alfred Perlstein <alfred@freebsd.org>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 */
27 /*-
28 * Copyright (c) 1982, 1986, 1989, 1993
29 * The Regents of the University of California. All rights reserved.
30 *
31 * This code is derived from software contributed to Berkeley by
32 * Scooter Morris at Genentech Inc.
33 *
34 * Redistribution and use in source and binary forms, with or without
35 * modification, are permitted provided that the following conditions
36 * are met:
37 * 1. Redistributions of source code must retain the above copyright
38 * notice, this list of conditions and the following disclaimer.
39 * 2. Redistributions in binary form must reproduce the above copyright
40 * notice, this list of conditions and the following disclaimer in the
41 * documentation and/or other materials provided with the distribution.
42 * 4. Neither the name of the University nor the names of its contributors
43 * may be used to endorse or promote products derived from this software
44 * without specific prior written permission.
45 *
46 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
47 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
50 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
51 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
52 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
53 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
54 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
55 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
56 * SUCH DAMAGE.
57 *
58 * @(#)ufs_lockf.c 8.3 (Berkeley) 1/6/94
59 */
60
61 #include <sys/cdefs.h>
62 __FBSDID("$FreeBSD: src/sys/kern/kern_lockf.c,v 1.65 2008/06/26 10:21:54 dfr Exp $");
63
64 #include "opt_debug_lockf.h"
65
66 #include <sys/param.h>
67 #include <sys/systm.h>
68 #include <sys/hash.h>
69 #include <sys/kernel.h>
70 #include <sys/limits.h>
71 #include <sys/lock.h>
72 #include <sys/mount.h>
73 #include <sys/mutex.h>
74 #include <sys/proc.h>
75 #include <sys/sx.h>
76 #include <sys/unistd.h>
77 #include <sys/vnode.h>
78 #include <sys/malloc.h>
79 #include <sys/fcntl.h>
80 #include <sys/lockf.h>
81 #include <sys/taskqueue.h>
82
83 #ifdef LOCKF_DEBUG
84 #include <sys/sysctl.h>
85
86 #include <ufs/ufs/quota.h>
87 #include <ufs/ufs/inode.h>
88
89 static int lockf_debug = 0; /* control debug output */
90 SYSCTL_INT(_debug, OID_AUTO, lockf_debug, CTLFLAG_RW, &lockf_debug, 0, "");
91 #endif
92
93 MALLOC_DEFINE(M_LOCKF, "lockf", "Byte-range locking structures");
94
95 struct owner_edge;
96 struct owner_vertex;
97 struct owner_vertex_list;
98 struct owner_graph;
99
100 #define NOLOCKF (struct lockf_entry *)0
101 #define SELF 0x1
102 #define OTHERS 0x2
103 static void lf_init(void *);
104 static int lf_hash_owner(caddr_t, struct flock *, int);
105 static int lf_owner_matches(struct lock_owner *, caddr_t, struct flock *,
106 int);
107 static struct lockf_entry *
108 lf_alloc_lock(struct lock_owner *);
109 static void lf_free_lock(struct lockf_entry *);
110 static int lf_clearlock(struct lockf *, struct lockf_entry *);
111 static int lf_overlaps(struct lockf_entry *, struct lockf_entry *);
112 static int lf_blocks(struct lockf_entry *, struct lockf_entry *);
113 static void lf_free_edge(struct lockf_edge *);
114 static struct lockf_edge *
115 lf_alloc_edge(void);
116 static void lf_alloc_vertex(struct lockf_entry *);
117 static int lf_add_edge(struct lockf_entry *, struct lockf_entry *);
118 static void lf_remove_edge(struct lockf_edge *);
119 static void lf_remove_outgoing(struct lockf_entry *);
120 static void lf_remove_incoming(struct lockf_entry *);
121 static int lf_add_outgoing(struct lockf *, struct lockf_entry *);
122 static int lf_add_incoming(struct lockf *, struct lockf_entry *);
123 static int lf_findoverlap(struct lockf_entry **, struct lockf_entry *,
124 int);
125 static struct lockf_entry *
126 lf_getblock(struct lockf *, struct lockf_entry *);
127 static int lf_getlock(struct lockf *, struct lockf_entry *, struct flock *);
128 static void lf_insert_lock(struct lockf *, struct lockf_entry *);
129 static void lf_wakeup_lock(struct lockf *, struct lockf_entry *);
130 static void lf_update_dependancies(struct lockf *, struct lockf_entry *,
131 int all, struct lockf_entry_list *);
132 static void lf_set_start(struct lockf *, struct lockf_entry *, off_t,
133 struct lockf_entry_list*);
134 static void lf_set_end(struct lockf *, struct lockf_entry *, off_t,
135 struct lockf_entry_list*);
136 static int lf_setlock(struct lockf *, struct lockf_entry *,
137 struct vnode *, void **cookiep);
138 static int lf_cancel(struct lockf *, struct lockf_entry *, void *);
139 static void lf_split(struct lockf *, struct lockf_entry *,
140 struct lockf_entry *, struct lockf_entry_list *);
141 #ifdef LOCKF_DEBUG
142 static int graph_reaches(struct owner_vertex *x, struct owner_vertex *y,
143 struct owner_vertex_list *path);
144 static void graph_check(struct owner_graph *g, int checkorder);
145 static void graph_print_vertices(struct owner_vertex_list *set);
146 #endif
147 static int graph_delta_forward(struct owner_graph *g,
148 struct owner_vertex *x, struct owner_vertex *y,
149 struct owner_vertex_list *delta);
150 static int graph_delta_backward(struct owner_graph *g,
151 struct owner_vertex *x, struct owner_vertex *y,
152 struct owner_vertex_list *delta);
153 static int graph_add_indices(int *indices, int n,
154 struct owner_vertex_list *set);
155 static int graph_assign_indices(struct owner_graph *g, int *indices,
156 int nextunused, struct owner_vertex_list *set);
157 static int graph_add_edge(struct owner_graph *g,
158 struct owner_vertex *x, struct owner_vertex *y);
159 static void graph_remove_edge(struct owner_graph *g,
160 struct owner_vertex *x, struct owner_vertex *y);
161 static struct owner_vertex *graph_alloc_vertex(struct owner_graph *g,
162 struct lock_owner *lo);
163 static void graph_free_vertex(struct owner_graph *g,
164 struct owner_vertex *v);
165 static struct owner_graph * graph_init(struct owner_graph *g);
166 #ifdef LOCKF_DEBUG
167 static void lf_print(char *, struct lockf_entry *);
168 static void lf_printlist(char *, struct lockf_entry *);
169 static void lf_print_owner(struct lock_owner *);
170 #endif
171
172 /*
173 * This structure is used to keep track of both local and remote lock
174 * owners. The lf_owner field of the struct lockf_entry points back at
175 * the lock owner structure. Each possible lock owner (local proc for
176 * POSIX fcntl locks, local file for BSD flock locks or <pid,sysid>
177 * pair for remote locks) is represented by a unique instance of
178 * struct lock_owner.
179 *
180 * If a lock owner has a lock that blocks some other lock or a lock
181 * that is waiting for some other lock, it also has a vertex in the
182 * owner_graph below.
183 *
184 * Locks:
185 * (s) locked by state->ls_lock
186 * (S) locked by lf_lock_states_lock
187 * (l) locked by lf_lock_owners_lock
188 * (g) locked by lf_owner_graph_lock
189 * (c) const until freeing
190 */
191 #define LOCK_OWNER_HASH_SIZE 256
192
193 struct lock_owner {
194 LIST_ENTRY(lock_owner) lo_link; /* (l) hash chain */
195 int lo_refs; /* (l) Number of locks referring to this */
196 int lo_flags; /* (c) Flags passwd to lf_advlock */
197 caddr_t lo_id; /* (c) Id value passed to lf_advlock */
198 pid_t lo_pid; /* (c) Process Id of the lock owner */
199 int lo_sysid; /* (c) System Id of the lock owner */
200 struct owner_vertex *lo_vertex; /* (g) entry in deadlock graph */
201 };
202
203 LIST_HEAD(lock_owner_list, lock_owner);
204
205 static struct sx lf_lock_states_lock;
206 static struct lockf_list lf_lock_states; /* (S) */
207 static struct sx lf_lock_owners_lock;
208 static struct lock_owner_list lf_lock_owners[LOCK_OWNER_HASH_SIZE]; /* (l) */
209
210 /*
211 * Structures for deadlock detection.
212 *
213 * We have two types of directed graph, the first is the set of locks,
214 * both active and pending on a vnode. Within this graph, active locks
215 * are terminal nodes in the graph (i.e. have no out-going
216 * edges). Pending locks have out-going edges to each blocking active
217 * lock that prevents the lock from being granted and also to each
218 * older pending lock that would block them if it was active. The
219 * graph for each vnode is naturally acyclic; new edges are only ever
220 * added to or from new nodes (either new pending locks which only add
221 * out-going edges or new active locks which only add in-coming edges)
222 * therefore they cannot create loops in the lock graph.
223 *
224 * The second graph is a global graph of lock owners. Each lock owner
225 * is a vertex in that graph and an edge is added to the graph
226 * whenever an edge is added to a vnode graph, with end points
227 * corresponding to owner of the new pending lock and the owner of the
228 * lock upon which it waits. In order to prevent deadlock, we only add
229 * an edge to this graph if the new edge would not create a cycle.
230 *
231 * The lock owner graph is topologically sorted, i.e. if a node has
232 * any outgoing edges, then it has an order strictly less than any
233 * node to which it has an outgoing edge. We preserve this ordering
234 * (and detect cycles) on edge insertion using Algorithm PK from the
235 * paper "A Dynamic Topological Sort Algorithm for Directed Acyclic
236 * Graphs" (ACM Journal of Experimental Algorithms, Vol 11, Article
237 * No. 1.7)
238 */
239 struct owner_vertex;
240
241 struct owner_edge {
242 LIST_ENTRY(owner_edge) e_outlink; /* (g) link from's out-edge list */
243 LIST_ENTRY(owner_edge) e_inlink; /* (g) link to's in-edge list */
244 int e_refs; /* (g) number of times added */
245 struct owner_vertex *e_from; /* (c) out-going from here */
246 struct owner_vertex *e_to; /* (c) in-coming to here */
247 };
248 LIST_HEAD(owner_edge_list, owner_edge);
249
250 struct owner_vertex {
251 TAILQ_ENTRY(owner_vertex) v_link; /* (g) workspace for edge insertion */
252 uint32_t v_gen; /* (g) workspace for edge insertion */
253 int v_order; /* (g) order of vertex in graph */
254 struct owner_edge_list v_outedges;/* (g) list of out-edges */
255 struct owner_edge_list v_inedges; /* (g) list of in-edges */
256 struct lock_owner *v_owner; /* (c) corresponding lock owner */
257 };
258 TAILQ_HEAD(owner_vertex_list, owner_vertex);
259
260 struct owner_graph {
261 struct owner_vertex** g_vertices; /* (g) pointers to vertices */
262 int g_size; /* (g) number of vertices */
263 int g_space; /* (g) space allocated for vertices */
264 int *g_indexbuf; /* (g) workspace for loop detection */
265 uint32_t g_gen; /* (g) increment when re-ordering */
266 };
267
268 static struct sx lf_owner_graph_lock;
269 static struct owner_graph lf_owner_graph;
270
271 /*
272 * Initialise various structures and locks.
273 */
274 static void
275 lf_init(void *dummy)
276 {
277 int i;
278
279 sx_init(&lf_lock_states_lock, "lock states lock");
280 LIST_INIT(&lf_lock_states);
281
282 sx_init(&lf_lock_owners_lock, "lock owners lock");
283 for (i = 0; i < LOCK_OWNER_HASH_SIZE; i++)
284 LIST_INIT(&lf_lock_owners[i]);
285
286 sx_init(&lf_owner_graph_lock, "owner graph lock");
287 graph_init(&lf_owner_graph);
288 }
289 SYSINIT(lf_init, SI_SUB_LOCK, SI_ORDER_FIRST, lf_init, NULL);
290
291 /*
292 * Generate a hash value for a lock owner.
293 */
294 static int
295 lf_hash_owner(caddr_t id, struct flock *fl, int flags)
296 {
297 uint32_t h;
298
299 if (flags & F_REMOTE) {
300 h = HASHSTEP(0, fl->l_pid);
301 h = HASHSTEP(h, fl->l_sysid);
302 } else if (flags & F_FLOCK) {
303 h = ((uintptr_t) id) >> 7;
304 } else {
305 struct proc *p = (struct proc *) id;
306 h = HASHSTEP(0, p->p_pid);
307 h = HASHSTEP(h, 0);
308 }
309
310 return (h % LOCK_OWNER_HASH_SIZE);
311 }
312
313 /*
314 * Return true if a lock owner matches the details passed to
315 * lf_advlock.
316 */
317 static int
318 lf_owner_matches(struct lock_owner *lo, caddr_t id, struct flock *fl,
319 int flags)
320 {
321 if (flags & F_REMOTE) {
322 return lo->lo_pid == fl->l_pid
323 && lo->lo_sysid == fl->l_sysid;
324 } else {
325 return lo->lo_id == id;
326 }
327 }
328
329 static struct lockf_entry *
330 lf_alloc_lock(struct lock_owner *lo)
331 {
332 struct lockf_entry *lf;
333
334 lf = malloc(sizeof(struct lockf_entry), M_LOCKF, M_WAITOK|M_ZERO);
335
336 #ifdef LOCKF_DEBUG
337 if (lockf_debug & 4)
338 printf("Allocated lock %p\n", lf);
339 #endif
340 if (lo) {
341 sx_xlock(&lf_lock_owners_lock);
342 lo->lo_refs++;
343 sx_xunlock(&lf_lock_owners_lock);
344 lf->lf_owner = lo;
345 }
346
347 return (lf);
348 }
349
350 static void
351 lf_free_lock(struct lockf_entry *lock)
352 {
353 /*
354 * Adjust the lock_owner reference count and
355 * reclaim the entry if this is the last lock
356 * for that owner.
357 */
358 struct lock_owner *lo = lock->lf_owner;
359 if (lo) {
360 KASSERT(LIST_EMPTY(&lock->lf_outedges),
361 ("freeing lock with dependancies"));
362 KASSERT(LIST_EMPTY(&lock->lf_inedges),
363 ("freeing lock with dependants"));
364 sx_xlock(&lf_lock_owners_lock);
365 KASSERT(lo->lo_refs > 0, ("lock owner refcount"));
366 lo->lo_refs--;
367 if (lo->lo_refs == 0) {
368 #ifdef LOCKF_DEBUG
369 if (lockf_debug & 1)
370 printf("lf_free_lock: freeing lock owner %p\n",
371 lo);
372 #endif
373 if (lo->lo_vertex) {
374 sx_xlock(&lf_owner_graph_lock);
375 graph_free_vertex(&lf_owner_graph,
376 lo->lo_vertex);
377 sx_xunlock(&lf_owner_graph_lock);
378 }
379 LIST_REMOVE(lo, lo_link);
380 free(lo, M_LOCKF);
381 #ifdef LOCKF_DEBUG
382 if (lockf_debug & 4)
383 printf("Freed lock owner %p\n", lo);
384 #endif
385 }
386 sx_unlock(&lf_lock_owners_lock);
387 }
388 if ((lock->lf_flags & F_REMOTE) && lock->lf_vnode) {
389 vrele(lock->lf_vnode);
390 lock->lf_vnode = NULL;
391 }
392 #ifdef LOCKF_DEBUG
393 if (lockf_debug & 4)
394 printf("Freed lock %p\n", lock);
395 #endif
396 free(lock, M_LOCKF);
397 }
398
399 /*
400 * Advisory record locking support
401 */
402 int
403 lf_advlockasync(struct vop_advlockasync_args *ap, struct lockf **statep,
404 u_quad_t size)
405 {
406 struct lockf *state, *freestate = NULL;
407 struct flock *fl = ap->a_fl;
408 struct lockf_entry *lock;
409 struct vnode *vp = ap->a_vp;
410 caddr_t id = ap->a_id;
411 int flags = ap->a_flags;
412 int hash;
413 struct lock_owner *lo;
414 off_t start, end, oadd;
415 int error;
416
417 /*
418 * Handle the F_UNLKSYS case first - no need to mess about
419 * creating a lock owner for this one.
420 */
421 if (ap->a_op == F_UNLCKSYS) {
422 lf_clearremotesys(fl->l_sysid);
423 return (0);
424 }
425
426 /*
427 * Convert the flock structure into a start and end.
428 */
429 switch (fl->l_whence) {
430
431 case SEEK_SET:
432 case SEEK_CUR:
433 /*
434 * Caller is responsible for adding any necessary offset
435 * when SEEK_CUR is used.
436 */
437 start = fl->l_start;
438 break;
439
440 case SEEK_END:
441 if (size > OFF_MAX ||
442 (fl->l_start > 0 && size > OFF_MAX - fl->l_start))
443 return (EOVERFLOW);
444 start = size + fl->l_start;
445 break;
446
447 default:
448 return (EINVAL);
449 }
450 if (start < 0)
451 return (EINVAL);
452 if (fl->l_len < 0) {
453 if (start == 0)
454 return (EINVAL);
455 end = start - 1;
456 start += fl->l_len;
457 if (start < 0)
458 return (EINVAL);
459 } else if (fl->l_len == 0) {
460 end = OFF_MAX;
461 } else {
462 oadd = fl->l_len - 1;
463 if (oadd > OFF_MAX - start)
464 return (EOVERFLOW);
465 end = start + oadd;
466 }
467 /*
468 * Avoid the common case of unlocking when inode has no locks.
469 */
470 if ((*statep) == NULL || LIST_EMPTY(&(*statep)->ls_active)) {
471 if (ap->a_op != F_SETLK) {
472 fl->l_type = F_UNLCK;
473 return (0);
474 }
475 }
476
477 /*
478 * Map our arguments to an existing lock owner or create one
479 * if this is the first time we have seen this owner.
480 */
481 hash = lf_hash_owner(id, fl, flags);
482 sx_xlock(&lf_lock_owners_lock);
483 LIST_FOREACH(lo, &lf_lock_owners[hash], lo_link)
484 if (lf_owner_matches(lo, id, fl, flags))
485 break;
486 if (!lo) {
487 /*
488 * We initialise the lock with a reference
489 * count which matches the new lockf_entry
490 * structure created below.
491 */
492 lo = malloc(sizeof(struct lock_owner), M_LOCKF,
493 M_WAITOK|M_ZERO);
494 #ifdef LOCKF_DEBUG
495 if (lockf_debug & 4)
496 printf("Allocated lock owner %p\n", lo);
497 #endif
498
499 lo->lo_refs = 1;
500 lo->lo_flags = flags;
501 lo->lo_id = id;
502 if (flags & F_REMOTE) {
503 lo->lo_pid = fl->l_pid;
504 lo->lo_sysid = fl->l_sysid;
505 } else if (flags & F_FLOCK) {
506 lo->lo_pid = -1;
507 lo->lo_sysid = 0;
508 } else {
509 struct proc *p = (struct proc *) id;
510 lo->lo_pid = p->p_pid;
511 lo->lo_sysid = 0;
512 }
513 lo->lo_vertex = NULL;
514
515 #ifdef LOCKF_DEBUG
516 if (lockf_debug & 1) {
517 printf("lf_advlockasync: new lock owner %p ", lo);
518 lf_print_owner(lo);
519 printf("\n");
520 }
521 #endif
522
523 LIST_INSERT_HEAD(&lf_lock_owners[hash], lo, lo_link);
524 } else {
525 /*
526 * We have seen this lock owner before, increase its
527 * reference count to account for the new lockf_entry
528 * structure we create below.
529 */
530 lo->lo_refs++;
531 }
532 sx_xunlock(&lf_lock_owners_lock);
533
534 /*
535 * Create the lockf structure. We initialise the lf_owner
536 * field here instead of in lf_alloc_lock() to avoid paying
537 * the lf_lock_owners_lock tax twice.
538 */
539 lock = lf_alloc_lock(NULL);
540 lock->lf_start = start;
541 lock->lf_end = end;
542 lock->lf_owner = lo;
543 lock->lf_vnode = vp;
544 if (flags & F_REMOTE) {
545 /*
546 * For remote locks, the caller may release its ref to
547 * the vnode at any time - we have to ref it here to
548 * prevent it from being recycled unexpectedly.
549 */
550 vref(vp);
551 }
552
553 /*
554 * XXX The problem is that VTOI is ufs specific, so it will
555 * break LOCKF_DEBUG for all other FS's other than UFS because
556 * it casts the vnode->data ptr to struct inode *.
557 */
558 /* lock->lf_inode = VTOI(ap->a_vp); */
559 lock->lf_inode = (struct inode *)0;
560 lock->lf_type = fl->l_type;
561 LIST_INIT(&lock->lf_outedges);
562 LIST_INIT(&lock->lf_inedges);
563 lock->lf_async_task = ap->a_task;
564 lock->lf_flags = ap->a_flags;
565
566 /*
567 * Do the requested operation. First find our state structure
568 * and create a new one if necessary - the caller's *statep
569 * variable and the state's ls_threads count is protected by
570 * the vnode interlock.
571 */
572 VI_LOCK(vp);
573 if (vp->v_iflag & VI_DOOMED) {
574 VI_UNLOCK(vp);
575 lf_free_lock(lock);
576 return (ENOENT);
577 }
578
579 /*
580 * Allocate a state structure if necessary.
581 */
582 state = *statep;
583 if (state == NULL) {
584 struct lockf *ls;
585
586 VI_UNLOCK(vp);
587
588 ls = malloc(sizeof(struct lockf), M_LOCKF, M_WAITOK|M_ZERO);
589 sx_init(&ls->ls_lock, "ls_lock");
590 LIST_INIT(&ls->ls_active);
591 LIST_INIT(&ls->ls_pending);
592 ls->ls_threads = 1;
593
594 sx_xlock(&lf_lock_states_lock);
595 LIST_INSERT_HEAD(&lf_lock_states, ls, ls_link);
596 sx_xunlock(&lf_lock_states_lock);
597
598 /*
599 * Cope if we lost a race with some other thread while
600 * trying to allocate memory.
601 */
602 VI_LOCK(vp);
603 if (vp->v_iflag & VI_DOOMED) {
604 VI_UNLOCK(vp);
605 sx_xlock(&lf_lock_states_lock);
606 LIST_REMOVE(ls, ls_link);
607 sx_xunlock(&lf_lock_states_lock);
608 sx_destroy(&ls->ls_lock);
609 free(ls, M_LOCKF);
610 lf_free_lock(lock);
611 return (ENOENT);
612 }
613 if ((*statep) == NULL) {
614 state = *statep = ls;
615 VI_UNLOCK(vp);
616 } else {
617 state = *statep;
618 state->ls_threads++;
619 VI_UNLOCK(vp);
620
621 sx_xlock(&lf_lock_states_lock);
622 LIST_REMOVE(ls, ls_link);
623 sx_xunlock(&lf_lock_states_lock);
624 sx_destroy(&ls->ls_lock);
625 free(ls, M_LOCKF);
626 }
627 } else {
628 state->ls_threads++;
629 VI_UNLOCK(vp);
630 }
631
632 sx_xlock(&state->ls_lock);
633 switch(ap->a_op) {
634 case F_SETLK:
635 error = lf_setlock(state, lock, vp, ap->a_cookiep);
636 break;
637
638 case F_UNLCK:
639 error = lf_clearlock(state, lock);
640 lf_free_lock(lock);
641 break;
642
643 case F_GETLK:
644 error = lf_getlock(state, lock, fl);
645 lf_free_lock(lock);
646 break;
647
648 case F_CANCEL:
649 if (ap->a_cookiep)
650 error = lf_cancel(state, lock, *ap->a_cookiep);
651 else
652 error = EINVAL;
653 lf_free_lock(lock);
654 break;
655
656 default:
657 lf_free_lock(lock);
658 error = EINVAL;
659 break;
660 }
661
662 #ifdef INVARIANTS
663 /*
664 * Check for some can't happen stuff. In this case, the active
665 * lock list becoming disordered or containing mutually
666 * blocking locks. We also check the pending list for locks
667 * which should be active (i.e. have no out-going edges).
668 */
669 LIST_FOREACH(lock, &state->ls_active, lf_link) {
670 struct lockf_entry *lf;
671 if (LIST_NEXT(lock, lf_link))
672 KASSERT((lock->lf_start
673 <= LIST_NEXT(lock, lf_link)->lf_start),
674 ("locks disordered"));
675 LIST_FOREACH(lf, &state->ls_active, lf_link) {
676 if (lock == lf)
677 break;
678 KASSERT(!lf_blocks(lock, lf),
679 ("two conflicting active locks"));
680 if (lock->lf_owner == lf->lf_owner)
681 KASSERT(!lf_overlaps(lock, lf),
682 ("two overlapping locks from same owner"));
683 }
684 }
685 LIST_FOREACH(lock, &state->ls_pending, lf_link) {
686 KASSERT(!LIST_EMPTY(&lock->lf_outedges),
687 ("pending lock which should be active"));
688 }
689 #endif
690 sx_xunlock(&state->ls_lock);
691
692 /*
693 * If we have removed the last active lock on the vnode and
694 * this is the last thread that was in-progress, we can free
695 * the state structure. We update the caller's pointer inside
696 * the vnode interlock but call free outside.
697 *
698 * XXX alternatively, keep the state structure around until
699 * the filesystem recycles - requires a callback from the
700 * filesystem.
701 */
702 VI_LOCK(vp);
703
704 state->ls_threads--;
705 wakeup(state);
706 if (LIST_EMPTY(&state->ls_active) && state->ls_threads == 0) {
707 KASSERT(LIST_EMPTY(&state->ls_pending),
708 ("freeing state with pending locks"));
709 freestate = state;
710 *statep = NULL;
711 }
712
713 VI_UNLOCK(vp);
714
715 if (freestate) {
716 sx_xlock(&lf_lock_states_lock);
717 LIST_REMOVE(freestate, ls_link);
718 sx_xunlock(&lf_lock_states_lock);
719 sx_destroy(&freestate->ls_lock);
720 free(freestate, M_LOCKF);
721 }
722 return (error);
723 }
724
725 int
726 lf_advlock(struct vop_advlock_args *ap, struct lockf **statep, u_quad_t size)
727 {
728 struct vop_advlockasync_args a;
729
730 a.a_vp = ap->a_vp;
731 a.a_id = ap->a_id;
732 a.a_op = ap->a_op;
733 a.a_fl = ap->a_fl;
734 a.a_flags = ap->a_flags;
735 a.a_task = NULL;
736 a.a_cookiep = NULL;
737
738 return (lf_advlockasync(&a, statep, size));
739 }
740
741 void
742 lf_purgelocks(struct vnode *vp, struct lockf **statep)
743 {
744 struct lockf *state;
745 struct lockf_entry *lock, *nlock;
746
747 /*
748 * For this to work correctly, the caller must ensure that no
749 * other threads enter the locking system for this vnode,
750 * e.g. by checking VI_DOOMED. We wake up any threads that are
751 * sleeping waiting for locks on this vnode and then free all
752 * the remaining locks.
753 */
754 VI_LOCK(vp);
755 state = *statep;
756 if (state) {
757 state->ls_threads++;
758 VI_UNLOCK(vp);
759
760 sx_xlock(&state->ls_lock);
761 sx_xlock(&lf_owner_graph_lock);
762 LIST_FOREACH_SAFE(lock, &state->ls_pending, lf_link, nlock) {
763 LIST_REMOVE(lock, lf_link);
764 lf_remove_outgoing(lock);
765 lf_remove_incoming(lock);
766
767 /*
768 * If its an async lock, we can just free it
769 * here, otherwise we let the sleeping thread
770 * free it.
771 */
772 if (lock->lf_async_task) {
773 lf_free_lock(lock);
774 } else {
775 lock->lf_flags |= F_INTR;
776 wakeup(lock);
777 }
778 }
779 sx_xunlock(&lf_owner_graph_lock);
780 sx_xunlock(&state->ls_lock);
781
782 /*
783 * Wait for all other threads, sleeping and otherwise
784 * to leave.
785 */
786 VI_LOCK(vp);
787 while (state->ls_threads > 1)
788 msleep(state, VI_MTX(vp), 0, "purgelocks", 0);
789 *statep = 0;
790 VI_UNLOCK(vp);
791
792 /*
793 * We can just free all the active locks since they
794 * will have no dependancies (we removed them all
795 * above). We don't need to bother locking since we
796 * are the last thread using this state structure.
797 */
798 LIST_FOREACH_SAFE(lock, &state->ls_pending, lf_link, nlock) {
799 LIST_REMOVE(lock, lf_link);
800 lf_free_lock(lock);
801 }
802 sx_xlock(&lf_lock_states_lock);
803 LIST_REMOVE(state, ls_link);
804 sx_xunlock(&lf_lock_states_lock);
805 sx_destroy(&state->ls_lock);
806 free(state, M_LOCKF);
807 } else {
808 VI_UNLOCK(vp);
809 }
810 }
811
812 /*
813 * Return non-zero if locks 'x' and 'y' overlap.
814 */
815 static int
816 lf_overlaps(struct lockf_entry *x, struct lockf_entry *y)
817 {
818
819 return (x->lf_start <= y->lf_end && x->lf_end >= y->lf_start);
820 }
821
822 /*
823 * Return non-zero if lock 'x' is blocked by lock 'y' (or vice versa).
824 */
825 static int
826 lf_blocks(struct lockf_entry *x, struct lockf_entry *y)
827 {
828
829 return x->lf_owner != y->lf_owner
830 && (x->lf_type == F_WRLCK || y->lf_type == F_WRLCK)
831 && lf_overlaps(x, y);
832 }
833
834 /*
835 * Allocate a lock edge from the free list
836 */
837 static struct lockf_edge *
838 lf_alloc_edge(void)
839 {
840
841 return (malloc(sizeof(struct lockf_edge), M_LOCKF, M_WAITOK|M_ZERO));
842 }
843
844 /*
845 * Free a lock edge.
846 */
847 static void
848 lf_free_edge(struct lockf_edge *e)
849 {
850
851 free(e, M_LOCKF);
852 }
853
854
855 /*
856 * Ensure that the lock's owner has a corresponding vertex in the
857 * owner graph.
858 */
859 static void
860 lf_alloc_vertex(struct lockf_entry *lock)
861 {
862 struct owner_graph *g = &lf_owner_graph;
863
864 if (!lock->lf_owner->lo_vertex)
865 lock->lf_owner->lo_vertex =
866 graph_alloc_vertex(g, lock->lf_owner);
867 }
868
869 /*
870 * Attempt to record an edge from lock x to lock y. Return EDEADLK if
871 * the new edge would cause a cycle in the owner graph.
872 */
873 static int
874 lf_add_edge(struct lockf_entry *x, struct lockf_entry *y)
875 {
876 struct owner_graph *g = &lf_owner_graph;
877 struct lockf_edge *e;
878 int error;
879
880 #ifdef INVARIANTS
881 LIST_FOREACH(e, &x->lf_outedges, le_outlink)
882 KASSERT(e->le_to != y, ("adding lock edge twice"));
883 #endif
884
885 /*
886 * Make sure the two owners have entries in the owner graph.
887 */
888 lf_alloc_vertex(x);
889 lf_alloc_vertex(y);
890
891 error = graph_add_edge(g, x->lf_owner->lo_vertex,
892 y->lf_owner->lo_vertex);
893 if (error)
894 return (error);
895
896 e = lf_alloc_edge();
897 LIST_INSERT_HEAD(&x->lf_outedges, e, le_outlink);
898 LIST_INSERT_HEAD(&y->lf_inedges, e, le_inlink);
899 e->le_from = x;
900 e->le_to = y;
901
902 return (0);
903 }
904
905 /*
906 * Remove an edge from the lock graph.
907 */
908 static void
909 lf_remove_edge(struct lockf_edge *e)
910 {
911 struct owner_graph *g = &lf_owner_graph;
912 struct lockf_entry *x = e->le_from;
913 struct lockf_entry *y = e->le_to;
914
915 graph_remove_edge(g, x->lf_owner->lo_vertex, y->lf_owner->lo_vertex);
916 LIST_REMOVE(e, le_outlink);
917 LIST_REMOVE(e, le_inlink);
918 e->le_from = NULL;
919 e->le_to = NULL;
920 lf_free_edge(e);
921 }
922
923 /*
924 * Remove all out-going edges from lock x.
925 */
926 static void
927 lf_remove_outgoing(struct lockf_entry *x)
928 {
929 struct lockf_edge *e;
930
931 while ((e = LIST_FIRST(&x->lf_outedges)) != NULL) {
932 lf_remove_edge(e);
933 }
934 }
935
936 /*
937 * Remove all in-coming edges from lock x.
938 */
939 static void
940 lf_remove_incoming(struct lockf_entry *x)
941 {
942 struct lockf_edge *e;
943
944 while ((e = LIST_FIRST(&x->lf_inedges)) != NULL) {
945 lf_remove_edge(e);
946 }
947 }
948
949 /*
950 * Walk the list of locks for the file and create an out-going edge
951 * from lock to each blocking lock.
952 */
953 static int
954 lf_add_outgoing(struct lockf *state, struct lockf_entry *lock)
955 {
956 struct lockf_entry *overlap;
957 int error;
958
959 LIST_FOREACH(overlap, &state->ls_active, lf_link) {
960 /*
961 * We may assume that the active list is sorted by
962 * lf_start.
963 */
964 if (overlap->lf_start > lock->lf_end)
965 break;
966 if (!lf_blocks(lock, overlap))
967 continue;
968
969 /*
970 * We've found a blocking lock. Add the corresponding
971 * edge to the graphs and see if it would cause a
972 * deadlock.
973 */
974 error = lf_add_edge(lock, overlap);
975
976 /*
977 * The only error that lf_add_edge returns is EDEADLK.
978 * Remove any edges we added and return the error.
979 */
980 if (error) {
981 lf_remove_outgoing(lock);
982 return (error);
983 }
984 }
985
986 /*
987 * We also need to add edges to sleeping locks that block
988 * us. This ensures that lf_wakeup_lock cannot grant two
989 * mutually blocking locks simultaneously and also enforces a
990 * 'first come, first served' fairness model. Note that this
991 * only happens if we are blocked by at least one active lock
992 * due to the call to lf_getblock in lf_setlock below.
993 */
994 LIST_FOREACH(overlap, &state->ls_pending, lf_link) {
995 if (!lf_blocks(lock, overlap))
996 continue;
997 /*
998 * We've found a blocking lock. Add the corresponding
999 |