IPV4: fib_trie split child off from tnode

For large tnode's the power of 2 allocation wastes almost half the space
since the tnode is allocated with the power of 2 sized child pointers.
To solve this add a layer of indirection. For small nodes (the common case)
can just use a single allocation, for larger use pages like before.

Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>


---
 net/ipv4/fib_trie.c |   43 ++++++++++++++++++++++++++-----------------
 1 file changed, 26 insertions(+), 17 deletions(-)

--- a/net/ipv4/fib_trie.c	2008-04-03 09:09:45.000000000 -0700
+++ b/net/ipv4/fib_trie.c	2008-04-03 22:08:33.000000000 -0700
@@ -120,10 +120,10 @@ struct tnode {
 	t_key key;
 	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
 	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
+	struct node **child;
 	unsigned int full_children;	/* KEYLENGTH bits needed */
 	unsigned int empty_children;	/* KEYLENGTH bits needed */
 	struct rcu_head rcu;
-	struct node *child[0];
 };
 
 #ifdef CONFIG_IP_FIB_TRIE_STATS
@@ -348,30 +348,40 @@ static inline void free_leaf_info(struct
 	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
 }
 
-static struct tnode *tnode_alloc(size_t size)
+static struct tnode *tnode_alloc(int bits)
 {
-	struct page *pages;
-
-	if (size <= PAGE_SIZE)
-		return kzalloc(size, GFP_KERNEL);
+	size_t space = sizeof(struct node *) << bits;
+	size_t size = space + sizeof(struct tnode);
+	struct tnode *tn;
 
-	pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
-	if (!pages)
+	tn = kzalloc(size > PAGE_SIZE ? sizeof(struct tnode) : size, GFP_KERNEL);
+	if (!tn)
 		return NULL;
 
-	return page_address(pages);
+	if (size <= PAGE_SIZE)
+		tn->child = (struct node **) (tn + 1);
+	else {
+		struct page *pages = alloc_pages(GFP_KERNEL|__GFP_ZERO,
+						 get_order(space));
+		if (!pages) {
+			kfree(tn);
+			return NULL;
+		}
+		tn->child = page_address(pages);
+	}
+
+	return tn;
 }
 
 static void __tnode_free_rcu(struct rcu_head *head)
 {
 	struct tnode *tn = container_of(head, struct tnode, rcu);
-	size_t size = sizeof(struct tnode) +
-		      (sizeof(struct node *) << tn->bits);
+	size_t space = sizeof(struct node *) << tn->bits;
+	size_t size = space + sizeof(struct tnode);
 
-	if (size <= PAGE_SIZE)
-		kfree(tn);
-	else
-		free_pages((unsigned long)tn, get_order(size));
+	if (size > PAGE_SIZE)
+		free_pages((unsigned long)tn->child, get_order(space));
+	kfree(tn);
 }
 
 static inline void tnode_free(struct tnode *tn)
@@ -404,8 +414,7 @@ static struct leaf_info *leaf_info_new(i
 
 static struct tnode *tnode_new(t_key key, int pos, int bits)
 {
-	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
-	struct tnode *tn = tnode_alloc(sz);
+	struct tnode *tn = tnode_alloc(bits);
 
 	if (tn) {
 		tn->parent = T_TNODE;