| Message ID | 20230710204339.3554919-2-willy@infradead.org (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | New page table range API | expand |
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?
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)
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.
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>
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
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 --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
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(+)