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