[PATCH] Fix off by one error in page_region_mask()

[PATCH] Fix off by one error in page_region_mask()

[Lachlan McIlroy]

final is calculated to be the last bit to set (ie inclusive) but when we
do the mask shifting final really needs to be first bit not to set.

For example if first and final are both bit 0 (ie only first bit to be set)
then mask is completely shifted and becomes all zeroes.

Or if first is 0 and final is 63 then the mask is shifted one bit when it
shouldn't be shifted at all.

--- xfs-fix.orig/fs/xfs/linux-2.6/xfs_buf.c
+++ xfs-fix/fs/xfs/linux-2.6/xfs_buf.c
@@ -129,15 +129,17 @@ page_region_mask(
  	int		first, final;

  	first = BTOPR(offset);
-	final = BTOPRT(offset + length - 1);
-	first = min(first, final);
+	final = BTOPRT(offset + length);
+
+	if (first >= final)
+		return 0UL;

  	mask = ~0UL;
  	mask <<= BITS_PER_LONG - (final - first);
  	mask >>= BITS_PER_LONG - (final);

  	ASSERT(offset + length <= PAGE_CACHE_SIZE);
-	ASSERT((final - first) < BITS_PER_LONG && (final - first) >= 0);
+	ASSERT((final - first) <= BITS_PER_LONG && (final - first) > 0);

  	return mask;
  }

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Eric Sandeen]

Lachlan McIlroy wrote:
> final is calculated to be the last bit to set (ie inclusive) but when we
> do the mask shifting final really needs to be first bit not to set.
> 
> For example if first and final are both bit 0 (ie only first bit to be set)
> then mask is completely shifted and becomes all zeroes.
> 
> Or if first is 0 and final is 63 then the mask is shifted one bit when it
> shouldn't be shifted at all.

Lachlan, what's the end result of this bug?  What's the broken behavior?

Thanks,
-Eric

> --- xfs-fix.orig/fs/xfs/linux-2.6/xfs_buf.c
> +++ xfs-fix/fs/xfs/linux-2.6/xfs_buf.c
> @@ -129,15 +129,17 @@ page_region_mask(
>   	int		first, final;
> 
>   	first = BTOPR(offset);
> -	final = BTOPRT(offset + length - 1);
> -	first = min(first, final);
> +	final = BTOPRT(offset + length);
> +
> +	if (first >= final)
> +		return 0UL;
> 
>   	mask = ~0UL;
>   	mask <<= BITS_PER_LONG - (final - first);
>   	mask >>= BITS_PER_LONG - (final);
> 
>   	ASSERT(offset + length <= PAGE_CACHE_SIZE);
> -	ASSERT((final - first) < BITS_PER_LONG && (final - first) >= 0);
> +	ASSERT((final - first) <= BITS_PER_LONG && (final - first) > 0);
> 
>   	return mask;
>   }
> 
> _______________________________________________
> xfs mailing list
> xfs@oss.sgi.com
> http://oss.sgi.com/mailman/listinfo/xfs
> 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Lachlan McIlroy]

Eric Sandeen wrote:
> Lachlan McIlroy wrote:
>> final is calculated to be the last bit to set (ie inclusive) but when we
>> do the mask shifting final really needs to be first bit not to set.
>>
>> For example if first and final are both bit 0 (ie only first bit to be set)
>> then mask is completely shifted and becomes all zeroes.
>>
>> Or if first is 0 and final is 63 then the mask is shifted one bit when it
>> shouldn't be shifted at all.
> 
> Lachlan, what's the end result of this bug?  What's the broken behavior?

There was no observed bug - well nothing I can tie directly to this code.
I found this by inspection while investigating the page bitmap stuff.
We have a problem with ia64 going to 64K page size with filesystems that
use a filesystem sector size of 512 bytes - we don't have the granularity
we need in the bitmap.

I suppose it is possible this bug could indicate a page region is not up
to date when it actually is and we might re-read something from disk and
overwrite the more up to date in-memory version.

