From b3832117b4b61374fac08692f1b1a620088342dd Mon Sep 17 00:00:00 2001 From: Alexander Duyck Date: Thu, 22 Jan 2015 15:51:08 -0800 Subject: [PATCH] fib_trie: Use index & (~0ul << n->bits) instead of index >> n->bits In doing performance testing and analysis of the changes I recently found that by shifting the index I had created an unnecessary dependency. I have updated the code so that we instead shift a mask by bits and then just test against that as that should save us about 2 CPU cycles since we can generate the mask while the key and pos are being processed. Signed-off-by: Alexander Duyck Signed-off-by: David S. Miller --- net/ipv4/fib_trie.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 281e5e0..dea2f80 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -961,12 +961,12 @@ static struct tnode *fib_find_node(struct trie *t, u32 key) * prefix plus zeros for the bits in the cindex. The index * is the difference between the key and this value. From * this we can actually derive several pieces of data. - * if !(index >> bits) - * we know the value is cindex - * else + * if (index & (~0ul << bits)) * we have a mismatch in skip bits and failed + * else + * we know the value is cindex */ - if (index >> n->bits) + if (index & (~0ul << n->bits)) return NULL; /* we have found a leaf. Prefixes have already been compared */ @@ -1301,12 +1301,12 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp, * prefix plus zeros for the "bits" in the prefix. The index * is the difference between the key and this value. From * this we can actually derive several pieces of data. - * if !(index >> bits) - * we know the value is child index - * else + * if (index & (~0ul << bits)) * we have a mismatch in skip bits and failed + * else + * we know the value is cindex */ - if (index >> n->bits) + if (index & (~0ul << n->bits)) break; /* we have found a leaf. Prefixes have already been compared */ -- 2.7.4