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