linux-kernel - Re: [PATCH v2 1/2] lib/math/rational.c: Fix divide by zero

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: <YK0fHBtcQ/32QiyT@smile.fi.intel.com>
Date:   Tue, 25 May 2021 19:00:28 +0300
From:   Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
To:     Trent Piepho <tpiepho@...il.com>
Cc:     linux-kernel@...r.kernel.org, andy@...nel.org,
        akpm@...ux-foundation.org, oskar@...ra.com,
        Daniel Latypov <dlatypov@...gle.com>,
        Yiyuan Guo <yguoaz@...il.com>
Subject: Re: [PATCH v2 1/2] lib/math/rational.c: Fix divide by zero

On Tue, May 25, 2021 at 07:42:49AM -0700, Trent Piepho wrote:
> If the input is out of the range of the allowed values, either larger
> than the largest value or closer to zero than the smallest non-zero
> allowed value, then a division by zero would occur.
> 
> In the case of input too large, the division by zero will occur on the
> first iteration.  The best result (largest allowed value) will be found
> by always choosing the semi-convergent and excluding the denominator
> based limit when finding it.
> 
> In the case of the input too small, the division by zero will occur on
> the second iteration.  The numerator based semi-convergent should not be
> calculated to avoid the division by zero.  But the semi-convergent vs
> previous convergent test is still needed, which effectively chooses
> between 0 (the previous convergent) vs the smallest allowed fraction
> (best semi-convergent) as the result.

LGTM, thanks!
Reviewed-by: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>

> Fixes: 323dd2c3ed0 ("lib/math/rational.c: fix possible incorrect result from rational fractions helper")
> Reported-by: Yiyuan Guo <yguoaz@...il.com>
> Signed-off-by: Trent Piepho <tpiepho@...il.com>
> ---
>  lib/math/rational.c | 16 +++++++++++-----
>  1 file changed, 11 insertions(+), 5 deletions(-)
> 
> diff --git a/lib/math/rational.c b/lib/math/rational.c
> index 9781d521963d..c0ab51d8fbb9 100644
> --- a/lib/math/rational.c
> +++ b/lib/math/rational.c
> @@ -12,6 +12,7 @@
>  #include <linux/compiler.h>
>  #include <linux/export.h>
>  #include <linux/minmax.h>
> +#include <linux/limits.h>
>  
>  /*
>   * calculate best rational approximation for a given fraction
> @@ -78,13 +79,18 @@ void rational_best_approximation(
>  		 * found below as 't'.
>  		 */
>  		if ((n2 > max_numerator) || (d2 > max_denominator)) {
> -			unsigned long t = min((max_numerator - n0) / n1,
> -					      (max_denominator - d0) / d1);
> +			unsigned long t = ULONG_MAX;
>  
> -			/* This tests if the semi-convergent is closer
> -			 * than the previous convergent.
> +			if (d1)
> +				t = (max_denominator - d0) / d1;
> +			if (n1)
> +				t = min(t, (max_numerator - n0) / n1);
> +
> +			/* This tests if the semi-convergent is closer than the previous
> +			 * convergent.  If d1 is zero there is no previous convergent as this
> +			 * is the 1st iteration, so always choose the semi-convergent.
>  			 */
> -			if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
> +			if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
>  				n1 = n0 + t * n1;
>  				d1 = d0 + t * d1;
>  			}
> -- 
> 2.26.2
> 

-- 
With Best Regards,
Andy Shevchenko