root/fs/locks.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. fcntl_getlk
  2. fcntl_setlk
  3. locks_deadlocked
  4. fcntl_remove_locks
  5. copy_flock
  6. conflict
  7. overlap
  8. lock_it
  9. alloc_lock
  10. 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  *  Deadlock Detection added by Kelly Carmichael, kelly@[142.24.8.65]
   8  *  September 17, 1994.
   9  *
  10  * FIXME: one thing isn't handled yet:
  11  *      - mandatory locks (requires lots of changes elsewhere)
  12  *
  13  *  Edited by Kai Petzke, wpp@marie.physik.tu-berlin.de
  14  *
  15  *  Converted file_lock_table to a linked list from an array, which eliminates
  16  *  the limits on how many active file locks are open - Chad Page
  17  *  (pageone@netcom.com), November 27, 1994 
  18  */
  19 
  20 #define DEADLOCK_DETECTION
  21 
  22 #include <asm/segment.h>
  23 
  24 #include <linux/malloc.h>
  25 #include <linux/sched.h>
  26 #include <linux/kernel.h>
  27 #include <linux/errno.h>
  28 #include <linux/stat.h>
  29 #include <linux/fcntl.h>
  30 
  31 #define OFFSET_MAX      ((off_t)0x7fffffff)     /* FIXME: move elsewhere? */
  32 
  33 static int copy_flock(struct file *filp, struct file_lock *fl, struct flock *l,
  34                       unsigned int fd);
  35 static int conflict(struct file_lock *caller_fl, struct file_lock *sys_fl);
  36 static int overlap(struct file_lock *fl1, struct file_lock *fl2);
  37 static int lock_it(struct file *filp, struct file_lock *caller, unsigned int fd);
  38 static struct file_lock *alloc_lock(struct file_lock **pos, struct file_lock *fl,
  39                                     unsigned int fd);
  40 static void free_lock(struct file_lock **fl);
  41 #ifdef DEADLOCK_DETECTION
  42 int locks_deadlocked(int my_pid,int blocked_pid);
  43 #endif
  44 
  45 static struct file_lock *file_lock_table = NULL;
  46 static struct file_lock *file_lock_free_list = NULL;
  47 
  48 int fcntl_getlk(unsigned int fd, struct flock *l)
     /* [previous][next][first][last][top][bottom][index][help] */
  49 {
  50         int error;
  51         struct flock flock;
  52         struct file *filp;
  53         struct file_lock *fl,file_lock;
  54 
  55         if (fd >= NR_OPEN || !(filp = current->files->fd[fd]))
  56                 return -EBADF;
  57         error = verify_area(VERIFY_WRITE,l, sizeof(*l));
  58         if (error)
  59                 return error;
  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, fd))
  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)
     /* [previous][next][first][last][top][bottom][index][help] */
  89 {
  90         int error;
  91         struct file *filp;
  92         struct file_lock *fl,file_lock;
  93         struct flock flock;
  94 
  95         /*
  96          * Get arguments and validate them ...
  97          */
  98 
  99         if (fd >= NR_OPEN || !(filp = current->files->fd[fd]))
 100                 return -EBADF;
 101         error = verify_area(VERIFY_READ, l, sizeof(*l));
 102         if (error)
 103                 return error;
 104         memcpy_fromfs(&flock, l, sizeof(flock));
 105         if (!copy_flock(filp, &file_lock, &flock, fd))
 106                 return -EINVAL;
 107         switch (file_lock.fl_type) {
 108         case F_RDLCK :
 109                 if (!(filp->f_mode & 1))
 110                         return -EBADF;
 111                 break;
 112         case F_WRLCK :
 113                 if (!(filp->f_mode & 2))
 114                         return -EBADF;
 115                 break;
 116         case F_SHLCK :
 117                 if (!(filp->f_mode & 3))
 118                         return -EBADF;
 119                 file_lock.fl_type = F_RDLCK;
 120                 break;
 121         case F_EXLCK :
 122                 if (!(filp->f_mode & 3))
 123                         return -EBADF;
 124                 file_lock.fl_type = F_WRLCK;
 125                 break;
 126         case F_UNLCK :
 127                 break;
 128         }
 129 
 130         /*
 131          * Scan for a conflicting lock ...
 132          */
 133   
 134         if (file_lock.fl_type != F_UNLCK) {
 135 repeat:
 136                 for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
 137                         if (!conflict(&file_lock, fl))
 138                                 continue;
 139                         /*
 140                          * File is locked by another process. If this is
 141                          * F_SETLKW wait for the lock to be released.
 142                          */
 143                         if (cmd == F_SETLKW) {
 144                                 if (current->signal & ~current->blocked)
 145                                         return -ERESTARTSYS;
 146 #ifdef DEADLOCK_DETECTION
 147                                 if (locks_deadlocked(file_lock.fl_owner->pid,fl->fl_owner->pid)) return -EDEADLOCK;
 148 #endif
 149                                 interruptible_sleep_on(&fl->fl_wait);
 150                                 if (current->signal & ~current->blocked)
 151                                         return -ERESTARTSYS;
 152                                 goto repeat;
 153                         }
 154                         return -EAGAIN;
 155                 }
 156         }
 157 
 158         /*
 159          * Lock doesn't conflict with any other lock ...
 160          */
 161 
 162         return lock_it(filp, &file_lock, fd);
 163 }
 164 
 165 #ifdef DEADLOCK_DETECTION
 166 /*
 167  * This function tests for deadlock condition before putting a process to sleep
 168  * this detection scheme is recursive... we may need some test as to make it
 169  * exit if the function gets stuck due to bad lock data.
 170  */
 171 
 172 int locks_deadlocked(int my_pid,int blocked_pid)
     /* [previous][next][first][last][top][bottom][index][help] */
 173 {
 174         int ret_val;
 175         struct wait_queue *dlock_wait;
 176         struct file_lock *fl;
 177         for (fl = file_lock_table; fl != NULL; fl = fl->fl_nextlink) {
 178                 if (fl->fl_owner == NULL) continue;     /* not a used lock */
 179                 if (fl->fl_owner->pid != my_pid) continue;
 180                 if (fl->fl_wait == NULL) continue;      /* no queues */
 181                 dlock_wait = fl->fl_wait;
 182                 do {
 183                         if (dlock_wait->task != NULL) {
 184                                 if (dlock_wait->task->pid == blocked_pid) return -EDEADLOCK;
 185                                 ret_val = locks_deadlocked(dlock_wait->task->pid,blocked_pid);
 186                                 if (ret_val) return -EDEADLOCK;
 187                         }
 188                         dlock_wait = dlock_wait->next;
 189                 } while (dlock_wait != fl->fl_wait);
 190         }
 191         return 0;
 192 }
 193 #endif
 194 
 195 /*
 196  * This function is called when the file is closed.
 197  */
 198 
 199 void fcntl_remove_locks(struct task_struct *task, struct file *filp,
     /* [previous][next][first][last][top][bottom][index][help] */
 200                         unsigned int fd)
 201 {
 202         struct file_lock *fl;
 203         struct file_lock **before;
 204 
 205         /* Find first lock owned by caller ... */
 206 
 207         before = &filp->f_inode->i_flock;
 208         while ((fl = *before) && (task != fl->fl_owner || fd != fl->fl_fd))
 209                 before = &fl->fl_next;
 210 
 211         /* The list is sorted by owner and fd ... */
 212 
 213         while ((fl = *before) && task == fl->fl_owner && fd == fl->fl_fd)
 214                 free_lock(before);
 215 }
 216 
 217 /*
 218  * Verify a "struct flock" and copy it to a "struct file_lock" ...
 219  * Result is a boolean indicating success.
 220  */
 221 
 222 static int copy_flock(struct file *filp, struct file_lock *fl, struct flock *l,
     /* [previous][next][first][last][top][bottom][index][help] */
 223                       unsigned int fd)
 224 {
 225         off_t start;
 226 
 227         if (!filp->f_inode)     /* just in case */
 228                 return 0;
 229         if (l->l_type != F_UNLCK && l->l_type != F_RDLCK && l->l_type != F_WRLCK
 230          && l->l_type != F_SHLCK && l->l_type != F_EXLCK)
 231                 return 0;
 232         switch (l->l_whence) {
 233         case 0 /*SEEK_SET*/ : start = 0; break;
 234         case 1 /*SEEK_CUR*/ : start = filp->f_pos; break;
 235         case 2 /*SEEK_END*/ : start = filp->f_inode->i_size; break;
 236         default : return 0;
 237         }
 238         if ((start += l->l_start) < 0 || l->l_len < 0)
 239                 return 0;
 240         fl->fl_type = l->l_type;
 241         fl->fl_start = start;   /* we record the absolute position */
 242         fl->fl_whence = 0;      /* FIXME: do we record {l_start} as passed? */
 243         if (l->l_len == 0 || (fl->fl_end = start + l->l_len - 1) < 0)
 244                 fl->fl_end = OFFSET_MAX;
 245         fl->fl_owner = current;
 246         fl->fl_fd = fd;
 247         fl->fl_wait = NULL;             /* just for cleanliness */
 248         return 1;
 249 }
 250 
 251 /*
 252  * Determine if lock {sys_fl} blocks lock {caller_fl} ...
 253  */
 254 
 255 static int conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
     /* [previous][next][first][last][top][bottom][index][help] */
 256 {
 257         if (   caller_fl->fl_owner == sys_fl->fl_owner
 258             && caller_fl->fl_fd == sys_fl->fl_fd)
 259                 return 0;
 260         if (!overlap(caller_fl, sys_fl))
 261                 return 0;
 262         switch (caller_fl->fl_type) {
 263         case F_RDLCK :
 264                 return sys_fl->fl_type != F_RDLCK;
 265         case F_WRLCK :
 266                 return 1;       /* overlapping region not owned by caller */
 267         }
 268         return 0;       /* shouldn't get here, but just in case */
 269 }
 270 
 271 static int overlap(struct file_lock *fl1, struct file_lock *fl2)
     /* [previous][next][first][last][top][bottom][index][help] */
 272 {
 273         return fl1->fl_end >= fl2->fl_start && fl2->fl_end >= fl1->fl_start;
 274 }
 275 
 276 /*
 277  * Add a lock to a file ...
 278  * Result is 0 for success or -ENOLCK.
 279  *
 280  * We merge adjacent locks whenever possible.
 281  *
 282  * WARNING: We assume the lock doesn't conflict with any other lock.
 283  */
 284   
 285 /*
 286  * Rewritten by Kai Petzke:
 287  * We sort the lock list first by owner, then by the starting address.
 288  *
 289  * To make freeing a lock much faster, we keep a pointer to the lock before the
 290  * actual one. But the real gain of the new coding was, that lock_it() and
 291  * unlock_it() became one function.
 292  *
 293  * To all purists: Yes, I use a few goto's. Just pass on to the next function.
 294  */
 295 
 296 static int lock_it(struct file *filp, struct file_lock *caller, unsigned int fd)
     /* [previous][next][first][last][top][bottom][index][help] */
 297 {
 298         struct file_lock *fl;
 299         struct file_lock *left = 0;
 300         struct file_lock *right = 0;
 301         struct file_lock **before;
 302         int added = 0;
 303 
 304         /*
 305          * Find the first old lock with the same owner as the new lock.
 306          */
 307 
 308         before = &filp->f_inode->i_flock;
 309         while ((fl = *before) &&
 310             (caller->fl_owner != fl->fl_owner ||
 311              caller->fl_fd != fl->fl_fd))
 312                 before = &fl->fl_next;
 313 
 314         /*
 315          * Look up all locks of this owner.
 316          */
 317 
 318         while (   (fl = *before)
 319                && caller->fl_owner == fl->fl_owner
 320                && caller->fl_fd == fl->fl_fd) {
 321                 /*
 322                  * Detect adjacent or overlapping regions (if same lock type)
 323                  */
 324                 if (caller->fl_type == fl->fl_type) {
 325                         if (fl->fl_end < caller->fl_start - 1)
 326                                 goto next_lock;
 327                         /*
 328                          * If the next lock in the list has entirely bigger
 329                          * addresses than the new one, insert the lock here.
 330                          */
 331                         if (fl->fl_start > caller->fl_end + 1)
 332                                 break;
 333 
 334                         /*
 335                          * If we come here, the new and old lock are of the
 336                          * same type and adjacent or overlapping. Make one
 337                          * lock yielding from the lower start address of both
 338                          * locks to the higher end address.
 339                          */
 340                         if (fl->fl_start > caller->fl_start)
 341                                 fl->fl_start = caller->fl_start;
 342                         else
 343                                 caller->fl_start = fl->fl_start;
 344                         if (fl->fl_end < caller->fl_end)
 345                                 fl->fl_end = caller->fl_end;
 346                         else
 347                                 caller->fl_end = fl->fl_end;
 348                         if (added) {
 349                                 free_lock(before);
 350                                 continue;
 351                         }
 352                         caller = fl;
 353                         added = 1;
 354                         goto next_lock;
 355                 }
 356                 /*
 357                  * Processing for different lock types is a bit more complex.
 358                  */
 359                 if (fl->fl_end < caller->fl_start)
 360                         goto next_lock;
 361                 if (fl->fl_start > caller->fl_end)
 362                         break;
 363                 if (caller->fl_type == F_UNLCK)
 364                         added = 1;
 365                 if (fl->fl_start < caller->fl_start)
 366                         left = fl;
 367                 /*
 368                  * If the next lock in the list has a higher end address than
 369                  * the new one, insert the new one here.
 370                  */
 371                 if (fl->fl_end > caller->fl_end) {
 372                         right = fl;
 373                         break;
 374                 }
 375                 if (fl->fl_start >= caller->fl_start) {
 376                         /*
 377                          * The new lock completely replaces an old one (This may
 378                          * happen several times).
 379                          */
 380                         if (added) {
 381                                 free_lock(before);
 382                                 continue;
 383                         }
 384                         /*
 385                          * Replace the old lock with the new one. Wake up
 386                          * anybody waiting for the old one, as the change in
 387                          * lock type might satisfy his needs.
 388                          */
 389                         wake_up(&fl->fl_wait);
 390                         fl->fl_start = caller->fl_start;
 391                         fl->fl_end   = caller->fl_end;
 392                         fl->fl_type  = caller->fl_type;
 393                         caller = fl;
 394                         added = 1;
 395                 }
 396                 /*
 397                  * Go on to next lock.
 398                  */
 399 next_lock:
 400                 before = &(*before)->fl_next;
 401         }
 402 
 403         if (! added) {
 404                 if (caller->fl_type == F_UNLCK) {
 405 /*
 406  * XXX - under iBCS-2, attempting to unlock a not-locked region is 
 407  *      not considered an error condition, although I'm not sure if this 
 408  *      should be a default behavior (it makes porting to native Linux easy)
 409  *      or a personality option.
 410  *
 411  *      Does Xopen/1170 say anything about this?
 412  *      - drew@Colorado.EDU
 413  */
 414 #if 0
 415                         return -EINVAL;
 416 #else
 417                         return 0;
 418 #endif
 419                 }
 420                 if (! (caller = alloc_lock(before, caller, fd)))
 421                         return -ENOLCK;
 422         }
 423         if (right) {
 424                 if (left == right) {
 425                         /*
 426                          * The new lock breaks the old one in two pieces, so we
 427                          * have to allocate one more lock (in this case, even
 428                          * F_UNLCK may fail!).
 429                          */
 430                         if (! (left = alloc_lock(before, right, fd))) {
 431                                 if (! added)
 432                                         free_lock(before);
 433                                 return -ENOLCK;
 434                         }
 435                 }
 436                 right->fl_start = caller->fl_end + 1;
 437         }
 438         if (left)
 439                 left->fl_end = caller->fl_start - 1;
 440         return 0;
 441 }
 442 
 443 /*
 444  * File_lock() inserts a lock at the position pos of the linked list.
 445  *
 446  *  Modified to create a new node if no free entries available - Chad Page
 447  *
 448  */
 449 
 450 static struct file_lock *alloc_lock(struct file_lock **pos,
     /* [previous][next][first][last][top][bottom][index][help] */
 451                                     struct file_lock *fl,
 452                                     unsigned int     fd)
 453 {
 454         struct file_lock *tmp;
 455 
 456         tmp = file_lock_free_list;
 457 
 458         if (tmp == NULL)
 459         {
 460                 /* Okay, let's make a new file_lock structure... */
 461                 tmp = (struct file_lock *)kmalloc(sizeof(struct file_lock), GFP_KERNEL);
 462                 tmp -> fl_owner = NULL;
 463                 tmp -> fl_next = file_lock_free_list;
 464                 tmp -> fl_nextlink = file_lock_table;
 465                 file_lock_table = tmp;
 466         }
 467         else
 468         {
 469                 /* remove from free list */
 470                 file_lock_free_list = tmp->fl_next;
 471         }
 472 
 473         if (tmp->fl_owner != NULL)
 474                 panic("alloc_lock: broken free list\n");
 475 
 476         tmp->fl_next = *pos;    /* insert into file's list */
 477         *pos = tmp;
 478 
 479         tmp->fl_owner = current;        /* FIXME: needed? */
 480         tmp->fl_fd = fd;                /* FIXME: needed? */
 481         tmp->fl_wait = NULL;
 482 
 483         tmp->fl_type = fl->fl_type;
 484         tmp->fl_whence = fl->fl_whence;
 485         tmp->fl_start = fl->fl_start;
 486         tmp->fl_end = fl->fl_end;
 487 
 488         return tmp;
 489 }
 490 
 491 /*
 492  * Add a lock to the free list ...
 493  */
 494 
 495 static void free_lock(struct file_lock **fl_p)
     /* [previous][next][first][last][top][bottom][index][help] */
 496 {
 497         struct file_lock *fl;
 498 
 499         fl = *fl_p;
 500         if (fl->fl_owner == NULL)       /* sanity check */
 501                 panic("free_lock: broken lock list\n");
 502 
 503         *fl_p = (*fl_p)->fl_next;
 504 
 505         fl->fl_next = file_lock_free_list;      /* add to free list */
 506         file_lock_free_list = fl;
 507         fl->fl_owner = NULL;                    /* for sanity checks */
 508 
 509         wake_up(&fl->fl_wait);
 510 }

/* [previous][next][first][last][top][bottom][index][help] */