xref: /freebsd/sys/kern/kern_lockf.c (revision 10f0bcab61ef441cb5af32fb706688d8cbd55dc0)

/*-
 * Copyright (c) 2008 Isilon Inc http://www.isilon.com/
 * Authors: Doug Rabson <dfr@rabson.org>
 * Developed with Red Inc: Alfred Perlstein <alfred@freebsd.org>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
/*-
 * Copyright (c) 1982, 1986, 1989, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Scooter Morris at Genentech Inc.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)ufs_lockf.c	8.3 (Berkeley) 1/6/94
 */

#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");

#include "opt_debug_lockf.h"

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/hash.h>
#include <sys/kernel.h>
#include <sys/limits.h>
#include <sys/lock.h>
#include <sys/mount.h>
#include <sys/mutex.h>
#include <sys/proc.h>
#include <sys/sx.h>
#include <sys/unistd.h>
#include <sys/vnode.h>
#include <sys/malloc.h>
#include <sys/fcntl.h>
#include <sys/lockf.h>
#include <sys/taskqueue.h>

#ifdef LOCKF_DEBUG
#include <sys/sysctl.h>

#include <ufs/ufs/quota.h>
#include <ufs/ufs/inode.h>

static int	lockf_debug = 0; /* control debug output */
SYSCTL_INT(_debug, OID_AUTO, lockf_debug, CTLFLAG_RW, &lockf_debug, 0, "");
#endif

MALLOC_DEFINE(M_LOCKF, "lockf", "Byte-range locking structures");

struct owner_edge;
struct owner_vertex;
struct owner_vertex_list;
struct owner_graph;

#define NOLOCKF (struct lockf_entry *)0
#define SELF	0x1
#define OTHERS	0x2
static void	 lf_init(void *);
static int	 lf_hash_owner(caddr_t, struct flock *, int);
static int	 lf_owner_matches(struct lock_owner *, caddr_t, struct flock *,
    int);
static struct lockf_entry *
		 lf_alloc_lock(struct lock_owner *);
static void	 lf_free_lock(struct lockf_entry *);
static int	 lf_clearlock(struct lockf *, struct lockf_entry *);
static int	 lf_overlaps(struct lockf_entry *, struct lockf_entry *);
static int	 lf_blocks(struct lockf_entry *, struct lockf_entry *);
static void	 lf_free_edge(struct lockf_edge *);
static struct lockf_edge *
		 lf_alloc_edge(void);
static void	 lf_alloc_vertex(struct lockf_entry *);
static int	 lf_add_edge(struct lockf_entry *, struct lockf_entry *);
static void	 lf_remove_edge(struct lockf_edge *);
static void	 lf_remove_outgoing(struct lockf_entry *);
static void	 lf_remove_incoming(struct lockf_entry *);
static int	 lf_add_outgoing(struct lockf *, struct lockf_entry *);
static int	 lf_add_incoming(struct lockf *, struct lockf_entry *);
static int	 lf_findoverlap(struct lockf_entry **, struct lockf_entry *,
    int);
static struct lockf_entry *
		 lf_getblock(struct lockf *, struct lockf_entry *);
static int	 lf_getlock(struct lockf *, struct lockf_entry *, struct flock *);
static void	 lf_insert_lock(struct lockf *, struct lockf_entry *);
static void	 lf_wakeup_lock(struct lockf *, struct lockf_entry *);
static void	 lf_update_dependancies(struct lockf *, struct lockf_entry *,
    int all, struct lockf_entry_list *);
static void	 lf_set_start(struct lockf *, struct lockf_entry *, off_t,
	struct lockf_entry_list*);
static void	 lf_set_end(struct lockf *, struct lockf_entry *, off_t,
	struct lockf_entry_list*);
static int	 lf_setlock(struct lockf *, struct lockf_entry *,
    struct vnode *, void **cookiep);
static int	 lf_cancel(struct lockf *, struct lockf_entry *, void *);
static void	 lf_split(struct lockf *, struct lockf_entry *,
    struct lockf_entry *, struct lockf_entry_list *);
#ifdef LOCKF_DEBUG
static int	 graph_reaches(struct owner_vertex *x, struct owner_vertex *y,
    struct owner_vertex_list *path);
static void	 graph_check(struct owner_graph *g, int checkorder);
static void	 graph_print_vertices(struct owner_vertex_list *set);
#endif
static int	 graph_delta_forward(struct owner_graph *g,
    struct owner_vertex *x, struct owner_vertex *y,
    struct owner_vertex_list *delta);
static int	 graph_delta_backward(struct owner_graph *g,
    struct owner_vertex *x, struct owner_vertex *y,
    struct owner_vertex_list *delta);
static int	 graph_add_indices(int *indices, int n,
    struct owner_vertex_list *set);
static int	 graph_assign_indices(struct owner_graph *g, int *indices,
    int nextunused, struct owner_vertex_list *set);
static int	 graph_add_edge(struct owner_graph *g,
    struct owner_vertex *x, struct owner_vertex *y);
static void	 graph_remove_edge(struct owner_graph *g,
    struct owner_vertex *x, struct owner_vertex *y);
static struct owner_vertex *graph_alloc_vertex(struct owner_graph *g,
    struct lock_owner *lo);
static void	 graph_free_vertex(struct owner_graph *g,
    struct owner_vertex *v);
static struct owner_graph * graph_init(struct owner_graph *g);
#ifdef LOCKF_DEBUG
static void	 lf_print(char *, struct lockf_entry *);
static void	 lf_printlist(char *, struct lockf_entry *);
static void	 lf_print_owner(struct lock_owner *);
#endif

/*
 * This structure is used to keep track of both local and remote lock
 * owners. The lf_owner field of the struct lockf_entry points back at
 * the lock owner structure. Each possible lock owner (local proc for
 * POSIX fcntl locks, local file for BSD flock locks or <pid,sysid>
 * pair for remote locks) is represented by a unique instance of
 * struct lock_owner.
 *
 * If a lock owner has a lock that blocks some other lock or a lock
 * that is waiting for some other lock, it also has a vertex in the
 * owner_graph below.
 *
 * Locks:
 * (s)		locked by state->ls_lock
 * (S)		locked by lf_lock_states_lock
 * (l)		locked by lf_lock_owners_lock
 * (g)		locked by lf_owner_graph_lock
 * (c)		const until freeing
 */
#define	LOCK_OWNER_HASH_SIZE	256

struct lock_owner {
	LIST_ENTRY(lock_owner) lo_link; /* (l) hash chain */
	int	lo_refs;	    /* (l) Number of locks referring to this */
	int	lo_flags;	    /* (c) Flags passwd to lf_advlock */
	caddr_t	lo_id;		    /* (c) Id value passed to lf_advlock */
	pid_t	lo_pid;		    /* (c) Process Id of the lock owner */
	int	lo_sysid;	    /* (c) System Id of the lock owner */
	struct owner_vertex *lo_vertex; /* (g) entry in deadlock graph */
};

LIST_HEAD(lock_owner_list, lock_owner);

static struct sx		lf_lock_states_lock;
static struct lockf_list	lf_lock_states; /* (S) */
static struct sx		lf_lock_owners_lock;
static struct lock_owner_list	lf_lock_owners[LOCK_OWNER_HASH_SIZE]; /* (l) */

/*
 * Structures for deadlock detection.
 *
 * We have two types of directed graph, the first is the set of locks,
 * both active and pending on a vnode. Within this graph, active locks
 * are terminal nodes in the graph (i.e. have no out-going
 * edges). Pending locks have out-going edges to each blocking active
 * lock that prevents the lock from being granted and also to each
 * older pending lock that would block them if it was active. The
 * graph for each vnode is naturally acyclic; new edges are only ever
 * added to or from new nodes (either new pending locks which only add
 * out-going edges or new active locks which only add in-coming edges)
 * therefore they cannot create loops in the lock graph.
 *
 * The second graph is a global graph of lock owners. Each lock owner
 * is a vertex in that graph and an edge is added to the graph
 * whenever an edge is added to a vnode graph, with end points
 * corresponding to owner of the new pending lock and the owner of the
 * lock upon which it waits. In order to prevent deadlock, we only add
 * an edge to this graph if the new edge would not create a cycle.
 *
 * The lock owner graph is topologically sorted, i.e. if a node has
 * any outgoing edges, then it has an order strictly less than any
 * node to which it has an outgoing edge. We preserve this ordering
 * (and detect cycles) on edge insertion using Algorithm PK from the
 * paper "A Dynamic Topological Sort Algorithm for Directed Acyclic
 * Graphs" (ACM Journal of Experimental Algorithms, Vol 11, Article
 * No. 1.7)
 */
struct owner_vertex;

struct owner_edge {
	LIST_ENTRY(owner_edge) e_outlink; /* (g) link from's out-edge list */
	LIST_ENTRY(owner_edge) e_inlink;  /* (g) link to's in-edge list */
	int		e_refs;		  /* (g) number of times added */
	struct owner_vertex *e_from;	  /* (c) out-going from here */
	struct owner_vertex *e_to;	  /* (c) in-coming to here */
};
LIST_HEAD(owner_edge_list, owner_edge);

