lkml.org 
[lkml]   [2015]   [Oct]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get_size()
From
Date
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 <linux@rasmusvillemoes.dk>
> Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
> ---
>  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.

>   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);
>  }

--
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy



\
 
 \ /
  Last update: 2015-10-26 17:21    [W:0.084 / U:0.420 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site