fib_trie: flush improvement

This is an attempt to fix the problem described in:

     http://bugzilla.kernel.org/show_bug.cgi?id=6648

I can reproduce this by loading lots and lots of routes and the taking the interface down. This causes all entries in trie to be flushed, but each leaf removal causes a rebalance of the trie. And since the removal is depth first, it creates lots of needless work.

Instead on flush, just walk the trie and prune as we go.
The implementation is for description only, it probably doesn't work yet.

Quoted 11 lines · Stephen Hemminger

This is an attempt to fix the problem described in:

     http://bugzilla.kernel.org/show_bug.cgi?id=6648

I can reproduce this by loading lots and lots of routes and the taking the interface down. This causes all entries in trie to be flushed, but each leaf removal causes a rebalance of the trie. And since the removal is depth first, it creates lots of needless work.

Instead on flush, just walk the trie and prune as we go.
The implementation is for description only, it probably doesn't work yet.

I dont get it, since the bug reporter mentions with recent kernels :

Fix inflate_threshold_root. Now=15 size=11 bits

Is it what you get with your tests ?

Pawel reports :

cat /proc/net/fib_triestat
Main: Aver depth: 2.26 Max depth: 6 Leaves: 235924
Internal nodes: 57854 1: 31632 2: 11422 3: 8475 4: 3755 5: 1676 6: 893 18: 1

Pointers: 609760 Null ptrs: 315983 Total size: 16240 kB

warning messages comes from rootnode that cannot be expanded, since it hits MAX_ORDER (on a 32bit x86)

(sizeof(struct tnode) + (sizeof(struct node *) << bits);) is rounded to 4 << (bit + 1), ie 2 << 20

For larger allocations Pawel has two choices :

change MAX_ORDER from 11 to 13 or 14
If this machine is a pure router, this change wont have performance impact.

Or (more difficult, but more appropriate for mainline) change fib_trie.c to use vmalloc() for very big allocaions (for the root only), and vfree()

Since vfree() cannot be called from rcu callback, one has to setup a struct work_struct helper.

Quoted 43 lines · Eric Dumazet

Quoted 12 lines · Stephen Hemminger

This is an attempt to fix the problem described in:

     http://bugzilla.kernel.org/show_bug.cgi?id=6648

I can reproduce this by loading lots and lots of routes and the taking the interface down. This causes all entries in trie to be flushed, but each leaf removal causes a rebalance of the trie. And since the removal is depth first, it creates lots of needless work.

Instead on flush, just walk the trie and prune as we go. The implementation is for description only, it probably doesn't work yet.

I dont get it, since the bug reporter mentions with recent kernels :

Fix inflate_threshold_root. Now=15 size=11 bits

Is it what you get with your tests ?

Pawel reports :

cat /proc/net/fib_triestat
Main: Aver depth: 2.26 Max depth: 6 Leaves: 235924
Internal nodes: 57854 1: 31632 2: 11422 3: 8475 4: 3755 5: 1676 6: 893 18: 1

Pointers: 609760 Null ptrs: 315983 Total size: 16240 kB

warning messages comes from rootnode that cannot be expanded, since it hits MAX_ORDER (on a 32bit x86)

(sizeof(struct tnode) + (sizeof(struct node *) << bits);) is rounded to 4 << (bit + 1), ie 2 << 20

For larger allocations Pawel has two choices :

change MAX_ORDER from 11 to 13 or 14
If this machine is a pure router, this change wont have performance impact.

Quoted 7 lines

Or (more difficult, but more appropriate for mainline) change fib_trie.c to use vmalloc() for very big allocaions (for the root only), and vfree()

Since vfree() cannot be called from rcu callback, one has to setup a struct work_struct helper.

Here is a patch (untested unfortunatly) to implement this.

[IPV4] fib_trie: root_tnode can benefit of vmalloc()

FIB_TRIE root node can be very large and currently hits MAX_ORDER limit. It also wastes about 50% of allocated size, because of power of two rounding of tnode.

A switch to vmalloc() can improve FIB_TRIE performance by allowing root node to grow
past the alloc_pages() limit, while preserving memory.

Special care must be taken to free such zone, as rcu handler is not allowed to call vfree(),
we use a worker instead.

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

Quoted 55 lines · On Wed, 02 Apr 2008 16:35:04 +0200 Eric Dumazet <[email protected]> wrote:

Quoted 32 lines · Eric Dumazet

Quoted 11 lines · Stephen Hemminger

This is an attempt to fix the problem described in:

     http://bugzilla.kernel.org/show_bug.cgi?id=6648

