[IPV4]: Convert FIB Trie to RCU.

* Removes RW-lock
* Proteced read functions uses
  rcu_dereference proteced with rcu_read_lock()
* writing of procted pointer w. rcu_assigen_pointer
* Insert/Replace atomic list_replace_rcu
* A BUG_ON condition removed.in trie_rebalance

With help from Paul E. McKenney.

Signed-off-by: Robert Olsson <Robert.Olsson@data.slu.se>
Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
Signed-off-by: David S. Miller <davem@davemloft.net>

1 files changed, 202 insertions, 187 deletions

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 9c4c7f0367b0..ff21748248e4 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -43,7 +43,7 @@
  *              2 of the License, or (at your option) any later version.
  */
 
-#define VERSION "0.325"
+#define VERSION "0.402"
 
 #include <linux/config.h>
 #include <asm/uaccess.h>
@@ -62,6 +62,7 @@
 #include <linux/netdevice.h>
 #include <linux/if_arp.h>
 #include <linux/proc_fs.h>
+#include <linux/rcupdate.h>
 #include <linux/skbuff.h>
 #include <linux/netlink.h>
 #include <linux/init.h>
@@ -81,22 +82,19 @@
 #define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
 #define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset))
 
-static DEFINE_RWLOCK(fib_lock);
-
 typedef unsigned int t_key;
 
 #define T_TNODE 0
 #define T_LEAF  1
 #define NODE_TYPE_MASK  0x1UL
 #define NODE_PARENT(node) \
-        ((struct tnode *)((node)->parent & ~NODE_TYPE_MASK))
-#define NODE_SET_PARENT(node, ptr) \
-        ((node)->parent = (((unsigned long)(ptr)) | \
-                     ((node)->parent & NODE_TYPE_MASK)))
-#define NODE_INIT_PARENT(node, type) \
-        ((node)->parent = (type))
-#define NODE_TYPE(node) \
-        ((node)->parent & NODE_TYPE_MASK)
+        ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK)))
+
+#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
+
+#define NODE_SET_PARENT(node, ptr)              \
+        rcu_assign_pointer((node)->parent,      \
+                           ((unsigned long)(ptr)) | NODE_TYPE(node))
 
 #define IS_TNODE(n) (!(n->parent & T_LEAF))
 #define IS_LEAF(n) (n->parent & T_LEAF)
@@ -110,10 +108,12 @@ struct leaf {
         t_key key;
         unsigned long parent;
         struct hlist_head list;
+        struct rcu_head rcu;
 };
 
 struct leaf_info {
         struct hlist_node hlist;
+        struct rcu_head rcu;
         int plen;
         struct list_head falh;
 };
@@ -125,6 +125,7 @@ struct tnode {
         unsigned short bits:5;          /* 2log(KEYLENGTH) bits needed */
         unsigned short full_children;   /* KEYLENGTH bits needed */
         unsigned short empty_children;  /* KEYLENGTH bits needed */
+        struct rcu_head rcu;
         struct node *child[0];
 };
 
@@ -168,11 +169,14 @@ static void trie_dump_seq(struct seq_file *seq, struct trie *t);
 static kmem_cache_t *fn_alias_kmem;
 static struct trie *trie_local = NULL, *trie_main = NULL;
 
+
+/* rcu_read_lock needs to be hold by caller from readside */
+
 static inline struct node *tnode_get_child(struct tnode *tn, int i)
 {
         BUG_ON(i >= 1 << tn->bits);
 
-        return tn->child[i];
+        return rcu_dereference(tn->child[i]);
 }
 
 static inline int tnode_child_length(const struct tnode *tn)
@@ -213,14 +217,6 @@ static inline int tkey_mismatch(t_key a, int offset, t_key b)
         return i;
 }
 
