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