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

[Vitaly Kuznetsov]

Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx> 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@xxxxxxxxxxxxxxxxxx>
>> Signed-off-by: Vitaly Kuznetsov <vkuznets@xxxxxxxxxx>
>> ---
>> Â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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/