[net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Jesper Dangaard Brouer]

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)
 
 /* Qdiscs using codel plugin must use codel_skb_cb in their own cb[] */
 struct codel_skb_cb {

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Eric Dumazet]

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

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Jesper Dangaard Brouer]

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)


-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Sr. Network Kernel Developer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Eric Dumazet]

On Thu, 2013-10-31 at 15:15 +0100, Jesper Dangaard Brouer wrote:

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

What about using the existing codel types ?

diff --git a/include/net/codel.h b/include/net/codel.h
index 389cf62..89a7781 100644
--- a/include/net/codel.h
+++ b/include/net/codel.h
@@ -72,7 +72,12 @@ static inline codel_time_t codel_get_time(void)
 	return ns >> CODEL_SHIFT;
 }
 
-#define codel_time_after(a, b)		((s32)(a) - (s32)(b) > 0)
+static inline bool codel_time_after(codel_time_t a, codel_time_t b)
+{
+	codel_tdiff_t delta = a - b;
+
+	return delta >= 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)


You need of course something similar for all variants.

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Jesper Dangaard Brouer]

On Thu, 31 Oct 2013 08:10:41 -0700
Eric Dumazet <eric.dumazet@gmail.com> wrote:

> On Thu, 2013-10-31 at 15:15 +0100, Jesper Dangaard Brouer wrote:
> 
> > 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)
> > 
> > 
> 
> What about using the existing codel types ?

Hmm, I would be okay to use codel types for typecheck(), but I don't
like the approach below, because we are hiding a typecast.  This just
makes the code harder to read/understand. An explicit cast shows that
we are doing something nasty, on purpose here.

I would rather keep as close as possible to include/linux/jiffies.h,
because I want readers to be-able to spot this pattern.


> diff --git a/include/net/codel.h b/include/net/codel.h
> index 389cf62..89a7781 100644
> --- a/include/net/codel.h
> +++ b/include/net/codel.h
> @@ -72,7 +72,12 @@ static inline codel_time_t codel_get_time(void)
>  	return ns >> CODEL_SHIFT;
>  }
>  
> -#define codel_time_after(a, b)		((s32)(a) - (s32)(b) > 0)
> +static inline bool codel_time_after(codel_time_t a, codel_time_t b)
> +{
> +	codel_tdiff_t delta = a - b;
> +
> +	return delta >= 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)
> 
> 
> You need of course something similar for all variants.
> 
> 



-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Sr. Network Kernel Developer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Ben Hutchings]

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.

-- 
Ben Hutchings, Staff Engineer, Solarflare
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Paul E. McKenney]

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

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Ben Hutchings]

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.

-- 
Ben Hutchings, Staff Engineer, Solarflare
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Paul E. McKenney]

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

Re: [net-next PATCH] net: codel: Avoid undefined behavior from signed overflow

[Jesper Dangaard Brouer]

On Wed, 30 Oct 2013 19:35:48 +0000
Ben Hutchings <bhutchings@solarflare.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.
> [...]
> 
> 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?)

For 16-bit I have tested that is fails, and that it does not help to
use the compiler flag: '-fno-strict-overflow' or '-fwrapv'. (this was
userspace test code, so I might be missing some kernel compiler options
that would make this work for 16-bit, but I doubt it)

#define works_u16_time_after(a,b)			\
	(typecheck(u_int16_t, a) &&		\
	 typecheck(u_int16_t, b) &&		\
	 ((int16_t)((b) - (a)) < 0))

#define bad_u16_time_after(a,b)			\
	(typecheck(u_int16_t, a) &&		\
	 typecheck(u_int16_t, b) &&		\
	 (((int16_t)(b) - (int16_t)(a)) < 0))


The bnx2x have a wrong/dangerup construct:

 File: drivers/net/ethernet/broadcom/bnx2x/bnx2x.h
 #define SUB_S16(a, b)		(s16)((s16)(a) - (s16)(b))
 #define SUB_S32(a, b)		(s32)((s32)(a) - (s32)(b))

I have tested this case, and it surprisingly works, due to the outer
(s16) cast I believe.

I think this should/could be fixed like:

diff --git a/drivers/net/ethernet/broadcom/bnx2x/bnx2x.h b/drivers/net/ethernet/broadcom/bnx2x/bnx2x.h
index 4e01c57..8969733 100644
--- a/drivers/net/ethernet/broadcom/bnx2x/bnx2x.h
+++ b/drivers/net/ethernet/broadcom/bnx2x/bnx2x.h
@@ -838,8 +838,8 @@ static inline bool bnx2x_fp_ll_polling(struct bnx2x_fastpath *fp)
 #define RCQ_TH_HI(bp)          (RCQ_TH_LO(bp) + DROPLESS_FC_HEADROOM)
 
 /* This is needed for determining of last_max */
-#define SUB_S16(a, b)          (s16)((s16)(a) - (s16)(b))
-#define SUB_S32(a, b)          (s32)((s32)(a) - (s32)(b))
+#define SUB_S16(a, b)          (s16)((u16)(a) - (u16)(b))
+#define SUB_S32(a, b)          (s32)((u32)(a) - (u32)(b))
 
 #define BNX2X_SWCID_SHIFT      17
 #define BNX2X_SWCID_MASK       ((0x1 << BNX2X_SWCID_SHIFT) - 1)


-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Sr. Network Kernel Developer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer