Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Richard W.M. Jones]

[I'm tracking this issue here:
https://bugzilla.redhat.com/show_bug.cgi?id=808421]

febootstrap uses the ext2fs library to construct an ext2 filesystem.

Since we updated to the latest version in git, febootstrap segfaults
in ext2fs_find_first_zero_generic_bmap (called from ext2fs_new_inode).
There's a complete stack trace in the bug above.

I'm not claiming that we are calling this library correctly, but,
you know, "it always worked until now".

Here is the calling code:

https://github.com/libguestfs/febootstrap/blob/636a80b5a70382f21da47c44a0acd3efa2bc7fcf/helper/ext2.c#L142

git bisect points to this change being the one which causes the
problem:

c1a1e7fc24d6e37f931bbb8eeb29c90243f0a55d is the first bad commit
commit c1a1e7fc24d6e37f931bbb8eeb29c90243f0a55d
Author: Sami Liedes <sami.liedes@iki.fi>
Date:   Sat Mar 10 22:36:12 2012 +0200

    libext2fs: Implement ext2fs_find_first_zero_generic_bmap().
    
    This function searches a bitmap for the first zero bit within a range.
    It checks if there is a bitmap backend specific implementation
    available (if the relevant field in bitmap_ops is non-NULL). If not,
    it uses a generic and slow method by repeatedly calling test_bmap() in
    a loop. Also change ext2fs_new_inode() to use this new function.
    
    This change in itself does not result in a large speedup, rather it
    refactors the code in preparation for the introduction of a faster
    find_first_zero() for bitarray based bitmaps.
    
    Signed-off-by: Sami Liedes <sami.liedes@iki.fi>
    Signed-off-by: Theodore Ts'o <tytso@mit.edu>

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
libguestfs lets you edit virtual machines.  Supports shell scripting,
bindings from many languages.  http://libguestfs.org

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Richard W.M. Jones]

On Fri, Mar 30, 2012 at 01:57:26PM +0100, Richard W.M. Jones wrote:
> [I'm tracking this issue here:
> https://bugzilla.redhat.com/show_bug.cgi?id=808421]

A bit of further investigation:

I'm currently not passing EXT2_FLAG_64BITS when opening the
filesystem.  Passing this flag fixes the issue, so I'm going to do
that (are there any downsides?)

It seems like a non-64-bit-compatible bitmap was being created, and
that doesn't have the bitmap->bitmap_ops field initialized because
gen_bitmap.c doesn't use this field.  Somehow, though, we end up
calling a function in gen_bitmap64.c which requires that this field be
defined.

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
libguestfs lets you edit virtual machines.  Supports shell scripting,
bindings from many languages.  http://libguestfs.org

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Eric Sandeen]

On 3/30/12 8:19 AM, Richard W.M. Jones wrote:
> On Fri, Mar 30, 2012 at 01:57:26PM +0100, Richard W.M. Jones wrote:
>> [I'm tracking this issue here:
>> https://bugzilla.redhat.com/show_bug.cgi?id=808421]
> 
> A bit of further investigation:
> 
> I'm currently not passing EXT2_FLAG_64BITS when opening the
> filesystem.  Passing this flag fixes the issue, so I'm going to do
> that (are there any downsides?)
> 
> It seems like a non-64-bit-compatible bitmap was being created, and
> that doesn't have the bitmap->bitmap_ops field initialized because
> gen_bitmap.c doesn't use this field.  Somehow, though, we end up
> calling a function in gen_bitmap64.c which requires that this field be
> defined.
> 
> Rich.
> 

Well here's what's busted:

        if (bitmap->bitmap_ops->find_first_zero)
                return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);

        if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
                return EINVAL;

bitmap->bitmap_ops->find_first_zero only exists for a 64-bit bitmap, which
gets tested after we try to deref it :(

I wonder if this fixes it:

diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index b57df54..ce6c23d 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -768,7 +768,7 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 {
 	int b;
 
-	if (bitmap->bitmap_ops->find_first_zero)
+	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero)
 		return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
 
 	if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)


But then the next conditional would give us EINVAL since !EXT2FS_IS_64_BITMAP,
and I don't think things would go well after that either.

I am a little confused by the existence of two different
struct ext2fs_struct_generic_bitmap's in the code.  But treating one as the
other looks doomed to failure ;)

I haven't wrapped my head around this yet.

-Eric

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Eric Sandeen]

On 3/30/12 2:38 PM, Eric Sandeen wrote:
> On 3/30/12 8:19 AM, Richard W.M. Jones wrote:
>> On Fri, Mar 30, 2012 at 01:57:26PM +0100, Richard W.M. Jones wrote:
>>> [I'm tracking this issue here:
>>> https://bugzilla.redhat.com/show_bug.cgi?id=808421]
>>
>> A bit of further investigation:
>>
>> I'm currently not passing EXT2_FLAG_64BITS when opening the
>> filesystem.  Passing this flag fixes the issue, so I'm going to do
>> that (are there any downsides?)
>>
>> It seems like a non-64-bit-compatible bitmap was being created, and
>> that doesn't have the bitmap->bitmap_ops field initialized because
>> gen_bitmap.c doesn't use this field.  Somehow, though, we end up
>> calling a function in gen_bitmap64.c which requires that this field be
>> defined.
>>
>> Rich.
>>
> 
> Well here's what's busted:
> 
>         if (bitmap->bitmap_ops->find_first_zero)
>                 return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
> 
>         if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
>                 return EINVAL;
> 
> bitmap->bitmap_ops->find_first_zero only exists for a 64-bit bitmap, which
> gets tested after we try to deref it :(
> 
> I wonder if this fixes it:

I guess it doesn't.  Seems ext2fs_find_first_zero_generic_bmap needs
a 32-bit-bitmap fallback.

-Eric

> diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
> index b57df54..ce6c23d 100644
> --- a/lib/ext2fs/gen_bitmap64.c
> +++ b/lib/ext2fs/gen_bitmap64.c
> @@ -768,7 +768,7 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
>  {
>  	int b;
>  
> -	if (bitmap->bitmap_ops->find_first_zero)
> +	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero)
>  		return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
>  
>  	if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
> 
> 
> But then the next conditional would give us EINVAL since !EXT2FS_IS_64_BITMAP,
> and I don't think things would go well after that either.
> 
> I am a little confused by the existence of two different
> struct ext2fs_struct_generic_bitmap's in the code.  But treating one as the
> other looks doomed to failure ;)
> 
> I haven't wrapped my head around this yet.
> 
> -Eric
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Sami Liedes]

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

