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