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