diff mbox series

[v5,01/38] minmax: Add in_range() macro

Message ID 20230710204339.3554919-2-willy@infradead.org
State New
Headers
Series New page table range API |

Commit Message

Matthew Wilcox July 10, 2023, 8:43 p.m. UTC 
  Determine if a value lies within a range more efficiently (subtraction +
comparison vs two comparisons and an AND).  It also has useful (under
some circumstances) behaviour if the range exceeds the maximum value of
the type.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 include/linux/minmax.h | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

Comments

Andrew Morton July 10, 2023, 11:13 p.m. UTC | #1 
On Mon, 10 Jul 2023 21:43:02 +0100 "Matthew Wilcox (Oracle)" <willy@infradead.org> wrote:

> Determine if a value lies within a range more efficiently (subtraction +
> comparison vs two comparisons and an AND).  It also has useful (under
> some circumstances) behaviour if the range exceeds the maximum value of
> the type.
> 
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> --- a/include/linux/minmax.h
> +++ b/include/linux/minmax.h
> @@ -158,6 +158,32 @@
>   */
>  #define clamp_val(val, lo, hi) clamp_t(typeof(val), val, lo, hi)
>  
> +static inline bool in_range64(u64 val, u64 start, u64 len)
> +{
> +	return (val - start) < len;
> +}
> +
> +static inline bool in_range32(u32 val, u32 start, u32 len)
> +{
> +	return (val - start) < len;
> +}
> +
> +/**
> + * in_range - Determine if a value lies within a range.
> + * @val: Value to test.
> + * @start: First value in range.
> + * @len: Number of values in range.
> + *
> + * This is more efficient than "if (start <= val && val < (start + len))".
> + * It also gives a different answer if @start + @len overflows the size of
> + * the type by a sufficient amount to encompass @val.  Decide for yourself
> + * which behaviour you want, or prove that start + len never overflow.
> + * Do not blindly replace one form with the other.
> + */
> +#define in_range(val, start, len)					\
> +	sizeof(start) <= sizeof(u32) ? in_range32(val, start, len) :	\
> +		in_range64(val, start, len)

There's nothing here to prevent callers from passing a mixture of
32-bit and 64-bit values, possibly resulting in truncation of `val' or
`len'.

Obviously caller is being dumb, but I think it's cost-free to check all
three of the arguments for 64-bitness?

Or do a min()/max()-style check for consistently typed arguments?
Matthew Wilcox July 11, 2023, 2:14 a.m. UTC | #2 
On Mon, Jul 10, 2023 at 04:13:41PM -0700, Andrew Morton wrote:
> > +/**
> > + * in_range - Determine if a value lies within a range.
> > + * @val: Value to test.
> > + * @start: First value in range.
> > + * @len: Number of values in range.
> > + *
> > + * This is more efficient than "if (start <= val && val < (start + len))".
> > + * It also gives a different answer if @start + @len overflows the size of
> > + * the type by a sufficient amount to encompass @val.  Decide for yourself
> > + * which behaviour you want, or prove that start + len never overflow.
> > + * Do not blindly replace one form with the other.
> > + */
> > +#define in_range(val, start, len)					\
> > +	sizeof(start) <= sizeof(u32) ? in_range32(val, start, len) :	\
> > +		in_range64(val, start, len)
> 
> There's nothing here to prevent callers from passing a mixture of
> 32-bit and 64-bit values, possibly resulting in truncation of `val' or
> `len'.
> 
> Obviously caller is being dumb, but I think it's cost-free to check all
> three of the arguments for 64-bitness?
> 
> Or do a min()/max()-style check for consistently typed arguments?

How about

#define in_range(val, start, len)					\
	(sizeof(val) | sizeof(start) | size(len)) <= sizeof(u32) ?	\
		in_range32(val, start, len) : in_range64(val, start, len)
Christoph Hellwig July 11, 2023, 5:28 a.m. UTC | #3 
On Mon, Jul 10, 2023 at 09:43:02PM +0100, Matthew Wilcox (Oracle) wrote:
> Determine if a value lies within a range more efficiently (subtraction +
> comparison vs two comparisons and an AND).  It also has useful (under
> some circumstances) behaviour if the range exceeds the maximum value of
> the type.

Should this also drop existing versions of in_range()?  E.g. btrfs
already has its own.
Andrew Morton July 11, 2023, 3:49 p.m. UTC | #4 
On Tue, 11 Jul 2023 03:14:44 +0100 Matthew Wilcox <willy@infradead.org> wrote:

> On Mon, Jul 10, 2023 at 04:13:41PM -0700, Andrew Morton wrote:
> > > +/**
> > > + * in_range - Determine if a value lies within a range.
> > > + * @val: Value to test.
> > > + * @start: First value in range.
> > > + * @len: Number of values in range.
> > > + *
> > > + * This is more efficient than "if (start <= val && val < (start + len))".
> > > + * It also gives a different answer if @start + @len overflows the size of
> > > + * the type by a sufficient amount to encompass @val.  Decide for yourself
> > > + * which behaviour you want, or prove that start + len never overflow.
> > > + * Do not blindly replace one form with the other.
> > > + */
> > > +#define in_range(val, start, len)					\
> > > +	sizeof(start) <= sizeof(u32) ? in_range32(val, start, len) :	\
> > > +		in_range64(val, start, len)
> > 
> > There's nothing here to prevent callers from passing a mixture of
> > 32-bit and 64-bit values, possibly resulting in truncation of `val' or
> > `len'.
> > 
> > Obviously caller is being dumb, but I think it's cost-free to check all
> > three of the arguments for 64-bitness?
> > 
> > Or do a min()/max()-style check for consistently typed arguments?
> 
> How about
> 
> #define in_range(val, start, len)					\
> 	(sizeof(val) | sizeof(start) | size(len)) <= sizeof(u32) ?	\
> 		in_range32(val, start, len) : in_range64(val, start, len)

