[v3,RESEND,4/6] bitmap: Introduce bitmap_off()
Commit Message
The bitmap_onto() function translates one bitmap relative to another but
no function are present to perform the reverse translation.
Introduce bitmap_off() to fill this hole.
Signed-off-by: Herve Codina <herve.codina@bootlin.com>
---
include/linux/bitmap.h | 3 +++
lib/bitmap.c | 42 ++++++++++++++++++++++++++++++++++++++++++
2 files changed, 45 insertions(+)
Comments
On 12/02/2024 08.56, Herve Codina wrote:
> The bitmap_onto() function translates one bitmap relative to another but
> no function are present to perform the reverse translation.
>
> Introduce bitmap_off() to fill this hole.
>
> Signed-off-by: Herve Codina <herve.codina@bootlin.com>
> ---
> include/linux/bitmap.h | 3 +++
> lib/bitmap.c | 42 ++++++++++++++++++++++++++++++++++++++++++
This patch, or the next in the series, should include a diffstat
mentioning lib/test_bitmap.c. And please make sure that the tests
exercise both expected use as well as corner cases, so that the actual
expected behavior is documented in code and not just in prose (which may
be ambiguous), and so that behavior-changing refactorings will not go
unnoticed.
Rasmus
On Mon, Feb 12, 2024 at 08:56:32AM +0100, Herve Codina wrote:
> The bitmap_onto() function translates one bitmap relative to another but
> no function are present to perform the reverse translation.
>
> Introduce bitmap_off() to fill this hole.
>
> Signed-off-by: Herve Codina <herve.codina@bootlin.com>
> ---
> include/linux/bitmap.h | 3 +++
> lib/bitmap.c | 42 ++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 45 insertions(+)
>
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 99451431e4d6..5ecfcbbc91f4 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -65,6 +65,7 @@ struct device;
> * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src)
> * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit)
> * bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap
> + * bitmap_off(dst, orig, relmap, nbits) *dst = bitmap_onto() reverse operation
> * bitmap_fold(dst, orig, sz, nbits) dst bits = orig bits mod sz
> * bitmap_parse(buf, buflen, dst, nbits) Parse bitmap dst from kernel buf
> * bitmap_parse_user(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf
> @@ -208,6 +209,8 @@ int bitmap_bitremap(int oldbit,
> const unsigned long *old, const unsigned long *new, int bits);
> void bitmap_onto(unsigned long *dst, const unsigned long *orig,
> const unsigned long *relmap, unsigned int bits);
> +void bitmap_off(unsigned long *dst, const unsigned long *orig,
> + const unsigned long *relmap, unsigned int bits);
> void bitmap_fold(unsigned long *dst, const unsigned long *orig,
> unsigned int sz, unsigned int nbits);
>
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index 2feccb5047dc..71343967335e 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -682,6 +682,48 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
> }
> EXPORT_SYMBOL(bitmap_onto);
>
> +/**
> + * bitmap_off - revert operation done by bitmap_onto()
This is definitely a bad name. I've no a better idea, but even
bitmap_onto_revert() would be better.
> + * @dst: resulting translated bitmap
> + * @orig: original untranslated bitmap
> + * @relmap: bitmap relative to which translated
> + * @bits: number of bits in each of these bitmaps
> + *
> + * Suppose onto computed using bitmap_onto(onto, src, relmap, n)
> + * The operation bitmap_off(result, onto, relmap, n) leads to a
> + * result equal or equivalent to src.
Agree with Rasmus. This should be well tested.
> + * The result can be 'equivalent' because bitmap_onto() and
> + * bitmap_off() are not bijective.
> + * The result and src values are equivalent in that sense that a
> + * call to bitmap_onto(onto, src, relmap, n) and a call to
> + * bitmap_onto(onto, result, relmap, n) will lead to the same onto
> + * value.
Did you mean "a call to bitmap_onto(onto, src, relmap, n) and a
call to bitmap_off(onto, result, relmap, n)"?
I think the whole paragraph adds more confusion than explanations.
If a new function is supposed to revert the result of some other
function, I'd better focus on testing that it actually reverts as
advertised, and keep description as brief as possible.
> + * If either of @orig or @relmap is empty (no set bits), then @dst
> + * will be returned empty.
Is this an exception from the 'revert' policy? Doesn't look like that.
So, what for mentioning this specific case?
> + * All bits in @dst not set by the above rule are cleared.
The above rule is about empty @orig and @relmap, not about setting
bits. What did you mean here?
> + */
> +void bitmap_off(unsigned long *dst, const unsigned long *orig,
> + const unsigned long *relmap, unsigned int bits)
> +{
> + unsigned int n, m; /* same meaning as in above comment */
In the above comment, n means the size of bitmaps, and m is not
mentioned at all.
> + if (dst == orig) /* following doesn't handle inplace mappings */
> + return;
> + bitmap_zero(dst, bits);
Can you add an empty line after 'return'.
> + m = 0;
> + for_each_set_bit(n, relmap, bits) {
> + /* m == bitmap_pos_to_ord(relmap, n, bits) */
Don't think we need this comment here. If you want to underline that
m tracks bit order, can you just give it a more explanatory name. For
example, 'bit_order'.
> + if (test_bit(n, orig))
> + set_bit(m, dst);
> + m++;
> + }
> +}
> +EXPORT_SYMBOL(bitmap_off);
> +
> #ifdef CONFIG_NUMA
> /**
> * bitmap_fold - fold larger bitmap into smaller, modulo specified size
> --
> 2.43.0
On Mon, Feb 12, 2024 at 10:37:18AM -0800, Yury Norov wrote:
> On Mon, Feb 12, 2024 at 08:56:32AM +0100, Herve Codina wrote:
> > The bitmap_onto() function translates one bitmap relative to another but
> > no function are present to perform the reverse translation.
> >
> > Introduce bitmap_off() to fill this hole.
> >
> > Signed-off-by: Herve Codina <herve.codina@bootlin.com>
> > ---
> > include/linux/bitmap.h | 3 +++
> > lib/bitmap.c | 42 ++++++++++++++++++++++++++++++++++++++++++
> > 2 files changed, 45 insertions(+)
> >
> > diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> > index 99451431e4d6..5ecfcbbc91f4 100644
> > --- a/include/linux/bitmap.h
> > +++ b/include/linux/bitmap.h
> > @@ -65,6 +65,7 @@ struct device;
> > * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src)
> > * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit)
> > * bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap
> > + * bitmap_off(dst, orig, relmap, nbits) *dst = bitmap_onto() reverse operation
> > * bitmap_fold(dst, orig, sz, nbits) dst bits = orig bits mod sz
> > * bitmap_parse(buf, buflen, dst, nbits) Parse bitmap dst from kernel buf
> > * bitmap_parse_user(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf
> > @@ -208,6 +209,8 @@ int bitmap_bitremap(int oldbit,
> > const unsigned long *old, const unsigned long *new, int bits);
> > void bitmap_onto(unsigned long *dst, const unsigned long *orig,
> > const unsigned long *relmap, unsigned int bits);
> > +void bitmap_off(unsigned long *dst, const unsigned long *orig,
> > + const unsigned long *relmap, unsigned int bits);
> > void bitmap_fold(unsigned long *dst, const unsigned long *orig,
> > unsigned int sz, unsigned int nbits);
> >
> > diff --git a/lib/bitmap.c b/lib/bitmap.c
> > index 2feccb5047dc..71343967335e 100644
> > --- a/lib/bitmap.c
> > +++ b/lib/bitmap.c
> > @@ -682,6 +682,48 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
> > }
> > EXPORT_SYMBOL(bitmap_onto);
> >
> > +/**
> > + * bitmap_off - revert operation done by bitmap_onto()
>
> This is definitely a bad name. I've no a better idea, but even
> bitmap_onto_revert() would be better.
>
> > + * @dst: resulting translated bitmap
> > + * @orig: original untranslated bitmap
> > + * @relmap: bitmap relative to which translated
> > + * @bits: number of bits in each of these bitmaps
> > + *
> > + * Suppose onto computed using bitmap_onto(onto, src, relmap, n)
> > + * The operation bitmap_off(result, onto, relmap, n) leads to a
> > + * result equal or equivalent to src.
>
> Agree with Rasmus. This should be well tested.
>
> > + * The result can be 'equivalent' because bitmap_onto() and
> > + * bitmap_off() are not bijective.
> > + * The result and src values are equivalent in that sense that a
> > + * call to bitmap_onto(onto, src, relmap, n) and a call to
> > + * bitmap_onto(onto, result, relmap, n) will lead to the same onto
> > + * value.
>
> Did you mean "a call to bitmap_onto(onto, src, relmap, n) and a
> call to bitmap_off(onto, result, relmap, n)"?
>
> I think the whole paragraph adds more confusion than explanations.
> If a new function is supposed to revert the result of some other
> function, I'd better focus on testing that it actually reverts as
> advertised, and keep description as brief as possible.
>
> > + * If either of @orig or @relmap is empty (no set bits), then @dst
> > + * will be returned empty.
>
> Is this an exception from the 'revert' policy? Doesn't look like that.
> So, what for mentioning this specific case?
>
> > + * All bits in @dst not set by the above rule are cleared.
>
> The above rule is about empty @orig and @relmap, not about setting
> bits. What did you mean here?
>
> > + */
> > +void bitmap_off(unsigned long *dst, const unsigned long *orig,
> > + const unsigned long *relmap, unsigned int bits)
> > +{
> > + unsigned int n, m; /* same meaning as in above comment */
>
> In the above comment, n means the size of bitmaps, and m is not
> mentioned at all.
>
> > + if (dst == orig) /* following doesn't handle inplace mappings */
> > + return;
> > + bitmap_zero(dst, bits);
>
> Can you add an empty line after 'return'.
>
> > + m = 0;
> > + for_each_set_bit(n, relmap, bits) {
> > + /* m == bitmap_pos_to_ord(relmap, n, bits) */
>
> Don't think we need this comment here. If you want to underline that
> m tracks bit order, can you just give it a more explanatory name. For
> example, 'bit_order'.
>
> > + if (test_bit(n, orig))
> > + set_bit(m, dst);
> > + m++;
Forgot to mention - we need a __set_bit() and __test_bit(), because the
whole function is not atomic. This applies to the bitmap_onto() as
well. Can you please send a patch fixing it for bitmap_onto() in the
next iteration?
> > + }
> > +}
> > +EXPORT_SYMBOL(bitmap_off);
> > +
> > #ifdef CONFIG_NUMA
> > /**
> > * bitmap_fold - fold larger bitmap into smaller, modulo specified size
> > --
> > 2.43.0
@@ -65,6 +65,7 @@ struct device;
* bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src)
* bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit)
* bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap
+ * bitmap_off(dst, orig, relmap, nbits) *dst = bitmap_onto() reverse operation
* bitmap_fold(dst, orig, sz, nbits) dst bits = orig bits mod sz
* bitmap_parse(buf, buflen, dst, nbits) Parse bitmap dst from kernel buf
* bitmap_parse_user(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf
@@ -208,6 +209,8 @@ int bitmap_bitremap(int oldbit,
const unsigned long *old, const unsigned long *new, int bits);
void bitmap_onto(unsigned long *dst, const unsigned long *orig,
const unsigned long *relmap, unsigned int bits);
+void bitmap_off(unsigned long *dst, const unsigned long *orig,
+ const unsigned long *relmap, unsigned int bits);
void bitmap_fold(unsigned long *dst, const unsigned long *orig,
unsigned int sz, unsigned int nbits);
@@ -682,6 +682,48 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
}
EXPORT_SYMBOL(bitmap_onto);
+/**
+ * bitmap_off - revert operation done by bitmap_onto()
+ * @dst: resulting translated bitmap
+ * @orig: original untranslated bitmap
+ * @relmap: bitmap relative to which translated
+ * @bits: number of bits in each of these bitmaps
+ *
+ * Suppose onto computed using bitmap_onto(onto, src, relmap, n)
+ * The operation bitmap_off(result, onto, relmap, n) leads to a
+ * result equal or equivalent to src.
+ *
+ * The result can be 'equivalent' because bitmap_onto() and
+ * bitmap_off() are not bijective.
+ * The result and src values are equivalent in that sense that a
+ * call to bitmap_onto(onto, src, relmap, n) and a call to
+ * bitmap_onto(onto, result, relmap, n) will lead to the same onto
+ * value.
+ *
+ * If either of @orig or @relmap is empty (no set bits), then @dst
+ * will be returned empty.
+ *
+ * All bits in @dst not set by the above rule are cleared.
+ */
+void bitmap_off(unsigned long *dst, const unsigned long *orig,
+ const unsigned long *relmap, unsigned int bits)
+{
+ unsigned int n, m; /* same meaning as in above comment */
+
+ if (dst == orig) /* following doesn't handle inplace mappings */
+ return;
+ bitmap_zero(dst, bits);
+
+ m = 0;
+ for_each_set_bit(n, relmap, bits) {
+ /* m == bitmap_pos_to_ord(relmap, n, bits) */
+ if (test_bit(n, orig))
+ set_bit(m, dst);
+ m++;
+ }
+}
+EXPORT_SYMBOL(bitmap_off);
+
#ifdef CONFIG_NUMA
/**
* bitmap_fold - fold larger bitmap into smaller, modulo specified size