1 /* $NetBSD: rf_cvscan.c,v 1.4 1999/02/05 00:06:07 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 "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 #include "rf_sys.h" 46 47 #define DO_CHECK_STATE(_hdr_) CheckCvscanState((_hdr_), __FILE__, __LINE__) 48 49 #define pri_ok(p) ( ((p) == RF_IO_NORMAL_PRIORITY) || ((p) == RF_IO_LOW_PRIORITY)) 50 51 static void 52 CheckCvscanState(RF_CvscanHeader_t * hdr, char *file, int line) 53 { 54 long i, key; 55 RF_DiskQueueData_t *tmp; 56 57 if (hdr->left != (RF_DiskQueueData_t *) NULL) 58 RF_ASSERT(hdr->left->sectorOffset < hdr->cur_block); 59 for (key = hdr->cur_block, i = 0, tmp = hdr->left; 60 tmp != (RF_DiskQueueData_t *) NULL; 61 key = tmp->sectorOffset, i++, tmp = tmp->next) 62 RF_ASSERT(tmp->sectorOffset <= key 63 && tmp->priority == hdr->nxt_priority && pri_ok(tmp->priority)); 64 RF_ASSERT(i == hdr->left_cnt); 65 66 for (key = hdr->cur_block, i = 0, tmp = hdr->right; 67 tmp != (RF_DiskQueueData_t *) NULL; 68 key = tmp->sectorOffset, i++, tmp = tmp->next) { 69 RF_ASSERT(key <= tmp->sectorOffset); 70 RF_ASSERT(tmp->priority == hdr->nxt_priority); 71 RF_ASSERT(pri_ok(tmp->priority)); 72 } 73 RF_ASSERT(i == hdr->right_cnt); 74 75 for (key = hdr->nxt_priority - 1, tmp = hdr->burner; 76 tmp != (RF_DiskQueueData_t *) NULL; 77 key = tmp->priority, tmp = tmp->next) { 78 RF_ASSERT(tmp); 79 RF_ASSERT(hdr); 80 RF_ASSERT(pri_ok(tmp->priority)); 81 RF_ASSERT(key >= tmp->priority); 82 RF_ASSERT(tmp->priority < hdr->nxt_priority); 83 } 84 } 85 86 87 88 static void 89 PriorityInsert(RF_DiskQueueData_t ** list_ptr, RF_DiskQueueData_t * req) 90 { 91 /* * insert block pointed to by req in to list whose first * entry is 92 * pointed to by the pointer that list_ptr points to * ie., list_ptr 93 * is a grandparent of the first entry */ 94 95 for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL && 96 (*list_ptr)->priority > req->priority; 97 list_ptr = &((*list_ptr)->next)) { 98 } 99 req->next = (*list_ptr); 100 (*list_ptr) = req; 101 } 102 103 104 105 static void 106 ReqInsert(RF_DiskQueueData_t ** list_ptr, RF_DiskQueueData_t * req, RF_CvscanArmDir_t order) 107 { 108 /* * insert block pointed to by req in to list whose first * entry is 109 * pointed to by the pointer that list_ptr points to * ie., list_ptr 110 * is a grandparent of the first entry */ 111 112 for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL && 113 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 * 125 ReqDequeue(RF_DiskQueueData_t ** list_ptr) 126 { 127 RF_DiskQueueData_t *ret = (*list_ptr); 128 if ((*list_ptr) != (RF_DiskQueueData_t *) NULL) { 129 (*list_ptr) = (*list_ptr)->next; 130 } 131 return (ret); 132 } 133 134 135 136 static void 137 ReBalance(RF_CvscanHeader_t * hdr) 138 { 139 /* DO_CHECK_STATE(hdr); */ 140 while (hdr->right != (RF_DiskQueueData_t *) 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 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 != (RF_DiskQueueData_t *) NULL;) { 156 RF_DiskQueueData_t *p = gp->next; 157 PriorityInsert(to_list_ptr, gp); 158 gp = p; 159 } 160 (*from_list_ptr) = (RF_DiskQueueData_t *) NULL; 161 } 162 163 164 165 static void 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 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 * 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 ((RF_DiskQueueData_t *) 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 != (RF_DiskQueueData_t *) 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 != (RF_DiskQueueData_t *) 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 != (RF_DiskQueueData_t *) 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 != (RF_DiskQueueData_t *) 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 277 RF_DiskQueueData_t * 278 rf_CvscanPeek(void *q_in) 279 { 280 RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in; 281 long range, i, sum_dist_left, sum_dist_right; 282 RF_DiskQueueData_t *tmp, *headElement; 283 284 DO_CHECK_STATE(hdr); 285 286 if (hdr->left_cnt == 0 && hdr->right_cnt == 0) 287 headElement = NULL; 288 else { 289 range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt, hdr->right_cnt)); 290 for (i = 0, tmp = hdr->left, sum_dist_left = 291 ((hdr->direction == rf_cvscan_RIGHT) ? range * hdr->change_penalty : 0); 292 tmp != (RF_DiskQueueData_t *) NULL && i < range; 293 tmp = tmp->next, i++) { 294 sum_dist_left += hdr->cur_block - tmp->sectorOffset; 295 } 296 for (i = 0, tmp = hdr->right, sum_dist_right = 297 ((hdr->direction == rf_cvscan_LEFT) ? range * hdr->change_penalty : 0); 298 tmp != (RF_DiskQueueData_t *) NULL && i < range; 299 tmp = tmp->next, i++) { 300 sum_dist_right += tmp->sectorOffset - hdr->cur_block; 301 } 302 303 if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right) 304 headElement = hdr->left; 305 else 306 headElement = hdr->right; 307 } 308 return (headElement); 309 } 310 311 312 313 /* 314 ** CVSCAN( 1, 0 ) is Shortest Seek Time First (SSTF) 315 ** lowest average response time 316 ** CVSCAN( 1, infinity ) is SCAN 317 ** lowest response time standard deviation 318 */ 319 320 321 int 322 rf_CvscanConfigure() 323 { 324 return (0); 325 } 326 327 328 329 void * 330 rf_CvscanCreate(RF_SectorCount_t sectPerDisk, 331 RF_AllocListElem_t * clList, 332 RF_ShutdownList_t ** listp) 333 { 334 RF_CvscanHeader_t *hdr; 335 long range = 2; /* Currently no mechanism to change these */ 336 long penalty = sectPerDisk / 5; 337 338 RF_MallocAndAdd(hdr, sizeof(RF_CvscanHeader_t), (RF_CvscanHeader_t *), clList); 339 bzero((char *) hdr, sizeof(RF_CvscanHeader_t)); 340 hdr->range_for_avg = RF_MAX(range, 1); 341 hdr->change_penalty = RF_MAX(penalty, 0); 342 hdr->direction = rf_cvscan_RIGHT; 343 hdr->cur_block = 0; 344 hdr->left_cnt = hdr->right_cnt = 0; 345 hdr->left = hdr->right = (RF_DiskQueueData_t *) NULL; 346 hdr->burner = (RF_DiskQueueData_t *) NULL; 347 DO_CHECK_STATE(hdr); 348 349 return ((void *) hdr); 350 } 351 352 353 #if defined(__NetBSD__) && defined(_KERNEL) 354 /* PrintCvscanQueue is not used, so we ignore it... */ 355 #else 356 static void 357 PrintCvscanQueue(RF_CvscanHeader_t * hdr) 358 { 359 RF_DiskQueueData_t *tmp; 360 361 printf("CVSCAN(%d,%d) at %d going %s\n", 362 (int) hdr->range_for_avg, 363 (int) hdr->change_penalty, 364 (int) hdr->cur_block, 365 (hdr->direction == rf_cvscan_LEFT) ? "LEFT" : "RIGHT"); 366 printf("\tLeft(%d): ", hdr->left_cnt); 367 for (tmp = hdr->left; 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("\tRight(%d): ", hdr->right_cnt); 374 for (tmp = hdr->right; 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 printf("\tBurner: "); 381 for (tmp = hdr->burner; tmp != (RF_DiskQueueData_t *) NULL; tmp = tmp->next) 382 printf("(%d,%ld,%d) ", 383 (int) tmp->sectorOffset, 384 (long) (tmp->sectorOffset + tmp->numSector), 385 tmp->priority); 386 printf("\n"); 387 } 388 #endif 389 390 391 /* promotes reconstruction accesses for the given stripeID to normal priority. 392 * returns 1 if an access was found and zero otherwise. Normally, we should 393 * only have one or zero entries in the burner queue, so execution time should 394 * be short. 395 */ 396 int 397 rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID, RF_ReconUnitNum_t which_ru) 398 { 399 RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in; 400 RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL; 401 int retval = 0; 402 403 DO_CHECK_STATE(hdr); 404 while (tmp) { /* handle entries at the front of the list */ 405 if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) { 406 hdr->burner = tmp->next; 407 tmp->priority = RF_IO_NORMAL_PRIORITY; 408 tmp->next = tlist; 409 tlist = tmp; 410 tmp = hdr->burner; 411 } else 412 break; 413 } 414 if (tmp) { 415 trailer = tmp; 416 tmp = tmp->next; 417 } 418 while (tmp) { /* handle entries on the rest of the list */ 419 if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) { 420 trailer->next = tmp->next; 421 tmp->priority = RF_IO_NORMAL_PRIORITY; 422 tmp->next = tlist; 423 tlist = tmp; /* insert on a temp queue */ 424 tmp = trailer->next; 425 } else { 426 trailer = tmp; 427 tmp = tmp->next; 428 } 429 } 430 while (tlist) { 431 retval++; 432 tmp = tlist->next; 433 RealEnqueue(hdr, tlist); 434 tlist = tmp; 435 } 436 RF_ASSERT(retval == 0 || retval == 1); 437 DO_CHECK_STATE((RF_CvscanHeader_t *) q_in); 438 return (retval); 439 } 440