struct owner_vertex {
	TAILQ_ENTRY(owner_vertex) v_link; /* (g) workspace for edge insertion */
	uint32_t	v_gen;		  /* (g) workspace for edge insertion */
	int		v_order;	  /* (g) order of vertex in graph */
	struct owner_edge_list v_outedges;/* (g) list of out-edges */
	struct owner_edge_list v_inedges; /* (g) list of in-edges */
	struct lock_owner *v_owner;	  /* (c) corresponding lock owner */
};
TAILQ_HEAD(owner_vertex_list, owner_vertex);

struct owner_graph {
	struct owner_vertex** g_vertices; /* (g) pointers to vertices */
	int		g_size;		  /* (g) number of vertices */
	int		g_space;	  /* (g) space allocated for vertices */
	int		*g_indexbuf;	  /* (g) workspace for loop detection */
	uint32_t	g_gen;		  /* (g) increment when re-ordering */
};

static struct sx		lf_owner_graph_lock;
static struct owner_graph	lf_owner_graph;

/*
 * Initialise various structures and locks.
 */
static void
lf_init(void *dummy)
{
	int i;

	sx_init(&lf_lock_states_lock, "lock states lock");
	LIST_INIT(&lf_lock_states);

	sx_init(&lf_lock_owners_lock, "lock owners lock");
	for (i = 0; i < LOCK_OWNER_HASH_SIZE; i++)
		LIST_INIT(&lf_lock_owners[i]);

	sx_init(&lf_owner_graph_lock, "owner graph lock");
	graph_init(&lf_owner_graph);
}
SYSINIT(lf_init, SI_SUB_LOCK, SI_ORDER_FIRST, lf_init, NULL);

/*
 * Generate a hash value for a lock owner.
 */
static int
lf_hash_owner(caddr_t id, struct flock *fl, int flags)
{
	uint32_t h;

	if (flags & F_REMOTE) {
		h = HASHSTEP(0, fl->l_pid);
		h = HASHSTEP(h, fl->l_sysid);
	} else if (flags & F_FLOCK) {
		h = ((uintptr_t) id) >> 7;
	} else {
		struct proc *p = (struct proc *) id;
		h = HASHSTEP(0, p->p_pid);
		h = HASHSTEP(h, 0);
	}

	return (h % LOCK_OWNER_HASH_SIZE);
}

/*
 * Return true if a lock owner matches the details passed to
 * lf_advlock.
 */
static int
lf_owner_matches(struct lock_owner *lo, caddr_t id, struct flock *fl,
    int flags)
{
	if (flags & F_REMOTE) {
		return lo->lo_pid == fl->l_pid
			&& lo->lo_sysid == fl->l_sysid;
	} else {
		return lo->lo_id == id;
	}
}

static struct lockf_entry *
lf_alloc_lock(struct lock_owner *lo)
{
	struct lockf_entry *lf;

	lf = malloc(sizeof(struct lockf_entry), M_LOCKF, M_WAITOK|M_ZERO);

#ifdef LOCKF_DEBUG
	if (lockf_debug & 4)
		printf("Allocated lock %p\n", lf);
#endif
	if (lo) {
		sx_xlock(&lf_lock_owners_lock);
		lo->lo_refs++;
		sx_xunlock(&lf_lock_owners_lock);
		lf->lf_owner = lo;
	}

	return (lf);
}

static void
lf_free_lock(struct lockf_entry *lock)
{
	/*
	 * Adjust the lock_owner reference count and
	 * reclaim the entry if this is the last lock
	 * for that owner.
	 */
	struct lock_owner *lo = lock->lf_owner;
	if (lo) {
		KASSERT(LIST_EMPTY(&lock->lf_outedges),
		    ("freeing lock with dependancies"));
		KASSERT(LIST_EMPTY(&lock->lf_inedges),
		    ("freeing lock with dependants"));
		sx_xlock(&lf_lock_owners_lock);
		KASSERT(lo->lo_refs > 0, ("lock owner refcount"));
		lo->lo_refs--;
		if (lo->lo_refs == 0) {
#ifdef LOCKF_DEBUG
			if (lockf_debug & 1)
				printf("lf_free_lock: freeing lock owner %p\n",
				    lo);
#endif
			if (lo->lo_vertex) {
				sx_xlock(&lf_owner_graph_lock);
				graph_free_vertex(&lf_owner_graph,
				    lo->lo_vertex);
				sx_xunlock(&lf_owner_graph_lock);
			}
			LIST_REMOVE(lo, lo_link);
			free(lo, M_LOCKF);
#ifdef LOCKF_DEBUG
			if (lockf_debug & 4)
				printf("Freed lock owner %p\n", lo);
#endif
		}
		sx_unlock(&lf_lock_owners_lock);
	}
	if ((lock->lf_flags & F_REMOTE) && lock->lf_vnode) {
		vrele(lock->lf_vnode);
		lock->lf_vnode = NULL;
	}
#ifdef LOCKF_DEBUG
	if (lockf_debug & 4)
		printf("Freed lock %p\n", lock);
#endif
	free(lock, M_LOCKF);
}

/*
 * Advisory record locking support
 */
