[PATCH v5 0/2] lib/string_helpers.c: fix infinite loop in string_get_size()

[PATCH v5 0/2] lib/string_helpers.c: fix infinite loop in string_get_size()

[Vitaly Kuznetsov]

This patch series prevents string_get_size() from entering an infinite loop
on some inputs and adds several basic tests for string_get_size() including
one to test for the issue.

Changes since v4:
- Signle quotes in pr_warn() to see empty strings [Andy Shevchenko].
- Check for test validity compile-time [Rasmus Villemoes, Andy Shevchenko].
- All __test_string_get_size() arguments are const.

Vitaly Kuznetsov (2):
  lib/string_helpers.c: fix infinite loop in string_get_size()
  lib/test-string_helpers.c: add string_get_size() tests

 lib/string_helpers.c      |  6 +++++-
 lib/test-string_helpers.c | 36 ++++++++++++++++++++++++++++++++++++
 2 files changed, 41 insertions(+), 1 deletion(-)

-- 
2.4.3

[PATCH v5 1/2] lib/string_helpers.c: fix infinite loop in string_get_size()

[Vitaly Kuznetsov]

Some string_get_size() calls (e.g.:
 string_get_size(1, 512, STRING_UNITS_10, ..., ...)
 string_get_size(15, 64, STRING_UNITS_10, ..., ...)
) result in an infinite loop. The problem is that if size is equal to
divisor[units]/blk_size and is smaller than divisor[units] we'll end
up with size == 0 when we start doing sf_cap calculations:

For string_get_size(1, 512, STRING_UNITS_10, ..., ...) case:
   ...
   remainder = do_div(size, divisor[units]); -> size is 0, remainder is 1
   remainder *= blk_size; -> remainder is 512
   ...
   size *= blk_size; -> size is still 0
   size += remainder / divisor[units]; -> size is still 0

The caller causing the issue is sd_read_capacity(), the problem was noticed
on Hyper-V, such weird size was reported by host when scanning collides
with device removal. This is probably a separate issue worth fixing, this
patch is intended to prevent the library routine from infinite looping.

Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
Acked-by: James Bottomley <JBottomley@Odin.com>
---
 lib/string_helpers.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/lib/string_helpers.c b/lib/string_helpers.c
index c98ae81..bbf1bef 100644
--- a/lib/string_helpers.c
+++ b/lib/string_helpers.c
@@ -59,7 +59,11 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 	}
 
 	exp = divisor[units] / (u32)blk_size;