On Fri, Mar 30, 2012 at 02:38:42PM -0500, Eric Sandeen wrote:
> On 3/30/12 8:19 AM, Richard W.M. Jones wrote:
> > It seems like a non-64-bit-compatible bitmap was being created, and
> > that doesn't have the bitmap->bitmap_ops field initialized because
> > gen_bitmap.c doesn't use this field.  Somehow, though, we end up
> > calling a function in gen_bitmap64.c which requires that this field be
> > defined.

Argh, indeed. I thought the 32-bit bitfields also have the bitmap_ops
field (and in the same offset), but they don't.

> Well here's what's busted:
> 
>         if (bitmap->bitmap_ops->find_first_zero)
>                 return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
> 
>         if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
>                 return EINVAL;
> 
> bitmap->bitmap_ops->find_first_zero only exists for a 64-bit bitmap, which
> gets tested after we try to deref it :(

Right, that's quite bogus. The !bitmap test should obviously be first,
not after we first dereference it. Then we should test for 64-bitness,
and only ever touch the bitmap_ops field if we have a 64-bit bitmap.

> I am a little confused by the existence of two different
> struct ext2fs_struct_generic_bitmap's in the code.  But treating one as the
> other looks doomed to failure ;)

In addition to that, there are actually three different versions of
many operations; they are named ext2_foo_bmap(), ext2_foo_bitmap() and
ext2_foo_bitmap2(). I'm quite confused too.

While I suggest passing EXT2_FLAG_64BITS to ext2fs_open() - it should
never break anything and only makes things faster - the code obviously
shouldn't break when that is not passed.

(I wonder if it would make sense to have something like
EXT2_BASE_FLAGS that could include any flags which never hurt,
currently apparently only EXT2_FLAG_64BITS. From the name of the flag
EXT2_FLAG_64BITS it's not obvious that you should always use it. As
far as I understand correctly, it's there only for ABI compatibility
with code compiled before the flag was introduced and it never makes
sense to not pass it in any new code.)

The patch below unbreaks the code (well, at least resize2fs
modified to not pass EXT2_FLAG_64BITS) for me.

	Sami Liedes

------------------------------------------------------------

commit bb8fe012a3b1705809f6129cd9c78d2cd855b1f8
Author: Sami Liedes <sami.liedes@iki.fi>
Date:   Fri Apr 6 22:06:30 2012 +0300

    Fix ext2fs_find_first_zero_generic_bmap() for 32-bit bitmaps.
    
    ext2fs_find_first_zero_generic_bmap() tries to handle old-style 32-bit
    bitmaps, but fails in several different ways.
    
    Fix the order of the (in)validity tests and the fallback code to never
    dereference the bitmap, as we don't know at that point if it's a
    32-bit bitmap or a 64-bitmap bitmap whose backend implementation does
    not support find_first_zero(). Use the generic bitop functions for
    everything instead.
    
    Addresses-Red-Hat-Bugzilla: #808421
    
    Signed-off-by: Sami Liedes <sami.liedes@iki.fi>
    Reported-by: Richard W.M. Jones <rjones@redhat.com>

diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index e765d2c..7e9b8a0 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -770,19 +770,25 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 {
 	int b;
 
-	if (bitmap->bitmap_ops->find_first_zero)
+	if (!bitmap)
+		return EINVAL;
+
+	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero)
 		return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
 
-	if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
+	if (!EXT2FS_IS_32_BITMAP(bitmap) || bitmap->cluster_bits)
 		return EINVAL;
 
