sys/kern/kern_ccms.c

   1 /*
   2  * Copyright (c) 2006 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  * $DragonFly: src/sys/kern/kern_ccms.c,v 1.4 2007/04/30 07:18:53 dillon Exp $
  35  */
  36 /*
  37  * The Cache Coherency Management System (CCMS)
  38  */
  39
  40 #include <sys/param.h>
  41 #include <sys/systm.h>
  42 #include <sys/kernel.h>
  43 #include <sys/malloc.h>
  44 #include <sys/objcache.h>
  45 #include <sys/ccms.h>
  46 #include <sys/sysctl.h>
  47 #include <sys/uio.h>
  48 #include <machine/limits.h>
  49
  50 struct ccms_lock_scan_info {
  51         ccms_dataspace_t ds;
  52         ccms_lock_t lock;
  53         ccms_cst_t  cst1;
  54         ccms_cst_t  cst2;
  55         ccms_cst_t  coll_cst;
  56 };
  57
  58 static int ccms_cst_cmp(ccms_cst_t b1, ccms_cst_t b2);
  59 static int ccms_lock_scan_cmp(ccms_cst_t b1, void *arg);
  60 static int ccms_lock_undo_cmp(ccms_cst_t b1, void *arg);
  61 static int ccms_dataspace_destroy_match(ccms_cst_t cst, void *arg);
  62 static int ccms_lock_get_match(struct ccms_cst *cst, void *arg);
  63 static int ccms_lock_undo_match(struct ccms_cst *cst, void *arg);
  64 static int ccms_lock_redo_match(struct ccms_cst *cst, void *arg);
  65 static int ccms_lock_put_match(struct ccms_cst *cst, void *arg);
  66
  67 RB_GENERATE3(ccms_rb_tree, ccms_cst, rbnode, ccms_cst_cmp,
  68              off_t, beg_offset, end_offset);
  69 static MALLOC_DEFINE(M_CCMS, "CCMS", "Cache Coherency Management System");
  70
  71 static int ccms_enable;
  72 SYSCTL_INT(_kern, OID_AUTO, ccms_enable, CTLFLAG_RW, &ccms_enable, 0, "");
  73
  74 static struct objcache *ccms_oc;
  75
  76 /*
  77  * Initialize the CCMS subsystem
  78  */
  79 static void
  80 ccmsinit(void *dummy)
  81 {
  82     ccms_oc = objcache_create_simple(M_CCMS, sizeof(struct ccms_cst));
  83 }
  84 SYSINIT(ccms, SI_BOOT2_MACHDEP, SI_ORDER_ANY, ccmsinit, NULL);
  85
  86 /*
  87  * Initialize a new CCMS dataspace.  Create a new RB tree with a single
  88  * element covering the entire 64 bit offset range.  This simplifies
  89  * algorithms enormously by removing a number of special cases.
  90  */
  91 void
  92 ccms_dataspace_init(ccms_dataspace_t ds)
  93 {
  94     ccms_cst_t cst;
  95
  96     RB_INIT(&ds->tree);
  97     ds->info = NULL;
  98     ds->chain = NULL;
  99     cst = objcache_get(ccms_oc, M_WAITOK);
 100     bzero(cst, sizeof(*cst));
 101     cst->beg_offset = LLONG_MIN;
 102     cst->end_offset = LLONG_MAX;
 103     cst->state = CCMS_STATE_INVALID;
 104     RB_INSERT(ccms_rb_tree, &ds->tree, cst);
 105 }
 106
 107 /*
 108  * Destroy a CCMS dataspace.
 109  */
 110 void
 111 ccms_dataspace_destroy(ccms_dataspace_t ds)
 112 {
 113     RB_SCAN(ccms_rb_tree, &ds->tree, NULL,
 114             ccms_dataspace_destroy_match, ds);
 115 }
 116
 117 static
 118 int
 119 ccms_dataspace_destroy_match(ccms_cst_t cst, void *arg)
 120 {
 121     ccms_dataspace_t ds = arg;
 122
 123     RB_REMOVE(ccms_rb_tree, &ds->tree, cst);
 124     objcache_put(ccms_oc, cst);
 125     return(0);
 126 }
 127
 128 /*
 129  * Obtain a CCMS lock
 130  */
 131 int
 132 ccms_lock_get(ccms_dataspace_t ds, ccms_lock_t lock)
 133 {
 134     struct ccms_lock_scan_info info;
 135
 136     if (ccms_enable == 0) {
 137         lock->ds = NULL;
 138         return(0);
 139     }
 140
 141     /*
 142      * Partition the CST space so the precise range is covered and
 143      * attempt to obtain the requested local lock (ltype) at the same
 144      * time.
 145      */
 146     lock->ds = ds;
 147     info.lock = lock;
 148     info.ds = ds;
 149     info.coll_cst = NULL;
 150     info.cst1 = objcache_get(ccms_oc, M_WAITOK);
 151     info.cst2 = objcache_get(ccms_oc, M_WAITOK);
 152
 153     RB_SCAN(ccms_rb_tree, &ds->tree, ccms_lock_scan_cmp,
 154             ccms_lock_get_match, &info);
 155
 156     /*
 157      * If a collision occured, undo the fragments we were able to obtain,
 158      * block, and try again.
 159      */
 160     while (info.coll_cst != NULL) {
 161         RB_SCAN(ccms_rb_tree, &ds->tree, ccms_lock_undo_cmp,
 162                 ccms_lock_undo_match, &info);
 163         info.coll_cst->blocked = 1;
 164         tsleep(info.coll_cst, 0,
 165                ((lock->ltype == CCMS_LTYPE_SHARED) ? "rngsh" : "rngex"),
 166                hz);
 167         info.coll_cst = NULL;
 168         RB_SCAN(ccms_rb_tree, &ds->tree, ccms_lock_scan_cmp,
 169                 ccms_lock_redo_match, &info);
 170     }
 171
 172     /*
 173      * Cleanup
 174      */
 175     if (info.cst1)
 176         objcache_put(ccms_oc, info.cst1);
 177     if (info.cst2)
 178         objcache_put(ccms_oc, info.cst2);
 179
 180     return(0);
 181 }
 182
 183 /*
 184  * Obtain a CCMS lock, initialize the lock structure from the uio.
 185  */
 186 int
 187 ccms_lock_get_uio(ccms_dataspace_t ds, ccms_lock_t lock, struct uio *uio)
 188 {
 189     ccms_ltype_t ltype;
 190     off_t eoff;
 191
 192     if (uio->uio_rw == UIO_READ)
 193         ltype = CCMS_LTYPE_SHARED;
 194     else
 195         ltype = CCMS_LTYPE_MODIFYING;
 196
 197     /*
 198      * Calculate the ending offset (byte inclusive), make sure a seek
 199      * overflow does not blow us up.
 200      */
 201     eoff = uio->uio_offset + uio->uio_resid - 1;
 202     if (eoff < uio->uio_offset)
 203         eoff = 0x7FFFFFFFFFFFFFFFLL;
 204     ccms_lock_init(lock, uio->uio_offset, eoff, ltype);
 205     return(ccms_lock_get(ds, lock));
 206 }
 207
 208 static
 209 int
 210 ccms_lock_get_match(ccms_cst_t cst, void *arg)
 211 {
 212     struct ccms_lock_scan_info *info = arg;
 213     ccms_lock_t lock = info->lock;
 214     ccms_cst_t ncst;
 215
 216     /*
 217      * If the lock's left edge is within the CST we must split the CST
 218      * into two pieces [cst][ncst].  lrefs must be bumped on the CST
 219      * containing the left edge.
 220      *
 221      * NOTE! cst->beg_offset may not be modified.  This allows us to avoid
 222      * having to manipulate the cst's position in the tree.
 223      */
 224     if (lock->beg_offset > cst->beg_offset) {
 225         ncst = info->cst1;
 226         info->cst1 = NULL;
 227         KKASSERT(ncst != NULL);
 228         *ncst = *cst;
 229         cst->end_offset = lock->beg_offset - 1;
 230         cst->rrefs = 0;
 231         ncst->beg_offset = lock->beg_offset;
 232         ncst->lrefs = 1;
 233         RB_INSERT(ccms_rb_tree, &info->ds->tree, ncst);
 234
 235         /*
 236          * ncst becomes our 'matching' cst.
 237          */
 238         cst = ncst;
 239     } else if (lock->beg_offset == cst->beg_offset) {
 240         ++cst->lrefs;
 241     }
 242
 243     /*
 244      * If the lock's right edge is within the CST we must split the CST
 245      * into two pieces [cst][ncst].  rrefs must be bumped on the CST
 246      * containing the right edge.
 247      *
 248      * NOTE! cst->beg_offset may not be modified.  This allows us to avoid
 249      * having to manipulate the cst's position in the tree.
 250      */
 251     if (lock->end_offset < cst->end_offset) {
 252         ncst = info->cst2;
 253         info->cst2 = NULL;
 254         KKASSERT(ncst != NULL);
 255         *ncst = *cst;
 256         cst->end_offset = lock->end_offset;
 257         cst->rrefs = 1;
 258         ncst->beg_offset = lock->end_offset + 1;
 259         ncst->lrefs = 0;
 260         RB_INSERT(ccms_rb_tree, &info->ds->tree, ncst);
 261         /* cst remains our 'matching' cst */
 262     } else if (lock->end_offset == cst->end_offset) {
 263         ++cst->rrefs;
 264     }
 265
 266     /*
 267      * The lock covers the CST, so increment the CST's coverage count.
 268      * Then attempt to obtain the shared/exclusive ltype.
 269      */
 270     ++cst->xrefs;
 271
 272     if (info->coll_cst == NULL) {
 273         switch(lock->ltype) {
 274         case CCMS_LTYPE_SHARED:
 275             if (cst->sharecount < 0) {
 276                 info->coll_cst = cst;
 277             } else {
 278                 ++cst->sharecount;
 279                 if (ccms_enable >= 9) {
 280                         kprintf("CST SHARE %d %lld-%lld\n", cst->sharecount,
 281                                 cst->beg_offset, cst->end_offset);
 282                 }
 283             }
 284             break;
 285         case CCMS_LTYPE_EXCLUSIVE:
 286             if (cst->sharecount != 0) {
 287                 info->coll_cst = cst;
 288             } else {
 289                 --cst->sharecount;
 290                 if (ccms_enable >= 9) {
 291                         kprintf("CST EXCLS %d %lld-%lld\n", cst->sharecount,
 292                                 cst->beg_offset, cst->end_offset);
 293                 }
 294             }
 295             break;
 296         case CCMS_LTYPE_MODIFYING:
 297             if (cst->sharecount != 0) {
 298                 info->coll_cst = cst;
 299             } else {
 300                 --cst->sharecount;
 301                 ++cst->modifycount;
 302                 if (ccms_enable >= 9) {
 303                         kprintf("CST MODXL %d %lld-%lld\n", cst->sharecount,
 304                                 cst->beg_offset, cst->end_offset);
 305                 }
 306             }
 307             break;
 308         }
 309     }
 310     return(0);
 311 }
 312
 313 /*
 314  * Undo a partially resolved ccms_ltype rangelock.  This is atomic with
 315  * the scan/redo code so there should not be any blocked locks when
 316  * transitioning to 0.
 317  */
 318 static
 319 int
 320 ccms_lock_undo_match(ccms_cst_t cst, void *arg)
 321 {
 322     struct ccms_lock_scan_info *info = arg;
 323     ccms_lock_t lock = info->lock;
 324
 325     switch(lock->ltype) {
 326     case CCMS_LTYPE_SHARED:
 327         KKASSERT(cst->sharecount > 0);
 328         --cst->sharecount;
 329         KKASSERT(cst->sharecount || cst->blocked == 0);
 330         break;
 331     case CCMS_LTYPE_EXCLUSIVE:
 332         KKASSERT(cst->sharecount < 0);
 333         ++cst->sharecount;
 334         KKASSERT(cst->sharecount || cst->blocked == 0);
 335         break;
 336     case CCMS_LTYPE_MODIFYING:
 337         KKASSERT(cst->sharecount < 0 && cst->modifycount > 0);
 338         ++cst->sharecount;
 339         --cst->modifycount;
 340         KKASSERT(cst->sharecount || cst->blocked == 0);
 341         break;
 342     }
 343     return(0);
 344 }
 345
 346 /*
 347  * Redo the local lock request for a range which has already been
 348  * partitioned.
 349  */
 350 static
 351 int
 352 ccms_lock_redo_match(ccms_cst_t cst, void *arg)
 353 {
 354     struct ccms_lock_scan_info *info = arg;
 355     ccms_lock_t lock = info->lock;
 356
 357     if (info->coll_cst == NULL) {
 358         switch(lock->ltype) {
 359         case CCMS_LTYPE_SHARED:
 360             if (cst->sharecount < 0) {
 361                 info->coll_cst = cst;
 362             } else {
 363                 if (ccms_enable >= 9) {
 364                         kprintf("CST SHARE %d %lld-%lld\n", cst->sharecount,
 365                                 cst->beg_offset, cst->end_offset);
 366                 }
 367                 ++cst->sharecount;
 368             }
 369             break;
 370         case CCMS_LTYPE_EXCLUSIVE:
 371             if (cst->sharecount != 0) {
 372                 info->coll_cst = cst;
 373             } else {
 374                 --cst->sharecount;
 375                 if (ccms_enable >= 9) {
 376                         kprintf("CST EXCLS %d %lld-%lld\n", cst->sharecount,
 377                                 cst->beg_offset, cst->end_offset);
 378                 }
 379             }
 380             break;
 381         case CCMS_LTYPE_MODIFYING:
 382             if (cst->sharecount != 0) {
 383                 info->coll_cst = cst;
 384             } else {
 385                 --cst->sharecount;
 386                 ++cst->modifycount;
 387                 if (ccms_enable >= 9) {
 388                         kprintf("CST MODXL %d %lld-%lld\n", cst->sharecount,
 389                                 cst->beg_offset, cst->end_offset);
 390                 }
 391             }
 392             break;
 393         }
 394     }
 395     return(0);
 396 }
 397
 398 /*
 399  * Release a CCMS lock
 400  */
 401 int
 402 ccms_lock_put(ccms_dataspace_t ds, ccms_lock_t lock)
 403 {
 404     struct ccms_lock_scan_info info;
 405
 406     if (lock->ds == NULL)
 407         return(0);
 408
 409     lock->ds = NULL;
 410     info.lock = lock;
 411     info.ds = ds;
 412     info.cst1 = NULL;
 413     info.cst2 = NULL;
 414
 415     RB_SCAN(ccms_rb_tree, &ds->tree, ccms_lock_scan_cmp,
 416             ccms_lock_put_match, &info);
 417
 418     if (info.cst1)
 419         objcache_put(ccms_oc, info.cst1);
 420     if (info.cst2)
 421         objcache_put(ccms_oc, info.cst2);
 422     return(0);
 423 }
 424
 425 static
 426 int
 427 ccms_lock_put_match(ccms_cst_t cst, void *arg)
 428 {
 429     struct ccms_lock_scan_info *info = arg;
 430     ccms_lock_t lock = info->lock;
 431     ccms_cst_t ocst;
 432
 433     /*
 434      * Undo the local shared/exclusive rangelock.
 435      */
 436     switch(lock->ltype) {
 437     case CCMS_LTYPE_SHARED:
 438         KKASSERT(cst->sharecount > 0);
 439         --cst->sharecount;
 440         if (ccms_enable >= 9) {
 441                 kprintf("CST UNSHR %d %lld-%lld (%d)\n", cst->sharecount,
 442                         cst->beg_offset, cst->end_offset, cst->blocked);
 443         }
 444         if (cst->blocked && cst->sharecount == 0) {
 445                 cst->blocked = 0;
 446                 wakeup(cst);
 447         }
 448         break;
 449     case CCMS_LTYPE_EXCLUSIVE:
 450         KKASSERT(cst->sharecount < 0);
 451         ++cst->sharecount;
 452         if (ccms_enable >= 9) {
 453                 kprintf("CST UNEXC %d %lld-%lld (%d)\n", cst->sharecount,
 454                         cst->beg_offset, cst->end_offset, cst->blocked);
 455         }
 456         if (cst->blocked && cst->sharecount == 0) {
 457                 cst->blocked = 0;
 458                 wakeup(cst);
 459         }
 460         break;
 461     case CCMS_LTYPE_MODIFYING:
 462         KKASSERT(cst->sharecount < 0 && cst->modifycount > 0);
 463         ++cst->sharecount;
 464         --cst->modifycount;
 465         if (ccms_enable >= 9) {
 466                 kprintf("CST UNMOD %d %lld-%lld (%d)\n", cst->sharecount,
 467                         cst->beg_offset, cst->end_offset, cst->blocked);
 468         }
 469         if (cst->blocked && cst->sharecount == 0) {
 470                 cst->blocked = 0;
 471                 wakeup(cst);
 472         }
 473         break;
 474     }
 475
 476     /*
 477      * Decrement the lock coverage count on the CST.  Decrement the left and
 478      * right edge counts as appropriate.
 479      *
 480      * When lrefs or rrefs drops to zero we check the adjacent entry to
 481      * determine whether a merge is possible.  If the appropriate refs field
 482      * (rrefs for the entry to our left, lrefs for the entry to our right)
 483      * is 0, then all covering locks must cover both entries and the xrefs
 484      * field must match.  We can then merge the entries if they have
 485      * compatible cache states.
 486      *
 487      * However, because we are cleaning up the shared/exclusive count at
 488      * the same time, the sharecount field may be temporarily out of
 489      * sync, so require that the sharecount field also match before doing
 490      * a merge.
 491      *
 492      * When merging an element which is being blocked on, the blocking
 493      * thread(s) will be woken up.
 494      *
 495      * If the dataspace has too many CSTs we may be able to merge the
 496      * entries even if their cache states are not the same, by dropping
 497      * both to a compatible (lower) cache state and performing the appropriate
 498      * management operations.  XXX
 499      */
 500     --cst->xrefs;
 501     if (lock->beg_offset == cst->beg_offset) {
 502         --cst->lrefs;
 503         if (cst->lrefs == 0) {
 504             if ((ocst = RB_PREV(ccms_rb_tree, &info->ds->tree, cst)) != NULL &&
 505                 ocst->rrefs == 0 &&
 506                 ocst->state == cst->state &&
 507                 ocst->sharecount == cst->sharecount
 508             ) {
 509                 KKASSERT(ocst->xrefs == cst->xrefs);
 510                 KKASSERT(ocst->end_offset + 1 == cst->beg_offset);
 511                 RB_REMOVE(ccms_rb_tree, &info->ds->tree, ocst);
 512                 cst->beg_offset = ocst->beg_offset;
 513                 cst->lrefs = ocst->lrefs;
 514                 if (ccms_enable >= 9) {
 515                     kprintf("MERGELEFT %p %lld-%lld (%d)\n",
 516                            ocst, cst->beg_offset, cst->end_offset,
 517                            cst->blocked);
 518                 }
 519                 if (ocst->blocked) {
 520                     ocst->blocked = 0;
 521                     wakeup(ocst);
 522                 }
 523                 objcache_put(ccms_oc, ocst);
 524             }
 525         }
 526     }
 527     if (lock->end_offset == cst->end_offset) {
 528         --cst->rrefs;
 529         if (cst->rrefs == 0) {
 530             if ((ocst = RB_NEXT(ccms_rb_tree, &info->ds->tree, cst)) != NULL &&
 531                 ocst->lrefs == 0 &&
 532                 ocst->state == cst->state &&
 533                 ocst->sharecount == cst->sharecount
 534             ) {
 535                 KKASSERT(ocst->xrefs == cst->xrefs);
 536                 KKASSERT(cst->end_offset + 1 == ocst->beg_offset);
 537                 RB_REMOVE(ccms_rb_tree, &info->ds->tree, ocst);
 538                 cst->end_offset = ocst->end_offset;
 539                 cst->rrefs = ocst->rrefs;
 540                 if (ccms_enable >= 9) {
 541                     kprintf("MERGERIGHT %p %lld-%lld\n",
 542                            ocst, cst->beg_offset, cst->end_offset);
 543                 }
 544                 objcache_put(ccms_oc, ocst);
 545             }
 546         }
 547     }
 548     return(0);
 549 }
 550
 551
 552 /*
 553  * RB tree compare function for insertions and deletions.  This function
 554  * compares two CSTs.
 555  */
 556 static int
 557 ccms_cst_cmp(ccms_cst_t b1, ccms_cst_t b2)
 558 {
 559     if (b1->end_offset < b2->beg_offset)
 560         return(-1);
 561     if (b1->beg_offset > b2->end_offset)
 562         return(1);
 563     return(0);
 564 }
 565
 566 /*
 567  * RB tree scanning compare function.  This function compares the CST
 568  * from the tree against the supplied ccms_lock and returns the CST's
 569  * placement relative to the lock.
 570  */
 571 static int
 572 ccms_lock_scan_cmp(ccms_cst_t cst, void *arg)
 573 {
 574     struct ccms_lock_scan_info *info = arg;
 575     ccms_lock_t lock = info->lock;
 576
 577     if (cst->end_offset < lock->beg_offset)
 578         return(-1);
 579     if (cst->beg_offset > lock->end_offset)
 580         return(1);
 581     return(0);
 582 }
 583
 584 /*
 585  * This function works like ccms_lock_scan_cmp but terminates at the
 586  * collision point rather then at the lock's ending offset.  Only
 587  * the CSTs that were already partially resolved are returned by the scan.
 588  */
 589 static int
 590 ccms_lock_undo_cmp(ccms_cst_t cst, void *arg)
 591 {
 592     struct ccms_lock_scan_info *info = arg;
 593     ccms_lock_t lock = info->lock;
 594
 595     if (cst->end_offset < lock->beg_offset)
 596         return(-1);
 597     if (cst->beg_offset >= info->coll_cst->beg_offset)
 598         return(1);
 599     return(0);
 600 }
 601