diff options
Diffstat (limited to 'mm/readahead.c')
| -rw-r--r-- | mm/readahead.c | 557 |
1 files changed, 557 insertions, 0 deletions
diff --git a/mm/readahead.c b/mm/readahead.c new file mode 100644 index 000000000000..b840e7c6ea74 --- /dev/null +++ b/mm/readahead.c @@ -0,0 +1,557 @@ +/* + * mm/readahead.c - address_space-level file readahead. + * + * Copyright (C) 2002, Linus Torvalds + * + * 09Apr2002 akpm@zip.com.au + * Initial version. + */ + +#include <linux/kernel.h> +#include <linux/fs.h> +#include <linux/mm.h> +#include <linux/module.h> +#include <linux/blkdev.h> +#include <linux/backing-dev.h> +#include <linux/pagevec.h> + +void default_unplug_io_fn(struct backing_dev_info *bdi, struct page *page) +{ +} +EXPORT_SYMBOL(default_unplug_io_fn); + +struct backing_dev_info default_backing_dev_info = { + .ra_pages = (VM_MAX_READAHEAD * 1024) / PAGE_CACHE_SIZE, + .state = 0, + .capabilities = BDI_CAP_MAP_COPY, + .unplug_io_fn = default_unplug_io_fn, +}; +EXPORT_SYMBOL_GPL(default_backing_dev_info); + +/* + * Initialise a struct file's readahead state. Assumes that the caller has + * memset *ra to zero. + */ +void +file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping) +{ + ra->ra_pages = mapping->backing_dev_info->ra_pages; + ra->prev_page = -1; +} + +/* + * Return max readahead size for this inode in number-of-pages. + */ +static inline unsigned long get_max_readahead(struct file_ra_state *ra) +{ + return ra->ra_pages; +} + +static inline unsigned long get_min_readahead(struct file_ra_state *ra) +{ + return (VM_MIN_READAHEAD * 1024) / PAGE_CACHE_SIZE; +} + +static inline void ra_off(struct file_ra_state *ra) +{ + ra->start = 0; + ra->flags = 0; + ra->size = 0; + ra->ahead_start = 0; + ra->ahead_size = 0; + return; +} + +/* + * Set the initial window size, round to next power of 2 and square + * for small size, x 4 for medium, and x 2 for large + * for 128k (32 page) max ra + * 1-8 page = 32k initial, > 8 page = 128k initial + */ +static unsigned long get_init_ra_size(unsigned long size, unsigned long max) +{ + unsigned long newsize = roundup_pow_of_two(size); + + if (newsize <= max / 64) + newsize = newsize * newsize; + else if (newsize <= max / 4) + newsize = max / 4; + else + newsize = max; + return newsize; +} + +/* + * Set the new window size, this is called only when I/O is to be submitted, + * not for each call to readahead. If a cache miss occured, reduce next I/O + * size, else increase depending on how close to max we are. + */ +static inline unsigned long get_next_ra_size(struct file_ra_state *ra) +{ + unsigned long max = get_max_readahead(ra); + unsigned long min = get_min_readahead(ra); + unsigned long cur = ra->size; + unsigned long newsize; + + if (ra->flags & RA_FLAG_MISS) { + ra->flags &= ~RA_FLAG_MISS; + newsize = max((cur - 2), min); + } else if (cur < max / 16) { + newsize = 4 * cur; + } else { + newsize = 2 * cur; + } + return min(newsize, max); +} + +#define list_to_page(head) (list_entry((head)->prev, struct page, lru)) + +/** + * read_cache_pages - populate an address space with some pages, and + * start reads against them. + * @mapping: the address_space + * @pages: The address of a list_head which contains the target pages. These + * pages have their ->index populated and are otherwise uninitialised. + * @filler: callback routine for filling a single page. + * @data: private data for the callback routine. + * + * Hides the details of the LRU cache etc from the filesystems. + */ +int read_cache_pages(struct address_space *mapping, struct list_head *pages, + int (*filler)(void *, struct page *), void *data) +{ + struct page *page; + struct pagevec lru_pvec; + int ret = 0; + + pagevec_init(&lru_pvec, 0); + + while (!list_empty(pages)) { + page = list_to_page(pages); + list_del(&page->lru); + if (add_to_page_cache(page, mapping, page->index, GFP_KERNEL)) { + page_cache_release(page); + continue; + } + ret = filler(data, page); + if (!pagevec_add(&lru_pvec, page)) + __pagevec_lru_add(&lru_pvec); + if (ret) { + while (!list_empty(pages)) { + struct page *victim; + + victim = list_to_page(pages); + list_del(&victim->lru); + page_cache_release(victim); + } + break; + } + } + pagevec_lru_add(&lru_pvec); + return ret; +} + +EXPORT_SYMBOL(read_cache_pages); + +static int read_pages(struct address_space *mapping, struct file *filp, + struct list_head *pages, unsigned nr_pages) +{ + unsigned page_idx; + struct pagevec lru_pvec; + int ret = 0; + + if (mapping->a_ops->readpages) { + ret = mapping->a_ops->readpages(filp, mapping, pages, nr_pages); + goto out; + } + + pagevec_init(&lru_pvec, 0); + for (page_idx = 0; page_idx < nr_pages; page_idx++) { + struct page *page = list_to_page(pages); + list_del(&page->lru); + if (!add_to_page_cache(page, mapping, + page->index, GFP_KERNEL)) { + mapping->a_ops->readpage(filp, page); + if (!pagevec_add(&lru_pvec, page)) + __pagevec_lru_add(&lru_pvec); + } else { + page_cache_release(page); + } + } + pagevec_lru_add(&lru_pvec); +out: + return ret; +} + +/* + * Readahead design. + * + * The fields in struct file_ra_state represent the most-recently-executed + * readahead attempt: + * + * start: Page index at which we started the readahead + * size: Number of pages in that read + * Together, these form the "current window". + * Together, start and size represent the `readahead window'. + * prev_page: The page which the readahead algorithm most-recently inspected. + * It is mainly used to detect sequential file reading. + * If page_cache_readahead sees that it is again being called for + * a page which it just looked at, it can return immediately without + * making any state changes. + * ahead_start, + * ahead_size: Together, these form the "ahead window". + * ra_pages: The externally controlled max readahead for this fd. + * + * When readahead is in the off state (size == 0), readahead is disabled. + * In this state, prev_page is used to detect the resumption of sequential I/O. + * + * The readahead code manages two windows - the "current" and the "ahead" + * windows. The intent is that while the application is walking the pages + * in the current window, I/O is underway on the ahead window. When the + * current window is fully traversed, it is replaced by the ahead window + * and the ahead window is invalidated. When this copying happens, the + * new current window's pages are probably still locked. So + * we submit a new batch of I/O immediately, creating a new ahead window. + * + * So: + * + * ----|----------------|----------------|----- + * ^start ^start+size + * ^ahead_start ^ahead_start+ahead_size + * + * ^ When this page is read, we submit I/O for the + * ahead window. + * + * A `readahead hit' occurs when a read request is made against a page which is + * the next sequential page. Ahead window calculations are done only when it + * is time to submit a new IO. The code ramps up the size agressively at first, + * but slow down as it approaches max_readhead. + * + * Any seek/ramdom IO will result in readahead being turned off. It will resume + * at the first sequential access. + * + * There is a special-case: if the first page which the application tries to + * read happens to be the first page of the file, it is assumed that a linear + * read is about to happen and the window is immediately set to the initial size + * based on I/O request size and the max_readahead. + * + * This function is to be called for every read request, rather than when + * it is time to perform readahead. It is called only once for the entire I/O + * regardless of size unless readahead is unable to start enough I/O to satisfy + * the request (I/O request > max_readahead). + */ + +/* + * do_page_cache_readahead actually reads a chunk of disk. It allocates all + * the pages first, then submits them all for I/O. This avoids the very bad + * behaviour which would occur if page allocations are causing VM writeback. + * We really don't want to intermingle reads and writes like that. + * + * Returns the number of pages requested, or the maximum amount of I/O allowed. + * + * do_page_cache_readahead() returns -1 if it encountered request queue + * congestion. + */ +static int +__do_page_cache_readahead(struct address_space *mapping, struct file *filp, + unsigned long offset, unsigned long nr_to_read) +{ + struct inode *inode = mapping->host; + struct page *page; + unsigned long end_index; /* The last page we want to read */ + LIST_HEAD(page_pool); + int page_idx; + int ret = 0; + loff_t isize = i_size_read(inode); + + if (isize == 0) + goto out; + + end_index = ((isize - 1) >> PAGE_CACHE_SHIFT); + + /* + * Preallocate as many pages as we will need. + */ + read_lock_irq(&mapping->tree_lock); + for (page_idx = 0; page_idx < nr_to_read; page_idx++) { + unsigned long page_offset = offset + page_idx; + + if (page_offset > end_index) + break; + + page = radix_tree_lookup(&mapping->page_tree, page_offset); + if (page) + continue; + + read_unlock_irq(&mapping->tree_lock); + page = page_cache_alloc_cold(mapping); + read_lock_irq(&mapping->tree_lock); + if (!page) + break; + page->index = page_offset; + list_add(&page->lru, &page_pool); + ret++; + } + read_unlock_irq(&mapping->tree_lock); + + /* + * Now start the IO. We ignore I/O errors - if the page is not + * uptodate then the caller will launch readpage again, and + * will then handle the error. + */ + if (ret) + read_pages(mapping, filp, &page_pool, ret); + BUG_ON(!list_empty(&page_pool)); +out: + return ret; +} + +/* + * Chunk the readahead into 2 megabyte units, so that we don't pin too much + * memory at once. + */ +int force_page_cache_readahead(struct address_space *mapping, struct file *filp, + unsigned long offset, unsigned long nr_to_read) +{ + int ret = 0; + + if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages)) + return -EINVAL; + + while (nr_to_read) { + int err; + + unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_CACHE_SIZE; + + if (this_chunk > nr_to_read) + this_chunk = nr_to_read; + err = __do_page_cache_readahead(mapping, filp, + offset, this_chunk); + if (err < 0) { + ret = err; + break; + } + ret += err; + offset += this_chunk; + nr_to_read -= this_chunk; + } + return ret; +} + +/* + * Check how effective readahead is being. If the amount of started IO is + * less than expected then the file is partly or fully in pagecache and + * readahead isn't helping. + * + */ +static inline int check_ra_success(struct file_ra_state *ra, + unsigned long nr_to_read, unsigned long actual) +{ + if (actual == 0) { + ra->cache_hit += nr_to_read; + if (ra->cache_hit >= VM_MAX_CACHE_HIT) { + ra_off(ra); + ra->flags |= RA_FLAG_INCACHE; + return 0; + } + } else { + ra->cache_hit=0; + } + return 1; +} + +/* + * This version skips the IO if the queue is read-congested, and will tell the + * block layer to abandon the readahead if request allocation would block. + * + * force_page_cache_readahead() will ignore queue congestion and will block on + * request queues. + */ +int do_page_cache_readahead(struct address_space *mapping, struct file *filp, + unsigned long offset, unsigned long nr_to_read) +{ + if (bdi_read_congested(mapping->backing_dev_info)) + return -1; + + return __do_page_cache_readahead(mapping, filp, offset, nr_to_read); +} + +/* + * Read 'nr_to_read' pages starting at page 'offset'. If the flag 'block' + * is set wait till the read completes. Otherwise attempt to read without + * blocking. + * Returns 1 meaning 'success' if read is succesfull without switching off + * readhaead mode. Otherwise return failure. + */ +static int +blockable_page_cache_readahead(struct address_space *mapping, struct file *filp, + unsigned long offset, unsigned long nr_to_read, + struct file_ra_state *ra, int block) +{ + int actual; + + if (!block && bdi_read_congested(mapping->backing_dev_info)) + return 0; + + actual = __do_page_cache_readahead(mapping, filp, offset, nr_to_read); + + return check_ra_success(ra, nr_to_read, actual); +} + +static int make_ahead_window(struct address_space *mapping, struct file *filp, + struct file_ra_state *ra, int force) +{ + int block, ret; + + ra->ahead_size = get_next_ra_size(ra); + ra->ahead_start = ra->start + ra->size; + + block = force || (ra->prev_page >= ra->ahead_start); + ret = blockable_page_cache_readahead(mapping, filp, + ra->ahead_start, ra->ahead_size, ra, block); + + if (!ret && !force) { + /* A read failure in blocking mode, implies pages are + * all cached. So we can safely assume we have taken + * care of all the pages requested in this call. + * A read failure in non-blocking mode, implies we are + * reading more pages than requested in this call. So + * we safely assume we have taken care of all the pages + * requested in this call. + * + * Just reset the ahead window in case we failed due to + * congestion. The ahead window will any way be closed + * in case we failed due to excessive page cache hits. + */ + ra->ahead_start = 0; + ra->ahead_size = 0; + } + + return ret; +} + +/* + * page_cache_readahead is the main function. If performs the adaptive + * readahead window size management and submits the readahead I/O. + */ +unsigned long +page_cache_readahead(struct address_space *mapping, struct file_ra_state *ra, + struct file *filp, unsigned long offset, + unsigned long req_size) +{ + unsigned long max, newsize; + int sequential; + + /* + * We avoid doing extra work and bogusly perturbing the readahead + * window expansion logic. + */ + if (offset == ra->prev_page && --req_size) + ++offset; + + /* Note that prev_page == -1 if it is a first read */ + sequential = (offset == ra->prev_page + 1); + ra->prev_page = offset; + + max = get_max_readahead(ra); + newsize = min(req_size, max); + + /* No readahead or sub-page sized read or file already in cache */ + if (newsize == 0 || (ra->flags & RA_FLAG_INCACHE)) + goto out; + + ra->prev_page += newsize - 1; + + /* + * Special case - first read at start of file. We'll assume it's + * a whole-file read and grow the window fast. Or detect first + * sequential access + */ + if (sequential && ra->size == 0) { + ra->size = get_init_ra_size(newsize, max); + ra->start = offset; + if (!blockable_page_cache_readahead(mapping, filp, offset, + ra->size, ra, 1)) + goto out; + + /* + * If the request size is larger than our max readahead, we + * at least want to be sure that we get 2 IOs in flight and + * we know that we will definitly need the new I/O. + * once we do this, subsequent calls should be able to overlap + * IOs,* thus preventing stalls. so issue the ahead window + * immediately. + */ + if (req_size >= max) + make_ahead_window(mapping, filp, ra, 1); + + goto out; + } + + /* + * Now handle the random case: + * partial page reads and first access were handled above, + * so this must be the next page otherwise it is random + */ + if (!sequential) { + ra_off(ra); + blockable_page_cache_readahead(mapping, filp, offset, + newsize, ra, 1); + goto out; + } + + /* + * If we get here we are doing sequential IO and this was not the first + * occurence (ie we have an existing window) + */ + + if (ra->ahead_start == 0) { /* no ahead window yet */ + if (!make_ahead_window(mapping, filp, ra, 0)) + goto out; + } + /* + * Already have an ahead window, check if we crossed into it. + * If so, shift windows and issue a new ahead window. + * Only return the #pages that are in the current window, so that + * we get called back on the first page of the ahead window which + * will allow us to submit more IO. + */ + if (ra->prev_page >= ra->ahead_start) { + ra->start = ra->ahead_start; + ra->size = ra->ahead_size; + make_ahead_window(mapping, filp, ra, 0); + } + +out: + return ra->prev_page + 1; +} + +/* + * handle_ra_miss() is called when it is known that a page which should have + * been present in the pagecache (we just did some readahead there) was in fact + * not found. This will happen if it was evicted by the VM (readahead + * thrashing) + * + * Turn on the cache miss flag in the RA struct, this will cause the RA code + * to reduce the RA size on the next read. + */ +void handle_ra_miss(struct address_space *mapping, + struct file_ra_state *ra, pgoff_t offset) +{ + ra->flags |= RA_FLAG_MISS; + ra->flags &= ~RA_FLAG_INCACHE; +} + +/* + * Given a desired number of PAGE_CACHE_SIZE readahead pages, return a + * sensible upper limit. + */ +unsigned long max_sane_readahead(unsigned long nr) +{ + unsigned long active; + unsigned long inactive; + unsigned long free; + + __get_zone_counts(&active, &inactive, &free, NODE_DATA(numa_node_id())); + return min(nr, (inactive + free) / 2); +} |