-	if (start < bitmap->start || end > bitmap->end || start > end) {
+	// We must be careful to not use any of bitmap's fields here,
+	// as it may actually be the different 32-bit version of the structure
+	if (start < ext2fs_get_block_bitmap_start(bitmap) ||
+	    end > ext2fs_get_block_bitmap_end(bitmap) || start > end) {
 		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
 		return EINVAL;
 	}
 
 	while (start <= end) {
-		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
+		b = ext2fs_test_generic_bitmap(bitmap, start);
 		if (!b) {
 			*out = start;
 			return 0;

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Eric Sandeen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 4/6/12 12:14 PM, Sami Liedes wrote:
> On Fri, Mar 30, 2012 at 02:38:42PM -0500, Eric Sandeen wrote:
>> On 3/30/12 8:19 AM, Richard W.M. Jones wrote:
>>> It seems like a non-64-bit-compatible bitmap was being created, and
>>> that doesn't have the bitmap->bitmap_ops field initialized because
>>> gen_bitmap.c doesn't use this field.  Somehow, though, we end up
>>> calling a function in gen_bitmap64.c which requires that this field be
>>> defined.
> 
> Argh, indeed. I thought the 32-bit bitfields also have the bitmap_ops
> field (and in the same offset), but they don't.

nope :)

>> Well here's what's busted:
>>
>>         if (bitmap->bitmap_ops->find_first_zero)
>>                 return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
>>
>>         if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
>>                 return EINVAL;
>>
>> bitmap->bitmap_ops->find_first_zero only exists for a 64-bit bitmap, which
>> gets tested after we try to deref it :(
> 
> Right, that's quite bogus. The !bitmap test should obviously be first,
> not after we first dereference it. Then we should test for 64-bitness,
> and only ever touch the bitmap_ops field if we have a 64-bit bitmap.
> 
>> I am a little confused by the existence of two different
>> struct ext2fs_struct_generic_bitmap's in the code.  But treating one as the
>> other looks doomed to failure ;)
> 
> In addition to that, there are actually three different versions of
> many operations; they are named ext2_foo_bmap(), ext2_foo_bitmap() and
> ext2_foo_bitmap2(). I'm quite confused too.

Yeah, it's rather inscrutable.

> While I suggest passing EXT2_FLAG_64BITS to ext2fs_open() - it should
> never break anything and only makes things faster - the code obviously
> shouldn't break when that is not passed.

Right, that was the whole point of the inscrutable mess above :(

> (I wonder if it would make sense to have something like
> EXT2_BASE_FLAGS that could include any flags which never hurt,
> currently apparently only EXT2_FLAG_64BITS. From the name of the flag
> EXT2_FLAG_64BITS it's not obvious that you should always use it. As
> far as I understand correctly, it's there only for ABI compatibility
> with code compiled before the flag was introduced and it never makes
> sense to not pass it in any new code.)
> 
> The patch below unbreaks the code (well, at least resize2fs
> modified to not pass EXT2_FLAG_64BITS) for me.

Thanks; I am actually just now testing my own patch, I wasn't sure if
you were around and I wanted to get this fixed.  :)

Mine is more invasive, with all of the full-on inscrutable redirection
mess every other bitmap function uses ;)  But maybe that's not necessary
for this new function, since there will be no old users of it.

We probably need a way to test at least every binary in e2fsprogs
with the 64-bit flags off, to be sure that old apps won't break.

For now I just edited every util which set the 64 bit flag and turned
that off, and ran make check.

I may send my patch as well, and see what Ted thinks is the best
fit for the current code layout... yours is simpler, and without
any API concerns/constraints, it may be better.

Thanks,
- -Eric

> 	Sami Liedes
> 
> ------------------------------------------------------------
> 
> commit bb8fe012a3b1705809f6129cd9c78d2cd855b1f8
> Author: Sami Liedes <sami.liedes@iki.fi>
> Date:   Fri Apr 6 22:06:30 2012 +0300
> 
>     Fix ext2fs_find_first_zero_generic_bmap() for 32-bit bitmaps.
>     
>     ext2fs_find_first_zero_generic_bmap() tries to handle old-style 32-bit
>     bitmaps, but fails in several different ways.
>     
>     Fix the order of the (in)validity tests and the fallback code to never
>     dereference the bitmap, as we don't know at that point if it's a
>     32-bit bitmap or a 64-bitmap bitmap whose backend implementation does
>     not support find_first_zero(). Use the generic bitop functions for
>     everything instead.
>     
>     Addresses-Red-Hat-Bugzilla: #808421
>     
>     Signed-off-by: Sami Liedes <sami.liedes@iki.fi>
>     Reported-by: Richard W.M. Jones <rjones@redhat.com>
> 
> diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
> index e765d2c..7e9b8a0 100644
> --- a/lib/ext2fs/gen_bitmap64.c
> +++ b/lib/ext2fs/gen_bitmap64.c
> @@ -770,19 +770,25 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
>  {
>  	int b;
>  
> -	if (bitmap->bitmap_ops->find_first_zero)
> +	if (!bitmap)
> +		return EINVAL;
> +
> +	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero)
>  		return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
>  
> -	if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
> +	if (!EXT2FS_IS_32_BITMAP(bitmap) || bitmap->cluster_bits)
>  		return EINVAL;
>  
> -	if (start < bitmap->start || end > bitmap->end || start > end) {
> +	// We must be careful to not use any of bitmap's fields here,
> +	// as it may actually be the different 32-bit version of the structure
> +	if (start < ext2fs_get_block_bitmap_start(bitmap) ||
> +	    end > ext2fs_get_block_bitmap_end(bitmap) || start > end) {
>  		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
>  		return EINVAL;
>  	}
>  
>  	while (start <= end) {
> -		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
> +		b = ext2fs_test_generic_bitmap(bitmap, start);
>  		if (!b) {
>  			*out = start;
>  			return 0;

-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQIcBAEBAgAGBQJPf0HAAAoJECCuFpLhPd7gGyQP/0qpH0dB55Ys5j70OBXIFtzT
rMqYcE7P+HZ66+zkWKqB2lKtnMLFXGxDkeQGQ4ECxrucKpcWWrwLSyvB11Py41rV
wal5Uymg41Q7lRjfnYeraKsObeT9VNlV5d/i1TVRZNG0ooHni/9loEShHnKUnlKs
kOROEFu6x/MHNTGeXtmU3aE2l9SCePJn3rQZHQrTeDo5/hm7lQwPUvTmk5Jg8F/v
uNW9zdnPOOvcSF1nmy8P32GKE750GwcrctVe0S9UUtiGr5XPSW7RdnynELRm/6kh
qpGv4v1dPjmG/uJvltxiKymhSv6zoj9NDqEz5V/iISrBvY108WWBFJVpp/EfgMph
luIPUV1zQ5KwQNyHSHgeGCuwa8R02I2sDwXQ/ZyZomOATK1dJ8s6ODkSFUL1pP3k
xZmnWJM9cw4pagCEagyvD6OtT43vvSVakPKxZGE/U67tVxLNZrzmGm79glDMhs70
xed0T5lYZoJEfoMAfLMW7CQYsceRs7bNLfBos1XL8vMhoq0ak8sXmSIiEzzHPOPK
scM+jKtisDqZE9s3j1LgA+aXhmag4/RwO8zTq0gNmZVD4slqbFXVXuIFjFbFR61i
F6ttZROBvo+//C7E7F1AXytCCvhPVQKgDH1aUq92mUmHsKh3CSEwr4BA+E+7+iOj
2WiGb4k3ZI0AcjcZljOi
=9/4M
-----END PGP SIGNATURE-----

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Eric Sandeen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 4/6/12 12:19 PM, Eric Sandeen wrote:

...

> Thanks; I am actually just now testing my own patch, I wasn't sure if
> you were around and I wanted to get this fixed.  :)
> 
> Mine is more invasive, with all of the full-on inscrutable redirection
> mess every other bitmap function uses ;)  But maybe that's not necessary
> for this new function, since there will be no old users of it.
> 
> We probably need a way to test at least every binary in e2fsprogs
> with the 64-bit flags off, to be sure that old apps won't break.
> 
> For now I just edited every util which set the 64 bit flag and turned
> that off, and ran make check.
> 
> I may send my patch as well, and see what Ted thinks is the best
> fit for the current code layout... yours is simpler, and without
> any API concerns/constraints, it may be better.

Ok, I also tested your patch through make check
with the 64 bit flags off on all the normal utils, and it passed (for all
but the one test which exclusively requires 64-bit bitmaps).  It seems fine
to me, thanks.

However, there seems to be some unstated (?) naming convention about foo_bmap
(for 64-bit bitmaps) vs. foo_bitmap (for 32-bit bitmaps), and "bitmap2"
functions which seem to take 64-bit args, etc.  I'm not sure if this new
function needs to follow similar conventions...

My patch is probably overkill, so I won't bother to send it unless Ted
thinks something like that is necessary.  Documenting the api preservation
framework for 64-bit bitmaps would be really helpful, I think.

- -Eric
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQIcBAEBAgAGBQJPf0SMAAoJECCuFpLhPd7ggW4QAJPYaqG9iW6sSg60ySNPlXTW
OM7DF5CAvexUTXFChNyh8C40UpEEo8ms//Etc+G46vSoOjlg3ZvBbmP0fOk8hBhE
ejsNSATpBSwvrgzV8gBi5ZNK6WmefC8PxKXiw17p0gn5oYjKTfBmeFmEjx0oHEGV
zN/BYGDBnzE4n7BGfAACOOZy1HZsWMd2Ud57OpoCsxoB73JrHcz6MEkeGBFqrBBu
WIIPPt4jr6aaEbg2ofQkfJoP3FTHY/tVu8ozAakVWA9AQ/RC3S++9gH44ir4gfYS
PWHUJkNtHn9izcvIlUgly4Vn5s+/Fghyz09qc4LuEzZHwB2NpWHmDsKIrTsIrfWL
f0RI/8uhXdh6T8hhxcYOc0O0vz8iW3k286lr/FzHaX4kXj4yMw4Kf4sMds+v67Zf
aMaQLR+l/UBQeq/vdsrLJcVqMFXovGUH6zmzsplDv98Kl3Lt0gmQHpROqOZPENtb
wvR3ZU4eexcGQxSF0HZtbdhY/PemsYkdSceven5rGr9MXWJUkbhX0wSuXE8jnb7h
wRs/jAvLlAgaPgygAv7eYdccXl069vlFaFHDnoEePlK4lsPC8VpdisxECRjguyz1
nzM6fM9ci3KiGoFBvpwToRL4jos+fUlBnsLQ2v2x1kOGdq8jiJ9C4P3vuz6iE6ZY
WD5TAC8TAzy4+MSx7Gu+
=HKbk
-----END PGP SIGNATURE-----

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Sami Liedes]

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

On Fri, Apr 06, 2012 at 12:31:25PM -0700, Eric Sandeen wrote:
> However, there seems to be some unstated (?) naming convention about foo_bmap
> (for 64-bit bitmaps) vs. foo_bitmap (for 32-bit bitmaps), and "bitmap2"
> functions which seem to take 64-bit args, etc.  I'm not sure if this new
> function needs to follow similar conventions...

I guess... I thought I had figured those out when I sent the patch,
but I'm not so sure anymore :-)

> My patch is probably overkill, so I won't bother to send it unless Ted
> thinks something like that is necessary.  Documenting the api preservation
> framework for 64-bit bitmaps would be really helpful, I think.

Yeah, I'm sorry it took me a while to look at this and for causing you
extra work.

	Sami

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Eric Sandeen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 4/6/12 12:47 PM, Sami Liedes wrote:
> On Fri, Apr 06, 2012 at 12:31:25PM -0700, Eric Sandeen wrote:
>> However, there seems to be some unstated (?) naming convention about foo_bmap
>> (for 64-bit bitmaps) vs. foo_bitmap (for 32-bit bitmaps), and "bitmap2"
>> functions which seem to take 64-bit args, etc.  I'm not sure if this new
>> function needs to follow similar conventions...
> 
> I guess... I thought I had figured those out when I sent the patch,
> but I'm not so sure anymore :-)
> 
>> My patch is probably overkill, so I won't bother to send it unless Ted
>> thinks something like that is necessary.  Documenting the api preservation
>> framework for 64-bit bitmaps would be really helpful, I think.
> 
> Yeah, I'm sorry it took me a while to look at this and for causing you
> extra work.

No worries, I could have waited, too ;)  Thanks!

