Skip to content

lib: rework bitmap_parse

Yury Norov lkml oe-kbuild-all 4 versions – Applied

Status from this message: [merged] cpumask-dont-calculate-length-of-the-input-string.patch removed from -mm tree

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v5 Latest7 patches 0 repliesApplied 7/7
  2. v47 patches 1 replySuperseded
  3. v37 patches 1 replySuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v17 patches10 repliesSuperseded

Changes in v5 from the cover letter

- remove isxdigit() with hex_to_bin() to avoid cache use by ctype table.
- rebase on top of next-20191220.

Patches in v5 All 7 applied

#Subject and filesSizeRepliesApplied
1/7lib/string: add strnchrnul()include/linux/string.h lib/string.c+18 -00 repliesApplied
2/7bitops: more BITS_TO_* macrosinclude/linux/bitops.h tools/include/linux/bitops.h+9 -50 repliesApplied
3/7lib: add test for bitmap_parse()lib/test_bitmap.c+93 -11 replyApplied
4/7lib: make bitmap_parse_user a wrapper on bitmap_parselib/bitmap.c+10 -100 repliesApplied
5/7lib: rework bitmap_parse()include/linux/bitmap.h lib/bitmap.c+84 -990 repliesApplied
6/7lib: new testcases for bitmap_parse{_user}lib/test_bitmap.c+8 -00 repliesApplied
7/7cpumask: don't calculate length of the input stringinclude/linux/cpumask.h+1 -30 repliesApplied

Reviews trailers per patch

6 of 7 patches have a Reviewed-by or Acked-by.

PatchAndy Shevchenko
1/7R-b
2/7R-b
3/7R-b
4/7R-b
5/7
6/7R-b
7/7R-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v5 thread

Cover letter [PATCH v5 0/7] lib: rework bitmap_parse

On top of next-20191220.

Similarly to recently revisited bitmap_parselist(), bitmap_parse() is ineffective and overcomplicated. This series reworks it, aligns its interface with bitmap_parselist() and makes it simpler to use.

The series also adds a test for the function and fixes usage of it in cpumask_parse() according to the 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.
v5:
- remove isxdigit() with hex_to_bin() to avoid cache use by ctype table.
- rebase on top of next-20191220.

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                 | 193 +++++++++++++++++------------------
 lib/string.c                 |  17 +++
 lib/test_bitmap.c            | 102 +++++++++++++++++-
 tools/include/linux/bitops.h |   9 +-
 8 files changed, 222 insertions(+), 117 deletions(-)
Signature · 1 line
2.20.1