root/fs/locks.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. fcntl_init_locks
  2. fcntl_getlk
  3. fcntl_setlk
  4. fcntl_remove_locks
  5. copy_flock
  6. conflict
  7. overlap
  8. lock_it
  9. unlock_it
  10. alloc_lock
  11. free_lock

   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)
     /* [<][>][^][v][top][bottom][index][help] */
  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)
     /* [<][>][^][v][top][bottom][index][help] */
  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)
     /* [<][>][^][v][top][bottom][index][help] */
  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_SHLCK :
 114                 if (!(filp->f_mode & 3))
 115                         return -EBADF;
 116                 file_lock.fl_type = F_RDLCK;
 117                 break;
 118         case F_EXLCK :
 119                 if (!(filp->f_mode & 3))
 120                         return -EBADF;
 121                 file_lock.fl_type = F_WRLCK;
 122                 break;
 123         case F_UNLCK :
 124                 break;
 125         }
 126 
 127         /*
 128          * F_UNLCK needs to be handled differently ...
 129          */
 130 
 131         if (file_lock.fl_type == F_UNLCK)
 132                 return unlock_it(filp, &file_lock);
 133 
 134         /*
 135          * Scan for a conflicting lock ...
 136          */
 137 
 138 repeat:
 139         for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
 140                 if (!conflict(&file_lock, fl))
 141                         continue;
 142                 /*
 143                  * File is locked by another process. If this is F_SETLKW
 144                  * wait for the lock to be released.
 145                  * FIXME: We need to check for deadlocks here.
 146                  */
 147                 if (cmd == F_SETLKW) {
 148                         interruptible_sleep_on(&fl->fl_wait);
 149                         goto repeat;
 150                 }
 151                 return -EAGAIN;
 152         }
 153 
 154         /*
 155          * Lock doesn't conflict with any other lock ...
 156          */
 157 
 158         return lock_it(filp, &file_lock);
 159 }
 160 
 161 /*
 162  * This function is called when the file is closed.
 163  */
 164 
 165 void fcntl_remove_locks(struct task_struct *task, struct file *filp)
     /* [<][>][^][v][top][bottom][index][help] */
 166 {
 167         struct file_lock *fl,*next;
 168 
 169         for (fl = filp->f_inode->i_flock; fl != NULL; ) {
 170                 /*
 171                  * If this one is freed, {fl_next} gets clobbered when the
 172                  * entry is moved to the free list, so grab it now ...
 173                  */
 174                 next = fl->fl_next;
 175                 if (fl->fl_owner == task)
 176                         free_lock(filp, fl);
 177                 fl = next;
 178         }
 179 }
 180 
 181 /*
 182  * Verify a "struct flock" and copy it to a "struct file_lock" ...
 183  * Result is a boolean indicating success.
 184  */
 185 
 186 static int copy_flock(struct file *filp, struct file_lock *fl, struct flock *l)
     /* [<][>][^][v][top][bottom][index][help] */
 187 {
 188         off_t start;
 189 
 190         if (!filp->f_inode)     /* just in case */
 191                 return 0;
 192         if (!S_ISREG(filp->f_inode->i_mode))
 193                 return 0;
 194         if (l->l_type != F_UNLCK && l->l_type != F_RDLCK && l->l_type != F_WRLCK)
 195                 return 0;
 196         switch (l->l_whence) {
 197         case 0 /*SEEK_SET*/ : start = 0; break;
 198         case 1 /*SEEK_CUR*/ : start = filp->f_pos; break;
 199         case 2 /*SEEK_END*/ : start = filp->f_inode->i_size; break;
 200         default : return 0;
 201         }
 202         if ((start += l->l_start) < 0 || l->l_len < 0)
 203                 return 0;
 204         fl->fl_type = l->l_type;
 205         fl->fl_start = start;   /* we record the absolute position */
 206         fl->fl_whence = 0;      /* FIXME: do we record {l_start} as passed? */
 207         if (l->l_len == 0 || (fl->fl_end = start + l->l_len - 1) < 0)
 208                 fl->fl_end = OFFSET_MAX;
 209         fl->fl_owner = current;
 210         fl->fl_wait = NULL;             /* just for cleanliness */
 211         return 1;
 212 }
 213 
 214 /*
 215  * Determine if lock {sys_fl} blocks lock {caller_fl} ...
 216  */
 217 
 218 static int conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
     /* [<][>][^][v][top][bottom][index][help] */
 219 {
 220         if (caller_fl->fl_owner == sys_fl->fl_owner)
 221                 return 0;
 222         if (!overlap(caller_fl, sys_fl))
 223                 return 0;
 224         switch (caller_fl->fl_type) {
 225         case F_RDLCK :
 226                 return sys_fl->fl_type != F_RDLCK;
 227         case F_WRLCK :
 228                 return 1;       /* overlapping region not owned by caller */
 229         }
 230         return 0;       /* shouldn't get here, but just in case */
 231 }
 232 
 233 static int overlap(struct file_lock *fl1, struct file_lock *fl2)
     /* [<][>][^][v][top][bottom][index][help] */
 234 {
 235         if (fl1->fl_start <= fl2->fl_start) {
 236                 return fl1->fl_end >= fl2->fl_start;
 237         } else {
 238                 return fl2->fl_end >= fl1->fl_start;
 239         }
 240 }
 241 
 242 /*
 243  * Add a lock to a file ...
 244  * Result is 0 for success or -ENOLCK.
 245  *
 246  * We try to be real clever here and always minimize the number of table
 247  * entries we use. For example we merge adjacent locks whenever possible. This
 248  * consumes a bit of cpu and code space, is it really worth it? Beats me.
 249  *
 250  * I've tried to keep the following as small and simple as possible. If you can
 251  * make it smaller or simpler, please do. /dje 92Aug11
 252  *
 253  * WARNING: We assume the lock doesn't conflict with any other lock.
 254  */
 255 
 256 static int lock_it(struct file *filp, struct file_lock *caller)
     /* [<][>][^][v][top][bottom][index][help] */
 257 {
 258         struct file_lock *fl,*new;
 259 
 260         /*
 261          * It's easier if we allocate a slot for the lock first, and then
 262          * release it later if we have to (IE: if it can be merged with
 263          * another). This way the for() loop always knows that {caller} is an
 264          * existing entry. This will cause the routine to fail unnecessarily
 265          * in rare cases, but perfection can be pushed too far. :-)
 266          */
 267 
 268         if ((caller = alloc_lock(filp, caller)) == NULL)
 269                 return -ENOLCK;
 270 
 271         /*
 272          * First scan to see if we are changing/augmenting an existing lock ...
 273          */
 274 
 275         for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
 276                 if (caller->fl_owner != fl->fl_owner)
 277                         continue;
 278                 if (caller == fl)
 279                         continue;
 280                 if (!overlap(caller, fl)) {
 281                         /*
 282                          * Detect adjacent regions (if same lock type) ...
 283                          */
 284                         if (caller->fl_type != fl->fl_type)
 285                                 continue;
 286                         if (caller->fl_end + 1 == fl->fl_start) {
 287                                 fl->fl_start = caller->fl_start;
 288                                 free_lock(filp, caller);
 289                                 caller = fl;
 290                                 /* must continue, may overlap others now */
 291                         } else if (caller->fl_start - 1 == fl->fl_end) {
 292                                 fl->fl_end = caller->fl_end;
 293                                 free_lock(filp, caller);
 294                                 caller = fl;
 295                                 /* must continue, may overlap others now */
 296                         }
 297                         continue;
 298                 }
 299                 /*
 300                  * We've found an overlapping region. Is it a change of lock
 301                  * type, or are we changing the size of the locked space?
 302                  */
 303                 if (caller->fl_type != fl->fl_type) {
 304                         if (caller->fl_start > fl->fl_start && caller->fl_end < fl->fl_end) {
 305                                 /*
 306                                  * The new lock splits the old one in two ...
 307                                  * {fl} is the bottom piece, {caller} is the
 308                                  * new lock, and {new} is the top piece.
 309                                  */
 310                                 if ((new = alloc_lock(filp, fl)) == NULL) {
 311                                         free_lock(filp, caller);
 312                                         return -ENOLCK;
 313                                 }
 314                                 fl->fl_end = caller->fl_start - 1;
 315                                 new->fl_start = caller->fl_end + 1;
 316                                 return 0;
 317                         }
 318                         if (caller->fl_start <= fl->fl_start && caller->fl_end >= fl->fl_end) {
 319                                 /*
 320                                  * The new lock completely replaces old one ...
 321                                  */
 322                                 free_lock(filp, fl);
 323                                 return 0;
 324                         }
 325                         if (caller->fl_end < fl->fl_end) {
 326                                 fl->fl_start = caller->fl_end + 1;
 327                                 /* must continue, may be more overlaps */
 328                         } else if (caller->fl_start > fl->fl_start) {
 329                                 fl->fl_end = caller->fl_start - 1;
 330                                 /* must continue, may be more overlaps */
 331                         } else {
 332                                 printk("lock_it: program bug: unanticipated overlap\n");
 333                                 free_lock(filp, caller);
 334                                 return -ENOLCK;
 335                         }
 336                 } else {        /* The new lock augments an existing lock ... */
 337                         int grew = 0;
 338 
 339                         if (caller->fl_start < fl->fl_start) {
 340                                 fl->fl_start = caller->fl_start;
 341                                 grew = 1;
 342                         }
 343                         if (caller->fl_end > fl->fl_end) {
 344                                 fl->fl_end = caller->fl_end;
 345                                 grew = 1;
 346                         }
 347                         free_lock(filp, caller);
 348                         caller = fl;
 349                         if (!grew)
 350                                 return 0;
 351                         /* must continue, may be more overlaps */
 352                 }
 353         }
 354 
 355         /*
 356          * New lock doesn't overlap any regions ...
 357          * alloc_lock() has already been called, so we're done!
 358          */
 359 
 360         return 0;
 361 }
 362 
 363 /*
 364  * Handle F_UNLCK ...
 365  * Result is 0 for success, or -EINVAL or -ENOLCK.
 366  * ENOLCK can happen when a lock is split into two.
 367  */
 368 
 369 static int unlock_it(struct file *filp, struct file_lock *caller)
     /* [<][>][^][v][top][bottom][index][help] */
 370 {
 371         int one_unlocked = 0;
 372         struct file_lock *fl,*next;
 373 
 374         for (fl = filp->f_inode->i_flock; fl != NULL; ) {
 375                 if (caller->fl_owner != fl->fl_owner || !overlap(caller, fl)) {
 376                         fl = fl->fl_next;
 377                         continue;
 378                 }
 379                 one_unlocked = 1;
 380                 if (caller->fl_start > fl->fl_start && caller->fl_end < fl->fl_end) {
 381                         /*
 382                          * Lock is split in two ...
 383                          * {fl} is the bottom piece, {next} is the top piece.
 384                          */
 385                         if ((next = alloc_lock(filp, fl)) == NULL)
 386                                 return -ENOLCK;
 387                         fl->fl_end = caller->fl_start - 1;
 388                         next->fl_start = caller->fl_end + 1;
 389                         return 0;
 390                 }
 391                 /*
 392                  * At this point we know there is an overlap and we know the
 393                  * lock isn't split into two ...
 394                  *
 395                  * Unless the lock table is broken, entries will not overlap.
 396                  * IE: User X won't have an entry locking bytes 1-3 and another
 397                  * entry locking bytes 3-5. Therefore, if the area being
 398                  * unlocked is a subset of the total area, we don't need to
 399                  * traverse any more of the list. The code is a tad more
 400                  * complicated by this optimization. Perhaps it's not worth it.
 401                  *
 402                  * WARNING: We assume free_lock() does not alter
 403                  *      {fl_start, fl_end}.
 404                  *
 405                  * {fl_next} gets clobbered when the entry is moved to
 406                  * the free list, so grab it now ...
 407                  */
 408                 next = fl->fl_next;
 409                 if (caller->fl_start <= fl->fl_start && caller->fl_end >= fl->fl_end) {
 410                         free_lock(filp, fl);
 411                 } else if (caller->fl_start > fl->fl_start) {
 412                         fl->fl_end = caller->fl_start - 1;
 413                 } else {
 414                         /* caller->fl_end < fl->fl_end */
 415                         fl->fl_start = caller->fl_end + 1;
 416                 }
 417                 if (caller->fl_start >= fl->fl_start && caller->fl_end <= fl->fl_end)
 418                         return 0;               /* no more to be found */
 419                 fl = next;
 420                 /* must continue, there may be more to unlock */
 421         }
 422 
 423         return one_unlocked ? 0 : -EINVAL;
 424 }
 425 
 426 static struct file_lock *alloc_lock(struct file *filp, struct file_lock *template)
     /* [<][>][^][v][top][bottom][index][help] */
 427 {
 428         struct file_lock *new;
 429 
 430         if (file_lock_free_list == NULL)
 431                 return NULL;                    /* no available entry */
 432         if (file_lock_free_list->fl_owner != NULL)
 433                 panic("alloc_lock: broken free list\n");
 434 
 435         new = file_lock_free_list;              /* remove from free list */
 436         file_lock_free_list = file_lock_free_list->fl_next;
 437 
 438         *new = *template;
 439 
 440         new->fl_next = filp->f_inode->i_flock;  /* insert into file's list */
 441         filp->f_inode->i_flock = new;
 442 
 443         new->fl_owner = current;        /* FIXME: needed? */
 444         new->fl_wait = NULL;
 445         return new;
 446 }
 447 
 448 /*
 449  * Add a lock to the free list ...
 450  *
 451  * WARNING: We must not alter {fl_start, fl_end}. See unlock_it().
 452  */
 453 
 454 static void free_lock(struct file *filp, struct file_lock *fl)
     /* [<][>][^][v][top][bottom][index][help] */
 455 {
 456         struct file_lock **fl_p;
 457 
 458         if (fl->fl_owner == NULL)       /* sanity check */
 459                 panic("free_lock: broken lock list\n");
 460 
 461         /*
 462          * We only use a singly linked list to save some memory space
 463          * (the only place we'd use a doubly linked list is here).
 464          */
 465 
 466         for (fl_p = &filp->f_inode->i_flock; *fl_p != NULL; fl_p = &(*fl_p)->fl_next) {
 467                 if (*fl_p == fl)
 468                         break;
 469         }
 470         if (*fl_p == NULL) {
 471                 printk("free_lock: lock is not in file's lock list\n");
 472         } else {
 473                 *fl_p = (*fl_p)->fl_next;
 474         }
 475 
 476         fl->fl_next = file_lock_free_list;      /* add to free list */
 477         file_lock_free_list = fl;
 478         fl->fl_owner = NULL;                    /* for sanity checks */
 479 
 480         wake_up(&fl->fl_wait);
 481 }

/* [<][>][^][v][top][bottom][index][help] */