[PATCH 1/2] lib: make bitmap_parselist thread-safe and much faster

[PATCH 1/2] lib: make bitmap_parselist thread-safe and much faster

[Yury Norov]

Current implementation of bitmap_parselist() uses the static variable to save
local state while setting bits in the bitmap. It is obviously wrong if we assume
execution in multiprocessor environment. Fortunately, it's possible to rewrite
this portion of code to avoid using the static variable.

It is also possible to set bits in the mask per-range with bitmap_set(), not
per-bit, as it is implemented now, with set_bit(); which is way faster.

The important side effect of this changes is that setting bits in this function
from now is not per-bit atomic and less memory-ordered. This is because set_bit()
guaranties the order of memory accesses, while bitmap_set() does not. I think
that it is the advantage of the new approach, because the bitmap_parselist() is
intended to initialise bit arrays, and user should protect the whole bitmap
during initialisation if needed. So protecting individual bits looks expensive 
and useless. Also, other range-oriented functions in lib/bitmap.c don't worry
much about atomicity.

With all that, setting 2k bits in map with the pattern like 0-2047:128/256
becomes ~50 times faster after applying the patch in my testing environment
(arm64 hosted on qemu).

The second patch of the series adds the test for bitmap_parselist(). It's not
intended to cover all tricky cases, just to make sure that I didn't screw up
during rework.

Signed-off-by: Yury Norov <ynorov@caviumnetworks.com>
---
 lib/bitmap.c | 18 ++++++------------
 1 file changed, 6 insertions(+), 12 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 9a532805364b..c82c61b66e16 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -513,7 +513,7 @@ static int __bitmap_parselist(const char *buf, unsigned int buflen,
 		int nmaskbits)
 {
 	unsigned int a, b, old_a, old_b;
-	unsigned int group_size, used_size;
+	unsigned int group_size, used_size, off;
 	int c, old_c, totaldigits, ndigits;
 	const char __user __force *ubuf = (const char __user __force *)buf;
 	int at_start, in_range, in_partial_range;
@@ -599,6 +599,8 @@ static int __bitmap_parselist(const char *buf, unsigned int buflen,
 			a = old_a;
 			b = old_b;
 			old_a = old_b = 0;
+		} else {
+			used_size = group_size = b - a + 1;
 		}
 		/* if no digit is after '-', it's wrong*/
 		if (at_start && in_range)
@@ -608,17 +610,9 @@ static int __bitmap_parselist(const char *buf, unsigned int buflen,
 		if (b >= nmaskbits)
 			return -ERANGE;
 		while (a <= b) {
-			if (in_partial_range) {
-				static int pos_in_group = 1;
-
-				if (pos_in_group <= used_size)
-					set_bit(a, maskp);
-
-				if (a == b || ++pos_in_group > group_size)
-					pos_in_group = 1;
-			} else
-				set_bit(a, maskp);
-			a++;
+			off = min(b - a + 1, used_size);
+			bitmap_set(maskp, a, off);
+			a += group_size;
 		}
 	} while (buflen && c == ',');
 	return 0;
-- 
2.11.0

[PATCH 2/2] lib: add test for bitmap_parselist()

[Yury Norov]

Do some basic checks for the bitmap_parselist().

Signed-off-by: Yury Norov <ynorov@caviumnetworks.com>
---
 lib/test_bitmap.c | 73 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 73 insertions(+)

diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 2526a2975c51..5b80dd94e4d1 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -165,6 +165,78 @@ static void __init test_zero_fill_copy(void)
 	expect_eq_pbl("128-1023", bmap2, 1024);
 }
 