-	if (size >= exp) {
+	/*
+	 * size must be strictly greater than exp here to ensure that remainder
+	 * is greater than divisor[units] coming out of the if below.
+	 */
+	if (size > exp) {
 		remainder = do_div(size, divisor[units]);
 		remainder *= blk_size;
 		i++;
-- 
2.4.3

[PATCH v5 2/2] lib/test-string_helpers.c: add string_get_size() tests

[Vitaly Kuznetsov]

Add a couple of simple tests for string_get_size(). The last one will hang
the kernel without the 'lib/string_helpers.c: fix infinite loop in
string_get_size()' fix.

Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
---
 lib/test-string_helpers.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/lib/test-string_helpers.c b/lib/test-string_helpers.c
index 8e376ef..98866a7 100644
--- a/lib/test-string_helpers.c
+++ b/lib/test-string_helpers.c
@@ -326,6 +326,39 @@ out:
 	kfree(out_test);
 }
 
+#define string_get_size_maxbuf 16
+#define test_string_get_size_one(size, blk_size, units, exp_result)            \
+	do {                                                                   \
+		BUILD_BUG_ON(sizeof(exp_result) >= string_get_size_maxbuf);    \
+		__test_string_get_size((size), (blk_size), (units),            \
+				       (exp_result));                          \
+	} while (0)
+
+
+static __init void __test_string_get_size(const u64 size, const u64 blk_size,
+					  const enum string_size_units units,
+					  const char *exp_result)
+{
+	char buf[string_get_size_maxbuf];
+
+	string_get_size(size, blk_size, units, buf, sizeof(buf));
+	if (!memcmp(buf, exp_result, strlen(exp_result) + 1))
+		return;
+
+	buf[sizeof(buf) - 1] = '\0';
+	pr_warn("Test 'test_string_get_size_one' failed!\n");
+	pr_warn("string_get_size(size = %llu, blk_size = %llu, units = %d\n",
+		size, blk_size, units);
+	pr_warn("expected: '%s', got '%s'\n", exp_result, buf);
+}
+
+static __init void test_string_get_size(void)
+{
+	test_string_get_size_one(16384, 512, STRING_UNITS_2, "8.00 MiB");
+	test_string_get_size_one(8192, 4096, STRING_UNITS_10, "32.7 MB");
+	test_string_get_size_one(1, 512, STRING_UNITS_10, "512 B");
+}
+
 static int __init test_string_helpers_init(void)
 {
 	unsigned int i;
@@ -344,6 +377,9 @@ static int __init test_string_helpers_init(void)
 	for (i = 0; i < (ESCAPE_ANY_NP | ESCAPE_HEX) + 1; i++)
 		test_string_escape("escape 1", escape1, i, TEST_STRING_2_DICT_1);
 
+	/* Test string_get_size() */
+	test_string_get_size();
+
 	return -EINVAL;
 }
 module_init(test_string_helpers_init);
-- 
2.4.3

Re: [PATCH v5 2/2] lib/test-string_helpers.c: add string_get_size() tests

[Rasmus Villemoes]

On Thu, Sep 17 2015, Vitaly Kuznetsov <vkuznets@redhat.com> wrote:

> +
> +static __init void test_string_get_size(void)
> +{
> +	test_string_get_size_one(16384, 512, STRING_UNITS_2, "8.00 MiB");
> +	test_string_get_size_one(8192, 4096, STRING_UNITS_10, "32.7 MB");

This is a little late, but I just noticed that string_get_size with
STRING_UNITS_10, block size >= 1024 and sufficiently large size seems to
be broken. Yes, 32.7 MB is what it produces, but is it what it should
give? 8192*4096 = 33554432, so I'd expect "33.5 MB". It does give that
when we pass size=65536 and block_size=512; a combination with the same
product.

I think the problem is that the remainder coming out of the while
(blk_size >= divisor[units]) loop is dropped on the floor in the
subsequent size > exp case - but I'm too lazy right now to figure out how
to fix it.

Rasmus

Re: [PATCH v5 2/2] lib/test-string_helpers.c: add string_get_size() tests

[Vitaly Kuznetsov]

Rasmus Villemoes <linux@rasmusvillemoes.dk> writes:

> On Thu, Sep 17 2015, Vitaly Kuznetsov <vkuznets@redhat.com> wrote:
>
>> +
>> +static __init void test_string_get_size(void)
>> +{
>> +	test_string_get_size_one(16384, 512, STRING_UNITS_2, "8.00 MiB");
>> +	test_string_get_size_one(8192, 4096, STRING_UNITS_10, "32.7 MB");
>
> This is a little late,

Thanks for the ping, it turns out this patch was never merged (though
the one fixing the issue was), I'll have to resend.

> but I just noticed that string_get_size with
> STRING_UNITS_10, block size >= 1024 and sufficiently large size seems to
> be broken. Yes, 32.7 MB is what it produces, but is it what it should
> give? 8192*4096 = 33554432, so I'd expect "33.5 MB". It does give that
> when we pass size=65536 and block_size=512; a combination with the same
> product.
>
> I think the problem is that the remainder coming out of the while
> (blk_size >= divisor[units]) loop is dropped on the floor in the
> subsequent size > exp case - but I'm too lazy right now to figure out how
> to fix it.

Ok, I'll take a look.

-- 
  Vitaly