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

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

[Vitaly Kuznetsov]

string_get_size(1, 512, 0, ..., ...) call results in an infinite loop. The
problem is that if size == 0 when we start calculating sf_cap this loop
will never end.

The caller causing the issue is sd_read_capacity(), the problem was noticed
on Hyper-V.

Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
---
 lib/string_helpers.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/string_helpers.c b/lib/string_helpers.c
index c98ae81..a155c7b 100644
--- a/lib/string_helpers.c
+++ b/lib/string_helpers.c
@@ -76,7 +76,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		i++;
 	}
 
-	sf_cap = size;
+	sf_cap = size ? size : 1;
 	for (j = 0; sf_cap*10 < 1000; j++)
 		sf_cap *= 10;
 
-- 
2.4.3

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

[Andrew Morton]

On Fri,  4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <vkuznets@redhat.com> wrote:

> string_get_size(1, 512, 0, ..., ...) call results in an infinite loop. The
> problem is that if size == 0 when we start calculating sf_cap this loop
> will never end.
> 
> The caller causing the issue is sd_read_capacity(), the problem was noticed
> on Hyper-V.

When fixing bugs, please provide enough info for others to be able to
understand which kernel version(s) need the fix.  In this case: what
end-user action triggers this bug?  (iow, how does sdkp->capacity
become zero?)

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

[James Bottomley]

[-- Attachment #1: Type: text/plain, Size: 975 bytes --]

On Thu, 2015-09-10 at 16:08 -0700, Andrew Morton wrote:
> On Fri,  4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <vkuznets@redhat.com> wrote:
> 
> > string_get_size(1, 512, 0, ..., ...) call results in an infinite loop. The
> > problem is that if size == 0 when we start calculating sf_cap this loop
> > will never end.
> > 
> > The caller causing the issue is sd_read_capacity(), the problem was noticed
> > on Hyper-V.
> 
> When fixing bugs, please provide enough info for others to be able to
> understand which kernel version(s) need the fix.  In this case: what
> end-user action triggers this bug?  (iow, how does sdkp->capacity
> become zero?)

Any more details.  The attached programme, which is cut straight out of
the algorithm in string_helpers.c and modified for a C environment
slightly (only in do_div and the typedefs) produces this

hello
STRING IS 512 B

With your input, so I don't think the problem is where you think it is.

James


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: test.c --]
[-- Type: text/x-csrc; name="test.c", Size: 2502 bytes --]

#include <sys/types.h>
#include <string.h>
#include <stdio.h>

# define do_div(n,base) ({					\
	u32 __base = (base);				\
	u32 __rem;						\
	__rem = ((u64)(n)) % __base;			\
	(n) = ((u64)(n)) / __base;				\
	__rem;							\
 })

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))

typedef unsigned long long u64;
typedef unsigned int u32;

enum string_size_units {
  STRING_UNITS_2,
  STRING_UNITS_10,
};

/**
 * string_get_size - get the size in the specified units
 * @size:	The size to be converted in blocks
 * @blk_size:	Size of the block (use 1 for size in bytes)
 * @units:	units to use (powers of 1000 or 1024)
 * @buf:	buffer to format to
 * @len:	length of buffer
 *
 * This function returns a string formatted to 3 significant figures
 * giving the size in the required units.  @buf should have room for
 * at least 9 bytes and will always be zero terminated.
 *
 */
void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
		     char *buf, int len)
{
	static const char *const units_10[] = {
		"B", "kB", "MB", "GB", "TB", "PB", "EB", "ZB", "YB"
	};
	static const char *const units_2[] = {
		"B", "KiB", "MiB", "GiB", "TiB", "PiB", "EiB", "ZiB", "YiB"
	};
	static const char *const *const units_str[] = {
		[STRING_UNITS_10] = units_10,
		[STRING_UNITS_2] = units_2,
	};
	static const unsigned int divisor[] = {
		[STRING_UNITS_10] = 1000,
		[STRING_UNITS_2] = 1024,
	};
	int i, j;
	u32 remainder = 0, sf_cap, exp;
	char tmp[8];
	const char *unit;

	tmp[0] = '\0';
	i = 0;
	if (!size)
		goto out;

	while (blk_size >= divisor[units]) {
		remainder = do_div(blk_size, divisor[units]);
		i++;
	}

	exp = divisor[units] / (u32)blk_size;
	if (size >= exp) {
		remainder = do_div(size, divisor[units]);
		remainder *= blk_size;
		i++;
	} else {
		remainder *= size;
	}

	size *= blk_size;
	size += remainder / divisor[units];
	remainder %= divisor[units];

	while (size >= divisor[units]) {
		remainder = do_div(size, divisor[units]);
		i++;
	}

	sf_cap = size;
	for (j = 0; sf_cap*10 < 1000; j++)
		sf_cap *= 10;

	if (j) {
		remainder *= 1000;
		remainder /= divisor[units];
		snprintf(tmp, sizeof(tmp), ".%03u", remainder);
		tmp[j+1] = '\0';
	}

 out:
	if (i >= ARRAY_SIZE(units_2))
		unit = "UNK";
	else
		unit = units_str[units][i];

	snprintf(buf, len, "%u%s %s", (u32)size,
		 tmp, unit);
}

