fix sparse warnings

Make FIB TRIE go through sparse checker without warnings.

Signed-off-by Stephen Hemminger <[email protected]>

We could use a better scheme with an extra indirection.

3) 'pos' and 'bits' fields of 'struct tnode' might be converted to plain uchar, instead of 5-bits fields, to reduce complexity for generated code.

Quoted 3 lines · Stephen Hemminger

Make FIB TRIE go through sparse checker without warnings.

Signed-off-by Stephen Hemminger <[email protected]>

Hi Stephen

While reviewing your patches (and fib code) I had some questions :

1) I was wondering isn't trie_collect_stats() a potential cpu hog (big latency) ?

2) struct tnode layout
If tnode->bits is large enough, we allocate a big area
of memory but roughly use only first half of it.
We could use a better scheme with an extra indirection. For small nodes, we use space right after tnode, but for big nodes, we allocate a power of two set of pages, to exactly match the memory need.

3) 'pos' and 'bits' fields of 'struct tnode' might be converted to plain uchar, instead of 5-bits fields, to reduce complexity for generated code.

4) full_children & empty_children being 'unsigned short', we probably are limited to 2^15 elements, but I could not find this limit enforced somewhere.

Remember that the code should be optimized for lookup, not management operations. We ran into this during testing (the test suite was looking for number of routes), thats why I put in the size field.

The existing dump code is really slow:

1) FIB_TRIE Under KVM:

     load 164393 routes		12.436 sec
     ip route | wc -l		12.569 sec
     grep /proc/net/route	25.357 sec

99% of the cpu time is spent in nextleaf() during these dump operations.

2) FIB_HASH Under KVM:

     load 164393 routes		10.833 sec
     ip route | wc -l		1.981 sec
     grep /proc/net/route	0.204 sec

Thanks for hacking and improving and the trie... another idea that could be also tested. If we look into routing table we see that most leafs only has one prefix

Main:

        Aver depth:     2.57
        Max depth:      7
        Leaves:         231173

ip route | wc -l 241649

Thats 231173/241649 = 96% with the current Internet routing.

How about if would have a fastpath and store one entry direct in the leaf struct this to avoid loading the leaf_info list in most cases?

One could believe that both lookup and dump could improve.

Quoted 7 lines

Thats 231173/241649 = 96% with the current Internet routing.

How about if would have a fastpath and store one entry direct in the leaf struct this to avoid loading the leaf_info list in most cases?

One could believe that both lookup and dump could improve.

You mean to include one "leaf_info" inside leaf structure, so that we can access it without cache line miss ?

fib_trie_seq_show() uses two helper functions, rtn_scope() and rtn_type() that can
write to static storage without locking.

Just pass to them a temporary buffer to avoid potential corruption (probably not triggerable but still...)

Signed-off-by Eric Dumazet <[email protected]>

Quoted 3 lines · Stephen Hemminger

Make FIB TRIE go through sparse checker without warnings.

Signed-off-by Stephen Hemminger <[email protected]>

Hi Stephen

While reviewing your patches (and fib code) I had some questions :

1) I was wondering isn't trie_collect_stats() a potential cpu hog (big latency) ?

2) struct tnode layout
If tnode->bits is large enough, we allocate a big area
of memory but roughly use only first half of it.
We could use a better scheme with an extra indirection. For small nodes, we use space right after tnode, but for big nodes, we allocate a power of two set of pages, to exactly match the memory need.

3) 'pos' and 'bits' fields of 'struct tnode' might be converted to plain uchar, instead of 5-bits fields, to reduce complexity for generated code.

4) full_children & empty_children being 'unsigned short', we probably are limited to 2^15 elements, but I could not find this limit enforced somewhere.

[FIB]: Reduce text size of net/ipv4/fib_trie.o

In struct tnode, we use two fields of 5 bits for 'pos' and 'bits'. Switching to plain 'unsigned char' (8 bits) take the same space because of compiler alignments, and reduce text size by 435 bytes on i386.

On i386 :

$ size net/ipv4/fib_trie.o.before_patch net/ipv4/fib_trie.o
    text    data     bss     dec     hex filename
   13714       4      64   13782    35d6 net/ipv4/fib_trie.o.before
   13279       4      64   13347    3423 net/ipv4/fib_trie.o

Signed-off-by Eric Dumazet <[email protected]>

Quoted 13 lines · On Sat, 12 Jan 2008 12:16:13 +0100 Eric Dumazet <[email protected]> wrote:

[FIB]: Reduce text size of net/ipv4/fib_trie.o

In struct tnode, we use two fields of 5 bits for 'pos' and 'bits'. Switching to plain 'unsigned char' (8 bits) take the same space because of compiler alignments, and reduce text size by 435 bytes on i386.

On i386 :

$ size net/ipv4/fib_trie.o.before_patch net/ipv4/fib_trie.o
    text    data     bss     dec     hex filename
   13714       4      64   13782    35d6 net/ipv4/fib_trie.o.before
   13279       4      64   13347    3423 net/ipv4/fib_trie.o

