linux-kernel - Re: [PATCH 27/54] lib/bitmap: add bitmap_weight

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: <Ye6egq/6It3LZs19@smile.fi.intel.com>
Date:   Mon, 24 Jan 2022 14:41:38 +0200
From:   Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
To:     Yury Norov <yury.norov@...il.com>
Cc:     Rasmus Villemoes <linux@...musvillemoes.dk>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Michał Mirosław <mirq-linux@...e.qmqm.pl>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        Peter Zijlstra <peterz@...radead.org>,
        David Laight <David.Laight@...lab.com>,
        Joe Perches <joe@...ches.com>, Dennis Zhou <dennis@...nel.org>,
        Emil Renner Berthing <kernel@...il.dk>,
        Nicholas Piggin <npiggin@...il.com>,
        Matti Vaittinen <matti.vaittinen@...rohmeurope.com>,
        Alexey Klimov <aklimov@...hat.com>,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH 27/54] lib/bitmap: add bitmap_weight_{cmp, eq, gt, ge,
 lt, le} functions

On Sun, Jan 23, 2022 at 10:38:58AM -0800, Yury Norov wrote:
> Many kernel users use bitmap_weight() to compare the result against
> some number or expression:
> 
> 	if (bitmap_weight(...) > 1)
> 		do_something();
> 
> It works OK, but may be significantly improved for large bitmaps: if
> first few words count set bits to a number greater than given, we can
> stop counting and immediately return.
> 
> The same idea would work in other direction: if we know that the number
> of set bits that we counted so far is small enough, so that it would be
> smaller than required number even if all bits of the rest of the bitmap
> are set, we can stop counting earlier.
> 
> This patch adds new bitmap_weight_cmp() as suggested by Michał Mirosław
> and a family of eq, gt, ge, lt and le wrappers to allow this optimization.

lt, and le

> The following patches apply new functions where appropriate.

What I missed in the above message is the rough statistics like some of them
are used more often, some less, and some, perhaps, just added for the sake of
symmetry (the latter is what would be important to see if there are APIs which
have no users at all).

> Suggested-by: "Michał Mirosław" <mirq-linux@...e.qmqm.pl> (for bitmap_weight_cmp)

Please, avoid using double quotes in the tags.

While at it, as a few folks already noticed, keep the subject lines in align
with the policies established in the certain subsystems (in this case seems
'bitmap:' should suffice). I would recommend to run

  `git log --oneline --no-merges -- ...file(s)_in_question...`

to figure out what is the most used and best fit in each case individually.

...

> + * Returns zero if weight of @src is equal to @num;
> + *	   negative number if weight of @src is less than @num;
> + *	   positive number if weight of @src is greater than @num;

> + * NOTES
> + *
> + * Because number of set bits cannot decrease while counting, when user
> + * wants to know if the number of set bits in the bitmap is less than
> + * @num, calling
> + *	bitmap_weight_cmp(..., @num) < 0
> + * is potentially less effective than
> + *	bitmap_weight_cmp(..., @num - 1) <= 0
> + *
> + * Consider an example:
> + * bitmap_weight_cmp(1000 0000 0000 0000, 1) < 0
> + *				    ^
> + *				    stop here
> + *
> + * bitmap_weight_cmp(1000 0000 0000 0000, 0) <= 0
> + *		     ^
> + *		     stop here

This probably should precede the Returns paragraph, also that paragraph can be
converted to a section in the documentation as follows:

 *
 * Returns:
 *   ...
 *

...

> +	if (num > (int)nbits || num < 0)

Wonder if

	if (abs(num) > nbits)

would be sufficient.

> +		return -num;

-- 
With Best Regards,
Andy Shevchenko