Skip to contentSkip to conversation

lib/string_helpers: fix precision issues and introduce tests

PATCH In review Vitaly Kuznetsov 4 participants 25 messages Oct 29, 2015 – Nov 3, 2015

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

v3 cover lib/string_helpers: fix precision issues and introduce tests

Linux always lies about your storage size when it has 4k sectors and its size is big enough. E.g. a device with 8192 4k sectors will be reported as "32.7 MB/32 MiB" while "33.5 MB/32 MiB" is expected. This series is supposed to fix the issue by fixing calculation precision in string_get_size() for all possible inputs.

PATCH 1/4 is a preparatory change, PATCH 2/4 adds additional protection against blk_size=0 (nobody is supposed to call string_get_size() with with blk_size=0, but better safe than sorry), PATCH 3/4 re-factors string_get_size() fixing the issue, PATCH 4/4 introduces tests for string_get_size().

PATCH 4/4 was previously sent as part of "lib/string_helpers.c: fix infinite loop in string_get_size()" series but it is still not merged upstream. In this submission I improve it and add additional tests to it.

Changes since v2:
- Separate blk_size check from Patch 3/4 to new Patch 2/4 [Andy Shevchenko]
- Slightly change the algorithm in Patch 3/4 [Rasmus Villemoes]

Vitaly Kuznetsov (4):
lib/string_helpers: change blk_size to u32 for string_get_size()
interface
lib/string_helpers.c: protect string_get_size() against blk_size=0 lib/string_helpers.c: don't lose precision in string_get_size() lib/test-string_helpers.c: add string_get_size() tests

 include/linux/string_helpers.h |  2 +-
 lib/string_helpers.c           | 38 ++++++++++++++-------------
 lib/test-string_helpers.c      | 58 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 79 insertions(+), 19 deletions(-)
Signature · 1 line
2.4.3
#1 lore raw

PATCH v3 1/4 lib/string_helpers: change blk_size to u32 for string_get_size() interface

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

---
 include/linux/string_helpers.h | 2 +-
 lib/string_helpers.c           | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)
include/linux/string_helpers.h +1 -1
index dabe643..1223e80 100644
@@ -10,7 +10,7 @@ enum string_size_units {
 	STRING_UNITS_2,		/* use binary powers of 2^10 */
 };
 
-void string_get_size(u64 size, u64 blk_size, enum string_size_units units,
+void string_get_size(u64 size, u32 blk_size, enum string_size_units units,
 		     char *buf, int len);
 
 #define UNESCAPE_SPACE		0x01
lib/string_helpers.c +2 -2
index 5939f63..f6c27dc 100644
@@ -26,7 +26,7 @@
  * 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,
+void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 		     char *buf, int len)
 {
 	static const char *const units_10[] = {
@@ -58,7 +58,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		i++;
 	}
 
-	exp = divisor[units] / (u32)blk_size;
+	exp = divisor[units] / blk_size;
 	/*
 	 * size must be strictly greater than exp here to ensure that remainder
 	 * is greater than divisor[units] coming out of the if below.
Signature · 1 line
2.4.3
#2 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

James

Quoted 33 lines
---
 include/linux/string_helpers.h | 2 +-
 lib/string_helpers.c           | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)
include/linux/string_helpers.h +1 -1
index dabe643..1223e80 100644
@@ -10,7 +10,7 @@ enum string_size_units {
 	STRING_UNITS_2,		/* use binary powers of 2^10 */
 };
 
-void string_get_size(u64 size, u64 blk_size, enum string_size_units units,
+void string_get_size(u64 size, u32 blk_size, enum string_size_units units,
 		     char *buf, int len);
 
 #define UNESCAPE_SPACE		0x01
lib/string_helpers.c +1 -1
index 5939f63..f6c27dc 100644
@@ -26,7 +26,7 @@
  * 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,
+void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 		     char *buf, int len)
 {
 	static const char *const units_10[] = {

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

Quoted 8 lines
lib/string_helpers.c +1 -1
@@ -58,7 +58,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		i++;
 	}
 
-	exp = divisor[units] / (u32)blk_size;
+	exp = divisor[units] / blk_size;
 	/*
 	 * size must be strictly greater than exp here to ensure that remainder
 	 * is greater than divisor[units] coming out of the if below.

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

#3 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 9 lines · James Bottomley
Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

May I politely ask how you tested it, and what you mean by "worked"? The bug I reported last week was particularly concerning block sizes >= 1024 (e.g. the 32768, 1024 pair giving 32.7 MB where the correct output would be 33.5 MB). Now it turns out that it was actually broken for smaller block sizes as well. For ~13000 semirandom size,blk_size pairs, the current code produces the wrong result in ~2100 cases. The new code reduces that to 122 cases, all of which are off by one in the last digit.

And I don't buy the symmetry argument either. Mathematically, it should give the same, but your algorithm produces 2.04 MB for 512,4096 and 2.09 MB for 4096,512.

Maybe the commit message could be better, but I think it makes a lot of sense to make blk_size u32. Breaking the symmetry between size and blk_size is good (less likely that the arguments get swapped). It allows a simpler implementation. It makes the generated code smaller.

Rasmus

#4 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 1 line · Rasmus Villemoes

block sizes as well. For ~13000 semirandom size,blk_size pairs,

Sorry, that should have been ~20000.

Rasmus

#5 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

In reply to Rasmus Villemoes
Quoted 12 lines · Rasmus Villemoes
Quoted 9 lines · James Bottomley
Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

Quoted 4 lines

May I politely ask how you tested it, and what you mean by "worked"? The bug I reported last week was particularly concerning block sizes >= 1024 (e.g. the 32768, 1024 pair giving 32.7 MB where the correct output would be 33.5 MB).

The test was basically a userspace version reversing the large size smaller block size numbers and verifying they produce the same output.

Quoted 5 lines

Now it turns out that it was actually broken for smaller
block sizes as well. For ~13000 semirandom size,blk_size pairs, the current code produces the wrong result in ~2100 cases. The new code reduces that to 122 cases, all of which are off by one in the last digit.

I wasn't making the point that there isn't a potential off by a couple of percent problem in the algorithm I was making the point that it should work as a multiplier of two u64 numbers, so I can't understand the rational basis for reducing the block size to u32.

Quoted 3 lines

And I don't buy the symmetry argument either. Mathematically, it should give the same, but your algorithm produces 2.04 MB for 512,4096 and 2.09 MB for 4096,512.

That's an off by 2.5%; it means there's a slight error in one of the carries it doesn't mean there's a fundamental problem in the algorithm.

Quoted 5 lines

Maybe the commit message could be better, but I think it makes a lot of sense to make blk_size u32. Breaking the symmetry between size and blk_size is good (less likely that the arguments get swapped). It allows a simpler implementation. It makes the generated code smaller.

The drive vendors are already pushing huge block size systems for ZBC. They're already talking about 2GB sectors, which is 31 bits ... they'll be over the 32 bit limit fairly shortly, I predict, so it makes no sense to have to have the storage layer do silly bit shifting because we were short sighted enough to cap block size to a u32.

James

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

#6 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

In reply to James Bottomley
Quoted 8 lines · James Bottomley
Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

We have 'u32 remainder' and then we do:

exp = divisor[units] / (u32)blk_size;
...
remainder = do_div(size, divisor[units]);
remainder *= blk_size;

I'm pretty sure it will overflow for some inputs.

Quoted 44 lines

James

Quoted 41 lines
---
 include/linux/string_helpers.h | 2 +-
 lib/string_helpers.c           | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)
include/linux/string_helpers.h +1 -1
index dabe643..1223e80 100644
@@ -10,7 +10,7 @@ enum string_size_units {
 	STRING_UNITS_2,		/* use binary powers of 2^10 */
 };
 
