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