X-Git-Url: https://err.no/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=net%2Fipv4%2Ffib_trie.c;h=b2dea4e5da77cfe2f00bf09cfaa5a0ec0e171ed5;hb=5d8c397f304e1363f8ff9749b08172eb59e6534a;hp=6f818cc7efd0e8dd5b58fb48cbfc16b5edca20f8;hpb=91b9a277fc4d207249e459a455abf804ebb5499d;p=linux-2.6 diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 6f818cc7ef..b2dea4e5da 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 #include @@ -62,6 +62,7 @@ #include #include #include +#include #include #include #include @@ -77,27 +78,23 @@ #undef CONFIG_IP_FIB_TRIE_STATS #define MAX_CHILDS 16384 -#define EXTRACT(p, n, str) ((str)<<(p)>>(32-(n))) #define KEYLENGTH (8*sizeof(t_key)) #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) @@ -111,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; }; @@ -126,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]; }; @@ -158,37 +158,28 @@ struct trie { unsigned int revision; }; -static int trie_debug = 0; - -#define DBG(x...) do { if (trie_debug) printk(x); } while (0) - -static int tnode_full(struct tnode *tn, struct node *n); static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); -static int tnode_child_length(struct tnode *tn); static struct node *resize(struct trie *t, struct tnode *tn); -static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err); -static struct tnode *halve(struct trie *t, struct tnode *tn, int *err); +static struct tnode *inflate(struct trie *t, struct tnode *tn); +static struct tnode *halve(struct trie *t, struct tnode *tn); static void tnode_free(struct tnode *tn); static void trie_dump_seq(struct seq_file *seq, struct trie *t); -extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio); -extern int fib_detect_death(struct fib_info *fi, int order, - struct fib_info **last_resort, int *last_idx, int *dflt); - -extern void rtmsg_fib(int event, u32 key, struct fib_alias *fa, int z, int tb_id, - struct nlmsghdr *n, struct netlink_skb_parms *req); -static kmem_cache_t *fn_alias_kmem; +static kmem_cache_t *fn_alias_kmem __read_mostly; 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(struct tnode *tn) +static inline int tnode_child_length(const struct tnode *tn) { return 1 << tn->bits; } @@ -226,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 @@ -297,63 +280,65 @@ static void fn_free_alias(struct fib_alias *fa) */ -static void check_tnode(struct tnode *tn) +static inline void check_tnode(const struct tnode *tn) { - if (tn && tn->pos+tn->bits > 32) { - printk("TNODE ERROR tn=%p, pos=%d, bits=%d\n", tn, tn->pos, tn->bits); - } + WARN_ON(tn && tn->pos+tn->bits > 32); } 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); @@ -361,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<parent = T_TNODE; tn->pos = pos; tn->bits = bits; tn->key = key; @@ -377,30 +387,17 @@ static struct tnode* tnode_new(t_key key, int pos, int bits) tn->empty_children = 1<child[i]; int isfull; - if (i >= 1<bits) { - printk("bits=%d, i=%d\n", tn->bits, i); - BUG(); - } - write_lock_bh(&fib_lock); - chi = tn->child[i]; + BUG_ON(i >= 1<bits); + /* update emptyChildren */ if (n == NULL && chi != NULL) @@ -449,20 +442,20 @@ 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) { int i; int err = 0; + struct tnode *old_tn; if (!tn) return NULL; - DBG("In tnode_resize %p inflate_threshold=%d threshold=%d\n", - tn, inflate_threshold, halve_threshold); + pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n", + tn, inflate_threshold, halve_threshold); /* No children */ if (tn->empty_children == tnode_child_length(tn)) { @@ -474,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; } @@ -559,9 +547,10 @@ static struct node *resize(struct trie *t, struct tnode *tn) 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >= inflate_threshold * tnode_child_length(tn))) { - tn = inflate(t, tn, &err); - - if (err) { + old_tn = tn; + tn = inflate(t, tn); + if (IS_ERR(tn)) { + tn = old_tn; #ifdef CONFIG_IP_FIB_TRIE_STATS t->stats.resize_node_skipped++; #endif @@ -581,9 +570,10 @@ static struct node *resize(struct trie *t, struct tnode *tn) 100 * (tnode_child_length(tn) - tn->empty_children) < halve_threshold * tnode_child_length(tn)) { - tn = halve(t, tn, &err); - - if (err) { + old_tn = tn; + tn = halve(t, tn); + if (IS_ERR(tn)) { + tn = old_tn; #ifdef CONFIG_IP_FIB_TRIE_STATS t->stats.resize_node_skipped++; #endif @@ -593,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; } @@ -618,21 +601,19 @@ static struct node *resize(struct trie *t, struct tnode *tn) return (struct node *) tn; } -static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err) +static struct tnode *inflate(struct trie *t, struct tnode *tn) { struct tnode *inode; struct tnode *oldtnode = tn; int olen = tnode_child_length(tn); int i; - DBG("In inflate\n"); + pr_debug("In inflate\n"); tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); - if (!tn) { - *err = -ENOMEM; - return oldtnode; - } + if (!tn) + return ERR_PTR(-ENOMEM); /* * Preallocate and store tnodes before the actual work so we @@ -653,39 +634,22 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err) left = tnode_new(inode->key&(~m), inode->pos + 1, inode->bits - 1); - - if (!left) { - *err = -ENOMEM; - break; - } + if (!left) + goto nomem; right = tnode_new(inode->key|m, inode->pos + 1, inode->bits - 1); - if (!right) { - *err = -ENOMEM; - break; - } + if (!right) { + tnode_free(left); + goto nomem; + } put_child(t, tn, 2*i, (struct node *) left); put_child(t, tn, 2*i+1, (struct node *) right); } } - if (*err) { - int size = tnode_child_length(tn); - int j; - - for (j = 0; j < size; j++) - if (tn->child[j]) - tnode_free((struct tnode *)tn->child[j]); - - tnode_free(tn); - - *err = -ENOMEM; - return oldtnode; - } - for (i = 0; i < olen; i++) { struct node *node = tnode_get_child(oldtnode, i); struct tnode *left, *right; @@ -763,23 +727,34 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err) } tnode_free(oldtnode); return tn; +nomem: + { + int size = tnode_child_length(tn); + int j; + + for (j = 0; j < size; j++) + if (tn->child[j]) + tnode_free((struct tnode *)tn->child[j]); + + tnode_free(tn); + + return ERR_PTR(-ENOMEM); + } } -static struct tnode *halve(struct trie *t, struct tnode *tn, int *err) +static struct tnode *halve(struct trie *t, struct tnode *tn) { struct tnode *oldtnode = tn; struct node *left, *right; int i; int olen = tnode_child_length(tn); - DBG("In halve\n"); + pr_debug("In halve\n"); tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); - if (!tn) { - *err = -ENOMEM; - return oldtnode; - } + if (!tn) + return ERR_PTR(-ENOMEM); /* * Preallocate and store tnodes before the actual work so we @@ -793,30 +768,17 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err) right = tnode_get_child(oldtnode, i+1); /* Two nonempty children */ - if (left && right) { - struct tnode *newBinNode = - tnode_new(left->key, tn->pos + tn->bits, 1); + if (left && right) { + struct tnode *newn; - if (!newBinNode) { - *err = -ENOMEM; - break; - } - put_child(t, tn, i/2, (struct node *)newBinNode); - } - } - - if (*err) { - int size = tnode_child_length(tn); - int j; + newn = tnode_new(left->key, tn->pos + tn->bits, 1); - for (j = 0; j < size; j++) - if (tn->child[j]) - tnode_free((struct tnode *)tn->child[j]); + if (!newn) + goto nomem; - tnode_free(tn); + put_child(t, tn, i/2, (struct node *)newn); + } - *err = -ENOMEM; - return oldtnode; } for (i = 0; i < olen; i += 2) { @@ -831,7 +793,7 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err) continue; put_child(t, tn, i/2, right); continue; - } + } if (right == NULL) { put_child(t, tn, i/2, left); @@ -841,15 +803,25 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err) /* Two nonempty children */ newBinNode = (struct tnode *) tnode_get_child(tn, i/2); put_child(t, tn, i/2, NULL); - - BUG_ON(!newBinNode); - put_child(t, newBinNode, 0, left); put_child(t, newBinNode, 1, right); put_child(t, tn, i/2, resize(t, newBinNode)); } tnode_free(oldtnode); return tn; +nomem: + { + int size = tnode_child_length(tn); + int j; + + for (j = 0; j < size; j++) + if (tn->child[j]) + tnode_free((struct tnode *)tn->child[j]); + + tnode_free(tn); + + return ERR_PTR(-ENOMEM); + } } static void trie_init(struct trie *t) @@ -858,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; @@ -889,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) { @@ -919,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; @@ -942,29 +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; - BUG_ON(!tn); - key = tn->key; - i = 0; while (tn != NULL && NODE_PARENT(tn) != NULL) { - if (i > 10) { - printk("Rebalance tn=%p \n", tn); - if (tn) - printk("tn->parent=%p \n", NODE_PARENT(tn)); - - printk("Rebalance tp=%p \n", tp); - if (tp) - printk("tp->parent=%p \n", NODE_PARENT(tp)); - } - - BUG_ON(i > 12); /* Why is this a bug? -ojn */ - i++; tp = NODE_PARENT(tn); cindex = tkey_extract_bits(key, tp->pos, tp->bits); @@ -984,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) { @@ -1027,10 +987,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen) pos = tn->pos + tn->bits; n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); - if (n && NODE_PARENT(n) != tn) { - printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n)); - BUG(); - } + BUG_ON(n && NODE_PARENT(n) != tn); } else break; } @@ -1084,8 +1041,6 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen) NODE_SET_PARENT(l, tp); - BUG_ON(!tp); - cindex = tkey_extract_bits(key, tp->pos, tp->bits); put_child(t, (struct tnode *)tp, cindex, (struct node *)l); } else { @@ -1125,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; } } @@ -1135,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,7 +1122,7 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, key = ntohl(key); - DBG("Insert table=%d %08x/%d\n", tb->tb_id, key, plen); + pr_debug("Insert table=%d %08x/%d\n", tb->tb_id, key, plen); mask = ntohl(inet_make_mask(plen)); @@ -1210,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) @@ -1271,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); @@ -1290,7 +1248,10 @@ err: return err; } -static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int *plen, const struct flowi *flp, + +/* 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) { int err, i; @@ -1299,7 +1260,7 @@ static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int *pl 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)) @@ -1335,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; @@ -1508,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; @@ -1519,7 +1480,7 @@ static int trie_leaf_remove(struct trie *t, t_key key) struct node *n = t->trie; struct leaf *l; - DBG("entering trie_leaf_remove(%p)\n", n); + pr_debug("entering trie_leaf_remove(%p)\n", n); /* Note that in the case skipped bits, those bits are *not* checked! * When we finish this, we will have NULL or a T_LEAF, and the @@ -1531,10 +1492,7 @@ static int trie_leaf_remove(struct trie *t, t_key key) check_tnode(tn); n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); - if (n && NODE_PARENT(n) != tn) { - printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n)); - BUG(); - } + BUG_ON(n && NODE_PARENT(n) != tn); } l = (struct leaf *) n; @@ -1549,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; } @@ -1573,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; @@ -1602,10 +1561,11 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, if (!fa) return -ESRCH; - DBG("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t); + pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t); 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; @@ -1633,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); @@ -1652,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; } @@ -1664,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++; } } @@ -1687,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); @@ -1725,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<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 */ @@ -1759,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); @@ -1766,11 +1723,12 @@ 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); - DBG("trie_flush found=%d\n", found); + pr_debug("trie_flush found=%d\n", found); return found; } @@ -1791,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) @@ -1804,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 || @@ -1855,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, @@ -1869,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; @@ -1944,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; @@ -1957,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; } @@ -2062,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"); @@ -2102,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; } @@ -2134,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 @@ -2178,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) @@ -2205,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; @@ -2213,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; @@ -2225,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])) { @@ -2245,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; @@ -2282,7 +2251,7 @@ static struct trie_stat *trie_collect_stats(struct trie *t) } } - read_unlock(&fib_lock); + rcu_read_unlock(); return s; }