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