2 * Copyright (c) 2006,2012 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"
54 * Initialize a new CCMS dataspace. Create a new RB tree with a single
55 * element covering the entire 64 bit offset range. This simplifies
56 * algorithms enormously by removing a number of special cases.
59 ccms_domain_init(ccms_domain_t *dom)
61 bzero(dom, sizeof(*dom));
62 /*kmalloc_create(&dom->mcst, "CCMS-cst");*/
63 /*dom->root.domain = dom;*/
67 ccms_domain_uninit(ccms_domain_t *dom)
69 /*kmalloc_destroy(&dom->mcst);*/
73 ccms_cst_init(ccms_cst_t *cst, void *handle)
75 bzero(cst, sizeof(*cst));
76 spin_init(&cst->spin);
81 ccms_cst_uninit(ccms_cst_t *cst)
83 KKASSERT(cst->count == 0);
84 if (cst->state != CCMS_STATE_INVALID) {
92 * Acquire an operational CCMS lock on multiple CSTs.
94 * This code is in the critical path and highly streamlined.
97 ccms_lock_get(ccms_lock_t *lock)
99 ccms_inode_t *cino = lock->cino;
102 lock->flags &= ~CCMS_LOCK_FAILED;
105 * Acquire all local locks first, then resolve them against the
106 * remote cache state. Order is important here.
109 KKASSERT(lock->req_d <= lock->req_t);
110 KKASSERT(lock->req_a <= lock->req_t);
111 ccms_thread_lock(&cino->topo_cst, lock->req_t);
114 ccms_thread_lock(&cino->attr_cst, lock->req_a);
116 ccms_thread_lock(&cino->data_cst[0], lock->req_d);
119 * Once the local locks are established the CST grant state cannot
120 * be pulled out from under us. However, it is entirely possible
121 * to deadlock on it so when CST grant state cannot be obtained
122 * trivially we have to unwind our local locks, then get the state,
125 if (lock->req_t > cino->topo_cst.state) {
126 ccms_rstate_get(lock, &cino->topo_cst, lock->req_t);
127 } else if (cino->topo_cst.state == CCMS_STATE_INVALID) {
128 ccms_rstate_get(lock, &cino->topo_cst, CCMS_STATE_ALLOWED);
129 } else if (cino->topo_cst.state == CCMS_STATE_SHARED &&
130 (lock->req_d > CCMS_STATE_SHARED ||
131 lock->req_a > CCMS_STATE_SHARED)) {
132 ccms_rstate_get(lock, &cino->topo_cst, CCMS_STATE_ALLOWED);
134 /* else the rstate is compatible */
136 if (lock->req_a > cino->attr_cst.state)
137 ccms_rstate_get(lock, &cino->attr_cst, lock->req_a);
139 if (lock->req_d > cino->data_cst[0].state)
140 ccms_rstate_get(lock, &cino->data_cst[0], lock->req_d);
143 * If the ccms_rstate_get() code deadlocks (or even if it just
144 * blocks), it will release all local locks and set the FAILED
145 * bit. The routine will still acquire the requested remote grants
146 * before returning but since the local locks are lost at that
147 * point the remote grants are no longer protected and we have to
150 if (lock->flags & CCMS_LOCK_FAILED) {
156 * Release a previously acquired CCMS lock.
159 ccms_lock_put(ccms_lock_t *lock)
161 ccms_inode_t *cino = lock->cino;
164 ccms_thread_unlock(&cino->data_cst[0]);
167 ccms_thread_unlock(&cino->attr_cst);
170 ccms_thread_unlock(&cino->topo_cst);
176 /************************************************************************
177 * CST SUPPORT FUNCTIONS *
178 ************************************************************************/
181 * Acquire local cache state & lock. If the current thread already holds
182 * the lock exclusively we bump the exclusive count, even if the thread is
183 * trying to get a shared lock.
186 ccms_thread_lock(ccms_cst_t *cst, ccms_state_t state)
189 * Regardless of the type of lock requested if the current thread
190 * already holds an exclusive lock we bump the exclusive count and
191 * return. This requires no spinlock.
193 if (cst->count < 0 && cst->td == curthread) {
199 * Otherwise use the spinlock to interlock the operation and sleep
202 spin_lock(&cst->spin);
203 if (state == CCMS_STATE_SHARED) {
204 while (cst->count < 0 || cst->upgrade) {
206 ssleep(cst, &cst->spin, 0, "ccmslck", hz);
209 KKASSERT(cst->td == NULL);
210 } else if (state == CCMS_STATE_EXCLUSIVE) {
211 while (cst->count != 0 || cst->upgrade) {
213 ssleep(cst, &cst->spin, 0, "ccmslck", hz);
218 spin_unlock(&cst->spin);
219 panic("ccms_thread_lock: bad state %d\n", state);
221 spin_unlock(&cst->spin);
225 * Same as ccms_thread_lock() but acquires the lock non-blocking. Returns
226 * 0 on success, EBUSY on failure.
229 ccms_thread_lock_nonblock(ccms_cst_t *cst, ccms_state_t state)
231 if (cst->count < 0 && cst->td == curthread) {
236 spin_lock(&cst->spin);
237 if (state == CCMS_STATE_SHARED) {
238 if (cst->count < 0 || cst->upgrade) {
239 spin_unlock(&cst->spin);
243 KKASSERT(cst->td == NULL);
244 } else if (state == CCMS_STATE_EXCLUSIVE) {
245 if (cst->count != 0 || cst->upgrade) {
246 spin_unlock(&cst->spin);
252 spin_unlock(&cst->spin);
253 panic("ccms_thread_lock_nonblock: bad state %d\n", state);
255 spin_unlock(&cst->spin);
260 * Temporarily upgrade a thread lock for making local structural changes.
261 * No new shared or exclusive locks can be acquired by others while we are
262 * upgrading, but other upgraders are allowed.
265 ccms_thread_lock_upgrade(ccms_cst_t *cst)
268 * Nothing to do if already exclusive
270 if (cst->count < 0) {
271 KKASSERT(cst->td == curthread);
272 return(CCMS_STATE_EXCLUSIVE);
276 * Convert a shared lock to exclusive.
278 if (cst->count > 0) {
279 spin_lock(&cst->spin);
284 ssleep(cst, &cst->spin, 0, "ccmsupg", hz);
288 spin_unlock(&cst->spin);
289 return(CCMS_STATE_SHARED);
291 panic("ccms_thread_lock_upgrade: not locked");
297 ccms_thread_lock_restore(ccms_cst_t *cst, ccms_state_t ostate)
299 if (ostate == CCMS_STATE_SHARED) {
300 KKASSERT(cst->td == curthread);
301 KKASSERT(cst->count == -1);
302 spin_lock(&cst->spin);
308 spin_unlock(&cst->spin);
311 spin_unlock(&cst->spin);
317 * Release a local thread lock
320 ccms_thread_unlock(ccms_cst_t *cst)
322 if (cst->count < 0) {
323 KKASSERT(cst->td == curthread);
324 if (cst->count < -1) {
328 spin_lock(&cst->spin);
329 KKASSERT(cst->count == -1);
334 spin_unlock(&cst->spin);
338 spin_unlock(&cst->spin);
339 } else if (cst->count > 0) {
340 spin_lock(&cst->spin);
341 if (--cst->count == 0 && cst->blocked) {
343 spin_unlock(&cst->spin);
347 spin_unlock(&cst->spin);
349 panic("ccms_thread_unlock: bad zero count\n");
354 * Release a local thread lock with special handling of the last lock
357 * If no upgrades are in progress then the last reference to the lock will
358 * upgrade the lock to exclusive (if it was shared) and return 0 without
361 * If more than one reference remains, or upgrades are in progress,
362 * we drop the reference and return non-zero to indicate that more
363 * locks are present or pending.
366 ccms_thread_unlock_zero(ccms_cst_t *cst)
368 if (cst->count < 0) {
370 * Exclusive owned by us, no races possible as long as it
371 * remains negative. Return 0 and leave us locked on the
374 KKASSERT(cst->td == curthread);
375 if (cst->count == -1) {
376 spin_lock(&cst->spin);
381 spin_unlock(&cst->spin);
384 spin_unlock(&cst->spin);
388 spin_unlock(&cst->spin);
394 * Convert the last shared lock to an exclusive lock
397 * If there are upgrades pending the cst is unlocked and
398 * the upgrade waiters are woken up. The upgrade count
399 * prevents new exclusive holders for the duration.
401 spin_lock(&cst->spin);
402 KKASSERT(cst->count > 0);
403 if (cst->count == 1) {
408 spin_unlock(&cst->spin);
411 spin_unlock(&cst->spin);
417 spin_unlock(&cst->spin);
422 spin_unlock(&cst->spin);
428 ccms_thread_lock_owned(ccms_cst_t *cst)
430 return(cst->count < 0 && cst->td == curthread);
436 * Acquire remote grant state. This routine can be used to upgrade or
437 * downgrade the state. If it blocks it will release any local locks
438 * acquired via (lock) but then it will continue getting the requested
443 ccms_rstate_get(ccms_lock_t *lock, ccms_cst_t *cst, ccms_state_t state)