linux-kernel - Re: [PATCH v1 2/5] lib/bitmap: Introduce bitmap_scatter() and 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: <ZRQZ2m0Rb/4AkeQ3@smile.fi.intel.com>
Date:   Wed, 27 Sep 2023 15:02:34 +0300
From:   Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
To:     Yury Norov <yury.norov@...il.com>
Cc:     Linus Walleij <linus.walleij@...aro.org>,
        Bartosz Golaszewski <bartosz.golaszewski@...aro.org>,
        linux-gpio@...r.kernel.org, linux-arm-kernel@...ts.infradead.org,
        linux-kernel@...r.kernel.org,
        Shubhrajyoti Datta <shubhrajyoti.datta@....com>,
        Srinivas Neeli <srinivas.neeli@....com>,
        Michal Simek <michal.simek@....com>,
        Bartosz Golaszewski <brgl@...ev.pl>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Marek Behún <kabel@...nel.org>
Subject: Re: [PATCH v1 2/5] lib/bitmap: Introduce bitmap_scatter() and
 bitmap_gather() helpers

On Tue, Sep 26, 2023 at 05:25:13PM -0700, Yury Norov wrote:
> On Tue, Sep 26, 2023 at 08:20:04AM +0300, Andy Shevchenko wrote:
> > These helpers are the optimized versions of the bitmap_remap()
> > where one of the bitmaps (source or destination) is of sequential bits.
> 
> If so, can you add a test that makes sure that new API is consistent
> with the old bitmap_remap? And also provide numbers how well are they
> optimized, comparing to bitmap_remap.

It's impossible. bitmap_remap() is universal, these APIs only for the specific
domain.

> > See more in the kernel documentation of the helpers.
> 
> I grepped the whole kernel, not only Documentation directory, and found
> nothing...

It's added in this patch in the format of kernel doc.

...

> > + * Returns: the weight of the @mask.
> 
> Returning a weight of the mask is somewhat non-trivial... To me it
> would be logical to return a weight of destination, for example...

> But I see that in the following patch you're using the returned value.
> Maybe add a few words to advocate that?

I'll look into it again, maybe dst would work as well, I don't remember why
I have chosen mask. Maybe because it's invariant here, dunno.

...

> > +	int n = 0;
> 
> Is n signed for purpose? I think it should be consistent with
> return value.

OK. No purpose there. Perhaps it's a leftover from the first experiments
on the implementation of these APIs.

...

> > + * Example:
> > + * If @src bitmap = 0x0302, with @mask = 0x1313, @dst will be 0x001a.
> 
> Not sure about others, but to me hex representation is quite useless,
> moreover it's followed by binary one.

Somebody is better at hex, somebody at binary one, I would leave both.

> > + * Or in binary form
> > + * @src			@mask			@dst
> > + * 0000001100000010	0001001100010011	0000000000011010
> > + *
> > + * (Bits 0, 1, 4, 8, 9, 12 are copied to the bits 0, 1, 2, 3, 4, 5)
> > + *
> > + * Returns: the weight of the @mask.
> > + */
> 
> It looks like those are designed complement to each other. Is that
> true? If so, can you make your example showing that
>         scatter -> gather -> scatter
> would restore the original bitmap?

It looks like you stopped reading documentation somewhere on the middle.
The two APIs are documented with the same example which makes it clear
that they are data-loss transformations.

Do you need something like this to be added (in both documentations):

  The bitmap_scatter(), when executed over the @dst bitmap, will
  restore the @src one if the @mask is kept the same, see the example
  in the function description.

?

> If I'm wrong, can you please underline that they are not complement,
> and why?

No, you are not.

...

> I feel like they should reside in header, because they are quite a small
> functions indeed, and they would benefit from compile-time optimizations
> without bloating the kernel.
> 
> Moreover, you are using them in patch #3 on 64-bit bitmaps, which
> would benefit from small_const_nbits() optimization.

I can move them into header.

...

> > +	DECLARE_BITMAP(bmap, 1024);

> Can you make it 1000? That way we'll test non-aligned case.

Sure. But it's not related to the patch. It will test bitmap_weight() and not
the new APIs, so, whatever is bigger 64 will suffice the purpose and won't
anyhow affect the newly added APIs.

...

> Would be interesting to compare bitmap scatter/gather performance
> against bitmap_remap.

Do you have a code in mind? I can incorporate it.

Again, you should understand that it's only applicable to the certain cases,
otherwise it makes no sense (it's like comparing performance of ffs() on
a single word against find_first_bit() on the arbitrary amount of words).

-- 
With Best Regards,
Andy Shevchenko