Subject: Re: [PATCH 3/6] IPV4 : use xor rather than multiple ands for route compare

From: Eric Dumazet <[email-masked]>
Date: Tue, 01 Apr 2008 07:52:03 +0200

Stephen Hemminger a écrit :
> The comparison in ip_route_input is a hot path, by recoding the C
> "and" as bit operations, fewer conditional branches get generated
> so the code should be faster. Maybe someday Gcc will be smart
> enough to do this?
> 
> Signed-off-by: Stephen Hemminger <[email-masked]>
> 
> --- a/net/ipv4/route.c	2008-03-31 10:57:30.000000000 -0700
> +++ b/net/ipv4/route.c	2008-03-31 11:10:44.000000000 -0700
> @@ -2079,14 +2079,14 @@ int ip_route_input(struct sk_buff *skb, 
>  	rcu_read_lock();
>  	for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
>  	     rth = rcu_dereference(rth->u.dst.rt_next)) {
> -		if (rth->fl.fl4_dst == daddr &&
> -		    rth->fl.fl4_src == saddr &&
> -		    rth->fl.iif == iif &&
> -		    rth->fl.oif == 0 &&
> -		    rth->fl.mark == skb->mark &&
> -		    rth->fl.fl4_tos == tos &&
> -		    net_eq(dev_net(rth->u.dst.dev), net) &&
> -		    rth->rt_genid == atomic_read(&rt_genid)) {
> +		if (((rth->fl.fl4_dst ^ daddr) |
> +		     (rth->fl.fl4_src ^ saddr) |
> +		     (rth->fl.iif ^ iif) |
> +		     rth->fl.oif |
> +		     (rth->fl.mark ^ skb->mark) |
> +		     (rth->fl.fl4_tos ^ tos) |
> +		     (rth->rt_genid ^ atomic_read(&rt_genid))) == 0 &&
> +		    net_eq(dev_net(rth->u.dst.dev), net)) {
>  			dst_use(&rth->u.dst, jiffies);
>  			RT_CACHE_STAT_INC(in_hit);
>  			rcu_read_unlock();
> 

Are you sure all fields share same cache lines, on 32bit and 64bit arches ?

I prefer having some conditional branches instead of cache misses, given that 
the first two branches are usually discriminant.

Maybe we could let one test on (daddr,saddr) to do a fast segregation (with 
one cache line at most) of candidates, then one remaining compare on other keys ?