sys/kern/kern_lockf.c

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