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