On Tue, Nov 22, 2022 at 10:04:58PM -0700, Andreas Dilger wrote: > On Nov 7, 2022, at 5:20 AM, Ritesh Harjani (IBM) <ritesh.list@xxxxxxxxx> wrote: > > > > Currently this function was not correctly comparing against the right > > length of the bitmap. Also when we compare bitarray v/s rbtree bitmap > > the value returned by ext2fs_test_generic_bmap() could be different in > > these two implementations. Hence only check against boolean value. > > > > Signed-off-by: Ritesh Harjani (IBM) <ritesh.list@xxxxxxxxx> > > --- > > lib/ext2fs/gen_bitmap.c | 9 ++++++--- The gen_bitmap.c file supports only the original 32-bit bitmaps, so there is not rbtree bitmap. That's why using memcmp is safe, and as near as I can tell, no changes are needed for the lib/ext2fs/gen_bitmap.c > > diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c > > index c860c10e..f7710afd 100644 > > --- a/lib/ext2fs/gen_bitmap64.c > > +++ b/lib/ext2fs/gen_bitmap64.c > > @@ -629,10 +629,14 @@ errcode_t ext2fs_compare_generic_bmap(errcode_t neq, > > (bm1->end != bm2->end)) > > Conversely, *this* version of the function is *not* doing the memcmp() of > the bulk of the bitmap contents, so it would appear to have a bug that the > patch fixes, but in a very slow manner. It would be better to use memcmp(). This is where we have a problem, and the reason why we can't use memcmp is because in the case where the bitmap is really encoded using an rbtree, a memcmp isn't applicable. We *could* extract the bitmap into a bitarray, but that would require allocating memory, and in the case of a very large file system/bitmap, especially when running on a 32-bit NAS box, we might not be able to *afford* to allocate that much memory (or it might not even be addressable :-). So yes, we need a fix here, and yes, comparing bit by bit is very slow. Fortunately, from what I can tell, no one is actually calling this function, which is why no once noticed that the 64-bit compare bitmap fucntion was totally hosed. So applying Ritesh's fix here makes sense, since it at least fixes the obvious problems. In the long term, we should probably add proper unit regression tests so can test whether or not this function is actually working correctly, and if we *want* a faster version of it, we could do something faster in the case where both bitmaps are the same type (e.g., both bitarrays or both rbtrees), and if they could do something where we look for "runs" where all of the bits are all set or not set, and then compare that against the other bitmap, etc. But given that we don't have anyusers of this function any more (we used to, but it disappeared when we optimzied e2fsck's pass5 implementation), that's probably not an urgent fix. - Ted
