Home | History | Annotate | Line # | Download | only in uvm
uvm_readahead.c revision 1.3
      1 /*	$NetBSD: uvm_readahead.c,v 1.3 2007/03/12 18:18:39 ad 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.3 2007/03/12 18:18:39 ad 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, IPL_NONE);
     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