From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S965985AbbJ0VC5 (ORCPT ); Tue, 27 Oct 2015 17:02:57 -0400 Received: from mail-wi0-f175.google.com ([209.85.212.175]:37630 "EHLO mail-wi0-f175.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S965634AbbJ0VCw (ORCPT ); Tue, 27 Oct 2015 17:02:52 -0400 From: Rasmus Villemoes To: Vitaly Kuznetsov Cc: Andrew Morton , Andy Shevchenko , Ulf Hansson , James Bottomley , Kees Cook , linux-kernel@vger.kernel.org Subject: Re: [PATCH v2 2/3] lib/string_helpers.c: don't lose precision in string_get_size() Organization: D03 References: <1445954787-18104-1-git-send-email-vkuznets@redhat.com> <1445954787-18104-3-git-send-email-vkuznets@redhat.com> X-Hashcash: 1:20:151027:vkuznets@redhat.com::wEt/kUJgjcPchkJ6:0000000000000000000000000000000000000000000oDu X-Hashcash: 1:20:151027:akpm@linux-foundation.org::M32m8X+BbMBAODGQ:0000000000000000000000000000000000001eOD X-Hashcash: 1:20:151027:andriy.shevchenko@linux.intel.com::n5DIeoV5qWO7Z1gj:00000000000000000000000000003Kl7 X-Hashcash: 1:20:151027:ulf.hansson@linaro.org::QYzc6qXi3m2sPaUn:0000000000000000000000000000000000000006OLl X-Hashcash: 1:20:151027:linux-kernel@vger.kernel.org::RCLlYrsN4i3LOlO7:000000000000000000000000000000000B9tO X-Hashcash: 1:20:151027:jbottomley@odin.com::pTMRukfJoYlGSsdc:000000000000000000000000000000000000000000AXxP X-Hashcash: 1:20:151027:keescook@chromium.org::IjbR2HGF3kf4N9oz:0000000000000000000000000000000000000000FKxF Date: Tue, 27 Oct 2015 22:02:49 +0100 In-Reply-To: <1445954787-18104-3-git-send-email-vkuznets@redhat.com> (Vitaly Kuznetsov's message of "Tue, 27 Oct 2015 15:06:26 +0100") Message-ID: <87twpcvxc6.fsf@rasmusvillemoes.dk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Oct 27 2015, Vitaly Kuznetsov wrote: > string_get_size() loses precision when there is a remainder for > blk_size / divisor[units] and size is big enough. E.g > string_get_size(8192, 4096, STRING_UNITS_10, ...) returns "32.7 MB" > while it is supposed to return "33.5 MB". For some artificial inputs > the result can be ridiculously wrong, e.g. > string_get_size(3000, 1900, STRING_UNITS_10, ...) returns "3.00 MB" > when "5.70 MB" is expected. > > The issues comes from the fact than we through away > blk_size / divisor[units] remainder when size is > exp. This can be fixed > by saving it and doing some non-trivial calculations later to fix the error > but that would make this function even more cumbersome. Slightly re-factor > the function to not lose the precision for all inputs. > > The overall complexity of this function comes from the fact that size can > be huge and we don't want to do size * blk_size as it can overflow. Do the > math in two steps: > 1) Reduce size to something < blk_size * divisor[units] > 2) Multiply the result (and the remainder) by blk_size and do final > calculations. > > Reported-by: Rasmus Villemoes > Signed-off-by: Vitaly Kuznetsov > --- > Changes since v1: > - Check against blk_size == 0 [Rasmus Villemoes] > - Do not rename 'i' to 'order' [Andy Shevchenko] > --- > lib/string_helpers.c | 37 ++++++++++++++++++++++++------------- > 1 file changed, 24 insertions(+), 13 deletions(-) > > diff --git a/lib/string_helpers.c b/lib/string_helpers.c > index f6c27dc..eba8e82 100644 > --- a/lib/string_helpers.c > +++ b/lib/string_helpers.c > @@ -44,7 +44,8 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units, > [STRING_UNITS_2] = 1024, > }; > int i, j; > - u32 remainder = 0, sf_cap, exp; > + u64 remainder = 0; > + u32 sf_cap; > char tmp[8]; > const char *unit; > > @@ -53,28 +54,36 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units, > if (!size) > goto out; > > - while (blk_size >= divisor[units]) { > - remainder = do_div(blk_size, divisor[units]); > - i++; > + if (!blk_size) { > + WARN_ON(1); > + size = 0; > + goto out; > } I don't think we need to handle that, but if you want, please put the WARN inside the conditional (so say "if (WARN_ON(!blk_size)) {...}". And don't make it _ONCE; the ordinary version is slightly cheaper (since there's no static bool __warned and no code to manage that). > > - exp = divisor[units] / 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. > + * size can be huge and doing size * blk_size right away can overflow. > + * As a first step reduce huge size to something less than > + * blk_size * divisor[units]. > */ > - if (size > exp) { > + while (size > (u64)blk_size * divisor[units]) { It seems weird that we reduce _more_ for smaller block sizes - indeed, for blk_size==1 we end up reducing size to <= 1000 (or 1024), which is certainly a good way to lose some precision. Also, this relies on blk_size being smaller than (roughly) sqrt(U64_MAX/divisor[units]), which is of course true in practice, but a slightly annoying implicit assumption. I do think that my approach of reducing size till it's smaller than U64_MAX/blk_size is simpler and better. There's much less fixup code. It's simply while (size > div_u64(U64_MAX, blk_size) { do_div(size, divisor[units]); ++i; } size *= blk_size; while (size > divisor[units]) { remainder = do_div(size, divisor[units]); ++i; } which is as self-explaining as it gets. And yes, one needs to use the include/linux/math64.h functions/macros for u64/u32 divisions - otherwise I'm pretty sure one will get friendly mails from the build bot. while (size > ) > remainder = do_div(size, divisor[units]); > - remainder *= blk_size; > i++; > - } else { > - remainder *= size; > } > > + /* Now we're OK with doing size * blk_size, it won't overflow. */ > size *= blk_size; > + remainder *= blk_size; > + /* > + * We were doing partial multiplication by blk_size. > + * remainder >= divisor[units] here means size should be increased. > + */ > size += remainder / divisor[units]; > - remainder %= divisor[units]; > + remainder -= (remainder / divisor[units]) * divisor[units]; > > + /* > + * Normalize. size >= divisor[units] means we still have enough > + * precision and dropping remainder is fine. > + */ > while (size >= divisor[units]) { > remainder = do_div(size, divisor[units]); > i++; > @@ -87,7 +96,8 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units, > if (j) { > remainder *= 1000; > remainder /= divisor[units]; > - snprintf(tmp, sizeof(tmp), ".%03u", remainder); > + /* remainder is < divisor[units] here, (u32) is legit */ What is actually important is that remainder is < 1000. remainder was initially < divisor[units], but then the multiplication and division transformed that into "1/1000s" of whatever unit we're using. > + snprintf(tmp, sizeof(tmp), ".%03u", (u32)remainder); > tmp[j+1] = '\0'; > } > > @@ -97,6 +107,7 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units, > else > unit = units_str[units][i]; > > + /* size is < divisor[units] here, (u32) is legit */ > snprintf(buf, len, "%u%s %s", (u32)size, > tmp, unit); > }