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