-void string_get_size(u64 size, u64 blk_size, enum string_size_units units,
+void string_get_size(u64 size, u32 blk_size, enum string_size_units units,
 		     char *buf, int len);
 
 #define UNESCAPE_SPACE		0x01
lib/string_helpers.c +2 -2
index 5939f63..f6c27dc 100644
@@ -26,7 +26,7 @@
  * 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,
+void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 		     char *buf, int len)
 {
 	static const char *const units_10[] = {
@@ -58,7 +58,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		i++;
 	}
 
-	exp = divisor[units] / (u32)blk_size;
+	exp = divisor[units] / blk_size;
 	/*
 	 * size must be strictly greater than exp here to ensure that remainder
 	 * is greater than divisor[units] coming out of the if below.
Signature · 1 line
  Vitaly
#7 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 11 lines · Vitaly Kuznetsov
Quoted 8 lines · James Bottomley
Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

Quoted 8 lines

We have 'u32 remainder' and then we do:

exp = divisor[units] / (u32)blk_size;
...
remainder = do_div(size, divisor[units]);
remainder *= blk_size;

I'm pretty sure it will overflow for some inputs.

It shouldn't; the full code snippet does this:

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

So by the time it reaches the statement you complain about, blk_size is already less than or equal to the divisor (which is 1000 or 1024) so truncating to 32 bits is always correct.

I'm sort of getting the impression you don't quite understand the
mathematics: i is the logarithm to the base divisor[units]. We reduce both operands to exponents of the logarithm base (adding the two bases together in i), which means they are by definition in a range between zero and the base and then multiply the remaining exponents correcting the result for a base overflow (so the result is always a correct exponent and i is the logarithm to the base). It's actually simply Napier's algorithm.

The reason we're getting the up to 2.5% rounding errors you complain about is because at each logarithm until the last one, we throw away the remainder (it's legitimate because it's always 1000x smaller than the exponent), but in the case of a large remainder it provides a small correction to the final operation which we don't account for. If you want to make a true correction, you save the penultimate residue in each case, multiply each by the *other* exponent add them together, divide by the base and increment the final result by the remainder.

However, for 2.5% the physicist in me says the above is way overkill.

James

Quoted 39 lines
Quoted 39 lines

James

Quoted 36 lines
---
 include/linux/string_helpers.h | 2 +-
 lib/string_helpers.c           | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)
include/linux/string_helpers.h +1 -1
index dabe643..1223e80 100644
@@ -10,7 +10,7 @@ enum string_size_units {
 	STRING_UNITS_2,		/* use binary powers of 2^10 */
 };
 
-void string_get_size(u64 size, u64 blk_size, enum string_size_units units,
+void string_get_size(u64 size, u32 blk_size, enum string_size_units units,
 		     char *buf, int len);
 
 #define UNESCAPE_SPACE		0x01
lib/string_helpers.c +1 -1
index 5939f63..f6c27dc 100644
@@ -26,7 +26,7 @@
  * 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,
+void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 		     char *buf, int len)
 {
 	static const char *const units_10[] = {
@@ -58,7 +58,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		i++;
 	}
 
Quoted 6 lines
Quoted 5 lines

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

Quoted 5 lines
lib/string_helpers.c +1 -1
-	exp = divisor[units] / (u32)blk_size;
+	exp = divisor[units] / blk_size;
 	/*
 	 * size must be strictly greater than exp here to ensure that remainder
 	 * is greater than divisor[units] coming out of the if below.

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

#8 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 30 lines · James Bottomley
Quoted 11 lines · Vitaly Kuznetsov
Quoted 8 lines · James Bottomley
Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

Quoted 8 lines

We have 'u32 remainder' and then we do:

exp = divisor[units] / (u32)blk_size;
...
remainder = do_div(size, divisor[units]);
remainder *= blk_size;

I'm pretty sure it will overflow for some inputs.

It shouldn't; the full code snippet does this:

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

        	exp = divisor[units] / (u32)blk_size;
Quoted 4 lines

So by the time it reaches the statement you complain about, blk_size is already less than or equal to the divisor (which is 1000 or 1024) so truncating to 32 bits is always correct.

I overlooked, sorry!

Quoted 9 lines

I'm sort of getting the impression you don't quite understand the
mathematics: i is the logarithm to the base divisor[units]. We reduce both operands to exponents of the logarithm base (adding the two bases together in i), which means they are by definition in a range between zero and the base and then multiply the remaining exponents correcting the result for a base overflow (so the result is always a correct exponent and i is the logarithm to the base). It's actually simply Napier's algorithm.

Quoted 8 lines

The reason we're getting the up to 2.5% rounding errors you complain about is because at each logarithm until the last one, we throw away the remainder (it's legitimate because it's always 1000x smaller than the exponent), but in the case of a large remainder it provides a small correction to the final operation which we don't account for. If you want to make a true correction, you save the penultimate residue in each case, multiply each by the *other* exponent add them together, divide by the base and increment the final result by the remainder.

My assumption was that we don't really need to support blk_sizes > U32_MAX and we can simplify string_get_size() instead of adding additional complexity. Apparently, the assumption was wrong.

Quoted 3 lines

However, for 2.5% the physicist in me says the above is way overkill.

It is getting was over 2.5% if blk_size is not a power of 2. While it is probably never the case for block subsystem the function is in lib and pretends to be general-enough. I'll try to make proper correction and let's see if it's worth the effort.

Thanks,

Quoted 47 lines

James

Quoted 45 lines
Quoted 44 lines

James

Quoted 41 lines
---
 include/linux/string_helpers.h | 2 +-
 lib/string_helpers.c           | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)
include/linux/string_helpers.h +1 -1
index dabe643..1223e80 100644
@@ -10,7 +10,7 @@ enum string_size_units {
 	STRING_UNITS_2,		/* use binary powers of 2^10 */
 };
 
