1139804Simp/*- 2177633Sdfr * Copyright (c) 2008 Isilon Inc http://www.isilon.com/ 3177633Sdfr * Authors: Doug Rabson <dfr@rabson.org> 4177633Sdfr * Developed with Red Inc: Alfred Perlstein <alfred@freebsd.org> 5177633Sdfr * 6177633Sdfr * Redistribution and use in source and binary forms, with or without 7177633Sdfr * modification, are permitted provided that the following conditions 8177633Sdfr * are met: 9177633Sdfr * 1. Redistributions of source code must retain the above copyright 10177633Sdfr * notice, this list of conditions and the following disclaimer. 11177633Sdfr * 2. Redistributions in binary form must reproduce the above copyright 12177633Sdfr * notice, this list of conditions and the following disclaimer in the 13177633Sdfr * documentation and/or other materials provided with the distribution. 14177633Sdfr * 15177633Sdfr * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16177633Sdfr * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17177633Sdfr * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18177633Sdfr * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19177633Sdfr * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20177633Sdfr * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21177633Sdfr * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22177633Sdfr * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23177633Sdfr * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24177633Sdfr * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25177633Sdfr * SUCH DAMAGE. 26177633Sdfr */ 27177633Sdfr/*- 281960Sdg * Copyright (c) 1982, 1986, 1989, 1993 291960Sdg * The Regents of the University of California. All rights reserved. 301960Sdg * 311960Sdg * This code is derived from software contributed to Berkeley by 321960Sdg * Scooter Morris at Genentech Inc. 331960Sdg * 341960Sdg * Redistribution and use in source and binary forms, with or without 351960Sdg * modification, are permitted provided that the following conditions 361960Sdg * are met: 371960Sdg * 1. Redistributions of source code must retain the above copyright 381960Sdg * notice, this list of conditions and the following disclaimer. 391960Sdg * 2. Redistributions in binary form must reproduce the above copyright 401960Sdg * notice, this list of conditions and the following disclaimer in the 411960Sdg * documentation and/or other materials provided with the distribution. 421960Sdg * 4. Neither the name of the University nor the names of its contributors 431960Sdg * may be used to endorse or promote products derived from this software 441960Sdg * without specific prior written permission. 451960Sdg * 461960Sdg * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 471960Sdg * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 481960Sdg * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 491960Sdg * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 501960Sdg * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 511960Sdg * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 521960Sdg * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 531960Sdg * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 541960Sdg * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 551960Sdg * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 561960Sdg * SUCH DAMAGE. 571960Sdg * 581960Sdg * @(#)ufs_lockf.c 8.3 (Berkeley) 1/6/94 591960Sdg */ 601960Sdg 61116182Sobrien#include <sys/cdefs.h> 62116182Sobrien__FBSDID("$FreeBSD$"); 63116182Sobrien 6432929Seivind#include "opt_debug_lockf.h" 6532929Seivind 661960Sdg#include <sys/param.h> 671960Sdg#include <sys/systm.h> 68177633Sdfr#include <sys/hash.h> 6941059Speter#include <sys/kernel.h> 70114216Skan#include <sys/limits.h> 7131561Sbde#include <sys/lock.h> 72101778Sphk#include <sys/mount.h> 7376166Smarkm#include <sys/mutex.h> 741960Sdg#include <sys/proc.h> 75177633Sdfr#include <sys/sx.h> 7618020Sbde#include <sys/unistd.h> 771960Sdg#include <sys/vnode.h> 781960Sdg#include <sys/malloc.h> 791960Sdg#include <sys/fcntl.h> 801960Sdg#include <sys/lockf.h> 81177633Sdfr#include <sys/taskqueue.h> 821960Sdg 831960Sdg#ifdef LOCKF_DEBUG 8422880Sbde#include <sys/sysctl.h> 8522880Sbde 8622880Sbde#include <ufs/ufs/quota.h> 8722880Sbde#include <ufs/ufs/inode.h> 8822880Sbde 89177633Sdfrstatic int lockf_debug = 0; /* control debug output */ 9024481SbdeSYSCTL_INT(_debug, OID_AUTO, lockf_debug, CTLFLAG_RW, &lockf_debug, 0, ""); 911960Sdg#endif 921960Sdg 93249132Smavstatic MALLOC_DEFINE(M_LOCKF, "lockf", "Byte-range locking structures"); 9430309Sphk 95177633Sdfrstruct owner_edge; 96177633Sdfrstruct owner_vertex; 97177633Sdfrstruct owner_vertex_list; 98177633Sdfrstruct owner_graph; 99177633Sdfr 100177633Sdfr#define NOLOCKF (struct lockf_entry *)0 1011960Sdg#define SELF 0x1 1021960Sdg#define OTHERS 0x2 103177633Sdfrstatic void lf_init(void *); 104177633Sdfrstatic int lf_hash_owner(caddr_t, struct flock *, int); 105177633Sdfrstatic int lf_owner_matches(struct lock_owner *, caddr_t, struct flock *, 106177633Sdfr int); 107177633Sdfrstatic struct lockf_entry * 108177633Sdfr lf_alloc_lock(struct lock_owner *); 109192685Skibstatic int lf_free_lock(struct lockf_entry *); 110177633Sdfrstatic int lf_clearlock(struct lockf *, struct lockf_entry *); 111177633Sdfrstatic int lf_overlaps(struct lockf_entry *, struct lockf_entry *); 112177633Sdfrstatic int lf_blocks(struct lockf_entry *, struct lockf_entry *); 113177633Sdfrstatic void lf_free_edge(struct lockf_edge *); 114177633Sdfrstatic struct lockf_edge * 115177633Sdfr lf_alloc_edge(void); 116177633Sdfrstatic void lf_alloc_vertex(struct lockf_entry *); 117177633Sdfrstatic int lf_add_edge(struct lockf_entry *, struct lockf_entry *); 118177633Sdfrstatic void lf_remove_edge(struct lockf_edge *); 119177633Sdfrstatic void lf_remove_outgoing(struct lockf_entry *); 120177633Sdfrstatic void lf_remove_incoming(struct lockf_entry *); 121177633Sdfrstatic int lf_add_outgoing(struct lockf *, struct lockf_entry *); 122177633Sdfrstatic int lf_add_incoming(struct lockf *, struct lockf_entry *); 123177633Sdfrstatic int lf_findoverlap(struct lockf_entry **, struct lockf_entry *, 124177633Sdfr int); 125177633Sdfrstatic struct lockf_entry * 126177633Sdfr lf_getblock(struct lockf *, struct lockf_entry *); 127177633Sdfrstatic int lf_getlock(struct lockf *, struct lockf_entry *, struct flock *); 128177633Sdfrstatic void lf_insert_lock(struct lockf *, struct lockf_entry *); 129177633Sdfrstatic void lf_wakeup_lock(struct lockf *, struct lockf_entry *); 130177633Sdfrstatic void lf_update_dependancies(struct lockf *, struct lockf_entry *, 131177633Sdfr int all, struct lockf_entry_list *); 132177633Sdfrstatic void lf_set_start(struct lockf *, struct lockf_entry *, off_t, 133177633Sdfr struct lockf_entry_list*); 134177633Sdfrstatic void lf_set_end(struct lockf *, struct lockf_entry *, off_t, 135177633Sdfr struct lockf_entry_list*); 136177633Sdfrstatic int lf_setlock(struct lockf *, struct lockf_entry *, 137177633Sdfr struct vnode *, void **cookiep); 138177633Sdfrstatic int lf_cancel(struct lockf *, struct lockf_entry *, void *); 139177633Sdfrstatic void lf_split(struct lockf *, struct lockf_entry *, 140177633Sdfr struct lockf_entry *, struct lockf_entry_list *); 141140808Sjeff#ifdef LOCKF_DEBUG 142177633Sdfrstatic int graph_reaches(struct owner_vertex *x, struct owner_vertex *y, 143177633Sdfr struct owner_vertex_list *path); 144177633Sdfrstatic void graph_check(struct owner_graph *g, int checkorder); 145177633Sdfrstatic void graph_print_vertices(struct owner_vertex_list *set); 146140808Sjeff#endif 147177633Sdfrstatic int graph_delta_forward(struct owner_graph *g, 148177633Sdfr struct owner_vertex *x, struct owner_vertex *y, 149177633Sdfr struct owner_vertex_list *delta); 150177633Sdfrstatic int graph_delta_backward(struct owner_graph *g, 151177633Sdfr struct owner_vertex *x, struct owner_vertex *y, 152177633Sdfr struct owner_vertex_list *delta); 153177633Sdfrstatic int graph_add_indices(int *indices, int n, 154177633Sdfr struct owner_vertex_list *set); 155177633Sdfrstatic int graph_assign_indices(struct owner_graph *g, int *indices, 156177633Sdfr int nextunused, struct owner_vertex_list *set); 157177633Sdfrstatic int graph_add_edge(struct owner_graph *g, 158177633Sdfr struct owner_vertex *x, struct owner_vertex *y); 159177633Sdfrstatic void graph_remove_edge(struct owner_graph *g, 160177633Sdfr struct owner_vertex *x, struct owner_vertex *y); 161177633Sdfrstatic struct owner_vertex *graph_alloc_vertex(struct owner_graph *g, 162177633Sdfr struct lock_owner *lo); 163177633Sdfrstatic void graph_free_vertex(struct owner_graph *g, 164177633Sdfr struct owner_vertex *v); 165177633Sdfrstatic struct owner_graph * graph_init(struct owner_graph *g); 166177633Sdfr#ifdef LOCKF_DEBUG 167177633Sdfrstatic void lf_print(char *, struct lockf_entry *); 168177633Sdfrstatic void lf_printlist(char *, struct lockf_entry *); 169177633Sdfrstatic void lf_print_owner(struct lock_owner *); 170177633Sdfr#endif 1711960Sdg 1721960Sdg/* 173177633Sdfr * This structure is used to keep track of both local and remote lock 174177633Sdfr * owners. The lf_owner field of the struct lockf_entry points back at 175177633Sdfr * the lock owner structure. Each possible lock owner (local proc for 176177633Sdfr * POSIX fcntl locks, local file for BSD flock locks or <pid,sysid> 177177633Sdfr * pair for remote locks) is represented by a unique instance of 178177633Sdfr * struct lock_owner. 179177633Sdfr * 180177633Sdfr * If a lock owner has a lock that blocks some other lock or a lock 181177633Sdfr * that is waiting for some other lock, it also has a vertex in the 182177633Sdfr * owner_graph below. 183177633Sdfr * 184177633Sdfr * Locks: 185177633Sdfr * (s) locked by state->ls_lock 186177633Sdfr * (S) locked by lf_lock_states_lock 187177633Sdfr * (l) locked by lf_lock_owners_lock 188177633Sdfr * (g) locked by lf_owner_graph_lock 189177633Sdfr * (c) const until freeing 190177633Sdfr */ 191177633Sdfr#define LOCK_OWNER_HASH_SIZE 256 192177633Sdfr 193177633Sdfrstruct lock_owner { 194177633Sdfr LIST_ENTRY(lock_owner) lo_link; /* (l) hash chain */ 195177633Sdfr int lo_refs; /* (l) Number of locks referring to this */ 196177633Sdfr int lo_flags; /* (c) Flags passwd to lf_advlock */ 197177633Sdfr caddr_t lo_id; /* (c) Id value passed to lf_advlock */ 198177633Sdfr pid_t lo_pid; /* (c) Process Id of the lock owner */ 199177633Sdfr int lo_sysid; /* (c) System Id of the lock owner */ 200177633Sdfr struct owner_vertex *lo_vertex; /* (g) entry in deadlock graph */ 201177633Sdfr}; 202177633Sdfr 203177633SdfrLIST_HEAD(lock_owner_list, lock_owner); 204177633Sdfr 205177633Sdfrstatic struct sx lf_lock_states_lock; 206177633Sdfrstatic struct lockf_list lf_lock_states; /* (S) */ 207177633Sdfrstatic struct sx lf_lock_owners_lock; 208177633Sdfrstatic struct lock_owner_list lf_lock_owners[LOCK_OWNER_HASH_SIZE]; /* (l) */ 209177633Sdfr 210177633Sdfr/* 211177633Sdfr * Structures for deadlock detection. 212177633Sdfr * 213177633Sdfr * We have two types of directed graph, the first is the set of locks, 214177633Sdfr * both active and pending on a vnode. Within this graph, active locks 215177633Sdfr * are terminal nodes in the graph (i.e. have no out-going 216177633Sdfr * edges). Pending locks have out-going edges to each blocking active 217177633Sdfr * lock that prevents the lock from being granted and also to each 218177633Sdfr * older pending lock that would block them if it was active. The 219177633Sdfr * graph for each vnode is naturally acyclic; new edges are only ever 220177633Sdfr * added to or from new nodes (either new pending locks which only add 221177633Sdfr * out-going edges or new active locks which only add in-coming edges) 222177633Sdfr * therefore they cannot create loops in the lock graph. 223177633Sdfr * 224177633Sdfr * The second graph is a global graph of lock owners. Each lock owner 225177633Sdfr * is a vertex in that graph and an edge is added to the graph 226177633Sdfr * whenever an edge is added to a vnode graph, with end points 227177633Sdfr * corresponding to owner of the new pending lock and the owner of the 228177633Sdfr * lock upon which it waits. In order to prevent deadlock, we only add 229177633Sdfr * an edge to this graph if the new edge would not create a cycle. 230177633Sdfr * 231177633Sdfr * The lock owner graph is topologically sorted, i.e. if a node has 232177633Sdfr * any outgoing edges, then it has an order strictly less than any 233177633Sdfr * node to which it has an outgoing edge. We preserve this ordering 234177633Sdfr * (and detect cycles) on edge insertion using Algorithm PK from the 235177633Sdfr * paper "A Dynamic Topological Sort Algorithm for Directed Acyclic 236177633Sdfr * Graphs" (ACM Journal of Experimental Algorithms, Vol 11, Article 237177633Sdfr * No. 1.7) 238177633Sdfr */ 239177633Sdfrstruct owner_vertex; 240177633Sdfr 241177633Sdfrstruct owner_edge { 242177633Sdfr LIST_ENTRY(owner_edge) e_outlink; /* (g) link from's out-edge list */ 243177633Sdfr LIST_ENTRY(owner_edge) e_inlink; /* (g) link to's in-edge list */ 244177633Sdfr int e_refs; /* (g) number of times added */ 245177633Sdfr struct owner_vertex *e_from; /* (c) out-going from here */ 246177633Sdfr struct owner_vertex *e_to; /* (c) in-coming to here */ 247177633Sdfr}; 248177633SdfrLIST_HEAD(owner_edge_list, owner_edge); 249177633Sdfr 250177633Sdfrstruct owner_vertex { 251177633Sdfr TAILQ_ENTRY(owner_vertex) v_link; /* (g) workspace for edge insertion */ 252177633Sdfr uint32_t v_gen; /* (g) workspace for edge insertion */ 253177633Sdfr int v_order; /* (g) order of vertex in graph */ 254177633Sdfr struct owner_edge_list v_outedges;/* (g) list of out-edges */ 255177633Sdfr struct owner_edge_list v_inedges; /* (g) list of in-edges */ 256177633Sdfr struct lock_owner *v_owner; /* (c) corresponding lock owner */ 257177633Sdfr}; 258177633SdfrTAILQ_HEAD(owner_vertex_list, owner_vertex); 259177633Sdfr 260177633Sdfrstruct owner_graph { 261177633Sdfr struct owner_vertex** g_vertices; /* (g) pointers to vertices */ 262177633Sdfr int g_size; /* (g) number of vertices */ 263177633Sdfr int g_space; /* (g) space allocated for vertices */ 264177633Sdfr int *g_indexbuf; /* (g) workspace for loop detection */ 265177633Sdfr uint32_t g_gen; /* (g) increment when re-ordering */ 266177633Sdfr}; 267177633Sdfr 268177633Sdfrstatic struct sx lf_owner_graph_lock; 269177633Sdfrstatic struct owner_graph lf_owner_graph; 270177633Sdfr 271177633Sdfr/* 272177633Sdfr * Initialise various structures and locks. 273177633Sdfr */ 274177633Sdfrstatic void 275177633Sdfrlf_init(void *dummy) 276177633Sdfr{ 277177633Sdfr int i; 278177633Sdfr 279177633Sdfr sx_init(&lf_lock_states_lock, "lock states lock"); 280177633Sdfr LIST_INIT(&lf_lock_states); 281177633Sdfr 282177633Sdfr sx_init(&lf_lock_owners_lock, "lock owners lock"); 283177633Sdfr for (i = 0; i < LOCK_OWNER_HASH_SIZE; i++) 284177633Sdfr LIST_INIT(&lf_lock_owners[i]); 285177633Sdfr 286177633Sdfr sx_init(&lf_owner_graph_lock, "owner graph lock"); 287177633Sdfr graph_init(&lf_owner_graph); 288177633Sdfr} 289177633SdfrSYSINIT(lf_init, SI_SUB_LOCK, SI_ORDER_FIRST, lf_init, NULL); 290177633Sdfr 291177633Sdfr/* 292177633Sdfr * Generate a hash value for a lock owner. 293177633Sdfr */ 294177633Sdfrstatic int 295177633Sdfrlf_hash_owner(caddr_t id, struct flock *fl, int flags) 296177633Sdfr{ 297177633Sdfr uint32_t h; 298177633Sdfr 299177633Sdfr if (flags & F_REMOTE) { 300177633Sdfr h = HASHSTEP(0, fl->l_pid); 301177633Sdfr h = HASHSTEP(h, fl->l_sysid); 302177633Sdfr } else if (flags & F_FLOCK) { 303177633Sdfr h = ((uintptr_t) id) >> 7; 304177633Sdfr } else { 305177633Sdfr struct proc *p = (struct proc *) id; 306177633Sdfr h = HASHSTEP(0, p->p_pid); 307177633Sdfr h = HASHSTEP(h, 0); 308177633Sdfr } 309177633Sdfr 310177633Sdfr return (h % LOCK_OWNER_HASH_SIZE); 311177633Sdfr} 312177633Sdfr 313177633Sdfr/* 314177633Sdfr * Return true if a lock owner matches the details passed to 315177633Sdfr * lf_advlock. 316177633Sdfr */ 317177633Sdfrstatic int 318177633Sdfrlf_owner_matches(struct lock_owner *lo, caddr_t id, struct flock *fl, 319177633Sdfr int flags) 320177633Sdfr{ 321177633Sdfr if (flags & F_REMOTE) { 322177633Sdfr return lo->lo_pid == fl->l_pid 323177633Sdfr && lo->lo_sysid == fl->l_sysid; 324177633Sdfr } else { 325177633Sdfr return lo->lo_id == id; 326177633Sdfr } 327177633Sdfr} 328177633Sdfr 329177633Sdfrstatic struct lockf_entry * 330177633Sdfrlf_alloc_lock(struct lock_owner *lo) 331177633Sdfr{ 332177633Sdfr struct lockf_entry *lf; 333177633Sdfr 334177633Sdfr lf = malloc(sizeof(struct lockf_entry), M_LOCKF, M_WAITOK|M_ZERO); 335177633Sdfr 336177633Sdfr#ifdef LOCKF_DEBUG 337177633Sdfr if (lockf_debug & 4) 338177633Sdfr printf("Allocated lock %p\n", lf); 339177633Sdfr#endif 340177633Sdfr if (lo) { 341177633Sdfr sx_xlock(&lf_lock_owners_lock); 342177633Sdfr lo->lo_refs++; 343177633Sdfr sx_xunlock(&lf_lock_owners_lock); 344177633Sdfr lf->lf_owner = lo; 345177633Sdfr } 346177633Sdfr 347177633Sdfr return (lf); 348177633Sdfr} 349177633Sdfr 350192685Skibstatic int 351177633Sdfrlf_free_lock(struct lockf_entry *lock) 352177633Sdfr{ 353192685Skib 354192685Skib KASSERT(lock->lf_refs > 0, ("lockf_entry negative ref count %p", lock)); 355192685Skib if (--lock->lf_refs > 0) 356192685Skib return (0); 357177633Sdfr /* 358177633Sdfr * Adjust the lock_owner reference count and 359177633Sdfr * reclaim the entry if this is the last lock 360177633Sdfr * for that owner. 361177633Sdfr */ 362177633Sdfr struct lock_owner *lo = lock->lf_owner; 363177633Sdfr if (lo) { 364177633Sdfr KASSERT(LIST_EMPTY(&lock->lf_outedges), 365177633Sdfr ("freeing lock with dependancies")); 366177633Sdfr KASSERT(LIST_EMPTY(&lock->lf_inedges), 367177633Sdfr ("freeing lock with dependants")); 368177633Sdfr sx_xlock(&lf_lock_owners_lock); 369177633Sdfr KASSERT(lo->lo_refs > 0, ("lock owner refcount")); 370177633Sdfr lo->lo_refs--; 371177633Sdfr if (lo->lo_refs == 0) { 372177633Sdfr#ifdef LOCKF_DEBUG 373177633Sdfr if (lockf_debug & 1) 374177633Sdfr printf("lf_free_lock: freeing lock owner %p\n", 375177633Sdfr lo); 376177633Sdfr#endif 377177633Sdfr if (lo->lo_vertex) { 378177633Sdfr sx_xlock(&lf_owner_graph_lock); 379177633Sdfr graph_free_vertex(&lf_owner_graph, 380177633Sdfr lo->lo_vertex); 381177633Sdfr sx_xunlock(&lf_owner_graph_lock); 382177633Sdfr } 383177633Sdfr LIST_REMOVE(lo, lo_link); 384177633Sdfr free(lo, M_LOCKF); 385177633Sdfr#ifdef LOCKF_DEBUG 386177633Sdfr if (lockf_debug & 4) 387177633Sdfr printf("Freed lock owner %p\n", lo); 388177633Sdfr#endif 389177633Sdfr } 390177633Sdfr sx_unlock(&lf_lock_owners_lock); 391177633Sdfr } 392177633Sdfr if ((lock->lf_flags & F_REMOTE) && lock->lf_vnode) { 393177633Sdfr vrele(lock->lf_vnode); 394177633Sdfr lock->lf_vnode = NULL; 395177633Sdfr } 396177633Sdfr#ifdef LOCKF_DEBUG 397177633Sdfr if (lockf_debug & 4) 398177633Sdfr printf("Freed lock %p\n", lock); 399177633Sdfr#endif 400177633Sdfr free(lock, M_LOCKF); 401192685Skib return (1); 402177633Sdfr} 403177633Sdfr 404177633Sdfr/* 4051960Sdg * Advisory record locking support 4061960Sdg */ 4071960Sdgint 408177633Sdfrlf_advlockasync(struct vop_advlockasync_args *ap, struct lockf **statep, 409177633Sdfr u_quad_t size) 4101960Sdg{ 411177633Sdfr struct lockf *state, *freestate = NULL; 412171193Sjeff struct flock *fl = ap->a_fl; 413177633Sdfr struct lockf_entry *lock; 414171193Sjeff struct vnode *vp = ap->a_vp; 415177633Sdfr caddr_t id = ap->a_id; 416177633Sdfr int flags = ap->a_flags; 417177633Sdfr int hash; 418177633Sdfr struct lock_owner *lo; 41982346Sache off_t start, end, oadd; 4201960Sdg int error; 4211960Sdg 4221960Sdg /* 423177633Sdfr * Handle the F_UNLKSYS case first - no need to mess about 424177633Sdfr * creating a lock owner for this one. 425177633Sdfr */ 426177633Sdfr if (ap->a_op == F_UNLCKSYS) { 427177633Sdfr lf_clearremotesys(fl->l_sysid); 428177633Sdfr return (0); 429177633Sdfr } 430177633Sdfr 431177633Sdfr /* 4321960Sdg * Convert the flock structure into a start and end. 4331960Sdg */ 4341960Sdg switch (fl->l_whence) { 4351960Sdg 4361960Sdg case SEEK_SET: 4371960Sdg case SEEK_CUR: 4381960Sdg /* 4391960Sdg * Caller is responsible for adding any necessary offset 4401960Sdg * when SEEK_CUR is used. 4411960Sdg */ 4421960Sdg start = fl->l_start; 4431960Sdg break; 4441960Sdg 4451960Sdg case SEEK_END: 44682516Sache if (size > OFF_MAX || 447171193Sjeff (fl->l_start > 0 && size > OFF_MAX - fl->l_start)) 448171193Sjeff return (EOVERFLOW); 4491960Sdg start = size + fl->l_start; 4501960Sdg break; 4511960Sdg 4521960Sdg default: 453171193Sjeff return (EINVAL); 4541960Sdg } 455171193Sjeff if (start < 0) 456171193Sjeff return (EINVAL); 45782200Sache if (fl->l_len < 0) { 458171193Sjeff if (start == 0) 459171193Sjeff return (EINVAL); 46082202Sache end = start - 1; 46182200Sache start += fl->l_len; 462171193Sjeff if (start < 0) 463171193Sjeff return (EINVAL); 464177633Sdfr } else if (fl->l_len == 0) { 465177633Sdfr end = OFF_MAX; 466177633Sdfr } else { 46782346Sache oadd = fl->l_len - 1; 468171193Sjeff if (oadd > OFF_MAX - start) 469171193Sjeff return (EOVERFLOW); 47082172Sache end = start + oadd; 47120676Sbde } 4721960Sdg /* 47320676Sbde * Avoid the common case of unlocking when inode has no locks. 47420676Sbde */ 475184227Sdfr VI_LOCK(vp); 476184227Sdfr if ((*statep) == NULL) { 47720676Sbde if (ap->a_op != F_SETLK) { 47820676Sbde fl->l_type = F_UNLCK; 479184227Sdfr VI_UNLOCK(vp); 480171193Sjeff return (0); 48120676Sbde } 48220676Sbde } 483184227Sdfr VI_UNLOCK(vp); 484177633Sdfr 48520676Sbde /* 486177633Sdfr * Map our arguments to an existing lock owner or create one 487177633Sdfr * if this is the first time we have seen this owner. 488171193Sjeff */ 489177633Sdfr hash = lf_hash_owner(id, fl, flags); 490177633Sdfr sx_xlock(&lf_lock_owners_lock); 491177633Sdfr LIST_FOREACH(lo, &lf_lock_owners[hash], lo_link) 492177633Sdfr if (lf_owner_matches(lo, id, fl, flags)) 493177633Sdfr break; 494177633Sdfr if (!lo) { 495177633Sdfr /* 496177633Sdfr * We initialise the lock with a reference 497177633Sdfr * count which matches the new lockf_entry 498177633Sdfr * structure created below. 499177633Sdfr */ 500177633Sdfr lo = malloc(sizeof(struct lock_owner), M_LOCKF, 501177633Sdfr M_WAITOK|M_ZERO); 502177633Sdfr#ifdef LOCKF_DEBUG 503177633Sdfr if (lockf_debug & 4) 504177633Sdfr printf("Allocated lock owner %p\n", lo); 505177633Sdfr#endif 506177633Sdfr 507177633Sdfr lo->lo_refs = 1; 508177633Sdfr lo->lo_flags = flags; 509177633Sdfr lo->lo_id = id; 510177633Sdfr if (flags & F_REMOTE) { 511177633Sdfr lo->lo_pid = fl->l_pid; 512177633Sdfr lo->lo_sysid = fl->l_sysid; 513177633Sdfr } else if (flags & F_FLOCK) { 514177633Sdfr lo->lo_pid = -1; 515177633Sdfr lo->lo_sysid = 0; 516177633Sdfr } else { 517177633Sdfr struct proc *p = (struct proc *) id; 518177633Sdfr lo->lo_pid = p->p_pid; 519177633Sdfr lo->lo_sysid = 0; 520177633Sdfr } 521177633Sdfr lo->lo_vertex = NULL; 522177633Sdfr 523177633Sdfr#ifdef LOCKF_DEBUG 524177633Sdfr if (lockf_debug & 1) { 525177633Sdfr printf("lf_advlockasync: new lock owner %p ", lo); 526177633Sdfr lf_print_owner(lo); 527177633Sdfr printf("\n"); 528177633Sdfr } 529177633Sdfr#endif 530177633Sdfr 531177633Sdfr LIST_INSERT_HEAD(&lf_lock_owners[hash], lo, lo_link); 532177633Sdfr } else { 533177633Sdfr /* 534177633Sdfr * We have seen this lock owner before, increase its 535177633Sdfr * reference count to account for the new lockf_entry 536177633Sdfr * structure we create below. 537177633Sdfr */ 538177633Sdfr lo->lo_refs++; 539171772Skib } 540177633Sdfr sx_xunlock(&lf_lock_owners_lock); 541177633Sdfr 542171193Sjeff /* 543177633Sdfr * Create the lockf structure. We initialise the lf_owner 544177633Sdfr * field here instead of in lf_alloc_lock() to avoid paying 545177633Sdfr * the lf_lock_owners_lock tax twice. 5461960Sdg */ 547177633Sdfr lock = lf_alloc_lock(NULL); 548192685Skib lock->lf_refs = 1; 5491960Sdg lock->lf_start = start; 5501960Sdg lock->lf_end = end; 551177633Sdfr lock->lf_owner = lo; 552177633Sdfr lock->lf_vnode = vp; 553177633Sdfr if (flags & F_REMOTE) { 554177633Sdfr /* 555177633Sdfr * For remote locks, the caller may release its ref to 556177633Sdfr * the vnode at any time - we have to ref it here to 557177633Sdfr * prevent it from being recycled unexpectedly. 558177633Sdfr */ 559177633Sdfr vref(vp); 560177633Sdfr } 561177633Sdfr 56287211Salfred /* 56387211Salfred * XXX The problem is that VTOI is ufs specific, so it will 56487211Salfred * break LOCKF_DEBUG for all other FS's other than UFS because 56587211Salfred * it casts the vnode->data ptr to struct inode *. 56687211Salfred */ 56787211Salfred/* lock->lf_inode = VTOI(ap->a_vp); */ 56887211Salfred lock->lf_inode = (struct inode *)0; 56922521Sdyson lock->lf_type = fl->l_type; 570177633Sdfr LIST_INIT(&lock->lf_outedges); 571177633Sdfr LIST_INIT(&lock->lf_inedges); 572177633Sdfr lock->lf_async_task = ap->a_task; 5731960Sdg lock->lf_flags = ap->a_flags; 574177633Sdfr 5751960Sdg /* 576177633Sdfr * Do the requested operation. First find our state structure 577177633Sdfr * and create a new one if necessary - the caller's *statep 578177633Sdfr * variable and the state's ls_threads count is protected by 579177633Sdfr * the vnode interlock. 5801960Sdg */ 581171193Sjeff VI_LOCK(vp); 582178243Skib if (vp->v_iflag & VI_DOOMED) { 583178243Skib VI_UNLOCK(vp); 584178243Skib lf_free_lock(lock); 585178243Skib return (ENOENT); 586178243Skib } 587177633Sdfr 588177633Sdfr /* 589177633Sdfr * Allocate a state structure if necessary. 590177633Sdfr */ 591177633Sdfr state = *statep; 592177633Sdfr if (state == NULL) { 593177633Sdfr struct lockf *ls; 594177633Sdfr 595177633Sdfr VI_UNLOCK(vp); 596177633Sdfr 597177633Sdfr ls = malloc(sizeof(struct lockf), M_LOCKF, M_WAITOK|M_ZERO); 598177633Sdfr sx_init(&ls->ls_lock, "ls_lock"); 599177633Sdfr LIST_INIT(&ls->ls_active); 600177633Sdfr LIST_INIT(&ls->ls_pending); 601177841Sdfr ls->ls_threads = 1; 602177633Sdfr 603177633Sdfr sx_xlock(&lf_lock_states_lock); 604177633Sdfr LIST_INSERT_HEAD(&lf_lock_states, ls, ls_link); 605177633Sdfr sx_xunlock(&lf_lock_states_lock); 606177633Sdfr 607177633Sdfr /* 608177633Sdfr * Cope if we lost a race with some other thread while 609177633Sdfr * trying to allocate memory. 610177633Sdfr */ 611177633Sdfr VI_LOCK(vp); 612178243Skib if (vp->v_iflag & VI_DOOMED) { 613178243Skib VI_UNLOCK(vp); 614178243Skib sx_xlock(&lf_lock_states_lock); 615178243Skib LIST_REMOVE(ls, ls_link); 616178243Skib sx_xunlock(&lf_lock_states_lock); 617178243Skib sx_destroy(&ls->ls_lock); 618178243Skib free(ls, M_LOCKF); 619178243Skib lf_free_lock(lock); 620178243Skib return (ENOENT); 621178243Skib } 622177633Sdfr if ((*statep) == NULL) { 623177841Sdfr state = *statep = ls; 624177841Sdfr VI_UNLOCK(vp); 625177633Sdfr } else { 626177841Sdfr state = *statep; 627177841Sdfr state->ls_threads++; 628177841Sdfr VI_UNLOCK(vp); 629177841Sdfr 630177633Sdfr sx_xlock(&lf_lock_states_lock); 631177633Sdfr LIST_REMOVE(ls, ls_link); 632177633Sdfr sx_xunlock(&lf_lock_states_lock); 633177633Sdfr sx_destroy(&ls->ls_lock); 634177633Sdfr free(ls, M_LOCKF); 635177633Sdfr } 636177841Sdfr } else { 637177841Sdfr state->ls_threads++; 638177841Sdfr VI_UNLOCK(vp); 639177633Sdfr } 640177633Sdfr 641177633Sdfr sx_xlock(&state->ls_lock); 642192683Skib /* 643192683Skib * Recheck the doomed vnode after state->ls_lock is 644192683Skib * locked. lf_purgelocks() requires that no new threads add 645192683Skib * pending locks when vnode is marked by VI_DOOMED flag. 646192683Skib */ 647192683Skib VI_LOCK(vp); 648192683Skib if (vp->v_iflag & VI_DOOMED) { 649194356Skib state->ls_threads--; 650194356Skib wakeup(state); 651192683Skib VI_UNLOCK(vp); 652193931Skib sx_xunlock(&state->ls_lock); 653192683Skib lf_free_lock(lock); 654192683Skib return (ENOENT); 655192683Skib } 656192683Skib VI_UNLOCK(vp); 657192683Skib 658192683Skib switch (ap->a_op) { 6591960Sdg case F_SETLK: 660177633Sdfr error = lf_setlock(state, lock, vp, ap->a_cookiep); 661171193Sjeff break; 6621960Sdg 6631960Sdg case F_UNLCK: 664177633Sdfr error = lf_clearlock(state, lock); 665177633Sdfr lf_free_lock(lock); 666171193Sjeff break; 6671960Sdg 6681960Sdg case F_GETLK: 669177633Sdfr error = lf_getlock(state, lock, fl); 670177633Sdfr lf_free_lock(lock); 671171193Sjeff break; 6728876Srgrimes 673177633Sdfr case F_CANCEL: 674177633Sdfr if (ap->a_cookiep) 675177633Sdfr error = lf_cancel(state, lock, *ap->a_cookiep); 676177633Sdfr else 677177633Sdfr error = EINVAL; 678177633Sdfr lf_free_lock(lock); 679177633Sdfr break; 680177633Sdfr 6811960Sdg default: 682177633Sdfr lf_free_lock(lock); 683140808Sjeff error = EINVAL; 684171193Sjeff break; 6851960Sdg } 686177633Sdfr 687177633Sdfr#ifdef INVARIANTS 688177633Sdfr /* 689177633Sdfr * Check for some can't happen stuff. In this case, the active 690177633Sdfr * lock list becoming disordered or containing mutually 691177633Sdfr * blocking locks. We also check the pending list for locks 692177633Sdfr * which should be active (i.e. have no out-going edges). 693177633Sdfr */ 694177633Sdfr LIST_FOREACH(lock, &state->ls_active, lf_link) { 695177633Sdfr struct lockf_entry *lf; 696177633Sdfr if (LIST_NEXT(lock, lf_link)) 697177633Sdfr KASSERT((lock->lf_start 698177633Sdfr <= LIST_NEXT(lock, lf_link)->lf_start), 699177633Sdfr ("locks disordered")); 700177633Sdfr LIST_FOREACH(lf, &state->ls_active, lf_link) { 701177633Sdfr if (lock == lf) 702177633Sdfr break; 703177633Sdfr KASSERT(!lf_blocks(lock, lf), 704177633Sdfr ("two conflicting active locks")); 705177633Sdfr if (lock->lf_owner == lf->lf_owner) 706177633Sdfr KASSERT(!lf_overlaps(lock, lf), 707177633Sdfr ("two overlapping locks from same owner")); 708177633Sdfr } 709177633Sdfr } 710177633Sdfr LIST_FOREACH(lock, &state->ls_pending, lf_link) { 711177633Sdfr KASSERT(!LIST_EMPTY(&lock->lf_outedges), 712177633Sdfr ("pending lock which should be active")); 713177633Sdfr } 714177633Sdfr#endif 715177633Sdfr sx_xunlock(&state->ls_lock); 716177633Sdfr 717177633Sdfr /* 718177633Sdfr * If we have removed the last active lock on the vnode and 719177633Sdfr * this is the last thread that was in-progress, we can free 720177633Sdfr * the state structure. We update the caller's pointer inside 721177633Sdfr * the vnode interlock but call free outside. 722177633Sdfr * 723177633Sdfr * XXX alternatively, keep the state structure around until 724177633Sdfr * the filesystem recycles - requires a callback from the 725177633Sdfr * filesystem. 726177633Sdfr */ 727177633Sdfr VI_LOCK(vp); 728177633Sdfr 729177633Sdfr state->ls_threads--; 730178243Skib wakeup(state); 731177633Sdfr if (LIST_EMPTY(&state->ls_active) && state->ls_threads == 0) { 732177633Sdfr KASSERT(LIST_EMPTY(&state->ls_pending), 733177633Sdfr ("freeing state with pending locks")); 734177633Sdfr freestate = state; 735177633Sdfr *statep = NULL; 736177633Sdfr } 737177633Sdfr 738171193Sjeff VI_UNLOCK(vp); 739177633Sdfr 740177633Sdfr if (freestate) { 741177633Sdfr sx_xlock(&lf_lock_states_lock); 742177633Sdfr LIST_REMOVE(freestate, ls_link); 743177633Sdfr sx_xunlock(&lf_lock_states_lock); 744177633Sdfr sx_destroy(&freestate->ls_lock); 745177633Sdfr free(freestate, M_LOCKF); 746171772Skib } 747140808Sjeff return (error); 7481960Sdg} 7491960Sdg 750177633Sdfrint 751177633Sdfrlf_advlock(struct vop_advlock_args *ap, struct lockf **statep, u_quad_t size) 752177633Sdfr{ 753177633Sdfr struct vop_advlockasync_args a; 754177633Sdfr 755177633Sdfr a.a_vp = ap->a_vp; 756177633Sdfr a.a_id = ap->a_id; 757177633Sdfr a.a_op = ap->a_op; 758177633Sdfr a.a_fl = ap->a_fl; 759177633Sdfr a.a_flags = ap->a_flags; 760177633Sdfr a.a_task = NULL; 761177633Sdfr a.a_cookiep = NULL; 762177633Sdfr 763177633Sdfr return (lf_advlockasync(&a, statep, size)); 764177633Sdfr} 765177633Sdfr 766178243Skibvoid 767178243Skiblf_purgelocks(struct vnode *vp, struct lockf **statep) 768178243Skib{ 769178243Skib struct lockf *state; 770178243Skib struct lockf_entry *lock, *nlock; 771178243Skib 772178243Skib /* 773178243Skib * For this to work correctly, the caller must ensure that no 774178243Skib * other threads enter the locking system for this vnode, 775178243Skib * e.g. by checking VI_DOOMED. We wake up any threads that are 776178243Skib * sleeping waiting for locks on this vnode and then free all 777178243Skib * the remaining locks. 778178243Skib */ 779178243Skib VI_LOCK(vp); 780192683Skib KASSERT(vp->v_iflag & VI_DOOMED, 781192683Skib ("lf_purgelocks: vp %p has not vgone yet", vp)); 782178243Skib state = *statep; 783178243Skib if (state) { 784192683Skib *statep = NULL; 785178243Skib state->ls_threads++; 786178243Skib VI_UNLOCK(vp); 787178243Skib 788178243Skib sx_xlock(&state->ls_lock); 789178243Skib sx_xlock(&lf_owner_graph_lock); 790178243Skib LIST_FOREACH_SAFE(lock, &state->ls_pending, lf_link, nlock) { 791178243Skib LIST_REMOVE(lock, lf_link); 792178243Skib lf_remove_outgoing(lock); 793178243Skib lf_remove_incoming(lock); 794178243Skib 795178243Skib /* 796178243Skib * If its an async lock, we can just free it 797178243Skib * here, otherwise we let the sleeping thread 798178243Skib * free it. 799178243Skib */ 800178243Skib if (lock->lf_async_task) { 801178243Skib lf_free_lock(lock); 802178243Skib } else { 803178243Skib lock->lf_flags |= F_INTR; 804178243Skib wakeup(lock); 805178243Skib } 806178243Skib } 807178243Skib sx_xunlock(&lf_owner_graph_lock); 808178243Skib sx_xunlock(&state->ls_lock); 809178243Skib 810178243Skib /* 811178243Skib * Wait for all other threads, sleeping and otherwise 812178243Skib * to leave. 813178243Skib */ 814178243Skib VI_LOCK(vp); 815178243Skib while (state->ls_threads > 1) 816178243Skib msleep(state, VI_MTX(vp), 0, "purgelocks", 0); 817178243Skib VI_UNLOCK(vp); 818178243Skib 819178243Skib /* 820178243Skib * We can just free all the active locks since they 821178243Skib * will have no dependancies (we removed them all 822178243Skib * above). We don't need to bother locking since we 823178243Skib * are the last thread using this state structure. 824178243Skib */ 825192684Skib KASSERT(LIST_EMPTY(&state->ls_pending), 826192684Skib ("lock pending for %p", state)); 827192684Skib LIST_FOREACH_SAFE(lock, &state->ls_active, lf_link, nlock) { 828178243Skib LIST_REMOVE(lock, lf_link); 829178243Skib lf_free_lock(lock); 830178243Skib } 831178243Skib sx_xlock(&lf_lock_states_lock); 832178243Skib LIST_REMOVE(state, ls_link); 833178243Skib sx_xunlock(&lf_lock_states_lock); 834178243Skib sx_destroy(&state->ls_lock); 835178243Skib free(state, M_LOCKF); 836178243Skib } else { 837178243Skib VI_UNLOCK(vp); 838178243Skib } 839178243Skib} 840178243Skib 8411960Sdg/* 842177633Sdfr * Return non-zero if locks 'x' and 'y' overlap. 843177633Sdfr */ 844177633Sdfrstatic int 845177633Sdfrlf_overlaps(struct lockf_entry *x, struct lockf_entry *y) 846177633Sdfr{ 847177633Sdfr 848177633Sdfr return (x->lf_start <= y->lf_end && x->lf_end >= y->lf_start); 849177633Sdfr} 850177633Sdfr 851177633Sdfr/* 852177633Sdfr * Return non-zero if lock 'x' is blocked by lock 'y' (or vice versa). 853177633Sdfr */ 854177633Sdfrstatic int 855177633Sdfrlf_blocks(struct lockf_entry *x, struct lockf_entry *y) 856177633Sdfr{ 857177633Sdfr 858177633Sdfr return x->lf_owner != y->lf_owner 859177633Sdfr && (x->lf_type == F_WRLCK || y->lf_type == F_WRLCK) 860177633Sdfr && lf_overlaps(x, y); 861177633Sdfr} 862177633Sdfr 863177633Sdfr/* 864177633Sdfr * Allocate a lock edge from the free list 865177633Sdfr */ 866177633Sdfrstatic struct lockf_edge * 867177633Sdfrlf_alloc_edge(void) 868177633Sdfr{ 869177633Sdfr 870177633Sdfr return (malloc(sizeof(struct lockf_edge), M_LOCKF, M_WAITOK|M_ZERO)); 871177633Sdfr} 872177633Sdfr 873177633Sdfr/* 874177633Sdfr * Free a lock edge. 875177633Sdfr */ 876177633Sdfrstatic void 877177633Sdfrlf_free_edge(struct lockf_edge *e) 878177633Sdfr{ 879177633Sdfr 880177633Sdfr free(e, M_LOCKF); 881177633Sdfr} 882177633Sdfr 883177633Sdfr 884177633Sdfr/* 885177633Sdfr * Ensure that the lock's owner has a corresponding vertex in the 886177633Sdfr * owner graph. 887177633Sdfr */ 888177633Sdfrstatic void 889177633Sdfrlf_alloc_vertex(struct lockf_entry *lock) 890177633Sdfr{ 891177633Sdfr struct owner_graph *g = &lf_owner_graph; 892177633Sdfr 893177633Sdfr if (!lock->lf_owner->lo_vertex) 894177633Sdfr lock->lf_owner->lo_vertex = 895177633Sdfr graph_alloc_vertex(g, lock->lf_owner); 896177633Sdfr} 897177633Sdfr 898177633Sdfr/* 899177633Sdfr * Attempt to record an edge from lock x to lock y. Return EDEADLK if 900177633Sdfr * the new edge would cause a cycle in the owner graph. 901177633Sdfr */ 902177633Sdfrstatic int 903177633Sdfrlf_add_edge(struct lockf_entry *x, struct lockf_entry *y) 904177633Sdfr{ 905177633Sdfr struct owner_graph *g = &lf_owner_graph; 906177633Sdfr struct lockf_edge *e; 907177633Sdfr int error; 908177633Sdfr 909177633Sdfr#ifdef INVARIANTS 910177633Sdfr LIST_FOREACH(e, &x->lf_outedges, le_outlink) 911177633Sdfr KASSERT(e->le_to != y, ("adding lock edge twice")); 912177633Sdfr#endif 913177633Sdfr 914177633Sdfr /* 915177633Sdfr * Make sure the two owners have entries in the owner graph. 916177633Sdfr */ 917177633Sdfr lf_alloc_vertex(x); 918177633Sdfr lf_alloc_vertex(y); 919177633Sdfr 920177633Sdfr error = graph_add_edge(g, x->lf_owner->lo_vertex, 921177633Sdfr y->lf_owner->lo_vertex); 922177633Sdfr if (error) 923177633Sdfr return (error); 924177633Sdfr 925177633Sdfr e = lf_alloc_edge(); 926177633Sdfr LIST_INSERT_HEAD(&x->lf_outedges, e, le_outlink); 927177633Sdfr LIST_INSERT_HEAD(&y->lf_inedges, e, le_inlink); 928177633Sdfr e->le_from = x; 929177633Sdfr e->le_to = y; 930177633Sdfr 931177633Sdfr return (0); 932177633Sdfr} 933177633Sdfr 934177633Sdfr/* 935177633Sdfr * Remove an edge from the lock graph. 936177633Sdfr */ 937177633Sdfrstatic void 938177633Sdfrlf_remove_edge(struct lockf_edge *e) 939177633Sdfr{ 940177633Sdfr struct owner_graph *g = &lf_owner_graph; 941177633Sdfr struct lockf_entry *x = e->le_from; 942177633Sdfr struct lockf_entry *y = e->le_to; 943177633Sdfr 944177633Sdfr graph_remove_edge(g, x->lf_owner->lo_vertex, y->lf_owner->lo_vertex); 945177633Sdfr LIST_REMOVE(e, le_outlink); 946177633Sdfr LIST_REMOVE(e, le_inlink); 947177633Sdfr e->le_from = NULL; 948177633Sdfr e->le_to = NULL; 949177633Sdfr lf_free_edge(e); 950177633Sdfr} 951177633Sdfr 952177633Sdfr/* 953177633Sdfr * Remove all out-going edges from lock x. 954177633Sdfr */ 955177633Sdfrstatic void 956177633Sdfrlf_remove_outgoing(struct lockf_entry *x) 957177633Sdfr{ 958177633Sdfr struct lockf_edge *e; 959177633Sdfr 960177633Sdfr while ((e = LIST_FIRST(&x->lf_outedges)) != NULL) { 961177633Sdfr lf_remove_edge(e); 962177633Sdfr } 963177633Sdfr} 964177633Sdfr 965177633Sdfr/* 966177633Sdfr * Remove all in-coming edges from lock x. 967177633Sdfr */ 968177633Sdfrstatic void 969177633Sdfrlf_remove_incoming(struct lockf_entry *x) 970177633Sdfr{ 971177633Sdfr struct lockf_edge *e; 972177633Sdfr 973177633Sdfr while ((e = LIST_FIRST(&x->lf_inedges)) != NULL) { 974177633Sdfr lf_remove_edge(e); 975177633Sdfr } 976177633Sdfr} 977177633Sdfr 978177633Sdfr/* 979177633Sdfr * Walk the list of locks for the file and create an out-going edge 980177633Sdfr * from lock to each blocking lock. 981177633Sdfr */ 982177633Sdfrstatic int 983177633Sdfrlf_add_outgoing(struct lockf *state, struct lockf_entry *lock) 984177633Sdfr{ 985177633Sdfr struct lockf_entry *overlap; 986177633Sdfr int error; 987177633Sdfr 988177633Sdfr LIST_FOREACH(overlap, &state->ls_active, lf_link) { 989177633Sdfr /* 990177633Sdfr * We may assume that the active list is sorted by 991177633Sdfr * lf_start. 992177633Sdfr */ 993177633Sdfr if (overlap->lf_start > lock->lf_end) 994177633Sdfr break; 995177633Sdfr if (!lf_blocks(lock, overlap)) 996177633Sdfr continue; 997177633Sdfr 998177633Sdfr /* 999177633Sdfr * We've found a blocking lock. Add the corresponding 1000177633Sdfr * edge to the graphs and see if it would cause a 1001177633Sdfr * deadlock. 1002177633Sdfr */ 1003177633Sdfr error = lf_add_edge(lock, overlap); 1004177633Sdfr 1005177633Sdfr /* 1006177633Sdfr * The only error that lf_add_edge returns is EDEADLK. 1007177633Sdfr * Remove any edges we added and return the error. 1008177633Sdfr */ 1009177633Sdfr if (error) { 1010177633Sdfr lf_remove_outgoing(lock); 1011177633Sdfr return (error); 1012177633Sdfr } 1013177633Sdfr } 1014177633Sdfr 1015177633Sdfr /* 1016177633Sdfr * We also need to add edges to sleeping locks that block 1017177633Sdfr * us. This ensures that lf_wakeup_lock cannot grant two 1018177633Sdfr * mutually blocking locks simultaneously and also enforces a 1019177633Sdfr * 'first come, first served' fairness model. Note that this 1020177633Sdfr * only happens if we are blocked by at least one active lock 1021177633Sdfr * due to the call to lf_getblock in lf_setlock below. 1022177633Sdfr */ 1023177633Sdfr LIST_FOREACH(overlap, &state->ls_pending, lf_link) { 1024177633Sdfr if (!lf_blocks(lock, overlap)) 1025177633Sdfr continue; 1026177633Sdfr /* 1027177633Sdfr * We've found a blocking lock. Add the corresponding 1028177633Sdfr * edge to the graphs and see if it would cause a 1029177633Sdfr * deadlock. 1030177633Sdfr */ 1031177633Sdfr error = lf_add_edge(lock, overlap); 1032177633Sdfr 1033177633Sdfr /* 1034177633Sdfr * The only error that lf_add_edge returns is EDEADLK. 1035177633Sdfr * Remove any edges we added and return the error. 1036177633Sdfr */ 1037177633Sdfr if (error) { 1038177633Sdfr lf_remove_outgoing(lock); 1039177633Sdfr return (error); 1040177633Sdfr } 1041177633Sdfr } 1042177633Sdfr 1043177633Sdfr return (0); 1044177633Sdfr} 1045177633Sdfr 1046177633Sdfr/* 1047177633Sdfr * Walk the list of pending locks for the file and create an in-coming 1048177633Sdfr * edge from lock to each blocking lock. 1049177633Sdfr */ 1050177633Sdfrstatic int 1051177633Sdfrlf_add_incoming(struct lockf *state, struct lockf_entry *lock) 1052177633Sdfr{ 1053177633Sdfr struct lockf_entry *overlap; 1054177633Sdfr int error; 1055177633Sdfr 1056177633Sdfr LIST_FOREACH(overlap, &state->ls_pending, lf_link) { 1057177633Sdfr if (!lf_blocks(lock, overlap)) 1058177633Sdfr continue; 1059177633Sdfr 1060177633Sdfr /* 1061177633Sdfr * We've found a blocking lock. Add the corresponding 1062177633Sdfr * edge to the graphs and see if it would cause a 1063177633Sdfr * deadlock. 1064177633Sdfr */ 1065177633Sdfr error = lf_add_edge(overlap, lock); 1066177633Sdfr 1067177633Sdfr /* 1068177633Sdfr * The only error that lf_add_edge returns is EDEADLK. 1069177633Sdfr * Remove any edges we added and return the error. 1070177633Sdfr */ 1071177633Sdfr if (error) { 1072177633Sdfr lf_remove_incoming(lock); 1073177633Sdfr return (error); 1074177633Sdfr } 1075177633Sdfr } 1076177633Sdfr return (0); 1077177633Sdfr} 1078177633Sdfr 1079177633Sdfr/* 1080177633Sdfr * Insert lock into the active list, keeping list entries ordered by 1081177633Sdfr * increasing values of lf_start. 1082177633Sdfr */ 1083177633Sdfrstatic void 1084177633Sdfrlf_insert_lock(struct lockf *state, struct lockf_entry *lock) 1085177633Sdfr{ 1086177633Sdfr struct lockf_entry *lf, *lfprev; 1087177633Sdfr 1088177633Sdfr if (LIST_EMPTY(&state->ls_active)) { 1089177633Sdfr LIST_INSERT_HEAD(&state->ls_active, lock, lf_link); 1090177633Sdfr return; 1091177633Sdfr } 1092177633Sdfr 1093177633Sdfr lfprev = NULL; 1094177633Sdfr LIST_FOREACH(lf, &state->ls_active, lf_link) { 1095177633Sdfr if (lf->lf_start > lock->lf_start) { 1096177633Sdfr LIST_INSERT_BEFORE(lf, lock, lf_link); 1097177633Sdfr return; 1098177633Sdfr } 1099177633Sdfr lfprev = lf; 1100177633Sdfr } 1101177633Sdfr LIST_INSERT_AFTER(lfprev, lock, lf_link); 1102177633Sdfr} 1103177633Sdfr 1104177633Sdfr/* 1105177633Sdfr * Wake up a sleeping lock and remove it from the pending list now 1106177633Sdfr * that all its dependancies have been resolved. The caller should 1107177633Sdfr * arrange for the lock to be added to the active list, adjusting any 1108177633Sdfr * existing locks for the same owner as needed. 1109177633Sdfr */ 1110177633Sdfrstatic void 1111177633Sdfrlf_wakeup_lock(struct lockf *state, struct lockf_entry *wakelock) 1112177633Sdfr{ 1113177633Sdfr 1114177633Sdfr /* 1115177633Sdfr * Remove from ls_pending list and wake up the caller 1116177633Sdfr * or start the async notification, as appropriate. 1117177633Sdfr */ 1118177633Sdfr LIST_REMOVE(wakelock, lf_link); 1119177633Sdfr#ifdef LOCKF_DEBUG 1120177633Sdfr if (lockf_debug & 1) 1121177633Sdfr lf_print("lf_wakeup_lock: awakening", wakelock); 1122177633Sdfr#endif /* LOCKF_DEBUG */ 1123177633Sdfr if (wakelock->lf_async_task) { 1124177633Sdfr taskqueue_enqueue(taskqueue_thread, wakelock->lf_async_task); 1125177633Sdfr } else { 1126177633Sdfr wakeup(wakelock); 1127177633Sdfr } 1128177633Sdfr} 1129177633Sdfr 1130177633Sdfr/* 1131177633Sdfr * Re-check all dependant locks and remove edges to locks that we no 1132177633Sdfr * longer block. If 'all' is non-zero, the lock has been removed and 1133177633Sdfr * we must remove all the dependancies, otherwise it has simply been 1134177633Sdfr * reduced but remains active. Any pending locks which have been been 1135177633Sdfr * unblocked are added to 'granted' 1136177633Sdfr */ 1137177633Sdfrstatic void 1138177633Sdfrlf_update_dependancies(struct lockf *state, struct lockf_entry *lock, int all, 1139177633Sdfr struct lockf_entry_list *granted) 1140177633Sdfr{ 1141177633Sdfr struct lockf_edge *e, *ne; 1142177633Sdfr struct lockf_entry *deplock; 1143177633Sdfr 1144177633Sdfr LIST_FOREACH_SAFE(e, &lock->lf_inedges, le_inlink, ne) { 1145177633Sdfr deplock = e->le_from; 1146177633Sdfr if (all || !lf_blocks(lock, deplock)) { 1147177633Sdfr sx_xlock(&lf_owner_graph_lock); 1148177633Sdfr lf_remove_edge(e); 1149177633Sdfr sx_xunlock(&lf_owner_graph_lock); 1150177633Sdfr if (LIST_EMPTY(&deplock->lf_outedges)) { 1151177633Sdfr lf_wakeup_lock(state, deplock); 1152177633Sdfr LIST_INSERT_HEAD(granted, deplock, lf_link); 1153177633Sdfr } 1154177633Sdfr } 1155177633Sdfr } 1156177633Sdfr} 1157177633Sdfr 1158177633Sdfr/* 1159177633Sdfr * Set the start of an existing active lock, updating dependancies and 1160177633Sdfr * adding any newly woken locks to 'granted'. 1161177633Sdfr */ 1162177633Sdfrstatic void 1163177633Sdfrlf_set_start(struct lockf *state, struct lockf_entry *lock, off_t new_start, 1164177633Sdfr struct lockf_entry_list *granted) 1165177633Sdfr{ 1166177633Sdfr 1167177633Sdfr KASSERT(new_start >= lock->lf_start, ("can't increase lock")); 1168177633Sdfr lock->lf_start = new_start; 1169177633Sdfr LIST_REMOVE(lock, lf_link); 1170177633Sdfr lf_insert_lock(state, lock); 1171177633Sdfr lf_update_dependancies(state, lock, FALSE, granted); 1172177633Sdfr} 1173177633Sdfr 1174177633Sdfr/* 1175177633Sdfr * Set the end of an existing active lock, updating dependancies and 1176177633Sdfr * adding any newly woken locks to 'granted'. 1177177633Sdfr */ 1178177633Sdfrstatic void 1179177633Sdfrlf_set_end(struct lockf *state, struct lockf_entry *lock, off_t new_end, 1180177633Sdfr struct lockf_entry_list *granted) 1181177633Sdfr{ 1182177633Sdfr 1183177633Sdfr KASSERT(new_end <= lock->lf_end, ("can't increase lock")); 1184177633Sdfr lock->lf_end = new_end; 1185177633Sdfr lf_update_dependancies(state, lock, FALSE, granted); 1186177633Sdfr} 1187177633Sdfr 1188177633Sdfr/* 1189177633Sdfr * Add a lock to the active list, updating or removing any current 1190177633Sdfr * locks owned by the same owner and processing any pending locks that 1191177633Sdfr * become unblocked as a result. This code is also used for unlock 1192177633Sdfr * since the logic for updating existing locks is identical. 1193177633Sdfr * 1194177633Sdfr * As a result of processing the new lock, we may unblock existing 1195177633Sdfr * pending locks as a result of downgrading/unlocking. We simply 1196177633Sdfr * activate the newly granted locks by looping. 1197177633Sdfr * 1198177633Sdfr * Since the new lock already has its dependancies set up, we always 1199177633Sdfr * add it to the list (unless its an unlock request). This may 1200177633Sdfr * fragment the lock list in some pathological cases but its probably 1201177633Sdfr * not a real problem. 1202177633Sdfr */ 1203177633Sdfrstatic void 1204177633Sdfrlf_activate_lock(struct lockf *state, struct lockf_entry *lock) 1205177633Sdfr{ 1206177633Sdfr struct lockf_entry *overlap, *lf; 1207177633Sdfr struct lockf_entry_list granted; 1208177633Sdfr int ovcase; 1209177633Sdfr 1210177633Sdfr LIST_INIT(&granted); 1211177633Sdfr LIST_INSERT_HEAD(&granted, lock, lf_link); 1212177633Sdfr 1213177633Sdfr while (!LIST_EMPTY(&granted)) { 1214177633Sdfr lock = LIST_FIRST(&granted); 1215177633Sdfr LIST_REMOVE(lock, lf_link); 1216177633Sdfr 1217177633Sdfr /* 1218177633Sdfr * Skip over locks owned by other processes. Handle 1219177633Sdfr * any locks that overlap and are owned by ourselves. 1220177633Sdfr */ 1221177633Sdfr overlap = LIST_FIRST(&state->ls_active); 1222177633Sdfr for (;;) { 1223177633Sdfr ovcase = lf_findoverlap(&overlap, lock, SELF); 1224177633Sdfr 1225177633Sdfr#ifdef LOCKF_DEBUG 1226177633Sdfr if (ovcase && (lockf_debug & 2)) { 1227177633Sdfr printf("lf_setlock: overlap %d", ovcase); 1228177633Sdfr lf_print("", overlap); 1229177633Sdfr } 1230177633Sdfr#endif 1231177633Sdfr /* 1232177633Sdfr * Six cases: 1233177633Sdfr * 0) no overlap 1234177633Sdfr * 1) overlap == lock 1235177633Sdfr * 2) overlap contains lock 1236177633Sdfr * 3) lock contains overlap 1237177633Sdfr * 4) overlap starts before lock 1238177633Sdfr * 5) overlap ends after lock 1239177633Sdfr */ 1240177633Sdfr switch (ovcase) { 1241177633Sdfr case 0: /* no overlap */ 1242177633Sdfr break; 1243177633Sdfr 1244177633Sdfr case 1: /* overlap == lock */ 1245177633Sdfr /* 1246177633Sdfr * We have already setup the 1247177633Sdfr * dependants for the new lock, taking 1248177633Sdfr * into account a possible downgrade 1249177633Sdfr * or unlock. Remove the old lock. 1250177633Sdfr */ 1251177633Sdfr LIST_REMOVE(overlap, lf_link); 1252177633Sdfr lf_update_dependancies(state, overlap, TRUE, 1253177633Sdfr &granted); 1254177633Sdfr lf_free_lock(overlap); 1255177633Sdfr break; 1256177633Sdfr 1257177633Sdfr case 2: /* overlap contains lock */ 1258177633Sdfr /* 1259177633Sdfr * Just split the existing lock. 1260177633Sdfr */ 1261177633Sdfr lf_split(state, overlap, lock, &granted); 1262177633Sdfr break; 1263177633Sdfr 1264177633Sdfr case 3: /* lock contains overlap */ 1265177633Sdfr /* 1266177633Sdfr * Delete the overlap and advance to 1267177633Sdfr * the next entry in the list. 1268177633Sdfr */ 1269177633Sdfr lf = LIST_NEXT(overlap, lf_link); 1270177633Sdfr LIST_REMOVE(overlap, lf_link); 1271177633Sdfr lf_update_dependancies(state, overlap, TRUE, 1272177633Sdfr &granted); 1273177633Sdfr lf_free_lock(overlap); 1274177633Sdfr overlap = lf; 1275177633Sdfr continue; 1276177633Sdfr 1277177633Sdfr case 4: /* overlap starts before lock */ 1278177633Sdfr /* 1279177633Sdfr * Just update the overlap end and 1280177633Sdfr * move on. 1281177633Sdfr */ 1282177633Sdfr lf_set_end(state, overlap, lock->lf_start - 1, 1283177633Sdfr &granted); 1284177633Sdfr overlap = LIST_NEXT(overlap, lf_link); 1285177633Sdfr continue; 1286177633Sdfr 1287177633Sdfr case 5: /* overlap ends after lock */ 1288177633Sdfr /* 1289177633Sdfr * Change the start of overlap and 1290177633Sdfr * re-insert. 1291177633Sdfr */ 1292177633Sdfr lf_set_start(state, overlap, lock->lf_end + 1, 1293177633Sdfr &granted); 1294177633Sdfr break; 1295177633Sdfr } 1296177633Sdfr break; 1297177633Sdfr } 1298177633Sdfr#ifdef LOCKF_DEBUG 1299177633Sdfr if (lockf_debug & 1) { 1300177633Sdfr if (lock->lf_type != F_UNLCK) 1301177633Sdfr lf_print("lf_activate_lock: activated", lock); 1302177633Sdfr else 1303177633Sdfr lf_print("lf_activate_lock: unlocked", lock); 1304177633Sdfr lf_printlist("lf_activate_lock", lock); 1305177633Sdfr } 1306177633Sdfr#endif /* LOCKF_DEBUG */ 1307177633Sdfr if (lock->lf_type != F_UNLCK) 1308177633Sdfr lf_insert_lock(state, lock); 1309177633Sdfr } 1310177633Sdfr} 1311177633Sdfr 1312177633Sdfr/* 1313177633Sdfr * Cancel a pending lock request, either as a result of a signal or a 1314177633Sdfr * cancel request for an async lock. 1315177633Sdfr */ 1316177633Sdfrstatic void 1317177633Sdfrlf_cancel_lock(struct lockf *state, struct lockf_entry *lock) 1318177633Sdfr{ 1319177633Sdfr struct lockf_entry_list granted; 1320177633Sdfr 1321177633Sdfr /* 1322177633Sdfr * Note it is theoretically possible that cancelling this lock 1323177633Sdfr * may allow some other pending lock to become 1324177633Sdfr * active. Consider this case: 1325177633Sdfr * 1326177633Sdfr * Owner Action Result Dependancies 1327177633Sdfr * 1328177633Sdfr * A: lock [0..0] succeeds 1329177633Sdfr * B: lock [2..2] succeeds 1330177633Sdfr * C: lock [1..2] blocked C->B 1331177633Sdfr * D: lock [0..1] blocked C->B,D->A,D->C 1332177633Sdfr * A: unlock [0..0] C->B,D->C 1333177633Sdfr * C: cancel [1..2] 1334177633Sdfr */ 1335177633Sdfr 1336177633Sdfr LIST_REMOVE(lock, lf_link); 1337177633Sdfr 1338177633Sdfr /* 1339177633Sdfr * Removing out-going edges is simple. 1340177633Sdfr */ 1341177633Sdfr sx_xlock(&lf_owner_graph_lock); 1342177633Sdfr lf_remove_outgoing(lock); 1343177633Sdfr sx_xunlock(&lf_owner_graph_lock); 1344177633Sdfr 1345177633Sdfr /* 1346177633Sdfr * Removing in-coming edges may allow some other lock to 1347177633Sdfr * become active - we use lf_update_dependancies to figure 1348177633Sdfr * this out. 1349177633Sdfr */ 1350177633Sdfr LIST_INIT(&granted); 1351177633Sdfr lf_update_dependancies(state, lock, TRUE, &granted); 1352177633Sdfr lf_free_lock(lock); 1353177633Sdfr 1354177633Sdfr /* 1355177633Sdfr * Feed any newly active locks to lf_activate_lock. 1356177633Sdfr */ 1357177633Sdfr while (!LIST_EMPTY(&granted)) { 1358177633Sdfr lock = LIST_FIRST(&granted); 1359177633Sdfr LIST_REMOVE(lock, lf_link); 1360177633Sdfr lf_activate_lock(state, lock); 1361177633Sdfr } 1362177633Sdfr} 1363177633Sdfr 1364177633Sdfr/* 13651960Sdg * Set a byte-range lock. 13661960Sdg */ 136712819Sphkstatic int 1368177633Sdfrlf_setlock(struct lockf *state, struct lockf_entry *lock, struct vnode *vp, 1369177633Sdfr void **cookiep) 13701960Sdg{ 13711960Sdg static char lockstr[] = "lockf"; 1372177633Sdfr int priority, error; 13731960Sdg 13741960Sdg#ifdef LOCKF_DEBUG 13751960Sdg if (lockf_debug & 1) 13761960Sdg lf_print("lf_setlock", lock); 13771960Sdg#endif /* LOCKF_DEBUG */ 13781960Sdg 13791960Sdg /* 13801960Sdg * Set the priority 13811960Sdg */ 13821960Sdg priority = PLOCK; 13831960Sdg if (lock->lf_type == F_WRLCK) 13841960Sdg priority += 4; 1385180025Sdfr if (!(lock->lf_flags & F_NOINTR)) 1386180025Sdfr priority |= PCATCH; 13871960Sdg /* 13881960Sdg * Scan lock list for this file looking for locks that would block us. 13891960Sdg */ 1390192681Skib if (lf_getblock(state, lock)) { 13911960Sdg /* 13921960Sdg * Free the structure and return if nonblocking. 13931960Sdg */ 1394177633Sdfr if ((lock->lf_flags & F_WAIT) == 0 1395177633Sdfr && lock->lf_async_task == NULL) { 1396177633Sdfr lf_free_lock(lock); 1397177633Sdfr error = EAGAIN; 1398177633Sdfr goto out; 13991960Sdg } 1400177633Sdfr 14011960Sdg /* 1402178873Sdfr * For flock type locks, we must first remove 1403178873Sdfr * any shared locks that we hold before we sleep 1404178873Sdfr * waiting for an exclusive lock. 1405178873Sdfr */ 1406178873Sdfr if ((lock->lf_flags & F_FLOCK) && 1407178873Sdfr lock->lf_type == F_WRLCK) { 1408178873Sdfr lock->lf_type = F_UNLCK; 1409178873Sdfr lf_activate_lock(state, lock); 1410178873Sdfr lock->lf_type = F_WRLCK; 1411178873Sdfr } 1412178873Sdfr 1413178873Sdfr /* 1414177633Sdfr * We are blocked. Create edges to each blocking lock, 1415177633Sdfr * checking for deadlock using the owner graph. For 1416177633Sdfr * simplicity, we run deadlock detection for all 1417177633Sdfr * locks, posix and otherwise. 14181960Sdg */ 1419177633Sdfr sx_xlock(&lf_owner_graph_lock); 1420177633Sdfr error = lf_add_outgoing(state, lock); 1421177633Sdfr sx_xunlock(&lf_owner_graph_lock); 14221960Sdg 1423177633Sdfr if (error) { 1424177633Sdfr#ifdef LOCKF_DEBUG 1425177633Sdfr if (lockf_debug & 1) 1426177633Sdfr lf_print("lf_setlock: deadlock", lock); 1427177633Sdfr#endif 1428177633Sdfr lf_free_lock(lock); 1429177633Sdfr goto out; 14301960Sdg } 1431177633Sdfr 14321960Sdg /* 1433177633Sdfr * We have added edges to everything that blocks 1434177633Sdfr * us. Sleep until they all go away. 14351960Sdg */ 1436177633Sdfr LIST_INSERT_HEAD(&state->ls_pending, lock, lf_link); 14371960Sdg#ifdef LOCKF_DEBUG 14381960Sdg if (lockf_debug & 1) { 1439177633Sdfr struct lockf_edge *e; 1440177633Sdfr LIST_FOREACH(e, &lock->lf_outedges, le_outlink) { 1441177633Sdfr lf_print("lf_setlock: blocking on", e->le_to); 1442177633Sdfr lf_printlist("lf_setlock", e->le_to); 1443177633Sdfr } 14441960Sdg } 14451960Sdg#endif /* LOCKF_DEBUG */ 1446177633Sdfr 1447177633Sdfr if ((lock->lf_flags & F_WAIT) == 0) { 1448177633Sdfr /* 1449177633Sdfr * The caller requested async notification - 1450177633Sdfr * this callback happens when the blocking 1451177633Sdfr * lock is released, allowing the caller to 1452177633Sdfr * make another attempt to take the lock. 1453177633Sdfr */ 1454177633Sdfr *cookiep = (void *) lock; 1455177633Sdfr error = EINPROGRESS; 1456177633Sdfr goto out; 1457177633Sdfr } 1458177633Sdfr 1459192685Skib lock->lf_refs++; 1460177633Sdfr error = sx_sleep(lock, &state->ls_lock, priority, lockstr, 0); 1461192685Skib if (lf_free_lock(lock)) { 1462192685Skib error = EINTR; 1463192685Skib goto out; 1464192685Skib } 1465192685Skib 146648556Sbde /* 146748556Sbde * We may have been awakened by a signal and/or by a 1468177633Sdfr * debugger continuing us (in which cases we must 1469177633Sdfr * remove our lock graph edges) and/or by another 1470177633Sdfr * process releasing a lock (in which case our edges 1471177633Sdfr * have already been removed and we have been moved to 1472178243Skib * the active list). We may also have been woken by 1473178243Skib * lf_purgelocks which we report to the caller as 1474178243Skib * EINTR. In that case, lf_purgelocks will have 1475178243Skib * removed our lock graph edges. 1476177633Sdfr * 1477177633Sdfr * Note that it is possible to receive a signal after 1478177633Sdfr * we were successfully woken (and moved to the active 1479177633Sdfr * list) but before we resumed execution. In this 1480177633Sdfr * case, our lf_outedges list will be clear. We 1481177633Sdfr * pretend there was no error. 1482177633Sdfr * 1483177633Sdfr * Note also, if we have been sleeping long enough, we 1484177633Sdfr * may now have incoming edges from some newer lock 1485177633Sdfr * which is waiting behind us in the queue. 148648556Sbde */ 1487178243Skib if (lock->lf_flags & F_INTR) { 1488178243Skib error = EINTR; 1489178243Skib lf_free_lock(lock); 1490178243Skib goto out; 1491178243Skib } 1492177633Sdfr if (LIST_EMPTY(&lock->lf_outedges)) { 1493177633Sdfr error = 0; 1494177633Sdfr } else { 1495177633Sdfr lf_cancel_lock(state, lock); 1496177633Sdfr goto out; 14971960Sdg } 1498177633Sdfr#ifdef LOCKF_DEBUG 1499177633Sdfr if (lockf_debug & 1) { 1500177633Sdfr lf_print("lf_setlock: granted", lock); 150148556Sbde } 1502177633Sdfr#endif 1503177633Sdfr goto out; 15041960Sdg } 15051960Sdg /* 1506177633Sdfr * It looks like we are going to grant the lock. First add 1507177633Sdfr * edges from any currently pending lock that the new lock 1508177633Sdfr * would block. 1509177633Sdfr */ 1510177633Sdfr sx_xlock(&lf_owner_graph_lock); 1511177633Sdfr error = lf_add_incoming(state, lock); 1512177633Sdfr sx_xunlock(&lf_owner_graph_lock); 1513177633Sdfr if (error) { 1514177633Sdfr#ifdef LOCKF_DEBUG 1515177633Sdfr if (lockf_debug & 1) 1516177633Sdfr lf_print("lf_setlock: deadlock", lock); 1517177633Sdfr#endif 1518177633Sdfr lf_free_lock(lock); 1519177633Sdfr goto out; 1520177633Sdfr } 1521177633Sdfr 1522177633Sdfr /* 15231960Sdg * No blocks!! Add the lock. Note that we will 15241960Sdg * downgrade or upgrade any overlapping locks this 15251960Sdg * process already owns. 15261960Sdg */ 1527177633Sdfr lf_activate_lock(state, lock); 1528177633Sdfr error = 0; 1529177633Sdfrout: 1530177633Sdfr return (error); 15311960Sdg} 15321960Sdg 15331960Sdg/* 15341960Sdg * Remove a byte-range lock on an inode. 15351960Sdg * 15361960Sdg * Generally, find the lock (or an overlap to that lock) 15371960Sdg * and remove it (or shrink it), then wakeup anyone we can. 15381960Sdg */ 153912819Sphkstatic int 1540177633Sdfrlf_clearlock(struct lockf *state, struct lockf_entry *unlock) 15411960Sdg{ 1542177633Sdfr struct lockf_entry *overlap; 15431960Sdg 1544177633Sdfr overlap = LIST_FIRST(&state->ls_active); 1545177633Sdfr 1546177633Sdfr if (overlap == NOLOCKF) 15471960Sdg return (0); 15481960Sdg#ifdef LOCKF_DEBUG 15491960Sdg if (unlock->lf_type != F_UNLCK) 15501960Sdg panic("lf_clearlock: bad type"); 15511960Sdg if (lockf_debug & 1) 15521960Sdg lf_print("lf_clearlock", unlock); 15531960Sdg#endif /* LOCKF_DEBUG */ 15541960Sdg 1555177633Sdfr lf_activate_lock(state, unlock); 15561960Sdg 15571960Sdg return (0); 15581960Sdg} 15591960Sdg 15601960Sdg/* 1561177633Sdfr * Check whether there is a blocking lock, and if so return its 1562177633Sdfr * details in '*fl'. 15631960Sdg */ 156412819Sphkstatic int 1565177633Sdfrlf_getlock(struct lockf *state, struct lockf_entry *lock, struct flock *fl) 15661960Sdg{ 1567177633Sdfr struct lockf_entry *block; 15681960Sdg 15691960Sdg#ifdef LOCKF_DEBUG 15701960Sdg if (lockf_debug & 1) 15711960Sdg lf_print("lf_getlock", lock); 15721960Sdg#endif /* LOCKF_DEBUG */ 15731960Sdg 1574177633Sdfr if ((block = lf_getblock(state, lock))) { 15751960Sdg fl->l_type = block->lf_type; 15761960Sdg fl->l_whence = SEEK_SET; 15771960Sdg fl->l_start = block->lf_start; 1578177633Sdfr if (block->lf_end == OFF_MAX) 15791960Sdg fl->l_len = 0; 15801960Sdg else 15811960Sdg fl->l_len = block->lf_end - block->lf_start + 1; 1582177633Sdfr fl->l_pid = block->lf_owner->lo_pid; 1583177633Sdfr fl->l_sysid = block->lf_owner->lo_sysid; 15841960Sdg } else { 15851960Sdg fl->l_type = F_UNLCK; 15861960Sdg } 15871960Sdg return (0); 15881960Sdg} 15891960Sdg 15901960Sdg/* 1591177633Sdfr * Cancel an async lock request. 1592177633Sdfr */ 1593177633Sdfrstatic int 1594177633Sdfrlf_cancel(struct lockf *state, struct lockf_entry *lock, void *cookie) 1595177633Sdfr{ 1596177633Sdfr struct lockf_entry *reallock; 1597177633Sdfr 1598177633Sdfr /* 1599177633Sdfr * We need to match this request with an existing lock 1600177633Sdfr * request. 1601177633Sdfr */ 1602177633Sdfr LIST_FOREACH(reallock, &state->ls_pending, lf_link) { 1603177633Sdfr if ((void *) reallock == cookie) { 1604177633Sdfr /* 1605177633Sdfr * Double-check that this lock looks right 1606177633Sdfr * (maybe use a rolling ID for the cancel 1607177633Sdfr * cookie instead?) 1608177633Sdfr */ 1609177633Sdfr if (!(reallock->lf_vnode == lock->lf_vnode 1610177633Sdfr && reallock->lf_start == lock->lf_start 1611177633Sdfr && reallock->lf_end == lock->lf_end)) { 1612177633Sdfr return (ENOENT); 1613177633Sdfr } 1614177633Sdfr 1615177633Sdfr /* 1616177633Sdfr * Make sure this lock was async and then just 1617177633Sdfr * remove it from its wait lists. 1618177633Sdfr */ 1619177633Sdfr if (!reallock->lf_async_task) { 1620177633Sdfr return (ENOENT); 1621177633Sdfr } 1622177633Sdfr 1623177633Sdfr /* 1624177633Sdfr * Note that since any other thread must take 1625177633Sdfr * state->ls_lock before it can possibly 1626177633Sdfr * trigger the async callback, we are safe 1627177633Sdfr * from a race with lf_wakeup_lock, i.e. we 1628177633Sdfr * can free the lock (actually our caller does 1629177633Sdfr * this). 1630177633Sdfr */ 1631177633Sdfr lf_cancel_lock(state, reallock); 1632177633Sdfr return (0); 1633177633Sdfr } 1634177633Sdfr } 1635177633Sdfr 1636177633Sdfr /* 1637177633Sdfr * We didn't find a matching lock - not much we can do here. 1638177633Sdfr */ 1639177633Sdfr return (ENOENT); 1640177633Sdfr} 1641177633Sdfr 1642177633Sdfr/* 16431960Sdg * Walk the list of locks for an inode and 16441960Sdg * return the first blocking lock. 16451960Sdg */ 1646177633Sdfrstatic struct lockf_entry * 1647177633Sdfrlf_getblock(struct lockf *state, struct lockf_entry *lock) 16481960Sdg{ 1649177633Sdfr struct lockf_entry *overlap; 16501960Sdg 1651177633Sdfr LIST_FOREACH(overlap, &state->ls_active, lf_link) { 16521960Sdg /* 1653177633Sdfr * We may assume that the active list is sorted by 1654177633Sdfr * lf_start. 16551960Sdg */ 1656177633Sdfr if (overlap->lf_start > lock->lf_end) 1657177633Sdfr break; 1658177633Sdfr if (!lf_blocks(lock, overlap)) 1659177633Sdfr continue; 1660177633Sdfr return (overlap); 16611960Sdg } 16621960Sdg return (NOLOCKF); 16631960Sdg} 16641960Sdg 16651960Sdg/* 1666177633Sdfr * Walk the list of locks for an inode to find an overlapping lock (if 1667177633Sdfr * any) and return a classification of that overlap. 16681960Sdg * 1669177633Sdfr * Arguments: 1670177633Sdfr * *overlap The place in the lock list to start looking 1671177633Sdfr * lock The lock which is being tested 1672177633Sdfr * type Pass 'SELF' to test only locks with the same 1673177633Sdfr * owner as lock, or 'OTHER' to test only locks 1674177633Sdfr * with a different owner 1675177633Sdfr * 1676177633Sdfr * Returns one of six values: 1677177633Sdfr * 0) no overlap 1678177633Sdfr * 1) overlap == lock 1679177633Sdfr * 2) overlap contains lock 1680177633Sdfr * 3) lock contains overlap 1681177633Sdfr * 4) overlap starts before lock 1682177633Sdfr * 5) overlap ends after lock 1683177633Sdfr * 1684177633Sdfr * If there is an overlapping lock, '*overlap' is set to point at the 1685177633Sdfr * overlapping lock. 1686177633Sdfr * 16871960Sdg * NOTE: this returns only the FIRST overlapping lock. There 16881960Sdg * may be more than one. 16891960Sdg */ 169012819Sphkstatic int 1691177633Sdfrlf_findoverlap(struct lockf_entry **overlap, struct lockf_entry *lock, int type) 16921960Sdg{ 1693177633Sdfr struct lockf_entry *lf; 16941960Sdg off_t start, end; 1695177633Sdfr int res; 16961960Sdg 1697177633Sdfr if ((*overlap) == NOLOCKF) { 16981960Sdg return (0); 1699177633Sdfr } 17001960Sdg#ifdef LOCKF_DEBUG 17011960Sdg if (lockf_debug & 2) 17021960Sdg lf_print("lf_findoverlap: looking for overlap in", lock); 17031960Sdg#endif /* LOCKF_DEBUG */ 17041960Sdg start = lock->lf_start; 17051960Sdg end = lock->lf_end; 1706177633Sdfr res = 0; 1707177633Sdfr while (*overlap) { 1708177633Sdfr lf = *overlap; 1709177633Sdfr if (lf->lf_start > end) 1710177633Sdfr break; 1711177633Sdfr if (((type & SELF) && lf->lf_owner != lock->lf_owner) || 1712177633Sdfr ((type & OTHERS) && lf->lf_owner == lock->lf_owner)) { 1713177633Sdfr *overlap = LIST_NEXT(lf, lf_link); 17141960Sdg continue; 17151960Sdg } 17161960Sdg#ifdef LOCKF_DEBUG 17171960Sdg if (lockf_debug & 2) 17181960Sdg lf_print("\tchecking", lf); 17191960Sdg#endif /* LOCKF_DEBUG */ 17201960Sdg /* 17211960Sdg * OK, check for overlap 17221960Sdg * 17231960Sdg * Six cases: 17241960Sdg * 0) no overlap 17251960Sdg * 1) overlap == lock 17261960Sdg * 2) overlap contains lock 17271960Sdg * 3) lock contains overlap 17281960Sdg * 4) overlap starts before lock 17291960Sdg * 5) overlap ends after lock 17301960Sdg */ 1731177633Sdfr if (start > lf->lf_end) { 17321960Sdg /* Case 0 */ 17331960Sdg#ifdef LOCKF_DEBUG 17341960Sdg if (lockf_debug & 2) 17351960Sdg printf("no overlap\n"); 17361960Sdg#endif /* LOCKF_DEBUG */ 1737177633Sdfr *overlap = LIST_NEXT(lf, lf_link); 17381960Sdg continue; 17391960Sdg } 1740177633Sdfr if (lf->lf_start == start && lf->lf_end == end) { 17411960Sdg /* Case 1 */ 17421960Sdg#ifdef LOCKF_DEBUG 17431960Sdg if (lockf_debug & 2) 17441960Sdg printf("overlap == lock\n"); 17451960Sdg#endif /* LOCKF_DEBUG */ 1746177633Sdfr res = 1; 1747177633Sdfr break; 17481960Sdg } 1749177633Sdfr if (lf->lf_start <= start && lf->lf_end >= end) { 17501960Sdg /* Case 2 */ 17511960Sdg#ifdef LOCKF_DEBUG 17521960Sdg if (lockf_debug & 2) 17531960Sdg printf("overlap contains lock\n"); 17541960Sdg#endif /* LOCKF_DEBUG */ 1755177633Sdfr res = 2; 1756177633Sdfr break; 17571960Sdg } 1758177633Sdfr if (start <= lf->lf_start && end >= lf->lf_end) { 17591960Sdg /* Case 3 */ 17601960Sdg#ifdef LOCKF_DEBUG 17611960Sdg if (lockf_debug & 2) 17621960Sdg printf("lock contains overlap\n"); 17631960Sdg#endif /* LOCKF_DEBUG */ 1764177633Sdfr res = 3; 1765177633Sdfr break; 17661960Sdg } 1767177633Sdfr if (lf->lf_start < start && lf->lf_end >= start) { 17681960Sdg /* Case 4 */ 17691960Sdg#ifdef LOCKF_DEBUG 17701960Sdg if (lockf_debug & 2) 17711960Sdg printf("overlap starts before lock\n"); 17721960Sdg#endif /* LOCKF_DEBUG */ 1773177633Sdfr res = 4; 1774177633Sdfr break; 17751960Sdg } 1776177633Sdfr if (lf->lf_start > start && lf->lf_end > end) { 17771960Sdg /* Case 5 */ 17781960Sdg#ifdef LOCKF_DEBUG 17791960Sdg if (lockf_debug & 2) 17801960Sdg printf("overlap ends after lock\n"); 17811960Sdg#endif /* LOCKF_DEBUG */ 1782177633Sdfr res = 5; 1783177633Sdfr break; 17841960Sdg } 17851960Sdg panic("lf_findoverlap: default"); 17861960Sdg } 1787177633Sdfr return (res); 17881960Sdg} 17891960Sdg 17901960Sdg/* 1791177633Sdfr * Split an the existing 'lock1', based on the extent of the lock 1792177633Sdfr * described by 'lock2'. The existing lock should cover 'lock2' 1793177633Sdfr * entirely. 1794177633Sdfr * 1795177633Sdfr * Any pending locks which have been been unblocked are added to 1796177633Sdfr * 'granted' 17971960Sdg */ 179812819Sphkstatic void 1799177633Sdfrlf_split(struct lockf *state, struct lockf_entry *lock1, 1800177633Sdfr struct lockf_entry *lock2, struct lockf_entry_list *granted) 18011960Sdg{ 1802177633Sdfr struct lockf_entry *splitlock; 18031960Sdg 18041960Sdg#ifdef LOCKF_DEBUG 18051960Sdg if (lockf_debug & 2) { 18061960Sdg lf_print("lf_split", lock1); 18071960Sdg lf_print("splitting from", lock2); 18081960Sdg } 18091960Sdg#endif /* LOCKF_DEBUG */ 18101960Sdg /* 1811177633Sdfr * Check to see if we don't need to split at all. 18121960Sdg */ 18131960Sdg if (lock1->lf_start == lock2->lf_start) { 1814177633Sdfr lf_set_start(state, lock1, lock2->lf_end + 1, granted); 18151960Sdg return; 18161960Sdg } 18171960Sdg if (lock1->lf_end == lock2->lf_end) { 1818177633Sdfr lf_set_end(state, lock1, lock2->lf_start - 1, granted); 18191960Sdg return; 18201960Sdg } 18211960Sdg /* 18221960Sdg * Make a new lock consisting of the last part of 1823177633Sdfr * the encompassing lock. 18241960Sdg */ 1825177633Sdfr splitlock = lf_alloc_lock(lock1->lf_owner); 1826177633Sdfr memcpy(splitlock, lock1, sizeof *splitlock); 1827192685Skib splitlock->lf_refs = 1; 1828177633Sdfr if (splitlock->lf_flags & F_REMOTE) 1829177633Sdfr vref(splitlock->lf_vnode); 1830177633Sdfr 1831177633Sdfr /* 1832177633Sdfr * This cannot cause a deadlock since any edges we would add 1833177633Sdfr * to splitlock already exist in lock1. We must be sure to add 1834177633Sdfr * necessary dependancies to splitlock before we reduce lock1 1835177633Sdfr * otherwise we may accidentally grant a pending lock that 1836177633Sdfr * was blocked by the tail end of lock1. 1837177633Sdfr */ 18381960Sdg splitlock->lf_start = lock2->lf_end + 1; 1839177633Sdfr LIST_INIT(&splitlock->lf_outedges); 1840177633Sdfr LIST_INIT(&splitlock->lf_inedges); 1841177633Sdfr sx_xlock(&lf_owner_graph_lock); 1842177633Sdfr lf_add_incoming(state, splitlock); 1843177633Sdfr sx_xunlock(&lf_owner_graph_lock); 1844177633Sdfr 1845177633Sdfr lf_set_end(state, lock1, lock2->lf_start - 1, granted); 1846177633Sdfr 18471960Sdg /* 18481960Sdg * OK, now link it in 18491960Sdg */ 1850177633Sdfr lf_insert_lock(state, splitlock); 18511960Sdg} 18521960Sdg 1853180025Sdfrstruct lockdesc { 1854180025Sdfr STAILQ_ENTRY(lockdesc) link; 1855177633Sdfr struct vnode *vp; 1856177633Sdfr struct flock fl; 1857177633Sdfr}; 1858180025SdfrSTAILQ_HEAD(lockdesclist, lockdesc); 1859177633Sdfr 1860180025Sdfrint 1861180025Sdfrlf_iteratelocks_sysid(int sysid, lf_iterator *fn, void *arg) 1862177633Sdfr{ 1863177633Sdfr struct lockf *ls; 1864177633Sdfr struct lockf_entry *lf; 1865180025Sdfr struct lockdesc *ldesc; 1866180025Sdfr struct lockdesclist locks; 1867180025Sdfr int error; 1868177633Sdfr 1869177633Sdfr /* 1870177633Sdfr * In order to keep the locking simple, we iterate over the 1871177633Sdfr * active lock lists to build a list of locks that need 1872180025Sdfr * releasing. We then call the iterator for each one in turn. 1873177633Sdfr * 1874177633Sdfr * We take an extra reference to the vnode for the duration to 1875177633Sdfr * make sure it doesn't go away before we are finished. 1876177633Sdfr */ 1877177633Sdfr STAILQ_INIT(&locks); 1878177633Sdfr sx_xlock(&lf_lock_states_lock); 1879177633Sdfr LIST_FOREACH(ls, &lf_lock_states, ls_link) { 1880177633Sdfr sx_xlock(&ls->ls_lock); 1881177633Sdfr LIST_FOREACH(lf, &ls->ls_active, lf_link) { 1882177633Sdfr if (lf->lf_owner->lo_sysid != sysid) 1883177633Sdfr continue; 1884177633Sdfr 1885180025Sdfr ldesc = malloc(sizeof(struct lockdesc), M_LOCKF, 1886177633Sdfr M_WAITOK); 1887180025Sdfr ldesc->vp = lf->lf_vnode; 1888180025Sdfr vref(ldesc->vp); 1889180025Sdfr ldesc->fl.l_start = lf->lf_start; 1890177633Sdfr if (lf->lf_end == OFF_MAX) 1891180025Sdfr ldesc->fl.l_len = 0; 1892177633Sdfr else 1893180025Sdfr ldesc->fl.l_len = 1894177633Sdfr lf->lf_end - lf->lf_start + 1; 1895180025Sdfr ldesc->fl.l_whence = SEEK_SET; 1896180025Sdfr ldesc->fl.l_type = F_UNLCK; 1897180025Sdfr ldesc->fl.l_pid = lf->lf_owner->lo_pid; 1898180025Sdfr ldesc->fl.l_sysid = sysid; 1899180025Sdfr STAILQ_INSERT_TAIL(&locks, ldesc, link); 1900177633Sdfr } 1901177633Sdfr sx_xunlock(&ls->ls_lock); 1902177633Sdfr } 1903177633Sdfr sx_xunlock(&lf_lock_states_lock); 1904177633Sdfr 1905180025Sdfr /* 1906180025Sdfr * Call the iterator function for each lock in turn. If the 1907180025Sdfr * iterator returns an error code, just free the rest of the 1908180025Sdfr * lockdesc structures. 1909180025Sdfr */ 1910180025Sdfr error = 0; 1911180025Sdfr while ((ldesc = STAILQ_FIRST(&locks)) != NULL) { 1912177633Sdfr STAILQ_REMOVE_HEAD(&locks, link); 1913180025Sdfr if (!error) 1914180025Sdfr error = fn(ldesc->vp, &ldesc->fl, arg); 1915180025Sdfr vrele(ldesc->vp); 1916180025Sdfr free(ldesc, M_LOCKF); 1917177633Sdfr } 1918180025Sdfr 1919180025Sdfr return (error); 1920177633Sdfr} 1921177633Sdfr 1922177633Sdfrint 1923180025Sdfrlf_iteratelocks_vnode(struct vnode *vp, lf_iterator *fn, void *arg) 1924180025Sdfr{ 1925180025Sdfr struct lockf *ls; 1926180025Sdfr struct lockf_entry *lf; 1927180025Sdfr struct lockdesc *ldesc; 1928180025Sdfr struct lockdesclist locks; 1929180025Sdfr int error; 1930180025Sdfr 1931180025Sdfr /* 1932180025Sdfr * In order to keep the locking simple, we iterate over the 1933180025Sdfr * active lock lists to build a list of locks that need 1934180025Sdfr * releasing. We then call the iterator for each one in turn. 1935180025Sdfr * 1936180025Sdfr * We take an extra reference to the vnode for the duration to 1937180025Sdfr * make sure it doesn't go away before we are finished. 1938180025Sdfr */ 1939180025Sdfr STAILQ_INIT(&locks); 1940194993Skib VI_LOCK(vp); 1941180025Sdfr ls = vp->v_lockf; 1942194993Skib if (!ls) { 1943194993Skib VI_UNLOCK(vp); 1944180025Sdfr return (0); 1945194993Skib } 1946194993Skib ls->ls_threads++; 1947194993Skib VI_UNLOCK(vp); 1948180025Sdfr 1949180025Sdfr sx_xlock(&ls->ls_lock); 1950180025Sdfr LIST_FOREACH(lf, &ls->ls_active, lf_link) { 1951180025Sdfr ldesc = malloc(sizeof(struct lockdesc), M_LOCKF, 1952180025Sdfr M_WAITOK); 1953180025Sdfr ldesc->vp = lf->lf_vnode; 1954180025Sdfr vref(ldesc->vp); 1955180025Sdfr ldesc->fl.l_start = lf->lf_start; 1956180025Sdfr if (lf->lf_end == OFF_MAX) 1957180025Sdfr ldesc->fl.l_len = 0; 1958180025Sdfr else 1959180025Sdfr ldesc->fl.l_len = 1960180025Sdfr lf->lf_end - lf->lf_start + 1; 1961180025Sdfr ldesc->fl.l_whence = SEEK_SET; 1962180025Sdfr ldesc->fl.l_type = F_UNLCK; 1963180025Sdfr ldesc->fl.l_pid = lf->lf_owner->lo_pid; 1964180025Sdfr ldesc->fl.l_sysid = lf->lf_owner->lo_sysid; 1965180025Sdfr STAILQ_INSERT_TAIL(&locks, ldesc, link); 1966180025Sdfr } 1967180025Sdfr sx_xunlock(&ls->ls_lock); 1968194993Skib VI_LOCK(vp); 1969194993Skib ls->ls_threads--; 1970194993Skib wakeup(ls); 1971194993Skib VI_UNLOCK(vp); 1972180025Sdfr 1973180025Sdfr /* 1974180025Sdfr * Call the iterator function for each lock in turn. If the 1975180025Sdfr * iterator returns an error code, just free the rest of the 1976180025Sdfr * lockdesc structures. 1977180025Sdfr */ 1978180025Sdfr error = 0; 1979180025Sdfr while ((ldesc = STAILQ_FIRST(&locks)) != NULL) { 1980180025Sdfr STAILQ_REMOVE_HEAD(&locks, link); 1981180025Sdfr if (!error) 1982180025Sdfr error = fn(ldesc->vp, &ldesc->fl, arg); 1983180025Sdfr vrele(ldesc->vp); 1984180025Sdfr free(ldesc, M_LOCKF); 1985180025Sdfr } 1986180025Sdfr 1987180025Sdfr return (error); 1988180025Sdfr} 1989180025Sdfr 1990180025Sdfrstatic int 1991180025Sdfrlf_clearremotesys_iterator(struct vnode *vp, struct flock *fl, void *arg) 1992180025Sdfr{ 1993180025Sdfr 1994180025Sdfr VOP_ADVLOCK(vp, 0, F_UNLCK, fl, F_REMOTE); 1995180025Sdfr return (0); 1996180025Sdfr} 1997180025Sdfr 1998180025Sdfrvoid 1999180025Sdfrlf_clearremotesys(int sysid) 2000180025Sdfr{ 2001180025Sdfr 2002180025Sdfr KASSERT(sysid != 0, ("Can't clear local locks with F_UNLCKSYS")); 2003180025Sdfr lf_iteratelocks_sysid(sysid, lf_clearremotesys_iterator, NULL); 2004180025Sdfr} 2005180025Sdfr 2006180025Sdfrint 2007177633Sdfrlf_countlocks(int sysid) 2008177633Sdfr{ 2009177633Sdfr int i; 2010177633Sdfr struct lock_owner *lo; 2011177633Sdfr int count; 2012177633Sdfr 2013177633Sdfr count = 0; 2014177633Sdfr sx_xlock(&lf_lock_owners_lock); 2015177633Sdfr for (i = 0; i < LOCK_OWNER_HASH_SIZE; i++) 2016177633Sdfr LIST_FOREACH(lo, &lf_lock_owners[i], lo_link) 2017177633Sdfr if (lo->lo_sysid == sysid) 2018177633Sdfr count += lo->lo_refs; 2019177633Sdfr sx_xunlock(&lf_lock_owners_lock); 2020177633Sdfr 2021177633Sdfr return (count); 2022177633Sdfr} 2023177633Sdfr 2024177633Sdfr#ifdef LOCKF_DEBUG 2025177633Sdfr 20261960Sdg/* 2027177633Sdfr * Return non-zero if y is reachable from x using a brute force 2028177633Sdfr * search. If reachable and path is non-null, return the route taken 2029177633Sdfr * in path. 20301960Sdg */ 2031177633Sdfrstatic int 2032177633Sdfrgraph_reaches(struct owner_vertex *x, struct owner_vertex *y, 2033177633Sdfr struct owner_vertex_list *path) 2034177633Sdfr{ 2035177633Sdfr struct owner_edge *e; 2036177633Sdfr 2037177633Sdfr if (x == y) { 2038177633Sdfr if (path) 2039177633Sdfr TAILQ_INSERT_HEAD(path, x, v_link); 2040177633Sdfr return 1; 2041177633Sdfr } 2042177633Sdfr 2043177633Sdfr LIST_FOREACH(e, &x->v_outedges, e_outlink) { 2044177633Sdfr if (graph_reaches(e->e_to, y, path)) { 2045177633Sdfr if (path) 2046177633Sdfr TAILQ_INSERT_HEAD(path, x, v_link); 2047177633Sdfr return 1; 2048177633Sdfr } 2049177633Sdfr } 2050177633Sdfr return 0; 2051177633Sdfr} 2052177633Sdfr 2053177633Sdfr/* 2054177633Sdfr * Perform consistency checks on the graph. Make sure the values of 2055177633Sdfr * v_order are correct. If checkorder is non-zero, check no vertex can 2056177633Sdfr * reach any other vertex with a smaller order. 2057177633Sdfr */ 205812819Sphkstatic void 2059177633Sdfrgraph_check(struct owner_graph *g, int checkorder) 20601960Sdg{ 2061177633Sdfr int i, j; 20621960Sdg 2063177633Sdfr for (i = 0; i < g->g_size; i++) { 2064177633Sdfr if (!g->g_vertices[i]->v_owner) 2065177633Sdfr continue; 2066177633Sdfr KASSERT(g->g_vertices[i]->v_order == i, 2067177633Sdfr ("lock graph vertices disordered")); 2068177633Sdfr if (checkorder) { 2069177633Sdfr for (j = 0; j < i; j++) { 2070177633Sdfr if (!g->g_vertices[j]->v_owner) 2071177633Sdfr continue; 2072177633Sdfr KASSERT(!graph_reaches(g->g_vertices[i], 2073177633Sdfr g->g_vertices[j], NULL), 2074177633Sdfr ("lock graph vertices disordered")); 2075177633Sdfr } 2076177633Sdfr } 2077177633Sdfr } 2078177633Sdfr} 2079177633Sdfr 2080177633Sdfrstatic void 2081177633Sdfrgraph_print_vertices(struct owner_vertex_list *set) 2082177633Sdfr{ 2083177633Sdfr struct owner_vertex *v; 2084177633Sdfr 2085177633Sdfr printf("{ "); 2086177633Sdfr TAILQ_FOREACH(v, set, v_link) { 2087177633Sdfr printf("%d:", v->v_order); 2088177633Sdfr lf_print_owner(v->v_owner); 2089177633Sdfr if (TAILQ_NEXT(v, v_link)) 2090177633Sdfr printf(", "); 2091177633Sdfr } 2092177633Sdfr printf(" }\n"); 2093177633Sdfr} 2094177633Sdfr 2095177633Sdfr#endif 2096177633Sdfr 2097177633Sdfr/* 2098177633Sdfr * Calculate the sub-set of vertices v from the affected region [y..x] 2099177633Sdfr * where v is reachable from y. Return -1 if a loop was detected 2100177633Sdfr * (i.e. x is reachable from y, otherwise the number of vertices in 2101177633Sdfr * this subset. 2102177633Sdfr */ 2103177633Sdfrstatic int 2104177633Sdfrgraph_delta_forward(struct owner_graph *g, struct owner_vertex *x, 2105177633Sdfr struct owner_vertex *y, struct owner_vertex_list *delta) 2106177633Sdfr{ 2107177633Sdfr uint32_t gen; 2108177633Sdfr struct owner_vertex *v; 2109177633Sdfr struct owner_edge *e; 2110177633Sdfr int n; 2111177633Sdfr 2112177633Sdfr /* 2113177633Sdfr * We start with a set containing just y. Then for each vertex 2114177633Sdfr * v in the set so far unprocessed, we add each vertex that v 2115177633Sdfr * has an out-edge to and that is within the affected region 2116177633Sdfr * [y..x]. If we see the vertex x on our travels, stop 2117177633Sdfr * immediately. 2118177633Sdfr */ 2119177633Sdfr TAILQ_INIT(delta); 2120177633Sdfr TAILQ_INSERT_TAIL(delta, y, v_link); 2121177633Sdfr v = y; 2122177633Sdfr n = 1; 2123177633Sdfr gen = g->g_gen; 2124177633Sdfr while (v) { 2125177633Sdfr LIST_FOREACH(e, &v->v_outedges, e_outlink) { 2126177633Sdfr if (e->e_to == x) 2127177633Sdfr return -1; 2128177633Sdfr if (e->e_to->v_order < x->v_order 2129177633Sdfr && e->e_to->v_gen != gen) { 2130177633Sdfr e->e_to->v_gen = gen; 2131177633Sdfr TAILQ_INSERT_TAIL(delta, e->e_to, v_link); 2132177633Sdfr n++; 2133177633Sdfr } 2134177633Sdfr } 2135177633Sdfr v = TAILQ_NEXT(v, v_link); 2136177633Sdfr } 2137177633Sdfr 2138177633Sdfr return (n); 2139177633Sdfr} 2140177633Sdfr 2141177633Sdfr/* 2142177633Sdfr * Calculate the sub-set of vertices v from the affected region [y..x] 2143177633Sdfr * where v reaches x. Return the number of vertices in this subset. 2144177633Sdfr */ 2145177633Sdfrstatic int 2146177633Sdfrgraph_delta_backward(struct owner_graph *g, struct owner_vertex *x, 2147177633Sdfr struct owner_vertex *y, struct owner_vertex_list *delta) 2148177633Sdfr{ 2149177633Sdfr uint32_t gen; 2150177633Sdfr struct owner_vertex *v; 2151177633Sdfr struct owner_edge *e; 2152177633Sdfr int n; 2153177633Sdfr 2154177633Sdfr /* 2155177633Sdfr * We start with a set containing just x. Then for each vertex 2156177633Sdfr * v in the set so far unprocessed, we add each vertex that v 2157177633Sdfr * has an in-edge from and that is within the affected region 2158177633Sdfr * [y..x]. 2159177633Sdfr */ 2160177633Sdfr TAILQ_INIT(delta); 2161177633Sdfr TAILQ_INSERT_TAIL(delta, x, v_link); 2162177633Sdfr v = x; 2163177633Sdfr n = 1; 2164177633Sdfr gen = g->g_gen; 2165177633Sdfr while (v) { 2166177633Sdfr LIST_FOREACH(e, &v->v_inedges, e_inlink) { 2167177633Sdfr if (e->e_from->v_order > y->v_order 2168177633Sdfr && e->e_from->v_gen != gen) { 2169177633Sdfr e->e_from->v_gen = gen; 2170177633Sdfr TAILQ_INSERT_HEAD(delta, e->e_from, v_link); 2171177633Sdfr n++; 2172177633Sdfr } 2173177633Sdfr } 2174177633Sdfr v = TAILQ_PREV(v, owner_vertex_list, v_link); 2175177633Sdfr } 2176177633Sdfr 2177177633Sdfr return (n); 2178177633Sdfr} 2179177633Sdfr 2180177633Sdfrstatic int 2181177633Sdfrgraph_add_indices(int *indices, int n, struct owner_vertex_list *set) 2182177633Sdfr{ 2183177633Sdfr struct owner_vertex *v; 2184177633Sdfr int i, j; 2185177633Sdfr 2186177633Sdfr TAILQ_FOREACH(v, set, v_link) { 2187177633Sdfr for (i = n; 2188177633Sdfr i > 0 && indices[i - 1] > v->v_order; i--) 2189177633Sdfr ; 2190177633Sdfr for (j = n - 1; j >= i; j--) 2191177633Sdfr indices[j + 1] = indices[j]; 2192177633Sdfr indices[i] = v->v_order; 2193177633Sdfr n++; 2194177633Sdfr } 2195177633Sdfr 2196177633Sdfr return (n); 2197177633Sdfr} 2198177633Sdfr 2199177633Sdfrstatic int 2200177633Sdfrgraph_assign_indices(struct owner_graph *g, int *indices, int nextunused, 2201177633Sdfr struct owner_vertex_list *set) 2202177633Sdfr{ 2203177633Sdfr struct owner_vertex *v, *vlowest; 2204177633Sdfr 2205177633Sdfr while (!TAILQ_EMPTY(set)) { 2206177633Sdfr vlowest = NULL; 2207177633Sdfr TAILQ_FOREACH(v, set, v_link) { 2208177633Sdfr if (!vlowest || v->v_order < vlowest->v_order) 2209177633Sdfr vlowest = v; 2210177633Sdfr } 2211177633Sdfr TAILQ_REMOVE(set, vlowest, v_link); 2212177633Sdfr vlowest->v_order = indices[nextunused]; 2213177633Sdfr g->g_vertices[vlowest->v_order] = vlowest; 2214177633Sdfr nextunused++; 2215177633Sdfr } 2216177633Sdfr 2217177633Sdfr return (nextunused); 2218177633Sdfr} 2219177633Sdfr 2220177633Sdfrstatic int 2221177633Sdfrgraph_add_edge(struct owner_graph *g, struct owner_vertex *x, 2222177633Sdfr struct owner_vertex *y) 2223177633Sdfr{ 2224177633Sdfr struct owner_edge *e; 2225177633Sdfr struct owner_vertex_list deltaF, deltaB; 2226177633Sdfr int nF, nB, n, vi, i; 2227177633Sdfr int *indices; 2228177633Sdfr 2229177633Sdfr sx_assert(&lf_owner_graph_lock, SX_XLOCKED); 2230177633Sdfr 2231177633Sdfr LIST_FOREACH(e, &x->v_outedges, e_outlink) { 2232177633Sdfr if (e->e_to == y) { 2233177633Sdfr e->e_refs++; 2234177633Sdfr return (0); 2235177633Sdfr } 2236177633Sdfr } 2237177633Sdfr 22381960Sdg#ifdef LOCKF_DEBUG 2239177633Sdfr if (lockf_debug & 8) { 2240177633Sdfr printf("adding edge %d:", x->v_order); 2241177633Sdfr lf_print_owner(x->v_owner); 2242177633Sdfr printf(" -> %d:", y->v_order); 2243177633Sdfr lf_print_owner(y->v_owner); 2244177633Sdfr printf("\n"); 224522521Sdyson } 2246177633Sdfr#endif 2247177633Sdfr if (y->v_order < x->v_order) { 2248177633Sdfr /* 2249177633Sdfr * The new edge violates the order. First find the set 2250177633Sdfr * of affected vertices reachable from y (deltaF) and 2251177633Sdfr * the set of affect vertices affected that reach x 2252177633Sdfr * (deltaB), using the graph generation number to 2253177633Sdfr * detect whether we have visited a given vertex 2254177633Sdfr * already. We re-order the graph so that each vertex 2255177633Sdfr * in deltaB appears before each vertex in deltaF. 2256177633Sdfr * 2257177633Sdfr * If x is a member of deltaF, then the new edge would 2258177633Sdfr * create a cycle. Otherwise, we may assume that 2259177633Sdfr * deltaF and deltaB are disjoint. 2260177633Sdfr */ 2261177633Sdfr g->g_gen++; 2262177633Sdfr if (g->g_gen == 0) { 2263177633Sdfr /* 2264177633Sdfr * Generation wrap. 2265177633Sdfr */ 2266177633Sdfr for (vi = 0; vi < g->g_size; vi++) { 2267177633Sdfr g->g_vertices[vi]->v_gen = 0; 2268177633Sdfr } 2269177633Sdfr g->g_gen++; 2270177633Sdfr } 2271177633Sdfr nF = graph_delta_forward(g, x, y, &deltaF); 2272177633Sdfr if (nF < 0) { 2273177633Sdfr#ifdef LOCKF_DEBUG 2274177633Sdfr if (lockf_debug & 8) { 2275177633Sdfr struct owner_vertex_list path; 2276177633Sdfr printf("deadlock: "); 2277177633Sdfr TAILQ_INIT(&path); 2278177633Sdfr graph_reaches(y, x, &path); 2279177633Sdfr graph_print_vertices(&path); 2280177633Sdfr } 2281177633Sdfr#endif 2282177633Sdfr return (EDEADLK); 2283177633Sdfr } 2284177633Sdfr 2285177633Sdfr#ifdef LOCKF_DEBUG 2286177633Sdfr if (lockf_debug & 8) { 2287177633Sdfr printf("re-ordering graph vertices\n"); 2288177633Sdfr printf("deltaF = "); 2289177633Sdfr graph_print_vertices(&deltaF); 2290177633Sdfr } 2291177633Sdfr#endif 2292177633Sdfr 2293177633Sdfr nB = graph_delta_backward(g, x, y, &deltaB); 2294177633Sdfr 2295177633Sdfr#ifdef LOCKF_DEBUG 2296177633Sdfr if (lockf_debug & 8) { 2297177633Sdfr printf("deltaB = "); 2298177633Sdfr graph_print_vertices(&deltaB); 2299177633Sdfr } 2300177633Sdfr#endif 2301177633Sdfr 2302177633Sdfr /* 2303177633Sdfr * We first build a set of vertex indices (vertex 2304177633Sdfr * order values) that we may use, then we re-assign 2305177633Sdfr * orders first to those vertices in deltaB, then to 2306177633Sdfr * deltaF. Note that the contents of deltaF and deltaB 2307177633Sdfr * may be partially disordered - we perform an 2308177633Sdfr * insertion sort while building our index set. 2309177633Sdfr */ 2310177633Sdfr indices = g->g_indexbuf; 2311177633Sdfr n = graph_add_indices(indices, 0, &deltaF); 2312177633Sdfr graph_add_indices(indices, n, &deltaB); 2313177633Sdfr 2314177633Sdfr /* 2315177633Sdfr * We must also be sure to maintain the relative 2316177633Sdfr * ordering of deltaF and deltaB when re-assigning 2317177633Sdfr * vertices. We do this by iteratively removing the 2318177633Sdfr * lowest ordered element from the set and assigning 2319177633Sdfr * it the next value from our new ordering. 2320177633Sdfr */ 2321177633Sdfr i = graph_assign_indices(g, indices, 0, &deltaB); 2322177633Sdfr graph_assign_indices(g, indices, i, &deltaF); 2323177633Sdfr 2324177633Sdfr#ifdef LOCKF_DEBUG 2325177633Sdfr if (lockf_debug & 8) { 2326177633Sdfr struct owner_vertex_list set; 2327177633Sdfr TAILQ_INIT(&set); 2328177633Sdfr for (i = 0; i < nB + nF; i++) 2329177633Sdfr TAILQ_INSERT_TAIL(&set, 2330177633Sdfr g->g_vertices[indices[i]], v_link); 2331177633Sdfr printf("new ordering = "); 2332177633Sdfr graph_print_vertices(&set); 2333177633Sdfr } 2334177633Sdfr#endif 2335177633Sdfr } 2336177633Sdfr 2337177633Sdfr KASSERT(x->v_order < y->v_order, ("Failed to re-order graph")); 2338177633Sdfr 2339177633Sdfr#ifdef LOCKF_DEBUG 2340177633Sdfr if (lockf_debug & 8) { 2341177633Sdfr graph_check(g, TRUE); 2342177633Sdfr } 2343177633Sdfr#endif 2344177633Sdfr 2345177633Sdfr e = malloc(sizeof(struct owner_edge), M_LOCKF, M_WAITOK); 2346177633Sdfr 2347177633Sdfr LIST_INSERT_HEAD(&x->v_outedges, e, e_outlink); 2348177633Sdfr LIST_INSERT_HEAD(&y->v_inedges, e, e_inlink); 2349177633Sdfr e->e_refs = 1; 2350177633Sdfr e->e_from = x; 2351177633Sdfr e->e_to = y; 2352177633Sdfr 2353177633Sdfr return (0); 23541960Sdg} 23551960Sdg 2356177633Sdfr/* 2357177633Sdfr * Remove an edge x->y from the graph. 2358177633Sdfr */ 2359177633Sdfrstatic void 2360177633Sdfrgraph_remove_edge(struct owner_graph *g, struct owner_vertex *x, 2361177633Sdfr struct owner_vertex *y) 2362177633Sdfr{ 2363177633Sdfr struct owner_edge *e; 2364177633Sdfr 2365177633Sdfr sx_assert(&lf_owner_graph_lock, SX_XLOCKED); 2366177633Sdfr 2367177633Sdfr LIST_FOREACH(e, &x->v_outedges, e_outlink) { 2368177633Sdfr if (e->e_to == y) 2369177633Sdfr break; 2370177633Sdfr } 2371177633Sdfr KASSERT(e, ("Removing non-existent edge from deadlock graph")); 2372177633Sdfr 2373177633Sdfr e->e_refs--; 2374177633Sdfr if (e->e_refs == 0) { 23751960Sdg#ifdef LOCKF_DEBUG 2376177633Sdfr if (lockf_debug & 8) { 2377177633Sdfr printf("removing edge %d:", x->v_order); 2378177633Sdfr lf_print_owner(x->v_owner); 2379177633Sdfr printf(" -> %d:", y->v_order); 2380177633Sdfr lf_print_owner(y->v_owner); 2381177633Sdfr printf("\n"); 2382177633Sdfr } 2383177633Sdfr#endif 2384177633Sdfr LIST_REMOVE(e, e_outlink); 2385177633Sdfr LIST_REMOVE(e, e_inlink); 2386177633Sdfr free(e, M_LOCKF); 2387177633Sdfr } 2388177633Sdfr} 2389177633Sdfr 23901960Sdg/* 2391177633Sdfr * Allocate a vertex from the free list. Return ENOMEM if there are 2392177633Sdfr * none. 2393177633Sdfr */ 2394177633Sdfrstatic struct owner_vertex * 2395177633Sdfrgraph_alloc_vertex(struct owner_graph *g, struct lock_owner *lo) 2396177633Sdfr{ 2397177633Sdfr struct owner_vertex *v; 2398177633Sdfr 2399177633Sdfr sx_assert(&lf_owner_graph_lock, SX_XLOCKED); 2400177633Sdfr 2401177633Sdfr v = malloc(sizeof(struct owner_vertex), M_LOCKF, M_WAITOK); 2402177633Sdfr if (g->g_size == g->g_space) { 2403177633Sdfr g->g_vertices = realloc(g->g_vertices, 2404177633Sdfr 2 * g->g_space * sizeof(struct owner_vertex *), 2405177633Sdfr M_LOCKF, M_WAITOK); 2406177633Sdfr free(g->g_indexbuf, M_LOCKF); 2407177633Sdfr g->g_indexbuf = malloc(2 * g->g_space * sizeof(int), 2408177633Sdfr M_LOCKF, M_WAITOK); 2409177633Sdfr g->g_space = 2 * g->g_space; 2410177633Sdfr } 2411177633Sdfr v->v_order = g->g_size; 2412177633Sdfr v->v_gen = g->g_gen; 2413177633Sdfr g->g_vertices[g->g_size] = v; 2414177633Sdfr g->g_size++; 2415177633Sdfr 2416177633Sdfr LIST_INIT(&v->v_outedges); 2417177633Sdfr LIST_INIT(&v->v_inedges); 2418177633Sdfr v->v_owner = lo; 2419177633Sdfr 2420177633Sdfr return (v); 2421177633Sdfr} 2422177633Sdfr 2423177633Sdfrstatic void 2424177633Sdfrgraph_free_vertex(struct owner_graph *g, struct owner_vertex *v) 2425177633Sdfr{ 2426177633Sdfr struct owner_vertex *w; 2427177633Sdfr int i; 2428177633Sdfr 2429177633Sdfr sx_assert(&lf_owner_graph_lock, SX_XLOCKED); 2430177633Sdfr 2431177633Sdfr KASSERT(LIST_EMPTY(&v->v_outedges), ("Freeing vertex with edges")); 2432177633Sdfr KASSERT(LIST_EMPTY(&v->v_inedges), ("Freeing vertex with edges")); 2433177633Sdfr 2434177633Sdfr /* 2435177633Sdfr * Remove from the graph's array and close up the gap, 2436177633Sdfr * renumbering the other vertices. 2437177633Sdfr */ 2438177633Sdfr for (i = v->v_order + 1; i < g->g_size; i++) { 2439177633Sdfr w = g->g_vertices[i]; 2440177633Sdfr w->v_order--; 2441177633Sdfr g->g_vertices[i - 1] = w; 2442177633Sdfr } 2443177633Sdfr g->g_size--; 2444177633Sdfr 2445177633Sdfr free(v, M_LOCKF); 2446177633Sdfr} 2447177633Sdfr 2448177633Sdfrstatic struct owner_graph * 2449177633Sdfrgraph_init(struct owner_graph *g) 2450177633Sdfr{ 2451177633Sdfr 2452177633Sdfr g->g_vertices = malloc(10 * sizeof(struct owner_vertex *), 2453177633Sdfr M_LOCKF, M_WAITOK); 2454177633Sdfr g->g_size = 0; 2455177633Sdfr g->g_space = 10; 2456177633Sdfr g->g_indexbuf = malloc(g->g_space * sizeof(int), M_LOCKF, M_WAITOK); 2457177633Sdfr g->g_gen = 0; 2458177633Sdfr 2459177633Sdfr return (g); 2460177633Sdfr} 2461177633Sdfr 2462177633Sdfr#ifdef LOCKF_DEBUG 2463177633Sdfr/* 2464177633Sdfr * Print description of a lock owner 2465177633Sdfr */ 2466177633Sdfrstatic void 2467177633Sdfrlf_print_owner(struct lock_owner *lo) 2468177633Sdfr{ 2469177633Sdfr 2470177633Sdfr if (lo->lo_flags & F_REMOTE) { 2471177633Sdfr printf("remote pid %d, system %d", 2472177633Sdfr lo->lo_pid, lo->lo_sysid); 2473177633Sdfr } else if (lo->lo_flags & F_FLOCK) { 2474177633Sdfr printf("file %p", lo->lo_id); 2475177633Sdfr } else { 2476177633Sdfr printf("local pid %d", lo->lo_pid); 2477177633Sdfr } 2478177633Sdfr} 2479177633Sdfr 2480177633Sdfr/* 24811960Sdg * Print out a lock. 24821960Sdg */ 2483140808Sjeffstatic void 2484177633Sdfrlf_print(char *tag, struct lockf_entry *lock) 24851960Sdg{ 24868876Srgrimes 248737951Sbde printf("%s: lock %p for ", tag, (void *)lock); 2488177633Sdfr lf_print_owner(lock->lf_owner); 248987211Salfred if (lock->lf_inode != (struct inode *)0) 2490177633Sdfr printf(" in ino %ju on dev <%s>,", 2491106584Smux (uintmax_t)lock->lf_inode->i_number, 2492177633Sdfr devtoname(lock->lf_inode->i_dev)); 2493177633Sdfr printf(" %s, start %jd, end ", 2494177633Sdfr lock->lf_type == F_RDLCK ? "shared" : 2495177633Sdfr lock->lf_type == F_WRLCK ? "exclusive" : 2496177633Sdfr lock->lf_type == F_UNLCK ? "unlock" : "unknown", 2497177633Sdfr (intmax_t)lock->lf_start); 2498177633Sdfr if (lock->lf_end == OFF_MAX) 2499177633Sdfr printf("EOF"); 250087211Salfred else 2501177633Sdfr printf("%jd", (intmax_t)lock->lf_end); 2502177633Sdfr if (!LIST_EMPTY(&lock->lf_outedges)) 2503177633Sdfr printf(" block %p\n", 2504177633Sdfr (void *)LIST_FIRST(&lock->lf_outedges)->le_to); 25051960Sdg else 25061960Sdg printf("\n"); 25071960Sdg} 25081960Sdg 2509140808Sjeffstatic void 2510177633Sdfrlf_printlist(char *tag, struct lockf_entry *lock) 25111960Sdg{ 2512177633Sdfr struct lockf_entry *lf, *blk; 2513177633Sdfr struct lockf_edge *e; 25141960Sdg 251587211Salfred if (lock->lf_inode == (struct inode *)0) 251687211Salfred return; 251787211Salfred 2518144278Sphk printf("%s: Lock list for ino %ju on dev <%s>:\n", 2519106584Smux tag, (uintmax_t)lock->lf_inode->i_number, 2520144278Sphk devtoname(lock->lf_inode->i_dev)); 2521178247Sdfr LIST_FOREACH(lf, &lock->lf_vnode->v_lockf->ls_active, lf_link) { 252237951Sbde printf("\tlock %p for ",(void *)lf); 2523177633Sdfr lf_print_owner(lock->lf_owner); 2524106584Smux printf(", %s, start %jd, end %jd", 252537951Sbde lf->lf_type == F_RDLCK ? "shared" : 252637951Sbde lf->lf_type == F_WRLCK ? "exclusive" : 252737951Sbde lf->lf_type == F_UNLCK ? "unlock" : 2528106584Smux "unknown", (intmax_t)lf->lf_start, (intmax_t)lf->lf_end); 2529177633Sdfr LIST_FOREACH(e, &lf->lf_outedges, le_outlink) { 2530177633Sdfr blk = e->le_to; 253137951Sbde printf("\n\t\tlock request %p for ", (void *)blk); 2532177633Sdfr lf_print_owner(blk->lf_owner); 2533106584Smux printf(", %s, start %jd, end %jd", 253437951Sbde blk->lf_type == F_RDLCK ? "shared" : 253537951Sbde blk->lf_type == F_WRLCK ? "exclusive" : 253637951Sbde blk->lf_type == F_UNLCK ? "unlock" : 2537106584Smux "unknown", (intmax_t)blk->lf_start, 2538106584Smux (intmax_t)blk->lf_end); 2539177633Sdfr if (!LIST_EMPTY(&blk->lf_inedges)) 254022521Sdyson panic("lf_printlist: bad list"); 254122521Sdyson } 254222521Sdyson printf("\n"); 25431960Sdg } 25441960Sdg} 25451960Sdg#endif /* LOCKF_DEBUG */ 2546