87d42128989062eaad512102b80dc8e8fd7ec2aa
[dragonfly.git] / sys / kern / vfs_rangelock.c
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  *
34  * $DragonFly: src/sys/kern/vfs_rangelock.c,v 1.2 2006/12/23 00:35:04 swildner Exp $
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)
141                 kprintf("warning: conflicted lock vp %p %lld,%lld blocked\n",
142                     vp, vr->vr_offset, vr->vr_length);
143             warned = 1;
144         }
145         conflicted = vrange_lock_conflicted(vp, vr);
146     }
147     if (warned) {
148         kprintf("waring: conflicted lock vp %p %lld,%lld unblocked\n",
149             vp, vr->vr_offset, vr->vr_length);
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