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 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 ccms_state_t 260 ccms_thread_lock_temp_release(ccms_cst_t *cst) 261 { 262 if (cst->count < 0) { 263 ccms_thread_unlock(cst); 264 return(CCMS_STATE_EXCLUSIVE); 265 } 266 if (cst->count > 0) { 267 ccms_thread_unlock(cst); 268 return(CCMS_STATE_SHARED); 269 } 270 return (CCMS_STATE_INVALID); 271 } 272 273 void 274 ccms_thread_lock_temp_restore(ccms_cst_t *cst, ccms_state_t ostate) 275 { 276 ccms_thread_lock(cst, ostate); 277 } 278 279 /* 280 * Temporarily upgrade a thread lock for making local structural changes. 281 * No new shared or exclusive locks can be acquired by others while we are 282 * upgrading, but other upgraders are allowed. 283 */ 284 ccms_state_t 285 ccms_thread_lock_upgrade(ccms_cst_t *cst) 286 { 287 /* 288 * Nothing to do if already exclusive 289 */ 290 if (cst->count < 0) { 291 KKASSERT(cst->td == curthread); 292 return(CCMS_STATE_EXCLUSIVE); 293 } 294 295 /* 296 * Convert a shared lock to exclusive. 297 */ 298 if (cst->count > 0) { 299 spin_lock(&cst->spin); 300 ++cst->upgrade; 301 --cst->count; 302 while (cst->count) { 303 cst->blocked = 1; 304 ssleep(cst, &cst->spin, 0, "ccmsupg", hz); 305 } 306 cst->count = -1; 307 cst->td = curthread; 308 spin_unlock(&cst->spin); 309 return(CCMS_STATE_SHARED); 310 } 311 panic("ccms_thread_lock_upgrade: not locked"); 312 /* NOT REACHED */ 313 return(0); 314 } 315 316 void 317 ccms_thread_lock_downgrade(ccms_cst_t *cst, ccms_state_t ostate) 318 { 319 if (ostate == CCMS_STATE_SHARED) { 320 KKASSERT(cst->td == curthread); 321 KKASSERT(cst->count == -1); 322 spin_lock(&cst->spin); 323 --cst->upgrade; 324 cst->count = 1; 325 cst->td = NULL; 326 if (cst->blocked) { 327 cst->blocked = 0; 328 spin_unlock(&cst->spin); 329 wakeup(cst); 330 } else { 331 spin_unlock(&cst->spin); 332 } 333 } 334 /* else nothing to do if excl->excl */ 335 } 336 337 /* 338 * Release a local thread lock 339 */ 340 void 341 ccms_thread_unlock(ccms_cst_t *cst) 342 { 343 if (cst->count < 0) { 344 /* 345 * Exclusive 346 */ 347 KKASSERT(cst->td == curthread); 348 if (cst->count < -1) { 349 ++cst->count; 350 return; 351 } 352 spin_lock(&cst->spin); 353 KKASSERT(cst->count == -1); 354 cst->count = 0; 355 cst->td = NULL; 356 if (cst->blocked) { 357 cst->blocked = 0; 358 spin_unlock(&cst->spin); 359 wakeup(cst); 360 return; 361 } 362 spin_unlock(&cst->spin); 363 } else if (cst->count > 0) { 364 /* 365 * Shared 366 */ 367 spin_lock(&cst->spin); 368 if (--cst->count == 0 && cst->blocked) { 369 cst->blocked = 0; 370 spin_unlock(&cst->spin); 371 wakeup(cst); 372 return; 373 } 374 spin_unlock(&cst->spin); 375 } else { 376 panic("ccms_thread_unlock: bad zero count\n"); 377 } 378 } 379 380 void 381 ccms_thread_lock_setown(ccms_cst_t *cst) 382 { 383 KKASSERT(cst->count < 0); 384 cst->td = curthread; 385 } 386 387 /* 388 * Release a previously upgraded local thread lock 389 */ 390 void 391 ccms_thread_unlock_upgraded(ccms_cst_t *cst, ccms_state_t ostate) 392 { 393 if (ostate == CCMS_STATE_SHARED) { 394 KKASSERT(cst->td == curthread); 395 KKASSERT(cst->count == -1); 396 spin_lock(&cst->spin); 397 --cst->upgrade; 398 cst->count = 0; 399 cst->td = NULL; 400 if (cst->blocked) { 401 cst->blocked = 0; 402 spin_unlock(&cst->spin); 403 wakeup(cst); 404 } else { 405 spin_unlock(&cst->spin); 406 } 407 } else { 408 ccms_thread_unlock(cst); 409 } 410 } 411 412 #if 0 413 /* 414 * Release a local thread lock with special handling of the last lock 415 * reference. 416 * 417 * If no upgrades are in progress then the last reference to the lock will 418 * upgrade the lock to exclusive (if it was shared) and return 0 without 419 * unlocking it. 420 * 421 * If more than one reference remains, or upgrades are in progress, 422 * we drop the reference and return non-zero to indicate that more 423 * locks are present or pending. 424 */ 425 int 426 ccms_thread_unlock_zero(ccms_cst_t *cst) 427 { 428 if (cst->count < 0) { 429 /* 430 * Exclusive owned by us, no races possible as long as it 431 * remains negative. Return 0 and leave us locked on the 432 * last lock. 433 */ 434 KKASSERT(cst->td == curthread); 435 if (cst->count == -1) { 436 spin_lock(&cst->spin); 437 if (cst->upgrade) { 438 cst->count = 0; 439 if (cst->blocked) { 440 cst->blocked = 0; 441 spin_unlock(&cst->spin); 442 wakeup(cst); 443 } else { 444 spin_unlock(&cst->spin); 445 } 446 return(1); 447 } 448 spin_unlock(&cst->spin); 449 return(0); 450 } 451 ++cst->count; 452 } else { 453 /* 454 * Convert the last shared lock to an exclusive lock 455 * and return 0. 456 * 457 * If there are upgrades pending the cst is unlocked and 458 * the upgrade waiters are woken up. The upgrade count 459 * prevents new exclusive holders for the duration. 460 */ 461 spin_lock(&cst->spin); 462 KKASSERT(cst->count > 0); 463 if (cst->count == 1) { 464 if (cst->upgrade) { 465 cst->count = 0; 466 if (cst->blocked) { 467 cst->blocked = 0; 468 spin_unlock(&cst->spin); 469 wakeup(cst); 470 } else { 471 spin_unlock(&cst->spin); 472 } 473 return(1); 474 } else { 475 cst->count = -1; 476 cst->td = curthread; 477 spin_unlock(&cst->spin); 478 return(0); 479 } 480 } 481 --cst->count; 482 spin_unlock(&cst->spin); 483 } 484 return(1); 485 } 486 #endif 487 488 int 489 ccms_thread_lock_owned(ccms_cst_t *cst) 490 { 491 return(cst->count < 0 && cst->td == curthread); 492 } 493 494 495 #if 0 496 /* 497 * Acquire remote grant state. This routine can be used to upgrade or 498 * downgrade the state. If it blocks it will release any local locks 499 * acquired via (lock) but then it will continue getting the requested 500 * remote grant. 501 */ 502 static 503 void 504 ccms_rstate_get(ccms_lock_t *lock, ccms_cst_t *cst, ccms_state_t state) 505 { 506 /* XXX */ 507 cst->state = state; 508 } 509 510 #endif 511