1 files changed, 41 insertions, 60 deletions

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 63c2fa7b68c4..291bdf50a21f 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -48,7 +48,7 @@
  *              Patrick McHardy <kaber@trash.net>
  */
 
-#define VERSION "0.408"
+#define VERSION "0.409"
 
 #include <asm/uaccess.h>
 #include <asm/system.h>
@@ -164,6 +164,14 @@ 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 size_t tnode_free_size;
+
+/*
+ * synchronize_rcu after call_rcu for that many pages; it should be especially
+ * useful before resizing the root node with PREEMPT_NONE configs; the value was
+ * obtained experimentally, aiming to avoid visible slowdown.
+ */
+static const int sync_pages = 128;
 
 static struct kmem_cache *fn_alias_kmem __read_mostly;
 static struct kmem_cache *trie_leaf_kmem __read_mostly;
@@ -317,8 +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 const int inflate_threshold_root = 30;
 
 static void __alias_free_mem(struct rcu_head *head)
 {
@@ -393,6 +400,8 @@ static void tnode_free_safe(struct tnode *tn)
         BUG_ON(IS_LEAF(tn));
         tn->tnode_free = tnode_free_head;
         tnode_free_head = tn;
+        tnode_free_size += sizeof(struct tnode) +
+                           (sizeof(struct node *) << tn->bits);
 }
 
 static void tnode_free_flush(void)
@@ -404,6 +413,11 @@ static void tnode_free_flush(void)
                 tn->tnode_free = NULL;
                 tnode_free(tn);
         }
+
+        if (tnode_free_size >= PAGE_SIZE * sync_pages) {
+                tnode_free_size = 0;
+                synchronize_rcu();
+        }
 }
 
 static struct leaf *leaf_new(void)
@@ -499,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;
@@ -521,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.
@@ -601,14 +604,17 @@ static struct node *resize(struct trie *t, struct tnode *tn)
 
         /* Keep root node larger  */
 
-        if (!tn->parent)
+        if (!node_parent((struct node*) tn)) {
                 inflate_threshold_use = inflate_threshold_root;
-        else
+                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))) {
@@ -625,35 +631,19 @@ static struct node *resize(struct trie *t, struct tnode *tn)
                 }
         }
 
-        if (max_resize < 0) {
-                if (!tn->parent)
-                        pr_warning("Fix inflate_threshold_root."
-                                   " Now=%d size=%d bits\n",
-                                   inflate_threshold_root, tn->bits);
-                else
-                        pr_warning("Fix inflate_threshold."
-                                   " Now=%d size=%d bits\n",
-                                   inflate_threshold, tn->bits);
-        }
-
         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)) {
 
@@ -668,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;
 
@@ -694,7 +675,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
                         tnode_free_safe(tn);
                         return n;
                 }
-
+        }
         return (struct node *) tn;
 }
 
@@ -1435,7 +1416,7 @@ static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
                         cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
                                                    pos, bits);
 
-                n = tnode_get_child(pn, cindex);
+                n = tnode_get_child_rcu(pn, cindex);
 
                 if (n == NULL) {
 #ifdef CONFIG_IP_FIB_TRIE_STATS
@@ -1570,7 +1551,7 @@ backtrace:
                 if (chopped_off <= pn->bits) {
                         cindex &= ~(1 << (chopped_off-1));
                 } else {
-                        struct tnode *parent = node_parent((struct node *) pn);
+                        struct tnode *parent = node_parent_rcu((struct node *) pn);
                         if (!parent)
                                 goto failed;
 
@@ -1783,7 +1764,7 @@ static struct leaf *trie_firstleaf(struct trie *t)
 static struct leaf *trie_nextleaf(struct leaf *l)
 {
         struct node *c = (struct node *) l;
-        struct tnode *p = node_parent(c);
+        struct tnode *p = node_parent_rcu(c);
 
         if (!p)
                 return NULL;    /* trie with just one leaf */
@@ -2391,7 +2372,7 @@ static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
         }
 }
 
-static const char *rtn_type_names[__RTN_MAX] = {
+static const char *const rtn_type_names[__RTN_MAX] = {
         [RTN_UNSPEC] = "UNSPEC",
         [RTN_UNICAST] = "UNICAST",
         [RTN_LOCAL] = "LOCAL",