1 /* $NetBSD: rf_cvscan.c,v 1.10 2002/09/23 04:02:29 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.10 2002/09/23 04:02:29 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 54 CheckCvscanState(RF_CvscanHeader_t * hdr) 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 void * 323 rf_CvscanCreate(RF_SectorCount_t sectPerDisk, 324 RF_AllocListElem_t * clList, 325 RF_ShutdownList_t ** listp) 326 { 327 RF_CvscanHeader_t *hdr; 328 long range = 2; /* Currently no mechanism to change these */ 329 long penalty = sectPerDisk / 5; 330 331 RF_MallocAndAdd(hdr, sizeof(RF_CvscanHeader_t), (RF_CvscanHeader_t *), clList); 332 memset((char *) hdr, 0, sizeof(RF_CvscanHeader_t)); 333 hdr->range_for_avg = RF_MAX(range, 1); 334 hdr->change_penalty = RF_MAX(penalty, 0); 335 hdr->direction = rf_cvscan_RIGHT; 336 hdr->cur_block = 0; 337 hdr->left_cnt = hdr->right_cnt = 0; 338 hdr->left = hdr->right = (RF_DiskQueueData_t *) NULL; 339 hdr->burner = (RF_DiskQueueData_t *) NULL; 340 DO_CHECK_STATE(hdr); 341 342 return ((void *) hdr); 343 } 344 345 346 #if defined(__NetBSD__) && defined(_KERNEL) 347 /* PrintCvscanQueue is not used, so we ignore it... */ 348 #else 349 static void 350 PrintCvscanQueue(RF_CvscanHeader_t * hdr) 351 { 352 RF_DiskQueueData_t *tmp; 353 354 printf("CVSCAN(%d,%d) at %d going %s\n", 355 (int) hdr->range_for_avg, 356 (int) hdr->change_penalty, 357 (int) hdr->cur_block, 358 (hdr->direction == rf_cvscan_LEFT) ? "LEFT" : "RIGHT"); 359 printf("\tLeft(%d): ", hdr->left_cnt); 360 for (tmp = hdr->left; tmp != (RF_DiskQueueData_t *) NULL; tmp = tmp->next) 361 printf("(%d,%ld,%d) ", 362 (int) tmp->sectorOffset, 363 (long) (tmp->sectorOffset + tmp->numSector), 364 tmp->priority); 365 printf("\n"); 366 printf("\tRight(%d): ", hdr->right_cnt); 367 for (tmp = hdr->right; tmp != (RF_DiskQueueData_t *) NULL; tmp = tmp->next) 368 printf("(%d,%ld,%d) ", 369 (int) tmp->sectorOffset, 370 (long) (tmp->sectorOffset + tmp->numSector), 371 tmp->priority); 372 printf("\n"); 373 printf("\tBurner: "); 374 for (tmp = hdr->burner; tmp != (RF_DiskQueueData_t *) NULL; tmp = tmp->next) 375 printf("(%d,%ld,%d) ", 376 (int) tmp->sectorOffset, 377 (long) (tmp->sectorOffset + tmp->numSector), 378 tmp->priority); 379 printf("\n"); 380 } 381 #endif 382 383 384 /* promotes reconstruction accesses for the given stripeID to normal priority. 385 * returns 1 if an access was found and zero otherwise. Normally, we should 386 * only have one or zero entries in the burner queue, so execution time should 387 * be short. 388 */ 389 int 390 rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID, RF_ReconUnitNum_t which_ru) 391 { 392 RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in; 393 RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL; 394 int retval = 0; 395 396 DO_CHECK_STATE(hdr); 397 while (tmp) { /* handle entries at the front of the list */ 398 if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) { 399 hdr->burner = tmp->next; 400 tmp->priority = RF_IO_NORMAL_PRIORITY; 401 tmp->next = tlist; 402 tlist = tmp; 403 tmp = hdr->burner; 404 } else 405 break; 406 } 407 if (tmp) { 408 trailer = tmp; 409 tmp = tmp->next; 410 } 411 while (tmp) { /* handle entries on the rest of the list */ 412 if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) { 413 trailer->next = tmp->next; 414 tmp->priority = RF_IO_NORMAL_PRIORITY; 415 tmp->next = tlist; 416 tlist = tmp; /* insert on a temp queue */ 417 tmp = trailer->next; 418 } else { 419 trailer = tmp; 420 tmp = tmp->next; 421 } 422 } 423 while (tlist) { 424 retval++; 425 tmp = tlist->next; 426 RealEnqueue(hdr, tlist); 427 tlist = tmp; 428 } 429 RF_ASSERT(retval == 0 || retval == 1); 430 DO_CHECK_STATE((RF_CvscanHeader_t *) q_in); 431 return (retval); 432 } 433