2017-12-28 15:00:44

by Yury Norov

[permalink] [raw]
Subject: [PATCH 1/2] bitmap: new bitmap_copy_safe and bitmap_{from,to}_arr32

This patchset replaces bitmap_{to,from}_u32array with more simple
and standard looking copy-like functions.

bitmap_from_u32array() takes 4 arguments (bitmap_to_u32array is similar):
- unsigned long *bitmap, which is destination;
- unsigned int nbits, the length of destination bitmap, in bits;
- const u32 *buf, the source; and
- unsigned int nwords, the length of source buffer in ints.

In description to the function it is detailed like:
* copy min(nbits, 32*nwords) bits from @buf to @bitmap, remaining
* bits between nword and nbits in @bitmap (if any) are cleared.

Having two size arguments looks unneeded and potentially dangerous.

It is unneeded because normally user of copy-like function should
take care of the size of destination and make it big enough to fit
source data.

And it is dangerous because function may hide possible error if user
doesn't provide big enough bitmap, and data becomes silently dropped.

That's why all copy-like functions have 1 argument for size of copying
data, and I don't see any reason to make bitmap_from_u32array()
different.

One exception that comes in mind is strncpy() which also provides size
of destination in arguments, but it's strongly argued by the possibility
of taking broken strings in source. This is not the case of
bitmap_{from,to}_u32array().

There is no many real users of bitmap_{from,to}_u32array(), and they all
very clearly provide size of destination matched with the size of
source, so additional functionality is not used in fact. Like this:
bitmap_from_u32array(to->link_modes.supported,
__ETHTOOL_LINK_MODE_MASK_NBITS,
link_usettings.link_modes.supported,
__ETHTOOL_LINK_MODE_MASK_NU32);
Where:
#define __ETHTOOL_LINK_MODE_MASK_NU32 \
DIV_ROUND_UP(__ETHTOOL_LINK_MODE_MASK_NBITS, 32)

In this patch, bitmap_copy_safe and bitmap_{from,to}_arr32 are introduced.

'Safe' in bitmap_copy_safe() stands for clearing unused bits in bitmap
beyond last bit till the end of last word. It is useful for hardening
API when bitmap is assumed to be exposed to userspace.

bitmap_{from,to}_arr32 functions are replacements for
bitmap_{from,to}_u32array. They don't take unneeded nwords argument, and
so simpler in implementation and understanding.

This patch suggests optimization for 32-bit systems - aliasing
bitmap_{from,to}_arr32 to bitmap_copy_safe.

Other possible optimization is aliasing 64-bit LE bitmap_{from,to}_arr32 to
more generic function(s). But I didn't end up with the function that would
be helpful by itself, and can be used to alias 64-bit LE
bitmap_{from,to}_arr32, like bitmap_copy_safe() does. So I preferred to
leave things as is.

The following patch switches kernel to new API and introduces test for it.

Discussion is here.
https://lkml.org/lkml/2017/11/15/592

Rebased on 4.15-rc5 with some minor changes, and resent.

CC: Andrew Morton <[email protected]>
CC: Ben Hutchings <[email protected]>
CC: David Decotigny <[email protected]>,
CC: David S. Miller <[email protected]>,
CC: Geert Uytterhoeven <[email protected]>
CC: Matthew Wilcox <[email protected]>
CC: Rasmus Villemoes <[email protected]>
Signed-off-by: Yury Norov <[email protected]>
---
include/linux/bitmap.h | 31 ++++++++++++++++++++++++++++
lib/bitmap.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 87 insertions(+)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 3489253e38fc..748eba1622b9 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -66,6 +66,8 @@
* bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region
* bitmap_from_u32array(dst, nbits, buf, nwords) *dst = *buf (nwords 32b words)
* bitmap_to_u32array(buf, nwords, src, nbits) *buf = *dst (nwords 32b words)
+ * bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst
+ * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst
*
*/

@@ -228,6 +230,35 @@ static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
}
}

