bufq_readprio.c revision 1.1.2.2
1 1.1.2.2 skrll /* $NetBSD: bufq_readprio.c,v 1.1.2.2 2004/10/19 15:58:02 skrll Exp $ */ 2 1.1.2.2 skrll /* NetBSD: subr_disk.c,v 1.61 2004/09/25 03:30:44 thorpej Exp */ 3 1.1.2.2 skrll 4 1.1.2.2 skrll /*- 5 1.1.2.2 skrll * Copyright (c) 1996, 1997, 1999, 2000 The NetBSD Foundation, Inc. 6 1.1.2.2 skrll * All rights reserved. 7 1.1.2.2 skrll * 8 1.1.2.2 skrll * This code is derived from software contributed to The NetBSD Foundation 9 1.1.2.2 skrll * by Jason R. Thorpe of the Numerical Aerospace Simulation Facility, 10 1.1.2.2 skrll * NASA Ames Research Center. 11 1.1.2.2 skrll * 12 1.1.2.2 skrll * Redistribution and use in source and binary forms, with or without 13 1.1.2.2 skrll * modification, are permitted provided that the following conditions 14 1.1.2.2 skrll * are met: 15 1.1.2.2 skrll * 1. Redistributions of source code must retain the above copyright 16 1.1.2.2 skrll * notice, this list of conditions and the following disclaimer. 17 1.1.2.2 skrll * 2. Redistributions in binary form must reproduce the above copyright 18 1.1.2.2 skrll * notice, this list of conditions and the following disclaimer in the 19 1.1.2.2 skrll * documentation and/or other materials provided with the distribution. 20 1.1.2.2 skrll * 3. All advertising materials mentioning features or use of this software 21 1.1.2.2 skrll * must display the following acknowledgement: 22 1.1.2.2 skrll * This product includes software developed by the NetBSD 23 1.1.2.2 skrll * Foundation, Inc. and its contributors. 24 1.1.2.2 skrll * 4. Neither the name of The NetBSD Foundation nor the names of its 25 1.1.2.2 skrll * contributors may be used to endorse or promote products derived 26 1.1.2.2 skrll * from this software without specific prior written permission. 27 1.1.2.2 skrll * 28 1.1.2.2 skrll * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 29 1.1.2.2 skrll * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 30 1.1.2.2 skrll * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 31 1.1.2.2 skrll * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 32 1.1.2.2 skrll * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 33 1.1.2.2 skrll * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 34 1.1.2.2 skrll * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 35 1.1.2.2 skrll * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 36 1.1.2.2 skrll * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 37 1.1.2.2 skrll * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 38 1.1.2.2 skrll * POSSIBILITY OF SUCH DAMAGE. 39 1.1.2.2 skrll */ 40 1.1.2.2 skrll 41 1.1.2.2 skrll /* 42 1.1.2.2 skrll * Copyright (c) 1982, 1986, 1988, 1993 43 1.1.2.2 skrll * The Regents of the University of California. All rights reserved. 44 1.1.2.2 skrll * (c) UNIX System Laboratories, Inc. 45 1.1.2.2 skrll * All or some portions of this file are derived from material licensed 46 1.1.2.2 skrll * to the University of California by American Telephone and Telegraph 47 1.1.2.2 skrll * Co. or Unix System Laboratories, Inc. and are reproduced herein with 48 1.1.2.2 skrll * the permission of UNIX System Laboratories, Inc. 49 1.1.2.2 skrll * 50 1.1.2.2 skrll * Redistribution and use in source and binary forms, with or without 51 1.1.2.2 skrll * modification, are permitted provided that the following conditions 52 1.1.2.2 skrll * are met: 53 1.1.2.2 skrll * 1. Redistributions of source code must retain the above copyright 54 1.1.2.2 skrll * notice, this list of conditions and the following disclaimer. 55 1.1.2.2 skrll * 2. Redistributions in binary form must reproduce the above copyright 56 1.1.2.2 skrll * notice, this list of conditions and the following disclaimer in the 57 1.1.2.2 skrll * documentation and/or other materials provided with the distribution. 58 1.1.2.2 skrll * 3. Neither the name of the University nor the names of its contributors 59 1.1.2.2 skrll * may be used to endorse or promote products derived from this software 60 1.1.2.2 skrll * without specific prior written permission. 61 1.1.2.2 skrll * 62 1.1.2.2 skrll * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 63 1.1.2.2 skrll * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 64 1.1.2.2 skrll * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 65 1.1.2.2 skrll * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 66 1.1.2.2 skrll * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 67 1.1.2.2 skrll * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 68 1.1.2.2 skrll * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 69 1.1.2.2 skrll * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 70 1.1.2.2 skrll * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 71 1.1.2.2 skrll * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 72 1.1.2.2 skrll * SUCH DAMAGE. 73 1.1.2.2 skrll * 74 1.1.2.2 skrll * @(#)ufs_disksubr.c 8.5 (Berkeley) 1/21/94 75 1.1.2.2 skrll */ 76 1.1.2.2 skrll 77 1.1.2.2 skrll #include <sys/cdefs.h> 78 1.1.2.2 skrll __KERNEL_RCSID(0, "$NetBSD: bufq_readprio.c,v 1.1.2.2 2004/10/19 15:58:02 skrll Exp $"); 79 1.1.2.2 skrll 80 1.1.2.2 skrll #include <sys/param.h> 81 1.1.2.2 skrll #include <sys/systm.h> 82 1.1.2.2 skrll #include <sys/buf.h> 83 1.1.2.2 skrll #include <sys/malloc.h> 84 1.1.2.2 skrll 85 1.1.2.2 skrll /* 86 1.1.2.2 skrll * Seek sort for disks. 87 1.1.2.2 skrll * 88 1.1.2.2 skrll * There are two queues. The first queue holds read requests; the second 89 1.1.2.2 skrll * holds write requests. The read queue is first-come first-served; the 90 1.1.2.2 skrll * write queue is sorted in ascendening block order. 91 1.1.2.2 skrll * The read queue is processed first. After PRIO_READ_BURST consecutive 92 1.1.2.2 skrll * read requests with non-empty write queue PRIO_WRITE_REQ requests from 93 1.1.2.2 skrll * the write queue will be processed. 94 1.1.2.2 skrll */ 95 1.1.2.2 skrll 96 1.1.2.2 skrll #define PRIO_READ_BURST 48 97 1.1.2.2 skrll #define PRIO_WRITE_REQ 16 98 1.1.2.2 skrll 99 1.1.2.2 skrll struct bufq_prio { 100 1.1.2.2 skrll TAILQ_HEAD(, buf) bq_read, bq_write; /* actual list of buffers */ 101 1.1.2.2 skrll struct buf *bq_write_next; /* next request in bq_write */ 102 1.1.2.2 skrll struct buf *bq_next; /* current request */ 103 1.1.2.2 skrll int bq_read_burst; /* # of consecutive reads */ 104 1.1.2.2 skrll }; 105 1.1.2.2 skrll 106 1.1.2.2 skrll static void 107 1.1.2.2 skrll bufq_prio_put(struct bufq_state *bufq, struct buf *bp) 108 1.1.2.2 skrll { 109 1.1.2.2 skrll struct bufq_prio *prio = bufq->bq_private; 110 1.1.2.2 skrll struct buf *bq; 111 1.1.2.2 skrll int sortby; 112 1.1.2.2 skrll 113 1.1.2.2 skrll sortby = bufq->bq_flags & BUFQ_SORT_MASK; 114 1.1.2.2 skrll 115 1.1.2.2 skrll /* 116 1.1.2.2 skrll * If it's a read request append it to the list. 117 1.1.2.2 skrll */ 118 1.1.2.2 skrll if ((bp->b_flags & B_READ) == B_READ) { 119 1.1.2.2 skrll TAILQ_INSERT_TAIL(&prio->bq_read, bp, b_actq); 120 1.1.2.2 skrll return; 121 1.1.2.2 skrll } 122 1.1.2.2 skrll 123 1.1.2.2 skrll bq = TAILQ_FIRST(&prio->bq_write); 124 1.1.2.2 skrll 125 1.1.2.2 skrll /* 126 1.1.2.2 skrll * If the write list is empty, simply append it to the list. 127 1.1.2.2 skrll */ 128 1.1.2.2 skrll if (bq == NULL) { 129 1.1.2.2 skrll TAILQ_INSERT_TAIL(&prio->bq_write, bp, b_actq); 130 1.1.2.2 skrll prio->bq_write_next = bp; 131 1.1.2.2 skrll return; 132 1.1.2.2 skrll } 133 1.1.2.2 skrll 134 1.1.2.2 skrll /* 135 1.1.2.2 skrll * If we lie after the next request, insert after this request. 136 1.1.2.2 skrll */ 137 1.1.2.2 skrll if (buf_inorder(prio->bq_write_next, bp, sortby)) 138 1.1.2.2 skrll bq = prio->bq_write_next; 139 1.1.2.2 skrll 140 1.1.2.2 skrll /* 141 1.1.2.2 skrll * Search for the first request at a larger block number. 142 1.1.2.2 skrll * We go before this request if it exists. 143 1.1.2.2 skrll */ 144 1.1.2.2 skrll while (bq != NULL && buf_inorder(bq, bp, sortby)) 145 1.1.2.2 skrll bq = TAILQ_NEXT(bq, b_actq); 146 1.1.2.2 skrll 147 1.1.2.2 skrll if (bq != NULL) 148 1.1.2.2 skrll TAILQ_INSERT_BEFORE(bq, bp, b_actq); 149 1.1.2.2 skrll else 150 1.1.2.2 skrll TAILQ_INSERT_TAIL(&prio->bq_write, bp, b_actq); 151 1.1.2.2 skrll } 152 1.1.2.2 skrll 153 1.1.2.2 skrll static struct buf * 154 1.1.2.2 skrll bufq_prio_get(struct bufq_state *bufq, int remove) 155 1.1.2.2 skrll { 156 1.1.2.2 skrll struct bufq_prio *prio = bufq->bq_private; 157 1.1.2.2 skrll struct buf *bp; 158 1.1.2.2 skrll 159 1.1.2.2 skrll /* 160 1.1.2.2 skrll * If no current request, get next from the lists. 161 1.1.2.2 skrll */ 162 1.1.2.2 skrll if (prio->bq_next == NULL) { 163 1.1.2.2 skrll /* 164 1.1.2.2 skrll * If at least one list is empty, select the other. 165 1.1.2.2 skrll */ 166 1.1.2.2 skrll if (TAILQ_FIRST(&prio->bq_read) == NULL) { 167 1.1.2.2 skrll prio->bq_next = prio->bq_write_next; 168 1.1.2.2 skrll prio->bq_read_burst = 0; 169 1.1.2.2 skrll } else if (prio->bq_write_next == NULL) { 170 1.1.2.2 skrll prio->bq_next = TAILQ_FIRST(&prio->bq_read); 171 1.1.2.2 skrll prio->bq_read_burst = 0; 172 1.1.2.2 skrll } else { 173 1.1.2.2 skrll /* 174 1.1.2.2 skrll * Both list have requests. Select the read list up 175 1.1.2.2 skrll * to PRIO_READ_BURST times, then select the write 176 1.1.2.2 skrll * list PRIO_WRITE_REQ times. 177 1.1.2.2 skrll */ 178 1.1.2.2 skrll if (prio->bq_read_burst++ < PRIO_READ_BURST) 179 1.1.2.2 skrll prio->bq_next = TAILQ_FIRST(&prio->bq_read); 180 1.1.2.2 skrll else if (prio->bq_read_burst < 181 1.1.2.2 skrll PRIO_READ_BURST + PRIO_WRITE_REQ) 182 1.1.2.2 skrll prio->bq_next = prio->bq_write_next; 183 1.1.2.2 skrll else { 184 1.1.2.2 skrll prio->bq_next = TAILQ_FIRST(&prio->bq_read); 185 1.1.2.2 skrll prio->bq_read_burst = 0; 186 1.1.2.2 skrll } 187 1.1.2.2 skrll } 188 1.1.2.2 skrll } 189 1.1.2.2 skrll 190 1.1.2.2 skrll bp = prio->bq_next; 191 1.1.2.2 skrll 192 1.1.2.2 skrll if (bp != NULL && remove) { 193 1.1.2.2 skrll if ((bp->b_flags & B_READ) == B_READ) 194 1.1.2.2 skrll TAILQ_REMOVE(&prio->bq_read, bp, b_actq); 195 1.1.2.2 skrll else { 196 1.1.2.2 skrll /* 197 1.1.2.2 skrll * Advance the write pointer before removing 198 1.1.2.2 skrll * bp since it is actually prio->bq_write_next. 199 1.1.2.2 skrll */ 200 1.1.2.2 skrll prio->bq_write_next = 201 1.1.2.2 skrll TAILQ_NEXT(prio->bq_write_next, b_actq); 202 1.1.2.2 skrll TAILQ_REMOVE(&prio->bq_write, bp, b_actq); 203 1.1.2.2 skrll if (prio->bq_write_next == NULL) 204 1.1.2.2 skrll prio->bq_write_next = 205 1.1.2.2 skrll TAILQ_FIRST(&prio->bq_write); 206 1.1.2.2 skrll } 207 1.1.2.2 skrll 208 1.1.2.2 skrll prio->bq_next = NULL; 209 1.1.2.2 skrll } 210 1.1.2.2 skrll 211 1.1.2.2 skrll return (bp); 212 1.1.2.2 skrll } 213 1.1.2.2 skrll 214 1.1.2.2 skrll void 215 1.1.2.2 skrll bufq_readprio_init(struct bufq_state *bufq) 216 1.1.2.2 skrll { 217 1.1.2.2 skrll struct bufq_prio *prio; 218 1.1.2.2 skrll 219 1.1.2.2 skrll bufq->bq_get = bufq_prio_get; 220 1.1.2.2 skrll bufq->bq_put = bufq_prio_put; 221 1.1.2.2 skrll MALLOC(bufq->bq_private, struct bufq_prio *, 222 1.1.2.2 skrll sizeof(struct bufq_prio), M_DEVBUF, M_ZERO); 223 1.1.2.2 skrll prio = (struct bufq_prio *)bufq->bq_private; 224 1.1.2.2 skrll TAILQ_INIT(&prio->bq_read); 225 1.1.2.2 skrll TAILQ_INIT(&prio->bq_write); 226 1.1.2.2 skrll } 227 1.1.2.2 skrll 228
Indexes created Tue Sep 30 11:09:46 GMT 2025