linux-kernel - Re: [PATCH 0/7] lib: 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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20190507210421.GA8935@yury-thinkpad>
Date:   Tue, 7 May 2019 14:04:21 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Andrew Morton <akpm@...ux-foundation.org>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Dmitry Torokhov <dmitry.torokhov@...il.com>,
        "David S . Miller" <davem@...emloft.net>,
        Stephen Rothwell <sfr@...b.auug.org.au>,
        Amritha Nambiar <amritha.nambiar@...el.com>,
        Willem de Bruijn <willemb@...gle.com>,
        Kees Cook <keescook@...omium.org>,
        Matthew Wilcox <willy@...radead.org>,
        "Tobin C . Harding" <tobin@...nel.org>,
        Will Deacon <will.deacon@....com>,
        Miklos Szeredi <mszeredi@...hat.com>,
        Vineet Gupta <vineet.gupta1@...opsys.com>,
        Chris Wilson <chris@...is-wilson.co.uk>,
        Arnaldo Carvalho de Melo <acme@...hat.com>,
        linux-kernel@...r.kernel.org
Cc:     Yury Norov <ynorov@...vell.com>, Jens Axboe <axboe@...nel.dk>,
        Steffen Klassert <steffen.klassert@...unet.com>
Subject: Re: [PATCH 0/7] lib: rework bitmap_parse

On Tue, Apr 30, 2019 at 06:06:29PM -0700, Yury Norov wrote:
> On top of next-20190418.
> 
> Similarly to recently revisited bitmap_parselist() [1],
> bitmap_parse() is ineffective and overcomplicated.  This
> series reworks it, aligns its interface with bitmap_parselist()
> and makes usage simpler.
> 
> The series also adds a test for the function and fixes usage of it
> in cpumask_parse() according to new design - drops the calculating
> of length of an input string.
> 
> The following users would also consider to drop the length argument,
> if possible:
> drivers/block/drbd/drbd_main.c:2608
> kernel/padata.c:924
> net/core/net-sysfs.c:726
> net/core/net-sysfs.c:1309
> net/core/net-sysfs.c:1391
> 
> bitmap_parse() takes the array of numbers to be put into the map in
> the BE order which is reversed to the natural LE order for bitmaps.
> For example, to construct bitmap containing a bit on the position 42,
> we have to put a line '400,0'. Current implementation reads chunk
> one by one from the beginning ('400' before '0') and makes bitmap
> shift after each successful parse. It makes the complexity of the
> whole process as O(n^2). We can do it in reverse direction ('0'
> before '400') and avoid shifting, but it requires reverse parsing
> helpers.
> 
> Tested on arm64 and BE mips.

Any comments?

> v1: https://lkml.org/lkml/2019/4/27/597
> v2:
>  - strnchrnul() signature and description changed, ifdeffery and
>    exporting removed;
>  - test split for better demonstration of before/after changes;
>  - minor naming and formatting issues fixed.
> 
> [1] https://lkml.org/lkml/2019/4/16/66
> 
> Yury Norov (7):
>   lib/string: add strnchrnul()
>   bitops: more BITS_TO_* macros
>   lib: add test for bitmap_parse()
>   lib: make bitmap_parse_user a wrapper on bitmap_parse
>   lib: rework bitmap_parse()
>   lib: new testcases for bitmap_parse{_user}
>   cpumask: don't calculate length of the input string
> 
>  include/linux/bitmap.h       |   8 +-
>  include/linux/bitops.h       |   5 +-
>  include/linux/cpumask.h      |   4 +-
>  include/linux/string.h       |   1 +
>  lib/bitmap.c                 | 197 +++++++++++++++++------------------
>  lib/string.c                 |  17 +++
>  lib/test_bitmap.c            | 102 +++++++++++++++++-
>  tools/include/linux/bitops.h |   9 +-
>  8 files changed, 226 insertions(+), 117 deletions(-)
> 
> -- 
> 2.17.1