+/*
+ * Copy bitmap and clear tail bits in last word.
+ */
+static inline void bitmap_copy_safe(unsigned long *dst,
+ const unsigned long *src, unsigned int nbits)
+{
+ bitmap_copy(dst, src, nbits);
+ if (nbits % BITS_PER_LONG)
+ dst[nbits / BITS_PER_LONG] &= BITMAP_LAST_WORD_MASK(nbits);
+}
+
+/*
+ * On 32-bit systems bitmaps are represented as u32 arrays internally, and
+ * therefore conversion is not needed when copying data from/to arrays of u32.
+ */
+#if BITS_PER_LONG == 64
+extern void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
+ unsigned int nbits);
+extern void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
+ unsigned int nbits);
+#else
+#define bitmap_from_arr32(bitmap, buf, nbits) \
+ bitmap_copy_safe((unsigned long *) (bitmap), \
+ (const unsigned long *) (buf), (nbits))
+#define bitmap_to_arr32(buf, bitmap, nbits) \
+ bitmap_copy_safe((unsigned long *) (buf), \
+ (const unsigned long *) (bitmap), (nbits))
+#endif
+
static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
const unsigned long *src2, unsigned int nbits)
{
diff --git a/lib/bitmap.c b/lib/bitmap.c
index d8f0c094b18e..47fe6441562c 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1214,3 +1214,59 @@ void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int n
}
EXPORT_SYMBOL(bitmap_copy_le);
#endif
+
+#if BITS_PER_LONG == 64
+/**
+ * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
+ * @bitmap: array of unsigned longs, the destination bitmap
+ * @buf: array of u32 (in host byte order), the source bitmap
+ * @nbits: number of bits in @bitmap
+ */
+void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
+ unsigned int nbits)
+{
+ unsigned int i, halfwords;
+
+ if (!nbits)
+ return;
+
+ halfwords = DIV_ROUND_UP(nbits, 32);
+ for (i = 0; i < halfwords; i++) {
+ bitmap[i/2] = (unsigned long) buf[i];
+ if (++i < halfwords)
+ bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
+ }
+
+ /* Clear tail bits in last word beyond nbits. */
+ if (nbits % BITS_PER_LONG)
+ bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
+}
+EXPORT_SYMBOL(bitmap_from_arr32);
+
+/**
+ * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
+ * @buf: array of u32 (in host byte order), the dest bitmap
+ * @bitmap: array of unsigned longs, the source bitmap
+ * @nbits: number of bits in @bitmap
+ */
+void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
+{
+ unsigned int i, halfwords;
+
+ if (!nbits)
+ return;
+
+ halfwords = DIV_ROUND_UP(nbits, 32);
+ for (i = 0; i < halfwords; i++) {
+ buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
+ if (++i < halfwords)
+ buf[i] = (u32) (bitmap[i/2] >> 32);
+ }
+
+ /* Clear tail bits in last element of array beyond nbits. */
+ if (nbits % BITS_PER_LONG)
+ buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
+}
+EXPORT_SYMBOL(bitmap_to_arr32);
+
+#endif
--
2.11.0


2017-12-28 15:00:54

by Yury Norov

[permalink] [raw]
Subject: [PATCH 2/2] bitmap: replace bitmap_{from,to}_u32array

with bitmap_{from,to}_arr32 over the kernel. Additionally to it:
* __check_eq_bitmap() now takes single nbits argument.
* __check_eq_u32_array is not used in new test but may be used in
future. So I don't remove it here, but annotate as __used.

Tested on arm64 and 32-bit BE mips.

CC: Andrew Morton <[email protected]>
CC: Ben Hutchings <[email protected]>
CC: David Decotigny <[email protected]>,
CC: David S. Miller <[email protected]>,
CC: Geert Uytterhoeven <[email protected]>
CC: Matthew Wilcox <[email protected]>
CC: Rasmus Villemoes <[email protected]>
Signed-off-by: Yury Norov <[email protected]>
---
arch/arm64/kernel/perf_event.c | 5 +-
include/linux/bitmap.h | 11 +--
lib/bitmap.c | 87 -----------------
lib/test_bitmap.c | 206 +++++++----------------------------------
net/core/ethtool.c | 53 +++++------
5 files changed, 55 insertions(+), 307 deletions(-)

diff --git a/arch/arm64/kernel/perf_event.c b/arch/arm64/kernel/perf_event.c
index 3affca3dd96a..75b220ba73a3 100644
--- a/arch/arm64/kernel/perf_event.c
+++ b/arch/arm64/kernel/perf_event.c
@@ -925,9 +925,8 @@ static void __armv8pmu_probe_pmu(void *info)
pmceid[0] = read_sysreg(pmceid0_el0);
pmceid[1] = read_sysreg(pmceid1_el0);

- bitmap_from_u32array(cpu_pmu->pmceid_bitmap,
- ARMV8_PMUV3_MAX_COMMON_EVENTS, pmceid,
- ARRAY_SIZE(pmceid));
+ bitmap_from_arr32(cpu_pmu->pmceid_bitmap,
+ pmceid, ARMV8_PMUV3_MAX_COMMON_EVENTS);
}

static int armv8pmu_probe_pmu(struct arm_pmu *cpu_pmu)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 748eba1622b9..757af9bc4d36 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -64,8 +64,6 @@
* bitmap_find_free_region(bitmap, bits, order) Find and allocate bit region
* bitmap_release_region(bitmap, pos, order) Free specified bit region
* bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region
- * bitmap_from_u32array(dst, nbits, buf, nwords) *dst = *buf (nwords 32b words)
- * bitmap_to_u32array(buf, nwords, src, nbits) *buf = *dst (nwords 32b words)
* bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst
* bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst
*
@@ -176,14 +174,7 @@ extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
extern int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
extern void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
extern int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
-extern unsigned int bitmap_from_u32array(unsigned long *bitmap,
- unsigned int nbits,
- const u32 *buf,
- unsigned int nwords);
-extern unsigned int bitmap_to_u32array(u32 *buf,
- unsigned int nwords,
- const unsigned long *bitmap,
- unsigned int nbits);
+
#ifdef __BIG_ENDIAN
extern void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
#else
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 47fe6441562c..9e498c77ed0e 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1106,93 +1106,6 @@ int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
EXPORT_SYMBOL(bitmap_allocate_region);

