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