sys/kern/bufq_priocscan.c

   1 /*      $NetBSD: bufq_priocscan.c,v 1.13 2009/01/16 01:44:27 yamt Exp $ */
   2
   3 /*-
   4  * Copyright (c)2004,2005,2006,2008,2009 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.13 2009/01/16 01:44:27 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/kmem.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 *bp)
 288 {
 289         struct bufq_priocscan * const q = bufq->bq_private;
 290         int i, j;
 291
 292         for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
 293                 struct cscan_queue * const cq = &q->bq_queue[i].q_queue;
 294                 for (j = 0; j < 2; j++) {
 295                         struct bqhead * const bqh = &cq->cq_head[j];
 296                         struct buf *bq;
 297
 298                         TAILQ_FOREACH(bq, bqh, b_actq) {
 299                                 if (bq == bp) {
 300                                         TAILQ_REMOVE(bqh, bp, b_actq);
 301                                         return bp;
 302                                 }
 303                         }
 304                 }
 305         }
 306         return NULL;
 307 }
 308
 309 static void
 310 bufq_priocscan_fini(struct bufq_state *bufq)
 311 {
 312
 313         KASSERT(bufq->bq_private != NULL);
 314         kmem_free(bufq->bq_private, sizeof(struct bufq_priocscan));
 315 }
 316
 317 static void
 318 bufq_priocscan_init(struct bufq_state *bufq)
 319 {
 320         struct bufq_priocscan *q;
 321         int i;
 322
 323         bufq->bq_get = bufq_priocscan_get;
 324         bufq->bq_put = bufq_priocscan_put;
 325         bufq->bq_cancel = bufq_priocscan_cancel;
 326         bufq->bq_fini = bufq_priocscan_fini;
 327         bufq->bq_private = kmem_zalloc(sizeof(struct bufq_priocscan), KM_SLEEP);
 328
 329         q = bufq->bq_private;
 330         for (i = 0; i < PRIOCSCAN_NQUEUE; i++) {
 331                 struct cscan_queue *cq = &q->bq_queue[i].q_queue;
 332
 333                 cscan_init(cq);
 334         }
 335 }