summaryrefslogtreecommitdiff
path: root/net/ipv4/fib_trie.c
diff options
context:
space:
mode:
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r--net/ipv4/fib_trie.c240
1 files changed, 129 insertions, 111 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index f6cdc012eec5..ea294fffb9ce 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;