Introduce a more complete version of context readahead, which is a full-fledged readahead algorithm by itself. It replaces some of the existing cases. - oversize read no behavior change; except in thrashed mode, async_size will be 0 - random read no behavior change; implies some different internal handling The random read will now be recorded in file_ra_state, which means in an intermixed sequential+random pattern, the sequential part's state will be flushed by random ones, and hence will be serviced by the context readahead instead of the stateful one. Also means that the first readahead for a sequential read in the middle of file will be started by the stateful one, instead of the sequential cache miss. - sequential cache miss better When walking out of a cached page segment, the readahead size will be fully restored immediately instead of ramping up from initial size. - hit readahead marker without valid state better in rare cases; costs more radix tree lookups, but won't be a problem with optimized radix_tree_prev_hole(). The added radix tree scan for history pages is to calculate the thrashing safe readahead size and adaptive async size. The algorithm first looks ahead to find the start point of next read-ahead, then looks backward in the page cache to get an estimation of the thrashing-threshold. It is able to automatically adapt to the thrashing threshold in a smooth workload. The estimation theory can be illustrated with figure: chunk A chunk B chunk C head l01 l11 l12 l21 l22 | |-->|-->| |------>|-->| |------>| | +-------+ +-----------+ +-------------+ | | | # | | # | | # | | | +-------+ +-----------+ +-------------+ | | |<==============|<===========================|<============================| L0 L1 L2 Let f(l) = L be a map from l: the number of pages read by the stream to L: the number of pages pushed into inactive_list in the mean time then f(l01) <= L0 f(l11 + l12) = L1 f(l21 + l22) = L2 ... f(l01 + l11 + ...) <= Sum(L0 + L1 + ...) <= Length(inactive_list) = f(thrashing-threshold) So the count of continuous history pages left in inactive_list is always a lower estimation of the true thrashing-threshold. Given a stable workload, the readahead size will keep ramping up and then stabilize in range (thrashing_threshold/2, thrashing_threshold) This is good because, it's in fact bad to always reach thrashing_threshold. That would not only be more susceptible to fluctuations, but also impose eviction pressure to the cached pages. To demo the thrashing safety, I run 300 200KB/s streams with mem=128M. Only 2031/61325=3.3% readahead windows are thrashed (due to workload fluctuation): # cat /debug/readahead/stats pattern readahead eof_hit cache_hit io sync_io mmap_io size async_size io_size initial 20 9 4 20 20 12 73 37 35 subsequent 3 3 0 1 0 1 8 8 1 context 61325 1 5479 61325 6788 5 14 2 13 thrash 2031 0 1222 2031 2031 0 9 0 6 around 235 90 142 235 235 235 60 0 19 fadvise 0 0 0 0 0 0 0 0 0 random 223 133 0 91 91 1 1 0 1 all 63837 236 6847 63703 9165 0 14 2 13 And the readahead inside a single stream is working as expected: # grep streams-3162 /debug/tracing/trace streams-3162 [000] 8602.455953: readahead: readahead-context(dev=0:2, ino=0, req=287352+1, ra=287354+10-2, async=1) = 10 streams-3162 [000] 8602.907873: readahead: readahead-context(dev=0:2, ino=0, req=287362+1, ra=287364+20-3, async=1) = 20 streams-3162 [000] 8604.027879: readahead: readahead-context(dev=0:2, ino=0, req=287381+1, ra=287384+14-2, async=1) = 14 streams-3162 [000] 8604.754722: readahead: readahead-context(dev=0:2, ino=0, req=287396+1, ra=287398+10-2, async=1) = 10 streams-3162 [000] 8605.191228: readahead: readahead-context(dev=0:2, ino=0, req=287406+1, ra=287408+18-3, async=1) = 18 streams-3162 [000] 8606.831895: readahead: readahead-context(dev=0:2, ino=0, req=287423+1, ra=287426+12-2, async=1) = 12 streams-3162 [000] 8606.919614: readahead: readahead-thrash(dev=0:2, ino=0, req=287425+1, ra=287425+8-0, async=0) = 1 streams-3162 [000] 8607.545016: readahead: readahead-context(dev=0:2, ino=0, req=287436+1, ra=287438+9-2, async=1) = 9 streams-3162 [000] 8607.960039: readahead: readahead-context(dev=0:2, ino=0, req=287445+1, ra=287447+18-3, async=1) = 18 streams-3162 [000] 8608.790973: readahead: readahead-context(dev=0:2, ino=0, req=287462+1, ra=287465+21-3, async=1) = 21 streams-3162 [000] 8609.763138: readahead: readahead-context(dev=0:2, ino=0, req=287483+1, ra=287486+15-2, async=1) = 15 streams-3162 [000] 8611.467401: readahead: readahead-context(dev=0:2, ino=0, req=287499+1, ra=287501+11-2, async=1) = 11 streams-3162 [000] 8642.512413: readahead: readahead-context(dev=0:2, ino=0, req=288053+1, ra=288056+10-2, async=1) = 10 streams-3162 [000] 8643.246618: readahead: readahead-context(dev=0:2, ino=0, req=288064+1, ra=288066+22-3, async=1) = 22 streams-3162 [000] 8644.278613: readahead: readahead-context(dev=0:2, ino=0, req=288085+1, ra=288088+16-3, async=1) = 16 streams-3162 [000] 8644.395782: readahead: readahead-context(dev=0:2, ino=0, req=288087+1, ra=288087+21-3, async=0) = 5 streams-3162 [000] 8645.109918: readahead: readahead-context(dev=0:2, ino=0, req=288101+1, ra=288108+8-1, async=1) = 8 streams-3162 [000] 8645.285078: readahead: readahead-context(dev=0:2, ino=0, req=288105+1, ra=288116+8-1, async=1) = 8 streams-3162 [000] 8645.731794: readahead: readahead-context(dev=0:2, ino=0, req=288115+1, ra=288122+14-2, async=1) = 13 streams-3162 [000] 8646.114250: readahead: readahead-context(dev=0:2, ino=0, req=288123+1, ra=288136+8-1, async=1) = 8 streams-3162 [000] 8646.626320: readahead: readahead-context(dev=0:2, ino=0, req=288134+1, ra=288144+16-3, async=1) = 16 streams-3162 [000] 8647.035721: readahead: readahead-context(dev=0:2, ino=0, req=288143+1, ra=288160+10-2, async=1) = 10 streams-3162 [000] 8647.693082: readahead: readahead-context(dev=0:2, ino=0, req=288157+1, ra=288165+12-2, async=1) = 8 streams-3162 [000] 8648.221368: readahead: readahead-context(dev=0:2, ino=0, req=288168+1, ra=288177+15-2, async=1) = 15 streams-3162 [000] 8649.280800: readahead: readahead-context(dev=0:2, ino=0, req=288190+1, ra=288192+23-3, async=1) = 23 [...] Signed-off-by: Wu Fengguang --- include/linux/fs.h | 1 mm/readahead.c | 155 ++++++++++++++++++++++++------------------- 2 files changed, 88 insertions(+), 68 deletions(-) --- linux.orig/mm/readahead.c 2010-02-24 10:44:42.000000000 +0800 +++ linux/mm/readahead.c 2010-02-24 10:44:44.000000000 +0800 @@ -68,6 +68,11 @@ static int __init check_readahead_size(v fs_initcall(check_readahead_size); /* + * Set async size to 1/# of the thrashing threshold. + */ +#define READAHEAD_ASYNC_RATIO 8 + +/* * Initialise a struct file's readahead state. Assumes that the caller has * memset *ra to zero. */ @@ -441,39 +446,16 @@ static pgoff_t count_history_pages(struc } /* - * page cache context based read-ahead + * Is @index recently readahead but not yet read by application? + * The low boundary is permissively estimated. */ -static int try_context_readahead(struct address_space *mapping, - struct file_ra_state *ra, - pgoff_t offset, - unsigned long req_size, - unsigned long max) +static bool ra_thrashed(struct file_ra_state *ra, pgoff_t index) { - pgoff_t size; - - size = count_history_pages(mapping, ra, offset, max); - - /* - * no history pages: - * it could be a random read - */ - if (!size) - return 0; - - /* - * starts from beginning of file: - * it is a strong indication of long-run stream (or whole-file-read) - */ - if (size >= offset) - size *= 2; - - ra->start = offset; - ra->size = get_init_ra_size(size + req_size, max); - ra->async_size = ra->size; - - return 1; + return (index >= ra->start - ra->size && + index < ra->start + ra->size); } + /* * A minimal readahead algorithm for trivial sequential/random reads. */ @@ -484,12 +466,26 @@ ondemand_readahead(struct address_space unsigned long req_size) { unsigned long max = max_sane_readahead(ra->ra_pages); + unsigned int size; + pgoff_t start; /* * start of file */ - if (!offset) - goto initial_readahead; + if (!offset) { + ra->start = offset; + ra->size = get_init_ra_size(req_size, max); + ra->async_size = ra->size > req_size ? + ra->size - req_size : ra->size; + goto readit; + } + + /* + * Context readahead is thrashing safe, and can adapt to near the + * thrashing threshold given a stable workload. + */ + if (ra->ra_flags & READAHEAD_THRASHED) + goto context_readahead; /* * It's the expected callback offset, assume sequential access. @@ -504,58 +500,81 @@ ondemand_readahead(struct address_space } /* - * Hit a marked page without valid readahead state. - * E.g. interleaved reads. - * Query the pagecache for async_size, which normally equals to - * readahead size. Ramp it up and use it as the new readahead size. + * oversize read, no need to query page cache */ - if (hit_readahead_marker) { - pgoff_t start; + if (req_size > max && !hit_readahead_marker) { + ra->start = offset; + ra->size = max; + ra->async_size = max; + goto readit; + } + /* + * page cache context based read-ahead + * + * ==========================_____________.............. + * [ current window ] + * ^offset + * 1) |---- A ---->[start + * 2) |<----------- H -----------| + * 3) |----------- H ----------->]end + * [ new window ] + * [=] cached,visited [_] cached,to-be-visited [.] not cached + * + * 1) A = pages ahead = previous async_size + * 2) H = history pages = thrashing safe size + * 3) H - A = new readahead size + */ +context_readahead: + if (hit_readahead_marker) { rcu_read_lock(); - start = radix_tree_next_hole(&mapping->page_tree, offset+1,max); + start = radix_tree_next_hole(&mapping->page_tree, + offset + 1, max); rcu_read_unlock(); - + /* + * there are enough pages ahead: no readahead + */ if (!start || start - offset > max) return 0; + } else + start = offset; + size = count_history_pages(mapping, ra, offset, + READAHEAD_ASYNC_RATIO * max); + /* + * no history pages cached, could be + * - a random read + * - a thrashed sequential read + */ + if (!size && !hit_readahead_marker) { + if (!ra_thrashed(ra, offset)) { + ra->size = min(req_size, max); + } else { + retain_inactive_pages(mapping, offset, min(2 * max, + ra->start + ra->size - offset)); + ra->size = max_t(int, ra->size/2, MIN_READAHEAD_PAGES); + ra->ra_flags |= READAHEAD_THRASHED; + } + ra->async_size = 0; ra->start = start; - ra->size = start - offset; /* old async_size */ - ra->size += req_size; - ra->size = get_next_ra_size(ra, max); - ra->async_size = ra->size; goto readit; } - /* - * oversize read + * history pages start from beginning of file: + * it is a strong indication of long-run stream (or whole-file reads) */ - if (req_size > max) - goto initial_readahead; - - /* - * sequential cache miss - */ - if (offset - (ra->prev_pos >> PAGE_CACHE_SHIFT) <= 1UL) - goto initial_readahead; - - /* - * Query the page cache and look for the traces(cached history pages) - * that a sequential stream would leave behind. - */ - if (try_context_readahead(mapping, ra, offset, req_size, max)) - goto readit; - + if (size >= offset) + size *= 2; /* - * standalone, small random read - * Read as is, and do not pollute the readahead state. + * pages to readahead are already cached */ - return __do_page_cache_readahead(mapping, filp, offset, req_size, 0); + if (size <= start - offset) + return 0; -initial_readahead: - ra->start = offset; - ra->size = get_init_ra_size(req_size, max); - ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size; + size -= start - offset; + ra->start = start; + ra->size = clamp_t(unsigned int, size, MIN_READAHEAD_PAGES, max); + ra->async_size = min(ra->size, 1 + size / READAHEAD_ASYNC_RATIO); readit: /* --- linux.orig/include/linux/fs.h 2010-02-24 10:44:43.000000000 +0800 +++ linux/include/linux/fs.h 2010-02-24 10:44:44.000000000 +0800 @@ -895,6 +895,7 @@ struct file_ra_state { /* ra_flags bits */ #define READAHEAD_MMAP_MISS 0x00000fff /* cache misses for mmap access */ +#define READAHEAD_THRASHED 0x10000000 /* * Don't do ra_flags++ directly to avoid possible overflow: -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/