2 * Copyright (c) 2006,2012-2014 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
35 * The Cache Coherency Management System (CCMS)
38 #include <sys/param.h>
39 #include <sys/systm.h>
40 #include <sys/kernel.h>
41 #include <sys/malloc.h>
42 #include <sys/objcache.h>
43 #include <sys/sysctl.h>
45 #include <machine/limits.h>
47 #include <sys/spinlock2.h>
49 #include "hammer2_ccms.h"
55 * Initialize a new CCMS dataspace. Create a new RB tree with a single
56 * element covering the entire 64 bit offset range. This simplifies
57 * algorithms enormously by removing a number of special cases.
60 ccms_domain_init(ccms_domain_t *dom)
62 bzero(dom, sizeof(*dom));
63 /*kmalloc_create(&dom->mcst, "CCMS-cst");*/
64 /*dom->root.domain = dom;*/
68 ccms_domain_uninit(ccms_domain_t *dom)
70 /*kmalloc_destroy(&dom->mcst);*/
74 ccms_cst_init(ccms_cst_t *cst, void *handle)
76 bzero(cst, sizeof(*cst));
77 spin_init(&cst->spin, "ccmscst");
82 ccms_cst_uninit(ccms_cst_t *cst)
84 KKASSERT(cst->count == 0);
85 if (cst->state != CCMS_STATE_INVALID) {
93 * Acquire an operational CCMS lock on multiple CSTs.
95 * This code is in the critical path and highly streamlined.
98 ccms_lock_get(ccms_lock_t *lock)
100 ccms_inode_t *cino = lock->cino;
103 lock->flags &= ~CCMS_LOCK_FAILED;
106 * Acquire all local locks first, then resolve them against the
107 * remote cache state. Order is important here.
110 KKASSERT(lock->req_d <= lock->req_t);
111 KKASSERT(lock->req_a <= lock->req_t);
112 ccms_thread_lock(&cino->topo_cst, lock->req_t);
115 ccms_thread_lock(&cino->attr_cst, lock->req_a);
117 ccms_thread_lock(&cino->data_cst[0], lock->req_d);
120 * Once the local locks are established the CST grant state cannot
121 * be pulled out from under us. However, it is entirely possible
122 * to deadlock on it so when CST grant state cannot be obtained
123 * trivially we have to unwind our local locks, then get the state,
126 if (lock->req_t > cino->topo_cst.state) {
127 ccms_rstate_get(lock, &cino->topo_cst, lock->req_t);
128 } else if (cino->topo_cst.state == CCMS_STATE_INVALID) {
129 ccms_rstate_get(lock, &cino->topo_cst, CCMS_STATE_ALLOWED);
130 } else if (cino->topo_cst.state == CCMS_STATE_SHARED &&
131 (lock->req_d > CCMS_STATE_SHARED ||
132 lock->req_a > CCMS_STATE_SHARED)) {
133 ccms_rstate_get(lock, &cino->topo_cst, CCMS_STATE_ALLOWED);
135 /* else the rstate is compatible */
137 if (lock->req_a > cino->attr_cst.state)
138 ccms_rstate_get(lock, &cino->attr_cst, lock->req_a);
140 if (lock->req_d > cino->data_cst[0].state)
141 ccms_rstate_get(lock, &cino->data_cst[0], lock->req_d);
144 * If the ccms_rstate_get() code deadlocks (or even if it just
145 * blocks), it will release all local locks and set the FAILED
146 * bit. The routine will still acquire the requested remote grants
147 * before returning but since the local locks are lost at that
148 * point the remote grants are no longer protected and we have to
151 if (lock->flags & CCMS_LOCK_FAILED) {
157 * Release a previously acquired CCMS lock.
160 ccms_lock_put(ccms_lock_t *lock)
162 ccms_inode_t *cino = lock->cino;
165 ccms_thread_unlock(&cino->data_cst[0]);
168 ccms_thread_unlock(&cino->attr_cst);
171 ccms_thread_unlock(&cino->topo_cst);
177 /************************************************************************
178 * CST SUPPORT FUNCTIONS *
179 ************************************************************************/
182 * Acquire local cache state & lock. If the current thread already holds
183 * the lock exclusively we bump the exclusive count, even if the thread is
184 * trying to get a shared lock.
187 ccms_thread_lock(ccms_cst_t *cst, ccms_state_t state)
190 * Regardless of the type of lock requested if the current thread
191 * already holds an exclusive lock we bump the exclusive count and
192 * return. This requires no spinlock.
195 if (cst->count < 0 && cst->td == curthread) {
201 * Otherwise use the spinlock to interlock the operation and sleep
204 spin_lock(&cst->spin);
205 if (state == CCMS_STATE_SHARED) {
206 while (cst->count < 0 || cst->upgrade) {
208 ssleep(cst, &cst->spin, 0, "ccmslck", hz);
211 KKASSERT(cst->td == NULL);
212 } else if (state == CCMS_STATE_EXCLUSIVE) {
213 while (cst->count != 0 || cst->upgrade) {
215 ssleep(cst, &cst->spin, 0, "ccmslck", hz);
220 spin_unlock(&cst->spin);
221 panic("ccms_thread_lock: bad state %d\n", state);
223 spin_unlock(&cst->spin);
227 * Same as ccms_thread_lock() but acquires the lock non-blocking. Returns
228 * 0 on success, EBUSY on failure.
231 ccms_thread_lock_nonblock(ccms_cst_t *cst, ccms_state_t state)
233 if (cst->count < 0 && cst->td == curthread) {
239 spin_lock(&cst->spin);
240 if (state == CCMS_STATE_SHARED) {
241 if (cst->count < 0 || cst->upgrade) {
242 spin_unlock(&cst->spin);
246 KKASSERT(cst->td == NULL);
247 } else if (state == CCMS_STATE_EXCLUSIVE) {
248 if (cst->count != 0 || cst->upgrade) {
249 spin_unlock(&cst->spin);
255 spin_unlock(&cst->spin);
256 panic("ccms_thread_lock_nonblock: bad state %d\n", state);
258 spin_unlock(&cst->spin);
264 ccms_thread_lock_temp_release(ccms_cst_t *cst)
266 if (cst->count < 0) {
267 ccms_thread_unlock(cst);
268 return(CCMS_STATE_EXCLUSIVE);
270 if (cst->count > 0) {
271 ccms_thread_unlock(cst);
272 return(CCMS_STATE_SHARED);
274 return (CCMS_STATE_INVALID);
278 ccms_thread_lock_temp_restore(ccms_cst_t *cst, ccms_state_t ostate)
280 ccms_thread_lock(cst, ostate);
284 * Temporarily upgrade a thread lock for making local structural changes.
285 * No new shared or exclusive locks can be acquired by others while we are
286 * upgrading, but other upgraders are allowed.
289 ccms_thread_lock_upgrade(ccms_cst_t *cst)
292 * Nothing to do if already exclusive
294 if (cst->count < 0) {
295 KKASSERT(cst->td == curthread);
296 return(CCMS_STATE_EXCLUSIVE);
300 * Convert a shared lock to exclusive.
302 if (cst->count > 0) {
303 spin_lock(&cst->spin);
308 ssleep(cst, &cst->spin, 0, "ccmsupg", hz);
312 spin_unlock(&cst->spin);
313 return(CCMS_STATE_SHARED);
315 panic("ccms_thread_lock_upgrade: not locked");
321 ccms_thread_lock_downgrade(ccms_cst_t *cst, ccms_state_t ostate)
323 if (ostate == CCMS_STATE_SHARED) {
324 KKASSERT(cst->td == curthread);
325 KKASSERT(cst->count == -1);
326 spin_lock(&cst->spin);
332 spin_unlock(&cst->spin);
335 spin_unlock(&cst->spin);
338 /* else nothing to do if excl->excl */
342 * Release a local thread lock
345 ccms_thread_unlock(ccms_cst_t *cst)
348 if (cst->count < 0) {
352 KKASSERT(cst->td == curthread);
353 if (cst->count < -1) {
357 spin_lock(&cst->spin);
358 KKASSERT(cst->count == -1);
363 spin_unlock(&cst->spin);
367 spin_unlock(&cst->spin);
368 } else if (cst->count > 0) {
372 spin_lock(&cst->spin);
373 if (--cst->count == 0 && cst->blocked) {
375 spin_unlock(&cst->spin);
379 spin_unlock(&cst->spin);
381 panic("ccms_thread_unlock: bad zero count\n");
386 ccms_thread_lock_setown(ccms_cst_t *cst)
388 KKASSERT(cst->count < 0);
393 * Release a previously upgraded local thread lock
396 ccms_thread_unlock_upgraded(ccms_cst_t *cst, ccms_state_t ostate)
398 if (ostate == CCMS_STATE_SHARED) {
400 KKASSERT(cst->td == curthread);
401 KKASSERT(cst->count == -1);
402 spin_lock(&cst->spin);
408 spin_unlock(&cst->spin);
411 spin_unlock(&cst->spin);
414 ccms_thread_unlock(cst);
420 * Release a local thread lock with special handling of the last lock
423 * If no upgrades are in progress then the last reference to the lock will
424 * upgrade the lock to exclusive (if it was shared) and return 0 without
427 * If more than one reference remains, or upgrades are in progress,
428 * we drop the reference and return non-zero to indicate that more
429 * locks are present or pending.
432 ccms_thread_unlock_zero(ccms_cst_t *cst)
434 if (cst->count < 0) {
436 * Exclusive owned by us, no races possible as long as it
437 * remains negative. Return 0 and leave us locked on the
440 KKASSERT(cst->td == curthread);
441 if (cst->count == -1) {
442 spin_lock(&cst->spin);
447 spin_unlock(&cst->spin);
450 spin_unlock(&cst->spin);
454 spin_unlock(&cst->spin);
460 * Convert the last shared lock to an exclusive lock
463 * If there are upgrades pending the cst is unlocked and
464 * the upgrade waiters are woken up. The upgrade count
465 * prevents new exclusive holders for the duration.
467 spin_lock(&cst->spin);
468 KKASSERT(cst->count > 0);
469 if (cst->count == 1) {
474 spin_unlock(&cst->spin);
477 spin_unlock(&cst->spin);
483 spin_unlock(&cst->spin);
488 spin_unlock(&cst->spin);
495 ccms_thread_lock_owned(ccms_cst_t *cst)
497 return(cst->count < 0 && cst->td == curthread);
503 * Acquire remote grant state. This routine can be used to upgrade or
504 * downgrade the state. If it blocks it will release any local locks
505 * acquired via (lock) but then it will continue getting the requested
510 ccms_rstate_get(ccms_lock_t *lock, ccms_cst_t *cst, ccms_state_t state)