/**
- * bitmap_from_u32array - copy the contents of a u32 array of bits to bitmap
- * @bitmap: array of unsigned longs, the destination bitmap, non NULL
- * @nbits: number of bits in @bitmap
- * @buf: array of u32 (in host byte order), the source bitmap, non NULL
- * @nwords: number of u32 words in @buf
- *
- * copy min(nbits, 32*nwords) bits from @buf to @bitmap, remaining
- * bits between nword and nbits in @bitmap (if any) are cleared. In
- * last word of @bitmap, the bits beyond nbits (if any) are kept
- * unchanged.
- *
- * Return the number of bits effectively copied.
- */
-unsigned int
-bitmap_from_u32array(unsigned long *bitmap, unsigned int nbits,
- const u32 *buf, unsigned int nwords)
-{
- unsigned int dst_idx, src_idx;
-
- for (src_idx = dst_idx = 0; dst_idx < BITS_TO_LONGS(nbits); ++dst_idx) {
- unsigned long part = 0;
-
- if (src_idx < nwords)
- part = buf[src_idx++];
-
-#if BITS_PER_LONG == 64
- if (src_idx < nwords)
- part |= ((unsigned long) buf[src_idx++]) << 32;
-#endif
-
- if (dst_idx < nbits/BITS_PER_LONG)
- bitmap[dst_idx] = part;
- else {
- unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
-
- bitmap[dst_idx] = (bitmap[dst_idx] & ~mask)
- | (part & mask);
- }
- }
-
- return min_t(unsigned int, nbits, 32*nwords);
-}
-EXPORT_SYMBOL(bitmap_from_u32array);
-
-/**
- * bitmap_to_u32array - copy the contents of bitmap to a u32 array of bits
- * @buf: array of u32 (in host byte order), the dest bitmap, non NULL
- * @nwords: number of u32 words in @buf
- * @bitmap: array of unsigned longs, the source bitmap, non NULL
- * @nbits: number of bits in @bitmap
- *
- * copy min(nbits, 32*nwords) bits from @bitmap to @buf. Remaining
- * bits after nbits in @buf (if any) are cleared.
- *
- * Return the number of bits effectively copied.
- */
-unsigned int
-bitmap_to_u32array(u32 *buf, unsigned int nwords,
- const unsigned long *bitmap, unsigned int nbits)
-{
- unsigned int dst_idx = 0, src_idx = 0;
-
- while (dst_idx < nwords) {
- unsigned long part = 0;
-
- if (src_idx < BITS_TO_LONGS(nbits)) {
- part = bitmap[src_idx];
- if (src_idx >= nbits/BITS_PER_LONG)
- part &= BITMAP_LAST_WORD_MASK(nbits);
- src_idx++;
- }
-
- buf[dst_idx++] = part & 0xffffffffUL;
-
-#if BITS_PER_LONG == 64
- if (dst_idx < nwords) {
- part >>= 32;
- buf[dst_idx++] = part & 0xffffffffUL;
- }
-#endif
- }
-
- return min_t(unsigned int, nbits, 32*nwords);
-}
-EXPORT_SYMBOL(bitmap_to_u32array);
-
-/**
* bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
* @dst: destination buffer
* @src: bitmap to copy
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index aa1f2669bdd5..de7ef2996a07 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -23,7 +23,7 @@ __check_eq_uint(const char *srcfile, unsigned int line,
const unsigned int exp_uint, unsigned int x)
{
if (exp_uint != x) {
- pr_warn("[%s:%u] expected %u, got %u\n",
+ pr_err("[%s:%u] expected %u, got %u\n",
srcfile, line, exp_uint, x);
return false;
}
@@ -33,19 +33,13 @@ __check_eq_uint(const char *srcfile, unsigned int line,

static bool __init
__check_eq_bitmap(const char *srcfile, unsigned int line,
- const unsigned long *exp_bmap, unsigned int exp_nbits,
- const unsigned long *bmap, unsigned int nbits)
+ const unsigned long *exp_bmap, const unsigned long *bmap,
+ unsigned int nbits)
{
- if (exp_nbits != nbits) {
- pr_warn("[%s:%u] bitmap length mismatch: expected %u, got %u\n",
- srcfile, line, exp_nbits, nbits);
- return false;
- }
-
if (!bitmap_equal(exp_bmap, bmap, nbits)) {
pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
srcfile, line,
- exp_nbits, exp_bmap, nbits, bmap);
+ nbits, exp_bmap, nbits, bmap);
return false;
}
return true;
@@ -69,6 +63,10 @@ __check_eq_pbl(const char *srcfile, unsigned int line,
static bool __init
__check_eq_u32_array(const char *srcfile, unsigned int line,
const u32 *exp_arr, unsigned int exp_len,
+ const u32 *arr, unsigned int len) __used;
+static bool __init
+__check_eq_u32_array(const char *srcfile, unsigned int line,
+ const u32 *exp_arr, unsigned int exp_len,
const u32 *arr, unsigned int len)
{
if (exp_len != len) {
@@ -255,171 +253,29 @@ static void __init test_bitmap_parselist(void)
}
}

-static void __init test_bitmap_u32_array_conversions(void)
+static void __init test_bitmap_arr32(void)
{
- DECLARE_BITMAP(bmap1, 1024);
- DECLARE_BITMAP(bmap2, 1024);
- u32 exp_arr[32], arr[32];
- unsigned nbits;
-
- for (nbits = 0 ; nbits < 257 ; ++nbits) {
- const unsigned int used_u32s = DIV_ROUND_UP(nbits, 32);
- unsigned int i, rv;
-
- bitmap_zero(bmap1, nbits);
- bitmap_set(bmap1, nbits, 1024 - nbits); /* garbage */
-
- memset(arr, 0xff, sizeof(arr));
- rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
- expect_eq_uint(nbits, rv);
-
- memset(exp_arr, 0xff, sizeof(exp_arr));
- memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
- expect_eq_u32_array(exp_arr, 32, arr, 32);
-
- bitmap_fill(bmap2, 1024);
- rv = bitmap_from_u32array(bmap2, nbits, arr, used_u32s);
- expect_eq_uint(nbits, rv);
- expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
-
- for (i = 0 ; i < nbits ; ++i) {
- /*
- * test conversion bitmap -> u32[]
- */
-
- bitmap_zero(bmap1, 1024);
- __set_bit(i, bmap1);
- bitmap_set(bmap1, nbits, 1024 - nbits); /* garbage */
-
- memset(arr, 0xff, sizeof(arr));
- rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
- expect_eq_uint(nbits, rv);
-
- /* 1st used u32 words contain expected bit set, the
- * remaining words are left unchanged (0xff)
- */
- memset(exp_arr, 0xff, sizeof(exp_arr));
- memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
- exp_arr[i/32] = (1U<<(i%32));
- expect_eq_u32_array(exp_arr, 32, arr, 32);
-
-
- /* same, with longer array to fill
- */
- memset(arr, 0xff, sizeof(arr));
- rv = bitmap_to_u32array(arr, 32, bmap1, nbits);
- expect_eq_uint(nbits, rv);
-
- /* 1st used u32 words contain expected bit set, the
- * remaining words are all 0s
- */
- memset(exp_arr, 0, sizeof(exp_arr));
- exp_arr[i/32] = (1U<<(i%32));
- expect_eq_u32_array(exp_arr, 32, arr, 32);
-
- /*
- * test conversion u32[] -> bitmap
- */
-
- /* the 1st nbits of bmap2 are identical to
- * bmap1, the remaining bits of bmap2 are left
- * unchanged (all 1s)
- */
- bitmap_fill(bmap2, 1024);
- rv = bitmap_from_u32array(bmap2, nbits,
- exp_arr, used_u32s);
- expect_eq_uint(nbits, rv);
-
- expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
-
- /* same, with more bits to fill
- */
- memset(arr, 0xff, sizeof(arr)); /* garbage */
- memset(arr, 0, used_u32s*sizeof(u32));
- arr[i/32] = (1U<<(i%32));
-
- bitmap_fill(bmap2, 1024);
- rv = bitmap_from_u32array(bmap2, 1024, arr, used_u32s);
- expect_eq_uint(used_u32s*32, rv);
-
- /* the 1st nbits of bmap2 are identical to
- * bmap1, the remaining bits of bmap2 are cleared
- */
- bitmap_zero(bmap1, 1024);
- __set_bit(i, bmap1);
- expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
-
-
- /*
- * test short conversion bitmap -> u32[] (1
- * word too short)
- */
- if (used_u32s > 1) {
- bitmap_zero(bmap1, 1024);
- __set_bit(i, bmap1);
- bitmap_set(bmap1, nbits,
- 1024 - nbits); /* garbage */
- memset(arr, 0xff, sizeof(arr));
-
- rv = bitmap_to_u32array(arr, used_u32s - 1,
- bmap1, nbits);
- expect_eq_uint((used_u32s - 1)*32, rv);
-
- /* 1st used u32 words contain expected
- * bit set, the remaining words are
- * left unchanged (0xff)
- */
- memset(exp_arr, 0xff, sizeof(exp_arr));
- memset(exp_arr, 0,
- (used_u32s-1)*sizeof(*exp_arr));
- if ((i/32) < (used_u32s - 1))
- exp_arr[i/32] = (1U<<(i%32));
- expect_eq_u32_array(exp_arr, 32, arr, 32);
- }
-
- /*
- * test short conversion u32[] -> bitmap (3
- * bits too short)
- */
- if (nbits > 3) {
- memset(arr, 0xff, sizeof(arr)); /* garbage */
- memset(arr, 0, used_u32s*sizeof(*arr));
- arr[i/32] = (1U<<(i%32));
-
- bitmap_zero(bmap1, 1024);
- rv = bitmap_from_u32array(bmap1, nbits - 3,
- arr, used_u32s);
- expect_eq_uint(nbits - 3, rv);
-
- /* we are expecting the bit < nbits -
- * 3 (none otherwise), and the rest of
- * bmap1 unchanged (0-filled)
- */
- bitmap_zero(bmap2, 1024);
- if (i < nbits - 3)
- __set_bit(i, bmap2);
- expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
-
- /* do the same with bmap1 initially
- * 1-filled
- */
-
- bitmap_fill(bmap1, 1024);
- rv = bitmap_from_u32array(bmap1, nbits - 3,
- arr, used_u32s);
- expect_eq_uint(nbits - 3, rv);
-
- /* we are expecting the bit < nbits -
- * 3 (none otherwise), and the rest of
- * bmap1 unchanged (1-filled)
- */
- bitmap_zero(bmap2, 1024);
- if (i < nbits - 3)
- __set_bit(i, bmap2);
- bitmap_set(bmap2, nbits-3, 1024 - nbits + 3);
- expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
- }
- }
+ unsigned int nbits, next_bit, len = sizeof(exp) * 8;
+ u32 arr[sizeof(exp) / 4];
+ DECLARE_BITMAP(bmap2, len);
+
+ memset(arr, 0xa5, sizeof(arr));
+
+ for (nbits = 0; nbits < len; ++nbits) {
+ bitmap_to_arr32(arr, exp, nbits);
+ bitmap_from_arr32(bmap2, arr, nbits);
+ expect_eq_bitmap(bmap2, exp, nbits);
+
+ next_bit = find_next_bit(bmap2,
+ round_up(nbits, BITS_PER_LONG), nbits);
+ if (next_bit < round_up(nbits, BITS_PER_LONG))
+ pr_err("bitmap_copy_arr32(nbits == %d:"
+ " tail is not safely cleared: %d\n",
+ nbits, next_bit);
+
+ if (nbits < len - 32)
+ expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
+ 0xa5a5a5a5);
}
}

