For locality, always allocate one leaf_info with the leaf.
This method uses pointer arithmetic to identify this specially allocated
leaf_info to avoid freeing it.

It is possible to construct pathalogical cases where this ends up
wasting a leaf_info, ie. construct a route with two prefixes then always
delete the first.

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


--- a/net/ipv4/fib_trie.c	2008-01-15 09:48:21.000000000 -0800
+++ b/net/ipv4/fib_trie.c	2008-01-15 09:49:39.000000000 -0800
@@ -326,8 +326,12 @@ static void __leaf_info_free_rcu(struct 
 	kfree(container_of(head, struct leaf_info, rcu));
 }
 
-static inline void free_leaf_info(struct leaf_info *leaf)
+static inline void free_leaf_info(struct leaf *l, struct leaf_info *leaf)
 {
+	/* special case of cached leaf_info */
+	if (leaf == (struct leaf_info *)(l + 1))
+		return;
+
 	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
 }
 
@@ -376,13 +380,25 @@ static struct leaf *leaf_new(void)
 	return l;
 }
 
+static void leaf_info_init(struct leaf_info *li, int plen)
+{
+	li->plen = plen;
+	INIT_LIST_HEAD(&li->falh);
+}
+
+static struct leaf_info *leaf_info_first(struct leaf *l, int plen)
+{
+	struct leaf_info *li = (struct leaf_info *) (l + 1);
+	leaf_info_init(li, plen);
+	return li;
+}
+
 static struct leaf_info *leaf_info_new(int plen)
 {
 	struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
-	if (li) {
-		li->plen = plen;
-		INIT_LIST_HEAD(&li->falh);
-	}
+	if (li)
+		leaf_info_init(li, plen);
+
 	return li;
 }
 
@@ -1046,18 +1062,13 @@ static struct list_head *fib_insert_node
 		insert_leaf_info(&l->list, li);
 		goto done;
 	}
-	l = leaf_new();
 
+	l = leaf_new();
 	if (!l)
 		return NULL;
 
 	l->key = key;
-	li = leaf_info_new(plen);
-
-	if (!li) {
-		tnode_free((struct tnode *) l);
-		return NULL;
-	}
+	li = leaf_info_first(l, plen);
 
 	fa_head = &li->falh;
 	insert_leaf_info(&l->list, li);
@@ -1090,7 +1101,7 @@ static struct list_head *fib_insert_node
 		}
 
 		if (!tn) {
-			free_leaf_info(li);
+			free_leaf_info(l, li);
 			tnode_free((struct tnode *) l);
 			return NULL;
 		}
@@ -1622,7 +1633,7 @@ static int fn_trie_delete(struct fib_tab
 
 	if (list_empty(fa_head)) {
 		hlist_del_rcu(&li->hlist);
-		free_leaf_info(li);
+		free_leaf_info(l, li);
 	}
 
 	if (hlist_empty(&l->list))
@@ -1666,7 +1677,7 @@ static int trie_flush_leaf(struct trie *
 
 		if (list_empty(&li->falh)) {
 			hlist_del_rcu(&li->hlist);
-			free_leaf_info(li);
+			free_leaf_info(l, li);
 		}
 	}
 	return found;
@@ -1933,7 +1944,8 @@ void __init fib_hash_init(void)
 	fn_alias_kmem = kmem_cache_create("ip_fib_alias", sizeof(struct fib_alias),
 					  0, SLAB_PANIC, NULL);
 
-	trie_leaf_kmem = kmem_cache_create("ip_fib_trie", sizeof(struct leaf),
+	trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
+					   sizeof(struct leaf) + sizeof(struct leaf_info),
 					   0, SLAB_PANIC, NULL);
 }
 

-- 
Stephen Hemminger <stephen.hemminger@vyatta.com>

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html