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

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

-- 
2.4.3

[PATCH v3 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 v3 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..ee67ada 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[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);
-- 
2.4.3

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

[Rasmus Villemoes]

On Mon, Sep 14 2015, Vitaly Kuznetsov <vkuznets@redhat.com> 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[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.

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

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

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

[Andy Shevchenko]

On Tue, 2015-09-15 at 00:00 +0200, Rasmus Villemoes wrote:
> On Mon, Sep 14 2015, Vitaly Kuznetsov <vkuznets@redhat.com> wrote:
> 

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

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

Agree with Rasmus.

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

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

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

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

[Vitaly Kuznetsov]

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

> On Tue, 2015-09-15 at 00:00 +0200, Rasmus Villemoes wrote:
>> On Mon, Sep 14 2015, Vitaly Kuznetsov <vkuznets@redhat.com> wrote:
>> 
>
> Vitaly, thanks for the test cases. My comments below.
>
>> > +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.
>
> Agree with Rasmus.
>
> And just to make a side note that useless use of min() since we have
> strnlen() :-)
>
>> 
>> > +	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.]
>> 
>> > +	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.

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.

-- 
  Vitaly

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

[Andy Shevchenko]

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

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.

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