target/linux/generic/pending-3.18/080-12-fib_trie-Move-resize-to-after-inflate-halve.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:56:31 -0800
   3 Subject: [PATCH] fib_trie: Move resize to after inflate/halve
   4
   5 This change consists of a cut/paste of resize to behind inflate and halve
   6 so that I could remove the two function prototypes.
   7
   8 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
   9 Signed-off-by: David S. Miller <davem@davemloft.net>
  10 ---
  11
  12 --- a/net/ipv4/fib_trie.c
  13 +++ b/net/ipv4/fib_trie.c
  14 @@ -149,8 +149,6 @@ struct trie {
  15  static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
  16                                   struct tnode *n, int wasfull);
  17  static struct tnode *resize(struct trie *t, struct tnode *tn);
  18 -static struct tnode *inflate(struct trie *t, struct tnode *tn);
  19 -static struct tnode *halve(struct trie *t, struct tnode *tn);
  20  /* tnodes to free after resize(); protected by RTNL */
  21  static struct callback_head *tnode_free_head;
  22  static size_t tnode_free_size;
  23 @@ -447,161 +445,6 @@ static void put_child_root(struct tnode
  24                 rcu_assign_pointer(t->trie, n);
  25  }
  26
  27 -#define MAX_WORK 10
  28 -static struct tnode *resize(struct trie *t, struct tnode *tn)
  29 -{
  30 -       struct tnode *old_tn, *n = NULL;
  31 -       int inflate_threshold_use;
  32 -       int halve_threshold_use;
  33 -       int max_work;
  34 -
  35 -       if (!tn)
  36 -               return NULL;
  37 -
  38 -       pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
  39 -                tn, inflate_threshold, halve_threshold);
  40 -
  41 -       /* No children */
  42 -       if (tn->empty_children > (tnode_child_length(tn) - 1))
  43 -               goto no_children;
  44 -
  45 -       /* One child */
  46 -       if (tn->empty_children == (tnode_child_length(tn) - 1))
  47 -               goto one_child;
  48 -       /*
  49 -        * Double as long as the resulting node has a number of
  50 -        * nonempty nodes that are above the threshold.
  51 -        */
  52 -
  53 -       /*
  54 -        * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
  55 -        * the Helsinki University of Technology and Matti Tikkanen of Nokia
  56 -        * Telecommunications, page 6:
  57 -        * "A node is doubled if the ratio of non-empty children to all
  58 -        * children in the *doubled* node is at least 'high'."
  59 -        *
  60 -        * 'high' in this instance is the variable 'inflate_threshold'. It
  61 -        * is expressed as a percentage, so we multiply it with
  62 -        * tnode_child_length() and instead of multiplying by 2 (since the
  63 -        * child array will be doubled by inflate()) and multiplying
  64 -        * the left-hand side by 100 (to handle the percentage thing) we
  65 -        * multiply the left-hand side by 50.
  66 -        *
  67 -        * The left-hand side may look a bit weird: tnode_child_length(tn)
  68 -        * - tn->empty_children is of course the number of non-null children
  69 -        * in the current node. tn->full_children is the number of "full"
  70 -        * children, that is non-null tnodes with a skip value of 0.
  71 -        * All of those will be doubled in the resulting inflated tnode, so
  72 -        * we just count them one extra time here.
  73 -        *
  74 -        * A clearer way to write this would be:
  75 -        *
  76 -        * to_be_doubled = tn->full_children;
  77 -        * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
  78 -        *     tn->full_children;
  79 -        *
  80 -        * new_child_length = tnode_child_length(tn) * 2;
  81 -        *
  82 -        * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
  83 -        *      new_child_length;
  84 -        * if (new_fill_factor >= inflate_threshold)
  85 -        *
  86 -        * ...and so on, tho it would mess up the while () loop.
  87 -        *
  88 -        * anyway,
  89 -        * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
  90 -        *      inflate_threshold
  91 -        *
  92 -        * avoid a division:
  93 -        * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
  94 -        *      inflate_threshold * new_child_length
  95 -        *
  96 -        * expand not_to_be_doubled and to_be_doubled, and shorten:
  97 -        * 100 * (tnode_child_length(tn) - tn->empty_children +
  98 -        *    tn->full_children) >= inflate_threshold * new_child_length
  99 -        *
 100 -        * expand new_child_length:
 101 -        * 100 * (tnode_child_length(tn) - tn->empty_children +
 102 -        *    tn->full_children) >=
 103 -        *      inflate_threshold * tnode_child_length(tn) * 2
 104 -        *
 105 -        * shorten again:
 106 -        * 50 * (tn->full_children + tnode_child_length(tn) -
 107 -        *    tn->empty_children) >= inflate_threshold *
 108 -        *    tnode_child_length(tn)
 109 -        *
 110 -        */
 111 -
 112 -       /* Keep root node larger  */
 113 -
 114 -       if (!node_parent(tn)) {
 115 -               inflate_threshold_use = inflate_threshold_root;
 116 -               halve_threshold_use = halve_threshold_root;
 117 -       } else {
 118 -               inflate_threshold_use = inflate_threshold;
 119 -               halve_threshold_use = halve_threshold;
 120 -       }
 121 -
 122 -       max_work = MAX_WORK;
 123 -       while ((tn->full_children > 0 &&  max_work-- &&
 124 -               50 * (tn->full_children + tnode_child_length(tn)
 125 -                     - tn->empty_children)
 126 -               >= inflate_threshold_use * tnode_child_length(tn))) {
 127 -
 128 -               old_tn = tn;
 129 -               tn = inflate(t, tn);
 130 -
 131 -               if (IS_ERR(tn)) {
 132 -                       tn = old_tn;
 133 -#ifdef CONFIG_IP_FIB_TRIE_STATS
 134 -                       this_cpu_inc(t->stats->resize_node_skipped);
 135 -#endif
 136 -                       break;
 137 -               }
 138 -       }
 139 -
 140 -       /* Return if at least one inflate is run */
 141 -       if (max_work != MAX_WORK)
 142 -               return tn;
 143 -
 144 -       /*
 145 -        * Halve as long as the number of empty children in this
 146 -        * node is above threshold.
 147 -        */
 148 -
 149 -       max_work = MAX_WORK;
 150 -       while (tn->bits > 1 &&  max_work-- &&
 151 -              100 * (tnode_child_length(tn) - tn->empty_children) <
 152 -              halve_threshold_use * tnode_child_length(tn)) {
 153 -
 154 -               old_tn = tn;
 155 -               tn = halve(t, tn);
 156 -               if (IS_ERR(tn)) {
 157 -                       tn = old_tn;
 158 -#ifdef CONFIG_IP_FIB_TRIE_STATS
 159 -                       this_cpu_inc(t->stats->resize_node_skipped);
 160 -#endif
 161 -                       break;
 162 -               }
 163 -       }
 164 -
 165 -
 166 -       /* Only one child remains */
 167 -       if (tn->empty_children == (tnode_child_length(tn) - 1)) {
 168 -               unsigned long i;
 169 -one_child:
 170 -               for (i = tnode_child_length(tn); !n && i;)
 171 -                       n = tnode_get_child(tn, --i);
 172 -no_children:
 173 -               /* compress one level */
 174 -               node_set_parent(n, NULL);
 175 -               tnode_free_safe(tn);
 176 -               return n;
 177 -       }
 178 -       return tn;
 179 -}
 180 -
 181 -
 182  static void tnode_clean_free(struct tnode *tn)
 183  {
 184         struct tnode *tofree;
 185 @@ -804,6 +647,160 @@ nomem:
 186         return ERR_PTR(-ENOMEM);
 187  }
 188
 189 +#define MAX_WORK 10
 190 +static struct tnode *resize(struct trie *t, struct tnode *tn)
 191 +{
 192 +       struct tnode *old_tn, *n = NULL;
 193 +       int inflate_threshold_use;
 194 +       int halve_threshold_use;
 195 +       int max_work;
 196 +
 197 +       if (!tn)
 198 +               return NULL;
 199 +
 200 +       pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
 201 +                tn, inflate_threshold, halve_threshold);
 202 +
 203 +       /* No children */
 204 +       if (tn->empty_children > (tnode_child_length(tn) - 1))
 205 +               goto no_children;
 206 +
 207 +       /* One child */
 208 +       if (tn->empty_children == (tnode_child_length(tn) - 1))
 209 +               goto one_child;
 210 +       /*
 211 +        * Double as long as the resulting node has a number of
 212 +        * nonempty nodes that are above the threshold.
 213 +        */
 214 +
 215 +       /*
 216 +        * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
 217 +        * the Helsinki University of Technology and Matti Tikkanen of Nokia
 218 +        * Telecommunications, page 6:
 219 +        * "A node is doubled if the ratio of non-empty children to all
 220 +        * children in the *doubled* node is at least 'high'."
 221 +        *
 222 +        * 'high' in this instance is the variable 'inflate_threshold'. It
 223 +        * is expressed as a percentage, so we multiply it with
 224 +        * tnode_child_length() and instead of multiplying by 2 (since the
 225 +        * child array will be doubled by inflate()) and multiplying
 226 +        * the left-hand side by 100 (to handle the percentage thing) we
 227 +        * multiply the left-hand side by 50.
 228 +        *
 229 +        * The left-hand side may look a bit weird: tnode_child_length(tn)
 230 +        * - tn->empty_children is of course the number of non-null children
 231 +        * in the current node. tn->full_children is the number of "full"
 232 +        * children, that is non-null tnodes with a skip value of 0.
 233 +        * All of those will be doubled in the resulting inflated tnode, so
 234 +        * we just count them one extra time here.
 235 +        *
 236 +        * A clearer way to write this would be:
 237 +        *
 238 +        * to_be_doubled = tn->full_children;
 239 +        * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
 240 +        *     tn->full_children;
 241 +        *
 242 +        * new_child_length = tnode_child_length(tn) * 2;
 243 +        *
 244 +        * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
 245 +        *      new_child_length;
 246 +        * if (new_fill_factor >= inflate_threshold)
 247 +        *
 248 +        * ...and so on, tho it would mess up the while () loop.
 249 +        *
 250 +        * anyway,
 251 +        * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
 252 +        *      inflate_threshold
 253 +        *
 254 +        * avoid a division:
 255 +        * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
 256 +        *      inflate_threshold * new_child_length
 257 +        *
 258 +        * expand not_to_be_doubled and to_be_doubled, and shorten:
 259 +        * 100 * (tnode_child_length(tn) - tn->empty_children +
 260 +        *    tn->full_children) >= inflate_threshold * new_child_length
 261 +        *
 262 +        * expand new_child_length:
 263 +        * 100 * (tnode_child_length(tn) - tn->empty_children +
 264 +        *    tn->full_children) >=
 265 +        *      inflate_threshold * tnode_child_length(tn) * 2
 266 +        *
 267 +        * shorten again:
 268 +        * 50 * (tn->full_children + tnode_child_length(tn) -
 269 +        *    tn->empty_children) >= inflate_threshold *
 270 +        *    tnode_child_length(tn)
 271 +        *
 272 +        */
 273 +
 274 +       /* Keep root node larger  */
 275 +
 276 +       if (!node_parent(tn)) {
 277 +               inflate_threshold_use = inflate_threshold_root;
 278 +               halve_threshold_use = halve_threshold_root;
 279 +       } else {
 280 +               inflate_threshold_use = inflate_threshold;
 281 +               halve_threshold_use = halve_threshold;
 282 +       }
 283 +
 284 +       max_work = MAX_WORK;
 285 +       while ((tn->full_children > 0 &&  max_work-- &&
 286 +               50 * (tn->full_children + tnode_child_length(tn)
 287 +                     - tn->empty_children)
 288 +               >= inflate_threshold_use * tnode_child_length(tn))) {
 289 +
 290 +               old_tn = tn;
 291 +               tn = inflate(t, tn);
 292 +
 293 +               if (IS_ERR(tn)) {
 294 +                       tn = old_tn;
 295 +#ifdef CONFIG_IP_FIB_TRIE_STATS
 296 +                       this_cpu_inc(t->stats->resize_node_skipped);
 297 +#endif
 298 +                       break;
 299 +               }
 300 +       }
 301 +
 302 +       /* Return if at least one inflate is run */
 303 +       if (max_work != MAX_WORK)
 304 +               return tn;
 305 +
 306 +       /*
 307 +        * Halve as long as the number of empty children in this
 308 +        * node is above threshold.
 309 +        */
 310 +
 311 +       max_work = MAX_WORK;
 312 +       while (tn->bits > 1 &&  max_work-- &&
 313 +              100 * (tnode_child_length(tn) - tn->empty_children) <
 314 +              halve_threshold_use * tnode_child_length(tn)) {
 315 +
 316 +               old_tn = tn;
 317 +               tn = halve(t, tn);
 318 +               if (IS_ERR(tn)) {
 319 +                       tn = old_tn;
 320 +#ifdef CONFIG_IP_FIB_TRIE_STATS
 321 +                       this_cpu_inc(t->stats->resize_node_skipped);
 322 +#endif
 323 +                       break;
 324 +               }
 325 +       }
 326 +
 327 +
 328 +       /* Only one child remains */
 329 +       if (tn->empty_children == (tnode_child_length(tn) - 1)) {
 330 +               unsigned long i;
 331 +one_child:
 332 +               for (i = tnode_child_length(tn); !n && i;)
 333 +                       n = tnode_get_child(tn, --i);
 334 +no_children:
 335 +               /* compress one level */
 336 +               node_set_parent(n, NULL);
 337 +               tnode_free_safe(tn);
 338 +               return n;
 339 +       }
 340 +       return tn;
 341 +}
 342 +
 343  /* readside must use rcu_read_lock currently dump routines
 344   via get_fa_head and dump */
 345