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]

Date:   Tue, 26 Sep 2023 19:10:33 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Andy Shevchenko <andriy.shevchenko@...ux.intel.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>,
        Andy Shevchenko <andy@...nel.org>,
        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

> > +unsigned int bitmap_gather(unsigned long *dst, const unsigned long *src,
> > +			   const unsigned long *mask, unsigned int nbits)
> > +{
> > +	unsigned int bit;
> > +	int n = 0;
> > +
> > +	bitmap_zero(dst, nbits);
> > +
> > +	for_each_set_bit(bit, mask, nbits)
> > +		__assign_bit(n++, dst, test_bit(bit, src));
> > +
> > +	return n;
> > +}
> > +EXPORT_SYMBOL(bitmap_gather);

So, if mask is 0b01, and src is 0b10, the output will be 0b00.
To me it sounds like you've gathered nothing, while the intention
was to gather all source bits to bit #0. This is my understanding
of the word 'gather', and this is how bitmap_remap() works.

bitmap_remap() handles it by wrapping around 0:
        set_bit(find_nth_bit(new, nbits, n % w), dst);

In your case, it may look like:
        n = off = 0;
        while (1) {
                off += n;
                n = 0;
        	for_each_set_bit(bit, mask, nbits) {
                        if (bit + off >= nbits)
                                return;
        		__assign_bit(n++, dst, test_bit(bit + off, src));
                }
        }

(Not tested, except that on piece of paper.)

If you claim you're replacing bitmap_remap(), you should correctly handle
the above case; when src == dst; when mask is empty, and probably more...

Thanks,
Yury