-void string_get_size(u64 size, u64 blk_size, enum string_size_units units,
+void string_get_size(u64 size, u32 blk_size, enum string_size_units units,
 		     char *buf, int len);
 
 #define UNESCAPE_SPACE		0x01
lib/string_helpers.c +2 -2
index 5939f63..f6c27dc 100644
@@ -26,7 +26,7 @@
  * 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,
+void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 		     char *buf, int len)
 {
 	static const char *const units_10[] = {
@@ -58,7 +58,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		i++;
 	}
 
-	exp = divisor[units] / (u32)blk_size;
+	exp = divisor[units] / blk_size;
 	/*
 	 * size must be strictly greater than exp here to ensure that remainder
 	 * is greater than divisor[units] coming out of the if below.
Signature · 1 line
  Vitaly
#9 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 62 lines · Vitaly Kuznetsov
Quoted 30 lines · James Bottomley
Quoted 11 lines · Vitaly Kuznetsov
Quoted 8 lines · James Bottomley
Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

Quoted 8 lines

We have 'u32 remainder' and then we do:

exp = divisor[units] / (u32)blk_size;
...
remainder = do_div(size, divisor[units]);
remainder *= blk_size;

I'm pretty sure it will overflow for some inputs.

It shouldn't; the full code snippet does this:

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

        	exp = divisor[units] / (u32)blk_size;
Quoted 4 lines

So by the time it reaches the statement you complain about, blk_size is already less than or equal to the divisor (which is 1000 or 1024) so truncating to 32 bits is always correct.

I overlooked, sorry!

Quoted 9 lines

I'm sort of getting the impression you don't quite understand the
mathematics: i is the logarithm to the base divisor[units]. We reduce both operands to exponents of the logarithm base (adding the two bases together in i), which means they are by definition in a range between zero and the base and then multiply the remaining exponents correcting the result for a base overflow (so the result is always a correct exponent and i is the logarithm to the base). It's actually simply Napier's algorithm.

Quoted 8 lines

The reason we're getting the up to 2.5% rounding errors you complain about is because at each logarithm until the last one, we throw away the remainder (it's legitimate because it's always 1000x smaller than the exponent), but in the case of a large remainder it provides a small correction to the final operation which we don't account for. If you want to make a true correction, you save the penultimate residue in each case, multiply each by the *other* exponent add them together, divide by the base and increment the final result by the remainder.

My assumption was that we don't really need to support blk_sizes > U32_MAX and we can simplify string_get_size() instead of adding additional complexity. Apparently, the assumption was wrong.

Quoted 1 line
Quoted 7 lines
Quoted 2 lines

However, for 2.5% the physicist in me says the above is way overkill.

It is getting was over 2.5% if blk_size is not a power of 2. While it is probably never the case for block subsystem the function is in lib and pretends to be general-enough. I'll try to make proper correction and let's see if it's worth the effort.

OK, this is the full calculation. It also includes an arithmetic rounding to the final figure print. I suppose it's not that much more complexity than the original, and it does make the algorithm easier to understand.

We could do with running the comments by some other non-mathematician, now I've explained it in detail to you two, to see if they actually give an understanding of the algorithm.

James

---

lib/string_helpers.c +42 -16
index 5939f63..1ec7e77a 100644
@@ -44,7 +44,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		[STRING_UNITS_2] = 1024,
 	};
 	int i, j;
-	u32 remainder = 0, sf_cap, exp;
+	u32 remainder = 0, sf_cap, r1 = 0, r2 = 0, round;
 	char tmp[8];
 	const char *unit;
 
@@ -53,27 +53,46 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 	if (!size)
 		goto out;
 
+	/* This is napier's algorithm.  Reduce the original block size to
+	 *
+	 * co * divisor[units]^i
+	 *
+	 * where co = blk_size + r1/divisor[units];
+	 *
+	 * and the same for size.  We simply add to the exponent i, because
+	 * the final calculation we're looking for is
+	 *
+	 * (co1 * co2) * divisor[units]^i
+	 */
+
+
 	while (blk_size >= divisor[units]) {
-		remainder = do_div(blk_size, divisor[units]);
+		r1 = do_div(blk_size, divisor[units]);
 		i++;
 	}
 
-	exp = divisor[units] / (u32)blk_size;
-	/*
-	 * 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;
+	while (size >= divisor[units]) {
+		r2 = do_div(size, divisor[units]);
 		i++;
-	} else {
-		remainder *= size;
 	}
 
-	size *= blk_size;
-	size += remainder / divisor[units];
-	remainder %= divisor[units];
+	/* here's the magic.  co1 * co2 may be > divisor[i], so correct for
+	 * that in the exponent and make sure that the additional corrections
+	 * from the remainders is added in.
+	 *
+	 * co1 *co2 = (blk_size + r1/divisor[units])*(size + r2/divisor[units])
+	 *
+	 * therefore
+	 *
+	 * co1*co2*divisor[units] = blk_size*size*divisor[units] +
+	 *          r1*size + r2*size + r1*r2/divisor[units]
+	 *
+	 * drop the last term because it's too small and perform the
+	 * calculation cleverly by decremeting i to be automatically dealing
+	 * with everything multiplied by divisor[units] */
+
+	--i;
+	size = size * blk_size * divisor[units] + r1 * size + r2 * blk_size;
 
 	while (size >= divisor[units]) {
 		remainder = do_div(size, divisor[units]);
@@ -81,8 +100,15 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 	}
 
 	sf_cap = size;
-	for (j = 0; sf_cap*10 < 1000; j++)
+	round = 500;
+	for (j = 0; sf_cap*10 < 1000; j++) {
 		sf_cap *= 10;
+		round /= 10;
+	}
+
+	/* add a 5 to the digit below what will be printed to ensure
+	 * an arithmetical round up */
+	remainder += round;
 
 	if (j) {
 		remainder *= 1000;

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

#10 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 71 lines · James Bottomley
Quoted 62 lines · Vitaly Kuznetsov
Quoted 30 lines · James Bottomley
Quoted 11 lines · Vitaly Kuznetsov
Quoted 8 lines · James Bottomley
Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

Quoted 8 lines

We have 'u32 remainder' and then we do:

exp = divisor[units] / (u32)blk_size;
...
remainder = do_div(size, divisor[units]);
remainder *= blk_size;

I'm pretty sure it will overflow for some inputs.

It shouldn't; the full code snippet does this:

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

        	exp = divisor[units] / (u32)blk_size;
Quoted 4 lines

So by the time it reaches the statement you complain about, blk_size is already less than or equal to the divisor (which is 1000 or 1024) so truncating to 32 bits is always correct.

I overlooked, sorry!

Quoted 9 lines

I'm sort of getting the impression you don't quite understand the
mathematics: i is the logarithm to the base divisor[units]. We reduce both operands to exponents of the logarithm base (adding the two bases together in i), which means they are by definition in a range between zero and the base and then multiply the remaining exponents correcting the result for a base overflow (so the result is always a correct exponent and i is the logarithm to the base). It's actually simply Napier's algorithm.

Quoted 8 lines

The reason we're getting the up to 2.5% rounding errors you complain about is because at each logarithm until the last one, we throw away the remainder (it's legitimate because it's always 1000x smaller than the exponent), but in the case of a large remainder it provides a small correction to the final operation which we don't account for. If you want to make a true correction, you save the penultimate residue in each case, multiply each by the *other* exponent add them together, divide by the base and increment the final result by the remainder.

My assumption was that we don't really need to support blk_sizes > U32_MAX and we can simplify string_get_size() instead of adding additional complexity. Apparently, the assumption was wrong.

Quoted 1 line
Quoted 7 lines
Quoted 2 lines

However, for 2.5% the physicist in me says the above is way overkill.

It is getting was over 2.5% if blk_size is not a power of 2. While it is probably never the case for block subsystem the function is in lib and pretends to be general-enough. I'll try to make proper correction and let's see if it's worth the effort.

Quoted 8 lines

OK, this is the full calculation. It also includes an arithmetic rounding to the final figure print. I suppose it's not that much more complexity than the original, and it does make the algorithm easier to understand.

We could do with running the comments by some other non-mathematician, now I've explained it in detail to you two, to see if they actually give an understanding of the algorithm.

Thanks, to me they look great! One nitpick below ...

Quoted 67 lines

James

---

lib/string_helpers.c +25 -15
index 5939f63..1ec7e77a 100644
@@ -44,7 +44,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		[STRING_UNITS_2] = 1024,
 	};
 	int i, j;
-	u32 remainder = 0, sf_cap, exp;
+	u32 remainder = 0, sf_cap, r1 = 0, r2 = 0, round;
 	char tmp[8];
 	const char *unit;
 
@@ -53,27 +53,46 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 	if (!size)
 		goto out;
 
+	/* This is napier's algorithm.  Reduce the original block size to
+	 *
+	 * co * divisor[units]^i
+	 *
+	 * where co = blk_size + r1/divisor[units];
+	 *
+	 * and the same for size.  We simply add to the exponent i, because
+	 * the final calculation we're looking for is
+	 *
+	 * (co1 * co2) * divisor[units]^i
+	 */
+
+
 	while (blk_size >= divisor[units]) {
-		remainder = do_div(blk_size, divisor[units]);
+		r1 = do_div(blk_size, divisor[units]);
 		i++;
 	}
 
-	exp = divisor[units] / (u32)blk_size;
-	/*
-	 * 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;
+	while (size >= divisor[units]) {
+		r2 = do_div(size, divisor[units]);
 		i++;
-	} else {
-		remainder *= size;
 	}
 
-	size *= blk_size;
-	size += remainder / divisor[units];
-	remainder %= divisor[units];
+	/* here's the magic.  co1 * co2 may be > divisor[i], so correct for
+	 * that in the exponent and make sure that the additional corrections
+	 * from the remainders is added in.
+	 *
+	 * co1 *co2 = (blk_size + r1/divisor[units])*(size + r2/divisor[units])
+	 *
+	 * therefore
+	 *

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

Quoted 10 lines
lib/string_helpers.c +9 -0
+	 * co1*co2*divisor[units] = blk_size*size*divisor[units] +
+	 *          r1*size + r2*size + r1*r2/divisor[units]
+	 *
+	 * drop the last term because it's too small and perform the
+	 * calculation cleverly by decremeting i to be automatically dealing
+	 * with everything multiplied by divisor[units] */
+
+	--i;
+	size = size * blk_size * divisor[units] + r1 * size + r2 *
 blk_size;

The last term is actually not that small. Here is an example:

size = 8192 blk_size = 1024

'As is' the algorithm gives us '8.38 MB', and if we add "+ r1 * r1 / divisor[units]" we get '8.39 MB' (the correct answer is 8192 * 1024 = 8388608 which is 8.39).

Both r1 and r2 are < divisor[units] here so r1 * r2 won't overflow u32, I suggest we add this term.

Quoted 10 lines
lib/string_helpers.c +2 -1
 	while (size >= divisor[units]) {
 		remainder = do_div(size, divisor[units]);
@@ -81,8 +100,15 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 	}
 
 	sf_cap = size;
-	for (j = 0; sf_cap*10 < 1000; j++)
+	round = 500;
+	for (j = 0; sf_cap*10 < 1000; j++) {

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

Quoted 10 lines
lib/string_helpers.c +6 -0
 		sf_cap *= 10;
+		round /= 10;
+	}
+
+	/* add a 5 to the digit below what will be printed to ensure
+	 * an arithmetical round up */
+	remainder += round;
 
 	if (j) {
 		remainder *= 1000;

Can I post this solution with your Suggested-by or do you plan to do it yourself?

Thanks,

Signature · 1 line
  Vitaly
#11 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 155 lines · Vitaly Kuznetsov
Quoted 71 lines · James Bottomley
Quoted 62 lines · Vitaly Kuznetsov
Quoted 30 lines · James Bottomley
Quoted 11 lines · Vitaly Kuznetsov
Quoted 8 lines · James Bottomley
Quoted 3 lines · Vitaly Kuznetsov

string_get_size() can't really handle huge block sizes, especially blk_size > U32_MAX but string_get_size() interface states the opposite. Change blk_size from u64 to u32 to reflect the reality.

What is the actual evidence for this? The calculation is designed to be a symmetric 128 bit multiply. When I wrote and tested it, it worked fine for huge block sizes.

Quoted 8 lines

We have 'u32 remainder' and then we do:

exp = divisor[units] / (u32)blk_size;
...
remainder = do_div(size, divisor[units]);
remainder *= blk_size;

I'm pretty sure it will overflow for some inputs.

It shouldn't; the full code snippet does this:

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

        	exp = divisor[units] / (u32)blk_size;
Quoted 4 lines

So by the time it reaches the statement you complain about, blk_size is already less than or equal to the divisor (which is 1000 or 1024) so truncating to 32 bits is always correct.

I overlooked, sorry!

Quoted 9 lines

I'm sort of getting the impression you don't quite understand the
mathematics: i is the logarithm to the base divisor[units]. We reduce both operands to exponents of the logarithm base (adding the two bases together in i), which means they are by definition in a range between zero and the base and then multiply the remaining exponents correcting the result for a base overflow (so the result is always a correct exponent and i is the logarithm to the base). It's actually simply Napier's algorithm.

Quoted 8 lines

The reason we're getting the up to 2.5% rounding errors you complain about is because at each logarithm until the last one, we throw away the remainder (it's legitimate because it's always 1000x smaller than the exponent), but in the case of a large remainder it provides a small correction to the final operation which we don't account for. If you want to make a true correction, you save the penultimate residue in each case, multiply each by the *other* exponent add them together, divide by the base and increment the final result by the remainder.

My assumption was that we don't really need to support blk_sizes > U32_MAX and we can simplify string_get_size() instead of adding additional complexity. Apparently, the assumption was wrong.

Quoted 1 line
Quoted 7 lines
Quoted 2 lines

However, for 2.5% the physicist in me says the above is way overkill.

It is getting was over 2.5% if blk_size is not a power of 2. While it is probably never the case for block subsystem the function is in lib and pretends to be general-enough. I'll try to make proper correction and let's see if it's worth the effort.

Quoted 8 lines

OK, this is the full calculation. It also includes an arithmetic rounding to the final figure print. I suppose it's not that much more complexity than the original, and it does make the algorithm easier to understand.

We could do with running the comments by some other non-mathematician, now I've explained it in detail to you two, to see if they actually give an understanding of the algorithm.

Thanks, to me they look great! One nitpick below ...

Quoted 71 lines

James

---

lib/string_helpers.c +29 -15
index 5939f63..1ec7e77a 100644
@@ -44,7 +44,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 		[STRING_UNITS_2] = 1024,
 	};
 	int i, j;
-	u32 remainder = 0, sf_cap, exp;
+	u32 remainder = 0, sf_cap, r1 = 0, r2 = 0, round;
 	char tmp[8];
 	const char *unit;
 
@@ -53,27 +53,46 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 	if (!size)
 		goto out;
 
+	/* This is napier's algorithm.  Reduce the original block size to
+	 *
+	 * co * divisor[units]^i
+	 *
+	 * where co = blk_size + r1/divisor[units];
+	 *
+	 * and the same for size.  We simply add to the exponent i, because
+	 * the final calculation we're looking for is
+	 *
+	 * (co1 * co2) * divisor[units]^i
+	 */
+
+
 	while (blk_size >= divisor[units]) {
-		remainder = do_div(blk_size, divisor[units]);
+		r1 = do_div(blk_size, divisor[units]);
 		i++;
 	}
 
-	exp = divisor[units] / (u32)blk_size;
-	/*
-	 * 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;
+	while (size >= divisor[units]) {
+		r2 = do_div(size, divisor[units]);
 		i++;
-	} else {
-		remainder *= size;
 	}
 
-	size *= blk_size;
-	size += remainder / divisor[units];
-	remainder %= divisor[units];
+	/* here's the magic.  co1 * co2 may be > divisor[i], so correct for
+	 * that in the exponent and make sure that the additional corrections
+	 * from the remainders is added in.
+	 *
+	 * co1 *co2 = (blk_size + r1/divisor[units])*(size + r2/divisor[units])
+	 *
+	 * therefore
+	 *
+	 * co1*co2*divisor[units] = blk_size*size*divisor[units] +
+	 *          r1*size + r2*size + r1*r2/divisor[units]
+	 *
+	 * drop the last term because it's too small and perform the
Quoted 8 lines

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

Quoted 6 lines
lib/string_helpers.c +5 -0
+	 * calculation cleverly by decremeting i to be automatically dealing
+	 * with everything multiplied by divisor[units] */
+
+	--i;
+	size = size * blk_size * divisor[units] + r1 * size + r2 *
 blk_size;

The last term is actually not that small. Here is an example:

It's always < 1 in the final equation because it's divided by the square of divisor[units]. However, that can make a contribution to the round up, I suppose leading to the truncation you see

Quoted 27 lines

size = 8192 blk_size = 1024

'As is' the algorithm gives us '8.38 MB', and if we add "+ r1 * r1 / divisor[units]" we get '8.39 MB' (the correct answer is 8192 * 1024 = 8388608 which is 8.39).

Both r1 and r2 are < divisor[units] here so r1 * r2 won't overflow u32, I suggest we add this term.

Quoted 18 lines
lib/string_helpers.c +8 -1
 	while (size >= divisor[units]) {
 		remainder = do_div(size, divisor[units]);
@@ -81,8 +100,15 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
 	}
 
 	sf_cap = size;
-	for (j = 0; sf_cap*10 < 1000; j++)
+	round = 500;
+	for (j = 0; sf_cap*10 < 1000; j++) {
 		sf_cap *= 10;
+		round /= 10;
+	}
+
+	/* add a 5 to the digit below what will be printed to ensure
+	 * an arithmetical round up */
+	remainder += round;
 
Quoted 5 lines

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

Quoted 2 lines
lib/string_helpers.c +0 -0
 	if (j) {
 		remainder *= 1000;

Can I post this solution with your Suggested-by or do you plan to do it yourself?

It was a suggestion when I explained what the missing sources of precision were, I don't think it's really a suggestion when it comes with an exemplary patch. However, the whole thing needs polishing because all the divisions need to be eliminated, since they're a huge source of problems for most 32 bit CPUs, so I can fix it all the way and repost.

James

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

#12 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 4 lines · James Bottomley

It was a suggestion when I explained what the missing sources of precision were, I don't think it's really a suggestion when it comes with an exemplary patch.

ex·em·pla·ry
adjective

1.
serving as a desirable model; representing the best of its kind.

Said exemplary patch produces "1.10 KiB" for size=2047, blk_size=1. (This is caused by the introduction of rounding, and is probably fixable.)

James, I do understand the algorithm you're trying to use. What I don't understand is why you insist on using the approach of reducing size and blk_size all the way before multiplying them. It seems much simpler to just reduce them till they're below U32_MAX (not keeping track of any remainders at that point), multiply them, and then proceed as usual, This avoids having to deal with weird cross-multiplication terms, gives more accurate results (yes, I tested that) and avoids the extra 64/32 division you introduce by decrementing i.

Rasmus

To be precise, the body I suggest is

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

whether the last one should be > or >= is debatable; I think 1024 KiB is better than 1.00 MiB.

#13 lore raw

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Quoted 17 lines · Rasmus Villemoes
Quoted 4 lines · James Bottomley

It was a suggestion when I explained what the missing sources of precision were, I don't think it's really a suggestion when it comes with an exemplary patch.

ex·em·pla·ry
adjective

1.
serving as a desirable model; representing the best of its kind.

Said exemplary patch produces "1.10 KiB" for size=2047, blk_size=1. (This is caused by the introduction of rounding, and is probably fixable.)

Quoted 8 lines

James, I do understand the algorithm you're trying to use. What I don't understand is why you insist on using the approach of reducing size and blk_size all the way before multiplying them. It seems much simpler to just reduce them till they're below U32_MAX (not keeping track of any remainders at that point), multiply them, and then proceed as usual, This avoids having to deal with weird cross-multiplication terms, gives more accurate results (yes, I tested that) and avoids the extra 64/32 division you introduce by decrementing i.

Well, wood and trees, I think. I don't believe there's any more accuracy with the second order term, but it is a lot simpler for anyone to understand. I'll post a v2.

James

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

#14 lore raw

PATCH v3 2/4 lib/string_helpers.c: protect string_get_size() against blk_size=0

In reply to Vitaly Kuznetsov

Division by zero happens if blk_size=0 is supplied to string_get_size(). Add WARN_ON() and set size to 0 to report '0 B'.

---
 lib/string_helpers.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/string_helpers.c +5 -0
index f6c27dc..ff3575b 100644
@@ -50,6 +50,11 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 
 	tmp[0] = '\0';
 	i = 0;
+
+	/* Calling string_get_size() with blk_size=0 is wrong! */
+	if (WARN_ON(!blk_size))
+		size = 0;
+
 	if (!size)
 		goto out;
 
Signature · 1 line
2.4.3
Reviewed-by on v3 2/4
#15 lore raw

Re: [PATCH v3 2/4] lib/string_helpers.c: protect string_get_size() against blk_size=0

Quoted 4 lines · Vitaly Kuznetsov

Division by zero happens if blk_size=0 is supplied to string_get_size(). Add WARN_ON() and set size to 0 to report '0 B'.

Quoted 28 lines
---
 lib/string_helpers.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/string_helpers.c +5 -1
index f6c27dc..ff3575b 100644
@@ -50,6 +50,11 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 
        tmp[0] = '\0';
        i = 0;
+
+       /* Calling string_get_size() with blk_size=0 is wrong! */
+       if (WARN_ON(!blk_size))
+               size = 0;
+
        if (!size)
                goto out;
 
--

2.4.3

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#16 lore raw

Re: [PATCH v3 2/4] lib/string_helpers.c: protect string_get_size() against blk_size=0

In reply to Vitaly Kuznetsov
Quoted 13 lines · Vitaly Kuznetsov

Division by zero happens if blk_size=0 is supplied to string_get_size(). Add WARN_ON() and set size to 0 to report '0 B'.

---
 lib/string_helpers.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/string_helpers.c +0 -0
index f6c27dc..ff3575b 100644

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

Quoted 6 lines
lib/string_helpers.c +3 -0
@@ -50,6 +50,11 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 
 	tmp[0] = '\0';
 	i = 0;
+
+	/* Calling string_get_size() with blk_size=0 is wrong! */
+	if (WARN_ON(!blk_size))

Get rid of the WARN_ON; it's the standard thing to do for a partially connected device. Seeing zero is standard in a whole variety of situations. SCSI shims the zero but most other drivers don't.

James

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

#17 lore raw

Re: [PATCH v3 2/4] lib/string_helpers.c: protect string_get_size() against blk_size=0

Quoted 15 lines · James Bottomley
Quoted 14 lines · Vitaly Kuznetsov

Division by zero happens if blk_size=0 is supplied to string_get_size(). Add WARN_ON() and set size to 0 to report '0 B'.

---
 lib/string_helpers.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/string_helpers.c +0 -0
index f6c27dc..ff3575b 100644
@@ -50,6 +50,11 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 
Quoted 9 lines

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

Quoted 5 lines
lib/string_helpers.c +3 -0
      tmp[0] = '\0';
      i = 0;
+
+     /* Calling string_get_size() with blk_size=0 is wrong! */
+     if (WARN_ON(!blk_size))

Get rid of the WARN_ON; it's the standard thing to do for a partially connected device. Seeing zero is standard in a whole variety of situations. SCSI shims the zero but most other drivers don't.

For *block* size? It will crash the kernel. I've checked, it wasn't changed from the beginning (b9f28d863594).

+ exp = divisor[units] / (u32)blk_size;

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#18 lore raw

Re: [PATCH v3 2/4] lib/string_helpers.c: protect string_get_size() against blk_size=0

Quoted 26 lines · Andy Shevchenko
Quoted 15 lines · James Bottomley
Quoted 14 lines · Vitaly Kuznetsov

Division by zero happens if blk_size=0 is supplied to string_get_size(). Add WARN_ON() and set size to 0 to report '0 B'.

---
 lib/string_helpers.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/string_helpers.c +0 -0
index f6c27dc..ff3575b 100644
@@ -50,6 +50,11 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 
Quoted 9 lines

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

Quoted 5 lines
lib/string_helpers.c +3 -0
      tmp[0] = '\0';
      i = 0;
+
+     /* Calling string_get_size() with blk_size=0 is wrong! */
+     if (WARN_ON(!blk_size))

Get rid of the WARN_ON; it's the standard thing to do for a partially connected device. Seeing zero is standard in a whole variety of situations. SCSI shims the zero but most other drivers don't.

Quoted 2 lines

For *block* size? It will crash the kernel. I've checked, it wasn't changed from the beginning (b9f28d863594).

The standard signal for a drive error in capacity is zero size and zero block size. We have to take that case as standard without emitting scary warnings.

James

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

#19 lore raw

Re: [PATCH v3 2/4] lib/string_helpers.c: protect string_get_size() against blk_size=0

Quoted 27 lines · James Bottomley
Quoted 26 lines · Andy Shevchenko
Quoted 24 lines · James Bottomley
Quoted 13 lines · Vitaly Kuznetsov

Division by zero happens if blk_size=0 is supplied to string_get_size(). Add WARN_ON() and set size to 0 to report '0 B'.

---
 lib/string_helpers.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/string_helpers.c +0 -0
index f6c27dc..ff3575b 100644

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

Quoted 6 lines
lib/string_helpers.c +3 -0
@@ -50,6 +50,11 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 
      tmp[0] = '\0';
      i = 0;
+
+     /* Calling string_get_size() with blk_size=0 is wrong! */
+     if (WARN_ON(!blk_size))

Get rid of the WARN_ON; it's the standard thing to do for a partially connected device. Seeing zero is standard in a whole variety of situations. SCSI shims the zero but most other drivers don't.

Quoted 6 lines
Quoted 2 lines

For *block* size? It will crash the kernel. I've checked, it wasn't changed from the beginning (b9f28d863594).

The standard signal for a drive error in capacity is zero size and zero block size. We have to take that case as standard without emitting scary warnings.

Ok, but what if size != 0? Is WARN_ON() justified in this case?

Signature · 1 line
  Vitaly
#20 lore raw

Re: [PATCH v3 2/4] lib/string_helpers.c: protect string_get_size() against blk_size=0

Quoted 29 lines · Vitaly Kuznetsov
Quoted 27 lines · James Bottomley
Quoted 26 lines · Andy Shevchenko
Quoted 24 lines · James Bottomley
Quoted 13 lines · Vitaly Kuznetsov

Division by zero happens if blk_size=0 is supplied to string_get_size(). Add WARN_ON() and set size to 0 to report '0 B'.

---
 lib/string_helpers.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/string_helpers.c +0 -0
index f6c27dc..ff3575b 100644

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

Quoted 6 lines
lib/string_helpers.c +3 -0
@@ -50,6 +50,11 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 
      tmp[0] = '\0';
      i = 0;
+
+     /* Calling string_get_size() with blk_size=0 is wrong! */
+     if (WARN_ON(!blk_size))

Get rid of the WARN_ON; it's the standard thing to do for a partially connected device. Seeing zero is standard in a whole variety of situations. SCSI shims the zero but most other drivers don't.

Quoted 8 lines
Quoted 6 lines
Quoted 2 lines

For *block* size? It will crash the kernel. I've checked, it wasn't changed from the beginning (b9f28d863594).

The standard signal for a drive error in capacity is zero size and zero block size. We have to take that case as standard without emitting scary warnings.

Ok, but what if size != 0? Is WARN_ON() justified in this case?

It's an arithmentic routine whose job is to multiply two numbers, not second guess the subsystem that gave it the numbers. Just on general architectural principles the only time it's allowed to dump a stack trace without confusing people is when the arithmetic operation it has been asked to do would produce an illegal result (which for two sixty four bit numbers multiplying to a 128 bit one is never).

James

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

#21 lore raw

PATCH v3 3/4 lib/string_helpers.c: don't lose precision in string_get_size()

In reply to Vitaly Kuznetsov

string_get_size() loses precision when there is a remainder for blk_size / divisor[units] and size is big enough. E.g string_get_size(8192, 4096, STRING_UNITS_10, ...) returns "32.7 MB" while it is supposed to return "33.5 MB". For some artificial inputs the result can be ridiculously wrong, e.g. string_get_size(3000, 1900, STRING_UNITS_10, ...) returns "3.00 MB" when "5.70 MB" is expected.

The issues comes from the fact than we through away
blk_size / divisor[units] remainder when size is > exp. This can be fixed by saving it and doing some non-trivial calculations later to fix the error but that would make this function even more cumbersome. Slightly re-factor the function to not lose the precision for all inputs.

The overall complexity of this function comes from the fact that size can be huge and we don't want to do size * blk_size as it can overflow. Do the math in two steps:
1) Reduce size to something < U64_MAX / blk_size.
2) Multiply the result by blk_size and do final calculations.

