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