-/* Candidate for fib_semantics */
-
-static void fn_free_alias(struct fib_alias *fa)
-{
-        fib_release_info(fa->fa_info);
-        kmem_cache_free(fn_alias_kmem, fa);
-}
-
 /*
   To understand this stuff, an understanding of keys and all their bits is 
   necessary. Every node in the trie has a key associated with it, but not 
@@ -292,53 +288,57 @@ static inline void check_tnode(const struct tnode *tn)
 static int halve_threshold = 25;
 static int inflate_threshold = 50;
 
-static struct leaf *leaf_new(void)
+
+static void __alias_free_mem(struct rcu_head *head)
 {
-        struct leaf *l = kmalloc(sizeof(struct leaf),  GFP_KERNEL);
-        if (l) {
-                NODE_INIT_PARENT(l, T_LEAF);
-                INIT_HLIST_HEAD(&l->list);
-        }
-        return l;
+        struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
+        kmem_cache_free(fn_alias_kmem, fa);
 }
 
-static struct leaf_info *leaf_info_new(int plen)
+static inline void alias_free_mem_rcu(struct fib_alias *fa)
 {
-        struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
-
-        if (!li)
-                return NULL;
+        call_rcu(&fa->rcu, __alias_free_mem);
+}
 
-        li->plen = plen;
-        INIT_LIST_HEAD(&li->falh);
+static void __leaf_free_rcu(struct rcu_head *head)
+{
+        kfree(container_of(head, struct leaf, rcu));
+}
 
-        return li;
+static inline void free_leaf(struct leaf *leaf)
+{
+        call_rcu(&leaf->rcu, __leaf_free_rcu);
 }
 
-static inline void free_leaf(struct leaf *l)
+static void __leaf_info_free_rcu(struct rcu_head *head)
 {
-        kfree(l);
+        kfree(container_of(head, struct leaf_info, rcu));
 }
 
-static inline void free_leaf_info(struct leaf_info *li)
+static inline void free_leaf_info(struct leaf_info *leaf)
 {
-        kfree(li);
+        call_rcu(&leaf->rcu, __leaf_info_free_rcu);
 }
 
 static struct tnode *tnode_alloc(unsigned int size)
 {
-        if (size <= PAGE_SIZE) {
-                return kmalloc(size, GFP_KERNEL);
-        } else {
-                return (struct tnode *)
-                        __get_free_pages(GFP_KERNEL, get_order(size));
-        }
+        struct page *pages;
+
+        if (size <= PAGE_SIZE)
+                return kcalloc(size, 1, GFP_KERNEL);
+
+        pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
+        if (!pages)
+                return NULL;
+
+        return page_address(pages);
 }
 
-static void __tnode_free(struct tnode *tn)
+static void __tnode_free_rcu(struct rcu_head *head)
 {
+        struct tnode *tn = container_of(head, struct tnode, rcu);
         unsigned int size = sizeof(struct tnode) +
-                                (1 << tn->bits) * sizeof(struct node *);
+                (1 << tn->bits) * sizeof(struct node *);
 
         if (size <= PAGE_SIZE)
                 kfree(tn);
@@ -346,6 +346,31 @@ static void __tnode_free(struct tnode *tn)
                 free_pages((unsigned long)tn, get_order(size));
 }
 
+static inline void tnode_free(struct tnode *tn)
+{
+        call_rcu(&tn->rcu, __tnode_free_rcu);
+}
+
+static struct leaf *leaf_new(void)
+{
+        struct leaf *l = kmalloc(sizeof(struct leaf),  GFP_KERNEL);
+        if (l) {
+                l->parent = T_LEAF;
+                INIT_HLIST_HEAD(&l->list);
+        }
+        return l;
+}
+
+static struct leaf_info *leaf_info_new(int plen)
+{
+        struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
+        if (li) {
+                li->plen = plen;
+                INIT_LIST_HEAD(&li->falh);
+        }
+        return li;
+}
+
 static struct tnode* tnode_new(t_key key, int pos, int bits)
 {
         int nchildren = 1<<bits;
@@ -354,7 +379,7 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
 
         if (tn) {
                 memset(tn, 0, sz);
-                NODE_INIT_PARENT(tn, T_TNODE);
+                tn->parent = T_TNODE;
                 tn->pos = pos;
                 tn->bits = bits;
                 tn->key = key;
@@ -367,17 +392,6 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
         return tn;
 }
 
-static void tnode_free(struct tnode *tn)
-{
-        if (IS_LEAF(tn)) {
-                free_leaf((struct leaf *)tn);
-                pr_debug("FL %p \n", tn);
-        } else {
-                __tnode_free(tn);
-                pr_debug("FT %p \n", tn);
-        }
-}
-
 /*
  * Check whether a tnode 'n' is "full", i.e. it is an internal node
  * and no bits are skipped. See discussion in dyntree paper p. 6
@@ -403,13 +417,11 @@ static inline void put_child(struct trie *t, struct tnode *tn, int i, struct nod
 
 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
 {
-        struct node *chi;
+        struct node *chi = tn->child[i];
         int isfull;
 
         BUG_ON(i >= 1<<tn->bits);
 
-        write_lock_bh(&fib_lock);
-        chi = tn->child[i];
 
         /* update emptyChildren */
         if (n == NULL && chi != NULL)
