[PATCH jiffies] Avoid undefined behavior from signed overflow

[PATCH jiffies] Avoid undefined behavior from signed overflow

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

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: John Stultz <john.stultz@linaro.org>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>

diff --git a/include/linux/jiffies.h b/include/linux/jiffies.h
index 97ba4e7..97967ba 100644
--- a/include/linux/jiffies.h
+++ b/include/linux/jiffies.h
@@ -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)
 
 /*

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Eric Dumazet]

On Sat, 2013-07-27 at 15:58 -0700, Paul E. McKenney wrote:
> 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.)
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Cc: John Stultz <john.stultz@linaro.org>
> Cc: "David S. Miller" <davem@davemloft.net>
> Cc: Arnd Bergmann <arnd@arndb.de>
> Cc: Ingo Molnar <mingo@kernel.org>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> 
> diff --git a/include/linux/jiffies.h b/include/linux/jiffies.h
> index 97ba4e7..97967ba 100644
> --- a/include/linux/jiffies.h
> +++ b/include/linux/jiffies.h
> @@ -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)
>  



time_after64() & time_after_eq64() probably need the same.

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Paul E. McKenney]

On Sun, Jul 28, 2013 at 11:46:59AM -0700, Eric Dumazet wrote:
> On Sat, 2013-07-27 at 15:58 -0700, Paul E. McKenney wrote:
> > 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.)
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > Cc: John Stultz <john.stultz@linaro.org>
> > Cc: "David S. Miller" <davem@davemloft.net>
> > Cc: Arnd Bergmann <arnd@arndb.de>
> > Cc: Ingo Molnar <mingo@kernel.org>
> > Cc: Linus Torvalds <torvalds@linux-foundation.org>
> > 
> > diff --git a/include/linux/jiffies.h b/include/linux/jiffies.h
> > index 97ba4e7..97967ba 100644
> > --- a/include/linux/jiffies.h
> > +++ b/include/linux/jiffies.h
> > @@ -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)
> 
> 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.)

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: John Stultz <john.stultz@linaro.org>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Eric Dumazet <eric.dumazet@gmail.com>
[ paulmck: Included time_after64() and time_after_eq64(), as suggested
  by Eric Dumazet.]

diff --git a/include/linux/jiffies.h b/include/linux/jiffies.h
index 97ba4e7..d235e88 100644
--- a/include/linux/jiffies.h
+++ b/include/linux/jiffies.h
@@ -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) \

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[caf]

Quoting "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>:

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

Don't worry, the case from signed to unsigned is actually well-defined -
the relevant part is 6.3.1.3p2 (in C99):

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

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Paul E. McKenney]

On Mon, Jul 29, 2013 at 03:30:35PM +1000, caf@guarana.org wrote:
> Quoting "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>:
> 
> >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.)
> 
> Don't worry, the case from signed to unsigned is actually well-defined -
> the relevant part is 6.3.1.3p2 (in C99):
> 
> >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.

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

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Kevin Easton]

Quoting "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>:

> On Mon, Jul 29, 2013 at 03:30:35PM +1000, caf@guarana.org wrote:
>> Quoting "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>:
>>
...
>> >
>> >Note that the C standard considers the cast from signed to
>> >unsigned to be implementation-defined, see 6.3.1.3p3.
...
>>
>> Don't worry, the case from signed to unsigned is actually well-defined -
>> the relevant part is 6.3.1.3p2 (in C99):
>>
>> >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.

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Paul E. McKenney]

On Tue, Jul 30, 2013 at 12:01:03AM +1000, Kevin Easton wrote:
> Quoting "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>:
> 
> >On Mon, Jul 29, 2013 at 03:30:35PM +1000, caf@guarana.org wrote:
> >>Quoting "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>:
> >>
> ...
> >>>
> >>>Note that the C standard considers the cast from signed to
> >>>unsigned to be implementation-defined, see 6.3.1.3p3.
> ...
> >>
> >>Don't worry, the case from signed to unsigned is actually well-defined -
> >>the relevant part is 6.3.1.3p2 (in C99):
> >>
> >>>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

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Linus Torvalds]

On Mon, Jul 29, 2013 at 7:28 AM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
>>
>> 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

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Paul E. McKenney]

On Sun, Aug 04, 2013 at 12:16:02PM -0700, Linus Torvalds wrote:
> On Mon, Jul 29, 2013 at 7:28 AM, Paul E. McKenney
> <paulmck@linux.vnet.ibm.com> wrote:
> >>
> >> 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)

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

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: John Stultz <john.stultz@linaro.org>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Kevin Easton <kevin@guarana.org>
[ paulmck: Included time_after64() and time_after_eq64(), as suggested
  by Eric Dumazet, also fixed commit message.]

diff --git a/include/linux/jiffies.h b/include/linux/jiffies.h
index 97ba4e7..d235e88 100644
--- a/include/linux/jiffies.h
+++ b/include/linux/jiffies.h
@@ -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) \

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Linus Torvalds]

On Sun, Aug 4, 2013 at 1:20 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
>
> 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

Re: [PATCH jiffies] Avoid undefined behavior from signed overflow

[Paul E. McKenney]

On Sun, Aug 04, 2013 at 01:23:13PM -0700, Linus Torvalds wrote:
> On Sun, Aug 4, 2013 at 1:20 PM, Paul E. McKenney
> <paulmck@linux.vnet.ibm.com> wrote:
> >
> > 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