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