1 /* $NetBSD: rf_stripelocks.c,v 1.34 2019/07/11 03:49:51 msaitoh Exp $ */ 2 /* 3 * Copyright (c) 1995 Carnegie-Mellon University. 4 * All rights reserved. 5 * 6 * Authors: Mark Holland, Jim Zelenka 7 * 8 * Permission to use, copy, modify and distribute this software and 9 * its documentation is hereby granted, provided that both the copyright 10 * notice and this permission notice appear in all copies of the 11 * software, derivative works or modified versions, and any portions 12 * thereof, and that both notices appear in supporting documentation. 13 * 14 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 15 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 16 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 17 * 18 * Carnegie Mellon requests users of this software to return to 19 * 20 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 21 * School of Computer Science 22 * Carnegie Mellon University 23 * Pittsburgh PA 15213-3890 24 * 25 * any improvements or extensions that they make and grant Carnegie the 26 * rights to redistribute these changes. 27 */ 28 29 /* 30 * stripelocks.c -- code to lock stripes for read and write access 31 * 32 * The code distinguishes between read locks and write locks. There can be 33 * as many readers to given stripe as desired. When a write request comes 34 * in, no further readers are allowed to enter, and all subsequent requests 35 * are queued in FIFO order. When a the number of readers goes to zero, the 36 * writer is given the lock. When a writer releases the lock, the list of 37 * queued requests is scanned, and all readersq up to the next writer are 38 * given the lock. 39 * 40 * The lock table size must be one less than a power of two, but HASH_STRIPEID 41 * is the only function that requires this. 42 * 43 * The code now supports "range locks". When you ask to lock a stripe, you 44 * specify a range of addresses in that stripe that you want to lock. When 45 * you acquire the lock, you've locked only this range of addresses, and 46 * other threads can concurrently read/write any non-overlapping portions 47 * of the stripe. The "addresses" that you lock are abstract in that you 48 * can pass in anything you like. The expectation is that you'll pass in 49 * the range of physical disk offsets of the parity bits you're planning 50 * to update. The idea behind this, of course, is to allow sub-stripe 51 * locking. The implementation is perhaps not the best imaginable; in the 52 * worst case a lock release is O(n^2) in the total number of outstanding 53 * requests to a given stripe. Note that if you're striping with a 54 * stripe unit size equal to an entire disk (i.e. not striping), there will 55 * be only one stripe and you may spend some significant number of cycles 56 * searching through stripe lock descriptors. 57 */ 58 59 #include <sys/cdefs.h> 60 __KERNEL_RCSID(0, "$NetBSD: rf_stripelocks.c,v 1.34 2019/07/11 03:49:51 msaitoh Exp $"); 61 62 #include <dev/raidframe/raidframevar.h> 63 64 #include "rf_raid.h" 65 #include "rf_stripelocks.h" 66 #include "rf_alloclist.h" 67 #include "rf_debugprint.h" 68 #include "rf_general.h" 69 #include "rf_driver.h" 70 #include "rf_shutdown.h" 71 72 #ifdef DEBUG 73 74 #define Dprintf1(s,a) rf_debug_printf(s,(void *)((unsigned long)a),NULL,NULL,NULL,NULL,NULL,NULL,NULL) 75 #define Dprintf2(s,a,b) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),NULL,NULL,NULL,NULL,NULL,NULL) 76 #define Dprintf3(s,a,b,c) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),NULL,NULL,NULL,NULL,NULL) 77 #define Dprintf4(s,a,b,c,d) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),NULL,NULL,NULL,NULL) 78 #define Dprintf5(s,a,b,c,d,e) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),NULL,NULL,NULL) 79 #define Dprintf6(s,a,b,c,d,e,f) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),(void *)((unsigned long)f),NULL,NULL) 80 #define Dprintf7(s,a,b,c,d,e,f,g) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),(void *)((unsigned long)f),(void *)((unsigned long)g),NULL) 81 #define Dprintf8(s,a,b,c,d,e,f,g,h) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),(void *)((unsigned long)f),(void *)((unsigned long)g),(void *)((unsigned long)h)) 82 83 #else /* DEBUG */ 84 85 #define Dprintf1(s,a) {} 86 #define Dprintf2(s,a,b) {} 87 #define Dprintf3(s,a,b,c) {} 88 #define Dprintf4(s,a,b,c,d) {} 89 #define Dprintf5(s,a,b,c,d,e) {} 90 #define Dprintf6(s,a,b,c,d,e,f) {} 91 #define Dprintf7(s,a,b,c,d,e,f,g) {} 92 #define Dprintf8(s,a,b,c,d,e,f,g,h) {} 93 94 #endif /* DEBUG */ 95 96 #define FLUSH 97 98 #define HASH_STRIPEID(_sid_) ( (_sid_) & (rf_lockTableSize-1) ) 99 100 static void AddToWaitersQueue(RF_StripeLockDesc_t * lockDesc, 101 RF_LockReqDesc_t * lockReqDesc); 102 static RF_StripeLockDesc_t *AllocStripeLockDesc(RF_StripeNum_t stripeID); 103 static void FreeStripeLockDesc(RF_StripeLockDesc_t * p); 104 static RF_LockTableEntry_t *rf_MakeLockTable(void); 105 #if RF_DEBUG_STRIPELOCK 106 static void PrintLockedStripes(RF_LockTableEntry_t * lockTable); 107 #endif 108 109 /* determines if two ranges overlap. always yields false if either 110 start value is negative */ 111 #define SINGLE_RANGE_OVERLAP(_strt1, _stop1, _strt2, _stop2) \ 112 ( (_strt1 >= 0) && (_strt2 >= 0) && \ 113 (RF_MAX(_strt1, _strt2) <= RF_MIN(_stop1, _stop2)) ) 114 115 /* determines if any of the ranges specified in the two lock 116 descriptors overlap each other */ 117 118 #define RANGE_OVERLAP(_cand, _pred) \ 119 ( SINGLE_RANGE_OVERLAP((_cand)->start, (_cand)->stop, \ 120 (_pred)->start, (_pred)->stop ) || \ 121 SINGLE_RANGE_OVERLAP((_cand)->start2, (_cand)->stop2, \ 122 (_pred)->start, (_pred)->stop ) || \ 123 SINGLE_RANGE_OVERLAP((_cand)->start, (_cand)->stop, \ 124 (_pred)->start2, (_pred)->stop2) || \ 125 SINGLE_RANGE_OVERLAP((_cand)->start2, (_cand)->stop2, \ 126 (_pred)->start2, (_pred)->stop2) ) 127 128 /* Determines if a candidate lock request conflicts with a predecessor 129 * lock req. Note that the arguments are not interchangeable. 130 * 131 * The rules are: 132 * 133 * a candidate read conflicts with a predecessor write if any 134 * ranges overlap 135 * 136 * a candidate write conflicts with a predecessor read if any 137 * ranges overlap 138 * 139 * a candidate write conflicts with a predecessor write if any 140 * ranges overlap */ 141 142 #define STRIPELOCK_CONFLICT(_cand, _pred) \ 143 RANGE_OVERLAP((_cand), (_pred)) && \ 144 ( ( (((_cand)->type == RF_IO_TYPE_READ) && \ 145 ((_pred)->type == RF_IO_TYPE_WRITE)) || \ 146 (((_cand)->type == RF_IO_TYPE_WRITE) && \ 147 ((_pred)->type == RF_IO_TYPE_READ)) || \ 148 (((_cand)->type == RF_IO_TYPE_WRITE) && \ 149 ((_pred)->type == RF_IO_TYPE_WRITE)) \ 150 ) \ 151 ) 152 153 #define RF_MAX_FREE_STRIPELOCK 128 154 #define RF_MIN_FREE_STRIPELOCK 32 155 156 static void rf_ShutdownStripeLocks(RF_LockTableEntry_t * lockTable); 157 static void rf_ShutdownStripeLockFreeList(void *); 158 static void rf_RaidShutdownStripeLocks(void *); 159 160 static void 161 rf_ShutdownStripeLockFreeList(void *ignored) 162 { 163 pool_destroy(&rf_pools.stripelock); 164 } 165 166 int 167 rf_ConfigureStripeLockFreeList(RF_ShutdownList_t **listp) 168 { 169 unsigned mask; 170 171 rf_pool_init(&rf_pools.stripelock, sizeof(RF_StripeLockDesc_t), 172 "rf_stripelock_pl", RF_MIN_FREE_STRIPELOCK, RF_MAX_FREE_STRIPELOCK); 173 rf_ShutdownCreate(listp, rf_ShutdownStripeLockFreeList, NULL); 174 175 for (mask = 0x1; mask; mask <<= 1) 176 if (rf_lockTableSize == mask) 177 break; 178 if (!mask) { 179 printf("[WARNING: lock table size must be a power of two. Setting to %d.]\n", RF_DEFAULT_LOCK_TABLE_SIZE); 180 rf_lockTableSize = RF_DEFAULT_LOCK_TABLE_SIZE; 181 } 182 return (0); 183 } 184 185 static void 186 rf_DestroyLockTable(RF_LockTableEntry_t *lockTable) 187 { 188 int i; 189 190 for (i = 0; i < rf_lockTableSize; i++) { 191 rf_destroy_mutex2(lockTable[i].mutex); 192 } 193 RF_Free(lockTable, rf_lockTableSize * sizeof(RF_LockTableEntry_t)); 194 } 195 196 static RF_LockTableEntry_t * 197 rf_MakeLockTable(void) 198 { 199 RF_LockTableEntry_t *lockTable; 200 int i; 201 202 lockTable = RF_Malloc(rf_lockTableSize * sizeof(*lockTable)); 203 if (lockTable == NULL) 204 return (NULL); 205 for (i = 0; i < rf_lockTableSize; i++) { 206 rf_init_mutex2(lockTable[i].mutex, IPL_VM); 207 } 208 return (lockTable); 209 } 210 211 static void 212 rf_ShutdownStripeLocks(RF_LockTableEntry_t * lockTable) 213 { 214 215 #if RF_DEBUG_STRIPELOCK 216 if (rf_stripeLockDebug) { 217 PrintLockedStripes(lockTable); 218 } 219 #endif 220 rf_DestroyLockTable(lockTable); 221 } 222 223 static void 224 rf_RaidShutdownStripeLocks(void *arg) 225 { 226 RF_Raid_t *raidPtr = (RF_Raid_t *) arg; 227 rf_ShutdownStripeLocks(raidPtr->lockTable); 228 } 229 230 int 231 rf_ConfigureStripeLocks(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr, 232 RF_Config_t *cfgPtr) 233 { 234 235 raidPtr->lockTable = rf_MakeLockTable(); 236 if (raidPtr->lockTable == NULL) 237 return (ENOMEM); 238 rf_ShutdownCreate(listp, rf_RaidShutdownStripeLocks, raidPtr); 239 240 return (0); 241 } 242 /* returns 0 if you've got the lock, and non-zero if you have to wait. 243 * if and only if you have to wait, we'll cause cbFunc to get invoked 244 * with cbArg when you are granted the lock. We store a tag in 245 * *releaseTag that you need to give back to us when you release the 246 * lock. */ 247 int 248 rf_AcquireStripeLock(RF_LockTableEntry_t *lockTable, RF_StripeNum_t stripeID, 249 RF_LockReqDesc_t *lockReqDesc) 250 { 251 RF_StripeLockDesc_t *lockDesc; 252 RF_StripeLockDesc_t *newlockDesc; 253 RF_LockReqDesc_t *p; 254 #if defined(DEBUG) && (RF_DEBUG_STRIPELOCK > 0) 255 int tid = 0; 256 #endif 257 int hashval = HASH_STRIPEID(stripeID); 258 int retcode = 0; 259 260 RF_ASSERT(RF_IO_IS_R_OR_W(lockReqDesc->type)); 261 262 #if RF_DEBUG_STRIPELOCK 263 if (rf_stripeLockDebug) { 264 if (stripeID == -1) { 265 Dprintf1("[%d] Lock acquisition suppressed (stripeID == -1)\n", tid); 266 } else { 267 Dprintf8("[%d] Trying to acquire stripe lock table 0x%lx SID %ld type %c range %ld-%ld, range2 %ld-%ld hashval %d\n", 268 tid, (unsigned long) lockTable, stripeID, lockReqDesc->type, lockReqDesc->start, 269 lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2); 270 Dprintf3("[%d] lock %ld hashval %d\n", tid, stripeID, hashval); 271 FLUSH; 272 } 273 } 274 #endif 275 if (stripeID == -1) 276 return (0); 277 lockReqDesc->next = NULL; /* just to be sure */ 278 newlockDesc = AllocStripeLockDesc(stripeID); 279 280 rf_lock_mutex2(lockTable[hashval].mutex); 281 for (lockDesc = lockTable[hashval].descList; lockDesc; 282 lockDesc = lockDesc->next) { 283 if (lockDesc->stripeID == stripeID) 284 break; 285 } 286 287 if (!lockDesc) { 288 /* no entry in table => no one reading or writing */ 289 lockDesc = newlockDesc; 290 lockDesc->next = lockTable[hashval].descList; 291 lockTable[hashval].descList = lockDesc; 292 if (lockReqDesc->type == RF_IO_TYPE_WRITE) 293 lockDesc->nWriters++; 294 lockDesc->granted = lockReqDesc; 295 #if RF_DEBUG_STRIPELOCK 296 if (rf_stripeLockDebug) { 297 Dprintf7("[%d] no one waiting: lock %ld %c %ld-%ld %ld-%ld granted\n", 298 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2); 299 FLUSH; 300 } 301 #endif 302 } else { 303 /* we won't be needing newlockDesc after all.. pity.. */ 304 FreeStripeLockDesc(newlockDesc); 305 306 if (lockReqDesc->type == RF_IO_TYPE_WRITE) 307 lockDesc->nWriters++; 308 309 if (lockDesc->nWriters == 0) { 310 /* no need to search any lists if there are no 311 * writers anywhere */ 312 lockReqDesc->next = lockDesc->granted; 313 lockDesc->granted = lockReqDesc; 314 #if RF_DEBUG_STRIPELOCK 315 if (rf_stripeLockDebug) { 316 Dprintf7("[%d] no writers: lock %ld %c %ld-%ld %ld-%ld granted\n", 317 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2); 318 FLUSH; 319 } 320 #endif 321 } else { 322 323 /* search the granted & waiting lists for a 324 * conflict. stop searching as soon as we 325 * find one */ 326 retcode = 0; 327 for (p = lockDesc->granted; p; p = p->next) 328 if (STRIPELOCK_CONFLICT(lockReqDesc, p)) { 329 retcode = 1; 330 break; 331 } 332 if (!retcode) 333 for (p = lockDesc->waitersH; p; p = p->next) 334 if (STRIPELOCK_CONFLICT(lockReqDesc, p)) { 335 retcode = 2; 336 break; 337 } 338 if (!retcode) { 339 /* no conflicts found => grant lock */ 340 lockReqDesc->next = lockDesc->granted; 341 lockDesc->granted = lockReqDesc; 342 #if RF_DEBUG_STRIPELOCK 343 if (rf_stripeLockDebug) { 344 Dprintf7("[%d] no conflicts: lock %ld %c %ld-%ld %ld-%ld granted\n", 345 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, 346 lockReqDesc->start2, lockReqDesc->stop2); 347 FLUSH; 348 } 349 #endif 350 } else { 351 #if RF_DEBUG_STRIPELOCK 352 if (rf_stripeLockDebug) { 353 Dprintf6("[%d] conflict: lock %ld %c %ld-%ld hashval=%d not granted\n", 354 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, 355 hashval); 356 Dprintf3("[%d] lock %ld retcode=%d\n", tid, stripeID, retcode); 357 FLUSH; 358 } 359 #endif 360 AddToWaitersQueue(lockDesc, lockReqDesc); 361 /* conflict => the current access must wait */ 362 } 363 } 364 } 365 366 rf_unlock_mutex2(lockTable[hashval].mutex); 367 return (retcode); 368 } 369 370 void 371 rf_ReleaseStripeLock(RF_LockTableEntry_t *lockTable, RF_StripeNum_t stripeID, 372 RF_LockReqDesc_t *lockReqDesc) 373 { 374 RF_StripeLockDesc_t *lockDesc, *ld_t; 375 RF_LockReqDesc_t *lr, *lr_t, *callbacklist, *t; 376 #if defined(DEBUG) && (RF_DEBUG_STRIPELOCK > 0) 377 int tid = 0; 378 #endif 379 int hashval = HASH_STRIPEID(stripeID); 380 int release_it, consider_it; 381 RF_LockReqDesc_t *candidate, *candidate_t, *predecessor; 382 383 RF_ASSERT(RF_IO_IS_R_OR_W(lockReqDesc->type)); 384 385 #if RF_DEBUG_STRIPELOCK 386 if (rf_stripeLockDebug) { 387 if (stripeID == -1) { 388 Dprintf1("[%d] Lock release suppressed (stripeID == -1)\n", tid); 389 } else { 390 Dprintf8("[%d] Releasing stripe lock on stripe ID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 391 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2, lockTable); 392 FLUSH; 393 } 394 } 395 #endif 396 if (stripeID == -1) 397 return; 398 399 rf_lock_mutex2(lockTable[hashval].mutex); 400 401 /* find the stripe lock descriptor */ 402 for (ld_t = NULL, lockDesc = lockTable[hashval].descList; 403 lockDesc; ld_t = lockDesc, lockDesc = lockDesc->next) { 404 if (lockDesc->stripeID == stripeID) 405 break; 406 } 407 RF_ASSERT(lockDesc); /* major error to release a lock that doesn't 408 * exist */ 409 410 /* find the stripe lock request descriptor & delete it from the list */ 411 for (lr_t = NULL, lr = lockDesc->granted; lr; lr_t = lr, lr = lr->next) 412 if (lr == lockReqDesc) 413 break; 414 415 RF_ASSERT(lr && (lr == lockReqDesc)); /* major error to release a 416 * lock that hasn't been 417 * granted */ 418 if (lr_t) 419 lr_t->next = lr->next; 420 else { 421 RF_ASSERT(lr == lockDesc->granted); 422 lockDesc->granted = lr->next; 423 } 424 lr->next = NULL; 425 426 if (lockReqDesc->type == RF_IO_TYPE_WRITE) 427 lockDesc->nWriters--; 428 429 /* search through the waiters list to see if anyone needs to 430 * be woken up. for each such descriptor in the wait list, we 431 * check it against everything granted and against everything 432 * _in front_ of it in the waiters queue. If it conflicts 433 * with none of these, we release it. 434 * 435 * DON'T TOUCH THE TEMPLINK POINTER OF ANYTHING IN THE GRANTED 436 * LIST HERE. 437 * 438 * This will roach the case where the callback tries to 439 * acquire a new lock in the same stripe. There are some 440 * asserts to try and detect this. 441 * 442 * We apply 2 performance optimizations: (1) if releasing this 443 * lock results in no more writers to this stripe, we just 444 * release everybody waiting, since we place no restrictions 445 * on the number of concurrent reads. (2) we consider as 446 * candidates for wakeup only those waiters that have a range 447 * overlap with either the descriptor being woken up or with 448 * something in the callbacklist (i.e. something we've just 449 * now woken up). This allows us to avoid the long evaluation 450 * for some descriptors. */ 451 452 callbacklist = NULL; 453 if (lockDesc->nWriters == 0) { /* performance tweak (1) */ 454 while (lockDesc->waitersH) { 455 /* delete from waiters list */ 456 lr = lockDesc->waitersH; 457 lockDesc->waitersH = lr->next; 458 459 RF_ASSERT(lr->type == RF_IO_TYPE_READ); 460 461 /* add to granted list */ 462 lr->next = lockDesc->granted; 463 lockDesc->granted = lr; 464 465 RF_ASSERT(!lr->templink); 466 /* put on callback list so that we'll invoke 467 callback below */ 468 lr->templink = callbacklist; 469 callbacklist = lr; 470 #if RF_DEBUG_STRIPELOCK 471 if (rf_stripeLockDebug) { 472 Dprintf8("[%d] No writers: granting lock stripe ID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 473 tid, stripeID, lr->type, lr->start, lr->stop, lr->start2, lr->stop2, (unsigned long) lockTable); 474 FLUSH; 475 } 476 #endif 477 } 478 lockDesc->waitersT = NULL; 479 /* we've purged the whole waiters list */ 480 481 } else 482 for (candidate_t = NULL, candidate = lockDesc->waitersH; 483 candidate;) { 484 485 /* performance tweak (2) */ 486 consider_it = 0; 487 if (RANGE_OVERLAP(lockReqDesc, candidate)) 488 consider_it = 1; 489 else 490 for (t = callbacklist; t; t = t->templink) 491 if (RANGE_OVERLAP(t, candidate)) { 492 consider_it = 1; 493 break; 494 } 495 if (!consider_it) { 496 #if RF_DEBUG_STRIPELOCK 497 if (rf_stripeLockDebug) { 498 Dprintf8("[%d] No overlap: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 499 tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2, 500 (unsigned long) lockTable); 501 FLUSH; 502 } 503 #endif 504 candidate_t = candidate; 505 candidate = candidate->next; 506 continue; 507 } 508 /* we have a candidate for release. check to 509 * make sure it is not blocked by any granted 510 * locks */ 511 release_it = 1; 512 for (predecessor = lockDesc->granted; predecessor; 513 predecessor = predecessor->next) { 514 if (STRIPELOCK_CONFLICT(candidate, 515 predecessor)) { 516 #if RF_DEBUG_STRIPELOCK 517 if (rf_stripeLockDebug) { 518 Dprintf8("[%d] Conflicts with granted lock: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 519 tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2, 520 (unsigned long) lockTable); 521 FLUSH; 522 } 523 #endif 524 release_it = 0; 525 break; 526 } 527 } 528 529 /* now check to see if the candidate is 530 * blocked by any waiters that occur before it 531 * it the wait queue */ 532 if (release_it) 533 for (predecessor = lockDesc->waitersH; 534 predecessor != candidate; 535 predecessor = predecessor->next) { 536 if (STRIPELOCK_CONFLICT(candidate, 537 predecessor)) { 538 #if RF_DEBUG_STRIPELOCK 539 if (rf_stripeLockDebug) { 540 Dprintf8("[%d] Conflicts with waiting lock: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 541 tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2, 542 (unsigned long) lockTable); 543 FLUSH; 544 } 545 #endif 546 release_it = 0; 547 break; 548 } 549 } 550 551 /* release it if indicated */ 552 if (release_it) { 553 #if RF_DEBUG_STRIPELOCK 554 if (rf_stripeLockDebug) { 555 Dprintf8("[%d] Granting lock to candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 556 tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2, 557 (unsigned long) lockTable); 558 FLUSH; 559 } 560 #endif 561 if (candidate_t) { 562 candidate_t->next = candidate->next; 563 if (lockDesc->waitersT == candidate) 564 lockDesc->waitersT = candidate_t; /* cannot be waitersH since candidate_t is not NULL */ 565 } else { 566 RF_ASSERT(candidate == lockDesc->waitersH); 567 lockDesc->waitersH = lockDesc->waitersH->next; 568 if (!lockDesc->waitersH) 569 lockDesc->waitersT = NULL; 570 } 571 /* move it to the granted list */ 572 candidate->next = lockDesc->granted; 573 lockDesc->granted = candidate; 574 575 RF_ASSERT(!candidate->templink); 576 /* put it on the list of things to be 577 called after we release the mutex */ 578 candidate->templink = callbacklist; 579 580 callbacklist = candidate; 581 582 if (!candidate_t) 583 candidate = lockDesc->waitersH; 584 else 585 candidate = candidate_t->next; 586 /* continue with the rest of the list */ 587 } else { 588 candidate_t = candidate; 589 /* continue with the rest of the list */ 590 candidate = candidate->next; 591 } 592 } 593 594 /* delete the descriptor if no one is waiting or active */ 595 if (!lockDesc->granted && !lockDesc->waitersH) { 596 RF_ASSERT(lockDesc->nWriters == 0); 597 #if RF_DEBUG_STRIPELOCK 598 if (rf_stripeLockDebug) { 599 Dprintf3("[%d] Last lock released (table 0x%lx): deleting desc for stripeID %ld\n", tid, (unsigned long) lockTable, stripeID); 600 FLUSH; 601 } 602 #endif 603 if (ld_t) 604 ld_t->next = lockDesc->next; 605 else { 606 RF_ASSERT(lockDesc == lockTable[hashval].descList); 607 lockTable[hashval].descList = lockDesc->next; 608 } 609 FreeStripeLockDesc(lockDesc); 610 lockDesc = NULL;/* only for the ASSERT below */ 611 } 612 rf_unlock_mutex2(lockTable[hashval].mutex); 613 614 /* now that we've unlocked the mutex, invoke the callback on 615 * all the descriptors in the list */ 616 617 /* if we deleted the descriptor, we should have no callbacks 618 * to do */ 619 RF_ASSERT(!((callbacklist) && (!lockDesc))); 620 for (candidate = callbacklist; candidate;) { 621 t = candidate; 622 candidate = candidate->templink; 623 t->templink = NULL; 624 (t->cbFunc) (t->cbArg); 625 } 626 } 627 /* must have the indicated lock table mutex upon entry */ 628 static void 629 AddToWaitersQueue(RF_StripeLockDesc_t *lockDesc, RF_LockReqDesc_t *lockReqDesc) 630 { 631 if (!lockDesc->waitersH) { 632 lockDesc->waitersH = lockDesc->waitersT = lockReqDesc; 633 } else { 634 lockDesc->waitersT->next = lockReqDesc; 635 lockDesc->waitersT = lockReqDesc; 636 } 637 } 638 639 static RF_StripeLockDesc_t * 640 AllocStripeLockDesc(RF_StripeNum_t stripeID) 641 { 642 RF_StripeLockDesc_t *p; 643 644 p = pool_get(&rf_pools.stripelock, PR_WAITOK); 645 if (p) { 646 p->stripeID = stripeID; 647 p->granted = NULL; 648 p->waitersH = NULL; 649 p->waitersT = NULL; 650 p->nWriters = 0; 651 p->next = NULL; 652 } 653 return (p); 654 } 655 656 static void 657 FreeStripeLockDesc(RF_StripeLockDesc_t *p) 658 { 659 pool_put(&rf_pools.stripelock, p); 660 } 661 662 #if RF_DEBUG_STRIPELOCK 663 static void 664 PrintLockedStripes(RF_LockTableEntry_t *lockTable) 665 { 666 int i, j, foundone = 0, did; 667 RF_StripeLockDesc_t *p; 668 RF_LockReqDesc_t *q; 669 670 rf_lock_mutex2(rf_printf_mutex); 671 printf("Locked stripes:\n"); 672 for (i = 0; i < rf_lockTableSize; i++) 673 if (lockTable[i].descList) { 674 foundone = 1; 675 for (p = lockTable[i].descList; p; p = p->next) { 676 printf("Stripe ID 0x%lx (%d) nWriters %d\n", 677 (long) p->stripeID, (int) p->stripeID, 678 p->nWriters); 679 680 if (!(p->granted)) 681 printf("Granted: (none)\n"); 682 else 683 printf("Granted:\n"); 684 for (did = 1, j = 0, q = p->granted; q; 685 j++, q = q->next) { 686 printf(" %c(%ld-%ld", q->type, (long) q->start, (long) q->stop); 687 if (q->start2 != -1) 688 printf(",%ld-%ld) ", (long) q->start2, 689 (long) q->stop2); 690 else 691 printf(") "); 692 if (j && !(j % 4)) { 693 printf("\n"); 694 did = 1; 695 } else 696 did = 0; 697 } 698 if (!did) 699 printf("\n"); 700 701 if (!(p->waitersH)) 702 printf("Waiting: (none)\n"); 703 else 704 printf("Waiting:\n"); 705 for (did = 1, j = 0, q = p->waitersH; q; 706 j++, q = q->next) { 707 printf("%c(%ld-%ld", q->type, (long) q->start, (long) q->stop); 708 if (q->start2 != -1) 709 printf(",%ld-%ld) ", (long) q->start2, (long) q->stop2); 710 else 711 printf(") "); 712 if (j && !(j % 4)) { 713 printf("\n "); 714 did = 1; 715 } else 716 did = 0; 717 } 718 if (!did) 719 printf("\n"); 720 } 721 } 722 if (!foundone) 723 printf("(none)\n"); 724 else 725 printf("\n"); 726 rf_unlock_mutex2(rf_printf_mutex); 727 } 728 #endif 729