| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Tue, 24 Feb 2015 12:50:49 -0800
From: Alexander Duyck <alexander.h.duyck@...hat.com>
To: netdev@...r.kernel.org
Subject: [RFC PATCH 26/29] fib_trie: Use put_child to only copy key_vectors
instead of pointers
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 <alexander.h.duyck@...hat.com>
---
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;
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists