rf_cvscan.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*      $NetBSD: rf_cvscan.c,v 1.11 2003/12/30 21:59:03 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 <sys/cdefs.h>
   38 __KERNEL_RCSID(0, "$NetBSD: rf_cvscan.c,v 1.11 2003/12/30 21:59:03 oster Exp $");
   39 
   40 #include <dev/raidframe/raidframevar.h>
   41 #include "rf_alloclist.h"
   42 #include "rf_stripelocks.h"
   43 #include "rf_layout.h"
   44 #include "rf_diskqueue.h"
   45 #include "rf_cvscan.h"
   46 #include "rf_debugMem.h"
   47 #include "rf_general.h"
   48 
   49 #define DO_CHECK_STATE(_hdr_) CheckCvscanState((_hdr_))
   50 
   51 #define pri_ok(p)  ( ((p) == RF_IO_NORMAL_PRIORITY) || ((p) == RF_IO_LOW_PRIORITY))
   52 
   53 static void 
   54 CheckCvscanState(RF_CvscanHeader_t *hdr)
   55 {
   56         long    i, key;
   57         RF_DiskQueueData_t *tmp;
   58 
   59         if (hdr->left != (RF_DiskQueueData_t *) NULL)
   60                 RF_ASSERT(hdr->left->sectorOffset < hdr->cur_block);
   61         for (key = hdr->cur_block, i = 0, tmp = hdr->left;
   62             tmp != (RF_DiskQueueData_t *) NULL;
   63             key = tmp->sectorOffset, i++, tmp = tmp->next)
   64                 RF_ASSERT(tmp->sectorOffset <= key
   65                     && tmp->priority == hdr->nxt_priority && pri_ok(tmp->priority));
   66         RF_ASSERT(i == hdr->left_cnt);
   67 
   68         for (key = hdr->cur_block, i = 0, tmp = hdr->right;
   69             tmp != (RF_DiskQueueData_t *) NULL;
   70             key = tmp->sectorOffset, i++, tmp = tmp->next) {
   71                 RF_ASSERT(key <= tmp->sectorOffset);
   72                 RF_ASSERT(tmp->priority == hdr->nxt_priority);
   73                 RF_ASSERT(pri_ok(tmp->priority));
   74         }
   75         RF_ASSERT(i == hdr->right_cnt);
   76 
   77         for (key = hdr->nxt_priority - 1, tmp = hdr->burner;
   78             tmp != (RF_DiskQueueData_t *) NULL;
   79             key = tmp->priority, tmp = tmp->next) {
   80                 RF_ASSERT(tmp);
   81                 RF_ASSERT(hdr);
   82                 RF_ASSERT(pri_ok(tmp->priority));
   83                 RF_ASSERT(key >= tmp->priority);
   84                 RF_ASSERT(tmp->priority < hdr->nxt_priority);
   85         }
   86 }
   87 
   88 
   89 
   90 static void 
   91 PriorityInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req)
   92 {
   93         /* * insert block pointed to by req in to list whose first * entry is
   94          * pointed to by the pointer that list_ptr points to * ie., list_ptr
   95          * is a grandparent of the first entry */
   96 
   97         for (; (*list_ptr) != (RF_DiskQueueData_t *) NULL &&
   98             (*list_ptr)->priority > req->priority;
   99             list_ptr = &((*list_ptr)->next)) {
  100         }
  101         req->next = (*list_ptr);
  102         (*list_ptr) = req;
  103 }
  104 
  105 
  106 
  107 static void 
  108 ReqInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req, RF_CvscanArmDir_t order)
  109 {
  110         /* * insert block pointed to by req in to list whose first * entry is
  111          * pointed to by the pointer that list_ptr points to * ie., list_ptr
  112          * is a grandparent of the first entry */
  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         }
  120         req->next = (*list_ptr);
  121         (*list_ptr) = req;
  122 }
  123 
  124 
  125 
  126 static RF_DiskQueueData_t *
  127 ReqDequeue(RF_DiskQueueData_t **list_ptr)
  128 {
  129         RF_DiskQueueData_t *ret = (*list_ptr);
  130         if ((*list_ptr) != (RF_DiskQueueData_t *) NULL) {
  131                 (*list_ptr) = (*list_ptr)->next;
  132         }
  133         return (ret);
  134 }
  135 
  136 
  137 
  138 static void 
  139 ReBalance(RF_CvscanHeader_t *hdr)
  140 {
  141         /* DO_CHECK_STATE(hdr); */
  142         while (hdr->right != (RF_DiskQueueData_t *) NULL
  143             && hdr->right->sectorOffset < hdr->cur_block) {
  144                 hdr->right_cnt--;
  145                 hdr->left_cnt++;
  146                 ReqInsert(&hdr->left, ReqDequeue(&hdr->right), rf_cvscan_LEFT);
  147         }
  148         /* DO_CHECK_STATE(hdr); */
  149 }
  150 
  151 
  152 
  153 static void 
  154 Transfer(RF_DiskQueueData_t **to_list_ptr, RF_DiskQueueData_t **from_list_ptr)
  155 {
  156         RF_DiskQueueData_t *gp;
  157         for (gp = (*from_list_ptr); gp != (RF_DiskQueueData_t *) NULL;) {
  158                 RF_DiskQueueData_t *p = gp->next;
  159                 PriorityInsert(to_list_ptr, gp);
  160                 gp = p;
  161         }
  162         (*from_list_ptr) = (RF_DiskQueueData_t *) NULL;
  163 }
  164 
  165 
  166 
  167 static void 
  168 RealEnqueue(RF_CvscanHeader_t *hdr, RF_DiskQueueData_t *req)
  169 {
  170         RF_ASSERT(req->priority == RF_IO_NORMAL_PRIORITY || req->priority == RF_IO_LOW_PRIORITY);
  171 
  172         DO_CHECK_STATE(hdr);
  173         if (hdr->left_cnt == 0 && hdr->right_cnt == 0) {
  174                 hdr->nxt_priority = req->priority;
  175         }
  176         if (req->priority > hdr->nxt_priority) {
  177                 /*
  178                 ** dump all other outstanding requests on the back burner
  179                 */
  180                 Transfer(&hdr->burner, &hdr->left);
  181                 Transfer(&hdr->burner, &hdr->right);
  182                 hdr->left_cnt = 0;
  183                 hdr->right_cnt = 0;
  184                 hdr->nxt_priority = req->priority;
  185         }
  186         if (req->priority < hdr->nxt_priority) {
  187                 /*
  188                 ** yet another low priority task!
  189                 */
  190                 PriorityInsert(&hdr->burner, req);
  191         } else {
  192                 if (req->sectorOffset < hdr->cur_block) {
  193                         /* this request is to the left of the current arms */
  194                         ReqInsert(&hdr->left, req, rf_cvscan_LEFT);
  195                         hdr->left_cnt++;
  196                 } else {
  197                         /* this request is to the right of the current arms */
  198                         ReqInsert(&hdr->right, req, rf_cvscan_RIGHT);
  199                         hdr->right_cnt++;
  200                 }
  201         }
  202         DO_CHECK_STATE(hdr);
  203 }
  204 
  205 
  206 
  207 void 
  208 rf_CvscanEnqueue(void *q_in, RF_DiskQueueData_t * elem, int priority)
  209 {
  210         RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
  211         RealEnqueue(hdr, elem /* req */ );
  212 }
  213 
  214 
  215 
  216 RF_DiskQueueData_t *
  217 rf_CvscanDequeue(void *q_in)
  218 {
  219         RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
  220         long    range, i, sum_dist_left, sum_dist_right;
  221         RF_DiskQueueData_t *ret;
  222         RF_DiskQueueData_t *tmp;
  223 
  224         DO_CHECK_STATE(hdr);
  225 
  226         if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
  227                 return ((RF_DiskQueueData_t *) NULL);
  228 
  229         range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt, hdr->right_cnt));
  230         for (i = 0, tmp = hdr->left, sum_dist_left =
  231             ((hdr->direction == rf_cvscan_RIGHT) ? range * hdr->change_penalty : 0);
  232             tmp != (RF_DiskQueueData_t *) NULL && i < range;
  233             tmp = tmp->next, i++) {
  234                 sum_dist_left += hdr->cur_block - tmp->sectorOffset;
  235         }
  236         for (i = 0, tmp = hdr->right, sum_dist_right =
  237             ((hdr->direction == rf_cvscan_LEFT) ? range * hdr->change_penalty : 0);
  238             tmp != (RF_DiskQueueData_t *) NULL && i < range;
  239             tmp = tmp->next, i++) {
  240                 sum_dist_right += tmp->sectorOffset - hdr->cur_block;
  241         }
  242 
  243         if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right) {
  244                 hdr->direction = rf_cvscan_LEFT;
  245                 hdr->cur_block = hdr->left->sectorOffset + hdr->left->numSector;
  246                 hdr->left_cnt = RF_MAX(hdr->left_cnt - 1, 0);
  247                 tmp = hdr->left;
  248                 ret = (ReqDequeue(&hdr->left)) /*->parent*/ ;
  249         } else {
  250                 hdr->direction = rf_cvscan_RIGHT;
  251                 hdr->cur_block = hdr->right->sectorOffset + hdr->right->numSector;
  252                 hdr->right_cnt = RF_MAX(hdr->right_cnt - 1, 0);
  253                 tmp = hdr->right;
  254                 ret = (ReqDequeue(&hdr->right)) /*->parent*/ ;
  255         }
  256         ReBalance(hdr);
  257 
  258         if (hdr->left_cnt == 0 && hdr->right_cnt == 0
  259             && hdr->burner != (RF_DiskQueueData_t *) NULL) {
  260                 /*
  261                 ** restore low priority requests for next dequeue
  262                 */
  263                 RF_DiskQueueData_t *burner = hdr->burner;
  264                 hdr->nxt_priority = burner->priority;
  265                 while (burner != (RF_DiskQueueData_t *) NULL
  266                     && burner->priority == hdr->nxt_priority) {
  267                         RF_DiskQueueData_t *next = burner->next;
  268                         RealEnqueue(hdr, burner);
  269                         burner = next;
  270                 }
  271                 hdr->burner = burner;
  272         }
  273         DO_CHECK_STATE(hdr);
  274         return (ret);
  275 }
  276 
  277 
  278 
  279 RF_DiskQueueData_t *
  280 rf_CvscanPeek(void *q_in)
  281 {
  282         RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
  283         long    range, i, sum_dist_left, sum_dist_right;
  284         RF_DiskQueueData_t *tmp, *headElement;
  285 
  286         DO_CHECK_STATE(hdr);
  287 
  288         if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
  289                 headElement = NULL;
  290         else {
  291                 range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt, hdr->right_cnt));
  292                 for (i = 0, tmp = hdr->left, sum_dist_left =
  293                     ((hdr->direction == rf_cvscan_RIGHT) ? range * hdr->change_penalty : 0);
  294                     tmp != (RF_DiskQueueData_t *) NULL && i < range;
  295                     tmp = tmp->next, i++) {
  296                         sum_dist_left += hdr->cur_block - tmp->sectorOffset;
  297                 }
  298                 for (i = 0, tmp = hdr->right, sum_dist_right =
  299                     ((hdr->direction == rf_cvscan_LEFT) ? range * hdr->change_penalty : 0);
  300                     tmp != (RF_DiskQueueData_t *) NULL && i < range;
  301                     tmp = tmp->next, i++) {
  302                         sum_dist_right += tmp->sectorOffset - hdr->cur_block;
  303                 }
  304 
  305                 if (hdr->right_cnt == 0 || sum_dist_left < sum_dist_right)
  306                         headElement = hdr->left;
  307                 else
  308                         headElement = hdr->right;
  309         }
  310         return (headElement);
  311 }
  312 
  313 
  314 
  315 /*
  316 ** CVSCAN( 1, 0 ) is Shortest Seek Time First (SSTF)
  317 **                              lowest average response time
  318 ** CVSCAN( 1, infinity ) is SCAN
  319 **                              lowest response time standard deviation
  320 */
  321 
  322 void   *
  323 rf_CvscanCreate(RF_SectorCount_t sectPerDisk,
  324     RF_AllocListElem_t *clList,
  325     RF_ShutdownList_t **listp)
  326 {
  327         RF_CvscanHeader_t *hdr;
  328         long    range = 2;      /* Currently no mechanism to change these */
  329         long    penalty = sectPerDisk / 5;
  330 
  331         RF_MallocAndAdd(hdr, sizeof(RF_CvscanHeader_t), (RF_CvscanHeader_t *), clList);
  332         memset((char *) hdr, 0, sizeof(RF_CvscanHeader_t));
  333         hdr->range_for_avg = RF_MAX(range, 1);
  334         hdr->change_penalty = RF_MAX(penalty, 0);
  335         hdr->direction = rf_cvscan_RIGHT;
  336         hdr->cur_block = 0;
  337         hdr->left_cnt = hdr->right_cnt = 0;
  338         hdr->left = hdr->right = (RF_DiskQueueData_t *) NULL;
  339         hdr->burner = (RF_DiskQueueData_t *) NULL;
  340         DO_CHECK_STATE(hdr);
  341 
  342         return ((void *) hdr);
  343 }
  344 
  345 
  346 #if defined(__NetBSD__) && defined(_KERNEL)
  347 /* PrintCvscanQueue is not used, so we ignore it... */
  348 #else
  349 static void 
  350 PrintCvscanQueue(RF_CvscanHeader_t *hdr)
  351 {
  352         RF_DiskQueueData_t *tmp;
  353 
  354         printf("CVSCAN(%d,%d) at %d going %s\n",
  355             (int) hdr->range_for_avg,
  356             (int) hdr->change_penalty,
  357             (int) hdr->cur_block,
  358             (hdr->direction == rf_cvscan_LEFT) ? "LEFT" : "RIGHT");
  359         printf("\tLeft(%d): ", hdr->left_cnt);
  360         for (tmp = hdr->left; tmp != (RF_DiskQueueData_t *) NULL; tmp = tmp->next)
  361                 printf("(%d,%ld,%d) ",
  362                     (int) tmp->sectorOffset,
  363                     (long) (tmp->sectorOffset + tmp->numSector),
  364                     tmp->priority);
  365         printf("\n");
  366         printf("\tRight(%d): ", hdr->right_cnt);
  367         for (tmp = hdr->right; 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("\tBurner: ");
  374         for (tmp = hdr->burner; 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 }
  381 #endif
  382 
  383 
  384 /* promotes reconstruction accesses for the given stripeID to normal priority.
  385  * returns 1 if an access was found and zero otherwise.  Normally, we should
  386  * only have one or zero entries in the burner queue, so execution time should
  387  * be short.
  388  */
  389 int 
  390 rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID, 
  391                  RF_ReconUnitNum_t which_ru)
  392 {
  393         RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
  394         RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL;
  395         int     retval = 0;
  396 
  397         DO_CHECK_STATE(hdr);
  398         while (tmp) {           /* handle entries at the front of the list */
  399                 if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) {
  400                         hdr->burner = tmp->next;
  401                         tmp->priority = RF_IO_NORMAL_PRIORITY;
  402                         tmp->next = tlist;
  403                         tlist = tmp;
  404                         tmp = hdr->burner;
  405                 } else
  406                         break;
  407         }
  408         if (tmp) {
  409                 trailer = tmp;
  410                 tmp = tmp->next;
  411         }
  412         while (tmp) {           /* handle entries on the rest of the list */
  413                 if (tmp->parityStripeID == parityStripeID && tmp->which_ru == which_ru) {
  414                         trailer->next = tmp->next;
  415                         tmp->priority = RF_IO_NORMAL_PRIORITY;
  416                         tmp->next = tlist;
  417                         tlist = tmp;    /* insert on a temp queue */
  418                         tmp = trailer->next;
  419                 } else {
  420                         trailer = tmp;
  421                         tmp = tmp->next;
  422                 }
  423         }
  424         while (tlist) {
  425                 retval++;
  426                 tmp = tlist->next;
  427                 RealEnqueue(hdr, tlist);
  428                 tlist = tmp;
  429         }
  430         RF_ASSERT(retval == 0 || retval == 1);
  431         DO_CHECK_STATE((RF_CvscanHeader_t *) q_in);
  432         return (retval);
  433 }
Cache object: 441d69ec3401536bdbb864df539d9358
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/dev/raidframe/rf_cvscan.c

FreeBSD/Linux Kernel Cross Reference
sys/dev/raidframe/rf_cvscan.c
