vnet/vnet/ip/lookup.c

   1 /*
   2  * Copyright (c) 2015 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  * ip/ip_lookup.c: ip4/6 adjacency and lookup table managment
  17  *
  18  * Copyright (c) 2008 Eliot Dresselhaus
  19  *
  20  * Permission is hereby granted, free of charge, to any person obtaining
  21  * a copy of this software and associated documentation files (the
  22  * "Software"), to deal in the Software without restriction, including
  23  * without limitation the rights to use, copy, modify, merge, publish,
  24  * distribute, sublicense, and/or sell copies of the Software, and to
  25  * permit persons to whom the Software is furnished to do so, subject to
  26  * the following conditions:
  27  *
  28  * The above copyright notice and this permission notice shall be
  29  * included in all copies or substantial portions of the Software.
  30  *
  31  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  32  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  33  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  34  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  35  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  36  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  37  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  38  */
  39
  40 #include <vppinfra/math.h>              /* for fabs */
  41 #include <vnet/ip/ip.h>
  42 #include <vnet/ip/adj_alloc.h>
  43
  44 static void
  45 ip_multipath_del_adjacency (ip_lookup_main_t * lm, u32 del_adj_index);
  46
  47 always_inline void
  48 ip_poison_adjacencies (ip_adjacency_t * adj, uword n_adj)
  49 {
  50   if (CLIB_DEBUG > 0)
  51     {
  52       u32 save_handle = adj->heap_handle;;
  53       u32 save_n_adj = adj->n_adj;
  54
  55       memset (adj, 0xfe, n_adj * sizeof (adj[0]));
  56
  57       adj->heap_handle = save_handle;
  58       adj->n_adj = save_n_adj;
  59     }
  60 }
  61
  62 static void
  63 ip_share_adjacency(ip_lookup_main_t * lm, u32 adj_index)
  64 {
  65   ip_adjacency_t * adj = ip_get_adjacency(lm, adj_index);
  66   uword * p;
  67   u32 old_ai;
  68   uword signature = vnet_ip_adjacency_signature (adj);
  69
  70   p = hash_get (lm->adj_index_by_signature, signature);
  71   /* Hash collision? */
  72   if (p)
  73     {
  74       /* Save the adj index, p[0] will be toast after the unset! */
  75       old_ai = p[0];
  76       hash_unset (lm->adj_index_by_signature, signature);
  77       hash_set (lm->adj_index_by_signature, signature, adj_index);
  78       adj->next_adj_with_signature = old_ai;
  79     }
  80   else
  81     {
  82       adj->next_adj_with_signature = 0;
  83       hash_set (lm->adj_index_by_signature, signature, adj_index);
  84     }
  85 }
  86
  87 static void
  88 ip_unshare_adjacency(ip_lookup_main_t * lm, u32 adj_index)
  89 {
  90   ip_adjacency_t * adj = ip_get_adjacency(lm, adj_index);
  91   uword signature;
  92   uword * p;
  93   u32 this_ai;
  94   ip_adjacency_t * this_adj, * prev_adj = 0;
  95
  96   signature = vnet_ip_adjacency_signature (adj);
  97   p = hash_get (lm->adj_index_by_signature, signature);
  98   if (p == 0)
  99       return;
 100
 101   this_ai = p[0];
 102   /* At the top of the signature chain (likely)? */
 103   if (this_ai == adj_index)
 104     {
 105       if (adj->next_adj_with_signature == 0)
 106         {
 107           hash_unset (lm->adj_index_by_signature, signature);
 108           return;
 109         }
 110       else
 111         {
 112           this_adj = ip_get_adjacency (lm, adj->next_adj_with_signature);
 113           hash_unset (lm->adj_index_by_signature, signature);
 114           hash_set (lm->adj_index_by_signature, signature,
 115                     this_adj->heap_handle);
 116         }
 117     }
 118   else                      /* walk signature chain */
 119     {
 120       this_adj = ip_get_adjacency (lm, this_ai);
 121       while (this_adj != adj)
 122         {
 123           prev_adj = this_adj;
 124           this_adj = ip_get_adjacency
 125             (lm, this_adj->next_adj_with_signature);
 126           /*
 127            * This can happen when creating the first multipath adj of a set
 128            * We end up looking at the miss adjacency (handle==0).
 129            */
 130           if (this_adj->heap_handle == 0)
 131             return;
 132         }
 133       prev_adj->next_adj_with_signature = this_adj->next_adj_with_signature;
 134     }
 135 }
 136
 137 int ip_register_adjacency(vlib_main_t *vm,
 138                           u8 is_ip4,
 139                           ip_adj_register_t *reg)
 140 {
 141   ip_lookup_main_t *lm = (is_ip4)?&ip4_main.lookup_main:&ip6_main.lookup_main;
 142   vlib_node_t *node = vlib_get_node_by_name (vm, (u8 *) ((is_ip4)?"ip4-lookup":"ip6-lookup"));
 143   vlib_node_t *next_node = vlib_get_node_by_name(vm, (u8 *) reg->node_name);
 144   *reg->next_index = vlib_node_add_next (vm, node->index, next_node->index);
 145   vec_validate(lm->registered_adjacencies, *reg->next_index);
 146   lm->registered_adjacencies[*reg->next_index] = *reg;
 147   return 0;
 148 }
 149
 150 int ip_init_registered_adjacencies(u8 is_ip4)
 151 {
 152   vlib_main_t *vm = vlib_get_main();
 153   ip_lookup_main_t *lm = (is_ip4)?&ip4_main.lookup_main:&ip6_main.lookup_main;
 154   ip_adj_register_t *reg = lm->registered_adjacencies;
 155   lm->registered_adjacencies = 0; //Init vector
 156   int rv;
 157   while (reg) {
 158     if((rv = ip_register_adjacency(vm, is_ip4, reg)))
 159       return rv;
 160     reg = reg->next;
 161   }
 162   return 0;
 163 }
 164
 165 /* Create new block of given number of contiguous adjacencies. */
 166 ip_adjacency_t *
 167 ip_add_adjacency (ip_lookup_main_t * lm,
 168                   ip_adjacency_t * copy_adj,
 169                   u32 n_adj,
 170                   u32 * adj_index_return)
 171 {
 172   ip_adjacency_t * adj;
 173   u32 ai, i, handle;
 174
 175   /* See if we know enough to attempt to share an existing adjacency */
 176   if (copy_adj && n_adj == 1)
 177     {
 178       uword signature;
 179       uword * p;
 180
 181       switch (copy_adj->lookup_next_index)
 182         {
 183         case IP_LOOKUP_NEXT_DROP:
 184           if (lm->drop_adj_index)
 185             {
 186               adj = ip_get_adjacency (lm, lm->drop_adj_index);
 187               *adj_index_return = lm->drop_adj_index;
 188               return (adj);
 189             }
 190           break;
 191
 192         case IP_LOOKUP_NEXT_LOCAL:
 193           if (lm->local_adj_index)
 194             {
 195               adj = ip_get_adjacency (lm, lm->local_adj_index);
 196               *adj_index_return = lm->local_adj_index;
 197               return (adj);
 198             }
 199         default:
 200           break;
 201         }
 202
 203       signature = vnet_ip_adjacency_signature (copy_adj);
 204       p = hash_get (lm->adj_index_by_signature, signature);
 205       if (p)
 206         {
 207           adj = vec_elt_at_index (lm->adjacency_heap, p[0]);
 208           while (1)
 209             {
 210               if (vnet_ip_adjacency_share_compare (adj, copy_adj))
 211                 {
 212                   adj->share_count++;
 213                   *adj_index_return = p[0];
 214                   return adj;
 215                 }
 216               if (adj->next_adj_with_signature == 0)
 217                 break;
 218               adj = vec_elt_at_index (lm->adjacency_heap,
 219                                       adj->next_adj_with_signature);
 220             }
 221         }
 222     }
 223
 224   lm->adjacency_heap = aa_alloc (lm->adjacency_heap, &adj, n_adj);
 225   handle = ai = adj->heap_handle;
 226
 227   ip_poison_adjacencies (adj, n_adj);
 228
 229   /* Validate adjacency counters. */
 230   vlib_validate_combined_counter (&lm->adjacency_counters, ai + n_adj - 1);
 231
 232   for (i = 0; i < n_adj; i++)
 233     {
 234       /* Make sure certain fields are always initialized. */
 235       adj[i].rewrite_header.sw_if_index = ~0;
 236       adj[i].explicit_fib_index = ~0;
 237       adj[i].mcast_group_index = ~0;
 238       adj[i].classify.table_index = ~0;
 239       adj[i].saved_lookup_next_index = 0;
 240       adj[i].special_adjacency_format_function_index = 0;
 241
 242       if (copy_adj)
 243         adj[i] = copy_adj[i];
 244
 245       adj[i].heap_handle = handle;
 246       adj[i].n_adj = n_adj;
 247       adj[i].share_count = 0;
 248       adj[i].next_adj_with_signature = 0;
 249
 250       /* Zero possibly stale counters for re-used adjacencies. */
 251       vlib_zero_combined_counter (&lm->adjacency_counters, ai + i);
 252     }
 253
 254   /* Set up to share the adj later */
 255   if (copy_adj && n_adj == 1)
 256     ip_share_adjacency(lm, ai);
 257
 258   *adj_index_return = ai;
 259   return adj;
 260 }
 261
 262 void
 263 ip_update_adjacency (ip_lookup_main_t * lm,
 264                      u32 adj_index,
 265                      ip_adjacency_t * copy_adj)
 266 {
 267   ip_adjacency_t * adj = ip_get_adjacency(lm, adj_index);
 268
 269   ip_call_add_del_adjacency_callbacks (lm, adj_index, /* is_del */ 1);
 270   ip_unshare_adjacency(lm, adj_index);
 271
 272   /* temporary redirect to drop while updating rewrite data */
 273   adj->lookup_next_index = IP_LOOKUP_NEXT_ARP;
 274   CLIB_MEMORY_BARRIER();
 275
 276   clib_memcpy (&adj->rewrite_header, &copy_adj->rewrite_header,
 277                VLIB_BUFFER_PRE_DATA_SIZE);
 278   adj->lookup_next_index = copy_adj->lookup_next_index;
 279   ip_share_adjacency(lm, adj_index);
 280   ip_call_add_del_adjacency_callbacks (lm, adj_index, /* is_del */ 0);
 281 }
 282
 283 static void ip_del_adjacency2 (ip_lookup_main_t * lm, u32 adj_index, u32 delete_multipath_adjacency)
 284 {
 285   ip_adjacency_t * adj;
 286
 287   ip_call_add_del_adjacency_callbacks (lm, adj_index, /* is_del */ 1);
 288
 289   adj = ip_get_adjacency (lm, adj_index);
 290
 291   /* Special-case miss, local, drop adjs */
 292   if (adj_index < 3)
 293       return;
 294
 295   if (adj->n_adj == 1)
 296     {
 297       if (adj->share_count > 0)
 298         {
 299           adj->share_count --;
 300           return;
 301         }
 302
 303       ip_unshare_adjacency(lm, adj_index);
 304     }
 305
 306   if (delete_multipath_adjacency)
 307     ip_multipath_del_adjacency (lm, adj_index);
 308
 309   ip_poison_adjacencies (adj, adj->n_adj);
 310
 311   aa_free (lm->adjacency_heap, adj);
 312 }
 313
 314 void ip_del_adjacency (ip_lookup_main_t * lm, u32 adj_index)
 315 { ip_del_adjacency2 (lm, adj_index, /* delete_multipath_adjacency */ 1); }
 316
 317 static int
 318 next_hop_sort_by_weight (ip_multipath_next_hop_t * n1,
 319                          ip_multipath_next_hop_t * n2)
 320 {
 321   int cmp = (int) n1->weight - (int) n2->weight;
 322   return (cmp == 0
 323           ? (int) n1->next_hop_adj_index - (int) n2->next_hop_adj_index
 324           : (cmp > 0 ? +1 : -1));
 325 }
 326
 327 /* Given next hop vector is over-written with normalized one with sorted weights and
 328    with weights corresponding to the number of adjacencies for each next hop.
 329    Returns number of adjacencies in block. */
 330 static u32 ip_multipath_normalize_next_hops (ip_lookup_main_t * lm,
 331                                              ip_multipath_next_hop_t * raw_next_hops,
 332                                              ip_multipath_next_hop_t ** normalized_next_hops)
 333 {
 334   ip_multipath_next_hop_t * nhs;
 335   uword n_nhs, n_adj, n_adj_left, i;
 336   f64 sum_weight, norm, error;
 337
 338   n_nhs = vec_len (raw_next_hops);
 339   ASSERT (n_nhs > 0);
 340   if (n_nhs == 0)
 341     return 0;
 342
 343   /* Allocate enough space for 2 copies; we'll use second copy to save original weights. */
 344   nhs = *normalized_next_hops;
 345   vec_validate (nhs, 2*n_nhs - 1);
 346
 347   /* Fast path: 1 next hop in block. */
 348   n_adj = n_nhs;
 349   if (n_nhs == 1)
 350     {
 351       nhs[0] = raw_next_hops[0];
 352       nhs[0].weight = 1;
 353       _vec_len (nhs) = 1;
 354       goto done;
 355     }
 356
 357   else if (n_nhs == 2)
 358     {
 359       int cmp = next_hop_sort_by_weight (&raw_next_hops[0], &raw_next_hops[1]) < 0;
 360
 361       /* Fast sort. */
 362       nhs[0] = raw_next_hops[cmp];
 363       nhs[1] = raw_next_hops[cmp ^ 1];
 364
 365       /* Fast path: equal cost multipath with 2 next hops. */
 366       if (nhs[0].weight == nhs[1].weight)
 367         {
 368           nhs[0].weight = nhs[1].weight = 1;
 369           _vec_len (nhs) = 2;
 370           goto done;
 371         }
 372     }
 373   else
 374     {
 375       clib_memcpy (nhs, raw_next_hops, n_nhs * sizeof (raw_next_hops[0]));
 376       qsort (nhs, n_nhs, sizeof (nhs[0]), (void *) next_hop_sort_by_weight);
 377     }
 378
 379   /* Find total weight to normalize weights. */
 380   sum_weight = 0;
 381   for (i = 0; i < n_nhs; i++)
 382     sum_weight += nhs[i].weight;
 383
 384   /* In the unlikely case that all weights are given as 0, set them all to 1. */
 385   if (sum_weight == 0)
 386     {
 387       for (i = 0; i < n_nhs; i++)
 388         nhs[i].weight = 1;
 389       sum_weight = n_nhs;
 390     }
 391
 392   /* Save copies of all next hop weights to avoid being overwritten in loop below. */
 393   for (i = 0; i < n_nhs; i++)
 394     nhs[n_nhs + i].weight = nhs[i].weight;
 395
 396   /* Try larger and larger power of 2 sized adjacency blocks until we
 397      find one where traffic flows to within 1% of specified weights. */
 398   for (n_adj = max_pow2 (n_nhs); ; n_adj *= 2)
 399     {
 400       error = 0;
 401
 402       norm = n_adj / sum_weight;
 403       n_adj_left = n_adj;
 404       for (i = 0; i < n_nhs; i++)
 405         {
 406           f64 nf = nhs[n_nhs + i].weight * norm; /* use saved weights */
 407           word n = flt_round_nearest (nf);
 408
 409           n = n > n_adj_left ? n_adj_left : n;
 410           n_adj_left -= n;
 411           error += fabs (nf - n);
 412           nhs[i].weight = n;
 413         }
 414
 415       nhs[0].weight += n_adj_left;
 416
 417       /* Less than 5% average error per adjacency with this size adjacency block? */
 418       if (error <= lm->multipath_next_hop_error_tolerance*n_adj)
 419         {
 420           /* Truncate any next hops with zero weight. */
 421           _vec_len (nhs) = i;
 422           break;
 423         }
 424     }
 425
 426  done:
 427   /* Save vector for next call. */
 428   *normalized_next_hops = nhs;
 429   return n_adj;
 430 }
 431
 432 always_inline uword
 433 ip_next_hop_hash_key_from_handle (uword handle)
 434 { return 1 + 2*handle; }
 435
 436 always_inline uword
 437 ip_next_hop_hash_key_is_heap_handle (uword k)
 438 { return k & 1; }
 439
 440 always_inline uword
 441 ip_next_hop_hash_key_get_heap_handle (uword k)
 442 {
 443   ASSERT (ip_next_hop_hash_key_is_heap_handle (k));
 444   return k / 2;
 445 }
 446
 447 static u32
 448 ip_multipath_adjacency_get (ip_lookup_main_t * lm,
 449                             ip_multipath_next_hop_t * raw_next_hops,
 450                             uword create_if_non_existent)
 451 {
 452   uword * p;
 453   u32 i, j, n_adj, adj_index, adj_heap_handle;
 454   ip_adjacency_t * adj, * copy_adj;
 455   ip_multipath_next_hop_t * nh, * nhs;
 456   ip_multipath_adjacency_t * madj;
 457
 458   n_adj = ip_multipath_normalize_next_hops (lm, raw_next_hops, &lm->next_hop_hash_lookup_key_normalized);
 459   nhs = lm->next_hop_hash_lookup_key_normalized;
 460
 461   /* Basic sanity. */
 462   ASSERT (n_adj >= vec_len (raw_next_hops));
 463
 464   /* Use normalized next hops to see if we've seen a block equivalent to this one before. */
 465   p = hash_get_mem (lm->multipath_adjacency_by_next_hops, nhs);
 466   if (p)
 467     return p[0];
 468
 469   if (! create_if_non_existent)
 470     return 0;
 471
 472   adj = ip_add_adjacency (lm, /* copy_adj */ 0, n_adj, &adj_index);
 473   adj_heap_handle = adj[0].heap_handle;
 474
 475   /* Fill in adjacencies in block based on corresponding next hop adjacencies. */
 476   i = 0;
 477   vec_foreach (nh, nhs)
 478     {
 479       copy_adj = ip_get_adjacency (lm, nh->next_hop_adj_index);
 480       for (j = 0; j < nh->weight; j++)
 481         {
 482           adj[i] = copy_adj[0];
 483           adj[i].heap_handle = adj_heap_handle;
 484           adj[i].n_adj = n_adj;
 485           i++;
 486         }
 487     }
 488
 489   /* All adjacencies should have been initialized. */
 490   ASSERT (i == n_adj);
 491
 492   vec_validate (lm->multipath_adjacencies, adj_heap_handle);
 493   madj = vec_elt_at_index (lm->multipath_adjacencies, adj_heap_handle);
 494
 495   madj->adj_index = adj_index;
 496   madj->n_adj_in_block = n_adj;
 497   madj->reference_count = 0;    /* caller will set to one. */
 498
 499   madj->normalized_next_hops.count = vec_len (nhs);
 500   madj->normalized_next_hops.heap_offset
 501     = heap_alloc (lm->next_hop_heap, vec_len (nhs),
 502                   madj->normalized_next_hops.heap_handle);
 503   clib_memcpy (lm->next_hop_heap + madj->normalized_next_hops.heap_offset,
 504           nhs, vec_bytes (nhs));
 505
 506   hash_set (lm->multipath_adjacency_by_next_hops,
 507             ip_next_hop_hash_key_from_handle (madj->normalized_next_hops.heap_handle),
 508             madj - lm->multipath_adjacencies);
 509
 510   madj->unnormalized_next_hops.count = vec_len (raw_next_hops);
 511   madj->unnormalized_next_hops.heap_offset
 512     = heap_alloc (lm->next_hop_heap, vec_len (raw_next_hops),
 513                   madj->unnormalized_next_hops.heap_handle);
 514   clib_memcpy (lm->next_hop_heap + madj->unnormalized_next_hops.heap_offset,
 515           raw_next_hops, vec_bytes (raw_next_hops));
 516
 517   ip_call_add_del_adjacency_callbacks (lm, adj_index, /* is_del */ 0);
 518
 519   return adj_heap_handle;
 520 }
 521
 522 /* Returns 0 for next hop not found. */
 523 u32
 524 ip_multipath_adjacency_add_del_next_hop (ip_lookup_main_t * lm,
 525                                          u32 is_del,
 526                                          u32 old_mp_adj_index,
 527                                          u32 next_hop_adj_index,
 528                                          u32 next_hop_weight,
 529                                          u32 * new_mp_adj_index)
 530 {
 531   ip_multipath_adjacency_t * mp_old, * mp_new;
 532   ip_multipath_next_hop_t * nh, * nhs, * hash_nhs;
 533   u32 n_nhs, i_nh;
 534
 535   mp_new = mp_old = 0;
 536   n_nhs = 0;
 537   i_nh = 0;
 538   nhs = 0;
 539
 540   /* If old adj is not multipath, we need to "convert" it by calling this
 541    * function recursively */
 542   if (old_mp_adj_index != ~0 && !ip_adjacency_is_multipath(lm, old_mp_adj_index))
 543     {
 544       ip_multipath_adjacency_add_del_next_hop(lm, /* is_del */ 0,
 545                                               /* old_mp_adj_index */ ~0,
 546                                               /* nh_adj_index */ old_mp_adj_index,
 547                                               /* weight * */ 1,
 548                                               &old_mp_adj_index);
 549     }
 550
 551   /* If old multipath adjacency is valid, find requested next hop. */
 552   if (old_mp_adj_index < vec_len (lm->multipath_adjacencies)
 553       && lm->multipath_adjacencies[old_mp_adj_index].normalized_next_hops.count > 0)
 554     {
 555       mp_old = vec_elt_at_index (lm->multipath_adjacencies, old_mp_adj_index);
 556
 557       nhs = vec_elt_at_index (lm->next_hop_heap, mp_old->unnormalized_next_hops.heap_offset);
 558       n_nhs = mp_old->unnormalized_next_hops.count;
 559
 560       /* Linear search: ok since n_next_hops is small. */
 561       for (i_nh = 0; i_nh < n_nhs; i_nh++)
 562         if (nhs[i_nh].next_hop_adj_index == next_hop_adj_index)
 563           break;
 564
 565       /* Given next hop not found. */
 566       if (i_nh >= n_nhs && is_del)
 567         return 0;
 568     }
 569
 570   hash_nhs = lm->next_hop_hash_lookup_key;
 571   if (hash_nhs)
 572     _vec_len (hash_nhs) = 0;
 573
 574   if (is_del)
 575     {
 576       if (n_nhs > 1)
 577         {
 578           /* Prepare lookup key for multipath with target next hop deleted. */
 579           if (i_nh > 0)
 580             vec_add (hash_nhs, nhs + 0, i_nh);
 581           if (i_nh + 1 < n_nhs)
 582             vec_add (hash_nhs, nhs + i_nh + 1, n_nhs - (i_nh + 1));
 583         }
 584     }
 585   else /* it's an add. */
 586     {
 587       /* If next hop is already there with the same weight, we have nothing to do. */
 588       if (i_nh < n_nhs && nhs[i_nh].weight == next_hop_weight)
 589         {
 590           new_mp_adj_index[0] = ~0;
 591           goto done;
 592         }
 593
 594       /* Copy old next hops to lookup key vector. */
 595       if (n_nhs > 0)
 596         vec_add (hash_nhs, nhs, n_nhs);
 597
 598       if (i_nh < n_nhs)
 599         {
 600           /* Change weight of existing next hop. */
 601           nh = vec_elt_at_index (hash_nhs, i_nh);
 602         }
 603       else
 604         {
 605           /* Add a new next hop. */
 606           vec_add2 (hash_nhs, nh, 1);
 607           nh->next_hop_adj_index = next_hop_adj_index;
 608         }
 609
 610       /* Set weight for added or old next hop. */
 611       nh->weight = next_hop_weight;
 612     }
 613
 614   if (vec_len (hash_nhs) > 0)
 615     {
 616       u32 tmp = ip_multipath_adjacency_get (lm, hash_nhs,
 617                                             /* create_if_non_existent */ 1);
 618       if (tmp != ~0)
 619         mp_new = vec_elt_at_index (lm->multipath_adjacencies, tmp);
 620
 621       /* Fetch again since pool may have moved. */
 622       if (mp_old)
 623         mp_old = vec_elt_at_index (lm->multipath_adjacencies, old_mp_adj_index);
 624     }
 625
 626   new_mp_adj_index[0] = mp_new ? mp_new - lm->multipath_adjacencies : ~0;
 627
 628   if (mp_new != mp_old)
 629     {
 630       if (mp_old)
 631         {
 632           ASSERT (mp_old->reference_count > 0);
 633           mp_old->reference_count -= 1;
 634         }
 635       if (mp_new)
 636         mp_new->reference_count += 1;
 637     }
 638
 639   if (mp_old && mp_old->reference_count == 0)
 640     ip_multipath_adjacency_free (lm, mp_old);
 641
 642  done:
 643   /* Save key vector next call. */
 644   lm->next_hop_hash_lookup_key = hash_nhs;
 645
 646   return 1;
 647 }
 648
 649 static void
 650 ip_multipath_del_adjacency (ip_lookup_main_t * lm, u32 del_adj_index)
 651 {
 652   ip_adjacency_t * adj = ip_get_adjacency (lm, del_adj_index);
 653   ip_multipath_adjacency_t * madj, * new_madj;
 654   ip_multipath_next_hop_t * nhs, * hash_nhs;
 655   u32 i, n_nhs, madj_index, new_madj_index;
 656
 657   if (adj->heap_handle >= vec_len (lm->multipath_adjacencies))
 658     return;
 659
 660   vec_validate (lm->adjacency_remap_table, vec_len (lm->adjacency_heap) - 1);
 661
 662   for (madj_index = 0; madj_index < vec_len (lm->multipath_adjacencies); madj_index++)
 663     {
 664       madj = vec_elt_at_index (lm->multipath_adjacencies, madj_index);
 665       if (madj->n_adj_in_block == 0)
 666         continue;
 667
 668       nhs = heap_elt_at_index (lm->next_hop_heap, madj->unnormalized_next_hops.heap_offset);
 669       n_nhs = madj->unnormalized_next_hops.count;
 670       for (i = 0; i < n_nhs; i++)
 671         if (nhs[i].next_hop_adj_index == del_adj_index)
 672           break;
 673
 674       /* del_adj_index not found in unnormalized_next_hops?  We're done. */
 675       if (i >= n_nhs)
 676         continue;
 677
 678       new_madj = 0;
 679       if (n_nhs > 1)
 680         {
 681           hash_nhs = lm->next_hop_hash_lookup_key;
 682           if (hash_nhs)
 683             _vec_len (hash_nhs) = 0;
 684           if (i > 0)
 685             vec_add (hash_nhs, nhs + 0, i);
 686           if (i + 1 < n_nhs)
 687             vec_add (hash_nhs, nhs + i + 1, n_nhs - (i + 1));
 688
 689           new_madj_index = ip_multipath_adjacency_get (lm, hash_nhs, /* create_if_non_existent */ 1);
 690
 691           lm->next_hop_hash_lookup_key = hash_nhs;
 692
 693           if (new_madj_index == madj_index)
 694             continue;
 695
 696           new_madj = vec_elt_at_index (lm->multipath_adjacencies, new_madj_index);
 697         }
 698
 699       lm->adjacency_remap_table[madj->adj_index] = new_madj ? 1 + new_madj->adj_index : ~0;
 700       lm->n_adjacency_remaps += 1;
 701       ip_multipath_adjacency_free (lm, madj);
 702     }
 703 }
 704
 705 void
 706 ip_multipath_adjacency_free (ip_lookup_main_t * lm,
 707                              ip_multipath_adjacency_t * a)
 708 {
 709   hash_unset (lm->multipath_adjacency_by_next_hops,
 710               ip_next_hop_hash_key_from_handle (a->normalized_next_hops.heap_handle));
 711   heap_dealloc (lm->next_hop_heap, a->normalized_next_hops.heap_handle);
 712   heap_dealloc (lm->next_hop_heap, a->unnormalized_next_hops.heap_handle);
 713
 714   ip_del_adjacency2 (lm, a->adj_index, a->reference_count == 0);
 715   memset (a, 0, sizeof (a[0]));
 716 }
 717
 718 always_inline ip_multipath_next_hop_t *
 719 ip_next_hop_hash_key_get_next_hops (ip_lookup_main_t * lm, uword k,
 720                                     uword * n_next_hops)
 721 {
 722   ip_multipath_next_hop_t * nhs;
 723   uword n_nhs;
 724   if (ip_next_hop_hash_key_is_heap_handle (k))
 725     {
 726       uword handle = ip_next_hop_hash_key_get_heap_handle (k);
 727       nhs = heap_elt_with_handle (lm->next_hop_heap, handle);
 728       n_nhs = heap_len (lm->next_hop_heap, handle);
 729     }
 730   else
 731     {
 732       nhs = uword_to_pointer (k, ip_multipath_next_hop_t *);
 733       n_nhs = vec_len (nhs);
 734     }
 735   *n_next_hops = n_nhs;
 736   return nhs;
 737 }
 738
 739 static uword
 740 ip_next_hop_hash_key_sum (hash_t * h, uword key0)
 741 {
 742   ip_lookup_main_t * lm = uword_to_pointer (h->user, ip_lookup_main_t *);
 743   ip_multipath_next_hop_t * k0;
 744   uword n0;
 745
 746   k0 = ip_next_hop_hash_key_get_next_hops (lm, key0, &n0);
 747   return hash_memory (k0, n0 * sizeof (k0[0]), /* seed */ n0);
 748 }
 749
 750 static uword
 751 ip_next_hop_hash_key_equal (hash_t * h, uword key0, uword key1)
 752 {
 753   ip_lookup_main_t * lm = uword_to_pointer (h->user, ip_lookup_main_t *);
 754   ip_multipath_next_hop_t * k0, * k1;
 755   uword n0, n1;
 756
 757   k0 = ip_next_hop_hash_key_get_next_hops (lm, key0, &n0);
 758   k1 = ip_next_hop_hash_key_get_next_hops (lm, key1, &n1);
 759
 760   return n0 == n1 && ! memcmp (k0, k1, n0 * sizeof (k0[0]));
 761 }
 762
 763 clib_error_t *
 764 ip_interface_address_add_del (ip_lookup_main_t * lm,
 765                               u32 sw_if_index,
 766                               void * addr_fib,
 767                               u32 address_length,
 768                               u32 is_del,
 769                               u32 * result_if_address_index)
 770 {
 771   vnet_main_t * vnm = vnet_get_main();
 772   ip_interface_address_t * a, * prev, * next;
 773   uword * p = mhash_get (&lm->address_to_if_address_index, addr_fib);
 774
 775   vec_validate_init_empty (lm->if_address_pool_index_by_sw_if_index, sw_if_index, ~0);
 776   a = p ? pool_elt_at_index (lm->if_address_pool, p[0]) : 0;
 777
 778   /* Verify given length. */
 779   if ((a && (address_length != a->address_length)) || (address_length == 0))
 780     {
 781       vnm->api_errno = VNET_API_ERROR_ADDRESS_LENGTH_MISMATCH;
 782       return clib_error_create
 783         ( "%U wrong length (expected %d) for interface %U",
 784           lm->format_address_and_length, addr_fib,
 785           address_length, a? a->address_length : -1,
 786           format_vnet_sw_if_index_name, vnm, sw_if_index);
 787     }
 788
 789   if (is_del)
 790     {
 791       if (!a)
 792         {
 793           vnet_sw_interface_t * si = vnet_get_sw_interface (vnm, sw_if_index);
 794           vnm->api_errno = VNET_API_ERROR_ADDRESS_NOT_FOUND_FOR_INTERFACE;
 795           return clib_error_create ("%U not found for interface %U",
 796                                     lm->format_address_and_length,
 797                                     addr_fib, address_length,
 798                                     format_vnet_sw_interface_name, vnm, si);
 799         }
 800
 801       if (a->prev_this_sw_interface != ~0)
 802         {
 803           prev = pool_elt_at_index (lm->if_address_pool, a->prev_this_sw_interface);
 804           prev->next_this_sw_interface = a->next_this_sw_interface;
 805         }
 806       if (a->next_this_sw_interface != ~0)
 807         {
 808           next = pool_elt_at_index (lm->if_address_pool, a->next_this_sw_interface);
 809           next->prev_this_sw_interface = a->prev_this_sw_interface;
 810
 811           if(a->prev_this_sw_interface == ~0)
 812                  lm->if_address_pool_index_by_sw_if_index[sw_if_index]  = a->next_this_sw_interface;
 813         }
 814
 815       if ((a->next_this_sw_interface  == ~0) &&  (a->prev_this_sw_interface == ~0))
 816         lm->if_address_pool_index_by_sw_if_index[sw_if_index] = ~0;
 817
 818       mhash_unset (&lm->address_to_if_address_index, addr_fib,
 819                    /* old_value */ 0);
 820       pool_put (lm->if_address_pool, a);
 821
 822       if (result_if_address_index)
 823         *result_if_address_index = ~0;
 824     }
 825
 826   else if (! a)
 827     {
 828       u32 pi; /* previous index */
 829       u32 ai;
 830       u32 hi; /* head index */
 831
 832       pool_get (lm->if_address_pool, a);
 833       memset (a, ~0, sizeof (a[0]));
 834       ai = a - lm->if_address_pool;
 835
 836       hi = pi = lm->if_address_pool_index_by_sw_if_index[sw_if_index];
 837       prev = 0;
 838       while (pi != (u32)~0)
 839         {
 840           prev = pool_elt_at_index(lm->if_address_pool, pi);
 841           pi = prev->next_this_sw_interface;
 842         }
 843       pi = prev ? prev - lm->if_address_pool : (u32)~0;
 844
 845       a->address_key = mhash_set (&lm->address_to_if_address_index,
 846                                   addr_fib, ai, /* old_value */ 0);
 847       a->address_length = address_length;
 848       a->sw_if_index = sw_if_index;
 849       a->flags = 0;
 850       a->prev_this_sw_interface = pi;
 851       a->next_this_sw_interface = ~0;
 852       if (prev)
 853           prev->next_this_sw_interface = ai;
 854
 855       lm->if_address_pool_index_by_sw_if_index[sw_if_index] =
 856         (hi != ~0) ? hi : ai;
 857       if (result_if_address_index)
 858         *result_if_address_index = ai;
 859     }
 860   else
 861     {
 862       if (result_if_address_index)
 863         *result_if_address_index = a - lm->if_address_pool;
 864     }
 865
 866
 867   return /* no error */ 0;
 868 }
 869
 870 void ip_lookup_init (ip_lookup_main_t * lm, u32 is_ip6)
 871 {
 872   ip_adjacency_t * adj;
 873   ip_adjacency_t template_adj;
 874
 875   /* ensure that adjacency is cacheline aligned and sized */
 876   ASSERT(STRUCT_OFFSET_OF(ip_adjacency_t, cacheline0) == 0);
 877   ASSERT(STRUCT_OFFSET_OF(ip_adjacency_t, cacheline1) == CLIB_CACHE_LINE_BYTES);
 878
 879   lm->adj_index_by_signature = hash_create (0, sizeof (uword));
 880   memset (&template_adj, 0, sizeof (template_adj));
 881
 882   /* Preallocate three "special" adjacencies */
 883   lm->adjacency_heap = aa_bootstrap (0, 3 /* n=1 free items */);
 884
 885   /* Hand-craft special miss adjacency to use when nothing matches in the
 886      routing table.  Same for drop adjacency. */
 887   adj = ip_add_adjacency (lm, /* template */ 0, /* n-adj */ 1,
 888                           &lm->miss_adj_index);
 889   adj->lookup_next_index = IP_LOOKUP_NEXT_MISS;
 890   ASSERT (lm->miss_adj_index == IP_LOOKUP_MISS_ADJ_INDEX);
 891
 892   /* Make the "drop" adj sharable */
 893   template_adj.lookup_next_index = IP_LOOKUP_NEXT_DROP;
 894   adj = ip_add_adjacency (lm, &template_adj, /* n-adj */ 1,
 895                           &lm->drop_adj_index);
 896
 897   /* Make the "local" adj sharable */
 898   template_adj.lookup_next_index = IP_LOOKUP_NEXT_LOCAL;
 899   template_adj.if_address_index = ~0;
 900   adj = ip_add_adjacency (lm, &template_adj, /* n-adj */ 1,
 901                           &lm->local_adj_index);
 902
 903   if (! lm->fib_result_n_bytes)
 904     lm->fib_result_n_bytes = sizeof (uword);
 905
 906   lm->multipath_adjacency_by_next_hops
 907     = hash_create2 (/* elts */ 0,
 908                     /* user */ pointer_to_uword (lm),
 909                     /* value_bytes */ sizeof (uword),
 910                     ip_next_hop_hash_key_sum,
 911                     ip_next_hop_hash_key_equal,
 912                     /* format pair/arg */
 913                     0, 0);
 914
 915   /* 1% max error tolerance for multipath. */
 916   lm->multipath_next_hop_error_tolerance = .01;
 917
 918   lm->is_ip6 = is_ip6;
 919   if (is_ip6)
 920     {
 921       lm->format_address_and_length = format_ip6_address_and_length;
 922       mhash_init (&lm->address_to_if_address_index, sizeof (uword),
 923                   sizeof (ip6_address_fib_t));
 924     }
 925   else
 926     {
 927       lm->format_address_and_length = format_ip4_address_and_length;
 928       mhash_init (&lm->address_to_if_address_index, sizeof (uword),
 929                   sizeof (ip4_address_fib_t));
 930     }
 931
 932   {
 933     int i;
 934
 935     /* Setup all IP protocols to be punted and builtin-unknown. */
 936     for (i = 0; i < 256; i++)
 937       {
 938         lm->local_next_by_ip_protocol[i] = IP_LOCAL_NEXT_PUNT;
 939         lm->builtin_protocol_by_ip_protocol[i] = IP_BUILTIN_PROTOCOL_UNKNOWN;
 940       }
 941
 942     lm->local_next_by_ip_protocol[IP_PROTOCOL_UDP] = IP_LOCAL_NEXT_UDP_LOOKUP;
 943     lm->local_next_by_ip_protocol[is_ip6 ? IP_PROTOCOL_ICMP6 : IP_PROTOCOL_ICMP] = IP_LOCAL_NEXT_ICMP;
 944     lm->builtin_protocol_by_ip_protocol[IP_PROTOCOL_UDP] = IP_BUILTIN_PROTOCOL_UDP;
 945     lm->builtin_protocol_by_ip_protocol[is_ip6 ? IP_PROTOCOL_ICMP6 : IP_PROTOCOL_ICMP] = IP_BUILTIN_PROTOCOL_ICMP;
 946   }
 947
 948   ip_init_registered_adjacencies(!is_ip6);
 949 }
 950
 951 u8 * format_ip_flow_hash_config (u8 * s, va_list * args)
 952 {
 953   u32 flow_hash_config = va_arg (*args, u32);
 954
 955 #define _(n,v) if (flow_hash_config & v) s = format (s, "%s ", #n);
 956   foreach_flow_hash_bit;
 957 #undef _
 958
 959   return s;
 960 }
 961
 962 u8 * format_ip_lookup_next (u8 * s, va_list * args)
 963 {
 964   ip_lookup_main_t * lm = va_arg (*args, ip_lookup_main_t *);
 965   ip_lookup_next_t n = va_arg (*args, u32);
 966   ip_adj_register_t *reg;
 967
 968   char * t = 0;
 969
 970   switch (n)
 971     {
 972     default:
 973       vec_validate(lm->registered_adjacencies, n);
 974       reg = vec_elt_at_index(lm->registered_adjacencies, n);
 975       if (reg->node_name) {
 976         s = format (s, "%s:", reg->node_name);
 977       }
 978       return s;
 979
 980     case IP_LOOKUP_NEXT_MISS: t = "miss"; break;
 981     case IP_LOOKUP_NEXT_DROP: t = "drop"; break;
 982     case IP_LOOKUP_NEXT_PUNT: t = "punt"; break;
 983     case IP_LOOKUP_NEXT_LOCAL: t = "local"; break;
 984     case IP_LOOKUP_NEXT_ARP: t = "arp"; break;
 985     case IP_LOOKUP_NEXT_CLASSIFY: t = "classify"; break;
 986     case IP_LOOKUP_NEXT_MAP: t = "map"; break;
 987     case IP_LOOKUP_NEXT_MAP_T: t = "map-t"; break;
 988     case IP_LOOKUP_NEXT_INDIRECT: t="indirect"; break;
 989     case IP_LOOKUP_NEXT_REWRITE:
 990       break;
 991     }
 992
 993   if (t)
 994     vec_add (s, t, strlen (t));
 995
 996   return s;
 997 }
 998
 999 static u8 * format_ip_interface_address (u8 * s, va_list * args)
