/*      $NetBSD: rf_cvscan.c,v 1.18 2021/07/27 03:09:26 oster Exp $     */
/*
* Copyright (c) 1995 Carnegie-Mellon University.
* All rights reserved.
*
* Author: Mark Holland
*
* Permission to use, copy, modify and distribute this software and
* its documentation is hereby granted, provided that both the copyright
* notice and this permission notice appear in all copies of the
* software, derivative works or modified versions, and any portions
* thereof, and that both notices appear in supporting documentation.
*
* CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
* CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
* FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
*
* Carnegie Mellon requests users of this software to return to
*
*  Software Distribution Coordinator  or  [email protected]
*  School of Computer Science
*  Carnegie Mellon University
*  Pittsburgh PA 15213-3890
*
* any improvements or extensions that they make and grant Carnegie the
* rights to redistribute these changes.
*/

/*******************************************************************************
*
* cvscan.c --  prioritized cvscan disk queueing code.
*
* Nov 9, 1994, adapted from raidSim version (MCH)
*
******************************************************************************/

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: rf_cvscan.c,v 1.18 2021/07/27 03:09:26 oster Exp $");

#include <dev/raidframe/raidframevar.h>
#include "rf_alloclist.h"
#include "rf_stripelocks.h"
#include "rf_layout.h"
#include "rf_diskqueue.h"
#include "rf_cvscan.h"
#include "rf_debugMem.h"
#include "rf_general.h"

#define DO_CHECK_STATE(_hdr_) CheckCvscanState((_hdr_))

#define pri_ok(p)  ( ((p) == RF_IO_NORMAL_PRIORITY) || ((p) == RF_IO_LOW_PRIORITY))

static void
CheckCvscanState(RF_CvscanHeader_t *hdr)
{
       long    i, key;
       RF_DiskQueueData_t *tmp;

       if (hdr->left != NULL)
               RF_ASSERT(hdr->left->sectorOffset < hdr->cur_block);
       for (key = hdr->cur_block, i = 0, tmp = hdr->left;
           tmp != NULL;
           key = tmp->sectorOffset, i++, tmp = tmp->next)
               RF_ASSERT(tmp->sectorOffset <= key
                   && tmp->priority == hdr->nxt_priority && pri_ok(tmp->priority));
       RF_ASSERT(i == hdr->left_cnt);

       for (key = hdr->cur_block, i = 0, tmp = hdr->right;
           tmp != 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));
       }
       RF_ASSERT(i == hdr->right_cnt);

       for (key = hdr->nxt_priority - 1, tmp = hdr->burner;
           tmp != 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);
       }
}



static void
PriorityInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req)
{
       /* * insert block pointed to by req in to list whose first * entry is
        * pointed to by the pointer that list_ptr points to * ie., list_ptr
        * is a grandparent of the first entry */

       for (; (*list_ptr) != NULL && (*list_ptr)->priority > req->priority;
           list_ptr = &((*list_ptr)->next)) {
       }
       req->next = (*list_ptr);
       (*list_ptr) = req;
}



static void
ReqInsert(RF_DiskQueueData_t **list_ptr, RF_DiskQueueData_t *req, RF_CvscanArmDir_t order)
{
       /* * insert block pointed to by req in to list whose first * entry is
        * pointed to by the pointer that list_ptr points to * ie., list_ptr
        * is a grandparent of the first entry */

       for (; (*list_ptr) != NULL &&
           ((order == rf_cvscan_RIGHT && (*list_ptr)->sectorOffset <= req->sectorOffset)
               || (order == rf_cvscan_LEFT && (*list_ptr)->sectorOffset > req->sectorOffset));
           list_ptr = &((*list_ptr)->next)) {
       }
       req->next = (*list_ptr);
       (*list_ptr) = req;
}



static RF_DiskQueueData_t *
ReqDequeue(RF_DiskQueueData_t **list_ptr)
{
       RF_DiskQueueData_t *ret = (*list_ptr);
       if ((*list_ptr) != NULL) {
               (*list_ptr) = (*list_ptr)->next;
       }
       return (ret);
}



