target/linux/generic/patches-3.18/080-08-fib_trie-Optimize-fib_table_insert.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:56:06 -0800
   3 Subject: [PATCH] fib_trie: Optimize fib_table_insert
   4
   5 This patch updates the fib_table_insert function to take advantage of the
   6 changes made to improve the performance of fib_table_lookup.  As a result
   7 the code should be smaller and run faster then 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 @@ -222,31 +222,6 @@ static inline t_key tkey_extract_bits(t_
  16                 return 0;
  17  }
  18
  19 -static inline int tkey_equals(t_key a, t_key b)
  20 -{
  21 -       return a == b;
  22 -}
  23 -
  24 -static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
  25 -{
  26 -       if (bits == 0 || offset >= KEYLENGTH)
  27 -               return 1;
  28 -       bits = bits > KEYLENGTH ? KEYLENGTH : bits;
  29 -       return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
  30 -}
  31 -
  32 -static inline int tkey_mismatch(t_key a, int offset, t_key b)
  33 -{
  34 -       t_key diff = a ^ b;
  35 -       int i = offset;
  36 -
  37 -       if (!diff)
  38 -               return 0;
  39 -       while ((diff << i) >> (KEYLENGTH-1) == 0)
  40 -               i++;
  41 -       return i;
  42 -}
  43 -
  44  /*
  45    To understand this stuff, an understanding of keys and all their bits is
  46    necessary. Every node in the trie has a key associated with it, but not
  47 @@ -485,6 +460,15 @@ static void tnode_put_child_reorg(struct
  48         rcu_assign_pointer(tn->child[i], n);
  49  }
  50
  51 +static void put_child_root(struct tnode *tp, struct trie *t,
  52 +                          t_key key, struct tnode *n)
  53 +{
  54 +       if (tp)
  55 +               put_child(tp, get_index(key, tp), n);
  56 +       else
  57 +               rcu_assign_pointer(t->trie, n);
  58 +}
  59 +
  60  #define MAX_WORK 10
  61  static struct tnode *resize(struct trie *t, struct tnode *tn)
  62  {
  63 @@ -959,138 +943,100 @@ static void trie_rebalance(struct trie *
  64
  65  static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
  66  {
  67 -       int pos, newpos;
  68 -       struct tnode *tp = NULL, *tn = NULL;
  69 -       struct tnode *n;
  70 -       struct tnode *l;
  71 -       int missbit;
  72         struct list_head *fa_head = NULL;
  73 +       struct tnode *l, *n, *tp = NULL;
  74         struct leaf_info *li;
  75 -       t_key cindex;
  76
  77 -       pos = 0;
  78 +       li = leaf_info_new(plen);
  79 +       if (!li)
  80 +               return NULL;
  81 +       fa_head = &li->falh;
  82 +
  83         n = rtnl_dereference(t->trie);
  84
  85         /* If we point to NULL, stop. Either the tree is empty and we should
  86          * just put a new leaf in if, or we have reached an empty child slot,
  87          * and we should just put our new leaf in that.
  88 -        * If we point to a T_TNODE, check if it matches our key. Note that
  89 -        * a T_TNODE might be skipping any number of bits - its 'pos' need
  90 -        * not be the parent's 'pos'+'bits'!
  91 -        *
  92 -        * If it does match the current key, get pos/bits from it, extract
  93 -        * the index from our key, push the T_TNODE and walk the tree.
  94 -        *
  95 -        * If it doesn't, we have to replace it with a new T_TNODE.
  96          *
  97 -        * If we point to a T_LEAF, it might or might not have the same key
  98 -        * as we do. If it does, just change the value, update the T_LEAF's
  99 -        * value, and return it.
 100 -        * If it doesn't, we need to replace it with a T_TNODE.
 101 +        * If we hit a node with a key that does't match then we should stop
 102 +        * and create a new tnode to replace that node and insert ourselves
 103 +        * and the other node into the new tnode.
 104          */
 105 +       while (n) {
 106 +               unsigned long index = get_index(key, n);
 107
 108 -       while (n && IS_TNODE(n)) {
 109 -               if (tkey_sub_equals(n->key, pos, n->pos-pos, key)) {
 110 -                       tp = n;
 111 -                       pos = n->pos + n->bits;
 112 -                       n = tnode_get_child(n,
 113 -                                           tkey_extract_bits(key,
 114 -                                                             n->pos,
 115 -                                                             n->bits));
 116 -
 117 -                       BUG_ON(n && node_parent(n) != tp);
 118 -               } else
 119 +               /* This bit of code is a bit tricky but it combines multiple
 120 +                * checks into a single check.  The prefix consists of the
 121 +                * prefix plus zeros for the "bits" in the prefix. The index
 122 +                * is the difference between the key and this value.  From
 123 +                * this we can actually derive several pieces of data.
 124 +                *   if !(index >> bits)
 125 +                *     we know the value is child index
 126 +                *   else
 127 +                *     we have a mismatch in skip bits and failed
 128 +                */
 129 +               if (index >> n->bits)
 130                         break;
 131 -       }
 132 -
 133 -       /*
 134 -        * n  ----> NULL, LEAF or TNODE
 135 -        *
 136 -        * tp is n's (parent) ----> NULL or TNODE
 137 -        */
 138
 139 -       BUG_ON(tp && IS_LEAF(tp));
 140 -
 141 -       /* Case 1: n is a leaf. Compare prefixes */
 142 -
 143 -       if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
 144 -               li = leaf_info_new(plen);
 145 -
 146 -               if (!li)
 147 -                       return NULL;
 148 +               /* we have found a leaf. Prefixes have already been compared */
 149 +               if (IS_LEAF(n)) {
 150 +                       /* Case 1: n is a leaf, and prefixes match*/
 151 +                       insert_leaf_info(&n->list, li);
 152 +                       return fa_head;
 153 +               }
 154
 155 -               fa_head = &li->falh;
 156 -               insert_leaf_info(&n->list, li);
 157 -               goto done;
 158 +               tp = n;
 159 +               n = rcu_dereference_rtnl(n->child[index]);
 160         }
 161 -       l = leaf_new(key);
 162 -
 163 -       if (!l)
 164 -               return NULL;
 165
 166 -       li = leaf_info_new(plen);
 167 -
 168 -       if (!li) {
 169 -               node_free(l);
 170 +       l = leaf_new(key);
 171 +       if (!l) {
 172 +               free_leaf_info(li);
 173                 return NULL;
 174         }
 175
 176 -       fa_head = &li->falh;
 177         insert_leaf_info(&l->list, li);
 178
 179 -       if (t->trie && n == NULL) {
 180 -               /* Case 2: n is NULL, and will just insert a new leaf */
 181 -
 182 -               node_set_parent(l, tp);
 183 -
 184 -               cindex = tkey_extract_bits(key, tp->pos, tp->bits);
 185 -               put_child(tp, cindex, l);
 186 -       } else {
 187 -               /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
 188 -               /*
 189 -                *  Add a new tnode here
 190 -                *  first tnode need some special handling
 191 -                */
 192 +       /* Case 2: n is a LEAF or a TNODE and the key doesn't match.
 193 +        *
 194 +        *  Add a new tnode here
 195 +        *  first tnode need some special handling
 196 +        *  leaves us in position for handling as case 3
 197 +        */
 198 +       if (n) {
 199 +               struct tnode *tn;
 200 +               int newpos;
 201
 202 -               if (n) {
 203 -                       pos = tp ? tp->pos+tp->bits : 0;
 204 -                       newpos = tkey_mismatch(key, pos, n->key);
 205 -                       tn = tnode_new(n->key, newpos, 1);
 206 -               } else {
 207 -                       newpos = 0;
 208 -                       tn = tnode_new(key, newpos, 1); /* First tnode */
 209 -               }
 210 +               newpos = KEYLENGTH - __fls(n->key ^ key) - 1;
 211
 212 +               tn = tnode_new(key, newpos, 1);
 213                 if (!tn) {
 214                         free_leaf_info(li);
 215                         node_free(l);
 216                         return NULL;
 217                 }
 218
 219 -               node_set_parent(tn, tp);
 220 -
 221 -               missbit = tkey_extract_bits(key, newpos, 1);
 222 -               put_child(tn, missbit, l);
 223 -               put_child(tn, 1-missbit, n);
 224 -
 225 -               if (tp) {
 226 -                       cindex = tkey_extract_bits(key, tp->pos, tp->bits);
 227 -                       put_child(tp, cindex, tn);
 228 -               } else {
 229 -                       rcu_assign_pointer(t->trie, tn);
 230 -               }
 231 +               /* initialize routes out of node */
 232 +               NODE_INIT_PARENT(tn, tp);
 233 +               put_child(tn, get_index(key, tn) ^ 1, n);
 234 +
 235 +               /* start adding routes into the node */
 236 +               put_child_root(tp, t, key, tn);
 237 +               node_set_parent(n, tn);
 238
 239 +               /* parent now has a NULL spot where the leaf can go */
 240                 tp = tn;
 241         }
 242
 243 -       if (tp && tp->pos + tp->bits > 32)
 244 -               pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
 245 -                       tp, tp->pos, tp->bits, key, plen);
 246 -
 247 -       /* Rebalance the trie */
 248 +       /* Case 3: n is NULL, and will just insert a new leaf */
 249 +       if (tp) {
 250 +               NODE_INIT_PARENT(l, tp);
 251 +               put_child(tp, get_index(key, tp), l);
 252 +               trie_rebalance(t, tp);
 253 +       } else {
 254 +               rcu_assign_pointer(t->trie, l);
 255 +       }
 256
 257 -       trie_rebalance(t, tp);
 258 -done:
 259         return fa_head;
 260  }
 261
 262 @@ -1470,11 +1416,11 @@ static void trie_leaf_remove(struct trie
 263         pr_debug("entering trie_leaf_remove(%p)\n", l);
 264
 265         if (tp) {
 266 -               t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
 267 -               put_child(tp, cindex, NULL);
 268 +               put_child(tp, get_index(l->key, tp), NULL);
 269                 trie_rebalance(t, tp);
 270 -       } else
 271 +       } else {
 272                 RCU_INIT_POINTER(t->trie, NULL);
 273 +       }
 274
 275         node_free(l);
 276  }