vnet/vnet/lisp-gpe/ip_forward.c

   1 /*
   2  * Copyright (c) 2016 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /**
  16  *  @file
  17  *  @brief LISP-GPE overlay IP forwarding logic and lookup data structures.
  18  *
  19  *  Provides an implementation of a Source/Dest (SD) IP FIB that leverages the
  20  *  existing destination only FIB. Lookups are done in two stages, first the
  21  *  destination FIB looks up a packet's destination address and then if a
  22  *  an SD entry is hit, the destination adjacency will point to the second
  23  *  stage, the source FIB, where the packet's source is looked up. Note that a
  24  *  miss in the source FIB does not result in an overall SD lookup retry with
  25  *  a less specific entry from the destination FIB.
  26  */
  27 #include <vnet/lisp-gpe/lisp_gpe.h>
  28
  29 /** Sets adj index for destination address in IP4 FIB. Similar to the function
  30  * in ip4_forward but this one avoids calling route callbacks */
  31 static void
  32 ip4_sd_fib_set_adj_index (lisp_gpe_main_t * lgm, ip4_fib_t * fib, u32 flags,
  33                           u32 dst_address_u32, u32 dst_address_length,
  34                           u32 adj_index)
  35 {
  36   ip_lookup_main_t *lm = lgm->lm4;
  37   uword *hash;
  38
  39   if (vec_bytes (fib->old_hash_values))
  40     memset (fib->old_hash_values, ~0, vec_bytes (fib->old_hash_values));
  41   if (vec_bytes (fib->new_hash_values))
  42     memset (fib->new_hash_values, ~0, vec_bytes (fib->new_hash_values));
  43   fib->new_hash_values[0] = adj_index;
  44
  45   /* Make sure adj index is valid. */
  46   if (CLIB_DEBUG > 0)
  47     (void) ip_get_adjacency (lm, adj_index);
  48
  49   hash = fib->adj_index_by_dst_address[dst_address_length];
  50
  51   hash = _hash_set3 (hash, dst_address_u32,
  52                      fib->new_hash_values, fib->old_hash_values);
  53
  54   fib->adj_index_by_dst_address[dst_address_length] = hash;
  55 }
  56
  57 /** Initialize the adjacency index by destination address vector for IP4 FIB.
  58  * Copied from ip4_forward since it's static */
  59 static void
  60 ip4_fib_init_adj_index_by_dst_address (ip_lookup_main_t * lm,
  61                                        ip4_fib_t * fib, u32 address_length)
  62 {
  63   hash_t *h;
  64   uword max_index;
  65
  66   ASSERT (lm->fib_result_n_bytes >= sizeof (uword));
  67   lm->fib_result_n_words = round_pow2 (lm->fib_result_n_bytes, sizeof (uword))
  68     / sizeof (uword);
  69
  70   fib->adj_index_by_dst_address[address_length] =
  71     hash_create (32 /* elts */ , lm->fib_result_n_words * sizeof (uword));
  72
  73   hash_set_flags (fib->adj_index_by_dst_address[address_length],
  74                   HASH_FLAG_NO_AUTO_SHRINK);
  75
  76   h = hash_header (fib->adj_index_by_dst_address[address_length]);
  77   max_index = (hash_value_bytes (h) / sizeof (fib->new_hash_values[0])) - 1;
  78
  79   /* Initialize new/old hash value vectors. */
  80   vec_validate_init_empty (fib->new_hash_values, max_index, ~0);
  81   vec_validate_init_empty (fib->old_hash_values, max_index, ~0);
  82 }
  83
  84 /** Add/del src route to IP4 SD FIB. */
  85 static void
  86 ip4_sd_fib_add_del_src_route (lisp_gpe_main_t * lgm,
  87                               ip4_add_del_route_args_t * a)
  88 {
  89   ip_lookup_main_t *lm = lgm->lm4;
  90   ip4_fib_t *fib;
  91   u32 dst_address, dst_address_length, adj_index, old_adj_index;
  92   uword *hash, is_del;
  93
  94   /* Either create new adjacency or use given one depending on arguments. */
  95   if (a->n_add_adj > 0)
  96     ip_add_adjacency (lm, a->add_adj, a->n_add_adj, &adj_index);
  97   else
  98     adj_index = a->adj_index;
  99
 100   dst_address = a->dst_address.data_u32;
 101   dst_address_length = a->dst_address_length;
 102
 103   fib = pool_elt_at_index (lgm->ip4_src_fibs, a->table_index_or_table_id);
 104
 105   if (!fib->adj_index_by_dst_address[dst_address_length])
 106     ip4_fib_init_adj_index_by_dst_address (lm, fib, dst_address_length);
 107
 108   hash = fib->adj_index_by_dst_address[dst_address_length];
 109
 110   is_del = (a->flags & IP4_ROUTE_FLAG_DEL) != 0;
 111
 112   if (is_del)
 113     {
 114       fib->old_hash_values[0] = ~0;
 115       hash = _hash_unset (hash, dst_address, fib->old_hash_values);
 116       fib->adj_index_by_dst_address[dst_address_length] = hash;
 117     }
 118   else
 119     ip4_sd_fib_set_adj_index (lgm, fib, a->flags, dst_address,
 120                               dst_address_length, adj_index);
 121
 122   old_adj_index = fib->old_hash_values[0];
 123
 124   /* Avoid spurious reference count increments */
 125   if (old_adj_index == adj_index
 126       && adj_index != ~0 && !(a->flags & IP4_ROUTE_FLAG_KEEP_OLD_ADJACENCY))
 127     {
 128       ip_adjacency_t *adj = ip_get_adjacency (lm, adj_index);
 129       if (adj->share_count > 0)
 130         adj->share_count--;
 131     }
 132
 133   ip4_fib_mtrie_add_del_route (fib, a->dst_address, dst_address_length,
 134                                is_del ? old_adj_index : adj_index, is_del);
 135
 136   /* Delete old adjacency index if present and changed. */
 137   if (!(a->flags & IP4_ROUTE_FLAG_KEEP_OLD_ADJACENCY)
 138       && old_adj_index != ~0 && old_adj_index != adj_index)
 139     ip_del_adjacency (lm, old_adj_index);
 140 }
 141
 142 /** Get src route from IP4 SD FIB. */
 143 static void *
 144 ip4_sd_get_src_route (lisp_gpe_main_t * lgm, u32 src_fib_index,
 145                       ip4_address_t * src, u32 address_length)
 146 {
 147   ip4_fib_t *fib = pool_elt_at_index (lgm->ip4_src_fibs, src_fib_index);
 148   uword *hash, *p;
 149
 150   hash = fib->adj_index_by_dst_address[address_length];
 151   p = hash_get (hash, src->as_u32);
 152   return (void *) p;
 153 }
 154
 155 /* *INDENT-OFF* */
 156 typedef CLIB_PACKED (struct ip4_route {
 157   ip4_address_t address;
 158   u32 address_length : 6;
 159   u32 index : 26;
 160 }) ip4_route_t;
 161 /* *INDENT-ON* */
 162
 163 /** Remove all routes from src IP4 FIB */
 164 void
 165 ip4_sd_fib_clear_src_fib (lisp_gpe_main_t * lgm, ip4_fib_t * fib)
 166 {
 167   ip4_route_t *routes = 0, *r;
 168   u32 i;
 169
 170   vec_reset_length (routes);
 171
 172   for (i = 0; i < ARRAY_LEN (fib->adj_index_by_dst_address); i++)
 173     {
 174       uword *hash = fib->adj_index_by_dst_address[i];
 175       hash_pair_t *p;
 176       ip4_route_t x;
 177
 178       x.address_length = i;
 179       x.index = 0;              /* shut up coverity */
 180
 181       /* *INDENT-OFF* */
 182       hash_foreach_pair (p, hash,
 183       ({
 184           x.address.data_u32 = p->key;
 185           vec_add1 (routes, x);
 186       }));
 187       /* *INDENT-ON* */
 188     }
 189
 190   vec_foreach (r, routes)
 191   {
 192     ip4_add_del_route_args_t a;
 193
 194     memset (&a, 0, sizeof (a));
 195     a.flags = IP4_ROUTE_FLAG_FIB_INDEX | IP4_ROUTE_FLAG_DEL;
 196     a.table_index_or_table_id = fib - lgm->ip4_src_fibs;
 197     a.dst_address = r->address;
 198     a.dst_address_length = r->address_length;
 199     a.adj_index = ~0;
 200
 201     ip4_sd_fib_add_del_src_route (lgm, &a);
 202   }
 203 }
 204
 205 /** Test if IP4 FIB is empty */
 206 static u8
 207 ip4_fib_is_empty (ip4_fib_t * fib)
 208 {
 209   u8 fib_is_empty;
 210   int i;
 211
 212   fib_is_empty = 1;
 213   for (i = ARRAY_LEN (fib->adj_index_by_dst_address) - 1; i >= 0; i--)
 214     {
 215       uword *hash = fib->adj_index_by_dst_address[i];
 216       uword n_elts = hash_elts (hash);
 217       if (n_elts)
 218         {
 219           fib_is_empty = 0;
 220           break;
 221         }
 222     }
 223   return fib_is_empty;
 224 }
 225
 226 /**
 227  * @brief Add/del route to IP4 SD FIB.
 228  *
 229  * Adds/remove routes to both destination and source FIBs. Entries added
 230  * to destination FIB are associated to adjacencies that point to the source
 231  * FIB and store the index of the particular source FIB associated to the
 232  * destination. Source FIBs are locally managed (see @ref lgm->ip4_src_fibs
 233  * and @ref lgm->ip6_src_fibs), but the adjacencies are allocated out of the
 234  * global adjacency pool.
 235  *
 236  * @param[in]   lgm             Reference to @ref lisp_gpe_main_t.
 237  * @param[out]  dst_prefix      Destination IP4 prefix.
 238  * @param[in]   src_prefix      Source IP4 prefix.
 239  * @param[in]   table_id        Table id.
 240  * @param[in]   add_adj         Pointer to the adjacency to be added.
 241  * @param[in]   is_add          Add/del flag.
 242  *
 243  * @return 0 on success.
 244  */
 245 static int
 246 ip4_sd_fib_add_del_route (lisp_gpe_main_t * lgm, ip_prefix_t * dst_prefix,
 247                           ip_prefix_t * src_prefix, u32 table_id,
 248                           ip_adjacency_t * add_adj, u8 is_add)
 249 {
 250   uword *p;
 251   ip4_add_del_route_args_t a;
 252   ip_adjacency_t *dst_adjp, dst_adj;
 253   ip4_address_t dst = ip_prefix_v4 (dst_prefix), src;
 254   u32 dst_address_length = ip_prefix_len (dst_prefix), src_address_length = 0;
 255   ip4_fib_t *src_fib;
 256
 257   if (src_prefix)
 258     {
 259       src = ip_prefix_v4 (src_prefix);
 260       src_address_length = ip_prefix_len (src_prefix);
 261     }
 262   else
 263     memset (&src, 0, sizeof (src));
 264
 265   /* lookup dst adj */
 266   p = ip4_get_route (lgm->im4, table_id, 0, dst.as_u8, dst_address_length);
 267
 268   if (is_add)
 269     {
 270       /* insert dst prefix to ip4 fib, if it's not in yet */
 271       if (p == 0)
 272         {
 273           /* allocate and init src ip4 fib */
 274           pool_get (lgm->ip4_src_fibs, src_fib);
 275           ip4_mtrie_init (&src_fib->mtrie);
 276
 277           /* configure adjacency */
 278           memset (&dst_adj, 0, sizeof (dst_adj));
 279
 280           /* reuse rewrite header to store pointer to src fib */
 281           dst_adj.rewrite_header.sw_if_index = src_fib - lgm->ip4_src_fibs;
 282
 283           /* dst adj should point to lisp gpe lookup */
 284           dst_adj.lookup_next_index = lgm->ip4_lookup_next_lgpe_ip4_lookup;
 285
 286           /* explicit_fib_index is used in IP6 FIB lookup, don't reuse it */
 287           dst_adj.explicit_fib_index = ~0;
 288           dst_adj.n_adj = 1;
 289
 290           /* make sure we have different signatures for adj in different tables
 291            * but with the same lookup_next_index and for adj in the same table
 292            * but associated to different destinations */
 293           dst_adj.if_address_index = table_id;
 294           dst_adj.indirect.next_hop.ip4 = dst;
 295
 296           memset (&a, 0, sizeof (a));
 297           a.flags = IP4_ROUTE_FLAG_TABLE_ID;
 298           a.table_index_or_table_id = table_id; /* vrf */
 299           a.adj_index = ~0;
 300           a.dst_address_length = dst_address_length;
 301           a.dst_address = dst;
 302           a.flags |= IP4_ROUTE_FLAG_ADD;
 303           a.add_adj = &dst_adj;
 304           a.n_add_adj = 1;
 305
 306           ip4_add_del_route (lgm->im4, &a);
 307
 308           /* lookup dst adj to obtain the adj index */
 309           p = ip4_get_route (lgm->im4, table_id, 0, dst.as_u8,
 310                              dst_address_length);
 311
 312           /* make sure insertion succeeded */
 313           if (CLIB_DEBUG)
 314             {
 315               ASSERT (p != 0);
 316               dst_adjp = ip_get_adjacency (lgm->lm4, p[0]);
 317               ASSERT (dst_adjp->rewrite_header.sw_if_index
 318                       == dst_adj.rewrite_header.sw_if_index);
 319             }
 320         }
 321     }
 322   else
 323     {
 324       if (p == 0)
 325         {
 326           clib_warning
 327             ("Trying to delete inexistent dst route for %U. Aborting",
 328              format_ip4_address_and_length, dst.as_u8, dst_address_length);
 329           return -1;
 330         }
 331     }
 332
 333   dst_adjp = ip_get_adjacency (lgm->lm4, p[0]);
 334
 335   /* add/del src prefix to src fib */
 336   memset (&a, 0, sizeof (a));
 337   a.flags = IP4_ROUTE_FLAG_TABLE_ID;
 338   a.table_index_or_table_id = dst_adjp->rewrite_header.sw_if_index;
 339   a.adj_index = ~0;
 340   a.flags |= is_add ? IP4_ROUTE_FLAG_ADD : IP4_ROUTE_FLAG_DEL;
 341   a.add_adj = add_adj;
 342   a.n_add_adj = is_add ? 1 : 0;
 343   /* if src prefix is null, add 0/0 */
 344   a.dst_address_length = src_address_length;
 345   a.dst_address = src;
 346   ip4_sd_fib_add_del_src_route (lgm, &a);
 347
 348   /* make sure insertion succeeded */
 349   if (CLIB_DEBUG && is_add)
 350     {
 351       uword *sai;
 352       ip_adjacency_t *src_adjp;
 353       sai = ip4_sd_get_src_route (lgm, dst_adjp->rewrite_header.sw_if_index,
 354                                   &src, src_address_length);
 355       ASSERT (sai != 0);
 356       src_adjp = ip_get_adjacency (lgm->lm4, sai[0]);
 357       ASSERT (src_adjp->if_address_index == add_adj->if_address_index);
 358     }
 359
 360   /* if a delete, check if there are elements left in the src fib */
 361   if (!is_add)
 362     {
 363       src_fib = pool_elt_at_index (lgm->ip4_src_fibs,
 364                                    dst_adjp->rewrite_header.sw_if_index);
 365       if (!src_fib)
 366         return 0;
 367
 368       /* if there's nothing left */
 369       if (ip4_fib_is_empty (src_fib))
 370         {
 371           /* remove the src fib ..  */
 372           pool_put (lgm->ip4_src_fibs, src_fib);
 373
 374           /* .. and remove dst route */
 375           memset (&a, 0, sizeof (a));
 376           a.flags = IP4_ROUTE_FLAG_TABLE_ID;
 377           a.table_index_or_table_id = table_id; /* vrf */
 378           a.adj_index = ~0;
 379           a.dst_address_length = dst_address_length;
 380           a.dst_address = dst;
 381           a.flags |= IP4_ROUTE_FLAG_DEL;
 382
 383           ip4_add_del_route (lgm->im4, &a);
 384         }
 385     }
 386
 387   return 0;
 388 }
 389
 390 /**
 391  * @brief Retrieve IP4 SD FIB entry.
 392  *
 393  * Looks up SD IP4 route by first looking up the destination in VPP's main FIB
 394  * and subsequently the source in the src FIB. The index of the source FIB is
 395  * stored in the dst adjacency's rewrite_header.sw_if_index. If source is 0
 396  * do search with 0/0 src.
 397  *
 398  * @param[in]   lgm             Reference to @ref lisp_gpe_main_t.
 399  * @param[out]  dst_prefix      Destination IP4 prefix.
 400  * @param[in]   src_prefix      Source IP4 prefix.
 401  * @param[in]   table_id        Table id.
 402  *
 403  * @return pointer to the adjacency if route found.
 404  */
 405 static void *
 406 ip4_sd_fib_get_route (lisp_gpe_main_t * lgm, ip_prefix_t * dst_prefix,
 407                       ip_prefix_t * src_prefix, u32 table_id)
 408 {
 409   uword *p;
 410   ip4_address_t dst = ip_prefix_v4 (dst_prefix), src;
 411   u32 dst_address_length = ip_prefix_len (dst_prefix), src_address_length = 0;
 412   ip_adjacency_t *dst_adj;
 413
 414   if (src_prefix)
 415     {
 416       src = ip_prefix_v4 (src_prefix);
 417       src_address_length = ip_prefix_len (src_prefix);
 418     }
 419   else
 420     memset (&src, 0, sizeof (src));
 421
 422   /* lookup dst adj */
 423   p = ip4_get_route (lgm->im4, table_id, 0, dst.as_u8, dst_address_length);
 424   if (p == 0)
 425     return p;
 426
 427   dst_adj = ip_get_adjacency (lgm->lm4, p[0]);
 428   return ip4_sd_get_src_route (lgm, dst_adj->rewrite_header.sw_if_index, &src,
 429                                src_address_length);
 430 }
 431
 432 /** Get src route from IP6 SD FIB. */
 433 static u32
 434 ip6_sd_get_src_route (lisp_gpe_main_t * lgm, u32 src_fib_index,
 435                       ip6_address_t * src, u32 address_length)
 436 {
 437   int rv;
 438   BVT (clib_bihash_kv) kv, value;
 439   ip6_src_fib_t *fib = pool_elt_at_index (lgm->ip6_src_fibs, src_fib_index);
 440
 441   ip6_address_t *mask;
 442
 443   ASSERT (address_length <= 128);
 444
 445   mask = &fib->fib_masks[address_length];
 446
 447   kv.key[0] = src->as_u64[0] & mask->as_u64[0];
 448   kv.key[1] = src->as_u64[1] & mask->as_u64[1];
 449   kv.key[2] = address_length;
 450
 451   rv = BV (clib_bihash_search_inline_2) (&fib->ip6_lookup_table, &kv, &value);
 452   if (rv == 0)
 453     return value.value;
 454
 455   return 0;
 456 }
 457
 458 static void
 459 compute_prefix_lengths_in_search_order (ip6_src_fib_t * fib)
 460 {
 461   int i;
 462   vec_reset_length (fib->prefix_lengths_in_search_order);
 463   /* Note: bitmap reversed so this is in fact a longest prefix match */
 464
 465   /* *INDENT-OFF* */
 466   clib_bitmap_foreach(i, fib->non_empty_dst_address_length_bitmap, ({
 467     int dst_address_length = 128 - i;
 468     vec_add1 (fib->prefix_lengths_in_search_order, dst_address_length);
 469   }));
 470   /* *INDENT-ON* */
 471 }
 472
 473 /** Add/del src route to IP6 SD FIB. Rewrite of ip6_add_del_route() because
 474  * it uses im6 to find the FIB .*/
 475 static void
 476 ip6_sd_fib_add_del_src_route (lisp_gpe_main_t * lgm,
 477                               ip6_add_del_route_args_t * a)
 478 {
 479   ip_lookup_main_t *lm = lgm->lm6;
 480   ip6_src_fib_t *fib;
 481   ip6_address_t dst_address;
 482   u32 dst_address_length, adj_index;
 483   uword is_del;
 484   u32 old_adj_index = ~0;
 485   BVT (clib_bihash_kv) kv, value;
 486
 487   vlib_smp_unsafe_warning ();
 488
 489   is_del = (a->flags & IP6_ROUTE_FLAG_DEL) != 0;
 490
 491   /* Either create new adjacency or use given one depending on arguments. */
 492   if (a->n_add_adj > 0)
 493     {
 494       ip_add_adjacency (lm, a->add_adj, a->n_add_adj, &adj_index);
 495     }
 496   else
 497     adj_index = a->adj_index;
 498
 499   dst_address = a->dst_address;
 500   dst_address_length = a->dst_address_length;
 501   fib = pool_elt_at_index (lgm->ip6_src_fibs, a->table_index_or_table_id);
 502
 503   ASSERT (dst_address_length < ARRAY_LEN (fib->fib_masks));
 504   ip6_address_mask (&dst_address, &fib->fib_masks[dst_address_length]);
 505
 506   /* refcount accounting */
 507   if (is_del)
 508     {
 509       ASSERT (fib->dst_address_length_refcounts[dst_address_length] > 0);
 510       if (--fib->dst_address_length_refcounts[dst_address_length] == 0)
 511         {
 512           fib->non_empty_dst_address_length_bitmap =
 513             clib_bitmap_set (fib->non_empty_dst_address_length_bitmap,
 514                              128 - dst_address_length, 0);
 515           compute_prefix_lengths_in_search_order (fib);
 516         }
 517     }
 518   else
 519     {
 520       fib->dst_address_length_refcounts[dst_address_length]++;
 521
 522       fib->non_empty_dst_address_length_bitmap =
 523         clib_bitmap_set (fib->non_empty_dst_address_length_bitmap,
 524                          128 - dst_address_length, 1);
 525       compute_prefix_lengths_in_search_order (fib);
 526     }
 527
 528   kv.key[0] = dst_address.as_u64[0];
 529   kv.key[1] = dst_address.as_u64[1];
 530   kv.key[2] = dst_address_length;
 531
 532   if (BV (clib_bihash_search) (&fib->ip6_lookup_table, &kv, &value) == 0)
 533     old_adj_index = value.value;
 534
 535   if (is_del)
 536     BV (clib_bihash_add_del) (&fib->ip6_lookup_table, &kv, 0 /* is_add */ );
 537   else
 538     {
 539       /* Make sure adj index is valid. */
 540       if (CLIB_DEBUG > 0)
 541         (void) ip_get_adjacency (lm, adj_index);
 542
 543       kv.value = adj_index;
 544
 545       BV (clib_bihash_add_del) (&fib->ip6_lookup_table, &kv, 1 /* is_add */ );
 546     }
 547
 548   /* Avoid spurious reference count increments */
 549   if (old_adj_index == adj_index
 550       && !(a->flags & IP6_ROUTE_FLAG_KEEP_OLD_ADJACENCY))
 551     {
 552       ip_adjacency_t *adj = ip_get_adjacency (lm, adj_index);
 553       if (adj->share_count > 0)
 554         adj->share_count--;
 555     }
 556
 557   /* Delete old adjacency index if present and changed. */
 558   {
 559     if (!(a->flags & IP6_ROUTE_FLAG_KEEP_OLD_ADJACENCY)
 560         && old_adj_index != ~0 && old_adj_index != adj_index)
 561       ip_del_adjacency (lm, old_adj_index);
 562   }
 563 }
 564
 565 static void
 566 ip6_src_fib_init (ip6_src_fib_t * fib)
 567 {
 568   uword i;
 569
 570   for (i = 0; i < ARRAY_LEN (fib->fib_masks); i++)
 571     {
 572       u32 j, i0, i1;
 573
 574       i0 = i / 32;
 575       i1 = i % 32;
 576
 577       for (j = 0; j < i0; j++)
 578         fib->fib_masks[i].as_u32[j] = ~0;
 579
 580       if (i1)
 581         fib->fib_masks[i].as_u32[i0] =
 582           clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
 583     }
 584
 585   if (fib->lookup_table_nbuckets == 0)
 586     fib->lookup_table_nbuckets = IP6_FIB_DEFAULT_HASH_NUM_BUCKETS;
 587
 588   fib->lookup_table_nbuckets = 1 << max_log2 (fib->lookup_table_nbuckets);
 589
 590   if (fib->lookup_table_size == 0)
 591     fib->lookup_table_size = IP6_FIB_DEFAULT_HASH_MEMORY_SIZE;
 592
 593   BV (clib_bihash_init) (&fib->ip6_lookup_table, "ip6 lookup table",
 594                          fib->lookup_table_nbuckets, fib->lookup_table_size);
 595
 596 }
 597
 598 /**
 599  * @brief Add/del route to IP6 SD FIB.
 600  *
 601  * Adds/remove routes to both destination and source FIBs. Entries added
 602  * to destination FIB are associated to adjacencies that point to the source
 603  * FIB and store the index of the particular source FIB associated to the
 604  * destination. Source FIBs are locally managed (see @ref lgm->ip4_src_fibs
 605  * and @ref lgm->ip6_src_fibs), but the adjacencies are allocated out of the
 606  * global adjacency pool.
 607  *
 608  * @param[in]   lgm             Reference to @ref lisp_gpe_main_t.
 609  * @param[out]  dst_prefix      Destination IP6 prefix.
 610  * @param[in]   src_prefix      Source IP6 prefix.
 611  * @param[in]   table_id        Table id.
 612  * @param[in]   add_adj         Pointer to the adjacency to be added.
 613  * @param[in]   is_add          Add/del flag.
 614  *
 615  * @return 0 on success.
 616  */
 617 static int
 618 ip6_sd_fib_add_del_route (lisp_gpe_main_t * lgm, ip_prefix_t * dst_prefix,
 619                           ip_prefix_t * src_prefix, u32 table_id,
 620                           ip_adjacency_t * add_adj, u8 is_add)
 621 {
 622   u32 adj_index;
 623   ip6_add_del_route_args_t a;
 624   ip_adjacency_t *dst_adjp, dst_adj;
 625   ip6_address_t dst = ip_prefix_v6 (dst_prefix), src;
 626   u32 dst_address_length = ip_prefix_len (dst_prefix), src_address_length = 0;
 627   ip6_src_fib_t *src_fib;
 628
 629   if (src_prefix)
 630     {
 631       src = ip_prefix_v6 (src_prefix);
 632       src_address_length = ip_prefix_len (src_prefix);
 633     }
 634   else
 635     memset (&src, 0, sizeof (src));
 636
 637   /* lookup dst adj and create it if it doesn't exist */
 638   adj_index = ip6_get_route (lgm->im6, table_id, 0, &dst, dst_address_length);
 639
 640   if (is_add)
 641     {
 642       /* insert dst prefix to ip6 fib, if it's not in yet */
 643       if (adj_index == 0)
 644         {
 645           /* allocate and init src ip6 fib */
 646           pool_get (lgm->ip6_src_fibs, src_fib);
 647           memset (src_fib, 0, sizeof (src_fib[0]));
 648           ip6_src_fib_init (src_fib);
 649
 650           memset (&dst_adj, 0, sizeof (dst_adj));
 651
 652           /* reuse rewrite header to store pointer to src fib */
 653           dst_adj.rewrite_header.sw_if_index = src_fib - lgm->ip6_src_fibs;
 654
 655           /* dst adj should point to lisp gpe ip lookup */
 656           dst_adj.lookup_next_index = lgm->ip6_lookup_next_lgpe_ip6_lookup;
 657
 658           /* explicit_fib_index is used in IP6 FIB lookup, don't reuse it */
 659           dst_adj.explicit_fib_index = ~0;
 660           dst_adj.n_adj = 1;
 661
 662           /* make sure we have different signatures for adj in different tables
 663            * but with the same lookup_next_index and for adj in the same table
 664            * but associated to different destinations */
 665           dst_adj.if_address_index = table_id;
 666           dst_adj.indirect.next_hop.ip6 = dst;
 667
 668           memset (&a, 0, sizeof (a));
 669           a.flags = IP6_ROUTE_FLAG_TABLE_ID;
 670           a.table_index_or_table_id = table_id; /* vrf */
 671           a.adj_index = ~0;
 672           a.dst_address_length = dst_address_length;
 673           a.dst_address = dst;
 674           a.flags |= IP6_ROUTE_FLAG_ADD;
 675           a.add_adj = &dst_adj;
 676           a.n_add_adj = 1;
 677
 678           ip6_add_del_route (lgm->im6, &a);
 679
 680           /* lookup dst adj to obtain the adj index */
 681           adj_index = ip6_get_route (lgm->im6, table_id, 0, &dst,
 682                                      dst_address_length);
 683
 684           /* make sure insertion succeeded */
 685           if (CLIB_DEBUG)
 686             {
 687               ASSERT (adj_index != 0);
 688               dst_adjp = ip_get_adjacency (lgm->lm6, adj_index);
 689               ASSERT (dst_adjp->rewrite_header.sw_if_index
 690                       == dst_adj.rewrite_header.sw_if_index);
 691             }
 692         }
 693     }
 694   else
 695     {
 696       if (adj_index == 0)
 697         {
 698           clib_warning
 699             ("Trying to delete inexistent dst route for %U. Aborting",
 700              format_ip_prefix, dst_prefix);
 701           return -1;
 702         }
 703     }
 704
 705   dst_adjp = ip_get_adjacency (lgm->lm6, adj_index);
 706
 707   /* add/del src prefix to src fib */
 708   memset (&a, 0, sizeof (a));
 709   a.flags = IP6_ROUTE_FLAG_TABLE_ID;
 710   a.table_index_or_table_id = dst_adjp->rewrite_header.sw_if_index;
 711   a.adj_index = ~0;
 712   a.flags |= is_add ? IP6_ROUTE_FLAG_ADD : IP6_ROUTE_FLAG_DEL;
 713   a.add_adj = add_adj;
 714   a.n_add_adj = is_add ? 1 : 0;
 715   /* if src prefix is null, add ::0 */
 716   a.dst_address_length = src_address_length;
 717   a.dst_address = src;
 718   ip6_sd_fib_add_del_src_route (lgm, &a);
 719
 720   /* make sure insertion succeeded */
 721   if (CLIB_DEBUG && is_add)
 722     {
 723       u32 sai;
 724       ip_adjacency_t *src_adjp;
 725       sai = ip6_sd_get_src_route (lgm, dst_adjp->rewrite_header.sw_if_index,
 726                                   &src, src_address_length);
 727       ASSERT (sai != 0);
 728       src_adjp = ip_get_adjacency (lgm->lm6, sai);
 729       ASSERT (src_adjp->if_address_index == add_adj->if_address_index);
 730     }
 731
 732   /* if a delete, check if there are elements left in the src fib */
 733   if (!is_add)
 734     {
 735       src_fib = pool_elt_at_index (lgm->ip6_src_fibs,
 736                                    dst_adjp->rewrite_header.sw_if_index);
 737       if (!src_fib)
 738         return 0;
 739
 740       /* if there's nothing left */
 741       if (clib_bitmap_count_set_bits
 742           (src_fib->non_empty_dst_address_length_bitmap) == 0)
 743         {
 744           /* remove src fib .. */
 745           pool_put (lgm->ip6_src_fibs, src_fib);
 746
 747           /* .. and remove dst route */
 748           memset (&a, 0, sizeof (a));
 749           a.flags = IP6_ROUTE_FLAG_TABLE_ID;
 750           a.table_index_or_table_id = table_id; /* vrf */
 751           a.adj_index = ~0;
 752           a.dst_address_length = dst_address_length;
 753           a.dst_address = dst;
 754           a.flags |= IP6_ROUTE_FLAG_DEL;
 755
 756           ip6_add_del_route (lgm->im6, &a);
 757         }
 758     }
 759
 760   return 0;
 761 }
 762
 763 /**
 764  * @brief Retrieve IP6 SD FIB entry.
 765  *
 766  * Looks up SD IP6 route by first looking up the destination in VPP's main FIB
 767  * and subsequently the source in the src FIB. The index of the source FIB is
 768  * stored in the dst adjacency's @ref rewrite_header.sw_if_index. If source is
 769  * 0 do search with ::/0 src.
 770  *
 771  * @param[in]   lgm             Reference to @ref lisp_gpe_main_t.
 772  * @param[out]  dst_prefix      Destination IP6 prefix.
 773  * @param[in]   src_prefix      Source IP6 prefix.
 774  * @param[in]   table_id        Table id.
 775  *
 776  * @return adjacency index if route found.
 777  */
 778 static u32
 779 ip6_sd_fib_get_route (lisp_gpe_main_t * lgm, ip_prefix_t * dst_prefix,
 780                       ip_prefix_t * src_prefix, u32 table_id)
 781 {
 782   u32 adj_index;
 783   ip6_address_t dst = ip_prefix_v6 (dst_prefix), src;
 784   u32 dst_address_length = ip_prefix_len (dst_prefix), src_address_length = 0;
 785   ip_adjacency_t *dst_adj;
 786
 787   if (src_prefix)
 788     {
 789       src = ip_prefix_v6 (src_prefix);
 790       src_address_length = ip_prefix_len (src_prefix);
 791     }
 792   else
 793     memset (&src, 0, sizeof (src));
 794
 795   /* lookup dst adj */
 796   adj_index = ip6_get_route (lgm->im6, table_id, 0, &dst, dst_address_length);
 797   if (adj_index == 0)
 798     return adj_index;
 799
 800   dst_adj = ip_get_adjacency (lgm->lm6, adj_index);
 801   return ip6_sd_get_src_route (lgm, dst_adj->rewrite_header.sw_if_index, &src,
 802                                src_address_length);
 803 }
 804
 805 /**
 806  * @brief Add/del route to IP4 or IP6 SD FIB.
 807  *
 808  * Adds/remove routes to both destination and source FIBs. Entries added
 809  * to destination FIB are associated to adjacencies that point to the source
 810  * FIB and store the index of the particular source FIB associated to the
 811  * destination. Source FIBs are locally managed (see @ref lgm->ip4_src_fibs
 812  * and @ref lgm->ip6_src_fibs), but the adjacencies are allocated out of the
 813  * global adjacency pool.
 814  *
 815  * @param[in]   lgm             Reference to @ref lisp_gpe_main_t.
 816  * @param[out]  dst_prefix      Destination IP prefix.
 817  * @param[in]   src_prefix      Source IP prefix.
 818  * @param[in]   table_id        Table id.
 819  * @param[in]   add_adj         Pointer to the adjacency to be added.
 820  * @param[in]   is_add          Add/del flag.
 821  *
 822  * @return 0 on success.
 823  */
 824 int
 825 ip_sd_fib_add_del_route (lisp_gpe_main_t * lgm, ip_prefix_t * dst_prefix,
 826                          ip_prefix_t * src_prefix, u32 table_id,
 827                          ip_adjacency_t * add_adj, u8 is_add)
 828 {
 829   return (ip_prefix_version (dst_prefix) == IP4 ?
 830           ip4_sd_fib_add_del_route : ip6_sd_fib_add_del_route) (lgm,
 831                                                                 dst_prefix,
 832                                                                 src_prefix,
 833                                                                 table_id,
 834                                                                 add_adj,
 835                                                                 is_add);
 836 }
 837
 838 /**
 839  * @brief Retrieve IP4 or IP6 SD FIB entry.
 840  *
 841  * Looks up SD IP route by first looking up the destination in VPP's main FIB
 842  * and subsequently the source in the src FIB. The index of the source FIB is
 843  * stored in the dst adjacency's @ref rewrite_header.sw_if_index. If source is
 844  * 0 do search with ::/0 src.
 845  *
 846  * @param[in]   lgm             Reference to @ref lisp_gpe_main_t.
 847  * @param[out]  dst_prefix      Destination IP prefix.
 848  * @param[in]   src_prefix      Source IP prefix.
 849  * @param[in]   table_id        Table id.
 850  *
 851  * @return adjacency index if route found.
 852  */
 853 u32
 854 ip_sd_fib_get_route (lisp_gpe_main_t * lgm, ip_prefix_t * dst_prefix,
 855                      ip_prefix_t * src_prefix, u32 table_id)
 856 {
 857   if (ip_prefix_version (dst_prefix) == IP4)
 858     {
 859       u32 *adj_index = ip4_sd_fib_get_route (lgm, dst_prefix, src_prefix,
 860                                              table_id);
 861       return (adj_index == 0) ? 0 : adj_index[0];
 862     }
 863   else
 864     return ip6_sd_fib_get_route (lgm, dst_prefix, src_prefix, table_id);
 865 }
 866
 867 always_inline void
 868 ip4_src_fib_lookup_one (lisp_gpe_main_t * lgm, u32 src_fib_index0,
 869                         ip4_address_t * addr0, u32 * src_adj_index0)
 870 {
 871   ip4_fib_mtrie_leaf_t leaf0, leaf1;
 872   ip4_fib_mtrie_t *mtrie0;
 873
 874   /* if default route not hit in ip4 lookup */
 875   if (PREDICT_TRUE (src_fib_index0 != (u32) ~ 0))
 876     {
 877       mtrie0 = &vec_elt_at_index (lgm->ip4_src_fibs, src_fib_index0)->mtrie;
 878
 879       leaf0 = leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
 880       leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 0);
 881       leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 1);
 882       leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 2);
 883       leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 3);
 884
 885       /* Handle default route. */
 886       leaf0 = (leaf0 == IP4_FIB_MTRIE_LEAF_EMPTY) ?
 887         mtrie0->default_leaf : leaf0;
 888       src_adj_index0[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
 889     }
 890   else
 891     src_adj_index0[0] = ~0;
 892 }
 893
 894 always_inline void
 895 ip4_src_fib_lookup_two (lisp_gpe_main_t * lgm, u32 src_fib_index0,
 896                         u32 src_fib_index1, ip4_address_t * addr0,
 897                         ip4_address_t * addr1, u32 * src_adj_index0,
 898                         u32 * src_adj_index1)
 899 {
 900   ip4_fib_mtrie_leaf_t leaf0, leaf1;
 901   ip4_fib_mtrie_t *mtrie0, *mtrie1;
 902
 903   /* if default route not hit in ip4 lookup */
 904   if (PREDICT_TRUE
 905       (src_fib_index0 != (u32) ~ 0 && src_fib_index1 != (u32) ~ 0))
 906     {
 907       mtrie0 = &vec_elt_at_index (lgm->ip4_src_fibs, src_fib_index0)->mtrie;
 908       mtrie1 = &vec_elt_at_index (lgm->ip4_src_fibs, src_fib_index1)->mtrie;
 909
 910       leaf0 = leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
 911
 912       leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 0);
 913       leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 0);
 914
 915       leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 1);
 916       leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 1);
 917
 918       leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 2);
 919       leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 2);
 920
 921       leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 3);
 922       leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 3);
 923
 924       /* Handle default route. */
 925       leaf0 = (leaf0 == IP4_FIB_MTRIE_LEAF_EMPTY) ?
 926         mtrie0->default_leaf : leaf0;
 927       leaf1 = (leaf1 == IP4_FIB_MTRIE_LEAF_EMPTY) ?
 928         mtrie1->default_leaf : leaf1;
 929       src_adj_index0[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
 930       src_adj_index1[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf1);
 931     }
 932   else
 933     {
 934       ip4_src_fib_lookup_one (lgm, src_fib_index0, addr0, src_adj_index0);
 935       ip4_src_fib_lookup_one (lgm, src_fib_index1, addr1, src_adj_index1);
 936     }
 937 }
 938
 939 /**
 940  * @brief IPv4 src lookup node.
 941  * @node lgpe-ip4-lookup
 942  *
 943  * The LISP IPv4 source lookup dispatch node.
 944  *
 945  * This is the IPv4 source lookup dispatch node. It first looks up the
 946  * adjacency hit in the main (destination) FIB and then uses its
 947  * <code>rewrite_header.sw_if_index</code>to find the source FIB wherein
 948  * the source IP is subsequently looked up. Data in the resulting adjacency
 949  * is used to decide the next node (the lisp_gpe interface) and if a flow
 950  * hash must be computed, when traffic can be load balanced over multiple
 951  * tunnels.
 952  *
 953  *
 954  * @param[in]   vm      vlib_main_t corresponding to current thread.
 955  * @param[in]   node    vlib_node_runtime_t data for this node.
 956  * @param[in]   frame   vlib_frame_t whose contents should be dispatched.
 957  *
 958  * @return number of vectors in frame.
 959  */
 960 always_inline uword
 961 lgpe_ip4_lookup (vlib_main_t * vm, vlib_node_runtime_t * node,
 962                  vlib_frame_t * from_frame)
 963 {
 964   u32 n_left_from, next_index, *from, *to_next;
 965   lisp_gpe_main_t *lgm = &lisp_gpe_main;
 966
 967   from = vlib_frame_vector_args (from_frame);
 968   n_left_from = from_frame->n_vectors;
 969
 970   next_index = node->cached_next_index;
 971
 972   while (n_left_from > 0)
 973     {
 974       u32 n_left_to_next;
 975
 976       vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
 977
 978       while (n_left_from >= 4 && n_left_to_next >= 2)
 979         {
 980           u32 bi0, bi1;
 981           vlib_buffer_t *b0, *b1;
 982           ip4_header_t *ip0, *ip1;
 983           u32 dst_adj_index0, src_adj_index0, src_fib_index0;
 984           u32 dst_adj_index1, src_adj_index1, src_fib_index1;
 985           ip_adjacency_t *dst_adj0, *src_adj0, *dst_adj1, *src_adj1;
 986           u32 next0, next1;
 987
 988           next0 = next1 = LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP;
 989
 990           /* Prefetch next iteration. */
 991           {
 992             vlib_buffer_t *p2, *p3;
 993
 994             p2 = vlib_get_buffer (vm, from[2]);
 995             p3 = vlib_get_buffer (vm, from[3]);
 996
 997             vlib_prefetch_buffer_header (p2, LOAD);
 998             vlib_prefetch_buffer_header (p3, LOAD);
 999
1000             CLIB_PREFETCH (p2->data, 2 * CLIB_CACHE_LINE_BYTES, LOAD);
1001             CLIB_PREFETCH (p3->data, 2 * CLIB_CACHE_LINE_BYTES, LOAD);
1002           }
1003
1004           bi0 = from[0];
1005           bi1 = from[1];
1006           to_next[0] = bi0;
1007           to_next[1] = bi1;
1008           from += 2;
1009           to_next += 2;
1010           n_left_to_next -= 2;
1011           n_left_from -= 2;
1012
1013           b0 = vlib_get_buffer (vm, bi0);
1014           b1 = vlib_get_buffer (vm, bi1);
1015
1016           ip0 = vlib_buffer_get_current (b0);
1017           ip1 = vlib_buffer_get_current (b1);
1018
1019           /* dst lookup was done by ip4 lookup */
1020           dst_adj_index0 = vnet_buffer (b0)->ip.adj_index[VLIB_TX];
1021           dst_adj_index1 = vnet_buffer (b1)->ip.adj_index[VLIB_TX];
1022
1023           dst_adj0 = ip_get_adjacency (lgm->lm4, dst_adj_index0);
1024           dst_adj1 = ip_get_adjacency (lgm->lm4, dst_adj_index1);
1025
1026           src_fib_index0 = dst_adj0->rewrite_header.sw_if_index;
1027           src_fib_index1 = dst_adj1->rewrite_header.sw_if_index;
1028
1029           ip4_src_fib_lookup_two (lgm, src_fib_index0, src_fib_index1,
1030                                   &ip0->src_address, &ip1->src_address,
1031                                   &src_adj_index0, &src_adj_index1);
1032
1033           /* if a source fib exists */
1034           if (PREDICT_TRUE ((u32) ~ 0 != src_adj_index0
1035                             && (u32) ~ 0 != src_adj_index1))
1036             {
1037               vnet_buffer (b0)->ip.adj_index[VLIB_TX] = src_adj_index0;
1038               vnet_buffer (b1)->ip.adj_index[VLIB_TX] = src_adj_index1;
1039
1040               src_adj0 = ip_get_adjacency (lgm->lm4, src_adj_index0);
1041               src_adj1 = ip_get_adjacency (lgm->lm4, src_adj_index1);
1042
1043               next0 = src_adj0->explicit_fib_index;
1044               next1 = src_adj1->explicit_fib_index;
1045
1046               /* prepare buffer for lisp-gpe output node */
1047               vnet_buffer (b0)->sw_if_index[VLIB_TX] =
1048                 src_adj0->rewrite_header.sw_if_index;
1049               vnet_buffer (b1)->sw_if_index[VLIB_TX] =
1050                 src_adj1->rewrite_header.sw_if_index;
1051
1052               /* if multipath: saved_lookup_next_index is reused to store
1053                * nb of sub-tunnels. If greater than 1, multipath is on.
1054                * Note that flow hash should be 0 after ipx lookup! */
1055               if (PREDICT_TRUE (src_adj0->saved_lookup_next_index > 1))
1056                 vnet_buffer (b0)->ip.flow_hash =
1057                   ip4_compute_flow_hash (ip0, IP_FLOW_HASH_DEFAULT);
1058
1059               if (PREDICT_TRUE (src_adj1->saved_lookup_next_index > 1))
1060                 vnet_buffer (b1)->ip.flow_hash =
1061                   ip4_compute_flow_hash (ip1, IP_FLOW_HASH_DEFAULT);
1062             }
1063           else
1064             {
1065               if ((u32) ~ 0 != src_adj_index0)
1066                 {
1067                   vnet_buffer (b0)->ip.adj_index[VLIB_TX] = src_adj_index0;
1068                   src_adj0 = ip_get_adjacency (lgm->lm4, src_adj_index0);
1069                   next0 = src_adj0->explicit_fib_index;
1070                   vnet_buffer (b0)->sw_if_index[VLIB_TX] =
1071                     src_adj0->rewrite_header.sw_if_index;
1072
1073                   if (PREDICT_TRUE (src_adj0->saved_lookup_next_index > 1))
1074                     vnet_buffer (b0)->ip.flow_hash =
1075                       ip4_compute_flow_hash (ip0, IP_FLOW_HASH_DEFAULT);
1076                 }
1077               else
1078                 {
1079                   next0 = LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP;
1080                 }
1081
1082               if ((u32) ~ 0 != src_adj_index1)
1083                 {
1084                   vnet_buffer (b1)->ip.adj_index[VLIB_TX] = src_adj_index1;
1085                   src_adj1 = ip_get_adjacency (lgm->lm4, src_adj_index1);
1086                   next1 = src_adj1->explicit_fib_index;
1087                   vnet_buffer (b1)->sw_if_index[VLIB_TX] =
1088                     src_adj1->rewrite_header.sw_if_index;
1089                   if (PREDICT_TRUE (src_adj1->saved_lookup_next_index > 1))
1090                     vnet_buffer (b1)->ip.flow_hash =
1091                       ip4_compute_flow_hash (ip1, IP_FLOW_HASH_DEFAULT);
1092                 }
1093               else
1094                 {
1095                   next1 = LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP;
1096                 }
1097             }
1098
1099           /* mark the packets for CP lookup if needed */
1100           if (PREDICT_FALSE (LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP == next0))
1101             vnet_buffer (b0)->lisp.overlay_afi = LISP_AFI_IP;
1102           if (PREDICT_FALSE (LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP == next1))
1103             vnet_buffer (b1)->lisp.overlay_afi = LISP_AFI_IP;
1104
1105           vlib_validate_buffer_enqueue_x2 (vm, node, next_index, to_next,
1106                                            n_left_to_next, bi0, bi1, next0,
1107                                            next1);
1108         }
1109
1110       while (n_left_from > 0 && n_left_to_next > 0)
1111         {
1112           vlib_buffer_t *b0;
1113           ip4_header_t *ip0;
1114           u32 bi0, dst_adj_index0, src_adj_index0, src_fib_index0;
1115           u32 next0 = LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP;
1116           ip_adjacency_t *dst_adj0, *src_adj0;
1117
1118           bi0 = from[0];
1119           to_next[0] = bi0;
1120           from += 1;
1121           to_next += 1;
1122           n_left_from -= 1;
1123           n_left_to_next -= 1;
1124
1125           b0 = vlib_get_buffer (vm, bi0);
1126           ip0 = vlib_buffer_get_current (b0);
1127
1128           /* dst lookup was done by ip4 lookup */
1129           dst_adj_index0 = vnet_buffer (b0)->ip.adj_index[VLIB_TX];
1130           dst_adj0 = ip_get_adjacency (lgm->lm4, dst_adj_index0);
1131           src_fib_index0 = dst_adj0->rewrite_header.sw_if_index;
1132
1133           /* do src lookup */
1134           ip4_src_fib_lookup_one (lgm, src_fib_index0, &ip0->src_address,
1135                                   &src_adj_index0);
1136
1137           /* if a source fib exists */
1138           if (PREDICT_TRUE ((u32) ~ 0 != src_adj_index0))
1139             {
1140               vnet_buffer (b0)->ip.adj_index[VLIB_TX] = src_adj_index0;
1141               src_adj0 = ip_get_adjacency (lgm->lm4, src_adj_index0);
1142               next0 = src_adj0->explicit_fib_index;
1143
1144               /* prepare packet for lisp-gpe output node */
1145               vnet_buffer (b0)->sw_if_index[VLIB_TX] =
1146                 src_adj0->rewrite_header.sw_if_index;
1147
1148               /* if multipath: saved_lookup_next_index is reused to store
1149                * nb of sub-tunnels. If greater than 1, multipath is on */
1150               if (PREDICT_TRUE (src_adj0->saved_lookup_next_index > 1))
1151                 vnet_buffer (b0)->ip.flow_hash =
1152                   ip4_compute_flow_hash (ip0, IP_FLOW_HASH_DEFAULT);
1153             }
1154           else
1155             {
1156               next0 = LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP;
1157             }
1158
1159           if (PREDICT_FALSE (LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP == next0))
1160             vnet_buffer (b0)->lisp.overlay_afi = LISP_AFI_IP;
1161
1162           vlib_validate_buffer_enqueue_x1 (vm, node, next_index, to_next,
1163                                            n_left_to_next, bi0, next0);
1164         }
1165       vlib_put_next_frame (vm, node, next_index, n_left_to_next);
1166     }
1167   return from_frame->n_vectors;
1168 }
1169
1170 /* *INDENT-OFF* */
1171 VLIB_REGISTER_NODE (lgpe_ip4_lookup_node) = {
1172   .function = lgpe_ip4_lookup,
1173   .name = "lgpe-ip4-lookup",
1174   .vector_size = sizeof (u32),
1175
1176   .type = VLIB_NODE_TYPE_INTERNAL,
1177
1178   .n_next_nodes = LGPE_IP4_LOOKUP_N_NEXT,
1179   .next_nodes = {
1180 #define _(sym,str) [LGPE_IP4_LOOKUP_NEXT_##sym] = str,
1181       foreach_lgpe_ip4_lookup_next
1182 #undef _
1183   },
1184 };
1185 /* *INDENT-ON* */
1186
1187 static u32
1188 ip6_src_fib_lookup (lisp_gpe_main_t * lgm, u32 src_fib_index,
1189                     ip6_address_t * src)
1190 {
1191   int i, len;
1192   int rv;
1193   BVT (clib_bihash_kv) kv, value;
1194   ip6_src_fib_t *fib = pool_elt_at_index (lgm->ip6_src_fibs, src_fib_index);
1195
1196   len = vec_len (fib->prefix_lengths_in_search_order);
1197
1198   for (i = 0; i < len; i++)
1199     {
1200       int dst_address_length = fib->prefix_lengths_in_search_order[i];
1201       ip6_address_t *mask;
1202
1203       ASSERT (dst_address_length >= 0 && dst_address_length <= 128);
1204
1205       mask = &fib->fib_masks[dst_address_length];
1206
1207       kv.key[0] = src->as_u64[0] & mask->as_u64[0];
1208       kv.key[1] = src->as_u64[1] & mask->as_u64[1];
1209       kv.key[2] = dst_address_length;
1210
1211       rv =
1212         BV (clib_bihash_search_inline_2) (&fib->ip6_lookup_table, &kv,
1213                                           &value);
1214       if (rv == 0)
1215         return value.value;
1216     }
1217
1218   return 0;
1219 }
1220
1221 always_inline void
1222 ip6_src_fib_lookup_one (lisp_gpe_main_t * lgm, u32 src_fib_index0,
1223                         ip6_address_t * addr0, u32 * src_adj_index0)
1224 {
1225   /* if default route not hit in ip6 lookup */
1226   if (PREDICT_TRUE (src_fib_index0 != (u32) ~ 0))
1227     src_adj_index0[0] = ip6_src_fib_lookup (lgm, src_fib_index0, addr0);
1228   else
1229     src_adj_index0[0] = ~0;
1230 }
1231
1232 always_inline void
1233 ip6_src_fib_lookup_two (lisp_gpe_main_t * lgm, u32 src_fib_index0,
1234                         u32 src_fib_index1, ip6_address_t * addr0,
1235                         ip6_address_t * addr1, u32 * src_adj_index0,
1236                         u32 * src_adj_index1)
1237 {
1238   /* if default route not hit in ip6 lookup */
1239   if (PREDICT_TRUE
1240       (src_fib_index0 != (u32) ~ 0 && src_fib_index1 != (u32) ~ 0))
1241     {
1242       src_adj_index0[0] = ip6_src_fib_lookup (lgm, src_fib_index0, addr0);
1243       src_adj_index1[0] = ip6_src_fib_lookup (lgm, src_fib_index1, addr1);
1244     }
1245   else
1246     {
1247       ip6_src_fib_lookup_one (lgm, src_fib_index0, addr0, src_adj_index0);
1248       ip6_src_fib_lookup_one (lgm, src_fib_index1, addr1, src_adj_index1);
1249     }
1250 }
1251
1252 /**
1253  * @brief IPv6 src lookup node.
1254  * @node lgpe-ip6-lookup
1255  *
1256  * The LISP IPv6 source lookup dispatch node.
1257  *
1258  * This is the IPv6 source lookup dispatch node. It first looks up the
1259  * adjacency hit in the main (destination) FIB and then uses its
1260  * <code>rewrite_header.sw_if_index</code>to find the source FIB wherein
1261  * the source IP is subsequently looked up. Data in the resulting adjacency
1262  * is used to decide the next node (the lisp_gpe interface) and if a flow
1263  * hash must be computed, when traffic can be load balanced over multiple
1264  * tunnels.
1265  *
1266  * @param[in]   vm      vlib_main_t corresponding to current thread.
1267  * @param[in]   node    vlib_node_runtime_t data for this node.
1268  * @param[in]   frame   vlib_frame_t whose contents should be dispatched.
1269  *
1270  * @return number of vectors in frame.
1271  */
1272 always_inline uword
1273 lgpe_ip6_lookup (vlib_main_t * vm, vlib_node_runtime_t * node,
1274                  vlib_frame_t * from_frame)
1275 {
1276   u32 n_left_from, next_index, *from, *to_next;
1277   lisp_gpe_main_t *lgm = &lisp_gpe_main;
1278
1279   from = vlib_frame_vector_args (from_frame);
1280   n_left_from = from_frame->n_vectors;
1281
1282   next_index = node->cached_next_index;
1283
1284   while (n_left_from > 0)
1285     {
1286       u32 n_left_to_next;
1287
1288       vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
1289
1290       while (n_left_from >= 4 && n_left_to_next >= 2)
1291         {
1292           u32 bi0, bi1;
1293           vlib_buffer_t *b0, *b1;
1294           ip6_header_t *ip0, *ip1;
1295           u32 dst_adj_index0, src_adj_index0, src_fib_index0, dst_adj_index1,
1296             src_adj_index1, src_fib_index1;
1297           ip_adjacency_t *dst_adj0, *src_adj0, *dst_adj1, *src_adj1;
1298           u32 next0, next1;
1299
1300           next0 = next1 = LGPE_IP6_LOOKUP_NEXT_LISP_CP_LOOKUP;
1301
1302           /* Prefetch next iteration. */
1303           {
1304             vlib_buffer_t *p2, *p3;
1305
1306             p2 = vlib_get_buffer (vm, from[2]);
1307             p3 = vlib_get_buffer (vm, from[3]);
1308
1309             vlib_prefetch_buffer_header (p2, LOAD);
1310             vlib_prefetch_buffer_header (p3, LOAD);
1311
1312             CLIB_PREFETCH (p2->data, 2 * CLIB_CACHE_LINE_BYTES, LOAD);
1313             CLIB_PREFETCH (p3->data, 2 * CLIB_CACHE_LINE_BYTES, LOAD);
1314           }
1315
1316           bi0 = from[0];
1317           bi1 = from[1];
1318           to_next[0] = bi0;
1319           to_next[1] = bi1;
1320           from += 2;
1321           to_next += 2;
1322           n_left_to_next -= 2;
1323           n_left_from -= 2;
1324
1325           b0 = vlib_get_buffer (vm, bi0);
1326           b1 = vlib_get_buffer (vm, bi1);
1327
1328           ip0 = vlib_buffer_get_current (b0);
1329           ip1 = vlib_buffer_get_current (b1);
1330
1331           /* dst lookup was done by ip6 lookup */
1332           dst_adj_index0 = vnet_buffer (b0)->ip.adj_index[VLIB_TX];
1333           dst_adj_index1 = vnet_buffer (b1)->ip.adj_index[VLIB_TX];
1334
1335           dst_adj0 = ip_get_adjacency (lgm->lm6, dst_adj_index0);
1336           dst_adj1 = ip_get_adjacency (lgm->lm6, dst_adj_index1);
1337
1338           src_fib_index0 = dst_adj0->rewrite_header.sw_if_index;
1339           src_fib_index1 = dst_adj1->rewrite_header.sw_if_index;
1340
1341           ip6_src_fib_lookup_two (lgm, src_fib_index0, src_fib_index1,
1342                                   &ip0->src_address, &ip1->src_address,
1343                                   &src_adj_index0, &src_adj_index1);
1344
1345           /* if a source fib exists */
1346           if (PREDICT_TRUE ((u32) ~ 0 != src_adj_index0
1347                             && (u32) ~ 0 != src_adj_index1))
1348             {
1349               vnet_buffer (b0)->ip.adj_index[VLIB_TX] = src_adj_index0;
1350               vnet_buffer (b1)->ip.adj_index[VLIB_TX] = src_adj_index1;
1351
1352               src_adj0 = ip_get_adjacency (lgm->lm6, src_adj_index0);
1353               src_adj1 = ip_get_adjacency (lgm->lm6, src_adj_index1);
1354
1355               next0 = src_adj0->explicit_fib_index;
1356               next1 = src_adj1->explicit_fib_index;
1357
1358               /* prepare buffer for lisp-gpe output node */
1359               vnet_buffer (b0)->sw_if_index[VLIB_TX] =
1360                 src_adj0->rewrite_header.sw_if_index;
1361               vnet_buffer (b1)->sw_if_index[VLIB_TX] =
1362                 src_adj1->rewrite_header.sw_if_index;
1363
1364               /* if multipath: saved_lookup_next_index is reused to store
1365                * nb of sub-tunnels. If greater than 1, multipath is on.
1366                * Note that flow hash should be 0 after ipx lookup! */
1367               if (PREDICT_TRUE (src_adj0->saved_lookup_next_index > 1))
1368                 vnet_buffer (b0)->ip.flow_hash =
1369                   ip6_compute_flow_hash (ip0, IP_FLOW_HASH_DEFAULT);
1370
1371               if (PREDICT_TRUE (src_adj1->saved_lookup_next_index > 1))
1372                 vnet_buffer (b1)->ip.flow_hash =
1373                   ip6_compute_flow_hash (ip1, IP_FLOW_HASH_DEFAULT);
1374             }
1375           else
1376             {
1377               if (src_adj_index0 != (u32) ~ 0)
1378                 {
1379                   vnet_buffer (b0)->ip.adj_index[VLIB_TX] = src_adj_index0;
1380                   src_adj0 = ip_get_adjacency (lgm->lm6, src_adj_index0);
1381                   next0 = src_adj0->explicit_fib_index;
1382                   vnet_buffer (b0)->sw_if_index[VLIB_TX] =
1383                     src_adj0->rewrite_header.sw_if_index;
1384
1385                   if (PREDICT_TRUE (src_adj0->saved_lookup_next_index > 1))
1386                     vnet_buffer (b0)->ip.flow_hash =
1387                       ip6_compute_flow_hash (ip0, IP_FLOW_HASH_DEFAULT);
1388                 }
1389               else
1390                 {
1391                   next0 = LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP;
1392                 }
1393
1394               if (src_adj_index1 != (u32) ~ 0)
1395                 {
1396                   vnet_buffer (b1)->ip.adj_index[VLIB_TX] = src_adj_index1;
1397                   src_adj1 = ip_get_adjacency (lgm->lm6, src_adj_index1);
1398                   next1 = src_adj1->explicit_fib_index;
1399                   vnet_buffer (b1)->sw_if_index[VLIB_TX] =
1400                     src_adj1->rewrite_header.sw_if_index;
1401
1402                   if (PREDICT_TRUE (src_adj1->saved_lookup_next_index > 1))
1403                     vnet_buffer (b1)->ip.flow_hash =
1404                       ip6_compute_flow_hash (ip1, IP_FLOW_HASH_DEFAULT);
1405                 }
1406               else
1407                 {
1408                   next1 = LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP;
1409                 }
1410             }
1411
1412           /* mark the packets for CP lookup if needed */
1413           if (PREDICT_FALSE (LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP == next0))
1414             vnet_buffer (b0)->lisp.overlay_afi = LISP_AFI_IP;
1415           if (PREDICT_FALSE (LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP == next1))
1416             vnet_buffer (b1)->lisp.overlay_afi = LISP_AFI_IP;
1417
1418           vlib_validate_buffer_enqueue_x2 (vm, node, next_index, to_next,
1419                                            n_left_to_next, bi0, bi1, next0,
1420                                            next1);
1421         }
1422
1423       while (n_left_from > 0 && n_left_to_next > 0)
1424         {
1425           vlib_buffer_t *b0;
1426           ip6_header_t *ip0;
1427           u32 bi0, dst_adj_index0, src_adj_index0, src_fib_index0;
1428           u32 next0 = LGPE_IP6_LOOKUP_NEXT_LISP_CP_LOOKUP;
1429           ip_adjacency_t *dst_adj0, *src_adj0;
1430
1431           bi0 = from[0];
1432           to_next[0] = bi0;
1433           from += 1;
1434           to_next += 1;
1435           n_left_from -= 1;
1436           n_left_to_next -= 1;
1437
1438           b0 = vlib_get_buffer (vm, bi0);
1439           ip0 = vlib_buffer_get_current (b0);
1440
1441           /* dst lookup was done by ip6 lookup */
1442           dst_adj_index0 = vnet_buffer (b0)->ip.adj_index[VLIB_TX];
1443           dst_adj0 = ip_get_adjacency (lgm->lm6, dst_adj_index0);
1444           src_fib_index0 = dst_adj0->rewrite_header.sw_if_index;
1445
1446           /* do src lookup */
1447           ip6_src_fib_lookup_one (lgm, src_fib_index0, &ip0->src_address,
1448                                   &src_adj_index0);
1449
1450           /* if a source fib exists */
1451           if (PREDICT_TRUE (src_adj_index0 != (u32) ~ 0))
1452             {
1453               vnet_buffer (b0)->ip.adj_index[VLIB_TX] = src_adj_index0;
1454               src_adj0 = ip_get_adjacency (lgm->lm6, src_adj_index0);
1455               next0 = src_adj0->explicit_fib_index;
1456
1457               /* prepare packet for lisp-gpe output node */
1458               vnet_buffer (b0)->sw_if_index[VLIB_TX] =
1459                 src_adj0->rewrite_header.sw_if_index;
1460
1461               /* if multipath: saved_lookup_next_index is reused to store
1462                * nb of sub-tunnels. If greater than 1, multipath is on */
1463               if (PREDICT_TRUE (src_adj0->saved_lookup_next_index > 1))
1464                 vnet_buffer (b0)->ip.flow_hash =
1465                   ip6_compute_flow_hash (ip0, IP_FLOW_HASH_DEFAULT);
1466             }
1467           else
1468             {
1469               next0 = LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP;
1470             }
1471
1472           /* mark the packets for CP lookup if needed */
1473           if (PREDICT_FALSE (LGPE_IP4_LOOKUP_NEXT_LISP_CP_LOOKUP == next0))
1474             vnet_buffer (b0)->lisp.overlay_afi = LISP_AFI_IP;
1475
1476           vlib_validate_buffer_enqueue_x1 (vm, node, next_index, to_next,
1477                                            n_left_to_next, bi0, next0);
1478         }
1479       vlib_put_next_frame (vm, node, next_index, n_left_to_next);
1480     }
1481   return from_frame->n_vectors;
1482 }
1483
1484 /* *INDENT-OFF* */
1485 VLIB_REGISTER_NODE (lgpe_ip6_lookup_node) = {
1486   .function = lgpe_ip6_lookup,
1487   .name = "lgpe-ip6-lookup",
1488   .vector_size = sizeof (u32),
1489
1490   .type = VLIB_NODE_TYPE_INTERNAL,
1491
1492   .n_next_nodes = LGPE_IP6_LOOKUP_N_NEXT,
1493   .next_nodes = {
1494 #define _(sym,str) [LGPE_IP6_LOOKUP_NEXT_##sym] = str,
1495       foreach_lgpe_ip6_lookup_next
1496 #undef _
1497   },
1498 };
1499 /* *INDENT-ON* */
1500
1501 /*
1502  * fd.io coding-style-patch-verification: ON
1503  *
1504  * Local Variables:
1505  * eval: (c-set-style "gnu")
1506  * End:
1507  */