[RFC PATCH 22/29] fib_trie: Allocate tnode as array of key_vectors instead of key_vector as array of tnode pointers

[Alexander Duyck <alexander.h.duyck@redhat.com>]

This change makes it so that we allocate a tnode as an array of key vectors
instead of a key vector with an array of tnode pointers.  By doing this we
set things up for a 1 cache line reduction since this places the key, key
info, and pointer to the next object all within 16B on 64b systems, and
within 12B on 32b systems.

In addition I have reordered the layout of the key_vector so that the leaf
and tnode pointers are at the start of the structure.  By doing this what
we end up doing is effectively navigating a list of pointers one after the
other to get to the fib_alias we are looking for, and we make it so that
there are no holes in the structure.

Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
 net/ipv4/fib_trie.c |   99 ++++++++++++++++++++++++++-------------------------
 1 file changed, 51 insertions(+), 48 deletions(-)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 58c8a89..f9abbf4 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -93,16 +93,16 @@ typedef unsigned int t_key;
 #define IS_LEAF(n)	(!(n)->bits)
 
 struct key_vector {
-	t_key key;
-	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
-	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
-	unsigned char slen;
 	union {
 		/* This list pointer if valid if bits == 0 (LEAF) */
 		struct hlist_head leaf;
 		/* The fields in this struct are valid if bits > 0 (TNODE) */
-		struct key_vector __rcu *tnode[0];
+		struct key_vector __rcu *tnode;
 	};
+	t_key key;
+	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
+	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
+	unsigned char slen;
 };
 
 struct tnode {
@@ -110,7 +110,7 @@ struct tnode {
 	t_key empty_children;		/* KEYLENGTH bits needed */
 	t_key full_children;		/* KEYLENGTH bits needed */
 	struct key_vector __rcu *parent;
-	struct key_vector kv[1];
+	struct key_vector kv[0];
 #define tn_bits kv[0].bits
 };
 
@@ -176,11 +176,11 @@ static inline struct fib_table *table_info(struct key_vector *kv)
 
 /* caller must hold RTNL */
 #define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)
-#define get_child(tn, i) rtnl_dereference((tn)->tnode[i])
+#define get_child(tn) rtnl_dereference((tn)->tnode)
 
 /* caller must hold RCU read lock or RTNL */
 #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)
-#define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])
+#define get_child_rcu(tn) rcu_dereference_rtnl((tn)->tnode)
 
 /* wrapper for rcu_assign_pointer */
 #define node_set_parent(n, p) rcu_assign_pointer(tn_info(n)->parent, p)
@@ -281,9 +281,9 @@ static inline void alias_free_mem_rcu(struct fib_alias *fa)
 	call_rcu(&fa->rcu, __alias_free_mem);
 }
 
-#define TNODE_SIZE(n) offsetof(struct tnode, kv[0].tnode[n])
+#define TNODE_SIZE(n) offsetof(struct tnode, kv[n])
 #define TNODE_KMALLOC_MAX \
