Skip to contentSkip to conversation

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

PATCH Superseded Vitaly Kuznetsov 3 participants 7 messages Sep 15, 2015 – Sep 16, 2015

Subsystems (2)

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

v4 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 v3:
- NULL termination fixes in PATCH 2/2 [Rasmus Villemoes, Andy Shevchenko]

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 | 27 +++++++++++++++++++++++++++
 2 files changed, 32 insertions(+), 1 deletion(-)
Signature · 1 line
2.4.3
#1 lore raw

PATCH v4 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 v4 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 | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
lib/test-string_helpers.c +27 -0
index 8e376ef..b00fc0a 100644
@@ -326,6 +326,30 @@ out:
 	kfree(out_test);
 }
 
+static __init void test_string_get_size_one(u64 size, u64 blk_size,
+					    const enum string_size_units units,
+					    const char *exp_result)
+{
+	char buf[16];
+
+	string_get_size(size, blk_size, units, buf, sizeof(buf));
+	if (!memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf) - 1) + 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 +368,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 v4 2/2] lib/test-string_helpers.c: add string_get_size() tests

Quoted 5 lines · 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.

Minor comments to address, otherwise

Reviewed-by:
Andy Shevchenko <[email protected]>

Quoted 13 lines
---
 lib/test-string_helpers.c | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
lib/test-string_helpers.c +0 -0
index 8e376ef..b00fc0a 100644
@@ -326,6 +326,30 @@ out:
 	kfree(out_test);
 }
 

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

Quoted 10 lines
lib/test-string_helpers.c +8 -1
+static __init void test_string_get_size_one(u64 size, u64 blk_size,
+					    const enum 
 string_size_units units,
+					    const char *exp_result)
+{
+	char buf[16];
+
+	string_get_size(size, blk_size, units, buf, sizeof(buf));
+	if (!memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf) 
- 1) + 1))

Actually you don't need to do this +- 1. Either you will have '\0' or not, it will be checked by memcmp() anyway.

Thus,
memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf))).

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

Quoted 2 lines
lib/test-string_helpers.c +2 -0
+		return;
+

Perhaps one line comment here
/* Make sure that buf will be always NULL-terminated */

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

Quoted 8 lines
lib/test-string_helpers.c +3 -0
+	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",

lib/test-string_helpers.c +2 -0
+		size, blk_size, units);
+	pr_warn("expected: %s, got %s\n", exp_result, buf);

Here I recommend to use single quotes (just to see empty strings)

…expected '%s', got '%s'…

Quoted 25 lines
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");

lib/test-string_helpers.c +1 -0
+	test_string_get_size_one(8192, 4096, STRING_UNITS_10, "32.7 

MB");

lib/test-string_helpers.c +6 -0
+	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 +368,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 · 2 lines
Andy Shevchenko <[email protected]>
Intel Finland Oy
#4 lore raw

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

Quoted 15 lines · Andy Shevchenko

lib/test-string_helpers.c out:

Quoted 10 lines · Vitaly Kuznetsov
(quoted diff) +2 -0
+static __init void test_string_get_size_one(u64 size, u64 blk_size,
+					    const enum 

string_size_units units,

lib/test-string_helpers.c +6 -1
+					    const char *exp_result)
+{
+	char buf[16];
+
+	string_get_size(size, blk_size, units, buf, sizeof(buf));
+	if (!memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf) 
- 1) + 1))

Actually you don't need to do this +- 1. Either you will have '\0' or not, it will be checked by memcmp() anyway.

Quoted 2 lines

Thus,
memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf))).

Huh? How does that ensure that string_get_size put a '\0' at the right spot? We do need the comparison to also cover the terminating '\0' in exp_result.

[It would be nice if we could assert at compile-time that strlen(exp_result) < sizeof(buf).]

Quoted 4 lines

Perhaps one line comment here
/* Make sure that buf will be always NULL-terminated */

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

Quoted 1 line
lib/test-string_helpers.c +1 -0
+	buf[sizeof(buf) - 1] = '\0';

<bikeshed>Could we pretty-please use different names for 0 the pointer and 0 the character, say in this case nul or NUL or '\0' or simply
0. Also, I don't see the value of the comment; that line is a totally standard idiom.</bikeshed>.

Quoted 5 lines

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

Quoted 1 line
lib/test-string_helpers.c +1 -0
+	pr_warn("expected: %s, got %s\n", exp_result, buf);

