Annotation of sys/dev/raidframe/rf_cvscan.c, Revision 1.1.1.1
1.1 nbrk 1: /* $OpenBSD: rf_cvscan.c,v 1.5 2002/12/16 07:01:03 tdeval Exp $ */
2: /* $NetBSD: rf_cvscan.c,v 1.5 1999/08/13 03:41:53 oster Exp $ */
3:
4: /*
5: * Copyright (c) 1995 Carnegie-Mellon University.
6: * All rights reserved.
7: *
8: * Author: Mark Holland
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: * cvscan.c -- prioritized cvscan disk queueing code.
34: *
35: * Nov 9, 1994, adapted from raidSim version (MCH)
36: *
37: *****************************************************************************/
38:
39: #include "rf_types.h"
40: #include "rf_alloclist.h"
41: #include "rf_stripelocks.h"
42: #include "rf_layout.h"
43: #include "rf_diskqueue.h"
44: #include "rf_cvscan.h"
45: #include "rf_debugMem.h"
46: #include "rf_general.h"
47:
48: void rf_CheckCvscanState(RF_CvscanHeader_t *, char *, int);
49: void rf_PriorityInsert(RF_DiskQueueData_t **, RF_DiskQueueData_t *);
50: void rf_ReqInsert(RF_DiskQueueData_t **, RF_DiskQueueData_t *,
51: RF_CvscanArmDir_t);
52: RF_DiskQueueData_t *rf_ReqDequeue(RF_DiskQueueData_t **);
53: void rf_ReBalance(RF_CvscanHeader_t *);
54: void rf_Transfer(RF_DiskQueueData_t **, RF_DiskQueueData_t **);
55: void rf_RealEnqueue(RF_CvscanHeader_t *, RF_DiskQueueData_t *);
56:
57: #define DO_CHECK_STATE(_hdr_) rf_CheckCvscanState((_hdr_), __FILE__, __LINE__)
58:
59: #define pri_ok(p) (((p) == RF_IO_NORMAL_PRIORITY) || \
60: ((p) == RF_IO_LOW_PRIORITY))
61:
62:
63: void
64: rf_CheckCvscanState(RF_CvscanHeader_t *hdr, char *file, int line)
65: {
66: long i, key;
67: RF_DiskQueueData_t *tmp;
68:
69: if (hdr->left != (RF_DiskQueueData_t *) NULL)
70: RF_ASSERT(hdr->left->sectorOffset < hdr->cur_block);
71: for (key = hdr->cur_block, i = 0, tmp = hdr->left;
72: tmp != (RF_DiskQueueData_t *) NULL;
73: key = tmp->sectorOffset, i++, tmp = tmp->next)
74: RF_ASSERT(tmp->sectorOffset <= key
75: && tmp->priority == hdr->nxt_priority &&
76: pri_ok(tmp->priority));
77: RF_ASSERT(i == hdr->left_cnt);
78:
79: for (key = hdr->cur_block, i = 0, tmp = hdr->right;
80: tmp != (RF_DiskQueueData_t *) NULL;
81: key = tmp->sectorOffset, i++, tmp = tmp->next) {
82: RF_ASSERT(key <= tmp->sectorOffset);
83: RF_ASSERT(tmp->priority == hdr->nxt_priority);
84: RF_ASSERT(pri_ok(tmp->priority));
85: }
86: RF_ASSERT(i == hdr->right_cnt);
87:
88: for (key = hdr->nxt_priority - 1, tmp = hdr->burner;
89: tmp != (RF_DiskQueueData_t *) NULL;
90: key = tmp->priority, tmp = tmp->next) {
91: RF_ASSERT(tmp);
92: RF_ASSERT(hdr);
93: RF_ASSERT(pri_ok(tmp->priority));
94: RF_ASSERT(key >= tmp->priority);
95: RF_ASSERT(tmp->priority < hdr->nxt_priority);
96: }
97: }
98:
99:
100: void
101: rf_PriorityInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req)
102: {
103: /*
104: * Insert block pointed to by req into list whose first entry is
105: * pointed to by the pointer that list_ptr points to.
106: * i.e. list_ptr is a grandparent of the first entry.
107: */
108:
109: for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
110: (*list_ptr)->priority > req->priority;
111: list_ptr = &((*list_ptr)->next)) {
112: }
113: req->next = (*list_ptr);
114: (*list_ptr) = req;
115: }
116:
117:
118: void
119: rf_ReqInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req,
120: RF_CvscanArmDir_t order)
121: {
122: /*
123: * Insert block pointed to by req into list whose first entry is
124: * pointed to by the pointer that list_ptr points to.
125: * i.e. list_ptr is a grandparent of the first entry.
126: */
127:
128: for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
129: ((order == rf_cvscan_RIGHT && (*list_ptr)->sectorOffset <=
130: req->sectorOffset) || (order == rf_cvscan_LEFT &&
131: (*list_ptr)->sectorOffset > req->sectorOffset));
132: list_ptr = &((*list_ptr)->next)) {
133: }
134: req->next = (*list_ptr);
135: (*list_ptr) = req;
136: }
137:
138:
139: RF_DiskQueueData_t *
140: rf_ReqDequeue(RF_DiskQueueData_t **list_ptr)
141: {
142: RF_DiskQueueData_t *ret = (*list_ptr);
143: if ((*list_ptr) != (RF_DiskQueueData_t *) NULL) {
144: (*list_ptr) = (*list_ptr)->next;
145: }
146: return (ret);
147: }
148:
149:
150: void
151: rf_ReBalance(RF_CvscanHeader_t *hdr)
152: {
153: /* DO_CHECK_STATE(hdr); */
154: while (hdr->right != (RF_DiskQueueData_t *) NULL
155: && hdr->right->sectorOffset < hdr->cur_block) {
156: hdr->right_cnt--;
157: hdr->left_cnt++;
158: rf_ReqInsert(&hdr->left, rf_ReqDequeue(&hdr->right),
159: rf_cvscan_LEFT);
160: }
161: /* DO_CHECK_STATE(hdr); */
162: }
163:
164:
165: void
166: rf_Transfer(RF_DiskQueueData_t **to_list_ptr, RF_DiskQueueData_t **from_list_ptr)
167: {
168: RF_DiskQueueData_t *gp;
169: for (gp = (*from_list_ptr); gp != (RF_DiskQueueData_t *) NULL;) {
170: RF_DiskQueueData_t *p = gp->next;
171: rf_PriorityInsert(to_list_ptr, gp);
172: gp = p;
173: }
174: (*from_list_ptr) = (RF_DiskQueueData_t *) NULL;
175: }
176:
177:
178: void
179: rf_RealEnqueue(RF_CvscanHeader_t *hdr, RF_DiskQueueData_t *req)
180: {
181: RF_ASSERT(req->priority == RF_IO_NORMAL_PRIORITY ||
182: req->priority == RF_IO_LOW_PRIORITY);
183:
184: DO_CHECK_STATE(hdr);
185: if (hdr->left_cnt == 0 && hdr->right_cnt == 0) {
186: hdr->nxt_priority = req->priority;
187: }
188: if (req->priority > hdr->nxt_priority) {
189: /*
190: * Dump all other outstanding requests on the back burner.
191: */
192: rf_Transfer(&hdr->burner, &hdr->left);
193: rf_Transfer(&hdr->burner, &hdr->right);
194: hdr->left_cnt = 0;
195: hdr->right_cnt = 0;
196: hdr->nxt_priority = req->priority;
197: }
198: if (req->priority < hdr->nxt_priority) {
199: /*
200: * Yet another low priority task !
201: */
202: rf_PriorityInsert(&hdr->burner, req);
203: } else {
204: if (req->sectorOffset < hdr->cur_block) {
205: /* This request is to the left of the current arms. */
206: rf_ReqInsert(&hdr->left, req, rf_cvscan_LEFT);
207: hdr->left_cnt++;
208: } else {
209: /* This request is to the right of the current arms. */
210: rf_ReqInsert(&hdr->right, req, rf_cvscan_RIGHT);
211: hdr->right_cnt++;
212: }
213: }
214: DO_CHECK_STATE(hdr);
215: }
216:
217:
218: void
219: rf_CvscanEnqueue(void *q_in, RF_DiskQueueData_t *elem, int priority)
220: {
221: RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
222: rf_RealEnqueue(hdr, elem /* req */ );
223: }
224:
225:
226: RF_DiskQueueData_t *
227: rf_CvscanDequeue(void *q_in)
228: {
229: RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
230: long range, i, sum_dist_left, sum_dist_right;
231: RF_DiskQueueData_t *ret;
232: RF_DiskQueueData_t *tmp;
233:
234: DO_CHECK_STATE(hdr);
235:
236: if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
237: return ((RF_DiskQueueData_t *) NULL);
238:
239: range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt,
240: hdr->right_cnt));
241: for (i = 0, tmp = hdr->left, sum_dist_left =
242: ((hdr->direction == rf_cvscan_RIGHT) ?
243: range * hdr->change_penalty : 0);
244: tmp != (RF_DiskQueueData_t *) NULL && i < range;
245: tmp = tmp->next, i++) {
246: sum_dist_left += hdr->cur_block - tmp->sectorOffset;
247: }
248: for (i = 0, tmp = hdr->right, sum_dist_right =
249: ((hdr->direction == rf_cvscan_LEFT) ?
250: range * hdr->change_penalty : 0);
251: tmp != (RF_DiskQueueData_t *) NULL && i < range;
252: tmp = tmp->next, i++) {
253: sum_dist_right += tmp->sectorOffset - hdr->cur_block;
254: }
255:
256: if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right) {
257: hdr->direction = rf_cvscan_LEFT;
258: hdr->cur_block = hdr->left->sectorOffset + hdr->left->numSector;
259: hdr->left_cnt = RF_MAX(hdr->left_cnt - 1, 0);
260: tmp = hdr->left;
261: ret = (rf_ReqDequeue(&hdr->left)) /*->parent*/ ;
262: } else {
263: hdr->direction = rf_cvscan_RIGHT;
264: hdr->cur_block = hdr->right->sectorOffset +
265: hdr->right->numSector;
266: hdr->right_cnt = RF_MAX(hdr->right_cnt - 1, 0);
267: tmp = hdr->right;
268: ret = (rf_ReqDequeue(&hdr->right)) /*->parent*/ ;
269: }
270: rf_ReBalance(hdr);
271:
272: if (hdr->left_cnt == 0 && hdr->right_cnt == 0
273: && hdr->burner != (RF_DiskQueueData_t *) NULL) {
274: /*
275: * Restore low priority requests for next dequeue.
276: */
277: RF_DiskQueueData_t *burner = hdr->burner;
278: hdr->nxt_priority = burner->priority;
279: while (burner != (RF_DiskQueueData_t *) NULL &&
280: burner->priority == hdr->nxt_priority) {
281: RF_DiskQueueData_t *next = burner->next;
282: rf_RealEnqueue(hdr, burner);
283: burner = next;
284: }
285: hdr->burner = burner;
286: }
287: DO_CHECK_STATE(hdr);
288: return (ret);
289: }
290:
291:
292: RF_DiskQueueData_t *
293: rf_CvscanPeek(void *q_in)
294: {
295: RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
296: long range, i, sum_dist_left, sum_dist_right;
297: RF_DiskQueueData_t *tmp, *headElement;
298:
299: DO_CHECK_STATE(hdr);
300:
301: if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
302: headElement = NULL;
303: else {
304: range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt,
305: hdr->right_cnt));
306: for (i = 0, tmp = hdr->left, sum_dist_left =
307: ((hdr->direction == rf_cvscan_RIGHT) ?
308: range * hdr->change_penalty : 0);
309: tmp != (RF_DiskQueueData_t *) NULL && i < range;
310: tmp = tmp->next, i++) {
311: sum_dist_left += hdr->cur_block - tmp->sectorOffset;
312: }
313: for (i = 0, tmp = hdr->right, sum_dist_right =
314: ((hdr->direction == rf_cvscan_LEFT) ?
315: range * hdr->change_penalty : 0);
316: tmp != (RF_DiskQueueData_t *) NULL && i < range;
317: tmp = tmp->next, i++) {
318: sum_dist_right += tmp->sectorOffset - hdr->cur_block;
319: }
320:
321: if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right)
322: headElement = hdr->left;
323: else
324: headElement = hdr->right;
325: }
326: return (headElement);
327: }
328:
329:
330: /*
331: * CVSCAN( 1, 0 ) is Shortest Seek Time First (SSTF)
332: * lowest average response time
333: * CVSCAN( 1, infinity ) is SCAN
334: * lowest response time standard deviation
335: */
336:
337:
338: int
339: rf_CvscanConfigure(void)
340: {
341: return (0);
342: }
343:
344:
345: void *
346: rf_CvscanCreate(RF_SectorCount_t sectPerDisk, RF_AllocListElem_t *clList,
347: RF_ShutdownList_t **listp)
348: {
349: RF_CvscanHeader_t *hdr;
350: long range = 2; /* Currently no mechanism to change these. */
351: long penalty = sectPerDisk / 5;
352:
353: RF_MallocAndAdd(hdr, sizeof(RF_CvscanHeader_t), (RF_CvscanHeader_t *),
354: clList);
355: bzero((char *) hdr, sizeof(RF_CvscanHeader_t));
356: hdr->range_for_avg = RF_MAX(range, 1);
357: hdr->change_penalty = RF_MAX(penalty, 0);
358: hdr->direction = rf_cvscan_RIGHT;
359: hdr->cur_block = 0;
360: hdr->left_cnt = hdr->right_cnt = 0;
361: hdr->left = hdr->right = (RF_DiskQueueData_t *) NULL;
362: hdr->burner = (RF_DiskQueueData_t *) NULL;
363: DO_CHECK_STATE(hdr);
364:
365: return ((void *) hdr);
366: }
367:
368:
369: #if (defined(__NetBSD__) || defined(__OpenBSD__)) && defined(_KERNEL)
370: /* rf_PrintCvscanQueue is not used, so we ignore it... */
371: #else
372: void
373: rf_PrintCvscanQueue(RF_CvscanHeader_t *hdr)
374: {
375: RF_DiskQueueData_t *tmp;
376:
377: printf("CVSCAN(%d,%d) at %d going %s\n",
378: (int) hdr->range_for_avg,
379: (int) hdr->change_penalty,
380: (int) hdr->cur_block,
381: (hdr->direction == rf_cvscan_LEFT) ? "LEFT" : "RIGHT");
382: printf("\tLeft(%d): ", hdr->left_cnt);
383: for (tmp = hdr->left; tmp != (RF_DiskQueueData_t *) NULL;
384: tmp = tmp->next)
385: printf("(%d,%ld,%d) ",
386: (int) tmp->sectorOffset,
387: (long) (tmp->sectorOffset + tmp->numSector),
388: tmp->priority);
389: printf("\n");
390: printf("\tRight(%d): ", hdr->right_cnt);
391: for (tmp = hdr->right; tmp != (RF_DiskQueueData_t *) NULL;
392: tmp = tmp->next)
393: printf("(%d,%ld,%d) ",
394: (int) tmp->sectorOffset,
395: (long) (tmp->sectorOffset + tmp->numSector),
396: tmp->priority);
397: printf("\n");
398: printf("\tBurner: ");
399: for (tmp = hdr->burner; tmp != (RF_DiskQueueData_t *) NULL;
400: tmp = tmp->next)
401: printf("(%d,%ld,%d) ",
402: (int) tmp->sectorOffset,
403: (long) (tmp->sectorOffset + tmp->numSector),
404: tmp->priority);
405: printf("\n");
406: }
407: #endif
408:
409:
410: /*
411: * Promote reconstruction accesses for the given stripeID to normal priority.
412: * Return 1 if an access was found and zero otherwise.
413: * Normally, we should only have one or zero entries in the burner queue,
414: * so execution time should be short.
415: */
416: int
417: rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID,
418: RF_ReconUnitNum_t which_ru)
419: {
420: RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
421: RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL;
422: int retval = 0;
423:
424: DO_CHECK_STATE(hdr);
425: while (tmp) { /* Handle entries at the front of the list. */
426: if (tmp->parityStripeID == parityStripeID &&
427: tmp->which_ru == which_ru) {
428: hdr->burner = tmp->next;
429: tmp->priority = RF_IO_NORMAL_PRIORITY;
430: tmp->next = tlist;
431: tlist = tmp;
432: tmp = hdr->burner;
433: } else
434: break;
435: }
436: if (tmp) {
437: trailer = tmp;
438: tmp = tmp->next;
439: }
440: while (tmp) { /* Handle entries on the rest of the list. */
441: if (tmp->parityStripeID == parityStripeID &&
442: tmp->which_ru == which_ru) {
443: trailer->next = tmp->next;
444: tmp->priority = RF_IO_NORMAL_PRIORITY;
445: tmp->next = tlist;
446: tlist = tmp; /* Insert on a temp queue. */
447: tmp = trailer->next;
448: } else {
449: trailer = tmp;
450: tmp = tmp->next;
451: }
452: }
453: while (tlist) {
454: retval++;
455: tmp = tlist->next;
456: rf_RealEnqueue(hdr, tlist);
457: tlist = tmp;
458: }
459: RF_ASSERT(retval == 0 || retval == 1);
460: DO_CHECK_STATE((RF_CvscanHeader_t *) q_in);
461: return (retval);
462: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_cvscan.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe