root/dev/raidframe/rf_cvscan.c

DEFINITIONS

1. rf_CheckCvscanState
2. rf_PriorityInsert
3. rf_ReqInsert
4. rf_ReqDequeue
5. rf_ReBalance
6. rf_Transfer
7. rf_RealEnqueue
8. rf_CvscanEnqueue
9. rf_CvscanDequeue
10. rf_CvscanPeek
11. rf_CvscanConfigure
12. rf_CvscanCreate
13. rf_PrintCvscanQueue
14. rf_CvscanPromote

    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 $      */
    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  */
   31 /*****************************************************************************
   32  *
   33  * cvscan.c --  prioritized cvscan disk queueing code.
   34  *
   35  * Nov 9, 1994, adapted from raidSim version (MCH)
   36  *
   37  *****************************************************************************/
   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"
   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 *,
RF_CvscanArmDir_t);
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 *);
   57 #define DO_CHECK_STATE(_hdr_)   rf_CheckCvscanState((_hdr_), __FILE__, __LINE__)
   59 #define pri_ok(p)       (((p) == RF_IO_NORMAL_PRIORITY) ||              \
   60                          ((p) == RF_IO_LOW_PRIORITY))
   63 void
rf_CheckCvscanState(RF_CvscanHeader_t *hdr, char *file, int line)
   65 {
   66         long i, key;
RF_DiskQueueData_t *tmp;
   69         if (hdr->left != (RF_DiskQueueData_t *) NULL)
RF_ASSERT(hdr->left->sectorOffset < hdr->cur_block);
   71         for (key = hdr->cur_block, i = 0, tmp = hdr->left;
tmp != (RF_DiskQueueData_t *) NULL;
key = tmp->sectorOffset, i++, tmp = tmp->next)
RF_ASSERT(tmp->sectorOffset <= key
   75                     && tmp->priority == hdr->nxt_priority && 
pri_ok(tmp->priority));
RF_ASSERT(i == hdr->left_cnt);
   79         for (key = hdr->cur_block, i = 0, tmp = hdr->right;
tmp != (RF_DiskQueueData_t *) NULL;
key = tmp->sectorOffset, i++, tmp = tmp->next) {
RF_ASSERT(key <= tmp->sectorOffset);
RF_ASSERT(tmp->priority == hdr->nxt_priority);
RF_ASSERT(pri_ok(tmp->priority));
   85         }
RF_ASSERT(i == hdr->right_cnt);
   88         for (key = hdr->nxt_priority - 1, tmp = hdr->burner;
tmp != (RF_DiskQueueData_t *) NULL;
key = tmp->priority, tmp = tmp->next) {
RF_ASSERT(tmp);
RF_ASSERT(hdr);
RF_ASSERT(pri_ok(tmp->priority));
RF_ASSERT(key >= tmp->priority);
RF_ASSERT(tmp->priority < hdr->nxt_priority);
   96         }
   97 }
  100 void
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          */
  109         for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
  110                (*list_ptr)->priority > req->priority;
list_ptr = &((*list_ptr)->next)) {
  112         }
req->next = (*list_ptr);
  114         (*list_ptr) = req;
  115 }
  118 void
rf_ReqInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req,
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          */
  128         for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
  129                ((order == rf_cvscan_RIGHT && (*list_ptr)->sectorOffset <=
req->sectorOffset) || (order == rf_cvscan_LEFT &&
  131                (*list_ptr)->sectorOffset > req->sectorOffset));
list_ptr = &((*list_ptr)->next)) {
  133         }
req->next = (*list_ptr);
  135         (*list_ptr) = req;
  136 }
RF_DiskQueueData_t *
rf_ReqDequeue(RF_DiskQueueData_t **list_ptr)
  141 {
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 }
  150 void
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) {
hdr->right_cnt--;
hdr->left_cnt++;
rf_ReqInsert(&hdr->left, rf_ReqDequeue(&hdr->right),
rf_cvscan_LEFT);
  160         }
  161         /* DO_CHECK_STATE(hdr); */
  162 }
  165 void
rf_Transfer(RF_DiskQueueData_t **to_list_ptr, RF_DiskQueueData_t **from_list_ptr)
  167 {
RF_DiskQueueData_t *gp;
  169         for (gp = (*from_list_ptr); gp != (RF_DiskQueueData_t *) NULL;) {
RF_DiskQueueData_t *p = gp->next;
rf_PriorityInsert(to_list_ptr, gp);
gp = p;
  173         }
  174         (*from_list_ptr) = (RF_DiskQueueData_t *) NULL;
  175 }
  178 void
