Avoid undefined behavior from signed overflow
PATCH 1/1 Avoid undefined behavior from signed overflow
According to the C standard 3.4.3p3, overflow of a signed integer results in undefined behavior. This commit therefore changes the definitions of time_after() and time_after_eq() to avoid this undefined behavior. The trick is that the subtraction is done using unsigned arithmetic, which according to 6.2.5p9 cannot overflow because it is defined as modulo arithmetic. This has the added (though admittedly quite small) benefit of shortening two lines of code by four characters each.
Note that the C standard considers the cast from signed to unsigned to be implementation-defined, see 6.3.1.3p3. However, on a two-complement system, an implementation that defines anything other than a reinterpretation of the bits is free come to me, and I will be happy to act as a witness for its being committed to an insane asylum. (Although I have nothing against saturating arithmetic or signals in some cases, these things really should not be the default.)
include/linux/jiffies.h +2 -2
@@ -101,13 +101,13 @@ static inline u64 get_jiffies_64(void)#define time_after (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(b) - (long)(a) < 0)) + ((long)((b) - (a)) < 0))#define time_before (a,b) time_after(b,a)#define time_after_eq (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(a) - (long)(b) >= 0)) + ((long)((a) - (b)) >= 0))#define time_before_eq (a,b) time_after_eq(b,a)/*
Quoted 32 lines · Paul E. McKenney
According to the C standard 3.4.3p3, overflow of a signed integer results in undefined behavior. This commit therefore changes the definitions of
time_after()andtime_after_eq()to avoid this undefined behavior. The trick is that the subtraction is done using unsigned arithmetic, which according to 6.2.5p9 cannot overflow because it is defined as modulo arithmetic. This has the added (though admittedly quite small) benefit of shortening two lines of code by four characters each.Note that the C standard considers the cast from signed to unsigned to be implementation-defined, see 6.3.1.3p3. However, on a two-complement system, an implementation that defines anything other than a reinterpretation of the bits is free come to me, and I will be happy to act as a witness for its being committed to an insane asylum. (Although I have nothing against saturating arithmetic or signals in some cases, these things really should not be the default.)
Signed-off-by Paul E. McKenney <[email protected]>Cc John Stultz <[email protected]>Cc "David S. Miller" <[email protected]>Cc Arnd Bergmann <[email protected]>Cc Ingo Molnar <[email protected]>Cc Linus Torvalds <[email protected]>include/linux/jiffies.h +0
-1@@ -101,13 +101,13 @@ static inline u64 get_jiffies_64(void)#define time_after (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(b) - (long)(a) < 0))
include/linux/jiffies.h static inline u64 get_jiffies_64(void) · line 112
Quoted 10 lines
include/linux/jiffies.h +2
-1+ ((long)((b) - (a)) < 0))#define time_before (a,b) time_after(b,a)#define time_after_eq (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(a) - (long)(b) >= 0)) + ((long)((a) - (b)) >= 0))#define time_before_eq (a,b) time_after_eq(b,a)
time_after64() & time_after_eq64() probably need the same.
Quoted 36 lines · Eric Dumazet
Quoted 35 lines · Paul E. McKenney
According to the C standard 3.4.3p3, overflow of a signed integer results in undefined behavior. This commit therefore changes the definitions of
time_after()andtime_after_eq()to avoid this undefined behavior. The trick is that the subtraction is done using unsigned arithmetic, which according to 6.2.5p9 cannot overflow because it is defined as modulo arithmetic. This has the added (though admittedly quite small) benefit of shortening two lines of code by four characters each.Note that the C standard considers the cast from signed to unsigned to be implementation-defined, see 6.3.1.3p3. However, on a two-complement system, an implementation that defines anything other than a reinterpretation of the bits is free come to me, and I will be happy to act as a witness for its being committed to an insane asylum. (Although I have nothing against saturating arithmetic or signals in some cases, these things really should not be the default.)
Signed-off-by Paul E. McKenney <[email protected]>Cc John Stultz <[email protected]>Cc "David S. Miller" <[email protected]>Cc Arnd Bergmann <[email protected]>Cc Ingo Molnar <[email protected]>Cc Linus Torvalds <[email protected]>include/linux/jiffies.h +1
-1@@ -101,13 +101,13 @@ static inline u64 get_jiffies_64(void)#define time_after (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(b) - (long)(a) < 0)) + ((long)((b) - (a)) < 0))#define time_before (a,b) time_after(b,a)
Quoted 8 lines
include/linux/jiffies.h static inline u64 get_jiffies_64(void) · line 111
Quoted 6 lines
include/linux/jiffies.h +1
-1#define time_after_eq (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(a) - (long)(b) >= 0)) + ((long)((a) - (b)) >= 0))#define time_before_eq (a,b) time_after_eq(b,a)
time_after64()&time_after_eq64()probably need the same.
It looks that way to me, too, good catch! Updated patch below.
Thanx, Paul
------------------------------------------------------------------------
jiffies: Avoid undefined behavior from signed overflow
According to the C standard 3.4.3p3, overflow of a signed integer results in undefined behavior. This commit therefore changes the definitions of time_after(), time_after_eq(), time_after64(), and time_after_eq64() to avoid this undefined behavior. The trick is that the subtraction is done using unsigned arithmetic, which according to 6.2.5p9 cannot overflow because it is defined as modulo arithmetic. This has the added (though admittedly quite small) benefit of shortening two lines of code by four characters each.
Note that the C standard considers the cast from signed to unsigned to be implementation-defined, see 6.3.1.3p3. However, on a two-complement system, an implementation that defines anything other than a reinterpretation of the bits is free come to me, and I will be happy to act as a witness for its being committed to an insane asylum. (Although I have nothing against saturating arithmetic or signals in some cases, these things really should not be the default.)
[ paulmck: Included time_after64() and time_after_eq64(), as suggested
by Eric Dumazet.]
include/linux/jiffies.h +4 -4
@@ -101,13 +101,13 @@ static inline u64 get_jiffies_64(void)#define time_after (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(b) - (long)(a) < 0)) + ((long)((b) - (a)) < 0))#define time_before (a,b) time_after(b,a)#define time_after_eq (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(a) - (long)(b) >= 0)) + ((long)((a) - (b)) >= 0))#define time_before_eq (a,b) time_after_eq(b,a)/*
@@ -130,13 +130,13 @@ static inline u64 get_jiffies_64(void)#define time_after64 (a,b) \ (typecheck(__u64, a) && \ typecheck(__u64, b) && \ - ((__s64)(b) - (__s64)(a) < 0)) + ((__s64)((b) - (a)) < 0))#define time_before64 (a,b) time_after64(b,a)#define time_after_eq64 (a,b) \ (typecheck(__u64, a) && \ typecheck(__u64, b) && \ - ((__s64)(a) - (__s64)(b) >= 0)) + ((__s64)((a) - (b)) >= 0))#define time_before_eq64 (a,b) time_after_eq64(b,a)#define time_in_range64 (a, b, c) \
Quoting "Paul E. McKenney" <[email protected]>:
Quoted 8 lines
According to the C standard 3.4.3p3, overflow of a signed integer results in undefined behavior. This commit therefore changes the definitions of
time_after()andtime_after_eq()to avoid this undefined behavior. The trick is that the subtraction is done using unsigned arithmetic, which according to 6.2.5p9 cannot overflow because it is defined as modulo arithmetic. This has the added (though admittedly quite small) benefit of shortening two lines of code by four characters each.
Quoted 7 lines
Note that the C standard considers the cast from signed to unsigned to be implementation-defined, see 6.3.1.3p3. However, on a two-complement system, an implementation that defines anything other than a reinterpretation of the bits is free come to me, and I will be happy to act as a witness for its being committed to an insane asylum. (Although I have nothing against saturating arithmetic or signals in some cases, these things really should not be the default.)
Don't worry, the case from signed to unsigned is actually well-defined - the relevant part is 6.3.1.3p2 (in C99):
Quoted 4 lines
Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.
...which ends up just being reinterpretation of the bits on a two's complement system, as you'd hope (after sign-extension to the width of the target unsigned type, that is). This actually means if you were mad enough to implement C on a sign-magnitude system, you'd be forced to do a non-trivial conversion in this case.
- Kevin
----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.
Quoted 18 lines · On Mon, Jul 29, 2013 at 03:30:35PM +1000, [email protected] wrote:
Quoting "Paul E. McKenney" <[email protected]>:
Quoted 8 lines
According to the C standard 3.4.3p3, overflow of a signed integer results in undefined behavior. This commit therefore changes the definitions of
time_after()andtime_after_eq()to avoid this undefined behavior. The trick is that the subtraction is done using unsigned arithmetic, which according to 6.2.5p9 cannot overflow because it is defined as modulo arithmetic. This has the added (though admittedly quite small) benefit of shortening two lines of code by four characters each.Quoted 7 lines
Note that the C standard considers the cast from signed to unsigned to be implementation-defined, see 6.3.1.3p3. However, on a two-complement system, an implementation that defines anything other than a reinterpretation of the bits is free come to me, and I will be happy to act as a witness for its being committed to an insane asylum. (Although I have nothing against saturating arithmetic or signals in some cases, these things really should not be the default.)
Quoted 7 lines
Don't worry, the case from signed to unsigned is actually well-defined - the relevant part is 6.3.1.3p2 (in C99):
Quoted 4 lines
Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.
Yep, but we are going in the other direction, from unsigned to signed.
Quoted 5 lines
...which ends up just being reinterpretation of the bits on a two's complement system, as you'd hope (after sign-extension to the width of the target unsigned type, that is). This actually means if you were mad enough to implement C on a sign-magnitude system, you'd be forced to do a non-trivial conversion in this case.
Fortunately, I never used signed-magnitude systems. And even when I used ones-complement systems back in my misguided youth, I didn't write C programs for them. ;-)
Thanx, Paul
Quoting "Paul E. McKenney" <[email protected]>:
Quoted 3 lines · On Mon, Jul 29, 2013 at 03:30:35PM +1000, [email protected] wrote:
Quoted 2 lines
Quoting "Paul E. McKenney" <[email protected]>:
...
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Note that the C standard considers the cast from signed to unsigned to be implementation-defined, see 6.3.1.3p3.
...
Quoted 10 lines
Quoted 8 lines
Don't worry, the case from signed to unsigned is actually well-defined - the relevant part is 6.3.1.3p2 (in C99):
Quoted 4 lines
Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.
Yep, but we are going in the other direction, from unsigned to signed.
Ahh, there's an error in the commit message (it says signed to unsigned).
- Kevin
----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.
Quoted 14 lines · Kevin Easton
Quoting "Paul E. McKenney" <[email protected]>:
Quoted 3 lines · On Mon, Jul 29, 2013 at 03:30:35PM +1000, [email protected] wrote:
Quoted 2 lines
Quoting "Paul E. McKenney" <[email protected]>:
...
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Note that the C standard considers the cast from signed to unsigned to be implementation-defined, see 6.3.1.3p3.
...
Quoted 4 lines
Quoted 4 lines
Don't worry, the case from signed to unsigned is actually well-defined - the relevant part is 6.3.1.3p2 (in C99):
Quoted 8 lines
Quoted 6 lines
Quoted 4 lines
Quoted 4 lines
Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.
Yep, but we are going in the other direction, from unsigned to signed.
Ahh, there's an error in the commit message (it says signed to unsigned).
Good catch, fixed!
Thanx, Paul
Quoted 4 lines · Paul E. McKenney
Quoted 2 lines
Ahh, there's an error in the commit message (it says signed to unsigned).
Good catch, fixed!
.. so I ended up waiting for that fixed version due to this email, but it never came. Should I just apply the original and re-fix it myself? Or is this queued up for 3.12 as being "not likely to actually matter", which is quite possibly true (since we compile with "-fno-strict-overflow", and thus gcc should hopefully not ever do any transformations that depend on signed integer overflows being undefined)
Linus
Quoted 7 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney
Quoted 2 lines
Ahh, there's an error in the commit message (it says signed to unsigned).
Good catch, fixed!
Quoted 7 lines
.. so I ended up waiting for that fixed version due to this email, but it never came. Should I just apply the original and re-fix it myself? Or is this queued up for 3.12 as being "not likely to actually matter", which is quite possibly true (since we compile with "-fno-strict-overflow", and thus gcc should hopefully not ever do any transformations that depend on signed integer overflows being undefined)
I have it queued up for 3.12, as you say, due to "-fno-strict-overflow". But if you would rather have it sooner, please let me know and I will send a pull request. Or, alternatively, please see below for the fixed patch.
Your choice! ;-)
Thanx, Paul
-------------------------------------------------------------------------
jiffies: Avoid undefined behavior from signed overflow
According to the C standard 3.4.3p3, overflow of a signed integer results in undefined behavior. This commit therefore changes the definitions of time_after(), time_after_eq(), time_after64(), and time_after_eq64() to avoid this undefined behavior. The trick is that the subtraction is done using unsigned arithmetic, which according to 6.2.5p9 cannot overflow because it is defined as modulo arithmetic. This has the added (though admittedly quite small) benefit of shortening two lines of code by four characters each.
Note that the C standard considers the cast from unsigned to signed to be implementation-defined, see 6.3.1.3p3. However, on a two-complement system, an implementation that defines anything other than a reinterpretation of the bits is free come to me, and I will be happy to act as a witness for its being committed to an insane asylum. (Although I have nothing against saturating arithmetic or signals in some cases, these things really should not be the default.)
[ paulmck: Included time_after64() and time_after_eq64(), as suggested
by Eric Dumazet, also fixed commit message.]
include/linux/jiffies.h +4 -4
@@ -101,13 +101,13 @@ static inline u64 get_jiffies_64(void)#define time_after (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(b) - (long)(a) < 0)) + ((long)((b) - (a)) < 0))#define time_before (a,b) time_after(b,a)#define time_after_eq (a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ - ((long)(a) - (long)(b) >= 0)) + ((long)((a) - (b)) >= 0))#define time_before_eq (a,b) time_after_eq(b,a)/*
@@ -130,13 +130,13 @@ static inline u64 get_jiffies_64(void)#define time_after64 (a,b) \ (typecheck(__u64, a) && \ typecheck(__u64, b) && \ - ((__s64)(b) - (__s64)(a) < 0)) + ((__s64)((b) - (a)) < 0))#define time_before64 (a,b) time_after64(b,a)#define time_after_eq64 (a,b) \ (typecheck(__u64, a) && \ typecheck(__u64, b) && \ - ((__s64)(a) - (__s64)(b) >= 0)) + ((__s64)((a) - (b)) >= 0))#define time_before_eq64 (a,b) time_after_eq64(b,a)#define time_in_range64 (a, b, c) \
Quoted 4 lines · Paul E. McKenney
I have it queued up for 3.12, as you say, due to "-fno-strict-overflow". But if you would rather have it sooner, please let me know and I will send a pull request.
No, that's fine. As long as it's somewhere. 3.12 is better, rc4 is already getting too big for my taste.
Linus
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney
I have it queued up for 3.12, as you say, due to "-fno-strict-overflow". But if you would rather have it sooner, please let me know and I will send a pull request.
No, that's fine. As long as it's somewhere. 3.12 is better, rc4 is already getting too big for my taste.
3.12 it is, then!
Thanx, Paul