sys/kern/kern_lockf.c

   1 /*
   2  * Copyright (c) 2004 Joerg Sonnenberger <joerg@bec.de>
   3  *
   4  * Copyright (c) 1982, 1986, 1989, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Scooter Morris at Genentech Inc.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  *
  38  *      @(#)ufs_lockf.c 8.3 (Berkeley) 1/6/94
  39  * $FreeBSD: src/sys/kern/kern_lockf.c,v 1.25 1999/11/16 16:28:56 phk Exp $
  40  * $DragonFly: src/sys/kern/kern_lockf.c,v 1.8 2004/05/04 17:00:55 joerg Exp $
  41  */
  42
  43 #include <sys/param.h>
  44 #include <sys/systm.h>
  45 #include <sys/kernel.h>
  46 #include <sys/lock.h>
  47 #include <sys/proc.h>
  48 #include <sys/unistd.h>
  49 #include <sys/vnode.h>
  50 #include <sys/malloc.h>
  51 #include <sys/fcntl.h>
  52 #include <sys/resourcevar.h>
  53
  54 #include <sys/lockf.h>
  55 #include <machine/limits.h>     /* for LLONG_MAX */
  56
  57 #ifdef INVARIANTS
  58 int lf_global_counter = 0;
  59 #endif
  60 #ifdef LOCKF_DEBUG
  61 int lf_print_ranges = 0;
  62
  63 static void     lf_print_lock(const struct lockf *);
  64 #endif
  65
  66 static MALLOC_DEFINE(M_LOCKF, "lockf", "Byte-range locking structures");
  67
  68 static void     lf_wakeup(struct lockf *, off_t, off_t);
  69 static int      lf_overlap(const struct lockf_range *, off_t, off_t);
  70 static int      lf_overlap_left(const struct lockf_range *, off_t, off_t);
  71 static int      lf_overlap_right(const struct lockf_range *, off_t, off_t);
  72 static int      lf_overlap_left2(const struct lockf_range *, off_t, off_t);
  73 static int      lf_overlap_right2(const struct lockf_range *, off_t, off_t);
  74 static int      lf_overlap_embedded(const struct lockf_range *, off_t, off_t);
  75 static struct lockf_range *lf_alloc_range(void);
  76 static void     lf_create_range(struct lockf_range *, struct proc *, int, int,
  77                                 off_t, off_t, int);
  78 static void     lf_destroy_range(struct lockf_range *, int);
  79
  80 static int      lf_setlock(struct lockf *, struct proc *, int, int,
  81                            off_t, off_t);
  82 static int      lf_clearlock(struct lockf *, struct proc *, int, int,
  83                              off_t, off_t);
  84 static int      lf_getlock(struct flock *, struct lockf *, struct proc *,
  85                            int, int, off_t, off_t);
  86
  87 static int      lf_count_change(struct proc *, int);
  88
  89 /*
  90  * Change the POSIX lock accounting for the given process.
  91  */
  92 void
  93 lf_count_adjust(struct proc *p, struct uidinfo *newowner)
  94 {
  95         struct uidinfo *uip;
  96
  97         KKASSERT(p != NULL);
  98
  99         uip = p->p_ucred->cr_uidinfo;
 100
 101         newowner->ui_posixlocks += p->p_numposixlocks;
 102         uip->ui_posixlocks -= p->p_numposixlocks;
 103
 104         KASSERT(uip->ui_posixlocks >= 0,
 105                 ("Negative number of POSIX locks held by old user: %d.",
 106                  uip->ui_posixlocks));
 107         KASSERT(newowner->ui_posixlocks >= 0,
 108                 ("Negative number of POSIX locks held by new user: %d.",
 109                  newowner->ui_posixlocks));
 110 }
 111
 112 static int
 113 lf_count_change(struct proc *owner, int diff)
 114 {
 115         struct uidinfo *uip;
 116         int max;
 117
 118         /* we might actually not have a process context */
 119         if (owner == NULL)
 120                 return(0);
 121
 122         uip = owner->p_ucred->cr_uidinfo;
 123
 124         max = MIN(owner->p_rlimit[RLIMIT_POSIXLOCKS].rlim_cur,
 125                   maxposixlocksperuid);
 126         if (diff > 0 && owner->p_ucred->cr_uid != 0 && max != -1 &&
 127             uip->ui_posixlocks >= max )
 128                 return(1);
 129
 130         uip->ui_posixlocks += diff;
 131
 132         KASSERT(uip->ui_posixlocks >= 0,
 133                 ("Negative number of POSIX locks held by user: %d.",
 134                  uip->ui_posixlocks));
 135
 136         return(0);
 137 }
 138
 139 /*
 140  * Advisory record locking support
 141  */
 142 int
 143 lf_advlock(struct vop_advlock_args *ap, struct lockf *lock, u_quad_t size)
 144 {
 145         struct flock *fl = ap->a_fl;
 146         struct proc *owner;
 147         off_t start, end;
 148         int type, flags;
 149
 150         if (lock->init_done == 0) {
 151                 TAILQ_INIT(&lock->lf_range);
 152                 TAILQ_INIT(&lock->lf_blocked);
 153                 lock->init_done = 1;
 154         }
 155
 156         /*
 157          * Convert the flock structure into a start and end.
 158          */
 159         switch (fl->l_whence) {
 160         case SEEK_SET:
 161         case SEEK_CUR:
 162                 /*
 163                  * Caller is responsible for adding any necessary offset
 164                  * when SEEK_CUR is used.
 165                  */
 166                 start = fl->l_start;
 167                 break;
 168
 169         case SEEK_END:
 170                 start = size + fl->l_start;
 171                 break;
 172
 173         default:
 174                 return(EINVAL);
 175         }
 176         if (start < 0)
 177                 return(EINVAL);
 178         if (fl->l_len == 0) {
 179                 flags |= F_NOEND;
 180                 end = LLONG_MAX;
 181         } else {
 182                 end = start + fl->l_len - 1;
 183                 if (end < start)
 184                         return(EINVAL);
 185         }
 186
 187         flags = ap->a_flags;
 188         type = fl->l_type;
 189         /*
 190          * This isn't really correct for flock-style locks,
 191          * but the current handling is somewhat broken anyway.
 192          */
 193         owner = (struct proc *)ap->a_id;
 194
 195         /*
 196          * Do the requested operation.
 197          */
 198         switch(ap->a_op) {
 199         case F_SETLK:
 200                 return(lf_setlock(lock, owner, type, flags, start, end));
 201
 202         case F_UNLCK:
 203                 return(lf_clearlock(lock, owner, type, flags, start, end));
 204
 205         case F_GETLK:
 206                 return(lf_getlock(fl, lock, owner, type, flags, start, end));
 207
 208         default:
 209                 return (EINVAL);
 210         }
 211         /* NOTREACHED */
 212 }
 213
 214 static int
 215 lf_setlock(struct lockf *lock, struct proc *owner, int type, int flags,
 216            off_t start, off_t end)
 217 {
 218         struct lockf_range *range, *first_match, *insert_point;
 219         int wakeup_needed, lock_needed;
 220         /* pre-allocation to avoid blocking in the middle of the algorithm */
 221         struct lockf_range *new_range1 = NULL, *new_range2 = NULL;
 222         int error = 0;
 223
 224         /* for restauration in case of hitting the POSIX lock limit below */
 225         struct lockf_range *orig_first_match = NULL;
 226         off_t orig_end = -1;
 227         int orig_flags = 0;
 228
 229 restart:
 230         if (new_range1 == NULL)
 231                 new_range1 = lf_alloc_range();
 232         if (new_range2 == NULL)
 233                 new_range2 = lf_alloc_range();
 234         first_match = NULL;
 235         insert_point = NULL;
 236         wakeup_needed = 0;
 237
 238 #ifdef LOCKF_DEBUG
 239         if (lf_print_ranges)
 240                 lf_print_lock(lock);
 241 #endif
 242
 243         TAILQ_FOREACH(range, &lock->lf_range, lf_link) {
 244                 if (insert_point == NULL && range->lf_start >= start)
 245                         insert_point = range;
 246                 if (lf_overlap(range, start, end) == 0)
 247                         continue;
 248                 if (range->lf_owner == owner) {
 249                         if (first_match == NULL)
 250                                 first_match = range;
 251                         continue;
 252                 }
 253                 if (type == F_WRLCK || range->lf_type == F_WRLCK)
 254                         break;
 255         }
 256
 257         if (range != NULL) {
 258                 struct lockf_range *brange;
 259                 int error;
 260
 261                 if ((flags & F_WAIT) == 0) {
 262                         error = EAGAIN;
 263                         goto do_cleanup;
 264                 }
 265
 266                 /*
 267                  * We are blocked. For POSIX locks we have to check
 268                  * for deadlocks and return with EDEADLK. This is done
 269                  * by checking wether range->lf_owner is already
 270                  * blocked.
 271                  *
 272                  * Since flock-style locks cover the whole file, a
 273                  * deadlock between those is nearly impossible.
 274                  * This can only occur if a process tries to lock the
 275                  * same inode exclusively while holding a shared lock
 276                  * with another descriptor.
 277                  * XXX How can we cleanly detect this?
 278                  * XXX The current mixing of flock & fcntl/lockf is evil.
 279                  *
 280                  * Handle existing locks of flock-style like POSIX locks.
 281                  */
 282                 if (flags & F_POSIX) {
 283                         TAILQ_FOREACH(brange, &lock->lf_blocked, lf_link)
 284                                 if (brange->lf_owner == range->lf_owner) {
 285                                         error = EDEADLK;
 286                                         goto do_cleanup;
 287                                 }
 288                 }
 289
 290                 /*
 291                  * For flock-style locks, we must first remove
 292                  * any shared locks that we hold before we sleep
 293                  * waiting for an exclusive lock.
 294                  */
 295                 if ((flags & F_FLOCK) && type == F_WRLCK)
 296                         lf_clearlock(lock, owner, type, flags, start, end);
 297
 298                 brange = new_range1;
 299                 new_range1 = NULL;
 300                 lf_create_range(brange, owner, type, 0, start, end, 0);
 301                 TAILQ_INSERT_TAIL(&lock->lf_blocked, brange, lf_link);
 302                 error = tsleep(brange, PCATCH, "lockf", 0);
 303
 304                 /*
 305                  * We may have been awaked by a signal and/or by a
 306                  * debugger continuing us (in which case we must remove
 307                  * ourselves from the blocked list) and/or by another
 308                  * process releasing/downgrading a lock (in which case
 309                  * we have already been removed from the blocked list
 310                  * and our lf_flags field is 1).
 311                  */
 312                 if (brange->lf_flags == 0)
 313                         TAILQ_REMOVE(&lock->lf_blocked, brange, lf_link);
 314                 lf_destroy_range(brange, 0);
 315
 316                 if (error)
 317                         goto do_cleanup;
 318                 goto restart;
 319         }
 320
 321         if (first_match == NULL) {
 322                 if (flags & F_POSIX) {
 323                         if (lf_count_change(owner, 1)) {
 324                                 error = ENOLCK;
 325                                 goto do_cleanup;
 326                         }
 327                 }
 328                 range = new_range1;
 329                 new_range1 = NULL;
 330                 lf_create_range(range, owner, type, flags, start, end, 1);
 331                 if (insert_point != NULL)
 332                         TAILQ_INSERT_BEFORE(insert_point, range, lf_link);
 333                 else
 334                         TAILQ_INSERT_TAIL(&lock->lf_range, range, lf_link);
 335                 goto do_wakeup;
 336         }
 337
 338         lock_needed = 1;
 339
 340         if (lf_overlap_left(first_match, start, end)) {
 341                 KKASSERT((flags & F_POSIX) != 0);
 342                 if (first_match->lf_end > end) {
 343                         if (first_match->lf_type == type)
 344                                 goto do_wakeup;
 345                         if (lf_count_change(owner, 2)) {
 346                                 error = ENOLCK;
 347                                 goto do_cleanup;
 348                         }
 349                         range = new_range1;
 350                         new_range1 = NULL;
 351                         lf_create_range(range, owner, type, flags,
 352                                         start, end, 1);
 353                         if (insert_point != NULL)
 354                                 TAILQ_INSERT_BEFORE(insert_point, range,
 355                                                     lf_link);
 356                         else
 357                                 TAILQ_INSERT_TAIL(&lock->lf_range, range,
 358                                                   lf_link);
 359                         insert_point = range;
 360                         range = new_range2;
 361                         new_range2 = NULL;
 362                         lf_create_range(range, owner, first_match->lf_type,
 363                                         first_match->lf_flags, end + 1,
 364                                         first_match->lf_end, 1);
 365                         TAILQ_INSERT_AFTER(&lock->lf_range, insert_point,
 366                                            range, lf_link);
 367                         first_match->lf_flags &= ~F_NOEND;
 368                         first_match->lf_end = start - 1;
 369                         if (type == F_RDLCK)
 370                                 wakeup_needed = 1;
 371                         goto do_wakeup;
 372                 }
 373                 /*
 374                  * left match, but not right match
 375                  *
 376                  * handle the lf_type != type case directly,
 377                  * merge the other case with the !lock_needed path.
 378                  */
 379                 if (first_match->lf_type != type) {
 380                         /*
 381                          * This is needed if the lockf acquisition below fails.
 382                          */
 383                         orig_first_match = first_match;
 384                         orig_end = first_match->lf_end;
 385                         orig_flags = first_match->lf_flags;
 386                         first_match->lf_end = start - 1;
 387                         first_match->lf_flags &= ~F_NOEND;
 388                         if (type == F_RDLCK)
 389                                 wakeup_needed = 1;
 390                         /* Try to find the next matching range */
 391                         range = TAILQ_NEXT(first_match, lf_link);
 392                         while (range != NULL) {
 393                                 if (range->lf_owner == owner &&
 394                                     lf_overlap(range, start, end))
 395                                         break;
 396                                 range = TAILQ_NEXT(range, lf_link);
 397                         }
 398                         if (range == NULL)
 399                                 goto do_wakeup;
 400                         first_match = range;
 401                         /* fall through to !left_match behaviour */
 402                 } else {
 403                         first_match->lf_end = end;
 404                         first_match->lf_flags |= flags & F_NOEND;
 405                         lock_needed = 0;
 406                 }
 407         }
 408
 409         if (lf_overlap_embedded(first_match, start, end)) {
 410                 if (first_match != insert_point) {
 411                         TAILQ_REMOVE(&lock->lf_range, first_match, lf_link);
 412                         TAILQ_INSERT_BEFORE(insert_point, first_match, lf_link);
 413                 }
 414                 first_match->lf_start = start;
 415                 first_match->lf_end = end;
 416                 first_match->lf_flags |= flags & F_NOEND;
 417                 lock_needed = 0;
 418         }
 419
 420         if (lock_needed == 0) {
 421                 struct lockf_range *nrange;
 422
 423                 range = TAILQ_NEXT(first_match, lf_link);
 424                 while (range != NULL) {
 425                         if (range->lf_owner != owner) {
 426                                 range = TAILQ_NEXT(range, lf_link);
 427                                 continue;
 428                         }
 429                         if (lf_overlap_embedded(range, start, end)) {
 430                                 nrange = TAILQ_NEXT(range, lf_link);
 431                                 TAILQ_REMOVE(&lock->lf_range, range,
 432                                              lf_link);
 433                                 lf_count_change(owner, -1);
 434                                 lf_destroy_range(range, 1);
 435                                 range = nrange;
 436                                 continue;
 437                         }
 438                         if (lf_overlap_right(range, start, end) == 0) {
 439                                 range = TAILQ_NEXT(range, lf_link);
 440                                 continue;
 441                         }
 442                         if (range->lf_type != type) {
 443                                 range->lf_start = end + 1;
 444                                 nrange = TAILQ_NEXT(range, lf_link);
 445                                 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 446                                 while (nrange != NULL) {
 447                                         if (nrange->lf_start >= end + 1)
 448                                                 break;
 449                                         nrange = TAILQ_NEXT(nrange, lf_link);
 450                                 }
 451                                 if (nrange != NULL)
 452                                         TAILQ_INSERT_BEFORE(nrange, range,
 453                                                             lf_link);
 454                                 else
 455                                         TAILQ_INSERT_TAIL(&lock->lf_range,
 456                                                           range, lf_link);
 457                                 break;
 458                         }
 459                         first_match->lf_end = range->lf_end;
 460                         first_match->lf_flags |=
 461                             range->lf_flags & F_NOEND;
 462                         TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 463                         lf_count_change(owner, -1);
 464                         lf_destroy_range(range, 1);
 465                         break;
 466                 }
 467                 goto do_wakeup;
 468         }
 469
 470         if (lf_overlap_right(first_match, start, end)) {
 471                 KKASSERT((flags & F_POSIX) != 0);
 472                 if (first_match->lf_type == type) {
 473                         first_match->lf_start = start;
 474                         if (first_match != insert_point) {
 475                                 TAILQ_REMOVE(&lock->lf_range, first_match,
 476                                              lf_link);
 477                                 TAILQ_INSERT_BEFORE(insert_point, first_match,
 478                                                     lf_link);
 479                         }
 480                         goto do_wakeup;
 481                 }
 482                 if (lf_count_change(owner, 1)) {
 483                         if (orig_first_match != NULL) {
 484                                 orig_first_match->lf_end = orig_end;
 485                                 orig_first_match->lf_flags = orig_end;
 486                         }
 487                         error = ENOLCK;
 488                         goto do_cleanup;
 489                 }
 490                 first_match->lf_start = end + 1;
 491                 KKASSERT(new_range1 != NULL);
 492                 range = new_range1;
 493                 new_range1 = NULL;
 494                 lf_create_range(range, owner, type, flags, start, end, 1);
 495                 TAILQ_INSERT_BEFORE(insert_point, range, lf_link);
 496                 range = TAILQ_NEXT(first_match, lf_link);
 497                 TAILQ_REMOVE(&lock->lf_range, first_match, lf_link);
 498                 while (range != NULL) {
 499                         if (range->lf_start >= first_match->lf_start)
 500                                 break;
 501                         range = TAILQ_NEXT(range, lf_link);
 502                 }
 503                 if (range != NULL)
 504                         TAILQ_INSERT_BEFORE(range, first_match, lf_link);
 505                 else
 506                         TAILQ_INSERT_TAIL(&lock->lf_range, first_match, lf_link);
 507                 goto do_wakeup;
 508         }
 509
 510 do_wakeup:
 511 #ifdef LOCKF_DEBUG
 512         if (lf_print_ranges)
 513                 lf_print_lock(lock);
 514 #endif
 515         if (wakeup_needed)
 516                 lf_wakeup(lock, start, end);
 517         error = 0;
 518 do_cleanup:
 519         if (new_range1 != NULL)
 520                 lf_destroy_range(new_range1, 0);
 521         if (new_range2 != NULL)
 522                 lf_destroy_range(new_range2, 0);
 523         return(error);
 524 }
 525
 526 static int
 527 lf_clearlock(struct lockf *lock, struct proc *owner, int type, int flags,
 528              off_t start, off_t end)
 529 {
 530         struct lockf_range *range, *trange;
 531         struct lockf_range *new_range;
 532         int error = 0;
 533
 534         new_range = lf_alloc_range();
 535
 536         TAILQ_FOREACH_MUTABLE(range, &lock->lf_range, lf_link, trange) {
 537                 if (range->lf_end < start)
 538                         continue;
 539                 if (range->lf_start > end)
 540                         break;
 541                 if (range->lf_owner != owner)
 542                         continue;
 543                 if (lf_overlap_embedded(range, start, end)) {
 544                         TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 545                         /* flock-locks are equal */
 546                         if (range->lf_flags & F_POSIX)
 547                                 lf_count_change(owner, -1);
 548                         lf_destroy_range(range, 1);
 549                         continue;
 550                 }
 551                 if (lf_overlap_left2(range, start, end)) {
 552                         KKASSERT(range->lf_flags & F_POSIX);
 553                         if (lf_overlap_right2(range, start, end)) {
 554                                 struct lockf_range *nrange;
 555
 556                                 if (lf_count_change(owner, 1)) {
 557                                         error = ENOLCK;
 558                                         goto do_cleanup;
 559                                 }
 560                                 nrange = new_range;
 561                                 new_range = NULL;
 562                                 lf_create_range(nrange, nrange->lf_owner,
 563                                     range->lf_type, range->lf_flags,
 564                                     end + 1, range->lf_end, 1);
 565                                 range->lf_end = start;
 566                                 range->lf_flags &= ~F_NOEND;
 567                                 for (; range != NULL;
 568                                      range = TAILQ_NEXT(range, lf_link))
 569                                         if (range->lf_start >= nrange->lf_start)
 570                                                 break;
 571                                 if (range != NULL)
 572                                         TAILQ_INSERT_BEFORE(range, nrange,
 573                                                             lf_link);
 574                                 else
 575                                         TAILQ_INSERT_TAIL(&lock->lf_range,
 576                                                           nrange, lf_link);
 577                                 break;
 578                         }
 579                         range->lf_end = start - 1;
 580                         range->lf_flags &= ~F_NOEND;
 581                         continue;
 582                 }
 583                 if (lf_overlap_right2(range, start, end)) {
 584                         struct lockf_range *nrange = range;
 585
 586                         KKASSERT(range->lf_flags & F_POSIX);
 587
 588                         range  = TAILQ_NEXT(range, lf_link);
 589                         TAILQ_REMOVE(&lock->lf_range, nrange, lf_link);
 590                         for (; range != NULL;
 591                              range = TAILQ_NEXT(range, lf_link))
 592                                 if (range->lf_start >= nrange->lf_start)
 593                                         break;
 594                         if (range != NULL)
 595                                 TAILQ_INSERT_BEFORE(range, nrange, lf_link);
 596                         else
 597                                 TAILQ_INSERT_TAIL(&lock->lf_range, nrange,
 598                                                   lf_link);
 599                         break;
 600                 }
 601         }
 602
 603         lf_wakeup(lock, start, end);
 604         error = 0;
 605
 606 do_cleanup:
 607         if (new_range != NULL)
 608                 lf_destroy_range(new_range, 0);
 609
 610         return(error);
 611 }
 612
 613 /*
 614  * Check whether there is a blocking lock,
 615  * and if so return its process identifier.
 616  */
 617 static int
 618 lf_getlock(struct flock *fl, struct lockf *lock, struct proc *owner,
 619            int type, int flags, off_t start, off_t end)
 620 {
 621         struct lockf_range *range;
 622
 623         TAILQ_FOREACH(range, &lock->lf_range, lf_link)
 624                 if (range->lf_owner != owner &&
 625                     lf_overlap(range, start, end) &&
 626                     (type == F_WRLCK || range->lf_type == F_WRLCK))
 627                         break;
 628         if (range == NULL) {
 629                 fl->l_type = F_UNLCK;
 630                 return(0);
 631         }
 632         fl->l_type = range->lf_type;
 633         fl->l_whence = SEEK_SET;
 634         fl->l_start = range->lf_start;
 635         if (range->lf_flags & F_NOEND)
 636                 fl->l_len = 0;
 637         else
 638                 fl->l_len = range->lf_end - range->lf_start + 1;
 639         if (range->lf_owner != NULL && (range->lf_flags & F_POSIX))
 640                 fl->l_pid = range->lf_owner->p_pid;
 641         else
 642                 fl->l_pid = -1;
 643         return(0);
 644 }
 645
 646 /*
 647  * Check wether range and [start, end] overlap.
 648  */
 649 static int
 650 lf_overlap(const struct lockf_range *range, off_t start, off_t end)
 651 {
 652         if (range->lf_start >= start && range->lf_start <= end)
 653                 return(1);
 654         else if (start >= range->lf_start && start <= range->lf_end)
 655                 return(1);
 656         else
 657                 return(0);
 658 }
 659
 660 /*
 661  * Wakeup pending lock attempts.
 662  */
 663 static void
 664 lf_wakeup(struct lockf *lock, off_t start, off_t end)
 665 {
 666         struct lockf_range *range, *nrange;
 667         TAILQ_FOREACH_MUTABLE(range, &lock->lf_blocked, lf_link, nrange) {
 668                 if (lf_overlap(range, start, end) == 0)
 669                         continue;
 670                 TAILQ_REMOVE(&lock->lf_blocked, range, lf_link);
 671                 range->lf_flags = 1;
 672                 wakeup(range);
 673         }
 674 }
 675
 676 static int
 677 lf_overlap_left(const struct lockf_range *range, off_t start, off_t end)
 678 {
 679         if (range->lf_start < start && range->lf_end >= start - 1 &&
 680             range->lf_end <= end)
 681                 return(1);
 682         else
 683                 return(0);
 684
 685 }
 686
 687 static int
 688 lf_overlap_right(const struct lockf_range *range, off_t start, off_t end)
 689 {
 690         if (range->lf_end > end && range->lf_start >= start &&
 691             range->lf_start - 1 <= end)
 692                 return(1);
 693         else
 694                 return(0);
 695 }
 696
 697 static int
 698 lf_overlap_left2(const struct lockf_range *range, off_t start, off_t end)
 699 {
 700         if (range->lf_start < start && range->lf_end >= start &&
 701             range->lf_end <= end)
 702                 return(1);
 703         else
 704                 return(0);
 705
 706 }
 707
 708 static int
 709 lf_overlap_right2(const struct lockf_range *range, off_t start, off_t end)
 710 {
 711         if (range->lf_end > end && range->lf_start >= start &&
 712             range->lf_start <= end)
 713                 return(1);
 714         else
 715                 return(0);
 716 }
 717
 718 static int
 719 lf_overlap_embedded(const struct lockf_range *range, off_t start, off_t end)
 720 {
 721         if (range->lf_start >= start && range->lf_end <= end)
 722                 return(1);
 723         else
 724                 return(0);
 725 }
 726
 727 static struct lockf_range *
 728 lf_alloc_range(void)
 729 {
 730 #ifdef INVARIANTS
 731         lf_global_counter++;
 732 #endif
 733         return(malloc(sizeof(struct lockf_range), M_LOCKF, M_WAITOK));
 734 }
 735
 736 static void
 737 lf_create_range(struct lockf_range *range, struct proc *owner, int type,
 738                 int flags, off_t start, off_t end, int accounting)
 739 {
 740         KKASSERT(start <= end);
 741         if (owner != NULL && (flags & F_POSIX) && accounting)
 742                 ++owner->p_numposixlocks;
 743         range->lf_type = type;
 744         range->lf_flags = flags;
 745         range->lf_start = start;
 746         range->lf_end = end;
 747         range->lf_owner = owner;
 748
 749 #ifdef LOCKF_DEBUG
 750         if (lf_print_ranges)
 751                 printf("lf_create_range: %lld..%lld\n", range->lf_start,
 752                        range->lf_end);
 753 #endif
 754 }
 755
 756 static void
 757 lf_destroy_range(struct lockf_range *range, int accounting)
 758 {
 759         struct proc *owner = range->lf_owner;
 760         int flags = range->lf_flags;
 761
 762 #ifdef LOCKF_DEBUG
 763         if (lf_print_ranges)
 764                 printf("lf_destroy_range: %lld..%lld\n", range->lf_start,
 765                        range->lf_end);
 766 #endif
 767
 768         free(range, M_LOCKF);
 769         if (owner != NULL && (flags & F_POSIX) && accounting) {
 770                 --owner->p_numposixlocks;
 771                 KASSERT(owner->p_numposixlocks >= 0,
 772                         ("Negative number of POSIX locks held by process: %d",
 773                          owner->p_numposixlocks));
 774         }
 775
 776 #ifdef INVARIANTS
 777         lf_global_counter--;
 778         KKASSERT(lf_global_counter>=0);
 779 #endif
 780 }
 781
 782 #ifdef LOCKF_DEBUG
 783 static void
 784 lf_print_lock(const struct lockf *lock)
 785 {
 786         struct lockf_range *range;
 787
 788         if (TAILQ_EMPTY(&lock->lf_range))
 789                 printf("lockf %p: no ranges locked\n", lock);
 790         else
 791                 printf("lockf %p:\n", lock);
 792         TAILQ_FOREACH(range, &lock->lf_range, lf_link)
 793                 printf("\t%lld..%lld type %s owned by %d\n",
 794                        range->lf_start, range->lf_end,
 795                        range->lf_type == F_RDLCK ? "shared" : "exclusive",
 796                        range->lf_flags & F_POSIX ? range->lf_owner->p_pid : -1);
 797         if (TAILQ_EMPTY(&lock->lf_blocked))
 798                 printf("no process waiting for range\n");
 799         else
 800                 printf("blocked locks:");
 801         TAILQ_FOREACH(range, &lock->lf_range, lf_link)
 802                 printf("\t%lld..%lld type %s waiting on %p\n",
 803                        range->lf_start, range->lf_end,
 804                        range->lf_type == F_RDLCK ? "shared" : "exclusive",
 805                        range);
 806 }
 807 #endif /* LOCKF_DEBUG */