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