Skip to contentSkip to conversation

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

PATCH Superseded Vitaly Kuznetsov 4 participants 9 messages Sep 4, 2015 – Sep 14, 2015

Subsystems (2)

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

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

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.

---
 lib/string_helpers.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/string_helpers.c +1 -1
index c98ae81..a155c7b 100644
@@ -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;
 
Signature · 1 line
2.4.3
maintainer
#1 lore raw
Quoted 6 lines · On Fri, 4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <[email protected]> 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?)

#2 lore raw
Quoted 6 lines · Andrew Morton
Quoted 4 lines · On Fri, 4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <[email protected]> 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.

Quoted 7 lines
Quoted 2 lines

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

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

}

#3 lore raw
Quoted 26 lines · James Bottomley
Quoted 13 lines · Andrew Morton
Quoted 9 lines · On Fri, 4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov < [email protected]>…

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.

Quoted 6 lines

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

Quoted 8 lines

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.

Signature · 2 lines
Andy Shevchenko <[email protected]>
Intel Finland Oy
#4 lore raw
Quoted 30 lines · Andy Shevchenko
Quoted 29 lines · James Bottomley
Quoted 13 lines · Andrew Morton
Quoted 9 lines · On Fri, 4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov < [email protected]>…

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.

Quoted 6 lines

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

Quoted 8 lines
Quoted 5 lines

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

Signature · 1 line
  Vitaly
#5 lore raw
Quoted 47 lines · Vitaly Kuznetsov
Quoted 45 lines · Andy Shevchenko
Quoted 43 lines · James Bottomley
Quoted 21 lines · Andrew Morton
Quoted 5 lines · On Fri, 4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov < [email protected]>…

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

Quoted 7 lines

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:

Quoted 4 lines

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

Quoted 7 lines
Quoted 3 lines

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

Signature · 2 lines
Andy Shevchenko <[email protected]>
Intel Finland Oy
#6 lore raw
In reply to James Bottomley
Quoted 19 lines · James Bottomley
Quoted 6 lines · Andrew Morton
Quoted 4 lines · On Fri, 4 Sep 2015 14:56:33 +0200 Vitaly Kuznetsov <[email protected]> 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.

Quoted 7 lines
Quoted 2 lines

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

Quoted 5 lines

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

Signature · 1 line
  Vitaly
#7 lore raw
In reply to Vitaly Kuznetsov
Quoted 17 lines · 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.

---
 lib/string_helpers.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/string_helpers.c +0 -0
index c98ae81..a155c7b 100644

lib/string_helpers.c void string_get_size(u64 size, u64 blk_size, const enum string_size_units units, · line 79

Quoted 5 lines
lib/string_helpers.c +1 -1
@@ -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

lib/string_helpers.c void string_get_size(u64 size, u64 blk_size, const enum string_size_units units, · line 82

Quoted 3 lines
lib/string_helpers.c +0 -0
 	for (j = 0; sf_cap*10 < 1000; j++)
 		sf_cap *= 10;
 

���{.n�+�������+%�����ݶ��w��{.n�+����{��G�����{ay�ʇڙ�,j��f���h��������z_�(�階�ݢj"���m������G������?����&���~��iO��z��v�^�m���� ������?�I�

#8 lore raw
Quoted 21 lines · James Bottomley
Quoted 20 lines · 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.

---
 lib/string_helpers.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/string_helpers.c +0 -0
index c98ae81..a155c7b 100644
@@ -76,7 +76,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		i++;
 	}
 
Quoted 6 lines

lib/string_helpers.c void string_get_size(u64 size, u64 blk_size, const enum string_size_units units, · line 79

Quoted 2 lines
lib/string_helpers.c +1 -1
-	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 ...

Quoted 1 line

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,

Quoted 6 lines

James

Quoted 3 lines
lib/string_helpers.c +0 -0
 	for (j = 0; sf_cap*10 < 1000; j++)
 		sf_cap *= 10;
 
Signature · 1 line
  Vitaly