1 /* $NetBSD: bufq_priocscan.c,v 1.14 2009/01/19 14:54:28 yamt Exp $ */ 2 3 /*- 4 * Copyright (c)2004,2005,2006,2008,2009 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.14 2009/01/19 14:54:28 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/bufq_impl.h> 37 #include <sys/kmem.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 * be careful: while making these values larger likely 163 * increases the total throughput, it can also increase latencies 164 * for some workloads. 165 */ 166 const int priocscan_burst[] = { 167 64, 16, 4 168 }; 169 170 static void bufq_priocscan_init(struct bufq_state *); 171 static void bufq_priocscan_put(struct bufq_state *, struct buf *); 172 static struct buf *bufq_priocscan_get(struct bufq_state *, int); 173 174 BUFQ_DEFINE(priocscan, 40, bufq_priocscan_init); 175 176 static inline struct cscan_queue *bufq_priocscan_selectqueue( 177 struct bufq_priocscan *, const struct buf *); 178 179 static inline struct cscan_queue * 180 bufq_priocscan_selectqueue(struct bufq_priocscan *q, const struct buf *bp) 181 { 182 static const int priocscan_priomap[] = { 183 [BPRIO_TIMENONCRITICAL] = 2, 184 [BPRIO_TIMELIMITED] = 1, 185 [BPRIO_TIMECRITICAL] = 0 186 }; 187 188 return &q->bq_queue[priocscan_priomap[BIO_GETPRIO(bp)]].q_queue; 189 } 190 191 static void 192 bufq_priocscan_put(struct bufq_state *bufq, struct buf *bp) 193 { 194 struct bufq_priocscan *q = bufq->bq_private; 195 struct cscan_queue *cq; 196 const int sortby = bufq->bq_flags & BUFQ_SORT_MASK; 197 198 cq = bufq_priocscan_selectqueue(q, bp); 199 cscan_put(cq, bp, sortby); 200 } 201 202 static struct buf * 203 bufq_priocscan_get(struct bufq_state *bufq, int remove) 204 { 205 struct bufq_priocscan *q = bufq->bq_private; 206 struct priocscan_queue *pq, *npq; 207 struct priocscan_queue *first; /* first non-empty queue */ 208 const struct priocscan_queue *epq; 209 const struct cscan_queue *cq; 210 struct buf *bp; 211 bool single; /* true if there's only one non-empty queue */ 212 213 pq = &q->bq_queue[0]; 214 epq = pq + PRIOCSCAN_NQUEUE; 215 for (; pq < epq; pq++) { 216 cq = &pq->q_queue; 217 if (!cscan_empty(cq)) 218 break; 219 } 220 if (pq == epq) { 221 /* there's no requests */ 222 return NULL; 223 } 224 225 first = pq; 226 single = true; 227 for (npq = first + 1; npq < epq; npq++) { 228 cq = &npq->q_queue; 229 if (!cscan_empty(cq)) { 230 single = false; 231 if (pq->q_burst > 0) 232 break; 233 pq = npq; 234 } 235 } 236 if (single) { 237 /* 238 * there's only a non-empty queue. just serve it. 239 */ 240 pq = first; 241 } else if (pq->q_burst > 0) { 242 /* 243 * XXX account only by number of requests. is it good enough? 244 */ 245 if (remove) { 246 pq->q_burst--; 247 } 248 } else { 249 /* 250 * no queue was selected due to burst counts 251 */ 252 int i; 253 #ifdef DEBUG 254 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 255 pq = &q->bq_queue[i]; 256 cq = &pq->q_queue; 257 if (!cscan_empty(cq) && pq->q_burst) 258 panic("%s: inconsist", __func__); 259 } 260 #endif /* DEBUG */ 261 262 /* 263 * reset burst counts 264 */ 265 if (remove) { 266 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 267 pq = &q->bq_queue[i]; 268 pq->q_burst = priocscan_burst[i]; 269 } 270 } 271 272 /* 273 * serve first non-empty queue. 274 */ 275 pq = first; 276 } 277 278 KDASSERT(!cscan_empty(&pq->q_queue)); 279 bp = cscan_get(&pq->q_queue, remove); 280 KDASSERT(bp != NULL); 281 KDASSERT(&pq->q_queue == bufq_priocscan_selectqueue(q, bp)); 282 283 return bp; 284 } 285 286 static struct buf * 287 bufq_priocscan_cancel(struct bufq_state *bufq, struct buf *bp) 288 { 289 struct bufq_priocscan * const q = bufq->bq_private; 290 int i, j; 291 292 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 293 struct cscan_queue * const cq = &q->bq_queue[i].q_queue; 294 for (j = 0; j < 2; j++) { 295 struct bqhead * const bqh = &cq->cq_head[j]; 296 struct buf *bq; 297 298 TAILQ_FOREACH(bq, bqh, b_actq) { 299 if (bq == bp) { 300 TAILQ_REMOVE(bqh, bp, b_actq); 301 return bp; 302 } 303 } 304 } 305 } 306 return NULL; 307 } 308 309 static void 310 bufq_priocscan_fini(struct bufq_state *bufq) 311 { 312 313 KASSERT(bufq->bq_private != NULL); 314 kmem_free(bufq->bq_private, sizeof(struct bufq_priocscan)); 315 } 316 317 static void 318 bufq_priocscan_init(struct bufq_state *bufq) 319 { 320 struct bufq_priocscan *q; 321 int i; 322 323 bufq->bq_get = bufq_priocscan_get; 324 bufq->bq_put = bufq_priocscan_put; 325 bufq->bq_cancel = bufq_priocscan_cancel; 326 bufq->bq_fini = bufq_priocscan_fini; 327 bufq->bq_private = kmem_zalloc(sizeof(struct bufq_priocscan), KM_SLEEP); 328 329 q = bufq->bq_private; 330 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 331 struct cscan_queue *cq = &q->bq_queue[i].q_queue; 332 333 cscan_init(cq); 334 } 335 } 336