summaryrefslogtreecommitdiff
path: root/net/ipv4/fib_trie.c
diff options
context:
space:
mode:
authorAlexander Duyck <alexander.h.duyck@redhat.com>2015-03-04 15:04:03 -0800
committerDavid S. Miller <davem@davemloft.net>2015-03-04 23:35:18 -0500
commit71e8b67d0fdd2fe22a657bb98716c5cf0e31e828 (patch)
tree5e5ab78f315e6cd7bc001a6627f2e3577e626301 /net/ipv4/fib_trie.c
parenta7e53531234dc206bb75abb5305a72665dd4d75d (diff)
fib_trie: Update last spot w/ idx >> n->bits code and explanation
This change updates the fib_table_lookup function so that it is in sync with the fib_find_node function in terms of the explanation for the index check based on the bits value. I have also updated it from doing a mask to just doing a compare as I have found that seems to provide more options to the compiler as I have seen it turn this into a shift of the value and test under some circumstances. In addition I addressed one minor issue in which we kept computing the key ^ n->key when checking the fib aliases. I pulled the xor out of the loop in order to reduce the number of memory reads in the lookup. As a result we should save a couple cycles since the xor is only done once much earlier in the lookup. Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r--net/ipv4/fib_trie.c18
1 files changed, 13 insertions, 5 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 3642b17c8726..08676c56efc3 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -1201,6 +1201,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
const t_key key = ntohl(flp->daddr);
struct tnode *n, *pn;
struct fib_alias *fa;
+ unsigned long index;
t_key cindex;
n = rcu_dereference(t->trie);
@@ -1216,19 +1217,23 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
/* Step 1: Travel to the longest prefix match in the trie */
for (;;) {
- unsigned long index = get_index(key, n);
+ index = get_index(key, n);
/* This bit of code is a bit tricky but it combines multiple
* checks into a single check. The prefix consists of the
* 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 & (~0ul << bits))
+ * if (index >= (1ul << bits))
* we have a mismatch in skip bits and failed
* else
* we know the value is cindex
+ *
+ * This check is safe even if bits == KEYLENGTH due to the
+ * fact that we can only allocate a node with 32 bits if a
+ * long is greater than 32 bits.
*/
- if (index & (~0ul << n->bits))
+ if (index >= (1ul << n->bits))
break;
/* we have found a leaf. Prefixes have already been compared */
@@ -1302,14 +1307,17 @@ backtrace:
}
found:
+ /* this line carries forward the xor from earlier in the function */
+ index = key ^ n->key;
+
/* Step 3: Process the leaf, if that fails fall back to backtracing */
hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
struct fib_info *fi = fa->fa_info;
int nhsel, err;
- if (((key ^ n->key) >= (1ul << fa->fa_slen)) &&
+ if ((index >= (1ul << fa->fa_slen)) &&
((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen != KEYLENGTH)))
- continue;
+ continue;
if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
continue;
if (fi->fib_dead)