1 /* 2 * Copyright (c) 2006,2012 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 /* 35 * The Cache Coherency Management System (CCMS) 36 */ 37 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> 44 #include <sys/uio.h> 45 #include <machine/limits.h> 46 47 #include <sys/spinlock2.h> 48 49 #include "hammer2_ccms.h" 50 51 int ccms_debug = 0; 52 53 /* 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. 57 */ 58 void 59 ccms_domain_init(ccms_domain_t *dom) 60 { 61 bzero(dom, sizeof(*dom)); 62 /*kmalloc_create(&dom->mcst, "CCMS-cst");*/ 63 /*dom->root.domain = dom;*/ 64 } 65 66 void 67 ccms_domain_uninit(ccms_domain_t *dom) 68 { 69 /*kmalloc_destroy(&dom->mcst);*/ 70 } 71 72 void 73 ccms_cst_init(ccms_cst_t *cst, void *handle) 74 { 75 bzero(cst, sizeof(*cst)); 76 spin_init(&cst->spin); 77 cst->handle = handle; 78 } 79 80 void 81 ccms_cst_uninit(ccms_cst_t *cst) 82 { 83 KKASSERT(cst->count == 0); 84 if (cst->state != CCMS_STATE_INVALID) { 85 /* XXX */ 86 } 87 cst->handle = NULL; 88 } 89 90 #if 0 91 /* 92 * Acquire an operational CCMS lock on multiple CSTs. 93 * 94 * This code is in the critical path and highly streamlined. 95 */ 96 void 97 ccms_lock_get(ccms_lock_t *lock) 98 { 99 ccms_inode_t *cino = lock->cino; 100 101 again: 102 lock->flags &= ~CCMS_LOCK_FAILED; 103 104 /* 105 * Acquire all local locks first, then resolve them against the 106 * remote cache state. Order is important here. 107 */ 108 if (lock->req_t) { 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); 112 } 113 if (lock->req_a) 114 ccms_thread_lock(&cino->attr_cst, lock->req_a); 115 if (lock->req_d) 116 ccms_thread_lock(&cino->data_cst[0], lock->req_d); 117 118 /* 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, 123 * and then loop. 124 */ 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); 133 } 134 /* else the rstate is compatible */ 135 136 if (lock->req_a > cino->attr_cst.state) 137 ccms_rstate_get(lock, &cino->attr_cst, lock->req_a); 138 139 if (lock->req_d > cino->data_cst[0].state) 140 ccms_rstate_get(lock, &cino->data_cst[0], lock->req_d); 141 142 /* 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 148 * retry. 149 */ 150 if (lock->flags & CCMS_LOCK_FAILED) { 151 goto again; 152 } 153 } 154 155 /* 156 * Release a previously acquired CCMS lock. 157 */ 158 void 159 ccms_lock_put(ccms_lock_t *lock) 160 { 161 ccms_inode_t *cino = lock->cino; 162 163 if (lock->req_d) { 164 ccms_thread_unlock(&cino->data_cst[0]); 165 } 166 if (lock->req_a) { 167 ccms_thread_unlock(&cino->attr_cst); 168 } 169 if (lock->req_t) { 170 ccms_thread_unlock(&cino->topo_cst); 171 } 172 } 173 174 #endif 175 176 /************************************************************************ 177 * CST SUPPORT FUNCTIONS * 178 ************************************************************************/ 179 180 /* 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. 184 */ 185 void 186 ccms_thread_lock(ccms_cst_t *cst, ccms_state_t state) 187 { 188 /* 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. 192 */ 193 if (cst->count < 0 && cst->td == curthread) { 194 --cst->count; 195 return; 196 } 197 198 /* 199 * Otherwise use the spinlock to interlock the operation and sleep 200 * as necessary. 201 */ 202 spin_lock(&cst->spin); 203 if (state == CCMS_STATE_SHARED) { 204 while (cst->count < 0 || cst->upgrade) { 205 cst->blocked = 1; 206 ssleep(cst, &cst->spin, 0, "ccmslck", hz); 207 } 208 ++cst->count; 209 KKASSERT(cst->td == NULL); 210 } else if (state == CCMS_STATE_EXCLUSIVE) { 211 while (cst->count != 0 || cst->upgrade) { 212 cst->blocked = 1; 213 ssleep(cst, &cst->spin, 0, "ccmslck", hz); 214 } 215 cst->count = -1; 216 cst->td = curthread; 217 } else { 218 spin_unlock(&cst->spin); 219 panic("ccms_thread_lock: bad state %d\n", state); 220 } 221 spin_unlock(&cst->spin); 222 } 223 224 /* 225 * Same as ccms_thread_lock() but acquires the lock non-blocking. Returns 226 * 0 on success, EBUSY on failure. 227 */ 228 int 229 ccms_thread_lock_nonblock(ccms_cst_t *cst, ccms_state_t state) 230 { 231 if (cst->count < 0 && cst->td == curthread) { 232 --cst->count; 233 return(0); 234 } 235 236 spin_lock(&cst->spin); 237 if (state == CCMS_STATE_SHARED) { 238 if (cst->count < 0 || cst->upgrade) { 239 spin_unlock(&cst->spin); 240 return (EBUSY); 241 } 242 ++cst->count; 243 KKASSERT(cst->td == NULL); 244 } else if (state == CCMS_STATE_EXCLUSIVE) { 245 if (cst->count != 0 || cst->upgrade) { 246 spin_unlock(&cst->spin); 247 return (EBUSY); 248 } 249 cst->count = -1; 250 cst->td = curthread; 251 } else { 252 spin_unlock(&cst->spin); 253 panic("ccms_thread_lock_nonblock: bad state %d\n", state); 254 } 255 spin_unlock(&cst->spin); 256 return(0); 257 } 258 259 /* 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. 263 */ 264 ccms_state_t 265 ccms_thread_lock_upgrade(ccms_cst_t *cst) 266 { 267 /* 268 * Nothing to do if already exclusive 269 */ 270 if (cst->count < 0) { 271 KKASSERT(cst->td == curthread); 272 return(CCMS_STATE_EXCLUSIVE); 273 } 274 275 /* 276 * Convert a shared lock to exclusive. 277 */ 278 if (cst->count > 0) { 279 spin_lock(&cst->spin); 280 ++cst->upgrade; 281 --cst->count; 282 while (cst->count) { 283 cst->blocked = 1; 284 ssleep(cst, &cst->spin, 0, "ccmsupg", hz); 285 } 286 cst->count = -1; 287 cst->td = curthread; 288 spin_unlock(&cst->spin); 289 return(CCMS_STATE_SHARED); 290 } 291 panic("ccms_thread_lock_upgrade: not locked"); 292 /* NOT REACHED */ 293 return(0); 294 } 295 296 void 297 ccms_thread_lock_restore(ccms_cst_t *cst, ccms_state_t ostate) 298 { 299 if (ostate == CCMS_STATE_SHARED) { 300 KKASSERT(cst->td == curthread); 301 KKASSERT(cst->count == -1); 302 spin_lock(&cst->spin); 303 --cst->upgrade; 304 cst->count = 1; 305 cst->td = NULL; 306 if (cst->blocked) { 307 cst->blocked = 0; 308 spin_unlock(&cst->spin); 309 wakeup(cst); 310 } else { 311 spin_unlock(&cst->spin); 312 } 313 } 314 } 315 316 /* 317 * Release a local thread lock 318 */ 319 void 320 ccms_thread_unlock(ccms_cst_t *cst) 321 { 322 if (cst->count < 0) { 323 KKASSERT(cst->td == curthread); 324 if (cst->count < -1) { 325 ++cst->count; 326 return; 327 } 328 spin_lock(&cst->spin); 329 KKASSERT(cst->count == -1); 330 cst->count = 0; 331 cst->td = NULL; 332 if (cst->blocked) { 333 cst->blocked = 0; 334 spin_unlock(&cst->spin); 335 wakeup(cst); 336 return; 337 } 338 spin_unlock(&cst->spin); 339 } else if (cst->count > 0) { 340 spin_lock(&cst->spin); 341 if (--cst->count == 0 && cst->blocked) { 342 cst->blocked = 0; 343 spin_unlock(&cst->spin); 344 wakeup(cst); 345 return; 346 } 347 spin_unlock(&cst->spin); 348 } else { 349 panic("ccms_thread_unlock: bad zero count\n"); 350 } 351 } 352 353 /* 354 * Release a local thread lock with special handling of the last lock 355 * reference. 356 * 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 359 * unlocking it. 360 * 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. 364 */ 365 int 366 ccms_thread_unlock_zero(ccms_cst_t *cst) 367 { 368 if (cst->count < 0) { 369 /* 370 * Exclusive owned by us, no races possible as long as it 371 * remains negative. Return 0 and leave us locked on the 372 * last lock. 373 */ 374 KKASSERT(cst->td == curthread); 375 if (cst->count == -1) { 376 spin_lock(&cst->spin); 377 if (cst->upgrade) { 378 cst->count = 0; 379 if (cst->blocked) { 380 cst->blocked = 0; 381 spin_unlock(&cst->spin); 382 wakeup(cst); 383 } else { 384 spin_unlock(&cst->spin); 385 } 386 return(1); 387 } 388 spin_unlock(&cst->spin); 389 return(0); 390 } 391 ++cst->count; 392 } else { 393 /* 394 * Convert the last shared lock to an exclusive lock 395 * and return 0. 396 * 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. 400 */ 401 spin_lock(&cst->spin); 402 KKASSERT(cst->count > 0); 403 if (cst->count == 1) { 404 if (cst->upgrade) { 405 cst->count = 0; 406 if (cst->blocked) { 407 cst->blocked = 0; 408 spin_unlock(&cst->spin); 409 wakeup(cst); 410 } else { 411 spin_unlock(&cst->spin); 412 } 413 return(1); 414 } else { 415 cst->count = -1; 416 cst->td = curthread; 417 spin_unlock(&cst->spin); 418 return(0); 419 } 420 } 421 --cst->count; 422 spin_unlock(&cst->spin); 423 } 424 return(1); 425 } 426 427 int 428 ccms_thread_lock_owned(ccms_cst_t *cst) 429 { 430 return(cst->count < 0 && cst->td == curthread); 431 } 432 433 434 #if 0 435 /* 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 439 * remote grant. 440 */ 441 static 442 void 443 ccms_rstate_get(ccms_lock_t *lock, ccms_cst_t *cst, ccms_state_t state) 444 { 445 /* XXX */ 446 cst->state = state; 447 } 448 449 #endif 450