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

[PATCH v4 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 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(-)

-- 
2.4.3

[PATCH v4 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 v4 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 | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/lib/test-string_helpers.c b/lib/test-string_helpers.c
index 8e376ef..b00fc0a 100644
--- a/lib/test-string_helpers.c
+++ b/lib/test-string_helpers.c
@@ -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);
-- 
2.4.3

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

[Andy Shevchenko]

On Tue, 2015-09-15 at 15:55 +0200, Vitaly Kuznetsov wrote:
> 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 <andriy.shevchenko@linux.intel.com>

> Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
> ---
>  lib/test-string_helpers.c | 27 +++++++++++++++++++++++++++
>  1 file changed, 27 insertions(+)
> 
> diff --git a/lib/test-string_helpers.c b/lib/test-string_helpers.c
> index 8e376ef..b00fc0a 100644
> --- a/lib/test-string_helpers.c
> +++ b/lib/test-string_helpers.c
> @@ -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))

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))).

> +		return;
> +

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

> +	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);

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

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

> +}
> +
> +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);

-- 
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

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

[Rasmus Villemoes]

On Tue, Sep 15 2015, Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote:

> On Tue, 2015-09-15 at 15:55 +0200, Vitaly Kuznetsov wrote:
>> +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))).

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).]

> Perhaps one line comment here
> /* Make sure that buf will be always NULL-terminated */
>
>> +	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>.

>> +	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.

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

[Andy Shevchenko]

On Wed, 2015-09-16 at 13:21 +0200, Rasmus Villemoes wrote:
> On Tue, Sep 15 2015, Andy Shevchenko <
> andriy.shevchenko@linux.intel.com> wrote:
> 
> > On Tue, 2015-09-15 at 15:55 +0200, Vitaly Kuznetsov wrote:
> > > +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))).
> 
> 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);
?

> [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?

> 
> > Perhaps one line comment here
> > /* Make sure that buf will be always NULL-terminated */
> > 
> > > +	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.

-- 
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

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

[Vitaly Kuznetsov]

Andy Shevchenko <andriy.shevchenko@linux.intel.com> writes:

> On Wed, 2015-09-16 at 13:21 +0200, Rasmus Villemoes wrote:
>> On Tue, Sep 15 2015, Andy Shevchenko <
>> andriy.shevchenko@linux.intel.com> wrote:
>> 
>> > On Tue, 2015-09-15 at 15:55 +0200, Vitaly Kuznetsov wrote:
>> > > +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))).
>> 
>> 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);
> ?
>
>> [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);
+}

>> 
>> > Perhaps one line comment here
>> > /* Make sure that buf will be always NULL-terminated */
>> > 
>> > > +	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.

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

-- 
  Vitaly