int
lf_advlockasync(struct vop_advlockasync_args *ap, struct lockf **statep,
    u_quad_t size)
{
	struct lockf *state, *freestate = NULL;
	struct flock *fl = ap->a_fl;
	struct lockf_entry *lock;
	struct vnode *vp = ap->a_vp;
	caddr_t id = ap->a_id;
	int flags = ap->a_flags;
	int hash;
	struct lock_owner *lo;
	off_t start, end, oadd;
	int error;

	/*
	 * Handle the F_UNLKSYS case first - no need to mess about
	 * creating a lock owner for this one.
	 */
	if (ap->a_op == F_UNLCKSYS) {
		lf_clearremotesys(fl->l_sysid);
		return (0);
	}

	/*
	 * Convert the flock structure into a start and end.
	 */
	switch (fl->l_whence) {

	case SEEK_SET:
	case SEEK_CUR:
		/*
		 * Caller is responsible for adding any necessary offset
		 * when SEEK_CUR is used.
		 */
		start = fl->l_start;
		break;

	case SEEK_END:
		if (size > OFF_MAX ||
		    (fl->l_start > 0 && size > OFF_MAX - fl->l_start))
			return (EOVERFLOW);
		start = size + fl->l_start;
		break;

	default:
		return (EINVAL);
	}
	if (start < 0)
		return (EINVAL);
	if (fl->l_len < 0) {
		if (start == 0)
			return (EINVAL);
		end = start - 1;
		start += fl->l_len;
		if (start < 0)
			return (EINVAL);
	} else if (fl->l_len == 0) {
		end = OFF_MAX;
	} else {
		oadd = fl->l_len - 1;
		if (oadd > OFF_MAX - start)
			return (EOVERFLOW);
		end = start + oadd;
	}
	/*
	 * Avoid the common case of unlocking when inode has no locks.
	 */
	if ((*statep) == NULL || LIST_EMPTY(&(*statep)->ls_active)) {
		if (ap->a_op != F_SETLK) {
			fl->l_type = F_UNLCK;
			return (0);
		}
	}

	/*
	 * Map our arguments to an existing lock owner or create one
	 * if this is the first time we have seen this owner.
	 */
	hash = lf_hash_owner(id, fl, flags);
	sx_xlock(&lf_lock_owners_lock);
	LIST_FOREACH(lo, &lf_lock_owners[hash], lo_link)
		if (lf_owner_matches(lo, id, fl, flags))
			break;
	if (!lo) {
		/*
		 * We initialise the lock with a reference
		 * count which matches the new lockf_entry
		 * structure created below.
		 */
		lo = malloc(sizeof(struct lock_owner), M_LOCKF,
		    M_WAITOK|M_ZERO);
#ifdef LOCKF_DEBUG
		if (lockf_debug & 4)
			printf("Allocated lock owner %p\n", lo);
#endif

		lo->lo_refs = 1;
		lo->lo_flags = flags;
		lo->lo_id = id;
		if (flags & F_REMOTE) {
			lo->lo_pid = fl->l_pid;
			lo->lo_sysid = fl->l_sysid;
		} else if (flags & F_FLOCK) {
			lo->lo_pid = -1;
			lo->lo_sysid = 0;
		} else {
			struct proc *p = (struct proc *) id;
			lo->lo_pid = p->p_pid;
			lo->lo_sysid = 0;
		}
		lo->lo_vertex = NULL;

#ifdef LOCKF_DEBUG
		if (lockf_debug & 1) {
			printf("lf_advlockasync: new lock owner %p ", lo);
			lf_print_owner(lo);
			printf("\n");
		}
#endif

		LIST_INSERT_HEAD(&lf_lock_owners[hash], lo, lo_link);
	} else {
		/*
		 * We have seen this lock owner before, increase its
		 * reference count to account for the new lockf_entry
		 * structure we create below.
		 */
		lo->lo_refs++;
	}
	sx_xunlock(&lf_lock_owners_lock);

	/*
	 * Create the lockf structure. We initialise the lf_owner
	 * field here instead of in lf_alloc_lock() to avoid paying
	 * the lf_lock_owners_lock tax twice.
	 */
	lock = lf_alloc_lock(NULL);
	lock->lf_start = start;
	lock->lf_end = end;
	lock->lf_owner = lo;
	lock->lf_vnode = vp;
	if (flags & F_REMOTE) {
		/*
		 * For remote locks, the caller may release its ref to
		 * the vnode at any time - we have to ref it here to
		 * prevent it from being recycled unexpectedly.
		 */
		vref(vp);
	}

	/*
	 * XXX The problem is that VTOI is ufs specific, so it will
	 * break LOCKF_DEBUG for all other FS's other than UFS because
	 * it casts the vnode->data ptr to struct inode *.
	 */
/*	lock->lf_inode = VTOI(ap->a_vp); */
	lock->lf_inode = (struct inode *)0;
	lock->lf_type = fl->l_type;
	LIST_INIT(&lock->lf_outedges);
	LIST_INIT(&lock->lf_inedges);
	lock->lf_async_task = ap->a_task;
	lock->lf_flags = ap->a_flags;

	/*
	 * Do the requested operation. First find our state structure
	 * and create a new one if necessary - the caller's *statep
	 * variable and the state's ls_threads count is protected by
	 * the vnode interlock.
	 */
	VI_LOCK(vp);

	/*
	 * Allocate a state structure if necessary.
	 */
	state = *statep;
	if (state == NULL) {
		struct lockf *ls;

		VI_UNLOCK(vp);

		ls = malloc(sizeof(struct lockf), M_LOCKF, M_WAITOK|M_ZERO);
		sx_init(&ls->ls_lock, "ls_lock");
		LIST_INIT(&ls->ls_active);
		LIST_INIT(&ls->ls_pending);

		sx_xlock(&lf_lock_states_lock);
		LIST_INSERT_HEAD(&lf_lock_states, ls, ls_link);
		sx_xunlock(&lf_lock_states_lock);

		/*
		 * Cope if we lost a race with some other thread while
		 * trying to allocate memory.
		 */
		VI_LOCK(vp);
		if ((*statep) == NULL) {
			(*statep) = ls;
		} else {
			sx_xlock(&lf_lock_states_lock);
			LIST_REMOVE(ls, ls_link);
			sx_xunlock(&lf_lock_states_lock);
			sx_destroy(&ls->ls_lock);
			free(ls, M_LOCKF);
		}
	}
	state = *statep;
	state->ls_threads++;

	VI_UNLOCK(vp);

	sx_xlock(&state->ls_lock);
	switch(ap->a_op) {
	case F_SETLK:
		error = lf_setlock(state, lock, vp, ap->a_cookiep);
		break;

	case F_UNLCK:
		error = lf_clearlock(state, lock);
		lf_free_lock(lock);
		break;

	case F_GETLK:
		error = lf_getlock(state, lock, fl);
		lf_free_lock(lock);
		break;

	case F_CANCEL:
		if (ap->a_cookiep)
			error = lf_cancel(state, lock, *ap->a_cookiep);
		else
			error = EINVAL;
		lf_free_lock(lock);
		break;

	default:
		lf_free_lock(lock);
		error = EINVAL;
		break;
	}

#ifdef INVARIANTS
	/*
	 * Check for some can't happen stuff. In this case, the active
	 * lock list becoming disordered or containing mutually
	 * blocking locks. We also check the pending list for locks
	 * which should be active (i.e. have no out-going edges).
	 */
	LIST_FOREACH(lock, &state->ls_active, lf_link) {
		struct lockf_entry *lf;
		if (LIST_NEXT(lock, lf_link))
			KASSERT((lock->lf_start
				<= LIST_NEXT(lock, lf_link)->lf_start),
			    ("locks disordered"));
		LIST_FOREACH(lf, &state->ls_active, lf_link) {
			if (lock == lf)
				break;
			KASSERT(!lf_blocks(lock, lf),
			    ("two conflicting active locks"));
			if (lock->lf_owner == lf->lf_owner)
				KASSERT(!lf_overlaps(lock, lf),
				    ("two overlapping locks from same owner"));
		}
	}
	LIST_FOREACH(lock, &state->ls_pending, lf_link) {
		KASSERT(!LIST_EMPTY(&lock->lf_outedges),
		    ("pending lock which should be active"));
	}
#endif
	sx_xunlock(&state->ls_lock);

	/*
	 * If we have removed the last active lock on the vnode and
	 * this is the last thread that was in-progress, we can free
	 * the state structure. We update the caller's pointer inside
	 * the vnode interlock but call free outside.
	 *
	 * XXX alternatively, keep the state structure around until
	 * the filesystem recycles - requires a callback from the
	 * filesystem.
	 */
	VI_LOCK(vp);

	state->ls_threads--;
	if (LIST_EMPTY(&state->ls_active) && state->ls_threads == 0) {
		KASSERT(LIST_EMPTY(&state->ls_pending),
		    ("freeing state with pending locks"));
		freestate = state;
		*statep = NULL;
	}

	VI_UNLOCK(vp);

	if (freestate) {
		sx_xlock(&lf_lock_states_lock);
		LIST_REMOVE(freestate, ls_link);
		sx_xunlock(&lf_lock_states_lock);
		sx_destroy(&freestate->ls_lock);
		free(freestate, M_LOCKF);
	}
	return (error);
}

int
lf_advlock(struct vop_advlock_args *ap, struct lockf **statep, u_quad_t size)
{
	struct vop_advlockasync_args a;

	a.a_vp = ap->a_vp;
	a.a_id = ap->a_id;
	a.a_op = ap->a_op;
	a.a_fl = ap->a_fl;
	a.a_flags = ap->a_flags;
	a.a_task = NULL;
	a.a_cookiep = NULL;

	return (lf_advlockasync(&a, statep, size));
}

/*
 * Return non-zero if locks 'x' and 'y' overlap.
 */
static int
lf_overlaps(struct lockf_entry *x, struct lockf_entry *y)
{

	return (x->lf_start <= y->lf_end && x->lf_end >= y->lf_start);
}

/*
 * Return non-zero if lock 'x' is blocked by lock 'y' (or vice versa).
 */
static int
lf_blocks(struct lockf_entry *x, struct lockf_entry *y)
{

	return x->lf_owner != y->lf_owner
		&& (x->lf_type == F_WRLCK || y->lf_type == F_WRLCK)
		&& lf_overlaps(x, y);
}

/*
 * Allocate a lock edge from the free list
 */
static struct lockf_edge *
lf_alloc_edge(void)
{

	return (malloc(sizeof(struct lockf_edge), M_LOCKF, M_WAITOK|M_ZERO));
}

/*
 * Free a lock edge.
 */
static void
lf_free_edge(struct lockf_edge *e)
{

	free(e, M_LOCKF);
}


/*
 * Ensure that the lock's owner has a corresponding vertex in the
 * owner graph.
 */
static void
lf_alloc_vertex(struct lockf_entry *lock)
{
	struct owner_graph *g = &lf_owner_graph;

	if (!lock->lf_owner->lo_vertex)
		lock->lf_owner->lo_vertex =
			graph_alloc_vertex(g, lock->lf_owner);
}

/*
 * Attempt to record an edge from lock x to lock y. Return EDEADLK if
 * the new edge would cause a cycle in the owner graph.
 */
static int
lf_add_edge(struct lockf_entry *x, struct lockf_entry *y)
{
	struct owner_graph *g = &lf_owner_graph;
	struct lockf_edge *e;
	int error;

#ifdef INVARIANTS
	LIST_FOREACH(e, &x->lf_outedges, le_outlink)
		KASSERT(e->le_to != y, ("adding lock edge twice"));
#endif

	/*
	 * Make sure the two owners have entries in the owner graph.
	 */
	lf_alloc_vertex(x);
	lf_alloc_vertex(y);

	error = graph_add_edge(g, x->lf_owner->lo_vertex,
	    y->lf_owner->lo_vertex);
	if (error)
		return (error);

	e = lf_alloc_edge();
	LIST_INSERT_HEAD(&x->lf_outedges, e, le_outlink);
	LIST_INSERT_HEAD(&y->lf_inedges, e, le_inlink);
	e->le_from = x;
	e->le_to = y;

	return (0);
}

/*
 * Remove an edge from the lock graph.
 */
static void
lf_remove_edge(struct lockf_edge *e)
{
	struct owner_graph *g = &lf_owner_graph;
	struct lockf_entry *x = e->le_from;
	struct lockf_entry *y = e->le_to;

	graph_remove_edge(g, x->lf_owner->lo_vertex, y->lf_owner->lo_vertex);
	LIST_REMOVE(e, le_outlink);
	LIST_REMOVE(e, le_inlink);
	e->le_from = NULL;
	e->le_to = NULL;
	lf_free_edge(e);
}

