Avoid extra calculation in ip_route_input_common

PATCH In review Michael Wang 3 participants 8 messages Dec 21, 2011

Subsystems (3)

Networking Network drivers IPv4/IPv6

lore

Share & tools

lore

Michael Wang

author

2011-12-21 05:12 UTC #0 lore raw

PATCH 1/1 Avoid extra calculation in ip_route_input_common

From: Michael Wang <[email protected]>

If previous condition doesn't meet, the later check will be cancelled. So we don't need to do all the calculation.

Signed-off-by Michael Wang <[email protected]>

---
 net/ipv4/route.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)

net/ipv4/route.c +4 -4

index f30112f..2872bfb 100644
@@ -2362,10 +2362,10 @@ int ip_route_input_common(struct sk_buff *skb, __be32 daddr, __be32 saddr,
 
 	for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
 	     rth = rcu_dereference(rth->dst.rt_next)) {
-		if ((((__force u32)rth->rt_key_dst ^ (__force u32)daddr) |
-		     ((__force u32)rth->rt_key_src ^ (__force u32)saddr) |
-		     (rth->rt_route_iif ^ iif) |
-		     (rth->rt_key_tos ^ tos)) == 0 &&
+		if (((__force u32)rth->rt_key_dst ^ (__force u32)daddr) == 0 &&
+		    ((__force u32)rth->rt_key_src ^ (__force u32)saddr) == 0 &&
+		    rth->rt_route_iif == iif &&
+		    rth->rt_key_tos == tos &&
 		    rth->rt_mark == skb->mark &&
 		    net_eq(dev_net(rth->dst.dev), net) &&
 		    !rt_is_expired(rth)) {

Signature · 1 line

1.7.4.1

Michael Wang

author

2011-12-21 05:20 UTC #1 lore raw

Please tell me if this patch is silly...
I really want to know the reason we need to use ^ and | instead of if and &&.

Quoted 15 lines · Michael Wang

From: Michael Wang <[email protected]>
If previous condition doesn't meet, the later check will be cancelled. So we don't need to do all the calculation.
Signed-off-by Michael Wang <[email protected]>
---
 net/ipv4/route.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)
net/ipv4/route.c +0 -0
index f30112f..2872bfb 100644

net/ipv4/route.c int ip_route_input_common(struct sk_buff *skb, __be32 daddr, __be32 saddr, · line 2365

Quoted 4 lines

net/ipv4/route.c +0 -1

@@ -2362,10 +2362,10 @@ int ip_route_input_common(struct sk_buff *skb, __be32 daddr, __be32 saddr,
 
 	for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
 	     rth = rcu_dereference(rth->dst.rt_next)) {
-		if ((((__force u32)rth->rt_key_dst ^ (__force u32)daddr) |

And I also wonder whether I can use "rth->rt_key_dst == daddr" here or not...

Thanks & Regards,
Michael Wang

Quoted 10 lines

net/ipv4/route.c +4 -3

-		     ((__force u32)rth->rt_key_src ^ (__force u32)saddr) |
-		     (rth->rt_route_iif ^ iif) |
-		     (rth->rt_key_tos ^ tos)) == 0 &&
+		if (((__force u32)rth->rt_key_dst ^ (__force u32)daddr) == 0 &&
+		    ((__force u32)rth->rt_key_src ^ (__force u32)saddr) == 0 &&
+		    rth->rt_route_iif == iif &&
+		    rth->rt_key_tos == tos &&
 		    rth->rt_mark == skb->mark &&
 		    net_eq(dev_net(rth->dst.dev), net) &&
 		    !rt_is_expired(rth)) {

Joe Perches

Acked-by Eric Dumazet on v1 1/1

2011-12-21 05:23 UTC #2 lore raw

In reply to Michael Wang

Quoted 4 lines · Michael Wang

From: Michael Wang <[email protected]>
If previous condition doesn't meet, the later check will be cancelled. So we don't need to do all the calculation.

Not sure about that.

Quoted 14 lines

Signed-off-by Michael Wang <[email protected]>

---
 net/ipv4/route.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)

net/ipv4/route.c +0 -1

index f30112f..2872bfb 100644
@@ -2362,10 +2362,10 @@ int ip_route_input_common(struct sk_buff *skb, __be32 daddr, __be32 saddr,
 
 	for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
 	     rth = rcu_dereference(rth->dst.rt_next)) {
-		if ((((__force u32)rth->rt_key_dst ^ (__force u32)daddr) |

net/ipv4/route.c int ip_route_input_common(struct sk_buff *skb, __be32 daddr, __be32 saddr, · line 2371

Quoted 10 lines

net/ipv4/route.c +4 -3

-		     ((__force u32)rth->rt_key_src ^ (__force u32)saddr) |
-		     (rth->rt_route_iif ^ iif) |
-		     (rth->rt_key_tos ^ tos)) == 0 &&
+		if (((__force u32)rth->rt_key_dst ^ (__force u32)daddr) == 0 &&
+		    ((__force u32)rth->rt_key_src ^ (__force u32)saddr) == 0 &&
+		    rth->rt_route_iif == iif &&
+		    rth->rt_key_tos == tos &&
 		    rth->rt_mark == skb->mark &&
 		    net_eq(dev_net(rth->dst.dev), net) &&
 		    !rt_is_expired(rth)) {

See:

commit c0b8c32b1c96afc9b32b717927330025cc1c501e

Author: Stephen Hemminger <[email protected]>
Date:   Thu Apr 10 04:00:28 2008 -0700

IPV4: use xor rather than multiple ands for route compare

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 protected]>

Acked-by Eric Dumazet <[email protected]>

Signed-off-by David S. Miller <[email protected]>

Michael Wang

author

2011-12-21 05:39 UTC #3 lore raw

Quoted 8 lines · Joe Perches

Quoted 4 lines · Michael Wang
From: Michael Wang <[email protected]>
If previous condition doesn't meet, the later check will be cancelled. So we don't need to do all the calculation.
Not sure about that.

Hi, Joe

Thanks for your reply :)

Quoted 31 lines

Quoted 14 lines

Signed-off-by Michael Wang <[email protected]>

---
 net/ipv4/route.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)

net/ipv4/route.c +0 -1

index f30112f..2872bfb 100644
@@ -2362,10 +2362,10 @@ int ip_route_input_common(struct sk_buff *skb, __be32 daddr, __be32 saddr,
 
 	for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
 	     rth = rcu_dereference(rth->dst.rt_next)) {
-		if ((((__force u32)rth->rt_key_dst ^ (__force u32)daddr) |

net/ipv4/route.c int ip_route_input_common(struct sk_buff *skb, __be32 daddr, __be32 saddr, · line 2371

Quoted 10 lines

net/ipv4/route.c +4 -3

-		     ((__force u32)rth->rt_key_src ^ (__force u32)saddr) |
-		     (rth->rt_route_iif ^ iif) |
-		     (rth->rt_key_tos ^ tos)) == 0 &&
+		if (((__force u32)rth->rt_key_dst ^ (__force u32)daddr) == 0 &&
+		    ((__force u32)rth->rt_key_src ^ (__force u32)saddr) == 0 &&
+		    rth->rt_route_iif == iif &&
+		    rth->rt_key_tos == tos &&
 		    rth->rt_mark == skb->mark &&
 		    net_eq(dev_net(rth->dst.dev), net) &&
 		    !rt_is_expired(rth)) {

See:

commit c0b8c32b1c96afc9b32b717927330025cc1c501e

Author: Stephen Hemminger <[email protected]>
Date:   Thu Apr 10 04:00:28 2008 -0700

Quoted 6 lines

IPV4: use xor rather than multiple ands for route compare
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?

This is what confused me, why "fewer conditional branches get generated" will make code faster?
In this example, I think the best condition when daddr is different, we only need to go to one branch do compare then quit, won't this be faster?

Thanks,
Michael Wang

Quoted 6 lines

Signed-off-by Stephen Hemminger <[email protected]>
Acked-by Eric Dumazet <[email protected]>
Signed-off-by David S. Miller <[email protected]>

Joe Perches

2011-12-21 05:50 UTC #4 lore raw

Quoted 6 lines · Michael Wang

Quoted 5 lines · Joe Perches
Quoted 4 lines · Michael Wang
From: Michael Wang <[email protected]>
If previous condition doesn't meet, the later check will be cancelled. So we don't need to do all the calculation.

[]

Quoted 6 lines

Quoted 6 lines
commit c0b8c32b1c96afc9b32b717927330025cc1c501e
Author: Stephen Hemminger <[email protected]>
Date:   Thu Apr 10 04:00:28 2008 -0700
IPV4: use xor rather than multiple ands for route compare

Quoted 8 lines

Quoted 4 lines
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?
This is what confused me, why "fewer conditional branches get generated" will make code faster?
In this example, I think the best condition when daddr is different, we only need to go to one branch do compare then quit, won't this be faster?

	if (a && b)
		...
pseudo-codes to:
	if (!a)
		goto fail;
	if (!b)
		goto fail;
	...

fail:

Each of those conditional branches has a cost. Combining tests of variables in the same cache lines has relatively little cost compared to the conditional branches.

That's the theory anyway.

If you have tests that demonstrate otherwise, please provide them.

cheers, Joe

Michael Wang

author

2011-12-21 06:00 UTC #5 lore raw

Quoted 31 lines · Joe Perches

Quoted 6 lines · Michael Wang
Quoted 5 lines · Joe Perches
Quoted 4 lines · Michael Wang
From: Michael Wang <[email protected]>
If previous condition doesn't meet, the later check will be cancelled. So we don't need to do all the calculation.
[]
Quoted 6 lines
Quoted 6 lines
commit c0b8c32b1c96afc9b32b717927330025cc1c501e
Author: Stephen Hemminger <[email protected]>
Date:   Thu Apr 10 04:00:28 2008 -0700
IPV4: use xor rather than multiple ands for route compare
Quoted 8 lines
Quoted 4 lines
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?
This is what confused me, why "fewer conditional branches get generated" will make code faster?
In this example, I think the best condition when daddr is different, we only need to go to one branch do compare then quit, won't this be faster?
	if (a && b)
		...
pseudo-codes to:
	if (!a)
		goto fail;
	if (!b)
		goto fail;
	...

Quoted 7 lines

fail:
Each of those conditional branches has a cost. Combining tests of variables in the same cache lines has relatively little cost compared to the conditional branches.

That make sense :)

Quoted 5 lines

That's the theory anyway.
If you have tests that demonstrate otherwise, please provide them.

I think the previous patch should have done such test, otherwise they won't do this change.

Thanks for your reply, that clear my confusion.

Regards,
Michael Wang

Quoted 2 lines

cheers, Joe

David Miller

maintainer

2011-12-21 05:58 UTC #6 lore raw

In reply to Michael Wang

From: Michael Wang <[email protected]>
Date: Wed, 21 Dec 2011 13:12:03 +0800

Quoted 6 lines

From: Michael Wang <[email protected]>
If previous condition doesn't meet, the later check will be cancelled. So we don't need to do all the calculation.
Signed-off-by Michael Wang <[email protected]>

This is intentional to reduce the number of branch prediction misses, please don't change this.

Once we read one of these values, the rest are incredibly cheap, the real cost is if we have tons of real branches here, each of which can be mispredicted.

Michael Wang

author

2011-12-21 06:04 UTC #7 lore raw

Quoted 8 lines · David Miller

From: Michael Wang <[email protected]>
Date: Wed, 21 Dec 2011 13:12:03 +0800
Quoted 5 lines
From: Michael Wang <[email protected]>
If previous condition doesn't meet, the later check will be cancelled. So we don't need to do all the calculation.

Quoted 9 lines

Quoted 1 line
Signed-off-by Michael Wang <[email protected]>
This is intentional to reduce the number of branch prediction misses, please don't change this.
Once we read one of these values, the rest are incredibly cheap, the real cost is if we have tons of real branches here, each of which can be mispredicted.

Hi, David

Thanks for your detailed explain, now I know the reason we use this style :)

Thanks,
Michael Wang