![[BACK]](/icons/back.gif){kind=icon}
Return to rf_stripelocks.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe|
Return to rf_stripelocks.c CVS log | Up to [local] / sys / dev / raidframe |
1.1 ! nbrk 1: /* $OpenBSD: rf_stripelocks.c,v 1.5 2002/12/16 07:01:05 tdeval Exp $ */
! 2: /* $NetBSD: rf_stripelocks.c,v 1.5 2000/01/08 23:45:05 oster Exp $ */
! 3:
! 4: /*
! 5: * Copyright (c) 1995 Carnegie-Mellon University.
! 6: * All rights reserved.
! 7: *
! 8: * Authors: Mark Holland, Jim Zelenka
! 9: *
! 10: * Permission to use, copy, modify and distribute this software and
! 11: * its documentation is hereby granted, provided that both the copyright
! 12: * notice and this permission notice appear in all copies of the
! 13: * software, derivative works or modified versions, and any portions
! 14: * thereof, and that both notices appear in supporting documentation.
! 15: *
! 16: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
! 17: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
! 18: * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
! 19: *
! 20: * Carnegie Mellon requests users of this software to return to
! 21: *
! 22: * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
! 23: * School of Computer Science
! 24: * Carnegie Mellon University
! 25: * Pittsburgh PA 15213-3890
! 26: *
! 27: * any improvements or extensions that they make and grant Carnegie the
! 28: * rights to redistribute these changes.
! 29: */
! 30:
! 31: /*
! 32: * stripelocks.c -- Code to lock stripes for read and write access.
! 33: *
! 34: * The code distinguishes between read locks and write locks. There can be
! 35: * as many readers to given stripe as desired. When a write request comes
! 36: * in, no further readers are allowed to enter, and all subsequent requests
! 37: * are queued in FIFO order. When the number of readers goes to zero, the
! 38: * writer is given the lock. When a writer releases the lock, the list of
! 39: * queued requests is scanned, and all readers up to the next writer are
! 40: * given the lock.
! 41: *
! 42: * The lock table size must be one less than a power of two, but HASH_STRIPEID
! 43: * is the only function that requires this.
! 44: *
! 45: * The code now supports "range locks". When you ask to lock a stripe, you
! 46: * specify a range of addresses in that stripe that you want to lock. When
! 47: * you acquire the lock, you've locked only this range of addresses, and
! 48: * other threads can concurrently read/write any non-overlapping portions
! 49: * of the stripe. The "addresses" that you lock are abstract in that you
! 50: * can pass in anything you like. The expectation is that you'll pass in
! 51: * the range of physical disk offsets of the parity bits you're planning
! 52: * to update. The idea behind this, of course, is to allow sub-stripe
! 53: * locking. The implementation is perhaps not the best imaginable; in the
! 54: * worst case a lock release is O(n^2) in the total number of outstanding
! 55: * requests to a given stripe. Note that if you're striping with a
! 56: * stripe unit size equal to an entire disk (i.e. not striping), there will
! 57: * be only one stripe and you may spend some significant number of cycles
! 58: * searching through stripe lock descriptors.
! 59: */
! 60:
! 61: #include "rf_types.h"
! 62: #include "rf_raid.h"
! 63: #include "rf_stripelocks.h"
! 64: #include "rf_alloclist.h"
! 65: #include "rf_general.h"
! 66: #include "rf_freelist.h"
! 67: #include "rf_debugprint.h"
! 68: #include "rf_driver.h"
! 69: #include "rf_shutdown.h"
! 70:
! 71: #define Dprintf1(s,a) \
! 72: rf_debug_printf(s, (void *)((unsigned long)a), \
! 73: NULL, NULL, NULL, NULL, NULL, NULL, NULL)
! 74: #define Dprintf2(s,a,b) \
! 75: rf_debug_printf(s, (void *)((unsigned long)a), \
! 76: (void *)((unsigned long)b), NULL, NULL, NULL, NULL, NULL, NULL)
! 77: #define Dprintf3(s,a,b,c) \
! 78: rf_debug_printf(s, (void *)((unsigned long)a), \
! 79: (void *)((unsigned long)b), (void *)((unsigned long)c), \
! 80: NULL, NULL, NULL, NULL, NULL)
! 81: #define Dprintf4(s,a,b,c,d) \
! 82: rf_debug_printf(s, (void *)((unsigned long)a), \
! 83: (void *)((unsigned long)b), (void *)((unsigned long)c), \
! 84: (void *)((unsigned long)d), NULL, NULL, NULL, NULL)
! 85: #define Dprintf5(s,a,b,c,d,e) \
! 86: rf_debug_printf(s, (void *)((unsigned long)a), \
! 87: (void *)((unsigned long)b), (void *)((unsigned long)c), \
! 88: (void *)((unsigned long)d), (void *)((unsigned long)e), \
! 89: NULL, NULL, NULL)
! 90: #define Dprintf6(s,a,b,c,d,e,f) \
! 91: rf_debug_printf(s, (void *)((unsigned long)a), \
! 92: (void *)((unsigned long)b), (void *)((unsigned long)c), \
! 93: (void *)((unsigned long)d), (void *)((unsigned long)e), \
! 94: (void *)((unsigned long)f), NULL, NULL)
! 95: #define Dprintf7(s,a,b,c,d,e,f,g) \
! 96: rf_debug_printf(s, (void *)((unsigned long)a), \
! 97: (void *)((unsigned long)b), (void *)((unsigned long)c), \
! 98: (void *)((unsigned long)d), (void *)((unsigned long)e), \
! 99: (void *)((unsigned long)f), (void *)((unsigned long)g), NULL)
! 100: #define Dprintf8(s,a,b,c,d,e,f,g,h) \
! 101: rf_debug_printf(s, (void *)((unsigned long)a), \
! 102: (void *)((unsigned long)b), (void *)((unsigned long)c), \
! 103: (void *)((unsigned long)d), (void *)((unsigned long)e), \
! 104: (void *)((unsigned long)f), (void *)((unsigned long)g), \
! 105: (void *)((unsigned long)h))
! 106:
! 107: #define FLUSH
! 108:
! 109: #define HASH_STRIPEID(_sid_) ((_sid_) & (rf_lockTableSize-1))
! 110:
! 111: void rf_AddToWaitersQueue(RF_LockTableEntry_t *, RF_StripeLockDesc_t *,
! 112: RF_LockReqDesc_t *);
! 113: RF_StripeLockDesc_t *rf_AllocStripeLockDesc(RF_StripeNum_t);
! 114: void rf_FreeStripeLockDesc(RF_StripeLockDesc_t *);
! 115: void rf_PrintLockedStripes(RF_LockTableEntry_t *);
! 116:
! 117: /*
! 118: * Determines if two ranges overlap. Always yields false if either start
! 119: * value is negative.
! 120: */
! 121: #define SINGLE_RANGE_OVERLAP(_strt1,_stop1,_strt2,_stop2) \
! 122: ((_strt1 >= 0) && (_strt2 >= 0) && \
! 123: (RF_MAX(_strt1, _strt2) <= RF_MIN(_stop1, _stop2)))
! 124:
! 125: /*
! 126: * Determines if any of the ranges specified in the two lock descriptors
! 127: * overlap each other.
! 128: */
! 129: #define RANGE_OVERLAP(_cand,_pred) \
! 130: (SINGLE_RANGE_OVERLAP((_cand)->start, (_cand)->stop, \
! 131: (_pred)->start, (_pred)->stop) || \
! 132: SINGLE_RANGE_OVERLAP((_cand)->start2, (_cand)->stop2, \
! 133: (_pred)->start, (_pred)->stop) || \
! 134: SINGLE_RANGE_OVERLAP((_cand)->start, (_cand)->stop, \
! 135: (_pred)->start2, (_pred)->stop2) || \
! 136: SINGLE_RANGE_OVERLAP((_cand)->start2, (_cand)->stop2, \
! 137: (_pred)->start2, (_pred)->stop2))
! 138:
! 139: /*
! 140: * Determines if a candidate lock request conflicts with a predecessor
! 141: * lock req. Note that the arguments are not interchangeable.
! 142: * The rules are:
! 143: * A candidate read conflicts with a predecessor write if any ranges overlap.
! 144: * A candidate write conflicts with a predecessor read if any ranges overlap.
! 145: * A candidate write conflicts with a predecessor write if any ranges overlap.
! 146: */
! 147: #define STRIPELOCK_CONFLICT(_cand,_pred) \
! 148: (RANGE_OVERLAP((_cand), (_pred)) && \
! 149: (((((_cand)->type == RF_IO_TYPE_READ) && \
! 150: ((_pred)->type == RF_IO_TYPE_WRITE)) || \
! 151: (((_cand)->type == RF_IO_TYPE_WRITE) && \
! 152: ((_pred)->type == RF_IO_TYPE_READ)) || \
! 153: (((_cand)->type == RF_IO_TYPE_WRITE) && \
! 154: ((_pred)->type == RF_IO_TYPE_WRITE)))))
! 155:
! 156: static RF_FreeList_t *rf_stripelock_freelist;
! 157: #define RF_MAX_FREE_STRIPELOCK 128
! 158: #define RF_STRIPELOCK_INC 8
! 159: #define RF_STRIPELOCK_INITIAL 32
! 160:
! 161: void rf_ShutdownStripeLockFreeList(void *);
! 162: void rf_RaidShutdownStripeLocks(void *);
! 163:
! 164: void
! 165: rf_ShutdownStripeLockFreeList(void *ignored)
! 166: {
! 167: RF_FREELIST_DESTROY(rf_stripelock_freelist, next,
! 168: (RF_StripeLockDesc_t *));
! 169: }
! 170:
! 171: int
! 172: rf_ConfigureStripeLockFreeList(RF_ShutdownList_t **listp)
! 173: {
! 174: unsigned mask;
! 175: int rc;
! 176:
! 177: RF_FREELIST_CREATE(rf_stripelock_freelist, RF_MAX_FREE_STRIPELOCK,
! 178: RF_STRIPELOCK_INITIAL, sizeof(RF_StripeLockDesc_t));
! 179: rc = rf_ShutdownCreate(listp, rf_ShutdownStripeLockFreeList, NULL);
! 180: if (rc) {
! 181: RF_ERRORMSG3("Unable to add to shutdown list file %s"
! 182: " line %d rc=%d.\n", __FILE__, __LINE__, rc);
! 183: rf_ShutdownStripeLockFreeList(NULL);
! 184: return (rc);
! 185: }
! 186: RF_FREELIST_PRIME(rf_stripelock_freelist, RF_STRIPELOCK_INITIAL, next,
! 187: (RF_StripeLockDesc_t *));
! 188: for (mask = 0x1; mask; mask <<= 1)
! 189: if (rf_lockTableSize == mask)
! 190: break;
! 191: if (!mask) {
! 192: printf("[WARNING: lock table size must be a power of two."
! 193: " Setting to %d.]\n", RF_DEFAULT_LOCK_TABLE_SIZE);
! 194: rf_lockTableSize = RF_DEFAULT_LOCK_TABLE_SIZE;
! 195: }
! 196: return (0);
! 197: }
! 198:
! 199: RF_LockTableEntry_t *
! 200: rf_MakeLockTable(void)
! 201: {
! 202: RF_LockTableEntry_t *lockTable;
! 203: int i, rc;
! 204:
! 205: RF_Calloc(lockTable, ((int) rf_lockTableSize),
! 206: sizeof(RF_LockTableEntry_t), (RF_LockTableEntry_t *));
! 207: if (lockTable == NULL)
! 208: return (NULL);
! 209: for (i = 0; i < rf_lockTableSize; i++) {
! 210: rc = rf_mutex_init(&lockTable[i].mutex);
! 211: if (rc) {
! 212: RF_ERRORMSG3("Unable to init mutex file %s line %d"
! 213: " rc=%d.\n", __FILE__, __LINE__, rc);
! 214: /* XXX Clean up other mutexes. */
! 215: return (NULL);
! 216: }
! 217: }
! 218: return (lockTable);
! 219: }
! 220:
! 221: void
! 222: rf_ShutdownStripeLocks(RF_LockTableEntry_t *lockTable)
! 223: {
! 224: int i;
! 225:
! 226: if (rf_stripeLockDebug) {
! 227: rf_PrintLockedStripes(lockTable);
! 228: }
! 229: for (i = 0; i < rf_lockTableSize; i++) {
! 230: rf_mutex_destroy(&lockTable[i].mutex);
! 231: }
! 232: RF_Free(lockTable, rf_lockTableSize * sizeof(RF_LockTableEntry_t));
! 233: }
! 234:
! 235: void
! 236: rf_RaidShutdownStripeLocks(void *arg)
! 237: {
! 238: RF_Raid_t *raidPtr = (RF_Raid_t *) arg;
! 239: rf_ShutdownStripeLocks(raidPtr->lockTable);
! 240: }
! 241:
! 242: int
! 243: rf_ConfigureStripeLocks(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr,
! 244: RF_Config_t *cfgPtr)
! 245: {
! 246: int rc;
! 247:
! 248: raidPtr->lockTable = rf_MakeLockTable();
! 249: if (raidPtr->lockTable == NULL)
! 250: return (ENOMEM);
! 251: rc = rf_ShutdownCreate(listp, rf_RaidShutdownStripeLocks, raidPtr);
! 252: if (rc) {
! 253: RF_ERRORMSG3("Unable to add to shutdown list file %s line %d"
! 254: " rc=%d.\n", __FILE__, __LINE__, rc);
! 255: rf_ShutdownStripeLocks(raidPtr->lockTable);
! 256: return (rc);
! 257: }
! 258: return (0);
! 259: }
! 260:
! 261: /*
! 262: * Returns 0 if you've got the lock, and non-zero if you have to wait.
! 263: * If and only if you have to wait, we'll cause cbFunc to get invoked
! 264: * with cbArg when you are granted the lock. We store a tag in *releaseTag
! 265: * that you need to give back to us when you release the lock.
! 266: */
! 267: int
! 268: rf_AcquireStripeLock(RF_LockTableEntry_t *lockTable, RF_StripeNum_t stripeID,
! 269: RF_LockReqDesc_t *lockReqDesc)
! 270: {
! 271: RF_StripeLockDesc_t *lockDesc;
! 272: RF_LockReqDesc_t *p;
! 273: int tid = 0, hashval = HASH_STRIPEID(stripeID);
! 274: int retcode = 0;
! 275:
! 276: RF_ASSERT(RF_IO_IS_R_OR_W(lockReqDesc->type));
! 277:
! 278: if (rf_stripeLockDebug) {
! 279: if (stripeID == -1)
! 280: Dprintf1("[%d] Lock acquisition supressed"
! 281: " (stripeID == -1).\n", tid);
! 282: else {
! 283: Dprintf8("[%d] Trying to acquire stripe lock table"
! 284: " 0x%lx SID %ld type %c range %ld-%ld, range2"
! 285: " %ld-%ld hashval %d.\n", tid,
! 286: (unsigned long) lockTable, stripeID,
! 287: lockReqDesc->type, lockReqDesc->start,
! 288: lockReqDesc->stop, lockReqDesc->start2,
! 289: lockReqDesc->stop2);
! 290: Dprintf3("[%d] lock %ld hashval %d.\n", tid, stripeID,
! 291: hashval);
! 292: FLUSH;
! 293: }
! 294: }
! 295: if (stripeID == -1)
! 296: return (0);
! 297: lockReqDesc->next = NULL; /* Just to be sure. */
! 298:
! 299: RF_LOCK_MUTEX(lockTable[hashval].mutex);
! 300: for (lockDesc = lockTable[hashval].descList; lockDesc;
! 301: lockDesc = lockDesc->next) {
! 302: if (lockDesc->stripeID == stripeID)
! 303: break;
! 304: }
! 305:
! 306: if (!lockDesc) {
! 307: /* No entry in table => no one reading or writing. */
! 308: lockDesc = rf_AllocStripeLockDesc(stripeID);
! 309: lockDesc->next = lockTable[hashval].descList;
! 310: lockTable[hashval].descList = lockDesc;
! 311: if (lockReqDesc->type == RF_IO_TYPE_WRITE)
! 312: lockDesc->nWriters++;
! 313: lockDesc->granted = lockReqDesc;
! 314: if (rf_stripeLockDebug) {
! 315: Dprintf7("[%d] no one waiting: lock %ld %c %ld-%ld"
! 316: " %ld-%ld granted.\n", tid, stripeID,
! 317: lockReqDesc->type,
! 318: lockReqDesc->start, lockReqDesc->stop,
! 319: lockReqDesc->start2, lockReqDesc->stop2);
! 320: FLUSH;
! 321: }
! 322: } else {
! 323:
! 324: if (lockReqDesc->type == RF_IO_TYPE_WRITE)
! 325: lockDesc->nWriters++;
! 326:
! 327: if (lockDesc->nWriters == 0) {
! 328: /*
! 329: * No need to search any lists if there are no writers
! 330: * anywhere.
! 331: */
! 332: lockReqDesc->next = lockDesc->granted;
! 333: lockDesc->granted = lockReqDesc;
! 334: if (rf_stripeLockDebug) {
! 335: Dprintf7("[%d] no writers: lock %ld %c %ld-%ld"
! 336: " %ld-%ld granted.\n", tid,
! 337: stripeID, lockReqDesc->type,
! 338: lockReqDesc->start, lockReqDesc->stop,
! 339: lockReqDesc->start2, lockReqDesc->stop2);
! 340: FLUSH;
! 341: }
! 342: } else {
! 343: /*
! 344: * Search the granted & waiting lists for a conflict.
! 345: * Stop searching as soon as we find one.
! 346: */
! 347: retcode = 0;
! 348: for (p = lockDesc->granted; p; p = p->next)
! 349: if (STRIPELOCK_CONFLICT(lockReqDesc, p)) {
! 350: retcode = 1;
! 351: break;
! 352: }
! 353: if (!retcode)
! 354: for (p = lockDesc->waitersH; p; p = p->next)
! 355: if (STRIPELOCK_CONFLICT(lockReqDesc, p))
! 356: {
! 357: retcode = 2;
! 358: break;
! 359: }
! 360: if (!retcode) {
! 361: /* No conflicts found => grant lock */
! 362: lockReqDesc->next = lockDesc->granted;
! 363: lockDesc->granted = lockReqDesc;
! 364: if (rf_stripeLockDebug) {
! 365: Dprintf7("[%d] no conflicts: lock %ld"
! 366: " %c %ld-%ld %ld-%ld granted.\n",
! 367: tid, stripeID, lockReqDesc->type,
! 368: lockReqDesc->start,
! 369: lockReqDesc->stop,
! 370: lockReqDesc->start2,
! 371: lockReqDesc->stop2);
! 372: FLUSH;
! 373: }
! 374: } else {
! 375: if (rf_stripeLockDebug) {
! 376: Dprintf6("[%d] conflict: lock %ld %c"
! 377: " %ld-%ld hashval=%d not"
! 378: " granted.\n", tid, stripeID,
! 379: lockReqDesc->type,
! 380: lockReqDesc->start,
! 381: lockReqDesc->stop,
! 382: hashval);
! 383: Dprintf3("[%d] lock %ld retcode=%d.\n",
! 384: tid, stripeID, retcode);
! 385: FLUSH;
! 386: }
! 387: /* Conflict => the current access must wait. */
! 388: rf_AddToWaitersQueue(lockTable, lockDesc,
! 389: lockReqDesc);
! 390: }
! 391: }
! 392: }
! 393:
! 394: RF_UNLOCK_MUTEX(lockTable[hashval].mutex);
! 395: return (retcode);
! 396: }
! 397:
! 398: void
! 399: rf_ReleaseStripeLock(RF_LockTableEntry_t *lockTable, RF_StripeNum_t stripeID,
! 400: RF_LockReqDesc_t *lockReqDesc)
! 401: {
! 402: RF_StripeLockDesc_t *lockDesc, *ld_t;
! 403: RF_LockReqDesc_t *lr, *lr_t, *callbacklist, *t;
! 404: RF_IoType_t type = lockReqDesc->type;
! 405: int tid = 0, hashval = HASH_STRIPEID(stripeID);
! 406: int release_it, consider_it;
! 407: RF_LockReqDesc_t *candidate, *candidate_t, *predecessor;
! 408:
! 409: RF_ASSERT(RF_IO_IS_R_OR_W(type));
! 410:
! 411: if (rf_stripeLockDebug) {
! 412: if (stripeID == -1)
! 413: Dprintf1("[%d] Lock release supressed"
! 414: " (stripeID == -1).\n", tid);
! 415: else {
! 416: Dprintf8("[%d] Releasing stripe lock on stripe ID %ld,"
! 417: " type %c range %ld-%ld %ld-%ld table 0x%lx.\n",
! 418: tid, stripeID, lockReqDesc->type,
! 419: lockReqDesc->start, lockReqDesc->stop,
! 420: lockReqDesc->start2, lockReqDesc->stop2,
! 421: lockTable);
! 422: FLUSH;
! 423: }
! 424: }
! 425: if (stripeID == -1)
! 426: return;
! 427:
! 428: RF_LOCK_MUTEX(lockTable[hashval].mutex);
! 429:
! 430: /* Find the stripe lock descriptor. */
! 431: for (ld_t = NULL, lockDesc = lockTable[hashval].descList;
! 432: lockDesc; ld_t = lockDesc, lockDesc = lockDesc->next) {
! 433: if (lockDesc->stripeID == stripeID)
! 434: break;
! 435: }
! 436: RF_ASSERT(lockDesc); /*
! 437: * Major error to release a lock that doesn't
! 438: * exist.
! 439: */
! 440:
! 441: /* Find the stripe lock request descriptor & delete it from the list. */
! 442: for (lr_t = NULL, lr = lockDesc->granted; lr; lr_t = lr, lr = lr->next)
! 443: if (lr == lockReqDesc)
! 444: break;
! 445:
! 446: RF_ASSERT(lr && (lr == lockReqDesc)); /*
! 447: * Major error to release a
! 448: * lock that hasn't been
! 449: * granted.
! 450: */
! 451: if (lr_t)
! 452: lr_t->next = lr->next;
! 453: else {
! 454: RF_ASSERT(lr == lockDesc->granted);
! 455: lockDesc->granted = lr->next;
! 456: }
! 457: lr->next = NULL;
! 458:
! 459: if (lockReqDesc->type == RF_IO_TYPE_WRITE)
! 460: lockDesc->nWriters--;
! 461:
! 462: /*
! 463: * Search through the waiters list to see if anyone needs to be woken
! 464: * up. For each such descriptor in the wait list, we check it against
! 465: * everything granted and against everything _in front_ of it in the
! 466: * waiters queue. If it conflicts with none of these, we release it.
! 467: *
! 468: * DON'T TOUCH THE TEMPLINK POINTER OF ANYTHING IN THE GRANTED LIST
! 469: * HERE.
! 470: * This will roach the case where the callback tries to acquire a new
! 471: * lock in the same stripe. There are some asserts to try and detect
! 472: * this.
! 473: *
! 474: * We apply 2 performance optimizations:
! 475: * (1) If releasing this lock results in no more writers to this
! 476: * stripe, we just release everybody waiting, since we place no
! 477: * restrictions on the number of concurrent reads.
! 478: * (2) We consider as candidates for wakeup only those waiters that
! 479: * have a range overlap with either the descriptor being woken up
! 480: * or with something in the callbacklist (i.e. something we've
! 481: * just now woken up).
! 482: * This allows us to avoid the long evaluation for some descriptors.
! 483: */
! 484:
! 485: callbacklist = NULL;
! 486: if (lockDesc->nWriters == 0) { /* Performance tweak (1). */
! 487: while (lockDesc->waitersH) {
! 488:
! 489: lr = lockDesc->waitersH; /*
! 490: * Delete from waiters
! 491: * list.
! 492: */
! 493: lockDesc->waitersH = lr->next;
! 494:
! 495: RF_ASSERT(lr->type == RF_IO_TYPE_READ);
! 496:
! 497: lr->next = lockDesc->granted; /*
! 498: * Add to granted list.
! 499: */
! 500: lockDesc->granted = lr;
! 501:
! 502: RF_ASSERT(!lr->templink);
! 503: lr->templink = callbacklist; /*
! 504: * Put on callback list
! 505: * so that we'll invoke
! 506: * callback below.
! 507: */
! 508: callbacklist = lr;
! 509: if (rf_stripeLockDebug) {
! 510: Dprintf8("[%d] No writers: granting lock"
! 511: " stripe ID %ld, type %c range %ld-%l"
! 512: "d %ld-%ld table 0x%lx.\n", tid, stripeID,
! 513: lr->type, lr->start, lr->stop,
! 514: lr->start2, lr->stop2,
! 515: (unsigned long) lockTable);
! 516: FLUSH;
! 517: }
! 518: }
! 519: lockDesc->waitersT = NULL; /*
! 520: * We've purged the whole
! 521: * waiters list.
! 522: */
! 523:
! 524: } else
! 525: for (candidate_t = NULL, candidate = lockDesc->waitersH;
! 526: candidate;) {
! 527:
! 528: /* Performance tweak (2). */
! 529: consider_it = 0;
! 530: if (RANGE_OVERLAP(lockReqDesc, candidate))
! 531: consider_it = 1;
! 532: else
! 533: for (t = callbacklist; t; t = t->templink)
! 534: if (RANGE_OVERLAP(t, candidate)) {
! 535: consider_it = 1;
! 536: break;
! 537: }
! 538: if (!consider_it) {
! 539: if (rf_stripeLockDebug) {
! 540: Dprintf8("[%d] No overlap: rejecting"
! 541: " candidate stripeID %ld, type %c"
! 542: " range %ld-%ld %ld-%ld table"
! 543: " 0x%lx.\n", tid, stripeID,
! 544: candidate->type,
! 545: candidate->start, candidate->stop,
! 546: candidate->start2, candidate->stop2,
! 547: (unsigned long) lockTable);
! 548: FLUSH;
! 549: }
! 550: candidate_t = candidate;
! 551: candidate = candidate->next;
! 552: continue;
! 553: }
! 554: /*
! 555: * We have a candidate for release. Check to make
! 556: * sure it is not blocked by any granted locks.
! 557: */
! 558: release_it = 1;
! 559: for (predecessor = lockDesc->granted; predecessor;
! 560: predecessor = predecessor->next) {
! 561: if (STRIPELOCK_CONFLICT(candidate, predecessor))
! 562: {
! 563: if (rf_stripeLockDebug) {
! 564: Dprintf8("[%d] Conflicts with"
! 565: " granted lock: rejecting"
! 566: " candidate stripeID %ld,"
! 567: " type %c range %ld-%ld"
! 568: " %ld-%ld table 0x%lx.\n",
! 569: tid, stripeID,
! 570: candidate->type,
! 571: candidate->start,
! 572: candidate->stop,
! 573: candidate->start2,
! 574: candidate->stop2,
! 575: (unsigned long) lockTable);
! 576: FLUSH;
! 577: }
! 578: release_it = 0;
! 579: break;
! 580: }
! 581: }
! 582:
! 583: /*
! 584: * Now check to see if the candidate is blocked by any
! 585: * waiters that occur before it in the wait queue.
! 586: */
! 587: if (release_it)
! 588: for (predecessor = lockDesc->waitersH;
! 589: predecessor != candidate;
! 590: predecessor = predecessor->next) {
! 591: if (STRIPELOCK_CONFLICT(candidate,
! 592: predecessor)) {
! 593: if (rf_stripeLockDebug) {
! 594: Dprintf8("[%d]"
! 595: " Conflicts with"
! 596: " waiting lock:"
! 597: " rejecting"
! 598: " candidate"
! 599: " stripeID %ld,"
! 600: " type %c"
! 601: " range %ld-%ld"
! 602: " %ld-%ld"
! 603: " table 0x%lx.\n",
! 604: tid, stripeID,
! 605: candidate->type,
! 606: candidate->start,
! 607: candidate->stop,
! 608: candidate->start2,
! 609: candidate->stop2,
! 610: (unsigned long)
! 611: lockTable);
! 612: FLUSH;
! 613: }
! 614: release_it = 0;
! 615: break;
! 616: }
! 617: }
! 618:
! 619: /* Release it if indicated. */
! 620: if (release_it) {
! 621: if (rf_stripeLockDebug) {
! 622: Dprintf8("[%d] Granting lock to"
! 623: " candidate stripeID %ld, type %c"
! 624: " range %ld-%ld %ld-%ld table"
! 625: " 0x%lx.\n", tid, stripeID,
! 626: candidate->type,
! 627: candidate->start, candidate->stop,
! 628: candidate->start2, candidate->stop2,
! 629: (unsigned long) lockTable);
! 630: FLUSH;
! 631: }
! 632: if (candidate_t) {
! 633: candidate_t->next = candidate->next;
! 634: if (lockDesc->waitersT == candidate)
! 635: /*
! 636: * Cannot be waitersH
! 637: * since candidate_t is
! 638: * not NULL.
! 639: */
! 640: lockDesc->waitersT =
! 641: candidate_t;
! 642: } else {
! 643: RF_ASSERT(candidate ==
! 644: lockDesc->waitersH);
! 645: lockDesc->waitersH =
! 646: lockDesc->waitersH->next;
! 647: if (!lockDesc->waitersH)
! 648: lockDesc->waitersT = NULL;
! 649: }
! 650: /* Move it to the granted list. */
! 651: candidate->next = lockDesc->granted;
! 652: lockDesc->granted = candidate;
! 653:
! 654: RF_ASSERT(!candidate->templink);
! 655: /*
! 656: * Put it on the list of things to be called
! 657: * after we release the mutex.
! 658: */
! 659: candidate->templink = callbacklist;
! 660: callbacklist = candidate;
! 661:
! 662: if (!candidate_t)
! 663: candidate = lockDesc->waitersH;
! 664: else
! 665: /*
! 666: * Continue with the rest of the list.
! 667: */
! 668: candidate = candidate_t->next;
! 669: } else {
! 670: candidate_t = candidate;
! 671: /* Continue with the rest of the list. */
! 672: candidate = candidate->next;
! 673: }
! 674: }
! 675:
! 676: /* Delete the descriptor if no one is waiting or active. */
! 677: if (!lockDesc->granted && !lockDesc->waitersH) {
! 678: RF_ASSERT(lockDesc->nWriters == 0);
! 679: if (rf_stripeLockDebug) {
! 680: Dprintf3("[%d] Last lock released (table 0x%lx):"
! 681: " deleting desc for stripeID %ld.\n", tid,
! 682: (unsigned long) lockTable, stripeID);
! 683: FLUSH;
! 684: }
! 685: if (ld_t)
! 686: ld_t->next = lockDesc->next;
! 687: else {
! 688: RF_ASSERT(lockDesc == lockTable[hashval].descList);
! 689: lockTable[hashval].descList = lockDesc->next;
! 690: }
! 691: rf_FreeStripeLockDesc(lockDesc);
! 692: lockDesc = NULL; /* Only for the ASSERT below. */
! 693: }
! 694: RF_UNLOCK_MUTEX(lockTable[hashval].mutex);
! 695:
! 696: /*
! 697: * Now that we've unlocked the mutex, invoke the callback on all the
! 698: * descriptors in the list.
! 699: */
! 700: RF_ASSERT(!((callbacklist) && (!lockDesc))); /*
! 701: * If we deleted the
! 702: * descriptor, we should
! 703: * have no callbacks to
! 704: * do.
! 705: */
! 706: for (candidate = callbacklist; candidate;) {
! 707: t = candidate;
! 708: candidate = candidate->templink;
! 709: t->templink = NULL;
! 710: (t->cbFunc) (t->cbArg);
! 711: }
! 712: }
! 713:
! 714: /* Must have the indicated lock table mutex upon entry. */
! 715: void
! 716: rf_AddToWaitersQueue(RF_LockTableEntry_t *lockTable,
! 717: RF_StripeLockDesc_t *lockDesc, RF_LockReqDesc_t *lockReqDesc)
! 718: {
! 719: int tid;
! 720:
! 721: if (rf_stripeLockDebug) {
! 722: Dprintf3("[%d] Waiting on lock for stripe %ld table 0x%lx.\n",
! 723: tid, lockDesc->stripeID, (unsigned long) lockTable);
! 724: FLUSH;
! 725: }
! 726: if (!lockDesc->waitersH) {
! 727: lockDesc->waitersH = lockDesc->waitersT = lockReqDesc;
! 728: } else {
! 729: lockDesc->waitersT->next = lockReqDesc;
! 730: lockDesc->waitersT = lockReqDesc;
! 731: }
! 732: }
! 733:
! 734: RF_StripeLockDesc_t *
! 735: rf_AllocStripeLockDesc(RF_StripeNum_t stripeID)
! 736: {
! 737: RF_StripeLockDesc_t *p;
! 738:
! 739: RF_FREELIST_GET(rf_stripelock_freelist, p, next,
! 740: (RF_StripeLockDesc_t *));
! 741: if (p) {
! 742: p->stripeID = stripeID;
! 743: }
! 744: return (p);
! 745: }
! 746:
! 747: void
! 748: rf_FreeStripeLockDesc(RF_StripeLockDesc_t *p)
! 749: {
! 750: RF_FREELIST_FREE(rf_stripelock_freelist, p, next);
! 751: }
! 752:
! 753: void
! 754: rf_PrintLockedStripes(RF_LockTableEntry_t *lockTable)
! 755: {
! 756: int i, j, foundone = 0, did;
! 757: RF_StripeLockDesc_t *p;
! 758: RF_LockReqDesc_t *q;
! 759:
! 760: RF_LOCK_MUTEX(rf_printf_mutex);
! 761: printf("Locked stripes:\n");
! 762: for (i = 0; i < rf_lockTableSize; i++)
! 763: if (lockTable[i].descList) {
! 764: foundone = 1;
! 765: for (p = lockTable[i].descList; p; p = p->next) {
! 766: printf("Stripe ID 0x%lx (%d) nWriters %d\n",
! 767: (long) p->stripeID, (int) p->stripeID,
! 768: p->nWriters);
! 769:
! 770: if (!(p->granted))
! 771: printf("Granted: (none)\n");
! 772: else
! 773: printf("Granted:\n");
! 774: for (did = 1, j = 0, q = p->granted; q;
! 775: j++, q = q->next) {
! 776: printf(" %c(%ld-%ld", q->type,
! 777: (long) q->start, (long) q->stop);
! 778: if (q->start2 != -1)
! 779: printf(",%ld-%ld) ",
! 780: (long) q->start2,
! 781: (long) q->stop2);
! 782: else
! 783: printf(") ");
! 784: if (j && !(j % 4)) {
! 785: printf("\n");
! 786: did = 1;
! 787: } else
! 788: did = 0;
! 789: }
! 790: if (!did)
! 791: printf("\n");
! 792:
! 793: if (!(p->waitersH))
! 794: printf("Waiting: (none)\n");
! 795: else
! 796: printf("Waiting:\n");
! 797: for (did = 1, j = 0, q = p->waitersH; q;
! 798: j++, q = q->next) {
! 799: printf("%c(%ld-%ld", q->type,
! 800: (long) q->start, (long) q->stop);
! 801: if (q->start2 != -1)
! 802: printf(",%ld-%ld) ",
! 803: (long) q->start2,
! 804: (long) q->stop2);
! 805: else
! 806: printf(") ");
! 807: if (j && !(j % 4)) {
! 808: printf("\n ");
! 809: did = 1;
! 810: } else
! 811: did = 0;
! 812: }
! 813: if (!did)
! 814: printf("\n");
! 815: }
! 816: }
! 817: if (!foundone)
! 818: printf("(none)\n");
! 819: else
! 820: printf("\n");
! 821: RF_UNLOCK_MUTEX(rf_printf_mutex);
! 822: }