target/linux/generic/patches-3.18/080-06-fib_trie-Optimize-fib_table_lookup-to-avoid-wasting-.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:55:54 -0800
   3 Subject: [PATCH] fib_trie: Optimize fib_table_lookup to avoid wasting
   4  time on loops/variables
   5
   6 This patch is meant to reduce the complexity of fib_table_lookup by reducing
   7 the number of variables to the bare minimum while still keeping the same if
   8 not improved functionality versus the original.
   9
  10 Most of this change was started off by the desire to rid the function of
  11 chopped_off and current_prefix_length as they actually added very little to
  12 the function since they only applied when computing the cindex.  I was able
  13 to replace them mostly with just a check for the prefix match.  As long as
  14 the prefix between the key and the node being tested was the same we know
  15 we can search the tnode fully versus just testing cindex 0.
  16
  17 The second portion of the change ended up being a massive reordering.
  18 Originally the calls to check_leaf were up near the start of the loop, and
  19 the backtracing and descending into lower levels of tnodes was later.  This
  20 didn't make much sense as the structure of the tree means the leaves are
  21 always the last thing to be tested.  As such I reordered things so that we
  22 instead have a loop that will delve into the tree and only exit when we
  23 have either found a leaf or we have exhausted the tree.  The advantage of
  24 rearranging things like this is that we can fully inline check_leaf since
  25 there is now only one reference to it in the function.
  26
  27 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  28 Signed-off-by: David S. Miller <davem@davemloft.net>
  29 ---
  30
  31 --- a/net/ipv4/fib_trie.c
  32 +++ b/net/ipv4/fib_trie.c
  33 @@ -90,6 +90,9 @@ typedef unsigned int t_key;
  34  #define IS_TNODE(n) ((n)->bits)
  35  #define IS_LEAF(n) (!(n)->bits)
  36
  37 +#define get_shift(_kv) (KEYLENGTH - (_kv)->pos - (_kv)->bits)
  38 +#define get_index(_key, _kv) (((_key) ^ (_kv)->key) >> get_shift(_kv))
  39 +
  40  struct tnode {
  41         t_key key;
  42         unsigned char bits;             /* 2log(KEYLENGTH) bits needed */
  43 @@ -1281,7 +1284,7 @@ static int check_leaf(struct fib_table *
  44                                 continue;
  45                         fib_alias_accessed(fa);
  46                         err = fib_props[fa->fa_type].error;
  47 -                       if (err) {
  48 +                       if (unlikely(err < 0)) {
  49  #ifdef CONFIG_IP_FIB_TRIE_STATS
  50                                 this_cpu_inc(t->stats->semantic_match_passed);
  51  #endif
  52 @@ -1303,7 +1306,7 @@ static int check_leaf(struct fib_table *
  53                                 res->prefixlen = li->plen;
  54                                 res->nh_sel = nhsel;
  55                                 res->type = fa->fa_type;
  56 -                               res->scope = fa->fa_info->fib_scope;
  57 +                               res->scope = fi->fib_scope;
  58                                 res->fi = fi;
  59                                 res->table = tb;
  60                                 res->fa_head = &li->falh;
  61 @@ -1321,23 +1324,24 @@ static int check_leaf(struct fib_table *
  62         return 1;
  63  }
  64
  65 +static inline t_key prefix_mismatch(t_key key, struct tnode *n)
  66 +{
  67 +       t_key prefix = n->key;
  68 +
  69 +       return (key ^ prefix) & (prefix | -prefix);
  70 +}
  71 +
  72  int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
  73                      struct fib_result *res, int fib_flags)
  74  {
  75 -       struct trie *t = (struct trie *) tb->tb_data;
  76 +       struct trie *t = (struct trie *)tb->tb_data;
  77  #ifdef CONFIG_IP_FIB_TRIE_STATS
  78         struct trie_use_stats __percpu *stats = t->stats;
  79  #endif
  80 -       int ret;
  81 -       struct tnode *n;
  82 -       struct tnode *pn;
  83 -       unsigned int pos, bits;
  84 -       t_key key = ntohl(flp->daddr);
  85 -       unsigned int chopped_off;
  86 -       t_key cindex = 0;
  87 -       unsigned int current_prefix_length = KEYLENGTH;
  88 -       struct tnode *cn;
  89 -       t_key pref_mismatch;
  90 +       const t_key key = ntohl(flp->daddr);
  91 +       struct tnode *n, *pn;
  92 +       t_key cindex;
  93 +       int ret = 1;
  94
  95         rcu_read_lock();
  96
  97 @@ -1349,170 +1353,102 @@ int fib_table_lookup(struct fib_table *t
  98         this_cpu_inc(stats->gets);
  99  #endif
 100
 101 -       /* Just a leaf? */
 102 -       if (IS_LEAF(n)) {
 103 -               ret = check_leaf(tb, t, n, key, flp, res, fib_flags);
 104 -               goto found;
 105 -       }
 106 -
 107         pn = n;
 108 -       chopped_off = 0;
 109 -
 110 -       while (pn) {
 111 -               pos = pn->pos;
 112 -               bits = pn->bits;
 113 +       cindex = 0;
 114
 115 -               if (!chopped_off)
 116 -                       cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
 117 -                                                  pos, bits);
 118 -
 119 -               n = tnode_get_child_rcu(pn, cindex);
 120 -
 121 -               if (n == NULL) {
 122 -#ifdef CONFIG_IP_FIB_TRIE_STATS
 123 -                       this_cpu_inc(stats->null_node_hit);
 124 -#endif
 125 -                       goto backtrace;
 126 -               }
 127 +       /* Step 1: Travel to the longest prefix match in the trie */
 128 +       for (;;) {
 129 +               unsigned long index = get_index(key, n);
 130 +
 131 +               /* This bit of code is a bit tricky but it combines multiple
 132 +                * checks into a single check.  The prefix consists of the
 133 +                * prefix plus zeros for the "bits" in the prefix. The index
 134 +                * is the difference between the key and this value.  From
 135 +                * this we can actually derive several pieces of data.
 136 +                *   if !(index >> bits)
 137 +                *     we know the value is child index
 138 +                *   else
 139 +                *     we have a mismatch in skip bits and failed
 140 +                */
 141 +               if (index >> n->bits)
 142 +                       break;
 143
 144 -               if (IS_LEAF(n)) {
 145 -                       ret = check_leaf(tb, t, n, key, flp, res, fib_flags);
 146 -                       if (ret > 0)
 147 -                               goto backtrace;
 148 +               /* we have found a leaf. Prefixes have already been compared */
 149 +               if (IS_LEAF(n))
 150                         goto found;
 151 -               }
 152 -
 153 -               cn = n;
 154
 155 -               /*
 156 -                * It's a tnode, and we can do some extra checks here if we
 157 -                * like, to avoid descending into a dead-end branch.
 158 -                * This tnode is in the parent's child array at index
 159 -                * key[p_pos..p_pos+p_bits] but potentially with some bits
 160 -                * chopped off, so in reality the index may be just a
 161 -                * subprefix, padded with zero at the end.
 162 -                * We can also take a look at any skipped bits in this
 163 -                * tnode - everything up to p_pos is supposed to be ok,
 164 -                * and the non-chopped bits of the index (se previous
 165 -                * paragraph) are also guaranteed ok, but the rest is
 166 -                * considered unknown.
 167 -                *
 168 -                * The skipped bits are key[pos+bits..cn->pos].
 169 -                */
 170 -
 171 -               /* If current_prefix_length < pos+bits, we are already doing
 172 -                * actual prefix  matching, which means everything from
 173 -                * pos+(bits-chopped_off) onward must be zero along some
 174 -                * branch of this subtree - otherwise there is *no* valid
 175 -                * prefix present. Here we can only check the skipped
 176 -                * bits. Remember, since we have already indexed into the
 177 -                * parent's child array, we know that the bits we chopped of
 178 -                * *are* zero.
 179 +               /* only record pn and cindex if we are going to be chopping
 180 +                * bits later.  Otherwise we are just wasting cycles.
 181                  */
 182 -
 183 -               /* NOTA BENE: Checking only skipped bits
 184 -                  for the new node here */
 185 -
 186 -               if (current_prefix_length < pos+bits) {
 187 -                       if (tkey_extract_bits(cn->key, current_prefix_length,
 188 -                                               cn->pos - current_prefix_length)
 189 -                           || !(cn->child[0]))
 190 -                               goto backtrace;
 191 +               if (index) {
 192 +                       pn = n;
 193 +                       cindex = index;
 194                 }
 195
 196 -               /*
 197 -                * If chopped_off=0, the index is fully validated and we
 198 -                * only need to look at the skipped bits for this, the new,
 199 -                * tnode. What we actually want to do is to find out if
 200 -                * these skipped bits match our key perfectly, or if we will
 201 -                * have to count on finding a matching prefix further down,
 202 -                * because if we do, we would like to have some way of
 203 -                * verifying the existence of such a prefix at this point.
 204 -                */
 205 -
 206 -               /* The only thing we can do at this point is to verify that
 207 -                * any such matching prefix can indeed be a prefix to our
 208 -                * key, and if the bits in the node we are inspecting that
 209 -                * do not match our key are not ZERO, this cannot be true.
 210 -                * Thus, find out where there is a mismatch (before cn->pos)
 211 -                * and verify that all the mismatching bits are zero in the
 212 -                * new tnode's key.
 213 -                */
 214 +               n = rcu_dereference(n->child[index]);
 215 +               if (unlikely(!n))
 216 +                       goto backtrace;
 217 +       }
 218
 219 -               /*
 220 -                * Note: We aren't very concerned about the piece of
 221 -                * the key that precede pn->pos+pn->bits, since these
 222 -                * have already been checked. The bits after cn->pos
 223 -                * aren't checked since these are by definition
 224 -                * "unknown" at this point. Thus, what we want to see
 225 -                * is if we are about to enter the "prefix matching"
 226 -                * state, and in that case verify that the skipped
 227 -                * bits that will prevail throughout this subtree are
 228 -                * zero, as they have to be if we are to find a
 229 -                * matching prefix.
 230 +       /* Step 2: Sort out leaves and begin backtracing for longest prefix */
 231 +       for (;;) {
 232 +               /* record the pointer where our next node pointer is stored */
 233 +               struct tnode __rcu **cptr = n->child;
 234 +
 235 +               /* This test verifies that none of the bits that differ
 236 +                * between the key and the prefix exist in the region of
 237 +                * the lsb and higher in the prefix.
 238                  */
 239 +               if (unlikely(prefix_mismatch(key, n)))
 240 +                       goto backtrace;
 241
 242 -               pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
 243 +               /* exit out and process leaf */
 244 +               if (unlikely(IS_LEAF(n)))
 245 +                       break;
 246
 247 -               /*
 248 -                * In short: If skipped bits in this node do not match
 249 -                * the search key, enter the "prefix matching"
 250 -                * state.directly.
 251 +               /* Don't bother recording parent info.  Since we are in
 252 +                * prefix match mode we will have to come back to wherever
 253 +                * we started this traversal anyway
 254                  */
 255 -               if (pref_mismatch) {
 256 -                       /* fls(x) = __fls(x) + 1 */
 257 -                       int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
 258 -
 259 -                       if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
 260 -                               goto backtrace;
 261 -
 262 -                       if (current_prefix_length >= cn->pos)
 263 -                               current_prefix_length = mp;
 264 -               }
 265 -
 266 -               pn = n; /* Descend */
 267 -               chopped_off = 0;
 268 -               continue;
 269
 270 +               while ((n = rcu_dereference(*cptr)) == NULL) {
 271  backtrace:
 272 -               chopped_off++;
 273 -
 274 -               /* As zero don't change the child key (cindex) */
 275 -               while ((chopped_off <= pn->bits)
 276 -                      && !(cindex & (1<<(chopped_off-1))))
 277 -                       chopped_off++;
 278 -
 279 -               /* Decrease current_... with bits chopped off */
 280 -               if (current_prefix_length > pn->pos + pn->bits - chopped_off)
 281 -                       current_prefix_length = pn->pos + pn->bits
 282 -                               - chopped_off;
 283 -
 284 -               /*
 285 -                * Either we do the actual chop off according or if we have
 286 -                * chopped off all bits in this tnode walk up to our parent.
 287 -                */
 288 -
 289 -               if (chopped_off <= pn->bits) {
 290 -                       cindex &= ~(1 << (chopped_off-1));
 291 -               } else {
 292 -                       struct tnode *parent = node_parent_rcu(pn);
 293 -                       if (!parent)
 294 -                               goto failed;
 295 -
 296 -                       /* Get Child's index */
 297 -                       cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
 298 -                       pn = parent;
 299 -                       chopped_off = 0;
 300 -
 301  #ifdef CONFIG_IP_FIB_TRIE_STATS
 302 -                       this_cpu_inc(stats->backtrack);
 303 +                       if (!n)
 304 +                               this_cpu_inc(stats->null_node_hit);
 305  #endif
 306 -                       goto backtrace;
 307 +                       /* If we are at cindex 0 there are no more bits for
 308 +                        * us to strip at this level so we must ascend back
 309 +                        * up one level to see if there are any more bits to
 310 +                        * be stripped there.
 311 +                        */
 312 +                       while (!cindex) {
 313 +                               t_key pkey = pn->key;
 314 +
 315 +                               pn = node_parent_rcu(pn);
 316 +                               if (unlikely(!pn))
 317 +                                       goto failed;
 318 +#ifdef CONFIG_IP_FIB_TRIE_STATS
 319 +                               this_cpu_inc(stats->backtrack);
 320 +#endif
 321 +                               /* Get Child's index */
 322 +                               cindex = get_index(pkey, pn);
 323 +                       }
 324 +
 325 +                       /* strip the least significant bit from the cindex */
 326 +                       cindex &= cindex - 1;
 327 +
 328 +                       /* grab pointer for next child node */
 329 +                       cptr = &pn->child[cindex];
 330                 }
 331         }
 332 -failed:
 333 -       ret = 1;
 334 +
 335  found:
 336 +       /* Step 3: Process the leaf, if that fails fall back to backtracing */
 337 +       ret = check_leaf(tb, t, n, key, flp, res, fib_flags);
 338 +       if (unlikely(ret > 0))
 339 +               goto backtrace;
 340 +failed:
 341         rcu_read_unlock();
 342         return ret;
 343  }