sys/dev/raidframe/rf_cvscan.c

   1 /*      $NetBSD: rf_cvscan.c,v 1.14 2006/10/12 01:31:50 christos 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.14 2006/10/12 01:31:50 christos 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 }