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