xref: /netbsd/sys/dev/raidframe/rf_cvscan.c (revision bf9ec67e)
1 /*	$NetBSD: rf_cvscan.c,v 1.8 2001/11/13 07:11:12 lukem Exp $	*/
2 /*
3  * Copyright (c) 1995 Carnegie-Mellon University.
4  * All rights reserved.
5  *
6  * Author: Mark Holland
7  *
8  * Permission to use, copy, modify and distribute this software and
9  * its documentation is hereby granted, provided that both the copyright
10  * notice and this permission notice appear in all copies of the
11  * software, derivative works or modified versions, and any portions
12  * thereof, and that both notices appear in supporting documentation.
13  *
14  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
15  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
16  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
17  *
18  * Carnegie Mellon requests users of this software to return to
19  *
20  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
21  *  School of Computer Science
22  *  Carnegie Mellon University
23  *  Pittsburgh PA 15213-3890
24  *
25  * any improvements or extensions that they make and grant Carnegie the
26  * rights to redistribute these changes.
27  */
28 
29 /*******************************************************************************
30  *
31  * cvscan.c --  prioritized cvscan disk queueing code.
32  *
33  * Nov 9, 1994, adapted from raidSim version (MCH)
34  *
35  ******************************************************************************/
36 
37 #include <sys/cdefs.h>
38 __KERNEL_RCSID(0, "$NetBSD: rf_cvscan.c,v 1.8 2001/11/13 07:11:12 lukem Exp $");
39 
40 #include <dev/raidframe/raidframevar.h>
41 #include "rf_alloclist.h"
42 #include "rf_stripelocks.h"
43 #include "rf_layout.h"
44 #include "rf_diskqueue.h"
45 #include "rf_cvscan.h"
46 #include "rf_debugMem.h"
47 #include "rf_general.h"
48 
49 #define DO_CHECK_STATE(_hdr_) CheckCvscanState((_hdr_), __FILE__, __LINE__)
50 
51 #define pri_ok(p)  ( ((p) == RF_IO_NORMAL_PRIORITY) || ((p) == RF_IO_LOW_PRIORITY))
52 
53 static void
54 CheckCvscanState(RF_CvscanHeader_t * hdr, char *file, int line)
55 {
56 	long    i, key;
57 	RF_DiskQueueData_t *tmp;
58 
59 	if (hdr->left != (RF_DiskQueueData_t *) NULL)
60 		RF_ASSERT(hdr->left->sectorOffset < hdr->cur_block);
61 	for (key = hdr->cur_block, i = 0, tmp = hdr->left;
62 	    tmp != (RF_DiskQueueData_t *) NULL;
63 	    key = tmp->sectorOffset, i++, tmp = tmp->next)
64 		RF_ASSERT(tmp->sectorOffset <= key
65 		    && tmp->priority == hdr->nxt_priority && pri_ok(tmp->priority));
66 	RF_ASSERT(i == hdr->left_cnt);
67 
68 	for (key = hdr->cur_block, i = 0, tmp = hdr->right;
69 	    tmp != (RF_DiskQueueData_t *) NULL;
70 	    key = tmp->sectorOffset, i++, tmp = tmp->next) {
71 		RF_ASSERT(key <= tmp->sectorOffset);
72 		RF_ASSERT(tmp->priority == hdr->nxt_priority);
73 		RF_ASSERT(pri_ok(tmp->priority));
74 	}
75 	RF_ASSERT(i == hdr->right_cnt);
76 
77 	for (key = hdr->nxt_priority - 1, tmp = hdr->burner;
78 	    tmp != (RF_DiskQueueData_t *) NULL;
79 	    key = tmp->priority, tmp = tmp->next) {
80 		RF_ASSERT(tmp);
81 		RF_ASSERT(hdr);
82 		RF_ASSERT(pri_ok(tmp->priority));
83 		RF_ASSERT(key >= tmp->priority);
84 		RF_ASSERT(tmp->priority < hdr->nxt_priority);
85 	}
86 }
87 
88 
89 
90 static void
91 PriorityInsert(RF_DiskQueueData_t ** list_ptr, RF_DiskQueueData_t * req)
92 {
93 	/* * insert block pointed to by req in to list whose first * entry is
94 	 * pointed to by the pointer that list_ptr points to * ie., list_ptr
95 	 * is a grandparent of the first entry */
96 
97 	for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
98 	    (*list_ptr)->priority > req->priority;
99 	    list_ptr = &((*list_ptr)->next)) {
100 	}
101 	req->next = (*list_ptr);
102 	(*list_ptr) = req;
103 }
104 
105 
106 
107 static void
108 ReqInsert(RF_DiskQueueData_t ** list_ptr, RF_DiskQueueData_t * req, RF_CvscanArmDir_t order)
109 {
110 	/* * insert block pointed to by req in to list whose first * entry is
111 	 * pointed to by the pointer that list_ptr points to * ie., list_ptr
112 	 * is a grandparent of the first entry */
113 
114 	for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
115 
116 	    ((order == rf_cvscan_RIGHT && (*list_ptr)->sectorOffset <= req->sectorOffset)
117 		|| (order == rf_cvscan_LEFT && (*list_ptr)->sectorOffset > req->sectorOffset));
118 	    list_ptr = &((*list_ptr)->next)) {
119 	}
120 	req->next = (*list_ptr);
121 	(*list_ptr) = req;
122 }
123 
124 
125 
126 static RF_DiskQueueData_t *
127 ReqDequeue(RF_DiskQueueData_t ** list_ptr)
128 {
129 	RF_DiskQueueData_t *ret = (*list_ptr);
130 	if ((*list_ptr) != (RF_DiskQueueData_t *) NULL) {
131 		(*list_ptr) = (*list_ptr)->next;
132 	}
133 	return (ret);
134 }
135 
136 
137 
138 static void
139 ReBalance(RF_CvscanHeader_t * hdr)
140 {
141 	/* DO_CHECK_STATE(hdr); */
142 	while (hdr->right != (RF_DiskQueueData_t *) NULL
143 	    && hdr->right->sectorOffset < hdr->cur_block) {
144 		hdr->right_cnt--;
145 		hdr->left_cnt++;
146 		ReqInsert(&hdr->left, ReqDequeue(&hdr->right), rf_cvscan_LEFT);
147 	}
148 	/* DO_CHECK_STATE(hdr); */
149 }
150 
151 
152 
153 static void
154 Transfer(RF_DiskQueueData_t ** to_list_ptr, RF_DiskQueueData_t ** from_list_ptr)
155 {
156 	RF_DiskQueueData_t *gp;
157 	for (gp = (*from_list_ptr); gp != (RF_DiskQueueData_t *) NULL;) {
158 		RF_DiskQueueData_t *p = gp->next;
159 		PriorityInsert(to_list_ptr, gp);
160 		gp = p;
161 	}
162 	(*from_list_ptr) = (RF_DiskQueueData_t *) NULL;
163 }
164 
165 
166 
167 static void
168 RealEnqueue(RF_CvscanHeader_t * hdr, RF_DiskQueueData_t * req)
169 {
170 	RF_ASSERT(req->priority == RF_IO_NORMAL_PRIORITY || req->priority == RF_IO_LOW_PRIORITY);
171 
172 	DO_CHECK_STATE(hdr);
173 	if (hdr->left_cnt == 0 && hdr->right_cnt == 0) {
174 		hdr->nxt_priority = req->priority;
175 	}
176 	if (req->priority > hdr->nxt_priority) {
177 		/*
178 		** dump all other outstanding requests on the back burner
179 		*/
180 		Transfer(&hdr->burner, &hdr->left);
181 		Transfer(&hdr->burner, &hdr->right);
182 		hdr->left_cnt = 0;
183 		hdr->right_cnt = 0;
184 		hdr->nxt_priority = req->priority;
185 	}
186 	if (req->priority < hdr->nxt_priority) {
187 		/*
188 		** yet another low priority task!
189 		*/
190 		PriorityInsert(&hdr->burner, req);
191 	} else {
192 		if (req->sectorOffset < hdr->cur_block) {
193 			/* this request is to the left of the current arms */
194 			ReqInsert(&hdr->left, req, rf_cvscan_LEFT);
195 			hdr->left_cnt++;
196 		} else {
197 			/* this request is to the right of the current arms */
198 			ReqInsert(&hdr->right, req, rf_cvscan_RIGHT);
199 			hdr->right_cnt++;
200 		}
201 	}
202 	DO_CHECK_STATE(hdr);
203 }
204 
205 
206 
207 void
208 rf_CvscanEnqueue(void *q_in, RF_DiskQueueData_t * elem, int priority)
209 {
210 	RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
211 	RealEnqueue(hdr, elem /* req */ );
212 }
213 
214 
215 
216 RF_DiskQueueData_t *
217 rf_CvscanDequeue(void *q_in)
218 {
219 	RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
220 	long    range, i, sum_dist_left, sum_dist_right;
221 	RF_DiskQueueData_t *ret;
222 	RF_DiskQueueData_t *tmp;
223 
224 	DO_CHECK_STATE(hdr);
225 
226 	if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
227 		return ((RF_DiskQueueData_t *) NULL);
228 
229 	range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt, hdr->right_cnt));
230 	for (i = 0, tmp = hdr->left, sum_dist_left =
231 	    ((hdr->direction == rf_cvscan_RIGHT) ? range * hdr->change_penalty : 0);
232 	    tmp != (RF_DiskQueueData_t *) NULL && i < range;
233 	    tmp = tmp->next, i++) {
234 		sum_dist_left += hdr->cur_block - tmp->sectorOffset;
235 	}
236 	for (i = 0, tmp = hdr->right, sum_dist_right =
237 	    ((hdr->direction == rf_cvscan_LEFT) ? range * hdr->change_penalty : 0);
238 	    tmp != (RF_DiskQueueData_t *) NULL && i < range;
239 	    tmp = tmp->next, i++) {
240 		sum_dist_right += tmp->sectorOffset - hdr->cur_block;
241 	}
242 
243 	if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right) {
244 		hdr->direction = rf_cvscan_LEFT;
245 		hdr->cur_block = hdr->left->sectorOffset + hdr->left->numSector;
246 		hdr->left_cnt = RF_MAX(hdr->left_cnt - 1, 0);
247 		tmp = hdr->left;
248 		ret = (ReqDequeue(&hdr->left)) /*->parent*/ ;
249 	} else {
250 		hdr->direction = rf_cvscan_RIGHT;
251 		hdr->cur_block = hdr->right->sectorOffset + hdr->right->numSector;
252 		hdr->right_cnt = RF_MAX(hdr->right_cnt - 1, 0);
253 		tmp = hdr->right;
254 		ret = (ReqDequeue(&hdr->right)) /*->parent*/ ;
255 	}
256 	ReBalance(hdr);
257 
258 	if (hdr->left_cnt == 0 && hdr->right_cnt == 0
259 	    && hdr->burner != (RF_DiskQueueData_t *) NULL) {
260 		/*
261 		** restore low priority requests for next dequeue
262 		*/
263 		RF_DiskQueueData_t *burner = hdr->burner;
264 		hdr->nxt_priority = burner->priority;
265 		while (burner != (RF_DiskQueueData_t *) NULL
266 		    && burner->priority == hdr->nxt_priority) {
267 			RF_DiskQueueData_t *next = burner->next;
268 			RealEnqueue(hdr, burner);
269 			burner = next;
270 		}
271 		hdr->burner = burner;
272 	}
273 	DO_CHECK_STATE(hdr);
274 	return (ret);
275 }
276 
277 
278 
279 RF_DiskQueueData_t *
280 rf_CvscanPeek(void *q_in)
281 {
282 	RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
283 	long    range, i, sum_dist_left, sum_dist_right;
284 	RF_DiskQueueData_t *tmp, *headElement;
285 
286 	DO_CHECK_STATE(hdr);
287 
288 	if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
289 		headElement = NULL;
290 	else {
291 		range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt, hdr->right_cnt));
292 		for (i = 0, tmp = hdr->left, sum_dist_left =
293 		    ((hdr->direction == rf_cvscan_RIGHT) ? range * hdr->change_penalty : 0);
294 		    tmp != (RF_DiskQueueData_t *) NULL && i < range;
295 		    tmp = tmp->next, i++) {
296 			sum_dist_left += hdr->cur_block - tmp->sectorOffset;
297 		}
298 		for (i = 0, tmp = hdr->right, sum_dist_right =
299 		    ((hdr->direction == rf_cvscan_LEFT) ? range * hdr->change_penalty : 0);
300 		    tmp != (RF_DiskQueueData_t *) NULL && i < range;
301 		    tmp = tmp->next, i++) {
302 			sum_dist_right += tmp->sectorOffset - hdr->cur_block;
303 		}
304 
305 		if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right)
306 			headElement = hdr->left;
307 		else
308 			headElement = hdr->right;
309 	}
310 	return (headElement);
311 }
312 
313 
314 
315 /*
316 ** CVSCAN( 1, 0 ) is Shortest Seek Time First (SSTF)
317 **				lowest average response time
318 ** CVSCAN( 1, infinity ) is SCAN
319 **				lowest response time standard deviation
320 */
321 
322 
323 int
324 rf_CvscanConfigure()
325 {
326 	return (0);
327 }
328 
329 
330 
331 void   *
332 rf_CvscanCreate(RF_SectorCount_t sectPerDisk,
333     RF_AllocListElem_t * clList,
334     RF_ShutdownList_t ** listp)
335 {
336 	RF_CvscanHeader_t *hdr;
337 	long    range = 2;	/* Currently no mechanism to change these */
338 	long    penalty = sectPerDisk / 5;
339 
340 	RF_MallocAndAdd(hdr, sizeof(RF_CvscanHeader_t), (RF_CvscanHeader_t *), clList);
341 	memset((char *) hdr, 0, sizeof(RF_CvscanHeader_t));
342 	hdr->range_for_avg = RF_MAX(range, 1);
343 	hdr->change_penalty = RF_MAX(penalty, 0);
344 	hdr->direction = rf_cvscan_RIGHT;
345 	hdr->cur_block = 0;
346 	hdr->left_cnt = hdr->right_cnt = 0;
347 	hdr->left = hdr->right = (RF_DiskQueueData_t *) NULL;
348 	hdr->burner = (RF_DiskQueueData_t *) NULL;
349 	DO_CHECK_STATE(hdr);
350 
351 	return ((void *) hdr);
352 }
353 
354 
355 #if defined(__NetBSD__) && defined(_KERNEL)
356 /* PrintCvscanQueue is not used, so we ignore it... */
357 #else
358 static void
359 PrintCvscanQueue(RF_CvscanHeader_t * hdr)
360 {
361 	RF_DiskQueueData_t *tmp;
362 
363 	printf("CVSCAN(%d,%d) at %d going %s\n",
364 	    (int) hdr->range_for_avg,
365 	    (int) hdr->change_penalty,
366 	    (int) hdr->cur_block,
367 	    (hdr->direction == rf_cvscan_LEFT) ? "LEFT" : "RIGHT");
368 	printf("\tLeft(%d): ", hdr->left_cnt);
369 	for (tmp = hdr->left; tmp != (RF_DiskQueueData_t *) NULL; tmp = tmp->next)
370 		printf("(%d,%ld,%d) ",
371 		    (int) tmp->sectorOffset,
372 		    (long) (tmp->sectorOffset + tmp->numSector),
373 		    tmp->priority);
374 	printf("\n");
375 	printf("\tRight(%d): ", hdr->right_cnt);
376 	for (tmp = hdr->right; tmp != (RF_DiskQueueData_t *) NULL; tmp = tmp->next)
377 		printf("(%d,%ld,%d) ",
378 		    (int) tmp->sectorOffset,
379 		    (long) (tmp->sectorOffset + tmp->numSector),
380 		    tmp->priority);
381 	printf("\n");
382 	printf("\tBurner: ");
383 	for (tmp = hdr->burner; tmp != (RF_DiskQueueData_t *) NULL; tmp = tmp->next)
384 		printf("(%d,%ld,%d) ",
385 		    (int) tmp->sectorOffset,
386 		    (long) (tmp->sectorOffset + tmp->numSector),
387 		    tmp->priority);
388 	printf("\n");
389 }
390 #endif
391 
392 
393 /* promotes reconstruction accesses for the given stripeID to normal priority.
394  * returns 1 if an access was found and zero otherwise.  Normally, we should
395  * only have one or zero entries in the burner queue, so execution time should
396  * be short.
397  */
398 int
399 rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID, RF_ReconUnitNum_t which_ru)
400 {
401 	RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
402 	RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL;
403 	int     retval = 0;
404 
405 	DO_CHECK_STATE(hdr);
406 	while (tmp) {		/* handle entries at the front of the list */
407 		if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) {
408 			hdr->burner = tmp->next;
409 			tmp->priority = RF_IO_NORMAL_PRIORITY;
410 			tmp->next = tlist;
411 			tlist = tmp;
412 			tmp = hdr->burner;
413 		} else
414 			break;
415 	}
416 	if (tmp) {
417 		trailer = tmp;
418 		tmp = tmp->next;
419 	}
420 	while (tmp) {		/* handle entries on the rest of the list */
421 		if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) {
422 			trailer->next = tmp->next;
423 			tmp->priority = RF_IO_NORMAL_PRIORITY;
424 			tmp->next = tlist;
425 			tlist = tmp;	/* insert on a temp queue */
426 			tmp = trailer->next;
427 		} else {
428 			trailer = tmp;
429 			tmp = tmp->next;
430 		}
431 	}
432 	while (tlist) {
433 		retval++;
434 		tmp = tlist->next;
435 		RealEnqueue(hdr, tlist);
436 		tlist = tmp;
437 	}
438 	RF_ASSERT(retval == 0 || retval == 1);
439 	DO_CHECK_STATE((RF_CvscanHeader_t *) q_in);
440 	return (retval);
441 }
442