@@ -454,7 +310,7 @@ static void noinline __init test_mem_optimisations(void)
static int __init test_bitmap_init(void)
{
test_zero_fill_copy();
- test_bitmap_u32_array_conversions();
+ test_bitmap_arr32();
test_bitmap_parselist();
test_mem_optimisations();

diff --git a/net/core/ethtool.c b/net/core/ethtool.c
index f8fcf450a36e..76f6ae37dd15 100644
--- a/net/core/ethtool.c
+++ b/net/core/ethtool.c
@@ -615,18 +615,15 @@ static int load_link_ksettings_from_user(struct ethtool_link_ksettings *to,
return -EFAULT;

memcpy(&to->base, &link_usettings.base, sizeof(to->base));
- bitmap_from_u32array(to->link_modes.supported,
- __ETHTOOL_LINK_MODE_MASK_NBITS,
- link_usettings.link_modes.supported,
- __ETHTOOL_LINK_MODE_MASK_NU32);
- bitmap_from_u32array(to->link_modes.advertising,
- __ETHTOOL_LINK_MODE_MASK_NBITS,
- link_usettings.link_modes.advertising,
- __ETHTOOL_LINK_MODE_MASK_NU32);
- bitmap_from_u32array(to->link_modes.lp_advertising,
- __ETHTOOL_LINK_MODE_MASK_NBITS,
- link_usettings.link_modes.lp_advertising,
- __ETHTOOL_LINK_MODE_MASK_NU32);
+ bitmap_from_arr32(to->link_modes.supported,
+ link_usettings.link_modes.supported,
+ __ETHTOOL_LINK_MODE_MASK_NBITS);
+ bitmap_from_arr32(to->link_modes.advertising,
+ link_usettings.link_modes.advertising,
+ __ETHTOOL_LINK_MODE_MASK_NBITS);
+ bitmap_from_arr32(to->link_modes.lp_advertising,
+ link_usettings.link_modes.lp_advertising,
+ __ETHTOOL_LINK_MODE_MASK_NBITS);

return 0;
}
@@ -642,18 +639,15 @@ store_link_ksettings_for_user(void __user *to,
struct ethtool_link_usettings link_usettings;

memcpy(&link_usettings.base, &from->base, sizeof(link_usettings));
- bitmap_to_u32array(link_usettings.link_modes.supported,
- __ETHTOOL_LINK_MODE_MASK_NU32,
- from->link_modes.supported,
- __ETHTOOL_LINK_MODE_MASK_NBITS);
- bitmap_to_u32array(link_usettings.link_modes.advertising,
- __ETHTOOL_LINK_MODE_MASK_NU32,
- from->link_modes.advertising,
- __ETHTOOL_LINK_MODE_MASK_NBITS);
- bitmap_to_u32array(link_usettings.link_modes.lp_advertising,
- __ETHTOOL_LINK_MODE_MASK_NU32,
- from->link_modes.lp_advertising,
- __ETHTOOL_LINK_MODE_MASK_NBITS);
+ bitmap_to_arr32(link_usettings.link_modes.supported,
+ from->link_modes.supported,
+ __ETHTOOL_LINK_MODE_MASK_NU32);
+ bitmap_to_arr32(link_usettings.link_modes.advertising,
+ from->link_modes.advertising,
+ __ETHTOOL_LINK_MODE_MASK_NU32);
+ bitmap_to_arr32(link_usettings.link_modes.lp_advertising,
+ from->link_modes.lp_advertising,
+ __ETHTOOL_LINK_MODE_MASK_NU32);

if (copy_to_user(to, &link_usettings, sizeof(link_usettings)))
return -EFAULT;
@@ -2359,10 +2353,8 @@ static int ethtool_get_per_queue_coalesce(struct net_device *dev,

useraddr += sizeof(*per_queue_opt);

- bitmap_from_u32array(queue_mask,
- MAX_NUM_QUEUE,
- per_queue_opt->queue_mask,
- DIV_ROUND_UP(MAX_NUM_QUEUE, 32));
+ bitmap_from_arr32(queue_mask, per_queue_opt->queue_mask,
+ MAX_NUM_QUEUE);

for_each_set_bit(bit, queue_mask, MAX_NUM_QUEUE) {
struct ethtool_coalesce coalesce = { .cmd = ETHTOOL_GCOALESCE };
@@ -2394,10 +2386,7 @@ static int ethtool_set_per_queue_coalesce(struct net_device *dev,

useraddr += sizeof(*per_queue_opt);

- bitmap_from_u32array(queue_mask,
- MAX_NUM_QUEUE,
- per_queue_opt->queue_mask,
- DIV_ROUND_UP(MAX_NUM_QUEUE, 32));
+ bitmap_from_arr32(queue_mask, per_queue_opt->queue_mask, MAX_NUM_QUEUE);
n_queue = bitmap_weight(queue_mask, MAX_NUM_QUEUE);
tmp = backup = kmalloc_array(n_queue, sizeof(*backup), GFP_KERNEL);
if (!backup)
--
2.11.0

2017-12-31 12:34:45

by Andy Shevchenko

[permalink] [raw]
Subject: Re: [PATCH 1/2] bitmap: new bitmap_copy_safe and bitmap_{from,to}_arr32

On Thu, Dec 28, 2017 at 5:00 PM, Yury Norov <[email protected]> wrote:
> This patchset replaces bitmap_{to,from}_u32array with more simple
> and standard looking copy-like functions.
>
> bitmap_from_u32array() takes 4 arguments (bitmap_to_u32array is similar):
> - unsigned long *bitmap, which is destination;
> - unsigned int nbits, the length of destination bitmap, in bits;
> - const u32 *buf, the source; and
> - unsigned int nwords, the length of source buffer in ints.
>
> In description to the function it is detailed like:
> * copy min(nbits, 32*nwords) bits from @buf to @bitmap, remaining
> * bits between nword and nbits in @bitmap (if any) are cleared.
>
> Having two size arguments looks unneeded and potentially dangerous.

For the first argument, it depends what logic we would like to put behind.
Imagine the case (and since these functions are targetting some wider
cases) when you have not aligned bitmap (nbits % BITS_PER_LONG != 0).

So, there are 2 cases, nwords > nbits / BITS_PER_U32, or nbits /
BITS_PER_U32 > nwords.

We have at least two options for the first one:
1) cut it to fit and return some code (or updated nbits, or ...) to
tell this to the caller;
2) return an error and do nothing.

For the second case one:
1) merge bitmaps;
2) fill with 0 or 1 (another parameter?) the rest of bitmap.

> It is unneeded because normally user of copy-like function should
> take care of the size of destination and make it big enough to fit
> source data.
>
> And it is dangerous because function may hide possible error if user
> doesn't provide big enough bitmap, and data becomes silently dropped.

We might return -E2BIG, for example.

> That's why all copy-like functions have 1 argument for size of copying
> data, and I don't see any reason to make bitmap_from_u32array()
> different.
>
> One exception that comes in mind is strncpy() which also provides size
> of destination in arguments, but it's strongly argued by the possibility
> of taking broken strings in source. This is not the case of
> bitmap_{from,to}_u32array().
>
> There is no many real users of bitmap_{from,to}_u32array(), and they all
> very clearly provide size of destination matched with the size of
> source, so additional functionality is not used in fact. Like this:
> bitmap_from_u32array(to->link_modes.supported,
> __ETHTOOL_LINK_MODE_MASK_NBITS,
> link_usettings.link_modes.supported,
> __ETHTOOL_LINK_MODE_MASK_NU32);
> Where:
> #define __ETHTOOL_LINK_MODE_MASK_NU32 \
> DIV_ROUND_UP(__ETHTOOL_LINK_MODE_MASK_NBITS, 32)

Consider more generic use of them.

For example, we have a big enough bitmap, but would like to copy only
few u32 items to it. Another case, we have quite big u32 array, but
would like to copy only some of them.
It is first what came to my mind, there are might be much more
interesting corner cases.

Will it survive?

> In this patch, bitmap_copy_safe and bitmap_{from,to}_arr32 are introduced.
>
> 'Safe' in bitmap_copy_safe() stands for clearing unused bits in bitmap
> beyond last bit till the end of last word. It is useful for hardening
> API when bitmap is assumed to be exposed to userspace.

Why not setting them? How do you know it's used in positive manner and
not negative (inverted)?

Another thing, it shouldn't be different by intuition how it behaves
against bitmap, either both magle it, or none. Or just choose another
(better) name. _safe sounds a bit confusing to me.

> bitmap_{from,to}_arr32 functions are replacements for
> bitmap_{from,to}_u32array. They don't take unneeded nwords argument, and
> so simpler in implementation and understanding.

Again, depends what logic we would like to have.
I can imagine the case when you have nbits defined as macro/constant
and wouldn't like to change over the code. In your case you
semantically substitute nbits of bitmap, by nbits of amount of data to
copy.

For me slightly cleaner to have full size of the destination buffer at
input rather than arbitrary number which might not prevent crashes in
some cases.

Consider snprintf() as example.

> This patch suggests optimization for 32-bit systems - aliasing
> bitmap_{from,to}_arr32 to bitmap_copy_safe.

So, you preventing *merge* by this. Not sure if it's desired.

> Other possible optimization is aliasing 64-bit LE bitmap_{from,to}_arr32 to
> more generic function(s). But I didn't end up with the function that would
> be helpful by itself, and can be used to alias 64-bit LE
> bitmap_{from,to}_arr32, like bitmap_copy_safe() does. So I preferred to
> leave things as is.
>
> The following patch switches kernel to new API and introduces test for it.
>
> Discussion is here.
> https://lkml.org/lkml/2017/11/15/592

Unfortunately didn't find any _discussion_ there...
Wasn't it elsewhere?

--
With Best Regards,
Andy Shevchenko

2018-01-04 17:44:04

by Yury Norov

[permalink] [raw]
Subject: Re: [PATCH 1/2] bitmap: new bitmap_copy_safe and bitmap_{from,to}_arr32

Hi Andy,

Thanks for review. Comments inline.

On Sun, Dec 31, 2017 at 02:34:42PM +0200, Andy Shevchenko wrote:
> On Thu, Dec 28, 2017 at 5:00 PM, Yury Norov <[email protected]> wrote:
> > This patchset replaces bitmap_{to,from}_u32array with more simple
> > and standard looking copy-like functions.
> >
> > bitmap_from_u32array() takes 4 arguments (bitmap_to_u32array is similar):
> > - unsigned long *bitmap, which is destination;
> > - unsigned int nbits, the length of destination bitmap, in bits;
> > - const u32 *buf, the source; and
> > - unsigned int nwords, the length of source buffer in ints.
> >
> > In description to the function it is detailed like:
> > * copy min(nbits, 32*nwords) bits from @buf to @bitmap, remaining
> > * bits between nword and nbits in @bitmap (if any) are cleared.
> >
> > Having two size arguments looks unneeded and potentially dangerous.
>
> For the first argument, it depends what logic we would like to put behind.
> Imagine the case (and since these functions are targetting some wider
> cases) when you have not aligned bitmap (nbits % BITS_PER_LONG != 0).
>
> So, there are 2 cases, nwords > nbits / BITS_PER_U32, or nbits /
> BITS_PER_U32 > nwords.
>
> We have at least two options for the first one:
> 1) cut it to fit and return some code (or updated nbits, or ...) to
> tell this to the caller;
> 2) return an error and do nothing.
>
> For the second case one:
> 1) merge bitmaps;
> 2) fill with 0 or 1 (another parameter?) the rest of bitmap.