---
Changes since v2:
- Reduce size to something < U64_MAX / blk_size as a first step instead of blk_size * divisor[units], remove fixup code [Rasmus Villemoes]
- Separate !blk_size check into a separate patch [Andy Shevchenko]

---
 lib/string_helpers.c | 31 ++++++++++++++-----------------
 1 file changed, 14 insertions(+), 17 deletions(-)
lib/string_helpers.c +14 -17
index ff3575b..29263c1 100644
@@ -44,7 +44,7 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 		[STRING_UNITS_2] = 1024,
 	};
 	int i, j;
-	u32 remainder = 0, sf_cap, exp;
+	u32 remainder = 0, sf_cap;
 	char tmp[8];
 	const char *unit;
 
@@ -58,27 +58,23 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 	if (!size)
 		goto out;
 
-	while (blk_size >= divisor[units]) {
-		remainder = do_div(blk_size, divisor[units]);
-		i++;
-	}
-
-	exp = divisor[units] / blk_size;
 	/*
-	 * size must be strictly greater than exp here to ensure that remainder
-	 * is greater than divisor[units] coming out of the if below.
+	 * size can be huge and doing size * blk_size right away can overflow.
+	 * As a first step reduce huge size to something less than
+	 * U64_MAX / blk_size.
 	 */
