BUG_ON(i >= 1<<tn->bits);
-
/* update emptyChildren */
if (n == NULL && chi != NULL)
tn->empty_children++;
* and we need to allocate a new one of those as well.
*/
- if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
- struct fib_alias *fa_orig;
+ if (fa && fa->fa_tos == tos &&
+ fa->fa_info->fib_priority == fi->fib_priority) {
+ struct fib_alias *fa_first, *fa_match;
err = -EEXIST;
if (cfg->fc_nlflags & NLM_F_EXCL)
goto out;
+ /* We have 2 goals:
+ * 1. Find exact match for type, scope, fib_info to avoid
+ * duplicate routes
+ * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
+ */
+ fa_match = NULL;
+ fa_first = fa;
+ fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
+ list_for_each_entry_continue(fa, fa_head, fa_list) {
+ if (fa->fa_tos != tos)
+ break;
+ if (fa->fa_info->fib_priority != fi->fib_priority)
+ break;
+ if (fa->fa_type == cfg->fc_type &&
+ fa->fa_scope == cfg->fc_scope &&
+ fa->fa_info == fi) {
+ fa_match = fa;
+ break;
+ }
+ }
+
if (cfg->fc_nlflags & NLM_F_REPLACE) {
struct fib_info *fi_drop;
u8 state;
- if (fi->fib_treeref > 1)
+ fa = fa_first;
+ if (fa_match) {
+ if (fa == fa_match)
+ err = 0;
goto out;
-
+ }
err = -ENOBUFS;
new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
if (new_fa == NULL)
new_fa->fa_type = cfg->fc_type;
new_fa->fa_scope = cfg->fc_scope;
state = fa->fa_state;
- new_fa->fa_state &= ~FA_S_ACCESSED;
+ new_fa->fa_state = state & ~FA_S_ACCESSED;
list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
alias_free_mem_rcu(fa);
* uses the same scope, type, and nexthop
* information.
*/
- fa_orig = fa;
- list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
- if (fa->fa_tos != tos)
- break;
- if (fa->fa_info->fib_priority != fi->fib_priority)
- break;
- if (fa->fa_type == cfg->fc_type &&
- fa->fa_scope == cfg->fc_scope &&
- fa->fa_info == fi)
- goto out;
- }
+ if (fa_match)
+ goto out;
if (!(cfg->fc_nlflags & NLM_F_APPEND))
- fa = fa_orig;
+ fa = fa_first;
}
err = -ENOENT;
if (!(cfg->fc_nlflags & NLM_F_CREATE))
return err;
}
-
/* should be called with rcu_read_lock */
static int check_leaf(struct trie *t, struct leaf *l,
t_key key, const struct flowi *flp,
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);
-
- /* 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;
+ struct tnode *tp = node_parent((struct node *) l);
- /*
- * 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);
}
/*
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) {
+ fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
+ list_for_each_entry_continue(fa, fa_head, fa_list) {
struct fib_info *fi = fa->fa_info;
if (fa->fa_tos != tos)
}
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);
return NULL; /* Root of trie */
}
-
static struct leaf *trie_firstleaf(struct trie *t)
{
struct tnode *n = (struct tnode *) rcu_dereference(t->trie);
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;
{
int i, s_i;
struct fib_alias *fa;
-
__be32 xkey = htonl(key);
s_i = cb->args[4];
return skb->len;
}
-static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb,
- struct sk_buff *skb, struct netlink_callback *cb)
+static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
+ struct sk_buff *skb, struct netlink_callback *cb)
{
- int h, s_h;
- struct list_head *fa_head;
- struct leaf *l = NULL;
+ struct leaf_info *li;
+ struct hlist_node *node;
+ int i, s_i;
- s_h = cb->args[3];
- h = 0;
+ s_i = cb->args[3];
+ i = 0;
- for (l = trie_firstleaf(t); l != NULL; h++, l = trie_nextleaf(l)) {
- if (h < s_h)
+ /* rcu_read_lock is hold by caller */
+ hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
+ if (i < s_i) {
+ i++;
continue;
- if (h > s_h)
- memset(&cb->args[4], 0,
- sizeof(cb->args) - 4*sizeof(cb->args[0]));
-
- fa_head = get_fa_head(l, plen);
+ }
- if (!fa_head)
- continue;
+ if (i > s_i)
+ cb->args[4] = 0;
- if (list_empty(fa_head))
+ if (list_empty(&li->falh))
continue;
- if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb) < 0) {
- cb->args[3] = h;
+ if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
+ cb->args[3] = i;
return -1;
}
+ i++;
}
- cb->args[3] = h;
+
+ cb->args[3] = i;
return skb->len;
}
static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
struct netlink_callback *cb)
{
- int m, s_m;
+ struct leaf *l;
struct trie *t = (struct trie *) tb->tb_data;
-
- s_m = cb->args[2];
+ t_key key = cb->args[2];
rcu_read_lock();
- for (m = 0; m <= 32; m++) {
- if (m < s_m)
- continue;
- if (m > s_m)
- memset(&cb->args[3], 0,
- sizeof(cb->args) - 3*sizeof(cb->args[0]));
+ /* Dump starting at last key.
+ * Note: 0.0.0.0/0 (ie default) is first key.
+ */
+ if (!key)
+ l = trie_firstleaf(t);
+ else {
+ l = fib_find_node(t, key);
+ if (!l) {
+ /* The table changed during the dump, rather than
+ * giving partial data, just make application retry.
+ */
+ rcu_read_unlock();
+ return -EBUSY;
+ }
+ }
- if (fn_trie_dump_plen(t, 32-m, tb, skb, cb) < 0) {
- cb->args[2] = m;
- goto out;
+ while (l) {
+ cb->args[2] = l->key;
+ if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
+ rcu_read_unlock();
+ return -1;
}
+
+ l = trie_nextleaf(l);
+ memset(&cb->args[3], 0,
+ sizeof(cb->args) - 3*sizeof(cb->args[0]));
}
rcu_read_unlock();
- cb->args[2] = m;
+
return skb->len;
-out:
- rcu_read_unlock();
- return -1;
}
void __init fib_hash_init(void)
struct leaf *l = (struct leaf *) n;
struct leaf_info *li;
struct hlist_node *node;
-
__be32 val = htonl(l->key);
seq_indent(seq, iter->depth);
struct fib_alias *fa;
__be32 mask, prefix;
- if (!li)
- continue;
-
mask = inet_make_mask(li->plen);
prefix = htonl(l->key);
projects / linux-2.6-omap-h63xx.git / blobdiff