lkml.org 
[lkml]   [2015]   [Oct]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get_size()
Date
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


\
 
 \ /
  Last update: 2015-10-27 10:01    [W:0.060 / U:0.360 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site