@@ -430,8 +442,7 @@ static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int w
         if (n)
                 NODE_SET_PARENT(n, tn);
 
-        tn->child[i] = n;
-        write_unlock_bh(&fib_lock);
+        rcu_assign_pointer(tn->child[i], n);
 }
 
 static struct node *resize(struct trie *t, struct tnode *tn)
@@ -456,17 +467,12 @@ static struct node *resize(struct trie *t, struct tnode *tn)
                 for (i = 0; i < tnode_child_length(tn); i++) {
                         struct node *n;
 
-                        write_lock_bh(&fib_lock);
                         n = tn->child[i];
-                        if (!n) {
-                                write_unlock_bh(&fib_lock);
+                        if (!n)
                                 continue;
-                        }
 
                         /* compress one level */
-                        NODE_INIT_PARENT(n, NODE_TYPE(n));
-
-                        write_unlock_bh(&fib_lock);
+                        NODE_SET_PARENT(n, NULL);
                         tnode_free(tn);
                         return n;
                 }
@@ -577,24 +583,17 @@ static struct node *resize(struct trie *t, struct tnode *tn)
 
 
         /* Only one child remains */
-
         if (tn->empty_children == tnode_child_length(tn) - 1)
                 for (i = 0; i < tnode_child_length(tn); i++) {
                         struct node *n;
 
-                        write_lock_bh(&fib_lock);
-
                         n = tn->child[i];
-                        if (!n) {
-                                write_unlock_bh(&fib_lock);
+                        if (!n)
                                 continue;
-                        }
 
                         /* compress one level */
 
-                        NODE_INIT_PARENT(n, NODE_TYPE(n));
-
-                        write_unlock_bh(&fib_lock);
+                        NODE_SET_PARENT(n, NULL);
                         tnode_free(tn);
                         return n;
                 }
@@ -831,19 +830,22 @@ static void trie_init(struct trie *t)
                 return;
 
         t->size = 0;
-        t->trie = NULL;
+        rcu_assign_pointer(t->trie, NULL);
         t->revision = 0;
 #ifdef CONFIG_IP_FIB_TRIE_STATS
         memset(&t->stats, 0, sizeof(struct trie_use_stats));
 #endif
 }
 
