From: Yury Norov <yury.norov@gmail.com>
To: Andrew Morton <akpm@linux-foundation.org>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
Rasmus Villemoes <linux@rasmusvillemoes.dk>,
Dmitry Torokhov <dmitry.torokhov@gmail.com>,
"David S . Miller" <davem@davemloft.net>,
Stephen Rothwell <sfr@canb.auug.org.au>,
Amritha Nambiar <amritha.nambiar@intel.com>,
Willem de Bruijn <willemb@google.com>,
Kees Cook <keescook@chromium.org>,
Matthew Wilcox <willy@infradead.org>,
"Tobin C . Harding" <tobin@kernel.org>,
Will Deacon <will.deacon@arm.com>,
Miklos Szeredi <mszeredi@redhat.com>,
Vineet Gupta <vineet.gupta1@synopsys.com>,
Chris Wilson <chris@chris-wilson.co.uk>,
Arnaldo Carvalho de Melo <acme@redhat.com>,
linux-kernel@vger.kernel.org
Cc: Yury Norov <yury.norov@gmail.com>, Jens Axboe <axboe@kernel.dk>,
Steffen Klassert <steffen.klassert@secunet.com>
Subject: [PATCH v4 0/7] lib: rework bitmap_parse
Date: Sun, 8 Sep 2019 20:30:14 -0700 [thread overview]
Message-ID: <20190909033021.11600-1-yury.norov@gmail.com> (raw)
Hi all,
I'm sorry for long delay with re-submission of this series
As Andy mentioned in review for v3, I switched to isxdigit()
where appropriate. I also removed my Marvell's signed-off-by
since I don't work for them anymore.
Thanks,
Yury
On top of next-20190904.
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.
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.
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.
v3:
- fix bitmap_clear() misuse.
- opencode in_str() helper.
- simplify while() in bitmap_parse()
v4:
- use isxdigit() where appropriate.
- clean signed-off-by list.
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 | 196 +++++++++++++++++------------------
lib/string.c | 17 +++
lib/test_bitmap.c | 102 +++++++++++++++++-
tools/include/linux/bitops.h | 9 +-
8 files changed, 225 insertions(+), 117 deletions(-)
--
2.20.1
next reply other threads:[~2019-09-09 3:33 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-09-09 3:30 Yury Norov [this message]
2019-09-09 3:30 ` [PATCH 1/7] lib/string: add strnchrnul() Yury Norov
2019-09-09 3:30 ` [PATCH 2/7] bitops: more BITS_TO_* macros Yury Norov
2019-09-09 3:30 ` [PATCH 3/7] lib: add test for bitmap_parse() Yury Norov
2019-09-09 3:30 ` [PATCH 4/7] lib: make bitmap_parse_user a wrapper on bitmap_parse Yury Norov
2019-09-09 3:30 ` [PATCH 5/7] lib: rework bitmap_parse() Yury Norov
2019-09-09 10:06 ` Andy Shevchenko
2019-09-09 3:30 ` [PATCH 6/7] lib: new testcases for bitmap_parse{_user} Yury Norov
2019-09-09 3:30 ` [PATCH 7/7] cpumask: don't calculate length of the input string Yury Norov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190909033021.11600-1-yury.norov@gmail.com \
--to=yury.norov@gmail.com \
--cc=acme@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=amritha.nambiar@intel.com \
--cc=andriy.shevchenko@linux.intel.com \
--cc=axboe@kernel.dk \
--cc=chris@chris-wilson.co.uk \
--cc=davem@davemloft.net \
--cc=dmitry.torokhov@gmail.com \
--cc=keescook@chromium.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@rasmusvillemoes.dk \
--cc=mszeredi@redhat.com \
--cc=sfr@canb.auug.org.au \
--cc=steffen.klassert@secunet.com \
--cc=tobin@kernel.org \
--cc=vineet.gupta1@synopsys.com \
--cc=will.deacon@arm.com \
--cc=willemb@google.com \
--cc=willy@infradead.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).