target/linux/generic/patches-3.18/080-15-fib_trie-Push-tnode-flushing-down-to-inflate-halve.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:56:49 -0800
   3 Subject: [PATCH] fib_trie: Push tnode flushing down to inflate/halve
   4
   5 This change pushes the tnode freeing down into the inflate and halve
   6 functions.  It makes more sense here as we have a better grasp of what is
   7 going on and when a given cluster of nodes is ready to be freed.
   8
   9 I believe this may address a bug in the freeing logic as well.  For some
  10 reason if the freelist got to a certain size we would call
  11 synchronize_rcu().  I'm assuming that what they meant to do is call
  12 synchronize_rcu() after they had handed off that much memory via
  13 call_rcu().  As such that is what I have updated the behavior to be.
  14
  15 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  16 Signed-off-by: David S. Miller <davem@davemloft.net>
  17 ---
  18
  19 --- a/net/ipv4/fib_trie.c
  20 +++ b/net/ipv4/fib_trie.c
  21 @@ -147,8 +147,6 @@ struct trie {
  22  };
  23
  24  static void resize(struct trie *t, struct tnode *tn);
  25 -/* tnodes to free after resize(); protected by RTNL */
  26 -static struct callback_head *tnode_free_head;
  27  static size_t tnode_free_size;
  28
  29  /*
  30 @@ -307,32 +305,6 @@ static struct tnode *tnode_alloc(size_t
  31                 return vzalloc(size);
  32  }
  33
  34 -static void tnode_free_safe(struct tnode *tn)
  35 -{
  36 -       BUG_ON(IS_LEAF(tn));
  37 -       tn->rcu.next = tnode_free_head;
  38 -       tnode_free_head = &tn->rcu;
  39 -}
  40 -
  41 -static void tnode_free_flush(void)
  42 -{
  43 -       struct callback_head *head;
  44 -
  45 -       while ((head = tnode_free_head)) {
  46 -               struct tnode *tn = container_of(head, struct tnode, rcu);
  47 -
  48 -               tnode_free_head = head->next;
  49 -               tnode_free_size += offsetof(struct tnode, child[1 << tn->bits]);
  50 -
  51 -               node_free(tn);
  52 -       }
  53 -
  54 -       if (tnode_free_size >= PAGE_SIZE * sync_pages) {
  55 -               tnode_free_size = 0;
  56 -               synchronize_rcu();
  57 -       }
  58 -}
  59 -
  60  static struct tnode *leaf_new(t_key key)
  61  {
  62         struct tnode *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
  63 @@ -433,17 +405,33 @@ static void put_child_root(struct tnode
  64                 rcu_assign_pointer(t->trie, n);
  65  }
  66
  67 -static void tnode_clean_free(struct tnode *tn)
  68 +static inline void tnode_free_init(struct tnode *tn)
  69  {
  70 -       struct tnode *tofree;
  71 -       unsigned long i;
  72 +       tn->rcu.next = NULL;
  73 +}
  74 +
  75 +static inline void tnode_free_append(struct tnode *tn, struct tnode *n)
  76 +{
  77 +       n->rcu.next = tn->rcu.next;
  78 +       tn->rcu.next = &n->rcu;
  79 +}
  80
  81 -       for (i = 0; i < tnode_child_length(tn); i++) {
  82 -               tofree = tnode_get_child(tn, i);
  83 -               if (tofree)
  84 -                       node_free(tofree);
  85 +static void tnode_free(struct tnode *tn)
  86 +{
  87 +       struct callback_head *head = &tn->rcu;
  88 +
  89 +       while (head) {
  90 +               head = head->next;
  91 +               tnode_free_size += offsetof(struct tnode, child[1 << tn->bits]);
  92 +               node_free(tn);
  93 +
  94 +               tn = container_of(head, struct tnode, rcu);
  95 +       }
  96 +
  97 +       if (tnode_free_size >= PAGE_SIZE * sync_pages) {
  98 +               tnode_free_size = 0;
  99 +               synchronize_rcu();
 100         }
 101 -       node_free(tn);
 102  }
 103
 104  static int inflate(struct trie *t, struct tnode *oldtnode)
 105 @@ -476,20 +464,23 @@ static int inflate(struct trie *t, struc
 106                                          inode->bits - 1);
 107                         if (!left)
 108                                 goto nomem;
 109 +                       tnode_free_append(tn, left);
 110
 111                         right = tnode_new(inode->key | m, inode->pos,
 112                                           inode->bits - 1);
 113
 114 -                       if (!right) {
 115 -                               node_free(left);
 116 +                       if (!right)
 117                                 goto nomem;
 118 -                       }
 119 +                       tnode_free_append(tn, right);
 120
 121                         put_child(tn, 2*i, left);
 122                         put_child(tn, 2*i+1, right);
 123                 }
 124         }
 125
 126 +       /* prepare oldtnode to be freed */
 127 +       tnode_free_init(oldtnode);
 128 +
 129         for (i = 0; i < olen; i++) {
 130                 struct tnode *inode = tnode_get_child(oldtnode, i);
 131                 struct tnode *left, *right;
 132 @@ -505,12 +496,13 @@ static int inflate(struct trie *t, struc
 133                         continue;
 134                 }
 135
 136 +               /* drop the node in the old tnode free list */
 137 +               tnode_free_append(oldtnode, inode);
 138 +
 139                 /* An internal node with two children */
 140                 if (inode->bits == 1) {
 141                         put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
 142                         put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
 143 -
 144 -                       tnode_free_safe(inode);
 145                         continue;
 146                 }
 147
 148 @@ -556,17 +548,19 @@ static int inflate(struct trie *t, struc
 149                 put_child(tn, 2 * i, left);
 150                 put_child(tn, 2 * i + 1, right);
 151
 152 -               tnode_free_safe(inode);
 153 -
 154 +               /* resize child nodes */
 155                 resize(t, left);
 156                 resize(t, right);
 157         }
 158
 159         put_child_root(tp, t, tn->key, tn);
 160 -       tnode_free_safe(oldtnode);
 161 +
 162 +       /* we completed without error, prepare to free old node */
 163 +       tnode_free(oldtnode);
 164         return 0;
 165  nomem:
 166 -       tnode_clean_free(tn);
 167 +       /* all pointers should be clean so we are done */
 168 +       tnode_free(tn);
 169         return -ENOMEM;
 170  }
 171
 172 @@ -599,17 +593,20 @@ static int halve(struct trie *t, struct
 173                         struct tnode *newn;
 174
 175                         newn = tnode_new(left->key, oldtnode->pos, 1);
 176 -
 177                         if (!newn) {
 178 -                               tnode_clean_free(tn);
 179 +                               tnode_free(tn);
 180                                 return -ENOMEM;
 181                         }
 182 +                       tnode_free_append(tn, newn);
 183
 184                         put_child(tn, i/2, newn);
 185                 }
 186
 187         }
 188
 189 +       /* prepare oldtnode to be freed */
 190 +       tnode_free_init(oldtnode);
 191 +
 192         for (i = 0; i < olen; i += 2) {
 193                 struct tnode *newBinNode;
 194
 195 @@ -636,11 +633,14 @@ static int halve(struct trie *t, struct
 196
 197                 put_child(tn, i / 2, newBinNode);
 198
 199 +               /* resize child node */
 200                 resize(t, newBinNode);
 201         }
 202
 203         put_child_root(tp, t, tn->key, tn);
 204 -       tnode_free_safe(oldtnode);
 205 +
 206 +       /* all pointers should be clean so we are done */
 207 +       tnode_free(oldtnode);
 208
 209         return 0;
 210  }
 211 @@ -798,7 +798,8 @@ no_children:
 212                 node_set_parent(n, tp);
 213
 214                 /* drop dead node */
 215 -               tnode_free_safe(tn);
 216 +               tnode_free_init(tn);
 217 +               tnode_free(tn);
 218         }
 219  }
 220
 221 @@ -884,16 +885,12 @@ static void trie_rebalance(struct trie *
 222
 223         while ((tp = node_parent(tn)) != NULL) {
 224                 resize(t, tn);
 225 -
 226 -               tnode_free_flush();
 227                 tn = tp;
 228         }
 229
 230         /* Handle last (top) tnode */
 231         if (IS_TNODE(tn))
 232                 resize(t, tn);
 233 -
 234 -       tnode_free_flush();
 235  }
 236
 237  /* only used from updater-side */