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