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