lkml.org 
[lkml]   [2020]   [Mar]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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@gmail.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

\
 
 \ /
  Last update: 2020-03-07 09:12    [W:0.066 / U:2.288 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site