This is the whole point of the patch.
Kernel users doesn't need all that functionality to manage the case
nwords != nbits / BITS_PER_U32. All existing users explicitly pass
nwords and nbits matched.

Support for unmatched nwords and nbits is pretty tricky. As you
mentioned here, there are 2 cases with (at least) 2 options for each
case. Existing code doesn't take all that into account, and if we go
handle it properly, we'll end up with quite big portion of code, which
we should also cover with tests, carefully comment and maintain. And
all this will be for nothing because there's no *real* users of that
functionality.

> > It is unneeded because normally user of copy-like function should
> > take care of the size of destination and make it big enough to fit
> > source data.
> >
> > And it is dangerous because function may hide possible error if user
> > doesn't provide big enough bitmap, and data becomes silently dropped.
>
> We might return -E2BIG, for example.
>
> > That's why all copy-like functions have 1 argument for size of copying
> > data, and I don't see any reason to make bitmap_from_u32array()
> > different.
> >
> > One exception that comes in mind is strncpy() which also provides size
> > of destination in arguments, but it's strongly argued by the possibility
> > of taking broken strings in source. This is not the case of
> > bitmap_{from,to}_u32array().
> >
> > There is no many real users of bitmap_{from,to}_u32array(), and they all
> > very clearly provide size of destination matched with the size of
> > source, so additional functionality is not used in fact. Like this:
> > bitmap_from_u32array(to->link_modes.supported,
> > __ETHTOOL_LINK_MODE_MASK_NBITS,
> > link_usettings.link_modes.supported,
> > __ETHTOOL_LINK_MODE_MASK_NU32);
> > Where:
> > #define __ETHTOOL_LINK_MODE_MASK_NU32 \
> > DIV_ROUND_UP(__ETHTOOL_LINK_MODE_MASK_NBITS, 32)
>
> Consider more generic use of them.
>
> For example, we have a big enough bitmap, but would like to copy only
> few u32 items to it. Another case, we have quite big u32 array, but
> would like to copy only some of them.
> It is first what came to my mind, there are might be much more
> interesting corner cases.
>
> Will it survive?