> 
> Thanks,
> -Eric
> 
>> --- xfs-fix.orig/fs/xfs/linux-2.6/xfs_buf.c
>> +++ xfs-fix/fs/xfs/linux-2.6/xfs_buf.c
>> @@ -129,15 +129,17 @@ page_region_mask(
>>   	int		first, final;
>>
>>   	first = BTOPR(offset);
>> -	final = BTOPRT(offset + length - 1);
>> -	first = min(first, final);
>> +	final = BTOPRT(offset + length);
>> +
>> +	if (first >= final)
>> +		return 0UL;
>>
>>   	mask = ~0UL;
>>   	mask <<= BITS_PER_LONG - (final - first);
>>   	mask >>= BITS_PER_LONG - (final);
>>
>>   	ASSERT(offset + length <= PAGE_CACHE_SIZE);
>> -	ASSERT((final - first) < BITS_PER_LONG && (final - first) >= 0);
>> +	ASSERT((final - first) <= BITS_PER_LONG && (final - first) > 0);
>>
>>   	return mask;
>>   }
>>
>> _______________________________________________
>> xfs mailing list
>> xfs@oss.sgi.com
>> http://oss.sgi.com/mailman/listinfo/xfs
>>
> 
> 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Eric Sandeen]

Lachlan McIlroy wrote:
> Eric Sandeen wrote:
>> Lachlan McIlroy wrote:
>>> final is calculated to be the last bit to set (ie inclusive) but when we
>>> do the mask shifting final really needs to be first bit not to set.
>>>
>>> For example if first and final are both bit 0 (ie only first bit to be set)
>>> then mask is completely shifted and becomes all zeroes.
>>>
>>> Or if first is 0 and final is 63 then the mask is shifted one bit when it
>>> shouldn't be shifted at all.
>> Lachlan, what's the end result of this bug?  What's the broken behavior?
> 
> There was no observed bug - well nothing I can tie directly to this code.
> I found this by inspection while investigating the page bitmap stuff.
> We have a problem with ia64 going to 64K page size with filesystems that
> use a filesystem sector size of 512 bytes - we don't have the granularity
> we need in the bitmap.
> 
> I suppose it is possible this bug could indicate a page region is not up
> to date when it actually is and we might re-read something from disk and
> overwrite the more up to date in-memory version.

ah, ok.  So I've seen this corruption on 64k pages too, on ppc... but I
take it this patch doesn't fix it...

Thanks,
-Eric

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Lachlan McIlroy]

Eric Sandeen wrote:
> Lachlan McIlroy wrote:
>> Eric Sandeen wrote:
>>> Lachlan McIlroy wrote:
>>>> final is calculated to be the last bit to set (ie inclusive) but when we
>>>> do the mask shifting final really needs to be first bit not to set.
>>>>
>>>> For example if first and final are both bit 0 (ie only first bit to be set)
>>>> then mask is completely shifted and becomes all zeroes.
>>>>
>>>> Or if first is 0 and final is 63 then the mask is shifted one bit when it
>>>> shouldn't be shifted at all.
>>> Lachlan, what's the end result of this bug?  What's the broken behavior?
>> There was no observed bug - well nothing I can tie directly to this code.
>> I found this by inspection while investigating the page bitmap stuff.
>> We have a problem with ia64 going to 64K page size with filesystems that
>> use a filesystem sector size of 512 bytes - we don't have the granularity
>> we need in the bitmap.
>>
>> I suppose it is possible this bug could indicate a page region is not up
>> to date when it actually is and we might re-read something from disk and
>> overwrite the more up to date in-memory version.
> 
> ah, ok.  So I've seen this corruption on 64k pages too, on ppc... but I
> take it this patch doesn't fix it...

I don't know - it might help.  But there's still an issue beyond this patch
that needs fixing.

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Timothy Shimmin]

Lachlan McIlroy wrote:
> final is calculated to be the last bit to set (ie inclusive) but when we
> do the mask shifting final really needs to be first bit not to set.
> 
> For example if first and final are both bit 0 (ie only first bit to be set)
> then mask is completely shifted and becomes all zeroes.
> 
> Or if first is 0 and final is 63 then the mask is shifted one bit when it
> shouldn't be shifted at all.
> 
> --- xfs-fix.orig/fs/xfs/linux-2.6/xfs_buf.c
> +++ xfs-fix/fs/xfs/linux-2.6/xfs_buf.c
> @@ -129,15 +129,17 @@ page_region_mask(
>   	int		first, final;
> 
>   	first = BTOPR(offset);
> -	final = BTOPRT(offset + length - 1);
> -	first = min(first, final);
> +	final = BTOPRT(offset + length);
> +
> +	if (first >= final)
> +		return 0UL;
> 
>   	mask = ~0UL;
>   	mask <<= BITS_PER_LONG - (final - first);
>   	mask >>= BITS_PER_LONG - (final);
> 
>   	ASSERT(offset + length <= PAGE_CACHE_SIZE);
> -	ASSERT((final - first) < BITS_PER_LONG && (final - first) >= 0);
> +	ASSERT((final - first) <= BITS_PER_LONG && (final - first) > 0);
> 
>   	return mask;
>   }
> 
> _______________________________________________
> xfs mailing list
> xfs@oss.sgi.com
> http://oss.sgi.com/mailman/listinfo/xfs

