net: alignment problem in icmp code

net: alignment problem in icmp code

[Pierre Ossman]

[-- Attachment #1: Type: text/plain, Size: 1132 bytes --]

Structure assignment have to be aligned just like any assignment, and the skb could point to anything. So take the safe route and use a memcpy().

Signed-off-by: Pierre Ossman <drzeus@drzeus.cx>
---

diff --git a/net/ipv4/icmp.c b/net/ipv4/icmp.c
index 272c69e..a7e2ec9 100644
--- a/net/ipv4/icmp.c
+++ b/net/ipv4/icmp.c
@@ -783,7 +783,7 @@ static void icmp_echo(struct sk_buff *skb)
 	if (!sysctl_icmp_echo_ignore_all) {
 		struct icmp_bxm icmp_param;
 
-		icmp_param.data.icmph	   = *icmp_hdr(skb);
+		memcpy(&icmp_param.data.icmph, icmp_hdr(skb), sizeof(struct icmphdr));
 		icmp_param.data.icmph.type = ICMP_ECHOREPLY;
 		icmp_param.skb		   = skb;
 		icmp_param.offset	   = 0;
@@ -819,7 +819,7 @@ static void icmp_timestamp(struct sk_buff *skb)
 	icmp_param.data.times[2] = icmp_param.data.times[1];
 	if (skb_copy_bits(skb, 0, &icmp_param.data.times[0], 4))
 		BUG();
-	icmp_param.data.icmph	   = *icmp_hdr(skb);
+	memcpy(&icmp_param.data.icmph, icmp_hdr(skb), sizeof(struct icmphdr));
 	icmp_param.data.icmph.type = ICMP_TIMESTAMPREPLY;
 	icmp_param.data.icmph.code = 0;
 	icmp_param.skb		   = skb;

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: net: alignment problem in icmp code

[David Miller]

From: Pierre Ossman <drzeus@drzeus.cx>
Date: Sat, 20 Oct 2007 23:35:40 +0200

> Structure assignment have to be aligned just like any assignment, and the skb could point to anything. So take the safe route and use a memcpy().
> 
> Signed-off-by: Pierre Ossman <drzeus@drzeus.cx>

Unfortunately this doesn't work, GCC can inline the memcpy just like
the assignment.

I tried to use a similar trick in the net/xfrm/xfrm_user.c code
but in the end it doesn't work at all.

Re: net: alignment problem in icmp code

[Pierre Ossman]

[-- Attachment #1: Type: text/plain, Size: 1382 bytes --]

On Sat, 20 Oct 2007 22:12:57 -0700 (PDT)
David Miller <davem@davemloft.net> wrote:

> From: Pierre Ossman <drzeus@drzeus.cx>
> Date: Sat, 20 Oct 2007 23:35:40 +0200
> 
> > Structure assignment have to be aligned just like any assignment, and the skb could point to anything. So take the safe route and use a memcpy().
> > 
> > Signed-off-by: Pierre Ossman <drzeus@drzeus.cx>
> 
> Unfortunately this doesn't work, GCC can inline the memcpy just like
> the assignment.
> 
> I tried to use a similar trick in the net/xfrm/xfrm_user.c code
> but in the end it doesn't work at all.

Inlining isn't the problem, but the defined semantics of assignment versus memcpy(). memcpy() must work on any region of memory, whilst assignment must only work on a properly aligned object. Since icmphdr contains a u32, the compiler "knows" the object will always be 32-bit aligned and generates assembly based on this assumption. Of course this is incorrect if the lower layers didn't have a multiple of 4 bytes of headers.

Anyway, I discovered the hard way that there are lots and lots of places in the IP code that assumes alignment, so this seems to be a rather daunting task to fix. So this patch will just be one very small piece of the puzzle. :/

(Perhaps something for kernel newbies, to track down and fix all the alignment assumptions in the IP stack?)

Rgds
Pierre

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: net: alignment problem in icmp code

[David Miller]

From: Pierre Ossman <drzeus@drzeus.cx>
Date: Sun, 21 Oct 2007 11:34:05 +0200

> Inlining isn't the problem, but the defined semantics of assignment
> versus memcpy(). memcpy() must work on any region of memory, whilst
> assignment must only work on a properly aligned object.

You are missing a crucial point.

The compiler may emit the same exact loads and stores when it inlines
memcpy() if it "knows" the objects are aligned properly.  And it very
much will do this.

If the compiler is calling memcpy() in your build, it's only because
gcc believes the the object is too big to optimally memcpy() inline.

Re: net: alignment problem in icmp code

[Pierre Ossman]

[-- Attachment #1: Type: text/plain, Size: 562 bytes --]

On Sun, 21 Oct 2007 12:48:14 -0700 (PDT)
David Miller <davem@davemloft.net> wrote:

> 
> You are missing a crucial point.
> 
> The compiler may emit the same exact loads and stores when it inlines
> memcpy() if it "knows" the objects are aligned properly.  And it very
> much will do this.
> 

Not sure that would be valid. memcpy() is defined as having void* arguments, and the compiler cannot just ignore that if it chooses to inline it.

Still, just give it the char* from the skb and it cannot make any assumption on alignment.

Rgds
Pierre

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: net: alignment problem in icmp code

[David Miller]

From: Pierre Ossman <drzeus@drzeus.cx>
Date: Sun, 21 Oct 2007 23:21:13 +0200

> Not sure that would be valid. memcpy() is defined as having void*
> arguments, and the compiler cannot just ignore that if it chooses to
> inline it.

Yes it can, there are C language rules about the alignment of types
that the compiler completely can take advantage of in those kinds of
situations.

If you don't believe me, compile something like the following
with optimizations enabled:

void foo(unsigned long long *a,
	 unsigned long long *b)
{
	memcpy(a, b, sizeof(*a));
}

You will get a 64-bit load and a 64-bit store emitted by
the compiler.  Here is what we get on sparc64:

foo:
	ldx	[%o1], %g1
	jmp	%o7+8
	 stx	%g1, [%o0]

Structure assignment is also essentially just another kind of
inline memcpy().

> Still, just give it the char* from the skb and it cannot make any
> assumption on alignment.

Yes, that would make it more likely to work.

However, instead of relying upon magic like this, let's just tell the
compiler explicitly what it going on by using get_unaligned().

Next, there are redundant stores being done here since the code and
type are explicitly overwritten in various ways.

commit 6471862b69e9272125f6a01916e6587523bf91f3
Author: David S. Miller <davem@sunset.davemloft.net>
Date:   Sun Oct 21 16:01:49 2007 -0700

    [IPV4]: Handle potentially unaligned icmp headers in skb.
    
    Signed-off-by: David S. Miller <davem@davemloft.net>

diff --git a/net/ipv4/icmp.c b/net/ipv4/icmp.c
index 272c69e..2b654b1 100644
--- a/net/ipv4/icmp.c
+++ b/net/ipv4/icmp.c
@@ -92,6 +92,7 @@
 #include <asm/system.h>
 #include <asm/uaccess.h>
 #include <net/checksum.h>
+#include <asm/unaligned.h>
 
 /*
  *	Build xmit assembly blocks
@@ -766,6 +767,17 @@ out_err:
 	goto out;
 }
 
+static void fill_icmp_param_data(struct icmp_bxm *param,
+				 struct icmphdr *src,
+				 u8 type, u8 code)
+{
+	struct icmphdr *dst = &param->data.icmph;
+
+	dst->type = type;
+	dst->code = code;
+	dst->un.gateway = get_unaligned(&src->un.gateway);
+}
+
 /*
  *	Handle ICMP_ECHO ("ping") requests.
  *
@@ -783,8 +795,10 @@ static void icmp_echo(struct sk_buff *skb)
 	if (!sysctl_icmp_echo_ignore_all) {
 		struct icmp_bxm icmp_param;
 
-		icmp_param.data.icmph	   = *icmp_hdr(skb);
-		icmp_param.data.icmph.type = ICMP_ECHOREPLY;
+		fill_icmp_param_data(&icmp_param,
+				     icmp_hdr(skb),
+				     ICMP_ECHOREPLY,
+				     icmp_hdr(skb)->code);
 		icmp_param.skb		   = skb;
 		icmp_param.offset	   = 0;
 		icmp_param.data_len	   = skb->len;
@@ -819,9 +833,8 @@ static void icmp_timestamp(struct sk_buff *skb)
 	icmp_param.data.times[2] = icmp_param.data.times[1];
 	if (skb_copy_bits(skb, 0, &icmp_param.data.times[0], 4))
 		BUG();
-	icmp_param.data.icmph	   = *icmp_hdr(skb);
-	icmp_param.data.icmph.type = ICMP_TIMESTAMPREPLY;
-	icmp_param.data.icmph.code = 0;
+	fill_icmp_param_data(&icmp_param, icmp_hdr(skb),
+			     ICMP_TIMESTAMPREPLY, 0);
 	icmp_param.skb		   = skb;
 	icmp_param.offset	   = 0;
 	icmp_param.data_len	   = 0;

Re: net: alignment problem in icmp code

[Pierre Ossman]

[-- Attachment #1: Type: text/plain, Size: 1850 bytes --]

On Sun, 21 Oct 2007 16:02:15 -0700 (PDT)
David Miller <davem@davemloft.net> wrote:

> From: Pierre Ossman <drzeus@drzeus.cx>
> Date: Sun, 21 Oct 2007 23:21:13 +0200
> 
> > Not sure that would be valid. memcpy() is defined as having void*
> > arguments, and the compiler cannot just ignore that if it chooses to
> > inline it.
> 
> Yes it can, there are C language rules about the alignment of types
> that the compiler completely can take advantage of in those kinds of
> situations.
> 

I'm not debating that. What I'm saying is that calling memcpy() casts your pointers to void* with the included semantical changes. It can't just ignore that because it decides to inline the function. It would be the same thing as when gcc decided to ignore the volatile qualifier on a pointer just because it could optimize away to the real object and discover it wasn't marked with volatile. Something that was considered a bug and was fixed.

> If you don't believe me, compile something like the following
> with optimizations enabled:

gcc has had bugs in the past.

> You will get a 64-bit load and a 64-bit store emitted by
> the compiler.  Here is what we get on sparc64:
> 

I assume those ops cause a bus error on unaligned addresses?

> 
> However, instead of relying upon magic like this, let's just tell the
> compiler explicitly what it going on by using get_unaligned().
> 

It wouldn't be magic:

memcpy(&icmp_param.data.icmph, skb_transport_header(skb), sizeof(struct icmphdr));

I believe platforms without alignment requirements could optimize this better than the series of assignments. Not that I think this will be a potential bottle neck, but still.

> Next, there are redundant stores being done here since the code and
> type are explicitly overwritten in various ways.

Indeed.

Rgds
Pierre

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: net: alignment problem in icmp code

[David Miller]

From: Pierre Ossman <drzeus@drzeus.cx>
Date: Mon, 22 Oct 2007 06:54:43 +0200

> On Sun, 21 Oct 2007 16:02:15 -0700 (PDT)
> David Miller <davem@davemloft.net> wrote:
> 
> > You will get a 64-bit load and a 64-bit store emitted by
> > the compiler.  Here is what we get on sparc64:
> 
> I assume those ops cause a bus error on unaligned addresses?

Sure.  But the language defines that the types in question
must be 64-bit aligned, so it is legal for the compiler to
emit this code.

It's not a GCC bug.

If you want to let the compiler know that a pointer to a type might
not be aligned, you have to tell it so.

Re: net: alignment problem in icmp code

[Pierre Ossman]

[-- Attachment #1: Type: text/plain, Size: 1854 bytes --]

On Sun, 21 Oct 2007 22:15:24 -0700 (PDT)
David Miller <davem@davemloft.net> wrote:

> 
> Sure.  But the language defines that the types in question
> must be 64-bit aligned, so it is legal for the compiler to
> emit this code.
> 
> It's not a GCC bug.
> 

I've confirmed this behaviour on the AVR32 arch, and had a second look in the spec. The only way GCC can get away with this is by using a very creative interpretation of the result of casting a pointer to one type to a pointer to another type (which ISO C leaves undefined). Basically:

1. A cast from a pointer to one type to a pointer to a second type does not change the value. (GCC behaviour which we rely on heavily, even in your suggested patch).

2. A cast from a pointer to one type to a pointer to a second type changes the value so that it properly aligns with the second type. (As a cast to void*, which memcpy() requires, is safe according to ISO C, the pointer modification must be from char* to struct icmphdr*).

As 1 and 2 conflict, GCC's behaviour for pointer casts is still rather undefined. So although within the requirements of ISO C, it's rather user hostile. And it casts doubt on every pointer cast used.

> If you want to let the compiler know that a pointer to a type might
> not be aligned, you have to tell it so.

Which you can't do within the confines of ISO C. The get_unaligned() macro uses some GCC trickery (even outside what GCC documents as defined behaviour). To stay "clean", you have to avoid casting char* to foo*.

With all that said, as GCC does what it does, we can't really rely on a memcpy() anyway, so I support your patch.

As for other instances of unaligned accesses, is there any active work on getting rid of those? And would you accept more patches for fixing them? (Code complexity being the downside)

Rgds
Pierre

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: net: alignment problem in icmp code

[David Miller]

From: Pierre Ossman <drzeus@drzeus.cx>
Date: Mon, 22 Oct 2007 09:23:50 +0200

> As for other instances of unaligned accesses, is there any active
> work on getting rid of those? And would you accept more patches for
> fixing them? (Code complexity being the downside)

On fast paths we aren't going to add things like get_unaligned()
calls.

Every architecture should handle unaligned accesses properly, and for
the fast paths the network driver should provide the packet fully
aligned or take steps to make it so if it can't DMA directly into
2-byte offset buffers (such as copying the packet).

What is the specific reason why you see packet headers unaligned?
It's probably just some AVR networking driver that needs tweaks.

Re: net: alignment problem in icmp code

[Pierre Ossman]

[-- Attachment #1: Type: text/plain, Size: 1205 bytes --]

On Mon, 22 Oct 2007 01:31:05 -0700 (PDT)
David Miller <davem@davemloft.net> wrote:

> 
> On fast paths we aren't going to add things like get_unaligned()
> calls.
> 
> Every architecture should handle unaligned accesses properly, and for
> the fast paths the network driver should provide the packet fully
> aligned or take steps to make it so if it can't DMA directly into
> 2-byte offset buffers (such as copying the packet).
> 

This seems like a rather evil layering violation. The hardware driver needs to be aware of every layer between itself and the IP stack for this to work. And what does "aligned" mean in this context? 32-bit aligned? 64-bit aligned? The entire thing is severely underdocumented (which is why I got hit by the problem in the first place).

Also, since I developed the code on a forgiving platform (x86), I didn't notice this requirement. Perhaps a WARN_ON(NET_IP_ALIGN && (skb->data & 0x3));?

> What is the specific reason why you see packet headers unaligned?
> It's probably just some AVR networking driver that needs tweaks.

It's my own driver (if_sdio for libertas), which did not reserve two bytes as that voodoo was unknown to me.

Rgds
Pierre

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: net: alignment problem in icmp code

[David Miller]

From: Pierre Ossman <drzeus@drzeus.cx>
Date: Mon, 22 Oct 2007 10:42:08 +0200

> This seems like a rather evil layering violation.

This has a 10+ year precedence and it's why the Linux networking stack
is so fast.  If you read any other driver you would have seen the
skb_reserve() call every one of them do to align the headers.

I think I've tolerated this long enough.

Are you going keep teaching me how the C language works, how GCC
interprets it, and how evil the Linux networking is, or are you going
to fix the bug in your driver? :-)

Re: net: alignment problem in icmp code

[Pierre Ossman]

[-- Attachment #1: Type: text/plain, Size: 1235 bytes --]

On Mon, 22 Oct 2007 02:05:38 -0700 (PDT)
David Miller <davem@davemloft.net> wrote:

> From: Pierre Ossman <drzeus@drzeus.cx>
> Date: Mon, 22 Oct 2007 10:42:08 +0200
> 
> > This seems like a rather evil layering violation.
> 
> This has a 10+ year precedence and it's why the Linux networking stack
> is so fast.  If you read any other driver you would have seen the
> skb_reserve() call every one of them do to align the headers.
> 

The norm seems to be to not comment this call. It's hardly obvious.

> I think I've tolerated this long enough.
> 
> Are you going keep teaching me how the C language works, how GCC
> interprets it, and how evil the Linux networking is, or are you going
> to fix the bug in your driver? :-)

Settle down, "bug" fixed even before this discussion even began. I just don't like papering over problems so I want to know why this is needed and if it isn't indicative of a larger problem. If you don't want the discussions, make sure people know the gotchas.

(And I wasn't try to teach anyone. I was giving my view on things, and if you think I'm off my meds, feel free to say so. Groveling and excessively putting every statement as a question demeans us both. ;))

Rgds
Pierre

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: net: alignment problem in icmp code

[Eric Dumazet]

Pierre Ossman a écrit :
> On Mon, 22 Oct 2007 02:05:38 -0700 (PDT)
> David Miller <davem@davemloft.net> wrote:
>
>   
>> From: Pierre Ossman <drzeus@drzeus.cx>
>> Date: Mon, 22 Oct 2007 10:42:08 +0200
>>
>>     
>>> This seems like a rather evil layering violation.
>>>       
>> This has a 10+ year precedence and it's why the Linux networking stack
>> is so fast.  If you read any other driver you would have seen the
>> skb_reserve() call every one of them do to align the headers.
>>
>>     
>
> The norm seems to be to not comment this call. It's hardly obvious.
>
>   
This is not obvious you are right, but documented in 
include/linux/skbuff.h (lines 1150 ...)

/*
 * CPUs often take a performance hit when accessing unaligned memory
 * locations. The actual performance hit varies, it can be small if the
 * hardware handles it or large if we have to take an exception and fix it
 * in software.
 *
 * Since an ethernet header is 14 bytes network drivers often end up with
 * the IP header at an unaligned offset. The IP header can be aligned by
 * shifting the start of the packet by 2 bytes. Drivers should do this
 * with:
 *
 * skb_reserve(NET_IP_ALIGN);
 *
 * The downside to this alignment of the IP header is that the DMA is now
 * unaligned. On some architectures the cost of an unaligned DMA is high
 * and this cost outweighs the gains made by aligning the IP header.
 *
 * Since this trade off varies between architectures, we allow NET_IP_ALIGN
 * to be overridden.
 */
#ifndef NET_IP_ALIGN
#define NET_IP_ALIGN    2
#endif

But then, many drivers dont use NET_IP_ALIGN but a hardcoded 2

drivers/net/pcnet32.c:608:              skb_reserve(rx_skbuff, 2);
drivers/net/pcnet32.c:1214:                     skb_reserve(newskb, 2);
drivers/net/pcnet32.c:1245:             skb_reserve(skb, 2);    /* 16 
byte align */
drivers/net/pcnet32.c:2396:                     skb_reserve(rx_skbuff, 2);
drivers/net/sundance.c:989:             skb_reserve(skb, 2);    /* 16 
byte align the IP header. */
drivers/net/sundance.c:1312:                            skb_reserve(skb, 
2);    /* 16 byte align the IP header */
drivers/net/sundance.c:1375:                    skb_reserve(skb, 2); /* 
Align IP on 16 byte boundaries */