For your examples, I think, we already have a set of suitable functions
in lib/bitmap.c. *arr32 functions are only to convert bitmaps from/to
u32 arrays with different endianness, probably taken from userspace or
some hardware.

So, for your 1st example, function may look like this:
void bitmap_insert(hugemap, offset, smallmap, nbits)
{
unsigned long first = offset / BITS_PER_LONG;
unsigned long off = offset % BITS_PER_LONG;
unsigned long last = first + (nbits + off) / BITS_PER_LONG;
unsigned long first_smallmap = hugemap[first]
& BITMAP_FIRST_WORD_MASK(offset);
unsigned long last_smallmap = hugemap[first]
& BITMAP_LAST_WORD_MASK(nbits);

bitmap_zero(tmp, nbits + off);
__bitmap_shift_right(tmp, off);

tmp[0] &= hugemap[first];
tmp[(nbits + off) / BITS_PER_LONG] &= hugemap[last];
bitmap_copy(hugemap[first], smallmap, nbits);
}

And usage:
DECLARE_BITMAP(tmp, nbits + off);

bitmap_from_arr32(tmp, arr32, nbits);
bitmap_insert(hugemap, offset, tmp, nbits)

This is pretty artificial example. If there'll be real users of
bitmap_insert, I believe implementation will be different. But
proposed API would work fine for the case. And I don't like the
idea to join functions that implement internal logic with interface
functions that do from/to conversion.

