[v2] Implement mul_u64_u64_div_u64_roundup()

[PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by David Laight 6 months, 4 weeks ago

Do an explicit BUG_ON(!divisor) instead of hoping the 'undefined
behaviour' the compiler generated for a compile-time 1/0 is in any
way useful.

It may be better to define the function to return ~(u64)0 for
divide by zero.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---

A new change for v2 of the patchset.
Whereas gcc inserts (IIRC) 'ud2' clang is likely to let the code
continue and generate 'random' results for any 'undefined bahaviour'.

 lib/math/div64.c | 10 +++-------
 1 file changed, 3 insertions(+), 7 deletions(-)

diff --git a/lib/math/div64.c b/lib/math/div64.c
index a5c966a36836..c426fa0660bc 100644
--- a/lib/math/div64.c
+++ b/lib/math/div64.c
@@ -186,6 +186,9 @@ EXPORT_SYMBOL(iter_div_u64_rem);
 #ifndef mul_u64_u64_div_u64
 u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
 {
+	/* Trigger exception if divisor is zero */
+	BUG_ON(!d);
+
 	if (ilog2(a) + ilog2(b) <= 62)
 		return div64_u64(a * b, d);
 
@@ -212,13 +215,6 @@ u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
 
 #endif
 
-	/* make sure d is not zero, trigger exception otherwise */
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wdiv-by-zero"
-	if (unlikely(d == 0))
-		return 1/0;
-#pragma GCC diagnostic pop
-
 	int shift = __builtin_ctzll(d);
 
 	/* try reducing the fraction in case the dividend becomes <= 64 bits */
-- 
2.39.5

Re: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by Nicolas Pitre 6 months, 3 weeks ago

On Sun, 18 May 2025, David Laight wrote:

> Do an explicit BUG_ON(!divisor) instead of hoping the 'undefined
> behaviour' the compiler generated for a compile-time 1/0 is in any
> way useful.
> 
> It may be better to define the function to return ~(u64)0 for
> divide by zero.
> 
> Signed-off-by: David Laight <david.laight.linux@gmail.com>
> ---
> 
> A new change for v2 of the patchset.
> Whereas gcc inserts (IIRC) 'ud2' clang is likely to let the code
> continue and generate 'random' results for any 'undefined bahaviour'.

clang does exactly the same as gcc.

As mentioned earlier, this is a soft NAK from me.

The above explanation is more speculation than fact. And here we really
want to duplicate the behavior a regular runtime 32-bit by 32-bit x/0
would produce, or in other words behave just like div64_u64() for that
matter.

>  lib/math/div64.c | 10 +++-------
>  1 file changed, 3 insertions(+), 7 deletions(-)
> 
> diff --git a/lib/math/div64.c b/lib/math/div64.c
> index a5c966a36836..c426fa0660bc 100644
> --- a/lib/math/div64.c
> +++ b/lib/math/div64.c
> @@ -186,6 +186,9 @@ EXPORT_SYMBOL(iter_div_u64_rem);
>  #ifndef mul_u64_u64_div_u64
>  u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
>  {
> +	/* Trigger exception if divisor is zero */
> +	BUG_ON(!d);
> +
>  	if (ilog2(a) + ilog2(b) <= 62)
>  		return div64_u64(a * b, d);
>  
> @@ -212,13 +215,6 @@ u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
>  
>  #endif
>  
> -	/* make sure d is not zero, trigger exception otherwise */
> -#pragma GCC diagnostic push
> -#pragma GCC diagnostic ignored "-Wdiv-by-zero"
> -	if (unlikely(d == 0))
> -		return 1/0;
> -#pragma GCC diagnostic pop
> -
>  	int shift = __builtin_ctzll(d);
>  
>  	/* try reducing the fraction in case the dividend becomes <= 64 bits */
> -- 
> 2.39.5
> 
>

Re: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by David Laight 6 months, 3 weeks ago

On Mon, 19 May 2025 22:21:15 -0400 (EDT)
Nicolas Pitre <npitre@baylibre.com> wrote:

> On Sun, 18 May 2025, David Laight wrote:
> 
> > Do an explicit BUG_ON(!divisor) instead of hoping the 'undefined
> > behaviour' the compiler generated for a compile-time 1/0 is in any
> > way useful.
> > 
> > It may be better to define the function to return ~(u64)0 for
> > divide by zero.
> > 
> > Signed-off-by: David Laight <david.laight.linux@gmail.com>
> > ---
> > 
> > A new change for v2 of the patchset.
> > Whereas gcc inserts (IIRC) 'ud2' clang is likely to let the code
> > continue and generate 'random' results for any 'undefined bahaviour'.  
> 
> clang does exactly the same as gcc.

Did you see the recent 'rant' from Linus about the way clang handles UB.
I'm pretty sure 'divide by zero' is UB, valid options include.
- Jump to random location in the current function (what Linus was ranting).
- Jump to any random location with any register values.
- Enable user access to all kernel memory.
- Permanently damage your cpu.
- Make your computer catch fire.
- Send an ICBM to some unspecified location.

If you want a 'divide by zero' error you better generate one. eg:
	int n = 0;
	OPTIMSER_HIDE_VAR(n);
	i = 1 / n;

    David

> 
> As mentioned earlier, this is a soft NAK from me.
> 
> The above explanation is more speculation than fact. And here we really
> want to duplicate the behavior a regular runtime 32-bit by 32-bit x/0
> would produce, or in other words behave just like div64_u64() for that
> matter.
> 
> >  lib/math/div64.c | 10 +++-------
> >  1 file changed, 3 insertions(+), 7 deletions(-)
> > 
> > diff --git a/lib/math/div64.c b/lib/math/div64.c
> > index a5c966a36836..c426fa0660bc 100644
> > --- a/lib/math/div64.c
> > +++ b/lib/math/div64.c
> > @@ -186,6 +186,9 @@ EXPORT_SYMBOL(iter_div_u64_rem);
> >  #ifndef mul_u64_u64_div_u64
> >  u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
> >  {
> > +	/* Trigger exception if divisor is zero */
> > +	BUG_ON(!d);
> > +
> >  	if (ilog2(a) + ilog2(b) <= 62)
> >  		return div64_u64(a * b, d);
> >  
> > @@ -212,13 +215,6 @@ u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
> >  
> >  #endif
> >  
> > -	/* make sure d is not zero, trigger exception otherwise */
> > -#pragma GCC diagnostic push
> > -#pragma GCC diagnostic ignored "-Wdiv-by-zero"
> > -	if (unlikely(d == 0))
> > -		return 1/0;
> > -#pragma GCC diagnostic pop
> > -
> >  	int shift = __builtin_ctzll(d);
> >  
> >  	/* try reducing the fraction in case the dividend becomes <= 64 bits */
> > -- 
> > 2.39.5
> > 
> >

Re: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by Nicolas Pitre 6 months, 3 weeks ago

On Tue, 20 May 2025, David Laight wrote:

> On Mon, 19 May 2025 22:21:15 -0400 (EDT)
> Nicolas Pitre <npitre@baylibre.com> wrote:
> 
> > On Sun, 18 May 2025, David Laight wrote:
> > 
> > > Do an explicit BUG_ON(!divisor) instead of hoping the 'undefined
> > > behaviour' the compiler generated for a compile-time 1/0 is in any
> > > way useful.
> > > 
> > > It may be better to define the function to return ~(u64)0 for
> > > divide by zero.
> > > 
> > > Signed-off-by: David Laight <david.laight.linux@gmail.com>
> > > ---
> > > 
> > > A new change for v2 of the patchset.
> > > Whereas gcc inserts (IIRC) 'ud2' clang is likely to let the code
> > > continue and generate 'random' results for any 'undefined bahaviour'.  
> > 
> > clang does exactly the same as gcc.
> 
> Did you see the recent 'rant' from Linus about the way clang handles UB.
> I'm pretty sure 'divide by zero' is UB, valid options include.
> - Jump to random location in the current function (what Linus was ranting).
> - Jump to any random location with any register values.
> - Enable user access to all kernel memory.
> - Permanently damage your cpu.
> - Make your computer catch fire.
> - Send an ICBM to some unspecified location.

LOL

> If you want a 'divide by zero' error you better generate one. eg:
> 	int n = 0;
> 	OPTIMSER_HIDE_VAR(n);
> 	i = 1 / n;

As you say then. As long as the resulting behavior is coherent for all 
division flavors on a given architecture.


Nicolas

Re: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by Uwe Kleine-König 6 months, 4 weeks ago

On Sun, May 18, 2025 at 02:38:46PM +0100, David Laight wrote:
> Do an explicit BUG_ON(!divisor) instead of hoping the 'undefined
> behaviour' the compiler generated for a compile-time 1/0 is in any
> way useful.
> 
> It may be better to define the function to return ~(u64)0 for
> divide by zero.
> 
> Signed-off-by: David Laight <david.laight.linux@gmail.com>
> ---
> 
> A new change for v2 of the patchset.
> Whereas gcc inserts (IIRC) 'ud2' clang is likely to let the code
> continue and generate 'random' results for any 'undefined bahaviour'.
> 
>  lib/math/div64.c | 10 +++-------
>  1 file changed, 3 insertions(+), 7 deletions(-)
> 
> diff --git a/lib/math/div64.c b/lib/math/div64.c
> index a5c966a36836..c426fa0660bc 100644
> --- a/lib/math/div64.c
> +++ b/lib/math/div64.c
> @@ -186,6 +186,9 @@ EXPORT_SYMBOL(iter_div_u64_rem);
>  #ifndef mul_u64_u64_div_u64
>  u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
>  {
> +	/* Trigger exception if divisor is zero */
> +	BUG_ON(!d);
> +

I'm unsure if I should like the BUG_ON better than return 1/0. My gut
feeling is that mul_u64_u64_div_u64() should behave in the same way as
e.g. div64_u64 (which is just `return dividend / divisor;` for 64bit
archs and thus triggers the same exception as `return 1/0;`.

If BUG_ON should be it, I'd prefer

	BUG_ON(unlikely(d == 0));

which keeps the unlikely() that is already in the check removed below
and is more explicit that checking for !d.

>  	if (ilog2(a) + ilog2(b) <= 62)
>  		return div64_u64(a * b, d);
>  
> @@ -212,13 +215,6 @@ u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
>  
>  #endif
>  
> -	/* make sure d is not zero, trigger exception otherwise */
> -#pragma GCC diagnostic push
> -#pragma GCC diagnostic ignored "-Wdiv-by-zero"
> -	if (unlikely(d == 0))
> -		return 1/0;
> -#pragma GCC diagnostic pop
> -
>  	int shift = __builtin_ctzll(d);
>  
>  	/* try reducing the fraction in case the dividend becomes <= 64 bits */

Best regards
Uwe

Re: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by David Laight 6 months, 4 weeks ago

On Mon, 19 May 2025 08:10:50 +0200
Uwe Kleine-König <u.kleine-koenig@baylibre.com> wrote:

> On Sun, May 18, 2025 at 02:38:46PM +0100, David Laight wrote:
> > Do an explicit BUG_ON(!divisor) instead of hoping the 'undefined
> > behaviour' the compiler generated for a compile-time 1/0 is in any
> > way useful.
> > 
> > It may be better to define the function to return ~(u64)0 for
> > divide by zero.
> > 
> > Signed-off-by: David Laight <david.laight.linux@gmail.com>
> > ---
> > 
> > A new change for v2 of the patchset.
> > Whereas gcc inserts (IIRC) 'ud2' clang is likely to let the code
> > continue and generate 'random' results for any 'undefined bahaviour'.
> > 
> >  lib/math/div64.c | 10 +++-------
> >  1 file changed, 3 insertions(+), 7 deletions(-)
> > 
> > diff --git a/lib/math/div64.c b/lib/math/div64.c
> > index a5c966a36836..c426fa0660bc 100644
> > --- a/lib/math/div64.c
> > +++ b/lib/math/div64.c
> > @@ -186,6 +186,9 @@ EXPORT_SYMBOL(iter_div_u64_rem);
> >  #ifndef mul_u64_u64_div_u64
> >  u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
> >  {
> > +	/* Trigger exception if divisor is zero */
> > +	BUG_ON(!d);
> > +  
> 
> I'm unsure if I should like the BUG_ON better than return 1/0. My gut
> feeling is that mul_u64_u64_div_u64() should behave in the same way as
> e.g. div64_u64 (which is just `return dividend / divisor;` for 64bit
> archs and thus triggers the same exception as `return 1/0;`.

You need to execute a run-time 1/0 not a compile-time one.
clang is likely to decide it is 'undefined behaviour' and just not
generate any code at all - including removing the 'if (!d)' condition.

For x86 gcc does (sometimes at least) generate 'if (!d) asm("ud2")'
but BUG_ON() adds a table entry for the fault site.

> If BUG_ON should be it, I'd prefer
> 
> 	BUG_ON(unlikely(d == 0));
> 
> which keeps the unlikely() that is already in the check removed below
> and is more explicit that checking for !d.

IIRC there is an 'unlikely' inside BUG_ON() - so the call site doesn't
need one.

	David

> >  	if (ilog2(a) + ilog2(b) <= 62)
> >  		return div64_u64(a * b, d);
> >  
> > @@ -212,13 +215,6 @@ u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
> >  
> >  #endif
> >  
> > -	/* make sure d is not zero, trigger exception otherwise */
> > -#pragma GCC diagnostic push
> > -#pragma GCC diagnostic ignored "-Wdiv-by-zero"
> > -	if (unlikely(d == 0))
> > -		return 1/0;
> > -#pragma GCC diagnostic pop
> > -
> >  	int shift = __builtin_ctzll(d);
> >  
> >  	/* try reducing the fraction in case the dividend becomes <= 64 bits */  
> 
> Best regards
> Uwe

Re: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by Nicolas Pitre 6 months, 4 weeks ago

On Mon, 19 May 2025, David Laight wrote:

> On Mon, 19 May 2025 08:10:50 +0200
> Uwe Kleine-König <u.kleine-koenig@baylibre.com> wrote:
> 
> > On Sun, May 18, 2025 at 02:38:46PM +0100, David Laight wrote:
> > > Do an explicit BUG_ON(!divisor) instead of hoping the 'undefined
> > > behaviour' the compiler generated for a compile-time 1/0 is in any
> > > way useful.
> > > 
> > > It may be better to define the function to return ~(u64)0 for
> > > divide by zero.
> > > 
> > > Signed-off-by: David Laight <david.laight.linux@gmail.com>
> > > ---
> > > 
> > > A new change for v2 of the patchset.
> > > Whereas gcc inserts (IIRC) 'ud2' clang is likely to let the code
> > > continue and generate 'random' results for any 'undefined bahaviour'.
> > > 
> > >  lib/math/div64.c | 10 +++-------
> > >  1 file changed, 3 insertions(+), 7 deletions(-)
> > > 
> > > diff --git a/lib/math/div64.c b/lib/math/div64.c
> > > index a5c966a36836..c426fa0660bc 100644
> > > --- a/lib/math/div64.c
> > > +++ b/lib/math/div64.c
> > > @@ -186,6 +186,9 @@ EXPORT_SYMBOL(iter_div_u64_rem);
> > >  #ifndef mul_u64_u64_div_u64
> > >  u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
> > >  {
> > > +	/* Trigger exception if divisor is zero */
> > > +	BUG_ON(!d);
> > > +  
> > 
> > I'm unsure if I should like the BUG_ON better than return 1/0. My gut
> > feeling is that mul_u64_u64_div_u64() should behave in the same way as
> > e.g. div64_u64 (which is just `return dividend / divisor;` for 64bit
> > archs and thus triggers the same exception as `return 1/0;`.
> 
> You need to execute a run-time 1/0 not a compile-time one.
> clang is likely to decide it is 'undefined behaviour' and just not
> generate any code at all - including removing the 'if (!d)' condition.

The code as it is works perfectly with both gcc and clang: it triggers 
the proper trap or
or call the corresponding exception handler. 

> For x86 gcc does (sometimes at least) generate 'if (!d) asm("ud2")'

And that's perfect. Did you find any occurrence when it is not the case?

> but BUG_ON() adds a table entry for the fault site.

You should really be as close as the behavior you get with a runtime x/y 
where y = 0. When that happens there are no BUG_ON().


Nicolas

Re: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by kernel test robot 6 months, 4 weeks ago

Hi David,

kernel test robot noticed the following build errors:

[auto build test ERROR on next-20250516]

url:    https://github.com/intel-lab-lkp/linux/commits/David-Laight/lib-mul_u64_u64_div_u64-rename-parameter-c-to-d/20250518-214037
base:   next-20250516
patch link:    https://lore.kernel.org/r/20250518133848.5811-3-david.laight.linux%40gmail.com
patch subject: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero
config: openrisc-allnoconfig (https://download.01.org/0day-ci/archive/20250518/202505182351.bPFZE1vO-lkp@intel.com/config)
compiler: or1k-linux-gcc (GCC) 14.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250518/202505182351.bPFZE1vO-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202505182351.bPFZE1vO-lkp@intel.com/

All errors (new ones prefixed by >>):

   lib/math/div64.c: In function 'mul_u64_u64_div_u64':
>> lib/math/div64.c:190:9: error: implicit declaration of function 'BUG_ON' [-Wimplicit-function-declaration]
     190 |         BUG_ON(!d);
         |         ^~~~~~


vim +/BUG_ON +190 lib/math/div64.c

   185	
   186	#ifndef mul_u64_u64_div_u64
   187	u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 d)
   188	{
   189		/* Trigger exception if divisor is zero */
 > 190		BUG_ON(!d);
   191	
   192		if (ilog2(a) + ilog2(b) <= 62)
   193			return div64_u64(a * b, d);
   194	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero

Posted by David Laight 6 months, 4 weeks ago

On Sun, 18 May 2025 23:42:44 +0800
kernel test robot <lkp@intel.com> wrote:

> Hi David,
> 
> kernel test robot noticed the following build errors:
> 
> [auto build test ERROR on next-20250516]
> 
> url:    https://github.com/intel-lab-lkp/linux/commits/David-Laight/lib-mul_u64_u64_div_u64-rename-parameter-c-to-d/20250518-214037
> base:   next-20250516
> patch link:    https://lore.kernel.org/r/20250518133848.5811-3-david.laight.linux%40gmail.com
> patch subject: [PATCH v2 next 2/4] lib: mul_u64_u64_div_u64() Use BUG_ON() for divide by zero
> config: openrisc-allnoconfig (https://download.01.org/0day-ci/archive/20250518/202505182351.bPFZE1vO-lkp@intel.com/config)
> compiler: or1k-linux-gcc (GCC) 14.2.0
> reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250518/202505182351.bPFZE1vO-lkp@intel.com/reproduce)
> 
> If you fix the issue in a separate patch/commit (i.e. not just a new version of
> the same patch/commit), kindly add following tags
> | Reported-by: kernel test robot <lkp@intel.com>
> | Closes: https://lore.kernel.org/oe-kbuild-all/202505182351.bPFZE1vO-lkp@intel.com/
> 
> All errors (new ones prefixed by >>):
> 
>    lib/math/div64.c: In function 'mul_u64_u64_div_u64':
> >> lib/math/div64.c:190:9: error: implicit declaration of function 'BUG_ON' [-Wimplicit-function-declaration]  
>      190 |         BUG_ON(!d);
>          |         ^~~~~~

compiles fine on x86 :-(