[GIT-PULL] More Squashfs fixes for 2.6.29?

[GIT-PULL] More Squashfs fixes for 2.6.29?

[Phillip Lougher]

Hi Linus,

Please consider pulling the following Squashfs commit. It fixes an important
mistake in a previous patch which flags some valid filesystems as corrupted.

Please pull from

git://git.kernel.org/pub/scm/linux/kernel/git/pkl/squashfs-linus.git 

Thanks

Phillip

commit 7dacdd0d86a70564cd56e49cd9432d68e0a58916
Author: Phillip Lougher <phillip@lougher.demon.co.uk>
Date:   Wed Mar 11 17:55:28 2009 +0000

Squashfs: Valid filesystems are flagged as bad by the corrupted fs patch

The problem arises due to an unexpected corner-case with zlib which the
corrupted filesystems patch didn't address.  Very occasionally zlib
exits needing a couple of extra bytes of input (up to 6 seen bytes in the
test filesystems), but with avail_out == 0 and no more output buffer
space available.  This situation was incorrectly flagged as an output buffer
overrun by the corrupted filesystems patch.

Signed-off-by: Phillip Lougher <phillip@lougher.demon.co.uk>
Reported-by: Stefan Lippers-Hollmann <s.L-H@gmx.de>
Tested-by: Geert Uytterhoeven <Geert.Uytterhoeven@sonycom.com>
---
 fs/squashfs/block.c |   29 ++++++++++++++++-------------
 1 files changed, 16 insertions(+), 13 deletions(-)