Quoted 2 lines

Signed-off-by Eric Dumazet <[email protected]>

I agree they should not have been bitfields in the first place.

4) full_children & empty_children being 'unsigned short', we probably are limited to 2^15 elements, but I could not find this limit enforced somewhere.

Quoted 3 lines · Eric Dumazet

4) full_children & empty_children being 'unsigned short', we probably are limited to 2^15 elements, but I could not find this limit enforced somewhere.

Two fixes are possible : Enlarge full_children & empty_children to 32bits, or force a limit in code to never exceed 2^15 children in a tnode. I chose the first solution since it can be done with 0 memory cost on 64bit arches.

[FIB]: full_children & empty_children should be uint, not ushort

If declared as unsigned short, these fields can overflow, and whole trie logic is broken. I could not make the machine crash, but some tnode can never be freed.

Note for 64 bit arches : By reordering t_key and parent in [node, leaf, tnode] structures, we can use 32 bits hole after t_key so that sizeof(struct tnode) doesnt change after this patch.

Signed-off-by Eric Dumazet <[email protected]>

net/ipv4/fib_trie.c +12 -13

index f26ba31..9696722 100644
@@ -97,13 +97,13 @@ typedef unsigned int t_key;
 #define IS_LEAF(n) (n->parent & T_LEAF)
 
 struct node {
-	t_key key;
 	unsigned long parent;
+	t_key key;
 };
 
 struct leaf {
-	t_key key;
 	unsigned long parent;
+	t_key key;
 	struct hlist_head list;
 	struct rcu_head rcu;
 };

@@ -116,12 +116,12 @@ struct leaf_info {
 };
 
 struct tnode {
-	t_key key;
 	unsigned long parent;
+	t_key key;
 	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
 	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
-	unsigned short full_children;	/* KEYLENGTH bits needed */
-	unsigned short empty_children;	/* KEYLENGTH bits needed */
+	unsigned int full_children;	/* KEYLENGTH bits needed */
+	unsigned int empty_children;	/* KEYLENGTH bits needed */
 	struct rcu_head rcu;
 	struct node *child[0];
 };

@@ -329,12 +329,12 @@ static inline void free_leaf_info(struct leaf_info *leaf)
 	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
 }
 
-static struct tnode *tnode_alloc(unsigned int size)
+static struct tnode *tnode_alloc(size_t size)
 {
 	struct page *pages;
 
 	if (size <= PAGE_SIZE)
-		return kcalloc(size, 1, GFP_KERNEL);
+		return kzalloc(size, GFP_KERNEL);
 
 	pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
 	if (!pages)

@@ -346,8 +346,8 @@ static struct tnode *tnode_alloc(unsigned int size)
 static void __tnode_free_rcu(struct rcu_head *head)
 {
 	struct tnode *tn = container_of(head, struct tnode, rcu);
-	unsigned int size = sizeof(struct tnode) +
-		(1 << tn->bits) * sizeof(struct node *);
+	size_t size = sizeof(struct tnode) +
+		      (sizeof(struct node *) << tn->bits);
 
 	if (size <= PAGE_SIZE)
 		kfree(tn);

@@ -386,8 +386,7 @@ static struct leaf_info *leaf_info_new(int plen)
 
 static struct tnode* tnode_new(t_key key, int pos, int bits)
 {
-	int nchildren = 1<<bits;
-	int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
+	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
 	struct tnode *tn = tnode_alloc(sz);
 
 	if (tn) {

@@ -399,8 +398,8 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
 		tn->empty_children = 1<<bits;
 	}
 
-	pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
-		 (unsigned int) (sizeof(struct node) * 1<<bits));
+	pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
+		 (unsigned long) (sizeof(struct node) << bits));
 	return tn;
 }
 

Quoted 8 lines · Eric Dumazet

Quoted 3 lines · Eric Dumazet

4) full_children & empty_children being 'unsigned short', we probably are limited to 2^15 elements, but I could not find this limit enforced somewhere.

Two fixes are possible : Enlarge full_children & empty_children to 32bits, or force a limit in code to never exceed 2^15 children in a tnode. I chose the first solution since it can be done with 0 memory cost on 64bit arches.

Thanks for spotting this. No we don't want put limits on the (root) node size. You see the comment in code is correct so unsigned short are some leftover from old testing which could have hit us hard as the routing table slowly grows.

Signed-off-by Robert Olsson <[email protected]>

Make FIB TRIE go through sparse checker without warnings.

Signed-off-by Stephen Hemminger <[email protected]>

trie_init is worthless it is just zeroing stuff that is already zero! Move the memset() down to make it obvious.

Signed-off-by Stephen Hemminger <[email protected]>

The revision element must of been part of an earlier design, because currently it is set but never used.

