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
rf_CheckCvscanState(RF_CvscanHeader_t * hdr,char * file,int line)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
rf_PriorityInsert(RF_DiskQueueData_t ** list_ptr,RF_DiskQueueData_t * req)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
rf_ReqInsert(RF_DiskQueueData_t ** list_ptr,RF_DiskQueueData_t * req,RF_CvscanArmDir_t order)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 *
rf_ReqDequeue(RF_DiskQueueData_t ** list_ptr)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
rf_ReBalance(RF_CvscanHeader_t * hdr)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
rf_Transfer(RF_DiskQueueData_t ** to_list_ptr,RF_DiskQueueData_t ** from_list_ptr)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
rf_RealEnqueue(RF_CvscanHeader_t * hdr,RF_DiskQueueData_t * req)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
rf_CvscanEnqueue(void * q_in,RF_DiskQueueData_t * elem,int priority)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 *
rf_CvscanDequeue(void * q_in)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 *
rf_CvscanPeek(void * q_in)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
rf_CvscanConfigure(void)339 rf_CvscanConfigure(void)
340 {
341 return (0);
342 }
343
344
345 void *
rf_CvscanCreate(RF_SectorCount_t sectPerDisk,RF_AllocListElem_t * clList,RF_ShutdownList_t ** listp)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
rf_PrintCvscanQueue(RF_CvscanHeader_t * hdr)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
rf_CvscanPromote(void * q_in,RF_StripeNum_t parityStripeID,RF_ReconUnitNum_t which_ru)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 }
463