It saves some typing ;)   sizeof(val+start+len)?  <no>
Ryan Roberts July 21, 2023, 10:14 a.m. UTC | #5 
On 10/07/2023 21:43, Matthew Wilcox (Oracle) wrote:
> Determine if a value lies within a range more efficiently (subtraction +
> comparison vs two comparisons and an AND).  It also has useful (under
> some circumstances) behaviour if the range exceeds the maximum value of
> the type.

Sorry it's taken me a while to looking at this.

I'm getting a lot of warnings about in_range() being redefined when building
arm64 (defconfig-ish) with this patch set on top of v6.5-rc2.

Looks like there are multiple existing implementations.

Thanks,
Ryan
David Laight July 24, 2023, 3:21 p.m. UTC | #6 
From: Andrew Morton
> Sent: 11 July 2023 00:14
> To: Matthew Wilcox (Oracle) <willy@infradead.org>
> Cc: linux-arch@vger.kernel.org; linux-mm@kvack.org; linux-kernel@vger.kernel.org
> Subject: Re: [PATCH v5 01/38] minmax: Add in_range() macro
> 
> On Mon, 10 Jul 2023 21:43:02 +0100 "Matthew Wilcox (Oracle)" <willy@infradead.org> wrote:
> 
> > Determine if a value lies within a range more efficiently (subtraction +
> > comparison vs two comparisons and an AND).  It also has useful (under
> > some circumstances) behaviour if the range exceeds the maximum value of
> > the type.
> >
> > Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> > --- a/include/linux/minmax.h
> > +++ b/include/linux/minmax.h
> > @@ -158,6 +158,32 @@
> >   */
> >  #define clamp_val(val, lo, hi) clamp_t(typeof(val), val, lo, hi)
> >
> > +static inline bool in_range64(u64 val, u64 start, u64 len)
> > +{
> > +	return (val - start) < len;
> > +}
> > +
> > +static inline bool in_range32(u32 val, u32 start, u32 len)
> > +{
> > +	return (val - start) < len;
> > +}
> > +
> > +/**
> > + * in_range - Determine if a value lies within a range.
> > + * @val: Value to test.
> > + * @start: First value in range.
> > + * @len: Number of values in range.
> > + *
> > + * This is more efficient than "if (start <= val && val < (start + len))".
> > + * It also gives a different answer if @start + @len overflows the size of
> > + * the type by a sufficient amount to encompass @val.  Decide for yourself
> > + * which behaviour you want, or prove that start + len never overflow.
> > + * Do not blindly replace one form with the other.
> > + */
> > +#define in_range(val, start, len)					\
> > +	sizeof(start) <= sizeof(u32) ? in_range32(val, start, len) :	\
> > +		in_range64(val, start, len)
> 
> There's nothing here to prevent callers from passing a mixture of
> 32-bit and 64-bit values, possibly resulting in truncation of `val' or
> `len'.
> 
> Obviously caller is being dumb, but I think it's cost-free to check all
> three of the arguments for 64-bitness?
> 
> Or do a min()/max()-style check for consistently typed arguments?

Just use integer promotions to extend everything to 'unsigned long long'.

#define in_range(val, start, len) ((val) + 0ull - (start)) < (len))

If all the values are unsigned 32bit the compiler will discard
all the zero extensions.

If values might be signed types (with non-negative values)
you might want to do explicit ((xxx) + 0u + 0ul + 0ull) to avoid
any potentially expensive sign extensions.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
diff mbox series

Patch

diff --git a/include/linux/minmax.h b/include/linux/minmax.h
index 396df1121bff..028069a1f7ef 100644
--- a/include/linux/minmax.h
+++ b/include/linux/minmax.h
@@ -158,6 +158,32 @@ 
  */
 #define clamp_val(val, lo, hi) clamp_t(typeof(val), val, lo, hi)
 
+static inline bool in_range64(u64 val, u64 start, u64 len)
+{
+	return (val - start) < len;
+}
+
+static inline bool in_range32(u32 val, u32 start, u32 len)
+{
+	return (val - start) < len;
+}
+
+/**
+ * in_range - Determine if a value lies within a range.
+ * @val: Value to test.
+ * @start: First value in range.
+ * @len: Number of values in range.
+ *
+ * This is more efficient than "if (start <= val && val < (start + len))".
+ * It also gives a different answer if @start + @len overflows the size of
+ * the type by a sufficient amount to encompass @val.  Decide for yourself
+ * which behaviour you want, or prove that start + len never overflow.
+ * Do not blindly replace one form with the other.
+ */
+#define in_range(val, start, len)					\
+	sizeof(start) <= sizeof(u32) ? in_range32(val, start, len) :	\
+		in_range64(val, start, len)
+
 /**
  * swap - swap values of @a and @b
  * @a: first value