Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1255959 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get_size() Vitaly Kuznetsov <vkuznets@redhat.com> - 2015-10-26 15:00 +0100
    Re: [PATCH 2/3] lib/string_helpers.c: don't lose precision in  string_get_size() Andy Shevchenko <andriy.shevchenko@linux.intel.com> - 2015-10-26 17:20 +0100
      Re: [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get_size() Vitaly Kuznetsov <vkuznets@redhat.com> - 2015-10-27 09:40 +0100
        Re: [PATCH 2/3] lib/string_helpers.c: don't lose precision in  string_get_size() Andy Shevchenko <andriy.shevchenko@linux.intel.com> - 2015-10-27 10:40 +0100
    Re: [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get_size() Rasmus Villemoes <linux@rasmusvillemoes.dk> - 2015-10-26 22:50 +0100
      Re: [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get_size() Vitaly Kuznetsov <vkuznets@redhat.com> - 2015-10-27 09:50 +0100

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

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;
 	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);
 }
-- 
2.4.3

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

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

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.

>  	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);
>  }

-- 
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1256572

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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

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

On Tue, 2015-10-27 at 09:36 +0100, Vitaly Kuznetsov wrote:
> 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.

[]

> > > -	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.

I agree that names suck, however it might be better to have separate
patch to fix naming.

Rasmus?

-- 
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1256306

So I also played with this over the weekend, and also threw together a
stupid script to check the output. I see you have more or less the same
idea I used, namely to combine size and blk_size earlier.

I put some code on github, https://github.com/Villemoes/get_size. All
versions still fail a very simply case, size=1594323, blk_size=1, for
which the correct answer is "1.52 MiB", but we get "1.51 MiB". But both
your version and my two attempts seem to have the property that they are
always at most one ULP (unit in the last place) too low, and never too
high. ATM, my version 2 fails 70 of the 13598 test cases, while yours
fail 86 (the former being a strict subset of the latter), so they're
very similar.

Regardless of which algorithm we go with, I have some cleanups I'd like
to do, but they're mostly independent and can wait.

Rasmus

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1256578

Rasmus Villemoes <linux@rasmusvillemoes.dk> writes:

> So I also played with this over the weekend, and also threw together a
> stupid script to check the output. I see you have more or less the same
> idea I used, namely to combine size and blk_size earlier.
>
> I put some code on github, https://github.com/Villemoes/get_size. All
> versions still fail a very simply case, size=1594323, blk_size=1, for
> which the correct answer is "1.52 MiB", but we get "1.51 MiB".

Yes, the algorithm still has minor glitches (e.g. rounding issues) but
I'd say keeping it simple enough here is worth it.

> But both
> your version and my two attempts seem to have the property that they are
> always at most one ULP (unit in the last place) too low, and never too
> high. ATM, my version 2 fails 70 of the 13598 test cases, while yours
> fail 86 (the former being a strict subset of the latter), so they're
> very similar.
>
> Regardless of which algorithm we go with, I have some cleanups I'd like
> to do, but they're mostly independent and can wait.
>
> Rasmus

-- 
  Vitaly
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web