Skip to contentSkip to conversation

lib/string_helpers.c: fix infinite loop in string_get_size()

PATCH In review Vitaly Kuznetsov 2 participants 5 messages Sep 17, 2015 – Oct 23, 2015

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

v5 cover lib/string_helpers.c: fix infinite loop in string_get_size()

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(-)
Signature · 1 line
2.4.3
#1 lore raw

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

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.

---
 lib/string_helpers.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
lib/string_helpers.c +5 -1
index c98ae81..bbf1bef 100644
@@ -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++;
Signature · 1 line
2.4.3
#2 lore raw

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

In reply to 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.

---
 lib/test-string_helpers.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
lib/test-string_helpers.c +36 -0
index 8e376ef..98866a7 100644
@@ -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);
Signature · 1 line
2.4.3
#3 lore raw

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

lib/test-string_helpers.c out: · line 358

Quoted 5 lines · Vitaly Kuznetsov
lib/test-string_helpers.c +5 -0
+
+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

#4 lore raw

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

Quoted 9 lines · Rasmus Villemoes

lib/test-string_helpers.c out: · line 358

Quoted 5 lines · Vitaly Kuznetsov
lib/test-string_helpers.c +5 -0
+
+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.

Quoted 11 lines

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.

Signature · 1 line
  Vitaly