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: <20200307081208.GA21695@yury-thinkpad>
Date:   Sat, 7 Mar 2020 00:12:08 -0800
From:   Yury Norov <yury.norov@...il.com>
To:     Stefano Brivio <sbrivio@...hat.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, 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

> 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?
 
> > 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.

> 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?

> All in all, I don't have a strong preference against this -- but I'm
> not too convinced it makes sense either.
> 
> -- 
> Stefano