* [PATCH 1/2] lib: make bitmap_parselist thread-safe and much faster @ 2017-08-07 22:54 Yury Norov 2017-08-07 22:54 ` [PATCH 2/2] lib: add test for bitmap_parselist() Yury Norov 0 siblings, 1 reply; 9+ messages in thread From: Yury Norov @ 2017-08-07 22:54 UTC (permalink / raw) To: Andrew Morton, Noam Camus, Rasmus Villemoes Cc: Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel, 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 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 2/2] lib: add test for bitmap_parselist() 2017-08-07 22:54 [PATCH 1/2] lib: make bitmap_parselist thread-safe and much faster Yury Norov @ 2017-08-07 22:54 ` Yury Norov 2017-08-09 3:28 ` kbuild test robot 2017-08-09 4:11 ` kbuild test robot 0 siblings, 2 replies; 9+ messages in thread From: Yury Norov @ 2017-08-07 22:54 UTC (permalink / raw) To: Andrew Morton, Noam Camus, Rasmus Villemoes Cc: Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel, 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 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] lib: add test for bitmap_parselist() 2017-08-07 22:54 ` [PATCH 2/2] lib: add test for bitmap_parselist() Yury Norov @ 2017-08-09 3:28 ` kbuild test robot 2017-08-09 20:33 ` Andrew Morton 2017-08-09 4:11 ` kbuild test robot 1 sibling, 1 reply; 9+ messages in thread From: kbuild test robot @ 2017-08-09 3:28 UTC (permalink / raw) To: Yury Norov Cc: kbuild-all, Andrew Morton, Noam Camus, Rasmus Villemoes, Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel, Yury Norov [-- 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 --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] lib: add test for bitmap_parselist() 2017-08-09 3:28 ` kbuild test robot @ 2017-08-09 20:33 ` Andrew Morton 2017-08-09 22:52 ` Yury Norov 0 siblings, 1 reply; 9+ messages in thread From: Andrew Morton @ 2017-08-09 20:33 UTC (permalink / raw) To: kbuild test robot Cc: Yury Norov, kbuild-all, Noam Camus, Rasmus Villemoes, Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel 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? ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] lib: add test for bitmap_parselist() 2017-08-09 20:33 ` Andrew Morton @ 2017-08-09 22:52 ` Yury Norov 2017-08-10 7:30 ` Rasmus Villemoes 0 siblings, 1 reply; 9+ messages in thread From: Yury Norov @ 2017-08-09 22:52 UTC (permalink / raw) To: Andrew Morton Cc: kbuild test robot, kbuild-all, Noam Camus, Rasmus Villemoes, Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel 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 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] lib: add test for bitmap_parselist() 2017-08-09 22:52 ` Yury Norov @ 2017-08-10 7:30 ` Rasmus Villemoes 2017-08-10 10:37 ` Yury Norov 0 siblings, 1 reply; 9+ messages in thread From: Rasmus Villemoes @ 2017-08-10 7:30 UTC (permalink / raw) To: Yury Norov Cc: Andrew Morton, kbuild test robot, kbuild-all, Noam Camus, Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel > 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). ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] lib: add test for bitmap_parselist() 2017-08-10 7:30 ` Rasmus Villemoes @ 2017-08-10 10:37 ` Yury Norov 0 siblings, 0 replies; 9+ messages in thread From: Yury Norov @ 2017-08-10 10:37 UTC (permalink / raw) To: Rasmus Villemoes Cc: Andrew Morton, kbuild test robot, kbuild-all, Noam Camus, Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] lib: add test for bitmap_parselist() 2017-08-07 22:54 ` [PATCH 2/2] lib: add test for bitmap_parselist() Yury Norov 2017-08-09 3:28 ` kbuild test robot @ 2017-08-09 4:11 ` kbuild test robot 2017-08-09 20:28 ` Andrew Morton 1 sibling, 1 reply; 9+ messages in thread From: kbuild test robot @ 2017-08-09 4:11 UTC (permalink / raw) To: Yury Norov Cc: kbuild-all, Andrew Morton, Noam Camus, Rasmus Villemoes, Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel, Yury Norov [-- 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 --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/2] lib: add test for bitmap_parselist() 2017-08-09 4:11 ` kbuild test robot @ 2017-08-09 20:28 ` Andrew Morton 0 siblings, 0 replies; 9+ messages in thread From: Andrew Morton @ 2017-08-09 20:28 UTC (permalink / raw) To: kbuild test robot Cc: Yury Norov, kbuild-all, Noam Camus, Rasmus Villemoes, Matthew Wilcox, Mauro Carvalho Chehab, linux-kernel 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); } } _ ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2017-08-10 10:38 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-08-07 22:54 [PATCH 1/2] lib: make bitmap_parselist thread-safe and much faster Yury Norov 2017-08-07 22:54 ` [PATCH 2/2] lib: add test for bitmap_parselist() Yury Norov 2017-08-09 3:28 ` kbuild test robot 2017-08-09 20:33 ` Andrew Morton 2017-08-09 22:52 ` Yury Norov 2017-08-10 7:30 ` Rasmus Villemoes 2017-08-10 10:37 ` Yury Norov 2017-08-09 4:11 ` kbuild test robot 2017-08-09 20:28 ` Andrew Morton
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).