Annotation of sys/dev/raidframe/rf_cvscan.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: rf_cvscan.c,v 1.5 2002/12/16 07:01:03 tdeval Exp $ */
! 2: /* $NetBSD: rf_cvscan.c,v 1.5 1999/08/13 03:41:53 oster Exp $ */
! 3:
! 4: /*
! 5: * Copyright (c) 1995 Carnegie-Mellon University.
! 6: * All rights reserved.
! 7: *
! 8: * Author: Mark Holland
! 9: *
! 10: * Permission to use, copy, modify and distribute this software and
! 11: * its documentation is hereby granted, provided that both the copyright
! 12: * notice and this permission notice appear in all copies of the
! 13: * software, derivative works or modified versions, and any portions
! 14: * thereof, and that both notices appear in supporting documentation.
! 15: *
! 16: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
! 17: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
! 18: * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
! 19: *
! 20: * Carnegie Mellon requests users of this software to return to
! 21: *
! 22: * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
! 23: * School of Computer Science
! 24: * Carnegie Mellon University
! 25: * Pittsburgh PA 15213-3890
! 26: *
! 27: * any improvements or extensions that they make and grant Carnegie the
! 28: * rights to redistribute these changes.
! 29: */
! 30:
! 31: /*****************************************************************************
! 32: *
! 33: * cvscan.c -- prioritized cvscan disk queueing code.
! 34: *
! 35: * Nov 9, 1994, adapted from raidSim version (MCH)
! 36: *
! 37: *****************************************************************************/
! 38:
! 39: #include "rf_types.h"
! 40: #include "rf_alloclist.h"
! 41: #include "rf_stripelocks.h"
! 42: #include "rf_layout.h"
! 43: #include "rf_diskqueue.h"
! 44: #include "rf_cvscan.h"
! 45: #include "rf_debugMem.h"
! 46: #include "rf_general.h"
! 47:
! 48: void rf_CheckCvscanState(RF_CvscanHeader_t *, char *, int);
! 49: void rf_PriorityInsert(RF_DiskQueueData_t **, RF_DiskQueueData_t *);
! 50: void rf_ReqInsert(RF_DiskQueueData_t **, RF_DiskQueueData_t *,
! 51: RF_CvscanArmDir_t);
! 52: RF_DiskQueueData_t *rf_ReqDequeue(RF_DiskQueueData_t **);
! 53: void rf_ReBalance(RF_CvscanHeader_t *);
! 54: void rf_Transfer(RF_DiskQueueData_t **, RF_DiskQueueData_t **);
! 55: void rf_RealEnqueue(RF_CvscanHeader_t *, RF_DiskQueueData_t *);
! 56:
! 57: #define DO_CHECK_STATE(_hdr_) rf_CheckCvscanState((_hdr_), __FILE__, __LINE__)
! 58:
! 59: #define pri_ok(p) (((p) == RF_IO_NORMAL_PRIORITY) || \
! 60: ((p) == RF_IO_LOW_PRIORITY))
! 61:
! 62:
! 63: void
! 64: rf_CheckCvscanState(RF_CvscanHeader_t *hdr, char *file, int line)
! 65: {
! 66: long i, key;
! 67: RF_DiskQueueData_t *tmp;
! 68:
! 69: if (hdr->left != (RF_DiskQueueData_t *) NULL)
! 70: RF_ASSERT(hdr->left->sectorOffset < hdr->cur_block);
! 71: for (key = hdr->cur_block, i = 0, tmp = hdr->left;
! 72: tmp != (RF_DiskQueueData_t *) NULL;
! 73: key = tmp->sectorOffset, i++, tmp = tmp->next)
! 74: RF_ASSERT(tmp->sectorOffset <= key
! 75: && tmp->priority == hdr->nxt_priority &&
! 76: pri_ok(tmp->priority));
! 77: RF_ASSERT(i == hdr->left_cnt);
! 78:
! 79: for (key = hdr->cur_block, i = 0, tmp = hdr->right;
! 80: tmp != (RF_DiskQueueData_t *) NULL;
! 81: key = tmp->sectorOffset, i++, tmp = tmp->next) {
! 82: RF_ASSERT(key <= tmp->sectorOffset);
! 83: RF_ASSERT(tmp->priority == hdr->nxt_priority);
! 84: RF_ASSERT(pri_ok(tmp->priority));
! 85: }
! 86: RF_ASSERT(i == hdr->right_cnt);
! 87:
! 88: for (key = hdr->nxt_priority - 1, tmp = hdr->burner;
! 89: tmp != (RF_DiskQueueData_t *) NULL;
! 90: key = tmp->priority, tmp = tmp->next) {
! 91: RF_ASSERT(tmp);
! 92: RF_ASSERT(hdr);
! 93: RF_ASSERT(pri_ok(tmp->priority));
! 94: RF_ASSERT(key >= tmp->priority);
! 95: RF_ASSERT(tmp->priority < hdr->nxt_priority);
! 96: }
! 97: }
! 98:
! 99:
! 100: void
! 101: rf_PriorityInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req)
! 102: {
! 103: /*
! 104: * Insert block pointed to by req into list whose first entry is
! 105: * pointed to by the pointer that list_ptr points to.
! 106: * i.e. list_ptr is a grandparent of the first entry.
! 107: */
! 108:
! 109: for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
! 110: (*list_ptr)->priority > req->priority;
! 111: list_ptr = &((*list_ptr)->next)) {
! 112: }
! 113: req->next = (*list_ptr);
! 114: (*list_ptr) = req;
! 115: }
! 116:
! 117:
! 118: void
! 119: rf_ReqInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req,
! 120: RF_CvscanArmDir_t order)
! 121: {
! 122: /*
! 123: * Insert block pointed to by req into list whose first entry is
! 124: * pointed to by the pointer that list_ptr points to.
! 125: * i.e. list_ptr is a grandparent of the first entry.
! 126: */
! 127:
! 128: for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
! 129: ((order == rf_cvscan_RIGHT && (*list_ptr)->sectorOffset <=
! 130: req->sectorOffset) || (order == rf_cvscan_LEFT &&
! 131: (*list_ptr)->sectorOffset > req->sectorOffset));
! 132: list_ptr = &((*list_ptr)->next)) {
! 133: }
! 134: req->next = (*list_ptr);
! 135: (*list_ptr) = req;
! 136: }
! 137:
! 138:
! 139: RF_DiskQueueData_t *
! 140: rf_ReqDequeue(RF_DiskQueueData_t **list_ptr)
! 141: {
! 142: RF_DiskQueueData_t *ret = (*list_ptr);
! 143: if ((*list_ptr) != (RF_DiskQueueData_t *) NULL) {
! 144: (*list_ptr) = (*list_ptr)->next;
! 145: }
! 146: return (ret);
! 147: }
! 148:
! 149:
! 150: void
! 151: rf_ReBalance(RF_CvscanHeader_t *hdr)
! 152: {
! 153: /* DO_CHECK_STATE(hdr); */
! 154: while (hdr->right != (RF_DiskQueueData_t *) NULL
! 155: && hdr->right->sectorOffset < hdr->cur_block) {
! 156: hdr->right_cnt--;
! 157: hdr->left_cnt++;
! 158: rf_ReqInsert(&hdr->left, rf_ReqDequeue(&hdr->right),
! 159: rf_cvscan_LEFT);
! 160: }
! 161: /* DO_CHECK_STATE(hdr); */
! 162: }
! 163:
! 164:
! 165: void
! 166: rf_Transfer(RF_DiskQueueData_t **to_list_ptr, RF_DiskQueueData_t **from_list_ptr)
! 167: {
! 168: RF_DiskQueueData_t *gp;
! 169: for (gp = (*from_list_ptr); gp != (RF_DiskQueueData_t *) NULL;) {
! 170: RF_DiskQueueData_t *p = gp->next;
! 171: rf_PriorityInsert(to_list_ptr, gp);
! 172: gp = p;
! 173: }
! 174: (*from_list_ptr) = (RF_DiskQueueData_t *) NULL;
! 175: }
! 176:
! 177:
! 178: void
! 179: rf_RealEnqueue(RF_CvscanHeader_t *hdr, RF_DiskQueueData_t *req)
! 180: {
! 181: RF_ASSERT(req->priority == RF_IO_NORMAL_PRIORITY ||
! 182: req->priority == RF_IO_LOW_PRIORITY);
! 183:
! 184: DO_CHECK_STATE(hdr);
! 185: if (hdr->left_cnt == 0 && hdr->right_cnt == 0) {
! 186: hdr->nxt_priority = req->priority;
! 187: }
! 188: if (req->priority > hdr->nxt_priority) {
! 189: /*
! 190: * Dump all other outstanding requests on the back burner.
! 191: */
! 192: rf_Transfer(&hdr->burner, &hdr->left);
! 193: rf_Transfer(&hdr->burner, &hdr->right);
! 194: hdr->left_cnt = 0;
! 195: hdr->right_cnt = 0;
! 196: hdr->nxt_priority = req->priority;
! 197: }
! 198: if (req->priority < hdr->nxt_priority) {
! 199: /*
! 200: * Yet another low priority task !
! 201: */
! 202: rf_PriorityInsert(&hdr->burner, req);
! 203: } else {
! 204: if (req->sectorOffset < hdr->cur_block) {
! 205: /* This request is to the left of the current arms. */
! 206: rf_ReqInsert(&hdr->left, req, rf_cvscan_LEFT);
! 207: hdr->left_cnt++;
! 208: } else {
! 209: /* This request is to the right of the current arms. */
! 210: rf_ReqInsert(&hdr->right, req, rf_cvscan_RIGHT);
! 211: hdr->right_cnt++;
! 212: }
! 213: }
! 214: DO_CHECK_STATE(hdr);
! 215: }
! 216:
! 217:
! 218: void
! 219: rf_CvscanEnqueue(void *q_in, RF_DiskQueueData_t *elem, int priority)
! 220: {
! 221: RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
! 222: rf_RealEnqueue(hdr, elem /* req */ );
! 223: }
! 224:
! 225:
! 226: RF_DiskQueueData_t *
! 227: rf_CvscanDequeue(void *q_in)
! 228: {
! 229: RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
! 230: long range, i, sum_dist_left, sum_dist_right;
! 231: RF_DiskQueueData_t *ret;
! 232: RF_DiskQueueData_t *tmp;
! 233:
! 234: DO_CHECK_STATE(hdr);
! 235:
! 236: if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
! 237: return ((RF_DiskQueueData_t *) NULL);
! 238:
! 239: range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt,
! 240: hdr->right_cnt));
! 241: for (i = 0, tmp = hdr->left, sum_dist_left =
! 242: ((hdr->direction == rf_cvscan_RIGHT) ?
! 243: range * hdr->change_penalty : 0);
! 244: tmp != (RF_DiskQueueData_t *) NULL && i < range;
! 245: tmp = tmp->next, i++) {
! 246: sum_dist_left += hdr->cur_block - tmp->sectorOffset;
! 247: }
! 248: for (i = 0, tmp = hdr->right, sum_dist_right =
! 249: ((hdr->direction == rf_cvscan_LEFT) ?
! 250: range * hdr->change_penalty : 0);
! 251: tmp != (RF_DiskQueueData_t *) NULL && i < range;
! 252: tmp = tmp->next, i++) {
! 253: sum_dist_right += tmp->sectorOffset - hdr->cur_block;
! 254: }
! 255:
! 256: if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right) {
! 257: hdr->direction = rf_cvscan_LEFT;
! 258: hdr->cur_block = hdr->left->sectorOffset + hdr->left->numSector;
! 259: hdr->left_cnt = RF_MAX(hdr->left_cnt - 1, 0);
! 260: tmp = hdr->left;
! 261: ret = (rf_ReqDequeue(&hdr->left)) /*->parent*/ ;
! 262: } else {
! 263: hdr->direction = rf_cvscan_RIGHT;
! 264: hdr->cur_block = hdr->right->sectorOffset +
! 265: hdr->right->numSector;
! 266: hdr->right_cnt = RF_MAX(hdr->right_cnt - 1, 0);
! 267: tmp = hdr->right;
! 268: ret = (rf_ReqDequeue(&hdr->right)) /*->parent*/ ;
! 269: }
! 270: rf_ReBalance(hdr);
! 271:
! 272: if (hdr->left_cnt == 0 && hdr->right_cnt == 0
! 273: && hdr->burner != (RF_DiskQueueData_t *) NULL) {
! 274: /*
! 275: * Restore low priority requests for next dequeue.
! 276: */
! 277: RF_DiskQueueData_t *burner = hdr->burner;
! 278: hdr->nxt_priority = burner->priority;
! 279: while (burner != (RF_DiskQueueData_t *) NULL &&
! 280: burner->priority == hdr->nxt_priority) {
! 281: RF_DiskQueueData_t *next = burner->next;
! 282: rf_RealEnqueue(hdr, burner);
! 283: burner = next;
! 284: }
! 285: hdr->burner = burner;
! 286: }
! 287: DO_CHECK_STATE(hdr);
! 288: return (ret);
! 289: }
! 290:
! 291:
! 292: RF_DiskQueueData_t *
! 293: rf_CvscanPeek(void *q_in)
! 294: {
! 295: RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
! 296: long range, i, sum_dist_left, sum_dist_right;
! 297: RF_DiskQueueData_t *tmp, *headElement;
! 298:
! 299: DO_CHECK_STATE(hdr);
! 300:
! 301: if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
! 302: headElement = NULL;
! 303: else {
! 304: range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt,
! 305: hdr->right_cnt));
! 306: for (i = 0, tmp = hdr->left, sum_dist_left =
! 307: ((hdr->direction == rf_cvscan_RIGHT) ?
! 308: range * hdr->change_penalty : 0);
! 309: tmp != (RF_DiskQueueData_t *) NULL && i < range;
! 310: tmp = tmp->next, i++) {
! 311: sum_dist_left += hdr->cur_block - tmp->sectorOffset;
! 312: }
! 313: for (i = 0, tmp = hdr->right, sum_dist_right =
! 314: ((hdr->direction == rf_cvscan_LEFT) ?
! 315: range * hdr->change_penalty : 0);
! 316: tmp != (RF_DiskQueueData_t *) NULL && i < range;
! 317: tmp = tmp->next, i++) {
! 318: sum_dist_right += tmp->sectorOffset - hdr->cur_block;
! 319: }
! 320:
! 321: if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right)
! 322: headElement = hdr->left;
! 323: else
! 324: headElement = hdr->right;
! 325: }
! 326: return (headElement);
! 327: }
! 328:
! 329:
! 330: /*
! 331: * CVSCAN( 1, 0 ) is Shortest Seek Time First (SSTF)
! 332: * lowest average response time
! 333: * CVSCAN( 1, infinity ) is SCAN
! 334: * lowest response time standard deviation
! 335: */
! 336:
! 337:
! 338: int
! 339: rf_CvscanConfigure(void)
! 340: {
! 341: return (0);
! 342: }
! 343:
! 344:
! 345: void *
! 346: rf_CvscanCreate(RF_SectorCount_t sectPerDisk, RF_AllocListElem_t *clList,
! 347: RF_ShutdownList_t **listp)
! 348: {
! 349: RF_CvscanHeader_t *hdr;
! 350: long range = 2; /* Currently no mechanism to change these. */
! 351: long penalty = sectPerDisk / 5;
! 352:
! 353: RF_MallocAndAdd(hdr, sizeof(RF_CvscanHeader_t), (RF_CvscanHeader_t *),
! 354: clList);
! 355: bzero((char *) hdr, sizeof(RF_CvscanHeader_t));
! 356: hdr->range_for_avg = RF_MAX(range, 1);
! 357: hdr->change_penalty = RF_MAX(penalty, 0);
! 358: hdr->direction = rf_cvscan_RIGHT;
! 359: hdr->cur_block = 0;
! 360: hdr->left_cnt = hdr->right_cnt = 0;
! 361: hdr->left = hdr->right = (RF_DiskQueueData_t *) NULL;
! 362: hdr->burner = (RF_DiskQueueData_t *) NULL;
! 363: DO_CHECK_STATE(hdr);
! 364:
! 365: return ((void *) hdr);
! 366: }
! 367:
! 368:
! 369: #if (defined(__NetBSD__) || defined(__OpenBSD__)) && defined(_KERNEL)
! 370: /* rf_PrintCvscanQueue is not used, so we ignore it... */
! 371: #else
! 372: void
! 373: rf_PrintCvscanQueue(RF_CvscanHeader_t *hdr)
! 374: {
! 375: RF_DiskQueueData_t *tmp;
! 376:
! 377: printf("CVSCAN(%d,%d) at %d going %s\n",
! 378: (int) hdr->range_for_avg,
! 379: (int) hdr->change_penalty,
! 380: (int) hdr->cur_block,
! 381: (hdr->direction == rf_cvscan_LEFT) ? "LEFT" : "RIGHT");
! 382: printf("\tLeft(%d): ", hdr->left_cnt);
! 383: for (tmp = hdr->left; tmp != (RF_DiskQueueData_t *) NULL;
! 384: 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;
! 392: tmp = tmp->next)
! 393: printf("(%d,%ld,%d) ",
! 394: (int) tmp->sectorOffset,
! 395: (long) (tmp->sectorOffset + tmp->numSector),
! 396: tmp->priority);
! 397: printf("\n");
! 398: printf("\tBurner: ");
! 399: for (tmp = hdr->burner; tmp != (RF_DiskQueueData_t *) NULL;
! 400: tmp = tmp->next)
! 401: printf("(%d,%ld,%d) ",
! 402: (int) tmp->sectorOffset,
! 403: (long) (tmp->sectorOffset + tmp->numSector),
! 404: tmp->priority);
! 405: printf("\n");
! 406: }
! 407: #endif
! 408:
! 409:
! 410: /*
! 411: * Promote reconstruction accesses for the given stripeID to normal priority.
! 412: * Return 1 if an access was found and zero otherwise.
! 413: * Normally, we should only have one or zero entries in the burner queue,
! 414: * so execution time should be short.
! 415: */
! 416: int
! 417: rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID,
! 418: RF_ReconUnitNum_t which_ru)
! 419: {
! 420: RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
! 421: RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL;
! 422: int retval = 0;
! 423:
! 424: DO_CHECK_STATE(hdr);
! 425: while (tmp) { /* Handle entries at the front of the list. */
! 426: if (tmp->parityStripeID == parityStripeID &&
! 427: tmp->which_ru == which_ru) {
! 428: hdr->burner = tmp->next;
! 429: tmp->priority = RF_IO_NORMAL_PRIORITY;
! 430: tmp->next = tlist;
! 431: tlist = tmp;
! 432: tmp = hdr->burner;
! 433: } else
! 434: break;
! 435: }
! 436: if (tmp) {
! 437: trailer = tmp;
! 438: tmp = tmp->next;
! 439: }
! 440: while (tmp) { /* Handle entries on the rest of the list. */
! 441: if (tmp->parityStripeID == parityStripeID &&
! 442: tmp->which_ru == which_ru) {
! 443: trailer->next = tmp->next;
! 444: tmp->priority = RF_IO_NORMAL_PRIORITY;
! 445: tmp->next = tlist;
! 446: tlist = tmp; /* Insert on a temp queue. */
! 447: tmp = trailer->next;
! 448: } else {
! 449: trailer = tmp;
! 450: tmp = tmp->next;
! 451: }
! 452: }
! 453: while (tlist) {
! 454: retval++;
! 455: tmp = tlist->next;
! 456: rf_RealEnqueue(hdr, tlist);
! 457: tlist = tmp;
! 458: }
! 459: RF_ASSERT(retval == 0 || retval == 1);
! 460: DO_CHECK_STATE((RF_CvscanHeader_t *) q_in);
! 461: return (retval);
! 462: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_cvscan.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe