home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / KERNEL-S / V1.0 / LINUX-1.0 / LINUX-1 / linux / fs / locks.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-01  |  11.2 KB  |  455 lines
  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.  *  Edited by Kai Petzke, wpp@marie.physik.tu-berlin.de
  13.  */
  14.  
  15. #include <asm/segment.h>
  16.  
  17. #include <linux/sched.h>
  18. #include <linux/kernel.h>
  19. #include <linux/errno.h>
  20. #include <linux/stat.h>
  21. #include <linux/fcntl.h>
  22.  
  23. #define OFFSET_MAX    ((off_t)0x7fffffff)    /* FIXME: move elsewhere? */
  24.  
  25. static int copy_flock(struct file *filp, struct file_lock *fl, struct flock *l,
  26.                       unsigned int fd);
  27. static int conflict(struct file_lock *caller_fl, struct file_lock *sys_fl);
  28. static int overlap(struct file_lock *fl1, struct file_lock *fl2);
  29. static int lock_it(struct file *filp, struct file_lock *caller, unsigned int fd);
  30. static struct file_lock *alloc_lock(struct file_lock **pos, struct file_lock *fl,
  31.                                     unsigned int fd);
  32. static void free_lock(struct file_lock **fl);
  33.  
  34. static struct file_lock file_lock_table[NR_FILE_LOCKS];
  35. static struct file_lock *file_lock_free_list;
  36.  
  37. /*
  38.  * Called at boot time to initialize the lock table ...
  39.  */
  40.  
  41. void fcntl_init_locks(void)
  42. {
  43.     struct file_lock *fl;
  44.  
  45.     for (fl = &file_lock_table[0]; fl < file_lock_table + NR_FILE_LOCKS - 1; fl++) {
  46.         fl->fl_next = fl + 1;
  47.         fl->fl_owner = NULL;
  48.     }
  49.     file_lock_table[NR_FILE_LOCKS - 1].fl_next = NULL;
  50.     file_lock_table[NR_FILE_LOCKS - 1].fl_owner = NULL;
  51.     file_lock_free_list = &file_lock_table[0];
  52. }
  53.  
  54. int fcntl_getlk(unsigned int fd, struct flock *l)
  55. {
  56.     int error;
  57.     struct flock flock;
  58.     struct file *filp;
  59.     struct file_lock *fl,file_lock;
  60.  
  61.     if (fd >= NR_OPEN || !(filp = current->filp[fd]))
  62.         return -EBADF;
  63.     error = verify_area(VERIFY_WRITE,l, sizeof(*l));
  64.     if (error)
  65.         return error;
  66.     memcpy_fromfs(&flock, l, sizeof(flock));
  67.     if (flock.l_type == F_UNLCK)
  68.         return -EINVAL;
  69.     if (!copy_flock(filp, &file_lock, &flock, fd))
  70.         return -EINVAL;
  71.  
  72.     for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
  73.         if (conflict(&file_lock, fl)) {
  74.             flock.l_pid = fl->fl_owner->pid;
  75.             flock.l_start = fl->fl_start;
  76.             flock.l_len = fl->fl_end == OFFSET_MAX ? 0 :
  77.                 fl->fl_end - fl->fl_start + 1;
  78.             flock.l_whence = fl->fl_whence;
  79.             flock.l_type = fl->fl_type;
  80.             memcpy_tofs(l, &flock, sizeof(flock));
  81.             return 0;
  82.         }
  83.     }
  84.  
  85.     flock.l_type = F_UNLCK;            /* no conflict found */
  86.     memcpy_tofs(l, &flock, sizeof(flock));
  87.     return 0;
  88. }
  89.  
  90. /*
  91.  * This function implements both F_SETLK and F_SETLKW.
  92.  */
  93.  
  94. int fcntl_setlk(unsigned int fd, unsigned int cmd, struct flock *l)
  95. {
  96.     int error;
  97.     struct file *filp;
  98.     struct file_lock *fl,file_lock;
  99.     struct flock flock;
  100.  
  101.     /*
  102.      * Get arguments and validate them ...
  103.      */
  104.  
  105.     if (fd >= NR_OPEN || !(filp = current->filp[fd]))
  106.         return -EBADF;
  107.     error = verify_area(VERIFY_WRITE, l, sizeof(*l));
  108.     if (error)
  109.         return error;
  110.     memcpy_fromfs(&flock, l, sizeof(flock));
  111.     if (!copy_flock(filp, &file_lock, &flock, fd))
  112.         return -EINVAL;
  113.     switch (file_lock.fl_type) {
  114.     case F_RDLCK :
  115.         if (!(filp->f_mode & 1))
  116.             return -EBADF;
  117.         break;
  118.     case F_WRLCK :
  119.         if (!(filp->f_mode & 2))
  120.             return -EBADF;
  121.         break;
  122.     case F_SHLCK :
  123.         if (!(filp->f_mode & 3))
  124.             return -EBADF;
  125.         file_lock.fl_type = F_RDLCK;
  126.         break;
  127.     case F_EXLCK :
  128.         if (!(filp->f_mode & 3))
  129.             return -EBADF;
  130.         file_lock.fl_type = F_WRLCK;
  131.         break;
  132.     case F_UNLCK :
  133.         break;
  134.     }
  135.  
  136.       /*
  137.        * Scan for a conflicting lock ...
  138.        */
  139.   
  140.     if (file_lock.fl_type != F_UNLCK) {
  141. repeat:
  142.         for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
  143.             if (!conflict(&file_lock, fl))
  144.                 continue;
  145.             /*
  146.              * File is locked by another process. If this is
  147.              * F_SETLKW wait for the lock to be released.
  148.              * FIXME: We need to check for deadlocks here.
  149.              */
  150.             if (cmd == F_SETLKW) {
  151.                 if (current->signal & ~current->blocked)
  152.                     return -ERESTARTSYS;
  153.                 interruptible_sleep_on(&fl->fl_wait);
  154.                 if (current->signal & ~current->blocked)
  155.                     return -ERESTARTSYS;
  156.                 goto repeat;
  157.             }
  158.             return -EAGAIN;
  159.           }
  160.       }
  161.  
  162.     /*
  163.      * Lock doesn't conflict with any other lock ...
  164.      */
  165.  
  166.     return lock_it(filp, &file_lock, fd);
  167. }
  168.  
  169. /*
  170.  * This function is called when the file is closed.
  171.  */
  172.  
  173. void fcntl_remove_locks(struct task_struct *task, struct file *filp,
  174.                         unsigned int fd)
  175. {
  176.     struct file_lock *fl;
  177.     struct file_lock **before;
  178.  
  179.     /* Find first lock owned by caller ... */
  180.  
  181.     before = &filp->f_inode->i_flock;
  182.     while ((fl = *before) && (task != fl->fl_owner || fd != fl->fl_fd))
  183.         before = &fl->fl_next;
  184.  
  185.     /* The list is sorted by owner and fd ... */
  186.  
  187.     while ((fl = *before) && task == fl->fl_owner && fd == fl->fl_fd)
  188.         free_lock(before);
  189. }
  190.  
  191. /*
  192.  * Verify a "struct flock" and copy it to a "struct file_lock" ...
  193.  * Result is a boolean indicating success.
  194.  */
  195.  
  196. static int copy_flock(struct file *filp, struct file_lock *fl, struct flock *l,
  197.                       unsigned int fd)
  198. {
  199.     off_t start;
  200.  
  201.     if (!filp->f_inode)    /* just in case */
  202.         return 0;
  203.     if (!S_ISREG(filp->f_inode->i_mode))
  204.         return 0;
  205.     if (l->l_type != F_UNLCK && l->l_type != F_RDLCK && l->l_type != F_WRLCK
  206.      && l->l_type != F_SHLCK && l->l_type != F_EXLCK)
  207.         return 0;
  208.     switch (l->l_whence) {
  209.     case 0 /*SEEK_SET*/ : start = 0; break;
  210.     case 1 /*SEEK_CUR*/ : start = filp->f_pos; break;
  211.     case 2 /*SEEK_END*/ : start = filp->f_inode->i_size; break;
  212.     default : return 0;
  213.     }
  214.     if ((start += l->l_start) < 0 || l->l_len < 0)
  215.         return 0;
  216.     fl->fl_type = l->l_type;
  217.     fl->fl_start = start;    /* we record the absolute position */
  218.     fl->fl_whence = 0;    /* FIXME: do we record {l_start} as passed? */
  219.     if (l->l_len == 0 || (fl->fl_end = start + l->l_len - 1) < 0)
  220.         fl->fl_end = OFFSET_MAX;
  221.     fl->fl_owner = current;
  222.     fl->fl_fd = fd;
  223.     fl->fl_wait = NULL;        /* just for cleanliness */
  224.     return 1;
  225. }
  226.  
  227. /*
  228.  * Determine if lock {sys_fl} blocks lock {caller_fl} ...
  229.  */
  230.  
  231. static int conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
  232. {
  233.     if (   caller_fl->fl_owner == sys_fl->fl_owner
  234.             && caller_fl->fl_fd == sys_fl->fl_fd)
  235.         return 0;
  236.     if (!overlap(caller_fl, sys_fl))
  237.         return 0;
  238.     switch (caller_fl->fl_type) {
  239.     case F_RDLCK :
  240.         return sys_fl->fl_type != F_RDLCK;
  241.     case F_WRLCK :
  242.         return 1;    /* overlapping region not owned by caller */
  243.     }
  244.     return 0;    /* shouldn't get here, but just in case */
  245. }
  246.  
  247. static int overlap(struct file_lock *fl1, struct file_lock *fl2)
  248. {
  249.     return fl1->fl_end >= fl2->fl_start && fl2->fl_end >= fl1->fl_start;
  250. }
  251.  
  252. /*
  253.  * Add a lock to a file ...
  254.  * Result is 0 for success or -ENOLCK.
  255.  *
  256.  * We merge adjacent locks whenever possible.
  257.  *
  258.  * WARNING: We assume the lock doesn't conflict with any other lock.
  259.  */
  260.   
  261. /*
  262.  * Rewritten by Kai Petzke:
  263.  * We sort the lock list first by owner, then by the starting address.
  264.  *
  265.  * To make freeing a lock much faster, we keep a pointer to the lock before the
  266.  * actual one. But the real gain of the new coding was, that lock_it() and
  267.  * unlock_it() became one function.
  268.  *
  269.  * To all purists: Yes, I use a few goto's. Just pass on to the next function.
  270.  */
  271.  
  272. static int lock_it(struct file *filp, struct file_lock *caller, unsigned int fd)
  273. {
  274.     struct file_lock *fl;
  275.     struct file_lock *left = 0;
  276.     struct file_lock *right = 0;
  277.     struct file_lock **before;
  278.     int added = 0;
  279.  
  280.     /*
  281.      * Find the first old lock with the same owner as the new lock.
  282.      */
  283.  
  284.     before = &filp->f_inode->i_flock;
  285.     while ((fl = *before) &&
  286.         (caller->fl_owner != fl->fl_owner ||
  287.          caller->fl_fd != fl->fl_fd))
  288.         before = &fl->fl_next;
  289.  
  290.     /*
  291.      * Look up all locks of this owner.
  292.      */
  293.  
  294.     while (   (fl = *before)
  295.                && caller->fl_owner == fl->fl_owner
  296.                && caller->fl_fd == fl->fl_fd) {
  297.         /*
  298.          * Detect adjacent or overlapping regions (if same lock type)
  299.          */
  300.         if (caller->fl_type == fl->fl_type) {
  301.             if (fl->fl_end < caller->fl_start - 1)
  302.                 goto next_lock;
  303.             /*
  304.              * If the next lock in the list has entirely bigger
  305.              * addresses than the new one, insert the lock here.
  306.              */
  307.             if (fl->fl_start > caller->fl_end + 1)
  308.                 break;
  309.  
  310.             /*
  311.              * If we come here, the new and old lock are of the
  312.              * same type and adjacent or overlapping. Make one
  313.              * lock yielding from the lower start address of both
  314.              * locks to the higher end address.
  315.              */
  316.             if (fl->fl_start > caller->fl_start)
  317.                 fl->fl_start = caller->fl_start;
  318.             else
  319.                 caller->fl_start = fl->fl_start;
  320.             if (fl->fl_end < caller->fl_end)
  321.                 fl->fl_end = caller->fl_end;
  322.             else
  323.                 caller->fl_end = fl->fl_end;
  324.             if (added) {
  325.                 free_lock(before);
  326.                 continue;
  327.             }
  328.             caller = fl;
  329.             added = 1;
  330.             goto next_lock;
  331.         }
  332.         /*
  333.          * Processing for different lock types is a bit more complex.
  334.          */
  335.         if (fl->fl_end < caller->fl_start)
  336.             goto next_lock;
  337.         if (fl->fl_start > caller->fl_end)
  338.             break;
  339.         if (caller->fl_type == F_UNLCK)
  340.             added = 1;
  341.         if (fl->fl_start < caller->fl_start)
  342.             left = fl;
  343.         /*
  344.          * If the next lock in the list has a higher end address than
  345.          * the new one, insert the new one here.
  346.          */
  347.         if (fl->fl_end > caller->fl_end) {
  348.             right = fl;
  349.             break;
  350.         }
  351.         if (fl->fl_start >= caller->fl_start) {
  352.             /*
  353.              * The new lock completely replaces an old one (This may
  354.              * happen several times).
  355.              */
  356.             if (added) {
  357.                 free_lock(before);
  358.                 continue;
  359.             }
  360.             /*
  361.              * Replace the old lock with the new one. Wake up
  362.              * anybody waiting for the old one, as the change in
  363.              * lock type migth satisfy his needs.
  364.              */
  365.             wake_up(&fl->fl_wait);
  366.             fl->fl_start = caller->fl_start;
  367.             fl->fl_end   = caller->fl_end;
  368.             fl->fl_type  = caller->fl_type;
  369.             caller = fl;
  370.             added = 1;
  371.         }
  372.         /*
  373.          * Go on to next lock.
  374.          */
  375. next_lock:
  376.         before = &(*before)->fl_next;
  377.     }
  378.  
  379.     if (! added) {
  380.         if (caller->fl_type == F_UNLCK)
  381.             return -EINVAL;
  382.         if (! (caller = alloc_lock(before, caller, fd)))
  383.             return -ENOLCK;
  384.     }
  385.     if (right) {
  386.         if (left == right) {
  387.             /*
  388.              * The new lock breaks the old one in two pieces, so we
  389.              * have to allocate one more lock (in this case, even
  390.              * F_UNLCK may fail!).
  391.              */
  392.             if (! (left = alloc_lock(before, right, fd))) {
  393.                 if (! added)
  394.                     free_lock(before);
  395.                 return -ENOLCK;
  396.             }
  397.         }
  398.         right->fl_start = caller->fl_end + 1;
  399.     }
  400.     if (left)
  401.         left->fl_end = caller->fl_start - 1;
  402.     return 0;
  403. }
  404.  
  405. /*
  406.  * File_lock() inserts a lock at the position pos of the linked list.
  407.  */
  408.  
  409. static struct file_lock *alloc_lock(struct file_lock **pos,
  410.                     struct file_lock *fl,
  411.                                     unsigned int     fd)
  412. {
  413.     struct file_lock *tmp;
  414.  
  415.     tmp = file_lock_free_list;
  416.     if (tmp == NULL)
  417.         return NULL;            /* no available entry */
  418.     if (tmp->fl_owner != NULL)
  419.         panic("alloc_lock: broken free list\n");
  420.  
  421.     /* remove from free list */
  422.     file_lock_free_list = tmp->fl_next;
  423.  
  424.     *tmp = *fl;
  425.  
  426.     tmp->fl_next = *pos;    /* insert into file's list */
  427.     *pos = tmp;
  428.  
  429.     tmp->fl_owner = current;    /* FIXME: needed? */
  430.     tmp->fl_fd = fd;        /* FIXME: needed? */
  431.     tmp->fl_wait = NULL;
  432.     return tmp;
  433. }
  434.  
  435. /*
  436.  * Add a lock to the free list ...
  437.  */
  438.  
  439. static void free_lock(struct file_lock **fl_p)
  440. {
  441.     struct file_lock *fl;
  442.  
  443.     fl = *fl_p;
  444.     if (fl->fl_owner == NULL)    /* sanity check */
  445.         panic("free_lock: broken lock list\n");
  446.  
  447.     *fl_p = (*fl_p)->fl_next;
  448.  
  449.     fl->fl_next = file_lock_free_list;    /* add to free list */
  450.     file_lock_free_list = fl;
  451.     fl->fl_owner = NULL;            /* for sanity checks */
  452.  
  453.     wake_up(&fl->fl_wait);
  454. }
  455.