From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752728AbbJ0IgQ (ORCPT ); Tue, 27 Oct 2015 04:36:16 -0400 Received: from mx1.redhat.com ([209.132.183.28]:59792 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750763AbbJ0IgM (ORCPT ); Tue, 27 Oct 2015 04:36:12 -0400 From: Vitaly Kuznetsov To: Andy Shevchenko Cc: Andrew Morton , Rasmus Villemoes , Ulf Hansson , James Bottomley , Kees Cook , linux-kernel@vger.kernel.org Subject: Re: [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get_size() References: <1445867720-25473-1-git-send-email-vkuznets@redhat.com> <1445867720-25473-3-git-send-email-vkuznets@redhat.com> <1445875739.6332.2.camel@linux.intel.com> Date: Tue, 27 Oct 2015 09:36:07 +0100 In-Reply-To: <1445875739.6332.2.camel@linux.intel.com> (Andy Shevchenko's message of "Mon, 26 Oct 2015 18:08:59 +0200") Message-ID: <87fv0wyah4.fsf@vitty.brq.redhat.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Andy Shevchenko writes: > On Mon, 2015-10-26 at 14:55 +0100, 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 >> --- >>  lib/string_helpers.c | 46 +++++++++++++++++++++++++----------------- >> ---- >>  1 file changed, 25 insertions(+), 21 deletions(-) >> >> diff --git a/lib/string_helpers.c b/lib/string_helpers.c >> index f6c27dc..0658994 100644 >> --- a/lib/string_helpers.c >> +++ b/lib/string_helpers.c >> @@ -43,41 +43,43 @@ void string_get_size(u64 size, u32 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; >> + int order = 0, j; >> + u64 remainder = 0; >> + u32 sf_cap; >>   char tmp[8]; >>   const char *unit; >>   >>   tmp[0] = '\0'; >> - i = 0; > > Maybe leave i naming as is. Your order is not strictly speaking an > order, rather 3x order. I will make patch neater. > While reading the original function I found meaningless 'i' and 'j' here a bit consufing but yes, strictly speaking 'i' is a power of divisor[units], not 'order' and I don't have a good name for it (div_power?). I'll revert back to 'i' in v2. >>   if (!size) >>   goto out; >>   >> - while (blk_size >= divisor[units]) { >> - remainder = do_div(blk_size, divisor[units]); >> - i++; >> - } >> - >> - 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]) { >>   remainder = do_div(size, divisor[units]); >> - remainder *= blk_size; >> - i++; >> - } else { >> - remainder *= size; >> + order++; >>   } >>   >> + /* 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++; >> + order++; >>   } >>   >>   sf_cap = size; >> @@ -87,16 +89,18 @@ 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 */ >> + snprintf(tmp, sizeof(tmp), ".%03u", (u32)remainder); >>   tmp[j+1] = '\0'; >>   } >>   >>   out: >> - if (i >= ARRAY_SIZE(units_2)) >> + if (order >= ARRAY_SIZE(units_2)) >>   unit = "UNK"; >>   else >> - unit = units_str[units][i]; >> + unit = units_str[units][order]; >>   >> + /* size is < divisor[units] here, (u32) is legit */ >>   snprintf(buf, len, "%u%s %s", (u32)size, >>    tmp, unit); >>  } -- Vitaly