Messages in this thread | | | Date | Sat, 7 Mar 2020 00:12:08 -0800 | From | Yury Norov <> | 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@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
| |