Merge branch 'release' of git://git.kernel.org/pub/scm/linux/kernel/git/aegl/linux-2.6

[linux-2.6-omap-h63xx.git] / net / ipv4 / fib_trie.c

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 90ae70870a1035bf5c4f2d492977a96a4876d1f3..ccd3efc6a173bc45ad189a9bca84d76d594f9eff 100644 (file)
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -41,9 +41,16 @@
  *             modify it under the terms of the GNU General Public License
  *             as published by the Free Software Foundation; either version
  *             2 of the License, or (at your option) any later version.
+ *
+ * Substantial contributions to this work comes from:
+ *
+ *             David S. Miller, <davem@davemloft.net>
+ *             Stephen Hemminger <shemminger@osdl.org>
+ *             Paul E. McKenney <paulmck@us.ibm.com>
+ *             Patrick McHardy <kaber@trash.net>
  */
 
-#define VERSION "0.404"
+#define VERSION "0.406"
 
 #include <linux/config.h>
 #include <asm/uaccess.h>
@@ -59,6 +66,7 @@
 #include <linux/errno.h>
 #include <linux/in.h>
 #include <linux/inet.h>
+#include <linux/inetdevice.h>
 #include <linux/netdevice.h>
 #include <linux/if_arp.h>
 #include <linux/proc_fs.h>
@@ -76,7 +84,7 @@
 #include "fib_lookup.h"
 
 #undef CONFIG_IP_FIB_TRIE_STATS
-#define MAX_CHILDS 16384
+#define MAX_STAT_DEPTH 32
 
 #define KEYLENGTH (8*sizeof(t_key))
 #define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
@@ -146,7 +154,7 @@ struct trie_stat {
        unsigned int tnodes;
        unsigned int leaves;
        unsigned int nullpointers;
-       unsigned int nodesizes[MAX_CHILDS];
+       unsigned int nodesizes[MAX_STAT_DEPTH];
 };
 
 struct trie {
@@ -286,6 +294,8 @@ static inline void check_tnode(const struct tnode *tn)
 
 static int halve_threshold = 25;
 static int inflate_threshold = 50;
+static int halve_threshold_root = 15;
+static int inflate_threshold_root = 25; 
 
 
 static void __alias_free_mem(struct rcu_head *head)
@@ -449,6 +459,8 @@ static struct node *resize(struct trie *t, struct tnode *tn)
        int i;
        int err = 0;
        struct tnode *old_tn;
+       int inflate_threshold_use;
+       int halve_threshold_use;
 
        if (!tn)
                return NULL;
@@ -541,10 +553,17 @@ static struct node *resize(struct trie *t, struct tnode *tn)
 
        check_tnode(tn);
 
+       /* Keep root node larger  */
+
+       if(!tn->parent)
+               inflate_threshold_use = inflate_threshold_root;
+       else 
+               inflate_threshold_use = inflate_threshold;
+
        err = 0;
        while ((tn->full_children > 0 &&
               50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
-                               inflate_threshold * tnode_child_length(tn))) {
+                               inflate_threshold_use * tnode_child_length(tn))) {
 
                old_tn = tn;
                tn = inflate(t, tn);
@@ -564,10 +583,18 @@ static struct node *resize(struct trie *t, struct tnode *tn)
         * node is above threshold.
         */
 
+
+       /* Keep root node larger  */
+
+       if(!tn->parent)
+               halve_threshold_use = halve_threshold_root;
+       else 
+               halve_threshold_use = halve_threshold;
+
        err = 0;
        while (tn->bits > 1 &&
               100 * (tnode_child_length(tn) - tn->empty_children) <
-              halve_threshold * tnode_child_length(tn)) {
+              halve_threshold_use * tnode_child_length(tn)) {
 
                old_tn = tn;
                tn = halve(t, tn);
@@ -1086,7 +1113,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
        }
 
        if (tp && tp->pos + tp->bits > 32)
-               printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
+               printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
                       tp, tp->pos, tp->bits, key, plen);
 
        /* Rebalance the trie */
@@ -1832,16 +1859,7 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi
                        i++;
                        continue;
                }
-               if (fa->fa_info->fib_nh == NULL) {
-                       printk("Trie error _fib_nh=NULL in fa[%d] k=%08x plen=%d\n", i, key, plen);
-                       i++;
-                       continue;
-               }
-               if (fa->fa_info == NULL) {
-                       printk("Trie error fa_info=NULL in fa[%d] k=%08x plen=%d\n", i, key, plen);
-                       i++;
-                       continue;
-               }
+               BUG_ON(!fa->fa_info);
 
                if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
                                  cb->nlh->nlmsg_seq,
@@ -1964,7 +1982,7 @@ struct fib_table * __init fib_hash_init(int id)
                trie_main = t;
 
        if (id == RT_TABLE_LOCAL)
-               printk("IPv4 FIB: Using LC-trie version %s\n", VERSION);
+               printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
 
        return tb;
 }
@@ -2022,7 +2040,15 @@ rescan:
 static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
                                       struct trie *t)
 {
-       struct node *n = rcu_dereference(t->trie);
+       struct node *n ;
+
+       if(!t)
+               return NULL;
+
+       n = rcu_dereference(t->trie);
+
+       if(!iter)
+               return NULL;
 
        if (n && IS_TNODE(n)) {
                iter->tnode = (struct tnode *) n;
@@ -2054,7 +2080,9 @@ static void trie_collect_stats(struct trie *t, struct trie_stat *s)
                        int i;
 
                        s->tnodes++;
-                       s->nodesizes[tn->bits]++;
+                       if(tn->bits < MAX_STAT_DEPTH)
+                               s->nodesizes[tn->bits]++;
+
                        for (i = 0; i < (1<<tn->bits); i++)
                                if (!tn->child[i])
                                        s->nullpointers++;
@@ -2084,8 +2112,8 @@ static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
        seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
        bytes += sizeof(struct tnode) * stat->tnodes;
 
-       max = MAX_CHILDS-1;
-       while (max >= 0 && stat->nodesizes[max] == 0)
+       max = MAX_STAT_DEPTH;
+       while (max > 0 && stat->nodesizes[max-1] == 0)
                max--;
 
        pointers = 0;
@@ -2368,6 +2396,7 @@ static unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi)
  */
 static int fib_route_seq_show(struct seq_file *seq, void *v)
 {
+       const struct fib_trie_iter *iter = seq->private;
        struct leaf *l = v;
        int i;
        char bf[128];
@@ -2379,6 +2408,8 @@ static int fib_route_seq_show(struct seq_file *seq, void *v)
                return 0;
        }
 
+       if (iter->trie == trie_local)
+               return 0;
        if (IS_TNODE(l))
                return 0;
 
@@ -2394,7 +2425,7 @@ static int fib_route_seq_show(struct seq_file *seq, void *v)
                prefix = htonl(l->key);
 
                list_for_each_entry_rcu(fa, &li->falh, fa_list) {
-                       const struct fib_info *fi = rcu_dereference(fa->fa_info);
+                       const struct fib_info *fi = fa->fa_info;
                        unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
 
                        if (fa->fa_type == RTN_BROADCAST