fs/locks.c

   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@lysaker.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@lysaker.kvaerner.no), February 21, 1995
  30  *
  31  *  Implemented two lock personalities - FL_FLOCK and FL_POSIX.
  32  *
  33  *  FL_POSIX locks are created with calls to fcntl() and lockf() through the
  34  *  fcntl() system call. They have the semantics described above.
  35  *
  36  *  FL_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  *  FL_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  *  FL_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  *  Andy Walker (andy@lysaker.kvaerner.no), June 09, 1995
  51  *
  52  *  Removed some race conditions in flock_lock_file(), marked other possible
  53  *  races. Just grep for FIXME to see them.
  54  *  Dmitry Gorodchanin (pgmdsg@ibi.com), February 09, 1996.
  55  *
  56  *  Addressed Dmitry's concerns. Deadlock checking no longer recursive.
  57  *  Lock allocation changed to GFP_ATOMIC as we can't afford to sleep
  58  *  once we've checked for blocking and deadlocking.
  59  *  Andy Walker (andy@lysaker.kvaerner.no), April 03, 1996.
  60  *
  61  *  Initial implementation of mandatory locks. SunOS turned out to be
  62  *  a rotten model, so I implemented the "obvious" semantics.
  63  *  See 'linux/Documentation/mandatory.txt' for details.
  64  *  Andy Walker (andy@lysaker.kvaerner.no), April 06, 1996.
  65  *
  66  *  Don't allow mandatory locks on mmap()'ed files. Added simple functions to
  67  *  check if a file has mandatory locks, used by mmap(), open() and creat() to
  68  *  see if system call should be rejected. Ref. HP-UX/SunOS/Solaris Reference
  69  *  Manual, Section 2.
  70  *  Andy Walker (andy@lysaker.kvaerner.no), April 09, 1996.
  71  *
  72  *  Tidied up block list handling. Added '/proc/locks' interface.
  73  *  Andy Walker (andy@lysaker.kvaerner.no), April 24, 1996.
  74  *
  75  *  Fixed deadlock condition for pathological code that mixes calls to
  76  *  flock() and fcntl().
  77  *  Andy Walker (andy@lysaker.kvaerner.no), April 29, 1996.
  78  *
  79  *  Allow only one type of locking scheme (FL_POSIX or FL_FLOCK) to be in use
  80  *  for a given file at a time. Changed the CONFIG_LOCK_MANDATORY scheme to
  81  *  guarantee sensible behaviour in the case where file system modules might
  82  *  be compiled with different options than the kernel itself.
  83  *  Andy Walker (andy@lysaker.kvaerner.no), May 15, 1996.
  84  *
  85  *  Added a couple of missing wake_up() calls. Thanks to Thomas Meckel
  86  *  (Thomas.Meckel@mni.fh-giessen.de) for spotting this.
  87  *  Andy Walker (andy@lysaker.kvaerner.no), May 15, 1996.
  88  *
  89  *  Changed FL_POSIX locks to use the block list in the same way as FL_FLOCK
  90  *  locks. Changed process synchronisation to avoid dereferencing locks that
  91  *  have already been freed.
  92  *  Andy Walker (andy@lysaker.kvaerner.no), Sep 21, 1996.
  93  *
  94  *  Made the block list a circular list to minimise searching in the list.
  95  *  Andy Walker (andy@lysaker.kvaerner.no), Sep 25, 1996.
  96  *
  97  *  Made mandatory locking a mount option. Default is not to allow mandatory
  98  *  locking.
  99  *  Andy Walker (andy@lysaker.kvaerner.no), Oct 04, 1996.
 100  *
 101  *  Some adaptations for NFS support.
 102  *  Olaf Kirch (okir@monad.swb.de), Dec 1996,
 103  *
 104  *  Fixed /proc/locks interface so that we can't overrun the buffer we are handed.
 105  *  Andy Walker (andy@lysaker.kvaerner.no), May 12, 1997.
 106  */
 107
 108 #include <linux/malloc.h>
 109 #include <linux/file.h>
 110 #include <linux/smp_lock.h>
 111
 112 #include <asm/uaccess.h>
 113
 114 #define OFFSET_MAX      ((off_t)LONG_MAX)       /* FIXME: move elsewhere? */
 115
 116 static int flock_make_lock(struct file *filp, struct file_lock *fl,
 117                                unsigned int cmd);
 118 static int posix_make_lock(struct file *filp, struct file_lock *fl,
 119                                struct flock *l);
 120 static int flock_locks_conflict(struct file_lock *caller_fl,
 121                                 struct file_lock *sys_fl);
 122 static int posix_locks_conflict(struct file_lock *caller_fl,
 123                                 struct file_lock *sys_fl);
 124 static int locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl);
 125 static int flock_lock_file(struct file *filp, struct file_lock *caller,
 126                            unsigned int wait);
 127 static int posix_locks_deadlock(struct file_lock *caller,
 128                                 struct file_lock *blocker);
 129
 130 static struct file_lock *locks_empty_lock(void);
 131 static struct file_lock *locks_init_lock(struct file_lock *,
 132                                          struct file_lock *);
 133 static void locks_insert_lock(struct file_lock **pos, struct file_lock *fl);
 134 static void locks_delete_lock(struct file_lock **thisfl_p, unsigned int wait);
 135 static char *lock_get_status(struct file_lock *fl, int id, char *pfx);
 136
 137 static void locks_insert_block(struct file_lock *blocker, struct file_lock *waiter);
 138 static void locks_delete_block(struct file_lock *blocker, struct file_lock *waiter);
 139 static void locks_wake_up_blocks(struct file_lock *blocker, unsigned int wait);
 140
 141 struct file_lock *file_lock_table = NULL;
 142
 143 /* Allocate a new lock, and initialize its fields from fl.
 144  * The lock is not inserted into any lists until locks_insert_lock() or
 145  * locks_insert_block() are called.
 146  */
 147 static inline struct file_lock *locks_alloc_lock(struct file_lock *fl)
 148 {
 149         return locks_init_lock(locks_empty_lock(), fl);
 150 }
 151
 152 /* Free lock not inserted in any queue.
 153  */
 154 static inline void locks_free_lock(struct file_lock *fl)
 155 {
 156         if (waitqueue_active(&fl->fl_wait))
 157                 panic("Attempting to free lock with active wait queue");
 158
 159         if (fl->fl_nextblock != NULL || fl->fl_prevblock != NULL)
 160                 panic("Attempting to free lock with active block list");
 161
 162         kfree(fl);
 163         return;
 164 }
 165
 166 /* Check if two locks overlap each other.
 167  */
 168 static inline int locks_overlap(struct file_lock *fl1, struct file_lock *fl2)
 169 {
 170         return ((fl1->fl_end >= fl2->fl_start) &&
 171                 (fl2->fl_end >= fl1->fl_start));
 172 }
 173
 174 /*
 175  * Check whether two locks have the same owner
 176  * N.B. Do we need the test on PID as well as owner?
 177  * (Clone tasks should be considered as one "owner".)
 178  */
 179 static inline int
 180 locks_same_owner(struct file_lock *fl1, struct file_lock *fl2)
 181 {
 182         return (fl1->fl_owner == fl2->fl_owner) &&
 183                (fl1->fl_pid   == fl2->fl_pid);
 184 }
 185
 186 /* Insert waiter into blocker's block list.
 187  * We use a circular list so that processes can be easily woken up in
 188  * the order they blocked. The documentation doesn't require this but
 189  * it seems like the reasonable thing to do.
 190  */
 191 static void locks_insert_block(struct file_lock *blocker,
 192                                struct file_lock *waiter)
 193 {
 194         struct file_lock *prevblock;
 195
 196         if (waiter->fl_prevblock) {
 197                 printk(KERN_ERR "locks_insert_block: remove duplicated lock "
 198                         "(pid=%d %ld-%ld type=%d)\n",
 199                         waiter->fl_pid, waiter->fl_start,
 200                         waiter->fl_end, waiter->fl_type);
 201                 locks_delete_block(waiter->fl_prevblock, waiter);
 202         }
 203
 204         if (blocker->fl_prevblock == NULL)
 205                 /* No previous waiters - list is empty */
 206                 prevblock = blocker;
 207         else
 208                 /* Previous waiters exist - add to end of list */
 209                 prevblock = blocker->fl_prevblock;
 210
 211         prevblock->fl_nextblock = waiter;
 212         blocker->fl_prevblock = waiter;
 213         waiter->fl_nextblock = blocker;
 214         waiter->fl_prevblock = prevblock;
 215
 216         return;
 217 }
 218
 219 /* Remove waiter from blocker's block list.
 220  * When blocker ends up pointing to itself then the list is empty.
 221  */
 222 static void locks_delete_block(struct file_lock *blocker,
 223                                struct file_lock *waiter)
 224 {
 225         struct file_lock *nextblock;
 226         struct file_lock *prevblock;
 227
 228         nextblock = waiter->fl_nextblock;
 229         prevblock = waiter->fl_prevblock;
 230
 231         if (nextblock == NULL)
 232                 return;
 233
 234         nextblock->fl_prevblock = prevblock;
 235         prevblock->fl_nextblock = nextblock;
 236
 237         waiter->fl_prevblock = waiter->fl_nextblock = NULL;
 238         if (blocker->fl_nextblock == blocker)
 239                 /* No more locks on blocker's blocked list */
 240                 blocker->fl_prevblock = blocker->fl_nextblock = NULL;
 241         return;
 242 }
 243
 244 /* The following two are for the benefit of lockd.
 245  */
 246 void
 247 posix_block_lock(struct file_lock *blocker, struct file_lock *waiter)
 248 {
 249         locks_insert_block(blocker, waiter);
 250         return;
 251 }
 252
 253 void
 254 posix_unblock_lock(struct file_lock *waiter)
 255 {
 256         if (waiter->fl_prevblock)
 257                 locks_delete_block(waiter->fl_prevblock, waiter);
 258         return;
 259 }
 260
 261 /* Wake up processes blocked waiting for blocker.
 262  * If told to wait then schedule the processes until the block list
 263  * is empty, otherwise empty the block list ourselves.
 264  */
 265 static void locks_wake_up_blocks(struct file_lock *blocker, unsigned int wait)
 266 {
 267         struct file_lock *waiter;
 268
 269         while ((waiter = blocker->fl_nextblock) != NULL) {
 270                 /* N.B. Is it possible for the notify function to block?? */
 271                 if (waiter->fl_notify)
 272                         waiter->fl_notify(waiter);
 273                 wake_up(&waiter->fl_wait);
 274                 if (wait) {
 275                         /* Let the blocked process remove waiter from the
 276                          * block list when it gets scheduled.
 277                          */
 278                         current->policy |= SCHED_YIELD;
 279                         schedule();
 280                 } else {
 281                         /* Remove waiter from the block list, because by the
 282                          * time it wakes up blocker won't exist any more.
 283                          */
 284                         locks_delete_block(blocker, waiter);
 285                 }
 286         }
 287         return;
 288 }
 289
 290 /* flock() system call entry point. Apply a FL_FLOCK style lock to
 291  * an open file descriptor.
 292  */
 293 asmlinkage long sys_flock(unsigned int fd, unsigned int cmd)
 294 {
 295         struct file_lock file_lock;
 296         struct file *filp;
 297         int error;
 298
 299         lock_kernel();
 300         error = -EBADF;
 301         filp = fget(fd);
 302         if (!filp)
 303                 goto out;
 304         error = -EINVAL;
 305         if (!flock_make_lock(filp, &file_lock, cmd))
 306                 goto out_putf;
 307         error = -EBADF;
 308         if ((file_lock.fl_type != F_UNLCK) && !(filp->f_mode & 3))
 309                 goto out_putf;
 310         error = flock_lock_file(filp, &file_lock,
 311                                 (cmd & (LOCK_UN | LOCK_NB)) ? 0 : 1);
 312 out_putf:
 313         fput(filp);
 314 out:
 315         unlock_kernel();
 316         return (error);
 317 }
 318
 319 /* Report the first existing lock that would conflict with l.
 320  * This implements the F_GETLK command of fcntl().
 321  */
 322 int fcntl_getlk(unsigned int fd, struct flock *l)
 323 {
 324         struct file *filp;
 325         struct file_lock *fl,file_lock;
 326         struct flock flock;
 327         int error;
 328
 329         error = -EFAULT;
 330         if (copy_from_user(&flock, l, sizeof(flock)))
 331                 goto out;
 332         error = -EINVAL;
 333         if ((flock.l_type != F_RDLCK) && (flock.l_type != F_WRLCK))
 334                 goto out;
 335
 336         error = -EBADF;
 337         filp = fget(fd);
 338         if (!filp)
 339                 goto out;
 340
 341         error = -EINVAL;
 342         if (!filp->f_dentry || !filp->f_dentry->d_inode)
 343                 goto out_putf;
 344
 345         if (!posix_make_lock(filp, &file_lock, &flock))
 346                 goto out_putf;
 347
 348         if (filp->f_op->lock) {
 349                 error = filp->f_op->lock(filp, F_GETLK, &file_lock);
 350                 if (error < 0)
 351                         goto out_putf;
 352                 else if (error == LOCK_USE_CLNT)
 353                   /* Bypass for NFS with no locking - 2.0.36 compat */
 354                   fl = posix_test_lock(filp, &file_lock);
 355                 else
 356                   fl = (file_lock.fl_type == F_UNLCK ? NULL : &file_lock);
 357         } else {
 358                 fl = posix_test_lock(filp, &file_lock);
 359         }
 360
 361         flock.l_type = F_UNLCK;
 362         if (fl != NULL) {
 363                 flock.l_pid = fl->fl_pid;
 364                 flock.l_start = fl->fl_start;
 365                 flock.l_len = fl->fl_end == OFFSET_MAX ? 0 :
 366                         fl->fl_end - fl->fl_start + 1;
 367                 flock.l_whence = 0;
 368                 flock.l_type = fl->fl_type;
 369         }
 370         error = -EFAULT;
 371         if (!copy_to_user(l, &flock, sizeof(flock)))
 372                 error = 0;
 373
 374 out_putf:
 375         fput(filp);
 376 out:
 377         return error;
 378 }
 379
 380 /* Apply the lock described by l to an open file descriptor.
 381  * This implements both the F_SETLK and F_SETLKW commands of fcntl().
 382  */
 383 int fcntl_setlk(unsigned int fd, unsigned int cmd, struct flock *l)
 384 {
 385         struct file *filp;
 386         struct file_lock file_lock;
 387         struct flock flock;
 388         struct dentry * dentry;
 389         struct inode *inode;
 390         int error;
 391
 392         /*
 393          * This might block, so we do it before checking the inode.
 394          */
 395         error = -EFAULT;
 396         if (copy_from_user(&flock, l, sizeof(flock)))
 397                 goto out;
 398
 399         /* Get arguments and validate them ...
 400          */
 401
 402         error = -EBADF;
 403         filp = fget(fd);
 404         if (!filp)
 405                 goto out;
 406
 407         error = -EINVAL;
 408         if (!(dentry = filp->f_dentry))
 409                 goto out_putf;
 410         if (!(inode = dentry->d_inode))
 411                 goto out_putf;
 412
 413         /* Don't allow mandatory locks on files that may be memory mapped
 414          * and shared.
 415          */
 416         if (IS_MANDLOCK(inode) &&
 417             (inode->i_mode & (S_ISGID | S_IXGRP)) == S_ISGID) {
 418                 struct vm_area_struct *vma;
 419                 spin_lock(&inode->i_shared_lock);
 420                 for(vma = inode->i_mmap;vma;vma = vma->vm_next_share) {
 421                         if (!(vma->vm_flags & VM_MAYSHARE))
 422                                 continue;
 423                         spin_unlock(&inode->i_shared_lock);
 424                         error = -EAGAIN;
 425                         goto out_putf;
 426                 }
 427                 spin_unlock(&inode->i_shared_lock);
 428         }
 429
 430         error = -EINVAL;
 431         if (!posix_make_lock(filp, &file_lock, &flock))
 432                 goto out_putf;
 433
 434         error = -EBADF;
 435         switch (flock.l_type) {
 436         case F_RDLCK:
 437                 if (!(filp->f_mode & FMODE_READ))
 438                         goto out_putf;
 439                 break;
 440         case F_WRLCK:
 441                 if (!(filp->f_mode & FMODE_WRITE))
 442                         goto out_putf;
 443                 break;
 444         case F_UNLCK:
 445                 break;
 446         case F_SHLCK:
 447         case F_EXLCK:
 448 #ifdef __sparc__
 449 /* warn a bit for now, but don't overdo it */
 450 {
 451         static int count = 0;
 452         if (!count) {
 453                 count=1;
 454                 printk(KERN_WARNING
 455                        "fcntl_setlk() called by process %d (%s) with broken flock() emulation\n",
 456                        current->pid, current->comm);
 457         }
 458 }
 459                 if (!(filp->f_mode & 3))
 460                         goto out_putf;
 461                 break;
 462 #endif
 463         default:
 464                 error = -EINVAL;
 465                 goto out_putf;
 466         }
 467
 468         if (filp->f_op->lock != NULL) {
 469                 error = filp->f_op->lock(filp, cmd, &file_lock);
 470                 if (error < 0)
 471                         goto out_putf;
 472         }
 473         error = posix_lock_file(filp, &file_lock, cmd == F_SETLKW);
 474
 475 out_putf:
 476         fput(filp);
 477 out:
 478         return error;
 479 }
 480
 481 /*
 482  * This function is called when the file is being removed
 483  * from the task's fd array.
 484  */
 485 void locks_remove_posix(struct file *filp, fl_owner_t owner)
 486 {
 487         struct inode * inode = filp->f_dentry->d_inode;
 488         struct file_lock file_lock, *fl;
 489         struct file_lock **before;
 490
 491         /*
 492          * For POSIX locks we free all locks on this file for the given task.
 493          */
 494 repeat:
 495         before = &inode->i_flock;
 496         while ((fl = *before) != NULL) {
 497                 if ((fl->fl_flags & FL_POSIX) && fl->fl_owner == owner) {
 498                         int (*lock)(struct file *, int, struct file_lock *);
 499                         lock = filp->f_op->lock;
 500                         if (lock) {
 501                                 file_lock = *fl;
 502                                 file_lock.fl_type = F_UNLCK;
 503                         }
 504                         locks_delete_lock(before, 0);
 505                         if (lock) {
 506                                 lock(filp, F_SETLK, &file_lock);
 507                                 /* List may have changed: */
 508                                 goto repeat;
 509                         }
 510                         continue;
 511                 }
 512                 before = &fl->fl_next;
 513         }
 514 }
 515
 516 /*
 517  * This function is called on the last close of an open file.
 518  */
 519 void locks_remove_flock(struct file *filp)
 520 {
 521         struct inode * inode = filp->f_dentry->d_inode;
 522         struct file_lock file_lock, *fl;
 523         struct file_lock **before;
 524
 525 repeat:
 526         before = &inode->i_flock;
 527         while ((fl = *before) != NULL) {
 528                 if ((fl->fl_flags & FL_FLOCK) && fl->fl_file == filp) {
 529                         int (*lock)(struct file *, int, struct file_lock *);
 530                         lock = NULL;
 531                         if (filp->f_op)
 532                                 lock = filp->f_op->lock;
 533                         if (lock) {
 534                                 file_lock = *fl;
 535                                 file_lock.fl_type = F_UNLCK;
 536                         }
 537                         locks_delete_lock(before, 0);
 538                         if (lock) {
 539                                 lock(filp, F_SETLK, &file_lock);
 540                                 /* List may have changed: */
 541                                 goto repeat;
 542                         }
 543                         continue;
 544                 }
 545                 before = &fl->fl_next;
 546         }
 547 }
 548
 549 struct file_lock *
 550 posix_test_lock(struct file *filp, struct file_lock *fl)
 551 {
 552         struct file_lock *cfl;
 553
 554         for (cfl = filp->f_dentry->d_inode->i_flock; cfl; cfl = cfl->fl_next) {
 555                 if (!(cfl->fl_flags & FL_POSIX))
 556                         continue;
 557                 if (posix_locks_conflict(cfl, fl))
 558                         break;
 559         }
 560
 561         return (cfl);
 562 }
 563
 564 int locks_mandatory_locked(struct inode *inode)
 565 {
 566         fl_owner_t owner = current->files;
 567         struct file_lock *fl;
 568
 569         /*
 570          * Search the lock list for this inode for any POSIX locks.
 571          */
 572         lock_kernel();
 573         for (fl = inode->i_flock; fl != NULL; fl = fl->fl_next) {
 574                 if (!(fl->fl_flags & FL_POSIX))
 575                         continue;
 576                 if (fl->fl_owner != owner)
 577                         break;
 578         }
 579         unlock_kernel();
 580         return fl ? -EAGAIN : 0;
 581 }
 582
 583 int locks_mandatory_area(int read_write, struct inode *inode,
 584                          struct file *filp, loff_t offset,
 585                          size_t count)
 586 {
 587         struct file_lock *fl;
 588         struct file_lock tfl;
 589         int error;
 590
 591         memset(&tfl, 0, sizeof(tfl));
 592
 593         tfl.fl_file = filp;
 594         tfl.fl_flags = FL_POSIX | FL_ACCESS;
 595         tfl.fl_owner = current->files;
 596         tfl.fl_pid = current->pid;
 597         init_waitqueue_head(&tfl.fl_wait);
 598         tfl.fl_type = (read_write == FLOCK_VERIFY_WRITE) ? F_WRLCK : F_RDLCK;
 599         tfl.fl_start = offset;
 600         tfl.fl_end = offset + count - 1;
 601
 602         error = 0;
 603         lock_kernel();
 604
 605 repeat:
 606         /* Search the lock list for this inode for locks that conflict with
 607          * the proposed read/write.
 608          */
 609         for (fl = inode->i_flock; ; fl = fl->fl_next) {
 610                 error = 0;
 611                 if (!fl)
 612                         break;
 613                 if (!(fl->fl_flags & FL_POSIX))
 614                         continue;
 615                 /* Block for writes against a "read" lock,
 616                  * and both reads and writes against a "write" lock.
 617                  */
 618                 if (posix_locks_conflict(fl, &tfl)) {
 619                         error = -EAGAIN;
 620                         if (filp && (filp->f_flags & O_NONBLOCK))
 621                                 break;
 622                         error = -ERESTARTSYS;
 623                         if (signal_pending(current))
 624                                 break;
 625                         error = -EDEADLK;
 626                         if (posix_locks_deadlock(&tfl, fl))
 627                                 break;
 628
 629                         locks_insert_block(fl, &tfl);
 630                         interruptible_sleep_on(&tfl.fl_wait);
 631                         locks_delete_block(fl, &tfl);
 632
 633                         /*
 634                          * If we've been sleeping someone might have
 635                          * changed the permissions behind our back.
 636                          */
 637                         if ((inode->i_mode & (S_ISGID | S_IXGRP)) != S_ISGID)
 638                                 break;
 639                         goto repeat;
 640                 }
 641         }
 642         unlock_kernel();
 643         return error;
 644 }
 645
 646 /* Verify a "struct flock" and copy it to a "struct file_lock" as a POSIX
 647  * style lock.
 648  */
 649 static int posix_make_lock(struct file *filp, struct file_lock *fl,
 650                            struct flock *l)
 651 {
 652         off_t start;
 653
 654         memset(fl, 0, sizeof(*fl));
 655
 656         init_waitqueue_head(&fl->fl_wait);
 657         fl->fl_flags = FL_POSIX;
 658
 659         switch (l->l_type) {
 660         case F_RDLCK:
 661         case F_WRLCK:
 662         case F_UNLCK:
 663                 fl->fl_type = l->l_type;
 664                 break;
 665         default:
 666                 return (0);
 667         }
 668
 669         switch (l->l_whence) {
 670         case 0: /*SEEK_SET*/
 671                 start = 0;
 672                 break;
 673         case 1: /*SEEK_CUR*/
 674                 start = filp->f_pos;
 675                 break;
 676         case 2: /*SEEK_END*/
 677                 start = filp->f_dentry->d_inode->i_size;
 678                 break;
 679         default:
 680                 return (0);
 681         }
 682
 683         if (((start += l->l_start) < 0) || (l->l_len < 0))
 684                 return (0);
 685         fl->fl_start = start;   /* we record the absolute position */
 686         if ((l->l_len == 0) || ((fl->fl_end = start + l->l_len - 1) < 0))
 687                 fl->fl_end = OFFSET_MAX;
 688
 689         fl->fl_file = filp;
 690         fl->fl_owner = current->files;
 691         fl->fl_pid = current->pid;
 692
 693         return (1);
 694 }
 695
 696 /* Verify a call to flock() and fill in a file_lock structure with
 697  * an appropriate FLOCK lock.
 698  */
 699 static int flock_make_lock(struct file *filp, struct file_lock *fl,
 700                            unsigned int cmd)
 701 {
 702         memset(fl, 0, sizeof(*fl));
 703
 704         init_waitqueue_head(&fl->fl_wait);
 705         if (!filp->f_dentry)    /* just in case */
 706                 return (0);
 707
 708         switch (cmd & ~LOCK_NB) {
 709         case LOCK_SH:
 710                 fl->fl_type = F_RDLCK;
 711                 break;
 712         case LOCK_EX:
 713                 fl->fl_type = F_WRLCK;
 714                 break;
 715         case LOCK_UN:
 716                 fl->fl_type = F_UNLCK;
 717                 break;
 718         default:
 719                 return (0);
 720         }
 721
 722         fl->fl_flags = FL_FLOCK;
 723         fl->fl_start = 0;
 724         fl->fl_end = OFFSET_MAX;
 725         fl->fl_file = filp;
 726         fl->fl_owner = NULL;
 727
 728         return (1);
 729 }
 730
 731 /* Determine if lock sys_fl blocks lock caller_fl. POSIX specific
 732  * checking before calling the locks_conflict().
 733  */
 734 static int posix_locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
 735 {
 736         /* POSIX locks owned by the same process do not conflict with
 737          * each other.
 738          */
 739         if (!(sys_fl->fl_flags & FL_POSIX) ||
 740             locks_same_owner(caller_fl, sys_fl))
 741                 return (0);
 742
 743         return (locks_conflict(caller_fl, sys_fl));
 744 }
 745
 746 /* Determine if lock sys_fl blocks lock caller_fl. FLOCK specific
 747  * checking before calling the locks_conflict().
 748  */
 749 static int flock_locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
 750 {
 751         /* FLOCK locks referring to the same filp do not conflict with
 752          * each other.
 753          */
 754         if (!(sys_fl->fl_flags & FL_FLOCK) ||
 755             (caller_fl->fl_file == sys_fl->fl_file))
 756                 return (0);
 757
 758         return (locks_conflict(caller_fl, sys_fl));
 759 }
 760
 761 /* Determine if lock sys_fl blocks lock caller_fl. Common functionality
 762  * checks for overlapping locks and shared/exclusive status.
 763  */
 764 static int locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
 765 {
 766         if (!locks_overlap(caller_fl, sys_fl))
 767                 return (0);
 768
 769         switch (caller_fl->fl_type) {
 770         case F_RDLCK:
 771                 return (sys_fl->fl_type == F_WRLCK);
 772
 773         case F_WRLCK:
 774                 return (1);
 775
 776         default:
 777                 printk("locks_conflict(): impossible lock type - %d\n",
 778                        caller_fl->fl_type);
 779                 break;
 780         }
 781         return (0);     /* This should never happen */
 782 }
 783
 784 /* This function tests for deadlock condition before putting a process to
 785  * sleep. The detection scheme is no longer recursive. Recursive was neat,
 786  * but dangerous - we risked stack corruption if the lock data was bad, or
 787  * if the recursion was too deep for any other reason.
 788  *
 789  * We rely on the fact that a task can only be on one lock's wait queue
 790  * at a time. When we find blocked_task on a wait queue we can re-search
 791  * with blocked_task equal to that queue's owner, until either blocked_task
 792  * isn't found, or blocked_task is found on a queue owned by my_task.
 793  *
 794  * Note: the above assumption may not be true when handling lock requests
 795  * from a broken NFS client. But broken NFS clients have a lot more to
 796  * worry about than proper deadlock detection anyway... --okir
 797  */
 798 static int posix_locks_deadlock(struct file_lock *caller_fl,
 799                                 struct file_lock *block_fl)
 800 {
 801         struct file_lock *fl;
 802         struct file_lock *bfl;
 803         void             *caller_owner, *blocked_owner;
 804         unsigned int     caller_pid, blocked_pid;
 805
 806         caller_owner = caller_fl->fl_owner;
 807         caller_pid = caller_fl->fl_pid;
 808         blocked_owner = block_fl->fl_owner;
 809         blocked_pid = block_fl->fl_pid;
 810
 811 next_task:
 812         if (caller_owner == blocked_owner && caller_pid == blocked_pid)
 813                 return (1);
 814         for (fl = file_lock_table; fl != NULL; fl = fl->fl_nextlink) {
 815                 if (fl->fl_owner == NULL || fl->fl_nextblock == NULL)
 816                         continue;
 817                 for (bfl = fl->fl_nextblock; bfl != fl; bfl = bfl->fl_nextblock) {
 818                         if (bfl->fl_owner == blocked_owner &&
 819                             bfl->fl_pid == blocked_pid) {
 820                                 if (fl->fl_owner == caller_owner &&
 821                                     fl->fl_pid == caller_pid) {
 822                                         return (1);
 823                                 }
 824                                 blocked_owner = fl->fl_owner;
 825                                 blocked_pid = fl->fl_pid;
 826                                 goto next_task;
 827                         }
 828                 }
 829         }
 830         return (0);
 831 }
 832
 833 /* Try to create a FLOCK lock on filp. We always insert new FLOCK locks at
 834  * the head of the list, but that's secret knowledge known only to the next
 835  * two functions.
 836  */
 837 static int flock_lock_file(struct file *filp, struct file_lock *caller,
 838                            unsigned int wait)
 839 {
 840         struct file_lock *fl;
 841         struct file_lock *new_fl = NULL;
 842         struct file_lock **before;
 843         struct inode * inode = filp->f_dentry->d_inode;
 844         int error, change;
 845         int unlock = (caller->fl_type == F_UNLCK);
 846
 847         /*
 848          * If we need a new lock, get it in advance to avoid races.
 849          */
 850         if (!unlock) {
 851                 error = -ENOLCK;
 852                 new_fl = locks_alloc_lock(caller);
 853                 if (!new_fl)
 854                         goto out;
 855         }
 856
 857         error = 0;
 858 search:
 859         change = 0;
 860         before = &inode->i_flock;
 861         while (((fl = *before) != NULL) && (fl->fl_flags & FL_FLOCK)) {
 862                 if (caller->fl_file == fl->fl_file) {
 863                         if (caller->fl_type == fl->fl_type)
 864                                 goto out;
 865                         change = 1;
 866                         break;
 867                 }
 868                 before = &fl->fl_next;
 869         }
 870         /* change means that we are changing the type of an existing lock, or
 871          * or else unlocking it.
 872          */
 873         if (change) {
 874                 /* N.B. What if the wait argument is false? */
 875                 locks_delete_lock(before, !unlock);
 876                 /*
 877                  * If we waited, another lock may have been added ...
 878                  */
 879                 if (!unlock)
 880                         goto search;
 881         }
 882         if (unlock)
 883                 goto out;
 884
 885 repeat:
 886         /* Check signals each time we start */
 887         error = -ERESTARTSYS;
 888         if (signal_pending(current))
 889                 goto out;
 890         for (fl = inode->i_flock; (fl != NULL) && (fl->fl_flags & FL_FLOCK);
 891              fl = fl->fl_next) {
 892                 if (!flock_locks_conflict(new_fl, fl))
 893                         continue;
 894                 error = -EAGAIN;
 895                 if (!wait)
 896                         goto out;
 897                 locks_insert_block(fl, new_fl);
 898                 interruptible_sleep_on(&new_fl->fl_wait);
 899                 locks_delete_block(fl, new_fl);
 900                 goto repeat;
 901         }
 902         locks_insert_lock(&inode->i_flock, new_fl);
 903         new_fl = NULL;
 904         error = 0;
 905
 906 out:
 907         if (new_fl)
 908                 locks_free_lock(new_fl);
 909         return error;
 910 }
 911
 912 /* Add a POSIX style lock to a file.
 913  * We merge adjacent locks whenever possible. POSIX locks are sorted by owner
 914  * task, then by starting address
 915  *
 916  * Kai Petzke writes:
 917  * To make freeing a lock much faster, we keep a pointer to the lock before the
 918  * actual one. But the real gain of the new coding was, that lock_it() and
 919  * unlock_it() became one function.
 920  *
 921  * To all purists: Yes, I use a few goto's. Just pass on to the next function.
 922  */
 923
 924 int posix_lock_file(struct file *filp, struct file_lock *caller,
 925                            unsigned int wait)
 926 {
 927         struct file_lock *fl;
 928         struct file_lock *new_fl, *new_fl2;
 929         struct file_lock *left = NULL;
 930         struct file_lock *right = NULL;
 931         struct file_lock **before;
 932         struct inode * inode = filp->f_dentry->d_inode;
 933         int error, added = 0;
 934
 935         /*
 936          * We may need two file_lock structures for this operation,
 937          * so we get them in advance to avoid races.
 938          */
 939         new_fl  = locks_empty_lock();
 940         new_fl2 = locks_empty_lock();
 941         error = -ENOLCK; /* "no luck" */
 942         if (!(new_fl && new_fl2))
 943                 goto out;
 944
 945         if (caller->fl_type != F_UNLCK) {
 946   repeat:
 947                 for (fl = inode->i_flock; fl != NULL; fl = fl->fl_next) {
 948                         if (!(fl->fl_flags & FL_POSIX))
 949                                 continue;
 950                         if (!posix_locks_conflict(caller, fl))
 951                                 continue;
 952                         error = -EAGAIN;
 953                         if (!wait)
 954                                 goto out;
 955                         error = -EDEADLK;
 956                         if (posix_locks_deadlock(caller, fl))
 957                                 goto out;
 958                         error = -ERESTARTSYS;
 959                         if (signal_pending(current))
 960                                 goto out;
 961                         locks_insert_block(fl, caller);
 962                         interruptible_sleep_on(&caller->fl_wait);
 963                         locks_delete_block(fl, caller);
 964                         goto repeat;
 965                 }
 966         }
 967
 968         /*
 969          * We've allocated the new locks in advance, so there are no
 970          * errors possible (and no blocking operations) from here on.
 971          *
 972          * Find the first old lock with the same owner as the new lock.
 973          */
 974
 975         before = &inode->i_flock;
 976
 977         /* First skip locks owned by other processes.
 978          */
 979         while ((fl = *before) && (!(fl->fl_flags & FL_POSIX) ||
 980                                   !locks_same_owner(caller, fl))) {
 981                 before = &fl->fl_next;
 982         }
 983
 984         /* Process locks with this owner.
 985          */
 986         while ((fl = *before) && locks_same_owner(caller, fl)) {
 987                 /* Detect adjacent or overlapping regions (if same lock type)
 988                  */
 989                 if (caller->fl_type == fl->fl_type) {
 990                         if (fl->fl_end < caller->fl_start - 1)
 991                                 goto next_lock;
 992                         /* If the next lock in the list has entirely bigger
 993                          * addresses than the new one, insert the lock here.
 994                          */
 995                         if (fl->fl_start > caller->fl_end + 1)
 996                                 break;
 997
 998                         /* If we come here, the new and old lock are of the
 999                          * same type and adjacent or overlapping. Make one
1000                          * lock yielding from the lower start address of both
1001                          * locks to the higher end address.
1002                          */
1003                         if (fl->fl_start > caller->fl_start)
1004                                 fl->fl_start = caller->fl_start;
1005                         else
1006                                 caller->fl_start = fl->fl_start;
1007                         if (fl->fl_end < caller->fl_end)
1008                                 fl->fl_end = caller->fl_end;
1009                         else
1010                                 caller->fl_end = fl->fl_end;
1011                         if (added) {
1012                                 locks_delete_lock(before, 0);
1013                                 continue;
1014                         }
1015                         caller = fl;
1016                         added = 1;
1017                 }
1018                 else {
1019                         /* Processing for different lock types is a bit
1020                          * more complex.
1021                          */
1022                         if (fl->fl_end < caller->fl_start)
1023                                 goto next_lock;
1024                         if (fl->fl_start > caller->fl_end)
1025                                 break;
1026                         if (caller->fl_type == F_UNLCK)
1027                                 added = 1;
1028                         if (fl->fl_start < caller->fl_start)
1029                                 left = fl;
1030                         /* If the next lock in the list has a higher end
1031                          * address than the new one, insert the new one here.
1032                          */
1033                         if (fl->fl_end > caller->fl_end) {
1034                                 right = fl;
1035                                 break;
1036                         }
1037                         if (fl->fl_start >= caller->fl_start) {
1038                                 /* The new lock completely replaces an old
1039                                  * one (This may happen several times).
1040                                  */
1041                                 if (added) {
1042                                         locks_delete_lock(before, 0);
1043                                         continue;
1044                                 }
1045                                 /* Replace the old lock with the new one.
1046                                  * Wake up anybody waiting for the old one,
1047                                  * as the change in lock type might satisfy
1048                                  * their needs.
1049                                  */
1050                                 locks_wake_up_blocks(fl, 0);
1051                                 fl->fl_start = caller->fl_start;
1052                                 fl->fl_end = caller->fl_end;
1053                                 fl->fl_type = caller->fl_type;
1054                                 fl->fl_u = caller->fl_u;
1055                                 caller = fl;
1056                                 added = 1;
1057                         }
1058                 }
1059                 /* Go on to next lock.
1060                  */
1061         next_lock:
1062                 before = &fl->fl_next;
1063         }
1064
1065         error = 0;
1066         if (!added) {
1067                 if (caller->fl_type == F_UNLCK)
1068                         goto out;
1069                 locks_init_lock(new_fl, caller);
1070                 locks_insert_lock(before, new_fl);
1071                 new_fl = NULL;
1072         }
1073         if (right) {
1074                 if (left == right) {
1075                         /* The new lock breaks the old one in two pieces,
1076                          * so we have to use the second new lock (in this
1077                          * case, even F_UNLCK may fail!).
1078                          */
1079                         left = locks_init_lock(new_fl2, right);
1080                         locks_insert_lock(before, left);
1081                         new_fl2 = NULL;
1082                 }
1083                 right->fl_start = caller->fl_end + 1;
1084                 locks_wake_up_blocks(right, 0);
1085         }
1086         if (left) {
1087                 left->fl_end = caller->fl_start - 1;
1088                 locks_wake_up_blocks(left, 0);
1089         }
1090 out:
1091         /*
1092          * Free any unused locks.  (They haven't
1093          * ever been used, so we use kfree().)
1094          */
1095         if (new_fl)
1096                 kfree(new_fl);
1097         if (new_fl2)
1098                 kfree(new_fl2);
1099         return error;
1100 }
1101
1102 /*
1103  * Allocate an empty lock structure. We can use GFP_KERNEL now that
1104  * all allocations are done in advance.
1105  */
1106 static struct file_lock *locks_empty_lock(void)
1107 {
1108         /* Okay, let's make a new file_lock structure... */
1109         return ((struct file_lock *) kmalloc(sizeof(struct file_lock),
1110                                                 GFP_KERNEL));
1111 }
1112
1113 /*
1114  * Initialize a new lock from an existing file_lock structure.
1115  */
1116 static struct file_lock *locks_init_lock(struct file_lock *new,
1117                                          struct file_lock *fl)
1118 {
1119         if (new) {
1120                 memset(new, 0, sizeof(*new));
1121                 new->fl_owner = fl->fl_owner;
1122                 new->fl_pid = fl->fl_pid;
1123                 init_waitqueue_head(&new->fl_wait);
1124                 new->fl_file = fl->fl_file;
1125                 new->fl_flags = fl->fl_flags;
1126                 new->fl_type = fl->fl_type;
1127                 new->fl_start = fl->fl_start;
1128                 new->fl_end = fl->fl_end;
1129                 new->fl_notify = fl->fl_notify;
1130                 new->fl_u = fl->fl_u;
1131         }
1132         return new;
1133 }
1134
1135 /* Insert file lock fl into an inode's lock list at the position indicated
1136  * by pos. At the same time add the lock to the global file lock list.
1137  */
1138 static void locks_insert_lock(struct file_lock **pos, struct file_lock *fl)
1139 {
1140         fl->fl_nextlink = file_lock_table;
1141         fl->fl_prevlink = NULL;
1142         if (file_lock_table != NULL)
1143                 file_lock_table->fl_prevlink = fl;
1144         file_lock_table = fl;
1145         fl->fl_next = *pos;     /* insert into file's list */
1146         *pos = fl;
1147
1148         return;
1149 }
1150
1151 /* Delete a lock and free it.
1152  * First remove our lock from the active lock lists. Then call
1153  * locks_wake_up_blocks() to wake up processes that are blocked
1154  * waiting for this lock. Finally free the lock structure.
1155  */
1156 static void locks_delete_lock(struct file_lock **thisfl_p, unsigned int wait)
1157 {
1158         struct file_lock *thisfl;
1159         struct file_lock *prevfl;
1160         struct file_lock *nextfl;
1161
1162         thisfl = *thisfl_p;
1163         *thisfl_p = thisfl->fl_next;
1164
1165         prevfl = thisfl->fl_prevlink;
1166         nextfl = thisfl->fl_nextlink;
1167
1168         if (nextfl != NULL)
1169                 nextfl->fl_prevlink = prevfl;
1170
1171         if (prevfl != NULL)
1172                 prevfl->fl_nextlink = nextfl;
1173         else
1174                 file_lock_table = nextfl;
1175
1176         locks_wake_up_blocks(thisfl, wait);
1177         locks_free_lock(thisfl);
1178
1179         return;
1180 }
1181
1182
1183 static char *lock_get_status(struct file_lock *fl, int id, char *pfx)
1184 {
1185         static char temp[155];
1186         char *p = temp;
1187         struct inode *inode;
1188
1189         inode = fl->fl_file->f_dentry->d_inode;
1190
1191         p += sprintf(p, "%d:%s ", id, pfx);
1192         if (fl->fl_flags & FL_POSIX) {
1193                 p += sprintf(p, "%6s %s ",
1194                              (fl->fl_flags & FL_ACCESS) ? "ACCESS" : "POSIX ",
1195                              (IS_MANDLOCK(inode) &&
1196                               (inode->i_mode & (S_IXGRP | S_ISGID)) == S_ISGID) ?
1197                              "MANDATORY" : "ADVISORY ");
1198         }
1199         else {
1200                 p += sprintf(p, "FLOCK  ADVISORY  ");
1201         }
1202         p += sprintf(p, "%s ", (fl->fl_type == F_RDLCK) ? "READ " : "WRITE");
1203         p += sprintf(p, "%d %s:%ld %ld %ld ",
1204                      fl->fl_pid,
1205                      kdevname(inode->i_dev), inode->i_ino, fl->fl_start,
1206                      fl->fl_end);
1207         sprintf(p, "%08lx %08lx %08lx %08lx %08lx\n",
1208                 (long)fl, (long)fl->fl_prevlink, (long)fl->fl_nextlink,
1209                 (long)fl->fl_next, (long)fl->fl_nextblock);
1210         return (temp);
1211 }
1212
1213 static inline int copy_lock_status(char *p, char **q, off_t pos, int len,
1214                                    off_t offset, off_t length)
1215 {
1216         off_t i;
1217
1218         i = pos - offset;
1219         if (i > 0) {
1220                 if (i >= length) {
1221                         i = len + length - i;
1222                         memcpy(*q, p, i);
1223                         *q += i;
1224                         return (0);
1225                 }
1226                 if (i < len) {
1227                         p += len - i;
1228                 }
1229                 else
1230                         i = len;
1231                 memcpy(*q, p, i);
1232                 *q += i;
1233         }
1234
1235         return (1);
1236 }
1237
1238 int get_locks_status(char *buffer, char **start, off_t offset, off_t length)
1239 {
1240         struct file_lock *fl;
1241         struct file_lock *bfl;
1242         char *p;
1243         char *q = buffer;
1244         off_t i, len, pos = 0;
1245
1246         for (fl = file_lock_table, i = 1; fl != NULL; fl = fl->fl_nextlink, i++) {
1247                 p = lock_get_status(fl, i, "");
1248                 len = strlen(p);
1249                 pos += len;
1250                 if (!copy_lock_status(p, &q, pos, len, offset, length))
1251                         goto done;
1252                 if ((bfl = fl->fl_nextblock) == NULL)
1253                         continue;
1254                 do {
1255                         p = lock_get_status(bfl, i, " ->");
1256                         len = strlen(p);
1257                         pos += len;
1258                         if (!copy_lock_status(p, &q, pos, len, offset, length))
1259                                 goto done;
1260                 } while ((bfl = bfl->fl_nextblock) != fl);
1261         }
1262 done:
1263         if (q != buffer)
1264                 *start = buffer;
1265         return (q - buffer);
1266 }
1267
1268
1269