linux/kernel.h: Fix DIV_ROUND_CLOSEST with unsigned divisors
PATCH v2 1/1 linux/kernel.h: Fix DIV_ROUND_CLOSEST with unsigned divisors
Commit 263a523 fixes a warning seen with W=1 due to change in DIV_ROUND_CLOSEST. Unfortunately, the C compiler converts divide operations with unsigned divisors to unsigned, even if the dividend is signed and negative (for example, -10 / 5U = 858993457). The C standard says "If one operand has unsigned int type, the other operand is converted to unsigned int", so the compiler is not to blame.
As a result, DIV_ROUND_CLOSEST(0, 2U) and similar operations now return bad values, since the automatic conversion of expressions such as "0 - 2U/2" to unsigned was not taken into account.
Fix by checking for the divisor variable type when deciding which operation to perform. This fixes DIV_ROUND_CLOSEST(0, 2U), but still returns bad values for negative dividends divided by unsigned divisors. Mark the latter case as unsupported.
---
v2: Description update (v1 wasn't supposed to make it to lkml)
include/linux/kernel.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
include/linux/kernel.h +4 -2
@@ -77,13 +77,15 @@/* * Divide positive or negative dividend by positive divisor and round -* to closest integer. Result is undefined for negative divisors. +* to closest integer. Result is undefined for negative divisors and +* for negative dividends if the divisor variable type is unsigned. */ #define DIV_ROUND_CLOSEST (x, divisor)( \ { \ typeof(x) __x = x; \ typeof(divisor) __d = divisor; \ - (((typeof(x))-1) > 0 || (__x) > 0) ? \ + (((typeof(x))-1) > 0 || \ + ((typeof(divisor))-1) > 0 || (__x) > 0) ? \ (((__x) + ((__d) / 2)) / (__d)) : \ (((__x) - ((__d) / 2)) / (__d)); \ } \
Signature · 7 lines
1.7.9.7 _______________________________________________ lm-sensors mailing list [email protected] http://lists.lm-sensors.org/mailman/listinfo/lm-sensors
Quoted 10 lines · On Wed, 19 Dec 2012 06:40:15 -0800 Guenter Roeck <[email protected]> wrote:
Commit 263a523 fixes a warning seen with W=1 due to change in
DIV_ROUND_CLOSEST. Unfortunately, the C compiler converts divide operations with unsigned divisors to unsigned, even if the dividend is signed and negative (for example, -10 / 5U = 858993457). The C standard says "If one operand has unsigned int type, the other operand is converted to unsigned int", so the compiler is not to blame.
As a result,DIV_ROUND_CLOSEST(0, 2U)and similar operations now return bad values, since the automatic conversion of expressions such as "0 - 2U/2" to unsigned was not taken into account.
Quoted 4 lines
Fix by checking for the divisor variable type when deciding which operation to perform. This fixes
DIV_ROUND_CLOSEST(0, 2U), but still returns bad values for negative dividends divided by unsigned divisors. Mark the latter case as unsupported.
The changelog didn't describe the end-user visible effects of the bug. Please always include this information. Because...
The patch is applicable to 3.7.x. Should we backport it?
_______________________________________________
lm-sensors mailing list
[email protected]
http://lists.lm-sensors.org/mailman/listinfo/lm-sensors
Quoted 13 lines · Andrew Morton
Quoted 10 lines · On Wed, 19 Dec 2012 06:40:15 -0800 Guenter Roeck <[email protected]> wrote:
Commit 263a523 fixes a warning seen with W=1 due to change in
DIV_ROUND_CLOSEST. Unfortunately, the C compiler converts divide operations with unsigned divisors to unsigned, even if the dividend is signed and negative (for example, -10 / 5U = 858993457). The C standard says "If one operand has unsigned int type, the other operand is converted to unsigned int", so the compiler is not to blame.
As a result,DIV_ROUND_CLOSEST(0, 2U)and similar operations now return bad values, since the automatic conversion of expressions such as "0 - 2U/2" to unsigned was not taken into account.
Quoted 8 lines
Quoted 4 lines
Fix by checking for the divisor variable type when deciding which operation to perform. This fixes
DIV_ROUND_CLOSEST(0, 2U), but still returns bad values for negative dividends divided by unsigned divisors. Mark the latter case as unsupported.The changelog didn't describe the end-user visible effects of the bug. Please always include this information. Because...
One observed effect is that the s2c_hwmon driver reports a value of 4198403 instead of 0 if the ADC reads 0.
Other impact is unpredictable. Problem is seen if the divisor is an unsigned variable or constant and the dividend is less than (divisor/2).
Quoted 2 lines
The patch is applicable to 3.7.x. Should we backport it?
Yes. DIV_ROUND_CLOSEST is used throughout the kernel, and impact is unpredictable.
3.6 needs it as well.
Hi Guenter,
Quoted 9 lines · Guenter Roeck
Quoted 2 lines · Andrew Morton
The changelog didn't describe the end-user visible effects of the bug. Please always include this information. Because...
One observed effect is that the
s2c_hwmondriver reports a value of 4198403 instead of 0 if the ADC reads 0.Other impact is unpredictable. Problem is seen if the divisor is an unsigned variable or constant and the dividend is less than (divisor/2).
Really? In my own testing, the problem only shows with dividend = 0, and even then, only when dividend is signed and divisor is not. DIV_ROUND_CLOSEST(5, 20U) returns 0 as expected, and so do DIV_ROUND_CLOSEST(0 / 20), DIV_ROUND_CLOSEST(0U / 20) and DIV_ROUND_CLOSEST(0U / 20U).
Are your observations different?
Quoted 6 lines
Quoted 1 line
The patch is applicable to 3.7.x. Should we backport it?
Yes.
DIV_ROUND_CLOSESTis used throughout the kernel, and impact is unpredictable.3.6 needs it as well.
Signature · 6 lines
Jean Delvare _______________________________________________ lm-sensors mailing list [email protected] http://lists.lm-sensors.org/mailman/listinfo/lm-sensors
Hi Jean,
Quoted 11 lines · Jean Delvare
Quoted 9 lines · Guenter Roeck
Quoted 2 lines · Andrew Morton
The changelog didn't describe the end-user visible effects of the bug. Please always include this information. Because...
One observed effect is that the
s2c_hwmondriver reports a value of 4198403 instead of 0 if the ADC reads 0.Other impact is unpredictable. Problem is seen if the divisor is an unsigned variable or constant and the dividend is less than (divisor/2).
Quoted 7 lines
Really? In my own testing, the problem only shows with dividend = 0, and even then, only when dividend is signed and divisor is not.
DIV_ROUND_CLOSEST(5, 20U)returns 0 as expected, and so doDIV_ROUND_CLOSEST(0 / 20),DIV_ROUND_CLOSEST(0U / 20)andDIV_ROUND_CLOSEST(0U / 20U).Are your observations different?
I tried it with this simple user-land program to get an idea what's going wrong in the s3c_hwmon.c ADC driver:
#define DIV_ROUND_CLOSEST(x, divisor)( \
{ \
typeof(x) __x = x; \
typeof(divisor) __d = divisor; \
(((typeof(x))-1) > 0 || (__x) > 0) ? \
(((__x) + ((__d) / 2)) / (__d)) : \
(((__x) - ((__d) / 2)) / (__d)); \
} \)
int main(int argc, char *argv[])
{
int x;
unsigned y;
printf("Constants\n");
printf("-1 -> %d\n", DIV_ROUND_CLOSEST(-1, 2));
printf("-1 -> %d\n", DIV_ROUND_CLOSEST(-1, 1023));
printf("0 -> %d\n", DIV_ROUND_CLOSEST(0, 1023));
printf("0 -> %d\n", DIV_ROUND_CLOSEST(0, 2));
printf("1 -> %d\n", DIV_ROUND_CLOSEST(1, 2));
printf("1 -> %d\n", DIV_ROUND_CLOSEST(3300, 1023));
printf("2 -> %d\n", DIV_ROUND_CLOSEST(6600, 1023));
printf("Variables\n");
x = -1; y = 2;
printf("-1 -> %d\n", DIV_ROUND_CLOSEST(x, y));
x = -1; y = 1023;
printf("-1 -> %d\n", DIV_ROUND_CLOSEST(x, y));
x = 0; y = 1023;
printf("0 -> %d\n", DIV_ROUND_CLOSEST(x, y));
x = 3300; y = 1023;
printf("3300 -> %d\n", DIV_ROUND_CLOSEST(3300, 1023));
x = 6600; y = 1023;
printf("6600 -> %d\n", DIV_ROUND_CLOSEST(6600, 1023));
return 0;
}Result is on my x86 host (same on my ARM target):
Constants
-1 -> -1
-1 -> 0
0 -> 0
0 -> 0
1 -> 1
1 -> 3
2 -> 6
Variables
-1 -> 2147483647
-1 -> 4198403
0 -> 4198403
3300 -> 3
6600 -> 6
Regards,
Juergen
Signature · 7 lines
Pengutronix e.K. | Juergen Beisert | Linux Solutions for Science and Industry | http://www.pengutronix.de/ | _______________________________________________ lm-sensors mailing list [email protected] http://lists.lm-sensors.org/mailman/listinfo/lm-sensors
Hi Juergen,
Quoted 32 lines · Juergen Beisert
Hi Jean,
Quoted 7 lines · Jean Delvare
Quoted 5 lines · Guenter Roeck
One observed effect is that the
s2c_hwmondriver reports a value of 4198403 instead of 0 if the ADC reads 0.Other impact is unpredictable. Problem is seen if the divisor is an unsigned variable or constant and the dividend is less than (divisor/2).
Quoted 7 lines
Really? In my own testing, the problem only shows with dividend = 0, and even then, only when dividend is signed and divisor is not.
DIV_ROUND_CLOSEST(5, 20U)returns 0 as expected, and so doDIV_ROUND_CLOSEST(0 / 20),DIV_ROUND_CLOSEST(0U / 20)andDIV_ROUND_CLOSEST(0U / 20U).Are your observations different?
I tried it with this simple user-land program to get an idea what's going wrong in the
s3c_hwmon.cADC driver:#define
DIV_ROUND_CLOSEST(x, divisor)( \{ \ typeof(x) __x = x; \ typeof(divisor) __d = divisor; \ (((typeof(x))-1) > 0 || (__x) > 0) ? \ (((__x) + ((__d) / 2)) / (__d)) : \ (((__x) - ((__d) / 2)) / (__d)); \ } \)
int
main(int argc, char *argv[])
Quoted 13 lines
{
int x;
unsigned y;
printf("Constants\n");
printf("-1 -> %d\n", DIV_ROUND_CLOSEST(-1, 2));
printf("-1 -> %d\n", DIV_ROUND_CLOSEST(-1, 1023));
printf("0 -> %d\n", DIV_ROUND_CLOSEST(0, 1023));
printf("0 -> %d\n", DIV_ROUND_CLOSEST(0, 2));
printf("1 -> %d\n", DIV_ROUND_CLOSEST(1, 2));
printf("1 -> %d\n", DIV_ROUND_CLOSEST(3300, 1023));
printf("2 -> %d\n", DIV_ROUND_CLOSEST(6600, 1023));This all works properly, because everything is signed here.
Quoted 4 lines
printf("Variables\n");
x = -1; y = 2;
printf("-1 -> %d\n", DIV_ROUND_CLOSEST(x, y));Quoted 8 lines
x = -1; y = 1023;
printf("-1 -> %d\n", DIV_ROUND_CLOSEST(x, y));
x = 0; y = 1023;
printf("0 -> %d\n", DIV_ROUND_CLOSEST(x, y));
x = 3300; y = 1023;
printf("3300 -> %d\n", DIV_ROUND_CLOSEST(3300, 1023));
x = 6600; y = 1023;
printf("6600 -> %d\n", DIV_ROUND_CLOSEST(6600, 1023));I don't think variables vs. constants make any difference. What makes a difference is signed vs. unsigned. You see failures here because y is unsigned. You'd see the same with the constants above by changing 2 to 2U and 1023 to 1023U.
Quoted 6 lines
return 0; }Result is on my x86 host (same on my ARM target):
Quoted 14 lines
Constants
-1 -> -1
-1 -> 0
0 -> 0
0 -> 0
1 -> 1
1 -> 3
2 -> 6
Variables
-1 -> 2147483647
-1 -> 4198403
0 -> 4198403
3300 -> 3
6600 -> 6
I see the same here with your test program.
Signature · 6 lines
Jean Delvare _______________________________________________ lm-sensors mailing list [email protected] http://lists.lm-sensors.org/mailman/listinfo/lm-sensors
Quoted 13 lines · Jean Delvare
Hi Guenter,
Quoted 9 lines · Guenter Roeck
Quoted 2 lines · Andrew Morton
The changelog didn't describe the end-user visible effects of the bug. Please always include this information. Because...
One observed effect is that the
s2c_hwmondriver reports a value of 4198403 instead of 0 if the ADC reads 0.Other impact is unpredictable. Problem is seen if the divisor is an unsigned variable or constant and the dividend is less than (divisor/2).
Quoted 7 lines
Really? In my own testing, the problem only shows with dividend == 0, and even then, only when dividend is signed and divisor is not.
DIV_ROUND_CLOSEST(5, 20U)returns 0 as expected, and so doDIV_ROUND_CLOSEST(0 / 20),DIV_ROUND_CLOSEST(0U / 20)andDIV_ROUND_CLOSEST(0U / 20U).Are your observations different?
Hmm, you are right - it only happens with 0. I thought I had also seen it with other values.
Quoted 7 lines
Quoted 6 lines
Quoted 1 line
The patch is applicable to 3.7.x. Should we backport it?
Yes.
DIV_ROUND_CLOSESTis used throughout the kernel, and impact is unpredictable.3.6 needs it as well.
Turns out 3.6 is EOL, so we'll only need it in 3.7.
Guenter
Hi Guenter,
Quoted 6 lines · Guenter Roeck
Commit 263a523 fixes a warning seen with W=1 due to change in
DIV_ROUND_CLOSEST. Unfortunately, the C compiler converts divide operations with unsigned divisors to unsigned, even if the dividend is signed and negative (for example, -10 / 5U = 858993457). The C standard says "If one operand has unsigned int type, the other operand is converted to unsigned int", so the compiler is not to blame.
This is surprising to say the least. But if the C standard says so...
I wouldn't be surprised if there are bugs because of this in the kernel and in other projects.
Quoted 8 lines
As a result,
DIV_ROUND_CLOSEST(0, 2U)and similar operations now return bad values, since the automatic conversion of expressions such as "0 - 2U/2" to unsigned was not taken into account.Fix by checking for the divisor variable type when deciding which operation to perform. This fixes
DIV_ROUND_CLOSEST(0, 2U), but still returns bad values for negative dividends divided by unsigned divisors. Mark the latter case as unsupported.
True but this last issue isn't specific to the DIV_ROUND_CLOSEST implementation, it would also happen with a simple division.
Quoted 15 lines
Reported-by Juergen Beisert <[email protected]>Tested-by Juergen Beisert <[email protected]>Cc Jean Delvare <[email protected]>Signed-off-by Guenter Roeck <[email protected]>---
v2: Description update (v1 wasn't supposed to make it to lkml)include/linux/kernel.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)include/linux/kernel.h +0
-0
include/linux/kernel.h line 81
Quoted 6 lines
include/linux/kernel.h +2
-1@@ -77,13 +77,15 @@/* * Divide positive or negative dividend by positive divisor and round -* to closest integer. Result is undefined for negative divisors. +* to closest integer. Result is undefined for negative divisors and +* for negative dividends if the divisor variable type is unsigned.
Thinking a bit more about this... Documenting the non-working cases is great, however I don't really expect all developers to pay attention. I can also imagine variable types changing from signed to unsigned later, and never thinking this can introduce a bug.
So, is there nothing we can do to spot at least the second issue at build time? For regular division there's nothing we can do (although I don't understand why gcc doesn't warn...) but here we get the opportunity to report the issue, let's take it.
And given that the divisor is almost always a constant, maybe we can check for negative divisors too, this would be safer and the code size increase would probably be very small in practice. Opinions?
include/linux/kernel.h line 91
Quoted 11 lines
include/linux/kernel.h +2
-1*/ #define DIV_ROUND_CLOSEST (x, divisor)( \ { \ typeof(x) __x = x; \ typeof(divisor) __d = divisor; \ - (((typeof(x))-1) > 0 || (__x) > 0) ? \ + (((typeof(x))-1) > 0 || \ + ((typeof(divisor))-1) > 0 || (__x) > 0) ? \ (((__x) + ((__d) / 2)) / (__d)) : \ (((__x) - ((__d) / 2)) / (__d)); \ } \
Looks good.
Signature · 6 lines
Jean Delvare _______________________________________________ lm-sensors mailing list [email protected] http://lists.lm-sensors.org/mailman/listinfo/lm-sensors
Quoted 12 lines · Jean Delvare
Hi Guenter,
Quoted 6 lines · Guenter Roeck
Commit 263a523 fixes a warning seen with W=1 due to change in
DIV_ROUND_CLOSEST. Unfortunately, the C compiler converts divide operations with unsigned divisors to unsigned, even if the dividend is signed and negative (for example, -10 / 5U = 858993457). The C standard says "If one operand has unsigned int type, the other operand is converted to unsigned int", so the compiler is not to blame.This is surprising to say the least. But if the C standard says so...
Agreed, but it is how it is.
Quoted 3 lines
I wouldn't be surprised if there are bugs because of this in the kernel and in other projects.
Might easily be. This might make a good interview question - I suspect many if not most engineers would fail it. At least I would have until yesterday :).
Quoted 4 lines
Quoted 4 lines
As a result,
DIV_ROUND_CLOSEST(0, 2U)and similar operations now return bad values, since the automatic conversion of expressions such as "0 - 2U/2" to unsigned was not taken into account.
Quoted 8 lines
Quoted 4 lines
Fix by checking for the divisor variable type when deciding which operation to perform. This fixes
DIV_ROUND_CLOSEST(0, 2U), but still returns bad values for negative dividends divided by unsigned divisors. Mark the latter case as unsupported.True but this last issue isn't specific to the
DIV_ROUND_CLOSESTimplementation, it would also happen with a simple division.
Correct, which is why I did not try to fix it. Still worth mentioning, though, in my opinion.
Quoted 32 lines
Quoted 15 lines
Reported-by Juergen Beisert <[email protected]>Tested-by Juergen Beisert <[email protected]>Cc Jean Delvare <[email protected]>Signed-off-by Guenter Roeck <[email protected]>---
v2: Description update (v1 wasn't supposed to make it to lkml)include/linux/kernel.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)include/linux/kernel.h +0
-0include/linux/kernel.h line 81
Quoted 6 lines
include/linux/kernel.h +2
-1@@ -77,13 +77,15 @@/* * Divide positive or negative dividend by positive divisor and round -* to closest integer. Result is undefined for negative divisors. +* to closest integer. Result is undefined for negative divisors and +* for negative dividends if the divisor variable type is unsigned. Thinking a bit more about this... Documenting the non-working cases is great, however I don't really expect all developers to pay attention. I can also imagine variable types changing from signed to unsigned later, and never thinking this can introduce a bug.
So, is there nothing we can do to spot at least the second issue at build time? For regular division there's nothing we can do (although I don't understand why gcc doesn't warn...) but here we get the opportunity to report the issue, let's take it.
Quoted 5 lines
And given that the divisor is almost always a constant, maybe we can check for negative divisors too, this would be safer and the code size increase would probably be very small in practice. Opinions?
Agreed, though we should fix the problem now and think about reporting afterwards.
Guenter
Quoted 17 lines
include/linux/kernel.h line 91
Quoted 11 lines
include/linux/kernel.h +2
-1*/ #define DIV_ROUND_CLOSEST (x, divisor)( \ { \ typeof(x) __x = x; \ typeof(divisor) __d = divisor; \ - (((typeof(x))-1) > 0 || (__x) > 0) ? \ + (((typeof(x))-1) > 0 || \ + ((typeof(divisor))-1) > 0 || (__x) > 0) ? \ (((__x) + ((__d) / 2)) / (__d)) : \ (((__x) - ((__d) / 2)) / (__d)); \ } \Looks good.
Signature · 1 line
Jean Delvare
Quoted 13 lines · Guenter Roeck
Quoted 11 lines · Jean Delvare
Hi Guenter,
Quoted 6 lines · Guenter Roeck
Commit 263a523 fixes a warning seen with W=1 due to change in
DIV_ROUND_CLOSEST. Unfortunately, the C compiler converts divide operations with unsigned divisors to unsigned, even if the dividend is signed and negative (for example, -10 / 5U = 858993457). The C standard says "If one operand has unsigned int type, the other operand is converted to unsigned int", so the compiler is not to blame.This is surprising to say the least. But if the C standard says so...
Quoted 7 lines
Agreed, but it is how it is.
Quoted 2 lines
I wouldn't be surprised if there are bugs because of this in the kernel and in other projects.
Might easily be. This might make a good interview question - I suspect many if not most engineers would fail it. At least I would have until yesterday :).
Neither did I. And I'm not sure I'll remember it in one year from now.
Quoted 11 lines
Quoted 11 lines
(...)
Thinking a bit more about this... Documenting the non-working cases is great, however I don't really expect all developers to pay attention. I can also imagine variable types changing from signed to unsigned later, and never thinking this can introduce a bug.So, is there nothing we can do to spot at least the second issue at build time? For regular division there's nothing we can do (although I don't understand why gcc doesn't warn...) but here we get the opportunity to report the issue, let's take it.
Quoted 7 lines
Quoted 4 lines
And given that the divisor is almost always a constant, maybe we can check for negative divisors too, this would be safer and the code size increase would probably be very small in practice. Opinions?
Agreed, though we should fix the problem now and think about reporting afterwards.
Yes, that's a good plan.
Signature · 6 lines
Jean Delvare _______________________________________________ lm-sensors mailing list [email protected] http://lists.lm-sensors.org/mailman/listinfo/lm-sensors