Messages in this thread | | | Date | Sat, 7 Mar 2020 14:32:43 +0100 | From | Stefano Brivio <> | Subject | Re: [PATCH] lib/bitmap: rework bitmap_cut() |
| |
On Sat, 7 Mar 2020 00:12:08 -0800 Yury Norov <yury.norov@gmail.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@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
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
| |