1 /* $NetBSD: rf_cvscan.c,v 1.18 2021/07/27 03:09:26 oster 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.18 2021/07/27 03:09:26 oster 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_))
50
51 #define pri_ok(p) ( ((p) == RF_IO_NORMAL_PRIORITY) || ((p) == RF_IO_LOW_PRIORITY))
52
53 static void
CheckCvscanState(RF_CvscanHeader_t * hdr)54 CheckCvscanState(RF_CvscanHeader_t *hdr)
55 {
56 long i, key;
57 RF_DiskQueueData_t *tmp;
58
59 if (hdr->left != NULL)
60 RF_ASSERT(hdr->left->sectorOffset < hdr->cur_block);
61 for (key = hdr->cur_block, i = 0, tmp = hdr->left;
62 tmp != 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 != 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 != 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
PriorityInsert(RF_DiskQueueData_t ** list_ptr,RF_DiskQueueData_t * req)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) != NULL && (*list_ptr)->priority > req->priority;
98 list_ptr = &((*list_ptr)->next)) {
99 }
100 req->next = (*list_ptr);
101 (*list_ptr) = req;
102 }
103
104
105
106 static void
ReqInsert(RF_DiskQueueData_t ** list_ptr,RF_DiskQueueData_t * req,RF_CvscanArmDir_t order)107 ReqInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req, RF_CvscanArmDir_t order)
108 {
109 /* * insert block pointed to by req in to list whose first * entry is
110 * pointed to by the pointer that list_ptr points to * ie., list_ptr
111 * is a grandparent of the first entry */
112
113 for (; (*list_ptr) != NULL &&
114 ((order == rf_cvscan_RIGHT && (*list_ptr)->sectorOffset <= req->sectorOffset)
115 || (order == rf_cvscan_LEFT && (*list_ptr)->sectorOffset > req->sectorOffset));
116 list_ptr = &((*list_ptr)->next)) {
117 }
118 req->next = (*list_ptr);
119 (*list_ptr) = req;
120 }
121
122
123
124 static RF_DiskQueueData_t *
ReqDequeue(RF_DiskQueueData_t ** list_ptr)125 ReqDequeue(RF_DiskQueueData_t **list_ptr)
126 {
127 RF_DiskQueueData_t *ret = (*list_ptr);
128 if ((*list_ptr) != NULL) {
129 (*list_ptr) = (*list_ptr)->next;
130 }
131 return (ret);
132 }
133
134
135
136 static void
ReBalance(RF_CvscanHeader_t * hdr)137 ReBalance(RF_CvscanHeader_t *hdr)
138 {
139 /* DO_CHECK_STATE(hdr); */
140 while (hdr->right != NULL
141 && hdr->right->sectorOffset < hdr->cur_block) {
142 hdr->right_cnt--;
143 hdr->left_cnt++;
144 ReqInsert(&hdr->left, ReqDequeue(&hdr->right), rf_cvscan_LEFT);
145 }
146 /* DO_CHECK_STATE(hdr); */
147 }
148
149
150
151 static void
Transfer(RF_DiskQueueData_t ** to_list_ptr,RF_DiskQueueData_t ** from_list_ptr)152 Transfer(RF_DiskQueueData_t **to_list_ptr, RF_DiskQueueData_t **from_list_ptr)
153 {
154 RF_DiskQueueData_t *gp;
155 for (gp = (*from_list_ptr); gp != NULL;) {
156 RF_DiskQueueData_t *p = gp->next;
157 PriorityInsert(to_list_ptr, gp);
158 gp = p;
159 }
160 (*from_list_ptr) = NULL;
161 }
162
163
164
165 static void
RealEnqueue(RF_CvscanHeader_t * hdr,RF_DiskQueueData_t * req)166 RealEnqueue(RF_CvscanHeader_t *hdr, RF_DiskQueueData_t *req)
167 {
168 RF_ASSERT(req->priority == RF_IO_NORMAL_PRIORITY || req->priority == RF_IO_LOW_PRIORITY);
169
170 DO_CHECK_STATE(hdr);
171 if (hdr->left_cnt == 0 && hdr->right_cnt == 0) {
172 hdr->nxt_priority = req->priority;
173 }
174 if (req->priority > hdr->nxt_priority) {
175 /*
176 ** dump all other outstanding requests on the back burner
177 */
178 Transfer(&hdr->burner, &hdr->left);
179 Transfer(&hdr->burner, &hdr->right);
180 hdr->left_cnt = 0;
181 hdr->right_cnt = 0;
182 hdr->nxt_priority = req->priority;
183 }
184 if (req->priority < hdr->nxt_priority) {
185 /*
186 ** yet another low priority task!
187 */
188 PriorityInsert(&hdr->burner, req);
189 } else {
190 if (req->sectorOffset < hdr->cur_block) {
191 /* this request is to the left of the current arms */
192 ReqInsert(&hdr->left, req, rf_cvscan_LEFT);
193 hdr->left_cnt++;
194 } else {
195 /* this request is to the right of the current arms */
196 ReqInsert(&hdr->right, req, rf_cvscan_RIGHT);
197 hdr->right_cnt++;
198 }
199 }
200 DO_CHECK_STATE(hdr);
201 }
202
203
204
205 void
rf_CvscanEnqueue(void * q_in,RF_DiskQueueData_t * elem,int priority)206 rf_CvscanEnqueue(void *q_in, RF_DiskQueueData_t * elem, int priority)
207 {
208 RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
209 RealEnqueue(hdr, elem /* req */ );
210 }
211
212
213
214 RF_DiskQueueData_t *
rf_CvscanDequeue(void * q_in)215 rf_CvscanDequeue(void *q_in)
216 {
217 RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
218 long range, i, sum_dist_left, sum_dist_right;
219 RF_DiskQueueData_t *ret;
220 RF_DiskQueueData_t *tmp;
221
222 DO_CHECK_STATE(hdr);
223
224 if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
225 return (NULL);
226
227 range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt, hdr->right_cnt));
228 for (i = 0, tmp = hdr->left, sum_dist_left =
229 ((hdr->direction == rf_cvscan_RIGHT) ? range * hdr->change_penalty : 0);
230 tmp != NULL && i < range;
231 tmp = tmp->next, i++) {
232 sum_dist_left += hdr->cur_block - tmp->sectorOffset;
233 }
234 for (i = 0, tmp = hdr->right, sum_dist_right =
235 ((hdr->direction == rf_cvscan_LEFT) ? range * hdr->change_penalty : 0);
236 tmp != NULL && i < range;
237 tmp = tmp->next, i++) {
238 sum_dist_right += tmp->sectorOffset - hdr->cur_block;
239 }
240
241 if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right) {
242 hdr->direction = rf_cvscan_LEFT;
243 hdr->cur_block = hdr->left->sectorOffset + hdr->left->numSector;
244 hdr->left_cnt = RF_MAX(hdr->left_cnt - 1, 0);
245 tmp = hdr->left;
246 ret = (ReqDequeue(&hdr->left)) /*->parent*/ ;
247 } else {
248 hdr->direction = rf_cvscan_RIGHT;
249 hdr->cur_block = hdr->right->sectorOffset + hdr->right->numSector;
250 hdr->right_cnt = RF_MAX(hdr->right_cnt - 1, 0);
251 tmp = hdr->right;
252 ret = (ReqDequeue(&hdr->right)) /*->parent*/ ;
253 }
254 ReBalance(hdr);
255
256 if (hdr->left_cnt == 0 && hdr->right_cnt == 0
257 && hdr->burner != NULL) {
258 /*
259 ** restore low priority requests for next dequeue
260 */
261 RF_DiskQueueData_t *burner = hdr->burner;
262 hdr->nxt_priority = burner->priority;
263 while (burner != NULL
264 && burner->priority == hdr->nxt_priority) {
265 RF_DiskQueueData_t *next = burner->next;
266 RealEnqueue(hdr, burner);
267 burner = next;
268 }
269 hdr->burner = burner;
270 }
271 DO_CHECK_STATE(hdr);
272 return (ret);
273 }
274
275 /*
276 ** CVSCAN( 1, 0 ) is Shortest Seek Time First (SSTF)
277 ** lowest average response time
278 ** CVSCAN( 1, infinity ) is SCAN
279 ** lowest response time standard deviation
280 */
281
282 void *
rf_CvscanCreate(RF_SectorCount_t sectPerDisk,RF_AllocListElem_t * clList,RF_ShutdownList_t ** listp)283 rf_CvscanCreate(RF_SectorCount_t sectPerDisk,
284 RF_AllocListElem_t *clList,
285 RF_ShutdownList_t **listp)
286 {
287 RF_CvscanHeader_t *hdr;
288 long range = 2; /* Currently no mechanism to change these */
289 long penalty = sectPerDisk / 5;
290
291 hdr = RF_MallocAndAdd(sizeof(*hdr), clList);
292 hdr->range_for_avg = RF_MAX(range, 1);
293 hdr->change_penalty = RF_MAX(penalty, 0);
294 hdr->direction = rf_cvscan_RIGHT;
295 hdr->cur_block = 0;
296 hdr->left_cnt = hdr->right_cnt = 0;
297 hdr->left = hdr->right = NULL;
298 hdr->burner = NULL;
299 DO_CHECK_STATE(hdr);
300
301 return ((void *) hdr);
302 }
303
304
305 #if defined(__NetBSD__) && defined(_KERNEL)
306 /* PrintCvscanQueue is not used, so we ignore it... */
307 #else
308 static void
PrintCvscanQueue(RF_CvscanHeader_t * hdr)309 PrintCvscanQueue(RF_CvscanHeader_t *hdr)
310 {
311 RF_DiskQueueData_t *tmp;
312
313 printf("CVSCAN(%d,%d) at %d going %s\n",
314 (int) hdr->range_for_avg,
315 (int) hdr->change_penalty,
316 (int) hdr->cur_block,
317 (hdr->direction == rf_cvscan_LEFT) ? "LEFT" : "RIGHT");
318 printf("\tLeft(%d): ", hdr->left_cnt);
319 for (tmp = hdr->left; tmp != NULL; tmp = tmp->next)
320 printf("(%d,%ld,%d) ",
321 (int) tmp->sectorOffset,
322 (long) (tmp->sectorOffset + tmp->numSector),
323 tmp->priority);
324 printf("\n");
325 printf("\tRight(%d): ", hdr->right_cnt);
326 for (tmp = hdr->right; tmp != NULL; tmp = tmp->next)
327 printf("(%d,%ld,%d) ",
328 (int) tmp->sectorOffset,
329 (long) (tmp->sectorOffset + tmp->numSector),
330 tmp->priority);
331 printf("\n");
332 printf("\tBurner: ");
333 for (tmp = hdr->burner; tmp != NULL; tmp = tmp->next)
334 printf("(%d,%ld,%d) ",
335 (int) tmp->sectorOffset,
336 (long) (tmp->sectorOffset + tmp->numSector),
337 tmp->priority);
338 printf("\n");
339 }
340 #endif
341
342
343 /* promotes reconstruction accesses for the given stripeID to normal priority.
344 * returns 1 if an access was found and zero otherwise. Normally, we should
345 * only have one or zero entries in the burner queue, so execution time should
346 * be short.
347 */
348 int
rf_CvscanPromote(void * q_in,RF_StripeNum_t parityStripeID,RF_ReconUnitNum_t which_ru)349 rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID,
350 RF_ReconUnitNum_t which_ru)
351 {
352 RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
353 RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL;
354 int retval = 0;
355
356 DO_CHECK_STATE(hdr);
357 while (tmp) { /* handle entries at the front of the list */
358 if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) {
359 hdr->burner = tmp->next;
360 tmp->priority = RF_IO_NORMAL_PRIORITY;
361 tmp->next = tlist;
362 tlist = tmp;
363 tmp = hdr->burner;
364 } else
365 break;
366 }
367 if (tmp) {
368 trailer = tmp;
369 tmp = tmp->next;
370 }
371 while (tmp) { /* handle entries on the rest of the list */
372 if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) {
373 trailer->next = tmp->next;
374 tmp->priority = RF_IO_NORMAL_PRIORITY;
375 tmp->next = tlist;
376 tlist = tmp; /* insert on a temp queue */
377 tmp = trailer->next;
378 } else {
379 trailer = tmp;
380 tmp = tmp->next;
381 }
382 }
383 while (tlist) {
384 retval++;
385 tmp = tlist->next;
386 RealEnqueue(hdr, tlist);
387 tlist = tmp;
388 }
389 RF_ASSERT(retval == 0 || retval == 1);
390 DO_CHECK_STATE((RF_CvscanHeader_t *) q_in);
391 return (retval);
392 }
393