This source file includes following definitions.
- rf_do_sstf_ord_q
- rf_closest_to_arm
- rf_SstfCreate
- rf_ScanCreate
- rf_CscanCreate
- rf_SstfEnqueue
- rf_do_dequeue
- rf_SstfDequeue
- rf_ScanDequeue
- rf_CscanDequeue
- rf_SstfPeek
- rf_ScanPeek
- rf_CscanPeek
- rf_SstfPromote
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 #include "rf_alloclist.h"
38 #include "rf_stripelocks.h"
39 #include "rf_layout.h"
40 #include "rf_diskqueue.h"
41 #include "rf_sstf.h"
42 #include "rf_debugMem.h"
43 #include "rf_general.h"
44 #include "rf_options.h"
45 #include "rf_raid.h"
46 #include "rf_types.h"
47
48 #define DIR_LEFT 1
49 #define DIR_RIGHT 2
50 #define DIR_EITHER 3
51
52 #define SNUM_DIFF(_a_,_b_) \
53 (((_a_) > (_b_)) ? ((_a_) - (_b_)) : ((_b_) - (_a_)))
54
55 #define QSUM(_sstfq_) \
56 (((_sstfq_)->lopri.qlen) + ((_sstfq_)->left.qlen) + \
57 ((_sstfq_)->right.qlen))
58
59
60 void rf_do_sstf_ord_q(RF_DiskQueueData_t **, RF_DiskQueueData_t **,
61 RF_DiskQueueData_t *);
62 void rf_do_dequeue(RF_SstfQ_t *, RF_DiskQueueData_t *);
63 RF_DiskQueueData_t *rf_closest_to_arm(RF_SstfQ_t *, RF_SectorNum_t,
64 int *, int);
65
66
67 void
68 rf_do_sstf_ord_q(RF_DiskQueueData_t **queuep, RF_DiskQueueData_t **tailp,
69 RF_DiskQueueData_t *req)
70 {
71 RF_DiskQueueData_t *r, *s;
72
73 if (*queuep == NULL) {
74 *queuep = req;
75 *tailp = req;
76 req->next = NULL;
77 req->prev = NULL;
78 return;
79 }
80 if (req->sectorOffset <= (*queuep)->sectorOffset) {
81 req->next = *queuep;
82 req->prev = NULL;
83 (*queuep)->prev = req;
84 *queuep = req;
85 return;
86 }
87 if (req->sectorOffset > (*tailp)->sectorOffset) {
88
89 r = NULL;
90 s = *tailp;
91 goto q_at_end;
92 }
93 for (s = NULL, r = *queuep; r; s = r, r = r->next) {
94 if (r->sectorOffset >= req->sectorOffset) {
95
96 RF_ASSERT(s);
97 req->next = r;
98 r->prev = req;
99 s->next = req;
100 req->prev = s;
101 return;
102 }
103 }
104 q_at_end:
105
106 RF_ASSERT(r == NULL);
107 RF_ASSERT(s);
108 RF_ASSERT(s == (*tailp));
109 req->next = NULL;
110 req->prev = s;
111 s->next = req;
112 *tailp = req;
113 }
114
115
116 #define DO_HEAD_DEQ(_r_,_q_) \
117 do { \
118 _r_ = (_q_)->queue; \
119 RF_ASSERT((_r_) != NULL); \
120 (_q_)->queue = (_r_)->next; \
121 (_q_)->qlen--; \
122 if ((_q_)->qlen == 0) { \
123 RF_ASSERT((_r_) == (_q_)->qtail); \
124 RF_ASSERT((_q_)->queue == NULL); \
125 (_q_)->qtail = NULL; \
126 } else { \
127 RF_ASSERT((_q_)->queue->prev == (_r_)); \
128 (_q_)->queue->prev = NULL; \
129 } \
130 } while (0)
131
132
133 #define DO_TAIL_DEQ(_r_,_q_) \
134 do { \
135 _r_ = (_q_)->qtail; \
136 RF_ASSERT((_r_) != NULL); \
137 (_q_)->qtail = (_r_)->prev; \
138 (_q_)->qlen--; \
139 if ((_q_)->qlen == 0) { \
140 RF_ASSERT((_r_) == (_q_)->queue); \
141 RF_ASSERT((_q_)->qtail == NULL); \
142 (_q_)->queue = NULL; \
143 } else { \
144 RF_ASSERT((_q_)->qtail->next == (_r_)); \
145 (_q_)->qtail->next = NULL; \
146 } \
147 } while (0)
148
149 #define DO_BEST_DEQ(_l_,_r_,_q_) \
150 do { \
151 if (SNUM_DIFF((_q_)->queue->sectorOffset,_l_) \
152 < SNUM_DIFF((_q_)->qtail->sectorOffset,_l_)) \
153 { \
154 DO_HEAD_DEQ(_r_,_q_); \
155 } else { \
156 DO_TAIL_DEQ(_r_,_q_); \
157 } \
158 } while (0)
159
160 RF_DiskQueueData_t *
161 rf_closest_to_arm(RF_SstfQ_t *queue, RF_SectorNum_t arm_pos, int *dir,
162 int allow_reverse)
163 {
164 RF_SectorNum_t best_pos_l = 0, this_pos_l = 0, last_pos = 0;
165 RF_SectorNum_t best_pos_r = 0, this_pos_r = 0;
166 RF_DiskQueueData_t *r, *best_l, *best_r;
167
168 best_r = best_l = NULL;
169 for (r = queue->queue; r; r = r->next) {
170 if (r->sectorOffset < arm_pos) {
171 if (best_l == NULL) {
172 best_l = r;
173 last_pos = best_pos_l = this_pos_l;
174 } else {
175 this_pos_l = arm_pos - r->sectorOffset;
176 if (this_pos_l < best_pos_l) {
177 best_l = r;
178 last_pos = best_pos_l = this_pos_l;
179 } else {
180 last_pos = this_pos_l;
181 }
182 }
183 } else {
184 if (best_r == NULL) {
185 best_r = r;
186 last_pos = best_pos_r = this_pos_r;
187 } else {
188 this_pos_r = r->sectorOffset - arm_pos;
189 if (this_pos_r < best_pos_r) {
190 best_r = r;
191 last_pos = best_pos_r = this_pos_r;
192 } else {
193 last_pos = this_pos_r;
194 }
195 if (this_pos_r > last_pos) {
196
197 break;
198 }
199 }
200 }
201 }
202 if ((best_r == NULL) && (best_l == NULL))
203 return (NULL);
204 if ((*dir == DIR_RIGHT) && best_r)
205 return (best_r);
206 if ((*dir == DIR_LEFT) && best_l)
207 return (best_l);
208 if (*dir == DIR_EITHER) {
209 if (best_l == NULL)
210 return (best_r);
211 if (best_r == NULL)
212 return (best_l);
213 if (best_pos_r < best_pos_l)
214 return (best_r);
215 else
216 return (best_l);
217 }
218
219
220
221
222
223 if (allow_reverse) {
224 if (*dir == DIR_RIGHT) {
225 *dir = DIR_LEFT;
226 return (best_l);
227 } else {
228 *dir = DIR_RIGHT;
229 return (best_r);
230 }
231 }
232
233
234
235 RF_ASSERT(*dir == DIR_RIGHT);
236 return (queue->queue);
237 }
238
239 void *
240 rf_SstfCreate(RF_SectorCount_t sect_per_disk, RF_AllocListElem_t *cl_list,
241 RF_ShutdownList_t **listp)
242 {
243 RF_Sstf_t *sstfq;
244
245 RF_CallocAndAdd(sstfq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
246 sstfq->dir = DIR_EITHER;
247 sstfq->allow_reverse = 1;
248 return ((void *) sstfq);
249 }
250
251 void *
252 rf_ScanCreate(RF_SectorCount_t sect_per_disk, RF_AllocListElem_t *cl_list,
253 RF_ShutdownList_t **listp)
254 {
255 RF_Sstf_t *scanq;
256
257 RF_CallocAndAdd(scanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
258 scanq->dir = DIR_RIGHT;
259 scanq->allow_reverse = 1;
260 return ((void *) scanq);
261 }
262
263 void *
264 rf_CscanCreate(RF_SectorCount_t sect_per_disk, RF_AllocListElem_t *cl_list,
265 RF_ShutdownList_t **listp)
266 {
267 RF_Sstf_t *cscanq;
268
269 RF_CallocAndAdd(cscanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
270 cscanq->dir = DIR_RIGHT;
271 return ((void *) cscanq);
272 }
273
274 void
275 rf_SstfEnqueue(void *qptr, RF_DiskQueueData_t *req, int priority)
276 {
277 RF_Sstf_t *sstfq;
278
279 sstfq = (RF_Sstf_t *) qptr;
280
281 if (priority == RF_IO_LOW_PRIORITY) {
282 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
283 RF_DiskQueue_t *dq;
284 dq = (RF_DiskQueue_t *) req->queue;
285 printf("raid%d: ENQ lopri %d,%d queues are %d,%d,%d.\n",
286 req->raidPtr->raidid, dq->row, dq->col,
287 sstfq->left.qlen, sstfq->right.qlen,
288 sstfq->lopri.qlen);
289 }
290 rf_do_sstf_ord_q(&sstfq->lopri.queue, &sstfq->lopri.qtail, req);
291 sstfq->lopri.qlen++;
292 } else {
293 if (req->sectorOffset < sstfq->last_sector) {
294 rf_do_sstf_ord_q(&sstfq->left.queue,
295 &sstfq->left.qtail, req);
296 sstfq->left.qlen++;
297 } else {
298 rf_do_sstf_ord_q(&sstfq->right.queue,
299 &sstfq->right.qtail, req);
300 sstfq->right.qlen++;
301 }
302 }
303 }
304
305 void
306 rf_do_dequeue(RF_SstfQ_t *queue, RF_DiskQueueData_t *req)
307 {
308 RF_DiskQueueData_t *req2;
309
310 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
311 printf("raid%d: rf_do_dequeue.\n", req->raidPtr->raidid);
312 }
313 if (req == queue->queue) {
314 DO_HEAD_DEQ(req2, queue);
315 RF_ASSERT(req2 == req);
316 } else
317 if (req == queue->qtail) {
318 DO_TAIL_DEQ(req2, queue);
319 RF_ASSERT(req2 == req);
320 } else {
321
322 RF_ASSERT(req->next);
323 RF_ASSERT(req->prev);
324 queue->qlen--;
325 req->next->prev = req->prev;
326 req->prev->next = req->next;
327 req->next = req->prev = NULL;
328 }
329 }
330
331 RF_DiskQueueData_t *
332 rf_SstfDequeue(void *qptr)
333 {
334 RF_DiskQueueData_t *req = NULL;
335 RF_Sstf_t *sstfq;
336
337 sstfq = (RF_Sstf_t *) qptr;
338
339 if (rf_sstfDebug) {
340 RF_DiskQueue_t *dq;
341 dq = (RF_DiskQueue_t *) req->queue;
342 RF_ASSERT(QSUM(sstfq) == dq->queueLength);
343 printf("raid%d: sstf: Dequeue %d,%d queues are %d,%d,%d.\n",
344 req->raidPtr->raidid, dq->row, dq->col,
345 sstfq->left.qlen, sstfq->right.qlen, sstfq->lopri.qlen);
346 }
347 if (sstfq->left.queue == NULL) {
348 RF_ASSERT(sstfq->left.qlen == 0);
349 if (sstfq->right.queue == NULL) {
350 RF_ASSERT(sstfq->right.qlen == 0);
351 if (sstfq->lopri.queue == NULL) {
352 RF_ASSERT(sstfq->lopri.qlen == 0);
353 return (NULL);
354 }
355 if (rf_sstfDebug) {
356 printf("raid%d: sstf: check for close lopri.\n",
357 req->raidPtr->raidid);
358 }
359 req = rf_closest_to_arm(&sstfq->lopri,
360 sstfq->last_sector, &sstfq->dir,
361 sstfq->allow_reverse);
362 if (rf_sstfDebug) {
363 printf("raid%d: sstf: rf_closest_to_arm said"
364 " %lx.\n", req->raidPtr->raidid,
365 (long) req);
366 }
367 if (req == NULL)
368 return (NULL);
369 rf_do_dequeue(&sstfq->lopri, req);
370 } else {
371 DO_BEST_DEQ(sstfq->last_sector, req, &sstfq->right);
372 }
373 } else {
374 if (sstfq->right.queue == NULL) {
375 RF_ASSERT(sstfq->right.qlen == 0);
376 DO_BEST_DEQ(sstfq->last_sector, req, &sstfq->left);
377 } else {
378 if (SNUM_DIFF(sstfq->last_sector,
379 sstfq->right.queue->sectorOffset) <
380 SNUM_DIFF(sstfq->last_sector,
381 sstfq->left.qtail->sectorOffset)) {
382 DO_HEAD_DEQ(req, &sstfq->right);
383 } else {
384 DO_TAIL_DEQ(req, &sstfq->left);
385 }
386 }
387 }
388 RF_ASSERT(req);
389 sstfq->last_sector = req->sectorOffset;
390 return (req);
391 }
392
393 RF_DiskQueueData_t *
394 rf_ScanDequeue(void *qptr)
395 {
396 RF_DiskQueueData_t *req = NULL;
397 RF_Sstf_t *scanq;
398
399 scanq = (RF_Sstf_t *) qptr;
400
401 if (rf_scanDebug) {
402 RF_DiskQueue_t *dq;
403 dq = (RF_DiskQueue_t *) req->queue;
404 RF_ASSERT(QSUM(scanq) == dq->queueLength);
405 printf("raid%d: scan: Dequeue %d,%d queues are %d,%d,%d.\n",
406 req->raidPtr->raidid, dq->row, dq->col,
407 scanq->left.qlen, scanq->right.qlen, scanq->lopri.qlen);
408 }
409 if (scanq->left.queue == NULL) {
410 RF_ASSERT(scanq->left.qlen == 0);
411 if (scanq->right.queue == NULL) {
412 RF_ASSERT(scanq->right.qlen == 0);
413 if (scanq->lopri.queue == NULL) {
414 RF_ASSERT(scanq->lopri.qlen == 0);
415 return (NULL);
416 }
417 req = rf_closest_to_arm(&scanq->lopri,
418 scanq->last_sector, &scanq->dir,
419 scanq->allow_reverse);
420 if (req == NULL)
421 return (NULL);
422 rf_do_dequeue(&scanq->lopri, req);
423 } else {
424 scanq->dir = DIR_RIGHT;
425 DO_HEAD_DEQ(req, &scanq->right);
426 }
427 } else
428 if (scanq->right.queue == NULL) {
429 RF_ASSERT(scanq->right.qlen == 0);
430 RF_ASSERT(scanq->left.queue);
431 scanq->dir = DIR_LEFT;
432 DO_TAIL_DEQ(req, &scanq->left);
433 } else {
434 RF_ASSERT(scanq->right.queue);
435 RF_ASSERT(scanq->left.queue);
436 if (scanq->dir == DIR_RIGHT) {
437 DO_HEAD_DEQ(req, &scanq->right);
438 } else {
439 DO_TAIL_DEQ(req, &scanq->left);
440 }
441 }
442 RF_ASSERT(req);
443 scanq->last_sector = req->sectorOffset;
444 return (req);
445 }
446
447 RF_DiskQueueData_t *
448 rf_CscanDequeue(void *qptr)
449 {
450 RF_DiskQueueData_t *req = NULL;
451 RF_Sstf_t *cscanq;
452
453 cscanq = (RF_Sstf_t *) qptr;
454
455 RF_ASSERT(cscanq->dir == DIR_RIGHT);
456 if (rf_cscanDebug) {
457 RF_DiskQueue_t *dq;
458 dq = (RF_DiskQueue_t *) req->queue;
459 RF_ASSERT(QSUM(cscanq) == dq->queueLength);
460 printf("raid%d: scan: Dequeue %d,%d queues are %d,%d,%d.\n",
461 req->raidPtr->raidid, dq->row, dq->col,
462 cscanq->left.qlen, cscanq->right.qlen,
463 cscanq->lopri.qlen);
464 }
465 if (cscanq->right.queue) {
466 DO_HEAD_DEQ(req, &cscanq->right);
467 } else {
468 RF_ASSERT(cscanq->right.qlen == 0);
469 if (cscanq->left.queue == NULL) {
470 RF_ASSERT(cscanq->left.qlen == 0);
471 if (cscanq->lopri.queue == NULL) {
472 RF_ASSERT(cscanq->lopri.qlen == 0);
473 return (NULL);
474 }
475 req = rf_closest_to_arm(&cscanq->lopri,
476 cscanq->last_sector, &cscanq->dir,
477 cscanq->allow_reverse);
478 if (req == NULL)
479 return (NULL);
480 rf_do_dequeue(&cscanq->lopri, req);
481 } else {
482
483
484
485
486 cscanq->right = cscanq->left;
487 cscanq->left.qlen = 0;
488 cscanq->left.queue = cscanq->left.qtail = NULL;
489 DO_HEAD_DEQ(req, &cscanq->right);
490 }
491 }
492 RF_ASSERT(req);
493 cscanq->last_sector = req->sectorOffset;
494 return (req);
495 }
496
497 RF_DiskQueueData_t *
498 rf_SstfPeek(void *qptr)
499 {
500 RF_DiskQueueData_t *req;
501 RF_Sstf_t *sstfq;
502
503 sstfq = (RF_Sstf_t *) qptr;
504
505 if ((sstfq->left.queue == NULL) && (sstfq->right.queue == NULL)) {
506 req = rf_closest_to_arm(&sstfq->lopri, sstfq->last_sector,
507 &sstfq->dir, sstfq->allow_reverse);
508 } else {
509 if (sstfq->left.queue == NULL)
510 req = sstfq->right.queue;
511 else {
512 if (sstfq->right.queue == NULL)
513 req = sstfq->left.queue;
514 else {
515 if (SNUM_DIFF(sstfq->last_sector,
516 sstfq->right.queue->sectorOffset) <
517 SNUM_DIFF(sstfq->last_sector,
518 sstfq->left.qtail->sectorOffset)) {
519 req = sstfq->right.queue;
520 } else {
521 req = sstfq->left.qtail;
522 }
523 }
524 }
525 }
526 if (req == NULL) {
527 RF_ASSERT(QSUM(sstfq) == 0);
528 }
529 return (req);
530 }
531
532 RF_DiskQueueData_t *
533 rf_ScanPeek(void *qptr)
534 {
535 RF_DiskQueueData_t *req;
536 RF_Sstf_t *scanq;
537 int dir;
538
539 scanq = (RF_Sstf_t *) qptr;
540 dir = scanq->dir;
541
542 if (scanq->left.queue == NULL) {
543 RF_ASSERT(scanq->left.qlen == 0);
544 if (scanq->right.queue == NULL) {
545 RF_ASSERT(scanq->right.qlen == 0);
546 if (scanq->lopri.queue == NULL) {
547 RF_ASSERT(scanq->lopri.qlen == 0);
548 return (NULL);
549 }
550 req = rf_closest_to_arm(&scanq->lopri,
551 scanq->last_sector, &dir, scanq->allow_reverse);
552 } else {
553 req = scanq->right.queue;
554 }
555 } else
556 if (scanq->right.queue == NULL) {
557 RF_ASSERT(scanq->right.qlen == 0);
558 RF_ASSERT(scanq->left.queue);
559 req = scanq->left.qtail;
560 } else {
561 RF_ASSERT(scanq->right.queue);
562 RF_ASSERT(scanq->left.queue);
563 if (scanq->dir == DIR_RIGHT) {
564 req = scanq->right.queue;
565 } else {
566 req = scanq->left.qtail;
567 }
568 }
569 if (req == NULL) {
570 RF_ASSERT(QSUM(scanq) == 0);
571 }
572 return (req);
573 }
574
575 RF_DiskQueueData_t *
576 rf_CscanPeek(void *qptr)
577 {
578 RF_DiskQueueData_t *req;
579 RF_Sstf_t *cscanq;
580
581 cscanq = (RF_Sstf_t *) qptr;
582
583 RF_ASSERT(cscanq->dir == DIR_RIGHT);
584 if (cscanq->right.queue) {
585 req = cscanq->right.queue;
586 } else {
587 RF_ASSERT(cscanq->right.qlen == 0);
588 if (cscanq->left.queue == NULL) {
589 RF_ASSERT(cscanq->left.qlen == 0);
590 if (cscanq->lopri.queue == NULL) {
591 RF_ASSERT(cscanq->lopri.qlen == 0);
592 return (NULL);
593 }
594 req = rf_closest_to_arm(&cscanq->lopri,
595 cscanq->last_sector, &cscanq->dir,
596 cscanq->allow_reverse);
597 } else {
598
599
600
601
602 req = cscanq->left.queue;
603 }
604 }
605 if (req == NULL) {
606 RF_ASSERT(QSUM(cscanq) == 0);
607 }
608 return (req);
609 }
610
611 int
612 rf_SstfPromote(void *qptr, RF_StripeNum_t parityStripeID,
613 RF_ReconUnitNum_t which_ru)
614 {
615 RF_DiskQueueData_t *r, *next;
616 RF_Sstf_t *sstfq;
617 int n;
618
619 sstfq = (RF_Sstf_t *) qptr;
620
621 n = 0;
622 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
623 printf("raid%d: promote %ld %d queues are %d,%d,%d.\n",
624 r->raidPtr->raidid, (long) parityStripeID,
625 (int) which_ru, sstfq->left.qlen, sstfq->right.qlen,
626 sstfq->lopri.qlen);
627 }
628 for (r = sstfq->lopri.queue; r; r = next) {
629 next = r->next;
630 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
631 printf("raid%d: check promote %lx.\n",
632 r->raidPtr->raidid, (long) r);
633 }
634 if ((r->parityStripeID == parityStripeID)
635 && (r->which_ru == which_ru)) {
636 rf_do_dequeue(&sstfq->lopri, r);
637 rf_SstfEnqueue(qptr, r, RF_IO_NORMAL_PRIORITY);
638 n++;
639 }
640 }
641 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
642 printf("raid%d: promoted %d matching I/Os queues are"
643 " %d,%d,%d.\n", r->raidPtr->raidid, n, sstfq->left.qlen,
644 sstfq->right.qlen, sstfq->lopri.qlen);
645 }
646 return (n);
647 }