rf_RealEnqueue(RF_CvscanHeader_t *hdr, RF_DiskQueueData_t *req)
  180 {
RF_ASSERT(req->priority == RF_IO_NORMAL_PRIORITY ||
req->priority == RF_IO_LOW_PRIORITY);
DO_CHECK_STATE(hdr);
  185         if (hdr->left_cnt == 0 && hdr->right_cnt == 0) {
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                  */
rf_Transfer(&hdr->burner, &hdr->left);
rf_Transfer(&hdr->burner, &hdr->right);
hdr->left_cnt = 0;
hdr->right_cnt = 0;
hdr->nxt_priority = req->priority;
  197         }
  198         if (req->priority < hdr->nxt_priority) {
  199                 /*
  200                  * Yet another low priority task !
  201                  */
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. */
rf_ReqInsert(&hdr->left, req, rf_cvscan_LEFT);
hdr->left_cnt++;
  208                 } else {
  209                         /* This request is to the right of the current arms. */
rf_ReqInsert(&hdr->right, req, rf_cvscan_RIGHT);
hdr->right_cnt++;
  212                 }
  213         }
DO_CHECK_STATE(hdr);
  215 }
  218 void
rf_CvscanEnqueue(void *q_in, RF_DiskQueueData_t *elem, int priority)
  220 {
RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
rf_RealEnqueue(hdr, elem /* req */ );
  223 }
RF_DiskQueueData_t *
rf_CvscanDequeue(void *q_in)
  228 {
RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
  230         long    range, i, sum_dist_left, sum_dist_right;
RF_DiskQueueData_t *ret;
RF_DiskQueueData_t *tmp;
DO_CHECK_STATE(hdr);
  236         if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
  237                 return ((RF_DiskQueueData_t *) NULL);
range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt,
hdr->right_cnt));
  241         for (i = 0, tmp = hdr->left, sum_dist_left =
  242              ((hdr->direction == rf_cvscan_RIGHT) ?
range * hdr->change_penalty : 0);
tmp != (RF_DiskQueueData_t *) NULL && i < range;
tmp = tmp->next, i++) {
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) ?
range * hdr->change_penalty : 0);
tmp != (RF_DiskQueueData_t *) NULL && i < range;
tmp = tmp->next, i++) {
sum_dist_right += tmp->sectorOffset - hdr->cur_block;
  254         }
  256         if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right) {
hdr->direction = rf_cvscan_LEFT;
hdr->cur_block = hdr->left->sectorOffset + hdr->left->numSector;
hdr->left_cnt = RF_MAX(hdr->left_cnt - 1, 0);
tmp = hdr->left;
ret = (rf_ReqDequeue(&hdr->left)) /*->parent*/ ;
  262         } else {
hdr->direction = rf_cvscan_RIGHT;
hdr->cur_block = hdr->right->sectorOffset +
hdr->right->numSector;
hdr->right_cnt = RF_MAX(hdr->right_cnt - 1, 0);
tmp = hdr->right;
ret = (rf_ReqDequeue(&hdr->right)) /*->parent*/ ;
  269         }
rf_ReBalance(hdr);
  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                  */
RF_DiskQueueData_t *burner = hdr->burner;
hdr->nxt_priority = burner->priority;
  279                 while (burner != (RF_DiskQueueData_t *) NULL &&
burner->priority == hdr->nxt_priority) {
RF_DiskQueueData_t *next = burner->next;
rf_RealEnqueue(hdr, burner);
burner = next;
  284                 }
hdr->burner = burner;
  286         }
DO_CHECK_STATE(hdr);
  288         return (ret);
  289 }
RF_DiskQueueData_t *
rf_CvscanPeek(void *q_in)
  294 {
RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
  296         long    range, i, sum_dist_left, sum_dist_right;
RF_DiskQueueData_t *tmp, *headElement;
DO_CHECK_STATE(hdr);
  301         if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
headElement = NULL;
  303         else {
range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt,
hdr->right_cnt));
  306                 for (i = 0, tmp = hdr->left, sum_dist_left =
  307                      ((hdr->direction == rf_cvscan_RIGHT) ?
range * hdr->change_penalty : 0);
tmp != (RF_DiskQueueData_t *) NULL && i < range;
tmp = tmp->next, i++) {
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) ?
range * hdr->change_penalty : 0);
tmp != (RF_DiskQueueData_t *) NULL && i < range;
tmp = tmp->next, i++) {
sum_dist_right += tmp->sectorOffset - hdr->cur_block;
  319                 }
  321                 if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right)
