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