target/linux/generic/patches-3.18/080-13-fib_trie-Add-functions-should_inflate-and-should_hal.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:56:37 -0800
   3 Subject: [PATCH] fib_trie: Add functions should_inflate and should_halve
   4
   5 This change pulls the logic for if we should inflate/halve the nodes out
   6 into separate functions.  It also addresses what I believe is a bug where 1
   7 full node is all that is needed to keep a node from ever being halved.
   8
   9 Simple script to reproduce the issue:
  10         modprobe dummy; ifconfig dummy0 up
  11         for i in `seq 0 255`; do ifconfig dummy0:$i 10.0.${i}.1/24 up; done
  12         ifconfig dummy0:256 10.0.255.33/16 up
  13         for i in `seq 0 254`; do ifconfig dummy0:$i down; done
  14
  15 Results from /proc/net/fib_triestat
  16 Before:
  17         Local:
  18                 Aver depth:     3.00
  19                 Max depth:      4
  20                 Leaves:         17
  21                 Prefixes:       18
  22                 Internal nodes: 11
  23                   1: 8  2: 2  10: 1
  24                 Pointers: 1048
  25         Null ptrs: 1021
  26         Total size: 11  kB
  27 After:
  28         Local:
  29                 Aver depth:     3.41
  30                 Max depth:      5
  31                 Leaves:         17
  32                 Prefixes:       18
  33                 Internal nodes: 12
  34                   1: 8  2: 3  3: 1
  35                 Pointers: 36
  36         Null ptrs: 8
  37         Total size: 3  kB
  38
  39 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  40 Signed-off-by: David S. Miller <davem@davemloft.net>
  41 ---
  42
  43 --- a/net/ipv4/fib_trie.c
  44 +++ b/net/ipv4/fib_trie.c
  45 @@ -647,12 +647,94 @@ nomem:
  46         return ERR_PTR(-ENOMEM);
  47  }
  48
  49 +/* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
  50 + * the Helsinki University of Technology and Matti Tikkanen of Nokia
  51 + * Telecommunications, page 6:
  52 + * "A node is doubled if the ratio of non-empty children to all
  53 + * children in the *doubled* node is at least 'high'."
  54 + *
  55 + * 'high' in this instance is the variable 'inflate_threshold'. It
  56 + * is expressed as a percentage, so we multiply it with
  57 + * tnode_child_length() and instead of multiplying by 2 (since the
  58 + * child array will be doubled by inflate()) and multiplying
  59 + * the left-hand side by 100 (to handle the percentage thing) we
  60 + * multiply the left-hand side by 50.
  61 + *
  62 + * The left-hand side may look a bit weird: tnode_child_length(tn)
  63 + * - tn->empty_children is of course the number of non-null children
  64 + * in the current node. tn->full_children is the number of "full"
  65 + * children, that is non-null tnodes with a skip value of 0.
  66 + * All of those will be doubled in the resulting inflated tnode, so
  67 + * we just count them one extra time here.
  68 + *
  69 + * A clearer way to write this would be:
  70 + *
  71 + * to_be_doubled = tn->full_children;
  72 + * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
  73 + *     tn->full_children;
  74 + *
  75 + * new_child_length = tnode_child_length(tn) * 2;
  76 + *
  77 + * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
  78 + *      new_child_length;
  79 + * if (new_fill_factor >= inflate_threshold)
  80 + *
  81 + * ...and so on, tho it would mess up the while () loop.
  82 + *
  83 + * anyway,
  84 + * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
  85 + *      inflate_threshold
  86 + *
  87 + * avoid a division:
  88 + * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
  89 + *      inflate_threshold * new_child_length
  90 + *
  91 + * expand not_to_be_doubled and to_be_doubled, and shorten:
  92 + * 100 * (tnode_child_length(tn) - tn->empty_children +
  93 + *    tn->full_children) >= inflate_threshold * new_child_length
  94 + *
  95 + * expand new_child_length:
  96 + * 100 * (tnode_child_length(tn) - tn->empty_children +
  97 + *    tn->full_children) >=
  98 + *      inflate_threshold * tnode_child_length(tn) * 2
  99 + *
 100 + * shorten again:
 101 + * 50 * (tn->full_children + tnode_child_length(tn) -
 102 + *    tn->empty_children) >= inflate_threshold *
 103 + *    tnode_child_length(tn)
 104 + *
 105 + */
 106 +static bool should_inflate(const struct tnode *tn)
 107 +{
 108 +       unsigned long used = tnode_child_length(tn);
 109 +       unsigned long threshold = used;
 110 +
 111 +       /* Keep root node larger */
 112 +       threshold *= node_parent(tn) ? inflate_threshold :
 113 +                                      inflate_threshold_root;
 114 +       used += tn->full_children;
 115 +       used -= tn->empty_children;
 116 +
 117 +       return tn->pos && ((50 * used) >= threshold);
 118 +}
 119 +
 120 +static bool should_halve(const struct tnode *tn)
 121 +{
 122 +       unsigned long used = tnode_child_length(tn);
 123 +       unsigned long threshold = used;
 124 +
 125 +       /* Keep root node larger */
 126 +       threshold *= node_parent(tn) ? halve_threshold :
 127 +                                      halve_threshold_root;
 128 +       used -= tn->empty_children;
 129 +
 130 +       return (tn->bits > 1) && ((100 * used) < threshold);
 131 +}
 132 +
 133  #define MAX_WORK 10
 134  static struct tnode *resize(struct trie *t, struct tnode *tn)
 135  {
 136         struct tnode *old_tn, *n = NULL;
 137 -       int inflate_threshold_use;
 138 -       int halve_threshold_use;
 139         int max_work;
 140
 141         if (!tn)
 142 @@ -668,86 +750,12 @@ static struct tnode *resize(struct trie
 143         /* One child */
 144         if (tn->empty_children == (tnode_child_length(tn) - 1))
 145                 goto one_child;
 146 -       /*
 147 -        * Double as long as the resulting node has a number of
 148 -        * nonempty nodes that are above the threshold.
 149 -        */
 150
 151 -       /*
 152 -        * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
 153 -        * the Helsinki University of Technology and Matti Tikkanen of Nokia
 154 -        * Telecommunications, page 6:
 155 -        * "A node is doubled if the ratio of non-empty children to all
 156 -        * children in the *doubled* node is at least 'high'."
 157 -        *
 158 -        * 'high' in this instance is the variable 'inflate_threshold'. It
 159 -        * is expressed as a percentage, so we multiply it with
 160 -        * tnode_child_length() and instead of multiplying by 2 (since the
 161 -        * child array will be doubled by inflate()) and multiplying
 162 -        * the left-hand side by 100 (to handle the percentage thing) we
 163 -        * multiply the left-hand side by 50.
 164 -        *
 165 -        * The left-hand side may look a bit weird: tnode_child_length(tn)
 166 -        * - tn->empty_children is of course the number of non-null children
 167 -        * in the current node. tn->full_children is the number of "full"
 168 -        * children, that is non-null tnodes with a skip value of 0.
 169 -        * All of those will be doubled in the resulting inflated tnode, so
 170 -        * we just count them one extra time here.
 171 -        *
 172 -        * A clearer way to write this would be:
 173 -        *
 174 -        * to_be_doubled = tn->full_children;
 175 -        * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
 176 -        *     tn->full_children;
 177 -        *
 178 -        * new_child_length = tnode_child_length(tn) * 2;
 179 -        *
 180 -        * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
 181 -        *      new_child_length;
 182 -        * if (new_fill_factor >= inflate_threshold)
 183 -        *
 184 -        * ...and so on, tho it would mess up the while () loop.
 185 -        *
 186 -        * anyway,
 187 -        * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
 188 -        *      inflate_threshold
 189 -        *
 190 -        * avoid a division:
 191 -        * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
 192 -        *      inflate_threshold * new_child_length
 193 -        *
 194 -        * expand not_to_be_doubled and to_be_doubled, and shorten:
 195 -        * 100 * (tnode_child_length(tn) - tn->empty_children +
 196 -        *    tn->full_children) >= inflate_threshold * new_child_length
 197 -        *
 198 -        * expand new_child_length:
 199 -        * 100 * (tnode_child_length(tn) - tn->empty_children +
 200 -        *    tn->full_children) >=
 201 -        *      inflate_threshold * tnode_child_length(tn) * 2
 202 -        *
 203 -        * shorten again:
 204 -        * 50 * (tn->full_children + tnode_child_length(tn) -
 205 -        *    tn->empty_children) >= inflate_threshold *
 206 -        *    tnode_child_length(tn)
 207 -        *
 208 +       /* Double as long as the resulting node has a number of
 209 +        * nonempty nodes that are above the threshold.
 210          */
 211 -
 212 -       /* Keep root node larger  */
 213 -
 214 -       if (!node_parent(tn)) {
 215 -               inflate_threshold_use = inflate_threshold_root;
 216 -               halve_threshold_use = halve_threshold_root;
 217 -       } else {
 218 -               inflate_threshold_use = inflate_threshold;
 219 -               halve_threshold_use = halve_threshold;
 220 -       }
 221 -
 222         max_work = MAX_WORK;
 223 -       while ((tn->full_children > 0 &&  max_work-- &&
 224 -               50 * (tn->full_children + tnode_child_length(tn)
 225 -                     - tn->empty_children)
 226 -               >= inflate_threshold_use * tnode_child_length(tn))) {
 227 -
 228 +       while (should_inflate(tn) && max_work--) {
 229                 old_tn = tn;
 230                 tn = inflate(t, tn);
 231
 232 @@ -764,16 +772,11 @@ static struct tnode *resize(struct trie
 233         if (max_work != MAX_WORK)
 234                 return tn;
 235
 236 -       /*
 237 -        * Halve as long as the number of empty children in this
 238 +       /* Halve as long as the number of empty children in this
 239          * node is above threshold.
 240          */
 241 -
 242         max_work = MAX_WORK;
 243 -       while (tn->bits > 1 &&  max_work-- &&
 244 -              100 * (tnode_child_length(tn) - tn->empty_children) <
 245 -              halve_threshold_use * tnode_child_length(tn)) {
 246 -
 247 +       while (should_halve(tn) && max_work--) {
 248                 old_tn = tn;
 249                 tn = halve(t, tn);
 250                 if (IS_ERR(tn)) {