[v2,1/6] math.h: Add macros for rounding to the closest value

  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@ti.com>
Acked-by: Andy Shevchenko <andriy.shevchenko@linux.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(+)
  

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.

I understand the point, but if you need to send a v3, please explain
the equivalency between roundclosest() and one (or both?) of the
round_closest_*() in case the argument is power-of-2.

Because from the above I don't see what I'll get in such a case.
  

Hi Andy,

Thanks for the review.

On 26/08/24 23:14, Andy Shevchenko wrote:
> 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.
> 
> I understand the point, but if you need to send a v3, please explain
> the equivalency between roundclosest() and one (or both?) of the
> round_closest_*() in case the argument is power-of-2.
> 

The equivalency between roundclosest w.r.t round_closest is same as
equivalency between existing macros rounddown w.r.t round_down. Functionally
both are same but the former is recommended to be used only for the scenario
where multiple is not power of 2 and latter is faster but is strictly for the
scenario where multiple is power of 2. I think the same is already summarized
well in commit message and further elaborated in the patch itself as part of
header file comments [1] so I personally don't think any update is required
w.r.t this.

[1]: https://lore.kernel.org/all/20240826150822.4057164-2-devarsht@ti.com

Regards
Devarsh
  

On Tue, 27 Aug 2024, Devarsh Thakkar <devarsht@ti.com> wrote:
> Hi Andy,
>
> Thanks for the review.
>
> On 26/08/24 23:14, Andy Shevchenko wrote:
>> 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.
>> 
>> I understand the point, but if you need to send a v3, please explain
>> the equivalency between roundclosest() and one (or both?) of the
>> round_closest_*() in case the argument is power-of-2.
>> 
>
> The equivalency between roundclosest w.r.t round_closest is same as
> equivalency between existing macros rounddown w.r.t round_down. Functionally
> both are same but the former is recommended to be used only for the scenario
> where multiple is not power of 2 and latter is faster but is strictly for the
> scenario where multiple is power of 2. I think the same is already summarized
> well in commit message and further elaborated in the patch itself as part of
> header file comments [1] so I personally don't think any update is required
> w.r.t this.

I still don't think rounddown vs. round_down naming is a good example to
model anything after.

I have yet to hear a single compelling argument in favor of having a
single underscore in the middle of a name having implications about the
inputs of a macro/function.

The macros being added here are at 2 or 3 in Rusty's scale [1]. We could
aim for 6 (The name tells you how to use it), but also do opportunistic
8 (The compiler will warn if you get it wrong) for compile-time
constants.

As-is, these, and round_up/round_down, are just setting a trap for an
unsuspecting kernel developer to fall into.


BR,
Jani.


[1] https://ozlabs.org/~rusty/index.cgi/tech/2008-03-30.html


>
> [1]: https://lore.kernel.org/all/20240826150822.4057164-2-devarsht@ti.com
>
> Regards
> Devarsh
  

Hi Nikula,

Thanks for the review.

On 27/08/24 18:10, Jani Nikula wrote:
> On Tue, 27 Aug 2024, Devarsh Thakkar <devarsht@ti.com> wrote:

[..]

>> The equivalency between roundclosest w.r.t round_closest is same as
>> equivalency between existing macros rounddown w.r.t round_down. Functionally
>> both are same but the former is recommended to be used only for the scenario
>> where multiple is not power of 2 and latter is faster but is strictly for the
>> scenario where multiple is power of 2. I think the same is already summarized
>> well in commit message and further elaborated in the patch itself as part of
>> header file comments [1] so I personally don't think any update is required
>> w.r.t this.
> 
> I still don't think rounddown vs. round_down naming is a good example to
> model anything after.
> 
> I have yet to hear a single compelling argument in favor of having a
> single underscore in the middle of a name having implications about the
> inputs of a macro/function.
> 
> The macros being added here are at 2 or 3 in Rusty's scale [1]. We could
> aim for 6 (The name tells you how to use it), but also do opportunistic
> 8 (The compiler will warn if you get it wrong) for compile-time
> constants.
> 

