[BACK]Return to bufq_priocscan.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / sys / kern

Annotation of src/sys/kern/bufq_priocscan.c, Revision 1.14

1.14    ! yamt        1: /*     $NetBSD: bufq_priocscan.c,v 1.13 2009/01/16 01:44:27 yamt Exp $ */
1.1       yamt        2:
                      3: /*-
1.13      yamt        4:  * Copyright (c)2004,2005,2006,2008,2009 YAMAMOTO Takashi,
1.1       yamt        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>
1.14    ! yamt       30: __KERNEL_RCSID(0, "$NetBSD: bufq_priocscan.c,v 1.13 2009/01/16 01:44:27 yamt Exp $");
1.1       yamt       31:
                     32: #include <sys/param.h>
                     33: #include <sys/systm.h>
                     34: #include <sys/buf.h>
1.2       yamt       35: #include <sys/bufq.h>
1.5       yamt       36: #include <sys/bufq_impl.h>
1.14    ! yamt       37: #include <sys/kmem.h>
1.1       yamt       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:
1.8       yamt       50: static inline int cscan_empty(const struct cscan_queue *);
1.1       yamt       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:
1.7       perry      55: static inline int
1.1       yamt       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
1.12      yamt      162:  * be careful: while making these values larger likely
                    163:  * increases the total throughput, it can also increase latencies
                    164:  * for some workloads.
1.1       yamt      165:  */
                    166: const int priocscan_burst[] = {
                    167:        64, 16, 4
                    168: };
                    169:
1.3       yamt      170: static void bufq_priocscan_init(struct bufq_state *);
1.1       yamt      171: static void bufq_priocscan_put(struct bufq_state *, struct buf *);
                    172: static struct buf *bufq_priocscan_get(struct bufq_state *, int);
1.3       yamt      173:
1.5       yamt      174: BUFQ_DEFINE(priocscan, 40, bufq_priocscan_init);
1.3       yamt      175:
1.7       perry     176: static inline struct cscan_queue *bufq_priocscan_selectqueue(
1.1       yamt      177:     struct bufq_priocscan *, const struct buf *);
                    178:
1.7       perry     179: static inline struct cscan_queue *
1.1       yamt      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;
1.9       thorpej   211:        bool single; /* true if there's only one non-empty queue */
1.1       yamt      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;
1.10      thorpej   226:        single = true;
1.1       yamt      227:        for (npq = first + 1; npq < epq; npq++) {
                    228:                cq = &npq->q_queue;
                    229:                if (!cscan_empty(cq)) {
1.10      thorpej   230:                        single = false;
1.1       yamt      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:                 */
1.4       yamt      245:                if (remove) {
                    246:                        pq->q_burst--;
                    247:                }
1.1       yamt      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:                 */
1.4       yamt      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:                        }
1.1       yamt      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:
1.11      reinoud   286: static struct buf *
1.13      yamt      287: bufq_priocscan_cancel(struct bufq_state *bufq, struct buf *bp)
1.11      reinoud   288: {
1.13      yamt      289:        struct bufq_priocscan * const q = bufq->bq_private;
                    290:        int i, j;
1.11      reinoud   291:
1.13      yamt      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:                                }
1.11      reinoud   303:                        }
                    304:                }
                    305:        }
                    306:        return NULL;
                    307: }
                    308:
1.3       yamt      309: static void
1.14    ! yamt      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
1.1       yamt      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;
1.11      reinoud   325:        bufq->bq_cancel = bufq_priocscan_cancel;
1.14    ! yamt      326:        bufq->bq_fini = bufq_priocscan_fini;
        !           327:        bufq->bq_private = kmem_zalloc(sizeof(struct bufq_priocscan), KM_SLEEP);
1.1       yamt      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: }

CVSweb <webmaster@jp.NetBSD.org>