Signed-off-by Stephen Hemminger <[email protected]>

Quoted 4 lines

The revision element must of been part of an earlier design, because currently it is set but never used.

Signed-off-by Stephen Hemminger <[email protected]>

I suspect Robert wanted to play around with some generation ID optimizations but never got around to it.

The idea was to have a selective flush of route cache entries when a fib insert/delete happened. From what I remember you added another/ better solution. Just a list with route cache entries pointing to parent route. So yes this was obsoleted by your/our effort to avoid total flushing of the route cache. Unfinished work.

According to http://bgpupdates.potaroo.net/instability/bgpupd.html
(last in page) we currently flush the route cache 2.80 times per second. when using full Internet routing with Linux. Maybe we're forced to pick up this thread again someday.

From: Robert Olsson <[email protected]>
Date: Mon, 14 Jan 2008 12:44:32 +0100

Quoted 5 lines

The idea was to have a selective flush of route cache entries when a fib insert/delete happened. From what I remember you added another/ better solution. Just a list with route cache entries pointing to parent route. So yes this was obsoleted by your/our effort to avoid total flushing of the route cache. Unfinished work.

Yes, that's right. The synchronization was very hard.

But there is another issue, see below....

Quoted 4 lines

According to http://bgpupdates.potaroo.net/instability/bgpupd.html
(last in page) we currently flush the route cache 2.80 times per second. when using full Internet routing with Linux. Maybe we're forced to pick up this thread again someday.

This proves we need to solve this problem.

The reason I've never gone back to that work is that I didn't want to do it while we still had multiple FIB data structure implementations.

Someone needs to go over whatever deficiencies exist in fib_trie vs. fib_hash so that we can delete fib_hash and move over to using fib_trie always. It makes no sense to implement everything interfacing into that code twice.

There was a full consensus that this was the way to move forward, we just need the dirty work to be done.

If someone wants to show their gratitude for my getting rid of the multipath cached routing code, the above work would be a great way to do so (hint hint) :-)

I will be glad to get this working. Is there any point in doing the a small systems version as well?

The size of structures is a debug thing, not something that needs to be part of a /proc api.

Signed-off-by Stephen Hemminger <[email protected]>

Turn the unused size field into a useful counter for the number of routes.

Signed-off-by Stephen Hemminger <[email protected]>

From: Stephen Hemminger <[email protected]>
Date: Fri, 11 Jan 2008 22:45:17 -0800

Quoted 3 lines

Turn the unused size field into a useful counter for the number of routes.

Quoted 2 lines

Signed-off-by Stephen Hemminger <[email protected]>

It's not useful if nothing reports it's value. I'm dropping this.

Unless you add code to provide this information via procfs or similar, better to just remove it.

The size field is added to /proc/net/fib_triestat that was the point.

Initialization of the slab cache's should be done when IP is initialized to make sure of available memory, and that code can be marked __init.

Signed-off-by Stephen Hemminger <[email protected]>

Combine the prefix information and the leaf together into one allocation. This is furthur simplified by converting the hlist into a simple bitfield.

Signed-off-by Stephen Hemminger <[email protected]>

This patch is experimental (ie it boots and loads routes), but is slower for the 163,000 route dump test.

---
 net/ipv4/fib_trie.c |  165 ++++++++++++++++++++--------------------------------
 1 file changed, 65 insertions(+), 100 deletions(-)

net/ipv4/fib_trie.c +65 -101

@@ -50,10 +50,9 @@
  *		Patrick McHardy <[email protected]>
  */
 
-#define VERSION "0.408"
+#define VERSION "0.409"
+
 
-#include <asm/uaccess.h>
-#include <asm/system.h>
 #include <linux/bitops.h>
 #include <linux/types.h>
 #include <linux/kernel.h>

@@ -80,6 +79,8 @@
 #include <net/tcp.h>
 #include <net/sock.h>
 #include <net/ip_fib.h>
+#include <asm/bitops.h>
+
 #include "fib_lookup.h"
 
 #define MAX_STAT_DEPTH 32

@@ -101,20 +102,24 @@ struct node {
 	t_key key;
 };
 
+struct leaf_info {
+	struct list_head falh;
+};
+
+#define INFO_SIZE	33
+/* NB: bitmap is in reverse order, so that find_first returns largest prefix */
+#define PLEN2BIT(x)	(INFO_SIZE - (x))
+
 struct leaf {
 	unsigned long parent;
 	t_key key;
-	struct hlist_head list;
 	struct rcu_head rcu;
-};
 
-struct leaf_info {
-	struct hlist_node hlist;
-	struct rcu_head rcu;
-	int plen;
-	struct list_head falh;
+	unsigned long bitmap[INFO_SIZE / BITS_PER_LONG + 1];
+	struct leaf_info info[INFO_SIZE];
 };
 
