diff options
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r-- | net/ipv4/fib_trie.c | 258 |
1 files changed, 139 insertions, 119 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index f6cdc012eec5..4b02d14e7ab9 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -122,7 +122,10 @@ struct tnode { unsigned char bits; /* 2log(KEYLENGTH) bits needed */ unsigned int full_children; /* KEYLENGTH bits needed */ unsigned int empty_children; /* KEYLENGTH bits needed */ - struct rcu_head rcu; + union { + struct rcu_head rcu; + struct work_struct work; + }; struct node *child[0]; }; @@ -160,7 +163,6 @@ static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, static struct node *resize(struct trie *t, struct tnode *tn); 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 struct kmem_cache *fn_alias_kmem __read_mostly; static struct kmem_cache *trie_leaf_kmem __read_mostly; @@ -334,6 +336,11 @@ static void __leaf_free_rcu(struct rcu_head *head) kmem_cache_free(trie_leaf_kmem, l); } +static inline void free_leaf(struct leaf *l) +{ + call_rcu_bh(&l->rcu, __leaf_free_rcu); +} + static void __leaf_info_free_rcu(struct rcu_head *head) { kfree(container_of(head, struct leaf_info, rcu)); @@ -346,16 +353,16 @@ static inline void free_leaf_info(struct leaf_info *leaf) static struct tnode *tnode_alloc(size_t size) { - struct page *pages; - if (size <= PAGE_SIZE) return kzalloc(size, GFP_KERNEL); + else + return __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL); +} - pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size)); - if (!pages) - return NULL; - - return page_address(pages); +static void __tnode_vfree(struct work_struct *arg) +{ + struct tnode *tn = container_of(arg, struct tnode, work); + vfree(tn); } static void __tnode_free_rcu(struct rcu_head *head) @@ -366,16 +373,17 @@ static void __tnode_free_rcu(struct rcu_head *head) if (size <= PAGE_SIZE) kfree(tn); - else - free_pages((unsigned long)tn, get_order(size)); + else { + INIT_WORK(&tn->work, __tnode_vfree); + schedule_work(&tn->work); + } } static inline void tnode_free(struct tnode *tn) { - if (IS_LEAF(tn)) { - struct leaf *l = (struct leaf *) tn; - call_rcu_bh(&l->rcu, __leaf_free_rcu); - } else + if (IS_LEAF(tn)) + free_leaf((struct leaf *) tn); + else call_rcu(&tn->rcu, __tnode_free_rcu); } @@ -1086,7 +1094,7 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen) li = leaf_info_new(plen); if (!li) { - tnode_free((struct tnode *) l); + free_leaf(l); return NULL; } @@ -1122,7 +1130,7 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen) if (!tn) { free_leaf_info(li); - tnode_free((struct tnode *) l); + free_leaf(l); return NULL; } @@ -1578,7 +1586,7 @@ static void trie_leaf_remove(struct trie *t, struct leaf *l) } else rcu_assign_pointer(t->trie, NULL); - tnode_free((struct tnode *) l); + free_leaf(l); } /* @@ -1665,7 +1673,7 @@ static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg) return 0; } -static int trie_flush_list(struct trie *t, struct list_head *head) +static int trie_flush_list(struct list_head *head) { struct fib_alias *fa, *fa_node; int found = 0; @@ -1683,7 +1691,7 @@ static int trie_flush_list(struct trie *t, struct list_head *head) return found; } -static int trie_flush_leaf(struct trie *t, struct leaf *l) +static int trie_flush_leaf(struct leaf *l) { int found = 0; struct hlist_head *lih = &l->list; @@ -1691,7 +1699,7 @@ static int trie_flush_leaf(struct trie *t, struct leaf *l) struct leaf_info *li = NULL; hlist_for_each_entry_safe(li, node, tmp, lih, hlist) { - found += trie_flush_list(t, &li->falh); + found += trie_flush_list(&li->falh); if (list_empty(&li->falh)) { hlist_del_rcu(&li->hlist); @@ -1782,7 +1790,7 @@ static int fn_trie_flush(struct fib_table *tb) int found = 0; for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) { - found += trie_flush_leaf(t, l); + found += trie_flush_leaf(l); if (ll && hlist_empty(&ll->list)) trie_leaf_remove(t, ll); @@ -2029,9 +2037,8 @@ struct fib_table *fib_hash_table(u32 id) /* Depth first Trie walk iterator */ struct fib_trie_iter { struct seq_net_private p; - struct trie *trie_local, *trie_main; + struct fib_table *tb; struct tnode *tnode; - struct trie *trie; unsigned index; unsigned depth; }; @@ -2084,31 +2091,26 @@ rescan: static struct node *fib_trie_get_first(struct fib_trie_iter *iter, struct trie *t) { - struct node *n ; + struct node *n; if (!t) return NULL; n = rcu_dereference(t->trie); - - if (!iter) + if (!n) return NULL; - if (n) { - if (IS_TNODE(n)) { - iter->tnode = (struct tnode *) n; - iter->trie = t; - iter->index = 0; - iter->depth = 1; - } else { - iter->tnode = NULL; - iter->trie = t; - iter->index = 0; - iter->depth = 0; - } - return n; + if (IS_TNODE(n)) { + iter->tnode = (struct tnode *) n; + iter->index = 0; + iter->depth = 1; + } else { + iter->tnode = NULL; + iter->index = 0; + iter->depth = 0; } - return NULL; + + return n; } static void trie_collect_stats(struct trie *t, struct trie_stat *s) @@ -2119,8 +2121,7 @@ static void trie_collect_stats(struct trie *t, struct trie_stat *s) memset(s, 0, sizeof(*s)); rcu_read_lock(); - for (n = fib_trie_get_first(&iter, t); n; - n = fib_trie_get_next(&iter)) { + for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) { if (IS_LEAF(n)) { struct leaf *l = (struct leaf *)n; struct leaf_info *li; @@ -2209,36 +2210,48 @@ static void trie_show_usage(struct seq_file *seq, } #endif /* CONFIG_IP_FIB_TRIE_STATS */ -static void fib_trie_show(struct seq_file *seq, const char *name, - struct trie *trie) +static void fib_table_print(struct seq_file *seq, struct fib_table *tb) { - struct trie_stat stat; - - trie_collect_stats(trie, &stat); - seq_printf(seq, "%s:\n", name); - trie_show_stats(seq, &stat); -#ifdef CONFIG_IP_FIB_TRIE_STATS - trie_show_usage(seq, &trie->stats); -#endif + if (tb->tb_id == RT_TABLE_LOCAL) + seq_puts(seq, "Local:\n"); + else if (tb->tb_id == RT_TABLE_MAIN) + seq_puts(seq, "Main:\n"); + else + seq_printf(seq, "Id %d:\n", tb->tb_id); } + static int fib_triestat_seq_show(struct seq_file *seq, void *v) { struct net *net = (struct net *)seq->private; - struct fib_table *tb; + unsigned int h; seq_printf(seq, "Basic info: size of leaf:" " %Zd bytes, size of tnode: %Zd bytes.\n", sizeof(struct leaf), sizeof(struct tnode)); - tb = fib_get_table(net, RT_TABLE_LOCAL); - if (tb) - fib_trie_show(seq, "Local", (struct trie *) tb->tb_data); + for (h = 0; h < FIB_TABLE_HASHSZ; h++) { + struct hlist_head *head = &net->ipv4.fib_table_hash[h]; + struct hlist_node *node; + struct fib_table *tb; + + hlist_for_each_entry_rcu(tb, node, head, tb_hlist) { + struct trie *t = (struct trie *) tb->tb_data; + struct trie_stat stat; + + if (!t) + continue; - tb = fib_get_table(net, RT_TABLE_MAIN); - if (tb) - fib_trie_show(seq, "Main", (struct trie *) tb->tb_data); + fib_table_print(seq, tb); + + trie_collect_stats(t, &stat); + trie_show_stats(seq, &stat); +#ifdef CONFIG_IP_FIB_TRIE_STATS + trie_show_usage(seq, &t->stats); +#endif + } + } return 0; } @@ -2274,67 +2287,79 @@ static const struct file_operations fib_triestat_fops = { .release = fib_triestat_seq_release, }; -static struct node *fib_trie_get_idx(struct fib_trie_iter *iter, - loff_t pos) +static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos) { + struct fib_trie_iter *iter = seq->private; + struct net *net = seq_file_net(seq); loff_t idx = 0; - struct node *n; + unsigned int h; - for (n = fib_trie_get_first(iter, iter->trie_local); - n; ++idx, n = fib_trie_get_next(iter)) { - if (pos == idx) - return n; - } + for (h = 0; h < FIB_TABLE_HASHSZ; h++) { + struct hlist_head *head = &net->ipv4.fib_table_hash[h]; + struct hlist_node *node; + struct fib_table *tb; - for (n = fib_trie_get_first(iter, iter->trie_main); - n; ++idx, n = fib_trie_get_next(iter)) { - if (pos == idx) - return n; + hlist_for_each_entry_rcu(tb, node, head, tb_hlist) { + struct node *n; + + for (n = fib_trie_get_first(iter, + (struct trie *) tb->tb_data); + n; n = fib_trie_get_next(iter)) + if (pos == idx++) { + iter->tb = tb; + return n; + } + } } + return NULL; } static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos) __acquires(RCU) { - struct fib_trie_iter *iter = seq->private; - struct fib_table *tb; - - if (!iter->trie_local) { - tb = fib_get_table(iter->p.net, RT_TABLE_LOCAL); - if (tb) - iter->trie_local = (struct trie *) tb->tb_data; - } - if (!iter->trie_main) { - tb = fib_get_table(iter->p.net, RT_TABLE_MAIN); - if (tb) - iter->trie_main = (struct trie *) tb->tb_data; - } rcu_read_lock(); - if (*pos == 0) - return SEQ_START_TOKEN; - return fib_trie_get_idx(iter, *pos - 1); + return fib_trie_get_idx(seq, *pos); } static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos) { struct fib_trie_iter *iter = seq->private; - void *l = v; + struct net *net = seq_file_net(seq); + struct fib_table *tb = iter->tb; + struct hlist_node *tb_node; + unsigned int h; + struct node *n; ++*pos; - if (v == SEQ_START_TOKEN) - return fib_trie_get_idx(iter, 0); - - v = fib_trie_get_next(iter); - BUG_ON(v == l); - if (v) - return v; + /* next node in same table */ + n = fib_trie_get_next(iter); + if (n) + return n; - /* continue scan in next trie */ - if (iter->trie == iter->trie_local) - return fib_trie_get_first(iter, iter->trie_main); + /* walk rest of this hash chain */ + h = tb->tb_id & (FIB_TABLE_HASHSZ - 1); + while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) { + tb = hlist_entry(tb_node, struct fib_table, tb_hlist); + n = fib_trie_get_first(iter, (struct trie *) tb->tb_data); + if (n) + goto found; + } + /* new hash chain */ + while (++h < FIB_TABLE_HASHSZ) { + struct hlist_head *head = &net->ipv4.fib_table_hash[h]; + hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) { + n = fib_trie_get_first(iter, (struct trie *) tb->tb_data); + if (n) + goto found; + } + } return NULL; + +found: + iter->tb = tb; + return n; } static void fib_trie_seq_stop(struct seq_file *seq, void *v) @@ -2391,22 +2416,15 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v) const struct fib_trie_iter *iter = seq->private; struct node *n = v; - if (v == SEQ_START_TOKEN) - return 0; - - if (!node_parent_rcu(n)) { - if (iter->trie == iter->trie_local) - seq_puts(seq, "<local>:\n"); - else - seq_puts(seq, "<main>:\n"); - } + if (!node_parent_rcu(n)) + fib_table_print(seq, iter->tb); if (IS_TNODE(n)) { struct tnode *tn = (struct tnode *) n; __be32 prf = htonl(mask_pfx(tn->key, tn->pos)); seq_indent(seq, iter->depth-1); - seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n", + seq_printf(seq, " +-- " NIPQUAD_FMT "/%d %d %d %d\n", NIPQUAD(prf), tn->pos, tn->bits, tn->full_children, tn->empty_children); @@ -2417,7 +2435,7 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v) __be32 val = htonl(l->key); seq_indent(seq, iter->depth); - seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val)); + seq_printf(seq, " |-- " NIPQUAD_FMT "\n", NIPQUAD(val)); hlist_for_each_entry_rcu(li, node, &l->list, hlist) { struct fib_alias *fa; @@ -2502,7 +2520,7 @@ static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos) struct fib_table *tb; rcu_read_lock(); - tb = fib_get_table(iter->p.net, RT_TABLE_MAIN); + tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN); if (!tb) return NULL; @@ -2584,15 +2602,16 @@ static int fib_route_seq_show(struct seq_file *seq, void *v) list_for_each_entry_rcu(fa, &li->falh, fa_list) { const struct fib_info *fi = fa->fa_info; unsigned flags = fib_flag_trans(fa->fa_type, mask, fi); - char bf[128]; + int len; if (fa->fa_type == RTN_BROADCAST || fa->fa_type == RTN_MULTICAST) continue; if (fi) - snprintf(bf, sizeof(bf), - "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u", + seq_printf(seq, + "%s\t%08X\t%08X\t%04X\t%d\t%u\t" + "%d\t%08X\t%d\t%u\t%u%n", fi->fib_dev ? fi->fib_dev->name : "*", prefix, fi->fib_nh->nh_gw, flags, 0, 0, @@ -2601,14 +2620,15 @@ static int fib_route_seq_show(struct seq_file *seq, void *v) (fi->fib_advmss ? fi->fib_advmss + 40 : 0), fi->fib_window, - fi->fib_rtt >> 3); + fi->fib_rtt >> 3, &len); else - snprintf(bf, sizeof(bf), - "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u", + seq_printf(seq, + "*\t%08X\t%08X\t%04X\t%d\t%u\t" + "%d\t%08X\t%d\t%u\t%u%n", prefix, 0, flags, 0, 0, 0, - mask, 0, 0, 0); + mask, 0, 0, 0, &len); - seq_printf(seq, "%-127s\n", bf); + seq_printf(seq, "%*s\n", 127 - len, ""); } } |