+/* readside most use rcu_read_lock currently dump routines
+ via get_fa_head and dump */
+
 static struct leaf_info *find_leaf_info(struct hlist_head *head, int plen)
 {
         struct hlist_node *node;
         struct leaf_info *li;
 
-        hlist_for_each_entry(li, node, head, hlist)
+        hlist_for_each_entry_rcu(li, node, head, hlist)
                 if (li->plen == plen)
                         return li;
 
@@ -862,28 +864,27 @@ static inline struct list_head * get_fa_head(struct leaf *l, int plen)
 
 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
 {
-        struct leaf_info *li = NULL, *last = NULL;
-        struct hlist_node *node;
+        struct leaf_info *li = NULL, *last = NULL;
+        struct hlist_node *node;
 
-        write_lock_bh(&fib_lock);
+        if (hlist_empty(head)) {
+                hlist_add_head_rcu(&new->hlist, head);
+        } else {
+                hlist_for_each_entry(li, node, head, hlist) {
+                        if (new->plen > li->plen)
+                                break;
 
-        if (hlist_empty(head)) {
-                hlist_add_head(&new->hlist, head);
-        } else {
-                hlist_for_each_entry(li, node, head, hlist) {
-                        if (new->plen > li->plen)
-                                break;
-
-                        last = li;
-                }
-                if (last)
-                        hlist_add_after(&last->hlist, &new->hlist);
-                else
-                        hlist_add_before(&new->hlist, &li->hlist);
-        }
-        write_unlock_bh(&fib_lock);
+                        last = li;
+                }
+                if (last)
+                        hlist_add_after_rcu(&last->hlist, &new->hlist);
+                else
+                        hlist_add_before_rcu(&new->hlist, &li->hlist);
+        }
 }
 
+/* rcu_read_lock needs to be hold by caller from readside */
+
 static struct leaf *
 fib_find_node(struct trie *t, u32 key)
 {
@@ -892,7 +893,7 @@ fib_find_node(struct trie *t, u32 key)
         struct node *n;
 
         pos = 0;
-        n = t->trie;
+        n = rcu_dereference(t->trie);
 
         while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
                 tn = (struct tnode *) n;
@@ -915,17 +916,13 @@ fib_find_node(struct trie *t, u32 key)
 
 static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
 {
-        int i;
         int wasfull;
         t_key cindex, key;
         struct tnode *tp = NULL;
 
         key = tn->key;
-        i = 0;
 
         while (tn != NULL && NODE_PARENT(tn) != NULL) {
-                BUG_ON(i > 12); /* Why is this a bug? -ojn */
-                i++;
 
                 tp = NODE_PARENT(tn);
                 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
@@ -945,6 +942,8 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
         return (struct node*) tn;
 }
 
+/* only used from updater-side */
+
 static  struct list_head *
 fib_insert_node(struct trie *t, int *err, u32 key, int plen)
 {
@@ -1081,7 +1080,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
                         cindex = tkey_extract_bits(key, tp->pos, tp->bits);
                         put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
                 } else {
-                        t->trie = (struct node*) tn; /* First tnode */
+                        rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
                         tp = tn;
                 }
         }
@@ -1091,7 +1090,8 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
                        tp, tp->pos, tp->bits, key, plen);
 
         /* Rebalance the trie */
-        t->trie = trie_rebalance(t, tp);
+
+        rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
 done:
         t->revision++;
 err:
@@ -1166,16 +1166,21 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
                         struct fib_info *fi_drop;
                         u8 state;
 
-                        write_lock_bh(&fib_lock);
+                        err = -ENOBUFS;
+                        new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
+                        if (new_fa == NULL)
+                                goto out;
 
                         fi_drop = fa->fa_info;
-                        fa->fa_info = fi;
-                        fa->fa_type = type;
-                        fa->fa_scope = r->rtm_scope;
+                        new_fa->fa_tos = fa->fa_tos;
+                        new_fa->fa_info = fi;
+                        new_fa->fa_type = type;
+                        new_fa->fa_scope = r->rtm_scope;
                         state = fa->fa_state;
-                        fa->fa_state &= ~FA_S_ACCESSED;
+                        new_fa->fa_state &= ~FA_S_ACCESSED;
 
-                        write_unlock_bh(&fib_lock);
+                        list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
+                        alias_free_mem_rcu(fa);
 
                         fib_release_info(fi_drop);
                         if (state & FA_S_ACCESSED)
@@ -1227,11 +1232,8 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
                         goto out_free_new_fa;
         }
 
-        write_lock_bh(&fib_lock);
-
-        list_add_tail(&new_fa->fa_list, (fa ? &fa->fa_list : fa_head));
-
-        write_unlock_bh(&fib_lock);
+        list_add_tail_rcu(&new_fa->fa_list,
+                          (fa ? &fa->fa_list : fa_head));
 
         rt_cache_flush(-1);
         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, nlhdr, req);
@@ -1246,6 +1248,8 @@ err:
         return err;
 }
 
+
+/* should be clalled with rcu_read_lock */
 static inline int check_leaf(struct trie *t, struct leaf *l,
                              t_key key, int *plen, const struct flowi *flp,
                              struct fib_result *res)
