sys/kern/kern_lockf.c

   1 /*
   2  * Copyright (c) 2004 Joerg Sonnenberger <joerg@bec.de>.  All rights reserved.
   3  * Copyright (c) 2006 Matthew Dillon <dillon@backplane.com>.  All rights reserved.
   4  *
   5  * Copyright (c) 1982, 1986, 1989, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * This code is derived from software contributed to Berkeley by
   9  * Scooter Morris at Genentech Inc.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. All advertising materials mentioning features or use of this software
  20  *    must display the following acknowledgement:
  21  *      This product includes software developed by the University of
  22  *      California, Berkeley and its contributors.
  23  * 4. Neither the name of the University nor the names of its contributors
  24  *    may be used to endorse or promote products derived from this software
  25  *    without specific prior written permission.
  26  *
  27  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37  * SUCH DAMAGE.
  38  *
  39  *      @(#)ufs_lockf.c 8.3 (Berkeley) 1/6/94
  40  * $FreeBSD: src/sys/kern/kern_lockf.c,v 1.25 1999/11/16 16:28:56 phk Exp $
  41  * $DragonFly: src/sys/kern/kern_lockf.c,v 1.37 2007/11/01 22:48:16 dillon Exp $
  42  */
  43
  44 #include <sys/param.h>
  45 #include <sys/systm.h>
  46 #include <sys/kernel.h>
  47 #include <sys/lock.h>
  48 #include <sys/proc.h>
  49 #include <sys/unistd.h>
  50 #include <sys/vnode.h>
  51 #include <sys/malloc.h>
  52 #include <sys/fcntl.h>
  53 #include <sys/resourcevar.h>
  54
  55 #include <sys/lockf.h>
  56 #include <machine/limits.h>     /* for LLONG_MAX */
  57 #include <machine/stdarg.h>
  58
  59 #include <sys/spinlock2.h>
  60
  61 #ifdef INVARIANTS
  62 int lf_global_counter = 0;
  63 #endif
  64
  65 #ifdef LOCKF_DEBUG
  66 int lf_print_ranges = 0;
  67
  68 static void _lf_print_lock(const struct lockf *);
  69 static void _lf_printf(const char *, ...);
  70
  71 #define lf_print_lock(lock) if (lf_print_ranges) _lf_print_lock(lock)
  72 #define lf_printf(ctl, args...) if (lf_print_ranges) _lf_printf(ctl, args)
  73 #else
  74 #define lf_print_lock(lock)
  75 #define lf_printf(ctl, args...)
  76 #endif
  77
  78 static MALLOC_DEFINE(M_LOCKF, "lockf", "Byte-range locking structures");
  79
  80 static void     lf_wakeup(struct lockf *, off_t, off_t);
  81 static struct lockf_range *lf_alloc_range(void);
  82 static void     lf_create_range(struct lockf_range *, struct proc *, int, int,
  83                                 off_t, off_t);
  84 static void     lf_insert(struct lockf_range_list *list,
  85                                 struct lockf_range *elm,
  86                                 struct lockf_range *insert_point);
  87 static void     lf_destroy_range(struct lockf_range *);
  88
  89 static int      lf_setlock(struct lockf *, struct proc *, int, int,
  90                            off_t, off_t);
  91 static int      lf_getlock(struct flock *, struct lockf *, struct proc *,
  92                            int, int, off_t, off_t);
  93
  94 static int      lf_count_change(struct proc *, int);
  95
  96 /*
  97  * Return TRUE (non-zero) if the type and posix flags match.
  98  */
  99 static __inline
 100 int
 101 lf_match(struct lockf_range *range, int type, int flags)
 102 {
 103         if (range->lf_type != type)
 104                 return(0);
 105         if ((range->lf_flags ^ flags) & F_POSIX)
 106                 return(0);
 107         return(1);
 108 }
 109
 110 /*
 111  * Check whether range and [start, end] overlap.
 112  */
 113 static __inline
 114 int
 115 lf_overlap(const struct lockf_range *range, off_t start, off_t end)
 116 {
 117         if (range->lf_start >= start && range->lf_start <= end)
 118                 return(1);
 119         else if (start >= range->lf_start && start <= range->lf_end)
 120                 return(1);
 121         else
 122                 return(0);
 123 }
 124
 125
 126 /*
 127  * Change the POSIX lock accounting for the given process.
 128  */
 129 void
 130 lf_count_adjust(struct proc *p, int increase)
 131 {
 132         struct uidinfo *uip;
 133
 134         KKASSERT(p != NULL);
 135
 136         uip = p->p_ucred->cr_uidinfo;
 137         spin_lock(&uip->ui_lock);
 138
 139         if (increase)
 140                 uip->ui_posixlocks += p->p_numposixlocks;
 141         else
 142                 uip->ui_posixlocks -= p->p_numposixlocks;
 143
 144         KASSERT(uip->ui_posixlocks >= 0,
 145                 ("Negative number of POSIX locks held by %s user: %d.",
 146                  increase ? "new" : "old", uip->ui_posixlocks));
 147         spin_unlock(&uip->ui_lock);
 148 }
 149
 150 static int
 151 lf_count_change(struct proc *owner, int diff)
 152 {
 153         struct uidinfo *uip;
 154         int max, ret;
 155
 156         /* we might actually not have a process context */
 157         if (owner == NULL)
 158                 return(0);
 159
 160         uip = owner->p_ucred->cr_uidinfo;
 161
 162         max = MIN(owner->p_rlimit[RLIMIT_POSIXLOCKS].rlim_cur,
 163                   maxposixlocksperuid);
 164
 165         spin_lock(&uip->ui_lock);
 166         if (diff > 0 && owner->p_ucred->cr_uid != 0 && max != -1 &&
 167             uip->ui_posixlocks >= max ) {
 168                 ret = 1;
 169         } else {
 170                 uip->ui_posixlocks += diff;
 171                 owner->p_numposixlocks += diff;
 172                 KASSERT(uip->ui_posixlocks >= 0,
 173                         ("Negative number of POSIX locks held by user: %d.",
 174                          uip->ui_posixlocks));
 175                 KASSERT(owner->p_numposixlocks >= 0,
 176                         ("Negative number of POSIX locks held by proc: %d.",
 177                          uip->ui_posixlocks));
 178                 ret = 0;
 179         }
 180         spin_unlock(&uip->ui_lock);
 181         return ret;
 182 }
 183
 184 /*
 185  * Advisory record locking support
 186  */
 187 int
 188 lf_advlock(struct vop_advlock_args *ap, struct lockf *lock, u_quad_t size)
 189 {
 190         struct flock *fl = ap->a_fl;
 191         struct proc *owner;
 192         off_t start, end;
 193         int type, flags, error;
 194         lwkt_token_t token;
 195
 196         /*
 197          * Convert the flock structure into a start and end.
 198          */
 199         switch (fl->l_whence) {
 200         case SEEK_SET:
 201         case SEEK_CUR:
 202                 /*
 203                  * Caller is responsible for adding any necessary offset
 204                  * when SEEK_CUR is used.
 205                  */
 206                 start = fl->l_start;
 207                 break;
 208
 209         case SEEK_END:
 210                 start = size + fl->l_start;
 211                 break;
 212
 213         default:
 214                 return(EINVAL);
 215         }
 216
 217         flags = ap->a_flags;
 218         if (start < 0)
 219                 return(EINVAL);
 220         if (fl->l_len == 0) {
 221                 flags |= F_NOEND;
 222                 end = LLONG_MAX;
 223         } else if (fl->l_len < 0) {
 224                 return(EINVAL);
 225         } else {
 226                 end = start + fl->l_len - 1;
 227                 if (end < start)
 228                         return(EINVAL);
 229         }
 230
 231         type = fl->l_type;
 232         /*
 233          * This isn't really correct for flock-style locks,
 234          * but the current handling is somewhat broken anyway.
 235          */
 236         owner = (struct proc *)ap->a_id;
 237
 238         /*
 239          * Do the requested operation.
 240          */
 241         token = lwkt_getpooltoken(lock);
 242
 243         if (lock->init_done == 0) {
 244                 TAILQ_INIT(&lock->lf_range);
 245                 TAILQ_INIT(&lock->lf_blocked);
 246                 lock->init_done = 1;
 247         }
 248
 249         switch(ap->a_op) {
 250         case F_SETLK:
 251                 /*
 252                  * NOTE: It is possible for both lf_range and lf_blocked to
 253                  * be empty if we block and get woken up, but another process
 254                  * then gets in and issues an unlock.  So VMAYHAVELOCKS must
 255                  * be set after the lf_setlock() operation completes rather
 256                  * then before.
 257                  */
 258                 error = lf_setlock(lock, owner, type, flags, start, end);
 259                 vsetflags(ap->a_vp, VMAYHAVELOCKS);
 260                 break;
 261
 262         case F_UNLCK:
 263                 error = lf_setlock(lock, owner, type, flags, start, end);
 264                 if (TAILQ_EMPTY(&lock->lf_range) &&
 265                     TAILQ_EMPTY(&lock->lf_blocked)) {
 266                         vclrflags(ap->a_vp, VMAYHAVELOCKS);
 267                 }
 268                 break;
 269
 270         case F_GETLK:
 271                 error = lf_getlock(fl, lock, owner, type, flags, start, end);
 272                 break;
 273
 274         default:
 275                 error = EINVAL;
 276                 break;
 277         }
 278         lwkt_reltoken(token);
 279         return(error);
 280 }
 281
 282 static int
 283 lf_setlock(struct lockf *lock, struct proc *owner, int type, int flags,
 284            off_t start, off_t end)
 285 {
 286         struct lockf_range *range;
 287         struct lockf_range *brange;
 288         struct lockf_range *next;
 289         struct lockf_range *first_match;
 290         struct lockf_range *last_match;
 291         struct lockf_range *insert_point;
 292         struct lockf_range *new_range1;
 293         struct lockf_range *new_range2;
 294         int wakeup_needed;
 295         int double_clip;
 296         int unlock_override;
 297         int error = 0;
 298         int count;
 299         struct lockf_range_list deadlist;
 300
 301         new_range1 = NULL;
 302         new_range2 = NULL;
 303         count = 0;
 304
 305 restart:
 306         /*
 307          * Preallocate two ranges so we don't have to worry about blocking
 308          * in the middle of the lock code.
 309          */
 310         if (new_range1 == NULL)
 311                 new_range1 = lf_alloc_range();
 312         if (new_range2 == NULL)
 313                 new_range2 = lf_alloc_range();
 314         first_match = NULL;
 315         last_match = NULL;
 316         insert_point = NULL;
 317         wakeup_needed = 0;
 318
 319         lf_print_lock(lock);
 320
 321         /*
 322          * Locate the insertion point for the new lock (the first range
 323          * with an lf_start >= start).
 324          *
 325          * Locate the first and latch ranges owned by us that overlap
 326          * the requested range.
 327          */
 328         TAILQ_FOREACH(range, &lock->lf_range, lf_link) {
 329                 if (insert_point == NULL && range->lf_start >= start)
 330                         insert_point = range;
 331
 332                 /*
 333                  * Skip non-overlapping locks.  Locks are sorted by lf_start
 334                  * So we can terminate the search when lf_start exceeds the
 335                  * requested range (insert_point is still guarenteed to be
 336                  * set properly).
 337                  */
 338                 if (range->lf_end < start)
 339                         continue;
 340                 if (range->lf_start > end) {
 341                         range = NULL;
 342                         break;
 343                 }
 344
 345                 /*
 346                  * Overlapping lock.  Set first_match and last_match if we
 347                  * are the owner.
 348                  */
 349                 if (range->lf_owner == owner) {
 350                         if (first_match == NULL)
 351                                 first_match = range;
 352                         last_match = range;
 353                         continue;
 354                 }
 355
 356                 /*
 357                  * If we aren't the owner check for a conflicting lock.  Only
 358                  * if not unlocking.
 359                  */
 360                 if (type != F_UNLCK) {
 361                         if (type == F_WRLCK || range->lf_type == F_WRLCK)
 362                                 break;
 363                 }
 364         }
 365
 366         /*
 367          * If a conflicting lock was observed, block or fail as appropriate.
 368          * (this code is skipped when unlocking)
 369          */
 370         if (range != NULL) {
 371                 if ((flags & F_WAIT) == 0) {
 372                         error = EAGAIN;
 373                         goto do_cleanup;
 374                 }
 375
 376                 /*
 377                  * We are blocked. For POSIX locks we have to check
 378                  * for deadlocks and return with EDEADLK. This is done
 379                  * by checking whether range->lf_owner is already
 380                  * blocked.
 381                  *
 382                  * Since flock-style locks cover the whole file, a
 383                  * deadlock between those is nearly impossible.
 384                  * This can only occur if a process tries to lock the
 385                  * same inode exclusively while holding a shared lock
 386                  * with another descriptor.
 387                  * XXX How can we cleanly detect this?
 388                  * XXX The current mixing of flock & fcntl/lockf is evil.
 389                  *
 390                  * Handle existing locks of flock-style like POSIX locks.
 391                  */
 392                 if (flags & F_POSIX) {
 393                         TAILQ_FOREACH(brange, &lock->lf_blocked, lf_link) {
 394                                 if (brange->lf_owner == range->lf_owner) {
 395                                         error = EDEADLK;
 396                                         goto do_cleanup;
 397                                 }
 398                         }
 399                 }
 400
 401                 /*
 402                  * For flock-style locks, we must first remove
 403                  * any shared locks that we hold before we sleep
 404                  * waiting for an exclusive lock.
 405                  */
 406                 if ((flags & F_POSIX) == 0 && type == F_WRLCK)
 407                         lf_setlock(lock, owner, F_UNLCK, 0, start, end);
 408
 409                 brange = new_range1;
 410                 new_range1 = NULL;
 411                 lf_create_range(brange, owner, type, 0, start, end);
 412                 TAILQ_INSERT_TAIL(&lock->lf_blocked, brange, lf_link);
 413                 error = tsleep(brange, PCATCH, "lockf", 0);
 414
 415                 /*
 416                  * We may have been awaked by a signal and/or by a
 417                  * debugger continuing us (in which case we must remove
 418                  * ourselves from the blocked list) and/or by another
 419                  * process releasing/downgrading a lock (in which case
 420                  * we have already been removed from the blocked list
 421                  * and our lf_flags field is 1).
 422                  *
 423                  * Sleep if it looks like we might be livelocking.
 424                  */
 425                 if (brange->lf_flags == 0)
 426                         TAILQ_REMOVE(&lock->lf_blocked, brange, lf_link);
 427                 if (count == 2)
 428                         tsleep(brange, 0, "lockfz", 2);
 429                 else
 430                         ++count;
 431                 lf_destroy_range(brange);
 432
 433                 if (error)
 434                         goto do_cleanup;
 435                 goto restart;
 436         }
 437
 438         /*
 439          * If there are no overlapping locks owned by us then creating
 440          * the new lock is easy.  This is the most common case.
 441          */
 442         if (first_match == NULL) {
 443                 if (type == F_UNLCK)
 444                         goto do_wakeup;
 445                 if (flags & F_POSIX) {
 446                         if (lf_count_change(owner, 1)) {
 447                                 error = ENOLCK;
 448                                 goto do_cleanup;
 449                         }
 450                 }
 451                 range = new_range1;
 452                 new_range1 = NULL;
 453                 lf_create_range(range, owner, type, flags, start, end);
 454                 lf_insert(&lock->lf_range, range, insert_point);
 455                 goto do_wakeup;
 456         }
 457
 458         /*
 459          * double_clip - Calculate a special case where TWO locks may have
 460          *               to be added due to the new lock breaking up an
 461          *               existing incompatible lock in the middle.
 462          *
 463          * unlock_override - Calculate a special case where NO locks
 464          *               need to be created.  This occurs when an unlock
 465          *               does not clip any locks at the front and rear.
 466          *
 467          * WARNING!  closef() and fdrop() assume that an F_UNLCK of the
 468          *           entire range will always succeed so the unlock_override
 469          *           case is mandatory.
 470          */
 471         double_clip = 0;
 472         unlock_override = 0;
 473         if (first_match->lf_start < start) {
 474                 if (first_match == last_match && last_match->lf_end > end)
 475                         double_clip = 1;
 476         } else if (type == F_UNLCK && last_match->lf_end <= end) {
 477                 unlock_override = 1;
 478         }
 479
 480         /*
 481          * Figure out the worst case net increase in POSIX locks and account
 482          * for it now before we start modifying things.  If neither the
 483          * first or last locks match we have an issue.  If there is only
 484          * one overlapping range which needs to be clipped on both ends
 485          * we wind up having to create up to two new locks, else only one.
 486          *
 487          * When unlocking the worst case is always 1 new lock if our
 488          * unlock request cuts the middle out of an existing lock range.
 489          *
 490          * count represents the 'cleanup' adjustment needed.  It starts
 491          * negative, is incremented whenever we create a new POSIX lock,
 492          * and decremented whenever we delete an existing one.  At the
 493          * end of the day it had better be <= 0 or we didn't calculate the
 494          * worse case properly here.
 495          */
 496         count = 0;
 497         if ((flags & F_POSIX) && !unlock_override) {
 498                 if (!lf_match(first_match, type, flags) &&
 499                     !lf_match(last_match, type, flags)
 500                 ) {
 501                         if (double_clip && type != F_UNLCK)
 502                                 count = -2;
 503                         else
 504                                 count = -1;
 505                 }
 506                 if (count && lf_count_change(owner, -count)) {
 507                         error = ENOLCK;
 508                         goto do_cleanup;
 509                 }
 510         }
 511         /* else flock style lock which encompasses entire range */
 512
 513         /*
 514          * Create and insert the lock represented the requested range.
 515          * Adjust the net POSIX lock count.  We have to move our insertion
 516          * point since brange now represents the first record >= start.
 517          *
 518          * When unlocking, no new lock is inserted but we still clip.
 519          */
 520         if (type != F_UNLCK) {
 521                 brange = new_range1;
 522                 new_range1 = NULL;
 523                 lf_create_range(brange, owner, type, flags, start, end);
 524                 lf_insert(&lock->lf_range, brange, insert_point);
 525                 insert_point = brange;
 526                 if (flags & F_POSIX)
 527                         ++count;
 528         } else {
 529                 brange = NULL;
 530         }
 531
 532         /*
 533          * Handle the double_clip case.  This is the only case where
 534          * we wind up having to add TWO locks.
 535          */
 536         if (double_clip) {
 537                 KKASSERT(first_match == last_match);
 538                 last_match = new_range2;
 539                 new_range2 = NULL;
 540                 lf_create_range(last_match, first_match->lf_owner,
 541                                 first_match->lf_type, first_match->lf_flags,
 542                                 end + 1, first_match->lf_end);
 543                 first_match->lf_end = start - 1;
 544                 first_match->lf_flags &= ~F_NOEND;
 545
 546                 /*
 547                  * Figure out where to insert the right side clip.
 548                  */
 549                 lf_insert(&lock->lf_range, last_match, first_match);
 550                 if (last_match->lf_flags & F_POSIX)
 551                         ++count;
 552         }
 553
 554         /*
 555          * Clip or destroy the locks between first_match and last_match,
 556          * inclusive.  Ignore the primary lock we created (brange).  Note
 557          * that if double-clipped, first_match and last_match will be
 558          * outside our clipping range.  Otherwise first_match and last_match
 559          * will be deleted.
 560          *
 561          * We have already taken care of any double clipping.
 562          *
 563          * The insert_point may become invalid as we delete records, do not
 564          * use that pointer any more.  Also, when removing something other
 565          * then 'range' we have to check to see if the item we are removing
 566          * is 'next' and adjust 'next' properly.
 567          *
 568          * NOTE: brange will be NULL if F_UNLCKing.
 569          */
 570         TAILQ_INIT(&deadlist);
 571         next = first_match;
 572
 573         while ((range = next) != NULL) {
 574                 next = TAILQ_NEXT(range, lf_link);
 575
 576                 /*
 577                  * Ignore elements that we do not own and ignore the
 578                  * primary request range which we just created.
 579                  */
 580                 if (range->lf_owner != owner || range == brange)
 581                         continue;
 582
 583                 /*
 584                  * We may have to wakeup a waiter when downgrading a lock.
 585                  */
 586                 if (type == F_UNLCK)
 587                         wakeup_needed = 1;
 588                 if (type == F_RDLCK && range->lf_type == F_WRLCK)
 589                         wakeup_needed = 1;
 590
 591                 /*
 592                  * Clip left.  This can only occur on first_match.
 593                  *
 594                  * Merge the left clip with brange if possible.  This must
 595                  * be done specifically, not in the optimized merge heuristic
 596                  * below, since we may have counted on it in our 'count'
 597                  * calculation above.
 598                  */
 599                 if (range->lf_start < start) {
 600                         KKASSERT(range == first_match);
 601                         if (brange &&
 602                             range->lf_end >= start - 1 &&
 603                             lf_match(range, type, flags)) {
 604                                 range->lf_end = brange->lf_end;
 605                                 range->lf_flags |= brange->lf_flags & F_NOEND;
 606                                 /*
 607                                  * Removing something other then 'range',
 608                                  * adjust 'next' if necessary.
 609                                  */
 610                                 if (next == brange)
 611                                         next = TAILQ_NEXT(next, lf_link);
 612                                 TAILQ_REMOVE(&lock->lf_range, brange, lf_link);
 613                                 if (brange->lf_flags & F_POSIX)
 614                                         --count;
 615                                 TAILQ_INSERT_TAIL(&deadlist, brange, lf_link);
 616                                 brange = range;
 617                         } else if (range->lf_end >= start) {
 618                                 range->lf_end = start - 1;
 619                                 if (type != F_UNLCK)
 620                                         range->lf_flags &= ~F_NOEND;
 621                         }
 622                         if (range == last_match)
 623                                 break;
 624                         continue;
 625                 }
 626
 627                 /*
 628                  * Clip right.  This can only occur on last_match.
 629                  *
 630                  * Merge the right clip if possible.  This must be done
 631                  * specifically, not in the optimized merge heuristic
 632                  * below, since we may have counted on it in our 'count'
 633                  * calculation.
 634                  *
 635                  * Since we are adjusting lf_start, we have to move the
 636                  * record to maintain the sorted list.  Since lf_start is
 637                  * only getting larger we can use the next element as the
 638                  * insert point (we don't have to backtrack).
 639                  */
 640                 if (range->lf_end > end) {
 641                         KKASSERT(range == last_match);
 642                         if (brange &&
 643                             range->lf_start <= end + 1 &&
 644                             lf_match(range, type, flags)) {
 645                                 brange->lf_end = range->lf_end;
 646                                 brange->lf_flags |= range->lf_flags & F_NOEND;
 647                                 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 648                                 if (range->lf_flags & F_POSIX)
 649                                         --count;
 650                                 TAILQ_INSERT_TAIL(&deadlist, range, lf_link);
 651                         } else if (range->lf_start <= end) {
 652                                 range->lf_start = end + 1;
 653                                 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 654                                 lf_insert(&lock->lf_range, range, next);
 655                         }
 656                         /* range == last_match, we are done */
 657                         break;
 658                 }
 659
 660                 /*
 661                  * The record must be entirely enclosed.  Note that the
 662                  * record could be first_match or last_match, and will be
 663                  * deleted.
 664                  */
 665                 KKASSERT(range->lf_start >= start && range->lf_end <= end);
 666                 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 667                 if (range->lf_flags & F_POSIX)
 668                         --count;
 669                 TAILQ_INSERT_TAIL(&deadlist, range, lf_link);
 670                 if (range == last_match)
 671                         break;
 672         }
 673
 674         /*
 675          * Attempt to merge locks adjacent to brange.  For example, we may
 676          * have had to clip first_match and/or last_match, and they might
 677          * be adjacent.  Or there might simply have been an adjacent lock
 678          * already there.
 679          *
 680          * Don't get fancy, just check adjacent elements in the list if they
 681          * happen to be owned by us.
 682          *
 683          * This case only gets hit if we have a situation where a shared
 684          * and exclusive lock are adjacent, and the exclusive lock is
 685          * downgraded to shared or the shared lock is upgraded to exclusive.
 686          */
 687         if (brange) {
 688                 range = TAILQ_PREV(brange, lockf_range_list, lf_link);
 689                 if (range &&
 690                     range->lf_owner == owner &&
 691                     range->lf_end == brange->lf_start - 1 &&
 692                     lf_match(range, type, flags)
 693                 ) {
 694                         /*
 695                          * Extend range to cover brange and scrap brange.
 696                          */
 697                         range->lf_end = brange->lf_end;
 698                         range->lf_flags |= brange->lf_flags & F_NOEND;
 699                         TAILQ_REMOVE(&lock->lf_range, brange, lf_link);
 700                         if (brange->lf_flags & F_POSIX)
 701                                 --count;
 702                         TAILQ_INSERT_TAIL(&deadlist, brange, lf_link);
 703                         brange = range;
 704                 }
 705                 range = TAILQ_NEXT(brange, lf_link);
 706                 if (range &&
 707                     range->lf_owner == owner &&
 708                     range->lf_start == brange->lf_end + 1 &&
 709                     lf_match(range, type, flags)
 710                 ) {
 711                         /*
 712                          * Extend brange to cover range and scrap range.
 713                          */
 714                         brange->lf_end = range->lf_end;
 715                         brange->lf_flags |= range->lf_flags & F_NOEND;
 716                         TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 717                         if (range->lf_flags & F_POSIX)
 718                                 --count;
 719                         TAILQ_INSERT_TAIL(&deadlist, range, lf_link);
 720                 }
 721         }
 722
 723         /*
 724          * Destroy deleted elements.  We didn't want to do it in the loop
 725          * because the free() might have blocked.
 726          *
 727          * Adjust the count for any posix locks we thought we might create
 728          * but didn't.
 729          */
 730         while ((range = TAILQ_FIRST(&deadlist)) != NULL) {
 731                 TAILQ_REMOVE(&deadlist, range, lf_link);
 732                 lf_destroy_range(range);
 733         }
 734
 735         KKASSERT(count <= 0);
 736         if (count < 0)
 737                 lf_count_change(owner, count);
 738 do_wakeup:
 739         lf_print_lock(lock);
 740         if (wakeup_needed)
 741                 lf_wakeup(lock, start, end);
 742         error = 0;
 743 do_cleanup:
 744         if (new_range1 != NULL)
 745                 lf_destroy_range(new_range1);
 746         if (new_range2 != NULL)
 747                 lf_destroy_range(new_range2);
 748         return(error);
 749 }
 750
 751 /*
 752  * Check whether there is a blocking lock,
 753  * and if so return its process identifier.
 754  */
 755 static int
 756 lf_getlock(struct flock *fl, struct lockf *lock, struct proc *owner,
 757            int type, int flags, off_t start, off_t end)
 758 {
 759         struct lockf_range *range;
 760
 761         TAILQ_FOREACH(range, &lock->lf_range, lf_link)
 762                 if (range->lf_owner != owner &&
 763                     lf_overlap(range, start, end) &&
 764                     (type == F_WRLCK || range->lf_type == F_WRLCK))
 765                         break;
 766         if (range == NULL) {
 767                 fl->l_type = F_UNLCK;
 768                 return(0);
 769         }
 770         fl->l_type = range->lf_type;
 771         fl->l_whence = SEEK_SET;
 772         fl->l_start = range->lf_start;
 773         if (range->lf_flags & F_NOEND)
 774                 fl->l_len = 0;
 775         else
 776                 fl->l_len = range->lf_end - range->lf_start + 1;
 777         if (range->lf_owner != NULL && (range->lf_flags & F_POSIX))
 778                 fl->l_pid = range->lf_owner->p_pid;
 779         else
 780                 fl->l_pid = -1;
 781         return(0);
 782 }
 783
 784 /*
 785  * Wakeup pending lock attempts.  Theoretically we can stop as soon as
 786  * we encounter an exclusive request that covers the whole range (at least
 787  * insofar as the sleep code above calls lf_wakeup() if it would otherwise
 788  * exit instead of loop), but for now just wakeup all overlapping
 789  * requests.  XXX
 790  */
 791 static void
 792 lf_wakeup(struct lockf *lock, off_t start, off_t end)
 793 {
 794         struct lockf_range *range, *nrange;
 795
 796         TAILQ_FOREACH_MUTABLE(range, &lock->lf_blocked, lf_link, nrange) {
 797                 if (lf_overlap(range, start, end) == 0)
 798                         continue;
 799                 TAILQ_REMOVE(&lock->lf_blocked, range, lf_link);
 800                 range->lf_flags = 1;
 801                 wakeup(range);
 802         }
 803 }
 804
 805 /*
 806  * Allocate a range structure and initialize it sufficiently such that
 807  * lf_destroy_range() does not barf.
 808  */
 809 static struct lockf_range *
 810 lf_alloc_range(void)
 811 {
 812         struct lockf_range *range;
 813
 814 #ifdef INVARIANTS
 815         atomic_add_int(&lf_global_counter, 1);
 816 #endif
 817         range = kmalloc(sizeof(struct lockf_range), M_LOCKF, M_WAITOK);
 818         range->lf_owner = NULL;
 819         return(range);
 820 }
 821
 822 static void
 823 lf_insert(struct lockf_range_list *list, struct lockf_range *elm,
 824           struct lockf_range *insert_point)
 825 {
 826         while (insert_point && insert_point->lf_start < elm->lf_start)
 827                 insert_point = TAILQ_NEXT(insert_point, lf_link);
 828         if (insert_point != NULL)
 829                 TAILQ_INSERT_BEFORE(insert_point, elm, lf_link);
 830         else
 831                 TAILQ_INSERT_TAIL(list, elm, lf_link);
 832 }
 833
 834 static void
 835 lf_create_range(struct lockf_range *range, struct proc *owner, int type,
 836                 int flags, off_t start, off_t end)
 837 {
 838         KKASSERT(start <= end);
 839         range->lf_type = type;
 840         range->lf_flags = flags;
 841         range->lf_start = start;
 842         range->lf_end = end;
 843         range->lf_owner = owner;
 844
 845         lf_printf("lf_create_range: %lld..%lld\n",
 846                         range->lf_start, range->lf_end);
 847 }
 848
 849 static void
 850 lf_destroy_range(struct lockf_range *range)
 851 {
 852         lf_printf("lf_destroy_range: %lld..%lld\n",
 853                   range->lf_start, range->lf_end);
 854         kfree(range, M_LOCKF);
 855 #ifdef INVARIANTS
 856         atomic_add_int(&lf_global_counter, -1);
 857         KKASSERT(lf_global_counter >= 0);
 858 #endif
 859 }
 860
 861 #ifdef LOCKF_DEBUG
 862
 863 static void
 864 _lf_printf(const char *ctl, ...)
 865 {
 866         struct proc *p;
 867         __va_list va;
 868
 869         if (lf_print_ranges) {
 870             if ((p = curproc) != NULL)
 871                 kprintf("pid %d (%s): ", p->p_pid, p->p_comm);
 872         }
 873         __va_start(va, ctl);
 874         kvprintf(ctl, va);
 875         __va_end(va);
 876 }
 877
 878 static void
 879 _lf_print_lock(const struct lockf *lock)
 880 {
 881         struct lockf_range *range;
 882
 883         if (lf_print_ranges == 0)
 884                 return;
 885
 886         if (TAILQ_EMPTY(&lock->lf_range)) {
 887                 lf_printf("lockf %p: no ranges locked\n", lock);
 888         } else {
 889                 lf_printf("lockf %p:\n", lock);
 890         }
 891         TAILQ_FOREACH(range, &lock->lf_range, lf_link)
 892                 kprintf("\t%lld..%lld type %s owned by %d\n",
 893                        range->lf_start, range->lf_end,
 894                        range->lf_type == F_RDLCK ? "shared" : "exclusive",
 895                        range->lf_flags & F_POSIX ? range->lf_owner->p_pid : -1);
 896         if (TAILQ_EMPTY(&lock->lf_blocked))
 897                 kprintf("no process waiting for range\n");
 898         else
 899                 kprintf("blocked locks:");
 900         TAILQ_FOREACH(range, &lock->lf_blocked, lf_link)
 901                 kprintf("\t%lld..%lld type %s waiting on %p\n",
 902                        range->lf_start, range->lf_end,
 903                        range->lf_type == F_RDLCK ? "shared" : "exclusive",
 904                        range);
 905 }
 906 #endif /* LOCKF_DEBUG */