Annotation of sys/dev/raidframe/rf_sstf.c, Revision 1.1.1.1
1.1 nbrk 1: /* $OpenBSD: rf_sstf.c,v 1.4 2002/12/16 07:01:05 tdeval Exp $ */
2: /* $NetBSD: rf_sstf.c,v 1.4 2000/01/08 23:45:05 oster Exp $ */
3:
4: /*
5: * Copyright (c) 1995 Carnegie-Mellon University.
6: * All rights reserved.
7: *
8: * Author: Jim Zelenka
9: *
10: * Permission to use, copy, modify and distribute this software and
11: * its documentation is hereby granted, provided that both the copyright
12: * notice and this permission notice appear in all copies of the
13: * software, derivative works or modified versions, and any portions
14: * thereof, and that both notices appear in supporting documentation.
15: *
16: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
17: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
18: * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
19: *
20: * Carnegie Mellon requests users of this software to return to
21: *
22: * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
23: * School of Computer Science
24: * Carnegie Mellon University
25: * Pittsburgh PA 15213-3890
26: *
27: * any improvements or extensions that they make and grant Carnegie the
28: * rights to redistribute these changes.
29: */
30:
31: /*****************************************************************************
32: *
33: * sstf.c -- Prioritized shortest seek time first disk queueing code.
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: /* Optimization. */
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: /* Insert after s, before r. */
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: /* Insert after s, at end of queue. */
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: /* For removing from head-of-queue. */
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: /* For removing from end-of-queue. */
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: /* Getting farther away. */
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: * Nothing in the direction we want to go. Reverse or
220: * reset the arm. We know we have an I/O in the other
221: * direction.
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: * Reset (beginning of queue).
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: /* Dequeue from middle of list. */
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: * There's I/Os to the left of the arm. Swing
484: * on back (swap queues).
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: * There's I/Os to the left of the arm. We'll end
600: * up swinging on back.
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: }
CVSweb