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