The macros use existing round_up/round_down underneath, so need to check if
they have compile-time checks but either-way this should not block the current
series as the series does not aim to enhance the existing round_up/round_down
macros.

> As-is, these, and round_up/round_down, are just setting a trap for an
> unsuspecting kernel developer to fall into.
> 

I understand what you are saying but I believe this was already discussed in
original patch series [1] where you had raised the same issue and it was even
discussed if we want to go with a new naming convention (like
round_closest_up_pow_2) [2] or not and the final consensus reached on naming
was to align with the existing round*() macros [3]. Moreover, I didn't hear
back any further arguments on this in further 8 revisions carrying this patch,
so thought this was aligned per wider consensus.

Anyways, to re-iterate the discussion do we want to change to below naming scheme?

round_closest_up_pow_2
round_closest_down_pow_2
roundclosest

or any other suggestions for naming ?

If there is a wider consensus on the suggested name (and ok to deviate from
existing naming convention), then we can go ahead with that.

[1]: https://lore.kernel.org/all/ZkIG0-01pz632l4R@smile.fi.intel.com/
[2]: https://lore.kernel.org/all/5ebcf480-81c6-4c2d-96e8-727d44f21ca9@ti.com/
[3]:
https://lore.kernel.org/all/ZkIG0-01pz632l4R@smile.fi.intel.com/#:~:text=series%20is%20that%3A%0A%2D-,align,-naming%20(with%20the

Regards
Devarsh
> 
> BR,
> Jani.
> 
> 
> [1] https://ozlabs.org/~rusty/index.cgi/tech/2008-03-30.html
> 
> 
>>
>> [1]: https://lore.kernel.org/all/20240826150822.4057164-2-devarsht@ti.com
>>
>> Regards
>> Devarsh
>
  

On Tue, 27 Aug 2024, Devarsh Thakkar <devarsht@ti.com> wrote:
> Hi Nikula,
>
> Thanks for the review.
>
> On 27/08/24 18:10, Jani Nikula wrote:
>> On Tue, 27 Aug 2024, Devarsh Thakkar <devarsht@ti.com> wrote:
>
> [..]
>
>>> The equivalency between roundclosest w.r.t round_closest is same as
>>> equivalency between existing macros rounddown w.r.t round_down. Functionally
>>> both are same but the former is recommended to be used only for the scenario
>>> where multiple is not power of 2 and latter is faster but is strictly for the
>>> scenario where multiple is power of 2. I think the same is already summarized
>>> well in commit message and further elaborated in the patch itself as part of
>>> header file comments [1] so I personally don't think any update is required
>>> w.r.t this.
>> 
>> I still don't think rounddown vs. round_down naming is a good example to
>> model anything after.
>> 
>> I have yet to hear a single compelling argument in favor of having a
>> single underscore in the middle of a name having implications about the
>> inputs of a macro/function.
>> 
>> The macros being added here are at 2 or 3 in Rusty's scale [1]. We could
>> aim for 6 (The name tells you how to use it), but also do opportunistic
>> 8 (The compiler will warn if you get it wrong) for compile-time
>> constants.
>> 
>
> The macros use existing round_up/round_down underneath, so need to check if
> they have compile-time checks but either-way this should not block the current
> series as the series does not aim to enhance the existing round_up/round_down
> macros.
>
>> As-is, these, and round_up/round_down, are just setting a trap for an
>> unsuspecting kernel developer to fall into.
>> 
>
> I understand what you are saying but I believe this was already discussed in
> original patch series [1] where you had raised the same issue and it was even
> discussed if we want to go with a new naming convention (like
> round_closest_up_pow_2) [2] or not and the final consensus reached on naming
> was to align with the existing round*() macros [3]. Moreover, I didn't hear
> back any further arguments on this in further 8 revisions carrying this patch,
> so thought this was aligned per wider consensus.
>
> Anyways, to re-iterate the discussion do we want to change to below naming scheme?
>
> round_closest_up_pow_2
> round_closest_down_pow_2
> roundclosest
>
> or any other suggestions for naming ?
>
> If there is a wider consensus on the suggested name (and ok to deviate from
> existing naming convention), then we can go ahead with that.

