![[first]](../icons/first.png){kind=icon}
![[previous]](../icons/n_left.png){kind=icon}
![[next]](../icons/n_right.png){kind=icon}
![[last]](../icons/last.png){kind=icon}
![[top]](../icons/n_top.png){kind=icon}
![[bottom]](../icons/bottom.png){kind=icon}
![[index]](../icons/index.png){kind=icon}
![[help]](../icons/help.png){kind=icon}
*/
1 /*
2 * linux/fs/locks.c
3 *
4 * Provide support for fcntl()'s F_GETLK, F_SETLK, and F_SETLKW calls.
5 * Doug Evans, 92Aug07, dje@sspiff.uucp.
6 *
7 * FIXME: two things aren't handled yet:
8 * - deadlock detection/avoidance (of dubious merit, but since it's in
9 * the definition, I guess it should be provided eventually)
10 * - mandatory locks (requires lots of changes elsewhere)
11 */
12
13 #include <asm/segment.h>
14
15 #include <linux/sched.h>
16 #include <linux/kernel.h>
17 #include <linux/errno.h>
18 #include <linux/stat.h>
19 #include <linux/fcntl.h>
20
21 #define OFFSET_MAX 0x7fffffff /* FIXME: move elsewhere? */
22
23 static int copy_flock(struct file *filp, struct file_lock *fl, struct flock *l);
24 static int conflict(struct file_lock *caller_fl, struct file_lock *sys_fl);
25 static int overlap(struct file_lock *fl1, struct file_lock *fl2);
26 static int lock_it(struct file *filp, struct file_lock *caller);
27 static int unlock_it(struct file *filp, struct file_lock *caller);
28 static struct file_lock *alloc_lock(struct file *filp, struct file_lock *template);
29 static void free_lock(struct file *filp, struct file_lock *fl);
30
31 static struct file_lock file_lock_table[NR_FILE_LOCKS];
32 static struct file_lock *file_lock_free_list;
33
34 /*
35 * Called at boot time to initialize the lock table ...
36 */
37
38 void fcntl_init_locks(void)
/* ![[next]](../icons/right.png)
![[first]](../icons/n_first.png)
![[top]](../icons/top.png)
*/
39 {
40 struct file_lock *fl;
41
42 for (fl = &file_lock_table[0]; fl < file_lock_table + NR_FILE_LOCKS - 1; fl++) {
43 fl->fl_next = fl + 1;
44 fl->fl_owner = NULL;
45 }
46 file_lock_table[NR_FILE_LOCKS - 1].fl_next = NULL;
47 file_lock_table[NR_FILE_LOCKS - 1].fl_owner = NULL;
48 file_lock_free_list = &file_lock_table[0];
49 }
50
51 int fcntl_getlk(unsigned int fd, struct flock *l)
/* ![[previous]](../icons/left.png)
*/
52 {
53 struct flock flock;
54 struct file *filp;
55 struct file_lock *fl,file_lock;
56
57 if (fd >= NR_OPEN || !(filp = current->filp[fd]))
58 return -EBADF;
59 verify_area(l, sizeof(*l));
60 memcpy_fromfs(&flock, l, sizeof(flock));
61 if (flock.l_type == F_UNLCK)
62 return -EINVAL;
63 if (!copy_flock(filp, &file_lock, &flock))
64 return -EINVAL;
65
66 for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
67 if (conflict(&file_lock, fl)) {
68 flock.l_pid = fl->fl_owner->pid;
69 flock.l_start = fl->fl_start;
70 flock.l_len = fl->fl_end == OFFSET_MAX ? 0 :
71 fl->fl_end - fl->fl_start + 1;
72 flock.l_whence = fl->fl_whence;
73 flock.l_type = fl->fl_type;
74 memcpy_tofs(l, &flock, sizeof(flock));
75 return 0;
76 }
77 }
78
79 flock.l_type = F_UNLCK; /* no conflict found */
80 memcpy_tofs(l, &flock, sizeof(flock));
81 return 0;
82 }
83
84 /*
85 * This function implements both F_SETLK and F_SETLKW.
86 */
87
88 int fcntl_setlk(unsigned int fd, unsigned int cmd, struct flock *l)
/* */
89 {
90 struct file *filp;
91 struct file_lock *fl,file_lock;
92 struct flock flock;
93
94 /*
95 * Get arguments and validate them ...
96 */
97
98 if (fd >= NR_OPEN || !(filp = current->filp[fd]))
99 return -EBADF;
100 verify_area(l, sizeof(*l));
101 memcpy_fromfs(&flock, l, sizeof(flock));
102 if (!copy_flock(filp, &file_lock, &flock))
103 return -EINVAL;
104 switch (file_lock.fl_type) {
105 case F_RDLCK :
106 if (!(filp->f_mode & 1))
107 return -EBADF;
108 break;
109 case F_WRLCK :
110 if (!(filp->f_mode & 2))
111 return -EBADF;
112 break;
113 case F_UNLCK :
114 break;
115 }
116
117 /*
118 * F_UNLCK needs to be handled differently ...
119 */
120
121 if (file_lock.fl_type == F_UNLCK)
122 return unlock_it(filp, &file_lock);
123
124 /*
125 * Scan for a conflicting lock ...
126 */
127
128 repeat:
129 for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
130 if (!conflict(&file_lock, fl))
131 continue;
132 /*
133 * File is locked by another process. If this is F_SETLKW
134 * wait for the lock to be released.
135 * FIXME: We need to check for deadlocks here.
136 */
137 if (cmd == F_SETLKW) {
138 interruptible_sleep_on(&fl->fl_wait);
139 goto repeat;
140 }
141 return -EAGAIN;
142 }
143
144 /*
145 * Lock doesn't conflict with any other lock ...
146 */
147
148 return lock_it(filp, &file_lock);
149 }
150
151 /*
152 * This function is called when the file is closed.
153 */
154
155 void fcntl_remove_locks(struct task_struct *task, struct file *filp)
/* */
156 {
157 struct file_lock *fl,*next;
158
159 for (fl = filp->f_inode->i_flock; fl != NULL; ) {
160 /*
161 * If this one is freed, {fl_next} gets clobbered when the
162 * entry is moved to the free list, so grab it now ...
163 */
164 next = fl->fl_next;
165 if (fl->fl_owner == task)
166 free_lock(filp, fl);
167 fl = next;
168 }
169 }
170
171 /*
172 * Verify a "struct flock" and copy it to a "struct file_lock" ...
173 * Result is a boolean indicating success.
174 */
175
176 static int copy_flock(struct file *filp, struct file_lock *fl, struct flock *l)
/* */
177 {
178 off_t start;
179
180 if (!filp->f_inode) /* just in case */
181 return 0;
182 if (!S_ISREG(filp->f_inode->i_mode))
183 return 0;
184 if (l->l_type != F_UNLCK && l->l_type != F_RDLCK && l->l_type != F_WRLCK)
185 return 0;
186 switch (l->l_whence) {
187 case 0 /*SEEK_SET*/ : start = 0; break;
188 case 1 /*SEEK_CUR*/ : start = filp->f_pos; break;
189 case 2 /*SEEK_END*/ : start = filp->f_inode->i_size; break;
190 default : return 0;
191 }
192 if ((start += l->l_start) < 0 || l->l_len < 0)
193 return 0;
194 fl->fl_type = l->l_type;
195 fl->fl_start = start; /* we record the absolute position */
196 fl->fl_whence = 0; /* FIXME: do we record {l_start} as passed? */
197 if (l->l_len == 0 || (fl->fl_end = start + l->l_len - 1) < 0)
198 fl->fl_end = OFFSET_MAX;
199 fl->fl_owner = current;
200 fl->fl_wait = NULL; /* just for cleanliness */
201 return 1;
202 }
203
204 /*
205 * Determine if lock {sys_fl} blocks lock {caller_fl} ...
206 */
207
208 static int conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
/* */
209 {
210 if (caller_fl->fl_owner == sys_fl->fl_owner)
211 return 0;
212 if (!overlap(caller_fl, sys_fl))
213 return 0;
214 switch (caller_fl->fl_type) {
215 case F_RDLCK :
216 return sys_fl->fl_type != F_RDLCK;
217 case F_WRLCK :
218 return 1; /* overlapping region not owned by caller */
219 }
220 return 0; /* shouldn't get here, but just in case */
221 }
222
223 static int overlap(struct file_lock *fl1, struct file_lock *fl2)
/* */
224 {
225 if (fl1->fl_start <= fl2->fl_start) {
226 return fl1->fl_end >= fl2->fl_start;
227 } else {
228 return fl2->fl_end >= fl1->fl_start;
229 }
230 }
231
232 /*
233 * Add a lock to a file ...
234 * Result is 0 for success or -ENOLCK.
235 *
236 * We try to be real clever here and always minimize the number of table
237 * entries we use. For example we merge adjacent locks whenever possible. This
238 * consumes a bit of cpu and code space, is it really worth it? Beats me.
239 *
240 * I've tried to keep the following as small and simple as possible. If you can
241 * make it smaller or simpler, please do. /dje 92Aug11
242 *
243 * WARNING: We assume the lock doesn't conflict with any other lock.
244 */
245
246 static int lock_it(struct file *filp, struct file_lock *caller)
/* */
247 {
248 struct file_lock *fl,*new;
249
250 /*
251 * It's easier if we allocate a slot for the lock first, and then
252 * release it later if we have to (IE: if it can be merged with
253 * another). This way the for() loop always knows that {caller} is an
254 * existing entry. This will cause the routine to fail unnecessarily
255 * in rare cases, but perfection can be pushed too far. :-)
256 */
257
258 if ((caller = alloc_lock(filp, caller)) == NULL)
259 return -ENOLCK;
260
261 /*
262 * First scan to see if we are changing/augmenting an existing lock ...
263 */
264
265 for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
266 if (caller->fl_owner != fl->fl_owner)
267 continue;
268 if (caller == fl)
269 continue;
270 if (!overlap(caller, fl)) {
271 /*
272 * Detect adjacent regions (if same lock type) ...
273 */
274 if (caller->fl_type != fl->fl_type)
275 continue;
276 if (caller->fl_end + 1 == fl->fl_start) {
277 fl->fl_start = caller->fl_start;
278 free_lock(filp, caller);
279 caller = fl;
280 /* must continue, may overlap others now */
281 } else if (caller->fl_start - 1 == fl->fl_end) {
282 fl->fl_end = caller->fl_end;
283 free_lock(filp, caller);
284 caller = fl;
285 /* must continue, may overlap others now */
286 }
287 continue;
288 }
289 /*
290 * We've found an overlapping region. Is it a change of lock
291 * type, or are we changing the size of the locked space?
292 */
293 if (caller->fl_type != fl->fl_type) {
294 if (caller->fl_start > fl->fl_start && caller->fl_end < fl->fl_end) {
295 /*
296 * The new lock splits the old one in two ...
297 * {fl} is the bottom piece, {caller} is the
298 * new lock, and {new} is the top piece.
299 */
300 if ((new = alloc_lock(filp, fl)) == NULL) {
301 free_lock(filp, caller);
302 return -ENOLCK;
303 }
304 fl->fl_end = caller->fl_start - 1;
305 new->fl_start = caller->fl_end + 1;
306 return 0;
307 }
308 if (caller->fl_start <= fl->fl_start && caller->fl_end >= fl->fl_end) {
309 /*
310 * The new lock completely replaces old one ...
311 */
312 free_lock(filp, fl);
313 return 0;
314 }
315 if (caller->fl_end < fl->fl_end) {
316 fl->fl_start = caller->fl_end + 1;
317 /* must continue, may be more overlaps */
318 } else if (caller->fl_start > fl->fl_start) {
319 fl->fl_end = caller->fl_start - 1;
320 /* must continue, may be more overlaps */
321 } else {
322 printk("lock_it: program bug: unanticipated overlap\n");
323 free_lock(filp, caller);
324 return -ENOLCK;
325 }
326 } else { /* The new lock augments an existing lock ... */
327 int grew = 0;
328
329 if (caller->fl_start < fl->fl_start) {
330 fl->fl_start = caller->fl_start;
331 grew = 1;
332 }
333 if (caller->fl_end > fl->fl_end) {
334 fl->fl_end = caller->fl_end;
335 grew = 1;
336 }
337 free_lock(filp, caller);
338 caller = fl;
339 if (!grew)
340 return 0;
341 /* must continue, may be more overlaps */
342 }
343 }
344
345 /*
346 * New lock doesn't overlap any regions ...
347 * alloc_lock() has already been called, so we're done!
348 */
349
350 return 0;
351 }
352
353 /*
354 * Handle F_UNLCK ...
355 * Result is 0 for success, or -EINVAL or -ENOLCK.
356 * ENOLCK can happen when a lock is split into two.
357 */
358
359 static int unlock_it(struct file *filp, struct file_lock *caller)
/* */
360 {
361 int one_unlocked = 0;
362 struct file_lock *fl,*next;
363
364 for (fl = filp->f_inode->i_flock; fl != NULL; ) {
365 if (caller->fl_owner != fl->fl_owner || !overlap(caller, fl)) {
366 fl = fl->fl_next;
367 continue;
368 }
369 one_unlocked = 1;
370 if (caller->fl_start > fl->fl_start && caller->fl_end < fl->fl_end) {
371 /*
372 * Lock is split in two ...
373 * {fl} is the bottom piece, {next} is the top piece.
374 */
375 if ((next = alloc_lock(filp, fl)) == NULL)
376 return -ENOLCK;
377 fl->fl_end = caller->fl_start - 1;
378 next->fl_start = caller->fl_end + 1;
379 return 0;
380 }
381 /*
382 * At this point we know there is an overlap and we know the
383 * lock isn't split into two ...
384 *
385 * Unless the lock table is broken, entries will not overlap.
386 * IE: User X won't have an entry locking bytes 1-3 and another
387 * entry locking bytes 3-5. Therefore, if the area being
388 * unlocked is a subset of the total area, we don't need to
389 * traverse any more of the list. The code is a tad more
390 * complicated by this optimization. Perhaps it's not worth it.
391 *
392 * WARNING: We assume free_lock() does not alter
393 * {fl_start, fl_end}.
394 *
395 * {fl_next} gets clobbered when the entry is moved to
396 * the free list, so grab it now ...
397 */
398 next = fl->fl_next;
399 if (caller->fl_start <= fl->fl_start && caller->fl_end >= fl->fl_end) {
400 free_lock(filp, fl);
401 } else if (caller->fl_start > fl->fl_start) {
402 fl->fl_end = caller->fl_start - 1;
403 } else {
404 /* caller->fl_end < fl->fl_end */
405 fl->fl_start = caller->fl_end + 1;
406 }
407 if (caller->fl_start >= fl->fl_start && caller->fl_end <= fl->fl_end)
408 return 0; /* no more to be found */
409 fl = next;
410 /* must continue, there may be more to unlock */
411 }
412
413 return one_unlocked ? 0 : -EINVAL;
414 }
415
416 static struct file_lock *alloc_lock(struct file *filp, struct file_lock *template)
/* */
417 {
418 struct file_lock *new;
419
420 if (file_lock_free_list == NULL)
421 return NULL; /* no available entry */
422 if (file_lock_free_list->fl_owner != NULL)
423 panic("alloc_lock: broken free list\n");
424
425 new = file_lock_free_list; /* remove from free list */
426 file_lock_free_list = file_lock_free_list->fl_next;
427
428 *new = *template;
429
430 new->fl_next = filp->f_inode->i_flock; /* insert into file's list */
431 filp->f_inode->i_flock = new;
432
433 new->fl_owner = current; /* FIXME: needed? */
434 new->fl_wait = NULL;
435 return new;
436 }
437
438 /*
439 * Add a lock to the free list ...
440 *
441 * WARNING: We must not alter {fl_start, fl_end}. See unlock_it().
442 */
443
444 static void free_lock(struct file *filp, struct file_lock *fl)
/* ![[last]](../icons/n_last.png)
*/
445 {
446 struct file_lock **fl_p;
447
448 if (fl->fl_owner == NULL) /* sanity check */
449 panic("free_lock: broken lock list\n");
450
451 /*
452 * We only use a singly linked list to save some memory space
453 * (the only place we'd use a doubly linked list is here).
454 */
455
456 for (fl_p = &filp->f_inode->i_flock; *fl_p != NULL; fl_p = &(*fl_p)->fl_next) {
457 if (*fl_p == fl)
458 break;
459 }
460 if (*fl_p == NULL) {
461 printk("free_lock: lock is not in file's lock list\n");
462 } else {
463 *fl_p = (*fl_p)->fl_next;
464 }
465
466 fl->fl_next = file_lock_free_list; /* add to free list */
467 file_lock_free_list = fl;
468 fl->fl_owner = NULL; /* for sanity checks */
469
470 wake_up(&fl->fl_wait);
471 }
![[bottom]](../icons/n_bottom.png){kind=icon}
*/