summaryrefslogtreecommitdiff
path: root/net/ipv4/fib_trie.c
diff options
context:
space:
mode:
authorAlexander Duyck <alexander.h.duyck@redhat.com>2015-03-06 09:54:02 -0800
committerDavid S. Miller <davem@davemloft.net>2015-03-06 15:49:27 -0500
commit8d8e810ca8ec2541f30af916f0de1b41ac86ec4a (patch)
tree32faecb04a40fd452dda7e46b07199bd1dd5d3c5 /net/ipv4/fib_trie.c
parent72be72607a560dfa7a4715cb372f9e1e40ed65a5 (diff)
fib_trie: Return pointer to tnode pointer in resize/inflate/halve
Resize related functions now all return a pointer to the pointer that references the object that was resized. Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r--net/ipv4/fib_trie.c106
1 files changed, 65 insertions, 41 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 488cebc86631..752520747056 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);
}