bufq_priocscan.c revision 1.9
1 /* $NetBSD: bufq_priocscan.c,v 1.9 2007/02/21 23:00:04 thorpej Exp $ */ 2 3 /*- 4 * Copyright (c)2004 YAMAMOTO Takashi, 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> 30 __KERNEL_RCSID(0, "$NetBSD: bufq_priocscan.c,v 1.9 2007/02/21 23:00:04 thorpej Exp $"); 31 32 #include <sys/param.h> 33 #include <sys/systm.h> 34 #include <sys/buf.h> 35 #include <sys/bufq.h> 36 #include <sys/bufq_impl.h> 37 #include <sys/malloc.h> 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 50 static inline int cscan_empty(const struct cscan_queue *); 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 55 static inline int 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 162 */ 163 const int priocscan_burst[] = { 164 64, 16, 4 165 }; 166 167 static void bufq_priocscan_init(struct bufq_state *); 168 static void bufq_priocscan_put(struct bufq_state *, struct buf *); 169 static struct buf *bufq_priocscan_get(struct bufq_state *, int); 170 171 BUFQ_DEFINE(priocscan, 40, bufq_priocscan_init); 172 173 static inline struct cscan_queue *bufq_priocscan_selectqueue( 174 struct bufq_priocscan *, const struct buf *); 175 176 static inline struct cscan_queue * 177 bufq_priocscan_selectqueue(struct bufq_priocscan *q, const struct buf *bp) 178 { 179 static const int priocscan_priomap[] = { 180 [BPRIO_TIMENONCRITICAL] = 2, 181 [BPRIO_TIMELIMITED] = 1, 182 [BPRIO_TIMECRITICAL] = 0 183 }; 184 185 return &q->bq_queue[priocscan_priomap[BIO_GETPRIO(bp)]].q_queue; 186 } 187 188 static void 189 bufq_priocscan_put(struct bufq_state *bufq, struct buf *bp) 190 { 191 struct bufq_priocscan *q = bufq->bq_private; 192 struct cscan_queue *cq; 193 const int sortby = bufq->bq_flags & BUFQ_SORT_MASK; 194 195 cq = bufq_priocscan_selectqueue(q, bp); 196 cscan_put(cq, bp, sortby); 197 } 198 199 static struct buf * 200 bufq_priocscan_get(struct bufq_state *bufq, int remove) 201 { 202 struct bufq_priocscan *q = bufq->bq_private; 203 struct priocscan_queue *pq, *npq; 204 struct priocscan_queue *first; /* first non-empty queue */ 205 const struct priocscan_queue *epq; 206 const struct cscan_queue *cq; 207 struct buf *bp; 208 bool single; /* true if there's only one non-empty queue */ 209 210 pq = &q->bq_queue[0]; 211 epq = pq + PRIOCSCAN_NQUEUE; 212 for (; pq < epq; pq++) { 213 cq = &pq->q_queue; 214 if (!cscan_empty(cq)) 215 break; 216 } 217 if (pq == epq) { 218 /* there's no requests */ 219 return NULL; 220 } 221 222 first = pq; 223 single = TRUE; 224 for (npq = first + 1; npq < epq; npq++) { 225 cq = &npq->q_queue; 226 if (!cscan_empty(cq)) { 227 single = FALSE; 228 if (pq->q_burst > 0) 229 break; 230 pq = npq; 231 } 232 } 233 if (single) { 234 /* 235 * there's only a non-empty queue. just serve it. 236 */ 237 pq = first; 238 } else if (pq->q_burst > 0) { 239 /* 240 * XXX account only by number of requests. is it good enough? 241 */ 242 if (remove) { 243 pq->q_burst--; 244 } 245 } else { 246 /* 247 * no queue was selected due to burst counts 248 */ 249 int i; 250 #ifdef DEBUG 251 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 252 pq = &q->bq_queue[i]; 253 cq = &pq->q_queue; 254 if (!cscan_empty(cq) && pq->q_burst) 255 panic("%s: inconsist", __func__); 256 } 257 #endif /* DEBUG */ 258 259 /* 260 * reset burst counts 261 */ 262 if (remove) { 263 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 264 pq = &q->bq_queue[i]; 265 pq->q_burst = priocscan_burst[i]; 266 } 267 } 268 269 /* 270 * serve first non-empty queue. 271 */ 272 pq = first; 273 } 274 275 KDASSERT(!cscan_empty(&pq->q_queue)); 276 bp = cscan_get(&pq->q_queue, remove); 277 KDASSERT(bp != NULL); 278 KDASSERT(&pq->q_queue == bufq_priocscan_selectqueue(q, bp)); 279 280 return bp; 281 } 282 283 static void 284 bufq_priocscan_init(struct bufq_state *bufq) 285 { 286 struct bufq_priocscan *q; 287 int i; 288 289 bufq->bq_get = bufq_priocscan_get; 290 bufq->bq_put = bufq_priocscan_put; 291 bufq->bq_private = malloc(sizeof(struct bufq_priocscan), 292 M_DEVBUF, M_ZERO); 293 294 q = bufq->bq_private; 295 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 296 struct cscan_queue *cq = &q->bq_queue[i].q_queue; 297 298 cscan_init(cq); 299 } 300 } 301
Indexes created Sat Sep 20 22:09:52 GMT 2025