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 <[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]>
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)
/*
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 <[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]>
>
> 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.
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 <[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]>
> >
> > 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 <[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]>
Cc: Eric Dumazet <[email protected]>
[ 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) \
Quoting "Paul E. McKenney" <[email protected]>:
> 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.
On Mon, Jul 29, 2013 at 03:30:35PM +1000, [email protected] wrote:
> Quoting "Paul E. McKenney" <[email protected]>:
>
> >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
Quoting "Paul E. McKenney" <[email protected]>:
> On Mon, Jul 29, 2013 at 03:30:35PM +1000, [email protected] wrote:
>> Quoting "Paul E. McKenney" <[email protected]>:
>>
...
>> >
>> >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.
On Tue, Jul 30, 2013 at 12:01:03AM +1000, Kevin Easton wrote:
> Quoting "Paul E. McKenney" <[email protected]>:
>
> >On Mon, Jul 29, 2013 at 03:30:35PM +1000, [email protected] wrote:
> >>Quoting "Paul E. McKenney" <[email protected]>:
> >>
> ...
> >>>
> >>>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
On Mon, Jul 29, 2013 at 7:28 AM, Paul E. McKenney
<[email protected]> 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
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
> <[email protected]> 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 <[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]>
Cc: Eric Dumazet <[email protected]>
Cc: Kevin Easton <[email protected]>
[ 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) \
On Sun, Aug 4, 2013 at 1:20 PM, Paul E. McKenney
<[email protected]> 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
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
> <[email protected]> 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