[PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Phillip Lougher]

Hi,

There is a readahead bug in do_generic_mapping_read (filemap.c).  This
bug appears to have been introduced in 2.6.8-rc1.  Specifically the bug
is caused by an incorrect code change which causes VFS to call
readpage() for indexes beyond the end of files where the file length is
zero or a 4k multiple.

In Squashfs this causes a variety of almost immediate OOPes because
Squashfs trusts the VFS not to pass invalid index values.  For other
filesystems it may also be causing subtle bugs.  I have received
prune_dcache oopes similar to Gene Heskett's (which was also
pointer corruption), and so it may fix this and other reported
readahead bugs.

The patch is against 2.6.8-rc3.

Regards

Phillip Lougher

diff --new-file -ur linux-2.6.8-rc3-squashfs2.0-test/mm/filemap.c linux-2.6.8-rc3-squashfs2.0-patched/mm/filemap.c
--- linux-2.6.8-rc3-squashfs2.0-test/mm/filemap.c       2004-08-05 02:14:39.000000000 +0100
+++ linux-2.6.8-rc3-squashfs2.0-patched/mm/filemap.c    2004-08-05 18:15:00.000000000 +0100
@@ -674,6 +674,15 @@
                 unsigned long nr, ret;

                 cond_resched();
+
+               /* nr is the maximum number of bytes to copy from this page */
+               nr = PAGE_CACHE_SIZE;
+               if (index == end_index) {
+                       nr = isize & ~PAGE_CACHE_MASK;
+                       if (nr <= offset)
+                               goto out;
+               }
+
                 page_cache_readahead(mapping, &ra, filp, index);

  find_page:
@@ -685,15 +694,6 @@
                 if (!PageUptodate(page))
                         goto page_not_up_to_date;
  page_ok:
