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