linux-ext4 - Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <5D9B4A3A-D5F9-4F94-ADA7-2E2CE88FAEE5@dilger.ca>
Date:	Mon, 12 Mar 2012 17:09:50 -0600
From:	Andreas Dilger <adilger@...ger.ca>
To:	Sami Liedes <sami.liedes@....fi>
Cc:	linux-ext4@...r.kernel.org
Subject: Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

On 2012-03-12, at 1:15 PM, Sami Liedes wrote:
> On Sun, Mar 11, 2012 at 03:51:05AM -0600, Andreas Dilger wrote:
>> Rather than making the bitmap searching loop more efficient, I've always thought
>> it would be better to have an interface that iterates over the bitmap and returns
>> the next set bit.  It is similar to what you implemented with ->find_first_zero(),
>> but it would be better to have (IMHO) ->find_next_zero() and ->find_next_set().
> 
> I've been thinking about this. Such an interface might be a good idea,
> and I could implement it and a corresponding backend implementation
> for the bit array backend, but I don't think ext2fs_new_inode() could
> properly exercise it and I'm hesitant to submit code that isn't tested
> by being actually properly used somewhere.

It is actually common practise in e2fsprogs to embed test programs in the
code being modified.  See tst_bitmaps.c, for example.  That can give you
better test coverage for rarely executed code, and the tests should be run
by anyone modifying the e2fsprogs code and for every RPM build.

The ext2fs_new_block2() function could be improved in a similar manner, and
in fact benefits even more than the inode allocator, because far more blocks
are allocated under normal usage.

> I will still do it if there's a general consensus that it's a good idea.

Let's hear back from Ted first.  He will probably have some good feedback on
the API design that he would like.

> It could be something along the lines of
> 
> * type ext2fs_bitmap_iterator, opaque to calling code, mainly a magic
>  number and backend-specific private data. In the bitarray case it
>  could just be the number of the bit pointed to and the end of the
>  range to iterate.
> 
> * bool bitmap_ops->deref_iterator(ext2fs_generic_bitmap, ext2fs_bitmap_iterator)
> 
> * ext2fs_bitmap_iterator ops->create_iterator()
>                            ->create_ranged_iterator(__u64 start, __u64 end)
>                            ->free_iterator(ext2fs_bitmap_iterator) 
> 
> * __u64 bitmap_ops->iterator_position(...)
> 
> * errcode_t ops->find_next_zero(..., __u64 *pos),
>               ->find_next_set(..., __u64 *pos)
>  * These would both increment the iterator and, if pos != NULL, set
>    *pos to the new bit position
> 
> * Modifying a bitmap invalidates all its iterators in such a way that
>  the only legal operation for them afterwards is ->free_iterator()

Note that there is already the rbtree bitmap implementation, which is needed
for huge filesystems in order to be able to run e2fsck without needing huge
amounts of RAM, so it should also have a backend iterator implementation.

> In the case of ext2fs_new_inode(), the function does not actually
> iterate through all zero bits; it really only wants to find the first
> zero in a certain range, after which it returns. So for simplicity of
> use (and efficiency) I think it still makes sense to have
> ->find_first_zero() too.
> 
> 	Sami

Cheers, Andreas

Download attachment "PGP.sig" of type "application/pgp-signature" (236 bytes)