- -Eric
 
> 	Sami

-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQIcBAEBAgAGBQJPf0jAAAoJECCuFpLhPd7g2V8P/Rdmakt3hb1mh0C7eu01Cpxw
X16f5Axzhsn0c0bfZsKeEZLB6bM+5TYdlARXATxfnVEZ/upbyCsF6bqZ0I5JxHj5
wTRuB7pwl8E+7vBANOu7aI7YT1Vb0eM2i3zIRONeqkYYYbRGllKeUPCdibnL2T5+
ybiAp2tXLR665LYtt0xcHVQ63L0NfYiditmpoMpxWKNfbu4OGhnpTw6bouzzdg1f
KeXQkMdd26oIl8myrp/zkuHCUtja9aSmv4KrcMcxOuFyCqCuyrQpwDx78fmKpnn8
njy/dqI2QY9c/FmScYcXyAQ6/SJ2gkzjm60dkLT8DvPYLky0ytdQQ3JeFh/kBZX9
iGnRSj+fPjujVtzG73x5d5Q8ayzr6jGR94Vm/krvBJ4Yz5GBJkcuR16/8Lmze8au
oKbaKx4PrvuRqD4PEKzmfkUpVFK0GDbXkKgG0wycU/qaFa8hrTrjIo3web3wNbUc
lZExrKB4Pazu65xrQHQih1uENzlJlC1vkhi99oqnrRDmc4/bvuprp//X9SxboGV+
nglwMEEFL7djPM4GSUMWEFz3qTDLZIXqjPV9XfJJvk6G62BbOHn2Q5YfIsyjNQOx
Wr26EkiGui5OXRAAJ9EYdqtSjip1CPyM05CibOQJeZLDZREmchgJKE0PMcLdWziV
y0l4cQNDitg/8ruuBMKk
=jMuN
-----END PGP SIGNATURE-----

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Richard W.M. Jones]

On Fri, Apr 06, 2012 at 10:14:01PM +0300, Sami Liedes wrote:
> While I suggest passing EXT2_FLAG_64BITS to ext2fs_open() - it should
> never break anything and only makes things faster [...]

