rf_sstf.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_sstf.c,v 1.11 2004/03/04 01:57:54 oster Exp $       */
    2 /*
    3  * Copyright (c) 1995 Carnegie-Mellon University.
    4  * All rights reserved.
    5  *
    6  * Author: Jim Zelenka
    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  * sstf.c --  prioritized shortest seek time first disk queueing code
   32  *
   33  ******************************************************************************/
   34 
   35 #include <sys/cdefs.h>
   36 __KERNEL_RCSID(0, "$NetBSD: rf_sstf.c,v 1.11 2004/03/04 01:57:54 oster Exp $");
   37 
   38 #include <dev/raidframe/raidframevar.h>
   39 
   40 #include "rf_alloclist.h"
   41 #include "rf_stripelocks.h"
   42 #include "rf_layout.h"
   43 #include "rf_diskqueue.h"
   44 #include "rf_sstf.h"
   45 #include "rf_debugMem.h"
   46 #include "rf_general.h"
   47 #include "rf_options.h"
   48 #include "rf_raid.h"
   49 
   50 #define DIR_LEFT   1
   51 #define DIR_RIGHT  2
   52 #define DIR_EITHER 3
   53 
   54 #define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_)))
   55 
   56 #define QSUM(_sstfq_) (((_sstfq_)->lopri.qlen)+((_sstfq_)->left.qlen)+((_sstfq_)->right.qlen))
   57 
   58 
   59 static void 
   60 do_sstf_ord_q(RF_DiskQueueData_t **,
   61     RF_DiskQueueData_t **,
   62     RF_DiskQueueData_t *);
   63 
   64 static RF_DiskQueueData_t *
   65 closest_to_arm(RF_SstfQ_t *,
   66     RF_SectorNum_t,
   67     int *,
   68     int);
   69 static void do_dequeue(RF_SstfQ_t *, RF_DiskQueueData_t *);
   70 
   71 
   72 static void 
   73 do_sstf_ord_q(queuep, tailp, req)
   74         RF_DiskQueueData_t **queuep;
   75         RF_DiskQueueData_t **tailp;
   76         RF_DiskQueueData_t *req;
   77 {
   78         RF_DiskQueueData_t *r, *s;
   79 
   80         if (*queuep == NULL) {
   81                 *queuep = req;
   82                 *tailp = req;
   83                 req->next = NULL;
   84                 req->prev = NULL;
   85                 return;
   86         }
   87         if (req->sectorOffset <= (*queuep)->sectorOffset) {
   88                 req->next = *queuep;
   89                 req->prev = NULL;
   90                 (*queuep)->prev = req;
   91                 *queuep = req;
   92                 return;
   93         }
   94         if (req->sectorOffset > (*tailp)->sectorOffset) {
   95                 /* optimization */
   96                 r = NULL;
   97                 s = *tailp;
   98                 goto q_at_end;
   99         }
  100         for (s = NULL, r = *queuep; r; s = r, r = r->next) {
  101                 if (r->sectorOffset >= req->sectorOffset) {
  102                         /* insert after s, before r */
  103                         RF_ASSERT(s);
  104                         req->next = r;
  105                         r->prev = req;
  106                         s->next = req;
  107                         req->prev = s;
  108                         return;
  109                 }
  110         }
  111 q_at_end:
  112         /* insert after s, at end of queue */
  113         RF_ASSERT(r == NULL);
  114         RF_ASSERT(s);
  115         RF_ASSERT(s == (*tailp));
  116         req->next = NULL;
  117         req->prev = s;
  118         s->next = req;
  119         *tailp = req;
  120 }
  121 /* for removing from head-of-queue */
  122 #define DO_HEAD_DEQ(_r_,_q_) { \
  123         _r_ = (_q_)->queue; \
  124         RF_ASSERT((_r_) != NULL); \
  125         (_q_)->queue = (_r_)->next; \
  126         (_q_)->qlen--; \
  127         if ((_q_)->qlen == 0) { \
  128                 RF_ASSERT((_r_) == (_q_)->qtail); \
  129                 RF_ASSERT((_q_)->queue == NULL); \
  130                 (_q_)->qtail = NULL; \
  131         } \
  132         else { \
  133                 RF_ASSERT((_q_)->queue->prev == (_r_)); \
  134                 (_q_)->queue->prev = NULL; \
  135         } \
  136 }
  137 
  138 /* for removing from end-of-queue */
  139 #define DO_TAIL_DEQ(_r_,_q_) { \
  140         _r_ = (_q_)->qtail; \
  141         RF_ASSERT((_r_) != NULL); \
  142         (_q_)->qtail = (_r_)->prev; \
  143         (_q_)->qlen--; \
  144         if ((_q_)->qlen == 0) { \
  145                 RF_ASSERT((_r_) == (_q_)->queue); \
  146                 RF_ASSERT((_q_)->qtail == NULL); \
  147                 (_q_)->queue = NULL; \
  148         } \
  149         else { \
  150                 RF_ASSERT((_q_)->qtail->next == (_r_)); \
  151                 (_q_)->qtail->next = NULL; \
  152         } \
  153 }
  154 
  155 #define DO_BEST_DEQ(_l_,_r_,_q_) { \
  156         if (SNUM_DIFF((_q_)->queue->sectorOffset,_l_) \
  157                 < SNUM_DIFF((_q_)->qtail->sectorOffset,_l_)) \
  158         { \
  159                 DO_HEAD_DEQ(_r_,_q_); \
  160         } \
  161         else { \
  162                 DO_TAIL_DEQ(_r_,_q_); \
  163         } \
  164 }
  165 
  166 static RF_DiskQueueData_t *
  167 closest_to_arm(queue, arm_pos, dir, allow_reverse)
  168         RF_SstfQ_t *queue;
  169         RF_SectorNum_t arm_pos;
  170         int    *dir;
  171         int     allow_reverse;
  172 {
  173         RF_SectorNum_t best_pos_l = 0, this_pos_l = 0, last_pos = 0;
  174         RF_SectorNum_t best_pos_r = 0, this_pos_r = 0;
  175         RF_DiskQueueData_t *r, *best_l, *best_r;
  176 
  177         best_r = best_l = NULL;
  178         for (r = queue->queue; r; r = r->next) {
  179                 if (r->sectorOffset < arm_pos) {
  180                         if (best_l == NULL) {
  181                                 best_l = r;
  182                                 last_pos = best_pos_l = this_pos_l;
  183                         } else {
  184                                 this_pos_l = arm_pos - r->sectorOffset;
  185                                 if (this_pos_l < best_pos_l) {
  186                                         best_l = r;
  187                                         last_pos = best_pos_l = this_pos_l;
  188                                 } else {
  189                                         last_pos = this_pos_l;
  190                                 }
  191                         }
  192                 } else {
  193                         if (best_r == NULL) {
  194                                 best_r = r;
  195                                 last_pos = best_pos_r = this_pos_r;
  196                         } else {
  197                                 this_pos_r = r->sectorOffset - arm_pos;
  198                                 if (this_pos_r < best_pos_r) {
  199                                         best_r = r;
  200                                         last_pos = best_pos_r = this_pos_r;
  201                                 } else {
  202                                         last_pos = this_pos_r;
  203                                 }
  204                                 if (this_pos_r > last_pos) {
  205                                         /* getting farther away */
  206                                         break;
  207                                 }
  208                         }
  209                 }
  210         }
  211         if ((best_r == NULL) && (best_l == NULL))
  212                 return (NULL);
  213         if ((*dir == DIR_RIGHT) && best_r)
  214                 return (best_r);
  215         if ((*dir == DIR_LEFT) && best_l)
  216                 return (best_l);
  217         if (*dir == DIR_EITHER) {
  218                 if (best_l == NULL)
  219                         return (best_r);
  220                 if (best_r == NULL)
  221                         return (best_l);
  222                 if (best_pos_r < best_pos_l)
  223                         return (best_r);
  224                 else
  225                         return (best_l);
  226         }
  227         /*
  228          * Nothing in the direction we want to go. Reverse or
  229          * reset the arm. We know we have an I/O in the other
  230          * direction.
  231          */
  232         if (allow_reverse) {
  233                 if (*dir == DIR_RIGHT) {
  234                         *dir = DIR_LEFT;
  235                         return (best_l);
  236                 } else {
  237                         *dir = DIR_RIGHT;
  238                         return (best_r);
  239                 }
  240         }
  241         /*
  242          * Reset (beginning of queue).
  243          */
  244         RF_ASSERT(*dir == DIR_RIGHT);
  245         return (queue->queue);
  246 }
  247 
  248 void   *
  249 rf_SstfCreate(sect_per_disk, cl_list, listp)
  250         RF_SectorCount_t sect_per_disk;
  251         RF_AllocListElem_t *cl_list;
  252         RF_ShutdownList_t **listp;
  253 {
  254         RF_Sstf_t *sstfq;
  255 
  256         RF_MallocAndAdd(sstfq, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
  257         sstfq->dir = DIR_EITHER;
  258         sstfq->allow_reverse = 1;
  259         return ((void *) sstfq);
  260 }
  261 
  262 void   *
  263 rf_ScanCreate(sect_per_disk, cl_list, listp)
  264         RF_SectorCount_t sect_per_disk;
  265         RF_AllocListElem_t *cl_list;
  266         RF_ShutdownList_t **listp;
  267 {
  268         RF_Sstf_t *scanq;
  269 
  270         RF_MallocAndAdd(scanq, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
  271         scanq->dir = DIR_RIGHT;
  272         scanq->allow_reverse = 1;
  273         return ((void *) scanq);
  274 }
  275 
  276 void   *
  277 rf_CscanCreate(sect_per_disk, cl_list, listp)
  278         RF_SectorCount_t sect_per_disk;
  279         RF_AllocListElem_t *cl_list;
  280         RF_ShutdownList_t **listp;
  281 {
  282         RF_Sstf_t *cscanq;
  283 
  284         RF_MallocAndAdd(cscanq, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
  285         cscanq->dir = DIR_RIGHT;
  286         return ((void *) cscanq);
  287 }
  288 
  289 void 
  290 rf_SstfEnqueue(qptr, req, priority)
  291         void   *qptr;
  292         RF_DiskQueueData_t *req;
  293         int     priority;
  294 {
  295         RF_Sstf_t *sstfq;
  296 
  297         sstfq = (RF_Sstf_t *) qptr;
  298 
  299         if (priority == RF_IO_LOW_PRIORITY) {
  300 #if RF_DEBUG_QUEUE
  301                 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
  302                         RF_DiskQueue_t *dq;
  303                         dq = (RF_DiskQueue_t *) req->queue;
  304                         printf("raid%d: ENQ lopri %d queues are %d,%d,%d\n",
  305                                req->raidPtr->raidid,
  306                                dq->col, 
  307                                sstfq->left.qlen, sstfq->right.qlen,
  308                                sstfq->lopri.qlen);
  309                 }
  310 #endif
  311                 do_sstf_ord_q(&sstfq->lopri.queue, &sstfq->lopri.qtail, req);
  312                 sstfq->lopri.qlen++;
  313         } else {
  314                 if (req->sectorOffset < sstfq->last_sector) {
  315                         do_sstf_ord_q(&sstfq->left.queue, &sstfq->left.qtail, req);
  316                         sstfq->left.qlen++;
  317                 } else {
  318                         do_sstf_ord_q(&sstfq->right.queue, &sstfq->right.qtail, req);
  319                         sstfq->right.qlen++;
  320                 }
  321         }
  322 }
  323 
  324 static void 
  325 do_dequeue(queue, req)
  326         RF_SstfQ_t *queue;
  327         RF_DiskQueueData_t *req;
  328 {
  329         RF_DiskQueueData_t *req2;
  330 
  331 #if RF_DEBUG_QUEUE
  332         if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
  333                 printf("raid%d: do_dequeue\n", req->raidPtr->raidid);
  334         }
  335 #endif
  336         if (req == queue->queue) {
  337                 DO_HEAD_DEQ(req2, queue);
  338                 RF_ASSERT(req2 == req);
  339         } else
  340                 if (req == queue->qtail) {
  341                         DO_TAIL_DEQ(req2, queue);
  342                         RF_ASSERT(req2 == req);
  343                 } else {
  344                         /* dequeue from middle of list */
  345                         RF_ASSERT(req->next);
  346                         RF_ASSERT(req->prev);
  347                         queue->qlen--;
  348                         req->next->prev = req->prev;
  349                         req->prev->next = req->next;
  350                         req->next = req->prev = NULL;
  351                 }
  352 }
  353 
  354 RF_DiskQueueData_t *
  355 rf_SstfDequeue(qptr)
  356         void   *qptr;
  357 {
  358         RF_DiskQueueData_t *req = NULL;
  359         RF_Sstf_t *sstfq;
  360 
  361         sstfq = (RF_Sstf_t *) qptr;
  362 
  363 #if RF_DEBUG_QUEUE
  364         if (rf_sstfDebug) {
  365                 RF_DiskQueue_t *dq;
  366                 dq = (RF_DiskQueue_t *) req->queue;
  367                 RF_ASSERT(QSUM(sstfq) == dq->queueLength);
  368                 printf("raid%d: sstf: Dequeue %d queues are %d,%d,%d\n",
  369                        req->raidPtr->raidid, dq->col, 
  370                        sstfq->left.qlen, sstfq->right.qlen, sstfq->lopri.qlen);
  371         }
  372 #endif
  373         if (sstfq->left.queue == NULL) {
  374                 RF_ASSERT(sstfq->left.qlen == 0);
  375                 if (sstfq->right.queue == NULL) {
  376                         RF_ASSERT(sstfq->right.qlen == 0);
  377                         if (sstfq->lopri.queue == NULL) {
  378                                 RF_ASSERT(sstfq->lopri.qlen == 0);
  379                                 return (NULL);
  380                         }
  381 #if RF_DEBUG_QUEUE
  382                         if (rf_sstfDebug) {
  383                                 printf("raid%d: sstf: check for close lopri",
  384                                        req->raidPtr->raidid);
  385                         }
  386 #endif
  387                         req = closest_to_arm(&sstfq->lopri, sstfq->last_sector,
  388                             &sstfq->dir, sstfq->allow_reverse);
  389 #if RF_DEBUG_QUEUE
  390                         if (rf_sstfDebug) {
  391                                 printf("raid%d: sstf: closest_to_arm said %lx",
  392                                        req->raidPtr->raidid, (long) req);
  393                         }
  394 #endif
  395                         if (req == NULL)
  396                                 return (NULL);
  397                         do_dequeue(&sstfq->lopri, req);
  398                 } else {
  399                         DO_BEST_DEQ(sstfq->last_sector, req, &sstfq->right);
  400                 }
  401         } else {
  402                 if (sstfq->right.queue == NULL) {
  403                         RF_ASSERT(sstfq->right.qlen == 0);
  404                         DO_BEST_DEQ(sstfq->last_sector, req, &sstfq->left);
  405                 } else {
  406                         if (SNUM_DIFF(sstfq->last_sector, sstfq->right.queue->sectorOffset)
  407                             < SNUM_DIFF(sstfq->last_sector, sstfq->left.qtail->sectorOffset)) {
  408                                 DO_HEAD_DEQ(req, &sstfq->right);
  409                         } else {
  410                                 DO_TAIL_DEQ(req, &sstfq->left);
  411                         }
  412                 }
  413         }
  414         RF_ASSERT(req);
  415         sstfq->last_sector = req->sectorOffset;
  416         return (req);
  417 }
  418 
  419 RF_DiskQueueData_t *
  420 rf_ScanDequeue(qptr)
  421         void   *qptr;
  422 {
  423         RF_DiskQueueData_t *req = NULL;
  424         RF_Sstf_t *scanq;
  425 
  426         scanq = (RF_Sstf_t *) qptr;
  427 
  428 #if RF_DEBUG_QUEUE
  429         if (rf_scanDebug) {
  430                 RF_DiskQueue_t *dq;
  431                 dq = (RF_DiskQueue_t *) req->queue;
  432                 RF_ASSERT(QSUM(scanq) == dq->queueLength);
  433                 printf("raid%d: scan: Dequeue %d queues are %d,%d,%d\n", 
  434                        req->raidPtr->raidid, dq->col, 
  435                        scanq->left.qlen, scanq->right.qlen, scanq->lopri.qlen);
  436         }
  437 #endif
  438         if (scanq->left.queue == NULL) {
  439                 RF_ASSERT(scanq->left.qlen == 0);
  440                 if (scanq->right.queue == NULL) {
  441                         RF_ASSERT(scanq->right.qlen == 0);
  442                         if (scanq->lopri.queue == NULL) {
  443                                 RF_ASSERT(scanq->lopri.qlen == 0);
  444                                 return (NULL);
  445                         }
  446                         req = closest_to_arm(&scanq->lopri, scanq->last_sector,
  447                             &scanq->dir, scanq->allow_reverse);
  448                         if (req == NULL)
  449                                 return (NULL);
  450                         do_dequeue(&scanq->lopri, req);
  451                 } else {
  452                         scanq->dir = DIR_RIGHT;
  453                         DO_HEAD_DEQ(req, &scanq->right);
  454                 }
  455         } else
  456                 if (scanq->right.queue == NULL) {
  457                         RF_ASSERT(scanq->right.qlen == 0);
  458                         RF_ASSERT(scanq->left.queue);
  459                         scanq->dir = DIR_LEFT;
  460                         DO_TAIL_DEQ(req, &scanq->left);
  461                 } else {
  462                         RF_ASSERT(scanq->right.queue);
  463                         RF_ASSERT(scanq->left.queue);
  464                         if (scanq->dir == DIR_RIGHT) {
  465                                 DO_HEAD_DEQ(req, &scanq->right);
  466                         } else {
  467                                 DO_TAIL_DEQ(req, &scanq->left);
  468                         }
  469                 }
  470         RF_ASSERT(req);
  471         scanq->last_sector = req->sectorOffset;
  472         return (req);
  473 }
  474 
  475 RF_DiskQueueData_t *
  476 rf_CscanDequeue(qptr)
  477         void   *qptr;
  478 {
  479         RF_DiskQueueData_t *req = NULL;
  480         RF_Sstf_t *cscanq;
  481 
  482         cscanq = (RF_Sstf_t *) qptr;
  483 
  484         RF_ASSERT(cscanq->dir == DIR_RIGHT);
  485 #if RF_DEBUG_QUEUE
  486         if (rf_cscanDebug) {
  487                 RF_DiskQueue_t *dq;
  488                 dq = (RF_DiskQueue_t *) req->queue;
  489                 RF_ASSERT(QSUM(cscanq) == dq->queueLength);
  490                 printf("raid%d: scan: Dequeue %d queues are %d,%d,%d\n", 
  491                        req->raidPtr->raidid, dq->col,
  492                        cscanq->left.qlen, cscanq->right.qlen,
  493                        cscanq->lopri.qlen);
  494         }
  495 #endif
  496         if (cscanq->right.queue) {
  497                 DO_HEAD_DEQ(req, &cscanq->right);
  498         } else {
  499                 RF_ASSERT(cscanq->right.qlen == 0);
  500                 if (cscanq->left.queue == NULL) {
  501                         RF_ASSERT(cscanq->left.qlen == 0);
  502                         if (cscanq->lopri.queue == NULL) {
  503                                 RF_ASSERT(cscanq->lopri.qlen == 0);
  504                                 return (NULL);
  505                         }
  506                         req = closest_to_arm(&cscanq->lopri, cscanq->last_sector,
  507                             &cscanq->dir, cscanq->allow_reverse);
  508                         if (req == NULL)
  509                                 return (NULL);
  510                         do_dequeue(&cscanq->lopri, req);
  511                 } else {
  512                         /*
  513                          * There's I/Os to the left of the arm. Swing
  514                          * on back (swap queues).
  515                          */
  516                         cscanq->right = cscanq->left;
  517                         cscanq->left.qlen = 0;
  518                         cscanq->left.queue = cscanq->left.qtail = NULL;
  519                         DO_HEAD_DEQ(req, &cscanq->right);
  520                 }
  521         }
  522         RF_ASSERT(req);
  523         cscanq->last_sector = req->sectorOffset;
  524         return (req);
  525 }
  526 
  527 RF_DiskQueueData_t *
  528 rf_SstfPeek(qptr)
  529         void   *qptr;
  530 {
  531         RF_DiskQueueData_t *req;
  532         RF_Sstf_t *sstfq;
  533 
  534         sstfq = (RF_Sstf_t *) qptr;
  535 
  536         if ((sstfq->left.queue == NULL) && (sstfq->right.queue == NULL)) {
  537                 req = closest_to_arm(&sstfq->lopri, sstfq->last_sector, &sstfq->dir,
  538                     sstfq->allow_reverse);
  539         } else {
  540                 if (sstfq->left.queue == NULL)
  541                         req = sstfq->right.queue;
  542                 else {
  543                         if (sstfq->right.queue == NULL)
  544                                 req = sstfq->left.queue;
  545                         else {
  546                                 if (SNUM_DIFF(sstfq->last_sector, sstfq->right.queue->sectorOffset)
  547                                     < SNUM_DIFF(sstfq->last_sector, sstfq->left.qtail->sectorOffset)) {
  548                                         req = sstfq->right.queue;
  549                                 } else {
  550                                         req = sstfq->left.qtail;
  551                                 }
  552                         }
  553                 }
  554         }
  555         if (req == NULL) {
  556                 RF_ASSERT(QSUM(sstfq) == 0);
  557         }
  558         return (req);
  559 }
  560 
  561 RF_DiskQueueData_t *
  562 rf_ScanPeek(qptr)
  563         void   *qptr;
  564 {
  565         RF_DiskQueueData_t *req;
  566         RF_Sstf_t *scanq;
  567         int     dir;
  568 
  569         scanq = (RF_Sstf_t *) qptr;
  570         dir = scanq->dir;
  571 
  572         if (scanq->left.queue == NULL) {
  573                 RF_ASSERT(scanq->left.qlen == 0);
  574                 if (scanq->right.queue == NULL) {
  575                         RF_ASSERT(scanq->right.qlen == 0);
  576                         if (scanq->lopri.queue == NULL) {
  577                                 RF_ASSERT(scanq->lopri.qlen == 0);
  578                                 return (NULL);
  579                         }
  580                         req = closest_to_arm(&scanq->lopri, scanq->last_sector,
  581                             &dir, scanq->allow_reverse);
  582                 } else {
  583                         req = scanq->right.queue;
  584                 }
  585         } else
  586                 if (scanq->right.queue == NULL) {
  587                         RF_ASSERT(scanq->right.qlen == 0);
  588                         RF_ASSERT(scanq->left.queue);
  589                         req = scanq->left.qtail;
  590                 } else {
  591                         RF_ASSERT(scanq->right.queue);
  592                         RF_ASSERT(scanq->left.queue);
  593                         if (scanq->dir == DIR_RIGHT) {
  594                                 req = scanq->right.queue;
  595                         } else {
  596                                 req = scanq->left.qtail;
  597                         }
  598                 }
  599         if (req == NULL) {
  600                 RF_ASSERT(QSUM(scanq) == 0);
  601         }
  602         return (req);
  603 }
  604 
  605 RF_DiskQueueData_t *
  606 rf_CscanPeek(qptr)
  607         void   *qptr;
  608 {
  609         RF_DiskQueueData_t *req;
  610         RF_Sstf_t *cscanq;
  611 
  612         cscanq = (RF_Sstf_t *) qptr;
  613 
  614         RF_ASSERT(cscanq->dir == DIR_RIGHT);
  615         if (cscanq->right.queue) {
  616                 req = cscanq->right.queue;
  617         } else {
  618                 RF_ASSERT(cscanq->right.qlen == 0);
  619                 if (cscanq->left.queue == NULL) {
  620                         RF_ASSERT(cscanq->left.qlen == 0);
  621                         if (cscanq->lopri.queue == NULL) {
  622                                 RF_ASSERT(cscanq->lopri.qlen == 0);
  623                                 return (NULL);
  624                         }
  625                         req = closest_to_arm(&cscanq->lopri, cscanq->last_sector,
  626                             &cscanq->dir, cscanq->allow_reverse);
  627                 } else {
  628                         /*
  629                          * There's I/Os to the left of the arm. We'll end
  630                          * up swinging on back.
  631                          */
  632                         req = cscanq->left.queue;
  633                 }
  634         }
  635         if (req == NULL) {
  636                 RF_ASSERT(QSUM(cscanq) == 0);
  637         }
  638         return (req);
  639 }
  640 
  641 int 
  642 rf_SstfPromote(qptr, parityStripeID, which_ru)
  643         void   *qptr;
  644         RF_StripeNum_t parityStripeID;
  645         RF_ReconUnitNum_t which_ru;
  646 {
  647         RF_DiskQueueData_t *r, *next;
  648         RF_Sstf_t *sstfq;
  649         int     n;
  650 
  651         sstfq = (RF_Sstf_t *) qptr;
  652 
  653         n = 0;
  654         for (r = sstfq->lopri.queue; r; r = next) {
  655                 next = r->next;
  656 #if RF_DEBUG_QUEUE
  657                 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
  658                         printf("raid%d: check promote %lx\n",
  659                                r->raidPtr->raidid, (long) r);
  660                 }
  661 #endif
  662                 if ((r->parityStripeID == parityStripeID)
  663                     && (r->which_ru == which_ru)) {
  664                         do_dequeue(&sstfq->lopri, r);
  665                         rf_SstfEnqueue(qptr, r, RF_IO_NORMAL_PRIORITY);
  666                         n++;
  667                 }
  668         }
  669 #if RF_DEBUG_QUEUE
  670         if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
  671                 printf("raid%d: promoted %d matching I/Os queues are %d,%d,%d\n",
  672                        r->raidPtr->raidid, n, sstfq->left.qlen, 
  673                        sstfq->right.qlen, sstfq->lopri.qlen);
  674         }
  675 #endif
  676         return (n);
  677 }
Cache object: b8ee313d149256ced7602195bcff3eab
[ 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_sstf.c

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