/*
 * Remove all out-going edges from lock x.
 */
static void
lf_remove_outgoing(struct lockf_entry *x)
{
	struct lockf_edge *e;

	while ((e = LIST_FIRST(&x->lf_outedges)) != NULL) {
		lf_remove_edge(e);
	}
}

/*
 * Remove all in-coming edges from lock x.
 */
static void
lf_remove_incoming(struct lockf_entry *x)
{
	struct lockf_edge *e;

	while ((e = LIST_FIRST(&x->lf_inedges)) != NULL) {
		lf_remove_edge(e);
	}
}

/*
 * Walk the list of locks for the file and create an out-going edge
 * from lock to each blocking lock.
 */
static int
lf_add_outgoing(struct lockf *state, struct lockf_entry *lock)
{
	struct lockf_entry *overlap;
	int error;

	LIST_FOREACH(overlap, &state->ls_active, lf_link) {
		/*
		 * We may assume that the active list is sorted by
		 * lf_start.
		 */
		if (overlap->lf_start > lock->lf_end)
			break;
		if (!lf_blocks(lock, overlap))
			continue;

		/*
		 * We've found a blocking lock. Add the corresponding
		 * edge to the graphs and see if it would cause a
		 * deadlock.
		 */
		error = lf_add_edge(lock, overlap);

		/*
		 * The only error that lf_add_edge returns is EDEADLK.
		 * Remove any edges we added and return the error.
		 */
		if (error) {
			lf_remove_outgoing(lock);
			return (error);
		}
	}

	/*
	 * We also need to add edges to sleeping locks that block
	 * us. This ensures that lf_wakeup_lock cannot grant two
	 * mutually blocking locks simultaneously and also enforces a
	 * 'first come, first served' fairness model. Note that this
	 * only happens if we are blocked by at least one active lock
	 * due to the call to lf_getblock in lf_setlock below.
	 */
	LIST_FOREACH(overlap, &state->ls_pending, lf_link) {
		if (!lf_blocks(lock, overlap))
			continue;
		/*
		 * We've found a blocking lock. Add the corresponding
		 * edge to the graphs and see if it would cause a
		 * deadlock.
		 */
		error = lf_add_edge(lock, overlap);

		/*
		 * The only error that lf_add_edge returns is EDEADLK.
		 * Remove any edges we added and return the error.
		 */
		if (error) {
			lf_remove_outgoing(lock);
			return (error);
		}
	}

	return (0);
}

/*
 * Walk the list of pending locks for the file and create an in-coming
 * edge from lock to each blocking lock.
 */
static int
lf_add_incoming(struct lockf *state, struct lockf_entry *lock)
{
	struct lockf_entry *overlap;
	int error;

	LIST_FOREACH(overlap, &state->ls_pending, lf_link) {
		if (!lf_blocks(lock, overlap))
			continue;

		/*
		 * We've found a blocking lock. Add the corresponding
		 * edge to the graphs and see if it would cause a
		 * deadlock.
		 */
		error = lf_add_edge(overlap, lock);

		/*
		 * The only error that lf_add_edge returns is EDEADLK.
		 * Remove any edges we added and return the error.
		 */
		if (error) {
			lf_remove_incoming(lock);
			return (error);
		}
	}
	return (0);
}

/*
 * Insert lock into the active list, keeping list entries ordered by
 * increasing values of lf_start.
 */
static void
lf_insert_lock(struct lockf *state, struct lockf_entry *lock)
{
	struct lockf_entry *lf, *lfprev;

	if (LIST_EMPTY(&state->ls_active)) {
		LIST_INSERT_HEAD(&state->ls_active, lock, lf_link);
		return;
	}

	lfprev = NULL;
	LIST_FOREACH(lf, &state->ls_active, lf_link) {
		if (lf->lf_start > lock->lf_start) {
			LIST_INSERT_BEFORE(lf, lock, lf_link);
			return;
		}
		lfprev = lf;
	}
	LIST_INSERT_AFTER(lfprev, lock, lf_link);
}

/*
 * Wake up a sleeping lock and remove it from the pending list now
 * that all its dependancies have been resolved. The caller should
 * arrange for the lock to be added to the active list, adjusting any
 * existing locks for the same owner as needed.
 */
static void
lf_wakeup_lock(struct lockf *state, struct lockf_entry *wakelock)
{

	/*
	 * Remove from ls_pending list and wake up the caller
	 * or start the async notification, as appropriate.
	 */
	LIST_REMOVE(wakelock, lf_link);
#ifdef LOCKF_DEBUG
	if (lockf_debug & 1)
		lf_print("lf_wakeup_lock: awakening", wakelock);
#endif /* LOCKF_DEBUG */
	if (wakelock->lf_async_task) {
		taskqueue_enqueue(taskqueue_thread, wakelock->lf_async_task);
	} else {
		wakeup(wakelock);
	}
}

/*
 * Re-check all dependant locks and remove edges to locks that we no
 * longer block. If 'all' is non-zero, the lock has been removed and
 * we must remove all the dependancies, otherwise it has simply been
 * reduced but remains active. Any pending locks which have been been
 * unblocked are added to 'granted'
 */
static void
lf_update_dependancies(struct lockf *state, struct lockf_entry *lock, int all,
	struct lockf_entry_list *granted)
{
	struct lockf_edge *e, *ne;
	struct lockf_entry *deplock;

	LIST_FOREACH_SAFE(e, &lock->lf_inedges, le_inlink, ne) {
		deplock = e->le_from;
		if (all || !lf_blocks(lock, deplock)) {
			sx_xlock(&lf_owner_graph_lock);
			lf_remove_edge(e);
			sx_xunlock(&lf_owner_graph_lock);
			if (LIST_EMPTY(&deplock->lf_outedges)) {
				lf_wakeup_lock(state, deplock);
				LIST_INSERT_HEAD(granted, deplock, lf_link);
			}
		}
	}
}

/*
 * Set the start of an existing active lock, updating dependancies and
 * adding any newly woken locks to 'granted'.
 */
static void
lf_set_start(struct lockf *state, struct lockf_entry *lock, off_t new_start,
	struct lockf_entry_list *granted)
{

	KASSERT(new_start >= lock->lf_start, ("can't increase lock"));
	lock->lf_start = new_start;
	LIST_REMOVE(lock, lf_link);
	lf_insert_lock(state, lock);
	lf_update_dependancies(state, lock, FALSE, granted);
}

/*
 * Set the end of an existing active lock, updating dependancies and
 * adding any newly woken locks to 'granted'.
 */
static void
lf_set_end(struct lockf *state, struct lockf_entry *lock, off_t new_end,
	struct lockf_entry_list *granted)
{

	KASSERT(new_end <= lock->lf_end, ("can't increase lock"));
	lock->lf_end = new_end;
	lf_update_dependancies(state, lock, FALSE, granted);
}

/*
 * Add a lock to the active list, updating or removing any current
 * locks owned by the same owner and processing any pending locks that
 * become unblocked as a result. This code is also used for unlock
 * since the logic for updating existing locks is identical.
 *
 * As a result of processing the new lock, we may unblock existing
 * pending locks as a result of downgrading/unlocking. We simply
 * activate the newly granted locks by looping.
 *
 * Since the new lock already has its dependancies set up, we always
 * add it to the list (unless its an unlock request). This may
 * fragment the lock list in some pathological cases but its probably
 * not a real problem.
 */
