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