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