1 /* $NetBSD: bufq_priocscan.c,v 1.2 2004/10/28 07:07:46 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.2 2004/10/28 07:07:46 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_put(struct bufq_state *, struct buf *); 167 static struct buf *bufq_priocscan_get(struct bufq_state *, int); 168 static __inline struct cscan_queue *bufq_priocscan_selectqueue( 169 struct bufq_priocscan *, const struct buf *); 170 171 static __inline struct cscan_queue * 172 bufq_priocscan_selectqueue(struct bufq_priocscan *q, const struct buf *bp) 173 { 174 static const int priocscan_priomap[] = { 175 [BPRIO_TIMENONCRITICAL] = 2, 176 [BPRIO_TIMELIMITED] = 1, 177 [BPRIO_TIMECRITICAL] = 0 178 }; 179 180 return &q->bq_queue[priocscan_priomap[BIO_GETPRIO(bp)]].q_queue; 181 } 182 183 static void 184 bufq_priocscan_put(struct bufq_state *bufq, struct buf *bp) 185 { 186 struct bufq_priocscan *q = bufq->bq_private; 187 struct cscan_queue *cq; 188 const int sortby = bufq->bq_flags & BUFQ_SORT_MASK; 189 190 cq = bufq_priocscan_selectqueue(q, bp); 191 cscan_put(cq, bp, sortby); 192 } 193 194 static struct buf * 195 bufq_priocscan_get(struct bufq_state *bufq, int remove) 196 { 197 struct bufq_priocscan *q = bufq->bq_private; 198 struct priocscan_queue *pq, *npq; 199 struct priocscan_queue *first; /* first non-empty queue */ 200 const struct priocscan_queue *epq; 201 const struct cscan_queue *cq; 202 struct buf *bp; 203 boolean_t single; /* true if there's only one non-empty queue */ 204 205 pq = &q->bq_queue[0]; 206 epq = pq + PRIOCSCAN_NQUEUE; 207 for (; pq < epq; pq++) { 208 cq = &pq->q_queue; 209 if (!cscan_empty(cq)) 210 break; 211 } 212 if (pq == epq) { 213 /* there's no requests */ 214 return NULL; 215 } 216 217 first = pq; 218 single = TRUE; 219 for (npq = first + 1; npq < epq; npq++) { 220 cq = &npq->q_queue; 221 if (!cscan_empty(cq)) { 222 single = FALSE; 223 if (pq->q_burst > 0) 224 break; 225 pq = npq; 226 } 227 } 228 if (single) { 229 /* 230 * there's only a non-empty queue. just serve it. 231 */ 232 pq = first; 233 } else if (pq->q_burst > 0) { 234 /* 235 * XXX account only by number of requests. is it good enough? 236 */ 237 pq->q_burst--; 238 } else { 239 /* 240 * no queue was selected due to burst counts 241 */ 242 int i; 243 #ifdef DEBUG 244 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 245 pq = &q->bq_queue[i]; 246 cq = &pq->q_queue; 247 if (!cscan_empty(cq) && pq->q_burst) 248 panic("%s: inconsist", __func__); 249 } 250 #endif /* DEBUG */ 251 252 /* 253 * reset burst counts 254 */ 255 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 256 pq = &q->bq_queue[i]; 257 pq->q_burst = priocscan_burst[i]; 258 } 259 260 /* 261 * serve first non-empty queue. 262 */ 263 pq = first; 264 } 265 266 KDASSERT(!cscan_empty(&pq->q_queue)); 267 bp = cscan_get(&pq->q_queue, remove); 268 KDASSERT(bp != NULL); 269 KDASSERT(&pq->q_queue == bufq_priocscan_selectqueue(q, bp)); 270 271 return bp; 272 } 273 274 void 275 bufq_priocscan_init(struct bufq_state *bufq) 276 { 277 struct bufq_priocscan *q; 278 int i; 279 280 bufq->bq_get = bufq_priocscan_get; 281 bufq->bq_put = bufq_priocscan_put; 282 bufq->bq_private = malloc(sizeof(struct bufq_priocscan), 283 M_DEVBUF, M_ZERO); 284 285 q = bufq->bq_private; 286 for (i = 0; i < PRIOCSCAN_NQUEUE; i++) { 287 struct cscan_queue *cq = &q->bq_queue[i].q_queue; 288 289 cscan_init(cq); 290 } 291 } 292