[dragonfly.git] / sys / kern / vfs_rangelock.c

/*
 * Copyright (c) 2004 The DragonFly Project.  All rights reserved.
 * 
 * This code is derived from software contributed to The DragonFly Project
 * by Matthew Dillon <dillon@backplane.com>
 * 
 * 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.
 * 3. Neither the name of The DragonFly Project 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 COPYRIGHT HOLDERS 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
 * COPYRIGHT HOLDERS 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.
 *
 * $DragonFly: src/sys/kern/vfs_rangelock.c,v 1.2 2006/12/23 00:35:04 swildner Exp $
 */
/*
 * This module implements hard range locks for files and directories.  It is
 * not to be confused with the UNIX advisory lock mechanism.  This module
 * will allow the kernel and VFS to break large I/O requests into smaller
 * pieces without losing atomicy guarentees and, eventually, this module will
 * be responsible for providing hooks for remote cache coherency protocols
 * as well.
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/buf.h>
#include <sys/conf.h>
#include <sys/kernel.h>
#include <sys/lock.h>
#include <sys/malloc.h>
#include <sys/mount.h>
#include <sys/unistd.h>
#include <sys/vnode.h>
#include <sys/poll.h>

#include <machine/limits.h>

#include <vm/vm.h>
#include <vm/vm_object.h>
#include <vm/vm_page.h>
#include <vm/vm_pager.h>
#include <vm/vnode_pager.h>

static void vrange_lock_overlapped(struct vnode *vp, 
			struct vrangelock *vr, struct vrangelock *scan);
static int vrange_lock_conflicted(struct vnode *vp, struct vrangelock *vr);

/*
 * Lock a range within a vnode.
 *
 * The lock list is sorted by vr_offset.
 */
void
vrange_lock(struct vnode *vp, struct vrangelock *vr)
{
    struct vrangelock *scan;
    off_t eoff;

    eoff = vr->vr_offset + vr->vr_length;

    KKASSERT((vr->vr_flags & RNGL_ONLIST) == 0);
    vr->vr_flags |= RNGL_ONLIST;

    TAILQ_FOREACH(scan, &vp->v_range.vh_list, vr_node) {
	/*
	 * If the new element is entirely in front of the scan element
	 * we are done.  If it is entirely beyond the scan element we
	 * loop.  Otherwise an overlap has occured.
	 */
	if (eoff <= scan->vr_offset) {
	    TAILQ_INSERT_BEFORE(scan, vr, vr_node);
	    return;
	}
	if (vr->vr_offset >= scan->vr_offset + scan->vr_length)
	    continue;
	vrange_lock_overlapped(vp, vr, scan);
    }
    TAILQ_INSERT_TAIL(&vp->v_range.vh_list, vr, vr_node);
}

/*
 * An overlap occured.  The request is still inserted sorted based on
 * vr_offset but we must also scan the conflict space and block while
 * conflicts exist.
 */
static void
vrange_lock_overlapped(struct vnode *vp, 
			struct vrangelock *vr, struct vrangelock *scan)
{
    int conflicted = 0;
    int inserted = 0;
    int warned = 0;
    off_t eoff;

    eoff = vr->vr_offset + vr->vr_length;

    while (scan->vr_offset < eoff) {
	if ((vr->vr_flags & scan->vr_flags & RNGL_SHARED) == 0) {
	    scan->vr_flags |= RNGL_CHECK;
	    vr->vr_flags |= RNGL_WAITING;
	    conflicted = 1;
	}
	if (inserted == 0 && vr->vr_offset < scan->vr_offset) {
	    TAILQ_INSERT_BEFORE(scan, vr, vr_node);
	    inserted = 1;
	}
	if ((scan = TAILQ_NEXT(scan, vr_node)) == NULL) {
	    if (inserted == 0)
		TAILQ_INSERT_TAIL(&vp->v_range.vh_list, vr, vr_node);
	    break;
	}
    }

    /*
     * sleep until the conflict has been resolved.
     */
    while (conflicted) {
	if (tsleep(&vp->v_range.vh_list, 0, "vrnglk", hz * 3) == EWOULDBLOCK) {
	    if (warned == 0)
		kprintf("warning: conflicted lock vp %p %lld,%lld blocked\n",
		    vp, (long long)vr->vr_offset, (long long)vr->vr_length);
	    warned = 1;
	}
	conflicted = vrange_lock_conflicted(vp, vr);
    }
    if (warned) {
	kprintf("waring: conflicted lock vp %p %lld,%lld unblocked\n",
	    vp, (long long)vr->vr_offset, (long long)vr->vr_length);
    }
}

/*
 * Check for conflicts by scanning both forwards and backwards from the
 * node in question.  The list is sorted by vr_offset but ending offsets
 * may vary.  Because of this, the reverse scan cannot stop early.
 *
 * Return 0 on success, 1 if the lock is still conflicted.  We do not
 * check elements that are waiting as that might result in a deadlock.
 * We can stop the moment we hit a conflict.
 */
