| Message ID | 20131030172341.19203.93490.stgit@dragon |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | David Miller |
| Headers | show |
On Wed, 2013-10-30 at 18:23 +0100, Jesper Dangaard Brouer wrote: > From: Jesper Dangaard Brouer <netoptimizer@brouer.com> > > As described in commit 5a581b367 (jiffies: Avoid undefined > behavior from signed overflow), according to the C standard > 3.4.3p3, overflow of a signed integer results in undefined > behavior. > > To fix this, do as the above commit, and do an unsigned > subtraction, and interpreting the result as a signed > two's-complement number. This is based on the theory from > RFC 1982 and is nicely described in wikipedia here: > https://en.wikipedia.org/wiki/Serial_number_arithmetic#General_Solution > > A side-note, I have seen practical issues with the previous logic > when dealing with 16-bit, on a 64-bit machine (gcc version > 4.4.5). This were 32-bit, which I have not observed issues with. > > Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com> > Signed-off-by: Jesper Dangaard Brouer <netoptimizer@brouer.com> > --- > > include/net/codel.h | 8 ++++---- > 1 files changed, 4 insertions(+), 4 deletions(-) > > diff --git a/include/net/codel.h b/include/net/codel.h > index 389cf62..700fcdf 100644 > --- a/include/net/codel.h > +++ b/include/net/codel.h > @@ -72,10 +72,10 @@ static inline codel_time_t codel_get_time(void) > return ns >> CODEL_SHIFT; > } > > -#define codel_time_after(a, b) ((s32)(a) - (s32)(b) > 0) > -#define codel_time_after_eq(a, b) ((s32)(a) - (s32)(b) >= 0) > -#define codel_time_before(a, b) ((s32)(a) - (s32)(b) < 0) > -#define codel_time_before_eq(a, b) ((s32)(a) - (s32)(b) <= 0) > +#define codel_time_after(a, b) ((s32)((a) - (b)) > 0) > +#define codel_time_after_eq(a, b) ((s32)((a) - (b)) >= 0) > +#define codel_time_before(a, b) ((s32)((a) - (b)) < 0) > +#define codel_time_before_eq(a, b) ((s32)((a) - (b)) <= 0) > I see nothing enforcing an unsigned subtraction as claimed in your changelog. a / b could be signed. Paul commit 5a581b367b5 was OK because of existing typecheck(unsigned long, ....) -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, 2013-10-30 at 18:23 +0100, Jesper Dangaard Brouer wrote: > From: Jesper Dangaard Brouer <netoptimizer@brouer.com> > > As described in commit 5a581b367 (jiffies: Avoid undefined > behavior from signed overflow), according to the C standard > 3.4.3p3, overflow of a signed integer results in undefined > behavior. [...] According to the real processors that Linux runs on, signed arithmetic uses 2's complement representation and overflow wraps accordingly. And we rely on that behaviour in many places, so we use '-fno-strict-overflow' to tell gcc not to assume we avoid signed overflow. (There is also '-fwrapv' which tells gcc to assume the processor behaves this way, but shouldn't it already know how the target machine works?) Ben.
On Wed, Oct 30, 2013 at 07:35:48PM +0000, Ben Hutchings wrote: > On Wed, 2013-10-30 at 18:23 +0100, Jesper Dangaard Brouer wrote: > > From: Jesper Dangaard Brouer <netoptimizer@brouer.com> > > > > As described in commit 5a581b367 (jiffies: Avoid undefined > > behavior from signed overflow), according to the C standard > > 3.4.3p3, overflow of a signed integer results in undefined > > behavior. > [...] > > According to the real processors that Linux runs on, signed arithmetic > uses 2's complement representation and overflow wraps accordingly. And > we rely on that behaviour in many places, so we use > '-fno-strict-overflow' to tell gcc not to assume we avoid signed > overflow. (There is also '-fwrapv' which tells gcc to assume the > processor behaves this way, but shouldn't it already know how the target > machine works?) We should still fix them as we come across them. There are a few types of loops where '-fno-strict-overflow' results in more instructions being generated. Thanx, Paul -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, 2013-10-30 at 13:13 -0700, Paul E. McKenney wrote: > On Wed, Oct 30, 2013 at 07:35:48PM +0000, Ben Hutchings wrote: > > On Wed, 2013-10-30 at 18:23 +0100, Jesper Dangaard Brouer wrote: > > > From: Jesper Dangaard Brouer <netoptimizer@brouer.com> > > > > > > As described in commit 5a581b367 (jiffies: Avoid undefined > > > behavior from signed overflow), according to the C standard > > > 3.4.3p3, overflow of a signed integer results in undefined > > > behavior. > > [...] > > > > According to the real processors that Linux runs on, signed arithmetic > > uses 2's complement representation and overflow wraps accordingly. And > > we rely on that behaviour in many places, so we use > > '-fno-strict-overflow' to tell gcc not to assume we avoid signed > > overflow. (There is also '-fwrapv' which tells gcc to assume the > > processor behaves this way, but shouldn't it already know how the target > > machine works?) > > We should still fix them as we come across them. There are a few types > of loops where '-fno-strict-overflow' results in more instructions > being generated. I realise there's an opportunity for optimisation, but if these cases are fixed on an ad-hoc basis, how will we know we're ready to make the switch? Ben.
On Wed, Oct 30, 2013 at 08:19:12PM +0000, Ben Hutchings wrote: > On Wed, 2013-10-30 at 13:13 -0700, Paul E. McKenney wrote: > > On Wed, Oct 30, 2013 at 07:35:48PM +0000, Ben Hutchings wrote: > > > On Wed, 2013-10-30 at 18:23 +0100, Jesper Dangaard Brouer wrote: > > > > From: Jesper Dangaard Brouer <netoptimizer@brouer.com> > > > > > > > > As described in commit 5a581b367 (jiffies: Avoid undefined > > > > behavior from signed overflow), according to the C standard > > > > 3.4.3p3, overflow of a signed integer results in undefined > > > > behavior. > > > [...] > > > > > > According to the real processors that Linux runs on, signed arithmetic > > > uses 2's complement representation and overflow wraps accordingly. And > > > we rely on that behaviour in many places, so we use > > > '-fno-strict-overflow' to tell gcc not to assume we avoid signed > > > overflow. (There is also '-fwrapv' which tells gcc to assume the > > > processor behaves this way, but shouldn't it already know how the target > > > machine works?) > > > > We should still fix them as we come across them. There are a few types > > of loops where '-fno-strict-overflow' results in more instructions > > being generated. > > I realise there's an opportunity for optimisation, but if these cases > are fixed on an ad-hoc basis, how will we know we're ready to make the > switch? I believe that there are some tools that check for code that relies on signed integer overflow. Probably not yet up to dealing with the kernel. In the meantime, fixing them as we come across them is not a bad approach. Thanx, Paul -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, 30 Oct 2013 11:01:44 -0700 Eric Dumazet <eric.dumazet@gmail.com> wrote: > On Wed, 2013-10-30 at 18:23 +0100, Jesper Dangaard Brouer wrote: > > From: Jesper Dangaard Brouer <netoptimizer@brouer.com> > > > > As described in commit 5a581b367 (jiffies: Avoid undefined > > behavior from signed overflow), according to the C standard > > 3.4.3p3, overflow of a signed integer results in undefined > > behavior. > > > > To fix this, do as the above commit, and do an unsigned > > subtraction, and interpreting the result as a signed > > two's-complement number. This is based on the theory from > > RFC 1982 and is nicely described in wikipedia here: > > https://en.wikipedia.org/wiki/Serial_number_arithmetic#General_Solution > > > > A side-note, I have seen practical issues with the previous logic > > when dealing with 16-bit, on a 64-bit machine (gcc version > > 4.4.5). This were 32-bit, which I have not observed issues with. > > > > Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com> > > Signed-off-by: Jesper Dangaard Brouer <netoptimizer@brouer.com> > > --- > > > > include/net/codel.h | 8 ++++---- > > 1 files changed, 4 insertions(+), 4 deletions(-) > > > > diff --git a/include/net/codel.h b/include/net/codel.h > > index 389cf62..700fcdf 100644 > > --- a/include/net/codel.h > > +++ b/include/net/codel.h > > @@ -72,10 +72,10 @@ static inline codel_time_t codel_get_time(void) > > return ns >> CODEL_SHIFT; > > } > > > > -#define codel_time_after(a, b) ((s32)(a) - (s32)(b) > 0) > > -#define codel_time_after_eq(a, b) ((s32)(a) - (s32)(b) >= 0) > > -#define codel_time_before(a, b) ((s32)(a) - (s32)(b) < 0) > > -#define codel_time_before_eq(a, b) ((s32)(a) - (s32)(b) <= 0) > > +#define codel_time_after(a, b) ((s32)((a) - (b)) > 0) > > +#define codel_time_after_eq(a, b) ((s32)((a) - (b)) >= 0) > > +#define codel_time_before(a, b) ((s32)((a) - (b)) < 0) > > +#define codel_time_before_eq(a, b) ((s32)((a) - (b)) <= 0) > > > > I see nothing enforcing an unsigned subtraction as claimed in your > changelog. > > a / b could be signed. > > Paul commit 5a581b367b5 was OK because of existing typecheck(unsigned > long, ....) Okay, I'll cook up another patch, after work. Adding all the typecheck() stuff, just bloats the code. Would it be better/okay just to do?: (s32)((u32)(a) - (u32)(b)) > 0)
diff --git a/include/net/codel.h b/include/net/codel.h index 389cf62..700fcdf 100644 --- a/include/net/codel.h +++ b/include/net/codel.h @@ -72,10 +72,10 @@ static inline codel_time_t codel_get_time(void) return ns >> CODEL_SHIFT; } -#define codel_time_after(a, b) ((s32)(a) - (s32)(b) > 0) -#define codel_time_after_eq(a, b) ((s32)(a) - (s32)(b) >= 0) -#define codel_time_before(a, b) ((s32)(a) - (s32)(b) < 0) -#define codel_time_before_eq(a, b) ((s32)(a) - (s32)(b) <= 0) +#define codel_time_after(a, b) ((s32)((a) - (b)) > 0) +#define codel_time_after_eq(a, b) ((s32)((a) - (b)) >= 0) +#define codel_time_before(a, b) ((s32)((a) - (b)) < 0) +#define codel_time_before_eq(a, b) ((s32)((a) - (b)) <= 0) /* Qdiscs using codel plugin must use codel_skb_cb in their own cb[] */ struct codel_skb_cb {