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