src/vnet/fib/fib_table.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 <vlib/vlib.h>
  17 #include <vnet/dpo/drop_dpo.h>
  18
  19 #include <vnet/fib/fib_table.h>
  20 #include <vnet/fib/fib_entry_cover.h>
  21 #include <vnet/fib/fib_internal.h>
  22 #include <vnet/fib/ip4_fib.h>
  23 #include <vnet/fib/ip6_fib.h>
  24 #include <vnet/fib/mpls_fib.h>
  25
  26 fib_table_t *
  27 fib_table_get (fib_node_index_t index,
  28                fib_protocol_t proto)
  29 {
  30     switch (proto)
  31     {
  32     case FIB_PROTOCOL_IP4:
  33         return (pool_elt_at_index(ip4_main.fibs, index));
  34     case FIB_PROTOCOL_IP6:
  35         return (pool_elt_at_index(ip6_main.fibs, index));
  36     case FIB_PROTOCOL_MPLS:
  37         return (pool_elt_at_index(mpls_main.fibs, index));
  38     }
  39     ASSERT(0);
  40     return (NULL);
  41 }
  42
  43 static inline fib_node_index_t
  44 fib_table_lookup_i (fib_table_t *fib_table,
  45                     const fib_prefix_t *prefix)
  46 {
  47     switch (prefix->fp_proto)
  48     {
  49     case FIB_PROTOCOL_IP4:
  50         return (ip4_fib_table_lookup(ip4_fib_get(fib_table->ft_index),
  51                                      &prefix->fp_addr.ip4,
  52                                      prefix->fp_len));
  53     case FIB_PROTOCOL_IP6:
  54         return (ip6_fib_table_lookup(fib_table->ft_index,
  55                                      &prefix->fp_addr.ip6,
  56                                      prefix->fp_len));
  57     case FIB_PROTOCOL_MPLS:
  58         return (mpls_fib_table_lookup(mpls_fib_get(fib_table->ft_index),
  59                                       prefix->fp_label,
  60                                       prefix->fp_eos));
  61     }
  62     return (FIB_NODE_INDEX_INVALID);
  63 }
  64
  65 fib_node_index_t
  66 fib_table_lookup (u32 fib_index,
  67                   const fib_prefix_t *prefix)
  68 {
  69     return (fib_table_lookup_i(fib_table_get(fib_index, prefix->fp_proto), prefix));
  70 }
  71
  72 static inline fib_node_index_t
  73 fib_table_lookup_exact_match_i (const fib_table_t *fib_table,
  74                                 const fib_prefix_t *prefix)
  75 {
  76     switch (prefix->fp_proto)
  77     {
  78     case FIB_PROTOCOL_IP4:
  79         return (ip4_fib_table_lookup_exact_match(ip4_fib_get(fib_table->ft_index),
  80                                                  &prefix->fp_addr.ip4,
  81                                                  prefix->fp_len));
  82     case FIB_PROTOCOL_IP6:
  83         return (ip6_fib_table_lookup_exact_match(fib_table->ft_index,
  84                                                  &prefix->fp_addr.ip6,
  85                                                  prefix->fp_len));
  86     case FIB_PROTOCOL_MPLS:
  87         return (mpls_fib_table_lookup(mpls_fib_get(fib_table->ft_index),
  88                                       prefix->fp_label,
  89                                       prefix->fp_eos));
  90     }
  91     return (FIB_NODE_INDEX_INVALID);
  92 }
  93
  94 fib_node_index_t
  95 fib_table_lookup_exact_match (u32 fib_index,
  96                               const fib_prefix_t *prefix)
  97 {
  98     return (fib_table_lookup_exact_match_i(fib_table_get(fib_index,
  99                                                          prefix->fp_proto),
 100                                            prefix));
 101 }
 102
 103 static fib_node_index_t
 104 fib_table_get_less_specific_i (fib_table_t *fib_table,
 105                                const fib_prefix_t *prefix)
 106 {
 107     fib_prefix_t pfx;
 108
 109     pfx = *prefix;
 110
 111     if (FIB_PROTOCOL_MPLS == pfx.fp_proto)
 112     {
 113         return (FIB_NODE_INDEX_INVALID);
 114     }
 115
 116     /*
 117      * in the absence of a tree structure for the table that allows for an O(1)
 118      * parent get, a cheeky way to find the cover is to LPM for the prefix with
 119      * mask-1.
 120      * there should always be a cover, though it may be the default route. the
 121      * default route's cover is the default route.
 122      */
 123     if (pfx.fp_len != 0) {
 124         pfx.fp_len -= 1;
 125     }
 126
 127     return (fib_table_lookup_i(fib_table, &pfx));
 128 }
 129
 130 fib_node_index_t
 131 fib_table_get_less_specific (u32 fib_index,
 132                              const fib_prefix_t *prefix)
 133 {
 134     return (fib_table_get_less_specific_i(fib_table_get(fib_index,
 135                                                         prefix->fp_proto),
 136                                           prefix));
 137 }
 138
 139 static void
 140 fib_table_entry_remove (fib_table_t *fib_table,
 141                         const fib_prefix_t *prefix,
 142                         fib_node_index_t fib_entry_index)
 143 {
 144     vlib_smp_unsafe_warning();
 145
 146     fib_table->ft_total_route_counts--;
 147
 148     switch (prefix->fp_proto)
 149     {
 150     case FIB_PROTOCOL_IP4:
 151         ip4_fib_table_entry_remove(ip4_fib_get(fib_table->ft_index),
 152                                    &prefix->fp_addr.ip4,
 153                                    prefix->fp_len);
 154         break;
 155     case FIB_PROTOCOL_IP6:
 156         ip6_fib_table_entry_remove(fib_table->ft_index,
 157                                    &prefix->fp_addr.ip6,
 158                                    prefix->fp_len);
 159         break;
 160     case FIB_PROTOCOL_MPLS:
 161         mpls_fib_table_entry_remove(mpls_fib_get(fib_table->ft_index),
 162                                     prefix->fp_label,
 163                                     prefix->fp_eos);
 164         break;
 165     }
 166
 167     fib_entry_unlock(fib_entry_index);
 168 }
 169
 170 static void
 171 fib_table_post_insert_actions (fib_table_t *fib_table,
 172                                const fib_prefix_t *prefix,
 173                                fib_node_index_t fib_entry_index)
 174 {
 175     fib_node_index_t fib_entry_cover_index;
 176
 177     /*
 178      * no cover relationships in the MPLS FIB
 179      */
 180     if (FIB_PROTOCOL_MPLS == prefix->fp_proto)
 181         return;
 182
 183     /*
 184      * find  the covering entry
 185      */
 186     fib_entry_cover_index = fib_table_get_less_specific_i(fib_table, prefix);
 187     /*
 188      * the indicies are the same when the default route is first added
 189      */
 190     if (fib_entry_cover_index != fib_entry_index)
 191     {
 192         /*
 193          * push any inherting sources from the cover onto the covered
 194          */
 195         fib_entry_inherit(fib_entry_cover_index,
 196                           fib_entry_index);
 197
 198         /*
 199          * inform the covering entry that a new more specific
 200          * has been inserted beneath it
 201          */
 202         fib_entry_cover_change_notify(fib_entry_cover_index,
 203                                       fib_entry_index);
 204     }
 205 }
 206
 207 static void
 208 fib_table_entry_insert (fib_table_t *fib_table,
 209                         const fib_prefix_t *prefix,
 210                         fib_node_index_t fib_entry_index)
 211 {
 212     vlib_smp_unsafe_warning();
 213
 214     fib_entry_lock(fib_entry_index);
 215     fib_table->ft_total_route_counts++;
 216
 217     switch (prefix->fp_proto)
 218     {
 219     case FIB_PROTOCOL_IP4:
 220         ip4_fib_table_entry_insert(ip4_fib_get(fib_table->ft_index),
 221                                    &prefix->fp_addr.ip4,
 222                                    prefix->fp_len,
 223                                    fib_entry_index);
 224         break;
 225     case FIB_PROTOCOL_IP6:
 226         ip6_fib_table_entry_insert(fib_table->ft_index,
 227                                    &prefix->fp_addr.ip6,
 228                                    prefix->fp_len,
 229                                    fib_entry_index);
 230         break;
 231     case FIB_PROTOCOL_MPLS:
 232         mpls_fib_table_entry_insert(mpls_fib_get(fib_table->ft_index),
 233                                     prefix->fp_label,
 234                                     prefix->fp_eos,
 235                                     fib_entry_index);
 236         break;
 237     }
 238
 239     fib_table_post_insert_actions(fib_table, prefix, fib_entry_index);
 240 }
 241
 242 void
 243 fib_table_fwding_dpo_update (u32 fib_index,
 244                              const fib_prefix_t *prefix,
 245                              const dpo_id_t *dpo)
 246 {
 247     vlib_smp_unsafe_warning();
 248
 249     switch (prefix->fp_proto)
 250     {
 251     case FIB_PROTOCOL_IP4:
 252         return (ip4_fib_table_fwding_dpo_update(ip4_fib_get(fib_index),
 253                                                 &prefix->fp_addr.ip4,
 254                                                 prefix->fp_len,
 255                                                 dpo));
 256     case FIB_PROTOCOL_IP6:
 257         return (ip6_fib_table_fwding_dpo_update(fib_index,
 258                                                 &prefix->fp_addr.ip6,
 259                                                 prefix->fp_len,
 260                                                 dpo));
 261     case FIB_PROTOCOL_MPLS:
 262         return (mpls_fib_forwarding_table_update(mpls_fib_get(fib_index),
 263                                                  prefix->fp_label,
 264                                                  prefix->fp_eos,
 265                                                  dpo));
 266     }
 267 }
 268
 269 void
 270 fib_table_fwding_dpo_remove (u32 fib_index,
 271                              const fib_prefix_t *prefix,
 272                              const dpo_id_t *dpo)
 273 {
 274     vlib_smp_unsafe_warning();
 275
 276     switch (prefix->fp_proto)
 277     {
 278     case FIB_PROTOCOL_IP4:
 279         return (ip4_fib_table_fwding_dpo_remove(ip4_fib_get(fib_index),
 280                                                 &prefix->fp_addr.ip4,
 281                                                 prefix->fp_len,
 282                                                 dpo,
 283                                                 fib_table_get_less_specific(fib_index,
 284                                                                             prefix)));
 285     case FIB_PROTOCOL_IP6:
 286         return (ip6_fib_table_fwding_dpo_remove(fib_index,
 287                                                 &prefix->fp_addr.ip6,
 288                                                 prefix->fp_len,
 289                                                 dpo));
 290     case FIB_PROTOCOL_MPLS:
 291         return (mpls_fib_forwarding_table_reset(mpls_fib_get(fib_index),
 292                                                 prefix->fp_label,
 293                                                 prefix->fp_eos));
 294     }
 295 }
 296
 297
 298 fib_node_index_t
 299 fib_table_entry_special_dpo_add (u32 fib_index,
 300                                  const fib_prefix_t *prefix,
 301                                  fib_source_t source,
 302                                  fib_entry_flag_t flags,
 303                                  const dpo_id_t *dpo)
 304 {
 305     fib_node_index_t fib_entry_index;
 306     fib_table_t *fib_table;
 307
 308     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 309     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 310
 311     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 312     {
 313         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 314                                                    source, flags,
 315                                                    dpo);
 316
 317         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 318         fib_table->ft_src_route_counts[source]++;
 319     }
 320     else
 321     {
 322         int was_sourced;
 323
 324         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 325         fib_entry_special_add(fib_entry_index, source, flags, dpo);
 326
 327         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 328         {
 329             fib_table->ft_src_route_counts[source]++;
 330         }
 331     }
 332
 333
 334     return (fib_entry_index);
 335 }
 336
 337 fib_node_index_t
 338 fib_table_entry_special_dpo_update (u32 fib_index,
 339                                     const fib_prefix_t *prefix,
 340                                     fib_source_t source,
 341                                     fib_entry_flag_t flags,
 342                                     const dpo_id_t *dpo)
 343 {
 344     fib_node_index_t fib_entry_index;
 345     fib_table_t *fib_table;
 346
 347     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 348     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 349
 350     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 351     {
 352         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 353                                                    source, flags,
 354                                                    dpo);
 355
 356         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 357         fib_table->ft_src_route_counts[source]++;
 358     }
 359     else
 360     {
 361         int was_sourced;
 362
 363         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 364
 365         if (was_sourced)
 366             fib_entry_special_update(fib_entry_index, source, flags, dpo);
 367         else
 368             fib_entry_special_add(fib_entry_index, source, flags, dpo);
 369
 370         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 371         {
 372             fib_table->ft_src_route_counts[source]++;
 373         }
 374     }
 375
 376     return (fib_entry_index);
 377 }
 378
 379 fib_node_index_t
 380 fib_table_entry_special_add (u32 fib_index,
 381                              const fib_prefix_t *prefix,
 382                              fib_source_t source,
 383                              fib_entry_flag_t flags)
 384 {
 385     fib_node_index_t fib_entry_index;
 386     dpo_id_t tmp_dpo = DPO_INVALID;
 387
 388     dpo_copy(&tmp_dpo, drop_dpo_get(fib_proto_to_dpo(prefix->fp_proto)));
 389
 390     fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix, source,
 391                                                       flags, &tmp_dpo);
 392
 393     dpo_unlock(&tmp_dpo);
 394
 395     return (fib_entry_index);
 396 }
 397
 398 void
 399 fib_table_entry_special_remove (u32 fib_index,
 400                                 const fib_prefix_t *prefix,
 401                                 fib_source_t source)
 402 {
 403     /*
 404      * 1 is it present
 405      *   yes => remove source
 406      *    2 - is it still sourced?
 407      *      no => cover walk
 408      */
 409     fib_node_index_t fib_entry_index;
 410     fib_table_t *fib_table;
 411
 412     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 413     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 414
 415     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 416     {
 417         /*
 418          * removing an etry that does not exist. i'll allow it.
 419          */
 420     }
 421     else
 422     {
 423         fib_entry_src_flag_t src_flag;
 424         int was_sourced;
 425
 426         /*
 427          * don't nobody go nowhere
 428          */
 429         fib_entry_lock(fib_entry_index);
 430         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 431
 432         src_flag = fib_entry_special_remove(fib_entry_index, source);
 433
 434         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 435         {
 436             /*
 437              * last source gone. remove from the table
 438              */
 439             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 440
 441             /*
 442              * now the entry is no longer in the table, we can
 443              * inform the entries that it covers to re-calculate their cover
 444              */
 445             fib_entry_cover_change_notify(fib_entry_index,
 446                                           FIB_NODE_INDEX_INVALID);
 447         }
 448         /*
 449          * else
 450          *   still has sources, leave it be.
 451          */
 452         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 453         {
 454             fib_table->ft_src_route_counts[source]--;
 455         }
 456
 457         fib_entry_unlock(fib_entry_index);
 458     }
 459 }
 460
 461 /**
 462  * fib_table_route_path_fixup
 463  *
 464  * Convert attached hosts to attached next-hops.
 465  *
 466  * This special case is required because an attached path will link to a
 467  * glean, and the FIB entry will have the interface or API/CLI source. When
 468  * the ARP/ND process is completes then that source (which will provide a
 469  * complete adjacency) will be lower priority and so the FIB entry will
 470  * remain linked to a glean and traffic will never reach the hosts. For
 471  * an ATTAHCED_HOST path we can link the path directly to the [incomplete]
 472  * adjacency.
 473  */
 474 static void
 475 fib_table_route_path_fixup (const fib_prefix_t *prefix,
 476                             fib_entry_flag_t eflags,
 477                             fib_route_path_t *path)
 478 {
 479     /*
 480      * not all zeros next hop &&
 481      * is recursive path &&
 482      * nexthop is same as the route's address
 483      */
 484     if ((!ip46_address_is_zero(&path->frp_addr)) &&
 485         (~0 == path->frp_sw_if_index) &&
 486         (0 == ip46_address_cmp(&path->frp_addr, &prefix->fp_addr)))
 487     {
 488         /* Prefix recurses via itse;f */
 489         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 490     }
 491     if (fib_prefix_is_host(prefix) &&
 492         ip46_address_is_zero(&path->frp_addr) &&
 493         path->frp_sw_if_index != ~0 &&
 494         path->frp_proto != DPO_PROTO_ETHERNET)
 495     {
 496         path->frp_addr = prefix->fp_addr;
 497         path->frp_flags |= FIB_ROUTE_PATH_ATTACHED;
 498     }
 499     if (eflags & FIB_ENTRY_FLAG_DROP)
 500     {
 501         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 502     }
 503     if (eflags & FIB_ENTRY_FLAG_LOCAL)
 504     {
 505         path->frp_flags |= FIB_ROUTE_PATH_LOCAL;
 506     }
 507     if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
 508     {
 509         path->frp_flags |= FIB_ROUTE_PATH_EXCLUSIVE;
 510     }
 511 }
 512
 513 fib_node_index_t
 514 fib_table_entry_path_add (u32 fib_index,
 515                           const fib_prefix_t *prefix,
 516                           fib_source_t source,
 517                           fib_entry_flag_t flags,
 518                           dpo_proto_t next_hop_proto,
 519                           const ip46_address_t *next_hop,
 520                           u32 next_hop_sw_if_index,
 521                           u32 next_hop_fib_index,
 522                           u32 next_hop_weight,
 523                           fib_mpls_label_t *next_hop_labels,
 524                           fib_route_path_flags_t path_flags)
 525 {
 526     fib_route_path_t path = {
 527         .frp_proto = next_hop_proto,
 528         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 529         .frp_sw_if_index = next_hop_sw_if_index,
 530         .frp_fib_index = next_hop_fib_index,
 531         .frp_weight = next_hop_weight,
 532         .frp_flags = path_flags,
 533         .frp_label_stack = next_hop_labels,
 534     };
 535     fib_node_index_t fib_entry_index;
 536     fib_route_path_t *paths = NULL;
 537
 538     vec_add1(paths, path);
 539
 540     fib_entry_index = fib_table_entry_path_add2(fib_index, prefix,
 541                                                 source, flags, paths);
 542
 543     vec_free(paths);
 544     return (fib_entry_index);
 545 }
 546
 547 fib_node_index_t
 548 fib_table_entry_path_add2 (u32 fib_index,
 549                            const fib_prefix_t *prefix,
 550                            fib_source_t source,
 551                            fib_entry_flag_t flags,
 552                            fib_route_path_t *rpath)
 553 {
 554     fib_node_index_t fib_entry_index;
 555     fib_table_t *fib_table;
 556     u32 ii;
 557
 558     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 559     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 560
 561     for (ii = 0; ii < vec_len(rpath); ii++)
 562     {
 563         fib_table_route_path_fixup(prefix, flags, &rpath[ii]);
 564     }
 565
 566     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 567     {
 568         fib_entry_index = fib_entry_create(fib_index, prefix,
 569                                            source, flags,
 570                                            rpath);
 571
 572         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 573         fib_table->ft_src_route_counts[source]++;
 574     }
 575     else
 576     {
 577         int was_sourced;
 578
 579         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 580         fib_entry_path_add(fib_entry_index, source, flags, rpath);;
 581
 582         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 583         {
 584             fib_table->ft_src_route_counts[source]++;
 585         }
 586     }
 587
 588     return (fib_entry_index);
 589 }
 590
 591 void
 592 fib_table_entry_path_remove2 (u32 fib_index,
 593                               const fib_prefix_t *prefix,
 594                               fib_source_t source,
 595                               fib_route_path_t *rpath)
 596 {
 597     /*
 598      * 1 is it present
 599      *   yes => remove source
 600      *    2 - is it still sourced?
 601      *      no => cover walk
 602      */
 603     fib_node_index_t fib_entry_index;
 604     fib_table_t *fib_table;
 605     u32 ii;
 606
 607     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 608     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 609
 610     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 611     {
 612         /*
 613          * removing an etry that does not exist. i'll allow it.
 614          */
 615     }
 616     else
 617     {
 618         fib_entry_src_flag_t src_flag;
 619         int was_sourced;
 620
 621         /*
 622          * if it's not sourced, then there's nowt to remove
 623          */
 624         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 625         if (!was_sourced)
 626         {
 627             return;
 628         }
 629
 630         /*
 631          * don't nobody go nowhere
 632          */
 633         fib_entry_lock(fib_entry_index);
 634
 635         for (ii = 0; ii < vec_len(rpath); ii++)
 636         {
 637             fib_table_route_path_fixup(
 638                 prefix,
 639                 fib_entry_get_flags_for_source(fib_entry_index,
 640                                                source),
 641                 &rpath[ii]);
 642         }
 643
 644         src_flag = fib_entry_path_remove(fib_entry_index, source, rpath);
 645
 646         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 647         {
 648             /*
 649              * last source gone. remove from the table
 650              */
 651             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 652
 653             /*
 654              * now the entry is no longer in the table, we can
 655              * inform the entries that it covers to re-calculate their cover
 656              */
 657             fib_entry_cover_change_notify(fib_entry_index,
 658                                           FIB_NODE_INDEX_INVALID);
 659         }
 660         /*
 661          * else
 662          *   still has sources, leave it be.
 663          */
 664         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 665         {
 666             fib_table->ft_src_route_counts[source]--;
 667         }
 668
 669         fib_entry_unlock(fib_entry_index);
 670     }
 671 }
 672
 673 void
 674 fib_table_entry_path_remove (u32 fib_index,
 675                              const fib_prefix_t *prefix,
 676                              fib_source_t source,
 677                              dpo_proto_t next_hop_proto,
 678                              const ip46_address_t *next_hop,
 679                              u32 next_hop_sw_if_index,
 680                              u32 next_hop_fib_index,
 681                              u32 next_hop_weight,
 682                              fib_route_path_flags_t path_flags)
 683 {
 684     /*
 685      * 1 is it present
 686      *   yes => remove source
 687      *    2 - is it still sourced?
 688      *      no => cover walk
 689      */
 690     fib_route_path_t path = {
 691         .frp_proto = next_hop_proto,
 692         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 693         .frp_sw_if_index = next_hop_sw_if_index,
 694         .frp_fib_index = next_hop_fib_index,
 695         .frp_weight = next_hop_weight,
 696         .frp_flags = path_flags,
 697     };
 698     fib_route_path_t *paths = NULL;
 699
 700     vec_add1(paths, path);
 701
 702     fib_table_entry_path_remove2(fib_index, prefix, source, paths);
 703
 704     vec_free(paths);
 705 }
 706
 707 static int
 708 fib_route_path_cmp_for_sort (void * v1,
 709                              void * v2)
 710 {
 711     return (fib_route_path_cmp(v1, v2));
 712 }
 713
 714 fib_node_index_t
 715 fib_table_entry_update (u32 fib_index,
 716                         const fib_prefix_t *prefix,
 717                         fib_source_t source,
 718                         fib_entry_flag_t flags,
 719                         fib_route_path_t *paths)
 720 {
 721     fib_node_index_t fib_entry_index;
 722     fib_table_t *fib_table;
 723     u32 ii;
 724
 725     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 726     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 727
 728     for (ii = 0; ii < vec_len(paths); ii++)
 729     {
 730         fib_table_route_path_fixup(prefix, flags, &paths[ii]);
 731     }
 732     /*
 733      * sort the paths provided by the control plane. this means
 734      * the paths and the extension on the entry will be sorted.
 735      */
 736     vec_sort_with_function(paths, fib_route_path_cmp_for_sort);
 737
 738     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 739     {
 740         fib_entry_index = fib_entry_create(fib_index, prefix,
 741                                            source, flags,
 742                                            paths);
 743
 744         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 745         fib_table->ft_src_route_counts[source]++;
 746     }
 747     else
 748     {
 749         int was_sourced;
 750
 751         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 752         fib_entry_update(fib_entry_index, source, flags, paths);
 753
 754         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 755         {
 756             fib_table->ft_src_route_counts[source]++;
 757         }
 758     }
 759
 760     return (fib_entry_index);
 761 }
 762
 763 fib_node_index_t
 764 fib_table_entry_update_one_path (u32 fib_index,
 765                                  const fib_prefix_t *prefix,
 766                                  fib_source_t source,
 767                                  fib_entry_flag_t flags,
 768                                  dpo_proto_t next_hop_proto,
 769                                  const ip46_address_t *next_hop,
 770                                  u32 next_hop_sw_if_index,
 771                                  u32 next_hop_fib_index,
 772                                  u32 next_hop_weight,
 773                                  fib_mpls_label_t *next_hop_labels,
 774                                  fib_route_path_flags_t path_flags)
 775 {
 776     fib_node_index_t fib_entry_index;
 777     fib_route_path_t path = {
 778         .frp_proto = next_hop_proto,
 779         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 780         .frp_sw_if_index = next_hop_sw_if_index,
 781         .frp_fib_index = next_hop_fib_index,
 782         .frp_weight = next_hop_weight,
 783         .frp_flags = path_flags,
 784         .frp_label_stack = next_hop_labels,
 785     };
 786     fib_route_path_t *paths = NULL;
 787
 788     vec_add1(paths, path);
 789
 790     fib_entry_index =
 791         fib_table_entry_update(fib_index, prefix, source, flags, paths);
 792
 793     vec_free(paths);
 794
 795     return (fib_entry_index);
 796 }
 797
 798 static void
 799 fib_table_entry_delete_i (u32 fib_index,
 800                           fib_node_index_t fib_entry_index,
 801                           const fib_prefix_t *prefix,
 802                           fib_source_t source)
 803 {
 804     fib_entry_src_flag_t src_flag;
 805     fib_table_t *fib_table;
 806     int was_sourced;
 807
 808     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 809     was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 810
 811     /*
 812      * don't nobody go nowhere
 813      */
 814     fib_entry_lock(fib_entry_index);
 815
 816     src_flag = fib_entry_delete(fib_entry_index, source);
 817
 818     if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 819     {
 820         /*
 821          * last source gone. remove from the table
 822          */
 823         fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 824
 825         /*
 826          * now the entry is no longer in the table, we can
 827          * inform the entries that it covers to re-calculate their cover
 828          */
 829         fib_entry_cover_change_notify(fib_entry_index,
 830                                       FIB_NODE_INDEX_INVALID);
 831     }
 832     /*
 833      * else
 834      *   still has sources, leave it be.
 835      */
 836     if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 837     {
 838         fib_table->ft_src_route_counts[source]--;
 839     }
 840
 841     fib_entry_unlock(fib_entry_index);
 842 }
 843
 844 void
 845 fib_table_entry_delete (u32 fib_index,
 846                         const fib_prefix_t *prefix,
 847                         fib_source_t source)
 848 {
 849     fib_node_index_t fib_entry_index;
 850
 851     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 852
 853     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 854     {
 855         /*
 856          * removing an etry that does not exist.
 857          * i'll allow it, but i won't like it.
 858          */
 859         if (0)
 860             clib_warning("%U not in FIB", format_fib_prefix, prefix);
 861     }
 862     else
 863     {
 864         fib_table_entry_delete_i(fib_index, fib_entry_index, prefix, source);
 865     }
 866 }
 867
 868 void
 869 fib_table_entry_delete_index (fib_node_index_t fib_entry_index,
 870                               fib_source_t source)
 871 {
 872     fib_prefix_t prefix;
 873
 874     fib_entry_get_prefix(fib_entry_index, &prefix);
 875
 876     fib_table_entry_delete_i(fib_entry_get_fib_index(fib_entry_index),
 877                              fib_entry_index, &prefix, source);
 878 }
 879
 880 fib_node_index_t
 881 fib_table_entry_local_label_add (u32 fib_index,
 882                                  const fib_prefix_t *prefix,
 883                                  mpls_label_t label)
 884 {
 885     fib_node_index_t fib_entry_index;
 886
 887     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 888
 889     if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
 890         !fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
 891     {
 892         /*
 893          * only source the prefix once. this allows the label change
 894          * operation to work
 895          */
 896         fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
 897                                                           FIB_SOURCE_MPLS,
 898                                                           FIB_ENTRY_FLAG_NONE,
 899                                                           NULL);
 900     }
 901
 902     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);
 903
 904     return (fib_entry_index);
 905 }
 906
 907 void
 908 fib_table_entry_local_label_remove (u32 fib_index,
 909                                     const fib_prefix_t *prefix,
 910                                     mpls_label_t label)
 911 {
 912     fib_node_index_t fib_entry_index;
 913     const void *data;
 914     mpls_label_t pl;
 915
 916     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 917
 918     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 919         return;
 920
 921     data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);
 922
 923     if (NULL == data)
 924         return;
 925
 926     pl = *(mpls_label_t*)data;
 927
 928     if (pl != label)
 929         return;
 930
 931     pl = MPLS_LABEL_INVALID;
 932
 933     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
 934     fib_table_entry_special_remove(fib_index,
 935                                    prefix,
 936                                    FIB_SOURCE_MPLS);
 937 }
 938
 939 u32
 940 fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
 941                                      u32 sw_if_index)
 942 {
 943     switch (proto)
 944     {
 945     case FIB_PROTOCOL_IP4:
 946         return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
 947     case FIB_PROTOCOL_IP6:
 948         return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
 949     case FIB_PROTOCOL_MPLS:
 950         return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
 951     }
 952     return (~0);
 953 }
 954
 955 flow_hash_config_t
 956 fib_table_get_flow_hash_config (u32 fib_index,
 957                                 fib_protocol_t proto)
 958 {
 959     fib_table_t *fib;
 960
 961     fib = fib_table_get(fib_index, proto);
 962
 963     return (fib->ft_flow_hash_config);
 964 }
 965
 966 flow_hash_config_t
 967 fib_table_get_default_flow_hash_config (fib_protocol_t proto)
 968 {
 969     switch (proto)
 970     {
 971     case FIB_PROTOCOL_IP4:
 972     case FIB_PROTOCOL_IP6:
 973         return (IP_FLOW_HASH_DEFAULT);
 974
 975     case FIB_PROTOCOL_MPLS:
 976         return (MPLS_FLOW_HASH_DEFAULT);
 977     }
 978
 979     ASSERT(0);
 980     return (IP_FLOW_HASH_DEFAULT);
 981 }
 982
 983 /**
 984  * @brief Table set flow hash config context.
 985  */
 986 typedef struct fib_table_set_flow_hash_config_ctx_t_
 987 {
 988     /**
 989      * the flow hash config to set
 990      */
 991     flow_hash_config_t hash_config;
 992 } fib_table_set_flow_hash_config_ctx_t;
 993
 994 static fib_table_walk_rc_t
 995 fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index,
 996                                    void *arg)
 997 {
 998     fib_table_set_flow_hash_config_ctx_t *ctx = arg;
 999
1000     fib_entry_set_flow_hash_config(fib_entry_index, ctx->hash_config);
1001
1002     return (FIB_TABLE_WALK_CONTINUE);
1003 }
1004
1005 void
1006 fib_table_set_flow_hash_config (u32 fib_index,
1007                                 fib_protocol_t proto,
1008                                 flow_hash_config_t hash_config)
1009 {
1010     fib_table_set_flow_hash_config_ctx_t ctx = {
1011         .hash_config = hash_config,
1012     };
1013     fib_table_t *fib;
1014
1015     fib = fib_table_get(fib_index, proto);
1016     fib->ft_flow_hash_config = hash_config;
1017
1018     fib_table_walk(fib_index, proto,
1019                    fib_table_set_flow_hash_config_cb,
1020                    &ctx);
1021 }
1022
1023 u32
1024 fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
1025                                         u32 sw_if_index)
1026 {
1027     fib_table_t *fib_table;
1028
1029     fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
1030                                   proto, sw_if_index),
1031                               proto);
1032
1033     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1034 }
1035
1036 u32
1037 fib_table_find (fib_protocol_t proto,
1038                 u32 table_id)
1039 {
1040     switch (proto)
1041     {
1042     case FIB_PROTOCOL_IP4:
1043         return (ip4_fib_index_from_table_id(table_id));
1044     case FIB_PROTOCOL_IP6:
1045         return (ip6_fib_index_from_table_id(table_id));
1046     case FIB_PROTOCOL_MPLS:
1047         return (mpls_fib_index_from_table_id(table_id));
1048     }
1049     return (~0);
1050 }
1051
1052 static u32
1053 fib_table_find_or_create_and_lock_i (fib_protocol_t proto,
1054                                      u32 table_id,
1055                                      fib_source_t src,
1056                                      const u8 *name)
1057 {
1058     fib_table_t *fib_table;
1059     fib_node_index_t fi;
1060
1061     switch (proto)
1062     {
1063     case FIB_PROTOCOL_IP4:
1064         fi = ip4_fib_table_find_or_create_and_lock(table_id, src);
1065         break;
1066     case FIB_PROTOCOL_IP6:
1067         fi = ip6_fib_table_find_or_create_and_lock(table_id, src);
1068         break;
1069     case FIB_PROTOCOL_MPLS:
1070         fi = mpls_fib_table_find_or_create_and_lock(table_id, src);
1071         break;
1072     default:
1073         return (~0);
1074     }
1075
1076     fib_table = fib_table_get(fi, proto);
1077
1078     if (NULL == fib_table->ft_desc)
1079     {
1080         if (name && name[0])
1081         {
1082             fib_table->ft_desc = format(NULL, "%s", name);
1083         }
1084         else
1085         {
1086             fib_table->ft_desc = format(NULL, "%U-VRF:%d",
1087                                         format_fib_protocol, proto,
1088                                         table_id);
1089         }
1090     }
1091
1092     return (fi);
1093 }
1094
1095 u32
1096 fib_table_find_or_create_and_lock (fib_protocol_t proto,
1097                                    u32 table_id,
1098                                    fib_source_t src)
1099 {
1100     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1101                                                 src, NULL));
1102 }
1103
1104 u32
1105 fib_table_find_or_create_and_lock_w_name (fib_protocol_t proto,
1106                                           u32 table_id,
1107                                           fib_source_t src,
1108                                           const u8 *name)
1109 {
1110     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1111                                                 src, name));
1112 }
1113
1114 u32
1115 fib_table_create_and_lock (fib_protocol_t proto,
1116                            fib_source_t src,
1117                            const char *const fmt,
1118                            ...)
1119 {
1120     fib_table_t *fib_table;
1121     fib_node_index_t fi;
1122     va_list ap;
1123
1124     va_start(ap, fmt);
1125
1126     switch (proto)
1127     {
1128     case FIB_PROTOCOL_IP4:
1129         fi = ip4_fib_table_create_and_lock(src);
1130         break;
1131     case FIB_PROTOCOL_IP6:
1132         fi = ip6_fib_table_create_and_lock(src, FIB_TABLE_FLAG_NONE, NULL);
1133         break;
1134      case FIB_PROTOCOL_MPLS:
1135         fi = mpls_fib_table_create_and_lock(src);
1136         break;
1137    default:
1138         return (~0);
1139     }
1140
1141     fib_table = fib_table_get(fi, proto);
1142
1143     fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);
1144
1145     va_end(ap);
1146     return (fi);
1147 }
1148
1149 static void
1150 fib_table_destroy (fib_table_t *fib_table)
1151 {
1152     vec_free(fib_table->ft_desc);
1153
1154     switch (fib_table->ft_proto)
1155     {
1156     case FIB_PROTOCOL_IP4:
1157         ip4_fib_table_destroy(fib_table->ft_index);
1158         break;
1159     case FIB_PROTOCOL_IP6:
1160         ip6_fib_table_destroy(fib_table->ft_index);
1161         break;
1162     case FIB_PROTOCOL_MPLS:
1163         mpls_fib_table_destroy(fib_table->ft_index);
1164         break;
1165     }
1166 }
1167
1168 void
1169 fib_table_walk (u32 fib_index,
1170                 fib_protocol_t proto,
1171                 fib_table_walk_fn_t fn,
1172                 void *ctx)
1173 {
1174     switch (proto)
1175     {
1176     case FIB_PROTOCOL_IP4:
1177         ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
1178         break;
1179     case FIB_PROTOCOL_IP6:
1180         ip6_fib_table_walk(fib_index, fn, ctx);
1181         break;
1182     case FIB_PROTOCOL_MPLS:
1183         mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
1184         break;
1185     }
1186 }
1187
1188 void
1189 fib_table_sub_tree_walk (u32 fib_index,
1190                          fib_protocol_t proto,
1191                          const fib_prefix_t *root,
1192                          fib_table_walk_fn_t fn,
1193                          void *ctx)
1194 {
1195     switch (proto)
1196     {
1197     case FIB_PROTOCOL_IP4:
1198         ip4_fib_table_sub_tree_walk(ip4_fib_get(fib_index), root, fn, ctx);
1199         break;
1200     case FIB_PROTOCOL_IP6:
1201         ip6_fib_table_sub_tree_walk(fib_index, root, fn, ctx);
1202         break;
1203     case FIB_PROTOCOL_MPLS:
1204         break;
1205     }
1206 }
1207
1208 void
1209 fib_table_unlock (u32 fib_index,
1210                   fib_protocol_t proto,
1211                   fib_source_t source)
1212 {
1213     fib_table_t *fib_table;
1214
1215     fib_table = fib_table_get(fib_index, proto);
1216     fib_table->ft_locks[source]--;
1217     fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS]--;
1218
1219     if (0 == fib_table->ft_locks[source])
1220     {
1221         /*
1222          * The source no longer needs the table. flush any routes
1223          * from it just in case
1224          */
1225         fib_table_flush(fib_index, proto, source);
1226     }
1227
1228     if (0 == fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS])
1229     {
1230         /*
1231          * no more locak from any source - kill it
1232          */
1233         fib_table_destroy(fib_table);
1234     }
1235 }
1236
1237 void
1238 fib_table_lock (u32 fib_index,
1239                 fib_protocol_t proto,
1240                 fib_source_t source)
1241 {
1242     fib_table_t *fib_table;
1243
1244     fib_table = fib_table_get(fib_index, proto);
1245     fib_table->ft_locks[source]++;
1246     fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS]++;
1247 }
1248
1249 u32
1250 fib_table_get_num_entries (u32 fib_index,
1251                            fib_protocol_t proto,
1252                            fib_source_t source)
1253 {
1254     fib_table_t *fib_table;
1255
1256     fib_table = fib_table_get(fib_index, proto);
1257
1258     return (fib_table->ft_src_route_counts[source]);
1259 }
1260
1261 u8*
1262 format_fib_table_name (u8* s, va_list* ap)
1263 {
1264     fib_node_index_t fib_index = va_arg(*ap, fib_node_index_t);
1265     fib_protocol_t proto = va_arg(*ap, int); // int promotion
1266     fib_table_t *fib_table;
1267
1268     fib_table = fib_table_get(fib_index, proto);
1269
1270     s = format(s, "%v", fib_table->ft_desc);
1271
1272     return (s);
1273 }
1274
1275 /**
1276  * @brief Table flush context. Store the indicies of matching FIB entries
1277  * that need to be removed.
1278  */
1279 typedef struct fib_table_flush_ctx_t_
1280 {
1281     /**
1282      * The list of entries to flush
1283      */
1284     fib_node_index_t *ftf_entries;
1285
1286     /**
1287      * The source we are flushing
1288      */
1289     fib_source_t ftf_source;
1290 } fib_table_flush_ctx_t;
1291
1292 static fib_table_walk_rc_t
1293 fib_table_flush_cb (fib_node_index_t fib_entry_index,
1294                     void *arg)
1295 {
1296     fib_table_flush_ctx_t *ctx = arg;
1297
1298     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1299     {
1300         vec_add1(ctx->ftf_entries, fib_entry_index);
1301     }
1302     return (FIB_TABLE_WALK_CONTINUE);
1303 }
1304
1305
1306 void
1307 fib_table_flush (u32 fib_index,
1308                  fib_protocol_t proto,
1309                  fib_source_t source)
1310 {
1311     fib_node_index_t *fib_entry_index;
1312     fib_table_flush_ctx_t ctx = {
1313         .ftf_entries = NULL,
1314         .ftf_source = source,
1315     };
1316
1317     fib_table_walk(fib_index, proto,
1318                    fib_table_flush_cb,
1319                    &ctx);
1320
1321     vec_foreach(fib_entry_index, ctx.ftf_entries)
1322     {
1323         fib_table_entry_delete_index(*fib_entry_index, source);
1324     }
1325
1326     vec_free(ctx.ftf_entries);
1327 }
1328
1329 u8 *
1330 format_fib_table_memory (u8 *s, va_list *args)
1331 {
1332     s = format(s, "%U", format_ip4_fib_table_memory);
1333     s = format(s, "%U", format_ip6_fib_table_memory);
1334     s = format(s, "%U", format_mpls_fib_table_memory);
1335
1336     return (s);
1337 }