Date:   Tue, 24 Jan 2023 11:59:39 -0500
From:   "Theodore Ts'o" <tytso@mit.edu>
To:     Andreas Dilger <adilger@dilger.ca>
Cc:     "Ritesh Harjani (IBM)" <ritesh.list@gmail.com>,
        linux-ext4@vger.kernel.org,
        Harshad Shirwadkar <harshadshirwadkar@gmail.com>,
        Li Xi <lixi@ddn.com>, Wang Shilong <wangshilong1991@gmail.com>
Subject: Re: [RFCv1 02/72] gen_bitmaps: Fix
 ext2fs_compare_generic_bmap/bitmap logic
Message-ID: <Y9AOe+gdM8g36g0d@mit.edu>
References: <cover.1667822611.git.ritesh.list@gmail.com>
 <da2a28305637aef648846f9bf75d269c0f7c6e57.1667822611.git.ritesh.list@gmail.com>
 <687F4A01-A443-4B5A-87B7-5958F2B3267F@dilger.ca>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <687F4A01-A443-4B5A-87B7-5958F2B3267F@dilger.ca>
Precedence: bulk

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@gmail.com> 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@gmail.com>
> > ---
> > 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