headElement = hdr->left;
  323                 else
headElement = hdr->right;
  325         }
  326         return (headElement);
  327 }
  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  */
  338 int
rf_CvscanConfigure(void)
  340 {
  341         return (0);
  342 }
  345 void   *
rf_CvscanCreate(RF_SectorCount_t sectPerDisk, RF_AllocListElem_t *clList,
RF_ShutdownList_t **listp)
  348 {
RF_CvscanHeader_t *hdr;
  350         long range = 2;         /* Currently no mechanism to change these. */
  351         long penalty = sectPerDisk / 5;
RF_MallocAndAdd(hdr, sizeof(RF_CvscanHeader_t), (RF_CvscanHeader_t *),
clList);
bzero((char *) hdr, sizeof(RF_CvscanHeader_t));
hdr->range_for_avg = RF_MAX(range, 1);
hdr->change_penalty = RF_MAX(penalty, 0);
hdr->direction = rf_cvscan_RIGHT;
hdr->cur_block = 0;
hdr->left_cnt = hdr->right_cnt = 0;
hdr->left = hdr->right = (RF_DiskQueueData_t *) NULL;
hdr->burner = (RF_DiskQueueData_t *) NULL;
DO_CHECK_STATE(hdr);
  365         return ((void *) hdr);
  366 }
  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 {
RF_DiskQueueData_t *tmp;
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");
printf("\tLeft(%d): ", hdr->left_cnt);
  383         for (tmp = hdr->left; tmp != (RF_DiskQueueData_t *) NULL;
tmp = tmp->next)
printf("(%d,%ld,%d) ",
  386                     (int) tmp->sectorOffset,
  387                     (long) (tmp->sectorOffset + tmp->numSector),
tmp->priority);
printf("\n");
printf("\tRight(%d): ", hdr->right_cnt);
  391         for (tmp = hdr->right; tmp != (RF_DiskQueueData_t *) NULL;
tmp = tmp->next)
printf("(%d,%ld,%d) ",
  394                     (int) tmp->sectorOffset,
  395                     (long) (tmp->sectorOffset + tmp->numSector),
tmp->priority);
printf("\n");
printf("\tBurner: ");
  399         for (tmp = hdr->burner; tmp != (RF_DiskQueueData_t *) NULL;
tmp = tmp->next)
printf("(%d,%ld,%d) ",
  402                     (int) tmp->sectorOffset,
  403                     (long) (tmp->sectorOffset + tmp->numSector),
tmp->priority);
printf("\n");
  406 }
  407 #endif
  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
rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID,
RF_ReconUnitNum_t which_ru)
  419 {
RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL;
  422         int retval = 0;
DO_CHECK_STATE(hdr);
  425         while (tmp) {           /* Handle entries at the front of the list. */
  426                 if (tmp->parityStripeID == parityStripeID &&
tmp->which_ru == which_ru) {
hdr->burner = tmp->next;
tmp->priority = RF_IO_NORMAL_PRIORITY;
tmp->next = tlist;
tlist = tmp;
tmp = hdr->burner;
  433                 } else
  434                         break;
  435         }
  436         if (tmp) {
trailer = tmp;
tmp = tmp->next;
  439         }
  440         while (tmp) {           /* Handle entries on the rest of the list. */
  441                 if (tmp->parityStripeID == parityStripeID &&
tmp->which_ru == which_ru) {
trailer->next = tmp->next;
tmp->priority = RF_IO_NORMAL_PRIORITY;
tmp->next = tlist;
tlist = tmp;    /* Insert on a temp queue. */
tmp = trailer->next;
  448                 } else {
trailer = tmp;
tmp = tmp->next;
  451                 }
  452         }
  453         while (tlist) {
retval++;
tmp = tlist->next;
rf_RealEnqueue(hdr, tlist);
tlist = tmp;
  458         }
RF_ASSERT(retval == 0 || retval == 1);
DO_CHECK_STATE((RF_CvscanHeader_t *) q_in);
  461         return (retval);
  462 }