| 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
| ||
|
Message-ID: <87fv0wyah4.fsf@vitty.brq.redhat.com>
Date: Tue, 27 Oct 2015 09:36:07 +0100
From: Vitaly Kuznetsov <vkuznets@...hat.com>
To: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Cc: Andrew Morton <akpm@...ux-foundation.org>,
Rasmus Villemoes <linux@...musvillemoes.dk>,
Ulf Hansson <ulf.hansson@...aro.org>,
James Bottomley <JBottomley@...n.com>,
Kees Cook <keescook@...omium.org>, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get_size()
Andy Shevchenko <andriy.shevchenko@...ux.intel.com> 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 <linux@...musvillemoes.dk>
>> Signed-off-by: Vitaly Kuznetsov <vkuznets@...hat.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.
>
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
--
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/
Powered by blists - more mailing lists