The stupid thing here is, I still don't remember which one is the
generic thing, rounddown() or round_down(). I have to look it up every
single time to be sure. I refuse to believe I'd be the only one.

It's okay to accidentally use the generic version, no harm done. It's
definitely not okay to accidentally use the special pow-2 version, so it
should have a special name. I think _pow2() or _pow_2() is a fine
suffix.

Another stupid thing is, I'd name the generic thing round_down(). But
whoopsie, that's not the generic thing.

This naming puts an unnecessary extra burden on people. It's a stupid
"convention" to follow. It's a mistake. Not repeating a mistake trumps
following the pattern.

There, I've said it. Up to the people who ack and commit to decide.


BR,
Jani.


>
> [1]: https://lore.kernel.org/all/ZkIG0-01pz632l4R@smile.fi.intel.com/
> [2]: https://lore.kernel.org/all/5ebcf480-81c6-4c2d-96e8-727d44f21ca9@ti.com/
> [3]:
> https://lore.kernel.org/all/ZkIG0-01pz632l4R@smile.fi.intel.com/#:~:text=series%20is%20that%3A%0A%2D-,align,-naming%20(with%20the
>
> Regards
> Devarsh
>> 
>> BR,
>> Jani.
>> 
>> 
>> [1] https://ozlabs.org/~rusty/index.cgi/tech/2008-03-30.html
>> 
>> 
>>>
>>> [1]: https://lore.kernel.org/all/20240826150822.4057164-2-devarsht@ti.com
>>>
>>> Regards
>>> Devarsh
>>
  

On 29. 08. 24, 11:19, Jani Nikula wrote:
> The stupid thing here is, I still don't remember which one is the
> generic thing, rounddown() or round_down(). I have to look it up every
> single time to be sure. I refuse to believe I'd be the only one.
> 
> It's okay to accidentally use the generic version, no harm done. It's
> definitely not okay to accidentally use the special pow-2 version, so it
> should have a special name. I think _pow2() or _pow_2() is a fine
> suffix.

Concur.
  

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@ti.com>
> Acked-by: Andy Shevchenko <andriy.shevchenko@linux.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
  

Hi Andy, Randy, Sebastian,

On 29/08/24 15:24, Jiri Slaby wrote:
> On 29. 08. 24, 11:19, Jani Nikula wrote:
>> The stupid thing here is, I still don't remember which one is the
>> generic thing, rounddown() or round_down(). I have to look it up every
>> single time to be sure. I refuse to believe I'd be the only one.
>>
>> It's okay to accidentally use the generic version, no harm done. It's
>> definitely not okay to accidentally use the special pow-2 version, so it
>> should have a special name. I think _pow2() or _pow_2() is a fine
>> suffix.
> 
> Concur.
> 

We have got 2 votes to change round_closest_up to round_closest_up_pow_2 and
likewise for round_closest_down to round_closest_up_pow_2.

Kindly let us know if you have any concerns w.r.t above name change. Else, I
was thinking to proceed with the suggestion.

Regards
Devarsh
  

On 8/29/24 2:54 AM, Jiri Slaby wrote:
> On 29. 08. 24, 11:19, Jani Nikula wrote:
>> The stupid thing here is, I still don't remember which one is the
>> generic thing, rounddown() or round_down(). I have to look it up every
>> single time to be sure. I refuse to believe I'd be the only one.
>>
>> It's okay to accidentally use the generic version, no harm done. It's
>> definitely not okay to accidentally use the special pow-2 version, so it
>> should have a special name. I think _pow2() or _pow_2() is a fine
>> suffix.
> 
> Concur.
> 

Ack here also. I prefer _pow2().