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 14, 2015 – Sep 15, 2015

Subsystems (2)

v3 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

v3 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 v2:
- Add a comment explaining the fix to string_get_size() [James Bottomley]
- Add string_get_size() tests [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 v3 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 v3 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..ee67ada 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[256];
+
+	string_get_size(size, blk_size, units, buf, sizeof(buf));
+	if (!strncmp(buf, exp_result, min(sizeof(buf), strlen(exp_result))))
+		return;
+
+	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 v3 2/2] lib/test-string_helpers.c: add string_get_size() tests

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

Quoted 9 lines · Vitaly Kuznetsov
lib/test-string_helpers.c +9 -0
+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[256];
+
+	string_get_size(size, blk_size, units, buf, sizeof(buf));
+	if (!strncmp(buf, exp_result, min(sizeof(buf), strlen(exp_result))))
+		return;

Nits: It probably makes sense to also test that string_get_size '\0'-terminates the buffer, so I'd spell this

if (!memcmp(buf, exp_result, min(sizeof(buf), strlen(exp_result)+1)))

With a generous stack buffer, that min() will always evaluate to the strlen(exp_result)+1. On that note: Maybe 256 is a bit excessive. I don't think this will run very deep in the kernel stack, but the code might get copy-pasted somewhere else. 16 should be plenty.

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

Quoted 3 lines
lib/test-string_helpers.c +3 -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);

[There's probably no pretty way of getting from units to a text representation, but it's slightly annoying to have to check the source for the enum definition to figure out what units=0 or units=1 means.]

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

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

In case we failed to '\0'-terminate buf, we might want to print it with "%.*s", (int)sizeof(buf), buf. But maybe I'm just overly paranoid.

Rasmus

#4 lore raw

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

Quoted 2 lines · Rasmus Villemoes

On Mon, Sep 14 2015, Vitaly Kuznetsov <[email protected]> wrote:

Vitaly, thanks for the test cases. My comments below.

Quoted 17 lines

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

Quoted 13 lines

+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 +5 -0
+{
+	char buf[256];
+
+	string_get_size(size, blk_size, units, buf, sizeof(buf));
+	if (!strncmp(buf, exp_result, min(sizeof(buf), 

strlen(exp_result))))

lib/test-string_helpers.c +1 -0
+		return;

Nits: It probably makes sense to also test that string_get_size '\0'-terminates the buffer, so I'd spell this

Quoted 8 lines

if (!memcmp(buf, exp_result, min(sizeof(buf),
strlen(exp_result)+1)))

With a generous stack buffer, that min() will always evaluate to the strlen(exp_result)+1. On that note: Maybe 256 is a bit excessive. I don't think this will run very deep in the kernel stack, but the code might
get copy-pasted somewhere else. 16 should be plenty.

Agree with Rasmus.

And just to make a side note that useless use of min() since we have strnlen() :-)

Quoted 11 lines

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

Quoted 5 lines
(quoted diff) +2 -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 +1 -0
+		size, blk_size, units);

[There's probably no pretty way of getting from units to a text representation, but it's slightly annoying to have to check the source
for the enum definition to figure out what units=0 or units=1 means.]

Quoted 5 lines

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

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

In case we failed to '\0'-terminate buf, we might want to print it with
"%.*s", (int)sizeof(buf), buf. But maybe I'm just overly paranoid.

I prefer to put '\0' at the position after we expected have an actual '\0'. In this case we always be NULL terminated. I did this for hexdump test cases.

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

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

Quoted 54 lines · Andy Shevchenko
Quoted 2 lines · Rasmus Villemoes

On Mon, Sep 14 2015, Vitaly Kuznetsov <[email protected]> wrote:

Vitaly, thanks for the test cases. My comments below.

Quoted 17 lines

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

Quoted 13 lines

+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 +5 -0
+{
+	char buf[256];
+
+	string_get_size(size, blk_size, units, buf, sizeof(buf));
+	if (!strncmp(buf, exp_result, min(sizeof(buf), 

strlen(exp_result))))

lib/test-string_helpers.c +1 -0
+		return;

Nits: It probably makes sense to also test that string_get_size '\0'-terminates the buffer, so I'd spell this

Quoted 8 lines

if (!memcmp(buf, exp_result, min(sizeof(buf),
strlen(exp_result)+1)))

With a generous stack buffer, that min() will always evaluate to the strlen(exp_result)+1. On that note: Maybe 256 is a bit excessive. I don't think this will run very deep in the kernel stack, but the code might
get copy-pasted somewhere else. 16 should be plenty.

Agree with Rasmus.

And just to make a side note that useless use of min() since we have strnlen() :-)

Quoted 11 lines

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

Quoted 5 lines
(quoted diff) +2 -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 +1 -0
+		size, blk_size, units);

[There's probably no pretty way of getting from units to a text representation, but it's slightly annoying to have to check the source
for the enum definition to figure out what units=0 or units=1 means.]

Quoted 5 lines

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

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

In case we failed to '\0'-terminate buf, we might want to print it with
"%.*s", (int)sizeof(buf), buf. But maybe I'm just overly paranoid.

Quoted 3 lines

I prefer to put '\0' at the position after we expected have an actual '\0'. In this case we always be NULL terminated. I did this for hexdump test cases.

Just to check I got your suggestions right:

...
+ if (!memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf) - 1) + 1))
+ return;
+
+ /* NULL terminate buf right after the expected '\0' */
+ buf[strnlen(exp_result, sizeof(buf) - 2) + 1] = '\0';
...

Alternatively, we could have avoided strnlen() by asserting strlen(exp_result) < sizeof(buf) - 1 at the very beginning.

Signature · 1 line
  Vitaly
#6 lore raw

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

Quoted 19 lines · Vitaly Kuznetsov
Quoted 5 lines · Andy Shevchenko

I prefer to put '\0' at the position after we expected have an actual
'\0'. In this case we always be NULL terminated. I did this for hexdump
test cases.

Just to check I got your suggestions right:

...

(quoted diff) +5 -1
+       if (!memcmp(buf, exp_result, strnlen(exp_result, sizeof(buf) 
- 1) + 1))
+               return;
+
+       /* NULL terminate buf right after the expected '\0' */
+       buf[strnlen(exp_result, sizeof(buf) - 2) + 1] = '\0';
...
Quoted 3 lines

Alternatively, we could have avoided strnlen() by asserting strlen(exp_result) < sizeof(buf) - 1 at the very beginning.

Just

buf[sizeof(buf) - 1] = '\0';

should be enough after you called the string_get_size().

And minimize the buffer to something like 16 (whatever is the biggest possible length + '\0' + some space for the wrong algorithm aligned to let's say 4.

Signature · 2 lines
Andy Shevchenko <[email protected]>
Intel Finland Oy