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