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.4 2005/03/03 05:00:22 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.4 2005/03/03 05:00:22 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/malloc.h>
   37 
   38 /*
   39  * Cyclical scan (CSCAN)
   40  */
   41 TAILQ_HEAD(bqhead, buf);
   42 struct cscan_queue {
   43         struct bqhead cq_head[2];       /* actual lists of buffers */
   44         int cq_idx;                     /* current list index */
   45         int cq_lastcylinder;            /* b_cylinder of the last request */
   46         daddr_t cq_lastrawblkno;        /* b_rawblkno of the last request */
   47 };
   48 
   49 static int __inline cscan_empty(const struct cscan_queue *);
   50 static void cscan_put(struct cscan_queue *, struct buf *, int);
   51 static struct buf *cscan_get(struct cscan_queue *, int);
   52 static void cscan_init(struct cscan_queue *);
   53 
   54 static __inline int
   55 cscan_empty(const struct cscan_queue *q)
   56 {
   57 
   58         return TAILQ_EMPTY(&q->cq_head[0]) && TAILQ_EMPTY(&q->cq_head[1]);
   59 }
   60 
   61 static void
   62 cscan_put(struct cscan_queue *q, struct buf *bp, int sortby)
   63 {
   64         struct buf tmp;
   65         struct buf *it;
   66         struct bqhead *bqh;
   67         int idx;
   68 
   69         tmp.b_cylinder = q->cq_lastcylinder;
   70         tmp.b_rawblkno = q->cq_lastrawblkno;
   71 
   72         if (buf_inorder(bp, &tmp, sortby))
   73                 idx = 1 - q->cq_idx;
   74         else
   75                 idx = q->cq_idx;
   76 
   77         bqh = &q->cq_head[idx];
   78 
   79         TAILQ_FOREACH(it, bqh, b_actq)
   80                 if (buf_inorder(bp, it, sortby))
   81                         break;
   82 
   83         if (it != NULL)
   84                 TAILQ_INSERT_BEFORE(it, bp, b_actq);
   85         else
   86                 TAILQ_INSERT_TAIL(bqh, bp, b_actq);
   87 }
   88 
   89 static struct buf *
   90 cscan_get(struct cscan_queue *q, int remove)
   91 {
   92         int idx = q->cq_idx;
   93         struct bqhead *bqh;
   94         struct buf *bp;
   95 
   96         bqh = &q->cq_head[idx];
   97         bp = TAILQ_FIRST(bqh);
   98 
   99         if (bp == NULL) {
  100                 /* switch queue */
  101                 idx = 1 - idx;
  102                 bqh = &q->cq_head[idx];
  103                 bp = TAILQ_FIRST(bqh);
  104         }
  105 
  106         KDASSERT((bp != NULL && !cscan_empty(q)) ||
  107                  (bp == NULL && cscan_empty(q)));
  108 
  109         if (bp != NULL && remove) {
  110                 q->cq_idx = idx;
  111                 TAILQ_REMOVE(bqh, bp, b_actq);
  112 
  113                 q->cq_lastcylinder = bp->b_cylinder;
  114                 q->cq_lastrawblkno =
  115                     bp->b_rawblkno + (bp->b_bcount >> DEV_BSHIFT);
  116         }
  117 
  118         return (bp);
  119 }
  120 
  121 static void
  122 cscan_init(struct cscan_queue *q)
  123 {
  124 
  125         TAILQ_INIT(&q->cq_head[0]);
  126         TAILQ_INIT(&q->cq_head[1]);
  127 }
  128 
  129 
  130 /*
  131  * Per-prioritiy CSCAN.
  132  *
  133  * XXX probably we should have a way to raise
  134  * priority of the on-queue requests.
  135  */
  136 #define PRIOCSCAN_NQUEUE        3
  137 
  138 struct priocscan_queue {
  139         struct cscan_queue q_queue;
  140         int q_burst;
  141 };
  142 
  143 struct bufq_priocscan {
  144         struct priocscan_queue bq_queue[PRIOCSCAN_NQUEUE];
  145 
  146 #if 0
  147         /*
  148          * XXX using "global" head position can reduce positioning time
  149          * when switching between queues.
  150          * although it might affect against fairness.
  151          */
  152         daddr_t bq_lastrawblkno;
  153         int bq_lastcylinder;
  154 #endif
  155 };
  156 
  157 /*
  158  * how many requests to serve when having pending requests on other queues.
  159  *
  160  * XXX tune
  161  */
  162 const int priocscan_burst[] = {
  163         64, 16, 4
  164 };
  165 
  166 static void bufq_priocscan_init(struct bufq_state *);
  167 static void bufq_priocscan_put(struct bufq_state *, struct buf *);
  168 static struct buf *bufq_priocscan_get(struct bufq_state *, int);
  169 
  170 BUFQ_DEFINE(priocscan, BUFQ_PRIOCSCAN, bufq_priocscan_init);
  171 
  172 static __inline struct cscan_queue *bufq_priocscan_selectqueue(
  173     struct bufq_priocscan *, const struct buf *);
  174 
  175 static __inline struct cscan_queue *
  176 bufq_priocscan_selectqueue(struct bufq_priocscan *q, const struct buf *bp)
  177 {
  178         static const int priocscan_priomap[] = {
  179                 [BPRIO_TIMENONCRITICAL] = 2,
  180                 [BPRIO_TIMELIMITED] = 1,
  181                 [BPRIO_TIMECRITICAL] = 0
  182         };
  183 
  184         return &q->bq_queue[priocscan_priomap[BIO_GETPRIO(bp)]].q_queue;
  185 }
  186 
  187 static void
  188 bufq_priocscan_put(struct bufq_state *bufq, struct buf *bp)
  189 {
  190         struct bufq_priocscan *q = bufq->bq_private;
  191         struct cscan_queue *cq;
  192         const int sortby = bufq->bq_flags & BUFQ_SORT_MASK;
  193 
  194         cq = bufq_priocscan_selectqueue(q, bp);
  195         cscan_put(cq, bp, sortby);
  196 }
  197 
  198 static struct buf *
  199 bufq_priocscan_get(struct bufq_state *bufq, int remove)
  200 {
  201         struct bufq_priocscan *q = bufq->bq_private;
  202         struct priocscan_queue *pq, *npq;
  203         struct priocscan_queue *first; /* first non-empty queue */
  204         const struct priocscan_queue *epq;
  205         const struct cscan_queue *cq;
  206         struct buf *bp;
  207         boolean_t single; /* true if there's only one non-empty queue */
  208 
  209         pq = &q->bq_queue[0];
  210         epq = pq + PRIOCSCAN_NQUEUE;
  211         for (; pq < epq; pq++) {
  212                 cq = &pq->q_queue;
  213                 if (!cscan_empty(cq))
  214                         break;
  215         }
  216         if (pq == epq) {
  217                 /* there's no requests */
  218                 return NULL;
  219         }
  220 
  221         first = pq;
  222         single = TRUE;
  223         for (npq = first + 1; npq < epq; npq++) {
  224                 cq = &npq->q_queue;
  225                 if (!cscan_empty(cq)) {
  226                         single = FALSE;
  227                         if (pq->q_burst > 0)
  228                                 break;
  229                         pq = npq;
  230                 }
  231         }
  232         if (single) {
  233                 /*
  234                  * there's only a non-empty queue.  just serve it.
  235                  */
  236                 pq = first;
  237         } else if (pq->q_burst > 0) {
  238                 /*
  239                  * XXX account only by number of requests.  is it good enough?
  240                  */
  241                 if (remove) {
  242                         pq->q_burst--;
  243                 }
  244         } else {
  245                 /*
  246                  * no queue was selected due to burst counts
  247                  */
  248                 int i;
  249 #ifdef DEBUG
  250                 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  251                         pq = &q->bq_queue[i];
  252                         cq = &pq->q_queue;
  253                         if (!cscan_empty(cq) && pq->q_burst)
  254                                 panic("%s: inconsist", __func__);
  255                 }
  256 #endif /* DEBUG */
  257 
  258                 /*
  259                  * reset burst counts
  260                  */
  261                 if (remove) {
  262                         for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  263                                 pq = &q->bq_queue[i];
  264                                 pq->q_burst = priocscan_burst[i];
  265                         }
  266                 }
  267 
  268                 /*
  269                  * serve first non-empty queue.
  270                  */
  271                 pq = first;
  272         }
  273 
  274         KDASSERT(!cscan_empty(&pq->q_queue));
  275         bp = cscan_get(&pq->q_queue, remove);
  276         KDASSERT(bp != NULL);
  277         KDASSERT(&pq->q_queue == bufq_priocscan_selectqueue(q, bp));
  278 
  279         return bp;
  280 }
  281 
  282 static void
  283 bufq_priocscan_init(struct bufq_state *bufq)
  284 {
  285         struct bufq_priocscan *q;
  286         int i;
  287 
  288         bufq->bq_get = bufq_priocscan_get;
  289         bufq->bq_put = bufq_priocscan_put;
  290         bufq->bq_private = malloc(sizeof(struct bufq_priocscan),
  291             M_DEVBUF, M_ZERO);
  292 
  293         q = bufq->bq_private;
  294         for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
  295                 struct cscan_queue *cq = &q->bq_queue[i].q_queue;
  296 
  297                 cscan_init(cq);
  298         }
  299 }

Cache object: c8aa54fc3c3c3e6a11f5cc3f7f45b0fa

[ 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