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