linux-kernel - Re: [PATCH v2] string_helpers: fix precision loss for some inputs

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]

Date:	Tue, 03 Nov 2015 15:42:29 -0800
From:	James Bottomley <James.Bottomley@...senPartnership.com>
To:	Rasmus Villemoes <linux@...musvillemoes.dk>
Cc:	Vitaly Kuznetsov <vkuznets@...hat.com>,
	linux-scsi <linux-scsi@...r.kernel.org>,
	"ulf.hansson@...aro.org" <ulf.hansson@...aro.org>,
	"andriy.shevchenko@...ux.intel.com" 
	<andriy.shevchenko@...ux.intel.com>,
	"keescook@...omium.org" <keescook@...omium.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"akpm@...ux-foundation.org" <akpm@...ux-foundation.org>
Subject: Re: [PATCH v2] string_helpers: fix precision loss for some inputs

On Wed, 2015-11-04 at 00:26 +0100, Rasmus Villemoes wrote:
> On Tue, Nov 03 2015, James Bottomley <James.Bottomley@...senPartnership.com> wrote:
> 
> > On Tue, 2015-11-03 at 23:13 +0100, Rasmus Villemoes wrote:
> >> On Tue, Nov 03 2015, James Bottomley <James.Bottomley@...senPartnership.com> wrote:
> >> 
> >> > From: James Bottomley <JBottomley@...n.com>
> >> >
> >> > It was noticed that we lose precision in the final calculation for some
> >> > inputs.  The most egregious example is size=3000 blk_size=1900 in units of 10
> >> > should yield 5.70 MB but in fact yields 3.00 MB (oops). This is because the
> >> > current algorithm doesn't correctly account for all the remainders in the
> >> > logarithms.  Fix this by doing a correct calculation in the remainders based
> >> > on napier's algorithm.  Additionally, now we have the correct result, we have
> >> > to account for arithmetic rounding because we're printing 3 digits of
> >> > precision.  This means that if the fourth digit is five or greater, we have to
> >> > round up, so add a section to ensure correct rounding.  Finally account for
> >> > all possible inputs correctly, including zero for block size.
> >> >
> >> > Reported-by: Vitaly Kuznetsov <vkuznets@...hat.com>
> >> > Cc: stable@...r.kernel.org	# delay backport by two months for testing
> >> > Fixes: b9f28d863594c429e1df35a0474d2663ca28b307
> >> > Signed-off-by: James Bottomley <JBottomley@...n.com>
> >> >
> >> > --
> >> >
> >> > v2: updated with a recommendation from Rasmus Villemoes to truncate the
> >> > initial precision at just under 32 bits
> >> >
> >> > diff --git a/lib/string_helpers.c b/lib/string_helpers.c
> >> > index 5939f63..363faca 100644
> >> > --- a/lib/string_helpers.c
> >> > +++ b/lib/string_helpers.c
> >> > @@ -43,38 +43,40 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
> >> >  		[STRING_UNITS_10] = 1000,
> >> >  		[STRING_UNITS_2] = 1024,
> >> >  	};
> >> > -	int i, j;
> >> > -	u32 remainder = 0, sf_cap, exp;
> >> > +	static const unsigned int rounding[] = { 500, 50, 5, 0};
> >> 
> >> j necessarily ends up being 0, 1 or 2. Any reason to include the last entry?
> >
> > No reason beyond a vague worry someone might try to increase the printed
> > precision by one digit.
> 
> But that would seem to require prepending 5000 to that array and
> changing various constants below to 10000 (aside from checking all
> callers to see if they pass a sufficient buffer size) - the 0 doesn't
> serve any purpose in that scenario either.
> 
> >> > +
> >> > +	while (blk_size >= UINT_MAX)
> >> >  		i++;
> >> > -	}
> >> >  
> >> > -	exp = divisor[units] / (u32)blk_size;
> >> > -	/*
> >> > -	 * size must be strictly greater than exp here to ensure that remainder
> >> > -	 * is greater than divisor[units] coming out of the if below.
> >> > -	 */
> >> > -	if (size > exp) {
> >> > -		remainder = do_div(size, divisor[units]);
> >> > -		remainder *= blk_size;
> >> > +	while (size >= UINT_MAX)
> >> >  		i++;
> >> 
> >> Please spell it U32_MAX
> >
> > Why?  there's no reason not to use the arithmetic UINT_MAX here.  Either
> > works, of course but UINT_MAX is standard.
> 
> We're dealing with explicitly sized integers

An integer is explicitly sized: it's 32 bits.  That's why UINT_MAX is a
universal constant.

>  and the comment even says
> that we're reducing till we fit in 32 bits, so that we can do a
> 32x32->64 multiplication. U32_MAX is the natural name for the
> appropriate constant.
> 
> Also, you could do > U32_MAX instead of >= U32_MAX, but that's unlikely
> to make any difference (well, except it might generate slightly better
> code, since it would allow gcc to just test the upper half for being 0,
> which might be cheaper on some architectures than comparing to a
> literal).

Heh if we're going to be that concerned about the code generation, then
we should just tell gcc exactly how to do it instead of hoping it can
work it out for itself, so

while (blk_size >> 32) {
...

James

> Rasmus
> --
> To unsubscribe from this list: send the line "unsubscribe linux-scsi" in
> the body of a message to majordomo@...r.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/