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
Attachment:
PGP.sig
Description: This is a digitally signed message part
