root/fs/locks.c

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

DEFINITIONS

This source file includes following definitions.
  1. locks_free_lock
  2. locks_insert_block
  3. locks_delete_block
  4. sys_flock
  5. fcntl_getlk
  6. fcntl_setlk
  7. locks_remove_locks
  8. posix_make_lock
  9. flock_make_lock
  10. posix_locks_conflict
  11. flock_locks_conflict
  12. locks_conflict
  13. locks_overlap
  14. posix_locks_deadlock
  15. flock_lock_file
  16. posix_lock_file
  17. locks_alloc_lock
  18. locks_insert_lock
  19. locks_delete_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 (dje@spiff.uucp), August 07, 1992
   6  *
   7  *  Deadlock detection added.
   8  *  FIXME: one thing isn't handled yet:
   9  *      - mandatory locks (requires lots of changes elsewhere)
  10  *  Kelly Carmichael (kelly@[142.24.8.65]), September 17, 1994.
  11  *
  12  *  Miscellaneous edits, and a total rewrite of posix_lock_file() code.
  13  *  Kai Petzke (wpp@marie.physik.tu-berlin.de), 1994
  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.
  17  *  Chad Page (pageone@netcom.com), November 27, 1994
  18  * 
  19  *  Removed dependency on file descriptors. dup()'ed file descriptors now
  20  *  get the same locks as the original file descriptors, and a close() on
  21  *  any file descriptor removes ALL the locks on the file for the current
  22  *  process. Since locks still depend on the process id, locks are inherited
  23  *  after an exec() but not after a fork(). This agrees with POSIX, and both
  24  *  BSD and SVR4 practice.
  25  *  Andy Walker (andy@keo.kvaerner.no), February 14, 1995
  26  *
  27  *  Scrapped free list which is redundant now that we allocate locks
  28  *  dynamically with kmalloc()/kfree().
  29  *  Andy Walker (andy@keo.kvaerner.no), February 21, 1995
  30  *
  31  *  Implemented two lock personalities - F_FLOCK and F_POSIX.
  32  *
  33  *  F_POSIX locks are created with calls to fcntl() and lockf() through the
  34  *  fcntl() system call. They have the semantics described above.
  35  *
  36  *  F_FLOCK locks are created with calls to flock(), through the flock()
  37  *  system call, which is new. Old C libraries implement flock() via fcntl()
  38  *  and will continue to use the old, broken implementation.
  39  *
  40  *  F_FLOCK locks follow the 4.4 BSD flock() semantics. They are associated
  41  *  with a file pointer (filp). As a result they can be shared by a parent
  42  *  process and its children after a fork(). They are removed when the last
  43  *  file descriptor referring to the file pointer is closed (unless explicitly
  44  *  unlocked). 
  45  *
  46  *  F_FLOCK locks never deadlock, an existing lock is always removed before
  47  *  upgrading from shared to exclusive (or vice versa). When this happens
  48  *  any processes blocked by the current lock are woken up and allowed to
  49  *  run before the new lock is applied.
  50  *
  51  *  NOTE:
  52  *  I do not intend to implement mandatory locks unless demand is *HUGE*.
  53  *  They are not in BSD, and POSIX.1 does not require them. I have never
  54  *  seen any public code that relied on them. As Kelly Carmichael suggests
  55  *  above, mandatory locks requires lots of changes elsewhere and I am
  56  *  reluctant to start something so drastic for so little gain.
  57  *  Andy Walker (andy@keo.kvaerner.no), June 09, 1995
  58  * 
  59  *  Removed some race conditions in flock_lock_file(), marked other possible
  60  *  races. Just grep for FIXME to see them. 
  61  *  Dmitry Gorodchanin (begemot@bgm.rosprint.net), Feb 09, 1996.
  62  */
  63 
  64 #include <asm/segment.h>
  65 
  66 #include <linux/malloc.h>
  67 #include <linux/sched.h>
  68 #include <linux/kernel.h>
  69 #include <linux/errno.h>
  70 #include <linux/stat.h>
  71 #include <linux/fcntl.h>
  72 
  73 
  74 #define OFFSET_MAX      ((off_t)0x7fffffff)     /* FIXME: move elsewhere? */
  75 
  76 static int flock_make_lock(struct file *filp, struct file_lock *fl,
  77                                unsigned int cmd);
  78 static int posix_make_lock(struct file *filp, struct file_lock *fl,
  79                                struct flock *l);
  80 static int flock_locks_conflict(struct file_lock *caller_fl,
  81                                 struct file_lock *sys_fl);
  82 static int posix_locks_conflict(struct file_lock *caller_fl,
  83                                 struct file_lock *sys_fl);
  84 static int locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl);
  85 static int flock_lock_file(struct file *filp, struct file_lock *caller,
  86                            unsigned int wait);
  87 static int posix_lock_file(struct file *filp, struct file_lock *caller,
  88                            unsigned int wait);
  89 static int posix_locks_deadlock(struct task_struct *my_task,
  90                                 struct task_struct *blocked_task);
  91 static int locks_overlap(struct file_lock *fl1, struct file_lock *fl2);
  92 
  93 static struct file_lock *locks_alloc_lock(struct file_lock *fl);
  94 static void locks_insert_lock(struct file_lock **pos, struct file_lock *fl);
  95 static void locks_delete_lock(struct file_lock **fl, unsigned int wait);
  96 
  97 static struct file_lock *file_lock_table = NULL;
  98 
  99 /* Free lock not inserted in any queue */
 100 static inline void locks_free_lock(struct file_lock **fl)
     /* [previous][next][first][last][top][bottom][index][help] */
 101 {
 102         kfree(*fl);
 103         *fl = NULL;                    /* Just in case */
 104 }
 105 
 106 /* Add lock fl to the blocked list pointed to by block.
 107  * We search to the end of the existing list and insert the the new
 108  * struct. This ensures processes will be woken up in the order they
 109  * blocked.
 110  * NOTE: nowhere does the documentation insist that processes be woken
 111  * up in this order, but it seems like the reasonable thing to do.
 112  * If the blocked list gets long then this search could get expensive,
 113  * in which case we could consider waking the processes up in reverse
 114  * order, or making the blocked list a doubly linked circular list.
 115  * 
 116  * This functions are called only from one place (flock_lock_file)
 117  * so they are inlined now. -- Dmitry Gorodchanin 02/09/96.
 118  */
 119 
 120 static inline void locks_insert_block(struct file_lock **block, 
     /* [previous][next][first][last][top][bottom][index][help] */
 121                                       struct file_lock *fl)
 122 {
 123         struct file_lock *bfl;
 124 
 125         while ((bfl = *block) != NULL) {
 126                 block = &bfl->fl_block;
 127         }
 128 
 129         *block = fl;
 130         fl->fl_block = NULL;
 131         
 132         return;
 133 }
 134 
 135 static inline void locks_delete_block(struct file_lock **block,
     /* [previous][next][first][last][top][bottom][index][help] */
 136                                       struct file_lock *fl)
 137 {
 138         struct file_lock *bfl;
 139         
 140         while ((bfl = *block) != NULL) {
 141                 if (bfl == fl) {
 142                         *block = fl->fl_block;
 143                         fl->fl_block = NULL;
 144                         return;
 145                 }
 146                 block = &bfl->fl_block;
 147         }
 148 }
 149 
 150 /* flock() system call entry point. Apply a FLOCK style locks to
 151  * an open file descriptor.
 152  */
 153 asmlinkage int sys_flock(unsigned int fd, unsigned int cmd)
     /* [previous][next][first][last][top][bottom][index][help] */
 154 {
 155         struct file_lock file_lock;
 156         struct file *filp;
 157 
 158         if ((fd >= NR_OPEN) || !(filp = current->files->fd[fd]))
 159                 return (-EBADF);
 160 
 161         if (!flock_make_lock(filp, &file_lock, cmd))
 162                 return (-EINVAL);
 163         
 164         if ((file_lock.fl_type != F_UNLCK) && !(filp->f_mode & 3))
 165                 return (-EBADF);
 166         
 167         return (flock_lock_file(filp, &file_lock, cmd & LOCK_UN ? 0 : cmd & LOCK_NB ? 0 : 1));
 168 }
 169 
 170 /* Report the first existing locks that would conflict with l. This implements
 171  * the F_GETLK command of fcntl().
 172  */
 173 int fcntl_getlk(unsigned int fd, struct flock *l)
     /* [previous][next][first][last][top][bottom][index][help] */
 174 {
 175         int error;
 176         struct flock flock;
 177         struct file *filp;
 178         struct file_lock *fl,file_lock;
 179 
 180         if ((fd >= NR_OPEN) || !(filp = current->files->fd[fd]))
 181                 return (-EBADF);
 182         error = verify_area(VERIFY_WRITE, l, sizeof(*l));
 183         if (error)
 184                 return (error);
 185 
 186         memcpy_fromfs(&flock, l, sizeof(flock));
 187         if ((flock.l_type == F_UNLCK) || (flock.l_type == F_EXLCK) ||
 188             (flock.l_type == F_SHLCK))
 189                 return (-EINVAL);
 190 
 191         if (!posix_make_lock(filp, &file_lock, &flock))
 192                 return (-EINVAL);
 193 
 194         for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
 195                 if (posix_locks_conflict(&file_lock, fl)) {
 196                         flock.l_pid = fl->fl_owner->pid;
 197                         flock.l_start = fl->fl_start;
 198                         flock.l_len = fl->fl_end == OFFSET_MAX ? 0 :
 199                                 fl->fl_end - fl->fl_start + 1;
 200                         flock.l_whence = 0;
 201                         flock.l_type = fl->fl_type;
 202                         memcpy_tofs(l, &flock, sizeof(flock));
 203                         return (0);
 204                 }
 205         }
 206 
 207         flock.l_type = F_UNLCK;                 /* no conflict found */
 208         memcpy_tofs(l, &flock, sizeof(flock));
 209         return (0);
 210 }
 211 
 212 /* Apply the lock described by l to an open file descriptor. This implements
 213  * both the F_SETLK and F_SETLKW commands of fcntl(). It also emulates flock()
 214  * in a pretty broken way for older C libraries.
 215  */
 216 int fcntl_setlk(unsigned int fd, unsigned int cmd, struct flock *l)
     /* [previous][next][first][last][top][bottom][index][help] */
 217 {
 218         int error;
 219         struct file *filp;
 220         struct file_lock file_lock;
 221         struct flock flock;
 222 
 223         /*
 224          * Get arguments and validate them ...
 225          */
 226 
 227         if ((fd >= NR_OPEN) || !(filp = current->files->fd[fd]))
 228                 return (-EBADF);
 229         
 230         error = verify_area(VERIFY_READ, l, sizeof(*l));
 231         if (error)
 232                 return (error);
 233         
 234         memcpy_fromfs(&flock, l, sizeof(flock));
 235         if (!posix_make_lock(filp, &file_lock, &flock))
 236                 return (-EINVAL);
 237         
 238         switch (flock.l_type) {
 239         case F_RDLCK :
 240                 if (!(filp->f_mode & 1))
 241                         return -EBADF;
 242                 break;
 243         case F_WRLCK :
 244                 if (!(filp->f_mode & 2))
 245                         return -EBADF;
 246                 break;
 247         case F_SHLCK :
 248         case F_EXLCK :
 249                 if (!(filp->f_mode & 3))
 250                         return -EBADF;
 251                 break;
 252         case F_UNLCK :
 253                 break;
 254         }
 255         
 256         return (posix_lock_file(filp, &file_lock, cmd == F_SETLKW));
 257 }
 258 
 259 /* This function is called when the file is closed.
 260  */
 261 void locks_remove_locks(struct task_struct *task, struct file *filp)
     /* [previous][next][first][last][top][bottom][index][help] */
 262 {
 263         struct file_lock *fl;
 264         struct file_lock **before;
 265 
 266         /* For POSIX locks we free all locks on this file for the given task.
 267          * For FLOCK we only free locks on this *open* file if it is the last
 268          * close on that file.
 269          */
 270         before = &filp->f_inode->i_flock;
 271         while ((fl = *before) != NULL) {
 272                 if (((fl->fl_flags == F_POSIX) && (fl->fl_owner == task)) ||
 273                     ((fl->fl_flags == F_FLOCK) && (fl->fl_file == filp) &&
 274                      (filp->f_count == 1)))
 275                         locks_delete_lock(before, 0);
 276                 else
 277                         before = &fl->fl_next;
 278         }
 279 
 280         return;
 281 }
 282 
 283 /* Verify a "struct flock" and copy it to a "struct file_lock" as a POSIX
 284  * style lock.
 285  */
 286 static int posix_make_lock(struct file *filp, struct file_lock *fl,
     /* [previous][next][first][last][top][bottom][index][help] */
 287                            struct flock *l)
 288 {
 289         off_t start;
 290 
 291         if (!filp->f_inode)     /* just in case */
 292                 return (0);
 293 
 294         switch (l->l_type) {
 295         case F_RDLCK :
 296         case F_WRLCK :
 297         case F_UNLCK :
 298                 fl->fl_type = l->l_type;
 299                 break;
 300         case F_SHLCK :
 301                 fl->fl_type = F_RDLCK;
 302                 break;
 303         case F_EXLCK :
 304                 fl->fl_type = F_WRLCK;
 305                 break;
 306         default :
 307                 return (0);
 308         }
 309 
 310         switch (l->l_whence) {
 311         case 0 : /*SEEK_SET*/
 312                 start = 0;
 313                 break;
 314         case 1 : /*SEEK_CUR*/
 315                 start = filp->f_pos;
 316                 break;
 317         case 2 : /*SEEK_END*/
 318                 start = filp->f_inode->i_size;
 319                 break;
 320         default :
 321                 return (0);
 322         }
 323 
 324         if (((start += l->l_start) < 0) || (l->l_len < 0))
 325                 return (0);
 326         fl->fl_start = start;   /* we record the absolute position */
 327         if ((l->l_len == 0) || ((fl->fl_end = start + l->l_len - 1) < 0))
 328                 fl->fl_end = OFFSET_MAX;
 329         
 330         fl->fl_flags = F_POSIX;
 331         fl->fl_file = filp;
 332         fl->fl_owner = current;
 333         fl->fl_wait = NULL;             /* just for cleanliness */
 334         
 335         return (1);
 336 }
 337 
 338 /* Verify a call to flock() and fill in a file_lock structure with an appropriate
 339  * FLOCK lock.
 340  */
 341 static int flock_make_lock(struct file *filp, struct file_lock *fl,
     /* [previous][next][first][last][top][bottom][index][help] */
 342                            unsigned int cmd)
 343 {
 344         if (!filp->f_inode)     /* just in case */
 345                 return (0);
 346 
 347         switch (cmd & ~LOCK_NB) {
 348         case LOCK_SH :
 349                 fl->fl_type = F_RDLCK;
 350                 break;
 351         case LOCK_EX :
 352                 fl->fl_type = F_WRLCK;
 353                 break;
 354         case LOCK_UN :
 355                 fl->fl_type = F_UNLCK;
 356                 break;
 357         default :
 358                 return (0);
 359         }
 360 
 361         fl->fl_flags = F_FLOCK;
 362         fl->fl_start = 0;
 363         fl->fl_end = OFFSET_MAX;
 364         fl->fl_file = filp;
 365         fl->fl_owner = current;
 366         fl->fl_wait = NULL;             /* just for cleanliness */
 367         
 368         return (1);
 369 }
 370 
 371 /* Determine if lock sys_fl blocks lock caller_fl. POSIX specific checking
 372  * before calling the locks_conflict().
 373  */
 374 static int posix_locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
     /* [previous][next][first][last][top][bottom][index][help] */
 375 {
 376         /* POSIX locks owned by the same process do not conflict with
 377          * each other.
 378          */
 379         if ((sys_fl->fl_flags == F_POSIX) &&
 380             (caller_fl->fl_owner == sys_fl->fl_owner))
 381                 return (0);
 382 
 383         return (locks_conflict(caller_fl, sys_fl));
 384 }
 385 
 386 /* Determine if lock sys_fl blocks lock caller_fl. FLOCK specific checking
 387  * before calling the locks_conflict().
 388  */
 389 static int flock_locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
     /* [previous][next][first][last][top][bottom][index][help] */
 390 {
 391         /* FLOCK locks referring to the same filp do not conflict with
 392          * each other.
 393          */
 394         if ((sys_fl->fl_flags == F_FLOCK) &&
 395             (caller_fl->fl_file == sys_fl->fl_file))
 396                 return (0);
 397 
 398         return (locks_conflict(caller_fl, sys_fl));
 399 }
 400 
 401 /* Determine if lock sys_fl blocks lock caller_fl. Common functionality
 402  * checks for overlapping locks and shared/exclusive status.
 403  */
 404 static int locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
     /* [previous][next][first][last][top][bottom][index][help] */
 405 {
 406         if (!locks_overlap(caller_fl, sys_fl))
 407                 return (0);
 408 
 409         switch (caller_fl->fl_type) {
 410         case F_RDLCK :
 411                 return (sys_fl->fl_type == F_WRLCK);
 412                 
 413         case F_WRLCK :
 414                 return (1);
 415 
 416         default:
 417                 printk("locks_conflict(): impossible lock type - %d\n",
 418                        caller_fl->fl_type);
 419                 break;
 420         }
 421         return (0);     /* This should never happen */
 422 }
 423 
 424 /* Check if two locks overlap each other.
 425  */
 426 static int locks_overlap(struct file_lock *fl1, struct file_lock *fl2)
     /* [previous][next][first][last][top][bottom][index][help] */
 427 {
 428         return ((fl1->fl_end >= fl2->fl_start) &&
 429                 (fl2->fl_end >= fl1->fl_start));
 430 }
 431 
 432 /* This function tests for deadlock condition before putting a process to sleep.
 433  * The detection scheme is recursive... we may need a test to make it exit if the
 434  * function gets stuck due to bad lock data. 4.4 BSD uses a maximum depth of 50
 435  * for this.
 436  * 
 437  * FIXME: 
 438  * IMHO this function is dangerous, deep recursion may result in kernel stack
 439  * corruption. Perhaps we need to limit depth here. 
 440  *              Dmitry Gorodchanin 09/02/96
 441  */
 442 static int posix_locks_deadlock(struct task_struct *my_task,
     /* [previous][next][first][last][top][bottom][index][help] */
 443                                 struct task_struct *blocked_task)
 444 {
 445         struct wait_queue *dlock_wait;
 446         struct file_lock *fl;
 447 
 448         for (fl = file_lock_table; fl != NULL; fl = fl->fl_nextlink) {
 449                 if (fl->fl_owner == NULL)
 450                         continue;       /* Should never happen! */
 451                 if (fl->fl_owner != my_task)
 452                         continue;
 453                 if (fl->fl_wait == NULL)
 454                         continue;       /* no queues */
 455                 dlock_wait = fl->fl_wait;
 456                 do {
 457                         if (dlock_wait->task != NULL) {
 458                                 if (dlock_wait->task == blocked_task)
 459                                         return (-EDEADLOCK);
 460                                 if (posix_locks_deadlock(dlock_wait->task, blocked_task))
 461                                         return (-EDEADLOCK);
 462                         }
 463                         dlock_wait = dlock_wait->next;
 464                 } while (dlock_wait != fl->fl_wait);
 465         }
 466         return (0);
 467 }
 468 
 469 /* Try to create a FLOCK lock on filp. We rely on FLOCK locks being sorting
 470  * first in an inode's lock list, and always insert new locks at the head
 471  * of the list.
 472  */
 473 static int flock_lock_file(struct file *filp, struct file_lock *caller,
     /* [previous][next][first][last][top][bottom][index][help] */
 474                            unsigned int wait)
 475 {
 476         struct file_lock *fl;
 477         struct file_lock *new_fl;
 478         struct file_lock **before;
 479         int change = 0;
 480 
 481         /* This a compact little algorithm based on us always placing FLOCK
 482          * locks at the front of the list.
 483          */
 484         before = &filp->f_inode->i_flock;
 485         while ((fl = *before) && (fl->fl_flags == F_FLOCK)) {
 486                 if (caller->fl_file == fl->fl_file) {
 487                         if (caller->fl_type == fl->fl_type)
 488                                 return (0);
 489                         change = 1;
 490                         break;
 491                 }
 492                 before = &fl->fl_next;
 493         }
 494         /* change means that we are changing the type of an existing lock, or
 495          * or else unlocking it.
 496          */
 497         if (change)
 498                 locks_delete_lock(before, caller->fl_type != F_UNLCK);
 499         if (caller->fl_type == F_UNLCK)
 500                 return (0);
 501         if ((new_fl = locks_alloc_lock(caller)) == NULL)
 502                 return (-ENOLCK);
 503  repeat:
 504         for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
 505                 if (!flock_locks_conflict(new_fl, fl))
 506                         continue;
 507                 
 508                 if (wait) {
 509                         if (current->signal & ~current->blocked) {
 510                                 /* Note: new_fl is not in any queue at this
 511                                  * point. So we must use locks_free_lock()
 512                                  * instead of locks_delete_lock()
 513                                  *      Dmitry Gorodchanin 09/02/96.
 514                                  */
 515                                 locks_free_lock(&new_fl);
 516                                 return (-ERESTARTSYS);
 517                         }
 518                         locks_insert_block(&fl->fl_block, new_fl);
 519                         interruptible_sleep_on(&new_fl->fl_wait);
 520                         wake_up(&new_fl->fl_wait);
 521                         if (current->signal & ~current->blocked) {
 522                                 /* If we are here, than we were awaken
 523                                  * by signal, so new_fl is still in 
 524                                  * block queue of fl. We need remove 
 525                                  * new_fl and then free it. 
 526                                  *      Dmitry Gorodchanin 09/02/96.
 527                                  */
 528 
 529                                 locks_delete_block(&fl->fl_block, new_fl);
 530                                 locks_free_lock(&new_fl);
 531                                 return (-ERESTARTSYS);
 532                         }
 533                         goto repeat;
 534                 }
 535                 
 536                 locks_free_lock(&new_fl);
 537                 return (-EAGAIN);
 538         }
 539         locks_insert_lock(&filp->f_inode->i_flock, new_fl);
 540         return (0);
 541 }
 542 
 543 /* Add a POSIX style lock to a file.
 544  * We merge adjacent locks whenever possible. POSIX locks come after FLOCK
 545  * locks in the list and are sorted by owner task, then by starting address
 546  *
 547  * Kai Petzke writes:
 548  * To make freeing a lock much faster, we keep a pointer to the lock before the
 549  * actual one. But the real gain of the new coding was, that lock_it() and
 550  * unlock_it() became one function.
 551  *
 552  * To all purists: Yes, I use a few goto's. Just pass on to the next function.
 553  */
 554 
 555 static int posix_lock_file(struct file *filp, struct file_lock *caller,
     /* [previous][next][first][last][top][bottom][index][help] */
 556                            unsigned int wait)
 557 {
 558         struct file_lock *fl;
 559         struct file_lock *new_fl;
 560         struct file_lock *left = NULL;
 561         struct file_lock *right = NULL;
 562         struct file_lock **before;
 563         int added = 0;
 564 
 565         if (caller->fl_type != F_UNLCK) {
 566 repeat:
 567                 for (fl = filp->f_inode->i_flock; fl != NULL; fl = fl->fl_next) {
 568                         if (!posix_locks_conflict(caller, fl))
 569                                 continue;
 570                         if (wait) {
 571                                 if (current->signal & ~current->blocked)
 572                                         return (-ERESTARTSYS);
 573                                 if (fl->fl_flags == F_POSIX)
 574                                         if (posix_locks_deadlock(caller->fl_owner, fl->fl_owner))
 575                                                 return (-EDEADLOCK);
 576                                 interruptible_sleep_on(&fl->fl_wait);
 577                                 if (current->signal & ~current->blocked)
 578                                         return (-ERESTARTSYS);
 579                                 goto repeat;
 580                         }
 581                         return (-EAGAIN);
 582                 }
 583         }
 584         /*
 585          * Find the first old lock with the same owner as the new lock.
 586          */
 587         
 588         before = &filp->f_inode->i_flock;
 589 
 590         /* First skip FLOCK locks and locks owned by other processes.
 591          */
 592         while ((fl = *before) && ((fl->fl_flags == F_FLOCK) ||
 593                                   (caller->fl_owner != fl->fl_owner))) {
 594                 before = &fl->fl_next;
 595         }
 596         
 597 
 598         /* Process locks with this owner.
 599          */
 600         while ((fl = *before) && (caller->fl_owner == fl->fl_owner)) {
 601                 /* Detect adjacent or overlapping regions (if same lock type)
 602                  */
 603                 if (caller->fl_type == fl->fl_type) {
 604                         if (fl->fl_end < caller->fl_start - 1)
 605                                 goto next_lock;
 606                         /* If the next lock in the list has entirely bigger
 607                          * addresses than the new one, insert the lock here.
 608                          */
 609                         if (fl->fl_start > caller->fl_end + 1)
 610                                 break;
 611 
 612                         /* If we come here, the new and old lock are of the
 613                          * same type and adjacent or overlapping. Make one
 614                          * lock yielding from the lower start address of both
 615                          * locks to the higher end address.
 616                          */
 617                         if (fl->fl_start > caller->fl_start)
 618                                 fl->fl_start = caller->fl_start;
 619                         else
 620                                 caller->fl_start = fl->fl_start;
 621                         if (fl->fl_end < caller->fl_end)
 622                                 fl->fl_end = caller->fl_end;
 623                         else
 624                                 caller->fl_end = fl->fl_end;
 625                         if (added) {
 626                                 locks_delete_lock(before, 0);
 627                                 continue;
 628                         }
 629                         caller = fl;
 630                         added = 1;
 631                         goto next_lock;
 632                 }
 633                 /* Processing for different lock types is a bit more complex.
 634                  */
 635                 if (fl->fl_end < caller->fl_start)
 636                         goto next_lock;
 637                 if (fl->fl_start > caller->fl_end)
 638                         break;
 639                 if (caller->fl_type == F_UNLCK)
 640                         added = 1;
 641                 if (fl->fl_start < caller->fl_start)
 642                         left = fl;
 643                 /* If the next lock in the list has a higher end address than
 644                  * the new one, insert the new one here.
 645                  */
 646                 if (fl->fl_end > caller->fl_end) {
 647                         right = fl;
 648                         break;
 649                 }
 650                 if (fl->fl_start >= caller->fl_start) {
 651                         /* The new lock completely replaces an old one (This may
 652                          * happen several times).
 653                          */
 654                         if (added) {
 655                                 locks_delete_lock(before, 0);
 656                                 continue;
 657                         }
 658                         /* Replace the old lock with the new one. Wake up
 659                          * anybody waiting for the old one, as the change in
 660                          * lock type might satisfy his needs.
 661                          */
 662                         wake_up(&fl->fl_wait);
 663                         fl->fl_start = caller->fl_start;
 664                         fl->fl_end = caller->fl_end;
 665                         fl->fl_type = caller->fl_type;
 666                         caller = fl;
 667                         added = 1;
 668                 }
 669                 /* Go on to next lock.
 670                  */
 671         next_lock:
 672                 before = &(*before)->fl_next;
 673         }
 674 
 675         /* FIXME:
 676          * Note: We may sleep in locks_alloc_lock(), so
 677          * the 'before' pointer may be not valid any more.
 678          * This can cause random kernel memory corruption.
 679          * It seems the right way is to alloc two locks
 680          * at the begining of this func, and then free them
 681          * if they were not needed.
 682          * Another way is to change GFP_KERNEL to GFP_ATOMIC
 683          * in locks_alloc_lock() for this case.
 684          * 
 685          * Dmitry Gorodchanin 09/02/96.
 686          */ 
 687         if (!added) {
 688                 if (caller->fl_type == F_UNLCK)
 689                         return (0);
 690                 if ((new_fl = locks_alloc_lock(caller)) == NULL)
 691                         return (-ENOLCK);
 692                 locks_insert_lock(before, new_fl);
 693 
 694         }
 695         if (right) {
 696                 if (left == right) {
 697                         /* The new lock breaks the old one in two pieces, so we
 698                          * have to allocate one more lock (in this case, even
 699                          * F_UNLCK may fail!).
 700                          */
 701                         if ((left = locks_alloc_lock(right)) == NULL) {
 702                                 if (!added)
 703                                         locks_delete_lock(before, 0);
 704                                 return (-ENOLCK);
 705                         }
 706                         locks_insert_lock(before, left);
 707                 }
 708                 right->fl_start = caller->fl_end + 1;
 709         }
 710         if (left)
 711                 left->fl_end = caller->fl_start - 1;
 712         return (0);
 713 }
 714 
 715 /* Allocate memory for a new lock and initialize its fields from
 716  * fl. The lock is not inserted into any lists until locks_insert_lock()
 717  * or locks_insert_block() are called.
 718  */
 719 
 720 static struct file_lock *locks_alloc_lock(struct file_lock *fl)
     /* [previous][next][first][last][top][bottom][index][help] */
 721 {
 722         struct file_lock *tmp;
 723 
 724         /* Okay, let's make a new file_lock structure... */
 725         if ((tmp = (struct file_lock *)kmalloc(sizeof(struct file_lock),
 726                                                GFP_KERNEL)) == NULL)
 727                 return (tmp);
 728 
 729         tmp->fl_nextlink = NULL;
 730         tmp->fl_prevlink = NULL;
 731         tmp->fl_next = NULL;
 732         tmp->fl_block = NULL;
 733         tmp->fl_flags = fl->fl_flags;
 734         tmp->fl_owner = fl->fl_owner;
 735         tmp->fl_file = fl->fl_file;
 736         tmp->fl_wait = NULL;
 737         tmp->fl_type = fl->fl_type;
 738         tmp->fl_start = fl->fl_start;
 739         tmp->fl_end = fl->fl_end;
 740 
 741         return (tmp);
 742 }
 743 
 744 /* Insert file lock fl into an inode's lock list at the position indicated
 745  * by pos. At the same time add the lock to the global file lock list.
 746  */
 747 
 748 static void locks_insert_lock(struct file_lock **pos, struct file_lock *fl)
     /* [previous][next][first][last][top][bottom][index][help] */
 749 {
 750         fl->fl_nextlink = file_lock_table;
 751         fl->fl_prevlink = NULL;
 752         if (file_lock_table != NULL)
 753                 file_lock_table->fl_prevlink = fl;
 754         file_lock_table = fl;
 755         fl->fl_next = *pos;     /* insert into file's list */
 756         *pos = fl;
 757 
 758         return;
 759 }
 760 
 761 /* Delete a lock and free it.
 762  * First remove our lock from the lock lists. Then remove all the blocked locks
 763  * from our blocked list, waking up the processes that own them. If told to wait,
 764  * then sleep on each of these lock's wait queues. Each blocked process will wake
 765  * up and immediately wake up its own wait queue allowing us to be scheduled again.
 766  * Lastly, wake up our own wait queue before freeing the file_lock structure.
 767  */
 768 
 769 static void locks_delete_lock(struct file_lock **fl_p, unsigned int wait)
     /* [previous][next][first][last][top][bottom][index][help] */
 770 {
 771         struct file_lock *fl;
 772         struct file_lock *bfl;
 773         
 774         fl = *fl_p;
 775         *fl_p = (*fl_p)->fl_next;
 776 
 777         if (fl->fl_nextlink != NULL)
 778                 fl->fl_nextlink->fl_prevlink = fl->fl_prevlink;
 779 
 780         if (fl->fl_prevlink != NULL)
 781                 fl->fl_prevlink->fl_nextlink = fl->fl_nextlink;
 782         else {
 783                 file_lock_table = fl->fl_nextlink;
 784         }
 785         
 786         while ((bfl = fl->fl_block) != NULL) {
 787                 fl->fl_block = bfl->fl_block;
 788                 bfl->fl_block = NULL;
 789                 wake_up(&bfl->fl_wait);
 790                 if (wait)
 791                         sleep_on(&bfl->fl_wait);
 792         }
 793 
 794         wake_up(&fl->fl_wait);
 795         kfree(fl);
 796 
 797         return;
 798 }

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