netdev - [RFC PATCH 24/29] fib_trie: Update tnode_new to drop use of put_child

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20150224205036.26106.23633.stgit@ahduyck-vm-fedora20>
Date:	Tue, 24 Feb 2015 12:50:36 -0800
From:	Alexander Duyck <alexander.h.duyck@...hat.com>
To:	netdev@...r.kernel.org
Subject: [RFC PATCH 24/29] fib_trie: Update tnode_new to drop use of
 put_child_root

This change makes it so that the tnode_new function will now insert itself
into the parent.  This is to enable the eventual moving of fields from the
key_vector of the local node into the parent.

Signed-off-by: Alexander Duyck <alexander.h.duyck@...hat.com>
---
 net/ipv4/fib_trie.c |   47 +++++++++++++++++++++++++++++++++++------------
 1 file changed, 35 insertions(+), 12 deletions(-)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 65ea194..e91233b 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -437,40 +437,63 @@ static void leaf_init(struct key_vector *tn, t_key key, struct key_vector *l)
 	rcu_assign_pointer(tn->tnode, l);
 }
 
-static struct key_vector *tnode_new(struct key_vector *pn, t_key key,
+static struct key_vector *tnode_new(struct key_vector *tn, t_key key,
 				    int pos, int bits)
 {
 	size_t sz = TNODE_SIZE(1ul << bits);
 	struct tnode *tnode = tnode_alloc(sz);
-	struct key_vector *tn = tnode->kv;
 	unsigned int shift = pos + bits;
+	unsigned long i;
 
 	/* verify bits and pos their msb bits clear and values are valid */
 	BUG_ON(!bits || (shift > KEYLENGTH));
 
-	pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0),
-		 sizeof(struct key_vector *) << bits);
+	pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0), sz - TNODE_SIZE(0));
 
 	if (!tnode)
 		return NULL;
 
+	/* link tnode to parent */
+	NODE_INIT_PARENT(tnode->kv, tn);
+
+	/* update parent node stats */
+	if (!IS_TRIE(tn)) {
+		unsigned long idx = get_index(key, tn);
+		struct key_vector *n = get_child(tn + idx);
+
+		BUG_ON(idx >= child_length(tn));
+
+		if (!n)
+			empty_child_dec(tn);
+		else if (tnode_full(tn, n))
+			tn_info(tn)->full_children--;
+		if ((pos + bits) == tn->pos)
+			tn_info(tn)->full_children++;
+
+		/* update offset to correct key_vector for update */
+		tn += idx;
+	}
+
 	/* populate tn_info section */
+	key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
 	if (bits == KEYLENGTH)
 		tnode->full_children = 1;
 	else
 		tnode->empty_children = 1ul << bits;
 
+	/* populate keys as though we are full of leaves */
+	for (i = (1ul << bits); i--;)
+		tnode->kv[i].key = key + (i << pos);
+
 	/* populate key vector */
-	tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
-	tn->pos = pos;
-	tn->bits = bits;
-	tn->slen = pos;
+	tnode->kv[0].pos = pos;
+	tnode->kv[0].bits = bits;
+	tnode->kv[0].slen = pos;
 
 	/* link parent to node */
-	NODE_INIT_PARENT(tn, pn);
-	put_child_root(pn, tn->key, tn);
+	rcu_assign_pointer(tn->tnode, tnode->kv);
 
-	return tn;
+	return tnode->kv;
 }
 
 static struct key_vector *tnode_clone(struct tnode *oldtnode)
@@ -2256,7 +2279,7 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
 		fib_table_print(seq, iter->tb);
 
 	if (IS_TNODE(n)) {
-		__be32 prf = htonl(n->key);
+		__be32 prf = htonl((n->key >> n->pos) << n->pos);
 
 		seq_indent(seq, iter->depth-1);
 		seq_printf(seq, "  +-- %pI4/%zu %u %u %u\n",

--
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