From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S964870AbbJ0PZo (ORCPT ); Tue, 27 Oct 2015 11:25:44 -0400 Received: from mga03.intel.com ([134.134.136.65]:45049 "EHLO mga03.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932274AbbJ0PZm (ORCPT ); Tue, 27 Oct 2015 11:25:42 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.20,205,1444719600"; d="scan'208";a="804430158" Message-ID: <1445959501.6332.33.camel@linux.intel.com> Subject: Re: [PATCH v2 2/3] lib/string_helpers.c: don't lose precision in string_get_size() From: Andy Shevchenko To: Vitaly Kuznetsov , Andrew Morton Cc: Rasmus Villemoes , Ulf Hansson , James Bottomley , Kees Cook , linux-kernel@vger.kernel.org Date: Tue, 27 Oct 2015 17:25:01 +0200 In-Reply-To: <1445954787-18104-3-git-send-email-vkuznets@redhat.com> References: <1445954787-18104-1-git-send-email-vkuznets@redhat.com> <1445954787-18104-3-git-send-email-vkuznets@redhat.com> Organization: Intel Finland Oy Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.18.1-1 Mime-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, 2015-10-27 at 15:06 +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 > --- > 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); Hmm... Isn't it too strong? WARN_ONCE() might reduce a noise. Or even pr_warn_once/ratelimited(). > + size = 0; > + goto out; >   } What about doing it before if (!size) ? Like  if (!blk_size) {  pr_warn_once(); /* or WARN_ONCE() ? */  /* Override size to follow error path */  size = 0; }   if (!size) Also, would it be separate patch? >   > - 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; >   } >   > + /* 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]; I'm sorry I didn't get what the purpose of change here. (Yes, I was thinking about u64 on 32-bit architecture, but % and / are working in the similar way aren't they?) >   > + /* > +  * 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 */ > + 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); >  } -- Andy Shevchenko Intel Finland Oy