diff --git a/fs/squashfs/block.c b/fs/squashfs/block.c
index 321728f..b85173f 100644
--- a/fs/squashfs/block.c
+++ b/fs/squashfs/block.c
@@ -166,6 +166,22 @@ int squashfs_read_data(struct super_block *sb, void **buffer, u64 index,
 
 		bytes = length;
 		do {
+			if (msblk->stream.avail_out == 0) {
+				if (page < pages) {
+					msblk->stream.next_out = buffer[page++];
+					msblk->stream.avail_out =
+								PAGE_CACHE_SIZE;
+				} else if (msblk->stream.avail_in > 0
+								|| bytes == 0) {
+					ERROR("zlib_inflate tried to "
+						"decompress too much data, "
+						"expected %d bytes.  Zlib "
+						"data probably corrupt\n",
+						srclength);
+					goto release_mutex;
+				}
+			}
+
 			if (msblk->stream.avail_in == 0 && k < b) {
 				avail = min(bytes, msblk->devblksize - offset);
 				bytes -= avail;
@@ -184,19 +200,6 @@ int squashfs_read_data(struct super_block *sb, void **buffer, u64 index,
 				offset = 0;
 			}
 
-			if (msblk->stream.avail_out == 0) {
-				if (page == pages) {
-					ERROR("zlib_inflate tried to "
-						"decompress too much data, "
-						"expected %d bytes.  Zlib "
-						"data probably corrupt\n",
-						srclength);
-					goto release_mutex;
-				}
-				msblk->stream.next_out = buffer[page++];
-				msblk->stream.avail_out = PAGE_CACHE_SIZE;
-			}
-
 			if (!zlib_init) {
 				zlib_err = zlib_inflateInit(&msblk->stream);
 				if (zlib_err != Z_OK) {
-- 
1.5.6.3

Re: [GIT-PULL] More Squashfs fixes for 2.6.29?

[Linus Torvalds]

On Wed, 11 Mar 2009, Phillip Lougher wrote:
> 
> Squashfs: Valid filesystems are flagged as bad by the corrupted fs patch
> 
> The problem arises due to an unexpected corner-case with zlib which the
> corrupted filesystems patch didn't address.  Very occasionally zlib
> exits needing a couple of extra bytes of input (up to 6 seen bytes in the
> test filesystems), but with avail_out == 0 and no more output buffer
> space available.  This situation was incorrectly flagged as an output buffer
> overrun by the corrupted filesystems patch.

I'm almost certain that this situation is caused by a bug in how you call 
zlib().

You've explicitly asked for Z_NO_FLUSH, and I suspect you should be using 
Z_SYNC_FLUSH (of Z_FINISH if you know you have all the input data). You 
want as much to be inflated as possible, and you do seem to be expecting 
it to flush as much as possible. 

However, I think the more direct cause is your inflate loop. The rules for 
running inflate() is to call it until it is done, or returns an error:

    inflate() should normally be called until it returns Z_STREAM_END or an
  error. However if all decompression is to be performed in a single step
  (a single call of inflate), the parameter flush should be set to
  Z_FINISH.

so you seem to be doing this all wrong. I think you _should_ be doing an 
inner loop over zlib_inflate() that just does inflates until you get a 
buffer error, and if you get a buffer error you then go on to the next 
page if avail_out is zero (all done if it's the last page), or fill the 
input buffer if it's empty.

So I really think you should fix the zlib_inflate() loop instead.

I dunno. At least that's what the docs suggest, and it's what we do in 
git (another heavy user of zlib, althoughb the usage patterns are rather 
different, and we _tend_ to 

			Linus

Re: [GIT-PULL] More Squashfs fixes for 2.6.29?

[Phillip Lougher]

Linus Torvalds wrote:
> 
> On Wed, 11 Mar 2009, Phillip Lougher wrote:
>> Squashfs: Valid filesystems are flagged as bad by the corrupted fs patch
>>
>> The problem arises due to an unexpected corner-case with zlib which the
>> corrupted filesystems patch didn't address.  Very occasionally zlib
>> exits needing a couple of extra bytes of input (up to 6 seen bytes in the
>> test filesystems), but with avail_out == 0 and no more output buffer
>> space available.  This situation was incorrectly flagged as an output buffer
>> overrun by the corrupted filesystems patch.
> 
> I'm almost certain that this situation is caused by a bug in how you call 
> zlib().
> 
> You've explicitly asked for Z_NO_FLUSH, and I suspect you should be using 
> Z_SYNC_FLUSH (of Z_FINISH if you know you have all the input data). You 
> want as much to be inflated as possible, and you do seem to be expecting 
> it to flush as much as possible. 

Z_NO_FLUSH and Z_SYNC_FLUSH are equivalent in the zlib implementation
according to the documentation...

    "In this implementation, inflate() always flushes as much output as
   possible to the output buffer, and always uses the faster approach on the
   first call. So the only effect of the flush parameter in this implementation
   is on the return value of inflate(), as noted below, or when it returns early
   because Z_BLOCK is used."

Which is why I never bothered to change it.  But, I agree it should be
Z_SYNC_FLUSH for correctness.


> 
> However, I think the more direct cause is your inflate loop. The rules for 
> running inflate() is to call it until it is done, or returns an error:
> 
>     inflate() should normally be called until it returns Z_STREAM_END or an
>   error. However if all decompression is to be performed in a single step
>   (a single call of inflate), the parameter flush should be set to
>   Z_FINISH.
> 
> so you seem to be doing this all wrong. I think you _should_ be doing an 
> inner loop over zlib_inflate() that just does inflates until you get a 
> buffer error, and if you get a buffer error you then go on to the next 
> page if avail_out is zero (all done if it's the last page), or fill the 
> input buffer if it's empty.

I originally implemented an inner loop, something like

do {
	if(avail_out == 0)
		Get next output buffer

	if(avail_in == 0)
		Get next input buffer

	do {
		err = zlib_inflate( xxxx )
	while (err == Z_OK);

} while (err == Z_BUF_ERROR);

But I optimised the inner loop out because of the following logic:

zlib_inflate always tries to make as much progress as possible, therefore
if it returns Z_OK it always either needs more input or more output, in which
case iterating around the outer loop will get the next buffer.  If it returns
any other error code (Z_STREAM_END or Z_DATA_ERROR) we want to terminate
the loop.  The inner loop iterating until Z_BUF_ERROR is received is therefore
unnecessary, it merely iterates twice, first receiving Z_OK, the second time
receiving Z_BUF_ERROR (because no progress can be made),  dropping out to
the outer loop to get the next buffers.

So this should have equivalent behaviour

do {
	if(avail_out == 0)
		Get next output buffer

	if(avail_in == 0)
		Get next input buffer

	err = zlib_inflate( xxxx )

} while (err == Z_OK);


I could put the inner loop back in if you prefer.

Phillip

> 
> So I really think you should fix the zlib_inflate() loop instead.
> 
> I dunno. At least that's what the docs suggest, and it's what we do in 
> git (another heavy user of zlib, althoughb the usage patterns are rather 
> different, and we _tend_ to 
> 
> 			Linus
> 

Re: [GIT-PULL] More Squashfs fixes for 2.6.29?

[Linus Torvalds]

On Thu, 12 Mar 2009, Phillip Lougher wrote:
> 
> But I optimised the inner loop out because of the following logic:
> 
> zlib_inflate always tries to make as much progress as possible

Is this strictly true? Your own bug report seems to say that it isn't.

Hmm. [ Goes back and looks. ] The zlib source code is a total piece of 
mess, but it does seem like it only does "goto inf_leave" when it needs 
more data (unless you ask for the "stop at block boundary", of course). Or 
in the Z_STREAM_END case, or errors. 

But your bug report sounds very much like you got all the data already 
(nothing available for output any more), but then didn't do the last CHECK 
stage (== no output, but the input contains the 32-bit adler checksum and 
the CHECK command). That would explain exactly the case of "a few extra 
bytes at the input, despite not having any output left".

And if you don't do the CHECK stage, then you're missing a large part of 
the corruption checking that zlib does.

So you should never exit based on whether you still need output. So that

	if (msblk->stream.avail_out == 0) {
		..
		else if (msblk->stream.avail_in > 0
			BUG

really looks _wrong_. It's not a buggy situation at all to have no output 
left to process, but still input in the input buffers. It may well just 
mean that you ended up having the CHECK part of the zlib buffer in a new 
input buffer.

		Linus

Re: [GIT-PULL] More Squashfs fixes for 2.6.29?

[Phillip Lougher]

Linus Torvalds wrote:
> 
> On Thu, 12 Mar 2009, Phillip Lougher wrote:
>> But I optimised the inner loop out because of the following logic:
>>
>> zlib_inflate always tries to make as much progress as possible
> 
> Is this strictly true? Your own bug report seems to say that it isn't.
> 
> Hmm. [ Goes back and looks. ] The zlib source code is a total piece of 
> mess, but it does seem like it only does "goto inf_leave" when it needs 
> more data (unless you ask for the "stop at block boundary", of course). Or 
> in the Z_STREAM_END case, or errors. 
> 
> But your bug report sounds very much like you got all the data already 
> (nothing available for output any more), but then didn't do the last CHECK 
> stage (== no output, but the input contains the 32-bit adler checksum and 
> the CHECK command). That would explain exactly the case of "a few extra 
> bytes at the input, despite not having any output left".

Yes, this is exactly what's happening.  Sorry if the bug report didn't
make it clear.

> 
> And if you don't do the CHECK stage, then you're missing a large part of 
> the corruption checking that zlib does.
> 
> So you should never exit based on whether you still need output. So that
> 
> 	if (msblk->stream.avail_out == 0) {
> 		..
> 		else if (msblk->stream.avail_in > 0
> 			BUG
> 
> really looks _wrong_. It's not a buggy situation at all to have no output 
> left to process, but still input in the input buffers. It may well just 
> mean that you ended up having the CHECK part of the zlib buffer in a new 
> input buffer.

Yes the check is pretty bogus.  I'm about to send an improved patch
that gets rid of this check (just relying on zlib to error if we've
got no more output buffers, and it wants to output).

I'll also put some more info into the commit indicating the problem
it's fixing.

Thanks

Phillip

> 
> 		Linus
>