1 /* 2 * Copyright (c) 2006,2012-2014 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 #include "hammer2.h" 51 52 int ccms_debug = 0; 53 54 /* 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. 58 */ 59 void 60 ccms_domain_init(ccms_domain_t *dom) 61 { 62 bzero(dom, sizeof(*dom)); 63 /*kmalloc_create(&dom->mcst, "CCMS-cst");*/ 64 /*dom->root.domain = dom;*/ 65 } 66 67 void 68 ccms_domain_uninit(ccms_domain_t *dom) 69 { 70 /*kmalloc_destroy(&dom->mcst);*/ 71 } 72 73 void 74 ccms_cst_init(ccms_cst_t *cst, void *handle) 75 { 76 bzero(cst, sizeof(*cst)); 77 spin_init(&cst->spin, "ccmscst"); 78 cst->handle = handle; 79 } 80 81 void 82 ccms_cst_uninit(ccms_cst_t *cst) 83 { 84 KKASSERT(cst->count == 0); 85 if (cst->state != CCMS_STATE_INVALID) { 86 /* XXX */ 87 } 88 cst->handle = NULL; 89 } 90 91 #if 0 92 /* 93 * Acquire an operational CCMS lock on multiple CSTs. 94 * 95 * This code is in the critical path and highly streamlined. 96 */ 97 void 98 ccms_lock_get(ccms_lock_t *lock) 99 { 100 ccms_inode_t *cino = lock->cino; 101 102 again: 103 lock->flags &= ~CCMS_LOCK_FAILED; 104 105 /* 106 * Acquire all local locks first, then resolve them against the 107 * remote cache state. Order is important here. 108 */ 109 if (lock->req_t) { 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); 113 } 114 if (lock->req_a) 115 ccms_thread_lock(&cino->attr_cst, lock->req_a); 116 if (lock->req_d) 117 ccms_thread_lock(&cino->data_cst[0], lock->req_d); 118 119 /* 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, 124 * and then loop. 125 */ 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); 134 } 135 /* else the rstate is compatible */ 136 137 if (lock->req_a > cino->attr_cst.state) 138 ccms_rstate_get(lock, &cino->attr_cst, lock->req_a); 139 140 if (lock->req_d > cino->data_cst[0].state) 141 ccms_rstate_get(lock, &cino->data_cst[0], lock->req_d); 142 143 /* 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 149 * retry. 150 */ 151 if (lock->flags & CCMS_LOCK_FAILED) { 152 goto again; 153 } 154 } 155 156 /* 157 * Release a previously acquired CCMS lock. 158 */ 159 void 160 ccms_lock_put(ccms_lock_t *lock) 161 { 162 ccms_inode_t *cino = lock->cino; 163 164 if (lock->req_d) { 165 ccms_thread_unlock(&cino->data_cst[0]); 166 } 167 if (lock->req_a) { 168 ccms_thread_unlock(&cino->attr_cst); 169 } 170 if (lock->req_t) { 171 ccms_thread_unlock(&cino->topo_cst); 172 } 173 } 174 175 #endif 176 177 /************************************************************************ 178 * CST SUPPORT FUNCTIONS * 179 ************************************************************************/ 180 181 /* 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. 185 */ 186 void 187 ccms_thread_lock(ccms_cst_t *cst, ccms_state_t state) 188 { 189 /* 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. 193 */ 194 LOCKENTER; 195 if (cst->count < 0 && cst->td == curthread) { 196 --cst->count; 197 return; 198 } 199 200 /* 201 * Otherwise use the spinlock to interlock the operation and sleep 202 * as necessary. 203 */ 204 spin_lock(&cst->spin); 205 if (state == CCMS_STATE_SHARED) { 206 while (cst->count < 0 || cst->upgrade) { 207 cst->blocked = 1; 208 ssleep(cst, &cst->spin, 0, "ccmslck", hz); 209 } 210 ++cst->count; 211 KKASSERT(cst->td == NULL); 212 } else if (state == CCMS_STATE_EXCLUSIVE) { 213 while (cst->count != 0 || cst->upgrade) { 214 cst->blocked = 1; 215 ssleep(cst, &cst->spin, 0, "ccmslck", hz); 216 } 217 cst->count = -1; 218 cst->td = curthread; 219 } else { 220 spin_unlock(&cst->spin); 221 panic("ccms_thread_lock: bad state %d\n", state); 222 } 223 spin_unlock(&cst->spin); 224 } 225 226 /* 227 * Same as ccms_thread_lock() but acquires the lock non-blocking. Returns 228 * 0 on success, EBUSY on failure. 229 */ 230 int 231 ccms_thread_lock_nonblock(ccms_cst_t *cst, ccms_state_t state) 232 { 233 if (cst->count < 0 && cst->td == curthread) { 234 --cst->count; 235 LOCKENTER; 236 return(0); 237 } 238 239 spin_lock(&cst->spin); 240 if (state == CCMS_STATE_SHARED) { 241 if (cst->count < 0 || cst->upgrade) { 242 spin_unlock(&cst->spin); 243 return (EBUSY); 244 } 245 ++cst->count; 246 KKASSERT(cst->td == NULL); 247 } else if (state == CCMS_STATE_EXCLUSIVE) { 248 if (cst->count != 0 || cst->upgrade) { 249 spin_unlock(&cst->spin); 250 return (EBUSY); 251 } 252 cst->count = -1; 253 cst->td = curthread; 254 } else { 255 spin_unlock(&cst->spin); 256 panic("ccms_thread_lock_nonblock: bad state %d\n", state); 257 } 258 spin_unlock(&cst->spin); 259 LOCKENTER; 260 return(0); 261 } 262 263 ccms_state_t 264 ccms_thread_lock_temp_release(ccms_cst_t *cst) 265 { 266 if (cst->count < 0) { 267 ccms_thread_unlock(cst); 268 return(CCMS_STATE_EXCLUSIVE); 269 } 270 if (cst->count > 0) { 271 ccms_thread_unlock(cst); 272 return(CCMS_STATE_SHARED); 273 } 274 return (CCMS_STATE_INVALID); 275 } 276 277 void 278 ccms_thread_lock_temp_restore(ccms_cst_t *cst, ccms_state_t ostate) 279 { 280 ccms_thread_lock(cst, ostate); 281 } 282 283 /* 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. 287 */ 288 ccms_state_t 289 ccms_thread_lock_upgrade(ccms_cst_t *cst) 290 { 291 /* 292 * Nothing to do if already exclusive 293 */ 294 if (cst->count < 0) { 295 KKASSERT(cst->td == curthread); 296 return(CCMS_STATE_EXCLUSIVE); 297 } 298 299 /* 300 * Convert a shared lock to exclusive. 301 */ 302 if (cst->count > 0) { 303 spin_lock(&cst->spin); 304 ++cst->upgrade; 305 --cst->count; 306 while (cst->count) { 307 cst->blocked = 1; 308 ssleep(cst, &cst->spin, 0, "ccmsupg", hz); 309 } 310 cst->count = -1; 311 cst->td = curthread; 312 spin_unlock(&cst->spin); 313 return(CCMS_STATE_SHARED); 314 } 315 panic("ccms_thread_lock_upgrade: not locked"); 316 /* NOT REACHED */ 317 return(0); 318 } 319 320 void 321 ccms_thread_lock_downgrade(ccms_cst_t *cst, ccms_state_t ostate) 322 { 323 if (ostate == CCMS_STATE_SHARED) { 324 KKASSERT(cst->td == curthread); 325 KKASSERT(cst->count == -1); 326 spin_lock(&cst->spin); 327 --cst->upgrade; 328 cst->count = 1; 329 cst->td = NULL; 330 if (cst->blocked) { 331 cst->blocked = 0; 332 spin_unlock(&cst->spin); 333 wakeup(cst); 334 } else { 335 spin_unlock(&cst->spin); 336 } 337 } 338 /* else nothing to do if excl->excl */ 339 } 340 341 /* 342 * Release a local thread lock 343 */ 344 void 345 ccms_thread_unlock(ccms_cst_t *cst) 346 { 347 LOCKEXIT; 348 if (cst->count < 0) { 349 /* 350 * Exclusive 351 */ 352 KKASSERT(cst->td == curthread); 353 if (cst->count < -1) { 354 ++cst->count; 355 return; 356 } 357 spin_lock(&cst->spin); 358 KKASSERT(cst->count == -1); 359 cst->count = 0; 360 cst->td = NULL; 361 if (cst->blocked) { 362 cst->blocked = 0; 363 spin_unlock(&cst->spin); 364 wakeup(cst); 365 return; 366 } 367 spin_unlock(&cst->spin); 368 } else if (cst->count > 0) { 369 /* 370 * Shared 371 */ 372 spin_lock(&cst->spin); 373 if (--cst->count == 0 && cst->blocked) { 374 cst->blocked = 0; 375 spin_unlock(&cst->spin); 376 wakeup(cst); 377 return; 378 } 379 spin_unlock(&cst->spin); 380 } else { 381 panic("ccms_thread_unlock: bad zero count\n"); 382 } 383 } 384 385 void 386 ccms_thread_lock_setown(ccms_cst_t *cst) 387 { 388 KKASSERT(cst->count < 0); 389 cst->td = curthread; 390 } 391 392 /* 393 * Release a previously upgraded local thread lock 394 */ 395 void 396 ccms_thread_unlock_upgraded(ccms_cst_t *cst, ccms_state_t ostate) 397 { 398 if (ostate == CCMS_STATE_SHARED) { 399 LOCKEXIT; 400 KKASSERT(cst->td == curthread); 401 KKASSERT(cst->count == -1); 402 spin_lock(&cst->spin); 403 --cst->upgrade; 404 cst->count = 0; 405 cst->td = NULL; 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 } else { 414 ccms_thread_unlock(cst); 415 } 416 } 417 418 #if 0 419 /* 420 * Release a local thread lock with special handling of the last lock 421 * reference. 422 * 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 425 * unlocking it. 426 * 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. 430 */ 431 int 432 ccms_thread_unlock_zero(ccms_cst_t *cst) 433 { 434 if (cst->count < 0) { 435 /* 436 * Exclusive owned by us, no races possible as long as it 437 * remains negative. Return 0 and leave us locked on the 438 * last lock. 439 */ 440 KKASSERT(cst->td == curthread); 441 if (cst->count == -1) { 442 spin_lock(&cst->spin); 443 if (cst->upgrade) { 444 cst->count = 0; 445 if (cst->blocked) { 446 cst->blocked = 0; 447 spin_unlock(&cst->spin); 448 wakeup(cst); 449 } else { 450 spin_unlock(&cst->spin); 451 } 452 return(1); 453 } 454 spin_unlock(&cst->spin); 455 return(0); 456 } 457 ++cst->count; 458 } else { 459 /* 460 * Convert the last shared lock to an exclusive lock 461 * and return 0. 462 * 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. 466 */ 467 spin_lock(&cst->spin); 468 KKASSERT(cst->count > 0); 469 if (cst->count == 1) { 470 if (cst->upgrade) { 471 cst->count = 0; 472 if (cst->blocked) { 473 cst->blocked = 0; 474 spin_unlock(&cst->spin); 475 wakeup(cst); 476 } else { 477 spin_unlock(&cst->spin); 478 } 479 return(1); 480 } else { 481 cst->count = -1; 482 cst->td = curthread; 483 spin_unlock(&cst->spin); 484 return(0); 485 } 486 } 487 --cst->count; 488 spin_unlock(&cst->spin); 489 } 490 return(1); 491 } 492 #endif 493 494 int 495 ccms_thread_lock_owned(ccms_cst_t *cst) 496 { 497 return(cst->count < 0 && cst->td == curthread); 498 } 499 500 501 #if 0 502 /* 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 506 * remote grant. 507 */ 508 static 509 void 510 ccms_rstate_get(ccms_lock_t *lock, ccms_cst_t *cst, ccms_state_t state) 511 { 512 /* XXX */ 513 cst->state = state; 514 } 515 516 #endif 517