I can reproduce this by loading lots and lots of routes and the taking the interface down. This causes all entries in trie to be flushed, but each leaf removal causes a rebalance of the trie. And since the removal is depth first, it creates lots of needless work.

Instead on flush, just walk the trie and prune as we go.
The implementation is for description only, it probably doesn't work yet.

I dont get it, since the bug reporter mentions with recent kernels :

Fix inflate_threshold_root. Now=15 size=11 bits

Is it what you get with your tests ?

Pawel reports :

cat /proc/net/fib_triestat
Main: Aver depth: 2.26 Max depth: 6 Leaves: 235924
Internal nodes: 57854 1: 31632 2: 11422 3: 8475 4: 3755 5: 1676 6: 893 18: 1

Pointers: 609760 Null ptrs: 315983 Total size: 16240 kB

warning messages comes from rootnode that cannot be expanded, since it hits MAX_ORDER (on a 32bit x86)

(sizeof(struct tnode) + (sizeof(struct node *) << bits);) is rounded to 4 << (bit + 1), ie 2 << 20

Quoted 9 lines

For larger allocations Pawel has two choices :

change MAX_ORDER from 11 to 13 or 14
If this machine is a pure router, this change wont have performance impact.

Or (more difficult, but more appropriate for mainline) change fib_trie.c to use vmalloc() for very big allocaions (for the root only), and vfree()

Since vfree() cannot be called from rcu callback, one has to setup a struct work_struct helper.

Here is a patch (untested unfortunatly) to implement this.

[IPV4] fib_trie: root_tnode can benefit of vmalloc()

FIB_TRIE root node can be very large and currently hits MAX_ORDER limit. It also wastes about 50% of allocated size, because of power of two rounding of tnode.

A switch to vmalloc() can improve FIB_TRIE performance by allowing root node to grow past the alloc_pages() limit, while preserving memory.

Special care must be taken to free such zone, as rcu handler is not allowed to call vfree(), we use a worker instead.

Quoted 3 lines

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

Rather than switching between three allocation strategies, I would rather just have kmalloc and vmalloc.

Eric wisely pointed out that for larger sizes of nodes, the current allocation in fib_trie wastes lots of memory. For a sample of routes extracted from the bugzilla bug the largest node grows to 2M bytes on 64 bit system. This leads to 2044K of wasted memory.

There are two possible solutions (see attached). One uses vmalloc() rather than alloc_pages, but has to add complexity on freeing. The other adds a layer of indirection to the tnode lookup.

Both have been tested on net-2.6.26 with the huge route table. I slightly prefer the vmalloc version, but both work fine.

IPV4: fib_trie use vmalloc for large tnodes

Use vmalloc rather than alloc_pages to avoid wasting memory. The problem is that tnode structure has a power of 2 sized array, plus a header. So the current code wastes almost half the memory allocated because it always needs the next bigger size to hold that small header.

This is similar to an earlier patch by Eric, but instead of a list and lock, I used a workqueue to handle the fact that vfree can't be done in interrupt context.

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

---
 net/ipv4/fib_trie.c |   25 +++++++++++++++----------
 1 file changed, 15 insertions(+), 10 deletions(-)

net/ipv4/fib_trie.c +15 -10

@@ -122,7 +122,10 @@ struct tnode {
 	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
 	unsigned int full_children;	/* KEYLENGTH bits needed */
 	unsigned int empty_children;	/* KEYLENGTH bits needed */
-	struct rcu_head rcu;
+	union {
+		struct rcu_head rcu;
+		struct work_struct work;
+	};
 	struct node *child[0];
 };
 

