target/linux/generic/patches-3.18/080-07-fib_trie-Optimize-fib_find_node.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:56:00 -0800
   3 Subject: [PATCH] fib_trie: Optimize fib_find_node
   4
   5 This patch makes use of the same features I made use of for
   6 fib_table_lookup to streamline fib_find_node.  The resultant code should be
   7 smaller and run faster than the original.
   8
   9 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  10 Signed-off-by: David S. Miller <davem@davemloft.net>
  11 ---
  12
  13 --- a/net/ipv4/fib_trie.c
  14 +++ b/net/ipv4/fib_trie.c
  15 @@ -892,28 +892,34 @@ static void insert_leaf_info(struct hlis
  16  }
  17
  18  /* rcu_read_lock needs to be hold by caller from readside */
  19 -
  20  static struct tnode *fib_find_node(struct trie *t, u32 key)
  21  {
  22         struct tnode *n = rcu_dereference_rtnl(t->trie);
  23 -       int pos = 0;
  24
  25 -       while (n && IS_TNODE(n)) {
  26 -               if (tkey_sub_equals(n->key, pos, n->pos-pos, key)) {
  27 -                       pos = n->pos + n->bits;
  28 -                       n = tnode_get_child_rcu(n,
  29 -                                               tkey_extract_bits(key,
  30 -                                                                 n->pos,
  31 -                                                                 n->bits));
  32 -               } else
  33 +       while (n) {
  34 +               unsigned long index = get_index(key, n);
  35 +
  36 +               /* This bit of code is a bit tricky but it combines multiple
  37 +                * checks into a single check.  The prefix consists of the
  38 +                * prefix plus zeros for the bits in the cindex. The index
  39 +                * is the difference between the key and this value.  From
  40 +                * this we can actually derive several pieces of data.
  41 +                *   if !(index >> bits)
  42 +                *     we know the value is cindex
  43 +                *   else
  44 +                *     we have a mismatch in skip bits and failed
  45 +                */
  46 +               if (index >> n->bits)
  47 +                       return NULL;
  48 +
  49 +               /* we have found a leaf. Prefixes have already been compared */
  50 +               if (IS_LEAF(n))
  51                         break;
  52 -       }
  53 -       /* Case we have found a leaf. Compare prefixes */
  54
  55 -       if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
  56 -               return n;
  57 +               n = rcu_dereference_rtnl(n->child[index]);
  58 +       }
  59
  60 -       return NULL;
  61 +       return n;
  62  }
  63
  64  static void trie_rebalance(struct trie *t, struct tnode *tn)