[RFC PATCH 26/29] fib_trie: Use put_child to only copy key_vectors instead of pointers
From: Alexander Duyck <hidden>
Date: 2015-02-24 20:50:51
Subsystem:
networking [general], networking [ipv4/ipv6], the rest · Maintainers:
"David S. Miller", Eric Dumazet, Jakub Kicinski, Paolo Abeni, David Ahern, Ido Schimmel, Linus Torvalds
This change prepares put_child to copy key_vectors from one tnode to another. The only consumers for this are insert, inflate, halve, and collapse. The general idea is to make sure the empty/full statistics for the parent node remain correct when we copy a key_vector from one node to another. Signed-off-by: Alexander Duyck <redacted> --- net/ipv4/fib_trie.c | 102 +++++++++++++++++++++++++++------------------------ 1 file changed, 53 insertions(+), 49 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index a76cc6d..4a807fc 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c@@ -373,33 +373,34 @@ static void drop_child(struct key_vector *tn, t_key key) static void put_child(struct key_vector *tn, unsigned long i, struct key_vector *n) { - struct key_vector *chi = get_child(tn + i); - int isfull, wasfull; + struct key_vector *tnode = get_child(n); - BUG_ON(i >= child_length(tn)); - - /* update emptyChildren, overflow into fullChildren */ - if (n == NULL && chi != NULL) - empty_child_inc(tn); - if (n != NULL && chi == NULL) - empty_child_dec(tn); + if (!IS_TRIE(tn)) { + struct key_vector *chi = get_child(tn + i); - /* update fullChildren */ - wasfull = tnode_full(tn, chi); - isfull = tnode_full(tn, n); + BUG_ON(i >= child_length(tn)); - if (wasfull && !isfull) - tn_info(tn)->full_children--; - else if (!wasfull && isfull) - tn_info(tn)->full_children++; + /* update emptyChildren and fullChildren */ + if (chi) { + empty_child_inc(tn); + if (tnode_full(tn, chi)) + tn_info(tn)->full_children--; + } + if (tnode) { + empty_child_dec(tn); + if (tnode_full(tn, tnode)) + tn_info(tn)->full_children++; - if (n && (tn->slen < n->slen)) - tn->slen = n->slen; + /* update suffix length */ + if (tn->slen < tnode->slen) + tn->slen = tnode->slen; + } - /* update offset to correct key_vector for update */ - tn += i; + /* update offset to correct key_vector for update */ + tn += i; + } - rcu_assign_pointer(tn->tnode, n); + rcu_assign_pointer(tn->tnode, tnode); } static void update_children(struct key_vector *tn)
@@ -676,31 +677,32 @@ static struct key_vector *inflate(struct net *net, struct trie *t, * nodes. */ for (i = child_length(oldtnode), m = 1u << tn->pos; i;) { - struct key_vector *inode = get_child(oldtnode + --i); + struct key_vector *inode = oldtnode + --i; + struct key_vector *tnode = get_child(inode); struct key_vector *node0, *node1; unsigned long j, k; /* An empty child */ - if (inode == NULL) + if (!tnode) continue; /* A leaf or an internal node with skipped bits */ - if (!tnode_full(oldtnode, inode)) { - put_child(tn, get_index(inode->key, tn), inode); + if (!tnode_full(oldtnode, tnode)) { + put_child(tn, get_index(tnode->key, tn), inode); continue; } /* drop the node in the old tnode free list */ - tnode_free_append(oldtnode, inode); + tnode_free_append(oldtnode, tnode); /* An internal node with two children */ - if (inode->bits == 1) { - put_child(tn, 2 * i + 1, get_child(inode + 1)); - put_child(tn, 2 * i, get_child(inode)); + if (tnode->bits == 1) { + put_child(tn, 2 * i + 1, tnode + 1); + put_child(tn, 2 * i, tnode); continue; } - /* We will replace this node 'inode' with two new + /* We will replace this node 'tnode' with two new * ones, 'node0' and 'node1', each with half of the * original children. The two new nodes will have * a position one bit further down the key and this
@@ -714,12 +716,12 @@ static struct key_vector *inflate(struct net *net, struct trie *t, * node0 and node1. So... we synthesize that bit in the * two new keys. */ - node1 = tnode_new(tn, inode->key | m, - inode->pos, inode->bits - 1); + node1 = tnode_new(tn, tnode->key | m, + tnode->pos, tnode->bits - 1); if (!node1) goto nomem; - node0 = tnode_new(tn, inode->key, - inode->pos, inode->bits - 1); + node0 = tnode_new(tn, tnode->key, + tnode->pos, tnode->bits - 1); tnode_free_append(tn, node1); if (!node0)
@@ -727,11 +729,11 @@ static struct key_vector *inflate(struct net *net, struct trie *t, tnode_free_append(tn, node0); /* populate child pointers in new nodes */ - for (k = child_length(inode), j = k / 2; j;) { - put_child(node1, --j, get_child(inode + --k)); - put_child(node0, j, get_child(inode + j)); - put_child(node1, --j, get_child(inode + --k)); - put_child(node0, j, get_child(inode + j)); + for (k = child_length(tnode), j = k / 2; j;) { + put_child(node1, --j, tnode + --k); + put_child(node0, j, tnode + j); + put_child(node1, --j, tnode + --k); + put_child(node0, j, tnode + j); } }
@@ -773,18 +775,23 @@ static struct key_vector *halve(struct net *net, struct trie *t, * nodes. */ for (i = child_length(oldtnode); i;) { - struct key_vector *node1 = get_child(oldtnode + --i); - struct key_vector *node0 = get_child(oldtnode + --i); + struct key_vector *node1 = oldtnode + --i; + struct key_vector *node0 = oldtnode + --i; + struct key_vector *tnode = get_child(node0); struct key_vector *inode; /* At least one of the children is empty */ - if (!node1 || !node0) { - put_child(tn, i / 2, node1 ? : node0); + if (!get_child(node1)) { + put_child(tn, i / 2, node0); + continue; + } + if (!get_child(node0)) { + put_child(tn, i / 2, node1); continue; } /* Two nonempty children */ - inode = tnode_new(tn, node0->key, oldtnode->pos, 1); + inode = tnode_new(tn, tnode->key, oldtnode->pos, 1); if (!inode) goto nomem; tnode_free_append(tn, inode);
@@ -827,10 +834,7 @@ static struct key_vector *collapse(struct net *net, struct trie *t, return node_parent(oldtnode); /* compress one level */ - if (IS_TRIE(pn)) - rcu_assign_pointer(pn->tnode, n); - else - put_child(pn, get_index(oldtnode->key, pn), n); + put_child(pn, get_index(oldtnode->key, pn), oldtnode + i); /* drop dead node */ vector_replace(net, node_parent(oldtnode), pn);
@@ -1180,7 +1184,7 @@ static struct fib_table *fib_insert_node(struct net *net, struct trie *t, goto notnode; /* initialize routes out of node */ - put_child(tn, get_index(key, tn) ^ 1, n); + put_child(tn, get_index(key, tn) ^ 1, tp + get_index(key, tp)); /* pop back out to bring tn to the same level as tp */ n = tn;