blob: 4a58befbde4a5f157f6c5372d0420ea9c5390e71 [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>
Jens Axboef5ff8422007-09-21 09:19:54 +020018#include <linux/pagemap.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070019
20void default_unplug_io_fn(struct backing_dev_info *bdi, struct page *page)
21{
22}
23EXPORT_SYMBOL(default_unplug_io_fn);
24
Fengguang Wuf615bfc2007-07-19 01:47:58 -070025/*
26 * Convienent macros for min/max read-ahead pages.
27 * Note that MAX_RA_PAGES is rounded down, while MIN_RA_PAGES is rounded up.
28 * The latter is necessary for systems with large page size(i.e. 64k).
29 */
30#define MAX_RA_PAGES (VM_MAX_READAHEAD*1024 / PAGE_CACHE_SIZE)
31#define MIN_RA_PAGES DIV_ROUND_UP(VM_MIN_READAHEAD*1024, PAGE_CACHE_SIZE)
32
Linus Torvalds1da177e2005-04-16 15:20:36 -070033struct backing_dev_info default_backing_dev_info = {
Fengguang Wuf615bfc2007-07-19 01:47:58 -070034 .ra_pages = MAX_RA_PAGES,
Linus Torvalds1da177e2005-04-16 15:20:36 -070035 .state = 0,
36 .capabilities = BDI_CAP_MAP_COPY,
37 .unplug_io_fn = default_unplug_io_fn,
38};
39EXPORT_SYMBOL_GPL(default_backing_dev_info);
40
41/*
42 * Initialise a struct file's readahead state. Assumes that the caller has
43 * memset *ra to zero.
44 */
45void
46file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
47{
48 ra->ra_pages = mapping->backing_dev_info->ra_pages;
Fengguang Wuf4e6b492007-10-16 01:24:33 -070049 ra->prev_pos = -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070050}
Steven Whitehoused41cc702006-01-30 08:53:33 +000051EXPORT_SYMBOL_GPL(file_ra_state_init);
Linus Torvalds1da177e2005-04-16 15:20:36 -070052
Linus Torvalds1da177e2005-04-16 15:20:36 -070053#define list_to_page(head) (list_entry((head)->prev, struct page, lru))
54
55/**
Randy Dunlapbd40cdd2006-06-25 05:48:08 -070056 * read_cache_pages - populate an address space with some pages & start reads against them
Linus Torvalds1da177e2005-04-16 15:20:36 -070057 * @mapping: the address_space
58 * @pages: The address of a list_head which contains the target pages. These
59 * pages have their ->index populated and are otherwise uninitialised.
60 * @filler: callback routine for filling a single page.
61 * @data: private data for the callback routine.
62 *
63 * Hides the details of the LRU cache etc from the filesystems.
64 */
65int read_cache_pages(struct address_space *mapping, struct list_head *pages,
66 int (*filler)(void *, struct page *), void *data)
67{
68 struct page *page;
69 struct pagevec lru_pvec;
70 int ret = 0;
71
72 pagevec_init(&lru_pvec, 0);
73
74 while (!list_empty(pages)) {
75 page = list_to_page(pages);
76 list_del(&page->lru);
77 if (add_to_page_cache(page, mapping, page->index, GFP_KERNEL)) {
78 page_cache_release(page);
79 continue;
80 }
81 ret = filler(data, page);
82 if (!pagevec_add(&lru_pvec, page))
83 __pagevec_lru_add(&lru_pvec);
84 if (ret) {
OGAWA Hirofumi38da2882006-12-06 20:36:46 -080085 put_pages_list(pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -070086 break;
87 }
Andrew Morton8bde37f2006-12-10 02:19:40 -080088 task_io_account_read(PAGE_CACHE_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -070089 }
90 pagevec_lru_add(&lru_pvec);
91 return ret;
92}
93
94EXPORT_SYMBOL(read_cache_pages);
95
96static int read_pages(struct address_space *mapping, struct file *filp,
97 struct list_head *pages, unsigned nr_pages)
98{
99 unsigned page_idx;
100 struct pagevec lru_pvec;
Zach Brown994fc28c2005-12-15 14:28:17 -0800101 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102
103 if (mapping->a_ops->readpages) {
104 ret = mapping->a_ops->readpages(filp, mapping, pages, nr_pages);
OGAWA Hirofumi029e3322006-11-02 22:07:06 -0800105 /* Clean up the remaining pages */
106 put_pages_list(pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700107 goto out;
108 }
109
110 pagevec_init(&lru_pvec, 0);
111 for (page_idx = 0; page_idx < nr_pages; page_idx++) {
112 struct page *page = list_to_page(pages);
113 list_del(&page->lru);
114 if (!add_to_page_cache(page, mapping,
115 page->index, GFP_KERNEL)) {
Zach Brown9f1a3cf2006-06-25 05:46:46 -0700116 mapping->a_ops->readpage(filp, page);
117 if (!pagevec_add(&lru_pvec, page))
118 __pagevec_lru_add(&lru_pvec);
119 } else
120 page_cache_release(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 }
122 pagevec_lru_add(&lru_pvec);
Zach Brown994fc28c2005-12-15 14:28:17 -0800123 ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700124out:
125 return ret;
126}
127
128/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700129 * do_page_cache_readahead actually reads a chunk of disk. It allocates all
130 * the pages first, then submits them all for I/O. This avoids the very bad
131 * behaviour which would occur if page allocations are causing VM writeback.
132 * We really don't want to intermingle reads and writes like that.
133 *
134 * Returns the number of pages requested, or the maximum amount of I/O allowed.
135 *
136 * do_page_cache_readahead() returns -1 if it encountered request queue
137 * congestion.
138 */
139static int
140__do_page_cache_readahead(struct address_space *mapping, struct file *filp,
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700141 pgoff_t offset, unsigned long nr_to_read,
142 unsigned long lookahead_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143{
144 struct inode *inode = mapping->host;
145 struct page *page;
146 unsigned long end_index; /* The last page we want to read */
147 LIST_HEAD(page_pool);
148 int page_idx;
149 int ret = 0;
150 loff_t isize = i_size_read(inode);
151
152 if (isize == 0)
153 goto out;
154
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700155 end_index = ((isize - 1) >> PAGE_CACHE_SHIFT);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700156
157 /*
158 * Preallocate as many pages as we will need.
159 */
160 read_lock_irq(&mapping->tree_lock);
161 for (page_idx = 0; page_idx < nr_to_read; page_idx++) {
Andrew Morton7361f4d2005-11-07 00:59:28 -0800162 pgoff_t page_offset = offset + page_idx;
Fengguang Wuc743d962007-07-19 01:48:04 -0700163
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164 if (page_offset > end_index)
165 break;
166
167 page = radix_tree_lookup(&mapping->page_tree, page_offset);
168 if (page)
169 continue;
170
171 read_unlock_irq(&mapping->tree_lock);
172 page = page_cache_alloc_cold(mapping);
173 read_lock_irq(&mapping->tree_lock);
174 if (!page)
175 break;
176 page->index = page_offset;
177 list_add(&page->lru, &page_pool);
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700178 if (page_idx == nr_to_read - lookahead_size)
179 SetPageReadahead(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180 ret++;
181 }
182 read_unlock_irq(&mapping->tree_lock);
183
184 /*
185 * Now start the IO. We ignore I/O errors - if the page is not
186 * uptodate then the caller will launch readpage again, and
187 * will then handle the error.
188 */
189 if (ret)
190 read_pages(mapping, filp, &page_pool, ret);
191 BUG_ON(!list_empty(&page_pool));
192out:
193 return ret;
194}
195
196/*
197 * Chunk the readahead into 2 megabyte units, so that we don't pin too much
198 * memory at once.
199 */
200int force_page_cache_readahead(struct address_space *mapping, struct file *filp,
Andrew Morton7361f4d2005-11-07 00:59:28 -0800201 pgoff_t offset, unsigned long nr_to_read)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700202{
203 int ret = 0;
204
205 if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages))
206 return -EINVAL;
207
208 while (nr_to_read) {
209 int err;
210
211 unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_CACHE_SIZE;
212
213 if (this_chunk > nr_to_read)
214 this_chunk = nr_to_read;
215 err = __do_page_cache_readahead(mapping, filp,
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700216 offset, this_chunk, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700217 if (err < 0) {
218 ret = err;
219 break;
220 }
221 ret += err;
222 offset += this_chunk;
223 nr_to_read -= this_chunk;
224 }
225 return ret;
226}
227
228/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 * This version skips the IO if the queue is read-congested, and will tell the
230 * block layer to abandon the readahead if request allocation would block.
231 *
232 * force_page_cache_readahead() will ignore queue congestion and will block on
233 * request queues.
234 */
235int do_page_cache_readahead(struct address_space *mapping, struct file *filp,
Andrew Morton7361f4d2005-11-07 00:59:28 -0800236 pgoff_t offset, unsigned long nr_to_read)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700237{
238 if (bdi_read_congested(mapping->backing_dev_info))
239 return -1;
240
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700241 return __do_page_cache_readahead(mapping, filp, offset, nr_to_read, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700242}
243
244/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700245 * Given a desired number of PAGE_CACHE_SIZE readahead pages, return a
246 * sensible upper limit.
247 */
248unsigned long max_sane_readahead(unsigned long nr)
249{
Christoph Lameter05a04162007-02-10 01:43:05 -0800250 return min(nr, (node_page_state(numa_node_id(), NR_INACTIVE)
251 + node_page_state(numa_node_id(), NR_FREE_PAGES)) / 2);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252}
Fengguang Wu5ce11102007-07-19 01:47:59 -0700253
254/*
255 * Submit IO for the read-ahead request in file_ra_state.
256 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700257static unsigned long ra_submit(struct file_ra_state *ra,
Fengguang Wu5ce11102007-07-19 01:47:59 -0700258 struct address_space *mapping, struct file *filp)
259{
Fengguang Wu5ce11102007-07-19 01:47:59 -0700260 int actual;
261
Fengguang Wu5ce11102007-07-19 01:47:59 -0700262 actual = __do_page_cache_readahead(mapping, filp,
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700263 ra->start, ra->size, ra->async_size);
Fengguang Wu5ce11102007-07-19 01:47:59 -0700264
265 return actual;
266}
Fengguang Wu122a21d2007-07-19 01:48:01 -0700267
268/*
Fengguang Wuc743d962007-07-19 01:48:04 -0700269 * Set the initial window size, round to next power of 2 and square
270 * for small size, x 4 for medium, and x 2 for large
271 * for 128k (32 page) max ra
272 * 1-8 page = 32k initial, > 8 page = 128k initial
273 */
274static unsigned long get_init_ra_size(unsigned long size, unsigned long max)
275{
276 unsigned long newsize = roundup_pow_of_two(size);
277
278 if (newsize <= max / 32)
279 newsize = newsize * 4;
280 else if (newsize <= max / 4)
281 newsize = newsize * 2;
282 else
283 newsize = max;
284
285 return newsize;
286}
287
288/*
Fengguang Wu122a21d2007-07-19 01:48:01 -0700289 * Get the previous window size, ramp it up, and
290 * return it as the new window size.
291 */
Fengguang Wuc743d962007-07-19 01:48:04 -0700292static unsigned long get_next_ra_size(struct file_ra_state *ra,
Fengguang Wu122a21d2007-07-19 01:48:01 -0700293 unsigned long max)
294{
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700295 unsigned long cur = ra->size;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700296 unsigned long newsize;
297
298 if (cur < max / 16)
Fengguang Wuc743d962007-07-19 01:48:04 -0700299 newsize = 4 * cur;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700300 else
Fengguang Wuc743d962007-07-19 01:48:04 -0700301 newsize = 2 * cur;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700302
303 return min(newsize, max);
304}
305
306/*
307 * On-demand readahead design.
308 *
309 * The fields in struct file_ra_state represent the most-recently-executed
310 * readahead attempt:
311 *
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700312 * |<----- async_size ---------|
313 * |------------------- size -------------------->|
314 * |==================#===========================|
315 * ^start ^page marked with PG_readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700316 *
317 * To overlap application thinking time and disk I/O time, we do
318 * `readahead pipelining': Do not wait until the application consumed all
319 * readahead pages and stalled on the missing page at readahead_index;
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700320 * Instead, submit an asynchronous readahead I/O as soon as there are
321 * only async_size pages left in the readahead window. Normally async_size
322 * will be equal to size, for maximum pipelining.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700323 *
324 * In interleaved sequential reads, concurrent streams on the same fd can
325 * be invalidating each other's readahead state. So we flag the new readahead
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700326 * page at (start+size-async_size) with PG_readahead, and use it as readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700327 * indicator. The flag won't be set on already cached pages, to avoid the
328 * readahead-for-nothing fuss, saving pointless page cache lookups.
329 *
Fengguang Wuf4e6b492007-10-16 01:24:33 -0700330 * prev_pos tracks the last visited byte in the _previous_ read request.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700331 * It should be maintained by the caller, and will be used for detecting
332 * small random reads. Note that the readahead algorithm checks loosely
333 * for sequential patterns. Hence interleaved reads might be served as
334 * sequential ones.
335 *
336 * There is a special-case: if the first page which the application tries to
337 * read happens to be the first page of the file, it is assumed that a linear
338 * read is about to happen and the window is immediately set to the initial size
339 * based on I/O request size and the max_readahead.
340 *
341 * The code ramps up the readahead size aggressively at first, but slow down as
342 * it approaches max_readhead.
343 */
344
345/*
346 * A minimal readahead algorithm for trivial sequential/random reads.
347 */
348static unsigned long
349ondemand_readahead(struct address_space *mapping,
350 struct file_ra_state *ra, struct file *filp,
Rusty Russellcf914a72007-07-19 01:48:08 -0700351 bool hit_readahead_marker, pgoff_t offset,
Fengguang Wu122a21d2007-07-19 01:48:01 -0700352 unsigned long req_size)
353{
Fengguang Wuf4e6b492007-10-16 01:24:33 -0700354 int max = ra->ra_pages; /* max readahead pages */
355 pgoff_t prev_offset;
356 int sequential;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700357
358 /*
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700359 * It's the expected callback offset, assume sequential access.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700360 * Ramp up sizes, and push forward the readahead window.
361 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700362 if (offset && (offset == (ra->start + ra->size - ra->async_size) ||
363 offset == (ra->start + ra->size))) {
364 ra->start += ra->size;
365 ra->size = get_next_ra_size(ra, max);
366 ra->async_size = ra->size;
367 goto readit;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700368 }
369
Fengguang Wuf4e6b492007-10-16 01:24:33 -0700370 prev_offset = ra->prev_pos >> PAGE_CACHE_SHIFT;
371 sequential = offset - prev_offset <= 1UL || req_size > max;
372
Fengguang Wu122a21d2007-07-19 01:48:01 -0700373 /*
374 * Standalone, small read.
375 * Read as is, and do not pollute the readahead state.
376 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700377 if (!hit_readahead_marker && !sequential) {
Fengguang Wu122a21d2007-07-19 01:48:01 -0700378 return __do_page_cache_readahead(mapping, filp,
379 offset, req_size, 0);
380 }
381
382 /*
383 * It may be one of
384 * - first read on start of file
385 * - sequential cache miss
386 * - oversize random read
387 * Start readahead for it.
388 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700389 ra->start = offset;
390 ra->size = get_init_ra_size(req_size, max);
391 ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700392
393 /*
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700394 * Hit on a marked page without valid readahead state.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700395 * E.g. interleaved reads.
396 * Not knowing its readahead pos/size, bet on the minimal possible one.
397 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700398 if (hit_readahead_marker) {
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700399 ra->start++;
400 ra->size = get_next_ra_size(ra, max);
Fengguang Wu122a21d2007-07-19 01:48:01 -0700401 }
402
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700403readit:
Fengguang Wu122a21d2007-07-19 01:48:01 -0700404 return ra_submit(ra, mapping, filp);
405}
406
407/**
Rusty Russellcf914a72007-07-19 01:48:08 -0700408 * page_cache_sync_readahead - generic file readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700409 * @mapping: address_space which holds the pagecache and I/O vectors
410 * @ra: file_ra_state which holds the readahead state
411 * @filp: passed on to ->readpage() and ->readpages()
Rusty Russellcf914a72007-07-19 01:48:08 -0700412 * @offset: start offset into @mapping, in pagecache page-sized units
Fengguang Wu122a21d2007-07-19 01:48:01 -0700413 * @req_size: hint: total size of the read which the caller is performing in
Rusty Russellcf914a72007-07-19 01:48:08 -0700414 * pagecache pages
Fengguang Wu122a21d2007-07-19 01:48:01 -0700415 *
Rusty Russellcf914a72007-07-19 01:48:08 -0700416 * page_cache_sync_readahead() should be called when a cache miss happened:
417 * it will submit the read. The readahead logic may decide to piggyback more
418 * pages onto the read request if access patterns suggest it will improve
419 * performance.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700420 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700421void page_cache_sync_readahead(struct address_space *mapping,
422 struct file_ra_state *ra, struct file *filp,
423 pgoff_t offset, unsigned long req_size)
Fengguang Wu122a21d2007-07-19 01:48:01 -0700424{
425 /* no read-ahead */
426 if (!ra->ra_pages)
Rusty Russellcf914a72007-07-19 01:48:08 -0700427 return;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700428
429 /* do read-ahead */
Rusty Russellcf914a72007-07-19 01:48:08 -0700430 ondemand_readahead(mapping, ra, filp, false, offset, req_size);
Fengguang Wu122a21d2007-07-19 01:48:01 -0700431}
Rusty Russellcf914a72007-07-19 01:48:08 -0700432EXPORT_SYMBOL_GPL(page_cache_sync_readahead);
433
434/**
435 * page_cache_async_readahead - file readahead for marked pages
436 * @mapping: address_space which holds the pagecache and I/O vectors
437 * @ra: file_ra_state which holds the readahead state
438 * @filp: passed on to ->readpage() and ->readpages()
439 * @page: the page at @offset which has the PG_readahead flag set
440 * @offset: start offset into @mapping, in pagecache page-sized units
441 * @req_size: hint: total size of the read which the caller is performing in
442 * pagecache pages
443 *
444 * page_cache_async_ondemand() should be called when a page is used which
445 * has the PG_readahead flag: this is a marker to suggest that the application
446 * has used up enough of the readahead window that we should start pulling in
447 * more pages. */
448void
449page_cache_async_readahead(struct address_space *mapping,
450 struct file_ra_state *ra, struct file *filp,
451 struct page *page, pgoff_t offset,
452 unsigned long req_size)
453{
454 /* no read-ahead */
455 if (!ra->ra_pages)
456 return;
457
458 /*
459 * Same bit is used for PG_readahead and PG_reclaim.
460 */
461 if (PageWriteback(page))
462 return;
463
464 ClearPageReadahead(page);
465
466 /*
467 * Defer asynchronous read-ahead on IO congestion.
468 */
469 if (bdi_read_congested(mapping->backing_dev_info))
470 return;
471
472 /* do read-ahead */
473 ondemand_readahead(mapping, ra, filp, true, offset, req_size);
474}
475EXPORT_SYMBOL_GPL(page_cache_async_readahead);