Improve heuristic detecting sequential reads
Subsystems (3)
Jan Kara
maintainerPATCH 1/1 Improve heuristic detecting sequential reads
Hello!
In thread http://lkml.org/lkml/2007/3/9/403, we discussed a problem
with the current heuristic for detecting sequential IO in do_generic_mapping_read() - for small files a page is marked as accessed only once which can cause a performance problems.
Attached is a patch that improves the heuristic by introducing a
ra.offset variable so now we can reliably detect sequetial reads. The patch replaces Nick's patch from http://lkml.org/lkml/2007/3/15/177
(Nick has acked to replace the patch). Could you please put the patch into -mm?
Bye
Honza
Signature · 2 lines
Jan Kara <[email protected]> SuSE CR Labs
Introduce ra.offset and store in it an offset where the previous read ended. This way we can detect whether reads are really sequential (and thus we should not mark the page as accessed repeatedly) or whether they are random and just happen to be in the same page (and the page should really be marked accessed again).
include/linux/fs.h +1 -0
@@ -702,6 +702,7 @@ struct file_ra_state {unsigned long ra_pages;/* Maximum readahead window */ unsigned long mmap_hit;/* Cache hit stat for mmap accesses */ unsigned long mmap_miss;/* Cache miss stat for mmap accesses */ +unsigned int offset;/* Offset where last read() ended in a page */ };#define RA_FLAG_MISS 0x01/* a cache miss occured against this file */ #define RA_FLAG_INCACHE 0x02/* file is already in cache */
mm/filemap.c +6 -3
@@ -868,6 +868,7 @@ void do_generic_mapping_read(struct addrunsigned long last_index;unsigned long next_index;unsigned long prev_index; +unsigned int prev_offset;loff_t isize;struct page *cached_page;int error;
@@ -877,6 +878,7 @@ void do_generic_mapping_read(struct addr index = *ppos >>PAGE_CACHE_SHIFT ; next_index = index; prev_index = ra.prev_page; + prev_offset = ra.offset; last_index = (*ppos + desc->count +PAGE_CACHE_SIZE -1 ) >>PAGE_CACHE_SHIFT ; offset = *ppos & ~PAGE_CACHE_MASK ;
@@ -924,10 +926,10 @@ page_ok:flush_dcache_page (page);/* -* When (part of) the same page is read multiple times -* in succession, only mark it as accessed the first time. +* When a sequential read accesses a page several times, +* only mark it as accessed the first time. */ -if (prev_index != index) +if (prev_index != index || offset != prev_offset)mark_page_accessed (page); prev_index = index;
@@ -945,6 +947,7 @@ page_ok: offset += ret; index += offset >>PAGE_CACHE_SHIFT ; offset &= ~PAGE_CACHE_MASK ; + prev_offset = ra.offset = offset;page_cache_release (page);if (ret == nr && desc->count)
mm/readahead.c +3 -0
@@ -207,6 +207,8 @@ out:* 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. +* offset: Offset in the prev_page where the last read ended - used for +* detection of sequential file reading. * ahead_start, * ahead_size: Together, these form the "ahead window". * ra_pages: The externally controlled max readahead for this fd.
@@ -473,6 +475,7 @@ page_cache_readahead(struct address_spac/* Note that prev_page == -1 if it is a first read */ sequential = (offset == ra->prev_page +1 ); ra->prev_page = offset; + ra->offset =0 ; max =get_max_readahead (ra); newsize =min (req_size, max);
Quoted 11 lines · Jan Kara
Hello!
In thread http://lkml.org/lkml/2007/3/9/403, we discussed a problem
with the current heuristic for detecting sequential IO indo_generic_mapping_read()- for small files a page is marked as accessed only once which can cause a performance problems.
Attached is a patch that improves the heuristic by introducing a
ra.offset variable so now we can reliably detect sequetial reads. The patch replaces Nick's patch from http://lkml.org/lkml/2007/3/15/177
(Nick has acked to replace the patch). Could you please put the patch into -mm?
There's a much more complete patchkit for this that gets reposted regularly on l-k. Perhaps it would make sense to test that first?
-Andi
Andrew Morton
maintainerQuoted 14 lines · On 11 Apr 2007 00:56:51 +0200 Andi Kleen <[email protected]> wrote:
Quoted 11 lines · Jan Kara
Hello!
In thread http://lkml.org/lkml/2007/3/9/403, we discussed a problem
with the current heuristic for detecting sequential IO indo_generic_mapping_read()- for small files a page is marked as accessed only once which can cause a performance problems.
Attached is a patch that improves the heuristic by introducing a
ra.offset variable so now we can reliably detect sequetial reads. The patch replaces Nick's patch from http://lkml.org/lkml/2007/3/15/177
(Nick has acked to replace the patch). Could you please put the patch into -mm?
Quoted 2 lines
There's a much more complete patchkit for this that gets reposted regularly on l-k. Perhaps it would make sense to test that first?
adaptive readahead? Has been in -mm for a year. Problem is, it is _so_ complete that I just don't know how to merge it. It's huge, and only Wu understands it. So it's really rather stuck.
Quoted 9 lines · Andrew Morton
Quoted 2 lines · On 11 Apr 2007 00:56:51 +0200 Andi Kleen <[email protected]> wrote:
There's a much more complete patchkit for this that gets reposted regularly on l-k. Perhaps it would make sense to test that first?
adaptive readahead? Has been in -mm for a year. Problem is, it is _so_ complete that I just don't know how to merge it. It's huge, and only Wu understands it. So it's really rather stuck.
Yeah, it is.
I'll come up with a minimal patch to first simplify the current readahead algorithm. The code is ready, if ignoring the document ;-)
Wu
Quoted 3 lines
adaptive readahead? Has been in -mm for a year. Problem is, it is _so_ complete that I just don't know how to merge it. It's huge, and only Wu understands it. So it's really rather stuck.
No benchmark numbers for/against it at all?
-Andi
Quoted 1 line
Andrew Morton
maintainerQuoted 4 lines · On Tue, 10 Apr 2007 17:54:11 +0200 Jan Kara <[email protected]> wrote:
Introduce ra.offset and store in it an offset where the previous read ended. This way we can detect whether reads are really sequential (and thus we should not mark the page as accessed repeatedly) or whether they are random and just happen to be in the same page (and the page should really be marked accessed again).
(less columns, please)
OK. So prev_page and prev_offset are now a complexified representation of a loff_t, no?
So why don't we just use a loff_t for this?
Anyway, the asymmetry in our handling of prev_index (sometimes called prev_page!) and prev_offset is unpleasing. This:
mm/filemap.c renamed from mm/filemap.c~readahead-improve-heuristic-detecting-sequential-reads-tidy +1 -1
@@ -933,6 +933,7 @@ page_ok:if (prev_index != index || offset != prev_offset)mark_page_accessed (page); prev_index = index; + prev_offset = ra.offset = offset;/* * Ok, we have the page, and it's up-to-date, so
@@ -948,7 +949,6 @@ page_ok: offset += ret; index += offset >>PAGE_CACHE_SHIFT ; offset &= ~PAGE_CACHE_MASK ; - prev_offset = ra.offset = offset;page_cache_release (page);if (ret == nr && desc->count)
improves things somewhat. But I think it would be nicer if their handling was unified, or at least consistent. We update ra.offset here, and we update ra.prev_page over there.
And shouldn't offset be called prev_offset? Or should prev_page be called page? Or index? Or prev_index? Or Marmaduke? The naming is all a mess.
Wanna take a look at all of this, please?
Jan Kara
maintainerQuoted 8 lines · Andrew Morton
Quoted 4 lines · On Tue, 10 Apr 2007 17:54:11 +0200 Jan Kara <[email protected]> wrote:
Introduce ra.offset and store in it an offset where the previous read ended. This way we can detect whether reads are really sequential (and thus we should not mark the page as accessed repeatedly) or whether they are random and just happen to be in the same page (and the page should really be marked accessed again).
(less columns, please)
Oops, sorry.
Quoted 2 lines
OK. So
prev_pageandprev_offsetare now a complexified representation of aloff_t, no?
Yes.
Quoted 1 line
So why don't we just use a
loff_tfor this?
I did not merge them because most other things in file_ra_state are in
pages and thus comparisons and assignments would require additional shifts, which would IMHO make the whole thing less clear.
Quoted 2 lines
Anyway, the asymmetry in our handling of
prev_index(sometimes calledprev_page!) andprev_offsetis unpleasing. This:
prev_page is a member of the file_ra_state. Probably prev_index would be
better name there...
Quoted 19 lines
mm/filemap.c renamed from mm/filemap.c~readahead-improve-heuristic-detecting-sequential-reads-tidy +1
-1@@ -933,6 +933,7 @@ page_ok:if (prev_index != index || offset != prev_offset)mark_page_accessed (page); prev_index = index; + prev_offset = ra.offset = offset;/* * Ok, we have the page, and it's up-to-date, so @@ -948,7 +949,6 @@ page_ok: offset += ret; index += offset >>PAGE_CACHE_SHIFT ; offset &= ~PAGE_CACHE_MASK ; - prev_offset = ra.offset = offset;page_cache_release (page);if (ret == nr && desc->count)
Quoted 3 lines
improves things somewhat. But I think it would be nicer if their handling was unified, or at least consistent. We update ra.offset here, and we update ra.prev_page over there.
It's clearer but wrong, as Wu already noted :). But the assignmentprev_index = index
can be shifted somewhat lower (definitely after the comment) which makes
things slightly more readable.
Quoted 2 lines
And shouldn't offset be called
prev_offset? Or shouldprev_pagebe called page? Or index? Orprev_index? Or Marmaduke? The naming is all a mess.
I vote for prev_index and 'offset' could be prev_offset. I'll create a
tidy-up patch...
Honza
Signature · 2 lines
Jan Kara <[email protected]> SuSE CR Labs
Jan Kara
maintainerQuoted 4 lines · Andrew Morton
And shouldn't offset be called
prev_offset? Or shouldprev_pagebe called page? Or index? Orprev_index? Or Marmaduke? The naming is all a mess.Wanna take a look at all of this, please?
OK, attached is a patch which changes prev_page to prev_index and offset
to prev_offset. It's still a bit misleading that in mm/filemap.c, variables with page-numbers are called <something>_index while in mm/readahead.c they are often called just offset... But let's leave it for next time.
Honza
Signature · 2 lines
Jan Kara <[email protected]> SuSE CR Labs
Rename file_ra_state.prev_page to prev_index and file_ra_state.offset to prev_offset. Also update of prev_index in do_generic_mapping_read() is now moved close to the update of prev_offset.
include/linux/fs.h +2 -2
@@ -696,13 +696,13 @@ struct file_ra_state {unsigned long size;unsigned long flags;/* ra flags RA_FLAG_xxx*/ unsigned long cache_hit;/* cache hit count*/ -unsigned long prev_page;/* Cache last read() position */ +unsigned long prev_index;/* Cache last read() position */ unsigned long ahead_start;/* Ahead window */ unsigned long ahead_size;unsigned long ra_pages;/* Maximum readahead window */ unsigned long mmap_hit;/* Cache hit stat for mmap accesses */ unsigned long mmap_miss;/* Cache miss stat for mmap accesses */ -unsigned int offset;/* Offset where last read() ended in a page */ +unsigned int prev_offset;/* Offset where last read() ended in a page */ };#define RA_FLAG_MISS 0x01/* a cache miss occured against this file */ #define RA_FLAG_INCACHE 0x02/* file is already in cache */
mm/filemap.c +4 -4
@@ -877,8 +877,8 @@ void do_generic_mapping_read(struct addr cached_page =NULL ; index = *ppos >>PAGE_CACHE_SHIFT ; next_index = index; - prev_index = ra.prev_page; - prev_offset = ra.offset; + prev_index = ra.prev_index; + prev_offset = ra.prev_offset; last_index = (*ppos + desc->count +PAGE_CACHE_SIZE -1 ) >>PAGE_CACHE_SHIFT ; offset = *ppos & ~PAGE_CACHE_MASK ;
@@ -931,7 +931,6 @@ page_ok:*/ if (prev_index != index || offset != prev_offset)mark_page_accessed (page); - prev_index = index;/* * Ok, we have the page, and it's up-to-date, so
@@ -947,7 +946,8 @@ page_ok: offset += ret; index += offset >>PAGE_CACHE_SHIFT ; offset &= ~PAGE_CACHE_MASK ; - prev_offset = ra.offset = offset; + prev_index = index; + prev_offset = ra.prev_offset = offset;page_cache_release (page);if (ret == nr && desc->count)
mm/readahead.c +15 -15
@@ -37,7 +37,7 @@ 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 ; + ra->prev_index =-1 ; }EXPORT_SYMBOL_GPL (file_ra_state_init);
@@ -202,19 +202,19 @@ out:* 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. +* prev_index: 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. -* offset: Offset in the prev_page where the last read ended - used for +* offset: Offset in the prev_index where the last read ended - used for * detection of sequential file reading. * 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. +* In this state, prev_index 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
@@ -417,7 +417,7 @@ static int make_ahead_window(struct addr ra->ahead_size =get_next_ra_size (ra); ra->ahead_start = ra->start + ra->size; - block = force || (ra->prev_page >= ra->ahead_start); + block = force || (ra->prev_index >= ra->ahead_start); ret =blockable_page_cache_readahead (mapping, filp, ra->ahead_start, ra->ahead_size, ra, block);
@@ -469,13 +469,13 @@ page_cache_readahead(struct address_spac* We avoid doing extra work and bogusly perturbing the readahead * window expansion logic. */ -if (offset == ra->prev_page && --req_size) +if (offset == ra->prev_index && --req_size) ++offset; -/* Note that prev_page == -1 if it is a first read */ - sequential = (offset == ra->prev_page +1 ); - ra->prev_page = offset; - ra->offset =0 ; +/* Note that prev_index == -1 if it is a first read */ + sequential = (offset == ra->prev_index +1 ); + ra->prev_index = offset; + ra->prev_offset =0 ; max =get_max_readahead (ra); newsize =min (req_size, max);
@@ -484,7 +484,7 @@ page_cache_readahead(struct address_spacif (newsize ==0 || (ra->flags &RA_FLAG_INCACHE )) goto out; - ra->prev_page += newsize -1 ; + ra->prev_index += newsize -1 ;/* * Special case - first read at start of file. We'll assume it's
@@ -540,18 +540,18 @@ page_cache_readahead(struct address_spac* 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) { +if (ra->prev_index >= ra->ahead_start) { ra->start = ra->ahead_start; ra->size = ra->ahead_size;make_ahead_window (mapping, filp, ra,0 ); recheck: -/* prev_page shouldn't overrun the ahead window */ - ra->prev_page =min (ra->prev_page, +/* prev_index shouldn't overrun the ahead window */ + ra->prev_index =min (ra->prev_index, ra->ahead_start + ra->ahead_size -1 ); } out: -return ra->prev_page +1 ; +return ra->prev_index +1 ; }EXPORT_SYMBOL_GPL (page_cache_readahead);