1/* $NetBSD: rf_stripelocks.c,v 1.35 2021/07/23 00:54:45 oster 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.35 2021/07/23 00:54:45 oster 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 100static void AddToWaitersQueue(RF_StripeLockDesc_t * lockDesc, 101 RF_LockReqDesc_t * lockReqDesc); 102static RF_StripeLockDesc_t *AllocStripeLockDesc(RF_Raid_t *raidPtr, RF_StripeNum_t stripeID); 103static void FreeStripeLockDesc(RF_Raid_t *raidPtr, RF_StripeLockDesc_t * p); 104static RF_LockTableEntry_t *rf_MakeLockTable(void); 105#if RF_DEBUG_STRIPELOCK 106static 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 156static void rf_ShutdownStripeLocks(RF_LockTableEntry_t * lockTable); 157static void rf_ShutdownStripeLockFreeList(void *); 158static void rf_RaidShutdownStripeLocks(void *); 159 160static void 161rf_ShutdownStripeLockFreeList(void *arg) 162{ 163 RF_Raid_t *raidPtr; 164 165 raidPtr = (RF_Raid_t *) arg; 166 167 pool_destroy(&raidPtr->pools.stripelock); 168} 169 170int 171rf_ConfigureStripeLockFreeList(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr, 172 RF_Config_t *cfgPtr) 173{ 174 unsigned mask; 175 176 rf_pool_init(raidPtr, raidPtr->poolNames.stripelock, &raidPtr->pools.stripelock, sizeof(RF_StripeLockDesc_t), 177 "strplock", RF_MIN_FREE_STRIPELOCK, RF_MAX_FREE_STRIPELOCK); 178 rf_ShutdownCreate(listp, rf_ShutdownStripeLockFreeList, raidPtr); 179 180 for (mask = 0x1; mask; mask <<= 1) 181 if (rf_lockTableSize == mask) 182 break; 183 if (!mask) { 184 printf("[WARNING: lock table size must be a power of two. Setting to %d.]\n", RF_DEFAULT_LOCK_TABLE_SIZE); 185 rf_lockTableSize = RF_DEFAULT_LOCK_TABLE_SIZE; 186 } 187 return (0); 188} 189 190static void 191rf_DestroyLockTable(RF_LockTableEntry_t *lockTable) 192{ 193 int i; 194 195 for (i = 0; i < rf_lockTableSize; i++) { 196 rf_destroy_mutex2(lockTable[i].mutex); 197 } 198 RF_Free(lockTable, rf_lockTableSize * sizeof(RF_LockTableEntry_t)); 199} 200 201static RF_LockTableEntry_t * 202rf_MakeLockTable(void) 203{ 204 RF_LockTableEntry_t *lockTable; 205 int i; 206 207 lockTable = RF_Malloc(rf_lockTableSize * sizeof(*lockTable)); 208 if (lockTable == NULL) 209 return (NULL); 210 for (i = 0; i < rf_lockTableSize; i++) { 211 rf_init_mutex2(lockTable[i].mutex, IPL_VM); 212 } 213 return (lockTable); 214} 215 216static void 217rf_ShutdownStripeLocks(RF_LockTableEntry_t * lockTable) 218{ 219 220#if RF_DEBUG_STRIPELOCK 221 if (rf_stripeLockDebug) { 222 PrintLockedStripes(lockTable); 223 } 224#endif 225 rf_DestroyLockTable(lockTable); 226} 227 228static void 229rf_RaidShutdownStripeLocks(void *arg) 230{ 231 RF_Raid_t *raidPtr = (RF_Raid_t *) arg; 232 rf_ShutdownStripeLocks(raidPtr->lockTable); 233} 234 235int 236rf_ConfigureStripeLocks(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr, 237 RF_Config_t *cfgPtr) 238{ 239 240 raidPtr->lockTable = rf_MakeLockTable(); 241 if (raidPtr->lockTable == NULL) 242 return (ENOMEM); 243 rf_ShutdownCreate(listp, rf_RaidShutdownStripeLocks, raidPtr); 244 245 return (0); 246} 247/* returns 0 if you've got the lock, and non-zero if you have to wait. 248 * if and only if you have to wait, we'll cause cbFunc to get invoked 249 * with cbArg when you are granted the lock. We store a tag in 250 * *releaseTag that you need to give back to us when you release the 251 * lock. */ 252int 253rf_AcquireStripeLock(RF_Raid_t *raidPtr, RF_LockTableEntry_t *lockTable, RF_StripeNum_t stripeID, 254 RF_LockReqDesc_t *lockReqDesc) 255{ 256 RF_StripeLockDesc_t *lockDesc; 257 RF_StripeLockDesc_t *newlockDesc; 258 RF_LockReqDesc_t *p; 259#if defined(DEBUG) && (RF_DEBUG_STRIPELOCK > 0) 260 int tid = 0; 261#endif 262 int hashval = HASH_STRIPEID(stripeID); 263 int retcode = 0; 264 265 RF_ASSERT(RF_IO_IS_R_OR_W(lockReqDesc->type)); 266 267#if RF_DEBUG_STRIPELOCK 268 if (rf_stripeLockDebug) { 269 if (stripeID == -1) { 270 Dprintf1("[%d] Lock acquisition suppressed (stripeID == -1)\n", tid); 271 } else { 272 Dprintf8("[%d] Trying to acquire stripe lock table 0x%lx SID %ld type %c range %ld-%ld, range2 %ld-%ld hashval %d\n", 273 tid, (unsigned long) lockTable, stripeID, lockReqDesc->type, lockReqDesc->start, 274 lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2); 275 Dprintf3("[%d] lock %ld hashval %d\n", tid, stripeID, hashval); 276 FLUSH; 277 } 278 } 279#endif 280 if (stripeID == -1) 281 return (0); 282 lockReqDesc->next = NULL; /* just to be sure */ 283 newlockDesc = AllocStripeLockDesc(raidPtr, stripeID); 284 285 rf_lock_mutex2(lockTable[hashval].mutex); 286 for (lockDesc = lockTable[hashval].descList; lockDesc; 287 lockDesc = lockDesc->next) { 288 if (lockDesc->stripeID == stripeID) 289 break; 290 } 291 292 if (!lockDesc) { 293 /* no entry in table => no one reading or writing */ 294 lockDesc = newlockDesc; 295 lockDesc->next = lockTable[hashval].descList; 296 lockTable[hashval].descList = lockDesc; 297 if (lockReqDesc->type == RF_IO_TYPE_WRITE) 298 lockDesc->nWriters++; 299 lockDesc->granted = lockReqDesc; 300#if RF_DEBUG_STRIPELOCK 301 if (rf_stripeLockDebug) { 302 Dprintf7("[%d] no one waiting: lock %ld %c %ld-%ld %ld-%ld granted\n", 303 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2); 304 FLUSH; 305 } 306#endif 307 } else { 308 /* we won't be needing newlockDesc after all.. pity.. */ 309 FreeStripeLockDesc(raidPtr, newlockDesc); 310 311 if (lockReqDesc->type == RF_IO_TYPE_WRITE) 312 lockDesc->nWriters++; 313 314 if (lockDesc->nWriters == 0) { 315 /* no need to search any lists if there are no 316 * writers anywhere */ 317 lockReqDesc->next = lockDesc->granted; 318 lockDesc->granted = lockReqDesc; 319#if RF_DEBUG_STRIPELOCK 320 if (rf_stripeLockDebug) { 321 Dprintf7("[%d] no writers: lock %ld %c %ld-%ld %ld-%ld granted\n", 322 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2); 323 FLUSH; 324 } 325#endif 326 } else { 327 328 /* search the granted & waiting lists for a 329 * conflict. stop searching as soon as we 330 * find one */ 331 retcode = 0; 332 for (p = lockDesc->granted; p; p = p->next) 333 if (STRIPELOCK_CONFLICT(lockReqDesc, p)) { 334 retcode = 1; 335 break; 336 } 337 if (!retcode) 338 for (p = lockDesc->waitersH; p; p = p->next) 339 if (STRIPELOCK_CONFLICT(lockReqDesc, p)) { 340 retcode = 2; 341 break; 342 } 343 if (!retcode) { 344 /* no conflicts found => grant lock */ 345 lockReqDesc->next = lockDesc->granted; 346 lockDesc->granted = lockReqDesc; 347#if RF_DEBUG_STRIPELOCK 348 if (rf_stripeLockDebug) { 349 Dprintf7("[%d] no conflicts: lock %ld %c %ld-%ld %ld-%ld granted\n", 350 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, 351 lockReqDesc->start2, lockReqDesc->stop2); 352 FLUSH; 353 } 354#endif 355 } else { 356#if RF_DEBUG_STRIPELOCK 357 if (rf_stripeLockDebug) { 358 Dprintf6("[%d] conflict: lock %ld %c %ld-%ld hashval=%d not granted\n", 359 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, 360 hashval); 361 Dprintf3("[%d] lock %ld retcode=%d\n", tid, stripeID, retcode); 362 FLUSH; 363 } 364#endif 365 AddToWaitersQueue(lockDesc, lockReqDesc); 366 /* conflict => the current access must wait */ 367 } 368 } 369 } 370 371 rf_unlock_mutex2(lockTable[hashval].mutex); 372 return (retcode); 373} 374 375void 376rf_ReleaseStripeLock(RF_Raid_t *raidPtr, RF_LockTableEntry_t *lockTable, RF_StripeNum_t stripeID, 377 RF_LockReqDesc_t *lockReqDesc) 378{ 379 RF_StripeLockDesc_t *lockDesc, *ld_t; 380 RF_LockReqDesc_t *lr, *lr_t, *callbacklist, *t; 381#if defined(DEBUG) && (RF_DEBUG_STRIPELOCK > 0) 382 int tid = 0; 383#endif 384 int hashval = HASH_STRIPEID(stripeID); 385 int release_it, consider_it; 386 RF_LockReqDesc_t *candidate, *candidate_t, *predecessor; 387 388 RF_ASSERT(RF_IO_IS_R_OR_W(lockReqDesc->type)); 389 390#if RF_DEBUG_STRIPELOCK 391 if (rf_stripeLockDebug) { 392 if (stripeID == -1) { 393 Dprintf1("[%d] Lock release suppressed (stripeID == -1)\n", tid); 394 } else { 395 Dprintf8("[%d] Releasing stripe lock on stripe ID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 396 tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2, lockTable); 397 FLUSH; 398 } 399 } 400#endif 401 if (stripeID == -1) 402 return; 403 404 rf_lock_mutex2(lockTable[hashval].mutex); 405 406 /* find the stripe lock descriptor */ 407 for (ld_t = NULL, lockDesc = lockTable[hashval].descList; 408 lockDesc; ld_t = lockDesc, lockDesc = lockDesc->next) { 409 if (lockDesc->stripeID == stripeID) 410 break; 411 } 412 RF_ASSERT(lockDesc); /* major error to release a lock that doesn't 413 * exist */ 414 415 /* find the stripe lock request descriptor & delete it from the list */ 416 for (lr_t = NULL, lr = lockDesc->granted; lr; lr_t = lr, lr = lr->next) 417 if (lr == lockReqDesc) 418 break; 419 420 RF_ASSERT(lr && (lr == lockReqDesc)); /* major error to release a 421 * lock that hasn't been 422 * granted */ 423 if (lr_t) 424 lr_t->next = lr->next; 425 else { 426 RF_ASSERT(lr == lockDesc->granted); 427 lockDesc->granted = lr->next; 428 } 429 lr->next = NULL; 430 431 if (lockReqDesc->type == RF_IO_TYPE_WRITE) 432 lockDesc->nWriters--; 433 434 /* search through the waiters list to see if anyone needs to 435 * be woken up. for each such descriptor in the wait list, we 436 * check it against everything granted and against everything 437 * _in front_ of it in the waiters queue. If it conflicts 438 * with none of these, we release it. 439 * 440 * DON'T TOUCH THE TEMPLINK POINTER OF ANYTHING IN THE GRANTED 441 * LIST HERE. 442 * 443 * This will roach the case where the callback tries to 444 * acquire a new lock in the same stripe. There are some 445 * asserts to try and detect this. 446 * 447 * We apply 2 performance optimizations: (1) if releasing this 448 * lock results in no more writers to this stripe, we just 449 * release everybody waiting, since we place no restrictions 450 * on the number of concurrent reads. (2) we consider as 451 * candidates for wakeup only those waiters that have a range 452 * overlap with either the descriptor being woken up or with 453 * something in the callbacklist (i.e. something we've just 454 * now woken up). This allows us to avoid the long evaluation 455 * for some descriptors. */ 456 457 callbacklist = NULL; 458 if (lockDesc->nWriters == 0) { /* performance tweak (1) */ 459 while (lockDesc->waitersH) { 460 /* delete from waiters list */ 461 lr = lockDesc->waitersH; 462 lockDesc->waitersH = lr->next; 463 464 RF_ASSERT(lr->type == RF_IO_TYPE_READ); 465 466 /* add to granted list */ 467 lr->next = lockDesc->granted; 468 lockDesc->granted = lr; 469 470 RF_ASSERT(!lr->templink); 471 /* put on callback list so that we'll invoke 472 callback below */ 473 lr->templink = callbacklist; 474 callbacklist = lr; 475#if RF_DEBUG_STRIPELOCK 476 if (rf_stripeLockDebug) { 477 Dprintf8("[%d] No writers: granting lock stripe ID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 478 tid, stripeID, lr->type, lr->start, lr->stop, lr->start2, lr->stop2, (unsigned long) lockTable); 479 FLUSH; 480 } 481#endif 482 } 483 lockDesc->waitersT = NULL; 484 /* we've purged the whole waiters list */ 485 486 } else 487 for (candidate_t = NULL, candidate = lockDesc->waitersH; 488 candidate;) { 489 490 /* performance tweak (2) */ 491 consider_it = 0; 492 if (RANGE_OVERLAP(lockReqDesc, candidate)) 493 consider_it = 1; 494 else 495 for (t = callbacklist; t; t = t->templink) 496 if (RANGE_OVERLAP(t, candidate)) { 497 consider_it = 1; 498 break; 499 } 500 if (!consider_it) { 501#if RF_DEBUG_STRIPELOCK 502 if (rf_stripeLockDebug) { 503 Dprintf8("[%d] No overlap: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 504 tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2, 505 (unsigned long) lockTable); 506 FLUSH; 507 } 508#endif 509 candidate_t = candidate; 510 candidate = candidate->next; 511 continue; 512 } 513 /* we have a candidate for release. check to 514 * make sure it is not blocked by any granted 515 * locks */ 516 release_it = 1; 517 for (predecessor = lockDesc->granted; predecessor; 518 predecessor = predecessor->next) { 519 if (STRIPELOCK_CONFLICT(candidate, 520 predecessor)) { 521#if RF_DEBUG_STRIPELOCK 522 if (rf_stripeLockDebug) { 523 Dprintf8("[%d] Conflicts with granted lock: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 524 tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2, 525 (unsigned long) lockTable); 526 FLUSH; 527 } 528#endif 529 release_it = 0; 530 break; 531 } 532 } 533 534 /* now check to see if the candidate is 535 * blocked by any waiters that occur before it 536 * it the wait queue */ 537 if (release_it) 538 for (predecessor = lockDesc->waitersH; 539 predecessor != candidate; 540 predecessor = predecessor->next) { 541 if (STRIPELOCK_CONFLICT(candidate, 542 predecessor)) { 543#if RF_DEBUG_STRIPELOCK 544 if (rf_stripeLockDebug) { 545 Dprintf8("[%d] Conflicts with waiting lock: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 546 tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2, 547 (unsigned long) lockTable); 548 FLUSH; 549 } 550#endif 551 release_it = 0; 552 break; 553 } 554 } 555 556 /* release it if indicated */ 557 if (release_it) { 558#if RF_DEBUG_STRIPELOCK 559 if (rf_stripeLockDebug) { 560 Dprintf8("[%d] Granting lock to candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n", 561 tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2, 562 (unsigned long) lockTable); 563 FLUSH; 564 } 565#endif 566 if (candidate_t) { 567 candidate_t->next = candidate->next; 568 if (lockDesc->waitersT == candidate) 569 lockDesc->waitersT = candidate_t; /* cannot be waitersH since candidate_t is not NULL */ 570 } else { 571 RF_ASSERT(candidate == lockDesc->waitersH); 572 lockDesc->waitersH = lockDesc->waitersH->next; 573 if (!lockDesc->waitersH) 574 lockDesc->waitersT = NULL; 575 } 576 /* move it to the granted list */ 577 candidate->next = lockDesc->granted; 578 lockDesc->granted = candidate; 579 580 RF_ASSERT(!candidate->templink); 581 /* put it on the list of things to be 582 called after we release the mutex */ 583 candidate->templink = callbacklist; 584 585 callbacklist = candidate; 586 587 if (!candidate_t) 588 candidate = lockDesc->waitersH; 589 else 590 candidate = candidate_t->next; 591 /* continue with the rest of the list */ 592 } else { 593 candidate_t = candidate; 594 /* continue with the rest of the list */ 595 candidate = candidate->next; 596 } 597 } 598 599 /* delete the descriptor if no one is waiting or active */ 600 if (!lockDesc->granted && !lockDesc->waitersH) { 601 RF_ASSERT(lockDesc->nWriters == 0); 602#if RF_DEBUG_STRIPELOCK 603 if (rf_stripeLockDebug) { 604 Dprintf3("[%d] Last lock released (table 0x%lx): deleting desc for stripeID %ld\n", tid, (unsigned long) lockTable, stripeID); 605 FLUSH; 606 } 607#endif 608 if (ld_t) 609 ld_t->next = lockDesc->next; 610 else { 611 RF_ASSERT(lockDesc == lockTable[hashval].descList); 612 lockTable[hashval].descList = lockDesc->next; 613 } 614 FreeStripeLockDesc(raidPtr, lockDesc); 615 lockDesc = NULL;/* only for the ASSERT below */ 616 } 617 rf_unlock_mutex2(lockTable[hashval].mutex); 618 619 /* now that we've unlocked the mutex, invoke the callback on 620 * all the descriptors in the list */ 621 622 /* if we deleted the descriptor, we should have no callbacks 623 * to do */ 624 RF_ASSERT(!((callbacklist) && (!lockDesc))); 625 for (candidate = callbacklist; candidate;) { 626 t = candidate; 627 candidate = candidate->templink; 628 t->templink = NULL; 629 (t->cbFunc) (t->cbArg); 630 } 631} 632/* must have the indicated lock table mutex upon entry */ 633static void 634AddToWaitersQueue(RF_StripeLockDesc_t *lockDesc, RF_LockReqDesc_t *lockReqDesc) 635{ 636 if (!lockDesc->waitersH) { 637 lockDesc->waitersH = lockDesc->waitersT = lockReqDesc; 638 } else { 639 lockDesc->waitersT->next = lockReqDesc; 640 lockDesc->waitersT = lockReqDesc; 641 } 642} 643 644static RF_StripeLockDesc_t * 645AllocStripeLockDesc(RF_Raid_t *raidPtr, RF_StripeNum_t stripeID) 646{ 647 RF_StripeLockDesc_t *p; 648 649 p = pool_get(&raidPtr->pools.stripelock, PR_WAITOK); 650 if (p) { 651 p->stripeID = stripeID; 652 p->granted = NULL; 653 p->waitersH = NULL; 654 p->waitersT = NULL; 655 p->nWriters = 0; 656 p->next = NULL; 657 } 658 return (p); 659} 660 661static void 662FreeStripeLockDesc(RF_Raid_t *raidPtr, RF_StripeLockDesc_t *p) 663{ 664 pool_put(&raidPtr->pools.stripelock, p); 665} 666 667#if RF_DEBUG_STRIPELOCK 668static void 669PrintLockedStripes(RF_LockTableEntry_t *lockTable) 670{ 671 int i, j, foundone = 0, did; 672 RF_StripeLockDesc_t *p; 673 RF_LockReqDesc_t *q; 674 675 rf_lock_mutex2(rf_printf_mutex); 676 printf("Locked stripes:\n"); 677 for (i = 0; i < rf_lockTableSize; i++) 678 if (lockTable[i].descList) { 679 foundone = 1; 680 for (p = lockTable[i].descList; p; p = p->next) { 681 printf("Stripe ID 0x%lx (%d) nWriters %d\n", 682 (long) p->stripeID, (int) p->stripeID, 683 p->nWriters); 684 685 if (!(p->granted)) 686 printf("Granted: (none)\n"); 687 else 688 printf("Granted:\n"); 689 for (did = 1, j = 0, q = p->granted; q; 690 j++, q = q->next) { 691 printf(" %c(%ld-%ld", q->type, (long) q->start, (long) q->stop); 692 if (q->start2 != -1) 693 printf(",%ld-%ld) ", (long) q->start2, 694 (long) q->stop2); 695 else 696 printf(") "); 697 if (j && !(j % 4)) { 698 printf("\n"); 699 did = 1; 700 } else 701 did = 0; 702 } 703 if (!did) 704 printf("\n"); 705 706 if (!(p->waitersH)) 707 printf("Waiting: (none)\n"); 708 else 709 printf("Waiting:\n"); 710 for (did = 1, j = 0, q = p->waitersH; q; 711 j++, q = q->next) { 712 printf("%c(%ld-%ld", q->type, (long) q->start, (long) q->stop); 713 if (q->start2 != -1) 714 printf(",%ld-%ld) ", (long) q->start2, (long) q->stop2); 715 else 716 printf(") "); 717 if (j && !(j % 4)) { 718 printf("\n "); 719 did = 1; 720 } else 721 did = 0; 722 } 723 if (!did) 724 printf("\n"); 725 } 726 } 727 if (!foundone) 728 printf("(none)\n"); 729 else 730 printf("\n"); 731 rf_unlock_mutex2(rf_printf_mutex); 732} 733#endif 734