linux-kernel - Re: [PATCH v2 1/6] math.h: Add macros for rounding to the closest value

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <ZtHM5+SJ15Db+P2z@e133380.arm.com>
Date: Fri, 30 Aug 2024 14:45:11 +0100
From: Dave Martin <Dave.Martin@....com>
To: Devarsh Thakkar <devarsht@...com>
Cc: mchehab@...nel.org, hverkuil-cisco@...all.nl,
	linux-media@...r.kernel.org, linux-kernel@...r.kernel.org,
	sebastian.fricke@...labora.com, linux-doc@...r.kernel.org,
	praneeth@...com, nm@...com, vigneshr@...com, s-jain1@...com,
	r-donadkar@...com, b-brnich@...com, detheridge@...com,
	p-mantena@...com, vijayp@...com, andi.shyti@...ux.intel.com,
	nicolas@...fresne.ca, andriy.shevchenko@...ux.intel.com,
	jirislaby@...nel.org, davidgow@...gle.com, dlatypov@...gle.com,
	corbet@....net, broonie@...nel.org, jani.nikula@...el.com,
	rdunlap@...radead.org, nik.borisov@...e.com
Subject: Re: [PATCH v2 1/6] math.h: Add macros for rounding to the closest
 value

On Mon, Aug 26, 2024 at 08:38:17PM +0530, Devarsh Thakkar wrote:
> Add below rounding related macros:
> 
> round_closest_up(x, y) : Rounds x to the closest multiple of y where y is a
> power of 2, with a preference to round up in case two nearest values are
> possible.
> 
> round_closest_down(x, y) : Rounds x to the closest multiple of y where y is
> a power of 2, with a preference to round down in case two nearest values
> are possible.
> 
> roundclosest(x, y) : Rounds x to the closest multiple of y, this macro
> should generally be used only when y is not multiple of 2 as otherwise
> round_closest* macros should be used which are much faster.
> 
> Examples:
>  * round_closest_up(17, 4) = 16
>  * round_closest_up(15, 4) = 16
>  * round_closest_up(14, 4) = 16
>  * round_closest_down(17, 4) = 16
>  * round_closest_down(15, 4) = 16
>  * round_closest_down(14, 4) = 12
>  * roundclosest(21, 5) = 20
>  * roundclosest(19, 5) = 20
>  * roundclosest(17, 5) = 15
> 
> Signed-off-by: Devarsh Thakkar <devarsht@...com>
> Acked-by: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
> ---
> NOTE: This patch is inspired from the Mentor Graphics IPU driver [1]
> which uses similar macro locally and which is updated in further patch
> in the series to use this generic macro instead along with other drivers
> having similar requirements.
> 
> Link: https://elixir.bootlin.com/linux/v6.8.9/source/drivers/gpu/ipu-v3/ipu-image-convert.c#L480 [1]
> 
> Past discussions and alignment on this:
> https://lore.kernel.org/all/7e3ad816-6a2a-4e02-9b41-03a8562812ad@ti.com/#r
> https://lore.kernel.org/all/ZkISG6p1tn9Do-xY@smile.fi.intel.com/#r
> https://lore.kernel.org/all/ZlTt-YWzyRyhmT9n@smile.fi.intel.com/
> https://lore.kernel.org/all/ZmHDWeuezCEgj20m@smile.fi.intel.com/
> https://lore.kernel.org/all/ZloMFfGKLry6EWNL@smile.fi.intel.com/
> 
> Changelog:
> V2:
> - Fix grammar in macro description
> - Update roundclosest macro to use roundup to avoid overflow scenario
> ---
>  include/linux/math.h | 63 ++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 63 insertions(+)
> 
> diff --git a/include/linux/math.h b/include/linux/math.h
> index f5f18dc3616b..b59a02a007d7 100644
> --- a/include/linux/math.h
> +++ b/include/linux/math.h
> @@ -34,6 +34,52 @@
>   */
>  #define round_down(x, y) ((x) & ~__round_mask(x, y))
>  
> +/**
> + * round_closest_up - round closest to be multiple of the specified value
> + *                    (which is power of 2) with preference to rounding up
> + * @x: the value to round
> + * @y: multiple to round closest to (must be a power of 2)
> + *
> + * Rounds @x to the closest multiple of @y (which must be a power of 2).
> + * The value can be rounded up or rounded down depending on the rounded
> + * value's closeness to the specified value. Also, there can be two closest
> + * values, i.e. the difference between the specified value and its rounded-up
> + * and rounded-down values could be the same. In that case, the rounded-up
> + * value is preferred.
> + *
> + * To perform arbitrary rounding to the closest value (not multiple of 2), use
> + * roundclosest().
> + *
> + * Examples:
> + * * round_closest_up(17, 4) = 16
> + * * round_closest_up(15, 4) = 16
> + * * round_closest_up(14, 4) = 16
> + */
> +#define round_closest_up(x, y) round_down((x) + (y) / 2, (y))
> +
> +/**
> + * round_closest_down - round closest to be multiple of the specified value
> + *                      (which is power of 2) with preference to rounding down
> + * @x: the value to round
> + * @y: multiple to round closest to (must be a power of 2)
> + *
> + * Rounds @x to the closest multiple of @y (which must be a power of 2).
> + * The value can be rounded up or rounded down depending on the rounded
> + * value's closeness to the specified value. Also, there can be two closest
> + * values, i.e. the difference between the specified value and its rounded-up
> + * and rounded-down values could be the same. In that case, the rounded-down
> + * value is preferred.
> + *
> + * To perform arbitrary rounding to the closest value (not multiple of 2), use
> + * roundclosest().
> + *
> + * Examples:
> + * * round_closest_down(17, 4) = 16
> + * * round_closest_down(15, 4) = 16
> + * * round_closest_down(14, 4) = 12
> + */
> +#define round_closest_down(x, y) round_up((x) - (y) / 2, (y))
> +
>  #define DIV_ROUND_UP __KERNEL_DIV_ROUND_UP
>  
>  #define DIV_ROUND_DOWN_ULL(ll, d) \
> @@ -77,6 +123,23 @@
>  }							\
>  )
>  
> +/**
> + * roundclosest - round to the nearest multiple
> + * @x: the value to round
> + * @y: multiple to round nearest to
> + *
> + * Rounds @x to the nearest multiple of @y.
> + * The rounded value can be greater or less than @x depending
> + * upon its nearness to @x. If @y is always a power of 2, consider
> + * using the faster round_closest_up() or round_closest_down().
> + *
> + * Examples:
> + * * roundclosest(21, 5) = 20
> + * * roundclosest(19, 5) = 20
> + * * roundclosest(17, 5) = 15
> + */
> +#define roundclosest(x, y) roundup((x) - (y) / 2, (y))

roundup() looks like it already does the wrong thing for negative
numbers:

	roundup(-10, 5)
	= (-10 + 4) / 5 * 5
	= -6 / 5 * 5
	= -1 * 5
	= -5

(DIV_ROUND_UP looks less broken in this regard, though it's complicated
and I haven't tried to understand it fully.)

Disregarding the issue of negative inputs, the proposed definition of
roundclosest() looks like it still doesn't always do the right thing
close to the upper limits of types, even when the expected result is
representable in the type.

For example, if I've understood this correctly, we can get:

	roundclosest(0xFFFFFFFFU, 0xFFFFU)
	= roundup(0xFFFFFFFF - 0x7FFFU, 0xFFFFU)
	= roundup(0xFFFF8000, 0xFFFFU)
	= ((0xFFFF8000 + (0xFFFFU - 1)) / 0xFFFFU) * 0xFFFFU
	= ((0xFFFF8000 + 0xFFFEU) / 0xFFFFU) * 0xFFFFU
	= (0x00007FFE / 0xFFFFU) * 0xFFFFU
	= 0

(Expected result: 0x00010001U * 0xFFFFU, = 0xFFFFFFFFU.)

I suppose this could be documented around, but it seems like a
potential trap and not something the caller would expect.

Cheers
---Dave