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