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

[Vitaly Kuznetsov <vkuznets@redhat.com>]

Andy Shevchenko <andriy.shevchenko@linux.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@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.
>

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