Re: [PATCH v3 3/4] lib/string_helpers.c: don't lose precision in string_get_size()

[Andy Shevchenko]

On Thu, Oct 29, 2015 at 6:30 PM, Vitaly Kuznetsov <vkuznets@xxxxxxxxxx> 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 < U64_MAX / blk_size.
> 2) Multiply the result by blk_size and do final calculations.
>
> Suggested-by: Rasmus Villemoes <linux@xxxxxxxxxxxxxxxxxx>
> Signed-off-by: Vitaly Kuznetsov <vkuznets@xxxxxxxxxx>

One nitpick below.

>         /*
> -        * 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
> +        * U64_MAX / blk_size.
>          */
> -       if (size > exp) {
> -               remainder = do_div(size, divisor[units]);
> -               remainder *= blk_size;
> -               i++;
> -       } else {
> -               remainder *= size;
> +       while (size > div_u64(U64_MAX, blk_size)) {
> +               /*
> +                * We do not need to keep the remainder as blk_size is capped
> +                * by U32_MAX and we'll still have enough precision after the
> +                * loop.
> +                */
> +               do_div(size, divisor[units]);

> +               ++i;

You may leave i++; here. Any reason not to do that?

>         }


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