+
 struct tnode {
 	unsigned long parent;
 	t_key key;

@@ -321,16 +326,6 @@ static void __leaf_free_rcu(struct rcu_h
 	kmem_cache_free(trie_leaf_kmem, leaf);
 }
 
-static void __leaf_info_free_rcu(struct rcu_head *head)
-{
-	kfree(container_of(head, struct leaf_info, rcu));
-}
-
-static inline void free_leaf_info(struct leaf_info *leaf)
-{
-	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
-}
-
 static struct tnode *tnode_alloc(size_t size)
 {
 	struct page *pages;

@@ -371,21 +366,37 @@ static struct leaf *leaf_new(void)
 	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
 	if (l) {
 		l->parent = T_LEAF;
-		INIT_HLIST_HEAD(&l->list);
+		bitmap_zero(l->bitmap, INFO_SIZE);
 	}
 	return l;
 }
 
-static struct leaf_info *leaf_info_new(int plen)
+static inline struct leaf_info *find_leaf_info(struct leaf *l, int plen)
 {
-	struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
-	if (li) {
-		li->plen = plen;
-		INIT_LIST_HEAD(&li->falh);
-	}
+	return test_bit(PLEN2BIT(plen), l->bitmap) ? &l->info[plen] : NULL;
+}
+
+static struct leaf_info *set_leaf_info(struct leaf *l, int plen)
+{
+	struct leaf_info *li = &l->info[plen];
+
+	INIT_LIST_HEAD(&li->falh);
+	set_bit(PLEN2BIT(plen), l->bitmap);
+
 	return li;
 }
 
+static inline void clear_leaf_info(struct leaf *l, int plen)
+{
+	smp_mb__before_clear_bit();
+	clear_bit(PLEN2BIT(plen), &l->bitmap);
+}
+
+static inline int leaf_info_empty(const struct leaf *l)
+{
+	return find_first_bit(l->bitmap, INFO_SIZE) >= INFO_SIZE;
+}
+
 static struct tnode* tnode_new(t_key key, int pos, int bits)
 {
 	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);

@@ -876,20 +887,6 @@ nomem:
 
 /* readside must use rcu_read_lock currently dump routines
  via get_fa_head and dump */
-
-static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
-{
-	struct hlist_head *head = &l->list;
-	struct hlist_node *node;
-	struct leaf_info *li;
-
-	hlist_for_each_entry_rcu(li, node, head, hlist)
-		if (li->plen == plen)
-			return li;
-
-	return NULL;
-}
-
 static inline struct list_head * get_fa_head(struct leaf *l, int plen)
 {
 	struct leaf_info *li = find_leaf_info(l, plen);

@@ -900,26 +897,6 @@ static inline struct list_head * get_fa_
 	return &li->falh;
 }
 
-static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
-{
-	struct leaf_info *li = NULL, *last = NULL;
-	struct hlist_node *node;
-
-	if (hlist_empty(head)) {
-		hlist_add_head_rcu(&new->hlist, head);
-	} else {
-		hlist_for_each_entry(li, node, head, hlist) {
-			if (new->plen > li->plen)
-				break;
-
-			last = li;
-		}
-		if (last)
-			hlist_add_after_rcu(&last->hlist, &new->hlist);
-		else
-			hlist_add_before_rcu(&new->hlist, &li->hlist);
-	}
-}
 
 /* rcu_read_lock needs to be hold by caller from readside */
 

@@ -993,6 +970,8 @@ static struct list_head *fib_insert_node
 	pos = 0;
 	n = t->trie;
 
+	pr_debug("fib_insert_node: %x/%d\n", key, plen);
+
 	/* If we point to NULL, stop. Either the tree is empty and we should
 	 * just put a new leaf in if, or we have reached an empty child slot,
 	 * and we should just put our new leaf in that.

@@ -1038,13 +1017,9 @@ static struct list_head *fib_insert_node
 
 	if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
 		l = (struct leaf *) n;
-		li = leaf_info_new(plen);
-
-		if (!li)
-			return NULL;
-
+		li = set_leaf_info(l, plen);
 		fa_head = &li->falh;
-		insert_leaf_info(&l->list, li);
+
 		goto done;
 	}
 	l = leaf_new();

@@ -1053,15 +1028,8 @@ static struct list_head *fib_insert_node
 		return NULL;
 
 	l->key = key;
-	li = leaf_info_new(plen);
-
-	if (!li) {
-		tnode_free((struct tnode *) l);
-		return NULL;
-	}
-
+	li = set_leaf_info(l, plen);
 	fa_head = &li->falh;
-	insert_leaf_info(&l->list, li);
 
 	if (t->trie && n == NULL) {
 		/* Case 2: n is NULL, and will just insert a new leaf */

@@ -1091,7 +1059,6 @@ static struct list_head *fib_insert_node
 		}
 
 		if (!tn) {
-			free_leaf_info(li);
 			tnode_free((struct tnode *) l);
 			return NULL;
 		}