+#define PARSE_TIME 0x1
+
+struct test_bitmap_parselist{
+	const int errno;
+	const char *in;
+	const unsigned long *expected;
+	const int nbits;
+	const int flags;
+};
+
+static const unsigned long exp[] = {1, 2, 0x0000ffff, 0xffff0000, 0x55555555,
+				0xaaaaaaaa, 0x11111111, 0x22222222, 0xffffffff,
+				0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
+static const unsigned long exp2[] = {0x3333333311111111, 0xffffffff77777777};
+
+static const struct test_bitmap_parselist parselist_tests[] __initconst = {
+	{0, "0",			&exp[0], 8, 0},
+	{0, "1",			&exp[1], 8, 0},
+	{0, "0-15",			&exp[2], 32, 0},
+	{0, "16-31",			&exp[3], 32, 0},
+	{0, "0-31:1/2",			&exp[4], 32, 0},
+	{0, "1-31:1/2",			&exp[5], 32, 0},
+	{0, "0-31:1/4",			&exp[6], 32, 0},
+	{0, "1-31:1/4",			&exp[7], 32, 0},
+	{0, "0-31:4/4",			&exp[8], 32, 0},
+	{0, "1-31:4/4",			&exp[9], 32, 0},
+	{0, "0-31:1/4,32-63:2/4",	&exp[10], 64, 0},
+	{0, "0-31:3/4,32-63:4/4",	&exp[11], 64, 0},
+
+	{0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",	exp2, 128, 0},
+
+	{0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
+
+	{-EINVAL, "-1",	NULL, 8, 0},
+	{-EINVAL, "-0",	NULL, 8, 0},
+	{-EINVAL, "10-1", NULL, 8, 0},
+	{-EINVAL, "0-31:10/1", NULL, 8, 0},
+};
+
+static void __init test_bitmap_parselist(void)
+{
+	int i;
+	int err;
+	cycles_t cycles;
+	DECLARE_BITMAP(bmap, 2048);
+
+	for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
+#define ptest parselist_tests[i]
+
+		cycles = get_cycles();
+		err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
+		cycles = get_cycles() - cycles;
+
+		if (err != ptest.errno) {
+			pr_err("test %d: input is %s, errno is %d, expected %d\n",
+					i, ptest.in, err, ptest.errno);
+			continue;
+		}
+
+		if (!err && ptest.expected
+			 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
+			pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
+					i, ptest.in, bmap[0], *ptest.expected);
+			continue;
+		}
+
+		if (ptest.flags & PARSE_TIME)
+			pr_err("test %d: input is '%s' OK, Time: %lu\n",
+					i, ptest.in, cycles);
+	}
+}
+
 static void __init test_bitmap_u32_array_conversions(void)
 {
 	DECLARE_BITMAP(bmap1, 1024);
@@ -365,6 +437,7 @@ static int __init test_bitmap_init(void)
 {
 	test_zero_fill_copy();
 	test_bitmap_u32_array_conversions();
+	test_bitmap_parselist();
 	test_mem_optimisations();
 
 	if (failed_tests == 0)
-- 
2.11.0

Re: [PATCH 2/2] lib: add test for bitmap_parselist()

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 4922 bytes --]

Hi Yury,

[auto build test WARNING on linus/master]
[also build test WARNING on v4.13-rc4 next-20170808]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url:    https://github.com/0day-ci/linux/commits/Yury-Norov/lib-make-bitmap_parselist-thread-safe-and-much-faster/20170809-105307
config: i386-randconfig-x000-201732 (attached as .config)
compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
reproduce:
        # save the attached .config to linux build tree
        make ARCH=i386 

All warnings (new ones prefixed by >>):

>> lib/test_bitmap.c:180:17: warning: large integer implicitly truncated to unsigned type [-Woverflow]
        0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
                    ^~~~~~~~~~~~~~~~~~
   lib/test_bitmap.c:180:37: warning: large integer implicitly truncated to unsigned type [-Woverflow]
        0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
                                        ^~~~~~~~~~~~~~~~~~
   lib/test_bitmap.c:181:38: warning: large integer implicitly truncated to unsigned type [-Woverflow]
    static const unsigned long exp2[] = {0x3333333311111111, 0xffffffff77777777};
                                         ^~~~~~~~~~~~~~~~~~
   lib/test_bitmap.c:181:58: warning: large integer implicitly truncated to unsigned type [-Woverflow]
    static const unsigned long exp2[] = {0x3333333311111111, 0xffffffff77777777};
                                                             ^~~~~~~~~~~~~~~~~~
   In file included from include/linux/printk.h:6:0,
                    from include/linux/kernel.h:13,
                    from include/linux/bitmap.h:9,
                    from lib/test_bitmap.c:7:
   lib/test_bitmap.c: In function 'test_bitmap_parselist':
   include/linux/kern_levels.h:4:18: warning: format '%lu' expects argument of type 'long unsigned int', but argument 4 has type 'cycles_t {aka long long unsigned int}' [-Wformat=]
    #define KERN_SOH "\001"  /* ASCII Start Of Header */
                     ^
   include/linux/kern_levels.h:10:18: note: in expansion of macro 'KERN_SOH'
    #define KERN_ERR KERN_SOH "3" /* error conditions */
                     ^~~~~~~~
   include/linux/printk.h:301:9: note: in expansion of macro 'KERN_ERR'
     printk(KERN_ERR pr_fmt(fmt), ##__VA_ARGS__)
            ^~~~~~~~
>> lib/test_bitmap.c:235:4: note: in expansion of macro 'pr_err'
       pr_err("test %d: input is '%s' OK, Time: %lu\n",
       ^~~~~~

vim +180 lib/test_bitmap.c

   177	
   178	static const unsigned long exp[] = {1, 2, 0x0000ffff, 0xffff0000, 0x55555555,
   179					0xaaaaaaaa, 0x11111111, 0x22222222, 0xffffffff,
 > 180					0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
   181	static const unsigned long exp2[] = {0x3333333311111111, 0xffffffff77777777};
   182	
   183	static const struct test_bitmap_parselist parselist_tests[] __initconst = {
   184		{0, "0",			&exp[0], 8, 0},
   185		{0, "1",			&exp[1], 8, 0},
   186		{0, "0-15",			&exp[2], 32, 0},
   187		{0, "16-31",			&exp[3], 32, 0},
   188		{0, "0-31:1/2",			&exp[4], 32, 0},
   189		{0, "1-31:1/2",			&exp[5], 32, 0},
   190		{0, "0-31:1/4",			&exp[6], 32, 0},
   191		{0, "1-31:1/4",			&exp[7], 32, 0},
   192		{0, "0-31:4/4",			&exp[8], 32, 0},
   193		{0, "1-31:4/4",			&exp[9], 32, 0},
   194		{0, "0-31:1/4,32-63:2/4",	&exp[10], 64, 0},
   195		{0, "0-31:3/4,32-63:4/4",	&exp[11], 64, 0},
   196	
   197		{0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",	exp2, 128, 0},
   198	
   199		{0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
   200	
   201		{-EINVAL, "-1",	NULL, 8, 0},
   202		{-EINVAL, "-0",	NULL, 8, 0},
   203		{-EINVAL, "10-1", NULL, 8, 0},
   204		{-EINVAL, "0-31:10/1", NULL, 8, 0},
   205	};
   206	
   207	static void __init test_bitmap_parselist(void)
   208	{
   209		int i;
   210		int err;
   211		cycles_t cycles;
   212		DECLARE_BITMAP(bmap, 2048);
   213	
   214		for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
   215	#define ptest parselist_tests[i]
   216	
   217			cycles = get_cycles();
   218			err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
   219			cycles = get_cycles() - cycles;
   220	
   221			if (err != ptest.errno) {
   222				pr_err("test %d: input is %s, errno is %d, expected %d\n",
   223						i, ptest.in, err, ptest.errno);
   224				continue;
   225			}
   226	
   227			if (!err && ptest.expected
   228				 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
   229				pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
   230						i, ptest.in, bmap[0], *ptest.expected);
   231				continue;
   232			}
   233	
   234			if (ptest.flags & PARSE_TIME)
 > 235				pr_err("test %d: input is '%s' OK, Time: %lu\n",
   236						i, ptest.in, cycles);
   237		}
   238	}
   239	

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 29920 bytes --]

Re: [PATCH 2/2] lib: add test for bitmap_parselist()

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 3988 bytes --]

Hi Yury,

[auto build test WARNING on linus/master]
[also build test WARNING on v4.13-rc4 next-20170808]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url:    https://github.com/0day-ci/linux/commits/Yury-Norov/lib-make-bitmap_parselist-thread-safe-and-much-faster/20170809-105307
config: xtensa-allmodconfig (attached as .config)
compiler: xtensa-linux-gcc (GCC) 4.9.0
reproduce:
        wget https://raw.githubusercontent.com/01org/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=xtensa 

All warnings (new ones prefixed by >>):

   lib/test_bitmap.c:180:5: warning: large integer implicitly truncated to unsigned type [-Woverflow]
        0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
        ^
   lib/test_bitmap.c:180:5: warning: large integer implicitly truncated to unsigned type [-Woverflow]
   lib/test_bitmap.c:181:1: warning: large integer implicitly truncated to unsigned type [-Woverflow]
    static const unsigned long exp2[] = {0x3333333311111111, 0xffffffff77777777};
    ^
   lib/test_bitmap.c:181:1: warning: large integer implicitly truncated to unsigned type [-Woverflow]
   lib/test_bitmap.c: In function 'test_bitmap_parselist':
>> lib/test_bitmap.c:235:4: warning: format '%lu' expects argument of type 'long unsigned int', but argument 4 has type 'cycles_t' [-Wformat=]
       pr_err("test %d: input is '%s' OK, Time: %lu\n",
       ^

vim +235 lib/test_bitmap.c

   177	
   178	static const unsigned long exp[] = {1, 2, 0x0000ffff, 0xffff0000, 0x55555555,
   179					0xaaaaaaaa, 0x11111111, 0x22222222, 0xffffffff,
 > 180					0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
   181	static const unsigned long exp2[] = {0x3333333311111111, 0xffffffff77777777};
   182	
   183	static const struct test_bitmap_parselist parselist_tests[] __initconst = {
   184		{0, "0",			&exp[0], 8, 0},
   185		{0, "1",			&exp[1], 8, 0},
   186		{0, "0-15",			&exp[2], 32, 0},
   187		{0, "16-31",			&exp[3], 32, 0},
   188		{0, "0-31:1/2",			&exp[4], 32, 0},
   189		{0, "1-31:1/2",			&exp[5], 32, 0},
   190		{0, "0-31:1/4",			&exp[6], 32, 0},
   191		{0, "1-31:1/4",			&exp[7], 32, 0},
   192		{0, "0-31:4/4",			&exp[8], 32, 0},
   193		{0, "1-31:4/4",			&exp[9], 32, 0},
   194		{0, "0-31:1/4,32-63:2/4",	&exp[10], 64, 0},
   195		{0, "0-31:3/4,32-63:4/4",	&exp[11], 64, 0},
   196	
   197		{0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",	exp2, 128, 0},
   198	
   199		{0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
   200	
   201		{-EINVAL, "-1",	NULL, 8, 0},
   202		{-EINVAL, "-0",	NULL, 8, 0},
   203		{-EINVAL, "10-1", NULL, 8, 0},
   204		{-EINVAL, "0-31:10/1", NULL, 8, 0},
   205	};
   206	
   207	static void __init test_bitmap_parselist(void)
   208	{
   209		int i;
   210		int err;
   211		cycles_t cycles;
   212		DECLARE_BITMAP(bmap, 2048);
   213	
   214		for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
   215	#define ptest parselist_tests[i]
   216	
   217			cycles = get_cycles();
   218			err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
   219			cycles = get_cycles() - cycles;
   220	
   221			if (err != ptest.errno) {
   222				pr_err("test %d: input is %s, errno is %d, expected %d\n",
   223						i, ptest.in, err, ptest.errno);
   224				continue;
   225			}
   226	
   227			if (!err && ptest.expected
   228				 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
   229				pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
   230						i, ptest.in, bmap[0], *ptest.expected);
   231				continue;
   232			}
   233	
   234			if (ptest.flags & PARSE_TIME)
 > 235				pr_err("test %d: input is '%s' OK, Time: %lu\n",
   236						i, ptest.in, cycles);
   237		}
   238	}
   239	

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 50926 bytes --]

Re: [PATCH 2/2] lib: add test for bitmap_parselist()

[Andrew Morton]

On Wed, 9 Aug 2017 12:11:15 +0800 kbuild test robot <lkp@intel.com> wrote:

> [auto build test WARNING on linus/master]
> [also build test WARNING on v4.13-rc4 next-20170808]
> [if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
> 
> url:    https://github.com/0day-ci/linux/commits/Yury-Norov/lib-make-bitmap_parselist-thread-safe-and-much-faster/20170809-105307
> config: xtensa-allmodconfig (attached as .config)
> compiler: xtensa-linux-gcc (GCC) 4.9.0
> reproduce:
>         wget https://raw.githubusercontent.com/01org/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
>         chmod +x ~/bin/make.cross
>         # save the attached .config to linux build tree
>         make.cross ARCH=xtensa 
> 
> All warnings (new ones prefixed by >>):
> 
>    lib/test_bitmap.c:180:5: warning: large integer implicitly truncated to unsigned type [-Woverflow]
>         0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
>         ^
>    lib/test_bitmap.c:180:5: warning: large integer implicitly truncated to unsigned type [-Woverflow]
>    lib/test_bitmap.c:181:1: warning: large integer implicitly truncated to unsigned type [-Woverflow]
>     static const unsigned long exp2[] = {0x3333333311111111, 0xffffffff77777777};
>     ^
>    lib/test_bitmap.c:181:1: warning: large integer implicitly truncated to unsigned type [-Woverflow]
>    lib/test_bitmap.c: In function 'test_bitmap_parselist':
> >> lib/test_bitmap.c:235:4: warning: format '%lu' expects argument of type 'long unsigned int', but argument 4 has type 'cycles_t' [-Wformat=]
>        pr_err("test %d: input is '%s' OK, Time: %lu\n",
>        ^

Maybe we need a %p thingy for printing cycles_t.  But this will do:

--- a/lib/test_bitmap.c~lib-add-test-for-bitmap_parselist-fix
+++ a/lib/test_bitmap.c
@@ -232,8 +232,9 @@ static void __init test_bitmap_parselist
 		}
 
 		if (ptest.flags & PARSE_TIME)
-			pr_err("test %d: input is '%s' OK, Time: %lu\n",
-					i, ptest.in, cycles);
+			pr_err("test %d: input is '%s' OK, Time: %llu\n",
+					i, ptest.in,
+					(unsigned long long)cycles);
 	}
 }
 
_

Re: [PATCH 2/2] lib: add test for bitmap_parselist()

[Andrew Morton]

On Wed, 9 Aug 2017 11:28:56 +0800 kbuild test robot <lkp@intel.com> wrote:

> [auto build test WARNING on linus/master]
> [also build test WARNING on v4.13-rc4 next-20170808]
> [if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
> 
> url:    https://github.com/0day-ci/linux/commits/Yury-Norov/lib-make-bitmap_parselist-thread-safe-and-much-faster/20170809-105307
> config: i386-randconfig-x000-201732 (attached as .config)
> compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
> reproduce:
>         # save the attached .config to linux build tree
>         make ARCH=i386 
> 
> All warnings (new ones prefixed by >>):
> 
> >> lib/test_bitmap.c:180:17: warning: large integer implicitly truncated to unsigned type [-Woverflow]
>         0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
>                     ^~~~~~~~~~~~~~~~~~

I assume that a simple convertion to unsigned long long will fix that,
but I'll await Yuri's input (and testing).

btw, exp[] and exp2[] could be __initconst?

Re: [PATCH 2/2] lib: add test for bitmap_parselist()

[Yury Norov]

On Wed, Aug 09, 2017 at 01:33:09PM -0700, Andrew Morton wrote:
> On Wed, 9 Aug 2017 11:28:56 +0800 kbuild test robot <lkp@intel.com> wrote:
> 
> > [auto build test WARNING on linus/master]
> > [also build test WARNING on v4.13-rc4 next-20170808]
> > [if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
> > 
> > url:    https://github.com/0day-ci/linux/commits/Yury-Norov/lib-make-bitmap_parselist-thread-safe-and-much-faster/20170809-105307
> > config: i386-randconfig-x000-201732 (attached as .config)
> > compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
> > reproduce:
> >         # save the attached .config to linux build tree
> >         make ARCH=i386 
> > 
> > All warnings (new ones prefixed by >>):
> > 
> > >> lib/test_bitmap.c:180:17: warning: large integer implicitly truncated to unsigned type [-Woverflow]
> >         0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
> >                     ^~~~~~~~~~~~~~~~~~
 
Ahh... I didn't take 32-bit arches into account...

> I assume that a simple convertion to unsigned long long will fix that,
> but I'll await Yuri's input (and testing).

The conversion to unsigned long long will work only for little endian
32-bit arches. We trapped into it once:
https://patchwork.kernel.org/patch/9260919+/

It should be the compile-time analogue of bitmap_from_u64()

The patch is attached and seems working to me. But I need some time
for testing...

Yury

>From be0e663b804daff0d0512e72cf94b5143270bd29 Mon Sep 17 00:00:00 2001
From: Yury Norov <ynorov@caviumnetworks.com>
Date: Thu, 10 Aug 2017 01:25:46 +0300
Subject: [PATCH] bitmap: introduce BITMAP_FROM_U64() and use it in test for
 bitmap_parselist()

The macro is the compile-time analogue of bitmap_from_u64() with the
same purpose: convert the 64-bit number to the properly ordered pair
of 32-bit parts to be suitable for filling the bitmap.

Signed-off-by: Yury Norov <ynorov@caviumnetworks.com>
---
 include/linux/bitmap.h |  6 ++++++
 lib/test_bitmap.c      | 23 +++++++++++++++++++----
 2 files changed, 25 insertions(+), 4 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 5797ca6fdfe2..bdc487e47de1 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -378,6 +378,12 @@ static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
 		dst[1] = mask >> 32;
 }
 
+#if __BITS_PER_LONG == 64
+#define BITMAP_FROM_U64(n) (n)
+#else
+#define BITMAP_FROM_U64(n) ((n) & ULONG_MAX), ((unsigned long long) (n) >> 32)
+#endif
+
 #endif /* __ASSEMBLY__ */
 
 #endif /* __LINUX_BITMAP_H */
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 5b80dd94e4d1..65b8fcc41fd0 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -175,10 +175,25 @@ struct test_bitmap_parselist{
 	const int flags;
 };
 
-static const unsigned long exp[] = {1, 2, 0x0000ffff, 0xffff0000, 0x55555555,
-				0xaaaaaaaa, 0x11111111, 0x22222222, 0xffffffff,
-				0xfffffffe, 0x3333333311111111, 0xffffffff77777777};
-static const unsigned long exp2[] = {0x3333333311111111, 0xffffffff77777777};
+static const unsigned long exp[] __initconst = {
+	BITMAP_FROM_U64(1),
+	BITMAP_FROM_U64(2),
+	BITMAP_FROM_U64(0x0000ffff),
+	BITMAP_FROM_U64(0xffff0000),
+	BITMAP_FROM_U64(0x55555555),
+	BITMAP_FROM_U64(0xaaaaaaaa),
+	BITMAP_FROM_U64(0x11111111),
+	BITMAP_FROM_U64(0x22222222),
+	BITMAP_FROM_U64(0xffffffff),
+	BITMAP_FROM_U64(0xfffffffe),
+	BITMAP_FROM_U64(0x3333333311111111),
+	BITMAP_FROM_U64(0xffffffff77777777)
+};
+
+static const unsigned long exp2[] __initconst = {
+	BITMAP_FROM_U64(0x3333333311111111),
+	BITMAP_FROM_U64(0xffffffff77777777)
+};
 
 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
 	{0, "0",			&exp[0], 8, 0},
-- 
2.11.0

Re: [PATCH 2/2] lib: add test for bitmap_parselist()

[Rasmus Villemoes]

> From be0e663b804daff0d0512e72cf94b5143270bd29 Mon Sep 17 00:00:00 2001
> From: Yury Norov <ynorov@caviumnetworks.com>
> Date: Thu, 10 Aug 2017 01:25:46 +0300
> Subject: [PATCH] bitmap: introduce BITMAP_FROM_U64() and use it in test for
>  bitmap_parselist()
>
> The macro is the compile-time analogue of bitmap_from_u64() with the
> same purpose: convert the 64-bit number to the properly ordered pair
> of 32-bit parts to be suitable for filling the bitmap.
>
> Signed-off-by: Yury Norov <ynorov@caviumnetworks.com>
> ---
>  include/linux/bitmap.h |  6 ++++++
>  lib/test_bitmap.c      | 23 +++++++++++++++++++----
>  2 files changed, 25 insertions(+), 4 deletions(-)
>
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 5797ca6fdfe2..bdc487e47de1 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -378,6 +378,12 @@ static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
>                 dst[1] = mask >> 32;
>  }
>
> +#if __BITS_PER_LONG == 64
> +#define BITMAP_FROM_U64(n) (n)
> +#else
> +#define BITMAP_FROM_U64(n) ((n) & ULONG_MAX), ((unsigned long long) (n) >> 32)
> +#endif
> +

The 32 bit version probably needs to come in two flavours depending on
little/big endian, no?

Could you also throw in some casts so that the behaviour is consistent
regardless of the type of the expression n, and so that both elements
in the pair are guaranteed to have the same type (unsigned long,
preferably, since that's what we're initializing). I.e., cast n to
(u64), do arithmetic, cast result to (unsigned long).

Re: [PATCH 2/2] lib: add test for bitmap_parselist()

[Yury Norov]

On Thu, Aug 10, 2017 at 09:30:31AM +0200, Rasmus Villemoes wrote:
> > From be0e663b804daff0d0512e72cf94b5143270bd29 Mon Sep 17 00:00:00 2001
> > From: Yury Norov <ynorov@caviumnetworks.com>
> > Date: Thu, 10 Aug 2017 01:25:46 +0300
> > Subject: [PATCH] bitmap: introduce BITMAP_FROM_U64() and use it in test for
> >  bitmap_parselist()
> >
> > The macro is the compile-time analogue of bitmap_from_u64() with the
> > same purpose: convert the 64-bit number to the properly ordered pair
> > of 32-bit parts to be suitable for filling the bitmap.
> >
> > Signed-off-by: Yury Norov <ynorov@caviumnetworks.com>
> > ---
> >  include/linux/bitmap.h |  6 ++++++
> >  lib/test_bitmap.c      | 23 +++++++++++++++++++----
> >  2 files changed, 25 insertions(+), 4 deletions(-)
> >
> > diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> > index 5797ca6fdfe2..bdc487e47de1 100644
> > --- a/include/linux/bitmap.h
> > +++ b/include/linux/bitmap.h
> > @@ -378,6 +378,12 @@ static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
> >                 dst[1] = mask >> 32;
> >  }
> >
> > +#if __BITS_PER_LONG == 64
> > +#define BITMAP_FROM_U64(n) (n)
> > +#else
> > +#define BITMAP_FROM_U64(n) ((n) & ULONG_MAX), ((unsigned long long) (n) >> 32)
> > +#endif
> > +
> 
> The 32 bit version probably needs to come in two flavours depending on
> little/big endian, no?
 
Actually no. For completeness:

There are four combinations of endianess and length of the word in linux ABIs:
LE64, BE64, LE32 and BE32. 64-bit LE and BE are naturally ordered and therefore
don't require any special handling.

32-bit LE ABI orders lo word of 64-bit number prior to hi, and 32-bit BE
orders hi word prior to lo in the memory. The bitmap in other hand is
represented as the array of 32-bit words, and the position of the bit
N may therefore be calculated as: word (N/32) and bit (N%32) in that
word. For example, bit #42 is located at 10th position of 2nd word.
It matches 32-bit LE ABI, and we can simply let the compiler store 64-bit
value on the memory like it usually does. But for BE we therefore need
to swap words manually.

With all that, the macro (n & ULONG_MAX, n >> 32) does exactly what
needed for 32-bit case. In LE environment it does in fact nothing, and
in BE environment it swaps hi and lo words.

> Could you also throw in some casts so that the behaviour is consistent
> regardless of the type of the expression n, and so that both elements
> in the pair are guaranteed to have the same type (unsigned long,
> preferably, since that's what we're initializing). I.e., cast n to
> (u64), do arithmetic, cast result to (unsigned long).

If no objections, I'll change the patch like you proposed here, add
the explanation below to the comment of macro and resend it after
finishing the testing. (I need time to setup some 32-bit BE
environment to do test.)

Yury