bridge: faster compare for link local addresses

bridge: faster compare for link local addresses

[Stephen Hemminger]

Use logic operations rather than memcmp() to compare destination
address with link local multicast addresses.

Signed-off-by: Stephen Hemminger <shemminger@linux-foundation.org>

---
 net/bridge/br_input.c |    6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

--- netem-dev.orig/net/bridge/br_input.c
+++ netem-dev/net/bridge/br_input.c
@@ -112,7 +112,11 @@ static int br_handle_local_finish(struct
  */
 static inline int is_link_local(const unsigned char *dest)
 {
-	return memcmp(dest, br_group_address, 5) == 0 && (dest[5] & 0xf0) == 0;
+	const u16 *a = (const u16 *) dest;
+	static const u16 *const b = (const u16 *const ) br_group_address;
+	static const u16 m = __constant_cpu_to_be16(0xfff0);
+
+	return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | ((a[2] ^ b[2]) & m)) == 0;
 }
 
 /*

Re: bridge: faster compare for link local addresses

[David Miller]

From: Stephen Hemminger <shemminger@linux-foundation.org>
Date: Mon, 12 Mar 2007 16:20:15 -0700

> Use logic operations rather than memcmp() to compare destination
> address with link local multicast addresses.
> 
> Signed-off-by: Stephen Hemminger <shemminger@linux-foundation.org>

With all of these Eric Dumazet'esque style changes I think we
may be producing a clone here :-)

Applied to net-2.6.22, thanks Stephen!

Re: bridge: faster compare for link local addresses

[Rick Jones]

Stephen Hemminger wrote:
> Use logic operations rather than memcmp() to compare destination
> address with link local multicast addresses.
> 
> Signed-off-by: Stephen Hemminger <shemminger@linux-foundation.org>
> 
> ---
>  net/bridge/br_input.c |    6 +++++-
>  1 file changed, 5 insertions(+), 1 deletion(-)
> 
> --- netem-dev.orig/net/bridge/br_input.c
> +++ netem-dev/net/bridge/br_input.c
> @@ -112,7 +112,11 @@ static int br_handle_local_finish(struct
>   */
>  static inline int is_link_local(const unsigned char *dest)
>  {
> -	return memcmp(dest, br_group_address, 5) == 0 && (dest[5] & 0xf0) == 0;
> +	const u16 *a = (const u16 *) dest;
> +	static const u16 *const b = (const u16 *const ) br_group_address;
> +	static const u16 m = __constant_cpu_to_be16(0xfff0);
> +
> +	return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | ((a[2] ^ b[2]) & m)) == 0;
>  }

Being paranoid - are there no worries about the alignment of dest?

rick jones

Re: bridge: faster compare for link local addresses

[David Miller]

From: Rick Jones <rick.jones2@hp.com>
Date: Mon, 12 Mar 2007 17:05:39 -0700

> Being paranoid - are there no worries about the alignment of dest?

If it's an issue, it's an issue elsewhere too, as the places
where Stephen took this idiomatic code from is the code
ethernet handling and that runs on every input packet via
eth_type_trans().

Re: bridge: faster compare for link local addresses

[Eric Dumazet]

On Tuesday 13 March 2007 15:01, Andi Kleen wrote:
> David Miller <davem@davemloft.net> writes:
> > From: Rick Jones <rick.jones2@hp.com>
> > Date: Mon, 12 Mar 2007 17:05:39 -0700
> >
> > > Being paranoid - are there no worries about the alignment of dest?
> >
> > If it's an issue, it's an issue elsewhere too, as the places
> > where Stephen took this idiomatic code from is the code
> > ethernet handling and that runs on every input packet via
> > eth_type_trans().
>
> As a quick note -- when you tell gcc the expected alignment
> by using correct types then moderm gcc should generate fast inline code
> for memcpy/memcmp/etc. by itself. It only falls back to a slow generic
> function when it cannot figure out the alignment or the size.
>
> So I expect just using u32 * instead of char * should have the same
> effect and would be somewhat cleaner and the memcmp could be kept.

For memcpy() yes you can have some optimizations.

But memcmp() has a strong semantic (in libc). memcmp(a, b, 6) should do 6 byte 
compares and conditional branches, regardless of a/b alignment.
Or use the x86 "rep cmpsb" instruction that basically has the same cost.

The trick we use in compare_ether_addr() reduces to one some arithmetic and 
one test.

return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2])) != 0;

I found this line as clean as memcmp(a, b, 6)

(On x86_64, were alignment is not mandatory, we could do :

((*(long *)a ^ *(long*)b) << 16) != 0)

(only if we can always read two extra bytes without faulting, of course :) )

Re: bridge: faster compare for link local addresses

[Andi Kleen]

David Miller <davem@davemloft.net> writes:

> From: Rick Jones <rick.jones2@hp.com>
> Date: Mon, 12 Mar 2007 17:05:39 -0700
> 
> > Being paranoid - are there no worries about the alignment of dest?
> 
> If it's an issue, it's an issue elsewhere too, as the places
> where Stephen took this idiomatic code from is the code
> ethernet handling and that runs on every input packet via
> eth_type_trans().

As a quick note -- when you tell gcc the expected alignment
by using correct types then moderm gcc should generate fast inline code 
for memcpy/memcmp/etc. by itself. It only falls back to a slow generic
function when it cannot figure out the alignment or the size.

So I expect just using u32 * instead of char * should have the same
effect and would be somewhat cleaner and the memcmp could be kept.

-Andi

Re: bridge: faster compare for link local addresses

[David Miller]

From: Eric Dumazet <dada1@cosmosbay.com>
Date: Tue, 13 Mar 2007 14:38:32 +0100

> But memcmp() has a strong semantic (in libc). memcmp(a, b, 6) should
> do 6 byte compares and conditional branches, regardless of a/b
> alignment.  Or use the x86 "rep cmpsb" instruction that basically
> has the same cost.

Yep, that's the issue, gcc won't make the reductions necessary
here to get it down to one comparison and one branch.

Re: bridge: faster compare for link local addresses

[Stephen Hemminger]

On Tue, 13 Mar 2007 12:39:54 -0700 (PDT)
David Miller <davem@davemloft.net> wrote:

> From: Eric Dumazet <dada1@cosmosbay.com>
> Date: Tue, 13 Mar 2007 14:38:32 +0100
> 
> > But memcmp() has a strong semantic (in libc). memcmp(a, b, 6) should
> > do 6 byte compares and conditional branches, regardless of a/b
> > alignment.  Or use the x86 "rep cmpsb" instruction that basically
> > has the same cost.
> 
> Yep, that's the issue, gcc won't make the reductions necessary
> here to get it down to one comparison and one branch.

Also, for our usage we only care about equality, not greater/less than
return value.

-- 
Stephen Hemminger <shemminger@linux-foundation.org>