target/linux/generic/patches-3.18/080-14-fib_trie-Push-assignment-of-child-to-parent-down-int.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:56:43 -0800
   3 Subject: [PATCH] fib_trie: Push assignment of child to parent down into
   4  inflate/halve
   5
   6 This change makes it so that the assignment of the tnode to the parent is
   7 handled directly within whatever function is currently handling the node be
   8 it inflate, halve, or resize.  By doing this we can avoid some of the need
   9 to set NULL pointers in the tree while we are resizing the subnodes.
  10
  11 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  12 Signed-off-by: David S. Miller <davem@davemloft.net>
  13 ---
  14
  15 --- a/net/ipv4/fib_trie.c
  16 +++ b/net/ipv4/fib_trie.c
  17 @@ -146,9 +146,7 @@ struct trie {
  18  #endif
  19  };
  20
  21 -static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
  22 -                                 struct tnode *n, int wasfull);
  23 -static struct tnode *resize(struct trie *t, struct tnode *tn);
  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 @@ -396,22 +394,13 @@ static inline int tnode_full(const struc
  29         return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
  30  }
  31
  32 -static inline void put_child(struct tnode *tn, unsigned long i,
  33 -                            struct tnode *n)
  34 -{
  35 -       tnode_put_child_reorg(tn, i, n, -1);
  36 -}
  37 -
  38 - /*
  39 -  * Add a child at position i overwriting the old value.
  40 -  * Update the value of full_children and empty_children.
  41 -  */
  42 -
  43 -static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
  44 -                                 struct tnode *n, int wasfull)
  45 +/* Add a child at position i overwriting the old value.
  46 + * Update the value of full_children and empty_children.
  47 + */
  48 +static void put_child(struct tnode *tn, unsigned long i, struct tnode *n)
  49  {
  50         struct tnode *chi = rtnl_dereference(tn->child[i]);
  51 -       int isfull;
  52 +       int isfull, wasfull;
  53
  54         BUG_ON(i >= tnode_child_length(tn));
  55
  56 @@ -422,10 +411,9 @@ static void tnode_put_child_reorg(struct
  57                 tn->empty_children--;
  58
  59         /* update fullChildren */
  60 -       if (wasfull == -1)
  61 -               wasfull = tnode_full(tn, chi);
  62 -
  63 +       wasfull = tnode_full(tn, chi);
  64         isfull = tnode_full(tn, n);
  65 +
  66         if (wasfull && !isfull)
  67                 tn->full_children--;
  68         else if (!wasfull && isfull)
  69 @@ -458,9 +446,10 @@ static void tnode_clean_free(struct tnod
  70         node_free(tn);
  71  }
  72
  73 -static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
  74 +static int inflate(struct trie *t, struct tnode *oldtnode)
  75  {
  76         unsigned long olen = tnode_child_length(oldtnode);
  77 +       struct tnode *tp = node_parent(oldtnode);
  78         struct tnode *tn;
  79         unsigned long i;
  80         t_key m;
  81 @@ -468,9 +457,8 @@ static struct tnode *inflate(struct trie
  82         pr_debug("In inflate\n");
  83
  84         tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
  85 -
  86         if (!tn)
  87 -               return ERR_PTR(-ENOMEM);
  88 +               return -ENOMEM;
  89
  90         /*
  91          * Preallocate and store tnodes before the actual work so we
  92 @@ -564,30 +552,36 @@ static struct tnode *inflate(struct trie
  93                         put_child(left, j, rtnl_dereference(inode->child[j]));
  94                         put_child(right, j, rtnl_dereference(inode->child[j + size]));
  95                 }
  96 -               put_child(tn, 2*i, resize(t, left));
  97 -               put_child(tn, 2*i+1, resize(t, right));
  98 +
  99 +               put_child(tn, 2 * i, left);
 100 +               put_child(tn, 2 * i + 1, right);
 101
 102                 tnode_free_safe(inode);
 103 +
 104 +               resize(t, left);
 105 +               resize(t, right);
 106         }
 107 +
 108 +       put_child_root(tp, t, tn->key, tn);
 109         tnode_free_safe(oldtnode);
 110 -       return tn;
 111 +       return 0;
 112  nomem:
 113         tnode_clean_free(tn);
 114 -       return ERR_PTR(-ENOMEM);
 115 +       return -ENOMEM;
 116  }
 117
 118 -static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
 119 +static int halve(struct trie *t, struct tnode *oldtnode)
 120  {
 121         unsigned long olen = tnode_child_length(oldtnode);
 122 +       struct tnode *tp = node_parent(oldtnode);
 123         struct tnode *tn, *left, *right;
 124         int i;
 125
 126         pr_debug("In halve\n");
 127
 128         tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
 129 -
 130         if (!tn)
 131 -               return ERR_PTR(-ENOMEM);
 132 +               return -ENOMEM;
 133
 134         /*
 135          * Preallocate and store tnodes before the actual work so we
 136 @@ -606,8 +600,10 @@ static struct tnode *halve(struct trie *
 137
 138                         newn = tnode_new(left->key, oldtnode->pos, 1);
 139
 140 -                       if (!newn)
 141 -                               goto nomem;
 142 +                       if (!newn) {
 143 +                               tnode_clean_free(tn);
 144 +                               return -ENOMEM;
 145 +                       }
 146
 147                         put_child(tn, i/2, newn);
 148                 }
 149 @@ -635,16 +631,18 @@ static struct tnode *halve(struct trie *
 150
 151                 /* Two nonempty children */
 152                 newBinNode = tnode_get_child(tn, i/2);
 153 -               put_child(tn, i/2, NULL);
 154                 put_child(newBinNode, 0, left);
 155                 put_child(newBinNode, 1, right);
 156 -               put_child(tn, i/2, resize(t, newBinNode));
 157 +
 158 +               put_child(tn, i / 2, newBinNode);
 159 +
 160 +               resize(t, newBinNode);
 161         }
 162 +
 163 +       put_child_root(tp, t, tn->key, tn);
 164         tnode_free_safe(oldtnode);
 165 -       return tn;
 166 -nomem:
 167 -       tnode_clean_free(tn);
 168 -       return ERR_PTR(-ENOMEM);
 169 +
 170 +       return 0;
 171  }
 172
 173  /* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
 174 @@ -704,45 +702,48 @@ nomem:
 175   *    tnode_child_length(tn)
 176   *
 177   */
 178 -static bool should_inflate(const struct tnode *tn)
 179 +static bool should_inflate(const struct tnode *tp, const struct tnode *tn)
 180  {
 181         unsigned long used = tnode_child_length(tn);
 182         unsigned long threshold = used;
 183
 184         /* Keep root node larger */
 185 -       threshold *= node_parent(tn) ? inflate_threshold :
 186 -                                      inflate_threshold_root;
 187 +       threshold *= tp ? inflate_threshold : inflate_threshold_root;
 188         used += tn->full_children;
 189         used -= tn->empty_children;
 190
 191         return tn->pos && ((50 * used) >= threshold);
 192  }
 193
 194 -static bool should_halve(const struct tnode *tn)
 195 +static bool should_halve(const struct tnode *tp, const struct tnode *tn)
 196  {
 197         unsigned long used = tnode_child_length(tn);
 198         unsigned long threshold = used;
 199
 200         /* Keep root node larger */
 201 -       threshold *= node_parent(tn) ? halve_threshold :
 202 -                                      halve_threshold_root;
 203 +       threshold *= tp ? halve_threshold : halve_threshold_root;
 204         used -= tn->empty_children;
 205
 206         return (tn->bits > 1) && ((100 * used) < threshold);
 207  }
 208
 209  #define MAX_WORK 10
 210 -static struct tnode *resize(struct trie *t, struct tnode *tn)
 211 +static void resize(struct trie *t, struct tnode *tn)
 212  {
 213 -       struct tnode *old_tn, *n = NULL;
 214 +       struct tnode *tp = node_parent(tn), *n = NULL;
 215 +       struct tnode __rcu **cptr;
 216         int max_work;
 217
 218 -       if (!tn)
 219 -               return NULL;
 220 -
 221         pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
 222                  tn, inflate_threshold, halve_threshold);
 223
 224 +       /* track the tnode via the pointer from the parent instead of
 225 +        * doing it ourselves.  This way we can let RCU fully do its
 226 +        * thing without us interfering
 227 +        */
 228 +       cptr = tp ? &tp->child[get_index(tn->key, tp)] : &t->trie;
 229 +       BUG_ON(tn != rtnl_dereference(*cptr));
 230 +
 231         /* No children */
 232         if (tn->empty_children > (tnode_child_length(tn) - 1))
 233                 goto no_children;
 234 @@ -755,39 +756,35 @@ static struct tnode *resize(struct trie
 235          * nonempty nodes that are above the threshold.
 236          */
 237         max_work = MAX_WORK;
 238 -       while (should_inflate(tn) && max_work--) {
 239 -               old_tn = tn;
 240 -               tn = inflate(t, tn);
 241 -
 242 -               if (IS_ERR(tn)) {
 243 -                       tn = old_tn;
 244 +       while (should_inflate(tp, tn) && max_work--) {
 245 +               if (inflate(t, tn)) {
 246  #ifdef CONFIG_IP_FIB_TRIE_STATS
 247                         this_cpu_inc(t->stats->resize_node_skipped);
 248  #endif
 249                         break;
 250                 }
 251 +
 252 +               tn = rtnl_dereference(*cptr);
 253         }
 254
 255         /* Return if at least one inflate is run */
 256         if (max_work != MAX_WORK)
 257 -               return tn;
 258 +               return;
 259
 260         /* Halve as long as the number of empty children in this
 261          * node is above threshold.
 262          */
 263         max_work = MAX_WORK;
 264 -       while (should_halve(tn) && max_work--) {
 265 -               old_tn = tn;
 266 -               tn = halve(t, tn);
 267 -               if (IS_ERR(tn)) {
 268 -                       tn = old_tn;
 269 +       while (should_halve(tp, tn) && max_work--) {
 270 +               if (halve(t, tn)) {
 271  #ifdef CONFIG_IP_FIB_TRIE_STATS
 272                         this_cpu_inc(t->stats->resize_node_skipped);
 273  #endif
 274                         break;
 275                 }
 276 -       }
 277
 278 +               tn = rtnl_dereference(*cptr);
 279 +       }
 280
 281         /* Only one child remains */
 282         if (tn->empty_children == (tnode_child_length(tn) - 1)) {
 283 @@ -797,11 +794,12 @@ one_child:
 284                         n = tnode_get_child(tn, --i);
 285  no_children:
 286                 /* compress one level */
 287 -               node_set_parent(n, NULL);
 288 +               put_child_root(tp, t, tn->key, n);
 289 +               node_set_parent(n, tp);
 290 +
 291 +               /* drop dead node */
 292                 tnode_free_safe(tn);
 293 -               return n;
 294         }
 295 -       return tn;
 296  }
 297
 298  /* readside must use rcu_read_lock currently dump routines
 299 @@ -882,34 +880,19 @@ static struct tnode *fib_find_node(struc
 300
 301  static void trie_rebalance(struct trie *t, struct tnode *tn)
 302  {
 303 -       int wasfull;
 304 -       t_key cindex, key;
 305         struct tnode *tp;
 306
 307 -       key = tn->key;
 308 -
 309 -       while (tn != NULL && (tp = node_parent(tn)) != NULL) {
 310 -               cindex = get_index(key, tp);
 311 -               wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
 312 -               tn = resize(t, tn);
 313 -
 314 -               tnode_put_child_reorg(tp, cindex, tn, wasfull);
 315 -
 316 -               tp = node_parent(tn);
 317 -               if (!tp)
 318 -                       rcu_assign_pointer(t->trie, tn);
 319 +       while ((tp = node_parent(tn)) != NULL) {
 320 +               resize(t, tn);
 321
 322                 tnode_free_flush();
 323 -               if (!tp)
 324 -                       break;
 325                 tn = tp;
 326         }
 327
 328         /* Handle last (top) tnode */
 329         if (IS_TNODE(tn))
 330 -               tn = resize(t, tn);
 331 +               resize(t, tn);
 332
 333 -       rcu_assign_pointer(t->trie, tn);
 334         tnode_free_flush();
 335  }
 336