Root/mm/readahead.c

1/*
2 * mm/readahead.c - address_space-level file readahead.
3 *
4 * Copyright (C) 2002, Linus Torvalds
5 *
6 * 09Apr2002 Andrew Morton
7 * Initial version.
8 */
9
10#include <linux/kernel.h>
11#include <linux/fs.h>
12#include <linux/gfp.h>
13#include <linux/mm.h>
14#include <linux/export.h>
15#include <linux/blkdev.h>
16#include <linux/backing-dev.h>
17#include <linux/task_io_accounting_ops.h>
18#include <linux/pagevec.h>
19#include <linux/pagemap.h>
20#include <linux/syscalls.h>
21#include <linux/file.h>
22
23/*
24 * Initialise a struct file's readahead state. Assumes that the caller has
25 * memset *ra to zero.
26 */
27void
28file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
29{
30    ra->ra_pages = mapping->backing_dev_info->ra_pages;
31    ra->prev_pos = -1;
32}
33EXPORT_SYMBOL_GPL(file_ra_state_init);
34
35#define list_to_page(head) (list_entry((head)->prev, struct page, lru))
36
37/*
38 * see if a page needs releasing upon read_cache_pages() failure
39 * - the caller of read_cache_pages() may have set PG_private or PG_fscache
40 * before calling, such as the NFS fs marking pages that are cached locally
41 * on disk, thus we need to give the fs a chance to clean up in the event of
42 * an error
43 */
44static void read_cache_pages_invalidate_page(struct address_space *mapping,
45                         struct page *page)
46{
47    if (page_has_private(page)) {
48        if (!trylock_page(page))
49            BUG();
50        page->mapping = mapping;
51        do_invalidatepage(page, 0);
52        page->mapping = NULL;
53        unlock_page(page);
54    }
55    page_cache_release(page);
56}
57
58/*
59 * release a list of pages, invalidating them first if need be
60 */
61static void read_cache_pages_invalidate_pages(struct address_space *mapping,
62                          struct list_head *pages)
63{
64    struct page *victim;
65
66    while (!list_empty(pages)) {
67        victim = list_to_page(pages);
68        list_del(&victim->lru);
69        read_cache_pages_invalidate_page(mapping, victim);
70    }
71}
72
73/**
74 * read_cache_pages - populate an address space with some pages & start reads against them
75 * @mapping: the address_space
76 * @pages: The address of a list_head which contains the target pages. These
77 * pages have their ->index populated and are otherwise uninitialised.
78 * @filler: callback routine for filling a single page.
79 * @data: private data for the callback routine.
80 *
81 * Hides the details of the LRU cache etc from the filesystems.
82 */
83int read_cache_pages(struct address_space *mapping, struct list_head *pages,
84            int (*filler)(void *, struct page *), void *data)
85{
86    struct page *page;
87    int ret = 0;
88
89    while (!list_empty(pages)) {
90        page = list_to_page(pages);
91        list_del(&page->lru);
92        if (add_to_page_cache_lru(page, mapping,
93                    page->index, GFP_KERNEL)) {
94            read_cache_pages_invalidate_page(mapping, page);
95            continue;
96        }
97        page_cache_release(page);
98
99        ret = filler(data, page);
100        if (unlikely(ret)) {
101            read_cache_pages_invalidate_pages(mapping, pages);
102            break;
103        }
104        task_io_account_read(PAGE_CACHE_SIZE);
105    }
106    return ret;
107}
108
109EXPORT_SYMBOL(read_cache_pages);
110
111static int read_pages(struct address_space *mapping, struct file *filp,
112        struct list_head *pages, unsigned nr_pages)
113{
114    struct blk_plug plug;
115    unsigned page_idx;
116    int ret;
117
118    blk_start_plug(&plug);
119
120    if (mapping->a_ops->readpages) {
121        ret = mapping->a_ops->readpages(filp, mapping, pages, nr_pages);
122        /* Clean up the remaining pages */
123        put_pages_list(pages);
124        goto out;
125    }
126
127    for (page_idx = 0; page_idx < nr_pages; page_idx++) {
128        struct page *page = list_to_page(pages);
129        list_del(&page->lru);
130        if (!add_to_page_cache_lru(page, mapping,
131                    page->index, GFP_KERNEL)) {
132            mapping->a_ops->readpage(filp, page);
133        }
134        page_cache_release(page);
135    }
136    ret = 0;
137
138out:
139    blk_finish_plug(&plug);
140
141    return ret;
142}
143
144/*
145 * __do_page_cache_readahead() actually reads a chunk of disk. It allocates all
146 * the pages first, then submits them all for I/O. This avoids the very bad
147 * behaviour which would occur if page allocations are causing VM writeback.
148 * We really don't want to intermingle reads and writes like that.
149 *
150 * Returns the number of pages requested, or the maximum amount of I/O allowed.
151 */
152static int
153__do_page_cache_readahead(struct address_space *mapping, struct file *filp,
154            pgoff_t offset, unsigned long nr_to_read,
155            unsigned long lookahead_size)
156{
157    struct inode *inode = mapping->host;
158    struct page *page;
159    unsigned long end_index; /* The last page we want to read */
160    LIST_HEAD(page_pool);
161    int page_idx;
162    int ret = 0;
163    loff_t isize = i_size_read(inode);
164
165    if (isize == 0)
166        goto out;
167
168    end_index = ((isize - 1) >> PAGE_CACHE_SHIFT);
169
170    /*
171     * Preallocate as many pages as we will need.
172     */
173    for (page_idx = 0; page_idx < nr_to_read; page_idx++) {
174        pgoff_t page_offset = offset + page_idx;
175
176        if (page_offset > end_index)
177            break;
178
179        rcu_read_lock();
180        page = radix_tree_lookup(&mapping->page_tree, page_offset);
181        rcu_read_unlock();
182        if (page)
183            continue;
184
185        page = page_cache_alloc_readahead(mapping);
186        if (!page)
187            break;
188        page->index = page_offset;
189        list_add(&page->lru, &page_pool);
190        if (page_idx == nr_to_read - lookahead_size)
191            SetPageReadahead(page);
192        ret++;
193    }
194
195    /*
196     * Now start the IO. We ignore I/O errors - if the page is not
197     * uptodate then the caller will launch readpage again, and
198     * will then handle the error.
199     */
200    if (ret)
201        read_pages(mapping, filp, &page_pool, ret);
202    BUG_ON(!list_empty(&page_pool));
203out:
204    return ret;
205}
206
207/*
208 * Chunk the readahead into 2 megabyte units, so that we don't pin too much
209 * memory at once.
210 */
211int force_page_cache_readahead(struct address_space *mapping, struct file *filp,
212        pgoff_t offset, unsigned long nr_to_read)
213{
214    int ret = 0;
215
216    if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages))
217        return -EINVAL;
218
219    nr_to_read = max_sane_readahead(nr_to_read);
220    while (nr_to_read) {
221        int err;
222
223        unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_CACHE_SIZE;
224
225        if (this_chunk > nr_to_read)
226            this_chunk = nr_to_read;
227        err = __do_page_cache_readahead(mapping, filp,
228                        offset, this_chunk, 0);
229        if (err < 0) {
230            ret = err;
231            break;
232        }
233        ret += err;
234        offset += this_chunk;
235        nr_to_read -= this_chunk;
236    }
237    return ret;
238}
239
240/*
241 * Given a desired number of PAGE_CACHE_SIZE readahead pages, return a
242 * sensible upper limit.
243 */
244unsigned long max_sane_readahead(unsigned long nr)
245{
246    return min(nr, (node_page_state(numa_node_id(), NR_INACTIVE_FILE)
247        + node_page_state(numa_node_id(), NR_FREE_PAGES)) / 2);
248}
249
250/*
251 * Submit IO for the read-ahead request in file_ra_state.
252 */
253unsigned long ra_submit(struct file_ra_state *ra,
254               struct address_space *mapping, struct file *filp)
255{
256    int actual;
257
258    actual = __do_page_cache_readahead(mapping, filp,
259                    ra->start, ra->size, ra->async_size);
260
261    return actual;
262}
263
264/*
265 * Set the initial window size, round to next power of 2 and square
266 * for small size, x 4 for medium, and x 2 for large
267 * for 128k (32 page) max ra
268 * 1-8 page = 32k initial, > 8 page = 128k initial
269 */
270static unsigned long get_init_ra_size(unsigned long size, unsigned long max)
271{
272    unsigned long newsize = roundup_pow_of_two(size);
273
274    if (newsize <= max / 32)
275        newsize = newsize * 4;
276    else if (newsize <= max / 4)
277        newsize = newsize * 2;
278    else
279        newsize = max;
280
281    return newsize;
282}
283
284/*
285 * Get the previous window size, ramp it up, and
286 * return it as the new window size.
287 */
288static unsigned long get_next_ra_size(struct file_ra_state *ra,
289                        unsigned long max)
290{
291    unsigned long cur = ra->size;
292    unsigned long newsize;
293
294    if (cur < max / 16)
295        newsize = 4 * cur;
296    else
297        newsize = 2 * cur;
298
299    return min(newsize, max);
300}
301
302/*
303 * On-demand readahead design.
304 *
305 * The fields in struct file_ra_state represent the most-recently-executed
306 * readahead attempt:
307 *
308 * |<----- async_size ---------|
309 * |------------------- size -------------------->|
310 * |==================#===========================|
311 * ^start ^page marked with PG_readahead
312 *
313 * To overlap application thinking time and disk I/O time, we do
314 * `readahead pipelining': Do not wait until the application consumed all
315 * readahead pages and stalled on the missing page at readahead_index;
316 * Instead, submit an asynchronous readahead I/O as soon as there are
317 * only async_size pages left in the readahead window. Normally async_size
318 * will be equal to size, for maximum pipelining.
319 *
320 * In interleaved sequential reads, concurrent streams on the same fd can
321 * be invalidating each other's readahead state. So we flag the new readahead
322 * page at (start+size-async_size) with PG_readahead, and use it as readahead
323 * indicator. The flag won't be set on already cached pages, to avoid the
324 * readahead-for-nothing fuss, saving pointless page cache lookups.
325 *
326 * prev_pos tracks the last visited byte in the _previous_ read request.
327 * It should be maintained by the caller, and will be used for detecting
328 * small random reads. Note that the readahead algorithm checks loosely
329 * for sequential patterns. Hence interleaved reads might be served as
330 * sequential ones.
331 *
332 * There is a special-case: if the first page which the application tries to
333 * read happens to be the first page of the file, it is assumed that a linear
334 * read is about to happen and the window is immediately set to the initial size
335 * based on I/O request size and the max_readahead.
336 *
337 * The code ramps up the readahead size aggressively at first, but slow down as
338 * it approaches max_readhead.
339 */
340
341/*
342 * Count contiguously cached pages from @offset-1 to @offset-@max,
343 * this count is a conservative estimation of
344 * - length of the sequential read sequence, or
345 * - thrashing threshold in memory tight systems
346 */
347static pgoff_t count_history_pages(struct address_space *mapping,
348                   struct file_ra_state *ra,
349                   pgoff_t offset, unsigned long max)
350{
351    pgoff_t head;
352
353    rcu_read_lock();
354    head = radix_tree_prev_hole(&mapping->page_tree, offset - 1, max);
355    rcu_read_unlock();
356
357    return offset - 1 - head;
358}
359
360/*
361 * page cache context based read-ahead
362 */
363static int try_context_readahead(struct address_space *mapping,
364                 struct file_ra_state *ra,
365                 pgoff_t offset,
366                 unsigned long req_size,
367                 unsigned long max)
368{
369    pgoff_t size;
370
371    size = count_history_pages(mapping, ra, offset, max);
372
373    /*
374     * no history pages:
375     * it could be a random read
376     */
377    if (!size)
378        return 0;
379
380    /*
381     * starts from beginning of file:
382     * it is a strong indication of long-run stream (or whole-file-read)
383     */
384    if (size >= offset)
385        size *= 2;
386
387    ra->start = offset;
388    ra->size = get_init_ra_size(size + req_size, max);
389    ra->async_size = ra->size;
390
391    return 1;
392}
393
394/*
395 * A minimal readahead algorithm for trivial sequential/random reads.
396 */
397static unsigned long
398ondemand_readahead(struct address_space *mapping,
399           struct file_ra_state *ra, struct file *filp,
400           bool hit_readahead_marker, pgoff_t offset,
401           unsigned long req_size)
402{
403    unsigned long max = max_sane_readahead(ra->ra_pages);
404
405    /*
406     * start of file
407     */
408    if (!offset)
409        goto initial_readahead;
410
411    /*
412     * It's the expected callback offset, assume sequential access.
413     * Ramp up sizes, and push forward the readahead window.
414     */
415    if ((offset == (ra->start + ra->size - ra->async_size) ||
416         offset == (ra->start + ra->size))) {
417        ra->start += ra->size;
418        ra->size = get_next_ra_size(ra, max);
419        ra->async_size = ra->size;
420        goto readit;
421    }
422
423    /*
424     * Hit a marked page without valid readahead state.
425     * E.g. interleaved reads.
426     * Query the pagecache for async_size, which normally equals to
427     * readahead size. Ramp it up and use it as the new readahead size.
428     */
429    if (hit_readahead_marker) {
430        pgoff_t start;
431
432        rcu_read_lock();
433        start = radix_tree_next_hole(&mapping->page_tree, offset+1,max);
434        rcu_read_unlock();
435
436        if (!start || start - offset > max)
437            return 0;
438
439        ra->start = start;
440        ra->size = start - offset; /* old async_size */
441        ra->size += req_size;
442        ra->size = get_next_ra_size(ra, max);
443        ra->async_size = ra->size;
444        goto readit;
445    }
446
447    /*
448     * oversize read
449     */
450    if (req_size > max)
451        goto initial_readahead;
452
453    /*
454     * sequential cache miss
455     */
456    if (offset - (ra->prev_pos >> PAGE_CACHE_SHIFT) <= 1UL)
457        goto initial_readahead;
458
459    /*
460     * Query the page cache and look for the traces(cached history pages)
461     * that a sequential stream would leave behind.
462     */
463    if (try_context_readahead(mapping, ra, offset, req_size, max))
464        goto readit;
465
466    /*
467     * standalone, small random read
468     * Read as is, and do not pollute the readahead state.
469     */
470    return __do_page_cache_readahead(mapping, filp, offset, req_size, 0);
471
472initial_readahead:
473    ra->start = offset;
474    ra->size = get_init_ra_size(req_size, max);
475    ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;
476
477readit:
478    /*
479     * Will this read hit the readahead marker made by itself?
480     * If so, trigger the readahead marker hit now, and merge
481     * the resulted next readahead window into the current one.
482     */
483    if (offset == ra->start && ra->size == ra->async_size) {
484        ra->async_size = get_next_ra_size(ra, max);
485        ra->size += ra->async_size;
486    }
487
488    return ra_submit(ra, mapping, filp);
489}
490
491/**
492 * page_cache_sync_readahead - generic file readahead
493 * @mapping: address_space which holds the pagecache and I/O vectors
494 * @ra: file_ra_state which holds the readahead state
495 * @filp: passed on to ->readpage() and ->readpages()
496 * @offset: start offset into @mapping, in pagecache page-sized units
497 * @req_size: hint: total size of the read which the caller is performing in
498 * pagecache pages
499 *
500 * page_cache_sync_readahead() should be called when a cache miss happened:
501 * it will submit the read. The readahead logic may decide to piggyback more
502 * pages onto the read request if access patterns suggest it will improve
503 * performance.
504 */
505void page_cache_sync_readahead(struct address_space *mapping,
506                   struct file_ra_state *ra, struct file *filp,
507                   pgoff_t offset, unsigned long req_size)
508{
509    /* no read-ahead */
510    if (!ra->ra_pages)
511        return;
512
513    /* be dumb */
514    if (filp && (filp->f_mode & FMODE_RANDOM)) {
515        force_page_cache_readahead(mapping, filp, offset, req_size);
516        return;
517    }
518
519    /* do read-ahead */
520    ondemand_readahead(mapping, ra, filp, false, offset, req_size);
521}
522EXPORT_SYMBOL_GPL(page_cache_sync_readahead);
523
524/**
525 * page_cache_async_readahead - file readahead for marked pages
526 * @mapping: address_space which holds the pagecache and I/O vectors
527 * @ra: file_ra_state which holds the readahead state
528 * @filp: passed on to ->readpage() and ->readpages()
529 * @page: the page at @offset which has the PG_readahead flag set
530 * @offset: start offset into @mapping, in pagecache page-sized units
531 * @req_size: hint: total size of the read which the caller is performing in
532 * pagecache pages
533 *
534 * page_cache_async_readahead() should be called when a page is used which
535 * has the PG_readahead flag; this is a marker to suggest that the application
536 * has used up enough of the readahead window that we should start pulling in
537 * more pages.
538 */
539void
540page_cache_async_readahead(struct address_space *mapping,
541               struct file_ra_state *ra, struct file *filp,
542               struct page *page, pgoff_t offset,
543               unsigned long req_size)
544{
545    /* no read-ahead */
546    if (!ra->ra_pages)
547        return;
548
549    /*
550     * Same bit is used for PG_readahead and PG_reclaim.
551     */
552    if (PageWriteback(page))
553        return;
554
555    ClearPageReadahead(page);
556
557    /*
558     * Defer asynchronous read-ahead on IO congestion.
559     */
560    if (bdi_read_congested(mapping->backing_dev_info))
561        return;
562
563    /* do read-ahead */
564    ondemand_readahead(mapping, ra, filp, true, offset, req_size);
565}
566EXPORT_SYMBOL_GPL(page_cache_async_readahead);
567
568static ssize_t
569do_readahead(struct address_space *mapping, struct file *filp,
570         pgoff_t index, unsigned long nr)
571{
572    if (!mapping || !mapping->a_ops || !mapping->a_ops->readpage)
573        return -EINVAL;
574
575    force_page_cache_readahead(mapping, filp, index, nr);
576    return 0;
577}
578
579SYSCALL_DEFINE(readahead)(int fd, loff_t offset, size_t count)
580{
581    ssize_t ret;
582    struct file *file;
583
584    ret = -EBADF;
585    file = fget(fd);
586    if (file) {
587        if (file->f_mode & FMODE_READ) {
588            struct address_space *mapping = file->f_mapping;
589            pgoff_t start = offset >> PAGE_CACHE_SHIFT;
590            pgoff_t end = (offset + count - 1) >> PAGE_CACHE_SHIFT;
591            unsigned long len = end - start + 1;
592            ret = do_readahead(mapping, file, start, len);
593        }
594        fput(file);
595    }
596    return ret;
597}
598#ifdef CONFIG_HAVE_SYSCALL_WRAPPERS
599asmlinkage long SyS_readahead(long fd, loff_t offset, long count)
600{
601    return SYSC_readahead((int) fd, offset, (size_t) count);
602}
603SYSCALL_ALIAS(sys_readahead, SyS_readahead);
604#endif
605

Archive Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9



interactive