[PATCH] Improve heuristic detecting sequential reads

[PATCH] Improve heuristic detecting sequential reads

[Jan Kara]

[-- Attachment #1: Type: text/plain, Size: 614 bytes --]

  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

-- 
Jan Kara <jack@suse.cz>
SuSE CR Labs

[-- Attachment #2: readahead-2.6.21-rc6.diff --]
[-- Type: text/x-patch, Size: 3581 bytes --]

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).

Signed-off-by: Jan Kara <jack@suse.cz>

diff -rupX /home/jack/.kerndiffexclude linux-2.6.21-rc6/include/linux/fs.h linux-2.6.21-rc6-1-readahead/include/linux/fs.h
--- linux-2.6.21-rc6/include/linux/fs.h	2007-04-10 17:09:58.000000000 +0200
+++ linux-2.6.21-rc6-1-readahead/include/linux/fs.h	2007-04-10 17:14:42.000000000 +0200
@@ -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 */
diff -rupX /home/jack/.kerndiffexclude linux-2.6.21-rc6/mm/filemap.c linux-2.6.21-rc6-1-readahead/mm/filemap.c
--- linux-2.6.21-rc6/mm/filemap.c	2007-04-10 17:10:00.000000000 +0200
+++ linux-2.6.21-rc6-1-readahead/mm/filemap.c	2007-04-10 17:18:10.000000000 +0200
@@ -868,6 +868,7 @@ void do_generic_mapping_read(struct addr
 	unsigned 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)
diff -rupX /home/jack/.kerndiffexclude linux-2.6.21-rc6/mm/readahead.c linux-2.6.21-rc6-1-readahead/mm/readahead.c
--- linux-2.6.21-rc6/mm/readahead.c	2007-04-10 17:10:00.000000000 +0200
+++ linux-2.6.21-rc6-1-readahead/mm/readahead.c	2007-04-10 17:14:42.000000000 +0200
@@ -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);

Re: [PATCH] Improve heuristic detecting sequential reads

[Andi Kleen]

Jan Kara <jack@suse.cz> writes:

>   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?

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

Re: [PATCH] Improve heuristic detecting sequential reads

[Andrew Morton]

On 11 Apr 2007 00:56:51 +0200
Andi Kleen <andi@firstfloor.org> wrote:

> Jan Kara <jack@suse.cz> writes:
> 
> >   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?
> 
> 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.

Re: [PATCH] Improve heuristic detecting sequential reads

[WU Fengguang]

On Tue, Apr 10, 2007 at 04:45:40PM -0700, Andrew Morton wrote:
> On 11 Apr 2007 00:56:51 +0200
> Andi Kleen <andi@firstfloor.org> 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

Re: [PATCH] Improve heuristic detecting sequential reads

[Andi Kleen]

> 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
> 

Re: [PATCH] Improve heuristic detecting sequential reads

[Andrew Morton]

On Tue, 10 Apr 2007 17:54:11 +0200 Jan Kara <jack@suse.cz> 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:

--- a/mm/filemap.c~readahead-improve-heuristic-detecting-sequential-reads-tidy
+++ a/mm/filemap.c
@@ -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?

Re: [PATCH] Improve heuristic detecting sequential reads

[Jan Kara]

On Tue 10-04-07 19:27:22, Andrew Morton wrote:
> On Tue, 10 Apr 2007 17:54:11 +0200 Jan Kara <jack@suse.cz> 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.

> OK.  So prev_page and prev_offset are now a complexified representation of a
> loff_t, no?  
  Yes.

> So why don't we just use a loff_t for 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.

> Anyway, the asymmetry in our handling of prev_index (sometimes called
> prev_page!) and prev_offset is unpleasing.  This:
  prev_page is a member of the file_ra_state. Probably prev_index would be
better name there...

> --- a/mm/filemap.c~readahead-improve-heuristic-detecting-sequential-reads-tidy
> +++ a/mm/filemap.c
> @@ -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.
  It's clearer but wrong, as Wu already noted :). But the assignment
prev_index = index
  can be shifted somewhat lower (definitely after the comment) which makes
things slightly more readable.

> 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.
  I vote for prev_index and 'offset' could be prev_offset. I'll create a
tidy-up patch...

									Honza
-- 
Jan Kara <jack@suse.cz>
SuSE CR Labs

Re: [PATCH] Improve heuristic detecting sequential reads

[Jan Kara]

[-- Attachment #1: Type: text/plain, Size: 598 bytes --]

On Tue 10-04-07 19:27:22, Andrew Morton wrote:
> 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?
  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
-- 
Jan Kara <jack@suse.cz>
SuSE CR Labs

[-- Attachment #2: readahead-2.6.21-rc6-tidy.diff --]
[-- Type: text/x-patch, Size: 6481 bytes --]

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.

Signed-off-by: Jan Kara <jack@suse.cz>

diff -rupX /home/jack/.kerndiffexclude linux-2.6.21-rc6-1-readahead/include/linux/fs.h linux-2.6.21-rc6-2-readahead-tidy/include/linux/fs.h
--- linux-2.6.21-rc6-1-readahead/include/linux/fs.h	2007-04-10 17:14:42.000000000 +0200
+++ linux-2.6.21-rc6-2-readahead-tidy/include/linux/fs.h	2007-04-12 17:01:08.000000000 +0200
@@ -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 */
diff -rupX /home/jack/.kerndiffexclude linux-2.6.21-rc6-1-readahead/mm/filemap.c linux-2.6.21-rc6-2-readahead-tidy/mm/filemap.c
--- linux-2.6.21-rc6-1-readahead/mm/filemap.c	2007-04-10 17:18:10.000000000 +0200
+++ linux-2.6.21-rc6-2-readahead-tidy/mm/filemap.c	2007-04-12 16:19:25.000000000 +0200
@@ -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)
diff -rupX /home/jack/.kerndiffexclude linux-2.6.21-rc6-1-readahead/mm/readahead.c linux-2.6.21-rc6-2-readahead-tidy/mm/readahead.c
--- linux-2.6.21-rc6-1-readahead/mm/readahead.c	2007-04-10 17:14:42.000000000 +0200
+++ linux-2.6.21-rc6-2-readahead-tidy/mm/readahead.c	2007-04-12 17:03:18.000000000 +0200
@@ -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_spac
 	if (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);