static void
ReBalance(RF_CvscanHeader_t *hdr)
{
       /* DO_CHECK_STATE(hdr); */
       while (hdr->right != NULL
           && hdr->right->sectorOffset < hdr->cur_block) {
               hdr->right_cnt--;
               hdr->left_cnt++;
               ReqInsert(&hdr->left, ReqDequeue(&hdr->right), rf_cvscan_LEFT);
       }
       /* DO_CHECK_STATE(hdr); */
}



static void
Transfer(RF_DiskQueueData_t **to_list_ptr, RF_DiskQueueData_t **from_list_ptr)
{
       RF_DiskQueueData_t *gp;
       for (gp = (*from_list_ptr); gp != NULL;) {
               RF_DiskQueueData_t *p = gp->next;
               PriorityInsert(to_list_ptr, gp);
               gp = p;
       }
       (*from_list_ptr) = NULL;
}



static void
RealEnqueue(RF_CvscanHeader_t *hdr, RF_DiskQueueData_t *req)
{
       RF_ASSERT(req->priority == RF_IO_NORMAL_PRIORITY || req->priority == RF_IO_LOW_PRIORITY);

       DO_CHECK_STATE(hdr);
       if (hdr->left_cnt == 0 && hdr->right_cnt == 0) {
               hdr->nxt_priority = req->priority;
       }
       if (req->priority > hdr->nxt_priority) {
               /*
               ** dump all other outstanding requests on the back burner
               */
               Transfer(&hdr->burner, &hdr->left);
               Transfer(&hdr->burner, &hdr->right);
               hdr->left_cnt = 0;
               hdr->right_cnt = 0;
               hdr->nxt_priority = req->priority;
       }
       if (req->priority < hdr->nxt_priority) {
               /*
               ** yet another low priority task!
               */
               PriorityInsert(&hdr->burner, req);
       } else {
               if (req->sectorOffset < hdr->cur_block) {
                       /* this request is to the left of the current arms */
                       ReqInsert(&hdr->left, req, rf_cvscan_LEFT);
                       hdr->left_cnt++;
               } else {
                       /* this request is to the right of the current arms */
                       ReqInsert(&hdr->right, req, rf_cvscan_RIGHT);
                       hdr->right_cnt++;
               }
       }
       DO_CHECK_STATE(hdr);
}



void
rf_CvscanEnqueue(void *q_in, RF_DiskQueueData_t * elem, int priority)
{
       RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
       RealEnqueue(hdr, elem /* req */ );
}



RF_DiskQueueData_t *
rf_CvscanDequeue(void *q_in)
{
       RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
       long    range, i, sum_dist_left, sum_dist_right;
       RF_DiskQueueData_t *ret;
       RF_DiskQueueData_t *tmp;

       DO_CHECK_STATE(hdr);

       if (hdr->left_cnt == 0 && hdr->right_cnt == 0)
               return (NULL);

       range = RF_MIN(hdr->range_for_avg, RF_MIN(hdr->left_cnt, hdr->right_cnt));
       for (i = 0, tmp = hdr->left, sum_dist_left =
           ((hdr->direction == rf_cvscan_RIGHT) ? range * hdr->change_penalty : 0);
           tmp != NULL && i < range;
           tmp = tmp->next, i++) {
               sum_dist_left += hdr->cur_block - tmp->sectorOffset;
       }
       for (i = 0, tmp = hdr->right, sum_dist_right =
           ((hdr->direction == rf_cvscan_LEFT) ? range * hdr->change_penalty : 0);
           tmp != NULL && i < range;
           tmp = tmp->next, i++) {
               sum_dist_right += tmp->sectorOffset - hdr->cur_block;
       }

       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 = (ReqDequeue(&hdr->left)) /*->parent*/ ;
       } 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 = (ReqDequeue(&hdr->right)) /*->parent*/ ;
       }
       ReBalance(hdr);

       if (hdr->left_cnt == 0 && hdr->right_cnt == 0
           && hdr->burner != NULL) {
               /*
               ** restore low priority requests for next dequeue
               */
               RF_DiskQueueData_t *burner = hdr->burner;
               hdr->nxt_priority = burner->priority;
               while (burner != NULL
                   && burner->priority == hdr->nxt_priority) {
                       RF_DiskQueueData_t *next = burner->next;
                       RealEnqueue(hdr, burner);
                       burner = next;
               }
               hdr->burner = burner;
       }
       DO_CHECK_STATE(hdr);
       return (ret);
}

