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

Groups > linux.kernel > #1258905 > unrolled thread

[PATCH v3 3/4] 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 v3 3/4] lib/string_helpers.c: don't lose precision in string_get_size() Vitaly Kuznetsov <vkuznets@redhat.com> - 2015-10-29 17:40 +0100
    Re: [PATCH v3 3/4] lib/string_helpers.c: don't lose precision in string_get_size() Andy Shevchenko <andy.shevchenko@gmail.com> - 2015-10-29 22:30 +0100

#1258905 — [PATCH v3 3/4] 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 < U64_MAX / blk_size.
2) Multiply the result by blk_size and do final calculations.

Suggested-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
---
Changes since v2:
- Reduce size to something < U64_MAX / blk_size as a first step instead of
  blk_size * divisor[units], remove fixup code [Rasmus Villemoes]
- Separate !blk_size check into a separate patch [Andy Shevchenko]
---
 lib/string_helpers.c | 31 ++++++++++++++-----------------
 1 file changed, 14 insertions(+), 17 deletions(-)

diff --git a/lib/string_helpers.c b/lib/string_helpers.c
index ff3575b..29263c1 100644
--- a/lib/string_helpers.c
+++ b/lib/string_helpers.c
@@ -44,7 +44,7 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 		[STRING_UNITS_2] = 1024,
 	};
 	int i, j;
-	u32 remainder = 0, sf_cap, exp;
+	u32 remainder = 0, sf_cap;
 	char tmp[8];
 	const char *unit;
 
@@ -58,27 +58,23 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 	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
+	 * U64_MAX / blk_size.
 	 */
-	if (size > exp) {
-		remainder = do_div(size, divisor[units]);
-		remainder *= blk_size;
-		i++;
-	} else {
-		remainder *= size;
+	while (size > div_u64(U64_MAX, blk_size)) {
+		/*
+		 * We do not need to keep the remainder as blk_size is capped
+		 * by U32_MAX and we'll still have enough precision after the
+		 * loop.
+		 */
+		do_div(size, divisor[units]);
+		++i;
 	}
 
+	/* Now we're OK with doing size * blk_size, it won't overflow. */
 	size *= blk_size;
-	size += remainder / divisor[units];
-	remainder %= divisor[units];
 
 	while (size >= divisor[units]) {
 		remainder = do_div(size, divisor[units]);
@@ -102,6 +98,7 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 	else
 		unit = units_str[units][i];
 
+	/* 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]

#1259016

On Thu, Oct 29, 2015 at 6:30 PM, Vitaly Kuznetsov <vkuznets@redhat.com> 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 < U64_MAX / blk_size.
> 2) Multiply the result by blk_size and do final calculations.
>
> Suggested-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>

One nitpick below.

>         /*
> -        * 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
> +        * U64_MAX / blk_size.
>          */
> -       if (size > exp) {
> -               remainder = do_div(size, divisor[units]);
> -               remainder *= blk_size;
> -               i++;
> -       } else {
> -               remainder *= size;
> +       while (size > div_u64(U64_MAX, blk_size)) {
> +               /*
> +                * We do not need to keep the remainder as blk_size is capped
> +                * by U32_MAX and we'll still have enough precision after the
> +                * loop.
> +                */
> +               do_div(size, divisor[units]);

> +               ++i;

You may leave i++; here. Any reason not to do that?

>         }


-- 
With Best Regards,
Andy Shevchenko
--
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