diff options
Diffstat (limited to 'net')
-rw-r--r-- | net/ipv4/fib_trie.c | 106 |
1 files changed, 65 insertions, 41 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 488cebc..7525207 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -144,7 +144,7 @@ struct trie { #endif }; -static void resize(struct trie *t, struct tnode *tn); +static struct tnode **resize(struct trie *t, struct tnode *tn); static size_t tnode_free_size; /* @@ -468,9 +468,11 @@ static void tnode_free(struct tnode *tn) } } -static void replace(struct trie *t, struct tnode *oldtnode, struct tnode *tn) +static struct tnode __rcu **replace(struct trie *t, struct tnode *oldtnode, + struct tnode *tn) { struct tnode *tp = node_parent(oldtnode); + struct tnode **cptr; unsigned long i; /* setup the parent pointer out of and back into this node */ @@ -483,6 +485,9 @@ static void replace(struct trie *t, struct tnode *oldtnode, struct tnode *tn) /* all pointers should be clean so we are done */ tnode_free(oldtnode); + /* record the pointer that is pointing to this node */ + cptr = tp ? tp->tnode : &t->trie; + /* resize children now that oldtnode is freed */ for (i = tnode_child_length(tn); i;) { struct tnode *inode = tnode_get_child(tn, --i); @@ -491,9 +496,11 @@ static void replace(struct trie *t, struct tnode *oldtnode, struct tnode *tn) if (tnode_full(tn, inode)) resize(t, inode); } + + return cptr; } -static int inflate(struct trie *t, struct tnode *oldtnode) +static struct tnode __rcu **inflate(struct trie *t, struct tnode *oldtnode) { struct tnode *tn; unsigned long i; @@ -503,7 +510,7 @@ static int inflate(struct trie *t, struct tnode *oldtnode) tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1); if (!tn) - return -ENOMEM; + goto notnode; /* prepare oldtnode to be freed */ tnode_free_init(oldtnode); @@ -580,16 +587,15 @@ static int inflate(struct trie *t, struct tnode *oldtnode) } /* setup the parent pointers into and out of this node */ - replace(t, oldtnode, tn); - - return 0; + return replace(t, oldtnode, tn); nomem: /* all pointers should be clean so we are done */ tnode_free(tn); - return -ENOMEM; +notnode: + return NULL; } -static int halve(struct trie *t, struct tnode *oldtnode) +static struct tnode __rcu **halve(struct trie *t, struct tnode *oldtnode) { struct tnode *tn; unsigned long i; @@ -598,7 +604,7 @@ static int halve(struct trie *t, struct tnode *oldtnode) tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1); if (!tn) - return -ENOMEM; + goto notnode; /* prepare oldtnode to be freed */ tnode_free_init(oldtnode); @@ -621,10 +627,8 @@ static int halve(struct trie *t, struct tnode *oldtnode) /* Two nonempty children */ inode = tnode_new(node0->key, oldtnode->pos, 1); - if (!inode) { - tnode_free(tn); - return -ENOMEM; - } + if (!inode) + goto nomem; tnode_free_append(tn, inode); /* initialize pointers out of node */ @@ -637,9 +641,12 @@ static int halve(struct trie *t, struct tnode *oldtnode) } /* setup the parent pointers into and out of this node */ - replace(t, oldtnode, tn); - - return 0; + return replace(t, oldtnode, tn); +nomem: + /* all pointers should be clean so we are done */ + tnode_free(tn); +notnode: + return NULL; } static void collapse(struct trie *t, struct tnode *oldtnode) @@ -796,10 +803,14 @@ static bool should_collapse(const struct tnode *tn) } #define MAX_WORK 10 -static void resize(struct trie *t, struct tnode *tn) +static struct tnode __rcu **resize(struct trie *t, struct tnode *tn) { +#ifdef CONFIG_IP_FIB_TRIE_STATS + struct trie_use_stats __percpu *stats = t->stats; +#endif struct tnode *tp = node_parent(tn); - struct tnode __rcu **cptr; + unsigned long cindex = tp ? get_index(tn->key, tp) : 0; + struct tnode __rcu **cptr = tp ? tp->tnode : &t->trie; int max_work = MAX_WORK; pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n", @@ -809,52 +820,57 @@ static void resize(struct trie *t, struct tnode *tn) * doing it ourselves. This way we can let RCU fully do its * thing without us interfering */ - cptr = tp ? &tp->tnode[get_index(tn->key, tp)] : &t->trie; - BUG_ON(tn != rtnl_dereference(*cptr)); + BUG_ON(tn != rtnl_dereference(cptr[cindex])); /* Double as long as the resulting node has a number of * nonempty nodes that are above the threshold. */ while (should_inflate(tp, tn) && max_work) { - if (inflate(t, tn)) { + struct tnode __rcu **tcptr = inflate(t, tn); + + if (!tcptr) { #ifdef CONFIG_IP_FIB_TRIE_STATS - this_cpu_inc(t->stats->resize_node_skipped); + this_cpu_inc(stats->resize_node_skipped); #endif break; } max_work--; - tn = rtnl_dereference(*cptr); + cptr = tcptr; + tn = rtnl_dereference(cptr[cindex]); } /* Return if at least one inflate is run */ if (max_work != MAX_WORK) - return; + return cptr; /* Halve as long as the number of empty children in this * node is above threshold. */ while (should_halve(tp, tn) && max_work) { - if (halve(t, tn)) { + struct tnode __rcu **tcptr = halve(t, tn); + + if (!tcptr) { #ifdef CONFIG_IP_FIB_TRIE_STATS - this_cpu_inc(t->stats->resize_node_skipped); + this_cpu_inc(stats->resize_node_skipped); #endif break; } max_work--; - tn = rtnl_dereference(*cptr); + cptr = tcptr; + tn = rtnl_dereference(cptr[cindex]); } /* Only one child remains */ if (should_collapse(tn)) { collapse(t, tn); - return; + return cptr; } /* Return if at least one deflate was run */ if (max_work != MAX_WORK) - return; + return cptr; /* push the suffix length to the parent node */ if (tn->slen > tn->pos) { @@ -863,6 +879,8 @@ static void resize(struct trie *t, struct tnode *tn) if (tp && (slen > tp->slen)) tp->slen = slen; } + + return cptr; } static void leaf_pull_suffix(struct tnode *tp, struct tnode *l) @@ -952,16 +970,18 @@ static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 slen, static void trie_rebalance(struct trie *t, struct tnode *tn) { - struct tnode *tp; + struct tnode __rcu **cptr = &t->trie; while (tn) { - tp = node_parent(tn); - resize(t, tn); - tn = tp; + struct tnode *tp = node_parent(tn); + + cptr = resize(t, tn); + if (!tp) + break; + tn = container_of(cptr, struct tnode, tnode[0]); } } -/* only used from updater-side */ static int fib_insert_node(struct trie *t, struct tnode *tp, struct fib_alias *new, t_key key) { @@ -969,7 +989,7 @@ static int fib_insert_node(struct trie *t, struct tnode *tp, l = leaf_new(key, new); if (!l) - return -ENOMEM; + goto noleaf; /* retrieve child from parent node */ if (tp) @@ -987,10 +1007,8 @@ static int fib_insert_node(struct trie *t, struct tnode *tp, struct tnode *tn; tn = tnode_new(key, __fls(key ^ n->key), 1); - if (!tn) { - node_free(l); - return -ENOMEM; - } + if (!tn) + goto notnode; /* initialize routes out of node */ NODE_INIT_PARENT(tn, tp); @@ -1010,6 +1028,10 @@ static int fib_insert_node(struct trie *t, struct tnode *tp, trie_rebalance(t, tp); return 0; +notnode: + node_free(l); +noleaf: + return -ENOMEM; } static int fib_insert_alias(struct trie *t, struct tnode *tp, @@ -1642,18 +1664,20 @@ backtrace: /* walk trie in reverse order */ do { while (!(cindex--)) { + struct tnode __rcu **cptr; t_key pkey = pn->key; n = pn; pn = node_parent(n); /* resize completed node */ - resize(t, n); + cptr = resize(t, n); /* if we got the root we are done */ if (!pn) goto flush_complete; + pn = container_of(cptr, struct tnode, tnode[0]); cindex = get_index(pkey, pn); } |