-               /* nr is the maximum number of bytes to copy from this page */
-               nr = PAGE_CACHE_SIZE;
-               if (index == end_index) {
-                       nr = isize & ~PAGE_CACHE_MASK;
-                       if (nr <= offset) {
-                               page_cache_release(page);
-                               goto out;
-                       }
-               }
                 nr = nr - offset;

                 /* If users can be writing to this page using arbitrary

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Nick Piggin]

Phillip Lougher wrote:

> Hi,
>
> There is a readahead bug in do_generic_mapping_read (filemap.c).  This
> bug appears to have been introduced in 2.6.8-rc1.  Specifically the bug
> is caused by an incorrect code change which causes VFS to call
> readpage() for indexes beyond the end of files where the file length is
> zero or a 4k multiple.
>
> In Squashfs this causes a variety of almost immediate OOPes because
> Squashfs trusts the VFS not to pass invalid index values.  For other
> filesystems it may also be causing subtle bugs.  I have received
> prune_dcache oopes similar to Gene Heskett's (which was also
> pointer corruption), and so it may fix this and other reported
> readahead bugs.
>
> The patch is against 2.6.8-rc3.
>

Good work - bug is mine, sorry.

You actually re-introduce a bug where read can return incorrect
data due to i_size changing from under it (I introduced this bug
while fixing that one).

My fix was to re-check i_size and update 'nr' after doing the
->readpage. You could probably fix up both problems with your
patch and also copying the hunk down to after i_size gets rechecked.
Does that sound ok?


The root of the problem is that i_size gets checked from multiple
places that it can get out of synch. A nice fix would be to snapshot
i_size once, and pass that around everywhere. Unfortunately this is
very intrusive.

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Nick Piggin]

Nick Piggin wrote:

> Phillip Lougher wrote:
>
>> Hi,
>>
>> There is a readahead bug in do_generic_mapping_read (filemap.c).  This
>> bug appears to have been introduced in 2.6.8-rc1.  Specifically the bug
>> is caused by an incorrect code change which causes VFS to call
>> readpage() for indexes beyond the end of files where the file length is
>> zero or a 4k multiple.
>>
>> In Squashfs this causes a variety of almost immediate OOPes because
>> Squashfs trusts the VFS not to pass invalid index values.  For other
>> filesystems it may also be causing subtle bugs.  I have received
>> prune_dcache oopes similar to Gene Heskett's (which was also
>> pointer corruption), and so it may fix this and other reported
>> readahead bugs.
>>
>> The patch is against 2.6.8-rc3.
>>
>
> Good work - bug is mine, sorry.
>

On second thought, maybe not. I think your filesystem is at fault.

Firstly, there possibly is a bug in do_pagecache_readahead which allows 
it to
read off the end of the file in a completely serialised situation. But 
even so,
notice the absence of locking - i_size can change at any time can't it? Then
your fix will blow up when you race with a truncate, right?

I think you need to handle reading off the end of the file properly: I'm not
too familiar with this code, but IIRC you are allowed to setup pagecache 
past
the end of the file - it gets handled correctly in 
do_generic_mapping_read, and
ends up falling off the LRU. This should help you.

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Ram]

On Thu, 2004-08-05 at 23:19, Nick Piggin wrote:
> Ram Pai wrote:
> 
> > 
> > there is a check in __do_page_cache_readahead()  that validates this.
> > But it is still not guaranteed to work correctly against races. 
> > 
> > The filesystem has to handle such out-of-bound requests gracefully.
> > 
> > However with Nick's fix in do_generic_mapping_read() the filesystem 
> > is gauranteed to be called with out-of-bound index, if the file size 
> > is a multiple of 4k. Without the fix, the filesystem might get
> > called with out-of-bound index only in racy conditions.
> > 
> 
> How's this?

If I understand your patch correctly: it takes care of files whose size
is 0 bytes, but not files of size 4k bytes or 8k bytes. or .. n*4k bytes

I think the original check that you removed should be reverted back and
the additional check that you introduced should remain.

RP
> 
> ---
> 
>  linux-2.6-npiggin/mm/filemap.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff -puN mm/filemap.c~fs-fix mm/filemap.c
> --- linux-2.6/mm/filemap.c~fs-fix	2004-08-06 16:16:26.000000000 +1000
> +++ linux-2.6-npiggin/mm/filemap.c	2004-08-06 16:18:22.000000000 +1000
> @@ -716,9 +716,9 @@ void do_generic_mapping_read(struct addr
>  	offset = *ppos & ~PAGE_CACHE_MASK;
>  
>  	isize = i_size_read(inode);
> -	end_index = isize >> PAGE_CACHE_SHIFT;
> -	if (index > end_index)
> +	if (*ppos >= isize)
>  		goto out;
> +	end_index = isize >> PAGE_CACHE_SHIFT;
>  
>  	for (;;) {
>  		struct page *page;
> 
> _

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Phillip Lougher]

Nick Piggin wrote:

> On second thought, maybe not. I think your filesystem is at fault.

No I'm not wrong here. With a read-only filesystem i_size can
never change, there are no possible race conditions.  If a too
large index is passed it is a VFS bug.  Are you suggesting I should
start to code assuming the VFS is broken?

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Phillip Lougher]

Nick Piggin wrote:
> Ram Pai wrote:
> 
>>
>> there is a check in __do_page_cache_readahead()  that validates this.
>> But it is still not guaranteed to work correctly against races.
>> The filesystem has to handle such out-of-bound requests gracefully.
>>
>> However with Nick's fix in do_generic_mapping_read() the filesystem is 
>> gauranteed to be called with out-of-bound index, if the file size is a 
>> multiple of 4k. Without the fix, the filesystem might get
>> called with out-of-bound index only in racy conditions.
>>
> 
> How's this?
> 

It doesn't work.  It correctly handles the case where *ppos is equal
to i_size on entry to the function (and this does work for files 0, 4k
and n * 4k in length), but it doesn't handle readahead inside the for
loop.  The check needs to be in the for loop.

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Ram Pai]

On Fri, 6 Aug 2004, Phillip Lougher wrote:

> Nick Piggin wrote:
> > Ram Pai wrote:
> > 
> >>
> >> there is a check in __do_page_cache_readahead()  that validates this.
> >> But it is still not guaranteed to work correctly against races.
> >> The filesystem has to handle such out-of-bound requests gracefully.
> >>
> >> However with Nick's fix in do_generic_mapping_read() the filesystem is 
> >> gauranteed to be called with out-of-bound index, if the file size is a 
> >> multiple of 4k. Without the fix, the filesystem might get
> >> called with out-of-bound index only in racy conditions.
> >>
> > 
> > How's this?
> > 
> 
> It doesn't work.  It correctly handles the case where *ppos is equal
> to i_size on entry to the function (and this does work for files 0, 4k
> and n * 4k in length), but it doesn't handle readahead inside the for
> loop.  The check needs to be in the for loop.


Thinking of it more.. Is it not right to leave the code as is now?

That way all filesystems that cannot handle out-of-bound index access
are forcefully made to fix it.  The filesystems anyway are not guaranteed
non-out-of-bound index access by the VFS.

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

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Nick Piggin]

Phillip Lougher wrote:
> Nick Piggin wrote:
> 
>> On second thought, maybe not. I think your filesystem is at fault.
> 
> 
> No I'm not wrong here. With a read-only filesystem i_size can
> never change, there are no possible race conditions.  If a too
> large index is passed it is a VFS bug.  Are you suggesting I should
> start to code assuming the VFS is broken?
> 

No, I suggest you start to code assuming this interface does
what it does. I didn't say there is no bug here, but nobody
else's filesystem breaks.

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Nick Piggin]

Phillip Lougher wrote:
> Nick Piggin wrote:
> 
>> Ram Pai wrote:
>>
>>>
>>> there is a check in __do_page_cache_readahead()  that validates this.
>>> But it is still not guaranteed to work correctly against races.
>>> The filesystem has to handle such out-of-bound requests gracefully.
>>>
>>> However with Nick's fix in do_generic_mapping_read() the filesystem 
>>> is gauranteed to be called with out-of-bound index, if the file size 
>>> is a multiple of 4k. Without the fix, the filesystem might get
>>> called with out-of-bound index only in racy conditions.
>>>
>>
>> How's this?
>>
> 
> It doesn't work.  It correctly handles the case where *ppos is equal
> to i_size on entry to the function (and this does work for files 0, 4k
> and n * 4k in length), but it doesn't handle readahead inside the for
> loop.  The check needs to be in the for loop.
> 
> 

I don't quite follow. What is i_size, *ppos, and desc->count
required for your problem to trigger?

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Phillip Lougher]

Nick Piggin wrote:
> Phillip Lougher wrote:
> 
>> Nick Piggin wrote:
>>
>>> On second thought, maybe not. I think your filesystem is at fault.
>>
>>
>>
>> No I'm not wrong here. With a read-only filesystem i_size can
>> never change, there are no possible race conditions.  If a too
>> large index is passed it is a VFS bug.  Are you suggesting I should
>> start to code assuming the VFS is broken?
>>
> 
> No, I suggest you start to code assuming this interface does
> what it does. I didn't say there is no bug here, but nobody
> else's filesystem breaks.
> 

Point one: The interface didn't do this UNTIL you changed the code
Point two: Just because no one has reported other filesystem
breakage, it doesn't mean other filesystems have not broken.

Perhaps I should have the check in my code.  However, it is
still stupid to fix an occasional race by ensuring readpage() is
always called with an out of bounds index when files are 0 or a
4K multiple.  The filesystem check may prevent a crash, but it
is needlessly wasteful by design, not through any inadvertant
race condition.

think is it stupid to fix an o.  However, I it
stupid to fix a race co
ll think it stupid to fix a race you en

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Phillip Lougher]

Nick Piggin wrote:

> No, I suggest you start to code assuming this interface does
> what it does. I didn't say there is no bug here, but nobody
> else's filesystem breaks.
> 

To stop this silly argument from escalating, I will patch my code.

Phillip

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[viro]

On Fri, Aug 06, 2004 at 08:14:55PM +0100, Phillip Lougher wrote:
> Point one: The interface didn't do this UNTIL you changed the code
> Point two: Just because no one has reported other filesystem
> breakage, it doesn't mean other filesystems have not broken.

Point three: it was never promised *AND* never intended.

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Phillip Lougher]

Nick Piggin wrote:
> Phillip Lougher wrote:
> 
>> It doesn't work.  It correctly handles the case where *ppos is equal
>> to i_size on entry to the function (and this does work for files 0, 4k
>> and n * 4k in length), but it doesn't handle readahead inside the for
>> loop.  The check needs to be in the for loop.
>>
>>
> 
> I don't quite follow. What is i_size, *ppos, and desc->count
> required for your problem to trigger?
> 

 From some output I prepared earlier :-)

Aug  6 16:15:29 pierrot kernel: Entered do_generic_mapping_read: *ppos 0x0, isize 0x3000
Aug  6 16:15:29 pierrot kernel: iteration 0x1
Aug  6 16:15:29 pierrot kernel: Entered squashfs_readpage, page index 0x0, inode->i_size 0x3000
Aug  6 16:15:29 pierrot kernel: at (ret == nr && desc->count) check: ret==nr ? yes, desc->count 0x3000
Aug  6 16:15:29 pierrot kernel: iteration 0x2
Aug  6 16:15:29 pierrot kernel: at (ret == nr && desc->count) check: ret==nr ? yes, desc->count 0x2000
Aug  6 16:15:29 pierrot kernel: iteration 0x3
Aug  6 16:15:29 pierrot kernel: at (ret == nr && desc->count) check: ret==nr ? yes, desc->count 0x1000
Aug  6 16:15:29 pierrot kernel: iteration 0x4
Aug  6 16:15:29 pierrot kernel: at "readpage: label", i_size 0x3000, *ppos 0x0, index 0x3
Aug  6 16:15:29 pierrot kernel: Entered squashfs_readpage, page index 0x3, inode->i_size 0x3000

iteration 0x1 etc are the separate passes through the loop.
The first squashfs_readpage is called via page_cache_readahead, which
reads pages 0, 1 and 2 (which is why no readpage is called in
iterations 2 and 3).  The second squashfs_readpage is called in the
fourth loop iteration by the 'goto no_cached_page' code path when no
page has been found by find_get_page, this is presumably because the
index is now out of bounds.

As I said in my previous email, I'm going to put an index
check into my code.  I don't want this argument to proceed
and myself to start (?) to look like an ass.

Phillip

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Andrew Morton]

Phillip Lougher <phillip@lougher.demon.co.uk> wrote:
>
> Nick Piggin wrote:
> 
> > No, I suggest you start to code assuming this interface does
> > what it does. I didn't say there is no bug here, but nobody
> > else's filesystem breaks.
> > 
> 
> To stop this silly argument from escalating, I will patch my code.
> 

Well I don't think it's silly.

We are deterministically asking the fs to read a page which lies outside
EOF, and we shouldn't.  If for no other reason than that the ever-popular
"read a million 4k files" workload will consume extra CPU and twice the
pagecache.

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Nick Piggin]

Phillip Lougher wrote:

> page has been found by find_get_page, this is presumably because the
> index is now out of bounds.

Hmm, yeah it looks like that will trigger an out of bounds read. I'm
trying to work out how it can be fixed without doing the i_size check
twice per page - not sure if it is possible. I'll have another look
tomorrow.

> 
> As I said in my previous email, I'm going to put an index
> check into my code.  I don't want this argument to proceed
> and myself to start (?) to look like an ass.
> 

That wasn't what I thought or intended at all. You probably know more
about this code than I do, but even if not you have found a bug or
regression in the code. So let's try to work this one out. So far I
am the only one who looks like an ass because I broke the thing in the
first place :P

Re: [PATCH] VFS readahead bug in 2.6.8-rc[1-3]

[Pozsar Balazs]

On Sat, Aug 07, 2004 at 04:58:21AM +1000, Nick Piggin wrote:
> Phillip Lougher wrote:
> >Nick Piggin wrote:
> >
> >>On second thought, maybe not. I think your filesystem is at fault.
> >
> >
> >No I'm not wrong here. With a read-only filesystem i_size can
> >never change, there are no possible race conditions.  If a too
> >large index is passed it is a VFS bug.  Are you suggesting I should
> >start to code assuming the VFS is broken?
> >
> 
> No, I suggest you start to code assuming this interface does
> what it does. I didn't say there is no bug here, but nobody
> else's filesystem breaks.

Well, that might not exactly be true. We have noticed the same problem 
with ext2 too. Maybe I can send an example initrd image which triggers 
the bug on Monday.


-- 
Pozsar Balazs