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