56b2c29a90819b234c618053c6ca0572ad0c242b
[dragonfly.git] / 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