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.12 2008/05/03 05:18:36 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.12 2008/05/03 05:18:36 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  * be careful: while making these values larger likely
  163  * increases the total throughput, it can also increase latencies
  164  * for some workloads.
  165  */
  166 const int priocscan_burst[] = {
  167         64, 16, 4
  168 };
  169 
  170 static void bufq_priocscan_init(struct bufq_state *);
  171 static void bufq_priocscan_put(struct bufq_state *, struct buf *);
  172 static struct buf *bufq_priocscan_get(struct bufq_state *, int);
  173 
  174 BUFQ_DEFINE(priocscan, 40, bufq_priocscan_init);
  175 
  176 static inline struct cscan_queue *bufq_priocscan_selectqueue(
  177     struct bufq_priocscan *, const struct buf *);
  178 
  179 static inline struct cscan_queue *
  180 bufq_priocscan_selectqueue(struct bufq_priocscan *q, const struct buf *bp)
  181 {
  182         static const int priocscan_priomap[] = {
  183                 [BPRIO_TIMENONCRITICAL] = 2,
  184                 [BPRIO_TIMELIMITED] = 1,
  185                 [BPRIO_TIMECRITICAL] = 0
  186         };
  187 
  188         return &q->bq_queue[priocscan_priomap[BIO_GETPRIO(bp)]].q_queue;
  189 }
  190 
  191 static void
  192 bufq_priocscan_put(struct bufq_state *bufq, struct buf *bp)
  193 {
  194         struct bufq_priocscan *q = bufq->bq_private;
  195         struct cscan_queue *cq;
  196         const int sortby = bufq->bq_flags & BUFQ_SORT_MASK;
  197 
  198         cq = bufq_priocscan_selectqueue(q, bp);
  199         cscan_put(cq, bp, sortby);
  200 }
  201 
  202 static struct buf *
  203 bufq_priocscan_get(struct bufq_state *bufq, int remove)
  204 {
  205         struct bufq_priocscan *q = bufq->bq_private;
  206         struct priocscan_queue *pq, *npq;
  207         struct priocscan_queue *first; /* first non-empty queue */
  208         const struct priocscan_queue *epq;
  209         const struct cscan_queue *cq;
  210         struct buf *bp;
  211         bool single; /* true if there's only one non-empty queue */
  212 
  213         pq = &q->bq_queue[0];
  214         epq = pq + PRIOCSCAN_NQUEUE;
  215         for (; pq < epq; pq++) {
  216                 cq = &pq->q_queue;
  217                 if (!cscan_empty(cq))
  218                         break;
  219         }
  220         if (pq == epq) {
  221                 /* there's no requests */
  222                 return NULL;
  223         }
  224 
  225         first = pq;
  226         single = true;
  227         for (npq = first + 1; npq < epq; npq++) {
  228                 cq = &npq->q_queue;
  229                 if (!cscan_empty(cq)) {
  230                         single = false;
  231                         if (pq->q_burst > 0)
  232                                 break;
  233                         pq = npq;
  234                 }
  235         }
  236         if (single) {
  237                 /*
  238                  * there's only a non-empty queue.  just serve it.
  239                  */
  240                 pq = first;
  241         } else if (pq->q_burst > 0) {
  242                 /*
  243                  * XXX account only by number of requests.  is it good enough?
  244                  */
  245                 if (remove) {
  246                         pq->q_burst--;
  247                 }
  248         } else {
  249                 /*
  250                  * no queue was selected due to burst counts
  251                  */
  252                 int i;
  253 #ifdef DEBUG
  254                 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  255                         pq = &q->bq_queue[i];
  256                         cq = &pq->q_queue;
  257                         if (!cscan_empty(cq) && pq->q_burst)
  258                                 panic("%s: inconsist", __func__);
  259                 }
  260 #endif /* DEBUG */
  261 
  262                 /*
  263                  * reset burst counts
  264                  */
  265                 if (remove) {
  266                         for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  267                                 pq = &q->bq_queue[i];
  268                                 pq->q_burst = priocscan_burst[i];
  269                         }
  270                 }
  271 
  272                 /*
  273                  * serve first non-empty queue.
  274                  */
  275                 pq = first;
  276         }
  277 
  278         KDASSERT(!cscan_empty(&pq->q_queue));
  279         bp = cscan_get(&pq->q_queue, remove);
  280         KDASSERT(bp != NULL);
  281         KDASSERT(&pq->q_queue == bufq_priocscan_selectqueue(q, bp));
  282 
  283         return bp;
  284 }
  285 
  286 static struct buf *
  287 bufq_priocscan_cancel(struct bufq_state *bufq, struct buf *buf)
  288 {
  289         struct cscan_queue *q = bufq->bq_private;
  290         struct bqhead *bqh;
  291         struct buf *bq;
  292         int idx;
  293 
  294         for (idx = 0; idx < 2; idx++) {
  295                 bqh = &q->cq_head[idx];
  296                 bq = TAILQ_FIRST(bqh);
  297                 while (bq) {
  298                         if (bq == buf) {
  299                                 TAILQ_REMOVE(bqh, bq, b_actq);
  300                                 return buf;
  301                         }
  302                         bq = TAILQ_NEXT(bq, b_actq);
  303                 }
  304         }
  305         return NULL;
  306 }
  307 
  308 static void
  309 bufq_priocscan_init(struct bufq_state *bufq)
  310 {
  311         struct bufq_priocscan *q;
  312         int i;
  313 
  314         bufq->bq_get = bufq_priocscan_get;
  315         bufq->bq_put = bufq_priocscan_put;
  316         bufq->bq_cancel = bufq_priocscan_cancel;
  317         bufq->bq_private = malloc(sizeof(struct bufq_priocscan),
  318             M_DEVBUF, M_ZERO);
  319 
  320         q = bufq->bq_private;
  321         for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  322                 struct cscan_queue *cq = &q->bq_queue[i].q_queue;
  323 
  324                 cscan_init(cq);
  325         }
  326 }
Cache object: b1c9d5046d9b8e2ebc70a29476294fd2
[ 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
