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(&fib_table->v4,
  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(&fib_table->mpls,
  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(&fib_table->v4,
  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(&fib_table->mpls,
  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(&fib_table->v4,
 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(&fib_table->mpls,
 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 and inform the covering entry that a new more specific
 185      * has been inserted beneath it
 186      */
 187     fib_entry_cover_index = fib_table_get_less_specific_i(fib_table, prefix);
 188     /*
 189      * the indicies are the same when the default route is first added
 190      */
 191     if (fib_entry_cover_index != fib_entry_index)
 192     {
 193         fib_entry_cover_change_notify(fib_entry_cover_index,
 194                                       fib_entry_index);
 195     }
 196 }
 197
 198 static void
 199 fib_table_entry_insert (fib_table_t *fib_table,
 200                         const fib_prefix_t *prefix,
 201                         fib_node_index_t fib_entry_index)
 202 {
 203     vlib_smp_unsafe_warning();
 204
 205     fib_entry_lock(fib_entry_index);
 206     fib_table->ft_total_route_counts++;
 207
 208     switch (prefix->fp_proto)
 209     {
 210     case FIB_PROTOCOL_IP4:
 211         ip4_fib_table_entry_insert(&fib_table->v4,
 212                                    &prefix->fp_addr.ip4,
 213                                    prefix->fp_len,
 214                                    fib_entry_index);
 215         break;
 216     case FIB_PROTOCOL_IP6:
 217         ip6_fib_table_entry_insert(fib_table->ft_index,
 218                                    &prefix->fp_addr.ip6,
 219                                    prefix->fp_len,
 220                                    fib_entry_index);
 221         break;
 222     case FIB_PROTOCOL_MPLS:
 223         mpls_fib_table_entry_insert(&fib_table->mpls,
 224                                     prefix->fp_label,
 225                                     prefix->fp_eos,
 226                                     fib_entry_index);
 227         break;
 228     }
 229
 230     fib_table_post_insert_actions(fib_table, prefix, fib_entry_index);
 231 }
 232
 233 void
 234 fib_table_fwding_dpo_update (u32 fib_index,
 235                              const fib_prefix_t *prefix,
 236                              const dpo_id_t *dpo)
 237 {
 238     vlib_smp_unsafe_warning();
 239
 240     switch (prefix->fp_proto)
 241     {
 242     case FIB_PROTOCOL_IP4:
 243         return (ip4_fib_table_fwding_dpo_update(ip4_fib_get(fib_index),
 244                                                 &prefix->fp_addr.ip4,
 245                                                 prefix->fp_len,
 246                                                 dpo));
 247     case FIB_PROTOCOL_IP6:
 248         return (ip6_fib_table_fwding_dpo_update(fib_index,
 249                                                 &prefix->fp_addr.ip6,
 250                                                 prefix->fp_len,
 251                                                 dpo));
 252     case FIB_PROTOCOL_MPLS:
 253         return (mpls_fib_forwarding_table_update(mpls_fib_get(fib_index),
 254                                                  prefix->fp_label,
 255                                                  prefix->fp_eos,
 256                                                  dpo));
 257     }
 258 }
 259
 260 void
 261 fib_table_fwding_dpo_remove (u32 fib_index,
 262                              const fib_prefix_t *prefix,
 263                              const dpo_id_t *dpo)
 264 {
 265     vlib_smp_unsafe_warning();
 266
 267     switch (prefix->fp_proto)
 268     {
 269     case FIB_PROTOCOL_IP4:
 270         return (ip4_fib_table_fwding_dpo_remove(ip4_fib_get(fib_index),
 271                                                 &prefix->fp_addr.ip4,
 272                                                 prefix->fp_len,
 273                                                 dpo));
 274     case FIB_PROTOCOL_IP6:
 275         return (ip6_fib_table_fwding_dpo_remove(fib_index,
 276                                                 &prefix->fp_addr.ip6,
 277                                                 prefix->fp_len,
 278                                                 dpo));
 279     case FIB_PROTOCOL_MPLS:
 280         return (mpls_fib_forwarding_table_reset(mpls_fib_get(fib_index),
 281                                                 prefix->fp_label,
 282                                                 prefix->fp_eos));
 283     }
 284 }
 285
 286
 287 fib_node_index_t
 288 fib_table_entry_special_dpo_add (u32 fib_index,
 289                                  const fib_prefix_t *prefix,
 290                                  fib_source_t source,
 291                                  fib_entry_flag_t flags,
 292                                  const dpo_id_t *dpo)
 293 {
 294     fib_node_index_t fib_entry_index;
 295     fib_table_t *fib_table;
 296
 297     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 298     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 299
 300     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 301     {
 302         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 303                                                    source, flags,
 304                                                    dpo);
 305
 306         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 307         fib_table->ft_src_route_counts[source]++;
 308     }
 309     else
 310     {
 311         int was_sourced;
 312
 313         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 314         fib_entry_special_add(fib_entry_index, source, flags, dpo);
 315
 316         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 317         {
 318             fib_table->ft_src_route_counts[source]++;
 319         }
 320     }
 321
 322
 323     return (fib_entry_index);
 324 }
 325
 326 fib_node_index_t
 327 fib_table_entry_special_dpo_update (u32 fib_index,
 328                                     const fib_prefix_t *prefix,
 329                                     fib_source_t source,
 330                                     fib_entry_flag_t flags,
 331                                     const dpo_id_t *dpo)
 332 {
 333     fib_node_index_t fib_entry_index;
 334     fib_table_t *fib_table;
 335
 336     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 337     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 338
 339     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 340     {
 341         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 342                                                    source, flags,
 343                                                    dpo);
 344
 345         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 346         fib_table->ft_src_route_counts[source]++;
 347     }
 348     else
 349     {
 350         int was_sourced;
 351
 352         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 353
 354         if (was_sourced)
 355             fib_entry_special_update(fib_entry_index, source, flags, dpo);
 356         else
 357             fib_entry_special_add(fib_entry_index, source, flags, dpo);
 358
 359         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 360         {
 361             fib_table->ft_src_route_counts[source]++;
 362         }
 363     }
 364
 365     return (fib_entry_index);
 366 }
 367
 368 fib_node_index_t
 369 fib_table_entry_special_add (u32 fib_index,
 370                              const fib_prefix_t *prefix,
 371                              fib_source_t source,
 372                              fib_entry_flag_t flags,
 373                              adj_index_t adj_index)
 374 {
 375     fib_node_index_t fib_entry_index;
 376     dpo_id_t tmp_dpo = DPO_INVALID;
 377
 378     if (ADJ_INDEX_INVALID != adj_index)
 379     {
 380         dpo_set(&tmp_dpo,
 381                 DPO_ADJACENCY,
 382                 FIB_PROTOCOL_MAX,
 383                 adj_index);
 384     }
 385     else
 386     {
 387         dpo_copy(&tmp_dpo, drop_dpo_get(fib_proto_to_dpo(prefix->fp_proto)));
 388     }
 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_route_path_t *path)
 477 {
 478     if (fib_prefix_is_host(prefix) &&
 479         ip46_address_is_zero(&path->frp_addr) &&
 480         path->frp_sw_if_index != ~0)
 481     {
 482         path->frp_addr = prefix->fp_addr;
 483         path->frp_flags |= FIB_ROUTE_PATH_ATTACHED;
 484     }
 485 }
 486
 487 fib_node_index_t
 488 fib_table_entry_path_add (u32 fib_index,
 489                           const fib_prefix_t *prefix,
 490                           fib_source_t source,
 491                           fib_entry_flag_t flags,
 492                           fib_protocol_t next_hop_proto,
 493                           const ip46_address_t *next_hop,
 494                           u32 next_hop_sw_if_index,
 495                           u32 next_hop_fib_index,
 496                           u32 next_hop_weight,
 497                           mpls_label_t *next_hop_labels,
 498                           fib_route_path_flags_t path_flags)
 499 {
 500     fib_route_path_t path = {
 501         .frp_proto = next_hop_proto,
 502         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 503         .frp_sw_if_index = next_hop_sw_if_index,
 504         .frp_fib_index = next_hop_fib_index,
 505         .frp_weight = next_hop_weight,
 506         .frp_flags = path_flags,
 507         .frp_label_stack = next_hop_labels,
 508     };
 509     fib_node_index_t fib_entry_index;
 510     fib_route_path_t *paths = NULL;
 511
 512     vec_add1(paths, path);
 513
 514     fib_entry_index = fib_table_entry_path_add2(fib_index, prefix,
 515                                                 source, flags, paths);
 516
 517     vec_free(paths);
 518     return (fib_entry_index);
 519 }
 520
 521 fib_node_index_t
 522 fib_table_entry_path_add2 (u32 fib_index,
 523                            const fib_prefix_t *prefix,
 524                            fib_source_t source,
 525                            fib_entry_flag_t flags,
 526                            fib_route_path_t *rpath)
 527 {
 528     fib_node_index_t fib_entry_index;
 529     fib_table_t *fib_table;
 530     u32 ii;
 531
 532     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 533     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 534
 535     for (ii = 0; ii < vec_len(rpath); ii++)
 536     {
 537         fib_table_route_path_fixup(prefix, &rpath[ii]);
 538     }
 539
 540     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 541     {
 542         fib_entry_index = fib_entry_create(fib_index, prefix,
 543                                            source, flags,
 544                                            rpath);
 545
 546         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 547         fib_table->ft_src_route_counts[source]++;
 548     }
 549     else
 550     {
 551         int was_sourced;
 552
 553         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 554         fib_entry_path_add(fib_entry_index, source, flags, rpath);;
 555
 556         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 557         {
 558             fib_table->ft_src_route_counts[source]++;
 559         }
 560     }
 561
 562     return (fib_entry_index);
 563 }
 564
 565 void
 566 fib_table_entry_path_remove2 (u32 fib_index,
 567                               const fib_prefix_t *prefix,
 568                               fib_source_t source,
 569                               fib_route_path_t *rpath)
 570 {
 571     /*
 572      * 1 is it present
 573      *   yes => remove source
 574      *    2 - is it still sourced?
 575      *      no => cover walk
 576      */
 577     fib_node_index_t fib_entry_index;
 578     fib_table_t *fib_table;
 579     u32 ii;
 580
 581     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 582     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 583
 584     for (ii = 0; ii < vec_len(rpath); ii++)
 585     {
 586         fib_table_route_path_fixup(prefix, &rpath[ii]);
 587     }
 588
 589     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 590     {
 591         /*
 592          * removing an etry that does not exist. i'll allow it.
 593          */
 594     }
 595     else
 596     {
 597         fib_entry_src_flag_t src_flag;
 598         int was_sourced;
 599
 600         /*
 601          * don't nobody go nowhere
 602          */
 603         fib_entry_lock(fib_entry_index);
 604         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 605
 606         src_flag = fib_entry_path_remove(fib_entry_index, source, rpath);
 607
 608         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 609         {
 610             /*
 611              * last source gone. remove from the table
 612              */
 613             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 614
 615             /*
 616              * now the entry is no longer in the table, we can
 617              * inform the entries that it covers to re-calculate their cover
 618              */
 619             fib_entry_cover_change_notify(fib_entry_index,
 620                                           FIB_NODE_INDEX_INVALID);
 621         }
 622         /*
 623          * else
 624          *   still has sources, leave it be.
 625          */
 626         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 627         {
 628             fib_table->ft_src_route_counts[source]--;
 629         }
 630
 631         fib_entry_unlock(fib_entry_index);
 632     }
 633 }
 634
 635 void
 636 fib_table_entry_path_remove (u32 fib_index,
 637                              const fib_prefix_t *prefix,
 638                              fib_source_t source,
 639                              fib_protocol_t next_hop_proto,
 640                              const ip46_address_t *next_hop,
 641                              u32 next_hop_sw_if_index,
 642                              u32 next_hop_fib_index,
 643                              u32 next_hop_weight,
 644                              fib_route_path_flags_t path_flags)
 645 {
 646     /*
 647      * 1 is it present
 648      *   yes => remove source
 649      *    2 - is it still sourced?
 650      *      no => cover walk
 651      */
 652     fib_route_path_t path = {
 653         .frp_proto = next_hop_proto,
 654         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 655         .frp_sw_if_index = next_hop_sw_if_index,
 656         .frp_fib_index = next_hop_fib_index,
 657         .frp_weight = next_hop_weight,
 658         .frp_flags = path_flags,
 659     };
 660     fib_route_path_t *paths = NULL;
 661
 662     fib_table_route_path_fixup(prefix, &path);
 663     vec_add1(paths, path);
 664
 665     fib_table_entry_path_remove2(fib_index, prefix, source, paths);
 666
 667     vec_free(paths);
 668 }
 669
 670 static int
 671 fib_route_path_cmp_for_sort (void * v1,
 672                              void * v2)
 673 {
 674     return (fib_route_path_cmp(v1, v2));
 675 }
 676
 677 fib_node_index_t
 678 fib_table_entry_update (u32 fib_index,
 679                         const fib_prefix_t *prefix,
 680                         fib_source_t source,
 681                         fib_entry_flag_t flags,
 682                         fib_route_path_t *paths)
 683 {
 684     fib_node_index_t fib_entry_index;
 685     fib_table_t *fib_table;
 686     u32 ii;
 687
 688     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 689     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 690
 691     for (ii = 0; ii < vec_len(paths); ii++)
 692     {
 693         fib_table_route_path_fixup(prefix, &paths[ii]);
 694     }
 695     /*
 696      * sort the paths provided by the control plane. this means
 697      * the paths and the extension on the entry will be sorted.
 698      */
 699     vec_sort_with_function(paths, fib_route_path_cmp_for_sort);
 700
 701     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 702     {
 703         fib_entry_index = fib_entry_create(fib_index, prefix,
 704                                            source, flags,
 705                                            paths);
 706
 707         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 708         fib_table->ft_src_route_counts[source]++;
 709     }
 710     else
 711     {
 712         int was_sourced;
 713
 714         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 715         fib_entry_update(fib_entry_index, source, flags, paths);
 716
 717         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 718         {
 719             fib_table->ft_src_route_counts[source]++;
 720         }
 721     }
 722
 723     return (fib_entry_index);
 724 }
 725
 726 fib_node_index_t
 727 fib_table_entry_update_one_path (u32 fib_index,
 728                                  const fib_prefix_t *prefix,
 729                                  fib_source_t source,
 730                                  fib_entry_flag_t flags,
 731                                  fib_protocol_t next_hop_proto,
 732                                  const ip46_address_t *next_hop,
 733                                  u32 next_hop_sw_if_index,
 734                                  u32 next_hop_fib_index,
 735                                  u32 next_hop_weight,
 736                                  mpls_label_t *next_hop_labels,
 737                                  fib_route_path_flags_t path_flags)
 738 {
 739     fib_node_index_t fib_entry_index;
 740     fib_route_path_t path = {
 741         .frp_proto = next_hop_proto,
 742         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 743         .frp_sw_if_index = next_hop_sw_if_index,
 744         .frp_fib_index = next_hop_fib_index,
 745         .frp_weight = next_hop_weight,
 746         .frp_flags = path_flags,
 747         .frp_label_stack = next_hop_labels,
 748     };
 749     fib_route_path_t *paths = NULL;
 750
 751     fib_table_route_path_fixup(prefix, &path);
 752     vec_add1(paths, path);
 753
 754     fib_entry_index =
 755         fib_table_entry_update(fib_index, prefix, source, flags, paths);
 756
 757     vec_free(paths);
 758
 759     return (fib_entry_index);
 760 }
 761
 762 static void
 763 fib_table_entry_delete_i (u32 fib_index,
 764                           fib_node_index_t fib_entry_index,
 765                           const fib_prefix_t *prefix,
 766                           fib_source_t source)
 767 {
 768     fib_entry_src_flag_t src_flag;
 769     fib_table_t *fib_table;
 770     int was_sourced;
 771
 772     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 773     was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 774
 775     /*
 776      * don't nobody go nowhere
 777      */
 778     fib_entry_lock(fib_entry_index);
 779
 780     src_flag = fib_entry_delete(fib_entry_index, source);
 781
 782     if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 783     {
 784         /*
 785          * last source gone. remove from the table
 786          */
 787         fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 788
 789         /*
 790          * now the entry is no longer in the table, we can
 791          * inform the entries that it covers to re-calculate their cover
 792          */
 793         fib_entry_cover_change_notify(fib_entry_index,
 794                                       FIB_NODE_INDEX_INVALID);
 795     }
 796     /*
 797      * else
 798      *   still has sources, leave it be.
 799      */
 800     if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 801     {
 802         fib_table->ft_src_route_counts[source]--;
 803     }
 804
 805     fib_entry_unlock(fib_entry_index);
 806 }
 807
 808 void
 809 fib_table_entry_delete (u32 fib_index,
 810                         const fib_prefix_t *prefix,
 811                         fib_source_t source)
 812 {
 813     fib_node_index_t fib_entry_index;
 814
 815     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 816
 817     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 818     {
 819         /*
 820          * removing an etry that does not exist.
 821          * i'll allow it, but i won't like it.
 822          */
 823         clib_warning("%U not in FIB", format_fib_prefix, prefix);
 824     }
 825     else
 826     {
 827         fib_table_entry_delete_i(fib_index, fib_entry_index, prefix, source);
 828     }
 829 }
 830
 831 void
 832 fib_table_entry_delete_index (fib_node_index_t fib_entry_index,
 833                               fib_source_t source)
 834 {
 835     fib_prefix_t prefix;
 836
 837     fib_entry_get_prefix(fib_entry_index, &prefix);
 838
 839     fib_table_entry_delete_i(fib_entry_get_fib_index(fib_entry_index),
 840                              fib_entry_index, &prefix, source);
 841 }
 842
 843 fib_node_index_t
 844 fib_table_entry_local_label_add (u32 fib_index,
 845                                  const fib_prefix_t *prefix,
 846                                  mpls_label_t label)
 847 {
 848     fib_node_index_t fib_entry_index;
 849
 850     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 851
 852     if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
 853         !fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
 854     {
 855         /*
 856          * only source the prefix once. this allows the label change
 857          * operation to work
 858          */
 859         fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
 860                                                           FIB_SOURCE_MPLS,
 861                                                           FIB_ENTRY_FLAG_NONE,
 862                                                           NULL);
 863     }
 864
 865     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);
 866
 867     return (fib_entry_index);
 868 }
 869
 870 void
 871 fib_table_entry_local_label_remove (u32 fib_index,
 872                                     const fib_prefix_t *prefix,
 873                                     mpls_label_t label)
 874 {
 875     fib_node_index_t fib_entry_index;
 876     const void *data;
 877     mpls_label_t pl;
 878
 879     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 880
 881     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 882         return;
 883
 884     data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);
 885
 886     if (NULL == data)
 887         return;
 888
 889     pl = *(mpls_label_t*)data;
 890
 891     if (pl != label)
 892         return;
 893
 894     pl = MPLS_LABEL_INVALID;
 895
 896     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
 897     fib_table_entry_special_remove(fib_index,
 898                                    prefix,
 899                                    FIB_SOURCE_MPLS);
 900 }
 901
 902 u32
 903 fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
 904                                      u32 sw_if_index)
 905 {
 906     switch (proto)
 907     {
 908     case FIB_PROTOCOL_IP4:
 909         return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
 910     case FIB_PROTOCOL_IP6:
 911         return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
 912     case FIB_PROTOCOL_MPLS:
 913         return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
 914     }
 915     return (~0);
 916 }
 917
 918 flow_hash_config_t
 919 fib_table_get_flow_hash_config (u32 fib_index,
 920                                 fib_protocol_t proto)
 921 {
 922     switch (proto)
 923     {
 924     case FIB_PROTOCOL_IP4:
 925         return (ip4_fib_table_get_flow_hash_config(fib_index));
 926     case FIB_PROTOCOL_IP6:
 927         return (ip6_fib_table_get_flow_hash_config(fib_index));
 928     case FIB_PROTOCOL_MPLS:
 929         return (mpls_fib_table_get_flow_hash_config(fib_index));
 930     }
 931     return (0);
 932 }
 933
 934
 935 u32
 936 fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
 937                                         u32 sw_if_index)
 938 {
 939     fib_table_t *fib_table;
 940
 941     fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
 942                                   proto, sw_if_index),
 943                               proto);
 944
 945     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
 946 }
 947
 948 u32
 949 fib_table_find (fib_protocol_t proto,
 950                 u32 table_id)
 951 {
 952     switch (proto)
 953     {
 954     case FIB_PROTOCOL_IP4:
 955         return (ip4_fib_index_from_table_id(table_id));
 956     case FIB_PROTOCOL_IP6:
 957         return (ip6_fib_index_from_table_id(table_id));
 958     case FIB_PROTOCOL_MPLS:
 959         return (mpls_fib_index_from_table_id(table_id));
 960     }
 961     return (~0);
 962 }
 963
 964 u32
 965 fib_table_find_or_create_and_lock (fib_protocol_t proto,
 966                                    u32 table_id)
 967 {
 968     fib_table_t *fib_table;
 969     fib_node_index_t fi;
 970
 971     switch (proto)
 972     {
 973     case FIB_PROTOCOL_IP4:
 974         fi = ip4_fib_table_find_or_create_and_lock(table_id);
 975         break;
 976     case FIB_PROTOCOL_IP6:
 977         fi = ip6_fib_table_find_or_create_and_lock(table_id);
 978         break;
 979     case FIB_PROTOCOL_MPLS:
 980         fi = mpls_fib_table_find_or_create_and_lock(table_id);
 981         break;
 982     default:
 983         return (~0);
 984     }
 985
 986     fib_table = fib_table_get(fi, proto);
 987
 988     fib_table->ft_desc = format(NULL, "%U-VRF:%d",
 989                                 format_fib_protocol, proto,
 990                                 table_id);
 991
 992     return (fi);
 993 }
 994
 995 u32
 996 fib_table_create_and_lock (fib_protocol_t proto,
 997                            const char *const fmt,
 998                            ...)
 999 {
1000     fib_table_t *fib_table;
1001     fib_node_index_t fi;
1002     va_list ap;
1003
1004     va_start(ap, fmt);
1005
1006     switch (proto)
1007     {
1008     case FIB_PROTOCOL_IP4:
1009         fi = ip4_fib_table_create_and_lock();
1010         break;
1011     case FIB_PROTOCOL_IP6:
1012         fi = ip6_fib_table_create_and_lock();
1013         break;
1014      case FIB_PROTOCOL_MPLS:
1015         fi = mpls_fib_table_create_and_lock();
1016         break;
1017    default:
1018         return (~0);
1019     }
1020
1021     fib_table = fib_table_get(fi, proto);
1022
1023     fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);
1024
1025     va_end(ap);
1026     return (fi);
1027 }
1028
1029 static void
1030 fib_table_destroy (fib_table_t *fib_table)
1031 {
1032     vec_free(fib_table->ft_desc);
1033
1034     switch (fib_table->ft_proto)
1035     {
1036     case FIB_PROTOCOL_IP4:
1037         ip4_fib_table_destroy(&fib_table->v4);
1038         break;
1039     case FIB_PROTOCOL_IP6:
1040         ip6_fib_table_destroy(fib_table->ft_index);
1041         break;
1042     case FIB_PROTOCOL_MPLS:
1043         mpls_fib_table_destroy(&fib_table->mpls);
1044         break;
1045     }
1046 }
1047
1048 void
1049 fib_table_walk (u32 fib_index,
1050                 fib_protocol_t proto,
1051                 fib_table_walk_fn_t fn,
1052                 void *ctx)
1053 {
1054     switch (proto)
1055     {
1056     case FIB_PROTOCOL_IP4:
1057         ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
1058         break;
1059     case FIB_PROTOCOL_IP6:
1060         ip6_fib_table_walk(fib_index, fn, ctx);
1061         break;
1062     case FIB_PROTOCOL_MPLS:
1063         mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
1064         break;
1065     }
1066 }
1067
1068 void
1069 fib_table_unlock (u32 fib_index,
1070                   fib_protocol_t proto)
1071 {
1072     fib_table_t *fib_table;
1073
1074     fib_table = fib_table_get(fib_index, proto);
1075     fib_table->ft_locks--;
1076
1077     if (0 == fib_table->ft_locks)
1078     {
1079         fib_table_destroy(fib_table);
1080     }
1081 }
1082 void
1083 fib_table_lock (u32 fib_index,
1084                 fib_protocol_t proto)
1085 {
1086     fib_table_t *fib_table;
1087
1088     fib_table = fib_table_get(fib_index, proto);
1089     fib_table->ft_locks++;
1090 }
1091
1092 u32
1093 fib_table_get_num_entries (u32 fib_index,
1094                            fib_protocol_t proto,
1095                            fib_source_t source)
1096 {
1097     fib_table_t *fib_table;
1098
1099     fib_table = fib_table_get(fib_index, proto);
1100
1101     return (fib_table->ft_src_route_counts[source]);
1102 }
1103
1104 u8*
1105 format_fib_table_name (u8* s, va_list ap)
1106 {
1107     fib_node_index_t fib_index = va_arg(ap, fib_node_index_t);
1108     fib_protocol_t proto = va_arg(ap, int); // int promotion
1109     fib_table_t *fib_table;
1110
1111     fib_table = fib_table_get(fib_index, proto);
1112
1113     s = format(s, "%v", fib_table->ft_desc);
1114
1115     return (s);
1116 }
1117
1118 /**
1119  * @brief Table flush context. Store the indicies of matching FIB entries
1120  * that need to be removed.
1121  */
1122 typedef struct fib_table_flush_ctx_t_
1123 {
1124     /**
1125      * The list of entries to flush
1126      */
1127     fib_node_index_t *ftf_entries;
1128
1129     /**
1130      * The source we are flushing
1131      */
1132     fib_source_t ftf_source;
1133 } fib_table_flush_ctx_t;
1134
1135 static int
1136 fib_table_flush_cb (fib_node_index_t fib_entry_index,
1137                     void *arg)
1138 {
1139     fib_table_flush_ctx_t *ctx = arg;
1140
1141     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1142     {
1143         vec_add1(ctx->ftf_entries, fib_entry_index);
1144     }
1145     return (1);
1146 }
1147
1148
1149 void
1150 fib_table_flush (u32 fib_index,
1151                  fib_protocol_t proto,
1152                  fib_source_t source)
1153 {
1154     fib_node_index_t *fib_entry_index;
1155     fib_table_flush_ctx_t ctx = {
1156         .ftf_entries = NULL,
1157         .ftf_source = source,
1158     };
1159
1160     fib_table_walk(fib_index, proto,
1161                    fib_table_flush_cb,
1162                    &ctx);
1163
1164     vec_foreach(fib_entry_index, ctx.ftf_entries)
1165     {
1166         fib_table_entry_delete_index(*fib_entry_index, source);
1167     }
1168
1169     vec_free(ctx.ftf_entries);
1170 }