Gee, I always find these tricky to get right.
I tend to like a userspace version and input various ranges,
such as extremes like you did, and verify it is working.

I kind of like first and final to be inclusive of the range to be set
(not so keen on making final to be first bit not to set -
name doesn't seem so good then).
And if one needs to know the size of the range to use (final - first + 1)
and for 0..final => size = final-0+1 = final+1.

And the thing about min(first, final) and (first >= final),
is interesting - I would have thought final would be expected to be >=
to the first ??

Okay, the other thing that interests me is the use of both BTOPR and BTOPRT
for given offsets.
BTOPR is the typical howmany() implementation, where if you go over
a multiple-boundaries worth then you need another multiple.
I would expect it to have values starting from 1.
So I was thinking typically of BTOPR for sizes and BTOPRT for 0-based offsets.
e.g. given multiple, 512
BTOPR  1..512 => 1, 513..1024 => 2
BTOPRT 0..511 => 0, 512..1023 => 1

So I find the code a bit hard to follow then.

--Tim

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Lachlan McIlroy]

Timothy Shimmin wrote:
> Lachlan McIlroy wrote:
>> final is calculated to be the last bit to set (ie inclusive) but when we
>> do the mask shifting final really needs to be first bit not to set.
>>
>> For example if first and final are both bit 0 (ie only first bit to be set)
>> then mask is completely shifted and becomes all zeroes.
>>
>> Or if first is 0 and final is 63 then the mask is shifted one bit when it
>> shouldn't be shifted at all.
>>
>> --- xfs-fix.orig/fs/xfs/linux-2.6/xfs_buf.c
>> +++ xfs-fix/fs/xfs/linux-2.6/xfs_buf.c
>> @@ -129,15 +129,17 @@ page_region_mask(
>>   	int		first, final;
>>
>>   	first = BTOPR(offset);
>> -	final = BTOPRT(offset + length - 1);
>> -	first = min(first, final);
>> +	final = BTOPRT(offset + length);
>> +
>> +	if (first >= final)
>> +		return 0UL;
>>
>>   	mask = ~0UL;
>>   	mask <<= BITS_PER_LONG - (final - first);
>>   	mask >>= BITS_PER_LONG - (final);
>>
>>   	ASSERT(offset + length <= PAGE_CACHE_SIZE);
>> -	ASSERT((final - first) < BITS_PER_LONG && (final - first) >= 0);
>> +	ASSERT((final - first) <= BITS_PER_LONG && (final - first) > 0);
>>
>>   	return mask;
>>   }
>>
>> _______________________________________________
>> xfs mailing list
>> xfs@oss.sgi.com
>> http://oss.sgi.com/mailman/listinfo/xfs
> 
> Gee, I always find these tricky to get right.
> I tend to like a userspace version and input various ranges,
> such as extremes like you did, and verify it is working.
> 
> I kind of like first and final to be inclusive of the range to be set
> (not so keen on making final to be first bit not to set -
> name doesn't seem so good then).
Using an inclusive final means we have to add 1 every time we use it - which
we could forget to do and maybe that was how this bug got introduced.

I would prefer a starting bit and a bit count but I was trying to limit
changes to a minimum.

We can change the name of final if you like.

> And if one needs to know the size of the range to use (final - first + 1)
> and for 0..final => size = final-0+1 = final+1.
> 
> And the thing about min(first, final) and (first >= final),
> is interesting - I would have thought final would be expected to be >=
> to the first ??
It wasn't the case with the old scheme.

If we have a 64KB page size then each bit is 1024 bytes and if we read the
second sector of a page:

first = BTOPR(512) = (512+1023)/1024 = 1
final = BTOPRT(512 + 512 - 1) = (1023/1024) = 0

So the off by one error creates a special case that we need to handle.
This shouldn't happen (first > final) if we remove the magic subtract 1
business:

final = BTOPRT(512 + 512) = (1024/1024) = 1

But should anyone pass in bad values that are not sector aligned this
assumption wont hold so be defensive and leave the > check in.  If we
know that the resultant mask should be all zeroes then bail early and
don't stuff around bit shifting a mask for nothing.

> 
> Okay, the other thing that interests me is the use of both BTOPR and BTOPRT
> for given offsets.
> BTOPR is the typical howmany() implementation, where if you go over
> a multiple-boundaries worth then you need another multiple.
> I would expect it to have values starting from 1.
> So I was thinking typically of BTOPR for sizes and BTOPRT for 0-based offsets.
> e.g. given multiple, 512
> BTOPR  1..512 => 1, 513..1024 => 2
> BTOPRT 0..511 => 0, 512..1023 => 1
These macros are used to round the boundaries inwards.  BTOPR rounds
up and BTOPRT rounds down.  We cannot flag partial regions as up to
date because we could expose bad data.  Actually if we have to round
then we've got a problem because if we have regions that are active
but not marked up to date we risk re-reading them and overwriting
in-memory changes.

> 
> So I find the code a bit hard to follow then.
> 
> --Tim
> 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Christoph Hellwig]

