linux-kernel - [PATCH 0/4] 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: Windows password security audit tool. GUI, reports in PDF.

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

Message-Id: <20190428032936.1317-1-ynorov@marvell.com>
Date:   Sat, 27 Apr 2019 20:29:30 -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>
Cc:     Yury Norov <ynorov@...vell.com>, linux-kernel@...r.kernel.org,
        Yury Norov <yury.norov@...il.com>,
        Jens Axboe <axboe@...nel.dk>,
        Steffen Klassert <steffen.klassert@...unet.com>
Subject: [PATCH 0/4] lib: rework bitmap_parse

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.

[1] https://lkml.org/lkml/2019/4/16/66

Yury Norov (6):
  lib/string: add strnchrnul()
  bitops: more BITS_TO_* macros
  lib/bitmap: make bitmap_parse_user a wrapper on bitmap_parse
  lib: rework bitmap_parse()
  lib: add test for bitmap_parse()
  cpumask: don't calculate length of the input string

 include/linux/bitmap.h       |   8 +-
 include/linux/bitops.h       |   3 +
 include/linux/cpumask.h      |   4 +-
 include/linux/string.h       |   3 +
 lib/bitmap.c                 | 197 +++++++++++++++++------------------
 lib/string.c                 |  20 ++++
 lib/test_bitmap.c            | 102 +++++++++++++++++-
 tools/include/linux/bitops.h |   9 +-
 8 files changed, 230 insertions(+), 116 deletions(-)

-- 
2.17.1