2 * Copyright (c) 2006 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
34 * $DragonFly: src/sys/kern/kern_ccms.c,v 1.2 2006/12/23 00:35:03 swildner Exp $
37 * The Cache Coherency Management System (CCMS)
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>
46 #include <sys/sysctl.h>
48 #include <machine/limits.h>
50 struct ccms_lock_scan_info {
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);
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");
71 static int ccms_enable;
72 SYSCTL_INT(_kern, OID_AUTO, ccms_enable, CTLFLAG_RW, &ccms_enable, 0, "");
74 static struct objcache *ccms_oc;
77 * Initialize the CCMS subsystem
82 ccms_oc = objcache_create_simple(M_CCMS, sizeof(struct ccms_cst));
83 kprintf("CCMSINIT\n");
85 SYSINIT(ccms, SI_SUB_OBJCACHE, SI_ORDER_ANY, ccmsinit, NULL);
88 * Initialize a new CCMS dataspace. Create a new RB tree with a single
89 * element covering the entire 64 bit offset range. This simplifies
90 * algorithms enormously by removing a number of special cases.
93 ccms_dataspace_init(ccms_dataspace_t ds)
100 cst = objcache_get(ccms_oc, M_WAITOK);
101 bzero(cst, sizeof(*cst));
102 cst->beg_offset = LLONG_MIN;
103 cst->end_offset = LLONG_MAX;
104 cst->state = CCMS_STATE_INVALID;
105 RB_INSERT(ccms_rb_tree, &ds->tree, cst);
109 * Destroy a CCMS dataspace.
112 ccms_dataspace_destroy(ccms_dataspace_t ds)
114 RB_SCAN(ccms_rb_tree, &ds->tree, NULL,
115 ccms_dataspace_destroy_match, ds);
120 ccms_dataspace_destroy_match(ccms_cst_t cst, void *arg)
122 ccms_dataspace_t ds = arg;
124 RB_REMOVE(ccms_rb_tree, &ds->tree, cst);
125 objcache_put(ccms_oc, cst);
133 ccms_lock_get(ccms_dataspace_t ds, ccms_lock_t lock)
135 struct ccms_lock_scan_info info;
137 if (ccms_enable == 0) {
143 * Partition the CST space so the precise range is covered and
144 * attempt to obtain the requested local lock (ltype) at the same
150 info.coll_cst = NULL;
151 info.cst1 = objcache_get(ccms_oc, M_WAITOK);
152 info.cst2 = objcache_get(ccms_oc, M_WAITOK);
154 RB_SCAN(ccms_rb_tree, &ds->tree, ccms_lock_scan_cmp,
155 ccms_lock_get_match, &info);
158 * If a collision occured, undo the fragments we were able to obtain,
159 * block, and try again.
161 while (info.coll_cst != NULL) {
162 RB_SCAN(ccms_rb_tree, &ds->tree, ccms_lock_undo_cmp,
163 ccms_lock_undo_match, &info);
164 info.coll_cst->blocked = 1;
165 tsleep(info.coll_cst, 0,
166 ((lock->ltype == CCMS_LTYPE_SHARED) ? "rngsh" : "rngex"),
168 info.coll_cst = NULL;
169 RB_SCAN(ccms_rb_tree, &ds->tree, ccms_lock_scan_cmp,
170 ccms_lock_redo_match, &info);
177 objcache_put(ccms_oc, info.cst1);
179 objcache_put(ccms_oc, info.cst2);
185 * Obtain a CCMS lock, initialize the lock structure from the uio.
188 ccms_lock_get_uio(ccms_dataspace_t ds, ccms_lock_t lock, struct uio *uio)
193 if (uio->uio_rw == UIO_READ)
194 ltype = CCMS_LTYPE_SHARED;
196 ltype = CCMS_LTYPE_MODIFYING;
199 * Calculate the ending offset (byte inclusive), make sure a seek
200 * overflow does not blow us up.
202 eoff = uio->uio_offset + uio->uio_resid - 1;
203 if (eoff < uio->uio_offset)
204 eoff = 0x7FFFFFFFFFFFFFFFLL;
205 ccms_lock_init(lock, uio->uio_offset, eoff, ltype);
206 return(ccms_lock_get(ds, lock));
211 ccms_lock_get_match(ccms_cst_t cst, void *arg)
213 struct ccms_lock_scan_info *info = arg;
214 ccms_lock_t lock = info->lock;
218 * If the lock's left edge is within the CST we must split the CST
219 * into two pieces [cst][ncst]. lrefs must be bumped on the CST
220 * containing the left edge.
222 * NOTE! cst->beg_offset may not be modified. This allows us to avoid
223 * having to manipulate the cst's position in the tree.
225 if (lock->beg_offset > cst->beg_offset) {
228 KKASSERT(ncst != NULL);
230 cst->end_offset = lock->beg_offset - 1;
232 ncst->beg_offset = lock->beg_offset;
234 RB_INSERT(ccms_rb_tree, &info->ds->tree, ncst);
237 * ncst becomes our 'matching' cst.
240 } else if (lock->beg_offset == cst->beg_offset) {
245 * If the lock's right edge is within the CST we must split the CST
246 * into two pieces [cst][ncst]. rrefs must be bumped on the CST
247 * containing the right edge.
249 * NOTE! cst->beg_offset may not be modified. This allows us to avoid
250 * having to manipulate the cst's position in the tree.
252 if (lock->end_offset < cst->end_offset) {
255 KKASSERT(ncst != NULL);
257 cst->end_offset = lock->end_offset;
259 ncst->beg_offset = lock->end_offset + 1;
261 RB_INSERT(ccms_rb_tree, &info->ds->tree, ncst);
262 /* cst remains our 'matching' cst */
263 } else if (lock->end_offset == cst->end_offset) {
268 * The lock covers the CST, so increment the CST's coverage count.
269 * Then attempt to obtain the shared/exclusive ltype.
273 if (info->coll_cst == NULL) {
274 switch(lock->ltype) {
275 case CCMS_LTYPE_SHARED:
276 if (cst->sharecount < 0) {
277 info->coll_cst = cst;
280 if (ccms_enable >= 9) {
281 kprintf("CST SHARE %d %lld-%lld\n", cst->sharecount,
282 cst->beg_offset, cst->end_offset);
286 case CCMS_LTYPE_EXCLUSIVE:
287 if (cst->sharecount != 0) {
288 info->coll_cst = cst;
291 if (ccms_enable >= 9) {
292 kprintf("CST EXCLS %d %lld-%lld\n", cst->sharecount,
293 cst->beg_offset, cst->end_offset);
297 case CCMS_LTYPE_MODIFYING:
298 if (cst->sharecount != 0) {
299 info->coll_cst = cst;
303 if (ccms_enable >= 9) {
304 kprintf("CST MODXL %d %lld-%lld\n", cst->sharecount,
305 cst->beg_offset, cst->end_offset);
315 * Undo a partially resolved ccms_ltype rangelock. This is atomic with
316 * the scan/redo code so there should not be any blocked locks when
317 * transitioning to 0.
321 ccms_lock_undo_match(ccms_cst_t cst, void *arg)
323 struct ccms_lock_scan_info *info = arg;
324 ccms_lock_t lock = info->lock;
326 switch(lock->ltype) {
327 case CCMS_LTYPE_SHARED:
328 KKASSERT(cst->sharecount > 0);
330 KKASSERT(cst->sharecount || cst->blocked == 0);
332 case CCMS_LTYPE_EXCLUSIVE:
333 KKASSERT(cst->sharecount < 0);
335 KKASSERT(cst->sharecount || cst->blocked == 0);
337 case CCMS_LTYPE_MODIFYING:
338 KKASSERT(cst->sharecount < 0 && cst->modifycount > 0);
341 KKASSERT(cst->sharecount || cst->blocked == 0);
348 * Redo the local lock request for a range which has already been
353 ccms_lock_redo_match(ccms_cst_t cst, void *arg)
355 struct ccms_lock_scan_info *info = arg;
356 ccms_lock_t lock = info->lock;
358 if (info->coll_cst == NULL) {
359 switch(lock->ltype) {
360 case CCMS_LTYPE_SHARED:
361 if (cst->sharecount < 0) {
362 info->coll_cst = cst;
364 if (ccms_enable >= 9) {
365 kprintf("CST SHARE %d %lld-%lld\n", cst->sharecount,
366 cst->beg_offset, cst->end_offset);
371 case CCMS_LTYPE_EXCLUSIVE:
372 if (cst->sharecount != 0) {
373 info->coll_cst = cst;
376 if (ccms_enable >= 9) {
377 kprintf("CST EXCLS %d %lld-%lld\n", cst->sharecount,
378 cst->beg_offset, cst->end_offset);
382 case CCMS_LTYPE_MODIFYING:
383 if (cst->sharecount != 0) {
384 info->coll_cst = cst;
388 if (ccms_enable >= 9) {
389 kprintf("CST MODXL %d %lld-%lld\n", cst->sharecount,
390 cst->beg_offset, cst->end_offset);
400 * Release a CCMS lock
403 ccms_lock_put(ccms_dataspace_t ds, ccms_lock_t lock)
405 struct ccms_lock_scan_info info;
407 if (lock->ds == NULL)
416 RB_SCAN(ccms_rb_tree, &ds->tree, ccms_lock_scan_cmp,
417 ccms_lock_put_match, &info);
420 objcache_put(ccms_oc, info.cst1);
422 objcache_put(ccms_oc, info.cst2);
428 ccms_lock_put_match(ccms_cst_t cst, void *arg)
430 struct ccms_lock_scan_info *info = arg;
431 ccms_lock_t lock = info->lock;
435 * Undo the local shared/exclusive rangelock.
437 switch(lock->ltype) {
438 case CCMS_LTYPE_SHARED:
439 KKASSERT(cst->sharecount > 0);
441 if (ccms_enable >= 9) {
442 kprintf("CST UNSHR %d %lld-%lld (%d)\n", cst->sharecount,
443 cst->beg_offset, cst->end_offset, cst->blocked);
445 if (cst->blocked && cst->sharecount == 0) {
450 case CCMS_LTYPE_EXCLUSIVE:
451 KKASSERT(cst->sharecount < 0);
453 if (ccms_enable >= 9) {
454 kprintf("CST UNEXC %d %lld-%lld (%d)\n", cst->sharecount,
455 cst->beg_offset, cst->end_offset, cst->blocked);
457 if (cst->blocked && cst->sharecount == 0) {
462 case CCMS_LTYPE_MODIFYING:
463 KKASSERT(cst->sharecount < 0 && cst->modifycount > 0);
466 if (ccms_enable >= 9) {
467 kprintf("CST UNMOD %d %lld-%lld (%d)\n", cst->sharecount,
468 cst->beg_offset, cst->end_offset, cst->blocked);
470 if (cst->blocked && cst->sharecount == 0) {
478 * Decrement the lock coverage count on the CST. Decrement the left and
479 * right edge counts as appropriate.
481 * When lrefs or rrefs drops to zero we check the adjacent entry to
482 * determine whether a merge is possible. If the appropriate refs field
483 * (rrefs for the entry to our left, lrefs for the entry to our right)
484 * is 0, then all covering locks must cover both entries and the xrefs
485 * field must match. We can then merge the entries if they have
486 * compatible cache states.
488 * However, because we are cleaning up the shared/exclusive count at
489 * the same time, the sharecount field may be temporarily out of
490 * sync, so require that the sharecount field also match before doing
493 * When merging an element which is being blocked on, the blocking
494 * thread(s) will be woken up.
496 * If the dataspace has too many CSTs we may be able to merge the
497 * entries even if their cache states are not the same, by dropping
498 * both to a compatible (lower) cache state and performing the appropriate
499 * management operations. XXX
502 if (lock->beg_offset == cst->beg_offset) {
504 if (cst->lrefs == 0) {
505 if ((ocst = RB_PREV(ccms_rb_tree, &info->ds->tree, cst)) != NULL &&
507 ocst->state == cst->state &&
508 ocst->sharecount == cst->sharecount
510 KKASSERT(ocst->xrefs == cst->xrefs);
511 KKASSERT(ocst->end_offset + 1 == cst->beg_offset);
512 RB_REMOVE(ccms_rb_tree, &info->ds->tree, ocst);
513 cst->beg_offset = ocst->beg_offset;
514 cst->lrefs = ocst->lrefs;
515 if (ccms_enable >= 9) {
516 kprintf("MERGELEFT %p %lld-%lld (%d)\n",
517 ocst, cst->beg_offset, cst->end_offset,
524 objcache_put(ccms_oc, ocst);
528 if (lock->end_offset == cst->end_offset) {
530 if (cst->rrefs == 0) {
531 if ((ocst = RB_NEXT(ccms_rb_tree, &info->ds->tree, cst)) != NULL &&
533 ocst->state == cst->state &&
534 ocst->sharecount == cst->sharecount
536 KKASSERT(ocst->xrefs == cst->xrefs);
537 KKASSERT(cst->end_offset + 1 == ocst->beg_offset);
538 RB_REMOVE(ccms_rb_tree, &info->ds->tree, ocst);
539 cst->end_offset = ocst->end_offset;
540 cst->rrefs = ocst->rrefs;
541 if (ccms_enable >= 9) {
542 kprintf("MERGERIGHT %p %lld-%lld\n",
543 ocst, cst->beg_offset, cst->end_offset);
545 objcache_put(ccms_oc, ocst);
554 * RB tree compare function for insertions and deletions. This function
558 ccms_cst_cmp(ccms_cst_t b1, ccms_cst_t b2)
560 if (b1->end_offset < b2->beg_offset)
562 if (b1->beg_offset > b2->end_offset)
568 * RB tree scanning compare function. This function compares the CST
569 * from the tree against the supplied ccms_lock and returns the CST's
570 * placement relative to the lock.
573 ccms_lock_scan_cmp(ccms_cst_t cst, void *arg)
575 struct ccms_lock_scan_info *info = arg;
576 ccms_lock_t lock = info->lock;
578 if (cst->end_offset < lock->beg_offset)
580 if (cst->beg_offset > lock->end_offset)
586 * This function works like ccms_lock_scan_cmp but terminates at the
587 * collision point rather then at the lock's ending offset. Only
588 * the CSTs that were already partially resolved are returned by the scan.
591 ccms_lock_undo_cmp(ccms_cst_t cst, void *arg)
593 struct ccms_lock_scan_info *info = arg;
594 ccms_lock_t lock = info->lock;
596 if (cst->end_offset < lock->beg_offset)
598 if (cst->beg_offset >= info->coll_cst->beg_offset)