-	ilog2((PAGE_SIZE - TNODE_SIZE(0)) / sizeof(struct key_vector *))
+	ilog2((PAGE_SIZE - TNODE_SIZE(0)) / sizeof(struct key_vector))
 
 static void __node_free_rcu(struct rcu_head *head)
 {
@@ -352,7 +352,7 @@ static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
 static void put_child(struct key_vector *tn, unsigned long i,
 		      struct key_vector *n)
 {
-	struct key_vector *chi = get_child(tn, i);
+	struct key_vector *chi = get_child(tn + i);
 	int isfull, wasfull;
 
 	BUG_ON(i >= child_length(tn));
@@ -375,7 +375,10 @@ static void put_child(struct key_vector *tn, unsigned long i,
 	if (n && (tn->slen < n->slen))
 		tn->slen = n->slen;
 
-	rcu_assign_pointer(tn->tnode[i], n);
+	/* update offset to correct key_vector for update */
+	tn += i;
+
+	rcu_assign_pointer(tn->tnode, n);
 }
 
 static void update_children(struct key_vector *tn)
@@ -384,7 +387,7 @@ static void update_children(struct key_vector *tn)
 
 	/* update all of the child parent pointers */
 	for (i = IS_TRIE(tn) ? 1 : child_length(tn); i;) {
-		struct key_vector *inode = get_child(tn, --i);
+		struct key_vector *inode = get_child(tn + --i);
 
 		if (!inode)
 			continue;
@@ -404,7 +407,7 @@ 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[0], n);
+		rcu_assign_pointer(tp->tnode, n);
 	else
 		put_child(tp, get_index(key, tp), n);
 }
@@ -461,10 +464,12 @@ static void tnode_replace(struct key_vector *oldtn,
 			  struct key_vector *tn)
 {
 	struct key_vector *pn = node_parent(oldtn);
-	unsigned long i = get_index(tn->key, pn);
+
+	/* update offset to correct key_vector for pointer update */
+	pn += get_index(tn->key, pn);
 
 	/* setup the parent pointer out of and back into this node */
-	rcu_assign_pointer(pn->tnode[i], tn);
+	rcu_assign_pointer(pn->tnode, tn);
 
 	/* update all of the child parent pointers */
 	update_children(tn);
@@ -573,7 +578,7 @@ static struct key_vector *resize_children(struct net *net, struct trie *t,
 
 	/* resize children now that oldtnode is freed */
 	for (i = child_length(tn); i;) {
-		struct key_vector *inode = get_child(tn, --i);
+		struct key_vector *inode = get_child(tn + --i);
 
 		/* resize child node */
 		if (tnode_full(tn, inode))
@@ -611,7 +616,7 @@ 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 = get_child(oldtnode + --i);
 		struct key_vector *node0, *node1;
 		unsigned long j, k;
 
@@ -630,8 +635,8 @@ static struct key_vector *inflate(struct net *net, struct trie *t,
 
 		/* 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, 0));
+			put_child(tn, 2 * i + 1, get_child(inode + 1));
+			put_child(tn, 2 * i, get_child(inode));
 			continue;
 		}
 
@@ -663,10 +668,10 @@ static struct key_vector *inflate(struct net *net, struct trie *t,
 
 		/* 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));
+			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));
 		}
 	}
 
@@ -708,8 +713,8 @@ 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 = get_child(oldtnode + --i);
+		struct key_vector *node0 = get_child(oldtnode + --i);
 		struct key_vector *inode;
 
 		/* At least one of the children is empty */
@@ -751,7 +756,7 @@ static struct key_vector *collapse(struct net *net, struct trie *t,
 
 	/* scan the tnode looking for that one child that might still exist */
 	for (i = child_length(oldtnode); i--;) {
-		struct key_vector *n = get_child(oldtnode, i);
+		struct key_vector *n = get_child(oldtnode + i);
 
 		if (!n)
 			continue;
@@ -790,7 +795,7 @@ static unsigned char update_suffix(struct key_vector *tn)
 	 * represent the nodes with suffix length equal to tn->pos
 	 */
 	for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {
-		struct key_vector *n = get_child(tn, i);
+		struct key_vector *n = get_child(tn + i);
 
 		if (!n || (n->slen <= slen))
 			continue;
@@ -932,7 +937,7 @@ static struct key_vector *resize(struct net *net, struct trie *t,
 	 * doing it ourselves.  This way we can let RCU fully do its
 	 * thing without us interfering
 	 */
-	BUG_ON(tn != get_child(tp, cindex));
+	BUG_ON(tn != get_child(tp + cindex));
 
 	/* Double as long as the resulting node has a number of
 	 * nonempty nodes that are above the threshold.
@@ -947,7 +952,7 @@ static struct key_vector *resize(struct net *net, struct trie *t,
 		}
 
 		max_work--;
-		tn = get_child(tp, cindex);
+		tn = get_child(tp + cindex);
 	}
 
 	/* Return if at least one inflate is run */
@@ -967,7 +972,7 @@ static struct key_vector *resize(struct net *net, struct trie *t,
 		}
 
 		max_work--;
-		tn = get_child(tp, cindex);
+		tn = get_child(tp + cindex);
 	}
 
 	/* Only one child remains */
@@ -1021,7 +1026,7 @@ static struct key_vector *fib_find_node(struct trie *t,
 
 	do {
 		*tp = n;
-		n = get_child_rcu(n, index);
+		n = get_child_rcu(n + index);
 
 		if (!n)
 			break;
@@ -1098,7 +1103,7 @@ static struct fib_table *fib_insert_node(struct net *net, struct trie *t,
 		goto noleaf;
 
 	/* retrieve child from parent node */
-	n = get_child(tp, get_index(key, tp));
+	n = get_child(tp + get_index(key, tp));
 
 	/* Case 2: n is a LEAF or a TNODE and the key doesn't match.
 	 *
@@ -1346,7 +1351,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
 	pn = t->kv;
 	cindex = 0;
 
-	n = get_child_rcu(pn, cindex);
+	n = get_child_rcu(pn);
 	if (!n)
 		return -EAGAIN;
 
@@ -1383,16 +1388,13 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
 			cindex = index;
 		}
 
-		n = get_child_rcu(n, index);
+		n = get_child_rcu(n + index);
 		if (unlikely(!n))
 			goto backtrace;
 	}
 
 	/* Step 2: Sort out leaves and begin backtracing for longest prefix */
 	for (;;) {
-		/* record the pointer where our next node pointer is stored */
-		struct key_vector __rcu **cptr = n->tnode;
-
 		/* This test verifies that none of the bits that differ
 		 * between the key and the prefix exist in the region of
 		 * the lsb and higher in the prefix.
@@ -1409,7 +1411,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
 		 * we started this traversal anyway
 		 */
 
-		while ((n = rcu_dereference(*cptr)) == NULL) {
+		while ((n = get_child_rcu(n)) == NULL) {
 backtrace:
 #ifdef CONFIG_IP_FIB_TRIE_STATS
 			if (!n)
@@ -1441,7 +1443,7 @@ backtrace:
 			cindex &= cindex - 1;
 
 			/* grab pointer for next child node */
-			cptr = &pn->tnode[cindex];
+			n = pn + cindex;
 		}
 	}
 
@@ -1616,7 +1618,7 @@ static struct key_vector *leaf_walk_rcu(struct key_vector **pn, t_key key)
 			break;
 
 		/* descend into the next child */
-		n = get_child_rcu(tn, cindex++);
+		n = get_child_rcu(tn + cindex++);
 		if (!n)
 			break;
 
@@ -1637,7 +1639,7 @@ static struct key_vector *leaf_walk_rcu(struct key_vector **pn, t_key key)
 		}
 
 		/* grab the next available node */
-		n = get_child_rcu(tn, cindex++);
+		n = get_child_rcu(tn + cindex++);
 		if (!n)
 			continue;
 
@@ -1688,7 +1690,7 @@ int fib_table_flush(struct net *net, struct fib_table *tb)
 		}
 
 		/* grab the next available node */
-		n = get_child(pn, cindex);
+		n = get_child(pn + cindex);
 		if (!n)
 			continue;
 
@@ -1827,7 +1829,8 @@ void __init fib_trie_init(void)
 					  0, SLAB_PANIC, NULL);
 
 	trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
-					   sizeof(struct tnode),
+					   sizeof(struct tnode) +
+					   sizeof(struct key_vector),
 					   0, SLAB_PANIC, NULL);
 }
 
@@ -1879,7 +1882,7 @@ static struct key_vector *fib_trie_get_next(struct fib_trie_iter *iter)
 
 	while (!IS_TRIE(pn)) {
 		while (cindex < child_length(pn)) {
-			struct key_vector *n = get_child_rcu(pn, cindex++);
+			struct key_vector *n = get_child_rcu(pn + cindex++);
 
 			if (!n)
 				continue;
@@ -1919,7 +1922,7 @@ static struct key_vector *fib_trie_get_first(struct fib_trie_iter *iter,
 	if (!t)
 		return NULL;
 
-	n = rcu_dereference(pn->tnode[0]);
+	n = rcu_dereference(pn->tnode);
 	if (!n)
 		return NULL;
 
@@ -2003,8 +2006,8 @@ static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
 	seq_putc(seq, '\n');
 	seq_printf(seq, "\tPointers: %u\n", pointers);
 
-	bytes += sizeof(struct key_vector *) * pointers;
-	seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
+	bytes += sizeof(struct key_vector) * pointers;
+	seq_printf(seq, "Empty vectors: %u\n", stat->nullpointers);
 	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
 }