Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux...

[pandora-kernel.git] / net / ipv4 / fib_trie.c

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index a96e5ec..b144508 100644 (file)
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -16,7 +16,7 @@
  *
  * An experimental study of compression methods for dynamic tries
  * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
- * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
+ * http://www.csc.kth.se/~snilsson/software/dyntrie2/
  *
  *
  * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
@@ -1342,7 +1342,7 @@ err:
 /* should be called with rcu_read_lock */
 static int check_leaf(struct trie *t, struct leaf *l,
                      t_key key,  const struct flowi *flp,
-                     struct fib_result *res)
+                     struct fib_result *res, int fib_flags)
 {
        struct leaf_info *li;
        struct hlist_head *hhead = &l->list;
@@ -1356,7 +1356,7 @@ static int check_leaf(struct trie *t, struct leaf *l,
                if (l->key != (key & ntohl(mask)))
                        continue;
 
-               err = fib_semantic_match(&li->falh, flp, res, plen);
+               err = fib_semantic_match(&li->falh, flp, res, plen, fib_flags);
 
 #ifdef CONFIG_IP_FIB_TRIE_STATS
                if (err <= 0)
@@ -1372,7 +1372,7 @@ static int check_leaf(struct trie *t, struct leaf *l,
 }
 
 int fib_table_lookup(struct fib_table *tb, const struct flowi *flp,
-                    struct fib_result *res)
+                    struct fib_result *res, int fib_flags)
 {
        struct trie *t = (struct trie *) tb->tb_data;
        int ret;
@@ -1384,8 +1384,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi *flp,
        t_key cindex = 0;
        int current_prefix_length = KEYLENGTH;
        struct tnode *cn;
-       t_key node_prefix, key_prefix, pref_mismatch;
-       int mp;
+       t_key pref_mismatch;
 
        rcu_read_lock();
 
@@ -1399,7 +1398,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi *flp,
 
        /* Just a leaf? */
        if (IS_LEAF(n)) {
-               ret = check_leaf(t, (struct leaf *)n, key, flp, res);
+               ret = check_leaf(t, (struct leaf *)n, key, flp, res, fib_flags);
                goto found;
        }
 
@@ -1424,7 +1423,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi *flp,
                }
 
                if (IS_LEAF(n)) {
-                       ret = check_leaf(t, (struct leaf *)n, key, flp, res);
+                       ret = check_leaf(t, (struct leaf *)n, key, flp, res, fib_flags);
                        if (ret > 0)
                                goto backtrace;
                        goto found;
@@ -1500,10 +1499,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi *flp,
                 * matching prefix.
                 */
 
-               node_prefix = mask_pfx(cn->key, cn->pos);
-               key_prefix = mask_pfx(key, cn->pos);
-               pref_mismatch = key_prefix^node_prefix;
-               mp = 0;
+               pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
 
                /*
                 * In short: If skipped bits in this node do not match
@@ -1511,13 +1507,9 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi *flp,
                 * state.directly.
                 */
                if (pref_mismatch) {
-                       while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
-                               mp++;
-                               pref_mismatch = pref_mismatch << 1;
-                       }
-                       key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
+                       int mp = KEYLENGTH - fls(pref_mismatch);
 
-                       if (key_prefix != 0)
+                       if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
                                goto backtrace;
 
                        if (current_prefix_length >= cn->pos)
@@ -1846,7 +1838,8 @@ void fib_table_select_default(struct fib_table *tb,
                if (!next_fi->fib_nh[0].nh_gw ||
                    next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
                        continue;
-               fa->fa_state |= FA_S_ACCESSED;
+
+               fib_alias_accessed(fa);
 
                if (fi == NULL) {
                        if (next_fi != res->fi)