-	if (size > exp) {
-		remainder = do_div(size, divisor[units]);
-		remainder *= blk_size;
-		i++;
-	} else {
-		remainder *= size;
+	while (size > div_u64(U64_MAX, blk_size)) {
+		/*
+		 * We do not need to keep the remainder as blk_size is capped
+		 * by U32_MAX and we'll still have enough precision after the
+		 * loop.
+		 */
+		do_div(size, divisor[units]);
+		++i;
 	}
 
+	/* Now we're OK with doing size * blk_size, it won't overflow. */
 	size *= blk_size;
-	size += remainder / divisor[units];
-	remainder %= divisor[units];
 
 	while (size >= divisor[units]) {
 		remainder = do_div(size, divisor[units]);
@@ -102,6 +98,7 @@ void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
 	else
 		unit = units_str[units][i];
 
+	/* size is < divisor[units] here, (u32) is legit */
 	snprintf(buf, len, "%u%s %s", (u32)size,
 		 tmp, unit);
 }
Signature · 1 line
2.4.3
#22 lore raw

Re: [PATCH v3 3/4] lib/string_helpers.c: don't lose precision in string_get_size()

Quoted 14 lines · Vitaly Kuznetsov

string_get_size() loses precision when there is a remainder for blk_size / divisor[units] and size is big enough. E.g string_get_size(8192, 4096, STRING_UNITS_10, ...) returns "32.7 MB" while it is supposed to return "33.5 MB". For some artificial inputs the result can be ridiculously wrong, e.g. string_get_size(3000, 1900, STRING_UNITS_10, ...) returns "3.00 MB" when "5.70 MB" is expected.

The issues comes from the fact than we through away
blk_size / divisor[units] remainder when size is > exp. This can be fixed by saving it and doing some non-trivial calculations later to fix the error but that would make this function even more cumbersome. Slightly re-factor the function to not lose the precision for all inputs.

Quoted 8 lines

The overall complexity of this function comes from the fact that size can be huge and we don't want to do size * blk_size as it can overflow. Do the math in two steps:
1) Reduce size to something < U64_MAX / blk_size.
2) Multiply the result by blk_size and do final calculations.

