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: <20200307001856.5181eda7@elisabeth>
Date:   Sat, 7 Mar 2020 00:18:56 +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()

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.

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?

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

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.

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

-- 
Stefano