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