Jens Laas writes: > Here is rework and cleanup of the resize function. > > Some bugs we had. We were using ->parent when we should use > node_parent(). Also we used ->parent which is not assigned by > inflate in inflate loop. > > Also a fix to set thresholds to power 2 to fit halve > and double strategy. > > max_resize is renamed to max_work which better indicates > it's function. > > Reaching max_work is not an error, so warning is removed. > max_work only limits amount of work done per resize. > (limits CPU-usage, outstanding memory etc). > > The clean-up makes it relatively easy to add fixed sized > root-nodes if we would like to decrease the memory pressure > on routers with large routing tables and dynamic routing. > If we'll need that... > > Its been tested with 280k routes. > > Work done together with Robert Olsson. > > Signed-off-by: Jens Låås Right we think is a step forward. No performance differences seen either for lookup or insert. Signed-off-by: Robert Olsson Cheers. --ro PS. We see ~7 Gbit/s simplex routing w/o route cache using packet distribution seen on core links. Using multiQ of course > --- > net/ipv4/fib_trie.c | 95 ++++++++++++-------------------------------------- > 1 files changed, 23 insertions(+), 72 deletions(-) > > diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c > index fe3c846..291bdf5 100644 > --- a/net/ipv4/fib_trie.c > +++ b/net/ipv4/fib_trie.c > @@ -48,7 +48,7 @@ > * Patrick McHardy > */ > > -#define VERSION "0.408" > +#define VERSION "0.409" > > #include > #include > @@ -325,10 +325,7 @@ static inline void check_tnode(const struct tnode *tn) > static const int halve_threshold = 25; > static const int inflate_threshold = 50; > static const int halve_threshold_root = 15; > -static const int inflate_threshold_root = 25; > - > -static int inflate_threshold_root_fix; > -#define INFLATE_FIX_MAX 10 /* a comment in resize() */ > +static const int inflate_threshold_root = 30; > > static void __alias_free_mem(struct rcu_head *head) > { > @@ -516,14 +513,14 @@ static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, > rcu_assign_pointer(tn->child[i], n); > } > > +#define MAX_WORK 10 > static struct node *resize(struct trie *t, struct tnode *tn) > { > int i; > - int err = 0; > struct tnode *old_tn; > int inflate_threshold_use; > int halve_threshold_use; > - int max_resize; > + int max_work; > > if (!tn) > return NULL; > @@ -538,18 +535,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) > } > /* One child */ > if (tn->empty_children == tnode_child_length(tn) - 1) > - for (i = 0; i < tnode_child_length(tn); i++) { > - struct node *n; > - > - n = tn->child[i]; > - if (!n) > - continue; > - > - /* compress one level */ > - node_set_parent(n, NULL); > - tnode_free_safe(tn); > - return n; > - } > + goto one_child; > /* > * Double as long as the resulting node has a number of > * nonempty nodes that are above the threshold. > @@ -618,15 +604,17 @@ static struct node *resize(struct trie *t, struct tnode *tn) > > /* Keep root node larger */ > > - if (!tn->parent) > - inflate_threshold_use = inflate_threshold_root + > - inflate_threshold_root_fix; > - else > + if (!node_parent((struct node*) tn)) { > + inflate_threshold_use = inflate_threshold_root; > + halve_threshold_use = halve_threshold_root; > + } > + else { > inflate_threshold_use = inflate_threshold; > + halve_threshold_use = halve_threshold; > + } > > - err = 0; > - max_resize = 10; > - while ((tn->full_children > 0 && max_resize-- && > + max_work = MAX_WORK; > + while ((tn->full_children > 0 && max_work-- && > 50 * (tn->full_children + tnode_child_length(tn) > - tn->empty_children) > >= inflate_threshold_use * tnode_child_length(tn))) { > @@ -643,47 +631,19 @@ static struct node *resize(struct trie *t, struct tnode *tn) > } > } > > - if (max_resize < 0) { > - if (!tn->parent) { > - /* > - * It was observed that during large updates even > - * inflate_threshold_root = 35 might be needed to avoid > - * this warning; but it should be temporary, so let's > - * try to handle this automatically. > - */ > - if (inflate_threshold_root_fix < INFLATE_FIX_MAX) > - inflate_threshold_root_fix++; > - else > - pr_warning("Fix inflate_threshold_root." > - " Now=%d size=%d bits fix=%d\n", > - inflate_threshold_root, tn->bits, > - inflate_threshold_root_fix); > - } else { > - pr_warning("Fix inflate_threshold." > - " Now=%d size=%d bits\n", > - inflate_threshold, tn->bits); > - } > - } else if (max_resize > 3 && !tn->parent && inflate_threshold_root_fix) > - inflate_threshold_root_fix--; > - > check_tnode(tn); > > + /* Return if at least one inflate is run */ > + if( max_work != MAX_WORK) > + return (struct node *) tn; > + > /* > * Halve as long as the number of empty children in this > * node is above threshold. > */ > > - > - /* Keep root node larger */ > - > - if (!tn->parent) > - halve_threshold_use = halve_threshold_root; > - else > - halve_threshold_use = halve_threshold; > - > - err = 0; > - max_resize = 10; > - while (tn->bits > 1 && max_resize-- && > + max_work = MAX_WORK; > + while (tn->bits > 1 && max_work-- && > 100 * (tnode_child_length(tn) - tn->empty_children) < > halve_threshold_use * tnode_child_length(tn)) { > > @@ -698,19 +658,10 @@ static struct node *resize(struct trie *t, struct tnode *tn) > } > } > > - if (max_resize < 0) { > - if (!tn->parent) > - pr_warning("Fix halve_threshold_root." > - " Now=%d size=%d bits\n", > - halve_threshold_root, tn->bits); > - else > - pr_warning("Fix halve_threshold." > - " Now=%d size=%d bits\n", > - halve_threshold, tn->bits); > - } > > /* Only one child remains */ > - if (tn->empty_children == tnode_child_length(tn) - 1) > + if (tn->empty_children == tnode_child_length(tn) - 1) { > +one_child: > for (i = 0; i < tnode_child_length(tn); i++) { > struct node *n; > > @@ -724,7 +675,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) > tnode_free_safe(tn); > return n; > } > - > + } > return (struct node *) tn; > } > > -- > 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