blob: 8762e8988972baa01820369ba1fd46d7e727d215 [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
25struct backing_dev_info default_backing_dev_info = {
Fengguang Wu535443f2007-10-16 01:24:36 -070026 .ra_pages = VM_MAX_READAHEAD * 1024 / PAGE_CACHE_SIZE,
Linus Torvalds1da177e2005-04-16 15:20:36 -070027 .state = 0,
28 .capabilities = BDI_CAP_MAP_COPY,
29 .unplug_io_fn = default_unplug_io_fn,
30};
31EXPORT_SYMBOL_GPL(default_backing_dev_info);
32
33/*
34 * Initialise a struct file's readahead state. Assumes that the caller has
35 * memset *ra to zero.
36 */
37void
38file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
39{
40 ra->ra_pages = mapping->backing_dev_info->ra_pages;
Fengguang Wuf4e6b492007-10-16 01:24:33 -070041 ra->prev_pos = -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070042}
Steven Whitehoused41cc702006-01-30 08:53:33 +000043EXPORT_SYMBOL_GPL(file_ra_state_init);
Linus Torvalds1da177e2005-04-16 15:20:36 -070044
Linus Torvalds1da177e2005-04-16 15:20:36 -070045#define list_to_page(head) (list_entry((head)->prev, struct page, lru))
46
47/**
Randy Dunlapbd40cdd2006-06-25 05:48:08 -070048 * read_cache_pages - populate an address space with some pages & start reads against them
Linus Torvalds1da177e2005-04-16 15:20:36 -070049 * @mapping: the address_space
50 * @pages: The address of a list_head which contains the target pages. These
51 * pages have their ->index populated and are otherwise uninitialised.
52 * @filler: callback routine for filling a single page.
53 * @data: private data for the callback routine.
54 *
55 * Hides the details of the LRU cache etc from the filesystems.
56 */
57int read_cache_pages(struct address_space *mapping, struct list_head *pages,
58 int (*filler)(void *, struct page *), void *data)
59{
60 struct page *page;
Linus Torvalds1da177e2005-04-16 15:20:36 -070061 int ret = 0;
62
Linus Torvalds1da177e2005-04-16 15:20:36 -070063 while (!list_empty(pages)) {
64 page = list_to_page(pages);
65 list_del(&page->lru);
Nick Piggineb2be182007-10-16 01:24:57 -070066 if (add_to_page_cache_lru(page, mapping,
67 page->index, GFP_KERNEL)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -070068 page_cache_release(page);
69 continue;
70 }
Nick Piggineb2be182007-10-16 01:24:57 -070071 page_cache_release(page);
72
Linus Torvalds1da177e2005-04-16 15:20:36 -070073 ret = filler(data, page);
Nick Piggineb2be182007-10-16 01:24:57 -070074 if (unlikely(ret)) {
OGAWA Hirofumi38da2882006-12-06 20:36:46 -080075 put_pages_list(pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -070076 break;
77 }
Andrew Morton8bde37f2006-12-10 02:19:40 -080078 task_io_account_read(PAGE_CACHE_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -070079 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070080 return ret;
81}
82
83EXPORT_SYMBOL(read_cache_pages);
84
85static int read_pages(struct address_space *mapping, struct file *filp,
86 struct list_head *pages, unsigned nr_pages)
87{
88 unsigned page_idx;
Zach Brown994fc28c2005-12-15 14:28:17 -080089 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -070090
91 if (mapping->a_ops->readpages) {
92 ret = mapping->a_ops->readpages(filp, mapping, pages, nr_pages);
OGAWA Hirofumi029e3322006-11-02 22:07:06 -080093 /* Clean up the remaining pages */
94 put_pages_list(pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -070095 goto out;
96 }
97
Linus Torvalds1da177e2005-04-16 15:20:36 -070098 for (page_idx = 0; page_idx < nr_pages; page_idx++) {
99 struct page *page = list_to_page(pages);
100 list_del(&page->lru);
Nick Piggineb2be182007-10-16 01:24:57 -0700101 if (!add_to_page_cache_lru(page, mapping,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102 page->index, GFP_KERNEL)) {
Zach Brown9f1a3cf2006-06-25 05:46:46 -0700103 mapping->a_ops->readpage(filp, page);
Nick Piggineb2be182007-10-16 01:24:57 -0700104 }
105 page_cache_release(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700106 }
Zach Brown994fc28c2005-12-15 14:28:17 -0800107 ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108out:
109 return ret;
110}
111
112/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700113 * do_page_cache_readahead actually reads a chunk of disk. It allocates all
114 * the pages first, then submits them all for I/O. This avoids the very bad
115 * behaviour which would occur if page allocations are causing VM writeback.
116 * We really don't want to intermingle reads and writes like that.
117 *
118 * Returns the number of pages requested, or the maximum amount of I/O allowed.
119 *
120 * do_page_cache_readahead() returns -1 if it encountered request queue
121 * congestion.
122 */
123static int
124__do_page_cache_readahead(struct address_space *mapping, struct file *filp,
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700125 pgoff_t offset, unsigned long nr_to_read,
126 unsigned long lookahead_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700127{
128 struct inode *inode = mapping->host;
129 struct page *page;
130 unsigned long end_index; /* The last page we want to read */
131 LIST_HEAD(page_pool);
132 int page_idx;
133 int ret = 0;
134 loff_t isize = i_size_read(inode);
135
136 if (isize == 0)
137 goto out;
138
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700139 end_index = ((isize - 1) >> PAGE_CACHE_SHIFT);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140
141 /*
142 * Preallocate as many pages as we will need.
143 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144 for (page_idx = 0; page_idx < nr_to_read; page_idx++) {
Andrew Morton7361f4d2005-11-07 00:59:28 -0800145 pgoff_t page_offset = offset + page_idx;
Fengguang Wuc743d962007-07-19 01:48:04 -0700146
Linus Torvalds1da177e2005-04-16 15:20:36 -0700147 if (page_offset > end_index)
148 break;
149
Nick Piggin00128182007-10-16 01:24:40 -0700150 rcu_read_lock();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700151 page = radix_tree_lookup(&mapping->page_tree, page_offset);
Nick Piggin00128182007-10-16 01:24:40 -0700152 rcu_read_unlock();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153 if (page)
154 continue;
155
Linus Torvalds1da177e2005-04-16 15:20:36 -0700156 page = page_cache_alloc_cold(mapping);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700157 if (!page)
158 break;
159 page->index = page_offset;
160 list_add(&page->lru, &page_pool);
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700161 if (page_idx == nr_to_read - lookahead_size)
162 SetPageReadahead(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163 ret++;
164 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165
166 /*
167 * Now start the IO. We ignore I/O errors - if the page is not
168 * uptodate then the caller will launch readpage again, and
169 * will then handle the error.
170 */
171 if (ret)
172 read_pages(mapping, filp, &page_pool, ret);
173 BUG_ON(!list_empty(&page_pool));
174out:
175 return ret;
176}
177
178/*
179 * Chunk the readahead into 2 megabyte units, so that we don't pin too much
180 * memory at once.
181 */
182int force_page_cache_readahead(struct address_space *mapping, struct file *filp,
Andrew Morton7361f4d2005-11-07 00:59:28 -0800183 pgoff_t offset, unsigned long nr_to_read)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700184{
185 int ret = 0;
186
187 if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages))
188 return -EINVAL;
189
190 while (nr_to_read) {
191 int err;
192
193 unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_CACHE_SIZE;
194
195 if (this_chunk > nr_to_read)
196 this_chunk = nr_to_read;
197 err = __do_page_cache_readahead(mapping, filp,
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700198 offset, this_chunk, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199 if (err < 0) {
200 ret = err;
201 break;
202 }
203 ret += err;
204 offset += this_chunk;
205 nr_to_read -= this_chunk;
206 }
207 return ret;
208}
209
210/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211 * This version skips the IO if the queue is read-congested, and will tell the
212 * block layer to abandon the readahead if request allocation would block.
213 *
214 * force_page_cache_readahead() will ignore queue congestion and will block on
215 * request queues.
216 */
217int do_page_cache_readahead(struct address_space *mapping, struct file *filp,
Andrew Morton7361f4d2005-11-07 00:59:28 -0800218 pgoff_t offset, unsigned long nr_to_read)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219{
220 if (bdi_read_congested(mapping->backing_dev_info))
221 return -1;
222
Fengguang Wu46fc3e72007-07-19 01:47:57 -0700223 return __do_page_cache_readahead(mapping, filp, offset, nr_to_read, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224}
225
226/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227 * Given a desired number of PAGE_CACHE_SIZE readahead pages, return a
228 * sensible upper limit.
229 */
230unsigned long max_sane_readahead(unsigned long nr)
231{
Christoph Lameter05a04162007-02-10 01:43:05 -0800232 return min(nr, (node_page_state(numa_node_id(), NR_INACTIVE)
233 + node_page_state(numa_node_id(), NR_FREE_PAGES)) / 2);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700234}
Fengguang Wu5ce11102007-07-19 01:47:59 -0700235
Peter Zijlstrae0bf68d2007-10-16 23:25:46 -0700236static int __init readahead_init(void)
237{
238 return bdi_init(&default_backing_dev_info);
239}
240subsys_initcall(readahead_init);
241
Fengguang Wu5ce11102007-07-19 01:47:59 -0700242/*
243 * Submit IO for the read-ahead request in file_ra_state.
244 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700245static unsigned long ra_submit(struct file_ra_state *ra,
Fengguang Wu5ce11102007-07-19 01:47:59 -0700246 struct address_space *mapping, struct file *filp)
247{
Fengguang Wu5ce11102007-07-19 01:47:59 -0700248 int actual;
249
Fengguang Wu5ce11102007-07-19 01:47:59 -0700250 actual = __do_page_cache_readahead(mapping, filp,
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700251 ra->start, ra->size, ra->async_size);
Fengguang Wu5ce11102007-07-19 01:47:59 -0700252
253 return actual;
254}
Fengguang Wu122a21d2007-07-19 01:48:01 -0700255
256/*
Fengguang Wuc743d962007-07-19 01:48:04 -0700257 * Set the initial window size, round to next power of 2 and square
258 * for small size, x 4 for medium, and x 2 for large
259 * for 128k (32 page) max ra
260 * 1-8 page = 32k initial, > 8 page = 128k initial
261 */
262static unsigned long get_init_ra_size(unsigned long size, unsigned long max)
263{
264 unsigned long newsize = roundup_pow_of_two(size);
265
266 if (newsize <= max / 32)
267 newsize = newsize * 4;
268 else if (newsize <= max / 4)
269 newsize = newsize * 2;
270 else
271 newsize = max;
272
273 return newsize;
274}
275
276/*
Fengguang Wu122a21d2007-07-19 01:48:01 -0700277 * Get the previous window size, ramp it up, and
278 * return it as the new window size.
279 */
Fengguang Wuc743d962007-07-19 01:48:04 -0700280static unsigned long get_next_ra_size(struct file_ra_state *ra,
Fengguang Wu122a21d2007-07-19 01:48:01 -0700281 unsigned long max)
282{
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700283 unsigned long cur = ra->size;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700284 unsigned long newsize;
285
286 if (cur < max / 16)
Fengguang Wuc743d962007-07-19 01:48:04 -0700287 newsize = 4 * cur;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700288 else
Fengguang Wuc743d962007-07-19 01:48:04 -0700289 newsize = 2 * cur;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700290
291 return min(newsize, max);
292}
293
294/*
295 * On-demand readahead design.
296 *
297 * The fields in struct file_ra_state represent the most-recently-executed
298 * readahead attempt:
299 *
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700300 * |<----- async_size ---------|
301 * |------------------- size -------------------->|
302 * |==================#===========================|
303 * ^start ^page marked with PG_readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700304 *
305 * To overlap application thinking time and disk I/O time, we do
306 * `readahead pipelining': Do not wait until the application consumed all
307 * readahead pages and stalled on the missing page at readahead_index;
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700308 * Instead, submit an asynchronous readahead I/O as soon as there are
309 * only async_size pages left in the readahead window. Normally async_size
310 * will be equal to size, for maximum pipelining.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700311 *
312 * In interleaved sequential reads, concurrent streams on the same fd can
313 * be invalidating each other's readahead state. So we flag the new readahead
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700314 * page at (start+size-async_size) with PG_readahead, and use it as readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700315 * indicator. The flag won't be set on already cached pages, to avoid the
316 * readahead-for-nothing fuss, saving pointless page cache lookups.
317 *
Fengguang Wuf4e6b492007-10-16 01:24:33 -0700318 * prev_pos tracks the last visited byte in the _previous_ read request.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700319 * It should be maintained by the caller, and will be used for detecting
320 * small random reads. Note that the readahead algorithm checks loosely
321 * for sequential patterns. Hence interleaved reads might be served as
322 * sequential ones.
323 *
324 * There is a special-case: if the first page which the application tries to
325 * read happens to be the first page of the file, it is assumed that a linear
326 * read is about to happen and the window is immediately set to the initial size
327 * based on I/O request size and the max_readahead.
328 *
329 * The code ramps up the readahead size aggressively at first, but slow down as
330 * it approaches max_readhead.
331 */
332
333/*
334 * A minimal readahead algorithm for trivial sequential/random reads.
335 */
336static unsigned long
337ondemand_readahead(struct address_space *mapping,
338 struct file_ra_state *ra, struct file *filp,
Rusty Russellcf914a72007-07-19 01:48:08 -0700339 bool hit_readahead_marker, pgoff_t offset,
Fengguang Wu122a21d2007-07-19 01:48:01 -0700340 unsigned long req_size)
341{
Fengguang Wuf4e6b492007-10-16 01:24:33 -0700342 int max = ra->ra_pages; /* max readahead pages */
343 pgoff_t prev_offset;
344 int sequential;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700345
346 /*
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700347 * It's the expected callback offset, assume sequential access.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700348 * Ramp up sizes, and push forward the readahead window.
349 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700350 if (offset && (offset == (ra->start + ra->size - ra->async_size) ||
351 offset == (ra->start + ra->size))) {
352 ra->start += ra->size;
353 ra->size = get_next_ra_size(ra, max);
354 ra->async_size = ra->size;
355 goto readit;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700356 }
357
Fengguang Wuf4e6b492007-10-16 01:24:33 -0700358 prev_offset = ra->prev_pos >> PAGE_CACHE_SHIFT;
359 sequential = offset - prev_offset <= 1UL || req_size > max;
360
Fengguang Wu122a21d2007-07-19 01:48:01 -0700361 /*
362 * Standalone, small read.
363 * Read as is, and do not pollute the readahead state.
364 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700365 if (!hit_readahead_marker && !sequential) {
Fengguang Wu122a21d2007-07-19 01:48:01 -0700366 return __do_page_cache_readahead(mapping, filp,
367 offset, req_size, 0);
368 }
369
370 /*
Fengguang Wu6b10c6c2007-10-16 01:24:34 -0700371 * Hit a marked page without valid readahead state.
372 * E.g. interleaved reads.
373 * Query the pagecache for async_size, which normally equals to
374 * readahead size. Ramp it up and use it as the new readahead size.
375 */
376 if (hit_readahead_marker) {
377 pgoff_t start;
378
379 read_lock_irq(&mapping->tree_lock);
380 start = radix_tree_next_hole(&mapping->page_tree, offset, max+1);
381 read_unlock_irq(&mapping->tree_lock);
382
383 if (!start || start - offset > max)
384 return 0;
385
386 ra->start = start;
387 ra->size = start - offset; /* old async_size */
388 ra->size = get_next_ra_size(ra, max);
389 ra->async_size = ra->size;
390 goto readit;
391 }
392
393 /*
Fengguang Wu122a21d2007-07-19 01:48:01 -0700394 * It may be one of
395 * - first read on start of file
396 * - sequential cache miss
397 * - oversize random read
398 * Start readahead for it.
399 */
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700400 ra->start = offset;
401 ra->size = get_init_ra_size(req_size, max);
402 ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700403
Fengguang Wuf9acc8c2007-07-19 01:48:08 -0700404readit:
Fengguang Wu122a21d2007-07-19 01:48:01 -0700405 return ra_submit(ra, mapping, filp);
406}
407
408/**
Rusty Russellcf914a72007-07-19 01:48:08 -0700409 * page_cache_sync_readahead - generic file readahead
Fengguang Wu122a21d2007-07-19 01:48:01 -0700410 * @mapping: address_space which holds the pagecache and I/O vectors
411 * @ra: file_ra_state which holds the readahead state
412 * @filp: passed on to ->readpage() and ->readpages()
Rusty Russellcf914a72007-07-19 01:48:08 -0700413 * @offset: start offset into @mapping, in pagecache page-sized units
Fengguang Wu122a21d2007-07-19 01:48:01 -0700414 * @req_size: hint: total size of the read which the caller is performing in
Rusty Russellcf914a72007-07-19 01:48:08 -0700415 * pagecache pages
Fengguang Wu122a21d2007-07-19 01:48:01 -0700416 *
Rusty Russellcf914a72007-07-19 01:48:08 -0700417 * page_cache_sync_readahead() should be called when a cache miss happened:
418 * it will submit the read. The readahead logic may decide to piggyback more
419 * pages onto the read request if access patterns suggest it will improve
420 * performance.
Fengguang Wu122a21d2007-07-19 01:48:01 -0700421 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700422void page_cache_sync_readahead(struct address_space *mapping,
423 struct file_ra_state *ra, struct file *filp,
424 pgoff_t offset, unsigned long req_size)
Fengguang Wu122a21d2007-07-19 01:48:01 -0700425{
426 /* no read-ahead */
427 if (!ra->ra_pages)
Rusty Russellcf914a72007-07-19 01:48:08 -0700428 return;
Fengguang Wu122a21d2007-07-19 01:48:01 -0700429
430 /* do read-ahead */
Rusty Russellcf914a72007-07-19 01:48:08 -0700431 ondemand_readahead(mapping, ra, filp, false, offset, req_size);
Fengguang Wu122a21d2007-07-19 01:48:01 -0700432}
Rusty Russellcf914a72007-07-19 01:48:08 -0700433EXPORT_SYMBOL_GPL(page_cache_sync_readahead);
434
435/**
436 * page_cache_async_readahead - file readahead for marked pages
437 * @mapping: address_space which holds the pagecache and I/O vectors
438 * @ra: file_ra_state which holds the readahead state
439 * @filp: passed on to ->readpage() and ->readpages()
440 * @page: the page at @offset which has the PG_readahead flag set
441 * @offset: start offset into @mapping, in pagecache page-sized units
442 * @req_size: hint: total size of the read which the caller is performing in
443 * pagecache pages
444 *
445 * page_cache_async_ondemand() should be called when a page is used which
Randy Dunlapf7850d92008-03-19 17:01:02 -0700446 * has the PG_readahead flag; this is a marker to suggest that the application
Rusty Russellcf914a72007-07-19 01:48:08 -0700447 * has used up enough of the readahead window that we should start pulling in
Randy Dunlapf7850d92008-03-19 17:01:02 -0700448 * more pages.
449 */
Rusty Russellcf914a72007-07-19 01:48:08 -0700450void
451page_cache_async_readahead(struct address_space *mapping,
452 struct file_ra_state *ra, struct file *filp,
453 struct page *page, pgoff_t offset,
454 unsigned long req_size)
455{
456 /* no read-ahead */
457 if (!ra->ra_pages)
458 return;
459
460 /*
461 * Same bit is used for PG_readahead and PG_reclaim.
462 */
463 if (PageWriteback(page))
464 return;
465
466 ClearPageReadahead(page);
467
468 /*
469 * Defer asynchronous read-ahead on IO congestion.
470 */
471 if (bdi_read_congested(mapping->backing_dev_info))
472 return;
473
474 /* do read-ahead */
475 ondemand_readahead(mapping, ra, filp, true, offset, req_size);
476}
477EXPORT_SYMBOL_GPL(page_cache_async_readahead);