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