diff options
author | Stephen Hemminger <stephen.hemminger@vyatta.com> | 2008-01-23 05:56:34 (GMT) |
---|---|---|
committer | David S. Miller <davem@davemloft.net> | 2008-01-28 23:11:00 (GMT) |
commit | 9195bef7fb0ba0a91d5ffa566bcf8e007e3c7172 (patch) | |
tree | 417eb71596accb170cbd8cdc42598170e3024264 /net | |
parent | a88ee229253b31e3a844b30525ff77fbfe3111d3 (diff) | |
download | linux-fsl-qoriq-9195bef7fb0ba0a91d5ffa566bcf8e007e3c7172.tar.xz |
[IPV4] fib_trie: avoid extra search on delete
Get rid of extra search that made route deletion O(n).
Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net')
-rw-r--r-- | net/ipv4/fib_trie.c | 50 |
1 files changed, 12 insertions, 38 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 2ea94eb..441c4ea 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -1545,49 +1545,23 @@ found: return ret; } -/* only called from updater side */ -static int trie_leaf_remove(struct trie *t, t_key key) +/* + * Remove the leaf and return parent. + */ +static void trie_leaf_remove(struct trie *t, struct leaf *l) { - t_key cindex; - struct tnode *tp = NULL; - struct node *n = t->trie; - struct leaf *l; - - pr_debug("entering trie_leaf_remove(%p)\n", n); + struct tnode *tp = node_parent((struct node *) l); - /* 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 - * T_LEAF may or may not match our key. - */ - - while (n != NULL && IS_TNODE(n)) { - struct tnode *tn = (struct tnode *) n; - check_tnode(tn); - n = tnode_get_child(tn, tkey_extract_bits(key, - tn->pos, tn->bits)); - - BUG_ON(n && node_parent(n) != tn); - } - l = (struct leaf *) n; - - if (!n || !tkey_equals(l->key, key)) - return 0; - - /* - * Key found. - * Remove the leaf and rebalance the tree - */ - tp = node_parent(n); - tnode_free((struct tnode *) n); + pr_debug("entering trie_leaf_remove(%p)\n", l); if (tp) { - cindex = tkey_extract_bits(key, tp->pos, tp->bits); + t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits); put_child(t, (struct tnode *)tp, cindex, NULL); rcu_assign_pointer(t->trie, trie_rebalance(t, tp)); } else rcu_assign_pointer(t->trie, NULL); - return 1; + tnode_free((struct tnode *) l); } /* @@ -1665,7 +1639,7 @@ static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg) } if (hlist_empty(&l->list)) - trie_leaf_remove(t, key); + trie_leaf_remove(t, l); if (fa->fa_state & FA_S_ACCESSED) rt_cache_flush(-1); @@ -1778,19 +1752,19 @@ static struct leaf *trie_nextleaf(struct leaf *l) static int fn_trie_flush(struct fib_table *tb) { struct trie *t = (struct trie *) tb->tb_data; - struct leaf *ll = NULL, *l = NULL; + struct leaf *l, *ll = NULL; int found = 0; for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) { found += trie_flush_leaf(t, l); if (ll && hlist_empty(&ll->list)) - trie_leaf_remove(t, ll->key); + trie_leaf_remove(t, ll); ll = l; } if (ll && hlist_empty(&ll->list)) - trie_leaf_remove(t, ll->key); + trie_leaf_remove(t, ll); pr_debug("trie_flush found=%d\n", found); return found; |