@@ -350,16 +353,16 @@ static inline void free_leaf_info(struct
 
 static struct tnode *tnode_alloc(size_t size)
 {
-	struct page *pages;
-
 	if (size <= PAGE_SIZE)
 		return kzalloc(size, GFP_KERNEL);
+	else
+		return __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
+}
 
-	pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
-	if (!pages)
-		return NULL;
-
-	return page_address(pages);
+static void __tnode_vfree(struct work_struct *arg)
+{
+	struct tnode *tn = container_of(arg, struct tnode, work);
+	vfree(tn);
 }
 
 static void __tnode_free_rcu(struct rcu_head *head)

@@ -370,8 +373,10 @@ static void __tnode_free_rcu(struct rcu_
 
 	if (size <= PAGE_SIZE)
 		kfree(tn);
-	else
-		free_pages((unsigned long)tn, get_order(size));
+	else {
+		INIT_WORK(&tn->work, __tnode_vfree);
+		schedule_work(&tn->work);
+	}
 }
 
 static inline void tnode_free(struct tnode *tn)

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 <[email protected]>

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

net/ipv4/fib_trie.c +26 -17

@@ -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;

Do we get slower with vmalloc due to TLB-lookups etc? Guess this should be investigated.

Quoted 2 lines

Do we get slower with vmalloc due to TLB-lookups etc? Guess this should be investigated.

In some cases it might even go faster because a lot of x86 CPUs have far more 4K TLBs than 2M TLBs. vmalloc is just quite expensive in setup/free time, but that shouldn't be a big issue here.

Quoted 3 lines · Andi Kleen

Quoted 2 lines

Do we get slower with vmalloc due to TLB-lookups etc? Guess this should be investigated.

Quoted 3 lines

In some cases it might even go faster because a lot of x86 CPUs have far more 4K TLBs than 2M TLBs. vmalloc is just quite expensive in setup/free time, but that shouldn't be a big issue here.

I've did some rDoS testing and the lookup performance is the same or slightly better. So it should be fine.

Quoted 5 lines · Robert Olsson

Quoted 3 lines · Andi Kleen

Quoted 2 lines

Do we get slower with vmalloc due to TLB-lookups etc? Guess this should be investigated.

Quoted 8 lines

Quoted 3 lines

In some cases it might even go faster because a lot of x86 CPUs have far more 4K TLBs than 2M TLBs. vmalloc is just quite expensive in setup/free time, but that shouldn't be a big issue here.

I've did some rDoS testing and the lookup performance is the same or slightly better. So it should be fine.

If you want more realistic worst case numbers run something in user space in the background that thrashes the TLBs constantly and then see how the numbers change.

The main advantage of using large pages is that they tend to be separated
from 4K TLBs and since most user space doesn't use large pages it gives the kernel an effective private TLB pool.

With vmalloc it will now compete with whatever other TLB pigs are active.

Eric wisely pointed out that for larger sizes of nodes, the current allocation in fib_trie wastes lots of memory. For a sample of routes extracted from the bugzilla bug the largest node grows to 2M bytes on 64 bit system. This leads to 2044K of wasted memory.

There are two possible solutions (see attached). One uses vmalloc() rather than alloc_pages, but has to add complexity on freeing. The other adds a layer of indirection to the tnode lookup.

Both have been tested on net-2.6.26 with the huge route table. I slightly prefer the vmalloc version, but both work fine.

------------------------------------------------------------------------

IPV4: fib_trie use vmalloc for large tnodes

Use vmalloc rather than alloc_pages to avoid wasting memory. The problem is that tnode structure has a power of 2 sized array, plus a header. So the current code wastes almost half the memory allocated because it always needs the next bigger size to hold that small header.

This is similar to an earlier patch by Eric, but instead of a list and lock, I used a workqueue to handle the fact that vfree can't be done in interrupt context.

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

---
 net/ipv4/fib_trie.c |   25 +++++++++++++++----------
 1 file changed, 15 insertions(+), 10 deletions(-)

Quoted 36 lines · Stephen Hemminger

Eric wisely pointed out that for larger sizes of nodes, the current allocation in fib_trie wastes lots of memory. For a sample of routes extracted from the bugzilla bug the largest node grows to 2M bytes on 64 bit system. This leads to 2044K of wasted memory.

There are two possible solutions (see attached). One uses vmalloc() rather than alloc_pages, but has to add complexity on freeing. The other adds a layer of indirection to the tnode lookup.

Both have been tested on net-2.6.26 with the huge route table. I slightly prefer the vmalloc version, but both work fine.

------------------------------------------------------------------------

IPV4: fib_trie use vmalloc for large tnodes

Use vmalloc rather than alloc_pages to avoid wasting memory. The problem is that tnode structure has a power of 2 sized array, plus a header. So the current code wastes almost half the memory allocated because it always needs the next bigger size to hold that small header.

This is similar to an earlier patch by Eric, but instead of a list and lock, I used a workqueue to handle the fact that vfree can't be done in interrupt context.

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

---
 net/ipv4/fib_trie.c |   25 +++++++++++++++----------
 1 file changed, 15 insertions(+), 10 deletions(-)

net/ipv4/fib_trie.c struct tnode { · line 130

Quoted 10 lines

net/ipv4/fib_trie.c +4 -1

@@ -122,7 +122,10 @@ struct tnode {
 	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
 	unsigned int full_children;	/* KEYLENGTH bits needed */
 	unsigned int empty_children;	/* KEYLENGTH bits needed */
-	struct rcu_head rcu;
+	union {
+		struct rcu_head rcu;
+		struct work_struct work;
+	};
 	struct node *child[0];
 

Hum...

I prefer my patch Stephen, as your version enlarges every tnode with an embedded "struct work_struct" which can be larger than a "struct rcu_head"

Quoted 2 lines · On Mon, 07 Apr 2008 18:46:29 +0200 Eric Dumazet <[email protected]> wrote:

I prefer my patch Stephen, as your version enlarges every tnode with an embedded "struct work_struct" which can be larger than a "struct rcu_head"

The number of tnode's is small and the size growth of 2*(unsigned long) is not worth worrying about. Also theoretically, my version could have multiple work elements processed at once.

This is an attempt to fix the problem described in:

     http://bugzilla.kernel.org/show_bug.cgi?id=6648

I can reproduce this by loading lots and lots of routes and the taking the interface down. This causes all entries in trie to be flushed, but each leaf removal causes a rebalance of the trie. And since the removal is depth first, it creates lots of needless work.

Instead on flush, just walk the trie and prune as we go.

net/ipv4/fib_trie.c +54 -28

@@ -1665,7 +1665,7 @@ static int fn_trie_delete(struct fib_tab
 	return 0;
 }
 
-static int trie_flush_list(struct trie *t, struct list_head *head)
+static int trie_flush_list(struct list_head *head)
 {
 	struct fib_alias *fa, *fa_node;
 	int found = 0;

@@ -1683,24 +1683,74 @@ static int trie_flush_list(struct trie *
 	return found;
 }
 
-static int trie_flush_leaf(struct trie *t, struct leaf *l)
+static int trie_flush_leaf(struct leaf *l)
 {
-	int found = 0;
 	struct hlist_head *lih = &l->list;
 	struct hlist_node *node, *tmp;
 	struct leaf_info *li = NULL;
+	int found = 0;
 
 	hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
-		found += trie_flush_list(t, &li->falh);
+		found += trie_flush_list(&li->falh);
 
 		if (list_empty(&li->falh)) {
 			hlist_del_rcu(&li->hlist);
 			free_leaf_info(li);
 		}
 	}
+	tnode_free((struct tnode *) l);
+
 	return found;
 }
 
+static int trie_flush(struct tnode *p)
+{
+	struct node *c = NULL;
+	t_key idx = 0;
+	int found = 0;
+
+	for(;;) {
+		for ( ;idx < (1u << p->bits); ++idx) {
+			struct node *c = p->child[idx];
+			if (!c)
+				continue;
+
+			rcu_assign_pointer(p->child[idx], NULL);
+			if (IS_LEAF(c)) {
+				found += trie_flush_leaf((struct leaf *) c);
+				continue;
+			}
+
+			/* Descend one level */
+			p = (struct tnode *) c;
+			idx = 0;
+		}
+
+		/* Node empty, free and go back up */
+		tnode_free((struct tnode *) c);
+		c = (struct node *) p;
+		p = node_parent(c);
+		if (p == NULL)
+			return found; /* at root */
+
+		idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
+	}
+}
+
+static int fn_trie_flush(struct fib_table *tb)
+{
+	struct trie *t = (struct trie *) tb->tb_data;
+	struct tnode *n = (struct tnode *) t->trie;
+
+	ASSERT_RTNL();
+	rcu_assign_pointer(t->trie, NULL);
+
+	if (IS_LEAF(n))
+		return trie_flush_leaf((struct leaf *) n);
+	else
+		return trie_flush(n);
+}
+
 /*
  * Scan for the next right leaf starting at node p->child[idx]
  * Since we have back pointer, no recursion necessary.

@@ -1772,30 +1822,6 @@ static struct leaf *trie_leafindex(struc
 }
 
 
-/*
- * Caller must hold RTNL.
- */
-static int fn_trie_flush(struct fib_table *tb)
-{
-	struct trie *t = (struct trie *) tb->tb_data;
-	struct leaf *l, *ll = NULL;
-	int found = 0;
-
-	for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
-		found += trie_flush_leaf(t, l);
-
-		if (ll && hlist_empty(&ll->list))
-			trie_leaf_remove(t, ll);
-		ll = l;
-	}
-
-	if (ll && hlist_empty(&ll->list))
-		trie_leaf_remove(t, ll);
-
-	pr_debug("trie_flush found=%d\n", found);
-	return found;
-}
-
 static void fn_trie_select_default(struct fib_table *tb,
 				   const struct flowi *flp,
 				   struct fib_result *res)