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.10 2004/05/07 05:45:31 dillon 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, error;
 149         lwkt_tokref ilock;
 150
 151         if (lock->init_done == 0) {
 152                 TAILQ_INIT(&lock->lf_range);
 153                 TAILQ_INIT(&lock->lf_blocked);
 154                 lock->init_done = 1;
 155         }
 156
 157         /*
 158          * Convert the flock structure into a start and end.
 159          */
 160         switch (fl->l_whence) {
 161         case SEEK_SET:
 162         case SEEK_CUR:
 163                 /*
 164                  * Caller is responsible for adding any necessary offset
 165                  * when SEEK_CUR is used.
 166                  */
 167                 start = fl->l_start;
 168                 break;
 169
 170         case SEEK_END:
 171                 start = size + fl->l_start;
 172                 break;
 173
 174         default:
 175                 return(EINVAL);
 176         }
 177         if (start < 0)
 178                 return(EINVAL);
 179         if (fl->l_len == 0) {
 180                 flags |= F_NOEND;
 181                 end = LLONG_MAX;
 182         } else {
 183                 end = start + fl->l_len - 1;
 184                 if (end < start)
 185                         return(EINVAL);
 186         }
 187
 188         flags = ap->a_flags;
 189         type = fl->l_type;
 190         /*
 191          * This isn't really correct for flock-style locks,
 192          * but the current handling is somewhat broken anyway.
 193          */
 194         owner = (struct proc *)ap->a_id;
 195
 196         /*
 197          * Do the requested operation.
 198          */
 199         lwkt_gettoken(&ilock, lwkt_token_pool_get(lock));
 200         switch(ap->a_op) {
 201         case F_SETLK:
 202                 error = lf_setlock(lock, owner, type, flags, start, end);
 203                 break;
 204
 205         case F_UNLCK:
 206                 error = lf_clearlock(lock, owner, type, flags, start, end);
 207                 break;
 208
 209         case F_GETLK:
 210                 error = lf_getlock(fl, lock, owner, type, flags, start, end);
 211                 break;
 212
 213         default:
 214                 error = EINVAL;
 215                 break;
 216         }
 217         lwkt_reltoken(&ilock);
 218         return(error);
 219 }
 220
 221 static int
 222 lf_setlock(struct lockf *lock, struct proc *owner, int type, int flags,
 223            off_t start, off_t end)
 224 {
 225         struct lockf_range *range, *first_match, *insert_point;
 226         int wakeup_needed, lock_needed;
 227         /* pre-allocation to avoid blocking in the middle of the algorithm */
 228         struct lockf_range *new_range1 = NULL, *new_range2 = NULL;
 229         int error = 0;
 230
 231         /* for restauration in case of hitting the POSIX lock limit below */
 232         struct lockf_range *orig_first_match = NULL;
 233         off_t orig_end = -1;
 234         int orig_flags = 0;
 235
 236 restart:
 237         if (new_range1 == NULL)
 238                 new_range1 = lf_alloc_range();
 239         if (new_range2 == NULL)
 240                 new_range2 = lf_alloc_range();
 241         first_match = NULL;
 242         insert_point = NULL;
 243         wakeup_needed = 0;
 244
 245 #ifdef LOCKF_DEBUG
 246         if (lf_print_ranges)
 247                 lf_print_lock(lock);
 248 #endif
 249
 250         TAILQ_FOREACH(range, &lock->lf_range, lf_link) {
 251                 if (insert_point == NULL && range->lf_start >= start)
 252                         insert_point = range;
 253                 if (lf_overlap(range, start, end) == 0)
 254                         continue;
 255                 if (range->lf_owner == owner) {
 256                         if (first_match == NULL)
 257                                 first_match = range;
 258                         continue;
 259                 }
 260                 if (type == F_WRLCK || range->lf_type == F_WRLCK)
 261                         break;
 262         }
 263
 264         if (range != NULL) {
 265                 struct lockf_range *brange;
 266                 int error;
 267
 268                 if ((flags & F_WAIT) == 0) {
 269                         error = EAGAIN;
 270                         goto do_cleanup;
 271                 }
 272
 273                 /*
 274                  * We are blocked. For POSIX locks we have to check
 275                  * for deadlocks and return with EDEADLK. This is done
 276                  * by checking wether range->lf_owner is already
 277                  * blocked.
 278                  *
 279                  * Since flock-style locks cover the whole file, a
 280                  * deadlock between those is nearly impossible.
 281                  * This can only occur if a process tries to lock the
 282                  * same inode exclusively while holding a shared lock
 283                  * with another descriptor.
 284                  * XXX How can we cleanly detect this?
 285                  * XXX The current mixing of flock & fcntl/lockf is evil.
 286                  *
 287                  * Handle existing locks of flock-style like POSIX locks.
 288                  */
 289                 if (flags & F_POSIX) {
 290                         TAILQ_FOREACH(brange, &lock->lf_blocked, lf_link)
 291                                 if (brange->lf_owner == range->lf_owner) {
 292                                         error = EDEADLK;
 293                                         goto do_cleanup;
 294                                 }
 295                 }
 296
 297                 /*
 298                  * For flock-style locks, we must first remove
 299                  * any shared locks that we hold before we sleep
 300                  * waiting for an exclusive lock.
 301                  */
 302                 if ((flags & F_FLOCK) && type == F_WRLCK)
 303                         lf_clearlock(lock, owner, type, flags, start, end);
 304
 305                 brange = new_range1;
 306                 new_range1 = NULL;
 307                 lf_create_range(brange, owner, type, 0, start, end, 0);
 308                 TAILQ_INSERT_TAIL(&lock->lf_blocked, brange, lf_link);
 309                 error = tsleep(brange, PCATCH, "lockf", 0);
 310
 311                 /*
 312                  * We may have been awaked by a signal and/or by a
 313                  * debugger continuing us (in which case we must remove
 314                  * ourselves from the blocked list) and/or by another
 315                  * process releasing/downgrading a lock (in which case
 316                  * we have already been removed from the blocked list
 317                  * and our lf_flags field is 1).
 318                  */
 319                 if (brange->lf_flags == 0)
 320                         TAILQ_REMOVE(&lock->lf_blocked, brange, lf_link);
 321                 lf_destroy_range(brange, 0);
 322
 323                 if (error)
 324                         goto do_cleanup;
 325                 goto restart;
 326         }
 327
 328         if (first_match == NULL) {
 329                 if (flags & F_POSIX) {
 330                         if (lf_count_change(owner, 1)) {
 331                                 error = ENOLCK;
 332                                 goto do_cleanup;
 333                         }
 334                 }
 335                 range = new_range1;
 336                 new_range1 = NULL;
 337                 lf_create_range(range, owner, type, flags, start, end, 1);
 338                 if (insert_point != NULL)
 339                         TAILQ_INSERT_BEFORE(insert_point, range, lf_link);
 340                 else
 341                         TAILQ_INSERT_TAIL(&lock->lf_range, range, lf_link);
 342                 goto do_wakeup;
 343         }
 344
 345         lock_needed = 1;
 346
 347         if (lf_overlap_left(first_match, start, end)) {
 348                 KKASSERT((flags & F_POSIX) != 0);
 349                 if (first_match->lf_end > end) {
 350                         if (first_match->lf_type == type)
 351                                 goto do_wakeup;
 352                         if (lf_count_change(owner, 2)) {
 353                                 error = ENOLCK;
 354                                 goto do_cleanup;
 355                         }
 356                         range = new_range1;
 357                         new_range1 = NULL;
 358                         lf_create_range(range, owner, type, flags,
 359                                         start, end, 1);
 360                         if (insert_point != NULL)
 361                                 TAILQ_INSERT_BEFORE(insert_point, range,
 362                                                     lf_link);
 363                         else
 364                                 TAILQ_INSERT_TAIL(&lock->lf_range, range,
 365                                                   lf_link);
 366                         insert_point = range;
 367                         range = new_range2;
 368                         new_range2 = NULL;
 369                         lf_create_range(range, owner, first_match->lf_type,
 370                                         first_match->lf_flags, end + 1,
 371                                         first_match->lf_end, 1);
 372                         TAILQ_INSERT_AFTER(&lock->lf_range, insert_point,
 373                                            range, lf_link);
 374                         first_match->lf_flags &= ~F_NOEND;
 375                         first_match->lf_end = start - 1;
 376                         if (type == F_RDLCK)
 377                                 wakeup_needed = 1;
 378                         goto do_wakeup;
 379                 }
 380                 /*
 381                  * left match, but not right match
 382                  *
 383                  * handle the lf_type != type case directly,
 384                  * merge the other case with the !lock_needed path.
 385                  */
 386                 if (first_match->lf_type != type) {
 387                         /*
 388                          * This is needed if the lockf acquisition below fails.
 389                          */
 390                         orig_first_match = first_match;
 391                         orig_end = first_match->lf_end;
 392                         orig_flags = first_match->lf_flags;
 393                         first_match->lf_end = start - 1;
 394                         first_match->lf_flags &= ~F_NOEND;
 395                         if (type == F_RDLCK)
 396                                 wakeup_needed = 1;
 397                         /* Try to find the next matching range */
 398                         range = TAILQ_NEXT(first_match, lf_link);
 399                         while (range != NULL) {
 400                                 if (range->lf_owner == owner &&
 401                                     lf_overlap(range, start, end))
 402                                         break;
 403                                 range = TAILQ_NEXT(range, lf_link);
 404                         }
 405                         if (range == NULL)
 406                                 goto do_wakeup;
 407                         first_match = range;
 408                         /* fall through to !left_match behaviour */
 409                 } else {
 410                         first_match->lf_end = end;
 411                         first_match->lf_flags |= flags & F_NOEND;
 412                         lock_needed = 0;
 413                 }
 414         }
 415
 416         if (lf_overlap_embedded(first_match, start, end)) {
 417                 if (first_match != insert_point) {
 418                         TAILQ_REMOVE(&lock->lf_range, first_match, lf_link);
 419                         TAILQ_INSERT_BEFORE(insert_point, first_match, lf_link);
 420                 }
 421                 first_match->lf_start = start;
 422                 first_match->lf_end = end;
 423                 first_match->lf_flags |= flags & F_NOEND;
 424                 lock_needed = 0;
 425         }
 426
 427         if (lock_needed == 0) {
 428                 struct lockf_range *nrange;
 429
 430                 range = TAILQ_NEXT(first_match, lf_link);
 431                 while (range != NULL) {
 432                         if (range->lf_owner != owner) {
 433                                 range = TAILQ_NEXT(range, lf_link);
 434                                 continue;
 435                         }
 436                         if (lf_overlap_embedded(range, start, end)) {
 437                                 nrange = TAILQ_NEXT(range, lf_link);
 438                                 TAILQ_REMOVE(&lock->lf_range, range,
 439                                              lf_link);
 440                                 lf_count_change(owner, -1);
 441                                 lf_destroy_range(range, 1);
 442                                 range = nrange;
 443                                 continue;
 444                         }
 445                         if (lf_overlap_right(range, start, end) == 0) {
 446                                 range = TAILQ_NEXT(range, lf_link);
 447                                 continue;
 448                         }
 449                         if (range->lf_type != type) {
 450                                 range->lf_start = end + 1;
 451                                 nrange = TAILQ_NEXT(range, lf_link);
 452                                 TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 453                                 while (nrange != NULL) {
 454                                         if (nrange->lf_start >= end + 1)
 455                                                 break;
 456                                         nrange = TAILQ_NEXT(nrange, lf_link);
 457                                 }
 458                                 if (nrange != NULL)
 459                                         TAILQ_INSERT_BEFORE(nrange, range,
 460                                                             lf_link);
 461                                 else
 462                                         TAILQ_INSERT_TAIL(&lock->lf_range,
 463                                                           range, lf_link);
 464                                 break;
 465                         }
 466                         first_match->lf_end = range->lf_end;
 467                         first_match->lf_flags |=
 468                             range->lf_flags & F_NOEND;
 469                         TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 470                         lf_count_change(owner, -1);
 471                         lf_destroy_range(range, 1);
 472                         break;
 473                 }
 474                 goto do_wakeup;
 475         }
 476
 477         if (lf_overlap_right(first_match, start, end)) {
 478                 KKASSERT((flags & F_POSIX) != 0);
 479                 if (first_match->lf_type == type) {
 480                         first_match->lf_start = start;
 481                         if (first_match != insert_point) {
 482                                 TAILQ_REMOVE(&lock->lf_range, first_match,
 483                                              lf_link);
 484                                 TAILQ_INSERT_BEFORE(insert_point, first_match,
 485                                                     lf_link);
 486                         }
 487                         goto do_wakeup;
 488                 }
 489                 if (lf_count_change(owner, 1)) {
 490                         if (orig_first_match != NULL) {
 491                                 orig_first_match->lf_end = orig_end;
 492                                 orig_first_match->lf_flags = orig_end;
 493                         }
 494                         error = ENOLCK;
 495                         goto do_cleanup;
 496                 }
 497                 first_match->lf_start = end + 1;
 498                 KKASSERT(new_range1 != NULL);
 499                 range = new_range1;
 500                 new_range1 = NULL;
 501                 lf_create_range(range, owner, type, flags, start, end, 1);
 502                 TAILQ_INSERT_BEFORE(insert_point, range, lf_link);
 503                 range = TAILQ_NEXT(first_match, lf_link);
 504                 TAILQ_REMOVE(&lock->lf_range, first_match, lf_link);
 505                 while (range != NULL) {
 506                         if (range->lf_start >= first_match->lf_start)
 507                                 break;
 508                         range = TAILQ_NEXT(range, lf_link);
 509                 }
 510                 if (range != NULL)
 511                         TAILQ_INSERT_BEFORE(range, first_match, lf_link);
 512                 else
 513                         TAILQ_INSERT_TAIL(&lock->lf_range, first_match, lf_link);
 514                 goto do_wakeup;
 515         }
 516
 517 do_wakeup:
 518 #ifdef LOCKF_DEBUG
 519         if (lf_print_ranges)
 520                 lf_print_lock(lock);
 521 #endif
 522         if (wakeup_needed)
 523                 lf_wakeup(lock, start, end);
 524         error = 0;
 525 do_cleanup:
 526         if (new_range1 != NULL)
 527                 lf_destroy_range(new_range1, 0);
 528         if (new_range2 != NULL)
 529                 lf_destroy_range(new_range2, 0);
 530         return(error);
 531 }
 532
 533 static int
 534 lf_clearlock(struct lockf *lock, struct proc *owner, int type, int flags,
 535              off_t start, off_t end)
 536 {
 537         struct lockf_range *range, *trange;
 538         struct lockf_range *new_range;
 539         int error = 0;
 540
 541         new_range = lf_alloc_range();
 542
 543         TAILQ_FOREACH_MUTABLE(range, &lock->lf_range, lf_link, trange) {
 544                 if (range->lf_end < start)
 545                         continue;
 546                 if (range->lf_start > end)
 547                         break;
 548                 if (range->lf_owner != owner)
 549                         continue;
 550                 if (lf_overlap_embedded(range, start, end)) {
 551                         TAILQ_REMOVE(&lock->lf_range, range, lf_link);
 552                         /* flock-locks are equal */
 553                         if (range->lf_flags & F_POSIX)
 554                                 lf_count_change(owner, -1);
 555                         lf_destroy_range(range, 1);
 556                         continue;
 557                 }
 558                 if (lf_overlap_left2(range, start, end)) {
 559                         KKASSERT(range->lf_flags & F_POSIX);
 560                         if (lf_overlap_right2(range, start, end)) {
 561                                 struct lockf_range *nrange;
 562
 563                                 if (lf_count_change(owner, 1)) {
 564                                         error = ENOLCK;
 565                                         goto do_cleanup;
 566                                 }
 567                                 nrange = new_range;
 568                                 new_range = NULL;
 569                                 lf_create_range(nrange, range->lf_owner,
 570                                     range->lf_type, range->lf_flags,
 571                                     end + 1, range->lf_end, 1);
 572                                 range->lf_end = start;
 573                                 range->lf_flags &= ~F_NOEND;
 574                                 for (; range != NULL;
 575                                      range = TAILQ_NEXT(range, lf_link))
 576                                         if (range->lf_start >= nrange->lf_start)
 577                                                 break;
 578                                 if (range != NULL)
 579                                         TAILQ_INSERT_BEFORE(range, nrange,
 580                                                             lf_link);
 581                                 else
 582                                         TAILQ_INSERT_TAIL(&lock->lf_range,
 583                                                           nrange, lf_link);
 584                                 break;
 585                         }
 586                         range->lf_end = start - 1;
 587                         range->lf_flags &= ~F_NOEND;
 588                         continue;
 589                 }
 590                 if (lf_overlap_right2(range, start, end)) {
 591                         struct lockf_range *nrange = range;
 592
 593                         KKASSERT(range->lf_flags & F_POSIX);
 594
 595                         range  = TAILQ_NEXT(range, lf_link);
 596                         TAILQ_REMOVE(&lock->lf_range, nrange, lf_link);
 597                         for (; range != NULL;
 598                              range = TAILQ_NEXT(range, lf_link))
 599                                 if (range->lf_start >= nrange->lf_start)
 600                                         break;
 601                         if (range != NULL)
 602                                 TAILQ_INSERT_BEFORE(range, nrange, lf_link);
 603                         else
 604                                 TAILQ_INSERT_TAIL(&lock->lf_range, nrange,
 605                                                   lf_link);
 606                         break;
 607                 }
 608         }
 609
 610         lf_wakeup(lock, start, end);
 611         error = 0;
 612
 613 do_cleanup:
 614         if (new_range != NULL)
 615                 lf_destroy_range(new_range, 0);
 616
 617         return(error);
 618 }
 619
 620 /*
 621  * Check whether there is a blocking lock,
 622  * and if so return its process identifier.
 623  */
 624 static int
 625 lf_getlock(struct flock *fl, struct lockf *lock, struct proc *owner,
 626            int type, int flags, off_t start, off_t end)
 627 {
 628         struct lockf_range *range;
 629
 630         TAILQ_FOREACH(range, &lock->lf_range, lf_link)
 631                 if (range->lf_owner != owner &&
 632                     lf_overlap(range, start, end) &&
 633                     (type == F_WRLCK || range->lf_type == F_WRLCK))
 634                         break;
 635         if (range == NULL) {
 636                 fl->l_type = F_UNLCK;
 637                 return(0);
 638         }
 639         fl->l_type = range->lf_type;
 640         fl->l_whence = SEEK_SET;
 641         fl->l_start = range->lf_start;
 642         if (range->lf_flags & F_NOEND)
 643                 fl->l_len = 0;
 644         else
 645                 fl->l_len = range->lf_end - range->lf_start + 1;
 646         if (range->lf_owner != NULL && (range->lf_flags & F_POSIX))
 647                 fl->l_pid = range->lf_owner->p_pid;
 648         else
 649                 fl->l_pid = -1;
 650         return(0);
 651 }
 652
 653 /*
 654  * Check wether range and [start, end] overlap.
 655  */
 656 static int
 657 lf_overlap(const struct lockf_range *range, off_t start, off_t end)
 658 {
 659         if (range->lf_start >= start && range->lf_start <= end)
 660                 return(1);
 661         else if (start >= range->lf_start && start <= range->lf_end)
 662                 return(1);
 663         else
 664                 return(0);
 665 }
 666
 667 /*
 668  * Wakeup pending lock attempts.
 669  */
 670 static void
 671 lf_wakeup(struct lockf *lock, off_t start, off_t end)
 672 {
 673         struct lockf_range *range, *nrange;
 674         TAILQ_FOREACH_MUTABLE(range, &lock->lf_blocked, lf_link, nrange) {
 675                 if (lf_overlap(range, start, end) == 0)
 676                         continue;
 677                 TAILQ_REMOVE(&lock->lf_blocked, range, lf_link);
 678                 range->lf_flags = 1;
 679                 wakeup(range);
 680         }
 681 }
 682
 683 static int
 684 lf_overlap_left(const struct lockf_range *range, off_t start, off_t end)
 685 {
 686         if (range->lf_start < start && range->lf_end >= start - 1 &&
 687             range->lf_end <= end)
 688                 return(1);
 689         else
 690                 return(0);
 691
 692 }
 693
 694 static int
 695 lf_overlap_right(const struct lockf_range *range, off_t start, off_t end)
 696 {
 697         if (range->lf_end > end && range->lf_start >= start &&
 698             range->lf_start - 1 <= end)
 699                 return(1);
 700         else
 701                 return(0);
 702 }
 703
 704 static int
 705 lf_overlap_left2(const struct lockf_range *range, off_t start, off_t end)
 706 {
 707         if (range->lf_start < start && range->lf_end >= start &&
 708             range->lf_end <= end)
 709                 return(1);
 710         else
 711                 return(0);
 712
 713 }
 714
 715 static int
 716 lf_overlap_right2(const struct lockf_range *range, off_t start, off_t end)
 717 {
 718         if (range->lf_end > end && range->lf_start >= start &&
 719             range->lf_start <= end)
 720                 return(1);
 721         else
 722                 return(0);
 723 }
 724
 725 static int
 726 lf_overlap_embedded(const struct lockf_range *range, off_t start, off_t end)
 727 {
 728         if (range->lf_start >= start && range->lf_end <= end)
 729                 return(1);
 730         else
 731                 return(0);
 732 }
 733
 734 static struct lockf_range *
 735 lf_alloc_range(void)
 736 {
 737 #ifdef INVARIANTS
 738         lf_global_counter++;
 739 #endif
 740         return(malloc(sizeof(struct lockf_range), M_LOCKF, M_WAITOK));
 741 }
 742
 743 static void
 744 lf_create_range(struct lockf_range *range, struct proc *owner, int type,
 745                 int flags, off_t start, off_t end, int accounting)
 746 {
 747         KKASSERT(start <= end);
 748         if (owner != NULL && (flags & F_POSIX) && accounting)
 749                 ++owner->p_numposixlocks;
 750         range->lf_type = type;
 751         range->lf_flags = flags;
 752         range->lf_start = start;
 753         range->lf_end = end;
 754         range->lf_owner = owner;
 755
 756 #ifdef LOCKF_DEBUG
 757         if (lf_print_ranges)
 758                 printf("lf_create_range: %lld..%lld\n", range->lf_start,
 759                        range->lf_end);
 760 #endif
 761 }
 762
 763 static void
 764 lf_destroy_range(struct lockf_range *range, int accounting)
 765 {
 766         struct proc *owner = range->lf_owner;
 767         int flags = range->lf_flags;
 768
 769 #ifdef LOCKF_DEBUG
 770         if (lf_print_ranges)
 771                 printf("lf_destroy_range: %lld..%lld\n", range->lf_start,
 772                        range->lf_end);
 773 #endif
 774
 775         free(range, M_LOCKF);
 776         if (owner != NULL && (flags & F_POSIX) && accounting) {
 777                 --owner->p_numposixlocks;
 778                 KASSERT(owner->p_numposixlocks >= 0,
 779                         ("Negative number of POSIX locks held by process: %d",
 780                          owner->p_numposixlocks));
 781         }
 782
 783 #ifdef INVARIANTS
 784         lf_global_counter--;
 785         KKASSERT(lf_global_counter>=0);
 786 #endif
 787 }
 788
 789 #ifdef LOCKF_DEBUG
 790 static void
 791 lf_print_lock(const struct lockf *lock)
 792 {
 793         struct lockf_range *range;
 794
 795         if (TAILQ_EMPTY(&lock->lf_range))
 796                 printf("lockf %p: no ranges locked\n", lock);
 797         else
 798                 printf("lockf %p:\n", lock);
 799         TAILQ_FOREACH(range, &lock->lf_range, lf_link)
 800                 printf("\t%lld..%lld type %s owned by %d\n",
 801                        range->lf_start, range->lf_end,
 802                        range->lf_type == F_RDLCK ? "shared" : "exclusive",
 803                        range->lf_flags & F_POSIX ? range->lf_owner->p_pid : -1);
 804         if (TAILQ_EMPTY(&lock->lf_blocked))
 805                 printf("no process waiting for range\n");
 806         else
 807                 printf("blocked locks:");
 808         TAILQ_FOREACH(range, &lock->lf_range, lf_link)
 809                 printf("\t%lld..%lld type %s waiting on %p\n",
 810                        range->lf_start, range->lf_end,
 811                        range->lf_type == F_RDLCK ? "shared" : "exclusive",
 812                        range);
 813 }
 814 #endif /* LOCKF_DEBUG */