Re: rib_trie / Fix inflate_threshold_root. Now=15 size=11 bits
From: Paweł Staszewski <hidden>
Date: 2009-06-29 08:08:11
Jarek Poplawski pisze:
To David Miller: since among patches tested negatively by Pawel are current 2 fixes from 2.6.31-rc, I hope they weren't sent to -stable yet. Otherwise, please withdraw them until they are tested alone. Thanks. To Pawel: On Sun, Jun 28, 2009 at 05:48:19PM +0200, Paweł Staszewski wrote:quoted
After apply this patch something is wrong Traffic is not forwarded no info in dmesg / no info from bgp and also i can't connect to bgpd process I revert kernel to past version with first Jarek patchSince checking this can take time I attach here a patch with only changes which are currently in 2.6.31-rc. Of course, this part can be broken as well, so it's up to you: if you could try it with caution somewhere it would be very helpful; otherwise don't bother. It could be applied to 2.6.29 with or without this currently working patch.
Ok.
I applied this patch 15mins ago to 2.6.29.5 and now it's working -
traffic is forwarded.
Some fib_triestats
cat /proc/net/fib_triestat
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.29
Max depth: 6
Leaves: 277015
Prefixes: 290493
Internal nodes: 67115
1: 35733 2: 13635 3: 9544 4: 4832 5: 2239 6: 1125 7: 5
9: 1 18: 1
Pointers: 686614
Null ptrs: 342485
Total size: 18396 kB
Counters:
---------
gets = 3956301
backtracks = 192497
semantic match passed = 3895955
semantic match miss = 133
null node hit= 4306948
skipped node resize = 0
Local:
Aver depth: 3.75
Max depth: 5
Leaves: 12
Prefixes: 13
Internal nodes: 10
1: 9 2: 1
Pointers: 22
Null ptrs: 1
Total size: 2 kB
Counters:
---------
gets = 3960981
backtracks = 2152441
semantic match passed = 4757
semantic match miss = 0
null node hit= 194997
skipped node resize = 0
quoted hunk ↗ jump to hunk
Thanks, Jarek P.--- (for 2.6.29.x, .28 or .27)diff -Nurp a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c--- a/net/ipv4/fib_trie.c 2009-06-27 20:25:06.000000000 +0200 +++ b/net/ipv4/fib_trie.c 2009-06-28 23:06:02.000000000 +0200@@ -123,6 +123,7 @@ struct tnode { union { struct rcu_head rcu; struct work_struct work; + struct tnode *tnode_free; }; struct node *child[0]; };@@ -161,6 +162,8 @@ static void tnode_put_child_reorg(struct static struct node *resize(struct trie *t, struct tnode *tn); static struct tnode *inflate(struct trie *t, struct tnode *tn); static struct tnode *halve(struct trie *t, struct tnode *tn); +/* tnodes to free after resize(); protected by RTNL */ +static struct tnode *tnode_free_head; static struct kmem_cache *fn_alias_kmem __read_mostly; static struct kmem_cache *trie_leaf_kmem __read_mostly;@@ -385,6 +388,24 @@ static inline void tnode_free(struct tno call_rcu(&tn->rcu, __tnode_free_rcu); } +static void tnode_free_safe(struct tnode *tn) +{ + BUG_ON(IS_LEAF(tn)); + tn->tnode_free = tnode_free_head; + tnode_free_head = tn; +} + +static void tnode_free_flush(void) +{ + struct tnode *tn; + + while ((tn = tnode_free_head)) { + tnode_free_head = tn->tnode_free; + tn->tnode_free = NULL; + tnode_free(tn); + } +} + static struct leaf *leaf_new(void) { struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);@@ -495,7 +516,7 @@ static struct node *resize(struct trie * /* No children */ if (tn->empty_children == tnode_child_length(tn)) { - tnode_free(tn); + tnode_free_safe(tn); return NULL; } /* One child */@@ -509,7 +530,7 @@ static struct node *resize(struct trie * /* compress one level */ node_set_parent(n, NULL); - tnode_free(tn); + tnode_free_safe(tn); return n; } /*@@ -670,7 +691,7 @@ static struct node *resize(struct trie * /* compress one level */ node_set_parent(n, NULL); - tnode_free(tn); + tnode_free_safe(tn); return n; }@@ -756,7 +777,7 @@ static struct tnode *inflate(struct trie put_child(t, tn, 2*i, inode->child[0]); put_child(t, tn, 2*i+1, inode->child[1]); - tnode_free(inode); + tnode_free_safe(inode); continue; }@@ -801,9 +822,9 @@ static struct tnode *inflate(struct trie put_child(t, tn, 2*i, resize(t, left)); put_child(t, tn, 2*i+1, resize(t, right)); - tnode_free(inode); + tnode_free_safe(inode); } - tnode_free(oldtnode); + tnode_free_safe(oldtnode); return tn; nomem: {@@ -885,7 +906,7 @@ static struct tnode *halve(struct trie * put_child(t, newBinNode, 1, right); put_child(t, tn, i/2, resize(t, newBinNode)); } - tnode_free(oldtnode); + tnode_free_safe(oldtnode); return tn; nomem: {@@ -983,12 +1004,14 @@ fib_find_node(struct trie *t, u32 key) return NULL; } -static struct node *trie_rebalance(struct trie *t, struct tnode *tn) +static void trie_rebalance(struct trie *t, struct tnode *tn) { int wasfull; - t_key cindex, key = tn->key; + t_key cindex, key; struct tnode *tp; + key = tn->key; + while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) { cindex = tkey_extract_bits(key, tp->pos, tp->bits); wasfull = tnode_full(tp, tnode_get_child(tp, cindex));@@ -998,6 +1021,7 @@ static struct node *trie_rebalance(struc (struct node *)tn, wasfull); tp = node_parent((struct node *) tn); + tnode_free_flush(); if (!tp) break; tn = tp;@@ -1007,7 +1031,10 @@ static struct node *trie_rebalance(struc if (IS_TNODE(tn)) tn = (struct tnode *)resize(t, (struct tnode *)tn); - return (struct node *)tn; + rcu_assign_pointer(t->trie, (struct node *)tn); + tnode_free_flush(); + + return; } /* only used from updater-side */@@ -1155,7 +1182,7 @@ static struct list_head *fib_insert_node /* Rebalance the trie */ - rcu_assign_pointer(t->trie, trie_rebalance(t, tp)); + trie_rebalance(t, tp); done: return fa_head; }@@ -1575,7 +1602,7 @@ static void trie_leaf_remove(struct trie if (tp) { t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits); put_child(t, (struct tnode *)tp, cindex, NULL); - rcu_assign_pointer(t->trie, trie_rebalance(t, tp)); + trie_rebalance(t, tp); } else rcu_assign_pointer(t->trie, NULL);