Thanks -- good to know, and this is what we did to fix febootstrap.

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
New in Fedora 11: Fedora Windows cross-compiler. Compile Windows
programs, test, and build Windows installers. Over 70 libraries supprt'd
http://fedoraproject.org/wiki/MinGW http://www.annexia.org/fedora_mingw

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Ted Ts'o]

I was flying back from San Francisco so I decided to take a look at
this while I was flying back.  So my patches overlapped with yours....

I think mine will be a tad bit faster for the fallback path since we
don't end up doing the 32-bit/64-bit each time we test a bit (since I
created a 32-bit and 64-bit ffz function). 

On Fri, Apr 06, 2012 at 10:14:01PM +0300, Sami Liedes wrote:
> 
> Argh, indeed. I thought the 32-bit bitfields also have the bitmap_ops
> field (and in the same offset), but they don't.

Yeah, the only thing which is the same is the offset.  The structure
definition is in gen_bitmap.c and gen_bitmap64.c, and they are
different depending on whether it is a 32-bit or 64-bit bitmap.

> > I am a little confused by the existence of two different
> > struct ext2fs_struct_generic_bitmap's in the code.  But treating one as the
> > other looks doomed to failure ;)
> 
> In addition to that, there are actually three different versions of
> many operations; they are named ext2_foo_bmap(), ext2_foo_bitmap() and
> ext2_foo_bitmap2(). I'm quite confused too.

Well, actually there are four.  The original 32-bit code has generic
bitmap code that is where most of the implementation exists.  Then we
have separate versions for block and inode bitmaps for the purposes of
type checking.

Then in the 64-bit code, we have the same thing; generic versions plus
block/inode specific versions, plus of course the multiple different
back-end implementations.

I've added test cases to exercise all of this code, which should
prevent problems in the future.  I expect that after we add a
find_first_set function, it's unlikely we'll need to be touching the
bitmap implementations again for the near future....

       		       	     	     	  - Ted

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Ted Ts'o]

On Fri, Mar 30, 2012 at 02:19:36PM +0100, Richard W.M. Jones wrote:
> 
> A bit of further investigation:
> 
> I'm currently not passing EXT2_FLAG_64BITS when opening the
> filesystem.  Passing this flag fixes the issue, so I'm going to do
> that (are there any downsides?)

No, there are no downsides with passing in EXT2_FLAG_64BITS (and it's
actually a good idea in case Fedora ever supports booting on ext4 file
systems with block numbers > 32 bits).  Still, it should have worked.

I'll chain the patches which should fix this to this message.

     	       	       	     	    	- Ted

[PATCH 1/3] libext2fs: add 32-bit compat code for ext2fs_find_first_zero_generic_bmap()

[Theodore Ts'o]

The lack of 32-bit support was causing febootstrap to crash since it
wasn't passing EXT2_FLAG_64BITS when opening the file system, so we
were still using the legacy bitmaps.

Addresses-Red-Hat-Bugzilla: #808421

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/ext2fs.h       |    3 +++
 lib/ext2fs/gen_bitmap.c   |   25 +++++++++++++++++++++++++
 lib/ext2fs/gen_bitmap64.c |   32 ++++++++++++++++++++++++++++----
 3 files changed, 56 insertions(+), 4 deletions(-)

diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 68e94a3..fda6ade 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1169,6 +1169,9 @@ extern errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
 						 errcode_t magic,
 						 __u32 start, __u32 num,
 						 void *in);
+extern errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap,
+						       __u32 start, __u32 end,
+						       __u32 *out);
 
 /* gen_bitmap64.c */
 
diff --git a/lib/ext2fs/gen_bitmap.c b/lib/ext2fs/gen_bitmap.c
index 6679bff..0bff854 100644
--- a/lib/ext2fs/gen_bitmap.c
+++ b/lib/ext2fs/gen_bitmap.c
@@ -504,6 +504,30 @@ static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap,
 	return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
 }
 
+errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap,
+						__u32 start, __u32 end,
+						__u32 *out)
+{
+	blk_t b;
+
+	if (start < bitmap->start || end > bitmap->end || start > end) {
+		ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
+		return EINVAL;
+	}
+
+	while (start <= end) {
+		b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap);
+		if (!b) {
+			*out = start;
+			return 0;
+		}
+		start++;
+	}
+
+	return ENOENT;
+}
+
+
 int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
 				   blk_t block, int num)
 {
@@ -558,3 +582,4 @@ void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 		ext2fs_fast_clear_bit(block + i - bitmap->start,
 				      bitmap->bitmap);
 }
+
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index e765d2c..07d6d52 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -770,12 +770,36 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 {
 	int b;
 
-	if (bitmap->bitmap_ops->find_first_zero)
-		return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
+	if (!bitmap)
+		return EINVAL;
 
-	if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
+	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero)
+		return bitmap->bitmap_ops->find_first_zero(bitmap, start,
+							   end, out);
+
+	if (EXT2FS_IS_32_BITMAP(bitmap)) {
+		blk_t blk = 0;
+		errcode_t retval;
+
+		if (((start) & ~0xffffffffULL) ||
+		    ((end) & ~0xffffffffULL)) {
+			ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
+			return EINVAL;
+		}
+
+		retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
+							       end, &blk);
+		if (retval == 0)
+			*out = blk;
+		return retval;
+	}
+
+	if (!EXT2FS_IS_64_BITMAP(bitmap))
 		return EINVAL;
 