One nitpick below.

Quoted 12 lines
        /*
lib/string_helpers.c +3 -7
-        * size must be strictly greater than exp here to ensure that remainder
-        * is greater than divisor[units] coming out of the if below.
+        * size can be huge and doing size * blk_size right away can overflow.
+        * As a first step reduce huge size to something less than
+        * U64_MAX / blk_size.
         */
-       if (size > exp) {
-               remainder = do_div(size, divisor[units]);
-               remainder *= blk_size;
-               i++;
-       } else {

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

Quoted 10 lines
lib/string_helpers.c +8 -1
-               remainder *= size;
+       while (size > div_u64(U64_MAX, blk_size)) {
+               /*
+                * We do not need to keep the remainder as blk_size is capped
+                * by U32_MAX and we'll still have enough precision after the
+                * loop.
+                */
+               do_div(size, divisor[units]);
 
+               ++i;

You may leave i++; here. Any reason not to do that?

Quoted 1 line
        }
Signature · 2 lines
With Best Regards,
Andy Shevchenko
#23 lore raw

PATCH v3 4/4 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().

---
 lib/test-string_helpers.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)
lib/test-string_helpers.c +58 -0
index 8e376ef..4c77b54 100644
@@ -326,6 +326,61 @@ out:
 	kfree(out_test);
 }
 