@@ -1256,7 +1260,7 @@ static inline int check_leaf(struct trie *t, struct leaf *l,
         struct hlist_head *hhead = &l->list;
         struct hlist_node *node;
 
-        hlist_for_each_entry(li, node, hhead, hlist) {
+        hlist_for_each_entry_rcu(li, node, hhead, hlist) {
                 i = li->plen;
                 mask = ntohl(inet_make_mask(i));
                 if (l->key != (key & mask))
@@ -1292,10 +1296,9 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
         t_key node_prefix, key_prefix, pref_mismatch;
         int mp;
 
-        n = t->trie;
-
-        read_lock(&fib_lock);
+        rcu_read_lock();
 
+        n = rcu_dereference(t->trie);
         if (!n)
                 goto failed;
 
@@ -1465,10 +1468,11 @@ backtrace:
 failed:
         ret = 1;
 found:
-        read_unlock(&fib_lock);
+        rcu_read_unlock();
         return ret;
 }
 
+/* only called from updater side */
 static int trie_leaf_remove(struct trie *t, t_key key)
 {
         t_key cindex;
@@ -1503,15 +1507,17 @@ static int trie_leaf_remove(struct trie *t, t_key key)
         t->revision++;
         t->size--;
 
+        preempt_disable();
         tp = NODE_PARENT(n);
         tnode_free((struct tnode *) n);
 
         if (tp) {
                 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
                 put_child(t, (struct tnode *)tp, cindex, NULL);
-                t->trie = trie_rebalance(t, tp);
+                rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
         } else
-                t->trie = NULL;
+                rcu_assign_pointer(t->trie, NULL);
+        preempt_enable();
 
         return 1;
 }
@@ -1527,7 +1533,6 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
         struct fib_alias *fa, *fa_to_delete;
         struct list_head *fa_head;
         struct leaf *l;
-        int kill_li = 0;
         struct leaf_info *li;
 
 
@@ -1560,6 +1565,7 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
 
         fa_to_delete = NULL;
         fa_head = fa->fa_list.prev;
+
         list_for_each_entry(fa, fa_head, fa_list) {
                 struct fib_info *fi = fa->fa_info;
 
@@ -1587,18 +1593,12 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
         l = fib_find_node(t, key);
         li = find_leaf_info(&l->list, plen);
 
-        write_lock_bh(&fib_lock);
-
-        list_del(&fa->fa_list);
+        list_del_rcu(&fa->fa_list);
 
         if (list_empty(fa_head)) {
-                hlist_del(&li->hlist);
-                kill_li = 1;
-        }
-        write_unlock_bh(&fib_lock);
-
-        if (kill_li)
+                hlist_del_rcu(&li->hlist);
                 free_leaf_info(li);
+        }
 
         if (hlist_empty(&l->list))
                 trie_leaf_remove(t, key);
@@ -1606,7 +1606,8 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
         if (fa->fa_state & FA_S_ACCESSED)
                 rt_cache_flush(-1);
 
-        fn_free_alias(fa);
+        fib_release_info(fa->fa_info);
+        alias_free_mem_rcu(fa);
         return 0;
 }
 
@@ -1618,12 +1619,10 @@ static int trie_flush_list(struct trie *t, struct list_head *head)
         list_for_each_entry_safe(fa, fa_node, head, fa_list) {
                 struct fib_info *fi = fa->fa_info;
 
-                if (fi && (fi->fib_flags&RTNH_F_DEAD)) {
-                        write_lock_bh(&fib_lock);
-                        list_del(&fa->fa_list);
-                        write_unlock_bh(&fib_lock);
-
-                        fn_free_alias(fa);
+                if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
+                        list_del_rcu(&fa->fa_list);
+                        fib_release_info(fa->fa_info);
+                        alias_free_mem_rcu(fa);
                         found++;
                 }
         }
@@ -1641,30 +1640,30 @@ static int trie_flush_leaf(struct trie *t, struct leaf *l)
                 found += trie_flush_list(t, &li->falh);
 
                 if (list_empty(&li->falh)) {
-                        write_lock_bh(&fib_lock);
-                        hlist_del(&li->hlist);
-                        write_unlock_bh(&fib_lock);
-
+                        hlist_del_rcu(&li->hlist);
                         free_leaf_info(li);
                 }
         }
         return found;
 }
 
