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