linux-kernel - Re: [PATCH] lib/bitmap: rework bitmap

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: <20200307143243.0ec974da@elisabeth>
Date:   Sat, 7 Mar 2020 14:32:43 +0100
From:   Stefano Brivio <sbrivio@...hat.com>
To:     Yury Norov <yury.norov@...il.com>
Cc:     Pablo Neira Ayuso <pablo@...filter.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH] lib/bitmap: rework bitmap_cut()

On Sat, 7 Mar 2020 00:12:08 -0800
Yury Norov <yury.norov@...il.com> wrote:

> On Sat, Mar 07, 2020 at 12:18:56AM +0100, Stefano Brivio wrote:
> > Hi Yuri,
> > 
> > I haven't reviewed the new implementation yet, just a few comments so
> > far:
> > 
> > On Fri,  6 Mar 2020 14:14:23 -0800
> > Yury Norov <yury.norov@...il.com> wrote:
> >   
> > > bitmap_cut() refers src after memmove(). If dst and src overlap,
> > > it may cause buggy behaviour because src may become inconsistent.  
> > 
> > I don't see how: src is always on the opposite side of the cut compared
> > to dst, and bits are copied one by one.  
> 
> Consider this example:
> int main()
> {
> 	char str[] = "Xabcde";
> 	char *s = str+1;
> 	char *d = str; // overlap
> 
> 	memmove(d, s, 5);
> 	printf("%s\n", s);
> 	printf("%s\n", d);
> }
> 
> yury:linux$ ./a.out
> bcdee
> abcdee
> 
> After memmove(), s[0] == 'b', which is wrong.
> 
> In current version src is used after memmove() to set 'keep', which
> may cause similar problem

Ah, yes, good point. This doesn't happen on a complete overlap (current
usage), but I see what you meant now.

Actually, to fix this, it would be enough to move the assignment of
'keep' before the memmove(), or assign 'keep' from 'dst'.

> > Also note that I originally designed this function for the single usage
> > it has, that is, with src being the same as dst, and this is the only
> > way it is used, so this case is rather well tested. Do you have any
> > specific case in mind?  
> 
> No. Do you have in mind a dst != src usecase?

I don't, I was just wondering about the reason behind your patch.

> > > The function complexity is of O(nbits * cut_bits), which can be
> > > improved to O(nbits).  
> > 
> > Nice, indeed.
> >   
> > > We can also rely on bitmap_shift_right() to do most of the work.  
> > 
> > Also nice.
> >   
> > > I don't like interface of bitmap_cut(). The idea of copying of a
> > > whole bitmap inside the function from src to dst doesn't look
> > > useful in practice. The function is introduced a few weeks ago and
> > > was most probably inspired by bitmap_shift_*. Looking at the code,
> > > it's easy to see that bitmap_shift_* is usually passed with
> > > dst == src. bitmap_cut() has a single user so far, and it also
> > > calls it with dst == src.  
> > 
> > I'm not fond of it either, but this wasn't just "inspired" by
> > bitmap_shift_*: I wanted to maintain a consistent interface with those,
> > and all the other functions of this kind taking separate dst and src.
> > 
> > For the current usage, performance isn't exceedingly relevant. If you
> > have another use case in mind where it's relevant, by all means, I
> > think it makes sense to change the interface.
> > 
> > Otherwise, I would still have a slight preference towards keeping the
> > interface consistent.  
> 
> There is no consistent interface. Bitmap_{set,clear) uses one
> notaton, bitmap_{and,or,shift) - another. I think that 'unary'
> operations should not copy the whole bitmap. If user wants, he
> can easily do it. In practice, nobody wants.

bitmap_set() and bitmap_clear() are conceptually in another class, I
think.

In any case, I agree that (map-wise) unary operations should naturally
not copy bitmaps, but I'm still not convinced that "fixing" this just
for bitmap_cut() is a good idea -- because of the inconsistency it adds.

How bad would it be to also adjust all usages of bitmap_{and,or,shift}
to behave in the same way?

> > By the way, I don't think it's possible to do that keeping the
> > memmove(), and at the same time implement the rest of this change,
> > because then we might very well hit some unexpected behaviour, using
> > bitmap_shift_right() later.  
> 
> I think it should work. Can you elaborate?

If you keep the memmove(), then use bitmap_shift_right() on dst, some
excess bits will be affected, unless you copy them back from src...
which at that point, you don't have anymore.

-- 
Stefano