vfs_lockf.c revision 1.38 1 1.38 christos /* $NetBSD: vfs_lockf.c,v 1.38 2005/03/20 19:16:33 christos Exp $ */
2 1.5 cgd
3 1.1 ws /*
4 1.4 mycroft * Copyright (c) 1982, 1986, 1989, 1993
5 1.4 mycroft * The Regents of the University of California. All rights reserved.
6 1.1 ws *
7 1.1 ws * This code is derived from software contributed to Berkeley by
8 1.1 ws * Scooter Morris at Genentech Inc.
9 1.1 ws *
10 1.1 ws * Redistribution and use in source and binary forms, with or without
11 1.1 ws * modification, are permitted provided that the following conditions
12 1.1 ws * are met:
13 1.1 ws * 1. Redistributions of source code must retain the above copyright
14 1.1 ws * notice, this list of conditions and the following disclaimer.
15 1.1 ws * 2. Redistributions in binary form must reproduce the above copyright
16 1.1 ws * notice, this list of conditions and the following disclaimer in the
17 1.1 ws * documentation and/or other materials provided with the distribution.
18 1.33 agc * 3. Neither the name of the University nor the names of its contributors
19 1.1 ws * may be used to endorse or promote products derived from this software
20 1.1 ws * without specific prior written permission.
21 1.1 ws *
22 1.1 ws * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 1.1 ws * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 1.1 ws * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 1.1 ws * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 1.1 ws * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 1.1 ws * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 1.1 ws * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 1.1 ws * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 1.1 ws * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 1.1 ws * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 1.1 ws * SUCH DAMAGE.
33 1.1 ws *
34 1.12 fvdl * @(#)ufs_lockf.c 8.4 (Berkeley) 10/26/94
35 1.1 ws */
36 1.18 lukem
37 1.18 lukem #include <sys/cdefs.h>
38 1.38 christos __KERNEL_RCSID(0, "$NetBSD: vfs_lockf.c,v 1.38 2005/03/20 19:16:33 christos Exp $");
39 1.1 ws
40 1.1 ws #include <sys/param.h>
41 1.1 ws #include <sys/systm.h>
42 1.1 ws #include <sys/kernel.h>
43 1.1 ws #include <sys/file.h>
44 1.1 ws #include <sys/proc.h>
45 1.1 ws #include <sys/vnode.h>
46 1.35 simonb #include <sys/pool.h>
47 1.1 ws #include <sys/fcntl.h>
48 1.1 ws #include <sys/lockf.h>
49 1.22 thorpej
50 1.35 simonb POOL_INIT(lockfpool, sizeof(struct lockf), 0, 0, 0, "lockfpl",
51 1.35 simonb &pool_allocator_nointr);
52 1.1 ws
53 1.1 ws /*
54 1.6 mycroft * This variable controls the maximum number of processes that will
55 1.6 mycroft * be checked in doing deadlock detection.
56 1.6 mycroft */
57 1.6 mycroft int maxlockdepth = MAXDEPTH;
58 1.6 mycroft
59 1.6 mycroft #ifdef LOCKF_DEBUG
60 1.6 mycroft int lockf_debug = 0;
61 1.6 mycroft #endif
62 1.6 mycroft
63 1.6 mycroft #define NOLOCKF (struct lockf *)0
64 1.6 mycroft #define SELF 0x1
65 1.6 mycroft #define OTHERS 0x2
66 1.6 mycroft
67 1.27 yamt static int lf_clearlock(struct lockf *, struct lockf **);
68 1.25 yamt static int lf_findoverlap(struct lockf *,
69 1.25 yamt struct lockf *, int, struct lockf ***, struct lockf **);
70 1.25 yamt static struct lockf *lf_getblock(struct lockf *);
71 1.25 yamt static int lf_getlock(struct lockf *, struct flock *);
72 1.27 yamt static int lf_setlock(struct lockf *, struct lockf **, struct simplelock *);
73 1.27 yamt static void lf_split(struct lockf *, struct lockf *, struct lockf **);
74 1.25 yamt static void lf_wakelock(struct lockf *);
75 1.38 christos static struct lockf *lf_alloc(uid_t, int);
76 1.38 christos static void lf_free(struct lockf *);
77 1.38 christos
78 1.24 yamt
79 1.24 yamt #ifdef LOCKF_DEBUG
80 1.25 yamt static void lf_print(char *, struct lockf *);
81 1.25 yamt static void lf_printlist(char *, struct lockf *);
82 1.24 yamt #endif
83 1.24 yamt
84 1.6 mycroft /*
85 1.16 sommerfe * XXX TODO
86 1.16 sommerfe * Misc cleanups: "caddr_t id" should be visible in the API as a
87 1.16 sommerfe * "struct proc *".
88 1.16 sommerfe * (This requires rototilling all VFS's which support advisory locking).
89 1.16 sommerfe */
90 1.16 sommerfe
91 1.16 sommerfe /*
92 1.16 sommerfe * If there's a lot of lock contention on a single vnode, locking
93 1.16 sommerfe * schemes which allow for more paralleism would be needed. Given how
94 1.16 sommerfe * infrequently byte-range locks are actually used in typical BSD
95 1.16 sommerfe * code, a more complex approach probably isn't worth it.
96 1.16 sommerfe */
97 1.16 sommerfe
98 1.16 sommerfe /*
99 1.38 christos * We enforce a limit on locks by uid, so that a single user cannot
100 1.38 christos * run the kernel out of memory. For now, the limit is pretty coarse.
101 1.38 christos * There is no limit on root.
102 1.38 christos *
103 1.38 christos * Splitting a lock will always succeed, regardless of current allocations.
104 1.38 christos * If you're slightly above the limit, we still have to permit an allocation
105 1.38 christos * so that the unlock can succeed. If the unlocking causes too many splits,
106 1.38 christos * however, you're totally cutoff.
107 1.38 christos */
108 1.38 christos int maxlocksperuid = 1024;
109 1.38 christos
110 1.38 christos /*
111 1.38 christos * 3 options for allowfail.
112 1.38 christos * 0 - always allocate. 1 - cutoff at limit. 2 - cutoff at double limit.
113 1.38 christos */
114 1.38 christos struct lockf *
115 1.38 christos lf_alloc(uid_t uid, int allowfail)
116 1.38 christos {
117 1.38 christos struct uidinfo *uip;
118 1.38 christos struct lockf *lock;
119 1.38 christos
120 1.38 christos uip = uid_find(uid);
121 1.38 christos if (uid && allowfail && uip->ui_lockcnt >
122 1.38 christos (allowfail == 1 ? maxlocksperuid : (maxlocksperuid * 2)))
123 1.38 christos return (NULL);
124 1.38 christos uip->ui_lockcnt++;
125 1.38 christos lock = pool_get(&lockfpool, PR_WAITOK);
126 1.38 christos lock->lf_uid = uid;
127 1.38 christos return (lock);
128 1.38 christos }
129 1.38 christos
130 1.38 christos void
131 1.38 christos lf_free(struct lockf *lock)
132 1.38 christos {
133 1.38 christos struct uidinfo *uip;
134 1.38 christos
135 1.38 christos uip = uid_find(lock->lf_uid);
136 1.38 christos uip->ui_lockcnt--;
137 1.38 christos pool_put(&lockfpool, lock);
138 1.38 christos }
139 1.38 christos
140 1.38 christos /*
141 1.4 mycroft * Do an advisory lock operation.
142 1.1 ws */
143 1.4 mycroft int
144 1.25 yamt lf_advlock(struct vop_advlock_args *ap, struct lockf **head, off_t size)
145 1.1 ws {
146 1.38 christos struct proc *p = curproc;
147 1.17 jdolecek struct flock *fl = ap->a_fl;
148 1.27 yamt struct lockf *lock = NULL;
149 1.27 yamt struct lockf *sparelock;
150 1.30 yamt struct simplelock *interlock = &ap->a_vp->v_interlock;
151 1.1 ws off_t start, end;
152 1.34 christos int error = 0;
153 1.1 ws
154 1.1 ws /*
155 1.1 ws * Convert the flock structure into a start and end.
156 1.1 ws */
157 1.1 ws switch (fl->l_whence) {
158 1.1 ws case SEEK_SET:
159 1.1 ws case SEEK_CUR:
160 1.1 ws /*
161 1.1 ws * Caller is responsible for adding any necessary offset
162 1.1 ws * when SEEK_CUR is used.
163 1.1 ws */
164 1.1 ws start = fl->l_start;
165 1.1 ws break;
166 1.1 ws
167 1.1 ws case SEEK_END:
168 1.1 ws start = size + fl->l_start;
169 1.1 ws break;
170 1.1 ws
171 1.1 ws default:
172 1.29 yamt return EINVAL;
173 1.1 ws }
174 1.1 ws if (start < 0)
175 1.29 yamt return EINVAL;
176 1.10 kleink
177 1.10 kleink /*
178 1.27 yamt * allocate locks before acquire simple lock.
179 1.27 yamt * we need two locks in the worst case.
180 1.27 yamt */
181 1.27 yamt switch (ap->a_op) {
182 1.27 yamt case F_SETLK:
183 1.27 yamt case F_UNLCK:
184 1.27 yamt /*
185 1.27 yamt * XXX for F_UNLCK case, we can re-use lock.
186 1.27 yamt */
187 1.27 yamt if ((fl->l_type & F_FLOCK) == 0) {
188 1.27 yamt /*
189 1.27 yamt * byte-range lock might need one more lock.
190 1.27 yamt */
191 1.38 christos sparelock = lf_alloc(p->p_ucred->cr_uid, 0);
192 1.27 yamt if (sparelock == NULL) {
193 1.27 yamt error = ENOMEM;
194 1.27 yamt goto quit;
195 1.27 yamt }
196 1.27 yamt break;
197 1.27 yamt }
198 1.27 yamt /* FALLTHROUGH */
199 1.27 yamt
200 1.27 yamt case F_GETLK:
201 1.27 yamt sparelock = NULL;
202 1.27 yamt break;
203 1.27 yamt
204 1.27 yamt default:
205 1.29 yamt return EINVAL;
206 1.27 yamt }
207 1.27 yamt
208 1.38 christos lock = lf_alloc(p->p_ucred->cr_uid, ap->a_op != F_UNLCK ? 1 : 2);
209 1.27 yamt if (lock == NULL) {
210 1.27 yamt error = ENOMEM;
211 1.27 yamt goto quit;
212 1.27 yamt }
213 1.27 yamt
214 1.30 yamt simple_lock(interlock);
215 1.27 yamt
216 1.27 yamt /*
217 1.10 kleink * Avoid the common case of unlocking when inode has no locks.
218 1.10 kleink */
219 1.10 kleink if (*head == (struct lockf *)0) {
220 1.17 jdolecek if (ap->a_op != F_SETLK) {
221 1.10 kleink fl->l_type = F_UNLCK;
222 1.27 yamt error = 0;
223 1.27 yamt goto quit_unlock;
224 1.10 kleink }
225 1.10 kleink }
226 1.10 kleink
227 1.1 ws if (fl->l_len == 0)
228 1.1 ws end = -1;
229 1.1 ws else
230 1.1 ws end = start + fl->l_len - 1;
231 1.1 ws /*
232 1.4 mycroft * Create the lockf structure.
233 1.1 ws */
234 1.1 ws lock->lf_start = start;
235 1.1 ws lock->lf_end = end;
236 1.37 perry /* XXX NJWLWP
237 1.21 thorpej * I don't want to make the entire VFS universe use LWPs, because
238 1.21 thorpej * they don't need them, for the most part. This is an exception,
239 1.21 thorpej * and a kluge.
240 1.21 thorpej */
241 1.21 thorpej
242 1.1 ws lock->lf_head = head;
243 1.1 ws lock->lf_type = fl->l_type;
244 1.1 ws lock->lf_next = (struct lockf *)0;
245 1.12 fvdl TAILQ_INIT(&lock->lf_blkhd);
246 1.17 jdolecek lock->lf_flags = ap->a_flags;
247 1.21 thorpej if (lock->lf_flags & F_POSIX) {
248 1.21 thorpej KASSERT(curproc == (struct proc *)ap->a_id);
249 1.21 thorpej }
250 1.23 mycroft lock->lf_id = (struct proc *)ap->a_id;
251 1.23 mycroft lock->lf_lwp = curlwp;
252 1.37 perry
253 1.1 ws /*
254 1.1 ws * Do the requested operation.
255 1.1 ws */
256 1.17 jdolecek switch (ap->a_op) {
257 1.4 mycroft
258 1.1 ws case F_SETLK:
259 1.30 yamt error = lf_setlock(lock, &sparelock, interlock);
260 1.27 yamt lock = NULL; /* lf_setlock freed it */
261 1.27 yamt break;
262 1.1 ws
263 1.1 ws case F_UNLCK:
264 1.27 yamt error = lf_clearlock(lock, &sparelock);
265 1.27 yamt break;
266 1.1 ws
267 1.1 ws case F_GETLK:
268 1.1 ws error = lf_getlock(lock, fl);
269 1.27 yamt break;
270 1.4 mycroft
271 1.1 ws default:
272 1.31 fvdl break;
273 1.27 yamt /* NOTREACHED */
274 1.27 yamt }
275 1.27 yamt
276 1.27 yamt quit_unlock:
277 1.30 yamt simple_unlock(interlock);
278 1.27 yamt quit:
279 1.27 yamt if (lock)
280 1.38 christos lf_free(lock);
281 1.27 yamt if (sparelock)
282 1.38 christos lf_free(sparelock);
283 1.27 yamt
284 1.29 yamt return error;
285 1.1 ws }
286 1.1 ws
287 1.1 ws /*
288 1.1 ws * Set a byte-range lock.
289 1.1 ws */
290 1.24 yamt static int
291 1.27 yamt lf_setlock(struct lockf *lock, struct lockf **sparelock,
292 1.27 yamt struct simplelock *interlock)
293 1.1 ws {
294 1.15 augustss struct lockf *block;
295 1.1 ws struct lockf **head = lock->lf_head;
296 1.1 ws struct lockf **prev, *overlap, *ltmp;
297 1.1 ws static char lockstr[] = "lockf";
298 1.1 ws int ovcase, priority, needtolink, error;
299 1.1 ws
300 1.1 ws #ifdef LOCKF_DEBUG
301 1.1 ws if (lockf_debug & 1)
302 1.1 ws lf_print("lf_setlock", lock);
303 1.1 ws #endif /* LOCKF_DEBUG */
304 1.1 ws
305 1.1 ws /*
306 1.1 ws * Set the priority
307 1.1 ws */
308 1.1 ws priority = PLOCK;
309 1.1 ws if (lock->lf_type == F_WRLCK)
310 1.1 ws priority += 4;
311 1.1 ws priority |= PCATCH;
312 1.1 ws /*
313 1.1 ws * Scan lock list for this file looking for locks that would block us.
314 1.1 ws */
315 1.7 christos while ((block = lf_getblock(lock)) != NULL) {
316 1.1 ws /*
317 1.1 ws * Free the structure and return if nonblocking.
318 1.1 ws */
319 1.1 ws if ((lock->lf_flags & F_WAIT) == 0) {
320 1.38 christos lf_free(lock);
321 1.29 yamt return EAGAIN;
322 1.1 ws }
323 1.1 ws /*
324 1.1 ws * We are blocked. Since flock style locks cover
325 1.1 ws * the whole file, there is no chance for deadlock.
326 1.1 ws * For byte-range locks we must check for deadlock.
327 1.1 ws *
328 1.1 ws * Deadlock detection is done by looking through the
329 1.1 ws * wait channels to see if there are any cycles that
330 1.1 ws * involve us. MAXDEPTH is set just to make sure we
331 1.16 sommerfe * do not go off into neverneverland.
332 1.1 ws */
333 1.1 ws if ((lock->lf_flags & F_POSIX) &&
334 1.1 ws (block->lf_flags & F_POSIX)) {
335 1.21 thorpej struct lwp *wlwp;
336 1.15 augustss struct lockf *waitblock;
337 1.1 ws int i = 0;
338 1.1 ws
339 1.23 mycroft /*
340 1.23 mycroft * The block is waiting on something. if_lwp will be
341 1.23 mycroft * 0 once the lock is granted, so we terminate the
342 1.23 mycroft * loop if we find this.
343 1.23 mycroft */
344 1.23 mycroft wlwp = block->lf_lwp;
345 1.23 mycroft while (wlwp && (i++ < maxlockdepth)) {
346 1.21 thorpej waitblock = (struct lockf *)wlwp->l_wchan;
347 1.1 ws /* Get the owner of the blocking lock */
348 1.1 ws waitblock = waitblock->lf_next;
349 1.1 ws if ((waitblock->lf_flags & F_POSIX) == 0)
350 1.1 ws break;
351 1.23 mycroft wlwp = waitblock->lf_lwp;
352 1.23 mycroft if (wlwp == lock->lf_lwp) {
353 1.38 christos lf_free(lock);
354 1.29 yamt return EDEADLK;
355 1.1 ws }
356 1.1 ws }
357 1.16 sommerfe /*
358 1.36 peter * If we're still following a dependency chain
359 1.16 sommerfe * after maxlockdepth iterations, assume we're in
360 1.16 sommerfe * a cycle to be safe.
361 1.16 sommerfe */
362 1.16 sommerfe if (i >= maxlockdepth) {
363 1.38 christos lf_free(lock);
364 1.29 yamt return EDEADLK;
365 1.16 sommerfe }
366 1.1 ws }
367 1.1 ws /*
368 1.1 ws * For flock type locks, we must first remove
369 1.1 ws * any shared locks that we hold before we sleep
370 1.1 ws * waiting for an exclusive lock.
371 1.1 ws */
372 1.1 ws if ((lock->lf_flags & F_FLOCK) &&
373 1.1 ws lock->lf_type == F_WRLCK) {
374 1.1 ws lock->lf_type = F_UNLCK;
375 1.27 yamt (void) lf_clearlock(lock, NULL);
376 1.1 ws lock->lf_type = F_WRLCK;
377 1.1 ws }
378 1.1 ws /*
379 1.1 ws * Add our lock to the blocked list and sleep until we're free.
380 1.1 ws * Remember who blocked us (for deadlock detection).
381 1.1 ws */
382 1.1 ws lock->lf_next = block;
383 1.12 fvdl TAILQ_INSERT_TAIL(&block->lf_blkhd, lock, lf_block);
384 1.1 ws #ifdef LOCKF_DEBUG
385 1.1 ws if (lockf_debug & 1) {
386 1.1 ws lf_print("lf_setlock: blocking on", block);
387 1.1 ws lf_printlist("lf_setlock", block);
388 1.1 ws }
389 1.1 ws #endif /* LOCKF_DEBUG */
390 1.27 yamt error = ltsleep(lock, priority, lockstr, 0, interlock);
391 1.16 sommerfe
392 1.16 sommerfe /*
393 1.16 sommerfe * We may have been awakened by a signal (in
394 1.16 sommerfe * which case we must remove ourselves from the
395 1.16 sommerfe * blocked list) and/or by another process
396 1.16 sommerfe * releasing a lock (in which case we have already
397 1.16 sommerfe * been removed from the blocked list and our
398 1.16 sommerfe * lf_next field set to NOLOCKF).
399 1.16 sommerfe */
400 1.16 sommerfe if (lock->lf_next != NOLOCKF) {
401 1.16 sommerfe TAILQ_REMOVE(&lock->lf_next->lf_blkhd, lock, lf_block);
402 1.16 sommerfe lock->lf_next = NOLOCKF;
403 1.16 sommerfe }
404 1.7 christos if (error) {
405 1.38 christos lf_free(lock);
406 1.29 yamt return error;
407 1.1 ws }
408 1.1 ws }
409 1.1 ws /*
410 1.1 ws * No blocks!! Add the lock. Note that we will
411 1.1 ws * downgrade or upgrade any overlapping locks this
412 1.1 ws * process already owns.
413 1.1 ws *
414 1.1 ws * Skip over locks owned by other processes.
415 1.1 ws * Handle any locks that overlap and are owned by ourselves.
416 1.1 ws */
417 1.23 mycroft lock->lf_lwp = 0;
418 1.1 ws prev = head;
419 1.1 ws block = *head;
420 1.1 ws needtolink = 1;
421 1.1 ws for (;;) {
422 1.7 christos ovcase = lf_findoverlap(block, lock, SELF, &prev, &overlap);
423 1.7 christos if (ovcase)
424 1.1 ws block = overlap->lf_next;
425 1.1 ws /*
426 1.1 ws * Six cases:
427 1.1 ws * 0) no overlap
428 1.1 ws * 1) overlap == lock
429 1.1 ws * 2) overlap contains lock
430 1.1 ws * 3) lock contains overlap
431 1.1 ws * 4) overlap starts before lock
432 1.1 ws * 5) overlap ends after lock
433 1.1 ws */
434 1.1 ws switch (ovcase) {
435 1.1 ws case 0: /* no overlap */
436 1.1 ws if (needtolink) {
437 1.1 ws *prev = lock;
438 1.1 ws lock->lf_next = overlap;
439 1.1 ws }
440 1.1 ws break;
441 1.1 ws
442 1.1 ws case 1: /* overlap == lock */
443 1.1 ws /*
444 1.1 ws * If downgrading lock, others may be
445 1.1 ws * able to acquire it.
446 1.1 ws */
447 1.1 ws if (lock->lf_type == F_RDLCK &&
448 1.1 ws overlap->lf_type == F_WRLCK)
449 1.1 ws lf_wakelock(overlap);
450 1.1 ws overlap->lf_type = lock->lf_type;
451 1.38 christos lf_free(lock);
452 1.1 ws lock = overlap; /* for debug output below */
453 1.1 ws break;
454 1.1 ws
455 1.1 ws case 2: /* overlap contains lock */
456 1.1 ws /*
457 1.1 ws * Check for common starting point and different types.
458 1.1 ws */
459 1.1 ws if (overlap->lf_type == lock->lf_type) {
460 1.38 christos lf_free(lock);
461 1.1 ws lock = overlap; /* for debug output below */
462 1.1 ws break;
463 1.1 ws }
464 1.1 ws if (overlap->lf_start == lock->lf_start) {
465 1.1 ws *prev = lock;
466 1.1 ws lock->lf_next = overlap;
467 1.1 ws overlap->lf_start = lock->lf_end + 1;
468 1.1 ws } else
469 1.27 yamt lf_split(overlap, lock, sparelock);
470 1.1 ws lf_wakelock(overlap);
471 1.1 ws break;
472 1.1 ws
473 1.1 ws case 3: /* lock contains overlap */
474 1.1 ws /*
475 1.1 ws * If downgrading lock, others may be able to
476 1.1 ws * acquire it, otherwise take the list.
477 1.1 ws */
478 1.1 ws if (lock->lf_type == F_RDLCK &&
479 1.1 ws overlap->lf_type == F_WRLCK) {
480 1.1 ws lf_wakelock(overlap);
481 1.1 ws } else {
482 1.19 matt while ((ltmp = TAILQ_FIRST(&overlap->lf_blkhd))) {
483 1.16 sommerfe KASSERT(ltmp->lf_next == overlap);
484 1.12 fvdl TAILQ_REMOVE(&overlap->lf_blkhd, ltmp,
485 1.12 fvdl lf_block);
486 1.16 sommerfe ltmp->lf_next = lock;
487 1.12 fvdl TAILQ_INSERT_TAIL(&lock->lf_blkhd,
488 1.12 fvdl ltmp, lf_block);
489 1.12 fvdl }
490 1.1 ws }
491 1.1 ws /*
492 1.1 ws * Add the new lock if necessary and delete the overlap.
493 1.1 ws */
494 1.1 ws if (needtolink) {
495 1.1 ws *prev = lock;
496 1.1 ws lock->lf_next = overlap->lf_next;
497 1.1 ws prev = &lock->lf_next;
498 1.1 ws needtolink = 0;
499 1.1 ws } else
500 1.1 ws *prev = overlap->lf_next;
501 1.38 christos lf_free(lock);
502 1.1 ws continue;
503 1.1 ws
504 1.1 ws case 4: /* overlap starts before lock */
505 1.1 ws /*
506 1.1 ws * Add lock after overlap on the list.
507 1.1 ws */
508 1.1 ws lock->lf_next = overlap->lf_next;
509 1.1 ws overlap->lf_next = lock;
510 1.1 ws overlap->lf_end = lock->lf_start - 1;
511 1.1 ws prev = &lock->lf_next;
512 1.1 ws lf_wakelock(overlap);
513 1.1 ws needtolink = 0;
514 1.1 ws continue;
515 1.1 ws
516 1.1 ws case 5: /* overlap ends after lock */
517 1.1 ws /*
518 1.1 ws * Add the new lock before overlap.
519 1.1 ws */
520 1.1 ws if (needtolink) {
521 1.1 ws *prev = lock;
522 1.1 ws lock->lf_next = overlap;
523 1.1 ws }
524 1.1 ws overlap->lf_start = lock->lf_end + 1;
525 1.1 ws lf_wakelock(overlap);
526 1.1 ws break;
527 1.1 ws }
528 1.1 ws break;
529 1.1 ws }
530 1.1 ws #ifdef LOCKF_DEBUG
531 1.1 ws if (lockf_debug & 1) {
532 1.1 ws lf_print("lf_setlock: got the lock", lock);
533 1.1 ws lf_printlist("lf_setlock", lock);
534 1.1 ws }
535 1.1 ws #endif /* LOCKF_DEBUG */
536 1.29 yamt return 0;
537 1.1 ws }
538 1.1 ws
539 1.1 ws /*
540 1.1 ws * Remove a byte-range lock on an inode.
541 1.1 ws *
542 1.1 ws * Generally, find the lock (or an overlap to that lock)
543 1.1 ws * and remove it (or shrink it), then wakeup anyone we can.
544 1.1 ws */
545 1.24 yamt static int
546 1.27 yamt lf_clearlock(struct lockf *unlock, struct lockf **sparelock)
547 1.1 ws {
548 1.1 ws struct lockf **head = unlock->lf_head;
549 1.15 augustss struct lockf *lf = *head;
550 1.1 ws struct lockf *overlap, **prev;
551 1.1 ws int ovcase;
552 1.1 ws
553 1.1 ws if (lf == NOLOCKF)
554 1.29 yamt return 0;
555 1.1 ws #ifdef LOCKF_DEBUG
556 1.1 ws if (unlock->lf_type != F_UNLCK)
557 1.1 ws panic("lf_clearlock: bad type");
558 1.1 ws if (lockf_debug & 1)
559 1.1 ws lf_print("lf_clearlock", unlock);
560 1.1 ws #endif /* LOCKF_DEBUG */
561 1.1 ws prev = head;
562 1.7 christos while ((ovcase = lf_findoverlap(lf, unlock, SELF,
563 1.7 christos &prev, &overlap)) != 0) {
564 1.1 ws /*
565 1.1 ws * Wakeup the list of locks to be retried.
566 1.1 ws */
567 1.1 ws lf_wakelock(overlap);
568 1.1 ws
569 1.1 ws switch (ovcase) {
570 1.1 ws
571 1.1 ws case 1: /* overlap == lock */
572 1.1 ws *prev = overlap->lf_next;
573 1.38 christos lf_free(overlap);
574 1.1 ws break;
575 1.1 ws
576 1.1 ws case 2: /* overlap contains lock: split it */
577 1.1 ws if (overlap->lf_start == unlock->lf_start) {
578 1.1 ws overlap->lf_start = unlock->lf_end + 1;
579 1.1 ws break;
580 1.1 ws }
581 1.27 yamt lf_split(overlap, unlock, sparelock);
582 1.1 ws overlap->lf_next = unlock->lf_next;
583 1.1 ws break;
584 1.1 ws
585 1.1 ws case 3: /* lock contains overlap */
586 1.1 ws *prev = overlap->lf_next;
587 1.1 ws lf = overlap->lf_next;
588 1.38 christos lf_free(overlap);
589 1.1 ws continue;
590 1.1 ws
591 1.1 ws case 4: /* overlap starts before lock */
592 1.1 ws overlap->lf_end = unlock->lf_start - 1;
593 1.1 ws prev = &overlap->lf_next;
594 1.1 ws lf = overlap->lf_next;
595 1.1 ws continue;
596 1.1 ws
597 1.1 ws case 5: /* overlap ends after lock */
598 1.1 ws overlap->lf_start = unlock->lf_end + 1;
599 1.1 ws break;
600 1.1 ws }
601 1.1 ws break;
602 1.1 ws }
603 1.1 ws #ifdef LOCKF_DEBUG
604 1.1 ws if (lockf_debug & 1)
605 1.1 ws lf_printlist("lf_clearlock", unlock);
606 1.1 ws #endif /* LOCKF_DEBUG */
607 1.29 yamt return 0;
608 1.1 ws }
609 1.1 ws
610 1.1 ws /*
611 1.1 ws * Check whether there is a blocking lock,
612 1.1 ws * and if so return its process identifier.
613 1.1 ws */
614 1.24 yamt static int
615 1.25 yamt lf_getlock(struct lockf *lock, struct flock *fl)
616 1.1 ws {
617 1.15 augustss struct lockf *block;
618 1.1 ws
619 1.1 ws #ifdef LOCKF_DEBUG
620 1.1 ws if (lockf_debug & 1)
621 1.1 ws lf_print("lf_getlock", lock);
622 1.1 ws #endif /* LOCKF_DEBUG */
623 1.1 ws
624 1.7 christos if ((block = lf_getblock(lock)) != NULL) {
625 1.1 ws fl->l_type = block->lf_type;
626 1.1 ws fl->l_whence = SEEK_SET;
627 1.1 ws fl->l_start = block->lf_start;
628 1.1 ws if (block->lf_end == -1)
629 1.1 ws fl->l_len = 0;
630 1.1 ws else
631 1.1 ws fl->l_len = block->lf_end - block->lf_start + 1;
632 1.1 ws if (block->lf_flags & F_POSIX)
633 1.23 mycroft fl->l_pid = ((struct proc *)block->lf_id)->p_pid;
634 1.1 ws else
635 1.1 ws fl->l_pid = -1;
636 1.1 ws } else {
637 1.1 ws fl->l_type = F_UNLCK;
638 1.1 ws }
639 1.29 yamt return 0;
640 1.1 ws }
641 1.1 ws
642 1.1 ws /*
643 1.1 ws * Walk the list of locks for an inode and
644 1.1 ws * return the first blocking lock.
645 1.1 ws */
646 1.24 yamt static struct lockf *
647 1.25 yamt lf_getblock(struct lockf *lock)
648 1.1 ws {
649 1.1 ws struct lockf **prev, *overlap, *lf = *(lock->lf_head);
650 1.1 ws
651 1.1 ws prev = lock->lf_head;
652 1.20 simonb while (lf_findoverlap(lf, lock, OTHERS, &prev, &overlap) != 0) {
653 1.1 ws /*
654 1.1 ws * We've found an overlap, see if it blocks us
655 1.1 ws */
656 1.1 ws if ((lock->lf_type == F_WRLCK || overlap->lf_type == F_WRLCK))
657 1.29 yamt return overlap;
658 1.1 ws /*
659 1.1 ws * Nope, point to the next one on the list and
660 1.1 ws * see if it blocks us
661 1.1 ws */
662 1.1 ws lf = overlap->lf_next;
663 1.1 ws }
664 1.29 yamt return NOLOCKF;
665 1.1 ws }
666 1.1 ws
667 1.1 ws /*
668 1.1 ws * Walk the list of locks for an inode to
669 1.1 ws * find an overlapping lock (if any).
670 1.1 ws *
671 1.1 ws * NOTE: this returns only the FIRST overlapping lock. There
672 1.1 ws * may be more than one.
673 1.1 ws */
674 1.24 yamt static int
675 1.25 yamt lf_findoverlap(struct lockf *lf, struct lockf *lock, int type,
676 1.25 yamt struct lockf ***prev, struct lockf **overlap)
677 1.1 ws {
678 1.1 ws off_t start, end;
679 1.1 ws
680 1.1 ws *overlap = lf;
681 1.1 ws if (lf == NOLOCKF)
682 1.29 yamt return 0;
683 1.1 ws #ifdef LOCKF_DEBUG
684 1.1 ws if (lockf_debug & 2)
685 1.1 ws lf_print("lf_findoverlap: looking for overlap in", lock);
686 1.1 ws #endif /* LOCKF_DEBUG */
687 1.1 ws start = lock->lf_start;
688 1.1 ws end = lock->lf_end;
689 1.1 ws while (lf != NOLOCKF) {
690 1.23 mycroft if (((type == SELF) && lf->lf_id != lock->lf_id) ||
691 1.23 mycroft ((type == OTHERS) && lf->lf_id == lock->lf_id)) {
692 1.1 ws *prev = &lf->lf_next;
693 1.1 ws *overlap = lf = lf->lf_next;
694 1.1 ws continue;
695 1.1 ws }
696 1.1 ws #ifdef LOCKF_DEBUG
697 1.1 ws if (lockf_debug & 2)
698 1.1 ws lf_print("\tchecking", lf);
699 1.1 ws #endif /* LOCKF_DEBUG */
700 1.1 ws /*
701 1.1 ws * OK, check for overlap
702 1.1 ws *
703 1.1 ws * Six cases:
704 1.1 ws * 0) no overlap
705 1.1 ws * 1) overlap == lock
706 1.1 ws * 2) overlap contains lock
707 1.1 ws * 3) lock contains overlap
708 1.1 ws * 4) overlap starts before lock
709 1.1 ws * 5) overlap ends after lock
710 1.1 ws */
711 1.1 ws if ((lf->lf_end != -1 && start > lf->lf_end) ||
712 1.1 ws (end != -1 && lf->lf_start > end)) {
713 1.1 ws /* Case 0 */
714 1.1 ws #ifdef LOCKF_DEBUG
715 1.1 ws if (lockf_debug & 2)
716 1.9 christos printf("no overlap\n");
717 1.1 ws #endif /* LOCKF_DEBUG */
718 1.1 ws if ((type & SELF) && end != -1 && lf->lf_start > end)
719 1.29 yamt return 0;
720 1.1 ws *prev = &lf->lf_next;
721 1.1 ws *overlap = lf = lf->lf_next;
722 1.1 ws continue;
723 1.1 ws }
724 1.1 ws if ((lf->lf_start == start) && (lf->lf_end == end)) {
725 1.1 ws /* Case 1 */
726 1.1 ws #ifdef LOCKF_DEBUG
727 1.1 ws if (lockf_debug & 2)
728 1.9 christos printf("overlap == lock\n");
729 1.1 ws #endif /* LOCKF_DEBUG */
730 1.29 yamt return 1;
731 1.1 ws }
732 1.1 ws if ((lf->lf_start <= start) &&
733 1.1 ws (end != -1) &&
734 1.1 ws ((lf->lf_end >= end) || (lf->lf_end == -1))) {
735 1.1 ws /* Case 2 */
736 1.1 ws #ifdef LOCKF_DEBUG
737 1.1 ws if (lockf_debug & 2)
738 1.9 christos printf("overlap contains lock\n");
739 1.1 ws #endif /* LOCKF_DEBUG */
740 1.29 yamt return 2;
741 1.1 ws }
742 1.1 ws if (start <= lf->lf_start &&
743 1.4 mycroft (end == -1 ||
744 1.1 ws (lf->lf_end != -1 && end >= lf->lf_end))) {
745 1.1 ws /* Case 3 */
746 1.1 ws #ifdef LOCKF_DEBUG
747 1.1 ws if (lockf_debug & 2)
748 1.9 christos printf("lock contains overlap\n");
749 1.1 ws #endif /* LOCKF_DEBUG */
750 1.29 yamt return 3;
751 1.1 ws }
752 1.1 ws if ((lf->lf_start < start) &&
753 1.1 ws ((lf->lf_end >= start) || (lf->lf_end == -1))) {
754 1.1 ws /* Case 4 */
755 1.1 ws #ifdef LOCKF_DEBUG
756 1.1 ws if (lockf_debug & 2)
757 1.9 christos printf("overlap starts before lock\n");
758 1.1 ws #endif /* LOCKF_DEBUG */
759 1.29 yamt return 4;
760 1.1 ws }
761 1.1 ws if ((lf->lf_start > start) &&
762 1.1 ws (end != -1) &&
763 1.1 ws ((lf->lf_end > end) || (lf->lf_end == -1))) {
764 1.1 ws /* Case 5 */
765 1.1 ws #ifdef LOCKF_DEBUG
766 1.1 ws if (lockf_debug & 2)
767 1.9 christos printf("overlap ends after lock\n");
768 1.1 ws #endif /* LOCKF_DEBUG */
769 1.29 yamt return 5;
770 1.1 ws }
771 1.1 ws panic("lf_findoverlap: default");
772 1.1 ws }
773 1.29 yamt return 0;
774 1.1 ws }
775 1.1 ws
776 1.1 ws /*
777 1.1 ws * Split a lock and a contained region into
778 1.1 ws * two or three locks as necessary.
779 1.1 ws */
780 1.24 yamt static void
781 1.27 yamt lf_split(struct lockf *lock1, struct lockf *lock2, struct lockf **sparelock)
782 1.1 ws {
783 1.15 augustss struct lockf *splitlock;
784 1.1 ws
785 1.1 ws #ifdef LOCKF_DEBUG
786 1.1 ws if (lockf_debug & 2) {
787 1.1 ws lf_print("lf_split", lock1);
788 1.1 ws lf_print("splitting from", lock2);
789 1.1 ws }
790 1.1 ws #endif /* LOCKF_DEBUG */
791 1.1 ws /*
792 1.1 ws * Check to see if spliting into only two pieces.
793 1.1 ws */
794 1.1 ws if (lock1->lf_start == lock2->lf_start) {
795 1.1 ws lock1->lf_start = lock2->lf_end + 1;
796 1.1 ws lock2->lf_next = lock1;
797 1.1 ws return;
798 1.1 ws }
799 1.1 ws if (lock1->lf_end == lock2->lf_end) {
800 1.1 ws lock1->lf_end = lock2->lf_start - 1;
801 1.1 ws lock2->lf_next = lock1->lf_next;
802 1.1 ws lock1->lf_next = lock2;
803 1.1 ws return;
804 1.1 ws }
805 1.1 ws /*
806 1.1 ws * Make a new lock consisting of the last part of
807 1.1 ws * the encompassing lock
808 1.1 ws */
809 1.27 yamt splitlock = *sparelock;
810 1.27 yamt *sparelock = NULL;
811 1.29 yamt memcpy(splitlock, lock1, sizeof(*splitlock));
812 1.1 ws splitlock->lf_start = lock2->lf_end + 1;
813 1.12 fvdl TAILQ_INIT(&splitlock->lf_blkhd);
814 1.1 ws lock1->lf_end = lock2->lf_start - 1;
815 1.1 ws /*
816 1.1 ws * OK, now link it in
817 1.1 ws */
818 1.1 ws splitlock->lf_next = lock1->lf_next;
819 1.1 ws lock2->lf_next = splitlock;
820 1.1 ws lock1->lf_next = lock2;
821 1.1 ws }
822 1.1 ws
823 1.1 ws /*
824 1.1 ws * Wakeup a blocklist
825 1.1 ws */
826 1.24 yamt static void
827 1.25 yamt lf_wakelock(struct lockf *listhead)
828 1.1 ws {
829 1.15 augustss struct lockf *wakelock;
830 1.1 ws
831 1.19 matt while ((wakelock = TAILQ_FIRST(&listhead->lf_blkhd))) {
832 1.16 sommerfe KASSERT(wakelock->lf_next == listhead);
833 1.12 fvdl TAILQ_REMOVE(&listhead->lf_blkhd, wakelock, lf_block);
834 1.1 ws wakelock->lf_next = NOLOCKF;
835 1.1 ws #ifdef LOCKF_DEBUG
836 1.1 ws if (lockf_debug & 2)
837 1.1 ws lf_print("lf_wakelock: awakening", wakelock);
838 1.12 fvdl #endif
839 1.29 yamt wakeup(wakelock);
840 1.1 ws }
841 1.1 ws }
842 1.1 ws
843 1.1 ws #ifdef LOCKF_DEBUG
844 1.1 ws /*
845 1.1 ws * Print out a lock.
846 1.1 ws */
847 1.24 yamt static void
848 1.25 yamt lf_print(char *tag, struct lockf *lock)
849 1.1 ws {
850 1.37 perry
851 1.9 christos printf("%s: lock %p for ", tag, lock);
852 1.1 ws if (lock->lf_flags & F_POSIX)
853 1.23 mycroft printf("proc %d", ((struct proc *)lock->lf_id)->p_pid);
854 1.1 ws else
855 1.23 mycroft printf("file 0x%p", (struct file *)lock->lf_id);
856 1.11 jtk printf(" %s, start %qx, end %qx",
857 1.1 ws lock->lf_type == F_RDLCK ? "shared" :
858 1.1 ws lock->lf_type == F_WRLCK ? "exclusive" :
859 1.1 ws lock->lf_type == F_UNLCK ? "unlock" :
860 1.1 ws "unknown", lock->lf_start, lock->lf_end);
861 1.19 matt if (TAILQ_FIRST(&lock->lf_blkhd))
862 1.19 matt printf(" block %p\n", TAILQ_FIRST(&lock->lf_blkhd));
863 1.1 ws else
864 1.9 christos printf("\n");
865 1.1 ws }
866 1.1 ws
867 1.24 yamt static void
868 1.25 yamt lf_printlist(char *tag, struct lockf *lock)
869 1.1 ws {
870 1.15 augustss struct lockf *lf, *blk;
871 1.1 ws
872 1.11 jtk printf("%s: Lock list:\n", tag);
873 1.12 fvdl for (lf = *lock->lf_head; lf; lf = lf->lf_next) {
874 1.9 christos printf("\tlock %p for ", lf);
875 1.1 ws if (lf->lf_flags & F_POSIX)
876 1.23 mycroft printf("proc %d", ((struct proc *)lf->lf_id)->p_pid);
877 1.1 ws else
878 1.23 mycroft printf("file 0x%p", (struct file *)lf->lf_id);
879 1.11 jtk printf(", %s, start %qx, end %qx",
880 1.1 ws lf->lf_type == F_RDLCK ? "shared" :
881 1.1 ws lf->lf_type == F_WRLCK ? "exclusive" :
882 1.1 ws lf->lf_type == F_UNLCK ? "unlock" :
883 1.1 ws "unknown", lf->lf_start, lf->lf_end);
884 1.19 matt TAILQ_FOREACH(blk, &lf->lf_blkhd, lf_block) {
885 1.12 fvdl if (blk->lf_flags & F_POSIX)
886 1.12 fvdl printf("proc %d",
887 1.23 mycroft ((struct proc *)blk->lf_id)->p_pid);
888 1.12 fvdl else
889 1.23 mycroft printf("file 0x%p", (struct file *)blk->lf_id);
890 1.12 fvdl printf(", %s, start %qx, end %qx",
891 1.12 fvdl blk->lf_type == F_RDLCK ? "shared" :
892 1.12 fvdl blk->lf_type == F_WRLCK ? "exclusive" :
893 1.12 fvdl blk->lf_type == F_UNLCK ? "unlock" :
894 1.12 fvdl "unknown", blk->lf_start, blk->lf_end);
895 1.19 matt if (TAILQ_FIRST(&blk->lf_blkhd))
896 1.12 fvdl panic("lf_printlist: bad list");
897 1.12 fvdl }
898 1.12 fvdl printf("\n");
899 1.1 ws }
900 1.1 ws }
901 1.1 ws #endif /* LOCKF_DEBUG */
902