[PATCH net-next] net: ipv4: Optimize check_leaf function

[PATCH net-next] net: ipv4: Optimize check_leaf function

[igorm]

From: Igor Maravic <igorm@etf.rs>

If the found tos is smaller then our tos,
don't pass through all the entries in fib_alias
list to find the match.
Directly jump to the last entry in the list, and check if the
tos value is 0.

Signed-off-by: Igor Maravic <igorm@etf.rs>
---
 net/ipv4/fib_trie.c |   10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 3c820da..ec45621 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -1366,8 +1366,14 @@ static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
 			struct fib_info *fi = fa->fa_info;
 			int nhsel, err;
 
-			if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
-				continue;
+			if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos) {
+				if (fa->fa_tos < flp->flowi4_tos) {
+					fa = list_entry_rcu(li->falh.prev, struct fib_alias, fa_list);
+					if (fa->fa_tos)
+						break;
+				} else
+					continue;
+			}
 			if (fi->fib_dead)
 				continue;
 			if (fa->fa_info->fib_scope < flp->flowi4_scope)
-- 
1.7.9.5

[PATCH net-next] net: ipv4: optimize tkey_mismatch

[igorm]

From: Igor Maravic <igorm@etf.rs>

Optimize tkey_mismatch function by using __fls function.

Signed-off-by: Igor Maravic <igorm@etf.rs>
---
 net/ipv4/fib_trie.c |   10 ++--------
 1 file changed, 2 insertions(+), 8 deletions(-)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index ec45621..b4b126c 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -265,14 +265,8 @@ static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
 
 static inline int tkey_mismatch(t_key a, int offset, t_key b)
 {
-	t_key diff = a ^ b;
-	int i = offset;
-
-	if (!diff)
-		return 0;
-	while ((diff << i) >> (KEYLENGTH-1) == 0)
-		i++;
-	return i;
+	t_key diff = (a ^ b) & (~((t_key)0) << offset >> offset);
+	return diff ? (KEYLENGTH - __fls(diff) - 1) : 0;
 }
 
 /*
-- 
1.7.9.5

Re: [PATCH net-next] net: ipv4: optimize tkey_mismatch

[David Miller]

From: igorm@etf.rs
Date: Tue, 28 Aug 2012 10:52:18 +0200

> From: Igor Maravic <igorm@etf.rs>
> 
> Optimize tkey_mismatch function by using __fls function.
> 
> Signed-off-by: Igor Maravic <igorm@etf.rs>

This will actually run slower on architectures like sparc that
don't have special instructions for __fls.

Your TOS "optimization" isn't very useful either since having
TOS routes is very rare.