linux-kernel - [PATCH 2/3] lib/string_helpers.c: don't lose precision in string_get

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 26 Oct 2015 14:55:19 +0100
From:	Vitaly Kuznetsov <vkuznets@...hat.com>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
	Ulf Hansson <ulf.hansson@...aro.org>,
	James Bottomley <JBottomley@...n.com>,
	Kees Cook <keescook@...omium.org>, linux-kernel@...r.kernel.org
Subject: [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@...musvillemoes.dk>
Signed-off-by: Vitaly Kuznetsov <vkuznets@...hat.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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/