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