static void
lf_activate_lock(struct lockf *state, struct lockf_entry *lock)
{
	struct lockf_entry *overlap, *lf;
	struct lockf_entry_list granted;
	int ovcase;

	LIST_INIT(&granted);
	LIST_INSERT_HEAD(&granted, lock, lf_link);

	while (!LIST_EMPTY(&granted)) {
		lock = LIST_FIRST(&granted);
		LIST_REMOVE(lock, lf_link);

		/*
		 * Skip over locks owned by other processes.  Handle
		 * any locks that overlap and are owned by ourselves.
		 */
		overlap = LIST_FIRST(&state->ls_active);
		for (;;) {
			ovcase = lf_findoverlap(&overlap, lock, SELF);

#ifdef LOCKF_DEBUG
			if (ovcase && (lockf_debug & 2)) {
				printf("lf_setlock: overlap %d", ovcase);
				lf_print("", overlap);
			}
#endif
			/*
			 * Six cases:
			 *	0) no overlap
			 *	1) overlap == lock
			 *	2) overlap contains lock
			 *	3) lock contains overlap
			 *	4) overlap starts before lock
			 *	5) overlap ends after lock
			 */
			switch (ovcase) {
			case 0: /* no overlap */
				break;

			case 1: /* overlap == lock */
				/*
				 * We have already setup the
				 * dependants for the new lock, taking
				 * into account a possible downgrade
				 * or unlock. Remove the old lock.
				 */
				LIST_REMOVE(overlap, lf_link);
				lf_update_dependancies(state, overlap, TRUE,
					&granted);
				lf_free_lock(overlap);
				break;

			case 2: /* overlap contains lock */
				/*
				 * Just split the existing lock.
				 */
				lf_split(state, overlap, lock, &granted);
				break;

			case 3: /* lock contains overlap */
				/*
				 * Delete the overlap and advance to
				 * the next entry in the list.
				 */
				lf = LIST_NEXT(overlap, lf_link);
				LIST_REMOVE(overlap, lf_link);
				lf_update_dependancies(state, overlap, TRUE,
					&granted);
				lf_free_lock(overlap);
				overlap = lf;
				continue;

			case 4: /* overlap starts before lock */
				/*
				 * Just update the overlap end and
				 * move on.
				 */
				lf_set_end(state, overlap, lock->lf_start - 1,
				    &granted);
				overlap = LIST_NEXT(overlap, lf_link);
				continue;

			case 5: /* overlap ends after lock */
				/*
				 * Change the start of overlap and
				 * re-insert.
				 */
				lf_set_start(state, overlap, lock->lf_end + 1,
				    &granted);
				break;
			}
			break;
		}
#ifdef LOCKF_DEBUG
		if (lockf_debug & 1) {
			if (lock->lf_type != F_UNLCK)
				lf_print("lf_activate_lock: activated", lock);
			else
				lf_print("lf_activate_lock: unlocked", lock);
			lf_printlist("lf_activate_lock", lock);
		}
#endif /* LOCKF_DEBUG */
		if (lock->lf_type != F_UNLCK)
			lf_insert_lock(state, lock);
	}
}

/*
 * Cancel a pending lock request, either as a result of a signal or a
 * cancel request for an async lock.
 */
static void
lf_cancel_lock(struct lockf *state, struct lockf_entry *lock)
{
	struct lockf_entry_list granted;

	/*
	 * Note it is theoretically possible that cancelling this lock
	 * may allow some other pending lock to become
	 * active. Consider this case:
	 *
	 * Owner	Action		Result		Dependancies
	 *
	 * A:		lock [0..0]	succeeds
	 * B:		lock [2..2]	succeeds
	 * C:		lock [1..2]	blocked		C->B
	 * D:		lock [0..1]	blocked		C->B,D->A,D->C
	 * A:		unlock [0..0]			C->B,D->C
	 * C:		cancel [1..2]
	 */

	LIST_REMOVE(lock, lf_link);

	/*
	 * Removing out-going edges is simple.
	 */
	sx_xlock(&lf_owner_graph_lock);
	lf_remove_outgoing(lock);
	sx_xunlock(&lf_owner_graph_lock);

	/*
	 * Removing in-coming edges may allow some other lock to
	 * become active - we use lf_update_dependancies to figure
	 * this out.
	 */
	LIST_INIT(&granted);
	lf_update_dependancies(state, lock, TRUE, &granted);
	lf_free_lock(lock);

	/*
	 * Feed any newly active locks to lf_activate_lock.
	 */
	while (!LIST_EMPTY(&granted)) {
		lock = LIST_FIRST(&granted);
		LIST_REMOVE(lock, lf_link);
		lf_activate_lock(state, lock);
	}
}

/*
 * Set a byte-range lock.
 */
static int
lf_setlock(struct lockf *state, struct lockf_entry *lock, struct vnode *vp,
    void **cookiep)
{
	struct lockf_entry *block;
	static char lockstr[] = "lockf";
	int priority, error;

#ifdef LOCKF_DEBUG
	if (lockf_debug & 1)
		lf_print("lf_setlock", lock);
#endif /* LOCKF_DEBUG */

	/*
	 * Set the priority
	 */
	priority = PLOCK;
	if (lock->lf_type == F_WRLCK)
		priority += 4;
	priority |= PCATCH;
	/*
	 * Scan lock list for this file looking for locks that would block us.
	 */
	while ((block = lf_getblock(state, lock))) {
		/*
		 * Free the structure and return if nonblocking.
		 */
		if ((lock->lf_flags & F_WAIT) == 0
		    && lock->lf_async_task == NULL) {
			lf_free_lock(lock);
			error = EAGAIN;
			goto out;
		}

		/*
		 * We are blocked. Create edges to each blocking lock,
		 * checking for deadlock using the owner graph. For
		 * simplicity, we run deadlock detection for all
		 * locks, posix and otherwise.
		 */
		sx_xlock(&lf_owner_graph_lock);
		error = lf_add_outgoing(state, lock);
		sx_xunlock(&lf_owner_graph_lock);

		if (error) {
#ifdef LOCKF_DEBUG
			if (lockf_debug & 1)
				lf_print("lf_setlock: deadlock", lock);
#endif
			lf_free_lock(lock);
			goto out;
		}

		/*
		 * For flock type locks, we must first remove
		 * any shared locks that we hold before we sleep
		 * waiting for an exclusive lock.
		 */
		if ((lock->lf_flags & F_FLOCK) &&
		    lock->lf_type == F_WRLCK) {
			lock->lf_type = F_UNLCK;
			lf_activate_lock(state, lock);
			lock->lf_type = F_WRLCK;
		}
		/*
		 * We have added edges to everything that blocks
		 * us. Sleep until they all go away.
		 */
		LIST_INSERT_HEAD(&state->ls_pending, lock, lf_link);
#ifdef LOCKF_DEBUG
		if (lockf_debug & 1) {
			struct lockf_edge *e;
			LIST_FOREACH(e, &lock->lf_outedges, le_outlink) {
				lf_print("lf_setlock: blocking on", e->le_to);
				lf_printlist("lf_setlock", e->le_to);
			}
		}
#endif /* LOCKF_DEBUG */

		if ((lock->lf_flags & F_WAIT) == 0) {
			/*
			 * The caller requested async notification -
			 * this callback happens when the blocking
			 * lock is released, allowing the caller to
			 * make another attempt to take the lock.
			 */
			*cookiep = (void *) lock;
			error = EINPROGRESS;
			goto out;
		}

		error = sx_sleep(lock, &state->ls_lock, priority, lockstr, 0);
		/*
		 * We may have been awakened by a signal and/or by a
		 * debugger continuing us (in which cases we must
		 * remove our lock graph edges) and/or by another
		 * process releasing a lock (in which case our edges
		 * have already been removed and we have been moved to
		 * the active list).
		 *
		 * Note that it is possible to receive a signal after
		 * we were successfully woken (and moved to the active
		 * list) but before we resumed execution. In this
		 * case, our lf_outedges list will be clear. We
		 * pretend there was no error.
		 *
		 * Note also, if we have been sleeping long enough, we
		 * may now have incoming edges from some newer lock
		 * which is waiting behind us in the queue.
		 */
		if (LIST_EMPTY(&lock->lf_outedges)) {
			error = 0;
		} else {
			lf_cancel_lock(state, lock);
			goto out;
		}
#ifdef LOCKF_DEBUG
		if (lockf_debug & 1) {
			lf_print("lf_setlock: granted", lock);
		}
#endif
		goto out;
	}
	/*
	 * It looks like we are going to grant the lock. First add
	 * edges from any currently pending lock that the new lock
	 * would block.
	 */
	sx_xlock(&lf_owner_graph_lock);
	error = lf_add_incoming(state, lock);
	sx_xunlock(&lf_owner_graph_lock);
	if (error) {
#ifdef LOCKF_DEBUG
		if (lockf_debug & 1)
			lf_print("lf_setlock: deadlock", lock);
#endif
		lf_free_lock(lock);
		goto out;
	}

	/*
	 * No blocks!!  Add the lock.  Note that we will
	 * downgrade or upgrade any overlapping locks this
	 * process already owns.
	 */
	lf_activate_lock(state, lock);
	error = 0;
out:
	return (error);
}

/*
 * Remove a byte-range lock on an inode.
 *
 * Generally, find the lock (or an overlap to that lock)
 * and remove it (or shrink it), then wakeup anyone we can.
 */
static int
lf_clearlock(struct lockf *state, struct lockf_entry *unlock)
{
	struct lockf_entry *overlap;

	overlap = LIST_FIRST(&state->ls_active);

	if (overlap == NOLOCKF)
		return (0);
#ifdef LOCKF_DEBUG
	if (unlock->lf_type != F_UNLCK)
		panic("lf_clearlock: bad type");
	if (lockf_debug & 1)
		lf_print("lf_clearlock", unlock);
#endif /* LOCKF_DEBUG */

	lf_activate_lock(state, unlock);

	return (0);
}

/*
 * Check whether there is a blocking lock, and if so return its
 * details in '*fl'.
 */
