linux-kernel - Re: [PATCH v3 3/4] lib/string_helpers.c: don't lose precision in string_get

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAHp75VcydcgrwPeUY1=Mv_417x1ysL-DAWOYUfpRG7uavYGNig@mail.gmail.com>
Date:	Thu, 29 Oct 2015 23:22:50 +0200
From:	Andy Shevchenko <andy.shevchenko@...il.com>
To:	Vitaly Kuznetsov <vkuznets@...hat.com>
Cc:	Andrew Morton <akpm@...ux-foundation.org>,
	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
	Ulf Hansson <ulf.hansson@...aro.org>,
	James Bottomley <JBottomley@...n.com>,
	Kees Cook <keescook@...omium.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH v3 3/4] lib/string_helpers.c: don't lose precision in string_get_size()

On Thu, Oct 29, 2015 at 6:30 PM, Vitaly Kuznetsov <vkuznets@...hat.com> 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@...musvillemoes.dk>
> Signed-off-by: Vitaly Kuznetsov <vkuznets@...hat.com>

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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/