@@ -1119,7 +1086,7 @@ static struct list_head *fib_insert_node
 
 	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
 done:
-	return fa_head;
+	return &li->falh;
 }
 
 /*

@@ -1281,14 +1248,14 @@ static int check_leaf(struct trie *t, st
 		      t_key key,  const struct flowi *flp,
 		      struct fib_result *res)
 {
-	struct leaf_info *li;
-	struct hlist_head *hhead = &l->list;
-	struct hlist_node *node;
+	int bit;
 
-	hlist_for_each_entry_rcu(li, node, hhead, hlist) {
-		int err;
-		int plen = li->plen;
+	/* need find highest prefix */
+	for_each_bit(bit, l->bitmap, INFO_SIZE) {
+		int plen = PLEN2BIT(bit);
+		struct leaf_info *li = &l->info[plen];
 		__be32 mask = inet_make_mask(plen);
+		int err;
 
 		if (l->key != (key & ntohl(mask)))
 			continue;

@@ -1622,12 +1589,10 @@ static int fn_trie_delete(struct fib_tab
 
 	list_del_rcu(&fa->fa_list);
 
-	if (list_empty(fa_head)) {
-		hlist_del_rcu(&li->hlist);
-		free_leaf_info(li);
-	}
+	if (list_empty(fa_head))
+		clear_leaf_info(l, plen);
 
-	if (hlist_empty(&l->list))
+	if (leaf_info_empty(l))
 		trie_leaf_remove(t, key);
 
 	if (fa->fa_state & FA_S_ACCESSED)

@@ -1659,18 +1624,17 @@ static int trie_flush_list(struct trie *
 static int trie_flush_leaf(struct trie *t, struct leaf *l)
 {
 	int found = 0;
-	struct hlist_head *lih = &l->list;
-	struct hlist_node *node, *tmp;
-	struct leaf_info *li = NULL;
+	int bit;
 
-	hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
+	for_each_bit(bit, l->bitmap, INFO_SIZE) {
+		int plen = PLEN2BIT(bit);
+		struct leaf_info *li = &l->info[plen];
 		found += trie_flush_list(t, &li->falh);
 
-		if (list_empty(&li->falh)) {
-			hlist_del_rcu(&li->hlist);
-			free_leaf_info(li);
-		}
+		if (list_empty(&li->falh))
+			clear_leaf_info(l, plen);
 	}
+
 	return found;
 }
 

@@ -1746,12 +1710,12 @@ static int fn_trie_flush(struct fib_tabl
 	for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
 		found += trie_flush_leaf(t, l);
 
-		if (ll && hlist_empty(&ll->list))
+		if (ll && leaf_info_empty(ll))
 			trie_leaf_remove(t, ll->key);
 		ll = l;
 	}
 
-	if (ll && hlist_empty(&ll->list))
+	if (ll && leaf_info_empty(ll))
 		trie_leaf_remove(t, ll->key);
 
 	pr_debug("trie_flush found=%d\n", found);

@@ -2428,10 +2392,11 @@ static int fib_route_seq_show(struct seq
 
 	if (iter->trie == iter->trie_local)
 		return 0;
+
 	if (IS_TNODE(l))
 		return 0;
 
-	for (i=32; i>=0; i--) {
+	for (i = 32; i >= 0; i--) {
 		struct leaf_info *li = find_leaf_info(l, i);
 		struct fib_alias *fa;
 		__be32 mask, prefix;

@@ -2439,7 +2404,7 @@ static int fib_route_seq_show(struct seq
 		if (!li)
 			continue;
 
-		mask = inet_make_mask(li->plen);
+		mask = inet_make_mask(i);
 		prefix = htonl(l->key);
 
 		list_for_each_entry_rcu(fa, &li->falh, fa_list) {
--

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

Quoted 9 lines · Stephen Hemminger

Combine the prefix information and the leaf together into one allocation. This is furthur simplified by converting the hlist into a simple bitfield.

Signed-off-by Stephen Hemminger <[email protected]>

This patch is experimental (ie it boots and loads routes), but is slower for the 163,000 route dump test.

Its also very memory expensive. That was not Robert suggestion I believe.

Its suggestion is to embedd one info into each leaves.

Please find attached to this mail a preliminary and incomplete patch I wrote this morning before coffee :), to get the idea.

Quoted 13 lines · Eric Dumazet

Quoted 9 lines · Stephen Hemminger

Combine the prefix information and the leaf together into one allocation. This is furthur simplified by converting the hlist into a simple bitfield.

Signed-off-by Stephen Hemminger <[email protected]>

This patch is experimental (ie it boots and loads routes), but is slower for the 163,000 route dump test.

Its also very memory expensive. That was not Robert suggestion I believe.

Quoted 4 lines

Its suggestion is to embedd one info into each leaves.

Please find attached to this mail a preliminary and incomplete patch I wrote this morning before coffee :), to get the idea.

Oops, patch reversed, sorry, and against another work pending in my tree.

Now time for cofee :)

Okay, I would rather see the leaf_info explicit inside the leaf, also your scheme probably breaks if I add two prefixes and then delete the first. Let me have a go at it.

Quoted 3 lines · Stephen Hemminger

Okay, I would rather see the leaf_info explicit inside the leaf, also your scheme probably breaks if I add two prefixes and then delete the first. Let me have a go at it.

I took Eric's patch a bit further...

Support for delete and dump is needed before any testing at all and maybe some macro for checking and setting FP-leaf's

Cheers.

					--ro

net/ipv4/fib_trie.c +3 -6

index 6dab753..f5b276c 100644
@@ -97,22 +97,32 @@ typedef unsigned int t_key;
 #define IS_LEAF(n) (n->parent & T_LEAF)
 
 struct node {
-	unsigned long parent;
-	t_key key;
+	unsigned long		parent;
+	t_key			key;
 };
 
 struct leaf {
-	unsigned long parent;
-	t_key key;
-	struct hlist_head list;
-	struct rcu_head rcu;
+	unsigned long		parent;

net/ipv4/fib_trie.c +10 -5

+
+	struct hlist_head	list;
+	struct rcu_head		rcu;
 };
 
 struct leaf_info {
-	struct hlist_node hlist;
-	struct rcu_head rcu;
-	int plen;
-	struct list_head falh;
+	struct hlist_node	hlist;
+	int			plen;
+	struct list_head	falh;
+	struct rcu_head		rcu;
 };
 
 struct tnode {

@@ -364,11 +374,13 @@ static inline void tnode_free(struct tnode *tn)
 		call_rcu(&tn->rcu, __tnode_free_rcu);
 }
 
-static struct leaf *leaf_new(void)
+static struct leaf *leaf_new(int plen)
 {
 	struct leaf *l = kmalloc(sizeof(struct leaf),  GFP_KERNEL);
 	if (l) {
 		l->parent = T_LEAF;
+		l->plen_iinfo = plen;
+		INIT_LIST_HEAD(&l->falh_iinfo);
 		INIT_HLIST_HEAD(&l->list);
 	}
 	return l;

@@ -890,7 +902,16 @@ static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
 
 static inline struct list_head * get_fa_head(struct leaf *l, int plen)

This is how I did it:

net/ipv4/fib_trie.c +0 -7

@@ -101,13 +101,6 @@ struct node {
 	t_key key;
 };
 
-struct leaf {
-	unsigned long parent;
-	t_key key;
-	struct hlist_head list;
-	struct rcu_head rcu;
-};
-
 struct leaf_info {
 	struct hlist_node hlist;
 	struct rcu_head rcu;

Quoted 19 lines · On Tue, 15 Jan 2008 09:47:53 -0800 Stephen Hemminger…

This is how I did it:

net/ipv4/fib_trie.c +0 -7

@@ -101,13 +101,6 @@ struct node {
 	t_key key;
 };
 
-struct leaf {
-	unsigned long parent;
-	t_key key;
-	struct hlist_head list;
-	struct rcu_head rcu;
-};
-
 struct leaf_info {
 	struct hlist_node hlist;
 	struct rcu_head rcu;

net/ipv4/fib_trie.c struct leaf_info { · line 116

Quoted 9 lines

net/ipv4/fib_trie.c +6 -0

@@ -115,6 +108,13 @@ struct leaf_info {
 	struct list_head falh;
 };
 
+struct leaf {
+	unsigned long parent;
+	t_key key;
+	struct hlist_head list;
+	struct rcu_head rcu;
+};

I like this :)

Your design is clean, but we waste some space (rcu in leaf_info "included"), we probably can do a litle bit better
(moving rcu at the end of leaf_info, and kmem_cache_create("ip_fib_trie", sizeof(struct leaf) + sizeof(struct_leaf_info) - sizeof(struct rcu_head))

net/ipv4/fib_trie.c void __init fib_hash_init(void) · line 1951

Quoted 7 lines

net/ipv4/fib_trie.c +2 -1

-	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);
 }

Thank you

Quoted 38 lines · On Tue, 15 Jan 2008 19:10:31 +0100 Eric Dumazet <[email protected]> wrote:

Quoted 19 lines · On Tue, 15 Jan 2008 09:47:53 -0800 Stephen Hemminger…

This is how I did it:

net/ipv4/fib_trie.c +0 -7

@@ -101,13 +101,6 @@ struct node {
 	t_key key;
 };
 
-struct leaf {
-	unsigned long parent;
-	t_key key;
-	struct hlist_head list;
-	struct rcu_head rcu;
-};
-
 struct leaf_info {
 	struct hlist_node hlist;
 	struct rcu_head rcu;

net/ipv4/fib_trie.c struct leaf_info { · line 116

Quoted 9 lines

net/ipv4/fib_trie.c +6 -0

@@ -115,6 +108,13 @@ struct leaf_info {
 	struct list_head falh;
 };
 
+struct leaf {
+	unsigned long parent;
+	t_key key;
+	struct hlist_head list;
+	struct rcu_head rcu;
+};

I like this :)

Your design is clean, but we waste some space (rcu in leaf_info "included"), we probably can do a litle bit better
(moving rcu at the end of leaf_info, and kmem_cache_create("ip_fib_trie", sizeof(struct leaf) + sizeof(struct_leaf_info) - sizeof(struct rcu_head))

Quoted 9 lines

net/ipv4/fib_trie.c void __init fib_hash_init(void) · line 1951

Quoted 7 lines

net/ipv4/fib_trie.c +2 -1

-	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);
 }

Thank you

Having multiple RCU links is a waste. I started on code that just splice's the leaf_info's off to a free_list and then do a mass free after and RCU barrier.

For the normal case of just freeing a leaf, it could just walk the chain in the RCU free of the leaf.

This is how I did it:

net/ipv4/fib_trie.c +44 -33

@@ -101,13 +101,6 @@ struct node {
 	t_key key;
 };
 
-struct leaf {
-	unsigned long parent;
-	t_key key;
-	struct hlist_head list;
-	struct rcu_head rcu;
-};
-
 struct leaf_info {
 	struct hlist_node hlist;
 	struct rcu_head rcu;

@@ -115,6 +108,13 @@ struct leaf_info {
 	struct list_head falh;
 };
 
+struct leaf {
+	unsigned long parent;
+	t_key key;
+	struct hlist_head list;
+	struct rcu_head rcu;
+};
+
 struct tnode {
 	unsigned long parent;
 	t_key key;

@@ -321,16 +321,6 @@ static void __leaf_free_rcu(struct rcu_h
 	kmem_cache_free(trie_leaf_kmem, leaf);
 }
 
-static void __leaf_info_free_rcu(struct rcu_head *head)
-{
-	kfree(container_of(head, struct leaf_info, rcu));
-}
-
-static inline void free_leaf_info(struct leaf_info *leaf)
-{
-	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
-}
-
 static struct tnode *tnode_alloc(size_t size)
 {
 	struct page *pages;

@@ -357,7 +347,7 @@ static void __tnode_free_rcu(struct rcu_
 		free_pages((unsigned long)tn, get_order(size));
 }
 
-static inline void tnode_free(struct tnode *tn)
+static void tnode_free(struct tnode *tn)
 {
 	if (IS_LEAF(tn)) {
 		struct leaf *l = (struct leaf *) tn;

@@ -376,16 +366,41 @@ 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;
 }
 
+static void __leaf_info_free_rcu(struct rcu_head *head)
+{
+	kfree(container_of(head, struct leaf_info, rcu));
+}
+
+static inline void free_leaf_info(struct leaf *l, struct leaf_info *leaf)
+{
+	if (leaf == (struct leaf_info *)(l + 1))
+		return;
+
+	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
+}
+
 static struct tnode* tnode_new(t_key key, int pos, int bits)
 {
 	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);

@@ -1047,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);

@@ -1091,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;
 		}

@@ -1624,7 +1634,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))

@@ -1668,7 +1678,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;

@@ -1935,7 +1945,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);
 }
 

Quoted 1 line · Stephen Hemminger

This is how I did it:

Yes looks like an elegant solution. Did you even test it? Maybe we see some effects in just dumping a full table?

Anyway lookup should be tested in some way. We can a lot of analyzing before getting to right entry, local_table backtracking, main lookup w. ev. backtracking etc. So hopefully we get paid for this work.

Also it might be idea to do some analysis of the fib_aliases list. Maybe the trick can be done again? ;)

So you think that a leaf cannot have 2 infos, one 'embeded' and one in the list ?

This improves locality for operations that touch all the leaves. Later patch will grow the size of the leaf so it becomes more important.

Signed-off-by Stephen Hemminger <[email protected]>

net/ipv4/fib_trie.c +4 -2

@@ -162,6 +162,7 @@ static struct tnode *halve(struct trie *
 static void tnode_free(struct tnode *tn);
 
 static struct kmem_cache *fn_alias_kmem __read_mostly;
+static struct kmem_cache *trie_leaf_kmem __read_mostly;
 
 static inline struct tnode *node_parent(struct node *node)
 {

@@ -316,7 +317,8 @@ static inline void alias_free_mem_rcu(st
 
 static void __leaf_free_rcu(struct rcu_head *head)
 {
-	kfree(container_of(head, struct leaf, rcu));
+	struct leaf *leaf = container_of(head, struct leaf, rcu);
+	kmem_cache_free(trie_leaf_kmem, leaf);
 }
 
 static void __leaf_info_free_rcu(struct rcu_head *head)

@@ -366,7 +368,7 @@ static inline void tnode_free(struct tno
 
 static struct leaf *leaf_new(void)
 {
-	struct leaf *l = kmalloc(sizeof(struct leaf),  GFP_KERNEL);
+	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
 	if (l) {
 		l->parent = T_LEAF;
 		INIT_HLIST_HEAD(&l->list);

This improves locality for operations that touch all the leaves. Later patch will grow the size of the leaf so it becomes more important.

Signed-off-by Stephen Hemminger <[email protected]>

Show number of entries in trie, the size field was being set but never used, but it only counted leaves, not all entries. Refactor the two cases in fib_triestat_seq_show into a single routine.

Note: the stat structure was being malloc'd but the stack usage isn't so high (288 bytes) that it is worth the additional complexity.

Signed-off-by Stephen Hemminger <[email protected]>

---
Patch against current net-2.6.25

net/ipv4/fib_trie.c +20 -30

@@ -148,10 +148,10 @@ struct trie_stat {
 
 struct trie {
 	struct node *trie;
+	unsigned int size;
 #ifdef CONFIG_IP_FIB_TRIE_STATS
 	struct trie_use_stats stats;
 #endif
-	int size;
 };
 
 static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);

@@ -1045,7 +1045,6 @@ static struct list_head *fib_insert_node
 		insert_leaf_info(&l->list, li);
 		goto done;
 	}
-	t->size++;
 	l = leaf_new();
 
 	if (!l)

@@ -1258,6 +1257,8 @@ static int fn_trie_insert(struct fib_tab
 	list_add_tail_rcu(&new_fa->fa_list,
 			  (fa ? &fa->fa_list : fa_head));
 
+	t->size++;
+
 	rt_cache_flush(-1);
 	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
 		  &cfg->fc_nlinfo, 0);

@@ -2128,50 +2129,34 @@ static void trie_show_usage(struct seq_f
 }
 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
 
+static void fib_trie_show(struct seq_file *seq, const char *name, struct trie *trie)
+{
+	struct trie_stat stat;
+
+	seq_printf(seq, "%s: %d\n", name, trie->size);
+	trie_collect_stats(trie, &stat);
+	trie_show_stats(seq, &stat);
+#ifdef CONFIG_IP_FIB_TRIE_STATS
+	trie_show_usage(seq, &trie->stats);
+#endif
+}
 
 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
 {
 	struct net *net = (struct net *)seq->private;
-	struct trie *trie_local, *trie_main;
-	struct trie_stat *stat;
 	struct fib_table *tb;
 
-	trie_local = NULL;
+	seq_printf(seq,
+		   "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
+		   sizeof(struct leaf), sizeof(struct tnode));
+
 	tb = fib_get_table(net, RT_TABLE_LOCAL);
 	if (tb)
-		trie_local = (struct trie *) tb->tb_data;
-
-	trie_main = NULL;
+		fib_trie_show(seq, "Local", (struct trie *) tb->tb_data);
+
 	tb = fib_get_table(net, RT_TABLE_MAIN);
 	if (tb)
-		trie_main = (struct trie *) tb->tb_data;
-
-
-	stat = kmalloc(sizeof(*stat), GFP_KERNEL);
-	if (!stat)
-		return -ENOMEM;
-
-	seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
-		   sizeof(struct leaf), sizeof(struct tnode));
-
-	if (trie_local) {
-		seq_printf(seq, "Local:\n");
-		trie_collect_stats(trie_local, stat);
-		trie_show_stats(seq, stat);
-#ifdef CONFIG_IP_FIB_TRIE_STATS
-		trie_show_usage(seq, &trie_local->stats);
-#endif
-	}
-
-	if (trie_main) {
-		seq_printf(seq, "Main:\n");
-		trie_collect_stats(trie_main, stat);

Keeping a 'size' counter is not necessary, since trie_collect_stats() must go through all the tree and get this information for free.

This 'size' field only slows down inserts/deletes and dirty a cacheline that readers will hit.

Show number of entries in trie, the size field was being set but never used, but it only counted leaves, not all entries. Refactor the two cases in fib_triestat_seq_show into a single routine.

Note: the stat structure was being malloc'd but the stack usage isn't so high (288 bytes) that it is worth the additional complexity.

Signed-off-by Stephen Hemminger <[email protected]>

Use %u instead of %d when printing unsigned values.

Signed-off-by Stephen Hemminger <[email protected]>

The only error from fib_insert_node is if memory allocation fails, so instead of passing by reference, just use the convention of returning NULL.

Signed-off-by Stephen Hemminger <[email protected]>

printk related cleanups:
* Get rid of unused printk wrappers.
* Make bug checks into KERN_WARNING because KERN_DEBUG gets ignored
* Turn one cryptic old message into something real
* Make sure all messages have KERN_XXX

The FIB TRIE code has a bunch of statistics, but the code is hidden behind an ifdef that was never implemented. Since it was dead code, it was broken as well.

This patch fixes that by making it a config option.

Signed-off-by Stephen Hemminger <[email protected]>