static int
lf_getlock(struct lockf *state, struct lockf_entry *lock, struct flock *fl)
{
	struct lockf_entry *block;

#ifdef LOCKF_DEBUG
	if (lockf_debug & 1)
		lf_print("lf_getlock", lock);
#endif /* LOCKF_DEBUG */

	if ((block = lf_getblock(state, lock))) {
		fl->l_type = block->lf_type;
		fl->l_whence = SEEK_SET;
		fl->l_start = block->lf_start;
		if (block->lf_end == OFF_MAX)
			fl->l_len = 0;
		else
			fl->l_len = block->lf_end - block->lf_start + 1;
		fl->l_pid = block->lf_owner->lo_pid;
		fl->l_sysid = block->lf_owner->lo_sysid;
	} else {
		fl->l_type = F_UNLCK;
	}
	return (0);
}

/*
 * Cancel an async lock request.
 */
static int
lf_cancel(struct lockf *state, struct lockf_entry *lock, void *cookie)
{
	struct lockf_entry *reallock;

	/*
	 * We need to match this request with an existing lock
	 * request.
	 */
	LIST_FOREACH(reallock, &state->ls_pending, lf_link) {
		if ((void *) reallock == cookie) {
			/*
			 * Double-check that this lock looks right
			 * (maybe use a rolling ID for the cancel
			 * cookie instead?)
			 */
			if (!(reallock->lf_vnode == lock->lf_vnode
				&& reallock->lf_start == lock->lf_start
				&& reallock->lf_end == lock->lf_end)) {
				return (ENOENT);
			}

			/*
			 * Make sure this lock was async and then just
			 * remove it from its wait lists.
			 */
			if (!reallock->lf_async_task) {
				return (ENOENT);
			}

			/*
			 * Note that since any other thread must take
			 * state->ls_lock before it can possibly
			 * trigger the async callback, we are safe
			 * from a race with lf_wakeup_lock, i.e. we
			 * can free the lock (actually our caller does
			 * this).
			 */
			lf_cancel_lock(state, reallock);
			return (0);
		}
	}

	/*
	 * We didn't find a matching lock - not much we can do here.
	 */
	return (ENOENT);
}

/*
 * Walk the list of locks for an inode and
 * return the first blocking lock.
 */
static struct lockf_entry *
lf_getblock(struct lockf *state, struct lockf_entry *lock)
{
	struct lockf_entry *overlap;

	LIST_FOREACH(overlap, &state->ls_active, lf_link) {
		/*
		 * We may assume that the active list is sorted by
		 * lf_start.
		 */
		if (overlap->lf_start > lock->lf_end)
			break;
		if (!lf_blocks(lock, overlap))
			continue;
		return (overlap);
	}
	return (NOLOCKF);
}

/*
 * Walk the list of locks for an inode to find an overlapping lock (if
 * any) and return a classification of that overlap.
 *
 * Arguments:
 *	*overlap	The place in the lock list to start looking
 *	lock		The lock which is being tested
 *	type		Pass 'SELF' to test only locks with the same
 *			owner as lock, or 'OTHER' to test only locks
 *			with a different owner
 *
 * Returns one of six values:
 *	0) no overlap
 *	1) overlap == lock
 *	2) overlap contains lock
 *	3) lock contains overlap
 *	4) overlap starts before lock
 *	5) overlap ends after lock
 *
 * If there is an overlapping lock, '*overlap' is set to point at the
 * overlapping lock.
 *
 * NOTE: this returns only the FIRST overlapping lock.  There
 *	 may be more than one.
 */
static int
lf_findoverlap(struct lockf_entry **overlap, struct lockf_entry *lock, int type)
{
	struct lockf_entry *lf;
	off_t start, end;
	int res;

	if ((*overlap) == NOLOCKF) {
		return (0);
	}
#ifdef LOCKF_DEBUG
	if (lockf_debug & 2)
		lf_print("lf_findoverlap: looking for overlap in", lock);
#endif /* LOCKF_DEBUG */
	start = lock->lf_start;
	end = lock->lf_end;
	res = 0;
	while (*overlap) {
		lf = *overlap;
		if (lf->lf_start > end)
			break;
		if (((type & SELF) && lf->lf_owner != lock->lf_owner) ||
		    ((type & OTHERS) && lf->lf_owner == lock->lf_owner)) {
			*overlap = LIST_NEXT(lf, lf_link);
			continue;
		}
#ifdef LOCKF_DEBUG
		if (lockf_debug & 2)
			lf_print("\tchecking", lf);
#endif /* LOCKF_DEBUG */
		/*
		 * OK, check for overlap
		 *
		 * Six cases:
		 *	0) no overlap
		 *	1) overlap == lock
		 *	2) overlap contains lock
		 *	3) lock contains overlap
		 *	4) overlap starts before lock
		 *	5) overlap ends after lock
		 */
		if (start > lf->lf_end) {
			/* Case 0 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 2)
				printf("no overlap\n");
#endif /* LOCKF_DEBUG */
			*overlap = LIST_NEXT(lf, lf_link);
			continue;
		}
		if (lf->lf_start == start && lf->lf_end == end) {
			/* Case 1 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 2)
				printf("overlap == lock\n");
#endif /* LOCKF_DEBUG */
			res = 1;
			break;
		}
		if (lf->lf_start <= start && lf->lf_end >= end) {
			/* Case 2 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 2)
				printf("overlap contains lock\n");
#endif /* LOCKF_DEBUG */
			res = 2;
			break;
		}
		if (start <= lf->lf_start && end >= lf->lf_end) {
			/* Case 3 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 2)
				printf("lock contains overlap\n");
#endif /* LOCKF_DEBUG */
			res = 3;
			break;
		}
		if (lf->lf_start < start && lf->lf_end >= start) {
			/* Case 4 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 2)
				printf("overlap starts before lock\n");
#endif /* LOCKF_DEBUG */
			res = 4;
			break;
		}
		if (lf->lf_start > start && lf->lf_end > end) {
			/* Case 5 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 2)
				printf("overlap ends after lock\n");
#endif /* LOCKF_DEBUG */
			res = 5;
			break;
		}
		panic("lf_findoverlap: default");
	}
	return (res);
}

/*
 * Split an the existing 'lock1', based on the extent of the lock
 * described by 'lock2'. The existing lock should cover 'lock2'
 * entirely.
 *
 * Any pending locks which have been been unblocked are added to
 * 'granted'
 */
static void
lf_split(struct lockf *state, struct lockf_entry *lock1,
    struct lockf_entry *lock2, struct lockf_entry_list *granted)
{
	struct lockf_entry *splitlock;

#ifdef LOCKF_DEBUG
	if (lockf_debug & 2) {
		lf_print("lf_split", lock1);
		lf_print("splitting from", lock2);
	}
#endif /* LOCKF_DEBUG */
	/*
	 * Check to see if we don't need to split at all.
	 */
	if (lock1->lf_start == lock2->lf_start) {
		lf_set_start(state, lock1, lock2->lf_end + 1, granted);
		return;
	}
	if (lock1->lf_end == lock2->lf_end) {
		lf_set_end(state, lock1, lock2->lf_start - 1, granted);
		return;
	}
	/*
	 * Make a new lock consisting of the last part of
	 * the encompassing lock.
	 */
	splitlock = lf_alloc_lock(lock1->lf_owner);
	memcpy(splitlock, lock1, sizeof *splitlock);
	if (splitlock->lf_flags & F_REMOTE)
		vref(splitlock->lf_vnode);

	/*
	 * This cannot cause a deadlock since any edges we would add
	 * to splitlock already exist in lock1. We must be sure to add
	 * necessary dependancies to splitlock before we reduce lock1
	 * otherwise we may accidentally grant a pending lock that
	 * was blocked by the tail end of lock1.
	 */
	splitlock->lf_start = lock2->lf_end + 1;
	LIST_INIT(&splitlock->lf_outedges);
	LIST_INIT(&splitlock->lf_inedges);
	sx_xlock(&lf_owner_graph_lock);
	lf_add_incoming(state, splitlock);
	sx_xunlock(&lf_owner_graph_lock);

	lf_set_end(state, lock1, lock2->lf_start - 1, granted);

	/*
	 * OK, now link it in
	 */
	lf_insert_lock(state, splitlock);
}

struct clearlock {
	STAILQ_ENTRY(clearlock) link;
	struct vnode *vp;
	struct flock fl;
};
STAILQ_HEAD(clearlocklist, clearlock);

