uvm_readahead.c revision 1.2 1 /* $NetBSD: uvm_readahead.c,v 1.2 2005/11/29 23:37:59 yamt Exp $ */
2
3 /*-
4 * Copyright (c)2003, 2005 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 /*
30 * uvm_object read-ahead
31 *
32 * TODO:
33 * - tune.
34 * - handle multiple streams.
35 * - find a better way to deal with PGO_LOCKED pager requests.
36 * (currently just ignored)
37 * - consider the amount of memory in the system.
38 * - consider the speed of the underlying device.
39 * - consider filesystem block size / block layout.
40 */
41
42 #include <sys/cdefs.h>
43 __KERNEL_RCSID(0, "$NetBSD: uvm_readahead.c,v 1.2 2005/11/29 23:37:59 yamt Exp $");
44
45 #include <sys/param.h>
46 #include <sys/pool.h>
47
48 #include <uvm/uvm.h>
49 #include <uvm/uvm_readahead.h>
50
51 #if defined(READAHEAD_DEBUG)
52 #define DPRINTF(a) printf a
53 #else /* defined(READAHEAD_DEBUG) */
54 #define DPRINTF(a) /* nothing */
55 #endif /* defined(READAHEAD_DEBUG) */
56
57 /*
58 * uvm_ractx: read-ahead context.
59 */
60
61 struct uvm_ractx {
62 int ra_flags;
63 #define RA_VALID 1
64 off_t ra_winstart; /* window start offset */
65 size_t ra_winsize; /* window size */
66 off_t ra_next; /* next offset to read-ahead */
67 };
68
69 #define RA_WINSIZE_INIT MAXPHYS /* initial window size */
70 #define RA_WINSIZE_MAX (MAXPHYS * 8) /* max window size */
71 #define RA_WINSIZE_SEQENTIAL RA_WINSIZE_MAX /* fixed window size used for
72 SEQUENTIAL hint */
73 #define RA_MINSIZE (MAXPHYS * 2) /* min size to start i/o */
74 #define RA_IOCHUNK MAXPHYS /* read-ahead i/o chunk size */
75
76 static off_t ra_startio(struct uvm_object *, off_t, size_t);
77 static struct uvm_ractx *ra_allocctx(void);
78 static void ra_freectx(struct uvm_ractx *);
79
80 static POOL_INIT(ractx_pool, sizeof(struct uvm_ractx), 0, 0, 0, "ractx",
81 &pool_allocator_nointr);
82
83 static struct uvm_ractx *
84 ra_allocctx(void)
85 {
86
87 return pool_get(&ractx_pool, PR_NOWAIT);
88 }
89
90 static void
91 ra_freectx(struct uvm_ractx *ra)
92 {
93
94 pool_put(&ractx_pool, ra);
95 }
96
97 /*
98 * ra_startio: start i/o for read-ahead.
99 *
100 * => start i/o for each RA_IOCHUNK sized chunk.
101 * => return offset to which we started i/o.
102 */
103
104 static off_t
105 ra_startio(struct uvm_object *uobj, off_t off, size_t sz)
106 {
107 const off_t endoff = off + sz;
108
109 DPRINTF(("%s: uobj=%p, off=%" PRIu64 ", endoff=%" PRIu64 "\n",
110 __func__, uobj, off, endoff));
111 off = trunc_page(off);
112 while (off < endoff) {
113 const size_t chunksize = RA_IOCHUNK;
114 int error;
115 size_t donebytes;
116 int npages;
117 int orignpages;
118 size_t bytelen;
119
120 KASSERT((chunksize & (chunksize - 1)) == 0);
121 KASSERT((off & PAGE_MASK) == 0);
122 bytelen = ((off + chunksize) & -(off_t)chunksize) - off;
123 KASSERT((bytelen & PAGE_MASK) == 0);
124 npages = orignpages = bytelen >> PAGE_SHIFT;
125 KASSERT(npages != 0);
126
127 /*
128 * use UVM_ADV_RANDOM to avoid recursion.
129 */
130
131 simple_lock(&uobj->vmobjlock);
132 error = (*uobj->pgops->pgo_get)(uobj, off, NULL,
133 &npages, 0, VM_PROT_READ, UVM_ADV_RANDOM, 0);
134 DPRINTF(("%s: off=%" PRIu64 ", bytelen=%zu -> %d\n",
135 __func__, off, bytelen, error));
136 if (error != 0 && error != EBUSY) {
137 if (error != EINVAL) { /* maybe past EOF */
138 DPRINTF(("%s: error=%d\n", __func__, error));
139 }
140 break;
141 }
142 KASSERT(orignpages == npages);
143 donebytes = orignpages << PAGE_SHIFT;
144 off += donebytes;
145 }
146
147 return off;
148 }
149
150 /* ------------------------------------------------------------ */
151
152 /*
153 * uvm_ra_allocctx: allocate a context.
154 */
155
156 struct uvm_ractx *
157 uvm_ra_allocctx(void)
158 {
159 struct uvm_ractx *ra;
160
161 ra = ra_allocctx();
162 if (ra != NULL) {
163 ra->ra_flags = 0;
164 }
165
166 return ra;
167 }
168
169 /*
170 * uvm_ra_freectx: free a context.
171 */
172
173 void
174 uvm_ra_freectx(struct uvm_ractx *ra)
175 {
176
177 KASSERT(ra != NULL);
178 ra_freectx(ra);
179 }
180
181 /*
182 * uvm_ra_request: update a read-ahead context and start i/o if appropriate.
183 *
184 * => called when [reqoff, reqoff+reqsize) is requested.
185 */
186
187 void
188 uvm_ra_request(struct uvm_ractx *ra, int advice, struct uvm_object *uobj,
189 off_t reqoff, size_t reqsize)
190 {
191
192 if (ra == NULL || advice == UVM_ADV_RANDOM) {
193 return;
194 }
195
196 /*
197 * XXX needs locking? maybe.
198 * but the worst effect is merely a bad read-ahead.
199 */
200
201 if (advice == UVM_ADV_SEQUENTIAL) {
202
203 /*
204 * always do read-ahead with a large window.
205 */
206
207 if ((ra->ra_flags & RA_VALID) == 0) {
208 ra->ra_winstart = ra->ra_next = 0;
209 ra->ra_flags |= RA_VALID;
210 }
211 if (reqoff < ra->ra_winstart) {
212 ra->ra_next = reqoff;
213 }
214 ra->ra_winsize = RA_WINSIZE_SEQENTIAL;
215 goto do_readahead;
216 }
217
218 /*
219 * a request with UVM_ADV_NORMAL hint. (ie. no hint)
220 *
221 * we keep a sliding window in order to determine:
222 * - if the previous read-ahead was successful or not.
223 * - how many bytes to read-ahead.
224 */
225
226 /*
227 * if it's the first request for this context,
228 * initialize context and return.
229 */
230
231 if ((ra->ra_flags & RA_VALID) == 0) {
232 initialize:
233 ra->ra_winstart = ra->ra_next = reqoff + reqsize;
234 ra->ra_winsize = RA_WINSIZE_INIT;
235 ra->ra_flags |= RA_VALID;
236 goto done;
237 }
238
239 /*
240 * if it isn't in our window,
241 * initialize context and return.
242 * (read-ahead miss)
243 */
244
245 if (reqoff < ra->ra_winstart ||
246 ra->ra_winstart + ra->ra_winsize < reqoff) {
247
248 /*
249 * ... unless we seem to be reading the same chunk repeatedly.
250 *
251 * XXX should have some margin?
252 */
253
254 if (reqoff + reqsize == ra->ra_winstart) {
255 DPRINTF(("%s: %p: same block: off=%" PRIu64
256 ", size=%zd, winstart=%" PRIu64 "\n",
257 __func__, ra, reqoff, reqsize, ra->ra_winstart));
258 goto done;
259 }
260 goto initialize;
261 }
262
263 /*
264 * it's in our window. (read-ahead hit)
265 * - start read-ahead i/o if appropriate.
266 * - advance and enlarge window.
267 */
268
269 do_readahead:
270
271 /*
272 * don't bother to read-ahead behind current request.
273 */
274
275 if (reqoff > ra->ra_next) {
276 ra->ra_next = reqoff;
277 }
278
279 /*
280 * try to make [reqoff, reqoff+ra_winsize) in-core.
281 * note that [reqoff, ra_next) is considered already done.
282 */
283
284 if (reqoff + ra->ra_winsize > ra->ra_next) {
285 off_t raoff = MAX(reqoff, ra->ra_next);
286 size_t rasize = reqoff + ra->ra_winsize - ra->ra_next;
287
288 #if defined(DIAGNOSTIC)
289 if (rasize > RA_WINSIZE_MAX) {
290
291 /*
292 * shouldn't happen as far as we're protected by
293 * kernel_lock.
294 */
295
296 printf("%s: corrupted context", __func__);
297 rasize = RA_WINSIZE_MAX;
298 }
299 #endif /* defined(DIAGNOSTIC) */
300
301 /*
302 * issue read-ahead only if we can start big enough i/o.
303 * otherwise we end up with a stream of small i/o.
304 */
305
306 if (rasize >= RA_MINSIZE) {
307 ra->ra_next = ra_startio(uobj, raoff, rasize);
308 }
309 }
310
311 /*
312 * update window.
313 *
314 * enlarge window by reqsize, so that it grows in a predictable manner
315 * regardless of the size of each read(2).
316 */
317
318 ra->ra_winstart = reqoff + reqsize;
319 ra->ra_winsize = MIN(RA_WINSIZE_MAX, ra->ra_winsize + reqsize);
320
321 done:;
322 }
323