+/* rcu_read_lock needs to be hold by caller from readside */
+
 static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
 {
         struct node *c = (struct node *) thisleaf;
         struct tnode *p;
         int idx;
+        struct node *trie = rcu_dereference(t->trie);
 
         if (c == NULL) {
-                if (t->trie == NULL)
+                if (trie == NULL)
                         return NULL;
 
-                if (IS_LEAF(t->trie))          /* trie w. just a leaf */
-                        return (struct leaf *) t->trie;
+                if (IS_LEAF(trie))          /* trie w. just a leaf */
+                        return (struct leaf *) trie;
 
-                p = (struct tnode*) t->trie;  /* Start */
+                p = (struct tnode*) trie;  /* Start */
         } else
                 p = (struct tnode *) NODE_PARENT(c);
 
@@ -1679,23 +1678,26 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
 
                 last = 1 << p->bits;
                 for (idx = pos; idx < last ; idx++) {
-                        if (!p->child[idx])
+                        c = rcu_dereference(p->child[idx]);
+
+                        if (!c)
                                 continue;
 
                         /* Decend if tnode */
-                        while (IS_TNODE(p->child[idx])) {
-                                p = (struct tnode*) p->child[idx];
-                                idx = 0;
+                        while (IS_TNODE(c)) {
+                                p = (struct tnode *) c;
+                                idx = 0;
 
                                 /* Rightmost non-NULL branch */
                                 if (p && IS_TNODE(p))
-                                        while (p->child[idx] == NULL && idx < (1 << p->bits)) idx++;
+                                        while (!(c = rcu_dereference(p->child[idx]))
+                                               && idx < (1<<p->bits)) idx++;
 
                                 /* Done with this tnode? */
-                                if (idx >= (1 << p->bits) || p->child[idx] == NULL)
+                                if (idx >= (1 << p->bits) || !c)
                                         goto up;
                         }
-                        return (struct leaf*) p->child[idx];
+                        return (struct leaf *) c;
                 }
 up:
                 /* No more children go up one step  */
@@ -1713,6 +1715,7 @@ static int fn_trie_flush(struct fib_table *tb)
 
         t->revision++;
 
+        rcu_read_lock();
         for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
                 found += trie_flush_leaf(t, l);
 
@@ -1720,6 +1723,7 @@ static int fn_trie_flush(struct fib_table *tb)
                         trie_leaf_remove(t, ll->key);
                 ll = l;
         }
+        rcu_read_unlock();  
 
         if (ll && hlist_empty(&ll->list))
                 trie_leaf_remove(t, ll->key);
@@ -1745,7 +1749,7 @@ fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib
         last_resort = NULL;
         order = -1;
 
-        read_lock(&fib_lock);
+        rcu_read_lock();
 
         l = fib_find_node(t, 0);
         if (!l)
@@ -1758,7 +1762,7 @@ fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib
         if (list_empty(fa_head))
                 goto out;
 
-        list_for_each_entry(fa, fa_head, fa_list) {
+        list_for_each_entry_rcu(fa, fa_head, fa_list) {
                 struct fib_info *next_fi = fa->fa_info;
 
                 if (fa->fa_scope != res->scope ||
@@ -1809,7 +1813,7 @@ fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib
         }
         trie_last_dflt = last_idx;
  out:;
-        read_unlock(&fib_lock);
+        rcu_read_unlock();
 }
 
 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
@@ -1823,7 +1827,9 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi
         s_i = cb->args[3];
         i = 0;
 
-        list_for_each_entry(fa, fah, fa_list) {
+        /* rcu_read_lock is hold by caller */
+
+        list_for_each_entry_rcu(fa, fah, fa_list) {
                 if (i < s_i) {
                         i++;
                         continue;
@@ -1898,7 +1904,7 @@ static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlin
 
         s_m = cb->args[1];
 
-        read_lock(&fib_lock);
+        rcu_read_lock();
         for (m = 0; m <= 32; m++) {
                 if (m < s_m)
                         continue;
@@ -1911,11 +1917,11 @@ static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlin
                         goto out;
                 }
         }
-        read_unlock(&fib_lock);
+        rcu_read_unlock();
         cb->args[1] = m;
         return skb->len;
 out:
-        read_unlock(&fib_lock);
+        rcu_read_unlock();
         return -1;
 }
 
@@ -2016,7 +2022,7 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
                                 putspace_seq(seq, indent+2);
                                 seq_printf(seq, "{/%d...dumping}\n", i);
 
-                                list_for_each_entry(fa, fa_head, fa_list) {
+                                list_for_each_entry_rcu(fa, fa_head, fa_list) {
                                         putspace_seq(seq, indent+2);
                                         if (fa->fa_info == NULL) {
                                                 seq_printf(seq, "Error fa_info=NULL\n");
@@ -2056,28 +2062,28 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
 
 static void trie_dump_seq(struct seq_file *seq, struct trie *t)
 {
-        struct node *n = t->trie;
+        struct node *n;
         int cindex = 0;
         int indent = 1;
         int pend = 0;
         int depth = 0;
         struct tnode *tn;
 
-        read_lock(&fib_lock);
-
+        rcu_read_lock();
+        n = rcu_dereference(t->trie);
         seq_printf(seq, "------ trie_dump of t=%p ------\n", t);
 
         if (!n) {
                 seq_printf(seq, "------ trie is empty\n");
 
-                read_unlock(&fib_lock);
+                rcu_read_unlock();
                 return;
         }
 
         printnode_seq(seq, indent, n, pend, cindex, 0);
 
         if (!IS_TNODE(n)) {
-                read_unlock(&fib_lock);
+                rcu_read_unlock();
                 return;
         }
 
@@ -2088,26 +2094,32 @@ static void trie_dump_seq(struct seq_file *seq, struct trie *t)
         depth++;
 
         while (tn && cindex < (1 << tn->bits)) {
-                if (tn->child[cindex]) {
+                struct node *child = rcu_dereference(tn->child[cindex]);
+                if (!child)
+                        cindex++;
+                else {
                         /* Got a child */
+                        printnode_seq(seq, indent, child, pend,
+                                      cindex, tn->bits);
 
-                        printnode_seq(seq, indent, tn->child[cindex], pend, cindex, tn->bits);
-                        if (IS_LEAF(tn->child[cindex])) {
+                        if (IS_LEAF(child))
                                 cindex++;
-                        } else {
+
+                        else {
                                 /*
                                  * New tnode. Decend one level
                                  */
 
                                 depth++;
-                                tn = (struct tnode *)tn->child[cindex];
-                                pend = tn->pos + tn->bits;
-                                putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
+                                n = child;
+                                tn = (struct tnode *)n;
+                                pend = tn->pos+tn->bits;
+                                putspace_seq(seq, indent);
+                                seq_printf(seq, "\\--\n");
                                 indent += 3;
                                 cindex = 0;
                         }
-                } else
-                        cindex++;
+                }
 
                 /*
                  * Test if we are done
@@ -2132,8 +2144,7 @@ static void trie_dump_seq(struct seq_file *seq, struct trie *t)
                         depth--;
                 }
         }
-
-        read_unlock(&fib_lock);
+        rcu_read_unlock();
 }
 
 static struct trie_stat *trie_stat_new(void)
@@ -2159,7 +2170,7 @@ static struct trie_stat *trie_stat_new(void)
 
 static struct trie_stat *trie_collect_stats(struct trie *t)
 {
-        struct node *n = t->trie;
+        struct node *n;
         struct trie_stat *s = trie_stat_new();
         int cindex = 0;
         int pend = 0;
@@ -2167,11 +2178,13 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
 
         if (!s)
                 return NULL;
+
+        rcu_read_lock();
+        n = rcu_dereference(t->trie);
+
         if (!n)
                 return s;
 
-        read_lock(&fib_lock);
-
         if (IS_TNODE(n)) {
                 struct tnode *tn = (struct tnode *)n;
                 pend = tn->pos+tn->bits;
@@ -2179,7 +2192,9 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
                 depth++;
 
                 while (tn && cindex < (1 << tn->bits)) {
-                        if (tn->child[cindex]) {
+                        struct node *ch = rcu_dereference(tn->child[cindex]);
+                        if (ch) {
+
                                 /* Got a child */
 
                                 if (IS_LEAF(tn->child[cindex])) {
@@ -2199,7 +2214,7 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
                                         s->nodesizes[tn->bits]++;
                                         depth++;
 
-                                        n = tn->child[cindex];
+                                        n = ch;
                                         tn = (struct tnode *)n;
                                         pend = tn->pos+tn->bits;
 
@@ -2236,7 +2251,7 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
                 }
         }
 
-        read_unlock(&fib_lock);
+        rcu_read_unlock();
         return s;
 }