void
lf_clearremotesys(int sysid)
{
	struct lockf *ls;
	struct lockf_entry *lf;
	struct clearlock *cl;
	struct clearlocklist locks;

	KASSERT(sysid != 0, ("Can't clear local locks with F_UNLCKSYS"));

	/*
	 * In order to keep the locking simple, we iterate over the
	 * active lock lists to build a list of locks that need
	 * releasing. We then call VOP_ADVLOCK for each one in turn.
	 *
	 * We take an extra reference to the vnode for the duration to
	 * make sure it doesn't go away before we are finished.
	 */
	STAILQ_INIT(&locks);
	sx_xlock(&lf_lock_states_lock);
	LIST_FOREACH(ls, &lf_lock_states, ls_link) {
		sx_xlock(&ls->ls_lock);
		LIST_FOREACH(lf, &ls->ls_active, lf_link) {
			if (lf->lf_owner->lo_sysid != sysid)
				continue;

			cl = malloc(sizeof(struct clearlock), M_LOCKF,
			    M_WAITOK);
			cl->vp = lf->lf_vnode;
			vref(cl->vp);
			cl->fl.l_start = lf->lf_start;
			if (lf->lf_end == OFF_MAX)
				cl->fl.l_len = 0;
			else
				cl->fl.l_len =
					lf->lf_end - lf->lf_start + 1;
			cl->fl.l_whence = SEEK_SET;
			cl->fl.l_type = F_UNLCK;
			cl->fl.l_pid = lf->lf_owner->lo_pid;
			cl->fl.l_sysid = sysid;
			STAILQ_INSERT_TAIL(&locks, cl, link);
		}
		sx_xunlock(&ls->ls_lock);
	}
	sx_xunlock(&lf_lock_states_lock);

	while ((cl = STAILQ_FIRST(&locks)) != NULL) {
		STAILQ_REMOVE_HEAD(&locks, link);
		VOP_ADVLOCK(cl->vp, 0, F_UNLCK, &cl->fl, F_REMOTE);
		vrele(cl->vp);
		free(cl, M_LOCKF);
	}
}

int
lf_countlocks(int sysid)
{
	int i;
	struct lock_owner *lo;
	int count;

	count = 0;
	sx_xlock(&lf_lock_owners_lock);
	for (i = 0; i < LOCK_OWNER_HASH_SIZE; i++)
		LIST_FOREACH(lo, &lf_lock_owners[i], lo_link)
			if (lo->lo_sysid == sysid)
				count += lo->lo_refs;
	sx_xunlock(&lf_lock_owners_lock);

	return (count);
}

#ifdef LOCKF_DEBUG

/*
 * Return non-zero if y is reachable from x using a brute force
 * search. If reachable and path is non-null, return the route taken
 * in path.
 */
static int
graph_reaches(struct owner_vertex *x, struct owner_vertex *y,
    struct owner_vertex_list *path)
{
	struct owner_edge *e;

	if (x == y) {
		if (path)
			TAILQ_INSERT_HEAD(path, x, v_link);
		return 1;
	}

	LIST_FOREACH(e, &x->v_outedges, e_outlink) {
		if (graph_reaches(e->e_to, y, path)) {
			if (path)
				TAILQ_INSERT_HEAD(path, x, v_link);
			return 1;
		}
	}
	return 0;
}

/*
 * Perform consistency checks on the graph. Make sure the values of
 * v_order are correct. If checkorder is non-zero, check no vertex can
 * reach any other vertex with a smaller order.
 */
static void
graph_check(struct owner_graph *g, int checkorder)
{
	int i, j;

	for (i = 0; i < g->g_size; i++) {
		if (!g->g_vertices[i]->v_owner)
			continue;
		KASSERT(g->g_vertices[i]->v_order == i,
		    ("lock graph vertices disordered"));
		if (checkorder) {
			for (j = 0; j < i; j++) {
				if (!g->g_vertices[j]->v_owner)
					continue;
				KASSERT(!graph_reaches(g->g_vertices[i],
					g->g_vertices[j], NULL),
				    ("lock graph vertices disordered"));
			}
		}
	}
}

static void
graph_print_vertices(struct owner_vertex_list *set)
{
	struct owner_vertex *v;

	printf("{ ");
	TAILQ_FOREACH(v, set, v_link) {
		printf("%d:", v->v_order);
		lf_print_owner(v->v_owner);
		if (TAILQ_NEXT(v, v_link))
			printf(", ");
	}
	printf(" }\n");
}

#endif

/*
 * Calculate the sub-set of vertices v from the affected region [y..x]
 * where v is reachable from y. Return -1 if a loop was detected
 * (i.e. x is reachable from y, otherwise the number of vertices in
 * this subset.
 */
static int
graph_delta_forward(struct owner_graph *g, struct owner_vertex *x,
    struct owner_vertex *y, struct owner_vertex_list *delta)
{
	uint32_t gen;
	struct owner_vertex *v;
	struct owner_edge *e;
	int n;

	/*
	 * We start with a set containing just y. Then for each vertex
	 * v in the set so far unprocessed, we add each vertex that v
	 * has an out-edge to and that is within the affected region
	 * [y..x]. If we see the vertex x on our travels, stop
	 * immediately.
	 */
	TAILQ_INIT(delta);
	TAILQ_INSERT_TAIL(delta, y, v_link);
	v = y;
	n = 1;
	gen = g->g_gen;
	while (v) {
		LIST_FOREACH(e, &v->v_outedges, e_outlink) {
			if (e->e_to == x)
				return -1;
			if (e->e_to->v_order < x->v_order
			    && e->e_to->v_gen != gen) {
				e->e_to->v_gen = gen;
				TAILQ_INSERT_TAIL(delta, e->e_to, v_link);
				n++;
			}
		}
		v = TAILQ_NEXT(v, v_link);
	}

	return (n);
}

/*
 * Calculate the sub-set of vertices v from the affected region [y..x]
 * where v reaches x. Return the number of vertices in this subset.
 */
static int
graph_delta_backward(struct owner_graph *g, struct owner_vertex *x,
    struct owner_vertex *y, struct owner_vertex_list *delta)
{
	uint32_t gen;
	struct owner_vertex *v;
	struct owner_edge *e;
	int n;

	/*
	 * We start with a set containing just x. Then for each vertex
	 * v in the set so far unprocessed, we add each vertex that v
	 * has an in-edge from and that is within the affected region
	 * [y..x].
	 */
	TAILQ_INIT(delta);
	TAILQ_INSERT_TAIL(delta, x, v_link);
	v = x;
	n = 1;
	gen = g->g_gen;
	while (v) {
		LIST_FOREACH(e, &v->v_inedges, e_inlink) {
			if (e->e_from->v_order > y->v_order
			    && e->e_from->v_gen != gen) {
				e->e_from->v_gen = gen;
				TAILQ_INSERT_HEAD(delta, e->e_from, v_link);
				n++;
			}
		}
		v = TAILQ_PREV(v, owner_vertex_list, v_link);
	}

	return (n);
}

static int
graph_add_indices(int *indices, int n, struct owner_vertex_list *set)
{
	struct owner_vertex *v;
	int i, j;

	TAILQ_FOREACH(v, set, v_link) {
		for (i = n;
		     i > 0 && indices[i - 1] > v->v_order; i--)
			;
		for (j = n - 1; j >= i; j--)
			indices[j + 1] = indices[j];
		indices[i] = v->v_order;
		n++;
	}

	return (n);
}

static int
graph_assign_indices(struct owner_graph *g, int *indices, int nextunused,
    struct owner_vertex_list *set)
{
	struct owner_vertex *v, *vlowest;

	while (!TAILQ_EMPTY(set)) {
		vlowest = NULL;
		TAILQ_FOREACH(v, set, v_link) {
			if (!vlowest || v->v_order < vlowest->v_order)
				vlowest = v;
		}
		TAILQ_REMOVE(set, vlowest, v_link);
		vlowest->v_order = indices[nextunused];
		g->g_vertices[vlowest->v_order] = vlowest;
		nextunused++;
	}

	return (nextunused);
}

static int
graph_add_edge(struct owner_graph *g, struct owner_vertex *x,
    struct owner_vertex *y)
{
	struct owner_edge *e;
	struct owner_vertex_list deltaF, deltaB;
	int nF, nB, n, vi, i;
	int *indices;

	sx_assert(&lf_owner_graph_lock, SX_XLOCKED);

