blob: 39bf45d4332070a3e28f54e995fbac96add4585f [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * mm/readahead.c - address_space-level file readahead.
3 *
4 * Copyright (C) 2002, Linus Torvalds
5 *
6 * 09Apr2002 akpm@zip.com.au
7 * Initial version.
8 */
9
10#include <linux/kernel.h>
11#include <linux/fs.h>
12#include <linux/mm.h>
13#include <linux/module.h>
14#include <linux/blkdev.h>
15#include <linux/backing-dev.h>
Andrew Morton8bde37f2006-12-10 02:19:40 -080016#include <linux/task_io_accounting_ops.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070017#include <linux/pagevec.h>
18
19void default_unplug_io_fn(struct backing_dev_info *bdi, struct page *page)
20{
21}
22EXPORT_SYMBOL(default_unplug_io_fn);
23
Fengguang Wuf615bfc2007-07-19 01:47:58 -070024/*
25 * Convienent macros for min/max read-ahead pages.
26 * Note that MAX_RA_PAGES is rounded down, while MIN_RA_PAGES is rounded up.
27 * The latter is necessary for systems with large page size(i.e. 64k).
28 */
29#define MAX_RA_PAGES (VM_MAX_READAHEAD*1024 / PAGE_CACHE_SIZE)
30#define MIN_RA_PAGES DIV_ROUND_UP(VM_MIN_READAHEAD*1024, PAGE_CACHE_SIZE)
31
Linus Torvalds1da177e2005-04-16 15:20:36 -070032struct backing_dev_info default_backing_dev_info = {
Fengguang Wuf615bfc2007-07-19 01:47:58 -070033 .ra_pages = MAX_RA_PAGES,
Linus Torvalds1da177e2005-04-16 15:20:36 -070034 .state = 0,
35 .capabilities = BDI_CAP_MAP_COPY,
36 .unplug_io_fn = default_unplug_io_fn,
37};
38EXPORT_SYMBOL_GPL(default_backing_dev_info);
39
40/*
41 * Initialise a struct file's readahead state. Assumes that the caller has
42 * memset *ra to zero.
43 */
44void
45file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
46{
47 ra->ra_pages = mapping->backing_dev_info->ra_pages;
Jan Kara6ce745e2007-05-06 14:49:26 -070048 ra->prev_index = -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070049}
Steven Whitehoused41cc702006-01-30 08:53:33 +000050EXPORT_SYMBOL_GPL(file_ra_state_init);
Linus Torvalds1da177e2005-04-16 15:20:36 -070051
Linus Torvalds1da177e2005-04-16 15:20:36 -070052#define list_to_page(head) (list_entry((head)->prev, struct page, lru))
53
54/**
Randy Dunlapbd40cdd2006-06-25 05:48:08 -070055 * read_cache_pages - populate an address space with some pages & start reads against them
Linus Torvalds1da177e2005-04-16 15:20:36 -070056 * @mapping: the address_space
57 * @pages: The address of a list_head which contains the target pages. These
58 * pages have their ->index populated and are otherwise uninitialised.
59 * @filler: callback routine for filling a single page.
60 * @data: private data for the callback routine.
61 *
62 * Hides the details of the LRU cache etc from the filesystems.
63 */
64int read_cache_pages(struct address_space *mapping, struct list_head *pages,
65 int (*filler)(void *, struct page *), void *data)
66{
67 struct page *page;
68 struct pagevec lru_pvec;
69 int ret = 0;
70
71 pagevec_init(&lru_pvec, 0);
72
73 while (!list_empty(pages)) {
74 page = list_to_page(pages);
75 list_del(&page->lru);
76 if (add_to_page_cache(page, mapping, page->index, GFP_KERNEL)) {
77 page_cache_release(page);
78 continue;
79 }
80 ret = filler(data, page);
81 if (!pagevec_add(&lru_pvec, page))
82 __pagevec_lru_add(&lru_pvec);
83 if (ret) {
OGAWA Hirofumi38da2882006-12-06 20:36:46 -080084 put_pages_list(pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -070085 break;
86 }
Andrew Morton8bde37f2006-12-10 02:19:40 -080087 task_io_account_read(PAGE_CACHE_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -070088 }
89 pagevec_lru_add(&lru_pvec);
90 return ret;
91}
92
93EXPORT_SYMBOL(read_cache_pages);
94
95static int read_pages(struct address_space *mapping, struct file *filp,
96 struct list_head *pages, unsigned nr_pages)
97{
98 unsigned page_idx;
99 struct pagevec lru_pvec;
Zach Brown994fc28c2005-12-15 14:28:17 -0800100 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700101
102 if (mapping->a_ops->readpages) {
103 ret = mapping->a_ops->readpages(filp, mapping, pages, nr_pages);
OGAWA Hirofumi029e3322006-11-02 22:07:06 -0800104 /* Clean up the remaining pages */
105 put_pages_list(pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700106 goto out;
107 }
108
109 pagevec_init(&lru_pvec, 0);
110 for (page_idx = 0; page_idx < nr_pages; page_idx++) {
111 struct page *page = list_to_page(pages);
112 list_del(&page->lru);
113 if (!add_to_page_cache(page, mapping,
114 page->index, GFP_KERNEL)) {
Zach Brown9f1a3cf2006-06-25 05:46:46 -0700115 mapping->a_ops->readpage(filp, page);
116 if (!pagevec_add(&lru_pvec, page))
117 __pagevec_lru_add(&lru_pvec);
118 } else
119 page_cache_release(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700120 }
121 pagevec_lru_add(&lru_pvec);
Zach Brown994fc28c2005-12-15 14:28:17 -0800122 ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700123out:
124 return ret;
125}
126
127/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700128 * do_page_cache_readahead actually reads a chunk of disk. It allocates all
129 * the pages first, then submits them all for I/O. This avoids the very bad
130 * behaviour which would occur if page allocations are causing VM writeback.
131 * We really don't want to intermingle reads and writes like that.
132 *
133 * Returns the number of pages requested, or the maximum amount of I/O allowed.
134 *
135 * do_page_cache_readahead() returns -1 if it encountered request queue
136 * congestion.
137 */
138static int
139__do_page_cache_readahead(struct address_space *mapping, struct file *filp,
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700140 pgoff_t offset, unsigned long nr_to_read,
141 unsigned long lookahead_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142{
143 struct inode *inode = mapping->host;
144 struct page *page;
145 unsigned long end_index; /* The last page we want to read */
146 LIST_HEAD(page_pool);
147 int page_idx;
148 int ret = 0;
149 loff_t isize = i_size_read(inode);
150
151 if (isize == 0)
152 goto out;
153
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700154 end_index = ((isize - 1) >> PAGE_CACHE_SHIFT);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155
156 /*
157 * Preallocate as many pages as we will need.
158 */
159 read_lock_irq(&mapping->tree_lock);
160 for (page_idx = 0; page_idx < nr_to_read; page_idx++) {
Andrew Morton7361f4d2005-11-07 00:59:28 -0800161 pgoff_t page_offset = offset + page_idx;
Fengguang Wuc743d962007-07-19 01:48:04 -0700162
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163 if (page_offset > end_index)
164 break;
165
166 page = radix_tree_lookup(&mapping->page_tree, page_offset);
167 if (page)
168 continue;
169
170 read_unlock_irq(&mapping->tree_lock);
171 page = page_cache_alloc_cold(mapping);
172 read_lock_irq(&mapping->tree_lock);
173 if (!page)
174 break;
175 page->index = page_offset;
176 list_add(&page->lru, &page_pool);
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700177 if (page_idx == nr_to_read - lookahead_size)
178 SetPageReadahead(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700179 ret++;
180 }
181 read_unlock_irq(&mapping->tree_lock);
182
183 /*
184 * Now start the IO. We ignore I/O errors - if the page is not
185 * uptodate then the caller will launch readpage again, and
186 * will then handle the error.
187 */
188 if (ret)
189 read_pages(mapping, filp, &page_pool, ret);
190 BUG_ON(!list_empty(&page_pool));
191out:
192 return ret;
193}
194
195/*
196 * Chunk the readahead into 2 megabyte units, so that we don't pin too much
197 * memory at once.
198 */
199int force_page_cache_readahead(struct address_space *mapping, struct file *filp,
Andrew Morton7361f4d2005-11-07 00:59:28 -0800200 pgoff_t offset, unsigned long nr_to_read)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201{
202 int ret = 0;
203
204 if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages))
205 return -EINVAL;
206
207 while (nr_to_read) {
208 int err;
209
210 unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_CACHE_SIZE;
211
212 if (this_chunk > nr_to_read)
213 this_chunk = nr_to_read;
214 err = __do_page_cache_readahead(mapping, filp,
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700215 offset, this_chunk, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700216 if (err < 0) {
217 ret = err;
218 break;
219 }
220 ret += err;
221 offset += this_chunk;
222 nr_to_read -= this_chunk;
223 }
224 return ret;
225}
226
227/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700228 * This version skips the IO if the queue is read-congested, and will tell the
229 * block layer to abandon the readahead if request allocation would block.
230 *
231 * force_page_cache_readahead() will ignore queue congestion and will block on
232 * request queues.
233 */
234int do_page_cache_readahead(struct address_space *mapping, struct file *filp,
Andrew Morton7361f4d2005-11-07 00:59:28 -0800235 pgoff_t offset, unsigned long nr_to_read)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700236{
237 if (bdi_read_congested(mapping->backing_dev_info))
238 return -1;
239
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700240 return __do_page_cache_readahead(mapping, filp, offset, nr_to_read, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241}
242
243/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700244 * Given a desired number of PAGE_CACHE_SIZE readahead pages, return a
245 * sensible upper limit.
246 */
247unsigned long max_sane_readahead(unsigned long nr)
248{
Christoph Lameter05a04162007-02-10 01:43:05 -0800249 return min(nr, (node_page_state(numa_node_id(), NR_INACTIVE)
250 + node_page_state(numa_node_id(), NR_FREE_PAGES)) / 2);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700251}
Fengguang Wu5ce11102007-07-19 01:47:59 -0700252
253/*
254 * Submit IO for the read-ahead request in file_ra_state.
255 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700256static unsigned long ra_submit(struct file_ra_state *ra,
Fengguang Wu5ce11102007-07-19 01:47:59 -0700257 struct address_space *mapping, struct file *filp)
258{
Fengguang Wu5ce11102007-07-19 01:47:59 -0700259 int actual;
260
Fengguang Wu5ce11102007-07-19 01:47:59 -0700261 actual = __do_page_cache_readahead(mapping, filp,
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700262 ra->start, ra->size, ra->async_size);
Fengguang Wu5ce11102007-07-19 01:47:59 -0700263
264 return actual;
265}
Fengguang Wu122a21d2007-07-19 01:48:01 -0700266
267/*
Fengguang Wuc743d962007-07-19 01:48:04 -0700268 * Set the initial window size, round to next power of 2 and square
269 * for small size, x 4 for medium, and x 2 for large
270 * for 128k (32 page) max ra
271 * 1-8 page = 32k initial, > 8 page = 128k initial
272 */
273static unsigned long get_init_ra_size(unsigned long size, unsigned long max)
274{
275 unsigned long newsize = roundup_pow_of_two(size);
276
277 if (newsize <= max / 32)
278 newsize = newsize * 4;
279 else if (newsize <= max / 4)
280 newsize = newsize * 2;
281 else
282 newsize = max;
283
284 return newsize;
285}
286
287/*
Fengguang Wu122a21d2007-07-19 01:48:01 -0700288 * Get the previous window size, ramp it up, and
289 * return it as the new window size.
290 */
Fengguang Wuc743d962007-07-19 01:48:04 -0700291static unsigned long get_next_ra_size(struct file_ra_state *ra,
Fengguang Wu122a21d2007-07-19 01:48:01 -0700292 unsigned long max)
293{
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700294 unsigned long cur = ra->size;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700295 unsigned long newsize;
296
297 if (cur < max / 16)
Fengguang Wuc743d962007-07-19 01:48:04 -0700298 newsize = 4 * cur;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700299 else
Fengguang Wuc743d962007-07-19 01:48:04 -0700300 newsize = 2 * cur;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700301
302 return min(newsize, max);
303}
304
305/*
306 * On-demand readahead design.
307 *
308 * The fields in struct file_ra_state represent the most-recently-executed
309 * readahead attempt:
310 *
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700311 * |<----- async_size ---------|
312 * |------------------- size -------------------->|
313 * |==================#===========================|
314 * ^start ^page marked with PG_readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700315 *
316 * To overlap application thinking time and disk I/O time, we do
317 * `readahead pipelining': Do not wait until the application consumed all
318 * readahead pages and stalled on the missing page at readahead_index;
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700319 * Instead, submit an asynchronous readahead I/O as soon as there are
320 * only async_size pages left in the readahead window. Normally async_size
321 * will be equal to size, for maximum pipelining.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700322 *
323 * In interleaved sequential reads, concurrent streams on the same fd can
324 * be invalidating each other's readahead state. So we flag the new readahead
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700325 * page at (start+size-async_size) with PG_readahead, and use it as readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700326 * indicator. The flag won't be set on already cached pages, to avoid the
327 * readahead-for-nothing fuss, saving pointless page cache lookups.
328 *
329 * prev_index tracks the last visited page in the _previous_ read request.
330 * It should be maintained by the caller, and will be used for detecting
331 * small random reads. Note that the readahead algorithm checks loosely
332 * for sequential patterns. Hence interleaved reads might be served as
333 * sequential ones.
334 *
335 * There is a special-case: if the first page which the application tries to
336 * read happens to be the first page of the file, it is assumed that a linear
337 * read is about to happen and the window is immediately set to the initial size
338 * based on I/O request size and the max_readahead.
339 *
340 * The code ramps up the readahead size aggressively at first, but slow down as
341 * it approaches max_readhead.
342 */
343
344/*
345 * A minimal readahead algorithm for trivial sequential/random reads.
346 */
347static unsigned long
348ondemand_readahead(struct address_space *mapping,
349 struct file_ra_state *ra, struct file *filp,
Rusty Russellcf914a72007-07-19 01:48:08 -0700350 bool hit_readahead_marker, pgoff_t offset,
Fengguang Wu122a21d2007-07-19 01:48:01 -0700351 unsigned long req_size)
352{
353 unsigned long max; /* max readahead pages */
Fengguang Wu122a21d2007-07-19 01:48:01 -0700354 int sequential;
355
356 max = ra->ra_pages;
357 sequential = (offset - ra->prev_index <= 1UL) || (req_size > max);
358
359 /*
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700360 * It's the expected callback offset, assume sequential access.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700361 * Ramp up sizes, and push forward the readahead window.
362 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700363 if (offset && (offset == (ra->start + ra->size - ra->async_size) ||
364 offset == (ra->start + ra->size))) {
365 ra->start += ra->size;
366 ra->size = get_next_ra_size(ra, max);
367 ra->async_size = ra->size;
368 goto readit;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700369 }
370
371 /*
372 * Standalone, small read.
373 * Read as is, and do not pollute the readahead state.
374 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700375 if (!hit_readahead_marker && !sequential) {
Fengguang Wu122a21d2007-07-19 01:48:01 -0700376 return __do_page_cache_readahead(mapping, filp,
377 offset, req_size, 0);
378 }
379
380 /*
381 * It may be one of
382 * - first read on start of file
383 * - sequential cache miss
384 * - oversize random read
385 * Start readahead for it.
386 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700387 ra->start = offset;
388 ra->size = get_init_ra_size(req_size, max);
389 ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700390
391 /*
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700392 * Hit on a marked page without valid readahead state.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700393 * E.g. interleaved reads.
394 * Not knowing its readahead pos/size, bet on the minimal possible one.
395 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700396 if (hit_readahead_marker) {
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700397 ra->start++;
398 ra->size = get_next_ra_size(ra, max);
Fengguang Wu122a21d2007-07-19 01:48:01 -0700399 }
400
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700401readit:
Fengguang Wu122a21d2007-07-19 01:48:01 -0700402 return ra_submit(ra, mapping, filp);
403}
404
405/**
Rusty Russellcf914a72007-07-19 01:48:08 -0700406 * page_cache_sync_readahead - generic file readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700407 * @mapping: address_space which holds the pagecache and I/O vectors
408 * @ra: file_ra_state which holds the readahead state
409 * @filp: passed on to ->readpage() and ->readpages()
Rusty Russellcf914a72007-07-19 01:48:08 -0700410 * @offset: start offset into @mapping, in pagecache page-sized units
Fengguang Wu122a21d2007-07-19 01:48:01 -0700411 * @req_size: hint: total size of the read which the caller is performing in
Rusty Russellcf914a72007-07-19 01:48:08 -0700412 * pagecache pages
Fengguang Wu122a21d2007-07-19 01:48:01 -0700413 *
Rusty Russellcf914a72007-07-19 01:48:08 -0700414 * page_cache_sync_readahead() should be called when a cache miss happened:
415 * it will submit the read. The readahead logic may decide to piggyback more
416 * pages onto the read request if access patterns suggest it will improve
417 * performance.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700418 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700419void page_cache_sync_readahead(struct address_space *mapping,
420 struct file_ra_state *ra, struct file *filp,
421 pgoff_t offset, unsigned long req_size)
Fengguang Wu122a21d2007-07-19 01:48:01 -0700422{
423 /* no read-ahead */
424 if (!ra->ra_pages)
Rusty Russellcf914a72007-07-19 01:48:08 -0700425 return;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700426
427 /* do read-ahead */
Rusty Russellcf914a72007-07-19 01:48:08 -0700428 ondemand_readahead(mapping, ra, filp, false, offset, req_size);
Fengguang Wu122a21d2007-07-19 01:48:01 -0700429}
Rusty Russellcf914a72007-07-19 01:48:08 -0700430EXPORT_SYMBOL_GPL(page_cache_sync_readahead);
431
432/**
433 * page_cache_async_readahead - file readahead for marked pages
434 * @mapping: address_space which holds the pagecache and I/O vectors
435 * @ra: file_ra_state which holds the readahead state
436 * @filp: passed on to ->readpage() and ->readpages()
437 * @page: the page at @offset which has the PG_readahead flag set
438 * @offset: start offset into @mapping, in pagecache page-sized units
439 * @req_size: hint: total size of the read which the caller is performing in
440 * pagecache pages
441 *
442 * page_cache_async_ondemand() should be called when a page is used which
443 * has the PG_readahead flag: this is a marker to suggest that the application
444 * has used up enough of the readahead window that we should start pulling in
445 * more pages. */
446void
447page_cache_async_readahead(struct address_space *mapping,
448 struct file_ra_state *ra, struct file *filp,
449 struct page *page, pgoff_t offset,
450 unsigned long req_size)
451{
452 /* no read-ahead */
453 if (!ra->ra_pages)
454 return;
455
456 /*
457 * Same bit is used for PG_readahead and PG_reclaim.
458 */
459 if (PageWriteback(page))
460 return;
461
462 ClearPageReadahead(page);
463
464 /*
465 * Defer asynchronous read-ahead on IO congestion.
466 */
467 if (bdi_read_congested(mapping->backing_dev_info))
468 return;
469
470 /* do read-ahead */
471 ondemand_readahead(mapping, ra, filp, true, offset, req_size);
472}
473EXPORT_SYMBOL_GPL(page_cache_async_readahead);