Here I recommend to use single quotes (just to see empty strings)

…expected '%s', got '%s'…

Good idea.

#5 lore raw

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

Quoted 23 lines · Rasmus Villemoes
Quoted 20 lines · Andy Shevchenko
Quoted 12 lines · Vitaly Kuznetsov

+static __init void test_string_get_size_one(u64 size, u64 blk_size,

(quoted diff) +1 -0
+					    const enum 

string_size_units units,

(quoted diff) +1 -0
+					    const char 

*exp_result)

lib/test-string_helpers.c +4 -0
+{
+	char buf[16];
+
+	string_get_size(size, blk_size, units, buf, 

sizeof(buf));

(quoted diff) +1 -0
+	if (!memcmp(buf, exp_result, strnlen(exp_result, 
Quoted 2 lines

sizeof(buf)
- 1) + 1))

Actually you don't need to do this +- 1. Either you will have '\0' or
not, it will be checked by memcmp() anyway.

Quoted 7 lines
Quoted 2 lines

Thus,
memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf))).

Huh? How does that ensure that string_get_size put a '\0' at the right
spot? We do need the comparison to also cover the terminating '\0' in exp_result.

Ah, you are right.

But seems we have length of the exp_result always smaller than buffer size, so, would we change this to
memcmp(…, strlen(exp_result) + 1);
?

Quoted 2 lines

[It would be nice if we could assert at compile-time that strlen(exp_result) < sizeof(buf).]

Interesting if BUILD_BUG_ON can help here. Can we use sizeof(exp_result) since all of them are literal constants?

Quoted 11 lines
Quoted 5 lines

Perhaps one line comment here
/* Make sure that buf will be always NULL-terminated */

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

Quoted 1 line
lib/test-string_helpers.c +1 -0
+	buf[sizeof(buf) - 1] = '\0';

<bikeshed>Could we pretty-please use different names for 0 the pointer
and 0 the character, say in this case nul or NUL or '\0' or simply
0. Also, I don't see the value of the comment; that line is a totally standard idiom.</bikeshed>.

Got your point.

Signature · 2 lines
Andy Shevchenko <[email protected]>
Intel Finland Oy
#6 lore raw

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

Quoted 39 lines · Andy Shevchenko
Quoted 23 lines · Rasmus Villemoes
Quoted 20 lines · Andy Shevchenko
Quoted 12 lines · Vitaly Kuznetsov

+static __init void test_string_get_size_one(u64 size, u64 blk_size,

(quoted diff) +1 -0
+					    const enum 

string_size_units units,

(quoted diff) +1 -0
+					    const char 

*exp_result)

lib/test-string_helpers.c +4 -0
+{
+	char buf[16];
+
+	string_get_size(size, blk_size, units, buf, 

sizeof(buf));

(quoted diff) +1 -0
+	if (!memcmp(buf, exp_result, strnlen(exp_result, 
Quoted 2 lines

sizeof(buf)
- 1) + 1))

Actually you don't need to do this +- 1. Either you will have '\0' or
not, it will be checked by memcmp() anyway.

Quoted 7 lines
Quoted 2 lines

Thus,
memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf))).

Huh? How does that ensure that string_get_size put a '\0' at the right
spot? We do need the comparison to also cover the terminating '\0' in exp_result.

Ah, you are right.

But seems we have length of the exp_result always smaller than buffer size, so, would we change this to
memcmp(…, strlen(exp_result) + 1);
?

Quoted 6 lines
Quoted 2 lines

[It would be nice if we could assert at compile-time that strlen(exp_result) < sizeof(buf).]

Interesting if BUILD_BUG_ON can help here. Can we use sizeof(exp_result) since all of them are literal constants?

Yes it can. The following seems to be working for me:

+#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(u64 size, 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);
+}

Quoted 12 lines
Quoted 11 lines
Quoted 5 lines

Perhaps one line comment here
/* Make sure that buf will be always NULL-terminated */

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

Quoted 1 line
lib/test-string_helpers.c +1 -0
+	buf[sizeof(buf) - 1] = '\0';

<bikeshed>Could we pretty-please use different names for 0 the pointer
and 0 the character, say in this case nul or NUL or '\0' or simply
0. Also, I don't see the value of the comment; that line is a totally standard idiom.</bikeshed>.

Quoted 1 line

Got your point.

I also wanted to avoid the comment as it is self-explanatory.

Signature · 1 line
  Vitaly