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: <20120312191514.GS6961@sli.dy.fi>
Date:	Mon, 12 Mar 2012 21:15:14 +0200
From:	Sami Liedes <sami.liedes@....fi>
To:	Andreas Dilger <adilger@...ger.ca>
Cc:	linux-ext4@...r.kernel.org
Subject: Re: [PATCH 4/5] libext2fs: Implement
 ext2fs_find_first_zero_generic_bmap().

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. I will still do it if
there's a general consensus that it's a good idea.

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()

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

Download attachment "signature.asc" of type "application/pgp-signature" (837 bytes)