/*
** CVSCAN( 1, 0 ) is Shortest Seek Time First (SSTF)
**                              lowest average response time
** CVSCAN( 1, infinity ) is SCAN
**                              lowest response time standard deviation
*/

void   *
rf_CvscanCreate(RF_SectorCount_t sectPerDisk,
   RF_AllocListElem_t *clList,
   RF_ShutdownList_t **listp)
{
       RF_CvscanHeader_t *hdr;
       long    range = 2;      /* Currently no mechanism to change these */
       long    penalty = sectPerDisk / 5;

       hdr = RF_MallocAndAdd(sizeof(*hdr), clList);
       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 = NULL;
       hdr->burner = NULL;
       DO_CHECK_STATE(hdr);

       return ((void *) hdr);
}


#if defined(__NetBSD__) && defined(_KERNEL)
/* PrintCvscanQueue is not used, so we ignore it... */
#else
static void
PrintCvscanQueue(RF_CvscanHeader_t *hdr)
{
       RF_DiskQueueData_t *tmp;

       printf("CVSCAN(%d,%d) at %d going %s\n",
           (int) hdr->range_for_avg,
           (int) hdr->change_penalty,
           (int) hdr->cur_block,
           (hdr->direction == rf_cvscan_LEFT) ? "LEFT" : "RIGHT");
       printf("\tLeft(%d): ", hdr->left_cnt);
       for (tmp = hdr->left; tmp != NULL; tmp = tmp->next)
               printf("(%d,%ld,%d) ",
                   (int) tmp->sectorOffset,
                   (long) (tmp->sectorOffset + tmp->numSector),
                   tmp->priority);
       printf("\n");
       printf("\tRight(%d): ", hdr->right_cnt);
       for (tmp = hdr->right; tmp != NULL; tmp = tmp->next)
               printf("(%d,%ld,%d) ",
                   (int) tmp->sectorOffset,
                   (long) (tmp->sectorOffset + tmp->numSector),
                   tmp->priority);
       printf("\n");
       printf("\tBurner: ");
       for (tmp = hdr->burner; tmp != NULL; tmp = tmp->next)
               printf("(%d,%ld,%d) ",
                   (int) tmp->sectorOffset,
                   (long) (tmp->sectorOffset + tmp->numSector),
                   tmp->priority);
       printf("\n");
}
#endif


/* promotes reconstruction accesses for the given stripeID to normal priority.
* returns 1 if an access was found and zero otherwise.  Normally, we should
* only have one or zero entries in the burner queue, so execution time should
* be short.
*/
int
rf_CvscanPromote(void *q_in, RF_StripeNum_t parityStripeID,
                RF_ReconUnitNum_t which_ru)
{
       RF_CvscanHeader_t *hdr = (RF_CvscanHeader_t *) q_in;
       RF_DiskQueueData_t *trailer = NULL, *tmp = hdr->burner, *tlist = NULL;
       int     retval = 0;

       DO_CHECK_STATE(hdr);
       while (tmp) {           /* handle entries at the front of the list */
               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;
               } else
                       break;
       }
       if (tmp) {
               trailer = tmp;
               tmp = tmp->next;
       }
       while (tmp) {           /* handle entries on the rest of the list */
               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;
               } else {
                       trailer = tmp;
                       tmp = tmp->next;
               }
       }
       while (tlist) {
               retval++;
               tmp = tlist->next;
               RealEnqueue(hdr, tlist);
               tlist = tmp;
       }
       RF_ASSERT(retval == 0 || retval == 1);
       DO_CHECK_STATE((RF_CvscanHeader_t *) q_in);
       return (retval);
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.