bufq_priocscan.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: bufq_priocscan.c,v 1.8 2006/05/22 12:42:01 yamt Exp $  */
    2 
    3 /*-
    4  * Copyright (c)2004 YAMAMOTO Takashi,
    5  * All rights reserved.
    6  *
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  * 1. Redistributions of source code must retain the above copyright
   11  *    notice, this list of conditions and the following disclaimer.
   12  * 2. Redistributions in binary form must reproduce the above copyright
   13  *    notice, this list of conditions and the following disclaimer in the
   14  *    documentation and/or other materials provided with the distribution.
   15  *
   16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   26  * SUCH DAMAGE.
   27  */
   28 
   29 #include <sys/cdefs.h>
   30 __KERNEL_RCSID(0, "$NetBSD: bufq_priocscan.c,v 1.8 2006/05/22 12:42:01 yamt Exp $");
   31 
   32 #include <sys/param.h>
   33 #include <sys/systm.h>
   34 #include <sys/buf.h>
   35 #include <sys/bufq.h>
   36 #include <sys/bufq_impl.h>
   37 #include <sys/malloc.h>
   38 
   39 /*
   40  * Cyclical scan (CSCAN)
   41  */
   42 TAILQ_HEAD(bqhead, buf);
   43 struct cscan_queue {
   44         struct bqhead cq_head[2];       /* actual lists of buffers */
   45         int cq_idx;                     /* current list index */
   46         int cq_lastcylinder;            /* b_cylinder of the last request */
   47         daddr_t cq_lastrawblkno;        /* b_rawblkno of the last request */
   48 };
   49 
   50 static inline int cscan_empty(const struct cscan_queue *);
   51 static void cscan_put(struct cscan_queue *, struct buf *, int);
   52 static struct buf *cscan_get(struct cscan_queue *, int);
   53 static void cscan_init(struct cscan_queue *);
   54 
   55 static inline int
   56 cscan_empty(const struct cscan_queue *q)
   57 {
   58 
   59         return TAILQ_EMPTY(&q->cq_head[0]) && TAILQ_EMPTY(&q->cq_head[1]);
   60 }
   61 
   62 static void
   63 cscan_put(struct cscan_queue *q, struct buf *bp, int sortby)
   64 {
   65         struct buf tmp;
   66         struct buf *it;
   67         struct bqhead *bqh;
   68         int idx;
   69 
   70         tmp.b_cylinder = q->cq_lastcylinder;
   71         tmp.b_rawblkno = q->cq_lastrawblkno;
   72 
   73         if (buf_inorder(bp, &tmp, sortby))
   74                 idx = 1 - q->cq_idx;
   75         else
   76                 idx = q->cq_idx;
   77 
   78         bqh = &q->cq_head[idx];
   79 
   80         TAILQ_FOREACH(it, bqh, b_actq)
   81                 if (buf_inorder(bp, it, sortby))
   82                         break;
   83 
   84         if (it != NULL)
   85                 TAILQ_INSERT_BEFORE(it, bp, b_actq);
   86         else
   87                 TAILQ_INSERT_TAIL(bqh, bp, b_actq);
   88 }
   89 
   90 static struct buf *
   91 cscan_get(struct cscan_queue *q, int remove)
   92 {
   93         int idx = q->cq_idx;
   94         struct bqhead *bqh;
   95         struct buf *bp;
   96 
   97         bqh = &q->cq_head[idx];
   98         bp = TAILQ_FIRST(bqh);
   99 
  100         if (bp == NULL) {
  101                 /* switch queue */
  102                 idx = 1 - idx;
  103                 bqh = &q->cq_head[idx];
  104                 bp = TAILQ_FIRST(bqh);
  105         }
  106 
  107         KDASSERT((bp != NULL && !cscan_empty(q)) ||
  108                  (bp == NULL && cscan_empty(q)));
  109 
  110         if (bp != NULL && remove) {
  111                 q->cq_idx = idx;
  112                 TAILQ_REMOVE(bqh, bp, b_actq);
  113 
  114                 q->cq_lastcylinder = bp->b_cylinder;
  115                 q->cq_lastrawblkno =
  116                     bp->b_rawblkno + (bp->b_bcount >> DEV_BSHIFT);
  117         }
  118 
  119         return (bp);
  120 }
  121 
  122 static void
  123 cscan_init(struct cscan_queue *q)
  124 {
  125 
  126         TAILQ_INIT(&q->cq_head[0]);
  127         TAILQ_INIT(&q->cq_head[1]);
  128 }
  129 
  130 
  131 /*
  132  * Per-prioritiy CSCAN.
  133  *
  134  * XXX probably we should have a way to raise
  135  * priority of the on-queue requests.
  136  */
  137 #define PRIOCSCAN_NQUEUE        3
  138 
  139 struct priocscan_queue {
  140         struct cscan_queue q_queue;
  141         int q_burst;
  142 };
  143 
  144 struct bufq_priocscan {
  145         struct priocscan_queue bq_queue[PRIOCSCAN_NQUEUE];
  146 
  147 #if 0
  148         /*
  149          * XXX using "global" head position can reduce positioning time
  150          * when switching between queues.
  151          * although it might affect against fairness.
  152          */
  153         daddr_t bq_lastrawblkno;
  154         int bq_lastcylinder;
  155 #endif
  156 };
  157 
  158 /*
  159  * how many requests to serve when having pending requests on other queues.
  160  *
  161  * XXX tune
  162  */
  163 const int priocscan_burst[] = {
  164         64, 16, 4
  165 };
  166 
  167 static void bufq_priocscan_init(struct bufq_state *);
  168 static void bufq_priocscan_put(struct bufq_state *, struct buf *);
  169 static struct buf *bufq_priocscan_get(struct bufq_state *, int);
  170 
  171 BUFQ_DEFINE(priocscan, 40, bufq_priocscan_init);
  172 
  173 static inline struct cscan_queue *bufq_priocscan_selectqueue(
  174     struct bufq_priocscan *, const struct buf *);
  175 
  176 static inline struct cscan_queue *
  177 bufq_priocscan_selectqueue(struct bufq_priocscan *q, const struct buf *bp)
  178 {
  179         static const int priocscan_priomap[] = {
  180                 [BPRIO_TIMENONCRITICAL] = 2,
  181                 [BPRIO_TIMELIMITED] = 1,
  182                 [BPRIO_TIMECRITICAL] = 0
  183         };
  184 
  185         return &q->bq_queue[priocscan_priomap[BIO_GETPRIO(bp)]].q_queue;
  186 }
  187 
  188 static void
  189 bufq_priocscan_put(struct bufq_state *bufq, struct buf *bp)
  190 {
  191         struct bufq_priocscan *q = bufq->bq_private;
  192         struct cscan_queue *cq;
  193         const int sortby = bufq->bq_flags & BUFQ_SORT_MASK;
  194 
  195         cq = bufq_priocscan_selectqueue(q, bp);
  196         cscan_put(cq, bp, sortby);
  197 }
  198 
  199 static struct buf *
  200 bufq_priocscan_get(struct bufq_state *bufq, int remove)
  201 {
  202         struct bufq_priocscan *q = bufq->bq_private;
  203         struct priocscan_queue *pq, *npq;
  204         struct priocscan_queue *first; /* first non-empty queue */
  205         const struct priocscan_queue *epq;
  206         const struct cscan_queue *cq;
  207         struct buf *bp;
  208         boolean_t single; /* true if there's only one non-empty queue */
  209 
  210         pq = &q->bq_queue[0];
  211         epq = pq + PRIOCSCAN_NQUEUE;
  212         for (; pq < epq; pq++) {
  213                 cq = &pq->q_queue;
  214                 if (!cscan_empty(cq))
  215                         break;
  216         }
  217         if (pq == epq) {
  218                 /* there's no requests */
  219                 return NULL;
  220         }
  221 
  222         first = pq;
  223         single = TRUE;
  224         for (npq = first + 1; npq < epq; npq++) {
  225                 cq = &npq->q_queue;
  226                 if (!cscan_empty(cq)) {
  227                         single = FALSE;
  228                         if (pq->q_burst > 0)
  229                                 break;
  230                         pq = npq;
  231                 }
  232         }
  233         if (single) {
  234                 /*
  235                  * there's only a non-empty queue.  just serve it.
  236                  */
  237                 pq = first;
  238         } else if (pq->q_burst > 0) {
  239                 /*
  240                  * XXX account only by number of requests.  is it good enough?
  241                  */
  242                 if (remove) {
  243                         pq->q_burst--;
  244                 }
  245         } else {
  246                 /*
  247                  * no queue was selected due to burst counts
  248                  */
  249                 int i;
  250 #ifdef DEBUG
  251                 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  252                         pq = &q->bq_queue[i];
  253                         cq = &pq->q_queue;
  254                         if (!cscan_empty(cq) && pq->q_burst)
  255                                 panic("%s: inconsist", __func__);
  256                 }
  257 #endif /* DEBUG */
  258 
  259                 /*
  260                  * reset burst counts
  261                  */
  262                 if (remove) {
  263                         for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  264                                 pq = &q->bq_queue[i];
  265                                 pq->q_burst = priocscan_burst[i];
  266                         }
  267                 }
  268 
  269                 /*
  270                  * serve first non-empty queue.
  271                  */
  272                 pq = first;
  273         }
  274 
  275         KDASSERT(!cscan_empty(&pq->q_queue));
  276         bp = cscan_get(&pq->q_queue, remove);
  277         KDASSERT(bp != NULL);
  278         KDASSERT(&pq->q_queue == bufq_priocscan_selectqueue(q, bp));
  279 
  280         return bp;
  281 }
  282 
  283 static void
  284 bufq_priocscan_init(struct bufq_state *bufq)
  285 {
  286         struct bufq_priocscan *q;
  287         int i;
  288 
  289         bufq->bq_get = bufq_priocscan_get;
  290         bufq->bq_put = bufq_priocscan_put;
  291         bufq->bq_private = malloc(sizeof(struct bufq_priocscan),
  292             M_DEVBUF, M_ZERO);
  293 
  294         q = bufq->bq_private;
  295         for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  296                 struct cscan_queue *cq = &q->bq_queue[i].q_queue;
  297 
  298                 cscan_init(cq);
  299         }
  300 }

Cache object: 9038afb2f7ac02a5d98727f66fdfad54

[ 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/kern/bufq_priocscan.c

FreeBSD/Linux Kernel Cross Reference
sys/kern/bufq_priocscan.c