int main(char *argc[], int argv)
{
char buf[512];

printf("hello\n");
string_get_size(1, 512, STRING_UNITS_2, buf, sizeof(buf));
printf("STRING IS %s\n", buf);

}

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

[Andy Shevchenko]

On Fri, 2015-09-11 at 18:31 +0000, James Bottomley wrote:
> On Thu, 2015-09-10 at 16:08 -0700, Andrew Morton wrote:
> > On Fri,  4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <
> > vkuznets@redhat.com> wrote:
> > 
> > > string_get_size(1, 512, 0, ..., ...) call results in an infinite 
> > > loop. The
> > > problem is that if size == 0 when we start calculating sf_cap 
> > > this loop
> > > will never end.
> > > 
> > > The caller causing the issue is sd_read_capacity(), the problem 
> > > was noticed
> > > on Hyper-V.
> > 
> > When fixing bugs, please provide enough info for others to be able 
> > to
> > understand which kernel version(s) need the fix.  In this case: 
> > what
> > end-user action triggers this bug?  (iow, how does sdkp->capacity
> > become zero?)
> 
> Any more details.  The attached programme, which is cut straight out 
> of
> the algorithm in string_helpers.c and modified for a C environment
> slightly (only in do_div and the typedefs) produces this
> 
> hello
> STRING IS 512 B
> 
> With your input, so I don't think the problem is where you think it 
> is.
> 
> James
> 

Vitaly, it might make sense to extend test-string_helpers.c to what you
are trying to do right.


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

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

[Vitaly Kuznetsov]

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

> On Fri, 2015-09-11 at 18:31 +0000, James Bottomley wrote:
>> On Thu, 2015-09-10 at 16:08 -0700, Andrew Morton wrote:
>> > On Fri,  4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <
>> > vkuznets@redhat.com> wrote:
>> > 
>> > > string_get_size(1, 512, 0, ..., ...) call results in an infinite 
>> > > loop. The
>> > > problem is that if size == 0 when we start calculating sf_cap 
>> > > this loop
>> > > will never end.
>> > > 
>> > > The caller causing the issue is sd_read_capacity(), the problem 
>> > > was noticed
>> > > on Hyper-V.
>> > 
>> > When fixing bugs, please provide enough info for others to be able 
>> > to
>> > understand which kernel version(s) need the fix.  In this case: 
>> > what
>> > end-user action triggers this bug?  (iow, how does sdkp->capacity
>> > become zero?)
>> 
>> Any more details.  The attached programme, which is cut straight out 
>> of
>> the algorithm in string_helpers.c and modified for a C environment
>> slightly (only in do_div and the typedefs) produces this
>> 
>> hello
>> STRING IS 512 B
>> 
>> With your input, so I don't think the problem is where you think it 
>> is.
>> 
>> James
>> 
>
> Vitaly, it might make sense to extend test-string_helpers.c to what you
> are trying to do right.

The issue is that string_get_size() enters an infinite loop on some
inputs so if we add a test for such inputs we'll hang our kernel...

-- 
  Vitaly

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

[Andy Shevchenko]

On Mon, 2015-09-14 at 14:43 +0200, Vitaly Kuznetsov wrote:
> Andy Shevchenko <andriy.shevchenko@linux.intel.com> writes:
> 
> > On Fri, 2015-09-11 at 18:31 +0000, James Bottomley wrote:
> > > On Thu, 2015-09-10 at 16:08 -0700, Andrew Morton wrote:
> > > > On Fri,  4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <
> > > > vkuznets@redhat.com> wrote:
> > > > 
> > > > > string_get_size(1, 512, 0, ..., ...) call results in an 
> > > > > infinite 
> > > > > loop. The
> > > > > problem is that if size == 0 when we start calculating sf_cap 
> > > > > 
> > > > > this loop
> > > > > will never end.
> > > > > 
> > > > > The caller causing the issue is sd_read_capacity(), the 
> > > > > problem 
> > > > > was noticed
> > > > > on Hyper-V.
> > > > 
> > > > When fixing bugs, please provide enough info for others to be 
> > > > able 
> > > > to
> > > > understand which kernel version(s) need the fix.  In this case: 
> > > > 
> > > > what
> > > > end-user action triggers this bug?  (iow, how does sdkp
> > > > ->capacity
> > > > become zero?)
> > > 
> > > Any more details.  The attached programme, which is cut straight 
> > > out 
> > > of
> > > the algorithm in string_helpers.c and modified for a C 
> > > environment
> > > slightly (only in do_div and the typedefs) produces this
> > > 
> > > hello
> > > STRING IS 512 B
> > > 
> > > With your input, so I don't think the problem is where you think 
> > > it 
> > > is.
> > > 
> > > James
> > > 
> > 
> > Vitaly, it might make sense to extend test-string_helpers.c to what 
> > you
> > are trying to do right.
> 
> The issue is that string_get_size() enters an infinite loop on some
> inputs so if we add a test for such inputs we'll hang our kernel...
> 

