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$");
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 static 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 int 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 int
351 lf_free_lock(struct lockf_entry *lock)
352 {
353
354 KASSERT(lock->lf_refs > 0, ("lockf_entry negative ref count %p", lock));
355 if (--lock->lf_refs > 0)
356 return (0);
357 /*
358 * Adjust the lock_owner reference count and
359 * reclaim the entry if this is the last lock
360 * for that owner.
361 */
362 struct lock_owner *lo = lock->lf_owner;
363 if (lo) {
364 KASSERT(LIST_EMPTY(&lock->lf_outedges),
365 ("freeing lock with dependancies"));
366 KASSERT(LIST_EMPTY(&lock->lf_inedges),
367 ("freeing lock with dependants"));
368 sx_xlock(&lf_lock_owners_lock);
369 KASSERT(lo->lo_refs > 0, ("lock owner refcount"));
370 lo->lo_refs--;
371 if (lo->lo_refs == 0) {
372 #ifdef LOCKF_DEBUG
373 if (lockf_debug & 1)
374 printf("lf_free_lock: freeing lock owner %p\n",
375 lo);
376 #endif
377 if (lo->lo_vertex) {
378 sx_xlock(&lf_owner_graph_lock);
379 graph_free_vertex(&lf_owner_graph,
380 lo->lo_vertex);
381 sx_xunlock(&lf_owner_graph_lock);
382 }
383 LIST_REMOVE(lo, lo_link);
384 free(lo, M_LOCKF);
385 #ifdef LOCKF_DEBUG
386 if (lockf_debug & 4)
387 printf("Freed lock owner %p\n", lo);
388 #endif
389 }
390 sx_unlock(&lf_lock_owners_lock);
391 }
392 if ((lock->lf_flags & F_REMOTE) && lock->lf_vnode) {
393 vrele(lock->lf_vnode);
394 lock->lf_vnode = NULL;
395 }
396 #ifdef LOCKF_DEBUG
397 if (lockf_debug & 4)
398 printf("Freed lock %p\n", lock);
399 #endif
400 free(lock, M_LOCKF);
401 return (1);
402 }
403
404 /*
405 * Advisory record locking support
406 */
407 int
408 lf_advlockasync(struct vop_advlockasync_args *ap, struct lockf **statep,
409 u_quad_t size)
410 {
411 struct lockf *state, *freestate = NULL;
412 struct flock *fl = ap->a_fl;
413 struct lockf_entry *lock;
414 struct vnode *vp = ap->a_vp;
415 caddr_t id = ap->a_id;
416 int flags = ap->a_flags;
417 int hash;
418 struct lock_owner *lo;
419 off_t start, end, oadd;
420 int error;
421
422 /*
423 * Handle the F_UNLKSYS case first - no need to mess about
424 * creating a lock owner for this one.
425 */
426 if (ap->a_op == F_UNLCKSYS) {
427 lf_clearremotesys(fl->l_sysid);
428 return (0);
429 }
430
431 /*
432 * Convert the flock structure into a start and end.
433 */
434 switch (fl->l_whence) {
435
436 case SEEK_SET:
437 case SEEK_CUR:
438 /*
439 * Caller is responsible for adding any necessary offset
440 * when SEEK_CUR is used.
441 */
442 start = fl->l_start;
443 break;
444
445 case SEEK_END:
446 if (size > OFF_MAX ||
447 (fl->l_start > 0 && size > OFF_MAX - fl->l_start))
448 return (EOVERFLOW);
449 start = size + fl->l_start;
450 break;
451
452 default:
453 return (EINVAL);
454 }
455 if (start < 0)
456 return (EINVAL);
457 if (fl->l_len < 0) {
458 if (start == 0)
459 return (EINVAL);
460 end = start - 1;
461 start += fl->l_len;
462 if (start < 0)
463 return (EINVAL);
464 } else if (fl->l_len == 0) {
465 end = OFF_MAX;
466 } else {
467 oadd = fl->l_len - 1;
468 if (oadd > OFF_MAX - start)
469 return (EOVERFLOW);
470 end = start + oadd;
471 }
472
473 retry_setlock:
474
475 /*
476 * Avoid the common case of unlocking when inode has no locks.
477 */
478 VI_LOCK(vp);
479 if ((*statep) == NULL) {
480 if (ap->a_op != F_SETLK) {
481 fl->l_type = F_UNLCK;
482 VI_UNLOCK(vp);
483 return (0);
484 }
485 }
486 VI_UNLOCK(vp);
487
488 /*
489 * Map our arguments to an existing lock owner or create one
490 * if this is the first time we have seen this owner.
491 */
492 hash = lf_hash_owner(id, fl, flags);
493 sx_xlock(&lf_lock_owners_lock);
494 LIST_FOREACH(lo, &lf_lock_owners[hash], lo_link)
495 if (lf_owner_matches(lo, id, fl, flags))
496 break;
497 if (!lo) {
498 /*
499 * We initialise the lock with a reference
500 * count which matches the new lockf_entry
501 * structure created below.
502 */
503 lo = malloc(sizeof(struct lock_owner), M_LOCKF,
504 M_WAITOK|M_ZERO);
505 #ifdef LOCKF_DEBUG
506 if (lockf_debug & 4)
507 printf("Allocated lock owner %p\n", lo);
508 #endif
509
510 lo->lo_refs = 1;
511 lo->lo_flags = flags;
512 lo->lo_id = id;
513 if (flags & F_REMOTE) {
514 lo->lo_pid = fl->l_pid;
515 lo->lo_sysid = fl->l_sysid;
516 } else if (flags & F_FLOCK) {
517 lo->lo_pid = -1;
518 lo->lo_sysid = 0;
519 } else {
520 struct proc *p = (struct proc *) id;
521 lo->lo_pid = p->p_pid;
522 lo->lo_sysid = 0;
523 }
524 lo->lo_vertex = NULL;
525
526 #ifdef LOCKF_DEBUG
527 if (lockf_debug & 1) {
528 printf("lf_advlockasync: new lock owner %p ", lo);
529 lf_print_owner(lo);
530 printf("\n");
531 }
532 #endif
533
534 LIST_INSERT_HEAD(&lf_lock_owners[hash], lo, lo_link);
535 } else {
536 /*
537 * We have seen this lock owner before, increase its
538 * reference count to account for the new lockf_entry
539 * structure we create below.
540 */
541 lo->lo_refs++;
542 }
543 sx_xunlock(&lf_lock_owners_lock);
544
545 /*
546 * Create the lockf structure. We initialise the lf_owner
547 * field here instead of in lf_alloc_lock() to avoid paying
548 * the lf_lock_owners_lock tax twice.
549 */
550 lock = lf_alloc_lock(NULL);
551 lock->lf_refs = 1;
552 lock->lf_start = start;
553 lock->lf_end = end;
554 lock->lf_owner = lo;
555 lock->lf_vnode = vp;
556 if (flags & F_REMOTE) {
557 /*
558 * For remote locks, the caller may release its ref to
559 * the vnode at any time - we have to ref it here to
560 * prevent it from being recycled unexpectedly.
561 */
562 vref(vp);
563 }
564
565 /*
566 * XXX The problem is that VTOI is ufs specific, so it will
567 * break LOCKF_DEBUG for all other FS's other than UFS because
568 * it casts the vnode->data ptr to struct inode *.
569 */
570 /* lock->lf_inode = VTOI(ap->a_vp); */
571 lock->lf_inode = (struct inode *)0;
572 lock->lf_type = fl->l_type;
573 LIST_INIT(&lock->lf_outedges);
574 LIST_INIT(&lock->lf_inedges);
575 lock->lf_async_task = ap->a_task;
576 lock->lf_flags = ap->a_flags;
577
578 /*
579 * Do the requested operation. First find our state structure
580 * and create a new one if necessary - the caller's *statep
581 * variable and the state's ls_threads count is protected by
582 * the vnode interlock.
583 */
584 VI_LOCK(vp);
585 if (vp->v_iflag & VI_DOOMED) {
586 VI_UNLOCK(vp);
587 lf_free_lock(lock);
588 return (ENOENT);
589 }
590
591 /*
592 * Allocate a state structure if necessary.
593 */
594 state = *statep;
595 if (state == NULL) {
596 struct lockf *ls;
597
598 VI_UNLOCK(vp);
599
600 ls = malloc(sizeof(struct lockf), M_LOCKF, M_WAITOK|M_ZERO);
601 sx_init(&ls->ls_lock, "ls_lock");
602 LIST_INIT(&ls->ls_active);
603 LIST_INIT(&ls->ls_pending);
604 ls->ls_threads = 1;
605
606 sx_xlock(&lf_lock_states_lock);
607 LIST_INSERT_HEAD(&lf_lock_states, ls, ls_link);
608 sx_xunlock(&lf_lock_states_lock);
609
610 /*
611 * Cope if we lost a race with some other thread while
612 * trying to allocate memory.
613 */
614 VI_LOCK(vp);
615 if (vp->v_iflag & VI_DOOMED) {
616 VI_UNLOCK(vp);
617 sx_xlock(&lf_lock_states_lock);
618 LIST_REMOVE(ls, ls_link);
619 sx_xunlock(&lf_lock_states_lock);
620 sx_destroy(&ls->ls_lock);
621 free(ls, M_LOCKF);
622 lf_free_lock(lock);
623 return (ENOENT);
624 }
625 if ((*statep) == NULL) {
626 state = *statep = ls;
627 VI_UNLOCK(vp);
628 } else {
629 state = *statep;
630 state->ls_threads++;
631 VI_UNLOCK(vp);
632
633 sx_xlock(&lf_lock_states_lock);
634 LIST_REMOVE(ls, ls_link);
635 sx_xunlock(&lf_lock_states_lock);
636 sx_destroy(&ls->ls_lock);
637 free(ls, M_LOCKF);
638 }
639 } else {
640 state->ls_threads++;
641 VI_UNLOCK(vp);
642 }
643
644 sx_xlock(&state->ls_lock);
645 /*
646 * Recheck the doomed vnode after state->ls_lock is
647 * locked. lf_purgelocks() requires that no new threads add
648 * pending locks when vnode is marked by VI_DOOMED flag.
649 */
650 VI_LOCK(vp);
651 if (vp->v_iflag & VI_DOOMED) {
652 state->ls_threads--;
653 wakeup(state);
654 VI_UNLOCK(vp);
655 sx_xunlock(&state->ls_lock);
656 lf_free_lock(lock);
657 return (ENOENT);
658 }
659 VI_UNLOCK(vp);
660
661 switch (ap->a_op) {
662 case F_SETLK:
663 error = lf_setlock(state, lock, vp, ap->a_cookiep);
664 break;
665
666 case F_UNLCK:
667 error = lf_clearlock(state, lock);
668 lf_free_lock(lock);
669 break;
670
671 case F_GETLK:
672 error = lf_getlock(state, lock, fl);
673 lf_free_lock(lock);
674 break;
675
676 case F_CANCEL:
677 if (ap->a_cookiep)
678 error = lf_cancel(state, lock, *ap->a_cookiep);
679 else
680 error = EINVAL;
681 lf_free_lock(lock);
682 break;
683
684 default:
685 lf_free_lock(lock);
686 error = EINVAL;
687 break;
688 }
689
690 #ifdef INVARIANTS
691 /*
692 * Check for some can't happen stuff. In this case, the active
693 * lock list becoming disordered or containing mutually
694 * blocking locks. We also check the pending list for locks
695 * which should be active (i.e. have no out-going edges).
696 */
697 LIST_FOREACH(lock, &state->ls_active, lf_link) {
698 struct lockf_entry *lf;
699 if (LIST_NEXT(lock, lf_link))
700 KASSERT((lock->lf_start
701 <= LIST_NEXT(lock, lf_link)->lf_start),
702 ("locks disordered"));
703 LIST_FOREACH(lf, &state->ls_active, lf_link) {
704 if (lock == lf)
705 break;
706 KASSERT(!lf_blocks(lock, lf),
707 ("two conflicting active locks"));
708 if (lock->lf_owner == lf->lf_owner)
709 KASSERT(!lf_overlaps(lock, lf),
710 ("two overlapping locks from same owner"));
711 }
712 }
713 LIST_FOREACH(lock, &state->ls_pending, lf_link) {
714 KASSERT(!LIST_EMPTY(&lock->lf_outedges),
715 ("pending lock which should be active"));
716 }
717 #endif
718 sx_xunlock(&state->ls_lock);
719
720 /*
721 * If we have removed the last active lock on the vnode and
722 * this is the last thread that was in-progress, we can free
723 * the state structure. We update the caller's pointer inside
724 * the vnode interlock but call free outside.
725 *
726 * XXX alternatively, keep the state structure around until
727 * the filesystem recycles - requires a callback from the
728 * filesystem.
729 */
730 VI_LOCK(vp);
731
732 state->ls_threads--;
733 wakeup(state);
734 if (LIST_EMPTY(&state->ls_active) && state->ls_threads == 0) {
735 KASSERT(LIST_EMPTY(&state->ls_pending),
736 ("freeing state with pending locks"));
737 freestate = state;
738 *statep = NULL;
739 }
740
741 VI_UNLOCK(vp);
742
743 if (freestate) {
744 sx_xlock(&lf_lock_states_lock);
745 LIST_REMOVE(freestate, ls_link);
746 sx_xunlock(&lf_lock_states_lock);
747 sx_destroy(&freestate->ls_lock);
748 free(freestate, M_LOCKF);
749 }
750
751 if (error == EDOOFUS) {
752 KASSERT(ap->a_op == F_SETLK, ("EDOOFUS"));
753 goto retry_setlock;
754 }
755 return (error);
756 }
757
758 int
759 lf_advlock(struct vop_advlock_args *ap, struct lockf **statep, u_quad_t size)
760 {
761 struct vop_advlockasync_args a;
762
763 a.a_vp = ap->a_vp;
764 a.a_id = ap->a_id;
765 a.a_op = ap->a_op;
766 a.a_fl = ap->a_fl;
767 a.a_flags = ap->a_flags;
768 a.a_task = NULL;
769 a.a_cookiep = NULL;
770
771 return (lf_advlockasync(&a, statep, size));
772 }
773
774 void
775 lf_purgelocks(struct vnode *vp, struct lockf **statep)
776 {
777 struct lockf *state;
778 struct lockf_entry *lock, *nlock;
779
780 /*
781 * For this to work correctly, the caller must ensure that no
782 * other threads enter the locking system for this vnode,
783 * e.g. by checking VI_DOOMED. We wake up any threads that are
784 * sleeping waiting for locks on this vnode and then free all
785 * the remaining locks.
786 */
787 VI_LOCK(vp);
788 KASSERT(vp->v_iflag & VI_DOOMED,
789 ("lf_purgelocks: vp %p has not vgone yet", vp));
790 state = *statep;
791 if (state) {
792 *statep = NULL;
793 state->ls_threads++;
794 VI_UNLOCK(vp);
795
796 sx_xlock(&state->ls_lock);
797 sx_xlock(&lf_owner_graph_lock);
798 LIST_FOREACH_SAFE(lock, &state->ls_pending, lf_link, nlock) {
799 LIST_REMOVE(lock, lf_link);
800 lf_remove_outgoing(lock);
801 lf_remove_incoming(lock);
802
803 /*
804 * If its an async lock, we can just free it
805 * here, otherwise we let the sleeping thread
806 * free it.
807 */
808 if (lock->lf_async_task) {
809 lf_free_lock(lock);
810 } else {
811 lock->lf_flags |= F_INTR;
812 wakeup(lock);
813 }
814 }
815 sx_xunlock(&lf_owner_graph_lock);
816 sx_xunlock(&state->ls_lock);
817
818 /*
819 * Wait for all other threads, sleeping and otherwise
820 * to leave.
821 */
822 VI_LOCK(vp);
823 while (state->ls_threads > 1)
824 msleep(state, VI_MTX(vp), 0, "purgelocks", 0);
825 VI_UNLOCK(vp);
826
827 /*
828 * We can just free all the active locks since they
829 * will have no dependancies (we removed them all
830 * above). We don't need to bother locking since we
831 * are the last thread using this state structure.
832 */
833 KASSERT(LIST_EMPTY(&state->ls_pending),
834 ("lock pending for %p", state));
835 LIST_FOREACH_SAFE(lock, &state->ls_active, lf_link, nlock) {
836 LIST_REMOVE(lock, lf_link);
837 lf_free_lock(lock);
838 }
839 sx_xlock(&lf_lock_states_lock);
840 LIST_REMOVE(state, ls_link);
841 sx_xunlock(&lf_lock_states_lock);
842 sx_destroy(&state->ls_lock);
843 free(state, M_LOCKF);
844 } else {
845 VI_UNLOCK(vp);
846 }
847 }
848
849 /*
850 * Return non-zero if locks 'x' and 'y' overlap.
851 */
852 static int
853 lf_overlaps(struct lockf_entry *x, struct lockf_entry *y)
854 {
855
856 return (x->lf_start <= y->lf_end && x->lf_end >= y->lf_start);
857 }
858
859 /*
860 * Return non-zero if lock 'x' is blocked by lock 'y' (or vice versa).
861 */
862 static int
863 lf_blocks(struct lockf_entry *x, struct lockf_entry *y)
864 {
865
866 return x->lf_owner != y->lf_owner
867 && (x->lf_type == F_WRLCK || y->lf_type == F_WRLCK)
868 && lf_overlaps(x, y);
869 }
870
871 /*
872 * Allocate a lock edge from the free list
873 */
874 static struct lockf_edge *
875 lf_alloc_edge(void)
876 {
877
878 return (malloc(sizeof(struct lockf_edge), M_LOCKF, M_WAITOK|M_ZERO));
879 }
880
881 /*
882 * Free a lock edge.
883 */
884 static void
885 lf_free_edge(struct lockf_edge *e)
886 {
887
888 free(e, M_LOCKF);
889 }
890
891
892 /*
893 * Ensure that the lock's owner has a corresponding vertex in the
894 * owner graph.
895 */
896 static void
897 lf_alloc_vertex(struct lockf_entry *lock)
898 {
899 struct owner_graph *g = &lf_owner_graph;
900
901 if (!lock->lf_owner->lo_vertex)
902 lock->lf_owner->lo_vertex =
903 graph_alloc_vertex(g, lock->lf_owner);
904 }
905
906 /*
907 * Attempt to record an edge from lock x to lock y. Return EDEADLK if
908 * the new edge would cause a cycle in the owner graph.
909 */
910 static int
911 lf_add_edge(struct lockf_entry *x, struct lockf_entry *y)
912 {
913 struct owner_graph *g = &lf_owner_graph;
914 struct lockf_edge *e;
915 int error;
916
917 #ifdef INVARIANTS
918 LIST_FOREACH(e, &x->lf_outedges, le_outlink)
919 KASSERT(e->le_to != y, ("adding lock edge twice"));
920 #endif
921
922 /*
923 * Make sure the two owners have entries in the owner graph.
924 */
925 lf_alloc_vertex(x);
926 lf_alloc_vertex(y);
927
928 error = graph_add_edge(g, x->lf_owner->lo_vertex,
929 y->lf_owner->lo_vertex);
930 if (error)
931 return (error);
932
933 e = lf_alloc_edge();
934 LIST_INSERT_HEAD(&x->lf_outedges, e, le_outlink);
935 LIST_INSERT_HEAD(&y->lf_inedges, e, le_inlink);
936 e->le_from = x;
937 e->le_to = y;
938
939 return (0);
940 }
941
942 /*
943 * Remove an edge from the lock graph.
944 */
945 static void
946 lf_remove_edge(struct lockf_edge *e)
947 {
948 struct owner_graph *g = &lf_owner_graph;
949 struct lockf_entry *x = e->le_from;
950 struct lockf_entry *y = e->le_to;
951
952 graph_remove_edge(g, x->lf_owner->lo_vertex, y->lf_owner->lo_vertex);
953 LIST_REMOVE(e, le_outlink);
954 LIST_REMOVE(e, le_inlink);
955 e->le_from = NULL;
956 e->le_to = NULL;
957 lf_free_edge(e);
958 }
959
960 /*
961 * Remove all out-going edges from lock x.
962 */
963 static void
964 lf_remove_outgoing(struct lockf_entry *x)
965 {
966 struct lockf_edge *e;
967
968 while ((e = LIST_FIRST(&x->lf_outedges)) != NULL) {
969 lf_remove_edge(e);
970 }
971 }
972
973 /*
974 * Remove all in-coming edges from lock x.
975 */
976 static void
977 lf_remove_incoming(struct lockf_entry *x)
978 {
979 struct lockf_edge *e;
980
981 while ((e = LIST_FIRST(&x->lf_inedges)) != NULL) {
982 lf_remove_edge(e);
983 }
984 }
985
986 /*
987 * Walk the list of locks for the file and create an out-going edge
988 * from lock to each blocking lock.
989 */
990 static int
991 lf_add_outgoing(struct lockf *state, struct lockf_entry *lock)
992 {
993 struct lockf_entry *overlap;
994 int error;
995
996 LIST_FOREACH(overlap, &state->ls_active, lf_link) {
997 /*
998 * We may assume that the active list is sorted by
999 * lf_start.
1000 */
1001 if (overlap->lf_start > lock->lf_end)
1002 break;
1003 if (!lf_blocks(lock, overlap))
1004 continue;
1005
1006 /*
1007 * We've found a blocking lock. Add the corresponding
1008 * edge to the graphs and see if it would cause a
1009 * deadlock.
1010 */
1011 error = lf_add_edge(lock, overlap);
1012
1013 /*
1014 * The only error that lf_add_edge returns is EDEADLK.
1015 * Remove any edges we added and return the error.
1016 */
1017 if (error) {
1018 lf_remove_outgoing(lock);
1019 return (error);
1020 }
1021 }
1022
1023 /*
1024 * We also need to add edges to sleeping locks that block
1025 * us. This ensures that lf_wakeup_lock cannot grant two
1026 * mutually blocking locks simultaneously and also enforces a
1027 * 'first come, first served' fairness model. Note that this
1028 * only happens if we are blocked by at least one active lock
1029 * due to the call to lf_getblock in lf_setlock below.
1030 */
1031 LIST_FOREACH(overlap, &state->ls_pending, lf_link) {
1032 if (!lf_blocks(lock, overlap))
1033 continue;
1034 /*
1035 * We've found a blocking lock. Add the corresponding
1036 * edge to the graphs and see if it would cause a
1037 * deadlock.
1038 */
1039 error = lf_add_edge(lock, overlap);
1040
1041 /*
1042 * The only error that lf_add_edge returns is EDEADLK.
1043 * Remove any edges we added and return the error.
1044 */
1045 if (error) {
1046 lf_remove_outgoing(lock);
1047 return (error);
1048 }
1049 }
1050
1051 return (0);
1052 }
1053
1054 /*
1055 * Walk the list of pending locks for the file and create an in-coming
1056 * edge from lock to each blocking lock.
1057 */
1058 static int
1059 lf_add_incoming(struct lockf *state, struct lockf_entry *lock)
1060 {
1061 struct lockf_entry *overlap;
1062 int error;
1063
1064 LIST_FOREACH(overlap, &state->ls_pending, lf_link) {
1065 if (!lf_blocks(lock, overlap))
1066 continue;
1067
1068 /*
1069 * We've found a blocking lock. Add the corresponding
1070 * edge to the graphs and see if it would cause a
1071 * deadlock.
1072 */
1073 error = lf_add_edge(overlap, lock);
1074
1075 /*
1076 * The only error that lf_add_edge returns is EDEADLK.
1077 * Remove any edges we added and return the error.
1078 */
1079 if (error) {
1080 lf_remove_incoming(lock);
1081 return (error);
1082 }
1083 }
1084 return (0);
1085 }
1086
1087 /*
1088 * Insert lock into the active list, keeping list entries ordered by
1089 * increasing values of lf_start.
1090 */
1091 static void
1092 lf_insert_lock(struct lockf *state, struct lockf_entry *lock)
1093 {
1094 struct lockf_entry *lf, *lfprev;
1095
1096 if (LIST_EMPTY(&state->ls_active)) {
1097 LIST_INSERT_HEAD(&state->ls_active, lock, lf_link);
1098 return;
1099 }
1100
1101 lfprev = NULL;
1102 LIST_FOREACH(lf, &state->ls_active, lf_link) {
1103 if (lf->lf_start > lock->lf_start) {
1104 LIST_INSERT_BEFORE(lf, lock, lf_link);
1105 return;
1106 }
1107 lfprev = lf;
1108 }
1109 LIST_INSERT_AFTER(lfprev, lock, lf_link);
1110 }
1111
1112 /*
1113 * Wake up a sleeping lock and remove it from the pending list now
1114 * that all its dependancies have been resolved. The caller should
1115 * arrange for the lock to be added to the active list, adjusting any
1116 * existing locks for the same owner as needed.
1117 */
1118 static void
1119 lf_wakeup_lock(struct lockf *state, struct lockf_entry *wakelock)
1120 {
1121
1122 /*
1123 * Remove from ls_pending list and wake up the caller
1124 * or start the async notification, as appropriate.
1125 */
1126 LIST_REMOVE(wakelock, lf_link);
1127 #ifdef LOCKF_DEBUG
1128 if (lockf_debug & 1)
1129 lf_print("lf_wakeup_lock: awakening", wakelock);
1130 #endif /* LOCKF_DEBUG */
1131 if (wakelock->lf_async_task) {
1132 taskqueue_enqueue(taskqueue_thread, wakelock->lf_async_task);
1133 } else {
1134 wakeup(wakelock);
1135 }
1136 }
1137
1138 /*
1139 * Re-check all dependant locks and remove edges to locks that we no
1140 * longer block. If 'all' is non-zero, the lock has been removed and
1141 * we must remove all the dependancies, otherwise it has simply been
1142 * reduced but remains active. Any pending locks which have been been
1143 * unblocked are added to 'granted'
1144 */
1145 static void
1146 lf_update_dependancies(struct lockf *state, struct lockf_entry *lock, int all,
1147 struct lockf_entry_list *granted)
1148 {
1149 struct lockf_edge *e, *ne;
1150 struct lockf_entry *deplock;
1151
1152 LIST_FOREACH_SAFE(e, &lock->lf_inedges, le_inlink, ne) {
1153 deplock = e->le_from;
1154 if (all || !lf_blocks(lock, deplock)) {
1155 sx_xlock(&lf_owner_graph_lock);
1156 lf_remove_edge(e);
1157 sx_xunlock(&lf_owner_graph_lock);
1158 if (LIST_EMPTY(&deplock->lf_outedges)) {
1159 lf_wakeup_lock(state, deplock);
1160 LIST_INSERT_HEAD(granted, deplock, lf_link);
1161 }
1162 }
1163 }
1164 }
1165
1166 /*
1167 * Set the start of an existing active lock, updating dependancies and
1168 * adding any newly woken locks to 'granted'.
1169 */
1170 static void
1171 lf_set_start(struct lockf *state, struct lockf_entry *lock, off_t new_start,
1172 struct lockf_entry_list *granted)
1173 {
1174
1175 KASSERT(new_start >= lock->lf_start, ("can't increase lock"));
1176 lock->lf_start = new_start;
1177 LIST_REMOVE(lock, lf_link);
1178 lf_insert_lock(state, lock);
1179 lf_update_dependancies(state, lock, FALSE, granted);
1180 }
1181
1182 /*
1183 * Set the end of an existing active lock, updating dependancies and
1184 * adding any newly woken locks to 'granted'.
1185 */
1186 static void
1187 lf_set_end(struct lockf *state, struct lockf_entry *lock, off_t new_end,
1188 struct lockf_entry_list *granted)
1189 {
1190
1191 KASSERT(new_end <= lock->lf_end, ("can't increase lock"));
1192 lock->lf_end = new_end;
1193 lf_update_dependancies(state, lock, FALSE, granted);
1194 }
1195
1196 /*
1197 * Add a lock to the active list, updating or removing any current
1198 * locks owned by the same owner and processing any pending locks that
1199 * become unblocked as a result. This code is also used for unlock
1200 * since the logic for updating existing locks is identical.
1201 *
1202 * As a result of processing the new lock, we may unblock existing
1203 * pending locks as a result of downgrading/unlocking. We simply
1204 * activate the newly granted locks by looping.
1205 *
1206 * Since the new lock already has its dependancies set up, we always
1207 * add it to the list (unless its an unlock request). This may
1208 * fragment the lock list in some pathological cases but its probably
1209 * not a real problem.
1210 */
1211 static void
1212 lf_activate_lock(struct lockf *state, struct lockf_entry *lock)
1213 {
1214 struct lockf_entry *overlap, *lf;
1215 struct lockf_entry_list granted;
1216 int ovcase;
1217
1218 LIST_INIT(&granted);
1219 LIST_INSERT_HEAD(&granted, lock, lf_link);
1220
1221 while (!LIST_EMPTY(&granted)) {
1222 lock = LIST_FIRST(&granted);
1223 LIST_REMOVE(lock, lf_link);
1224
1225 /*
1226 * Skip over locks owned by other processes. Handle
1227 * any locks that overlap and are owned by ourselves.
1228 */
1229 overlap = LIST_FIRST(&state->ls_active);
1230 for (;;) {
1231 ovcase = lf_findoverlap(&overlap, lock, SELF);
1232
1233 #ifdef LOCKF_DEBUG
1234 if (ovcase && (lockf_debug & 2)) {
1235 printf("lf_setlock: overlap %d", ovcase);
1236 lf_print("", overlap);
1237 }
1238 #endif
1239 /*
1240 * Six cases:
1241 * 0) no overlap
1242 * 1) overlap == lock
1243 * 2) overlap contains lock
1244 * 3) lock contains overlap
1245 * 4) overlap starts before lock
1246 * 5) overlap ends after lock
1247 */
1248 switch (ovcase) {
1249 case 0: /* no overlap */
1250 break;
1251
1252 case 1: /* overlap == lock */
1253 /*
1254 * We have already setup the
1255 * dependants for the new lock, taking
1256 * into account a possible downgrade
1257 * or unlock. Remove the old lock.
1258 */
1259 LIST_REMOVE(overlap, lf_link);
1260 lf_update_dependancies(state, overlap, TRUE,
1261 &granted);
1262 lf_free_lock(overlap);
1263 break;
1264
1265 case 2: /* overlap contains lock */
1266 /*
1267 * Just split the existing lock.
1268 */
1269 lf_split(state, overlap, lock, &granted);
1270 break;
1271
1272 case 3: /* lock contains overlap */
1273 /*
1274 * Delete the overlap and advance to
1275 * the next entry in the list.
1276 */
1277 lf = LIST_NEXT(overlap, lf_link);
1278 LIST_REMOVE(overlap, lf_link);
1279 lf_update_dependancies(state, overlap, TRUE,
1280 &granted);
1281 lf_free_lock(overlap);
1282 overlap = lf;
1283 continue;
1284
1285 case 4: /* overlap starts before lock */
1286 /*
1287 * Just update the overlap end and
1288 * move on.
1289 */
1290 lf_set_end(state, overlap, lock->lf_start - 1,
1291 &granted);
1292 overlap = LIST_NEXT(overlap, lf_link);
1293 continue;
1294
1295 case 5: /* overlap ends after lock */
1296 /*
1297 * Change the start of overlap and
1298 * re-insert.
1299 */
1300 lf_set_start(state, overlap, lock->lf_end + 1,
1301 &granted);
1302 break;
1303 }
1304 break;
1305 }
1306 #ifdef LOCKF_DEBUG
1307 if (lockf_debug & 1) {
1308 if (lock->lf_type != F_UNLCK)
1309 lf_print("lf_activate_lock: activated", lock);
1310 else
1311 lf_print("lf_activate_lock: unlocked", lock);
1312 lf_printlist("lf_activate_lock", lock);
1313 }
1314 #endif /* LOCKF_DEBUG */
1315 if (lock->lf_type != F_UNLCK)
1316 lf_insert_lock(state, lock);
1317 }
1318 }
1319
1320 /*
1321 * Cancel a pending lock request, either as a result of a signal or a
1322 * cancel request for an async lock.
1323 */
1324 static void
1325 lf_cancel_lock(struct lockf *state, struct lockf_entry *lock)
1326 {
1327 struct lockf_entry_list granted;
1328
1329 /*
1330 * Note it is theoretically possible that cancelling this lock
1331 * may allow some other pending lock to become
1332 * active. Consider this case:
1333 *
1334 * Owner Action Result Dependancies
1335 *
1336 * A: lock [0..0] succeeds
1337 * B: lock [2..2] succeeds
1338 * C: lock [1..2] blocked C->B
1339 * D: lock [0..1] blocked C->B,D->A,D->C
1340 * A: unlock [0..0] C->B,D->C
1341 * C: cancel [1..2]
1342 */
1343
1344 LIST_REMOVE(lock, lf_link);
1345
1346 /*
1347 * Removing out-going edges is simple.
1348 */
1349 sx_xlock(&lf_owner_graph_lock);
1350 lf_remove_outgoing(lock);
1351 sx_xunlock(&lf_owner_graph_lock);
1352
1353 /*
1354 * Removing in-coming edges may allow some other lock to
1355 * become active - we use lf_update_dependancies to figure
1356 * this out.
1357 */
1358 LIST_INIT(&granted);
1359 lf_update_dependancies(state, lock, TRUE, &granted);
1360 lf_free_lock(lock);
1361
1362 /*
1363 * Feed any newly active locks to lf_activate_lock.
1364 */
1365 while (!LIST_EMPTY(&granted)) {
1366 lock = LIST_FIRST(&granted);
1367 LIST_REMOVE(lock, lf_link);
1368 lf_activate_lock(state, lock);
1369 }
1370 }
1371
1372 /*
1373 * Set a byte-range lock.
1374 */
1375 static int
1376 lf_setlock(struct lockf *state, struct lockf_entry *lock, struct vnode *vp,
1377 void **cookiep)
1378 {
1379 static char lockstr[] = "lockf";
1380 int priority, error;
1381
1382 #ifdef LOCKF_DEBUG
1383 if (lockf_debug & 1)
1384 lf_print("lf_setlock", lock);
1385 #endif /* LOCKF_DEBUG */
1386
1387 /*
1388 * Set the priority
1389 */
1390 priority = PLOCK;
1391 if (lock->lf_type == F_WRLCK)
1392 priority += 4;
1393 if (!(lock->lf_flags & F_NOINTR))
1394 priority |= PCATCH;
1395 /*
1396 * Scan lock list for this file looking for locks that would block us.
1397 */
1398 if (lf_getblock(state, lock)) {
1399 /*
1400 * Free the structure and return if nonblocking.
1401 */
1402 if ((lock->lf_flags & F_WAIT) == 0
1403 && lock->lf_async_task == NULL) {
1404 lf_free_lock(lock);
1405 error = EAGAIN;
1406 goto out;
1407 }
1408
1409 /*
1410 * For flock type locks, we must first remove
1411 * any shared locks that we hold before we sleep
1412 * waiting for an exclusive lock.
1413 */
1414 if ((lock->lf_flags & F_FLOCK) &&
1415 lock->lf_type == F_WRLCK) {
1416 lock->lf_type = F_UNLCK;
1417 lf_activate_lock(state, lock);
1418 lock->lf_type = F_WRLCK;
1419 }
1420
1421 /*
1422 * We are blocked. Create edges to each blocking lock,
1423 * checking for deadlock using the owner graph. For
1424 * simplicity, we run deadlock detection for all
1425 * locks, posix and otherwise.
1426 */
1427 sx_xlock(&lf_owner_graph_lock);
1428 error = lf_add_outgoing(state, lock);
1429 sx_xunlock(&lf_owner_graph_lock);
1430
1431 if (error) {
1432 #ifdef LOCKF_DEBUG
1433 if (lockf_debug & 1)
1434 lf_print("lf_setlock: deadlock", lock);
1435 #endif
1436 lf_free_lock(lock);
1437 goto out;
1438 }
1439
1440 /*
1441 * We have added edges to everything that blocks
1442 * us. Sleep until they all go away.
1443 */
1444 LIST_INSERT_HEAD(&state->ls_pending, lock, lf_link);
1445 #ifdef LOCKF_DEBUG
1446 if (lockf_debug & 1) {
1447 struct lockf_edge *e;
1448 LIST_FOREACH(e, &lock->lf_outedges, le_outlink) {
1449 lf_print("lf_setlock: blocking on", e->le_to);
1450 lf_printlist("lf_setlock", e->le_to);
1451 }
1452 }
1453 #endif /* LOCKF_DEBUG */
1454
1455 if ((lock->lf_flags & F_WAIT) == 0) {
1456 /*
1457 * The caller requested async notification -
1458 * this callback happens when the blocking
1459 * lock is released, allowing the caller to
1460 * make another attempt to take the lock.
1461 */
1462 *cookiep = (void *) lock;
1463 error = EINPROGRESS;
1464 goto out;
1465 }
1466
1467 lock->lf_refs++;
1468 error = sx_sleep(lock, &state->ls_lock, priority, lockstr, 0);
1469 if (lf_free_lock(lock)) {
1470 error = EDOOFUS;
1471 goto out;
1472 }
1473
1474 /*
1475 * We may have been awakened by a signal and/or by a
1476 * debugger continuing us (in which cases we must
1477 * remove our lock graph edges) and/or by another
1478 * process releasing a lock (in which case our edges
1479 * have already been removed and we have been moved to
1480 * the active list). We may also have been woken by
1481 * lf_purgelocks which we report to the caller as
1482 * EINTR. In that case, lf_purgelocks will have
1483 * removed our lock graph edges.
1484 *
1485 * Note that it is possible to receive a signal after
1486 * we were successfully woken (and moved to the active
1487 * list) but before we resumed execution. In this
1488 * case, our lf_outedges list will be clear. We
1489 * pretend there was no error.
1490 *
1491 * Note also, if we have been sleeping long enough, we
1492 * may now have incoming edges from some newer lock
1493 * which is waiting behind us in the queue.
1494 */
1495 if (lock->lf_flags & F_INTR) {
1496 error = EINTR;
1497 lf_free_lock(lock);
1498 goto out;
1499 }
1500 if (LIST_EMPTY(&lock->lf_outedges)) {
1501 error = 0;
1502 } else {
1503 lf_cancel_lock(state, lock);
1504 goto out;
1505 }
1506 #ifdef LOCKF_DEBUG
1507 if (lockf_debug & 1) {
1508 lf_print("lf_setlock: granted", lock);
1509 }
1510 #endif
1511 goto out;
1512 }
1513 /*
1514 * It looks like we are going to grant the lock. First add
1515 * edges from any currently pending lock that the new lock
1516 * would block.
1517 */
1518 sx_xlock(&lf_owner_graph_lock);
1519 error = lf_add_incoming(state, lock);
1520 sx_xunlock(&lf_owner_graph_lock);
1521 if (error) {
1522 #ifdef LOCKF_DEBUG
1523 if (lockf_debug & 1)
1524 lf_print("lf_setlock: deadlock", lock);
1525 #endif
1526 lf_free_lock(lock);
1527 goto out;
1528 }
1529
1530 /*
1531 * No blocks!! Add the lock. Note that we will
1532 * downgrade or upgrade any overlapping locks this
1533 * process already owns.
1534 */
1535 lf_activate_lock(state, lock);
1536 error = 0;
1537 out:
1538 return (error);
1539 }
1540
1541 /*
1542 * Remove a byte-range lock on an inode.
1543 *
1544 * Generally, find the lock (or an overlap to that lock)
1545 * and remove it (or shrink it), then wakeup anyone we can.
1546 */
1547 static int
1548 lf_clearlock(struct lockf *state, struct lockf_entry *unlock)
1549 {
1550 struct lockf_entry *overlap;
1551
1552 overlap = LIST_FIRST(&state->ls_active);
1553
1554 if (overlap == NOLOCKF)
1555 return (0);
1556 #ifdef LOCKF_DEBUG
1557 if (unlock->lf_type != F_UNLCK)
1558 panic("lf_clearlock: bad type");
1559 if (lockf_debug & 1)
1560 lf_print("lf_clearlock", unlock);
1561 #endif /* LOCKF_DEBUG */
1562
1563 lf_activate_lock(state, unlock);
1564
1565 return (0);
1566 }
1567
1568 /*
1569 * Check whether there is a blocking lock, and if so return its
1570 * details in '*fl'.
1571 */
1572 static int
1573 lf_getlock(struct lockf *state, struct lockf_entry *lock, struct flock *fl)
1574 {
1575 struct lockf_entry *block;
1576
1577 #ifdef LOCKF_DEBUG
1578 if (lockf_debug & 1)
1579 lf_print("lf_getlock", lock);
1580 #endif /* LOCKF_DEBUG */
1581
1582 if ((block = lf_getblock(state, lock))) {
1583 fl->l_type = block->lf_type;
1584 fl->l_whence = SEEK_SET;
1585 fl->l_start = block->lf_start;
1586 if (block->lf_end == OFF_MAX)
1587 fl->l_len = 0;
1588 else
1589 fl->l_len = block->lf_end - block->lf_start + 1;
1590 fl->l_pid = block->lf_owner->lo_pid;
1591 fl->l_sysid = block->lf_owner->lo_sysid;
1592 } else {
1593 fl->l_type = F_UNLCK;
1594 }
1595 return (0);
1596 }
1597
1598 /*
1599 * Cancel an async lock request.
1600 */
1601 static int
1602 lf_cancel(struct lockf *state, struct lockf_entry *lock, void *cookie)
1603 {
1604 struct lockf_entry *reallock;
1605
1606 /*
1607 * We need to match this request with an existing lock
1608 * request.
1609 */
1610 LIST_FOREACH(reallock, &state->ls_pending, lf_link) {
1611 if ((void *) reallock == cookie) {
1612 /*
1613 * Double-check that this lock looks right
1614 * (maybe use a rolling ID for the cancel
1615 * cookie instead?)
1616 */
1617 if (!(reallock->lf_vnode == lock->lf_vnode
1618 && reallock->lf_start == lock->lf_start
1619 && reallock->lf_end == lock->lf_end)) {
1620 return (ENOENT);
1621 }
1622
1623 /*
1624 * Make sure this lock was async and then just
1625 * remove it from its wait lists.
1626 */
1627 if (!reallock->lf_async_task) {
1628 return (ENOENT);
1629 }
1630
1631 /*
1632 * Note that since any other thread must take
1633 * state->ls_lock before it can possibly
1634 * trigger the async callback, we are safe
1635 * from a race with lf_wakeup_lock, i.e. we
1636 * can free the lock (actually our caller does
1637 * this).
1638 */
1639 lf_cancel_lock(state, reallock);
1640 return (0);
1641 }
1642 }
1643
1644 /*
1645 * We didn't find a matching lock - not much we can do here.
1646 */
1647 return (ENOENT);
1648 }
1649
1650 /*
1651 * Walk the list of locks for an inode and
1652 * return the first blocking lock.
1653 */
1654 static struct lockf_entry *
1655 lf_getblock(struct lockf *state, struct lockf_entry *lock)
1656 {
1657 struct lockf_entry *overlap;
1658
1659 LIST_FOREACH(overlap, &state->ls_active, lf_link) {
1660 /*
1661 * We may assume that the active list is sorted by
1662 * lf_start.
1663 */
1664 if (overlap->lf_start > lock->lf_end)
1665 break;
1666 if (!lf_blocks(lock, overlap))
1667 continue;
1668 return (overlap);
1669 }
1670 return (NOLOCKF);
1671 }
1672
1673 /*
1674 * Walk the list of locks for an inode to find an overlapping lock (if
1675 * any) and return a classification of that overlap.
1676 *
1677 * Arguments:
1678 * *overlap The place in the lock list to start looking
1679 * lock The lock which is being tested
1680 * type Pass 'SELF' to test only locks with the same
1681 * owner as lock, or 'OTHER' to test only locks
1682 * with a different owner
1683 *
1684 * Returns one of six values:
1685 * 0) no overlap
1686 * 1) overlap == lock
1687 * 2) overlap contains lock
1688 * 3) lock contains overlap
1689 * 4) overlap starts before lock
1690 * 5) overlap ends after lock
1691 *
1692 * If there is an overlapping lock, '*overlap' is set to point at the
1693 * overlapping lock.
1694 *
1695 * NOTE: this returns only the FIRST overlapping lock. There
1696 * may be more than one.
1697 */
1698 static int
1699 lf_findoverlap(struct lockf_entry **overlap, struct lockf_entry *lock, int type)
1700 {
1701 struct lockf_entry *lf;
1702 off_t start, end;
1703 int res;
1704
1705 if ((*overlap) == NOLOCKF) {
1706 return (0);
1707 }
1708 #ifdef LOCKF_DEBUG
1709 if (lockf_debug & 2)
1710 lf_print("lf_findoverlap: looking for overlap in", lock);
1711 #endif /* LOCKF_DEBUG */
1712 start = lock->lf_start;
1713 end = lock->lf_end;
1714 res = 0;
1715 while (*overlap) {
1716 lf = *overlap;
1717 if (lf->lf_start > end)
1718 break;
1719 if (((type & SELF) && lf->lf_owner != lock->lf_owner) ||
1720 ((type & OTHERS) && lf->lf_owner == lock->lf_owner)) {
1721 *overlap = LIST_NEXT(lf, lf_link);
1722 continue;
1723 }
1724 #ifdef LOCKF_DEBUG
1725 if (lockf_debug & 2)
1726 lf_print("\tchecking", lf);
1727 #endif /* LOCKF_DEBUG */
1728 /*
1729 * OK, check for overlap
1730 *
1731 * Six cases:
1732 * 0) no overlap
1733 * 1) overlap == lock
1734 * 2) overlap contains lock
1735 * 3) lock contains overlap
1736 * 4) overlap starts before lock
1737 * 5) overlap ends after lock
1738 */
1739 if (start > lf->lf_end) {
1740 /* Case 0 */
1741 #ifdef LOCKF_DEBUG
1742 if (lockf_debug & 2)
1743 printf("no overlap\n");
1744 #endif /* LOCKF_DEBUG */
1745 *overlap = LIST_NEXT(lf, lf_link);
1746 continue;
1747 }
1748 if (lf->lf_start == start && lf->lf_end == end) {
1749 /* Case 1 */
1750 #ifdef LOCKF_DEBUG
1751 if (lockf_debug & 2)
1752 printf("overlap == lock\n");
1753 #endif /* LOCKF_DEBUG */
1754 res = 1;
1755 break;
1756 }
1757 if (lf->lf_start <= start && lf->lf_end >= end) {
1758 /* Case 2 */
1759 #ifdef LOCKF_DEBUG
1760 if (lockf_debug & 2)
1761 printf("overlap contains lock\n");
1762 #endif /* LOCKF_DEBUG */
1763 res = 2;
1764 break;
1765 }
1766 if (start <= lf->lf_start && end >= lf->lf_end) {
1767 /* Case 3 */
1768 #ifdef LOCKF_DEBUG
1769 if (lockf_debug & 2)
1770 printf("lock contains overlap\n");
1771 #endif /* LOCKF_DEBUG */
1772 res = 3;
1773 break;
1774 }
1775 if (lf->lf_start < start && lf->lf_end >= start) {
1776 /* Case 4 */
1777 #ifdef LOCKF_DEBUG
1778 if (lockf_debug & 2)
1779 printf("overlap starts before lock\n");
1780 #endif /* LOCKF_DEBUG */
1781 res = 4;
1782 break;
1783 }
1784 if (lf->lf_start > start && lf->lf_end > end) {
1785 /* Case 5 */
1786 #ifdef LOCKF_DEBUG
1787 if (lockf_debug & 2)
1788 printf("overlap ends after lock\n");
1789 #endif /* LOCKF_DEBUG */
1790 res = 5;
1791 break;
1792 }
1793 panic("lf_findoverlap: default");
1794 }
1795 return (res);
1796 }
1797
1798 /*
1799 * Split an the existing 'lock1', based on the extent of the lock
1800 * described by 'lock2'. The existing lock should cover 'lock2'
1801 * entirely.
1802 *
1803 * Any pending locks which have been been unblocked are added to
1804 * 'granted'
1805 */
1806 static void
1807 lf_split(struct lockf *state, struct lockf_entry *lock1,
1808 struct lockf_entry *lock2, struct lockf_entry_list *granted)
1809 {
1810 struct lockf_entry *splitlock;
1811
1812 #ifdef LOCKF_DEBUG
1813 if (lockf_debug & 2) {
1814 lf_print("lf_split", lock1);
1815 lf_print("splitting from", lock2);
1816 }
1817 #endif /* LOCKF_DEBUG */
1818 /*
1819 * Check to see if we don't need to split at all.
1820 */
1821 if (lock1->lf_start == lock2->lf_start) {
1822 lf_set_start(state, lock1, lock2->lf_end + 1, granted);
1823 return;
1824 }
1825 if (lock1->lf_end == lock2->lf_end) {
1826 lf_set_end(state, lock1, lock2->lf_start - 1, granted);
1827 return;
1828 }
1829 /*
1830 * Make a new lock consisting of the last part of
1831 * the encompassing lock.
1832 */
1833 splitlock = lf_alloc_lock(lock1->lf_owner);
1834 memcpy(splitlock, lock1, sizeof *splitlock);
1835 splitlock->lf_refs = 1;
1836 if (splitlock->lf_flags & F_REMOTE)
1837 vref(splitlock->lf_vnode);
1838
1839 /*
1840 * This cannot cause a deadlock since any edges we would add
1841 * to splitlock already exist in lock1. We must be sure to add
1842 * necessary dependancies to splitlock before we reduce lock1
1843 * otherwise we may accidentally grant a pending lock that
1844 * was blocked by the tail end of lock1.
1845 */
1846 splitlock->lf_start = lock2->lf_end + 1;
1847 LIST_INIT(&splitlock->lf_outedges);
1848 LIST_INIT(&splitlock->lf_inedges);
1849 sx_xlock(&lf_owner_graph_lock);
1850 lf_add_incoming(state, splitlock);
1851 sx_xunlock(&lf_owner_graph_lock);
1852
1853 lf_set_end(state, lock1, lock2->lf_start - 1, granted);
1854
1855 /*
1856 * OK, now link it in
1857 */
1858 lf_insert_lock(state, splitlock);
1859 }
1860
1861 struct lockdesc {
1862 STAILQ_ENTRY(lockdesc) link;
1863 struct vnode *vp;
1864 struct flock fl;
1865 };
1866 STAILQ_HEAD(lockdesclist, lockdesc);
1867
1868 int
1869 lf_iteratelocks_sysid(int sysid, lf_iterator *fn, void *arg)
1870 {
1871 struct lockf *ls;
1872 struct lockf_entry *lf;
1873 struct lockdesc *ldesc;
1874 struct lockdesclist locks;
1875 int error;
1876
1877 /*
1878 * In order to keep the locking simple, we iterate over the
1879 * active lock lists to build a list of locks that need
1880 * releasing. We then call the iterator for each one in turn.
1881 *
1882 * We take an extra reference to the vnode for the duration to
1883 * make sure it doesn't go away before we are finished.
1884 */
1885 STAILQ_INIT(&locks);
1886 sx_xlock(&lf_lock_states_lock);
1887 LIST_FOREACH(ls, &lf_lock_states, ls_link) {
1888 sx_xlock(&ls->ls_lock);
1889 LIST_FOREACH(lf, &ls->ls_active, lf_link) {
1890 if (lf->lf_owner->lo_sysid != sysid)
1891 continue;
1892
1893 ldesc = malloc(sizeof(struct lockdesc), M_LOCKF,
1894 M_WAITOK);
1895 ldesc->vp = lf->lf_vnode;
1896 vref(ldesc->vp);
1897 ldesc->fl.l_start = lf->lf_start;
1898 if (lf->lf_end == OFF_MAX)
1899 ldesc->fl.l_len = 0;
1900 else
1901 ldesc->fl.l_len =
1902 lf->lf_end - lf->lf_start + 1;
1903 ldesc->fl.l_whence = SEEK_SET;
1904 ldesc->fl.l_type = F_UNLCK;
1905 ldesc->fl.l_pid = lf->lf_owner->lo_pid;
1906 ldesc->fl.l_sysid = sysid;
1907 STAILQ_INSERT_TAIL(&locks, ldesc, link);
1908 }
1909 sx_xunlock(&ls->ls_lock);
1910 }
1911 sx_xunlock(&lf_lock_states_lock);
1912
1913 /*
1914 * Call the iterator function for each lock in turn. If the
1915 * iterator returns an error code, just free the rest of the
1916 * lockdesc structures.
1917 */
1918 error = 0;
1919 while ((ldesc = STAILQ_FIRST(&locks)) != NULL) {
1920 STAILQ_REMOVE_HEAD(&locks, link);
1921 if (!error)
1922 error = fn(ldesc->vp, &ldesc->fl, arg);
1923 vrele(ldesc->vp);
1924 free(ldesc, M_LOCKF);
1925 }
1926
1927 return (error);
1928 }
1929
1930 int
1931 lf_iteratelocks_vnode(struct vnode *vp, lf_iterator *fn, void *arg)
1932 {
1933 struct lockf *ls;
1934 struct lockf_entry *lf;
1935 struct lockdesc *ldesc;
1936 struct lockdesclist locks;
1937 int error;
1938
1939 /*
1940 * In order to keep the locking simple, we iterate over the
1941 * active lock lists to build a list of locks that need
1942 * releasing. We then call the iterator for each one in turn.
1943 *
1944 * We take an extra reference to the vnode for the duration to
1945 * make sure it doesn't go away before we are finished.
1946 */
1947 STAILQ_INIT(&locks);
1948 VI_LOCK(vp);
1949 ls = vp->v_lockf;
1950 if (!ls) {
1951 VI_UNLOCK(vp);
1952 return (0);
1953 }
1954 ls->ls_threads++;
1955 VI_UNLOCK(vp);
1956
1957 sx_xlock(&ls->ls_lock);
1958 LIST_FOREACH(lf, &ls->ls_active, lf_link) {
1959 ldesc = malloc(sizeof(struct lockdesc), M_LOCKF,
1960 M_WAITOK);
1961 ldesc->vp = lf->lf_vnode;
1962 vref(ldesc->vp);
1963 ldesc->fl.l_start = lf->lf_start;
1964 if (lf->lf_end == OFF_MAX)
1965 ldesc->fl.l_len = 0;
1966 else
1967 ldesc->fl.l_len =
1968 lf->lf_end - lf->lf_start + 1;
1969 ldesc->fl.l_whence = SEEK_SET;
1970 ldesc->fl.l_type = F_UNLCK;
1971 ldesc->fl.l_pid = lf->lf_owner->lo_pid;
1972 ldesc->fl.l_sysid = lf->lf_owner->lo_sysid;
1973 STAILQ_INSERT_TAIL(&locks, ldesc, link);
1974 }
1975 sx_xunlock(&ls->ls_lock);
1976 VI_LOCK(vp);
1977 ls->ls_threads--;
1978 wakeup(ls);
1979 VI_UNLOCK(vp);
1980
1981 /*
1982 * Call the iterator function for each lock in turn. If the
1983 * iterator returns an error code, just free the rest of the
1984 * lockdesc structures.
1985 */
1986 error = 0;
1987 while ((ldesc = STAILQ_FIRST(&locks)) != NULL) {
1988 STAILQ_REMOVE_HEAD(&locks, link);
1989 if (!error)
1990 error = fn(ldesc->vp, &ldesc->fl, arg);
1991 vrele(ldesc->vp);
1992 free(ldesc, M_LOCKF);
1993 }
1994
1995 return (error);
1996 }
1997
1998 static int
1999 lf_clearremotesys_iterator(struct vnode *vp, struct flock *fl, void *arg)
2000 {
2001
2002 VOP_ADVLOCK(vp, 0, F_UNLCK, fl, F_REMOTE);
2003 return (0);
2004 }
2005
2006 void
2007 lf_clearremotesys(int sysid)
2008 {
2009
2010 KASSERT(sysid != 0, ("Can't clear local locks with F_UNLCKSYS"));
2011 lf_iteratelocks_sysid(sysid, lf_clearremotesys_iterator, NULL);
2012 }
2013
2014 int
2015 lf_countlocks(int sysid)
2016 {
2017 int i;
2018 struct lock_owner *lo;
2019 int count;
2020
2021 count = 0;
2022 sx_xlock(&lf_lock_owners_lock);
2023 for (i = 0; i < LOCK_OWNER_HASH_SIZE; i++)
2024 LIST_FOREACH(lo, &lf_lock_owners[i], lo_link)
2025 if (lo->lo_sysid == sysid)
2026 count += lo->lo_refs;
2027 sx_xunlock(&lf_lock_owners_lock);
2028
2029 return (count);
2030 }
2031
2032 #ifdef LOCKF_DEBUG
2033
2034 /*
2035 * Return non-zero if y is reachable from x using a brute force
2036 * search. If reachable and path is non-null, return the route taken
2037 * in path.
2038 */
2039 static int
2040 graph_reaches(struct owner_vertex *x, struct owner_vertex *y,
2041 struct owner_vertex_list *path)
2042 {
2043 struct owner_edge *e;
2044
2045 if (x == y) {
2046 if (path)
2047 TAILQ_INSERT_HEAD(path, x, v_link);
2048 return 1;
2049 }
2050
2051 LIST_FOREACH(e, &x->v_outedges, e_outlink) {
2052 if (graph_reaches(e->e_to, y, path)) {
2053 if (path)
2054 TAILQ_INSERT_HEAD(path, x, v_link);
2055 return 1;
2056 }
2057 }
2058 return 0;
2059 }
2060
2061 /*
2062 * Perform consistency checks on the graph. Make sure the values of
2063 * v_order are correct. If checkorder is non-zero, check no vertex can
2064 * reach any other vertex with a smaller order.
2065 */
2066 static void
2067 graph_check(struct owner_graph *g, int checkorder)
2068 {
2069 int i, j;
2070
2071 for (i = 0; i < g->g_size; i++) {
2072 if (!g->g_vertices[i]->v_owner)
2073 continue;
2074 KASSERT(g->g_vertices[i]->v_order == i,
2075 ("lock graph vertices disordered"));
2076 if (checkorder) {
2077 for (j = 0; j < i; j++) {
2078 if (!g->g_vertices[j]->v_owner)
2079 continue;
2080 KASSERT(!graph_reaches(g->g_vertices[i],
2081 g->g_vertices[j], NULL),
2082 ("lock graph vertices disordered"));
2083 }
2084 }
2085 }
2086 }
2087
2088 static void
2089 graph_print_vertices(struct owner_vertex_list *set)
2090 {
2091 struct owner_vertex *v;
2092
2093 printf("{ ");
2094 TAILQ_FOREACH(v, set, v_link) {
2095 printf("%d:", v->v_order);
2096 lf_print_owner(v->v_owner);
2097 if (TAILQ_NEXT(v, v_link))
2098 printf(", ");
2099 }
2100 printf(" }\n");
2101 }
2102
2103 #endif
2104
2105 /*
2106 * Calculate the sub-set of vertices v from the affected region [y..x]
2107 * where v is reachable from y. Return -1 if a loop was detected
2108 * (i.e. x is reachable from y, otherwise the number of vertices in
2109 * this subset.
2110 */
2111 static int
2112 graph_delta_forward(struct owner_graph *g, struct owner_vertex *x,
2113 struct owner_vertex *y, struct owner_vertex_list *delta)
2114 {
2115 uint32_t gen;
2116 struct owner_vertex *v;
2117 struct owner_edge *e;
2118 int n;
2119
2120 /*
2121 * We start with a set containing just y. Then for each vertex
2122 * v in the set so far unprocessed, we add each vertex that v
2123 * has an out-edge to and that is within the affected region
2124 * [y..x]. If we see the vertex x on our travels, stop
2125 * immediately.
2126 */
2127 TAILQ_INIT(delta);
2128 TAILQ_INSERT_TAIL(delta, y, v_link);
2129 v = y;
2130 n = 1;
2131 gen = g->g_gen;
2132 while (v) {
2133 LIST_FOREACH(e, &v->v_outedges, e_outlink) {
2134 if (e->e_to == x)
2135 return -1;
2136 if (e->e_to->v_order < x->v_order
2137 && e->e_to->v_gen != gen) {
2138 e->e_to->v_gen = gen;
2139 TAILQ_INSERT_TAIL(delta, e->e_to, v_link);
2140 n++;
2141 }
2142 }
2143 v = TAILQ_NEXT(v, v_link);
2144 }
2145
2146 return (n);
2147 }
2148
2149 /*
2150 * Calculate the sub-set of vertices v from the affected region [y..x]
2151 * where v reaches x. Return the number of vertices in this subset.
2152 */
2153 static int
2154 graph_delta_backward(struct owner_graph *g, struct owner_vertex *x,
2155 struct owner_vertex *y, struct owner_vertex_list *delta)
2156 {
2157 uint32_t gen;
2158 struct owner_vertex *v;
2159 struct owner_edge *e;
2160 int n;
2161
2162 /*
2163 * We start with a set containing just x. Then for each vertex
2164 * v in the set so far unprocessed, we add each vertex that v
2165 * has an in-edge from and that is within the affected region
2166 * [y..x].
2167 */
2168 TAILQ_INIT(delta);
2169 TAILQ_INSERT_TAIL(delta, x, v_link);
2170 v = x;
2171 n = 1;
2172 gen = g->g_gen;
2173 while (v) {
2174 LIST_FOREACH(e, &v->v_inedges, e_inlink) {
2175 if (e->e_from->v_order > y->v_order
2176 && e->e_from->v_gen != gen) {
2177 e->e_from->v_gen = gen;
2178 TAILQ_INSERT_HEAD(delta, e->e_from, v_link);
2179 n++;
2180 }
2181 }
2182 v = TAILQ_PREV(v, owner_vertex_list, v_link);
2183 }
2184
2185 return (n);
2186 }
2187
2188 static int
2189 graph_add_indices(int *indices, int n, struct owner_vertex_list *set)
2190 {
2191 struct owner_vertex *v;
2192 int i, j;
2193
2194 TAILQ_FOREACH(v, set, v_link) {
2195 for (i = n;
2196 i > 0 && indices[i - 1] > v->v_order; i--)
2197 ;
2198 for (j = n - 1; j >= i; j--)
2199 indices[j + 1] = indices[j];
2200 indices[i] = v->v_order;
2201 n++;
2202 }
2203
2204 return (n);
2205 }
2206
2207 static int
2208 graph_assign_indices(struct owner_graph *g, int *indices, int nextunused,
2209 struct owner_vertex_list *set)
2210 {
2211 struct owner_vertex *v, *vlowest;
2212
2213 while (!TAILQ_EMPTY(set)) {
2214 vlowest = NULL;
2215 TAILQ_FOREACH(v, set, v_link) {
2216 if (!vlowest || v->v_order < vlowest->v_order)
2217 vlowest = v;
2218 }
2219 TAILQ_REMOVE(set, vlowest, v_link);
2220 vlowest->v_order = indices[nextunused];
2221 g->g_vertices[vlowest->v_order] = vlowest;
2222 nextunused++;
2223 }
2224
2225 return (nextunused);
2226 }
2227
2228 static int
2229 graph_add_edge(struct owner_graph *g, struct owner_vertex *x,
2230 struct owner_vertex *y)
2231 {
2232 struct owner_edge *e;
2233 struct owner_vertex_list deltaF, deltaB;
2234 int nF, nB, n, vi, i;
2235 int *indices;
2236
2237 sx_assert(&lf_owner_graph_lock, SX_XLOCKED);
2238
2239 LIST_FOREACH(e, &x->v_outedges, e_outlink) {
2240 if (e->e_to == y) {
2241 e->e_refs++;
2242 return (0);
2243 }
2244 }
2245
2246 #ifdef LOCKF_DEBUG
2247 if (lockf_debug & 8) {
2248 printf("adding edge %d:", x->v_order);
2249 lf_print_owner(x->v_owner);
2250 printf(" -> %d:", y->v_order);
2251 lf_print_owner(y->v_owner);
2252 printf("\n");
2253 }
2254 #endif
2255 if (y->v_order < x->v_order) {
2256 /*
2257 * The new edge violates the order. First find the set
2258 * of affected vertices reachable from y (deltaF) and
2259 * the set of affect vertices affected that reach x
2260 * (deltaB), using the graph generation number to
2261 * detect whether we have visited a given vertex
2262 * already. We re-order the graph so that each vertex
2263 * in deltaB appears before each vertex in deltaF.
2264 *
2265 * If x is a member of deltaF, then the new edge would
2266 * create a cycle. Otherwise, we may assume that
2267 * deltaF and deltaB are disjoint.
2268 */
2269 g->g_gen++;
2270 if (g->g_gen == 0) {
2271 /*
2272 * Generation wrap.
2273 */
2274 for (vi = 0; vi < g->g_size; vi++) {
2275 g->g_vertices[vi]->v_gen = 0;
2276 }
2277 g->g_gen++;
2278 }
2279 nF = graph_delta_forward(g, x, y, &deltaF);
2280 if (nF < 0) {
2281 #ifdef LOCKF_DEBUG
2282 if (lockf_debug & 8) {
2283 struct owner_vertex_list path;
2284 printf("deadlock: ");
2285 TAILQ_INIT(&path);
2286 graph_reaches(y, x, &path);
2287 graph_print_vertices(&path);
2288 }
2289 #endif
2290 return (EDEADLK);
2291 }
2292
2293 #ifdef LOCKF_DEBUG
2294 if (lockf_debug & 8) {
2295 printf("re-ordering graph vertices\n");
2296 printf("deltaF = ");
2297 graph_print_vertices(&deltaF);
2298 }
2299 #endif
2300
2301 nB = graph_delta_backward(g, x, y, &deltaB);
2302
2303 #ifdef LOCKF_DEBUG
2304 if (lockf_debug & 8) {
2305 printf("deltaB = ");
2306 graph_print_vertices(&deltaB);
2307 }
2308 #endif
2309
2310 /*
2311 * We first build a set of vertex indices (vertex
2312 * order values) that we may use, then we re-assign
2313 * orders first to those vertices in deltaB, then to
2314 * deltaF. Note that the contents of deltaF and deltaB
2315 * may be partially disordered - we perform an
2316 * insertion sort while building our index set.
2317 */
2318 indices = g->g_indexbuf;
2319 n = graph_add_indices(indices, 0, &deltaF);
2320 graph_add_indices(indices, n, &deltaB);
2321
2322 /*
2323 * We must also be sure to maintain the relative
2324 * ordering of deltaF and deltaB when re-assigning
2325 * vertices. We do this by iteratively removing the
2326 * lowest ordered element from the set and assigning
2327 * it the next value from our new ordering.
2328 */
2329 i = graph_assign_indices(g, indices, 0, &deltaB);
2330 graph_assign_indices(g, indices, i, &deltaF);
2331
2332 #ifdef LOCKF_DEBUG
2333 if (lockf_debug & 8) {
2334 struct owner_vertex_list set;
2335 TAILQ_INIT(&set);
2336 for (i = 0; i < nB + nF; i++)
2337 TAILQ_INSERT_TAIL(&set,
2338 g->g_vertices[indices[i]], v_link);
2339 printf("new ordering = ");
2340 graph_print_vertices(&set);
2341 }
2342 #endif
2343 }
2344
2345 KASSERT(x->v_order < y->v_order, ("Failed to re-order graph"));
2346
2347 #ifdef LOCKF_DEBUG
2348 if (lockf_debug & 8) {
2349 graph_check(g, TRUE);
2350 }
2351 #endif
2352
2353 e = malloc(sizeof(struct owner_edge), M_LOCKF, M_WAITOK);
2354
2355 LIST_INSERT_HEAD(&x->v_outedges, e, e_outlink);
2356 LIST_INSERT_HEAD(&y->v_inedges, e, e_inlink);
2357 e->e_refs = 1;
2358 e->e_from = x;
2359 e->e_to = y;
2360
2361 return (0);
2362 }
2363
2364 /*
2365 * Remove an edge x->y from the graph.
2366 */
2367 static void
2368 graph_remove_edge(struct owner_graph *g, struct owner_vertex *x,
2369 struct owner_vertex *y)
2370 {
2371 struct owner_edge *e;
2372
2373 sx_assert(&lf_owner_graph_lock, SX_XLOCKED);
2374
2375 LIST_FOREACH(e, &x->v_outedges, e_outlink) {
2376 if (e->e_to == y)
2377 break;
2378 }
2379 KASSERT(e, ("Removing non-existent edge from deadlock graph"));
2380
2381 e->e_refs--;
2382 if (e->e_refs == 0) {
2383 #ifdef LOCKF_DEBUG
2384 if (lockf_debug & 8) {
2385 printf("removing edge %d:", x->v_order);
2386 lf_print_owner(x->v_owner);
2387 printf(" -> %d:", y->v_order);
2388 lf_print_owner(y->v_owner);
2389 printf("\n");
2390 }
2391 #endif
2392 LIST_REMOVE(e, e_outlink);
2393 LIST_REMOVE(e, e_inlink);
2394 free(e, M_LOCKF);
2395 }
2396 }
2397
2398 /*
2399 * Allocate a vertex from the free list. Return ENOMEM if there are
2400 * none.
2401 */
2402 static struct owner_vertex *
2403 graph_alloc_vertex(struct owner_graph *g, struct lock_owner *lo)
2404 {
2405 struct owner_vertex *v;
2406
2407 sx_assert(&lf_owner_graph_lock, SX_XLOCKED);
2408
2409 v = malloc(sizeof(struct owner_vertex), M_LOCKF, M_WAITOK);
2410 if (g->g_size == g->g_space) {
2411 g->g_vertices = realloc(g->g_vertices,
2412 2 * g->g_space * sizeof(struct owner_vertex *),
2413 M_LOCKF, M_WAITOK);
2414 free(g->g_indexbuf, M_LOCKF);
2415 g->g_indexbuf = malloc(2 * g->g_space * sizeof(int),
2416 M_LOCKF, M_WAITOK);
2417 g->g_space = 2 * g->g_space;
2418 }
2419 v->v_order = g->g_size;
2420 v->v_gen = g->g_gen;
2421 g->g_vertices[g->g_size] = v;
2422 g->g_size++;
2423
2424 LIST_INIT(&v->v_outedges);
2425 LIST_INIT(&v->v_inedges);
2426 v->v_owner = lo;
2427
2428 return (v);
2429 }
2430
2431 static void
2432 graph_free_vertex(struct owner_graph *g, struct owner_vertex *v)
2433 {
2434 struct owner_vertex *w;
2435 int i;
2436
2437 sx_assert(&lf_owner_graph_lock, SX_XLOCKED);
2438
2439 KASSERT(LIST_EMPTY(&v->v_outedges), ("Freeing vertex with edges"));
2440 KASSERT(LIST_EMPTY(&v->v_inedges), ("Freeing vertex with edges"));
2441
2442 /*
2443 * Remove from the graph's array and close up the gap,
2444 * renumbering the other vertices.
2445 */
2446 for (i = v->v_order + 1; i < g->g_size; i++) {
2447 w = g->g_vertices[i];
2448 w->v_order--;
2449 g->g_vertices[i - 1] = w;
2450 }
2451 g->g_size--;
2452
2453 free(v, M_LOCKF);
2454 }
2455
2456 static struct owner_graph *
2457 graph_init(struct owner_graph *g)
2458 {
2459
2460 g->g_vertices = malloc(10 * sizeof(struct owner_vertex *),
2461 M_LOCKF, M_WAITOK);
2462 g->g_size = 0;
2463 g->g_space = 10;
2464 g->g_indexbuf = malloc(g->g_space * sizeof(int), M_LOCKF, M_WAITOK);
2465 g->g_gen = 0;
2466
2467 return (g);
2468 }
2469
2470 #ifdef LOCKF_DEBUG
2471 /*
2472 * Print description of a lock owner
2473 */
2474 static void
2475 lf_print_owner(struct lock_owner *lo)
2476 {
2477
2478 if (lo->lo_flags & F_REMOTE) {
2479 printf("remote pid %d, system %d",
2480 lo->lo_pid, lo->lo_sysid);
2481 } else if (lo->lo_flags & F_FLOCK) {
2482 printf("file %p", lo->lo_id);
2483 } else {
2484 printf("local pid %d", lo->lo_pid);
2485 }
2486 }
2487
2488 /*
2489 * Print out a lock.
2490 */
2491 static void
2492 lf_print(char *tag, struct lockf_entry *lock)
2493 {
2494
2495 printf("%s: lock %p for ", tag, (void *)lock);
2496 lf_print_owner(lock->lf_owner);
2497 if (lock->lf_inode != (struct inode *)0)
2498 printf(" in ino %ju on dev <%s>,",
2499 (uintmax_t)lock->lf_inode->i_number,
2500 devtoname(lock->lf_inode->i_dev));
2501 printf(" %s, start %jd, end ",
2502 lock->lf_type == F_RDLCK ? "shared" :
2503 lock->lf_type == F_WRLCK ? "exclusive" :
2504 lock->lf_type == F_UNLCK ? "unlock" : "unknown",
2505 (intmax_t)lock->lf_start);
2506 if (lock->lf_end == OFF_MAX)
2507 printf("EOF");
2508 else
2509 printf("%jd", (intmax_t)lock->lf_end);
2510 if (!LIST_EMPTY(&lock->lf_outedges))
2511 printf(" block %p\n",
2512 (void *)LIST_FIRST(&lock->lf_outedges)->le_to);
2513 else
2514 printf("\n");
2515 }
2516
2517 static void
2518 lf_printlist(char *tag, struct lockf_entry *lock)
2519 {
2520 struct lockf_entry *lf, *blk;
2521 struct lockf_edge *e;
2522
2523 if (lock->lf_inode == (struct inode *)0)
2524 return;
2525
2526 printf("%s: Lock list for ino %ju on dev <%s>:\n",
2527 tag, (uintmax_t)lock->lf_inode->i_number,
2528 devtoname(lock->lf_inode->i_dev));
2529 LIST_FOREACH(lf, &lock->lf_vnode->v_lockf->ls_active, lf_link) {
2530 printf("\tlock %p for ",(void *)lf);
2531 lf_print_owner(lock->lf_owner);
2532 printf(", %s, start %jd, end %jd",
2533 lf->lf_type == F_RDLCK ? "shared" :
2534 lf->lf_type == F_WRLCK ? "exclusive" :
2535 lf->lf_type == F_UNLCK ? "unlock" :
2536 "unknown", (intmax_t)lf->lf_start, (intmax_t)lf->lf_end);
2537 LIST_FOREACH(e, &lf->lf_outedges, le_outlink) {
2538 blk = e->le_to;
2539 printf("\n\t\tlock request %p for ", (void *)blk);
2540 lf_print_owner(blk->lf_owner);
2541 printf(", %s, start %jd, end %jd",
2542 blk->lf_type == F_RDLCK ? "shared" :
2543 blk->lf_type == F_WRLCK ? "exclusive" :
2544 blk->lf_type == F_UNLCK ? "unlock" :
2545 "unknown", (intmax_t)blk->lf_start,
2546 (intmax_t)blk->lf_end);
2547 if (!LIST_EMPTY(&blk->lf_inedges))
2548 panic("lf_printlist: bad list");
2549 }
2550 printf("\n");
2551 }
2552 }
2553 #endif /* LOCKF_DEBUG */
Cache object: c514e86eebf63df703f690167b008f62
|