> > In this patch, bitmap_copy_safe and bitmap_{from,to}_arr32 are introduced.
> >
> > 'Safe' in bitmap_copy_safe() stands for clearing unused bits in bitmap
> > beyond last bit till the end of last word. It is useful for hardening
> > API when bitmap is assumed to be exposed to userspace.
>
> Why not setting them? How do you know it's used in positive manner and
> not negative (inverted)?

They are not used at all normally. So any value is OK except one that
represents kernel state. Consider an attack where kernel is requested
to create 1-bit-length bitmap on stack and return it to user. If we
don't clear tail 31 or 63 bits, attacker get it. I don't know any
real example, but original functions take care of it, so I do.

> Another thing, it shouldn't be different by intuition how it behaves
> against bitmap, either both magle it, or none. Or just choose another
> (better) name. _safe sounds a bit confusing to me.

I picked term from implementation of list. There 'safe' stands for
safety against entry deletion. And here it was assumed safety against
kernel data expose. Any better name is welcome.

> > bitmap_{from,to}_arr32 functions are replacements for
> > bitmap_{from,to}_u32array. They don't take unneeded nwords argument, and
> > so simpler in implementation and understanding.
>
> Again, depends what logic we would like to have.
> I can imagine the case when you have nbits defined as macro/constant
> and wouldn't like to change over the code. In your case you
> semantically substitute nbits of bitmap, by nbits of amount of data to
> copy.
>
> For me slightly cleaner to have full size of the destination buffer at
> input rather than arbitrary number which might not prevent crashes in
> some cases.
>
> Consider snprintf() as example.