Did you guys come to a conclusion in your discussions?

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Lachlan McIlroy]

Christoph Hellwig wrote:
> Did you guys come to a conclusion in your discussions?
> 
No conclusion, well nothing that resulted in an ack.

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Lachlan McIlroy]

Lachlan McIlroy wrote:
> Christoph Hellwig wrote:
>> Did you guys come to a conclusion in your discussions?
>>
> No conclusion, well nothing that resulted in an ack.

Was anyone okay with this fix?

> 
> _______________________________________________
> xfs mailing list
> xfs@oss.sgi.com
> http://oss.sgi.com/mailman/listinfo/xfs

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Christoph Hellwig]

On Mon, Jan 19, 2009 at 05:53:37PM +1100, Lachlan McIlroy wrote:
> Lachlan McIlroy wrote:
> > Christoph Hellwig wrote:
> >> Did you guys come to a conclusion in your discussions?
> >>
> > No conclusion, well nothing that resulted in an ack.
> 
> Was anyone okay with this fix?

I think it's okay to go.  It fixes the one off so it's go.

The code is still a very hard to understand mess, but that's not what
the patch was supposed to fix..

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Christoph Hellwig]

On Thu, Jan 22, 2009 at 05:25:39PM -0500, Christoph Hellwig wrote:
> On Mon, Jan 19, 2009 at 05:53:37PM +1100, Lachlan McIlroy wrote:
> > Lachlan McIlroy wrote:
> > > Christoph Hellwig wrote:
> > >> Did you guys come to a conclusion in your discussions?
> > >>
> > > No conclusion, well nothing that resulted in an ack.
> > 
> > Was anyone okay with this fix?
> 
> I think it's okay to go.  It fixes the one off so it's go.
> 
> The code is still a very hard to understand mess, but that's not what
> the patch was supposed to fix..

Any reason this isn't in yet?

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] Fix off by one error in page_region_mask()

[Felix Blyakher]

On Feb 15, 2009, at 1:16 PM, Christoph Hellwig wrote:

> On Thu, Jan 22, 2009 at 05:25:39PM -0500, Christoph Hellwig wrote:
>> On Mon, Jan 19, 2009 at 05:53:37PM +1100, Lachlan McIlroy wrote:
>>> Lachlan McIlroy wrote:
>>>> Christoph Hellwig wrote:
>>>>> Did you guys come to a conclusion in your discussions?
>>>>>
>>>> No conclusion, well nothing that resulted in an ack.
>>>
>>> Was anyone okay with this fix?
>>
>> I think it's okay to go.  It fixes the one off so it's go.
>>
>> The code is still a very hard to understand mess, but that's not what
>> the patch was supposed to fix..
>
> Any reason this isn't in yet?

Sorry, I was holding it. I had some doubts with the mod, but
couldn't materialize them into a real argument.
I guess, I just check it in (I saw your ACK some time ago, Christoph),
and deal with anything popping up in this area later.

Felix

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs