src/vnet/adj/adj_nbr.c

   1 /*
   2  * Copyright (c) 2016 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 #include <vnet/adj/adj_nbr.h>
  17 #include <vnet/adj/adj_internal.h>
  18 #include <vnet/ethernet/arp_packet.h>
  19 #include <vnet/fib/fib_walk.h>
  20
  21 /*
  22  * Vector Hash tables of neighbour (traditional) adjacencies
  23  *  Key: interface(for the vector index), address (and its proto),
  24  *       link-type/ether-type.
  25  */
  26 static BVT(clib_bihash) **adj_nbr_tables[FIB_PROTOCOL_MAX];
  27
  28 // FIXME SIZE APPROPRIATELY. ASK DAVEB.
  29 #define ADJ_NBR_DEFAULT_HASH_NUM_BUCKETS (64 * 64)
  30 #define ADJ_NBR_DEFAULT_HASH_MEMORY_SIZE (32<<20)
  31
  32
  33 #define ADJ_NBR_SET_KEY(_key, _lt, _nh)         \
  34 {                                               \
  35     _key.key[0] = (_nh)->as_u64[0];             \
  36     _key.key[1] = (_nh)->as_u64[1];             \
  37     _key.key[2] = (_lt);                        \
  38 }
  39
  40 #define ADJ_NBR_ITF_OK(_proto, _itf)                    \
  41     (((_itf) < vec_len(adj_nbr_tables[_proto])) &&      \
  42      (NULL != adj_nbr_tables[_proto][sw_if_index]))
  43
  44 static void
  45 adj_nbr_insert (fib_protocol_t nh_proto,
  46                 vnet_link_t link_type,
  47                 const ip46_address_t *nh_addr,
  48                 u32 sw_if_index,
  49                 adj_index_t adj_index)
  50 {
  51     BVT(clib_bihash_kv) kv;
  52
  53     if (sw_if_index >= vec_len(adj_nbr_tables[nh_proto]))
  54     {
  55         vec_validate(adj_nbr_tables[nh_proto], sw_if_index);
  56     }
  57     if (NULL == adj_nbr_tables[nh_proto][sw_if_index])
  58     {
  59         adj_nbr_tables[nh_proto][sw_if_index] =
  60             clib_mem_alloc_aligned(sizeof(BVT(clib_bihash)),
  61                                    CLIB_CACHE_LINE_BYTES);
  62         memset(adj_nbr_tables[nh_proto][sw_if_index],
  63                0,
  64                sizeof(BVT(clib_bihash)));
  65
  66         BV(clib_bihash_init) (adj_nbr_tables[nh_proto][sw_if_index],
  67                               "Adjacency Neighbour table",
  68                               ADJ_NBR_DEFAULT_HASH_NUM_BUCKETS,
  69                               ADJ_NBR_DEFAULT_HASH_MEMORY_SIZE);
  70     }
  71
  72     ADJ_NBR_SET_KEY(kv, link_type, nh_addr);
  73     kv.value = adj_index;
  74
  75     BV(clib_bihash_add_del) (adj_nbr_tables[nh_proto][sw_if_index], &kv, 1);
  76 }
  77
  78 void
  79 adj_nbr_remove (adj_index_t ai,
  80                 fib_protocol_t nh_proto,
  81                 vnet_link_t link_type,
  82                 const ip46_address_t *nh_addr,
  83                 u32 sw_if_index)
  84 {
  85     BVT(clib_bihash_kv) kv;
  86
  87     if (!ADJ_NBR_ITF_OK(nh_proto, sw_if_index))
  88         return;
  89
  90     ADJ_NBR_SET_KEY(kv, link_type, nh_addr);
  91     kv.value = ai;
  92
  93     BV(clib_bihash_add_del) (adj_nbr_tables[nh_proto][sw_if_index], &kv, 0);
  94 }
  95
  96 static adj_index_t
  97 adj_nbr_find (fib_protocol_t nh_proto,
  98               vnet_link_t link_type,
  99               const ip46_address_t *nh_addr,
 100               u32 sw_if_index)
 101 {
 102     BVT(clib_bihash_kv) kv;
 103
 104     ADJ_NBR_SET_KEY(kv, link_type, nh_addr);
 105
 106     if (!ADJ_NBR_ITF_OK(nh_proto, sw_if_index))
 107         return (ADJ_INDEX_INVALID);
 108
 109     if (BV(clib_bihash_search)(adj_nbr_tables[nh_proto][sw_if_index],
 110                                &kv, &kv) < 0)
 111     {
 112         return (ADJ_INDEX_INVALID);
 113     }
 114     else
 115     {
 116         return (kv.value);
 117     }
 118 }
 119
 120 static inline u32
 121 adj_get_nd_node (fib_protocol_t proto)
 122 {
 123     switch (proto) {
 124     case FIB_PROTOCOL_IP4:
 125         return (ip4_arp_node.index);
 126     case FIB_PROTOCOL_IP6:
 127         return (ip6_discover_neighbor_node.index);
 128     case FIB_PROTOCOL_MPLS:
 129         break;
 130     }
 131     ASSERT(0);
 132     return (ip4_arp_node.index);
 133 }
 134
 135 /**
 136  * @brief Check and set feature flags if o/p interface has any o/p features.
 137  */
 138 static void
 139 adj_nbr_evaluate_feature (adj_index_t ai)
 140 {
 141     ip_adjacency_t *adj;
 142     vnet_feature_main_t *fm = &feature_main;
 143     i16 feature_count;
 144     u8 arc_index;
 145     u32 sw_if_index;
 146
 147     adj = adj_get(ai);
 148
 149     switch (adj->ia_link)
 150     {
 151     case VNET_LINK_IP4:
 152         arc_index = ip4_main.lookup_main.output_feature_arc_index;
 153         break;
 154     case VNET_LINK_IP6:
 155         arc_index = ip6_main.lookup_main.output_feature_arc_index;
 156         break;
 157     case VNET_LINK_MPLS:
 158         arc_index = mpls_main.output_feature_arc_index;
 159         break;
 160     default:
 161         return;
 162     }
 163
 164     sw_if_index = adj->rewrite_header.sw_if_index;
 165     if (vec_len(fm->feature_count_by_sw_if_index[arc_index]) > sw_if_index)
 166     {
 167         feature_count = fm->feature_count_by_sw_if_index[arc_index][sw_if_index];
 168         if (feature_count > 0)
 169             adj->rewrite_header.flags |= VNET_REWRITE_HAS_FEATURES;
 170     }
 171
 172     return;
 173 }
 174
 175 static ip_adjacency_t*
 176 adj_nbr_alloc (fib_protocol_t nh_proto,
 177                vnet_link_t link_type,
 178                const ip46_address_t *nh_addr,
 179                u32 sw_if_index)
 180 {
 181     ip_adjacency_t *adj;
 182
 183     adj = adj_alloc(nh_proto);
 184
 185     adj_nbr_insert(nh_proto, link_type, nh_addr,
 186                    sw_if_index,
 187                    adj_get_index(adj));
 188
 189     /*
 190      * since we just added the ADJ we have no rewrite string for it,
 191      * so its for ARP
 192      */
 193     adj->lookup_next_index = IP_LOOKUP_NEXT_ARP;
 194     adj->sub_type.nbr.next_hop = *nh_addr;
 195     adj->ia_link = link_type;
 196     adj->ia_nh_proto = nh_proto;
 197     adj->rewrite_header.sw_if_index = sw_if_index;
 198     memset(&adj->sub_type.midchain.next_dpo, 0,
 199            sizeof(adj->sub_type.midchain.next_dpo));
 200
 201     adj_nbr_evaluate_feature (adj_get_index(adj));
 202     return (adj);
 203 }
 204
 205 /*
 206  * adj_nbr_add_or_lock
 207  *
 208  * Add an adjacency for the neighbour requested.
 209  *
 210  * The key for an adj is:
 211  *   - the Next-hops protocol (i.e. v4 or v6)
 212  *   - the address of the next-hop
 213  *   - the interface the next-hop is reachable through
 214  */
 215 adj_index_t
 216 adj_nbr_add_or_lock (fib_protocol_t nh_proto,
 217                      vnet_link_t link_type,
 218                      const ip46_address_t *nh_addr,
 219                      u32 sw_if_index)
 220 {
 221     adj_index_t adj_index;
 222     ip_adjacency_t *adj;
 223
 224     adj_index = adj_nbr_find(nh_proto, link_type, nh_addr, sw_if_index);
 225
 226     if (ADJ_INDEX_INVALID == adj_index)
 227     {
 228         vnet_main_t *vnm;
 229
 230         vnm = vnet_get_main();
 231         adj = adj_nbr_alloc(nh_proto, link_type, nh_addr, sw_if_index);
 232         adj_index = adj_get_index(adj);
 233         adj_lock(adj_index);
 234
 235         vnet_rewrite_init(vnm, sw_if_index,
 236                           adj_get_nd_node(nh_proto),
 237                           vnet_tx_node_index_for_sw_interface(vnm, sw_if_index),
 238                           &adj->rewrite_header);
 239
 240         /*
 241          * we need a rewrite where the destination IP address is converted
 242          * to the appropriate link-layer address. This is interface specific.
 243          * So ask the interface to do it.
 244          */
 245         vnet_update_adjacency_for_sw_interface(vnm, sw_if_index, adj_index);
 246     }
 247     else
 248     {
 249         adj_lock(adj_index);
 250     }
 251
 252     return (adj_index);
 253 }
 254
 255 adj_index_t
 256 adj_nbr_add_or_lock_w_rewrite (fib_protocol_t nh_proto,
 257                                vnet_link_t link_type,
 258                                const ip46_address_t *nh_addr,
 259                                u32 sw_if_index,
 260                                u8 *rewrite)
 261 {
 262     adj_index_t adj_index;
 263     ip_adjacency_t *adj;
 264
 265     adj_index = adj_nbr_find(nh_proto, link_type, nh_addr, sw_if_index);
 266
 267     if (ADJ_INDEX_INVALID == adj_index)
 268     {
 269         adj = adj_nbr_alloc(nh_proto, link_type, nh_addr, sw_if_index);
 270         adj->rewrite_header.sw_if_index = sw_if_index;
 271     }
 272     else
 273     {
 274         adj = adj_get(adj_index);
 275     }
 276
 277     adj_lock(adj_get_index(adj));
 278     adj_nbr_update_rewrite(adj_get_index(adj),
 279                            ADJ_NBR_REWRITE_FLAG_COMPLETE,
 280                            rewrite);
 281
 282     return (adj_get_index(adj));
 283 }
 284
 285 /**
 286  * adj_nbr_update_rewrite
 287  *
 288  * Update the adjacency's rewrite string. A NULL string implies the
 289  * rewirte is reset (i.e. when ARP/ND etnry is gone).
 290  * NB: the adj being updated may be handling traffic in the DP.
 291  */
 292 void
 293 adj_nbr_update_rewrite (adj_index_t adj_index,
 294                         adj_nbr_rewrite_flag_t flags,
 295                         u8 *rewrite)
 296 {
 297     ip_adjacency_t *adj;
 298
 299     ASSERT(ADJ_INDEX_INVALID != adj_index);
 300
 301     adj = adj_get(adj_index);
 302
 303     if (flags & ADJ_NBR_REWRITE_FLAG_COMPLETE)
 304     {
 305         /*
 306          * update the adj's rewrite string and build the arc
 307          * from the rewrite node to the interface's TX node
 308          */
 309         adj_nbr_update_rewrite_internal(adj, IP_LOOKUP_NEXT_REWRITE,
 310                                         adj_get_rewrite_node(adj->ia_link),
 311                                         vnet_tx_node_index_for_sw_interface(
 312                                             vnet_get_main(),
 313                                             adj->rewrite_header.sw_if_index),
 314                                         rewrite);
 315     }
 316     else
 317     {
 318         adj_nbr_update_rewrite_internal(adj, IP_LOOKUP_NEXT_ARP,
 319                                         adj_get_nd_node(adj->ia_nh_proto),
 320                                         vnet_tx_node_index_for_sw_interface(
 321                                             vnet_get_main(),
 322                                             adj->rewrite_header.sw_if_index),
 323                                         rewrite);
 324     }
 325 }
 326
 327 /**
 328  * adj_nbr_update_rewrite_internal
 329  *
 330  * Update the adjacency's rewrite string. A NULL string implies the
 331  * rewirte is reset (i.e. when ARP/ND etnry is gone).
 332  * NB: the adj being updated may be handling traffic in the DP.
 333  */
 334 void
 335 adj_nbr_update_rewrite_internal (ip_adjacency_t *adj,
 336                                  u32 adj_next_index,
 337                                  u32 this_node,
 338                                  u32 next_node,
 339                                  u8 *rewrite)
 340 {
 341     ip_adjacency_t *walk_adj;
 342     adj_index_t walk_ai;
 343     vlib_main_t * vm;
 344     u32 old_next;
 345     int do_walk;
 346
 347     vm = vlib_get_main();
 348     old_next = adj->lookup_next_index;
 349
 350     walk_ai = adj_get_index(adj);
 351     if (VNET_LINK_MPLS == adj->ia_link)
 352     {
 353         /*
 354          * The link type MPLS has no children in the control plane graph, it only
 355          * has children in the data-palne graph. The backwalk is up the former.
 356          * So we need to walk from its IP cousin.
 357          */
 358         walk_ai = adj_nbr_find(adj->ia_nh_proto,
 359                                fib_proto_to_link(adj->ia_nh_proto),
 360                                &adj->sub_type.nbr.next_hop,
 361                                adj->rewrite_header.sw_if_index);
 362     }
 363
 364     /*
 365      * Don't call the walk re-entrantly
 366      */
 367     if (ADJ_INDEX_INVALID != walk_ai)
 368     {
 369         walk_adj = adj_get(walk_ai);
 370         if (IP_ADJ_SYNC_WALK_ACTIVE & walk_adj->ia_flags)
 371         {
 372             do_walk = 0;
 373         }
 374         else
 375         {
 376             /*
 377              * Prevent re-entrant walk of the same adj
 378              */
 379             walk_adj->ia_flags |= IP_ADJ_SYNC_WALK_ACTIVE;
 380             do_walk = 1;
 381         }
 382     }
 383     else
 384     {
 385         do_walk = 0;
 386     }
 387
 388     /*
 389      * lock the adjacencies that are affected by updates this walk will provoke.
 390      * Since the aim of the walk is to update children to link to a different
 391      * DPO, this adj will no longer be in use and its lock count will drop to 0.
 392      * We don't want it to be deleted as part of this endevour.
 393      */
 394     adj_lock(adj_get_index(adj));
 395     adj_lock(walk_ai);
 396
 397     /*
 398      * Updating a rewrite string is not atomic;
 399      *  - the rewrite string is too long to write in one instruction
 400      *  - when swapping from incomplete to complete, we also need to update
 401      *    the VLIB graph next-index of the adj.
 402      * ideally we would only want to suspend forwarding via this adj whilst we
 403      * do this, but we do not have that level of granularity - it's suspend all
 404      * worker threads or nothing.
 405      * The other chioces are:
 406      *  - to mark the adj down and back walk so child load-balances drop this adj
 407      *    from the set.
 408      *  - update the next_node index of this adj to point to error-drop
 409      * both of which will mean for MAC change we will drop for this adj
 410      * which is not acceptable. However, when the adj changes type (from
 411      * complete to incomplete and vice-versa) the child DPOs, which have the
 412      * VLIB graph next node index, will be sending packets to the wrong graph
 413      * node. So from the options above, updating the next_node of the adj to
 414      * be drop will work, but it relies on each graph node v4/v6/mpls, rewrite/
 415      * arp/midchain always be valid w.r.t. a mis-match of adj type and node type
 416      * (i.e. a rewrite adj in the arp node). This is not enforcable. Getting it
 417      * wrong will lead to hard to find bugs since its a race condition. So we
 418      * choose the more reliable method of updating the children to use the drop,
 419      * then switching adj's type, then updating the children again. Did I mention
 420      * that this doesn't happen often...
 421      * So we need to distinguish between the two cases:
 422      *  1 - mac change
 423      *  2 - adj type change
 424      */
 425     if (do_walk &&
 426         old_next != adj_next_index &&
 427         ADJ_INDEX_INVALID != walk_ai)
 428     {
 429         /*
 430          * the adj is changing type. we need to fix all children so that they
 431          * stack momentarily on a drop, while the adj changes. If we don't do
 432          * this  the children will send packets to a VLIB graph node that does
 433          * not correspond to the adj's type - and it goes downhill from there.
 434          */
 435         fib_node_back_walk_ctx_t bw_ctx = {
 436             .fnbw_reason = FIB_NODE_BW_REASON_FLAG_ADJ_DOWN,
 437             /*
 438              * force this walk to be synchrous. if we don't and a node in the graph
 439              * (a heavily shared path-list) chooses to back-ground the walk (make it
 440              * async) then it will pause and we will do the adj update below, before
 441              * all the children are updated. not good.
 442              */
 443             .fnbw_flags = FIB_NODE_BW_FLAG_FORCE_SYNC,
 444         };
 445
 446         fib_walk_sync(FIB_NODE_TYPE_ADJ, walk_ai, &bw_ctx);
 447     }
 448
 449     /*
 450      * If we are just updating the MAC string of the adj (which we also can't
 451      * do atomically), then we need to stop packets switching through the adj.
 452      * We can't do that on a per-adj basis, so it's all the packets.
 453      * If we are updating the type, and we walked back to the children above,
 454      * then this barrier serves to flush the queues/frames.
 455      */
 456     vlib_worker_thread_barrier_sync(vm);
 457
 458     adj->lookup_next_index = adj_next_index;
 459
 460     if (NULL != rewrite)
 461     {
 462         /*
 463          * new rewrite provided.
 464          * fill in the adj's rewrite string, and build the VLIB graph arc.
 465          */
 466         vnet_rewrite_set_data_internal(&adj->rewrite_header,
 467                                        sizeof(adj->rewrite_data),
 468                                        rewrite,
 469                                        vec_len(rewrite));
 470         vec_free(rewrite);
 471     }
 472     else
 473     {
 474         vnet_rewrite_clear_data_internal(&adj->rewrite_header,
 475                                          sizeof(adj->rewrite_data));
 476     }
 477     adj->rewrite_header.next_index = vlib_node_add_next(vlib_get_main(),
 478                                                         this_node,
 479                                                         next_node);
 480
 481     /*
 482      * done with the rewirte update - let the workers loose.
 483      */
 484     vlib_worker_thread_barrier_release(vm);
 485
 486     if (do_walk &&
 487         (old_next != adj->lookup_next_index) &&
 488         (ADJ_INDEX_INVALID != walk_ai))
 489     {
 490         /*
 491          * backwalk to the children so they can stack on the now updated
 492          * adjacency
 493          */
 494         fib_node_back_walk_ctx_t bw_ctx = {
 495             .fnbw_reason = FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE,
 496         };
 497
 498         fib_walk_sync(FIB_NODE_TYPE_ADJ, walk_ai, &bw_ctx);
 499     }
 500     /*
 501      * Prevent re-entrant walk of the same adj
 502      */
 503     if (do_walk)
 504     {
 505         walk_adj->ia_flags &= ~IP_ADJ_SYNC_WALK_ACTIVE;
 506     }
 507
 508     adj_unlock(adj_get_index(adj));
 509     adj_unlock(walk_ai);
 510 }
 511
 512 typedef struct adj_db_count_ctx_t_ {
 513     u64 count;
 514 } adj_db_count_ctx_t;
 515
 516 static void
 517 adj_db_count (BVT(clib_bihash_kv) * kvp,
 518               void *arg)
 519 {
 520     adj_db_count_ctx_t * ctx = arg;
 521     ctx->count++;
 522 }
 523
 524 u32
 525 adj_nbr_db_size (void)
 526 {
 527     adj_db_count_ctx_t ctx = {
 528         .count = 0,
 529     };
 530     fib_protocol_t proto;
 531     u32 sw_if_index = 0;
 532
 533     for (proto = FIB_PROTOCOL_IP4; proto <= FIB_PROTOCOL_IP6; proto++)
 534     {
 535         vec_foreach_index(sw_if_index, adj_nbr_tables[proto])
 536         {
 537             if (NULL != adj_nbr_tables[proto][sw_if_index])
 538             {
 539                 BV(clib_bihash_foreach_key_value_pair) (
 540                     adj_nbr_tables[proto][sw_if_index],
 541                     adj_db_count,
 542                     &ctx);
 543             }
 544         }
 545     }
 546     return (ctx.count);
 547 }
 548
 549 /**
 550  * @brief Context for a walk of the adjacency neighbour DB
 551  */
 552 typedef struct adj_walk_ctx_t_
 553 {
 554     adj_walk_cb_t awc_cb;
 555     void *awc_ctx;
 556 } adj_walk_ctx_t;
 557
 558 static void
 559 adj_nbr_walk_cb (BVT(clib_bihash_kv) * kvp,
 560                  void *arg)
 561 {
 562     adj_walk_ctx_t *ctx = arg;
 563
 564     // FIXME: can't stop early...
 565     ctx->awc_cb(kvp->value, ctx->awc_ctx);
 566 }
 567
 568 void
 569 adj_nbr_walk (u32 sw_if_index,
 570               fib_protocol_t adj_nh_proto,
 571               adj_walk_cb_t cb,
 572               void *ctx)
 573 {
 574     if (!ADJ_NBR_ITF_OK(adj_nh_proto, sw_if_index))
 575         return;
 576
 577     adj_walk_ctx_t awc = {
 578         .awc_ctx = ctx,
 579         .awc_cb = cb,
 580     };
 581
 582     BV(clib_bihash_foreach_key_value_pair) (
 583         adj_nbr_tables[adj_nh_proto][sw_if_index],
 584         adj_nbr_walk_cb,
 585         &awc);
 586 }
 587
 588 /**
 589  * @brief Context for a walk of the adjacency neighbour DB
 590  */
 591 typedef struct adj_walk_nh_ctx_t_
 592 {
 593     adj_walk_cb_t awc_cb;
 594     void *awc_ctx;
 595     const ip46_address_t *awc_nh;
 596 } adj_walk_nh_ctx_t;
 597
 598 static void
 599 adj_nbr_walk_nh_cb (BVT(clib_bihash_kv) * kvp,
 600                     void *arg)
 601 {
 602     ip_adjacency_t *adj;
 603     adj_walk_nh_ctx_t *ctx = arg;
 604
 605     adj = adj_get(kvp->value);
 606
 607     if (!ip46_address_cmp(&adj->sub_type.nbr.next_hop, ctx->awc_nh))
 608         ctx->awc_cb(kvp->value, ctx->awc_ctx);
 609 }
 610
 611 /**
 612  * @brief Walk adjacencies on a link with a given v4 next-hop.
 613  * that is visit the adjacencies with different link types.
 614  */
 615 void
 616 adj_nbr_walk_nh4 (u32 sw_if_index,
 617                  const ip4_address_t *addr,
 618                  adj_walk_cb_t cb,
 619                  void *ctx)
 620 {
 621     if (!ADJ_NBR_ITF_OK(FIB_PROTOCOL_IP4, sw_if_index))
 622         return;
 623
 624     ip46_address_t nh = {
 625         .ip4 = *addr,
 626     };
 627
 628     adj_walk_nh_ctx_t awc = {
 629         .awc_ctx = ctx,
 630         .awc_cb = cb,
 631         .awc_nh = &nh,
 632     };
 633
 634     BV(clib_bihash_foreach_key_value_pair) (
 635         adj_nbr_tables[FIB_PROTOCOL_IP4][sw_if_index],
 636         adj_nbr_walk_nh_cb,
 637         &awc);
 638 }
 639
 640 /**
 641  * @brief Walk adjacencies on a link with a given v6 next-hop.
 642  * that is visit the adjacencies with different link types.
 643  */
 644 void
 645 adj_nbr_walk_nh6 (u32 sw_if_index,
 646                  const ip6_address_t *addr,
 647                  adj_walk_cb_t cb,
 648                  void *ctx)
 649 {
 650     if (!ADJ_NBR_ITF_OK(FIB_PROTOCOL_IP6, sw_if_index))
 651         return;
 652
 653     ip46_address_t nh = {
 654         .ip6 = *addr,
 655     };
 656
 657     adj_walk_nh_ctx_t awc = {
 658         .awc_ctx = ctx,
 659         .awc_cb = cb,
 660         .awc_nh = &nh,
 661     };
 662
 663     BV(clib_bihash_foreach_key_value_pair) (
 664         adj_nbr_tables[FIB_PROTOCOL_IP6][sw_if_index],
 665         adj_nbr_walk_nh_cb,
 666         &awc);
 667 }
 668
 669 /**
 670  * @brief Walk adjacencies on a link with a given next-hop.
 671  * that is visit the adjacencies with different link types.
 672  */
 673 void
 674 adj_nbr_walk_nh (u32 sw_if_index,
 675                  fib_protocol_t adj_nh_proto,
 676                  const ip46_address_t *nh,
 677                  adj_walk_cb_t cb,
 678                  void *ctx)
 679 {
 680     if (!ADJ_NBR_ITF_OK(adj_nh_proto, sw_if_index))
 681         return;
 682
 683     adj_walk_nh_ctx_t awc = {
 684         .awc_ctx = ctx,
 685         .awc_cb = cb,
 686         .awc_nh = nh,
 687     };
 688
 689     BV(clib_bihash_foreach_key_value_pair) (
 690         adj_nbr_tables[adj_nh_proto][sw_if_index],
 691         adj_nbr_walk_nh_cb,
 692         &awc);
 693 }
 694
 695 /**
 696  * Flags associated with the interface state walks
 697  */
 698 typedef enum adj_nbr_interface_flags_t_
 699 {
 700     ADJ_NBR_INTERFACE_UP = (1 << 0),
 701 } adj_nbr_interface_flags_t;
 702
 703 /**
 704  * Context for the state change walk of the DB
 705  */
 706 typedef struct adj_nbr_interface_state_change_ctx_t_
 707 {
 708     /**
 709      * Flags on the interface
 710      */
 711     adj_nbr_interface_flags_t flags;
 712 } adj_nbr_interface_state_change_ctx_t;
 713
 714 static adj_walk_rc_t
 715 adj_nbr_interface_state_change_one (adj_index_t ai,
 716                                     void *arg)
 717 {
 718     /*
 719      * Back walk the graph to inform the forwarding entries
 720      * that this interface state has changed. Do this synchronously
 721      * since this is the walk that provides convergence
 722      */
 723     adj_nbr_interface_state_change_ctx_t *ctx = arg;
 724
 725     fib_node_back_walk_ctx_t bw_ctx = {
 726         .fnbw_reason = ((ctx->flags & ADJ_NBR_INTERFACE_UP) ?
 727                         FIB_NODE_BW_REASON_FLAG_INTERFACE_UP :
 728                         FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN),
 729         /*
 730          * the force sync applies only as far as the first fib_entry.
 731          * And it's the fib_entry's we need to converge away from
 732          * the adjacencies on the now down link
 733          */
 734         .fnbw_flags = (!(ctx->flags & ADJ_NBR_INTERFACE_UP) ?
 735                        FIB_NODE_BW_FLAG_FORCE_SYNC :
 736                        0),
 737     };
 738
 739     fib_walk_sync(FIB_NODE_TYPE_ADJ, ai, &bw_ctx);
 740
 741     return (ADJ_WALK_RC_CONTINUE);
 742 }
 743
 744 /**
 745  * @brief Registered function for SW interface state changes
 746  */
 747 static clib_error_t *
 748 adj_nbr_sw_interface_state_change (vnet_main_t * vnm,
 749                                    u32 sw_if_index,
 750                                    u32 flags)
 751 {
 752     fib_protocol_t proto;
 753
 754     /*
 755      * walk each adj on the interface and trigger a walk from that adj
 756      */
 757     for (proto = FIB_PROTOCOL_IP4; proto <= FIB_PROTOCOL_IP6; proto++)
 758     {
 759         adj_nbr_interface_state_change_ctx_t ctx = {
 760             .flags = ((flags & VNET_SW_INTERFACE_FLAG_ADMIN_UP) ?
 761                       ADJ_NBR_INTERFACE_UP :
 762                       0),
 763         };
 764
 765         adj_nbr_walk(sw_if_index, proto,
 766                      adj_nbr_interface_state_change_one,
 767                      &ctx);
 768     }
 769
 770     return (NULL);
 771 }
 772
 773 VNET_SW_INTERFACE_ADMIN_UP_DOWN_FUNCTION_PRIO(
 774     adj_nbr_sw_interface_state_change,
 775     VNET_ITF_FUNC_PRIORITY_HIGH);
 776
 777 /**
 778  * @brief Invoked on each SW interface of a HW interface when the
 779  * HW interface state changes
 780  */
 781 static void
 782 adj_nbr_hw_sw_interface_state_change (vnet_main_t * vnm,
 783                                       u32 sw_if_index,
 784                                       void *arg)
 785 {
 786     adj_nbr_interface_state_change_ctx_t *ctx = arg;
 787     fib_protocol_t proto;
 788
 789     /*
 790      * walk each adj on the interface and trigger a walk from that adj
 791      */
 792     for (proto = FIB_PROTOCOL_IP4; proto <= FIB_PROTOCOL_IP6; proto++)
 793     {
 794         adj_nbr_walk(sw_if_index, proto,
 795                      adj_nbr_interface_state_change_one,
 796                      ctx);
 797     }
 798 }
 799
 800 /**
 801  * @brief Registered callback for HW interface state changes
 802  */
 803 static clib_error_t *
 804 adj_nbr_hw_interface_state_change (vnet_main_t * vnm,
 805                                    u32 hw_if_index,
 806                                    u32 flags)
 807 {
 808     /*
 809      * walk SW interface on the HW
 810      */
 811     adj_nbr_interface_state_change_ctx_t ctx = {
 812         .flags = ((flags & VNET_HW_INTERFACE_FLAG_LINK_UP) ?
 813                   ADJ_NBR_INTERFACE_UP :
 814                   0),
 815     };
 816
 817     vnet_hw_interface_walk_sw(vnm, hw_if_index,
 818                               adj_nbr_hw_sw_interface_state_change,
 819                               &ctx);
 820
 821     return (NULL);
 822 }
 823
 824 VNET_HW_INTERFACE_LINK_UP_DOWN_FUNCTION_PRIO(
 825     adj_nbr_hw_interface_state_change,
 826     VNET_ITF_FUNC_PRIORITY_HIGH);
 827
 828 static adj_walk_rc_t
 829 adj_nbr_interface_delete_one (adj_index_t ai,
 830                               void *arg)
 831 {
 832     /*
 833      * Back walk the graph to inform the forwarding entries
 834      * that this interface has been deleted.
 835      */
 836     fib_node_back_walk_ctx_t bw_ctx = {
 837         .fnbw_reason = FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE,
 838     };
 839
 840     fib_walk_sync(FIB_NODE_TYPE_ADJ, ai, &bw_ctx);
 841
 842     return (ADJ_WALK_RC_CONTINUE);
 843 }
 844
 845 /**
 846  * adj_nbr_interface_add_del
 847  *
 848  * Registered to receive interface Add and delete notifications
 849  */
 850 static clib_error_t *
 851 adj_nbr_interface_add_del (vnet_main_t * vnm,
 852                            u32 sw_if_index,
 853                            u32 is_add)
 854 {
 855     fib_protocol_t proto;
 856
 857     if (is_add)
 858     {
 859         /*
 860          * not interested in interface additions. we will not back walk
 861          * to resolve paths through newly added interfaces. Why? The control
 862          * plane should have the brains to add interfaces first, then routes.
 863          * So the case where there are paths with a interface that matches
 864          * one just created is the case where the path resolved through an
 865          * interface that was deleted, and still has not been removed. The
 866          * new interface added, is NO GUARANTEE that the interface being
 867          * added now, even though it may have the same sw_if_index, is the
 868          * same interface that the path needs. So tough!
 869          * If the control plane wants these routes to resolve it needs to
 870          * remove and add them again.
 871          */
 872         return (NULL);
 873     }
 874
 875     for (proto = FIB_PROTOCOL_IP4; proto <= FIB_PROTOCOL_IP6; proto++)
 876     {
 877         adj_nbr_walk(sw_if_index, proto,
 878                      adj_nbr_interface_delete_one,
 879                      NULL);
 880     }
 881
 882     return (NULL);
 883
 884 }
 885
 886 VNET_SW_INTERFACE_ADD_DEL_FUNCTION(adj_nbr_interface_add_del);
 887
 888
 889 static adj_walk_rc_t
 890 adj_nbr_show_one (adj_index_t ai,
 891                   void *arg)
 892 {
 893     vlib_cli_output (arg, "[@%d]  %U",
 894                      ai,
 895                      format_ip_adjacency, ai,
 896                      FORMAT_IP_ADJACENCY_NONE);
 897
 898     return (ADJ_WALK_RC_CONTINUE);
 899 }
 900
 901 static clib_error_t *
 902 adj_nbr_show (vlib_main_t * vm,
 903               unformat_input_t * input,
 904               vlib_cli_command_t * cmd)
 905 {
 906     adj_index_t ai = ADJ_INDEX_INVALID;
 907     u32 sw_if_index = ~0;
 908
 909     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 910     {
 911         if (unformat (input, "%d", &ai))
 912             ;
 913         else if (unformat (input, "%U",
 914                            unformat_vnet_sw_interface, vnet_get_main(),
 915                            &sw_if_index))
 916             ;
 917         else
 918             break;
 919     }
 920
 921     if (ADJ_INDEX_INVALID != ai)
 922     {
 923         vlib_cli_output (vm, "[@%d] %U",
 924                          ai,
 925                          format_ip_adjacency, ai,
 926                          FORMAT_IP_ADJACENCY_DETAIL);
 927     }
 928     else if (~0 != sw_if_index)
 929     {
 930         fib_protocol_t proto;
 931
 932         for (proto = FIB_PROTOCOL_IP4; proto <= FIB_PROTOCOL_IP6; proto++)
 933         {
 934             adj_nbr_walk(sw_if_index, proto,
 935                          adj_nbr_show_one,
 936                          vm);
 937         }
 938     }
 939     else
 940     {
 941         fib_protocol_t proto;
 942
 943         for (proto = FIB_PROTOCOL_IP4; proto <= FIB_PROTOCOL_IP6; proto++)
 944         {
 945             vec_foreach_index(sw_if_index, adj_nbr_tables[proto])
 946             {
 947                 adj_nbr_walk(sw_if_index, proto,
 948                              adj_nbr_show_one,
 949                              vm);
 950             }
 951         }
 952     }
 953
 954     return 0;
 955 }
 956
 957 /*?
 958  * Show all neighbour adjacencies.
 959  * @cliexpar
 960  * @cliexstart{sh adj nbr}
 961  * [@2] ipv4 via 1.0.0.2 loop0: IP4: 00:00:22:aa:bb:cc -> 00:00:11:aa:bb:cc
 962  * [@3] mpls via 1.0.0.2 loop0: MPLS_UNICAST: 00:00:22:aa:bb:cc -> 00:00:11:aa:bb:cc
 963  * [@4] ipv4 via 1.0.0.3 loop0: IP4: 00:00:22:aa:bb:cc -> 00:00:11:aa:bb:cc
 964  * [@5] mpls via 1.0.0.3 loop0: MPLS_UNICAST: 00:00:22:aa:bb:cc -> 00:00:11:aa:bb:cc
 965  * @cliexend
 966  ?*/
 967 VLIB_CLI_COMMAND (ip4_show_fib_command, static) = {
 968     .path = "show adj nbr",
 969     .short_help = "show adj nbr [<adj_index>] [interface]",
 970     .function = adj_nbr_show,
 971 };
 972
 973 static ip46_type_t
 974 adj_proto_to_46 (fib_protocol_t proto)
 975 {
 976     switch (proto)
 977     {
 978     case FIB_PROTOCOL_IP4:
 979         return (IP46_TYPE_IP4);
 980     case FIB_PROTOCOL_IP6:
 981         return (IP46_TYPE_IP6);
 982     default:
 983         return (IP46_TYPE_IP4);
 984     }
 985     return (IP46_TYPE_IP4);
 986 }
 987
 988 u8*
 989 format_adj_nbr_incomplete (u8* s, va_list *ap)
 990 {
 991     index_t index = va_arg(*ap, index_t);
 992     CLIB_UNUSED(u32 indent) = va_arg(*ap, u32);
 993     vnet_main_t * vnm = vnet_get_main();
 994     ip_adjacency_t * adj = adj_get(index);
 995
 996     s = format (s, "arp-%U", format_vnet_link, adj->ia_link);
 997     s = format (s, ": via %U",
 998                 format_ip46_address, &adj->sub_type.nbr.next_hop,
 999                 adj_proto_to_46(adj->ia_nh_proto));
1000     s = format (s, " %U",
1001                 format_vnet_sw_interface_name,
1002                 vnm,
1003                 vnet_get_sw_interface(vnm,
1004                                       adj->rewrite_header.sw_if_index));
1005
1006     return (s);
1007 }
1008
1009 u8*
1010 format_adj_nbr (u8* s, va_list *ap)
1011 {
1012     index_t index = va_arg(*ap, index_t);
1013     CLIB_UNUSED(u32 indent) = va_arg(*ap, u32);
1014     ip_adjacency_t * adj = adj_get(index);
1015
1016     s = format (s, "%U", format_vnet_link, adj->ia_link);
1017     s = format (s, " via %U ",
1018                 format_ip46_address, &adj->sub_type.nbr.next_hop,
1019                 adj_proto_to_46(adj->ia_nh_proto));
1020     s = format (s, "%U",
1021                 format_vnet_rewrite,
1022                 &adj->rewrite_header, sizeof (adj->rewrite_data), 0);
1023
1024     return (s);
1025 }
1026
1027 static void
1028 adj_dpo_lock (dpo_id_t *dpo)
1029 {
1030     adj_lock(dpo->dpoi_index);
1031 }
1032 static void
1033 adj_dpo_unlock (dpo_id_t *dpo)
1034 {
1035     adj_unlock(dpo->dpoi_index);
1036 }
1037
1038 static void
1039 adj_mem_show (void)
1040 {
1041     fib_show_memory_usage("Adjacency",
1042                           pool_elts(adj_pool),
1043                           pool_len(adj_pool),
1044                           sizeof(ip_adjacency_t));
1045 }
1046
1047 const static dpo_vft_t adj_nbr_dpo_vft = {
1048     .dv_lock = adj_dpo_lock,
1049     .dv_unlock = adj_dpo_unlock,
1050     .dv_format = format_adj_nbr,
1051     .dv_mem_show = adj_mem_show,
1052 };
1053 const static dpo_vft_t adj_nbr_incompl_dpo_vft = {
1054     .dv_lock = adj_dpo_lock,
1055     .dv_unlock = adj_dpo_unlock,
1056     .dv_format = format_adj_nbr_incomplete,
1057 };
1058
1059 /**
1060  * @brief The per-protocol VLIB graph nodes that are assigned to an adjacency
1061  *        object.
1062  *
1063  * this means that these graph nodes are ones from which a nbr is the
1064  * parent object in the DPO-graph.
1065  */
1066 const static char* const nbr_ip4_nodes[] =
1067 {
1068     "ip4-rewrite",
1069     NULL,
1070 };
1071 const static char* const nbr_ip6_nodes[] =
1072 {
1073     "ip6-rewrite",
1074     NULL,
1075 };
1076 const static char* const nbr_mpls_nodes[] =
1077 {
1078     "mpls-output",
1079     NULL,
1080 };
1081 const static char* const nbr_ethernet_nodes[] =
1082 {
1083     "adj-l2-rewrite",
1084     NULL,
1085 };
1086 const static char* const * const nbr_nodes[DPO_PROTO_NUM] =
1087 {
1088     [DPO_PROTO_IP4]  = nbr_ip4_nodes,
1089     [DPO_PROTO_IP6]  = nbr_ip6_nodes,
1090     [DPO_PROTO_MPLS] = nbr_mpls_nodes,
1091     [DPO_PROTO_ETHERNET] = nbr_ethernet_nodes,
1092 };
1093
1094 const static char* const nbr_incomplete_ip4_nodes[] =
1095 {
1096     "ip4-arp",
1097     NULL,
1098 };
1099 const static char* const nbr_incomplete_ip6_nodes[] =
1100 {
1101     "ip6-discover-neighbor",
1102     NULL,
1103 };
1104 const static char* const nbr_incomplete_mpls_nodes[] =
1105 {
1106     "mpls-adj-incomplete",
1107     NULL,
1108 };
1109
1110 const static char* const * const nbr_incomplete_nodes[DPO_PROTO_NUM] =
1111 {
1112     [DPO_PROTO_IP4]  = nbr_incomplete_ip4_nodes,
1113     [DPO_PROTO_IP6]  = nbr_incomplete_ip6_nodes,
1114     [DPO_PROTO_MPLS] = nbr_incomplete_mpls_nodes,
1115 };
1116
1117 void
1118 adj_nbr_module_init (void)
1119 {
1120     dpo_register(DPO_ADJACENCY,
1121                  &adj_nbr_dpo_vft,
1122                  nbr_nodes);
1123     dpo_register(DPO_ADJACENCY_INCOMPLETE,
1124                  &adj_nbr_incompl_dpo_vft,
1125                  nbr_incomplete_nodes);
1126 }