+	start >>= bitmap->cluster_bits;
+	end >>= bitmap->cluster_bits;
+
 	if (start < bitmap->start || end > bitmap->end || start > end) {
 		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
 		return EINVAL;
@@ -784,7 +808,7 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 	while (start <= end) {
 		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
 		if (!b) {
-			*out = start;
+			*out = start << bitmap->cluster_bits;
 			return 0;
 		}
 		start++;
-- 
1.7.10.rc3

[PATCH 2/3] libext2fs: use correct types in ext2fs_find_first_zero_block_bitmap2()

[Theodore Ts'o]

Fortunately nothing was using this inline function, so we'll just fix
the types in its function signature, which were nonsensical (this was
caused by a cut-and-paste error).

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/bitops.h |   12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h
index 9382790..ae2142c 100644
--- a/lib/ext2fs/bitops.h
+++ b/lib/ext2fs/bitops.h
@@ -153,9 +153,9 @@ extern void ext2fs_fast_unmark_inode_bitmap2(ext2fs_inode_bitmap bitmap,
 extern int ext2fs_fast_test_inode_bitmap2(ext2fs_inode_bitmap bitmap,
 					  ext2_ino_t inode);
 extern errcode_t ext2fs_find_first_zero_block_bitmap2(ext2fs_block_bitmap bitmap,
-						      ext2_ino_t start,
-						      ext2_ino_t end,
-						      ext2_ino_t *out);
+						      blk64_t start,
+						      blk64_t end,
+						      blk64_t *out);
 extern errcode_t ext2fs_find_first_zero_inode_bitmap2(ext2fs_inode_bitmap bitmap,
 						      ext2_ino_t start,
 						      ext2_ino_t end,
@@ -605,9 +605,9 @@ _INLINE_ int ext2fs_fast_test_inode_bitmap2(ext2fs_inode_bitmap bitmap,
 }
 
 _INLINE_ errcode_t ext2fs_find_first_zero_block_bitmap2(ext2fs_block_bitmap bitmap,
-							ext2_ino_t start,
-							ext2_ino_t end,
-							ext2_ino_t *out)
+							blk64_t start,
+							blk64_t end,
+							blk64_t *out)
 {
 	__u64 o;
 	errcode_t rv;
-- 
1.7.10.rc3

[PATCH 3/3] libext2fs: improve testing coverage of tst_bitmaps

[Theodore Ts'o]

Improve the test coverage of tst_bitmaps by:

   (a) adding the ability to test the legacy (32-bit) bitmap code
   (b) adding tests for ext2fs_find_first_zero_inode_bitmap2() and
       ext2fs_find_first_zero_block_bitmap2()

The recent regressions caused by the addition (and use) of
ext2fs_find_first_zero_inode_bitmap2() would have been caught if we
had added these tests first.  (Another object lesson in why unit tests
are critically important!)

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/Makefile.in        |    3 ++
 lib/ext2fs/tst_bitmaps.c      |   88 ++++++++++++++++++++++++++++++++++++++---
 lib/ext2fs/tst_bitmaps_cmd.ct |    6 +++
 lib/ext2fs/tst_bitmaps_cmds   |   11 ++++++
 lib/ext2fs/tst_bitmaps_exp    |   22 +++++++++++
 5 files changed, 124 insertions(+), 6 deletions(-)

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 8840a32..507a459 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -403,6 +403,9 @@ check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
 		./tst_bitmaps -t 3 -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
 	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
+	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
+		./tst_bitmaps -l -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
+	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
 
 installdirs::
 	$(E) "	MKINSTALLDIRS $(libdir) $(includedir)/ext2fs"
diff --git a/lib/ext2fs/tst_bitmaps.c b/lib/ext2fs/tst_bitmaps.c
index 27722e5..22346a2 100644
--- a/lib/ext2fs/tst_bitmaps.c
+++ b/lib/ext2fs/tst_bitmaps.c
@@ -151,7 +151,7 @@ int check_fs_open(char *name)
 
 static void setup_filesystem(const char *name,
 			     unsigned int blocks, unsigned int inodes,
-			     unsigned int type)
+			     unsigned int type, int flags)
 {
 	struct ext2_super_block param;
 	errcode_t retval;
@@ -160,7 +160,7 @@ static void setup_filesystem(const char *name,
 	ext2fs_blocks_count_set(&param, blocks);
 	param.s_inodes_count = inodes;
 
-	retval = ext2fs_initialize("test fs", EXT2_FLAG_64BITS, &param,
+	retval = ext2fs_initialize("test fs", flags, &param,
 				   test_io_manager, &test_fs);
 
 	if (retval) {
@@ -198,6 +198,7 @@ void setup_cmd(int argc, char **argv)
 	unsigned int	blocks = 128;
 	unsigned int	inodes = 0;
 	unsigned int	type = EXT2FS_BMAP64_BITARRAY;
+	int		flags = EXT2_FLAG_64BITS;
 
 	if (test_fs) {
 		ext2fs_close(test_fs);
@@ -205,7 +206,7 @@ void setup_cmd(int argc, char **argv)
 	}
 
 	reset_getopt();
-	while ((c = getopt(argc, argv, "b:i:t:")) != EOF) {
+	while ((c = getopt(argc, argv, "b:i:lt:")) != EOF) {
 		switch (c) {
 		case 'b':
 			blocks = parse_ulong(optarg, argv[0],
@@ -219,6 +220,9 @@ void setup_cmd(int argc, char **argv)
 			if (err)
 				return;
 			break;
+		case 'l':	/* Legacy bitmaps */
+			flags = 0;
+			break;
 		case 't':
 			type = parse_ulong(optarg, argv[0],
 					   "bitmap backend type", &err);
@@ -231,7 +235,7 @@ void setup_cmd(int argc, char **argv)
 			return;
 		}
 	}
-	setup_filesystem(argv[0], blocks, inodes, type);
+	setup_filesystem(argv[0], blocks, inodes, type, flags);
 }
 
 void close_cmd(int argc, char **argv)
@@ -399,6 +403,40 @@ void do_testb(int argc, char *argv[])
 	printf("Block %u is %s\n", block, test_result ? "set" : "clear");
 }
 
+void do_ffzb(int argc, char *argv[])
+{
+	unsigned int start, end;
+	int err;
+	errcode_t retval;
+	blk64_t out;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 3 && argc != 3) {
+		com_err(argv[0], 0, "Usage: ffzb <start> <end>");
+		return;
+	}
+
+	start = parse_ulong(argv[1], argv[0], "start", &err);
+	if (err)
+		return;
+
+	end = parse_ulong(argv[2], argv[0], "end", &err);
+	if (err)
+		return;
+
+	retval = ext2fs_find_first_zero_block_bitmap2(test_fs->block_map,
+						      start, end, &out);
+	if (retval) {
+		printf("ext2fs_find_first_zero_block_bitmap2() returned %s\n",
+		       error_message(retval));
+		return;
+	}
+	printf("First unmarked block is %llu\n", out);
+}
+
+
 void do_zerob(int argc, char *argv[])
 {
 	if (check_fs_open(argv[0]))
@@ -488,6 +526,40 @@ void do_testi(int argc, char *argv[])
 	printf("Inode %u is %s\n", inode, test_result ? "set" : "clear");
 }
 
+void do_ffzi(int argc, char *argv[])
+{
+	unsigned int start, end;
+	int err;
+	errcode_t retval;
+	ext2_ino_t out;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 3 && argc != 3) {
+		com_err(argv[0], 0, "Usage: ffzi <start> <end>");
+		return;
+	}
+
+	start = parse_ulong(argv[1], argv[0], "start", &err);
+	if (err)
+		return;
+
+	end = parse_ulong(argv[2], argv[0], "end", &err);
+	if (err)
+		return;
+
+	retval = ext2fs_find_first_zero_inode_bitmap2(test_fs->inode_map,
+						      start, end, &out);
+	if (retval) {
+		printf("ext2fs_find_first_zero_inode_bitmap2() returned %s\n",
+		       error_message(retval));
+		return;
+	}
+	printf("First unmarked inode is %u\n", out);
+}
+
+
 void do_zeroi(int argc, char *argv[])
 {
 	if (check_fs_open(argv[0]))
@@ -506,10 +578,11 @@ int main(int argc, char **argv)
 	char		*request = (char *)NULL;
 	char		*cmd_file = 0;
 	int		sci_idx;
+	int		flags = EXT2_FLAG_64BITS;
 
 	add_error_table(&et_ss_error_table);
 	add_error_table(&et_ext2_error_table);
-	while ((c = getopt (argc, argv, "b:i:t:R:f:")) != EOF) {
+	while ((c = getopt (argc, argv, "b:i:lt:R:f:")) != EOF) {
 		switch (c) {
 		case 'b':
 			blocks = parse_ulong(optarg, argv[0],
@@ -523,6 +596,9 @@ int main(int argc, char **argv)
 			if (err)
 				return;
 			break;
+		case 'l':	/* Legacy bitmaps */
+			flags = 0;
+			break;
 		case 't':
 			type = parse_ulong(optarg, argv[0],
 					   "bitmap backend type", &err);
@@ -558,7 +634,7 @@ int main(int argc, char **argv)
 	printf("%s %s.  Type '?' for a list of commands.\n\n",
 	       subsystem_name, version);
 
-	setup_filesystem(argv[0], blocks, inodes, type);
+	setup_filesystem(argv[0], blocks, inodes, type, flags);
 
 	if (request) {
 		code = ss_execute_line(sci_idx, request);
diff --git a/lib/ext2fs/tst_bitmaps_cmd.ct b/lib/ext2fs/tst_bitmaps_cmd.ct
index 5a51d23..1e1e5d3 100644
--- a/lib/ext2fs/tst_bitmaps_cmd.ct
+++ b/lib/ext2fs/tst_bitmaps_cmd.ct
@@ -21,6 +21,9 @@ request do_clearb, "Clear block",
 request do_testb, "Test block",
 	test_block, testb;
 
+request do_ffzb, "Find first zero block",
+	find_first_zero_block, ffzb;
+
 request do_zerob, "Clear block bitmap",
 	clear_block_bitmap, zerob;
 
@@ -33,6 +36,9 @@ request do_cleari, "Clear inode",
 request do_testi, "Test inode",
 	test_inode, testi;
 
+request do_ffzi, "Find first zero inode",
+	find_first_zero_inode, ffzi;
+
 request do_zeroi, "Clear inode bitmap",
 	clear_inode_bitmap, zeroi;
 
diff --git a/lib/ext2fs/tst_bitmaps_cmds b/lib/ext2fs/tst_bitmaps_cmds
index 13f4ea8..9a4f3d0 100644
--- a/lib/ext2fs/tst_bitmaps_cmds
+++ b/lib/ext2fs/tst_bitmaps_cmds
@@ -16,6 +16,12 @@ testb 11
 testb 15
 testb 16
 dump_bb
+ffzb 11 16
+ffzb 12 16
+ffzb 12 20
+clearb 13
+ffzb 12 20
+setb 13
 clearb 12 7
 testb 12 7
 setb 15
@@ -33,6 +39,11 @@ seti 5
 testi 6
 testi 1
 dump_ib
+ffzi 1 6
+ffzi 2 5
+ffzi 2 6
+cleari 4
+ffzi 2 6
 zeroi
 testi 5
 seti 5
diff --git a/lib/ext2fs/tst_bitmaps_exp b/lib/ext2fs/tst_bitmaps_exp
index aa64ae7..2d406ce 100644
--- a/lib/ext2fs/tst_bitmaps_exp
+++ b/lib/ext2fs/tst_bitmaps_exp
@@ -36,6 +36,18 @@ tst_bitmaps: testb 16
 Block 16 is set
 tst_bitmaps: dump_bb
 block bitmap: 00f80000000000000000000000000000
+tst_bitmaps: ffzb 11 16
+First unmarked block is 11
+tst_bitmaps: ffzb 12 16
+ext2fs_find_first_zero_block_bitmap2() returned No such file or directory
+tst_bitmaps: ffzb 12 20
+First unmarked block is 17
+tst_bitmaps: clearb 13
+Clearing block 13, was set before
+tst_bitmaps: ffzb 12 20
+First unmarked block is 13
+tst_bitmaps: setb 13
+Setting block 13, was clear before
 tst_bitmaps: clearb 12 7
 Clearing blocks 12 to 18
 tst_bitmaps: testb 12 7
@@ -70,6 +82,16 @@ tst_bitmaps: testi 1
 Inode 1 is clear
 tst_bitmaps: dump_ib
 inode bitmap: 1e000000
+tst_bitmaps: ffzi 1 6
+First unmarked inode is 1
+tst_bitmaps: ffzi 2 5
+ext2fs_find_first_zero_inode_bitmap2() returned No such file or directory
+tst_bitmaps: ffzi 2 6
+First unmarked inode is 6
+tst_bitmaps: cleari 4
+Clearing inode 4, was set before
+tst_bitmaps: ffzi 2 6
+First unmarked inode is 4
 tst_bitmaps: zeroi
 Clearing inode bitmap.
 tst_bitmaps: testi 5
-- 
1.7.10.rc3

Re: [PATCH 1/3] libext2fs: add 32-bit compat code for ext2fs_find_first_zero_generic_bmap()

[Eric Sandeen]

On 4/6/12 11:59 AM, Theodore Ts'o wrote:
> The lack of 32-bit support was causing febootstrap to crash since it
> wasn't passing EXT2_FLAG_64BITS when opening the file system, so we
> were still using the legacy bitmaps.

Thanks Ted, these look good (and similar to the patch path I was going down)

-Eric

> Addresses-Red-Hat-Bugzilla: #808421
> 
> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> ---
>  lib/ext2fs/ext2fs.h       |    3 +++
>  lib/ext2fs/gen_bitmap.c   |   25 +++++++++++++++++++++++++
>  lib/ext2fs/gen_bitmap64.c |   32 ++++++++++++++++++++++++++++----
>  3 files changed, 56 insertions(+), 4 deletions(-)
> 
> diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
> index 68e94a3..fda6ade 100644
> --- a/lib/ext2fs/ext2fs.h
> +++ b/lib/ext2fs/ext2fs.h
> @@ -1169,6 +1169,9 @@ extern errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
>  						 errcode_t magic,
>  						 __u32 start, __u32 num,
>  						 void *in);
> +extern errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap,
> +						       __u32 start, __u32 end,
> +						       __u32 *out);
>  
>  /* gen_bitmap64.c */
>  
> diff --git a/lib/ext2fs/gen_bitmap.c b/lib/ext2fs/gen_bitmap.c
> index 6679bff..0bff854 100644
> --- a/lib/ext2fs/gen_bitmap.c
> +++ b/lib/ext2fs/gen_bitmap.c
> @@ -504,6 +504,30 @@ static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap,
>  	return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
>  }
>  
> +errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap,
> +						__u32 start, __u32 end,
> +						__u32 *out)
> +{
> +	blk_t b;
> +
> +	if (start < bitmap->start || end > bitmap->end || start > end) {
> +		ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
> +		return EINVAL;
> +	}
> +
> +	while (start <= end) {
> +		b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap);
> +		if (!b) {
> +			*out = start;
> +			return 0;
> +		}
> +		start++;
> +	}
> +
> +	return ENOENT;
> +}
> +
> +
>  int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
>  				   blk_t block, int num)
>  {
> @@ -558,3 +582,4 @@ void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
>  		ext2fs_fast_clear_bit(block + i - bitmap->start,
>  				      bitmap->bitmap);
>  }
> +
> diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
> index e765d2c..07d6d52 100644
> --- a/lib/ext2fs/gen_bitmap64.c
> +++ b/lib/ext2fs/gen_bitmap64.c
> @@ -770,12 +770,36 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
>  {
>  	int b;
>  
> -	if (bitmap->bitmap_ops->find_first_zero)
> -		return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
> +	if (!bitmap)
> +		return EINVAL;
>  
> -	if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
> +	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero)
> +		return bitmap->bitmap_ops->find_first_zero(bitmap, start,
> +							   end, out);
> +
> +	if (EXT2FS_IS_32_BITMAP(bitmap)) {
> +		blk_t blk = 0;
> +		errcode_t retval;
> +
> +		if (((start) & ~0xffffffffULL) ||
> +		    ((end) & ~0xffffffffULL)) {
> +			ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
> +			return EINVAL;
> +		}
> +
> +		retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
> +							       end, &blk);
> +		if (retval == 0)
> +			*out = blk;
> +		return retval;
> +	}
> +
> +	if (!EXT2FS_IS_64_BITMAP(bitmap))
>  		return EINVAL;
>  
> +	start >>= bitmap->cluster_bits;
> +	end >>= bitmap->cluster_bits;
> +
>  	if (start < bitmap->start || end > bitmap->end || start > end) {
>  		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
>  		return EINVAL;
> @@ -784,7 +808,7 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
>  	while (start <= end) {
>  		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
>  		if (!b) {
> -			*out = start;
> +			*out = start << bitmap->cluster_bits;
>  			return 0;
>  		}
>  		start++;

Re: Commit c1a1e7fc24d6 causes segfault in ext2fs_new_inode

[Eric Sandeen]

On 3/30/12 5:57 AM, Richard W.M. Jones wrote:
> [I'm tracking this issue here:
> https://bugzilla.redhat.com/show_bug.cgi?id=808421]
> 
> febootstrap uses the ext2fs library to construct an ext2 filesystem.
> 
> Since we updated to the latest version in git, febootstrap segfaults
> in ext2fs_find_first_zero_generic_bmap (called from ext2fs_new_inode).
> There's a complete stack trace in the bug above.
> 
> I'm not claiming that we are calling this library correctly, but,
> you know, "it always worked until now".

Sami, can you take a look at this one?  It seems that your commit does
not handle 32-bit bitmaps.

Thanks,
-Eric

> Here is the calling code:
> 
> https://github.com/libguestfs/febootstrap/blob/636a80b5a70382f21da47c44a0acd3efa2bc7fcf/helper/ext2.c#L142
> 
> git bisect points to this change being the one which causes the
> problem:
> 
> c1a1e7fc24d6e37f931bbb8eeb29c90243f0a55d is the first bad commit
> commit c1a1e7fc24d6e37f931bbb8eeb29c90243f0a55d
> Author: Sami Liedes <sami.liedes@iki.fi>
> Date:   Sat Mar 10 22:36:12 2012 +0200
> 
>     libext2fs: Implement ext2fs_find_first_zero_generic_bmap().
>     
>     This function searches a bitmap for the first zero bit within a range.
>     It checks if there is a bitmap backend specific implementation
>     available (if the relevant field in bitmap_ops is non-NULL). If not,
>     it uses a generic and slow method by repeatedly calling test_bmap() in
>     a loop. Also change ext2fs_new_inode() to use this new function.
>     
>     This change in itself does not result in a large speedup, rather it
>     refactors the code in preparation for the introduction of a faster
>     find_first_zero() for bitarray based bitmaps.
>     
>     Signed-off-by: Sami Liedes <sami.liedes@iki.fi>
>     Signed-off-by: Theodore Ts'o <tytso@mit.edu>
> 
> Rich.
>