I didn't see a problem to add this test case. Since test module is
dedicated for that (tests).

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

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

[Vitaly Kuznetsov]

James Bottomley <jbottomley@odin.com> writes:

> On Thu, 2015-09-10 at 16:08 -0700, Andrew Morton wrote:
>> On Fri,  4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <vkuznets@redhat.com> wrote:
>> 
>> > string_get_size(1, 512, 0, ..., ...) call results in an infinite loop. The
>> > problem is that if size == 0 when we start calculating sf_cap this loop
>> > will never end.
>> > 
>> > The caller causing the issue is sd_read_capacity(), the problem was noticed
>> > on Hyper-V.
>> 
>> When fixing bugs, please provide enough info for others to be able to
>> understand which kernel version(s) need the fix.  In this case: what
>> end-user action triggers this bug?  (iow, how does sdkp->capacity
>> become zero?)
>
> Any more details.  The attached programme, which is cut straight out of
> the algorithm in string_helpers.c and modified for a C environment
> slightly (only in do_div and the typedefs) produces this
>
> hello
> STRING IS 512 B
>
> With your input, so I don't think the problem is where you think it
> is.

Sorry for delayed reply, I was traveling.

Please change
string_get_size(1, 512, STRING_UNITS_2, buf, sizeof(buf));

to
string_get_size(1, 512, STRING_UNITS_10, buf, sizeof(buf));

in your test.c program to see the issue, it will enter the infinite loop
as well.

Regardless to Hyper-V I think such library function shouldn't do such
nasty things (but I'll try to investigate why such small size was
reported).

-- 
  Vitaly

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

[James Bottomley]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="utf-8", Size: 1305 bytes --]

On Fri, 2015-09-04 at 14:56 +0200, Vitaly Kuznetsov wrote:
> string_get_size(1, 512, 0, ..., ...) call results in an infinite loop. The
> problem is that if size == 0 when we start calculating sf_cap this loop
> will never end.
> 
> The caller causing the issue is sd_read_capacity(), the problem was noticed
> on Hyper-V.
> 
> Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
> ---
>  lib/string_helpers.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/lib/string_helpers.c b/lib/string_helpers.c
> index c98ae81..a155c7b 100644
> --- a/lib/string_helpers.c
> +++ b/lib/string_helpers.c
> @@ -76,7 +76,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
>  		i++;
>  	}
>  
> -	sf_cap = size;
> +	sf_cap = size ? size : 1;

If size can become zero after the scale adjustment, then there's a fault
in the algorithm, and this probably isn't the right fix.  However, I did
a brief calculation, and I can't see how size becomes zero ... it might
be that I haven't looked at this long enough (I am on holiday).

James

>  	for (j = 0; sf_cap*10 < 1000; j++)
>  		sf_cap *= 10;
>  


ÿôèº{.nÇ+‰·Ÿ®‰­†+%ŠËÿ±éݶ\x17¥Šwÿº{.nÇ+‰·¥Š{±þG«éÿŠ{ayº\x1dʇڙë,j\a­¢f£¢·hšïêÿ‘êçz_è®\x03(­éšŽŠÝ¢j"ú\x1a¶^[m§ÿÿ¾\a«þG«éÿ¢¸?™¨è­Ú&£ø§~á¶iO•æ¬z·švØ^\x14\x04\x1a¶^[m§ÿÿÃ\fÿ¶ìÿ¢¸?–I¥

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

[Vitaly Kuznetsov]

James Bottomley <jbottomley@odin.com> writes:

> On Fri, 2015-09-04 at 14:56 +0200, Vitaly Kuznetsov wrote:
>> string_get_size(1, 512, 0, ..., ...) call results in an infinite loop. The
>> problem is that if size == 0 when we start calculating sf_cap this loop
>> will never end.
>> 
>> The caller causing the issue is sd_read_capacity(), the problem was noticed
>> on Hyper-V.
>> 
>> Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
>> ---
>>  lib/string_helpers.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>> 
>> diff --git a/lib/string_helpers.c b/lib/string_helpers.c
>> index c98ae81..a155c7b 100644
>> --- a/lib/string_helpers.c
>> +++ b/lib/string_helpers.c
>> @@ -76,7 +76,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
>>  		i++;
>>  	}
>>  
>> -	sf_cap = size;
>> +	sf_cap = size ? size : 1;
>
> If size can become zero after the scale adjustment, then there's a fault
> in the algorithm, and this probably isn't the right fix.  However, I did
> a brief calculation, and I can't see how size becomes zero ...

... but it does ...

> it might be that I haven't looked at this long enough (I am on holiday).

The function itself looks over complicated to me but you're probably
right and I'll try to find the root cause of the issue in the algorythm.

Thanks,

>
> James
>
>>  	for (j = 0; sf_cap*10 < 1000; j++)
>>  		sf_cap *= 10;
>>  

-- 
  Vitaly