+#define string_get_size_maxbuf 16
+#define test_string_get_size_one(size, blk_size, exp_result10, exp_result2)    \
+	do {                                                                   \
+		BUILD_BUG_ON(sizeof(exp_result10) >= string_get_size_maxbuf);  \
+		BUILD_BUG_ON(sizeof(exp_result2) >= string_get_size_maxbuf);   \
+		__test_string_get_size((size), (blk_size), (exp_result10),     \
+				       (exp_result2));                         \
+	} while (0)
+
+
+static __init void __test_string_get_size(const u64 size, const u32 blk_size,
+					  const char *exp_result10,
+					  const char *exp_result2)
+{
+	char buf10[string_get_size_maxbuf];
+	char buf2[string_get_size_maxbuf];
+
+	string_get_size(size, blk_size, STRING_UNITS_10, buf10, sizeof(buf10));
+	string_get_size(size, blk_size, STRING_UNITS_2, buf2, sizeof(buf2));
+
+	if (!memcmp(buf10, exp_result10, strlen(exp_result10) + 1))
+		goto check_stringunits_2;
+
+	buf10[sizeof(buf10) - 1] = '\0';
+
+	pr_warn("Test 'test_string_get_size' failed!\n");
+	pr_warn("string_get_size(size = %llu, blk_size = %u, units = %s)\n",
+		size, blk_size, "STRING_UNITS_10");
+	pr_warn("expected: '%s', got '%s'\n", exp_result10, buf10);
+
+check_stringunits_2:
+	if (!memcmp(buf2, exp_result2, strlen(exp_result2) + 1))
+		return;
+
+	buf2[sizeof(buf2) - 1] = '\0';
+
+	pr_warn("Test 'test_string_get_size' failed!\n");
+	pr_warn("string_get_size(size = %llu, blk_size = %u, units = %s)\n",
+		size, blk_size, "STRING_UNITS_2");
+	pr_warn("expected: '%s', got '%s'\n", exp_result2, buf2);
+}
+
+static __init void test_string_get_size(void)
+{
+	test_string_get_size_one(16384, 512, "8.38 MB", "8.00 MiB");
+	test_string_get_size_one(500118192, 512, "256 GB", "238 GiB");
+	test_string_get_size_one(8192, 4096, "33.5 MB", "32.0 MiB");
+	test_string_get_size_one(1100, 1, "1.10 kB", "1.07 KiB");
+	test_string_get_size_one(3000, 1900, "5.70 MB", "5.43 MiB");
+	test_string_get_size_one(U64_MAX, 4096, "75.5 ZB", "63.9 ZiB");
+	test_string_get_size_one(1999, U32_MAX, "8.58 TB", "7.80 TiB");
+	test_string_get_size_one(1, 512, "512 B", "512 B");
+	test_string_get_size_one(0, 512, "0 B", "0 B");
+}
+
 static int __init test_string_helpers_init(void)
 {
 	unsigned int i;
@@ -344,6 +399,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
#24 lore raw

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

Quoted 35 lines · Vitaly Kuznetsov

Add a couple of simple tests for string_get_size().

---
 lib/test-string_helpers.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)