	LIST_FOREACH(e, &x->v_outedges, e_outlink) {
		if (e->e_to == y) {
			e->e_refs++;
			return (0);
		}
	}

#ifdef LOCKF_DEBUG
	if (lockf_debug & 8) {
		printf("adding edge %d:", x->v_order);
		lf_print_owner(x->v_owner);
		printf(" -> %d:", y->v_order);
		lf_print_owner(y->v_owner);
		printf("\n");
	}
#endif
	if (y->v_order < x->v_order) {
		/*
		 * The new edge violates the order. First find the set
		 * of affected vertices reachable from y (deltaF) and
		 * the set of affect vertices affected that reach x
		 * (deltaB), using the graph generation number to
		 * detect whether we have visited a given vertex
		 * already. We re-order the graph so that each vertex
		 * in deltaB appears before each vertex in deltaF.
		 *
		 * If x is a member of deltaF, then the new edge would
		 * create a cycle. Otherwise, we may assume that
		 * deltaF and deltaB are disjoint.
		 */
		g->g_gen++;
		if (g->g_gen == 0) {
			/*
			 * Generation wrap.
			 */
			for (vi = 0; vi < g->g_size; vi++) {
				g->g_vertices[vi]->v_gen = 0;
			}
			g->g_gen++;
		}
		nF = graph_delta_forward(g, x, y, &deltaF);
		if (nF < 0) {
#ifdef LOCKF_DEBUG
			if (lockf_debug & 8) {
				struct owner_vertex_list path;
				printf("deadlock: ");
				TAILQ_INIT(&path);
				graph_reaches(y, x, &path);
				graph_print_vertices(&path);
			}
#endif
			return (EDEADLK);
		}

#ifdef LOCKF_DEBUG
		if (lockf_debug & 8) {
			printf("re-ordering graph vertices\n");
			printf("deltaF = ");
			graph_print_vertices(&deltaF);
		}
#endif

		nB = graph_delta_backward(g, x, y, &deltaB);

#ifdef LOCKF_DEBUG
		if (lockf_debug & 8) {
			printf("deltaB = ");
			graph_print_vertices(&deltaB);
		}
#endif

		/*
		 * We first build a set of vertex indices (vertex
		 * order values) that we may use, then we re-assign
		 * orders first to those vertices in deltaB, then to
		 * deltaF. Note that the contents of deltaF and deltaB
		 * may be partially disordered - we perform an
		 * insertion sort while building our index set.
		 */
		indices = g->g_indexbuf;
		n = graph_add_indices(indices, 0, &deltaF);
		graph_add_indices(indices, n, &deltaB);

		/*
		 * We must also be sure to maintain the relative
		 * ordering of deltaF and deltaB when re-assigning
		 * vertices. We do this by iteratively removing the
		 * lowest ordered element from the set and assigning
		 * it the next value from our new ordering.
		 */
		i = graph_assign_indices(g, indices, 0, &deltaB);
		graph_assign_indices(g, indices, i, &deltaF);

#ifdef LOCKF_DEBUG
		if (lockf_debug & 8) {
			struct owner_vertex_list set;
			TAILQ_INIT(&set);
			for (i = 0; i < nB + nF; i++)
				TAILQ_INSERT_TAIL(&set,
				    g->g_vertices[indices[i]], v_link);
			printf("new ordering = ");
			graph_print_vertices(&set);
		}
#endif
	}

	KASSERT(x->v_order < y->v_order, ("Failed to re-order graph"));

#ifdef LOCKF_DEBUG
	if (lockf_debug & 8) {
		graph_check(g, TRUE);
	}
#endif

	e = malloc(sizeof(struct owner_edge), M_LOCKF, M_WAITOK);

	LIST_INSERT_HEAD(&x->v_outedges, e, e_outlink);
	LIST_INSERT_HEAD(&y->v_inedges, e, e_inlink);
	e->e_refs = 1;
	e->e_from = x;
	e->e_to = y;

	return (0);
}

/*
 * Remove an edge x->y from the graph.
 */
static void
graph_remove_edge(struct owner_graph *g, struct owner_vertex *x,
    struct owner_vertex *y)
{
	struct owner_edge *e;

	sx_assert(&lf_owner_graph_lock, SX_XLOCKED);

	LIST_FOREACH(e, &x->v_outedges, e_outlink) {
		if (e->e_to == y)
			break;
	}
	KASSERT(e, ("Removing non-existent edge from deadlock graph"));

	e->e_refs--;
	if (e->e_refs == 0) {
#ifdef LOCKF_DEBUG
		if (lockf_debug & 8) {
			printf("removing edge %d:", x->v_order);
			lf_print_owner(x->v_owner);
			printf(" -> %d:", y->v_order);
			lf_print_owner(y->v_owner);
			printf("\n");
		}
#endif
		LIST_REMOVE(e, e_outlink);
		LIST_REMOVE(e, e_inlink);
		free(e, M_LOCKF);
	}
}

/*
 * Allocate a vertex from the free list. Return ENOMEM if there are
 * none.
 */
static struct owner_vertex *
graph_alloc_vertex(struct owner_graph *g, struct lock_owner *lo)
{
	struct owner_vertex *v;

	sx_assert(&lf_owner_graph_lock, SX_XLOCKED);

	v = malloc(sizeof(struct owner_vertex), M_LOCKF, M_WAITOK);
	if (g->g_size == g->g_space) {
		g->g_vertices = realloc(g->g_vertices,
		    2 * g->g_space * sizeof(struct owner_vertex *),
		    M_LOCKF, M_WAITOK);
		free(g->g_indexbuf, M_LOCKF);
		g->g_indexbuf = malloc(2 * g->g_space * sizeof(int),
		    M_LOCKF, M_WAITOK);
		g->g_space = 2 * g->g_space;
	}
	v->v_order = g->g_size;
	v->v_gen = g->g_gen;
	g->g_vertices[g->g_size] = v;
	g->g_size++;

	LIST_INIT(&v->v_outedges);
	LIST_INIT(&v->v_inedges);
	v->v_owner = lo;

	return (v);
}

static void
graph_free_vertex(struct owner_graph *g, struct owner_vertex *v)
{
	struct owner_vertex *w;
	int i;

	sx_assert(&lf_owner_graph_lock, SX_XLOCKED);

	KASSERT(LIST_EMPTY(&v->v_outedges), ("Freeing vertex with edges"));
	KASSERT(LIST_EMPTY(&v->v_inedges), ("Freeing vertex with edges"));

	/*
	 * Remove from the graph's array and close up the gap,
	 * renumbering the other vertices.
	 */
	for (i = v->v_order + 1; i < g->g_size; i++) {
		w = g->g_vertices[i];
		w->v_order--;
		g->g_vertices[i - 1] = w;
	}
	g->g_size--;

	free(v, M_LOCKF);
}

static struct owner_graph *
graph_init(struct owner_graph *g)
{

	g->g_vertices = malloc(10 * sizeof(struct owner_vertex *),
	    M_LOCKF, M_WAITOK);
	g->g_size = 0;
	g->g_space = 10;
	g->g_indexbuf = malloc(g->g_space * sizeof(int), M_LOCKF, M_WAITOK);
	g->g_gen = 0;

	return (g);
}

#ifdef LOCKF_DEBUG
/*
 * Print description of a lock owner
 */
static void
lf_print_owner(struct lock_owner *lo)
{

	if (lo->lo_flags & F_REMOTE) {
		printf("remote pid %d, system %d",
		    lo->lo_pid, lo->lo_sysid);
	} else if (lo->lo_flags & F_FLOCK) {
		printf("file %p", lo->lo_id);
	} else {
		printf("local pid %d", lo->lo_pid);
	}
}

/*
 * Print out a lock.
 */
static void
lf_print(char *tag, struct lockf_entry *lock)
{

	printf("%s: lock %p for ", tag, (void *)lock);
	lf_print_owner(lock->lf_owner);
	if (lock->lf_inode != (struct inode *)0)
		printf(" in ino %ju on dev <%s>,",
		    (uintmax_t)lock->lf_inode->i_number,
		    devtoname(lock->lf_inode->i_dev));
	printf(" %s, start %jd, end ",
	    lock->lf_type == F_RDLCK ? "shared" :
	    lock->lf_type == F_WRLCK ? "exclusive" :
	    lock->lf_type == F_UNLCK ? "unlock" : "unknown",
	    (intmax_t)lock->lf_start);
	if (lock->lf_end == OFF_MAX)
		printf("EOF");
	else
		printf("%jd", (intmax_t)lock->lf_end);
	if (!LIST_EMPTY(&lock->lf_outedges))
		printf(" block %p\n",
		    (void *)LIST_FIRST(&lock->lf_outedges)->le_to);
	else
		printf("\n");
}

static void
lf_printlist(char *tag, struct lockf_entry *lock)
{
	struct lockf_entry *lf, *blk;
	struct lockf_edge *e;

	if (lock->lf_inode == (struct inode *)0)
		return;

	printf("%s: Lock list for ino %ju on dev <%s>:\n",
	    tag, (uintmax_t)lock->lf_inode->i_number,
	    devtoname(lock->lf_inode->i_dev));
	LIST_FOREACH(lf, &lock->lf_inode->i_lockf->ls_active, lf_link) {
		printf("\tlock %p for ",(void *)lf);
		lf_print_owner(lock->lf_owner);
		printf(", %s, start %jd, end %jd",
		    lf->lf_type == F_RDLCK ? "shared" :
		    lf->lf_type == F_WRLCK ? "exclusive" :
		    lf->lf_type == F_UNLCK ? "unlock" :
		    "unknown", (intmax_t)lf->lf_start, (intmax_t)lf->lf_end);
		LIST_FOREACH(e, &lf->lf_outedges, le_outlink) {
			blk = e->le_to;
			printf("\n\t\tlock request %p for ", (void *)blk);
			lf_print_owner(blk->lf_owner);
			printf(", %s, start %jd, end %jd",
			    blk->lf_type == F_RDLCK ? "shared" :
			    blk->lf_type == F_WRLCK ? "exclusive" :
			    blk->lf_type == F_UNLCK ? "unlock" :
			    "unknown", (intmax_t)blk->lf_start,
			    (intmax_t)blk->lf_end);
			if (!LIST_EMPTY(&blk->lf_inedges))
				panic("lf_printlist: bad list");
		}
		printf("\n");
	}
}
#endif /* LOCKF_DEBUG */