netdev - [RFC PATCH 25/29] fib_trie: Add function for dropping children from trie

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20150224205043.26106.81972.stgit@ahduyck-vm-fedora20>
Date:	Tue, 24 Feb 2015 12:50:43 -0800
From:	Alexander Duyck <alexander.h.duyck@...hat.com>
To:	netdev@...r.kernel.org
Subject: [RFC PATCH 25/29] fib_trie: Add function for dropping children from
 trie

The freeing of tnodes and leaves becomes a special case when the
key_vectors for those nodes have been pushed up to the parent.  The
handling is pretty strait forward.  A removed node will have its' pointer
set to NULL and will require suffix length to be reset to pos when the
suffix and pos values have been moved into the parent key_vector array.

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

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index e91233b..a76cc6d 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -346,6 +346,27 @@ static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
 	return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
 }
 
+static void drop_child(struct key_vector *tn, t_key key)
+{
+	/* update parent tnode statistics */
+	if (!IS_TRIE(tn)) {
+		unsigned long i = get_index(key, tn);
+		struct key_vector *n = get_child(tn + i);
+
+		if (n) {
+			empty_child_inc(tn);
+			if (tnode_full(tn, n))
+				tn_info(tn)->full_children--;
+		}
+
+		/* update offset to correct key_vector for update */
+		tn += i;
+	}
+
+	/* clear tnode pointers */
+	RCU_INIT_POINTER(tn->tnode, NULL);
+}
+
 /* Add a child at position i overwriting the old value.
  * Update the value of full_children and empty_children.
  */
@@ -403,15 +424,6 @@ static void update_children(struct key_vector *tn)
 	}
 }
 
-static inline void put_child_root(struct key_vector *tp, t_key key,
-				  struct key_vector *n)
-{
-	if (IS_TRIE(tp))
-		rcu_assign_pointer(tp->tnode, n);
-	else
-		put_child(tp, get_index(key, tp), n);
-}
-
 static void leaf_init(struct key_vector *tn, t_key key, struct key_vector *l)
 {
 	/* link leaf to parent */
@@ -815,7 +827,10 @@ static struct key_vector *collapse(struct net *net, struct trie *t,
 			return node_parent(oldtnode);
 
 		/* compress one level */
-		put_child_root(pn, oldtnode->key, n);
+		if (IS_TRIE(pn))
+			rcu_assign_pointer(pn->tnode, n);
+		else
+			put_child(pn, get_index(oldtnode->key, pn), n);
 
 		/* drop dead node */
 		vector_replace(net, node_parent(oldtnode), pn);
@@ -826,7 +841,7 @@ static struct key_vector *collapse(struct net *net, struct trie *t,
 	}
 
 	/* no children, just update pointer to NULL */
-	put_child_root(pn, oldtnode->key, NULL);
+	drop_child(pn, oldtnode->key);
 	node_free(oldtnode);
 
 	return pn;
@@ -1565,7 +1580,7 @@ static void fib_remove_alias(struct net *net, struct trie *t,
 	 * out parent suffix lengths as a part of trie_rebalance
 	 */
 	if (hlist_empty(&l->leaf)) {
-		put_child_root(tp, l->key, NULL);
+		drop_child(tp, l->key);
 		node_free(l);
 		trie_rebalance(net, t, tp);
 		return;
@@ -1768,7 +1783,7 @@ int fib_table_flush(struct net *net, struct fib_table *tb)
 		n->slen = slen;
 
 		if (hlist_empty(&n->leaf)) {
-			put_child_root(pn, n->key, NULL);
+			drop_child(pn, n->key);
 			node_free(n);
 		} else {
 			leaf_pull_suffix(pn, 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