1000 {
1001   ip_lookup_main_t * lm = va_arg (*args, ip_lookup_main_t *);
1002   u32 if_address_index = va_arg (*args, u32);
1003   ip_interface_address_t * ia = pool_elt_at_index (lm->if_address_pool, if_address_index);
1004   void * a = ip_interface_address_get_address (lm, ia);
1005
1006   if (lm->is_ip6)
1007     return format (s, "%U", format_ip6_address_and_length, a, ia->address_length);
1008   else
1009     return format (s, "%U", format_ip4_address_and_length, a, ia->address_length);
1010 }
1011
1012 u32 vnet_register_special_adjacency_format_function
1013 (ip_lookup_main_t * lm, format_function_t * fp)
1014 {
1015     u32 rv;
1016     /*
1017      * Initialize the format function registration vector
1018      * Index 0 must be invalid, to avoid finding and fixing trivial bugs
1019      * all over the place
1020      */
1021     if (vec_len (lm->special_adjacency_format_functions) == 0)
1022       {
1023         vec_add1 (lm->special_adjacency_format_functions,
1024                   (format_function_t *) 0);
1025       }
1026
1027     rv = vec_len (lm->special_adjacency_format_functions);
1028     vec_add1 (lm->special_adjacency_format_functions, fp);
1029     return rv;
1030 }
1031
1032 /** @brief Pretty print helper function for formatting specific adjacencies.
1033     @param s - input string to format
1034     @param args - other args passed to format function such as:
1035                   - vnet_main_t
1036                   - ip_lookup_main_t
1037                   - adj_index
1038 */
1039 u8 * format_ip_adjacency (u8 * s, va_list * args)
1040 {
1041   vnet_main_t * vnm = va_arg (*args, vnet_main_t *);
1042   ip_lookup_main_t * lm = va_arg (*args, ip_lookup_main_t *);
1043   u32 adj_index = va_arg (*args, u32);
1044   ip_adjacency_t * adj = ip_get_adjacency (lm, adj_index);
1045   ip_adj_register_t *reg;
1046
1047   if (adj->lookup_next_index < vec_len (lm->registered_adjacencies))
1048     {
1049       reg = vec_elt_at_index(lm->registered_adjacencies,
1050                              adj->lookup_next_index);
1051       if (reg->fn)
1052         {
1053           s = format(s, " %U", reg->fn, lm, adj);
1054           goto format_done;
1055         }
1056     }
1057
1058   switch (adj->lookup_next_index)
1059     {
1060     case IP_LOOKUP_NEXT_REWRITE:
1061       s = format (s, "%U",
1062                   format_vnet_rewrite,
1063                   vnm->vlib_main, &adj->rewrite_header,
1064                   sizeof (adj->rewrite_data));
1065       break;
1066
1067     case IP_LOOKUP_NEXT_ARP:
1068       if (adj->if_address_index != ~0)
1069         s = format (s, " %U", format_ip_interface_address, lm,
1070                     adj->if_address_index);
1071       if (adj->arp.next_hop.ip6.as_u64[0] || adj->arp.next_hop.ip6.as_u64[1])
1072         s = format (s, " via %U", format_ip46_address,
1073                     &adj->arp.next_hop, IP46_TYPE_ANY);
1074       break;
1075     case IP_LOOKUP_NEXT_LOCAL:
1076       if (adj->if_address_index != ~0)
1077         s = format (s, " %U", format_ip_interface_address, lm,
1078                     adj->if_address_index);
1079       break;
1080
1081     case IP_LOOKUP_NEXT_CLASSIFY:
1082       s = format (s, " table %d", adj->classify.table_index);
1083       break;
1084     case IP_LOOKUP_NEXT_INDIRECT:
1085       s = format (s, " via %U", format_ip46_address,
1086                   &adj->indirect.next_hop, IP46_TYPE_ANY);
1087       break;
1088
1089     default:
1090       s = format (s, " unknown %d", adj->lookup_next_index);
1091       break;
1092     }
1093
1094  format_done:
1095   if (adj->explicit_fib_index != ~0 && adj->explicit_fib_index != 0)
1096     s = format (s, " lookup fib index %d", adj->explicit_fib_index);
1097   if (adj->share_count > 0)
1098     s = format (s, " shared %d", adj->share_count + 1);
1099   if (adj->next_adj_with_signature)
1100     s = format (s, " next_adj_with_signature %d", adj->next_adj_with_signature);
1101
1102   return s;
1103 }
1104
1105 u8 * format_ip_adjacency_packet_data (u8 * s, va_list * args)
1106 {
1107   vnet_main_t * vnm = va_arg (*args, vnet_main_t *);
1108   ip_lookup_main_t * lm = va_arg (*args, ip_lookup_main_t *);
1109   u32 adj_index = va_arg (*args, u32);
1110   u8 * packet_data = va_arg (*args, u8 *);
1111   u32 n_packet_data_bytes = va_arg (*args, u32);
1112   ip_adjacency_t * adj = ip_get_adjacency (lm, adj_index);
1113
1114   switch (adj->lookup_next_index)
1115     {
1116     case IP_LOOKUP_NEXT_REWRITE:
1117       s = format (s, "%U",
1118                   format_vnet_rewrite_header,
1119                   vnm->vlib_main, &adj->rewrite_header, packet_data, n_packet_data_bytes);
1120       break;
1121
1122     default:
1123       break;
1124     }
1125
1126   return s;
1127 }
1128
1129 static uword unformat_ip_lookup_next (unformat_input_t * input, va_list * args)
1130 {
1131   ip_lookup_next_t * result = va_arg (*args, ip_lookup_next_t *);
1132   ip_lookup_next_t n;
1133
1134   if (unformat (input, "drop"))
1135     n = IP_LOOKUP_NEXT_DROP;
1136
1137   else if (unformat (input, "punt"))
1138     n = IP_LOOKUP_NEXT_PUNT;
1139
1140   else if (unformat (input, "local"))
1141     n = IP_LOOKUP_NEXT_LOCAL;
1142
1143   else if (unformat (input, "arp"))
1144     n = IP_LOOKUP_NEXT_ARP;
1145
1146   else if (unformat (input, "classify"))
1147     n = IP_LOOKUP_NEXT_CLASSIFY;
1148
1149   else
1150     return 0;
1151
1152   *result = n;
1153   return 1;
1154 }
1155
1156 static uword unformat_ip_adjacency (unformat_input_t * input, va_list * args)
1157 {
1158   vlib_main_t * vm = va_arg (*args, vlib_main_t *);
1159   ip_adjacency_t * adj = va_arg (*args, ip_adjacency_t *);
1160   u32 node_index = va_arg (*args, u32);
1161   vnet_main_t * vnm = vnet_get_main();
1162   u32 sw_if_index, is_ip6;
1163   ip46_address_t a46;
1164   ip_lookup_next_t next;
1165
1166   is_ip6 = node_index == ip6_rewrite_node.index;
1167   adj->rewrite_header.node_index = node_index;
1168   adj->explicit_fib_index = ~0;
1169
1170   if (unformat (input, "arp %U %U",
1171                 unformat_vnet_sw_interface, vnm, &sw_if_index,
1172                 unformat_ip46_address, &a46, is_ip6?IP46_TYPE_IP6:IP46_TYPE_IP4))
1173     {
1174       ip_lookup_main_t * lm = is_ip6 ? &ip6_main.lookup_main : &ip4_main.lookup_main;
1175       ip_adjacency_t * a_adj;
1176       u32 adj_index;
1177
1178       if (is_ip6)
1179         adj_index = ip6_fib_lookup (&ip6_main, sw_if_index, &a46.ip6);
1180       else
1181         adj_index = ip4_fib_lookup (&ip4_main, sw_if_index, &a46.ip4);
1182
1183       a_adj = ip_get_adjacency (lm, adj_index);
1184
1185       if (a_adj->rewrite_header.sw_if_index != sw_if_index)
1186         return 0;
1187
1188       if (is_ip6)
1189         ip6_adjacency_set_interface_route (vnm, adj, sw_if_index, a_adj->if_address_index);
1190       else
1191         ip4_adjacency_set_interface_route (vnm, adj, sw_if_index, a_adj->if_address_index);
1192     }
1193
1194   else if (unformat_user (input, unformat_ip_lookup_next, &next))
1195     {
1196       adj->lookup_next_index = next;
1197       adj->if_address_index = ~0;
1198       if (next == IP_LOOKUP_NEXT_LOCAL)
1199         (void) unformat (input, "%d", &adj->if_address_index);
1200       else if (next == IP_LOOKUP_NEXT_CLASSIFY)
1201         {
1202           if (!unformat (input, "%d", &adj->classify.table_index))
1203             {
1204               clib_warning ("classify adj must specify table index");
1205               return 0;
1206             }
1207         }
1208       else if (next == IP_LOOKUP_NEXT_DROP)
1209         {
1210           adj->rewrite_header.node_index = 0;
1211         }
1212     }
1213
1214   else if (unformat_user (input,
1215                           unformat_vnet_rewrite,
1216                           vm, &adj->rewrite_header, sizeof (adj->rewrite_data)))
1217     adj->lookup_next_index = IP_LOOKUP_NEXT_REWRITE;
1218
1219   else
1220     return 0;
1221
1222   return 1;
1223 }
1224
1225 clib_error_t *
1226 vnet_ip_route_cmd (vlib_main_t * vm, unformat_input_t * main_input, vlib_cli_command_t * cmd)
1227 {
1228   vnet_main_t * vnm = vnet_get_main();
1229   clib_error_t * error = 0;
1230   u32 table_id, is_del;
1231   u32 weight, * weights = 0;
1232   u32 * table_ids = 0;
1233   u32 sw_if_index, * sw_if_indices = 0;
1234   ip4_address_t ip4_addr, * ip4_dst_addresses = 0, * ip4_via_next_hops = 0;
1235   ip6_address_t ip6_addr, * ip6_dst_addresses = 0, * ip6_via_next_hops = 0;
1236   u32 dst_address_length, * dst_address_lengths = 0;
1237   ip_adjacency_t parse_adj, * add_adj = 0;
1238   unformat_input_t _line_input, * line_input = &_line_input;
1239   f64 count;
1240   u32 outer_table_id;
1241
1242   is_del = 0;
1243   table_id = 0;
1244   count = 1;
1245
1246   /* Get a line of input. */
1247   if (! unformat_user (main_input, unformat_line_input, line_input))
1248     return 0;
1249
1250   memset(&parse_adj, 0, sizeof (parse_adj));
1251
1252   while (unformat_check_input (line_input) != UNFORMAT_END_OF_INPUT)
1253     {
1254       if (unformat (line_input, "table %d", &table_id))
1255         ;
1256       else if (unformat (line_input, "del"))
1257         is_del = 1;
1258       else if (unformat (line_input, "add"))
1259         is_del = 0;
1260       else if (unformat (line_input, "count %f", &count))
1261         ;
1262
1263       else if (unformat (line_input, "%U/%d",
1264                          unformat_ip4_address, &ip4_addr,
1265                          &dst_address_length))
1266         {
1267           vec_add1 (ip4_dst_addresses, ip4_addr);
1268           vec_add1 (dst_address_lengths, dst_address_length);
1269         }
1270
1271       else if (unformat (line_input, "%U/%d",
1272                          unformat_ip6_address, &ip6_addr,
1273                          &dst_address_length))
1274         {
1275           vec_add1 (ip6_dst_addresses, ip6_addr);
1276           vec_add1 (dst_address_lengths, dst_address_length);
1277         }
1278
1279       else if (unformat (line_input, "via %U %U weight %u",
1280                          unformat_ip4_address, &ip4_addr,
1281                          unformat_vnet_sw_interface, vnm, &sw_if_index,
1282                          &weight))
1283         {
1284           vec_add1 (ip4_via_next_hops, ip4_addr);
1285           vec_add1 (sw_if_indices, sw_if_index);
1286           vec_add1 (weights, weight);
1287           vec_add1 (table_ids, (u32)~0);
1288         }
1289
1290       else if (unformat (line_input, "via %U %U weight %u",
1291                          unformat_ip6_address, &ip6_addr,
1292                          unformat_vnet_sw_interface, vnm, &sw_if_index,
1293                          &weight))
1294         {
1295           vec_add1 (ip6_via_next_hops, ip6_addr);
1296           vec_add1 (sw_if_indices, sw_if_index);
1297           vec_add1 (weights, weight);
1298           vec_add1 (table_ids, (u32)~0);
1299         }
1300
1301       else if (unformat (line_input, "via %U %U",
1302                          unformat_ip4_address, &ip4_addr,
1303                          unformat_vnet_sw_interface, vnm, &sw_if_index))
1304         {
1305           vec_add1 (ip4_via_next_hops, ip4_addr);
1306           vec_add1 (sw_if_indices, sw_if_index);
1307           vec_add1 (weights, 1);
1308           vec_add1 (table_ids, (u32)~0);
1309         }
1310
1311       else if (unformat (line_input, "via %U %U",
1312                          unformat_ip6_address, &ip6_addr,
1313                          unformat_vnet_sw_interface, vnm, &sw_if_index))
1314         {
1315           vec_add1 (ip6_via_next_hops, ip6_addr);
1316           vec_add1 (sw_if_indices, sw_if_index);
1317           vec_add1 (weights, 1);
1318           vec_add1 (table_ids, (u32)~0);
1319         }
1320       else if (unformat (line_input, "via %U",
1321                          unformat_ip4_address, &ip4_addr))
1322         {
1323           vec_add1 (ip4_via_next_hops, ip4_addr);
1324           vec_add1 (sw_if_indices, (u32)~0);
1325           vec_add1 (weights, 1);
1326           vec_add1 (table_ids, table_id);
1327         }
1328       else if (unformat (line_input, "via %U",
1329                          unformat_ip6_address, &ip6_addr))
1330         {
1331           vec_add1 (ip6_via_next_hops, ip6_addr);
1332           vec_add1 (sw_if_indices, (u32)~0);
1333           vec_add1 (weights, 1);
1334           vec_add1 (table_ids, (u32)table_id);
1335         }
1336
1337       else if (vec_len (ip4_dst_addresses) > 0
1338                && unformat (line_input, "via %U",
1339                             unformat_ip_adjacency, vm, &parse_adj, ip4_rewrite_node.index))
1340           vec_add1 (add_adj, parse_adj);
1341
1342       else if (vec_len (ip6_dst_addresses) > 0
1343                && unformat (line_input, "via %U",
1344                             unformat_ip_adjacency, vm, &parse_adj, ip6_rewrite_node.index))
1345         vec_add1 (add_adj, parse_adj);
1346       else if (unformat (line_input, "lookup in table %d", &outer_table_id))
1347         {
1348           uword * p;
1349
1350           if (vec_len (ip4_dst_addresses) > 0)
1351             p = hash_get (ip4_main.fib_index_by_table_id, outer_table_id);
1352           else
1353             p = hash_get (ip6_main.fib_index_by_table_id, outer_table_id);
1354
1355           if (p == 0)
1356             {
1357               error = clib_error_return (0, "Nonexistent outer table id %d",
1358                                          outer_table_id);
1359               goto done;
1360             }
1361
1362           parse_adj.lookup_next_index = IP_LOOKUP_NEXT_LOCAL;
1363           parse_adj.explicit_fib_index = p[0];
1364           vec_add1 (add_adj, parse_adj);
1365         }
1366       else
1367         {
1368           error = unformat_parse_error (line_input);
1369           goto done;
1370         }
1371     }
1372
1373   unformat_free (line_input);
1374
1375   if (vec_len (ip4_dst_addresses) + vec_len (ip6_dst_addresses) == 0)
1376     {
1377       error = clib_error_return (0, "expected ip4/ip6 destination address/length.");
1378       goto done;
1379     }
1380
1381   if (vec_len (ip4_dst_addresses) > 0 && vec_len (ip6_dst_addresses) > 0)
1382     {
1383       error = clib_error_return (0, "mixed ip4/ip6 address/length.");
1384       goto done;
1385     }
1386
1387   if (vec_len (ip4_dst_addresses) > 0 && vec_len (ip6_via_next_hops) > 0)
1388     {
1389       error = clib_error_return (0, "ip4 destinations with ip6 next hops.");
1390       goto done;
1391     }
1392
1393   if (vec_len (ip6_dst_addresses) > 0 && vec_len (ip4_via_next_hops) > 0)
1394     {
1395       error = clib_error_return (0, "ip6 destinations with ip4 next hops.");
1396       goto done;
1397     }
1398
1399   if (! is_del && vec_len (add_adj) + vec_len (weights) == 0)
1400     {
1401       error = clib_error_return (0, "no next hops or adjacencies to add.");
1402       goto done;
1403     }
1404
1405   {
1406     int i;
1407     ip4_main_t * im4 = &ip4_main;
1408     ip6_main_t * im6 = &ip6_main;
1409
1410     for (i = 0; i < vec_len (ip4_dst_addresses); i++)
1411       {
1412         ip4_add_del_route_args_t a;
1413
1414         memset (&a, 0, sizeof (a));
1415         a.flags = IP4_ROUTE_FLAG_TABLE_ID;
1416         a.table_index_or_table_id = table_id;
1417         a.dst_address = ip4_dst_addresses[i];
1418         a.dst_address_length = dst_address_lengths[i];
1419         a.adj_index = ~0;
1420
1421         if (is_del)
1422           {
1423             if (vec_len (ip4_via_next_hops) == 0)
1424               {
1425                 uword * dst_hash, * dst_result;
1426                 u32 dst_address_u32;
1427                 ip4_fib_t * fib;
1428
1429                 fib = find_ip4_fib_by_table_index_or_id (im4, table_id,
1430                                                          0 /* by table id */);
1431
1432                 a.flags |= IP4_ROUTE_FLAG_DEL;
1433                 dst_address_u32 = a.dst_address.as_u32
1434                   & im4->fib_masks[a.dst_address_length];
1435
1436                 dst_hash =
1437                   fib->adj_index_by_dst_address[a.dst_address_length];
1438                 dst_result = hash_get (dst_hash, dst_address_u32);
1439                 if (dst_result)
1440                   a.adj_index = dst_result[0];
1441                 else
1442                   {
1443                     clib_warning ("%U/%d not in FIB",
1444                                   format_ip4_address, &a.dst_address,
1445                                   a.dst_address_length);
1446                     continue;
1447                   }
1448
1449                 ip4_add_del_route (im4, &a);
1450                 ip4_maybe_remap_adjacencies (im4, table_id,
1451                                              IP4_ROUTE_FLAG_TABLE_ID);
1452               }
1453             else
1454               {
1455                 u32 i, j, n, f, incr;
1456                 ip4_address_t dst = a.dst_address;
1457                 f64 t[2];
1458                 n = count;
1459                 t[0] = vlib_time_now (vm);
1460                 incr = 1<<(32 - a.dst_address_length);
1461                 for (i = 0; i < n; i++)
1462                   {
1463                     f = i + 1 < n ? IP4_ROUTE_FLAG_NOT_LAST_IN_GROUP : 0;
1464                     a.dst_address = dst;
1465                     for (j = 0; j < vec_len (ip4_via_next_hops); j++)
1466                       {
1467                         if (table_ids[j] != (u32)~0)
1468                           {
1469                             uword * p = hash_get (im4->fib_index_by_table_id,
1470                                                   table_ids[j]);
1471                             if (p == 0)
1472                               {
1473                                 clib_warning ("no such FIB table %d",
1474                                               table_ids[j]);
1475                                 continue;
1476                               }
1477                             table_ids[j] = p[0];
1478                           }
1479
1480                         ip4_add_del_route_next_hop (im4,
1481                                                     IP4_ROUTE_FLAG_DEL | f,
1482                                                     &a.dst_address,
1483                                                     a.dst_address_length,
1484                                                     &ip4_via_next_hops[j],
1485                                                     sw_if_indices[j],
1486                                                     weights[j], (u32)~0,
1487                                                     table_ids[j] /* fib index */);
1488                       }
1489                     dst.as_u32 = clib_host_to_net_u32 (incr + clib_net_to_host_u32 (dst.as_u32));
1490                   }
1491                 t[1] = vlib_time_now (vm);
1492                 if (count > 1)
1493                   vlib_cli_output (vm, "%.6e routes/sec", count / (t[1] - t[0]));
1494               }
1495           }
1496         else
1497           {
1498             if (vec_len (add_adj) > 0)
1499               {
1500                 a.flags |= IP4_ROUTE_FLAG_ADD;
1501                 a.add_adj = add_adj;
1502                 a.n_add_adj = vec_len (add_adj);
1503
1504                 ip4_add_del_route (im4, &a);
1505               }
1506             else if (vec_len (ip4_via_next_hops) > 0)
1507               {
1508                 u32 i, j, n, f, incr;
1509                 ip4_address_t dst = a.dst_address;
1510                 f64 t[2];
1511                 n = count;
1512                 t[0] = vlib_time_now (vm);
1513                 incr = 1<<(32 - a.dst_address_length);
1514                 for (i = 0; i < n; i++)
1515                   {
1516                     f = i + 1 < n ? IP4_ROUTE_FLAG_NOT_LAST_IN_GROUP : 0;
1517                     a.dst_address = dst;
1518                     for (j = 0; j < vec_len (ip4_via_next_hops); j++)
1519                       {
1520                         if (table_ids[j] != (u32)~0)
1521                           {
1522                             uword * p = hash_get (im4->fib_index_by_table_id,
1523                                                   table_ids[j]);
1524                             if (p == 0)
1525                               {
1526                                 clib_warning ("no such FIB table %d",
1527                                               table_ids[j]);
1528                                 continue;
1529                               }
1530                             table_ids[j] = p[0];
1531                           }
1532                       ip4_add_del_route_next_hop (im4,
1533                                                   IP4_ROUTE_FLAG_ADD | f,
1534                                                   &a.dst_address,
1535                                                   a.dst_address_length,
1536                                                   &ip4_via_next_hops[j],
1537                                                   sw_if_indices[j],
1538                                                   weights[j], (u32)~0,
1539                                                   table_ids[j] /* fib index */);
1540                       }
1541                     dst.as_u32 = clib_host_to_net_u32 (incr + clib_net_to_host_u32 (dst.as_u32));
1542                   }
1543                 t[1] = vlib_time_now (vm);
1544                 if (count > 1)
1545                   vlib_cli_output (vm, "%.6e routes/sec", count / (t[1] - t[0]));
1546               }
1547           }
1548       }
1549
1550     for (i = 0; i < vec_len (ip6_dst_addresses); i++)
1551       {
1552         ip6_add_del_route_args_t a;
1553
1554
1555         memset (&a, 0, sizeof (a));
1556         a.flags = IP6_ROUTE_FLAG_TABLE_ID;
1557         a.table_index_or_table_id = table_id;
1558         a.dst_address = ip6_dst_addresses[i];
1559         a.dst_address_length = dst_address_lengths[i];
1560         a.adj_index = ~0;
1561
1562         if (is_del)
1563           {
1564             if (vec_len (ip6_via_next_hops) == 0)
1565               {
1566                 BVT(clib_bihash_kv) kv, value;
1567                 ip6_address_t dst_address;
1568                 ip6_fib_t * fib;
1569
1570                 fib = find_ip6_fib_by_table_index_or_id (im6, table_id,
1571                                                          0 /* by table id */);
1572
1573                 a.flags |= IP4_ROUTE_FLAG_DEL;
1574
1575                 dst_address = ip6_dst_addresses[i];
1576
1577                 ip6_address_mask (&dst_address,
1578                                   &im6->fib_masks[dst_address_length]);
1579
1580                 kv.key[0] = dst_address.as_u64[0];
1581                 kv.key[1] = dst_address.as_u64[1];
1582                 kv.key[2] = ((u64)(fib - im6->fibs)<<32)
1583                   | a.dst_address_length;
1584
1585                 if (BV(clib_bihash_search)(&im6->ip6_lookup_table,
1586                                            &kv, &value) == 0)
1587                   a.adj_index = value.value;
1588                 else
1589                   {
1590                     clib_warning ("%U/%d not in FIB",
1591                                   format_ip6_address, &a.dst_address,
1592                                   a.dst_address_length);
1593                     continue;
1594                   }
1595
1596                 a.flags |= IP6_ROUTE_FLAG_DEL;
1597                 ip6_add_del_route (im6, &a);
1598                 ip6_maybe_remap_adjacencies (im6, table_id,
1599                                              IP6_ROUTE_FLAG_TABLE_ID);
1600               }
1601             else
1602               {
1603                 u32 i;
1604                 for (i = 0; i < vec_len (ip6_via_next_hops); i++)
1605                   {
1606                     ip6_add_del_route_next_hop (im6,
1607                                                 IP6_ROUTE_FLAG_DEL,
1608                                                 &a.dst_address,
1609                                                 a.dst_address_length,
1610                                                 &ip6_via_next_hops[i],
1611                                                 sw_if_indices[i],
1612                                                 weights[i], (u32)~0,
1613                                                 table_ids[i] /* fib index */);
1614                   }
1615               }
1616           }
1617         else
1618           {
1619             if (vec_len (add_adj) > 0)
1620               {
1621                 a.flags |= IP6_ROUTE_FLAG_ADD;
1622                 a.add_adj = add_adj;
1623                 a.n_add_adj = vec_len (add_adj);
1624
1625                 ip6_add_del_route (im6, &a);
1626               }
1627             else if (vec_len (ip6_via_next_hops) > 0)
1628               {
1629                 u32 i;
1630                 for (i = 0; i < vec_len (ip6_via_next_hops); i++)
1631                   {
1632                     ip6_add_del_route_next_hop (im6,
1633                                                 IP6_ROUTE_FLAG_ADD,
1634                                                 &a.dst_address,
1635                                                 a.dst_address_length,
1636                                                 &ip6_via_next_hops[i],
1637                                                 sw_if_indices[i],
1638                                                 weights[i], (u32)~0,
1639                                                 table_ids[i]);
1640                   }
1641               }
1642           }
1643       }
1644   }
1645
1646  done:
1647   vec_free (add_adj);
1648   vec_free (weights);
1649   vec_free (dst_address_lengths);
1650   vec_free (ip4_dst_addresses);
1651   vec_free (ip6_dst_addresses);
1652   vec_free (ip4_via_next_hops);
1653   vec_free (ip6_via_next_hops);
1654   return error;
1655 }
1656
1657 VLIB_CLI_COMMAND (vlib_cli_ip_command, static) = {
1658   .path = "ip",
1659   .short_help = "Internet protocol (IP) commands",
1660 };
1661
1662 VLIB_CLI_COMMAND (vlib_cli_show_ip_command, static) = {
1663   .path = "show ip",
1664   .short_help = "Internet protocol (IP) show commands",
1665 };
1666
1667 VLIB_CLI_COMMAND (vlib_cli_show_ip4_command, static) = {
1668   .path = "show ip4",
1669   .short_help = "Internet protocol version 4 (IP4) show commands",
1670 };
1671
1672 VLIB_CLI_COMMAND (vlib_cli_show_ip6_command, static) = {
1673   .path = "show ip6",
1674   .short_help = "Internet protocol version 6 (IP6) show commands",
1675 };
1676
1677 /*?
1678  * To add or delete routes, use ip route add / del
1679  * @cliexpar
1680  * @cliexstart{ip route}
1681  * To add or delete straightforward static routes, use ip route add / del:
1682  *  vpp# ip route add 6.0.1.2/32 via 6.0.0.1 GigabitEthernet2/0/0
1683  *  vpp# ip route del 6.0.1.2/32 via 6.0.0.1 GigabitEthernet2/0/0
1684  *
1685  * Multiple routes
1686  *
1687  * Mainly for route add/del performance testing, one can add or delete
1688  * multiple routes by adding 'count N' to the previous item:
1689  *  vpp# ip route add count 10 7.0.0.0/24 via 6.0.0.1 GigabitEthernet2/0/0
1690  *
1691  * Multipath
1692  *
1693  * Add multiple routes for the same destination to create equal-cost multipath:
1694  *  vpp# ip route add 7.0.0.1/32 via 6.0.0.1 GigabitEthernet2/0/0
1695  *  vpp# ip route add 7.0.0.1/32 via 6.0.0.2 GigabitEthernet2/0/0
1696  *
1697  * For unequal-cost multipath, specify the desired weights:
1698  *  vpp# ip route add 7.0.0.1/32 via 6.0.0.1 GigabitEthernet2/0/0 weight 1
1699  *  vpp# ip route add 7.0.0.1/32 via 6.0.0.2 GigabitEthernet2/0/0 weight 3
1700  *
1701  * This combination of weights results in 3/4 of the traffic following the second path, 1/4 following the first path.
1702  * @cliexend
1703  ?*/
1704 VLIB_CLI_COMMAND (ip_route_command, static) = {
1705   .path = "ip route",
1706   .short_help = "Add/delete IP routes",
1707   .function = vnet_ip_route_cmd,
1708   .is_mp_safe = 1,
1709 };
1710
1711 /*
1712  * The next two routines address a longstanding script hemorrhoid.
1713  * Probing a v4 or v6 neighbor needs to appear to be synchronous,
1714  * or dependent route-adds will simply fail.
1715  */
1716 static clib_error_t *
1717 ip6_probe_neighbor_wait (vlib_main_t *vm, ip6_address_t * a, u32 sw_if_index,
1718                          int retry_count)
1719 {
1720   vnet_main_t * vnm = vnet_get_main();
1721   clib_error_t * e;
1722   int i;
1723   int resolved = 0;
1724   uword event_type;
1725   uword *event_data = 0;
1726
1727   ASSERT (vlib_in_process_context(vm));
1728
1729   if (retry_count > 0)
1730     vnet_register_ip6_neighbor_resolution_event
1731       (vnm, a, vlib_get_current_process (vm)->node_runtime.node_index,
1732        1 /* event */, 0 /* data */);
1733
1734   for (i = 0; i < retry_count; i++)
1735     {
1736       /* The interface may be down, etc. */
1737       e = ip6_probe_neighbor (vm, a, sw_if_index);
1738
1739       if (e)
1740         return e;
1741
1742       vlib_process_wait_for_event_or_clock (vm, 1.0);
1743       event_type = vlib_process_get_events (vm, &event_data);
1744       switch (event_type)
1745         {
1746         case 1: /* resolved... */
1747           vlib_cli_output (vm, "Resolved %U",
1748                            format_ip6_address, a);
1749           resolved = 1;
1750           goto done;
1751
1752         case ~0: /* timeout */
1753           break;
1754
1755         default:
1756           clib_warning ("unknown event_type %d", event_type);
1757         }
1758       vec_reset_length (event_data);
1759     }
1760
1761  done:
1762
1763   if (!resolved)
1764     return clib_error_return (0, "Resolution failed for %U",
1765                               format_ip6_address, a);
1766   return 0;
1767 }
1768
1769 static clib_error_t *
1770 ip4_probe_neighbor_wait (vlib_main_t *vm, ip4_address_t * a, u32 sw_if_index,
1771                          int retry_count)
1772 {
1773   vnet_main_t * vnm = vnet_get_main();
1774   clib_error_t * e;
1775   int i;
1776   int resolved = 0;
1777   uword event_type;
1778   uword *event_data = 0;
1779
1780   ASSERT (vlib_in_process_context(vm));
1781
1782   if (retry_count > 0)
1783     vnet_register_ip4_arp_resolution_event
1784       (vnm, a, vlib_get_current_process (vm)->node_runtime.node_index,
1785        1 /* event */, 0 /* data */);
1786
1787   for (i = 0; i < retry_count; i++)
1788     {
1789       /* The interface may be down, etc. */
1790       e = ip4_probe_neighbor (vm, a, sw_if_index);
1791
1792       if (e)
1793         return e;
1794
1795       vlib_process_wait_for_event_or_clock (vm, 1.0);
1796       event_type = vlib_process_get_events (vm, &event_data);
1797       switch (event_type)
1798         {
1799         case 1: /* resolved... */
1800           vlib_cli_output (vm, "Resolved %U",
1801                            format_ip4_address, a);
1802           resolved = 1;
1803           goto done;
1804
1805         case ~0: /* timeout */
1806           break;
1807
1808         default:
1809           clib_warning ("unknown event_type %d", event_type);
1810         }
1811       vec_reset_length (event_data);
1812     }
1813
1814  done:
1815
1816   vec_reset_length (event_data);
1817
1818   if (!resolved)
1819     return clib_error_return (0, "Resolution failed for %U",
1820                               format_ip4_address, a);
1821   return 0;
1822 }
1823
1824 static clib_error_t *
1825 probe_neighbor_address (vlib_main_t * vm,
1826                         unformat_input_t * input,
1827                         vlib_cli_command_t * cmd)
1828 {
1829   vnet_main_t * vnm = vnet_get_main();
1830   unformat_input_t _line_input, * line_input = &_line_input;
1831   ip4_address_t a4;
1832   ip6_address_t a6;
1833   clib_error_t * error = 0;
1834   u32 sw_if_index = ~0;
1835   int retry_count = 3;
1836   int is_ip4 = 1;
1837   int address_set = 0;
1838
1839   /* Get a line of input. */
1840   if (! unformat_user (input, unformat_line_input, line_input))
1841     return 0;
1842
1843   while (unformat_check_input (line_input) != UNFORMAT_END_OF_INPUT)
1844     {
1845       if (unformat_user (line_input, unformat_vnet_sw_interface, vnm,
1846                          &sw_if_index))
1847         ;
1848       else if (unformat (line_input, "retry %d", &retry_count))
1849         ;
1850
1851       else if (unformat (line_input, "%U", unformat_ip4_address, &a4))
1852         address_set++;
1853       else if (unformat (line_input, "%U", unformat_ip6_address, &a6))
1854         {
1855           address_set++;
1856           is_ip4 = 0;
1857         }
1858       else
1859         return clib_error_return (0, "unknown input '%U'",
1860                                   format_unformat_error, line_input);
1861     }
1862
1863   unformat_free (line_input);
1864
1865   if (sw_if_index == ~0)
1866     return clib_error_return (0, "Interface required, not set.");
1867   if (address_set == 0)
1868     return clib_error_return (0, "ip address required, not set.");
1869   if (address_set > 1)
1870     return clib_error_return (0, "Multiple ip addresses not supported.");
1871
1872   if (is_ip4)
1873     error = ip4_probe_neighbor_wait (vm, &a4, sw_if_index, retry_count);
1874   else
1875     error = ip6_probe_neighbor_wait (vm, &a6, sw_if_index, retry_count);
1876
1877   return error;
1878 }
1879
1880 VLIB_CLI_COMMAND (ip_probe_neighbor_command, static) = {
1881   .path = "ip probe-neighbor",
1882   .function = probe_neighbor_address,
1883   .short_help = "ip probe-neighbor <intfc> <ip4-addr> | <ip6-addr> [retry nn]",
1884   .is_mp_safe = 1,
1885 };
1886
1887 typedef CLIB_PACKED (struct {
1888   ip4_address_t address;
1889
1890   u32 address_length : 6;
1891
1892   u32 index : 26;
1893 }) ip4_route_t;
1894
1895 static int
1896 ip4_route_cmp (void * a1, void * a2)
1897 {
1898   ip4_route_t * r1 = a1;
1899   ip4_route_t * r2 = a2;
1900
1901   int cmp = ip4_address_compare (&r1->address, &r2->address);
1902   return cmp ? cmp : ((int) r1->address_length - (int) r2->address_length);
1903 }
1904
1905 static clib_error_t *
1906 ip4_show_fib (vlib_main_t * vm, unformat_input_t * input, vlib_cli_command_t * cmd)
1907 {
1908   vnet_main_t * vnm = vnet_get_main();
1909   ip4_main_t * im4 = &ip4_main;
1910   ip4_route_t * routes, * r;
1911   ip4_fib_t * fib;
1912   ip_lookup_main_t * lm = &im4->lookup_main;
1913   uword * results, i;
1914   int verbose, matching, mtrie, include_empty_fibs;
1915   ip4_address_t matching_address;
1916   u8 clear = 0;
1917   int table_id = -1;
1918
1919   routes = 0;
1920   results = 0;
1921   verbose = 1;
1922   include_empty_fibs = 0;
1923   matching = 0;
1924   mtrie = 0;
1925   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1926     {
1927       if (unformat (input, "brief") || unformat (input, "summary")
1928           || unformat (input, "sum"))
1929         verbose = 0;
1930
1931       else if (unformat (input, "mtrie"))
1932         mtrie = 1;
1933
1934       else if (unformat (input, "include-empty"))
1935         include_empty_fibs = 1;
1936
1937       else if (unformat (input, "%U", unformat_ip4_address, &matching_address))
1938         matching = 1;
1939
1940       else if (unformat (input, "clear"))
1941         clear = 1;
1942
1943       else if (unformat (input, "table %d", &table_id))
1944                ;
1945       else
1946         break;
1947     }
1948
1949   vec_foreach (fib, im4->fibs)
1950     {
1951       int fib_not_empty;
1952
1953       fib_not_empty = 0;
1954       for (i = 0; i < ARRAY_LEN (fib->adj_index_by_dst_address); i++)
1955         {
1956           uword * hash = fib->adj_index_by_dst_address[i];
1957           uword n_elts = hash_elts (hash);
1958           if (n_elts)
1959             {
1960               fib_not_empty = 1;
1961               break;
1962             }
1963         }
1964
1965       if (fib_not_empty == 0 && include_empty_fibs == 0)
1966         continue;
1967
1968       if (table_id >= 0 && table_id != (int)fib->table_id)
1969         continue;
1970
1971       if (include_empty_fibs)
1972           vlib_cli_output (vm, "Table %d, fib_index %d, flow hash: %U",
1973                            fib->table_id, fib - im4->fibs,
1974                            format_ip_flow_hash_config, fib->flow_hash_config);
1975
1976       /* Show summary? */
1977       if (! verbose)
1978         {
1979         if (include_empty_fibs == 0)
1980             vlib_cli_output (vm, "Table %d, fib_index %d, flow hash: %U",
1981                              fib->table_id, fib - im4->fibs,
1982                              format_ip_flow_hash_config, fib->flow_hash_config);
1983           vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
1984           for (i = 0; i < ARRAY_LEN (fib->adj_index_by_dst_address); i++)
1985             {
1986               uword * hash = fib->adj_index_by_dst_address[i];
1987               uword n_elts = hash_elts (hash);
1988               if (n_elts > 0)
1989                 vlib_cli_output (vm, "%20d%16d", i, n_elts);
1990             }
1991           continue;
1992         }
1993
1994       if (routes)
1995         _vec_len (routes) = 0;
1996       if (results)
1997         _vec_len (results) = 0;
1998
1999       for (i = 0; i < ARRAY_LEN (fib->adj_index_by_dst_address); i++)
2000         {
2001           uword * hash = fib->adj_index_by_dst_address[i];
2002           hash_pair_t * p;
2003           ip4_route_t x;
2004
2005           x.address_length = i;
2006
2007           if (matching)
2008             {
2009               x.address.as_u32 = matching_address.as_u32 & im4->fib_masks[i];
2010               p = hash_get_pair (hash, x.address.as_u32);
2011               if (p)
2012                 {
2013                   if (lm->fib_result_n_words > 1)
2014                     {
2015                       x.index = vec_len (results);
2016                       vec_add (results, p->value, lm->fib_result_n_words);
2017                     }
2018                   else
2019                     x.index = p->value[0];
2020                   vec_add1 (routes, x);
2021                 }
2022             }
2023           else
2024             {
2025               hash_foreach_pair (p, hash, ({
2026                 x.address.data_u32 = p->key;
2027                 if (lm->fib_result_n_words > 1)
2028                   {
2029                     x.index = vec_len (results);
2030                     vec_add (results, p->value, lm->fib_result_n_words);
2031                   }
2032                 else
2033                   x.index = p->value[0];
2034
2035                 vec_add1 (routes, x);
2036               }));
2037             }
2038         }
2039
2040       vec_sort_with_function (routes, ip4_route_cmp);
2041       if (vec_len(routes)) {
2042           if (include_empty_fibs == 0)
2043               vlib_cli_output (vm, "Table %d, fib_index %d, flow hash: %U",
2044                                fib->table_id, fib - im4->fibs,
2045                                format_ip_flow_hash_config, fib->flow_hash_config);
2046           if (mtrie)
2047               vlib_cli_output (vm, "%U", format_ip4_fib_mtrie, &fib->mtrie);
2048           vlib_cli_output (vm, "%=20s%=16s%=16s%=16s",
2049                            "Destination", "Packets", "Bytes", "Adjacency");
2050       }
2051       vec_foreach (r, routes)
2052         {
2053           vlib_counter_t c, sum;
2054           uword i, j, n_left, n_nhs, adj_index, * result = 0;
2055           ip_adjacency_t * adj;
2056           ip_multipath_next_hop_t * nhs, tmp_nhs[1];
2057
2058           adj_index = r->index;
2059           if (lm->fib_result_n_words > 1)
2060             {
2061               result = vec_elt_at_index (results, adj_index);
2062               adj_index = result[0];
2063             }
2064
2065           adj = ip_get_adjacency (lm, adj_index);
2066           if (adj->n_adj == 1)
2067             {
2068               nhs = &tmp_nhs[0];
2069               nhs[0].next_hop_adj_index = ~0; /* not used */
2070               nhs[0].weight = 1;
2071               n_nhs = 1;
2072             }
2073           else
2074             {
2075               ip_multipath_adjacency_t * madj;
2076               madj = vec_elt_at_index (lm->multipath_adjacencies, adj->heap_handle);
2077               nhs = heap_elt_at_index (lm->next_hop_heap, madj->normalized_next_hops.heap_offset);
2078               n_nhs = madj->normalized_next_hops.count;
2079             }
2080
2081           n_left = nhs[0].weight;
2082           vlib_counter_zero (&sum);
2083           for (i = j = 0; i < adj->n_adj; i++)
2084             {
2085               n_left -= 1;
2086               vlib_get_combined_counter (&lm->adjacency_counters,
2087                                          adj_index + i, &c);
2088               if (clear)
2089                 vlib_zero_combined_counter (&lm->adjacency_counters,
2090                                             adj_index + i);
2091               vlib_counter_add (&sum, &c);
2092               if (n_left == 0)
2093                 {
2094                   u8 * msg = 0;
2095                   uword indent;
2096
2097                   if (j == 0)
2098                     msg = format (msg, "%-20U",
2099                                   format_ip4_address_and_length,
2100                                   r->address.data, r->address_length);
2101                   else
2102                     msg = format (msg, "%U", format_white_space, 20);
2103
2104                   msg = format (msg, "%16Ld%16Ld ", sum.packets, sum.bytes);
2105
2106                   indent = vec_len (msg);
2107                   msg = format (msg, "weight %d, index %d",
2108                                 nhs[j].weight, adj_index + i);
2109
2110                   if (ip_adjacency_is_multipath(lm, adj_index))
2111                       msg = format (msg, ", multipath");
2112
2113                   msg = format (msg, "\n%U%U",
2114                                 format_white_space, indent,
2115                                 format_ip_adjacency,
2116                                 vnm, lm, adj_index + i);
2117
2118                   vlib_cli_output (vm, "%v", msg);
2119                   vec_free (msg);
2120
2121                   if (result && lm->format_fib_result)
2122                     vlib_cli_output (vm, "%20s%U", "",
2123                                      lm->format_fib_result, vm, lm, result,
2124                                      i + 1 - nhs[j].weight,
2125                                      nhs[j].weight);
2126
2127                   j++;
2128                   if (j < n_nhs)
2129                     {
2130                       n_left = nhs[j].weight;
2131                       vlib_counter_zero (&sum);
2132                     }
2133                 }
2134             }
2135         }
2136     }
2137
2138   vec_free (routes);
2139   vec_free (results);
2140
2141   return 0;
2142 }
2143
2144 /*?
2145  * Show FIB/route entries
2146  *
2147  * @cliexpar
2148  * @cliexstart{show ip fib}
2149  * Display the IPv4 FIB.
2150  * This command will run for a long time when the FIBs comprise millions of entries.
2151  *   vpp# sh ip fib
2152  *   Table 0
2153  *   Destination         Packets          Bytes         Adjacency
2154  *   6.0.0.0/8                          0               0 weight 1, index 3
2155  *                                                       arp fake-eth0 6.0.0.1/8
2156  *   6.0.0.1/32                         0               0 weight 1, index 4
2157  *                                                        local 6.0.0.1/8
2158  *
2159  *  And so forth. Use 'show ip fib summary' for a summary:
2160  *
2161  *   vpp# sh ip fib summary
2162  *   Table 0
2163  *   Prefix length         Count
2164  *         8               1
2165  *        32               4
2166  * @cliexend
2167  ?*/
2168 VLIB_CLI_COMMAND (ip4_show_fib_command, static) = {
2169   .path = "show ip fib",
2170   .short_help = "show ip fib [mtrie] [summary] [table <n>] [<ip4-addr>] [clear] [include-empty]",
2171   .function = ip4_show_fib,
2172 };
2173
2174 typedef struct {
2175   ip6_address_t address;
2176
2177   u32 address_length;
2178
2179   u32 index;
2180 } ip6_route_t;
2181
2182 typedef struct {
2183   u32 fib_index;
2184   ip6_route_t ** routep;
2185 } add_routes_in_fib_arg_t;
2186
2187 static void add_routes_in_fib (BVT(clib_bihash_kv) * kvp, void *arg)
2188 {
2189   add_routes_in_fib_arg_t * ap = arg;
2190
2191   if (kvp->key[2]>>32 == ap->fib_index)
2192     {
2193       ip6_address_t *addr;
2194       ip6_route_t * r;
2195       addr = (ip6_address_t *) kvp;
2196       vec_add2 (*ap->routep, r, 1);
2197       r->address = addr[0];
2198       r->address_length = kvp->key[2] & 0xFF;
2199       r->index = kvp->value;
2200     }
2201 }
2202
2203 typedef struct {
2204   u32 fib_index;
2205   u64 count_by_prefix_length[129];
2206 } count_routes_in_fib_at_prefix_length_arg_t;
2207
2208 static void count_routes_in_fib_at_prefix_length
2209 (BVT(clib_bihash_kv) * kvp, void *arg)
2210 {
2211   count_routes_in_fib_at_prefix_length_arg_t * ap = arg;
2212   int mask_width;
2213
2214   if ((kvp->key[2]>>32) != ap->fib_index)
2215     return;
2216
2217   mask_width = kvp->key[2] & 0xFF;
2218
2219   ap->count_by_prefix_length[mask_width]++;
2220 }
2221
2222 static int
2223 ip6_route_cmp (void * a1, void * a2)
2224 {
2225   ip6_route_t * r1 = a1;
2226   ip6_route_t * r2 = a2;
2227
2228   int cmp = ip6_address_compare (&r1->address, &r2->address);
2229   return cmp ? cmp : ((int) r1->address_length - (int) r2->address_length);
2230 }
2231
2232 static clib_error_t *
2233 ip6_show_fib (vlib_main_t * vm, unformat_input_t * input, vlib_cli_command_t * cmd)
2234 {
2235   vnet_main_t * vnm = vnet_get_main();
2236   ip6_main_t * im6 = &ip6_main;
2237   ip6_route_t * routes, * r;
2238   ip6_fib_t * fib;
2239   ip_lookup_main_t * lm = &im6->lookup_main;
2240   uword * results;
2241   int verbose;
2242   BVT(clib_bihash) * h = &im6->ip6_lookup_table;
2243   __attribute__((unused)) u8 clear = 0;
2244   add_routes_in_fib_arg_t _a, *a=&_a;
2245   count_routes_in_fib_at_prefix_length_arg_t _ca, *ca = &_ca;
2246
2247   routes = 0;
2248   results = 0;
2249   verbose = 1;
2250   if (unformat (input, "brief") || unformat (input, "summary")
2251       || unformat (input, "sum"))
2252     verbose = 0;
2253
2254   if (unformat (input, "clear"))
2255     clear = 1;
2256
2257   vlib_cli_output (vm, "FIB lookup table: %d buckets, %lld MB heap",
2258                    im6->lookup_table_nbuckets, im6->lookup_table_size>>20);
2259   vlib_cli_output (vm, "%U", format_mheap, h->mheap, 0 /*verbose*/);
2260   vlib_cli_output (vm, " ");
2261
2262   vec_foreach (fib, im6->fibs)
2263     {
2264       vlib_cli_output (vm, "VRF %d, fib_index %d, flow hash: %U",
2265                        fib->table_id, fib - im6->fibs,
2266                        format_ip_flow_hash_config, fib->flow_hash_config);
2267
2268       /* Show summary? */
2269       if (! verbose)
2270         {
2271           int len;
2272           vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
2273
2274           memset (ca, 0, sizeof(*ca));
2275           ca->fib_index = fib - im6->fibs;
2276
2277           BV(clib_bihash_foreach_key_value_pair)
2278             (h, count_routes_in_fib_at_prefix_length, ca);
2279
2280           for (len = 128; len >= 0; len--)
2281             {
2282               if (ca->count_by_prefix_length[len])
2283                 vlib_cli_output (vm, "%=20d%=16lld",
2284                                  len, ca->count_by_prefix_length[len]);
2285             }
2286           continue;
2287         }
2288
2289       if (routes)
2290         _vec_len (routes) = 0;
2291       if (results)
2292         _vec_len (results) = 0;
2293
2294       a->fib_index = fib - im6->fibs;
2295       a->routep = &routes;
2296
2297       BV(clib_bihash_foreach_key_value_pair)(h, add_routes_in_fib, a);
2298
2299       vec_sort_with_function (routes, ip6_route_cmp);
2300
2301       vlib_cli_output (vm, "%=45s%=16s%=16s%=16s",
2302                        "Destination", "Packets", "Bytes", "Adjacency");
2303       vec_foreach (r, routes)
2304         {
2305           vlib_counter_t c, sum;
2306           uword i, j, n_left, n_nhs, adj_index, * result = 0;
2307           ip_adjacency_t * adj;
2308           ip_multipath_next_hop_t * nhs, tmp_nhs[1];
2309
2310           adj_index = r->index;
2311           if (lm->fib_result_n_words > 1)
2312             {
2313               result = vec_elt_at_index (results, adj_index);
2314               adj_index = result[0];
2315             }
2316
2317           adj = ip_get_adjacency (lm, adj_index);
2318           if (adj->n_adj == 1)
2319             {
2320               nhs = &tmp_nhs[0];
2321               nhs[0].next_hop_adj_index = ~0; /* not used */
2322               nhs[0].weight = 1;
2323               n_nhs = 1;
2324             }
2325           else
2326             {
2327               ip_multipath_adjacency_t * madj;
2328               madj = vec_elt_at_index (lm->multipath_adjacencies, adj->heap_handle);
2329               nhs = heap_elt_at_index (lm->next_hop_heap, madj->normalized_next_hops.heap_offset);
2330               n_nhs = madj->normalized_next_hops.count;
2331             }
2332
2333           n_left = nhs[0].weight;
2334           vlib_counter_zero (&sum);
2335           for (i = j = 0; i < adj->n_adj; i++)
2336             {
2337               n_left -= 1;
2338               vlib_get_combined_counter (&lm->adjacency_counters,
2339                                          adj_index + i, &c);
2340               if (clear)
2341                 vlib_zero_combined_counter (&lm->adjacency_counters,
2342                                             adj_index + i);
2343               vlib_counter_add (&sum, &c);
2344               if (n_left == 0)
2345                 {
2346                   u8 * msg = 0;
2347                   uword indent;
2348
2349                   if (j == 0)
2350                     msg = format (msg, "%-45U",
2351                                   format_ip6_address_and_length,
2352                                   r->address.as_u8, r->address_length);
2353                   else
2354                     msg = format (msg, "%U", format_white_space, 20);
2355
2356                   msg = format (msg, "%16Ld%16Ld ", sum.packets, sum.bytes);
2357
2358                   indent = vec_len (msg);
2359                   msg = format (msg, "weight %d, index %d",
2360                                 nhs[j].weight, adj_index + i);
2361
2362                   if (ip_adjacency_is_multipath(lm, adj_index + i))
2363                       msg = format (msg, ", multipath");
2364
2365                   msg = format (msg, "\n%U%U",
2366                                 format_white_space, indent,
2367                                 format_ip_adjacency,
2368                                 vnm, lm, adj_index + i);
2369
2370                   vlib_cli_output (vm, "%v", msg);
2371                   vec_free (msg);
2372
2373                   j++;
2374                   if (j < n_nhs)
2375                     {
2376                       n_left = nhs[j].weight;
2377                       vlib_counter_zero (&sum);
2378                     }
2379                 }
2380             }
2381
2382           if (result && lm->format_fib_result)
2383             vlib_cli_output (vm, "%20s%U", "", lm->format_fib_result, vm, lm, result, 0);
2384         }
2385       vlib_cli_output (vm, " ");
2386     }
2387
2388   vec_free (routes);
2389   vec_free (results);
2390
2391   return 0;
2392 }
2393
2394 /*?
2395  * Show FIB6/route entries
2396  *
2397  * @cliexpar
2398  * @cliexstart{show ip fib}
2399  * Display the IPv6 FIB.
2400  * This command will run for a long time when the FIBs comprise millions of entries.
2401  * See 'show ip fib'
2402  * @cliexend
2403  ?*/
2404 VLIB_CLI_COMMAND (ip6_show_fib_command, static) = {
2405   .path = "show ip6 fib",
2406   .short_help = "show ip6 fib [summary] [clear]",
2407   .function = ip6_show_fib,
2408 };