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