In comment to the patch I mentioned strncpy() function, but it's also true
for snprintf():
One exception that comes in mind is strncpy() which also provides size
of destination in arguments, but it's strongly argued by the possibility
of taking broken strings in source. This is not the case of
bitmap_{from,to}_u32array().

> > This patch suggests optimization for 32-bit systems - aliasing
> > bitmap_{from,to}_arr32 to bitmap_copy_safe.
>
> So, you preventing *merge* by this. Not sure if it's desired.

Sorry, I don't understand it. Could you elaborate?

> > Other possible optimization is aliasing 64-bit LE bitmap_{from,to}_arr32 to
> > more generic function(s). But I didn't end up with the function that would
> > be helpful by itself, and can be used to alias 64-bit LE
> > bitmap_{from,to}_arr32, like bitmap_copy_safe() does. So I preferred to
> > leave things as is.
> >
> > The following patch switches kernel to new API and introduces test for it.
> >
> > Discussion is here.
> > https://lkml.org/lkml/2017/11/15/592
>
> Unfortunately didn't find any _discussion_ there...
> Wasn't it elsewhere?

I was going to write 'RFC' but wrote 'discussion' for some reason.
There's no much discussion. Matthew Wilcox approved the idea, and
Andrew Morton took this series into his tree, which I also assume
means approve.

Yury

2018-01-08 23:29:28

by Rasmus Villemoes

[permalink] [raw]
Subject: Re: [PATCH 1/2] bitmap: new bitmap_copy_safe and bitmap_{from,to}_arr32

On 28 December 2017 at 16:00, Yury Norov <[email protected]> wrote:
>
> In this patch, bitmap_copy_safe and bitmap_{from,to}_arr32 are introduced.
>
> 'Safe' in bitmap_copy_safe() stands for clearing unused bits in bitmap
> beyond last bit till the end of last word. It is useful for hardening
> API when bitmap is assumed to be exposed to userspace.

I agree completely with getting rid of the complexity of the u32array
functions, and also think they should simply be implemented as a
memcpy() when possible.

I'm not a fan of the _safe suffix, though. It doesn't say what it's
safe from. For example, one possible interpretation is that it allows
src or dst to be NULL (becoming a noop in such a case). Why not say
what it does? _clear_tail, _clear_rest, something like that. Or maybe,
can we simply make bitmap_copy behave that way? Hm, probably not, a
bit too many users to check they'd all be ok with that.

Rasmus

2018-01-09 05:16:05

by Yury Norov

[permalink] [raw]
Subject: Re: [PATCH 1/2] bitmap: new bitmap_copy_safe and bitmap_{from,to}_arr32

On Tue, Jan 09, 2018 at 12:29:23AM +0100, Rasmus Villemoes wrote:
> On 28 December 2017 at 16:00, Yury Norov <[email protected]> wrote:
> >
> > In this patch, bitmap_copy_safe and bitmap_{from,to}_arr32 are introduced.
> >
> > 'Safe' in bitmap_copy_safe() stands for clearing unused bits in bitmap
> > beyond last bit till the end of last word. It is useful for hardening
> > API when bitmap is assumed to be exposed to userspace.
>
> I agree completely with getting rid of the complexity of the u32array
> functions, and also think they should simply be implemented as a
> memcpy() when possible.
>
> I'm not a fan of the _safe suffix, though. It doesn't say what it's
> safe from. For example, one possible interpretation is that it allows
> src or dst to be NULL (becoming a noop in such a case). Why not say
> what it does? _clear_tail, _clear_rest, something like that.

OK, _clear_tail sounds good. I have to send v2 anyway because there's
new driver coming that uses u32array, and I'll also do rename.
https://www.spinics.net/lists/arm-kernel/msg627220.html

> Or maybe,
> can we simply make bitmap_copy behave that way? Hm, probably not, a
> bit too many users to check they'd all be ok with that.

Yep, and there's explicit comment in lib/bitmap.c:
* The possible unused bits in the last, partially used word
* of a bitmap are 'don't care'. The implementation makes
* no particular effort to keep them zero. It ensures that
* their value will not affect the results of any operation.
* The bitmap operations that return Boolean (bitmap_empty,
* for example) or scalar (bitmap_weight, for example) results
* carefully filter out these unused bits from impacting their
* results.

Changing this may potentially affect performance, and anyway, too
revolutionary to me.

Yury