static int
vrange_lock_conflicted(struct vnode *vp, struct vrangelock *vr)
{
    struct vrangelock *scan;
    off_t eoff;

    eoff = vr->vr_offset + vr->vr_length;

    KKASSERT(vr->vr_flags & RNGL_WAITING);
    scan = vr;
    while ((scan = TAILQ_PREV(scan, vrangelock_list, vr_node)) != NULL) {
	if (scan->vr_flags & RNGL_WAITING)
		continue;
	if (scan->vr_offset + scan->vr_length > vr->vr_offset) {
	    if ((vr->vr_flags & scan->vr_flags & RNGL_SHARED) == 0) {
		scan->vr_flags |= RNGL_CHECK;
		return(1);
	    }
	}
    }
    scan = vr;
    while ((scan = TAILQ_NEXT(scan, vr_node)) != NULL) {
	if (eoff <= scan->vr_offset)
	    break;
	if (scan->vr_flags & RNGL_WAITING)
	    continue;
	if ((vr->vr_flags & scan->vr_flags & RNGL_SHARED) == 0) {
	    scan->vr_flags |= RNGL_CHECK;
	    return(1);
	}
    }
    vr->vr_flags &= ~RNGL_WAITING;
    return(0);
}

void
vrange_unlock(struct vnode *vp, struct vrangelock *vr)
{
    KKASSERT((vr->vr_flags & RNGL_ONLIST) != 0);
    vr->vr_flags &= ~RNGL_ONLIST;
    TAILQ_REMOVE(&vp->v_range.vh_list, vr, vr_node);
    if (vr->vr_flags & RNGL_CHECK) {
	vr->vr_flags &= ~RNGL_CHECK;
	wakeup(&vp->v_range.vh_list);
    }
}
Commit	Line	Data
6ddb7618 MD	1	/*
	2	* Copyright (c) 2004 The DragonFly Project. All rights reserved.
	3	*
	4	* This code is derived from software contributed to The DragonFly Project
	5	* by Matthew Dillon <dillon@backplane.com>
	6	*
	7	* Redistribution and use in source and binary forms, with or without
	8	* modification, are permitted provided that the following conditions
	9	* are met:
	10	*
	11	* 1. Redistributions of source code must retain the above copyright
	12	* notice, this list of conditions and the following disclaimer.
	13	* 2. Redistributions in binary form must reproduce the above copyright
	14	* notice, this list of conditions and the following disclaimer in
	15	* the documentation and/or other materials provided with the
	16	* distribution.
	17	* 3. Neither the name of The DragonFly Project nor the names of its
	18	* contributors may be used to endorse or promote products derived
	19	* from this software without specific, prior written permission.
	20	*
	21	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	22	* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	23	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
	24	* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
	25	* COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
	26	* INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
	27	* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
	28	* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
	29	* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
	30	* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
	31	* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	32	* SUCH DAMAGE.
	33	*
6ea70f76	34	* $DragonFly: src/sys/kern/vfs_rangelock.c,v 1.2 2006/12/23 00:35:04 swildner Exp $
6ddb7618 MD	35	*/
	36	/*
	37	* This module implements hard range locks for files and directories. It is
	38	* not to be confused with the UNIX advisory lock mechanism. This module
	39	* will allow the kernel and VFS to break large I/O requests into smaller
	40	* pieces without losing atomicy guarentees and, eventually, this module will
	41	* be responsible for providing hooks for remote cache coherency protocols
	42	* as well.
	43	*/
	44
	45	#include <sys/param.h>
	46	#include <sys/systm.h>
	47	#include <sys/buf.h>
	48	#include <sys/conf.h>
	49	#include <sys/kernel.h>
	50	#include <sys/lock.h>
	51	#include <sys/malloc.h>
	52	#include <sys/mount.h>
	53	#include <sys/unistd.h>
	54	#include <sys/vnode.h>
	55	#include <sys/poll.h>
	56
	57	#include <machine/limits.h>
	58
	59	#include <vm/vm.h>
	60	#include <vm/vm_object.h>
	61	#include <vm/vm_page.h>
	62	#include <vm/vm_pager.h>
	63	#include <vm/vnode_pager.h>
	64
	65	static void vrange_lock_overlapped(struct vnode *vp,
	66	struct vrangelock vr, struct vrangelock scan);
	67	static int vrange_lock_conflicted(struct vnode vp, struct vrangelock vr);
	68
	69	/*
	70	* Lock a range within a vnode.
	71	*
	72	* The lock list is sorted by vr_offset.
	73	*/
	74	void
	75	vrange_lock(struct vnode vp, struct vrangelock vr)
	76	{
	77	struct vrangelock *scan;
	78	off_t eoff;
	79
	80	eoff = vr->vr_offset + vr->vr_length;
	81
	82	KKASSERT((vr->vr_flags & RNGL_ONLIST) == 0);
	83	vr->vr_flags \|= RNGL_ONLIST;
	84
	85	TAILQ_FOREACH(scan, &vp->v_range.vh_list, vr_node) {
	86	/*
	87	* If the new element is entirely in front of the scan element
	88	* we are done. If it is entirely beyond the scan element we
	89	* loop. Otherwise an overlap has occured.
	90	*/
	91	if (eoff <= scan->vr_offset) {
	92	TAILQ_INSERT_BEFORE(scan, vr, vr_node);
	93	return;
	94	}
	95	if (vr->vr_offset >= scan->vr_offset + scan->vr_length)
	96	continue;
	97	vrange_lock_overlapped(vp, vr, scan);
	98	}
99	TAILQ_INSERT_TAIL(&vp->v_range.vh_list, vr, vr_node);
100	}
101
102	/*
103	* An overlap occured. The request is still inserted sorted based on
104	* vr_offset but we must also scan the conflict space and block while
105	* conflicts exist.
106	*/
107	static void
108	vrange_lock_overlapped(struct vnode *vp,
109	struct vrangelock vr, struct vrangelock scan)
110	{
111	int conflicted = 0;
112	int inserted = 0;
113	int warned = 0;
114	off_t eoff;
115
116	eoff = vr->vr_offset + vr->vr_length;
117
118	while (scan->vr_offset < eoff) {
119	if ((vr->vr_flags & scan->vr_flags & RNGL_SHARED) == 0) {
120	scan->vr_flags \|= RNGL_CHECK;
121	vr->vr_flags \|= RNGL_WAITING;
122	conflicted = 1;
123	}
124	if (inserted == 0 && vr->vr_offset < scan->vr_offset) {
125	TAILQ_INSERT_BEFORE(scan, vr, vr_node);
126	inserted = 1;
127	}
128	if ((scan = TAILQ_NEXT(scan, vr_node)) == NULL) {
129	if (inserted == 0)
130	TAILQ_INSERT_TAIL(&vp->v_range.vh_list, vr, vr_node);
131	break;
132	}
133	}
134
135	/*
136	* sleep until the conflict has been resolved.
137	*/
138	while (conflicted) {
139	if (tsleep(&vp->v_range.vh_list, 0, "vrnglk", hz * 3) == EWOULDBLOCK) {
140	if (warned == 0)
6ea70f76	141	kprintf("warning: conflicted lock vp %p %lld,%lld blocked\n",
973c11b9	142	vp, (long long)vr->vr_offset, (long long)vr->vr_length);
6ddb7618 MD	143	warned = 1;
	144	}
	145	conflicted = vrange_lock_conflicted(vp, vr);
	146	}
	147	if (warned) {
6ea70f76	148	kprintf("waring: conflicted lock vp %p %lld,%lld unblocked\n",
973c11b9	149	vp, (long long)vr->vr_offset, (long long)vr->vr_length);
6ddb7618 MD	150	}
	151	}
	152
	153	/*
	154	* Check for conflicts by scanning both forwards and backwards from the
	155	* node in question. The list is sorted by vr_offset but ending offsets
	156	* may vary. Because of this, the reverse scan cannot stop early.
	157	*
	158	* Return 0 on success, 1 if the lock is still conflicted. We do not
	159	* check elements that are waiting as that might result in a deadlock.
	160	* We can stop the moment we hit a conflict.
	161	*/
	162	static int
	163	vrange_lock_conflicted(struct vnode vp, struct vrangelock vr)
	164	{
	165	struct vrangelock *scan;
	166	off_t eoff;
	167
	168	eoff = vr->vr_offset + vr->vr_length;
	169
	170	KKASSERT(vr->vr_flags & RNGL_WAITING);
	171	scan = vr;
	172	while ((scan = TAILQ_PREV(scan, vrangelock_list, vr_node)) != NULL) {
	173	if (scan->vr_flags & RNGL_WAITING)
	174	continue;
	175	if (scan->vr_offset + scan->vr_length > vr->vr_offset) {
	176	if ((vr->vr_flags & scan->vr_flags & RNGL_SHARED) == 0) {
	177	scan->vr_flags \|= RNGL_CHECK;
	178	return(1);
	179	}
	180	}
	181	}
	182	scan = vr;
	183	while ((scan = TAILQ_NEXT(scan, vr_node)) != NULL) {
	184	if (eoff <= scan->vr_offset)
	185	break;
	186	if (scan->vr_flags & RNGL_WAITING)
	187	continue;
	188	if ((vr->vr_flags & scan->vr_flags & RNGL_SHARED) == 0) {
	189	scan->vr_flags \|= RNGL_CHECK;
	190	return(1);
	191	}
	192	}
	193	vr->vr_flags &= ~RNGL_WAITING;
	194	return(0);
	195	}
	196
	197	void
	198	vrange_unlock(struct vnode vp, struct vrangelock vr)
	199	{
	200	KKASSERT((vr->vr_flags & RNGL_ONLIST) != 0);
	201	vr->vr_flags &= ~RNGL_ONLIST;
	202	TAILQ_REMOVE(&vp->v_range.vh_list, vr, vr_node);
	203	if (vr->vr_flags & RNGL_CHECK) {
	204	vr->vr_flags &= ~RNGL_CHECK;
	205	wakeup(&vp->v_range.vh_list);
	206	}
	207	}
	208