lib/test-string_helpers.c +20 -0
index 8e376ef..4c77b54 100644
@@ -326,6 +326,61 @@ out:
        kfree(out_test);
 }
 
+#define string_get_size_maxbuf 16
+#define test_string_get_size_one(size, blk_size, exp_result10, exp_result2)    \
+       do {                                                                   \
+               BUILD_BUG_ON(sizeof(exp_result10) >= string_get_size_maxbuf);  \
+               BUILD_BUG_ON(sizeof(exp_result2) >= string_get_size_maxbuf);   \
+               __test_string_get_size((size), (blk_size), (exp_result10),     \
+                                      (exp_result2));                         \
+       } while (0)
+
+
+static __init void __test_string_get_size(const u64 size, const u32 blk_size,
+                                         const char *exp_result10,
+                                         const char *exp_result2)
+{
+       char buf10[string_get_size_maxbuf];
+       char buf2[string_get_size_maxbuf];
+
+       string_get_size(size, blk_size, STRING_UNITS_10, buf10, sizeof(buf10));
+       string_get_size(size, blk_size, STRING_UNITS_2, buf2, sizeof(buf2));
+

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

Quoted 10 lines
lib/test-string_helpers.c +9 -0
+       if (!memcmp(buf10, exp_result10, strlen(exp_result10) + 1))
+               goto check_stringunits_2;
+
 
+       buf10[sizeof(buf10) - 1] = '\0';
+
+       pr_warn("Test 'test_string_get_size' failed!\n");
+       pr_warn("string_get_size(size = %llu, blk_size = %u, units = %s)\n",
+               size, blk_size, "STRING_UNITS_10");
+       pr_warn("expected: '%s', got '%s'\n", exp_result10, buf10);

Looks to me as a helper function

test_string_get_size_pr_err(size, blk_size, units, exp_result, buf, buflen) {}

if (memcmp(buf10, exp_result10, strlen(exp_result10) + 1))
_pr_err(...);

Quoted 48 lines
lib/test-string_helpers.c +26 -0
+
+check_stringunits_2:
+       if (!memcmp(buf2, exp_result2, strlen(exp_result2) + 1))
+               return;
+
+       buf2[sizeof(buf2) - 1] = '\0';
+
+       pr_warn("Test 'test_string_get_size' failed!\n");
+       pr_warn("string_get_size(size = %llu, blk_size = %u, units = %s)\n",
+               size, blk_size, "STRING_UNITS_2");
+       pr_warn("expected: '%s', got '%s'\n", exp_result2, buf2);
+}
+
+static __init void test_string_get_size(void)
+{
+       test_string_get_size_one(16384, 512, "8.38 MB", "8.00 MiB");
+       test_string_get_size_one(500118192, 512, "256 GB", "238 GiB");
+       test_string_get_size_one(8192, 4096, "33.5 MB", "32.0 MiB");
+       test_string_get_size_one(1100, 1, "1.10 kB", "1.07 KiB");
+       test_string_get_size_one(3000, 1900, "5.70 MB", "5.43 MiB");
+       test_string_get_size_one(U64_MAX, 4096, "75.5 ZB", "63.9 ZiB");
+       test_string_get_size_one(1999, U32_MAX, "8.58 TB", "7.80 TiB");
+       test_string_get_size_one(1, 512, "512 B", "512 B");
+       test_string_get_size_one(0, 512, "0 B", "0 B");
 
+}
+
 static int __init test_string_helpers_init(void)
 {
        unsigned int i;
lib/test-string_helpers.c +3 -1
@@ -344,6 +399,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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 2 lines
With Best Regards,
Andy Shevchenko